FFT 2D

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

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();
}