周彤彤，楊恢先，李淼，譚正華，張建波

1.湘潭大學(xué)材料與光電物理學(xué)院，湖南湘潭 411105

2.湘潭大學(xué)信息工程學(xué)院，湖南湘潭 411105

馬爾可夫隨機(jī)場(chǎng)約束下的PCM圖像分割算法

周彤彤1，楊恢先1，李淼1，譚正華2，張建波2

1.湘潭大學(xué)材料與光電物理學(xué)院，湖南湘潭 411105

2.湘潭大學(xué)信息工程學(xué)院，湖南湘潭 411105

1 引言

圖像分割是圖像分析與理解中一個(gè)最為基本的處理步驟，其目的是將圖像劃分為多個(gè)互不重疊的若干區(qū)域，每個(gè)區(qū)域內(nèi)的像素具有相似的或一致的性質(zhì)[1]。圖像分割質(zhì)量的好壞直接影響后續(xù)圖像處理的效果，甚至決定其成敗，因此，圖像分割一直是人們高度重視的研究方向。

模糊C-均值聚類(lèi)算法（Fuzzy C-Means，F(xiàn)CM）廣泛應(yīng)用于模式識(shí)別、圖像處理和視頻檢索等領(lǐng)域，是一種建立在平方誤差最小準(zhǔn)則上的聚類(lèi)算法，但它對(duì)噪聲點(diǎn)和野值點(diǎn)很敏感。R.Krishnapuram和J.Keller于1993年提出的可能性C均值（Possibilistic C-Means，PCM）聚類(lèi)算法放寬了隸屬度的約束條件，構(gòu)造了一個(gè)新的目標(biāo)函數(shù)。PCM能夠聚類(lèi)包含噪聲或野值點(diǎn)的數(shù)據(jù)，使噪聲數(shù)據(jù)具有很小的隸屬度值，在某種程度上改進(jìn)了FCM算法的不足。但放寬了隸屬度的約束條件使得實(shí)際聚類(lèi)中容易出現(xiàn)聚類(lèi)中心的重合，造成圖像的過(guò)分割，尤其在多目標(biāo)圖像分割中往往不能取得理想的分割效果[2]。一個(gè)完整的分割模型應(yīng)該在充分考慮灰度信息的同時(shí)，還要考慮像素的空間信息對(duì)分割的影響。馬爾可夫隨機(jī)場(chǎng)（Markov Random Field，MRF）很好地描述了相鄰像素和相關(guān)特征間的相互依賴(lài)關(guān)系，彌補(bǔ)了PCM聚類(lèi)算法對(duì)像素鄰域信息描述的不足。利用多級(jí)邏輯模型，以Gibbs能量的形式引入先驗(yàn)鄰域約束信息，提出馬爾可夫隨機(jī)場(chǎng)與PCM聚類(lèi)算法相融合的圖像分割新算法（Markov and Possibilistic C-Means，MPCM），將鄰域信息充分地引入到圖像分割中，從而提高可能性聚類(lèi)算法的分割性能并改善分割的視覺(jué)效果。

2 FCM算法

FCM聚類(lèi)算法在圖像分割中是根據(jù)圖像像素和聚類(lèi)中心的加權(quán)相似性測(cè)度，對(duì)目標(biāo)函數(shù)進(jìn)行迭代優(yōu)化以確定最佳聚類(lèi)的一種算法?；舅悸窞椋簩?shù)據(jù)集X分為C類(lèi)，X中任意樣本對(duì)i類(lèi)的隸屬度u，分類(lèi)結(jié)果用一個(gè)模糊隸屬度矩陣U表示，模糊C均值聚類(lèi)是通過(guò)最小化隸屬度矩陣U和聚類(lèi)中心矩陣V的目標(biāo)函數(shù)J實(shí)現(xiàn)的：

其中，uik為第k個(gè)像素對(duì)第i類(lèi)的隸屬度，U={uik}為隸屬度矩陣，V={v1,v2,…,vc}為c個(gè)聚類(lèi)中心點(diǎn)集，2≤c≤n，m∈[1,∞)為模糊加權(quán)指數(shù)，它控制數(shù)據(jù)劃分過(guò)程的模糊程度，當(dāng)m=1時(shí)，模糊聚類(lèi)就退化為硬C均值聚類(lèi)，通常m=2。

（4）重復(fù)步驟（2）、（3），直至式（4）收斂[3]。

3 PCM算法

PCM目標(biāo)函數(shù)定義為：

改進(jìn)后的目標(biāo)函數(shù)通過(guò)增加一個(gè)懲罰項(xiàng)使有代表性的特征點(diǎn)隸屬度盡可能高，而沒(méi)有代表性的特征點(diǎn)隸屬度盡可能低，從而具有更好的聚類(lèi)效果。聚類(lèi)的準(zhǔn)則為取JPCM(U,V;X)的極小值[4]。

