基于k均值聚类的图像分割研究2012

1、 多媒体通信课程论文姓 名：严宏海班 级: 075102学 号：专 业: 通信工程 学 院：机械与电子信息学院指导老师: 刘 勇 日 期：2012年10月20日 k均值聚类在彩色图像分割中的应用研究摘要 基于人类视觉将图像分割成若干个有意义的区域是目标检测和模式识别的基础。 图像分割属于图像处理中一种重要的图像分析技术。图像分割的传统方法是对灰度图像分割，处理图像的亮度分量，简单快速。本论文首先介绍了传统的图像分割与K-均值聚类算法分割，然后重点介绍一种基于K-均值聚类算法的图像改进分割方法。在分析聚类结果对初值依赖性的基础上,对初值选取方法进行了分析和研究,结合粗糙集理论和K-均值聚类算法，

2、提出了一种图像的粗糙聚类分割方法，试验结果表明，其比随机选取聚类的中心点和个数，减少了运算量，提高了分类精度和准确性。改进的分割方法能够实时稳定的对目标分割提取，分割效果良好。引言根据抽象程度和处理方法的不同，图像技术可以分为三个层次：图像处理、图像分析和图像理解，这三个层次的有机结合也可以称为图像工程。图像处理是较低层的操作，主要在图像像素级上进行操作。有代表性的图像处理技术包括图像降噪、图像编码和图像分割。图像分割是一种关键的图像处理技术。作为后续图像分析和图像理解的基础，图像分割技术一直是图像理论发展的瓶颈之一。图像分割在实际中的应用非常广泛，对图像目标的提取、测量都离不开图像分割，是图

3、象处理、模式识别和人工智能等多个领域中一个十分重要且又十分困难的问题。分割的准确性直接影响后续任务的有效性，因此具有十分重要的意义。图像分割又是一种特殊的图像处理技术。像素级的图像处理可以分成两类，一类是针对像素值的处理，另一类是把像素分类的处理。图像降噪技术、图像编码技术、数字水印技术等虽然各有其特点和应用领域，但其实质都是针对像素值的操作。不同于这些技术，图像分割，其实质是一个按照像素属性（灰度、纹理、颜色等）进行聚类的过程。一图像分割概述 图像分割是一种重要的图像分析技术。在对图像的研究和应用中，人们往往仅对图像中的某些部分感兴趣。这些部分常称为目标或前景（其他部分称为背景）。它们一般对

4、应图像中特定的、具有独特性质的区域。为了辨识和分析图像中的目标，需要将它们从图像中分离提取出来，在此基础上才有可能进一步对目标进行测量，对图像进行利用。图像分割就是把图像分成各具特性的区域并提取出感兴趣目标的技术和过程。现有的图像分割方法主要分以下几类：基于阈值的分割方法、基于区域的分割方法、基于边缘的分割方法以及基于特定理论的分割方法等。1. 基于阈值的分割方法包括全局阈值、自适应阈值、最佳阈值等等。阈值分割算法的关键是确定阈值，如果能确定一个合适的阈值就可准确地将图像分割开来。阈值确定后，将阈值与像素点的灰度值比较和像素分割可对各像素并行地进行，分割的结果直接给出图像区域。全局阈值是指整幅

5、图像使用同一个阈值做分割处理，适用于背景和前景有明显对比的图像。它是根据整幅图像确定的：T=T(f)。但是这种方法只考虑像素本身的灰度值，一般不考虑空间特征，因而对噪声很敏感。常用的全局阈值选取方法有利用图像灰度直方图的峰谷法、最小误差法、最大类间方差法、最大熵自动阈值法以及其它一些方法。2基于边缘的分割方法检测灰度级或者结构具有突变的地方，表明一个区域的终结，也是另一个区域开始的地方。这种不连续性称为边缘。不同的图像灰度不同，边界处一般有明显的边缘，利用此特征可以分割图像。图像中边缘处像素的灰度值不连续，这种不连续性可通过求导数来检测到。对于阶跃状边缘，其位置对应一阶导数的极值点，对应二阶导

