信息疼术2018年第6期文章编号=1009 -2552 (2018)06 -0092 -03 DOI：10.13274/ki.hdzj.2018. 06.019基于聚类的图像分割方法综述赵祥宇\陈沫涵2(1.上海理工大学光电信息与计算机学院，上海200093; 2.上海西南位育中学，上海200093)摘要：图像分割是图像识别和机器视觉领域中关键的预处理操作。
分割理论算法众多，文中 具体介绍基于聚类的分割算法的思想和原理，并将包含的典型算法的优缺点进行介绍和分析。
经过比较后，归纳了在具体应用中如何对图像分割算法的抉择问题。
近年来传统分割算法不断 被科研工作者优化和组合，相信会有更多的分割新算法井喷而出。
关键词：聚类算法；图像分割；分类中图分类号：TP391.41 文献标识码：AA survey of image segmentation based on clusteringZHAO Xiang-yu1，CHEN Mo-han2(1.School of Optical Electrical and Computer Engineering，University of Shanghai for Science and Technology，Shanghai200093，China；2.Shanghai Southwest Weiyu Middle School，Shanghai200093，China) Abstract:Image segmentation is a key preprocessing operation in image recognition and machine vision. There are many existing theoretical methods,and this paper introduces the working principle ol image segmentation algorithm based on clustering.Firstly,the advantages and disadvantages ol several typical algorithms are introduced and analyzed.Alter comparison,the paper summarizes the problem ol the selection ol image segmentation algorithm in practical work.In recent years,the traditional segmentation algorithms were improved and combined by the researchers,it believes that more new algorithms are blown out.Key words:clustering algorithm；image segmentation；classilication0引百近年来科学技术的不断发展，计算机视觉和图像 识别发挥着至关重要的作用。
在实际应用和科学研 究中图像处理必不可少,进行图像处理必然用到图像 分割方法,根据检测图像中像素不重叠子区域，将感 兴趣目标区域分离出来。
传统的图像分割方法:阈值 法[1]、区域法[2]、边缘法[3]等。
近年来传统分割算法 不断被研究人员改进和结合，出现了基于超像素的分 割方法[4]，本文主要介绍超像素方法中基于聚类的经 典方法，如Mean Shift算法、K-m eans 算法、Fuzzy C-mean算法、Medoidshilt算法、Turbopixels算法和 SLIC 算法。
简要分析各算法的基本思想和分割效果。
1聚类算法1.1 Mean Shil't算法1975年,Fukunaga[5]提出一种快速统计迭代算法，即Mean Shilt算法（均值漂移算法）。
直到1995 年,Cheng[6]对其进行改进，定义了核函数和权值系 数，在全局优化和聚类等方面的应用，扩大了 Mean shil't算法适用范围。
1997至2003年间，Co-maniciu[7-9]提出了基于核密度梯度估计的迭代式 搜索算法,并将该方法应用在图像平滑、分割和视频 跟踪等领域。
均值漂移算法的基本思想是通过反复 迭代计算当前点的偏移均值，并挪动被计算点，经过 反复迭代计算和多次挪动，循环判断是否满足条件, 达到后则终止迭代过程[10]。
Mean shil't的基本形 式为：收稿日期：2017-06 -13基金项目：国家自然科学基金资助项目（81101116)作者简介：赵祥宇（1992-)，男，硕士研究生，研究方向为数字图像处理。
—92 —M h(x)=!X(x，-x)⑴其中，^是一个h为半径的圆形区域，圆形区域内包含尺个数据样本点。
从样本中选择一个初始点以此为圆心，画h为半径的一个圆。
计算圆内所有点到圆中心点之间的向量总和,可称为Meanshift向量。
重复以上步骤,通过有限次迭代计算，该算法会得到一个概率密度最大的收敛点，即数据分布的稳定点，称为密度极大值点。
通过Meanshift对做图像做分割处理，就是把具有相同密度极大值点的像素聚类到同一区域的过程。
其定义[11]为：- 2C= arg m^in X I I' -之I I屮（I I1h^H)⑵Meanshift算法的优点是稳定性和鲁棒性较好，具有广泛的应用前景。
该算法缺点在于给定的图像 语义信息较少，进行分割时效果较差，同时时间复杂 度较高，导致分割速度慢，图像分割块数量变得不 可控。
1.2 K-means算法1967年，Macquine改进算法后提出了 K-means 聚类算法,可用来处理数据聚类的问题。
该算法高 效简单在实际应用和理论研究中应用十分广泛。
通 过计算样本中的每个聚类中所有像素点的平均值进 而得出聚类中心点。
K-means算法的基本工作原理 是接收用户输人的参数（将给定的^个数据样本点平均分成K个组，把输人的K个点作为要收敛的 聚类中心。
计算簇中其他采样点到尺个收敛中心 点的欧氏距离，并对比全部采样点和收敛中心点之 间的距离。
通过对比最小的欧氏距离进行归类，然 后经重复迭代，逐次得到尺个聚类的均值。
直到聚 类的性能准则函数最优,整体误差最小，获得最佳的 聚类效果。
优点是一种处理聚类问题的简单快速高效的算 法。
此算法对处理大数据集是相对可扩展和高效率 的。
其时间复杂度是〇(^沿），其中W代表所有数 据样本的总和，尺代表簇的个数^代表算法迭代次 数，其中选取且。
当使用算法分割图像 中所包含的聚类数量较多，且每个聚类之间差异明 显时，效果较好。
缺点在于算法中的聚类数目K值是用户必须 事先给出，初始聚类中心点的确定将会影响整个分 割效果。
当处理不规则形状的聚类时，由于采用距 离函数作为判别样本间相似度的方法，会对分割结 果产生影响。
聚类后的结果易受到噪音点的影响，同样会对结果不利。
1.3 Fuzzy C-mean算法Ruspini[l2]率先提出了一种基于目标函数的模 糊聚类分析方法。
Dunn[l3]在1974年时，率先将硬 聚类加人到模糊聚类方法中，同年，Bezdek提出模 糊C均值聚类算法理论。
1980年Bezdek对Fuzzy C-means(模糊C均值）算法的收敛性在文献[l4]进 行证明，表明FCM算法最终会收敛到一个极值处。
Fuzzy C-mean聚类算法对K-means算法做出改进，由于图像目标的类别属性在实际应用中难以准确区 分,提出了隶属度的概念，并通过隶属度判断每个目 标样本的隶属度。
Fuzzy C-mean聚类的基本工作原 理是,将提供的《个样本分为C组,通过迭代寻找 各个组的聚类中心与隶属度值％,使非相似性指 标的目标函数J(R F)取最小值[15—17]。
该算法将 隶属度0至1分别分派给每个数据对象，数据对象 所属于哪类的问题是由隶属度值来决定。
且规定每 一个样本的隶属度值的总和是1。
优点在于当使用算法分割图像中所包含的聚类 数量较多,且每个聚类之间差异明显时，可以实现简 单高效的聚类且效果较好。
但不足之处在于需要接 收参数C，若给定的参数的不恰当，会对聚类结果产 生负面影响。
当给定的待检测数据样本总数过大并 特征点过多，其聚类效果不好。
由于算法没有分析 图像中各个像素间的领域关系，导致分割后的样本 点易受噪声点的影响。
1.4 Medoidshift算法为了扩大Mean Shift算法的应用范围，在Mean Shift算法的基础上Sheikh等人[18]提出了Me-doidshift算法。
Medoidshift算法与 MeanShift算法相 类似，同样可以收敛至聚类中心，并计算聚类的数 目。
不同之处,MeanShift算法经过多次迭代计算出 的均值，即偏移值。
相比较Medoidshift算法不要求 求出平均值,而是从数据中将偏移值取出，但仍然需 要确定两点之间距离。
Medoidshift算法每次迭代会 计算出新的中心点，并非新位置，中心点可以被定义 如下：- 2 =arg min X||'-Z||V( ||*h7k ||) (3)MeanShift算法，其时间复杂度为0(抓27〇，(d 为数据维度，^为算法迭代次数，W为样本总数）。
相比较Medoidshift聚类算法的劣势是其时间消耗 过大，在0(dW2 +妒）至0(抓+#38)之间。
Ved-aldi等人[19]对Medoidshift算法做出改进，其不需要 使用梯度来寻找概率密度的模式，而仅仅是将每个 点移动到使概率密度增加的最近的点来获得，此算—93 —法称为Quickshift 。
其时间复杂度降到了 0( dW 2), 改进了其速度慢的缺点。
但Qukkshift 算法由于采 用非迭代的方式，对图像块的数量和大小不能有效 的控制。
1.5 Turbopixels 算法Turbopixels 算法在 2009 年被 Levinshtein 等人[2°]提出，是一种几何流的超像素快速分割算法。
使用超像素分割算法分割图像像素块应先满足以下 几个条件:①每个图像块尺寸大小尽可能均勻;②各 个图像块之间紧凑连接且保持连通;③各图像块彼此不覆盖且每块边界光滑无特殊棱角。
Turbopixels 算法的具体实现流程如下：①首先为避免在给种子点定义时被噪声污染, 特添加扰动。
② 对图像中的像素点进行标记。
③ 初始化水平集函数。
④ 执行以下步骤,通过反复迭代并检验种子点 膨胀边缘的演化速度是否为0,若达到则停止，反之 继续，一是首先水平集曲线函数演化;二是开始对未 分配区域进行比较;三是边界上的所有像素点的演 化速度是由根据比较的结果进行更新。