A fast implementation of the ISODATA clustering algorithm

Clustering is central to many image processing and remote sensing applications. isodatais one of the most popular and widely used clustering methods in geoscience applications, but
it can run slowly, particularly with large data sets. We present a more efficient approach to
isodata clustering, which achieves better running times by storing the points in a kd-tree and
through a modification of the way in which the algorithm estimates the dispersion of each
cluster. We also present an approximate version of the algorithm which allows the user to
further improve the running time, at the expense of lower fidelity in computing the nearest
cluster center to each point. We provide both theoretical and empirical justification that our
modified approach produces clusterings that are very similar to those produced by the standard
isodata approach. We also provide empirical studies on both synthetic data and remotely
sensed Landsat and MODIS images that show that our approach has significantly lower running
times.