毕业设计（论文）基于聚类分析的图像分割的研究和应用

《毕业设计（论文）基于聚类分析的图像分割的研究和应用》由会员分享，可在线阅读，更多相关《毕业设计（论文）基于聚类分析的图像分割的研究和应用（34页珍藏版）》请在装配图网上搜索。

1、本科毕业论文 (设计)题 目： 学 院：信息工程学院 专 业：计算机科学与技术 姓 名： 指导教师 2008年6月5日3基于聚类分析的图像分割的研究和应用摘 要聚类分析是数据挖掘的重要研究内容之一，在识别数据的内在结构方面有极其重要的作用。数据挖掘技术是近几年国内迅速开始发展起来的一门新技术,其研究涉及机器学习、神经网络、统计学多个学科领域的知识，其发展对未来社会的各个领域的作用将会越来越大。图像分割是图像分析中的一个基本问题，随着技术的进步,图像使用的越来越多,对图像的分割也越来越引起人们的重视。本文主要是通过数据挖掘中聚类分析算法对图像进行分割。本文首先简要概述了本课题的背景、国内外动态；

2、其次又详细介绍了数据挖掘的基本知识和聚类分析的各种算法；然后具体给出了如何利用聚类分析中的k-means算法在RGB和HSV颜色空间下实现图像分割；最后，通过图像分割系统在遥感中的应用，验证系统的有效性。关键词 数据挖掘 聚类分析 图像分割 k-means HSVThe research and application of image segmentation based on clustering analysisABSTRACTClustering analysis is one of the most important directions of research of data m

3、ining and it plays an important role in the identification of datas intrinsic structure aspect. Data mining is a new technology which has developed rapidly in recent years. Its study involves machine learning, neural network, statistics and many other subjects and its development has been more and m

4、ore significant to every field of the society. Image segmentation is one of the basic problems of image analysis. With the development of technology, the image will be used more widely and image analysis will get more and more peoples closer attention.This paper mainly uses clustering analysis of da

5、ta mining to implement image segmentation. It first briefly outlines the topics background, the domestic and foreign tendencies. Next, it introduces detailed basic acknowledge of data mining and every algorithm of clustering analysis. Then it realizes the function of image segmentation by k-means al

6、gorithm under the colorful space of RGB and HSV. At last, the application of the image segmentation system in remote image will be used to test its validation.KEYWORDS Data Mining Clustering Analysis Image Segmentation K-means HSV目录1前言11.1 研究的目的和意义11.2 国内外研究动态11.3 研究的主要内容和论文结构22.数据挖掘中的聚类分析技术42.1 数据挖

7、掘概述42.1.1 数据挖掘基本概念42.1.2 数据挖掘的分类42.1.3 数据挖掘过程52.1.4 数据挖掘方法62.2 聚类分析算法介绍72.2.1 聚类概念82.2.2 聚类分析算法的类别83.基于K-means聚类算法图像分割系统的设计与实现153.1 图像分割153.2 RGB和HSV颜色空间153.2.1 RGB颜色空间153.2.2 HSV颜色空间163.2.3 RGB与HSV颜色空间比较163.3 图像分割系统的整体设计173.3.1 系统的整体功能模块设计173.3.2系统的整体处理流程设计173.4 图像分割系统的实现183.4.1 系统实现环境183.4.2 各功能模块

8、实现183.2 实验分析224. 遥感图像在图像分割系统的应用234.1 遥感的基本概念234.1.1 遥感的定义234.1.2 遥感的基本原理234.1.3 遥感数据的分类234.2 遥感图像分割244.2.1 遥感图像的RGB颜色空间下图像分割244.2.2 遥感图像的HSV颜色空间下图像分割254.2.3 RGB和HSV颜色空间下图像分割效果比较26总结27谢辞28参考文献291前言1.1 研究的目的和意义聚类分析研究有很长的历史，几十年来，其重要性及其研究方向的交叉特性得到人们的肯定。聚类分析是数据挖掘研究方向的重要研究内容之一，在识别数据的内在结构方面有极其重要的作用。数据挖掘技术是

