1、1K-means 聚类算法分析应用研究摘要： 本文浅谈了数字图像处理的发展概况、研究背景并对彩色图像 K-means算法进行分析.主要详细谈论了是对 K-means算法的一些认识，并且介绍 K-means聚类的算法思想、工作原理、聚类算法流程、以及对算法结果进行分析，得出其特点及实际使用情况。 关键字：数字图像处理；K-means 算法；聚类 一、数字图像处理发展概况及边缘的概念 数字图像处理（Digital Image Processing）即计算机图像处理，就是利用计算机对图像进行去除噪声、增强、复原、分割、特征提取、识别等处理的理论、方法和技术1。最早出现于 20世纪 50年代，它作为一
2、门学科大约形成于 20世纪 60年代初期。它以改善图像的质量为对象，以改善人的视觉效果为目的。在处理过程中，输入低质量图像，输出质量高图像，图像增强、复原、编码、压缩等都是图像处理常用的方法1。数字图像处理在航天、航空、星球探测、通信技术、军事公安、生物工程和医学等领域都有广泛的应用，并取得了巨大的成就。 边缘就是图像中灰度有阶跃变化或屋顶变化的像素的集合，边缘是图像最重要的特征之一，它包含了图像的大部分信息。实质上边缘检测就是采用算法提取图像中对象与背景间的交界线。在目标与背景、目标与目标、区域与区域、基元与基元之间都存在边缘，这是图像分割所依2赖的最重要的特征之一。根据灰度变化的剧烈程度，
3、边缘可以分为两种：一种是屋顶边缘，一种为阶跃性边缘。对于屋顶状边缘，二阶导数在边缘初取极值，而对阶跃性边缘，二阶导数在边缘处零交叉；。 二、彩色图像的 K-means聚类算法 （一）K-means 聚类 聚类就是把数据分成几组，按照定义的测量标准，同组内数据与其他组数据相比具有较强的相似性。K-means 聚类就是首先从 n个数据对象任选 k个对象作为初始聚类中心；剩下的其它对象，则根据它们与这些聚类中心的距离（相似度） ，分别将它们分配给与其最相似的（聚类中心所代表的）聚类；然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值） ；一直重复此过程直至标准测度函数收敛为止。通常都采用均方
4、差作标准测度函数。k 个聚类有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。 聚类的用途是很广泛的。在商业上，聚类可以帮助市场分析人员从消费者数据库中区分出不同的消费群体来，并且概括出每一类消费者的消费模式或者说习惯。它作为数据挖掘中的一个模块，可以作为一个单独的工具以发现数据库中分布的一些深层的信息，并且概括出每一类的特点，或者把注意力放在某一个特定的类上以作进一步的分析；并且，聚类分析也可以作为数据挖掘算法中其他分析算法的一个预处理步骤。 （二）算法思想分析 输入：聚类个数 k，以及包含 n 个数据对象的彩色图片。 输出：满足方差最小标准的 k个聚类。 3处理流程： (1)从
5、 n 个数据对象任意选择 k 个对象作为初始聚类中心； (2)根据每个聚类对象的均值（中心对象） ，计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分； (3)重新计算每个（有变化）聚类的均值（中心对象） ； (4)循环(2)到(3)直到每个聚类不再发生变化为止。 首先设置 K值，也就是确定若干个聚类中心。使用 rand函数随机获得 K个颜色值，存放在矩阵 miu中，第一次对每个像素点中的 K种颜色进行迭代运算，得到最小的颜色矩阵的 2范数，同时标记该颜色，依次相加的到各点的颜色矩阵总值。再次迭代得到 K中颜色的各个矩阵均值。最后提取出标记的各个颜色，依次对各个点进行颜色赋
6、值，使每个像素点的颜色归类。得到聚类后的图像。 （三）算法的数学描述 （四）算法过程分析 设置 K值为 8，读入一幅图片后计算图像上所有的像素点个数为 N，即令 N=size(X,1)*size(X,2)，令颜色矩阵 R为矩阵N,K并清零。随机获得颜色聚类中心为 Miu=fix(255*rand(K,3)。 在 10次迭代中，对每一个像素点进行 k=8次迭代，计算该点颜色值与各个聚类中心的欧氏距离 dis。若 dis最小，则标记此时颜色矩阵为R(n,k)=1。依次对 8个聚类中心迭代，计算标记的每一个坐标点的颜色总值 sum1和总数量 sum2，计算新的聚类中心 Miu(k,:)=sum1/s
7、um2。再4次对所有点进行迭代，根据第一次迭代时标记的 R(n,k)值，若 R(n,k)为真时，对该点颜色赋值为聚类中心 k的颜色值。依次分析聚类出最终效果图。 图 K-means 聚类算法流程图 （五）K-means 算法结果分析 K-means 算法取 K值为 8，就是通过对每个像素点进行 8次迭代找到欧式距离最小的聚类中心，依次迭代，得出平均聚类中心，以最后得到的 8个平均聚类中心为图像的最优聚类中心，依次为各个像素点进行聚类操作，最后得到聚类后的图像边缘。 本算法由于要对图像的各个像素均进行多次迭代，因此执行算法将会耗费很长时间，对一幅 800x600的图片进行一次聚类需要耗时 200
8、s左右，其运行效率较低。但是由于本算法采用的是动态获取聚类中心，且直接对彩色图像的 RGB颜色进行分析聚类，故得到的图像边缘检测效果比较好。K-means 算法的特点：聚类中心用各类别中所有数据的平均值表示。 三、结语 K-means 算法的一个特点就是在每次迭代中都要考察每个样本的分类是否正确。如果不正确必须调整，在调整完全部样本后，修改聚类中心，然后再进入下一次的迭代。K-means 算法工作原理3：首先算法随机从数据集中选 K个点作为初始聚类中心，再计算每个样本到聚类中距离，把样本归到离它最近的聚类中心所在的类。通过计算新形成的每一个聚5类的数据对象的平均值得出新聚类中心，若相邻两次的聚类中心没有变化，则证明样本调整结束，聚类准则函数已经收敛。若再一次迭代算法中，所有的样本被正确分类，就不会有调整，聚类中心也不变化，这就标志着已经收敛，算法结束。 参考文献： 1 何东健.数字图像处理.西安:西安电子科技大学出版社,2008； 2 史习云.改进的 k-means聚类算法在图像检索中的应用研究D.中国优秀硕士学位论文全文数据库,2010,(08)； “本文中所涉及到的图表、公式、注解等请以 PDF格式阅读”
