基于改進人工蜂群算法的多閾值圖像分割

李鑫鑫,劉群鋒

(東莞理工學院 計算機學院,廣東 東莞 523808)

0 引 言

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

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

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

1 閾值分割方法

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

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

(1)

(2)

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

(3)

第Ci類的平均灰度值為:

(4)

第Ci類的方差為:

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

(5)

被分割后圖像的類間方差為:

(6)

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

(7)

2 基于改進人工蜂群算法的多閾值圖像分割

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

2.1 人工蜂群算法

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

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

(8)

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

(9)

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

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

2.2 DIRECT算法

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

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

(10)

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

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

DIRECT算法的步驟如下:

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

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

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

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

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

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

圖1 DIRECT算法的迭代過程

2.3 基于改進人工蜂群的多閾值圖像分割方法

2.3.1 改進的人工蜂群算法

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

第一步:初始化種群;

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

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

第四步:選擇POH,并對其進行采樣和分割;

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

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

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

2.3.2 基于改進的人工蜂群的多閾值圖像分割方法

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

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

3 實驗結(jié)果與分析

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

3.1 實驗設(shè)置

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

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

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

3.2 圖像分割質(zhì)量評價指標

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

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

(11)

(12)

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

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

(13)

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

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

(14)

(15)

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

(16)

(17)

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

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

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

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

表2 實驗結(jié)果比較

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

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

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

4 結(jié)束語

首先對閾值分割的國內(nèi)外研究進行了一個梳理,并在前人的基礎(chǔ)上,提出了一種基于IABC的多閾值彩色圖像分割方法,并簡要證明了IABC算法的全局收斂性。首先,將DIRECT算法的分割過程與ABC算法聯(lián)系起來,使得DIRECT算法能夠為人工蜂群算法提供足夠好的初始種群,再將OTSU作為目標函數(shù),以提高圖像被分割后的質(zhì)量。確定了圖像分割的閾值后,對分割后的圖像與原始圖像使用了三個評價指標,即PSNR、SSIM和FSIM,對結(jié)果進行分析,結(jié)果證明了該算法的優(yōu)越性。