基于增強布谷鳥算法的彩色圖像多閾值分割

蒲國林，邱玉輝

（1.四川文理學院計算機學院，四川達州635000；2.西南大學計算機與信息科學學院，重慶400715）

基于增強布谷鳥算法的彩色圖像多閾值分割

蒲國林1，邱玉輝2

（1.四川文理學院計算機學院，四川達州635000；2.西南大學計算機與信息科學學院，重慶400715）

為提高彩色圖像多閾值分割的速度和質量，針對布谷鳥算法的缺陷，對每一次萊維飛行結束后，提出一個新的尋優方程進行尋優引導，并對發現概率和步子因子都各提出了一個新的運行方程，以此為基礎，提出了一種增強布谷鳥算法（ECS），并以此ECS算法作用于彩色圖像多閾值分割中，通過本文所提出算法和標準粒子群算法及標準布谷鳥算法的對比實驗表明，本文所提的ECS算法無論在彩色圖像分割的主觀效果上還是客觀效果上都是最好的，完全能運用于實際的多閾值分割中。

彩色圖像；多閾值分割；布谷鳥算法；發現概率；步長因子；粒子群算法

圖像分割特別是彩色圖像分割是數字圖像處理的重要步驟，現在已經廣泛應用于目標檢測、視覺跟蹤、場景理解和基于內容的圖像檢索等方面。圖像分割主要有4個類型：基于聚類的方法、基于區域的方法、基于閾值的方法和基于邊緣檢測的方法。基于閾值的方法簡單、高效，并得到了廣泛使用。在基于閾值的方法中，隨著分割閾值數的增加，分割的目標更接近于真實的子目標，分割效果也越理想，但分割的數據量急劇增加，分割速度也越來越慢，有時候隨著分割閾值數的增加分割質量反而降低，主要是由于多維閾值的選擇比較。如何尋找最理想的閾值將彩色圖像的各個需求子目標分割開來，是研究人員一直以來努力尋求的目標。

隨著群體智能算法如粒子群算法［1］、蟻群算法［2］、人工蜂群算法［3］等在各方面的快速發展，在彩色圖像分割領域也取得了重要進步［4-5］，但至今為止優秀圖像分割算法特別是彩色圖像分割算法并不多，各個算法都是在某些方面或某個領域有較好的效果，統一高效的彩色圖像分割算法目前還沒有。

近年來新出來的布谷鳥算法［6］以參數簡單，實現容易，效率較高的優點，已應用在某此方面并取得了進步［7-8］，但布谷鳥算法也存在收斂慢，易陷入局部最優等缺點，本文提出一種增強布谷鳥算法應用于解決彩色圖像多閾值分割，增強布谷鳥算法的有效性能，實驗表明在彩色圖像多閾值分割中取得了較好的效果。

1　Tsallis熵函數的彩色圖像分割原理

在熵的圖像閾值分割中，Tsallis熵［9］將圖像分割為各個子系統后各個圖像子系統的概率分布關系比較清楚的表示出來，并且算法較為簡單，在有些方面已經得到了較為成功的應用［10-11］。Tsallis熵公式如下：

其中q是待定系數，Pi∈［0，1］代表各個系統的概率，且熵各個子系統熵的關系表示如下：

這個公式分兩種情況分別說明了彩色圖像和灰度圖像的Tsallis熵，假設輸入圖像的灰度級為G級，各個灰度級像素點的概率分布為P1，P2，P3…PG。

假設A、B分別為圖像分割中兩個子區域（也可以為前景和目標物），則對應概率公式如下：

這里：

因此對各個子區域，tsallis熵分類如下：

這個最優閾值可以采用較少的計算量用以下公式計算：

其中，

上面公式可以直接到多閾值情況如下：

2　彩色圖像布谷鳥算法的多閾值分割

文中以布谷鳥算法對彩色圖像的閾值分割進行多閾值尋優，并以Tsallis熵函數［12］作為適應度函數，由于布谷鳥算法本身容易陷入局部最優，收斂速度較慢，故本文提出一種增強布谷鳥算法，并根據最大Tsallis熵函數理論進行多閾值尋優，所求最優解的各個分量即為多閾值最優分割中的各個閾值。

2.1布谷鳥算法

