Threshold Selection Method Based on Reciprocal Gray Entropy and Artificial Bee Colony Optimization

Wu Yiquan（吳一全），Meng Tianliang（孟天亮），Wu Shihua（吳詩婳），Lu Wenping（盧文平）

1.College of Electronic and Information Engineering，Nanjing University of Aeronautics and Astronautics，Nanjing，210016，P.R.China；2.Engineering Technology Research Center of Wuhan Intelligent Basin，Changjiang River Scientific Research Institute，Changjiang Water Resources Commission of the Ministry of Water Resources，Wuhan，430010，P.R.China；3.Key Laboratory of the Yellow River Sediment of Ministry of Water Resource，Yellow River Institute of Hydraulic Research，Zhengzhou，450003，P.R.China；4.State Key Laboratory of Urban Water Resource and Environment，Harbin Institute of Technology，Harbin，150090，P.R.China；5.State Key Laboratory of Food Science and Technology，Jiangnan University，Wuxi，214122，P.R.China

1 Introduction

Image segmentation is a significant step in the process from image preprocessing to image recognition or visual detection.Thresholding is the most widely used image segmentation meth－od.It is proved to be effective and easy to implement.Thresholding is applied to many fields［1－4］，such as remote sensing image monitoring，machine visual measurement and infrared object detection.The core of thresholding is searching for the optimal threshold quickly to achieve accurate segmentation.The methods［5－6］which take maximum Shannon entropy as the criterion have attracted much attention among existing threshold selection methods.One－dimensional（1－D）maximum Shannon entropy method was first proposed by Kapur，et al［7］.To improve the segmentation effects of noisy images，Abutaleb［8］and Brink［9］extended the 1－D method to two－dimensional（2－D）maximum Shannon entropy threshold selection.Du，et al［10］utilized the particle swarm optimization algorithm to accelerate the processing of 2－D maximum Shannon entropy method.However，the maximum Shannon entropy method searches for the optimal threshold only according to the probability information of gray level，ignoring the gray level uniformity within classes，which results in inaccurate segmentation of some images.Considering the gray level uniformity within classes，a threshold selection method based on Shannon gray entropy was proposed［11］.The gray entropy describes the gray level difference within classes.The larger the gray entropy is，the smaller the gray level difference within classes is，which indicates that the gray levels are more uniform within either objective class or background class，thus superior segmentation effects are achieved.

The maximum Shannon entropy method and the Shannon gray entropy method mentioned above are both based on the logarithmic entropy.However，the logarithm has the drawback of undefined value at zero points，which will cause some troubles when dealing with the data.For this reason，Pal，et al［12］introduced the idea of exponential entropy，and replaced the frequently used Shannon entropy in threshold selection criterion.The problem of undefined value of logarithm was avoided and the maximum exponential entropy threshold selection method was presented.Recently，a reciprocal entropy［13］was introduced as the threshold selection criterion.It also avoided the drawback of Shannon entropy and attained good segmentation effects.Moreover，the involved multiplication and division operations in this reciprocal entropy were less time－consuming than both the logarithm operations in Shannon entropy and the exponent operations in exponential entropy in practical systems.Through the above analysis，if the advantages of reciprocal entropy are combined with those of gray entropy，a more accurate and faster image segmentation method can be expected.Meanwhile，the traditional 2－D histogram region division is kind of unreasonable［14］and has to search for two thresholds，namely original gray level threshold and neighborhood average gray level threshold.If adopting 2－D histogram oblique division，the segmentation will be more accurate，and only one threshold instead of two needs to be computed，thus the running time is significantly reduced.For further improving the processing efficiency，the artificial bee colony（ABC）algorithm proposed lately［15－16］can be adopted.ABC algorithm copies the process of bee gathering nectar.It makes use of local optimizing behavior of each bee to obtain the global optimal value.This algorithm has the advantages of high convergence precision and fast searching speed［17］，and it can properly avoid the local extremum.Thus the real－time performance of reciprocal gray entropy thresholding method with 2－D histogram oblique division can be further improved with the help of ABC optimization.

