均值聚类分割范文

2024-07-03

均值聚类分割范文（精选8篇）

均值聚类分割第1篇

图像分割是模式识别、计算机视觉领域的经典研究课题之一, 是由图像处理到图像分析的关键技术, 在实际生活中的应用非常广泛。作为模糊聚类算法中典型的形式, 模糊C均值 (FCM) 算法已广泛地应用在图像分割领域。但是该算法存在容易收敛到局部极值、计算量大、容易受噪声影响等不足。针对传统的FCM算法对颜色相近的区域很难分割和容易受噪声干扰的缺点, 本文对FCM分割算法进行了改进。

2 模糊C均值聚类 (FCM) 算法

传统的FCM算法通过迭代使得模糊目标函数达到最小以确定最佳聚类, 该算法的实现方法是根据数据点的特征将数据点划分为要求的几个类, 使得被划分到每个类内的数据点的特征尽量相似, 而不同类之间的数据点特征尽量不同。用隶属度函数表示样本与子集的隶属关系, 子集构成的矩阵称为模糊隶属矩阵。

设表示各类的聚类中心, 目标函数定义为:

其中, U为模糊隶属矩阵, 为模糊指数;dik A为第个样本到第i类的距离, 其定义为:

xk为Rs空间中第k个样本;表示样本点xk到聚类中心vi的欧式距离;A一般取单位矩阵。

3 基于各向异性均值漂移的FCM聚类算法 (AMSFCM)

均值漂移 (Mean Shift, 简称MS) 算法是一种有效的特征空间聚类算法, 该算法的原理简单、迭代效率高, 已广泛应用在图像分割和信息跟踪等领域。它的基本原理是通过迭代搜索特征空间中样本点信息最聚集的地方, 迭代过程中搜索点沿着样本点密集的方向移动到密度函数的局部极大值点, 对于图像分割, 就是要找到不同色彩的聚类点。

基于各向异性均值漂移的模糊C均值聚类算法 (AMSFCM) 的思想是在FCM算法的基础上对样本点进行均值漂移聚类, 由于MS算法是在特征空间中搜索到局部密度极大点, 分割图像时统一考虑图像的空间信息和颜色信息, 对于彩色图像, 每个像素点的信息可用5维特征空间中的值来表示, 即。其中, 前两个参数 (x, y) 表示像素在特征空间中的坐标, 通过色彩转换将图像中的亮度、色差都一一表示出来, 颜色空间 (L, U, V) 中的参数分别表示图像的亮度和色差, 本算法中颜色之间的色距用马氏距离来定义。颜色值差异大的色距也大, 颜色值差异小的色距也小。坐标和颜色都相近的像素点, 在其对应的5维特征空间中也相近, 因此聚类过程中我们把坐标和色距都相近的点归为一类, 实现图像分割。

在AMSFCM算法中我们使用下面的核函数

其中, hs, hr分别表示像素点特征空间和颜色空间中核函数的带宽, xs, xr分别为像素点在空间位置的坐标和该像素点的 (灰度图像q=1, 彩色图像q=3) 维向量特征。

为了自适应地调整带宽, 我们可以将核密度估计表示成如下的形式

其中, 核函数kr的带宽hr是带宽矩阵Hs的函数, 为马氏距离, 在聚类过程中, 通过调节空间信息中的带宽来更新颜色信息的带宽hr, 目的是尽量缩小马氏距离, 以便对相似像素进行较优的分割。

在实际应用中, 像素点的分布在在方向上常常是不对称的。MS算法中的核函数决定算法本身的收敛性, 同时核函数是否为各向异性决定MS算法是否各向异性。因此将带宽矩阵分解为:

根据公式 (6) 更新带宽矩阵

具体执行步骤如下:

步骤一:初始化参数:指定聚类类别数c, 11) ;设置迭代计数器b=0, 设定迭代停止阈值

步骤二:用值在[0, 1]间的随机数初始化隶属矩阵U0;

步骤三:利用公式 (7) 计算c个聚类中心

步骤五:利用公式 (4) 和公式 (5) 计算核函数的带宽;

步骤六:计算MS向量,

当MS向量小于ε1时, 迭代停止;

步骤七:将空间距离和色距相近的像素点作为一类重构图像;

步骤八:循环执行步骤三到步骤七, 当迭代终止。

4 实验结果与分析

为便于比较, 实验在给定相同的初始隶属度矩阵的情况下分别采用传统的FCM算法和改进算法对图像进行分割。

实验一:对临床脑部MR图像分割, 参数初始值设置如下:聚类类别数为灰质、白质、脑脊液、背景等4类;最大迭代次数100;模糊指数;核函数的带宽分别为迭代停止阈值分别为分割结果如下图所示:

实验二:对含有密度为1%椒盐噪声的脑部MR图像分割, 参数设置如下:核函数带宽矩阵的带宽分别为;其它参数与实验一相同。分割结果如下图所示:

图2、图5分别为使用FCM算法的分割结果, 图3、图6分别为使用的AMSFCM算法的分割结果。从实验结果可以看出, 由于原始脑部MR图像中灰质部分与白质部分的色差较小, 使用基于欧式距离的FCM算法, 由于没有考虑像素的空间信息, 在分割灰质与白质区域时容易发生颜色漂移, 造成误分割, 而且分割结果对椒盐噪声也很敏感。而改进的算法采用基于各向异性的核函数, 同时考虑了像素的本身信息与空间信息, 能够克服颜色相近区域的漂移现象, 通过使用马氏距离加大相近颜色的色距, 能够对原始图像准确的分割, 同时降低了噪声对分割的干扰。

5 结论

本文针对传统FCM算法对颜色相近区域和细长区域很难分割和容易受噪声干扰的缺点, 提出了一种改进的模糊C均值聚类图像分割方法, 即MSFCM算法。该算法在图像分割过程中使用各向异性核函数通过关联每个样本点的空间信息和颜色信息反映了图像的真实结构。通过对脑部MR图像进行分割比较, 证明本文提出的算法具有较强的抗噪性, 特别是去除椒盐噪声, 在分割颜色变化不明显的区域时更体现了改进算法的优势。

参考文献

[1]J.C.Bezdek.Cluster validity with fuzzy sets[J].Journal of Cybernetics, 1974.

[2]Y.Z.Cheng.Mean shift, mode seeking, and clustering[J].IEEE Trans on pattern analysis and machine intelligence, 1995.

[3]R.T.Collins.Mean-shift blob tracking through scale space[C].Processings2003 IEEE computer society conference on computer vision and pattern recognition.Los Alamitos:IEEE computer society, 2003.

[4]李华, 张明新, 郑金龙.融合多特征的均值漂移彩色图像分割方法[J].计算机应用, 2009.

[5]伊怀锋, 黄先武.基于均值偏移的彩色图像分割算法[J].计算机应用, 2006.

[6]J.wang, B.Thiesson.Image and video segmentation by anisotropic kernel mean shift[C].Processings of European conference on computer vision.New York, 2004.

均值聚类分割第2篇

基于K均值聚类和遗传算法的多航迹规划方法

提出了一种在未知动态环境中利用K均值聚类和遗传算法的.飞行器多航迹规划方法.针对飞行器在动态环境下需要调整飞行航迹的问题,该方法可以规划出多条可供选择的航迹,使飞行器能在障碍和威胁等环境发生变化时选择可行的飞行线路.实验结果表明,该方法能有效地完成多条航迹的规划,获得满足要求的多条飞行航迹.

作者：严江江丁明跃周成平YAN Jiang-jiang DING Ming-yue ZHOU Cheng-ping 作者单位：华中科技大学图像识别与人工智能研究所,武汉,430074 刊名：火力与指挥控制 ISTIC PKU英文刊名：FIRE CONTROL & COMMAND CONTROL 年，卷(期)： 35(3) 分类号：V279 关键词：无人飞行器聚类遗传算法多航迹规划

均值聚类分割第3篇

图像分割是指把图像分成具有不同特性的区域并提出感兴趣的目标,它是图像处理到图像分析的关键步骤。近年来,模糊C均值(FCM)算法[1,2]作为一种无监督聚类算法已成功应用在医疗诊断、目标识别和图像分割等领域,其主要目的在于将向量空间的样本点按照某种距离度量划分成一定数量的子空间。