布谷鳥算法是一個新的元啟發式優化算法，此算法受到布谷鳥種群通過將自己的蛋放到其他種群鳥兒鳥窩中的育雛寄生行為的啟發而產生，當宿主發現了這些布谷鳥蛋后，可能會將這些蛋扔出去或拋棄這個鳥巢而建一個新的鳥巢，CS算法將布谷鳥種群這種育雛行為和一些鳥兒的萊維飛行行為相結合并理想化這種行為，使之成為一種獨立的算法，用來解決許多約束優化問題。其位置變量公式如下：

其中λ是分布因子，τ（）函數是一個gamma分布函數。

2.2布谷鳥優化算法的改進

為了提高布谷鳥算法的收斂速度，在每一次萊維飛行結束后，進行尋優引導。

其中SPi，j為當前位置的第j個元素，SPbest，j為當前最優位置的最j個元素，j∈｛1，2，…D｝并且j為問題的維度，i，j，n互不相等，g為高斯變異因子，λi，j∈［0，1.5］的隨機數，βi，j∈［-1，1］的隨機數，通過此搜索方程，可以在每一次萊維飛行結束后，加強引導，以促進算法向最優位置搜索，同時通過高斯變異因子將陷入局部最優的粒子跳出局部最優。

同時在布谷鳥算法中，步長因子和發現概率對布谷鳥算法的收斂也是至關重要，通過對粒子群算法和人工蜂群算法以及其他群體智能的研究，結合實驗，我們對步長因子和發現概率各提出了一個新的公式如下：

上兩式中，Sa，min，Sa，max分別表示步長因子的最小和最大值，fmax，fmin分別表示發現概率的最大和最小值，t，tmax分別表示當前迭代次數和最大迭代次數，m1，m2為控制因子，m1∈［0，1］，m2∈［π，10］，采用上面兩式，可以保證搜索前期萊維飛行距離遠，尋優能力較強，這樣可以避免早熟現象，而后期局部尋優能力較強，加快收斂。

2.3本文提出的算法

文中提出的增強布谷鳥算法運用于彩色圖像多閾值分割過程中，每個鳥巢中鳥蛋的個數就是此彩色圖像分割中的閾值個數，也就是本文采用的適應度函數中Tsallis熵函數的變量個數，所求的全局最優解對應的就是彩色圖像分割中全局最優閾值。

其改進算法如下：

1）初始化布谷鳥算法產生N只鳥窩（即n個初始解）及相關初始參數如發現概率、步長因子、最大迭代次數等，本實驗中步長因子的最小值、最大值分別為Sa，min=0.000 5和Sa，max= 0.5，發現概率的最大值和最小值分別為fmax=0.5和fmin=0.001，最大迭代次數tmax為300，控制因子m1，m2分別取為m1=0.6，m2=6。

2）根據本改進布谷鳥算法選擇相應的搜索邊界（上界和下界本文中上界設為256，下界設為1）。

3）以Tsallis熵函數作為適應度函數，根據搜索方程及本文提出的步長因子公式（10）和發現概率公式（11），產生隨機解。

4）當不滿足停止條件時，進行萊維隨機飛行，每次萊維飛行結束至下次飛行前，運用方程（9）進行尋優引導，并計算出當前Tsallis熵函數值。

5）當前適應度值（熵函數值）與當前最優適應度值比較，若當前對應的適應度值更優，則取代當前最優值，將當前適應度值作為全局最優值，并產生一個新的鳥窩。

6）以當前發現概率發現質量差的鳥窩時，該鳥窩被拋棄，建立新的鳥窩。

7）保留當前最優解。

8）根據當前最優解得到當前全局最優閾值。

3　實驗結果與分析

本實驗基于MATLAB平臺，硬件配置為CPU3.4 GHz四核，內存4 G，分兩部分，第一部分是主觀實驗，通過本文算法和粒子群及標準布谷鳥算法以Tsallis熵函數為適應度函數對多張圖像進行分割對比實驗，第二部分是客觀實驗，通過對3種算法的彩色圖像分割時間和質量進行比較。

3.13種算法在以Tsallis熵函數為適應度值時的彩色圖像分割結果比較

本實驗部分的實驗圖像素材來源于實驗室或從網絡中下載，由于篇幅本文選擇了基于三亞大東海的圖像，3種算法分別在三亞大東海實驗圖像中進行二維、三維以及四維閾值分割，本實驗項目是一個機器視覺項目的子項目，目的是為了準確分割出圖中的各個對象以便能對各個目標對象進行自動分類識別，以下是分割實驗結果圖像。

