Fourier Transform Model of Image Formation

This activity will be about Fourier Transform and its applications in imaging. I used Scilab to perform the Fourier Transform on the images. This activity is composed of four parts: discrete FFT familiarization, convolution, template matching using correlation and edge detection.

For the first part of this activity, we generated certain shapes: a circle, the letter “A”, a sinusoid along the x-direction (corrugated roof), a simulated double slit, a square aperture and a 2D Gaussian bell curve.

Figure 1. Circle generated from Scilab

Figure 2. The letter “A” made from MS Paint

Figure 3. Sinusoid along x-direction generated from Scilab

Figure 4. Simulated double slit generated from Scilab

Figure 5. Square aperture generated from Scilab

Figure 6. Gaussian bell curve generated from Scilab

After generating these images, I applied 2D Fourier Transform on each of them. Note that the result for the fourier transform will be complex and will have a real and imaginary part. By taking the absolute value of the values that I got from applying the FFT, I will get its modulus.

Figure 7. FFT of circle

Figure 8. FFT of the letter “A”

Figure 9. FFT of the sinusoid along the x-direction

Figure 10. FFT of the double slit

Figure 11. FFT of the square aperture

Figure 12. FFT of the Gaussian curve

The physical interpretation of Fourier transform in Optics is like a lens which follows the criteria below:

Figure 13. The physical interpretation of Fourier Transform Retrieved from: cns-alumni.bu.edu

The lens above takes the Fourier transform of the input image. The resulting image at the screen will then be the Fourier image. Note that the input image must be of a distance f from the lens where f is the focal length of the lens. Likewise, the resulting image must also be of the same distance f from the lens on the other side. It is observed that rays are coning out of the input image and because the image is at the focus, the output rays are parallel to each other and producing the Fourier image on the screen [1]. This will make sense later on in this activity.

Conversely, it works with input parallel rays:

Figure 14. Parallel rays concentrate after passing through the lens Retrieved from: cns-alumni.bu.edu

Basically, the first part is just for the familiarization of the Fourier transforms of common patterns. A circular aperture will produce a transform of a circle with rings around it. As seen from Figure 13 and Figure 14, if the image is small, the transform will be big and likewise, if the image is big, the transform will be small. This also applies to the letter “A”. A bigger letter would lead to a smaller transform.

For the sinusoid, the Fourier transform also shows peaks on all frequencies inside the sinusoid just like on the 1D Fourier Transform of a sine wave. The smaller the frequency is, the closer the peak is to the middle peak. The middle peak in Figure 9 signifies the bias that I applied on the sinusoid.

For the double slit, it will show a pattern similar to that of Young’s double slit experiment. The diffraction pattern is dependent on the slit width and the length of separation.

For the square aperture, it is similar to the circular aperture. Several ring-like patterns are observed but is incomplete due to the corner of the square. Also, a bigger square leads to a smaller transform and vice versa.

Lastly, the Gaussian bell curve is somewhat similar to the circular aperture. Another circular shape can be seen on the Fourier transform. The difference is that the transform of the bell curve does not have rings around it. This is because the value of the bell curve anywhere does not become zero. A unique property about the Gaussian bell curve is that its transform is also a Gaussian bell curve.

For all these Fourier transforms, I performed another Fourier transform on them and resulted in the original image but is rotated 180°.

The second part of this activity deals with convolution. I created a 128×128 image of the letters “VIP” as shown below.

Figure 15. The letters “VIP”

I also generated a circular aperture and used fftshift() on it. I then performed Fourier transform on the image with the “VIP”. I multiplied the two resulting images and again, performed the second Fourier transform on it. The results were:

Figure 16. The convolved image with the radius of circle equal to 0.1

Figure 17. The convolved image with the radius of circle equal to 0.4

Figure 18. The convolved image with the radius of circle equal to 0.7

Figure 19. The convolved image with the radius of circle equal to 1

The difference in these images is their resolution. A smaller circular aperture leads to an image of lower resolution and a bigger aperture leads to an image of higher resolution.

The third part of the activity is about template matching using correlation. I created a 128×128 image of the statement “THE RAIN IN SPAIN STAYS MAINLY IN THE PLAIN” using Paint. I also made a separate 128×128 image of the letter “A” of the same font and size as the A’s from the above statement. I placed the “A” in the middle of the image.

Figure 20. The image of the statement mentioned above

Figure 21. The letter “A” to be used in template matching

I took the Fourier transforms of both images and multiplied the Fourier transform of “A” to the conjugate of the Fourier transform of the statement. I performed another Fourier transform on the resultant image and got:

Figure 22. The resultant image after performing the second Fourier transform

It is noticeable that the resultant image is somewhat similar to that of the original image but is very blurry. Another observation is that five very white points can be seen on what appears to be where the letter “A”s are located. This technique is called correlation. By applying a filter on the code, I can eliminate rest of the image and only the five white points remain.

Figure 23. Filtered image of Figure 22

The last part of this activity is about edge detection using correlation. I used the same image in Figure 15. I also generated three 128×128 matrices with different types of 3×3 patterns in the middle. I created a horizontal pattern, vertical pattern and dot pattern. I repeated the same procedure on the third part of the activity with the statement now being the letters “VIP” and the letter “A” now being the pattern.

Figure 24. Resultant image for the horizontal pattern

Figure 25. Resultant image for the vertical pattern

Figure 26. Resultant image for the dot pattern

This technique scans the whole image and searches it for a pattern similar to the pattern given as observed from part 3. The dot pattern can be used for edge detection of certain shapes because of the work it did in Figure 26.

But this activity will not end with me not trying something new. I leaned that the correlation technique allows us to scan the whole image and search of the similar pattern it has been given. I tried this technique on the famous game called “Where’s Waldo?”. I made a program dedicated to it but unfortunately, the one I tried with the colored version of the game does not return good results so I only did it with a black and white version of the game. First, I tried to find Waldo on the image and isolated him and created a new file of the same size as the original one with only Waldo in the middle and covered in black background.

Figure 27. Where’s Waldo?

Figure 28. There’s Waldo!

I used correlation to find Waldo and the resulting image is:

Figure 29. Resultant image of “Where’s Waldo?”

Although it is unclear but A white peak can be seen encircled by the red circle. If I map it to the original image of “Where’s Waldo?”, it is where Waldo should be located. I can say that this technique really is helpful.

References:

[1] S. Lehar. An Intuitive Explanation of Fourier Theory. Retrieved: September 15, 2015 from http://cns-alumni.bu.edu/~slehar/fourier/fourier.html

Review:

First of all, I would like to thank everyone who helped me in finishing this activity. I thank Ms. Eloisa Ventura for guiding me to get the correct results for this activity. I would also like to thank Ma’am Jing for the additional guidance and for confirming everything.

Secondly, I enjoyed this activity because for me, this is brand new information. Making the code is also fun because I have interest in programming. If I were to rate myself in this activity, I would give myself a 10 + 2 so a 12 for experimenting on the popular game “Where’s Waldo?”.

Appendix:

The codes I used for activity 5