6. Fourier Transform Model of Image Formation

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.

(a) Binary image, (b) its FT (c) shifted FT by fftshift() and (d) reconstruction of the FT by fft2()

Fourier transforms of circles with increasing radius

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.

(a) Image of letter "A", (b) its FT by fft2(), (c) shifted FFT and (d) its reconstruction by fft2()

Simulation of an imaging device

Imaging "VIP" with increasing aperture size

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.

(a) Image of template, (b) text of interest and (c) and template matching. The locations of the template "A" is indicated by the bright points in the resulting image.

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

Edge detection (bottom row) with various patterns (top row).

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!

Edge detection by SIP's edge() function

On a side note, SIP includes built-in colormaps that can enhance the details of a Fourier transform.

SIP colormaps (a) hsv, (b) jet, (c) hot and (d) sip 12

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.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s