圖1　三亞大東海原圖及PSO算法的二維、三維、四維分割實驗結果圖

圖2　三亞大東海原圖及標準CS算法的二維、三維、四維分割實驗結果圖

圖3　三亞大東海原圖及增強CS（ECS）算法的二維、三維、四維分割實驗結果圖

從圖1至圖3的分割結果來看，3種算法在相同維數進行分割時，無論是二維分割、三維分割還是四維分割，圖3的分割效果是最好的，這表明本文提出的ECS算法和其他兩種算法相比在彩色圖像多閾值分割時效果是最好的，在同為二維分割時，PSO算法分割效果最差，在沙灘的分割上有許多雜色粒子像素塊存在，而我們的目標是分割出沙灘區域，在PSO這種分割中，就出現了過分割現象，遠處的椰樹及建筑分割模糊，近處的休息椅子許多沒有分割出來。CS算法明顯要好些，ECS算法的分割效果最好，其近沙灘分割比較清晰，而PSO分割時出現了不同的像素斑塊過分割現象。同為三維和四維圖像分割時，同樣PSO算法效果最差，ECS分割效果最好。在ECS的四維分割時，無論是遠處的建筑還是椰樹其分割都比較清楚，甚至天上的云層形狀也分割得比較清晰，近處沙灘的邊緣輪廓也比較清楚分割出來。

3.23種算法多閾值分割實驗的客觀數據指標比較

本實驗部分以基于粒子群算法、布谷鳥算法以及本文中提出的ECS算法，以Tsallis熵函數為適應度函數，其實驗評價指標包括3種算法在3種閾值情況下Tsallis熵的最優目標值比較如表1所示，結構相似性SSIM［13］和特征相似性FSIM［14］值比較如表2和表3所示，分割時間、質量均一度的比較如表4所示，其中圖像質量均一度［15］計算公式如下：

式中T表示閾值的個數，Rj表示分割區域j，gmax，gmin，ui分別表示圖像對應區域中的最大灰度值，最小灰度值，以及對應區域j的灰度均值，而gi表示像素i的灰度值，M表示一個給定圖像中像素的總體數量。

表1　3種算法使用Tsallis Entropy的最優目標值比較

表2　3種算法使用Tsallis entropy的SSIM值比較

表3　3種算法使用Tsallis entropy的FSIM值比較

表4　3種算法的閾值、運行時間及均一度比較

如上述表1至表4所示，表1從全局最優適應度值即全局最優閾值的角度說明，ECS算法具有全局最優目標值就是說具有最優分割閾值，表2的結構相似性（SSIM）和表3特征相似性（FSIM）從圖像的結構、相位及梯度方面說明了圖像分割后失真程度或錯分率，并且從表2和表3還可以看出本文提出的ECS算法所分割圖像無論在二閾值、三閾值還是四閾值情況下，其失真程度或錯分率都是最低的，而PSO失真度或錯分率都是最高的，CS算法居中。從分割的時間來看，在同為二維閾值時，CS算法的分割時間是PSO算法分割時間的92%，ECS算法的彩色圖像分割時間是CS算法分割時間的86%，在同為三維閾值分割時，CS算法是PSO算法時間的90%，ECS算法是PSO時間的74%。在同為四維閾值分割時，CS算法分割時間是PSO算法分割時間的85%，ECS算法的分割時間是PSO算法分割時間的67%。因此無論從不同算法的相同閾值分割還是同一種算法的不同分割閾值的分割時間來看，ECS算法的分割時間都是最少的，CS算法所用時間居中，PSO算法所用時間最多，在均一度方面，按照均一度原理，圖像分割后的均一度越高，說明圖像分割質量越好。從表4來看，很明顯，在同一種算法中，隨著閾值分割數的提高，分割質量也隨著提高，在不同閾值分割時，本文提出的ECS算法的均一度相對來說，都是最高的，因此說明本文提出的算法其多閾值分割質量是有明顯提高的。

4　結束語

