Transformada Rápida de Fourier

Pelas equações 3.8 e 3.9, pode-se notar que a transformada discreta de Fourier, bem como sua inversa, são um tanto caras computacionalmente. De fato, a transformada discreta de Fourier possui uma complexidade de tempo quadrática O($N^2$), sendo $N$ o tamanho do sinal ou o número total de pixels em uma imagem.

Porém, quando o tamanho do sinal $x$ é uma potência de 2, pode-se aplicar um algoritmo chamado Transformada Rápida de Fourier (``Fast Fourier Transform'' - FFT), baseado em um método chamado dobramentos sucessivos [Gonzalez and Woods, 1992]. A ordem de complexidade de execução desse algoritmo é de O($N log_2 N$), sendo, portanto, altamente eficiente se comparado à transformada de Fourier discreta comum.

Esse algoritmo torna possível a aplicação da transformada de Fourier para imagens ou padrões de alta dimensionalidade. Para se fazer uma comparação prática, foi realizado um teste utilizando o software MatLab, que possui a FFT implementada. Foram criados dois sinais aleatórios (ou seja, contendo apenas ruídos) $x_1$ e $x_2$. O sinal $x_1$ possui tamanho $2^{23}$ e $x_2$ possui uma dimensão a menos que $x_1$, ou seja, o tamanho de $x_2$ é $2^{23} - 1$. O tempo levado para obter-se a transformada de Fourier de $x_1$ foi de 10,8198 segundos. Já o tempo levado para realizar a mesma tarefa em $x_2$ (o qual é menor que $x_1$, mas cujo tamanho não é uma potência de 2) foi de 128,8102 segundos.