多目標粒子群和人工蜂群混合優(yōu)化的閾值圖像分割算法*

趙 鳳，孔令潤，馬改妮

(1.西安郵電大學通信與信息工程學院,陜西 西安 710121; 2.西安郵電大學電子信息現(xiàn)場勘驗應用技術公安部重點實驗室,陜西 西安 710121)

1 引言

隨著目標識別、機器視覺的不斷發(fā)展，圖像分割技術越來越受到人們的重視。圖像分割的目的是將一幅圖像劃分為多個感興趣的區(qū)域，以便后續(xù)對這些區(qū)域進行進一步處理。目前常用的分割方法主要包括基于閾值的分割方法[1]、基于區(qū)域的分割方法[2]和基于聚類的分割方法[3]等。在諸多的圖像分割方法中，基于閾值的圖像分割方法因其性能穩(wěn)定、算法簡單等特點，一直是圖像分割領域中的熱門研究方向。其中，最大類間方差法(Otsu)[4]、最大熵法(Kapur)[5]由于其原理簡單，易于實現(xiàn)，因此是最常見的2種閾值分割算法。但是，上述算法對于雙峰不明顯的復雜圖像分割效果不佳；而且在進行多閾值圖像分割時，由于計算量過大，效率太低，往往也不能得到理想的分割結果。

為了解決上述問題，有學者將粒子群優(yōu)化PSO(Particle Swarm Optimization)算法[6]和人工蜂群ABC(Artificial Bee Colony)算法[7]等生物啟發(fā)式算法應用到閾值圖像分割[8 - 11]中。文獻[8]針對二維Otsu算法計算量過大的缺點，采用PSO算法尋找最優(yōu)的二維閾值向量，實驗結果表明，該算法在取得較為理想分割結果的同時，大大減少了計算量。文獻[9]提出了一種基于ABC優(yōu)化的閾值圖像分割算法，將最大熵函數(shù)作為需要優(yōu)化的目標函數(shù)，可以得到良好的分割結果。需要指出的是，PSO算法和ABC算法在優(yōu)化的后期階段都存在一些問題[12,13]，PSO算法易陷入局部最優(yōu)，而ABC算法的全局搜索能力雖然強，但局部搜索能力較弱，不能達到一個很好的平衡。因此，有學者結合ABC算法與PSO算法的優(yōu)點，提出了ABC算法和PSO算法相結合的混合優(yōu)化算法[14,15]。文獻[15]在PSO算法中引入人工蜂群搜索算子，利用人工蜂群算子具有較強的全局探索能力的特點，對粒子的歷史最優(yōu)位置進行搜索，從而避免陷入局部最優(yōu)。

然而，上述方法都只是單個閾值準則下的優(yōu)化問題，無法滿足用戶多方面的需求，因此多個閾值準則下的圖像分割問題越來越值得研究。近年來，多目標優(yōu)化算法被用到閾值圖像分割[16 - 18]中，與其他單目標的閾值分割算法相比，多目標優(yōu)化算法在多個閾值準則之間協(xié)調權衡，盡量使得各個閾值準則都達到最優(yōu)。在文獻[17]中，Nakib等人提出了利用第2代非支配排序遺傳算法NSGA-Ⅱ(Non-dominated Sorting Genetic Algorithms-Ⅱ)[18]同時優(yōu)化改進的類間方差、香農熵和2-D熵函數(shù)這3個目標函數(shù)。

本文針對多閾值分割問題，利用PSO算法開采能力強而ABC算法注重探索能力的特性，提出了基于多目標粒子群和人工蜂群混合優(yōu)化MPS-ABC(Multi-objective Particle Swarm and Artificial Bee Colony hybrid optimization)的閾值圖像分割算法。該算法采用改進的最大類間方差準則和最大熵準則作為多目標進化的2個適應度函數(shù)，提出了一種粒子群和蜂群的混合進化策略，并對ABC算法的搜索策略進行了改進，在進化過程中每隔1代進行1次信息的交互，避免由于錯誤的信息判斷而陷入局部最優(yōu)的問題，從而能夠更加有效地逼近最優(yōu)閾值。本文將最大類間方差法[4]、最大熵法[5]、基于最大熵的人工蜂群閾值MEABCT(the Maximum Entropy based Artificial Bee Colony Thresholding)圖像分割算法[9]、基于Otsu標準的多級閾值粒子群優(yōu)化算法[19]PSO-Otsu(Particle Swarm Optimization algorithm for multilevel thresholding by the criteria of Otsu)、多目標人工蜂群優(yōu)化MOABC(Multi-objective Optimization method based on the Artificial Bee Colony)算法[20]和基于多目標粒子群優(yōu)化MOPSO(Multi-Objective Particle Swarm Optimization)的閾值圖像分割算法[21]作為對比算法。實驗結果表明，本文算法對于目標和背景復雜的多閾值圖像的分割，不但縮短了計算時間，而且還能取得較為理想的分割結果。

