A multi-level thresholding approach using a hybrid optimal estimation algorithm

doi:10.1016/j.patrec.2006.11.005

Pattern Recognition Letters

Volume 28, Issue 5, 1 April 2007, Pages 662-669

https://doi.org/10.1016/j.patrec.2006.11.005 Get rights and content

Abstract

This paper presented a hybrid optimal estimation algorithm for solving multi-level thresholding problems in image segmentation. The distribution of image intensity is modeled as a random variable, which is approximated by a mixture Gaussian model. The Gaussian’s parameter estimates are iteratively computed by using the proposed PSO + EM algorithm, which consists of two main components: (i) global search by using particle swarm optimization (PSO); (ii) the best particle is updated through expectation maximization (EM) which leads the remaining particles to seek optimal solution in search space. In the PSO + EM algorithm, the parameter estimates fed into EM procedure are obtained from global search performed by PSO, expecting to provide a suitable starting point for EM while fitting the mixture Gaussians model. The preliminary experimental results show that the hybrid PSO + EM algorithm could solve the multi-level thresholding problem quite swiftly, and also provide quality thresholding outputs for complex images.

Introduction

Image thresholding is very useful in separating objects from background image, or discriminating objects from objects that have distinct gray-levels. Sezgin and Sankur (2004) have presented a thorough survey of a variety of thresholding techniques, among which global histogram-based algorithms, such as minimum error thresholding (Kittler and Illingworth, 1986), are employed to determine the threshold. In parametric approaches (Weszka and Rosenfeld, 1979, Synder et al., 1990), the gray-level distribution of each class has a probability density function (PDF) that is assumed to obey a (mixture) Gaussian distribution. An attempt to find an estimate of the parameters of the distribution that will best fit the given histogram data is made by using the least-squares estimation (LSE) method. Typically, it leads to a nonlinear optimization problem, of which the solution is computationally expensive and time-consuming. Besides, Snyder et al. presented an alternative method for fitting curves based on a heuristic method called tree annealing; Yin (1999) proposed a fast scheme for optimal thresholding using genetic algorithms, and Yen et al. (1995) proposed a new criterion for multi-level thresholding, termed automatic thresholding criterion (ATC) to deal with automatic selection of a robust, optimum threshold for image segmentation. More recently, Zahara et al. (2005) proposed a hybrid Nelder-Mead Particle Swarm Optimization (NM-PSO) method to solve the objective function of Gaussian curve fitting for multi-level thresholding. The NM-PSO method is efficient in solving the multi-level thresholding problem and could provide better effectiveness than the other traditional methods in the context of visualization, object size and image contrast. However, curve fitting is usually time-consuming for multi-level thresholding. To further enhance efficiency while maintaining quality effectiveness, an improved method is warranted. For further details of the NM-PSO method, see Zahara et al., 2005, Fan and Zahara, 2006.

In this paper, an improvement upon Gaussian curve fitting is reported that the efficiency of image thresholding methods could be enhanced in the case of multi-level thresholding. We present a hybrid expectation maximization (EM) and particle swarm optimization (PSO + EM) algorithm to solve the objective function of Gaussian parameter estimation. The PSO + EM algorithm is applied to image thresholding with multi-modal histograms, and the performances of PSO + EM on Gaussian curve fitting are compared to the NM-PSO method. Section 2 introduces the parametric objective functions that need to be solved in image thresholding. In Section 3, the proposed hybrid PSO + EM algorithm is detailed. Section 4 gives the experimental results and compares performances between two different methods. Lastly, Section 5 concludes this research.

Section snippets

Minimum error thresholding by Gaussian model

