مطالعه مقایسه ای تکنیک های مختلف متا هیوریستیک اعمال شده برای مسئله آستانه چند سطحی

The multilevel thresholding problem is often treated as a problem of optimization of an objective function. This paper presents both adaptation and comparison of six meta-heuristic techniques to solve the multilevel thresholding problem: a genetic algorithm, particle swarm optimization, differential evolution, ant colony, simulated annealing and tabu search. Experiments results show that the genetic algorithm, the particle swarm optimization and the differential evolution are much better in terms of precision, robustness and time convergence than the ant colony, simulated annealing and tabu search. Among the first three algorithms, the differential evolution is the most efficient with respect to the quality of the solution and the particle swarm optimization converges the most quickly.

Image thresholding is widely used as a popular tool in image segmentation. It is useful in separating objects from background, or discriminating objects from objects that have distinct gray levels. Thresholding involves bi-level thresholding and multilevel thresholding. Bi-level thresholding classifies the pixels into two groups, one including those pixels with gray levels above a certain threshold, the other including the rest. Multilevel thresholding divides the pixels into several classes. The pixels belonging to the same class have gray levels within a specific range defined by several thresholds. Both bi-level and multilevel thresholding methods can be classified into parametric and nonparametric approaches. The nonparametric approach is based on a search of the thresholds optimizing an objective function such as the between-class variance (Otsu's function) (Otsu, 1979), entropy (Kapur's function) (Kapur et al., 1985). In parametric approach, the gray-level distribution of each class has a probability density function that is assumed to obey a given distribution. An attempt to find an estimate of the parameters of the distribution that best fits the given histogram data is made by using the least-squares method. It typically leads to a nonlinear optimization problem, of which the solution is computationally expensive and time-consuming. A great number of thresholding methods belonging to parametric and nonparametric approaches have been proposed in order to perform bi-level thresholding (Sezgin and Sankur, 2004; Lievers and Pilkey, 2004; Chu et al., 2004; Gonzales-Baron and Butler, 2006). They are extendable for multilevel thresholding as well. However, the amount of thresholding computation significantly increases with this extension. To overcome this problem, several techniques have been proposed. Some of them are designed especially for computation acceleration of a specific objective function, such as the Otsu's function (Lin, 2001; Dong et al., 2008; Riddi et al., 1987; Ng, 2004; Liao et al., 2001), while other techniques are designed to be used with a general purpose. Among the last category, we can find those that involve a sequential dichotomization technique (Yen et al., 1995; Sezgin and Tasaltin, 2000; Wu et al., 2004) and those that use an iterative scheme (Yin and Chen, 1997). In the first strategy, the histogram is dichotomized into two distributions by using a bi-level thresholding and the distribution with the largest variance is further dichotomized in two more distributions by applying the same bi-level thresholding. This dichotomization process is repeated until a stopping criterion is satisfied. The dichotomization techniques are faster algorithms. Unfortunately, they are sub-optimal techniques and they do not provide the optimal threshold values. The second approach starts with initial thresholds. Then, these thresholds are adjusted iteratively to improve the value of the objective function. This improvement process stops when the value of the objective function does not increase between two consecutive iterations. The implementation of this method is similar to the one presented by Luo and Tian (2000), where the Kapur's function is maximised by using the iterated conditional modes (ICM) algorithm. However, the iterative schemes are sensitive to initial values of thresholds and can converge to the local optimum. Other strategies can also be applied for fast multilevel thresholding, as the one proposed in Kim et al. (2003), where the resolution of the histogram is reduced using the wavelet transform. From the reduced histogram, the optimal thresholds are determined faster by optimizing the objective function based on an exhaustive search. The selected threshold values are then expanded to the original scale. Another alternative to fast multilevel thresholding uses a new class of algorithms, called meta-heuristics. A meta-heuristic is a set of algorithmic concepts that can be used to define heuristic methods applicable to a wide set of various problems (Blum and Roli, 2001; Glover and Kochenberger, 2003). In other words, a meta-heuristic can be seen as a general-purpose heuristic method, designed to guide an underlying problem specific heuristic toward promising regions of the search space, containing high-quality solutions. A meta-heuristic therefore is a general algorithmic framework, which can be applied to different optimization problems at the price of relatively few modifications. The meta-heuristic techniques are able to escape from local optima and their use has significantly increased the ability of finding very high-quality solutions to hard, practically relevant combinatorial optimization problems in a reasonable time. This is particularly true for large and poorly understood problems. Several different meta-heuristics have been proposed and new ones are under constant development. Some of the most famous ones are Genetic Algorithms (GA) (Goldberg, 1989), Particle Swarm Optimization (PSO) (Kennedy and Eberhart, 1995), Differential Evolution (DE) (Storn and Price, 1995), Ant Colony Optimization (ACO) (Dorigo and Stützle, 2000), Simulated Annealing (SA) (Kirkpatrick et al., 1983), Tabu Search (TS) (Glover and Laguna, 1997) and explorative local search methods, including Adaptive Search Procedure (GRASP), Variable Neighborhood Search (VNS), Guided Local Search (GLS) and Iterated Local Search (ILS) (Blum and Roli, 2001; Glover and Kochenberger, 2003). Taking into account the advantages of the meta-heuristics to escape from local optima with a reasonable time, some meta-heuristic techniques have been extensively employed to search more fastly the optimal thresholds. These techniques are designed to be used with a general purpose, with either the parametric or the non-parametric approaches, for the multilevel thresholding problem. This problem, which consists in searching the various thresholds, can be considered as a nonlinear optimization problem and the objective functions can have several local optima. For solving such NP-hard problems, enumerative search methods are practically inappropriate because of the presence of several local minima. Their performance deteriorates with the complexity of the problem related to the number of thresholds. For example, the complexity of an exhaustive search grows exponentially with the number k of thresholds as O(L(k-1))O(L(k-1)), L representing the number of gray levels in the image. Indeed, the optimization techniques based on GA have been widely applied to solve the multilevel thresholding (Yin, 1999; Jinsong et al., 1999; Yang et al., 2003; Chang and Yan, 2003; Cao et al., 2008; Hammouche et al., 2008; Lai and Tseng, 2004; Tao et al., 2003; Bazi et al., 2007). In Yin (1999), Jinsong et al. (1999), Yang et al. (2003), Chang and Yan (2003), Cao et al. (2008), Hammouche et al. (2008), the GA uses binary encoding while in Lai and Tseng (2004), Tao et al. (2003) and Bazi et al. (2007), the floating encoding is used. In addition to the way of coding the vectors solutions, these techniques differ by their fitness function. In Yin (1999) and Cao et al. (2008) the objective function is similar to Otsu's or Kapur's functions. In Jinsong et al. (1999) the objective function is the Kapur's function and in Yang et al. (2003) it is assimilated to the relative entropy (Chang et al., 1994). Chang and Yan (2003) have employed a GA to maximize the conditional probability entropy (CPE) based on Bayesian theory, in order to determine the optimal thresholds. CPE considers that the pixels with the same gray level in an image may belong to different classes with different probabilities. An optimal classification method for these pixels is to classify them in the class with higher probability. More recently, the GA presented in Hammouche et al. (2008) determines the threshold number as well as the optimal threshold values, by using an objective function derived from a correlation function (Yen et al., 1995). In Lai and Tseng (2004), the intensity distributions of objects and background in an image are assumed to be Gaussian distributions with distinct means and standard deviations. The histogram of a given image is fitted to a mixture Gaussian probability density function. The GA is used to estimate the parameters in the mixture density function, so that the square error between the density function and the actual histogram is minimal. Tao et al. (2003) use a GA in order to find the optimal combination of all the fuzzy parameters by maximizing the fuzzy entropy. The fuzzy parameters describe the membership functions of three parts of the image, namely dark, gray and white parts. The optimal parameters are then used to define two threshold values. Bazi et al. (2007) use a genetic algorithm to provide the initial parameters to the expectation-maximization (EM) algorithm. The parameters of the objects and background classes are assumed to follow generalized Gaussian distributions. Each chromosome is viewed as a vector representing statistical parameters defining the mixture of the class distributions. The DE, an improved version of GA is used for image thresholding. The proposed method in Rahnamayan et al. (2006) splits the input image in n sub-images and assigns a threshold level to each sub-image. Then the DE algorithm is applied to find the optimal threshold values by minimizing the dissimilarity between the input image and its binary version. Finally, the sub-images, thresholded by the corresponding threshold optimal values, are assembled to form the binary image. Unfortunately, this method which is specifically designed in the case of local and bilevel thresholding, cannot be applied to the global multilevel thresholding. Besides GAs, PSO is another latest evolutionary optimization technique, which is used for the multilevel thresholding (Zahara et al., 2005; Yin, 2007; Feng et al., 2005; Maitra and Chatterjee, 2008; Fan and Lin, 2007). In Zahara et al. (2005), the PSO is used in conjunction with the simplex method for the Gaussian curve fitting and for the Otsu's function optimization. It is used in Yin (2007), for optimizing the cross entropy (Li and Lee, 1993) and for determining the single threshold value maximizing the 2-D entropy (Feng et al., 2005). The strategy developed in Maitra and Chatterjee (2008) uses the Kapur's function as criterion; it employs a cooperative learning that consists in decomposing a high-dimensional swarm into several one-dimensional swarms. The comprehensive learning allows discouraging convergence in each one-dimensional swarm. In Fan and Lin (2007), the histogram is approximated by a mixture Gaussian model. The Gaussian's parameter estimates are iteratively computed by combining the PSO with the EM algorithm. Like the GA and the PSO, SA (Cheng et al., 1998; Hou et al., 2006; Nakib et al., 2007) and ACO (Tao et al., 2007) have been, also, exploited in image thresholding. In Nakib et al. (2007), the SA is used as a multiobjective optimization technique to find the optimal threshold values of three criteria, namely the within-class criterion, the entropy and the overall probability of error criterion. The same paper proposes a variant of SA in order to solve the Gaussian curve-fitting problem. As in Tao et al. (2003), the SA (Cheng et al., 1998) and the ACO (Tao et al., 2007) are also used to find the optimal combination of all the fuzzy parameters by maximizing the fuzzy entropy. The fuzzy parameters describe also the membership functions of two parts of the image, namely dark and bright parts. Despite the intensive use of the meta-heuristics in thresholding, no paper related to the ACO applied specifically to global multilevel thresholding was found in our bibliography search. In addition, no work would be published concerning Tabu-based multilevel thresholding and DE algorithm allowing the direct computing of the threshold values. So, in this paper, three new multilevel thresholding techniques based on the DE, ACO and TS are developed in order to determine directly the values of thresholds. A comparative study between six meta-heuristic techniques, namely a GA, PSO, DE, ACO, SA and TS, is then conducted in the multilevel thresholding framework. The choice of these six meta-heuristics, contrary to the other methods, as explorative local search methods, is motivated by their use of nature inspired concepts. For each of the six meta-heuristics quoted previously, more sophisticated versions have been developed. However, to carry out an equitable comparison between these meta-heuristics, only the standard versions will be used in this paper. The remainder of this paper is organized as follows. In Section 2, the problem of the multilevel thresholding is formulated as an optimization problem and the objective function treated are briefly presented. The Section 3 deals with a review of the meta-heuristic optimization techniques and their application for the resolution of the multilevel thresholding problem. Section 4 gives comparative results of the six implemented meta-heuristic techniques. Concluding remarks are given in Section 5

In this paper, three new multilevel thresholding techniques based on DE, ACO and TS were proposed in order to determine directly the values of thresholds. Furthermore, we considered three other meta-heuristic algorithms for solving the multilevel thresholding problem, namely GA, PSO and SA. These six meta-heuristic algorithms were then compared by testing them on various images. We have found that all algorithms are comparable in term of solution quality when the threshold number is small, i.e. less than or equal to 2. While this number increases, the GA, PSO and DE provide better results than ACO, SA and TS with a little advantage to the DE. In term of execution time, the GA, PSO and DE are most efficient than other algorithms with a great speed for the PSO. Finally, it turned out that, in the multilevel thresholding framework, the PSO is superior compared to other meta-heuristics both respect to precision, as well as robustness of the results and runtime. One can see through this study that, except for ACO, the population based meta-heuristics like GA, PSO and DE outperform the meta-heuristics like TS and SA, which handle a single solution. Several local optima of the objective function appear when the number of thresholds increases and TS and SA found difficulties to escape from these local optima. Further works consist in applying sophistical versions of ACO and TS to solve the multilevel thresholding problem. This comparison can also be extended to other meta-heuristics, such as the iterated local search, the variable neighborhood search, or by using a hybridization between two or several meta-heuristics.