基于图像片的图像处理思想[3,4]是近年来刚刚兴起的用于去除图像噪声的一种方法,其基本原理是将原先图像处理中的点用局部图像片来替代,增加了单个像素点的计算信息,在图像去噪领域得到了很好的应用。本文将这种以片代点的思想应用于基于模糊聚类方法的图像分割,通过实验证明本文的方法很好地克服了基于FCM图像分割所存在的问题,同时该方法也为聚类分割提供了一种全新的思路。

2. 模糊C均值聚类

2.1 传统模糊C均值算法(FCM)

模糊聚类由Dunn[1]首先提出,并由Bezdek[2]推广为一般的模糊C均值聚类算法。该算法通过最小化一个二次目标函数,将数据集(图像)划分为若干类。

FCM算法中目标函数定义如下:

其中,U={uik}∈Rn×c为隶属度矩阵,V={v1,v2,…,vc}∈Rc×p为c个聚类中心的集合,m∈[1,∞]为加权指数,通过大量研究表明,m的最佳选择范围为[1.5,2.5],通常取m=2较为理想。dik=|xk-vi|A表示第k个样本到第i类中心vi的距离,|誗|A表示A范数,一般定义为欧氏距离。

FCM的目标函数可以通过迭代更新隶属度矩阵U和聚类中心集合V达到最优解:

不断更新上述两式直到聚类中心集合V的变化值小于设定值ε(ε>0)。

传统的FCM算法在图像处理过程中主要存在两方面的缺陷:一是对于图像噪声的敏感,这主要是因为传统的FCM算法仅仅考虑了图像各个像素点灰度值之间的差别而没有将图像的其它信息考虑进去,例如空间信息等;另一个就是隶属度函数非单峰值的现象[4]。一般认为,当某一点属于某一类时,该点所对应隶属度的值应该趋向于1,该点其它类对应隶属度的值趋向于0,这就是本文所说的单峰值,如图1(a)所示。但是通过(2)式计算所得的FCM隶属度uik并无法满足单峰值特性。图1(b)中,u1(x),u2(x),u3(x)是FCM的隶属度分布情况,聚类中心为v1=1,v2=3,v3=8。u1(x)在5附近达到局部最大值,因此u1(x)并非单峰值。这种非单峰值的现象在一定程度会影响分类结果。图1(c)为本文方法的隶属度分布。

2.2 FCM的改进算法

为了克服FCM对于图像噪声的敏感性,自FCM被提出之后,人们对其抗噪性进行了大量的研究。因此在传统FCM算法中加入空间约束成为研究的热点。

Ahmed等人[5]于2002年提出了BCFCM,将像素点的局部区域均值引入到传统的FCM目标函数中,以达到抗噪效果,其目标函数如下:

其中xr表示以k点为中心的邻域Nk中像素点的灰度值,nk为集合Nk的势,即Nk中的像素个数。参数用来控制该局部项对于全局的影响。在此基础上,Chen等人[6]提出了BCFCM的快速算法,FCM_S1和FCM_S2,通过提前计算出各个像素点的局部均值来提高算法速度。

随后,Szil觃gyi等人[7]将BCFCM算法流程重组,提出了EnFCM。他们首先对图像进行均值滤波,如下:

其中,ζk表示各个像素点滤波后的灰度值。其目标函数为:

式中,hl表示图像中灰度级为l,l∈{1,2,…L}总像素点个数,L为图像的灰度级个数,对于一般的灰度图像而言,L=256。相应的更新函数为:

无论是经典的BCFCM还是改进的MFGFCM都不可避免地需要通过一些控制参数来控制局部区域约束项,而这些参数的设定往往都要根据具体实验而定,无法提出一个统一的标准方法,在实现及使用过程中,参数的设定较为繁琐。针对此问题,本文提出了一种全新的聚类方法。使用图像片来代替单个像素点的计算,不仅拉大了像素点与聚类中心之间的距离,使得聚类精度更高,同时消除了目标函数中的局部区域控制项,与传统FCM相比,在参数设置方面仅仅增加了一个片窗口大小的设置,就能够达到更好的抗噪性能。另一方面,本文还有效地消除了由于FCM所导致的隶属度函数的非单峰值现象,与理想的隶属度函数分布十分相近,以达到提高分割精度的目的。

3. 基于图像片的模糊C均值聚类的图像分割方法

3.1 图像片的思想

图像片的思想来源于图像去噪领域中的一种非局部平均的图像去噪方法[3,4],其基本思想是利用图像的局部相似信息来代替单个像素点的相似信息。这里所谓的局部相似信息即图像片。图像片包含更多的图像信息,能够比单个像素点更好描述图像的特征,因此基于图像片的图像去噪方法能够更好地保持纹理等具有重复结构的特征。本文正是在借鉴这种方法的基础上,将图像片的思想用于聚类分割算法中,以图像片代替单个像素点,通过计算图像片与聚类中心的相似性,增加像素点与聚类中心的距离,虽然在一定程度上拉大了像素点与其所对应聚类中心的距离,但同时也大大增加了该点与其它聚类中心的距离,这样从整体看来,该方法可以使分类更加精确。另一方面,以片代点的思想,可以很好地克服单个像素点灰度值对于分类的绝对影响,即克服噪声的影响,从而达到抗噪目的。本文正是使用图像片来代替单个像素点,通过计算图像片与聚类中心之间的欧氏距离,来计算该片中心点的隶属度,达到对该点进行分类的目的。

3.2 本文算法

本文将图像片代替像素点的思想用于聚类分割,提出了基于图像片的模糊C均值聚类(IPFCM)方法。

令I:Ω→Rn为定义在连续域Ω奂R2上的二维图像,当n=1时,表示灰度图像;当n=3时,表示彩色图像。本文以灰度图像为例进行介绍。

令片PI(x,y)为定义在图像I中的点(x,y)∈Ω上的以(x,y)为中心的q×q邻域中所有像素灰度值的集合。其中邻域窗口长度q=2r+1为奇数,r∈N*为邻域窗口半径。将片PI(x,y)排列成q2维的向量

即图像中的每一个像素点都对应一个q2维的向量。这对应的目标函数为:

其中,U={uik}∈RN×c为隶属度矩阵,V=(v1,v2,…,vc)为c个聚类中心的集合,N为图像中总像素数,m∈[1,∞]为加权指数,取值与FCM相同。d∧ik=|PkI-vi|A表示第k个图像片到第i类中心vi的距离,由于片PkI为一个向量,可以采用两种方式来计算该距离,一是用向量均值,二是用向量总和,为了提高计算速度,本文采用向量均值来计算该距离:

函数具有单峰值性,其中。

现只考虑单个图像片PkI,令uij,i∈{1,…,c},k∈{1,…,N}为当前图像片所属类对应的隶属度。推导过程中使用m=2,根据Lagrange乘子寻优算法有:

进一步可得到:

通过式(16)可以看出,本文方法可以很好的控制隶属度函数的单峰值性,如图1(c)所示,从中发现本文的隶属度函数分布与理想分布十分接近,这就很好的克服了FCM方法中非单峰值的特点,进而保证了聚类的精确性。聚类中心集合V的更新如下:

均值。

3.3 算法流程

本文算法具体流程如下:

步骤一:初始化参数,设置m=2,ε=0.01,c初始化聚类中心集合V。一般而言,对于灰度图像,在0到255的范围内随机生成c个整数,作为V的初始值,并通过更新达到最佳聚类中心值;

步骤二:设置图像片邻域窗口半径r,并根据公式(9)将图像中每一个像素点扩展为q2维的向量,其中q=2r+1;

步骤三:根据公式(16)更新隶属度矩阵U;

步骤四:根据公式(17)更新聚类中心V;

步骤五:比较更新前后的聚类中心,如果|Vnew-Vold|<ε,则停止迭代输出结果图像;否则回到步骤三继续更新迭代。

4. 实验结果

首先讨论图像片半径的选取,再对人工合成灰度图像不同方法的实验结果进行定量比较;最后对医学图像进行实验。

4.1 图像片大小的选择

与FCM相比,本文唯一的额外参数为图像片半径r的设置。r越大,聚类分割的抗噪性越强,但在增加算法时间复杂度的同时容易造成图像边缘点的误分类;r越小,虽然提高了图像的分割精度,减小了算法的时间复杂度,却是以牺牲抗噪性为代价的。如图2所示,第一行为噪声较小的不同图像片半径的分割结果;第二行为噪声较大的不同图像片半径的分割结果。图2中,对于噪声较小的图像而言,r=1的图像片克服图像中噪声影响的同时,很好的保持了图像边缘,在区域的交界处误分类点数很少,随着的增大,区域交界处愈加的不平滑,r=3时图像区域交界处甚至出现了“过渡区域”。当图像噪声较大时,r=1的图像片的抗噪效果明显不如r=3的图像片,但是r=3时图像区域交界处出现“过渡区域”,这将导致分割精度的大幅度降低。对于实际图像而言,虽然噪声是不可避免的,但其强度相对较低,同时结构比较复杂,图像各个区域交界处较多,因此一般采用r=1的图像片来进行处理。

