2-D Image Fourier Transform

Last updated on 03/05/2000
by Jason Plumb

This project involves reading in an image (in PGM format) and computing the 2-D FFT of the image.  The intended application is to determine the spatial domain configuration of a wire mesh imprint left on counterfeit money.

The final report project, including software instruction manual can be found here.

Download files:

• pgmfile.h, pgmfile.cpp - Helper class for dealing with PGM files.  Has a bug-fix that prevented ASCII format PGM files from being read properly.
• fourier.h, fourier.cpp - Main application files
• four1.h, four1.cpp - 1-D FFT routine files (from Numerical Recipes Software)
• fourier.exe - Executable program file

Notes/Problems:

When constructing the code for this project, I ran into several pitfalls that I thought I would briefly discuss here to help others avoid making the same mistakes.  Most of these are stupid mistakes that can be avoided by reading documents in detail...but I'm lazy.

• The four1 function supplied to us is only capable of performing a 1-D FFT.  This means that in order to use this function to do a 2-D FFT on the input image, you will need to make use of the separability concept.  This means that you will need to do a 1-D FFT for each row, multiply the result (real and imaginary) by the image width, and store the results.  Then perform a 1-D FFT on each column and store the result.
• The nn parameter passed to the four1 function must be a power of 2.  This is a real pain -- it means that you have to create a new arrays with new sizes that are powers of 2.
• The size of the array passed to the four1 function should be double the number of real input points.  This is due to the fact that the four1 function will return both real and imaginary parts in the same array.
• If your arrays are 0 based (which if you're coding in C they probably are), you must pass array-1 as the first parameter to the four1 function.  If you don't do this, the four1 function will probably write out of the array bounds and all sorts of problems will crop up.
• I have no idea why, but I had to invert the image after performing the FFT to get it to look right.  This may be a problem with my drawing method, but I don't see it.  Very strange strange strange.