Digital Image Processing Topics - Computer Graphics and Geometric Modeling - page 781

There are discrete versions of the Fourier transform and its inverse. We give the
one-dimensional version as an example.

Definition. If f(k) and G(u) are functions defined on the integers, then

N -

Â

1

1 - 2 p i uk

Ê
Ë

ˆ
¯

() = () Fu fk exp , where 0 ££ - u N 1 ,

N N

k = 0

is called the discrete Fourier transform of f and

N -

 0

1

2 p i uk

N

Ê
Ë

ˆ
¯

() = () gk Gu exp , where 0 ££ - k N 1 ,

k =

is called the discrete inverse Fourier transform of G .

The Fourier transform is computationally very expensive to implement. Therefore,
it was quite a breakthrough when an efficient way to implement it, called the Fast
Fourier Transform (FFT), was published in 1965 in the paper [CooT65]. Thanks to the
FFT, many signal processing algorithms are now practical.
A real nice interpretation of the discrete Fourier transform can be found in
[Glas99]. It can be thought of as expressing an arbitrary polygon as a sum of basic
regular polygons.

21.7 Convolution

Definition. Given two functions f, g: R Æ R , define their convolution , f*g , by

•

Ú

( )( ) = () ( ) fgx * ftgx tdt - .

-•

We give some conditions for when the convolution exists.

21.7.1 Theorem. If f, g: R Æ R , then the convolution integral

•

Ú

() ( )

ftgx tdt -

-•

converges absolutely for all x under either of the following two conditions:

(1) The function f is absolutely integrable and g is bounded.
(2) Both f and g are absolutely integrable and both belong to L 2 ( R ).

If both f and g are also continuous, then the convolution integral is also continuous
under either condition (1) or (2).

Proof. See [Seel66] or [Apos58].

21.7.2 Example. Figure 21.8 shows the convolution of the two functions