Image segmentation using multilevel thresholding based on modified bird mating optimization

Abstract

Multilevel thresholding using Otsu or Kapur methods is widely used in the context of image segmentation. These methods select optimal thresholds in gray level images by maximizing between-class variance or entropy criterion. These methods become time consuming and less efficient with increasing number of thresholds. To increase the efficiency of the image segmentation using multilevel thresholding based on Kapur and Otsu methods, we developed a hybrid optimization algorithm named BMO-DE based on bird mating optimization (BMO) and differential evolutionary (DE) algorithms. The efficiency of the proposed method was evaluated on eight standard benchmark images. The proposed method achieved better segmentation results in term of solution quality and stability in comparison with other well-known techniques including bacterial foraging (BF), modified bacterial foraging (MBF), particle swarm optimization (PSO), genetic algorithm (GA) and hybrid algorithm named PSO-DE.

1 Introduction

Image segmentation is the process of partitioning an image into a number of homogenous regions, each containing pixels with similar attributes like intensity or texture. It is considered as an important pre-processing step in applications such as object detection and tracking, and medical image analysis [8, 12, 22, 29, 31, 37, 39, 40, 46, 48]. One of the widely used methods for image segmentation is thresholding. It can be classified into bi-level and multilevel thresholding depending on the number of regions. In bi-level thresholding, the image pixels are classified into two regions, with gray levels greater or less than a certain threshold. In multilevel thresholding, an input image is segmented into several distinct regions with multiple thresholds [3, 7, 17, 22]. As an efficient tool, histogram thresholding can be used for image segmentation. However, finding the exact location of valleys in a multimodal histogram is not trivial.

The optimal thresholds in bi-level or multilevel thresholding can be determined using parametric or non-parametric approaches [14]. In the parametric approach, a probability density function is assigned to each class (region) with the distribution parameters computed by using the least-squares methods. In the non-parametric approaches, the thresholding method searches for optimal thresholds in the histogram by optimizing an objective function based on some criteria such as between-class variance (Otsu’ [28]) or entropy [19]. However, all of these methods are computationally complex and less efficient due to the exhaustive search especially when the number of thresholds increases.

Recently, evolutionary algorithms inspired by biological evolution have been combined with multilevel thresholding algorithms such as Genetic Algorithm (GA) [11], Particle swarm optimization (PSO) [9, 13, 18, 26, 33, 44] bacterial foraging algorithm (BFO) [36, 37], differential evaluation (DE) [34, 43], artificial bee colony (ABC) [2, 16], cuckoo search (CS) [1, 32], watershed algorithm [47], fuzzy logic [24], hybrid method [30], honey bee mating optimization (HBMO) [15], wind driven optimization (WDO) [5], self-adaptive parameter optimization [23], grey wolf optimizer (GWO) [20], Whale Optimization Algorithm (WOA) and Moth-Flame Optimization (MFO) [10] for optimal multilevel thresholding. The multilevel thresholding using evolutionary algorithms have been applied in various applications including brain tissue segmentation from magnetic resonance images [21, 25, 38, 41] and satellite hyper-spectral image segmentation [6, 35]. Among all the multilevel thresholding algorithms, GA, PSO and BFO have shown good segmentation results with significant reduced computational cost for multilevel thresholding using Otsu criterion or Kapur’s entropy.

Although the evolutionary algorithms provide promising results for finding optimal thresholds in comparison with the parametric approaches, most of them exhibits slow convergence and may get trapped in local minima highly affecting their quality of segmentation [20]. The hybridization of the evolutionary methods is a practical solution to overcome this limitation by improving their efficiency in terms of convergence speed and solution quality.

Recently, Askarzadeh [4] proposed the bird mating optimization (BMO) algorithm, a population based method based on bird mating phenomenon, in which each bird attempts to breed a quality brood as much as possible. BMO employs distinct patterns to move through the search space without being trapped in local extrema. Thus, it can explore the search space and generate new solutions while maintaining the population diversity. Although BMO presents promising results in solving optimization problems, it is still inefficient in terms of convergence speed and quality of solution [49]. In order to improve the quality of the BMO solution, we introduce a hybrid algorithm (called BMO-DE) based on BMO and the differential evolutionary (DE) algorithm. DE is an easy-to-use general search algorithm with a simple structure holding acceptable convergence properties; however it may get trapped in local minima. The proposed hybrid algorithm BMO-DE was used to efficiently solve the multilevel thresholding problem for image segmentation by using the objective functions of Kapur’s and Otsu’s methods.

