A multilevel color image thresholding scheme based on minimum cross entropy and differential evolution

doi:10.1016/j.patrec.2014.11.009

Pattern Recognition Letters

Volume 54, 1 March 2015, Pages 27-35

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

Highlights

•
A new multi-level thresholding approach is proposed for color images.
•
The minimum cross-entropy approach is extended to color images.
•
Simple evolutionary search is used to solve the underlying optimization problem.
•
The proposed method is validated by using the Berkley Segmentation Datasets.

Abstract

We propose a novel multi-level thresholding method for unsupervised separation between objects and background from a natural color image using the concept of the minimum cross entropy (MCE). MCE based thresholding techniques are widely popular for segmenting grayscale images. Color image segmentation is still a challenging field as it involves 3-D histogram unlike the 1-D histogram of grayscale images. Effectiveness of entropy based multi-level thresholding for color image is yet to be explored and this paper presents a humble contribution in this context. We have used differential evolution (DE), a simple yet efficient evolutionary algorithm of current interest, to improve the computation time and robustness of the proposed algorithm. The performance of DE is also investigated extensively through comparison with other well-known nature inspired global optimization techniques like genetic algorithm (GA), particle swarm optimization (PSO), and artificial bee colony (ABC). The proposed method is evaluated by comparing it with seven other prominent algorithms both qualitatively and quantitatively using a well known benchmark suite – the Barkley Segmentation Dataset (BSDS300) with 300 distinct images. Such comparison reflects the efficiency of our algorithm

Introduction

Image segmentation, the process of partitioning an image into meaningful parts or objects, appears as a fundamental step in many image, video, and computer vision related applications. It is a critical step towards content analysis and interpretation of various types of images such as medical images, satellite images, and natural images. For the first two types, gray scale images are the preferred and available source, while for later, the color images are widely acceptable.

Segmentation obtained through bi-level thresholding subdivides an image into two homogenous regions based on texture, histogram, edge etc. In literature, several image segmentation techniques, such as gray level thresholding, interactive pixel classification, neural network based approaches, edge detection, and fuzzy rule based segmentation have been reported [1], [2], [3], [4], [5], [6]. Among these methods, gray level global thresholding techniques are the most popular ones and many algorithms have been proposed in this direction, see for example the works of Kapur et al. [7], Wong and Sahoo [8], Pal [9], Li and Lee [10], Otsu [11] and Rosin [12].

Entropy-based global thresholding scheme has received considerable attention from the researchers, working on segmentation. The principal assumption of entropy-based global thresholding stands on the entropy of the image histogram as a summation of two regions – the object(s) and the background. Recent developments in information theory have intensified the opportunity to investigate the use of various entropies to find efficient separation between objects and background. Some of these such as Shannon entropy, Renyi entropy [13], Tsallis entropy [14], and cross entropy [15] etc. have been widely used for thresholding images. Among the nonparametric approaches cross entropy proposed by Kullback [16] is perhaps the most preferable technique. Note that all the above mentioned techniques are for bi-level thresholding. A more practical approach for image thresholding is to consider multiple levels so that the image may be divided into more than one objects and background. However the main problem associated with multi-level thresholding is its large time complexity [17], [18], [19], [20]. Researchers used various methods to enhance the computational speed of multi-level thresholding based approaches see for example [21], [22], [23], [24], [25]. Formulating total entropy as an objective function and solving it by using global optimization algorithms attracted considerable attention in recent years [26].

Metaheuristics provide a very popular way to yield near optimal solutions of a wide variety of complex optimization problems without requiring the knowledge of derivatives or without being sensitive to the choice of initial solutions. Derivative-free metaheuristic optimizers, based on the simulations of some natural phenomena, have been widely used for segmenting images through both bi-level and multi-level thresholding, see for example [27], [28], [29], [30], [31]. Applications of some well-known metaheuristics like genetic algorithms (GAs) [32], particle swarm optimization (PSO) [27], [33], [34], artificial bee colony (ABC) [68] etc. can also be found in literature on segmentation and thresholding. differential evolution (DE) is arguably one of the most powerful as well as popular evolutionary real-parameter optimizers of current interest [35], [36]. It has been shown that DE can outperform state-of-art metaheuristics like GA and PSO when it is used for multi-level thresholding based image segmentation [37], [38], [39]. However, all the above mentioned algorithms were tested on grayscale images. For segmentation of practical interest a color image is more acceptable than the gray scale images.

