基于半監督信息的截集式可能性C-均值聚類算法

范九倫 高夢飛于海燕 陳斌斌

(西安郵電大學通信與信息工程學院 西安 710121)

(西安郵電大學電子信息勘驗應用技術公安部重點實驗室 西安 710121)

1 引言

圖像分割[1]是計算機視覺領域中的重要技術，是后續進行圖像分析與識別的基礎，其目的是從圖像中將感興趣的區域與其他部分進行分離并提取出來。常規的圖像分割方法包括：基于閾值的分割方法[2]、基于區域的分割方法[3]、基于邊緣的分割方法[4]、基于聚類的分割方法[5]等。作為聚類圖像分割的常用方法，模糊C-均值(Fuzzy C-Means,FCM)[6]對噪聲點和奇異點非常敏感。這主要是緣于該算法對隸屬度有約束條件：要求各個樣本點到所有類的隸屬度之和必須為1。

為解決FCM聚類算法對噪聲敏感的問題，Krishnapuram等人[7]提出可能性C-均值(Possibilistic C-Means,PCM)聚類算法，PCM聚類算法放棄了FCM聚類算法中隸屬度和為1的約束條件，能明顯改善FCM聚類算法的噪聲敏感問題。然而PCM聚類算法完全釋放了類間關系，只有PCM目標函數在全體聚類中心重合時才能獲得真正的全局最優解，導致PCM聚類算法非常不穩定，容易出現聚類中心重合的問題[8,9]。除此之外，PCM聚類算法還存在對初始化敏感、參數設置敏感等一系列問題。為解決這些問題，學者對PCM聚類算法進行了一些改進，Pal等人[10]提出了可能性-模糊混合聚類算法，以克服聚類中心重合現象。Memon等人[11]將核PCM聚類算法和FCM聚類算法相結合，提出了結合局部信息的核PCM聚類算法，該算法提高了PCM對噪聲的魯棒性。

針對PCM的聚類中心重合問題，從隸屬度的修改入手，文獻[12]提出了截集式可能性C-均值(Cutset-type Possibilistic C-Means,C-PCM)聚類算法，C-PCM聚類算法將截集門限引入PCM聚類算法中，并選擇部分樣本的隸屬度進行修改，從而引入類間關系，該算法在一定程度上能夠克服PCM的聚類中心重合問題。C-PCM聚類算法在對目標大小相近的數據聚類的時候，能夠找到正確的聚類中心，但是對小目標數據進行聚類時仍然存在聚類中心重合問題。具體來說，小目標的聚類中心會嚴重偏離到大目標的數據區域，從而影響聚類效果。

半監督聚類[13–15]使用半監督信息來指導聚類過程，一定程度上改善了聚類效果和運行效率。2009年，Yasunori等人[13]將監督隸屬度引入FCM聚類算法中，提出了半監督模糊C-均值(Semi-Supervised Fuzzy C-Means,SS-FCM)聚類算法。2012年，Yin等人[14]提出將監督隸屬度引入熵正則化FCM聚類算法中，提出了熵正則化半監督模糊聚類算法，避免了模糊因子人為確定的問題。本文將半監督引入C-PCM聚類算法中，提出半監督截集式可能性C-均值(Semi-Supervised Cutset-type Possibilistic C-Means,SS-C-PCM)聚類算法，通過將標簽數據引入目標函數中，防止C-PCM聚類算法的中心偏移問題，從而改善了小目標數據的聚類效果。

超像素最早由Ren等人[16]提出，它由一系列位置相鄰且顏色、亮度、紋理等特征相似的像素點組成子區域，這些子區域保留了進一步進行圖像分割的有效信息，并且不會破壞圖像中物體的邊界信息。同時超像素圖像的子區域內的像素具有相近的圖像特征，針對小區域進行處理可以大大減少計算量，提高分割效率[17–20]。鑒于此，本文將超像素子區域信息以彩色直方圖[21]的形式引入SS-C-PCM聚類算法的目標函數中，進一步提出了一種基于差分進化超像素的半監督截集式可能性C-均值

(differential evolutionary superpixel-based Semi-Supervised Cutset-type Possibilistic C-Means,desSS-C-PCM)聚類算法，提高了聚類算法的運行效率。

