An overview of Fourier analysis for signal processing

Kristian Sandberg
Dept. of Applied Mathematics
University of Colorado at Boulder

What's the deal with Fourier analysis? Why is Fourier analysis used in such a great variety of applications? These notes try to give an "intuitive" approach to Fourier analysis with emphasis towards signal processing.

Idea

The Fourier transform can separate low- and high- frequency information of a signal.
Low frequencies $\leftrightarrow$ background, overall shape
High frequencies $\leftrightarrow$ details, edges, noise

One-dimensional signals

A one-dimensional signal describe for example a row of an image, a sound signal or an electric current.

**Figure 1:** Example of a Fourier transform of a one-dimensional signal. (Oppposite convention also possible, that is, low frequencies to the left and to the right and high frequencies in the center.)
$\begin{figure} \begin{center} {\epsfxsize=5in \epsfbox{ex1d1.eps} } \end{center} \end{figure}$

**Figure:** Example of a Fourier transform of a one-dimensional signal. The upper row displays the original signal along with the magnitude of its Fourier transform. In the lower left image only the lowest $10\%$ of the frequencies were used to reconstruct the signal. Note how these frequencies can describe the "overall shape" and the rough location of the original signal. However, detailed information about the edges are lost. In the lower right image the highest $90\%$ of the frequencies were used to reconstruct the signal. Note how these high frequencies contain information about the edges and their location. However, the high passed signal tells us little about the overall shape of the original signal.
$\begin{figure} \begin{center} {\epsfxsize=5in \epsfbox{ex1d2.eps} } \end{center} \end{figure}$

**Figure:** Example of a Fourier transform of a one-dimensional signal. The upper row displays the original "noisy" signal along with the magnitude of its Fourier transform. In the lower left image only the lowest $10\%$ of the frequencies were used to reconstruct the signal. Most of the noise is gone! In the lower right image the highest $90\%$ of the frequencies were used to reconstruct the signal. This reconstruction contains mainly noise.
$\begin{figure} \begin{center} {\epsfxsize=5in \epsfbox{ex1d3.eps} } \end{center} \end{figure}$

What's going on mathematically?

A signal can be described as a function f(x).
Functions can be thought of as vectors in a vector space.
We can introduce an orthonormal basis in the vector space of periodic functions by

$\begin{displaymath}\{ e^{2\pi i kx} \}_{k=0}^\infty = \{ \cos(2\pi kx)+i\sin(2\pi kx) \}_{k=0}^\infty \ . \end{displaymath}$
By using the orthogonal decomposition theorem we can expand f(x) as

$\begin{displaymath}f(x) = \sum_{k=0}^\infty < f(x),e^{2\pi i kx}> \ e^{2\pi ikx} \ . \end{displaymath}$
The (magnitude of the) expansion coefficients

$\begin{displaymath}< f(x),e^{2\pi i kx} \ > \ =\int_0^1 f(x)e^{-2\pi ikx}\ dx \end{displaymath}$

are the numbers displayed in upper right plots in the examples above.
A basis function $e^{2\pi i kx}$ with a large k is a rapidly oscillating function.
Rapidly oscillating basis functions can pick up details of a function.
A basis function $e^{2\pi i kx}$ with a small k is a slowly oscillating function.
Slowly oscillating basis functions can pick up overall shape of a function, but cannot pick up information about details of the function.
The expansion coefficients are computed by

$\begin{displaymath}< f(x),e^{2\pi i kx} \ > \ =\int_0^1 f(x)e^{-2\pi ikx}\ dx \s... ...c{1}{N}\sum_{k=0}^N f(\frac{n}{N})e^{-2\pi ik\frac{n}{N}} \ . \end{displaymath}$

This sum is called the Discrete Fourier Transform (DFT).
By a clever organization of the computations, these sums can be computed in a "fast" manner called the Fast Fourier Transform (FFT).

Two-dimensional signals

Two-dimensional signals can be represented by matrices.
An image is a two-dimensional signal.
We can represent a two-dimensional signal as a surface or as an image. When displayed as an image, a large magnitude is represented by the color white and a small magnitude is represented by the color black.
We get the two-dimensional Fourier transform by performing a sequence of one-dimensional transforms on all the rows and all the columns.
The magnitude of the two-dimensional Fourier transform can also be represented as an image. Low frequencies are located in the center of the image and high frequencies are located towards the edges. (Opposite convention also possible.)
The two-dimensional Fourier transform contains information about the direction of features in the original signal.

**Figure 4:** Example of a Fourier transform of a two-dimensional signal. The image does not have any variation in the vertical direction, and therefore no vertical frequencies. The image contains high horizontal frequencies that describe the edges of the line.
$\begin{figure} \begin{center} {\epsfxsize=5in \epsfbox{ex2d1.eps} } \end{center} \end{figure}$

**Figure 5:** Example of a Fourier transform of a two-dimensional signal. The image does not have any variation in the horizontal direction, and therefore no horizontal frequencies. The image contains high vertical frequencies that describe the edges of the line.
$\begin{figure} \begin{center} {\epsfxsize=5in \epsfbox{ex2d2.eps} } \end{center} \end{figure}$

**Figure 6:** The upper left image contains the original signal and the upper right image the magnitude of its Fourier transform. The lower left image contains a low-passed reconstruction of the signal (only low frequencies used for reconstruction) which gives a rough picture of the overall shape. The lower right image contains a high-passed reconstruction of the signal where only the highest frequencies were used. Note how the edges are emphasized.
$\begin{figure} \begin{center} {\epsfxsize=5in \epsfbox{ex2d3.eps} } \end{center} \end{figure}$

About this document ...

An overview of Fourier analysis for signal processing

This document was generated using the LaTeX2HTML translator Version 98.1 release (February 19th, 1998)

The command line arguments were:
latex2html -split 0 -no_navigation fourier.tex.

The translation was initiated by Kristian Sandberg on 2001-11-19

Kristian Sandberg
2001-11-19