wij =exp(-
I iI j
2
l
2
2
)
(4)
wij = I i I j
(4)相似度矩阵、度矩阵及拉普拉斯矩阵
(5)
上述权函数仅考虑了像素之间的灰度关系，没有考虑其空间关系。
图论分割算法常把所定义的最优割集准则转化为求解相似度矩阵或拉普拉 斯矩阵的特征值及特征矢量问题。相似度常用 W 或 A 表示，有时也称亲和力 (affinity)矩阵。 将原图像中的像素从左到有单行排列并作为相似度矩阵的行序列及列序列,相似 度矩阵中每一个元素的值为使用相似度函数计算所得到的值,因此若一幅图像尺 寸为 M N ，则其相似度矩阵元素个数将
XXX
XX 教授
计算机科学与技术
计算机学院
本科毕业设计说明书（论文）
1. 引言
第 2页
共 21页
数字图像处理技术是一个跨学科的领域。随着计算机科学技术的不断发展， 图像处理和分析逐渐形成了自己的科学体系，新的处理方法层出不穷，尽管其发 展历史不长，但却引起各方面人士的广泛关注。首先，视觉是人类最重要的感知 手段，图像又是视觉的基础，因此，数字图像成为心理学、生理学、计算机科学 等诸多领域内的学者们研究视觉感知的有效工具。 其次， 图像处理在军事、 遥感、 气象等大型应用中有不断增长的需求。 基于图论的图像分割技术是近年来国际上图像分割领域的一个新的研究热 点。该方法将图像映射为带权无向图，把像素视作节点。利用最小剪切准则得到 图像的最佳分割 该方法本质上将图像分割问题转化为最优化问题。是一种点对 聚类方法。对数据聚类也具有很好的应用前景。但由于其涉及的理论知识较多， 应用也还处在初级阶段。 因此国内这方面的研究报道并不多见，本文将对图论方 法用于图像分割的基本理论进行简要介绍， 并对当前图论方法用于图像分割的最 新研究进展进行综述，并着重介绍基于等周图割的图像分割的方法。
cut 2 A, B
cut1 A, B
本科毕业设计说明书（论文）
1 x 2 if i A if i B ( 6)
第 6页
共 21页
若最终势函数中某像素对应的值为1．则该像素属于集合A，若为0则属于集 合B。但实际划分求解得到的结果 x i 常为0到1之间的实数值，此时可用k均值聚 类等方法进一步决定像素的归属。 许多图论分割算法将图划分问题转化为求解下述方程的第二小特征矢量 问题：
本科毕业设计说明书（论文）
前三种准则的较详细的性能对比参见文献[17]。
表1 几种常见准则的比较
第 7页
共 21页
准则 Minimum Cut
准则形式 Cut(A,B)=
uA ,vB
准则实现方式 树图缩减
特点 易倾向于 较小的分 割

w u, v
Average Cut
Avcut(A,B)=
2. 图像目标分割与提取技术综述
图像分割是一种重要的图像技术， 在理论研究和实际应用中都得到了人们的 广泛重视。 图像分割的方法和种类有很多， 有些分割运算可直接应用于任何图像， 而另一些只能适用于特殊类别的图像。有些算法需要先对图像进行粗分割，因为 他们需要从图像中提取出来的信息。例如，可以对图像的灰度级设置门限的方法 分割。值得提出的是，没有唯一的标准的分割方法。许多不同种类的图像或景物 都可作为待分割的图像数据， 不同类型的图像，已经有相对应的分割方法对其分 割，同时，某些分割方法也只是适合于某些特殊类型的图像分割。分割结果的好 坏需要根据具体的场合及要求衡量。 图像分割是从图像处理到图像分析的关键步 骤，可以说，图像分割结果的好坏直接影响对图像的理解。
本科毕业设计说明书（论文）
第 1页
共 21页
清华大学本科生毕业设计
题目: 基于 MATLAB 的图像分割算法研究
作者姓名 学号 指导教师 学科专业
所在学院 提交日期
目录： 1 引言 2 图像目标分割与提取技术综述 3 最优割集准则的设计 4 基于等周图割的图像分割 5 编程语言的选择 6 程序运行结果
cut(A,B) cut(A,B) + A B
求方程 (D-W)x= x
易倾向于 较大的分 割
Normalize Cut
Ncut=
assoc A,V
cut A, B

