Two-dimensional cross entropy multi-threshold image segmentation based on improved BBO algorithm

LI Wei, HU Xiao-hui, WANG Hong-chuang

(School of Electronic and Information Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China)

0 Introduction

Biogeography-based optimization (BBO) algorithm is a population evolutionary algorithm proposed by American scholar Dan S in 2008 based on biogeography theory and species migration mathematical model[1]. BBO algorithm has its unique features. BBO algorithm calculates the immigration rate and emigration rate of each generation by the fitness value of individual, and improves the quality of low quality solution through high quality solution. BBO algorithm has been successfully applied to a variety of practical problems since it was proposed. For example, Roy et al. used BBO algorithm to optimize the optimal power flow problem[2]. Chen et al. applied the BBO algorithm to the economic dispatch problem of power system reform[3]. However, BBO algorithm is also inadequate, and its convergence rate is relatively fast at the beginning of the evolution process, then it is easy to fall into local optimization and premature[4]. In order to improve the performance of BBO algorithm and correct the above shortcomings, in this paper, the migration and mutation of traditional BBO algorithm are improved.

Threshold segmentation is a kind of image segmentation method which is widely used. The key is how to select the appropriate threshold to obtain the best segmentation results. The most commonly used threshold methods are the maximum Tsallis entropy method, the maximum entropy method and the cross entropy method etc[5]. Multi-threshold segmentation needs to search an optimal threshold combination in the whole gray range. The computational complexity is large and the time and space complexity are high. From the view of improving the optimal threshold search mechanism, researchers introduced the optimization algorithm to solve the problem[6].

In this paper, the problem of multithreshold segmentation is discussed. The migration and mutation operators of BBO algorithm are improved to some extent. The algorithm efficiency is improved and the algorithm can converge to the global optimal solution quickly, and the improved BBO algorithm is applied to the multi-threshold image segmentation based on two-dimensional cross entropy.

1 Basic BBO algorithm

In BBO algorithm, each individual is called as a habitat. Each habitat is judged by means of habitat suitability indices (HSI). The D dimension of the characteristic variable for habitat suitability is suitable index vector (SIV). Changes of HSI in habitats depend on migration and variation of species. Species in the search for the most suitable habitat not only change the habitat environment, but also improve the species diversity of the habitat[7-8].

In BBO algorithm, information sharing between habitats is achieved through immigration rates and emigration rates. Immigration rateλiand emigration rateμiare expressed as

λi=I(1-Si/Smax),

(1)

μi=E(Si/Smax),

(2)

whereIis the biggest immigration rate,Eis the largest emigration rate,Siis the current population quantity,Smaxis the maximum population size.

The BBO algorithm consists of two main operations: migration and mutation operation. In BBO algorithm, the index of a species looking for its habitat is the migration rate, and the index of choosing a species to move out from its habitat is the emigration rate. Thus, migration actions enable species to migrate from high migration rates to habitats with high immigration rates, thereby improving the suitability index for migratory habitats with high immigration rates. The pseudo code of the migration operation is expressed as following algorithm 1, whereNis the number of habitats,Dis the characteristic numbers in a single habitat,rand(0,1) is the random number between (0,1).

Algorithm1Migration operator

Fori=1 toN

Forj=1 toD

According to the high immigration rateλiselect the habitat to be moved in

Ifrand(0,1)<λi

Choose the features that need to be changedHi(i,j);

According to high emigration rateμiselect the habitatHjto be moved out

Ifrand(0,1)<μi

Select features that need to be moved outHj(i,j)

Then the featureHj(i,j) in theHjreplace the featureHi(i,j) in theHi

End if

End if

End for

End for

The main steps of BBO mutation algorithm is: firstly, select a habitat of mutation, then select a characteristic variable of the habitat variation, finally, replace the variables with variables of random selection. The probability of variationmiis related to the prior probabilityPiof species. The variation can be written as

mi=mmax(1-Pi/Pmax),

(3)

wheremmaxis custom parameter,Pmax=maxPirepresents the maximum variance probability.

The pseudo code of mutation operator is expressed as algorithm 2.

Algorithm2Mutation operator

Fori=1 toN

Select habitats to be mutatedHi

