Twice Told Tale: Properties and Applications of the 2D Fourier Transform

Anamorphic Property of FT of 2D patterns

Anamorphic property of FT is shown where a wide pattern has a long FT and a long pattern has a wide FT. This is shown in figure 1. Also, two dots along x produces a sine along y.

Figure 1. Anamorphic property of FT. The left panels refers to the 2D patterns. The right panels refers to the FT of each pattern. a) Tall rectangle apperture produces a wide FT. b) a wide rectangle aperture produces a tall FT. c)  Two dots along x-axis symmetric about the center produces an airy pattern with a superimposed sinusoidal signal along y.  d) The frequency of the sinusoidal signal decreases when the spacing between the dots is decreased.

Rotation Property of the FT

For a sinusoidal signal, the produced FT will be two peaks centered at zero. The peak corresponds to the frequency of the signal. Higher frequency shows that the peaks move farther away from the center as shown in figures 3 and 4. A constant signal will have an FT with a peak at zero since a constant signal can be thought of as a sine with a very low frequency. Therefore, when a sine has a constant bias, a peak at the center will be observed in the FT. When the bias in a sine is also a sine with a lower frequency, peaks nearer the center will be observed in the FT, corresponding to the frequency or the bias. These are all seen in figure 2. In this case, the higher peaks corresponds to the frequency of the main sine signal. So for sinusoidal signals with bias, to obtain the frequency of the main sine signal, a low pass filter can be used mask off the peaks near the center and to isolate the peak corresponding to the main signal.

Figure 2. FT of sines. Left panels refer to the sinusoidal signals. Right panels refer to the FT. a) Sine centered at zero. The FT has two peaks along y centered at zero. b) Sine with a contant bias. FT aside from the two symmetric peaks, also has a peak at zero. c) Sine with a sinusoidal bias. FT has a peak at zero, two small peaks near the origin, and another two far from the origin.

Figure 3. FT of a sinusoid while increasing frequency. Increase in the frequency of the sine shifts the peaks in the FT farther from the origin.

Figure 4. FT of the sinusoid wil a constant bias. A peak at the center can be observed.

A rotated pattern produces an FT rotated in the same direction. This can be observed in figure 5. 

Multiplication of patterns produces an FT which is a convolution of the FT of the individual patterns. Figure 6(a) shows the multiplication of a sinusoidal along x and a sinusoidal along y. The FT of a sinusoid along x are two deltas along y, and the FT of a sinusoid along y are two dirac deltas along x. The produces FT in figure 6(a) left panel is a convolution of two dirac deltas along x with two dirac deltas along y. Combining this again with a rotated sinusoid produces an FT with peaks along a rotated axis. 

Figure 5. Rotating the sinusoid rotates the FT at the same angle. 

Figure 6. Combination of sinusoids. a) Combining a horizontal and a vertical sinusoid (right panel) produces a FT with peaks along X and along Y. b) Combining a rotated sinuoid with the figure in (a) (right panel) produces the same FT but now with peaks along a rotated axis. 

Convolution Theorem Redux

In this part the convolution will be more emphasized. The FT of two dirac delta of one pixel as a peak, is a sinusoid. Convolving a dot of some radius with the dirac delta has an Airy pattern with a superimposed sinusoidal FT. For a square convolved with the two dirac deltas, the FT is a sine along x and along y with a superimposed sine signal. For a gaussian convolved with the two dirac deltas, the FT is a gaussian superimposed with a sine signal. This are all shown in figure 7. Increasing the size of the shape convolved with the two dirac deltas, decreases the size of the FT, as can be seen in figures 8-10. 

Figure 7.  The 2D patterns (left panel) and its FT (left panels). a) binary image of two dots with one pixel each produces a very big FT with a superimposed sine. b) Replacing the dots with circles produces an Airy pattern with a sine of the same frequency. c) Replacing the dots with squares produces a sinusoidal along the center of x and y with a super imposed sine of the same frequency as in (a) and (b). d) replacing the dots with gaussians produces one gaussian with superimposed sine same as in (a), (b), and (c). 

Figure 8. FT of two dots with increasing radius. The size of the FT is inversely proportional with the radius of the circle. 

Figure 9. FT of two squares with varying width. The thickness of the FT is inversely proportional to the width of the squares. 

