基于混合ABC-CS算法的彩色圖像多閾值分割*

蒲國林　衛(wèi)洪春　向　偉　邱玉輝

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

?

基于混合ABC-CS算法的彩色圖像多閾值分割*

蒲國林1衛(wèi)洪春1向偉1邱玉輝2

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

摘要將人工蜂群算法中引領蜂和跟隨蜂的開采行為融入布谷鳥算法(CS)的每一次萊維飛行結束后進行尋優(yōu)引導，對發(fā)現(xiàn)概率和步子因子也采用了相應新的變異因子隨著布谷鳥算法運行而動態(tài)改變，以此為基礎，提出了一種混合人工蜂群算法的布谷鳥算法(HACS)，并以此HACS算法作用于彩色圖像多閾值分割，實驗表明，HACS算法有效解決了布谷鳥算法收斂時間較長、精度不高的問題，在彩色圖像多閾值分割中取得了較好的效果。

關鍵詞人工蜂群算法; 開采行為; 布谷鳥算法; 發(fā)現(xiàn)概率; 步子因子

Class NumberTP391

1引言

彩色圖像閾值分割是圖像分割和解釋的基本過程，也是將圖像從背景中分離出來的最為普遍的方法，目前已經(jīng)應用于多個方面[1～2]，一般情況下是根據(jù)一個或多個閾值將圖像分離為各個感興趣的區(qū)域，相比256級的灰度圖像的閾值分割，彩色圖像的多閾值分割能得到更詳細的信息，更有效的處理能力，但彩色圖像的多閾值分割是一個挑戰(zhàn)性的任務，因為隨著分割層級的增加，運算代價也會隨著增加[3]，彩色圖像分割目前主要有基于區(qū)域分割的方法、基于邊緣分割的方法、基于特征空間的方法、基于梯度閾值的方法等。近年來，出現(xiàn)了許多經(jīng)典的圖像分割技術，但實驗證明，這些經(jīng)典的圖像分割技術大多以窮盡搜索最優(yōu)閾值為特征，比較耗時，為了提高圖像分割的質量和速度，也出現(xiàn)了一些令人感興趣的方法[4～5]，為了得到理想的彩色圖像分割結果，最突出的問題是如何選擇最合適的閾值問題，在這方面，基于進化和群集的算法在從目標函數(shù)中尋找最優(yōu)解的能力相當優(yōu)秀，目前這些算法由于能在復雜問題中得到高質量的解而廣泛使用，由于這些算法的優(yōu)勢，因而已被廣泛使用在圖像分割的閾值尋優(yōu)方面[6～7]，目前研究表明基于群體的算法在多閾值分割問題方面更精確[8]，隨著群體智能算法的發(fā)展，更多的群體智能算法被應用在圖像多閾值分割領域[9～10]，但彩色圖像的多閾值分割問題始終存在分割時間過長、分割質量與理想要求有較大差距的問題。

要提高彩色圖像分割的質量和速度，本文采用人工蜂群算法[11]和布谷鳥算法[12～13]相結合的方法，并對布谷鳥算法中的發(fā)現(xiàn)概率和步長因子也進行了改進。

2混合人工蜂群布谷鳥算法的彩色圖像多閾值分割

為解決當前彩色圖像多閾值分割中分割清晰度不高、過分割、效率低等缺陷，采用本文提出的HACS混合算法進行彩色圖像分割，而效益度(適應度)函數(shù)采用Tsallis最小交叉熵函數(shù)[14]，此HACS混合算法運用于彩色圖像多閾值分割所求得的全局最優(yōu)解就是所求的一系列最優(yōu)閾值組合。

2.1布谷鳥算法

布谷鳥算法是一種新的元啟發(fā)式優(yōu)化算法，其主要原理是雌性布谷鳥將宿主的蛋推出去而放入自己的蛋，這種行為之所以成功主要在于布谷鳥蛋模仿宿主蛋的行為。通過宿主發(fā)現(xiàn)布谷鳥蛋而布谷鳥蛋不斷模仿宿主蛋這種行為實際上實現(xiàn)了進化，因為布谷鳥產蛋的時間剛好就是宿主鳥產蛋的時間，在本算法中每有一只布谷鳥蛋就引進一個新解，其目的是用新的有潛力的更好解取代不是很好的解，在簡單情況下，每只鳥巢只有一個蛋，在復雜情況下，每只鳥巢可以有多個蛋并代表一系列解，應用這種搜索作為一種優(yōu)化算法，并采用三個規(guī)則[15～16]，其位置變量公式如下：