Color image segmentation involves subdividing an image into homogeneous regions based on the color information, texture, and edges. However, unsupervised natural color image segmentation still remains a challenge for the researchers. Several works have been published in the last two decades in this direction. Some of the well cited techniques are mean-shift clustering [40], [41], graph based methods [42], [43], region based split and merge techniques [44], [45], Markov random field models [46], histogram based method [47], hybrid methods [48], [49], texture based color image segmentation [50], pixel clustering [51], principal component analysis based method [52] etc. The entropy based methods are yet to be applied on color images for achieving natural segmentation.

In this work, we propose an automatic multi-level color image thresholding scheme based on the minimum cross entropy thresholding (MCET) computationally aided with the DE algorithm. DE is used to reduce the computational time for optimization while still maintaining sufficient accuracy. Extensive simulations have been undertaken to demonstrate the efficiency and robustness of the DE based scheme in comparison to three other popular nature-inspired optimization techniques: GA, PSO, and ABC. An extensive comparative study is also presented on the 300 images from the Berkeley Segmentation Dataset (BSDS 300) involving seven no-evolutionary segmentation methods and on the basis of the performance metrics like probability rand index (PRI), variation of information (VOI), global consistency error (GCE), and boundary displacement error (BDE) in context to multilevel thresholding. The outcomes of the DE-based MCET segmentation is tested for different number of threshold levels and assessed by using human made segmentations on the basis of the aforementioned performance metrics. The experimental results reported in this study are also compared with some widely popular color image segmentation schemes.

The paper is organized in the following way. Section 2 briefly introduces the cross entropy and multi-level minimum cross entropy along with their mathematical formulations. The DE algorithm is outlined in Section 3. Section 4 describes the proposed approach in sufficient details. Experimental results of applying the proposed method to the BSDS 300 benchmarks along with statistical analyses and comparison with other metaheuristics and segmentation algorithms have been provided in Section 5. Finally the paper is concluded in Section 6.

Section snippets

Cross entropy

Let F = {f₁, f₂, …, f_N} and G = {g₁, g₂, …, g_N} be two probability distributions on the same set. The cross entropy between F and G is defined by [16]: $D (F, G) = \sum_{i = 1}^{N} f_{i} \log \frac{f_{i}}{g_{i}} .$

In order to understand the concept of multilevel thresholding of color images, we briefly overview the bi-level thresholding for color images. The performance of the segmentation algorithm is partially dependent on the choice of color spaces due to non uniform illumination of regions. Literature reveals that perceptually

Differential evolution (DE)

The initial generation of a standard DE algorithm [35], [36] consists of the four basic steps – initialization, mutation, recombination or crossover, and selection, of which, only last three steps are repeated into the subsequent DE generations. The generations continue till some termination criterion (such as exhaustion of maximum functional evaluations) is satisfied.

The ith individual (parameter vector) of the population at generation G is a D-dimensional vector containing a set of D

Color image segmentation based on multi-level MCET

In this section we describe the color image segmentation process using the idea of multi-level MCET and DE. The histogram for color images h(i) is calculated and used (as in Eq. (6)) to form the objective function for the DE algorithm. The threshold values are attained by minimizing the objective function and the segmented RGB color images are formed with these threshold values. The RGB color space is used to demonstrate differences of regions more prominently.

For better discrimination between

Experimental setup

All the simulations have been performed using MATLAB R2012a in a workstation with Intel® Coreۛ i3 3.2 GHz processor. The DE/rand/1/bin scheme (it is the DE/rand/1 scheme explained in Section 3 with the binomial crossover) is used to compute the threshold levels efficiently. The parametric settings of DE, GA, PSO, and ABC have been adopted using the guidelines provided in the respective literatures [26], [39]. Results have been obtained by replacing DE with these algorithms in the same procedure

Conclusion

A histogram based natural color image segmentation technique by using multi-level minimum cross entropy and an evolutionary algorithm (DE) is proposed. MCET based approach aided with DE delivers acceptable results in reasonable amount of computational time. DE has been shown to outperform three widely known derivative-free metaheuristic global optimizers GA, PSO, and ABC. A popular region merging technique called statistical region merging is applied along with MCET to obtain more