2 粒子群優(yōu)化算法和蜂群算法的基礎理論

2.1 粒子群優(yōu)化算法

PSO算法[6]是模擬鳥群覓食行為的一種優(yōu)化算法。PSO算法首先在搜索空間內生成1組均勻分布的粒子xi=(xi,1,xi,2,…,xi,D),i= 1,2,…,N，N表示種群規(guī)模，D表示粒子的維度。每1個粒子會有1個速度來決定飛行的距離和方向，速度的更新是由當前粒子經(jīng)歷過的最好位置以及所有粒子在每次迭代中得到的最好位置決定的。粒子的速度更新如式(1)所示：

(1)

對于每1個粒子xi，更新方式如式(2)所示：

xi,j(t+1)=xi,j(t)+vi,j(t)

(2)

(3)

其中，f是目標函數(shù)。

全局最優(yōu)解gbest由式(4)計算得出：

(4)

2.2 人工蜂群算法

在ABC算法[7]中，蜂群由雇傭蜂、跟隨蜂和偵察蜂3個部分組成，整個蜂群的目標是尋找花蜜量最大的蜜源，即優(yōu)化問題中的最優(yōu)解。雇傭蜂的數(shù)量和跟隨蜂的數(shù)量是相等的。雇傭蜂的作用是搜索花蜜源并把蜜源信息傳遞給跟隨蜂；跟隨蜂根據(jù)蜜源的豐富程度采用輪盤賭的方式選擇蜜源進行跟隨，并在蜜源周圍進行搜索；如果蜜源經(jīng)過多次更新沒有改進，則放棄該蜜源，雇傭蜂變?yōu)閭刹榉潆S機搜索新蜜源。在ABC算法中，每個蜜源代表優(yōu)化問題的1個可能解，蜜源的花蜜量(解的優(yōu)劣)是通過適應度值來評定的。雇傭蜂的數(shù)量等于蜜源的數(shù)量。

假設問題的解空間是D維的，則第i個蜜源的位置可以表示為1個D維的向量xi=(xi,1,xi,2,…,xi,D),i= 1,2,…,N，N代表蜜源的數(shù)量。ABC算法各個階段的細節(jié)如下所示：

在種群的初始化階段，根據(jù)式(5)來隨機產(chǎn)生蜜源的位置:

(5)

在雇傭蜂階段，雇傭蜂會在蜜源周圍進行搜索，并按照式(6)產(chǎn)生新的個體x′i，每1個蜜源對應1個變量trial來記錄該蜜源連續(xù)未被改善的次數(shù)，若某一蜜源的trial值超過限定的循環(huán)次數(shù)l，則對應雇傭蜂轉化為偵察蜂隨機搜索新蜜源。

x′i,j=xi,j+rand()·(xi,j-xk,j)

(6)

其中，j是{1,2,…,D}中隨機選擇的整數(shù)，代表雇傭蜂隨機地選擇可行解的一維進行更新搜索；xk,j表示在蜜源中隨機地選擇1個不同于xi,j的蜜源。

在跟隨蜂階段，跟隨蜂會評估雇傭蜂帶回的花蜜量的信息，并采用輪盤賭的方法選擇雇傭蜂進行跟隨。跟隨蜂選擇雇傭蜂的概率計算如式(7)所示:

(7)

其中，fit(xi)代表第i個蜜源的花蜜量。

在偵查蜂階段，如前文所述，若1個蜜源經(jīng)過l次循環(huán)之后不能被改進，則該蜜源被放棄，同時，該蜜源處的雇傭蜂成為偵察蜂，偵查蜂會根據(jù)式(5)產(chǎn)生1個新的蜜源。

