Share Email Print
cover

Proceedings Paper

Efficient interactive agglomerative hierarchical clustering algorithm for hyperspectral image processing
Author(s): Sabbir A. Rahman
Format Member Price Non-Member Price
PDF $14.40 $18.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

Paper Abstract

Traditional hierarchical clustering algorithms require the calculation of a dissimilarity matrix which is mapped to a binary tree or 'dendogram' based upon some predetermined criterion. Although 'optimally efficient' algorithms requiring O(N2) time and O(N) storage are known for several clustering methods, with few exceptions these algorithms are relatively inefficient in practice as many pairwise distance are measured which are not necessary for generation of the binary tree. We describe here a novel 'almost single link' algorithm which is efficient both theoretically and in practice, and which can be extended to provide fast algorithms for centroid, medium and single link clustering of large data sets. Generalization to other related clustering methods is expected to be straightforward. Our algorithm also suggests a fairly efficient method for generating minimal spanning trees. In performing the segmentation we employ a particular representation of the binary tree which simplifies the task of manual investigation of the hierarchy. A customized graphical user interface including a 2D scatter plot, a visual display of the dendogram, and a false color image with overlayered clusters makes the clustering procedure a highly interactive one. By suggesting, for each of the clustering methods, possible criteria which might be useful for extracting relevant clusters from the tree information, we are able to fully automate the cluster selection procedure and thereby further reduce the effort required to segment an image. The algorithms described have been transcribed into C code and combined into a single package, the 'hierarchical agglomerative clusterer', which has been applied to the analysis of hyperspectral image data of various forest and desert scenes acquired by the HYDICE sensor. The analyses were performed on a 266 Mhz Pentium PC platform running Windows NT 4.0. Typical segmentation times for the fastest algorithm ranged form 17 seconds for a 15232-pixel image to 2833 seconds for a 209840-pixel image, each pixel representing a 210-band spectrum. These initial studies suggest that the HAC package will provide a sound framework for making detailed comparisons of the effects of different clustering algorithms or dissimilarity measures. Its overall speed makes it a promising tool not only for hyperspectral image processing applications but for multivariate data analysis as a whole.

Paper Details

Date Published: 16 October 1998
PDF: 12 pages
Proc. SPIE 3438, Imaging Spectrometry IV, (16 October 1998); doi: 10.1117/12.328105
Show Author Affiliations
Sabbir A. Rahman, Raytheon Optical Systems, Inc. (United Kingdom)


Published in SPIE Proceedings Vol. 3438:
Imaging Spectrometry IV
Michael R. Descour; Sylvia S. Shen, Editor(s)

© SPIE. Terms of Use
Back to Top