One of the most advanced techniques in image thresholding is “minimum error thresholding” proposed by Kittler and Illingworth (1986), which was remarked in the survey paper presented by Sezgin and Sankur (2004). In the beginning, we consider an image whose pixels assume gray level values, x, from the interval [0, n]. It is convenient to summarize the distribution of gray levels in the form of a histogram h(x) which gives the frequency of occurrence of each gray level in the image (Kittler and

Hybrid PSO + EM method

In this paper, the development of the hybrid algorithm intends to improve the efficiency of the optimal thresholding techniques currently applied in practice. The goal of integrating expectation maximization (EM) algorithm and particle swarm optimization (PSO) is to combine their advantages and compensate for each other’s disadvantages. For instance, the EM algorithm is efficient but excessively sensitive to the starting point (i.e., initial estimates). A poor starting point might make the EM

Experimental results

In this section, we evaluate and compare the performances of these two methods: the NM-PSO algorithm and proposed PSO + EM algorithm while implementing Gaussian curve fitting for multi-level thresholding. Both methods are implemented on an Intel Celeron 2.8 GHz platform with 512 MB DDR-RAM using Matlab. The test images are of size 256 × 256 pixels with 8 bit gray-levels, taken under natural room lighting without the support of any special light source. The stopping criterion of NM-PSO referred to

Concluding remarks

The NM-PSO algorithm has been verified that is effective in the bi-level and tri-level thresholding cases, but its computation time becomes aggravated in the case of higher dimensional thresholding. In order to make the evolutionary computation method more practical in on-line applications, a much faster searching procedure called the PSO + EM algorithm is proposed, which solves the objective function of mixture Gaussian curve fitting by combining the EM and PSO algorithms. Experimental results

Acknowledgements

The authors wish to thank two anonymous referees for providing many constructive suggestions that greatly improved the quality on an earlier version of this paper.

References (14)

J. Kittler et al.
Minimum error thresholding
Pattern Recognition Lett.
(1986)
P.Y. Yin
A fast scheme for optimal thresholding using genetic algorithms
Signal Process.
(1999)
E. Zahara et al.
Optimal multi-thresholding using a hybrid optimization approach
Pattern Recognition Lett.
(2005)
Eberhart, R.C., Shi, Y., 2001. Tracking and optimizing dynamic systems with particle swarms. In: Proc. of the Congress...
S.-K.S. Fan et al.
A hybrid simplex search and particle swarm optimization for unconstrained optimization
Eur. J. Oper. Res.
(2006)
Hu, X., Eberhart, R.C., 2001. Tracking dynamic systems with PSO: Where’s the cheese? In: Proc. of The Workshop on...
J. Kennedy et al.
Particle Swarm Optimization

There are more references available in the full text version of this article.

Cited by (53)

Processing of micro-CT images of granodiorite rock samples using convolutional neural networks (CNN), Part II: Semantic segmentation using a 2.5D CNN
2023, Minerals Engineering
X-ray computed tomography (XCT) is routinely used in geosciences for the purpose of rock characterisation. High-quality micro-CT images are successfully used for fracture characterisation, as well as analysis of grains and pores. In contrast, the use of XCT for mineral identification is uncommon and often ineffective. Implementation of micro-CT imaging techniques for mineral identification is affected by the accuracy and precision of the image segmentation results. Conventional segmentation methods such as thresholding, watershed, and active contouring are user-biased and do not provide the robust distinction between various heavy accessory minerals in granite rocks. Heavy ore minerals such as pyrite, chalcopyrite, molybdenite, and ilmenite are readily recognised in grey-scale micro-CT images because of their high attenuation coefficient, but further differentiation between these minerals using only traditional segmentation methods is challenging. Conversely, deep convolutional neural networks (CNNs) are fully self-trained, and they have demonstrated accurate semantic segmentation results for rock images. However, the application of CNN semantic segmentation for igneous rocks is not well documented. In this research, the U-Net 2.5D CNN was deployed to train the neural network on a combination of high-resolution micro-CT and mineral liberation analysis (MLA) images to identify different accessory mineral regions of interest (ROIs). The image segmentation results were assessed using MLA and SEM data, and the accuracy of segmentation was found to be greater than 97%. The methodology developed in this study can be extended to map the mineralogy of granite samples unseen by the CNN to further validate the robustness of the approach.
Building façade element extraction based on multidimensional virtual semantic feature map ensemble learning and hierarchical clustering
2022, International Journal of Applied Earth Observation and Geoinformation
Building façade elements are an important foundation for smart cities. As buildings exhibit an array of textures and geometric forms, the process of image acquisition is easily affected, although the robustness of texture in scenes (e.g., dilapidated buildings) is poor, with high point cloud data, and low recognition efficiency; therefore, the accuracy of building element extraction based on a single data source remains limited. In this research, a method for building façade element extraction based on multidimensional virtual semantic feature map ensemble learning and hierarchical clustering is proposed. Point clouds were obtained by multi-view images, and then the multidimensional virtual semantic feature maps, including color, texture, orientation, and curvature semantics, were acquired via reprojection. The multi-semantic feature block pre-segmentation, considering multiple features, was obtained by ensemble learning, and a hierarchical clustering strategy was established for to achieve fine extraction of building façade elements. Experiments were conducted across multiple building types, and the results showed that: 1) The method can use different virtual semantic feature map and clustering strategies to achieve accurate extraction of diverse building façade elements; 2) The method achieved joint learning tasks in both 2D and 3D space; and, 3) The proposed method achieved fine extraction of building elements with pixel accuracy (PA) over 70% in all experiments and mean intersection over union (mIoU) up to 95%, which were better than the image based method. In summary, this method offers a novel, more reliable method for segmenting and extracting building façade elements, which has important theoretical and practical significance.
Human mental search-based multilevel thresholding for image segmentation
2020, Applied Soft Computing
Multilevel thresholding is one of the principal methods of image segmentation. These methods enjoy image histogram for segmentation. The quality of segmentation depends on the value of the selected thresholds. Since an exhaustive search is made for finding the optimum value of the objective function, the conventional methods of multilevel thresholding are time-consuming computationally, especially when the number of thresholds increases. Use of evolutionary algorithms has attracted a lot of attention under such circumstances. Human mental search algorithm is a population-based evolutionary algorithm inspired by the manner of human mental search in online auctions. This algorithm has three interesting operators: (1) clustering for finding the promising areas, (2) mental search for exploring the surrounding of every solution using Levy distribution, and (3) moving the solutions toward the promising area. In the present study, multilevel thresholding is proposed for image segmentation using human mental search algorithm. Kapur (entropy) and Otsu (between-class variance) criteria were used for this purpose. The advantages of the proposed method are described using twelve images and in comparison with other existing approaches, including genetic algorithm, particle swarm optimization, differential evolution, firefly algorithm, bat algorithm, gravitational search algorithm, and teaching-learning-based optimization. The obtained results indicated that the proposed method is highly efficient in multilevel image thresholding in terms of objective function value, peak signal to noise, structural similarity index, feature similarity index, and the curse of dimensionality. In addition, two nonparametric statistical tests verified the efficiency of the proposed algorithm, statistically.
Social spiders optimization and flower pollination algorithm for multilevel image thresholding: A performance study
2016, Expert Systems with Applications
Citation Excerpt :
In fact, several biologically inspired global optimization algorithms have been recently proposed to deal with image multilevel thresholding. Within this context, we can refer to examples of genetic algorithms (GA) (Fan & Lin, 2007; Hammouche, Diaf, & Siarry, 2008; Manikandan et al., 2014; Tang, Yuan, Sun, Yang, & Gao, 2011; Yin, 1999; Zhang et al., 2014), particle swarm optimization algorithm (PSO) (Gao, Xu, Sun, & Tang, 2010; Gao, Xu, Sun, & Tang, 2013; Ghamisi et al., 2014; Maitra & Chatterjee, 2008; Yin, 2007), ant colony optimization algorithms (ACO) (Tao, Jin, & Liu, 2007), bacterial foraging algorithm (BFO) (Bakhshali & Shamsi, 2014; Sanyal, Chatterjee, & Munshi, 2011; Sathya & Kayalvizhi, 2011a, 2011b), honey bee mating optimization (HBMO) (Horng, 2010a, 2010b), firefly algorithm (FFA) (Horng & Liou, 2011; Raja, Rajinikanth, & Latha, 2014; Yang, 2009), wind driven optimization (WDO) (Bayraktar, Komurcu, Bossard, & Werner, 2013; Bayraktar, Turpin, & Werner, 2011; Bhandari, Singh, Kumar, & Singh, 2014), cuckoo search (CS) (Bhandari et al., 2014; Panda, Agrawal, & Bhuyan, 2013; Sanjay, Rutuparna, Sudipta, & Panigrahib, 2013; Brajevic, Tuba & Bacanin, 2012), artificial bee colony (ABC) (Akay, 2013; Bhandari, Kumar, & Singh, 2015; Cuevas, Sención, Zaldivar, Pérez-Cisneros, & Sossa, 2012; Horng, 2011; Kumar, Kumar, Sharma, & Pant, 2013; Ma, Liang, Guo, Fan, & Yin, 2011; Zhang & Wu 2011), harmony search (HS) algorithm (Oliva, Cuevas, Pajares, Zaldivar, & Perez-Cisneros, 2013), differential evolution (DE) (Cuevas, Zaldivar, & Pérez-Cisneros, 2010; Ouadfel & Meshoul, 2014; Sarkar, RanjanPatra, & Das, 2011), electromagnetism optimization (EMO) (Oliva et al., 2014). More recently, new metaheuristics have been developed based on the simulation of natural systems such as the flower pollination (FP) algorithm (Yang, 2012) and the social spider optimization (SSO) (Cuevas, Cienfuegos, Zaldivar, & Perez, 2013).
In this paper, we investigate the ability of two new nature-inspired metaheuristics namely the flower pollination (FP) and the social spiders optimization (SSO) algorithms to solve the image segmentation problem via multilevel thresholding. The FP algorithm is inspired from the biological process of flower pollination. It relies on two basic mechanisms to generate new solutions. The first one is the global pollination modeled in terms of a Levy distribution while the second one is the local pollination that is based on random selection of local solutions. For its part, the SSO algorithm mimics different natural cooperative behaviors of a spider colony. It considers male and female search agents subject to different evolutionary operators. In the two proposed algorithms, candidate solutions are firstly generated using the image histogram. Then, they are evolved according to the dynamics of their corresponding operators. During the optimization process, solutions are evaluated using the between-class variance or Kapur's method. The performance of each of the two proposed approaches has been assessed using a variety of benchmark images and compared against two other nature inspired algorithms from the literature namely PSO and BAT algorithms. Results have been analyzed both qualitatively and quantitatively based on the fitness values of obtained best solutions and two popular performance measures namely PSNR and SSIM indices as well. Experimental results have shown that both SSO and FP algorithms outperform PSO and BAT algorithms while exhibiting equal performance for small numbers of thresholds. For large numbers of thresholds, it was observed that the performance of FP algorithm decreases as it is often trapped in local minima. In contrary, the SSO algorithm provides a good balance between exploration and exploitation and has shown to be the most efficient and the most stable for all images even with the increase of the threshold number. These promising results suggest that the SSO algorithm can be effectively considered as an attractive alternative for the multilevel image thresholding problem.
Optimal multilevel thresholding using molecular kinetic theory optimization algorithm
2014, Applied Mathematics and Computation
Multilevel thresholding is one of the most widely used techniques for image segmentation. However, the conventional multilevel thresholding methods are time-consuming algorithms since they exhaustively search for the optimal thresholds to optimize the objective functions. In this paper, a molecular kinetic theory optimization algorithm (MKTOA) is applied to overcome this drawback. MKTOA is used to find the optimal threshold values for maximizing the Kapur’s and Otsu’s objective functions. Three different methods are compared to this proposed method: the molecular force based particle swarm optimization (MPSO) algorithm, the differential evolution (DE) algorithm and the bacterial foraging (BF) algorithm. Experimental results show that MKTOA is much better in terms of robustness, computational efficiency, peak signal to noise ratio (PSNR) and ability to conquer “the Curse of Dimensionality” than MPSO, DE and BF.
Multi-level image thresholding by synergetic differential evolution
2014, Applied Soft Computing Journal
Citation Excerpt :
All works on neural networks illustrated that the methods of neural networks were capable in handling image segmentation problems. Taking into account the advantages of the evolutionary algorithms (EAs), the deployment of thresholding techniques based on it have flourished in recent years [4–8,10,12–16]. It has been shown that these techniques offer better performances than the classical approaches due to their domain independent nature and the capability of finding optimal or near optimal solutions in a large search space.
The multi-level image thresholding is often treated as a problem of optimization. Typically, finding the parameters of these problems leads to a nonlinear optimization problem, for which obtaining the solution is computationally expensive and time-consuming. In this paper a new multi-level image thresholding technique using synergetic differential evolution (SDE), an advanced version of differential evolution (DE), is proposed. SDE is a fusion of three algorithmic concepts proposed in modified versions of DE. It utilizes two criteria (1) entropy and (2) approximation of normalized histogram of an image by a mixture of Gaussian distribution to find the optimal thresholds. The experimental results show that SDE can make optimal thresholding applicable in case of multi-level thresholding and the performance is better than some other multi-level thresholding methods.

View all citing articles on Scopus

View full text

A multi-level thresholding approach using a hybrid optimal estimation algorithm

Abstract

Introduction

Section snippets

Minimum error thresholding by Gaussian model

Hybrid PSO + EM method

Experimental results

Concluding remarks

Acknowledgements

Pattern Recognition Lett.

Signal Process.

Pattern Recognition Lett.

A hybrid simplex search and particle swarm optimization for unconstrained optimization

Eur. J. Oper. Res.

Particle Swarm Optimization