通過分析以上2種算法可以得出：PSO算法更側重于開采能力，局部搜索能力更強，但是容易陷入局部最優(yōu)；而ABC算法則更加注重探索能力，全局搜索能力相對更強。因此，本文結合PSO算法和ABC算法各自的優(yōu)點，提出了一種基于粒子群和蜂群的混合優(yōu)化算法MPS-ABC,并將其用到圖像分割中，以達到更好的分割效果。

3 基于多目標粒子群和人工蜂群混合優(yōu)化的閾值圖像分割算法

3.1 種群初始化及編碼

本文所提出的MPS-ABC算法是對圖像的閾值進行編碼，編碼方式采用實數(shù)制編碼，編碼范圍是[Imin,Imax]，其中Imax和Imin分別表示圖像像素的最大值和最小值。本文算法使用式(5)來生成初始種群，并將生成的種群隨機等分為種群Q1和種群Q2，使其分別作為PSO算法和ABC算法的初始種群。

3.2 適應度函數(shù)的構造

適應度函數(shù)主要用于評價種群中個體的優(yōu)劣性。本文將改進的類間方差函數(shù)和最大熵函數(shù)作為待優(yōu)化的適應度函數(shù)。設1幅圖像總的像素數(shù)目為C，其灰度級為[0,255]，Ci表示像素值為i的像素個數(shù)，則像素值i出現(xiàn)的概率pi由式(8)計算得出：

(8)

設圖像的閾值為t1,t2,…,tn，改進的最大類間函數(shù)定義如下：

(9)

其中，

最大熵函數(shù)的定義如下：

H(t1,t2,…,tn)=H0+…+Hk+…+Hn

(10)

其中,H0,…,Hk,…,Hn分別計算如下：

3.3 粒子群和蜂群的混合優(yōu)化策略

在3.1節(jié)得到2組初始種群，Q1按照PSO算法進行尋優(yōu)，個體的更新采用式(2)進行；Q2按照ABC算法進行尋優(yōu)，為了保證算法的探索能力，同時提高開采能力，在ABC算法中的雇傭蜂階段提出了新的搜索方程[22]：

(M(x)-xk)+A(i)·(xi-xk)

(11)

A(i)=(1+trial(i))-0.2+0.1·rand()

(12)

其中，trial(i)代表第i個個體連續(xù)未更新的次數(shù)。

由于新的搜索方程(11)中引入了最優(yōu)解，因此在提高開采能力的同時也保證了算法的探索能力，能夠讓該算法在全局搜索與局部搜索之間達到更好的平衡。與此同時，算法在混合優(yōu)化的過程中，每隔1次迭代會利用1種信息交流機制進行信息的交互，避免錯誤的信息判斷而陷入局部最優(yōu)解。種群之間的信息交流機制如下所示：

(1)在蜂群的進化過程中，將粒子群更新后的解作為蜂群的初始種群，并在雇傭蜂階段比較式(11)產(chǎn)生的解yi、原解xi和粒子群中的全局最優(yōu)解gbest的適應度值，保留最優(yōu)個體。經(jīng)過l次循環(huán)之后，若還未找到更優(yōu)解，則放棄原來的解，并按照式(5)產(chǎn)生1個新解。

3.4 最優(yōu)解的選擇

本文采用多目標方法進行優(yōu)化，每次迭代產(chǎn)生的解都會根據(jù)擁擠距離進行非支配排序，并保留非支配解，因此經(jīng)過上述步驟會獲得一組非支配解集。但是，在實際應用中，我們往往只需要1個最優(yōu)解。本文通過計算每個非支配解的類間差異和類內差異的加權比值F[23]來選取種群的最優(yōu)解,并對其中的類內差異進行擴展，選取使得F取最大值的個體作為種群最優(yōu)解。加權比值F的定義如下所示：

(13)

(14)

其中，xij表示第j類中的第i個像素的灰度值。

Figure 1 Segmentation results on #3096圖1 #3096分割結果

Figure 2 Segmentation results on #24063圖2 #24063分割結果

3.5 混合優(yōu)化算法的流程

混合優(yōu)化算法的流程如下所示：

