基于改進(jìn)人工蜂群算法的多閾值圖像分割

李鑫鑫,劉群鋒

(東莞理工學(xué)院 計(jì)算機(jī)學(xué)院,廣東 東莞 523808)

0 引 言

圖像的分割技術(shù)在圖像處理方面起著至關(guān)重要的作用,是圖像分析和識(shí)別的首要任務(wù)[1]。圖像分割指的是將目標(biāo)圖像處理成多個(gè)具有獨(dú)特性質(zhì)的區(qū)域并提取出對(duì)使用者有用的或者感興趣的部分的技術(shù)[2]。圖像的閾值分割是根據(jù)圖像的局部或者全局信息來(lái)確定分割閾值,包括單閾值分割和多閾值分割,在實(shí)際的生活中,多閾值的分割應(yīng)用更為廣泛[3]。圖像的多閾值選取方法包括最大類(lèi)間方差[4]、最小交叉熵[5]和Tsallis熵[6]等。

智能優(yōu)化算法為圖像多閾值分割技術(shù)提供了一種十分有效的方式,愈來(lái)愈多的研究者將智能優(yōu)化算法與閾值選取方法相結(jié)合來(lái)得到質(zhì)量較好的分割圖像。吳祿慎等人[7]將教與學(xué)搜索策略和模擬退火機(jī)制引入布谷鳥(niǎo)算法,提出了基于改進(jìn)布谷鳥(niǎo)算法的多閾值灰色圖像的分割。高揚(yáng)等人[8]分析并研究了基于改進(jìn)的人工蜂群算法(Artificial Bee Colony Algorithm,ABC)的閾值分割方法,將其應(yīng)用在了圖像分割問(wèn)題上,實(shí)驗(yàn)結(jié)果表明改進(jìn)的人工蜂群算法在高維分割圖像問(wèn)題上有很好的性能和穩(wěn)定性。徐朗等人[9]將蜻蜓算法與差分進(jìn)化算法結(jié)合,提出了一種基于改進(jìn)的蜻蜓算法(Improved Dragonfly Algorithm,IDA)的彩色圖像多閾值分割技術(shù),實(shí)驗(yàn)證明,與其他算法相比,該算法得到的分割閾值最優(yōu),且分割出的圖像質(zhì)量較好。S. Pare等人[10]提出基于蝙蝠算法的多閾值分割技術(shù)用于分割彩色的衛(wèi)星圖像。Mahajan等人[11]提出了基于樽海鞘群算法(Salp Swarm Algorithm)的多閾值分割技術(shù),并將第二類(lèi)模糊熵作為適應(yīng)度函數(shù)進(jìn)行計(jì)算得到最佳閾值。

上面提到的算法都能夠有效地得到圖像分割的閾值,但是大部分都不能保證圖像分割后的質(zhì)量。提高圖像分割后的質(zhì)量是一個(gè)非常重要的問(wèn)題,因此,該文提出了一種基于改進(jìn)的ABC算法(Improved ABC,IABC)的多閾值圖像分割方法。ABC算法具有魯棒性強(qiáng)、精度高等優(yōu)點(diǎn),但其自身具有過(guò)早收斂、局部搜索能力差的缺點(diǎn)[12]。為了能夠彌補(bǔ)ABC算法的缺陷,該文利用DIRECT算法全局收斂并能夠快速定位到最優(yōu)值區(qū)域的特點(diǎn),為ABC算法選擇良好的種群,種群經(jīng)過(guò)數(shù)代演化后得到的最優(yōu)解會(huì)返回到DIRECT算法的分割區(qū)域中并指導(dǎo)DIRECT的分割,再次為ABC算法選取更好的種群,循環(huán)這個(gè)過(guò)程直到滿(mǎn)足算法的停止條件。將IABC算法得到的圖像分割結(jié)果與多種算法得到的結(jié)果進(jìn)行比較,實(shí)驗(yàn)數(shù)據(jù)表明該算法得到的分割后的圖像質(zhì)量更好。

1 閾值分割方法

本節(jié)主要介紹了閾值的分割方法——最大類(lèi)間方差。

