毕业论文（设计）基于聚类分析的图像分割算法.docx
《毕业论文（设计）基于聚类分析的图像分割算法.docx》由会员分享，可在线阅读，更多相关《毕业论文（设计）基于聚类分析的图像分割算法.docx（37页珍藏版）》请在冰点文库上搜索。
摘 要
图像分割是将一副图像分为若干个互不重叠的区域，有相同的属性和意义。
图像分割作为图像处理的一个重要环节，普遍用于医学、军事、交通等各计算机视觉范畴，是目前最热门的研究课题之一。
其分割的准确性直接决定后续图像分析的质量，因而至关重要。
目前人们已经提出了很多处理方法，也取得了一些成就，但由于其本身有些复杂，很多问题还远远没有解决。
本文主要介绍基于聚类分析的图像分割算法，具体说明了K均值聚类算法的具体原理及算法过程，并经过实验对其分析和研究。
在此基础上完成了基于
K均值聚类算法的彩色图像分割实验和医学影像实验，验证了K均值聚类算法用于图像分割的适用性。
关键词：
图像分割；聚类分析；K均值聚类算法；彩色图像；医学影像
Abstract
Imagesegmentationistodecomposeanimageintoanumberofregionsthataremeaningfulandhavethesameattributesthatdonotoverlapeachother.Asanimportantpartofimageprocessing,imagesegmentationiswidelyusedinmedical,military,transportationandothercomputervisionfieldandisoneofthemostpopularresearchtopics.Theaccuracyofitssegmentationdirectlydeterminesthequalityofthesubsequentimageanalysis,soitisofgreatsignificance.Atpresent,peoplehaveputforwardalotofsolutionsthatgotsuccessinsomedegree,butbecauseofitscomplex,manyproblemsarefarfrombeingresolved.
Thispapermainlyintroducestheimagesegmentationalgorithmbasedonclusteringanalysis.TheprincipleofK-meansclusteringalgorithmaredescribedindetail.Andistestedonartificialdataexperiment..Andthen,thecolorimagesegmentationexperimentandthemedicalimageexperimentbasedontheK-meansclusteringalgorithmareanalyzed.
Key words：
Image segmentation,；clustering analysis；K-means clusteringalgorithm；colorimage；medicalimage
III
目 录
摘 要 I
Abstract II
目 录 III
第一章绪论 1
1.1研究背景及意义 1
1.1.1图像分割概述 1
1.1.2常用的图像分割方法 2
1.2主要研究内容与工作安排 4
第二章聚类分析及分割图像 5
2.1聚类分析概述 5
2.2聚类分析方法 6
2.2.1划分聚类算法 6
2.2.2层次聚类算法 6
2.2.3密度聚类算法 6
2.2.4模型聚类算法 7
2.3分割图像介绍 8
2.3.1灰度图像 8
2.3.2彩色图像 9
2.3.3纹理图像 12
2.3.4遥感图像 12
第三章基于K均值聚类算法的图像分割 14
3.1.K均值聚类算法原理 14
3.2K均值聚类算法流程 15
3.3K均值聚类算法仿真实验 17
第四章实验结果及分析 19
4.1K均值聚类算法分割彩色图像 19
4.1.1彩色图像实验 19
4.1.2实验结果与分析 20
4.2K均值聚类算法分割医学影像 21
4.2.1医学影像介绍 21
4.2.2医学影像实验结果与分析 22
4.3本章小结 25
第五章总结 26
参考文献 28
致 谢 30
附 录 31
第一章绪论
1.1研究背景及意义
随着全球范围内计算机水平的不断提高，数字图像处理和分析逐渐独当一面，形成了各自的研究领域。
尽管时间不长，但新方法不断产生，引起研究人员的研究兴趣。
众所周知，视觉是人们赖以生存的感觉，而图像又是视觉的根源，因此数字图像成为计算机学、生理学、心理学等科学领域研究不可或缺的工具，图像处理也在遥感、气象、军事等重要领域内发挥重要作用。
图像分割[1]是把图像分成若干个满足不同需求的区域，从图像处理到图像分析、从图像识别到计算机预先处理，都不能缺少。
由计算机自动分割时，仅有的依据是图像中像素的亮度及颜色，就会遇到许多难点，如光照不均匀、受噪声干扰、图像不清晰以及出现阴影等，导致常发生分割错误。
图像分割需要继续改进，引入一些新知识和人工智能方法，来纠正分割中可能会出现的错误，使问题变得更复杂。
因此，我们要致力于快速有效地将需要的部分分离出来，由下文来着重介绍。
1.1.1图像分割概述
图像分割[2]是为更好地分析图像而将图像划分为若干个特定的区域的技术，定义如下：
集合R代表整个图像区域，分割R图像是将R分成N个满足以下
条件的非空子集R1,R2,R3,…,RN
设集合S是完整的图像，分割S就像把S分为若干个非空子集S1,S2,K,Sn，满足以下条件：
0
n
（1）åSi=S；
i=1
（2）对所有的i和j，i¹
j有SiÇSj=Æ；
（3）对i=1,2,3,K,n，有P（Si）=true；
（4）对i¹
j，有P（SiÈSj）=
false；
（5）对i=1,2,3,K,n，Si是连通的区域。
其中：
P（Si）是集合Si内所含元素的性质，Æ是空集。
对以上几个条件的解释如下：
（1）完备性：
分割后的所有区域合并起来必须包括原图像中的所有部分；
（2）独立性：
分割后的N个子区域互相独立，无交集；
（3）相似性：
每个子集中的元素有一种相似特性，与其他子集区别开；
（4）互斥性：
各子集间无共有的特性，属性不同；
（5）连通性：
同一子区域内，像素之间互通。
实际应用中，我们需要将图像划分为背景和不同的目标，若划分满足以上条件，Ri（i=1,2,3,…,n）就称为R的分割。
1.1.2常用的图像分割方法
当前可用的图像分割方法主要为：
基于阈值的分割方法[3]、基于边缘的分割方法[4]、基于区域的分割方法[5]以及基于聚类的分割方法[6]。
1）基于阈值的图像分割
阈值分割法的原理是用一个或多个阈值作为分类依据，将图像的灰度级进行区分，分在同一类中的像素目标相同，从而来区别物体和背景。
具体步骤：
先确定合适的阈值，再将像素的灰度值跟阈值进行比较，最后进行分类。
阈值分割法非常依赖阈值的选择，因此关键在于选择正确的阈值。
此算法的优点是简单有效，计算代价小，速度快，尤其是图像的灰度区别大时，效果较好；缺点是有局限性，图像的空间特性和纹理等实用信息被去除，只考虑像素本身的取值，对噪声很敏感，有时分割效果不大好。
现已有许多阈值分割改进算法，尤其针对阈值的选择，如最大熵法、基于图像统计阈值法、最小误差法、二维熵阈值法、改进的Otsu法等。
2）基于边缘的图像分割
区域分割法的原理是将相同或相似性质的像素连起来得到新图像，优点是用像素的相似性和空间的邻接性，除去孤立噪声的干扰，深入至像素级，得到的结果较为准确。
基于区域的分割方法主要分为区域生长和分裂合并。
区域生长法是先在每个区域内找一个种子像素，再将邻域中与种子像素相似的像素点合并到种子像素所在的集合。
循环往复，直至没有像素可以被合并，算法停止。
重要因素是种子像素、生长准则和终止条件。
优点是计算速度快、
32
复杂度低；缺点是在事先不知道具体情况，只能随机选择种子点和相似性准则，分割结果出错的可能性大大增加。
分裂合并法是先不停地将整个图像分成多个子区域，再将相邻的具有相似性的区域合在一起。
优点是不含种子点，省去很多步骤；缺点是若达不到深像素级，分割精度就不高，若达到深像素级，合并的工作量增大，时间复杂度提升。
分水岭算法也是基于区域的图像分割算法之一。
原理是洼地积水：
先求梯度图，再把它看做一个地形图，较平坦地带梯度的值较小，构成盆地；边界地带梯度的值较大，构成山脊。
水从盆地最低洼处流入，水位不断上涨，为了防止洼地相连，必须在山脊上建水坝。
当水位不断涨高时，水坝也越筑越高，直至达到最高山脊，算法完成，每一个独立的积水盆地为一个分割区域。
优点是稳定性强，缺点是易分割过度。
3）基于区域的图像分割
经常会用的是基于空域的梯度算子，梯度算子是用图像空域的差分求导。
一般用于灰度图像，利用不同图像灰度不同、边界处有明显边缘的特点分割图像。
通常基于边缘的分割方法指的是基于灰度值的边缘检测，在边缘灰度值会显现出阶跃型或屋顶型变化。
阶跃状边缘对应的是一阶导数的极值点和二阶导数的过零点（零交叉点），于是会用微分算子进行边缘检测。
一阶微分算子有Roberts算子、Prewitt算子和Sobel算子，二阶微分算子有Laplace算子和Kirsh算子等。
微分算子的优点是对边缘灰度值相差较大、噪声较小等简单的图像，效果较好；缺点是若有噪声，没有边界的地方会出现边缘，有边界的地方却不能出现边缘。
1.2主要研究内容与工作安排
本文主要介绍图像分割、聚类分析和基于K均值聚类分析的图像分割算法原理和算法过程，再做基于K均值聚类算法的彩色图像分割实验和医学图像分割实验，验证K均值聚类算法的适用性。
本文的章节结构安排如下：
第一章绪论主要介绍了本文研究的背景及意义，归纳了图像分割的概念、方法，同时介绍了本论文的主要研究内容与工作安排。
第二章详细介绍聚类分析的定义、流程、当前的经典算法，再介绍这几种经典算法的原理、实现的方法、优缺点比较等。
第三章 详细介绍基于K均值聚类算法的图像分割，具体阐述K均值聚类算法的思想、具体流程以及优缺点，通过仿真实验来分析。
第四章做基于K均值聚类算法的彩色图像分割实验和医学图像分割实验，验证K均值聚类算法的适用性。
第五章总结全文，提出展望。
总结全文主要叙述的内容和实验的结果分析，并指出在实验中的不足，对于下一步工作进行展望。
第二章聚类分析及分割图像
2.1聚类分析概述
聚类是指将将物理或抽象的集合分到不同的类或者簇的过程，同一簇中的对象相似性大，而不同簇间的对象相异性大。
聚类分析不必事先给出一个分类的标准，而是从样本数据出发自动分类，使用不同的方法[7]。
聚类方法的特点如下：
1、简单、直观；2、聚类结果可以出现多个解，研究者经过判断和分析进行选择；3、与实际真实存在的类别数无关，总能分成几类；4.结果与选择的聚类变量息息相关，添或删一些变量很可能得到不同的解；
5、研究者在使用时应特别注意各个影响因素；6.需要事先对异常值和特殊的变量做标准化处理。
聚类分析流程图如下：
聚类分析
对象表示
的集合
聚类
对象间相似性度量
对象选择
聚类评估
反馈控制 反馈控制
图2.1聚类分析流程图
2.2聚类分析方法
2.2.1划分聚类算法
假定集合中有N个像素，人为将这N个像素划分成K个组，表示K个聚类。
每个组都必须满足不为空，每个记录必须只在一组。
不断迭代，改动组中的数，使相似的记录归于同一个组，不太相似的记录归于不同的组。
经典的划分聚类算法有：
K-means[8]：
采用距离作为评价的相似性标准，对象的间距越小，相似度越
大，距离近的对象组成簇，最后得到的簇紧挨在一起且相互独立。
K-medoids：
采用绝对差值和
SAD（SumofAbsoluteDifferences）来衡量聚类结果的优劣，是K-means的一种改进。
PAM（PartitioningAroundMedoids）：
把中心点作为划分依据，每换一个
中心点，算出的SAD值越小，说明聚类效果越好，反复迭代直至找到最好的划
分。
2.2.2层次聚类算法
层次聚类算法[9]是将数据对象想象成一棵聚类的树，根据树的方向从上至下或从下至上完成聚类。
从上至下是分裂式的层次聚类，从全部开始，不断将属于不同聚类的数分裂出去，直到满足某个条件算法结束；从下至上是聚合式的层次聚类，将每个数都作为一个初始中心，通过一定方法判断相似的簇，并将其合并成一个簇，不断重复，直到不再合并。
2.2.3密度聚类算法
将数据分布的密度作为评判的标准，把密度相似的样本聚在一起。
鉴于聚类不需要提前知道数据的分布情况，所以优点是能发现数据中类的形状。
经典的密度聚类方法[10]有DBSCAN：
用空间索引来搜数据的邻域，把核心数作为起点，把对象组成一个簇，满足密度可达，簇的数量由算法自动确定。
但低密度区的点容易被忽略，因此DBSCAN不是一种完整的聚类方法。
2.2.4模型聚类算法
处理数据时有效地利用某些数学模型，将数据和模型并在一起，主要分成统计学法和神经网络法[11]。
基于统计学的聚类算法主要有：
COBWeb的基础是机器学习，需要将处理的数据形成分类模式再进行分类，同时说明了每组数的特点，使每组对象能够代表一个类或者概念；AutoClass的基础是概率混合模型，说明聚类的目标是属性的分布概率。
优点是能处理混合型数据，前提是各属性相互独立。
基于神经网络的聚类算法主要有：
自组织神经网络SOM的基础是生理学和脑科学，属于无监督的学习，适用于数据聚类。
聚类算法总结：
近年来研究聚类在科学领域十分热门，因为以上的聚类都有各自的不足之处，所以很多学者都想要改进现有的聚类方法，或是提出一种
新的聚类方法。
以下是简单的总结：
1、k-means方法在进行聚类之前需要人们事先确定聚类数目[12]，而实操时聚类的数目并不能提前知晓，往往要用实验来判断合适的聚类数目，才能保证聚类结果较好。
2、传统的聚类方法只能适用于某种情况下，如BIRCH方法[13]只适用于球状簇，对于没有规则的聚类，效果不好；虽然孤立点并不怎么和K-medoids法有关，但计算代价大。
因此有学者提出综合以上聚类，获得最优化结果。
3、有文献提到了基于最小生成树的聚类算法[14]，原理是逐渐丢弃最长边来获得结果。
将某个阈值设置成边界点，超过阈值的边不需要算而可以直接删掉，从而使计算效率升高，使计算成本下降。
4、当前许多方法处理小型数据和低维数据的功能较好，但当数的规模增大、维度提高时，功能就不如之前，如k-medoids法，而实操时数据又大都属于大规模高维度。
有文献提到在高维空间挖掘映射聚类PCKA[15]，它删掉了没有关系的维度，从多个维度中选了离得近的维度并沿着它分类，以此将高维数据聚在一起。
5、当前许多算法都只处于理论假设之下，如聚类能很好地被分开，没有突出的孤立点等，但现实数据通常很复杂，噪声很大，因此如何有效消除噪声影响、提高处理现实数据的能力，成为我们将要攻克的难题。
2.3分割图像介绍
2.3.1灰度图像
灰度图[16]是指黑白间按对数分为256色阶的图。
每幅图由红、绿、蓝三个通道组成，不同的灰度色阶表示红、绿、蓝在图像中所占的比例。
在计算机中，灰度图像的每个像素只有一个采样颜色，往往从最暗的黑到最亮的白。
黑白图像只有黑和白两种颜色，而灰度图像在黑和白中间还有很多级的颜色深度。
灰度可以通过以下几种方法来转化：
1、浮点算法[17]：
Gray=R´0.30+G´0.59+B´0.11
2、整数方法[18]：
Gray=（R´30+G´59+B´11）/100
3、移位方法[19]：
Gray=（R´76+G´151+B´28）?
8
4、平均值法[20]：
Gray=（R+B+G）/3
5、仅取绿色：
Gray=G
（2-1）
（2-2）
（2-3）
（2-4）
（2-5）
用上述方法求出灰度，将原来的红、绿、蓝全部用灰度替代，形成新的颜色。
灰度直方图是一种函数，指标是灰度级，当取不同灰度值的面积或像素数时，可以看到图像中的比例，是基本信息之一。
灰度直方图灰度级的分布表示图像所含的许多特点，为分析图像给出有力的凭证。
比如：
若直方图上很窄的区域内有密集的点，证明对比度很低；若直方图上有两个峰值，证明原图中很有可能有两种区域，只是亮度不同。
如下图所示，即使用Matlab对一幅彩色图像进行灰度处理以及呈现出的灰度直方图：
3500
3000
2500
2000
1500
1000
0
500
0 50 100 150 200 250 300
（a）（b）
图2.4.1（a）灰度图像;（b）灰度直方图
2.3.2彩色图像
彩色图像的每个像素由R、G、B分量构成，其中R、G、B由不同的灰度级描述，分割思想与灰度图像大体一致。
但比起灰度图像，彩色图像能给我们更多丰富的信息，颜色空间的表达方式也五花八门。
所以在实操中，先适当转化彩色图像的各个分量，变为灰度图像，再用对应的分割算法进行分割。
RGB三原色到灰度的转换公式：
Gray=0.30´R+0.59´G+0.11´B
（2-6）
如下图所示，即使用Matlab对一幅彩色图像提取RGB分量后所呈现出的效果图：
（a）（b）
（c） （d）
图2.4.2（a）原图像;（b）红色分量图;（c）绿色分量图;（d）蓝色分量图
如上图所示，是彩色图像的RGB分量图，（a）图像是原始图像，（b）图像是提取红色分量后产生的图像，（c）图像是是提取绿色分量后产生的图像，（d）图像是提取蓝色分量后产生的图像。
通过图像我们可以看到，与原始图像相比，（b）
（c）（d）三幅图像都呈现出了不同的颜色效果，因此我们可得，一幅彩色图像就是由不同的RGB分量叠加组成的。
我们常用的色彩空间除了RGB以外，还有Lab、CMYK等，本文采用的就是将彩色图像从RGB转换到Lab彩色空间。
Lab色彩空间没有RGB颜色空间用得多，它基于1931年国际照明委员会
（CIE）定的颜色度量国际标准。
1976年，经改后被正式定名为CIELab[21]。
它是一种基于生理上的特征且与设备没有关系的颜色系统，用数字化来传递人的视觉感应。
Lab颜色空间中的L分量表示像素的亮度，取值范围是[0,100]，表示从纯黑到纯白；a表示从洋红色（通道里的白色）至深绿色（通道里的黑色）的范围，取值范围是[127,-128]；b表示从焦黄色（通道里的白色）至袅蓝色
（通道里的黑色）的范围，取值范围是[127,-128]。
a、b通道也会没有颜色，当50%中性灰色时，离灰色越近，颜色越少，颜色还没有亮度。
RGB转Lab色彩空间原理：
RGB无法直接转化成LAB，需要先转化成XYZ再换为LAB，即：
RGB—
—XYZ——LAB。
因此转换公式分两部分：
（1）RGB转XYZ
设r,g,b为像素三个通道，取值范围在[0,255]，转换公式如下：
ï
ìR=gamma（
ï
r ）
255.0
g
ïR=gamma（ ）
í
ï
ï
ïR=gamma（
î
255.0
b ）
255.0
（2-7）
ì（x+0.055）2.4，（x>0.04045）
í
gamma（x）=ï
1.055
x
ï
ï，（其它）
î12.92
（2-8）
éXù éRù
ê ú êú
êYú=M×êGú
其中M分别取
êëZúû
êëBúû （2-9）
0.4124、0.3576、0.1805、0.2126、0.7152、0.0722、0.0193、0.1192、0.9505。
等同于如下公式：
X=var_R´0.4124+var_G´0.3576+var_B´0.1805
Y=var_R´0.2126+var_G´0.7152+var_B´0.0722
Z=var_R´0.0193+var_G´0.1192+var_B´0.9505
（2）XYZ转LAB
（2-10）
n
L*=116f（Y/Y）-16
a*=500[f（X/X
n）-f（Y/Yn）]
n n
b*=200[f（Y/Y）-f（Z/Z）]
（2-11）
ìt1/3
í
f（t）=ï
ïï 2+
129 4
（ ）t
î36 29
ift>（6）3
29
otherwise
（2-12）
上面两个公式中，L*，，a*
；
b*是式（2.11）算出的值,代表LAB色彩空间三个通道
X，Y，Z是RGB转XYZ后计算出来的值；
Xn，Yn，Zn一般定为95.047，100.0，108.833。
2.3.3纹理图像
纹理反映出图像中的同质，是物体表层结构组织排列的平缓或周期性变化,会出现某种局部序列性不断重复、排列非随机、区域内大致均匀的特点，展现为像素及其周围空间邻域的灰度分布[21]。
纹理特征可以分为以下四种类型：
（1）统计型纹理特征：
基于像素和邻域内的灰度属性直接从图像域提取纹理特征，以GLCM（灰度共生矩阵）为主，搭建在图像的条件概率密度上。
（2）模型型纹理特征：
基于某种参数的分布模型方式直接从图像域提取纹理特征，以参数为特征进行图像分割，核心问题是参数的估计，提取方法以随机场方法和分形方法为主。
（3）信号处理型纹理特征：
主要用某种线性变换、
升级会员 