Abstract
In this paper we present a method based on the k-means algorithm for multilevel thresholding of grayscale images. The clustering is computed over the histogram rather than on the full list of intensity levels. Our implementation runs in linear time per iteration proportional to the number of bins of the histogram, not depending on the size of the image nor on the number of clusters/levels as in a traditional implementation. Therefore, it is possible to get a large speedup when the number of bins of the histogram is significantly shorter than the number of pixels. In order to achieve that running time, two restrictions were exploited in our implementation: (I) we target only grayscale images and (II) thresholding does not use spatial information.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
MacQueen, J., et al.: Some methods for classification and analysis of multivariate observations. In: Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, California, USA, vol. 1, p. 14 (1967)
Otsu, N.: A threshold selection method from gray-level histograms. IEEE Transactions on Systems, Man and Cybernetics 9(1), 62–66 (1979)
Tsai, D.M., Chen, Y.H.: A fast histogram-clustering approach for multi-level thresholding. Pattern Recognition Letters 13(4), 245–252 (1992)
Tsai, W.H.: Moment-preserving thresolding: A new approach. Computer Vision, Graphics, and Image Processing 29(3), 377–393 (1985)
Yen, J.C., Chang, F.J., Chang, S.: A new criterion for automatic multilevel thresholding. IEEE Transactions on Image Processing 4(3), 370–378 (1995)
Wang, S., Haralick, R.M.: Automatic multithreshold selection. Computer Vision, Graphics, and Image Processing 25(1), 46–67 (1984)
Sahoo, P., Soltani, S., Wong, A.: A survey of thresholding techniques. Computer Vision, Graphics, and Image Processing 41(2), 233–260 (1988)
Liu, D., Yu, J.: Otsu method and k-means. In: Ninth International Conference on Hybrid Intelligent Systems, HIS 2009, vol. 1, pp. 344–349 (August 2009)
Ng, H.P., Ong, S.H., Foong, K.W.C., Goh, P.S., Nowinski, W.: Medical image segmentation using k-means clustering and improved watershed algorithm. In: 2006 IEEE Southwest Symposium on Image Analysis and Interpretation, pp. 61–65 (2006)
Pham, D.L., Xu, C., Prince, J.L.: Current methods in medical image segmentation 1. Annual Review of Biomedical Engineering 2(1), 315–337 (2000)
Soares, F., Catalao, J., Nico, G.: Using k-means and morphological segmentation for intertidal flats recognition. In: 2012 IEEE International Geoscience and Remote Sensing Symposium (IGARSS), pp. 764–767 (July 2012)
Bishop, C.M., et al.: Pattern recognition and machine learning, vol. 1. Springer, New York (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Fonseca, P., Wainer, J. (2014). A Linear Time Implementation of k-Means for Multilevel Thresholding of Grayscale Images. In: Bayro-Corrochano, E., Hancock, E. (eds) Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications. CIARP 2014. Lecture Notes in Computer Science, vol 8827. Springer, Cham. https://doi.org/10.1007/978-3-319-12568-8_15
Download citation
DOI: https://doi.org/10.1007/978-3-319-12568-8_15
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-12567-1
Online ISBN: 978-3-319-12568-8
eBook Packages: Computer ScienceComputer Science (R0)