图3显示了本文方法不同图像片大小的图像分割结果。图像来源于BrainWeb1,原图为加噪9%的MR脑图像。对比实验显示出,随着图像片半径的增大,分割结果变得更为平滑,灰质与白质的边缘部分细节丢失更为严重。

本文对MR图像的分割精度进行了定量分析。目前,已有很多种图像分割精度的评判标准,本文采用较常用的两种方法:JS(Jaccard similarity)方法[8]和DC(Dice coefficient)方法[8],其度量公式依次为:

(18)、(19)式中,S1,S2表示需要比较的两幅分割结果,这里使用分类分割后的结果与BrainWeb中的人工分割结果进行比较。|誗|表示相应区域中的像素点个数。这里采用公式(18)对图3的分割结果进行精度计算,如表1所示。通过表1的定量分析证明了上述现象。尽管很好的克服了噪声的影响,但是图像分割精度过差,r越大分割精度也就越低,无法满足实际需要。当r=0时,此时的IPFCM方法退化为FCM方法,分割图像的细节能够得到较好的保持,但对于噪声的敏感性是无法避免的,这也是FCM本身无法克服的缺陷。从实验结果可以看出,r=1的图像片处理结果无论在分割精度、细节保持还是克服噪声方面,都具有很好的效果。

实验过程中,基本参数设定为:m=2,ε=0.01,所有聚类方法均使用半径r=1的窗口,人工合成图像中c=3,医学图像中c=4,聚类中心则根据c的大小随机生成相应的聚类中心集。

4.2 合成图像

图4为各个聚类方法的分割结果比较。该图像来自IBSR,选用256*256大小的带噪图像对FCM、BCFCM、EnFCM、FGFCM、MFGFCM、IPFCM这六种方法进行方法比较。其中,只有FCM与IPFCM不需要额外的参数设定,BCFCM、EnFCM、FGFCM、MFGFCM均需要一个或几个控制参数,这些参数的设定并非本文重点,这里不一一列举。图4中,FCM方法对于噪声的敏感显而易见,BCFCM不仅无法达到满意的抗噪结果,其效率也十分低下,运行开销较大;EnFCM与FGFCM方法虽然比较地好提高了运行速度,但是分割结果还是可以看到该方法无法消除的部分噪声;从结果来看,MFGFCM与IPFCM的抗噪性最好,细节上本文方法要优于MFGFCM。

对于合成图像的分割精度计算,采用如下公式:

计算结果如表2所示。通过表2的对比,在相同噪声的情况下,IPFCM的分割精度最高。这些噪声图像都是在图4(a)的原图基础上增加不同的噪声,其中,Gaussian1、Gaussian2、Gaussian3都是均值为0,方差依次为0.01、0.03、0.05的高斯白噪声;Impluse为椒盐噪声;Mixed1、Mixed2分别为方差为0.04、0.08的混合噪声。

由于噪声强度问题,以上分析只能体现出MFGFCM与IPFCM拥有较好的抗噪性,但两者之间的比较不够突出,图5使用了另外一幅合成图像,从中明显可以看出IPFCM的抗噪性明显优于MFGFCM。

4.3 MR脑图像

本文对核磁共振(MR)图像使用EnFCM、MFGFCM、IPFCM三种方法在不同噪声水平下的分割结果进行比较。由于本文是针对聚类方法提出的新思想,而不是针对脑图像应用,没有加入MR脑图像去偏移场的计算,因此本文选用T1模态1mm切片厚度无偏移场的不同噪声水平下的脑图片,图6第一列的三幅图像分别为加噪0%、3%、9%的第96针脑图像,其分割结果如图6第二至第四列图像所示。

通过EnFCM、MFGFCM、IPFCM三种方法的比较,还是可以看出IPFCM在抗噪方面是最好的。

表3列出了图6中各种方法分割后灰质、白质的分割精度。通过定量分析得出在克服噪声影响的同时IPFCM在同类方法中的分割精度较高,且无需过多参数设定,具有较强的可靠性。

以上多组不同类型的实验,对IPFCM进行了全面的分析,不仅表明了IPFCM的有效性和精确性,同时还对图像片半径的选择进行了讨论。一般情况下,建议设置半径为r=1。4.1中的实验表明图像片窗口越大,IPFCM的抗噪性就越强,但是边缘模糊现象就越明显。4.2和4.3中的实验显示,当图像片半径为时,无论合成图像还是MR脑图像,IPFCM都可以得到较高的分割精度,因此图像片半径为具有很强的适用性。

5. 结论

本文提出一种全新的基于图像片进行模糊C均值聚类的图像分割理念与IPFCM方法,通过实验对比发现,IPFCM很好地克服了FCM分割方法对于噪声的敏感以及隶属度函数的非单峰值的缺陷,具有很好的抗噪性和较高的分割精度,图像的隶属度函数与理想隶属度函数十分接近。与同类方法相比,IPFCM不需要过多的参数设定,具有很好的鲁棒性和较强的可靠性。同时,本文将聚类中心的每一个成员扩展为一个向量,并给出了向量聚类中心的更新公式,为日后将多种图像特征加入FCM对图像进行分割提供了充分的理论基础。需要指出的是,本文采用正方形图像片,并未将图像像素点的方向信息考虑进去,使得图像细节部分容易被起周边像素影响而丢失信息。另一方面,当使用半径较大的图像片时,将会不可避免的降低分割精度,可以对分割后的图像进行二次聚类以提高分割精度。如何在图像片中加入方向信息,以及引入哪些图像特征将是未来研究工作的重点。

参考文献

[1]J C Dunn.A fuzzy relative of the ISODATA process and its use in detecting compact well separated cluster[J].Journal of Cybemet,3:32～57,1974.

[2]J C Bezdek.Pattern recognition with fuzzy objective function algorithms[M].Norwell,MA,USA:Kluwer Academic Publishers,1981.

[3]A.Buades,B.Coll,and J.-M.Morel.A non-local algorithm for image denoising[J],Proc.IEEE Conf.Computer Vision and Pattern Recognition,vol.2,pp.60-65,Jun.2005.

[4]F.Hoppner,F.Klawonn.Improved fuzzy partitions for fuzzy regression models[J],Int.J.Approx.Reason.32(2)85-102,2003.

[5]MN Ahmed,SM Yamany,N Mohamed,AA Farag,Moriarty T.A modified fuzzy c-means algorithm for bias field estimation and segmentation of MRI data[J].IEEE Trans Med Imag21,193-199,2002.

[6]S Chen,DQ Zhang.Robust image segmentation using FCM with spatial constraints based on new kernel-induced distance measure[J].IEEE Trans Syst Man Cybern Part B34,1907-1916,2004.

[7]L Szilágyi,Z Benyó,SM Szilágyi,HS Adam.MR brain image segmentation using an enhanced fuzzy c-means algorithm[J].Proc25th Ann Int Conf IEEE EMBS,2003:724-726.

均值聚类分割第4篇

传统的FCM算法虽然快速简单, 但并没有考虑目标物体的形状等先验知识, 没有对样本特征进行优化, 而是基于样本特征间的欧氏距离进行聚类。对噪声和异常点缺乏足够的鲁棒性, 分割时间依赖于图像的大小, 因此图像越大, 分割时间越长。在过去几十年中, 随着对模糊C-均值聚类算法的深入研究, 针对其不足, 国内外学者提出了许多改进的FCM算法, 并融合其他技术以提高图像分割性能。Ahmed等[2]结合空间邻域信息, 提出FCM_S算法, 取得了好的分割效果;陈和张等[3]人又在此基础上提出了其变体算法FCM_S1和FCM_S2, 减少了运算量。Wang X等[4]提出运用权重思想确定像素点隶属度, 抑制了噪声的干扰。结合空间信息的FCM增强算法已有效地用于图像降噪及图像分割[5]。后来很多学者提出了基于核函数的模糊C-均值聚类算法 (KF-CM) , 通过引入核函数将传统的FCM推广到了核空间, 对图像的特征具有较好的适应性, 同时核函数对噪声具有很好的抑制能力。因此, 学者们在FCM算法中引入核函数。Zhang和Chen等用非线性函数对图像像素进行空间变换, 将FCM_S算法、FCM_S1算法和FCM_S2算法扩展到相应的核版本, 以此来增强FCM_S算法、FCM_S1算法和FCM_S2算法的抗噪性能, 在新的特征空间按照FCM算法对图像各点进行聚类。

