Multilevel Thresholding for Image Segmentation using the Galaxy-based Search Algorithm

Full Text (PDF, 1259KB), PP.19-33

Views: 0 Downloads: 0


Hamed Shah-Hosseini 1,*

1. Freelance researcher, Tehran, Iran

* Corresponding author.


Received: 11 Feb. 2013 / Revised: 3 May 2013 / Accepted: 7 Aug. 2013 / Published: 8 Oct. 2013

Index Terms

Image Segmentation, Thresholding, Metaheuristic, Optimization, OTSU, Chaos


In this paper, image segmentation of gray-level images is performed by multilevel thresholding. The optimal thresholds for this purpose are found by maximizing the between-class variance (the Otsu’s criterion). The optimization (maximization) is conducted by a novel nature-inspired search algorithm, which is called Galaxy-based Search Algorithm or GbSA. The proposed GbSA is a metaheuristic for continuous optimization. It resembles the spiral arms of some galaxies to search for the optimal thresholds. The GbSA also uses a modified Hill Climbing algorithm as a local search. The GbSA also utilizes chaos for improving its performance, which is implemented by the logistic map. Experimental results show that the GbSA finds the optimal or very near optimal thresholds in all runs of the algorithm.

Cite This Paper

Hamed Shah-Hosseini, "Multilevel Thresholding for Image Segmentation using the Galaxy-based Search Algorithm", International Journal of Intelligent Systems and Applications(IJISA), vol.5, no.11, pp.19-33, 2013. DOI:10.5815/ijisa.2013.11.03


[1]E. Zahara, S.K.S. Fan, and D.M. Tsai. Optimal multi-thresholding using a hybrid optimization approach. Pattern Recognition Letters, vol. 26, no. 8, 2005, pp. 1082–1095.

[2]P.Y. Yin. Multilevel minimum cross entropy threshold selection based on particle swarm optimization. Appl. Math. Comput, vol. 184, no. 2, 2007, pp. 503–513.

[3]N.R. Pal, and S.K. Pal. A review on image segmentation techniques. Pattern Recognition, vol. 26, no. 9, 1993, pp. 1277–1294.

[4]N. Otsu. A threshold selection method from gray-level histogram. IEEE Trans. Systems Man Cybern., vol. 9, no. 1, 1979, pp. 62–66.

[5]P.S. Liao, T.S. Chen, and P.C. Chung. A fast algorithm for multi-level thresholding. J. Inf. Sci. Eng., vol. 17, no. 5, 2001, pp. 713–727.

[6]B. Biianu, S. Lee, and S. Das. Adaptive Image Segmentation Using Genetic and Hybrid Search Methods. IEEE Transactions on Aerospace and Electronic Systems, vol. 31, no. 4, 1995, pp. 1268-1291.

[7]L. Cao, P. Bao, and Z.K. Shi. The strongest schema learning GA and its application to multilevel thresholding. Image Vision and Computing, vol. 26, no. 5, 2008, pp. 716–724.

[8]M. Maitra, and A. Chatterjee. A hybrid cooperative–comprehensive learning based PSO algorithm for image segmentation using multilevel thresholding. Expert Systems with Applications, vol. 34, no. 2, 2008, pp. 1341–1350.

[9]H. Gao, W. Xu, J. Sun, and Y. Tang. Multilevel thresholding for image segmentation through an improved quantum-behaved particle swarm algorithm. IEEE Transactions On Instrumentation And Measurement, vol. 59, no. 4, 2010, pp. 934-946.

[10]W.B. Tao, H. Jin, and L.M. Liu. Object segmentation using ant colony optimization algorithm and fuzzy entropy. Pattern Recognition Letters, vol. 28, no. 7, 2008, pp. 788–796.

[11]H. Shah-Hosseini. Intelligent Water Drops algorithm for automatic multilevel thresholding of gray-level images using a modified Otsu’s criterion. International Journal of Modelling, Identification and Control, vol. 15, no. 4, 2012, pp. 241–249.

[12]K. Hammouchea, M. Diaf, and P. Siarry. A comparative study of various meta-heuristic techniques applied to the multilevel thresholding problem. Engineering Applications of Artificial Intelligence, vol. 23, 2010, pp. 676–688.

[13]H. Shah-Hosseini. Otsu’s Criterion-based Multilevel Thresholding by a Nature-inspired Metaheuristic called Galaxy-based Search Algorithm. Third World Congress on Nature and Biologically Inspired Computing (NaBIC’11), October 2011, Salamanca, Spain. 

[14]E.H.L. Aarts and J.K. Lenstra. Local search in combinatorial optimization. In: Discrete Mathematics and Optimization, (Eds.), Wiley, Chichester, UK, 1997. 

[15]M. Sezgin and B. Sankur. Survey over image thresholding techniques and quantitative performance evaluation. Journal of Electronic Imaging, vol 13, no 1, 2004, pp. 146–165.

[16]T.W. Ridler and S. Calvard. Picture thresholding using an iterative selection method. IEEE Trans. Systems, Man, and Cybernetics, vol. 8, no. 8, 1978, pp. 630-632.

[17]H. Shah-Hosseini and R. Safabakhsh. TASOM: a new time adaptive self-organizing map. IEEE Transactions on Systems, Man and Cybernetics—Part B, vol. 33, no. 2, 2003, pp. 271–28. 

[18]H. Shah-Hosseini and R. Safabakhsh. Automatic multilevel thresholding for image segmentation by the growing time adaptive self-organizing map. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 24, no. 10, 2002, pp. 1388–1393. 

[19]Y.J. Zhang. A survey on evaluation methods for image segmentation. Pattern Recognition, vol. 29, no. 8, 1996, pp. 1335-1346.

[20]J.F. Canny. A computational approach to edge detection. IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 8, no. 6, 1986, pp. 667-698.

[21]D.Y. Huang and C.H. Wang. Optimal multi-level thresholding using a two-stage Otsu optimization approach. Pattern Recognition Letters, vol. 30, no. 3, 2009, pp. 275–284.

[22]N. Mladenovic, and P. Hansen. Variable neighborhood search. Computers Operational Research, 1997, vol. 24, 1097-1100.

[23]H.R. Lourenço, O. Martin and T. Stützle. Iterated Local Search. Handbook of Metaheuristics. Kluwer Academic Publishers, International Series in Operations Research & Management Science, vol. 57, 2003, pp. 321–353.

[24]N. Krasnogor and J. Smith. A tutorial for competent memetic algorithms: model, taxonomy, and design issues. IEEE Transactions on Evolutionary Computation, vol. 9, no. 5, 2005, pp. 474–488.

[25]J. Holland. Adaptation in natural and artificial systems. Ann Arbor: University of Michigan Press, 1975.

[26]E. Ott, Chaos in Dynamical Systems, Cambridge, 2002.

[27]USC-SIPI Image Database, 2012. Available at:

[28]H. Shah-Hosseini. Principal components analysis by the galaxy-based search algorithm: a novel metaheuristic for continuous optimization. International Journal of Computational Science and Engineering, vol. 6, no.1/2, 2011, pp. 132 – 140.