(20 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 +
[[Category:2D rect]]
 +
[[Category:continuous-space Fourier transform]]
 +
[[Category:ECE438]]
 +
[[Category:tutorial]]
 +
 
== Spectral Analysis of 2D Signals (December 1, 2009) ==
 
== Spectral Analysis of 2D Signals (December 1, 2009) ==
 
----
 
----
  
<blockquote>'''Here, I will describe and explain the basics behind analyzing the spectrum of ''2-D signals'' - principally <big><u>''images''!</u></big>'''
+
<big><blockquote>'''Here, I will describe and explain the basics behind analyzing the <u>spectrum of ''2-D signals''</u> (including ''images''''').
- Ryan Scheidt</blockquote>
+
- [[User:Rscheidt|Ryan Scheidt]]</blockquote></big>
 
+
----
 +
<br><br>
 
----
 
----
Spectral analysis of two-dimensional (2D) signals is not much different from the one-dimensional (1D) FFT <small>[Fast Fourier Transform - see [http://en.wikipedia.org/wiki/Fast_Fourier_transform]]</small> that we are (more) accustomed to. The only difference is that our signals are now represented in one more plane. We can think of this difference (1D vs. 2D) as the difference between, say, a ''one-dimensional'' longitudinal wave in a slinky (like this: [http://www.youtube.com/watch?v=upcTmdqrEeo]), versus a ''two-dimensional'' wave from a trampoline (e.g. drop a baseball in the center (or given any other excitation), and the wave will propagate in both x and y-directions ([http://www.youtube.com/watch?v=QdkMmvFE6MA]).
+
Spectral analysis of two-dimensional (2D) signals is not much different from the one-dimensional (1D) FFT <small>(Fast Fourier Transform - see [http://en.wikipedia.org/wiki/Fast_Fourier_transform])</small> that we are (more) accustomed to. <br><br>The only difference is that our signals are now represented in one more plane. We can think of this difference (1D vs. 2D) as the difference between, say, a ''one-dimensional'' longitudinal wave in a slinky (like this: [http://www.youtube.com/watch?v=upcTmdqrEeo]), versus a ''two-dimensional'' wave from a trampoline (e.g. drop a baseball in the center (or given any other excitation), and the wave will propagate in both x and y-directions ([http://www.youtube.com/watch?v=QdkMmvFE6MA])).
  
For those familiar with the properties of the 1D Fourier Transform (FT), the 2-D Continuous-Space Fourier Transform (CSFT) [see [https://engineering.purdue.edu/~bouman/ece637/notes/pdf/CSFT.pdf] for a reference] is an intuitive extension of the 1D properties. The following Rhea link shows some of these properties: [https://kiwi.ecn.purdue.edu/rhea/index.php/Student_summary_spectral_analysis_2D_signals].
+
For those familiar with the properties of the 1D Fourier Transform (FT), the 2-D Continuous-Space Fourier Transform (CSFT) (see [https://engineering.purdue.edu/~bouman/ece637/notes/pdf/CSFT.pdf] for a reference) is an intuitive extension of the 1D properties. The following Rhea link shows some of these properties: [https://kiwi.ecn.purdue.edu/rhea/index.php/Student_summary_spectral_analysis_2D_signals].
 
----
 
----
 
<br><br>
 
<br><br>
Line 19: Line 25:
 
[[Image:Rect16.png|left|800px]]
 
[[Image:Rect16.png|left|800px]]
 
This is exactly what was expected. Remember, that when we double the width of a 1D rect(x) function, the corresponding sinc(f) has twice the height and twice the frequency. In two dimensions, the corresponding will thus be quadrupled in height (multiplied by two ''twice''), with twice the frequency.
 
This is exactly what was expected. Remember, that when we double the width of a 1D rect(x) function, the corresponding sinc(f) has twice the height and twice the frequency. In two dimensions, the corresponding will thus be quadrupled in height (multiplied by two ''twice''), with twice the frequency.
 +
 +
Here's what the two CSFT's look like projected as a one-dimensional image:
 +
[[Image:Rect8and16.png|left|800px]]
 
----
 
----
 
<br><br>
 
<br><br>
Line 24: Line 33:
 
Now let's look at the 2D circ(*) function. Here's the 2-dimensional circ(x,y) function and its CSFT:<br><br>
 
Now let's look at the 2D circ(*) function. Here's the 2-dimensional circ(x,y) function and its CSFT:<br><br>
 
[[Image:Circ4.png|left|800px]]
 
[[Image:Circ4.png|left|800px]]
The name of this CSFT is Jinc(u,v) - [see http://mathworld.wolfram.com/JincFunction.html] Let's try making the "circle" a little bit larger with a radius of 8. We'll watch what happens to the frequency of the 2-dimensional jinc(u,v) function:
+
The name of this CSFT is Jinc(u,v) - (see [http://mathworld.wolfram.com/JincFunction.html]) Let's try making the "circle" a little bit larger with a radius of 8. We'll watch what happens to the frequency of the 2-dimensional jinc(u,v) function:
 
[[Image:Circ8.png|left|800px]]
 
[[Image:Circ8.png|left|800px]]
 
Note that both the frequency and magnitude of the jinc(u,v) also went up (more precisely: magnitude ''quadrupled'' and frequency ''doubled'', just like the sinc(u,v) as done previously).
 
Note that both the frequency and magnitude of the jinc(u,v) also went up (more precisely: magnitude ''quadrupled'' and frequency ''doubled'', just like the sinc(u,v) as done previously).
 +
 +
Here's what the two CSFT's look like projected as a one-dimensional image:
 +
[[Image:Circ4and8.png|left|800px]]
 
----
 
----
 
<br><br>
 
<br><br>
Line 35: Line 47:
 
[[Image:Cos2D_withDC.png|left|800px]]
 
[[Image:Cos2D_withDC.png|left|800px]]
 
Note that the added DC term of 1 shows up in the CSFT as an impulse at the origin (u=0, v=0).<br><br>
 
Note that the added DC term of 1 shows up in the CSFT as an impulse at the origin (u=0, v=0).<br><br>
'''Now let's combine two 2D cosine waves:'''
+
<u>'''Now let's combine two 2D cosine waves:'''</u>
 
[[Image:CosTwice.png|left|800px]]
 
[[Image:CosTwice.png|left|800px]]
 
Can you see all five components? There is a small component at the origin (due to the 0.2 DC term)!
 
Can you see all five components? There is a small component at the origin (due to the 0.2 DC term)!
Line 46: Line 58:
 
[[Image:Lena.gif|left|256px]]
 
[[Image:Lena.gif|left|256px]]
 
----
 
----
<br>
+
<br><br>
 
+
----
Let's look at what the 2D FFT of Lena looks like. We will look at some simple 3X3 filters that are then convolved with the original image to create a filtered image. ''[Here is an excellent webpage showing how 2D convolution works: [http://www.songho.ca/dsp/convolution/convolution2d_example.html]]''<br><br>
+
<big><u>Let's look at what the 2D FFT of Lena looks like.</u></big><br><br> We will look at some simple 3X3 filters that are then convolved with the original image to create a filtered image. ''(For those who have forgotten or need a refresher, here is an excellent webpage showing how 2D convolution is done: [http://www.songho.ca/dsp/convolution/convolution2d_example.html])''<br><br>
The following pictures show the original image (Lena), the image of the filter, and the filtered image (done with conv2). MATLAB m-files available upon request.  
+
The following pictures show the original image (Lena), the image of the filter, and the filtered image (done with conv2). Note that the FFT2 are plotted as log values, in order to enhance the "contrast" between values.
  
 
The colormaps to the right of each image show the corresponding values for each shade of gray (i.e. continuum from white to black). Each image is "normalized to 256 values" so that for each pixel, the lowest values (even if negative) are mapped to 0 (black) and the highest values are mapped to 255 (white).
 
The colormaps to the right of each image show the corresponding values for each shade of gray (i.e. continuum from white to black). Each image is "normalized to 256 values" so that for each pixel, the lowest values (even if negative) are mapped to 0 (black) and the highest values are mapped to 255 (white).
 
+
<br><br>
Let's start with the filter = 1/16*[1 2 1; 2 4 2; 1 2 1], commonly referred to as an "average filter":
+
<u>'''Let's start with the filter = 1/16*[1 2 1; 2 4 2; 1 2 1], commonly referred to as an "average filter":'''</u>
 
[[Image:Filter1_image.png|left|800px]]
 
[[Image:Filter1_image.png|left|800px]]
 
Can you tell that the filtered image is "smoothed"? Let's look at the images as 3-dimensional projections for easier visualization (via MATLAB's mesh command). First the original image:
 
Can you tell that the filtered image is "smoothed"? Let's look at the images as 3-dimensional projections for easier visualization (via MATLAB's mesh command). First the original image:
Line 63: Line 75:
 
<br><br>
 
<br><br>
 
----
 
----
Let's look at a few other filters briefly:
+
<big><u>Let's look at a few other filters briefly:</u></big>
[[Image:Filter2_image.png|left|800px]]
+
<br><br>
[[Image:Filter3_image.png|left|800px]]
+
'''Here's the filter = 1/9*[-1 -1 -1;-1 8 -1;-1 -1 -1], referred to as an "edge detector":'''
[[Image:Filter4_image.png|left|800px]]
+
[[Image:Filter5.png|left|800px]]
[[Image:Filter5_image.png|left|800px]]
+
Here's what individual rows of the image and filtered image look like:
 +
[[Image:Filter5Rows.png|left|400px]]
 +
Notice that the filter only responds to sharp discontinuities (i.e. rapid changes) in the original image. Since 0 is mapped to gray, the filtered image is mostly gray, with the outlines visible.
 +
----
 +
<br><br>
 +
----
 +
<u>'''Here is the filter = [-1 -1 -1; 2 2 2; -1 -1 -1], used as an "''horizontal'' edge detector":'''</u>
 +
[[Image:Filter7.png|left|800px]]
 +
Again, here's what individual rows of the image and filtered image look like:
 +
[[Image:Filter7Rows.png|left|400px]]
 +
----
 +
<br><br>
 +
----
 +
<u>'''Here is the filter = [-1 2 -1; -1 2 -1; -1 2 -1], used as an "''vertical'' edge detector":'''</u>
 +
[[Image:Filter8.png|left|800px]]
 +
Again, here's what individual rows of the image and filtered image look like:
 +
[[Image:Filter8Rows.png|left|400px]]
 +
Can you see the difference in the filtered image here versus the "horizontally filtered" image as before? View the images at full resolution and note which details are emphasized/de-emphasized in each case.
 +
----
 +
<br><br>
 +
----
 +
<big>'''Lastly, let's look at what happens to the FFT2 of Lena as we add noise to the image (using MATLAB's randn).'''</big><br><br> Here's the original image and corresponding CSFT:
 +
[[Image:Lena.png|left|800px]]
 +
Now let's add a little bit of noise (100*randn(512,512)):
 +
[[Image:Lena100.png|left|800px]]
 +
With ten times more noise:
 +
[[Image:Lena1000.png|left|800px]]
 +
And ten times more noise again!:
 +
[[Image:Lena10000.png|left|800px]]
 +
<big>'''We see that the noisy image approaches an impulse at the origin (with "white noise" elsewhere), indicating that the image's periodic nature is degraded and soon approaches simply a DC image (represented by an impulse at the origin).
 +
'''</big>
 +
----
 +
Wow! What a page! I think you should consider including it in your e-portfolio when you apply for jobs/graduate school. --[[User:Mboutin|Mboutin]] 12:29, 27 November 2009 (UTC)
 +
 
 +
Any chance you could present on Monday instead of Tuesday? --[[User:weim|weim]]
 +
 
 +
Sorry, I cannot make Mondays due to a meeting at that time. -- [[User:rscheidt|rscheidt]]
 +
----
 +
[[ECE438|Back to ECE438]]

Latest revision as of 11:23, 18 March 2013


Spectral Analysis of 2D Signals (December 1, 2009)


Here, I will describe and explain the basics behind analyzing the spectrum of 2-D signals (including images). - Ryan Scheidt




Spectral analysis of two-dimensional (2D) signals is not much different from the one-dimensional (1D) FFT (Fast Fourier Transform - see [1]) that we are (more) accustomed to.

The only difference is that our signals are now represented in one more plane. We can think of this difference (1D vs. 2D) as the difference between, say, a one-dimensional longitudinal wave in a slinky (like this: [2]), versus a two-dimensional wave from a trampoline (e.g. drop a baseball in the center (or given any other excitation), and the wave will propagate in both x and y-directions ([3])).

For those familiar with the properties of the 1D Fourier Transform (FT), the 2-D Continuous-Space Fourier Transform (CSFT) (see [4] for a reference) is an intuitive extension of the 1D properties. The following Rhea link shows some of these properties: [5].





Now let's look at the spectral analysis of some elementary 2D signals.

We'll start with the 2-dimensional rect(*) signal. Here's the 2-dimensional rect(x,y) function and its CSFT:

(Note: click on any of the following images and then click on the "Full resolution" hyperlink to see the full image.)

Rect8.png

Now let's make the "rectangle" a little bit bigger: 16X16. We'll watch what happens to the frequency of the 2-dimensional sinc function:

Rect16.png

This is exactly what was expected. Remember, that when we double the width of a 1D rect(x) function, the corresponding sinc(f) has twice the height and twice the frequency. In two dimensions, the corresponding will thus be quadrupled in height (multiplied by two twice), with twice the frequency.

Here's what the two CSFT's look like projected as a one-dimensional image:

Rect8and16.png




Now let's look at the 2D circ(*) function. Here's the 2-dimensional circ(x,y) function and its CSFT:

Circ4.png

The name of this CSFT is Jinc(u,v) - (see [6]) Let's try making the "circle" a little bit larger with a radius of 8. We'll watch what happens to the frequency of the 2-dimensional jinc(u,v) function:

Circ8.png

Note that both the frequency and magnitude of the jinc(u,v) also went up (more precisely: magnitude quadrupled and frequency doubled, just like the sinc(u,v) as done previously).

Here's what the two CSFT's look like projected as a one-dimensional image:

Circ4and8.png




Now let's look at the 2D cos(*) function. Here's a 2-dimensional cos(x,y) function and its CSFT:

Cos2D.png

Now let's add a DC component and watch what happens to the CSFT components:

Cos2D withDC.png

Note that the added DC term of 1 shows up in the CSFT as an impulse at the origin (u=0, v=0).

Now let's combine two 2D cosine waves:

CosTwice.png

Can you see all five components? There is a small component at the origin (due to the 0.2 DC term)!





Now let's look at images briefly.

The following image, commonly referred to as "Lena" (sometimes also "Lenna"), is a famous image utilized in standard image processing algorithms and testing. The background behind this image is quite interesting. Here are some links for the interested reader: [7], [8]

Lena.gif




Let's look at what the 2D FFT of Lena looks like.

We will look at some simple 3X3 filters that are then convolved with the original image to create a filtered image. (For those who have forgotten or need a refresher, here is an excellent webpage showing how 2D convolution is done: [9])

The following pictures show the original image (Lena), the image of the filter, and the filtered image (done with conv2). Note that the FFT2 are plotted as log values, in order to enhance the "contrast" between values.

The colormaps to the right of each image show the corresponding values for each shade of gray (i.e. continuum from white to black). Each image is "normalized to 256 values" so that for each pixel, the lowest values (even if negative) are mapped to 0 (black) and the highest values are mapped to 255 (white).

Let's start with the filter = 1/16*[1 2 1; 2 4 2; 1 2 1], commonly referred to as an "average filter":

Filter1 image.png

Can you tell that the filtered image is "smoothed"? Let's look at the images as 3-dimensional projections for easier visualization (via MATLAB's mesh command). First the original image:

MeshOriginal.png
Notice that the following filtered image has much more gradual color gradations (e.g. the red "lingers around longer" and there is less blue; this is because this filter acts as a low pass filter, removing high frequency components!):
MeshFiltered.png

Here's what the image and filtered image look like in two specific rows of the image:

Row128 256.png

Can you see how the filter removed the high frequency "noise"?





Let's look at a few other filters briefly:

Here's the filter = 1/9*[-1 -1 -1;-1 8 -1;-1 -1 -1], referred to as an "edge detector":

Filter5.png

Here's what individual rows of the image and filtered image look like:

Filter5Rows.png

Notice that the filter only responds to sharp discontinuities (i.e. rapid changes) in the original image. Since 0 is mapped to gray, the filtered image is mostly gray, with the outlines visible.





Here is the filter = [-1 -1 -1; 2 2 2; -1 -1 -1], used as an "horizontal edge detector":

Filter7.png

Again, here's what individual rows of the image and filtered image look like:

Filter7Rows.png




Here is the filter = [-1 2 -1; -1 2 -1; -1 2 -1], used as an "vertical edge detector":

Filter8.png

Again, here's what individual rows of the image and filtered image look like:

Filter8Rows.png

Can you see the difference in the filtered image here versus the "horizontally filtered" image as before? View the images at full resolution and note which details are emphasized/de-emphasized in each case.





Lastly, let's look at what happens to the FFT2 of Lena as we add noise to the image (using MATLAB's randn).

Here's the original image and corresponding CSFT:

Lena.png

Now let's add a little bit of noise (100*randn(512,512)):

Lena100.png

With ten times more noise:

Lena1000.png

And ten times more noise again!:

Lena10000.png

We see that the noisy image approaches an impulse at the origin (with "white noise" elsewhere), indicating that the image's periodic nature is degraded and soon approaches simply a DC image (represented by an impulse at the origin).


Wow! What a page! I think you should consider including it in your e-portfolio when you apply for jobs/graduate school. --Mboutin 12:29, 27 November 2009 (UTC)

Any chance you could present on Monday instead of Tuesday? --weim

Sorry, I cannot make Mondays due to a meeting at that time. -- rscheidt


Back to ECE438

Alumni Liaison

has a message for current ECE438 students.

Sean Hu, ECE PhD 2009