基于空间模糊聚类的图像分割优化算法

深圳大学研究生课程论文题目基于空间模糊聚类的图像分割优化算法成绩专业信息与通信工程课程名称、代码模糊数学理论年级研一姓名梁运恺同组人叶韩学号21501304062150130407时间2015/1/6任课教师李良群1基于空间模糊聚类的图像分割优化算法【摘要】针对传统模糊C－均值(FCM)算法抗噪性能差的问题，提出一种新的基于空间模糊聚类的图像分割优化算法。该算法通过在传统FCM算法基础上加入图像特征项中像素间的空间位置信息，解决了传统FCM对噪声敏感的问题，增强了算法的鲁棒性。实验结果表明，该算法可实现有效分割，分割效果显著优于传统FCM算法。【关键词】图像分割；模糊聚类；ＦＣＭ算法；空间位置信息；TheSpatialFuzzyClusteringOptimizationAlgorithmforImageSegmentationAbstract:Forthepooranti-noiseperformancelimitationsofthetraditionalfuzzyC-means(FCM)algorithm.Weproposedanewspatialfuzzyclusteringoptimizationalgorithmforimagesegmentation.weaddedawealthofspatialinformationbetweenpixelsintheimagefeatureitems,sothatthetraditionalFCMsensitivetonoisewassolved.Andtherobustnessofthealgorithmwasenhanced.Experimentalresultsshowthatouralgorithmcanachievetheeffectivesegmentationthenoiseimages.AndtheresultsaresignificantlybetterthanthosebytraditionalFCMimagesegmentationalgorithm.Keywords:imagesegmentation;fuzzyclustering;FCMalgorithm;spatialinformation1.引言图像分割是图像处理到图像分析的关键步骤，是进一步理解图像的基础。图像分割本质上是基于某种相似性准则对像素进行分类，在期望的分割结果中，属于同类的像素特征不仅在数值上相似，其空间位置信息也有紧密联系。数据聚类方法对图像进行分割具有直观和易于实现的特点，其中最有效的是模糊C－均值（FuzzyC-means,FCM）聚类算法。但传统的FCM算法未考虑图像的空间信息，在处理受噪声污染的图像时常会得到不理想的分割结果，因此，本文提出一种改进的FCM算法。针对传统FCM算法在分割过程中只考虑本地信息的问题，本文算法加入有影响力的特征因子，即空间位置信息。实验结果表明，本文算法可显著2抑制噪声并保留实际图像的特征。2.FCM聚类简介2.1模糊集合基本知识首先说明隶属度函数的概念。隶属度函数是表示一个对象x隶属于集合A的程度的函数，通常记做μA(x)，其自变量范围是所有可能属于集合A的对象（即集合A所在空间中的所有点），取值范围是[0,1]，即0=μA(x)=1。μA(x)=1表示x完全隶属于集合A，相当于传统集合概念上的x∈A。一个定义在空间X={x}上的隶属度函数就定义了一个模糊集合A，或者叫定义在论域X={x}上的模糊子集。对于有限个对象x1，x2，……，xn模糊集合可以表示为：X}x|)x),(x{(uA~iiiA有了模糊集合的概念，一个元素隶属于模糊集合就不是硬性的了，在聚类的问题中，可以把聚类生成的簇看成模糊集合，因此，每个样本点隶属于簇的隶属度就是[0，1]区间里面的值。2.2C均值聚类C均值聚类也称K均值聚类（K-Means），已经应用到各种领域。它的核心思想如下：算法把n个向量xj(1,2…,n)分为c个组Gi(i=1,2,…,c)，并求每组的聚类中心，使得非相似性（或距离）指标的价值函数（或目标函数）达到最小。当选择欧几里德距离为组j中向量xk与相应聚类中心ci间的非相似性指标时，价值函数可定义为：)cx(JJ2c1iGk,xikc1iiik这里是组I内的价值函数。这样Ji的值依赖于Gi的几何特性和ci的位置。一般来说，可用一个通用距离函数d(xk,ci)代替组I中的向量xk，则相应的总价值函数可表示为：))c(xd(JJikc1iGk,xc1iiik为简单起见，这里用欧几里德距离作为向量的非相似性指标，且总的价值函数表示为（2）式。(1)(2)(3)3划分过的组一般用一个c×n的二维隶属矩阵U来定义。如果第j个数据点xj属于组i，则U中的元素uij为1；否则，该元素取0。一旦确定聚类中心ci，可导出如下使式子最小的uij：其他0c-xc-x，如果ik对每个1u2kj2ijij重申一点，如果ci是xj的最近的聚类中心，那么xj属于组i。由于一个给定数据只能属于一个组，所以隶属矩阵U具有如下性质：njucji.....111i且nucinjij11另一方面，如果固定uij则使（6.2）式最小的最佳聚类中心就是组I中所有向量的均值：kkGxkkx,iiG1c这里|Gi|是Gi的规模。为便于批模式运行，这里给出数据集xi（1，2…，n）的K均值算法；该算法重复使用下列步骤，确定聚类中心ci和隶属矩阵U：步骤1：初始化聚类中心ci,i=1,…,c。典型的做法是从所有数据点中任取c个点；步骤2：用式（6.4）确定隶属矩阵U；步骤3：根据式（6.2）计算价值函数。如果它小于某个确定的阀值，或它相对上次价值函数质的改变量小于某个阀值，则算法停止；步骤4：根据式（6.5）修正聚类中心。返回步骤2。该算法本身是迭代的，且不能确保它收敛于最优解。K均值算法的性能依赖于聚类中心的初始位置。所以，为了使它可取，要么用一些前端方法求好的初始聚类中心；要么每次用不同的初始聚类中心，将该算法运行多次。此外，上述算法仅仅是一种具有代表性的方法；我们还可以先初始化一个任意的隶属矩阵，然后再执行迭代过程。K均值算法也可以在线方式运行。这时，通过时间平均，导出相应的聚类中心和相应的组。即对于给定的数据点x，该算法求出最近的聚类中心ci，并用下(4)(5)(6)(7)4面公式进行修正：)(ckicx这种在线公式本质上嵌入了许多非监督学习神经元网络的学习法则。2.3模糊C均值聚类（FCM）模糊C均值聚类即众所周知的模糊ISODATA，是用隶属度确定每个数据点属于某个聚类的程度的一种聚类算法。1973年，Bezdek提出了该算法，作为早期硬C均值聚类（HCM）方法的一种改进。FCM把n个向量xi（i=1,2,…,n）分为c个模糊组，并求每组的聚类中心，使得非相似性指标的价值函数达到最小。FCM与HCM的主要区别在于FCM用模糊划分，使得每个给定数据点用值在0，1间的隶属度来确定其属于各个组的程度。与引入模糊划分相适应，隶属矩阵U允许有取值在0，1间的元素。不过，加上归一化规定，一个数据集的隶属度的和总等于1:njucji.....111i那么，FCM的价值函数（或目标函数）就是式（2）的一般化形式:2111),...,(ijcinjmijciicduJccUJ这里uij介于0，1间；ci为模糊组I的聚类中心，dij=||ci-xj||为第I个聚类中心与第j个数据点间的欧几里德距离；且是一个加权指数。构造如下新的目标函数，可求得使式子(6.10)达到最小值的必要条件：)1()1(),...,(),...,,,...,(J112111111ciijmjiijcimjmijciijmjicmcuduuccUJccU这里j=1到n，是(9）式的n个约束式的拉格朗日乘子。对所有输入参量求导，使式（10）达到最小的必要条件为：njmijjnjmijiuxu/c1和))(/(1u1)1(2cknjkijijdd(8)(9)(10)(12)(13)(11)5由上述两个必要条件，模糊C均值聚类算法是一个简单的迭代过程。在批处理方式运行时，FCM用下列步骤确定聚类中心ci和隶属矩阵U[1]：步骤1：用值在0，1间的随机数初始化隶属矩阵U，使其满足式（9）中的约束条件；步骤2：用式（12）计算c个聚类中心ci，i=1,…,c；步骤3：根据式（10）计算价值函数。如果它小于某个确定的阀值，或它相对上次价值函数值的改变量小于某个阀值，则算法停止；步骤4：用（13）计算新的U矩阵,返回步骤2；上述算法也可以先初始化聚类中心，然后再执行迭代过程。由于不能确保FCM收敛于一个最优解。算法的性能依赖于初始聚类中心。因此，我们要么用另外的快速算法确定初始聚类中心，要么每次用不同的初始聚类中心启动该算法，多次运行FCM。2.4FCM算法的应用通过上面的讨论，我们不难看出FCM算法需要两个参数一个是聚类数目C，另一个是参数m。一般来讲C要远远小于聚类样本的总个数，同时要保证C1。对于m，它是一个控制算法的柔性的参数，如果m过大，则聚类效果会很次，而如果m过小则算法会接近HCM聚类算法。算法的输出是C个聚类中心点向量和C*N的一个模糊划分矩阵，这个矩阵表示的是每个样本点属于每个类的隶属度。根据这个划分矩阵按照模糊集合中的最大隶属原则就能够确定每个样本点归为哪个类。聚类中心表示的是每个类的平均特征，可以认为是这个类的代表点。从算法的推导过程中我们不难看出，算法对于满足正态分布的数据聚类效果会很好，另外，算法对孤立点是敏感的。3FCM算法的优化传统FCM方法分割图像只考虑了灰度特征，而忽略了像素间丰富的空间依赖关系，仅将像素作为独立的点进行处理，使其对图像中的噪声和异常值较敏感，噪声像素因其异常特征常会被错误的分类，导致本属于同类的像素不能连续，无法形成有效分割区域。本文提出的基于空间位置信息的模糊聚类算法可有效解决该问题，提高传统ＦＣＭ算法的鲁棒性。63.1算法描述本文算法加入了对像素间空间位置信息的考虑，即算法主要使用像素间的空间关系和灰度级关系两个特征。定义如下：jiGSijijijH其中：第ｉ像素表示局部中心像素；第ｊ像素表示Ｎ个ｉ像素周围邻域像素的集合；Ｓｉｊ表示局部空间关系；Ｇｉｊ表示局部灰度级关系；Ｈｉｊ表示图像的局部特征。Ｓｉｊ使像素间的相互影响根据其到中心像素的距离而改变，定义如下：22ij)()(Sijijbyax其中(ｘｊ,ｙｊ)，(ａｉ,ｂｉ)分别表示ｊ像素和聚类中心ｉ像素的空间坐标．Gij使像素间的相互影响根据其灰度级的距离而改变，定义如下：2ij)()(fGiijjbafyx其中：ｆ(i)表示空间窗口内中心像素的灰度值；f(j)表示同一窗口内第ｊ个像素的灰度值。引入上述定义后，根据Lagrange乘数法，得到初始参数如下：)1/(2k)])(/()[(),(ucpijjikiiivwvwyx]),(/[]),([),(v11cqiiikicqiiikiikyxwyxyx其中ｗｉ即为通过加入空间信息后得到的初始聚类中心矩阵。最后，用带有空间信息的FCM算法将图像分割，先用式(17)与(18)对隶属度函数和聚类中心矩阵进行更新，再迭代直到满足条件|V|newoldV时收敛，从而得到最终的分割结果。(14)(15)(16)(17)(18)74实验结果4.1FCM聚类结果图4.1FCM图像分割系统84.2FLICM聚类结果图4.2FLICM图像分割系统4.3实验结果分析综上所述，本文提出了一种基于灰度信息和空间信息的自适应空间聚类方法，该算法通过在聚类目标函数中引入空间约束，扩大了特征空间，充分利用了图像中丰富的空间位置信息。用本文算法对图像进行分割，实验结果表明，该算法