基于最小生成树的图像分割方法研究

1、 目 录摘 要.I Abstract.III 第一章 绪论 (11.1课题研究的背景和意义 (11.2国内外研究现状 (21.2.1 边界检测和边缘连接 (21.2.2 基于区域的分割 (31.2.3 结合特定理论工具的分割技术 (41.3本文的主要工作及创新点 (71.4本文的组织 (7第二章 基于图论的图像分割方法 (92.1基本理论概念 (92.1.1 图的分割 (92.1.2 图像的分割 (112.1.3 彩色空间分割 (132.2三种基于图论的图像分割方法 (142.2.1 Ratio Cut 分割法 (142.2.2 Normalized Cut方法 (152.2.3 Isoper

2、imetric Ratio 方法 (162.3最小生成树分割方法 (182.3.1 最小生成树概念 (182.3.2 构造最小生成树 (192.4本章小结 (21第三章 基于数学形态学分水岭算法 (223.1形态学图像处理 (223.1.1 基本概念 (223.1.2 灰度图像中的基本操作 (233.1.3 灰度级形态学的应用 (243.2分水岭算法 (253.2.1 分水岭概念 (253.2.2 分水岭分割二值图像 (263.2.3 分水岭分割梯度图像 (273.2.4 控制分水岭过分割方法 (283.3本章小结 (30第四章 基于分水岭的最小生成树图像分割方法 (314.1图像预处理 (3

3、14.1.1 颜色空间变换 (314.1.2 求取梯度图像 (32方法 (344.2基于分水岭的最小生成树图像分割方法K VW4.2.1 方法背景 (344.2.2 Vincent分水岭算法 (344.2.3 最小生成树合并区域 (37方法 (424.2.4 K VW4.3实验分析 (444.4本章小结 (46第五章 总结与展望 (4775.1已完成的工作 (475.2进一步的研究工作 (47参考文献 (49致 谢 (52攻读硕士学位期间发表的论文和参与的项目 (53基于最小生成树的图像分割方法研究摘 要图像处理广泛应用在医学图像、遥感云图、指纹识别、人脸检测、地质勘探等领域。图像分割是图像处

4、理过程中的一个关键步骤,为图像检索、图像分析提供有效的信息,使更高层次的图像处理成为可能。常见的图像分割方法归纳为基于边界检测和边缘连接的方法、基于区域的分割方法和结合特定理论工具的分割方法三大类。近几年,将图论方法与其他方法结合,使图像分割转变为最优化问题,成为国内外图像分割领域研究的热点。本文详细阐述了基于图论的图像分割方法,在分析最小生成树方法的概念、原理的基础上,针对Kruskal算法无法根据新生成区域修改加权区域邻接图的不足,提出一种改进的Kruskal算法:区域合并后,重新计算新区域与相邻区域的权重,修改WRAG和边的排列顺序。改进算法使WRAG更接近原图像的特征。为了降低Krus

5、kal算法中节点和边的数目,在介绍了分水岭算法的思想、基本模型和主要缺陷后,将基于数学形态学的分水岭方法引入最小生成树方法中,方法。首先,利用分水岭方法对梯度图像预分割,生成的过度分割提出K VW区域转化为无向图中的节点,相邻区域间的差异转化为边的权重,构造加权区域邻接图(WRAG,再利用改进的Kruskal算法,结合Deepthi Narayan提出的合并准则,通过区域内部差异函数、阈值函数,比较区域内部差异和外部差异,利用图像自身信息,将符合合并准则的区域进行合并操作。基于分水岭的最小生成树方法既能消除分水岭的过度分割现象,又能降低边的数目,获得图像的全局特征,保持较好的区域一致性。方法的

6、分割效果。最后,本文通过对多幅彩色图像的对比实验,验证K VW实验表明:对于前景、背景对比明显,区域内部特征变化缓慢,区域边缘部分特征变化剧烈的彩色图像,本文的方法分割效果较好,具有较强的适用性和较高的实用价值。对于包含较多噪声和细节的彩色图像,分割结果会存在冗余区域和错误边界的现象,需要进一步改进。关键词:图像分割;最小生成树;分水岭;图论; Kruskal算法中图分类号: TP391.4Research of image segmentation based on minimum spanningtreeAbstractImage processing is widely used in

7、medical images, remote sensing images, fingerprint identification, face detection, geological exploration and other fields. As a critical step in the image processing,image segmentation can provide effective information for image retrieval and image analysis, make it possible to a high level of imag

8、e processing. Common methods of image segmentation can be summarized as follow: methods based on boundary detection and edge linking, methods based on region, methods based on special theory. In recent years, the combining of graph theory with other methods is becoming a hot spot in the both domesti

9、c and foreign research field.This paper describes the image segmentation methods based on graph theory in detail. After the analysis of concepts and theories, an improved Kruskal-Minimum spanning tree algorithm is proposed, which can update the weighted region adjacency graph (WRAG. In this algorith

10、m, recalculating weights of the new region and its adjacent regions must be done after a merging, as well as changing WRAG and sorting edges. The WRAG of improved algorithm is much closer to the characteristics of the original image.The Watershed algorithm is introduced of its concepts, theories and

11、 flaws. In order to reduce the number of nodes and edges, this paper proposes a new method, named K VWmethod, combining Vincent-Watershed with Kruskal-Minimum spanning tree algorithm. Firstly, presegmentation on the gradient image is completed by the Watershed algorithm, obtaining a large number of

12、small regions. Then calculating the weights and constructing the WRAG. The nodes represent small regions, the edges between nodes represent the relationship between regions. Secondly, with Deepthi Narayan-merging criteria, the modified Kruskal algorithm can obtain better region similarity, by compar

13、ing regional differences between the internal and external information of the image own. The K VWmethod can not only eliminate the phenomenon of over segmentation, but also reduce the number of edges.By contrast experiments on series of color images, analyzing the advantages ofthe K VWmethod. The re

14、sults show that the proposed method of segmentation has good performance and strong applicability for color images, in which, there are intense contrasting of prospects and backgrounds. Its internal characterstics of regions change slowly and external characterstics of regional edges chage rapidly.

15、To those color images, which containing more noise and details, the segmentation results of method will include redundant reginons and incorrect borderline. It needs K VWfurther improvement.Key words: Image segmentation;Minimum spanning tree;Watershed;Graph theory;Kruskal algorithmClassification: TP

16、391.4第一章 绪论1.1课题研究的背景和意义视觉是人类最高级的感知手段,从视觉系统中能够获得大量的图像信息。随着计算机及其相关学科的发展,成像机器可覆盖从伽马射线到无线电波的几乎全部电磁波谱,因此数字图像处理的对象包括超声波、电子显微镜及计算机等产生的图像。为了从这些获取的图像中提取有用的信息,人们需要对图像进行分析,检测其中感兴趣的目标,获得它们的详细信息,建立图像的客观描述。在图像自动模式识别和场景分析之前,图像分割成为图像处理过程中的关键步骤。图像分割是利用图像的某些特性,如灰度、颜色、纹理、形状等,将图像分割成若干个子区域或对象,使同一区域内的像素间具有一致性1。图像分割的程度取决

17、于要解决的问题,若感兴趣的对象已经分离出来,就停止分割,否则会出现过度分割的小区域;如果分割不够,目标中就会包含冗余部分,两种分割效果都不符合人类视觉特性。因此,精确的图像分割为图像检索、图像分析提供有效的信息,使更高层次的图像处理成为可能。图像处理已在很多领域得到广泛应用,包括医学图像、遥感云图、交通图像分析、指纹识别、人脸检测、地质勘探等:(1生物医学工程方面。20世纪后期发展起来的现代医学影像技术,可以借助各种成像设备,获得X光图像、CT图像、核磁共振图像(MRI、超声图像及各种内窥镜图像等。通过图像处理,将病源的位置及形状部分提取出来,对病理组织的特征参数进行测量与统计,可以帮助医生分

18、析病情,做出正确的临床诊断,制定放射、化学、外科等治疗方案。(2航空航天技术方面。当遥感卫星经过地面上空时,星载可见光照相机等遥感仪器,能获得大量对地观测照片,传送给地面处理中心进行分析。遥感卫星图像可广泛应用于科学研究和工农业生产领域,包括国土普查、石油勘探、铁路选线、海洋海岸测绘、地图测绘、目标点定位、地质调查、电站选址、地震预报、草原及林区普查、历史文物考古等。1(3社会安全与管理方面。人脸识别、指纹识别、掌形识别等通过对人脸、指纹、掌形的动态或静态图像序列的分析,提取出有效信息,通过对比库“辨认”或“确认”身份,帮助公安部门刑事侦查,加强情报系统和安全部门的入口控制,也可以对银行、公司

19、、公共场合的视频监控图像进行目标识别。汽车牌照自动识别技术能够用于高速公路自动超速监管、港口和机场停车场管理、公路和桥梁自动收费系统等。(4工业和工程方面。过程自动控制方面如装配线中精密零件表面缺陷检测,印刷电路板瑕疵检查,邮政信件的自动分拣等。在有毒及放射性环境中识别工件及物体的形状和排列状态等。目前研究的具备视觉、听觉和触觉功能的智能机器人涉及到机器视觉,图像处理技术提供了让机器模仿生物,感知物体的基础,从而能够在环境中发现目标。几十年来,各相关学科的迅猛发展,对图像处理的要求越来越高,使得图像处理的研究更加深入和广泛。自20世纪70年代图像分割出现后,很多研究人员为之付出了巨大的努力,至

20、今己有许多种分割方法。由于不同种类的图像,在不同应用场合下需要提取不同的图像特征,现有的分割方法在通用性方面和精度方面都有很大的提高余地,所以人们还在努力研究能够普遍适用、准确率高的分割算法。对图像分割的深入研究不仅会推动数字图像处理的发展,而且会推动模式识别、计算机视觉、人工智能等计算机分支学科的发展。1.2 国内外研究现状最早的图像分割研究对象是灰度图像,随着计算机及其相关技术的发展,彩色图像越来越多,应用于彩色图像的分割技术成为研究的热点。图像分割方法种类繁多,目前已有上千种方法,近年又出现了许多新思路和新方法,大致可以归纳为基于边界检测和边缘连接的方法、基于区域的分割方法和结合特定理论

21、工具的分割方法三大类:1.2.1边界检测和边缘连接边缘检测方法是灰度图像分割中广泛使用的一种方法,以各种微分算子为基础,结合门限、平滑等手段,利用边界的梯度变化性质检测不同区域的边缘。这些年人们提出了很多的模板2,如一阶Robert算子,Sobel算子,Prewitt算子和Canny算子,二阶Laplacian算子。这些模板只能在小尺度内滤波,对于边界明显和噪声低的图像,能够获得较好的分割效果,对于边缘复杂的图像,容易受到伪轮廓线或边界空白的干扰,无法保证得到闭合的边界,分割效果不理想。为此, Rosenfele提出了多尺度3边缘检测的思想,利用小尺度滤波定位边缘,利用大尺度滤波抑制噪声,结合

22、不同尺度的信息最终决定边缘点。后来,经过Marr、Hildretch、Witkin等人的完善逐步形成了一套理论。1.2.2 基于区域的分割基于区域的分割方法根据同一区域内的像素特性相似,不同区域间的像素特性相异的准则,将图像中的像素进行分类。常见的有特征空间聚类和区域生长两种方法4:特征空间聚类是将特征空间中的点进行聚类,每个类代表图像中的一个区域,类内相似度较高,类间相似度较低。这种方法易于实现,缺点是不易找到最佳聚类特征。常见的聚类方法有K-means算法5、模糊ISODATA算法6和高斯混合密度降解(GMDD算法7。K-means算法可以通过试探法确定类的数目,判别准则通常基于分割后类内

23、和类间特征值的散布图,因此要求类内接近而类间差别大。ISODATA算法是在K-means算法的基础上发展的,算法运行时需要预先定义聚类的数目,通常先根据经验取稍大的值,然后通过合并距离较近的聚类得到最后的聚类数目。GMDD算法是一种基于稳健统计理论的层次聚类方法,通过优化算法获得特征空间中与预先假设最符的特征分布,逐步分离特征空间,直到特征空间全部降解为一组特征模式的混合密度分布集。GMDD方法中的特征类别不受限制,参数估计与初始状态无关,抗干扰能力强。区域生长是一种根据事先定义的准则将像素或子区域聚合成更大区域的过程。它的基本思想是给每个分割区域找一个种子像素作为生长的起点,然后将种子像素周

24、围的相似像素合并到种子区域。通常根据像素间的连通性和相邻性,选取生长准则,当没有像素满足加入某个区域的条件时,停止区域生长。区域生长方法存在一些缺点:1. 只能近似分割,分割结果不精确;2. 分割结果与种子点的选择有关;3. 容易受到噪声影响。黄力明8提出一种基于微粒群算法的区域生长图像分割方法,利用微粒群较强的搜索能力搜索像素种子点,克服了传统区域生长方法不能自动选择种子且容易导致过分割的局限性。1.2.3 结合特定理论工具的分割技术1.2.3.1基于数学形态学的分割方法数学形态学诞生于1964年,1982年Serra将它引入图像处理,90年代人们开始深入研究使用数学形态学分割图像。基于数学

25、形态学分割方法的基本思想是用一定形态的结构元素度量和提取图像中的对应形状,达到对图像分析和识别的目的。1991年Vincent与Solille9提出一种模拟浸水过程的分水岭算法,通过筑造大坝阻止不同盆地间的汇水,大坝在图像上形成轮廓线,包围性质相似的像素。分水岭算法容易受到噪声和细节影响,产生过度分割现象。2000年黄风岗等10提出一种柔性形态学边缘检测算子,将柔性形态变换运用到边缘检测,既保留了经典形态算子的优良特性,又获得一定程度的鲁棒性。1.2.3.2 基于模糊数学的分割方法1965年,著名控制论专家L.A.Zadeh首先提出模糊集的概念,创立了模糊数学,逐步形成了一套严格的数学方法,用

26、来描述带有模糊不确定性的现象和事物。1979年Rosenfeld首次把模糊数学引入到图像处理中后,人们不断提出新的分割方法,特别是应用在医学图像分析中。基于模糊数学的分割方法,每个像素由归属值表达属于某个区域或者某个边的度,这种方法常与其他方法结合使用。1996年Udupa11等人提出了基于模糊连通度的区域增长算法,通过比较图像中所有点与目标和背景种子点的连通度大小来进行目标和背景的分割。Clark等人12提出模糊C-均值(FCM聚类算法,通过对目标函数的迭代优化实现集合划分,可以表示各个像素属于不同类别的程度。1.2.3.3基于遗传算法的分割方法遗传算法是基于进化论中自然选择机制的、并行的、

27、统计的随机化搜索方法。1975年由Holland提出,80年代Goldberg完成了遗传算法的基本框架。它以编码空间代替问题的参数空间,以适应度函数为评价依据,以编码群体为进化基础,以对群体中个体位串遗传操作实现选择和遗传机制,通过对群体进行复制、交叉、变异完成搜索过程。遗传算法具有全局搜索能力,为函数优化提供了一个有效的途径和通用框架,通常将它与其他方法结合使用。文献13将它与C-均值方法结合,避免聚类方法陷入局部最小值,又可尽快达到最优,文献14将它与模糊集合论结合,可以提高分割的鲁棒性。2000年薛景浩等15提出了一种基于阈值曲面的二维遗传算法,采用基于阈值曲面的二维染色体编码方式,使用

28、Hopfield 网络的能量函数形式,结合图像最优分割准则构造适应度函数。算法强调相邻像素点的等同性,适于消除成块出现的突发噪声,但在分割含有随机噪声的图像时,因为灰度曲面的随机尖锐凹凸而产生误差。1.2.3.4基于活动轮廓模型的分割方法活动轮廓模型主要包括参数活动轮廓模型和几何活动轮廓模型。1987年Kass等人16提出参数活动轮廓模型(Snake模型,基本思想是在图像边界附近定义一条带有能量的闭合曲线,由于受到曲线自身内力和图像数据所构造的外力作用,闭合曲线向着能量最小的方向演化,最后收敛于图像的边界。该模型有三个缺点:1. 对初始曲线的位置比较敏感;2. 由于能量泛函的非凸性,曲线在演化

29、过程中容易陷入局部极小值点;3. 曲线的拓扑结构在演化过程中不会发生改变。1989年Axel等人17在模型中增加气球力,使变形曲线作为一个整体膨胀或收缩,1998年Xu18提出使用梯度向量流代替模型中的梯度场,Amini19提出了基于动态规划的Snake算法来求解全局最优曲线,Williams20提出结合贪婪算法,加快了Snake模型求解最优曲线的速度。几何活动轮廓模型经历了从曲线的曲率运动,到测地线几何变形模型,再到引入面积约束项的过程。Osher和Sethian21提出的基于水平集(level set理论的几何活动轮廓模型,通过一个高维函数曲面来表达低维的演化曲线或曲面,将演化方程转化为高

30、维水平集函数的演化偏微分方程,避免了变形曲线或曲面的参数化过程,解决了通过曲线拓扑结构的变化分割多个目标的问题,能够表示任意复杂形状的目标边界。Caselles等22提出的测地线活动轮廓模型,能够同时检测多个目标的边界,对凹陷区域也能有效分割。Siddiqi23在测地主动轮廓线模型上,增加了一个面积约束项,提高了变形曲线跨越图像边缘较小缝隙的能力,但对较大缝隙,仍无法跨越。1.2.3.5基于人工神经网络的分割方法基于人工神经网络方法的主要思想是将图像映射为一个神经网络,每个像素点是一个神经元,通过动态方程引导神经元的状态向最低能量方向变化,提取图像边缘。这种方法的优点是具有高度的并行性,快速的

31、计算能力,较强的鲁棒性和抗干扰能力。能够很好地解决图像噪声、组织不均匀、生物形态的多变性等问题,适用于断层扫描(CT图像和核磁共振(MRI图像。缺点是事先需要很长的学习过程训练神经网络,初始化可能影响分割结果。Huang24提出利用最小化一个合适能量函数的Hopfield神经网络进行灰度图像分割,Ong等25提出基于Kohonen自组织网络(SOM的两步分层神经网络用于彩色图像分割,应骏等26提出结合马尔算子特性的神经网络,能够提高对边缘检测的整体性能。1.2.3.6基于图论的分割方法基于图论的分割方法是将图像映射为无向图,无向图中的节点表示像素,节点间的边表示像素间的关系,边的权重表示像素间

32、的差异或相似度,利用图论中的相关知识进行图像分割。基于图论的图像分割方法可以分为基于最小生成树的方法、最小化/最大流方法、谱方法等。1971年,Zahn27提出了基于最小生成树的图像分割方法,使用固定阈值进行分类,对于像素特征变化剧烈但属于同一目标的区域,分割效果不好。1997年Shi和Malik28提出了归一化切割方法,将计算最优值问题转化为求解矩阵的特征值和特征向量,克服了偏向划分单个节点的缺陷。2004年Felzenszwalb29提出了通过比较区域间和区域内的特征差来判定区域边界的方法,能够获得全局特征。1.2.3.7 其他方法随着成像设备和技术的发展,图像颜色从灰度图像向彩色图像发展

33、,图像种类从2-D图像向高维图像发展,包括3-D图像,立体图像,多光谱图像及多视场图像等,分割的对象也从静止图像向运动图像发展,序列图像中运动目标的分割,视频图像的时间切割技术成为新的研究领域。因此图像分割技术更多地与其它学科相联系,除了使用人工智能、神经网络、遗传算法、模糊数学外,还可以结合统计学、信息论、小波变换等理论。随着各学科新理论和新方法的提出,人们也试着将其应用到图像分割中,例如利用马尔可夫随机场30、布朗链31、专家系统32等。总之,找到一种精确度高,抗噪能力强,运算速度快,适用于各种类型图像的分割方法是较为困难的,但它正是新的图像分割方法层出不穷的动力。1.3本文的主要工作及创

34、新点本文的主要工作:(1说明了课题的选取背景和意义,回顾了国内外图像分割的研究和发展现状。(2详细阐述了基于图论的图像分割方法,包括图的分割,图像到图的转化和图像的分割准则,重点介绍了最小生成树分割方法,针对Kruskal算法不能根据新生成区域修改邻接图的缺点,提出一种改进的Kruskal算法。(3介绍了基于数学形态学分水岭算法,包括基本概念,灰度图像中四个基本操作以及灰度级形态学的应用,然后介绍了分水岭算法的思想,基本模型和主要缺陷,针对分水岭方法产生的过度分割现象,将最小生成树与分水岭方法结方法,实验验证该方法对彩色图像的分割效果。合,提出K VW本文的创新点:(1提出一种改进的Krusk

35、al算法。原Kruskal算法构造最小生成树,边的数目固定为m,合并两个区域后,没有更新WRAG。改进的Kruskal算法,在区域合并后,重新计算新区域与相邻区域的权重,修改WRAG和边的排列顺序,减少了边的数目,使WRAG更接近原图特征。方法。(2提出基于分水岭的最小生成树方法(K VW使用分水岭方法对图像预分割,生成的过度分割区域转化为无向图中节点和边的关系,构造区域邻接图(WRAG,利用最小生成树方法改进的Kruskal 算法,将符合合并准则的区域进行合并,能够消除分水岭的过度分割现象,获取图像的全局特征。1.4本文的组织论文共分五章,各章的主要内容如下:第一章绪论,介绍了图像分割的研究

36、背景和意义,当前国内外的研究现状,论文的创新点和组织结构。第二章基于图论的图像分割方法,首先介绍了图论中的几个重要概念,包括图的分割,图像到图的转化和图像的分割准则,然后介绍了三种常用的基于图论的图像分割方法的分割准则,重点介绍了最小生成树方法的概念和构造过程,指出这种方法存在的的优点和缺点。第三章基于数学形态学分水岭算法,首先介绍了形态学中几个基本概念,灰度图像中四个基本操作以及灰度级形态学的应用,然后介绍了分水岭算法的思想,基本模型和主要缺陷和控制分水岭过分割的常用方法。第四章基于分水岭的最小生成树图像分割方法,首先介绍了图像分割前的预处理过程,包括颜色空间转换和求取梯度图像,然后介绍了经

37、典的Vincent分水岭算法,给出了它的主要步骤和伪代码,分析了Kruskal算法存在的缺点,并做方法,通过实了相应的改进。将分水岭与最小生成树方法结合,提出了K VW验进行验证。第五章总结与展望,总结了本文的主要工作,指出以后需要进一步完善的地方。第二章 基于图论的图像分割方法图论起源于著名的柯尼斯堡七桥问题。1736年欧拉用抽象分析法将这个问题转化为一个图论问题:用点代替每块陆地,用连接相应两点的一条线代替桥。欧拉证明了这个问题无解,并且给出了对于一个特定图以某种方式走遍的判定法则。从19世纪中叶到20世纪中叶,图论问题大量出现,如汉密尔顿图问题、四色猜想等。这些问题的出现进一步促进了图论

38、的发展。1847年,克希霍夫(Kirchhoff 用图论分析电网络,这是最早一个应用于工程科学的例子。随着计算机科学的迅猛发展,在现实生活中的许多问题,如交通网络问题,运输的优化问题,社会学中某类关系的研究,都可以用图论进行研究和处理。图论在计算机领域中,诸如算法、语言、数据库、网络理论、数据结构、操作系统、人工智能等方面都有广泛应用。近年来基于图论的图像分割技术是国际图像分割领域中一个新的研究热点。该方法将图像映射为带权无向图,将像素视为节点,利用某种准则得到图像的最佳分割,将图像分割问题转化为最优化问题。2.1基本理论概念2.1.1 图的分割2.1.1.1 图、加权图和连通图图是由若干给定

39、的顶点及连接两顶点的边所构成的一种拓扑图形,用顶点代表事物,用连接两顶点的边代表相应两个事物间的关系。若用符号G 代表图,则(,G V E =,其中V 代表顶点的集合,E 代表边的集合,每条边对应着两个相关的顶点。对E 中的每条边e ,赋给一个实数(w e ,称为边e 的权,每个边都赋有权的图称为加权图。权在不同的问题中会有不同的含义,可以表示距离、费用、时间、电阻等。在无向图G 中,如果从顶点u 到顶点v 有路径,则称u 和v 是连通的。如果图中任意两个顶点u 和v 都是连通的,则称图G 是连通图,否则称为非连通图。2.1.1.2 子图、补图和割两个图(,G V E =和(,G V E =,

40、若V 是V 的子集,E 是E 的子集,则称G 为G 的子图。给定一个图G ,由G 中所有节点和所有能使G 成为完全图的添加边组成的图,称为图G 相对于完全图的补图(Complement ,或简称为G 的补图。若(,G V E =为连通图,边集E E 1,使图G 删除了1E 的所有边后,所得到的子图是非连通图,而删除了1E 的任何真子集后所得到的子图仍是连通图,则称1E 是G 的一个边割集(Edge Cutest 。若某一条边构成一个边割集,则称该边为割边(Cut Edge ,割边的集合叫做割集(Cut Set ,割集的权值之和称作割(Cut 。2.1.1.3 邻接矩阵邻接矩阵(Adjacenc

41、y Matrix 是表示顶点之间相邻关系的矩阵。设(E V G ,=为无向图。其中12(,n V v v v = ,那么n n ×邻接矩阵A =ij a ,其中:1,(,0,(,i j ij i j v v E a v v E = 或 (2-1例如图2-1中G 的邻接矩阵如图2-2所示。 图2-1 G 图2-2 G 的邻接矩阵 如果G 为加权图,则将1ij a =改为(,ij a w i j =。例如图2-3中G 的邻接矩阵如图2-4所示。 图2-3 G 图2-4 G 的邻接矩阵2.1.1.4 图的最优分割准则令图(,G V E =,G 被划分为A 和B 两部分,且有A B V =,

42、A B =,顶点间边上的权为(,w u v ,将图G 划分为A 、B 两部分的代价函数为:,(,(,u A v B cut A B w u v = (2-2使得式(2-2值最小的划分准则称为最小割集准则。常见的割集准则有归一化切割(Normalized Cut 28、最小切割(Minimum Cut 33、平均切割(Average Cut 34、比例切割(Ratio Cut 35、等周切割(Isoperimetric Cut 36、最小最大切割(Min-max Cut 37、前景切割(ForgoundCut 38、嵌套切割(Nested Cut 39。最优分割准则的实现一般有两种方式:将最优准

43、则转化为求解矩阵方程;使用所定义的准则直接进行图缩减。2.1.2图像的分割图像分割是将人们感兴趣的具有同质特性的目标区域提取出来的过程,在分割过程中可以使用像素的灰度、颜色、纹理等特性。在图像处理早期阶段,因为图像主要是灰度图像,所以发展起来的图像分割技术也针对灰度图像,随着成像设备技术的发展,彩色图像成为主要的处理对象,原来的技术不能直接应用在彩色图像上,需要根据图像中的多种信息来进行分割。2.1.2.1图像到图的转化将图像映射到加权图(Weighted Graph ,用图G 中的顶点i v V 表示图像中的像素,用图的边ij e 表示像素之间的相邻关系,边上的权重ij w 表示像素特征之间

44、的差异或相似性。2.1.2.2权函数权函数一般定义为两个节点之间的相似度,常见的权函数有如下形式:2222222|exp(,|(,exp(0,i j i j i j X I X X F F X X r w i j otherwise <=× (2-3 对于灰度图像,i F 和j F 分别表示像素i 和j 的灰度值,i X 和j X 分别为像素i 和j 的空间坐标,I 为灰度高斯函数的标准方差,X 为空间距离高斯函数的标准方差,r 为两像素之间的有效距离。这种权值函数的定义,考虑到空间距离,对于灰度图像计算量很大,对于彩色图像计算量更大。在不考虑空间距离的邻域系统中,可以简单地把

45、权函数定义为相邻像素特征之间的绝对差值:(,|i j w i j F F = (2-4对于灰度图像,i F 的值为像素的灰度值,对于RGB 颜色空间的彩色图像,i F 可以是R 、G 、B 中的任意颜色分量,或者是其组合;对于HSI 颜色空间,i F 可以是H 、S 、I 的组合,或者是H 和S 的组合。还有其它一些利用图像的灰度、颜色、纹理、距离、形状、运动等信息构造权函数的方法,但是对于不同的图像,选择一种信息还是几种信息的组合,分割图像的效果可能是不同的。2.1.2.3 邻域系统邻域系统定义了像素间的相邻关系,一阶邻域系统为4连通结构,二阶邻域系统为8连通结构,一般图像分割算法使用二阶邻

46、域系统,如果为了减少运算量,可以使用4连通结构,但是分割效果不如8连通结构。如图2-5为4连通结构,像素p 的坐标为(,x y ,它的4连通邻域坐标分别为(,1x y 、(,1x y +、(1,x y 、(1,x y +,如果p 位于图像的边界,则p 的某一邻域像素位于图像的外部。 图2-5 p 的4连通邻域 图2-6 p 的8连通邻域如图2-6为8连通结构,p 的另外4个连通邻域坐标分别为(1,1x y 、(1,1x y +、(1,1x y +、(1,1x y +,如果p 位于图像的边界,则p 的某些邻域像素位于图像的外部。2.1.2.4图像的最佳分割将图像分割为多个小区域时,对图像分割效果

47、的好坏,没有绝对的客观评价准则,使用不同的图像,不同的分割原则和方法,得到的效果可能互有好坏,无法找到通用的方法适用于所有的图像。除了从方法的时间复杂度、空间复杂度、抗噪性等客观指标分析外,一般是基于人类的视觉系统,对人的视觉系统看到的结果进行评价,即分割结果是否将我们感兴趣的目标区域(前景和背景区域精确分割开,是否存在错误分割、过分割或者欠分割。各种算法分割出的区域与人类视觉判断的分割区域之间会有3种误差:一种是分割后的图像中存在冗余区域;一种是应分割开的区域未被分割;另一种是分割算法没有正确给出边界。在基于图论的图像分割方法中,可以明确地规定图像分割的准则,将图分割成多个子集,子集内顶点间

48、关系紧密,而子集间顶点的关系松散。若使用分割函数,可以设一幅图像为一个带权无向图(,G V E W =,像素集当做节点集V ,边缘集当做边集E ,像素间的连接权为(,w i j 。将图像二分为集合A 、B 的代价函数为,(,(,i A j B cut A B w i j =,对于一幅图像,使得(,cut A B 函数最小的划分即图像的最佳分割,这种分割准则应对某类图像具有可靠的一致性或稳定性,相邻区域之间的边界应是完整和精确定位的。2.1.3彩色空间分割2.1.3.1 RGB 向量空间分割RGB 颜色空间是一种立方体空间结构模型,用Red 、Green 、Blue 三个基本分量表示颜色,不同的

49、颜色处在立方体上或者其内部。使用RGB 彩色向量空间分割图像的方法直观,给定一个感兴趣的彩色点样品集,可以得到一个彩色平均估计,这种彩色是希望分割的彩色。令这个平均彩色用RGB 向量来表示,分割的目的是将给定图像中的每个RGB 像素分类,因此需要设置相似性度量。最简单的度量之一是欧氏距离,令z 代表RGB 空间中的任意一点,如果它们之间的距离小于特定的阈值0D ,则称与z 是相似的,与z 之间的欧氏距离为:1122222(,(T R R G G B B D a z a z a z =+z z z ( (2-5 其中,下标,R G B 表示向量与z 的RGB 分量。 2.1.3.2 HSI 向量

50、空间分割如果只在单独的平面上分割一幅彩色图像,可以选择HSI 颜色空间,它是接近人对颜色视觉感知的一种彩色空间。色调(Hue 反映颜色的类别,区分不同颜色的特征属性。饱和度(Saturation 表示颜色接近光谱色的程度,反映颜色的纯度。强度(Intensity 表示颜色明暗的程度,主要受光源强弱影响。HSI 三个分量间的相关性比RGB 三个分量间的小,而人眼对H 、S 、I 变化的区分能力比对R ,G 、B 的强。在HSI 空间中彩色图像的每个均匀性彩色区域都对应一个相对一致的色调,这使色调能够用来进行独立于阴影的彩色区域分割。因此HSI (色调、饱和度和强度颜色空间模型可从携带的彩色信息中

51、消去强度分量的影响,使HSI 模型成为开发基于彩色描述的图像处理方法的理想工具。2.2三种基于图论的图像分割方法基于图论的图像分割,使划分的两个子图内部相似度最大,子图间的相似度最小,尽量避免出现分割粗糙现象或者过度分割现象。Ratio Cut 方法直接使用定义准则进行图缩减,而Normalized Cut 方法结合谱方法,求解矩阵方程。2.2.1 Ratio Cut 分割法Ratio Cut 35是Wang Song 提出的具有稳定的边权函数的图割模型,定义了一个新的代价函数,并给出寻找最小比例割的执行算法。在构建的图G 中,赋给每条边(,u v 两个权重1(,0w u v >和2(,

52、0w u v >,1(,w u v 为第一边权重,表示两个区域之间的相似度;2(,w u v 为第二边权重,表示(U u 与(U v 之间边的数目;12(,(,w u v w u v 为边权重比率,如果2(,w u v =1,边权重比率表示的就是两个区域间每条边在单位长度上的平均一致性。定义第一边界代价函数和第二边界代价函数分别为:11,(,(,(,u A v B u v E c A B w u v = (2-6 22,(,(,(,u A v B u v E c A B w u v =(2-7一般地,1(,c A B 用来描述图G 中两区域A 和B 间的相似度,2(,c A B 描述区域

53、A 和B 间边界的长度。定义第一环路代价函数和第二环路代价函数为:11(,(,u v C c C w u v = (2-8 22(,(,u v C c C w u v =(2-9该算法的关键是找到一个最小的比率切割迭代执行分割,切割比率代价函数为:12(,(,(,c A B Rcut A B c A B = (2-10 只要使(,Rcut A B 达到最小,两分割区域A 、B 间边界的平均差别将达到最大。Wang Song 指出,找到图像对应图的最小比例割是个NP 完全问题,而且随着图中顶点数目的增多,求解耗时将会大幅增加。所以,在无法直接求取最小比例割的情况下,将计算最优的Rcut 值问题在

54、其对应的无向圈中做了简化:最小比率切割缩减到最小比率环路;最小比率环路缩减到负代价简单环路;负代价简单环路缩减到最小代价理想匹配。一个图的最小代价理想匹配比较容易找到,求解Rcut 值的问题也就迎刃而解。Ratio Cut 方法允许图像的周界被切割,保证二分产生的部分是连续的,并且不会产生边界长度的偏差,可以避免划分向短边偏移。但是,即使采用近似求解,计算量还是很大,运算速度较慢。2.2.2 Normalized Cut 方法J. Shi 和J.Malik 28提出了 Normalized Cut 方法,定义分割准则:(,(,(,(,(,cut A B cut A B Rcut A B ass

55、oc A V assoc B V =+ (2-11 其中,(,(,u A v V assoc A V w u v =,表示A 中所有节点和V 中所有节点连接边的权值之和,(,assoc B V 含义类同。Normalized Cut 分割原则与谱方法结合,需将计算最优值问题转化为求解矩阵特征值和特征向量问题。设(,G V E =,其邻接矩阵定义为(uv A G a =,若u 和v 相邻,则1uv a =,若u 和v 不相邻,则0uv a =。度对角矩阵为(:u D G diag d u V =,其中u d 是顶点u 的度。则图G 的Laplacian 矩阵定义为:(L G D G A G =

56、(2-12 令|n V =,x 是一个n 的指示向量,1i x =表示节点i 在A 中,1i x =表示节点i 在B 中,令W 为n n ×对称矩阵, 且,(,i j W i j w =,(,i j d w i j =,D 为对角矩阵且(,i D i i d =,0/i i ix ik d d >=,I 为全1的1n ×向量,则: (1(1(1(1(44(1T T T T x D W x x D W x Ncut x kI DI k I DI+=+ (2-13 若令1k b k =+,(1(12x b x y +=,则 (min T y T y D W y Ncut

57、x y Dy= (1,y i b ,0T y DI = (2-14 其中1表示元素全为1的1N ×向量,如果y 的取值限制为实数,那么求解最优值问题相当于一个求解一般的特征值问题:(D W y Dy = (2-15 用y 作指示向量,使用特征方程的第二个最小的特征值所对应的特征向量作为问题的解,这个特征向量称为Fiedler 向量,由Fielder 最先用来分割图,它代表最佳划分图的一个解。在向量y 中选择一个分割值,使y 中大于该数的部分所对应的节点在A 中,其余在B 中,并且采用递归算法以相同的方式对分割得到的子图进一步进行划分,直到满足终止条件。由于(,assoc A V 表示A 中所有节点和V 中所有节点连接边的权值之和,当A 中只包含一个节点时,(,assoc A V 的值很小,即计算Ncut 时有一个分母很小,这不符合