)mposed 
listances 
ent is to 
surface. 
nt of ex- 
ed using 
>xponen- 
ant, as it 
n to bea 
a set Sy 
, a set of 
p-and-go 
»9 is a set 
airborne 
NT 
eferred to 
, an auto- 
 transfor- 
two 2.5D 
sented by 
nd Strunz 
ported us- 
data than 
re used in 
  
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B4. Istanbul 2004 
triangular plane patches of S,. A similar algorithm was 
trialled on small artificial data sets (Schenk et al., 2000) in 
a comparison study of matching algorithms. Habib et al. 
(2001) report on such an algorithm where the parameters 
of the transformation are found with a System featuring a 
Hough transform. 
2..2 The Matching Algorithm: Let the three rotation 
angles w, ó and x, the three translations TuTy and 77 
and the scaling factor s be the seven parameters of a con- 
formal transformation which moves the set of points S» 
to a position 55, which minimises the set of the normal 
distances from the points of S to the facets of Si. The 
normal distance from a point I" € S^ to a plane defined by 
the three vertices (P. Q, R) C S, of the triangle enclosing 
the point 7" is given by: 
y laa] + by! + c.z1 — d| 
m TU oS 
va? +b? 4 ¢2 
where a, b, c and d are functions of P, Q and Rc; I' (a^, yl, 2) 
is a function of w, ¢, &, Tx, Ty, Ty, s and Tr; 55) 
with 7 € S». 
An approximation D* of the normal distance D is obtained 
by linearising Equation | using a Taylor expansion and 
keeping only the first order derivatives : 
(1) 
0D ap 0D 
Ow Od OK 
oD oD oD 
ATE d Aly ne AT 
tt Tar vt aah 
oD 
where: 
Do is the distance D evaluated at the initial value of the 
parameters of the transformation; 
Au, Ab, AK, ATX. ATy, ATz and As are corrections 
to initial values of the parameters. 
Let V be the difference between the approximated normal 
distance D* and the exact distance D: 
Dzli-U 
Equation 1 can thus be written as: 
  
This calculation repeated over the n points of S» is ar- 
ranged in matrix notation to give: 
v=L+AX ( 
Cn 
~ 
where; 
Vis ann x 1 vector of residuals 
L is a n x 1 vector of "observables" Dg (also called the 
"absolute term") 
A is an n x 7 matrix of the first order derivatives (often 
called the “design” matrix) 
X is a 7 x 1 vector of correction to the initial values of the 
parameters (to be estimated) 
The conventional least squares solution for a system of 
weighted observations is given by: 
X= (ATC AAT, (6) 
where: 
X is the vector of least squares estimators 
G is the variance/covariance matrix of the observations. 
2.2 Weighting Techniques 
The denser the data, the more faithful the triangulated sur- 
face is to the true surface. The use of weights in a least 
squares fit becomes essential when the reference data is ir- 
regularly distributed. Large triangles are formed in sparse 
data areas, and small weights have to be given to the cor- 
responding normal equations to counterbalance the result- 
ing large interpolation errors. The weighting technique 
adopted for this project is based on the interpolation er- 
rors 02, which are estimated from an exponential model fit- 
ted on the experimental covariogram. A comparison study 
of weighting techniques for least squares surface matching 
found that the best results in a sparse reference data envi- 
ronment were obtained with this method (Paquet, 2003a). 
This method involves the production of a covariogram or 
covariance function, from which the mean of the product of 
the heights can be evaluated for any given distance between 
the points. The covariances for a distance d are obtained 
oD on =: db using: 
96). Reg- DZ Dp El Ar —Ap + — AR (3) 8 sw fm 
» Ow Op Ok un MA M tird) 
fied p D 2D oD ene = a 
ES ie ne TOL AT + D + AT, ; Lb : 
Carras and OT. 73 OTy OTz The data point spacing is irregular and the distance and 
ell, 1995; oD , product of the heights are calculated for each pair of points 
cal (coastal + 3705 =} in the data set. These results are then classed in bins, ac- 
aas (2002) cording to the range of the distance separating them. Fi- 
hnique for With the model requirement that D — 0 and rearranging ~~ nally the mean distance, mean product and standard de- 
: deforma- 
solving for 
viation of the products are calculated in each bin. The 
covariogram is the plot of the value of the mean product 
Equation 3: 
  
V = Dar oD, + 28 ni + QU (4) Versus the mean distances. The experimental covariogram 
Ow db ^C OR. fitted with an exponential model is shown in Figure 1. The 
ce in heights oD 9 OD. + OD s weight of the normal equation is then computed as the in- 
f the other tors AT OTy et OTz AT. verse of the standard error of prediction a?(Q): 
sarch min- oD wae 
s of $3 t0 +Z— AS W = 1/c°(O) (8) 
0s 
1173