Estou trabalhando com correlação 2D para técnicas de processamento de imagem (reconhecimento de padrões, etc ...). Fiquei me perguntando se existe uma abordagem teórica sobre como saber quando usar a multiplicação no espaço de frequência sobre a correlação no espaço de tempo. Para tamanhos de 2 x espaço de freqüência é, obviamente, mais rápido, mas como sobre tamanhos pequenos nobres, como, por exemplo, 11?
Suponho que isso esteja sendo feito em uma CPU convencional, um núcleo, executando um thread simples, sem hardware sofisticado. Se houver mais do que isso acontecendo, provavelmente pode ser explicado com ajustes no raciocínio de um sistema mais simples. Não se pode dizer muito mais sem um sistema específico para discutir ou um livro inteiro ou um trabalho de pesquisa para cobrir uma gama de possibilidades.
Eu não me preocuparia com tamanhos de dois em dois. Não importa. Algoritmos de FFT com unidades borboleta e tudo o que existe para fatores de 3, ou qualquer número pequeno, não apenas 2. Existem algoritmos inteligentes para séries de dados de tamanho médio também. Não gosto de citar a Wikipedia sobre isso devido à sua natureza impermanente, mas de qualquer maneira:
existem FFTs com complexidade O (N log N) para todos os N, mesmo para N primos
As implementações de FFTs para N arbitrário podem ser encontradas na biblioteca da GPL, FFTW .
A única maneira confiável em termos de engenharia séria é construir e medir, mas certamente podemos ter uma idéia da teoria, para ver as relações entre variáveis. Precisamos de estimativas de quantas operações aritméticas estão envolvidas para cada método.
A multiplicação ainda é mais lenta que a adição na maioria das CPUs, mesmo que a diferença tenha diminuído tremendamente ao longo dos anos, então vamos contar as multiplicações. Contabilizar também a adição exige um pouco mais de reflexão e acompanhamento das coisas.
Uma convolução direta, na verdade multiplicando e adicionando usando o kernel de convolução, repetindo para cada pixel de saída, precisa de multiplicações W² · K², em que W é o número de pixels ao longo de um lado da imagem (assumindo quadrado por simplicidade) e K é o tamanho do núcleo de convolução, como pixels ao longo de um lado. São necessárias multiplicações de K² para calcular um pixel de saída usando o kernel e a parte do mesmo tamanho da imagem de entrada. Repita o procedimento para todos os pixels de saída, com o mesmo número da imagem de entrada.
(N mults ) direto = W² · K²
Para fazer o trabalho no espaço de Fourier, precisamos transformar a imagem. Isso é feito aplicando uma FFT a cada coluna separadamente e depois a cada linha. O FFT para N pontos de dados leva cerca de 2N · log (N) multiplicações; queremos que N seja W, o comprimento de uma coluna ou linha. Todos os logaritmos aqui são de base dois.
Existem W linhas e colunas W, portanto, depois que todas as FFTs estiverem concluídas, fizemos multiplicações de 2W · (2W · log (W)). Dobro disso, porque depois que multiplicamos pela transformação de Fourier do kernel, precisamos inverter-Fourier os dados para voltar à imagem sensível. Isso é 8W² · log (W). Obviamente, é necessário fazer a multiplicação pela transformação de Fourier do kernel, outras multiplicações de W². (Feito uma vez, não uma vez por pixel de saída, por linha ou qualquer coisa.) Essas são multiplicações complexas, portanto, são multiplicações reais de 4W².
Então, a menos que eu tenha me enganado (e provavelmente o fiz), temos
(N pontos ) Fourier = 4W² · (2 · log (W) + 1)
Quando queremos fazer as coisas da maneira direta? Quando K é suficientemente pequeno para tornar W² · K² menor que 4W² · (2 · log (W) + 1). Um fator comum de W² é facilmente calculado. Provavelmente, podemos abandonar o "+1", pois estamos lidando com estimativas idealizadas. É provável que o +1 seja perdido em erros em relação às implementações reais, por não contar adições, sobrecargas de loop e assim por diante. Isso deixa:
K² < 8·log(W)
Essa é a condição aproximada para a escolha de uma abordagem direta sobre uma abordagem de espaço de frequência.
Observe que a correlação de duas imagens do mesmo tamanho é como convolver com um núcleo de tamanho K = W. O espaço de Fourier é sempre o caminho para fazê-lo.
Isso pode ser refinado e discutido para dar conta de sobrecarga, canalização de opcodes, ponto flutuante vs. ponto fixo e jogado pela janela com GPGPU e hardware especializado.