基于二維直方圖的改進的PCM聚類分割方法

林愛英，賈芳，昝紅英

(1.河南農業大學理學院，河南 鄭州 450002；2.鄭州大學信息工程學院，河南 鄭州 450001)

圖像分割是把圖像分成各具特性的區域并提取出特定目標的技術和過程，圖像分割的效果直接決定了后續圖像分析、圖像理解和模式識別的性能，因此，圖像分割在計算機視覺和圖像識別中占有相當重要的地位.模糊C均值(FCM)聚類算法[1-3]是圖像分割領域研究最多的方法之一.然而，FCM算法的抗噪聲性能比較差，為此Krishinapuram和Keller提出了一種新的模糊聚類方法PCM[4](Possibilistic C-means，可能性C-均值)，該方法使得噪聲點在所有聚類中的隸屬度都很低，因此該算法對噪聲有很好的免疫性.本文中在充分研究PCM算法的基礎上，提出一種改進的PCM聚類新方法，并把該方法應用到圖像分割中.該改進方法對標準的PCM算法中的聚類中心進行修正，取而代之的是具有典型性的樣本模式替代標準PCM算法中的聚類中心.

另一方面，為了充分利用圖像像素的灰度信息和空間鄰域信息，提出一個利用二維直方圖和改進的PCM聚類相結合的方法對圖像進行分割.首先構造一個二維直方圖，然后利用改進的PCM聚類算法對二維直方圖中的點進行可能性聚類，最后根據各像素的隸屬度對圖像進行分割.本文中采用的二維直方圖中，同時考慮了各像素的灰度值分布和它們的鄰域像素的平均灰度值分布，使得在一維直方圖中物體和背景的分布區分不明顯的現象在二維直方圖中得到了較好的改善.通過對幾幅不同噪聲圖像的分割，結果表明所提出的方法是非常有效的.

1 改進的PCM聚類算法

(1)

約束條件的改變使每個聚類之間相互獨立，因此uij真正地表示了兼容度和可能值.

根據約束(1)，重新定義PCM聚類的目標函數：

(2)

其中，L=(β1，…，βC)表示C個聚類原型的集合，模糊C劃分矩陣U=[uij]是一個C×N矩陣，uij表示特征點xj在聚類βi中的隸屬度，N是集合中數據的個數，dij是xj與聚類原型βi之間的距離，m∈[1，∞)是模糊加權指數.改進后的目標函數Jm(L，U)通過增加一個懲罰項使有代表性的特征點的隸屬度盡可能高，而沒有代表性的特征點的隸屬度盡可能低.這就使得噪聲點的隸屬度變得很小，噪聲環境中的隸屬度幾乎與無噪聲情況一樣，這正是PCM聚類抗噪效果好的原因.

1.2改進的PCM聚類算法(IPCM) PCM所產生的聚類中心基本上都是重新生成的模式，所以在實際的引用中很難適用.為此，重新定義PCM的聚類中心，取而代之的是具有典型性的樣本模式，從而PCM算法轉化為一個樣本模式搜索算法，這種方法稱為改進的PCM聚類方法(IPCM).目的是選取樣本點作為聚類原型的中心，從而代替使用樣本點坐標的平均值作為聚類原型的中心.

IPCM的隸屬度約束和目標函數與PCM相同，已在(1)式和(2)式中給出.由于最佳聚類對應于目標函數取得極值的情況，因此將(2)式對uij取導數并置0，得到隸屬度表達式：

(3)

(4)

其中，k為整數，一般取1.選擇的距離測度為矩陣加權范數，即：

(5)

為了選取具有典型性的樣本作為聚類中心，將文獻[8]中PCM聚類中心公式：

(6)

修改為：

(7)

這里，i=1，…，C，l是迭代計數器.改進的PCM聚類原型的具體求解過程如下：

(8)

將樣本點分別作為Pi(l+1)代入式(8)中，那么使Wi最小的樣本點x將被確定為第l+1次迭代中第i類的聚類中心.

