一種求解圖像分割問題的限速-離散蜂群優化算法

周 遜，郭 敏，馬 苗

(陜西師范大學計算機科學學院，西安 710062)

1 概述

基于圖論的圖像分割是當前圖像分割領域一個熱點問題。該方法將整幅圖像看作一幅無向帶權圖，圖像中每一個像素對應圖中一個節點，邊上的權值代表像素的近似關系，利用最小剪切準則得到圖像最佳分割。文獻［1 -2］綜合考慮分割后子圖的內部相似度和子圖之間的相似度，提出的Normalized Cut 準則是一種規范化的準則，有效避免了出現歪斜分割區域。由設計復雜性可知，歸一化圖像分割權值矩陣構造的計算量非常大。文獻［3］通過加入先驗知識得到優質分割結果;文獻［4］利用分水嶺算法對圖像進行預處理，有效地降低了權值計算維度。由于最小化Ncut 值是NP-hard 問題，文獻［2］提出譜聚類算法，將問題轉換為求解特大矩陣的第二小特征值，得到了Ncut 值的近似解。近年來，群智能優化算法在求解組合優化問題時顯示出其獨特的優勢，文獻［5］利用粒子群算法對非線性約束問題進行優化，減少了多重制冷系統中的能源消耗;文獻［6］采用魚群優化算法對灰色理論中的GM(1，1)模型參數進行優化;文獻［7］利用細菌覓食算法求解任何尺寸的矩形微帶天線的諧振頻率問題。

蜂群優化算法［8］具有控制參數少、易于實現、計算簡潔等優點，文獻［9］將蜂群算法用于MESFET 的小信號模型參數的提取，在時間和質量上效果較佳;文獻［10］將蜂群算法優化與混沌搜索相結合在PID控制調整中得到應用。但蜂群算法求解歸一化圖像分割問題時存在早熟收斂、長期停滯等缺點，一直制約其在該領域發展。本文提出一種限速-離散蜂群優化算法(Speed-limiting Discrete Artificial Bee Colony Algorithm，SLDABC)，用于解決歸一化的彩色圖像分割問題，該算法將標準蜂群優化算法離散化，在離散域上求解問題，重新定義了蜂群位置的變換方式;增加速度的定義，并引入一個對速度限制的過程;同時，自適應地調整個體蜂速度更新因子，增加了種群的多樣性。

2 歸一化彩色圖像分割方法

2.1 歸一化圖像分割

無向帶權圖每個邊有權值ω(i，j)，ω(i，j)表示像素i 和像素j 之間的相似度，通過刪去某些邊將圖分成2 個點集，使得A∪B=V，A∩B=?，被刪去的邊的權值總和稱為割cut。

由于其容易劃分出孤立點，Shi 和Malik 提出一種規范化的分割方法，歸一化分割描述如下:

其中，asso(A，V)表示A 中節點與圖G 中所有節點之間的聯系程度;asso(B，V)表示B 中節點與圖G 中所有節點之間的聯系程度。可以看出Ncut 值越小，劃分的結果越好。

2.2 圖像預處理

彩色圖像顏色信息量非常大，通常認為每個像素是由R，G，B 3 個顏色分量組成。若以像素點構造權值矩陣必然造成非常大的計算量，為了減少計算量，本文針對彩色圖像的3 個顏色分量通道分別做模糊C 均值處理，每個顏色分量通道分別聚類為c 個最大相似區域IR，IG，IB，取IR，IG，IB的交集將圖像分為n 塊最大相似區域，再以n 塊最大相似區域構造權值矩陣。

3 基于SLDABC 的歸一化彩色圖像分割方法

3.1 標準蜂群算法原理

標準蜂群算法(Artificial Bee Colony Algorithm，ABC)［11］利用蜜蜂的采蜜行為進行空間搜索，每個食物源的位置代表優化問題的一個可行解，食物源的花蜜量作為可行解的適應度值，蜜蜂尋找最優食物源的過程即是尋找最優解的過程。ABC 算法隨機產生N 個食物源，每個食物源對應一個引領蜂。當所有的引領蜂完成搜索后，跟隨蜂則根據一定概率選擇一個食物源進行采蜜。劣質食物源對應的引領蜂變為偵察蜂，隨機尋找新的食物源。引領蜂產生新的鄰域位置和偵察蜂搜索新的食物源的公式分別為:

