超像素驅(qū)動的代理輔助多目標(biāo)聚類圖像分割

趙 鳳，張莉陽

(西安郵電大學(xué) 通信與信息工程學(xué)院,陜西 西安 710121；西安郵電大學(xué) 電子信息現(xiàn)場勘驗應(yīng)用技術(shù)公安部重點實驗室,陜西 西安 710121)

圖像分割是指將圖像分成若干互不重疊的子區(qū)域，使得同一個子區(qū)域內(nèi)的特征具有一定相似性、不同子區(qū)域間特征呈現(xiàn)較為明顯的差異[1]?，F(xiàn)有的圖像分割方法主要包括閾值的方法[2]、區(qū)域的方法[3]和聚類的方法[4]等。其中，基于聚類的方法是眾多研究者研究的熱點之一，模糊C-均值(fuzzy C-means,FCM)聚類算法[5]是一種經(jīng)典的聚類算法，但是FCM算法具有對聚類中心初始值敏感、易陷入局部最優(yōu)及易受噪聲影響等缺點。針對FCM算法的不足，核模糊C-均值聚類算法[6](kernel fuzzy C-means clustering,KFCM)將原空間線性不可分的樣本變?yōu)榫€性可分或近似線性可分。

在實際應(yīng)用中，為了滿足不同需求，需要從多個角度考慮問題。因此，多目標(biāo)進(jìn)化算法(multi-objective evolutionary genetic algorithm,MOEA)的研究吸引到眾多研究者的關(guān)注，多目標(biāo)進(jìn)化聚類算法也取得了豐碩的成果[7]。與單目標(biāo)聚類算法相比，多目標(biāo)進(jìn)化聚類算法降低了對聚類中心初始值的敏感程度且解決了易陷入局部最優(yōu)的缺點。此外，該類算法通過選取合適的染色體編碼策略和適應(yīng)度函數(shù)可以自動確定聚類數(shù)目，減少了人為干預(yù)。多目標(biāo)可變長遺傳模糊聚類算法[8](multi-objective variable string length genetic fuzzy clustering algorithm,MOVGA)已經(jīng)被成功應(yīng)用于腦部醫(yī)學(xué)圖像的分割。

然而，多目標(biāo)進(jìn)化聚類算法應(yīng)用于圖像分割時，往往是基于像素進(jìn)行聚類，分割效果不好且運行時間太長。為此，通過引入超像素信息和基于代理輔助參考向量引導(dǎo)的多目標(biāo)進(jìn)化算法，擬提出一種超像素驅(qū)動的代理輔助多目標(biāo)聚類圖像分割算法。利用超像素策略得到超像素區(qū)域，并提取每個超像素區(qū)域的代表特征得到超像素信息，采用融合超像素信息的MOVGA有效性函數(shù)作為適應(yīng)度函數(shù)，進(jìn)行基于代理輔助參考向量引導(dǎo)的多目標(biāo)進(jìn)化聚類，并采用融合超像素信息的最優(yōu)解評價指標(biāo)選取最優(yōu)解，實現(xiàn)多目標(biāo)進(jìn)化聚類圖像分割。

1 多目標(biāo)進(jìn)化聚類算法

1.1 多目標(biāo)優(yōu)化理論

在人們的日常生活和工作中，經(jīng)常會遇到需要優(yōu)化多個相互沖突的目標(biāo)問題，這類問題被稱為多目標(biāo)優(yōu)化問題。以最小化目標(biāo)函數(shù)為例，假設(shè)決策變量為z=(z1,z2,…,zα)，目標(biāo)函數(shù)為f(z)=[f1(z),f2(z),…,fβ(z)]，那么多目標(biāo)優(yōu)化問題的數(shù)學(xué)表達(dá)式為

其中，滿足約束條件gi(z)和hj(z)的變量z為可行解，所有可行解的集合稱為可行解集合。設(shè)z1和z2是上述最小化多目標(biāo)優(yōu)化問題的兩個可行解，當(dāng)且僅當(dāng)對所有子目標(biāo)函數(shù)，z1不比z2差，且至少存在一個子目標(biāo)函數(shù)，z1比z2好，則稱z1Pareto支配z2。一個解被稱為Pareto最優(yōu)解或者非支配解，當(dāng)且僅當(dāng)沒有其他解可以支配它。由Pareto最優(yōu)解構(gòu)成的集合被稱為Pareto最優(yōu)解集或者非支配解集。

1.2 多目標(biāo)進(jìn)化聚類

進(jìn)化算法是一種全局優(yōu)化算法。將進(jìn)化算法引入到多目標(biāo)優(yōu)化中，使得聚類算法具有較強的全局搜索能力。不同的多目標(biāo)進(jìn)化優(yōu)化算法相繼被提出，如非支配排序遺傳算法[9](non-dominated sorting genetic algorithm,NSGA)和改進(jìn)的非支配排序遺傳算法NSGA-II[10]等。

