28 
CMRT09: Object Extraction for 3D City Models, Road Databases and Traffic Monitoring - Concepts, Algorithms, and Evaluation 
course of the roads. In order to find the most probable course of 
the road, the subgraphs are evaluated using relations between 
the road parts and linear programming. If a DSM is available, it 
can be used in the grouping and road part extraction processes. 
DSMs have been used in the past for road extraction, but their 
influence was limited due to the relatively poor performance of 
standard image matching techniques (Zhang, 2004). We think 
that with the advent of new dense image matching techniques, 
e.g. (Pierrot-Deseilligny and Paparoditis, 2006; Hirschmiiller, 
2008), the importance of incorporating 3D information into the 
road extraction process will increase. In this paper, the 
extraction results that were achieved with and without the DSM 
are compared in order to demonstrate the respective potentials 
for road extraction. The main goal of this paper is to present the 
new method for road subgraph evaluation and to assess the 
influence of the DSM on the road extraction results. The road 
extraction approach is described in Section 2. The segmentation 
and road part extraction, which are explained in detail in (Grote 
et al., 2007; Grote and Heipke, 2008), are only reviewed 
briefly. Our new method for road subgraph evaluation is 
discussed in more detail, as well as the incorporation of the 
DSM. In Section 3, results are presented with a comparison 
between the results achieved with and without the DSM. 
Section 4 gives conclusions and directions for future work. 
2. APPROACH 
2.1 Overview 
Our goal is the extraction of roads from high resolution aerial 
images in suburban areas. We use colour infrared (CIR) images 
with a ground resolution of approximately 10 cm. Optionally, a 
DSM, e.g. generated by image matching, can also be used. The 
approach consists of three steps, namely segmentation, road 
part extraction and subgraph generation. In the segmentation 
step, the image is first divided into many small segments, which 
are then grouped into larger segments having meaningful 
shapes. Potential road parts are extracted from the grouped 
segments using shape criteria. If a DSM is available, height can 
be used as additional criterion in the grouping and road part 
extraction steps. The road parts are then assembled to road 
subgraphs (Fig. 1) if they potentially belong to the same road; 
junctions are not considered in this step. Several branches are 
allowed to be present in one subgraph. In the next step, these 
ambiguities are resolved by optimising the graph in a way that 
finds the best possibility for the course of the road without 
branches. 
Figure 1. Road subgraphs. Dashed lines: real road network; 
grey rectangles: extracted road parts; continuous 
lines: edges of road subgraphs. The blue lines 
delineate two examples for distinct road subgraphs. 
In Fig. 1, the term road subgraph and its components are 
explained. The term subgraph is used in order to indicate that it 
does not represent a complete, interconnected road network. A 
road subgraph consists of several assembled road parts. A road 
part is a segment which is classified as a road. It can correspond 
to a whole road between two junctions or only a part of the 
road, or it can be a false positive. Each subgraph extends only 
as far as road parts can be found in a more or less straight 
continuation; in this way, each subgraph usually represents only 
one road. Each road part in a subgraph has two nodes which are 
connected via a road edge. A node can also maintain 
connections to nodes of other road parts via gap edges. These 
gap edges can be understood as hypotheses for connections 
between extracted road parts that were missed in the original 
road part extraction process. If more than one such connection 
exists at one node, the node has several branches. These 
branches correspond to conflicting hypotheses for a completion 
of the road. In order to achieve a consistent road network, these 
conflicts have to be resolved by road subgraph evaluation. 
2.2 Segmentation and Road Part Extraction 
The first stage of the road extraction is the segmentation of the 
image, which is carried out in two steps, namely initial 
segmentation and grouping. The goal of the initial segmentation 
is to divide the image into small regions whose borders coincide 
with the road borders as completely as possible. The normalized 
cuts algorithm (Shi and Malik, 2000) is used for this initial 
segmentation, in which connections between pixels are 
weighted according to their similarities. The similarities of 
pixel pairs are determined using colour and edge criteria. 
Details can be found in (Grote et al., 2007). 
The normalized cuts algorithm results in a considerable 
oversegmentation. This is necessary in order to preserve most 
road borders, but as a result, the initial segments must be 
grouped in order to obtain segments that correspond to road 
parts. Grouping is carried out iteratively using colour and edge 
criteria, this time considering the properties of the regions (as 
opposed to those of the pixels, which were used in the initial 
segmentation). Segments with irregular shapes that cover roads 
across junctions can occur in this step. Therefore, the skeletons 
of the segments are examined. If they have several long 
branches (not to be confused with the branches of subgraphs), 
the segments are split. 
In the next step, hypotheses for road parts are extracted from 
the grouped segments. Geometric and radiometric criteria are 
used for the extraction. The geometric criteria are elongation 
(ratio of squared perimeter to area), width constancy (ratio of 
mean width to standard deviation) and difference to average 
road width. As radiometric criteria, the NDVI (normalized 
difference vegetation index) and the standard deviation of 
colour are used. In addition, dark areas are excluded because 
shadow areas often have similar geometric properties to road 
parts. The parameters used for the experiments described in this 
paper are listed in Table 1. The elongation, width constancy, 
compliance with average road width and the NDVI are used to 
determine a quality measure for each road part hypothesis. The 
road parts are represented as regions; for the following road 
subgraph generation a representation by the centre lines and 
average widths is also used. For calculating the centre line, the 
region boundary is split into two parts at the points on the 
boundary that are farthest away from each other. Distance 
transforms are calculated for both parts, and the points where