其中，xi，j(i=1，2，…，N，j=1，2，…，D)是一個食物源;xk，j是xi，j附近的一個食物源;Φ 和φ 是［-1，1］之間的隨機數。

ABC 算法求解連續域約束數值優化問題能夠得到很好的結果，但是它是一種新型的隨機優化算法，其研究剛剛起步，求某些特定問題時限制了蜂群的多樣性，算法容易早熟，且其求解離散域的約束優化問題需要重新定義算法的參數與運算公式，使得求解問題的質量下降。針對上述問題，本文提出了一種限速-離散蜂群算法(Speed Limited-Disperse Artificial Bee Colony Algorithm，SLDABC)來解決歸一化彩色圖像分割問題。

3.2 SLDABC 算法

SLDABC 算法以標準離散蜂群優化算法為基礎，給出了速度與慣性權重的定義，引入自適應慣性權重調整模式控制算法的收斂，設定限速模型來控制種群的多樣性。

3.2.1 速度和慣性權重的定義

定義1 個體蜂速度的大小決定該個體蜂在空間中運動的趨勢，間接決定著個體蜂的下一個位置。Vi=(vi，1，vi，2，…，vi，D)，其中，vi，k(k=1，2，…，D)為第i 個個體蜂在D 維解空間的速度。通過速度的變化控制位置的變化。

定義2 慣性權重是控制個體蜂的以前速度及相互之間的位置差異對當前速度的影響比重。

慣性權重的調控影響到算法的收斂速度及算法的穩定性。

3.2.2 離散化蜂群算法速度的表達

將標準蜂群算法離散化，Xi(xi，1，xi，2，…，xi，D)表示第i 個個體蜂在D 維解空間的位置，xi，k(k=1，2，…，D)的取值為0 或1;Vi=(vi，1，vi，2，…，vi，D)表示第i 個個體蜂在D 維解空間的速度和分別表示第i 個個體蜂在第m 次迭代中的位置及速度;w1，w2表示慣性權重。

本文提出的離散蜂群優化算法的新的速度更新公式為:

其中，r 為［0，2］間的隨機數。

3.2.3 自適應慣性權重調整機制

標準蜂群算法個體蜂的搜素空間隨著迭代進化而收縮，導致只有當優化問題的全局最優值在初始搜索空間時，算法才有可能找到解，使得最優解能否找到非常依賴初始化的群體。本文算法設計了一個動態權重調整機制，由個體蜂自身的適應度確定其動態權重，計算方式如下:

其中，fit(Xi)表示第i 個個體蜂在位置Xi處的適應度值;mean(fit(X))，max(fit(X))，min(fit(X))分別表示本次迭代過程中個體蜂平均、最大、最小適應度值。個體蜂的速度是決定其位置的關鍵因素，初始種群中個體蜂的速度波動較大，適應度值波動也較大，由于慣性權重由本次迭代的適應度值的mean(fit(X))，max(fit(X))和min(fit(X))決定，使得算法在前期的時候偏向于在全局搜索，當逐漸找到全局最優區域時，個體蜂的速度波動較小，使得算法偏向于在局部區域搜索調整解，本文提出這一自適應權重調整機制使得算法的穩定性及收斂速度得到了較大的提高。

3.2.4 限速-離散蜂群算法模型設計

歸一化圖像分割是二元標號問題，函數需要在二進制空間內使得個體蜂的位置趨向判別為0 或1，當速度vi，k越大時，位置xi，k則更容易被選擇為1;反之則容易被選擇為0。即由個體蜂速度決定一個范圍在［0，1］之間的概率選擇參數s:若s 接近1，則個體蜂的位置更加趨近于選擇1;反之，則個體蜂的位置更加趨近于選擇0。文獻［12］提出使用Sigmoid函數求參數s，公式如下:

本文算法設定一個限制速度vSL，當個體蜂的速度超過限制速度，則對其進行特定變換，減緩s趨向于1 和0，使得其能夠全方位在解空間中搜索可能的解，有效找到最優局部解空間。具體操作如下:

速度的限制是為了使位置的變化富有多樣性，使群體多樣化。由公式可以看出，當 vi，k＞vSL時，s減緩趨向于1 的速度;當vi，k＜(-vSL)時，s 則減緩趨向于0 的速度。這樣個體蜂的狀態更加容易得到改變，防止了個體蜂停滯不前，使其在更大的范圍內去搜索解，種群變得多樣化。表1 給出了特定限制速度下的s 的取值范圍。

