nbul 2004 
ie number 
'aks using 
od. This 
ck width. 
determine 
es chosen 
complete 
Its shown 
grid, will 
ent. 
A EN N N: 
1 tool for 
al energy 
uld be on 
curvature 
icture for 
efficients 
or which 
ban area 
ution for 
| varying 
«es to the 
erated in 
| energy 
all nodes 
sans that 
dels) was 
“A snake 
constraint 
e defined 
/ internal 
es which 
lependent 
d define 
(1) 
  
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B3. Istanbul 2004 
‚where / is current time or evolution step, s is proportional to 
the curve length, and x and y represent coordinates for nodes in 
the image domain. In this paper, the internal and external 
energy at any node are determined throughout the curve, and 
we find the optimum position of nodes with energy minimizing 
techniques. The energy of the snake can be written as a 
summation of internal and image energy as, 
T ke = En (v) + Zin (v) (2) 
The internal energy controls the shape of the curve with 
geometric constraints and can be decomposed into a first and 
second order term as, 
l 
E.) [a() |v (s,0F +B) |v, (NP ds* 8 
0 
Here, coefficient a controls the elastic force of the curve and 
coefficient B controls the bending force of the curve. More 
detailed description for the internal energy will be stated next 
section. The image energy attracts the curve to the salient 
features in the image and is represented as, 
l 
E, (v) == [P(v(s,1))ds (4) 
0 
where P(v(s, t)) is function value corresponding to the feature 
of interest. In this paper, we focus on the edges as the salient 
feature, so P(v(s, 1)) is the image gradient. 
The total energy of the snake is written as 
| ^ 
Epic = Jalv G0 lv. GOl -Po,n) as: © 
0 
To minimize the energy functional, we use the Euler-Lagrange 
differential equations of the functional yielding the following 
simplified Euler evolution equation, 
 9PO(sD) (6) 
Ov 
  
Ov(s,t 
( à an pv.) 
; | sss 
Where y represents the viscosity of the curve. The higher 
viscosity makes the evolution of the curve slower. v, is the 
second derivatives with respect to s. The temporal derivative 
can be numerically written as 
Ov(s,r) 
NEWS: (7) 
Assuming external forces are changed very slowly with time 
step, substitute equation (7) to equation (6), equation (6) is 
rewritten as, 
OP(v(s,t —1)) 
=—7(v(s,r)=v(s,1—1)) (8) 
Ov 
av (s, 7) s Wu (s,7) + 
Let V, be a set of each nodes as, 
V, = {v(i,1),i =1,2..0n} (9) 
where n is the total number of nodes in the curve. 
Then, with equation (9) equation (8) can be rewritten in matrix 
form as 
ani air PUO (10) 
Ov 
where the matrix 4 is a pentadiagonal banded matrix composed 
of a and fj, and / is an nxn identity matrix. With the initial curve 
modeled by sequential list of nodes, the next curve is calculated 
by equation (10) iteratively and iteration will be stopped when 
total energy change is less than a threshold. Finally, we can find 
an optimal position of curve with this energy minimization 
technique. 
4.2 Local Energy Coefficients for Urban city block detection 
As stated in the previous section, snakes have internal energy 
components which are controlled by coefficients « and fl. For 
accurate delineation of city blocks, boundaries of detected 
edges should remain in linear form in the preserve of 
concavities (parking lot near the side of city block) and 
convexities (parked car at the side of a city block). With the 
above mentioned characteristics, we know that the corner 
region is well suited for lower f// compared with the sides of the 
block. Figure 9 shows us the difference between applying 
global energy coefficients (constants) versus local energy 
coefficients (context dependent). In Figure 9, the target for 
snakes simulates the example of a city block. The red line is a 
curve which is composed of blue nodes. Figure 9b is a result of 
applying global energy coefficients (constants) with initial 
contour in Figure 9a. Here, the corner area is well delineated, 
however snakes is sensitive to the concave and convex part. But 
applying different weighting coefficients to the corner and side 
area, an improved result is obtaining particularly in the side area. 
7 5 70M Lema. 
iu 
    
(c) 
Figure 9. Global and local energy coefficients for snakes. (a) 
Initial contour (b) Global coefficient with a — 1, f — 0. (c) Local 
coefficient: a — 1, f — 0 for corner area and a ^ 300, f — 0 for 
side area. 
To use local weighting coefficients, we must have a priori 
knowledge about the point context before minimization. For our 
city block case, the point context (corner vs. side) is determined 
from the initialization. Davis ef a/ (1995) tried to apply local 
coefficients for the snakes, and they had a little success because 
their resultant snake model did not fit with user expectation. 
Main problem for their approach is due to the unreliability of 
expectations for target shape. However, we can overcome that 
problem by using the ‘detected lines on the road’ obtained in 
the previous section. Detailed usage is described in the next 
section. 
4.3 Applying Adaptive Snakes to City Block Delineation 
Generally, initial curves for snakes are given by manually. 
However, road intersection, which are determined by detected 
lines on the road, generate the initial curves in our approach and 
also, they give us the information for the corner area. Seeing the 
result of detected lines in Figure 8, we focus on two facts; the