趙 鳳, 孔令潤

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

圖像分割的目的是根據(jù)特定的標準將圖像分成若干具有獨特性質(zhì)的互不相干區(qū)域，使得同一區(qū)域內(nèi)的像素特征具有較高相似性，而不同區(qū)域的像素特征具有較大差異性[1]。圖像分割是圖像處理的重要一環(huán)，其結(jié)果會直接影響到后續(xù)圖像處理的質(zhì)量。

現(xiàn)有的圖像分割方法主要包括基于閾值[2]、基于聚類[3]和基于區(qū)域的分割方法[4]等幾類。基于閾值的圖像分割是一種常用的分割方法。圖像閾值是指從背景中提取出的場景對象，有助于分析和解釋圖像?；陂撝档膱D像分割算法假定圖像的直方圖呈雙峰分布，通過在兩峰之間確定某一準則來選擇一個恰當?shù)拈撝担憧蓪崿F(xiàn)圖像的目標和背景的分離。Otsu最大類間方差法[5]、最大熵法[6]和模糊熵法[7]等是比較常用的閾值分割方法。Otsu最大類間方差法利用最大化分割后圖像的類間方差來選取最佳閾值，其原理簡單且對大多數(shù)圖像都能獲得較好的分割結(jié)果。然而，當圖像直方圖沒有明顯的雙峰時，最大類間方差法的分割效果不佳。由于很多圖像的特征信息具有模糊性，因此有學者以香農(nóng)熵為基礎，結(jié)合圖像的模糊數(shù)學描述，提出了圖像模糊熵的概念并將其應用到閾值圖像分割中[8]。在進行多閾值圖像分割時，由于模糊隸屬函數(shù)包含的參數(shù)較多，取值范圍較大，導致該方法分割效果不佳且計算量較大[9]。

為了降低計算量，群智能優(yōu)化算法被用到圖像分割中[10-13]。常見的群智能優(yōu)化算法有粒子群優(yōu)化(particle swarm optimization, PSO)算法[14]和蟻群優(yōu)化(ant colony optimization, ACO)算法[15]等。如文獻[10]針對二維Otsu算法計算量過大的缺點，采用PSO算法尋找最優(yōu)的二維閾值向量，在取得較為理想分割結(jié)果的同時，減小了計算量。文獻[12]提出了基于最小交叉熵的螢火蟲閾值圖像分割算法，對多閾值圖像可以得到良好的分割結(jié)果，并且縮短了計算時間。這些啟發(fā)式算法雖然算法簡單，易于實現(xiàn)，但在迭代后期易陷入局部最優(yōu)，從而影響了分割效果。

為了避免陷入局部最優(yōu)，多元宇宙優(yōu)化(multi-verse optimization, MVO)算法[16]被提出，其具有參數(shù)少、結(jié)構(gòu)簡單、效率高等優(yōu)點。由于MVO算法引入了動態(tài)參數(shù)來控制種群的進化，因此在迭代后期更容易跳出局部最優(yōu)。在MVO算法的基礎上，有學者提出了混合優(yōu)化算法[17-18]，如文獻[17]結(jié)合PSO算法和MVO算法解決全局數(shù)值優(yōu)化和無功優(yōu)化調(diào)度問題。然而，上述方法只考慮了一個目標函數(shù)，當面對多目標優(yōu)化問題時，應用受限。

近年來，多目標優(yōu)化算法被應用到閾值圖像分割[19-21]中，如文獻[19]結(jié)合多目標粒子群優(yōu)化提出了一種基于支配和多樣性準則的多目標閾值分割算法。文獻[21]結(jié)合多元宇宙理論，將類間方差函數(shù)和最大熵函數(shù)作為待優(yōu)化的目標函數(shù)，提出了基于多目標多元宇宙理論的閾值圖像分割算法。不論是最大類間方差法還是最大熵法雖然易于實現(xiàn)，但對于目標和背景差異不明顯的圖像，分割效果不理想。

本文擬針對多目標、多閾值圖像分割問題，提出一種引入混沌搜索的多目標粒子群和多元宇宙混合優(yōu)化(chaos search-based multi-objective hybrid optimization combing particle swarm and multi-verse, CSMHO-PSM)的閾值圖像分割算法。采用類間方差函數(shù)和模糊熵函數(shù)作為多目標優(yōu)化的兩個目標函數(shù)。將MVO算法引入到PSO算法中，引入混沌搜索策略，通過混合優(yōu)化的方法得到更優(yōu)解，避免陷入局部最優(yōu)解。采用類內(nèi)差異性與類間緊致性的加權(quán)比值來確定算法非支配解集中的最優(yōu)解，實現(xiàn)多閾值圖像分割。

1 基礎理論概述

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