2 可能性C-均值聚類算法

為了改善FCM聚類算法的噪聲敏感性，Krishnapuram等人[7]提出了PCM聚類算法，該算法通過改變FCM聚類算法的約束條件進而減少噪聲對聚類的影響。PCM算法的目標函數為

PCM聚類算法通過釋放隸屬度和為1的約束條件，提高了聚類算法對噪聲的魯棒性。但是PCM對隸屬度的約束過于寬泛，使得PCM缺乏類間關系，目標函數(式(1))在全體聚類中心重合時才能獲得真正的全局最優解，最終導致算法容易產生聚類中心重合問題[8,9]，也稱為一致性聚類問題。此外PCM聚類算法存在對初始化、參數設置敏感的問題。

3 截集式可能性C-均值聚類算法

為了克服PCM最突出的問題—中心重合問題，Yu等人[12]將截集概念引入PCM聚類算法中，通過截集門限選擇部分樣本點并修改其典型值，進而引入類間關系，從而提出了截集式可能性C-均值(C-PCM)聚類算法，能夠在一定程度上克服PCM的聚類中心重合問題。C-PCM的目標函數為

典型值t k i和聚類中心vk的更新公式與PCM算法的更新公式相同，懲罰因子η為提前設置，在算法中取固定值。其中，截集采用基于陰影集的理論[22,23]自適應選取。C-PCM聚類算法通過將樣本點的非獲勝典型值進行修改，進而增大獲勝典型值與非獲勝典型值的差值，從而引入類間關系。該算法在對各類大小相近的數據進行聚類時，能夠很好地克服PCM的聚類中心重合問題。但是在各類樣本容量大小相差較大，即包含小目標的數據進行聚類時，仍然存在聚類中心偏移、部分中心重合問題。

4 半監督模糊C-均值聚類

當樣本不平衡時，C-PCM算法對包含小目標的數據進行聚類時，存在聚類效果不理想的問題。具體來說如果數據集中存在一個類的樣本容量很大，而另一類的樣本容量很小，那么樣本容量較小的類中心很容易就偏移到樣本容量大的數據區域中。針對這一問題，本文借鑒Yasunori等人[13]提出的半監督思想，將監督隸屬度引入C-PCM聚類算法中。Yasunori等人[13]提出半監督模糊C-均值(Semi-Supervised Fuzzy C-Means,SS-FCM)聚類算法，其目標函數為

5 本文算法

SS-FCM聚類算法利用已知類別標簽的少量樣本指導模糊聚類過程，一定程度上提高了運行效率。本文引入該算法的思想，將監督信息融入CPCM聚類算法的目標函數中，提出半監督截集式可能性C-均值(Semi-Supervised Cutset-type Possibilistic C-Means,SS-C-PCM)聚類算法；同時將SS-C-PCM聚類算法應用到彩色圖像中：為了降低計算復雜度，提高分割效果，利用差分進化超像素算法對圖像進行預處理的同時引入空間信息，進而提出了一種基于差分進化超像素的半監督截集式可能性C-均值聚類算法desSS-C-PCM。

5.1 半監督截集式可能性C-均值聚類算法

針對C-PCM聚類算法對包含小目標的數據進行聚類時出現中心偏移、部分中心重合現象，本文借鑒半監督模糊C-均值聚類算法[13]的思想，將半監督信息引入C-PCM的目標函數中，利用已知類別標簽的少量樣本指導C-PCM聚類算法的聚類過程。半監督截集式可能性C-均值聚類算法的目標函數為

5.2 基于差分進化超像素的半監督截集式可能性C-均值聚類算法

傳統的聚類圖像分割算法是在像素層面進行聚類，其計算復雜度高，算法運行時間長，占用空間大。超像素圖像是一系列位置相鄰且顏色、亮度、紋理等特征相似的像素點組成的子區域，且超像素子區域的個數遠小于彩色圖像的像素數。差分進化超像素(Differential Evolutionary Superpixel,DES)算法是由Gong等人[19]在2018年提出的一種新的基于全局優化的進化超像素方法，相對于簡單線性迭代聚類超像素算法[20]，該算法可以更好地捕獲圖像的邊界信息，提高圖像的邊界依附性。為減少計算量，改善圖像的分割效果，本文將差分進化超像素(DES)算法獲取的超像素子區域信息引入本文的SS-C-PCM圖像分割算法中，并借鑒Lei等人[21]提出的彩色直方圖的方法重新設計目標函數，進而提出了一種基于差分進化超像素的半監督截集式可能性C-均值(differential evolutionary superpixel-based Semi-Supervised Cutset-type Possibilistic C-Means，desSS-C-PCM)聚類算法，該算法的目標函數為

