Fua-2 
Our ultimate goal is to accommodate the full taxonomy of snakes described by table 1. The colums 
represent different type 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. 
Constraints/Type 
Simple curve 
Ribbon curve 
Network 
Smooth 
Polygonal 
Planar 
Rectilinear 
Low res. roads, rivers. 
Man-made structures. 
Planar structures. 
Roof tops, parking lots. 
High res. roads. 
City streets 
City streets 
City streets 
Road network. 
Street Networks. 
Street Networks. 
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. 
2.1 Polygonal Snakes 
A simple polygonal snake, C , can be modeled as a sequential list of vertices, that is, in two dimensions, a list 
of 2-D vertices S 2 of the form 
S 2 = {(*. Vi), 1' = 1,..n} , (1) 
and, in three dimensions, a list of 3-D vertices .S3 of the form 
S3 = {(x, y, Zi), i = 1,.. .,n} . (2) 
In the two dimensional case, the “image energy” of these curves—the term we try to minimize when we 
perform the optimization, is taken to be 
£,(C) =£ \VI(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 {x,y) in the image, and \C\ is the length of C. In practice, £j(C) is computed by 
integrating the gradient values |VI(f(s))| in precomputed gradient images along the line segments that 
connect the polygonal vertices. 1 We therefore rewrite £j as 
£/ = ^ S((x, - , y$), (xt+i 1 Vi+i))/ 'y ^ I't.i+i ) 
1 <• <n 1 <i<n 
S{{xi, yi), {Xj, yj )) = - f |VZ(x,- + X(xj — Xi),yi + \(yj — y,))| dA , ( 4 ) 
Jo 
Li,j = \J~ x * ) 2 ff - (jj — ) 2 • 
L,j is the length of the individual line segments and S((x i} y,), (xj, yj)), the sum of the gradient values along 
one segment, is computed by sampling the segment at regular intervals. 
In the three dimensional case, £/(C) is computed by projecting the curve into a number of images, 
computing the image energy of each projetion and summing these energies. Formally, given a set of N 
1 The gradient images are computed by gaussian smoothing the original image and taking the x and y derivatives to be finite 
differences of neighboring pixels.