FFT 2D

This is an example of a 2D discrete Fourier transform, applied to greyscale images. The leftmost images are the input, the center images and rightmost images represent the magnitude and phase of the Fourier transform. Note that for the magnitude plot, the 0 frequency is in the middle, with positive to the right and negative frequencies to the left.

Joseph Fourier

Magnitude

Phase

Sierpinsky fr.

Magnitude

Phase

Polar shape

Magnitude

Phase

Aliased circle

Magnitude

Phase

Video

Implementation

The implementation of the 2D Fourier Transform uses a regular 1D FFT function for every row of the image, then for every column of the result. The simplest way to implement this is by transforming every row of the input, rotating the resulting data (so that columns become rows), transforming the rotated data, and then rotating it back.

Using this FFT function:

void FFT( complex *data, int data_size );

I implemented the FFT2D like this:

void FFT2D(complex *data, int w, int h)
{
    // Transform every row
    for (int y = 0; y < h; ++y)
	FFT(&data[y * w], w);

    rotate_left();

    for (int y = 0; y < w; ++y)
	FFT(&data[y * h], h);

    rotate_right();
}

Fraunhofer Diffraction

I discovered randomly that the light diffraction pattern created by sending light through a rectangular aperture is the same as the 2D Fourier Transform of a rectangular signal.

Below you can see the input on the left: a small white rectangle on a black background, and on the right the magnitude plot of the 2D Fourier Transform of the input:

Left: Square input, Right: Magnitude of Fourier Transform of input

Below, you see a frame grab from an experiment showing Fraunhofer diffraction from shooting a laser beam through a rectangular aperture. It shows the exact same pattern:

Fraunhofer diffraction of laser beam through rectangular aperture

The full experiment is shown here: Prof. Shaoul Ezekiel (MIT): 'Optics: Fraunhofer and Fresnel Diffraction' See also Wikipedia: Fraunhofer diffraction equation for showing that the diffraction and Fourier transform of the aperture function are the same.

Download

This executable demonstrates the 2D Fourier Transform with a few examples. Download Win32 zip