（计算数学专业论文）基于马尔可夫随机场的图像分割研究.pdf

摘要 论文题目：基于马尔可夫随机场的图像分割研究 学科专业：计算数学 研究生：胡阳涟签名： 指导教师：赵凤群教授签名： 摘要 图像分割是计算机视觉中的关键技术之一。基于马尔可夫随机场( m a r k o vr a n d o m f i e l d ，m r f ) 模型的图像分割方法，是一种基于统计的分割方法，具有能充分利用先验知 识，能形成闭合的边界，模型参数少且易于和其他方法相结合等优点，所以此方法在图像 分割领域中得到了广泛的应用。 本文研究了基于m r f 的图像分割算法，重点研究了基于m r f 的图像分割模型中的参 数估计方法，以及m r f 中的最大后验概率( m a x i m u map o s t e r i o r i ，m a p ) i n 题的求解方法。 首先，研究了m r f 中m a p 问题的求解方法。为提高传统的模拟退火( s i m u l a t e d a n n e a l i n g ，s a ) 算法求解m a p 问题的速度，在s a 算法基础上提出了一种基于振动点的s a 算 法。在初始分割后，将图像的像素点分为两类：振动点和稳定点，并借助链表的数据结构 存储振动点，每次迭代只对链表里面的振动点进行计算，以减少运算量。另外，本文还对 s a 算法的停步准则进行了改进，避免了全局能量的计算。实验表明这种基于振动点的改 进s a 算法在不影响分割效果的前提下，大幅度提高了计算效率。 其次，研究了m r f 中的参数估计方法。介绍了两种传统的参数估计方法：样本训练法 和e m 算法，并对两种方法进行了数值模拟和对比。然后，结合四叉树分解提出了一种新 的非均匀m r f 的耦合系数估计方法。实验表明，本文的估计方法较为准确，将它应用到 图像分割中，能增强图像分割的自适应性，改善分割效果。 关键词：图像分割；马尔可夫随机场；振动点；模拟退火；耦合系数；四叉树分解 西安理工大学硕士学位论文 t i t l e ：s t u d yo ni m a g es e g m e n t a t i o nb a s e do nm a r k o v r a n d o mf i e l d m a j o r ：c o m p u t a t i o n a lm a t h e m a t i c s n a m e ：h uy a n g l i a n s u p e r v i s o r ：p r o f z h a of e n g q u n a b s t r a c t s i g n a t u r e ：卧例蝴 s i g n a t u r e ： i m a g es e g m e n t a t i o ni so n eo fk e yi s s u e si nc o m p u t e rv i s i o n t h ei m a g es e g m e n t a t i o n b a s e do nm r fm o d e lh a sr e c e i v e dm u c ha p p r e c i a t i o n ，s u c ha st h ea b i l i t yt om a k eu s eo fp r i o r k n o w l e d g e ，t h ea b i l i t yt og e n e r a t ec o n n e c t e db o u n d a r y , l e s sp a r a m e t e r , c a ne a s i l yc o m b i n e w i t h o t h e rs e g m e n t a t i o nm e t h o d s ot h ea l g o r i t h mh a sw i d e l yu s e di nt h ei m a g es e g m e n t a t i o nf i e l d i m a g es e g m e n t a t i o na l g o r i t h mb a s e do nm r f i ss t u d i e di nt h i st h e s i s ，a n de s p e c i a l l yt w o p r o b l e m sa r ed i s c u s s e d ，t h a ti st h ep a r a m e t e re s t i m a t i o ni nm r fa n dt h es o l v i n go ft h em a p p r o b l e mi nm r f f i r s t l y , t h em a pp r o b l e mi nm r f i sd i s c u s s e d an e ws aa l g o r i t h mb a s e do nv i b r a n t p o i n t si sp r e s e n t e dt oi n c r e a s et h es p e e do ft h et r a d i t i o n a ls aa l g o r i t h mi ns o l v i n gt h em a p p r o b l e m a f t e rt h ep r e s e g m e n t a t i o no f t h ei m a g e ，i m a g ep i x e l sa r cd i v i d e di n t ot w oc l a s s e s ：t h e s t a b l ep o i n t sa n dt h ev i b r a n tp o i n t s t h ev i b r a n tp o i n t sa l es t o r e db yal i n k e dl i s t o n l yt h e v i b r a n tp o i n t sa led e a rw i t hi ne a c hi t e r a t i o nt or e d u c ec o m p u t a t i o nl o a d a n dt h e n ，t h es t o p r u l eo ft h es aa l g o r i t h mi sa l s oi m p r o v e dt oa v o i dt h ec o m p u t a t i o no fg l o b a le n e r g y t h e e x p e r i m e n tr e s u l t si n d i c a t et h a tt h ei m p r o v e ds aa l g o r i t h mb a s e do nv i b r a n tp o i n t sc a ng r e a t l y i m p r o v et h ec o m p u t a t i o n a le f f i c i e n c yw h i l em a i n t a i n i n gt h es e g m e n t a t i o ne f f e c t s e c o n d l y , t h ep a r a m e t e re s t i m a t i o nm e t h o di nm r f i ss t u d i e d t w ot r a d i t i o n a lp a r a m e t e r e s t i m a t i o na l g o r i t h m sa r ei n t r o d u c e d ：t h es a m p l et r a i n i n ga l g o r i t h ma n dt h ee ma l g o r i t h m ，a n d t h e nn u m e r i c a le x p e r i m e n t sa r ed o n et oc o m p a r ew i t ht h et w oa l g o r i t h m s a f t e r w a r d ，an o v e l e s t i m a t em e t h o db a s e do nq u a d t r e ed e c o m p o s i n gi sp r o p o s e dt oe s t i m a t et h ei s o m o r p h i c c o e f f i c i e n t si ni n h o m o g e n e o u sm a r k o vr a n d o mf i e l d t h ee x p e r i m e n tr e s u l t ss h o wt h a tt h e i s o m o r p h i cc o e f f i c i e n te s t i m a t e db yt h i sa l g o r i t h mc a ns i g n i f i c a n t l yi m p r o v et h ee f f e c to ft h e s e g m e n t a t i o na n dt h ea d a p t a b i l i t yo ft h ei m a g es e g m e n t a t i o na l g o r i t h m 1 i 摘要 k e yw o r d s ：i m a g es 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 ；v i b r a n tp o i n t s ；s i m u l a t e da n n e a l i n g ； i s o m o r p h i cc o e f f i c i e n t ；q u a d t r e ed e c o m p o s i n g i i i 独创，性j j 声，明 秉承祖国优良道德传统和学校的严谨学风郑重申明：本人所呈交的学位论文是我食 _ ，。一一 。，二+ ， ， 。 人在导师指导下进行的研究工作及取得的成果尽我所知，- 除特别加以标注和致谢的地 ：， ，t - t ， 方外，4 论文中不包含其他人的研究成果c ：与我一同工作的同志对本文所论述的工作和成 i 4 果的任何贡献均已在论文中作了明确的说明并已致谢d 一 一 ：本论文及其相关资料若有不实之处，：由本人承担一切相关责任 论文作者签名：= - ，奎酗里堡垒；游多月矽黟 学位论文使用授权声明 苯人查毯翌 垒：在导师的指导下创作完成毕业论文“本人已通过论文的答癣0 并 。 一 已经在西安理工大学申请博士硕士学位c ：本人作为学位论文著作权拥有者，同意授权 ， j ，；一， 、 西安理工大学拥有学位论文的部分使用权，即；、l 已获学位的研究生按学校规定提交 。 。 二 印刷版和电子版学位论文i 学校可以采用影印，o 缩印或其他复制手段保存研究生上交的 学位论文，可以将学位论文的全部或部分内容编人有关数据库进行检索；，2 、) 一为教学和 。1 一、 科研目的，学校可以将公开的学位论文或解密后的学位论文作为资料在图书馆、资料室 等场所或在校园网上供校内师生阅读、浏览 本人学位论文全部或部分内容的公布7 。( 包括刊登) 一授权西安理工大学研究生部办 理o ：( 保密的学位论文在解密后，适用本授权说明) ， 沦文作者签名i 导师签名i j 五磷锄序每月m 碍 第一章绪论 1 绪论 图像分割是机器视觉系统以及图像工程中的一个最基本的前期准备工作，也是由图像 处理到图像分析的关键步骤。这是因为图像的分割，目标的分离，特征的提取和参数的测 量将原始图像转化为更抽象更紧凑的形式，使得更高层的分析和理解成为可能【1 1 。由于图 像分割的复杂性，现在尚无通用理论适合各种图像的分割。 1 1 图像分割的目的和意义 图像分割是由图像处理到图像分析的关键步骤，在图像工程中占据重要的位置，一方 面，它是目标表达的基础，对特征测量有重要的影响。另一方面，因为图像分割及其基于 分割的目标表达、特征提取和参数测量等将原始图像转化为更抽象更紧凑的形式，使得更 高层的图像分析和理解成为可能。 所谓图像分割就是要将图像表示为物理上有意义的连通区域的集合，也就是根据目标 与背景的先验知识，对图像中的目标、背景进行标记，定位，然后将目标从背景或其他伪 目标中分离出来。由于这些被分割的区域在某些特性上相近，因而图像分割常用于模式识 别与图像理解以及图像压缩与编码。由分割产生的区域是图像内容的一种表示，它是对图 像进行视觉分析和模式识别的基本前提，分割结果的质量直接影响到以后的图像分析、识 别和解释的质量，具有重要的意义。图像分割的目的在于根据某些特征( 如灰度级、频谱、 纹理等) 将一幅图像分成若干有意义的区域，使得这些特征在某一区域内表现一致或相似， 而在不同区域间表现出明显的不同。 图像分割在实际中已得到了广泛的应用，例如在工业自动化，工业测量，生产线产品 检测，生产过程控制，文档图像处理，生物医学图像分析，安防监控等方面。在国防军事 领域，图像分割更是诸如遥感图像分析，目标定位，目标跟踪等技术的必不可少的前期工 作。总而言之，只要对图像进行目标的定位，测量，跟踪等，都离不开图像分割。虽然人 们对图像分割技术已经做了大量的研究，但是由于图像的复杂性，还没有一种适合于所有 图像的通用算法。因此，图像分割一直以来都是图像技术中的研究热点。 1 2 图像分割方法综述 1 2 1 传统的图像分割方法 关于图像分割技术，由于问题本身的重要性和困难性，从2 0 世纪7 0 年代起图像分割 问题就吸引了很多研究人员为之付出了巨大的努力。虽然到目前为止，还不存在一个通用 西安理工大学硕士学位论文 的完美的图像分割的方法，但是对于图像分割的一般性规律，则基本上已经达成了共识， 已经产生了相当多的研究结果和方法。在国内外学者对图像分割进行的研究中，产生了大 量的有价值的成果。根据研究的角度不同，图像分割方法大致分为基于边缘检测的分割方 法，基于阈值的分割方法和基于区域提取的分割方法等。 a 基于边缘检测的分割方法 基于边缘检测的图像分割方法是通过检测出不同区域的边界来进行分割的。图像最基 本的特征是边缘，所谓边缘是指其周围像素灰度有阶跃变化或屋顶状变化的那些像素集 合，它存在于目标与背景、目标与目标、区域与区域、基元与基元之间。经典的边缘提取 是以原始图像为基础的，对图像的每个像素考察它的某个邻域内灰度变化，利用边缘邻近 一阶或二阶方向导数的变化规律，用简单的方法检测边缘。 梯度算子是一种常用的边缘检测算子。梯度对应一阶导数，梯度算子是一阶导数算子。 对一个连续函数f ( x ，y ) ，它在位置( z ，少) 的梯度可表示为一个矢量( 两个分量分别是沿x 和】，方向的一阶导数) ： v f ( x , y ) ： c x ，g ，】r ：ii o f ，_ o f ( 1 1 ) l 掰o y j 这个矢量的幅度和方向角分别为： 聊昭( 夥) = i 颗：，l = q + 嘭 l 佗 ( 1 2 ) 伊( x ，y ) = a r c t a l l ( g ，q ) ( 1 3 ) 式( 1 2 ) 的幅度计算是以2 范数来计算的，由于涉及到平方和开方运算，计算量比较大。 在实用中为了计算简便，也可不用上述对应欧氏距离的2 范数。一种简单的方法是采用1 范数，即 l v f ( 。) i = 俐+ 例 ( 1 4 ) 另一种简单的方法是采用o o 范数，即 i 默。，i = m a x 俐，l q l ) ( 1 5 ) 以上各式中的偏导数需要对每个像素位置计算，在实际中常用小区域模板卷积来进行计 算。对g 。和g ，各用一个模板，所以需要两个模板组合起来构成一个梯度算子。根据模板 的大小，其中元素( 系数) 的不同，人们已经提出了许多不同的算子。最简单的梯度算子 是罗伯特交叉( r o b e r t sc r o s s ) 算子和索贝尔( s o b e l ) 算子，它们都用两个3 3 模板， 分别见图卜l ( a ) 和( c ) ，其中s o b e l 算子是效果比较好的一种，得到广泛应用，本文第四 章的算法中就用到了这种算子。 2 第一章绪论 田田圈圈圈圈 ( a ) r o b e r t s 算子( b ) p r e w it t 算子( c ) s o b e l 算子 ( a ) r o b e r t so p e r a t o r( b ) p r e w it to p e r a t o r( c ) s o b e lo p e r a t o r 图卜1 常用梯度算子模板 f i g l - 1g r a d i e n to p e r a t o rt e m p l a t e si nc o i n l t i o nu s e 算子运算时是采用类似卷积的方式，将模板在图像上移动并在每个位置计算对应中心 像素的梯度值，所以对一幅灰度图求梯度所得的结果是一幅梯度图。在边缘灰度值过渡比 较尖锐且图像中噪声比较小时，梯度算子工作效果较好。 二阶导数算子也常常用于边缘检测。拉普拉斯( l a p l a c i a n ) 算子是一种常用的二阶导 数算子，实际中可根据二阶导数过零点的性质来确定边缘的位置。对一个连续函数 f ( x ，y ) ，它在位置( x ，y ) 的拉普拉斯值定义为如下： v z 厂：箕+ 箕 ( 1 6 ) 舐。 砂 在图像中，计算函数的拉普拉斯值也可以借助各种模板实现。这里对模板的基本要求 是对应中心像素的系数是正的，而对应中心像素邻近像素的系数应是负的，且它们的和应 该是零。常用的两种模板见图1 - 2 ，它们均满足上面条件。 圈圈 图1 - 2 拉普拉斯算子模板 f i g l 。2t e m p l a t e so fl a p l a c i a no p e r a t o r 基于边缘检测的图像分割方法具有计算量小、速度快的优点，但是也存在着一些问题。 在图像分割时，如果对象的部分边界纹理和相邻部分背景纹理相近或者相同，则对象区域 在提取时，其边界线会出现断点，不连续，分段连续等情况。在图像有噪声干扰时，也会 使轮廓线断开，所以在对象区域提取时，未得到闭合的边界以使对象区域完整的分开，应 经历一个使不连续边界闭合的过程，即边界闭合技术。常用的边界闭合技术有基于梯度闭 合技术、霍夫变换的技术、并行区域技术、数学形态学技术等。图1 - 3 为几种常用的边缘 检测算子效果图。 3 西安理工太擘硕士学位论疋 ( a ) s o b e l 算子检测结果 ( a ) r e s u l to fs o b e lo p e m t o r ( b ) r o b e r t 葬于检测结果 ( b ) r e s u l to fr o b e r to p e r a t o r ( c ) p r e w i | 算子检测结果 c ) r e s u l to fp r e w i lo p e r a o r f d ) l a p l a c i a n 算于检删结果 ( d ) r e s u l to fl a p l a c i a no p e r a t o r 图卜3 儿种边缘检测算子效果图 f i g l 一3r e s u i t so fs e v e r a le d g e d e l e t i o n o p e e a l o r b 基于阈值的分割方法 图像的闽值分割法是经典的、流行的图像分割方法之，也是最简单的一种图像分 割方法。这种方法的关键在于寻找适当的扶度闽值。通常是根据图像的灰度直方图来选 取分割所使用的阅值。其基本思想是一般图像都由不同区域构成，其直方图呈现多峰值， 每个峰值对应一个区域，每个谷值对应一个区域，以谷值点作为闽值划分相邻峰值。图 卜4 即为敢峰直方图示意图。多闽值方法止用于图像的直方图曲线有多个峰值的情况， 分割是以各个谷值为闺值将图像划分为不同的区域，达到分割图像的目的。 阖值分割可以通过全局的信息如整个图像的灰度直方图，或者局部信息如扶度共生 矩阵实现。如果在整个图像中h 使用一个闽值，则这种方法叫做全局阈值法。反之，如 果这个图像被分割成几个区域，针对每一个区域均有一个闽值，则这种方法叫做局部闽 值法。一些学者认为也可以把闽值分割技术分为单阈值法和多阈值法。在单闽值法巾， 第一章绪论 整个图像分成两个区域，即日标对缘( 黑色) 和背景( 白色) 。当整个图像由几个带有不同 表面特征的对象组成时( 对于强度图像，表示具有不同扶度值的日标) 需要几个不同的闽 值这就是多闽值法。 目1 4 般峰直方圈 f i g l 4 d o u b l e 口e a k h i s t o g r a m ( a ) 原幽 a ) o r i g n n a li m a g e c o ) 闻值分割图 ( b ) t h r e s h o l ds c j g n e n t a t i o ni m a g e ( c ) 原幽 ( a ) o n 目n a li m a g e ( d ) 闺值分割凹 c o ) t h r e s h o l ds c g m e n t a t i o n i m a g e 幽1 4 阈值分割技果 f i g l 5 t h r e s h o l ds e g m e n t a t i o nr e s u l t 闽值分割技术是一种简单的图像分割技术，但它仅适用于高反差的简单图像的分割， 不能满足灰度渐变或以某种纹理而不是扶度束表征不同区域的那些复杂图像的分割。如 图l - 5 是对一幅简单的高反差图像的闽值分割结果，可以看h j 分割效果还是比较理想 的。而图i 一5 ( d ) 是对一幅纹理较复杂的图像的闽值分割结果，从图上可以看出分割效果 西安理工大学硕士学位论五 比较差，没有迭渤区域提取的目的。 c 基于区域提取的分割方法 区域跟踪是寻找具有相似性的像素群，它们对应某种实体世界的平面或物体，其方法 是：从某一像素出发按照属性一致性原则( 这个一致性可以是狄度级、彩色、组织、梯度 或其他特性) 逐步地增加像素，即区域增长，对由这些像素组成的区域使用某种均匀测度 函数测试其均匀性。若为真。则继续扩大区域，直到均匀测度为假。常用的方法有区域分 割、区域生长法和区域分裂合并法。 区域生长法是从满足检测准则的点开始，从各个方向丌始“生跃”物体，因为物体同 一区域中像素点的灰度级相差很小，可假设吖为一个已满足检测准则的- 4 , 块物体那 么开始检查它所有邻近点的扶度值，如果满足检测准则，即将该邻点并入上述小块中，当 邻近点被接受后“生长”成新的m ，再用得到的新村重复上面的过程，直到没有可接受 的邻近点时生长过程中止。具体做法是先对每个需要分割的区域找1 个种子像素作为生 长的起点，然后将种子像素周围邻域中与种子像素有相同的或相似性质的像素( 根据事先 确定的生长或相似准则来判定) 合并到种子像索所在的区域中。将这些新像素当作新的种 子像素继续进行上面的过程，直到再没有满足条件的像素可被包括进来，这样一个区域就 长成了。图卜6 和图卜7 演示了一个区域增长算法的例子。按照灰度相似程度的增长准则， 图像被分成了很多个区域。每个圆形区域的质心都标识出来了。 图16 原始蹦像 f i g l 一6o r i g i n a li m a g e 第一章绪论 ! ! 龟、镪 毫巴冀诚 ! 9 i 霭bj i 闰卜7 区域增眭祛分割结果 f i 9 1 - 7s e g m e n t a t i o n 碡s m t b yr e g i o n a lg r o w t h m e t h o d 区域增长型算法更多的把灰度或纹理的同一性与空间的位置联系在一起，因此能得到 满意的效果。目前，图像块的初始划分常常是固定的或是人为规定的。实际上，每幅图 像应当存在一个适合它的初始划块的最佳划分，因此有必要自适应地确定图像块的初始划 分。对于图像块的一致性度量，常采用利用扶度或灰度统计特性的方法。用灰度的方法 比较简单但效果不是很好，用灰度统计特性的方法效果比较好，但计算量大，影响处理速 度，因此也有必要探求更有效的度量图像块属性一致性的方法1 6 】。 1 2 2 当前流行的图像分割方法 近些年来，数学各分支在理论和应用上的逐步深入，使得数学形态学、模糊数学、遗 传学算法，变分法，随机场理论等在图像分割技术应用中取得很大进展，产生了不少新的 分割算法。这些新近发展起来的图像分割算法，往往是通过将数学各分支的理论与基本分 割算法相结合来实现的。这些新算法主要包括基于数学形态学的分割算法，基于模糊数学 的分割算法，基于遗传算法的分割方法，基于神经网络的分割方法，基于s n a k e 模型的 分割方法，基于水平集的分割方法，基于m r f 模型的分割方法等口l 。 a 基于数学形态学的分割算涪 基于数学形态学的分割算法基本思想是对图像用一定的结构元素进行基本操作之后， 再与原图相减，它利用图像的拓扑特性进行操作，利用集合论对图像进行非线性变换。它 最基本的操作是腐蚀和膨胀，通过它们的不同组台形成形态开、形态闭，对灰度数字图像 按照一定的结构元素取最大值和最小值，进而实现图像的分割。 b 基于模糊数学的分割算法 这类方法主要有广义模糊算予与模糊闽值法两种分割算法。广义模糊算子认为灰度的 变化是光照不均造成的，边缘是高频成分但图像边缘包括了图像其它部分的灰度信息， 西安理工大学硕士学位论文 由于量化影响，灰度值在边缘处产生突变。此算子在广义模糊集合的范围内对图像处理， 使真正的边缘处于较低灰度级，但还有些不是边缘的像素点的灰度也在较低灰度级中， 虽然算法的计算简明，且边缘细腻，但得到的边缘图会出现断线问题。模糊阈值法引入灰 度图像的模糊数学描述，通过计算图像的模糊率或模糊熵来选取图像的分割阈值，最后用 阈值法处理图像得到边界【引。 c 基于遗传算法的分割方法 此算法是j h o l l a n d 受生物进化论思想启发提出的一种优化问题的解决方法，它使用 参数编码集而不是参数本身，通过模拟进化，以适者生存的策略搜索函数的解空间。它是 在点群中而不是在单点进行寻优。遗传算法在求解过程中使用随机转换规则而不是确定性 规则来工作，它唯一需要的信息是适应值。通过对群体进行简单的复制( d u p l i c a t i o n ) 、杂 交( c r o s s o v e r ) 、变异( m u t a t i o n ) 作用完成搜索过程。此算法主要用在某些阈值法、基于参 数模型匹配算法及区域生长法中，以改进它们的性能。由于此法能进行能量函数全局最小 优化搜索，且可以降低搜索空间维数，降低算法对模板初始位置的敏感，计算时间也大为 减少。其缺点是容易收敛于局部最优。 d 基于神经网络的分割方法 人工神经网络( a r t i f i c i a l n e u r a l n e t w o r k ，a n n ) 具有自组织、自学习、自适应的性能和 非常强的非线性映射能力，适合解决背景知识不清楚、推理规则不明确和比较复杂的分类 问题，因而也适合解决比较复杂的图像分割问题【9 】。a n n 本身具有的分类属性是实现边 缘检测、区域分割的基础，基于神经网络图像分割算法是目前研究较多、文献报道较热的 分割算法。原则上讲【l0 1 ，大部分分割方法都可用人工神经网络实现。但由于a n n 用于分 割的研究起步较晚，因此，只有多层前馈神经网络，多层误差反传神经网络，自组织神经 网络，h o p f i e l d 神经网络以及满足约束的神经网络等得到了应用。 e 基于s n a k e 模型的分割方法 s n a k e 模型( 主动轮廓线模型) 是由k a s s 于1 9 8 7 年提出，s n a k e 模型思想简单，它 是一种基于二维曲线的动态生长来实现边缘检测的模型。s n a k e 模型是一种可形变模型 ( 弹性模型) ，原始的s n a k e 是由一组控制点组成的轮廓参数曲线。通过构造能量函数， 使总能量达到最小，得到一个好的轮廓。s n a k e 模型给出的是一个泛函形式，获得较好轮 廓的过程也就成为了一个泛函求极值的问题即典型的变分问题。s n a k e 模型已经被证实为 一种高效的轮廓探测法，但传统的s n a k e 方法有许多不足：分割的结果对初始点的位置 依赖很大，容易收敛到局部极值，收敛慢且不能收敛深度凹陷区域等。在传统s n a k e 模 型求解时，往往使用了图像的边缘信息，导致分割具有很强的噪音干扰。 f 基于水平集的分割方法 8 第一章绪论 水平集方法足一种新颖的求解几何曲线演化的方法，它以一种隐含的方式柬表达平面 闭台曲线或者立体闭台曲线，从而避免了对闭合曲线演化过程叶1 的跟踪，将曲线演化转化 成一个纯粹的求偏微分方程数值解问题j 。另外，水平集方法应用于几何曲线演化时， 避免了演化曲线的参数化过程。这样，曲线的拓扑结构的变化，即分裂或合并，就变得非 常自然【l2 ”i 。因此，近年来，水平集方法鹾渐成为研究的热点，并被应用于图像分割【1 。i 、 阿像平滑i l ”、运动分割以及运动目标跟踪【i ”，甚至立体视觉和图像的恢复。 水平集方法的基本思想是：先给定一封闭的初始轮廓( 如图1 8 ( a ) ) ，该初始轮廓 不断沿其法线方向向外或向内以一定的速度演化，得到曲线( 曲面) 族如图1 8 ( b ) 。 骥豳 ( a ) 含初始轮廓线的图像( b ) 亦平集刿像分割结果 ( a ) t h e i m a g e w i t h i n i t i a lc v e ( b ) s e g m e n t a t i o nr e s u l t 时l e v e ls e t m e t h o d | 璺 卜8 水平集图像分荆 f i g l 8 i m a g es e g m e n t a t i o nb y l e v e ls e t m e t h o d 水平集方法把曲线旗看作是更高维空自j 曲面的零水平集 = 0 ，而( 置，) 则被称为 水平集函数，当轮廓改变拓扑结构时，仍可以保持连续，因而从原理上保持了这种方法 很容易处理拓扑结构改变的问题。 g 基于马尔可夫随机场模型的分割方法 m r f 理论是一种分析物理现象的空间或时间相关特性的概率理论，对它的研究早在上 世纪6 0 年代就已经开始了，但是直到7 0 年代初期才获得了重要的实质性进展，即发现了 g i b b s 随机场与m r f 的等价性。这个等价关系被称为h m n r n e f s l e y - c l i f f o r d 定理mj ，根据 这个定理可以方便地使用g i b b s 随机场定义和描述i v i r f ，这已经成为贝叶斯估计问题中建 立先验概率模型的一种流行的方法，并且被广泛应用于图像分割领域。基于m r f 模型的 图像分割具有如下的优点：( 1 ) 模型的参数较少，便于处理：( 2 ) 模型具有空间约束能力，能 得到更好的分割效果：( 3 ) 基于模型的方法易于结台其他方法，易于拓展：( 4 ) 不同的模型先 验可以反映各种图像属性，方法稳定。 但是传统的基于哳啦模型的图像分割方法还有模型参数估计不准确、求解速度慢、 且容易陷入局部最优解等缺陷。对于基于m r f 模型的图像分割，一直是国内外学者的研 究热点，人们的研究主要集中在以下3 个方面：对模型参数估计算法的研究、对模型求解 算法的研究以及对模型的改进。 当前流行的图像分割算法还有基于分形理论、基于围论、基于小波理论等算法，这些 西安理工大学硕士学位论文 算法各自有自己的优势和缺点。 1 3 本文的主要研究内容 本文系统的研究了基于m r f 理论的图像分割方法。本文共分五章，具体安排如下： 第一章首先概述了图像分割的目的、意义、方法等，指出了传统的图像分割方法的优 缺点。然后概述了当前流行的图像分割方法，介绍了基于m r f 的图像分割方法的优缺点 以及当前该领域研究的热点。 第二章详细介绍了m r f 理论以及基于m r f 的图像分割实施方法，叙述了基于m r f 模型 的图像分割数学模型的建立以及求解方法。 第三章介绍了传统的求解m r f m a p 问题的算法，针对基于m r f 的图像分割模型中m a p 问题求解速度慢的特点，提出了一种基于振动点的迭代方法，并提出用链表来表示振动点 序列。该方法明显提高了模型的求解速度，并且不影响求解的精度。 第四章提出了一种基于四叉树分解的非均匀m r f 耦合系数估计方法，并成功的将此方 法运用到基于非均匀m r f 的图像分割中去，改善了图像分割效果，提高了图像分割的自适 应性。 第五章是总结与展望。在对本文工作进行总结的基础上，对于尚待研究的问题以及基 m r f 的图像分割领域的研究热点问题进行了展望。 l o 第二章图像处理中的m r f 模型 2 图像处理中的m r f 模型 2 1m r f 与邻域系统 m r f 是对马尔可夫链的推广，在纯数学理论中找不到这个概念的描述。马尔可夫链 的原始模型是俄国数学家a a m a r k o v 于1 9 0 7 年提出的，它是一类重要的随机过程。人 们在实际中经常遇到具有这种特性的随机过程：即在己知它目前的状态( 现在) 的条件下， 它未来的演变( 将来) 不依赖于它以往的演变( 过去) 。这种已知“现在”的条件下，“将 来与“过去 独立的特性称为马尔可夫性，具有马尔可夫性的随机过程叫做马尔可夫过 程1 剐。 m r f 理论是一种研究分析物理现象的空间或时间相关特性的概率理论，对它的研究 早在上世纪6 0 年代就已经开始，但是直到7 0 年代初期才获得了重要的实质性的进展，即 发现了g i b b s 随机场与m r f 场的等价性。这个等价关系被称为h a m m e r s l e y - c l i f f o r d 定理， 根据这个定理可以方便地用g i b b s 定义和描述m r f ，这已经成为贝叶斯估计问题中建立 先验概率模型的一种流行的方法，并且被广泛应用于图像处理领域中，如图像纹理模型构 造【1 9 】、图像分割【2 0 ，2 1 1 以及运动分析【2 2 】等领域。 m r f 理论为描述图像邻域像素等其它空域上的邻近特征的相互依赖关系提供了一个 十分方便而且有效的建模方法。m r f 借助条件概率的方法来描述邻域像素或特征之间的 关系。在实际应用中，m r f 模型的概率密度是通过与其对应的g i b b s 随机场的概率密度 来定义的。 对于定义在二维空间上的图像，可以将它看为一个二维随机场，自然也存在二维 m r f ，此时必须考虑空间的关系，m r f 使用图论中的概念表示二维平面上的随机场。 可以利用图来直观的表示图像中像素之间的相关模式。用图表示m r f 的优点在于比 较直观、清楚，可以将复杂的问题分解成几个简单的问题。图的这些特点可以用来表示 m r f 中的马尔可夫性，从而为贝叶斯分析带来一定的帮助。下面分别给出二维方格 n xn ( n = 1 ，2 ，) ) 中二维邻域系统和势团的概念。 定义2 1 二维邻域系统设m = m 西i ( f ，j ) n xn ，m i cn xn ) ，如果对任意的 ( f ，j ) n x n ，m 抒cn x n ，满足 1 ) ( f ，) 仨m f 2 ) 如果( 尼，) m 抒，那么( f ，j ) m 材 那么称m 打为( f ，) 的一个邻域，m 就是n xn 的一个邻域系统。 西安理工大学硕士学位论文 定义2 2 势团( c l i q u e s ) 设m 是的一个邻域系统，c 是与m 有关的n x n 上的 一个子集，如果有 1 ) c 由单个像元( 平面上的点) 组成，或者 2 ) 女口果( f ，j ) ( 尼，) ，“，j ) c ，( 尼，) c ，就得至0 ( f ，) m “ 那么称c 是与m 有关的一个势团，m 上所有的势团记为c 。下面的图2 1 和2 2 分别是 一阶和二阶邻域系统的示意图。 f i 9 2 一 a 叠q 瑚瞄 葛3 ， 盔驴饕 图2 - 2 平面上的二阶邻域系统 f i 9 2 2s e c o n do r d e rn e i g h b o r h o o do np l a n e 定义2 3 二维m r f 设x = x o ，i ，) 是二维方格n xn ( n = 1 ，2 ，厂 ) 上的随机场， m = m fl ( f ，) n xn ，m 扩n xn 是邻域系统， 如果对一切( i ，) n xn 有 p lx , t ，( f ，) n xn ，( j ，) ( 七，) ) = p ，( 尼，) m 盯j ，就称x 是关丁邻域系统m 的二维马 尔可犬随机场( m r f ) 。 1 2 萋熬蒸 第二章图像处理中的m r f 模型 2 2m r f 与glb b s 随机场的等价关系 按照上面m r f 的定义，一个m r f 可以用条件分布来描述，这个分布刻画了随机场 的局部特性。但是由局部特性来定义整个随机场有一些固有的困难。例如局部特性可能不 唯一地或一致地定义一个随机场，从局部特性获得组合分布也存在困难等。b e s a g 提出了 关于方形网格上数据的统计学模型，把m a r k o v 随机场和g i b b s 分布联系起来，解决了 该数学模型的实际应用方法。在这种数学模型指导下，使用局部的图像运算就可以获得全 局性的处理结果。 定义2 4g i b b s 随机场2 3 1 设m = i ( f ，) n xn , m i y n xn 是定义在二维网格 上的邻域系统，c 表示m 中所有的势团，c 表示c 中的元素，那么我们称随机场 x = ，i ，j n ) 符合g i b b s 分布，当且仅当其联合分布为 1 一竺盟 p ( x = x ) = 寺p r+ 厶 其中 u ( x ) = v a x ) c e c 称为能量函数，其值越小，即实现x 的能量越小，越能实现，v c ( x ) 是与势团相关的势函 数，通过适当的选择势团的势函数，可以形成多类别的g i b b s 分布的随机场。在邻域系统 确定后，知道了势团的势函数也就知道了相应纹理的统计特性，所以m r f 模型变成了势 团势函数的参数模型，其中 c ，( x ) z ：y g 一了 是归一化常数，参数丁可以控制p ( x ) 的形状，z 值越大，其分布越平坦。在应用过程中 可将丁视为常量，也可以逐渐变化。 m r f 刻画了图像邻域统计性质，而g i b b s 分布则使用联合概率刻画其全局性，b e s a g 在文献 1 7 】中发表了m r f 与g i b b s 分布的等价性的研究结果，并将其表述为如下的 h a m m e r s l e y - c l i f o r d 定理。 定理2 1h a m m e r s l e y - c l i f o r d 定理设 m = m 盯) n xn ，m 玎cn x 奶 是定义在二维网格上的邻域系统，随机场x = ，f ，j n ) 是关于邻域系统m 的m r f ， 当且仅当其联合分布是与肘有关势团的g i b b s 分布，即 西安理工大学硕士学位论文 p = 勃l 以。= 。，沏，n ) ( f ，川 e x p - z 圪( x ) 】 2 ：z o 。x p t - z v 。( x ) 一l xuc e c = p = 勤il 。= 。，( 朋，n ) m 驴) 其中 u ( x ) = 圪( x ) c e c 圪( x ) 是与势团相关的势函数，z = p 州驯r 是归一化的常数。 常用的势函数有自生模型【2 4 】、自正态模型【2 5 】、s a r 模型闭和i s i n g 模型【2 7 】等。为了 计算方便，各个势团的势函数选取一般都不复杂，本文的所有算法均采用简单的i s i n g 模型。 i s i n g 模型是e r n s ti s i n g 在研究统计力学中的铁磁学模型时提出的。该模型旨在于描 述铁磁粒子间相互作用时的能量关系，其中铁磁粒子对应两种状态u p 和d o w n ，分别对应 取值i 和1 ，这与二值图像中图像像素的二值性极为相似。i s i n g 模型的势函数的形式记 为圪( 置) = - f i x ( k xx r ) ，其中r 为s 邻域内的相邻像素，为耦合系数，用来表征势团 内的点作用的强弱。 根据m r f 与g i b b s 分布的一致性，通过能量函数确定m r f 的条件概率，从而使其 在全局上具有一致性。通过单个像素及其邻域的简单的局部交互，m r f 模型可以获得复 杂的全局行为，即计算局部的g i b b s 分布得到全局的统计结果。 2 3 基于m r f 的图像分割理论框架 基于m r f 理论的图像处理涉及到图像恢复、图像分割等图像分析领域。如上节所述， 可以根据图像中像素之间的相关模式确定先验概率。m r f 理论在实际应用中常常与统计 决策和估计理论相结合，根据一定的最优化准则来确定目标函数。最大后验概率准贝i j ( m a p ) 是最常用的最优化准则，也是m r f 建模中最常用的最优化准则。m r f 模型与m a p 准 则结合在一起就称m a p i v i r f 体系，该体系结构最早是由g e m a na n dg e m a n 在文献 2 0 中提出的，并获得及其广泛的应用。 图像分割问题实际上可以看