融合改進人工蜂群與Otsu的圖像分割算法

徐 武,王欣達,高 寒,秦浩然

(1. 云南民族大學電氣信息工程學院,云南 昆明 650000;2. 中國石油運輸公司,新疆 烏魯木齊 830014)

1 引言

圖像分割就是把圖像分成若干個特定的、具有獨特性質的區域并提出感興趣目標的過程,是在整個圖像處理流程中一個至關重要的環節,隨著圖像分割技術的發展,它在影像醫學、無人駕駛、增強現實等方面都有著不俗的作用。人工蜂群算法是一種基于種群的元啟發式智能算法,人工蜂群性能主要取決于搜索方程和個體選擇策略,基本人工蜂群的搜索方程包含隨機個體信息較強,相較于一般群體智能優化算法。

遺傳算法的全局搜索和局部開發在求解過程中表現出互補性,但在操作上又具有矛盾性,為更好的平衡二者,同時滿足求解效率和求解精度,相關學者從搜索機制改進和融合算法等方面進行了有效研究。王勛等[2]提出了一種將遺傳算法與混沌系統和頻度記憶相結合的分割方法,降低了誤配率并提高了魯棒性。朱瑛等[3]提出了一種運用蟻群算法結合二維Otsu的改進算法,提高了其魯棒性同時還具有較好的抑制噪聲的效果。劉申曉等[4]將Otsu算法與粒子群算法相結合,其適應度函數為類間方差,再對粒子群算法進行改進優化,在不影響原本分割效果的情況下,成功地減小了目標的失真度。黃翠玲等[5]提出將人工蜂群算法與Otsu分割算法相結合,并提出反向學習策略產生新蜜源,提高了其分割效果。李云紅等[6]在對紅外目標進行分割的基礎上,引入了人工蜂群算法,將Otsu算法與其相結合,處理后得到了更加精確的分割目標。

通過分析,雖然上述方法都可以有效地對目標圖像進行分割,但因都基于RGB顏色空間,導致有著墜入局部最優次數多、收斂速度不夠迅速、適應值精度不高等缺點。本文提出了一種在HSV空間進行對人工蜂群算法改進并與二維Otsu融合的算法。在將RGB顏色空間轉化到HSV顏色空間的基礎上,通過混沌規則和差分進化優化初始化種群和建立新的引領蜂搜索方程,克服了原算法收斂速度慢和趨于局部最優的缺點。結果表明,經過改進算法處理之后的目標圖像,具有較強的抗噪能力,分割精準度也大幅提高。

2 HSV顏色空間的轉換

圖像采集設備所采集的圖像通常為RGB圖像[7],RGB圖像也被廣泛應用在圖像處理的各領域,但RGB 圖像也有自身的局限性,在RGB顏色空間中R、G、B三通道分量以線性組合方式表示不同顏色,難以精確表示不同顏色,定量分析困難[8]。

HSV色彩空間具備良好的設備無關性,因此在圖像處理中具有一定的普適性,而且人類視覺色彩空間與HSV更加匹配。對于彩色目標而言HSV色彩空間在局部顏色相同的圖像區域,其色相值一致性很高,非常便于圖像分割[9]。故本文采用將RGB圖像轉換HSV圖像的方法。

HSV色彩空間中H是色調,用來表示各種色彩;S是飽和度,用來表示顏色值光譜色所占的比值;V是亮度,用來表示顏色明亮的程度。

RGB空間HSV空間的具體步驟:

步驟1:先對原來的RGB顏色空間的R、G、B轉換為0到1之間的實數,如式(1)所示

(1)

設(r、g、b)為R空間的1個點,歸一化后,其為[0,1]之間的實數,減少計算的復雜度。

步驟2:根據計算出r、g、b的值計算出H、S、V的值,如式(2)、(3)、(4)所示

(2)

(3)

V=max

(4)

式中,max和min分別為r、g、b中的最大值和最小值。

H分量值規范化在0～360之間,S分量規范化在0～255之間,但在計算機數值計算時,會將H、S歸一化為[0,1]之間的實數。

3 人工蜂群算法

人工蜂群算法是研究蜜蜂的社會體系后,模仿蜜蜂在蜜源中收集蜂蜜的行為而總結提煉出的一種解決多變量函數優化問題的算法,以蜜蜂收集蜂蜜的驚人效率,最終在群體中使全局最優值突現出來[10]。

ABC算法的具體步驟如下:

步驟1:蜜源的初始化,隨機生成多個蜜源,如式(5)所示

(5)

式中,Xij為第i個蜜蜂第j維搜索后的位置,Xjmax表示第j維變量的最大值,Xjmin表示第j維變量的最小值。

