一種改進(jìn)的核可能性C?均值聚類(lèi)圖像分割算法

梁丹 于海燕 范九倫 雒僖

摘? 要： 可能性C?均值聚類(lèi)（PCM）算法比傳統(tǒng)模糊C?均值聚類(lèi)算法具有更好的魯棒性，但其應(yīng)用于圖像分割時(shí)沒(méi)有充分考慮圖像的局部空間信息。基于PCM算法，提出一種核空間與自適應(yīng)中值濾波相結(jié)合的改進(jìn)算法。算法利用自適應(yīng)中值濾波獲得像素的局部空間信息，并由此生成一種新的模糊因子加入到目標(biāo)函數(shù)中，然后在核空間中對(duì)目標(biāo)函數(shù)進(jìn)行優(yōu)化求解，得到最優(yōu)聚類(lèi)中心和隸屬度。由實(shí)驗(yàn)結(jié)果可知，所提算法對(duì)被高椒鹽噪聲污染的圖像具有較高的準(zhǔn)確性和魯棒性。

關(guān)鍵詞： 可能性C?均值聚類(lèi); 目標(biāo)函數(shù)求解; 自適應(yīng)中值濾波; 局部空間信息; 圖像分割; 實(shí)驗(yàn)分析

中圖分類(lèi)號(hào)： TN911.73?34; TP391? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼： A? ? ? ? ? ? ? ? ? 文章編號(hào)： 1004?373X（2020）05?0046?05

An improved kernel possibilistic C?means clustering algorithm for image segmentation

LIANG Dan1， 2， 3， YU Haiyan1， 2， 3， FAN Jiulun1， 2， 3， LUO Xi1， 2， 3

（1. School of Communication and Information Engineering， Xian University Posts and Telecommunications， Xian 710121， China;

2. Key Laboratory of Electronic Information Application Technology for Investigation， Ministry of Public Security， Xian 710121， China;

3. Shaanxi International Joint Research Center for Wireless Communication and Information Processing， Xian 710121， China）

Abstract： The possibilistic C?means （PCM） clustering algorithm has better robustness than traditional fuzzy C?means clustering algorithm， but it fails to fully consider the local spatial information of image when it is applied to image segmentation. In view of this， an improved algorithm combining kernel space and adaptive median filtering is proposed based on the PCM algorithm. In the algorithm， the adaptive median filtering is used to obtain the local spatial information of pixel， with which a new fuzzy factor is generated and added to an objective function， and then， the objective function is optimized and solved in the kernel space to obtain the optimal cluster center and the membership degree. The experimental results show that the proposed algorithm has high accuracy and robustness for images contaminated by high salt?and?pepper noise.

Keywords： possibilistic C?means clustering; objective function solution; adaptive median filtering; local spatial information; image segmentation; experiment analysis

0? 引? 言

圖像分割是圖像處理領(lǐng)域中一項(xiàng)重要的研究?jī)?nèi)容，它將圖像分為不同的區(qū)域，這些區(qū)域具有相同的特點(diǎn)，如灰度級(jí)、顏色、色調(diào)、紋理等。圖像分割技術(shù)在目標(biāo)識(shí)別與跟蹤、圖像檢索以及人臉識(shí)別等領(lǐng)域具有重要價(jià)值。模糊聚類(lèi)算法在圖像分割[1?6]中應(yīng)用最為廣泛，其中，模糊C?均值聚類(lèi)（FCM）算法[7?8]在圖像分割中應(yīng)用最流行，它是一個(gè)著名的非監(jiān)督模糊聚類(lèi)算法。FCM算法存在對(duì)噪聲敏感的缺點(diǎn)，因?yàn)橛屑s束條件隸屬度值歸一化的限制，使得數(shù)據(jù)點(diǎn)中噪聲點(diǎn)和非噪聲點(diǎn)對(duì)聚類(lèi)具有相同的影響力，導(dǎo)致噪聲點(diǎn)具有較大的隸屬度而被劃分到某一類(lèi)中。為此，學(xué)者們?cè)贔CM算法的基礎(chǔ)上對(duì)隸屬度提出了很多改進(jìn)算法[9?12]，其中，可能性C?均值聚類(lèi)（PCM）算法[13]放棄了對(duì)隸屬度歸一化的限制，使得噪聲數(shù)據(jù)具有較小的隸屬度值，提高了算法的魯棒性。FCM算法和PCM算法主要適合對(duì)團(tuán)狀凸數(shù)據(jù)聚類(lèi)，對(duì)那些非凸數(shù)據(jù)聚類(lèi)時(shí)，其聚類(lèi)性能并不理想，為此文獻(xiàn)[14?15]提出了基于核空間的模糊C?均值聚類(lèi)（KFCM）算法和基于核的可能性聚類(lèi)（KPCM）算法，它通過(guò)核函數(shù)將樣本數(shù)據(jù)通過(guò)非線性映射至高維特征空間，對(duì)非凸數(shù)據(jù)也能夠取得較理想的聚類(lèi)結(jié)果，改善了樣本的可分性，提高了算法的聚類(lèi)性能。

