Using a training data set optimal parameters can be deter- 
mined by simulated annealing (Hellwich, 1998). 
Results are line pixels with line directions and no-line pix- 
els, and posterior odds of the most probable line state ver- 
sus the no-line state for each pixel. The latter are used for 
snake-based linear feature extraction explained in the next 
section. 
3 SNAKES 
This Section is based on (Laptev, 1997), where details of 
the approach can be found. 
3.1 Basics of Snakes 
The concept “snake”, also called “active contour model”, 
was originally introduced in (Kass et al., 1987). It combines 
internal smoothness constraints like bending of a curve with 
image forces like the gradient. This idea can be repre- 
sented as a sum of its energies 
E(¥) = Eimg(9) + Eine (©) (9) 
where E;n: represents the internal energy and Eim, the 
image energy. The position of the snake where all these 
forces compensate each other corresponds to the local 
minimum of the snake's total energy E. Thus, the prob- 
lem of the optimization of the snake's position is equivalent 
to the minimization of its energy. 
The image energy of the snake can be defined as: 
1 
Fons} = -[ P(i(s, t))ds, (10) 
0 
where P(V(s,t)) is a function with high values correspond- 
ing to the features of interest. When attracting the snake 
to edges in images, P(v(s,t)) is usually taken equal to the 
magnitude of the image gradient, that i$ 
P(v(s,t)) — |VI(v(s, t))], (11) 
where I(7(s,t)) is the raw image or — more often — the im- 
age convolved with the Gaussian kernel. The convolution 
with a Gaussian kernel smoothes the image and removes 
disturbances which prevent the snake from moving toward 
the positions with lower image energy corresponding to the 
more salient image features. 
The internal energy makes it possible to introduce geomet- 
ric constraints on the shape of the snake. It can be defined 
as 
1 
50-1 sa! 
0 
md 
  
2 
a 2360 as, ( (12) 
    
| +20) 
  
where a(s) and ß(s) are arbitrary functions that control the 
snake’s tension and rigidity. The constraint on tension is 
introduced by the first order term and makes the snake act 
like a membrane. The rigidity is constrained by the second 
order term and makes the snake act like a thin plate. 
In order to find the optimal position for the snake, its energy 
has to be minimized. According to the variational calculus 
this must be a solution to the Euler-Lagrange differential 
equation of motion. When choosing a particular deforma- 
tion energy the differential equation controling the motion 
of the snake becomes linear and can be separated. This 
has the advantage of solving one optimization step in linear 
time. For the actual implementation the equations have to 
be discretized. For details of this refer to (Laptev, 1997). 
3.2 Ribbon Snakes 
The goal of this paper is to extract linear features with sig- 
nificant width. They can be modeled by ribbons whose 
sides correspond to the features' boundaries. Using rib- 
bon snakes, linear features can be extracted by optimizing 
the position and the width of the ribbon. In order to rep- 
resent ribbon snakes, the parametric curve v(s,t) can be 
augmented by a third component w(s, t) (Fua and Leclerc, 
1990): 
V(s,t) = (x(s,t),y(s,t),w(s,t)), 
Such representation implies that each slice of the ribbon 
snake (so, to) is characterized by its width 2w(so, to) and 
the location of its center (z(so,to), y(so,to)). All center 
points compose the centerline of the ribbon (cf. Figure 2 
(a). 
In order to perform the optimization of the ribbon snake, 
the forces which act on it have to be defined. The advan- 
tage of the ribbon’s representation in equation (13) is that 
the expression for the snake's internal energy Fin: Can be 
directly used for ribbon snakes. Doing so, the width of rib- 
bons will be constrained by tension and rigidity in the same 
way as the two coordinate components. The internal forces 
which act on the ribbon snake will on the one hand con- 
strain the ribbon's centerline to be a smooth curve. On the 
other hand, they will control the distance between the rib- 
bon's sides, forcing the sides to be parallel. 
In contrast to the original snakes, the image information for 
ribbon snakes has to be taken into account not at the center 
of the curve (z(s,t), y(s, t)), but at the ribbon's left and right 
sides. As shown in Figure 2 (a), for each slice of the ribbon 
Ü(so, to) there exist two points Jr (so, to) and Un(so, to) cor- 
responding to the ribbon's left and right sides. Adapting 
the expression for image energy Ein, in equation (10) to 
ribbon snakes, the function P(v(s,t)) in equation (11) has 
to be redefined. Requiring the image contrast to be large 
along the left and the right side of the ribbon, P can be de- 
fined as the sum of the image gradient magnitudes on the 
left and right ribbon sides: 
P(v(s,t)) — |VI(én(s, t))| - IVI(or (s, t))] (14) 
However, when searching for linear features which are 
known to be brighter or darker than their surroundings, the 
result of the extraction can be improved if the direction of 
image gradients at the left and right sides of the ribbon will 
be taken into consideration, too. For example, the extrac- 
tion of bright linear features implies that the image inten- 
sity at the ribbon sides has to change from dark to bright 
at the left ribbon side and from bright to dark at its right 
side (cf. Figure 2 (b)). This is equivalent to demanding the 
projection of image gradient on the vector 7i(s, t) to be neg- 
ative along the ribbon's left side v; (s, t) and positive along 
its right side Vr(s,t). Taking this into account, the function 
P(w(s,t)) can be redefined as 
P(ü(s,t)) = (VI(@r(s,t)) — VI(@r(s,t))) - À(s,t). (15) 
534 International Archives of Photogrammetry and Remote Sensing. Vol. XXXII, Part 7, Budapest, 1998 
(0<s<1), (13) 
  
  
  
Fig 
bot 
(z( 
ent 
the 
3.3 
tere 
sna 
the. 
far 
inet 
ima 
in (| 
is g 
cen 
app 
stra 
sna 
opti 
hav 
A p: 
lanc 
strai 
tude 
the 
sho 
be s 
half 
whe 
and