6、数的过零点(零交叉点)。因此常用微分算子进行边缘检测。常用的一阶微分算子有Roberts算子、Prewitt算子和Sobel算子，二阶微分算子有Laplace算子和Kirsh算子等。在实际中各种微分算子常用小区域模板来表示，微分运算是利用模板和图像卷积来实现。这些算子对噪声敏感，只适合于噪声较小不太复杂的图像。3基于聚类分析的图像分割方法特征空间聚类法进行图像分割是将图像空间中的像素用对应的特征空间点表示，根据它们在特征空间的聚集对特征空间进行分割，然后将它们映射回原图像空间，得到分割结果。其中，K均值、模糊C均值聚类(FCM)算法是最常用的聚类算法。K均值算法先选K个初始类均值，然后将每个像

7、素归入均值离它最近的类并计算新的类均值。迭代执行前面的步骤直到新旧类均值之差小于某一阈值。模糊C均值算法是在模糊数学基础上对K均值算法的推广，是通过最优化一个模糊目标函数实现聚类，它不像K均值聚类那样认为每个点只能属于某一类，而是赋予每个点一个对各类的隶属度，用隶属度更好地描述边缘像素亦此亦彼的特点，适合处理事物内在的不确定性。利用模糊C均值(FCM)非监督模糊聚类标定的特点进行图像分割，可以减少人为的干预，且较适合图像中存在不确定性和模糊性的特点。二K均值聚类分割算法2.1 聚类将物理或抽象对象的集合分成由类似的对象组成的多个类的过程被称为聚类。由聚类所生成的簇是一组数据对象的集合，这些对象

8、与同一个簇中的对象彼此相似，与其他簇中的对象相异。聚类分析又称群分析，它是研究（样品或指标）分类问题的一种统计分析方法。聚类分析计算方法主要有如下几种：划分方法，层次方法，基于密度的方法，基于网格的方法，基于模型的方法。K-均值聚类算法是著名的划分聚类分割方法。划分方法的基本思想是：给定一个有N个元组或者纪录的数据集，分裂法将构造K个分组，每一个分组就代表一个聚类，K<N。而且这K个分组满足下列条件：（1） 每一个分组至少包含一个数据纪录；（2）每一个数据纪录属于且仅属于一个分组；对于给定的K，算法首先给出一个初始的分组方法，以后通过反复迭代的方法改变分组，使得每一次改进之后的分组方案都

9、较前一次好，而所谓好的标准就是：同一分组中的记录越近越好，而不同分组中的纪录越远越好。2.2 K-均值聚类算法的工作原理：K-means算法的工作原理：算法首先随机从数据集中选取 K个点作为初始聚类中心，然后计算各个样本到聚类中的距离，把样本归到离它最近的那个聚类中心所在的类。计算新形成的每一个聚类的数据对象的平均值来得到新的聚类中心，如果相邻两次的聚类中心没有任何变化，说明样本调整结束，聚类准则函数 已经收敛。本算法的一个特点是在每次迭代中都要考察每个样本的分类是否正确。若不正确，就要调整，在全部样本调整完后，再修改聚类中心，进入下一次迭代。这个过程将不断重复直到满足某个终止条件，终止条件可

10、以是以下任何一个： （1）没有对象被重新分配给不同的聚类。 （2）聚类中心再发生变化。 （3）误差平方和局部最小。2.3 K-means聚类算法的一般步骤：处理流程：（1） 从 n个数据对象任意选择 k 个对象作为初始聚类中心；（2） 循环（3）到（4）直到每个聚类不再发生变化为止；（3） 根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分；（4） 重新计算每个（有变化）聚类的均值（中心对象），直到聚类中心不再变化。这种划分使得下式最小 2.4 K-均值聚类法的缺点： 缺点: （1）在 K-means 算法中 K 是事先给定的，这个 K

