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

《基于最小生成树的图像分割方法研究.doc》由会员分享，可在线阅读，更多相关《基于最小生成树的图像分割方法研究.doc（70页珍藏版）》请在三一办公上搜索。

1、目 录摘 要IAbstractIII第一章 绪论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 Isoperimetric Ratio 方法162.3 最小生成树分割方

2、法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 图像预处理314.1.1 颜色空间变换314.1.2 求取梯度图像324.2 基于分水岭的最小生成树图像分割方法 K VW 方法34

3、4.2.1 方法背景344.2.2 Vincent 分水岭算法344.2.3 最小生成树合并区域374.2.4 K VW 方法424.3 实验分析444.4 本章小结46第五章 总结与展望4775.1 已完成的工作475.2 进一步的研究工作47参考文献49致 谢52攻读硕士学位期间发表的论文和参与的项目53基于最小生成树的图像分割方法研究摘 要图像处理广泛应用在医学图像、遥感云图、指纹识别、人脸检测、地质勘探等领域。图像分割是图像处理过程中的一个关键步骤，为图像检索、图像分析提供有效的信息，使更高层次的图像处理成为可能。常见的图像分割方法归纳为基于边界检测和边缘连接的方法、基于区域的分割方法

4、和结合特定理论工具的分割方法三大类。近几年，将图论方法与其他方法结合，使图像分割转变为最优化问题，成为国内外图像分割领域研究的热点。本文详细阐述了基于图论的图像分割方法，在分析最小生成树方法的概念、原理的基础上，针对 Kruskal 算法无法根据新生成区域修改加权区域邻接图的不足，提出一种改进的 Kruskal 算法：区域合并后，重新计算新区域与相邻区域的权重，修改 WRAG 和边的排列顺序。改进算法使 WRAG 更接近原图像的特征。为了降低 Kruskal 算法中节点和边的数目，在介绍了分水岭算法的思想、基本模型和主要缺陷后，将基于数学形态学的分水岭方法引入最小生成树方法中， 提出 K VW

5、 方法。首先，利用分水岭方法对梯度图像预分割，生成的过度分割区域转化为无向图中的节点，相邻区域间的差异转化为边的权重，构造加权区域邻接图（WRAG），再利用改进的 Kruskal 算法，结合 Deepthi Narayan 提出的合并准则，通过区域内部差异函数、阈值函数，比较区域内部差异和外部差异，利用图像自身信息，将符合合并准则的区域进行合并操作。基于分水岭的最小生成树方法既能消除分水岭的过度分割现象，又能降低边的数目，获得图像的全局特征，保持较好的区域一致性。最后，本文通过对多幅彩色图像的对比实验，验证 K VW 方法的分割效果。实验表明：对于前景、背景对比明显，区域内部特征变化缓慢，区域

6、边缘部分特征变化剧烈的彩色图像，本文的方法分割效果较好，具有较强的适用性和较高的实用价值。对于包含较多噪声和细节的彩色图像，分割结果会存在冗余区域和错误边界的现象，需要进一步改进。关键词：图像分割；最小生成树；分水岭；图论； Kruskal 算法中图分类号： TP391.4Research of image segmentation based on minimum spanning treeAbstractImage processing is widely used in medical images, remote sensing images, fingerprint identifi

7、cation, 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 image processing. Common methods of image segmentation can be s

8、ummarized 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 domestic and foreign research field.This paper describes the image

9、 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 algorithm, recalculating weights of the new region and its adjacen

10、t 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 flaws. In order to reduce the number of nodes and edges,

11、this paper proposes a new method, named K VW method, 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 small regions. Then calculating the weights and construct

12、ing 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 comparing regional differences between the internal and externa

13、l information of the image own. The K VW method 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 VW method. The results show that the proposed method of segmentation has

14、 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. To those color images, which containing more noise and

15、details, the segmentation results of K VW method will include redundant reginons and incorrect borderline. It needs further improvement.Key words: Image segmentation；Minimum spanning tree；Watershed；Graph theory； Kruskal algorithmClassification: TP391.4第一章 绪论1.1 课题研究的背景和意义视觉是人类最高级的感知手段，从视觉系统中能够获得大量的图

