Activity 7 - Fourier Transform Model of Image Formation

This activity served as an introduction to manipulating images in the frequency domain to enhance or remove certain parts of an image.

Brief background: basically the Fourier Transform is a linear transform of a function f(x) into F(k) through the following equation:

In App Phy 183 and App Phy 185 we applied the Fourier Transform on various time-domain signals (sound, etc.) to convert them into frequency domain. Now, we apply the two-dimensional FT to an image to obtain the spatial frequency of an image:

However, this integral can be approximated by the Fast Fourier Transform (FFT) algorithm, which is basically the discrete FT, and is widely used in many computational and image processing programs like Python and Scilab. Now this exercise is a familiarization to the fft() and fft2() functions of Scilab.

First I created a white circle centered on a black background and took its FT using fft2(). However, we still need to apply fftshift() to obtain the correct form of the image, because the application of fft2() causes the resulting image to be "wrapped around". fftshift() corrects the image.

 

Figure 1. (a) Image of a circle. (b) FT of a circle using fft2(). (c) Zoom in at the center of the image in b. (d) Reconstructed circle using ifft().

im = imread(path+'\circle.jpg');
ft = fft2(im);
imshow(mat2gray(fftshift(abs(ft))));    //to show the image properly
ift = ifft(ft);                         //reconstruct the image
imshow(mat2gray(abs(ift)));

The result seems like a white dot at the center, but if we zoom ~200% we will be able to see a rough Airy pattern, which is the result if we solve for the FT of a circle analytically. Now we have confirmed that we indeed obtain the analytic FT by just applying fft2() on our images.

Now we want to recover our circle by either applying ifft() (inverse FT) or applying fft2() again to the image. The result is the same, however ifft() recovers the original image while fft2() recovers a flipped version of the image. For this case, the result is not yet apparent since our image is a circle.

Next, we repeat the same process for an image of the letter A (white on black). Here the difference between applying ifft() and applying fft2() twice is evident:

Figure 2. (a) Image of the letter A. (b) FT of the letter A. (c) Reconstructed image by applying fft2() again. (d) Reconstructed image by applying ifft().

Next we examine the convolution of two images. In signal processing, the convolution of two signals basically is like overlaying the two signals and combining them to create one signal that looks like its two "components". The 2-d convolution integral is given by

In the Fourier space, however, the convolution operation becomes a multiplication:

Taking the convolution of two images is like simulating an imaging device such as a digital camera, with one of the images acting as the aperture, and the other is the actual image being obtained. Here, I first created an image showing the letters "VIP" (white on black) and created another image of a circle with radius r = 0.1. Then I take the FT of the VIP image and multiply it with the circle element-wise. The reason why we no longer took the FT of the circle is that we assume the circle is already the FT of the aperture. Also, I varied the radius and observed the results:

Figure 3. (a) Original VIP image. (b) Convolution of VIP image with circle of r = 0.1 (c) Convolution of 

VIP image with circle of r = 0.3 (d) Convolution of VIP image with circle of r = 0.6(e) Convolution of VIP

image with circle of r = 1.1

convolution = apert .* fft2(im);
imshow(mat2gray(abs(ifft(convolution)))); 

We can see here that as the radius is increased, the sharpness of the image also increases. Next, I also took the correlation between two images, given by

which in Fourier space becomes a multiplication:

where F* is the complex conjugate of F. Correlation is used in template matching when you want to know how similar the two images are. In this example, we have an image of a simple rhyme, and we find how many times the letter "A" appeared in the rhyme. I multiplied the conjugate of the FT of the rhyme with the FT of the letter A and displayed the output as shown below. In addition, I also tried if we will be able to locate two- and three-letter patterns and entire words.

 Figure 4. (a) Original image of the rhyme. (b) Image of the letter A, centered at a black background.

(c) Result of template matching using correlation, showing all positions of 'A'.

 Figure 5. (a) Image of the word 'IN'. (b) Positions of the word 'IN'

as detected by correlation.

 Figure 6. (a) Image of the word 'AIN'. (b) Positions of the word

'AIN' as detected by correlation.

 Figure 7. (a) Image of the word 'SPAIN'. (b) Positions of the word

'SPAIN' as detected by correlation.

correlation = conj(fft2(rhyme)) .* fft2(pattern);imshow(mat2gray(abs(ifft(correlation))));

Lastly, I also used convolution to detect the edges in the VIP image used before. The technique is to multiply a matrix pattern where the total sum of the elements is equal to 0. I tried four patterns: horizontal, vertical, diagonal and spot pattern, and the results are shown below.

 Figure 8. Edge detection using (a) horizontal pattern; (b) vertical pattern; (c) diagonal pattern; (d) spot pattern. It can

be seen that the pattern finds the edge that is most similar to it, which explains why the first image only has horizontal

lines, the second one only has vertical lines, etc.

edge = fft2(im) .* fft2(pattern);imshow(mat2gray(abs(ifft(edge))));

Grade I give myself: 11/10. Although I finished this activity relatively early, I was not able to post a blog entry immediately. However, I was also able to extend the template matching to two letters, three letters and words.