在約束條件下，根據(jù)拉格朗日條件極值法則，得到目標(biāo)函數(shù)式（5）取得極小值的必要條件：

估計(jì)ηi值的方法是使用FCM算法收斂后得到的值進(jìn)行估計(jì)，一般情況下，ηi在算法執(zhí)行期間，其值不改變。其中參數(shù)ηi文獻(xiàn)[5]中給出的為：

PCM算法通常以FCM模糊初始劃分，然后更加精確地計(jì)算隸屬度矩陣。PCM能夠聚類(lèi)包含噪聲或野值點(diǎn)的數(shù)據(jù)，使噪聲數(shù)據(jù)具有很小的隸屬度值，因而減少了噪聲點(diǎn)對(duì)聚類(lèi)中心的影響。但是PCM由于缺乏對(duì)圖像空間特征和像素特征的綜合考慮，會(huì)導(dǎo)致對(duì)于執(zhí)行區(qū)域的過(guò)分割或者誤分割，在多目標(biāo)圖像分割時(shí)難以分割出滿(mǎn)意的結(jié)果[6]。

4 Markov隨機(jī)場(chǎng)與Gibbs隨機(jī)場(chǎng)

時(shí)，才是在指標(biāo)集S上關(guān)于鄰域系統(tǒng)N的Markov隨機(jī)場(chǎng)。MRF有效表達(dá)了當(dāng)前像素的標(biāo)記僅與其鄰域中像素的標(biāo)記有關(guān)，與其他位置像素的標(biāo)記情況無(wú)關(guān)。

MRF很好地反應(yīng)了圖像的局部特性，但是用局部特性定義整個(gè)圖像很難。Hamersley-Clifford定理揭示了MRF與Gibbs分布之間的等價(jià)性，把MRF與Gibbs分布對(duì)應(yīng)起來(lái)，通過(guò)單個(gè)像素及其鄰域的簡(jiǎn)單特性得到整個(gè)圖像的全局特性：

式（10）可以理解為：若zi鄰域中劃分為第k類(lèi)的像素個(gè)數(shù)越多，則zi屬于第k的可能性越大[8]。

Gibbs隨機(jī)場(chǎng)理論很好地描述了圖像位置之間的相鄰關(guān)系，為在圖像分割中引入空間信息提供了很好的理論依據(jù)。

5 馬氏空間約束下的PCM圖像分割算法

由PCM的計(jì)算過(guò)程可知，PCM算法只考慮了像素的灰度信息，沒(méi)有考慮像素間的空間信息，也就是說(shuō)它在圖像分割時(shí)沒(méi)有考慮各個(gè)像素點(diǎn)的灰度特征與其鄰域像素灰度的關(guān)聯(lián)程度。對(duì)于圖像數(shù)據(jù)而言，相鄰像素之間存在著非常強(qiáng)的相關(guān)性。因此，為了能夠獲得更理想的圖像分割效果，將馬爾可夫隨機(jī)場(chǎng)引入到PCM聚類(lèi)算法中，形成既包含像素的灰度信息又考慮到像素空間信息的MPCM算法，定義新的距離函數(shù)：

這樣，新的目標(biāo)函數(shù)既包含了像素的灰度信息，即數(shù)據(jù)到聚類(lèi)中心的距離(xk,vi)，又融入了該像素局部鄰域中的空間信息。若點(diǎn)xk為噪聲點(diǎn)或野值點(diǎn)，即便它在特征域中與第i類(lèi)聚類(lèi)中心的距離較小，但它的鄰域信息卻表明它被劃分為第k類(lèi)的似然度（概率）較小，則兩者的綜合作用促使其不能標(biāo)記為第k類(lèi)。反之也成立。

同樣，依據(jù)拉格朗日極值法則，目標(biāo)函數(shù)式（12）取得極小值的必要條件為：

MPCM的具體步驟如下：

（1）給定類(lèi)別數(shù)c，參數(shù)m，允許的誤差值，對(duì)圖像利用FCM進(jìn)行初始分割，為MPCM算法提供初始參數(shù)估計(jì)。

（2）根據(jù)多級(jí)邏輯模型，計(jì)算圖像各點(diǎn)屬于各類(lèi)的先驗(yàn)概率P(i,j)。

（3）由式（13）、式（14）計(jì)算更新聚類(lèi)中心與隸屬度數(shù)組。

6 實(shí)驗(yàn)結(jié)果與分析

為評(píng)估算法性能，利用Matlab分別實(shí)現(xiàn)FCM，PCM和MPCM這三種算法。

