CISC 457, Lecture 16 - 2D Discrete Fourier Transform

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)$.

2D Inverse DFT

Visualizing the 2D DFT

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.

Intuition

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)

$B_{1,0}(x,y)$ $B_{2,0}(x,y)$ $B_{3,0}(x,y)$

$\mathbf{B_{1,0}(x,y)}$ (wavenumber 1)	$\mathbf{B_{2,0}(x,y)}$ (wavenumber 2)	$\mathbf{B_{3,0}(x,y)}$ (wavenumber 3)
$B_{1,0}(x,y)$	$B_{2,0}(x,y)$	$B_{3,0}(x,y)$

Other basis functions travel in other directions and have other wavenumbers, like these below.

The red circle in each image has diameter equal to the image width, and can be used to count how many cycles there are per image width in the direction of travel.

Suppose $k$ is the number of cycles per image width in the direction of travel. Then the wavenumbers $(u,v)$ are a distance $k$ from the origin in the Fourier domain, so $k = \sqrt{u^2+v^2}$. Knowing $k$ and the direction (or angle) of travel allows you to calculate $u$ and $v$.

$\mathbf{B_{8,4}(x,y)}$
(wavenumber 8.94) $\mathbf{B_{17,6}(x,y)}$
(wavenumber 18.03)

$B_{8,4}(x,y)$ $B_{17,6}(x,y)$

$\mathbf{B_{-5,11}(x,y)}$
(wavenumber 12.08) $\mathbf{B_{54,43}(x,y)}$
(wavenumber 69.03)

$B_{-5,11}(x,y)$ $B_{54,43}(x,y)$

$\mathbf{B_{8,4}(x,y)}$ (wavenumber 8.94)	$\mathbf{B_{17,6}(x,y)}$ (wavenumber 18.03)
$B_{8,4}(x,y)$	$B_{17,6}(x,y)$

$\mathbf{B_{-5,11}(x,y)}$ (wavenumber 12.08)	$\mathbf{B_{54,43}(x,y)}$ (wavenumber 69.03)
$B_{-5,11}(x,y)$	$B_{54,43}(x,y)$

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.