How the 2D FFT works

Mike X Cohen
A free video tutorial from Mike X Cohen
Neuroscientist, writer, professor
4.6 instructor rating • 20 courses • 110,868 students

Lecture description

Explanation of the 2D FFT used for image processing.

Learn more from the full course

Master the Fourier transform and its applications

Learn the Fourier transform in MATLAB and Python, and its applications in digital signal processing and image processing

06:41:42 of on-demand video • Updated April 2021

  • Learn about one of the single most important equations in all of modern technology and therefore human civilization.
  • The fundamental concepts underlying the Fourier transform
  • Sine waves, complex numbers, dot products, sampling theorem, aliasing, and more!
  • Interpret the results of the Fourier transform
  • Apply the Fourier transform in MATLAB and Python!
  • Use the fast Fourier transform in signal processing applications
  • Improve your MATLAB and/or Python programming skills
  • Know the limitations of interpreting the Fourier transform.
English [Auto] In this video, I'm going to explain the two dimensional Fourier transform, that's the 48 transform as it applies to images, which, of course are 2D. In some sense, the two defoliate transform is really just a simple, straightforward extension of the one dimensional Fourier transform that you've been learning about so far. However, it's not quite that simple. Well, I should say implementing the the is really simple. The difficulty is interpreting the results of the two DFT. And even more complicated is trying to predict what an image might look like based on its tudy for a power spectrum. First, let me explain how pictures are represented on computers when you have a picture like this, your computer represents this as a matrix and the color in each element of this matrix corresponds to a number. So, in fact, the matrix looks like this. You can see that larger numbers correspond to darker colors. Now I'll explain how to implement a 2D 50. When the data are in a two dimensional matrix, you can take the one DFT along the columns of the Matrix that will produce a matrix of one dimensional footy's and that you can see in this image here. So now frequency is on the Y axis. This top row here corresponds to the DC offset and all the values, the values in each element of this matrix are the Fourier coefficients for each column of this matrix. Then the next step is to perform a one day effort on the roads of this matrix. Now, the result of this step will be a two dimensional matrix of Fourier coefficients, the low frequency coefficients are in the corners and the Nyquist frequency is in the middle. In a previous video, I showed that in some disciplines people will show the one dimensional power spectrum with DC in the middle. Negative frequencies on the left and positive frequencies on the right. For images shifting the coefficients around so that Nykvist is at the edges and the low frequencies are at the center of the Matrix is commonly done. So typically people would rearrange this power spectrum or this Fourier spectrum to show low frequencies in the center going up to higher frequencies and then the nyqvist frequency at the corners. Computationally, that's really all there is to the study effort. What's really tricky is figuring out how to map the features of an image onto locations in the tudy for a plain. Now, oftentimes when people teach about the two dimensional Fourier transform, they will immediately jump into showing power spectra of natural images. But I think that makes things really complicated. I think it's better to start with really simple images and first try to build a bit of intuition about how to interpret this two-dimensional for a plane. Therefore, what I'm going to do in the rest of this video is show you examples of how spatial frequency phase and location affect the results of the 2D 48 transform. And I'm going to show you this through a series of movies, so first is a movie that will illustrate the different spatial frequencies of an image and how those affect the resulting Fourier transform. So actually, I'll just start by running this whole cell. So what you see here is a sign gradient. So it's a two dimensional sine wave and the spatial frequency is increasing over time. Here are the two images resulting from the 2D 48 transform. We have the amplitude spectrum and the phase spectrum. So you'll notice that what I've done here is to change the sine wave frequency over time, but holds all the other variables constant. For example, the phase, the orientation. This is just like a real scientific experiment where you hold as many variables constant as possible and you change only one variable at a time in order to understand the effects of that variable independent of all the other variables. Anyway, the important point of this video is to see that as the sine wave frequency increases this the center location of this is moving further and further away from the origin. And that's because the center of this block corresponds to lower frequencies and the frequencies get higher as we move further away from the center. Now it look like this thing was getting wider and narrower, so the width of the peak was changing, but that's actually not a really interesting feature. It's actually just due to the non stationary these related to the spatial frequency relative to the size of this image. You would see the same thing in the time domain, in the amplitude spectrum of a sine wave that has non integer number of cycles in the time window that you compute the 48 transform of. Now, the phase spectrum, let me run this again, the phase spectrum initially looks like it's changing a lot, but actually these are mostly rounding errors and you shouldn't pay too much attention to them. To understand why, you can refer back to the video about interpreting phase values and the effects of uncertainty and noise when the amplitude is close to zero. And in this case, the amplitude of all of these sine waves is basically zero, plus some computer rounding error for pretty much everywhere in this for a plane except for this line here. Now, one thing I'd like to mention about this line here of sine wave frequencies, spatial frequencies, these are arbitrary numbers that I picked because they looked good on my computer screen. Depending on your screen resolution, these values may or may not look really good. So I encourage you to play around with these numbers and find a range that looks reasonable for you. OK, so this was all for two days sideways with one specific phase, so one specific orientation of this gradient, it's interesting to watch what happens when we change the phase of this to design patch. So now I'm going to change this to be pay over for instead of pay over to run this cell again, and now you see that the gradient is oriented this way and you can see the same phenomenon. So this little splotch of amplitude is getting further and further away from the origin as the sine wave frequencies increase. However, now they're going up and down the diagonal here instead of on the horizontal line here. Again, this kind of pulsating of size that it sometimes gets larger and sometimes gets smaller. That's not a terribly interesting feature that's really just related to non-state personalities introduced by clipping at the boundaries of this image. OK, now for the next experiment. Here, I'm going to change the face of the sign, so here I change the face once it was fixed at PI over two and then I fixed it to PI over four. Now, what I'm going to do is fix the sine wave frequency. So we just leave the sine wave frequency constant and the sine phase is going to vary over time between zero and PI. So let's run this video and see what the effects are on the tutty power spectrum. So you can see this is rotating around. And here you see that. These amplitudes, these little buttons are moving around the frequency plane like this, so let's run this again. So the sign patch is rotating around, this is like the face of a clock, you know, this would make a really cool clockface. And now notice what's happening in the amplitude spectrum, the distance away from the origin is constant. So these things are always the same distance away from the origin of this amplitude spectrum plane. And instead, they are rotating around the origin as the gradient, the phase of this sine wave is rotating. Again, I encourage you to pause the video and change these parameters and keep exploring this code. Now for the third experiment, the third experiment is going to be all about the physical location, the spatial location of the image. So in this case, I'm using a threshold, a 2D Gaussian, and that's going to create a ball that will move around on this plane. So let me first run the video and then I'll walk you through a little bit of the code. So here's this ball that's moving around. In this case, it's just going up and down. Now, what's interesting is that the amplitude spectrum is basically unchanged. Again, you see there's some, you know, rounding error, some really tiny changes out here, but those you can basically just ignore. The important point is that as this ball moves around in space, the features of the ball, the spectral features of the ball are not changing. It's the same ball everywhere it goes. However, it's moving in location and that is represented in the face. So you can see that those. The phase dynamics are changing, their looks like they're rotating around and the amplitude is remaining constant, so you can change the width of the Gaussian with this parameter here with so we can try changing this to 50. And when I run this again, watch what happens to the size of this ball and the size of this ball in the amplitude spectrum. So you see this one got bigger and this one also got a bit bigger. And again, there's some, you know, weird stuff happening here, but that's mostly just due to non stationary, those resulting from the edges of this image and the finite size of this plane. So in this video, I introduced you to the two dimensional Fourier transform, I explained mechanistically how it works by applying the one dimensional Fourier transform to the columns and then a one defoliate transform to the rose of that resulting Fourier coefficients. Matrix I showed several movies in Matlab that I hope will help you build some intuition about the relationship between spatial frequency, fais spatial location and the two key result from the two dimensional you transform, which are the amplitude spectrum and the phase spectrum.