马尔可夫随机场约束下的PCM图像分割算法

周彤彤，杨恢先，李淼，谭正华，张建波

1.湘潭大学材料与光电物理学院，湖南湘潭 411105

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

马尔可夫随机场约束下的PCM图像分割算法

周彤彤1，杨恢先1，李淼1，谭正华2，张建波2

1.湘潭大学材料与光电物理学院，湖南湘潭 411105

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

1 引言

图像分割是图像分析与理解中一个最为基本的处理步骤，其目的是将图像划分为多个互不重叠的若干区域，每个区域内的像素具有相似的或一致的性质[1]。图像分割质量的好坏直接影响后续图像处理的效果，甚至决定其成败，因此，图像分割一直是人们高度重视的研究方向。

模糊C-均值聚类算法（Fuzzy C-Means，FCM）广泛应用于模式识别、图像处理和视频检索等领域，是一种建立在平方误差最小准则上的聚类算法，但它对噪声点和野值点很敏感。R.Krishnapuram和J.Keller于1993年提出的可能性C均值（Possibilistic C-Means，PCM）聚类算法放宽了隶属度的约束条件，构造了一个新的目标函数。PCM能够聚类包含噪声或野值点的数据，使噪声数据具有很小的隶属度值，在某种程度上改进了FCM算法的不足。但放宽了隶属度的约束条件使得实际聚类中容易出现聚类中心的重合，造成图像的过分割，尤其在多目标图像分割中往往不能取得理想的分割效果[2]。一个完整的分割模型应该在充分考虑灰度信息的同时，还要考虑像素的空间信息对分割的影响。马尔可夫随机场（Markov Random Field，MRF）很好地描述了相邻像素和相关特征间的相互依赖关系，弥补了PCM聚类算法对像素邻域信息描述的不足。利用多级逻辑模型，以Gibbs能量的形式引入先验邻域约束信息，提出马尔可夫随机场与PCM聚类算法相融合的图像分割新算法（Markov and Possibilistic C-Means，MPCM），将邻域信息充分地引入到图像分割中，从而提高可能性聚类算法的分割性能并改善分割的视觉效果。

2 FCM算法

FCM聚类算法在图像分割中是根据图像像素和聚类中心的加权相似性测度，对目标函数进行迭代优化以确定最佳聚类的一种算法。基本思路为：将数据集X分为C类，X中任意样本对i类的隶属度u，分类结果用一个模糊隶属度矩阵U表示，模糊C均值聚类是通过最小化隶属度矩阵U和聚类中心矩阵V的目标函数J实现的：

其中，uik为第k个像素对第i类的隶属度，U={uik}为隶属度矩阵，V={v1,v2,…,vc}为c个聚类中心点集，2≤c≤n，m∈[1,∞)为模糊加权指数，它控制数据划分过程的模糊程度，当m=1时，模糊聚类就退化为硬C均值聚类，通常m=2。

（4）重复步骤（2）、（3），直至式（4）收敛[3]。

3 PCM算法

PCM目标函数定义为：

改进后的目标函数通过增加一个惩罚项使有代表性的特征点隶属度尽可能高，而没有代表性的特征点隶属度尽可能低，从而具有更好的聚类效果。聚类的准则为取JPCM(U,V;X)的极小值[4]。

在约束条件下，根据拉格朗日条件极值法则，得到目标函数式（5）取得极小值的必要条件：

估计ηi值的方法是使用FCM算法收敛后得到的值进行估计，一般情况下，ηi在算法执行期间，其值不改变。其中参数ηi文献[5]中给出的为：

PCM算法通常以FCM模糊初始划分，然后更加精确地计算隶属度矩阵。PCM能够聚类包含噪声或野值点的数据，使噪声数据具有很小的隶属度值，因而减少了噪声点对聚类中心的影响。但是PCM由于缺乏对图像空间特征和像素特征的综合考虑，会导致对于执行区域的过分割或者误分割，在多目标图像分割时难以分割出满意的结果[6]。

4 Markov随机场与Gibbs随机场

时，才是在指标集S上关于邻域系统N的Markov随机场。MRF有效表达了当前像素的标记仅与其邻域中像素的标记有关，与其他位置像素的标记情况无关。

MRF很好地反应了图像的局部特性，但是用局部特性定义整个图像很难。Hamersley-Clifford定理揭示了MRF与Gibbs分布之间的等价性，把MRF与Gibbs分布对应起来，通过单个像素及其邻域的简单特性得到整个图像的全局特性：