assoc B ,V
cut A, B
求方程 (D-W)x= Dx
当类间重 叠较大时 易出现歪 斜划分
M N
2
。
将相似度矩阵的每行元素相加。即得到该节点的度，以所有度值为对角元 素构成的对角矩阵即为度矩阵，度矩阵常用D表示。 拉普拉斯矩阵为L=D—W， 在图论分割算法中拉普拉斯为常用的标准矩阵。 (5)势函数、Fiedler矢量及谱 势函数为代表某像素划分归属的指示矢量(indicator vector)。其定义为：
D D W D 2
1 2
1
x= x
(7)
这里的第二小特征矢量为第二个最小特征值对应的特征矢量， 它代表了最 佳图划分的一个解(即势函数)，把这一特征矢量称为Fiedler矢量。与特征矢量(不 一定是Fiedler矢量)对应的特征值称为谱。
3 最优割集准则的设计
目前，基于图论的图像分割方法的研究主要集中在以下几个方面：(1)最优 剪切准则的设计；(2)谱方法用于分割；(3)快速算法的设计；(4)其他图论分割方 法。 通过对以上图论的研究与比较，我们现在应该找出一种较好的图像分割的方 法，或是得到这种方法的途径。
iA, jB

w i, j
(2)
对于一幅图像，使得上述代价函数最小的划分即为图像的最佳分割。 (3)权函数 权函数一般定义为两个节点之间的相似度。 在基于图论的图像分割方法中． 常
本科毕业设计说明书（论文）
见的权函数有如下形式：
|| X i X j || 2 2 || Fi F j || 2 exp 2 2 wij exp l 2 l 0 others if
Assoc(A,V)=
uA ,vB

u, v
cut A, B W B
Min-Max Cut
Mcut=
cut A, B ห้องสมุดไป่ตู้ W A

求方程 (D-W)x=
后置处理 需要花费 大量时间 速度较慢， 可避免划 分向短边 偏移
Dx 1
Ratio Cut
Rcut(A,B)=
第 5页
共 21页
|| X i X j || 2 r
(3)
上式权函数中， 对于灰度图像， Fi的值为像素的灰度值， Xi为像素的空间坐标， l 为灰度高斯函数的标准方差， X 为空间距离高斯函数的标准方差。r为两像素之 间的有效距离。若超过这一距离，则认为两像素之间的相似度为0。此相似度函 数认为，两像素之间的灰度值越接近，则两像素之间的相似度越大，两像素之间 的距离越近则其相似度也越大。 另外，文献[16]定义了如下两个权函数为：
3.1割集准则
由式(2)的最优分割准则及式(3)的相似度函数可知， 基于图论的最优分割基 本原则就是使划分成的两个子图(区域)内部相似度最大．子图之间的相似度最 小．同时应使得划分的区域尽量避免出现歪斜(即偏向小区域)分割。 割集准则的好坏直接影响到分割结果的优劣。常见的割集准则有Minimum cut，Average cut，Normalize cut，Min-maxCut，Ratio cut，Foreground-cut，Bcut， Isoperimetric ratio， Nested cut。 表1列出了几种常见的割集准则。 其中Norma1ize cut 是一种较规范的形式， 可以将准则转化为求解矩阵的特征矢量问题 Isoperimetric ratio是一种较新颖的图论分割算法，且运算速度较快，不需要对相似度矩阵进行 重构。 最优准则的实现有两种方式：一种是将最优准则转化为求解矩阵方程 ，另 一种方法是使用所定义的准则直接进行图缩减。
2.1.1 研究背景与意义
数字图像目标分割与提取是数字图像处理和计算机视觉领域中一个备受关 注的研究分支。 因为在目标分割与提取过程中可以利用大量的数字图像处理的方 法，加上其在计算机视觉、模式识别等领域中的广泛应用，都吸引了众多研究者 的注意。 相信对这一问题的深入研究不仅会不断完善对这一问题的解决，而且必 将推动模式识别、计算机视觉、人工智能等计算机科学分支的发展。图像分割和 边缘检测的问题在近二十年中得到了广泛的关注和长足的发展， 国内外很多研究 人士提出了很多方法， 在不同的领域取得了一定的成果。但是对于寻找一种能够 普遍适用于各种复杂情况的准确率很高的分割和检测算法，还有很大的探索空 间。 边缘提取和分割是图像分析的经典研究课题之一， 目前的理论和方法仍存在 许多不足之处，仍在不断改进和发展。需要说明的是：边缘与物体间的边界并不 等同， 边缘指的是图像中像素的值有突变的地方，而物体间的边界指的是现实场 景中的存在与物体之间的边界。 有可能有边缘的地方并非边界，也有可能边界的 地方并无边缘，因为现实中的物体是三维的，而图像只具有二维信息，从三维到
uA,vB

w u, v
(1)
使得上述剪切值最小的划分(A，B)即为图G的最优二元划分．这一划分准则称为 最小割集(Minimum cut)准则。 (2)图像的最佳分割 将一幅图像视为一个带权的无向图G=( V，E)，像素集被看作节点集.边缘集 被看作边集E，像素之间的连接权为W（i,j），则将图像二值划分为两个集合(区 域)A，B的代价函数为： cut(A, B)=
2.2
基于图论的图像分割
基于图论的图像分割技术是近年来国际上图像分割领域的一个新的研究热
点，在此，有必要先介绍一下基于图论分割的一些基本知识。