1.2.11 Discrete Fourier Transform
INPUT OUTPUT
Input Description:
A sequence of n real or complex values h_i, 0 \leq i \leq n-1, sampled
at uniform intervals from a function h.
Problem:
The discrete Fourier transform H of h,
H_m = \sum_{k=0}^{n-1} h_k e^{2 \pi i k m / n}, 0 \leq m \leq n-1.
Excerpt from
The Algorithm Design Manual:
Although computer scientists tend to be relatively unfamiliar with Fourier transforms, electrical engineers
and signal processors eat them for breakfast. Functionally, Fourier transforms provide a way to convert
samples of a standard time-series into the ``frequency domain''. This provides a ``dual'' representation of
the function, in which certain operations become easier than in the time domain. Applications of Fourier
transforms include:
- Filtering: -- Taking the Fourier transform of a function is equivalent to representing it as
the sum of sine functions. By eliminating undesirable high- and/or low-frequency components (i.e. dropping
some of the sine functions) and taking an inverse Fourier transform to get us back into the time domain, we can
filter an image to remove noise and other artifacts. For example, the sharp spike in the figure above
describes the period of a single sine function that closely models the input data.
- Image Compression -- A smoothed, filtered image contains less information than a noisy image,
while retaining a similar appearance. Thus encoding the smoothed image will require fewer bits to represent
than the original image. By eliminating the coefficients of sine functions that contribute relatively little
to the image, we can further reduce the size of the image, at little cost in image fidelity.
- Convolution and Deconvolution -- Fourier transforms can be used to efficiently compute convolutions of two sequences.
A convolution is the pairwise product of elements from two different sequences, such as in multiplying two
n-variable polynomials f and g or multiplying two long integers. Implementing the
product directly takes O(n2), while O(n \lg n)
suffices using the fast Fourier transform.
Another example comes from image processing.
\index{scanner, OCR}
Because a scanner measures the darkness of an image patch instead of a single point,
the scanned input is always blurred.
A reconstruction of the original signal can be obtained by deconvoluting the
input signal with a Gaussian point-spread function.
Recommended Books
Related Problems
This page last modified on 2008-07-10
.
www.algorist.com
Algorithms in Java, Third Edition (Parts 1-4)
A Primer on Wavelets and Their Scientific Applications
The Fourier Transform and its Applications
Numerical Recipes in C
The Fast Fourier Transform and Its Applications
