多目標混合優(yōu)化的閾值圖像分割

趙 鳳, 孔令潤

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

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

現有的圖像分割方法主要包括基于閾值[2]、基于聚類[3]和基于區(qū)域的分割方法[4]等幾類?；陂撝档膱D像分割是一種常用的分割方法。圖像閾值是指從背景中提取出的場景對象，有助于分析和解釋圖像?；陂撝档膱D像分割算法假定圖像的直方圖呈雙峰分布，通過在兩峰之間確定某一準則來選擇一個恰當的閾值，便可實現圖像的目標和背景的分離。Otsu最大類間方差法[5]、最大熵法[6]和模糊熵法[7]等是比較常用的閾值分割方法。Otsu最大類間方差法利用最大化分割后圖像的類間方差來選取最佳閾值，其原理簡單且對大多數圖像都能獲得較好的分割結果。然而，當圖像直方圖沒有明顯的雙峰時，最大類間方差法的分割效果不佳。由于很多圖像的特征信息具有模糊性，因此有學者以香農熵為基礎，結合圖像的模糊數學描述，提出了圖像模糊熵的概念并將其應用到閾值圖像分割中[8]。在進行多閾值圖像分割時，由于模糊隸屬函數包含的參數較多，取值范圍較大，導致該方法分割效果不佳且計算量較大[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)的二維閾值向量，在取得較為理想分割結果的同時，減小了計算量。文獻[12]提出了基于最小交叉熵的螢火蟲閾值圖像分割算法，對多閾值圖像可以得到良好的分割結果，并且縮短了計算時間。這些啟發(fā)式算法雖然算法簡單，易于實現，但在迭代后期易陷入局部最優(yōu)，從而影響了分割效果。

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

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

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

1 基礎理論概述

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

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

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

粒子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是目標函數。

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

(4)

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

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

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

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

步驟2在每次迭代中，根據宇宙的標準膨脹率對宇宙進行排序，然后通過輪盤賭機制選擇其中一個宇宙來建立一個白洞[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算法相結合能改善PSO算法在迭代后期易陷入局部最優(yōu)的缺點。

1.3 混沌搜索

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

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

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

(10)

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

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

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

(11)

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

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

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

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

2.1 種群的初始化及編碼

對圖像閾值進行編碼，編碼方式為實數制編碼，編碼范圍為[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]之間的隨機數。

2.2 適應度函數的構造

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

(13)

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

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，則基于兩閾值的模糊熵函數可以定義為

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

(16)

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

(17)

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

(18)

(19)

(20)

總模糊熵的大小f2(t1,t2)由a1,b1,c1,a2,b2,c2等6個參數確定，利用最大熵準來確定6個參數的最優(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)

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

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

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

Pr=λ+trial(m)/Tmax。

(24)

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

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

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

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

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

(25)

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

(26)

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

3 實驗結果及分析

采用多幅Berkeley圖像和互聯網腦分割庫(the Internet brain segmentation repository, IBSR)的核磁共振(nuclear magnetic resonance, MR)圖像進行分割實驗，以圖像分割準確率、峰值信噪比(peak signal-to-noise ratio, PSNR)、結構相似性(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時，分割結果最優(yōu)，因此本算法的λ取0.08。

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

3.1 Berkeley圖像分割實驗

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

圖2 #3096分割結果

圖3 #24063分割結果

圖4 #135069分割結果

圖5 #241004分割結果

選取10幅Berkeley圖像測試不同算法的準確率、PSNR值和SSIM值，共做實驗5次，取5次實驗的平均值。4種算法的分割準確率、PSNR值和SSIM值如表1所示?？梢钥闯鯟SMHO-PSM算法相較于其他3種對比算法能夠取得更優(yōu)的分割結果。例如，對于圖像#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圖像分割實驗

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

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

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

不同算法對MR圖像的分割準確率如表2所示。可以看出，本文算法相對于其他對比算法能夠取得更好的分割結果。對于切片號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圖像上的各項評價指標和視覺效果上的表現，本文所提出的CSMHO-PSM算法的性能更好，能夠得到更優(yōu)的分割結果。這是因為相對于MOPSO算法，CSMHO-PSM算法引入了MVO算法來改進PSO算法，避免了PSO算法在迭代后期易陷入局部最優(yōu)的缺點。

4 結語

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