A Fully Adaptive and Hybrid Method for Image Segmentation Using Multilevel Thresholding

Full Text (PDF, 478KB), PP.46-57

Views: 0 Downloads: 0

Author(s)

Salima Ouadfel 1,* Souham Meshoul 1

1. College of Engineering, MISC laboratory, CICS Group, Department of Computer Science, University Mentouri – Constantine, Algeria

* Corresponding author.

DOI: https://doi.org/10.5815/ijigsp.2013.01.07

Received: 18 Sep. 2012 / Revised: 24 Oct. 2012 / Accepted: 29 Nov. 2012 / Published: 8 Jan. 2013

Index Terms

Image segmentation, Multilevel thresholding, Particle swarm optimization, Simulated annealing

Abstract

High level tasks in image analysis and understanding are based on accurate image segmentation which can be accomplished through multilevel thresholding. In this paper, we propose a new method that aims to determine the number of thresholds as well as their values to achieve multilevel thresholding. The method is adaptive as the number of thresholds is not required as a prior knowledge but determined depending on the used image. The main feature of the method is that it combines the fast convergence of Particle Swarm Optimization (PSO) with the jumping property of simulated annealing to escape from local optima to perform a search in a space the dimensions of which represent the number of thresholds and their values. Only the maximum number of thresholds should be provided and the adopted encoding encompasses a continuous part and a discrete part that are updated through continuous and binary PSO equations. Experiments and comparative results with other multilevel thresholding methods using a number of synthetic and real test images show the efficiency of the proposed method.

Cite This Paper

Salima Ouadfel,Souham Meshoul,"A Fully Adaptive and Hybrid Method for Image Segmentation Using Multilevel Thresholding", IJIGSP, vol.5, no.1, pp.46-57, 2013. DOI: 10.5815/ijigsp.2013.01.07

Reference

[1]Sezgin, M., & Sankur, B.. ‘Survey over image thresholding techniques and quantitative performance’. Journal of Electronic Imaging, (2004) 13 146 – 165.

[2]Kittler, J., & Illingworth, J. Minimum error thresholding. Pattern Recognition, (1986) 19, 41–47.

[3]Wang, S., Chung, F. L., & Xiong, F. A novel image thresholding method based on Parzen window estimate. Pattern Recognition,. (2008) 41, 117–129 

[4]Otsu, N. A threshold selection method from gray level histograms. IEEE Transactions on Systems, Man and Cybernetics SMC-9,. (1979) 62–66 

[5]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 Image Processing(1985),29, 273–28

[6]Yen, P-Y., A fast scheme for multilevel thresholding using genetic algorithms. Signal Processing. (1999) 72 85-95. 

[7]Hammouche, K., Diaf, M., & Siarry, P., A multilevel automatic thresholding method based on a genetic algorithm for a fast image segmentation. Computer Vision Image Understanding. (2008) 109 (2) 163–175. 

[8]Wu, B.-F., Chen, Y.-L., & Chiu, C.-C., Recursive algorithms for image segmentation based on a discriminant criterion, International. Journal. Signal Processing (2004) 1 55–60. 

[9]Huang, D.-Y., & Wang, C.-H. Optimal multi-level thresholding using a two-stage Otsu optimization approach. Pattern Recognition Letters, (2009) 30 (3), 275-284.

[10]Wang, N., Li, X., & Chen, X. H. Fast three-dimensional Otsu thresholding with shuffled frog-leaping algorithm. Pattern Recognition Letters. (2010) 31 (13), 1809–1815 

[11]Li, C. H., & Tam, P. K. S. An iterative algorithm for minimum cross entropy thresholding. Pattern Recognition Letters, (1998) 19 (8), 771-776 

[12]Chung, K.-L., & Tsai, C.-L. Fast incremental algorithm for speeding up the computation of binarization. Applied Mathematics and Computation, (2009) 212 (2), 396-408. 

[13]Yin, P. I Multilevel minimum cross entropy threshold selection based on particle swarm optimization’. Applied Mathematics and Computation. (2007) 184 (2), 503–513. 

[14]Shelokar, P.S., Jayaraman, V.K, & Kulkarni, B.D. An Ant Colony approach for Clustering. Anal. Chim. Acta 59, (2004) pp 187–195 

