A multilevel automatic thresholding method based on a genetic algorithm for a fast image segmentation

https://doi.org/10.1016/j.cviu.2007.09.001Get rights and content

Abstract

In this paper, a multilevel thresholding method which allows the determination of the appropriate number of thresholds as well as the adequate threshold values is proposed. This method combines a genetic algorithm with a wavelet transform. First, the length of the original histogram is reduced by using the wavelet transform. Based on this lower resolution version of the histogram, the number of thresholds and the threshold values are determined by using a genetic algorithm. The thresholds are then projected onto the original space. In this step, a refinement procedure may be added to detect accurate threshold values. Experiments and comparative results with multilevel thresholding methods over a synthetic histogram and real images show the efficiency of the proposed method.

Introduction

Image thresholding is widely used as a popular tool in image segmentation. It is useful to separate objects from background, or discriminate objects from objects that have distinct grey levels. Thresholding involves bi-level thresholding and multilevel thresholding. Bi-level thresholding classifies the pixels into two groups, one including those pixels with grey 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 grey levels within a specific range defined by several thresholds. Both bi-level and multilevel thresholding methods can be classified into parametric and non-parametric approaches. The non-parametric approach is based on a search of the thresholds optimizing an objective function, such as the between-class variance (Otsu’s function) [1], entropy (Kapur’s function) [2]. In the parametric approach, the grey 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 fit the given histogram data is made by using the least-squares method. It typically leads to a nonlinear optimization problem, of which solving is time-consuming. A great number of thresholding methods of parametric or non-parametric type have been proposed in order to perform bi-level thresholding [3], [4], [5], [6]. They are extendable to multilevel thresholding as well. However, the amount of thresholding computation significantly increases with this extension. To overcome this problem, several techniques have been proposed. In [7], the Otsu’s function is modified in order to be optimized by a fast recursive algorithm along with a look-up-table. In [8], Lin has proposed a fast thresholding computation using the Otsu’s function. His approach is based on the search of the thresholds where zero first partial derivatives of the Otsu’s function occur by using a successive substitution technique. In [9], the resolution of the histogram is reduced using the wavelet transform. Using the reduced histogram, the optimal thresholds are determined by optimizing the Otsu’s function based on an exhaustive search. The selected threshold values are then expanded to the original scale.

The pairwise nearest neighbour method previously used in hierarchical clustering has been adapted to multilevel thresholding [10]. Among all possible thresholds, the one that increases the objective function is selected. The selected threshold is then removed and the means of the classes are updated. The selection and removing processes are repeated until the desired number of thresholds is reached. Another hierarchical clustering method used to solve the multilevel thresholding problem was recently proposed [11]. Initially, each non-empty grey level of the histogram is considered as a separate mode representing a cluster. Then the similarities between adjacent clusters are computed and the most similar pairs are merged. The estimated thresholds defined as the highest grey levels of the clusters are obtained by iterating this operation until the desired number of clusters is found.

Another fast multilevel thresholding technique has been proposed by Yin [12]. The thresholds optimizing the Otsu’s or the Kapur’s functions are searched by using an iterative scheme. This technique starts from random initial thresholds. Then, these thresholds are iteratively adjusted 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, where the Kapur’s function is maximized by using the Iterated Conditional Modes (ICM) algorithm [13].

Several techniques using genetic algorithms (GAs) have also been proposed to solve the multilevel thresholding problem [14], [15], [16], [17], [18], [19], [20]. GAs are optimization algorithms based on the mechanics of natural selection and natural genetics. Yin [14] has proposed a fast thresholding method based on a genetic algorithm, where the objective function is similar to Otsu’s or Kapur’s function. The solution is encoded as a binary string T such that T = t1, t2, …, tk−1, where ti, the value of ith threshold, has log2(L) bits and a value within [0, L  1]. This same technique has been used in [15], [16]. In [15], the objective function is similar to Kapur’s function and in [16] it is assimilated to the relative entropy [21]. Chang and Yan have proposed a thresholding technique using a Conditional Probability Entropy (CPE) based on Bayesian theory. They have employed a GA to maximize the CPE in order to determine the thresholds [17]. CPE considers that the pixels with the same grey 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. The chromosome structure in their GA is based on the conditional probability function employed, with two parameters for each class. The chromosome is then constituted of 2k parameters and each parameter has log2(L) bits. In [18], a multilevel optimal thresholding technique based on an approach using a GA has been proposed. 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. use a genetic algorithm in order to find the optimal combination of all the fuzzy parameters by maximizing the fuzzy entropy [19]. The fuzzy parameters describe the membership functions of three parts of the image, namely dark, grey and white parts. The optimal parameters are then used to define two threshold values. More recently, Bazi et al. use a genetic algorithm to provide the initial parameters to the expectation-maximization (EM) algorithm. The parameters are the objects and background classes, which are assumed to follow generalized Gaussian distributions [20]. Each chromosome is viewed as a vector representing statistical parameters defining the mixture of the class distributions.

