622 
The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Voi. XXXVII. Part B3b. Beijing 2008 
robust, and computationally feasible road detection algorithms 
is essential. 
In this research we develop semi-automatic road extraction 
system for updating and storage road network data bases and to 
reduce charges and also keeping or increasing precision and 
speed of information extraction in comparison with field work 
and GPS usage. Combination of some of the existing road 
extraction techniques such as spectral and spatial data 
clustering, morphological functions and graph theory is used in 
this proposed system. 
In the proposed system, primarily the input images that are 
multi-spectral and pan-sharpened IKONOS images of Lavasan 
city in Iran (with respectively 4 and 1 meters spatial resolution), 
are spectrally classified by use of Fuzzy C-Means (FCM) 
clustering technique and road class binary image is obtained by 
definition of threshold value. This technique (FCM) tests 
different distance function types in performing FCM clustering 
and finds the most precise and fastest one. Afterwards, quality 
of detected road features is improved using morphological 
operators. Our approach proceeds by performing spatial cluster 
analysis using k-means technique and hence road center line 
nodes are attained. In this step, effect of choosing different 
number of cluster centers in spatial domain for comprehensive 
road shape estimation is investigated. Finally by use of graph 
theory and minimum spanning tree (MST) and defining an 
appropriate cost function, these key points are connected and 
vector road centerline is obtained. These road vectors can be 
directly imported into GIS environment in different formats for 
updating digital road maps. 
The main achievement of the proposed system is extraction of 
different shaped roads such as straight, spiral, junction and 
square and attaining acceptable precisions in order to updating 
road maps. The only drawback of this system is limitation in 
completely extraction of road center line in place of squares and 
closed loops. So supervision of human operator for completing 
missed links and closing the loops is inevitable. 
This paper consists of five sections. After this introduction, 
Section 2 describes c-means and FCM clustering algorithms, 
morphological operators and MST algorithms as part of the 
background information. Section 3 presents in detail the 
proposed semi automatic road extraction algorithm. Section 4 
provides some experimental results of application of the 
proposed algorithm to image data. Conclusions are given in 
Section 5. 
2. BACKGROUND 
2.1 C-Means and FCM Clustering Techniques 
There are several methods for segmenting images based on two 
fundamental properties of the pixel values: One of them is 
“discontinuity” that uses the discontinuities between gray-level 
regions to detect isolated points, edges and contours within an 
image. The other is “similarity” that uses decision criteria to 
separate an image into different groups, based on the similarity 
of the pixel levels. Clustering is one of the methods of second 
category. 
While there are many different algorithms for clustering, this 
paper focuses on the two well-known clustering algorithms for 
classification of image in spatial and spectral domain; c-means 
and fuzzy c-means (FCM) clustering. 
K-means Clustering 
The K-means algorithm is one of the most popular iterative 
descent clustering methods. It is intended for situations in 
which each object belongs to one class exclusively. The K- 
means method is numerical, unsupervised, non-deterministic 
and iterative. 
In this kind of clustering the dataset is partitioned into K 
clusters and the data points are randomly assigned to the 
clusters. Then for each data point the distance to each cluster is 
calculated and the data point is moved into closest cluster. 
These steps are repeated until no data point is moved from one 
cluster to another. At this point the clusters are stable and the 
clustering process ends. For more information about K-means 
technique see (Hung, 2005). 
Fuzzy C-Means Clustering (FCM clustering) 
Among the various clustering algorithms, FCM is one of the 
most popular methods used in data analysis since it is suited to 
deal with imprecise and uncertain nature of image data sets, 
such as remote sensing images. 
This technique offers the opportunity to deal with data that 
belong to more than one cluster at the same time. Most of the 
fuzzy clustering algorithms are objective function based. They 
make an optimal classification by minimizing an objective 
function. In objective function based clustering usually each 
cluster is represented by a cluster model. This model consists of 
a cluster center and maybe some additional information about 
the size and the shape of the cluster. The extension of the 
cluster in different directions of the underlying domain is 
determined by the size and shape parameters. 
The degrees of membership of each data point in different 
clusters are computed from the distances of the data point to the 
cluster centers by considering the size and the shape of the 
cluster as stated by the additional model information. The closer 
a data point is to the center of a cluster, the higher is its degree 
of membership to this cluster. So the division of a dataset into c 
clusters can be stated as the minimization of the distances of the 
data points to the cluster centers, since, of course, we want to 
maximize the degrees of membership. 
The Fuzzy C-means (FCM) algorithm proposed by Bezdek is an 
unsupervised clustering technique, aims to find fuzzy 
partitioning of a given training set, by minimizing of the basic 
c-means objective function. For more information about FCM 
technique, see (Hoppner, 1997; Modenesi et al., 2006; Dave, 
1989) 
2.2 Morphological Functions 
The word morphology commonly denotes a branch of biology 
that deals with the form and structure of animals and plants. We 
use the same word here in the context of mathematical 
morphology as a tool for extracting image components that are 
useful in image representation and description of region shape, 
such as boundaries, skeleton and the convex hull. We are 
interested also in morphological techniques for pre- or post 
processing (Gonzalez, 2002). 
The language of mathematical morphology is set theory. 
Different morphological operators are made using structural 
elements. Structural elements are the basic component of the 
morphological functions that define the neighbourhood of the 
image pixels by using 1 and 0 values. 
By combining set theory rules by logical operators, different 
morphological functions are made such as Dilation, Erosion,