next up previous
Next: Two-dimensional Fourier Filtering Up: Image_Processing Previous: Fast Fourier Transform

Two-Dimensional Fourier Transform

Fourier transform can be generalized to higher dimensions. For example, many signals $f(x,y)$ are functions of 2D space defined over an x-y plane. Two-dimensional Fourier transform also has four different forms depending on whether the 2D signal is periodic and discrete.

Physical Meaning of 2DFT

Consider the Fourier transform of continuous, aperiodic signal (the result is easily generalized to other cases):

\begin{displaymath}F(u,v)=\int \int_{-\infty}^{\infty} f(x,y) e^{-j2\pi(xu+yv)} dx\;dy \end{displaymath}


\begin{displaymath}f(x,y)=\int \int_{-\infty}^{\infty} F(u,v) e^{ j2\pi(xu+yv)} du\;dv \end{displaymath}

The inverse transform represents the spatial function $f(x,y)$ as a linear combination of complex exponentials $e^{ j2\pi(xu+yv)}$ with complex weights $F(u,v)$.

Now the 2DFT of a signal $f(x,y)$ can be written as:

\begin{displaymath}
f(x,y)=\int\int_{-\infty}^{\infty} \vert F(u,v)\vert e^{j\an...
...t e^{j(\angle{F(u,v)}+2\pi w(\vec{r} \cdot \vec{n}))}
\;du\;dv
\end{displaymath}

which represents a signal $f(x,y)$ as a linear combination (integration) of infinite 2D spatial planar sinusoids $F(u,v)$ of

The 2D function shown below contains three frequency components (2D sinusoidal waves) of different frequencies and directions:

sin_wave.gif

Matrix Form of 2D DFT

Consider the 2D DFT:

\begin{displaymath}
X[k,l] = \frac{1}{\sqrt{N}}\sum_{n=0}^{N-1} [ \frac{1}{\sqr...
...sum_{n=0}^{N-1} w_N[n,l] [ \sum_{m=0}^{M-1} w_M[m,k] x[m,n] ]
\end{displaymath}

where, as defined before

\begin{displaymath}w_M[m,k]\stackrel{\triangle}{=} \frac{1}{\sqrt{M}}e^{-j2\pi m...
...[n,l]\stackrel{\triangle}{=} \frac{1}{\sqrt{N}}e^{-j2\pi nl/N} \end{displaymath}

We further define

\begin{displaymath}X'[k,n]\stackrel{\triangle}{=} \sum_{m=0}^{M-1} w_M[m,k] x[m,n],
\;\;\;(k=0,1,\cdots,M-1) \end{displaymath}

and rewrite the 2D transform as

\begin{displaymath}X[k,l] = \sum_{n=0}^{N-1} w_N[n,l] X'[k,n],
\;\;\;(l=0,1,\cdots,N-1) \end{displaymath}

The above two equations are the two steps for a 2D transform:
  1. Column Transform:

    First consider the expression for $X'[k,n]$. As the summation is with respect to the row index $m$ of $x[m,n]$, the column index $n$ can be treated as a parameter, and the expression is the 1D Fourier transform of the nth column vector of ${\bf x}$, which can be written in column vector (vertical) form for the nth column:

    \begin{displaymath}\left[ \begin{array}{c}X'[0,n]  \cdots  X'[M-1,n]\end{arr...
...c} x[0,n]  \cdots  x[M-1,n]\end{array} \right]_{M\times 1}
\end{displaymath}

    or more concisely

    \begin{displaymath}{\bf X'}_n={\bf W}_M{\bf x}_n,\;\;\;\;(n=0,\cdots,N-1) \end{displaymath}

    i.e., the nth column of ${\bf X'}$ is the 1D FT of the nth column of ${\bf x}$. Putting all $N$ columns together, we have

    \begin{displaymath}[ {\bf X'}_0,\cdots,{\bf X'}_{N-1}]=
{\bf W}_M   [ {\bf x}_0,\cdots,{\bf x}_{N-1} ] \end{displaymath}

    or more concisely

    \begin{displaymath}{\bf X'}= {\bf W}_M   {\bf x} \end{displaymath}

    where ${\bf W}_M$ is a $M$ by $M$ Fourier transform matrix.

  2. Row Transform:

    Now we reconsider the 2DFT expression above

    \begin{displaymath}X[k,l] = \sum_{n=0}^{N-1} w_N[n,l] X'[k,n] \end{displaymath}

    As the summation is with respective to the column index n of $X'[k,n]$, the row index $k$ can be treated as a parameter, and the expression is the 1D Fourier transform of the kth row vector of ${\bf X'}$, which can be written in row vector (horizontal) form for the kth row:

    \begin{displaymath}[ X[k,0], \cdots, X'[k,N-1] ]=[ X'[k,0], \cdots, X'[k,N-1] ]
...
...[n,l] & \cdots  \cdots & \cdots & \cdots \end{array} \right]
\end{displaymath}

    or more concisely

    \begin{displaymath}{\bf X}_k^T= {\bf X'}_k^T {\bf W}_N,\;\;\;\;(k=0,\cdots,M-1) \end{displaymath}

    i.e., the kth row of ${\bf X}$ is the 1D FT of the kth row of ${\bf X'}$. Putting all $M$ rows together, we have

    \begin{displaymath}\left[ \begin{array}{c}
{\bf X}_0^T  . . {\bf X}_{M-1}...
...^T  . . {\bf X'}_{M-1}^T \end{array} \right]
{\bf W}_N
\end{displaymath}

    or more concisely

    \begin{displaymath}{\bf X} = {\bf X'} {\bf W}_N \end{displaymath}

    But as $ {\bf X'} = {\bf W}_M   {\bf x} $, we finally have

    \begin{displaymath}{\bf X} ={\bf W}_M   {\bf x}   {\bf W}_N \end{displaymath}

This expression indicates that 2D DFT can be carried out by 1D transforming all the rows of the 2D signal ${\bf x}$ and then 1D transforming all the columns of the resulting matrix. The order of the steps is not important. The transform can also be carried out by the column transform followed by the row transform.

Similarly, the inverse 2D DFT can be written as

\begin{displaymath}{\bf x}= {\bf W}_M^*   {\bf X}  {\bf W_N}^* \end{displaymath}

It is obvious that the complexity of 2D DFT is $O(N^3)$ (assuming $M=N$), which can be reduced to $O(N^2 log_2 N)$ if FFT is used.

A 2D DFT Example

Consider a real 2D signal:

\begin{displaymath}{\bf x}_r=\left[
\begin{array}{rrrrrrrr}
0.0 & 0.0 & 0.0 & 0...
...& 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0 & 0.0
\end{array} \right]
\end{displaymath}

The imaginary part ${\bf x}_i={\bf0}$. The 2D Fourier spectrum ${\bf X}$ of this signal can be found by 2D DFT. The real part of the spectrum is:

\begin{displaymath}{\bf X}_r = \left[
\begin{array}{r\vert rrr\vert r\vert rrr} ...
...-32.7 & 1.6 & -21.0 & 13.2 & 27.7 & -11.3
\end{array} \right] \end{displaymath}

and the imaginary part of the spectrum is:

\begin{displaymath}{\bf X}_i = \left[
\begin{array}{r\vert rrr\vert r\vert rrr} ...
...0 & -16.8 & 30.2 & -6.9 & 27.1 & -89.2 \\
\end{array} \right] \end{displaymath}

Pay close attention to the even and odd symmetry of the spectrum.


next up previous
Next: Two-dimensional Fourier Filtering Up: Image_Processing Previous: Fast Fourier Transform
Ruye Wang 2007-11-15