（计算机应用技术专业论文）一种混合无监督图像分割算法.pdf

摘要 摘要 图像分割是计算机视觉的预处理部分，在人工智能领域占有非常重要的地位。分水 岭算法是快速有效的图像分割算法，但它有一个内在的缺陷，用纯粹的分水岭算法来进 行图像分割的结果通常是过分割的【2 一钉，所以在应用分水岭算法的时候必须根据所要分 割的图像特点来对算法进行改进。改进的方向一般包括以下三个：首先，在分水岭算法 执行之前对图像进行平滑，从而消除细小噪声对算法结果的影响，这在分水岭算法的应 用领域称为图像预处理；其次，直接对分水岭算法本身的区域形成过程进行控制和改进； 再次，将算法分割结果中过度分割的区域进行合并。 本文研究了所有上述三个改进方向，并针对分水岭算法本身的改进以及区域合并的 后处理过程给出了独创的算法。 在图像预处理中本文使用多尺度的形态学滤波技术来平滑图像。 在分水岭算法执行过程中，本文引入湖最小值的概念来改进l i n e 3 1 的顺序无关算法， 并结合落差来控制区域的形成。l i n 通过引入特殊的不确定标记r i d g e 得到一种与像素 访问顺序无关的分水岭算法，证实了自下而上的泛洪算法和自上而下的降水算法可以得 到一致的分割结果。但其算法仅仅使用像素灰度作为地形特征，因而结果中有过多的 r i d g e 标记，这些标记不属于任何区域，影响了算法的进一步应用。我们将湖最小值 当作像素除灰度之外的附加地形特征，在标记时予以参照，从而减少了约8 0 的不确定 标记数量。此外，本文引入的落差也减少了约1 0 的分割结果区域，从而减少了后续合 并工作的计算复杂度。 在执行了改进的分水岭算法之后，本文使用层次聚类技术来合并算法的分割结果区 域。在聚类相似测度的计算中，推导出一个启发式的基于b a y e s i a n 目标函数以及m a r k o v 随机域理论的简单计算模型，这个模型的两个部分分别代表了使相邻区域保持独立的因 素和使相邻区域合并到一起的因素，两个因素间的相互制衡使得算法在b a y e s i a n 目标下 得到了最优的分割结果。从实验结果上看，这种基于区域的简单计算模型有效的减少了 层次聚类的计算复杂度，即使是复杂的航空图像也能在几十秒内就完成聚类。 最后，本文综合三个改进方向的工作得到一个多阶段的图像分割算法，算法停止条 件依赖于层次聚类中的相似测度，因而该多阶段算法是无监督的，这也使得算法更加通 用。实验结果表明本文算法具有良好的计算效率，并能得到有效的分割结果。 关键词：图像分割；分水岭算法；多阶段无监督分割；m r f ：层次聚类。 a b s t r a c t a b s t r a c t w a t e r s h e dt r a n s f o r mi saf a s tm o r p h o l o g i c - b a s e di m a g es e g m e n t a t i o na l g o r i t h mw h i c h g a i n e dal o ti n t e r e s tr e c e n t l y b u tp u r ew a t e r s h e da l w a y sp r o d u c e sa no v e r - s e g m e n t e dr e s u l t t h i st h e s i sc o n t a i n sr e s e a r c ho nt h r e ed i f f e r e n tw a y sf o rm o d i f y i n gt h ew a t e r s h e da l g o r i t h m ， w h i c hr e p r e s e n tt h r e ed i f f e r e n ts t a g e so fac o m p l e t ea l g o r i t h m t h ef i r s ts t a g ei st ou s e m u l t i s c a l em o r p h o l o g i cf i l t e rt os m o o t ht h eg r a d i e n ti m a g e ，t h es e c o n ds t a g ei st oc o n t r o lt h e f o r m i n gp r o c e d u r eo fw a t e r s h e dl i n e s ，w h i l et h et h i r ds t a g ei s t om e r g er e g i o n sw i t ha h i e r a r c h i c a lc l u s t e r i n ga l g o r i t h m t h es e c o n da n dt h i r ds t a g e sc o n t a i nc r e a t i v er e s e a r c h e so ft h i st h e s i s i nt h es e c o n ds t a g e ， am o d i f i e do r d e r - i n v a r i a n ta l g o r i t h mw a sp r o p o s e d ，w h i c hu s e sl a k em i n i m u ma n dw a t e r s h e d f a l lt or e p r e s e n tt o p o g r a p h i c a li n f o r m a t i o ns oa st od e d u c et h en u m b e ro fr i d g el a b e l si n l i n sa l g o r i t h m 川h e r eo r d e r - i n v a r i a n tm e a n st h a ta l g o r i t h mr e s u l ti si n d e p e n d e n to fp i x e l s p r o c e s s i n go r d e r , s ot h et w ol i t e r a t ei m p l e m e n t a t i o n so fw a t e r s h e da l g o r i t h m i m m e r s i o n a p p r o a c ha n dt o b o g g a na p p r o a c h c a ng e tt h es a m es e g m e n t a t i o nr e s u l t a n di nt h et h i r d s t a g e ，an e wh e u r i s t i cr e g i o n b a s e dm o d e lw h i c hi sd e r i v e df r o mb a y e s i a nm e t h o da n d m a r k o vr a n d o mf i e l di su s e dt op e r f o r mh i e r a r c h i c a lc l u s t e r i n g t h i sm o d e li s e a s i l y c o m p u t e da n dc o n t a i n st w od i f f e r e n tp a r t s ，o n ew o r k sa saf a c t o rt h a tm e r g e st h ea d j a c e n t r e g i o n s ，a n dt h eo t h e rk e e p sr e g i o ni n d e p e n d e n t l y i ti st h ei n t e r a c t i o no ft h e s et w op a r t st h a t p r o d u c eo p t i m a ls e g m e n t a t i o nr e s u l tu n d e rb a y e s i a nc r i t e r i a t h ep r o p o s e dm o d i f i e do r d e r - i n v a r i a n ta l g o r i t h mi nt h es e c o n ds t a g ec a nd e d u c et h e n u m b e ro fr i d g el a b e l sb ya b o u t8 0 a sw e l la st h en u m b e ro fs e g m e n t e dr e g i o n sb ya b o u t 1o a n dt h eh i e r a r c h ym o d e li nt h et h i r ds t a g ec a nm e r g er e g i o n si nas i m i l a rw a ya sh u m a n p e r c e p t i o n b o t ho ft h e s ec r e a t i v er e s e a r c h e sc a nb e n e f i tc o m p l e t em u l t i s t a g es e g m e n t a t i o n a l g o r i t h mb ye l i m i n a t i n gt h eu n c e r t a i n t ya n dd e d u c i n gt h ec o m p u t a t i o nc o m p l e x i t y k e yw o r d s ：i m a g es e g m e n t a t i o n ；w a t e r s h e da l g o r i t h m ；m u l t i s t a g eu n s u p e r v i s e d s e g m e n t a t i o n ；m a r k o vr a n d o mf i e l d ( m r f ) ；h i e r a r c h i c a lc l u s t e r i n g 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含本人为获得江南 大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志 对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 签名： 日 期： 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规定： 江南大学有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文， 并且本人电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 签名： 导师签名： 派扦 一章镕论 第一章绪论 图像分割是计算机视觉的预处理部分，其目的是从图像中提取一些信息，使得输出 图像的信息所包含的数据要远远少于原始图像的数据，但是与原始数据相比，这些少量 的输出信息更能被机器视觉系统所理解。然而，由于对囝像信息的理解受到其场景中的 光照条件，透视角度甚至是人的主观判断的影响，很难得到通用的图像分割算法。此外， 在图像获取时的噪声干扰以及图像传输过程中的信息丢失等都会影响图像的质量，为分 割算法的设计带来了更大的挑战。可以说图像分割是影响机器视觉、人工智能等领域快 速发展的晟基本问题。 分水岭算法是一种基于数学形奄学理论的快速图像分割算法，它早在上世纪七十年 代末就被学者提出，但一直受限于计算复杂而得不到广泛应用。直到九十年代初 v i n c e n t 提出模拟泛洪的快速方法后“1 ，分水岭算法便成了图像分割中最重要的研究热 点，同时也被广泛地应用于各种领域，甚至成了一些数学软件中图像分割的标准算法。 然而，分水岭算法有一个固有的缺陷：用它进行图像分割的结果通常包含许多细小的区 域，称为是过分割的，图1 1 演示了v i n c e n t 算法的分割结果。分水岭的过分割问题使 得在应用时需要对算法进行其它改进处理，改进的内容包括在算法执行前对图像进行空 问滤波，直接对算法本身的分水岭形成过程进行限制以及在算法执行后对过分割的小区 域进行合并这三个方面。有关分水岭算法的研究内容就主要涉及到这三个改进方向中， 每年都会有大量的研究成果发表出来，它们要么关注于预处理或者后续处理等算法理论 方面，要么关注于为具体的应用领域设计合适的改进算法。 孵骚慧熬鞭嫒 、。辩 m 蕤鬣 围卜1v i n c e n t 分水岭算法结果演示。图( a ) 为一幅人造的飞机图像，( c ) 为一幅航互图像。 ( b ) 和( d ) 分别给出7 两幅图像的分水岭变换的结果，用黑色标记出分割区域的边界。 本文主要研究分水岭算法及其改进的各个方向，并虽终给出一个完整的适用于不同 图像的多阶段无监督分割算法。在本章简要介绍图像分割和分水岭算法的相关内容后， 第二章给出了数学形态学的基本知识，它们是分水岭算法的理论基础，同时我们介绍了 形态学多尺度空间滤波，并用该滤波技术柬进行分水岭算法的预处理。在第三章，我们 引入湖最小值以及落差的概念，直接对分水岭算法的执行过程进行改进，改进后得到了 一个与像素访问顺序无关的稳定算法。然后我们将该稳定算法的分割结果应用于基于区 域的层次聚类模型，构成一个多阶段的分割算法。有关层次聚类模型的内容在第四章， 它包台了两个计算部分，一个使结果区域合并，另一个保持结果区域的独立，两部分相 习一 鬟 江南火学硕士学位论文 互作用并在贝叶斯决策下寻求最优，从而有效地合并了分水岭算法过度分割的结果区 域。整体的算法总结以及实验结果在第五章，其中也包括对多尺度形态学空间滤波中的 尺度选择、稳定算法中的落差选择以及层次聚类时的参数选择的详细讨论。 1 1 图像分割的理论基础 一副图像可以定义为一个二维函数f ( x ，y ) ，其中x 和y 是空间坐标，而在任意一 对坐标处的函数值称为该坐标处图像的亮度。对于狄度图像，亮度是一个数值，对于彩 色图像，亮度是其所用颜色空间的一个向量。当_ y 和厂的值都是有限的离散值时，该 图像为数字图像，它可以用二维数组来表示，数组中的每一个元素称为像素。图像分割 依据一些特征( 如亮度、纹理等) 信息将图像中的像素分成不同的连通区域【5 ，6 】，从而为 后续的工作如计算机视觉、场景分析建模等提供支持。 1 1 1 图像分割的定义 图像分割将图像像素按照一定的标准分成不同的区域，也就是连通的像素集合。分 割的标准可以基于像素亮度、图像纹理、频谱等特征信息，而分割成的各个邻接区域的 这些特征互不相同。图像分割的结果是区域的集合，这些区域互不相交，并且覆盖了整 个图像。 令g 表示整个图像，则图像分割可以看作是把g 分成刀个子区域蜀，r ：，恐兄的过 程，且需满足： n ( a )【j r i = g i j ( b )对vi ，i = 1 , 2 ，n ，r i 是连通的 ( c )对vi ，j = 1 , 2 ，n 且i j 有r inr i = 西 ( d ) p ( r i ) = t r u e ，i _ 1 ，2 ，n ( e ) p ( r iu r i ) = f a l s e ，对于任何邻接的区域r i 和r i 其中，( a ) 要求图像中的每个像素都应该被分割至一个具体的区域，( b ) 要求一个 区域内的两个像素应该有路径可以连通，( c ) 表示一个像素只能属于一个区域，从这三 点看，分割的定义类似于数学中的划分概念。此外，p ( r ，) 是定义在区域足上的谓词， 用于表示该区域是否具有某种性质。比如在以像素亮度为分割标准的算法中，该谓词就 可以表示区域中的像素是否具有相似的亮度。因此，( d ) 和( e ) 就表示在图像分割的 结果中，任意区域内的像素应具有相似的特征，而任意两个邻接区域的特征不相似。 图像分割的目的是从复杂的图像信息提取出简化的更有意义更利于后续处理分析 的信息，通常被用于对象识别和边缘检测中。因此图像细分的程度取决于所要解决的问 题，当后续应用中感兴趣的对象已经分割出来之后就应该停止分割。例如，对于交通图 像的分割，如果是用于测量汽车速度，则当把汽车从背景中分割出来时就应该停止分割， 而如果是用于识别牌照，则应该细分到将牌照也分割出来。然而，实际算法的设计并不 2 第一章绪论 像直观上这么简单，分割的细分程度及算法停止条件都是需要仔细考虑的内容。 1 1 2 图像分割算法分类 图像分割是机器视觉的基础和难点之一，也是视频分析、场景建模的基础，同时它 还广泛地应用于医学、地理学及军事学【7 8 】。鉴于此，每年都会涌现出大量关于图像分割 的研究，涉及到图像分割的各个领域和方向。 ( 1 ) 灰度图像分割和彩色图像分割。 根据图像像素的亮度空间，图像分割包括灰度图像分割和彩色图像分割。其中灰度 图像分割主要是基于灰度值的不连续性和相似性进行分割，分割结果中同一区域的像素 灰度具有相似性，而区域之间边缘部分的像素灰度值不连续。彩色图像的分割还需要考 虑颜色空间的特性【9 , 1 0 】，如果先根据像素亮度的多维的颜色空间分量得到一个一维的像 素特征，则可以将这个像素特征对应于灰度图像中的像素灰度，此时任何灰度图像分割 的算法都可以应用于彩色图像的分割。此外，彩色图像的分割还可以基于不同颜色空间 各自的信息，或结合颜色纹理信息来进行分割1 1 。 ( 2 ) 有监督分割和无监督分割。 按照分割过程中是否依赖先验信息，图像分割可以分为有监督和无监督的分割。对 于有监督的分割，通常需要知道待识别的对象特征，如形状、亮度等，这些特征可以根 据一组训练样本图像来获得，并通过特征描绘算子予以描述。在正式的算法中便可以使 用之前的特征描绘算子来执行分割。此外，也可以使用人们对图像的直观判断来进行标 记，并在标记的基础上进行分割，具体的有基于标记的区域增长算法【l2 】和基于标记的分 水岭算法【1 3 】等。一般而言，凡是在分割算法中需要训练样本以获得先验信息，或是需要 人工干预的算法均属于有监督的分割算法，反之便是无监督的算法。可见，由于无监督 的分割算法不需要先验信息，因此更加通用，对于计算机视觉以及视频分割更有实际意 义【1 4 】。然而也正是由于没有先验信息及人工干预，对于无监督的分割算法的设计需要更 加精细的考虑。 ( 3 ) 基于区域的分割和基于对象边缘的分割。 按照分割手段的不同可以分为基于区域和基于对象边缘的分割。 基于区域的分割的最终目标是要使分割结果区域的图像亮度、纹理等特征具有相似 性，基本的方法包括区域增长法和区域分割合并法。区域增长法是根据预先定义的生长 准则来把像素或子区域集合成较大的区域的处理方法。通常是以一组种子点来开始形成 增长区域，并将像素特征类似于种子点的像素( i ：l 女n 与种子点具有小于某指定亮度差的 像素) 附加到由种子点所生长出的区域上。根据种子点的选取中是否需先验信息，算法 又分为无监督的区域增长和有监督的区域增长。选取种子点的先验信息可以来源于已经 成功分割的图像( 作为样本) ，也可以来源于待识别的对象的特征。当没有先验信息时， 就需要对所有像素按统一的标准计算特征，通过各个像素的特征来选取种子，在生长过 程期间又根据这些特征来附加像素。例如将灰度值为局部极大值或极小值的像素作为种 3 江南人学硕士学位论文 子点，再把生长区域的邻接像素中灰度值相近的像素附加进区域。本文重点研究的分水 岭算法实质上就是一种区域生长算法，在不进行预处理的情况下，其种子点选取为梯度 图像的局部极小值的像素，区域生长过程中使用一种基于地形测度的距离度量来附加像 素。区域生长法是一种有种子点来生长区域的自下向上的方法，另一种基于区域的分割 方法区域分割合并法则先用一种自上至下的分割过程将图像细分为一组互不相连的区 域，然后再将具有相似特征的邻接区域合并。 前面提到，分割结果区域内部的像素亮度或纹理信息要有相似性，这就涉及到相似 度准则的选择。而且相似度准则除了要考虑到区域内部的像素灰度信息之外，还要考虑 区域生长过程中的空间信息。设想如果仅用灰度值来做相似度准则，将图像中具有相同 灰度的像素归结为一个区域，则分割结果连区域连通特性也不会满足。 通常，基于区域的图像分割过程就是将图像中的像素标记为不同的标记的过程，而 连通的具有相同标记的像素点构成了分割的个区域。因此，将模式识别领域中的分类 或聚类算法应用到像素点上就可以对图像进行分割，这时图像分割操作也可以看成是由 原始的数字图像得到标记了区域的图像的一种变换。 与基于区域的分割不同的是基于对象边缘检测的分割，这种分割的依据是边缘像素 亮度值的不连续性。不连续性的度量是由梯度向量的幅值实现的。二维函数f ( x ，) ，) 的梯 度向量定义为 夥= 阱 矽 a x 矽 砂 该向量的幅值是 m a g ( v f ) = + g ； 为了简化计算，幅值也可以省掉平方根或者取绝对值来近似 m a g ( v f ) z + g ；或m a g ( v f ) z igl + ig ，l 与边缘检测相关的研究重点在于检测器的设计，也就是数字图像中的像素灰度不连 续性的度量方法设计。经典的方法有s o b e l 边缘检测，p r e w i t t 边缘检测等 5 , 1 5 l 。通常计 算得到的亮度变化幅度还要和阈值进行比较，只有亮度变化大于阈值的像素才被认作是 边缘。在阈值选择时有全局阈值和局部阈值两种情况，其中后者通过在不同图像范围设 置不同的阈值，可以使得边缘检测结果更加准确。此外，由图像分割的定义可以看到， 边缘检测的结果应该是一系列闭合的边缘。但是，实际上由于图像噪声、不均匀照明引 起的边缘断裂和杂散的不连续亮度等的影响，很难得到完整的闭合边缘。因此通用的边 缘检测算法都会有一个链接过程把像素组装成有意义的边缘，h o u g h 变换就是这样一种 链接图像线段的方法【l6 1 。 4 第一章绪论 1 2 分水岭算法介绍 由于数字图像中噪声的存在以及图像场景的随机性，使得对像素点的分类并不像表 面上那样自然。此外，基于像素分类的办法大多需要复杂的计算【5 1 7 】，这不能满足那些 需要快速分割结果的需求。直到上世纪9 0 年代初，v i n c e n t 的研究成果1 2 j 改变了图像分 割技术的应用前景。他将s b e u c h e r 和c l a n t u 6 j o u l 【i 】于上世纪7 0 年代末提出的用于 灰度图像分割的分水岭算法用一种模拟水面沉浸的办法予以实现，大大减少了分割所用 的计算时间，使得分水岭算法成为了图像分割领域的研究热点。然而，由于分水岭算法 对图像中的噪声敏感，它的分割结果必然是过度的。为了弥补这个的缺点，在v i n c e n t 提出模拟沉浸的算法之后的几年一直到今天，不断有学者提出基于分水岭算法的改进分 割方法，这些方法有的结合传统的统计分割技术以实现区域增长和合并【l8 1 9 】，有的使用 空间滤波技术消除噪声【2 ，3 1 ，还有的直接控制分水岭算法本身形成分割区域的机制【2 们， 他们将这些方法应用到生物医疗、计算机视觉、卫星雷达遥感图像的分析，为科技的发 展及人们生活质量的提高做出了重大贡献。 分水岭算法是一种基于区域的算法，它最初的思想来源于地理学：在地理学中，分 水岭是指一个山脊，在该山脊旁的区域中有着不同流向的水系。汇水盆地是指水流入的 地理区域。想象一片山地，雨水降落在其表面并顺着地势聚集在相应的汇水笳地中，只 有山脊上的雨水流入周围的汇水盆地的概率是一样的。在图像中，汇水盈地就是分割的 区域，山脊就是区域边界。此外，还可以把分水岭算法想象成是水面浸溢的过程，也就 是常说的泛洪过程。水从各个汇水瓮地的最低点开始向上漫溢，在一些点上不同汇水盆 地满溢上来的水会相互交汇，于是在这些点上建起大坝来阻止水的交汇。最终，每一个 汇水盆地都会被大坝所包围，这些水坝所在位置就对应着分水岭。有关分水岭算法的这 两种直观理解对应着学术上的两种算法实现，分别是自上而下的降水算法和自下而上的 泛洪算法。 然而，如果仅是把分水岭算法应用到原始狄度图像，得到的经常是没有意义的分割 结果【3 1 。只有把算法应用于梯度图像才能得到合理的结果，这是因为区域的边界应该是 那些变化明显的地方，也就是梯度绝对值较大的地方。而灰度值大小只是表明图像本身 的场景。所以通常情况下，我们可以将梯度图像看作是地理平面，而梯度绝对值就是平 面上点的海拔高度。图1 2 给出了一维情况的分水岭算法的图形描述。 5 江南人学硕士学位论文 - ，“) ，t x ) 爪之 罗紫。 一 l 一一_ 一 一 一 l - 、 一一，一，7 一 i ( c ) ( d ) 图卜2 一维情况下的分水岭算法描述图。( a ) 中厂o ) 是一个一维的函数，( b ) 是( a ) 的一阶 导数，( c ) 中g o ) 刊厂g ) i 是( a ) 中函数一阶导数的绝对值。从( c ) 中看出g ( x ) 在定义域内有 两个局部极大值点，三个局部最小值点，它们将原函数分成了三个区域，结果在( d ) 中显示。 有关分水岭算法的研究大都涉及以下三个方面： 首先是分水岭算法结果的精确性，分割结果是否独立于执行算法时处理像素的顺 序，各种不同的分水岭算法实现( 自项向下的降水算法和自底向上的泛洪算法) 所得到 的结果是否一致等。y u n g c h i e hl i n 等人的研究【3 】表明，只要去除计算过程中像素处理 顺序的影响，自底向上模拟泛洪的算法和自顶向下模拟降水的算法可以得到完全一致的 分割结果。此外，h i e ut a tn g u y e n 2 0 】提出了一种基于能量函数的水蛇算法，该方法也是 一种区域生长法，不同的是他们引入了能量函数，并证明当能量函数取得最小值时分割 的结果就是分水岭算法所得到的结果，反之也成立。 其次，由于分水岭算法对噪声敏感，任何区域极小值都对应着一个分割区域，这使 得算法总是得到过度分割的结果，因而必须对基本的算法进行改进才可以应用。我们在 下一小节将重点讨论解决过分割问题的改进方向，这也是本文的主要研究内容。 再次，近年来并行计算技术的发展加速了对分水岭算法并行化的研究，其中 r o e r d i n k 2 1 】详细讨论了基于顺序扫描像素的分水岭算法的并行计算策略，周海芳则通 过引入伪种子点来使得区域增长相互独立，给出一种优化的并行计算方法。 1 3 分水岭算法的改进方向 纯粹的分水岭算法的分割结果数目等于梯度图像中局部极小值的数目，由于图像场 景的随机性以及图像获取、传输过程中硬件设备的干扰，大多数图像的小噪声都非常多， 其梯度图像的局部极小值也非常多，以致纯粹的分水岭算法必然带来过度分割的结果， 因此必须对算法进行改进。通用的改进方向主要有三个：一是在应用算法前针对梯度图 6 第一章终论 像进行改进，基标在于消除不重要的区域极小值点；二是直接对分水岭算法本身进行改 进，通过控制分割区域形成过程来消除不应有的分割区域；三是在分水岭算法结束之后 合并过分割的区域。本节中我们将分别介绍这三种改进方向的理论和学术上的成果。 ( 1 ) 应用算法前针对梯度图像的改进。 执行分水岭算法前对梯度图像的改进所研究的内容既包括对梯度图像本身进行修 改，又包括在生成梯度图像时进行梯度算子的设计。 对于梯度图像本身的修改在分水岭改进的领域中称作预处理，方法主要包括对梯度 图进行空间滤波以消除区域极小值，以及使用基于标记的方法修改梯度图像以使得区域 极小值仅出现在标记位置。相比而言，前者计算量较少并且不需要先验知识，但有可能 过滤掉有用的细节信息；而标记方法则能够精确的控制分割的区域数目和位置，但是需 要额外的标记过程。进行梯度图豫豹空闻滤波时除了可使用传统的g a u s s 滤波、s o b e l 滤波外，使用数学形态学知识进行多尺度空间滤波成为近年来的研究热点【2 3 , 2 4 ，特别是 基予形态学多尺度重构的空闻滤波技术已经取得了很好的效果。其中，刘海华【2 5 】将形态 学的多尺度信息与图像分割的结果堆栈相结合，彭启民【l0 】将形态学多尺度信息应用于获 取彩色图像的梯度以进行分割。此外，王小鹏【2 6 】在形态学尺度空间滤波的基础上对梯度 图像进行修正，进一步减少了区域极小值。他们考虑到随机噪声既可能是高亮干扰，还 可能是细小的暗色干扰，提出混合形态学开闭重建的尺度空间平滑办法。此外对于特定 的应j 雳，在预处理中还可以根据福关图像的特性，雩l 入标记符柬控制分割结果。基于标 记来改进分水岭的过分割问题关键在于标记的选取，既可以在具有局部最小梯度值的像 素中按照某种标准选择像素 乍为标记，也可以用其它方法选择非局部最小的像素点作为 标记，然盾使用s o i l l e 2 7 】介绍的强制最小技术修改梯度图像，使得局部最小值仅仅出现 在标记的位置。由于分水岭算法的分割区域对应着梯度图像的局部最小值，因此基于标 记的改进方法能够控制分割的区域数目及位置。对于对象识别问题还可以在感兴趣的对 象区域设定内部标记符，在背景区域设定外部标记符，并且针对内外部标记采用不同的 泛洪技术，从而在计算中将焦点关注于对象。高丽根据照度。反射模型获褥频域信息 并将对象特征保存在低频成分，从而构造出个基于频域信息的标记算法。 针对梯度图像的改进还包括梯度图像生成过程的改进，也就是根据原始图像的特点 选择更合适的梯度算子。p a u lr h i l l 2 s 】引入基于纹理的梯度算子从而消除噪声和细小变 化对于分割结果的影响。此外在使用不同的梯度算予前还可以对原图像进行一定的平 滑，过滤掉原图像中的细小噪声，但平滑的方法一定要与梯度算子的特点相适应。 ( 2 ) 分水岭算法中区域形成过程的改进。 改进的第二个方向是壹接对分承岭变换中产生分割区域的过程进行改进，逶常是通 过设置区域特征的阀值以控制区域的形成来实现。在基本的分水岭算法中，水面从区域 极小值开始向上漫溢，丽且不固极小值处漫滋上来的水面交汇的地方就是分水岭，实际 上这里的分水岭也就是区域的极大值。当区域极小值与周围的极大值的落差不是很明显 的时候，对一些应用而言这样的区域就可以不予考虑。例如对象识别和行为判断等应用 7 江南大学硕士学位论文 方向中，所要做的是提取对象的信息，这时由于场景中对象与背景的区分是明显的，并 且可以不考虑背景中的细小变化，所以基本分水岭算法中的那些“落差 不明显的汇水 盆地就可以不被当作分割结果中的区域，基于这种思想，崔明【2 9 】等人定义了分水岭点的 落差概念，并设定阈值，只有当落差大于阈值的情况下才将汇水盆地看作是分割结果， 详细内容请参见他们的论文。此外，r i c h a r db e a r e 【3 0 】给出一种限制区域增长的办法，该 方法基于水蛇算法【2 0 】中的能量函数，并在分水岭变换的过程中引入了边界的限制以控制 噪声的影响。 ( 3 ) 算法结束后对过分割的区域进行合并。 改进分水岭算法的最后一个方向是对算法执行后过度分割的区域进行处理，一般是 利用聚类算法或区域生长算法将相似的邻接区域进行合并( 融合) 。注意这时要用的相 似测度是用于测量区域之间的相似性，而不是像素和区域间的相似性，因此要区别于一 般的区域生长算法。在区域合并过程中，可以将两个区域的平均灰度差看作是不相似的 测度，然后选择不相似测度最小的邻接区域进行合并。但仅仅使用平均灰度来测量相似 性缺少图像的空间信息和场景信息等先验知识，分割结果经常不合实际。在图像分割领 域，马尔科夫随机域( m r f ) 模型经常被用来表示图像的空间连接特性【3 卜33 1 ，在该模型 中相邻的像素具有较高的概率被分类到同一区域。而且由于m r f 完全用数学公式表示 先验信息，它也非常适用于无监督的分割【3 4 。6 】。a n j a ns a r k a r t 3 7 】等人就将m r f 与区域邻 接图相结合，得到通用于一般图像和纹理图像的无监督分割方法。s a n g h o o nl e e 1 。7 】则通 过优化基于m r f 的b a y e s i a n 目标函数来实现区域合并和像素分类。除了基于m r f 的 相似测度外，r o b e r t 3 8 】还使用频谱聚类技术对区域进行合并。 1 4 本文工作 分水岭算法内在的过分割缺陷使得必须对它进行改进才能应用于实际，本文就是要 综合各种改进办法以得到一种准确而有效的图像分割方法。为了更加通用，我们最终给 出的算法是无监督的，也就是说基于标记等依赖于先验信息的方法和要求训练集来判断 分割参数的方法都不是本文的研究内容。 本文涉及到改进分水岭算法的所有三个方向，在算法执行之前我们应用形态学膨胀 腐蚀来减弱原始图像中噪声的干扰，并对梯度图像进行多尺度形态学重构滤波。对原始 图像的滤波可以减弱噪声对梯度图像的影响，从而使得对梯度图像滤波时的尺度选择更 加自由，可以更好地配合后续两个方向的改进工作。由于本文的算法在对梯度图像执行 分水岭分割后还有层次聚类合并区域的过程，所以形态学滤波中尺度的选择与刘海华 2 5 】 的完全基于形态学尺度空间的算法有所不同，刘的算法使用尺度堆栈得到相应的分割结 果堆栈然后再结合具体应用选择哪个是合适的尺度，而本文形态学滤波中尺度的选择必 须要配合后续的改进算法以获得最优结果。 在分水岭算法执行过程中，引入湖最小值的概念来改进l i n 3 】的顺序无关算法，并 结合落差来控制区域的形成。l i n 通过引入特殊标记r i d g e 得到一种与像素访问顺序无 8 第一章绪论 关的分水岭算法，证实了自下丽上的泛洪算法和皇上而下的降水算法可以得到一致的分 割结果。其算法思想是在执行分水岭变换的过程中，当参考标记的像素具有相同的地形 特征时，就使用r i d g e 来标记待处理的像素。但其算法仅仅使用像素灰度作为地形特 征，这使得结果中有过多的r i d g e 标记，这些标记不属于任何区域，影响了算法的进 一步应用。本文中，我们将湖最小值当作像素除灰度之外的附加地形特征，在标记时予 以参照，从面减少了约8 0 的r i d g e 标记像素。此外，本文零| 入的落差也减少了约1 0 的分割结果区域，从而减少了后续合并工作的计算复杂度。 在分水岭算法执行之后的区域合并过程弓| 入层次聚类的方法，它需要使用某个相似 ( 或不相似) 测度来判断待合并的区域，在每一步聚类过程中都合并相似度最高( 或者 不相似度最低) 的两个区域。在相似测度的计算中，我们使用m r f 测量区域之间的连 接特性，使用灰度平均值和区域大小表示区域内部的信息，推导出一个基于b a y e s i a n 理 论的计算不相似测度的简单公式，这个公式的两个部分分别代表了使区域保持独立的因 素和使相邻区域合并到一起麓因素，两个因素闻的权衡依赖于梯度图像的信息以及初始 分割结果。有关聚类的停止条件使用基于b a y e s i a n 目标函数的方法，并结合聚类中计算 相似测度的公式，给出了一个启发式的算法停止条件。 综上，本文各章节的内容如下： 第二章介绍形态学尺度空间滤波的知识，其中包括形态学基本运算，形态学尺度空 间特征以及应用多尺度形态学重构技术进行图像平滑。 第三章介绍l i n t 3 】的顺序无关的分水岭算法，该算法基于v i n c e n t t 2 】的模拟泛洪算法 以及f a i r f i e l d t 3 9 1 下降差异增强理论和m o r t e n s e n e 4 嘲的模拟降水算法。同时提出独创的改 进算法，改进过程中通过引入湖最小值作为像素的额外地形特征来减少不确定标记数 量，通过弓| 入落差来减少分割结果的区域数量，并给出模拟泛洪和模拟降水两个方向上 改进算法的具体实现。从结果上看，我们的改进算法在大幅度减少r i d g e 标记数量的 基础上保持了顺序无关的特性，泛洪和降水两个方向的实现得到了相同的分割结果。 第窭章介绍用于合并分水岭算法产生的分割结果区域静层次聚类算法。并基于 b a y e s i a n 圈标函数和m a r k o v 随机域的概念推导出一个简单的计算不相似测度的公式， 该公式包含促使区域合并以及傈持区域独立的两部分，两者相互制衡使得分割结果在基 于b a y e s i a n 目标函数的决策下达到最优。 第五章概括了本文的完整算法，它包括用多尺度形态学滤波进行预处理、执行改进 的顺序无关算法以及在分水岭算法的基硪上进行层次聚类来合并区域这三个阶段。同时 我们讨论了算法的停止条件，并给出算法参数不同选择情况下的各种实验结果。 9 江南人学硕士学位论文 第二章形态学尺度空间滤波技术 形态学本身是生物学中的一个分支，用于处理动物和植物的形状和结构。数学形态 学在表示区域边界和骨骼时非常有用，因而也引用该语义，它由法国科学家g m a t h e r o n 和j s e r r a 于1 9 6 4 年在积分几何的基础上创立。数学形态学建立在严格的数学理论基础 上，其计算主要是对信号进行卷积处理。在应用于离散的数字图像领域时，二维的卷积 操作又有非常简单的计算方式，即只需用结构元素( s t r u c t u r i n ge l e m e n t ) 对图像像素进行 简单的集合论基本操作。结构元素也是由一些具有数值的点组成，并且可以有不同的大 小和形状，用来提取图像不同的特征或过滤不同噪声。尺度在直观上可以理解为与结构 元素大小相关的东西，如圆形结构元素的半径或者线形结构元素的长度。在滤波过程中， 通过尺度的变换可以控制过滤的信息。在应用到与分水岭算法相关的图像预处理时，有 个关键的假设就是信息被理解成函数的极小值，因为在纯粹的分水岭变换中的结果区域 数量和图像区域极小值相同，滤波也就是过滤掉某些区域极小值。 本章中，我们先给出形态学的基本运算，包括形态学膨胀腐蚀，开闭运算以及形态 学梯度运算。然后介绍形态学尺度空间的特性，最后使用多尺度的形态学重构技术来进 行图像滤波。 2 1 形态学基本运算 这里我们引用j a c k w a y 2 3 】对形态学操作的定义：给出两个函数f ：dcr ”- - ) r 和 g ：gc 7 r ”- - ) r ，本节的定义均是基于这两个函数的运算。 2 1 1 形态学膨胀腐蚀 【定义2 1 膨胀 ：使用结构元素g ( x ) 对函数f ( x ) 的膨胀记为( feg ) ) ，并且定义 ( o g ) ( x ) = s u p ( ( x f ) + g o ) ) m g c 、d x 定义2 2 腐蚀】：使用结构元素g ( x ) 对函数f ( x ) 的腐蚀记为( 厂0g ) ) ，并且定义 ( 厂0g ) ( x ) = i n f ( 厂( x + f ) 一g ( f ) l e u ，1 l _ x 其中见表示定义域d 的偏移，皿= 缸+ f ：r e d ) ，s u p ) 和i n f ) 表示厂在定义域内的 上确界( 最小上界闭包) 和下确界( 最大下界闭包) 。 在二值图像中，膨胀的几何解释为g 在内完全匹配的情况下平移时的并集；腐蚀 的几何解释为g 与有重叠的情况下平移时的并集。图2 1 给出了二值图像膨胀腐蚀的 结果演示，从中可以看出，膨胀使二值图像加粗，腐蚀使图像细化，具体的效果由结构 元素控制。 1 0 第= $ m 女# t 度卒问滤被技术 口口口一 口嚣口慧一口麓 口口口口口一一 【af b f r ) 图2 - 1 离散的二值图像膨胀腐蚀结果演示( a ) 像素是图像以厦结构元素平移时的中- o ，( 蔫 口口口口 为原始图像，( b ) 是结构元素，有黑由纹理的 c ) 是腐蚀运算的结果，( d ) 是膨胀运算的结果 对于灰座幽像而言，定义域是二维离散空间，则膨胀与腐蚀分划定义为： ( ，o g ) ( x ，y ) = m a x ( f ( x x 。，y y ) + g ( z 。，y ) l ( x ，y ) g ( ，0 9 ) ( z ，y ) = m i n ( f ( x + x 。，y + y 一g ( x ，y ) l ( j ，y g 其中，g 是g 的定义域，对于膨胀运算，f ( x ，y ) 在定义域d 外假设为吨对于腐 蚀运算假设为+ 。灰度图像的膨胀腐蚀运算类似于空间卷积处理结构元素可以看作 是掩模。计算时结构元素在圈像上平移，每个平移位置都将结构元素值与相对应的像素 亮度值相加，并将其中晟大的值作为该位置膨胀运算的值。而腐蚀则是用像素亮度值减 去结构元素对应位置上的值，并将虽小的值作为该位置腐蚀运算的结果。实际上，在将 膨胀和腐蚀应用于灰度图像时，通常使用平坦的结构元素束执行，这种结构元素中g 在 定义城内的值都是0 ，因此驮度图像的膨胀和腐蚀可以简化为： ( ，0 9 ) ( z ，y ) = m a x f ( x z ，y y 1 ) i ( x 。，y ) g ) ( ，o g ) ( x ，y ) = m i n f ( x + x ，y + y ) ( x ，y ) g 2 1 2 形态学开闭运算 在图像处理的实际应用中，更多的以各种组合的形式来使用膨胀和腐蚀，从而获得 各种效果。常用的有形态学开运算、闭运算以及形态学梯度。 f 定义23 开运算 ：结构元素g 对函数，的开运算记为f 。g ，并定义为用gx , t f 先做腐 蚀运算，再对腐蚀的结果进行膨胀： ，。g = ( f o g ) o g 【定义2 4 闭运算 ：结构元素g 对函数，的闭运算记为f g ，并定义为用g 对，先做膨 胀运算，再对膨胀的结果进行腐蚀： f g = ( ，o g ) 0 9 在二值