（计算机应用技术专业论文）基于图论的图像谱分割技术.pdf

? j y r l l l l1 1 r r 8 i j r j i o i r1 8 ii i 3 i o i i i 攀 ， 多。 k ， ， c l a s s i f i e di n d e x ： u d c ： ad i s s e r t a t i o nf o rt h ed e g r e eo fm e n g t h e i m a g es p e c t r u ms e g m e n t a t i o n b a s e d o n g r a p ht h e o r y c a n d i d a t e ：i j uk u if e n g s u p e r v i s o r ：a s s o c i a t ep r o f z h e n gl i y i n g a c a d e m i cd e g r e e a p p l i e df o r ：m a s t e ro fe n g i n e e r i n g s p e c i a l i t y ：c o m p u t e ra p p l i e dt e c h n o l o g y d a t eo fs u b m i s s i o n ：d e c e m b e r , 2 0 0 9 d a t eo fo r a le x a m i n a t i o n ：m a r c h ，2 0 1 0 u n i v e r s i t y ：h a r b i ne n g i n e e r i n gu n i v e r s i t y 上 、 i ， - 。 j 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用已在 文中指出，并与参考文献相对应。除文中已注明引用的内容外， 本论文不包含任何其他个人或集体已经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 作者( 签字) ：翻1 歪国 日期：和f o 年- ；月f 7 日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文雠授予学位后即可口在授予学位1 2 个月后口 解密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) ：勃1 奎础 日期：砷年弓月j ) 日 导师( 签字) ：神诵锹 f o 年乡月f 甲 0 哈尔滨t 程大学硕士学位论文 摘要 图像分割是数字图像分析的重要环节，在整个的图像分析中起着承前启 后的作用，它既是对所有图像预处理效果的一个检验，也是后续图像分析与 解释的基础。因此，过去的四十多年里，图像分割技术一直广泛的受到人们 的重视，研究者提出了数以千计的不同算法。虽然这些算法在不同程度上取 得了一定成绩，但是图像分割问题还远远没有解决，仍然面临着严峻的挑战。 本文在阅读大量相关文献的基础之上，对归一化割准贝j j ( n o r m a l i z c dc u t ， n c u t ) 进行研究，提出了改进的基于图谱理论的图像多阈值分割技术。通常所 用的n c u t 算法都是以图像中的像素点为节点创建无向带权图，在该无向图 的基础上产生的是一个n x n 维的权值矩阵，其中是图像中像素的个数， 当图像非常大时算法的时间复杂度必然很大。为了克服这一问题，本文提出 了基于n c u t 准则和图像二维直方图的图像多阈值分割方法。该方法的主体 思想是：在图像的二维灰度直方图的基础之上利用k - 均值聚类分析法对图像 进行预分割，将预分割得到的小而连续的区域作为节点创建无向带权图。在 该无向图基础之上产生的权值矩阵的维数将远远小于n x n 从而大大减小了 算法的时间复杂度和空间复杂度。文中最后介绍了算法的仿真实现并最终给 出了相关的实验结果。 关键词：图谱理论；图像分割；归一化割；多阈值分割；二维灰度直方图 i m a n yr e l a t e dl i t e r a t u r e s ，t h e n w ep r o p o s e da n i m p r o v e di m a g es p e c t r u m s e g m e n t a t i o nt e c h n o l o g yw h i c hi sb a s e do ng r a p ht h e o r y t h eu s u a l l yn o r m a l i z e d c u tt h e o r yu s et h ep i x e l si nt h ep i c t u r e sa st h en o d e st oc r e a t et h ew e i g h t e d u n d i r e c t e dl i a i s o ng r a p h t h e nc r e a t ean x nd i m sw e i g h t e dm a t r i xa c c o r d i n gt o t h ew e i g h t e du n d i r e c t e dl i a i s o ng r a p h t h et i m ec o m p l e x i t yo ft h ea l g o r i t h mw i l l b e c o m ev e r r yb i gi ft h eg r a p hi sv e r yb i g , i no r d e rt oo v e r c o m et h i sp r o b l e m ，t h i s p a p e r p r o p o s e sa ni m a g es e g m e n t a t i o nm e t h o db a s e do nn c u tc r i t e r i o na n di m a g e 2 - d s h i s t o g r a m t h em a i nt h e o r yo ft h i s m e t h o di st h a t ，f i r s t ，a c c o r d i n gt ot h e t w o d i mh i s t o g r a mo ft h ei m a g e ，w em a k eu s eo ft h ek - m e a n sc l u s t e r i n ga n a l y s i s m e t h o dt o p r e s e g m e n t t h e g r a p h ，a n dt h e n ，u s e t h eo u t c o m eo ft h e i m a g e p r e s e g m e n t a t i o n ，s m a l la n dc o n t i n u o u sa r e a ，a sn o d e so ft h ew e i g h t e du n d i r e c t e d l i a i s o ng r a p h t h ed i m e n s i o no ft h ew e i g h t e dm a t r i x ，a c c o r d i n gt ot h ew e i g h t e d u n d i r e c t e dl i a i s o ng r a p h ，w i l lf a rf r o mn x n ，t h a ti st os a y ，t h i sm e t h o dd e c r e a s et h e c o m p l e x i t yo ft h ea l g o r i t h m a tt h ee n do ft h i sp a p e l w eg i v eo u tt h es i m u l a t i o n r e a l i z a t i o no ft h ea l g o r i t h ma n dt h eo u t c o m eo ft h ee x p e r i m e n t k e yw o r d s ：g r a p h i cs p e c t r u mt h e o r y ；t h ei m a g es p e c t r u ms e g m e n t a t i o n ；t h e l 哈尔滨工程大学硕十学位论文 n o r m a l i z e dc u t ；m u l t i l e v e lt h r e s h o l d i n gs e g m e n t a t i o n ；g r e yl e v e l h i s t o g r a m 2 a 哈尔滨丁程大学硕士学位论文 目录 第1 章绪论 1 1 引言 1 2 基于图谱理论的图象分割技术研究的目的和意义 1 3 基于图谱理论的图象分割技术的研究现状 1 4 论文的主要工作及论文的结构 第2 章图谱理论及割集准则一 2 1 图谱理论 2 2 割集准则的比较 2 3 割集准则的应用 2 4 本章小结 第3 章基于图谱理论的多阈值分割技术 3 1 图像的多阂值分割 3 2 图像的二维直方图 3 3 基于k - m e a n s 二维直方图技术 3 4n c u t 的权函数选择 3 5n c u t 算法 3 5 1n c u t 简介 3 5 2n c u t 分割的具体步骤 3 6 基于n c u t 的多阈值分割方法。 3 7 本章小结 第4 章实验结果的分析。 4 1 测试数据以及算法参数选择 4 2 测试结果 4 3 本章小结。 ， 一 哈尔滨t 程大学硕士学位论文 结论5 4 参考文献5 6 攻读硕士学位期间发表的论文和取得的科研成果6 2 致谢。6 3 2 产 一 哈尔滨下程大学硕十学位论文 第1 章绪论 1 1 引言 随着计算机的快速发展，新的技术不断涌现，计算机的应用越来越广泛， 几乎渗透到了社会的各个领域。图像分割就是伴随着计算机的发展而兴起的 一种图像图形学领域的新的应用技术，是计算机图像图形学与计算机视觉领 域中最为基础和前沿的领域之一，是各种图像处理、识别、分析的基本前提。 图像分割理论是从上个世纪8 0 年代才开始出现的，后来逐渐受到计算机图像 图形学领域诸多学者们的广泛关注和重视，但是由于各种条件的限制图像分 割技术并没有得到实际的发展，后来因为引入了很多其他领域学科的一些新 的理论，例如：小波变换、分形理论、形态学、模糊数学、人工智能等，由 于这些理论的加入逐渐产生了一些新的分割效果较好的图像分割算法，到目 前为止人们已经提出了上千种图像分割算法。例如：直方图阈值法、边缘检 测法、基于区域的方法、聚类分析法、神经网络法、模糊阈值法等。但是因 为现在没有通用的分割理论，大多图像分割算法都是针对某一具体领域的图 像的，并没有一种适合所有图像的分割效果较好的分割算法，即在实际应用 中，当感兴趣的对象已经被分离出来时就停止分割。同时，也没有出现判断 分割算法好坏的通用标准，这给图像分割技术的应用带来了很多实际的困难。 因此，很多研究图形图像方面的学者正在努力的从事着图像分割理论的研究。 近年来人们又把图论中的一些理论引入了图像分割领域，产生了基于图论的 图像谱分割技术。 图像的谱分割技术在图像分割领域表现出了良好的发展前景。该技术的 基本思想是把一幅目标图像映射到一个无向带权图中，然后把对图分割的问 题转化为聚类分析问题。图像的谱分割技术作为一种新兴的图像分割技术， 不仅具有良好的分割性能，而且具有很好的应用前景。但是在将一幅目标图 像映射到一个无向带权图的过程中如果图像的尺寸非常大的话那么算法的时 广 哈尔滨_ t 程大学硕十学位论文 间复杂度也将会非常的大，这使得算法的实时性很差，因此，在很多实时性 要求很高的应用领域该算法就不再适用。正因为这个原因很多图像图形学领 域的研究学者们正在积极的研究新的改进的谱分割算法。 1 2 基于图谱理论的图象分割技术研究的目的和意义 图像分割是从图像处理到图像分析转变的关键，也是一种基本的计算机 视觉技术。这是因为通过图像的分割、目标的分离、特征的提取和参数的测 量等技术将原始图像转化为更抽象更紧凑的形式，为进一步的图像分析和理 解提供帮助。图像分割就是根据图像的空间、纹理、颜色、灰度、几何形状 等的特征将目标图像分割成若干个具有特殊含义的互不相交的子区域，使得 这些特征在同一区域的内部表现出极强的一致性和相似性，而在不同的区域 之间则表现出极大的差异性。简单的讲：图像分割，就是将一幅图像划分成 与其中所含有的真实世界中的物体或区域有极强相关性的若干组成部分的一 个过程。 图像分割是图像处理与计算机视觉领域的一个难题，尽管它一直受到科 研人员的重视和研究，但是他的发展仍然十分缓慢，近年来研究人员不断的 改进原有的图像分割方法并将其它学科领域的新理论和新方法引入图像分割 领域，从而提出了不少的新的分割方法。 常见的图像分割方法有：阈值法、边缘检测法、区域生长法、聚类分析 法、基于图论的图像谱分割方法等。其中阈值法是一种比较常用的图像分割 方法，它的实质是根据图像的灰度直方图中波峰、波谷的位置得到用于图像 分割的阈值，根据现有的研究，阈值法分为全局阈值法和局部阈值法两种。 基于边缘检测的图像分割方法是通过检测出不同区域的边缘来进行图像的分 割，所谓的边缘就是那些与周围的像素之间有灰度值的阶跃性变化的像素的 集合，这种阶跃性变化通常情况下会出现在目标与背景之间，基于边缘检测 法的图像分割技术正是根据这种像素间灰度值的阶跃性变化来进行图像分割 的。区域法利用像素的局部空间信息对图像进行分割，将具有相似特征的像 2 哈尔滨t 程大学硕十学位论文 素集合起来构成区域，目前比较成熟的区域法有：区域生长法和分裂合并法。 虽然已经出现了很多的图像分割方法和技术，但是到目前为止这些图像 分割的方法和技术都只是针对某一具体问题或某类具体图像而言的，仍然没 有一种图像分割的方法和技术能够适用于所有的图像，而且也没有一种统一 的衡量指标或函数用来说明某一种图像分割的方法或技术的好坏。因此，很 多计算机视觉领域的学者们正在不懈的在该领域进行研究。近年来人们把图 论的一些技术和知识引入了图像分割领域，后来出现了图像的谱分割技术， 由于该技术具有非常优越的分割性能，而逐渐受到人们的广泛关注和重视。 随着谱分割技术的发展，归一化割( n o r m a u z e dc u t ，n c u t ) 算法在1 9 9 7 年诞生， 该算法是由s h i 和m a l i k 共同提出的一种无监督自动阈值检测的图像分割技 术。n c u t 算法是利用区域内部的相似性来归一化区域之间的分离性，使得区 域内的相似性最大，而区域间的相似性最小。近年来，该算法由于其显著的 分割效果在图像处理及相关的领域中得到了广泛的使用。 该方法的出现使得图像分割领域又有了进一步的跨越性的发展，对该技 术的研究和改进，能够提高图像分割效果的精确度，从而使分割出来的人们 感兴趣的目标更加清晰准确，使下一步的图像理解、分析成为可能。 综上所述，对基于图论的图像谱分割技术的算法的研究具有很重要的应 用前景和研究价值。 1 3 基于图谱理论的图象分割技术的研究现状 近年来图谱划分理论作为一种新兴的图像分割工具逐渐受到世人的广泛 关注和重视，基于图论的聚类优化问题的研究始于2 0 世纪6 0 年代，而在图 像的处理与分析方面的应用是在2 0 世纪8 0 年代以后。它的基本思想是将目 标图像看成一个无向带权图，该无向图中的每一个节点代表原始图像中的一 个像素或区域，连接每两个节点之间的边的权值表示这两个节点属于同一个 区域的可能性，权值的大小取决于结点之间的相似性、临近性以及相连续性。 根据图的某种特定划分建立相应的能量函数，该能量函数的最小值即对应图 3 一 哈尔滨下程大学硕士学位论文 像的一个最佳分割。依据这一思想，研究者提出了各种图谱划分准则，其中 比较有代表性的图谱划分准则有：最小划分1 1 l 、平均划分1 2 l 、归一化划分l a l 、 比例划分1 4 1 等等。 一、国外研究现状 从2 0 世纪9 0 年代至今，国际上出现了众多对基于图谱理论的图像分割、 图像聚类等技术的分析与研究。这些技术的一个共同的主题是加权图的形式 与构造方法，加权图的每一个节点对应于图像中的每个像素或者小区域，加 权图的每一条边被赋予一个权值，这个权值是通过对属于同一分割中的与该 边相关联的像素或区域的一致性来测量的，这里的一致性包括( 相似性、临近 性以及相连续性) 。通过使图的划分过程中节点的特定代价函数最小化，将图 分割成不同的组成成分，分割过程是一个递归二元分裂过程，直到满足某种 结束条件而结束分割。 图的邻接矩阵的谱即图的邻接谱的研究至今为止已经有相当长的历史， 而且已经形成了一系列相对成熟的理论。图的邻接谱在量子化学研究领域首 次被提出，该理论是1 9 3 1 年由e h u c k e l l n 在对非饱和碳水化合物的一种近似 处理的过程中产生了对相应分子的图论模型，然后将图论模型映射到标准特 征空间，用标准特征空间中的特征值表示特定电子的能量级。很多年以后， e h u c k e l 模型与图谱的数学理论之间的联系才开始受到后人的关注，并且被 众多的研究者广泛的开发利用，现在该理论已被成熟的应用到图像的分割领 域，而且分割效果非常理想。在图像分割领域最早明确提出研究图的邻接谱 的是l e o l l a t z 和u s i n g o g o w i t z l 0 1 ，后来在1 9 世纪6 0 年代，h s a c h s 和 a j h o f f i n a n 提出的文献1 7 1 中也提到了对图的邻接谱的应用。到了1 9 世纪7 0 年代，在d c v e t k o v i & l 的博士论文中引用了大量的参考文献，这些文献都涉 及图的邻接矩阵的特征值，即图的邻接谱。1 0 年后，几乎所有的涉及图的邻 接谱的结论都被收到( ( s p e c t r a o f g r a p h s ) ) 这本书中。该书是由d c v e t k o v i c ， m d o o b 和h s a c h s 一起编写的。这本书包含了从1 9 6 0 年到1 9 7 8 年之间一共 将近六百篇的与图的邻接谱相关的参考文献。后来为了进一步研究图的邻接 4 一 哈尔滨下程大学硕士学位论文 谱，在1 9 8 8 年，d c v e t k o v i c ，m d o o b ，i g u t m a n 和a t o r g a s e v 一起合著 r e e e n t r e s u l t si nt h et h e o r yo f g r a p hs p e c t r a ) ，这本书总结了1 9 7 8 到1 9 8 4 年之间关 于图的邻接谱的研究的一些理论，并且提供了超过七百篇的来自于数学和化 学领域的相关文献，同时，该书还收录了来自其他领域( 例如，临床医学、社 会科学、机械工程、物理、地理、航海等) 的相关参考文献。关于图的邻接谱 理论近年来的发展，在1 9 9 5 年出版的d c v e t k o v i c ，m d o o b 和h s a c h s 的第 三版著作( s p e c t r ao f g r a p h s ) 中有着详尽的阐述。 图的l a p l a c e 谱是图谱理论中的另一个重要的研究领域。由于图的l a p l a c e 矩阵与数学、物理中的l a p l a c e 算子离散化形式有着紧密的联系，因此从某种 意义上讲，图的l a p l a c e 谱的研究比邻接谱的研究具有更加重要的意义。 l a p l a c e 矩阵一词最早是1 8 4 7 年k i r c h h o f f 9 在研究电流理论时发现的矩阵树 定理中提到的；研究l a p l a c e 特征值与图的不变量之间的联系的早期经典著作 是由f i e l d l e p l o l 编写的。1 9 8 5 年，a n d e r s o n 和m o r l e 少l - l 第一次对l a p l a c e 矩阵 的最大特征值进行了估计，此后，m e r r i s 2 j ，m o h a r l l 3 1 等人对l a p l a c e 矩阵的 特征值作出了更具有科学依据的新的估计，并提出了一些新的问题和猜想。 后来f r i c c h u n g 在1 9 9 4 年瑞士召开的数学家大会上的报告中将l a p l a c e 矩 阵的研究推向了一个新的层面。图g 的l a p l a c e 矩阵l 和邻接矩阵彳 相比，由于在定义l a p l a c e 矩阵时引入了顶点的度，因此与图的邻接矩阵特 征值相比l a p l a c e 特征值更能反映图的结构性质，所以l a p l a c e 特征值的研究 越来越受到人们的关注和重视。 此外，图本身的一些重要的不变量，例如：图的最大割( m a x c u 0 、等周 数等，除了能够反映图的一些结构性质外，还有很多更加广泛的应用。然而， 引入这些不变量后算法的复杂度在一定程度上有所增加，而图的f 邻接矩阵或 l a p l a c e 矩阵) 特征值可以通过多项式渐进求根理论求得，而且到目前为止该 理论已经比较成熟和完善。因而，建立图的代数不变量( 图的谱) 与图本身的 不变量之间的联系，是非常重要也十分有效的。 从2 0 世纪6 0 年代末以来，h s w i l f 和a j h o f f m a n l b 】提出了用特征值来 5 一 一 表示 1 9 7 9 另外 展图 的等 非随 面发 究热 域作 本质 数据 阶段 数作 以及 一种 性， 为图 带权 图中 权值 划分 除了 分准 一 声 ， 哈尔滨t 程大学硕+ 学位论文 法的实时性比较差，因此在很多实时视觉处理领域无法得到广泛的应用。为 了解决这一问题，本文提出了一种改进的基于图谱划分的多阈值分割算法， 该算法是一种无监督的自动阈值分割方法，用图谱划分测度作为阈值分割的 准则来区分目标和背景。该方法首先对目标图像进行预分割，然后将预分割 中得到的各个小而连续的区域看做一个节点，连接每两个节点的权值反映了 这两个节点隶属于同一个区域的可能性，同时为了减少算法的时间复杂度和 空间复杂度本文采用的是基于图像灰度级的对称矩阵职其大小远远小于2 5 6 x 2 5 6 ) 来描述图像中各个部分之间的关系，而不是采用j v x j v ( j v 为图像中像 素的个数) 的对称矩阵肌本文所提出的方法的优点是利用简洁的特征系统的 求解，代替对复杂的原始图像相关信息的处理，从而大大减少了算法的时间 复杂度和空间复杂度，提高了算法的实时性。仿真结果表明，该算法对于背 景不是很复杂的图像有很好的处理结果，对于这类图像采用本文的方法进行 图像分割将会更加有效。 1 4 论文的主要工作及论文的结构 本论文的主要工作介绍如下：本论文提出了一种基于谱分割技术的多阈 值分割方法，首先将采集到的标准彩色图像转换成灰度图像，对灰度图像求 解对应的灰度直方图，由于一维灰度直方图仅仅涉及到图像像素的灰度信息， 为了引入图像像素的空间坐标信息，本文对图像的每个像素求解邻域灰度均 值，然后根据像素原始灰度值与邻域灰度均值的比例关系构建图像的二维灰 度直方图。在二维灰度直方图的基础上，采用k - 均值( k - m e a n s ) 聚类分析法 先对图像进行预分割，将分割得到的各个小而连续的子区域作为节点，构造 带权无向图。对构造的无向图采用n c u t 准则进行分割。具体做法是：为图 像图中连接每两个节点的边赋予权值，该权值用来表征这两个节点属于同一 个类的可能性。然后，将带权无向图的权值矩阵映射到标准特征空间，在标 准特征空间中求解特征值，将特征值排序，寻找次小特征值对应的特征向量， 利用该特征向量的性质指导原始图像的分割。计算此次分割的n c u t 值，将 7 哈尔滨t 程大学 n c u t 值与预先给定的初始值进行比较， 续进行分割则重复进行以上过程，直到 本论文的结构一共由五部分组成， 第1 章为绪论，首先介绍了图像分 究现状。然后，主要介绍了几种常见的 的方法等等。最后，则介绍了本文的章 第2 章图谱理论及割集准则，主要 阵、l a p l a c i a n 矩阵、邻接矩阵、图像连 方法等。同时，介绍了图谱理论中常用 致的比较。最后，将图像的分割引入特 种割集准则对图像进行分割。 第3 章基于图谱理论的多阈值分割 算法，然后详细介绍了本文所提出的基 第4 章实验结果的分析，首先通过 效果以及分割数据的分析，证实本算法 对该类图像采用本文的算法进行图像分 过对一致性测量函数的计算数据的分析 及实时性。 最后是总结与展望。 8 哈尔滨下程大学硕十学位论文 第2 章图谱理论及割集准则 计算机视觉是一门发展非常迅速的学科，到目前为止，己经形成了从最 初的图像获取到最终的目标图像分割、提取、显示等较为完整的体系。经过 计算机图像图形学领域的诸多学者们多年的研究扩展，计算机视觉在飞机导 航、遥感气象、机器人定位、精密工业测量、目标识别、虚拟现实以及医学、 军事、航海、航空等领域的应用越来越广泛，图像处理方法从早期的粗略的 图像匹配即以统计学的相关理论为基础的图像匹配，发展到今天精细的特征 匹配即具有很强的生理学背景的图像匹配，从计算机串行视觉处理发展到计 算机并行视觉处理，从低层视觉处理即仅依赖于输入信号的视觉处理，发展 到高层视觉处理即同时依赖于特征、结构、关系和知识的视觉处理，图像处 理的效果在一步步的逐渐提高，该领域的理论正处在不断发展、不断壮大与 完善的过程之中。近几年来，一些计算机图形图像学领域的研究者将图谱理 论引入计算机视觉的相关问题的研究之中，并且效果显著。 目前基于图论的图像谱分割技术研究的几个主要焦点为：谱方法的应用； 快速算法的设计；最优剪切准则的设计；其它图论分割方法的提出。 2 1 图谱理论 图像的谱分割技术近年来在图像分割领域表现出了良好的发展前景。早 期的图像谱分割技术的总体思想是：将原始图像映射为无向带权图，把图像 中的像素视为无向图中的节点，用相应的相似度距离公式计算任意两个节点 的距离，将计算得到的结果作为连接两个节点之间的边的权值，再利用相应 的图谱划分准则得到图像的最佳分割。 图谱理论主要涉及图的邻接( 矩阵的) 谱和图的l a p l a c e ( 矩阵的) 谱，是图 论特别是组合矩阵论和代数图论共同关注的一个重要课题。图谱理论研究的 主要途径是：通过图的矩阵可以是邻接矩阵也可以是l a p l a c e 矩阵来表示图 的拓扑结构和图的置换相似不变量之间的联系，通过将矩阵论特别是组合矩 q 哈尔滨t 程大学硕士学位论文 阵论和对称矩阵理论以及非负矩阵理论中的经典结论用于图的拓扑结构的研 究，以推动后者的快速发展。 基于图论的图像分割准则主要有以下三种。 1 ) 基于区域合并的分割准则 基于特征向量的分割准则 3 ) 基于归一化割的分割准则 文献p 4 i 中对以上三种分割准则的分析与比较如下表2 1 所示： 表2 1 三种图像分割准则的比较 分割准则算法复杂度优缺点纹理处理不确定参数 特征向量较高聚类不够紧简单处理分类个数c 密 归一化割很高难以判断分效果较好，已分割结束点r 割结束点经投入应用 区域合并较低过分割目前还未有阈值函数中 研究的参数k 以上三种图像分割准则中，基于特征向量的分割准则由于其聚类不够紧 密、对纹理的处理效果不够好不如基于n c u t 准则的分割准则，而n c u t 准则 则与基于区域合并的分割准则各有优缺点，但是从实际的应用层面上来说， 基于n c u t 准则的分割算法在算法复杂度方面有着一定的优势。在日后的研 究中，可使用n c u t 准则进行初始分割，然后引入其它的附加准则，例如，借 鉴另外两种分割准则，把分割得到的连通区域作为一个整体的节点继续进行 分割，从而避免欠分割。也可在分割进行到一定阶段后引入纹理信息进行处 理，这些应是以后所要研究的方向。 一、图的最优划分准则 设一个无向带权图a - ( v , o ，其中矿是图中所有节点的集合，e 是图中 边的集合，节点集v 的基为n = i v l ，将图g 通过删去某些边而划分成互不连 接的a 、b 两个部分，且这两部分满足au b = v , ar i b = 巾两个条件，w m ，v ) 1 0 哈尔滨t 程大学硕士学位论文 是为连接每两个节点的边均赋予的权值，用来衡量节点u 和l ，的相似度，也 就是属于同一块区域的可能性。彳、曰两个部分的不相似程度，即分离度可以 定义为：原先连接这两部分而现在删去的那些边的权值之和，这个分离度在 图论中被称为割( c u t ) ，定义如下1 1 5 l ： c u t ( a ，丑) ；w ( u ， ，)( 2 - 1 ) | i e 矗胁 图的最优二元划分就是满足上述割值最小的划分，称为最小割集准则 ( m i n i m u mc u t ，简称m c u t ) 。 二、图像的最佳分割 将图像的分割看成图的聚类分析问题，根据这一思想将一幅图像看成一 个带权的无向图g = ( 儿d ，图像中的像素集被看成是图中的节点集 图像 中物体的边缘被看成是图中的边集e ，图g 中节点之间的连接权为w ( i j ) ，它 表示该边所连接的两个节点撕属于同一个区域的可能性，w ( i j ) 的大小与这两 个点的连续性、邻近性等信息相关。文献1 1 6 1 将图像二值划分为两个集合( 区 域，曰的代价函数为： c u t ( a ，b ) ；w ( i ，_ ) ( 2 2 ) 瞎砑- b 对于一幅图像来说，使得上述代价函数取值最小的划分即为图像的最佳 分割。 三、相似度矩阵、度矩阵、邻接矩阵、l a p l a c i a n 矩阵的定义 基于图论的图像分谱割技术常常把对最优割集准则的计算转化为求解相 似度矩阵或l a p l a c i a n 矩阵所对应的特征空间中的特征值以及相应的特征矢 量的问题。 带权无向图g 的相似度矩阵通常用职g ) 来表示，又称为亲和力矩阵 ( a f f i n i t y ) 。将原图像中像素的一个排列作为相似度矩阵中元素的序列，通过 相似度函数计算得到相似度矩阵中每一个元素的值，该值即为连接节点之间 的边的权值。 哈尔滨t 程大学硕+ 学位论文 将相似度矩阵每行元素相加求和即得到相应节点的度，用所有节点的度 建立的对角阵称为度矩阵，带权无向图g 的度矩阵常用d ( g ) 来表示。 带权无向图g 的l a p l a c i a n 矩阵为( g ) ，它的计算公式为 l ( g ) ；d ( g ) - 职g ) ，在图论分割算法中l a p l a c i a n 矩阵是常用的标准矩阵。构 造一个图的l a p l a c i a n 矩阵的公式如下1 1 7 1 ： f a ui f ( v j ，) e k i ； d e g ( h ) f = j( 2 3 ) 1 0o t h e r w i s e 其中，a 6 j 为边e “的权值，d e g ( v i ) 为点v i 的度。l a p l a c i a n 矩阵的最小特 征值为零。如果图g 是一个连通图，则l a p l a c i a n 矩阵的所有特征值都大于 零，如果图g 不连通，则l a p l a c i a n 矩阵特征值中零的个数代表了图g 的连 通分支数，并且零特征值对应的特征向量中的各分量只有两种值，其中的某 一个数对应的点集就是不连通图g 所对应的连通分量。 带权无向图g 的邻接矩阵用彳( g ) 表示，它用一个二维数组来表示带权无 向图g 中顶点间的相邻关系。设带权无向图g = ( ”司，有n 个顶点，即- i 卅= ，l ， 其中咒1 ，图g 的邻接矩阵彳是一个n 阶方阵，该方阵的表达式如下： r 1 e e l 旷t o - ， 对于灰度图像来说，r 的值是图像中像素的灰度值，墨的值是像素的空 间坐标，矿，的值是灰度高斯函数的标准方差，口z 为空间距离高斯函数的标 准方差，烈f ，f ) 是两个像素之间的实际距离，是两个像素之间的有效距离， 若实际距离超过了有效距离则认为两个像素之间的相似度为0 ，l i 0 ：表示一 个矢量的二范数，此相似度函数认为两个像素之间的灰度值越接近像个像素 之间的相似度越大，同时两个像素之间的距离越接近则其相似度也越大。 一、特征空间的选择 1 ) 距离特征空间的选择，在本论文中选取的是像素的欧式空间坐标值。 亮度特征空间的选择，在本论文中选取的是像素的灰度值( 0 - 2 5 5 ) 。 3 ) 颜色特征空间的选择，r g b 彩色空间的r 、g 、口，三个分量并不是 一个很好的选择，因为r g b 的欧氏空间距离和实际的颜色差异并不 一致，为了解决这个问题，姜侃等人使用了h s v 空间作为颜色特征 空间旧，但从实际应用的效果来看l 口6 空间最接近人眼的感觉； 4 l 纹理特征空间的选择是一个相对复杂的问题，首先没有已知的标准 纹理基元集合，这使我们无法取得各个分量，其次常见的基于统计 信息的方差、能量、熵等信息量不能准确的表现某一点的纹理特征。 一个比较理想的做法是采用一系列滤波器：五，厶。对某特定空间( 例 如：以当前像素点为中心的四邻域或八邻域) 进行滤波，滤波器的 输出厂作为纹理特征空间，对于特定的滤波器来说，输出可以用来 估计局部信息尺度( 例如：四邻域或八邻域) 中各项异性的对比度【1 8 l 。 像素点之间的权函数的选取就是对以上几个特征空间的综合考评。 哈尔滨丁程大学硕+ 学位论文 二、势函数、f i e d l e r 矢量以及谱的定义 势函数是用来表示某个像素划分归属的指示矢量( i n d i c a t o rv e c t o r ) 其具体 定义为： 门f a x l 。 of圣彳(3-5) 若最终的势函数中某像素对应的值为1 ，则表示该像素属于集合彳，若 为o 则表示该像素属于集合b 。但是实际的图像划分所求得的结果中麓常常 是【0 ，1 】之间的一个实数此时可以采用k - m e a n s 聚类等方法进一步决定像素的 归属。 许多的图论分割算法将图的划分问题转化成求解下述方程的第二小特征 矢量问题： 1l d 2 p w ) d 2 z1 缸 ( 3 - 6 ) 这里的第二小特征矢量为第二个最小特征值对应的特征矢量，它代表了 最佳图划分的一个解即势函数。通常把这个特征矢量称为f i e l d e r 矢量。与特 征矢量( 不一定是f i e l d e r ) 所对应的特征值称为谱。 m x n 矩阵a = ( a i j ) ，其中a i i c ，当m - - n 时称为r l 阶方阵，五是n 阶方阵彳 的特征值，如果存在非零咒维列向量使得a x = 2 x ，则z 称为彳的与特征值a 对应的特征向量。由公式a x = l y 可知a 是多项式x a ( 2 ) = d e t ( m n - a ) 的根，这里 厶是n 阶方阵，张a ) 称为么的特征多项式，是关于九的n 次多项式。由高斯 定理可知：特征方程翰q ) = 0 有以个根，分别是a j 如 ，因为这珂个根不一 定互异，我们把重集 2 1 2 z ) 称为谱( s p e c t r u m ) ，记为s p e c a ，这里屯如 互异，m ，是九的代数重数，而 所对应的所有特征向量加上零向量构成一个 线性子空间，称为与九相对应的根子空间，也就是公式。4 壮j y 所决定的齐次 方程组的解空间，它的维数是： 珂r a n k ( 2 i l n - a ) ，称为特征值九的几何重数。 三、常用的权函数公式 文献l l l 中闫成新等人指出常用的谱分割的权函数公式有如下两种： 哈尔滨丁程大学硕十学位论文 w = i ，f 一，1 w 驴一卅学， ( 3 忉 ( 3 - 8 ) 公式( 3 7 ) 和( 3 - 8 ) 中的这两个权函数只涉及到了图像的灰度信息，没有考 虑像素的空间位置信息，为了在权函数中引入像素的空间坐标信息。本文借 鉴了文献 s 8 1 中谢明霞等人介绍的n c u t 权值的计算方法： 令肚 ( f d ；i = 0 ，1 ，n h - 1 ；y = o ，1 ，n w - 1 ) 上= o ，1 ，2 5 5 ，其中n h 和玎w 分别表示图像的高度和宽度，令雕) 为图像在像素g ) 处的灰度值，则y 和 触，y ) 满足如下条件： ，o ，y ) e l ，v ( x ，y ) e v ( 3 - 9 ) 圪- ，y ) ：厂 ，y ) ，七， ，y ) e v ，ke l( 3 1 0 ) 2 5 5 u v , 一y ，v jn v k z e p ，k y , k ，j e l0 1 1 ) 如果将图像中的每个像素看作一个节点，每对节点均用一条边连接起来， 为每条边赋予一个权值，边的权值反映这两个像素属于同一个子类的可能性， 那么我们就可以利用像素的灰度值以及它们的空间位置，构建一个带权的无 向图g = ( 以曰。将图像中像素的灰度信息和空间坐标信息一同引入无向图g 中得到的权值计算公式为： w ( i 9j ) ；e x p ( 一j i ! 二g 掣一旦三! 堡羔掣) ( 3 - 1 2 ) a ta x 该权函数，同时涉及到图像的灰度信息和空间信息，使得处理的结果更 加准确。 哈尔滨工程大学硕十学位论文 3 5n c u t 算法 3 5 1n c u t 简介 本文借鉴了文献1 2 3 1 中陶文兵等人提出的一种改进的n c u t 算法，该算法定 义图g 中连接两个节点i 和的边的权值如下嘲： 吣护 一 警：警】 其中五是节点i 的空间位置，f f 是节点f 的灰度值，口工是距离空间高斯 函数的标准方差，口，是灰度空间高斯函数的标准方差，i i 1 1 2 标示一个矢量的 二范数，r 是两个像素之间的有效距离，他决定了参与计算权值的领域节点 的个数，随着，取值的不断增加参与计算权值的节点个数也不断增加，同时 算法的时间复杂度也相应增加，最终得到的分割结果的精确度也会得到提高。 超过有效距离的两个像素之间的相似度为o 。该灰度函数既考虑了距离特征 空间的特征又兼顾了亮度特征空间的特征，我们认为两个像素之间的灰度值 之差越小那么它们的相似度也就越大，同时，两个像素之间的距离之差越小 那么它们的相似度也越大。 根据文献1 2 3 l 对于任意门限“o f 2 5 5 ) 我们都可以得到图像相对应的图 g = ( 啊) 的一个二元划分跆似丑，可以使类内相似度最大，类间相似度最小， 这样得到的图像分割效果较好。公式中的彳和b 可分别表示为 r2 5 5 a = u v + ，b = u k ，k e l ( 3 1 4 ) k - 0k - t + l 将上式代入公式，通过转换可知： 3 7 、， 31 - 0 r r s 卜 、-，、j-， ， ， 疗：， u d d 哈尔滨工程大学硕十学位论文 c 以似，b ) 坐 ) 。荟( 荟w )l i 舶为为 = 骞啦驴v ，】 ( 3 - 1 5 ) 一斛荔叫 ，2 盛，2 骞套l 露叫 回 口s s o c ( b , b ) | 一：w ( u | v ) 1 ；善2 5 5 引2 5 5 馨】 。彻 伽形，_ ) 2 搿( 3 - 1 s ) 我们假设( 3 - 1 8 ) 式表示k 中所有节点( 灰度值为z ) 与嵋中所有节点( 灰度值 为- ) 之间的总的连接权值之和，于是公式( 3 - 1 5 ) 、( 3 1 6 ) 、( 3 - 1 7 ) 可以转化为： 翻f 似，b ) 。荟荟- 甜形，_ ) ( 3 - 1 9 ) 一c ，彳) 2 荟善c 矧彤，_ ) ( 3 2 0 ) 掷。c ( 曰，b ) 2i 1 l - 。c 甜形，v j ) ( 3 - 2 1 ) 同时可证以下公式成立： a s s o c ( a ，y ) = a s s o c ( a ，彳) + c u t ( a ，b )( 3 - 2 2 ) a s s o c ( b ，y ) = a s s o c ( b ，b ) + c u t ( a ，丑)( 3 - 2 3 ) 于是n c u t 的定义式为： 胁f 似，b ) 一忑而c u 万t ( a 丽, b )+ 忑丽