(1)

其中，vit+1表示第t+1迭代中第i個鳥窩位置,vit表示第t迭代中第i個鳥窩位置，α表示步長因子，levy(λ)表示萊維飛行因子其公式如下：

(2)

其中λ是分布因子，τ()函數(shù)是一個gamma分布函數(shù)。

2.2布谷鳥優(yōu)化算法的改進

在此混合人工蜂群算法和布谷鳥算法的混合算法中，通過將人工蜂群算法中引領蜂和跟隨蜂開采方程應用于每一次萊維飛行結束后，并對原人工蜂群算法中引領蜂和跟隨蜂的搜索方程進行了改進，其新的搜索方程如下：

BSi,j=BSi,j+α(BSbest,j-BSk,j)+λ(BSm,j-BSi,j)

(3)

其中左邊BSi,j表示萊維飛行結束變異后的第i個位置，而等式右邊第一個因子BSi,j表示萊維飛行結束后未進行變異前的第i個位置的第j個元素，BSbest,j為此混合算法中搜索得到的當前全局最優(yōu)解的第j個元素，j∈{1,2,…,N}并且N為此混合算法的種群規(guī)模，在此混合算法中各參數(shù)i,k,m各異，α和β是隨機數(shù)，其取值范圍分別在[-1,1.5]和[-1,1]之間，同時經(jīng)過研究發(fā)現(xiàn)，布谷鳥算法中步長因子和發(fā)現(xiàn)概率對整個布谷鳥算法的效率和收斂精度也有較大影響，根據(jù)對布谷鳥算法的運行規(guī)律實驗觀察，發(fā)現(xiàn)若步長因子和發(fā)現(xiàn)概率前期較大，是有利于全局最優(yōu)搜索的，而后期的值應當適當減少才有利于局部收斂和全局最優(yōu)解的求取。故本文對步長因子和發(fā)現(xiàn)概率各提出了一個變異因子，使步長因子和發(fā)現(xiàn)概率隨著此算法的運行而動態(tài)變化，其動態(tài)變異方程如下：

(4)

方程(4)是步長因子動態(tài)變異方程，Tmax、Tmin分別表示當前步長因子的最大值和最小值，i為此混合算法中當前迭代次數(shù)。

(5)

方程(5)是本文混合算法中所提出的發(fā)現(xiàn)概率變異方程，pmax(t)表示此混合算法中當前代的最大發(fā)現(xiàn)概率，pmin(t)表示此混合算法中當前代的最小發(fā)現(xiàn)概率，Tmax表示當前最大迭代次數(shù)。

2.3本文提出的算法

在本文所提出的HACS算法運用于彩色圖像多閾值分割中時，以Tsallis最小交叉熵為適應度函數(shù)，所求得的全局最優(yōu)解的各個解分量就是本文所提算法中所求得最優(yōu)位置鳥巢中鳥蛋的個數(shù)(Tsallis最小交叉熵變量個數(shù))，也就是所求得的彩色圖像多閾值分割中全局最優(yōu)閾值的各個分量分數(shù)。

其改進算法如下：

1) 初始化此混合算法中所有參數(shù)。

2) 產生初始HACS的種群。

3) 根據(jù)HACS算法產生隨機解，以Tsallis最小交叉熵計算效益度值。

4) 從當前所得到的全部解中，識別出局部最優(yōu)解和全局最優(yōu)解，并開始迭代程序。

5) 在每次萊維飛行結束后采用式(3)尋優(yōu)，而步長因子和發(fā)現(xiàn)概率也分別按式(4)、式(5)計算效益度值，識別出局部最優(yōu)和全局最優(yōu)鳥窩位置。

6) 更新種群。

7) 重復前述4)、5)、6)步驟過程，直至滿足預定的結束條件為止。

8) 輸出得到最終全局最優(yōu)解的各個解分量，就是所求得彩色圖像分割的一系列閾值。

3實驗結果與分析

本實驗硬件平臺為4核3.3GHz，4G內存，以Matlab作為軟件平臺，為測試本文所提出的改進算法性能，將本實驗分為兩大部分，第一部分是主觀實驗部分，以本文所提出HACS算法進行彩色圖像多閾值分割的結果圖進行主觀分析，第二部分是客觀實驗，從HACS算法、ABC算法、CS算法這三種算法分別對彩色圖像多閾值分割的速度和質量進行分析比較。

3.1三種算法在桃花島圖上進行多閾值分割的實驗結果圖主觀效果比較