步驟1設置種群的規(guī)模N，最大迭代次數(shù)Tmax，局部循環(huán)次數(shù)l，學習因子c1和c2，慣性權重w。

步驟2由式(5)進行種群初始化，并將種群隨機等分為2個種群Q1和Q2。

步驟3設置初始的迭代步數(shù)iter=0。

步驟4種群Q1按照式(11)產(chǎn)生新解，種群Q2按照式(2)產(chǎn)生新解，分別計算新產(chǎn)生解的適應度值。對所有解進行評估，保留非支配解，實現(xiàn)對非支配解集的更新。

步驟52個種群每隔1代進行1次信息的交互。

步驟6更新迭代步數(shù)iter=iter+1，當算法迭代達到Tmax次時終止，輸出找到的解集，否則轉至步驟4。

步驟7從得到的1組非支配解集中，根據(jù)加權比值F選擇最終解。

4 實驗結果與分析

為了驗證本文算法的性能，采用Otsu算法、Kapur算法、MEABCT算法、PSO-Otsu算法、MOABC算法和MOPSO算法作為比較算法。實驗分為2個部分：第1部分采用多幅Berkeley圖像進行驗證，第2部分用核磁共振(MR)圖像進行分割實驗。本文所提出的MPS-ABC算法和6種對比算法的參數(shù)設置如下：本文算法以及其他6種對比算法的種群規(guī)模均設置為30，最大迭代次數(shù)為100；MEABCT算法和MOABC算法的局部循環(huán)次數(shù)設置為100，PSO-Otsu算法中的c1和c2都取1.8，w0取3，ri(t) 是0～1的隨機數(shù)；MOPSO算法和本文算法的學習因子c1=1，c2=2，慣性權重w=0.5。

Figure 3 Segmentation results on #241004圖3 #241004分割結果

Figure 4 Segmentation results on #55067圖4 #55067分割結果

4.1 Berkeley圖像對比實驗

本節(jié)采用多幅Berkeley圖像來驗證算法的分割性能。在Berkeley圖庫中選擇圖像#3096、#24063、#241004、#55067作為實驗對比圖。分割結果如圖1～圖4所示，其中a～i分別展示的是原圖像、標準分割圖、Kapur算法、Otsu算法、MEABCT算法、PSO-Otsu算法、MOABC算法、MOPSO算法和MPS-ABC算法的分割結果。此外，本文采用圖像分割準確率來客觀評價算法的分割結果，相應的結果如表1所示。表2給出的是本文算法和對比算法在6幅Berkeley圖像上得到的最優(yōu)分割閾值。

由圖1～圖4可以明顯看出，本文算法相對于其他6種對比算法能夠取得更好的分割結果。對于圖像#3096，可以看出Kapur算法、Otsu算法、MEABCT算法和PSO-Otsu算法都在圖像的左下角存在明顯的錯分，本文算法相比于這4種算法在視覺效果方面明顯取得了更好的分割效果。在圖2中，Kapur算法、Otsu算法、MEABCT算法、PSO-Otsu算法和MOABC算法對于右上角的天空以及門前的柵欄都存在錯分；而MOPSO算法雖然能分清門前的柵欄，但對于右上角的天空那一部分處理不佳；而本文算法借鑒了ABC算法的進化策略，并且對ABC算法的進化策略進行了改進，所以相對于MOPSO算法來說更容易跳出局部最優(yōu)以找到最優(yōu)閾值，因此對門前的柵欄和右上角的天空都取得了良好的分割效果。

Table 1 Segmentation accuracy values of all algorithms on Berkeley images表1 所有算法在Berkeley圖像上的分割準確率

Table 2 The best thresholds of all algorithms on Berkeley images表2 所有算法在Berkeley圖像上的最優(yōu)分割閾值

根據(jù)表1的準確率對比也可以明顯看出，本文所提出的MPS-ABC算法相較于其他6種對比算法，在大多數(shù)圖像上都取得了較高的分割準確率。例如，對于圖像#135069，本文算法的分割準確率可以達到0.991 6，而Otsu算法和MEABCT算法的分割準確率分別為0.554 1和0.605 5；對比多類分割圖像#55067的分割準確率結果，本文算法的分割準確率為0.921 0，相對于Kapur算法在準確率方面提高了0.118 4，比PSO-Otsu算法高出0.230 6。

