International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B3. Istanbul 2004 
  
where (NL, NS) is the size of image (number of lines, number 
of samples) Also, we define the function N(X) which 
represents total number of elements for set X. 
i) With o; calculate the line coordinates set P; with point 
coordinates (/; , s;), 
1</,<NL 
(45° < 09 «:13592) 
PE P, 71: cosQ 
S. II ——— 
f sin 
Iss, < NS 
P = p;—$,:sinÓ (09«0«45? 9r 135? € 0 < 180°)’ 
I ut lut 
d cosÓ 
11) Next, we count the pixels where the edges coincide with the 
lines just described. For each line, 7, overlay with each edge, X. 
The total number of coincident pixels (C;) will be an indicator 
of "obstacles" encountered by that line. A large number of such 
obstacles will indicate that it is less likely to be a road feature, 
whereas a small number of obstacles will mean that it is more 
likely to be a road feature. The number of line/edge coincident 
pixels is 
C=] NE) 
k 
where E, is an edge pixel. 
iil) We characterize the degree, to which the line is free from 
obstructing edges as, 
Fs N(P)—-N(C) x100 (0 € F; < 100). 
N(E) 
A high value (near 100) of F; is an indicator of a road. 
Repeating this process for each line we can make a graph of the 
free passage measure vs. line number. Peaks in this graph will 
very likely correspond to roads. 
  
  
  
  
  
  
  
  
Figure 7. Result of acupuncture method on small example 
region. (a)-(c) are for Ay, and (a)-(c) are for 0,2. (a) and (d) 
Free passage measure. (b) and (e) Clustering result. (c) and (f) 
Detected lines on the road. 
Figure 7 is the example of applying acupuncture algorithm to 
one of the regions. In this region, the predetermined dominant 
road directions are 2.5? (0,;) and 91? (0,;). Figure 7a, 7b and 7c 
are for 2.5? case and others are for 91? case. Figure 7a and 7d 
show the graph that represents the relationship between line 
number and the free passage measure. In Figure 7a, Figure 7b, 
468 
Figure 7d and Figure 7e, the X axis represents the line number 
and the Y axis is the free passage measure. 
From the graphs in Figure 7a and 7d, we select the peaks using 
modified hierarchical histogram clustering method. This 
method requires the user to specify a minimal block width. 
Figure 7b and 7e are the results for that method and determine 
the lines selected as roads. The 0,, graphs yields 3 lines chosen 
as roads. The 0,, graphs yields 4 lines. Applying the complete 
Acupuncture method to the study area yields the results shown 
in Figure 8. Those lines, interpreted as an urban road grid, will 
be used as initial approximations for the snake refinement. 
    
eL eme EN 
Des: 
Figure 8. Detected lines on the road by acupuncture method 
4. Adaptive Snakes 
Many research groups have tried to use snakes as a tool for 
rural area road extraction, and they have applied global energy 
coefficients. Applying global energy coefficients should be on 
the assumption that the linear features have similar curvature 
characteristics through the curve. Since the road structure for 
rural roads is not so complex, global energy coefficients 
perform well. Here, we propose adaptive snakes for which 
energy coefficients vary locally to accommodate urban area 
road extraction. First, we introduce the general solution for 
snakes and second, present the advantage of local varying 
energy coefficients. Third, we apply the proposed snakes to the 
study area with initial approximations which are generated in 
previous section. In this paper, we define ‘global energy 
coefficients’ as applying the same coefficients to the all nodes 
in one curve while ‘local energy coefficients’ means that 
coefficients vary locally. 
4.1 General Solution for Snakes 
The original concept for snakes (Active contour models) was 
introduced by Kass ef. al(1988), and they define it as “A snake 
is an energy-minimizing spline guided by external constraint 
forces and influenced by image forces". Also, it can be defined 
as a movable curve in image domain controlled by internal 
forces (elastic and bending force etc.) and image forces which 
attract or repel the curve. 
The Snakes can be modeled as a curve with time-dependent 
sequential list of nodes in two dimensions and define 
parametrically like 
v(s,t) = (x(s,f), y(s,t)) O<s<1 (1) 
  
Intern 
,wher 
the ct 
the ii 
energ 
we fin 
techn 
summ 
The i 
geom 
secon 
Here, 
coeffi 
detail 
sectioi 
featur 
where 
of inte 
feature 
The to 
To mit 
differe 
simpli 
where 
viscosi 
second 
can be 
Assum 
Step, s 
rewritte 
Qv 
Let V,t 
where r