實(shí)驗(yàn)1采用醫(yī)學(xué)腦部MR圖像對(duì)多目標(biāo)圖像分割進(jìn)行實(shí)驗(yàn)分析，如圖1所示。MR成像由于各種電磁噪聲的干擾以及成像設(shè)備的局限性，雖然在軟組織之間可以獲得很高的對(duì)比度，但圖像的信噪比比較低。根據(jù)腦部MR圖像的基本特征將圖像類(lèi)別設(shè)置為4，分別表示白質(zhì)、灰質(zhì)、腦脊髓和背景四個(gè)部分。由圖1可以看出，F(xiàn)CM算法較好地分割出了腦部圖像的各部分，但是存在過(guò)分割和輪廓變形等缺點(diǎn)。PCM分割算法無(wú)法正確分割出腦部圖像的各部分，分割結(jié)果失真嚴(yán)重。MPCM算法完整地分割出腦部的各部分組織并且對(duì)邊界定位較為準(zhǔn)確，分割結(jié)果更加理想。

圖1 腦部MR圖像的分割結(jié)果

實(shí)驗(yàn)2采用遙感圖像對(duì)多目標(biāo)圖像分割進(jìn)行實(shí)驗(yàn)分析，如圖2所示。遙感圖像由于環(huán)境和傳感器的影響，具有灰度變化大、紋理復(fù)雜及邊界模糊等特點(diǎn)，而且不同領(lǐng)域遙感圖像的應(yīng)用對(duì)遙感圖像處理有著不同的要求，尤其在含多目標(biāo)復(fù)雜圖像的圖像分割中由于遙感信息的不確定性及多解性，分割難度比較大。

圖2 遙感圖像的分割結(jié)果

設(shè)置圖像類(lèi)別數(shù)為4，從分割結(jié)果可以看出，F(xiàn)CM算法基本能夠完成分割的要求，但是存在噪聲污染，在細(xì)節(jié)部分各個(gè)類(lèi)別出現(xiàn)混淆。PCM算法混淆了圖像類(lèi)別，雖然對(duì)邊緣部分分割的結(jié)果比較好，但圖像信息丟失嚴(yán)重。MPCM算法既有比較好的去噪效果，也能將各部分比較準(zhǔn)確地分割出來(lái)，明顯改善了PCM在多目標(biāo)圖像分割中的過(guò)分割現(xiàn)象，從圖像視覺(jué)效果看也更加清晰。

7 結(jié)束語(yǔ)

利用Markov隨機(jī)場(chǎng)模型，在PCM算法的框架中引入鄰域關(guān)系限制，完善了圖像分割方法，提出了馬氏空間約束下的PCM圖像分割算法。實(shí)驗(yàn)表明，MPCM算法比PCM算法在多目標(biāo)圖像分割上有較為明顯的改進(jìn)，可以有效改善PCM算法在多目標(biāo)分割中過(guò)分割現(xiàn)象，能取得比PCM算法更好更加穩(wěn)定的分割效果，為后續(xù)的特征提取、目標(biāo)識(shí)別及跟蹤處理等提供了良好的基礎(chǔ)。

[1]蔡濤，徐國(guó)華，徐筱龍.基于模糊C均值與Markov隨機(jī)場(chǎng)的圖像分割[J].計(jì)算機(jī)工程，2007，33（20）：34-36.

[2]武小紅，周建江.可能性模糊C均值聚類(lèi)新算法[J].電子學(xué)報(bào)，2008，36（10）：1996-2000.

[3]李志梅，肖德貴.快速模糊C均值聚類(lèi)的圖像分割方法[J].計(jì)算機(jī)工程與應(yīng)用，2009，45（12）：187-189.

[4]周巧萍.可能性聚類(lèi)算法的研究[D].太原：中北大學(xué)，2008：13-31.

[5]Krishnapuram R，Keller J M.A possibilistic approach to clustering[J].IEEE Trans on Fuzzy Systems，1993，1（2）：98-110.

[6]林愛(ài)英，賈芳，昝紅英.基于二維直方圖的改進(jìn)的PCM聚類(lèi)分割方法[J].湖北大學(xué)學(xué)報(bào)：自然科學(xué)版，2012，34（1）：31-35.

[7]Besag J.On the statistical analysis of dirty pictures[J].Journal Analysis of Royal Statistical Society，1986，B48（3）：259-302.

[8]馮衍秋，陳武凡，梁斌，等.基于Gibbs隨機(jī)場(chǎng)與模糊C均值聚類(lèi)的圖像分割新算法[J].電子學(xué)報(bào)，2004，32（4）：645-647.

[9]Krishnapuram R，Keller J M.The possibilistic e-means algorithm：insights and recommendations[J].IEEE Trans on Fuzzy Systems，1996，4（3）：385-393.