16、像信息。随 着计算机及其相关学科的发展，成像机器可覆盖从伽马射线到无线电波的几乎全 部电磁波谱，因此数字图像处理的对象包括超声波、电子显微镜及计算机等产生 的图像。为了从这些获取的图像中提取有用的信息，人们需要对图像进行分析，检测 其中感兴趣的目标，获得它们的详细信息，建立图像的客观描述。在图像自动模式识别和场景分析之前，图像分割成为图像处理过程中的关键 步骤。图像分割是利用图像的某些特性，如灰度、颜色、纹理、形状等，将图像 分割成若干个子区域或对象，使同一区域内的像素间具有一致性1。图像分割的 程度取决于要解决的问题，若感兴趣的对象已经分离出来，就停止分割，否则会 出现过度分割的小区域；如果

17、分割不够，目标中就会包含冗余部分，两种分割效 果都不符合人类视觉特性。因此，精确的图像分割为图像检索、图像分析提供有 效的信息，使更高层次的图像处理成为可能。图像处理已在很多领域得到广泛应用，包括医学图像、遥感云图、交通图像 分析、指纹识别、人脸检测、地质勘探等：（1）生物医学工程方面。20 世纪后期发展起来的现代医学影像技术，可以借助各种成像设备，获得 X 光图像、CT 图像、核磁共振图像（MRI）、超声图像及各种内窥镜图像等。通过图像处理，将病源的位置及形状部分提取出来，对病理组织的特征参数进行测量与统计，可以帮助医生分析病情，做出正确的临床诊断，制定放射、化学、外科等治疗方案。（2）航空

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

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

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

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

22、arr、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提出一种基于微粒群算法的区域生长图像分割方法，利用微粒群较3强的搜索能力搜索像素种子点，克服了传统区域生长方法不能自动选择种子且容易导致过分割的局限性。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-均值方法结4合，避免聚类方法陷入局部最小值，又可尽快达到最优，文献14将它与模糊集合论结合，可以提高分割的鲁棒性。2000 年薛景浩等15提出了一种基于阈值曲面的二

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

29、 对初始曲线的位置比较敏感； 2. 由于能量泛函的非凸性，曲线在演化过程中容易陷入局部极小值点； 3. 曲线的拓扑结构在演化过程中不会发生改变。 1989 年 Axel 等人17在模型中增加气球力，使变形曲线作为一个整体膨胀或收缩，1998 年 Xu18提出使用梯度向量流代替模型中的梯度场，Amini19提出了基于动态规划的 Snake 算法来求解全局最优曲线，Williams20提出结合贪婪算法，加快了 Snake 模型求解最优曲线的速度。几何活动轮廓模型经历了从曲线的曲率运动，到测地线几何变形模型，再到引入面积约束项的过程。Osher 和 Sethian21提出的基于水平集（level s

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

31、通过动态方程引导神经元的状态向最低能量方向变化，提取图像边缘。这种方法的优点是具有高度的并行性，快速的计算能力，较强的鲁棒性和抗干扰能力。能够很好地解决图像噪声、组织不均匀、生物形态的多变性等问题，适用于断层扫描（CT）图像和核磁共振（MRI）图像。缺点是事先需要很长的学习过程训练神经网络，初始化可能影响分割结果。Huang24提出利用最小化一个合适能量函数的 Hopfield 神经网络进行灰度图像分割，Ong 等25提出基于 Kohonen 自组织网络（SOM）的两步分层神经网络用于彩色图像分割，应骏等26提出结合马尔算子特性的神经网络，能够提高对边缘检测的整体性能。1.2.3.6 基于图论

32、的分割方法基于图论的分割方法是将图像映射为无向图，无向图中的节点表示像素，节点间的边表示像素间的关系，边的权重表示像素间的差异或相似度，利用图论中的相关知识进行图像分割。基于图论的图像分割方法可以分为基于最小生成树的方法、最小化/最大流方法、谱方法等。1971 年，Zahn27提出了基于最小生成树的图像分割方法，使用固定阈值进行分类，对于像素特征变化剧烈但属于同一目标的区域，分割效果不好。1997 年 Shi 和 Malik28提出了归一化切割方法，将计算最优值问题转化为求解矩阵的特征值和特征向量，克服了偏向划分单个节点的缺陷。2004 年 Felzenszwalb29提出了通过比较区域间和区