本文為了提高彩色圖像多閾值分割的速度和改進彩色圖像多閾值分割的效果，對現在比較優秀的布谷鳥算法的尋優方式、發現概率和步長因子都進行了改進，以此改進的ECS算法運用于彩色圖像分割中，并與標準PSO算法和CS算法進行了對比實驗，實驗說明本文提出的ECS算法無論是分割速度還是分割效果都是最好的。

［1］Kennedy J，Eberhart R C.Particle swarm optimization［C］// Proceedings of the 1995 IEEE International Conference on Neural Networks.Piscataway，NJ，Perth，IEEE service center，1995:1942-1948.

［2］Salima Ouadfel，Mohamed Batouche.An efficient ant algorithm for swarm-based image clustering［J］.Computer Science，2007（3）3:162-167.

［3］Karaboga D.An idea based on honey bee swarm for numerical optimization.Technical Report，Erciyes University，Engineering Faculty［J］.Computer Engineer-ing Department，2005.

［4］Liu Y，Mu C，Kou W，et al.Modified particle swarm optimization-based multilevel thresholding for image segmentation［J］.Soft Computing，2014:1-17.

［5］Huang P，Cao H，Luo S.An artificial ant colonies approach to medical imagesegmentation Comput［J］.Methods Progr. Biomed，2008，92（1）:267-273.

［6］Basu M，Chowdhury A.Cuckoo search algorithm for economic dispatch［J］.Energy，2013，60（1）:99-108.

［7］Valian E，Mohanna S，Tavakoli S.Improved cuckoo search algorithm for global optimization［J］.Int.J.Comunications and Information Technology，2014，1（1）:31-34.

［8］Yang X S，Deb S.Cuckoo search via Levy flights，Proceedings of the world congress on nature and biologically inspired computing Coimbatore［J］.NABIC，2009（4）:210-214.

［9］尹詩白，趙祥模，王衛星，等.遞推人工蜂群的模糊劃分熵多閾值分割算法［J］.西安交通大學學報，2012，46（10）:72-77.

［10］邸秋艷.基于Tsallis熵的閾值圖像分割方法研究［D］.燕山大學，2009.

［11］Sathya P D，Kayalvizhi R.PSO-based Tsallis thresholding selection procedure for image segmentation［J］.International Journal of Computer Applications，2010，5（4）:39-46.

［12］Portes DE Albuquerque M，Esquef I A，et al.Image thresholding using Tsallis entropy［J］.Pattern Recognition Letters，2004，25（9）:1059-1065.

［13］龐建新，張榮，張暉，等.圖像結構失真的編碼質量評價［J］.中國圖象圖形學報，2009，14（8）:1560-1568.

［14］ZHANG Lin，ZHANG Lei，MOU Xuan-qin，et al.FSIM:a feature similarity index for image quality assessmen［J］.IEEE Trans on Image Processing，2011，20（8）:2378-2386.

［15］TANG Ke-zong，YUAN Xiao-jing，SUN Ting-kai，et al.An improved scheme for minimum cross entropy threshold selection based on genetic algorithm［J］.Knowledge-based Systems，2011，24（8）:1131-1138.

A color image multi threshold image segmentation method based on enhanced cuckoo algorithm

PU Guo-lin1，QIU Yu-hui2
（1.School of Computer Science，Sichuan University of Arts and Science，Dazhou 635000，China；2.College of Computer and Information Science，Southwest University，Chongqing 400715，China）

In order to improve the speed and quality of color image segmentation，aiming at the limitation of the cuckoo algorithm，every time after the end of the Lévy flight，a new optimization seeking equation is proposed，and the discovery probability and the pace factor are respectively proposed a new operating equation.Based on this，proposed an enhanced cuckoo algorithm（ECS），and the ECS algorithm is based on the multi threshold segmentation of color image.Through the comparison of the proposed algorithm（ECS），the standard PSO algorithm and the standard CS algorithm，the ECS algorithm is the best of both subjective and objective results，fully able to be applied to the actual multi threshold segmentation.

color image；multi-threshold segmentation；cuckoo algorithm；detection probability；step factor；particle swarm optimization

TN 911.73

A

1674－6236（2016）12-0009-05

2016-02-22稿件編號：201602092

國家自然科學基金（61152003）；四川省教育廳資助科研項目（15ZB0323）

蒲國林（1971—），男，四川宣漢人，博士研究生，副教授。研究方向：人工智能，數字圖像處理。