[10]劉小芳，曾黃麟，呂炳朝.點(diǎn)密度函數(shù)加權(quán)模糊C-均值算法的聚類(lèi)分析[J].計(jì)算機(jī)工程與應(yīng)用，2004，40（24）：64-65.

[11]林亞忠，郝剛.結(jié)合隨機(jī)場(chǎng)的自適應(yīng)加權(quán)FCM改進(jìn)方法[J].計(jì)算機(jī)工程與應(yīng)用，2011，47（15）：171-174.

[12]Pam D L，Prince J L.Adaptive fuzzy segmentation of magnetic resonance images[J].IEEE Trans on Medical Imaging，1999，18（9）：737-752.

[13]Jia Kexin，He Zishu.Binary morphology based kernelized Possibilistic C-Means algorithm[J].International Journal of Advancements in Computing Technology，2011，3（5）：97-107.

[14]張玉花，陳秋紅.一種二型模糊可能性聚類(lèi)紅外圖像分割算法[J].激光與紅外，2009，39（7）：780-783.

[15]田小林，焦李成，緱水平.基于ICA優(yōu)化空間信息PCM的SAR圖像分割[J].電子與信息學(xué)報(bào)，2008，30（7）：1751-1755.

[16]霍東民，劉高煥，駱劍承.基于PCM改進(jìn)算法的遙感混合像元模擬分析[J].遙感學(xué)報(bào)，2005，9（2）：131-137.

ZHOU Tongtong1,YANG Huixian1,LI Miao1,TAN Zhenghua2,ZHANG Jianbo2

1.Faculty of Material and Photoelectronic Physics,Xiangtan University,Xiangtan,Hunan 411105,China
2.College of Information Engineering,Xiangtan University,Xiangtan,Hunan 411105,China

Compared with Fuzzy C-Means（FCM）clustering,Possibilistic C-Means（PCM）has a better anti jamming capability. But the Possibilistic C-Means clustering is very sensitive to initial conditions and is very easy to cause the clustering result of consistency.And it doesn’t take into account the pixel spatial information.It is extremely unstable when it is used in image segmentation especially in multi-object image segmentation.Based on the PCM clustering,the prior spatial constraint is incorporated according to Markov random field theory,to build a new clustering objective function including the establishment of gray information and spatial information.This paper presents a new image segmentation algorithm（MPCM）combining Markov and PCM clustering. With experiments,using MPCM algorithm can achieve a better segmentation result than PCM in multi-object image segmentation.

image segmentation;Possibilistic C-Means（PCM）;Markov random field;clustering

與模糊C均值（FCM）算法相比較，可能性C均值（PCM）聚類(lèi)算法具有更好的抗干擾能力。但PCM聚類(lèi)算法對(duì)初始化條件很敏感，在聚類(lèi)的過(guò)程中很容易導(dǎo)致聚類(lèi)結(jié)果一致性，并且沒(méi)有考慮到像素的空間信息，用在圖像分割尤其是多目標(biāo)圖像分割上效果極不穩(wěn)定。在PCM算法的基礎(chǔ)上，利用Markov隨機(jī)場(chǎng)中的鄰域關(guān)系屬性，引入先驗(yàn)空間約束信息，建立包含灰度信息與空間信息的新聚類(lèi)目標(biāo)函數(shù)，提出馬爾可夫隨機(jī)場(chǎng)與PCM聚類(lèi)算法相融合的圖像分割新算法（MPCM算法）。實(shí)驗(yàn)結(jié)果表明，在多目標(biāo)圖像分割上利用MPCM算法可以取得比PCM更好的分割效果。

圖像分割；可能性C均值；Markov隨機(jī)場(chǎng)；聚類(lèi)

A

TN911.73

10.3778/j.issn.1002-8331.1303-0510

ZHOU Tongtong,YANG Huixian,LI Miao,et al.Image segmentation on Possibilistic C-Means clustering algorithm based on Markov spatial constraint.Computer Engineering and Applications,2013,49（24）：157-160.

湖南省教育廳科研項(xiàng)目（No.10C1263）；湘潭大學(xué)科研項(xiàng)目（No.11QDZ11）。

周彤彤（1989—），女，碩士研究生，主要從事圖像處理方面的研究；楊恢先（1963—），男，教授，碩士生導(dǎo)師，主要從事圖像處理、人工智能方面的研究；李淼（1987—），男，碩士研究生，主要從事圖像處理方面的研究。E-mail：Z451206817@126.com

2013-04-01

2013-06-06

1002-8331（2013）24-0157-04

CNKI出版日期：2013-09-12http://www.cnki.net/kcms/detail/11.2127.TP.20130912.1436.015.html