本文结合空间邻域和灰度信息, 引入核函数, 针对RF-CM[6]算法未考虑噪声和邻域之间关系, 无法有效避免噪声影响的缺点, 提出基于空间信息的核均值聚类分割算法。实验表明, 提出算法分割结果保留了图像更多细节和边缘信息, 同时具有较强的抗噪声能力。

1 RFCM算法

FCM算法最早由Dunn提出, 而后由Bezdek[1]进行完善。传统的FCM算法是一种迭代算法, 将图像中所有的像素点当作孤立的数据进行聚类, 是一种无监督分类方法。由于原始的FCM算法未考虑图像的空间信息, 这使得算法在运行过程中对噪声十分敏感。FCM算法通过将图像I={f (i, j) , 0≤i≤M, 0≤j≤N}分成c类, 实现图像的分割, 其中f (i, j) 为特征数据。

RFCM算法是广义模糊C均值聚类算法的改进算法[11]是FCM的一个改进算法。通过在隶属度函数中引入一个单一数据点的量, 使得分配更清晰。

RFCM的目标函数如下:

使用拉格朗日数乘法最小化式 (1) , 新的聚类中心vi和隶属度函数uij更新方程如下:

为满足uij, 0≤uij≤1, α (0≤α≤1) , aj=α·min{‖xj-vs‖2|s∈{1, 2, …, c}}参数控制收敛速度, 当α=0时, RFCM算法等价于FCM。

在参数α选取适当的情况下, RFCM不仅可以更快速地聚类, 还具有良好的聚类性能。但是, RFCM算法中噪声被视为正常图像的一部分, 未考虑噪声和邻域之间的关系, 故无法有效避免噪声的影响。

2 改进的基于空间信息的核聚类算法

2.1 核表示和核函数

文献[3]提出了基于核函数的FCM算法KFCM。Φ:x∈XRd|→Φ (x) ∈RH (d<<H) 是由一个非线性映射到一个高维特征空间F的变换, 在F中, 欧氏距离‖x-y‖2被‖Φ (x) -Φ (y) ‖2取代, 定义为:

每一个线性算法仅利用内积就可以很容易地扩展到非线性, 只要通过满足Mercer条件的核函数[15]。因为高斯核函数对应的特征空间是无穷维的, 有限的样本在该特征空间肯定是线性可分的, 所以较常用。本文中采用高斯核函数。这里, 核函数K (x, y) 被用来计算F的内积。定义核函数如下:

将式 (4) 带入 (5) 式得到:

样本方差来估计σ2被定义为:

2.2 KSNRFCM算法

本算法引入核函数并提出结合局部空间和灰度信息的一个新的模糊C均值聚类图像分割算法 (KSNRFCM) 。通过内核替代 (即方程 (6) ) , 所述核广义模糊C-均值聚类目标函数如下:

利用拉格朗日乘子法得到隶属度函数和聚类中心:

NKRFCM算法的基本步骤如下:

步骤1:确定聚类数c, 模糊加权指数 (此处直接定义为2) , 迭代停止阈值ε, 令初始迭代次数为n=0。

步骤2:初始聚类中心vi (0) 。

步骤3:根据式 (9) 计算新的隶属度uij。

步骤4:根据式 (10) 计算新的聚类中心vi。

步骤5:停止条件|Unew-Uold|<ε, 算法终止, 否则, 令n=n+1, 转至步骤3。 (U=[u1, u2, …, uc]是聚类原型向量)

步骤6:按照最大隶属度原则对图像进行分割。

3 实验结果与讨论

为验证本文算法有效性, 实验中将算法用于lena图像进行分割实验, 并与FCM、RFCM、NRFCM以及KGFCM分割方法进行了比较。为验证算法可行性, 在Visual C++6.0环境下进行实验, 在实验中选取λ=0.02。所有算法在Microsoft windows XP计算机上进行。

3.1 含噪图像实验结果分析

为验证试验结果有效性, 对图1 (a) 原始图像加入高斯噪声和椒盐噪声, 分别运用RFCM、NRFCM算法与本文所提出算法进行比较, 设置分类数c=2。

图1 (b) 为加入均值为0, 局部方差为0.01的高斯噪声后的图像, 图1 (c) 为RFCM算法分割结果, 图1 (e) 为NRF-CM算法分割结果, 图1 (f) 为本文算法分割结果。

可以看出, 利用本文所提出算法进行图像分割, 噪声抑制效果比RFCM算法和NRFCM算法更好。分割后, 方形零件周界清晰。

3.2 图像分割细节实验结果分析

将本文算法应用于lena图像进行分割实验, 并与FCM、RFCM、NRFCM以及KGFCM分割方法进行了比较。

如图2, (b) 是FCM算法分割结果; (c) 为KGFCM算法分割结果; (d) 为RFCM算法分割结果; (e) 是NRFCM算法分割结果; (f) 本文提出算法分割结果。

对比图2, 结合图3本文算法分割lena图对比明显区域描述看出:对于图中的脸部、嘴巴和帽子流苏部分的细节与边缘部分 (红框区域) , 本文所提算法分割效果更好, 细节显示更充分。结合图像的分割性能指标 (表1) , 本文所提出算法在分割过程中保留了更多图像的细节信息。

3.3 分割性能指标分析

为了对算法进行客观、定量的评价, 本文采用常用的图像分割评价标准最大香农熵Hmax[6]对上述分割结果进行评价, 定义如下:

其中, P0, P1分别表示分割图像的二值输出为1和0的概率。对大多数图像而言, 香农熵代表图像的信息量, 如果分割后的图像香农熵越大, 分割图像从原始图像中得到的信息量越大。分割图像细节越丰富, 总体分割效果越好。这里分别对lena图像、flower图像以及脑出血放射图像进行仿真验证。

得到分割性能指标如下表所示:

4 结束语

本文提出结合空间邻域和灰度信息的新的模糊C-均值聚类图像分割算法 (SNRFCM) , 然后在新的目标函数中采用内核感应距离代替欧氏距离, 同时通过引入核函数, 提出了一种基于空间信息的核聚类图像分割算法 (SKNRFCM) 。通过使用一个惩罚因子, 有效地减少噪声对聚类结果的负面影响。通过使用聚类权重, 有效避免部分噪声影响。实验结果表明, 通过与FCM、RFCM、NRFCM和KGFCM算法进行比较, 本文所提出算法具有良好的分割性能, 尤其在图像分割细节和边缘方面, 同时具有较好的抗噪声能力。

摘要：RFCM是对传统的模糊C均值聚类算法的一个改进算法。但未考虑噪声和邻域间的关系, 故无法有效避免噪声影响。为克服以上缺点, 提出结合空间邻域和灰度信息的核模糊C均值聚类图像分割算法。通过使用一个距离惩罚项, 有效地减少噪声对聚类结果的负面影响;通过使用聚类权重有效避免块噪声;引入空间约束项、采用内核感应距离, 使分割结果更好地保留了图像细节, 分割更加准确。实验结果表明, 与FCM、RFCM、NRFCM和KGFCM比较, 该算法保留更多图像细节和边缘信息, 同时具有较强的抗噪声能力。

关键词：RFCM,图像分割,模糊C均值聚类,核函数

参考文献

[1]BEZDEK JC.Cluster Validity with Fuzzy Sets[J].Cybernetics and Systems, 1974, 3 (3) :56-75.

[2]AHMED MN, YAMANY SM, MOHAMED N, et al.A Modified Fuzzy C-means Algorithm for Bias Field Estimation and Segmentation of MRI data[J].IEEE Trans Med Imag, 2002, 21:193-199.

[3]Zhang DQ, Chen SC.A Novel Kernelized Fuzzy C-Means Algorithm with Application in Medical Image[J].Artificial Intelligence in Medicine, 2004, 32 (1) .

[4]Wang X, Wang Y, Wang L.Improving fuzzy c-means clustering based on feature-weight learning[J].Pattern Recognition Letters, 2004, 25:1123-1132.

