Fundamentals of Digital Image Processing - Control of Color Imaging Systems: Analysis and Design - page 47

signal can be expanded into sine and cosine using the continuous Fourier transform.
The DFT of an N M discrete signal f ( n, m ) is de ned as

X X

M 1 N 1

f ( n, m ) e j 2 N nk e j 2 M ml

F ( k, l ) ¼ ( 2 : 59 )

m ¼ 0 n ¼ 0

For k ¼ 0, 1, 2, ... , N 1, and l ¼ 0, 1, 2, ... , M 1. The DFT coef cients are

2 N k and 2 M l. They are gener-

samples of F (v x , v y ) uniformly spaced at v x ¼ v y ¼

ally complex valued and can be used to expand f ( n, m ) in terms of 2-D complex

exponential signals (basis functions). This expansion is called the inverse DFT and is
given by

M 1

X

N 1

X

1
MN

F ( k, l ) e j 2 N nk e j 2 M ml

f ( n, m ) ¼ ( 2 : 60 )

l ¼ 0 k ¼ 0

N f x

k

The discrete frequency indices k and l correspond to the analog frequencies and

N f y , where f x and f y are the sampling frequencies in the x-andy-directions,
respectively. The complexity of DFT computation is measured in terms of the
number of multiplications required in implementing Equation 2.59. Assuming
that N ¼ M, the number of complex multiplications needed to compute one sample
of F ( k, l )

k

is N 2 . Since there are N 2 DFT samples to be computed, the total number
of multiplications is N 4 . We refer to this as direct computation. We can compute 2-D
DFT more ef ciently by using the fact that the basis functions involved in DFT

expansion are separable. As a result of this, we can compute the 2-D DFT by taking
the 1-D DFT of each row of the image and then taking the 1-D DFT of the columns
of the intermediate image G ( n, l ) , as shown in Figure 2.21.

1-D N -Point
DFT

G ( n, l )

f ( n, m )

1-D N -Point
DFT

F ( k, l )

FIGURE 2.21 Row column decomposition.

-