楊 威,馬 瑜,孔聰雅,蘆 玥,王 慧
(寧夏大學(xué) 物理與電子電氣工程學(xué)院,寧夏 銀川 750021)
圖像分割是圖像處理的重要步驟,閾值分割法因其簡單有效性應(yīng)用廣泛。其中Otsu分割算法利用閾值將圖像分成目標(biāo)和背景兩類,離散度矩陣值最大時獲得最佳閾值,因其與圖像像素分布無關(guān),適合多類圖像分割。袁小翠等人以目標(biāo)出現(xiàn)的概率為權(quán)重,對Otsu算法的離散度矩陣進行加權(quán),提升了Otsu算法分割精度[1]。同時,粒子群算法、螢火蟲算法、蜂群算法等智能算法應(yīng)用其中,能夠改進Otsu分割算法實時性差的問題[2-4]。
狼群算法是2007年吳虎勝提出模擬自然界狼群分工搜索行為的一種智能算法。由于算法搜索能力強,已被廣泛應(yīng)用[5]?;诶侨核惴?,眾多學(xué)者提出很多改進,主要是對狼群算法搜索過程的改進,提高狼群的搜索速度和精度。王盈祥等人提出一種基于差分進化的狼群算法,通過對多個函數(shù)測試證明了改進算法的有效性[6]。焦瑞芳等人在狼群游走行為中引入隨機擾動策略動態(tài)調(diào)整算法權(quán)重,并在算法圍捕行為中引入混沌全局搜索,提高算法尋優(yōu)精度[7]。曹爽等人將PSO算法中的粒子尋優(yōu)過程引入到狼群算法游走、召喚行為中,利用混沌法對得到的次優(yōu)解進行優(yōu)化,提高算法的尋優(yōu)準(zhǔn)確度[8]。
在信號分析與處理過程中,需要借助恰當(dāng)?shù)臄?shù)學(xué)模型來解決,分?jǐn)?shù)階微積分的引入使其提升到新的高度[9]。2010年,Pires等人最早將分?jǐn)?shù)階算法引入PSO算法中,通過5個著名函數(shù)的測試分析驗證了分?jǐn)?shù)階算法對PSO算法收斂性的提升,并進一步驗證了算法的收斂速度與分?jǐn)?shù)階階次密切相關(guān)[10]。魏晶茹等提出了一種自適應(yīng)的分?jǐn)?shù)階粒子群算法,通過粒子的速度和位置信息自適應(yīng)地選取分?jǐn)?shù)階階次,使算法得到了更好的收斂性能[11]。近期, Mousavi等人將分?jǐn)?shù)階應(yīng)用于螢火蟲算法中,也取得了可觀的實驗結(jié)果[12]。考慮分?jǐn)?shù)階微積分在信號及圖像處理應(yīng)用的優(yōu)越性及狼群算法的簡單有效性,本文將分?jǐn)?shù)階優(yōu)化的狼群算法引入到Otsu圖像分割算法中,利用分?jǐn)?shù)階算法對過去狀態(tài)有記憶性的優(yōu)點,用自適應(yīng)分?jǐn)?shù)階階次來控制狼群在游走過程中的位置更新,并在狼群圍捕行為中引入粒子對稱分布方法[13],調(diào)整狼群圍捕過程中的位置,克服陷入局部最優(yōu)的缺點,結(jié)合二維Otsu分割算法來確定最佳分割閾值,加快了算法收斂速度。
傳統(tǒng)狼群算法模擬了狼群捕食過程中的游走、召喚和圍攻行為。在頭狼的領(lǐng)導(dǎo)下,探狼和猛狼互相合作尋找解空間中最優(yōu)解。
2.1.1 頭狼的選取
初始狼群數(shù)N,將解空間中具有最大目標(biāo)函數(shù)值的位置記為頭狼位置。如有多個最優(yōu)解,則隨機選取一頭作為頭狼Ylead。頭狼不參與游走和圍攻行為,直至在迭代過程中被具有更優(yōu)解的其他狼代替。
2.1.2 游走行為
選取最優(yōu)解中的Snum匹(頭狼除外)作為探狼開始游走行為。在游走過程中,如其目標(biāo)函數(shù)值Yim優(yōu)于Ylead,則替代頭狼;否則,探狼朝h個方向前進尋優(yōu),在d維空間中,探狼i的游走公式為:
(1)
其中:m∈{1,2,…,h},Pa為前進步長,Snum取[n/(α+1),n/α]之間的整數(shù)。α為探狼比因子。
探狼i在游走過程中記錄每步前進后該位置的目標(biāo)函數(shù)值Yim,選擇目標(biāo)函數(shù)值大的方向更新探狼位置,直到探狼i的目標(biāo)函數(shù)值Yim>Ylead或達到最大游走次數(shù)Tmax。
2.1.3 召喚行為
頭狼召喚附近Mnum匹猛狼向其靠近。其中Mnum=N-Snum-1,猛狼以步長Pb快速向頭狼靠近。猛狼i的行為公式為:
xid(t+1)=xid(t)+Pb·
(gd(t)-xid(t))/|gd(t)-xid(t)|,
(2)
式中g(shù)d為t代頭狼在第d維空間中的位置。若猛狼感知的適應(yīng)度值Yim>Ylead,便代替頭狼發(fā)起召喚行為。否則猛狼繼續(xù)搜索直到與頭狼的位置小于dnear進入圍攻行為。dnear可由下式得到:
(3)
w為距離判定因子,xmaxd和xmind分別為第d維空間的上限和下限。
2.1.4 圍攻行為
頭狼作為全局最優(yōu)值被視為猛狼圍攻方向。猛狼以步長Pc向頭狼靠近,猛狼圍攻行為公式為:
xid(t+1)=xid(t)+λ·
Pc·|gd(t)-xid(t)|,
(4)
其中λ為[-1,1]間均勻分布的隨機數(shù)。圍攻后,若有個體狼所處位置適應(yīng)度值大于原頭狼適應(yīng)度值,便更新狼位置信息,否則,頭狼位置不變。
其中,3種圍攻步長滿足以下關(guān)系:
Pa=Pb/2=2×Pc=|dmax-dmin|/S,
(5)
dmax和dmin分別為待尋優(yōu)變量的取值范圍的最大值和最小值,S為步長因子。
2.1.5 群體更新
按“由強到弱”分配食物,將R匹目標(biāo)函數(shù)值最小的狼隨機替代。R取[N/2×ξ,N/2]中的隨機數(shù),ξ是狼群更新比例因子。
基于不同的定義,分?jǐn)?shù)階微積分有不同的表達形式。最為常用的為Grumwald-Letniko定義(G-L定義)。
G-L定義的離散表達形式為[10]:
(6)
傳統(tǒng)狼群游走行為忽略了探狼之前的游走狀態(tài),尋優(yōu)結(jié)果取決于h的取值,若h較大,尋優(yōu)精度高但收斂速度慢;h過小算法容易陷入局部最優(yōu)。
令表達式(6)中的r=4,得:
(7)
由式(7)可看出,分?jǐn)?shù)階導(dǎo)數(shù)結(jié)果不僅與當(dāng)前項有關(guān),還與之前狀態(tài)值有關(guān),且過去事件的影響隨著時間的推移而減小。由于其固有的記憶特性,非常適合描述不可逆性和混沌等現(xiàn)象,所以考慮將其引入狼群算法的游走行為。
由式(1)可知,狼群每次的游走行為可描述為:
(8)
式(8)左邊為分?jǐn)?shù)階G-L定義階次v=1時(假設(shè)T=1)的離散形式,可以寫作:
(9)
結(jié)合公式(7),狼群的游走行為可表示為:
(10)
可以看出,分?jǐn)?shù)階階次影響著探狼位置更新。當(dāng)v很小時,將忽略先前的活動并容易陷入局部最優(yōu);當(dāng)v很大時,將呈現(xiàn)更多樣化的行為,從而可以探索新的解決方案。但是v太大,則花費時間多。所以本文將進化因子f引入公式對階次v進行修正,利用探狼位置信息自適應(yīng)地調(diào)整分?jǐn)?shù)階次,調(diào)整公式如下[11]:
(1)探狼i到其他探狼的平均距離計算為:
式中:N和D分別為探狼個數(shù)和空間維數(shù)。
其中,dg為全局最優(yōu)位置到其他探狼的平均距離,dmax和dmin為所有dix中的最大值和最小值。
(3)當(dāng)v∈[0.5,0.8]時,收斂速度更快,故:
v(f)=1/2e-0.47f∈[0.5,0.8]。
二維Otsu算法的橫坐標(biāo)為灰度,縱坐標(biāo)為灰度級與平均灰度級之差,即灰度-梯度二維直方圖,這樣,圖像的像素信息主要集中在平面一側(cè),且目標(biāo)和背景主要集中在梯度較小區(qū)域(圖像目標(biāo)和背景區(qū)域),圖像梯度值較大的點(圖像噪聲點)成功地和圖像的目標(biāo)及背景分離,減少噪聲對圖像分割的影響。設(shè)圖像總像素點數(shù)為N,nij為灰度i、梯度j的像數(shù)點數(shù),nij發(fā)生的概率為:
(11)
設(shè)分割閾值的平均灰度值為s,梯度值為t,圖像被閾值(s,t)分為背景類B和目標(biāo)類T,兩類出現(xiàn)的概率分別為:
(12)
背景類和目標(biāo)類對應(yīng)的均值向量uB和uT及所有像素點的總均值向量u分別如下:
(13)
定義離散度矩陣為:
(14)
圖像分割效果與離散度值成正比,因此取離散度值最大時的閾值作為最佳分割閾值:
tr(S(s*,t*))=max(tr(S(s,t))),
(15)
將Otsu算法的離散度矩陣作為改進狼群算法的尋優(yōu)函數(shù),采用粒子對稱分布方法改進狼群算法圍捕行為。算法步驟如下:
(1)參數(shù)初始化。設(shè)種群數(shù)N=20,個體狼位置xi,探狼比因子α=4,最大迭代次數(shù)NIter=100,最大游走次數(shù)Tmax=20,步長因子S=1 000。
(2)選取頭狼。將個體狼位置作為待尋優(yōu)的二維閾值向量,式(15)作為探狼目標(biāo)函數(shù),根據(jù)目標(biāo)函數(shù)值選出頭狼。
(3)游走行為。探狼根據(jù)游走公式(10)執(zhí)行游走行為,若探狼計算所得目標(biāo)函數(shù)值Yim>Ylead便代替頭狼進行召喚行為。否則,繼續(xù)游走行為直到最大游走次數(shù)Tmax,轉(zhuǎn)步驟(4)。
(4)召喚行為。猛狼根據(jù)式(2)向獵物靠近,在此過程中,若猛狼的目標(biāo)函數(shù)值Yim>Ylead,則取代頭狼執(zhí)行召喚行為,否則繼續(xù)搜索直到與頭狼的位置小于dnear時轉(zhuǎn)至步驟(5)。
(5)圍攻行為。猛狼及探狼根據(jù)式(4)向獵物移動,在移動過程中根據(jù)粒子對稱分布方法,調(diào)整狼群移動位置,實施圍捕行為。
(6)選取目標(biāo)函數(shù)值最大的個體狼作為頭狼,并對狼群群體進行更新。
(7)若算法達到最大迭代次數(shù),則輸出頭狼位置,作為最佳分割閾值,否則返回步驟(2)。
該算法具體流程圖如圖1所示。
圖1 分?jǐn)?shù)階狼群Otsu算法流程圖Fig.1 Flowchart of the two-dimensional Otsu based improved WPA
本文采用人物L(fēng)ena圖像、醫(yī)學(xué)肺部圖像及景物蘭花圖像進行實驗,并分別對比了本文提出的算法、傳統(tǒng)狼群優(yōu)化二維Otsu算法(WPA Otsu算法)以及文獻[11]提出算法(分?jǐn)?shù)階粒子群Otsu算法)的分割性能。
圖2 Lena圖像分割結(jié)果Fig.2 Segmentation results of the image Lena
采用適應(yīng)度值[11]和峰值信噪比(PSNR)[7]作為評價圖像分割效果的客觀評價指標(biāo)。適應(yīng)度值越大,圖像分割結(jié)果越好;PSNR值越大,算法抗噪性能越好。用適應(yīng)度曲線中達到收斂的迭代次數(shù)作為評價算法速度的指標(biāo),迭代次數(shù)越少,算法速度越快。實驗的硬件條件為:window7系統(tǒng),Intel i3處理器(2.53 GHz),2.00 GB內(nèi)存,MatlabR2013。
圖3 肺組織圖像分割結(jié)果Fig.3 Segmentation results of the image Lung
圖4 蘭花圖像分割結(jié)果Fig.4 Segmentation results of the image Orchid
主觀視覺上,對Lena圖像的分割處理,本文算法在紅色圖框區(qū)域保證了圖像細(xì)節(jié)部分的分割;對肺組織圖像的分割,本文算法能夠保證在指定組織處分割出完整清晰的輪廓;對景物蘭花圖像的分割,則顯示出更多細(xì)節(jié)。
由圖5(a)及表1的數(shù)據(jù)可以看出,對Lena圖像的分割結(jié)果,本文算法的適應(yīng)度值及PSNR值均高于另外兩種算法。由于適應(yīng)度值越大,Otsu分割算法中離散度矩陣的值越大,即目標(biāo)及背景類分割越明顯,可見本文算法提升了圖像分割結(jié)果的準(zhǔn)確度。同時,本文算法的PSNR值相較于另外兩種算法有提升,說明本文算法的抗噪性能得到了保障。由圖5(a)的適應(yīng)度曲線也可以直觀地看出,經(jīng)過10次迭代本文算法找到最佳閾值, 經(jīng)過60次迭代后WPAOtsu算法找到最佳閾值,經(jīng)過15次迭代后文獻[11]算法找到最佳閾值。 可知本文算法最先達到收斂。
(a)Lena圖像適應(yīng)度曲線(a)Fitness curves of image Lena
(b)肺組織圖像適應(yīng)度曲線(b)Fitness curves of image Lung
(c)蘭花圖像適應(yīng)度曲線(c)Fitness curve of image Orchid圖5 各圖像不同算法的適應(yīng)度曲線Fig.5 Fitness curves of different images
Tab.1 Segmentation results of image Lena by different algorithm
算法最佳閾值迭代次數(shù)適應(yīng)度值PSNRWPA Otsu算法(233,134)602 613.29.016 3文獻[11]算法(143,134)152 622.39.016 3本文算法(135,142)102 622.49.016 4
表2 3種算法對肺組織CT圖像分割結(jié)果對比
Tab.2 Segmentation results of image CT Lung by different algorithm
算法最佳閾值迭代次數(shù)適應(yīng)度值PSNRWPA Otsu算法(60,63)402 948.713.119文獻[11]算法(59,63)172 948.613.119本文算法(60,63)62 948.813.157
表3 3種算法對蘭花圖像分割結(jié)果對比
Tab.3 Segmentation results of image Orchid by different algorithm
算法最佳閾值迭代次數(shù)適應(yīng)度值PSNRWPA Otsu算法(112,117)701 574.58.098 6文獻[11]算法(111,118)201 574.48.098 6本文算法(112,119)41 574.68.135 0
由圖5(b)及表2可以看出,對肺組織圖像的分割結(jié)果,本文算法的適應(yīng)度值較文獻[11]算法有所提高,并與WPA Otsu算法持平,本文算法的PSNR值較另外兩種算法有提高,說明本文算法能夠保證圖像的分割精度,且抗噪性能得到保證。從圖5(b)的適應(yīng)度曲線可以看出,本文算法經(jīng)過6次迭代找到最佳閾值,WPAOtsu算法在40次迭代后找到最佳閾值,文獻[11]算法經(jīng)過17次左右找到最佳閾值。說明相較于另外兩種算法,本文算法的收斂速度更快。
由圖5(c)及表3可以看出,蘭花圖像的適應(yīng)度值及PSNR值相比另兩種算法均有增加,可見本文算法能夠保證分割準(zhǔn)確度,且抗噪性能提升。由圖5(c)的適應(yīng)度曲線可知,經(jīng)過4次迭代,本文算法找到最佳閾值, 經(jīng)70次左右迭代,WPAOtsu算法達到完全收斂,經(jīng)20次迭代,文獻[11]算法達到收斂。說明相對于另外兩種算法,本文算法收斂速度有了大幅度提高。
綜上3類不同領(lǐng)域圖像,由4.1節(jié)中的分割結(jié)果可知,從主觀視覺比較本文算法分割結(jié)果與另兩種算法分割結(jié)果,可知本文算法能夠保證分割結(jié)果的精度。由4.2節(jié)的適應(yīng)度曲線對比可知,本文算法采用自適應(yīng)分?jǐn)?shù)階階次來控制狼群的游走過程,結(jié)合狼群算法的召喚、圍攻行為,極大提高了全局搜索能力,克服了陷入局部最優(yōu)缺點,因此相較另兩種算法,本文算法全局收斂能力更強,收斂速度更快。各參數(shù)對比進一步說明,本文改進的算法,提升了適應(yīng)度值,即提升了Otsu分割算法中離散度矩陣的值,離散度矩陣值越大,說明圖像分割效果越明顯,因此本文算法保證了圖像分割的準(zhǔn)確度;而本文算法達到完全收斂的迭代次數(shù)明顯少于另外兩種算法,可見本文算法用在圖像的分割上收斂速度相比其他算法要快得多;同時,本文算法的PSNR值也有提高,說明本算法的抗噪性能得到保證。
為提高傳統(tǒng)狼群優(yōu)化二維Otsu分割圖像算法的尋優(yōu)能力,克服算法容易陷入局部最優(yōu)的缺點,本文將自適應(yīng)分?jǐn)?shù)階微分引入到狼群算法并應(yīng)用于Otsu分割圖像算法中。利用分?jǐn)?shù)階微分對過去狀態(tài)有記憶性的優(yōu)點,用自適應(yīng)分?jǐn)?shù)階階次來控制狼群在游走過程中的位置更新,提高狼群尋優(yōu)能力,并在狼群圍捕行為中引入粒子對稱分布方法。在移動過程中,通過調(diào)節(jié)狼群在最優(yōu)解周圍的分布,使狼群在最優(yōu)解兩側(cè)的個數(shù)均等,進而調(diào)整狼群圍捕過程中的位置,提高種群多樣性,克服算法陷入局部最優(yōu)的缺點,結(jié)合二維Otsu分割算法確定最佳分割閾值,加快算法收斂速度。實驗結(jié)果表明,從主觀視覺和客觀指標(biāo)上都驗證了該算法分割圖像可以保證分割結(jié)果的精確性。本文算法收斂次數(shù)較傳統(tǒng)狼群算法平均提升50次左右,較文獻[11]算法平均加快10次左右。說明本文算法收斂速度更快。因此相較于另外兩種算法,本文算法在分割圖像時收斂速度更快,并且能夠保障圖像分割精度。