一種基于Levy-人工蜂群的三維Otsu閾值分割算法*

黃翠玲，孔韋韋，李 萌，呼亞萍

(1.西安郵電大學(xué) 計算機學(xué)院，西安 710121；2.陜西省網(wǎng)絡(luò)數(shù)據(jù)分析與智能處理重點實驗室，西安 710121)

0 引 言

圖像分割技術(shù)是計算機視覺和數(shù)字圖像處理領(lǐng)域中的一項重要研究內(nèi)容，其主要目標是將圖像目標與背景按照某種規(guī)則分開來，目前已被廣泛應(yīng)用于遙感[1]、軍事[2]、氣象[3]、醫(yī)療[4]等方面。

在眾多圖像分割方法中，基于閾值的分割方法占有十分重要的地位。其中，日本學(xué)者Otsu[5]提出的一維Otsu算法以目標和背景的類間方差為準則，計算復(fù)雜度較低，并能在一般情況下取得較好的分割性能。然而，當該算法用于含噪圖像的分割任務(wù)時效果并不理想。在此基礎(chǔ)上，二維Otsu分割算法[6]綜合利用了圖像像素點與其鄰域空間的相關(guān)信息，當作用于低對比度、低信噪比的目標分割時，二維Otsu算法具有較理想的分割效果，但其對象區(qū)域和背景區(qū)域上的概率和近似為1的假設(shè)不夠普遍。為此，文獻[7]提出了一種基于三維Otsu算法的閾值分割算法，通過限定迭代空間和搜索空間，并用布谷鳥搜索算法進行尋優(yōu)，但該方法對于椒鹽噪聲的圖像仍然存在錯分的問題。徐青等[8]提出了新的基于分解直方圖的三維Otsu分割算法，能夠滿足一定的實時性，但分解技術(shù)使得目標及背景部分都有不少錯分，分割效果不夠理想。劉思言[9]提出了一種直方圖區(qū)域合并算法，在每次迭代中減少一個閾值，并挑選出相鄰區(qū)域進行合并，直到達到符合要求的閾值數(shù)目。姜圣濤等[10]利用自適應(yīng)差分進化算法選取閾值分割所需要的最佳參數(shù)，把參數(shù)帶入廣義模糊熵的補函數(shù)進而得到圖像的閾值。文獻[11]提出了基于白頂帽規(guī)模的粗麻布血管增強濾波器和多閾值Otsu方法，開發(fā)了一種三維Otsu混合分割方法，解決了強度不均勻的問題。文獻[12]提出了一種基于三維Otsu和多尺度圖像表示的閾值分割算法，使用多數(shù)表決規(guī)則將分割結(jié)果加以合并以獲得最終分割結(jié)果。高揚等[13]提出了一種改進的人工蜂群算法來處理圖像分割問題，能夠取得開發(fā)和探索的平衡，但其更適合解決多級圖像分割問題，普遍性不夠。

綜上所述，傳統(tǒng)三維Otsu算法在一維Otsu算法的基礎(chǔ)上改進，由于維度的增加，時間復(fù)雜度也大幅增加。在此背景下，本文為了提高三維Otsu算法的運算效率，提出了一種通過Levy-人工蜂群算法進行尋優(yōu)的算法，從而獲取到最佳閾值。仿真實驗結(jié)果表明，該算法能夠有效降低計算復(fù)雜度以及閾值獲取的時間，分割后的圖像效果也更為理想。

1 三維Otsu算法

三維Otsu算法利用原圖像、鄰域平滑圖像及鄰域中值圖像構(gòu)成了三維直方圖，具有一定的抗噪性，其原理如下：假設(shè)一幅圖像的尺寸為M×N，灰度級為L，f(x,y)為像素點(x,y)的灰度值，g(x,y)為像素點(x,y)的鄰域均值，h(x,y)為像素點(x,y)的鄰域中值，則g(x,y)與h(x,y)的灰度級也為L。g(x,y)和h(x,y)分別定義為

(1)

(2)

式中：med表示中值，k×k為鄰域大小。

將任一像素點(x,y)的f(x,y)、g(x,y)以及h(x,y)構(gòu)成一個三元組(i,j,k)，并將該三元組定義為三維直方圖。顯然，該三維直方圖對應(yīng)一個尺寸為L×L×L的正方體區(qū)域，如圖1(a)所示，其三個坐標分別表示圖像像素點的灰度值、鄰域均值及鄰域中值。設(shè)mijk為像素點(i,j,k)出現(xiàn)的頻數(shù)，則(i,j,k)出現(xiàn)的頻率pijk由下式確定:

(3)

設(shè)分割閾值為(s,t,q)，其將三維直方圖分為8個部分，如圖1(b)～(d)所示。其中，區(qū)域0和1分別代表圖像的背景和目標，區(qū)域2～7 表示圖像邊界附近的邊緣和噪聲。由于邊界區(qū)域的像素點遠小于圖像背景與目標區(qū)域的像素點，因此可假設(shè)目標和背景區(qū)域的概率和近似為1。

