馬爾可夫隨機場約束下的PCM圖像分割算法

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

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

2.湘潭大學信息工程學院，湖南湘潭 411105

馬爾可夫隨機場約束下的PCM圖像分割算法

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

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

2.湘潭大學信息工程學院，湖南湘潭 411105

1 引言

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

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

2 FCM算法

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

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

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

3 PCM算法

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

改進后的目標函數(shù)通過增加一個懲罰項使有代表性的特征點隸屬度盡可能高，而沒有代表性的特征點隸屬度盡可能低，從而具有更好的聚類效果。聚類的準則為取JPCM(U,V;X)的極小值[4]。

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

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

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

4 Markov隨機場與Gibbs隨機場

時，才是在指標集S上關于鄰域系統(tǒng)N的Markov隨機場。MRF有效表達了當前像素的標記僅與其鄰域中像素的標記有關，與其他位置像素的標記情況無關。

MRF很好地反應了圖像的局部特性，但是用局部特性定義整個圖像很難。Hamersley-Clifford定理揭示了MRF與Gibbs分布之間的等價性，把MRF與Gibbs分布對應起來，通過單個像素及其鄰域的簡單特性得到整個圖像的全局特性：

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

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

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

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

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

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

MPCM的具體步驟如下：

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

（2）根據(jù)多級邏輯模型，計算圖像各點屬于各類的先驗概率P(i,j)。

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

6 實驗結(jié)果與分析

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

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

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

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

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

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

7 結(jié)束語

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

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

[2]武小紅，周建江.可能性模糊C均值聚類新算法[J].電子學報，2008，36（10）：1996-2000.

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

[4]周巧萍.可能性聚類算法的研究[D].太原：中北大學，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]林愛英，賈芳，昝紅英.基于二維直方圖的改進的PCM聚類分割方法[J].湖北大學學報：自然科學版，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隨機場與模糊C均值聚類的圖像分割新算法[J].電子學報，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]劉小芳，曾黃麟，呂炳朝.點密度函數(shù)加權模糊C-均值算法的聚類分析[J].計算機工程與應用，2004，40（24）：64-65.

[11]林亞忠，郝剛.結(jié)合隨機場的自適應加權FCM改進方法[J].計算機工程與應用，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]張玉花，陳秋紅.一種二型模糊可能性聚類紅外圖像分割算法[J].激光與紅外，2009，39（7）：780-783.

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

[16]霍東民，劉高煥，駱劍承.基于PCM改進算法的遙感混合像元模擬分析[J].遙感學報，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）聚類算法具有更好的抗干擾能力。但PCM聚類算法對初始化條件很敏感，在聚類的過程中很容易導致聚類結(jié)果一致性，并且沒有考慮到像素的空間信息，用在圖像分割尤其是多目標圖像分割上效果極不穩(wěn)定。在PCM算法的基礎上，利用Markov隨機場中的鄰域關系屬性，引入先驗空間約束信息，建立包含灰度信息與空間信息的新聚類目標函數(shù)，提出馬爾可夫隨機場與PCM聚類算法相融合的圖像分割新算法（MPCM算法）。實驗結(jié)果表明，在多目標圖像分割上利用MPCM算法可以取得比PCM更好的分割效果。

圖像分割；可能性C均值；Markov隨機場；聚類

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.

湖南省教育廳科研項目（No.10C1263）；湘潭大學科研項目（No.11QDZ11）。

周彤彤（1989—），女，碩士研究生，主要從事圖像處理方面的研究；楊恢先（1963—），男，教授，碩士生導師，主要從事圖像處理、人工智能方面的研究；李淼（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