nterface concept 
external Software 
SDK is to call the 
"he user has to set a 
ther a server, client 
operation produces 
isible for the chosen 
ss of the produced 
ter. Afterwards it is 
1e global pointer. If 
once you don’t have 
tity is. The function 
clusive all parameter 
r a function call with 
r.SetAperture(int i) 
SetAperture(int i) 
in external software 
function calls in his 
ited connection kind 
application. Beyond 
s a clear and safe 
IENCES WITH THE 
)LLEI D7 METRIC, 
Recife, Brazil 1999 
IMPROVING THE ROBUSTNESS OF LEAST SQUARES TEMPLATE MATCHING WITH 
A LINE-SEARCH ALGORITHM 
Niclas Borlin 
Department of Computing Science,Umeé University, SE-901 87 UME A, Sweden, niclas.borlin@cs.umu.se 
Working Group V/3 
KEY WORDS: Algorithms, Matching, Digital, Reliability, Targets, Non-linear Optimization 
ABSTRACT 
The Adaptive Least Squares Matching (ALSM) problem of Gruen is conventionally described as a statistical estimation 
problem. This paper shows that the ALSM problem may also be interpreted as a weighted non-linear least squares prob- 
lem. This enables optimization theory to be applied to the ALSM problem. The ALSM algorithm may be interpreted as 
an instance of the well-known Gauss-Newton algorithm. A problem-independent termination criteria is introduces based 
on angles in high-dimensional vector spaces. The line-search modification of the Gauss-Newton method is explained and 
applied to the ALSM problem. The implications of the line-search modification is an increased robustness, reduced oscil- 
lations, and increased pull-in range. A potential drawback is the increased number of convergences toward side minima 
in images with repeating patterns. 
1 ADAPTIVE LEAST SQUARES MATCHING 
Adaptive Least Squares Matching (ALSM) (Gruen, 1985, 
Gruen, 1996) is a powerful technique for locating features 
in digital images. A template image defines the feature and 
may either be synthetic or from a real image. 
In (Gruen, 1985, Gruen, 1996), ALSM is described as a 
statistical estimation problem 
IC, 9) — elz,y) = glm,y), (1) 
where f(x,y) is the template, e(x, y) is noise, and g(x, y) 
is called a picture, formed by re-sampling a real image 
90(x, y) under geometrical and radio-metrical transforma- 
tions. Calculating the difference 1 = f(x,y) — go(z, y) 
and linearizing Equation (1) leads to an initial observation 
equation 
1—e = Ax. (2) 
In this equation, the design matrix A contain the coeffi- 
cients of the linearized equation and x contain the param- 
eter corrections to be estimated. If the statistical assump- 
tions E(e) = 0, E(ee”) = 03 P-* hold, the least squares 
estimation of Equation (2) is 
& = (ATPA) ATPI. (3) 
Since the original problem is non-linear, the final solution 
is obtained iteratively, with the picture re-sampled and the 
design matrix re-calculated at each iteration. The iteration 
is stopped when the correction & fall below a certain size. 
This may be interpreted as that we start with xg as the 
identity transformation and calculate g(z, y) (-go(x, y)), 
l, and A to establish the observation equations (2). The 
calculated correction X is added to the current approxi- 
mation as x, — xo -- Xo. The process is then repeated with 
g(z, y), l, and A calculated from x, instead of xo, etc. 
The important observations are that g(z, y), 1, and A may 
be formulated as functions of x, and that the parameter 
approximations are updated as 
Xkp41 — Xp + Xg- 4) 
2 NON-LINEAR LEAST SQUARES 
A weighted non-linear least squares problem (see e.g. (Den- 
nis Jr. and Schnabel, 1983)) is written as 
min f(x) = min 5 |]LF(x)|3 = min JF (x) "WF (x), 
(5) 
where the residual function F(x) is a twice continuously 
differentiable vector-valued function from t^ to 30", n is 
the number of parameters, and m is the number of obser- 
vations. The matrix W is a symmetric positive definite 
weight matrix and LTL = W. 
2.1 The Gauss-Newton method 
A classical method for solving Problem (5) is the Gauss- 
Newton method. At each iteration k, the function F(x) is 
linearized around the current point x, i.e. 
F(xx + pr) & F(x&) + J (Xx) Pr, (6) 
where the Jacobian J, (x) is a matrix with partial deriva- 
tives such that 
  
9 f;(x) 
3x); = : 7 
The vector p; is found by solving 
d 
min z ||L(Fs 4- J«pi)l|2, (8) 
Pr 2 
where F, = F(x;) and Jy = J(x4). The solution to 
Problem (8) is 
Pr = (JE WI,) ! JE W(—F,) (9) 
and the next approximation is calculated as 
Xk+1 = Xk + Pk. (10) 
2.2 Geometric interpretation 
Geometrically, the function F(x) defines a surface in R™. 
Problem (5) corresponds to finding the point x ,, in param- 
eter space corresponding to the point F(x) in observation