OSA's Digital Library

Journal of the Optical Society of America A

Journal of the Optical Society of America A

| OPTICS, IMAGE SCIENCE, AND VISION

  • Editor: Stephen A. Burns
  • Vol. 26, Iss. 11 — Nov. 1, 2009
  • pp: 2434–2443

Fast color quantization using weighted sort-means clustering

M. Emre Celebi  »View Author Affiliations


JOSA A, Vol. 26, Issue 11, pp. 2434-2443 (2009)
http://dx.doi.org/10.1364/JOSAA.26.002434


View Full Text Article

Enhanced HTML    Acrobat PDF (1763 KB)





Browse Journals / Lookup Meetings

Browse by Journal and Year


   


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools

Share
Citations

Abstract

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

OCIS Codes
(100.2000) Image processing : Digital image processing
(100.5010) Image processing : Pattern recognition

ToC Category:
Image Processing

History
Original Manuscript: April 22, 2009
Revised Manuscript: July 24, 2009
Manuscript Accepted: August 15, 2009
Published: October 27, 2009

Citation
M. Emre Celebi, "Fast color quantization using weighted sort-means clustering," J. Opt. Soc. Am. A 26, 2434-2443 (2009)
http://www.opticsinfobase.org/josaa/abstract.cfm?URI=josaa-26-11-2434


Sort:  Author  |  Year  |  Journal  |  Reset  