然而，當(dāng)圖像中含有大量噪聲時(shí)，PCM算法無(wú)法得到理想的分割效果，因?yàn)樗雎粤藞D像的空間位置信息。目前學(xué)者們已經(jīng)在傳統(tǒng)的FCM算法中加入空間信息[16?18]，提出了大量基于FCM算法的改進(jìn)算法，改善了圖像的分割結(jié)果。但由于FCM算法對(duì)噪聲敏感，因此改進(jìn)算法也存在對(duì)噪聲敏感的缺點(diǎn)。PCM算法在一定程度上對(duì)噪聲具有魯棒性，結(jié)合空間信息的PCM算法能夠進(jìn)一步提高圖像的分割結(jié)果。

針對(duì)被高椒鹽噪聲污染的圖像，利用自適應(yīng)中值濾波算法能夠根據(jù)噪聲大小自適應(yīng)調(diào)節(jié)濾波半徑的特點(diǎn)，本文提出一種改進(jìn)的核可能性C?均值聚類(lèi)圖像分割算法，提高了算法的聚類(lèi)性能和有效性，進(jìn)一步解決了在強(qiáng)噪聲干擾下圖像的聚類(lèi)分割效果不理想的問(wèn)題。仿真實(shí)驗(yàn)結(jié)果表明了本文算法的有效性。

1? 可能性C?均值聚類(lèi)算法

設(shè)數(shù)據(jù)集[X]由[n]個(gè)[p]維的數(shù)據(jù)組成，數(shù)據(jù)集可表示為[X={x1，x2，…，xn}∈Rn×p]，可能性C?均值聚類(lèi)算法是一種迭代聚類(lèi)方法，通過(guò)最小化目標(biāo)函數(shù)對(duì)樣本數(shù)據(jù)進(jìn)行分類(lèi)，其目標(biāo)函數(shù)[Jm]可表示為：

[Jm（T，V）=i=1nk=1ctmkixi-vk2+k=1cηki=1n（1-tki）m] （1）

滿足約束條件：

[i=1ntki>0，k=1，2，…，c， 0≤tki≤1] （2）

式中：[n]表示數(shù)據(jù)樣本的個(gè)數(shù);[c]表示聚類(lèi)個(gè)數(shù);[m]表示模糊加權(quán)指數(shù)，常取[m=2];[T=[tik]]（[i=1，2，…，n];[k=1，2，…，c]）為隸屬度矩陣，表示第[i]個(gè)樣本對(duì)第[k]個(gè)聚類(lèi)中心的隸屬程度;[V=[vk]]（[k=1，2，…，c]）表示聚類(lèi)中心集合;[ηk]為一正數(shù)，一般取值為：

[ηk=Ki=1ntmkixi-vk2i=1ntmki] （3）

式中[K]為一正整數(shù)，通常取[K]=1。

隸屬度[tki]和聚類(lèi)中心[vk]的迭代公式為：

[tki=1+xi-vk2ηk-1m-1] （4）

[vk=i=1ntmkixii=1ntmki]? （5）

通過(guò)反復(fù)迭代式（4）～式（5），使得PCM算法收斂。

2? 圖像分割算法

2.1? 自適應(yīng)中值濾波算法

