（电路与系统专业论文）基于图论的彩色图像分割方法研究[电路与系统专业优秀论文].pdf

华南师范大学( 】4 级顺f 研究生学位论文 彩 论是中 割，冉 将直接 像分割 像分割 甚 法之一 个无向 就完成 要有两 ( m i n i 本 都进行 了一种 于传统 造过程 可分割 复上述 实验证 果。 色图像分割是几乎 层的图像分析，还 进行后面的特征提 影响其后的中、高 方法一直是图像领 仍然是一个没有得 于图论的彩色图像 。一般而言，图论 图的最优化问题， 了对原彩色图像的 种：最小生成树( 摘要 所有中、高层彩色图 是高层的图像理鳃， 取、模式识别等工作 层处理工作的成败。 域的研究重点。但是 到很好解决的问题。 分割方法是目前效果 方法是将原来的彩色 运用图论的算法实现 分割。目前基于图论 m i n i m a ls p a n n i n gt r e e 摘要， 像处理工作的基础。无 都需要先对图像进行分 。而且图像分割的质量 因此，高质量的彩色图 直到目前为止，彩色图 最优的彩色图像分割方 图像分割问题转化为一 对无向图的最优化，也 的彩色图像分割方法主 ) 与最小割 m i z e d c u t ) 。 文对两种基于图论的彩色图像分割方法一最小生成树和最小割 了较深入的研究。其中，第一种方法一最小生成树，本文提h 利用最小生成树的局部闽值实现彩色图像分割的方法，它不唰 的最小生成树的全局闽值方法。该方法通过考查最小生成树构 中的区域一致性变化，计算出一个局部闽值，利用该局部阈值 出原彩色图像中的两个最终区域。对于图像中的剩余区域，重 过程继续进行分割，直至原图像中所有的区域都被分割出来。 明，本文的局部阈值方法比传统的全局阂值具有更好的分割效 第二种方法一最 ( n o r m a l i z e dc u t ) ， 点。但归一割的最 p o l y n o m i a lc o m p l e t e 小割，利用最小割的修正 可以克服最小割易于分割 小化问题是一个n p 完备( ) 问题，人们一般只能得到 形式一归一割 出图像中的孤立点的缺 n o n d e t e r m i n i s t i c 它的近似解。最近有人 针对灰度图像的分割提出一种模糊迭代的归一割方法，巧妙地回避了 求解归一割最小化的问题。本文主要研究利用这种方法解决彩色图像 l 华南师范人学0 4 级硕卜研究生学位论文 摘要 分割的问题，包括：在彩色空间下选取一一种合适的相似性度量，以及 用单链表的运算代替矩阵运算来计算归一割。实验证明，本文设计的 方法能较好地应用于彩色图像分割。 关键词：彩色图像分割；图论；最小生成树；最小割；归一一割 华南帅范人学0 4 级顾i ：研究生学位论文 a b s t r a c t a b s t r a c t c o l o ri m a g es e g m e n t a t i o n i st h eb a s i so fa l m o s ta l lt h em i d l e v e la n d h i g h - l e v e l w o r k so fc o l o ri m a g ep r o c e s s i n g w h e t h e ri nt h em i d l e v e lw o r k so f i m a g ea n a l y s i s ，o ri nt h eh i g h l e v e lw o r k so fi m a g eu n d e r s t a n d i n g ，t h ep r o c e d u r eo f i m a g es e g m e n t a t i o ni sa l w a y sc a r r i e do u t a st h ef i r s ts t e p ，f o l l o w e db yo t h e rs t e p s s u c ha sf e a t u r ee x t r a c t i o n ，p a t t e r nr e c o g n i t i o n ，e t c m o r e o v e r ，t h eq u a l i t yo fi m a g e s e g m e n t a t i o nw i l l # v e ad i r e c ti n f l u e n c eo nt h er e s u l to fi t ss u b s e q u e n t i a ls t e p s t h u s ， s t u d i e so fh i 曲q u a l i t yc o l o ri m a g es e g m e n t a t i o nm e t h o d sh a v ea l w a y sg a i n e dal o t o fa t t e n t i o ni nt h ef i e l do fi m a g ep r o c e s s i n g h o w e v e r ，s of a rt h ep r o b l e mo fc o l o r i m a g es e g m e n t a t i o nh a sn o tb e e nw e l ls o l v e dy e t c o l o ri m a g es e g m e n t a t i o nm e t h o d sb a s e do ng r a p ht h e o r y a r ea m o n g t h o s es o l u t i o n s t h a th a v ea c h i e v e db e s tp e r f o r m a n c e i ng e n e r a l ，t h i sk i n do f m e t h o d st r a n s f o r m st h ep r o b l e mo fi m a g es e g m e n t a t i o n i n t o t h ep r o b l e mo f g r a p ho p t i m i z a t i o n ，a n dr e a l i z e si m a g es e g m e n t a t i o nb y o p t i m i z i n gt h eg r a p hu s i n g g r a p ht h e o r y t h e r e a r em a i n l yt w ot y p e so ft h i sk i n do fm e t h o d s - m i n i m a l s p a n n i n gt r e e ，a n dm i n i m i z e dc u t b o t ho ft h et w ot y p e s m i n i m a ls p a n n i n gt r e ea n dm i n i m i z e dc u ta r e d i s c u s s e di nd e t a i li nt h i st h e s i s f o rt h ef i r s tt y p e - m i n i m a ls p a n n i n gt r e e ( m s t ) ， an e wm e t h o do f s e g m e n t i n gc o l o ri m a g e su s i n g l o c a lt h r e s h o l d si sp r o p o s e d u n l i k et h et r a d i t i o n a lm e t h o d st h a te m p l o yag l o b a lt h r e s h o l d ，t h ep r o p o s e d m e t h o dc a l c u l a t e sal o c a lt h r e s h o l d d u r i n gt h ep r o c e s s o f c o n s t r u c t i n gm s t ， a c c o r d i n g t ot h ec h a n g eo f h o m o g e n e i t i e so fm e r g i n gr e g i o n s t h e nb yu s i n g t h i sl o c a lt h r e s h o l d ，t w of i n a lr e g i o n sc a nb es e g m e n t e df r o mt h eo r i g i n a li m a g e t h ea b o v ep r o c e s si sr e p e a t e dt os e g m e n tt h er e m a i n i n gr e g i o n s i nt h eo r i g i n a l i m a g e ，a n ds t o p sw h e nn or e g i o nr e m a i n s e x p e r i m e n t ss h o wt h a t t h ep r o p o s e d m e t h o di ss u p e r i o rt ot h et r a d i t i o n a lo n e s f o rt h es e c o n dt y p e m i n i m i z e dc u t ( m i n c u t ) ，i t sm o d i f i e df o r m ， n o r m a l i z e dc u t ，c a nb eu s e dt oo v e r c o m et h ed r a w b a c ko fm i n c u tt h a tf a v o r st o i n 华南师范人学0 4 缓坝f 研究生学位论史a b s t r a d s e g m e n t i s o l a t e dp i x e l s b u tt h ep r o b l e mo f m i n i m i z i n g n o r m a l i z e dc u ti s n o n d e t e r m i n i s t i c p o l y n o m i a lc o m p l e t e ( n pc o m p l e t e ) ，a n do n l y t h e a p p r o x i m a t i o nt o i t ss o l u t i o n sc a nb eg o t t e n r e c e n t l ys o m e o n e p r o p o s e daf u z z y i t e r a t i o nm e t h o do fn o r m a l i z e dc u tt o s e g m e n tg r a y l e v e li m a g e s ，w h i c h s t r a t e g i c a l l ya v o i d e d t h en pc o m p l e t ep r o b l e mo fm i n i m i z i n gn o r m a l i z e dc u t i n t h i st h e s i s ，am e t h o do f u t i l i z i n g t h ef u z z yi t e r a t i o nm e t h o do fn o r m a l i z e dc u tt o s e g m e n tc o l o ri m a g e s i sd e v i s e d ，i n c l u d i n gc h o o s i n gp r o p e rm e a s u r e m e n to fc o l o r s i m i l a r i t y ，a n du s i n gl i n e a rc h a i n i n s t e a do fm a t r i xt oc a l c u l a t en o r m a l i z e dc u t e x p e r i m e n t ss h o wt h a tt h ed e v i s e dm e t h o dw o r k sw e l lo ns e g m e n t i n gc o l o ri m a g e s k e y w o r d s ：c o l o ri m a g es e g m e n t a t i o n ；g r a p ht h e o r y ；m i n i m a ls p a n n i n gt r e e ； m i n i m i z e dc u t ；n o r m a l i z e dc u t i v 华南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确的方式标明。 本人完全意识到本声明的法律结果由本人承担。 论文作者签名；彦内牵 日期：) 泖年，月扣日 学位论文使用授权声明 本人完全了解华南师范大学有关收集、保留和使用学位论文的规 定，即：研究生在校攻读学位期间论文工作的知识产权单位属华南师 范大学。学校有权保留并向国家主管部门或其指定机构送交论文的电 子版和纸质版，允许学位论文被检索、查阅和借阅。学校可以公布学 位论文的全部或部分内容，可以允许采用影印、缩印、数字化或其他 复制手段保存、汇编学位论文。( 保密的论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密范围，在- 年后解密适用 本授权书。非保密论文注释：本学位论文不属于保密范围，适用本授权 书。 论文作者签名：杏匈牵 日期：唧年f 月扣日 导师签名： 日期：砷年，月；p 日 日期：二一f 年j 月；p 日 t 一1 华南师范人学0 4 级坝f 研究生学位论文 第一章绪论 第一章绪论 1 1 彩色图像分割的研究背景 在过去的十多年中，随着彩色技术的进步，彩色图像工程得到了 迅速发展。彩色图像工程主要包含三个层次1 1 1 ：图像处理，图像分析 和图像理解。其中，图像处理是低层操作，它的特点是输入、输出都 是图像。典型的图像处理工作有：图像增强。图像分析是中层操作， 它的特点是输入为图像，而输出是对图像特征的描述。典型的图像分 析工作有：模式识别。图像理解是商层操作，它的特点是输入为图像 特征，输出是对输入特征的解释。典型的图像理解工作有：计算机视 觉。 彩色图像分割是彩色图像工程的中、高层操作中一个非常关键的 部分。因为无论是中层的图像分析，还是高层的图像理解，都需要先 对原彩色图像进行分割，再对分割结果进行特征提取、目标识别等工 作，分割的质量将直接影响其后的工作能否成功。因此，彩色图像分 割在彩色图像工程中占有重要地位。 彩色图像分割在各领域都有十分广泛的应用。在互联网的图像检 索中1 2 , 3 1 ，样本图像中感兴趣的区域被分割出来，用于在目标图像中 查找与其相似的区域。在图像编码中【4 ”，彩色图像被分割成不同的 对象区域并分别进行编码，从而实现码率压缩。在运动跟踪中1 6 1 ，需 要分割一系列的彩色图像序列以提取运动目标。在医学上1 7 , 8 1 ，皮肤 的彩色显微图像被分割为感染部分和非感染部分，用于进行皮肤癌的 诊断。在这些应用中，分割都是为了进一步对图像进行分析、识别， 分割的准确性将影响后面工作的有效性。因此，彩色图像分割的方法 至关重要。 1 2 目前彩色图像分割的主要方法 华南师范大学0 4 级顾i 。研究生学位论文第一章绪论 彩色图像分割的方法有许多，但它们一般都满足以下对于分割的 基本要求1 9 j ： 假设p ( ) 是一个一致性谓词，它定义在一组相互连接的象素上。 则：分割是将象素集合f 划分为一些相互连接的子集或区域 ，s ：，s 。) ，使得以下两式同时成立 旦s # f 且s i a s j 。中 ( 1 1 ) p ( s ) - t r u e 且尸( su s j ) 一f a l s e( 1 2 ) 式中，中为空集 f ，j l 2 ，胛且f j 式( 1 1 ) 表示原图像完全被分解为一些区域，并且这些区域是互不重叠 的。式( 1 2 ) 表示分割结果中的任一区域本身是具有一致性的，且它是 在当前一致性谓词下所能得到的最大区域，因为它与其他任何区域合 并后所产生的新区域将不具备一致性。 彩色图像分割的具体方法主要可分为以下几类： ( 1 )基于直方图的方法 基于直方图的方法认为：直方图中的每个峰值均对应于一个区 域，而位于两个相邻峰值之自j 的谷值则对应于区域的边界。因此，利 用直方图中所有的谷值可以确定一系列的阈值，这些阈值界定了原彩 色图像中各区域的颜色范围。通过将图像中的每个象素与这些阈值进 行比较，就可以确定该象素所在的区域，从而实现对各个区域的划分 o o - t 2 l 。 彩色图像需要考虑三个颜色分量，因此它的直方图应该是三维 的。然而，考查一个三维直方图是一项非常复杂的工作，因此人们通 常采用降维的方法，将三维直方图投影到二维或一维平面上，用考查 多个低维直方图来代替原来三维直方图l ”。”。 基于直方图的方法最直观，应用也最普遍。但它的主要缺点是只 考虑到图像的彩色信息，而忽略了象素之间的空间邻接关系，即分割 2 华南师范大学0 4 级硕卜研究生学位论文第一常绪论 仅在状态空自j 进行。因此，基于直方图的方法对噪声和区域颜色不均 匀比较敏感，它通常只适合于分割噪声很小、区域颜色均匀的彩色图 像。 ( 2 )基于边界的方法 基于边界的方法认为：象素的颜色在两个区域的边界上将会剧烈 变化，因此，可以利用边缘检测算子来寻找区域的边界，从而实现对 图像中各区域的划分。彩色图像边缘检测主要有两种方法：一种方法 是将彩色图像的三个彩色分量分别进行灰度边缘检测，然后将这三个 彩色分量的边缘综合起来得到原彩色图像的边界 1 s - 1 7 1 。常用的灰度边 缘检测算子有s o b e l ，p r e w i t t ，r o b e r t 和c a n n y 。另一种方法是直接对彩色 矢量进行边缘检测，这就需要事先定义一个矢量边缘检测算子p s - 2 0 l 。 通常第二种方法效果比第一种方法更好，但运算过程却复杂得多。 值得注意的是，利用基于边界的方法所得到的分割结果不仅包含 了彩色图像的真实边界，同时也包含了大量由噪声引起的伪边界。因 此，基于边界的方法一般不能单独用于彩色图像分割，它必须与其他 类型的方法( 如：基于区域的方法) 结合使用。 ( 3 )基于区域的方法 基于区域的方法认为：同一区域内的象素特性是相似的，而不同 区域之间的象素差别很大。因此，根据一些事先定义的相似度准则， 可以对图像中的象素进行分类，从而实现对图像中各个区域的划分。 基于区域的方法主要有两种：区域生长1 2 1 。l ，以及区域分离与合并 1 2 3 - 2 4 1 。区域生长是一个由底向上的过程。它仞始时在图像中确定若 干个象素作为种子点，并按照相似性规则将种子点与其相邻的象素合 并，构成了小区域。然后小区域以同样的相似性规则与其周围的象素 进行合并，逐渐构成大区域。这个过程一直进行，直到图像中全部象 素都加入其附近的区域为止。而区域分离与合并却是一个从顶至下的 过程。它初始时将整幅图像看成为一个区域。整个过程中，不满足一 致性条件的区域被分裂为四个区域，而满足一致性条件的四个相邻区 3 华南师范大学0 4 级硕f 研究生学位论文第一章绪论 域被合并为一个区域。重复此过程，直到无法进行分裂和合并时为 止。 基于区域的方法优点是对噪声不敏感，但它依赖于事先定义的某 个一致性条件。然而，在某些彩色图像中，却并不是所有区域都能用 一个相同的一致性条件来描述，此时基于区域的方法将会造成图像中 的某些区域过度分割。因此，它只适合于彩色图像中所有区域都满足 相同的一致性条件的情况。 ( 4 )基于特定理论工具的方法 基于特定理论工具的方法主要有以下几种：基于数学形态学的方 法，基于神经网络的方法和基于图论的方法。 基于数学形态学的方法主要利用一定形态的结构元素去度量和提 取图像中的对应形状，以达到对图像进行分析和识别的目的。典型的 形态学分割方法有：利用开操作和闭操作确定区域边界m “，以及利 用分水岭算法进行分割 z 6 - ”i，等。基于形态学的彩色图像分割方法 的优点是：定位效果好，精度高，抗噪性好。但其缺点是：要求根据 图像特征事先选取合适的结构元素。另外，利用数学形态学进行操作 比较耗时。 基于神经网络的方法是将原彩色图像分割的问题转换为一个能量 函数最小化的问题，该能量函数决定了神经网络的结构。目| ；i 用到的 神经网络主要有以下几种：h n n ( h o p f i e l d n e u r a l n e t w o r k s ) 。s o m ( t h es e l f - o r g a n i z i n gm a p ) p o l，和r c e ( r e s t r i c t e dc o u l o m be n e r g y ) 1 3 1 1 ， 等。基于神经网络的方法需要事先对神经网络的权值进行大量的训练 才能得到一个完整的网络，训练过程非常耗时。但利用训练好的神经 网络进行分割将会非常迅速、准确。 基于图论的方法是将原彩色图像分割的问题转换为一个无向图最 优化的问题。它将原彩色图像中的象素用无向图中的节点表示，象素 之间的关系用节点之白j 的边表示，由此可将原彩色图像映射为一个无 向图。无向图的最优化方法主要有两种：最小生成树( m i n i m a l 4 华南师范大学0 4 级硕l 研究生学位论文第一章绪论 s p a n n i n g t r e e ) l ”t “”1 和最小割( m i n i m i z e dc u t ) a 6 - “ 。最小生成 树是在无向图中寻找一条最短路径，该路径中的各连同分量对应于原 图像中的各区域。而最小割是在无向图中找出一个具有最小割的点 集，该点集及其补集将原图像分割为两个区域，在原图像中迭代地使 用最小割可分割出图像中所有的区域。基于图论的方法利用无向图表 示和组织图像，能够得到很好的分割效果。但它的缺点是求解无向图 最优化问题时耗时较大。 1 3 论文的研究内容及结构概要 在上述所有的彩色图像分割方法中，基于图论的方法是效果最优 的方法之一。基于图论的彩色图像分割方法比较新颖，目前国内对它 的研究还很少。本文对两种基于图论的彩色图像分割方法一最小生成 树( m s t ) 和最小割( m i n c u t ) 都进行了较深入的研究。其中，第 一类方法一最小生成树，传统方法一般采用全局阂值作为最小生成树 的终止条件。而本文主要研究了利用局部阈值作为终止条件的方法。 实验证明，局部阈值的方法比全局阈值能更好地分割出彩色图像中的 非均匀区域。对于第二种方法一最小割，在最小割的迭代问题上，最 近国外有人采用一种模糊迭代的方法对灰度图像进行分割，取得了很 好的效果。而本文主要研究利用这种模糊迭代的方法进行彩色图像分 割，并对不同类型的彩色图像进行了实验，给出了实验结果。最后， 本文以最小生成树和最小割这两种方法为例，对基于图论的彩色图像 分割方法进行了讨论和总结。 本文的结构安排如下： 第一章绪论。介绍了彩色图像分割的研究背景、目前主要的研究 方法以及本论文的研究内容。 第二章最小生成树实现彩色图像分割。介绍了图论中最小生成树 的基本原理。由于最小生成树常与分水岭算法结合使用，因此接下来 简单地介绍了分水岭算法的基本原理。最后回顾了传统的利用最小生 5 华南师范大学0 4 级硕l ：研究生学位沦义 第一章绪论 成树的全局阈值实现彩色图像分割的方法，并提出了一种利用最小生 成树的局部阂值实现彩色图像分割的方法。 第三章最小割实现彩色图像分割。介绍了图论中最小割的基本原 理以及最小割的修正一归割。由于归一剖的最小化是一个n p 完备 问题，求解它是很困难的，一般人们只能得到它的近似解。最近有人 针对灰度图像提出一种模糊迭代的归一割方法，巧妙地回避了求解归 一割最小化的问题。本文设计了一种利用它进行彩色图像分割的方 法。 第四章实验结果及分析。分别对两种基于图论的彩色图像分割方 法一最小生成树和最小割进行了彩色图像分割实验，并对实验结果进 行了分析和讨论。 第五章总结与展望。对本文目前所做的工作进行了总结，并对今 后进一步要做的工作进行了展望。 1 4 本章小结 本章首先介绍了彩色图像分割的研究背景，然后阐述了目前彩色 图像分割的主要研究方法。接下来介绍了论文的研究内容一基于图论 的彩色图像分割方法。最后给出了论文的结构安排。 6 华南师范大学0 4 缎碗 。研究生学位论文第二章最小生成树实现彩色图像分割 第二章最小生成树实现彩色图像分割 2 1 图论中最小生成树的基本原理 最小生成树是图论中的术语，它的定义如下1 4 1 l ： 设无向图g 一，怛 ) ，其中v 一“) 为无向图中所有节点的集合， e 一 ( h ，v ，) 为无向图中所有边的集合。一个典型的无向图g 1 一以， ) 如图2 1 所示，其中 k 一 嵋，v 2 ，吩，k ，吩，巨a 心，v 2 ) ，( k ，屹) ，( 吃，b ) ，( 屹，v s ) ，( v 3 ，略) ，( v 3 ，坞) ) a 图2 1 一个典犁的无向图g 1 一( 嵋， 局) ) 无向图中从节点q 到节点v ，的路径( p a t h ) 是一个节点序列 “t u 。，u ，一v ，)，其中( + ) e ，1s ks m 。路径的长度是路径 上的边数目。第一个节点和最后一个节点相同的路径称为回路或环 ( c y c l e ) 。序列中节点不重复的路径称为简单路径。除了第一个节 点和最后一个节点外，其余节点不重复出现的回路，称为简单回路或 简单环。 在无向图g 中，如果从节点q 到节点”f 有路径，则称u 和v ，是连 通的。如果对于图中任意两个节点吩，v ，e v ，m 和v ，都是连通的，则 称g 是连通图( c o n n e c t e d g r a p h ) 。无向图中的极大连通子图被称为 连通分量。一个连通图的生成树是一个极小连通子图，它含有图中全 部节点，但只有足以构成一棵树的n 一1 条边。无向图g 1的一棵生 成树如图2 2 所示。 7 牛南师范大学0 4 级硕 研究生学位论文 第二章最小生成树实现彩色图像分割 图2 2 无向图g 1 的一棵生成树 如果在一棵生成树上添加一条边，必定构成一个环，因为这条边 使得它依附的那两个节点之间有了第二条路径。一棵有n 个节点的生 成树有且仅有n 一1 条边。如果一个图有n 个节点和小于n 一1 条 边，则是非连通图。如果它有多于n 一1 条边，则一定有环。但是， 有n 一1 条边的图不一定是生成树。 从一个无向图g 中可以构造许多不同的生成树。假设对无向图g 的每条边都赋予一个权值，则一棵生成树的代价( c o s t ) 就是该生成 树上各条边的权值之和。其中，代价最小的那棵生成树被称为最小代 价生成树( m i n i m a l c o s t s p a n n i n g t r e e ) ，简称为最小生成树。 ， 构造最小生成树有多种算法，其中在图像分割中所采用的是克鲁 斯卡尔( k r u s k a l ) 算法，它适合于求边稀疏的无向图的最小生成树。 克鲁斯卡尔算法如下1 4 1 1 ： 假设无向图g 。，但 ) ，则令最小生成树的初始状态为只有n 个 节点而无边的非连通图t 一， ) ，图中每个节点白成一个连通分量。 在e 中选择权值最小的边，若该边依附的节点落在t 中不同的连通分 量上，则将此边加入到t 中，否则舍去此边而选择下一条权值最小的 边。依次类推，直至t 中所有节点都在同一连通分量上为止。依照克 鲁斯卡尔算法构造一棵最小生成树的过程如图2 3 所示。 8 华南师范大学0 4 级硕 研究生学位论文 第一二章最小生成树实现彩色幽像分割 o o ( a ) 加权的无向图( b ) 最小生成树的初始状态 ( c ) 向最小生成树添加第一条边( d ) 向最小生成树添加第一二条边 ( e ) 向最小生成树添加第三条边( d 最终构造的最小生成树 图2 3克鲁斯乍尔算法构造最小生成树的过程 2 2 分水岭算法的引入 在最小生成树实现彩色图像分割的方法中，常常将最小生成树与 9 华南师范夫学0 4 级硕仁研究生学位论文第二章最小生成树实现彩色图像分割 分水岭算法结合使用。下面将简单介绍分水岭算法的基本原理。 分水岭的概念是以对图像进行三维可视化处理为基础的：其中两 个是坐标，另一个是灰度级 i i 。对于这样一种“地形学”解释，主要 考虑三类点：( a ) 属于局部性最小值的点；( b ) 当一滴水放在某 点的位置上的时候，水一定会下落到一个单一的最小值点；( c ) 当 水处在某个点的位置上时，水会等概率地流向一个以上的最小值点。 对于一个特定区域的最小值，满足条件( b ) 的点的集合称为这个最 小值的“汇水瓮地”或“分水岭”，而满足条件( c ) 的点的集合称 为“分割线”或“分水线”。 分水蛉算法实际上就是找出分水线。它的基本思想很简单：假设 在每个区域最小值的位置上打一个洞并且让水以均匀的上升速率从洞 中涌出，从低到高淹没整个地形。当处在不同的汇聚盆地中的水将要 聚合在一起时，修建的大坝将阻止聚合。水只能达到大坝的顶部处于 水线之上的程度。这些大坝的边界对应于分水岭的分割线。所以，它 们是由分水岭算法提取出来的连续的边界线。分水岭算法的原理可以 用图2 4 解释。 臻硒二 局部最小值 局部最小值 ( a ) 地形学上的三类点( b ) 水位与大坝之间的关系 图2 4 分水岭算法的原理 分水岭算法的主要优点是能够确定单象素宽度的边界，并且这些 边界是连续无问断的。这也是它优于其他所有边界检测算子的地方。 但它的缺点是对图像噪声非常敏感，常常使图像过度分割。 2 3 传统的最小生成树的全局阙值方法 在传统方法中，通常使用最小生成树的全局阈值方法实现彩色图 1 0 华南帅范人学0 4 级硕卜研究生学位论文 第一章鼯小生成树实现彩色图像分割 像的分割，流程如图2 5 所示。 图2 5传统的最小生成树的全局阈值方法流程图 首先，分水岭算法对原彩色图像进行初始分割，得到一幅过度分 割的彩色图像。由初始分割结果构造区域邻接图( r e g i o n a d j a c e n c y g r a p h ) ：分割结果中的每个区域都可以表示为无向图中的一个节 点；对于分割结果中的任意两个相邻区域，在无向图中相应的两个节 点之自】添加一条边，边的权值代表这两个区域的相似程度。由于此无 向图可以表示图像中各区域的邻接关系，因此它被称为区域邻接图， 如图2 6 所示。 华南师范人学0 4 级硕e 研究生学位论文 第二章最小生成树实现彩色图像分割 ( a ) 图像的各区域 c o ) 相应的区域邻接图 图2 6 图像的各区域及其相应的区域邻接图 然后，由区域邻接图( r a g ) 构造最小生成树，过程如下：将当 前r a g 中最小的边权值与一个事先定义的全局阈值比较，若小于则继 续构造最小生成树，否则终止构造最小生成树。最后，最小生成树中 的每个连通分量都对应于原彩色图像中的一个区域，从而实现了对原 彩色图像的分割。 另外，在构造最小生成树( m s t ) 的过程中，每次向m s t 添加一 条边之后都需要更新r a g ：添加到m s t 的这条边在原r a g 中消失，同 时将原来r a g 中连接在该边上的两个节点合并为一个新节点。重新考 查该新节点与其他节点之间的连接关系，包括：丢弃连接在相同节点 上的多余边，以及更新各边的权值，如图2 7 所示，其中粗线表示所 构造的m s t 中的边。 ( a ) 初始r a g( b ) 添加边e ( 4 ，6 ) 剑m s t 1 2 华南师范大学0 4 级硕 研究生学位论文 第一章最小生成埘实现彩色图像分割 ( c ) 添加边p ( 2 ，3 ) 到m s t ( d ) 若干步后，晟终构造的m s t 图2 7 区域邻接幽( r a g ) 的更新 可以看到，传统方法利用一个事先定义的全局阈值确定何时终止 构造最小生成树，过程比较简单。但缺点是一个合适的全局阈值常常 需要对图像进行大量的实验才能得到。而且有时采用全局阈值不一定 能取得满意的分割效果，因为实际中对图像的不同区域及其邻域进行 分割时，往往需要使用不同的阈值。而使用一个相同的全局阈值进行 分割可能会造成图像中的某些区域很好地分离出来，但其他区域却被 过度分割。 2 4 最小生成树的局部阈值方法 本文提出了一种利用最小生成树的局部阈值实现彩色图像分割的 方法，它是对n a v o n1 4 2 1 等人的局部阈值方法的改进。n a v o n 等人采 用区域合并前后的灰度方差变化计算出一个局部阈值，用于分割原彩 色图像中的某个区域。对于彩色分布均匀的图像，该方法能取得很好 的分割效果。但对于彩色分布不均匀的图像，尤其是带有一定纹理的 彩色图像，该方法会出现较严重的过度分割。其主要原因是用灰度分 量代替彩色矢量求取局部阅值，造成了部分彩色信息丢失。但另一方 面，如果直接对彩色矢量求方差，将会是一件十分复杂的工作。 本文利用最小生成树的局部阈值实现彩色图像分割，主要进行了 两个方面的工作。首先，增加了图像预处理部分，改进了图像的初始 华南师范大学0 4 级硕研究生学位论文第一二章最小生成树实现彩色图像分割 分割结果，也即改进了初始的r a g 。其次，采用了合并前后的区域颜 色变化与区域面积的乘积计算局部阈值，考虑了全部的彩色信息，同 时也克服了图像中的彩色分布不均匀。本文分割方法的流程如图2 8 所示。 图2 8 本文利_ f j 最小生成树的局部阈值实现彩色图像分割的流程图 首先，图像预处理部分是为了消除原图像中的部分噪声，减小由 分水岭算法造成的过度分割的区域数目。本文采用一个mxm 的高斯 1 4 华南师范大学0 4 级舰l 研究生学位论文 第一章最小生成树实现彩色图像分割 低通滤波器h s ，“，y ) 对彩色图像的灰度分量f ( x ，y ) 进行平滑处理，然 后再用s o b e l 算子对其求梯度，并将所得梯度的模值进行阙值化处理， 即： l ( x ，y ) 。f ( x ，y ) h g l o ，y ) ( 2 1 ) i v l ( x ，y ) h l ( x ，y ) s a x ，y ) l + i l ( x ，y ) + s ，o ，y ) i ( 2 2 ) i 咻川一彤矧漕陬以小r ( 2 s ) 式中，术为求卷积 o ，y ) 为s o b e l 算子的水平方向掩模 s ，o ，y ) 为s o b e l 算子的垂直方向掩模 i o l 为取绝对值 本文取m = 3 ；t = 0 1 m a x l 吼0 ，y ) i ) 。 在利用分水岭算法进行初始分割以及利用初始分割结果构造区域 邻接图之后，将根据该区域邻接图构造最小生成树。与传统方法不同 的是，本文没有采用全局阈值判断是否终止构造最小生成树，而是将 最小生成树的构造过程一直进行到底，从而得到一棵完整的最小生成 树。并且在构造最小生成树的过程中，为计算局部阈值，需要在构造 的每一步都记录以下信息： 九最小生成树( m s t ) 中边的数目m ： 九 合并的两个区域编号f ，j ： 九 选取的边的权值e ( f ，j ) ： 九区域i 的合并次数 m ； 九 区域，的合并次数m ， ； 九 区域i 在第m ，次合并前后的致性变化h o m o ( r 7 。) ： 九 区域，在第m ，次合并| ； 后的一致性变化h o m o ( r 7 ) ； 其中，r 7 表示第m ，次合并的区域f ，同理有r ? 。 本文定义边的权值p ( f ，j ) 为： e “，) 一e ( 8 7 。，r ? ) 一q d c ( 8 7 ，r 7 ) + 吡d n ( 曩，r j ”) ( 2 4 ) 牛南师范丈学0 4 级硕i 。研究生学位论文 第一章最小生成树实现彩色图像分割 同时定义： e a r ? ，月，m ，) 一而万万面可石面i 丽丽丽面f 话丽( 2 5 ) d a ( r 7 。，彤m ) 一i ，y ) i l , ( 2 6 ) ( j ，y 培* ，和r ? 的公掊边界上 式中，q ，吐为常量，本文取q 一0 8 , o j 2 = 0 2 d c ( 彤，r ? ) 表示彤。与尺? 之间的颜色差异 如( 砰。，尺? ) 表示区域衅和r ? 的公共边界的强度 ，( ) ，g ( ) ，6 ( ) 分别表示区域的中心颜色在彩色空白j r g b 中的r ， g ，b 分量 厶为区域彤和r ? 的公共边界的长度 另外，本文定义区域i 在第m ；次合并f j 后的一致性变化 h o m o ( r m )( 同理有h o m d 俾m ，) ) 为： h o r n o , ( r ? 。) 一s i z e ( r - - ) 4 ( r ( r 7 ) 一，( 8 7 。1 ) ) 2 + ( g ( 墨? 。) 一g ( r ， - i ) ) 2 + ( 6 ( 8 7 l - b ( r ? 1 式中，s 妇( s 7 。1 ) 是区域彤1 的大小 ( 2 7 ) 根据以上记录的信息，可以建立两组关系，从而计算出局部阈 值。第一组关系是任意区域i 在合并前后的一致性变化h o m o ( r m 1 与 其合并次数m ，之间的关系。对于固定i ，h o m o ( r 。) 实际上为合并 次数m ，的函数，其典型曲线如图2 9 所示，其中横坐标为m ；，纵 坐标为h o m d ( 掣。) 。 图2 9 固定i h o m o ( r 7 )对于合并次数m j 的典氆曲线 1 6 华南| i i l j 范人学0 4 级欢i 研究生学位论文第一二章最小生成辨实现彩色幽像分割 第二组关系是构造m s t 的过程中，当前边的数目所与区域i 、j 的合并次数m ，、m 之间的映射关系，可记为： m l ( 对于任意f ，j ) m i j ( 2 8 ) 式( 2 8 ) 表示，由m s t 中的边数目m 可以确定当 j 合并的两个区域标号 i ，j 及其合并次数m j，m ， 。 根据这两组关系，可按如下方法计算出局部阈值： 首先由第一组关系，对于每个区域f ，找出h o m o ( r ) 中第一个 显著的峰值所对应的合并次数他。，即： 珊。一m i n 枷jih o m o ( 彤。) ( 2 9 ) 式中，一k + m a x h o m o ( 彤m k 为常数，本文取k = 0 0 1 0 1 然后依次考查m = l 2 。由第二组关系，可确定m 所对应的两个 合并区域i ，j 以及这两个区域的合并次数m ，m ， 。若当前合并 的两个区域恰好都是第一次发生显著的一致性变化，即： m i ；m i o 且m 一m p ( 2 1 0 ) 则本次构造m s t 时所选取的边p ( f ，) 为所求的局部阈值，此时应当终 止构造m s t 。并且此次合并的两个区域为最终区域，它们应当从原彩 色图像中分割出来。 此时从图像中分割出了两个区域。若图像中的还有剩余区域，则 需要修改r a g ，并开始构造新的m s t 。由于每次只从图像中能分割出 两个区域，因此上述过程需重复进行，直至图像中没有剩余区域，此 时分割完毕。 在第四章的实验部分将看到，本文提出的最小生成树的局部阈值 方法对于彩色分布不均匀的图像能够进行很好的分割，它优于传统的 最小生成树的全局阂值方法。关于本文方法在分割性能上的详细讨论 将在第四章给出。 1 7 牛南帅范人学0 4 级硕f j 研究生学位论文第一二章壤小生成钳实现彩色图像分割 2 5 本章小结 本章首先介绍了图论中最小生成树的基本原理以及分水岭算法的 基本原理。然后回顾了传统的利用最小生成树的全局阂值实现彩色图 像分割的方法。最后提出了一种利用最小生成树的局部阈值实现彩色 图像分割的方法，该方法的主要创新点是： ( 1 ) 设计了一种对图像进行了预处理的方法。通过预处理，改 进了图像的初始分割结果，也即改进了初始的区域邻接图( r a g ) 。 ( 2 ) 提出了一种计算局部阈值的方法。它将合并前后区域颜色 的变化与区域面积的乘积作为区域一致性的度量，既考虑了彩色空间 下全部的彩色信息，同时也能够克服图像中的彩色分布不均匀。 1 8 毕南师范人学0 4 级硕卜研究生学位论空第二审屉小划实现彩色图像分割 第三章最小割实现彩色图像分割 3 1 图论中最小割的基本原理 图论中与最小割( m i n i m i z e d c u t ) 有关的术语如下，它们分别 是：邻接矩阵( a d j a c e n c ym a t r i x ) ，度( d e g r e e ) ，容量( v o l u m e ) ，以及割 ( c u t ) d 3 1 。设有无向图g 一，但 ) ，则 ( 1 ) 邻接矩阵( a d j a c e n c y m a t r i x ) 的定义如下： w 1 【】( 3 1 ) 式中，f ，j e v f p “，j ) 的权值，若e ( f ，) e 。 o l 若。( f ，) 芒 图3 1 表示了邻接矩阵中的元素 与无向图的关系。 i 图3 1 邻接矩阵