The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Vol. XXXVII. Part B4. Beijing 2008 
2. STRUCTURAL ATTRIBUTES 
In this section we present four road network extraction methods, 
two of which were used in this work. A method is proposed to 
represent the extracted road networks as graphs. A 
morphological segmentation method is proposed to segment the 
urban areas in an image. Finally we describe the road network 
and urban region structural features used for the classification 
and indexing of satellite images. 
2.1 Road Network and Urban Region Extraction 
In order to compute the structural features of the road network, 
we first need to extract the road network from the image, and 
then convert the output to an appropriate representation. This 
representation should be independent of the output of the 
extraction algorithm, since we do not want to be committed to 
any single such method. In the preliminary studies reported in 
(Bhattacharya et al., 2006) we considered two network 
extraction methods (Rochery et ah, 2003, Lacoste et ah, 2005). 
The method of (Rochery et ah, 2003) is based on Higher-Order 
Active Contours (HOACs) which are a generalization of 
standard active contours. The method of (Lacoste et ah, 2005) 
models the line network as an object process, where the objects 
are interacting line segments. The output is a set of line 
segments of varying lengths, orientations, and positions. In spite 
of producing good extraction results, these methods were not 
used in this work due to the fact that they were not adapted for 
an optimization on large image databases, since manual 
expertise is needed to set the parameters in the algorithms 
according to image complexities. 
In the work reported in this paper we considered the two 
network extraction methods reported in (Fischler et ah, 1981, 
Desolneux et ah, 2000). These methods were rather easier to 
handle and could easily be adapted to large image database. The 
parameters once set in the algorithms works well with images 
of certain resolution. The output of the method described in 
(Fischler et ah, 1981) is a binary image, which after a distance 
function computation can serve directly as an input to our 
method. Figure 1(b) shows examples of the extracted network. 
The output of the method described in (Desolneux et ah, 2000) 
is a list of multiply aligned segments. In order to have a 
suitable input for our method, we convert the output of this 
method into a binary image, and use some image processing 
techniques to obtain single connected segments. Figure 1(d) 
shows examples of the extracted network. We then compute a 
distance function which then acts as an input to our method. 
The distance function resulting from these methods is converted 
to a graph representation of the road network for feature 
computation purposes. The graph itself captures the network 
topology, while the network geometry is encoded by decorating 
the vertices and edges with geometrical information. The 
conversion is performed by computing the shock locus of the 
distance function using the method of (Dimitrov et al., 2000, 
Siddiqi et al., 2002), extended to deal with multiple and 
multiply connected components with the depth-first search 
(DFS) algorithm (Cormen et al., 2001). The method identifies 
the shock points by finding out the limiting behavior of the 
average outward flux of the distance function as the region 
enclosing the shock point shrinks to zero. A suitable 
thresholding on this flux yields an approximation to the shock 
locus. The graph is constructed by taking triple (or, 
exceptionally, higher degree) points and end points as vertices, 
corresponding to junctions and terminals, while the edges are 
composed of all other points, and correspond to road segments 
between junctions and terminals. Figure 2 shows an example of 
the representation graph. The road network, Figure 2(b) is first 
extracted from the input image Figure 2(a). 
Figure 1: Extraction results with 2 methods. Example (b) is with 
the method of (Fischler et al., 1981) and example (d) is with 
themethod of (Desolneux et al., 2000) 
(c) Shock locus of road network (d) Graph representation 
Figure 2: An example of the graph representation. 
The methods cited in our study are robust on many such road 
characteristics but they often failed to extract the narrow and 
finely structured road networks which are almost hidden in 
small urban areas. This failure of the extraction methods and 
hence the features computed from road networks poorly classify 
images containing such areas. In order to obtain some 
188