Beside GAs, particle swarm optimization (PSO) is another latest evolutionary optimization technique which was used for the multilevel thresholding [22], [23], [24]. In [22], PSO is used in conjunction with the simplex method for the Gaussian curve fitting and for the Otsu’s function optimization. The method presented in [23] uses PSO to optimize the cross entropy [25] and in [24] the histogram is approximated by a mixture Gaussian model. The Gaussian’s parameter estimates are iteratively computed by combining PSO with EM algorithm. Like the genetic algorithms and PSO, simulated annealing algorithm has been exploited to optimize the modified Otsu’s function [26].

The main problem associated with the aforementioned methods is that the number of thresholds with which the grey level image should be segmented cannot be automatically determined. To overcome this problem, Yen et al. proposed a new criterion for multilevel thresholding, called Automatic Thresholding Criterion (ATC) [27]. This criterion is used with a sequential dichotomization technique [27], [28]. In this strategy, the histogram is dichotomized in 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 cost function (ATC) reaches its minimum. In [29], the same dichotomization process is repeated until a cost function derived from Otsu’s function becomes higher than a specified value. The dichotomization techniques are faster algorithms; unfortunately, they are sub-optimal techniques, they do not allow providing the optimal threshold values.

In this paper, we propose a fast multilevel thresholding technique based on a GA able to determinate the appropriate number of thresholds, as well as appropriate threshold values, by optimizing ATC proposed by Yen et al. The proposed GA uses a new string representation of the chromosome, which is different from those previously mentioned. It is combined with a wavelet transform-based technique in order to reduce the time computation. This proposed method can be considered as similar to the multilevel thresholding method presented by Kim et al. [9], except that the proposed GA is used to search for the optimal thresholds. The using of GAs has many advantages over traditional searching techniques [30]. Particularly, GA-based methods are global searching techniques capable, most often, to prevent from trapping into locally optimal solutions. Another advantage is that the GA-based methods can become faster through parallel implementations.

In the next section, the proposed multilevel thresholding technique using a GA is described. In Section 3, the performance of the proposed method is tested on several examples and is compared with other multilevel thresholding methods. Concluding remarks are given in Section 4.

Section snippets

The proposed multilevel thresholding method

Suppose that an image I having N pixels with L grey levels L = {0, 1, …, L  1} is to be classified into k classes (C1, C2, …, Ck) with the set of thresholds T = {t1, t2, …, tk−1}. For convenience, we assume two other thresholds t0 = 0 and tk = L  1. The histogram of the image is indicated by h(i), i = 0, …, L  1, where h(i) represents the number of pixels with the grey level i.

The proposed genetic thresholding technique is based on a standard GA. It allows the determination of the number of thresholds as well as

Experimental results and comparison with other methods

In this section, we will evaluate the performance of the proposed multilevel thresholding method using a GA. Some experiments with a synthetic histogram and real images are presented to illustrate the key features of the proposed method in the determination of the number of thresholds and its efficiency for thresholding computation. Comparisons are performed with results provided by other multilevel thresholding methods.

Eight well-known images named Lena, Blood, Peppers, House, Airplane, Lac,

Conclusion

In this paper, we have proposed a new multilevel thresholding method based on a genetic algorithm, which enables determining the appropriate number of thresholds, as well as the adequate threshold values. The length of the original histogram is reduced by using a wavelet transform. Based on this lower resolution version of the histogram, the optimal threshold values are determined by using a standard GA. In this GA is used a new string representation of the chromosome, which is different from

References (30)

  • Z. Hou et al.

    On minimum variance thresholding

    Pattern Recognit. Lett.

    (2006)
  • M. Sezgin et al.

    A new dichotomization technique to multilevel thresholding devoted to inspection applications

    Pattern Recognit. Lett.

    (2000)
  • N. Otsu

    A threshold selection method for grey level histograms

    IEEE Trans. Syst. Man Cybern.

    (1979)
  • E.J.N. Kapur et al.

    A new method for grey-level picture thresholding using the entropy of the histogram

    Comput. Vis. Graph. Image Process.

    (1985)
  • M. Sezgin et al.

    Survey over image thresholding techniques and quantitative performance evaluation

    J. Electron. Imaging

    (2004)
  • Cited by (236)

    View all citing articles on Scopus
    View full text