在本實驗中為驗證本文所提出HACS算法彩色圖像多閾值分割的主觀效果，選取了大量素材，進行了大量實驗，本實驗素材都是從網(wǎng)上或實驗室獲得，由于篇幅所限，本文只選取了浙江舟山桃花鳥圖的三種算法實驗結果進行比較分析。下圖分別是HACS算法、ABC算法、CS算法的二維、三維、四維實驗結果圖像。

圖1　桃花島原圖及ABC算法的多閾值分割實驗結果圖

圖1是ABC算法的實驗結果圖，從橫向來看，圖1(b)～(d)圖的分割效果中，(d)圖分割效果最好，(b)效果最差，(c)圖的分割效果居中，在(d)圖的桃花島圖中遠處天上的云層、遠處及近處的山和圖前面的亭式建筑都一定程度分割出來了，而(b)圖無論是云層、遠山及近山、近處亭式建筑分割得都不太清楚?？v向來看，圖2是CS算法的分割結果圖，其分割效果比ABC好些，而圖3的HACS算法的分割效果從整體來看是最好的。在相同維數(shù)情況下，如都在二維、三維、四維情況下，HACS算法比ABC算法和CS算法的分割效果都好，在圖3(d)圖中，天上的云層、遠處的山及近處的山，近處的亭式建筑甚至亭式建筑后面的樹都分割得比較清楚，明顯比圖2(d)、圖1(d)效果要好。

圖2　桃花島原圖及CS算法的多閾值分割實驗結果圖

圖3　桃花島原圖及HACS算法的多閾值分割實驗結果圖

3.2HACS算法、ABC算法、CS算法多閾值分割實驗結果的客觀分析

本實驗中為了對本文所提出的HACS算法的多閾值分割結果進行客觀分析，采用HACS算法和標準ABC算法以及標準CS算法進行對比實驗，以Tsallis最小交叉熵函數(shù)為適應度函數(shù)，采用閾值、分割時間、均一度[17]作為評價指標，對應3.1部分的實驗結果圖，分別給出了三種算法對應的二閾值、三閾值、四閾值指標數(shù)據(jù)，具體指標數(shù)據(jù)如表1。

從表1三種算法的實驗指標數(shù)據(jù)來看，在運行時間方面，在同為二維閾值的情況下，HACS算法的運行時間是CS算法運行時間的76.91%，而ABC算法的運行時間是CS算法運行時間的77.42%。在同為三維閾值的情況下，HACS算法的運行時間是CS算法的運行時間的81.70%,而ABC算法的運行時間是CS算法的運行時間的86.87%。在同為四維閾值的情況下，HACS算法的運行時間是CS算法的運行時間的80.74%，而ABC算法的運行時間是CS算法運行時間的88.59%。因而無論從二維、三維、四維閾值分割的情況來看，HACS算法的運行時間都是最短的，在均一度方面，每一種算法隨著閾值數(shù)的增加，其分割質量明顯變好，而三種算法中，無論從相同閾值數(shù)來看，還是從整體分割情況來看，HACS算法的分割質量都是最好的，另外本實驗中還知道ABC算法運行時間比CS算法運行時間短，這說明ABC算法的多閾值分割速度比CS算法快。

表1　HACS、ABC、CS三種算法的實驗指標數(shù)據(jù)比較

4結語

彩色圖像多閾值分割一直以來是研究的難題，本文通過將人工蜂群算法和布谷鳥算法相結合實現(xiàn)兩種算法的優(yōu)勢互補，將此混合算法和人工蜂群算法、布谷鳥算法以Tsallis最小交叉熵作為適應度函數(shù)進行彩色圖像多閾值分割的對比實驗，實驗結果表明本文所提出的人工蜂群布谷鳥混合算法在彩色圖像分割的無論主觀效果還是客觀效果，都是最好的。

參 考 文 獻

[1] N. Paragios, R. Deriche. Geodesic active contours and level sets for the detection and tracking of moving objects[J]. IEEE Trans. Pattern Anal. Mach. Intell,2000,22(3):266-280.

[2] T. Zhang, D. Freedman. Tracking objects using density matching and shape priors[C]//Proceedings of IEEE International Conference on Computer Vision,2003(2):1056-1062.

[3] Dey, S., Saha, I., Bhattacharyya, S., et al. Multi-level thresholding using quantum inspired meta-heuristics[J]. Knowledge-Based Systems,2014,67:373-400.

[4] Manikandan, S., Ramar, K., Willjuice, I. M., et al. Multilevel thresholding for segmentation of medical brain images using real coded genetic algorithm[J]. Measurement,2014,47:558-568.

