fourier transform of images

The Fourier transform re-expresses an image not as a grid of pixel intensities but as a sum of 2D waves, sinusoidal ripples of brightness at every possible frequency and orientation. Just as a musical chord can be decomposed into its constituent pure tones, an image can be decomposed into its constituent spatial frequencies. Low frequencies describe slow, broad variations (the overall shading, large smooth regions); high frequencies describe rapid variations (sharp edges, fine texture, and noise). Moving to this frequency domain turns many spatial operations into something far simpler.

Formally the 2D discrete Fourier transform of an M-by-N image f is F(u,v) = sum over x,y of f(x,y) * exp(-j*2*pi*(u*x/M + v*y/N)), a complex number for each frequency pair (u,v). Its magnitude gives the strength of that frequency (usually displayed as the magnitude spectrum, with the DC or zero-frequency term shifted to the center via fftshift), and its phase encodes where features sit; perceptually the phase carries most of the image's structure. The computation is made practical by the Fast Fourier Transform (FFT), which reduces the cost from order N-squared to order N log N.

The payoff is the convolution theorem: convolution in the spatial domain equals simple pointwise multiplication in the frequency domain. So filtering becomes multiply the image's spectrum by the filter's spectrum, then transform back, often faster than a large spatial convolution, and conceptually transparent. A low-pass filter keeps the center of the spectrum (smoothing), a high-pass keeps the outside (edges/sharpening), a band-pass keeps a ring, and a notch filter deletes a specific frequency to kill periodic interference such as scanner stripes or power-line hum. The pitfalls are that the DFT assumes the image tiles periodically, so opposite edges that do not match create cross-shaped spectral artifacts (cured by windowing), and an ideal brick-wall filter causes ringing (the Gibbs phenomenon), so smooth filters like Gaussian or Butterworth are preferred.