Basic image processing operations - Feature Extraction and Image Processing - page 84

Since smoothing was earlier achieved by low-pass filtering the Fourier transform (Section
2.8), the Fourier transform actually gives an alternative method to implement template
convolution. In Fourier transforms, the dual process to convolution is multiplication (as in
Section 2.3). So template convolution can be implemented by multiplying the Fourier
transform of the template with the Fourier transform of the picture to which the template
is to be applied. The result needs to be inverse transformed to return to the picture domain.
The transform of the template and the picture need to be the same size. Accordingly, the
image containing the template is zero-padded prior to its transform. The process is illustrated
in Code 3.8 and starts by calculation of the transform of the zero-padded template. The
convolution routine then multiplies the transform of the template by the transform of the
picture point by point (using the vectorize operator). When the routine is invoked, it is
supplied with a transformed picture. The resulting transform is re-ordered prior to inverse
transformation, to ensure that the image is presented correctly. (Theoretical study of this
process is presented in Section 5.3.2 where we show how the same process can be used to
find shapes in images.)

conv(pic,temp):= pic - spectrum ←

Fourier(pic)

temp - spectrum ← Fourier(temp)

→

convolved - spectrum ←

(pic - spectrum.temp - spectrum)

result ← inv - Fourier(rearrange(convolved - spectrum))

result

new - smooth :=conv(p, square)

Code 3.8 Template convolution by the Fourier transform

Code 3.8 is simply a different implementation of direct averaging. It achieves the same
result, but by transform domain calculus. It can be faster to use the transform rather than
the direct implementation. The computational cost of a 2D FFT is of the order of N 2 log( N ).
If the transform of the template is precomputed, there are two transforms required and
there is one multiplication for each of the N 2 transformed points. The total cost of the
Fourier implementation of template convolution is then of the order of
C FFT = 4 N 2 log( N ) + N 2 (3.18)

The cost of the direct implementation for an m × m template is then m 2 multiplications for
each image point, so the cost of the direct implementation is of the order of
C dir = N 2 m 2 (3.19)

For C dir < C FFT , we require:
N 2 m 2 < 4 N 2 log( N ) + N 2 (3.20)

If the direct implementation of template matching is faster than its Fourier implementation,
we need to choose m so that
m 2 < 4 log( N ) + 1 (3.21)

This implies that, for a 256 × 256 image, a direct implementation is fastest for 3 × 3 and