基于鴿群優(yōu)化算法的圖像分割方法研究

胡春鶴， 王依帆， 朱書豪， 劉文定

(北京林業(yè)大學(xué) 工學(xué)院，北京 100083)

0 引言

圖像分割技術(shù)將圖像分割成若干個(gè)具有獨(dú)特性質(zhì)的區(qū)域，并從中提取出所需目標(biāo)，是當(dāng)前圖像分析和識(shí)別技術(shù)的研究熱點(diǎn)，被廣泛應(yīng)用于多個(gè)領(lǐng)域，如機(jī)器視覺[1]、交通控制[2]、衛(wèi)星定位物體[3]、病蟲害監(jiān)測(cè)[4]等.

圖像分割技術(shù)屬于典型的分類問題，依照不同的分類準(zhǔn)則，主要分為閾值分割[5]、區(qū)域分割[6]、邊緣分割[7]等.由于閾值分割相較于其他方法具有簡(jiǎn)單、易實(shí)現(xiàn)的特點(diǎn)，使其成為圖像分割領(lǐng)域應(yīng)用最為廣泛的一類方法[8].圖像閾值分割法根據(jù)提取目標(biāo)與背景在像素灰度上的差距，利用單一或多個(gè)閾值對(duì)像素點(diǎn)灰度進(jìn)行逐一比較實(shí)現(xiàn)分割[9].該方法分割效果優(yōu)劣的關(guān)鍵在于最優(yōu)閾值的選擇，這通常需要求解含有多種約束條件的非線性優(yōu)化問題.由于非線性優(yōu)化方程的梯度難以求解，使得現(xiàn)有求解過程復(fù)雜且耗費(fèi)大量運(yùn)算時(shí)間[10].

仿生群體智能優(yōu)化算法因其能夠有效處理非線性優(yōu)化問題，同時(shí)具有收斂速度快等特點(diǎn)而受到廣泛關(guān)注.利用此類方法解決圖像分割算法問題已成為這一領(lǐng)域的研究熱點(diǎn).仿生群體智能優(yōu)化算法是一類通過模擬自然界生物群體，如蟻群[11]、狼群[12]等群體行為而產(chǎn)生的隨機(jī)搜索與優(yōu)化算法.利用上述方法解決圖像分割問題，仍然存在著收斂速度慢、優(yōu)化結(jié)果易陷入局部最優(yōu)等問題.近年來，一種受鴿子歸巢行為啟發(fā)而產(chǎn)生的鴿群優(yōu)化算法(pigeon-inspired optimization,PIO)在群體智能優(yōu)化領(lǐng)域逐漸取得關(guān)注[13].該算法相較于一般仿生優(yōu)化算法具有結(jié)果最優(yōu)性、快速收斂性以及參數(shù)量適中等顯著優(yōu)勢(shì)，被廣泛用于解決無人機(jī)編隊(duì)[14]、控制參數(shù)優(yōu)化[15]等多個(gè)領(lǐng)域.顯然，筆者開展的適應(yīng)于圖像分割的PIO算法對(duì)該領(lǐng)域具有重要意義.

PIO算法以最大間類方差為優(yōu)化目標(biāo)，以像素概率分布有限為約束條件，將圖像分割問題建模為一類有約束的非線性優(yōu)化問題，修改PIO優(yōu)化算法對(duì)該優(yōu)化問題實(shí)現(xiàn)求解獲得最優(yōu)閾值，根據(jù)所得最優(yōu)閾值實(shí)現(xiàn)圖像分割[16].進(jìn)一步與現(xiàn)有粒子群優(yōu)化算法(particle swarm optimization,PSO)[17]、KSW[18]等圖像分割方法對(duì)比，驗(yàn)證本文方法的有效性.

1 問題描述

圖像前景與背景通常存在一定的灰度差異，若能找到區(qū)分上述差異的最優(yōu)灰度閾值，則可通過對(duì)比各像素點(diǎn)灰度值與最優(yōu)閾值進(jìn)行像素點(diǎn)二值化，即可實(shí)現(xiàn)分類，從而達(dá)到分割的目的.

假定給定的原始圖像的灰度直方圖包含L個(gè)灰度等級(jí)，設(shè)rk為第k個(gè)灰度等級(jí)，nk是在rk灰度等級(jí)上的像素點(diǎn)，N為總的像素點(diǎn)數(shù)，L為圖像的灰度值，則可以得出原始圖像的灰度概率分布函數(shù)滿足：

(1)

采用直方圖均衡化處理，可以使得圖像清晰度增加，即增加背景與前景的對(duì)比度.其實(shí)現(xiàn)通過式(1)所示累積分布函數(shù)P(rk)得到式(2)和式(3)所示圖像的原始灰度分布C(rk)和增強(qiáng)后灰度值Sk，達(dá)到圖像增強(qiáng)的目的：