9、从上个世纪80年代开始发展起来的一门交叉学科,涉及到数据库、统计学、人工只能和机器学习多个领域。计算机的应用普及产生了大量数据，数据挖掘就是利用上述学科的技术进行大量的数据处理。数据挖掘的应用范围非常的广泛，从农业生产的预测到基因分类，从信用卡欺诈到税务稽查，数据挖掘技术对未来社会的各个领域将起到越来越大的作用。图象分割是指将图像分解为各具特性的区域并提取出感兴趣目标的技术和过程，它是图像理解、模式识别和计算机视觉领域中一个十分重要且又十分困难的问题,是计算机视觉技术中首要的关键步骤。图象分割在工业自动化、在线产品检验、生产过程控制、文档图象处理、遥感和生物医学图象分析、图象编码、保安监视,以

10、及军事、体育和农业工程等方面已得到广泛的应用。图象分割是指在一幅彩色图像中分离出主要的色彩一致的区域，随着技术的进步,图像使用的越来越多,对图像的分割也越来越引起人们的重视。据国外专家预测，在今后的510年内，随着数据量的日益积累以及计算机的广泛应用，数据挖掘将在中国形成一个产业。1.2 国内外研究动态1989年8月，在第11届国际人工智能联合会议的专题研讨会上，首次提出“在数据库中的知识发现”(KDD: Knowledge Discovery in Database)技术，1991、1993、1994年又相继举行了KDD专题讨论会。1995年，在美国计算机年会(ACM)上，提出了数据挖掘(D

11、M: Data Mining)的概念，即通过从数据库中抽取隐含的、未知的、具有潜在使用价值信息的过程。由于数据库中的数据被形象地比喻为矿床，因此，数据挖掘一词很快流传开来。由于它应用的普遍性及由此带来的高效益，新型的数据分析技术-数据挖掘成为一个具有广阔应用前景的热门研究方向。KDD的研究吸引了大量的各个领域的专家和研究机构从事该领域的研究。许多公司纷纷推出了自己的数据挖掘系统。我国的数据挖掘研究开始于90年代中期，到90年代中后期，初步形成了知识发现和数据挖掘的基本框架。自90年代中期一批研究成果（学术论文)逐渐发表在计算机学报、计算机研究与发展、软件学报、人工智能与模式识别等刊物上，研究重

12、点也正在从发现方法转向系统应用，并且注重多种发现策略和技术的集成，以及多种学科之间的相互渗透。但是基本上还是以学术研究为主，实际应用上处于起步阶段。目前，国内的许多科研单位和高等院校竞相开展知识发现的基础理论及其应用研究。与国外相比，国内对DMKD的研究稍晚，没有形成整体力量。目前，国内的许多科研单位和高等院校竞相开展知识发现的基础理论及其应用研究，如清华大学、中科院计算技术研究所、空军第三研究所、海军装备论证中心等。北京系统工程研究所对模糊方法在知识发现中的应用进行了较深入的研究，北京大学也在开展对数据立方体代数的研究；华中理工大学、复旦大学、浙江大学、中国科技大学、中科院数学研究所、吉林大

13、学等单位开展了对关联规则开采算法的优化和改造；南京大学、四川联合大学和上海交通大学等单位探讨、研究了非结构化数据的知识发现以及Web数据挖掘；我校数据仓库与数据挖掘课题组在数据仓库与数据挖掘相结合方面的研究取得了较大的进展，目前正积极推进研究成果在金融、统计、商业和制造业领域的应用。因此，国内迫切需要对国外的数据挖掘技术记性剖析，在掌握核心技术的前提下才能真正超越。1.3 研究的主要内容和论文结构本文主要内容就是利用聚类分析中的K-MEANS算法在RGB和HSV颜色空间下实现图像分割系统，并应用于遥感图像，其具体有下面几方面内容：1、 了解数据挖掘的概念，熟悉聚类分析的思想算法，特别掌握k-m

