Fourier Transform Model of Image Formation

The key feature of the Fourier Transform is it converts a signal with dimension x into a signal with dimension 1/x. So, for a signal that has dimensions of space, its fourier transform is a signal with inverse space or spatial frequency as its dimension. Given an image f(x,y), its Fourier Transform is given by

equation 1: Equation for the Fourier Transform of a function f(x,y).

where fx and fy are the dimensions of the signal in fourier space. Cooley and Tukey developed an algorithm that can implement the Fourier Transform efficiently and quickly. It's so powerful that most of the signal and image processing software have their algorithm. In Scilab, to implement the Fourier Transform, fft() for 1-D signal and fft2() for 2-D signal is used.

I. Familiarization

Figure 1: Fourier Transform of a circle. In Scilab, the function fft2() used to derive the circle's Fourier Transform.


Figure 2: Fourier Transform of the letter A. Take note that it is a capital A. fft2() of Scilab was also used.

Figure 1 shows the fourier transform of a circle. This image is produced using the algorithm developed by Cooley and Tukey. It is consistent with the theoretical Fourier Transform of a circle. Figure 2 shows the fourier transform of letter A, capital letter A. Given that for a circle, its correct Fourier Transform was derived using the algorithm developed by Cooley and Tukey, it is safe to assume that figure 2 also presents the correct Fourier Transform of a capital letter A.

It is important to note that two of the key properties of the FFT() algorithm is that 1) the output of fft2() has quadrants along the diagonal interchanged and 2) the output of fft2() is a complex number array. Because of these two properties, the functions fftshift() and abs() are used. fftshift() reverts back the original arrangement of the quadrants and abs() displays the intensity distribution of the image, computing only the modulus of the complex number array.

Figure 3: Inverse Fourier Transform of Figure 1. This image is also equivalent to taking the fourier transform of a circle twice.


Figure 4. Inverse Fourier Transfrom of Figure 2. Again this image is equivalent to taking the fourier transform of the image of letter A twice.

As noted in the caption of figures 3 and 4, the Inverse Fourier Transform is just done by taking the fourier transform of the image twice. Theoretically, doing this method results in an image that is inverted when compared to the original image, as seen in figure 4. In order to explain this, take note of the exp(-i..) term in equation 1, with such term, taking the FT twice results in an equation with a term ..-i*-i.. which is equal to -1, this -1 is the reason why taking the FT twice results in an inverted image of the original one.

II. Simulation of an Imaging Device

Figure 5: Circle. This image represents the aperture of a circular lens.


Figure 6: Word VIP. This represents the object to be viewed through the aperture of the circular lens.

Convolution, according to Wolfram, is an integral that expresses the amount of overlap of one function, g, as it is shifted unto another function, f. Equation 2 shows how one function is convoluted unto another function in mathematical form.

Equation 2: Convolution between the function f(x,y) and g(x,y)

According to the handout given by Dr. Soriano, Convolution is actually a linear operation, which actually means that if f and g are recast by linear transformations, in this case the Fourier Transformation, these function obey the convolution theorem in which

H = FG

where H, F and G are Fourier Transforms of h, f and g respectively.

Convolution is used to model the linear regime of instruments or detection devices used in imaging processes. Say the object is given by the function f(x,y) and the transfer function of the imaging device is given by g(x,y), their convolution, which is h, is then the image produced by the detection system, which, in general, will never be exactly the same as the original object. This is most especially the case in real systems in which the aperture of the imaging device has a finite size. Due to this 'limitation', not all rays containing the information of the object passes through the aperture and hence reconstruction of the original object is never perfect.

In this activity, figure 5 is treated as the aperture of the imaging device while figure 6 is treated as the object to be imaged. By taking advantage of the properties of Convolution, all that is needed to do is get the product of their individual fft's and then do an inverse fft to derive what is sought, which is the convolved image of figure 5 and figure 6. It is important to take note that figure 5, the aperture, is already in the spatial frequency domain and deriving its fft is not needed.

figure 7: Effect of increasing aperture size on the convolved image. The aperture size started out with a radius of 1% of the total pixel size and is gradually increased up to an aperture size with radius about 99% of the total pixel size.

Figure 7 simulates the effects of real systems, wherein the size of an aperture can greatly affect the quality of the convolved image. The greater is the size of the aperture, the better is the quality of the image.

III. Template Matching using Correlation

Correlation, according to the handout given by Dr. Soriano, is a measure of the degree of similarity between two function f and g. The more identical they are at certain position (x,y) the greater is their correlation value. The correlation between two 2-dimensional functions is given by equation 3.

Equation 3: Correlation between f(x,y) and g(x,y)

Similar with convolution, correlation also has a theorem which holds for linear transforms of f and g and it states that

P = F*G

where P, F and G are, in this case, Fourier transforms of p, f and g respectively.The asterisk (*) above F indicates complex conjugation, meaning, F* is a complex conjugate of F. It is also important to note that if one of the functions is an even function, then correlation is just equal to the convolution.

An important application of the correlation concept is template matching. Template matching is actually a pattern recognition technique which finds identical patterns in a scene or in this case, finding identical letters in a sentence.

Figure 8: The sentence to be examined. The sentence is of font Arial with font size 12.


Figure 9: Image of letter a. For this case, it is written of font Arial with font size 12.

Take note of the correlation theorem and let f be the image in figure 8 while g be the image in figure 9. By taking their individual Fourier Transforms and using the conj() function in Scilab, the correlation theorem can then be implemented and the result is displayed on figure 10. It is important to solve for the inverse Fourier Transform of P in order to determine the correlation between figure 8 and figure 9.

Figure 10: Correlation between Figure 8 and Figure 9. The high intensity colors(white) indicate a high correlation between the two images, figure 8 and 9.

Recall the sentence in figure 8 and determine where the letters a are in the sentence. Notice that in their locations, a high intensity color (white) can be observed. This observation actually indicates a high correlation between the images in figures 8 and 9. So, by using the correlation theorem and its concept, the location of the letter a and its quantity was obtained. Notice that there are also relatively high correlation spots (but not as high as the ones in letter a) in the location of the letters that looks like a, in this case, the letters e and , in some degree, p. This suggests that using this method to differentiate certain patterns, or in this case, letters, may not be very efficient without further analysis of the correlated image. At first glance, errors in calculation and analysis may occur, thus it is important to further process figure 10 in order to properly distinguish letter a from the sentence.

IV. Edge Detection
Another import application of the convolution and correlation concept is Edge Detection. Edge Detection is actually a template matching of an edge pattern with an image. In this case, the edge pattern is a 3x3 arbitrary matrix whose total sum is zero. The following figures show the results of convolving figure 6 (the image VIP) to an arbitrary edge pattern.

figure 11: Convolving the 'VIP' image with the matrix [-1,-1,-1;2,2,2;-1,-1,-1].


figure 12: Convolving the 'VIP' image with the matrix [-1,2-1;-1,2,-1;-1,2,-1]


figure 13: Convolving the 'VIP' image with the matrix [-1,-1,-1;-1,8,-1;-1,-1,-1]

Notice the effect of convolving the arbitrary matrix on the image VIP, depending on the arbitrary matrix, certain edges the the image VIP can only be seen.

Technical Correctness: 5/5. The concepts and equations used were adequately explained.

Quality of Presentation: 5/5. The images are posted with high quality complete with captions fully explaining the image

Overall Score: 8/10. Due to late posting, a deduction of 2 points is given.