NASA Logo

NTRS

NTRS - NASA Technical Reports Server

Back to Results
A Fast Implementation of the ISOCLUS AlgorithmUnsupervised clustering is a fundamental tool in numerous image processing and remote sensing applications. For example, unsupervised clustering is often used to obtain vegetation maps of an area of interest. This approach is useful when reliable training data are either scarce or expensive, and when relatively little a priori information about the data is available. Unsupervised clustering methods play a significant role in the pursuit of unsupervised classification. One of the most popular and widely used clustering schemes for remote sensing applications is the ISOCLUS algorithm, which is based on the ISODATA method. The algorithm is given a set of n data points (or samples) in d-dimensional space, an integer k indicating the initial number of clusters, and a number of additional parameters. The general goal is to compute a set of cluster centers in d-space. Although there is no specific optimization criterion, the algorithm is similar in spirit to the well known k-means clustering method in which the objective is to minimize the average squared distance of each point to its nearest center, called the average distortion. One significant feature of ISOCLUS over k-means is that clusters may be merged or split, and so the final number of clusters may be different from the number k supplied as part of the input. This algorithm will be described in later in this paper. The ISOCLUS algorithm can run very slowly, particularly on large data sets. Given its wide use in remote sensing, its efficient computation is an important goal. We have developed a fast implementation of the ISOCLUS algorithm. Our improvement is based on a recent acceleration to the k-means algorithm, the filtering algorithm, by Kanungo et al.. They showed that, by storing the data in a kd-tree, it was possible to significantly reduce the running time of k-means. We have adapted this method for the ISOCLUS algorithm. For technical reasons, which are explained later, it is necessary to make a minor modification to the ISOCLUS specification. We provide empirical evidence, on both synthetic and Landsat image data sets, that our algorithm's performance is essentially the same as that of ISOCLUS, but with significantly lower running times. We show that our algorithm runs from 3 to 30 times faster than a straightforward implementation of ISOCLUS. Our adaptation of the filtering algorithm involves the efficient computation of a number of cluster statistics that are needed for ISOCLUS, but not for k-means.
Document ID
20030093575
Acquisition Source
Goddard Space Flight Center
Document Type
Preprint (Draft being sent to journal)
Authors
Memarsadeghi, Nargess
(NASA Goddard Space Flight Center Greenbelt, MD, United States)
Mount, David M.
(Maryland Univ. College Park, MD, United States)
Netanyahu, Nathan S.
(Bar-Ilan Univ. Ramat-Gan, Israel)
LeMoigne, Jacqueline
(NASA Goddard Space Flight Center Greenbelt, MD, United States)
Date Acquired
August 21, 2013
Publication Date
January 1, 2003
Subject Category
Earth Resources And Remote Sensing
Meeting Information
Meeting: IEEE 2003 International Geoscience and Remote Sensing Symposium
Location: Toulouse
Country: France
Start Date: July 21, 2003
End Date: July 25, 2003
Sponsors: Institute of Electrical and Electronics Engineers
Distribution Limits
Public
Copyright
Work of the US Gov. Public Use Permitted.
Document Inquiry

Available Downloads

There are no available downloads for this record.
No Preview Available