References

  1. L. Brun and A. Trémeau, Digital Color Imaging Handbook (CRC Press, 2002), pp. 589-638.
  2. C.-K. Yang and W.-H. Tsai, “Color image compression using quantization, thresholding, and edge detection techniques all based on the moment-preserving principle,” Pattern Recogn. Lett. 19, 205-215 (1998). [CrossRef]
  3. Y. Deng and B. Manjunath, “Unsupervised segmentation of color-texture regions in images and video,” IEEE Trans. Pattern Anal. Mach. Intell. 23, 800-810 (2001). [CrossRef]
  4. O. Sertel, J. Kong, G. Lozanski, A. Shanaah, U. Catalyurek, J. Saltz, and M. Gurcan, “Texture classification using nonlinear color quantization: application to histopathological image analysis,” in IEEE International Conference on Acoustics, Speech and Signal Processing 2008, ICAASP 2008 (IEEE, 2008), pp. 597-600. [CrossRef]
  5. C.-T. Kuo and S.-C. Cheng, “Fusion of color edge detection and color quantization for color image watermarking using principal axes analysis,” Pattern Recogn. 40, 3691-3704 (2007). [CrossRef]
  6. Y. Deng, B. Manjunath, C. Kenney, M. Moore, and H. Shin, “An efficient color representation for image retrieval,” IEEE Trans. Image Process. 10, 140-147 (2001). [CrossRef]
  7. Z. Xiang, “Color quantization,” in Handbook of Approximation Algorithms and Metaheuristics (Chapman & Hall/CRC, 2007), pp. 86-1-86-17. [CrossRef]
  8. R. S. Gentile, J. P. Allebach, and E. Walowit, “Quantization of color images based on uniform color spaces,” J. Electron. Imaging 16, 11-21 (1990).
  9. P. Heckbert, “Color image quantization for frame buffer display,” ACM SIGGRAPH Comput. Graph. 16, 297-307 (1982). [CrossRef]
  10. M. Gervautz and W. Purgathofer, “A simple method for color quantization: octree quantization,” in New Trends in Computer Graphics (Springer-Verlag, 1988), pp. 219-231. [CrossRef]
  11. S. Wan, P. Prusinkiewicz, and S. Wong, “Variance-based color image quantization for frame buffer display,” Color Res. Appl. 15, 52-58 (1990). [CrossRef]
  12. M. Orchard and C. Bouman, “Color quantization of images,” IEEE Trans. Signal Process. 39, 2677-2690 (1991). [CrossRef]
  13. X. Wu, “Efficient statistical computations for optimal color quantization,” in Graphics Gems Volume II (Academic, 1991), pp. 126-133.
  14. G. Joy and Z. Xiang, “Center-cut for color image quantization,” Visual Comput. 10, 62-66 (1993). [CrossRef]
  15. C.-Y. Yang and J.-C. Lin, “RWM-cut for color image quantization,” Comput. Graph. 20, 577-588 (1996). [CrossRef]
  16. S. Cheng and C. Yang, “Fast and novel technique for color quantization using reduction of color space dimensionality,” Pattern Recogn. Lett. 22, 845-856 (2001). [CrossRef]
  17. Y. Sirisathitkul, S. Auwatanamongkol, and B. Uyyanonvara, “Color image quantization using distances between adjacent colors along the color axis with highest color variance,” Pattern Recogn. Lett. 25, 1025-1043 (2004). [CrossRef]
  18. K. Kanjanawanishkul and B. Uyyanonvara, “Novel fast color reduction algorithm for time-constrained applications,” J. Visual Commun. Image Represent 16, 311-332 (2005). [CrossRef]
  19. W. H. Equitz, “A new vector quantization clustering algorithm,” IEEE Trans. Acoust., Speech, Signal Process. 37, 1568-1575 (1989). [CrossRef]
  20. R. Balasubramanian and J. Allebach, “A new approach to palette selection for color images,” J. Electron. Imaging 17, 284-290 (1991).
  21. Z. Xiang and G. Joy, “Color image quantization by agglomerative clustering,” IEEE Comput. Graphics Appl. 14, 44-48 (1994). [CrossRef]
  22. L. Velho, J. Gomez, and M. Sobreiro, “Color image quantization by pairwise clustering,” in X Brazilian Symposium on Computer Graphics and Image Processing 1977 (IEEE Computer Society, 1997), pp. 203-210. [CrossRef]
  23. L. Brun and M. Mokhtari, “Two high speed color quantization algorithms,” in Proceedings of the First International Conference on Color in Graphics and Image Processing (IEEE, 2000), pp. 116-121.
  24. H. Kasuga, H. Yamamoto, and M. Okamoto, “Color quantization using the fast K-means algorithm,” Syst. Comput. Jpn. 31, 33-40 (2000). [CrossRef]
  25. Y.-L. Huang and R.-F. Chang, “A fast finite-state algorithm for generating RGB palettes of color quantized images,” J. Inf. Sci. Eng. 20, 771-782 (2004).
  26. Y.-C. Hu and M.-G. Lee, “K-means based color palette design scheme with the use of stable flags,” J. Electron. Imaging 16, 033003 (2007). [CrossRef]
  27. Y.-C. Hu and B.-H. Su, “Accelerated K-means clustering algorithm for colour image quantization,” Imaging Sci. J. 56, 29-40 (2008). [CrossRef]
  28. Z. Xiang, “Color image quantization by minimizing the maximum intercluster distance,” ACM Trans. Graphics 16, 260-276 (1997). [CrossRef]
  29. O. Verevka and J. Buchanan, “Local K-means algorithm for colour image quantization,” in Proceedings of the Graphics/Vision Interface Conference (ACM, 1995), pp. 128-135.
  30. P. Scheunders, “Comparison of clustering algorithms applied to color image quantization,” Pattern Recogn. Lett. 18, 1379-1384 (1997). [CrossRef]
  31. M. E. Celebi, “An effective color quantization method based on the competitive learning paradigm,” in Proceedings of the International Conference on Image Processing, Computer Vision, and Pattern Recognition (2009), pp. 876-880.
  32. D. Ozdemir and L. Akarun, “Fuzzy algorithm for color quantization of images,” Pattern Recogn. 35, 1785-1791 (2002). [CrossRef]
  33. G. Schaefer and H. Zhou, “Fuzzy clustering for colour reduction in images,” Telecommun. Syst. 40, 17-25 (2009). [CrossRef]
  34. Z. Bing, S. Junyi, and P. Qinke, “An adjustable algorithm for color quantization,” Pattern Recogn. Lett. 25, 1787-1797 (2004). [CrossRef]
  35. A. Dekker, “Kohonen neural networks for optimal colour quantization,” Network Comput. Neural Syst. 5, 351-367 (1994). [CrossRef]
  36. N. Papamarkos, A. Atsalakis, and C. Strouthopoulos, “Adaptive color reduction,” IEEE Trans. Syst., Man, Cybern., Part B: Cybern. 32, 44-56 (2002). [CrossRef]
  37. C.-H. Chang, P. Xu, R. Xiao, and T. Srikanthan, “New adaptive color quantization method based on self-organizing maps,” IEEE Trans. Neural Netw. 16, 237-249 (2005). [CrossRef] [PubMed]
  38. Y. Linde, A. Buzo, and R. Gray, “An algorithm for vector quantizer design,” IEEE Trans. Commun. 28, 84-95 (1980). [CrossRef]
  39. G. Gan, C. Ma, and J. Wu, Data Clustering: Theory, Algorithms, and Applications (SIAM, 2007). [CrossRef]
  40. P. Drineas, A. Frieze, R. Kannan, S. Vempala, and V. Vinay, “Clustering large graphs via the singular value decomposition,” Mach. Learn. 56, 9-33 (2004). [CrossRef]
  41. S. Lloyd, “Least squares quantization in PCM,” IEEE Trans. Inf. Theory 28, 129-136 (1982). [CrossRef]
  42. E. Forgy, “Cluster analysis of multivariate data: efficiency vs. interpretability of classification,” Biometrics 21, 768 (1965).
  43. S. Phillips, “Acceleration of K-means and related clustering algorithms,” in Proceedings of the 4th International Workshop on Algorithm Engineering and Experiments (2002), pp. 166-177.
  44. T. Kanungo, D. Mount, N. Netanyahu, C. Piatko, R. Silverman, and A. Wu, “An efficient K-means clustering algorithm: analysis and implementation,” IEEE Trans. Pattern Anal. Mach. Intell. 24, 881-892 (2002). [CrossRef]
  45. S. Har-Peled and A. Kushal, “Smaller coresets for K-median and K-means clustering,” in Proceedings of the 21st Annual Symposium on Computational Geometry (2004), pp. 126-134.
  46. C. Elkan, “Using the triangle inequality to accelerate K-means,” in Proceedings of the 20th International Conference on Machine Learning (2003), pp. 147-153.
  47. J. C. Bezdek, Pattern Recognition with Fuzzy Objective Function Algorithms (Springer-Verlag, 1981).
  48. J. F. Kolen and T. Hutcheson, “Reducing the time complexity of the fuzzy C-means algorithm,” IEEE Trans. Fuzzy Syst. 10, 263-267 (2002). [CrossRef]
  49. Uncompressed full-resolution images are available at http://www.lsus.edu/faculty/~ecelebi/color_quantization.htm.

Cited By

Alert me when this paper is cited

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.

Figures

Fig. 1 Fig. 2 Fig. 3
 
Fig. 4
 

« Previous Article  |  Next Article »

OSA is a member of CrossRef.

CrossCheck Deposited