14、eans算法的思想及句体实现。2、 基于数据挖掘聚类分析方法，完成RGB颜色空间下的图像分割系统。3、 研究RGB和HSV颜色空间的转换关系，实现RGB空间到HSV空间转换，从而实现HSV空间下的图像分割。4、 将图像分割系统应用于遥感图像分割，并对分割结果进行分析。按照本文的主要内容，本文的论文结构如下：第一章 ：前言。本章主要简单介绍了本论文的目的和意义、国内外研究动态和研究的主要内容。第二章 ：数据挖掘技术中的聚类分析技术。本章主要介绍了数据挖掘概述和聚类分析各种算法。第三章 ：图像分割系统的实现。本章首先介绍了图像分割系统的概念，然后又具体给出了系统的结构设计和程序流程设计，最后给出了

15、具体结构的各模块设计实现。第四章 ：遥感图像在图像分割系统中的应用。本章主要是将图像分割系统应用到遥感图像的聚类分析中，并在RGB、HSV两种颜色空间下进行图像分割，进行比较、总结。第五章 ：总结。272.数据挖掘中的聚类分析技术2.1 数据挖掘概述2.1.1 数据挖掘基本概念数据挖掘(Data Mining)就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。它是一种新的商业信息处理技术，其主要特点是对商业数据库中的大量业务数据进行抽取、转换、分析和其他模型化处理，从中提取辅助商业决策的关键数据。简而言之，数据

16、挖掘其实是一类深层次的数据分析方法。从这个角度数据挖掘也可以描述为：按企业制定的业务目标，对大量的企业数据进行探索和分析，揭示隐藏的、未知的或验证已知的规律性，并进一步将其模型化的先进有效的方法。2.1.2 数据挖掘的分类数据挖掘设计的科学领域和方法很多，有很多种分类方法。根据挖掘任务，可分为分类或预测模型发现、数据总结、聚类、关联规则发现、序列模型发现、依赖关系或以来模型发现、异常和趋势发现等。下面将具体介绍各种方法。关联分析(association analysis)关联规则挖掘是由Rakesh Apwal等人首先提出的。两个或两个以上变量的取值之间存在某种规律性，就称为关联。数据关联是数

17、据库中存在的一类重要的、可被发现的知识。关联分为简单关联、时序关联和因果关联。关联分析的目的是找出数据库中隐藏的关联网。一般用支持度和可信度两个阀值来度量关联规则的相关性，还不断引入兴趣度、相关性等参数，使得所挖掘的规则更符合需求。 聚类分析(clustering)聚类是把数据按照相似性归纳成若干类别，同一类中的数据彼此相似，不同类中的数据相异。聚类分析可以建立宏观的概念，发现数据的分布模式，以及可能的数据属性之间的相互关系。分类(classification)分类就是找出一个类别的概念描述，它代表了这类数据的整体信息，即该类的内涵描述，并用这种描述来构造模型，一般用规则或决策树模式表示。分类

18、是利用训练数据集通过一定的算法而求得分类规则。分类可被用于规则描述和预测。预测(predication)预测是利用历史数据找出变化规律，建立模型，并由此模型对未来数据的种类及特征进行预测。预测关心的是精度和不确定性，通常用预测方差来度量。时序模式(time-series pattern)时序模式是指通过时间序列搜索出的重复发生概率较高的模式。与回归一样，它也是用己知的数据预测未来的值，但这些数据的区别是变量所处时间的不同。偏差分析(deviation)在偏差中包括很多有用的知识，数据库中的数据存在很多异常情况，发现数据库中数据存在的异常情况是非常重要的。偏差检验的基本方法就是寻找观察结果与参照

19、之间的差别。2.1.3 数据挖掘过程数据挖掘是指一个完整的过程，该过程从大型数据库中挖掘先前未知的、有效的、可实用的信息，并使用这些信息做出决策或丰富知识。数据挖掘的基本过程和主要步骤如图2.1所示：逻辑数据库被选择的数据据预处理后的数据被转换的数据据据被抽取的信息息被同化的知识识选择 善而从 择择择预处理转换挖掘分析和同化图2.1过程中各步骤的大体内容如下：1确定业务对象，清晰地定义出业务问题。认清数据挖掘的目的是数据挖掘的重要一步，挖掘的最后结构不可预测，但要探索的问题应该是有预见的，为了数据挖掘而挖掘则带有盲目性，是不会成功的。2数据准备。(1)数据选择。搜索所有与业务对象有关的内部和外