基于差分進化超像素的半監督截集式可能性C-均值(desSS-C-PCM)聚類算法步驟如下，流程圖如圖1所示。

圖1 desSS-C-PCM算法流程圖

步驟1給定聚類數目c，超像素個數k，模糊因子m，懲罰因子η。設置最大循環次數Tmax和算法停止的閾值ε；

6 實驗結果分析

為了驗證本文所提SS-C-PCM和d esSS-CPCM算法有效性，本節采用人工合成數據集和Berkeley圖像[24]進行仿真實驗，采用的對比算法有FCM聚類算法、SS-FCM聚類算法、C-PCM聚類算法。實驗環境為MATLAB R2014a，參數設置分別為m=2，設置η為 20，最大迭代次數rmax=100，算法停止的閾值為ε=0.00001。

6.1 人工合成數據實驗

圖2顯示了各個算法對3類數據集的聚類結果，可以看出FCM,SS-FCM,C-PCM算法其中一類的中心發生嚴重偏移，而本文所提SS-C-PCM算法利用少量的監督信息來指導聚類過程，得到的中心只發生了輕微偏移。表1顯示了各個算法的中心偏移量。

表1 針對數據集X1600各個算法的中心偏移量以及迭代次數

圖2 針對數據集X 1600的聚類結果

6.2 Berkeley圖像對比實驗

對于圖3#124084，其標準分割應為3類：紅色花瓣為第1類，黃色花蕊為第2類，除花以外的背景歸為第3類。FCM算法在背景處理上出現了較多的錯分；C-PCM算法將花瓣和花蕊分割為一類，沒有成功地分割出花蕊，分割效果較差；SS-FCM算法雖然在FCM的基礎上加入了半監督，提高了該算法的運行效率，但是分割結果相對于FCM，并沒有得到提升；SS-C-PCM算法相對于C-PCM算法，分割效果有一定的改善；desSS-C-PCM算法雖然在一些細節上出現了分割錯誤，但是能較好地將花朵從背景中分割出來。

圖3 #124084分割結果圖

表2分別給出了FCM,C-PCM,SS-FCM,SSC-PCM算法以及desSS-C-PCM算法的分割準確率，從表2可以看出，FCM算法和C-PCM算法的分割準確率相對較低；SS-FCM算法在分割圖像#3063,#135069以及#238011時，分割準確率相對于FCM有比較明顯的提升，對于大部分圖像，SSFCM的分割準確率相對于FCM沒有明顯的改善；SS-C-PCM算法在C-PCM算法的基礎上加入了半監督，相對于C-PCM算法，SS-C-PCM算法在分割圖像#42044時，分割準確率下降了0.0114，在分割其余18張圖像時，SS-C-PCM算法的分割準確率都有所提高；desSS-C-PCM算法通過DES超像素獲取空間信息，并通過半監督信息來指導聚類過程，所以分割準確率有明顯的提高。

表2 各個算法的分割準確率對比

7 結束語

針對C-PCM算法在處理小目標數據時聚類中心嚴重偏移的問題，本文將半監督信息引入C-PCM算法，提出半監督截集式可能性C-均值(SS-CPCM)聚類算法。為了改善C-PCM算法對彩色圖像的分割效果以及運行效率，本文通過DES超像素算法獲取空間信息，將此空間信息引入SS-C-PCM算法中，提出基于DES超像素的半監督截集式可能性C均值(desSS-C-PCM)聚類算法，并將其用到彩色圖像分割。實驗結果表明，SS-C-PCM算法提高了C-PCM算法的運行效率以及分割準確率，desSSC-PCM算法在SS-C-PCM算法的基礎上進一步提高了分割準確率以及運行效率。下一步將研究本文算法在噪聲環境下對彩色圖像的分割效果。