分割聚类（精选八篇）
分割聚类 篇1
本文在FCM的基础上提出了二次聚类图像分割算法。根据图像的 (l, α, β) 颜色空间, 将图像进行二次聚类划分为若干具有不同颜色特征或亮度的聚类域。从而实现图像的全局分割。
1本文算法
1.1 lαβ颜色空间
lαβ颜色空间是Ruderman等人基于人类视觉对图像数据的感知研究提出的[2], 其中, l表示非彩色亮度通道;α表示彩色的黄-蓝通道;β表示红-绿通道。本文算法首先把图像转换到 (l, α, β) 颜色空间, 其转换过程如下:
1) RGB到lαβ颜色空间的变换:先转换到LMS空间, 再转换到lαβ空间。
1.2二次聚类算法
首先图像分成若干个子集, 对各个子集进行第一次聚类, 然后将第一次聚类中心组成一个集合再次聚类求得第二次聚类中心, 根据像素点到第二次聚类中心的隶属度函数所得整幅图像的聚类域[3]。
设待处理的图像I大小为H*S, 即进行颜色聚类分析的元素个数为N, N=H*S, 则I可表示成集合I={x1, x2, …, xN}以图像I的每一行为一个子集将图像分为H个子集, 记为Im, m=1, 2, …, H。Im={x1m, x2m, …, xsm}, xim为m子集的像素点。先定义则数据点xim的密度为:
dij为数据点xim到数据点xjm的欧氏距离。这里r取适当值。如果数据点具有最大的分布密度, 那么子集Im的第一个聚类中心为:
Cmc1为xim邻域内的数据点集。找出第一个聚类中心后, 接着在集合{Im-Cmc1}中查找具有最大密度的数据值作为第二个聚类中心记为Cmc2, 数据点集记为Cmc2。重复同样的过程直至, k为获得的中心个数。令m=1, 2, …, H, 重复上述过程可获得第一次聚类中心集 (x1c, x2c, …, xcnc) 和对应的分布密度。对这个数据集进行第一次聚类, 密度函数改为:
2实验结果分析
分别采用灰度图像和彩色图像来验证二次聚类图像分割算法的有效性。由于本文提出的二次聚类通过亮度值的大小进行聚类, 所以图像的各聚类域将自动进行划分, 无需计算聚类域的匹配权值, 大大提高了图像分割的速度。图1、3为原始图像, 图2是原图1的分割结果, 图4是原图3的分割结果。
3 结论
由于聚类样本数量显著减少, 故可以大幅提高算法的计算速度, 进而可以利用聚类有效性分析指标快速确定聚类数目[4]。二次聚类分割可以使得计算量不会随样本维数增加呈指数增长, 分割区域类别明显。但是, 对于场景复杂的图像本文算法并不能很好的将各类别区分开来, 所以本文算法还受到领域的限制, 有待于进一步研究。
摘要：图像分割技术在各个领域中应用广泛, 简单描述了模糊C均值聚类算法, 在此基础上利用图像 (l, α, β) 颜色空间分离, 将亮度空间进行二次聚类, 根据像素点到第二次聚类中心的隶属度所得整幅图像的聚类域.能有效的将灰度图像或彩色图像中相似区域聚集分类, 为图像预处理提供很大帮助。通过实验验证了算法的有效性。
关键词：图像分割,二次聚类,颜色空间,相似区域
参考文献
[1]Ruderman D.L, Cronin TW, Chiao CC.Statistics of coneresponses to natural images:Implications for visual coding[J].Journ of Optical Society of America, 1998, 15 (8) :2036-204.
[2]刘蕊洁, 张金波, 刘锐.模糊c均值聚类算法[J].重庆工学院学报, 2007.21.1.
[3]钱小燕, 肖亮, 吴慧中.模糊颜色聚类在颜色传输中的应用[J].计算机辅助设计与图形学学报, 2006, 18 (9) :1332-1336.
分割聚类 篇2
关键词：机器视觉；模糊；分割算法；聚类；草莓图像
中图分类号：S126 文献标识码：A 文章编号：1674-1161（2014）07-0021-03
机器视觉技术是农业机器人的核心技术之一，而图像分割又是机器视觉技术的前提和关键。对于草莓采摘机器人来讲，图像分割效果的优劣直接影响机械手的采摘精度[1]。将自然状态下的成熟草莓从复杂环境背景中识别出来，并准确地计算其外形尺寸及形心位置，是草莓采摘机器人进行目标空间准确定位的基础。在自然状态下生长的草莓的植株叶子状况和成熟度都存在差异，且采集到的图像受拍摄距离、拍摄角度、光照条件、噪声等因素影响，给草莓果实图像的分割带来了一定的困难[2]。不同类型图像具有的图像特征有很大差异，所以到目前为止，研究者们还没有找到一个适合所有图像类型的通用分割算法，使得图像分割的新思路和新算法不断涌现[3-4]。
图像分割通常需要进行反复试验。聚类分析是多元统计分析的一种，是一种重要的数据分析技术，它根据一定的准则把数据分成大小不同的簇，使同一簇对象之间的相似度最大，而不同簇之间的相似度最小，以便揭示数据之间的联系与区别[5]。针对草莓果实图像的特点，提出一种模糊C-均值聚类（FCM）图像分割方法，来改善图像的分割效果。
1 普通C均值聚类算法
普通C均值聚类是一种硬划分，具有“非此即彼”的性质。算法把n个向量xj（j=0，1，……n）分为c个组Gi（i=0，1……c），求出每组的聚类中心v，使得具有非相似性指标的目标函数达到最小。当选择欧几里德距离作为组j中向量xk与相应聚类中心vi间的非相似性指标时，价值函数可定义为：
J=Ji=||xk-vi||2 （1）
定义一个c×n的二维隶属矩阵u：
uik=1 对每个k≠i，如果||xj-vi||2≤||xj-vk||2
0 其它 （2）
其中，vi为聚类中心，其值为分组i中所有向量的均值。则：
vi=xk （3）
其中，|Gi|=∑uij，隶属矩阵u具有性质：uij=1，?j=1，…，n，且uij=n，普通C均值算法的性能依赖于聚类中心的初始位置，并且有较快的收敛速度，对于简单分明的图像具有较好的分割效果[6]。
2 模糊C-均值聚类（FCM）图像分割算法
模糊C-均值聚类算法最先由提出来的，后经改进。该算法是聚类分析与模糊数学相结合的产物，它是依据最小二乘法原理，用隶属度确定每个数据点属于某个聚类程度的一种聚类算法。FCM把n个向量xi（i-0，1……n）分成c个模糊组，使用取值在[0 1]间的隶属度来确定每个数据点属于各个组的程度，隶属矩阵u允许取值在0，1之间的元素，一个数据集的隶属度的和为1，即：
模糊聚类的优点是不但能明确指出每类的中心，同时还能指明类之间的衔接和离散情况，是一种非常有效的聚类方法，FCM计算流程如图1所示。
FCM算法利用两层迭代求价值函数J（u， v1……uc）的最小值，内层用于计算聚类中心v及更新模糊隶属度矩阵μ，外层用于判断算法是否收敛到预定的阈值ε。迭代结束后，从产生的隶属度矩阵中，得到每个像素对某一个聚类中心的隶属度，根据其隶属度的大小决定该像素的归属。
3 结论与讨论
分别使用普通C均值聚类算法和模糊C-均值聚类（FCM）图像分割算法对草莓果实图像（图2和图3）进行分割，结果如图4和图5所示。由分割的结果可以看出，模糊C-均值聚类（FCM）图像分割算法不但能明确指出每类的中心，还指明类之间的衔接和离散情况，分割效果比较满意。
参考文献
[1] 张铁中，陈利兵.基于图像的草莓重心位置和采摘点的确定[J].中国农业大学学报，2005，10（1）：48-51.
[2] 张凯良，杨丽. 草莓采摘位置机器视觉与激光辅助定位方法[J].農业机械学报，2010，41（4）：151-155.
[3] 谢志勇，张铁中. 基于RGB彩色模型的草莓图像色调分割算法[J].中国农业大学学报，2006，11（1）：8486.
[4] 金立左，夏良正，杨世周.图象分割的自适应模糊阈值法[J].中国图象图形学报，2000，5（5）：217-220.
[5] 杨勇，郑崇勋，林盘.基于改进的模糊c均值聚类图像分割新算法[J].光电子，2005，16（9）：111-112.
基于模糊聚类的图像分割方法 篇3
关键词：模糊聚类,图像分割,模糊C均值聚类
1 引言
随着现代科技的不断突破, 图像领域中的图像分割也得到了很大的发展。我们在分析和对比应用过程中, 只针对比较重要的部分进行操作这些区域我们命名为焦点, 基本上这种焦点都集中在指定的位置。而我们需要对这些地方进行辨析, 所以我们把这些位置分割开来, 继而有效的采取额外的方式对分割出来的图片进行操作。
2 模糊数学基础
模糊数学作为一种新提出的工具, 主要用于解决那些具有不确定性, 也就是我们所说的具有模糊性的问题。模糊数学是于1965年提出的, 有扎德教授最先提出。模糊数学由于其有效性, 被广泛应用于解决图像信息处理, 以及医疗诊断还有AI (人工智能) 中的模糊问题。
2.1 模糊集的概念
假如A是U从0到1上的映射, 即A∶U→[0, 1], u→A (u) 就把A记做U上的模糊区间, 把映射方程A记做模糊集上的隶属函数 (membership function) , 而函数A () 称为模糊集A的隶属函数 (membership function) }A (u) 称为u对模糊集A的隶属度 (membership degree) 。模糊集F简记为F集。对于某F集合A, 若A (u) 仅取。和1两个数时, A就蜕化成普通集合。所以, 普通集合是模糊集的特殊形式。若A (u) =0则A称为空集;若A (u) =1时, 则A称为全集U。
在数学理论中, 集合都拥有一些自身的特性, 比如交换运算顺序结果不变等, 模糊集合作为一种集合, 和我们通常的集合一样, 也满足那些基本的集合运算规律。但模糊集合也有异于普通集合的地方, 就是不满足集合中存在的非A即B的运算规律, 因为模糊集合存在很多不可区分的区域, 我们将这些区域称之为中间区域。
要确定模糊集合中的元素的归属, 必须事先制定好隶属度, 再根据隶属度来确定元素的归属。对于一般的集合, 隶属度函数只允许有俩个取值:即0和1。而对于模糊关系, 它定义的值得区间是从0到1不间断的值, 不同的值对应了相应的隶属度确定会影响到分类效果, 因此, 如何确定隶属度函数是在集合理论中至关重要的一个步骤。对于不同的方法, 隶属度函数的确定也随之不同, 我们需要根据实际中所采用的集合来确定所适用的隶属度函数。比较常见的确定隶属度的方法有:基于主观经验的隶属度方法, 还有基于推理方法的隶属度方法以及基于调查统计的隶属度方法。
在我们工程实践当中隶属函数被分成3种形式: (a) S方法 (代表大的隶属度) (b) Z方法 (区间表示小的隶属度) (c) N方法 (折中的隶属度) 。其中S方法主要是来象征比较长的, 比较高的, 比较旧的模糊关系, Z函数方法主要来象征比较轻松的, 比较狭小的模糊关系。N则表示有活力的隶属度关系。
2.2 模糊关系
我们所说的模糊关系, 本质上是一种数学模型的昵称, 该数学模型的程度相关的元素之间的这种关系就是我们所定义的模糊关系。这种情况下的模糊关系我们可以理解一个关联情况。我们用数学上的二进制来表示相关度的存在情况, 有相关的用1来标明, 没有相关的则用0来代表。我们所定义的模糊值得区间范围是从0到1, 值越小表示关联性越大, 相反则表示越小。
3 聚类分析
所谓的聚类分析, 就是事先制定好一些分类准则, 然后再依据制定好的准则把事物进行分类, 我们把这样的数学过程称之为聚类。聚类分析在数据的分组以及划分中应用得非常广泛。它把我们所要分类的样本集合中一些比较相似的元素或数据规划为同一个类, 由于没有利用辅助的信息, 因此, 聚类分析是可以视为一种无监督的分类方法。通过聚类分析, 可以使在同一个类别中的元素具有最大的相似度。在图像分割, 模式识别以及特征分类提取领域都可以发现由于聚类分析的有效性, 而得到了很好的发展和应用。
在早期的聚类分析中, 每个样本都有一个明确的类别, 会把每个样本严格地进行划分, 这样的划分方法我们将其称之为硬聚类。经典的C-均值聚类方法, 是目前学术界使用最广的方法之一。当下, 硬聚类明显存在着不足之处:硬聚类只能将物体分成两个类别, 而现实中并不是完全的非此即彼, 也有中立的情形, 这种情况就不能使用硬聚类来划分。我们以一幅图像为例, 按照硬聚类的方法, 我们要将每个像素严格的分化到定义好的某个类别。显然这样做是不合理的, 因为图像本身就存在一些含糊的区域, 这种现象在复杂的医学图像中更为明显。这时候我们不能采用硬聚类的方法来分类, 这项工作旨在合理的区分边界, 这些边界的确定是用模糊来处理的最佳选择。
4 模糊c均值聚类算法
4.1 模糊数据集的C划分
论域指聚类分析对象的全体 (数据集X) , 为刻画X中的每个对象即样本, 选用数量可确定的参数值。则有X={x1, x2, ..., xn}, 每个参数值刻画xk (k=1, 2, ..., n) 的某个特征。c划分是这样产生的:依据每个样本间的亲疏关系, 对模式向量 (论域X中的n个样本所对应的) 分析其相似性。
X1, X2, ..., XC是对数据集X进行C划分得到的C个子集。如果符合下面两个式子, 则把它称作X的硬C划分:
如果用隶属函数Uik表示样本xk (l<=k<=n) 对子集Xi (l<=i<=c) 的隶属关系则有硬C划分中Uik为子集Xi的特征函数, 有Uik∈{0, 1}的划分也能由隶属函数来表达, 这样就能用矩阵U=[uik]c*n表示, 矩阵由c个子集的特征函数值构成的。第i个子集的特征函数对应矩阵U中的第i行, 而样本xk针对于c子集的隶属函数对应矩阵U中第k列, 因此, 我们可得到X的硬C划分空间为:
4.2模糊C均值聚类算法
有时满足要求的分类很多, 我们要选择合理的聚类准则来搜寻合理的分类结果。最小平方误差和在硬据类中是常用的聚类准则之一。
假定硬划分矩阵为, 特征空间矢量集合是V={v1, v2, ..., vn}第i类的聚类中心矢量用vi (1<=i<=c) 表示。硬聚类分析的目标函数可以写作:J (U, V) =ΣΣuik (dik)
上式里J (U, V) 指每中样本与它的聚类原型的误差平方和;dik是欧式距离, 用来度量第i类中心v与第k个数据样本xk之间的距离, 它表示为:dik=d (xk-vi) =‖xk-vi‖
为了让该分区能产生最小的函数值:J (U′, V′) =min J (U, V) , 要搜寻一个最佳分区U。即聚类准则为使J (U, V) 为最小, 应该找到最佳的组对 (U, Y) 。
其中, m称为平滑指数, 又称加权指数。在不对隶属度加权的情况下, 从硬聚类目标函数到模糊聚类目标函数的推广将无效, 虽然m的出现导致不彩色 (从数学角度看) 。在上述目标函数中, 第i类的聚类模型v跟样本xk之间的距离度量可以表述为:
其中, A是s*s阶的正定矩阵, 且为对称的, 式子对应为欧式距离仅当A为单位矩阵I时。由于矩阵U中各列都是独立的, 为得到极小值min{Jm (U, V) }, 即聚类准则为取Jm (U, V) 的极小值, 因此有:
4.3 模糊c均值聚类图像分割算法
为了实现图像分割, 可以用模糊聚类的方法对图中属性相一致的像素进行处理, 然后标定每类像, FCM算法正是用这样的方法来做的。把像素点的征当作样本点的特征, 图像的像素点当作数据集的样本点, 则图像的分割问题转化为下列优化问题:
其中, 第i类中样本k的隶属度为ui, 聚类空间的样本数为n, 聚类的类数m>1, (dik) 2=‖xk-vi‖= (xkvi) TA (xk-vi) 表示样本xk距聚类中心v的欧式距离, X={xl, x2, ..., xc}是样本集, U={uik}是表示一个。
由FCM算法, 可得FCM图像分割算法如下:
(1) 设n=M*N为像素点个数, 对图像矩阵FM*N=[f (i, j) ]M*N行化。初始化聚类原型模式V (0) , 设定迭代计数器r=0;设定迭代停止阈值为0.01;给定聚类类别数c (2<c<n) 和m (m>1) 。
(5) 去模糊化。把目标从背景中分离是图像分割的最终目的, 需要把模糊阈值描述去模糊, 从而使模糊阈值选择描述吻合于目标识别任务。第k个样本点所属的类别用Ck表示, 我们使用最大隶属函数法去模糊, 则得到。
5 总结
图像分割中经常要考虑设定阈值的问题, 若用FCM方法 (模糊C均值聚类) 就可以绕过这个问题, 并且能解决由阈值化分割中产生多个分支的分割问题。不确定性和模糊性是图像拥有的特点, FCM方法正好适合这个特点。同时FCM算法很适合于自动分割的应用领域, 因为在聚类过程中, 它不需要任何人工的干预, 属于无监督的分类方法。
参考文献
[1]周芳芳, 樊晓平, 叶榛.均值漂移算法的研究与应用[J].控制与决策.2007 (08) .
[2]李华, 张明新, 郑金龙.融合多特征的均值漂移彩色图像分割方法[J].计算机应用.2009 (08) .
[3]罗希平, 田捷.图像分割方法综述[J], 模式识别与人工智能, 2003:200-208.
[4]韩思奇, 王蕾.图像分割的阈值法综述[J], 系统工程与电子技术, 2007:102-110.
[5]RM Haralick, LG Shapiro.Image segmentation techniques[J], Computer vision, graphics, and image, 2000:123-127.
分割聚类 篇4
群体智能算法是基于群体行为对给定目标进行寻优的一种启发式搜索算法, 自20世纪80年代出现这类算法以来, 已经得到了众多研究人员的广泛关注, 并已发展成为优化技术领域的一个热点研究方向。粒子群优化 (Particle Swarm Optimization, PSO) 算法[1]是一种典型的群智能优化算法, 该算法于1995年由美国社会心理学家Kennedy博士和电气工程师Eberhart博士在对社会型生物群体行为模拟的基础上提出。由于PSO算法计算简单、控制参数较少且易于实现, 因此已被广泛应用于各种优化计算领域[2,3,4]。因为PSO算法通常无法保证收敛于优化问题的全局最优解甚至于局部最优解[5], 因此, 国内学者孙俊等人受量子力学等相关理论的启发, 利用量子测不准原理来描述粒子的运动状态, 并在PSO算法基础上提出了具有量子行为和全局收敛性能的量子粒子群优化 (Quantum-behaved Particle Swarm Optimization, QPSO) 算法[6], 该算法认为处于量子束缚态的粒子可以以一定的概率密度出现在空间中的任何点, 粒子可以在整个可行空间中进行搜索且不会发散到无穷远处。
在图像处理的研究中, 人们通常会关注图像中的某些局部内容, 如目标或者前景, 以便进行后续的图像处理, 这种把图像分成若干个特定的、具有独特性质的区域并提取出感兴趣的目标的技术和过程, 称为图像分割。图像分割是图像分析的重要环节, 经过图像分割所提取出的目标可以广泛应用于图像的语义识别、图像搜索等众多领域。
1 相关概念
1.1 标准PSO算法
由Kennedy和Eberhart所提出的PSO算法, 其主要思想来源于对鸟类群体行为的研究。在利用该算法解决优化问题的过程中, 首先是要初始化一组随机解, 然后通过迭代方式来搜寻最优值。在PSO算法中, 每个优化问题的解都被看做搜索空间中的一只鸟, 称为“粒子”。所有的粒子对应着优化问题的适应值, 粒子的速度决定了其飞行的方向和距离, 粒子通过追寻群体中的最优粒子来完成解空间的搜索, 其具体的算法原理描述如下:
其中, r1, r2为 (0, 1) 区间的随机数, c1, c2称为学习因子或加速系数, w称为惯性权重。
1.2 QPSO算法
由于PSO算法不能收敛于全局最优解, 甚至局部最优解[5], 许多学者提出了大量的方法以改进PSO算法的收敛性能, 但实际情况表明, 很多方法对PSO算法的改进是有限的。孙俊等人在研究了Clerc等人关于收敛行为的研究成果后, 从量子力学的角度出发, 提出了具有量子行为的粒子群优化算, 即QPSO算法[6]。在该算法中, 由于其采用了量子测不准理论, 因此粒子的位置和速度不能同时被精确测定, 但由波函数的统计意义, 可以通过波函数给定的概率密度函数来确定粒子在某个时刻出现的概率, 该算法原理描述如下:
在一个N维的目标搜索空间中, QPSO算法由M个代表潜在问题解的粒子组成群体X (t) ={X1 (t) , X2 (t) , …, XM (t) }, 在t时刻, 第i个粒子位置为:
在QPSO算法中, 粒子不再有速度向量, 个体最好位置为Pi (t) =[Pi, 1 (t) , Pi, 2 (t) , …, Pi, N (t) ], 群体的全局最好位置为G (t) =[G1 (t) , G2 (t) , …, GN (t) ], 且G (t) =Pg (t) , 其中g为处于全局最好位置粒子的下标, g∈{1, 2, …, M}。
对于最小化问题, 目标函数值越小, 对应的适应值越好。粒子i的个体最好位置pbest由下式确定:
群体的全局最好位置由式 (4) 和式 (5) 确定:
在算法运行中, 由于每一次更新粒子位置前都要计算全局最好位置, 因此只须将每一个粒子的当前个体位置的适应度值与全局最好位置的适应度值作比较, 若前者好, 则更新G (t) 。令:
则粒子的进化方程 (位置更新方程) 为:
1.3 K-均值聚类算法
K-均值聚类算法又叫K-Means聚类算法, 其算法原理是:首先随机地从数据集中选取K个点作为初始聚类中心, 然后计算各个样本到聚类中的距离, 把样本归到离它最近的那个聚类中心所在的类;然后计算新形成的每一个聚类的数据对象的平均值来得到新的聚类中心, 如果相邻两次的聚类中心没有任何变化, 说明样本调整结束, 聚类准则函数已经收敛。K-均值聚类算法的一个特点是在每次迭代中都要检查每个样本的分类是否正确, 若不正确, 则需进行调整, 待全部样本调整结束后, 再修改聚类中心, 进入新一轮的迭代。如果在迭代过程中, 所有的样本均被正确分类, 则聚类中心不会再有变化, 这标志着算法已经收敛。K-均值聚类算法的算法流程可以描述如下:
Step 1从n个数据对象任意选择k个对象作为初始聚类中心。
Step 2根据每个聚类对象的均值 (中心对象) , 依据距离公式 (8) 计算每个对象与这些中心对象的距离;并根据最小距离重新对相应的对象进行划分。
Step 3按照公式 (9) 重新计算每个 (有变化) 聚类的均值 (中心对象) 。
Step 4计算误差平方和准则函数 (10) 的值, 判断是否满足算法结束条件, 若满足, 则算法结束。否则循环Step 2到Step 3, 直到满足算法结束条件为止 (即每个聚类不再发生变化, 或达到最大迭代次数) 。
其中:p表示聚类样本个数, zp表示第p个样本, mj表示第j个聚类的聚类中心向量, nj表示聚类中所包含的样本个数, cj表示第j个聚类。
2 基于QPSO聚类算法的图像分割
2.1 QPSO聚类算法的图像分割流程
K-均值聚类算法是当前流行的基于图像颜色的图像分割方法, 在进行QPSO算法聚类分割时, 受K-均值聚类算法的良好性能的启发, 我们采用K-均值聚类算法中样本到聚类中心的距离作为QPSO算法中聚类的度量标准, 即:
类似地, 我们采用误差平方和准则函数作为QPSO算法的适应度函数, 即:
其中, Nd表示输入的维数, 也就是每一个样本的维数, 即每个向量的参数个数, Nc表示聚类中心点的个数, p表示聚类样本个数, zp表示第p个样本, mj表示第j个中心向量, |Cij|表示类别Cij所包含的数据个数。则基于QPSO的聚类算法的图像分割流程如下:
Step 1提取图像的RGB通道的灰度级强度作为特征向量。
Step 2初始化 (聚类中心、个体最优解、全局最优解) 。
Step 3根据式式 (11) 计算聚类, 根据式式 (12) 计算个体的适应度函数值。
Step 4计算并更新粒子群的平均最好位置mbest, 更新个体最好位置pbest和全局最好位置gbest。
Step 5根据式 (6) 计算随机点p。
Step 6根据式 (7) 更新粒子的中心向量。
Step 7重复Step 2至Step 6, 直到满足迭代结束条件或最大迭代次数为止。
3 实验结果
为验证基于QPSO聚类算法的图像分割性能, 我们分别采用基于QPSO聚类算法和K-均值聚类分割算法对255×255的Lenna灰度图和250×350的彩色婴儿图进行实验对比分析, 实验环境选用AMD Athon 645 4核3.10GHz处理器, 内存为4GB的PC机, 其分割结果如图1所示:
通过对以上两组分割结果图像的对比, 我们看到QPSO聚类算法和K-均值聚类算法对原图 (a) 和原图 (b) 进行的图像分割都取得了比较良好的效果, 且基于QPSO聚类算法的图像分割结果轮廓更为清晰, 层次更为分明。
表1给出了二种算法对Lenna灰度图和彩色婴儿图分割的对比数据, 从表1可以看出, K-均值聚类算法在分割时间开销上相对于QPSO聚类算法有着一定的优势, 且基于QPSO聚类算法在分割Lenna灰度图和彩色婴儿图中, 其误差平方和项对应的J值均小于相应的K-均值聚类算法。此外, 由于K-均值聚类算法对初始聚类中心的选取至关重要, 若选取不得当, 可能会大大增加聚类的时间开销, 甚至在一定的迭代步内可能无法得到满足精度要求的解。而QPSO聚类算法对初始聚类中心没有任何要求, 且其可以得到比K-均值聚类算法精度更高的聚类中心。
4 结语
受K-均值聚类算法的启发, 我们设计了基于QPSO的聚类算法来处理图像分割问题。实验结果表明, 相对于K-均值聚类算法, QPSO聚类算法在不需要选择适当的初始聚类中心的情况下也能够获得精度比K-均值聚类算法更高的聚类中心, 且基于QPSO聚类算法的图像分割方法比K-均值聚类算法的图像分割得到的分割图像轮廓更为清晰, 层次更为分明。
摘要：量子粒子群优化算法克服了传统粒子群优化算法中无法保证全局收敛、容易陷入局部最优的缺点, 是近年来优化技术领域的一个研究热点。本文结合当前图像分割中常用的K-均值聚类算法中的相关技术, 设计了基于QPSO的聚类算法并将其用于图像分割处理问题中。实验结果表明:在图像分割处理中, 相对于K-均值聚类算法, QPSO聚类算法不仅不依赖于初始聚类中心的选择, 而且还能得到相对于K-均值聚类算法精度更高的聚类中心, 其在图像分割中的效果优于通常的K-均值聚类算法。
关键词：PSO算法,QPSO算法,K-Means聚类,图像分割
参考文献
[1]Kennedy J, Eberhart R C.Particle swarm optimization[C].IEEE International Conference on Neural Networks, 1995, 1942-1948.
[2]Cohen S, de Castro L N.Data clustering with particle swarms[C].IEEE Congress on Evolutionary Computation, 2006:1792-1798.
[3]Lope H S, Coelho L S.Particle swarn optimization with fast local search for the blind traveling salesman problem[C].Fifth Interna tional Conference on Hybrid Intelligent Systems, 2005:245-250.
[4]Nenortaite J, Simutis R.Adapting particle swarm optimization to stock markets[C].Proceedings 5th International Conference on Intelligent Systems Design and Applications, 2005:520-525.
[5]Van Den Bergh F.An analysis of particle swarm optimizers[D].University of Pretoria, 2006.
分割聚类 篇5
近年来, SAR影像在国民经济、科技、资源利用的作用日益突出, 其在国防军事中的重要地位更是不可小觑。国内外对SAR影像的分割研究中, 分割方法可分为基于图像驱动及基于模型驱动的方法。前一种方法有基于直方图阈值、边缘检测、区域增长等的算法, 后一种方法有基于马尔可夫随机场、模糊理论、神经网络、多尺度和分水岭等模型算法。两类SAR影像分割方法各自存在缺陷。
文章中, 将模糊聚类理论应用于SAR海陆影像分割中, 建立基于核模糊c-均值聚类与阈值分割结合的SAR影像组合分割模型, 实现对SAR影像的分割, 并对文章算法进行评价。
1 核模糊c-均值聚类基本理论
1.1 模糊数学与模糊集合
L.A.Zadeh在1965年[1]提出了模糊数学这一概念, 用隶属程度来描述差异的中间过渡, 它是用精确的数学语言对模糊性的一种描述。在实际模式识别中, 利用“最大隶属度原则”[2]进行对象分类识别。
1.2 核模糊c-均值聚类
核模糊聚类引入了模糊聚类分析与核函数, 对样本进行软划分, 并且对非超球体、被噪声污染、多种模式原型混合以及不对称数据等多种数据结构分割更为理想。Girolami M[3]和张莉等[4]提出了将核函数引入到聚类分析中, 在高维特征空间中进行聚类。伍忠东等[5]进一步构造基于核函数的模糊核c-均值算法 (KFCM) 。曲福恒等[6]利用Zangwill收敛性定理, 证明了核模糊c-均值聚类算法 (KFCM) 的收敛性。
2 SAR组合分割算法
2.1 图像预处理
选择增强Lee滤波器对SAR原影像进行斑点去噪。
2.2 SAR影像粗分割
选用多项式核模糊c-均值聚类算法 (以下记为p KFCMClust) 将图像分割为3类:为油膜, 水体和待分类别。
2.3 SAR影像细分割
细分割中, 对粗分割中的待分类别区域单独进行阈值分割细分, 最终划分为两类。
3 分割实验
文章采用的数据为青岛附近海域SAR影像, 摄于2010年7月4日, 影像上有海水和油膜两种物体。
3.1 实验
从实验结果图中可看出, 经文章算法处理的分割图的轮廓更接近于实际边缘的轮廓, 不受高亮杂质噪声的影响, 分割效果较好。
3.2 实验结果
从上述实验的评价结果来看, 经文章算法处理得到的目标接近于真实目标, 具有较为理想的分割效果。
4 结束语
文章章在SAR影像分割研究中引入模糊聚类分析, 设计了基于核模糊c-均值聚类与阈值分割结合的SAR影像分割算法, 对SAR影像实现分割实验。从实验分析结果可以得出结论:核模糊c-均值聚类算法能较好得抑制SAR噪声, 分割结果的目标不含过多杂质, 对SAR影像的分割具有较高的可靠性。
摘要：由于SAR影像存在强烈的相干斑点噪声, 传统的方法分割方法存在缺陷。文章在SAR影像分割研究中引入模糊聚类分析, 设计了基于核模糊c-均值聚类与阈值分割结合的SAR影像分割算法, 对SAR影像实现分割实验, 通过实验分割结果的分析, 证明了算法的可靠性。
关键词：SAR影像分割,多项式核模糊c-均值聚类,阈值分割
参考文献
[1]L.E.Zadeh.Fussy sets[J].Information and Control, 1965, 8 (3) :338-353.
[2]赵伟舟.基于模糊聚类的SAR影像分割研究与实现[J].电脑知识与技术, 2008, 3 (4) :768-769+779.
[3]Girolami M.Mercer Kernel Based clustering in Feature.Space[J].IEEE Trans on Neural Networks, 2002, 13 (3) :780-784.
[4]张莉, 周传达, 焦李成.核聚类算法[J].计算机学报, 2002, 25 (6) :587-590.
[5]伍忠东, 高新波, 谢维信.基于核方法的模糊聚类算法[J].西安电子科技大学学报 (自然科学版) , 2004, 31 (4) :533-537.
分割聚类 篇6
图像分割是一种重要的图像分析工具,是从图像处理到图像分割的重要步骤,也是进一步图像理解的基础,在机器视觉、目标识别、医学图像处理中都有广泛的应用。传统的分割方法有阈值分割、边缘检测、基于区域的分割、基于形态学分水岭的分割[1]。近年来,随着各学科许多新理论和方法的提出,人们也提出了许多结合一些特定理论、方法和工具的分割技术[2]。
聚类是将数据对象分成类或簇的过程,使同一个簇中的对象之间具有很高的相似度,而不同簇中的对象高度相异。相异度根据描述对象的属性值评估,通常使用距离度量。聚类源于许多研究领域,包括数据挖掘、统计学、生物学和机器学习[3]。而图像分割恰好是将图像的像素集进行分类的问题,自然地将聚类分析用于图像之中[7,8]。
早在1979年,Coleman和Anderews提出用聚类算法进行图像分割。K-均值聚类[4]是聚类方法中一种无监督自适应算法,能通过迭代对给定的数据进行分类,[5]中通过基于粗糙集理论的算法求出初始聚类的数目和均值,能有效提高分类准确性。但K-均值算法对于离群点是敏感的,因为一个具有很大的极端值的对象可能显著地扭曲数据的分布。通过我们改进的K-均值算法,有效地消除了离群点对聚类结果的影响,提高了分类的精度。
2 K-均值聚类算法
2.1 数据集的c划分
设数据集X={x1,x2,…,xn}是聚类分析对象的全体(称为论域),X中的每个对象xk(k=1,2,…,n)(称为样本)用有限个参数值来刻画,每个参数值刻画xk的某个特征。聚类分析就是分析论域X中n个样本所对应的模式向量的相似性,按照各样本间的亲疏关系,产生X的c划分。
数据集X的c划分得到的c个子集X1,X2,…,Xc如果满足下列条件,则称之为X的硬c划分:
2.2 K-均值聚类
K均值聚类算法[4]是聚类中硬c划分的一种,它以K为输入参数,把N个对象的集合分成K个簇,使得结果簇内的相似度高,而簇间的相似度低。簇的相似度是关于簇中对象的均值度量,可以看作簇的质心或重心。它的核心思想如下:
算法随机选择K个对象,每个对象代表一个簇的初始均值或中心。对剩余的每个对象,计算其与各个簇中心的距离,根据使距离指标的目标函数最小的原则将它划分到最相似的簇。然后重新计算各个簇的新均值,更新簇中心。这个过程不断重复,直到准则函数收敛。
假设要聚成K个类,由人为决定K个类的中心C1(1),C2(1),C3(1),……,Ck(1),在第k次迭代中,样本集{X}用如下方法分类:
对所有i=1,2,…,K,i≠j
设Sj(k)的新的类中心为Cj(k+1)
对所有j=1,2,…,K,若Cj(k+1)=Cj(k),则终止。否则,进入以上过程的循环。
3 改进的K-均值算法
由于K-均值算法对离群点的不适应,而平方误差函数的使用更是严重恶化了这一影响。所以,我们可以使用绝对误差标准来降低K-均值算法对离群点的敏感性。可以不采用簇中对象的均值作为参照点,而是在每个簇中选出一个实际的对象来替换该簇,其余的每个对象聚类到与其最相似的代表性对象所在的簇中。这样,划分方法仍然基于最小化所有对象与其对应的参照点之间的相异度之和的原则来执行。使用绝对误差标准的定义如下:
其中,E是数据集中所有对象的绝对误差之和;p是空间中的点,代表簇Cj中一个给定对象;Oj是簇Cj中的代表对象。通过算法的迭代,直到每个代表对象都成为它的簇的实际中心点,或最靠中心的对象。每当重新分配发生时,绝对误差E的差对代价函数都会有影响。因此,如果当前的代表对象被非代表对象所取代,代价函数就计算绝对误差值的差。交换的总代价时所有非代表对象所产生的代价之和。如果总代价是负的,则E将会减小,簇中心可以被随机簇内点所取代;如果代价是正的,则当前的簇中心是可以接受的,在本次迭代中不会发生变化。算法如下:
(1)从给定数据中任意选择K个对象作为初始聚类中心;
(2)根据平均距离和最小的原则进行分类;
(3)随机选择一个非中心点数据代替现有中心点;
(4)计算交换后的总代价函数值E;
(5)if E<0,then用该数据替换现有中心点成为新的中心;
(6)until不再发生变化。
4 实验结果分析
为验证本文算法的有效性和正确性,我们采用Matlab编程环境进行基于改进的K-均值算法的仿真实验。本文选用了不同分辨率的多对图像进行检验,将K-均值聚类算法与本文改进的聚类算法的结果进行了对比。图1(a)、图2(a)为原始图像,图1(b)、图2(b)为使用K-均值聚类的图像,图1(c)、图2(c)为使用改进的K-均值算法聚类的图像。从实验结果看,本文算法得到的图像效果较清晰,突出了目标区域,提高了分割精度。
5 结束语
本文在基于K-均值聚类算法的基础上进行了改进,通过比较替换簇中心后绝对误差值的差的代价函数,选择最优的代表对象作为中心点,提高了聚类中心的精准度和分类的准确度,有效地改善了基于聚类方法的图像分割结果,是一种有效的图像分割算法。
参考文献
[1]Rafael C.Gonzalez,Richard E.Woods.Digital Image Processing[M].New York:Prentice Hall,2002.
[2]章毓晋.图像分割[M].北京:科学出版社,2001.
[3]Jiawei Han,Micheline Kamber.Data Mining:Concepts and Techniques[M].USA:Morgan Kaufmann,2005.
[4]J.MacQueen.Some methods for classification and analysis of multivariate observations.In L.M.Le Cam and J.Neyman,editors,Pro-ceedings of the5'th Berkeley Symposium on Mathematical Statistics and Probability,volume1,pages281-297.U.California Press,1967.
[5]邵锐,巫兆聪,钟世明.基于粗糙集的K-均值聚类算法在图像分割中的应用[J].测绘信息与工程,2005,30(5).
[6]郑洪英.数据挖掘聚类算法的分析和应用研究[D].重庆:重庆大学,2002.
[7]T.Kanungo,D.M.Mount,and N.S.Netanyahu,et al.The Analysis of a Simple K-Means Clustering Algorithm[J].Symposium on Computational Geometry,2000,January.
云模型和谱聚类的图像分割特性分析 篇7
1.1 云模型
云模型是用自然语言值表示的某个定性概念与其定量表示之间的不确定性转换模型。设U是一个用精确数值表示的定量论域, C是U上的定性概念, 若定量值, 且x是定性概念C的一次随机实现, x对C的确定度μ (x) ∈[0, 1]是有稳定倾向的随机数, 则x在论域U上的分布成为云模型, 简称云, 每一个x成为一个云滴。
云模型的数字特征用期望Ex, 熵En和超熵He来表示, 它们反映概念C整体上的定性特征。期望Ex就是最能够代表定性概念的点, 反映了云的重心。熵En表示定性概念的不确定性度量, 由概念的随机性和模糊性共同决定。一方面熵是定性概念随机性的度量, 反映了能够代表这个定性概念的云滴的离散程度。另一方面又是定性概念亦此亦彼的度量, 反映了论域空间中可被概念接受的云滴的取值范围。超熵He是熵的不确定性度量, 反映了论域空间代表该概念的所有点的不确定度的聚集性, 即云滴的聚集度, 超熵的大小间接表示了云的离散程度和厚度。
云模型的种类有很多, 如正态云模型、对称云模型、半云模型、组合云模型等。正态云是一种最基本的云模型, 其普适性建立在正态分布的普适性基础之上, 是描述概念的有力数学方法之一。
1.2 图像分割的云模型聚类分析
利用云模型分割图像就是将像元划分为不同类别的过程。由于正态云具有普适性, 不同类别在图像上的像元灰度分布可以用一个正态云来表示, 云模型的期望值就是最能代表该类别在图像上的像元灰度值。于是定量的像元灰度数据就转化成了一系列用云模型表示的定性概念。定性概念在图像上表征为一个正态云或几个正态云的组合。像元灰度对应云滴, 它是图像的一次随机实现。定性概念表征图像的一个类别, 像元间相似度体现云滴的离散程度, 云滴的离散程度又是对定性概念的不确定性度量, 即像元间相似度能够区分不同的类别。像元对类别的确定度反映其聚类关系的模糊性, 由云滴对云的隶属程度来确定像元的类别。
由上述分析得到, 基于云模型的分割图像过程就是将论域中的定量数值映射为定性概念, 实现定量数值与定性概念的不确定性转换。基于一维云模型的图像聚类算法的步骤: (1) 对原始图像进行预处理, 生成一维灰度直方图。通过拟合离散的灰度频率分布图, 得到平滑的灰度频率分布曲线; (2) 云变换。使用拟合数据, 利用最小二乘计算灰度频率分布曲线极大值的云期望曲线。接着, 灰度频率分布曲线减去云期望曲线, 得到新的数据分布曲线。最后, 生成若干粒度不同的云, 获得一定数量的底层云概念; (3) 云综合。先计算不同云模型之间的距离, 利用“积分”云综合方法, 将云模型距离最小的云进行综合, 将底层云合并为高层云概念, 得到云泛概念树的层次结构图; (4) 概念判别与分割。根据聚类数目, 确定合适的定性概念层次。然后, 根据极大判定法, 判断像元灰度值隶属于某个定性概念的程度, 实现图像分割。
1.3 适用于云模型分析的图像
期望Ex反映组成定性概念所有云滴的重心, 对应于图像, 则是组成图像目标类的像元灰度均值。它是定性概念最具决定性的特征, 直接决定概念本身, 原因是云模型以灰度作为分类依据, 根据阈值 (即云的重心) 完成聚类过程。熵En是定性概念亦此亦彼的度量, 随着对En值的由小到大调整, 发现越来越多的像元会从一个概念变成另一个概念。当En值由大到小进行调整时, 目标类边缘发生模糊现象, 像元对目标类的隶属度较小, 像元对目标类的模糊性增强。可见, 云模型的熵有效地表达了图像分割中存在的不确定性, 实现了图像的软分割。超熵He表示云滴的聚集度, 反映相同灰度值下像元的聚集程度。随着对He值的由大到小调整, 图像好像被带入噪声, 不同概念之间发生变化, 图像质量变差。反之, 图像会越来越清晰, 就好像云层的厚度变得厚实了。可见, 超熵是熵的不确定性度量。
综上所述, 在假设正态分布的前提下, 云模型是将模糊性和随机性相结合的一种聚类分析方法。它实现了灰度图像软分割, 对聚类结果具有较好的可解释性和可用性, 实现简单。
2 谱聚类及适用图像
2.1 谱聚类
谱聚类分析方法根据给定的样本数据集定义一个描述成对数据点的相似度矩阵, 并计算矩阵的特征值和特征向量, 然后选择合适的特征向量聚类不同的数据点。谱聚类分割图像, 是将图像映射为无向加权图G, 其中每个像元xj对应顶点vj, 顶点vi和vj间的边有权值wij≥0, 利用剪切准则完成图像的最优分割。从图论角度看, 谱聚类问题转变成如何划分图G的连通子图, 使得子图内部相似度较大, 子图之间的相似度较小。
常见聚类准则的目标函数有Minimum Cut、Average Cut、Normalized Cut (Ncut) 、Min-max Cut、Ratio Cut等。由于Ncut方法不仅能满足样本内的相似度最大, 同时让样本间的相异度最大, 成为机器学习和计算机视觉等多个领域研究聚类问题的一种经典的方法。本文主要使用Ncut方法进行图像分割来分析谱聚类的特性。
2.2 图像分割的谱聚类分析
谱聚类的主要思想是将模式从高维空间映射到一个由部分特征向量张成的低维空间, 然后在低维空间上再以传统方式 (如k-means) 或其他方式聚类。在降维过程中, 将高维空间的模式结构映射到低维空间中, 保持代数性质或几何性质不变, 通过局部结构来计算和度量全局结构。Ncut算法的图像k类划分的具体步骤: (1) 将图像m×n映射为一个图, 图的每一个节点对应一个像元。令N=m×n, 把这个图用邻接矩阵的形式表示出来, 组成一个N×N的矩阵W, 矩阵W元素的值wij表示像元对之间的相似度; (2) 把W的每一列元素加起来得到N个数, 把它们放在对角线上 (其他地方都是零) , 得到矩阵W的节点度矩阵, 记为D。并令L=W-D, 得到Laplacian稀疏矩阵; (3) 求出L的前k个特征值{λ}ki=1以及对应的特征向量{v}kj=1; (4) 把这k个特征 (列) 向量排列在一起组成一个N×K的矩阵, 将其中每一行看作k维空间中的一个向量, 并使用k-means算法进行聚类。聚类的结果中每一行所属的目标类就是原来图中的节点亦即最初的N个数据点分别所属的目标类。
2.3 适用于谱聚类分析的图像
谱聚类分割图像的过程大致为三个步骤: (1) 相似性的度量, 计算像元对之间的相似性; (2) 制定聚类准则, 由目标函数来衡量聚类的好坏; (3) 计算和优化目标函数。针对上述三个方面来分析谱聚类的主要特性。
(1) 相似性的度量图G中节点i和j之间的边权重wij定义为特征相似指数函数与空间邻近指数函数的乘积, 其表达式如下:
上式中, σ是尺度参数, X (i) 表示节点i的空间位置, F (i) 表示像元的灰度、纹理特征或颜色特征向量。可见, wij仅仅表示区域r中像元间的局部相似性, 当节点i和j之间的距离大于r时, wij=0。
(2) 制定聚类准则。Ncut的目标函数形式如下:
其中V=A∪B, 表示A、B像元集合之间连接边的权重之和。、assoc (B, V) 分别表示集合A、B的所有像元连接图V的全部像元的权重之和。这样使得Ncut (A, B) 取得极小值, 保证类内相似度最大, 类间相似度最小。
(3) 计算和优化目标函数。由于谱聚类将像元集合分成不相交的连通片, 给像元分配离散值, 像0-1式的, 这种离散化, 会造成求解的NP问题。解决NP问题的步骤:先对目标函数变形, 利用Rayleigh quotient性质, 将目标函数的极值问题转化为特征值与对应的特征向量求取问题。于是 (2) 式转变成以下形式:
此时通用特征向量y被松弛到[-1, 1]实数域区间。对 (2) 式求极小值, 就转化为 (3) 式的极小特征值对应的特征向量中, 因为极小特征值为0, 因此取第二小特征值对应的特征向量去逼近, 由于图像聚类信息包含在特征向量中, 于是利用第二小特征值能够将图像分为两类。通过迭代, 能够完成图像的k类划分。
综上述所, 谱聚类算法具有识别非凸分布的聚类能力, 能够在连续域中获得全局最优解, 只需计算特征值与特征向量, 易于实现。它能够对任意图像的灰度、纹理、颜色或形状等特征进行分割, 同时对聚类结果具有较好的可解释性和可用性。
3 云模型和谱聚类的图像分割与分析
为了验证云模型和谱聚类的聚类特性, 分别对两种算法进行图像分割实验, 并对它们的聚类特性进行分析与比较。
3.1 基于云模型的图像分割
根据云模型的图像聚类算法的实验步骤, 对灰度图像Cameraman进行云变换和云综合, 得到两个定性概念, 一是人和部分建筑物, 二是天空和部分草地, 从而实现图像的灰度聚类。分割结果如图1所示。
3.2 基于谱聚类的图像分割
实验1是谱聚类方法对一幅山峦图像的分割, 其中仅仅包含灰度信息。分割只采用灰度相似关系构建相似矩阵。聚类数目定为4类, 分割结果如图2所示。
实验2是谱聚类方法对一幅房屋图像的分割, 其中包含灰度信息与明显的纹理信息。将灰度信息与纹理信息结合, 进行分割实验。聚类数目定为3类, 分割结果如图3所示。
实验3是谱聚类方法对一幅美女图像的分割, 其中包含颜色信息与纹理信息。将颜色信息与纹理信息结合, 进行分割实验。聚类数目定为14类, 分割结果如图4所示 (图片源自美国加州大学Berkeley分校的计算机视觉组) 。
3.3 图像分割下云模型和谱聚类的聚类特性比较
上述实验结果表明, 云模型与谱聚类对图像分割方法具有可行性。在谱聚类实验过程中, 实验2能够将纹理区域和非纹理区域较好地划分开, 通过组合方式划分, 将房屋的屋瓦和屋脊划分为一个区域。实验3将纹理特征与颜色特征组合一起, 将纹理区域和颜色区域较好地区分开。通过云模型和谱聚类的聚类分析和图像分割实验结果比较, 可以得出两者在聚类特性上的区别, 如表1所示。
参考文献
[1]JAIN A K, MURTY M N, FLYNN P J.Data Clustering:A Review[J].ACM Computing Surveys, 1999 (3) .
[2]M G.H OMRAN, ANDRIES P.ENGELBRECHT, A.Salman.An overv iew of clustering methods[J].Intelligent Data Analysis, 2007 (6) .
[3]李德毅, 杜鹢.不确定性人工智能[M].北京:国防工业出版社, 2005.
[4]FAN R K.Chung, Spectral Graph Theory[M].California:Fresno State University, 1997.
[5]秦昆.不确定性图像分割的新方法[D].武汉:武汉大学, 2007.
[6]J SHI AND J.MALIK.Normalized cuts and image segmentation[J].TPAMI, 2000.
[7]BACH, F, JORDAN, M.Learning spectral clustering[J].Neural Infor-mation Processing Systems, 2003.
[8]LUXBURG U.A Tutorial of spectral clustering[R].Technical Report149.August, 2006.
[9]J.MALIK, S.BELONGIE, T.LEUNG, et al.Contour and texture analy-sis for image segmentation[J].IJCV, 2001 (1) .
[10]T.LEUNG AND J.MALIK.Contour continuity in region-based im-age segmentation[J].Fifth European Conf.on Computer Vision, 1998, volume1.
浅谈聚类算法在图像分割中的应用 篇8
关键词：聚类算法,K均值,模糊聚类,均值漂移,近邻传播算法
随着信息技术的高速发展, 人们每天都处理大量的图像信息, 然而, 不是图像中的所有信息都是我们需要的, 所以, 这就需要我们进一步对图像进行处理, 得到能够满足人们需要的信息。这就需要我们通过技术手段把图像中特定的信息从整体中分割出来, 这便是图像分割, 即将输入的图像分割成若干有意义的目标区域[1]。近年来, 聚类算法在图像分割中有着广泛的应用。目前比较经典的聚类算法有:K均值聚类, 模糊聚类, 均值漂移算法, 近邻聚类算法。
1 聚类算法
⑴K均值聚类。K均值算法是最经典的聚类算法。由于其简单高效, 是应用最广泛的聚类算法。它的基本思想是:预先设定K类, 随机选中K个元素作为每一类的中心。计算其它元素与K个中心之间的聚类, 根据距离的大小, 归入距离最小的类中。然后重新计算每一个类的中心值, 即所有类中元素的平均值, 得到新的中心值后。再次重新分类, 不断重复此过程, 直到目标函数收敛。通常定义的目标函数为:
式中:p为对象空间中一个数据对象;mi为类ci的均值。
⑵模糊聚类。模糊聚类算法是由K均值聚类算法发展而来的。它的基本思想是:把所有元素分为C个模糊聚簇, 求出每个簇的中心, 使得非相似性指标的函数达到最小值。它在确定每一个元素时, 不是K均值非0即1, 而是使用0~1之间的数字来赋予元素隶属于某一簇的程度。它的目标函数为:FCM聚类算法目标函数为:
式中:Xj表示样本;N表示样本数目, 通常表示图像像素数;C表示聚类数目; 是矢量Xj隶属于第i类的隶属度函数, 满足uij∈[0, 1]且 ;Z表示聚类中心。
⑶均值漂移算法。均值漂移是一种不需要参数的无监督聚类方法。它的主要思想是, 在概率空间中求解概率密度极值的最优算法。它让每一个点漂移到密度函数局部最大值出, 即均值漂移向量的方向是数据的密度梯度估计方向一致。[2]文献[3]中对均值漂移算法原理的描述如下:假设核函数H如果满足一定的统计矩约束概率密度函数, 可以用于非参数概率密度估计, 若样本集{xi}n是依密度函数f (x) 经过n次独立抽样得到的, 则给出的密度函数估计为[4]:
其中, 核函数满足:
⑷近邻聚类算法。近邻传播聚类算法是一种基于近邻信息传播的聚类算法, 其目的是找到最优的类代表点集合, 一个类代表点对应为实际数据集中的一个数据点, 使得所有数据点到最近的类代表点的相似度之和最大。如果设数据点的相似度为数据点的欧式距离的负数, 则妙算法的目标函数与经典的K中心聚类算法的目标函数一致。近邻传播聚类算法还有两个重要的信息量参数, 分别是responsibility和availability, r (i, k) 表示从点i发送到候选聚类中心k的数值消息, 反映k点是否适合作为i点的聚类中心。a (i, k) 则从候选聚类中心k发送到i的数值消息, 反映i点是否选择k作为其聚类中心。r (i, k) 与a (i, k) 越强, 则k点作为聚类中心的可能性就越大, 并且i点隶属于以k点为聚类中心的聚类的可能性也越大。对于任意数据点xi, 计算所有数据点的r (i, k) 和a (i, k) 。
3 小结
K均值聚类由于其简单高效, 是应用最广泛的聚类算法。但是它也有很多局限性, 其中聚类类别的数目需要先验知识, 而初试聚类中心的选择不同也对聚类最终结果有很大的影响, 所以聚类的稳定性欠缺。
模糊聚类算法, 也是比较普遍使用的聚类算法。一般情况下不需要人为干预和设定阈值, 就可使图像分割区域自动化。但是模糊聚类数目的确定也是个难题, 需要先验知识, 而算法本身迭代过程计算量非常大, 而算法对噪音比较敏感, 所以, 时常会出现过分割现象。
均值漂移算法是一种无需任何参数的聚类算法, 对噪音有很好的鲁棒性, 可以处理任意形状和特征空间的图像, 非常适用于真实世界中的图像。但是该算法受核函数的影响比较大, 由于核函数参数的设置问题, 图像会产生过分割或欠分割现象。
近邻传播聚类算法, 相比较其它算法能更快的处理大规模数据, 得到较好的聚类结果。它对数据形成的相似矩阵的对称性没有任何要求, 所以其应用的范围很大。但是对于一些本书具有复杂结构的数据集, 近邻传播算法通常得不到合理的聚类结果。
参考文献
[1]Gonzalez Rafael C, Woods Richard E, Eddins Steven L.Digital Image Processing.阮秋琦, 等, 译.电子工业出版社, 2005.[1]Gonzalez Rafael C, Woods Richard E, Eddins Steven L.Digital Image Processing.阮秋琦, 等, 译.电子工业出版社, 2005.
[2]王爽, 夏玉, 焦李成.基于均值漂移的自适应纹理图像分割方法[J].Journal of Software, 2010, 21 (6) :1451-1461.[2]王爽, 夏玉, 焦李成.基于均值漂移的自适应纹理图像分割方法[J].Journal of Software, 2010, 21 (6) :1451-1461.
[3]沈占锋, 骆剑承, 胡晓东, 孙卫刚.高分辨率遥感影像多尺度均值漂移分割算法研究[J].武汉大学学报 (信息科学版) , 2010, 03:313-316.[3]沈占锋, 骆剑承, 胡晓东, 孙卫刚.高分辨率遥感影像多尺度均值漂移分割算法研究[J].武汉大学学报 (信息科学版) , 2010, 03:313-316.