最大類(lèi)間方差是一種無(wú)參數(shù)、無(wú)監(jiān)督的自動(dòng)閾值選擇的方法[4],也被稱(chēng)為OTSU方法。假設(shè)I是一幅擁有M×N個(gè)像素的圖像,[0,1,…,L-1]表示圖像I有L個(gè)灰度級(jí)別,[th1,th2,…,thk-1]表示由算法找到的k-1個(gè)閾值。ni表示第i個(gè)灰度級(jí)在圖像中的個(gè)數(shù),那么圖像I灰度級(jí)的概率分布是:

(1)

(2)

k-1個(gè)閾值將圖像分為了C1,C2,…,Ck類(lèi),則第Ci類(lèi)出現(xiàn)的概率為:

(3)

第Ci類(lèi)的平均灰度值為:

(4)

第Ci類(lèi)的方差為:

σi=ωi(μ0-μ)2,i=1,2,…,k

(5)

被分割后圖像的類(lèi)間方差為:

(6)

由以上分析可得到Otsu方法的目標(biāo)函數(shù)為:

(7)

2 基于改進(jìn)人工蜂群算法的多閾值圖像分割

本節(jié)在分析了ABC算法以及DIRECT算法后,提出了IABC算法并簡(jiǎn)要論證了IABC算法的全局收斂性,隨后提出了基于IABC算法的閾值分割技術(shù)。

2.1 人工蜂群算法

ABC算法[13]是模仿蜂群采蜜行為的一種智能優(yōu)化算法。人工蜂群算法包含三種蜜蜂,(a)雇傭蜂:去食物源采蜜;(b)觀(guān)察蜂:根據(jù)雇傭蜂采回花蜜的數(shù)量(目標(biāo)函數(shù)的適應(yīng)值)選擇食物源;(c)偵察蜂:當(dāng)花蜜的數(shù)量不再上升時(shí),偵察蜂會(huì)重新隨機(jī)選擇一個(gè)食物源給雇傭蜂。

ABC算法主要分為四個(gè)階段。第一個(gè)階段(初始化階段):初始化種群數(shù)量SN,雇傭蜂種群的初始位置{xi},i∈[1,2,…,SN/2];第二階段(雇傭蜂階段):雇傭蜂將返回蜂巢,與觀(guān)察蜂分享信息后返回到食物源位置,根據(jù)表達(dá)式(8)尋找新的食物源位置。

(8)

其中,xij表示食物源xi在第j維度的位置,k∈[1,2,…,SN]和rij∈[-1,1]是隨機(jī)數(shù)。第三階段(觀(guān)察蜂階段):觀(guān)察蜂會(huì)依概率:

(9)

選擇需要觀(guān)察的雇傭蜂,其中f(xi)表示食物源xi的函數(shù)值,即花蜜的數(shù)量,觀(guān)察蜂會(huì)根據(jù)式選擇食物源的位置,使用貪婪策略選擇是否更新食物源位置;第四階段(偵察蜂階段):當(dāng)雇傭蜂帶回花蜜的數(shù)量處于停滯狀態(tài)時(shí),偵察蜂會(huì)隨機(jī)指定一個(gè)新的食物源給雇傭蜂。

其中,食物源表示目標(biāo)函數(shù)可行解,對(duì)應(yīng)的花蜜數(shù)量表示目標(biāo)函數(shù)的適應(yīng)值,通常雇傭蜂的數(shù)量與觀(guān)察蜂的數(shù)量相同,為種群數(shù)量的一半。

2.2 DIRECT算法

DIRECT算法[14]是一種確定性算法,在初始階段能夠很快找到目標(biāo)函數(shù)最優(yōu)解所在的區(qū)域[15]。然而,劉[16]發(fā)現(xiàn),將DIRECT算法運(yùn)用在目標(biāo)函數(shù)線(xiàn)性校正前后,性能有非常大的不同,于是提出了具有魯棒性的DIRECT算法。該文將使用劉提出的DIRECT算法。

