基于核与局部信息的多维度模糊聚类图像分割算法
开篇：润墨网以专业的文秘视角，为您筛选了一篇基于核与局部信息的多维度模糊聚类图像分割算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要：在以聚类分析为背景的图像分割算法中，引入局部信息是为了在保留图像细节的同时尽可能地减少噪声。在模糊C均值算法基础上，提出了一种基于核与局部信息的多维度模糊聚类分析方法来权衡图像中的噪声和细节。该算法引入2个基于局部信息的图像变体，即平滑和锐化处理后的图像，使之与原始图像一起构成多维度的灰度值向量来替换原始单维的灰度值； 再利用核方法提高其鲁棒性； 最后添加一个邻域隶属度差异惩罚项很好地修正和增强了最终的分割效果。在人工合成图片的去噪实验中，所提方法取得了近99%的分割正确率，优于Nystrom归一化分割（NNcut）和基于模糊局部信息C均值（FLICM）算法；同时在自然图片和医学图片的对比实验以及参数调控实验中，展现出了其在处理图像噪声和细节时灵活、稳定、健壮且易于调控的特点。
关键词：聚类分析；图像分割；模糊C均值；多维度；核方法；局部信息
中图分类号： TP391.4
文献标志码：A
0引言
图像分割在图像处理以及计算机视觉中一直以来都扮演着极其关键的角色。其主要目的就是将一幅图像分割成数个互不相交的区域，且这些区域是各具特点的。在诸多的图像分割方法[1-5]中，基于聚类分析的图像分割算法是目前研究最多、应用最广泛的算法之一。从聚类分析的角度出发，图像分割实际上就是将图像中所有的像素点依据其特征而进行聚类的过程。本文研究的主要内容是在聚类分析领域最为经典的模糊C均值聚类 （Fuzzy CMeans， FCM） 算法。
Ruspini[6]首先在1969年提出了模糊划分的概念，将模糊集理论引入聚类分析中，扩展了隶属度的取值范围并取得了更佳的聚类效果和数据表达能力。随后，基于目标函数的模糊聚类方法[7-10]成为了研究的热门。FCM算法在1974年被Dunn[11]首次提出，并且在1981年由Bezdek[12]进行开发，后发展成为该领域研究的主流。在传统的基于FCM的图像分割算法中，所有的像素点仅仅根据其灰度值（或色彩值）进行聚类而不考虑其位置信息，尤其在图像存在噪声点、奇异点时，分割效果不甚理想。于是，人们开始尝试着将空间信息融入到聚类算法之中。
由于FCM是一种基于目标函数的模糊聚类方法，所以许多的改进算法都将位置信息作为调整项加入到原始的目标函数中，从而对聚类结果进行优化。1998年Tolias等[13]提出了一种基于邻域规则的增强机制（rulebased neighborhood enhancement）来引入空间信息约束并在之后将其改进为AFCS（Adaptive Fuzzy Clustering Segmentation）算法[14]。但该算法所制定的规则相当繁琐和复杂，导致其未能得到积极的发展。2002年Ahmed等[15]提出了一种新颖的改进思路将空间局部信息引入到原始目标函数中，该算法的主要思想即是将每个像素点邻域内所有像素点的灰度均值与聚类中心的距离作为惩罚项来对聚类结果进行约束和修正，被称作BCFCM（BiasCorrected FCM）算法。但空间邻域惩罚项在每一步的迭代求解过程中都要进行计算导致该算法的计算量非常大。2004年，Chen等[16]为了提高计算效率，对BCFCM的目标函数进行了优化，代入滤波后的图像信息数据进行计算从而巧妙避免了之前空间邻域惩罚项繁琐的层层迭代。但值得注意的是，这些方法都存在一些至关重要的因子来控制添加的惩罚项和原始目标函数之间的平衡，而大部分情况下，这些因子是难以调控的，并且对聚类结果影响非常之大。2007年，Cai等[17]提出了一些方法来自适应地衡量这些调控因子以及相关参数的值。近些年仍有许多相关算法被陆续的提出和改进[18-25]，例如在2010年Krinidis等[19]提出的FLICM（Fuzzy Local Information CMeans）算法，在该算法中就不需要对任何的参数进行预先的调试和设定。
但参数的自适应求解所付出的时间代价也是昂贵的，FLICM算法处理一张100×100像素图片的平均用时也超过100s，而且不能灵活地根据用户需求来对图片分割结果进行调整。于是，迫切需求一种计算快捷效果稳定且易于调控的图像分割算法。这也是本文旨在解决的问题。
1基于核的多维度模糊C均值聚类方法
本章首先介绍经典的FCM算法及其应用在图像分割上的原理；然后提出基于图像局部信息的多维灰度值向量方法，来权衡图像噪声和细节；并用核方法进行处理，在加速聚类算法速度的同时也提高了聚类结果的鲁棒性。
1.1经典模糊C均值方法与图像分割
把传统的FCM应用于图像分割就是单纯地把图像中所有像素点的灰度值进行聚类。在FCM中，整个聚类过程就是将一个目标函数的值最小化的过程。当n个数据xi要被聚成c类时，目标函数可以表示成如下的形式：
JFCM=∑ni=1∑ck=1umikxi-vk2（1）
其中：V={vk}表示第k个聚类中心，显然，vk和原始数据xi是同维数的； xi-vk2表示第i个数据和第k个聚类中心的距离，本文采用欧氏距离； 而U={uik}则是第i个数据xi对于第k个聚类中心的隶属度，并满足如下条件：
U={uik∈[0，1]∑ck=1uik=1}（2
式（1）中，m>1表示模糊系数，大多数情况下（包括在本文中）m=2。使得目标函数最小则是一个条件极值问题。这样，V和U就可以通过迭代式求解得到：
v*k=∑ni=1umijxi/∑ni=1umij（3
u*ik=1∑cl=1xi-vk2xi-vl21m-1（4
对于一张由n个像素点组成的图像I，需要被聚成c类，每一个像素点的灰度值xi是已知的，通过上述的方法就可以得到最终的隶属度矩阵U，即每一个像素点对每一类的隶属度。对于第i个像素点，如果uik在ui1～uic中最大，那么这个像素点将被归为第k类。
1.2基于图像局部信息的多维度模糊聚类方法
如图1中所示的3幅图像。后两张图像分别是由第1张图像通过平滑滤波器和锐化滤波器而得到的。尽管这3幅图像在计算机中存储的灰度值矩阵不同，但从人的感官认识上出发，它们却是极其相似的，甚至可以说是同一张图片。包括在引言中也提到，使用滤波后的图像数据信息能够巧妙地引入局部信息。但不同于之前将滤波后的图像数据经过处理作为惩罚项直接添加到原始目标函数上，本文则是将滤波后的图像灰度值信息添加到原始图像灰度值信息的第二维和第三维上，使原本图像一维的灰度值信息拓展成三维的灰度值信息，并且可以通过调整它们在构成三维灰度值向量时的权重来灵活地决定最终结果是更倾向于去噪还是更多地保留细节。
例如，图1中原始的图1（a）由n个像素点构成，其灰度值向量为A=[x1，x2，…，xn]T，那么通过平滑滤波后得到的图1（b）的灰度值为B=[y1，y2，…，yn]T，通过锐化滤波后得到的图1（c）的灰度值向量为C=[z1，z2，…，zn]T，最终通过一定权重配比，使用Data=[αA；βB；γC]作为数据集进行聚类，权重向量W=[α，β，γ]在没有特殊要求的情况下令W=[1，0.5，0.5] 来一般性地权衡噪声和细节。
1.3核方法
通过使用上述多维度方法后，聚类的数据集由原始的1维数据拓展成了三维，核方法的引入能够显著提升聚类算法在处理高维时的效率和鲁棒性。下面给出基于核方法的模糊C均值聚类（Kernel Fuzzy CMeans， KFCM）算法[26]的基本概念。
定义一个从原始空间X到特征空间H的映射Φ：x∈XΦ（x）∈H。利用核函数把原始空间的点映射到特征空间中，FCM目标函数中的距离即变为核化距离，由此得到KFCM的目标函数：
JKFCM=∑ni=1∑ck=1umikΦ（xi）-Φ（vk）2（5）
其中Φ（xi）-Φ（vk）2即表示核化距离，利用核函数的性质：K（x，y）=〈Φ（x），Φ（y）〉，从而简化内积运算，于是有：
Φ（xi）-Φ（vk）2=K（xi，xi）+K（vk，vk）-2K（xi，vk）（6
高斯核函数是使用最普遍的核函数之一，具体形式如下：
K（x，y）=exp[-（x-y2）/σ]（7）
其中：σ是该核函数的核参数，本文中默认使用σ=20。显然K（x，x）=0，式（5）即可以简化为：
JKFCM=2∑ni=1∑ck=1umik（1-K（xi，vk））（8
2邻域隶属度差异惩罚项与算法模型
2.1邻域隶属度差异惩罚项
尽管使用多维度的核模糊聚类方法已经能很好地解决图像分割的问题了，但是为了使最终算法更加健壮，适应性更强，其聚类结果仍需进一步的调整和改进。
如图2所示，图2（a）需要被分成3类，一个误分类有可能在这种情况下发生，即图2（b）中黑白边界处的像素点被归到错误的类别中。究其原因在于，使用多维度灰度信息时，平滑滤波和锐化滤波都容易使边界处的像素点灰度值发生突变，很有可能导致这些像素点最终的隶属度偏离正确的范围而造成偶然的误分类。邻域隶属度差异度惩罚项[27]的添加就能够有效地缓解该问题，且进一步提高了算法的去噪能力。其定义如下：
G=∑ni=1∑ck=1∑j≠i j∈Eiumik（1-ujk）m（9）
其中，Ei是指第i个像素点xi的邻域范围，一般采用8邻域范围。由于ujk表示xj对第k类的隶属度，那么1-ujk就表示xj不属于第k类的程度。式（9）最终求和结果的物理含义就是指每个像素点与其邻域像素点不属于同一类的程度，即隶属度差异。该惩罚项的值越小则表示相邻像素点的隶属度差异越小，聚类结果更倾向于将相邻的像素点归为同一类。这对抑制不良的隶属度偏移以及加强算法去噪能力作出了更进一步的贡献。同时，为了使计算过程更加方便，这里引入邻域矩阵Nij的概念：
Nij=
1，xi和xj相邻且i≠j
0，其他 （10）
那么式（9）就可以改写成：
G=∑ni=1∑ck=1∑nj=1umik（1-ujk）mNij（11
2.2最终算法模型
添加了邻域隶属度差异惩罚项后，最终的目标函数如下所示：
JMDKFCM=2∑ni=1∑ck=1umik（1-K（xi，vk））+
λ∑ni=1∑ck=1∑nj=1umik（1-ujk）mNij（12）
其中，λ是一个控制因子来平衡该惩罚项的值，避免其对原始目标函数造成过度的影响。与FCM和KFCM类似，使目标函数极小化，隶属度矩阵U和聚类中心V便可以通过迭代法求解得到：
v*k=∑ni=1umikK（xi，vk）xi∑ni=1umikK（xi，vk）（13
u*ik=1∑cl=12（1-K（xi，vk））+λ∑nj=1（1-ujk）mNij2（1-K（xi，vl））+λ∑nj=1（1-ujk）mNij 1 m-1（14
实际上，由于添加的惩罚项和聚类中心V是无关的，所以该算法中V的迭代式和KFCM是一致的。为了加速迭代过程，先使用计算量较少的KFCM方法来得到隶属度矩阵UKFCM和聚类中心VKFCM，然后用它们来初始化该迭代过程能够有效地减少计算时间。
此外，当得到UKFCM和VKFCM时，λ的值由式（15）得到：
ω=λ∑ni=1∑ck=1∑nj=1umik（1-ujk）mNij2∑ni=1∑ck=1umik（1-K（xi，vk））（15）
其中，ω∈[0，0.1]来控制最终分割结果的平滑程度。更确切地说，当使用KFCM的结果来对JMDKFCM进行初始化时，邻域隶属度差异惩罚项的值最好不超过原始目标函数值的10%从而避免失衡。一般地，默认取ω=0.01即可达到较佳的效果，也可依据用户的设定来自行调整。当ω=0时即表示不使用该邻域隶属度差异惩罚项。
2.3算法流程综述
多维度核模糊C均值聚类方法（MultiDimensional Kernel Fuzzy CMeans clustering method，MDKFCM）的主要思想是：根据原始图像进行平滑和锐化滤波处理，使得每一个像素点的灰度值由1维扩展成3维；构建三维灰度值矩阵，通过邻域隶属度差异惩罚项构建新聚类算法，再进行处理计算，得到最终的隶属度矩阵和聚类中心，从而进行图像分割。
其算法流程具体如下：
输入图像Ix由n个像素点构成，其灰度值向量为A=[x1，x2，…，xn]T，需要被分成c类；
输出最终的UMDKFCM和VMDKFCM以及图像分割结果。
步骤1得到原图像通过平滑滤波后图像Iy的灰度值向量B=[y1，y2，…，yn]T，以及锐化滤波后图像Iz的灰度值向量C=[z1，z2，…，zn]T；
步骤2根据选取的权重向量W=[α，β，γ]，默认取W=[1，0.5，0.5]，来构建图像的多维灰度向量Data=[αA；βB；γC]；
步骤3通过KFCM对Data进行聚类，得到隶属度矩阵UKFCM和聚类中心VKFCM；
步骤4将UKFCM和VKFCM代入式（15）并设置ω，默认取ω=0.01，从而求解出λ的值；
步骤5λ得到后，通过式（13）、（14）求出UMDKFCM和VMDKFCM；
步骤6根据UMDKFCM来确定每个像素点该被归为哪类；
步骤7将图像每一个像素点的灰度值设置成其所属的那一类的聚类中心的值（第一维）。
3实验结果与分析
3.1参数设置
权重向量W=[1，0.5，0.5]，ω=0.01时，即能满足一般性的分割需求。但由于在3.2和3.3节中，实验的主要目的是为了去除噪声，所以这里对W进行适当的调整。通过实验相关结果分析，当处理椒盐噪声时设定W=[1，1，0.25]，处理高斯噪声和莱斯噪声时设定W=[1，1.5，0.25]，可以达到较理想的去噪效果。
3.2人工合成图片的去噪实验
图3～图5展示了在3张合成图片I1、I2、I3上施加不同程度、不同类型的噪声后，MDKFCM与NNcut （Nystrom Normalized Cut）[28]和FLICM[19]算法的分割实验对比。从中可以看出，NNcut算法虽然有一定的去噪能力，但还远不能满足需求；FLICM算法在图片I2上的表现很好，但在图片I1和I3上的处理结果仍保留了许多的噪声点；而MDKFCM在3张图片上的实验表现均十分优秀，尤其在图片I1上，分割结果几乎和原图无异。此外，通过将MDKFCM算法在图片I2和I3上的分割结果和原始图像进行比较得知，其误差基本上都出现在图像中不同区域的交界处。由于多维度方法和邻域隶属度差异惩罚项都是基于像素点的局部信息而提出的，所以在区域边界处的分割准确率有所波动也是可以预见的结果。
表1详细给出了在3张合成图片I1、I2、I3上施加0.03的椒盐噪声和高斯噪声后，不同算法分割结果的正确率。正确率定义为正确分割的像素点占图像总像素点的比重。从中可以看出，MDKFCM算法表现最佳，且分割正确率均在99%以上。
3.3医学图片与自然图片的去噪实验
图6和图7展示了3种算法在医学图片I4、I5上的实验结果对比。从图6中可以看出，在施加了l=9莱斯噪声的医学图片I4上进行实验，3种算法都表现出了相当不错的去噪能力；而图7的实验结果则表明，当莱斯噪声程度加大到l=20时，NNcut算法的处理结果变得很不理想，大部分的噪声依旧被保留了下来，但FLICM和MDKFCM却仍能保持较好的分割结果。值得注意的是，图7中MDKFCM的分割结果较FLICM而言，还留有少许的许噪声点；但另一方面，更多的图像细节如内侧的纹路也被保留了下来。实际上，虽然MDKCM可以通过参数的调节来得到更好的结果，但有一点不可避免的就是，更多的细节往往就意味着更多的噪声，更高强度的去噪往往带来的就是更多细节的流失。
接下来，自然图片I6、I7也被施加以不同种类的人造噪声来测试该3种算法在自然图片上的去噪表现。如图8所示，自然图片I6在被施加了0.015高斯噪声后，NNCut算法表现不佳，FLICM和MDKFCM均表现良好；图9则展示了带有0.02椒盐噪声的自然图片I7上的分割实验结果，FLICM和MDKFCM算法的分割效果均明显优于NNcut，而相比较之下，兼顾去噪能力和细节保留综合考虑，MDKFCM的分割效果要好于FLCIM。此外，大量实验也表明，当处理的图片越大，即像素点越多时，各算法的处理效果均会有不同程度的下滑。
3.4调控参数对实验结果的影响
以上的实验结果可以充分展示MDKFCM在对抗噪声时的卓越表现。但在实际应用中，人造噪声却并不是问题的关键所在。更多的时候，图像分割需要根据用户的需求来进行调整。例如图10中所示的Lena图像，用户实际期望的分割结果是忽略图像中的小细节，如发丝中的毛糙等。在权重向量W=[1，0.5，0.5]的前提下逐渐增大ω的值来观察MDKFCM算法的分割结果，从中可以明显看出，发丝内部的细节逐渐减少，整个区域趋于整体化，图像的轮廓也得到凸显。另一方面，参数改变对分割结果的影响十分平滑，由此也充分证明MDKFCM的效果稳定且易于调控。
同样地，权重向量W也能对分割结果产生类似的影响，具体如图11中所示。设定ω=0.01，随着W第3维锐化滤波的权重逐渐下降，第二维平滑滤波的权重逐渐上升，分割结果则愈加平整。实际上，虽然W和ω在构造算法模型时是相互独立的，但其对图像分割结果的影响却是相辅相成，相互渗透的。通过对它们进行合理的调控，就能够灵活而又方便地依据具体需求来对图像分割的结果进行调整。
4结语
虽然MDKFCM算法能够灵活且高效地处理在不同需求下的图像分割问题，但该算法的提出更多的是在于使图像分割的结果趋于平坦而规避毛糙，同时彰显整体轮廓，迎合人的视觉感官印象。在MDKFCM算法中，多维度方法的提出源自于不同的滤波图片在人眼中却看似相同这一现象，而邻域隶属度惩罚项的提出则源于人的视觉注意机制更容易将相邻的像素点归为一类。综上所述，MDKFCM算法更倾向于去解决那些注重整体外形而非内部细节的图像分割问题。除此之外，本文仍有许多未能考虑周全之处，如本文中所使用的模糊指数、核参数、滤波模板等都是统一设定，未能详细讨论其对图像分割结果的具体影响，以及算法速度上虽有明显的优势，但并未从时间复杂度层面上给出理论证明，有待在以后工作过程中进行补充和完善。
参考文献：
[1] FU K S， MUI J K. A survey on image segmentation[J]. Pattern Recognition， 1981， 13（1）：3-16.
[2] HARALICK R M， SHAPIRO L G. Image segmentation techniques[J]. Computer Vision Graphics and Image Processing， 1985， 29（85）：100-132.
[3] PAL N R， PAL S K. A review on image segmentation techniques[J]. Pattern Recognition， 1993， 26（93）：1277-1294.
[4] ZHANG Y J. A survey on evaluation methods for image segmentation[J]. Pattern Recognition， 1996， 29（95）：1335-1346.
[5] CHENG H， JIANG X， SUN Y， et al. Color image segmentation： advances and prospects[J]. Pattern Recognition， 2001， 34（1）：2259-2281.
[6] RUSPINI E H. A new approach to clustering[J]. Information and Control， 1969， 15（69）：22-32.
[7] DUNN J C. A graph theoretic analysis of pattern classification via Tamuras fuzzy relation[J]. IEEE Transactions on Systems Man and Cybernetics， 1974， 4（3）：310-313.
[8] BACKER E， JAIN A K. A clustering performance measure based on fuzzy set decomposition[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 1981， 3（1）：66-75.
[9] WU Z， LEAHY R. An optimal graph theoretic approach to data clustering： theory and its application to image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 1993， 15（11）：1101-1113.
[10] LE K. Fuzzy relation compositions and pattern recognition[J]. Information Sciences， 1996， 89（24）： 107-130.
[11] DUNN J C. A fuzzy relative of the ISODATA process and its use in detecting compact wellseparated clusters[J]. Journal of Cybernetics， 1974， 3（3）：32-57.
[12] BEZDEK J C. Pattern recognition with fuzzy objective function algorithms[M]. New York： Plenum Press， 1981：15-45.
[13] TOLIAS Y A， PANAS S M. On applying spatial constraints in fuzzy image clustering using a fuzzy rulebased system[J]. IEEE Signal Processing Letters， 1998， 5（10）：245-247.
[14] TOLIAS Y A， PANAS S M. Image segmentation by a fuzzy clustering algorithm using adaptive spatially constrained membership functions[J]. IEEE Transactions on Systems Man and Cybernetics Part A： Systems and Humans， 1998， 28（3）：359-369.
[15] AHMED M N， YAMANY S M， MOHAMED N， et al. A modified fuzzy Cmeans algorithm for bias field estimation and segmentation of MRI data[J]. IEEE Transactions on Medical Imaging， 2002， 21（3）：193-199.
[16] CHEN S， ZHANG D. Robust image segmentation using FCM with spatial constraints based on new kernelinduced distance measure[J]. IEEE Transactions on Systems Man and Cybernetics Part B， 2004， 34（4）：1907-1916.