The paper is organized as follows: Section 2 presents the Kapur’s and Otsu’s methods for multilevel thresholding. Section 3 gives an overview of the ‌BMO, DE and proposed hybrid BMO-DE algorithms. The application of the proposed BMO-DE algorithm for multilevel thresholding is presented in Section 4. Finally, performance evaluation and conclusion are given in sections 5 and 6, respectively.

2 Optimal thresholding methods

Suppose a given image has N pixels and L gray levels over [0, L-1]. The probability of gray level i is given as follows:

$$ {P}_i=\frac{f_i}{N},\kern0.5em N=\sum \limits_{i=0}^{L-1}{f}_i,\kern0.5em i=0,1,...,L-1 $$

(1)

Where f_i is the number of pixels with gray level i. In optimal thresholding methods optimal thresholds are found such that the segmented classes satisfy desired properties. We used the entropy criterion (Kapur’s) and between-class variance (Otsu’s) method to perform image segmentation via multilevel thresholding.

2.1 Entropy criterion method

The Kapur’s method for image thresholding maximizes the posterior entropy by measuring the homogeneity of image regions [19, 45]. According to this criterion, the objective function based on bi-level thresholding is described as follows:

$$ fit(x)={H}_1+{H}_2 $$

(2)

where

$$ {\displaystyle \begin{array}{cc}{H}_1=-\sum \limits_{i=0}^{x-1}\frac{P_i}{w_1}\ln \frac{P_i}{w_1},& {w}_1=\sum \limits_{i=0}^{x-1}{P}_i\\ {}{H}_2=-\sum \limits_{i=x}^{L-1}\frac{P_i}{w_2}\ln \frac{P_i}{w_2},& {w}_2=\sum \limits_{i=x}^{L-1}{P}_i\end{array}} $$

(3)

Gray level that maximizes eq. 2 is considered as the optimal threshold x.

The Kapur’s method can be extended to multilevel thresholding to find c thresholds X = [x₁, x₂, ..., x_c] by maximizing the following objective function:

$$ fit(X)={H}_1+{H}_2+...+{H}_c $$

(4)

where

$$ {\displaystyle \begin{array}{l}{H}_1=-\sum \limits_{i=0}^{x_1-1}\frac{P_i}{w_1}\ln \frac{P_i}{w_1}\kern0.84em ,{w}_1=\sum \limits_{i=0}^{x_1-1}{P}_i\\ {}{H}_2=-\sum \limits_{i={x}_1}^{x_2-1}\frac{P_i}{w_2}\ln \frac{P_i}{w_2}\kern0.6em ,{w}_2=\sum \limits_{i={x}_1}^{x_2-1}{P}_i\\ {}\kern0.6em \vdots \\ {}{H}_c=-\sum \limits_{i={x}_c}^{L-1}\frac{P_i}{w_c}\ln \frac{P_i}{w_c}\kern0.6em ,{w}_c=\sum \limits_{i={x}_c}^{L-1}{P}_i\kern0.36em \end{array}} $$

(5)

where H₁, H₂, ..., H_care the Kapur’s entropies and w₁, w₂, ..., w_care the probabilities of the segmented classes.

2.2 Between-class variance method

Otus’s method selects the optimal threshold at levelx, which maximizes the between-class variance. According to this threshold, the input image is divided into two classes: C₁ and C₂; where class C₁includes gray levels from 0 to x − 1 and class C₂ consists of gray levels from x to L − 1. The cumulative probabilities w₁ and w₂, and the mean gray levels μ₁ and μ₂ for classes C₁ and C₂are defined as follows:

$$ {w}_1=\sum \limits_{i=0}^{x-1}{P}_i,\kern0.5em {\mu}_1=\sum \limits_{i=0}^{x-1}i\times \frac{P_i}{w_1} $$

(6)

$$ {w}_2=\sum \limits_{i=x}^{L-1}{P}_i,\kern0.5em {\mu}_2=\sum \limits_{i=x}^{L-1}i\times \frac{P_i}{w_2} $$

(7)

The optimum threshold is selected in a way that maximizes the objective function:

$$ fit(x)={\sigma}_1+{\sigma}_2 $$

(8)

where