自適應(yīng)中值濾波算法[19]主要有三個(gè)目的：去除脈沖噪聲;平滑其他非脈沖噪聲;保護(hù)圖像邊緣信息。它在濾波時(shí)使用一個(gè)矩形區(qū)域的窗口[Sxy]，能夠根據(jù)噪聲強(qiáng)弱改變?yōu)V波窗半徑的大小。當(dāng)判斷濾波窗中心像素是噪聲時(shí)，自適應(yīng)中值濾波器為常規(guī)中值濾波器，即用中值代替該值;當(dāng)判斷濾波窗中心像素不是噪聲時(shí)，則不改變其當(dāng)前像素值。自適應(yīng)中值濾波器能夠得到比常規(guī)中值濾波器更好的濾波效果，因?yàn)樗鼘?duì)噪聲概率更大的脈沖噪聲進(jìn)行平滑的同時(shí)還能更好地保持圖像細(xì)節(jié)。

自適應(yīng)中值濾波算法由兩部分組成：第一層（Leve1A）和第二層（Leve1B）。

第一層（Leve1A）：

[A1=Zmed-Zmin] （6）

[A2=Zmed-Zmax] （7）

如果[A1]>0并且[A2]<0，則轉(zhuǎn)到Leve1B，否則增加濾波窗[Sxy]的尺寸。如果濾波窗[Sxy]的大小達(dá)到[Smax]，則重復(fù)執(zhí)行Leve1A，否則把[Sxy]作為輸出。

第二層（Leve1B）：

[B1=Zxy-Zmin] （8）

[B2=Zxy-Zmax] （9）

如果[B1]>0并且[B2]<0，則把[Zxy]作為輸出值，否則把[Zmed]作為輸出值。

式中：[Zmin]表示在[Sxy]濾波窗內(nèi)灰度的最小值;[Zmax]表示在濾波窗[Sxy]內(nèi)灰度的最大值;[Zmed]表示在[Sxy]濾波窗內(nèi)灰度的中值;[Zxy]表示坐標(biāo)[（x，y）]處的灰度值;[Smax]表示[Sxy]所允許的最大窗口尺寸。

2.2? 一種改進(jìn)的核可能性C?均值聚類(lèi)圖像分割算法

FLICM[17]算法在目標(biāo)函數(shù)中引入無(wú)參數(shù)模糊因子[Gki]，即引入局部空間信息，控制圖像中噪聲和細(xì)節(jié)的平衡，但是對(duì)受高強(qiáng)度噪聲污染的圖像無(wú)法達(dá)到理想分割的效果。在本文算法中，用核空間歐氏距離代替PCM中樣本與聚類(lèi)中心之間的歐氏距離，引入自適應(yīng)中值濾波算法對(duì)圖像進(jìn)行濾波，并將模糊因子中的局部鄰域值替換為自適應(yīng)中值濾波的像素值，以更好地利用鄰域像素。

新的目標(biāo)函數(shù)為：

[Jm=i=1nk=1ctmkiΦ（xi）-Φ（vk）2+G′ki+ηk=1ci=1n（1-tki）m]? （10）

滿足約束條件：

[i=1ntki>0， ? ? k=1，2，…，c; 0≤tki≤1] （11）

式中：[n]表示一幅圖像的像素個(gè)數(shù);[c]表示圖像的聚類(lèi)數(shù)目;[tki]表示第[i]個(gè)像素對(duì)[k]個(gè)聚類(lèi)中心的隸屬度值;參數(shù)[m]表示隸屬度的加權(quán)指數(shù)，決定聚類(lèi)結(jié)果的模糊程度，[m∈1，+∞]，通常[m]=2;[xi]表示原始圖像的像素;[vk]表示聚類(lèi)中心;[Φ]表示高維空間的非線性映射;[G′ki]表示模糊因子;[η]為一正數(shù)。

其中，調(diào)整模糊因子為：

[G′ki=j∈Nii≠j11+dij（1-tkj）mΦ（xj）-Φ（vk）2] （12）

式中：[xj]表示經(jīng)過(guò)自適應(yīng)中值濾波后的像素;[Ni]表示中心像素為[i]的鄰域窗口;[dij]表示中心像素[i]和其所對(duì)應(yīng)鄰域窗口中的像素[j]之間的歐氏距離;[tkj]表示隸屬度。

核空間平方歐氏距離為：

[Φ（xi）-Φ（vk）2=K（xi，xi）+K（vk，vk）-2K（xi，vk）] （13）

