Next: The Imaging Process
Up: Introduction
Previous: The software environment
Template matching is the generic name for a set of techniques that
quantify the similarity of two digital images, or portion thereof, in
order to establish whether they are the same or not. Digital images
are commonly represented with numerical arrays: monochrome images
require a single matrix while color images require multiple matrices,
one per color component. We will restrict our attention to monochrome
images. Digital images can be stored in various formats such as jpeg, tiff, or ppm. A variant of the latter, specific
to grey level images, is commonly identified with a .pgm suffix.
Package AnImAl provides convenient functions to read them:
2#2
Note the darker region: it identifies R output. The coordinate system
most often associated to an image is left-handed: the value of the 3#3
coordinate increases from left to right while that of the 4#4
coordinate increases from top to bottom (see
Figure 2.1). This is due to images being stored as
arrays and to the fact that the 4#4 coordinate is associated to the
row number. R provides extensive graphical facilities and function
tm.ploteps can be used to turn their output to postscript
files:
5#5
Setting tm.plot.defaultFormat <- "X11" (uncommenting line 1
above) makes subsequent calls to tm.plot use the windowing
system. We will routinely use tm.plot to produce the images
inserted in this manual.
Figure 1.1:
A sample monochrome image with its left-handed coordinate
system.
[width=10cm]figures/sampleImage.jpg |
The existence of an image coordinate system allows us to specify in a
compact way rectangular regions: we simply need to provide the
coordinates 6#6 of its upper left corner and the horizontal
and vertical dimensions
7#7:
8#8
The result, reported in Figure 1.2, is a new, smaller image
that carries on the knowledge of its original placement as the axes
values show.
Figure:
A detail of Figure 2.1: let us note that
the coordinates in the original image are preserved.
[width=10cm]figures/sampleEye.jpg |
As clarified in Figure TM1.2, the search for a template, such as the
one presented in Figure 1.2, within an image, such as
the one in Figure 2.1, is performed by scanning the
whole image, extracting at each image position a region of interest
whose size corresponds to that of the template:
9#9
Function ia.show in line 4 of the above code snippet would show
image portion w in a window. However, what we need to do is to
compare each image w to the reference template eye1
assessing their similarity. We should also store the resulting values
in a map so that we can access them freely after the computation is
completed.
Codelet 1 Basic template matching (./R/tm.basicTemplateMatching.R)
-2
- This function illustrates the most basic template matching technique:
the template is moved over each image position and the sum of the squared
difference of aligned image and template pixels is considered an indicator
of template dissimilarity.
10#10
The first step is to get the linear dimensions
of the template
11#11
We then determine the extent of the image region
of interest over which we need to slide our template
12#12
This allows us to prepare the storage for the similarity scores
13#13
and to perform the actual computation loop,
14#14
sliding along each row
and extracting in turn an image portion
matching the size of the template
15#15
We modify the template so that it overlaps
the extracted region
16#16
and compute (and store) the matching score
17#17
We can finally return the image representing the similarity
map
18#18
It is now easy to spot our template in the image:
19#19
Note that the position of the template differs from that of the
original eye1 as we down-sampled the image: the coordinates are
halved. We can also have a look at the resulting matrices to get an
idea of how extremal the matching value at the correct position is:
this is related to the concept of signal to noise ratio that we will
consider in depth in later chapters.
20#20
Figure 1.3:
The distance map (left) and the similarity map (right) corresponding to the matching of template eye1 to face1.
[width=8cm]figures/distanceMatch.jpg
[width=8cm]figures/similarityMatch.jpg
|
AnImAl provides ia.correlation, a faster and more flexible
function to perform the task that will be considered in
Chapter 3. Changing the value
0.001 used in the computation of simScores
significantly affects the distribution of values:
21#21
The resulting distributions are reported in Figure 1.4.
Figure 1.4:
The distributions of similarity scores obtained varying the
denominator constant, 0.001, 0.01, 0.1
respectively from left to right. The highest similarity value
determines the x range: the lower the value used in the
normalization, the higher the dynamic range exhibited by the
scores and the more far apart the value corresponding to the
correct position from the remaining ones.
[width=5.5cm]figures/scoresHistA.jpg
[width=5.5cm]figures/scoresHistB.jpg
[width=5.5cm]figures/scoresHistC.jpg
|
Next: The Imaging Process
Up: Introduction
Previous: The software environment
Roberto Brunelli
2008-11-25