[5]WU M, SCHOLKOPF B.A local learning approach for clustering[J].Adv.Neural Inf.Process Syst, 2007, 19:1529-1536.

均值聚类分割第5篇

1 K-均值聚类算法

聚类是对数据空间中数据对象进行分类,位于同一类中的数据对象之间的相似度较大,而位于不同类之间的数据对象差异度较大。聚类是一种无监督学习,能自动对数据集进行划分。常见的聚类算法有:K-means,DBSCAN,CURE等算法。K-means即K-均值聚类,该算法确定的K个划分到达平方误差最小,当聚类是密集的,且类与类之间区别明显时,效果较好。并且对于处理大数据集,该算法是相对可伸缩和高效的,计算的复杂度为O(NKt),其中N是数据对象的数目,t是迭代的次数,具体步骤如下:

第一步,选K个初始聚类中心,z1(1),z2(1),…,zK(1),其中括号内的序号为寻找聚类中心的迭代运算的次序号。聚类中心的向量值可任意设定,例如可选开始的K个模式样本的向量值作为初始聚类中心。

第二步,逐个将需分类的模式样本{x}按最小距离准则分配给K个聚类中心中的某一个zj(1)。假设i=j时,则zi(k)= zj(k),其中k为迭代运算的次序号,第一次迭代k=1,Sj表示第j个聚类,其聚类中心为zj。

第三步,计算各个聚类中心的新的向量值zj(k+1),j=1,2,…,K,求各聚类域中所包含样本的均值向量:其中Nj为第j个聚类域Sj中所包含的样本个数。以均值向量作为新的聚类中心,可使如下聚类准则函数最小:在这一步中要分别计算K个聚类中的样本均值向量,所以称之为K-均值算法。

第四步,若zi(k+1)≠zj(k),j=1,2,…,K,则返回第二步,将模式样本逐个重新分类,重复迭代运算;若 zi(k+1)= zj(k),j=1,2,…,K,则算法收敛,计算结束。

2 本文算法

本文提出的结合K-均值聚类的分水岭算法,目的是对已经聚类的颜色目标进行分割,从而完成PCB彩色图像的分割。

2.1 分水岭算法

分水岭分割方法,是一种基于拓扑理论的数学形态学的分割方法,其基本思想是把图像看作是测地学上的拓扑地貌,图像中每一点像素的灰度值表示该点的海拔高度,每一个局部极小值及其影响区域称为集水盆,而集水盆的边界则形成分水岭。分水岭的概念和形成可以通过模拟浸入过程来说明。在每一个局部极小值表面,刺穿一个小孔,然后把整个模型慢慢浸入水中,随着浸入的加深,每一个局部极小值的影响域慢慢向外扩展,在两个集水盆汇合处构筑大坝,即形成分水岭。对于分水岭变换(Watershed by Immersion),令f:D是一幅灰度图像,它的最大和最小灰度值为h_max和h_min。定义一个从h_min到h_max的水位h不断递增的递归过程。在这个过程中每个与不同的局部最小相关的汇水盆地都不断扩展,定义X(h)记作在水位h时候汇水盆地的集合的并。在h+1层,一个连通分量T(h+1)或者是一个新的局部最小,或者是一个已经存在的X(h)中的一个盆地的扩展。对于后者,按邻接关系计算高度为h+1的每一个点与各汇水盆地的距离。如果1个点与2个以上的盆地等距离,则它不属于任何盆地,否则它属于与它距离最近的盆地。这样从而产生新的X(h+1)。把在高度h出现的局部最小记作MIN(h)。把Y(h+1,X(h))记作高度为h+1同时属于X(h)的点的集合。

undefined

分水岭变换Watershed(f)就是X(h_max)的补集。

2.2 结合K-均值聚类的分水岭算法

2.2.1 颜色空间选择

选择合适的颜色空间是成功进行彩色图像分割的首要环节,计算机处理分析系统接收到的PCB彩色图像是在RGB颜色空间中表示的。由于彩色显示器采用红、绿和蓝来生成目标颜色,所以RGB颜色空间是计算机图形学最通常的选择,这样可以简化系统的构架与设计。RGB颜色空间用三维的笛卡尔坐标系统来表示,如图1所示。

注:WHITE:白色;BLACK:黑色;RED:红色;BLUE:蓝色;CYAN:青色; GRE- EN:绿色;YELLO:黄色;MAGENTA :洋红。

其中,每个顶点的三色叠加值如表1所示。

可见RGB颜色空间的色彩是比较丰富的,同时还是显示器硬件系统的默认颜色空间,做图像处理时的速度比其他颜色空间快,所以本文选择RGB颜色空间。

2.2.2 图像分割算法

将PCB彩色图像在RGB颜色空间中分别提取R、G、B三个灰度图像。将每幅灰度图像的像素值考虑成一组二维数学矩阵,在其中随机选取2个像素值x(i, j)和y(i, j)作为初始聚类中心,根据下列公式对剩余的像素值进行聚类

undefined

其中,当z(i, j)取到x(i, j)或y(i, j)时,上述公式中D为0,当z(i, j)为异于x(i, j)和y(i, j)的像素值时,设置D0为0.05,验证下列公式

undefined

设置阈值T,对T进行取值,满足上述公式则完成三幅灰度图像的聚类。对每幅聚类后的灰度图像进行分水岭分割,即对已经聚类好的灰度图像,利用公式(1)寻找相同高度的像素值,对分水岭变换后的三幅灰度图像进行单通道图像整合,合成RGB空间的彩色图像,即完成PCB彩色图像的分割。算法流程如图2所示。

3 实验与分析

利用本文提出的算法,在MATLAB 7.1环境下,对用CCD摄像机获取的PCB彩色图像进行仿真,如图3所示,可以看到,本文提出的算法可以很好地分割PCB彩色图像,分割清晰,PCB的结构保持完整,同时由于所采取的方法均为无监督算法,所以整体程序所消耗的时间较短,仅为7.254 s,说明了本文算法的高效性。

4 结论

本文成功地分割了PCB彩色图像,提出了结合聚类算法的分水岭算法,通过实验仿真可以看到,所提出的算法可以清晰地分割PCB彩色图像,为之后的PCB检测工作奠定了基础。

参考文献

[1]杜颜颜,杨帆,王晓颖.一种彩色PCB图像的边缘检测算法研究[J].电视技术,2011,35(13):112-115.

[2]李刚,韩建国.PCB图像检测中阈值化分割的研究[J].北京化工大学学报,2002,29(4):72-74.

[3]赵晓霞,王明泉,李高亮.一种基于偏微分方程的PCB图像增强方法[J].电视技术,2011,36(3):33-35.

[4]孙晓霞,熊红云.PCB检测系统中的图像预处理[J].中国科技信息,2007,30(22):116-117.图3实验仿真图

[5]曾成,赵锡钧,徐欣,等.PCB检测中图像分割技术研究[J].传感器与微系统,2011,30(2):26-28.

[6]曾歆懿,章云,季秀霞,等.基于分水岭变换的PCB图像分割[J].质量工程卷,2007,20(1):22-26.

均值聚类分割第6篇

关键词：电煤泥浮选,模糊C均值聚类,二维直方图加权的模糊C-均值聚类,分水岭,图像分割

在煤泥浮选过程中, 浮选泡沫层起着极其重要的作用, 包含有大量与浮选过程变量及浮选结果相关的信息。泡沫尺寸等特征与浮选指标存在着极强的相关性, 因此浮选图像中气泡的准确提取成为关键。现场采集的煤泥浮选泡沫图像, 其灰度直方图多为单峰, 且像素灰度分布比较集中, 因此煤泥背景和前景泡沫的灰度值对比度低, 边缘较模糊, 使得气泡边缘难以提取;而且有些气泡的亮点不明显, 在变为二值图像时, 当阈值选取不合适时不能准确提取其亮点。为此本文采用基于二维直方图加权的模糊C-均值聚类的算法将图像像素大致划分为三类, 即气泡顶点、气泡表面及背景三种像素, 这样就使泡沫图像相对于背景像素更加分明, 气泡顶点像素被准确提取, 为后续的基于标记分水岭分割的标记提取提供良好的条件。

1 模糊C-均值聚类煤泥浮选泡沫图像的分割处理

模糊C均值 (FCM) 聚类分割算法是基于对模糊目标函数的优化基础上的一种数据聚类方法, 它是将向量空间的样本点按照某种距离度量划分成C个子空间, 聚类的结果特征是一个数据对聚类中心的隶属程度, 目前在图像处理等领域中得到广泛的应用。