改進的PCM算法的迭代過程如下[9]：

(1)初始化可能性C劃分U(0)、聚類數目C、迭代計數器l以及加權指數m；

(2)用(4)式估算ηi；

(3)將U(l)代入(7)式選取聚類原型模式P(l+1)，再用(3)式計算U(l+1)；

(4)滿足‖P(l-1)-P(l)‖<ε時，算法停止，否則l=l+1，重復第3步.

改進的PCM算法仍將具有PCM算法所具有的一切優點，算法幾乎不受噪聲影響，且改進的算法選取具有典型性的樣本作為聚類中心，這就使得該算法在實際應用中更具有合理性.下面，我們將這種改進的PCM聚類算法應用到圖像分割中.

2 基于二維直方圖的改進的PCM分割算法

過去人們所提出的各種閾值分割方法，大多是從圖像的灰度分布直方圖上進行的，使用這種方法在噪聲的干擾下通常并沒有得到滿意的結果.分割效果不好的關鍵原因就是在一維直方圖中，物體的分布和背景的分布已經相互重疊、不可區分，這就使得許多分割方法的前提假設不成立.因為每一圖像像素與其鄰域像素的相關性是相當大的，由此文獻[10]中提出了二維直方圖的思想，不僅考慮到了像素點的信息，而且還用到了鄰域點的信息，使得在一維直方圖中的重疊的地方得以分開.

設原圖像h(x，y)的灰度級數為L，大小為M*N，我們用g(x，y)表示圖像上坐標為(x，y)的像素點的K×K鄰域的平均灰度值，g(x，y)的定義如下：

(9)

其中[]表示取整運算.K為鄰域寬度，一般取奇數.

從g(x，y)的定義可以看出，如果圖像的灰度級為L，那么相應的像素鄰域平均灰度的灰度級也為L.由h(x，y)和g(x，y)可以構成一個二元組，每個二元組屬于二維平面上的一個點.這種二維直方圖不僅考慮到了單個灰度值的統計狀況，而且還涉及到了鄰域信息.設二元組(s，t)出現的頻數為fst，它代表h(x，y)中灰度級為s，g(x，y)中灰度級為t同時出現的二維點數.顯然有下面的關系式成立：

(10)

pst為點灰度-區域灰度均值對(s，t)發生的概率，即：pst=fst/(M*N)，其中M*N為圖像的大小，那么{pst，s，t=0，1，…，L-1}就是該圖像的關于點灰度-區域灰度均值的二維直方圖.圖1(c)、圖1(d)分別是圖1(b)的一維和二維直方圖.可以看出，在強噪聲干擾下，一維直方圖是單峰的，二維直方圖由于利用了圖像鄰域的相關信息，物體和背景的雙峰分布仍明顯地得到保留.

圖1 圖像及其直方圖

下面由h(x，y)和g(x，y)構成二元組F(x，y)=(s，t)，用改進的PCM迭代過程(1)～(4)進行聚類，最終求得聚類中心P和聚類的隸屬度函數U.算法收斂后的分割過程是這樣進行的：設物體的平均灰度值比背景大，那么當‖U1‖>‖U2‖時，U1和U2分別對應物體和背景的隸屬度函數；否則U1和U2分別對應背景和物體的隸屬度函數.對于前一種情況，如下進行圖像分割：

(11)

3 實驗結果及分析

仿真實驗是在Matlab 6.5環境下，在奔騰4、2.4 GHz CPU和512 M內存微處理器上進行的.在實驗中采用了疊加均值為0、方差為0.01的高斯噪聲的4幅圖像.為了驗證提出算法的有效性，采用二維Otsu、二維最大熵和本文方法(稱為2D-IPCM)進行圖像分割對比實驗.實驗結果如圖2～5所示.

從圖2～5的仿真結果可以看出，二維Otsu法和二維最大熵法對噪聲圖像的分割效果基本相同，都存在一些錯分的點；而本文中提出的改進PCM聚類算法，取得了比較滿意的效果，從而說明提出的新方法對于高斯噪聲圖像分割是非常有效的.

