Image Processing Reference
In-Depth Information
Consider a gray scale image of size 512
512 pixels. We wish to sharpen the
image by processing it with a FIR high-pass
filter of size 11
11. For simplicity,
let
filter as it can be equally taken
advantage of in both direct convolution and FFT-based convolution. Determine
which approach will be faster, block convolution using overlap
s ignore any symmetrical properties of the
'
add method with
-
64-point FFT or direct convolution in spatial domain?
S
OLUTION
The speed of any digital signal processing algorithm depends on the number of
multiplications and additions performed. Since multiplication takes more time
than addition, we ignore addition and compute the number of multiplications.
Generally speaking, algorithm A will be faster than algorithm B if the number of
multiplications in A is less than B.
Let N
1
be the total number of real multiplications when the convolution is
performed in spatial domain and N
2
be the total number of real multiplications
when the overlap
add method is used with a 64-point FFT and inverse FFT.
Assume that the 2-D FFT is computed using row
-
column decomposition. Then,
-
512
2
pixels
11
2
multiplication
10
6
N
1
¼
=
pixel
¼
31, 719, 424
¼
31
:
719424
Each 2-D FFT requires
64
2
2
log
2
(64
2
)
¼
24, 576 complex multiplications. The size of
each block is (64
11
þ
1)
(64
11
þ
1)
¼
54
54 and the number of blocks is
54
2
100. Therefore, 100 FFTs are needed to transform the blocks, 1 FFT to
transform the
512
filter, 100
64
64
¼
409, 600 complex multiplications to multiply
the transform coef
cients, and 100 FFTs to come back to the pixel domain. This is
equal to a total of 201 FFTs and 409,600 complex multiplications. Therefore,
N
2
¼
201
24, 576
þ
409, 600
¼
5, 349, 376 complex multiplications
Now each complex multiplication is equal to three real multiplications using the
following algorithm
one multiplication
one multiplication
acbd ¼
a(cd)
þ d(ab)
Two multiplications
one multiplication
ad þbc ¼ d(ab)
þ
b(d þc)
One additional multiplication
Note that the term d(ab) is computed once.
Then,
(aþ jb)(cþ jd)
¼ acbd þ j(ad þbc)
Therefore,
N
2
N
1
¼
3
5, 349, 376
31, 719, 424
¼
0
:
507
This implies that, in this case, the frequency domain convolution is almost twice
faster than the spatial domain convolution.
Search WWH ::
Custom Search