步驟2:引領蜂在蜜源按式(6)搜索新蜜源

X′ij=Xij+R(Xij-Xkj)

(6)

式中:R為[0,1]間的隨機數。

步驟3:跟隨蜂將采用輪盤賭的方法進行對引領蜂的選擇,并按照式(7)計算概率

(7)

解的適應度函數為式(8)

(8)

步驟4:計算并記錄該位置下適應度函數值,在選擇的引領蜂蜜源的領域根據式(6)尋找新的蜜源。若新的蜜源比之前的好,則跟隨蜂代替之前的引領蜂。

步驟5:如果一個蜜源在閾值L內沒有找到更好的蜜源,則將該蜜源遺棄,并產生偵察蜂按照式(9)尋找更好的蜜源

(9)

式中,trial為目前已經迭代的次數,L為迭代次數的上限。

步驟6:記錄到目前為止最好的新蜜源,判斷新確定的蜜源、跟隨蜂、引領蜂位置是否達到最大迭代次數,如果達到,輸出最佳蜜源位置,即最優分割閾值(s,t),否則,返回步驟2。

4 二維Otsu算法

最大類間方差法,又被稱為Otsu算法,它將未處理的目標通過其灰度值來生成閾值,之后將目標根據生成的閾值來分為前景與背景,它們之間最大間類方差的差別越大,經過Otsu算法處理之后的目標也就越明顯。由于一維Otsu算法在信噪比低的圖像中分割效果較差,而二維Otsu算法利用圖像的局部信息,可有效避免噪聲的影響[11],為了提高人工蜂群算法的運行效率,本文采用二維Otsu分割算法。

設有一幅大小為M×N的灰度圖像,i為灰度值,L為灰度級數,則梯度值為j的像素nij的概率如式(10)

(10)

背景A和目標B的概率如式(11)、(12)

(11)

(12)

式中,s和t分別為分割閾值的平均灰度級和梯度級。

背景A和目標B的均值向量uA和uB分別為式(13)、(14)

(13)

(14)

圖像的總均值向量u如式(15)

(15)

兩像素間的離散度矩陣如式(16)

S(s,t)=pA(uA-u)(uA-u)T+pB(uB-u)(uB-u)T

(16)

背景類和目標類間的差別與離散度測度成正比,因此最佳閾值(s*,t*)為離散度選取最大時的閾值,如式(17)

tr(S(s*,t*))=max(tr(S(s,t)))

(17)

5 改進的人工蜂群算法

為了提高算法的搜索能力,同時提高算法開采能力和收斂速度,本文在標準蜂群算法的基礎上,提出了一種改進的人工蜂群算法。算法主要是對種群初始化和引領蜂搜索方程進行改進。

5.1 種群初始化的改進

種群初始化是進化算法的一個關鍵點,因為它影響著算法的收斂速度和最終解的質量。為了選擇更好的初始種群,論文提出一種新的初始化方法,利用具有遍歷性、隨機性的混沌系統和不規則性的對立的學習方法來生成初始種群。

在Logistic映射式的基礎上(式(18)),結合正弦函數,構建出新的一維混沌映射,更新后的函數如式(19)所示

Zk+1=μ×Zk(1-Zk)

(18)

Zk+1=μ×sin(πZk)(1-Zk)

(19)

式中,k表示的是迭代的次數,μ的值設為4,Z是[0,1]的隨機數。

將初始化位置式(5),更新為式(20):

(20)

在優化領域,混沌映射可以用于替代偽隨機數生成器,生成0到1之間的混沌數。經過實驗證明,利用混沌序列進行種群初始化、選擇、交叉和變異等操作會影響算法的整個過程,而且能取得比偽隨機數更好的效果。

5.2 引領蜂搜索方程的優化

ABC性能主要取決于搜索方程和個體選擇策略,基本ABC的搜索方程包含隨機個體信息較強,比較其它的算法,雖然在局部最優、收斂速度等方面存在缺點,但同時存在著不俗的全局搜索能力。

在ABC算法的引領蜂階段,每個個體在自己的食物源位置周圍尋找更好的個體。為了加快收斂速度,將每個個體鄰域內的最優個體作為精英解,引導種群向精英解逼近。

差分進化算法是一種在遺傳算法等多種進化算法的思想基礎上提出的,相比于其它進化算法,有著更加優秀的逼近效果,常常被用來求解多維空間整體的最優解。差分進化算法的大致流程為,在種群初始化之后,再經過變異、交叉、選擇三個操作。其中變異操作如式(21):

Xi=Xr1+F(Xr2-Xr3)

(21)

