The incremental online k-means clustering algorithm and its application to color quantization

Color quantization is a common image processing operation with various applications in computer graphics, image processing, and computer vision. Color quantization is essentially a large-scale combinatorial optimization problem. Many clustering algorithms, both of hierarchical and partitional types, have been applied to this problem since the 1980s. In general, hierarchical color quantization algorithms are faster, whereas partitional ones produce better results provided that they are initialized properly. In this paper, we propose a novel partitional color quantization algorithm based on a binary splitting formulation of MacQueen’s online k-means algorithm. Unlike MacQueen’s original algorithm, the proposed algorithm is both deterministic and free of initialization. Experiments on a diverse set of public test images demonstrate that the proposed algorithm is significantly faster than two popular batch k-means algorithms while yielding nearly identical results. In other words, unlike previously proposed k-means variants, our algorithm addresses both the initialization and acceleration issues of k-means without sacrificing the simplicity of the algorithm. The presented algorithm may be of independent interest as a general-purpose clustering algorithm.