多目標(biāo)進(jìn)化聚類算法[11]利用多目標(biāo)進(jìn)化算法同時優(yōu)化反映連通性和總體偏差的兩個適應(yīng)度函數(shù)，但是，該算法屬于硬聚類，不符合現(xiàn)實世界亦此亦彼的特點。MOVGA算法可同時優(yōu)化類內(nèi)緊致和類間分離兩個適應(yīng)度函數(shù)實現(xiàn)多目標(biāo)進(jìn)化聚類[8]?，F(xiàn)有的多目標(biāo)進(jìn)化聚類算法通常是采用NSGA-II算法作為基本大框架。

2 超像素驅(qū)動代理輔助多目標(biāo)聚類

2.1 超像素區(qū)域代表特征的獲取

傳統(tǒng)的聚類算法應(yīng)用于圖像分割時，通常是基于像素進(jìn)行聚類，分割效果不好，且計算效率很低。2003年，超像素[12]的概念被提出。所謂超像素，是指圖像中局部的、具有一致性的，能夠保持一定圖像局部結(jié)構(gòu)特征的子區(qū)域[13]。之后，學(xué)者們提出了眾多超像素算法，如Normalized cuts算法[14]和簡單線性迭代聚類[15](simple linear iterative cluster,SLIC)算法等。

然而，超像素算法計算復(fù)雜度較高，邊緣分割貼合度較差。差分進(jìn)化超像素分割[16-17](differen-tial evolutionary superpixel segmentation,DES)算法與其他超像素算法相比，最大的優(yōu)點是在對圖像進(jìn)行超像素分割時，考慮多個全局屬性的綜合目標(biāo)函數(shù)，包括超像素內(nèi)誤差、邊界梯度和正則化項，然后在差分進(jìn)化這個強大的全局優(yōu)化器上完成優(yōu)化，超像素邊緣貼合度更高，形狀更加規(guī)則，且該算法的計算復(fù)雜度與圖像大小成正比。因此，超像素驅(qū)動的代理輔助多目標(biāo)聚類圖像分割算法采用DES方法提取圖像的超像素區(qū)域。

對圖像進(jìn)行差分進(jìn)化超像素分割，獲得K個超像素區(qū)域B={B1,B2,…,BK}，然后提取每個超像素區(qū)域的代表特征。對于第k個超像素區(qū)域，其代表特征紅綠藍(lán)(red green blue,RGB)值[18]的計算公式為

其中：yp表示該超像素區(qū)域內(nèi)像素點p的RGB特征值；yn表示該超像素區(qū)域內(nèi)中值像素點n的RGB特征值。w(yp,yn)表示像素點p與n之間的權(quán)重，計算公式為

w(yp,yn)=Dpn×Lpn,

Lpn=e-|yp-yn|2/δ2。

其中：(ρ,θ)表示超像素中像素點的坐標(biāo)；x表示超像素中像素點的個數(shù)；δ表示該超像素區(qū)域的顏色特征方差。Dpn表示位置權(quán)重[19]，像素點p距離n越近，其權(quán)重越高。Lpn表示顏色權(quán)重[18]，像素點p與n顏色信息越接近，其權(quán)重越高。最后得到超像素區(qū)域的代表特征r={r1,r2,…,rK}。

2.2 適應(yīng)度函數(shù)計算

在多目標(biāo)進(jìn)化聚類算法中，通常根據(jù)適應(yīng)度函數(shù)的大小對個體進(jìn)行優(yōu)勝劣汰，選擇合適的適應(yīng)度函數(shù)對提高算法性能很關(guān)鍵。因此，所提算法采用兩個適應(yīng)度函數(shù)，一個是融合超像素信息的類內(nèi)緊致性函數(shù)，另一個是融合超像素信息的類間分離性函數(shù)。融合超像素信息的類內(nèi)緊致性函數(shù)定義為

(1)

其中：m表示模糊指數(shù)；C表示聚類數(shù)目；vi表示第i類聚類中心；uik表示第k個超像素區(qū)域?qū)Φ趇類聚類中心的隸屬度，計算公式為

(2)

融合超像素信息的類間分離性函數(shù)定義為

(3)

其中，μlq表示vq相對于vl的隸屬度，計算公式為

根據(jù)函數(shù)J和S的描述可知，J要盡可能小，S要盡可能大。

2.3 染色體編碼、種群初始化及進(jìn)化操作策略

