ISPRS Commission III, Vol.34, Part 3A „Photogrammetric Computer Vision“, Graz, 2002 
  
  
Attributes / Relations 
Average Enclosed 
Intensity inside segment 
Road Property Addressed 
Roads generally have high gray- 
scale intensities 
  
  
Width — Average distance 
between edges 
Road widths usually fall within 
a certain range 
  
Difference in spatial 
direction between edges 
Roads generally appear as pairs 
of spatially parallel boundaries 
  
Difference in gradient 
direction between edges 
Road boundaries have opposite 
gradient directions 
  
Intensity difference 
(between inside and 
outside the segment) 
Road appears brighter than its 
surroundings 
  
  
  
  
Table 1. Description of Road Segment Attributes 
Initial tests on our sample data set using cluster analysis 
revealed that the last three attributes do not usefully distinguish 
between different road segments. Since these attributes were 
ineffective, they were not used in clustering. 
2.2 Inductive Learning 
Inductive learning is the process of generating a decision tree by 
having the computer "learn" rules, based on pre-classified 
examples provided to it. The resulting decision tree can then be 
used to classify new examples. One example application of an 
inductive learner to road recognition is to calculate thresholds, 
used for selecting edges that match road-sides. Traditionally 
these thresholds would be determined by human experts, but 
inductive learning can provide a more customized and locally 
applicable result. 
2.3 Clustering 
Clustering is the process of automatically grouping a given set of 
data into separate clusters such that data points with similar 
characteristics will belong to the same cluster. While there are 
many different algorithms for clustering, in this paper we focus 
on the KMeans and kNN algorithms. Here we describe these 
algorithms briefly (see Weiss et al, 1991 for further details). 
The clustering data set in RAIL is made up of points described 
by level 1 attributes, where each point represents an edge pair. 
This data set is to be segmented into n clusters. Each cluster 
centre is initialized with a random point from the data set, and 
each remaining point is then grouped into the closest cluster, one 
at a time. 
KMeans measures the distance between the point and the centre 
of every cluster, eventually placing the point in the closest 
cluster. After all the data points are clustered, the centre is re- 
evaluated for each cluster, then the data points are clustered 
again iteratively. The kNN algorithm differs in that, when 
grouping the data points, it looks at the k nearest neighbours 
(i.e. the closest points from existing clusters), and the data point 
is placed in the cluster containing the most neighbours. We also 
used the modification suggested by (Barandela et al, 2001) to 
improve kNN's performance. 
Once the clusters have been formed, clusters of interest are 
identified by visual inspection. In road extraction, clustering can 
be used, for example, to create a group of edges (or other image- 
level objects) that have similar shape, intensity, and so on, and 
hence form part of a road. 
A large number of experiments need to be run with different 
parameters in order to find the setting that produces the best 
result for a given problem. This whole clustering process 
requires a lot of hand tuning, to find a suitable algorithm, select 
the associated parameters, and finally pick out the useful 
clusters. In this paper we will suggest ways to automate this 
laborious process by applying inductive learning techniques to 
each of these stages 
3. INDUCTIVE CLUSTERING 
Our inductive clustering framework has been designed to learn 
from cluster descriptions what constitutes a good road cluster, 
and apply the learned knowledge to perform clustering 
automatically. The ultimate goal is to allow the system to take a 
new image and deduce, from the characteristics of the image, the 
optimal algorithm and parameters to use. It will then 
automatically identify the road cluster for the user. 
This framework uses a multi-level learning strategy to tackle the 
process systematically at the following three stages (Figure 2): 
  
  
Training Phase 
  
Training image with 
reference model 
Parameter Learning 
Rules for n 
Algorithm Learning 
Rules for algorithm 
Cluster Learning 
Rules for 
Clustering 
  
  
  
  
  
  
  
   
  
  
  
     
Testing/Application Phase good cluster 
  
  
New image without 
reference model 
  
  
  
  
  
Figure 2. Inductive Clustering Framework Overview 
Parameter Learning: Learn the parameters that will give the 
best result for a given algorithm and image type. Parameters 
include 7 (the number of clusters) and k, in kNN clustering. 
Algorithm Learning: Learn which algorithm is most suitable 
for a given image type. The previous stage determines the 
parameters to use for each algorithm. 
Cluster Learning: We then learn to identify the road clusters 
by comparing their characteristics to known road and non-road 
clusters.