Image Processing Reference
In-Depth Information
y(1, 2)
¼ x(1, 2)
þx(1, 1)
þx(0, 2)
þx(0, 1)
¼
0
þ
3
þ
0
þ
1
¼
4
y(2, 0)
¼ x(2, 0)
þx(2,
1)
þx(1, 0)
þx(1,
1)
¼
0
þ
0
1
þ
0
¼
1
y(2, 1)
¼ x(2, 1)
þx(2, 0)
þx(1, 1)
þx(1, 0)
¼
0
þ
0
þ
3
1
¼
2
y(2, 2)
¼ x(2, 2)
þx(2, 1)
þx(1, 2)
þx(1, 1)
¼
0
þ
0
þ
0
þ
3
¼
3
Hence
2
4
3
5
231
154
y(n, m)
¼ x(n, m)
*
h(n, m)
¼
123
So, in general, to perform fast convolution, one would be interested in computing
linear convolution via DFT. As will be shown, the FFT can be employed for this
purpose provided that the data is properly formatted to avoid circular convolution.
Suppose that signal f (n, m)isMM and the
lter h(n, m)isLL and we would like
to compute g(n, m), the linear convolution of f (n, m) and h(n, m) using DFT.
a. Choose N the DFT size to be N MþL
1
b. De
ne NN arrays
f (n, m) 0
n, m M
1
f (n, m)
¼
(2
:
66)
0
otherwise
h(n, m) 0
n, m L
1
h(n, m)
¼
(2
:
67)
0
otherwise
c. Compute
IDFT{DFT[f (n, m)]DFT[h(n, m)]}
g(n, m)
¼
(2
:
68)
d. Find
g(n, m)
¼ g(n, m)0
n, m MþL
1
(2
:
69)
Example 2.9
Convolve the following 2-D sequences using DFT,
2
4
3
5
124
232
314
13
21
f (n, m)
¼
and h(n, m)
¼
S
OLUTION
a. Choose DFT size to be N
3
þ
2
1
¼
4 and let N ¼
4.
b. Zero-pad the signal
f (n, m) and compute its DFT
Search WWH ::
Custom Search