基于改进的K―means聚类算法在图像分割中的研究

来源:用户上传      作者:

　　摘 要：图像分割是由图像处理到图像分析的关键步骤。传统的K-means聚类算法在进行图像分割处理时，由于其算法本身的一些缺陷，使得图像颜色像素在进行聚类时会出现比较高误分类率，为了降低这一比率本文将一种改进的K-means聚类方法应用于图像分割研究中，取得了明显的效果。
　　关键词：K-means聚类；图像分割；欧几里得距离
　　中图分类号：TP18
　　图像分割技术在数字图像处理领域是十分重要的一部分。近年来，研究人员不断改进原有的图像分割方法并把其它学科的一些新理论和新方法用于图像分割，提出了不少新的分割方法。
　　图像分割就是把图像分成若干个特定的、具有独特性质的区域并提出感兴趣目标的技术和过程。一般人们在研究一副图像时，往往只对图像中的某些部分感兴趣。图像分割就是借助场景图像的特征信息将图像划分成一些有意义的区域，这些特征包括梯度、灰度、色彩和形状等。另外，图像分割作为从图像处理到图像分析的关键步骤，为更高层次的图像理解奠定了基础。
　　目前彩色图像分割技术主要采用的方法有：直方图阀值化，特征空间聚类分析方法，基于区域的方法，边缘检测，模糊技术和人工神经网络的方法等。其中特征空间聚类分析方法是一种不需先验知识的统计方法，其具有算法简单、快速，收敛性好等优点，成为目前进行图像分割处理首选的方法之一。
　　1 传统K-means聚类方法
　　K-means聚类方法是在1967年由Mac Queen提出的，是目前最流行的聚类分析方法之一。K-means算法的基本思想是从随机捡取的K个聚类中心开始，根据欧几里得距离把每个点分配到最接近其均值的聚类中，然后计算被分配到每个聚类的点的均值向量，并作为新的中心进行递归，直到聚类中心不再发生变化。在这种分类情况下，同一类中的数据相似度最大，不同类间的数据差异性最大。
　　针对以上传统的K-means算法思想，也存在着不少缺点，最主要的两个缺陷在于：（1）初始聚类中心的选取直接影响最终的聚类结果，可能形成局部最优解而聚类失败；（2）聚类数目无法确定，只能根据以往经验进行大概估计，这样一般不能最佳的聚类效果。以下就针对初始聚类中心的选取对传统的K-means算法进行改进。
　　2 改进的K-means算法
　　由于聚类算法的目标是要尽可能的将相似度越小的数据对象归为一类，而将相似度越大的数据对象归为不同类。因此，不同类别的聚类中心一般是相似度比较小的，即欧几里得距离比较远的两个数据对象。这样选取出来的初始聚类中心才能达到比较好的聚类结果。根据此推论，初始聚类中心的选取，应该尽量保证其之间的距离大。通常情况下样本数据集是比较庞大的，我们可以采取逐一划分依次确定聚类中心的方法：首先，我们按照经验给出我们要确定的聚类中心的个数K，接着，在数据集中找出距离最远的两个数据对象作为最初的两个聚类中心，对剩下的所有数据计算它们到这两个中心的距离，按照距离最小划分到离它们最近的聚类中心的所属类中，这样就把数据集划分成了以这两个数据对象为聚类中心的两个类。接下来，对包含数据对象多的这个类以同样的方法选出2个新的聚类中心并划分成2个新的类，重复操作直到找出K个聚类中心为止。由于，每次划分都是找相距最远的数据对象作为聚类中心，因此，通过以上方法所获得的K个聚类中心两两之间有较大的距离。
　　对于初始聚类数据集M={x1，x2，x3，…，xm-1，xm}，有m个数据对象，从M中选择K个数据对象作为初始聚类中心的具体步骤是：
　　（1）初始化数据集M。
　　（2）建立K个空类簇，对其中一个初始化为数据集M。
　　（3）计算所有类簇包含数据元素的个数，选择其最多的一个类簇，标记为N。
　　（4）计算N中两两数据对象之间的欧几里得距离，找出其中距离最大的两个数据对象xi和xj，将xi和xj标记为X类和Y类，并填充到空类簇中。
　　（5）以xi和xj为聚类中心，分别计算N中剩余数据对象到xi和xj得欧几里得距离，将它们划分到离它们距离最小的类中。
　　（6）检查是否将数据集M划分为K个类簇，是则结束，否则转至3）。
　　3 实验分析
　　我们将改进后的算法和传统的K-means聚类算法进行对比：对于图像的分割结果，难免产生错分的像素，而错分像素数据是衡量图像分割质量的一个非常重要的数据标准。本文用具有代表性的5个图像进行两种算法的聚类处理，最后统计出误差概率如表1所示。
　　从表1我们可以看出本文改进之后的K-means算法在对图像颜色数据进行聚类处理时，误分类像素比率有明显的降低。说明本文的算法在彩色图像分割方面具有更好的优越性，并具有一定的鲁棒性。
　　4 结束语
　　从上面的实验结果可以看出改进之后的K-means聚类算法确实可以降低像素的误分类率，但是降低的幅度比较小。因此，接下来的工作可以从K-means聚类的其他几个缺陷处入手，结合其他学科多种方法来进一步降低误分率和提高算法的时间和空间效率。
　　参考文献：
　　[1]Han J，Kamber M（加）.范明，孟小峰，译.数据挖掘概念与技术[M].北京：机械工业出版社，2001：223-262.
　　[2]吴夙慧，成颖，郑彦宁.K-means算法研究综述[J].现代图书情报技术，2011（05）：28-35.
　　[3]陈光平，王文鹏，黄俊.一种改进初始聚类中心选择的K-means算法[J].小型微型计算机系统，2012（33）：1320-1323.
　　[4]林开颜，吴军辉，徐立鸿.彩色图像分割方法综述[J].中国图象图形学报，2005（10）：1-10.
　　[5]汤叶青.K-means算法的改进研究[D].北京首都师范大学，2012：19-26.
　　[6]张玉芳，毛嘉莉，熊忠阳.一种改进的K-means算法[J].计算机应用，2003（23）：31-33.
　　作者简介：姚丽君（1980-），女，陕西宝鸡人，助教，本科，研究方向：图形图像处理。
　　作者单位：衡阳师范学院，湖南衡阳 421008
　　基金项目：衡阳师范学院科学基金项目（项目编号：12A20）。
转载注明来源:https://www.xzbu.com/8/view-6524615.htm