表1 限制速度下s 的取值范圍

分析實驗時間和實驗效果，當vSL取2 時，綜合分析結果較好。

3.2.5 適應度函數

SLDABC 算法中可將歸一化圖像分割的分割值Ncut 作為適應度值，適應度函數即為式(2)，顯然當適應度值越小時指導圖像分割的效果越好。同時為防止蜂群在搜索過程中拋棄最佳蜜源，導致不必要的耗時。本文設定一個公告板來記錄蜂群在迭代搜索中達到的最優位置及所在位置的適應度值。

3.3 算法描述

本文設定蜂群數量為n，最大迭代次數為m，具體算法步驟如下:

Step1初始化:隨機生成n 個個體蜂。

Step2算法迭代:

(1)利用式(2)計算每個個體蜂的fit(Xi)，if fit(Xi)＞maxfit(X)，將得到的最優適應度值fit(X)和其所在位置狀態Xi記錄到公告板中。

(2)利用式(10)控制速度變化對位置變化影響的幅度，通過式(5)進行速度更新，式(6)和式(7)進行慣性權重更新，通過一定概率選擇個體蜂進行跟隨，計算新的fit(Xi)，if fit(Xi)＜max fit(X)，則max fit(X)=fit(Xi)，同時記錄到公告板中;iffit(Xi)≥max fit(X)，則max fit(X)=max fit(X)。

(3)對Step2 循環迭代，直至達到最大迭代次數或者達到理論最佳適應度值。

Step3結果輸出:結合最優fit(Xi)及個體蜂最優位置指導分割圖像。

4 仿真結果與分析

為了驗證本文算法的可行性及高效性，分別從收斂性、求解質量、算法耗時3 個方面進行仿真實驗，并與魚群優化算法及粒子群優化算法進行了比較。為了體現本文算法的優越性，采用相同硬件環境:Microsoft Windows 7 Professional，CPU 為Intel Core 2.2 GHz，RAM 大小為2 GB。采用相同的隨機數據，設定種群數量n 為100、最大迭代次數m 為100，對2 幅大小均為256×256 的彩色圖像進行測試。

實驗1 算法收斂性比較

圖1、圖2 分別是圖像sunshade 與圖像pilot 運用粒子群優化算法(DPSO)、魚群優化算法(DAFO)、標準蜂群優化算法(DABC)及SLDABC 算法求解圖像分割的迭代收斂比較。

圖1 圖像sunshade 運用不同算法求解分割的迭代收斂比較

圖2 圖像pilot 運用不同算法求解分割的迭代收斂比較

由圖1、圖2 可以看出，DPSO、DAFO 與DABC 算法在局部最優解停留時間過長，搜索全局最優值緩慢，這是因為DPSO 算法、DAFO 算法與DABC 算法隨機搜索時變化較少且當搜索到局部最優解時較難跳出所致。而SLDABC 算法采用了自適應的權值調整模式，根據自身及群體的適應度有目的變化，同時由于SLDABC 算法采用了限速模型，使得算法即使搜索到局部最優也很容易擺脫，繼續向全局最優靠近。

實驗2 算法分割效果比較

圖像分割的好壞，肉眼判斷是最直接的評價標準。圖3、圖4 分別是圖像sunshade 與圖像pilot 的原圖及不同算法求解的分割效果。

彩色圖像sunshade 顏色信息量比較豐富，DPSO算法對顏色信息判別能力欠缺，將較大的地面區域劃分為背景。圖像pilot，由于其背景和前景的差別不大，DAFO 算法與DABC 算法對前景和背景某些差別不大的地方造成誤判，DAFO 算法將一部分藍天區域劃分成了背景區域，DABC 算法飛機頂部及飛行員影子劃分欠佳。SLDABC 算法能夠有效識別圖像所包含的信息，對前景和背景的區分明確，細節處理到位，準確地分割圖像，效果明顯優于DPSO、DAFO及DABC 算法。

圖3 圖像sunshade 運用不同算法的分割效果

圖4 圖像pilot 運用不同算法的分割效果

實驗3 Ncut 值及耗時比較

