Multilevel minimum cross entropy threshold selection based on particle swarm optimization. (English) Zbl 1119.94004

Summary: Thresholding is one of the popular and fundamental techniques for conducting image segmentation. Many thresholding techniques have been proposed in the literature. Among them, the minimum cross entropy thresholding (MCET) have been widely adopted. Although the MCET method is effective in the bilevel thresholding case, it could be very time-consuming in the multilevel thresholding scenario for more complex image analysis. This paper first presents a recursive programming technique which reduces an order of magnitude for computing the MCET objective function. Then, a particle swarm optimization (PSO) algorithm is proposed for searching the near-optimal MCET thresholds. The experimental results manifest that the proposed PSO-based algorithm can derive multiple MCET thresholds which are very close to the optimal ones examined by the exhaustive search method. The convergence of the proposed method is analyzed mathematically and the results validate that the proposed method is efficient and is suited for real-time applications.


94A08 Image processing (compression, reconstruction, etc.) in information and communication theory
90C59 Approximation methods and heuristics in mathematical programming
Full Text: DOI


[1] Abutaleb, A.S., Automatic thresholding of gray-level pictures using two-dimensional entropy, Computer vision graphics and image processing, 47, 22-32, (1989)
[2] Brink, A.D.; Pendock, N.E., Minimum cross-entropy threshold selection, Pattern recognition, 29, 179-188, (1996)
[3] Cheng, H.D.; Chen, J.R.; Li, J.G., Threshold selection based on fuzzy c-partition entropy approach, Pattern recognition, 31, 857-870, (1998)
[4] Clerc, M.; Kennedy, J., The particle swarm explosion, stability, and convergence in a multidimensional complex space, IEEE transaction on evolutionary computation, 6, 58-73, (2002)
[5] M. Dorigo, Optimization, learning, and natural algorithms, Ph.D. Thesis, Dip. Elettronica e Informazione, Politecnico di Milano, Italy, 1992.
[6] R.C. Eberhart, Y. Shi, Evolving artificial neural networks, in: Proc. Int’l. Conf. on Neural Networks and Brain, PL5-PL13, 1998.
[7] Glover, F., Tabu search – part I, ORSA journal of computing, 1, 190-206, (1989) · Zbl 0753.90054
[8] Goldberg, D.E., Genetic algorithms in search, optimization, and machine learning, (1997), Addison Wesley Reading, MA
[9] Kapur, J.N.; Sahoo, P.K.; Wong, A.K.C., A new method for gray-level picture thresholding using the entropy of the histogram, Computer vision graphics and image processing, 29, 273-285, (1985)
[10] J. Kennedy, R.C. Eberhart, Particle swarm optimization, in: Proc. IEEE Int’l. Conf. on Neural Networks, vol. IV, 1995, pp. 1942-1948.
[11] Kirkpatrick, S.; Gelatt, C.; Vecchi, M., Optimization by simulated annealing, Science, 220, 671-680, (1983) · Zbl 1225.90162
[12] Kittler, J.; Illingworth, J., Minimum error thresholding, Pattern recognition, 19, 41-47, (1986)
[13] Kullback, S., Information theory and statistics, (1968), Dover New York · Zbl 0149.37901
[14] Kurugollu, F.; Sankur, B.; Harmanci, A.E., Color image segmentation using histogram multithresholding and fusion, Image and vision computing, 19, 915-928, (2001)
[15] Lee, S.U.; Chung, S.Y.; Park, R.H., A comparative performance study of several global thresholding techniques for segmentation, Computer vision graphics and image processing, 52, 171-190, (1990)
[16] Li, C.H.; Lee, C.K., Minimum cross entropy thresholding, Pattern recognition, 26, 617-625, (1993)
[17] Li, C.H.; Tam, P.K.S., An iterative algorithm for minimum cross entropy thresholding, Pattern recognition letters, 19, 771-776, (1998) · Zbl 0908.68065
[18] Lim, Y.K.; Lee, S.U., On the color image segmentation algorithm based on the thresholding and the fuzzy c-means techniques, Pattern recognition, 23, 935-952, (1990)
[19] Otsu, N., A threshold selection method from gray-level histograms, IEEE transactions on systems man and cybernetics, SMC-9, 62-66, (1979)
[20] Pal, N.R., On minimum cross-entropy thresholding, Pattern recognition, 29, 575-580, (1996)
[21] Papamarkos, N.; Strouthopoulos, C.; Andreadis, I., Multithresholding of color and gray-level images through a neural network technique, Image and vision computing, 18, 213-222, (2000)
[22] Parsopoulos, K.E.; Vrahatis, M.N., Recent approaches to global optimization problems through particle swarm optimization, Natural computing, 1, 235-306, (2002) · Zbl 1018.68063
[23] Pun, T., Entropy thresholding: A new approach, Computer vision graphics and image processing, 16, 210-239, (1981)
[24] Rosenfeld, A.; De la Torre, P., Histogram concavity analysis as an aid in threshold selection, IEEE transactions on systems man and cybernetics, SMC-13, 231-235, (1983)
[25] Sahoo, P.K.; Soltani, S.; Wong, A.K.C.; Chen, Y.C., A survey of thresholding techniques, Computer vision graphics and image processing, 41, 233-260, (1988)
[26] Sahoo, P.K.; Wilkins, C.; Yeager, J., Threshold selection using renyi’s entropy, Pattern recognition, 30, 71-84, (1997) · Zbl 1121.94302
[27] Sankur, B.; Sezgin, M., Survey over image thresholding techniques and quantitative performance evaluation, Journal of electronic imaging, 13, 146-165, (2004)
[28] Shigenori, N.; Takamu, G.; Toshiku, Y.; Yoshikazu, F., A hybrid particle swarm optimization for distribution state estimation, IEEE transaction on power systems, 18, 60-68, (2003)
[29] Strouthopoulos, C.; Papamarkos, N., Multithresholding of mixed-type documents, Engineering applications of artificial intelligence, 13, 323-343, (2000)
[30] V. Tandon, Closing the gap between CAD/CAM and optimized CNC end milling, Master thesis, Purdue School of Engineering and Technology, Indiana University Purdue University Indianapolis, 2000.
[31] Trelea, I.C., The particle swarm optimization algorithm: convergence analysis and parameter selection, Information processing letters, 85, 317-325, (2003) · Zbl 1156.90463
[32] Yen, J.C.; Chang, F.J.; Chang, S., A new criterion for automatic multilevel thresholding, IEEE transactions on image processing, IP-4, 370-378, (1995)
[33] Yin, P.Y.; Chen, L.H., New method for multilevel thresholding using the symmetry and duality of the histogram, Journal of electronic imaging, 2, 337-344, (1993)
[34] Yin, P.Y., A discrete particle swarm algorithm for optimal polygonal approximation of digital curves, Journal of visual communication and image representation, 15, 241-260, (2004)
[35] H. Yoshida, K. Kawata, Y. Fukuyama, Y. Nakanishi, A particle swarm optimization for reactive power and voltage control considering voltage stability, in: Proc. Int’l. Conf. on Intelligent System Application to Power Systems, 1999, pp. 117-121.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.