Notes on 2D FFT for Images

These notes revisit the two-dimensional Discrete Fourier Transform (DFT) of an image through the group-theoretic lens emphasised by Maslen and Rockmore, tracing it from the theory to the libraries. The DFT of an image is the Fourier transform on the group ℤ_N × ℤ_M and a few facts about that group do most of the work: its direct-product form is why the 2D transform separates into one-dimensional transforms, and the way a transform length factors into smaller pieces is what the Cooley–Tukey algorithm exploits. When a length resists such factoring, libraries fall back on Bluestein's algorithm. These are the choices that cuFFT, FFTW (and hence MATLAB's fft2) and OpenCV make in practice.