通過比較本文算法與其余6種對比算法在準確率以及視覺效果上的差異可知，本文算法的尋優(yōu)能力更強，能夠更加有效地逼近最優(yōu)閾值。

為了驗證本文算法的有效性，圖5給出了Kapur算法、Otsu算法、MEABCT算法、PSO-Otsu算法、MOABC算法、MOPSO算法和MPS-ABC算法在多幅Berkeley圖像下的平均PR曲線對比圖。通過圖5可以看出，本文算法性能優(yōu)于其他6種對比算法。

Figure 5 PR curves comparison of each algorithm圖5 各個算法的PR曲線對比

與已有的Otsu算法與Kapur算法相比，本文算法在多閾值情況下不但分割效果有所提升，運行時間也大大降低。圖6給出了本文算法與Otsu算法、Kapur算法、MOPSO算法以及MOABC算法在5幅閾值圖像#55067下的運行時間對比。可以看出，本文算法相較于Otsu算法和Kapur算法不但分割效果更好，而且運行時間大大降低。而相較于MOPSO算法和MOABC算法，本文算法在運行時間基本相同的情況下，分割效果更好。

Figure 6 Run time comparison of each algorithm圖6 各算法的運行時間對比

4.2 MR圖像對比實驗

為了進一步驗證本文算法的性能，本節(jié)選擇來自互聯(lián)網(wǎng)腦分割庫IBSR(The Internet Brain Segmentation Repository)的MR圖像進行分割實驗，并用圖像分割準確率作為評價標準。如圖7～圖9所示為本文算法與其他6種對比算法在3幅MR圖像上的分割結果；對比算法和本文MPS-ABC算法的準確率如表3所示。

Figure 7 Segmentation results on the slice 12 of image 12-3圖7 圖像12-3切片號為12的分割結果圖

Figure 8 Segmentation results on the slice 50 of image 2-4圖8 圖像2-4切片號為50的分割結果圖

Figure 9 Segmentation results on the slice 45 of image 100-23圖9 圖像100-23切片號為45的分割結果圖

從視覺效果看，本文算法能夠取得較為理想的分割結果。由圖7～圖9中可以看出，本文算法相較于Kapur算法、PSO-Otsu算法、MOABC算法、MOPSO算法能夠有效地分清灰質和白質，在視覺效果上有了明顯的提升；而Otsu算法和MEABCT算法雖然能大致分清灰質和白質，但本文算法在一些細節(jié)處理方面的性能更優(yōu)。

分析表3中的分割準確率可以看出，本文算法相對于其他對比算法能夠取得更好的分割結果。對于圖像2-4，切片號為7時，本文提出的MPS-ABC算法的準確率為0.973 3，而Kapur算法、PSO-Otsu算法和MOPSO算法的準確率分別為0.938 6,0.925 1和0.944 4；對于圖像110-3，切片號為37時，本文算法的準確率為0.935 6，相對于Kapur算法提升了0.053 7，相較于MEABCT算法準確率提高了0.053 5，比MOPSO算法的準確率高出0.064 7。

綜合各算法在圖像分割準確率和視覺效果上的表現(xiàn)可知，本文所提出的MPS-ABC算法的性能更好，能夠得到更優(yōu)的分割結果。

5 結束語

將粒子群和蜂群的混合優(yōu)化策略引入到閾值圖像分割算法中，使算法在全局和局部搜索能力之間建立一個良好的平衡。同時將多目標優(yōu)化引入到閾值圖像分割中，采用改進的最大類間方差和最大熵2個準則作為該算法的目標函數(shù)；在ABC算法的進化過程中對搜索方程進行了改進，增強了算法的尋優(yōu)能力，避免種群陷入局部最優(yōu)，使得算法能更加有效地逼近最優(yōu)閾值，獲得更加好的圖像分割效果。

Table 3 Segmentation accuracy values of all algorithms on MR images 表3 所有算法在MR圖像上的分割準確率

本文算法的閾值數(shù)目是提前設定好的，因此如何自適應地確定圖像閾值數(shù)目是我們下一步的研究方向。此外，閾值圖像分割對噪聲比較敏感，因此如何利用圖像的空間信息，使得被噪聲污染的圖像能夠取得良好的分割結果將是一個非常有意義的研究方向。