Others view: Quicksort algorithm ♦ Welcome ♦ 2-3-4 tree ♦ Code 39 ♦ Contact ♦ Reversal potential ♦ Besicovitch set ♦

**Two dimensional Fourier Transform** is a transform that can be applied to an image. It is a similar to to the usual Fourier transform that is extended in two directions.

Same as the usual FFT produces two vectors for the single input (sine coefficients and cosine coefficients, or real and imaginary part), 2D FFT produces to output pictures (real and imaginary) for the single input. For the real world images (as taken with camera) it is usually assumed that the real part is brightness and the imaginary part is 0.

2 dimensional Fourier transform involves a number of 1 dimensional fourier transforms. It is achieved by first transforming each row, replacing each row with its transform and then transforming each column, replacing each column with its transform. This follows directly from the definition of the fourier transform of a continuous variable or the discrete fourier transform of a discrete system. The algorithm is described in more details in ^{[1]} ^{[2]} ^{[3]}.

For the image *f(x,y)*, its 2D FFT *F(u,v)* can be found using formula

[[Math:c| F(u,v)=\frac 1 {MN} \sum_{x=0}^M \sum_{y=0}^N f(x,y) e^{ -j 2 \pi ( ux / M \plus vy / N) } ]]

Here *x, y* are the pixel coordinates in the image and *u, v* are coordinates in the "transformed image".

The inverse transform (from FFT back to the original image, possibly after filtering) can be obtained using formula

[[Math:c| f(x,y)= \sum_{u=0}^M \sum_{v=0}^N F(u,v) e^{ j 2 \pi ( ux / M \plus vy / N) } ]]

These formulas assume calculation using complex numbers ( [[Math:c|j=\sqrt{(-1)}]] ). Raising exponent by such numbers results periodic patterns, important feature of such transforms. *M* and *N* are the image dimensions.

The obtained transform then can be modified by image processing tools, restoring from it altered input image afterwards. This allows to get effects that are difficult to produce by processing the input image directly. Machine vision software also frequently analyses FFT transform of the input as provides information that may be difficult to obtain from the image directly. Hypothesis exists that human vision mechanism internally also uses FFT transform or at least something that looks very similar.

The usual grayscale real world picture only has real part (the brightness or the pixel). Transform also has imaginary part that is represented in applet by colour. If transform is modified, it may produce the version of the initial image that has imaginary part as well. The applet allows to modify both input and transform, allowing to observe the consequences of these changes.

- Java applet was written by BrainFlux (Jason Gallicchio) company and released under GPL. Original version runs here. The applet seem evolving and original version may contain new images or features.

^{1 }Paul Bourke (1993). Detailed description of 1D and 2D FFT transforms, includes formulas and source code in C^{2 }Brayer J.M. Introduction to Fourier transform for image processing.^{3 }2D Fourier Transform, Introduction