20、部数据信息，并从中选择出适用于数据挖掘应用的数据。(2)数据预处理。研究数据的质量，进行数据的集成、变换、归约、压缩等为进一步的分析作准备，并确定将要进行的挖掘操作的类型。(3)数据转换。将数据转换成一个分析模型，这个分析模型是针对挖掘算法建立的这是数据挖掘成功的关键。3数据挖掘。对所得到的经过转换的数据进行挖掘。除了完善和选择合适的挖掘算法外，其余一切工作都能自动地完成。4结果分析。解释并评估结果。其使用的分析方法一般应视挖掘操作而定，通常会用到可视化技术。5知识同化。将分析所得到的知识集成到业务信息系统的组织结构中去。2.1.4 数据挖掘方法神经网络方法神经网络由于本身良好的自组织自适应性

21、、并行处理、分布存储和高度容错等特性非常适合解决数据挖掘的问题，因此近年来越来越受到人们的关注。典型的神经网络模型主要分3大类：以感知机、BP反向传播模型、函数型网络为代表的，用于分类、预测和模式识别的前馈式神经网络模型；以Hopfield的离散模型和连续模型为代表的，分别用于联想记忆和优化计算的反馈式神经网络模型；以ART模型、Koholon模型为代表的，用于聚类的自组织映射方法。神经网络方法的缺点是黑箱性，人们难以理解网络的学习和决策过程。本文用到了Kohonen自组织神经网络，具体将在后面讲述。遗传算法遗传算法是一种基于生物自然选择与遗传机理的随机搜索算法，是一种仿生全局优化方法。遗传算

22、法具有的隐含并行性、易于和其它模型结合等性质使得它在数据挖掘中被加以应用。决策树方法决策树是一种常用于预测模型的算法，它通过将大量数据有目的分类，从中找到一些有价值的，潜在的信息。它的主要优点是描述简单，分类速度快，特别适合大规模的数据处理。粗集方法粗集理论是一种研究不精确、不确定知识的数学工具。粗集方法有几个优点：不需要给出额外信息；简化输入信息的表达空间；算法简单，易于操作。粗集处理的对象是类似二维关系表的信息表。覆盖正例排斥反例方法它是利用覆盖所有正例、排斥所有反例的思想来寻找规则。首先在正例集合中任选一个种子，到反例集合中逐个比较。与字段取值构成的选择子相容则舍去，相反则保留。按此思想

23、循环所有正例种子，将得到正例的规则(选择子的合取式)。统计分析方法在数据库字段项之间存在两种关系：函数关系(能用函数公式表示的确定性关系)和相关关系(不能用函数公式表示，但仍是相关确定性关系)，对它们的分析可采用统计学方法，即利用统计学原理对数据库中的信息进行分析。可进行常用统计(求大量数据中的最大值、最小值、总和、平均值等)、回归分析(用回归方程来表示变量间的数量关系)、相关分析(用相关系数来度量变量间的相关程度)、差异分析(从样本统计量的值得出差异来确定总体参数之间是否存在差异)等。模糊集方法即利用模糊集合理论对实际问题进行模糊评判、模糊决策、模糊模式识别和模糊聚类分析。系统的复杂性越高，

24、模糊性越强，一般模糊集合理论是用隶属度来刻画模糊事物的亦此亦彼性的。有人在传统模糊理论和概率统计的基础上，提出了定性定量不确定性转换模型云模型，并形成了云理论。2.2 聚类分析算法介绍聚类分析研究有很长的历史，几十年来，其重要性及与其他研究方向的交叉特性得到人们的肯定。聚类是数据挖掘、模式识别等研究方向的重要研究内容之一，在识别数据的内在结构方面具有极其重要的作用，聚类主要应用于模式识别中的语音识别、字符识别等，机器学习中的聚类算法应用于图像分割和机器视觉，图像处理中聚类用于数据压缩和信息检索，聚类的另一个主要应用是数据挖掘(多关系数据挖掘)、时空数据库应用(GIS等)、序列和异类数据分析等，

