hood constraints between individual patches to enforce the local 
continuity in a global solution (Gruen, Agouris, 1994). In another 
approach least squares template matching was combined with 
Kalman filtering of the parameters of the road for road tracking 
(Vosselman, Knecht, 1995). 
Instead of a square or rectangular template, we extend the least 
squares template matching technique into LSB-Snakes by using a 
deformable contour as the template. This is shown in Figure 2. 
The ribbon with black outline is our initial template and the white 
one is the final solution. Its centre line is the extracted feature, in 
the example of the figure the centre line of a road segment. 
Suppose a linear feature, the centre line of the template is 
approximated by a spline curve and represented in parametric 
form as 
x(s) 2 WNTG)X, , 
i=l 
; (2-5) 
y) = NV Nor, , 
i=1 
where X; and Y; are the coefficients of the B-spline curve in x 
and y direction respectively. In terms of the B-spline concept, 
they form the coordinates of the control polygon of the curve. 
Ni (s) is the normalized mth B-spline between knots u; and 
u |, (Bartels, et al., 1987). While the knot sequence is 
i+m+ 
given, feature extraction can be treated as a problem of 
estimation of the coefficients X; and Y; of the spline curve. 
The first order differentials of the B-spline curve can be obtained 
as 
n 
Y NEGAX,, 
i=1 
> 
A 
Il 
(2-6) 
A 
Il 
n 
y= SUN"GAY,. 
i=l 
Substituting the terms in equation (2-4), we obtain the linearized 
photometric observation equations with respect to the 
coefficients of the B-splines. The linearization of the observation 
equations for all involved pixels can be expressed in matrix form 
as 
-e, 2 G,NAX «G,NAY-1, ; P (2-7) 
m 
with 
N = INT) Ns)... Nc): Q-8) 
Since a linear feature is essentially unidirectional, the template 
would slide along it during matching. To ease this problem and 
simplify the implementation, the above equations are changed to 
268 
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996 
TE mx 
GNAX 4, isavesP 
GNM EP 
mx. * 
(2-9) 
TE my my ^ 
A pair of independent observation equations are thus formed for 
the x and y directions. The observation vectors /,,. and Py 
x 
contain the differences of conjugate pixels, P, , and P, y are the 
x 
corresponding weight matrices, which are introduced as diagonal 
matrices. 
2.2 Geometric observation equations 
In a semi-automatic feature extraction scheme, a set of seed 
points near the feature of interest is given by a human operator or 
other preprocessing procedures. In terms of least squares 
adjustment, these seed points can be interpreted as the control 
points which determine the location of the feature to be extracted. 
Because they are only coarsely given, a correction has to be 
estimated. Therefore they should be considered as observations. 
Thus the second type of observation equations can be established 
as 
TE ex 
| 
= 
| 
= 
e 
(2-10) 
ey = V0 , P , 
where x, and y, are the observation vectors of coordinates of 
the seed points in x and y direction respectively, P... and P. 
are the corresponding weight matrices, introduced as diagonal 
matrices. The linearization of the coordinates with respect to the 
coefficients of the B-splines can be expressed in matrix form as 
ex 
Tex = NAX -t.. ; P... , Q-11) 
“22 7 MAY fo: P 
in which £,, and £,, are given by 
t., =x0-x,=NX"-x 
3 0 0 
er (2-12) 
Lom Y m yg m MY yo.. 
With the seed points an initial curve is formed as a first shape 
approximation of the feature. [n order to stabilize the local 
deformation of the template we introduce the following 
smoothness constraints. Assume the initial curve is expressed by 
x9(s) and y9(s). We establish the third type of observation 
equations based on the first and second derivatives of the curve as 
2x À x (5) —x9(s) ; P. NS im 
E = y,(s) - y°(s) > P , 
TEssx = EG) xA) , Po ’ (2-14) 
T€ dy. 3s (5) HAE , Py : 
Linearizing them with respect to the coefficients of the B-spline 
they can be expressed in matrix form as 
   
Where ^ 
defined 1 
Any oth: 
formula! 
these ob: 
2.3 Sol 
In our le 
as the pr 
Y of the 
function 
and the 
constrail 
equivale 
T. 
y Pv - 
In terms 
the snak 
external 
the ima 
constra 
location 
To mini 
the follc 
A furthe 
normal 
respecti 
it can be 
bm 
various 
well est 
utilized