Discrete Fourier Transform (DFT) is a powerful tool for frequency-domain analysis of images. Cooley and Tukey formulated the algorithm that is the basis of the Fast Fourier Transform (FFT) found in current scientific computing applications.
FFT transforms a spatial image into spatial frequency spectra. Here is a short discussion on lenses as Fourier transformers (LOL at transformers). It described the lens as carrying-out a a 2-D Fourier Transform.
Discrete Fourier Transform
Taking a 128×128 image of a circle, application of fft2() will reveal a shifted Fourier transform. The image is split into four parts and each one is inverted with the center of the image turned out. fftshift() remedies this by reorienting the parts. Application of fft2() reconstructs this image.
Similarity theorem of Fourier Transforms seen visually.
Increase in spatial dimension results to a decrease in frequency-domain dimensions and overall amplitude of spectrum. In the previous figure, we have the Fourier transforms of circles from radius 0.1 to 0.7.
Cooley-Tukey Algorithm, Fast Fourier Transform and Data Reordering
For an N =N1N2 sized data, N1 DFTs are performed of size nd N2 twiddle factors are introduced and N2 DFTs of size N1 are performed. Recombining the smaller DFTs, we get reordered data. Hence, the need for fftshift().
Here is a discussion of the Cooley-Tukey Algorithm, data reordering and Butterfly diagrams.
The FT pattern is not necessarily similar to the original image. The FT reveals the spatial frequency of the image, thus, for a circle which is symmetric in all directions, the FT exhibits a similar symmetry. The letter A which shows a signature FT unlike the original image.
Simulation of an imaging device
The image and the lens are represented as matrices and are convolved. It appears that as the lens diameter increases, the simulated image improves. For smaller apertures, the FT is greater and the resulting image is dominated by the aperture’s FT. At larger apertures, the FT is smaller and the image is clearer. Physically, what happens is that the image diffracts through a smaller aperture and at larger diameters, diffraction at the aperture edges is minimal.
Correlation. discussion.
Template matching using correlation.
In the resulting image, the locations of the letter A were identified by bright spots. In frequency space, one can imagine that the spectra of A is squared, hence the bright spots.
Edge detection using convolution integral
Similar to template matching. Here we have an edge pattern. The code is able to identify the edges of the word VIP successfully. The detection is different for different patterns. SIP has a simple tool that accomplishes this successfully, edge(). Check out SIP macros in your Scilab contrib folder. Thumbs up to comprehensible docstrings!
On a side note, SIP includes built-in colormaps that can enhance the details of a Fourier transform.
References:
1. The Lens as a Fourier Transform System. Optical Engineering Laboratory, University of Warwick. 2001
2. A. Bovik. Handbook of Image and Video Processing. Academic Press 2000.
From the Panopticon 
Leave a comment