25、此外，聚类还应用于统计科学，值得一提的是，聚类分析对生物学、心理学、考古学、地质学、地理学以及市场营销等研究也都有重要作用。2.2.1 聚类概念迄今为止，聚类还没有一个学术界公认的定义，这里给出 EverittIs 在1974年关于聚类所下的定义：一个类簇内的实体是相似的，不同类簇的实体是不相似的；一个类簇是测试空间中点的会聚，同一类簇的任意两个点间的距离小于不同类簇的任意两个点间的距离；类簇可以描述为一个包含密度相对较高的点集的多维空间中的连通区域，它们借助包含密度相对较低的点集的区域与其他区域(类簇)相分离。聚类过程：1) 数据准备：包括特征标准化和降维，2) 特征选择：从最初的特征中选择

26、最有效的特征，并将其存储于向量中，3) 特征提取：通过对所选择的特征进行转换形成新的突出特征，4) 聚类(或分组)：首先选择合适特征类型的某种距离函数(或构造新的距离函数)进行接近程度的度量；5) 聚类结果评估：是指对聚类结果进行评估，评估主要有3种：外部有效性评估、内部有效性评估和相关性测试评估。2.2.2 聚类分析算法的类别没有任何一种聚类技术(聚类算法)可以普遍适用于揭示各种多维数据集所呈现出来的多种多样的结构，根据数据在聚类中的积聚规则以及应用这些规则的方法，有多种聚类算法。聚类算法有多种分类方法，聚类算法可以分为以下几大类：分割聚类方法(Partitioning Method)、层次

27、聚类方法(Hierarchical Method)、基于密度(Density-Based)的聚类方法、基于网格(Grid-Based)的聚类方法、基于模型(Model-Based)的聚类方法等等。1基于划分的方法:所谓基于划分的方法(Partitioning Method)是指给定一个包含n个数据对象的数据集，以及要生成的簇的数目K，采用一个划分准则（称为相似度函数）将数据对象组织为K个划分(kCanvas-Pixelsxy & 0x0000ff; G = (pBitmap-Canvas-Pixelsxy & 0x00ff00) 8; /“与”操作后并右移8位 B = (pBitmap-Can

28、vas-Pixelsxy & 0xff0000) 16;3.4.2.2 空间转换模块本模块的主要功能是实现颜色空间RGB和HSV的相互转换，其算法实现如下：(1) RGB 转换成 HSVmax=maximum of RGBmin=minimum of RGBV=maxS=(max-min)/maxIf S=0, H is underfined,Else delta=max-minIf R=max, H=(G-b)/delta;If G=max, H=2+(B-R)/deltaIf B=max,H=4+(R-G)/deltaH=H*60If H0, H=H+360(2) HSV转换成 RGBIf

29、 S=0 and H=underfined,R=G=B=VIf H=360, H=0H=H/60I=floor(H)F=H-1P=V*(1-S)q=V*(1-(s*f)t=V*(1-(S*(1-f)If i=0, R=v, G=t, B=pIf i=1, R=q, G=v, B=pIf i=2, R=p, G=v, B=tIf i=3, R=p, G=q, B=vIf i=4, R=t, G=p, B=vIf i=5, R=v, G=p, B=qwhere floor() is the C floor function.3.4.2.3 聚类分析模块在本模块中，主要用K-means算法实现聚类分

30、析，其算法描述如下：1、算法策略：首先随机地选择k个对象，每个对象代表了一个簇的平均值或中心。对剩余的每个对象，根据其与各个簇中心的距离，将它放入最近的簇，然后重新计算每个簇的平均值。这个过程不断重复，直到准则函数收敛。通常，采用平方误差准则函数，其定义如下：E是数据集中所有对象的平方误差的总和，p是空间中的点，表示给定的数据对象，m是簇Ci的平均值（p和mi都是多维的）。2、算法描述输入：簇的数目上和包含n个对象的数据库。输出：K个簇，使平方误差准则最小。方法：1) 任意选择k个对象作为初始的簇中心；2) Repeat；3) 根据簇中对象的平均值，将每个对象重新赋给最类似的簇；4) 更新簇的