DIRECT算法主要包含三個(gè)主要操作,選擇潛在最優(yōu)超矩形(Potential Optimal Hyperrectangle,POH),在POH中抽去樣本點(diǎn)和分割POH。抽樣操作:假設(shè)POH的最長(zhǎng)邊為δ,表示最長(zhǎng)邊的維度的集合,c為POH的中心,在的每一個(gè)維度上進(jìn)行抽樣,其中ei是一個(gè)第i個(gè)元素為1的單位向量;分割操作:優(yōu)先選擇最小值所在的維度被分割成三等分;POH的區(qū)域選擇:假設(shè)分割后所得到的超矩形的集合為,ci和σi表示第i個(gè)超矩形的中心和大小,fmin表示當(dāng)前函數(shù)的最小值,如果存在一個(gè)常數(shù)γ>0滿(mǎn)足:

(10)

則矩形j是一個(gè)POH,其中ε>0是給定的常數(shù)。

圖1表示的是DIRECT算法的迭代過(guò)程,在第一次迭代時(shí),選擇整個(gè)搜索空間作為POH,并對(duì)其最長(zhǎng)邊所在的維度進(jìn)行抽樣,對(duì)最優(yōu)解所在的維度進(jìn)行三等分。第二次迭代與第三次迭代重復(fù)選擇、抽樣、分割三個(gè)步驟直到停止條件被滿(mǎn)足。

DIRECT算法的步驟如下:

第一步:將搜索空間初始化為一個(gè)單位超矩形,記作c1為這個(gè)超矩形的中心,fmin=f(c1);

第二步:識(shí)別潛在最優(yōu)矩形S;

第三步:選擇矩形j∈S;

第四步:對(duì)矩形j進(jìn)行采樣,確定分割超矩形的方式,并更新fmin;

第五步:S=S-{j},如果S≠?,返回第三步;

第六步:滿(mǎn)足循環(huán)條件則返回第二步,否則停止。

圖1 DIRECT算法的迭代過(guò)程

2.3 基于改進(jìn)人工蜂群的多閾值圖像分割方法

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

IABC算法首先執(zhí)行DIRECT算法,根據(jù)2.2節(jié)的分析,DIRECT算法不僅能夠很快地找到最優(yōu)解所在的區(qū)域,而且每次迭代之后至少能夠生成5個(gè)可行解,足以形成一個(gè)種群并進(jìn)行種群的演化,也就是說(shuō),DIRECT算法可以為ABC算法提供一個(gè)非常好的種群。ABC算法在經(jīng)過(guò)一定次數(shù)的迭代后,將生成的最優(yōu)解返回到DIRECT算法的分割區(qū)域中并將區(qū)域進(jìn)行分割,不斷進(jìn)行種群選擇和種群進(jìn)化直到滿(mǎn)足停止條件。其中ABC算法得到的最優(yōu)解的加入破壞了DIRECT算法三等分分割原則,這時(shí)應(yīng)遵循采樣點(diǎn)在超矩形中心這一原則對(duì)分割區(qū)域進(jìn)行分割。IABC算法的步驟如下:

第一步:初始化種群;

第二步:若迭代次數(shù)大于1,執(zhí)行第三步,否則執(zhí)行第四步;

第三步:從現(xiàn)有的解中采用完全隨機(jī)選擇方法選擇一組種群作為初始種群,執(zhí)行ABC算法,得到最優(yōu)解并返回到分割區(qū)域中,對(duì)該區(qū)域進(jìn)行分割;

第四步:選擇POH,并對(duì)其進(jìn)行采樣和分割;

第五步:若滿(mǎn)足停止條件則停止,否則繼續(xù)執(zhí)行第二步。

Johns等人[14]在論文中論述了DIRECT算法的收斂性——如果目標(biāo)函數(shù)是連續(xù)的,則DIRECT算法保證可以找到函數(shù)的全局最優(yōu)值。通過(guò)論文[14]中的論述過(guò)程可知,根據(jù)POH的區(qū)域選擇的規(guī)則即表達(dá)式(10)可推出在每一次迭代的過(guò)程中至少有一個(gè)最大的超矩形會(huì)成為POH,因此每一個(gè)超矩形在有限次迭代過(guò)程中都會(huì)被分割。由于每一個(gè)超矩形都會(huì)在有限迭代次數(shù)內(nèi)被分割,在有限次迭代過(guò)程中,每一個(gè)超矩形的大小都會(huì)小于一個(gè)任意的σ(σ>0),這意味著,超矩形采樣的點(diǎn)都會(huì)落在某個(gè)采樣點(diǎn)的σ鄰域內(nèi)。因此,DIRECT算法是全局收斂的。

