融合改進(jìn)人工蜂群與Otsu的圖像分割算法

徐 武,王欣達(dá),高 寒,秦浩然

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

1 引言

圖像分割就是把圖像分成若干個(gè)特定的、具有獨(dú)特性質(zhì)的區(qū)域并提出感興趣目標(biāo)的過程,是在整個(gè)圖像處理流程中一個(gè)至關(guān)重要的環(huán)節(jié),隨著圖像分割技術(shù)的發(fā)展,它在影像醫(yī)學(xué)、無人駕駛、增強(qiáng)現(xiàn)實(shí)等方面都有著不俗的作用。人工蜂群算法是一種基于種群的元啟發(fā)式智能算法,人工蜂群性能主要取決于搜索方程和個(gè)體選擇策略,基本人工蜂群的搜索方程包含隨機(jī)個(gè)體信息較強(qiáng),相較于一般群體智能優(yōu)化算法。

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

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

2 HSV顏色空間的轉(zhuǎn)換

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

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

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

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

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

(1)

設(shè)(r、g、b)為R空間的1個(gè)點(diǎn),歸一化后,其為[0,1]之間的實(shí)數(shù),減少計(jì)算的復(fù)雜度。

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

(2)

(3)

V=max

(4)

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

H分量值規(guī)范化在0～360之間,S分量規(guī)范化在0～255之間,但在計(jì)算機(jī)數(shù)值計(jì)算時(shí),會(huì)將H、S歸一化為[0,1]之間的實(shí)數(shù)。

3 人工蜂群算法

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

ABC算法的具體步驟如下:

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

(5)

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

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

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

(6)

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

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

(7)

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

(8)

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

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

(9)

式中,trial為目前已經(jīng)迭代的次數(shù),L為迭代次數(shù)的上限。

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

4 二維Otsu算法

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

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

(10)

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

(11)

(12)

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

背景A和目標(biāo)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)

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

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

(17)

5 改進(jìn)的人工蜂群算法

為了提高算法的搜索能力,同時(shí)提高算法開采能力和收斂速度,本文在標(biāo)準(zhǔn)蜂群算法的基礎(chǔ)上,提出了一種改進(jìn)的人工蜂群算法。算法主要是對種群初始化和引領(lǐng)蜂搜索方程進(jìn)行改進(jìn)。

5.1 種群初始化的改進(jìn)

種群初始化是進(jìn)化算法的一個(gè)關(guān)鍵點(diǎn),因?yàn)樗绊懼惴ǖ氖諗克俣群妥罱K解的質(zhì)量。為了選擇更好的初始種群,論文提出一種新的初始化方法,利用具有遍歷性、隨機(jī)性的混沌系統(tǒng)和不規(guī)則性的對立的學(xué)習(xí)方法來生成初始種群。

在Logistic映射式的基礎(chǔ)上(式(18)),結(jié)合正弦函數(shù),構(gòu)建出新的一維混沌映射,更新后的函數(shù)如式(19)所示

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

(18)

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

(19)

式中,k表示的是迭代的次數(shù),μ的值設(shè)為4,Z是[0,1]的隨機(jī)數(shù)。

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

(20)

在優(yōu)化領(lǐng)域,混沌映射可以用于替代偽隨機(jī)數(shù)生成器,生成0到1之間的混沌數(shù)。經(jīng)過實(shí)驗(yàn)證明,利用混沌序列進(jìn)行種群初始化、選擇、交叉和變異等操作會(huì)影響算法的整個(gè)過程,而且能取得比偽隨機(jī)數(shù)更好的效果。

5.2 引領(lǐng)蜂搜索方程的優(yōu)化

ABC性能主要取決于搜索方程和個(gè)體選擇策略,基本ABC的搜索方程包含隨機(jī)個(gè)體信息較強(qiáng),比較其它的算法,雖然在局部最優(yōu)、收斂速度等方面存在缺點(diǎn),但同時(shí)存在著不俗的全局搜索能力。

在ABC算法的引領(lǐng)蜂階段,每個(gè)個(gè)體在自己的食物源位置周圍尋找更好的個(gè)體。為了加快收斂速度,將每個(gè)個(gè)體鄰域內(nèi)的最優(yōu)個(gè)體作為精英解,引導(dǎo)種群向精英解逼近。

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

Xi=Xr1+F(Xr2-Xr3)

(21)

其思路為首先以一組隨機(jī)的種群初始化為起點(diǎn),在初始化的種群里兩個(gè)隨機(jī)的目標(biāo)向量做差生成差分向量,之后將得到的值與權(quán)值結(jié)合并與另外一個(gè)全新的目標(biāo)向量相加,完成變異的過程;其次將相加之后的變異向量與確定的父代目標(biāo)向量進(jìn)行交叉得到實(shí)驗(yàn)向量,完成交叉的過程;最后比較兩代之間的適應(yīng)度值,若子代較優(yōu)則進(jìn)行再一次的迭代,否則父代將被留存下。循環(huán)此過程,不斷地進(jìn)行迭代,每次都保留適應(yīng)度值較優(yōu)的目標(biāo),不斷地向最優(yōu)值收斂。

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

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

(22)

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

本文改進(jìn)后的算法的具體流程圖如圖1所示。

圖1 本文算法流程圖

6 實(shí)驗(yàn)結(jié)果與分析

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

圖2 迭代次數(shù)與函數(shù)值的收斂曲線圖

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

標(biāo)準(zhǔn)ABC算法,其迭代次數(shù)達(dá)到27次附近,才基本保持不變,27次之后保持穩(wěn)定。對兩個(gè)不同算法形成的曲線進(jìn)行分析,本文算法與未改進(jìn)之前的算法相比,大幅縮減了迭代總次數(shù),陷入局部最優(yōu)的次數(shù)也有明顯的改進(jìn)。

實(shí)驗(yàn)選取的室外路障照片和室內(nèi)滅火器照片在不同算法下的對比結(jié)果如圖3、圖4所示。

圖3 路障照片實(shí)驗(yàn)結(jié)果對比

圖4 滅火器照片實(shí)驗(yàn)結(jié)果對比

分別對比了不同算法的運(yùn)行時(shí)間,迭代次數(shù)以及求得最優(yōu)解次數(shù)和PSNR(Peak Signal to Noise Ratio)指標(biāo)進(jìn)行比較,因?yàn)槠綍r(shí)最常見并且使用最普遍的一種圖像分割指標(biāo)就是PSNR,它是基于對應(yīng)像素點(diǎn)間的誤差,即基于誤差敏感的圖像質(zhì)量評價(jià),計(jì)算方法如式(23)、(24)

(23)

(24)

實(shí)驗(yàn)結(jié)果如表1所示。

表1 算法PSNR對比

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

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

表2 圖像分割算法對比

7 結(jié)論

1)本文提出采用HSV顏色空間,克服了RGB顏色空間不能準(zhǔn)確的使目標(biāo)與背景產(chǎn)生明顯對比的缺點(diǎn)。利用HSV色相值的特點(diǎn),成功實(shí)現(xiàn)了對目標(biāo)圖像的高準(zhǔn)度分割。

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

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