Others view: Nussinov algorithm ♦ XOR gate ♦ Welcome ♦ Atomic orbitals ♦ Forum and issue tracker ♦ Reversal potential/ ♦ Biomorphs ♦ Matrix ♦

2D Fast Fourier Transform

2D FFT demo. Left side shows original image, right side - transformed result. Pictures at the bottom are image presets. Middle area allows to manipulate images. For instance, by moving the input picture with hand tool you see how FFT output depends on the position of the object. Same way moving FFT transform shows the image, represented by such shifted transform. Other three tools are painting tools. They allow you to alter both initial and transformed output and observe how does it impact another image. The button in the centre is the value selector for the painting tools that allows to pick values in the complex plane. Other tools and applet in general are described through the messages at the bottom line. The applet is well documented at http://www.brainflux.org/Math/Fourier_Analysis/2D_Fourier/index.html

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.

Real and imaginary parts

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.

Algorithm


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



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



These formulas assume calculation using complex numbers ( ). Raising exponent by such numbers results periodic patterns, important feature of such transforms. M and N are the image dimensions.

FFT transform of the square (the dashed outline of the square is not part of the transform)
FFT transform of the square (the dashed outline of the square is not part of the transform)

Applications

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.

Acknowledgements

  • 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.

References

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