當(dāng)取高斯核函數(shù)時(shí)，[K（x，x）=1，K（x，y）=exp-x-y2σ2]，則：

[Φ（xi）-Φ（vk）2=21-K（xi，vk）] （14）

式中[σ]表示帶寬，表示為：

[σ=1N-1i=1N（di-d）12]? （15）

式中：[d]表示像素[xi]和像素均值[x]之間的距離，[d=xi-x]，[d]的表達(dá)式為：

[d=i=1NdiN] （16）

將高斯核函數(shù)公式代入目標(biāo)函數(shù)，可將目標(biāo)函數(shù)簡(jiǎn)化為：

[Jm（T，V）=i=1nk=1ctmki1-K（xi，vk）+G′ki+k=1cηi=1n（1-tki）m]? （17）

式中：

[G′ki=j∈Nii≠j11+dij（1-tkj）m（1-K（xj，vk））] （18）

隸屬度[tki]和聚類(lèi)中心[vk]的表達(dá)式為：

[tki=1+2（1-K（xi，vk））+G′kiη-1m-1]? ?（19）

[vk=i=1ntmki（K（xi，vk））xi+A1i=1ntmki（K（xi，vk））+A2]? （20）

式中：

[A1=i=1ntmkij∈Nii≠j（1-tkj）m（K（xj，vk））xj11+dij] （21）

[A2=i=1ntmkij∈Nii≠j（1-tkj）m（K（xj，vk））11+dij] （22）

本文算法步驟為：

Step1：設(shè)置聚類(lèi)類(lèi)別數(shù)[c]，隸屬度加權(quán)指數(shù)[m]，迭代誤差限[ε]，最大迭代次數(shù)[T]，初始迭代次數(shù)[t]=1。

Step2：通過(guò)自適應(yīng)中值濾波算法對(duì)圖像進(jìn)行平滑處理，得到濾波后的圖像[I1]。

Step3：運(yùn)行FCM算法，把FCM得到的隸屬度劃分矩陣作為本文算法的初始隸屬度矩陣[t（0）ki]。

Step4：通過(guò)式（20），更新聚類(lèi)中心[v（t）k]。

Step5：通過(guò)式（21），更新隸屬度[t（t）ki]。

Step6：當(dāng)[v（t）k-v（t+1）k<ε]或者[T>Tmax]時(shí)停止迭代，輸出隸屬度[t（t）ki]和聚類(lèi)中心[v（t）k];否則，返回Step4進(jìn)行下一次迭代。

Step7：通過(guò)對(duì)最終輸出的隸屬度[t（t）ki]和聚類(lèi)中心[v（t）k]產(chǎn)生分割圖像[I2]。

3? 實(shí)驗(yàn)結(jié)果及分析

通過(guò)Matlab仿真軟件來(lái)驗(yàn)證本文算法對(duì)人工合成圖像和自然圖像的有效性及魯棒性，并用PCM[13]，KFCM_S1[16]，KFCM_S2[16]，ARKFCM[18]，F(xiàn)LICM[17]算法作為比較算法。對(duì)所有的比較算法，設(shè)置共同參數(shù)為[m=2]，[ε=]0.000 01，局部鄰域窗口為3×3。對(duì)于KFCM_S1和KFCM_S2算法，取[a=2]。對(duì)于本文算法，設(shè)置自適應(yīng)中值濾波的最大濾波半徑為10，[η=]0.05。

實(shí)驗(yàn)一：對(duì)人工圖像（synthetical，200×200）添加強(qiáng)度為0.2的椒鹽噪聲，采用6種算法對(duì)其進(jìn)行分割，分割結(jié)果如圖1所示。

