# Image processing and the Fourier Transform

I am trying to understand how and why the fourier transform is used in image processing / computer vision. Below is what I have gathered so far. Would my understanding of it be correct? If not, could somebody explain it to me in simple, plain english? Or, does anybody have anything to add to it? Last but not least, could somebody explain the "discrete fourier transform"?

The fourier transform decomposes an image into its sine and cosine components. Put simply, sine and cosine are waves starting at a minimum and maximum respectively. In the real world, we can't tell whether a wave that we observe started at a maximum or minimum point, and therefore we can't really distinguish between the two. Therefore, sine and cosine are simply referred to as sinusoids.

When applying the FT to an image, we transform it from its spatial domain into a "frequency domain", which in essence is the image represented in terms of its variation in colour and brightness over time (well, not time, but space. That is, over a number of pixels).

EDIT: Why would I use the Fourier Transform? And what are its benefits over other methods? For example, one application in literature is in shape recognition or noise elimination. In basic terms, how could one go about shape recognition using the FT?

-

## migrated from stackoverflow.comFeb 26 '13 at 12:50

This question came from our site for professional and enthusiast programmers.

Here's a real-world (if a bit dated) application: use the FFT to efficiently compute compute the normalized cross-correlation between a pattern and an image, used in tracking (or, how they got Tom Hanks to chat with LBJ in "Forrest Gump"): idiom.com/~zilla/Papers/nvisionInterface/nip.html – Franco Callari Feb 25 '13 at 18:20
Mhh, sorry, could you elaborate? I don't fully understand :) – user1796218 Feb 25 '13 at 18:51
You asked: "Why would I use the Fourier Transform?", I gave you a real-word example where the Fast Fourier Transform is used to accelerate the computation of the normalized cross-correlation for feature tracking in a movie sequence. That algorithm was first used in the production of "Forrest Gump", read the paper for details. – Franco Callari Feb 25 '13 at 19:25
This might be of use to you. – Mohammad Feb 26 '13 at 13:47
Really, the Fourier transform breaks a signal up into complex exponentials, so it can measure the magnitude and phase at each point, but maybe this is more confusing than helpful. :D dsp.stackexchange.com/a/449/29 – endolith Feb 26 '13 at 15:35

At a conceptual level, the Fourier Transform tells you what is happening in the image in terms the frequencies of those sinusoids. For example, if you have a picture of a plain wall, the values of the pixels change very little as you go from left to right or from top to bottom. In the frequency domain that means that your image contains low frequencies, but no high frequencies.

On the other hand, if you have a picture of a picket fence, then the values of the pixels change all the time as you go from left to right. So in Fourier domain you have high frequencies in the X direction, but not in the Y direction.

Finally, if you have a picture of a checkerboard, then the pixel values change a lot in both directions. Thus the Fourier transform of the image will have high frequencies in both X and Y.

Because the Fourier transform tells you what is happening in your image, it is often convenient to describe image processing operations in terms of what they do to the frequencies contained in the image. For example, eliminating high frequencies blurs the image. Eliminating low frequencies gives you edges. And enhancing high frequencies while keeping the low frequencies sharpens the image.

FFT is used extensively in image processing and computer vision. For example, convolution, a fundamental image processing operation, can be done much faster by using the FFT. The Wiener filter, used for image deblurring, is defined in therms of the Fourier transform. But more importantly, even when the Fourier transform is not used directly, it provides a very useful framework for reasoning about the image processing operations.

Steve Eddins, one of the authors of "Digital Image Processing with MATLAB", has a whole series of blog posts on the Fourier transform and how it is used in image processing.

-