圖1 圖像的三維直方圖

令圖像背景和目標對應(yīng)的兩個區(qū)域分別為C0與C1，則C0與C1對應(yīng)的概率p0、p1可以分別表示為

(4)

(5)

與二維Otsu算法類似，可以采用sB作為trsB(i,j,k)為類間的離散度測度，即

trSB(i,j,k)=

(6)

(i*,j*,k*)=maxtrSB(i,j,k) 。

(7)

2 改進算法的三維Otsu算法

2.1 人工蜂群算法原理

人工蜂群(Artificial Bee Colony,ABC)算法具有較快的收斂速度。該算法將人工蜂群分為引領(lǐng)蜂、跟隨蜂和偵察蜂三類。在搜索過程中，引領(lǐng)蜂和跟隨蜂負責搜索新蜜源，即尋找最優(yōu)解，而偵察蜂負責觀察是否陷入局部最優(yōu)，若陷入局部最優(yōu)則隨機搜索其他新蜜源。每個蜜源代表一個可能解，蜜源的花蜜量代表相應(yīng)解的質(zhì)量。

2.2 Levy飛行模型

Levy飛行是法國數(shù)學(xué)家萊維(Levy)提出的一種概率分布，已證實自然界的很多動物覓食軌跡遵從Levy分布，Levy飛行服從Levy分布。Levy飛行是一種頻繁的短距離與偶爾的長距離之間的運動軌跡，能夠加強信息的交互，避免搜索過程陷入局部最優(yōu)[14]。Levy飛行如下式:

Levy～u=t-λ，1<λ≤3。

(8)

由式(8)可以看出，Levy基本上形成了具有冪律步長分布且尾巴較重的隨機游走過程。 Levy可以最大化提高未知的、大型環(huán)境的搜索效率。Levy分布的隨機步長如下:

(9)

式中：

(10)

(11)

假設(shè)β=1.5，l=50，起點為(0,0)，連續(xù)100步，Levy飛行軌跡如圖2所示。

圖2 Levy飛行軌跡圖

由圖2可以看出，在Levy的飛行中，短距離深入和偶爾的長距離行走交替發(fā)生，因此搜索的部分解靠近局部最優(yōu)值，從而加快了搜索速度；搜索的另一部分解遠離局部最優(yōu)值，可以避免算法陷入局部最優(yōu)。

2.3 改進人工蜂群算法

ABC算法的具體步驟如下：

Step1 初始化各個參數(shù)，確定搜索范圍，并且按照式(12)隨機產(chǎn)生初始解：

(12)

Step2 引領(lǐng)蜂在蜜源附近按式(13)進行領(lǐng)域搜索產(chǎn)生新蜜源:

Xij′=Xij+R(Xij-Xkj) 。

(13)

式中：R為[0,1]間的隨機數(shù)。

Step3 跟隨蜂根據(jù)引領(lǐng)蜂分享的蜜源信息，按照式(14)計算概率：

(14)

解的適應(yīng)度函數(shù)為

(15)

式中：fi為解的函數(shù)值。

Step4 跟隨蜂依據(jù)概率Pi選擇解或者蜜源，跟隨蜂在蜜源i附近根據(jù)式(13)產(chǎn)生一個新蜜源，并計算該位置下適應(yīng)度函數(shù)值。

Step5 比較引領(lǐng)蜂和跟隨蜂搜索的蜜源的花蜜數(shù)量大小，其中引領(lǐng)蜂、蜜源位置由花蜜數(shù)量較優(yōu)的解來表示。

Step6 判斷是否有放棄的解，若有則相應(yīng)偵察蜂替換為引領(lǐng)蜂，偵察蜂根據(jù)式(13)隨機搜索新的食物源。

Step7 記錄到目前為止最好的新蜜源。

Step8 判斷新確定的蜜源、跟隨蜂、引領(lǐng)蜂位置是否滿足循環(huán)終止條件，如果滿足，循環(huán)結(jié)束，輸出最佳蜜源位置，即最優(yōu)分割閾值；否則，返回Step 2繼續(xù)搜索。

在經(jīng)典的人工蜂群算法中，種群的初始化位置是隨機的，如式(12)所示。該方法雖然簡單，但算法的求解效率會降低，且算法易陷入局部最優(yōu)的問題。因此為了解決該問題，本文算法在原始算法的蜜源位置更新操作中引入了Levy飛行機制和改進的位置更新方法，進一步提高了蜂群算法的全局搜索能力。Levy飛行機制會產(chǎn)生隨機跳躍和方向上的極速變化，能夠擴展搜索空間，并有效避免蜂群算法陷入局部最優(yōu)。

(16)

(17)

本文提出的人工蜂群優(yōu)化的三維Otsu圖像分割算法是基于灰度閾值實現(xiàn)的圖像分割；人工蜂群算法采用輪盤賭方式迭代搜索新蜜源，該方式具有更多的隨機性，并評價Levy飛行路徑對應(yīng)的最大類間方差，獲得最佳分割閾值。算法流程圖如圖3所示。

