Dr. Cho’s Website
Course Materials

Introduction to the discrete Fourier transform

Dr. Huidae Cho
Institute for Environmental and Spatial Analysis
University of North Georgia

1   Fourier transform

The Fourier transform is a special case of the Fourier series where $T\rightarrow\infty$.

The period of frequency approaches infinity, which means there are no repeating signals.

2   Discrete Fourier transform

In digital image processing, we use the discrete Fourier transform because digital images are discrete, not continuous.

We are only interested in period $M$ (the number of pixels in a 1-dimensional image strip).

The period $T$ and the number of Fourier transforms can be constrained between $[0, M-1]$.

One-dimensional discrete Fourier transform can be written as \[ F(u)=\frac{1}{M}\sum_{x=0}^{M-1}f(x)e^{-2i\pi ux/M} \]

and

\[ f(x)=\sum_{u=0}^{M-1}F(u)e^{2i\pi ux/M}. \]

3   Meanings of each term in the discrete Fourier transform

\begin{align*} F(0)&=\frac{1}{M}\sum_{x=0}^{M-1}f(x)\\ &\qquad\quad\cdots\\ F(u)&=\frac{1}{M}\sum_{x=0}^{M-1}f(x)e^{-2i\pi(u/M)x}\\ &\qquad\quad\cdots\\ F(M-1)&=\frac{1}{M}\sum_{x=0}^{M-1}f(x)e^{-2i\pi\left[(M-1)/M\right]x}\\ \end{align*}

$F(u)$ represents the $u/M$ frequency meaning that the pixel intensity varies from dark to light and back to dark $u$ times over $M$ pixels.

The contrast between the darkest and lightest pixel values is $2\times F(u)$.

4   One-dimensional exercise

fourier_exercise_1d.py

See how the Fourier spectrum is always positive. Refer to the Properties of the discrete Fourier transform.

1d-pulse-image.png

fourier-transform-of-1d-pulse-image.png

5   Two-dimensional discrete Fourier transform

$f(x,y)$ is an $M\times N$ ($M$ rows, $N$ columns) image.

\[ F(u,v)=\frac{1}{MN}\sum_{x=0}^{M-1}\sum_{y=0}^{N-1}f(x,y)e^{-2i\pi(ux/M+vy/N)} \]

and

\[ f(x,y)=\sum_{u=0}^{M-1}\sum_{v=0}^{N-1}F(u,v)e^{2i\pi(ux/M+vy/N)}. \]

6   Properties of the discrete Fourier transform

Fourier spectrum \[ \left|F(u,v)\right|=\left[R^2(u,v)+I^2(u,v)\right]^{1/2} \]

Fourier phase angle \[ \phi(u,v)=\tan^{-1}\left[\frac{I(u,v)}{R(u,v)}\right] \]

Fourier power spectrum \[ \begin{split} P(u,v) &=\left|F(u,v)\right|^2\\ &=R^2(u,v)+I^2(u,v) \end{split} \]

where $R(u,v)$ and $I(u,v)$ are the real and imaginary parts of $F(u,v)$.

7   Two-dimensional exercise

fourier_exercise_2d.py

See how the Fourier transform of a vertically long rectangle shows a horizontally long pattern.

rectangular-image.png

fourier-transform-of-rectangular-image.png