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 , generating
a sequence of sampled values
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.
![]() |
We generate the Fourier transform at discrete frequencies
We now approximate the integral equation for the Fourier transform by a discrete summation:
Typically, the sampling distance is set to 1, so the
discrete Fourier transform is given by
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,
The DFT needs N complex multiplications of fk by and N-1 additions of the resulting values to transform N
values; its complexity is thus proportional to N2, 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 log2 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.