In view of the above mentioned factors，a new image threshold selection method is proposed based on reciprocal gray entropy with 2－D histogram oblique division and ABC optimization.Firstly，the definition of reciprocal gray entropy is introduced and the 1－D reciprocal gray entropy thresholding method is given.Then the criterion function of 2－D reciprocal gray entropy threshold selection is derived.To improve the real－time performance，ABC optimization is adopted to accelerate the search for optimal threshold.Finally，a large number of experiments have been performed on different kinds of images.And the proposed method is compared with the maximum Shannon entropy method with 2－D histogram oblique division and the maximum reciprocal entro－py method with 2－D histogram oblique division based on niche chaotic mutation particle swarm optimization（NCPSO）is made.

2 1－D Threshold Selection Based on Reciprocal Gray Entropy

Suppose that f（m，n）stands for the gray level of the pixel（m，n）in an image whose size is Mpixel×Npixel and total number of gray levels is L.The number of pixels with gray level i（i＝0，1，…，L－1）is denoted as h（i）.Now the image is segmented into two classes，i.e.，the object class Co＝｛（m，n）｜f（m，n）＝0，1，…，t｝and the background class Cb＝｛（m，n）｜f（m，n）＝t＋1，t＋2，…，L－1｝（We regard dark pixels as the object pixels for convenience）.Suppose

Then the reciprocal gray entropy of the object class is

The reciprocal gray entropy of the background class is

Larger reciprocal gray entropy means the gray levels within classes are more uniform and the segmentation effect is better.Thus the optimal threshold t＊is determined by the maximum value of reciprocal gray entropy

3 2－D Threshold Selection Based on Reciprocal Gray Entropy and Histogram Oblique Division

Suppose the gray level and neighborhood average gray level of the pixel（m，n）are f（m，n）and g（m，n），respectively（written as i and j in the following formulae，i，j＝0，1，…，L－1），and h（i，j）denotes the frequency of the pairs（i，j）.Obviously

The traditional gray level neighborhood average gray level histogram division is shown in Fig.1.Four rectangular regions around the 2－D point（t，s）are obtained.Set of dark pixels，that is lower left quarter of 2－D histogram region，stands for the object region.And the upper right quarter stands for background region.The upper left quarter and the lower right quarter are regarded as regions of edges and noise because the difference between original gray levels and neighborhood average gray levels of the pixels here is large.However，this division does not match the real 2－D gray level probability distribution.Therefore，oblique division manner is adopted to the 2－D histogram region，which is a more accurate division of object class and background class.Moreover the threshold to be computed is reduced to one.As a result，the running time of the proposed method decreases.

Fig.1 Region division of 2－D histogram

In Fig.1，the 2－D histogram region is divided by the straight line g＝－f＋t.Suppose the lower left part of the straight line is object region，and the upper right part is background region.The sums of gray levels of the object class and the background class areμo（t）＝ ［）］Tand μb（t）＝］T，respectively.Their computational methods are given later in this paper.The sum of gray levels of the whole image is

Similar to the 1－D reciprocal gray entropy，the 2－D reciprocal gray entropy H2（t）can be written as

where Ho（t）and Hb（t）stand for the reciprocal gray entropy of the object class and the background class，respectively.They can be calculated by the following formulae.

（1）0≤t≤L－1

（2）L－1＜t≤2L－2

The sums of gray levels of object class and background classμo（t）＝and μb（t）＝can be calculated by recursive algorithm.For example，when 0＜t≤L－1

When L－1＜t≤2L－2，the recursive algorithm is similar，and unnecessary repeating is avoided here.In this way，the algorithmic running time can be reduced to a great extent.The reciprocal gray entropy threshold selection formula with 2－D histogram oblique division is as follows

To further accelerate the search for optimal threshold，ABC optimization is adopted.

4 ABC Optimization Algorithm

ABC algorithm copies the process of bee gathering nectar.It includes three parts，namely leading bees，observation bees and detective bees.

（1）Leading bees

The number of leading bees is denoted by NL.Each leading bee corresponds to a food source.The location of food source is the potential solution of criterion function，or the potential optimal threshold.The profits of food sources are represented by the fitness of solutions

where Xi（i＝1，2，…，NL）denotes the possible solution，f（Xi）denotes the value of objective function which is corresponding to Eq.（5）.Each leading bee looks for a new food source near the last one.The new position is determined by the following formula

whereεis a random number on［－1，1］，Xlthe position of the lth food source（l≠i）.The leading bee chooses the better one from the two food sources in terms of corresponding fitness.

（2）Observation bees

Each observation bee selects a leading bee to follow.Which one to select is determined by the proportion of profits Pi.