Figure 10. FT of two gaussian is a gaussian with a super imposed sine. Increase n the variance of the gaussian decreases the size of the FT. 

Figure 11 shows the effect of the convolution of a pattern with a dirac delta. This results to an imprint of the pattern at the location of the dirac delta. Figure 11 a) is the convolution of randomly placed dirac deltas with a paw print and a mickey mouse head. Note that the resulting convolution has an increased dimension with the original. The convolution of an NxN matrix with dirac deltas with an nxn pattern results to an N+n-1 by N + n-1 matrix. The placement of the pattern is the relative location of the dirac delta with the center. The convolution in figure 11 a) can be used as an acitivity for finding the hidden mickey. Figure 11 b) is a more challenging convolution since the r, g, and b channels has to be preserved. To do this, I convolved the R, G, and B channels of the colored flower pattern with the randomly placed dirac deltas shown in the left panel. The background of each colored flower pattern was segmented using a threshold. The segmentation however is not perfect especially for the white flower since the background of each colored flower pattern is white. A mask was made so that areas already placed with a flower will not be added with another pattern. Without the mask, the colors of the flowers will be destroyed, since the steps were done separately for each R, G, and B channel. Figure 11 c) increased the dirac deltas and the flower patterns. This method could be used for fast creation of colorful floral patterns. 

Figure 11. Convolution of a pattern (right panels) with dirac deltas at random locations (left panels). 

Equally spaced dirac deltas produced equally spaced FT. The spacing however is opposite for each FT pair. A widely spaced pattern will have a narrowly spaced FT. This is shown in figure 12. 

Figure 12. FT of equally spaced ones. The increase in the spacing of the ones in the pattern produces a decrease in the spacing of the ones in the FT. 

Fingerprints: Ridge Enhancement

For a fingerprint, the information are in the ridges of the pattern. The fingerprint however has ink blotches, making the pattern inaccurate. To recover the ridges in the fingerprint, a mask can be used in the FT to preserve the circular peaks corresponding to the ridges. This is shown in figure 13. 

Figure 13. Ridge enhancement of a fingerprint. a) The fingerprint. b) The FT showing a circular ring near the center. c) Isolating the circular ring and the peak at the center using a mask. d) The inverse FT of (c) capturing the ridges of the fingerprint. 

Lunar Landing Scanned Pictures: Line removal

Repeating lines can also be removed with the knowledge that the FT of repeating lines are peaks along x or along y. A mask covering the peaks spanning vertically and horizontally in the FT can be used as shown in figure 14. The resulting image from the inverse FT in figure 14 d) shows a cleaned image where the lines were removed. Care should be observed however since some sharp edges which are part of the picture got smoothed out due to some removed signals in the image. 

Figure 14. Line removal of a lunar landing image. a) The scanned image. b) The FT showing peaks spanning horizontally and vertically along the center. c) Removing the peaks using a mask. d) The cleaned image. 

Canvas Weave Modeling and Removal

For paintings or other materials printed in a canvas, the texture of the canvas messes up with the information contained in the material. From scanned painting, there is a repeating pattern which seems to be not included in the painting. This repeating pattern is similar to the patterns in figure 6. A mask should be created to remove twin peaks of the combined sinusoidal signals. Figure 15 d) shows a clean image. The FT of the peaks removed by the mask, is a weave pattern as shown in figure 15 e). 

Figure 15. Removal of canvas weave in a scanned painting. a) The painting. b) the FT of the image. c) Removal of the peaks corresponding to the canvas using a mask. d) The cleaned image. e) The inverse FT of the peaks removed in (b). f) The result of subtracting the cleaned image from the original image. 

For this work, I give myself 10/10 since i completed all the necessary activities. I would like also acknowledge Justin, Chloe and Ado for helping me with some parts.

Mark Twain once said that history doesn't repeat itself, but it does rhyme. - Albert-László Barabási

Fourier for Today: Fourier Transform Model of Image Formation

Fourier transform is a wonderful linear transform which converts a signal into its inverse dimension. For a signal with dimensions of space, FT converts it to a signal of spatial frequency. For a 2D image, the FT is given in the equation below.  A powerful implementation of FT is the fast fourier transform algorithm which is fft2() in matlab and something similar in other packages. This function however has different properties and we should be careful in using them.