Calculatemiaccording toPi. Then, select the featureHi(i,j) withmi

Ifrand(0,1)

ReplaceHi(i,j) by randomly generated eigenvalues

End if

End for

2 Improved BBO algorithm

2.1 Selection operation

Prior to the first migration and mutation, the initial population is evaluated by HSI, thus retaining several excellent solutions. Then, each migration and mutation retains the optimal solution of the new set and compares it with the optimal solution retained by the previous generation. If the new solution is better than the reserved old solution, the new solution is used to replace the old one, otherwise the old solution is retained. This method not only accelerates the convergence speed, but also helps the subsequent migration and mutation. The pseudo code of the selection operator is represented as algorithm 3, in whichNPrepresents the number of good solutions,HSIjrepresents the value of the suitability index of the old solution, andHSIxrepresents the value of the fitness index of the new solution.

Algorithm3Select operator

Fori=itoNP

IfHSIj(i)

Replace old solutions with new ones

End if

Else retain old solutions

End for

2.2 Improved migration operations

For BBO algorithm, the traditional migration operations are carried out among existing habitats, and the global search capability is poor. Moreover, for the migration operations of the traditional BBO algorithm, it is not always good for the habitat with a higher immigration rate. In addition, if each move is carried out from the same habitat with higher emigration rate, the diversity of the final population will be reduced, which will slow the convergence rate and eventually fall into the local optimum. In order to improve its global search capability and make migration more effective, in this paper, we will optimize the selection of the moving species of BBO algorithm, and optimize the migration by using the retained excellent solution. The optimization is

Hi←He+R(-1,1)(Hr-He),

(4)

whereHiis selected habitats for moving in,Heis selected habitats for removal,Hris one of the best chosed solutions,R(-1,1) represents the random number between [-1,1].

The pseudo code algorithm 4 of the migration strategy is shown as follows.

Algorithm4Improved migration operator

Fori=1 toN

Forj=1 toD

According to immigration rateλiselect the habitatHito be moved in

Ifrand(0,1)<λi

Choose the features that need to be changedHi(i,j);

According to emigration rateμiselect the habitatHeto move out

Ifrand(0,1)<μi

Select features that need to be moved outHe(i,j).

End if

End if

End for

End for

2.3 Binary mutation operation

The traditional mutation operations in BBO algorithm use random generated eigenvalues instead of the original eigenvalues of the selected habitat. This method not only has certain blindness, but also leads to slow convergence of BBO algorithm. For this reason, this paper proposes a method to calculate the eigenvalues of the selected habitat by means of binary values, so as to obtain better variation eigenvalues. Therefore, the blindness caused by the variation of the traditional BBO algorithm is reduced to some extent, and the convergence speed is improved to a certain extent. Its performance is

Hi←Hr1+Fi⊗(Hr2⊕Hr),

(5)

where “⊕” means XOR operation, “⊗” is representation and operation,Hr1andHr2represent two randomly generated different eigenvalues,Hris the best individual to retain the operation,Firepresents binary variation scale factor that is randomly generated binary bit strings. The pseudo code for mutation policy is shown in algorithm 5.

Algorithm5Mutation operator

Fori=1 toN

Select habitats to be mutatedHi

Themiis computed according toPi, and then the featureHi(i,j) is selected bymi

Ifrand(0,1)

The eigenvalues calculated by Eq.(5) instead ofHi(i,j)

End if

End for

3 Multi-threshold image segmentation

3.1 Two-dimensional cross entropy for multi-threshold image segmentation

Studies have found that the two-dimensional histogram method ignores the straight part of the boundary zone and zone in the region near the noise threshold, and the calculation is relatively complex. So, in order to improve the segmentation accuracy and reduce the computational complexity, two-dimensional diagonal cross entropy method is used[9-10].

Compared with the two-dimensional histogram, the two-dimensional oblique method divides the histogram into two parts, and the optimal threshold vector (T,S) from the straight point becomes the best thresholdTin the oblique segmentation method. The computational complexity of the threshold method is reduced. The method of threshold two-dimensional cross entropy threshold is described as follows:

Fig.1 Two-dimensional oblique method

1) As shown in Fig.1(a), when 0

(6)

(7)

(8)