1.1 模糊C均值聚类算法 (FCM)

1.2 加权的模糊C均值聚类算法 (WFCM)

由于FCM没有考虑样本矢量特征对分类的不同影响, 也未将各个向量对于聚类效果的影响, 提出了基于特征加权的FCM算法。在FCM的基础上, 加权模糊C均值聚类的目标函数为:

1.3 加权的模糊C均值聚类算法的分类

在图像处理中, 使用FCM聚类算法进行聚类时, 每一个像素点都是样本, 而且都要计算它对于每一类的隶属度, 随着图像尺寸的增大, 相应的样本个数也随之增大, 这就导致处理时间加大, 从而影响了图像处理的实时性要求;而加权模糊C均值聚类的图像分割方法是将图像空间信息融入到标准FCM算法中, 将图像从像素空间映射到其灰度直方图特征空间, 能快速有效地分割图像, 降低了运算量和算法的复杂度。对于给定灰阶的图像, 无论图像的尺寸如何变化, 而分类的样本数是固定的, 不随尺寸的增大而增多, 即聚类算法的处理处理速度不会因图像的增大而减慢。加权的模糊C均值聚类算法分为一维直方图加权的模糊C均值聚类和二维直方图加权的模糊C均值聚类算法。

1.3.1 一维直方图加权的模糊C均值聚类的具体算法

设图像尺寸为M×N, 各灰度级出现的频度为:

其中n (l) 是灰度为l的像素在图像中出现的次数, L为灰度级数目, M×N为图像的尺寸。且满足:

1.3.2 二维直方图加权的模糊C均值聚类的具体算法

在一维加权的图像分割算法中, 由于噪声的干扰, 使目标和背景分布相互重叠而不可区分, 使得基于一维灰度直方图模糊聚类分割方法由于权重的误差出现偏差, 从而不能获得满意的分割结果。由于图像中像素与其邻域像素间存在较大的相关性, 因而在二维直方图加权的分割算法中, 平滑图像的像素值恰恰是其领域像素的反映, 当利用了像素空间相关这一空间信息后, 目标和背景的分布就会比在一维直方图容易区分。这样, 除了利用像素点的灰度信息外, 还利用了像素点与其邻域间相关的空间信息, 就一定会产生更好的分割效果。

2 实验与结果分析

对于在煤泥浮选现场所获得的泡沫图像, 像素尺寸为512×512, 由于泡沫图像按灰度大体分为三类, 即气泡顶点、气泡表面、背景的灰度。因而取聚类种类c=3, m=2, ε=10-5, 最大迭代次数为100;在模糊C均值聚类算法和一维直方图加权的模糊C均值聚类算法中由于一般认为比较合适的聚类中心是出现在样本点比较密集的地方, 因而聚类中心取:

其中rand (3, 2) 是在Matlab程序中生成的一个3行2列的0-1的随机矩阵, 在二维直方图加权的模糊C均值聚类算法中平滑图像 (x, y) 是原图像经3*3均值滤波后的平滑图像。对于浮选泡沫图像分别使用FCM、一维直方图WFCM和二维直方图WFCM进行图像分割, 原图像及经三种算法聚类后的图像分别如图1、2、3、4所示。从聚类结果可知FCM聚类的迭代次数为43, 聚类时间为9.312s;一维直方图加权WFCM聚类的迭代次数为23, 聚类时间为0.062s;二维直方图加权WFCM聚类的迭代次数为23, 聚类时间为7.063s。由此可知基于一维直方图的WFCM聚类速度最快, 其次为二维直方图的WFCM, FCM聚类速度最慢;对于所用迭代次数来看, 一维直方图的WFCM与二维直方图的WFCM相同, 均少于FCM的迭代次数;从聚类效果来看, FCM与二维直方图的WFCM效果相差不大, 但FCM细节效果不如二维直方图的WFCM, 而一维直方图的WFCM的聚类效果是最差的, 即使它的聚类时间快。通过三种聚类方法的对比可知, 二维直方图的WFCM聚类效果最好, 使气泡对比度增加, 气泡边缘更加清晰。

3 结论

基于二维直方图的WFCM聚类不仅迭代次数少, 收敛较快, 而且对于气泡区域定位准确, 检测出了不易提取的气泡亮点, 增加了气泡边缘与背景的对比度, 使得气泡更显清晰。能够准确地反映出图像的真实信息。使得通过二维直方图的WFCM聚类后的图像在标记点的提取中更为准确, 为后续的分水岭的图像分割奠定基础。

参考文献

[1]Kaartinen J., Hatonen J., Hyotyniemi H., et al.Machine vision based control of zinc flotation-A case study.Control Engineering Practice, 2006, 14 (12) :1455-1466.

[2]李志梅.基于模糊聚类的图像分割算法研究[D].湖南大学硕士学位论文, 2008, 2-3.

[3]高新波.模糊聚类分析及其应用[M].陕西:西安电子科技大学出版社, 2004.

[4]P R NIKHIL.J C BEZDEK.On cluster validity for the fuzzy C-means model[J].IEEE Transactions on Fuzzy Systems, 1995, 3 (3) :370-379.

基于层次的K-均值聚类第7篇

聚类是数据分析中的一项重要技术,是众多科学领域和工程技术中的一项基础性工作。这种技术被广泛应用于生物学、天体物理学、模式识别、数据挖掘、计算机图像处理、最优化问题等。聚类是把d维特征空间中的n个数据点分成k个不同的类,使类内数据点的相似度高、不同类间的数据点的相似度低[1,2,3,4]。这里的相似在特征空间中表现为距离近,所以距离可以用来对2个数据点进行相似性测度。

K-均值聚类是在各个领域用得最多的聚类算法之一。它的主要特点是:对给定的数据集可能存在的类数目需要作出假设;对用来代表某类的类中心需要在迭代计算前做初始化;迭代计算出的类中心容易陷入某些满足局部最优的值中。可以看出,设定恰当的类数目和初始化合适的类中心是K-均值聚类算法中的关键。文献[5]中用基于模糊K-均值的分裂算法(FBSA)来确定类数目,文献[6]中用聚类中心初始化算法(CCIA)来确定初始的类中心,它们都不同程度地提高了聚类精度。这里介绍一种基于层次的K-均值聚类(HKMA)。在该算法中,对传统K-均值聚类中划分矩阵里的元素(“隶属”概率)做了形式上的改变,同时引入一个调控因子。这里希望通过调控因子来决定聚类结果中的类中心和实际类数目。

2传统K-均值聚类

2.1 K-均值聚类

K-均值聚类的首要目标是迭代计算出类中心[7]。这些类中心是通过最小化下面的代价函数得到的。

$c o s t f (Ρ, U) = \sum_{i = 1}^{n} \sum_{j = 1}^{c} p_{i j} x_{i} - u_{j}^{2} (1)$

这里n是给定数据集的数据点的总个数;c是潜在的类数目;X={x1,x2,…,xn}是特征数据集;U= {u1,u2,…,uc}是类中心集;P=(pij)n×c是一个划分矩阵(“隶属”概率集),其中元素pij是数据点xi属于由类中心uj代表的类j的成员的概率,对任意的i=1,2,…,n满足 $\sum_{j = 1}^{c} p_{i j} = 1$ ,对任意的i=1,2,…,n和j=1,2,…,c满足pij≥0。

最小化代价函数cost f(P,U)可以得到划分矩阵和代表各个类的类中心的迭代表达式:

K-均值聚类在迭代过程中,c个类中心会不断移动,以使得代价函数cost f达到最小值。其中迭代的每一步,一个数据点都是确定性地属于某一类,这由式(2)可以看出。这只是判定一个点属于某一类的一种方式。事实上,在以距离度量两点相似性的聚类算法中,一个点属于某一类是一个随该点与该类中心距离衰减的函数。基于此,完全可以用模糊划分矩阵来代替一般划分矩阵,使一个点以一定概率属于某一类。这就是模糊K-均值聚类。

2.2 模糊K-均值聚类

模糊K-均值聚类的首要目标也是迭代计算出类中心[7]。这些类中心通过最小化下面的代价函数得到。

$c o s t f_{b} (Ρ, U) = \sum_{i = 1}^{n} \sum_{j = 1}^{c} p_{i j}^{b} ∥ x_{i} - u_{j} ∥^{2} (4)$

这里概率上的指数b叫模糊度,是一个用来控制不同类别的混合程度的自由参数。

