Abstract
Multilevel image thresholding plays a crucial role in analyzing and interpreting the digital images. Previous studies revealed that classical exhaustive search techniques are time consuming as the number of thresholds increased. To solve the problem, many nature-inspired algorithms (NAs) which can produce high-quality solutions in reasonable time have been utilized for multilevel thresholding. This chapter discusses three typical kinds of NAs and their hybridizations in solving multilevel image thresholding. Accordingly, a novel hybrid algorithm of gravitational search algorithm (GSA) with genetic algorithm (GA), named GSA-GA, is proposed to explore optimal threshold values efficiently. The chosen objective functions in this chapter are Kapur’s entropy and Otsu criteria. This chapter conducted experiments on two well-known test images and two real satellite images using various numbers of thresholds to evaluate the performance of different NAs.
Access provided by Autonomous University of Puebla. Download chapter PDF
Similar content being viewed by others
Keywords
- Image segmentation
- Multilevel thresholding
- Nature-inspired algorithms (NAs)
- Gravitational search algorithm (GSA)
- Genetic algorithm (GA)
- Kapur’s entropy
- Otsu
1 Introduction
For the analysis, interpretation, and understanding of digital images, segmentation is one of the most essential and fundamental technologies [1]. It is useful for partitioning a digital image into multiple regions/objects with distinct gray-levels [2]. Over the several decades, three main categories in image segmentation have been exploited in the literatures: (1) edge-based image segmentation, (2) region-based image segmentation, and (3) special theory-based image segmentation. Detailed introduction of their properties are presented in [3]. Particularly, thresholding technique of the region-based segmentation is regard as the most popular one out of others [4]. The main purpose of image thresholding is to determine one (bi-level thresholding) or m ( multilevel thresholding) appropriate threshold values for an image to divide pixels of the image into different groups [5, 6]. In the recent years, increasing complexity of digital images, such as intensity inhomogeneity, makes multilevel thresholding approaches drawn much more attention. This is mainly due to its easy implementation and low storage memory characteristic [7].
Generally, the multilevel thresholding transforms the image segmentation to an optimization problem where the appropriate threshold values are found by maximizing or minimizing a criterion. For example, in the popular Otsu’s method [8], thresholds are determined by maximizing the between-class variance. In the Kapur’s entropy [9], the optimum thresholds are achieved by maximizing the entropy of different classes. A fuzzy entropy measure is applied for picking the optimum thresholds in [10] while Qiao et al. [11] formulated the thresholding criterion by exploring the knowledge in terms of intensity contrast. Researches have also developed some other preferable criteria, including fuzzy similarity measure [12], Bayesian error [13], cross entropy [14], Tsallis entropy [15], and so on.
Exhaustive search algorithms achieved optimization of the aforementioned criteria. However, the methods will become quiet time consuming if the number of desired thresholds is increased [16]. Moreover, the exhaustive search algorithms prone to premature convergence when dealing with complex real life images [17–19]. Nature-inspired algorithms (NAs) possess the ability for searching the optimal solutions on the basis of any objective function [7]. Furthermore, the population-based nature of NAs allows the generation of several candidate thresholds in a single run [20]. The population-based nature of NAs thus remarkably reduces the computational time of multilevel thresholding. Consequently, many NAs have been preferred in finding optimum thresholds for image thresholding.
The NAs can be categorized into three typical kinds: swarm intelligence algorithms (SIAs), evolutionary algorithms (EAs), and physics-based algorithms (PAs) in accordance with their original inspirations. Popular NAs chosen for multilevel thresholding include genetic algorithm (GA) [8, 21–24], differential evolution (DE) [18, 25–27], simulated annealing (SA) [16, 28], ant colony optimization (ACO) [29, 30], artificial bee colony optimization (ABC) [17, 31], differential search algorithm (DS) [16, 32], particle swarm optimization (PSO) [17, 33–35], and so on. Generally speaking, all these algorithms have achieved certain successes and have showed different advantages. For example, DE achieves higher quality of the optimal thresholds than GA, PSO, ACO, and SA whereas PSO converges the most quickly when comparing with ACO, GA, DE, and SA [21]. Besides, the DS consumes the shortest running time for multilevel color image thresholding when comparing with DE, GA, PSO, ABC, etc. [16].
Moreover, to further improve the optimization ability of these NAs, large amounts of variants, such as hybrid algorithms have been proposed. Many of the hybrid algorithms have been utilized in solving multilevel thresholding problems, including GAPSO (hybrid GA with PSO) [36, 37], ACO/PSO (hybrid ACO with PSO) [38], SA/PSO (hybrid SA with PSO) [39], BBO-DE (hybrid DE with biogeography-based optimization (BBO)) [40] etc. It is demonstrated that these hybrid algorithms can always perform more effective search ability than the original ones. But simple hybrid model easily causes high-computational complexity.
Therefore, in this chapter, we developed a novel hybrid algorithm of GSA with GA ( GSA-GA) for multilevel thresholding. The proposed GSA-GA is expected to rapidly obtain the high-quality optimal thresholds. In GSA-GA, the discrete mutation operator [41] is introduced to promote the population diversity when premature convergence occurred. Moreover, for selecting the particles for mutation, the roulette selection [42] is also introduced. The introduction of these operators therefore could promote GSA-GA to perform faster and more accurate multilevel image thresholding. Both Kapur’s entropy and Otsu are considered as evaluation criteria for GSA-GA.
Section 2 formulates the multilevel thresholding problem as an optimization problem first and then introduces two criteria briefly. In Sect. 3, typical NAs and hybrid NAs based multilevel image thresholding are overviewed. Section 4 describes the proposed GSA-GA algorithm and states its application in multilevel thresholding. In Sect. 5, experiments are conducted over two standard test images and two real satellite images to evaluate the effectiveness of the GSA-GA. Finally, the chapter is concluded in Sect. 6.
2 Formulation of Multilevel Thresholding Problem
Optimal thresholding methods search for the optimum thresholds by minimizing or maximizing an objective function. Parameters in the utilized objective function are made up by the selected thresholds in each iteration. Specially, the purpose of multilevel thresholding is to classify the Num pixels of an image into K classes using a set of thresholds \(Th=(td_1, td_2, \ldots , td_m)\) where \(m=K-1\). Obviously, different sets of thresholds will produce different image segmentation results. Researchers have formulated some criteria for constructing efficient objective functions [8, 9, 12, 13, 43, 44]. Two most preferred criteria are Kapur’s entropy and Otsu methods as they are relatively easy to use. They are also chosen as criteria in this chapter.
2.1 Kapur’s Entropy Criterion
The Kapur’s entropy criterion, proposed by Kapur et al. [9], is originally developed for bi-level image thresholding. In this method, proper segmentation of an image is achieved by maximizing the Kapur’s entropy. For a bi-level thresholding, the Kapur’s entropy can be described as follows:
where \(HE_i\) is the entropy of class i (\(i \in {0, 1}\)) and \(\omega _i\) is the probability of class i, \(td_0\) is the optimum threshold of the bi-level thresholding. Assume that there are L gray-levels in a given image, the probability of the gray-level i can be defined as follows:
where \(hist_i\) denotes the number of pixels with gray-level i.
As shown in (1) and (2), \(td_0\) is the selected threshold. To obtain the optimum threshold \(td_0\), the fitness function (3) needs to be maximized as follows:
To solve complex multilevel thresholding problems, the Kapur’s entropy has been extended to determine m thresholds for a given image, i.e., \([td_1, td_2, \ldots , td_m]\). The objective of the Kapur’s entropy-based multilevel thresholding is to maximize the fitness function (4) as follows:
where
2.2 Otsu Criterion
The Otsu criterion [8] is another histogram-based multilevel image thresholding algorithm. The method divides the given image into m classes so that the total variance of different classes is maximized. The object function of Otsu is defined as the sum of sigma functions of each class as follows:
The sigma functions are as follows:
where \(\mu _i\) is the mean gray-level of class i (\(i \in {0, 1}\)) and \(\mu _T\) is the mean intensity of the original image.
Similar to the entropy method, the Otsu criterion has already been extent to multilevel thresholding problems. The objective in the Otsu-based multilevel thresholding is to maximize the following function:
where
3 Nature-Inspired Algorithms Based Multilevel Thresholding
In this chapter, we categorized the NAs utilized for multilevel thresholding into three kinds: SIAs, EAs, and PAs based on their original inspirations. Since different kinds of NAs possess unique information sharing mechanisms, certain successes have been produced by each kind of NA. Sections 3.1–3.3 give a detailed review of the three aforementioned kinds of NAs based multilevel thresholding, respectively. In Sect. 3.4, we briefly reviewed the hybrid NAs based multilevel thresholding.
3.1 Swarm Intelligence-Based Optimization Algorithms Based Multilevel Thresholding
SIAs are mainly proposed by mimicking the foraging or hunting behaviors of different species like ants, bees, birds, cuckoos, bats, wolf, and so on [45]. Well-known SIAs include ACO [29], ABC [31], PSO [46], cuckoo search algorithm (CS) [47], Bat Algorithm (BA) [48], and Gray Wolf Optimizer (GWO) [49], etc. In these algorithms, one special particle/individual with the best performance is usually chosen as exemplar/leader for others. The guidance of the exemplar ensures the population evolves directionally in each iteration. The directional search property equips the SIAs with the fast convergence performance [50].
Application of swarm intelligence thereby makes a success in decreasing the computational complexity problem of multilevel thresholding. For example, in [30], Tao et al. utilized ACO to optimize the fuzzy entropy criterion while Zhang et al. search for the optimum multilevel thresholding on the basis of the maximum Tsallis entropy [51]. Similarly, ABC, BA, and GWO also obtained certain successes in multilevel thresholding [6, 17, 51–54]. Besides, as one of the most popular swarm intelligence-based optimization algorithm, PSO and its various variants have contributed to multilevel thresholding a lot [2, 17, 33–35, 55]. Moreover, Hammouche et al. have found that PSO converges more quickly than ACO, ABC, and SA because of all particles can directly learn from the global best particle [21].
Although SIAs contribute a lot to image thresholding, their fast convergence property caused rapid decrease of population diversity. That is, exploration of SIAs is insufficient. This defective exploration of SIAs may result in temperature convergence of multilevel thresholding.
3.2 Evolutionary Algorithms Based Multilevel Thresholding
EAs are motivated by the principle of evolution through selection and mutation. In the past decade, many EAs, such as GA [8], DE [27], and DS [32], have been widely applied. In conventional EAs, evolutionary processes are conducted through reproduction, crossover, mutation, and selection operators. Particularly, only two individuals are randomly selected to exchange information in a single crossover operation [50]. Similarly, in a traditional mutation operator, only two genes in the individuals are randomly varied [50]. Obviously, evolutionary performance of EAs is not as directional as SIAs do. It is omnidirectional to some extent. Thereby EAs have better exploration than SIAs.
Naturally, a number of researchers have paid close attention to obtain optimal thresholds by EAs, especially the GA [21–24] and DE [18, 25, 26]. The favorable exploration ability of EAs makes them achieve remarkable progress in the research area of multilevel thresholding. However, the omnidirectional characteristic of EAs leads to their slow convergence. Moreover, the success of some EAs in solving specific problems highly rely on the user set trial vector generation strategies and control parameters [16].
3.3 Physics-Based Algorithms Based Multilevel Thresholding
The PAs, as the name suggested, are constructed by simulating the phenomenon of physics. For instance, SA [28] imitates the annealing process of melted iron; search algorithm (GSA) [56] inspired by the gravitational kinematics; electromagnetism-like algorithm (EM) [57] and charged search system (CSS) algorithm [58] are proposed on the basis of electrodynamics. More detailed survey of the PAs can be found in [59]. Individuals in PAs explore the search space follows several exemplars. Accordingly, interactions among individuals result in iterative improvement of solutions quality over time. Search diversity of PAs is better than that of SIAs and thus PAs usually perform better exploration. On the other hand, their more directional search property keep higher convergence speed of them. Nevertheless, none of the PAs can solve all the optimization problems in accordance with the “No Free Lunch Theorems” [60].
Comparing with the SIAs and EAs, few researchers have focused on their application on multilevel thresholding. GSA, which possesses simple concept, high-computational efficiency, and few parameters, has proven its promising efficiency in solving complex problems [56, 61]. Furthermore, numerical experiments has confirmed the superiority of GSA with respect to search ability and speed over many other NAs, such as PSO, GA, ACO etc. [56, 62–64]. These advantages make GSA a potential choice for solving multilevel thresholding.
3.4 Hybrid NAs Based Multilevel Thresholding
As discussed in Sects. 3.1–3.3, each kind of NAs has separate and unique advantages and disadvantages. To incorporate different advantages of various NAs and improve the optimization ability of them, large amounts of hybrid algorithms have been proposed over the past decades. For instance, in GAPSO [9], the mutation operator of GA is introduced to PSO to tackle the premature convergence problem while the memory property of PSO is preserved. BBO-DE [40] incorporate both the crossover operator and the selection operator of DE algorithm to BBO to promote exploration ability of BBO while the exploitation ability of BBO is kept. Experiments reported in the literatures demonstrated that these hybrid algorithms can always perform more effective search ability than the original ones.
Many of the hybrid algorithms have already been utilized to solving multilevel thresholding problems, including GAPSO [9], ACO/PSO [38], SA/PSO [39], and BBO-DE [40], etc. The hybrid algorithms usually possess advantages of each composed algorithm. Due to simple hybrid model easily causes high-computational complexity, new NAs, or efficient hybrid NAs are desirable.
4 GSA-GA Based Multilevel Image Thresholding
This chapter introduces a novel hybrid GSA-GA for multilevel image thresholding [65]. Although many researches have paid close attention to the improvement of GSA and presented some GSA variants in the past few years [1, 61, 66, 67], very few of the algorithms have focused on the application on multilevel thresholding. When applying GSA into multilevel image thresholding, especially when the desired number of thresholds is large, the premature convergence and high time-consuming problems become more serious.
The lack of diversity is one important reason for the premature convergence [68]. In GSA-GA, the discrete mutation operator of GA was introduced to promote the population diversity when premature convergence occurred. Moreover, for decreasing computational time, adaptive method is utilized to judge whether the hybridization of GSA and GA are performed. The details of GSA-GA and its application for multilevel image thresholding are given in Sects. 4.1 and 4.2, respectively.
4.1 GSA-GA
In GSA-GA, to adaptively identify whether the hybridization of GSA and GA is necessary, the standard deviations of objective functions and the ratio of the current iteration t to the maximum iterations maxiterations are calculated before conducting the selection and mutation operators of GA. More specifically, when particles are trapped (judging by \(rand< std(fit)\) or \(rand<t/maxiterations)\), the roulette selection and discrete mutation operators are carried out to update position of each particle and thus to diversify the population. Due to the population diversity is crucial for a health search, combination of GA, and GSA can help the algorithm escape from local optima. Besides, because of satisfaction of the condition ‘\(rand<t/maxiterations\)’ becomes easier by the lapse of time, GSA-GA can utilize selection and mutation operators to accelerate convergence in the last iterations. The principle of GSA-GA is shown in Fig. 1. The detailed introduction of the method can be found in [65].
4.2 Implementation of GSA-GA for Multilevel Thresholding
The application of GSA-GA approach to the multilevel image thresholding problem depends on the criterion used for optimization. In this chapter, the Kapur’s entropy and Otsu criteria were implemented. To start the GSA-GA for multilevel thresholding, initial population \(\varvec{X}=[\varvec{X}_1,\varvec{X}_2,\ldots ,\varvec{X}_i,\ldots ,\varvec{X}_N]\) where \(\varvec{X}_i=[x_{i1},x_{i2},\ldots ,x_{iD}]\) should be randomly generated first. Each particle \(\varvec{X}_i\) is comprised of a set of gray values, which stands for a candidate solution of the required threshold values. The size of the population is N (can be set by users), and dimension of each particle is D, which is also the number of desired thresholds: \(D=m\). In the iteration process, the fitness value of each particle is calculated from the Kapur’s entropy or Otsu criterion using Eqs. (4)–(5) and (8)–(9), respectively. The pseudocode of the GSA-GA algorithm for multilevel image thresholding is shown in Fig. 2.
5 Experimental Results and Discussion
In this section, the experimental results are presented. The performance of GSA-GA has been evaluated and compared with the other 6 NAs: the standard GSA [56], GGSA (Adaptive gbest-guided GSA) [67], PSOGSA (hybrid PSO and GSA) [66], DS (Differential Search algorithm) [32], BBO-DE [40], and GAPSO [36] by conducting experiments on two benchmark images that has been tested in many related literatures. Furthermore, to evaluate the ability of GSA-GA based thresholding on more complex and difficulty images, we conducted experiments on two real satellite images adopted from NASA (http://earthobservatory.nasa.gov/Images/?eocn=topnav046eoci=images). The obtained experimental results of the 7 algorithms are also compared. For the satellite images, the low spectral and spatial resolution usually makes objects hard to be segmented, while the high resolution always leads to highly computational complexity during the image segmentation. The four experimental images and corresponding histogram of each image are given in Fig. 3 as shown in Sect. 5.1.
5.1 Test Images
The two standard benchmark test images are two widely utilized images: House and pepper, as shown in Fig. 3a and b, respectively. Size of every tested benchmark images is 256 \(\times \) 256. The two tested satellite images are named SFB and NR respectively as shown in Fig. 3c and d. The image SFB is acquired by the Thematic Mapper on Landsat 5 on September 9, 2002 while image NR is an astronaut photograph taken by Kodak 760 C digital camera on November 8, 2006. Size of the image SFB and NR are 512 \(\times \) 512 and 539 \(\times \) 539, respectively. Due to the two satellite images are multi-spectral images, we transformed the two images using a famous orthogonal transformation method, i.e., principal component analysis (PCA). As the most informative component, the first principal component is selected for multilevel image thresholding in this chapter.
5.2 Experimental Settings
The relative parameter settings of algorithms utilized in this chapter are shown in Table 1. As illustrated in Table 1, to perform a fair experiment, in all of the seven algorithms, the population size (N) and maximum number of fitness evaluations (FEs) were set to 30 and 3000, respectively. For GSA-GA, GSA, PSOGSA, and GGSA, the initial gravitational constant \(G_0\) and decrease coefficient \(\beta \) were set to 100 and 20 as the default values in original GSA [56]. For PSOGSA, the two acceleration coefficients (\(c_1\) and \(c_2\)) were set to 0.5 and 1.5, respectively as suggested in [66]. For GGSA, the two acceleration coefficients (\(c_1\) and \(c_2\)) were set to \(-2t^3/{Iter^3_\mathrm{max}}+2\) and \(2t^3/{Iter^3_\mathrm{max}}\), respectively as recommended in [67]. The other parameters in DS, BBO-DE, and GAPSO were all adopted as the suggested values in the original papers. To be specific, in DS, the two control parameters (i.e., \(p_1\) and \(p_2\)) were both set to 0.3*rand; in BBO-DE, the mutation scheme was the DE/rand/1, the crossover probability (CR), the scaling factor (F), and the elitism parameter (\(n_\mathrm{{elit}}\)) were set to 0.9, 0.5, and 2 [40]; in GAPSO, the mutation probability (\(p_m\)) was set to 0.1, the crossover probability (denoted by \(p_c\)) was set to 1, and the two acceleration coefficients were both set to 2 [36]. For GSA-GA, the mutation probability \(p_m\) was set to 0.1 as it is recommended in many GA based algorithms [23, 37, 40].
5.3 Performance Metrics
In this chapter, the uniformity measure [69] is adopted to qualitatively judge the segmentation results based on different thresholds. The uniformity measure (u) is calculated as follows:
where m is the number of desired thresholds, \(Re_j\) is the j-th segmented region, Num is the total number of pixels in the given image IMG, \(f_i\) is the gray-level of pixel i, \(g_j\) is the mean gray-level of pixels in j-th region, \(f_{max}\) and \(f_{min}\) are the maximum and minimum gray-level of pixels in the given image, respectively. Typically, \(u \in \)[0, 1] and a higher value of uniformity indicates that there is better uniformity in the thresholding image.
5.4 Experiment 1: Maximizing Kapur’s Entropy
The Kapur’s entropy criterion was first maximized to construct an optimally segmented image for all the seven NAs. Table 2 presented the best uniformity (u) and the corresponding threshold values (Th) on all the test images produced by the algorithms after 30 independent runs. Moreover, to test the stability of thresholding methods, average uniformity of 30 independent runs are reported in Table 3. Besides, to test the computation complexity, the mean of CPU times are reported in Table 4.
As shown in Table 2, for image House, GSA-GA outperformed GSA, PSOGSA, GGSA, DS, and GAPSO on all the different number of thresholds. Although BBO-DE gained the best uniformity when \(m=4\), GSA-GA has a better mean uniformity as illustrated in Table 3. For image Pepper, SFB and NR, GSA-GA performed as well as or was better than the other GSA-based segmentation methods on the best uniformity reported in Table 2. Meanwhile, mean uniformity of the three images shown in Table 3 also confirmed the superiority of GSA-GA in most cases. This may be due to that the introduced mutation operator prevents GSA from getting stuck to local optima. Furthermore, when comparing with DS, BBO-DE, and GAPSO, GSA-GA displayed the best on both the best and mean uniformity as presented in Tables 2 and 3. That is to say, variant-based multilevel image thresholding methods are more efficient than other NAs based techniques. That is because particles in GSA variants can learn from other particles fuller than other NAs. Besides, it is worth noting that the mean CPU times of GSA-GA are visible smaller than the comparison algorithms as reported in Table 4.
For a visual interpretation of the segmentation results, the segmented images of the two satellite images obtained based on the optimum thresholds shown in Table 2 were presented in Figs. 4 and 5 with \(m=2-5\). For the two images, it is hard to say which number of thresholds is more suitable for due to the complexity of these images. Their inherent uncertainty and ambiguity make it a challenging task for these tested algorithms to determine the proper number of classes in a given image.
5.5 Experiment 2: Maximizing Otsu
This section devotes to maximize the Otsu criterion to construct an optimally segmented image for all of the seven algorithms. Experiments were performed on all the test images shown in Fig. 3. The best uniformity (u) and the corresponding threshold values (Th) produced by the algorithms were given in Table 5 after 30 independent runs. Similar to Sect. 5.4, to test the stability of the algorithms, Table 6 presented the mean of uniformity. In addition, Table 7 provided the mean of CPU times.
Generally speaking, with the Otsu criterion, GSA-GA yielded better results than the other six comparison algorithms as illustrated in Table 5. Moreover, similar to the results given in Table 4, the mean uniformity reported in Table 6 also confirms the superiority of GSA-based methods comparing with other NAs. Mean CPU times illustrated in Table 7 showed that the computational time of GSA-GA is also the lowest. Especially, time consuming of GSA-GA is much lower than that of DS. In Figs. 6 and 7, the segmentation images of SFB and NR by all the seven NAs used the Otsu criterion are presented.
Furthermore, comparing the mean uniformity shown in Tables 3 and 6, we can concluded that for a given image, thresholds determined based on different criteria can be different. For images Pepper, SFB, and NR, the thresholding results using Otsu criterion is better than the results on the basis of Kapur’s entropy. While for the image House, we observed completely opposite conclusions. Thereby, comprehensive analysis for choosing the most appropriate objective function are desired in the future real-world application.
5.6 Running Time Analysis Using Student’s t-test
To statistically analyze the time-consuming shown in Tables 4 and 7, a parametric significance proof known as the Student’s t-test was conducted in this section [55]. This test allows assessing result differences between two related methods (one of the methods is chosen as control method). In this chapter, the control algorithm is GSA-GA. Results of GSA-GA were compared with other six comparison NAs in terms of the mean CPU times. The null hypothesis in this chapter is that there is no significance difference between the mean CPU times achieved by two compared algorithms for a test image over 30 independent runs. The significance level is \(\alpha =0.05\). Accordingly, if the produced t-value of a test is smaller than or equal to the critical value “−2.045”, the null hypothesis for the paired t-test should be rejected [70, 71].
Tables 8 and 9 reported the t-values produced by Student’s t-test for the pairwise comparison of six groups. These groups were formed by GSA-GA (with Kapur’s entropy and Otsu, respectively) versus other comparison algorithms. In Tables 8 and 9, if the null hypothesis is rejected, we define a symbol “\(h=0\)” which means the difference between the results obtained by two algorithms are not different. By contrast, “\(h=1\)” indicates that the difference between GSA-GA and the compared algorithm is significant.
As illustrated in Tables 8 and 9, for all the test images, the produced t-values for the experiments on the Kapur’s entropy and Otsu criteria were smaller than the critical value. The results indicated that GSA-GA performed significantly fast image segmentation compared with the other six algorithms.
6 Conclusion
Multilevel thresholding is a fundamental and important technology for image segmentation and a fundamental process in image interpretation. An overview of the grayscale image segmentation using multilevel thresholding and nature-inspired algorithms is discussed in this chapter. On one hand, the NAs based multilevel image thresholding can reduce the computational consuming of exhaustive search algorithms based techniques. On the other hand, the global optimization property of NAs makes them as preferable choices for multilevel thresholding. Although some drawbacks of the NAs limited their application, hybrid algorithms can promote their performances. Therefore, a novel multilevel thresholding algorithm for image segmentation by employing an improved GSA variant, called GSA-GA is proposed in this chapter. In GSA-GA, the roulette selection and discrete mutation operators of GA were introduced into GSA to improve the search accuracy and speed of GSA. Experiments on benchmark images and real-word satellite images confirmed the superiority of GSA-GA compared with GSA, PSOGSA, GGSA, DS, BBO-DE, and GAPSO. Potential future investigation can be on the analysis of different criteria. By comprehensive analysis, the most appropriate criterion for constructing objective function can be selected or developed.
References
Zhang, A.Z., Sun, G.Y., Wang, Z.J., Yao, Y.J.: A hybrid genetic algorithm and gravitational search algorithm for global optimization. Neural. Netw. World. 25, 53–73 (2015)
Ghamisi, P., Couceiro, M.S., Martins, F.M., Atli, B.J.: Multilevel image segmentation based on fractional-order Darwinian particle swarm optimization. IEEE. Trans. Geosci. Remote. Sens. 52, 2382–2394 (2014)
Kang, W.X., Yang, Q.Q., Liang, R.P.: The comparative research on image segmentation algorithms. In: 2009 First International Workshop on Education Technology and Computer Science, pp. 703-707. IEEE (2009)
Bhandari, A.K., Singh, V.K., Kumar, A., Singh, G.K.: Cuckoo search algorithm and wind driven optimization based study of satellite image segmentation for multilevel thresholding using Kapur’s entropy. Expert. Syst. Appl. 41, 3538–3560 (2014)
Dey, S., Bhattacharyya, S., Maulik, U.: Quantum Behaved Multi-objective PSO and ACO Optimization for Multi-level Thresholding. IEEE, New York (2014)
Horng, M.H.: Multilevel thresholding selection based on the artificial bee colony algorithm for image segmentation. Expert. Syst. Appl. 38, 13785–13791 (2011)
Bhandari, A.K., Kumar, A., Singh, G.K.: Tsallis entropy based multilevel thresholding for colored satellite image segmentation using evolutionary algorithms. Expert. Syst. Appl. 42, 8707–8730 (2015)
Otsu, N.: A threshold selection method from gray-level histograms. IEEE. Trans. Syst. Man Cybern. 9, 62–66 (1979)
Kapur, J.N., Sahoo, P.K., Wong, A.K.: A new method for gray-level picture thresholding using the entropy of the histogram. Comput. Vison Graph. 29, 273–285 (1985)
Huang, L.K., Wang, M.J.J.: Image thresholding by minimizing the measures of fuzziness. Pattern Recogn. 28, 41–51 (1995)
Qiao, Y., Hu, Q.M., Qian, G.Y., Luo, S.H., Nowinski, W.L.: Thresholding based on variance and intensity contrast. Pattern. Recogn. 40, 596–608 (2007)
Li, X.Q., Zhao, Z.W., Cheng, H.D.: Fuzzy entropy threshold approach to breast cancer detection. Inf. Sci. Appl. 4, 49–56 (1995)
Kittler, J., Illingworth, J.: Minimum error thresholding. Pattern Recogn. 19, 41–47 (1986)
Li, C.H., Tam, P.K.S.: An iterative algorithm for minimum cross entropy thresholding. Pattern Recogn. Lett. 19, 771–776 (1998)
de Albuquerque, M.P., Esquef, I.A., Mello, A.R.G.: Image thresholding using Tsallis entropy. Pattern. Recogn. Lett. 25, 1059–1065 (2004)
Kurban, T., Civicioglu, P., Kurban, R., Besdok, E.: Comparison of evolutionary and swarm based computational techniques for multilevel color image thresholding. Appl. Soft Comput. 23, 128–143 (2014)
Akay, B.: A study on particle swarm optimization and artificial bee colony algorithms for multilevel thresholding. Appl. Soft. Comput. 13, 3066–3091 (2013)
Ali, M., Ahn, C.W., Pant, M.: Multi-level image thresholding by synergetic differential evolution. Appl. Soft. Comput. 17, 1–11 (2014)
Chander, A., Chatterjee, A., Siarry, P.: A new social and momentum component adaptive PSO algorithm for image segmentation. Expert. Syst. Appl. 5, 4998–500 (2011)
Coello, C.C., Lamont, G.B., Van Veldhuizen, D.A.: Evolutionary algorithms for solving multi-objective problems. Springer Science & Business Media, Berlin (2007)
Hammouche, K., Diaf, M., Siarry, P.: A multilevel automatic thresholding method based on a genetic algorithm for a fast image segmentation. Comput. Vis. Image Underst. 109, 163–175 (2008)
Tao, W.B., Tian, J.W., Liu, J.: Image segmentation by three-level thresholding based on maximum fuzzy entropy and genetic algorithm. Pattern Recogn. Lett. 24, 3069–3078 (2003)
Yin, P.Y.: A fast scheme for optimal thresholding using genetic algorithms. Signal Process. 72, 85–95 (1999)
Zhang, J., Percy, R.G., McCarty Jr., J.C.: Introgression genetics and breeding between Upland and Pima cotton: a review. Euphytica 198, 1–12 (2014)
Ayala, H.V.H., dos Santos, F.M., Mariani, V.C., dos Santos Coelho, L.: Image thresholding segmentation based on a novel beta differential evolution approach. Expert. Syst. Appl. 42, 2136–2142 (2015)
Sarkar, S., Das, S., Chaudhuri, S.S.: A multilevel color image thresholding scheme based on minimum cross entropy and differential evolution. Pattern Recogn. Lett. 54, 27–35 (2015)
Storn, R., Price, K.: Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces. J. Global. Optim. 11, 341–359 (1997)
Kirkpatrick, S.: Optimization by simulated annealing: quantitative studies. J. Stat. Phys. 34, 975–986 (1984)
Drigo, M., Maniezzo, V., Colorni, A.: Ant system: optimization by a colony of cooperation agents. IEEE Trans. Syst. Man Cybern. B 26, 29–41 (1996)
Tao, W.B., Jin, H., Liu, L.M.: Object segmentation using ant colony optimization algorithm and fuzzy entropy. Pattern Recogn. Lett. 28, 788–796 (2007)
Karaboga, D.: An idea based on honey bee swarm for numerical optimization. In: Broy, M., Dener, E. (eds.) Software Pioneers, pp. 10–13. Springer, Heidelberg (2002)
Civicioglu, P.: Transforming geocentric cartesian coordinates to geodetic coordinates by using differential search algorithm. Comput. Geosci. 46, 229–247 (2012)
Clerc, M., Kennedy, J.: The particle swarm-explosion, stability, and convergence in a multidimensional complex space. IEEE Trans. Evol. Comput. 6, 58–73 (2002)
Nabizadeh, S., Faez, K., Tavassoli, S., Rezvanian, A.: A Novel Method for Multi-level Image Thresholding Using Particle Swarm Optimization Algorithms. IEEE, New York (2010)
Yin, P.Y.: Multilevel minimum cross entropy threshold selection based on particle swarm optimization. Appl. Math. Comput. 184, 503–513 (2007)
Baniani, E.A., Chalechale, A.: Hybrid PSO and genetic algorithm for multilevel maximum entropy criterion threshold selection. Int. J. Hybrid Inf. Technol. 6, 131–140 (2013)
Juang, C.F.: A hybrid of genetic algorithm and particle swarm optimization for recurrent network design. Proc IEEE Trans. Syst. Man Cybern. B 34, 997–1006 (2004)
Patel, M.K., Kabat, M.R., Tripathy, C.R.: A hybrid ACO/PSO based algorithm for QoS multicast routing problem. Ain Shams Eng. J. 5, 113–120 (2014)
Zhang, Y.D., Wu, L.N.: A robust hybrid restarted simulated annealing particle swarm optimization technique. Adv. Comput. Sci. Appl. 1, 5–8 (2012)
Boussaïd, I., Chatterjee, A., Siarry, P., Ahmed-Nacer, M.: Hybrid BBO-DE Algorithms for Fuzzy Entropy-based Thresholding. Springer, Heidelberg (2013)
Gong, W.Y., Cai, Z.H., Ling, C.X., Li, H.: A real-coded biogeography-based optimization with mutation. Appl. Math. Comput. 216, 2749–2758 (2010)
John, H.: Holland. Adaptation in Natural and Artificial Systems. MIT Press, Cambridge (1992)
Li, C.H., Lee, C.: Minimum cross entropy thresholding. Pattern Recogn. 26, 617–625 (1993)
Tsai, W.H.: Moment-preserving thresolding: a new approach. Comput. Vison Graph. 29, 377–393 (1985)
Blum, C., Li, X.: Swarm Intelligence in Optimization. Springer, Heidelberg (2008)
Kenndy, J., Eberhart, R.C., Labahn, G.: Particle Swarm Optimization. Kluwer, Boston (1995)
Yang, X.S., Deb, S.: Cuckoo Search via Lévy Flights. IEEE, New York (2009)
Yang, X.S., Hossein, G.A.: Bat algorithm: a novel approach for global engineering optimization. Eng. Comput. 29, 464–483 (2012)
Mirjalili, S., Mirjalili, S.Z.M., Lewis, A.: Grey Wolf Optimizer. Adv. Eng. Softw. 69, 46–61 (2014)
Gong Y.J., Li, J.J., Zhou, Y., Li, Y., Chung, H.S.H., Shi, Y.H., Zhang, J.: Genetic learning particle swarm optimization. IEEE Trans. Cybern., 1–14 (2015)
Zhang, Y.D., Wu, L.N.: Optimal multi-level thresholding based on maximum Tsallis entropy via an artificial bee colony approach. Entropy 13, 841–859 (2011)
Alihodzic, A., Tuba, M.: Bat algorithm (BA) for image thresholding. Recent Res. Telecommun. Inf. Electron. Signal Process, 17–19 (2013)
Alihodzic, A., Tuba, M.: Improved bat algorithm applied to multilevel image thresholding. Sci World J. (2014). doi:10.1155/2014/176718
Ye, Z.W., Wang, M.W., Liu, W., Chen, S.B.: Fuzzy entropy based optimal thresholding using bat algorithm. Appl. Soft. Comput. 31, 381–395 (2015)
Li, Y.Y., Jiao, L.C., Shang, R.H., Stolkin, R.: Dynamic-context cooperative quantum-behaved particle swarm optimization based on multilevel thresholding applied to medical image segmentation. Inf. Sci. 294, 408–422 (2015)
Rashedi, E., Nezamabadi-Pour, H., Saryazdi, S.: GSA: a gravitational search algorithm. Inf. Sci. 179, 2232–2248 (2009)
Birbil, S., Fang, S.C.: An electromagnetism-like mechanism for global optimization. J. Global. Optim. 25, 263–282 (2003)
Kaveh, A., Talatahari, S.: A novel heuristic optimization method: charged system search. Acta. Mech. 213, 267–289 (2010)
Biswas, A., Mishra, K.K., Tiwari, S., Misra, A.K.: Physics-inspired optimization algorithms: a survey. J. Optim. 2013, 1–16 (2013)
Wolpert, D.H., Macready, W.G.: No free lunch theorems for optimization. IEEE Trans. Evol. Comp. 1, 67–82 (1997)
Jiang, S., Wang, Y., Ji, Z.: Convergence analysis and performance of an improved gravitational search algorithm. Appl. Soft Comput. 24, 363–384 (2014)
Kumar, J.V., Kumar, D.V., Edukondalu, K.: Strategic bidding using fuzzy adaptive gravitational search algorithm in a pool based electricity market. Appl. Soft Comput. 13, 2445–2455 (2013)
Mirjalili, S., Hashim, S.Z.M., Sardroudi, H.M.: Training feedforward neural networks using hybrid particle swarm optimization and gravitational search algorithm. Appl. Math. Comput. 218, 11125–11137 (2012)
Sabri, N.M., Puteh, M., Mahmood, M.R.: A review of gravitational search algorithm. Int. J. Adv. Soft Comput. Appl. 5, 1–39 (2013)
Sun, G.Y., Zhang, A.Z., Yao, Y.J., Wang, Z.J.: A novel hybrid algorithm of gravitational search algorithm with genetic algorithm for multi-level thresholding. Appl. Soft Comput. 46, 703–730 (2016). doi:10.1016/j.asoc.2016.01.054
Mirjalili, S., Hashim, S.Z.M.: A new hybrid PSOGSA algorithm for function optimization. IEEE, New York (2010)
Mirjalili, S., Lewis, A.: Adaptive gbest-guided gravitational search algorithm. Neural Comput. Appl. 25, 1569–1584 (2014)
Herrera, F., Lozano, M., Verdegay, J.L.: Fuzzy connectives based crossover operators to model genetic algorithms population diversity. Fuzzy. Set. Syst. 92, 21–30 (1997)
Sahoo, P.K., Soltani, S., Wong, A.K.C.: A survey of thresholding techniques. Neural. Comput. Appl. 41, 233–260 (1988)
Derrac, J., García, S., Molina, D., Herrera, F.: A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms. Swarm Evol. Comput. 1, 3–18 (2011)
Liang, J.J., Qin, A.K., Suganthan, P.N., Baskar, S.: Comprehensive learning particle swarm optimizer for global optimization of multimodal functions. IEEE Ttans. Evolut. Comput. 10, 281–295 (2006)
Acknowledgments
This work was supported by the Chinese Natural Science Foundation Projects (No. 41471353, No. 41271349), Fundamental Research Funds for the Central Universities (No. 14CX02039A, No. 15CX06001A), and the China Scholarship Council.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing AG
About this chapter
Cite this chapter
Sun, G., Zhang, A., Wang, Z. (2016). Grayscale Image Segmentation Using Multilevel Thresholding and Nature-Inspired Algorithms. In: Bhattacharyya, S., Dutta, P., De, S., Klepac, G. (eds) Hybrid Soft Computing for Image Segmentation. Springer, Cham. https://doi.org/10.1007/978-3-319-47223-2_2
Download citation
DOI: https://doi.org/10.1007/978-3-319-47223-2_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-47222-5
Online ISBN: 978-3-319-47223-2
eBook Packages: Computer ScienceComputer Science (R0)