圖3 算法流程圖

該算法實現(xiàn)過程簡單，參數(shù)較少，結(jié)合Levy飛行策略，能避免算法陷入局部最優(yōu)的問題。同時，該算法適合處理分辨率高的圖像，算法時間復(fù)雜度明顯減小，能夠避免存儲空間的浪費，并且抗噪性大大提升，算法可以較快地找到最佳閾值。

3 仿真實驗

3.1 實驗條件

為了驗證本文算法的可行性和有效性，Matlab R2018b軟件上進行實驗，實驗平臺為Windows 8.1，64位操作系統(tǒng)，4 GB內(nèi)存。

首先選取Benchmarks測試函數(shù)的常用函數(shù)對本文算法及傳統(tǒng)三維Otsu算法進行尋優(yōu)性能測試。實驗中用到的測試函數(shù)，如表1所示。為了保證實驗的公平性，考慮到算法隨機性對實驗結(jié)果的影響，將本文算法及傳統(tǒng)三維Otsu算法分別運行10次。將實驗中的參數(shù)進行設(shè)定，蜂群總數(shù)為100，循環(huán)次數(shù)為1 000，limit為100，優(yōu)化參數(shù)的空間為[-500,500],兩種算法下測試函數(shù)的平均值如表2所示。

表1 Benchmarks測試函數(shù)

表2 算法測試結(jié)果

通過對比兩種算法下測試函數(shù)的平均值可以得知，本文算法收斂性更好，其求解精度比傳統(tǒng)三維Otsu算法好，性能也略優(yōu)于傳統(tǒng)三維Otsu算法，尋優(yōu)能力也更強，尤其是Sphere函數(shù)和Griewank函數(shù)在分割精度與穩(wěn)定性方面有很大的提升。

3.2 主觀評價結(jié)果

為驗證本文算法的分割效果，實驗選取Lena、man、Plane、Kids、Boat 5幅含噪圖像，顯示Lena實驗結(jié)果，將本文算法與文獻[10]算法、遺傳算法以及傳統(tǒng)三維Otsu算法進行對比。分割結(jié)果如圖4所示。

圖4 Lena圖像分割結(jié)果

從直觀視覺效果來看，文獻[10]算法分割圖像其輪廓相對清晰，但噪聲去除較為粗糙；三維Otsu算法噪聲處理結(jié)果較為明顯，但容易出現(xiàn)圖像邊緣信息保存不完整的現(xiàn)象；遺傳算法在邊緣信息保存方面優(yōu)于三維Otsu算法，但在大噪聲點易產(chǎn)生階梯效應(yīng)；與上述三種算法相比，本文算法分割得到的圖像區(qū)域一致性較好，圖像更清晰，并且圖像的抗噪性也更好，能夠?qū)D像與背景更好地分割出來。

3.3 客觀評價結(jié)果

為了定量地評價各優(yōu)化算法在圖像分割精度方面的能力，本文對各算法的均方誤差(Mean Square Error,MSE)和峰值信噪比(Peak Signal-to-Noise Ratio,PSNR)指標進行比較，其結(jié)果如表3和表4所示。首先，本文算法的MSE數(shù)值略小于其他優(yōu)化算法，其得到的分割誤差更小，分割效果相對較好；其次，本文算法PSNR數(shù)值高于另外兩種算法，說明分割圖像的失真程度更低，更接近于原圖像。由表3和表4不難看出，各優(yōu)化算法數(shù)值上差別不大，但本文算法相對于其他算法仍有一定優(yōu)勢，因此可以得出，本文算法的分割精度更高，獲得的分割效果更好。

表3 不同算法MSE值對比

表4 不同算法PSNR值對比

3.4 分析與討論

為了進一步評價幾種算法及本文算法在閾值分割方面的性能，本文對不同算法程序運行時間進行了比較與分析。為了保證數(shù)據(jù)的公平性，每組實驗均進行5次，并取其平均值作為本實驗結(jié)果的數(shù)據(jù)。各算法的平均運行時間如表5所示。

表5 各算法平均運行時間

由表5可以看出，本文算法在平均運行時間方面比其他幾種算法都要低，充分表明本文算法在分割圖像復(fù)雜度方面有很大的優(yōu)越性，更適用于實時性更高的場合。

4 結(jié)束語

針對三維Otsu算法分割效率低的問題，本文采用Levy飛行對人工蜂群算法進行優(yōu)化，加強了各人工蜂間的信息交互能力，且收斂速度更快；并將三維Otsu算法與之結(jié)合，提出了一種基于人工蜂群優(yōu)化的三維Otsu算法，有效降低了閾值分割時間復(fù)雜度。與傳統(tǒng)三維Otsu算法相比，本文算法得到的分割圖像精度更高，提高了運行效率，可為后續(xù)的目標檢測、識別等做更有效的準備。如何針對三維Otsu算法進行更好的優(yōu)化將是下一階段需要研究的主要問題。