According to Eq.（8），the observation bee randomly observes a new food source around the leading bee it follows.The leading bee will come to the food source found by the observation bee if this one is better，otherwise it will stay.

（3）Detective bees

When a leading bee falls into a local extremum，this leading bee turns into a detective bee.It will randomly search a new food source to jump out of the local extremum.

These three parts cycle until the best location is found.The specific procedures applying ABC optimization to reciprocal gray entropy threshold selection method with 2－D histogram oblique division are as follows.

Step 1 Set the controlling values.The number of all the bees is 10，5leading bees and 5observation bees.The max cycle number CMis 10，and the cycle number CLis set to 3，which is used to judge whether a leading bee has fallen into a local extremum.The space to search is［0，510］.

Step 2 Initialize the location Xi（i＝1，2，…，5）of each leading bee.Xiis a random integer in the range［0，510］.Then Eq.（7）is used to calculate the fitness of Xi.

Step 3 According to Eq.（8），each leading bee randomly looks for a new food source Ziaround the old one.The fitness of Ziis calculated，and if Ziis better，its value will replace the last value of Xi.

Step 4 According to Eq.（9），each observation bee picks a leading bee to follow，at the same time it searches for a better food source around the leading bee，and it will also give the better value to Xiif it finds one.

Step 5 If the cycle number reaches CLbut the fitness of Xiis still not improved，then the corresponding leading bee will turn into a detective bee to look for a new food source.

Step 6 When a cycle is over，the optimal solution of this cycle is recorded，and the variable C of cycle number automatically pluses 1.

Step 7 When the cycle number Creaches the max cycle number CM，the iteration progress is finished.Then the image is segmented by the obtained optimal threshold.Otherwise，go to Step 3to continue the cycle progress.

5 Results and Discussion

Experiments have been done on many different kinds of images with the proposed method，and the results are given.A large number of experimental results show that，compared with maximum Shannon entropy method with 2－D histogram oblique division［14］and maximum reciprocal entropy method with 2－D histogram oblique division based on NCPSO［13］，the proposed method has obvious advantages.Now we analyze the effectiveness of the proposed method with two bright images（meat images）（252pixel×200 pixel／1024pixel×739pixel）and two dark images（SAR remote sensing images）（199pixel×199 pixel／205pixel×135pixel）.The corresponding running time is listed in Table 1.The processing environment of all these three methods is Pentium（R）Dual－Core CPU 2.10GHz／2GB，Matlab R2010b.

Figs.2，3are two bright images with low contrast.Since both maximum Shannon entropy method with 2－D histogram oblique division［14］and maximum reciprocal entropy method with 2－Dhistogram oblique division based on NCPSO［13］tend to focus on small targets（small areas with very different gray levels），their segmentation results are not so satisfactory.However，the proposed method takes into account the gray level uniformity within classes，not just the probability distribution.Therefore，better segmentation results are obtained.It can be seen that the proposed method is able to segment meat images excellently.Not only the outlines are clear but also the lean meat areas and the fat meat areas are distinguished accurately.For the same reason，in Fig.4the first two methods regard the highlighted bridge as the target，as a result large area of shadow which is connected with the water area is segmented in the land area.This will surely make troubles for river extraction in the next step.The proposed method segments the river in the SAR remote sensing image 1accurately，meanwhile it keeps the details of land areas well.In Fig.5，maximum Shannon entropy method with 2－D histogram oblique division［14］basically has the river detected，but the edges and details are not clear.Maximum reciprocal entropy method with 2－D histogram oblique division based on NCPSO［13］does not segment the image effectively，the infor－

mation of the river area is annihilated.The result of the proposed method shows river area and land area clearly，and many details are also kept very well.

Table 1 Comparisons of three methods in optimal thresholds and running time

Fig.2 Meat image 1and segmentation results

Fig.3 Meat image 2and segmentation results

Fig.4 SAR remote sensing image 1and segmentation results

Fig.5 SAR remote sensing image 2and segmentation results

From data shown in Table 1，it can be seen that maximum Shannon entropy method with 2－D histogram oblique division［14］can deal with images with small size quickly，but when the size of images is large，the processing time increases rapidly.Maximum reciprocal entropy method with 2－D histogram oblique division based on NCPSO［13］and the proposed method do not suffer from the problem，and both can satisfy the real－time requirement.

6 Conclusions

