In: Paparoditis N.. Pierrot-Deseilligny M.. Mallet C.. Tournaire O. (Eds). IAPRS. Vol. XXXVIII. Part ЗА - Saint-Mandé, France. September 1-3, 2010 
300 
who model occlusions, shadows and disruptions of roadsides by 
driveways. There are only few examples for the explicit use of 
context objects in urban areas. Approaches incorporating height 
data use high regions implicitly as context objects to exclude 
them from the search space, e.g. Hu et al. (2004). Hinz and 
Baumgartner (2003) explicitly model cars and buildings and 
their relations to roads in order to assist the road extraction. 
In this paper, we present a new approach for road network 
extraction in suburban areas. In this context ‘suburban’ means 
areas with relatively low buildings and not as densely built-up 
as inner city centres. We use high resolution colour infrared 
(CIR) images and a DSM, but no prior information from road 
databases in order to be able to deal with regions where this 
information is not available. Unlike other authors we do not rely 
on specific road patterns, straight roads or the existence of road 
markings because of the variations in these respects that occur 
especially in newly built-up areas. Our approach is region- 
based, but we start with a segmentation of the image, not with a 
multispectral classification. In this way, the method can be more 
easily transferred to different regions and sensors. Knowledge 
about the appearance of roads in aerial images is used already in 
the segmentation, which is based on normalized cuts (Shi & 
Malik, 2000). Context objects such as buildings, vegetation and 
vehicles are used in the road extraction process, because they 
can cause disturbances in the appearance of roads, for example 
by occlusions. The network is created by linking the extracted 
roads via junction connections; isolated short roads are 
eliminated in this process. In section 2 the road extraction 
method is described. In section 3 results are presented as well as 
an analysis of their completeness and correctness. Section 4 
gives some conclusions and suggestions for further work. 
2. METHODS 
The goal of our approach is the extraction of a road network in 
suburban areas. We follow a region-based strategy on high 
resolution aerial images and use road-specific knowledge from 
the segmentation through the whole process to the network 
linking. A DSM is used as additional information. Road 
extraction starts with an initial segmentation of the image. 
Afterwards, the segments are grouped, and road parts are 
extracted. The road parts are connected locally, and ambiguous 
connections (links from one end of a road part to more than one 
other road part) are resolved through optimisation. Afterwards, 
the locally connected road parts (road strings) are linked to a 
network by setting up junction connections. 
2.1 Image segmentation, grouping and road part extraction 
2.1.1 Initial segmentation: For the initial segmentation the 
normalized cuts algorithm is used (Shi & Malik, 2000), in 
which an image is represented as a graph and segmented 
considering similarities between pairs of pixels. The segment 
borders are optimised globally such that the similarity of pixels 
between segments is minimal while the similarity of pixels 
inside the same segment is maximal. A weight matrix is set up; 
the weights represent the similarities between the pixel pairs. 
The Laplacian matrix is calculated from the weight matrix, and 
eigenvectors are calculated from the Laplacian. After a 
discretisation the eigenvectors define the segmentation of the 
image: each eigenvector represents a segment. As the dimension 
of both the weight matrix and the Laplacian is (number of 
pixels) 2 , computing the eigenvectors is only computationally 
tractable if the weight matrix is sparse. Thus, non-zero weights 
are only assigned to pixel pairs in a local neighbourhood. It is 
an advantage of the normalised cuts method that model 
knowledge can be integrated into the segmentation via the 
definition of the weight matrix. In our application, the weights 
are based on several similarity criteria specifically designed to 
separate road areas from non-road areas. One criterion is the 
colour similarity; another is the existence and strength of edges 
between the pixels. The similarity values are combined to one 
weight Wjf for each pixel pair i and j. More details on the 
definition of these weights can be found in Grote et al. (2007). 
More recently we have integrated a new criterion based on the 
normalised difference vegetation index (NDVI) in order to 
distinguish between pixels with vegetation and pixels without 
vegetation. A threshold is applied to the NDVI and a new 
similarity weight = w NDVI • wf is determined for pixel pairs 
not belonging to the same NDVI region, with 0 < w NDV ,« 1, 
so that their weights will be lowered considerably. Using the 
NDVI improves the separation between roads and vegetation 
significantly. 
2.1.2 Grouping: The result of the normalized cuts algorithm 
is over-segmented, which is necessary to ensure that most road 
borders in the image will be segment borders. But for road 
extraction, the segments first have to be grouped to larger 
segments. Two segments can be merged if they fulfil certain 
criteria, based on the appearance of roads. As the road surface is 
usually homogeneous at least in sections, the difference of the 
colour histograms and the edge strength along the shared border 
are used as a grouping criterion. Other criteria are the convexity 
of the merged regions, the shared border length (absolute and 
relative to the segment border lengths), and the mean height 
difference (from the DSM). The grouping is done iteratively. In 
each iteration cycle all segment pairs are evaluated according to 
the grouping criteria. In order to decide if two segments are 
candidates for merging, the values for the criteria are combined 
using fuzzy sets and a set of rules, ensuring that segments can 
be merged not only if all criteria are fulfilled but also if one or 
two are poor. For example, if at least two of the edge, colour 
and convexity criteria are very good and the third is still good, 
the criterion for the relative border length can be disregarded. 
All segment pairs that are candidates for merging are sorted by 
the sum of the normalised values for the criteria. In each 
iteration cycle, the best 10 % of segment pairs are merged. 
2.1.3 Road part extraction: Road parts are extracted from 
the grouped segments according to geometric and radiometric 
criteria. Geometrically, road parts are elongated and in most 
cases convex regions with a limited range of widths, so the 
elongation (ratio of squared perimeter to area), the convexity 
(ratio of segment area to area of convex hull) and the width 
constancy (ratio of mean width to standard deviation of width) 
should be high and the average width should lie within the 
range of typical road widths. The centre line for each road part 
is determined by a distance transform. The average width is 
twice the average distance between the centre line and the 
segment borders. Additionally, the road parts should have a 
minimum length, and they should lie in low regions in the 
normalised DSM. As radiometric criteria a low NDVI and a low 
standard deviation of the intensity are required, and the 
intensity should neither be very low nor very high. All criteria 
must meet certain thresholds for the region to be extracted as a 
road part, but some criteria are balanced against each other: to 
allow the extraction of curved road parts, the convexity can be 
lower than the threshold if the elongation is high. After the 
extraction, adjacent road parts are merged if they have similar 
directions and if the merged region also fulfils the criteria for 
road parts. A quality measure is calculated for each road part