Fua - 4 
where K is a pentadiagonal matrix, and X and Y are the vectors of the x and y vertex coordinates. Because 
K is pentadiagonal, the solution to this set of equations can be computed efficiently in O(n) time using LI 
decomposition and backsubstitution. Note that the LU decomposition need be recomputed only when o 
In practice a is computed in the following manner. We start with an initial step size A p , expressed in 
pixels, and use the following formula to compute the viscosity: 
where n is the number of vertices. This ensures that the initial displacement of each vertex is on the average 
of magnitude A p . Because of the non linear 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 is repeated until the step size becomes 
less than some threshold value. In most cases, because of the presence of the linear term that propagates 
constraints along the whole curve in one iteration, it takes only a small number of iterations to optimize the 
3-D Curves. To extend the smooth snakes to three dimensions, we add one term in z to the deformation 
energy of Equation 7 and Ed becomes 
Since the derivatives of Ed with respect to x, y, and z are still decoupled, we can rewrite Equation 10 as a 
set of three differential equations in the three spatial coordinates: 
projections, and their derivatives, are computed from the state vector S using the camera models. Similarly, 
to compute the viscosity, we use the camera models to translate the average initial step A p , a number of 
pixels, into a step A w expressed in world units and use the latter in Equation 11. 
state vector 5 becomes the vector 5 = {(x, t/j w,)}, i = 1,.. .,n} and the average edge strength the sum of 
changes. 
initial curve. 
( 12 ) 
+ H -2 ^(2x, - x,_i - x i+1 ) 2 + (2y, - yi -1 - y,+i) 2 + (2z, - z,_i - ¿¿+i) 2 
(K + aI)X t 
(K + aI)Z t 
{K + aI)Y t 
where X ,Y , and Z are the vectors of the x,y, and z vertex coordinates. 
The only major difference with the 2-D case is the use of the images’ camera models. In practice, Ei(C) 
is computed by summing gradient values along the line segments linking the vertices’ projections. These 
Ribbons 2-D snakes can also be extended to describe ribbon-like objects such as roads in aerial images. 
A ribbon snake is implemented as a polygonal curve forming the center of the road. Associated with each 
vertex i of this curve is a width that defines the two curves that are the candidate road boundaries. The 
the edge strengths along the two boundary curves. Since the width of roads tends to vary gradually, we add 
an additional energy term of the form