K均值算法图像分割

K均值算法图像分割 () 题 目 基于特征的图像分割技术 学生姓名 万亚堃 学 号 20111334044 学 院 电子与信息工程学院 专 业 通信工程 指导教师 胡昭华老师 二,一五年四月五日 1 目 录 1.绪论...............................................................................................错误～未定义书签。 1.1 课题研究意义 ........................................................................错误～未定义书签。 1.2图像分割技术发展概况 ..............................................................错误～未定义书签。 1.3 图像分割方法的现状 .................................................................错误～未定义书签。 1.4论文内容 ....................................................................................错误～未定义书签。 2.基于综合特征的图像分割 .............................................................错误～未定义书签。 2.1概述............................................................................................错误～未定义书签。 2.2颜色空间选取 .............................................................................错误～未定义书签。 2.3图像特征提取 .............................................................................错误～未定义书签。 2.3.1颜色特征提取.......................................................................错误～未定义书签。 2.3.2纹理特征提取.......................................................................错误～未定义书签。 2.4综合特征分割 .............................................................................错误～未定义书签。 3.K均值算法 ....................................................................................错误～未定义书签。 3.1原始K均值算法 .........................................................................错误～未定义书签。 3.2K均值聚类分割算法 ....................................................................错误～未定义书签。 3.2.1 聚类 ..................................................................................错误～未定义书签。 3.2.2 K-均值聚类算法的工作原理:...........................................错误～未定义书签。 3.2.3 K-means聚类算法的一般步骤: .......................................错误～未定义书签。 3.2.4 K-均值聚类法的缺点:......................................................错误～未定义书签。 3.3(基于灰度空间的彩色图像像素聚类 .........................................错误～未定义书签。 3.4改进的k-均值聚类图像分割算法................................................错误～未定义书签。 3.5分割结果及分析 .........................................................................错误～未定义书签。 4.本文结论 .......................................................................................错误～未定义书签。 4.1存在的问题以及对未来的展望 ...................................................错误～未定义书签。 参考文献 ..........................................................................................错误～未定义书签。 致 谢 ............................................................................................错误～未定义书签。 附一:K-均值聚类改进前的matlab源程序 ......................................错误～未定义书签。 2 基于特征的图像分割技术 万亚堃 南京信息工程大学电子与信息工程学院，江苏 南京 210044 摘 要:图像分割是指将一副图像分解为若干互不交叠的有意义且具有相同属性的区域。图像分割是数字图像处理中的一项关键技术～其分割的准确性直接影响后续任务的有效性～因此具有十分重要的意义。现有的分割算法在不同程度上取得了一定的成功～但是图像分割的很多问题还远远没有解决～该方面的研究仍然面临很多挑战。 本文采用改进的K均值算法进行图像分割～在颜色空间选取上也采用比较好的RBG颜色空间～对图像分别进行了颜色特征提取与纹理特征提取～最后进行了原始K均值算法与改进后的K均值算法分割图形的比较～实验结果 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 明本文提出的方法可以很好的从图像中分割出有意义的区域～更突出目标区域。 关键词:图像分割～颜色空间～K均值聚类。 Based on the characteristics of the image segmentation technology Wanyakun 3 NUIST，Nanjing 210044，China Abstract,Image segmentation is a pair of images are decomposed into several mutually overlapping area of meaningful and with the same attribute. Image segmentation is a key technology of digital image processing，The segmentation accuracy directly affect the effectiveness of the subsequent task, So it is of vital significance. Existing segmentation algorithm in different degree, has achieved some success, but is far from solved many problems of image segmentation, the research still faces many challenges. Image segmentation is one of the most basic and important field in image processing, is to visual image analysis and pattern recognition is the basic premise. Proposed in this paper USES the improved k-means algorithm for image segmentation, on the selection of color space is better HUV based on color space (by linear RBG color space transformation). Image feature and color feature extraction of texture feature extraction respectively, finally has carried on the original k-means algorithm and the improved k-means algorithm segmentation graphical comparison of the experimental results show that the proposed approach can be very good meaningful regions segmented from the image. Keywords: Image segmentation, color space, k-means clustering. 1.绪论 1.1 课题研究意义 图像分割是数字图像处理中的一项关键技术，它通常用于对图像进行分析、识别、编码等处理之前的预处理环节，其分割的准确性直接影响后续任务的有效性，因此具有十分重要的意义。自上世纪70年代以来，已经出现了多种图像分割方法，而每一种图像分割方法 4 都是为了解决一些特定的应用问题。该技术成功地应用于许多领域，例如:交通路口的电子警察、光学字符识别(OCR)、指纹识别、机动车牌号识别等等。 图像分割是指将一副图像分解为若干互不交叠的有意义且具有相同属性的区域。好的图像分割应具备的特性:?分割出来的各区域对某种性质如灰度、纹理而言具有相似性，区域内部比较平整;?相邻区域对分割所依据的性质有明显的差异;?区域边界上是明确和规整的。 大多数图像分割方法只是部分满足上述特征。如果强调分割区域的同性质约束，则分割区域很容易产生大量小孔和不规则边缘;若强调不同区域间性质差异的显著性，则易造成不 同区域的合并。具体处理时，不同的图像分割方法总是在各种约束条件之间寻找一种合理的平衡。 虽然图像分割方法已经有了很大的发展，但由于它的复杂性，仍有很多问题没有很好地得到解决。因此，人们至今还一直在努力发展新的、更有潜力的分割算法，以期实现更通用、更完美的分割结果。实践表明，对图像分割理论与技术的进一步研究仍然具有非常重要的意义。 本文首先对数字图像分割的一些经典分割方法作了概述，然后分析了现有项目开发中使用的图像分割方法所存在的问题，最后基于经典算法进行技术改进，实现了一种新的分割方 法，并将其应用到实验当中，取得了良好的效果。 1.2图像分割技术发展概况 利用计算机进行图像处理有两个目的:一是产生出更适合人观察和识别的图像，二是希望能够由计算机自动识别和理解图像。无论为了哪种目的，关键的一步就是能够对包含有大量、各式各样景物信息的图像进行分解，分解的最终结果是一些具有某种特征的最小成分即图像的基元。图像的特征指图像中可用作标志的属性。它可分为图像统计特征和图像的视觉特征两类。图像的视觉特征是一些人为特征，需通过变换才能得到，如图像的直方图。图像的视觉特征指人的视觉可直接感受到的自然特征，如区域的亮度、纹理或轮廓等等。上述将图像分解成具有不同特殊单元的过程就是图像的分割，由此可以看出，图像分割是实现图像分析的重要步骤。 图像分割是图像分析的初始步骤之一，也是图像处理最原始的问题，几乎自数字图像处理问世不久，人们就开始了图像分割技术的研究，并取得了相当的进展和成功。但由于它的复杂性，有许多问题没有很好地解决，因此人们至今还一直在努力发展新的、更有潜力的 分 割算法，以期实现更通用、更完美的分割结果。图像分割是计算机图像处理的一个基本问题，是许多后续图像分析任务的第一步处理，特别是对于图像识别、图像的可视化和基于目标的图像压缩都高度依赖于分割结果。图像分割是由图像处理进到图像分析的关键步 5 骤，也是一种基本的计算机视觉技术，这是因为图像的分割、目标的分离、特征的提取和参数的测量将原始的图像转化为更抽象、更紧凑的形式，使得更高层的分析和理解成为可能。通常，分割问题包括将给定图像中相似的块分割成一个区，相邻的分割结果是不相似的。从另一个角度 说，分割也可以被认为是像素的标记处理，属于同一区域的像素被标上相同的号。一直以来，人们致力于分割方法的研究，提出了很多分割方法。但是，图像分割仍然是图像处理中 的一 个瓶颈。实际上，图像分割就是把图像中的目标分成许多感兴趣的区域与图像中各种物体目标相对应。目前可能的理解图像方法只限于信息中部分特征，如:灰度差别、局部纹理差别、 彩色差别、局部统计特征或局部区域的频谱特征的差别等成熟技术表征的特征。既然我们只能用图像信息中某些部分特征去分割区域，因此各种分割方法必然带有局限性。迄今为止，还没有一种图像分割方法适用于所有的图像。 图像分割的实质是要正确地划分属性空间，使得具有相同属性的像素归属于同一区域，不同属性的像素归属不同的区域。 图像分割方法的研究始于上世纪 50 年代，研究己有几十年的历史，借助各种理论 至今已提出了上千种各种类型的分割算法，而且这方面的研究仍在积极进行中。经典的 图像分割方法分为以下几种: 、阈值分割技术 1 阈值分割技术是经典的、流行的图像分割方法之一，也是最简单的一种图像分割方法，这种方法的关键在于寻找适当的灰度阈值。常用的方法有最大类间方差法、最小误差法、最大熵法等。这些方法都是基于一维灰度直方图，而且对整幅图像使用一个固定全局阈值，如果图像中有阴影或光照不均等，分割效果会受到影响。为此，提出了用二维直方图或者动态阈值等技术进行分割，但同时计算复杂度会增加。阈值分割技术它仅适用于高反差的简单图像的分割，不能满足灰度渐变或以某种纹理而不是灰度来表征不同区域的那些复杂图像的分割。 2、区域技术 区域技术通过对目标像素的直接检测来实现分割。区域生长法是一种常用的区域技术。区域增长是:先从每个需要分割的目标中找一个种子像素作为生长的起点，然后将其周围的像素按照某种相似性 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 (如灰度相似性)与之对比，如果满足标准则合并到种子像素的集合内，将新合并的像素作为新的种子像素继续向外扩展，直到找不到满足条件的像素为止。这种方法能够同时利用图像的多种性质进行分割，但是由于它采用串行机制，计算时间较长，实时性较差。 3、边缘检测技术 图像分割能够通过检测不同区域的边缘来获得。在目标的边缘处常常有灰度的急剧变 6 化，借助各种空域微分算子，如梯度算子，方向算子，拉普拉斯算子和马尔算子等，能够检测出图像中具有边缘特性的像素点。在此基础上，采用边界闭合技术把边缘像素连接起来组成目标区域的封闭边界，从而达到分割的目的。但边界检测是一项困难的工作，因为通常图像的边界都很难找到。 随着数学工具，成像设备和计算机技术的发展，图像分割方法呈现出新的特点和趋势: (1)多种新兴数学工具的加入，使得新的方法不断涌现。人工神经网络，小波理论和遗传算法是加世纪 90 年代兴起的新型理论工具，人们将其应用到图像分割中，起到了改善分割效果，扩展适用范围以及提高运算速度等作用。 (2)成像设备和技术的发展使得应用对象的范围大大扩展。现在采集的图像种类与以往相比有了较大的变化和发展，不仅仅局限于常见的两维静止灰度图像，还有各种3 维图像，彩色图像，运动图像等等。这些发展对图像分割方法提出了更高的 要求 对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗 。 (3)多特征的利用和多方法的融合。图像分割方法要取得更好的效果，不能局限于单一特征的分析，而要综合利用多种信息。图像分割是一个复杂的过程，需要融合多种方法的优势进行。 1.3 图像分割方法的现状 从上世纪五十年代开始，学者一直热衷于研究图像分割技术。迄今为止，已提出上千种 图像分割算法，依这些算法对图像处理的特点，主要可分为以下几类方法。 (1)阈值分割法 阈值分割法作为一种常见的区域并行技术，它通过设置阀值，把像素点按灰度级分若干类，从而实现图像分割。由于是直接利用图像的灰度特性，因此计算方便简明、实用性强。显然，阈值分割方法的关键和难点是如何取得一个合适的阈值，而实际应用中阈值设定易受噪声和光亮度影响。近年来关于阈值分割法主要有:最大相关性原则选择阈值法、基于图像拓扑稳定状态法、灰度共生矩阵法、熵法、峰值和谷值分析法等。其中，自适应阈值法、最大熵法、模糊阈值法、类间阈值法是对传统阈值法改进较成功的几种算法。更多的情况下，阈值的选择会综合运用两种或两种以上的方法，这也是图像分割发展的一个趋势。例如，将图像的灰度直方图看作是高斯分布的选择法与自适应定向正交投影高斯分解法的结合，较好地拟合了直方图的多峰特性，从而得到了更为准确的分割效果。阈值法的缺陷主要在于它仅仅考虑了图像的灰度信息，而忽略了图像的空间信息。对于非此即彼的简单图像处理(如一些二值图像的处理)是有效的，但是对于图像中不存在明显的灰度差异或各物体的灰度值范围有较大重叠的图像分割问题则难以得到准确的分割效果。 (2)基于边缘的图像分割法 边缘总是以强度突变的形式出现，可以定义为图像局部特征的不连续性，如灰度的突变、纹理结构的突变等。边缘常常意味着一个区域的终结和另一个区域的开始，图像的边缘包含 了物体形状的重要信息，它不仅在分析图像时大幅度地减少了要处理的信息量，还保护了 7 目标的边界结构。对于边缘的检测常常借助空间微分算子进行，通过将其模板与图像卷积完成。 两个具有不同灰度值的相邻区域之间总存在灰度边缘，而这正是灰度值不连续的结果，这种不连续可以利用求一阶和二阶导数检测到。 当今的局部技术边缘检测方法中，主要有一次微分(Sobel算子、Roberts算子)、二次微分(拉普拉斯算子等)和模板操作(Prewitt算子、Kirsch算子和Robinson算子)等。这些边缘检测器对边缘灰度值过渡比较尖锐且噪声较小等不太复杂的图像可以取得较好的效果，但对于边缘复杂(如边缘模糊、边缘丢失、边缘不连续等)的图像效果不太理想。此外，噪声的存在使基于导数的边缘检测方法效果明显降低，在噪声较大的情况下所用的边缘检测算子通常都是先对图像进行适当的平滑，抑制噪声，然后求导数,或者对图像进行局部拟合，然后再用拟合光滑函数的导数来代替直接的数值导数，如Marr算子、Canny算子等。有关学者曾给出了一种基于彩色边缘的图像分割方法，这是对传统边缘分割方法只适用于灰度图像状况的一个突破。 在未来的研究中，用于提取初始边缘点的自适应阈值选取、用于图像层次分割的更大区域的选取，以及如何确认重要边缘去除假边缘将变得非常重要。 (3) 基于聚类的分割法 对灰度图像和彩色图像中相似灰度或色度合并的方法称之为聚类，通过聚类将图像表示为不同区域即所谓的聚类分割方法。此方法的实质是将图像分割问题转化为模式识别的聚 类分析，如k均值、参数密度估计、非参数密度估计等方法都能用于图像分割。常用的聚类分割有颜色聚类分、灰度聚类分割和像素空间聚类分割。颜色聚类分割实际上是将相似的几种颜色合并为一色，描述颜色近似程度的指标是色差，在标准CIE匀色空间中，色差是用两个颜色的距离来表示的。但是显示器采用的RGB空间是显示器的设备空间，与CIE系统的真实三原色不同，为简单起见，一般采用RGB色空间中的距离来表示。 灰度聚类分割就是只把图像分成目标和背景两类，而且仅考虑像素的灰度，这就是一个 在一维空间中把数据分成两类的问题。通过在灰度空间完成聚类，得到两个聚类中心(用灰度值表征)，聚类中心连线的中点便是阈值。显然这个概念也可以轻松地延扩至多阈值和动 态阈值的情况。 像素空间聚类分割在某些特定的尺度上观察图像，比如说把图像信号通过一个带通滤波 器，滤波的结果将使图像的局部信息更好地被表达。通过一个多尺度分解，轮廓信息可以在大尺度图像上保留下来，细节或者突变信息可以在中小尺度上体现，基于多尺度图像特征聚类的分割方法渐渐得到了人们的关注。 (3) 函数优化法 8 基于函数优化的分割方法是图像分割中另一大类常用的方法，其基本思路是给出一个目标函数，通过该目标函数的极大化或极小化来分割图像，G.A.Hewer等人提出了一个具有广 泛意义的目标函数。统计学分割法、结合区域与边缘信息法、最小描述长度(MDL)法、基于贝叶斯公式的分割法等是目前几种活跃的函数优化法。 统计学分割法就是把图像中各个像素点的灰度值看作是具有一定概率分布的随机变量，且观察到的实际物体是作了某种变换并加入噪声的结果。统计学分割方法包括基于马尔科夫随机场法(MRF)、标号法(Labeling)和混合分布法(Mixture)等。 结合区域与边缘信息法是基于区域信息的图像分割的主要方法。区域增长有两种方式:一种是先将图像分割成很多一致性较强的小区域，再按一定的规则将小区域融合成大区域， 达到分割图像的目的;另一种是事先给定图像中要分割目标的一个种子区域，再在种子区域基础上将周围的像素点以一定的规则加入其中，最终达到目标与背景分离的目的。分裂合并法对图像的分割是按区域生长法沿相反方向进行的，无需设置种子点，其基本思想是给定相似测度和同质测度，从整幅图像开始，如果区域不满足同质测度，则分裂成任意大小的不重叠子区域;如果两个邻域的子区域满足相似测度则合并。 最小长度描述法(MDL)的基本思路是用一种计算机语言来描述图像的区域和边界信息，得到一个描述长度函数，以此作为目标函数，根据图像极小化描述长度从而得到分割结果。MDL准则主要应用于区域竞争中，即通过这种规则对比若干个种子区域，找出其中的 坏种子。它常常与其他方法结合使用。 1.4论文内容 本文通过大量阅读图像分割技术方面的文献，认真研究K均值算法，并对其中的一些算法提出了改进优化了K均值算法。算法流程为颜色空间选取--图像特征提取(颜色特征提取和纹理特征提取)--综合特征分割--分割结果及分析。 文章内容安排如下: (1)第一章:主要阐述课题研究意义，图像分割技术发展概况，图像分割方法的现状，论文的主要内容。 (2)第二章:主要阐述技术基于综合特征的图像分割的流程颜色空间的选取(比较HSV颜色空间与RGB颜色空间，最后选择了RGB颜色空间--图像特征的提取(分别进行颜色特征提取和纹理特征提取)--综合特征分割(先用原始的K均值算法，然后再使用改进后的K均值算法，对两者进行比较，K均值算法的流程为初始聚类--K均值迭代--后处理)--分割结果及其分析(对原始K均值算法与改进后的K均值算法所分割出来的图像进行对比，发现区别得出结论)。 (3)第三章:存在的问题以及对未来的展望。 9 2.基于综合特征的图像分割 2.1概述 目前彩色图像的分割方法大多仅用颜色特征或纹理特征，难以满足基于内容检索应用的 需要。例如目前很有代表性的VisualSEEK系统仅仅采用颜色特征用于分割，很容易对高纹理区域产生过分割，而一些仅用纹理分割的算法又没有充分利用颜色所携带的丰富信息，可能产生欠分割，不管是只使用颜色特征进行的分割，还是只是用纹理特征进行的分割在对图像进行分割的时候都会产生不好的影响，因此有效地融合颜色和纹理信息是获得稳健的图像分割的重要途径。目前，这方面的分割方法的研究相对较少。针对这个问题，该文提出了一种利用图像的颜色和纹理综合特征进行分割的方法。 图像分割方法有很多种，其中，聚类法是一个较简单有效的综合特征分割方法，已被广泛应用到图像分割领域。典型的聚类方法有K均值法、ISODATA法、模糊C均值法等。ISODATA法有六个参数必须由用户提供，较难实现，且不能做到自动分割;模糊C均值法是对特征集的模糊划分，这种方法主要用于三维图像和医疗图像的分割;而K均值法通过改进可以做到一定程度的自动分割，而且适合于分割普通图像，在处理大量数据集方面也具有其它聚类算法无法比拟的优势，但是，K均值法的缺点在于需要具有聚类数目及聚类中心的先验知识，聚类结果往往与初始聚类个数和聚类中心的选定有关，聚类只考虑图像点的特征相近性，未考虑点的位置邻近性。因此该文采用了改进的K均值算法来进行图像分割。改进后的方法能克服以上缺陷，分割出有意义的区域。 2.2颜色空间选取 由于HSV颜色空间在视觉上比RGB颜色空间更均匀，即HSV的空间距离比RGB的空间距离更加符合人眼视觉特征，因此目前有许多图像分割算法采用了HSV空间。但是，从RGB到HSV的转换是个非线性变换，H和S都有不可避免的奇异点，即在转换公式中出现分母为零的情况。在奇异点附近即使R、G、B的值有很小变化也引起变换值有很大的跳动，这样会产生不稳定，因此不宜用于区域分割算法中。 从这点说，由R、G、B经线性变换法得到的彩色坐标系更为可取，替代非线性的色调和饱和度变换的方法是采用三滤波器值的线性变换。文章采用了YUV空间，YUV空间是由RGB空间经过线性变换得到的。RGB空间到YUV空间的转换公式为: YR0.2990.1440.587，，，，，， ,,,,,,UG,0.1690.500,0.332= ,,,,,, ,,,,,,V0.55,0.081B,0.419，，，，，， 认知科学表明，YUV是一种独立于设备的彩色空间，它按照人类的感知程度以一致的尺 10 度表示色彩差别，而且，该文经过实验发现，采用YUV空间产生的分割结果比HSV空间的分割结果更好。 2.3图像特征提取 2.3.1颜色特征提取 采用4*4的图像块为图像分割的最小单位，因此，特征提取的最小单位也是4*4的图像块。对于小块的颜色特征，直接采用小块里的各个像素的Y、U、V的颜色均值。设小块的16个点从上至下，从左至右标号为1，2，3,4,5,6,7,8,9,10,11,12,13，14，15，16，该小块的颜色特征(Y、U、V)计算公式为: 16161611Y=，U=， YiUiV,Vi,,,1616i,1i,1,i1 2.3.2纹理特征提取 由于小波变换能提取图像的高频信息，因此，它非常适合于提取图像的纹理特征。考虑到计算的简洁性和效率，该文选择了哈尔小波。小波变换的对象是各个4*4的图像块。一次小波变换后，一个4*4的块分解成四个频带，低频带LL及三个高频带HL、LH、HH，每个频带包含4个系数，见图1。 (a) 原始图像 LL HL LH HH 11 (b)小波变换 图1小波变换示意图 提取三个高频带的小波能量作为纹理特征。以HL频带为例，假设其对应的小波系数为 {}该频带对应的纹理特征量计算如下: ,,,cccck,lk,l，1k，1,lk，1,l，1 1112(3) f,(,,c，，kl1,14,,i0j0 从HH和LH频带计算另两个纹理特征量，计算公式类似式(3)，即求该频带的小波系数 的二阶矩的均值。 2.4综合特征分割 将颜色特征的三维向量和纹理特征的三维向量组合成一个六维向量，利用这种综合特征向量来分割图像，以达到预期的图像分割效果。 3.K均值算法 3.1原始K均值算法 K均值聚类法可以用来进行综合特征的分割，下面是原始均值算法的伪代码。 原始K均值算法的伪代码如下: function Direct-k-means( ) ,,j,,,,...,)初始化K个模板(使{1,2，???，k}， wiwwwwjl123k l,{1,2，???，n} 对应于模板聚类 cwjj Repeat ,其中l, for 每个输入向量{1,2，???,n} il do 加入最近的聚类,对应的模板为 将 icwljj ,,,,j, (即符合{1,2，???，k}) iwiwljlj ,j, for 每个聚类{1,2，???，k} cj 12 do 按照目前中的所有样本来更新模板: cwjj il ,,wji,lcjcj k2 E,,计算误差函数: ,,iwljj,1,iclj Until不改变或者聚类成员不再改变。从以上步骤可以看出，最终的聚类依赖于初始聚 类中心及聚类数目K值的选择。很多情况下要得到图像的先验知识是不可能的，因此，K均值聚类算法中，类别数目的确定是个难点，数目过多会产生过分割(分割得过细)，过少又会导致欠分割(有的区域未分割出来)。我们提出了一种改进的K均值方法来分割图像，使得这些参数可以通过图像的统计信息确定相应的初始值，而无需用户进行事先的指定，然后再根据K均值迭代对聚类个数和模板初值进行不断的调整，直到聚类个数和模板初值不再变化为止，而且，通过加入后处理，兼顾了聚类时点的位置连通关系。 3.2K均值聚类分割算法 3.2.1 聚类 将物理或抽象对象的集合分成由类似的对象组成的多个类的过程被称为聚类。由聚类所生成的簇是一组数据对象的集合，这些对象与同一个簇中的对象彼此相似，与其他簇中的对象相异。聚类分析又称群分析，它是研究(样品或指标)分类问题的一种统计分析方法。聚类分析计算方法主要有如下几种:划分方法，层次方法，基于密度的方法，基于网格的方法，基于模型的方法。 K-均值聚类算法是著名的划分聚类分割方法。划分方法的基本思想是:给定一个有N个元组或者纪录的数据集，分裂法将构造K个分组，每一个分组就代表一个聚类，K 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 都较前一次好，而所谓好的标准就是:同一分组中的记录越近越好，而不同分组中的纪录越远越好。 3.2.2 K-均值聚类算法的工作原理: K-means算法的工作原理:算法首先随机从数据集中选取 K个点作为初始聚类中心，然后计算各个样本到聚类中的距离，把样本归到离它最近的那个聚类中心所在的类。计算新形成的每一个聚类的数据对象的平均值来得到新的聚类中心，如果相邻两次的聚类中心没有任何变化，说明样本调整结束，聚类准则函数 已经收敛。本算法的一个特点是在每次迭代中都要考察每个样本的分类是否正确。若不正确，就要调整，在全部样本调整完后，再修改 13 聚类中心，进入下一次迭代。这个过程将不断重复直到满足某个终止条件，终止条件可以是以下任何一个: (1)没有对象被重新分配给不同的聚类。 (2)聚类中心再发生变化。 (3)误差平方和局部最小。 3.2.3 K-means聚类算法的一般步骤: 处理流程: (1) 从 n个数据对象任意选择 k 个对象作为初始聚类中心; (2) 循环(3)到(4)直到每个聚类不再发生变化为止; (3) 根据每个聚类对象的均值(中心对象)，计算每个对象与这些中心对象的距离;并根据最小距离重新对相应对象进行划分; (4) 重新计算每个(有变化)聚类的均值(中心对象)，直到聚类中心不再变化。这种划分使得下式最小 2k Exm,,,,ijjx,,1,ij 3.2.4 K-均值聚类法的缺点: 缺点: )在 K-means 算法中 K 是事先给定的，这个 K 值的选定是非常难以估计的。 (1 (2)在 K-means 算法中，首先需要根据初始聚类中心来确定一个初始划分，然后对初始划分进行优化。 (3) K-means算法需要不断地进行样本分类调整 不断地计算调整后的新的聚类中心 因此当数据量非常大时 算法的时间开销是非常大的。 (4)K-means算法对一些离散点和初始k值敏感，不同的距离初始值对同样的数据样本可能得到不同的结果。 3.3(基于灰度空间的彩色图像像素聚类 1(读取彩色图像，将RGB值转化为灰度值 2. 利用k均值聚类对像素的灰度值进行划分，提取特征点(本方法采用误差平方和准则函数判断聚类是否合理)。 3.利用matlab编程实现结果如下: 随即地取c1(1)=25; c2(1)=125; c3(1)=200;%选择三个初始聚类中心 14 图1 得到最终聚类中心的灰度值如下: R =109.5763 G =158.0943 B =212.8034 随机选取聚类中心的K-均值聚类结果: 图2 3.4改进的k-均值聚类图像分割算法 4.1 K-均值聚类算法中重要的一步是初始聚类中心的选取，一般是随机选取待聚类样 15 本集的K个样本，聚类的性能与初始聚类中心的选取有关，聚类的结果与样本的位置有极大的相关性。一旦这 K个样本选取不合理，将会增加运算的复杂程度，误导聚类过程，得到不合理的聚类结果。通过粗糙集理论提供 K-均值聚类所需要的初始类的个数和均值，提高了聚类的效率和分类的精度。 于粗糙集理论的灰度空间划分 1.粗糙集的研究对象是由一个多值属性集合描述的对象集合。主要思想是在保持分类能力不变的情况下，通过知识约简，导出问题的决策和分类规则[4]。粗糙集理论能很好地近似分类。从图像的直方图可以看出图形一般呈谷峰状分布，同一区域内像素的灰度值比较接近，而且不同区域内像素数大小不等。若灰度值相差不大的像素可归为一类，则可将图像分为几类。为此，定义像素的灰度值差为条件属性，等价关系R定义为:如果两个像素灰度值差小于定间距D，则两个像素是相关的，属于等价类。 首先确定间距D，通过原图可求出灰度值分布范围，根据灰度值范围可求出灰度级数L。将灰度级范围内对应像素个数最多的灰度值定义为中心点P。计算L个中心点之两两间距，若最小距离小于间距D，则将相应中心点合并，并将两点的算术平均值作为该中心点的值。重复进行直到所有中心点的两两间距均大于间距D。中心点的个数和数值就是K_均值聚类所需要的初始类的个数和均值。 ()i，其中为第 i次迭代后赋给类j的像素集合, 2.像素的灰度值为xp(0,1,,255),？Qpj 为第 j类的均值。 ,j 具体步骤如下: (1)(2)()l? 将粗糙集理论提供的L个中心点P作为初始类均值 ,,,。 ？,,,12l i? 在第次迭代时，考察每个像素，计算它与每个灰度级的均值之间的间距，即它与聚类中心的距离 D，将每个像素赋均值距其最近的类，即 ()()iiDxDxjl,,,,,,min,(1,2,)？ (3.6) ,,plpj ()i则。 xQ,pj (1)i，,,1/Nxjl,1,2,？N?对于,计算新的聚类中心，更新类均值:，式中，,jjpj()ixQ,j ()iQ是中的像素个数。 j (1)()ii，jK,1,2,？,,,?将所有像素逐个考察，如果，有 ，则算法收敛，结束;jj 否则返回?继续下一次迭代。 ? 以上聚类过程结束后，为了增强显示效果，分割结果各像素以聚类中心灰度值作为该类最终灰度 16 由原图像的灰度直方图，本文将定间距D设为32，灰度级L的个数为8。原灰度图 的灰度值范围为[0，255]，被分成8个灰度级，七个灰度级对应中心点P为{32，64，96， 128，160，192，224，256}。计算这12个中心点之两两间距，若最小距离小于间距20， 则将相应中心点合并，并将两点的算术平均值作为该中心点的值，处理后结果P{32,160， 192} 下面将c1(1)=32;c2(1)=160;c3(1)=192;作为初始聚类中心，编程进行聚类分析。得到结果如下: 图3 图3与图2相比分类结果更好，图像分割效果更明显，更能表现图像特征。边缘更加清晰，分割结果既突出了目标，又保留了细节信息，达到了较好的分割效果。因此，基于粗糙集的K_均值聚类算法可以有效地对灰度图像进行分割，从分割后的图像中可获取更多的目标信息，为进一步的图像分析和理解提供了良好的基础。 继续对多幅图像用上述两种方法进行K-均值聚类分割，得到如下对比图像: 17 图4 K-均值聚类得到的: 图5 根据改进的K-均值算法得到的: 18 图6 原始图像: 图7 K-均值聚类得到的: 19 图8 根据改进的K-均值算法得到的: 20 图七 3.5分割结果及分析 原始的 K 均值分割方法容易产生过分割，应该合并的区域没有合并，导致这些区域不能组成独立的物体而且原始 K 均值方法也容易产生欠分割，原因是采用的聚类没有考虑各点的位置关系，会产生不相邻的点被归到一个区域，导致区域不连通，通常不连通的区域不能对应一个独立 的物体，影响了后面的检索。改进后的 K 均值算法能分割出普通图像的目标区域，例如， 由于有相似的纹理和颜色、花朵、花叶、黑马、白马、草原、大海、草坪、树等独立完整的有意义的区域可以被分割出来。 试验表明，基于粗糙集理论和K-均值聚类算法的图像分割方法，比随机选取聚类的中心点和个数减少了运算量，提高了分类精度和准确性，而且对于低对比度、多层次变化背景的图像的形状特征提取具有轮廓清晰、算法运行速度快等特点，是一种有效的灰度图像分割算法。 4.本文结论 4.1存在的问题以及对未来的展望 虽然近年来研究成果越来越多,但由于图像分割本身所具有的难度,使研究没有大的突破性的进展.仍然存在的问题主要有两个:其一是没有一种普遍使用的分割算法;其二是没有一个好的通用的分割评价标准. 从图像分割研究的历史来看,可以看到对图像分割的研究有几个明显的趋势:一是对原有算法的不断改进;二是新方法、新概念的引入和多种方法的有效综合运用.人们逐渐认识到现有的任何一种单独的图像分割算法都难以对一般图像取得令人满意的分割效果,因而很多人在把新方法和新概念不断的引入图像分割领域的同时,也更加重视把各种方法综合起来运用.在新出现的分割方法中,基于小波变换的图像分割方法就是一种很好的方法.三是交互式分割研究的深入.由于很多场合需要对目标图像进行边分割分析,例如对医学图像的分析,因 此需要进行交互式分割研究.事实证明,交互式分割技术有着广泛的应用.四是对特殊图像分割的研究越来越得到重视.目前有很多针对立体图像、彩色图像、多光谱图像以及多视场图像分割的研究,也有对运动图像及视频图像中目标分割的研究,还有对深度图像、纹理(Texture)图像、计算机断层扫描(CT)、磁共振图像、共聚焦激光扫描显微镜图像、合成孔雷达图像等特殊图像的分割技术的研究.五是对图像分割评价的研究和对评价系数的研究越来越得到关注.相信随着研究的不断深入,存在的问题会很快得到圆满的解决. 21 参考文献 1.樊昀，王润生，面向内容检索的彩色图像分割[J],计算机研究与发展，2002;39(3) 2.黄健元,模糊 ISODATA 聚类分析方法的改进[J],南京航空航天大学学报，2000;32(2) 3.耿伯英，杨静宇,基于多分辨率分析及 QFCM 算法的图像分割方法研究[J],计算机研究与发展，2000;37(8) 4.张旭丽,两种基于空间域聚类分析的彩色图像分割方法比较[J],贵州工业大学学报(自然版)，2001;30(2) 5.曹莉华,用颜色特征进行基于形状的检索[J],计算机工程与应用，1999;,35(12):22-24 6.叶桦，章国宝，陈维南,基于小波变换的纹理图像分割[J],东南大学学报，1999;29(1) 7.K Alsabti，S Ranka，V Singh，An Efficient K-Means Clustering Algorithm。,1997 8.田玉敏，乃学尚，高有行等,基于整数小波系数的纹理图像检索方法研究[J]西安电子科技大学学报，2003;30(1):90-93 9.曹莉华，柳伟，李国辉,基于多种主色调的图像检索算法研究与实现[J]计算机研究与发展，1999;36(1):96-100 吴军辉,徐立鸿. 彩色图像分割方法综述[J ]. 中国图象图形学报, 2005, 10 (1) :1- 10. 10.开颜, 11.滕升华. 黑白影像的彩色化研究[D ]. 北京:中国科学院电子学研究所, 2006. 12.章毓晋(图像分割[M](北京:科学出版社，200l 13.蔡煦，朱波，曾广周(一种彩色多级闯值的图像分割方法及在形状特征提取方面的应用[J](山东大学学报(工学版)，2002，32(4):333,336 14.吴国雄，陈武凡(图像的模糊增强与聚类分割[J](小型微型计算机系统，1994，15(11):21,26 15.童星.王命延一种基于粗糙集的图像边缘检测方法[期刊论文]-计算机与现代化 2009(10) 16.黄长专.王彪.杨忠图像分割方法研究[期刊论文]-计算机技术与发展 2009(6) 17.周萍. 改进的图像分割遗传K?均值聚类算法[ J] . 海军工程大学学报, 2009, 6, 21( 3) : 75-78. 18.张忠林, 曹志宇, 李元韬. 基于加权欧式距离的K?means 算法研究[ J] . 郑州大学学报: 工学版, 2010, 31( 1) : 89-92. 22 致 谢 时光如白驹过隙，转瞬即释。四年的大学生活临近了尾声。这短短四年的学习时间，使我终生受益并为将来的人生旅程准备一些经验和教训，是我的人生中弥足珍贵的四年。论文的顺利完成，离不开各位老师、同学和朋友的关心和帮助。 在这里感谢我的导师:胡邵华老师。论文是在他的悉心指导下完成的。导师渊博的专业知识，严谨的治学态度，精益求精的工作作风，诲人不倦的高尚师德，严以律己、宽以待人的崇高风范，朴实无华、平易近人的人格魅力对我影响深远。不仅使我树立了远大的学术目标、掌握了基本的研究方法，还使我明白了许多待人接物与为人处世的道理。本论文从选题到完成，每一步都是在导师的指导下完成的，倾注了导师大量的心血。 感谢我的同学朋友们，从遥远的家来到这个陌生的城市里，是他们和我共同维系着彼此之间深厚的感情，没有他们的帮助和支持是没有办法完成我的学位论文的，同窗之间的友谊永远长存。我们在一起的日子，我会记一辈子的。 感谢我的爸爸妈妈，焉得谖草，言树之背，养育之恩，无以回报，你们永远健康快乐是我最大的心愿。 23 在论文即将完成之际，我的心情无法平静，从开始进入课题到论文的顺利完成，有多 少可敬的师长、同学、朋友给了我无言的帮助，在这里请接受我诚挚的谢意～在此表示深 深的感谢。 附一:K-均值聚类改进前的matlab源程序 [RGB,map]= imread ('F:\a2.jpg'); %读入 imshow(RGB);title(' 图一 原图像') img=rgb2gray(RGB); [m,n]=size(img); figure subplot(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-c1(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的大小改变此处条件，寻找最小的聚类中心 24 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);%将所有低灰度求和取平均，作为下一个低灰度中心 c2(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; end end R G B for i=1:200%判断类别 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); end subplot(2,2,3),imshow(img);title(' 图三 聚类后的图像') subplot(2,2,4),imhist(img);title(' 图四 聚类后的灰度图像直方图') (2)根据不同的K值编程主要思路如下: for i=1:m*n c1(1)=25;c2(1)=125;c3(1)=200; c4(4)=245; %选择K个初始聚类中心 r=abs(img-c1(i));g=abs(img-c2(i)); b=abs(img-c3(i));s=abs(img-c4(i)); %计算各像素灰 25 度与聚类中心的距离 n_r=find(r-g<=0&r-b<=0&r-s<=0);%寻找聚类中心 n_g=find(r-g>=0&g-b<=0&g-s<=0); n_b=find(g-b>0&r-b>0&b-s<=0); n_s=find(s-r<=0&s-g<=0&s-b<=0); i=i+1;%更新聚类中心 c1(i)=sum(img(n_r))/length(n_r);%将所有低灰度求和取平均，作为下一个低灰度中 心 c2(i)=sum(img(n_g))/length(n_g); c3(i)=sum(img(n_b))/length(n_b); c4(i)=sum(img(n_s))/length(n_s); d1(i)=abs(c1(i)-c1(i-1));%聚类中心收敛准则 d2(i)=abs(c2(i)-c2(i-1)); d3(i)=abs(c3(i)-c3(i-1)); d4(i)=abs(c4(i)-c4(i-1)); if (dk(i)==0) end; 附二:K-均值聚类改进后的matlab源程序 RGB= imread ('F:\a.jpg'); %读入像 img=rgb2gray(RGB); [m,n]=size(img); subplot(2,2,1),imshow(img);title(' 图一 原图灰度图像') subplot(2,2,2),imhist(img);title(' 图二 原图像的灰度直方图') hold off; img=double(img); for i=1:200 c1(1)=25; c2(1)=125; c3(1)=200;%选择三个初始聚类中心 r=abs(img-c1(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);%寻找最小的聚类中心 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);%将所有低灰度求和取平均，作为下一个低灰度中心 c2(i)=sum(img(n_g))/length(n_g);%将所有低灰度求和取平均，作为下一个中间灰度中 26 心 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.001&&d2(i)<=0.001&&d3(i)<=0.001 R=c1(i); G=c2(i); B=c3(i); k=i; break; end end R G B img=uint8(img); img(find(imgR&imgG))=255; subplot(2,2,3),imshow(img);title(' 图三 聚类后的灰度图像') subplot(2,2,4),imhist(img);title(' 图四 聚类后的灰度图像直方图') 27