$$ {\sigma}_1={w}_1{\left({\mu}_1-{\mu}_{Total}\right)}^2,\kern0.5em {\sigma}_2={w}_2{\left({\mu}_2-{\mu}_{Total}\right)}^2 $$

(9)

and μ_Total is the mean intensity of the whole image defined as follows:

$$ {\mu}_{Total}={w}_1{\mu}_1+{w}_2{\mu}_2 $$

(10)

This process can be extended to multilevel thresholding:

$$ fit(X)={\sigma}_1+{\sigma}_2+...+{\sigma}_c $$

(11)

where

$$ {\displaystyle \begin{array}{c}{\sigma}_1={w}_1{\left({\mu}_1-{\mu}_{Total}\right)}^2,\\ {}{\sigma}_2={w}_2{\left({\mu}_2-{\mu}_{Total}\right)}^2,\\ {}\vdots \\ {}{\sigma}_c={w}_c{\left({\mu}_c-{\mu}_{Total}\right)}^2\end{array}} $$

(12)

and c thresholds are defined as X = [x₁, x₂, ..., x_c].

3 Proposed BMO-DE method

3.1 Bird mating optimization (BMO)

BMO is a meta-heuristic optimization algorithm based on mating behavior of birds. In this algorithm the population is called society and each member of the society is named bird, which represents a feasible solution. The society has two parts consisting of males and females. The birds in the society are responsible to breed a quality brood as much as possible. The female birds are classified into parthenogenetics and polyandrous. The males are divided into three groups namely monogamous, polygynous and promiscuous. According to the mating pattern of the birds, BMO possesses five updating patterns, each of them has different updating phase and produces a solution as described below [4].

Monogamy is a mating system that a male bird mates with one female. Each monogamous bird selects an interesting female by evaluating the quality of the female birds in a probabilistic approach and mates with her. The chance of each female depends on promising gens of that female. In this system the new offspring brood is generated as follows:

$$ {\displaystyle \begin{array}{l}{\overrightarrow{X}}_b=\overrightarrow{X}+W\times \overrightarrow{r}\times \left({\overrightarrow{X}}^l-\overrightarrow{X}\right)\\ {} for\ m=1\ to\ c\\ {} if\ {r}_1> mcf\\ {}\kern1em {X}_b(m)= lb(m)-{r}_2\times \left( lb(m)- ub(m)\right)\\ {} else\\ {}\kern1em {X}_b(m)=X(m);\\ {}\kern0.5em end\ if\\ {} end\ for\end{array}} $$

(13)

The first part of Eq. 13 shows that by combining the monogamous bird $\overrightarrow{X}$ with the interesting female ${\overrightarrow{X}}^l$, the new brood ${\overrightarrow{X}}_b$ inherits the good genes from his parents. In this equation, W is a time-varying weight showing the role of the interesting female on each of the offspring broods. $\overrightarrow{r}$denotes a c dimensional vector, in which each element has a uniform distribution between 0 and 1, and c is the dimension of the problem. The second part of the Eq. 13 defines the mutation operation in one of the brood’s genes with the probability of 1 − mcf, where lb and ub are lower and upper bounds of the dimension of the problem and r_n is a random variable between 0 and 1.

Polygyny indicates a mating system that polygynous bird mates with several female birds to have better genes for the brood. The new offspring brood is calculated as below:

$$ {\displaystyle \begin{array}{l}{\overrightarrow{X}}_b=\overrightarrow{X}+W\times \sum \limits_{k=1}^{nl}{\overrightarrow{r}}_k\times \left({\overrightarrow{X}}_k^l-\overrightarrow{X}\right)\\ {} for\ m=1\ to\ c\\ {}\kern0.75em if\ {r}_1> mcf\\ {}\kern2em {X}_b(m)= lb(m)-{r}_2\times \left( lb(m)- ub(m)\right)\\ {}\kern0.75em else\\ {}\kern1.25em {X}_b(m)=X(m);\\ {}\kern0.5em end\ if\\ {} end\ for\end{array}} $$

(14)

where n_lis the number of interesting female birds.

Promiscuity is a mating system in which two birds have unstable relationships. This mating presents a chaotic sequence. In this system a male bird mates with one female according to Eq. 13.

Parthenogenesis is another mating system that each female can raise brood without the help of males. By making a small change in genes of each female the offspring brood is generated as follows:

$$ {\displaystyle \begin{array}{l} for\kern0.24em m=1\kern0.36em to\kern0.24em c\\ {}\kern0.36em if\kern0.24em {r}_1> mcfp\\ {}\kern0.72em {X}_b(m)=X(m)+ mu\times \left({r}_2-{r}_3\right)\times X(m);\\ {} else\\ {}\kern0.6em {X}_b(m)=X(m);\\ {}\kern0.36em end\; if\\ {} end\; for\end{array}} $$

(15)

where mcfp and mu are the mutation control factor and the step size, respectively.

Polyandry implies a mating system that a female bird mates with several males. The polyandrous bird choices monogamous males probabilistically. The brood is generated using Eq. 14.

3.2 Differential evolution (DE)

The differential evolution (DE) algorithm is an evolutionary optimization technique introduced by Storn and Price in 1995 [42]. DE with good global search ability uses crossover and mutation operators like GA but with different mechanism. In c dimensional search spaces, each individual in the DE population is produced by X_j = (x_{j, 1},  … , x_{j, c}) from the feasible solution space. At each generation, mutant vectors (X_mut, X_mut1, X_mut2and X_mut3) are generated for each individual according to the following three strategies:

$$ {\displaystyle \begin{array}{l}{X}_{mut}={X}_{p0}+{F}_1\times \left({X}_{p1}-{X}_{p2}\right)\\ {}{X}_{mut\;1}={X}_{p0}+{F}_1\times \left({X}_{p1}-{X}_{p2}\right)+{F}_2\times \left({X}_{best}-{X}_{worst}\right)\\ {}{X}_{mut2}={F}_3\times \left({X}_{best}-{X}_{worst}\right)+{X}_{p3}\\ {}{X}_{mut3}={X}_{p0}+{F}_1\times \left({X}_{p4}-{X}_{p3}\right)\end{array}} $$

(16)

where p0, p1, p2, p3 and p4 are the different random integer numbers from [1, N_pop] and N_pop is the size of the population. In order to adjust the difference vectors F₁, F₂ and F₃ are chosen as scaling factors selected randomly by using normal distribution.

After applying mutation, trial vectors X_new, X_new1, X_new2 and X_new3 named crossover vectors are produced by crossover operation based on X_jand X_mut, X_mut1, X_mut2, and X_mut3 vectors as:

$$ {\displaystyle \begin{array}{l}\begin{array}{cc}{x}_{new,m}=\Big\{{}_{x_{j,m}}^{x_{mut1,m}}& \begin{array}{l} if\ \mathit{\operatorname{rand}}< CR\ or\ m=z\\ {} otherwise\end{array}\\ {}{x}_{new1,m}=\Big\{{}_{x_{j,m}}^{x_{mut3,m}}& \begin{array}{l} if\ \mathit{\operatorname{rand}}< CR1\ or\ m=z\\ {} otherwise\end{array}\end{array}\\ {}\begin{array}{cc}{x}_{new2,m}=\Big\{{}_{x_{mut2,m}}^{x_{mut,m}}& \begin{array}{l} if\ \mathit{\operatorname{rand}}< CR2\ or\ m=z\\ {} otherwise\end{array}\\ {}{x}_{new3,m}=\Big\{{}_{x_{mut1,m}}^{x_{mut,m}}& \begin{array}{l} if\ \mathit{\operatorname{rand}}< CR3\ or\ m=z\\ {} otherwise\end{array}\end{array}\\ {}m=\mathrm{1...}c\kern0.5em \end{array}} $$

(17)

where x_{j, m} and x_{new, m}, x_{new1, m}, x_{new2, m}, x_{new3, m} are the m^th dimensional components of the vectors X_j and x_new, x_new1, x_new2, x_new3, respectively. CR, CR1, CR2 and CR3 are the crossover constants, which are usually set to fixed values within (0,1); z is an integer number that is randomly chosen from the index set {1, 2, ..., c}, which makes sure crossover vectors get at least one parameter from mutant vectors.

3.3 Hybrid BMO-DE algorithm

The proposed hybrid evolutionary algorithm (called BMO-DE) was developed by integrating DE into BMO for updating population (society). We used DE to improve the solution quality of the BMO algorithm. The proposed hybrid algorithm was implemented as follows:

• Step 1: Initialization: an initial society S is randomly generated as $S=\left[{X}_1,{X}_2,...,{X}_{N_{pop}}\right]$ where X_j = [x₁, ...x_c] represents the j^th bird in the society.

• Step 2: Fitness function: in this step, a constrained optimization problem with regard to predefined variables should be solved:

$$ Fit(X)= fit(X)-{k}_1\left(\sum \limits_{a=1}^{N_{eq}}{\left({h}_a(X)\right)}^2\right)-{k}_2\left(\sum \limits_{b=1}^{Nueq}{\left(\mathit{\operatorname{Max}}\left[0,-{g}_b(X)\right]\right)}^2\right) $$

(18)

where fit(X) is the objective function; N_eq and N_ueq are the number of equality and inequality constraints of the problem, respectively; h_a(X) for a = 1, ..., N_eq and g_b(X) for b = 1, ..., N_ueq are constraints that should be fulfilled; and k₁ and k₂ are the penalty coefficients that are set in order to meet the constraints. If there are no constraints in the problem, the penalty coefficients are set to zero and the value of the fitness function Fit(X) and the objective function fit(X) are equal.

• Step 3: Ranking and classification: the birds in the society are ranked and classified into two groups (male and female) according to their fitness function. The females are equally divided into two groups as parthenogenetic and polyandrous birds. The males are categorized into three groups called monogamous, polygynous and promiscuous.

• Step 4: Breeding: select the j^th bird and calculate a brood using its pattern.

• Step 5: Replacement: replace the new brood with its own bird if it has a better quality.

• Step 6: Hybrid BMO-DE: apply the DE to the j^th brood of the monogamous or polygynous birds. If the quality of the DE mutant vector is better than its own brood, the brood abandons the society and the DE vector is joined to the society as a new brood.

• Step 7: repeat steps 4–6 until all birds are evaluated.

• Step 8: if the termination criterion is satisfied, stop the search procedure. Otherwise, replace the initial population with the current population and go back to step 3.

• Step 9: the bird with the best quality is selected from the society as the final solution.

The flowchart of the hybrid BMO-DE is illustrated in Fig. 1.

Fig. 1

The flowchart of the proposed hybrid BMO-DE algorithm

4 Image segmentation using the proposed BMO-DE

In the society of birds, they are responsible to breed a quality brood with superior genes. In the multilevel thresholding problem, the proposed BMO-DE algorithm is applied to imitate the behaviour of birds to breed broods (optimal threshold values) that optimize objective functions given by Eqs. 4 or 11. The image histogram is the input of this algorithm and the optimal bird ${\overrightarrow{X}}_b$, which represents the optimal threshold is the output.

Suppose that to find c thresholds for the segmentation problem, the search space is c-dimensional and the j^th bird can be represented by a c-dimensional vectorX_j = [x_{j, 1}, x_{j, 2}, ..., x_{j, c}] of the possible real values corresponding to the thresholds. In the first stage of the proposed multilevel thresholding method, an initial society consisting of N_pop vectors X_j = [x_{j, 1}, x_{j, 2}, ..., x_{j, c}], j = 1, ..., N_pop is generated randomly as birds according to Eq. 19:

$$ {x}_{j,k}=\mathit{\operatorname{rand}}(.)\times \left({x}_{\max, k}-{x}_{\min, k}\right)+{x}_{\min, k} $$

(19)

Where x_{min, k} and x_{max, k} are the minimum and maximum of the gray levels in the input image and the birds X_j = [x_{j, 1}, x_{j, 2}, ..., x_{j, c}] (thresholds) are initialized within this range. Each bird with length c is a feasible solution of the thresholding problem. The fitness function is used to assess the quality of each bird X_j. Since there are no constraints in our problem, the objective function and fitness function in Eq. 18 are the same. Therefore, the fitness function is calculated based on Kapur’s entropy (Eq. 4) or Otsu’s criterion (Eq. 11) for each bird X_j in the society.

In the second stage, the birds of the society (thresholds) are sorted based on their quality (value of fitness function) and they are classified into males and females. The females are those birds that have promising genes (i.e. the most fitness function value) and they are equally divided into two groups: i) parthenogenetic group with better genes (better thresholds) and ii) polyandrous group. On the other hand, the males are categorized into three groups (step 3 in subsection 3.3). The better ones make the first group named monogamous and the birds in the second group are named polygynous. The birds in the third group, named promiscuous, have the worse quality (worse threshold) are excluded from the society and replaced with ones that are generated using a chaotic sequence. Each bird as an optimal threshold breeds a brood according to its pattern (Eqs. 13 to 15). The bird (threshold in the previous iteration) can be replaced with its own brood (threshold in the new iteration) if the quality of the brood is better, in other words, it has a fitness function value greater than that of its parent.

In the third stage, DE is applied to each brood of the monogamous or polygynous birds based on Eqs. 16 and 17. If the fitness function value of the DE mutant vector is better than that of its own brood, the brood is updated with the DE vector. The search procedure is repeated until the termination criterion is satisfied. The bird X_j with the best quality, a vector consisting of c thresholds, represents the final solution of the multilevel thresholding problem.

5 Performance evaluation

The performance of the proposed method and that of other well-known methods including PSO, GA, BF, MBF [37] and hybrid PSO-DE algorithm [27] was evaluated on standard test images: Lena, Peppers, Baboon, Hunter, Cameraman, Living room, Airplane and Butterfly. The original images and their corresponding histograms are shown in Fig. 2. The proposed BMO-DE based multilevel thresholding method was implemented in MATLAB using a Pentium(R) Dual core 2.30 GHz and 2 GB of memory. The mean and standard deviation of the objective function values as well as the corresponding CPU time were reported within a range of thresholds for each multilevel thresholding method included in the study.

Fig. 2

Original gray level test images and the corresponding histograms that are used to perform experiments. The size of images are 512 × 512. (a) Lena, (b) Peppers, (c) Baboon, (d) Hunter, (e) Cameraman, (f) Living room, (g) Airplane and (h) Butterfly

5.1 Segmentation result

Figures 3 and 4 show the segmentation results obtained by the proposed BMO-DE methods based on Kapur’s entropy and Otsu criteria using three thresholds, respectively. As shown, the segmentation accuracy was improved significantly with increasing the number of thresholds.

Fig. 3

Segmentation of test images using the proposed BMO-DE-Kapur multilevel thresholding method. The first, second and third columns represent the segmented image into four (c = 3), five (c = 4) and six (c = 5) regions, respectively. From top to bottom: Lena, Peppers, Baboon, Hunter, Cameraman, Living room, Airplane and Butterfly

Fig. 4

Segmentation of test images using the proposed BMO-DE-Otsu multilevel thresholding method. The first, second and third columns represent the segmented image into four (c = 3), five (c = 4) and six (c = 5) regions, respectively. From top to bottom: Lena, Peppers, Baboon, Hunter, Cameraman, Living room, Airplane and Butterfly

5.2 Solution quality

Tables 1 and 2 show the mean (± std) objective values obtained using both Otsu’s and Kapur’s objective functions for BMO-DE, PSO-DE, GA, PSO, BF and MBF. The corresponding threshold values are shown in Tables 3 and 4. In order to evaluate the stability of the evolutionary methods for multilevel thresholding we computed the standard deviation (std) of their objective function values over K runs as follows [37]:

$$ std=\sqrt{\sum \limits_{a=1}^K\frac{\left({\delta}_a-\mu \right)}{K}} $$

(20)

Table 1 The mean and std. of objective function values for different threshold levels (c = 2,3,4,5) obtained by Kapur based BMO-DE, PSO-DE, MBF, BF, PSO and GA algorithms. The asterisks show statistical differences between our algorithm and each of the other approaches using t-test at a significance level of 0.05

Table 2 The mean and std. of objective function values at 50 runs for different threshold levels (c = 2,3,4,5) obtained by Otsu based BMO-DE, PSO-DE, MBF, BF, PSO and GA algorithms. The asterisks show statistical differences between our algorithm and each of the other approaches using t-test at a significance level of 0.05

Table 3 The optimal threshold values obtained by BMO-DE, PSO-DE, GA, PSO, BF and MBF based Kapur’s entropy methods for different threshold levels (c = 2,3,4,5)

Table 4 The optimal threshold values obtained by BMO-DE, PSO-DE, GA, PSO, BF and MBF based Otsu’s entropy methods for different threshold levels (c = 2,3,4,5)

where K is number of runs for each algorithm, δ_ais the best objective value obtained by the a^th run of the algorithm, and μ is the mean value of δ. A lower standard deviation indicates higher stability for the algorithm. We evaluated the stability of the evolutionary algorithms over 50 runs (K = 50). As shown in Tables 1 and 2, the proposed method exhibited higher stability in comparison with other methods using both Otsu’s and Kapur’s objective functions. We also performed a statistical analysis using t-test at a significance level of 0.05 to assess the significant differences between the objective values of the proposed algorithm and those of PSO-DE, MBF, BF, PSO and GA over the runs. The statistical differences (P < 0.05) between our algorithm and each of the other approaches are shown by asterisks in Tables 1 and 2. Moreover, in most cases our method yielded higher values using both Otsu’s and Kapur’s objective functions. The Kapur based PSO-DE algorithm, however, showed a comparable accuracy to that of our method.

We further evaluated the accuracy of the proposed BMO-DE based multilevel thresholding algorithm on synthetic images corrupted with white Gaussian noise scaled so that the signal to noise ratio (SNR) ranged from 2 to 12 according to eq. 21. Figure 5 shows a series of noisy images containing three layers with different SNR. Figure 6 shows the mean objective function values obtained using the Otsu based BMO-DE multilevel thresholding (two thresholds) algorithm for the noisy images illustrated in Fig. 5. As shown, our method performed better on noisy images with low SNR in comparison with other methods.

$$ SNR=\frac{\mu_{sig}}{\delta_{sig}} $$

(21)

where μ_sig and δ_sigare average and standard deviation of the signal values respectively.

Fig. 5

Synthetic images with three layers and different SNR

Fig. 6

Objective values for Otsu based multilevel thresholding (c = 2) for synthetic images with different SNR

5.3 Computation time

Table 5 shows the computational efficiency of the proposed BMO-DE algorithm for multilevel thresholding in comparison with other evolutionary algorithms in terms of average execution time (CPU time taken in seconds) over 50 runs. Compared to other evolutionary algorithms [37], the proposed BMO-DE multilevel thresholding algorithm provided lower computational time. The comparison between the run time of the Kapur and Otsu based evolutionary algorithms showed that the multilevel thresholding based on Otsu’s objective function was faster.

Table 5 Average CPU time (sec) of BMO-DE, PSO-DE, MBF, BF, PSO and GA based algorithms each at 50 runs

5.4 Advantage and disadvantage of the proposed algorithm

Multilevel thresholding using Kapur’s or Otsu’s algorithms is computationally expensive with increasing number of thresholds. The proposed BMO-DE-based algorithm exhibited significantly reduced computational complexity by reducing efficiently the search space.

Success of the evolutionary algorithms depends on the balance between generation of new solutions in untested regions (exploration) and concentration in the vicinity of the current good solution (exploitation) [4]. The proposed BMO-DE method provides a good balance between the exploration and exploitation parameters, which enable the algorithm to avoid local optima and achieve better performance in comparison with other algorithms.

The main limitation of the proposed segmentation method is its sensitivity to noise and intensity inhomogeneity. In these cases, the fitness function should be improved to use local information derived from neighboring pixels.

6 Conclusion

For image segmentation, the optimal thresholds in bi-level/multilevel thresholding methods can be obtained by maximizing an objective function based on some criteria such as the Otsu’ criterion or Kapur’s entropy, which tries to maximize the between-class variance and the posterior entropy, respectively. These methods achieve good performances for bi-level thresholding. However, by increasing the number of thresholds in multilevel thresholding, the computational complexity is increased and the segmentation accuracy might be affected be getting trapped in local extrema. Thus, a practical solution to overcome these weaknesses is to combine evolutionary methods with multilevel thresholding algorithms. In this paper, we presented a hybrid multilevel thresholding method based on the combined BMO and DE algorithms.

BMO employs distinct patterns to move through the search space without getting trapped in local extrema. It can explore the search space and generate new solutions while maintaining the population diversity. Although BMO presents promising solutions for optimization problems, it is still insufficient in terms of convergence speed and quality of solution [49]. In order to improve the quality of the BMO solution, we proposed an efficient hybrid algorithm, named BMO-DE, based on the BMO and DE algorithms. DE is easy to use, keeps a simple structure, holds acceptable convergence properties and can find the solution rapidly; however it may get trapped in local minima. By hybridization of BMO and DE, these shortcomings can be overcome. The performance of the proposed algorithm was evaluated on eight standard test images. Compared to the other well-known evolutionary algorithms including GA, PSO, BF and MBF, our algorithm achieved better results in terms of solution quality and stability. In future work, we will improve the objective function by integrating the spatial constraints and local information to further improve the accuracy of image segmentation using multilevel thresholding.