對聚類中心采用實數(shù)編碼。假設(shè)一個染色體是由d維數(shù)據(jù)空間里的C個聚類中心組成，那么該染色體的長度為d×C。例如，在三維數(shù)據(jù)空間里，兩個聚類中心(19.9,15.5,17.4)和(129.9,132.8,48.9)構(gòu)成染色體(19.9,15.5,17.4,129.9,132.8,48.9)。所提算法的初始種群是從超像素區(qū)域的代表特征r={r1,r2,…,rK}中隨機選取產(chǎn)生。

采用基于代理輔助參考向量引導(dǎo)的多目標(biāo)進(jìn)化算法[20](kriging-assisted reference vector guided evolutionary algorithm,K-RVEA)進(jìn)行多目標(biāo)聚類圖像分割。Kriging模型[21]作為代理模型，以基于參考向量引導(dǎo)的進(jìn)化算法[22](reference vector guided evolutionary algorithm,RVEA)為底層進(jìn)化算法。K-RVEA首先初始化一組均勻分布的參考向量[22]，使用這組參考向量將目標(biāo)空間劃分為多個子空間，并使用參考向量在每個子空間中指導(dǎo)選擇新個體；然后利用初始種群中的所有個體對于每個適應(yīng)度函數(shù)訓(xùn)練Kriging模型，通過模擬二進(jìn)制交叉算子和多項式變異算子生成子代種群，利用Kriging模型預(yù)測子代個體的適應(yīng)度函數(shù)值。采用基于角度懲罰距離的選擇策略[22]選擇新種群。在管理Kriging模型時，利用Kriging模型給出近似目標(biāo)值中的不確定性信息、參考向量的分布以及個體的位置，既保證了多樣性和收斂性，又保證了二者的平衡，在多目標(biāo)進(jìn)化優(yōu)化問題中至關(guān)重要。

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

在進(jìn)化到最后一代時，會得到一個非支配解集，每一個解都同等重要，但是，實際應(yīng)用中通常只需要一個最優(yōu)解。聚類有效性指數(shù)I[23]通常被用來作為多目標(biāo)進(jìn)化的選解指標(biāo)，從非支配解集中選擇使I值最大的解作為最優(yōu)解。所提算法將超像素信息引入I指標(biāo)，構(gòu)造融合超像素信息的有效性指數(shù)SI從非支配解集中選擇出一個最優(yōu)解，其定義式為

(4)

(5)

(6)

其中：E1對于給定的數(shù)據(jù)集來說是一個常數(shù)。EC度量了類內(nèi)緊致性，其值越小越好；DC度量了兩個類之間的最大可分性，其值越大越好。因此，SI值越大越好。

2.5 算法流程

所提算法步驟具體如下。

步驟1對彩色圖像進(jìn)行差分進(jìn)化超像素分割，得到K個超像素區(qū)域，提取每個超像素區(qū)域的代表特征r={r1,r2,…,rK}。

步驟2設(shè)置種群規(guī)模N，最大迭代次數(shù)T，聚類數(shù)目C，用于更新Kriging模型的個體數(shù)目M，更新Kriging模型之前的固定迭代次數(shù)wmax，交叉概率p0和變異概率pm。

步驟3初始化參考向量、染色體編碼和初始化種群。

步驟4按照式(1)和式(3)計算初始種群的適應(yīng)度函數(shù)值，并使用初始種群中的個體及其適應(yīng)度函數(shù)訓(xùn)練Kriging模型，設(shè)置t=0，w=0。

步驟5利用進(jìn)化操作策略生成子代種群，利用Kriging模型預(yù)測目標(biāo)函數(shù)值，并將父代與子代合并。

步驟6采用基于角度懲罰距離的選擇策略選擇新種群，更新參考矢量，并設(shè)置w=w+1。

步驟7判斷是否需要更新Kriging模型。若w>wmax，則更新Kriging模型，并設(shè)置w=0，執(zhí)行步驟8；若否，直接執(zhí)行步驟8。

步驟8判斷是否達(dá)到最大迭代次數(shù)，若是，則迭代終止，得到最后一代非支配解集；否則，t=t+1，執(zhí)行步驟5。

步驟9利用式(4)選出最優(yōu)個體，得到最優(yōu)的聚類中心。

步驟10根據(jù)最優(yōu)聚類中心，對每個超像素區(qū)域進(jìn)行標(biāo)簽分配進(jìn)而獲得圖像中所有像素的標(biāo)簽，輸出圖像分割結(jié)果。

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

3.1 實驗設(shè)置及說明