The definition of reciprocal gray entropy and the 1－D reciprocal gray entropy threshold selection method are introduced.Based on this，reciprocal gray entropy threshold selection method with 2－D histogram oblique division is proposed.Furthermore，ABC optimization algorithm is adopted to accelerate the searching process.The proposed method avoids the drawback of undefined value at zero points of Shannon entropy.Moreover，taking into account the gray level uniformity within classes the image segmentation accuracy is improved.The object and background are segmented accurately and the details in the segmented image are kept very well.A large number of experimental results show that，compared with maximum Shannon entropy method with 2－D histogram oblique division［14］and maximum reciprocal entropy method with 2－D histogram oblique division based on NCPSO［13］，the proposed method has obvious advantages in segmentation effects and can meet the real－time processing requirement.

［1］ An Chengjin，Niu Zhaodong，Li Zhijun，et al.Otsu threshold comparison and SAR water segmentation result analysis［J］.Journal of Electronics and Information Technology，2010，32（9）：2215－2219.（in Chinese）

［2］ Zheng D M，Dai Z D，Wang H M.Development and preliminary application of objectifying system for TCM color inspection［J］.Transactions of Nanjing University of Aeronautics and Astronautics，2012，29（4）：395－403.

［3］ Liu Songlin，Niu Zhaodong，Chen Zengping.Minimum error thresholding for infrared image under constraint of cross entropy［J］.Infrared and Laser Engineering，2014，43（3）：979－984.（in Chinese）

［4］ Gao Weiwei，Shen Jianxin，Wang Yuliang.Comparative approaches for automated detection of hard exudates in fundus images［J］.Journal of Nanjing University of Aeronautics and Astronautics，2013，45（1）：55－61.（in Chinese）

［5］ Cao L，Shi Z K，Cheng K W.Automatic multilevel thresholding method based on maximum entropy［J］.Transactions of Nanjing University of Aeronautics and Astronautics，2005，22（4）：335－338.

［6］ Guo Haitao，Tian Tan，Wang Lianyu，et al.Image segmentation using the maximum entropy of the twodimensional bound histogram［J］.Acta Optica Sinica，2006，26（4）：506－509.（in Chinese）

［7］ Kapur J N，Sahoo P K，Wong A K C.A new method for gray－level picture thresholding using the entropy of histogram［J］.Computer Vision，Graphics and Image Processing，1985，29（1）：273－285.

［8］ Abutaleb A S.Automatic thresholding of gray－level picture using two－dimensional entropies［J］.Pattern Recognition，1989，47（1）：22－32.

［9］ Brink A D.Thresholding of digital image using twodimensional entropies［J］.Pattern Recognition，1992，25（8）：803－808.

［10］Du F，Shi W K，Chen L Z，et al.Infrared image seg－mentation with 2Dmaximum entropy method based on particle swarm optimization［J］.Pattern Recognition Letters，2005，26（5）：597－603.

［11］Wu Yiquan，Ji Shouxin，Wu Shihua，et al.Gray entropy image thresholding based on two－dimensional histogram vertical and oblique segmentation［J］.Journal of Tianjin University，2011，44（12）：1043－1049.（in Chinese）

［12］Pal S K，Pal N R.Entropic thresholding［J］.Signal Processing，1989，16（2）：97－108.

［13］Wu Yiquan，Zhan Bichao.Thresholding based on reciprocal entropy and chaotic particle swarm optimization［J］.Signal Processing，2010，26（7）：1044－1049.（in Chinese）

［14］Wu Yiquan，Pan Zhe，Wu Wenyi.Maximum entropy image thresholding based on two－dimensional histo－gram oblique segmentation［J］.Pattern Recognition and Artificial Intelligence，2009，22（1）：162－168.（in Chinese）

［15］Xiao Y H，Cao Y F，Yu W Y，et al.Multi－level threshold selection based on artificial bee colony algorithm and maximum entropy for image segmentation［J］.International Journal of Computer Applications in Technology，2012，43（4）：343－350.

［16］Horng M H.Multilevel thresholding selection based on the artificial bee colony algorithm for image segmentation［J］.Expert Systems with Applications，2011，38（11）：13785－13791.

［17］Ma M，Liang J H，Guo M，et al.SAR image segmentation based on artificial bee colony algorithm［J］.Applied Soft Computing Journal，2011，11（8）：5205－5214.