2-D Discrete Fourier Transform

The Podcast. Play it whilst you read the blogpost!

IN: 01

Subject: 2-Dimensional Fourier Transform

Written by Chubak Bidpaa

The source for this episode is Gonzalez and Woods’ Chapter 04 Page 240 onward. We’ll also use a few other sources, which will be highlighted in the blog post.

Have you watched the movie Tron? Some of you may, some of you may have not. Well, let’s not fret over it. The sujet of this movie is that a ragtag group of individuals transform themselves into a video game world, to fight a battle. Keyword here, at least for us, is transform. A Fourier transform is something akin to this: Signals are transformed from their cozy spatial domain into a cryptic frequency domain. By the way of this transformation, we can apply operations that are impossible to think of in the spatial domain.

 

Fun Fact: Tron was the first movie to use computer-generated imagery.

But pray tell, what is this Fourier transform you speak of? Well, it basically a complex function, don’t forget, complex, in which we use Euler’s Formula to generate a sinusoidal periodic value for our analogue function. But that’s just it – Analgoue. Analogue signals are continuous, meaning they are infinite, however, the digital signals we deal with in computers everyday are discrete. So how to compensate for this difference?

It all boils down to the difference between integration, and summation. Integrals are basically the area under the curve of a function, so they are infinite, and continuous, however, summations are finite, and discrete. So by replacing the integral symbol with sigma symbol, we can have ourselves a nice and dandy equation for calculating discrete Fourier transform in 2-D. Refer to the blog post to see this equation, equation 1-1.

Equation 1-1:

F(u, v) = \sum_{x=0}^{M=1} \sum_{y=0}^{N-1} f(x, y)e^{-j2\pi(ux/M+uy/n)}

To revert this transformation back into the spatial domain, we’ll use Inverse Discrete Fourier Transform. Refer to equation 1-2 to get a grasp of what IDFT holds in the sack. As you may notice, the inverse DFT is the average of the opposite of the Euler’s Formula.

Equation 1-2:

f(x, y) = \frac{1}{MN} \sum_{x=0}^{M=1} \sum_{y=0}^{N-1} f(x, y)e^{j2\pi(ux/M+uy/n)}

But what is this Euler’s Formula you speak of? Well, refer to equation 1-3 to see the complex interpretation of Euler’s Formula. We talk about complex numbers as if knowing about them is rite of passage. No. it would, however, be my privilege to talk about complex numbers, for those who are otherwise unaware!

Equation 1-3:

e^{j\theta} = \cos{\theta} + j\sin{\theta}

Well, let me start off by saying that there are basically two sorts of numbers. Real, and Complex. Complex numbers have two sections, a real section, and an imaginary section. Refer to equation 1-5 (1-4) to find out what an “imaginary” number is.

Equation 1-5 (1-4):

a (\text{real part}) + bi (\text{imaginary part})

i = \sqrt(-1)

Let’s ask ourselves this question: We have a frequency interval, and then we have an spatial interval. How are these two related? Well, easy! You can see their relation in formula 1-5 and 1-6, in which we have captured the separation between samples, in the divisor or the quotient, and delta u and v being the separation between the frequencies.

Equations 1-5 and 1-6:

\Delta u = \frac{M}{\Delta T}

\Delta v = \frac{N}{\Delta Z}

Another property of DFT is the fact that you can rotate and translate the domain easily as one, two three. Another property of it is its periodicity. Meaning that both DFT and IDFT are infinitely periodic in both u and v directions, as you can see in figure 1-1 in the blog post.

 

 

Figure 1-1

In equations 1-7 through 1-8, you can see the definition of phase spectrum. This is what we in the signal processing simply call Fourier spectrum. What’s the use? Visualization, my fam! And if you remember Winamp, an audio player from the early Aughts in which we used to play music files we downloaded off Limewire, you’d remember power spectrum. Power Spectrum is Fourier Spectrum squared. But what is it, really? Let’s not fret, it’s basically the Fourier transform in polar coordinates. In equation 1-9 you see equation for phase angle. And in figure 1-2 you can see it in action.

Equations 1-7, 1-8, and 1-9:

F(u, v) = R(u, v) + jI(u, v) = |F(u, v)|e^{j\phi (uv)}

F(u, v) = [R^2(u, v) + I^2(u, v)] ^ {1/2}

\phi(u, v) = arctan\left[\frac{I(u, v)}{R(u, v)}\right]

 

 

Figure 1-2-1
Figure 1-2-2

Let’s talk about convolution. We have two very different sorts of convolutions in signal processing, one is convolution in the spatial domain, one is convolution in the frequency domain. We’re not concerned with the spatial domain right now, so let’s talk about the frequency domain. In frequency domain, the convolution is just the result of multiplying two Fourier functions together. Referring to equation 1-10, we’ll realize that convolution in the frequency domain equates the circular convolution in the spatial domain. But whilst you’re there, take a look at equation 1-11. Looks familiar? Yes, the multiplication of two signals in the spatial domain equals something close to IDFT of a circular convolution. But what is this circular convolution? Refer to equation 1-12.

Equation 1-10, 1-11, and 1-12:

(f \star h) (x, y) = \sum_{m=0}^{M - 1} \sum_{n=0}{N-1} f(m, n)h(x - m, y - n)

(f \star h) (x, y) \Leftrightarrow (F \bullet H) (u, v)

(f \bullet h) (x, y) \Leftrightarrow \frac{1}{MN}(F \star H)(u, v)

Correlation is another one of DFT properties. We denote correlation with a hallow star. Correlation is similar to convolution, except correlation is used to compare the two signals.

What’s important about DFT is that it’s separable. Pray tell mister man, what does it mean? It simply means that you can do certain operations on the rows, and certain operations on the columns ,and then mix and match them together.

But how do you apply DFT? The formula shows that it sums up a complex operation on all rows, and on all columns. So how does it get to be so fast, insomuch as it has been in practice for ages, and I can apply a DFT on a large image, or an audio file? The answer lies in Fast Fourier Transform, or FFT. We’ll discuss FFT soon.

I hope you’ve enjoyed the first episode of my podcast plus blog post. I’ve spent a lot of time on it, and remember that I make these podcasts episodes plus blog posts to learn, more than to teach. So if there are inaccuracies, please forgive me. If you have any corrections to this podcast episode or blog post, just tell me, and I’ll add it to the addendum.

Let’s hope Partly Shaderly podcast slash blog takes off!

 

 

Print Friendly, PDF & Email

Leave a Reply

Your email address will not be published. Required fields are marked *