PRECISION OF IMAGE MATCHING
J.C. TRINDER, K. BECEK AND B.E. DONNELLY
School of Surveying
University of N.S.W.
P.O. Box 1, Kensington, NSW 2033 Australia
Abstract
A simulation study of the precision of image matching based on the least squares and cross-correlation methods is being carried out
on a variety of simulated images of typical objects on digitized photographs or satellite data. The tests in this paper will demonstrate
the precision of image matching by both methods, and also the factors which influence the precision such as the amount of detail in
the image, the size of the detail, the image quality, image geometry and quantization level. As the method is based on simulated
images with known positions of the centres of both image windows, a reliable estimate of the precision of the matching is possible.
Key Words: Image Matching, Image Processing, Algorithmic.
1. Introduction
Developments of software for machine vision applications of
photogrammetry based on digital images have been under way
in the School of Surveying for some time, (Trinder et al
1990). The technology is designed for medicine and quality
control for manufacturing. The precisions of image matching
achieved with tests of these developments to date have been of
the order of 0.2 to 0.3 pixel. In addition, a check on the
accuracies of the geometry of the object using analogue images
observed in an analytical stereoplotter, indicated accuracies of
the order of Imm to 2mm, depending on the camera geometry,
for a camera to object distance of 1.8m. While these precisions
are typical of those obtained by many researchers, it became
necessary to investigate the precision of image matching that
can be achieved with the method and the factors such as image
content and quality which influence them, to determine if
improvements in the results are achievable. It is noted that the
precisions of template matching to well defined targets by
Beyer (1992) are of the order of 0.02 pixel. The results of the
study of the precision of image matching are described in this
paper.
In an earlier study, investigations were carried out on the
precision of target location on simulated digital images, based
on the computation of the target centroid, as a function of
image quality variables such as target size, extent of blur in the
image, pixel size, quantization level, and noise (Trinder,
1989). This paper extends this study to investigations of the
accuracy of image matching, based on the method of least
squares (Foerstner 1982) of a range of simulated digital
images, subject to the same variables as those above, together
with variables such as displacements, scale changes and
rotations between the two images.
2. Creation of Image Windows
The images generated in this study are designed to represent
typical features in photographic or satellite images over which
image matching may be undertaken. Therefore features that
can be generated by the software involve a range of shapes
such as circles, crosses, crosses with additional blobs, t-
junctions, v-junctions and grids. Each feature is described by a
grid of sample points, typically 64 by 64 points or 128 by
128. The features are then subjected to image blur by
convolution by FFT of the feature with a Gaussian spread
function with 26 widths ranging from 10 to 50pm, which are
typical of those which occur for standard aerial photography or
satellite images. A spread function of 26 value of 0 um is also
possible for testing images when no blur is present in the
image. The next step is to digitize the feature with pixel sizes
ranging from 10um to 50um. This process has been described
previously (Trinder 1989). The intensity of each pixel is a
function of the volume of the solid contained by the
intersection of the surface, representing the intensity
distribution of the feature in the x and y directions, and the
column representing the pixel. This volume is derived by
820
interpolating sufficient values within the area of each pixel,
from the surface representing the intensity of the feature, to
give adequate precision. During the digitisation process, 8
quantization levels can be selected, resulting in digital data of
28, 27, 26, 25, 24, 23, 22,21 grey values which means
encoding into 8, 7, ...1 bits, respectively. Noise can be
introduced into the digitized data prior to quantization. The
size of the feature in relation to the pixel size determines the
size of the image window, which is therefore a dependent
variable in this study.
The process of image matching clearly requires two separate
images to be generated. The first image, coded as the left hand
image, was derived according to the description above, while
the dimensions and orientation, where appropriate, of the
second or right image were varied from those of the left image
to simulate changes in scale and rotations between the two
images. This enabled tests to be carried out on the effects of
geometric distortions in the features in the two windows on the
efficiency of the image matching. The digitisation process of
the right window is repeated a number of times to simulate the
circumstance in practice where the position of the initial pixel
with respect to the location of the feature may vary randomly.
This is applied in the horizontal direction only (i.e. x-direction)
by displacing the commencing pixel in the range of + 1 pixel
from the initial position on the feature by a random generator.
Obviously, since the features have been computer generated,
the exact locations of the centres of the features are known.
In summary, the following parameters can be varied in this
study on the accuracies of image matching:-
* feature characteristics of shape, size, image quality
and noise,
* pixel size used for digitizing, and therefore window
size, and commencing position of the digitizing,
* quantization level,
* feature position, scale and orientation.
3. Image Matching
Image matching has been carried out by both the least squares
and cross-correlation methods. The tests have involved the
computation of the matching of the right image to the left
image, commencing with the initial assumption that the correct
matching position of the right window is indeed the centre of
the window. Displacements, scale changes and rotations of the
feature in the right window with respect to the feature in the
left window can be selected by data input. It follows that the
correct position of matching will be subject to these
displacements, scale changes and rotations, and the matching
procedure should therefore reveal the effects of these
parameters. Tests will determine the maximum values of these
parameters which can be accommodated in the matching
process. Since the commencing position of the digitization
PRECISION OF MATCHING - RMS (pixel x 1000)
