In 2D, $f$ is a function of two variables: $f(x,y)$. Suppose
$x \in [0,N)$ and $y \in [0,M)$. Then the 2D DFT is
$\displaystyle F(u,v) = \sum_{y=0}^{M-1} \;\;
\underbrace{\left( \sum_{x=0}^{N-1} f(x,y) \; e^{\large -i {2 \pi x \over N} u} \right)}_{\Large F(u,y)}
\;\; e^{\large -i {2 \pi y \over M} v}$
where $F(u,y)$ is the FT of row $y$ for wavenumber $u$.
Equivalently,
$\displaystyle F(u,v) = \sum_{x=0}^{N-1} \;\;
\underbrace{\left( \sum_{y=0}^{M-1} f(x,y) \; e^{\large -i {2 \pi y \over M} v} \right)}_{\Large F(x,v)}
\;\; e^{\large -i {2 \pi x \over N} u}$
where $F(x,v)$ is the FT of column $x$ for wavenumber $v$.
So $F(u,v)$ can be computed in two steps:
- Compute $F(u,y)$ for all $(u,y)$.
- Use $F(u,y)$ to compute $F(u,v)$ for all $(u,v)$.
For simplicity, let both dimensions be of size $N$. Then the 2D DFT is
$\begin{array}{rl}
\displaystyle F(u,v)
= & \sum_{x=0}^{N-1} \;\; \sum_{y=0}^{N-1} f(x,y) \; e^{\large -i {2 \pi y \over N} v} \;\; e^{\large -i {2 \pi x \over N} u} \\
= & \underbrace{\sum_x \; \sum_y}_\textrm{sum over the 2D domain} \;\; f(x,y) \;\; \underbrace{e^{\large -i {2 \pi \over N} (xu + yv)}}_\textrm{2D basis function in $u$ and $v$} \\
\end{array}$
So, for a particular $u$ and $v$, the double summation projects
the 2D function, $f(x,y)$, onto a 2D basis function, $e^{\large i {2
\pi \over N} (x u + y v)}$.
In the exponent is
$\begin{array}{rl}
xu + yv & = (x,y) \cdot (u,v) \\
& = \underbrace{ (x,y) \cdot (u,v) \over \mid (u,v) \mid }_t \; \underbrace{\mid (u,v) \mid}_k \\
& = t \; k
\end{array}$
where
- $t$ is the length of the projection of $(x,y)$ onto the line of $(u,v)$, and
- $k$ is the distance of $(u,v)$ from the origin.
So the 2D DFT becomes
$\displaystyle F(u,v) = \sum_x \; \sum_y \;\; f(x,y) \;\; e^{\large -i {2 \: \pi \: t \over N} k}$
Above, $k$ acts as the wavenumber and $t$ acts as the position on the wave.
$k$ and $t$ are shown below:
The real insight is that all points $(x,y)$ with the same
projection, $t$, onto the line of $(u,v)$ have the same
position on the wave since they have the same value for
$e^{\large i {2 \: \pi \: t \over N} k}$.
For a particular $t$, these $(x,y)$ lie on a line perpendicular to $(u,v)$.
So the crest of the wave is perpendicular to $(u,v)$ and the
wave travels in direction $(u,v)$.
The wave's wavenumber (i.e. the number of cycles in $[0,N)$) is
equal to $k$, the distance of $(u,v)$ from the origin.
So a position $(u,v)$ in the 2D FT
corresponds to a wave travelling in the direction $(u,v)$ with
wavenumber $\mid (u,v) \mid$.
And $F(u,v)$ contains the complex coefficient which define the
wave's amplitude and phase.
Let $B_{u,v}(x,y)$ be the complex Fourier basis function for
wavenumbers $u$ and $v$. We saw above that this is a
sinusoidal wave travelling through the image in direction
$(u,v)$ with wavenumber $| (u,v) |$.
Here are some of the basis functions travelling in
the horizontal direction. The brightest parts correspond
to a value of +1, while the darkest parts correspond to a
value of -1. Note that the wavenumbers are 1, 2, and 3,
corresponding to 1, 2, and 3 cycles of the sinusoid in the
horizontal direction:
$\mathbf{B_{1,0}(x,y)}$
(wavenumber 1) |
$\mathbf{B_{2,0}(x,y)}$
(wavenumber 2) |
$\mathbf{B_{3,0}(x,y)}$
(wavenumber 3) |
 |
 |
 |
Other basis functions travel in other directions and have
other wavenumbers, like these:
$\mathbf{B_{8,4}(x,y)}$
(wavenumber 8.94) |
$\mathbf{B_{17,6}(x,y)}$
(wavenumber 18.03) |
$\mathbf{B_{54,43}(x,y)}$
(wavenumber 69.03) |
$\mathbf{B_{-5,11}(x,y)}$
(wavenumber 12.08) |
 |
 |
 |
 |
When we project our image, $f(x,y)$, onto $B_{u,v}(x,y)$,
we get a complex coefficient, $c_{u,v}$, which is stored in
location $(u,v)$ of the Fourier Transform. In most
visualizations of the Fourier domain, the origin is in the
centre, $u$ is the horizontal axis, and $v$ is the vertical
axis. Here's a Fourier Transform with the origin in the
centre, showing only the magnitudes of the
$c_{u,v}$:
Note that point $(0,0)$ in the Transform is the "DC"
component, and the corresponding basis function,
$B_{0,0}(x,y)$, is equal to 1 everywhere. Projecting $f(x,y)$
onto $B_{0,0}(x,y)$ and normalizing by ${1 \over M N}$ for an
$M \times N$ image yields the average value of the
image. For this reason, the $c_{0,0}$ coefficient is usually
much, much larger than all the other $c_{u,v}$ in the Transform.
