周 遜，郭 敏，馬 苗

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

1 概述

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

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

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

2.1 歸一化圖像分割

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

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

其中，asso(A，V)表示A 中節(jié)點與圖G 中所有節(jié)點之間的聯(lián)系程度;asso(B，V)表示B 中節(jié)點與圖G 中所有節(jié)點之間的聯(lián)系程度?？梢钥闯鯪cut 值越小，劃分的結(jié)果越好。

2.2 圖像預處理

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

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

3.1 標準蜂群算法原理

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

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

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

3.2 SLDABC 算法

SLDABC 算法以標準離散蜂群優(yōu)化算法為基礎(chǔ)，給出了速度與慣性權(quán)重的定義，引入自適應慣性權(quán)重調(diào)整模式控制算法的收斂，設(shè)定限速模型來控制種群的多樣性。

3.2.1 速度和慣性權(quán)重的定義

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

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

慣性權(quán)重的調(diào)控影響到算法的收斂速度及算法的穩(wěn)定性。

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表示慣性權(quán)重。

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

其中，r 為［0，2］間的隨機數(shù)。

3.2.3 自適應慣性權(quán)重調(diào)整機制

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

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

3.2.4 限速-離散蜂群算法模型設(shè)計

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

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

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

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

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

3.2.5 適應度函數(shù)

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

3.3 算法描述

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

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

Step2算法迭代:

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

(2)利用式(10)控制速度變化對位置變化影響的幅度，通過式(5)進行速度更新，式(6)和式(7)進行慣性權(quán)重更新，通過一定概率選擇個體蜂進行跟隨，計算新的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 循環(huán)迭代，直至達到最大迭代次數(shù)或者達到理論最佳適應度值。

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

4 仿真結(jié)果與分析

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

實驗1 算法收斂性比較

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

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

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

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

實驗2 算法分割效果比較

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

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

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

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

實驗3 Ncut 值及耗時比較

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

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

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

5 結(jié)束語

基于圖論的圖像分割已經(jīng)成為圖像分割領(lǐng)域的一個熱點研究方向，是圖像理解、圖像分析、模式識別等領(lǐng)域中的關(guān)鍵。本文以標準蜂群算法為基礎(chǔ)，提出改進蜂群算法SLDABC，算法主要特點如下:(1)將標準蜂群離散化，定義蜂群速度，得到新的離散位置定義，利用智能優(yōu)化算法有效解決了NP-hard問題;(2)針對智能優(yōu)化算法容易局部收斂，將速度進行了限制，并設(shè)計了限速函數(shù)，求得的解的質(zhì)量有較大提高;(3)在蜂群位置變化的過程中增加了自適應權(quán)重策略，動態(tài)改變和確定個體蜂當前的速度，有利于提高算法收斂速度;(4)為防止算法在迭代過程中舍棄最優(yōu)解，設(shè)定一個公告板用來保存算法在迭代過程中尋找到的最優(yōu)解。實驗結(jié)果表明，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.