How does a 2D Fourier Transform of an image work?

Question

I understand how a 1D Fourier transform separates a signal into its component frequencies, but I'm having difficulty understanding how a 2D Fourier transform affects a 2D image.

From another question, John Calsbeek linked to an interesting paper about measuring the quality of noise functions. This showed various noise functions and the Fourier transform of each.

Is this a discrete transform of the pixel data, or a continuous transform of the continuous interpolating function which is used to generate the noise at arbitrary points?

Is the annular shape analagous to taking 1D Fourier transforms of the line through the centre of the image at every possible angle? Or is the transform for each possible angle also measured across the whole 2D space rather than only along a line through the centre? I'm trying to get an intuitive feel for what changes in the input image correspond to what changes in the Fourier transform.

Answer 1

A 2D Fourier transform is performed by first doing a 1D Fourier transform on each row of the image, then taking the result and doing a 1D Fourier transform on each column. Or vice versa; it doesn't matter.

Just as a 1D Fourier transform allows you to decompose a function into a sum of (1D) sine waves at various frequencies, a 2D Fourier transform decomposes a function as a sum of 2D sine waves. These waves can have different frequencies along the x and y axes. They generically have the form:

$$ \exp \bigl(i \cdot (k_x x + k_y y) \bigr) $$

where $k_x$ and $k_y$ are the frequencies along the $x$ and $y$ axes. These two values form a vector called the wave-vector. In the spatial domain, the wave is oriented along the $(k_x, k_y)$ vector with a frequency along its axis of $\sqrt{k_x^2 + k_y^2}$.

Just as for the 1D Fourier transform, there exist both discrete and continuous versions. The result of a discrete 2D Fourier transform is a matrix of complex amplitudes for a set of discrete $(k_x, k_y)$ values. This is commonly visualized (like in the paper you linked to) as an image where the pixel at coordinates $(k_x, k_y)$ represents the amplitude of that wave-vector.

So, an annular shape in a 2D Fourier transform indicates rotational invariance of the distribution of frequencies (i.e. just as much amplitude for waves in every direction), with a narrow range of magnitudes (from the inside of the annulus to the outside). In other words, the paper is using the Fourier transform to demonstrate that their noise is reasonably isotropic and band-limited.