[5] Dirami, A., Hammouche, K., Diaf, M., et al. Fast multilevel thresholding for image segmentation through a multiphase level set method[J]. Signal Processing,2013,93(1):139-153.

[6] Liu, Y., Mu, C., Kou, W., et al. Modified particle swarm optimization-based multilevel thresholding for image segmentation[J]. Soft Computing,2015,19(5):1311-1327.

[7] Zhang, J., Li, H., Tang, Z., et al. An improved quantum inspired genetic algorithm for image multilevel thresholding segmentation[J]. Mathematical Problems in Engineering,2014:1-12.

[8] Kurban, T., Civicioglu, P., Kurban, R., et al. Comparison of evolutionary and swarm based computational techniques for multilevel color image thresholding[J]. Applied Soft Computing,2014,23:128-143.

[9] Zhang, Y., Wu, L. Optimal multi-level thresholding based on maximum Tsallis entropy via an artificial bee colony approach[J]. Entropy,2011,13(4):841-859.

[10] Agrawal, S., Panda, R., Bhuyan, S., et al. Tsallis entropy based optimal multilevel thresholding using cuckoo search algorithm[J]. Swarm and Evolutionary Computation,2013,11:16-30.

[11] D. Karaboga. An Idea Based on Honey Bee Swarm for Numerical Optimization[R]. Kayseri: Erciyes University,2005.

[12] Afzalan E, Joorabian M. An improved cuckoo search algorithm for power economic load dispatch[J]. International Transactions on Electrical Energy Systems,2015,25(6):958-975.

[13] M. Basu, A. Chowdhury, Cuckoo search algorithm for economic dispatch[J]. Energy,2013,60(1):99-108.

[14] 唐英干,邸秋艷,關新平,等.基于最小Tsallis交叉嫡的閾值圖像分割方法[J].儀器儀表學報,2008,29(9):1868-1872.

TANG Yinggan, GUAN Xinping, Liu Fucai, et al. thresholding image segmentation method based on minimum Tsallis cross entropy[J]. Chinese Journal of Scientific Instrument,2008,29(9):1868-1872.

[15] Yang XS, Deb S. Multiobjective cuckoo search for design optimization[J]. Comput Oper Res,2013,40:1616-24.

[16] Abd-Elaziz AY, Ali ES. Cuckoo search algorithm based load frequency controller design for nonlinear interconnected power system[J]. Int J Electric Power Energy Syst,2015,73:632-43.

[17] TANG Kezong, YUAN Xiaojing, SUN Tingkai, et al. An improved scheme for minimum cross entropy threshold selection based on genetic algorithm[J]. Knowledge-based Systems,2011,24(8):1131-1138.

收稿日期:2016年1月6日,修回日期:2016年2月19日

基金項目:國家自然科學基金(編號：61152003);國家檔案局科技項目(編號：2014-X-65);四川省教育廳重點項目(編號：16ZA0353);四川省教育廳資助科研項目(編號：15ZB0323);四川文理學院智能計算與物聯(lián)網(wǎng)工程技術中心資助。

作者簡介:蒲國林,男,博士,副教授,研究方向：人工智能、數(shù)字圖像處理。衛(wèi)洪春,男,碩士,講師,研究方向：圖形圖像處理。向偉,男,碩士,講師,研究方向：軟件工程、智能計算。邱玉輝,男,教授,博士生導師,研究方向：人工智能。

中圖分類號TP391

DOI:10.3969/j.issn.1672-9722.2016.07.029

Color Image Multi Threshold Segmentation Based on Hybrid ABC-CS Algorithm

PU Guolin1WEI Hongchun1XIANG Wei1QIU Yuhui2

(1. School of Computer Science, Sichuan University of Arts and Science, Dazhou635000)(2. College of computer and Information Science, Southwest University, Chongqing400715)

AbstractThe behaviors of employed bees, onlooker bees in artificial bee colony algorithm are introduced into every time after the end of flight Levi of cuckoo search(CS) algorithm to optimized guiding, the discovery probability and the pace factor are also using the corresponding new variation factors, and change with cuckoo algorithm operation. Based on this, a hybrid artificial bee colony algorithm and cuckoo search algorithm (HACS) is proposed, and the HACS algorithm is used for color image segmentation. Experimental results show, the HACS algorithm can effectively solve the cuckoo algorithm long convergence time, lower accuracy. Good results have been achieved in the color image multi threshold segmentation.

Key Wordsartificial bee colony algorithm, mining behavior, cuckoo algorithm, detection probability, step factor