[15]Goldberg, D.E., Genetic Algorithms in Search, Optimization, and Machine Learning..Addison-Wesley, Reading, MA. (1989)

[16]Kennedy, J & Eberhart, R. C. Particle swarm optimization. In Proc.IEEE Int. Conf. Neural Netw, Perth, Australia,. (1995) 4, 1948–1972 

[17]Storn, R., & Price, K. Differential Evolution — a simple and efficient heuristic for global optimization over continuous spaces. Technical Report TR-95-012.,ICSI. (1995)

[18]Kirkpatrick, S., Gelatt, C.D., & Vecchi, M.P. Optimization by simulated annealing. Science .220 4598, (1983) 71–680. 

[19]Karaboga, D. An idea based on honey bee swarm for numerical optimization, Technical Report TR06, Erciyes University, Engineering Faculty, Computer Engineering Department. (2005)

[20]Passino, K.M., Biomimicry of bacterial foraging for distributed optimization and control. IEEE Transactions on Control Systems Magazine (2002) 22 (3), 52–67.

[21]Lai, C.-C., and Tseng, D.C A hybrid approach using Gaussian smoothing and genetic algorithm for multilevel thresholding. International Journal of Hybrid Intelligent Systems. ., (2004) 13, 143–152.

[22]Srinivas, M., & Patnaik, L.M. Adaptive probabilities of crossover and mutation in genetic algorithms, IEEE Transactions on Systems, Man and Cybernetics (1994) 24 (4). 

[23]Cao,L.,Bao,P.,Shi,Z.,. The strongest schema learning GA and its application to multilevel thresholding Image and Vision Computing 146 (9–10), (2008) 387–390. 

[24]Cuevas, E., Zaldivar, D. & Pérez-Cisneros, M. A novel multi-threshold segmentation approach based on differential evolution optimization. Expert Systems with Applications (2010) 37, 5265-5271. 

[25]Rahnamayan, S., Tizhoosh, H.R., & Salama, M.M.A. Image thresholding using differential evolution. In: Proceedings of International Conference on Image Processing, Computer Vision and Pattern Recognition, Las Vegas, USA, (2006) 244–249. 

[26]Sarkar, S, Gyana RanjanPatra, & Das, S. A Differential Evolution Based Approach for Multilevel Image Segmentation Using Minimum Cross Entropy Thresholding. SEMCCO (2011) 1. 51-58. 

[27]Du, F., Shi, W. K., Chen, L. Z., Deng, Y., & Zhu, Z. Infrared image segmentation with 2-D maximum entropy method based on particle swarm optimization PSO’. Pattern Recognition Letters, (2005) 265, 597–603. 

[28]Madhubanti, M., & Amitava, A. A hybrid cooperative-comprehensive learning based PSO algorithm for image segmentation using multilevel thresholding. Expert Systems with Application, (2008) 34, 1341–1350. 

[29]Ye, Z. W., Chen, H. W., Li, W., & Zhang, J. P.. Automatic threshold selection based on particle swarm optimization algorithm. In Proceedings of international conference on intelligent computation technology and automation. 2008. 36– 39

[30]Zhang, R. & Liu, J. Underwater image segmentation with maximum entropy based on Particle Swarm Optimization PSO. In Proceedings of the first international multi symposiums on computer and computational Sciences IMSCCS’06, (2006). 360–363. 

[31]Horng, M.-H. Multilevel thresholding selection based on the artificial bee colony algorithm for image segmentation. Expert Systems with Applications. (2011) 38, 13785-13791. 

[32]Zhang, Y., & Wu, L. Optimal Multi-Level Thresholding Based on Maximum Tsallis Entropy via an Artificial Bee Colony Approach. Entropy, (2011) 134, 841-859

[33]Sathya, P. D., & Kayalvizhi, R. Modified bacterial foraging algorithm based multilevel thresholding for image segmentation. Engineering Applications of Artificial Intelligence, In Press SEAINPC. (2011) 65–69. 

[34]Hammouche, K., Diaf, M., & Siarry, P. A comparative study of various metaheuristic techniques applied to multilevel thresholding problem. Engineering Applications of Artificial Intelligence, (2010) 23, 667–688. 

