The discrete Fourier transform

So far, we have been considering functions defined on the continuous line. In digital images we can only process a function defined on a discrete set of points. This leads us to the discrete Fourier transform(DFT), whose equations are very similar to those for the continuous Fourier transform.

The DFT provides information over a discrete number of frequencies, so we need to determine precisely which frequencies these are. To do this, we sample a continuous function f at intervals of $\Delta$, generating a sequence of sampled values

$$f_k = f(k \Delta),$$

where $k = \ldots, -2, -1, 0, 1, 2, \ldots$The reciprocal of $\Delta$ is the sampling rate, or frequency. For any sampling interval $\Delta$, there is a special frequency $\omega_c$ called the Nyquist critical frequency:

$$\omega_c = \frac{1}{2 \Delta}.$$

The Nyquist frequency represents the highest frequency that can be represented by something sampled at intervals of $\Delta$, that is, a frequency having wavelength of $2 \Delta$. Alternatively, if one is seeking to describe a function by a set of discrete values, we must sample the function at 2 times the highest frequency in the function.

For example, critical sampling of a sine wave is at 2 sample points per cycle; sampling at any slower rate will ``miss'' the sine wave.

 

Figure 8: Critical sampling of a sine wave. Sampling at a slower rate will miss the structure of the particular sine wave.

If we wish to take the Fourier transform of N sampled values of a function $\{f_k, k = 0, 1, \ldots \}$ with N items of input, then we will not be able to produce more than N independent items of output.

We generate the Fourier transform at discrete frequencies

$$\omega_n = \frac{n}{N \Delta},$$

where $n = \frac{-N}{2}, \frac{-N}{2} + 1, \ldots, \frac{N}{2}.$These limits correspond to the upper and lower Nyquist frequencies.

We now approximate the integral equation for the Fourier transform by a discrete summation:

Typically, the sampling distance $\Delta$ is set to 1, so the discrete Fourier transform is given by

$$F_n = \sum_{k=0}^{N-1} f_k e^{-2 \pi i kn/N}.$$

The inverse discrete Fourier transform is given by

$$f_k = \frac{1}{N} \sum_{n=0}^{N-1} F_n e^{2 \pi i kn/N}.$$

Note that the only differences between the forward and inverse transforms are (i) changing the sign in the exponential, and (ii) dividing the answer by N.

So far, we are considering n to vary from -N/2 to N/2 as k varies from 0 to N-1. However, our equation for the DFT is periodic in n with period N, that is,

$$e^{-2 \pi i k \frac{1}{N}} = e^{-2 \pi i k \frac{N+1}{N}}.$$

Thus, if we let n vary from 0 to N-1 (which is a complete period) we will cover all the frequencies and n will vary in exact correspondence to k. Thus

• n = 0 corresponds to the zero frequency component,
• $1 \leq n \leq \frac{N}{2} - 1$ corresponds to the frequencies $0 < \omega < \omega_c$,
• $\frac{N}{2} + 1 \leq n \leq N-1$ corresponds to the frequencies $- \omega_c < \omega < 0$, and
• n = N/2 corresponds to both $-\omega_c$ and $\omega_c$.

All standard implementations of the FFT produce data in this form.

The DFT needs N complex multiplications of f_k by $e^{-2 \pi ikn/N}$ and N-1 additions of the resulting values to transform N values; its complexity is thus proportional to N², thus justifying its nickname of the Slow Fourier Transform.

The Fast Fourier Transform (FFT) is an ingenious algorithm which exploits various properties of the Fourier transform to enable the transformation to be done in O(N log₂ N) operations. However, the FFT requires the size of the input data to be a power of 2; if this is not the case, the data are either truncated or padded out with zeros.