References (68)

FuK.S. et al.
A survey on image segmentation
Pattern Recogn.
(1981)
PalN.R. et al.
A review on image segmentation techniques
Pattern Recogn.
(1993)
SahooP.K. et al.
A survey of thresholding techniques
Comput. Vis. Graphics Image Process.
(1988)
KapurJ.N. et al.
A new method for gray-level picture thresholding using the entropy of the histogram
Comput. Vis. Graphics Image Process.
(1985)
PalN.R.
On minimum cross entropy thresholding
Pattern Recogn.
(1996)
LiC.H. et al.
Minimum cross entropy thresholding
Pattern Recogn.
(1993)
RosinP.L.
Unimodal thresholding
Pattern Recogn.
(2001)
SahooP.K. et al.
A thresholding method based on two dimensional Renyi's entropy
Pattern Recogn.
(2004)
LiC.H. et al.
An iterative algorithm for minimum cross entropy thresholding
Pattern Recogn. Lett.
(1998)
KittlerJ. et al.
Minimum error thresholding
Pattern Recogn.
(1986)

PunT.

Entropy thresholding: a new approach

Comput. Vis. Graphics Image Process.

(1981)

WangS. et al.

A novel image thresholding method based on Parzen window estimate

Pattern Recogn.

(2008)

ZaharaE. et al.

Optimal multi-thresholding using a hybrid optimization approach

Pattern Recogn. Lett.

(2005)

DiramiA. et al.

Fast multilevel thresholding for image segmentation through a multiphase level set method

Signal Process.

(2013)

AroraS. et al.

Multilevel thresholding for image segmentation through a fast statistical recursive algorithm

Pattern Recogn. Lett.

(2008)

SezginM. et al.

A new dichotomization technique to multilevel thresholding devoted to inspection applications

Pattern Recogn. Lett.

(2000)

YinP.Y. et al.

A fast iterative scheme for multilevel thresholding methods

Signal Process.

(1997)

HammoucheK. et al.

A comparative study of various meta-heuristic techniques applied to the multilevel thresholding problem

Eng. Appl. Artif. Intell.

(2010)

AkayB.

A study on particle swarm optimization and artificial bee colony algorithms for multilevel thresholding

Appl. Soft Comput.

(2013)

TaoW.B. et al.

Image segmentation by three-level thresholding based on maximum fuzzy entropy and genetic algorithm

Pattern Recogn. Lett.

(2003)

BaziY. et al.

Image thresholding based on the EM algorithm and the generalized Gaussian distribution

Pattern Recogn.

(2007)

HammoucheK. et al.

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

Comput. Vis. Image Und.

(2008)

TangK. et al.

An improved scheme for minimum cross entropy threshold selection based on genetic algorithm

Knowl.-Based Syst.

(2011)

YinP.Y.

Multilevel minimum cross entropy threshold selection based on particle swarm optimization

Appl. Math. Comput.

(2007)

ChengH.D. et al.

Color image segmentation based on homogram thresholding and region merging

Pattern Recogn.

(2002)

Siang TanK. et al.

Color image segmentation using histogram thresholding–Fuzzy C-means hybrid approach

Pattern Recogn.

(2011)

YuZ. et al.

An adaptive unsupervised approach toward pixel clustering and color image segmentation

Pattern Recogn.

(2010)

HanY. et al.

Variational and PCA based natural image segmentation

Pattern Recogn.

(2013)

YangA.Y. et al.

Unsupervised segmentation of natural images via lossy data compression

Comput. Vis. Image Und.

(2008)

HuangR. et al.

Image segmentation via coherent clustering in L^∗a^∗b^∗ color space

Pattern Recogn. Lett.

(2011)

DerracJ. et al.

A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms

Swarm Evol. Comput.

(2011)

SezginM. et al.

Survey over image thresholding techniques and quantitative performance evaluation

J. Electron. Imaging

(2004)

DeyV. et al.

A review on image segmentation techniques with remote sensing perspective

ZhangaH. et al.

Image segmentation evaluation: a survey of unsupervised methods

Comput. Vis. Image Und.

(2008)

Cited by (143)

