i- 
Peter Doucette 
This paper presents a semi-automated clustering-based approach to road centerline vectorization from high resolution 
imagery that represents a variation of Kohonen's self-organizing map (SOM) algorithm (Kohonen, 1997). The 
neurobiologically inspired SOM algorithm belongs to the unsupervised learning (clustering) variety of artificial neural 
networks (ANN). While cluster analysis is often used as a form of unsupervised spectral classification, the interest here 
is to use cluster analysis to find and map spatial structure within spectrally classified road pixels. The spectral 
classification step is what renders the method semi-automated. Beyond this, we assume that no ancillary cartographic 
information is available, e.g. DEM or coarse-resolution vectors. From a binary image of spectrally classified road 
pixels, localized road centerline nodes are mapped via an iterative clustering method. The nodes self-organize according 
to the local density fluctuations of the input, and global structure is provided by linking cluster centers with a minimum 
spanning tree (MST) algorithm. The MST cost function incorporates global cluster statistics to deal with image noise. 
The subsequent tree structure is densified and pruned locally as needed, and candidate loops are closed where 
appropriate. Finally, nodes are ordered for topological consistency, and a vectorized road network is available for direct 
GIS database entry. Since clustering exemplifies a local center-of-gravity approach, it is not sensitive to edge definition 
of road features, and allows for more meaningful exploitation of multispectral imagery versus edge-based methods. 
2 METHODS FOR SELF-ORGANIZATION 
Cluster analysis is a basic method of self-organization. It describes a regression solution that optimally partitions an m- 
dimensional input space containing a set of N vectors, P = {X,, X,..., Xy}, where X; = [Xo 1» X6 20-5 XG, m € N”, into 
a representative set of K cluster centers, or *codebook" vectors, C 2 (W;, W;,..., Wy), where W; € 9i". Each W; 
represents a single "codeword" in the codebook, and in general K «« N, where K must be prespecified. Cluster analysis 
is sometimes referred to as vector quantization (VQ). Usage of the latter term is generally associated with signal 
compression, and the former with pattern recognition. In the present context, we are interested in aspects of both. In 
(Linde et al., 1980) an important distinction is drawn between aspects of cluster analysis and VQ concerning the 
intended application. For example, one application may require the design of a vector codebook from a set of training 
vectors, which are subsequently fixed for use in quantizing (classifying) new vectors outside of the training set, e.g., test 
vectors. In contrast, another application may use the codebook only for purposes of pattern detection within the training 
set; i.e., the training set is the entire set. Our road extraction strategy is an example of the latter, where the 
dimensionality of the input vectors is m = 2 for (x, y) pixel coordinates. 
2.1 Iterative Optimization 
Iterative optimization is the most widely used approach to cluster analysis. The basic idea is to iteratively adjust a set of 
initialized K codebook vectors in such a way as to globally improve a criterion function, e.g., sum-squared-error (SSE). 
The limitations associated with this "hill-climbing" technique include a guarantee of only local optimization (not 
global), and sensitivity to the initial quantity and location of the codebook vectors. Despite these shortcomings, the 
simplicity of implementation and its computational tractability makes iterative optimization a viable approach for many 
applications, including the current one. We consider two familiar techniques: K-means and Kohonen learning. 
2..1 Batch Codebook Updating. The most recognizable clustering method by name is perhaps the K-means 
algorithm (MacQueen, 1967). It is also identified as the generalized Lloyd algorithm (GLA) based on an earlier work by 
Lloyd, which was formally published in (Lloyd, 1982). For completeness, we list the steps of the K-means algorithm: 
Initialize K codebook vectors in the input space. 
Partition the samples according which codeword each sample is closest to; ties resolved arbitrarily. 
For each partition, compute the mean of its associated samples from the previous step. 
Iterate from step 2 until a stopping criterion is satisfied. 
P ur 
Though many different measures are cited in the literature, the L, (Euclidean) norm is a standard choice for the 
similarity measure of step 2. The L, norm is sometimes used to improve computational performance. K-means is 
considered a batch method because the entire codebook is updated at each iteration, which differs from the sequential 
method of Kohonen discussed next. 
2.1.2 The Self-Organizing Map (SOM) is the artificial neural network based on competitive learning developed by 
(Kohonen, 1982). It is distinct from K-means in three respects: 1) codewords are updated sequentially (as opposed to 
batch), 2) codewords are spatially ordered in the input space according to a predefined topology in a independent 
network space, and 3) use of a smoothing kernel and learning rate schedule during codeword updating. A primary goal 
of the SOM is to define a mapping from an input space 9t," onto a network space Ry’, where m 2 d, and typically d < 2. 
Fig. 1 illustrates the topological ordering of a simple one-dimensional SOM network with four neurons, and a two- 
  
International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000. 247