Fast Fourier Transform (FFT) é o nome do algoritmo que calcula a transformada de Fourier discreta para uma função em tempo O(n lg n). Essa é uma economia considerável se levarmos em conta o tempo de execução do algoritmo tradicional, ou seja, aplicando-se a fórmula da transformada diretamente aos dados. Essa implementação ingênua calcula a transformada em tempo O(n^2). Existem várias versões para algoritmo da FFT, e o mesmo foi descoberto independentemente por várias pessoas. Há registros de sua formulação desde 1805, por Gauss. No entanto foi apenas na década de 60 que sua aplicação foi redescoberta.
A aplicação do FFT é importante para a solução de vários problemas, como correlação e autocorrelação, filtragem ótima, estimativa de potência espectral e o cálculo de integrais de Fourier, entre outros. No nosso caso temos interesse na aplicação da FFT ao problema da convolução (e possivelmente deconvolução).
Este trabalho está assim estruturado:
Para este exercício foram utilizados o algoritmo da FFT e sua implementação descrita no livro Numerical Recipes in C.
Você pode encontrar o código dessa implementação aqui.
Costa & César, Shapes Analysis and Classification: Theory and Practice, CRC Press, 2001.
Gonzales & Woods, Digital Image Processing, 1993.
Press, Teukolsky, Vetterling & Flannery, Numerical Recipes in C, Second Edition, Cambridge University Press, 1992.