Image processing uses processes called "Transforms" to manipulate and compress images. These "transformations" include the Fourier Transform (FT), Walsh Transform, Hadamard Transform, Discrete Cosine Transform (DCT), Haar Transform, and Slant Transform. Of all these transforms, the best known is the Fourier Transform. Deriving the other transforms is usually analogous to the derivation of the FT.

Essentially, the Fourier Transform maps a given function f(x) from the Spatial Domain (of x) into the Frequency Domain (u) using the Fourier Function F(u). This is useful for implementing frequency filters and other processing techniques. For this transformation to work, f(x) must be integratable and continuous over the range (+infinity,-infinity).

The Fourier Transform of f(x) (in one dimension) is given by:

where e represents the natural log and  i is the square root of (-1) and thus F(u) is usually a complex function.

When given the Fourier Transform, the original function can be derived using the formula:

When graphed, the spectrum of F(u) is usually graphed. The spectrum is defined as (here with "|" being used in the sense of "absolute value" notation):

or the absolute value or magnitude of F(u) using the length of the hypotenuse of the complex number when graphed on the Argand plane. In the same way as the one dimensional Fourier Transform, a two dimensional function can also be derived using:

and its inverse Fourier Transform:

Resolution of Complex numbers in a form suitable for computer manipulation involves invoking Euler's Formula of the form:

Discrete Fourier Transforms

Because computers cannot handle continuous functions, the Fourier Transform is "discretized" over some arbitrary range using the formula:

where (1/N) becomes a scaling factor for the total of N points in the set. The two dimensional Discrete Fourier Transform (DFT) is derived analogously.

Fast Fourier Transforms

One problem with Discrete Fourier Transforms is their computation cost. A one dimensional transform takes n² cycles to compute: one cycle for each value of x and one for each value of u (since u=x). This cost is even more excessive for two dimensional transforms where we need to cycle through each value of x,y,u and v for a O(n)=n⁴. These costs make Fourier Transforms difficult to compute for all but very small images (where x is very small).

Fortunately, this computation cost can be reduced using a technique called the Fast Fourier Transform (FFT). Information, discussions, and algorithms for the FFT are available throughout the internet and a selection of links is provided below. Using FFT, the computational effort required to derive the one dimensional FT is now n*log₂n and for the two dimensional FT, O(n)=n²log₂n--a very dramatic improvement.

Results

To illustrate what Fourier Transforms look like, the left hand image is the image of f(x), and the image on the right its respective Fourier Transform. The 32 and 64 bit images were created using the Discrete Fourier Transform using the code supplied. The 256 bit images were created using the Fast Fourier Transform algorithm. In all cases, the Fourier Transforms were rotated 90 degrees around the origin to shift the image to the center of the display. Note: All the images have been scaled to the same size for consistency of appearance.

As can be seen from the transforms, the image is a sparsely populated set of data points. Compression is possible by measuring a radius from the middle and then truncating all points outside of the resulting circle. This compression will also lose some higher frequency detail. Alternatively, truncating data points within the middle of the image will result in a loss of low frequency components of the image.

The accompanying source code is copyright the author and all rights are reserved. Please do not reproduce this code for any projects, publications, or assignments without the express permission of the author.

Code

My code (in C) for Fourier Transforms is available.

main.c

The main program controls the file I/O, image parsing, conversion to complex numbers, and image representation functions. Note that the size of the image is hard coded as precompiler directives. The code could also receive the image size as a parameter and utilize calloc calls to create the necessary arrays. Verbose output is available by defining _DEBUG_ as a precompiler directive.

img.h

Global variables and struct definitions and functions supporting Complex number calculations.

fft.h

The header file for the Discrete Fourier Transform, Fast Fourier Transform and supporting functions. The reverse function performs a bit-wise reversal of the image array's subscripts. The bit_print function is courtesy of the Al Kelley and Ira Pohl book A Book on C.

fft.c

The source code for the functions contained in fft.h

Other References

• Fast Fourier Transform