PSO算法[14]源自于對鳥群捕食行為的研究，其首先在搜索空間內(nèi)生成一組均勻分布的粒子Xi={Xi,1,Xi,2,…,Xi,D},(i=1,2,…,N),N表示種群規(guī)模，D表示粒子的最大維度。

粒子的速度決定飛行的距離和方向。由當前粒子經(jīng)歷過的最好位置(全局極值)以及所有粒子在每次迭代中得到的最好位置(個體極值)決定速度的更新過程。

粒子i在維度j的第t+1次速度更新過程[14]可以表示為

(1)

粒子i在維度j第t+1次的位置更新方式[14]可以表示為

Xi,j(t+1)=Xi,j(t)+Vi,j(t)。

(2)

假設優(yōu)化問題是極小化問題，粒子i第t+1次迭代的個體最優(yōu)解[14]計算公式為

(3)

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

全局最優(yōu)解gbest的計算公式[14]

(4)

將粒子群算法應用到閾值圖像分割中，能有效減小多閾值分割的計算量。

1.2 多元宇宙優(yōu)化算法

MVO算法[16]是基于物理學中多元宇宙理論中的黑洞、白洞和蟲洞等3個主要概念提出的群智能優(yōu)化算法。白洞是一個只發(fā)射不吸收的特殊天體；黑洞剛好與白洞相反，它吸引宇宙中一切事物，所有的物理定律在黑洞中都會失效；蟲洞作為連結(jié)白洞和黑洞的多維時空隧道，將個體傳送到宇宙的任意角落，甚至是從一個宇宙到另一個宇宙。而多元宇宙通過白洞、黑洞和蟲洞相互作用達到一個穩(wěn)定狀態(tài)。在優(yōu)化問題中，假設每個解都是一個宇宙，每個解中的變量都是相應宇宙中的對象。MVO算法可以簡單地歸納為以下幾個步驟。

步驟1初始化宇宙數(shù)U和最大迭代次數(shù)q。

步驟2在每次迭代中，根據(jù)宇宙的標準膨脹率對宇宙進行排序，然后通過輪盤賭機制選擇其中一個宇宙來建立一個白洞[16]，其公式為

(5)

步驟3更新蟲洞存在概率PWE和蟲洞向最優(yōu)宇宙移動的旅行距離率RTD。PWE和RTD的計算公式[16]分別為

(6)

(7)

步驟4計算當前宇宙膨脹率，若宇宙膨脹率優(yōu)于當前宇宙膨脹率，則更新當前宇宙保存膨脹率，否則，保持當前宇宙。

步驟5更新宇宙位置，并在最優(yōu)宇宙中尋找最優(yōu)個體。其選擇條件[16]為

若r2

(8)

將MVO算法與PSO算法相結(jié)合能改善PSO算法在迭代后期易陷入局部最優(yōu)的缺點。

1.3 混沌搜索

混沌搜索[22]通過某種特定方式迭代產(chǎn)生混沌序列，然后通過載波的方式將混沌變量放大到優(yōu)化變量的取值范圍中，混沌搜索的過程如下。

首先隨機初始一個D維的向量y0=[y0,1,y0,2,…,y0,D],0

yn+1,D=μyn,D(1-yn,D)。

(10)

其中：n∈[0,Nmax]，Nmax為解的最大個數(shù)；μ是混沌狀態(tài)的控制參數(shù)，μ取4時，Logistic方程完全進入混沌狀態(tài)。

向量y0產(chǎn)生混沌序列后，通過載波的方式將混沌變量的值映射到優(yōu)化變量的取值范圍。然后實行載波操作將混沌變量放大，再加載于待搜索的個體變量上，從而得到新個體yn,D，生成公式[23]可以表示為

yn,D=fz,D(2yn,D-1)。

(11)

其中：fz,D代表待搜索個體；Rz,D為混沌搜索半徑。

為了進一步提高閾值分割算法的精度，可以進行K次混沌搜索，以提高種群多樣性，從而優(yōu)化閾值圖像分割的效果。

2 基于CSMHO-PSM的閾值圖像分割

將類間方差函數(shù)和模糊熵函數(shù)作為算法的兩個目標函數(shù)，并引入MVO算法來改進PSO算法易陷入局部最優(yōu)的缺點。加入混沌搜索策略以提高算法的搜索精度，使其更加有效地逼近最優(yōu)閾值。多目標進化后會產(chǎn)生一組非支配解，利用類間差異和類內(nèi)差異的加權(quán)比值來選擇最優(yōu)解。

2.1 種群的初始化及編碼

對圖像閾值進行編碼，編碼方式為實數(shù)制編碼，編碼范圍為[Imin,Imax]，Imin和Imax分別表示圖像像素的最小值和最大值。設算法中種群規(guī)模為g(g=1,2,…,N)，其解的維度為e(e=1,2,…,D)，則其種群初始解可表示為