從圖1中可以看出，PCM算法的分割結(jié)果最不理想，其中包含的噪聲點(diǎn)最多，這是因?yàn)镻CM算法忽略了圖像中像素的空間信息，導(dǎo)致算法對(duì)噪聲敏感。KFCM_S1算法、KFCM_S2算法引入了均值濾波和中值濾波，結(jié)合了圖像像素的空間信息，并轉(zhuǎn)化到核空間。相比而言，對(duì)于含椒鹽噪聲的圖像，KFCM_S2比KFCM_S1的分割效果更好，但分割結(jié)果中仍含有噪聲，分割效果欠佳。ARKFCM引入正則化參數(shù)控制空間信息，同樣轉(zhuǎn)化到核空間，但對(duì)被噪聲影響嚴(yán)重的圖像分割效果較差。FLICM算法結(jié)合了圖像局部信息的灰度信息和空間信息，能夠更多地利用圖像中像素的空間信息，但是仍對(duì)含噪強(qiáng)度較大的圖像魯棒性較差，因此該算法的分割效果仍然不理想。本文算法通過(guò)引入自適應(yīng)中值濾波，并結(jié)合濾波后圖像像素的局部空間信息，同時(shí)使用具有魯棒性的核函數(shù)，因此得到了理想的分割效果。

采用分割精度[17]（Segmentation Accuracy，SA）作為算法性能的客觀評(píng)價(jià)指標(biāo)，可表示為：

[SA=i=1cAi?Cij=1cCj]? ?（23）

式中：[c]表示聚類(lèi)個(gè)數(shù);[Ai]表示由分割算法得到屬于第[i]類(lèi)的像素點(diǎn)集;[Ci]表示在標(biāo)準(zhǔn)圖像中屬于第[i]類(lèi)的點(diǎn)集;SA表示正確分類(lèi)的像素?cái)?shù)占圖像像素總數(shù)的比重。

表1給出了隨著噪聲強(qiáng)度增強(qiáng)，6種不同算法分割結(jié)果的分割精度（SA）值。由表1可得，隨著噪聲強(qiáng)度的增大，其余5種算法分割精度逐步降低，但本文算法仍然能夠保持較高的分割精度。

實(shí)驗(yàn)二： 圖像（#42049 321×481）添加強(qiáng)度為0.1的椒鹽噪聲和均值為0，方差為0.001的高斯噪聲，使用6種算法分別對(duì)其進(jìn)行分割，結(jié)果如圖2所示。

由圖2可以看出，PCM，KFCM_S1，KFCM_S2，ARKFCM和FLICM算法的分割結(jié)果中均含有不同程度大小的噪聲，對(duì)噪聲的抑制能力不強(qiáng)，算法的魯棒性較差，因此這5種算法對(duì)圖像#42049的分割效果不佳。而本文算法對(duì)噪聲有一定的抑制能力，具有更好的魯棒性，得到了較好的分割效果。

表2為對(duì)圖像#42049分別添加不同噪聲強(qiáng)度的混合噪聲，Mixed1，Mixed2，Mixed3分別表示均值為0，方差為0.001和強(qiáng)度為0.1，0.2，0.3的椒鹽噪聲，并采用峰值信噪比[20]（Peak Signal?to?Noise Ratio，PSNR）作為客觀評(píng)價(jià)指標(biāo)。由表2可得，隨著噪聲強(qiáng)度的增大，本文算法相比于其他5種算法具有較高的峰值信噪比，進(jìn)一步證明了本文算法的魯棒性。

實(shí)驗(yàn)三：圖像cameraman（256×256）添加強(qiáng)度為0.2的椒鹽噪聲，使用6種算法分別對(duì)其進(jìn)行分割，結(jié)果如圖3所示。

由圖3和表3可明顯看出，將本文算法與PCM，KFCM_S1，KFCM_S2，F(xiàn)LICM，ARKFCM算法作比較，可明顯得出本文算法具有較好的分割結(jié)果，且隨著噪聲強(qiáng)度的增大，本文算法仍能夠保持較高的魯棒性。

4? 結(jié)? 語(yǔ)

本文提出一種改進(jìn)的核可能性均值聚類(lèi)圖像分割算法。算法通過(guò)利用模糊因子和自適應(yīng)中值濾波獲取圖像的局部空間信息，并采用核空間歐氏距離代替?zhèn)鹘y(tǒng)的歐氏距離作為相似性度量，最后實(shí)現(xiàn)對(duì)加入椒鹽噪聲圖像的分割。通過(guò)仿真實(shí)驗(yàn)表明，本文算法相比于PCM，KFCM_S1，KFCM_S2，F(xiàn)LICM，ARKFCM算法具有更好的分割效果和魯棒性。

參考文獻(xiàn)

