The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Vol. XXXVII. Part B3b. Beijing 2008 
For the road extraction the image is first segmented with the 
normalized cuts algorithm using edge and colour criteria. The 
main goal of this step is the separation of road areas and non 
road areas. The parameters of the normalized cuts algorithm are 
selected such that an oversegmentation is achieved because we 
do not want to miss any road boundaries. Therefore, a grouping 
step follows, in which the segments are grouped again 
according to colour and edge criteria, this time not of single 
pixels but of the regions. Then, the segments have to be 
evaluated in order to extract potential road parts, based mainly 
on shape criteria. If the roads are undisturbed and clearly visible, 
several different roads often are grouped together as one 
segment, resulting in irregular shapes which cannot easily be 
identified as road parts by shape criteria. Therefore, large 
segments are split up according to the branches of their 
skeletons before the road part evaluation. The goal is to extract 
road parts that cover a large part of the road surfaces while 
keeping the number of false positives low. After the extraction 
neighbouring road parts with similar directions are assembled to 
chains because sometimes the road is covered by several road 
parts, for example due to disturbances caused by context objects 
or different road surfaces. As only road parts with similar main 
directions are linked, junctions are not considered in this step. 
2.2 Segmentation and grouping 
2.2.1 Segmentation: The first step is the segmentation of the 
image, which is done with normalized cuts. The normalized 
cuts algorithm is a graph-based segmentation method in which 
the pixels are seen as nodes of a graph, connected by weighted 
edges. The edge weights describe the similarity of the pixels. 
The graph is divided into segments by minimising the 
normalized cuts criterion, which maximises the similarity 
within each segment as well as the dissimilarity between 
different segments. Details of the algorithm can be found in 
(Shi and Malik, 2000). One advantage of this method is that it 
aims for a global optimisation of the segmentation while in 
determining the edge weights local features are taken into 
account. Another advantage is that the similarity measure is 
generic, so it can be adapted to the application, and several 
criteria can be combined. The goal of the segmentation is a 
good division between road areas and non-road areas. Three 
criteria are used for the determination of the weights: colour, 
edges and hue. The choice of these criteria is based on the 
appearance of roads in high-resolution aerial images as 
homogeneous regions bordered by edges. The number of 
segments has to be predefined in the current application. It is 
chosen to be high enough to detect the majority of road borders, 
which leads to an oversegmentation. For details of this step 
refer to (Grote et al., 2007). 
2.2.2 Grouping: In the next step, the segments are grouped 
in order to reverse the oversegmentation. The grouping is based 
on shape and edge criteria, like the segmentation, but this time 
the features of the regions, not of single pixels, are considered. 
The features used are: 
border region. The mean edge strength is taken from a Canny 
edge image. It should not exceed a defined threshold. As an 
improvement of our previous work, here also the direction of 
the edges in the border region is taken into account: only edges 
that run approximately parallel to the border are considered in 
calculating the mean edge strength. In addition, the part of the 
shared border region which contains parallel edges is put in 
proportion to the whole border region, so the separating 
influence of a small part of the border region with a strong edge 
remains small. 
For the second criterion, the standard deviation of colour, the 
three channels are considered separately. In each channel the 
standard deviation of the merged region should not exceed a 
threshold. 
The third criterion is the difference of the colour histograms 
between the regions. This criterion is the replacement for the 
previously used mean value of colour; it is more robust. For 
each channel, the colour histograms in both regions are 
calculated and compared with the chi-square measure (Press et 
al., 1992). The chi-square distances should not exceed a defined 
threshold. 
The fourth criterion, the length ratio of the shared border to the 
border of the smaller region, is applied only if the main 
directions of both regions, computed via the orientation of the 
best fit ellipses, differ. In this way the composition of elongated 
regions is not disturbed, but the formation of protruding parts 
through merging is discouraged. When the directions of both 
regions differ, a significant part of the region must constitute 
the shared border. 
All conditions must be met for two segments to be merged. The 
process is done iteratively; in each iteration the ten best pairs of 
regions are merged, until no more regions can be found that 
fulfil the conditions. The result of the segmentation and 
grouping are segments which are relatively homogeneous in 
colour, and most segments belonging to road areas are large 
enough to be evaluated by shape in the next step. 
2.3 Road part extraction 
In order to extract road parts from the segments, the segments 
are evaluated using shape criteria and some radiometric criteria. 
Large segments are subdivided before the evaluation because 
often one road segment covers several roads connected via 
junctions. These road segments cannot be detected using shape 
criteria because their shape is irregular. 
For the subdivision the skeleton of the region is calculated. 
Before the skeleton calculation the region is smoothed with 
morphological operations (opening, closing) in order to obtain a 
smoothed skeleton. Note that this step may result in different 
unconnected skeletons for one segment because the opening 
operation can break up the segment into several parts. After an 
elimination of short branches, each remaining skeleton junction 
is examined. First the branches are divided into two groups 
according to their direction. The direction of one branch is 
taken as reference for one group, and branches whose directions 
differ more than 45° from this direction are placed in the other 
group. The group with fewer branches (usually one) defines the 
secondary direction. If there is the same number of branches in 
each group, the group with the shorter total length defines the 
secondary direction. Then for each branch that belongs to the 
secondary direction it is determined at which point the branch 
should be separated from the region. For this purpose, a line