Ig,e=Imin+r5(Imax-Imin)。

(12)

其中：Imin和Imax分別表示一幅圖像像素灰度值的最小值和最大值；r5表示[0,1]之間的隨機數(shù)。

2.2 適應度函數(shù)的構(gòu)造

采用類間方差函數(shù)和模糊熵函數(shù)作為優(yōu)化的適應度函數(shù)。假設一幅圖像總的像素數(shù)目為C，其灰度級h的取值范圍為[0,255]，具有灰度級h的像素個數(shù)為Ch，則灰度級h出現(xiàn)的概率為

(13)

設圖像閾值為t1,…,tl,…,tn，閾值數(shù)目l=1,2,…,n，基于多閾值的類間方差函數(shù)的可以定義為

f1(t1,…,tl,…,tn)=w0(μ0-μT)2+…+wk(μk-μT)2+…+wn(μn-μT)2。

(14)

(15)

當式(14)中的f1(t1,…,tl,…,tn)取最大值時，即可獲得圖像的最佳閾值。

假設一幅圖像的閾值為t1,t2，則基于兩閾值的模糊熵函數(shù)可以定義為

f2(t1,t2)=H0+H1+H2。

(16)

式(16)中H0,H1,H2的計算公式分別[24]為

(17)

其中u0(h),u1(h),u2(h)分別表示3個隸屬度函數(shù)，可以用0≤a1≤b1≤c1≤a2≤b2≤c2的6個參數(shù)確定。u0(h),u1(h),u2(h)表達式[23]分別為

(18)

(19)

(20)

總模糊熵的大小f2(t1,t2)由a1,b1,c1,a2,b2,c2等6個參數(shù)確定，利用最大熵準來確定6個參數(shù)的最優(yōu)組合[23]，最優(yōu)分割閾值滿足

u0(t1)=u1(t1)=0.5,u1(t2)=u2(t2)=0.5。

(21)

由式(18)、式(19)和式(20)可以得出閾值t1,t2的計算方法[23]分別為

(22)

(23)

由兩閾值的模糊熵函數(shù)的定義公式可以擴展到單閾值和多閾值問題。

2.3 引入混沌搜索的混合優(yōu)化策略

為了克服PSO算法在迭代后期易陷入局部最優(yōu)的缺點，將MVO算法引入到PSO算法中，利用一個可能性參數(shù)來控制種群的進化方向。可能性參數(shù)Pr計算方法為

Pr=λ+trial(m)/Tmax。

(24)

其中：trial (m)表示當前迭代次數(shù)；Tmax表示最大迭代次數(shù)；λ是一個動態(tài)參數(shù)，其取值大小會直接影響種群的進化方向。

隨機生成一個數(shù)r6∈[0,1]，若r6小于Pr，則采用MVO算法進行進化，否則采用PSO算法進行進化。

進化完成后，為了提高算法的精度，在新產(chǎn)生解的周圍進行K次混沌搜索，并根據(jù)適應度函數(shù)的值來判斷是否保留搜索到的解。

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

采用多目標方法進行優(yōu)化，在進化結(jié)束后會獲得一組非支配解集。而在實際應用中，只需要一個最優(yōu)解，因此，需要計算每個非支配解的類間差異和類內(nèi)緊致的加權(quán)比值[24]的最大值作為最優(yōu)解，加權(quán)比值的定義為

(25)

其中：k表示閾值數(shù)目；C為圖像像素的總數(shù)；SA和SE分別表示類間差異性和類內(nèi)緊致性，其表達式分別為

(26)

其中：Cb為第b類的像素總數(shù)；yb表示第b類的灰度平均值；y表示所有像素的平均灰度值；xhb表示第b類中的第h個像素的灰度值。

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

采用多幅Berkeley圖像和互聯(lián)網(wǎng)腦分割庫(the Internet brain segmentation repository, IBSR)的核磁共振(nuclear magnetic resonance, MR)圖像進行分割實驗，以圖像分割準確率、峰值信噪比(peak signal-to-noise ratio, PSNR)、結(jié)構(gòu)相似性(structural similarity, SSIM)作為評價指標，驗證算法的性能。

由式(24)可以看出，λ的取值大小會直接影響種群的進化方向，為此對4幅Berkeley圖像#3096、#238011、#241004、#42049進行圖像分割試驗，以確定合適的λ值。當λ分別取0、0.03、0.05、0.08、0.10、0.12、0.20、0.30、0.40、0.50時，4幅圖像在不同λ下的分割準確率如圖1所示?？梢钥闯靓巳?.08時，分割結(jié)果最優(yōu)，因此本算法的λ取0.08。

圖1 4幅圖像在不同λ下的分割準確率

3.1 Berkeley圖像分割實驗

