基于二維直方圖的改進(jìn)的PCM聚類分割方法

林愛英，賈芳，昝紅英

(1.河南農(nóng)業(yè)大學(xué)理學(xué)院，河南 鄭州 450002；2.鄭州大學(xué)信息工程學(xué)院，河南 鄭州 450001)

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

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

1 改進(jìn)的PCM聚類算法

(1)

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

根據(jù)約束(1)，重新定義PCM聚類的目標(biāo)函數(shù)：

(2)

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

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

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

(3)

(4)

其中，k為整數(shù)，一般取1.選擇的距離測度為矩陣加權(quán)范數(shù)，即：

(5)

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

(6)

修改為：

(7)

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

(8)

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

改進(jìn)的PCM算法的迭代過程如下[9]：

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

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

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

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

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

2 基于二維直方圖的改進(jìn)的PCM分割算法

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

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

(9)

其中[]表示取整運(yùn)算.K為鄰域?qū)挾龋话闳∑鏀?shù).

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

(10)

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

圖1 圖像及其直方圖

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

(11)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表1 3種方法錯分點(diǎn)數(shù)的比較

4 結(jié)論

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

[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] 張嬋，高新波，姬紅兵.視頻關(guān)鍵幀提取的可能性C-模式聚類算法[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，2005，17(9):2040-2045.

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

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