33、域内的特征差来判定区域边界的方法，能够获得全局特征。1.2.3.7 其他方法随着成像设备和技术的发展，图像颜色从灰度图像向彩色图像发展，图像种类从 2-D 图像向高维图像发展，包括 3-D 图像，立体图像，多光谱图像及多视场图像等，分割的对象也从静止图像向运动图像发展，序列图像中运动目标的分割，视频图像的时间切割技术成为新的研究领域。因此图像分割技术更多地与其它学科相联系，除了使用人工智能、神经网络、遗传算法、模糊数学外，还可以结合统计学、信息论、小波变换等理论。随着各学科新理论和新方法的提出，人们也试着将其应用到图像分割中，例如利用马尔可夫随机场30、布朗链31、专家系统32等。总之，找到一

34、种精确度高，抗噪能力强，运算速度快，适用于各种类型图像的分割方法是较为困难的，但它正是新的图像分割方法层出不穷的动力。61.3 本文的主要工作及创新点本文的主要工作：（1）说明了课题的选取背景和意义，回顾了国内外图像分割的研究和发展现状。（2）详细阐述了基于图论的图像分割方法，包括图的分割，图像到图的转化和图像的分割准则，重点介绍了最小生成树分割方法，针对 Kruskal 算法不能根据新生成区域修改邻接图的缺点，提出一种改进的 Kruskal 算法。（3）介绍了基于数学形态学分水岭算法，包括基本概念，灰度图像中四个基本操作以及灰度级形态学的应用，然后介绍了分水岭算法的思想，基本模型和主要缺陷，

35、针对分水岭方法产生的过度分割现象，将最小生成树与分水岭方法结合，提出 K VW 方法，实验验证该方法对彩色图像的分割效果。本文的创新点：（1）提出一种改进的 Kruskal 算法。原 Kruskal 算法构造最小生成树，边的数目固定为 m ，合并两个区域后，没有更新 WRAG。改进的 Kruskal 算法，在区域合并后，重新计算新区域与相邻区域的权重，修改 WRAG 和边的排列顺序，减少了边的数目，使 WRAG 更接近原图特征。（2）提出基于分水岭的最小生成树方法（ K VW 方法）。使用分水岭方法对图像预分割，生成的过度分割区域转化为无向图中节点和边的关系，构造区域邻接图（WRAG），利用最

36、小生成树方法改进的 Kruskal算法，将符合合并准则的区域进行合并，能够消除分水岭的过度分割现象，获取图像的全局特征。1.4 本文的组织论文共分五章，各章的主要内容如下：第一章绪论，介绍了图像分割的研究背景和意义，当前国内外的研究现状，论文的创新点和组织结构。第二章基于图论的图像分割方法，首先介绍了图论中的几个重要概念，包括图的分割，图像到图的转化和图像的分割准则，然后介绍了三种常用的基于图论的图像分割方法的分割准则，重点介绍了最小生成树方法的概念和构造过程，指7出这种方法存在的的优点和缺点。第三章基于数学形态学分水岭算法，首先介绍了形态学中几个基本概念，灰度图像中四个基本操作以及灰度级形态

37、学的应用，然后介绍了分水岭算法的思想，基本模型和主要缺陷和控制分水岭过分割的常用方法。第四章基于分水岭的最小生成树图像分割方法，首先介绍了图像分割前的预处理过程，包括颜色空间转换和求取梯度图像，然后介绍了经典的 Vincent 分水岭算法，给出了它的主要步骤和伪代码，分析了 Kruskal 算法存在的缺点，并做了相应的改进。将分水岭与最小生成树方法结合，提出了 K VW 方法，通过实验进行验证。第五章总结与展望，总结了本文的主要工作，指出以后需要进一步完善的地方。8第二章 基于图论的图像分割方法图论起源于著名的柯尼斯堡七桥问题。1736 年欧拉用抽象分析法将这个问题转化为一个图论问题：用点代替

38、每块陆地，用连接相应两点的一条线代替桥。欧拉证明了这个问题无解，并且给出了对于一个特定图以某种方式走遍的判定法则。从 19 世纪中叶到 20 世纪中叶，图论问题大量出现，如汉密尔顿图问题、四色猜想等。这些问题的出现进一步促进了图论的发展。1847 年，克希霍夫（Kirchhoff）用图论分析电网络，这是最早一个应用于工程科学的例子。随着计算机科学的迅猛发展，在现实生活中的许多问题，如交通网络问题，运输的优化问题，社会学中某类关系的研究，都可以用图论进行研究和处理。图论在计算机领域中，诸如算法、语言、数据库、网络理论、数据结构、操作系统、人工智能等方面都有广泛应用。近年来基于图论的图像分割技术是