為了驗證所提算法的分割性能，采用多幅Berkeley圖像[24]和Weizmann圖像[25]進(jìn)行實驗。以K-RVEA為進(jìn)化策略，以MOVGA的兩個目標(biāo)函數(shù)為適應(yīng)度函數(shù)，構(gòu)造KRVEA-MOVGA。分別對比FCM算法[5]、KFCM算法[6]、MOVGA[8]、KRVEA-MOVGA和所提算法的分割準(zhǔn)確率。實驗均在CPU為Intel(R) Core(TM) i5-6 500，內(nèi)存為8 GB，系統(tǒng)類型為64位操作系統(tǒng)配置的臺式機上運行，使用仿真軟件為Matlab 2018a。

所有算法的模糊指數(shù)均設(shè)置為2；最大迭代次數(shù)均設(shè)置為100；FCM算法、KFCM算法、KRVEA-MOVGA及所提算法的聚類數(shù)目均是根據(jù)人工分割的標(biāo)準(zhǔn)圖提前給定，MOVGA的聚類數(shù)目自適應(yīng)確定，其最大值設(shè)置為10；FCM算法和KFCM算法的結(jié)束閾值設(shè)置為10-5；MOVGA、KRVEA-MOVGA及所提算法的種群規(guī)模均設(shè)置為50，交叉概率設(shè)置為0.9，變異概率設(shè)置為0.1；所提算法的超像素數(shù)目設(shè)置為500。

3.2 Berkeley圖像分割實驗

5種算法在12幅Berkeley圖像上的分割準(zhǔn)確率如表1所示。可以看出，所提算法在大多數(shù)情況下，相較于其他4種算法能取得更好的分割結(jié)果。例如，對于圖像#3063，所提算法的圖像分割準(zhǔn)確率達(dá)到0.993 8，比FCM算法、KFCM算法、MOVGA和KRVEA-MOVGA分別提高了0.264 7、0.433 0、0.346 1和0.001 0。

表1 5種算法對Berkeley圖像的分割準(zhǔn)確率

MOVGA、KRVEA-MOVGA和所提算法在12幅Berkeley圖像平均運行時間分別為628 s、46 s和32 s，因此，與其他多目標(biāo)進(jìn)化聚類算法相比，所提算法不僅提高了圖像分割效果，同時也提高了時間效率。

為了檢驗所提算法在Berkeley圖像的視覺分割效果，圖1-圖3分別給出了圖像#3063、#24063和#238011在所有算法上的分割結(jié)果。從圖1中可以看出，F(xiàn)CM算法和KFCM算法的結(jié)果有較多錯分，MOVGA的結(jié)果中，天空背景分割效果不好，而所提算法相較于KRVEA-MOVGA，分割效果更好。從圖3中可以看出， FCM算法和KFCM算法都有錯分，所提算法相較于其他算法，展示出了更好的分割效果。

3.3 Weizmann圖像分割實驗

5種算法在12幅Weizmann圖像上的分割準(zhǔn)確率如表2所示?？梢钥闯?，所提算法在大多數(shù)圖像上的分割性能是所有算法中最好的。例如，對于圖像#leafpav，所提算法的圖像分割準(zhǔn)確率達(dá)到0.987 5，比FCM算法、KFCM算法、MOVGA和KRVEA-MOVGA的準(zhǔn)確率分別提高了0.015、0.012 4、0.452 4和0.004 5。

表2 5種算法對Weizmann圖像的分割準(zhǔn)確率

續(xù)表2 5種算法對Weizmann圖像的分割準(zhǔn)確率

MOVGA、MOVGA和所提算法在12幅Weizmann圖像平均運行時間分別為301 s、36 s和32 s，因此，與其他多目標(biāo)進(jìn)化聚類算法相比，所提算法不僅提高了圖像分割效果，同時也提高了時間效率。

為了檢驗所提算法在Weizmann圖像的視覺分割效果，圖4和圖5分別給出了圖像europe_holiday_484和beltaine_4_bg_050502在所有算法上的分割結(jié)果。從圖5可以看出，F(xiàn)CM算法、KFCM算法和MOVGA的結(jié)果有較多錯分，沒有將背景與目標(biāo)分離，與KRVEA-MOVGA相比，所提算法的圖像分割效果更好。

圖4 europe_holiday_484分割結(jié)果

圖5 beltaine_4_bg_050502分割結(jié)果

4 結(jié)語

超像素驅(qū)動的代理輔助多目標(biāo)聚類圖像分割算法先對彩色圖像進(jìn)行超像素分割得到超像素區(qū)域，然后提取每個超像素區(qū)域的代表特征。設(shè)計融合超像素信息的適應(yīng)度函數(shù)和最優(yōu)解評價指標(biāo)，基于代理輔助參考向量引導(dǎo)進(jìn)行多目標(biāo)進(jìn)化聚類。實驗結(jié)果表明，相比于FCM算法、KFCM算法、MOVGA和KRVEA-MOVGA，該算法能夠取得較好的圖像分割結(jié)果，同時也提高了時間效率。