基于二维直方图的改进的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.