一種求解圖像分割問(wèn)題的限速-離散蜂群優(yōu)化算法

周 遜，郭 敏，馬 苗

(陜西師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院，西安 710062)

1 概述

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

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

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

2.1 歸一化圖像分割

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

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

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

2.2 圖像預(yù)處理

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

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

3.1 標(biāo)準(zhǔn)蜂群算法原理

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

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

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

3.2 SLDABC 算法

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

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

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

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

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

3.2.2 離散化蜂群算法速度的表達(dá)

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

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

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

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

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

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

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

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

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

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

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

分析實(shí)驗(yàn)時(shí)間和實(shí)驗(yàn)效果，當(dāng)vSL取2 時(shí)，綜合分析結(jié)果較好。

3.2.5 適應(yīng)度函數(shù)

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

3.3 算法描述

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

Step1初始化:隨機(jī)生成n 個(gè)個(gè)體蜂。

Step2算法迭代:

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

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

(3)對(duì)Step2 循環(huán)迭代，直至達(dá)到最大迭代次數(shù)或者達(dá)到理論最佳適應(yīng)度值。

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

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

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

實(shí)驗(yàn)1 算法收斂性比較

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

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

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

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

實(shí)驗(yàn)2 算法分割效果比較

圖像分割的好壞，肉眼判斷是最直接的評(píng)價(jià)標(biāo)準(zhǔn)。圖3、圖4 分別是圖像sunshade 與圖像pilot 的原圖及不同算法求解的分割效果。

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

圖3 圖像sunshade 運(yùn)用不同算法的分割效果

圖4 圖像pilot 運(yùn)用不同算法的分割效果

實(shí)驗(yàn)3 Ncut 值及耗時(shí)比較

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

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

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

5 結(jié)束語(yǔ)

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

［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］張超群，鄭建國(guó)，王 翔.蜂群算法研究綜述［J］.計(jì)算機(jī)應(yīng)用研究，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.