Fourier transform

For a square image of size NxN the two dimensional DFT is given by:

`F(k,l)=1/(N^2)sum_(i=0)^(N-1)sum_(j=0)^(N-1)f(i,j)e^(-i2pi((ki)/N + (ij)/N)```

where `f(i,j)` = is the image in the [[spatial domain]] and the exponential term is the basic function corresponding for each point F(k,l) in the Fourier space. The equatation can be interpreted as: the value of each point F(k,l) is obtained by multiplying the spatial image with the corresponding base function and summing the result.

The picture below shows 2 images with their Fourier Transforms directly underneath. The images are a pure horizontal cosine of 8 cycles and a pure vertical cosine of 32 cycles. Notice that the FT for each just has a single component, represented by 2 bright spots symmetrically placed about the enter of the FT image. The center of the image is the origin of the frequency coordinate system. The u-axis runs left to right through the center and represents the horizontal component of frequency. The v-axis runs bottom to top through the center and represents the vertical component of frequency. In both cases there is a dot at the center that represents the (0,0) frequency term or average value of the image. Images usually have a large average value (like 128) and lots of low frequency information so FT images usually have a bright blob of components near the center. Notice that high frequencies in the vertical direction will cause bright dots away from the center in the vertical direction. And that high frequencies in the horizontal direction will cause bright dots away from the center in the horizontal direction.

Here are 2 images of more general Fourier components. They are images of 2D cosines with both horizontal and vertical components. The one on the left has 4 cycles horizontally and 16 cycles vertically. The one on the right has 32 cycles horizontally and 2 cycles vertically. (Note: You see a gray band when the function goes through gray = 128 which happens twice/cycle.) You may begin to notice there is a lot of symmetry. For all REAL (as opposed to IMAGINARY or COMPLEX) images, the FT is symmetrical about the origin so the 1st and 3rd quadrants are the same and the 2nd and 4th quadrants are the same. If the image is symmetrical about the x-axis (as the cosine images are) 4-fold symmetry results.


Sources:
http://homepages.inf.ed.ac.uk/rbf/HIPR2/fourier.htm
http://www.cs.unm.edu/~brayer/vision/fourier.html
http://research.stowers-institute.org/efg/Report/FourierAnalysis.pdf