Peter Doucette
3.2 Edge Detection
When the spatial resolution of an image is such that road features manifest as elongated regions instead of single edges,
edge-based extraction methods often impose the additional constraint of anti-parallelism (Neuenschwander et al., 1995).
Another approach is to extract single edges from reduced resolution layers, and fuse the multi-scale space results
(Baumgartner et al., 1999). These methods can perform quite well, yet may carry some extra algorithmic overhead. In
general, edge-based road extraction requires reasonably well-defined edges. The Canny operator edge detection results
in fig. 6 demonstrate that edge definition can be locally problematic in high spatial and spectral resolution images.
Moreover, the stream feature in the upper left can be easily misconstrued as a road in this case. We conjecture that edge
detection methods in general benefit relatively little from the additional spectral information contained in multispectral
versus single layer images. On the other hand, region-based methods may have potentially more to gain from additional
spectral information, which is a premise of our approach.
SW : d
3 4 Ey i {x - G
CTS, | 2 [i
ce 2] t a
: T LS EX iz
E * SN x 400 pm
HE AT TERRE cas ARG eT
T. US pen ae eM A = iB . wi A
PX Ge. DUS uz Li
} M £i. T4
à * a : : Il s =
JE te 6 Y
ix Zo.
Bi + jd ^
» 1: 3
zd op
++ s NA
JE a d
eo mM ET = ^, "|
OX NIA an. e S
DU RT A
hj $5 ize yu j^ da MS men neg (a) (b)
Figure 6. Canny edge detection from (a) PC1 of original image; (b) MLC road class binary image
3.3 Deriving Topology from Spatial Clusters
3.3.1 MST and K-means. Graph-theoretic methods have been suggested as an effective means of deriving structural
information for curvilinear features (Zahn, 1971; Suk and Song, 1984; Dobie and Lewis, 1993) or elongated regions
(Lipari et al., 1989) via selective linkaging of samples. Similarly, Kangas et al. (1995) describes a variation of the SOM
in which the mimimum spanning tree (MST) algorithm is used as the neighborhood criterion between codewords in
sample space to enhance the mapping of certain feature types. Inspired by this variation, we employ MST to link
codewords (post-convergence) as opposed to individual samples to derive road topology. But unlike Kangas, K-means
clustering is used instead of Kohonen learning. The incentives for doing so include a generally faster convergence, no
learning rate or neighborhood parameter requirements, a lighter computational load, less susceptibility to local minima
traps, and less dependence on the order of sample presentation. (The ‘arbitrary’ tie rule in step 2 makes K-means
sensitive to sample presentation order.)
Fig. 7 demonstrates the vectorization process with the road class binary image of test area 1 as input. In fig.7a the
codebook is initialized as a grid in the input space. Such initialization achieves an efficient balance between final cluster
size uniformity and algorithmic convergence time. An advantage with batch codeword updating is that the median or
trimmed mean can be easily substituted for the mean computation in step 3 of K-means to enhance noise tolerance.
Although this adds slightly to computational requirements, it is particularly effective for samples exhibiting strong
central tendencies, as is the case here. This reveals yet another limitation of sequential updating, which intrinsically
finds the local simple mean. Fig. 7b shows the codebook convergence using ‘K-trimmed means’ clustering.
Convergence is fast, requiring = 20 iterations within 10 seconds from an uncompiled script routine on a 300Mhz
Pentium. Thin dotted lines indicate the Voronoi tessellation polygons (the dual of Delaunay triangulation) for the nodes,
which provide a helpful visualization of each codeword's "influence region" in the input space. At this stage, dead and
weak codewords are determined for removal from further consideration. To assess relative cluster strength, eq. (2)
shows the normalized cluster scatter measure used, where S; is the scatter matrix for the ith codeword, C;.
250 International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000.
