基于改进的K_means算法在图像分割中的应用

李栋+刘萌萌+郭莎

摘要：图像分割是图像处理中一种重要的图像分析技术。对灰度图像的分割，处理图像的亮度分量又是图像分割的基本方法。图像分割方法对区域的目标检测和模式识别有重要的意义。K_means算法是基于元素距离中心点的大小作为相似性度量的聚类算法。该文通过参数统计直方图来预估中心点k值的个数，并根据直方图峰值的位置来确定聚类中心的位置。该方法的初始聚类中心值与实际中心值相差不多，因此，大大减少了迭代次数，计算量更少。结果表明，改进K_Means聚类算法提高了图像分割的效率，降低了K_means算法的时间复杂度和空间复杂度。

关键词：K_means；聚类算法；图像分割；数据挖掘；图像处理

中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2016）08-0166-03

1 概述

根据图像处理方法和抽象程度的不同，图像技术可以分为图像理解、图像分析和图像处理三个层次，这三个层次的结合也称为图像工程。其中，最基本的操作是图像处理，主要进行的操作是在像素级上的。图像处理中比较有代表性的技术包括图像降噪、图像分割和图像编码。在图像处理中，图像分割是一种关键的技术，是图像理解和图像分析的基础。图像分割技术在图像理论中一直是发展的瓶颈之一。图像分割的应用非常广，比如对图像中目标的提取和测量都需要图像分割。图像分割是图像处理、模式识别和人工智能等多个领域中一个十分重要且又十分困难的问题。后续任务的有效性直接取决于图像分割的准确性。因此对图像分割的研究具有十分重要的意义。

图像分割[1-3]是一种比较特殊的图像处理技术。图像处理根据像素级别可以分成两类，一类是针对像素值的处理，另一类是把像素分类的处理。图像降噪技术、图像编码技术、数字水印技术等虽然各有其特点和应用领域，但其实质都是针对像素值的操作。图像分割是指将图像中有意义的特征或者需要应用的特征提取出来，以便进一步分析和研究。到目前为止，国内外学者已经提出了阈值法[4]、区域生长法[5]、遗传算法[6]等方法解决图像分割问题，取得了不少好的成果。不同于这些技术，本文提出一种基于改进的K_means算法，应用于图像分割领域，解决K_means固有的缺陷，并且提高图像分割的效率。

2 传统的K_means聚类算法思想

K_means主要是基于划分策略[9]，该方法在Data Mining领域中思想十分经典且用途广泛。其方法的基本思想是：首先用户根据以往经验及专业知识等通过人机交互人为预先定义聚集初始数目k，系统在所有对象中随机选择k个作为最初的聚集中心，根据距离（相似度）分别将初始k个对象距离最近的其他对象跟其当前对象归为一类。系统多次迭代该过程，逐次渐进更新各聚集中心的值，直至标准测度函数开始收敛为止。由于方差可以用来度量中心值和同类其他对象之间的偏离程度，也就是距离程度，所以一般该测度函数多采用方差表示，其定义如公式（1）所示：

其中K为预定义的归类数目，[Xi]为簇Ci的平均值，也就是中心点值。

所获得的聚类应满足高内聚低耦合特性，即同一类内对象间距离小；不同类之间的对象相似度低。

2.1 传统K_means算法

假设要把对象集D划分为k个不同类，传统k均值算法描述如下：

步骤1：人为预先从所有对象中随机选择k个的归类中心；

步骤2：对于对象集中的任意一个对象，分别计算其到各个中心对象的相似度，选择距离最小的那个对象作为该对象的同类对象，归为同类；

步骤3：对于各个归类中心的值，采用均值法更新；

步骤4：对于所有的归类中心，多次重复步骤2和3循环更新后，若其函数收敛或达到最大更新次数，则算法结束归类分类也结束，否则系统继续循环更新。

2.2 传统算法缺点

基于划分的思想使得该算法易于理解且实现简单，但是传统方法在实现聚类分类对象时存在两个主要缺点[10-11]：

1）首先该方法需要预先决定聚类的类数目，而在现实具体应用中类的数目是难以估计且难以准确确定的，不同的类数目往往在实现中可能会造成完全不同的分类结果。类的准确分类分数很难合理确定，尤其是对于复杂具有不确定性的未知对象样本集，类数目的选择需要根据以往的专业经验和行业知识并经过多次试验才能指定。为了取得较好的实验效果，需多次试探不同归类个数才能得到较为合理的类数目，这样就使得类的数目难以确定。

2）在传统算法中，需要先根据随机选定的初始归类中心进行初始划分，然后进一步对该划分进行不断的优化。由于初始中心选择的随机性，在系统实现聚类时可能会导致完全不同的归类结果，而实际的数据集不仅具有数据不确定性，且数据集中往往存在脏数据，算法实现中若取相互距离最远的k个对象值分别代表不同的类别，极有可能会取到脏数据中的对象，也就是噪声点，一开始的中心选取必然会影响到该数据集的聚类效果，容易使得聚类陷入局部最优，从而造成分割不准确，分割效果差的问题。

3 K_means算法的改进

针对算法固有的缺陷，近几年越来越多的研究人员投入研究，杨善林[12]等人给出距离代价函数作为最佳聚类数的有效性检验函数，提出了一种新的k值优化算法，k从0到n个点遍历，距离代价最小的k就是最终结果， 并且证明k最大为n的理论证明。但是该方法主要针对k值的优化，对于初始中心点没有进行研究。

汪中[13]等人改进初始中心点的算法，采用基于密度初始化中心点算法，根据数据集的密度散步搜索出簇类中心，间接找到对象出现密集的区域。利用密度分布搜索到聚类中心，遍历k，均衡化函数最小时对应个数为最优聚类个数k。解决了k需要人为指定并且原始中心随机的问题，但是它的时间复杂度相应增大。

屈新怀[14]等人将初始中心位置设置在密集数据区域的中心，避免孤立点和噪声的干扰，利用遗传算法生成聚类个数k。该方法要进行基于密度的中心点选择和遗传算法，都增加了时间复杂度，对于实时性要求比较高的情况，该算法不适合。