Yandong Wang 
  
ROAD NETWORK EXTRACTION BY HIERARCHICAL GROUPING 
"Yandong WANG and John TRINDER 
School of Geomatic Engineering 
The University of New South Wales 
Sydney, NSW 2052, Australia 
ywane € intermap.ca, j.trinder? unsw.edu.au 
  
Working Group III/3 
KEY WORDS: Feature Extraction, Image Processing, Photogrammetry, Recognition, Topology. 
ABSTRACT 
This paper presents an automatic method for road network extraction from low-resolution images using hierarchical 
grouping technique. The method consists of three major steps: firstly it extracts line features from original images and 
generates smooth lines in a split-and-merge operation; a hierarchy of line images is created using different thresholds 
for line length, based on the generated line images; the linear features in the line images are then grouped hierarchically. 
Finally, knowledge of road networks is applied to remove non-road segments to form a complete road network. The 
paper includes results of tests on the implementation of these procedures. 
1 INTRODUCTION 
Automatic road extraction aims at recognizing roads in images and locating them accurately, and thus providing up-to- 
date information of roads for various applications such as updating of GIS data for mapping and urban planning. The 
former concerns the identification of roads in images, while the latter concentrates on determining their spatial positions 
in the image. Obviously, identifying roads in the image is more difficult than defining their locations, as recognition 
requires the use of domain knowledge of roads (Gunst 1996; Trinder and Wang, 1998). 
A road is a man-made object in the real world, which serves as a tool for communication between two different 
communities. It has distinct geometric and radiometric surface properties, as well as topology. In low-resolution 
images, a road is a line feature with distinct contrast against its background, and it connects to other roads to form a 
road network. These properties are widely used for delineation of roads in the existing methods for road extraction, in 
which a road is usually delineated in three steps, i.e. road finding, road tracking and road linking. In road finding, a line 
operator is usually applied to find seed points of roads (Bajcsy and Tavakoli, 1976; Fischler et al, 1981; Ton et al, 1989; 
Trinder and Li, 1995). Some other methods such as wavelet transform (Grün and Li, 1995) and gradient direction 
profile analysis (Wang et al, 1992) are also used to detect seed points of roads. At this stage, existing maps and GIS can 
also be used to provide approximate positions of existing roads and their properties (Maillard and Cavayas, 1989; 
Bordes et al, 1997) or possible structures and shapes of roads (Cleynenbreugel et al, 1990). Once the seed points of a 
road are found, they are extended in a local area based on some geometric and photometric criteria. Road points can be 
tracked by graph searching (Fischler et al, 1981; Wang and Howarth, 1987; Wang et al, 1992), by dynamic 
programming (Grün and Li, 1995) or by an active testing method (Geman and Jedynak, 1996). Due to the effects of 
occlusions such as shadows cast by trees and overpasses, vehicles on the road, surface anomalies, etc., the tracked roads 
are usually divided into segments. Therefore, segments are finally linked together to form continuous roads based on 
geometric constraints such as collinearity and proximity (Vasudevan et al, 1988; Ton et al, 1989). 
This paper presents a novel method for automatic road network extraction from low-resolution images. The method 
uses image processing for finding road candidates and knowledge of road networks for elimination of false roads. It 
operates in three major steps. Firstly, it extracts lines from the original image using a line operator such as a 
morphological operator. A split-and-merge operation is applied to the extracted lines to generate smooth line segments. 
A hierarchy of line images is generated by applying several thresholds of line length to the extracted line images. 
Progressing through the levels of the hierarchy will result in an increasingly dense distribution of line segments. Lines 
are grouped according to their similarities in geometry and radiometry. The grouping of line segments starts from the 
top of the hierarchy (with sparse distribution of line segments) to create the main structure of the road network. It then 
proceeds through the levels of the hierarchy to the lowest level (most densely distributed set of line segments) to add 
  
International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000. 943