其思路為首先以一組隨機的種群初始化為起點,在初始化的種群里兩個隨機的目標向量做差生成差分向量,之后將得到的值與權值結合并與另外一個全新的目標向量相加,完成變異的過程;其次將相加之后的變異向量與確定的父代目標向量進行交叉得到實驗向量,完成交叉的過程;最后比較兩代之間的適應度值,若子代較優則進行再一次的迭代,否則父代將被留存下。循環此過程,不斷地進行迭代,每次都保留適應度值較優的目標,不斷地向最優值收斂。

為提高人工蜂群算法的搜索性能,論文根據差分進化的方法結合正弦映射將式(21)進行改進,如式(22)所示:

Xij=Xbest+sin(πFij)(Xr1-Xr2+Xr3-Xr4)

(22)

式中,r1,r2,r3互為隨機數字,且r1,r2,r3∈(1,N),r1≠r2≠r3,i∈[1,N],d∈[1,D]。Xbest是當前種群中具有最佳適應度的最佳解,Fij是區間(0,1]上隨機分布的數字。

本文改進后的算法的具體流程圖如圖1所示。

圖1 本文算法流程圖

6 實驗結果與分析

仿真是分別采取標準ABC與Otsu結合算法、文獻[5]算法和本文算法對圖像測試,圖片取自于室外與室內的自攝照片,為了對比不同算法的快速性,因此,在保證能搜索到最優閾值的前提下盡可能減少算法的迭代次數,從而讓算法的運行時間降到最低。迭代次數與函數值的仿真結果如圖2所示。

圖2 迭代次數與函數值的收斂曲線圖

圖2中分析可以看出,本文算法在迭代次數到達10次左右時,函數值已保持基本不變,其數值穩定在124左右,在10次之后,函數值保持穩定,最終確定收斂閾值。

標準ABC算法,其迭代次數達到27次附近,才基本保持不變,27次之后保持穩定。對兩個不同算法形成的曲線進行分析,本文算法與未改進之前的算法相比,大幅縮減了迭代總次數,陷入局部最優的次數也有明顯的改進。

實驗選取的室外路障照片和室內滅火器照片在不同算法下的對比結果如圖3、圖4所示。

圖3 路障照片實驗結果對比

圖4 滅火器照片實驗結果對比

分別對比了不同算法的運行時間,迭代次數以及求得最優解次數和PSNR(Peak Signal to Noise Ratio)指標進行比較,因為平時最常見并且使用最普遍的一種圖像分割指標就是PSNR,它是基于對應像素點間的誤差,即基于誤差敏感的圖像質量評價,計算方法如式(23)、(24)

(23)

(24)

實驗結果如表1所示。

表1 算法PSNR對比

本文算法是在Otsu算法和標準人工蜂群的基礎上優化的。為了定量地評價各優化算法在圖像分割精度方面的性能,分析表1,標準ABC+Otsu算法、文獻[5]算法和本文算法分割室外路障照片的PSNR分別為8.5412、8.6547和8.8793,室內滅火器的PSNR分別為9.4436、9.5664和9.8058。分析PSNR,本文算法PSNR數值分別高于其它兩種算法約3.9%和2.5%,說明分割圖像的失真程度更低,更接近于原圖像,算法的分割精度更高,取得的分割效果更好。

通過對表2的各項指標綜合分析可以看出,標準ABC+Otsu算法、文獻[5]算法和本文算法分割室外路障照片的運算時間分別為298,286和267ms,迭代次數分別為27、18和9次,室內滅火器的運算時間分別為203,187和155ms,迭代次數分別為26,13和8次;結果表明,在算法迭代次數,程序運行時間這兩個方面本文算法具有顯著的優勢,而且從分割出圖像可以看出,本文算法在噪聲去除和目標識別方面突出的優勢,如圖3室外路障照片對比可以看出對地板上的噪聲有明顯的去除效果,路障的邊緣輪廓也得到了更好的效果、圖4室內滅火器照片明顯的去除了地磚之間的縫隙,將照片內的主體更在清晰地突顯出來。綜合來看,本文算法多項指標對于另外2種算法有很大的提升,對圖像分割有很大的幫助。

表2 圖像分割算法對比

7 結論

1)本文提出采用HSV顏色空間,克服了RGB顏色空間不能準確的使目標與背景產生明顯對比的缺點。利用HSV色相值的特點,成功實現了對目標圖像的高準度分割。

2)在其它兩種算法的實驗結果的對比中,本文算法的大幅縮減了迭代次數和運行時間,并具有更好的降噪效果,能夠更明顯的突出目標圖像,得到了更為理想的分割圖像。

3)根據PSNR指標,本文算法相較于另外兩種算法都有較大提升,提高約為3.9%和2.5%,大幅降低了目標圖像分割后的失真度,提高了圖像的分割質量。