It is time to continue our work with the mighty Fourier Transform. Previously, on Activity #5, I showed how the Fourier Transform is related to a simple lens system, in which the object (which is the image generated using Scilab) is placed at the focus of the image. The corresponding image of the lens system is the Fourier Transform of the generated image from Scilab, which acts as a light aperture. The FT’s of the images were obtained via Cooley and Tukey’s Fast Fourier Transform (FFT) algorithm, which also has its own inherent properties. I have also shown the importance of FT in the computation of the convolution and correlation of two 2D signals. Moreover, the edge-detection techniques, which is used to detect locations where the brightness of an image sharply changes, were done using correlation and convolution using FT. You can always visit my previous post if all seems to be complicated.
Now, it is time to discover what lies beyond Fourier Transform. In this activity, I will engage into in-depth discussions on some of the FT’s acquired from the previous activity. I will also do corrections, most importantly on the sinusoids along the axes (corrugated roof), since there is a significant difference between the FT of an actual 2D signal and the FT of a grayscale image generated from Scilab. I will then utilize what we’ve known about FT to clean and filter out obstructions and unwanted patterns in images, while preserving the actual image. Yes, this is digital processing at its finest.
I. Anamorphic Property of FT of Different 2D Patterns
Woah, that’s quite an unusual word. According to Vocabulary.com, Anamorphism is a distorted projection or perspective, especially images distorted in such a way that it becomes visible or legible when viewed in a special way. I remember during my Physics 166 class, in the Year of the Light conference when me and my project partner, Jesli Santiago, worked on anamorphic optical images, which become undistorted whenever a cylindrical mirror was placed at the center of the image. People attending the conference had fun playing with it, and we had quite engaging discussions with them.
Enough with the sidetrack, let’s move on to anamorphic property of the Fourier Transform. We know that the FT maps a 2D function of spatial dimensions x and y to its spatial frequency domain, or in 1/x and 1/y dimensions. Thus, if the dimension of an aperture is prominent or large with respect to an axis, then its FT would have smaller dimensions with respect to that particular axis [1]. To start things off, let’s take a look first at the FT of circular apertures of varying radii. The aperture images used all have image dimension 128×128 pixels, and are generated in Scilab. The FFT code used is similar that in Activity #5.
Similar to the circular aperture in Activity #5, the FT of a circle is an Airy pattern, a pattern consisting of concentric circles with decreasing intensity as they deviate from the center due to constructive and destructive interference in a lens system. Irregularities in the outer circles are due the circular aperture being made up of pixels, thus they are not perfect curved line circles. Notice that the central intensities in Figs. 1a and 1b are larger than that of the proceeding circles. As the radius increases, the central region becomes smaller, and the Airy pattern becomes indistinguishable. By the nature of FT, the larger circles will have a smaller spatial frequency dimension. This is anamorphism in FT.
Let’s now look at images with different symmetries with respect to the major axes. Take a look at the tall rectangle and its FT below.
The tall rectangle has a longer height than its width, thus, the central intensity has a longer x-axis dimension (width) than that of the y-axis (height). Remember that the FT maps the image into its inverse dimension, or frequency, so a large dimension along the y-axis comes a smaller dimension in the 1/y space. Moreover, the FT shows a similar Airy pattern as observed from the square function in Activity #5. We can then extend this to a wide rectangle.
In this case, the y-axis (height) dimension of the central intensity in the FT is more prominent than that of the x-axis part (width). Again, this is due to FT’s anamorphism.
To further investigate of FT’s anamorphism, let’s consider the FT of two dots along the x-axis, symmetric with respect to the y-axis.
The two dots can be considered as two Dirac deltas (impulse signals) along the x-axis. These two impulse functions locates the coordinates of the frequency of a sinusoid signal along the x-axis. Thus, if one is to obtain its FT, we obtain a sinusoid signal along the x-axis in Fig. 4b, with its frequency determined by the location of the dots. I will discuss further the significance and principle behind sinusoids , dots and their FT’s on the next part, but for now, in the spirit of anamorphism, we investigate the effect of varying the distance between the two dots.
From Fig. 5a, the spacing between the dots is decreased, and the white bands increased in width. As the spacing is increased from Fig. 5b-5d, the white band spacing decreased. The signals then across the x-axis have their frequencies increased. The distance of the spacing between the dots is a dimension along the y-axis, thus, an increased spacing will result to a smaller white band width, which is also a y-axis dimension. The x-axis dimension was not changed. Again, anamorphism is detected. Curiously, there is certain pattern similar to all of the FT’s in Fig. 5. There’s a central intensity, in which a faint Airy pattern surrounds it, visible on the FT’s with high frequency sinusoids. Remember in Activity #5, where we investigated convolution? This faint Airy pattern is due to convolution. Later I will discuss this further, when we investigate convolution further.
It is also worth comparing this with the FT of a double slit in Activity #5. You can view this from my previous post. The FT contains a pattern similar to that obtained from Young’s double slit experiment, in which alternating dark and white bands were observed in a finite region. Since there is now a significant width and height for two dots separated, the sinusoid pattern is now visible in a smaller region, all thanks to anamorphism.
We now move on with another property of the FT, which is its rotation property.
II. Rotation Property of FT
Before we move on with the rotation property of Fourier Transform, let me discuss first the significance of FT in signal processing. Back in Applied Physics 185, we had a lot of activities regarding one-dimensional signals, which are time-dependent. The purpose of FT is to determine the frequency of the signal, which is very relevant in characterizing not just continuous signals, but also discrete time signals. The of FT of a 1D signal is then designated by two Dirac delta peaks, one positive frequency and the other negative of it (this is an inherent property of the FT algorithm). The magnitude of the location of the peaks is then the frequency of the signal.
Let me then extend this to 2D signals, in which there is a space-dependent signal not only in the x-axis, but also in the y-axis. But first, let us go back to the image of a sinusoid along the x-axis. I present here a code generating the sinusoid along the x-axis with a spatial frequency of f = 4, and its FT. The sine wave used is z = sin(2πft).
What happens here is that the true x and y values of the images were plotted. The usual FT of the graph is obtained, but the x and y axes of the FT were adjusted for a sinusoid of frequency 4 Hz. The frequency axes were calculated using Nyquist-Shannon Sampling Theorem. The plot has a specific value at each coordinate, which is represented by the z-axis. Thus, to plot the 3D graph, the mesh() function is used. Here are the results.
As you can see, the FT of the sinusoid are two dots (Dirac deltas), located at (x,y) = (4,0) and (-4,0). This signifies that the frequency along the x-axis is 4, and along the y is zero. This is consistent with our waveform. I added another graph in the code, which presents the 3D graph of the sinusoid, shown below.
This is to certify that the graph indeed extends along the z-axis, which has boundaries [-1,1]. Now, why did I even bother to show this. Well, one of our mistakes in obtaining the FT of images is that images don’t have negative values! This will give a huge effect in FT of images. To show this, I generated an image that utilizes the same sinusoid from the code previously shown converted to grayscale, together with its 3D graph.
Definitely, there’s something wrong here. The FT showed multiple dots, rather than two dots for a single sinusoid. Time for a little investigation! I’ll show to you the 3D plot of the grayscale image.
We can now see the culprit of our mystery case. The mat2gray() image converter used in Scilab only allows positive values of the sinusoid, unlike that of the explicit plot from the previous code. To remedy the situation, we can just add a constant bias (in this case, a value of 1 to include the negative values) and then get its FT. But wait, there’s more! The mat2gray() also tapers the values greater than 1 for decimal digits. The best remedy for this is to convert the values into unsigned integers using the uint8() function of Scilab. The values are then converted into grayscale values from 0 to 255. We can now proceed with the FT. Below are the results.
Now, there’s still quite wrong here. An additional center spot is observed. This center peak is mainly due to the bias added to the signal, which is equivalent to 1. One can also obtain the constant bias by averaging the values of the signal. Finally, we get the correct FT of this sinusoid, which is the same as in Fig. 6b.
Interferograms exhibit these kinds of sinusoid patterns. One can then recover the actual frequencies by doing the process shown. However, one must be cautious upon using the mat2gray() function of Scilab, since it has restrictions on negative values. Moreover, the constant bias added to the image would also propagate on the interferogram.
With that in mind, let’s now do something with our sinusoids. What happens when the spatial frequencies are increased? Well, let’s take a look at the figures below.
The first sinusoid in Fig. 12a represents a sinusoid with spatial frequency 1 Hz, which can be thought of as the fundamental frequency. The others are now then the higher harmonics on that fundamental, because they are integer multiples of the fundamental frequency (odd harmonics). As the spatial frequency increases, the separation of the dots increases, which indicates that the x-coordinates of the spatial frequency increased [2]. This is a supportive examination on the FT’s of sinusoids and dots, as shown in Fig. 5.
Now, what if the added bias is not constant? Let’s try to examine this by adding the harmonics in Fig. 12. Below are their images and FT’s. The image of the FT’s are kinda dim, so you can just click it and zoom.
The sinusoids here represent a resultant sinusoid when the signals with different frequencies where added together. The FT’s then look like they’re also added together, in which the multiple dots gives information about the spatial frequencies involved. Since these FT’s are images, one can’t just obtain the actual values of the spatial frequencies. One must then impose pixel-to-frequency relations to properly indicate the value of the spatial frequencies.
Let us now proceed with the section’s main goal, which is to demonstrate the rotation property of the FT. We do this by starting with the sinusoid from Fig. 10a, which has a spatial frequency of 4. We introduce the rotation matrix shown below.
The angle θ refers to the angle of rotation in the counter-clockwise direction. We rotate the said sinusoid with specific angles of rotation and observe their FT’s, as shown below.
As I have predicted, the dots also had their orientations rotated, which depends on the configuration of the sinusoid. Their separation is still constant, but the FT’s indicate the presence of the y-coordinate of the spatial frequency. Since the separation is constant, the distance of one dot from the center must then also be 4. For the configuration shown in Fig. 14d, the sinusoid is along the y-axis, which would make the FT associated consistent.
Now, let’s try combining 2D images of rotated sinusoids. First, let’s first observe what happens when we add them, mathematically. We are then combining sinusoids, which would then result to multiple dots as observed in Fig. 13. But what happens when the sinusoids are not oriented in the same direction? Let’s see the combinations of two sinusoids with spatial frequencies 4 and 6 rotated along different axes (both are sine functions).
The dots in the FT’s were dark and hard to decipher, so I increased their intensities without altering their positions. As predicted, their FT’s are just like added the individual component’s FT. The image in Fig. 15a has both vertical and horizontal sinusoid, so the combination has both horizontal and vertical pairs of dots. The separation of the dots for the vertical ones is longer than that of the horizontal ones, which is because the sinusoid that has the higher frequency (f = 6) is along the y-axis. In Fig. 15b, only the sinusoid with the higher frequency is rotated by 45 degrees counter-clockwise, and so the image of the FT shows the rotation of the pair of dots with longer separation, while the other pair lies in the x-axis. Finally, in Fig. 15c, both sinusoids were rotated, and so both pairs are rotated according to the orientation of the sinusoids. One can then predict the sinusoid constituents of an image by obtaining their FT’s.
We are not done yet in this section, though. We can also combine sinusoids by multiplying them on one another. Before we go on multiplying sinusoids, let me first construct an approach on how we can predict their FT’s given the factors. In trigonometry, one can use the product-to-sum identities of sine and cosine to predict the constituent sinusoids, whenever they are seen as sums of sinusoids. I present here the identities (thanks to SOS Math for the identities) used.
So whenever we multiply two sine functions, one can see at as the difference between the cosines of the sum of the difference and the sum of the angles. Let’s now try doing it with the constituent sinusoids from Fig. 15.
In Fig. 16, we multiplied two sine functions of spatial frequencies 4 and 6 with different orientations. In Fig. 16a, the sinusoid along the x-axis has spatial frequency 4 and 6 along the y-axis. From the identities shown earlier, the product of two sine functions are two cosine functions, in which the frequencies are the sum and difference of the two frequencies. This means that the resultant cosines have spatial frequencies along both the x and y axes. Thus, the white dots should be observed at the coordinates of the spatial frequencies, meaning the first pair is observed at (x,y) = (4,6) and (-4,-6), while the other pair is due to the difference, observed at (x,y) = (-4,6) and (4,-6). In Fig. 16b, the sinusoid that has a spatial frequency of 6 was tilted by 45 degrees, meaning, the sinusoid has constituents both along the x and y axes. The identity then utilizes both frequencies to obtain the two cosines. The same goes for Fig. 16c, where in this case, both sinusoids were tilted 45 degrees in the opposite direction. As observed, it looks like as if the FT of the sinusoid in Fig. 16a was tilted by 45 degrees also.
Before I end this part, let me just obtain the FT of a complex two-valued sinusoid function shown below.
The image of the sinusoid and its FT is then given by:
As can be deduced from the given function, there are four frequencies since each of the two sinusoids added can be transformed into again two sinsuoids with frequencies based on the identity provided earlier. As a result, the FT gives a pattern similar to that in Fig. 16a, in which the other pairs have higher coordinate values. Different patterns can then be produced from 2D sinusoids, in which FT can be of great help in determining the associated spatial frequencies. One can then obtain the equation of the sinusoidal image by doing FT.
Now, we move on to FT’s convolution property, and its application to image filtering.
III. Convolution Theorem Redux
Filtering in Fourier space can be achieved by exploiting FT’s convolution properties. We filter out unwanted patterns from images by producing filter masks to block the frequencies of the unwanted patterns. We do these by doing a convolution of the filter mask and the image in Fourier space. Moreover, convolution in FT has distinct properties [1]:
- The FT of a convolution of two functions in space is the product of the two functions’ FT , i.e.,
FT [ f ∗g ]=FG. - The convolution of a Dirac delta and a function f(t) results in a replication of f(t) in the location of the Dirac delta.
Let’s demonstrate first convolution properties of FT before we engage in filtering images. First, we again produce the FT of two dots separated symmetrically along the x-axis.
Again, we observe that the FT of two dots is a sinusoid, which is along the x-axis. Now, what happens when we replace the two dots with two circles with similar radii? Let’s see the figures below.
As you can see, the FT of the two circles is like an Airy pattern, in which a corrugated roof is placed under it. The image produced then like a multiplication of the FT of a circle with that of the FT of two dots separated along the x-axis. In the spirit of convolution, the image in Fig. 19a is the convolution of the two dots with that of a circle. The FT of the convolution is the product of their FT’s.
We can also vary the radius of the circle and observe the effect.
As the radius of the circles decreases, the observed Airy pattern then decreases in size. This then affects the convolution of the circle and the two dots. Remember a while ago when we saw a faint Airy pattern in the FT of two dots separated by a definite distance? Well, that faint Airy pattern could be attributed to convolution of a circle and two dots. The dots shown could have a finite radius, which became apparent in its FT.
What if we replace the dots with squares? Let’s see below.
Again, much like in Fig. 19, the FT of the two squares is just the product of the FT of a square and the FT of the two dots. And by varying their sizes, we observe the FT’s below.
The image is consistent with that of Fig. 20, in which the pattern decreases in size as the length of the square increases.
I also did the convolution for a Gaussian aperture, shown below.
The same mechanism is also observed, in which the FT of the Gaussian aperture is similar to that obtained in Activity #5. I changed the value of the standard deviation σ and obtained their FT’s, as shown below.
Again, the same principle as that with the circles of varying radii apply to Gaussian apertures, only that the Airy pattern is not visible anymore. This is the apparent property of the Gaussian aperture. Moreover, I have shown here that the FT of a Gaussian distribution is still a Gaussian distribution.
Let us now utilize the convolution property of FT for Dirac deltas. I have here a 200×200 image of 10 white dots located randomly along the black image, and associated with it is a “thunderbolt” figure.
As stated earlier, the convolution of two images is the product of their FT’s. Thus, by multiplying their FT’s and obtaining the product’s inverse FT, we get the following figure.
Tadaaa! The convolution of the two images from Fig. 25 is shown precisely. Mathematically speak, the integral of a Dirac delta at a certain value multiplied by a function is the function itself at that certain value. The convolution then replicates the “thunderbolt” figure at the location of the dots or Dirac deltas.
Finally, we move on the FT of repeated patterns. I have here a grid of points spaced equally, with its FT obtained.
We can think of the square grid as a set of two points symmetrically placed along the x and y axes. This means that the FT is a sum of a whole bunch of sinusoids. The sinusoids then add up into small dots. We can vary the spacing between the dots and observe their FT’s.
As the dot spacing increases, their FT’s dot spacing then decreases, and more dots will be observed. Again, as in part I, this is due to FT’s anamorphism. Moreover, this is an important fact when we venture into filtering in FT, since numerous patterns has specific dots in the FT space, and as the patterns become more prominent, their FT’s becoming less prominent, but with a higher intensity.
And with all the properties being explained thoroughly, let’s move on with the most vital application of FT: Enhancement of Images.
IV. Filtering in Fourier Space
A. Ridge Enhancement: Fingerprints
One of the feats of forensic science is being able to identify criminals by just obtaining their prints left in the crime scene, particularly, fingerprints. Although sometimes, fingerprints left in the crime scene could be riddled with blotches blocking the ridge patterns. Thus, it is necessary to filter out these blotches to identify the criminal.
To demonstrate this, let me show you a fingerprint of my own right thumb. Shown here are the original, grayscale and binary image.
As you can see, not only the blotches are present in my fingerprint, but also straight slash marks randomly placed in the fingerprint. I didn’t even know I had those, I might have been cut a million times in my right thumb. The binary image in Fig. 29c is just a black-and-white version of the grayscale image, which is used to emphasize the patterns of the fingerprint. To clean the fingerprint, let us apply our Fourier transform knowledge. Shown below is the code used to remove the blotches, given a filter mask.
Let me go over the code given. Our first job is to determine the fingerprint’s FT image. Then, one must identify the location of the ridge patterns, in which a mask must be created to highlight the ridge patterns. Shown below are the FT of the fingerprint and the used mask.
As you can observe, the FT of the ridge patterns are highlighted by the wavy, high intensity lines surrounding the center. One can also see lines connecting the FT of the ridge pattern to the center, which could be the FT of the slash marks in my thumb. Looking now at the filter, you can clearly see how unsophisticated I am in using MS Paint. Nevertheless, the main thing is, we want to filter out everything, except the FT of the ridge patterns. It is also necessary to give enough space for the component at the middle of the FT, which might drop the quality of the resulting image. With those images obtain, one can then proceed by multiplying the two images above to obtain their convolution. Then we can now obtain its inverse FT, which are shown below.
Talk about miracles, eh? As you can see, the ridge patterns are cleaned thoroughly, although some of the regions were a bit blurry. I can also say that the slash marks were also removed, and that’s one thing I didn’t expect. Before I move on, let me just show my initial reaction upon seeing this.
Time for me to do some explaining. This just proves that the slash marks’ FT where those lines connecting the ridge patterns and the center. Moreover, the grayscale image’s quality dropped a bit because of the filter used, in which a broad approximation for the filtering of the ridge pattern is involved. The center component of the FT might also have affected the quality, although I really liked the quality more since it highlighted the ridge patterns. The binary image is the final proof that those slash marks and blotches were lessened, and the necessary patterns behind it are improved.
Now, I’m gonna give a little information about fingerprint recognition. The automated method of verifying the human that has similar fingerprint requires only distinct patterns for it to obtain a match. According to Wikipedia, there are three basic patterns of fingerprint ridges. First is the arch, which enters from one side, passes through the center forming an arch, and then ends on the other side. The other is a loop, which enters the finger on one side, loops, then exits the same side. Finally is the whorl, which are the concentric curved patterns in the center of the finger. Moreover, there are also major minutiae that are essential in fingerprint verification such as ridge endings, bifurcations (splitting of ridges) and short ridges. With these patterns, the fingerprint matching machine can easily obtain a match even though the fingerprint is incomplete or in this case, filled with unnecessary marks and blotches. I thank my professor, Ma’am Jing for giving me this info.
B. Line Removal: Cleaning a Lunatic Photo
We are not done yet, bros! Let’s do some more cleaning, lunar style. Images from outer space are not exempted to imaging mishaps. I have here a composite image a surface on the moon obtained by the unmanned Lunar Orbiter V spacecraft in 1967 [1].
As you can see, the image is filled with vertical lines, much similar to that of when papers are folded. It really pains me to see photos treated as scientific feats dirtied by unnecessary marks. With that, it’s high time for some cleaning. Using the same code written above, the photo is cleared off with the necessary filter. Although this time, the log() of the FT values is needed to reduce the values to applicable magnitude. I first used the grayscaled red filter of the image to test the code.
Unlike that in the case of the fingerprint, we not concerned with the FT of the surface but with the FT of the vertical lines. By anamorphism, the vertical lines’ FT image is then mapped horizontally, which signifies that the horizontal lines at the center of the FT are the FT of those lines. The vertical lines in the FT could have been due to the horizontal lines that can clearly be seen in the original photo. To filter them out then, the filter found in Fig. 33b was used. And here’s the result.
Obviously, the vertical lines in the original photo were filtered out, although there were a bit left in the last picture. The quality of the shadows in the craters were also dropped, which could have been due to the filtering of some other intensities. What’s important here is that the vertical lines were filtered out, and a work of art is saved.
But wait, there’s more. I’ve only shown here the filtered image of the red gray map of the image. That means, with the proper algorithm, I can restore the color from the original image. This is done by doing the FT on all the color components: Red, Green and Blue dimensions. By doing so, the restoration is shown below.
With such beauty, one can only imagine the wonders of digital imaging.
C. Canvas Weave Modelling and Removal
Hohoho! You think we’re done with that? It’s high time for another cleaning, art style! Digital images of famous art are always hindered by the kind of materials used in making the art. An example is the patterns observed from a canvas fabric, which is prominent in most paintings. I have here an image of an oil painting from the UP Vargas Museum Collection [1].
The beauty of the art work is botched by the apparent weave patterns. Well, it’s Fourier Transform to the rescue. Using the same code as before, the FT and the appropriate filter were generated, as shown below.
Using the image of the FT of the painting, I predicted where the FT’s of the patterns were placed. Since the pattern is repetitive and numerous in the painting, their FT’s could be the white twinkling stars around the center. To block off their intensities, the filter in Fig. 37b is used. The final image is shown below.
Again, the numerous canvas weave patterns were filtered off, and the image is clearer. Similar to that in the lunar photo, one can also restore its color using the RGB color spaces. The colored image is shown below.
Comparing this with the original painting, we observe that the color were different. Could it be that colors were also filtered in Fourier space? To show that this could be the case, I used the inverted filter below to check out the filtered patterns.
I used this to obtain the image of the filtered patterns, and show below is the colored image of the filtered out pattern.
And yes, some of the colors were filtered. The pattern of the canvas is also seen here. I still don’t have the solution for the color restoration in Scilab, so maybe we can use another useful program. To remedy this, I opened the image in Adobe Photoshop CS6 and manipulated its color levels, saturation, exposure and contrast to finally achieve the original colors. Here’s what I’ve got.
What can I say? Scilab cleaning worked wonderfully!
Another day, another long post. This for me is officially the most tiring activity. It’s not how hard the code was done, it’s the “cleaning” of the code. Every code that I have typed is well riddled with errors, most of it due to wrong variables, wrong image call, and most of all, wrong output. Yet again, those are nothing compared to my results. The mere fact that we can process images just by using Fast Fourier Transform for me is a wonder. Photoshop, GIMP, and other image processing softwares are there, but it’s more challenging when you’re doing the same thing not by manipulating the image visually, but by using scripts and codes. And we’re not just manipulating any old images out there, but we’re actually improving the quality of some of the most important images in history. Fingerprints to identify criminals, moon surface pictures to understand the geology of our own moon, and cleaning the best paintings from the best artists, all these improving our quality of living and our way of viewing life. I am hoping to learn more from image processing, and how I can enhance images more. With that, I am giving myself a 12/10 venturing the wonders of FT. Time to party people!
Acknowledgements: I would like to thank Ma’am Jing for giving me the utmost help for improving my results, particularly for the sinusoids and the cleaned images.
References:
[1] Soriano, M., “Properties and Applications of the 2D Fourier Transform,” 2014.
[2] Lehar, S., “An Intuitive Explanation of Fourier Theory.” Retrieved from: <http://cns-alumni.bu.edu/~slehar/fourier/fourier.html>
Barteezy's Applied Physics 186 Experience 
2 thoughts on “Activity #6 – Properties and Applications of the 2D Fourier Transform”