文档介绍：基于K-means 的图像分割
一、实验目的
通过 K-means 聚类实现图像分割。
二、算法描述
图像分割就是把图像分成若干个特定的、具有独特性质的区域并提出感兴趣目标的技术和过程。它是由图像处理到图像分析的关键步骤。现有的图像分割方法主要分以下几类:基于阀值的分割方法、基于区域的分割方法、基于边缘的分割方法以及基于特定理论的分割方法等。近年来,研究人员不断改进原有的图像分割方法并把其它学科的一些新理论和新方法用于图像分割,提出了不少新的分割方法。
K-means 算法是很典型的基于距离的聚类算法,采用距离作为相似性的评价指标,即认为两个对象的距离越近,其相似度就越大。该算法认为簇是由距离靠近的对象组成的,因此把得到紧凑且独立的簇作为最终目标。
K-means算法的工作原理:算法首先随机从数据集中选取 K个点作为初始聚类中心,然后计算各个样本到聚类中的距离,把样本归到离它最近的那个聚类中心所在的类。计算新形成的每一个聚类的数据对象的平均值来得到新的聚类中心,如果相邻两次的聚类中心没有任何变化,说明样本调整结束,聚类准则函数已经收敛。本算法的一个特点是在每次迭代中都要考察每个样本的分类是否正确。若不正确,就要调整,在全部样本调整完后,再修改聚类中心,进入下一次迭代。如果在一次迭代算法中,所有的样本被正确分类,则不会有调整,聚类中心也不会有任何变化,这标志着已经收敛,因此算法结束。
算法过程如下:
为中心向量c1, c2, …, ck初始化k个种子
分组:将样本分配给距离其最近的中心向量
由这些样本构造不相交( non-overlapping )的聚类
确定中心:用各个聚类的中心向量作为新的中心
重复分组和确定中心的步骤,直至算法收敛
输入:k,data[n];
三、算法的步骤
(1) 从数据集中任意选取k个赋给初始的聚类中心c1, c2, …, ck;
(2) 对数据集中的每个样本点xi,计算其与各个聚类中心cj的欧氏距离并获取其类别
标号:
(3) 按下式重新计算k个聚类中心;
(4) 重复步骤2和步骤3,直到达到最大迭代次数为止。
四、程序
我在本次实验中对图像进行了分割这让我对K-means 聚类算法有了更深一步的了解与应用,我了解到该算法的一些优缺点:
K-means 算法的特点——采用两阶段反复循环过程算法,结束的条件是不再有数据元素被重新分配:
①指定聚类,即指定数据到某一个聚类,使得它与这个聚类中心的距离比它到其它聚类中心的距离要近。
②修改聚类中心。
优点:本算法确定的K 个划分到达平方误差最小。当聚类是密集的,且类与类之间区别明显时,效果较好。对于处理大数据集,这个算法是相对可伸缩和高效的,计算的复杂度为O(NKt),其中N是数据对象的数目,t是迭代的次数。一般来说,K<<N,t<<N 。
缺点主要有三个:
①在 K-means 算法中 K 是事先给定的,这个 K 值的选定是非常难以估计的。很多时候,事先并不知道给定的数据集应该分成多少个类别才最合适。这也是 K-means 算法的一个不足。有的算法是通过类的自动合并和分裂,得到较为合理的类型数目 K,例如 ISODATA 算法。关于 K-means 算法中聚类数目K 值的确定在文献[23]中,是根据方差分析