最小化代价函数Costfb(P,U)可以得到模糊划分矩阵和各个类中心的迭代表达式:

$\begin{array}{l} p_{i j} = {\begin{matrix} (\sum_{k = 1}^{c} (\frac{∥ x_{i} - u_{j} ∥}{∥ x_{i} - u_{k} ∥})^{\frac{2}{b - 1}})^{- 1} & i f ∥ x_{i} - u_{k} ∥ > 0 \\ 1 & i f ∥ x_{i} - u_{j} ∥ = 0 \\ 0 & i f ∥ x_{i} - u_{k} ∥ = 0 \end{matrix} (5) \\ u_{j} = \sum_{i = 1}^{n} p_{i j}^{b} x_{i} / \sum_{i = 1}^{Ν} p_{i j}^{b} (6) \end{array}$

模糊K-均值聚类与K-均值聚类相比有2点不同:一是引入了模糊“隶属”关系,使一个样本点以一定概率属于某一类别,这样更接近一个事实,即K-均值聚类是一种基于距离的聚类方法;二是引入了隶属度这个自由参数,可以控制不同类别的混合程度,使聚类达到更好的结果。当取b=1,且使P中每一个样本点属于某类别的n个概率值中,最大者置为1,其他置为0时,模糊K-均值聚类就过渡到了K-均值聚类。K-均值聚类是模糊K-均值聚类的一种近似,一个特例,这也正是模糊K-均值比K-均值的聚类精度更高的原因。

3基于层次的K-均值聚类(HKMA)

对一个给定类构型的数据集,该类构型的平均总代价(平均总能量)可表示为:

$[E] = \sum_{i = 1}^{n} \sum_{j = 1}^{c} p_{i j} E_{i j}$

其中: Eij=‖xi-uj‖2 (7)

数据集类构型的信息熵可表示为:

$Η = - \sum_{i = 1}^{n} \sum_{j = 1}^{c} p_{i j} \log_{2} p_{i j}$

这里n是给定数据集的数据点的总个数,c是潜在的类数目;X={x1,x2,…,xn}是特征数据集,U= {u1,u2,…,uc}是类中心集,P=(pij)n×c 是一个模糊划分矩阵(模糊“隶属”概率集),其中元素pij是数据点xi属于由类中心uj代表的类j的成员概率,对任意的i=1,2,…,n满足 $\sum_{j = 1}^{c} p_{i j} = 1$ ,对任意的i=1,2,…,n和j=1,2,…,c满足pij≥0,E=(Eij)n×c是对应于P的代价(能量)矩阵,Eij是数据点xi以概率pij属于类j的成员时的代价(能量)。

在平均总代价(平均总能量)不变的约束下,为得到信息熵的最大值,对熵函数求导可得吉布斯概率分布:

$p_{i j} = \frac{\exp (- β E_{i j})}{Ζ_{i}} (8)$

其中Zi是数据点xi的配分函数,表达式为:

$Ζ_{i} = \sum_{k = 1}^{c} e x p (- β E_{i k}) (9)$

这里的β是拉格朗日乘子,其值由约束公式(平均总代价不变)来确定。

对一个给定类构型的数据集,可以认为不同的数据点“隶属”于自己的类的概率是独立的。这样总的配分函数可表示为:

$Ζ = \prod_{i = 1}^{n} Ζ_{i}$

由总配分函数可以得到该方法所需要的代价函数(自由能):

$\begin{array}{l} F = - \frac{1}{β} \ln Ζ \\ = - \frac{1}{β} \sum_{i = 1}^{n} \ln (\sum_{j = 1}^{c} e x p (- β ∥ x_{i} - u_{j} ∥^{2})) (10) \end{array}$

由式(7)～(8)知模糊划分矩阵:

$p_{i j} = \frac{\exp (- β ∥ x_{i} - u_{j} ∥^{2})}{\sum_{k = 1}^{c} e x p (- β ∥ x_{i} - u_{k} ∥^{2})} (11)$

为了使代价函数(自由能)最小,对代价函数求导,得到类中心表达式:

$u_{j} = \sum_{i = 1}^{n} x_{i} p_{i j} / \sum_{i = 1}^{n} p_{i j} (12)$

基于层次的K-均值聚类算法(HKMA)与传统的K-均值聚类算法相比较,有两点不同。一是划分矩阵中元素(“隶属”概率)的形式发生了变化。数据点间的相似性从原来直接由点到类中心的距离倒数1/dij(或者能量倒数1/Eij)来度量,变为现在的以指数形式exp(-β dij)(或者exp(-βEij))来度量。这样,“隶属”概率成为距离的缓变(光滑)函数,使得聚类结果对初始化类中心不再像原来那么敏感,有利于提高聚类精度。二是增加了一项用来调节“隶属”概率模糊度的调控因子β。当β增大时,“隶属”概率模糊度降低。事实上,β=0时,各个“隶属”概率值相同,每个点都等概率地属于每一类;而当β→∞时,一个点以概率1属于离自己最近的类中心所代表的那个类,基于层次的K-均值聚类退化为传统的K-均值聚类。

原则上,改变设定的类数目,就会改变类中心的个数。然而,当β一定时,却存在某个类数目临界值c0,使得c>c0时,结果只能得到c0个不同的类中心,而剩下的c-c0个类中心都重叠在c0个类中心上。这说明β决定着聚类结果中的类中心和实际类数目。在下面的仿真试验中将会看到这一点。

4试验

4.1 二维正态分布随机数据集

用正态随机数产生器产生一个数据集。该数据集由4个子数据集组成,子数据集分别是以(1,1.5),(1,2.5),(5,2)和(7,2)为中心的正态分布数。每一个子数据集有160个数据样本构成。下图是该数据集在c=6,β分别等于0,0.25,0.95,2.90情况下的聚类结果。其中每一个方框标示一个类中心,代表聚类结果中的一个类。当β=0时,每个数据点都以相同的概率隶属于每一个类,由公式(8)知道所有类中心相互重叠,都处在数据集的质心上,结果只有一个类(见图1(a))。当β=0.25时,“隶属”概率模糊度降低,对距离的依赖加强,原来的一个大类分裂成两个小类(见图1(b))。β继续增加,“隶属”概率模糊度进一步降低,新的小类分裂成更小的类(见图1(c),图1(d))。这种过程一直进行下去,直到β足够大(如β →∞)时分裂成设定的类数目c。

4.2 Iris数

Iris数据集共有3类,分别代表鸢尾属植物(Iris flowers)的3个不同种类:Iris setosa,Iris versicolor和Iris virginica。每一类有50个样本,总共有150个样本。每一个样本通过萼片长度(sepal length)、萼片宽度(sepal width)、花瓣长度(petal length)和花瓣宽度(petal width)四个属性描述。

用HKMA对Iris数进行聚类,β值不同时结果类数目不同,显示层次聚类的性质。图2中上半图是Iris数的3个种类在第一维和第四维上的投影,在此作为参照图;下半图是在β=0.75的情况下对Iris数聚类所得结果在第一维和第四维上的投影。两图对照可以看出,150个样本中只有15个样本分类错误。

5结语

基于层次的K-均值聚类(HKMA),是在统计力学基础上,借鉴传统K-均值聚类算法改进而来的。该算法配分矩阵元素(“隶属”概率)的形式提高了聚类的精度,它所特有的调控因子使其具有层次聚类的特性。结果不再像以前那样由设定的类数目确定类中心,而是由得到的类中心确定实际的类数目。

参考文献

[1]Domany E.Superparamagnetic Clustering of Data-The De-finitive Solution of an Ill-Posed Problem.Physica A,1999,263:158-169.

[2]Blatt M,Wiseman S,Domany E.Super-paramagnetic Cluste-ring of Data.Physical Review Letters,1996,76:3 251-3 255.

[3]Blatt M,Wiseman S,Domany E.Clustering Data through anAnalogy to the Potts Model.Advances in Neural InformationProcessing System,MIT Press,1996.

[4]Blatt M,Wiseman S,Domany E.Data Clustering Using aModel Granular Magnet[J].Neural Computation,1997(9):1 805-1 842.

[5]Haojun Sun,Shengrui Wang,Qingshan Jiang.FCM-basedModel Selection Algorithms for Determining the Number ofClusters.Pattern Recognition,2004,37:2 027-2 037.

[6]Shehroz S Khan,Amir Ahmad.Cluster Center InitializationAlgorithm for K-means Clustering.Pattern Recognition Let-ters,2004,25:1 293-1 302.

基于权重系数模糊C均值聚类第8篇

1 模糊C均值聚类算法

FCM算法[3]由Bezdek于1974年首次提出, 通过最优化目标函数值来获得数据样本的最优划分, 由于算法中没有考虑样本数据的领域信息, 导致分割结果易受噪声和复杂背景的干扰而出现误分割。Girolam等人对FCM算法进行了改进, 提出了核模糊聚类算法 (KFCM) [8], 将核函数的概念引入到样本数据与聚类中心的相似性度量中, 增强了算法对噪声的鲁棒性。Wang等将局部和非局部空间约束引入到FCM算法中, 对MRI脑图像进行分割并获得了较好的分割结果, 但该方法对于信噪比较低的图像分割效果不理想[9]。Yang等人将高斯核函数和支持向量机方法引入到F CM算法中, 极大地抑制了图像中存在的噪声和离群像素的干扰, 获得了较好的分类结果[10]。文献[11]提出了一种基于全局空间相似性的模糊聚类算法, 将数据空间位置信息引入到数据与聚类中心的相似性度量计算中, 增强了分割结果的空间分布连续性。

该文提出一种基于权重系数模糊C均值聚类算法, 并将其应用于图像分割中。算法通过定义权重系数矩阵并构造相应的核函数, 将数据样本中每个样本的邻域特征信息引入到数据样本与聚类中心的相似性计算中, 通过核函数将样本集合中的样本映射到高维空间中, 实现样本在特征空间的优化。由于该文算法充分考虑了样本点的邻域信息, 极大地抑制了样本空间中的噪点和离群样本点, 与传统FCM算法相比, 该文算法能够获得更加精确的图像分割结果。

模糊C均值聚类算法是一种无监督的自动分割方法, 算法首先要确定聚类中心数c并初始化聚类中心点, 通过迭代更新聚类中心和最小化目标函数值来计算样本中数据与各个聚类中心的隶属度, 根据隶属度矩阵对样本集合X= (x1, x2, …xn) ∈Rn×p中数据进行分类。FCM算法目标函数如下式所示:

式中:xi∈X为样本中第i个数据;vj∈V, V= (v1, v2, …vn) ∈Rn×p为第j个聚类中心;ij为第i个数据到第j个聚类中心的隶属度;m=2为权重指数。算法通过更新聚类中心和隶属度矩阵来最小化目标函数值, 其更新公式如公式 (2) 和公式 (3) 所示:

2 基于权重系数模糊C均值聚类

由于传统FCM算法仅对孤立数据样本点进行分类, 没有考虑其领域信息, 导致分割结果空间分布不连续, 在图像分割中常常表现为分割结果易受孤立噪点和复杂背景的干扰而出现误分割现象。该文将权重系数概念引入到节点间相似性度量中, 考虑了数据的领域相关性, 增强了分割结果的空间分布连续性, 获得的分类结果更加符合人们的实际需求。权重系数定义如下:

从目标函数定义中可以看到, 特征空间样本距离如下所示:

其中K (x, y) (28)  (x)  (y) 为线性核函数, 则基于权重系数模糊C均值聚类目标函数更新公式如下式所示:

将基于权重系数特征空间样本距离带入聚类中心和隶属度矩阵更新公式中, 可以得到改进的聚类中心和隶属度更新公式如下式所示:

基于权重系数模糊C均值聚类算法流程如下所示:

(1) 确定聚类中心个数c和最大迭代次数N;初始化隶属度矩阵和聚类中心;

(2) 设迭代次数t=1, 并以样本集合中每个数据点为中心, 计算其3×3邻域样本值与其对应权重系数的乘积和;

(3) 更新聚类中心;

(4) 更新隶属度矩阵;

(5) 如果满足终止条件, 即相邻两次迭代目标函数值之差小于给定阈值或大于最大迭代次数, 退出循环, 根据每个样本点到各个聚类中心隶属度函数值的大小对数据样本点进行分类;否则, 执行步骤 (3) , t=t+1。

3 结果与分析

为了验证该文算法的可行性, 分别对遥感图像、具有自然背景彩色图像和星云图像三类具有不同特征的图像进行仿真实验 (如图1、图2和图3所示) , 比较该文算法与FCM算法和KFC M算法分割结果的精确性。图 (a) 为原始图像, 图 (b) 为FCM算法分割结果, 图 (c) 为KFCM算法分割结果, 图 (d) 为该文算法分割结果, 从分割结果中可以看到, 传统FCM算法易受噪声和杂波的干扰导致分割结果目标空间分布离散, 无法对图像中目标进行精确分割;KFCM算法分割结果在一定程度上抑制了图像中噪声和杂波的干扰, 分割结果类内数据空间分布连续增强, 但仍无法获得令人满意的分割结果;该文算法通过定义权重矩阵, 将图像中每个像点的邻域信息引入到聚类中心和隶属度矩阵的更新计算中, 增强了算法对噪声和杂波的鲁棒性, 获得了较好的图像分割结果。

4 结语

该文提出一种基于权重系数模糊C均值聚类算法, 并将其应用于图像分割中。该文算法根据图像中每个像点及其邻域像点的空间位置关系, 定义相应的权重系数矩阵, 构造相应的核函数, 并将其引入到模糊C均值聚类中。通过核函数将样本集合中的样本映射到高维空间中, 实现样本在特征空间的优化。图像中每个像点邻域特征信息的引入增强了算法对噪声和杂波的鲁棒性, 提高了图像分割结果的精度。

摘要：传统基于模糊C均值聚类图像分割算法易受复杂纹理和噪声干扰, 无法准确分割图像。针对这一现象, 提出一种基于权重系数模糊C均值聚类算法, 并将其应用于图像分割中。算法定义权重系数矩阵, 将每个像点的邻域信息引入到像点间相似性度量中, 计算每个像点与聚类中心点的邻域相似程度, 根据权重系数矩阵确定邻域中每个像点在邻域特征计算中所占权重, 增强了算法对噪点和杂波的鲁棒性。实验结果表明, 与传统模糊C均值聚类算法相比, 该文算法获得更加精确的图像分割结果。

关键词：模糊C均值聚类,权重系数,FCM

参考文献

[1]Karasulu B, Korukoglu S.A simulated annealing-based optimal threshold determining method in edge-based segmentation of grayscale images[J].Applied Soft Computing, 2011, 11 (2) :2246-2259.

[2]Isa N A M, Salamah S A, Ngah U K.Adaptive fuzzy movingk-means clustering algorithm for image segmentation[J].IEEETransactions on Consumer Electronics, 2009, 55 (4) :2145-2153.

[3]Bezdek J C.Cluster validity with fuzzy sets[J].Cybernetics and Systems, 1974, 3 (3) :58-73.

[4]Boykov Y, Veksler O, Zabih R.Fast approximate energy minimization via graph cuts[C]//Proceedings of the 7th IEEE International Conference on Computer Vision.Los Alamitos:IEEE Computer Society Press, 1999, 1:377-384.

[5]L.Grady, Random Walks for Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.28, no.11, pp.17681783, 2006.

[6]Mortensen E, Morse B, Barrett W, et al.Adaptive boundary detection using'live-wire'two-dimensional dynamic programming[C]//Proceedings of Computers in Cardiology.Los Alamitos:IEEE Computer Society Press, 1992:635-638.

[7]Kass M, Witkin A, Terzopoulos D.Snakes:active contour models[J].International Journal of Computer Vision, 1987, 1 (4) :321-331.

[8]Girolami M.Mercer kernel-based clustering in feature space[J].IEEE Transactions on Neural Networks, 2002, 13 (3) :780-784.

[9]Wang J Z, Kong J, Lu Y H, et al.A modified FCM algorithm for MRI brain image segmentation using both local and non-local spatial constraints[J].Computerized Medical Imaging and Graphics, 2008, 32 (8) :685-698.

[10]Yang X W, Zhang G Q, Lu J, et al.A kernel fuzzyc-means clustering-based fuzzy support vector machine algorithm for classification problems with outliers or noises[J].IEEE Transactions on Fuzzy Systems, 2011, 19 (1) :105-115.

本文来自 99学术网(www.99xueshu.com)，转载请保留网址和出处

【均值聚类分割】相关文章：

基于一种动态颜色模型的模糊C-均值图像分割05-30

聚类算法在医学图像分割中的应用12-15

均值模糊07-01

均值方差模型05-29

均值不等式06-24

K均值算法06-25