Color quantization is an important operation with numerous applications in graphics and image processing. Most quantization methods are essentially based on data clustering algorithms. However, despite its popularity as a general purpose clustering algorithm, K-means has not received much respect in the color quantization literature because of its high computational requirements and sensitivity to initialization. In this paper, a fast color quantization method based on K-means is presented. The method involves several modifications to the conventional (batch) K-means algorithm, including data reduction, sample weighting, and the use of the triangle inequality to speed up the nearest-neighbor search. Experiments on a diverse set of images demonstrate that, with the proposed modifications, K-means becomes very competitive with state-of-the-art color quantization methods in terms of both effectiveness and efficiency.
© 2009 Optical Society of America
Original Manuscript: April 22, 2009
Revised Manuscript: July 24, 2009
Manuscript Accepted: August 15, 2009
Published: October 27, 2009
M. Emre Celebi, "Fast color quantization using weighted sort-means clustering," J. Opt. Soc. Am. A 26, 2434-2443 (2009)