oth geometric and 
ding, a river or the 
nimum value of the 
(or nearly satisfies) 
ieously and enforce 
| consistency of the 
ect databases from 
low computational 
roperties. 
s. We then present 
Finally, we demon- 
raints upon individ- 
on multiple snakes 
'odels. 
KES 
urves that may be 
rtices, or, for more 
or a 3-D extruded 
. In the latter case, 
ust supply not only 
s’ that defines the 
with some of these 
as,” that is, circular 
to remain planar. 
these features rest 
pe is defined by the 
minimizing an ob- 
e full taxonomy of 
Table 1. The al- 
| within the Radius 
DE) [Mundy et al., 
sled as a sequential 
| list of 2-D vertices 
ba (1) 
    
  
| Constraints/ Type || Simple curve 
| Ribbon curve 
| Network 
| Triangulated meshes | 
  
  
  
  
  
  
Smooth Low res. roads, rivers High res. roads | Road network Terrain 
Polygonal Man-made structures City streets Street Networks 
Planar Planar structures City streets Street Networks 
Rectilinear Roof tops, parking lots | City streets Buildings 
  
  
  
Table 1: Snake taxonomy. The columns represent different types of snakes and the rows different kinds of constraints that 
can be brought to bear. The table entries are examples of objects that can be modeled using these combinations. 
and, in three dimensions, a list of 3-D vertices $3 of the form 
$: mins) -1Lh...nl. (2) 
In this paper, we refer to S, the vector of all z, y, and z coor- 
dinates of the 2-D or 3-D vertices that define the deformable 
model's shape as the model's state vector. 
In the 2-D case, the “image energy" of these curves—the 
term we try to minimize when we perform the optimization 
is taken to be 
IC] 
£0) =~ | IVZ(f(s))] ds, (3) 
where I represents the image gray levels, s is the arc length 
of C, f(s) is a vector function mapping the arc length s to 
points (z,y) in the image, and |C| is the length of C. In 
practice, £r(C) is computed by integrating the gradient values 
|VZ(f(s))| in precomputed gradient images along the line 
segments that connect the polygonal vertices. 
In the 3-D case, illustrated by Figures 1 and 2(a), &r(C) is 
computed by projecting the curve into a number of images, 
computing the image energy of each projection, and summing 
these energies. 
2.2 Smooth Snakes and Ribbons 
These snakes are used to model smoothly curving features 
such as roads or ridgelines. 
2-D curves. Following Kass et a/. [1988], we choose the 
vertices of such curves to be roughly equidistant and add to 
the image energy £r a regularization term £p of the form 
£p(C) 2 i Yo, (zi — zii + (yi - yi) 
tu2 à (20 — Tics — zii) + (Que — Yi—r — vi+1)” 
(4) 
and define the "total energy" £r as 
The first term of £p approximates the curve's tension, and 
the second term approximates the sum of the square of the 
curvatures, assuming that the vertices are roughly equidis- 
tant. In addition, when starting, as we do, with regularly 
spaced vertices, this second term tends to maintain that reg- 
ularity. To perform the optimization we could use the steepest 
or conjugate gradient, but it would be slow for curves with 
large numbers of vertices. Instead, it has proven much more 
effective to embed the curve in a viscous medium and solve 
the equation of the dynamics 
OE dS 
ct eni omi 6 
Sedan j (6) 
ue EEE 
wit 35 = as 95° 
International Archives 
of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996 
where £ is the energy of Equation 5, o the viscosity of the 
medium, and S the state vector that defines the current posi- 
tion of the curve. Since the deformation energy £p in Equa- 
tion 4 is quadratic, its derivative with respect to S is linear, 
and therefore Equation 6 can be rewritten as 
  
  
  
KsS: + a(S: — Se-1) = = E 
> (Ks+al)S = aSi1- = n (7) 
where 8£p ; 
55 = KS 
and Ks is a sparse matrix. Note that the derivatives of £p 
with respect to z and y are decoupled so that we can rewrite 
Equation 7 as a set of two differential equations of the form 
ei s o 
K IV -—-tzoV-i-- 
(K+a )V t aV; 1 aV s 
where V stands for either X or Y , the vectors of the x and y 
vertex coordinates, and K is a pentadiagonal matrix. Because 
K is pentadiagonal, the solution to this set of equations can 
be computed efficiently in O(n) time using LU decomposition 
and backsubstitution. Note that the LU decomposition need 
be recomputed only when a changes. 
In practice, a is computed in the following manner. We start 
with an initial step size A5, expressed in pixels, and use the 
following formula to compute the viscosity: 
vn | O€ 
A, as , (9) 
  
a = 
  
where n is the number of vertices. This ensures that the 
initial displacement of each vertex is on the average of mag- 
nitude A,. Because of the nonlinear term, we must verify 
that the energy has decreased from one iteration to the next. 
If, instead, the energy has increased, the curve is reset to its 
previous position, the step size is decreased, and the viscosity 
recomputed accordingly. This procedure is repeated until the 
step size becomes less than some threshold value. In most 
cases, because of the presence of the linear term that prop- 
agates constraints along the whole curve in one iteration, it 
takes only a small number of iterations to optimize the initial 
curve. 
3-D curves. To extend the smooth snakes to three dimen- 
sions, we add one term in z to the deformation energy of 
Equation 4. Since the derivatives of £p with respect to x, 
y, and z are still decoupled, we can rewrite Equation 7 as a 
set of three differential equations of the form of Equation 8, 
where V. now stands for either X, Y, or Z, the zr, y, or z 
vertex coordinates. 
The only major difference with the 2-D case is the use of the 
images’ camera models. In practice, £;(C) is computed by 
223