K-Means Cluster Analysis for Image Segmentation

Abstract

Does K-Means reasonably divides the data into k groups is an important question that arises when one works on Image Segmentation? Which color space one should choose and how to ascertain that the k we determine is valid? The purpose of this study was to explore the answers to aforementioned questions. We perform K-Means on a number of 2-cluster, 3-cluster and k-cluster color images (k>3) in RGB and L*a*b* feature space. Ground truth (GT) images have been used to accomplish validation task. Silhouette analysis supports the peaks for given k-cluster image. Model accuracy in RGB space falls between 30% and 55% while in L*a*b* color space it ranges from 30% to 65%. Though few images used, but experimentation proves that K-Means significantly segment images much better in L*a*b* color space as compared to RGB feature space.

References

• L. Lucchese, S. K. Mitra, "Color Image Segmentation: A State of the Art Survey," (invited paper), Image Processing, Vision and Pattern Recognition, Proc. of Indian National Science Academy, vol. 67, A, No. 2, pp. 207-221, March-2001.
• H. D. Cheng , X. H. Jiang , Y. Sun , Jing Li Wang, "Color image segmentation: Advances and prospects (2001)",Pattern Recognition, 34, 2001, 2259 - 2281
• W. Skarbek, A. Koschan, "Colour Image Segmentation- A Survey", Technical Report 94-32, Technical University Berlin, October. 1994
• K. S. Fu, J. K. Mui,"A Survey on Image Segmentation," Pattern Recognition, Vol. 14, pp. 3-16, 1981.
• N. R. Pal and S. K. Pal, "A Review on Image Segmentation Techniques," Pattern Recognition, Vol26, No. 9, pp. 1277-1294, 1993.
• Haralick, R. M. and Shapiro, L. G. , Survey: "Image Segmentation Techniques". CVGIP, vol. 29, 1985,pp. 100-132.
• G. B. Coleman and H. C. Andrews "Image segmentation by clustering", Proc. IEEE, vol. 67, pp. 773 -785 1979
• Lloyd SP "Least squares quantization in PCM. Unpublished Bell Lab. Tech. Note, portions presented at the Institute of Mathematical statistics Meeting Atlantic City, NJ, sep. 1957.
• MacQueen, J. (1967) "Some methods for classification and analysis of multivariate observations". In Proc. 5th Symp. Math Statist Prob (pp. 281–297).
• Arthur Dempster, Nan Laird, and Donald Rubin. "Maximum likelihood from incomplete data via the EM algorithm". Journal of the Royal Statistical Society, Series B, 39(1):1–38, 1977
• C. M. Bishop, Neural Networks for Pattern Recognition, Oxford University Press, New York, 1996
• G. McLachlan and D. Peel, Finite Mixture Models, John Wiley & Sons, Brisbane, 2001.
• P. Haim, F. Joseph, and J. Ian, "A study of Gaussian mixture models for color and texture features for image classification and segmentation," Pattern Recognition, vol 39, no. 4, pp. 695-706, 2006.
• J. K. Udupa, S. Samarasekera, "Fuzzy connectedness and object definition: theory, algorithm and applications in image segmentation, Graph. Models Image Process", 58(3) (1996) 246–261.
• S. M. Yamany, A. A. Farag and S. Hsu, "A fuzzy hyperspectral classifier for automatic target recognition (ATR) systems", Pattern Recognit. Lett. , 20 (1999)1431–1438
• G. C. Karmakar and L. S. Dooley, "A generic fuzzy rule based image segmentation algorithm", Pattern Recognition Letters, 23(10) (2002) 1215-1227
• W. Woelker, "Image Segmentation Based on an Adaptive 3D Analysis of the CIE-L*a*b* Color Space," Proc. of SPIE'96- Visual communications and Image Processing '96, Vol. 2727, pp. 1197-1203, 1996
• D. Comaniciu, P. Meer, "Robust Analysis of Feature Spaces:Color ImageSegmentation," Proc. of CVPR'97, pp. 750-755
• H. D. Cheng and Y. Sun, "A hierarchical approach to color image segmentation using homogeneity", IEEE Transactions on Image Processing 9 (12) (2000)2071–2082
• Yonghong Zhang , "EM algorithm with improvement for color image segmentation in multiple color spaces", Electronics, Communications and Control (ICECC), 2011, pp. 853 - 857
• L. Lucchese and S. K. Mitra, "Unsupervised segmentation of color images based on K-Means clustering in the chromaticity plane", Proc. of Content-based access of image and video libraries, pp. 74-78, 1999.
• Chi zhang, P. Wang, A New Method of Color Image Segmentation Based on Intensity and Hue Clustering, volume 3 2002.
• Tse-Wei Chen , Yi-Ling Chen and Shao-Yi Chien (2010), "Fast Image Segmentation Based on K-Means Clustering with Histograms in HSV Color Space," Journal of Scientific Research ISSN I452-2I6X Vol. 44 No. 2, pp. 337-35 I
• F. Gibou and R. Fedkiw, "A fast hybrid K-Means level set algorithm for segmentation," in Proc. 4th Annu. Hawaii Int. Conf. Stat. Math. , 2005,pp. 281–291.
• De Montréal, "A De-Texturing and Spatially Constrained K-Means Approach for Image Segmentation Max Mignotte", ELSEVIER, Pattern Recognition Letters 32 (2011) pp. 359-367.
• Ethem Alpaydin, "Introduction to Machine Learning", MIT Press, 2004.
• L. Kaufman and P. J. Rousseeuw. Finding groups in data: an introduction to cluster analysis. John Wiley and Sons, New York, 1990.
• Provost Foster J. , Fawcett Tom, and Kohavi Ron, "The case against accuracy estimation for comparing induction algorithms". Proceedings of the Fifteenth International Conference on Machine Learning, Morgan Kaufmann Publishers Inc , pages 445–453,1998.
• T. Fawcett, "ROC Graphs: Notes and Practical Considerations for Researchers",Intelligent Enterprise Technologies Laboratory, 2004.
• M. Zweig and G. Campbell, "Receiver-Operating Characteristic (ROC) Plots: A Fundamental Evaluation Tool in Clinical Medicine", Clin. Chem. 39/4, 561-577, 1993.
• Borenstein and J. Malik. Shape guided object segmentation. In IEEE Conference on Computer Vision and Pattern Recognition, 2006.
• E. Borenstein, E. Sharon, and S. Ullman. Combining top-down and bottom-up segmentation. In Proceedings of the 2004 Conference on Computer Vision and Pattern Recognition Workshop (CVPRW'04).
• E. Borenstein and S. Ullman. Class-speci?c, top- down segmentation. In European Conference on Computer Vision, 2002.
• D. Martin, C. Fowlkes, D. Tal, and J. Malik, "A Database of Human Segmented Natural Images and Its Application to Evaluating Segmentation Algorithms and Measuring Ecological Statistics," Proc. IEEE Eighth Int'l Conf. Computer Vision, pp. 416-423, July 2001.
• http://www. wisdom. weizmann. ac. il/~vision/Seg_Evaluation_DB/index. html

Index Terms

Keywords