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

Example 2.10

Compute g(n, m) ¼ f (n, m) * h(n, m) using a 4-point FFT, where

2
4

3
5

19 16 19 3 9 17 6 8
59 84 904 7
12 12 8 4 9 14 4 17

10 16 18 12 8 8 14 12 11

11

f (n, m) ¼ and h(n, m) ¼

18 18 1 5 17 17 6 10

15 15 7 4 11 10 11 18

9 4 16 0 4 14 3 16

0 8 0 15 13 9 14 13

S OLUTION
First we find the block size B

B ¼ NLþ 1 ¼ 4 2 þ 1 ¼ 3

Now, divide the image into B 2 ¼ 9 blocks

2
4

3
5 ,

2
4

3
5 ,

2
4

3
5

19 16 19
59 8
12 12

39 7
4190
49 4

680
4170
4170

f 1 (n, m) ¼ f 2 (n, m) ¼ f 3 (n, m) ¼

8

2
4

3
5 ,

2
4

3
5 ,

2
4

3
5

10 16 18
18 18

12 8 8
5 7 7
4 1 0

14 12 0
6 00
11 18 0

f 4 (n,m) ¼ 1 f 5 (n,m) ¼ f 6 (n,m) ¼

15 15 7

2
4

3
5 ,

2
4

3
5 ,

2
4

3
5

9416
080
000

04 4
15 13 9
000

3 60
14 13 0
000

f 7 (n, m) ¼ f 8 (n, m) ¼ f 9 (n, m) ¼

Next, we convolve each block with h(n, m) using FFT and inverse FFT, that is, for
i ¼

1, 2, ... , 9, we compute

¼ IFFT{FFT[f i (n, m)]FFT[h(n, m)]}

g i (n, m)

where:

2
4

3
5

2
4

3
5

0
f i (n, m) 0
0
0000

1100
1100
0000
0000

f i (n, m) h i (n, m)

¼ and ¼

All FFTs and IFFTs are 4 4 and are computed using row column decomposition.

-

The results are