(2)

Sk=(L-1)·C(rk),(0≤rk≤1).

(3)

根據(jù)像素點(diǎn)分布概率，若選取k作為閾值，則圖像將會(huì)被分割為大于和小于k的兩部分，這兩類像素點(diǎn)在圖像中的概率分別為：

(4)

(5)

式中：w是第一類像素點(diǎn)的概率；u是第二類像素點(diǎn)的概率，那么上述兩類像素點(diǎn)的內(nèi)部方差為：

(6)

(7)

式中：pi(·)為每點(diǎn)為該類像素點(diǎn)的概率；u0、u1分別為第一類、第二類像素點(diǎn)的均值.

實(shí)現(xiàn)最優(yōu)圖像分割的優(yōu)化目標(biāo)函數(shù)為：

A=maxδw2(K)，

(8)

其中，δw2為各類間方差，其計(jì)算公式為：

δw2=w0w1(u1-u0)2.

(9)

當(dāng)兩類的類間方差最大時(shí)所取得自變量的值即為最優(yōu)閾值，從而可根據(jù)此閾值得到圖像分割的結(jié)果.

考慮到圖像分割過程中，所提取的目標(biāo)圖像面積可以通過人眼目測(cè)、手動(dòng)尺寸測(cè)量或者其他的方法粗略地測(cè)出來從而得到了兩類像素點(diǎn)在圖像中概率的范圍，將其作為約束條件，則有：

α≤w0≤β，

(10)

λ≤w1≤γ.

(11)

2 基于鴿群優(yōu)化的圖像分割算法

2.1 鴿群優(yōu)化算法

鴿群優(yōu)化算法是根據(jù)鴿群歸巢的群體特性而建立的一類仿生優(yōu)化方法.當(dāng)鴿群距離巢穴較遠(yuǎn)時(shí)主要采用磁場(chǎng)輔助導(dǎo)航，具有全局最優(yōu)特性，而當(dāng)臨近目的地的時(shí)候則主要根據(jù)地標(biāo)導(dǎo)航，具有局部快速收斂特性.通過將鴿巢視作優(yōu)化目標(biāo)，鴿群視作優(yōu)化變量，則在距離最優(yōu)值較遠(yuǎn)時(shí)采用“磁場(chǎng)”全局優(yōu)化，用于提高尋找全局最優(yōu)適應(yīng)度點(diǎn)的速度；當(dāng)臨近優(yōu)化值較近時(shí)采用“地標(biāo)”交互優(yōu)化，加快收斂速度.

在鴿群模型中，由于鴿群位于磁場(chǎng)中，所以鴿群中每一個(gè)成員的位置以及速度都會(huì)受到磁場(chǎng)的影響.鴿子飛行的過程中位置和速度會(huì)持續(xù)更新.對(duì)于給定優(yōu)化目標(biāo)，上述位置與速度分別代表著優(yōu)化變量與優(yōu)化方向.當(dāng)算法開始時(shí)，每一點(diǎn)按照初始速度從初始位置出發(fā)，向擁有最優(yōu)適應(yīng)度的點(diǎn)收斂，到一定程度時(shí)，此類迭代停止，之后就需要引入地標(biāo)模型.

當(dāng)磁場(chǎng)模型的迭代結(jié)束后，位置的主要影響因素就變成了地標(biāo)和磁場(chǎng),這時(shí)鴿子飛行時(shí)就需要加大鴿群內(nèi)部的資源共享，從而提高收斂速度.通過引入鴿群的中心位置來表征鴿群內(nèi)部的信息交換以及資源共享.

2.2 圖像分割算法

針對(duì)最優(yōu)灰度閾值的尋找問題，采用上述鴿群算法來求解.磁場(chǎng)模型以及地標(biāo)模型保證圖像分割過程中每次優(yōu)化迭代向著最優(yōu)分割閾值收斂.假定鴿子飛行的過程中位置和速度根據(jù)式(12)～(13)進(jìn)行迭代持續(xù)更新：

Vi(t)=Vi(t-1)·e-Rt+rand·(Xg-Xi(t-1))；

(12)

Xi(t)=Xi(t-1)+Vi(t)，

(13)

式中：Xi(t)和Vi(t)分別表示鴿群中第i只鴿子的位置以及單位時(shí)間內(nèi)位置的變化量；R為磁場(chǎng)因子；Xg則為鴿群中位置最好的鴿子所在的位置，通過比較鴿群中所有鴿子的位置所對(duì)應(yīng)的最優(yōu)值；rand∈(0,1)是隨機(jī)數(shù).

假定鴿群中鴿子的總數(shù)為M，則鴿群中心位置Xc滿足：

(14)

在有限次迭代后，鴿群位置臨近目的點(diǎn)時(shí)鴿子位置變更為：

