Image FFT bench: the spectrum as a column field (3D)

The transform

For an N x N image x(m,n) the 2D discrete Fourier transform is X(u,v) = sum_m sum_n x(m,n) e^(-2 pi i (u m + v n)/N). It is separable, so the page runs a radix-2 Cooley-Tukey FFT on every row and then on every column: O(N^2 log N) instead of O(N^4). The inverse uses the opposite sign and a factor 1/N^2 (one 1/N per direction).

Reading the spectrum

After fftshift the middle is the DC term X(0,0)/N^2 = mean brightness. A bin at (u,v) is a plane wave with sqrt(u^2+v^2) cycles per image, travelling at angle atan2(v,u). A pure grating 0.5 + 0.5 sin(2 pi (k m)/N) therefore gives exactly two spikes at (+-k, 0) with height N^2/4. Real images obey the Hermitian symmetry X(-u,-v) = conj X(u,v), which is why every spectrum is point-symmetric.

Parseval and the shift theorem

Energy is conserved: sum |x|^2 = (1/N^2) sum |X|^2. A circular shift by (dx, dy) multiplies the spectrum by a pure phase, X'(u,v) = X(u,v) e^(-2 pi i (u dx + v dy)/N), so |X| does not change and only the phase turns; the fourth graph compares the measured phase of Y/X with that line.

Filters

A filter multiplies X by a mask M(u,v) and transforms back. An ideal low-pass is a disc; its inverse is a sinc-like kernel, hence the ringing near edges. The Gaussian option uses exp(-r^2/(2R^2)), which has no ringing. High-pass is the complement, band-pass a ring, the notch removes the ring at the dominant frequency.

Numerical checks and honest simplifications

• Parseval holds to rounding error (about 1e-15 relative).
• The shift theorem is tested by really shifting the image and transforming it again.
• The fast transform is compared with the direct O(N^4) definition on an 8 x 8 test image.
• The image is assumed periodic (the DFT wraps around), so a shifted image wraps, and edges that do not match produce leakage across the spectrum; no window function is applied.
• Images are small synthetic test patterns (64 or 128 pixels), not photographs, and grey levels are shown after min-max scaling.

What you see in 3D

The two monitors show the image x(m,n) and the filtered reconstruction. The column field in front is the spectrum after fftshift: the middle column is the DC term, a column at distance r from the middle is a wave with r cycles per image. Column height is log(1+|X|), colour is the same magnitude ramp (or the phase wheel). A filter lowers the removed columns, so you see which frequencies reach the result. The numbers come from the same engine as the 2D page.