2) As shown in Fig.1(b), whenL-1

(9)

(10)

(11)

According to Eqs.(6)-(11), the criterion function of two-dimensional cross entropy threshold selection can be obtained as

(12)

In this paper, two-dimensional cross entropy single threshold segmentation is extended to multi-threshold segmentation, as shown in Fig.2, wherecbrepresents the background andc0,c1,…,ckstand for the target.

Fig.2 Multi-threshold oblique division

According to Eq.(12), the threshold values areT1,T2,…,Tk, and the corresponding two dimensional cross entropy is

∂(T1,T2,…,Tk)=∂(c0)+∂(c1)+…+∂(ck)=

(13)

3.2 Multi-threshold image segmentation based on improved BBO algorithm

Fig.3 Flow chart

1) Read into the picture, smooth processing, build two-dimensional histogram, initialize parameters, set the population number asP, the number of threshold asN.

2) The initial habitat matrixMis randomly generated withProw andNcolumn.

3) The entropy of each candidate solution is calculated by the criterion function, and the candidate solution is sorted in descending order according to the entropy. The algorithm 3 in this paper is implemented for retaining several candidate solutions.

4) Perform the migration of the algorithm 4. When the change of the candidate solution value is not obvious, the algorithm 5 in this paper is implemented, and multation is started.

5) Again, perform the algorithm 3 operation in this paper.

6) If the value of the optimal candidate solution remains almost constant, the loop is finished and the optimal candidate solution is obtained, otherwise, go to 4).

7) The best solution is used to segment the image and output the segmented image.

In this paper, BBO algorithm sets 2 ideal rules:

1) All habitats have the same species.

2) Habitat suitability depends on the criterion function.

4 Results

In this paper, the proposed method is implemented using MATLAB (R2014b, Math Works, Inc., Natick, MA, USA), all programs are carried out on a computer with 2.4 GHz 4-core CPU, 4 GB memory and Windows operating system (Microsoft Corporation, Redmond, WA, USA).

Experiment is carried out to evaluate the performance of our proposed method. Two standard graphs of baboon (512×512) and fingerprint (512×512) with 3, 4 and 5 threshold segmentation are used in this paper, respectively. The experimental results are compared with two-dimensional multi-threshold segmentation of particle swarm optimization (PSO) algorithm and the standard BBO algorithm. In this paper, all programs run 40 times independently. Besides the initialization parameters of the three algorithms are the same.

The following Fig.4 is three standard images of rice, fingerprint and baboon for image segmentation. In order to reflect the segmentation effect better, 3, 4 and 5 threshold segmentation are carried out for the three images in this paper. Fig.4(a) is the original image, Figs.4(b)-(d) are the 3 threshold image segmentation, 4 threshold image segmentation, 5 threshold image segmentation of the three algorithms. Among them, the display sequence from top to bottom is PSO algorithm, standard BBO algorithm and the proposed algorithm in this paper.

Fig.4 Experimental results

As seen from Table 1, when running in rice graph with the proposed method, the time of 3 threshold, 4 threshold, 5 threshold are 0.18, 0.56 and 0.92 s respectively, and the uniformity are 0.928 5, 0.942 8 and 0.974 2. Running in fingerprint graph with the proposed method, the time of 3 threshold, 4 threshold, 5 threshold are 0.12, 0.52 and 0.82 s respectively, and the uniformity are 0.865 4, 0.923 1 and 0.957 6. Running in baboon graph with the proposed method, the time of 3 threshold, 4 threshold, 5 threshold are 0.21, 1.32 and 1.70 s respectively, and the uniformity are 0.853 1, 0.956 5 and 0.973 2. Compared with the other two segmentation algorithms, the proposed algorithm has less running time and higher consistency in the three images.

Table 1 Experimental data sheet

For threshold segmentation results, the quality of segmentation is usually judged by the naked eye, but this is not scientific. So it is necessary to choose a scientific way to judge the result of segmentation. In this paper, the performance of segmentation algorithm is evaluated by image segmentation quality evaluation index and region consistency.

A good segmentation algorithm should be able to generate segmentation results within regions that have similarity (consistency). The consistency of this feature can be obtained by calculating the characteristic variance in the region, that is

