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

TABLE 2.1
Direct 2-D DFT=FFT Comparison
Technique

No. of Complex Multiplications %

Direct computation N 4 ¼ 7 : 871947 10 10 100

Row column decomposition

(1-D DFT)

2N 3 ¼ 2 : 73154048 10 8 0.4

-

N 2 log 2 ( N ) ¼ 2 : 359296 10 6 Row - column decomposition

(1-D FFT)

0.0035

column
decomposition, we need to compute 2N 1-D DFTs and each 1-D DFT requires N 2
multiplications. Therefore, the total number of complex multiplications needed is
2N N 2

This is called the row column decomposition technique. With row

- -

¼

2N 3 . Now, if we use row column decomposition with fast Fourier

transform (FFT) algorithm, the total number of multiplications will be reduced to
2N

-

2

log 2 ( N ) ¼ N 2 log 2 ( N )

. This is due to the fact that the total number of
multiplications necessary to compute N-point FFT is 2 . To see the compu-

tational advantage of using FFT for 2-D DFT computation, consider calculating the
2-D DFT of a 512

log 2 ( N )

512 image using direct computation, row column decompos-

-

ition and row column decomposition with the FFT algorithm replacing direct DFT

computation. The comparison is shown in Table 2.1.

-

Properties of 2-D DFT
The properties of 2-D DFT are listed below. The proofs are left as an exercise.

2 - D DFT

2 - D DFT F 2 ( k, l )

! !

a. Linearity property:Iff 1 ( n, m ) F 1 ( k, l ) and f 2 ( n, m ) ,

then

2 - D DFT

!

af 1 ( n, m ) þ bf 2 ( n, m ) aF 1 ( k, l ) þ bF 2 ( k, l ) ( 2 : 61 )

b. Conjugation property:Iff ( n, m ) is a real sequence, then its DFT F ( k, l )

satis es the following conjugation property

F ( k, l ) ¼ F* ( N k, M l ) ( 2 : 62 )

This means that half of the DFT data is redundant data.

2 - D DFT F ( k, l ) 2 - D DFT F (v

! !

c. Rotation property: ff ( n, m ) or f ( r, u) , w)

where

n ¼ r cos u , m ¼ r sin u , k ¼ v cos w , l ¼ v sin w