根據Normalized Cut 求解方式，可以看出Ncut值越小，指導分割的圖像越好，Ncut 值是判定圖像分割效果優劣的理論依據。表2 是DPSO、DAFO、DABC 及SLDABC 算法求解分割時的Ncut 值及耗時比較，為了方便比較，表2 列出的運行時間都是優化算法迭代求解的耗時。

表2 不同算法求解時的Ncut 值及耗時比較

由表2 數據可知，SLDABC 算法在數據上都要優于DPSO 算法和DAFO 算法。SLDABC 算法通過對個體蜂速度的限制使得其對初始種群的依賴較小，使個體蜂迅速脫離局部解空間，在更大的范圍內搜索最優解，增加了達到全局最優解的可能性，同時縮短了算法運行時間。

5 結束語

基于圖論的圖像分割已經成為圖像分割領域的一個熱點研究方向，是圖像理解、圖像分析、模式識別等領域中的關鍵。本文以標準蜂群算法為基礎，提出改進蜂群算法SLDABC，算法主要特點如下:(1)將標準蜂群離散化，定義蜂群速度，得到新的離散位置定義，利用智能優化算法有效解決了NP-hard問題;(2)針對智能優化算法容易局部收斂，將速度進行了限制，并設計了限速函數，求得的解的質量有較大提高;(3)在蜂群位置變化的過程中增加了自適應權重策略，動態改變和確定個體蜂當前的速度，有利于提高算法收斂速度;(4)為防止算法在迭代過程中舍棄最優解，設定一個公告板用來保存算法在迭代過程中尋找到的最優解。實驗結果表明，SLDABC 算法在解決歸一化彩色圖像分割問題上效果好且耗時少。

［1］Shi Jianbo，Malik J.Normalized Cuts and Image Segmentation ［C］//Proc.of IEEE CS Conf.on Computer Vision and Pattern Recognition.［S.1.］:IEEE Press，1997:731-737.

［2］Shi Jianbo，Malik J.Normalized Cuts and Image Segmentation［J］.IEEE Transactions on Pattern Analysis Machine Intelligence，2000，22(8):888-905.

［3］Xu Linli，Li Wenye，Dale S.Fast Normalized Cut with Linear Constraints［C］//Proc.of IEEE Conference on Digital Object Identifier.［S.1.］:IEEE Press，2009:2866-2873.

［4］Liu Haitao，Wang Yinlong，Yao Huifen.A New Normalized-cut Image Segmentation Algorithm Based on Watershed Transform ［J］.Applied Mechanics and Materials，2012，235(1):45-48.

［5］Beghi A，Cecchinato L，Cosi G，et al.A PSO-based Algorithm for Optimal Multiple Chiller Systems Operation［J］.Applied Thermal Engineering，2012，32(1):31-40.

［6］Lin Zhensi，Zhang Qishan，Liu Hong.Parameters Optimization of GM(1，1)Model Based on Artificial Fish Swarm Algorithm［J］.Theory and Application，2012，2(2):166-177.

［7］Gollapudi S，Pattnaik S，Bajpai O，et al.Bacterial Foraging Optimization Technique to Calculate Resonant Frequency of Rectangular Microstrip Antenna［J］.International Journal of RF and Microwave Computer-Aided Engineering，2008，18(4):383-388.

［8］Karaboga D，Basturk B.On the Performance of Artificial Bee Colony Algorithm［J］.Applied Soft Computing，2008，8(1):687-697.

［9］Sabat S L，Udgata S K，Abraharm A.Artificial Bee Colony Algorithm for Small Signal Model Parameter Extraction of MESFET［J］.Engineering Applications of Artificial Intelligence，2010，23(1):689-694.

［10］Yan Gaowei，Li Chuangqin.An Effective Refinement Artificial Bee Colony Optimization Algorithm Based on Chaotic Search and Application for PID Control Tuning［J］.Journal of Computational Information Systems，2011，7(9):3309-3316.

［11］張超群，鄭建國，王 翔.蜂群算法研究綜述［J］.計算機應用研究，2011，28(9):3201-3214.

［12］Kennedy J，Eberhart R C.A Discrete Binary Version of the Particle Swarm Algorithm［C］//Proc.of IEEE International Conference on Computational Cybemetics and Simulation.Washington D.C.，USA:IEEE Computer Society，1997:4104-4108.