Lévy–Cauchy arithmetic optimization algorithm combined with rough K-means for image segmentation
2023, Applied Soft Computing
Rough K-Means (RKM) is a well-known unsupervised clustering algorithm based on rough set logic that is utilized in a wide range of applications. However, when dealing with complex problems like image segmentation, it is frequently trapped in local optima during execution, resulting in undesirable segmentation results. To handle the issue in a realistic computing time, this study develops a Lévy–Cauchy Arithmetic Optimization Algorithm (LCAOA), an enhanced form of AOA, for performing rough clustering. The Levy flight and Cauchy distribution help in exploration and exploitation, respectively, in the proposed LCAOA. Therefore, well-balanced exploration and exploitation have been incorporated into LCAOA, which is a major problem of classical AOA. Opposition-based learning is also incorporated into LCAOA to maintain an efficient population during the optimization process. As the segmentation efficacy is somewhat dependent on the selection of color spaces caused by the non-illumination of regions, the suggested method employs the CIELab color space. The suggested method is compared to conventional and Nature-Inspired Optimization Algorithms (NIOA)-based state-of-the-art image segmentation techniques over traditional color images, color pathology images, and leaf images. The proposed clustering methodology outperforms all other examined clustering algorithms, according to the results of the experiments. For example, proposed LCAOA-based rough clustering gives average Feature Similarity Index (FSIM) values of 0.9513, 0.9688, and 0.9769 for traditional color images with 4, 6, and 8 clusters, respectively. The proposed technique is associated with an average FSIM value of 0.9525 for cluster number 2 in images of oral pathology. Lastly, for leaf images, the proposed approach yields a mean FSIM value of 0.9759 with an accuracy of greater than 97% for cluster number 2.
A novel minimum generalized cross entropy-based multilevel segmentation technique for the brain MRI/dermoscopic images
2022, Computers in Biology and Medicine
One of the challenging and the primary stages of medical image examination is the identification of the source of any disease, which may be the aberrant damage or change in tissue or organ caused by infections, injury, and a variety of other factors. Any such condition related to skin or brain sometimes advances in cancer and becomes a life-threatening disease. So, an efficient automatic image segmentation approach is required at the initial stage of medical image analysis.
To make a segmentation process efficient and reliable, it is essential to use an appropriate objective function and an efficient optimization algorithm to produce optimal results.
The above problem is resolved in this paper by introducing a new minimum generalized cross entropy (MGCE) as an objective function, with the inclusion of the degree of divergence. Another key contribution is the development of a new optimizer called opposition African vulture optimization algorithm (OAVOA). The proposed optimizer boosted the exploration, skill by inheriting the opposition-based learning.
The experimental work in this study starts with a performance evaluation of the optimizer over a set of standards (23 numbers) and IEEE CEC14 (8 numbers) Benchmark functions. The comparative analysis of test results shows that the OAVOA outperforms different state-of-the-art optimizers. The suggested OAVOA-MGCE based multilevel thresholding approach is carried out on two different types of medical images – Brain MRI Images (AANLIB dataset), and dermoscopic images (ISIC 2016 dataset) and found superior than other entropy-based thresholding methods.
HWOA: A hybrid whale optimization algorithm with a novel local minima avoidance method for multi-level thresholding color image segmentation
2022, Expert Systems with Applications
Traditional methods to address color image segmentation work efficiently for bi-level thresholding. However, for multi-level thresholding, traditional methods suffer from time complexity that increases exponentially with the increasing number of threshold levels. To overcome this problem, in this paper, a new approach is proposed to tackle multi-threshold color image segmentation by employing the Otsu method as an objective function. This approach is based on a hybrid of the whale optimization algorithm (WOA) with a novel method called the local minima avoidance method (LMAM), abbreviated as HWOA. LMAM avoids local minima by updating the whale either within the search space of the problem or between two whales selected randomly from the population-based on a certain probability. HWOA is validated on ten color images taken from the Berkeley University Dataset by measuring the objective values, peak signal-to-noise ratio (PSNR), structural similarity index (SSIM), features similarity index (FSIM), and CPU time, and compared with a number of the well-known robust meta-heuristic algorithms: the sine–cosine algorithm (SCA), WOA, modified salp swarm algorithm (MSSA), improved marine predators algorithm (IMPA), modified Cuckoo Search (CS) using McCulloch’s algorithm (CSMC), and equilibrium optimizer (EO). The experimental results show that HWOA is superior to all the other algorithms in terms of PSNR, FSIM, and objective values, and is competitive in terms of SSIM.
An unsupervised segmentation method based on dynamic threshold neural P systems for color images
2022, Information Sciences
Citation Excerpt :
Table 2 provides a comparison of the proposed method and other compared methods on BSD300. The compared methods include DSA [13], SFFCM [15], PRIF [21], DEA [33], MCE-DE [34], ATP [39], WCP [40], UHIS-FEM [44] and 2DKLMPSO [48]. It can be seen in Table 2 that DTNP achieves the best value for VOI and GCE metrics, and DTNP has a better value of PRI metric.
Dynamic threshold neural P (DTNP) systems are a new variant of spiking neural P (SNP) systems, abstracted by the spiking and dynamic threshold mechanisms of biological neurons. Motivated by the two mechanisms, this paper develops a novel segmentation method for color images. For this purpose, a 2-dimentional DTNP system with local topology is designed. The spiking mechanism of neurons is used to achieve regional growth, and dynamic threshold is considered to realize the choice of seeds. Moreover, local weights that combine color information can control the regional growth. The proposed segmentation method is evaluated on two benchmark Berkeley segmentation data sets (BSD300 and BSD500) and is compared with 17 state-of-the-art segmentation methods. Experimental results demonstrate the availability and effectiveness of the proposed segmentation method for color images.
An improved symbiotic organisms search algorithm for higher dimensional optimization problems
2022, Knowledge-Based Systems
The symbiotic organisms search (SOS) algorithm was introduced by considering the relationships among the creatures in a natural ecosystem. Despite the superior efficiency of SOS, it has been observed that fixing benefit factors of mutualism phase at 1 or 2; the algorithm obstructs itself from an extensive and diverse search of the search region. Moreover, alteration of random dimensions in the parasitism phase increases the computational burden of the algorithm. Considering these limitations, a modified SOS algorithm, namely nwSOS, has been proposed in this study to solve higher dimensional optimization problems. In the suggested nwSOS, the benefit factors are calculated by a non-linear approach. The mutual vector is modified, and weights of both benefit factors are utilized to effectively explore and exploit the search region. Moreover, the parasitism phase is tailored to lessen the computational overhead. The modified method is then used to evaluate twenty basic benchmark functions using 100 and 500 dimensions. Results are compared with six state-of-the-art algorithms and with SOS and its five modified variants. Four designing issues from both unconstrained and constrained classifications are solved utilizing nwSOS. Complexity analysis, statistical analysis, and convergence analysis are executed to measure the algorithm’s effectiveness from different aspects. Moreover, the proposed algorithm has been used for segmenting COVID-19 chest X-ray images with the help of multi-level thresholding approach using different thresholds. All the results confirmed the enhancement of the proposed algorithm.
A two-phase quasi-affine transformation evolution with feedback for parameter identification of photovoltaic models
2021, Applied Soft Computing
Metaheuristic algorithm is a prestigious technique for solving optimization problems. QUATRE is a simple but powerful algorithm. However, QUATRE also shows premature convergence and is easily trapped in local optima for complex optimization problems. This work presents a novel algorithm named two-phase QUasi-Affine Transformation Evolution with feedback (tfQUATRE). The proposed tfQUATRE is an enhanced quasi-affine transformation evolution algorithm. In tfQUATRE, a two-phase approach is introduced to improve the exploration and exploitation abilities by adjusting the search tendency at different phases. Moreover, the historical population is employed for the feedback approach to guide the search towards promising areas to maintain population diversity, which boosts the exploration ability. The comprehensive performance of tfQUATRE is evaluated in the simulations. First, the performance of tfQUATRE is evaluated under the CEC2017 test suite. The simulations prove that tfQUATRE is superior to 12 state-of-the-art algorithms. In addition, tfQUATRE is applied to extract the parameters of photovoltaic (PV) systems in real application. The experimental results confirm that the proposed tfQUATRE is more competitive than 17 recent counterparts.

View all citing articles on Scopus

: This paper has been recommended for acceptance by S. Sarkar.

View full text