根據(jù)改進(jìn)的ABC算法的過(guò)程可知,在DIRECT的分割區(qū)域加入了由種群進(jìn)化得到的一個(gè)最優(yōu)解,最優(yōu)解的加入意味著使得DIRECT算法能夠提前分割這些區(qū)域,對(duì)DIRECT算法中POH的選擇以及采樣都不造成任何影響,因此IABC算法也是一種全局收斂的算法。

2.3.2 基于改進(jìn)的人工蜂群的多閾值圖像分割方法

IABC算法將OTSU方法作為目標(biāo)函數(shù),即表達(dá)式(7),得到最優(yōu)閾值對(duì)圖像進(jìn)行分割。圖2是基于改進(jìn)的ABC算法的多閾值分割圖像方法的流程。

圖2 多閾值圖像分割方法的流程

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

本節(jié)主要圍繞改進(jìn)的人工蜂群算法在圖像分割方面的實(shí)驗(yàn)展開(kāi)論述,詳細(xì)說(shuō)明了實(shí)驗(yàn)的設(shè)置以及評(píng)價(jià)指標(biāo)和實(shí)驗(yàn)結(jié)果的分析等。為了說(shuō)明算法的優(yōu)劣,在保證圖像大小、種群大小、函數(shù)評(píng)估次數(shù)等都相同的前提下,將本實(shí)驗(yàn)得到的結(jié)果與ABC算法[13]、IDA算法[9]和AHHO算法[17]得到的結(jié)果相比較。

3.1 實(shí)驗(yàn)設(shè)置

在本節(jié)中,將表達(dá)式(7)作為目標(biāo)函數(shù),但根據(jù)問(wèn)題的屬性,該目標(biāo)函數(shù)是離散問(wèn)題,在實(shí)驗(yàn)中,首先將目標(biāo)函數(shù)的變量做連續(xù)化處理,即使得閾值的取值范圍為[0,255],且目標(biāo)函數(shù)為fOTSU(xi)=fOTSU(?xi」)。隨后使用2.3節(jié)提出的彩色圖像多閾值分割方法分割四幅大小均為481×321×3的RGB圖片,如圖3所示(依次為horse.jpg、lake.jpg、pig.jpg、stone.jpg,圖片來(lái)自于伯克利分割數(shù)據(jù)集[18])。本實(shí)驗(yàn)在“Linux 3.10.0”系統(tǒng)上的“Matlab 2020b”軟件上進(jìn)行。由于隨機(jī)性的存在,對(duì)每幅圖像,對(duì)OTSU方法運(yùn)行30次再求平均值。實(shí)驗(yàn)的參數(shù)如表1所示。

圖3 RGB圖片 表1 參數(shù)設(shè)置

參數(shù)值函數(shù)評(píng)估次數(shù)15 000種群大小30種群迭代次數(shù)50觀(guān)察蜂數(shù)量15雇傭蜂數(shù)量15停滯界限100

3.2 圖像分割質(zhì)量評(píng)價(jià)指標(biāo)

為了評(píng)估圖像分割算法的優(yōu)劣,文中采取了三個(gè)圖像質(zhì)量評(píng)價(jià)指標(biāo),即峰值信噪比(Peak Signal-to-Noise Ratio,PSNR)、結(jié)構(gòu)相似性(Structural Similarity Index,SSIM)和特征相似性(Feature Similarity index,FSIM)[19]。

PSNR用于驗(yàn)證原始圖像I與分割后的圖像K之間的相似性,其表達(dá)式為:

(11)

(12)

其中,MSE是原始圖像I與處理后的圖像K之間的均方誤差(Mean Square Error),Iij和Kij表示對(duì)應(yīng)圖像的第i行第j列的像素值。

SSIM是用于比較原始圖像與分割后圖像之間結(jié)構(gòu)的相似性,也就是圖像中相鄰像素之間的關(guān)系,其表達(dá)式為:

(13)

其中,μI和μK分別是原始圖像與分割后圖像像素的均值,σI和σK對(duì)應(yīng)的是圖像的標(biāo)準(zhǔn)差,σIK表示的是原始圖像I與分割后圖像K像素之間的協(xié)方差,λ1和λ2是常數(shù)。

FSIM用于比較圖像之間的特征相似性,即相位一致性(Phase Congruency,PC)和梯度的特征(Gradient Magnitude,G)[19],表達(dá)式如下:

(14)

(15)

SL(x)=SPC(i)·SG(i)

(16)

(17)

其中,PCm(i)=max{PCI(i),PCK(i)}。

這三種指標(biāo)有一個(gè)共同點(diǎn),即求得的值越大,表示由分割得到的圖像質(zhì)量越高。

3.3 實(shí)驗(yàn)數(shù)值結(jié)果與分析

表2展示了文中算法與ABC算法、IDA算法以及AHHO (Altruistic Harris Hawks’ Optimization)算法得到的實(shí)驗(yàn)數(shù)據(jù)結(jié)果,比較數(shù)據(jù)包括算法運(yùn)行30次之后得到的平均PSNR、平均SSIM和平均FSIM。黑色加粗的數(shù)值表示文中算法與其他三種算法相比較得到的較好的值。

表2 實(shí)驗(yàn)結(jié)果比較

從表2中可以看出,以O(shè)TSU為目標(biāo)函數(shù)時(shí),使用文中算法得到的圖像閾值分割結(jié)果要遠(yuǎn)遠(yuǎn)好于其他三種算法得到的結(jié)果;當(dāng)以PSNR為評(píng)價(jià)指標(biāo)時(shí),文中算法要遠(yuǎn)好于其他三個(gè)算法,即使用IABC對(duì)圖像進(jìn)行分割后的質(zhì)量與原圖像相似性高;當(dāng)以SSIM作為圖像的質(zhì)量評(píng)價(jià)標(biāo)準(zhǔn)時(shí),從實(shí)驗(yàn)的比較結(jié)果看,文中算法在lake.jpg圖像上表現(xiàn)最差,在pig.jpg圖像上表現(xiàn)最好;當(dāng)以FSIM作為圖像的質(zhì)量評(píng)價(jià)標(biāo)準(zhǔn)時(shí),在大多數(shù)情況下,IABC算法分割得到的圖片與原圖片的特征最相似。

圖4是圖像的分割結(jié)果,由于篇幅原因,僅給出基于改進(jìn)的人工蜂群的多閾值圖像方法的實(shí)驗(yàn)結(jié)果。結(jié)合表2和圖4可以發(fā)現(xiàn),當(dāng)k值較低時(shí),得到的分割圖像細(xì)節(jié)較少,圖像的質(zhì)量也相對(duì)較差,當(dāng)k值較大時(shí),圖像細(xì)節(jié)越多,圖像的質(zhì)量也越好,越接近未被分割的圖像。

圖4 基于改進(jìn)的人工蜂群的多閾值圖像分割方法的實(shí)驗(yàn)可視化結(jié)果 (從左向右分別是k-1=4,6,8,10所對(duì)應(yīng)的結(jié)果)

4 結(jié)束語(yǔ)

首先對(duì)閾值分割的國(guó)內(nèi)外研究進(jìn)行了一個(gè)梳理,并在前人的基礎(chǔ)上,提出了一種基于IABC的多閾值彩色圖像分割方法,并簡(jiǎn)要證明了IABC算法的全局收斂性。首先,將DIRECT算法的分割過(guò)程與ABC算法聯(lián)系起來(lái),使得DIRECT算法能夠?yàn)槿斯し淙核惴ㄌ峁┳銐蚝玫某跏挤N群,再將OTSU作為目標(biāo)函數(shù),以提高圖像被分割后的質(zhì)量。確定了圖像分割的閾值后,對(duì)分割后的圖像與原始圖像使用了三個(gè)評(píng)價(jià)指標(biāo),即PSNR、SSIM和FSIM,對(duì)結(jié)果進(jìn)行分析,結(jié)果證明了該算法的優(yōu)越性。