For our 186 subject, it is a required skill to be familiar with and to know by heart the fourier transform of different patterns. There are a few get away tips to easily familiarize oneself on FT. first is that the FT of a pattern is in inverse dimension of those of the pattern. From here, we can say that when the pattern is long then the FT is short or when the pattern is short the FT will be long. The FT of a small aperture will be wide. Second is that when the pattern is rotated, the FT will be in the same rotation. Last is that the product of two patterns will have a FT of the sum of the individual FT of the patterns. It is also important to note that the FT of an FT of a pattern is the pattern itself, so a pattern and its FT is somehow like a pair. So now, we look at FT of some basic patterns. 

Figure 1 shows the FT of a circle. 1(a) is the circle. This pattern could be thought of as a circular aperture. Figure 1(b) is the output of the FFT algorithm, which is not yet center shifted. This should always be noted in using FFT algorithms from packages. The function fftshift() can fix it. Figure 1(c) is the FFT of the circular aperture, which is an Airy pattern. Note that the pattern is medium sized, producing a medium size FT. Figure 1 (d) is the FT of the Airy pattern in figure 1 (c) showing that the FT of the FT of the circle is a circle. It should be noted also that the FT of a function is complex. Figure 2 shows the real and imaginary parts of the FT. 

Figure 1. The FT of a circular aperture. (a) the circular aperture. (b) The pattern produced by the FFT algorithm. (c) The FT of the pattern. (d) the inverse fourier transform of the FT. 

Figure 2. The complex FT of letter A. (a) the pattern A. (b) The FT of the pattern. (c) The FT of the FT of the pattern. (d) The real part of the FT of the pattern. (e) The complex part of the FT of the pattern. 

Figure 3. a) A sinusoid along x (corrugated roof) b) The FFT of the sinusoid which is a two dirac deltas and a direct delta at the center 0. 

Figure 3 shows the FFT of a sinusoid along x, which is a two dirac delta with peaks corresponding to the frequency of the sinusoidal signal. For the fourier series, any signal can be expressed as a linear superposition of weighted sines and cosines of different frequencies. The fourier transform shows the distribution and the relative strengths of sinusoids in the signal. In this case, the frequency as which the sinusoid was made is at the peak of the dirac delta, which is the sinusoid with the highest strength. The spread of the dirac delta shows the other available signals. A constant signal is like a sinusoid with a very low frequency, which has an FFT of dirac deltas very near the center 0. So for a constant signal, the FFT is at the center. A double slit however, as seen in figure 4, can be thought of as a many dirac delta signals along the y axis centered at x = 0. It’s FFT will be a sinusoid along x-axis. Another signal that can be thought of as a superposition of many sinusoids is a square pattern. The FFT is a sinusoidal signal forming a cross. Since the square is wide along x and along y, the FFT is thin and long along x and y. 

Figure 4. The double slit and its FFT which is a sinusoid along the x-axis but confined only along y = 0.

Figure 5. Square and its FFT, which are sinusoids along x and y forming a cross

A Gaussian bell curve will always have a Gaussian as its FFT. A small pattern will have a big FFT. This is shown in figure 6. 

Figure 6. The FFT pair which is a small and big 2D Gaussian bell curve

Simulation of an imaging device

Convolution is used in imaging such that the resulting convolution of 2 patterns looks like both the 2 patterns. The result is like the smearing of one pattern to the other. For an object, the resulting image taken by an imaging device is the convolution of the object and the transfer function of the imaging device.

It is also essential to note that the FFT of a convolution is the product of the individual FFT of two patterns. With this in mind, to determine the FFT of a difficult pattern, the pattern could be broken down to easy patterns with known FFT and obtain the product of the FFTs.

In the next part, we will simulate an imaging device. For a digital camera for example, the finite lens radius limits the gathered rays reflected from the object, making the reconstruction imperfect.

We have an object which is the letters VIP in Arial font. The imaging device is shown by a white centered circle. In figure 7, radius of the imaging device was increased from left to right. The increase in the radius of the imaging device reblurred the reconstructed image. The greater the radius, the better the quality of the produced image. This can be observed also in a video bellow where the radius of the aperture increases. 

Figure 7. The convolution of the letters VIP and a circle with varying radius. a) r = 0.1 b) r = 0.3 c) r = 0.5 d) r = 0.7 e) r = 0.9

Template matching using correlation

