Activity 6 - Deeper into the Fourier Transform (Properties and Applications of the 2D Fourier Transform)

After the last post, I thought I had enough of the Fourier transform for a while. Partly the reason why it took me so long to put up this write up (I'm so sorry Ma'am! =( ). But anyway, it's time to dive even deeper into the fourier transform!

ANAMORPHISM

What is anamorphism? Cool sounding word, but in the context of the fourier transform (FT), what does it really mean? A quick Merriam Webster search on the meaning of the word "anamorphic" gives us exactly what we want. It defines the word anamorphic as:

"producing, relating to, or marked by intentional distortion (as by unequal magnification along perpendicular axes) of an image"

-Merriam Webster

So what does this really mean in terms of the fourier transform? As demonstrated in my last blog post, the fourier transform of images of circles of increasing radii are circular airy patterns of decreasing radii (though the definition of the "radius" of an airy pattern is used pretty loosely here). This stems from the mathematical result that the FT space is the inverse dimension of the spatial domain.  What the "circles example" in the last post tells us is that what is wide along an axis in the spatial domain is narrow along the same axis in the spatial frequency domain. Furthermore, from this same example, this seems to be the case for all possible axes that pass through the center of the image (and there's nothing that could indicate otherwise anyway). 

To test this theory, let's take the fourier transform of some sample test images generated in Scilab. These are displayed in Figure 1. 

Figure 1. Shown in the upper row are pattern images generated in Scilab which include (a) a vertical rectangle, (b) a horizontal rectangle, (c) two dots along the horizontal spaced far apart, and (d) two dots along the horizontal spaced near to each other. In the second  row are the corresponding fourier transforms.

Looking at Figure 1a and its corresponding FT in Figure 1e, we see that the narrowness along the horizontal axis in the test image results in a widely spread pattern along the horizontal in its FT. Furthermore, the wideness along the vertical direction in the spatial domain results in a narrow pattern being formed along the same direction in the spatial frequency domain. This is consistent with the horizontally oriented rectangle and its FT in Figures 1b and 1f. As an added insight, we can also explain the continuity of results from the FT in Figures 1e and 1f using the rotation property of the two-dimensional fourier transform, but more on this later!

Interestingly enough, this anamorphic property can be used to explain the sinusoidal patterns that result from applying the FT to two dots. The explanation, however, may not be as tastefully intuitive. Consider the widely spaced apart dots in Figure 1c and the narrowly spaced apart dots in Figure 1d. A quick observation that most people make is that a narrower spacing between dots results in wider spaced "fringes" in its FT. The two dots are practically infinitely narrow and thus from the anamorphic property of the FT, we would expect the resulting FT pattern to be infinitely wide in all directions. This, of course, is obvious for the vertical directions, but what of the other directions? Does the anamorphic property not hold here? What's important to remember is that each dot produces its own Airy pattern and due to the anamorphic property of the FT, we would expect the concentric Airy patterns to be infinitely wide. The infinite wideness of the individual airy patterns is responsible for the infinite wideness along the vertical. Along other directions, however, we must take into account the superposition of the pixel values from the individual airy patterns (remember that this superposition takes place BEFORE plotting with imshow()). It just so happens, as in the double slit experiment, the patterns combine to form sinusoidal fringes along the axis on which the dots lie.

I also found it quite interesting to try and see the "continuity" between FT patterns as the original test image was changed. For this, consider the gif below.

Figure 2. Shown above are the test images (left) and the resulting fourier transforms (right). The test images are of two dots with decreasing spacing in between them.

Consistent with the previous results, we see that the narrower the space between the two dots, the wider the spaces between fringes in fourier space. Moreover, it's interesting to see that when the spacing is zero (or when the dots combine to form a single dot), the resulting FT output is that of a completely white image. If you haven't realized it yet, this is consistent with the fact that the FT of an impulse function is a constant!

Additional Properties of the Fourier Transform

Moving on, we tackle another interesting property of FT: its rotation property. To do this, we consider using sinusoidal test images. However, before anything else, let's digress slightly and consider the two cases that will shed some more light on the FT of images in general. Consider Figure 3. 

Figure 3. Shown on the left is the FFT output of a sinusoidal image that was generated, saved, and then reread into the program. Shown in the right is the FFT output of a sinusoidal image that was processed directly after its generation. . Note that both sinusoidal test images used were of exactly the same frequency and amplitude. 

Since both are FTs of the same sinusoidal image, why does one exhibit spectral leakage while the other produces ideal results? The problem lies in the fact that digitally stored images have no negative values. Thus, by generating, saving and then rereading the sinusoidal image into the program before finally taking its fourier transform, we essentially clip our generated sinusoidal signal. In the fourier domain, this clipping results in the apparent presence of higher frequency signals as shown in above (right image). This issue, however, can be circumvented by applying the FT directly after the test image array is generated in order to avoid signal clipping. This way, we obtain the true predicted result (without any spectral leakage) as shown in Figure 3 (right image).

So from the previous demonstration, we saw that the occurrence of spectral leakage in the FT of an image containing only sinusoidal signals can be explained by considering the unavoidable clipping of negative values when the original images are saved. Thus, as long as we apply the fourier transform directly after generating the pixel values (without saving and then reopening the image) of the original image, this problem shouldn't come up. So I proceeded to take the fourier transform of sinusoids of different frequencies.

Figure 4. Shown are sinusoidal test images (left) and the resulting FT outputs (right). Note that "spectral leakage" in the FT occurs for only some test images. The frequencies of the sinusoids are integer multiples of 2π. 

First off, we see that the results are consistent with the trend suggested by the results in Figures 1c and 1d given the fact that the application of the fourier transform twice reverts the image back to the spatial domain (see my previous blog post). Intriguingly, it is observed that spectral leakage occurs for some of the test images despite the fact that the "fix" mentioned earlier was implemented. 

So what's happening? Notice that the spectral leakage only occurs for some test images. Furthermore, we see that there is some periodicity to the appearance of the spectral leakage as the frequency of the sinusoidal signal within the test image is changed at interger multiples of 2π. For some seemingly special sinusoidal frequencies, there is practically no spectral leakage, as is expected! Hopefully, after watching the above gif (enough times), one should realize that the test images with sinusoidal patterns that were "cut properly" in the vertical direction are the only ones that yield FT with ideal spectral leakage free patterns! 

Consider the two cases taken from the gif (Figure 4) shown below.

Figure 5. "Stiched" sinusoidal images (top) and the resulting FT results from one half of the stitched image.

Shown in Figure 5 are two images each with a sinusoidal pattern of a different frequency. Let's say the patterns on the right are of frequency A while the ones on the B are of frequency B. To prove a point, I duplicated the test images and stitched them one on top of the other. Notice how after duplicating and stitching the pattern of frequency A, there is no break in the periodicity of the pattern formed. In other words, we still end up with an image with a signal of frequency A, albeit being double in length along the original. Looking at the pattern of frequency B, however, we notice that there is an obvious "break" or discontinuity in the steady sinusoidal pattern after the stitching process. Coincidentally, the resulting FT of the original test image has significant spectral leakage! Thus, to put it plainly, it seems as the "cutting" of the sinusoidal pattern by the finite dimensions of the image has a significant effect on the amount of spectral leakage present in the FT patterns. This is analogous to a problem I encountered last semester (Applied Physics 185?) while using the 1-D FT. We must remember that the FT assumes that the signal being analyzed is infinitely periodic and thus essentially "stitches" together duplicates of the original sample taken. Thus, the observable spectral leakage in the pattern of frequency B is due to the FT detecting the discontinuity in the stitched image. Notice how if we instead stitch the duplicates side by side, there is no discontinuity in the pattern as the sinusoid is oriented along the vertical. Correspondingly, for both patterns, we don't observe spectral leakage on all other axes except the vertical.

So now that we've found possible causes of spectral leakage, what are possible ways to prevent this? Because negative pixel values are clipped in real digital images (assuming the image is "cut" properly), what we can do is to add a DC bias to the image to prevent this clipping. Take a look at Figure 6. 

Figure 6. The fourier transform of a sinusoidal pattern with an increasing DC bias added. The test images used were sinusoidal patterns with varying levels of DC bias.  

As shown in Figure 6, the FT starts off with no DC bias and significant spectral leakage to higher frequencies as a result of the clipping of negative values. Addition of a bias, however, shifts the original sinusoidal signal up to yield less and less clipping. This, of course, results in less and less spectral leakage, as well as the occurrence of a central bright spot in the generated FT. Note also that as the DC bias is increased, the central bright spot gets brighter and brighter while the peripheral spots get dark and darker. This is just a result of the scaling down of the peripheral pixel values as the maximum pixel value of the image increases (the DC bright spot) due to the mat2gray() function.

Now suppose we take a picture of the interferogram from a double slit experiment. Being encoded in a digital image, we would not only expect the presence of a DC signal (due to the average brightness of the image), but also some spectral leakage. How then can we determine the actual frequency of the sinusoidal pattern produced? We make use of the fact that although significant spectral leakage may occur, the magnitude of this leakage still pales in comparison with the magnitude of the main frequencies of the image. Thus, we can eliminate the spectral leakage by binarizing the images using an appropriate threshold pixel value. This was done in Figure 7 using a Scilab generated sinusoidal image (one of the images used previously).

    

Figure 7. Shown above are the FT of a generated sinusoidal image (left) and the result after the binarization procedure.

Note how the low magnitude pixel values in the generated FT are not present in the binarized result. Thus, only the significant spectral contributions are emphasized.

Now suppose we add in non constant biases in the form of very low frequency sinusoids. How then can we get the actual frequencies of the interferogram?

Figure 8. Shown above are the interferogram with added non constant biases (leftmost), the resulting FT (middle) and the processed FT to isolate the actual frequencies (rightmost).

To circumvent this (using the fact that we have prior knowledge that the added biases are non constant sinusoids), we simply just set the value of the pixels around the center of the image to zero and apply the binarization procedure presented earlier. This was done in Figure 8. Another interesting observation is that the addition of low frequency sinusoids to the original interferogram led to a FT composed of the superposition of the individual FT patterns of each sinusoid.

Let's consider rotating the sinusoid and observing it's output.

Figure 9. Shown above are sinusoidal test images rotated at different angles (left) and the corresponding fourier transform (right). 

We see that as the sinusoid is rotated, the corresponding fourier transform is rotated as well! Although this rotation property of the FT may seem like an entirely different property, this is simply a result of the anamorphic quality of the FT. Remember: "What is wide along one axis in the spatial domain is narrow along the same axis in the spatial frequency domain". Rotation of the sinusoid just changes the directions of these axes!

Now let's try looking at the FT of combinations of a sinusoids. We consider the FT of the product of two sinusoids along axes directed at different angles.

Figure 10. Shown are both the product of two sinusoids (with equal frequencies) along different directions (left) and the resulting FT patterns (right).

What we see here is that the pattern formed by the product of two sinusoids of equal frequencies leads to FT patterns that imitate grid patterns. Furthermore, we see that the grid patterns seem to lean in the same direction as the spatial domain patterns. When the sinusoids are along perpendicular axes (like the horizontal and vertical axes), we obtain a square grid. We therefore expect that adding more sinusoids with frequencies that are integer multiples of each other along these two axes will generate an extended square gird. 

Now, let's try to add some rotated sinusoids to our product of sinusoids pattern.

Figure 11. Shown above are both the combination of sinusoids (left) pattern and the resulting FT (right).

Were you able to predict the FT pattern on the right? 

Despite the fact that complete prediction of the FT of a given pattern is very difficult (especially in the cases wherein the pattern is a superposition of many different sinusoids), the important takeaway is that given any pattern that forms some sort of repetitive grid, we can expect the resulting FT pattern to be some arrangement of dots positioned symmetrically about the center of the image.

CONVOLUTION THEOREM REDUX

Now we move on to another very interesting property of the FT. We know from the previous parts that the fourier transform of two equally placed dots is that of a sinusoid as shown in Figure 12.

Figure 12. Two equally spaced dots (left) and the resulting FT pattern. 

What if we, instead of varying the distance between the dots, changed their shapes? Consider now the various gifs in Figure 13.

Figure 13. Test patterns are on the left while the resulting FT patterns are on the right

Very interesting!!! We see that we get the usual Airy patterns associated with circles, squares and Gaussians (as we saw in the last blog post as well), and yet it seems to be "modulated" by the FT pattern of the two equally spaced dots shown earlier. Going back to the physical interpretation of the FT transform as the process behind diffraction phenomena, we see that this strange property of the FT is consistent with what is observed in double slit experiments. Particularly, for finite double slits, we expect to not only see the usual interference fringes, but also the modulating envelope function due to diffraction. In our case, the shape of the slits provides the "envelope" function while the interference effects result from the double nature of the slits. 

Moving on,  we consider the convolution between a centered test pattern and an image with randomly placed 1's. Take a look at Figure 14. 

Figure 14. Shown above are a test pattern (left), ten randomly situated "dirac deltas" (middle), and the convolution between the two (right).

Note that the randomly spaced 1's are approximations for the dirac delta function! It just so turns out that the convolution between dirac deltas and any test pattern leads to the pattern appearing at the dirac delta points within the convolution result! This is a rather cool geometrical way to think of the convolution with a dirac delta function that is absent from the 1-dimensional approach.

Lastly, let's take a look at the FT of grid patterns.

Figure 15. Test grid patterns in the first column and the corresponding FT patterns in the second column.

We see once again the anamorphic property of the FT! Notice how the wider the spaces between the dots in the spatial domain, the smaller the spaces are between the dots in the spatial frequency domain. This trend is seen for both test images used. I could not, however, explain the occurence of the central vertical line in the image.

SOME FILTERING EXAMPLES

Now that we have a rather solid understanding of many of the properties and principles of the fourier transform, let's take a look at some concrete real world examples where we can apply our knowledge.

The FT can be used to filter out unwanted features in an image. Particularly, it is especially useful when the unwanted feature has some periodicity iwthin the image. Consider the lunar orbiter space photo shown in the upper left corner of Figure 16. 

Figure 16. Shown are the original photo (upper left), the logarithm of its FT (lower left), and the processed images along with the filters used in the second and third columns. 

The horizontal lines in the original photo are results of the stitching of the individual strips of photo taken. As shown in its fourier transform, these horizontal lines are represented by a strong vertical line passing through the center of the spectrum. Note that, due to the range of large range of intensity values in the spatial frequency domain of the image, the logarithm of the FT was shown instead. There is also an evident horizontal line in the spatial frequency spectra although no visible vertical lines are present in the original photo. Thus, to remove the unwanted feature, we simply multiply generated filters and then reapply the FT to change the image back to the spatial domain. Notice that the filters used above leave a space in the middle so as not to filter out the DC component of the image. Doing so will drastically reduce the brightness of the original image, something we don't want to do. Moreover, I decided to block out the "ringing" lines as well by placing thinner lines positioned about the main filter lines. Looking at the second column of images, we see that hastily removing both the strong vertical and horizontal lines results in a processed image that is free of the horizontal lines, yet is slightly discolored when compared to the original. As shown in the third column, however, removal only of the vertical line in the spectra results in the disappearance of the horizontal lines in the original image, but at the same time, retaining most of the quality of the original image.

As a second example, let's consider processing a photo of a painting. In the painting shown in Figure 17, we see that the canvas dominates most of the detail within the scene. There is some periodicity to this canvas, however, and thus we attempt to remove this using FT filtering. For this special case, I applied the filtering technique to each individual RGB channel and then recombined the channels using GIMP.

Figure 17. Shown are the original painting (upper left), the logarithm of the fourier transform (upper middle), the filter used (upper right), the filtered photo (lower left), the white balanced filtered photo (lower middle), and the FT of  the original image after application of the inverse of the filter shown in the upper right (lower right).

As shown in Figure 17, the FT of the painting reveals several bright spots. Driven by our observations earlier with the combinations of sinusoids, we can guess that the periodic canvas pattern must be represented by symmetrically placed dots in the fourier domain. Note that the constrast of the FT shown was enchanced to make it easier to filter out the unwanted features. Using the filter in the upper right of Figure 16, we obtain the processed image in the lower left. Note, however, that although the canvas pattern was removed, the colors of the processed image seem a bit off compared to the original image. Inevitably, some of the color was filtered out. This is further verified by the "grid image" obtained by using the inverse filter on the original photo. We see that some color was lost in the filtering process. Inspired by my App Phy 187 lessons, I attempted to restore the colors in the original photo by white balancing (see the lower middle photo) the processed photo. This, however, was in vain. Still, it looks better to me! HAHA

The last filtering example that I'd like to consider is that of cleaning a fingerprint. Often times, digitally acquired fingerprints need to be processed in order for fingerprinting matching algorithms to work properly. Shown in Figure 18 is the summary of the process I implemented to enhance the ridges of a scanned fingerprint.

Figure 17. Summary of the process of enhancing the ridges in a fingerprint

Taking the FT of the original scanned fingerprint, we see that the pattern consists of fairly concentric rings. This is to be expected if we think about the ridges of the fingerprint as the "fringes" encountered so many times in this blog post. Moreover, because the ridges form rough ellipses, we expect their FT equivalents to be ellipses as well. Interestingly, the FT also shows lines cutting across the ellipse. Using the filter in the middle of the photo, we retain only the elliptical rings, and the DC component to obtain the processed fingerprint pattern (2nd from the right). Note that the filtering process was even able to remove the white background of the original scanned fingerprint! These regions, however, are not reliably accurate representations of the original scanned fingerprint. Thus, we apply a black mask patterned after the shape of the original fingerprint to obtain the final image on the rightmost part of Figure 17. Note that the image was binarized as well to enchance the contrast of the ridges. We see that the ridges are considerably enhanced! Moreoever, we see that the crease marks cutting horizontally across the original fingerprint are removed. The blotch marks are also considerably filtered out.

WHEW. Now that was a long post again. After two LONG blog posts, I feel now that I pretty much have a good grip on using the 2-D FT in (at least) the simplest of applications. I really feel I was able to tackle a lot of interesting points within this blog. For this reason, I'd give myself a 12/10.

ACKNOWLEDGEMENTS:

I'd like to acknowledge Mario Onglao's blog for giving me the idea to utilize gifs in my discussion. Not only did this help me consolidate a lot of the information nicely, but it actually brought up more questions that needed to be answered.