采用多幅Berkeley圖像來驗證算法性能。在Berkeley圖庫選擇#3096、#24063、#135069和#241004進行分割，分割結(jié)果如圖2—圖5所示?？梢钥闯鯟SMHO-PSM算法相對于其他對比算法能夠取得更好的分割結(jié)果。在圖3中，基于多目標粒子群優(yōu)化[25](multi-objective particle swarm optimization, MOPSO)的閾值圖像分割算法和Otsu算法對于右上角的天空和門前的柵欄都存在錯分。CSMHO-PSM算法對于天空右上角基本無錯分。對于圖像#135069，CSMHO-PSM算法相對于Otsu算法明顯能夠得到更好的分割結(jié)果，對比MOPSO算法和基于多目標多元宇宙優(yōu)化(multi-objective multi-verse optimization, MOMVO)的閾值圖像分割算法[21]，CSMHO-PSM算法在細節(jié)處理方面更為出色，能夠更好地保留兩只鳥連接處的細節(jié)信息。

圖2 #3096分割結(jié)果

圖3 #24063分割結(jié)果

圖4 #135069分割結(jié)果

圖5 #241004分割結(jié)果

選取10幅Berkeley圖像測試不同算法的準確率、PSNR值和SSIM值，共做實驗5次，取5次實驗的平均值。4種算法的分割準確率、PSNR值和SSIM值如表1所示?？梢钥闯鯟SMHO-PSM算法相較于其他3種對比算法能夠取得更優(yōu)的分割結(jié)果。例如，對于圖像#135069，CSMHO-PSM算法的圖像分割準確率能達到0.991 7，比Otsu法提高了0.4396，對比PSNR值和SSIM值也分別提高了13.551和0.180 5。在圖像#3096中，CSMHO-PSM算法相對于其他對比算法，在圖像分割準確率、PSNR值和SSIM上均有所提高。對于多類圖像#241004，雖然CSMHO-PSM算法的分割準確率略低于Otsu法，但PSNR值和SSIM值相較于其他3種方法均有所提高。

表1 4種算法對Berkeley圖像的分割準確率、PSNR值和SSIM值

3.2 MR圖像分割實驗

為了進一步驗證本文算法的實用性，選擇更復雜的、來自互聯(lián)網(wǎng)腦分割庫(the Internet brain segmentation repository, IBSR)的MR圖像進行分割實驗，并用圖像分割準確率作為評價標準。不同算法對兩幅MR圖像的分割結(jié)果分別如圖6—圖7所示。從視覺效果看，本文算法能夠取得較為理想的分割結(jié)果。由圖6中可以看出，本文算法相較于Otsu算法和MOPSO算法能夠有效的分清灰質(zhì)和白質(zhì)，在視覺效果上有了明顯的提升；MOMVO算法雖然能大致分清灰質(zhì)和白質(zhì)，但在一些細節(jié)處理方面本文算法的性能更優(yōu)。

圖6 切片號12對應的12-3圖像分割結(jié)果

圖7 切片號39對應的16-3圖像分割結(jié)果

不同算法對MR圖像的分割準確率如表2所示。可以看出，本文算法相對于其他對比算法能夠取得更好的分割結(jié)果。對于切片號7對應的圖像2-4，本文提出的CSMHO-PSM算法的準確率為0.967 4，而Otsu算法、MOPSO算法和MOMVO算法的準確率分別為0.953 7、0.941 2和0.955 3；對于切片號8對應的圖像8-4，本文算法的準確率為0.967 2，相對于Otsu算法的準確率提升了0.015 3，比MOPSO算法和MOMVO算法的準確率分別高出0.023 2和0.016 5。

表2 4種算法對MR圖像的分割準確率

綜合不同算法在分割Berkeley圖像和MR圖像上的各項評價指標和視覺效果上的表現(xiàn)，本文所提出的CSMHO-PSM算法的性能更好，能夠得到更優(yōu)的分割結(jié)果。這是因為相對于MOPSO算法，CSMHO-PSM算法引入了MVO算法來改進PSO算法，避免了PSO算法在迭代后期易陷入局部最優(yōu)的缺點。

4 結(jié)語

針對PSO算法易陷入局部最優(yōu)，從而導致圖像分割效果不穩(wěn)定的缺點，提出了一種基于粒子群和多元宇宙混合優(yōu)化的閾值圖像分割算法。算法結(jié)合了多目標優(yōu)化，并將類間方差函數(shù)和模糊熵函數(shù)作為待優(yōu)化的目標函數(shù)。為了進一步避免算法陷入局部最優(yōu)，在算法中加入混沌搜索策略。仿真實驗結(jié)果表明，本文算法能夠較好地分割圖像，相較于Otsu算法、MOPSO算法和MOMVO算法具有更優(yōu)的分割準確率。