[35]Bruzzese, D. & Giani, U. Automatic Multilevel Thresholding Based on a Fuzzy Entropy Measure. In Classification and Multivariate Analysis for Complex Data Structures, (2011) 125-133 

[36]Yen, J.C., Chang, F.J. & Chang, S. A new criterion for automatic multilevel thresholding, IEEE Trans. Image 78. 

[37]Sezgin, M., & Tasaltin, R., A new dichotomization technique to multilevel thresholding devoted to inspection applications, Pattern Recognition. Letters. (2000) 21 151–161.

[38]Djerou, L., Khelil, N., Dehimi, H. E., & Batouche, M. Automatic Multilevel Thresholding Using Binary Particle Swarm Optimization for Image Segmentation. 2009 International Conference of Soft Computing and Pattern Recognition, (2009). 66-71. 

[39]S-Hosseini, H., Intelligent water drops algorithm for automatic multilevel thresholding of grey-level images using a modified Otsu’s criterion. Int. J. Modelling, Identification and Control, (2012) 15, 4, 241 

[40]Al-Obeidat, F, Belacel,N, Carretero, J.A & Mahanti, P. An evolutionary framework using particle swarm optimization for classification method proaftn . Applied Soft Computing (2011) 11 (8) 4971–4980. 

[41]Chen, S. & Luk, B.L. Digital IIR filter design using particle swarm optimisation, International Journal of Modelling, Identification and Control, (2010) 9 (4) 327–335. 

[42]Poli, R, Analysis of the publications on the applications of particle swarm optimisation, Journal of Artificial Evolution

[43]Radha,T., Pant,M., Abraham, A., & Bouvry,P., Swarm Optimization: Hybridization Perspectives and Experimental Illustrations, Applied Maths and Computation, Elsevier Science, Netherlands, (2011) 217 (1) 5208-5226. 

[44]Valdez, F, Melin,P, & Castillo, O. An improved evolutionary method with fuzzy logic for combining particle swarm optimization and genetic algorithms, Applied Soft Computing (2011) 11 (2) 2625–2632. 

[45]Zhang, Y., & Wu, L. Optimal Multi-Level Thresholding Based on Maximum Tsallis Entropy via an Artificial Bee Colony Approach. Entropy, (2011) 134, 841-859

[46]Zhang, Y., Zhang, M. & Liang, Y.C.H. A hybrid Aco/Pso algorithm and its applications, International Journal of Modelling, Identification and Control,(2009) 8 (4) 309–316. 

[47]Shi,Y., & Eberhart, R. C., A modified particle swarm optimizer. In Proceeding IEEE Congr. Evol. Comput., (1998) 69–73. 

[48]Kennedy, J & Eberhart, R. C. A discrete binary version of the particle swarm algorithm, in Procs. of the Conf. on SMC97, Piscataway, NJ, USA, (1997) 4104-4109. 

[49]Chaojun, D., & Qiu, Z., Particle swarm optimization algorithm based on the idea of simulated annealing, International Journal of Computer Science and Network Security, (2006) 6 (10) 152–157. 

[50]Fang, L., Chen,P., & Liu, S. Particle swarm optimization with simulated annealing for tsp, in Proceedings of the 6th WSEAS International Conference on Artificial Intelligence, Knowledge Engineering and Data Bases (AIKED ’07), (2007) 206–210, World Scientific and Engineering Academy and Society (WSEAS), Stevens Point,Wis, USA,

[51]Wang, X., & Li,J Hybrid particle swarm optimization with simulated annealing, in Proceedings of the 3rd International Conference on Machine Learning and Cybernetics (ICMLC ’04), ., (2004) 4 2402–2405. 

[52]Xia, W. J., & Wu, Z. M A hybrid particle swarm optimization approach for the job-shop scheduling problem, International Journal of Advanced Manufacturing Technology, (2006) 29 (3-4), 360–366.

[53]Yang, G., Chen, D., & Zhou, G., A new hybrid algorithm of particle swarm optimization, in Lecture Notes in Computer Science, (2006) 41 15, 50–60.

[54]Metropolis, N., Rosenbluth, A.W., Rosenbluth, M.N., &Teller, A.H. Equation of state calculations by fast computer machines, Journal of Chemical Physics (1953) 21 (6) 1087–1092.