Xi(t)=Xi(t-1)·e-Rt+rand·(Xg-Xc).

(15)

基于對(duì)于全局收斂速度以及局部搜索速度的綜合考慮，假定R迭代次數(shù)滿足下式：

(16)

2.3 算法流程

筆者提出的基于鴿群優(yōu)化算法圖像閾值分割算法的具體步驟如下.

步驟1 確定初始的位置X0，鴿子總數(shù)G，兩種概率的最大值w0max、w1max，最小值w0min、w1min，初始速度V0，總的迭代次數(shù)N以及磁場(chǎng)模型的迭代次數(shù)N0.

步驟2 計(jì)算兩類像素點(diǎn)的概率w0、w1，兩類點(diǎn)的均值δ02、δ12，兩類間方差δw2(k).

步驟3 計(jì)算得到每點(diǎn)的適應(yīng)度f(x).

步驟4 將該點(diǎn)的f(x)與該點(diǎn)的歷史最佳位置pbest(i,t)的f(pbest(i,t))相對(duì)比，取較大者作為該點(diǎn)的歷史最佳位置.

步驟5 將該點(diǎn)的f(x)與全局的最優(yōu)位置Xg(t)的f(Xg(t))相對(duì)比，取較大者作為當(dāng)前全局最優(yōu)位置.

步驟6 在前N0代的迭代中，使用式(12)和式(13)來進(jìn)行更新點(diǎn)的速度和位置；在迭代N0代后使用式(15)來進(jìn)行位置的更新.

步驟7 重復(fù)步驟2～步驟6，直到迭代第N代后，迭代停止，輸出經(jīng)過圖像分割處理后的圖像，得到使得類間方差最大的k，將其作為閾值.

步驟8 將大于閾值的點(diǎn)分出來放到一幅圖像中，即完成圖像分割，輸出分割得到的圖像.

3 實(shí)驗(yàn)結(jié)果與對(duì)比分析

3.1 實(shí)驗(yàn)環(huán)境

為測(cè)試PIO優(yōu)化算法對(duì)圖像的分割性能，以圖1(a)所示Lena、圖1(b)所示Enamel和圖1(c)所示car作為測(cè)試對(duì)象進(jìn)行分割實(shí)驗(yàn)，隨后分別采用粒子群優(yōu)化算法(PSO)、KSW圖像分割算法與本文方法進(jìn)行對(duì)比測(cè)試.本文的實(shí)驗(yàn)硬件平臺(tái)為Intel 2.4 GHz CPU，內(nèi)存4 GB，仿真環(huán)境為MATLAB 2014，圖像大小為256×256.

圖1 典型測(cè)試圖像Fig.1 Typical image for test

測(cè)試中所有算法使用的個(gè)體總?cè)簲?shù)均為20，迭代次數(shù)均為100，磁場(chǎng)因子R為0.3.本文算法中N代表總的迭代次數(shù)，N0代表當(dāng)接近優(yōu)化值采用“地標(biāo)”交互優(yōu)化時(shí)的迭代次數(shù)，值由式(17)進(jìn)行確定.為體現(xiàn)結(jié)果的精確性和高效性，選取時(shí)間t和重疊度IOU(式(18))作為實(shí)驗(yàn)評(píng)判標(biāo)準(zhǔn).IOU為候選框area(G)與原標(biāo)記框area(C)的交集與并集的比值，即本文中分割圖像與原圖像的交集與并集的比值.重疊度越高，圖像分割效果越好.

N0=N-N×5%.

(17)

(18)

3.2 結(jié)果分析

分別用3種不同的算法對(duì)圖像進(jìn)行分割，為了提高結(jié)果的準(zhǔn)確性，使用3種不同的算法對(duì)3張具有代表性的圖片進(jìn)行了100次處理，得到了每次的處理時(shí)間，并分別與原灰度圖像進(jìn)行重疊度分析，結(jié)果如圖2～4所示.可以明顯看出，KSW算法分割閾值界限模糊，導(dǎo)致分割效果差，前景與背景有所融合，PIO與PSO算法切割效果清晰，從圖中所標(biāo)區(qū)域看到PIO算法細(xì)節(jié)切割更為精確，重疊度更高.

圖2 KSW分割結(jié)果Fig.2 KSW split result

圖3 PSO分割結(jié)果Fig.3 PSO split result

圖4 PIO分割結(jié)果Fig.4 PIO split result

圖2～4對(duì)比分析，KSW算法未將圖像與背景完全分割出來；再將PIO算法分割圖像與PSO算法分割圖像進(jìn)一步進(jìn)行細(xì)節(jié)對(duì)比，在標(biāo)紅圈部分可以看到，PIO算法分割效果精確性更高，圖像與背景分割明顯.

表1 各圖像對(duì)應(yīng)不同算法的分割時(shí)間和重疊率 Tab.1 Segmentation time and overlap of different image segmentation algorithms

