Figure 5: Left to right: Patch positions after zero, one, two and final iteration with line-search (upper row) and without 
line-search (lower row). 
the weight matrix W = I, this corresponds to the resid- 
ual F(x) being orthogonal to the plane spanned by the 
columns of J(x), as illustrated in Figure 4. If W # I, 
the vectors will instead be conjugate with respect to W. 
Near the solution, the angle 9 between J ; p; and F'; will 
approach 7/2 and the quotient |LJ x pk||/||LF || = cos 8 
will approach zero. Thus, a termination criteria on 8 may 
be formulated as 
ILI pi|| € &|[LF|| 
for a constant € = cos ! (1/2 — fiiit). 
This termination criteria will work for almost all problems 
with a non-zero optimal residual. However, for very small 
optimal residuals, e.g. for synthetic, perfect data, the ter- 
mination criteria may have to be adjusted to 
|LJzpzl| < + e)|[LFr||- 
to avoid unnecessary iterations due to round-off errors. 
Of course a heuristic problem-dependent termination cri- 
teria may be used as well. 
5 SIMULATIONS 
5.1 Example iteration 
The Gauss-Newton method with and without line-search 
was applied to a least squares template matching problem 
where the template was a 11 x 11 pixels white square with 
a4 pixel black border. The image consisted of tiled squares 
19 pixels wide with a separation of 12 pixels. The template 
was binary (black=0, white=255) while the image was low- 
pass filtered in order to create a more difficult matching 
problem. The transformation had 8 parameters, allowing 
affine deformation and radiometric changes both in scale 
and shift. The picture re-sampling function was bilinear. 
Implementation details are found in (Borlin, 2002). 
A typical example of the algorithmic differences is shown 
in Figure 5. In the first iteration both algorithms take a full 
step (first and second column). In the second iteration, the 
undamped algorithm takes the full step (lower third col- 
umn) and starts to diverge. After 20 more iterations, it os- 
cillates about the position shown in the lower right column. 
In contrast, the damped algorithm rejects the step lengths 
a = 1 and a = 0.5 since the residual norm would increase, 
but accepts a = 0.25 (top third column), and converges in 
six iterations toward the optimal solution (upper right col- 
umn). 
5.2 Pull-in range 
The effect on the pull-in range was investigated by ap- 
plying the two algorithms with progressively more distant 
starting approximations and recording their success or fail- 
ure. 
The optimal patch parameters were a11 = b11 = 57.95, 
aı2 = b91 = 1.56, 5] — b19 = 0, Tg — 34.33, rt = 0.1. 
The starting approximation of the patch position a11,511 
was varied between 45 and 71. The starting approxima- 
tions of the other geometric parameters were a1» — 051 — 
1.5 and a91 = bız = 0. The starting values for the radio- 
metric parameters were approximated from the picture at 
the initial patch position. 
The pull-in ranges and side minima convergence for the 
algorithms are illustrated in figures 6 and 7, respectively. 
The undamped algorithm converged toward the correct so- 
lution for 223 starting positions while the damped algo- 
rithm succeeded for 326 starting positions. The undamped 
algorithm converged toward a side minima at 5 occasions. 
The corresponding number for the damped algorithm was 
48. 
6 SUMMARY 
These simulations illustrate the usefulness of a line-search 
strategy in solving an Adaptive Least Squares Matching 
problem. In the example iteration, the damped algorithm 
avoids divergence at the cost of two extra residual calcu- 
lations in the second iteration, a cost which is more than 
balanced by the fourteen extra iterations the undamped al- 
gorithm performs before giving up. For the same problem, 
the pull-in range for the damped algorithm is higher than 
for the undamped algorithm. However, the repetitive pat- 
terns in the example image also increased the convergence 
towards identical side-mimina. This is likely to be less of 
a problem in less non-repetitive images. 
—10— 
  
Figure 6: 
undampe: 
for which 
converge 
Finally, tl 
potential 
two resez 
squares o 
plored in 
REFERI 
Bórlin, N 
Gauss-Ne 
Departme 
Dennis Ji 
Methods 
Equation: 
Eriksson, 
Nonlinea: 
ment of C 
Eriksson, 
P-A., 19 
forward 1 
Optimiza 
Gruen, A 
tal measi 
Close Ra 
tles, Caitl