wherei=1,…,krepresents the segmented target area respectively,krepresents the number of thresholds,i=0 stands for thekbackground area,Airepresents the number of pixels in the region,σirepresents the variance of pixels in the region,sumrepresents the total number of pixels in the entire image[11].

It can be seen from the segmentation effect, the two-dimensional cross entropy multi-threshold image segmentation method based on the improved BBO algorithm is superior to two-dimensional multi-threshold segmentation of standard BBO algorithm and PSO algorithm, and the stability of the algorithm is improved. In addition, the method in this paper can improve the segmentation efficiency a little.

The two-dimensional cross entropy multi-threshold segmentation method based on the standard BBO algorithm is a multi-threshold image segmentation method based on the traditional migration and mutation strategy. The standard BBO algorithm may not change the fitness index of the affected habitat during migration, and there is no specific variation direction in the mutation operation.

Based on the improved BBO algorithm, the two-dimensional cross entropy multi-threshold segmentation method has the advantages as follows:

1) The improved BBO algorithm can effectively change the premature convergence and invalidation of the migration operation;

2) The improved BBO algorithm can effectively change the blindness of mutation operation;

3) Combining the improved BBO algorithm with the two-dimensional cross entropy multi-threshold segmentation method, the optimal solution can be obtained quickly and the segmentation efficiency can be improved.

Based on the above analysis, we can draw the conclusion that the two-dimensional cross entropy multi-threshold image segmentation method based on the improved BBO algorithm can segment images quickly and effectively.

5 Conclusion

In this paper, a two-dimensional cross entropy multi-threshold image segmentation method based on improved BBO algorithm is proposed. The algorithm aims to reduce the complexity of image segmentation and improve the seg-mentation performance.Firstly, the theory of standard BBO algorithm is expounded. Secondly, the idea of improved BBO algorithm is put forward. Finally, this paper expounds the two-dimensional cross entropy threshold segmentation theory, which is extended to multi-threshold segmentation, and the segmentation method is applied on the standard image. Experimental results show that the segmentation method proposed in this paper is an effective image segmentation algorithm.

[1] Dan S. Biogeography-based optimization. IEEE Transactions on Evolutionary Computation, 2008, 12(6): 702-713.

[2] Roy P K, Ghoshal S P, Thakur S S. Biogeography-based optimization for multi-constraint optimal power flow with emission and non-smooth cost function. Expert Systems with Applications, 2010, 37(12): 8221-8228.

[3] Chen Z, Hu Z J. A modified hybrid PSO-BBO algorithm for dynamic economic dispatch. Power System Protection & Control, 2014, 42(18): 44-49.

[4] Xiong G J, Shi D Y, Duan X Z. Enhancing the performance of biogeography-based optimization using polyphyletic migration operator and orthogonal learning. Computers & Operations Research, 2014, 41(1): 125-139.

[5] Zhang X M, Zheng Y B. Precise 2-D Tsallis entropy image threshold segmentation and its fast recursive realization. Chinese Journal of Scientific Instrument, 2011, 32(8): 1796-1802.

[6] Sathya P D, Kayalvizhi R. Modified bacterial foraging algorithm based multilevel thresholding for image segmentation. Engineering Applications of Artificial Intelligence, 2011, 24(4): 595-615.

[7] Ma H P, Li X, Lin S D. Analysis of mobility model of biogeography-based optimization algorithm. In: Proceedings of China Intelligent Automation Conference, 2009: 16-21.

[8] Wu B, Lin J G, Cui Z Y. Comparison of migration operator in biogeography-based optimization algorithm. Computer Engineering and Applications, 2012, 48(25): 61-64.

[9] Wan S, Liu J, Yu B. Exponential cross entropy thresholding for seal image based on 2-dimensional oblique segmentation. Microcomputer & Its Applications, 2013, 47(12): 38-42.

[10] Fang J L, Lei B. Two-dimensional cross-entropy linear-type threshold segmentation method for gray-level images. Acta Electronica Sinica, 2009, 35(4): 751-755.

[11] Hou G X, Bi D Y, Wu C K. Study on image segm-entation quality evaluation method. Journal of Image and Graphics, 2000, 5(1): 42-46.