sensor system configuration is applied: GPS, INS and cameras. 
The GPS and the INS have been integrated to determine the 
vehicle trajectory (Schwarz et al. 1993). After post-mission 
Kalman filtering, the trajectory is obtained with high accuracy, 
and represented in a global coordinate system. The velocity of 
vehicle is about 60 km/hr and the image capture rate is one 
image pair per 0.4 second. 
A high accuracy method (El-Shemy and Schwarz, 1993) has 
been used to calibrate parameters of the geometric 
transformation relationships between the vehicle coordinate 
system and the various sensor systems such as the GPS, the 
INS and the camera. As a result, the image sequences are 
georeferenced in the same coordinate system. 
3. SYNTHESIS OF MULTIPLE CONSTRAINTS INTO 
A PHYSICALLY-BASED 3D SHAPE MODEL 
It has been of considerable interest in using deformable models 
to address image segmentation. The active contour model (2D 
snake) has been shown successful in interactive boundary 
extraction (Kass et al., 1988; Terzopoulos et al., 1988; and 
Menet et al., 1990). The main advantage of deformable models 
is that both geometric and physical constraints can be 
incorporated into the model, comparing the conventional 
methods in which only geometric constraints are considered. 
For this reason, we proposed an approach based on an 1dea of 
"shape from sequences", in which a  physically-based 
deformable curve model in space 1s employed to accommodate 
the combinations of multiple constraints for the reconstruction 
of 3D road centerlines. 
3.1. 3D Road Shape Modeling by B-splines 
In this road model, 3D cubic B-splines are introduced in 
defining a 3D active curve model (a 3D B-snake): 
m-i 
Q(u) — ( x(u,), yw), z(u) ) - ( XViB(u) ), j=0.1....n-1 (1) 
1-0 
where B; are the basis functions of B-splines, V;-(X, Y,Zj are 
a set of control vertex to this B-spline curve, n and m are the 
numbers of sampling points on the curve and control vertices, 
respectively. There are following reasons of choosing B-splines 
to represent the model: (a) the property of local control: only a 
small part of the curve needs to change if a control vertices 1s 
modified; (b) the possibility of including features (e.g., corners 
and straight lines): corners or straight lines can be imposed on 
the curve if multiple knots are posed. (c) invariant 
characteristics: the control vertices of B-splines are invariant 
under affine and projective transformation; (d) numeric 
advantages: the number of unknowns in (1) of determining a 
curve is m, the number of control vertices, instead of n, the 
number of sampling points on the curve. 
3.2. Deformation Mechanism 
By use of the least action principle (Hamilton's principle), the 
deformable dynamics of the model is governed by an equation 
of motion: 
E = es Ein(Q(u)) + e2Eeu(Q(U)) > min (2) 
where E, represents the external energy acting on the model 
(Eex is defined in section 3.5), and E; is the internal energy 
858 
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996 
resisting deformable away from the natural state and 
maintaining the local continuity and connectivity, e; and e? are 
constants for weighting these two terms. E;,, is described as the 
smoothness energy consisting of two terms: 
Eim= a(fQGo du) * Bejg Qo du) BG) 
Q Q 
The first term is a measure of the distance discontinuities 
(stretching effectiveness) while the second term is a measure of 
the orientation discontinuities (bending effectiveness). The 
constants a and f control the relative balance of stretching and 
bending force. The total energy E is a function of the set of 
control vertices. Therefore, minimizing the energy of the curve 
results in a final shape of the model. 
3.3. Solution for the Minimization of Energy 
Substituting (1) and (3) into (2), the discrete version we get 1s 
E - E telatuX VB Bu EVBI QUY | 
j=0 
+ezFox [Q(w;)1} (4) 
To obtain the extreme minimum of E, Apply 
CE | OY z 0, k=0,4.2,.....m (5) 
Finally the resulting equations are 
n-i 
m—1 
X V4 au) B' (wy) Bi (uj) + B14) Bk" (1) Bi" (uj)] 
1201/50 
n-4 
z—(e2/ e) > Br(uj)Fex' (Q(uj)) ,k=01,2,...m (6) 
j=0 
An iterative method (Kass et al., 1988) can be used to solve the 
above equations: 
V — (A^ My! (yW-F) (7) 
where y is an Euler step size, and A is a banded matrix (mxm). 
It should be noted that the dimension of the inversion is m 
instead of n (the dimension of the classic snake). 
3.4. Reconstruction Procedure 
Given an image sequence of road centerlines, the following 
steps of processing are performed: 
|l. The vehicle trajectory corresponding to the desired road 
centerlines 1s obtained by a post-mission Kalman filter using 
the GPS/INS navigation data (figure 1). 7; indicates the 
position of the exposure camera station along the trajectory. 
2. The initial line segments of road centerlines in the first 
stereo image pair of the image sequence are delineated by the 
operator. After photogrammetric intersection, a corresponding 
3D line segment is determined. This segment is denoted by 
  
SoS1 1n figure 1. 
3. Calculate the vector differences 7:7: +1 between the positions 
of station 7; and T;.;, Shift the differential vector 7iTi+: from 
the trajectory to the desired centerline position one by one. A 
sequence of points S; on the approximate centerline is 
obtained. 
     
» A