Correlation is another tool used to look into the degree of similarity of two patterns. The high the correlation at a certain pixel implies that the patterns are identical at that point. This can used for template matching or pattern recognition. For the activity, we used a template with the text: “THE RAIN IN SPAIN STAYS MAINLY IN THE PLAIN” in Arial 12. The letter “A” typed also in Arial 12 was correlated with the pattern. The center of the bright spots show the center of the location of the letter “A”.

Figure 8. Template matching using the correlation of a letter to a pattern. a) The pattern used. b) the letter A was detected in the pattern. c) The brightest spots in the correlation shows the centers of the location of the occurrence of A in the pattern in (a). 

Another template matching application if the edge detection in an image using an edge pattern. The edge patterns used are 3x3 matrices such that the total sum of the elements is zero. Figure 9 shows the edge patterns used and its convolution with the VIP image. As can be seen the white pixels in the convolution represents the areas at which the image and the edge pattern matches. For the horizontal pattern (a) the horizontal lines were not seen while the vertical lines were not seen when using the vertical pattern (b). The slant and curve edges for (a) and (b) looks pixelized and was badly connected. A clean detection was done by the spot (c). For the diagonal patterns in (d) and (e), the verticals and the horizontal lines were not detected.

Figure 9. The edge patterns used (upper panel) and its convolution with the image VIP (lower panel) the edge patterns are: a) horizontal b) vertical c) spot d) diagonal with a negative slope e) diagonal with a positive slope. 

For this activity, I would give myself 10/10 for the activity. In general, this activity is not that fun, however, among all the activities, I enjoyed looking at the edge detection results in images and the template matching using correlation. I did it for the exploration part. However, I did not get to finish the template matching.

At first I thought that the correlation would be a nice technique to be used for handwriting character recognition such that a program can recognize each letter from an image of text. However, changing the font and the size of the template letter would not make it detectable for the program anymore. Good thing however, I did center shifting using the centroid of the letters before doing the correlations so that shifting the location of the template letter from the center would still make it detectable since. In figure 10, I correlated all the letters in the text with the text image. My plan is to correlate each letter to the image and the peak locations would mean that the letter occurred in that location. The program will then reconstruct the text in the image using the letters and the peak locations basing on the index. The spacing between the words would be neglected. The problem however is for letters with high correlations. A nice example would be the letter I, where it detected 14 peak locations instead of 6.

Figure 10. The correlations (shown in the lower panels) of the image in figure 8 a) with the letters (shown in the upper panels). 

For the edge detection, I planned on using only the spot edge pattern since the results in the VIP image is clean, however, when using it alone, the resulting edges are not continuous and smooth. It also detected some undesired edge which created noise in the image. So for this, I added each of the resulting convolutions of the image with the edge patterns (horizontal, vertical, spot, diagonal with a negative slope, and diagonal with a positive slope) and applied a threshold to clean the image. I compared the technique to the edge detection package in Matlab using the Prewitt algorithm. The results are shown in figures 11 and 12. The edge detection method is shown in column b while the Prewitt algorithm is shown in column c.

Figure 11. The application of edge detection method to the images in column a) using convolution with the edge patterns (column b) compared with the Prewitt algorithm (column c)

Figure 12. Another application of the edge detection method to the images in column a) using convolution with the edge patterns (column b) compared with the Prewitt algorithm (column c)

For the images in figure 11, the results of the convolution is better compared with the Prewitt algorithm since most of the essential details were overlooked by the Prewitt algorithm such as the jaws of the kid, the outline of its face, etc. The result of the convolution however is messier as can be observed in the uppermost panel. 

For the images in figure 12, the Prewitt algorithm produced cleaner and better results. Some edges, especially in the middle panel, were omitted by the convolution method while it was perfectly outlined by the Prewitt. 

To improve this method, one can think of a way to give weights to the effect of convolving different patterns in  the image. The identification of the threshold for each image could also be automatically known using the histogram of the intensity.

I would like to thank Elijah Justin Medina for all the creative ideas which either he shared or was inspired by him. I cannot accurately remember some, but there sure are a lot of things he contributed into the making of this activity.

Beyond the edge of the world there’s a space where emptiness and substance neatly overlap, where past and future form a continuous, endless loop. And, hovering about, there are signs no one has ever read, chords no one has ever heard. - Haruki Murakami, Kafka on the Shore