Image Processing Reference
In-Depth Information
is clearly a large penalty and so a direct digital implementation of template matching is
slow. Accordingly, this guarantees interest in techniques that can deliver the same result,
but faster, such as using a Fourier implementation based on fast transform calculus.
5.3.2
Fourier transform implementation
We can implement template matching via the Fourier transform by using the
duality
between convolution and multiplication. This duality establishes that a multiplication in
the space domain corresponds to a convolution in the frequency domain and vice versa.
This can be exploited for faster computation by using the frequency domain, given the fast
Fourier transform algorithm. Thus, in order to find a shape we can compute the cross-
correlation as a multiplication in the frequency domain. However, the matching process in
Equation 5.11 is actually
correlation
(Section 2.3),
not
convolution. Thus, we need to
express the correlation in terms of a convolution. This can be done as follows. First, we
can rewrite the
correlation
in Equation 5.11 as
xy W
IT
=
I T
(5.17)
xy
,
x iy j
- ,
-
(,
)
where
x
=
x
+
i
and
y
=
y
+
j
.
Convolution
is defined as
xy W
IT
=
I
T
(5.18)
xy
,
ixjy
-
, -
(,
)
Thus, in order to implement template matching in the frequency domain, we need to
express Equation 5.17 in terms of Equation 5.18. This can be achieved by considering that
xy W
ITIT
=
=
I T
(5.19)
xy
,
ixjy
-
, -
(,
)
where
T
′ =
T
-
x,
-
y
(5.20)
That is, correlation is equivalent to convolution when the template is changed according to
Equation 5.20. This equation reverses the co-ordinate axes and it corresponds to a horizontal
and a vertical flip.
In the frequency domain, convolution corresponds to
multiplication
.
As such, we have
that Equation 5.19 can be implemented by
I
*
T
′ =
F
-1
(
F
(
I
)
F
(
T
′ )) (5.21)
where
F
denotes Fourier transformation as in Chapter 2 (and calculated by the FFT) and
F
-1
denotes the inverse FFT. This can be computationally faster than its direct implementation,
given the speed advantage of the FFT. There are two ways of implementing this equation.
In the first approach, we can compute
T
′ by flipping the template and then computing its
Fourier transform
F
(
T
′ ). In the second approach, we compute the transform of
F
(
T
) and
then we compute the complex
conjugate
. That is,
F
(
T
′ ) = [
F
(
T
)]* (5.22)
where [ ]* denotes the complex conjugate of the transform data (yes, we agree it's an
unfortunate symbol clash with convolution, but both are standard symbols). So conjugation
of the transform of the template implies that the product of the two transforms leads to
correlation. That is,