[1] BAI X， CHEN Z， ZHANG Y， et al. Infrared ship target segmentation based on spatial information improved FCM [J]. IEEE transactions on cybernetics， 2016， 46（12）： 3259?3271.

[2] WAN L， ZHANG T， XIANG Y， et al. A robust fuzzy C?means algorithm based on Bayesian nonlocal spatial information for SAR image segmentation [J]. IEEE journal of selected topics in applied earth observations and remote sensing， 2018， 11（3）： 896?906.

[3] NGATCHOU A， BITJOKA L， MFOUMOU E， et al. Robust and fast segmentation based on fuzzy clustering combined with unsupervised histogram analysis [J]. IEEE intelligent systems， 2017， 32（5）： 6?13.

[4] DESPOTOVIC I， VANSTEENKISTE E， PHILIPS W. Spatially coherent fuzzy clustering for accurate and noise?robust image segmentation [J]. IEEE signal processing letters， 2013， 20（4）： 295?298.

[5] CAO H， DENG H， WANG Y. Segmentation of M?FISH images for improved classification of chromosomes with an adaptive fuzzy C?means clustering algorithm [J]. IEEE transactions on fuzzy systems， 2012， 20（1）： 1?8.

[6] MAT ISA N A， SALAMAH S A， NGAH U K. Adaptive fuzzy moving K?means clustering algorithm for image segmentation [J]. IEEE transactions on consumer electronics， 2009， 55（4）： 2145?2153.

[7] BEZDEK J C. Pattern recognition with fuzzy objective function algorithms [M]. New York： Plenum Press， 1981.

[8] LIU G， ZHANG Y， WANG A. Incorporating adaptive local information into fuzzy clustering for image segmentation [J]. IEEE transactions on image processing， 2015， 24（11）： 3990?4000.

[9] ZHU L， CHUNG F， WANG S. Generalized fuzzy C?means clustering algorithm with improved fuzzy partitions [J]. IEEE transactions on systems， man， and cybernetics， Part B （Cybernetics）， 2009， 39（3）： 578?591.

[10] 文傳軍，詹永照.基于樣本模糊隸屬度歸[n]化約束的松弛模糊C均值聚類(lèi)算法[J].科學(xué)技術(shù)與工程，2017，17（36）：96?104.

[11] 胡嘉駿，侯麗麗，王志剛，等.基于模糊C均值隸屬度約束的圖像分割算法[J].計(jì)算機(jī)應(yīng)用，2016，36（z1）：126?129.

[12] GHARIEB R R， GENDY G， ABDELFATTAH A， et al. Adaptive local data and membership based KL divergence incorporating C?means algorithm for fuzzy image segmentation [J]. Applied soft computing， 2017， 59： 143?152.

[13] KRISHNAPURAM R， KELLER J M. A possibilistic approach to clustering [J]. IEEE transactions on fuzzy systems， 1993， 1（2）： 98?110.

[14] ZHANG D Q， CHEN S C. A novel kernelized fuzzy C?means algorithm with application in medical image segmentation [J]. Artificial intelligence in medicine， 2004， 34（4）： 1907?1916.

[15] 呂佳，熊忠陽(yáng).基于核的可能性聚類(lèi)算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2006，27（13）：2466?2468.

[16] CHEN S C， ZHANG D Q. Robust image segmentation using FCM with spatial constraints based on new kernel?induced distance measure [J]. IEEE transactions on systems， man， and cybernetics， Part B （Cybernetics）， 2004， 34（4）： 1907?1916.

[17] KRINIDIS S， CHATZIS V. A robust fuzzy local information C?means clustering algorithm [J]. IEEE transactions on image processing， 2010， 19（5）： 1328?1337.

[18] FANG R， LU Y N， LIU X N， et al. Segmentation of brain MR images using an adaptively regularized kernel FCM algorithm with spatial constraints [C]// 2017 10th International Congress on Image and Signal Processing， Biomedical Engineering and Informatics （CISP?BMEI）. Shanghai， China： IEEE， 2017： 1?6.

[19] 岡薩雷斯.數(shù)字圖像處理[M].阮秋琦，阮宇智，譯.北京：電子工業(yè)出版社，2006.

[20] 何晶，吳成茂.核空間自適應(yīng)非局部均值魯棒分割算法[J].光電子?激光，2017，28（8）：910?917.