圖2 smile圖像分割結果(64*64)

圖3 rice圖像分割結果(256*256)

圖4 circuit圖像分割結果(280*272)

圖5 lena圖像分割結果(512*512)

為了進一步驗證本文中方法的抗噪聲能力，對上述的4副不同圖像疊加了噪聲密度為0.05的椒鹽噪聲進行對比實驗.實驗結果如圖6～9所示.

圖6 smile圖像分割結果(64*64)

圖7 rice圖像分割結果(256*256)

圖8 circuit圖像分割結果(280*272)

圖9 lena圖像分割結果(512*512)

從圖6～9的仿真結果可以看出，提出的改進PCM聚類算法，對于含有椒鹽噪聲的圖像取得了比較滿意的分割效果，從而說明提出的新方法對于椒鹽噪聲圖像分割是非常有效的.

為了進一步驗證提出的方法的有效性，把圖2和圖6人造圖像的分割結果與原圖(不加噪聲)進行點對點的對比，可以得出錯分的像素點數.表1對3種方法在兩種噪聲環境的錯分點數進行了統計，可以看出，相對二維Otsu法和二維最大熵函數法，本文中提出的改進的FCM方法錯分點數少得多.

表1 3種方法錯分點數的比較

4 結論

相對于標準的PCM聚類方法，改進算法的最大特點是用具有代表性的樣本模式代替原來的聚類原型，使得改進的PCM算法更為適用.另外，二維直方圖中，同時考慮各像素的灰度值分布和它們的鄰域像素的平均灰度值分布，這使得在一維直方圖中物體和背景的分布區分不明顯的現象在二維直方圖中得到了較好的改善.圖像分割實質上是聚群問題，因此利用改進的PCM聚類算法將物體從背景中分割出來是非常合適的.通過對幾副不同噪聲干擾的圖像的分割實驗，表明本文中提出的方法是相當有效的.需要指出的是，為了提高聚類算法的速度，可利用快速聚類模糊算法[11]來實現本文中提出的圖像分割方法，大大增加算法的實用性.

[1] NikhilR P and Sankar K. A review on image segmentation techniques[J].Pattern Recognition，1993，26(9):1227-1294.

[2] Pham D L，Prince J L. An adaptive fuzzy c-means algorithm for image segmentation in the presence of intensity in-homogeneities[J].Pattern Recognition Letters，1999，20:57-68.

[3] Chen W J，Giger M L,Bick U. A fuzzy c-means (FCM)-based approach for computerized segmentation of breast lesions in dynamic contrast enhanced MRI images. Acad. Radio，2006，13(1):63-72.

[4] Krishnapuram R，Keller J. A possibilistic approach to clustering[J].IEEE Transactions on Fuzzy Systems，1993，1(2):98-110.

[5] Bezdek J C. Pattern recognition with fuzzy objective function algorithms[M].New York:Norwell，1981.

[6] Zadel L A. Fuzzy sets as a basis for the theory of possibility[J].Fuzzy Sets and Systems，1978(1):3-28.

[7] Zadeh L H，Michie D，Michie L. The theory of approximate reasoning[J].Machine intelligence，1979(9):149-194.

[8] Cai W L，Chen S C，Zhang D Q. Fast and robust fuzzy c-means clustering algorithms incorporating local information for image segmentation[J].Pattern Recognition，2007，40(7):825-838.

[9] 張嬋，高新波，姬紅兵.視頻關鍵幀提取的可能性C-模式聚類算法[J].計算機輔助設計與圖形學學報，2005，17(9):2040-2045.

[10] 劉健莊.基于二維直方圖的圖像模糊聚類分割方法[J].電子學報，1992，20(9):40-46.

[11] 劉健莊，謝維信.一種改進的AFCM聚類算法[J].西安電子科技大學學報，1990，17(3)：75-80.