39、国际图像分割领域中一个新的研究热点。该方法将图像映射为带权无向图，将像素视为节点，利用某种准则得到图像的最佳分割，将图像分割问题转化为最优化问题。2.1 基本理论概念2.1.1 图的分割2.1.1.1 图、加权图和连通图图是由若干给定的顶点及连接两顶点的边所构成的一种拓扑图形，用顶点代表事物，用连接两顶点的边代表相应两个事物间的关系。若用符号G 代表图，则G = (V , E) ，其中V 代表顶点的集合，E 代表边的集合，每条边对应着两个相关的顶点。对 E 中的每条边e ，赋给一个实数 w( e) ，称为边e 的权，每个边都赋有权的图称为加权图。权在不同的问题中会有不同的含义，可以表示距离、费

40、用、时间、电阻等。在无向图G 中，如果从顶点u 到顶点v 有路径，则称u 和v 是连通的。如果图中任意两个顶点u 和v 都是连通的，则称图G 是连通图，否则称为非连通图。2.1.1.2 子图、补图和割两个图G = (V , E) 和G= (V ,E)，若V是V 的子集， E是 E 的子集，则9称G为G 的子图。给定一个图G ，由G 中所有节点和所有能使G 成为完全图的添加边组成的图，称为图G 相对于完全图的补图（Complement），或简称为G 的 补图。若G = (V , E) 为连通图，边集 E1 E ，使图G 删除了 E1 的所有边后，所得到的子图是非连通图，而删除了 E1 的任何真子

41、集后所得到的子图仍是连通图，则称 E1 是G 的一个边割集（Edge Cutest）。若某一条边构成一个边割集，则称该边为割边（Cut Edge），割边的集合叫做割集（Cut Set），割集的权值之和称作割（Cut）。2.1.1.3 邻接矩阵邻接矩阵（Adjacency Matrix）是表示顶点之间相邻关系的矩阵。设 G =（V , E）为无向图。其中V = ( v1 , v2 , ,vn ) ，那么 n n 邻接矩阵 A = aij ，其中：1,( v , v) Eaiji j=( vi , v j ) E(2-1)0 或,例如图 2-1 中G 的邻接矩阵如图 2-2 所示。图 2-1 G图

42、 2-2 G 的邻接矩阵如果G 为加权图，则将 aij =1改为 aij = w(i , j) 。例如图 2-3 中G的邻接矩阵 如图 2-4 所示。图 2-3 G图 2-4 G的邻接矩阵102.1.1.4 图的最优分割准则令图G = (V , E) ，G 被划分为 A 和 B 两部分，且有 A B =V ， A B = ，顶点间边上的权为 w(u , v) ，将图G 划分为 A 、 B 两部分的代价函数为：cut ( A, B ) = w(u , v)（2-2）u A , vB使得式（2-2）值最小的划分准则称为最小割集准则。常见的割集准则有归一化切割（Normalized Cut）28、最

43、小切割（MinimumCut）33、平均切割（Average Cut）34、比例切割（Ratio Cut）35、等周切割（Isoperimetric Cut） 36、最小最大切割（Min-max Cut）37、前景切割（ForgoundCut）38、嵌套切割（Nested Cut）39。最优分割准则的实现一般有两种方式：将最优准则转化为求解矩阵方程；使用所定义的准则直接进行图缩减。2.1.2 图像的分割图像分割是将人们感兴趣的具有同质特性的目标区域提取出来的过程，在分割过程中可以使用像素的灰度、颜色、纹理等特性。在图像处理早期阶段，因为图像主要是灰度图像，所以发展起来的图像分割技术也针对灰度图像，随着成像设备技术的发展，彩色图像成为主要的处理对象，原来的技术不能直接应用在彩色图像上，需要根据图像中的多种信息来进行分割。2.1.2.1 图像到图的转化将图像映射到加权图（Weighted Graph），用图G 中的顶点vi V 表示图像中的像素，用图的边eij 表示像素之间的相邻关系，边上的权重 wij 表示像素特征之间的差异或相似性。2.1.2.2 权函数权函数一般定义为两个节点之间的相似度，常见的权函数有如下形式：