為了避免隨機(jī)性，筆者采用箱式圖統(tǒng)計(jì)并對(duì)比3種算法的分割結(jié)果.

圖5 Lena的算法統(tǒng)計(jì)結(jié)果Fig.5 Lena’s algorithmic statistics

圖6 Enamel的算法統(tǒng)計(jì)結(jié)果Fig.6 Enamel’s algorithmic statistics

圖7 car的算法統(tǒng)計(jì)結(jié)果Fig.7 Car’s algorithmic statistics

分割時(shí)間上，PSO效率較低，PIO和KSW更占據(jù)優(yōu)勢(shì).進(jìn)而得到以下結(jié)論：

(1)KSW算法分割結(jié)果前景與背景有所融合，對(duì)比不顯著，圖像分割清晰度不夠，且在多次實(shí)驗(yàn)中分割結(jié)果差別較大，可看出算法穩(wěn)定性不足，在重疊度上也可以明顯看出，該算法較PIO和PSO分割效果不理想.

(2)相較于KSW算法，PSO算法和PIO算法有顯著改善，兩算法重疊度均高達(dá)0.90，在處理結(jié)果上具有較好效果，這主要是由于仿生智能優(yōu)化算法具有較強(qiáng)的魯棒性和搜索能力，能夠克服KSW算法抗干擾能力弱的缺點(diǎn)，提高圖像的分割精度，并求解到更優(yōu)的閾值.

(3)從時(shí)間上分析，KSW算法運(yùn)行效率較高，但由于其魯棒性差，分割精度低，在實(shí)際應(yīng)用中并不占優(yōu)勢(shì).PSO算法時(shí)間復(fù)雜度與迭代次數(shù)和維數(shù)線性相關(guān)，因此時(shí)間復(fù)雜度相對(duì)較高，運(yùn)行時(shí)間慢，效率低，是PIO算法運(yùn)行所用時(shí)間的兩倍，且通過對(duì)算法的分析，得出其在解決多峰值問題時(shí)易陷入局部最優(yōu)解，因此出現(xiàn)停滯現(xiàn)象而搜索不到更好的解.

(4)PIO算法不僅可以更加清晰地分割出前景與背景，而且對(duì)于單峰和多峰圖像分割效果均理想，具有較強(qiáng)的魯棒性和精確性，同時(shí)，采用地標(biāo)算子和地磁場(chǎng)相結(jié)合的方式進(jìn)行尋解，避免了算法陷入局部最優(yōu)解，更優(yōu)的尋解能力也使得該算法的收斂速度明顯更有優(yōu)勢(shì)，運(yùn)算效率有效提高，在實(shí)際應(yīng)用中可以滿足圖像的實(shí)時(shí)性要求.

3.3 參數(shù)靈敏度分析

為了進(jìn)一步優(yōu)化PIO算法，對(duì)同一張圖片在不同PIO算法種群數(shù)參數(shù)下進(jìn)行處理，分析參數(shù)對(duì)算法結(jié)果的影響.圖8～9給出了時(shí)間以及重疊率與種群數(shù)關(guān)系的擬合結(jié)果.

圖8 算法時(shí)間隨種群數(shù)的變化Fig.8 Algorithm time varies with population

圖9 重疊度隨種群數(shù)的變化Fig.9 The degree of overlap varies with population size

從圖8和圖9可以看出，運(yùn)算時(shí)間隨著種群數(shù)量的增加呈顯著增加趨勢(shì)，而重疊度相對(duì)于種群數(shù)量變化較小.因此PIO算法解決圖像分割問題僅依賴少量種群，即僅需少量時(shí)間就可以得到較好的分割結(jié)果.具體而言，當(dāng)種群數(shù)為30時(shí)，PIO算法分割圖像的結(jié)果最好，并且算法時(shí)間也比較小.

4 結(jié)論

筆者針對(duì)傳統(tǒng)圖像閾值分割方法最優(yōu)閾值選擇不理想且分割效率低等問題，提出了一種基于PIO優(yōu)化算法的圖像分割方法.該方法以分割閾值為優(yōu)化變量，圖像范圍為約束條件，建立有約束優(yōu)化方程，然后以隨機(jī)的分割閾值作為迭代初值，采用PIO算法求解得到最優(yōu)閾值，最后采用最佳閾值進(jìn)行圖像分割.PIO仿真以及與PSO、KSW算法對(duì)比結(jié)果表明，本文算法在時(shí)間和重疊度上均具有優(yōu)勢(shì)，具有很好的魯棒性與適應(yīng)性，且運(yùn)算效率高,收斂速度快，具有更強(qiáng)的尋優(yōu)能力，因此對(duì)于圖像分割具有精確性和高效性的優(yōu)點(diǎn).