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.