Last updated on October 16, 1995 at 9:50 PM.
Suppose that we have a continuous function 
with Fourier Transform 
that we want to sample into a discrete function 
(Fourier Transform 
)
with uniform spacing h.
This is equivalent to multiplying the function by a comb with spacing h:
According to the Convolution Theorem, this is equivalent to convolving
with the Fourier Transform of the sampling comb,
a comb in the frequency domain with spacing 
:
This means that the discrete sampling causes the Fourier Transform of
original function to be duplicated over and over again with spacing 
.
If the Fourier Transform of the original function is bandlimited to the
range 
, these duplicated copies don't overlap and we can
completely reconstruct the original function by selecting one of the
copies and taking its inverse transform.
If the the Fourier Transform does have frequencies greater than
, the duplicate copies overlap and add together.
The information in the signal is lost and cannot be recovered.
This is called aliasing and happens whenever a function is undersampled.
In order to avoid aliasing, the highest frequency component 
of the
original function must be less than half the inverse of the sampling rate 
:
If we know the highest frequency 
, we can determine the
minumum sampling rate:
In other words, we must sample a signal at twice its highest frequency in
order to avoid aliasing.
This is called the Nyquist Rate of the signal.
In digital images, each pixel is a discrete sample of the original scene. In order to avoid aliasing in the image, we must sample the scene at twice the highest spatial frequency in the scene.
Because it involves undersampling, aliasing manifests itself through high-frequency components masquerading as low-frequency ones. (If you ever listen to an audio signal that has been undersampled, listen for the low-frequency tones that should be there-that's the aliasing.)
In images, it appears as low-frequency patterns scattered throughout the image. These patterns are called Moiré patterns, and can be seen in the following images.
 |
 |
 |
 |
Have you ever seen someone on TV wearing a striped shirt or suit with very tight spacing and noticed a strange pattern that seems to dance around on the shirt or suit? That's a Moiré pattern. No one on TV should ever wear tightly-striped shirts or herring-bone suits (at least until we get HDTV and the sampling rate increases).
Aliasing is a well-known problem in computer graphics when trying to paint a thin line or edge on a set of discrete pixels. In this case, the aliasing causes a specific pattern manifest as the jagged edge that follows the pixel grid and is called ``jaggies''. Jaggies and aliasing are one and the same-not enough spatial samples to adequately represent the data. Not surprisingly, most attempts in computer graphics to reduce the jaggies involve image-processing techniques for reducing aliasing. Such techniques are called antialiasing, and (time permitting) we will cover them later in the course.
the Discrete Fourier Transform can be written as
If N is a multiple of 2,
for some positive number M.
Substituting 2M for N gives
Separating out the M odd terms and the M even terms,
Since
and
,
Notice that this is the Fourier Transform of the even terms
(we'll call it 
)
plus a constant 
times the Fourier Transform of the odd terms
(we'll call it 
).
Simplified, this means that the first M terms of the Fourier Transform of 2M
items can be computed by
Similarly, the last M terms can be computed by
This means that an N-point transform can be computed by separating the
odd and even elements of the original function, computing their
individual 
element DFTs, and then combining them using
Eqs. 8.11-8.12.
If N is a power of two, we can repeat this process recursively.
Eventually, we get down to two one-point transforms, each of which is its own transform.
We combine these, recombine the results, recombine those results, etc.
until we have the complete transform.
This divide-and-conquer
Fast Fourier Transform (FFT)
algorithm takes 
operations, as compared
to 
for the Discrete Fourier Transform.
You should realize that the Fast Fourier Transform is nothing but an algorithm for computing the Discrete Fourier Transform in a faster way. It is not anything different. A lot of people say they ``compute the FFT of an image'', but doing so is like saying they ``quicksort some data''. One sorts data--quicksort is one algorithm for doing it. Likewise one computes Discrete Fourier Transforms--the FFT is one algorithm for doing it.
Also keep in mind that the FFT only works when N is a power of two. When N isn't a power of two, one can usually pad the data to make it so.
|
In-class exercise/question:
|
image with another, it takes 
operations.
If you compute the DFT of the image using the direct algorithm,
you can use the separability of the Fourier Transform to
compute the DFT of the N rows (
operations each)
and then replace the rows with their respective DFTs and
compute the DFTs of the N columns (again, 
operations each).
The total number of operations is thus 
).
If you use the same algorithm as above but replace the one-dimensional
DFTs with the FFT algorithm, the total operations is 
.
One can thus take advantage of the Convolution Theorem to compute the convolution of two functions by
operations instead of
--a significant savings.
However, order of complexity only tells half the story--it describes how the complexity grows with the data size, but it doesn't include the precise number of operations per item. For algorithms with low complexity, it is common to find that higher-complexity algorithms actually perform better with smaller data sizes but are soon outpaced by the lower-complexity algorithm. There is usually a break-even point beyond which the lower-complexity algorithm becomes more efficient.
For convolutions, this break-even point is about 
.
That is, for convolution kernels that are 
or smaller it's
usually more efficient to use the direct convolution algorithm.
For kernels that are 
or larger, it's usually more efficient
to convert things to the frequency domain and back.
© Bryan S. Morse, 1995