Uniqki: A Personal Wiki Builder
A Uniqki site

Introduction to the discrete Fourier transform

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   Exercise: One-dimensional image

fourier_exercise_1d.py

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

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   Exercise: Two-dimensional image

fourier_exercise_2d.py

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