趙 鳳,孔令潤(rùn),馬改妮
(1.西安郵電大學(xué)通信與信息工程學(xué)院,陜西 西安 710121; 2.西安郵電大學(xué)電子信息現(xiàn)場(chǎng)勘驗(yàn)應(yīng)用技術(shù)公安部重點(diǎn)實(shí)驗(yàn)室,陜西 西安 710121)
隨著目標(biāo)識(shí)別、機(jī)器視覺的不斷發(fā)展,圖像分割技術(shù)越來(lái)越受到人們的重視。圖像分割的目的是將一幅圖像劃分為多個(gè)感興趣的區(qū)域,以便后續(xù)對(duì)這些區(qū)域進(jìn)行進(jìn)一步處理。目前常用的分割方法主要包括基于閾值的分割方法[1]、基于區(qū)域的分割方法[2]和基于聚類的分割方法[3]等。在諸多的圖像分割方法中,基于閾值的圖像分割方法因其性能穩(wěn)定、算法簡(jiǎn)單等特點(diǎn),一直是圖像分割領(lǐng)域中的熱門研究方向。其中,最大類間方差法(Otsu)[4]、最大熵法(Kapur)[5]由于其原理簡(jiǎn)單,易于實(shí)現(xiàn),因此是最常見的2種閾值分割算法。但是,上述算法對(duì)于雙峰不明顯的復(fù)雜圖像分割效果不佳;而且在進(jìn)行多閾值圖像分割時(shí),由于計(jì)算量過大,效率太低,往往也不能得到理想的分割結(jié)果。
為了解決上述問題,有學(xué)者將粒子群優(yōu)化PSO(Particle Swarm Optimization)算法[6]和人工蜂群ABC(Artificial Bee Colony)算法[7]等生物啟發(fā)式算法應(yīng)用到閾值圖像分割[8 - 11]中。文獻(xiàn)[8]針對(duì)二維Otsu算法計(jì)算量過大的缺點(diǎn),采用PSO算法尋找最優(yōu)的二維閾值向量,實(shí)驗(yàn)結(jié)果表明,該算法在取得較為理想分割結(jié)果的同時(shí),大大減少了計(jì)算量。文獻(xiàn)[9]提出了一種基于ABC優(yōu)化的閾值圖像分割算法,將最大熵函數(shù)作為需要優(yōu)化的目標(biāo)函數(shù),可以得到良好的分割結(jié)果。需要指出的是,PSO算法和ABC算法在優(yōu)化的后期階段都存在一些問題[12,13],PSO算法易陷入局部最優(yōu),而ABC算法的全局搜索能力雖然強(qiáng),但局部搜索能力較弱,不能達(dá)到一個(gè)很好的平衡。因此,有學(xué)者結(jié)合ABC算法與PSO算法的優(yōu)點(diǎn),提出了ABC算法和PSO算法相結(jié)合的混合優(yōu)化算法[14,15]。文獻(xiàn)[15]在PSO算法中引入人工蜂群搜索算子,利用人工蜂群算子具有較強(qiáng)的全局探索能力的特點(diǎn),對(duì)粒子的歷史最優(yōu)位置進(jìn)行搜索,從而避免陷入局部最優(yōu)。
然而,上述方法都只是單個(gè)閾值準(zhǔn)則下的優(yōu)化問題,無(wú)法滿足用戶多方面的需求,因此多個(gè)閾值準(zhǔn)則下的圖像分割問題越來(lái)越值得研究。近年來(lái),多目標(biāo)優(yōu)化算法被用到閾值圖像分割[16 - 18]中,與其他單目標(biāo)的閾值分割算法相比,多目標(biāo)優(yōu)化算法在多個(gè)閾值準(zhǔn)則之間協(xié)調(diào)權(quán)衡,盡量使得各個(gè)閾值準(zhǔn)則都達(dá)到最優(yōu)。在文獻(xiàn)[17]中,Nakib等人提出了利用第2代非支配排序遺傳算法NSGA-Ⅱ(Non-dominated Sorting Genetic Algorithms-Ⅱ)[18]同時(shí)優(yōu)化改進(jìn)的類間方差、香農(nóng)熵和2-D熵函數(shù)這3個(gè)目標(biāo)函數(shù)。
本文針對(duì)多閾值分割問題,利用PSO算法開采能力強(qiáng)而ABC算法注重探索能力的特性,提出了基于多目標(biāo)粒子群和人工蜂群混合優(yōu)化MPS-ABC(Multi-objective Particle Swarm and Artificial Bee Colony hybrid optimization)的閾值圖像分割算法。該算法采用改進(jìn)的最大類間方差準(zhǔn)則和最大熵準(zhǔn)則作為多目標(biāo)進(jìn)化的2個(gè)適應(yīng)度函數(shù),提出了一種粒子群和蜂群的混合進(jìn)化策略,并對(duì)ABC算法的搜索策略進(jìn)行了改進(jìn),在進(jìn)化過程中每隔1代進(jìn)行1次信息的交互,避免由于錯(cuò)誤的信息判斷而陷入局部最優(yōu)的問題,從而能夠更加有效地逼近最優(yōu)閾值。本文將最大類間方差法[4]、最大熵法[5]、基于最大熵的人工蜂群閾值MEABCT(the Maximum Entropy based Artificial Bee Colony Thresholding)圖像分割算法[9]、基于Otsu標(biāo)準(zhǔn)的多級(jí)閾值粒子群優(yōu)化算法[19]PSO-Otsu(Particle Swarm Optimization algorithm for multilevel thresholding by the criteria of Otsu)、多目標(biāo)人工蜂群優(yōu)化MOABC(Multi-objective Optimization method based on the Artificial Bee Colony)算法[20]和基于多目標(biāo)粒子群優(yōu)化MOPSO(Multi-Objective Particle Swarm Optimization)的閾值圖像分割算法[21]作為對(duì)比算法。實(shí)驗(yàn)結(jié)果表明,本文算法對(duì)于目標(biāo)和背景復(fù)雜的多閾值圖像的分割,不但縮短了計(jì)算時(shí)間,而且還能取得較為理想的分割結(jié)果。
PSO算法[6]是模擬鳥群覓食行為的一種優(yōu)化算法。PSO算法首先在搜索空間內(nèi)生成1組均勻分布的粒子xi=(xi,1,xi,2,…,xi,D),i= 1,2,…,N,N表示種群規(guī)模,D表示粒子的維度。每1個(gè)粒子會(huì)有1個(gè)速度來(lái)決定飛行的距離和方向,速度的更新是由當(dāng)前粒子經(jīng)歷過的最好位置以及所有粒子在每次迭代中得到的最好位置決定的。粒子的速度更新如式(1)所示:
(1)
對(duì)于每1個(gè)粒子xi,更新方式如式(2)所示:
xi,j(t+1)=xi,j(t)+vi,j(t)
(2)
(3)
其中,f是目標(biāo)函數(shù)。
全局最優(yōu)解gbest由式(4)計(jì)算得出:
(4)
在ABC算法[7]中,蜂群由雇傭蜂、跟隨蜂和偵察蜂3個(gè)部分組成,整個(gè)蜂群的目標(biāo)是尋找花蜜量最大的蜜源,即優(yōu)化問題中的最優(yōu)解。雇傭蜂的數(shù)量和跟隨蜂的數(shù)量是相等的。雇傭蜂的作用是搜索花蜜源并把蜜源信息傳遞給跟隨蜂;跟隨蜂根據(jù)蜜源的豐富程度采用輪盤賭的方式選擇蜜源進(jìn)行跟隨,并在蜜源周圍進(jìn)行搜索;如果蜜源經(jīng)過多次更新沒有改進(jìn),則放棄該蜜源,雇傭蜂變?yōu)閭刹榉潆S機(jī)搜索新蜜源。在ABC算法中,每個(gè)蜜源代表優(yōu)化問題的1個(gè)可能解,蜜源的花蜜量(解的優(yōu)劣)是通過適應(yīng)度值來(lái)評(píng)定的。雇傭蜂的數(shù)量等于蜜源的數(shù)量。
假設(shè)問題的解空間是D維的,則第i個(gè)蜜源的位置可以表示為1個(gè)D維的向量xi=(xi,1,xi,2,…,xi,D),i= 1,2,…,N,N代表蜜源的數(shù)量。ABC算法各個(gè)階段的細(xì)節(jié)如下所示:
在種群的初始化階段,根據(jù)式(5)來(lái)隨機(jī)產(chǎn)生蜜源的位置:
(5)
在雇傭蜂階段,雇傭蜂會(huì)在蜜源周圍進(jìn)行搜索,并按照式(6)產(chǎn)生新的個(gè)體x′i,每1個(gè)蜜源對(duì)應(yīng)1個(gè)變量trial來(lái)記錄該蜜源連續(xù)未被改善的次數(shù),若某一蜜源的trial值超過限定的循環(huán)次數(shù)l,則對(duì)應(yīng)雇傭蜂轉(zhuǎn)化為偵察蜂隨機(jī)搜索新蜜源。
x′i,j=xi,j+rand()·(xi,j-xk,j)
(6)
其中,j是{1,2,…,D}中隨機(jī)選擇的整數(shù),代表雇傭蜂隨機(jī)地選擇可行解的一維進(jìn)行更新搜索;xk,j表示在蜜源中隨機(jī)地選擇1個(gè)不同于xi,j的蜜源。
在跟隨蜂階段,跟隨蜂會(huì)評(píng)估雇傭蜂帶回的花蜜量的信息,并采用輪盤賭的方法選擇雇傭蜂進(jìn)行跟隨。跟隨蜂選擇雇傭蜂的概率計(jì)算如式(7)所示:
(7)
其中,fit(xi)代表第i個(gè)蜜源的花蜜量。
在偵查蜂階段,如前文所述,若1個(gè)蜜源經(jīng)過l次循環(huán)之后不能被改進(jìn),則該蜜源被放棄,同時(shí),該蜜源處的雇傭蜂成為偵察蜂,偵查蜂會(huì)根據(jù)式(5)產(chǎn)生1個(gè)新的蜜源。
通過分析以上2種算法可以得出:PSO算法更側(cè)重于開采能力,局部搜索能力更強(qiáng),但是容易陷入局部最優(yōu);而ABC算法則更加注重探索能力,全局搜索能力相對(duì)更強(qiáng)。因此,本文結(jié)合PSO算法和ABC算法各自的優(yōu)點(diǎn),提出了一種基于粒子群和蜂群的混合優(yōu)化算法MPS-ABC,并將其用到圖像分割中,以達(dá)到更好的分割效果。
本文所提出的MPS-ABC算法是對(duì)圖像的閾值進(jìn)行編碼,編碼方式采用實(shí)數(shù)制編碼,編碼范圍是[Imin,Imax],其中Imax和Imin分別表示圖像像素的最大值和最小值。本文算法使用式(5)來(lái)生成初始種群,并將生成的種群隨機(jī)等分為種群Q1和種群Q2,使其分別作為PSO算法和ABC算法的初始種群。
適應(yīng)度函數(shù)主要用于評(píng)價(jià)種群中個(gè)體的優(yōu)劣性。本文將改進(jìn)的類間方差函數(shù)和最大熵函數(shù)作為待優(yōu)化的適應(yīng)度函數(shù)。設(shè)1幅圖像總的像素?cái)?shù)目為C,其灰度級(jí)為[0,255],Ci表示像素值為i的像素個(gè)數(shù),則像素值i出現(xiàn)的概率pi由式(8)計(jì)算得出:
(8)
設(shè)圖像的閾值為t1,t2,…,tn,改進(jìn)的最大類間函數(shù)定義如下:
(9)
其中,
最大熵函數(shù)的定義如下:
H(t1,t2,…,tn)=H0+…+Hk+…+Hn
(10)
其中,H0,…,Hk,…,Hn分別計(jì)算如下:
在3.1節(jié)得到2組初始種群,Q1按照PSO算法進(jìn)行尋優(yōu),個(gè)體的更新采用式(2)進(jìn)行;Q2按照ABC算法進(jìn)行尋優(yōu),為了保證算法的探索能力,同時(shí)提高開采能力,在ABC算法中的雇傭蜂階段提出了新的搜索方程[22]:
(M(x)-xk)+A(i)·(xi-xk)
(11)
A(i)=(1+trial(i))-0.2+0.1·rand()
(12)
其中,trial(i)代表第i個(gè)個(gè)體連續(xù)未更新的次數(shù)。
由于新的搜索方程(11)中引入了最優(yōu)解,因此在提高開采能力的同時(shí)也保證了算法的探索能力,能夠讓該算法在全局搜索與局部搜索之間達(dá)到更好的平衡。與此同時(shí),算法在混合優(yōu)化的過程中,每隔1次迭代會(huì)利用1種信息交流機(jī)制進(jìn)行信息的交互,避免錯(cuò)誤的信息判斷而陷入局部最優(yōu)解。種群之間的信息交流機(jī)制如下所示:
(1)在蜂群的進(jìn)化過程中,將粒子群更新后的解作為蜂群的初始種群,并在雇傭蜂階段比較式(11)產(chǎn)生的解yi、原解xi和粒子群中的全局最優(yōu)解gbest的適應(yīng)度值,保留最優(yōu)個(gè)體。經(jīng)過l次循環(huán)之后,若還未找到更優(yōu)解,則放棄原來(lái)的解,并按照式(5)產(chǎn)生1個(gè)新解。
本文采用多目標(biāo)方法進(jìn)行優(yōu)化,每次迭代產(chǎn)生的解都會(huì)根據(jù)擁擠距離進(jìn)行非支配排序,并保留非支配解,因此經(jīng)過上述步驟會(huì)獲得一組非支配解集。但是,在實(shí)際應(yīng)用中,我們往往只需要1個(gè)最優(yōu)解。本文通過計(jì)算每個(gè)非支配解的類間差異和類內(nèi)差異的加權(quán)比值F[23]來(lái)選取種群的最優(yōu)解,并對(duì)其中的類內(nèi)差異進(jìn)行擴(kuò)展,選取使得F取最大值的個(gè)體作為種群最優(yōu)解。加權(quán)比值F的定義如下所示:
(13)
(14)
其中,xij表示第j類中的第i個(gè)像素的灰度值。
Figure 1 Segmentation results on #3096圖1 #3096分割結(jié)果
Figure 2 Segmentation results on #24063圖2 #24063分割結(jié)果
混合優(yōu)化算法的流程如下所示:
步驟1設(shè)置種群的規(guī)模N,最大迭代次數(shù)Tmax,局部循環(huán)次數(shù)l,學(xué)習(xí)因子c1和c2,慣性權(quán)重w。
步驟2由式(5)進(jìn)行種群初始化,并將種群隨機(jī)等分為2個(gè)種群Q1和Q2。
步驟3設(shè)置初始的迭代步數(shù)iter=0。
步驟4種群Q1按照式(11)產(chǎn)生新解,種群Q2按照式(2)產(chǎn)生新解,分別計(jì)算新產(chǎn)生解的適應(yīng)度值。對(duì)所有解進(jìn)行評(píng)估,保留非支配解,實(shí)現(xiàn)對(duì)非支配解集的更新。
步驟52個(gè)種群每隔1代進(jìn)行1次信息的交互。
步驟6更新迭代步數(shù)iter=iter+1,當(dāng)算法迭代達(dá)到Tmax次時(shí)終止,輸出找到的解集,否則轉(zhuǎn)至步驟4。
步驟7從得到的1組非支配解集中,根據(jù)加權(quán)比值F選擇最終解。
為了驗(yàn)證本文算法的性能,采用Otsu算法、Kapur算法、MEABCT算法、PSO-Otsu算法、MOABC算法和MOPSO算法作為比較算法。實(shí)驗(yàn)分為2個(gè)部分:第1部分采用多幅Berkeley圖像進(jìn)行驗(yàn)證,第2部分用核磁共振(MR)圖像進(jìn)行分割實(shí)驗(yàn)。本文所提出的MPS-ABC算法和6種對(duì)比算法的參數(shù)設(shè)置如下:本文算法以及其他6種對(duì)比算法的種群規(guī)模均設(shè)置為30,最大迭代次數(shù)為100;MEABCT算法和MOABC算法的局部循環(huán)次數(shù)設(shè)置為100,PSO-Otsu算法中的c1和c2都取1.8,w0取3,ri(t) 是0~1的隨機(jī)數(shù);MOPSO算法和本文算法的學(xué)習(xí)因子c1=1,c2=2,慣性權(quán)重w=0.5。
Figure 3 Segmentation results on #241004圖3 #241004分割結(jié)果
Figure 4 Segmentation results on #55067圖4 #55067分割結(jié)果
本節(jié)采用多幅Berkeley圖像來(lái)驗(yàn)證算法的分割性能。在Berkeley圖庫(kù)中選擇圖像#3096、#24063、#241004、#55067作為實(shí)驗(yàn)對(duì)比圖。分割結(jié)果如圖1~圖4所示,其中a~i分別展示的是原圖像、標(biāo)準(zhǔn)分割圖、Kapur算法、Otsu算法、MEABCT算法、PSO-Otsu算法、MOABC算法、MOPSO算法和MPS-ABC算法的分割結(jié)果。此外,本文采用圖像分割準(zhǔn)確率來(lái)客觀評(píng)價(jià)算法的分割結(jié)果,相應(yīng)的結(jié)果如表1所示。表2給出的是本文算法和對(duì)比算法在6幅Berkeley圖像上得到的最優(yōu)分割閾值。
由圖1~圖4可以明顯看出,本文算法相對(duì)于其他6種對(duì)比算法能夠取得更好的分割結(jié)果。對(duì)于圖像#3096,可以看出Kapur算法、Otsu算法、MEABCT算法和PSO-Otsu算法都在圖像的左下角存在明顯的錯(cuò)分,本文算法相比于這4種算法在視覺效果方面明顯取得了更好的分割效果。在圖2中,Kapur算法、Otsu算法、MEABCT算法、PSO-Otsu算法和MOABC算法對(duì)于右上角的天空以及門前的柵欄都存在錯(cuò)分;而MOPSO算法雖然能分清門前的柵欄,但對(duì)于右上角的天空那一部分處理不佳;而本文算法借鑒了ABC算法的進(jìn)化策略,并且對(duì)ABC算法的進(jìn)化策略進(jìn)行了改進(jìn),所以相對(duì)于MOPSO算法來(lái)說更容易跳出局部最優(yōu)以找到最優(yōu)閾值,因此對(duì)門前的柵欄和右上角的天空都取得了良好的分割效果。
Table 1 Segmentation accuracy values of all algorithms on Berkeley images表1 所有算法在Berkeley圖像上的分割準(zhǔn)確率
Table 2 The best thresholds of all algorithms on Berkeley images表2 所有算法在Berkeley圖像上的最優(yōu)分割閾值
根據(jù)表1的準(zhǔn)確率對(duì)比也可以明顯看出,本文所提出的MPS-ABC算法相較于其他6種對(duì)比算法,在大多數(shù)圖像上都取得了較高的分割準(zhǔn)確率。例如,對(duì)于圖像#135069,本文算法的分割準(zhǔn)確率可以達(dá)到0.991 6,而Otsu算法和MEABCT算法的分割準(zhǔn)確率分別為0.554 1和0.605 5;對(duì)比多類分割圖像#55067的分割準(zhǔn)確率結(jié)果,本文算法的分割準(zhǔn)確率為0.921 0,相對(duì)于Kapur算法在準(zhǔn)確率方面提高了0.118 4,比PSO-Otsu算法高出0.230 6。
通過比較本文算法與其余6種對(duì)比算法在準(zhǔn)確率以及視覺效果上的差異可知,本文算法的尋優(yōu)能力更強(qiáng),能夠更加有效地逼近最優(yōu)閾值。
為了驗(yàn)證本文算法的有效性,圖5給出了Kapur算法、Otsu算法、MEABCT算法、PSO-Otsu算法、MOABC算法、MOPSO算法和MPS-ABC算法在多幅Berkeley圖像下的平均PR曲線對(duì)比圖。通過圖5可以看出,本文算法性能優(yōu)于其他6種對(duì)比算法。
Figure 5 PR curves comparison of each algorithm圖5 各個(gè)算法的PR曲線對(duì)比
與已有的Otsu算法與Kapur算法相比,本文算法在多閾值情況下不但分割效果有所提升,運(yùn)行時(shí)間也大大降低。圖6給出了本文算法與Otsu算法、Kapur算法、MOPSO算法以及MOABC算法在5幅閾值圖像#55067下的運(yùn)行時(shí)間對(duì)比??梢钥闯?,本文算法相較于Otsu算法和Kapur算法不但分割效果更好,而且運(yùn)行時(shí)間大大降低。而相較于MOPSO算法和MOABC算法,本文算法在運(yùn)行時(shí)間基本相同的情況下,分割效果更好。
Figure 6 Run time comparison of each algorithm圖6 各算法的運(yùn)行時(shí)間對(duì)比
為了進(jìn)一步驗(yàn)證本文算法的性能,本節(jié)選擇來(lái)自互聯(lián)網(wǎng)腦分割庫(kù)IBSR(The Internet Brain Segmentation Repository)的MR圖像進(jìn)行分割實(shí)驗(yàn),并用圖像分割準(zhǔn)確率作為評(píng)價(jià)標(biāo)準(zhǔn)。如圖7~圖9所示為本文算法與其他6種對(duì)比算法在3幅MR圖像上的分割結(jié)果;對(duì)比算法和本文MPS-ABC算法的準(zhǔn)確率如表3所示。
Figure 7 Segmentation results on the slice 12 of image 12-3圖7 圖像12-3切片號(hào)為12的分割結(jié)果圖
Figure 8 Segmentation results on the slice 50 of image 2-4圖8 圖像2-4切片號(hào)為50的分割結(jié)果圖
Figure 9 Segmentation results on the slice 45 of image 100-23圖9 圖像100-23切片號(hào)為45的分割結(jié)果圖
從視覺效果看,本文算法能夠取得較為理想的分割結(jié)果。由圖7~圖9中可以看出,本文算法相較于Kapur算法、PSO-Otsu算法、MOABC算法、MOPSO算法能夠有效地分清灰質(zhì)和白質(zhì),在視覺效果上有了明顯的提升;而Otsu算法和MEABCT算法雖然能大致分清灰質(zhì)和白質(zhì),但本文算法在一些細(xì)節(jié)處理方面的性能更優(yōu)。
分析表3中的分割準(zhǔn)確率可以看出,本文算法相對(duì)于其他對(duì)比算法能夠取得更好的分割結(jié)果。對(duì)于圖像2-4,切片號(hào)為7時(shí),本文提出的MPS-ABC算法的準(zhǔn)確率為0.973 3,而Kapur算法、PSO-Otsu算法和MOPSO算法的準(zhǔn)確率分別為0.938 6,0.925 1和0.944 4;對(duì)于圖像110-3,切片號(hào)為37時(shí),本文算法的準(zhǔn)確率為0.935 6,相對(duì)于Kapur算法提升了0.053 7,相較于MEABCT算法準(zhǔn)確率提高了0.053 5,比MOPSO算法的準(zhǔn)確率高出0.064 7。
綜合各算法在圖像分割準(zhǔn)確率和視覺效果上的表現(xiàn)可知,本文所提出的MPS-ABC算法的性能更好,能夠得到更優(yōu)的分割結(jié)果。
將粒子群和蜂群的混合優(yōu)化策略引入到閾值圖像分割算法中,使算法在全局和局部搜索能力之間建立一個(gè)良好的平衡。同時(shí)將多目標(biāo)優(yōu)化引入到閾值圖像分割中,采用改進(jìn)的最大類間方差和最大熵2個(gè)準(zhǔn)則作為該算法的目標(biāo)函數(shù);在ABC算法的進(jìn)化過程中對(duì)搜索方程進(jìn)行了改進(jìn),增強(qiáng)了算法的尋優(yōu)能力,避免種群陷入局部最優(yōu),使得算法能更加有效地逼近最優(yōu)閾值,獲得更加好的圖像分割效果。
Table 3 Segmentation accuracy values of all algorithms on MR images 表3 所有算法在MR圖像上的分割準(zhǔn)確率
本文算法的閾值數(shù)目是提前設(shè)定好的,因此如何自適應(yīng)地確定圖像閾值數(shù)目是我們下一步的研究方向。此外,閾值圖像分割對(duì)噪聲比較敏感,因此如何利用圖像的空間信息,使得被噪聲污染的圖像能夠取得良好的分割結(jié)果將是一個(gè)非常有意義的研究方向。