11、值的选定是非常难以估计的。 （2）在 K-means 算法中，首先需要根据初始聚类中心来确定一个初始划分，然后对初始划分进行优化。（3） K-means算法需要不断地进行样本分类调整不断地计算调整后的新的聚类中心因此当数据量非常大时算法的时间开销是非常大的。（4）K-means算法对一些离散点和初始k值敏感，不同的距离初始值对同样的数据样本可能得到不同的结果。三基于灰度空间的彩色图像像素聚类 1读取彩色图像，将RGB值转化为灰度值 2. 利用k均值聚类对像素的灰度值进行划分，提取特征点（本方法采用误差平方和准则函数判断聚类是否合理）。 3.利用matlab编程实现结果如下：随即地取c1(1)=

12、15; c2(1)=100; c3(1)=150;%选择三个初始聚类中心得到最终聚类中心的灰度值如下：R =36.4825 G =165.2593 B =232.4027 随机选取聚类中心的K-均值聚类结果：图一四改进的k-均值聚类图像分割算法4.1 K-均值聚类算法中重要的一步是初始聚类中心的选取，一般是随机选取待聚类样本集的K个样本，聚类的性能与初始聚类中心的选取有关，聚类的结果与样本的位置有极大的相关性。一旦这 K个样本选取不合理，将会增加运算的复杂程度，误导聚类过程，得到不合理的聚类结果。通过粗糙集理论提供 K-均值聚类所需要的初始类的个数和均值，提高了聚类的效率和分类的精度。 于粗糙

13、集理论的灰度空间划分1.粗糙集的研究对象是由一个多值属性集合描述的对象集合。主要思想是在保持分类能力不变的情况下，通过知识约简，导出问题的决策和分类规则4。粗糙集理论能很好地近似分类。从图像的直方图可以看出图形一般呈谷峰状分布，同一区域内像素的灰度值比较接近，而且不同区域内像素数大小不等。若灰度值相差不大的像素可归为一类，则可将图像分为几类。为此，定义像素的灰度值差为条件属性，等价关系R定义为：如果两个像素灰度值差小于定间距D，则两个像素是相关的，属于等价类，即R一z|z。一z，I<D(i，J一0，1，.，255)首先确定间距D，通过原图可求出灰度值分布范围，根据灰度值范围可求出灰度级数

14、L。将灰度级范围内对应像素个数最多的灰度值定义为中心点P。计算L个中心点之两两间距，若最小距离小于间距D，则将相应中心点合并，并将两点的算术平均值作为该中心点的值。重复进行直到所有中心点的两两间距均大于间距D。中心点的个数和数值就是K_均值聚类所需要的初始类的个数和均值。2.像素的灰度值为，其中为第 i次迭代后赋给类j的像素集合, 为第 j类的均值。 具体步骤如下： 将粗糙集理论提供的L个中心点P作为初始类均值 ,。 在第次迭代时，考察每个像素，计算它与每个灰度级的均值之间的间距，即它与聚类中心的距离 D，将每个像素赋均值距其最近的类，即 (3.6)则。对于,计算新的聚类中心，更新类均值:，式

15、中，是中的像素个数。将所有像素逐个考察，如果，有 ，则算法收敛，结束；否则返回继续下一次迭代。 以上聚类过程结束后，为了增强显示效果，分割结果各像素以聚类中心灰度值作为该类最终灰度针对上图，根据改进后的K-均值聚类算法： 图二由原图像的灰度直方图，本文将定间距D设为32，灰度级L的个数为8。原灰度图的灰度值范围为0，255，被分成8个灰度级，七个灰度级对应中心点P为32，64，96，128，160，192，224，256。计算这12个中心点之两两间距，若最小距离小于间距20，则将相应中心点合并，并将两点的算术平均值作为该中心点的值，处理后结果为P32,160，192下面将c1(1)=32;c2

16、(1)=160;c3(1)=192;作为初始聚类中心，编程进行聚类分析。得到结果如下： 图三图三与图一相比分类结果更好，图像分割效果更明显，更能表现图像特征。边缘更加清晰，分割结果既突出了目标，又保留了细节信息，达到了较好的分割效果。因此，基于粗糙集的K_均值聚类算法可以有效地对灰度图像进行分割，从分割后的图像中可获取更多的目标信息，为进一步的图像分析和理解提供了良好的基础。4.2 继续对多幅图像用上述两种方法进行K-均值聚类分割，得到如下对比图像：K-均值聚类得到的：根据改进后的K-均值算法得到的：试验表明，基于粗糙集理论和K-均值聚类算法的图像分割方法，比随机选取聚类的中心点和个数减少了运

