LEAST SQUARES MATCHING BY SEARCH
Tapani Sarjakoski and Jussi Lammi
ESPA Systems Ltd.
Tekniikantie 12, FIN-02150 Espoo
Finland
ISPRS Working Group III/2
KEY WORDS: Digital Aerial Imagery, Least Squares Matching, Line Matching, Area Matching, Search Techniques
ABSTRACT
The paper studies a method for solving the least squares matching by search. The basic principle of the method is
straightforward: 1) the object function (the minimum sum of squared residuals) is expressed in terms of original, non-
linearized equations, 2) search space is defined in terms of unknown parameters and 3) the object function is solved by
means of numerical analysis using search.
The paper begins with a general formulation of the least squares object function in terms of object-space gray
value matching and non-linear observation equations. Bilinear interpolation of the gray level values is used as a method
for achieving subpixel accuracy. A search method based on a predetermined search space and complete search is
described in its generic form. Usage of hierarchical search methods and case-dependent knowledge are introduced for
making the search efficient. Supersampling of gray level values with bilinear interpolation is used as a preprocessing
procedure for making the computations simple in the innermost loop.
The method as such is independent of the application area. The treatment taken in this paper is based on cases
where aerial images are used. The case-dependent heuristic search methods are introduced for image to multi-image
matching when the image orientations are known either precisely or approximately. The cases for height determination
and template matching for signalized points in aerial triangulation are also covered. It is shown that the effect due to the
terrain tilt can be handled rigorously using only two parameters. This is essential for keeping the size of the search
space as small as possible.
It is concluded that the applicability of the least squares matching by search is as wide as the applicability of
least squares matching in general, ranging from aerial triangulation to digital elevation computation. It clearly has the
benefit of being less sensitive of approximate values. Its straightforward formulation yields a straightforward
implementation. It is also straightforward to implement other optimality criteria, like the use of L,-norm. Its computation
cost is tolerable in practice, even when used as a part of interactive measurement methods. In addition, the search-
based method is directly suitable for multithreaded programming techniques to utilize multiprocessor workstations in a
highly efficient way.
subpixel accuracy. Although the field of numerical
analysis identifies several methods for solving systems
of non-linear equations by iteration or search, the
techniques used in this study are mainly originated from
heuristic search techniques used in artificial intelligence.
1. INTRODUCTION
Least squares matching or correlation is known as one of
the best methods for image matching on subpixel
accuracy. It also provides a unified optimization criterion
for matching on multiple images. There are several 2. BASIC FORMULAS
variants of least squares matching that are based on
conventional least squares adjustment, including use of
approximate values and solving a linearized equation
system. For convergence to a correct minimum, these
methods are critically dependent on approximate values
in the range of few pixels, expressed in image scale.
This paper studies a method for solving the least
squares matching by search. The basic principle of the
method is straightforward: 1) the object function (the
minimum sum of squared residuals) is expressed in terms
of original, non-linearized equations, 2) search space is
defined in terms of unknown parameters and 3) the
minimum of the object function is found by means of
numerical analysis using search. Bilinear interpolation of
the gray level values is used as a method for achieving
The basic formulation for least squares matching has
been introduced simultaneously by Fórstner (1982) and
by Thurgood and Mikhail (1982), further refined by
Ackermann (1984) and adapted for multi-image matching
by Grün (1985). Those formulations are based on
linearized equations and conventional techniques for
solving and otherwise treating overdetermined linearized
equations systems by means of least squares
adjustment. Probability theory for linear or linearized
equation systems can therefore be applied directly.
Least squares matching can also be expressed in
terms of non-linear functions. For matching two
continuous and two dimensional gray level functions we
have the following formula
724
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996
x22
an
whe
g,(a
g(x
X ax
Forn
that
geor
diffe
strait
1987
1992
I
>
il
e
wher
