Introduction to the discrete Fourier transform
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
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
See how the Fourier transform of a vertically long rectangle shows a horizontally long pattern.
