Feature extraction by shape matching - Feature Extraction and Image Processing - page 171

I ∗ T ′ = F -1 ( F ( I ) [ F ( T )]*) (5.23)
For both implementations, Equations 5.21 and 5.23 will evaluate the match and, more
quickly for large templates than by direct implementation of template matching. Note that
one assumption is that the transforms are of the same size, even though the template's
shape is usually much smaller than the image. There is actually a selection of approaches;
a simple solution is to include extra zero values ( zero-padding ) to make the image of the
template the same size as the image.
The code to implement template matching by Fourier, FTConv , is given in Code 5.2 .
The implementation takes the image and the flipped template. The template is zero-padded
and then transforms are evaluated. The required convolution is obtained by multiplying the
transforms and then applying the inverse. The resulting image is the magnitude of the
inverse transform. This could naturally be invoked as a single function, rather than as
procedure, but the implementation is less clear. This process can be formulated using
brightness or edge data, as appropriate. Should we seek scale invariance, to find the
position of a template irrespective of its size, then we need to formulate a set of templates
that range in size between the maximum expected variation. Each of the templates of
differing size is then matched by frequency domain multiplication. The maximum frequency
domain value, for all sizes of template, indicates the position of the template and, naturally,
gives a value for its size. This can of course be a rather lengthy procedure when the
template ranges considerably in size.

%Fourier Transform Convolution

function FTConv(inputimage,template)

%image size
[rows,columns]=size(inputimage);

%FT
Fimage=fft2(inputimage,rows,columns);
Ftemplate=fft2(template,rows,columns);

%Convolution
G=Fimage.*Ftemplate;

%Modulus
Z=log(abs(fftshift(G)));

%Inverse
R=real(ifft2(G));

Code 5.2 Implementing convolution by the frequency domain

Figure 5.5 illustrates the results of template matching in the Fourier domain. This
example uses the image and template shown in Figure 5.2. Figure 5.5 (a) shows the flipped
and padded template. The Fourier transforms of the image and of the flipped template are
given in Figures 5.5 (b) and 5.5 (c), respectively. These transforms are multiplied, point by