17、算量，提高了分类精度和准确性，而且对于低对比度、多层次变化背景的图像的形状特征提取具有轮廓清晰、算法运行速度快等特点，是一种有效的灰度图像分割算法。参考文献1 林开颜,吴军辉,徐立鸿. 彩色图像分割方法综述J . 中国图象图形学报, 2005, 10 (1) :1- 10.2滕升华. 黑白影像的彩色化研究D . 北京:中国科学院电子学研究所, 2006.3 章毓晋图像分割M北京：科学出版社，200l4蔡煦，朱波，曾广周一种彩色多级闯值的图像分割方法及在形状特征提取方面的应用J山东大学学报(工学版)，2002，32(4)：3333365 吴国雄，陈武凡图像的模糊增强与聚类分割J小型微型计算机系统

18、，1994，15(11)：21266.童星.王命延一种基于粗糙集的图像边缘检测方法期刊论文-计算机与现代化 2009(10)7黄长专.王彪.杨忠图像分割方法研究期刊论文-计算机技术与发展 2009(6)8 周萍. 改进的图像分割遗传K􀀁均值聚类算法 J . 海军工程大学学报, 2009, 6, 21( 3) : 75-78. 9 张忠林, 曹志宇, 李元韬. 基于加权欧式距离的K􀀁means 算法研究 J . 郑州大学学报: 工学版, 2010, 31( 1) : 89-92.10 11 附一：K-均值聚类改进前的matlab源程序 RGB,map= imr

19、ead ('F:a.jpg'); %读入imshow(RGB);title(' 图一 原图像')img=rgb2gray(RGB);m,n=size(img);figuresubplot(2,2,1),imshow(img);title(' 图二 原图像的灰度图像')subplot(2,2,2),imhist(img);title(' 图三 聚类前的灰度图像直方图') img=double(img);for i=1:m*n c1(1)=25; c2(1)=125; c3(1)=200;%选择三个初始聚类中心 r=abs(img-c

20、1(i); g=abs(img-c2(i); b=abs(img-c3(i);%计算各像素灰度与聚类中心的距离 r_g=r-g; g_b=g-b; r_b=r-b; n_r=find(r_g<=0&r_b<=0);%根据K的大小改变此处条件，寻找最小的聚类中心 n_g=find(r_g>0&g_b<=0);%寻找中间的一个聚类中心 n_b=find(g_b>0&r_b>0);%寻找最大的聚类中心 i=i+1;%更新聚类中心 c1(i)=sum(img(n_r)/length(n_r);%将所有低灰度求和取平均，作为下一个低灰度中心 c

21、2(i)=sum(img(n_g)/length(n_g);%将所有低灰度求和取平均，作为下一个中间灰度中心 c3(i)=sum(img(n_b)/length(n_b);%将所有低灰度求和取平均，作为下一个高灰度中心 d1(i)=abs(c1(i)-c1(i-1);%聚类中心收敛准则 d2(i)=abs(c2(i)-c2(i-1); d3(i)=abs(c3(i)-c3(i-1); if (d1(i)=0&&d2(i)=0&&d3(i)=0) R=c1(i);%最终的聚类中心 G=c2(i); B=c3(i); k=i; break; endendR G Bf

22、or i=1:m*n%判断类别 r=abs(img-R); g=abs(img-G); b=abs(img-B);%计算各像素灰度与聚类中心的距离 r_g=r-g; g_b=g-b; r_b=r-b; n_r=find(r_g<=0&r_b<=0); n_g=find(r_g>0&g_b<=0); n_b=find(g_b>0&r_b>0);img=uint8(img);img(find(r_g<=0&r_b<=0)=uint8(R);img(find(r_g>0&g_b<=0)=uint8(G);img(find(g_b>0&r_b>0)=uint8(B);endsubplot(2,2,3),imshow(img);titl