31、平均值，即计算每个簇中对象的平均值；5) Until各簇的中心点不再发生变化；3、算法评述(1)时间复杂度，其中,n是所有对象的数目,k是簇的数目,t是迭代的次数。通常,kn,且tCanvas-Pixelsxy=R+(G8)+(BCanvas-Draw(0,0,pBitmap)来实现显示图片，从而实现本模块的功能。3.2 实验分析为了初步确定此系统的图像分割效果，本节将演示对一幅.bmp格式的图片进行图像分割的效果。原图如图3.4所示： 图3.4 原图在RGB颜色空间下进行图像分割，在输入的K值不同的情况下，其效果如下： 图3.5 分割后K=4 图3.6 分割后K=5 图3.7 分割后K=6在

32、HSV颜色空间下进行图像分割，其效果随K值变化情况如下： 图3.9 分割后K=4 图3.10 分割后K=5 图3.11 分割后K=6由上可以看出，此系统可以根据K值的不同，按照要求进行图像分割。显而易见的是，图像分割的效果，与选取的K值有很大关系。K值太小，会使某些颜色不能分辨出来，从视觉来看，与实际图像差别很大；而K值太大，又会影响效果，当大到一定程序，分割的效果也不会有多大的变化，因此，选取合适的K值很重要，这也是此算法一个很大的缺点。4. 遥感图像在图像分割系统的应用4.1 遥感的基本概念4.1.1 遥感的定义遥感(remote sensing)是20世纪60年代发展起来的对地观测综合性

33、技术。简单地理解就是“遥远的感知”。遥感是应用探测仪器，不与探测目标相接触，从远处把目标的电磁波特性记录下来，通过分析，揭示出物体的特征性质及其变化的综合性探测技术。遥感技术的发展，揭开了人类从外层空间观测地球、探索宇宙空间的序幕，为我们认识国土、开发资源、研究环境、分析全球变化找到了新的途径。遥感数字图像处理是计算机数字图像处理技术与遥感图像分析技术结合而形成的一门新兴科学。遥感数字图像处理技术的出现，从根本上改变了传统遥感图像的处理方式与识别方式，为遥感技术系统的完善，实现对地物高效、快速识别以及多源信息的数字化融合处理创造了良好的条件。4.1.2 遥感的基本原理遥感图像数据反映的是成像区

34、域内地物的电磁波辐射能力，有明确的物理意义，而地物反射和发射电磁波能量的能力又直接与地物本身的属性和状态有关，因此遥感图像数据值的大小及其变化主要是由地物的类型及变化所引起的。遥感的基本原理就是通过对遥感图像数据的大小和变化规律的分析处理来有效地识别和研究地物类型。遥感数字图像处理作为遥感图像处理的一种重要手段，是利用计算机通过数字处理的方法来增强和提取遥感图像中的专业信息。4.1.3 遥感数据的分类遥感影像分类根据是否需要先验知识可分为监督分类和非监督分类。监督分类:首先需要从研究区域选取有代表性的训练场地作为样本;根据已知训练区提供的样本，通过选择特征参数(如像元灰度值、方差等)，建立判别

35、函数，据此对样本像元进行分类，依据样本类别的特征来识别非样本像元的归属类别。非监督分类:是在没有先验类别(训练场地)作为样本的条件下，即事先不知道类别特征，主要根据像元间相似度的大小进行归类合并。遥感图像的无监督分类，通过聚类分析抽取特征，在对研究对象没有任何先验知识的情况下，充分利用遥感影像地物光谱特征的分布规律，可以提供对于待研究图像一个总体的、概况性的描述，具有操作简便、快速和有利于计算机进行自动识别的优点。长期以来受到人们的重视，结合实地调查与样本分析，得到了广泛的应用。K-means算法是对遥感图像在没有先验知识情况下进行无监督分类的重要算法之一，在遥感影像的分析中有着广泛的应用。4.2 遥感图像分割在遥感图像分割应用中，我们选取了东营地区的一幅30米分辨率的遥感图像，从图像中截取了2个不同部分，如图4.1、图4.2，分别在RGB和HSV颜色空间下对三幅图像进行分割，并对结果进行分析。4.2.1 遥感图像的RGB颜色空间下图像分割本文选取了2幅.bmp格式的图片，如图4.1、图4.2所示，其中图4.2更有规律，图4.1 内像素的聚集较杂乱无章。 图4.1 遥感图一 图4.2遥感图二将图4.1 中的图片，分别在K=4, 5, 6的情况下