式（10）可以理解为：若zi邻域中划分为第k类的像素个数越多，则zi属于第k的可能性越大[8]。

Gibbs随机场理论很好地描述了图像位置之间的相邻关系，为在图像分割中引入空间信息提供了很好的理论依据。

5 马氏空间约束下的PCM图像分割算法

由PCM的计算过程可知，PCM算法只考虑了像素的灰度信息，没有考虑像素间的空间信息，也就是说它在图像分割时没有考虑各个像素点的灰度特征与其邻域像素灰度的关联程度。对于图像数据而言，相邻像素之间存在着非常强的相关性。因此，为了能够获得更理想的图像分割效果，将马尔可夫随机场引入到PCM聚类算法中，形成既包含像素的灰度信息又考虑到像素空间信息的MPCM算法，定义新的距离函数：

这样，新的目标函数既包含了像素的灰度信息，即数据到聚类中心的距离(xk,vi)，又融入了该像素局部邻域中的空间信息。若点xk为噪声点或野值点，即便它在特征域中与第i类聚类中心的距离较小，但它的邻域信息却表明它被划分为第k类的似然度（概率）较小，则两者的综合作用促使其不能标记为第k类。反之也成立。

同样，依据拉格朗日极值法则，目标函数式（12）取得极小值的必要条件为：

MPCM的具体步骤如下：

（1）给定类别数c，参数m，允许的误差值，对图像利用FCM进行初始分割，为MPCM算法提供初始参数估计。

（2）根据多级逻辑模型，计算图像各点属于各类的先验概率P(i,j)。

（3）由式（13）、式（14）计算更新聚类中心与隶属度数组。

6 实验结果与分析

为评估算法性能，利用Matlab分别实现FCM，PCM和MPCM这三种算法。

实验1采用医学脑部MR图像对多目标图像分割进行实验分析，如图1所示。MR成像由于各种电磁噪声的干扰以及成像设备的局限性，虽然在软组织之间可以获得很高的对比度，但图像的信噪比比较低。根据脑部MR图像的基本特征将图像类别设置为4，分别表示白质、灰质、脑脊髓和背景四个部分。由图1可以看出，FCM算法较好地分割出了脑部图像的各部分，但是存在过分割和轮廓变形等缺点。PCM分割算法无法正确分割出脑部图像的各部分，分割结果失真严重。MPCM算法完整地分割出脑部的各部分组织并且对边界定位较为准确，分割结果更加理想。

图1 脑部MR图像的分割结果

实验2采用遥感图像对多目标图像分割进行实验分析，如图2所示。遥感图像由于环境和传感器的影响，具有灰度变化大、纹理复杂及边界模糊等特点，而且不同领域遥感图像的应用对遥感图像处理有着不同的要求，尤其在含多目标复杂图像的图像分割中由于遥感信息的不确定性及多解性，分割难度比较大。

图2 遥感图像的分割结果

设置图像类别数为4，从分割结果可以看出，FCM算法基本能够完成分割的要求，但是存在噪声污染，在细节部分各个类别出现混淆。PCM算法混淆了图像类别，虽然对边缘部分分割的结果比较好，但图像信息丢失严重。MPCM算法既有比较好的去噪效果，也能将各部分比较准确地分割出来，明显改善了PCM在多目标图像分割中的过分割现象，从图像视觉效果看也更加清晰。

7 结束语

利用Markov随机场模型，在PCM算法的框架中引入邻域关系限制，完善了图像分割方法，提出了马氏空间约束下的PCM图像分割算法。实验表明，MPCM算法比PCM算法在多目标图像分割上有较为明显的改进，可以有效改善PCM算法在多目标分割中过分割现象，能取得比PCM算法更好更加稳定的分割效果，为后续的特征提取、目标识别及跟踪处理等提供了良好的基础。

[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]刘小芳，曾黄麟，吕炳朝.点密度函数加权模糊C-均值算法的聚类分析[J].计算机工程与应用，2004，40（24）：64-65.

[11]林亚忠，郝刚.结合随机场的自适应加权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优化空间信息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聚类算法对初始化条件很敏感，在聚类的过程中很容易导致聚类结果一致性，并且没有考虑到像素的空间信息，用在图像分割尤其是多目标图像分割上效果极不稳定。在PCM算法的基础上，利用Markov随机场中的邻域关系属性，引入先验空间约束信息，建立包含灰度信息与空间信息的新聚类目标函数，提出马尔可夫随机场与PCM聚类算法相融合的图像分割新算法（MPCM算法）。实验结果表明，在多目标图像分割上利用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