（计算机应用技术专业论文）灰度图像分割算法的研究.pdf

山东大学硕士学位论文 摘要 人通过视觉感知半数以上的外界信息，因此图像处理领域的进展对我们感知 外部世界有很大帮助。随着计算机处理速度的提高和图像处理技术的成熟，数字 图像作为一种直接而丰富的信息载体，已成为计算机科学领域越来越重要的研究 对象。 在对图像的研究和应用中，人们往往只对图像的某些部分感兴趣，这些部分 被称为前景，余下的部分被称为背景。图像分割就是将图像分为各具特色的区域 并提取出前景的技术和过程。另一方面，前景的边界是我们感兴趣的对象，如果 我们能检测出这些边缘，就可以提取出前景。这种基于边缘的图像分割，也被称 为边缘检测。 本文首先简单介绍了一些常见的边缘检测方法和算子，给出了不同算子对同 一幅图像进行分割的结果，并对结果进行了分析。随后讨论了基于可变模型的分 割。可变模型分参数可变模型和几何可变模型两大类，前者通过参数显式表达， 如本文将讨论s n a k e 模型。后者，又称水平集方法( l e v e ls e tm e t h o d ) ，通过 高维函数隐含表达目标对象。本文将以可变模型为重点，详细讨论基于这两类模 型的分割方法。 s n a k e ，又被称为参数主动轮廓，是定义在图像域中的一条弹性曲线。该曲 线在内部能量和以边界为特征的外部能量的驱使下不断变形。当总能量达到局部 极小时，曲线就刻画了目标的边界，从而给出了目标边缘一个有意义的描述。本 文详细描述了s n a k e 模型的原理，算法，并给出了实例。但该方法也存在某些不 足，针对这些不足，本文介绍了相应的改进。 水平集方法是本文的重中之重。该模型因有较好的数学理论基础，具有很强 的改变拓扑的能力。在分割复杂结构时有着巨大的优势。本文详细描述了该模型 的原理，算法和重要的改进，并在原始f a s tm a r c h i n gm e t h o d s 的基础上做了较 大的改动，使之能够处理由离散点构成的区域。还针对水平集方法效率不高的缺 点提出了一种改进方案：预先将象素分为两类，对两类象素定义不同的演化速度， 以达到提高效率的目的，并在最后通过实验证明了新思路的优势。 山东大学硕士学位论文 关键词灰度图像；图像分割；边缘检测；水平集方法：s n a k e 模型 l i 山东大学硕士学位论文 a b s t r a c t p e o p l ep e r c e i v eo v e rh a l fo f t h ei n f o r m a t i o nt h r o u g hv i s i o n s o ，t h ed e v e l o p m e n ti n t h ef i e l do fi m a g ep r o c e s s i n gd o e s 懈ag r e a tf a v o rt oo u rp e r c e p t i o no ft h eo u t s i d e w i t l lt h ei m p r o v e m e n to ft h ep r o c e s s i n ga b i l i t i e so ft h ec o m p u t e r s a n dt h em a l u r i t y o f t h ei m a g ep r o c e s s i n gt e c h n i q u e s ，d i 舀t a ii m a g e s ，w h i c hc a r r ya b u n d a n ti n f o r m a t i o n d i r e c t l y , b e c o m em o r ea n dn r ei m p o r t a n t a st h er e s e a r c ho b j e c t si nt h ef i e l do f c o m p m e r s c i e n c e i nt h er e s e a r c ha n dt h eu s eo f t h ei m a g e s ，p e o p l ea r eo n l yi n t e r e s t e di ns o m ep a r t s ，w e c a l lt h e mf o r e g r o u n d s t h er e s tc a l l e db a c k g r o u n d s1 h et e c h n i q u e sa n dt h ep r o c e s s e s 幻d i v i d et h ei m a g ei n t os e v e r a lp a r t sw h i c hh a v ed i f f e r e n tf e a t u r e sa n dt op i e ku p f o r e g r o u n da r ec a l l e di m a g es e g m e n t a t i o n o nt h eo t h e rh a n d , t h eb o u n d a r i e so ft h e f o r e g r o u n d sa l et h ee d g e sw ea r ei n t e r e s t e di n o n c et h e s ee d g e sa r ed e t e c t e d , t h e f o r e g r o u n d sa r ep i c k e du p t h e s ee d g eb a s e di m a g es e g m e n t a t i o na l s oc a l l e de d g e d e t e e t i o n i nt h eb e g i n n i n g ，t h i st h e w sw i l li n t r o d u c es o m ec o m i n o ne d g ed e t e c t i o nm e t h o d sa n d o p e r a t o r sb r i e f l y , c o m p a r ea n da n a l y s i st h e d i f f e r e n tr e s u l t sp r o c 豁s e db yt h e s e o p e r a t o r s t h e nw ew i l ld i s c u s st h ed e f o r m a b l em o d e l sb a s e ds e g m e n t a t i o n t h i s m e t h o dc 锄b ed i v i d e di n t ot w oc l a s s e s ：p a r a m e t r i cd e f o r m a b l em o d e la n dg e o m e t r i c d e f o r m a b l em o d e l i nt h ef i r s tc l a s s ，t h eb o n n d a 拶a n dt h es h a p eo ft h eo b j e c ta g e r e p r e s e n t e db yt h ep a r a m e t e r se x p l i c i t l y , l i k es n a k e i nt h es e c o n dc l a s s , 1 1 1 e ya r e r e p r e s e n t e db yh i g h e rd i m e n s i o nf i n l e f i o n si n e x p l i c i f l y w ew i l lf o c u so i lt h i sm o d e l ， g i v eap a 币c l l l 盯d e s c r i p f i o no f t h e s et w oc l a s s e si nt h i st h e s i s s n a k e , a l s oc a l l e dp a r a m e t r i cj s c t i v ec o n t o u r , i sa l le l a s t i cc u r v ed e f i n e di ni m a g ef i e l d t h ee n r v ed e f o r m e dd r i v e nb yi n n e re n e r g yo ft h ec u r v ea n do u t e re n e r g yc o r r e l a t e d 1 1 1 山东大学硕士学位论文 w i mt h ee d g e s ，t h ec u r v ed e s c r i b e st h eb o u n d a r yo ft h eo b j e c t sw h e nt h et o t a le n e r g y r e a c h e dt h el o c a lm i n i m u m , s ow ec a ng e tam e a n i n g f u ld e s c r i p t i o no ft h eb o u n d a r y w ew i ne x p a t i a t eo nt h et h e o r i e s t h ea l g o r i t h m sa n dt h ei n s t a n c e s t h em o d e l sh a v e s o m es h o r t c o m i n g s s ow ew i l li n t r o d u c ec o r r e s p o n d i n gi m p r o v e m e n t s t h es e c o n dc l a s s ，a l s oc a l l e dl e v e ls e tm e t h o d , i sb u i l to nap e r f e c tf o u n d a t i o no f m a t h e m a t i c s s oi ti sg o o da td e a l i n gw i t ht h ec h a n g e so ft h et o p o l o g i e s ，a n da l w a y s u s e di nt h es e g m e n t a t i o no fc o m p l e xs f 九l c t u r e s w ew i l lf o c u so hl h el e v e ls e t m e t h o d ；d e s c r i b et h et h e o r y , t h ea l g o r i t h m sa n dt h ei m p o r t a n ti m p r o v e m e n t sa b o u ti t a n dia l s om a d es o m ei m p r o v e m e n t st ot h eo r i g i n a lf a s tm a r c h i n gm e t h o d at o p r o c e s st h ep o i n tc l o u d t oe n h a n c et h ep e r f o r m a n c ea n dt h ee f f i c i e n c yo f t h el e v e ls e t m e t h o d ，w ed i v i d et h ep i x e l si n t ot w oc l a s s t h e nd e f i n ed i f f e r e n te v o l v es p e e d s t h er e s u l t so f t h ee x p e r i m e n t ss h o w e du st h ea d v a n t a g e so f t h en e wm e t h o d k e yw o r d s ：g r a ys c a i ei m a g e ；i m a g es e g m e n t a t i o n ；e d g ed e t e c t i o n ；l e v e ls e t m e t h o d ；s n a k em o d e l 1 v 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：日期：丝望：竺翌 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 觯一名：和 山东大学硕士学位论文 第1 章绪论 1 1 课题的研究背景与意义 人通过视觉感知半数以上的外界信息，因此图像处理领域的进展对我们感知 外部世界有很大的帮助。随着信息时代特别是数字时代的来临，再加上计算机处 理速度的提高和图像处理技术的成熟，数字图像作为一种直接而内容丰富的 信息载体已成为计算机科学领域越来越重要的研究对象。 在对图像的研究和应用中，人们往往只对图像的某些部分感兴趣，通常称这 些部分为前景，余下的部分通常被称为背景。图像分割就是将图像分为各具特色 的区域并提取出前景的技术和过程。 图像分割在很多方面，如医学图像分析“1 ，交通监控等，都有着非常广泛 的应用啪，具有重要的意义0 1 。 ( 1 ) 分割的结果常用于图像分析，如不同形式图像的配准与融合，结构的测 量，图像重建以及运动跟踪等。 ( 2 ) 在系统仿真，效果评估，图像的3 d 重建以及三维定位等可视化系统 中，图像分割都是预处理的重要步骤。 ( 3 ) 图像分割可在不丢失有用信息的前提下进行数据压缩，这就降低了传输 的带宽，对提高图像在因特网上的传输速度至关重要。 ( 4 ) 分割后的图像与噪声的关系减弱，具有降噪功能，便于图像的理解。 1 2 目前研究现状 多年来，图像分割一直受到人们的高度重视，分割算法层出不穷m 。 ( 1 ) 阈值分割方法。 对灰度图像的阈值分割嘟脚州，需要先确定一个或几个处于灰度范围之中的 值作为阈值，然后将图像中象素的灰度值都与该阈值进行比较，根据比较结果将 象素分为两类或多类。这几类象素一般分属图像的多类区域，从而达到分割的目 山东大学硕士学位论文 的。如果需要我们将象素分为两类，那么，如何确定一个最优阈值就是分割的关 键。现有的大部分算法都集中在如何确定阀值上。根据分割算法所依据的特征， 该类方法又可以被分为以下几类：直方图与直方图变换法、最大类空间方差法、 最小误差法与均匀化误差法、共生矩阵法、最大熵法、简单统计法与局部特性法、 概率松弛法、模糊集法、特征空间聚类法、基于过渡区的阂值选取法等。 ( 2 ) 边缘检测。 边缘检测以图像一阶导数的极值或二阶导数过零点作为判断边缘点的基本 依据。经典的边缘检测方法是构造差分算子用以检测图像灰度阶跃变化，进行分 割。如r o b e r tc r o s s 算子、s o b e l 算子、p r e w i t t 算子、l a p l a c e 算子等。除上述 这些比较简单的算子外，边缘检测还包括以下几类：c a n n y 边缘检测”，多尺度 方法嘲、多分辨分法、基于边界曲线拟合方法、状态空间搜索法、动态规划法、 哈夫变换等。 ( 3 ) 基于区域的分割方法。 区域分割1 的实质就是把具有某种相似性质的象素连通起来，从而得到 所需区域的方法。它利用了图像空间的局部信息，可有效的克服其它方法存在的 图像分割空间不连续的缺点，但它通常也会造成图像的过度分割。该类方法通常 又可分为三小类：1 ) 区域生长，是按区域属性特征一致的准则，将属性相近的 连通象素分到同一区域的分割方法；2 ) 区域分裂，则是按区域问属性特征不一 致的准则，将属性不同的连通象素分割到不同区域的分割方法；3 ) 综合利用上 述两种方法，就是分裂合并的方法。 ( 4 ) 基于可变模型的分割方法 这类方法将图像，初始轮廓，目标轮廓和约束相统一。其原理是在图像空间 内给定初始的曲线或曲面，同时定义与曲线或曲面形状相关的内能及与图像相关 的外能。其中，内能也称弹力，控制曲线或曲面的光滑与连续，外能一般与边缘 特征相关，如梯度，以促使轮廓向边缘移动。在两者的共同作用下，轮廓发生变 形，最后得到图像前景的连续边缘。可变模型一般可被分为参数可变模型和几何 可变模型两大类。前者可由参数显式表达，如s n a k e 模型“”。后者需要通过高维 函数隐含表达，如l e v e ls e t 方法“。 ( 5 ) 其他分割方法 2 山东大学硕士学位论文 这些分割方法通常同特定的理论工具结合，如数字形态学“1 ，模糊理论，人 工神经网络，遗传算法，小波分析和变换等。现在，图像分割领域不断地 有新方法、新概念引入，原有方法也彼此相互融合，取长补短，综合运用。 1 3 本文贡献 本文首先对常用的图像分割及边缘检测算法做了回顾和总结，并在后续章节 对几类常用的分割和边缘检测方法的原理，算法步骤和优缺点做了详细的描述。 本文用较大的篇幅叙述了基于l e v e ls e t 的分割方法，针对传统l e v e ls e t 方法无法分割由离散点组成的区域的缺点，本文在第四章提出了一种扩展的f a s t m a r c h i n g 方法。该方法首先借助d e l a u n a y 三角剖分法，将点集所在的区域划分 为三角面网络，使互不关联的点转化成彼此邻接的三角形。然后修改原有的f a s t m a r c h i n g 方法，使之以三角形为处理的基本单元，相较原有方法中的基本单元 象素，大大减少了单元的数目，可以高效地获取由离散点组成的区域。 针对原有水平集图像分割算法的不足，本文还在第五章提出了一种加速算 法，以提高效率。该方法首先依据象素点邻近区域灰度值的方差将图像象素分为 性质相近类和性质相异类两类，然后分别定义两类中曲线点的演化速度。在定义 速度时我们又引入了一个度量区域相异度。最后通过实验，我们可以证明新 方法兼顾了效率与定位的准确。 1 4 各章节安排 第一章简单描述了图像分割与数字图像边缘检测的背景与意义，对其当前的 研究现状做了概括和总结，并简要的介绍了自己所做的工作。 第二章对图像分割与数字图像的边缘检测作了细致的描述，介绍了常用的算 法和算子。对比并分析了r o b e r tc r o s s ，s o b e l ，p r e w i t t ，l a p l a c e 算子和 c a n n y 边缘检测对同一幅图像处理的结果。 第三章详细插述了s n a k e 模型的原理，算法，步骤及不足，并介绍了相应的 改进算法和g v f ( g r a d i e n tv e c t o rf l o ) 。 第四章是本文的重点，详细描述了水平集方法的原理，算法和步骤，并介绍 了两个重要的改进算法一一窄带( n a r r o wb a n d ) 算法和f a s tm a r c h i n g 山东大学硕士学位论文 m e t h o d s ( f m m ) ，随后提出了一种扩展的f m m ，并结合了d e l a u n a y 三角化，用以 分割由离散点组成的区域。 第五章提出了一种基于l e v e ls e t 的分割方法，该方法首先根据图像象素与 其邻近象素的灰度方差，将这些象素分为两类，然后分别定义两类中曲线点的演 化速度。在定义速度时我们又引入区域相异度。最后，用实验证明了该方法兼顾 了效率与定位的准确。 本文第六章是对课题现有成果的总结和未来发展的展望。 4 山东大学硕士学位论文 第2 章图像分割及边缘检测 在对图像的研究和应用中，人们往往只对图像中的某些部分感兴趣，这些部 分通常被称为前景，余下的部分通常被称为背景。图像分割就是将图像分为各具 特色的区域并提取出前景的技术和过程。作为图像分析中的关键一步，图像分割 在图像工程中占有重要的地位。一方面它是目标表达的基础，对特征的测量有巨 大的影响；另一方面，它将原始图像抽象为更紧凑的形式，使更高层次的图像分 析和理解成为可能。 2 1 图像分割 图像分割是三维重建的基础，也是数字图像处理的基本问题和难题之一。在 交通图像分析，视频压缩，目标跟踪和机器视觉等方面都有着广泛的应用。是当 今计算机图形学领域中的一个热点问题。 2 ，2 边缘检测 灰度图像是由图像的亮度函数来描述的，其边缘可以定义为图像亮度函数不 连续的点的集合，描述了灰度函数的局部突变。既然灰度图像的边缘检测就是要 保留图像灰度值变化剧烈的区域，从数学上，最直观的方法就是微分( 对于数字 图像来说就是差分) ，从信号处理的角度看，可以说是用高通滤波器保留高频信 号，这是最为关键的一步。如有必要，滤波前也可以对输入图像进行消除噪声的 处理。用于图像识别的边缘检测方法输出的一般是二值图像，即只有黑白两个灰 度的图像，其中一个灰度代表边缘，另一个代表背景。有时还需要把边缘细化为 一个象素的宽度。总的说来边缘提取的步骤有如下几步：1 ) 去噪声；2 ) 微分运 算；3 ) 二值化处理；4 ) 细化。 第二步是关键，有不少书就直接把第二步和第三步合称为边缘检测，本文也 采用这种定义。 前面提到过，图像中前景与背景间灰度的变化意味着边界的存在，所以我们 只需扫描整幅图像比较相临象索，找出这种灰度的变化也就找出了边界。梯度算 山东大学硕士学位论文 子是一种较为基础的方法。梯度对应一阶导数，因而梯度算子便是一阶导数算予， 在图像边缘灰度值过渡比较尖锐而且图像噪声较少时，检测结果让人比较满意。 首先介绍一下图像梯度的概念。给定一幅二维图像f ( x , y ) ，在坐标点( x , y ) 处 f ( x ，y ) 的梯度被定义为一个矢量： 可化y ) 缸 钞( x ，y ) 咖 它有两条重要性质： 1 ) 函数f ( x ，力的值变化最大的方向为梯度的方向。 2 ) 梯度的幅度用g 【， ，y ) 】表示，则有： g 【厂( x ，力1 - 根据这两条性质，可以得出这样的结论：梯度的数值就是y ( x ，力在其变化最大 的方向上，单位距离上所改变的量。 对于二维数字图像，该式中的偏导数可以用后向差分来近似表示。 o f ( = x , 一y ) 。厂( x ，y ) 一( x + 1 ，y ) 蹦 a f ( = x , 一y ) 厂( 工，y ) 一厂( x ，y + 1 ) 哕 经过这种近似后，梯度的模可以写成 ( u 毽”】= j f ( x , y ) - - f ( x + l , y ) j + f ( x , y ) - - f ( x , y + 1 ) j 但经过这种近似后，计算仍然复杂，所以我们一般又采用下列近似公式 g f ( x , y ) l = v ( x , y ) - f ( x + l , y ) l + i 傀力一( 五y + 1 ) l ( 1 1 ) 需要注意的是，对图像的最后一行和最后一列的象素不能求梯度，我们一般重复 其前一行及前一列的结果。 山东大学硕士学位论文 普通的梯度算子有r o b e r tc r o s s 算子，s o b e l 算子，p r e w i t t 算子。它们都 是模板运算，为此我们需要首先定义一个模板，模板的大小以3 x 3 较常见，也有 2 2 ，5 5 或更大尺寸的。运算时，需对图像进行扫描，把模板中心与图像的每 一个象素相对应，然后用与模板对应的公式，对中心点及其周围点的象素值进行 运算( 当然，根据模板的不同，靠近图像边赛的几行或几列不能进行这种运算) ， 得出的结果即可作为输出图像中对应点的象素值。 1 r o b e r to r o s s 边缘检测算子 r o b e r tc r o s s 边缘检测算予采用了如下所示的两个2 * 2 模板： 1001 o 一1 - 1 0 所对应公式分别为 g 【i j 】h = f i j - f 【i + l j + 1 i c 计i j ，2 f i + i j l - f i j + 1 i 可见其是一种利用局部差分方法寻找边缘的算子，对前景背景对比度高且低噪音 的图像响应最好。 一l a ) 理想的二值图像 b ) r c 垂直方向处理后的结果c ) r c 水平方向处理后的结果 圈2 - 1r o b e r tc r o s s 边缘检测算子对2 值图像的检测结果 2 $ o b e l 边缘检测算子 s o b e l 算予采用卷积核对图像边缘进行检测，采用如下两个卷积核： l 2 l l0 1 o00 20 2 一l 一2 1 lo 一1 两个卷积核对应的公式如下： g 【i j 】h = l f 【i * 1 j + l 】十2 f 【i j + 1 】+ f 【i + 1 j + 1 】一f 【i m j - 1 - 2 f i , j 1 - f l i + i j - 1 l 7 山东大学硕士学位论文 g i j 】，= i f 【i l j 1 + 2 f i 一1 j l + f 【i i j + 1 - f 【i + l j 1 1 2 f i + l j l - f i i + l j + l l l 前一个核可以较好得检测出水平边缘，后一个核可以较好得检测出垂直边 缘。对一点而言，需要比较两个卷积结果，将大的值作为该点的输出值，以得到 最后的结果。 a ) s o b e l 垂直方向上处理后的结果b ) s o b e l 水平方向上处理后的结果 图2 - 2s o b e l 边缘检测算子对2 值图像的检测结果 3 p r e w i t t 边缘检测算子 p r e w i t t 算子，和s o b e l 算子相类似，也采用了两个卷积核，如下： 一1 一l l 1o 一1 o0ol0 - i l1l1o l 对应公式分别是： c , - i j h = l f 【i - l j + 1 】+ f 【i j + l 】+ f 【i + 1 j + l 】趣i 一1 j h - f i j - 1 】一f 【i + i d - 1 】l g i j ，= l f 【i - 1 j - 1 q s i - 1 j l + t i 一1 j + 1 】f 【i + l j - 1 】- f 【i + l j 】一f f i + i j + 1 i 4 l a p l a c e 边缘检测算子。 与上面提到的算子相比，l a p l a c e 算子可以算得上是一种比较“另类”的方 法，其特点是具有各向同性的性质，即其对边缘的检测结果与边缘的方向无关， 因此计算时只需使用一个模板，这就使其计算量较前面提到的方法小，l a p l a c e 算子的模板有很多，以下是比较常见的3 3 模板和5 x 5 模版： 山东大学硕士学位论文 一1 一l l 一181 一l 一1 一l o1o l 一41 olo 一2 4 4 4 2 40 8o一4 482 48 4 4o8o一4 2 4 4 4 2 圆 9 山东大学硕士学位论文 该方法在使用时要提供一些参数，用于控制算法的性能，实际上，对于不同的图 像以及不同的精度要求，也应该提供不同的参数，以达到最佳效果。c a n n y 边缘 检测的步骤如下： 1 ) 计算g a u s s i a n 函数沿x ，y 方向一阶导数的卷积值。 2 ) 计算图像中各象素点的梯度方向和大小。 3 ) 计算图像中各点沿梯度方向求二阶导数的值。 4 ) 在图像中标记出沿梯度方向求得的二阶导数的零点。 5 ) 检查在4 中作过标记的点。凡梯度超过高阈值的点均标记为真正的边缘；凡 梯度位于高低阂值之间的点均标记为候选的边缘；凡是梯度低于低闺值的点 均视为非边缘。 6 ) 多尺度特征合成。 它也有模板运算方法，模板的大小与提供的参数有关，标准的大小差不多是 1 7 + 1 7 ，可以根据算子的可分离性使用快速算法。否则，算法速度会非常慢。 a ) l e n a 原图 c ) 大尺度下检测到的边缘d ) 多尺度合成的边缘 图2 - 4c a n n y 边缘检测实例 i o j搏；，lln心娆 门；lllli，0“m 山东大学硕士学位论文 下面我们比较上述算子的检测结果，图2 - 5 显示了不同的边缘检测算子对同 一幅图像的检测结果，可以看出差别还是很大的。c a n n y 的结果最好，能够检测 出全部边缘，并且保持连续，其次是l a p l a c e 算子，结果可以接受，但边缘有缺 失。s o b e l 和p r e w i t t 算子的结果差不多，最差的是r o b e r tc r o s s ，结果让人无 法接受。 e ) l a p i a c e 的结果f ) c a n n y 的结果 图2 - 5 不同的边缘检测算子对同一幅图像的检测结果 山东大学硕士学位论文 第3 章s n a k e 模型 s n a k e ，又称参数主动轮廓，是定义在图像域中的一条弹性曲线“”。该曲线 在曲线内部能量和图像外部能量的驱使下不断变形，当总能量达到局部极小时， 曲线所处位置也就刻画了图像的某些特征。我们可以选用不同的内，外部能量表 达式，以获取不同的图像特征。如果我们选择了边界特征，就认为最终得到的演 化曲线给出了目标边缘一个有意义的描述。因此，s n a k e 模型被广泛应用于轮廓 提取，边缘检测，运动跟踪，形状建模中。 3 1 原理 基于s n a k e 模型的方法是一个自顶向下的过程“7 加”。该模型有两个主要特 点：一方面，它将目标轮廓的初始估计、曲线性质、图像信息和先验知识融于一 个统一的过程：另一方面，它在分割目标边缘的过程中寻找能量泛函的局部极小 点，而非全局极小点。 传统s n a k e 模型可以用曲线v ( s ) = ( x ( s ) y ( s ) ) ，s 【o ，l 】来定义。它是以归一化 的弧长作参数的曲线表达形式。采用s n a k e 模型提取目标轮廓的过程，就是使如 下的能量函数达到一个理想的局部极小的过程： i 百( = l ( 舷。( + 耐( v ) ) 出 ( 3 1 ) b e 。( v ) = 丢【口( s ) 卜( s ) 1 2 十觑s ) l 矿o ) 1 2 】 e 。( v ) 代表曲线的内部能量，一阶导数项i v ( s ) 1 2 是曲线的弹性能量，二阶导 数项i v 。( s ) 1 2 是曲线的刚性能量，口( s ) ，卢( s ) 为权重，其大小对曲线的性质有重 要的影响。当两者都不为零时，对应的轮廓线是一条连续的光滑曲线。当a ( s o ) 为 零时，曲线在v ( s o ) 处不连续，当卢( ) 为零时，曲线在v ( s o ) 处会产生角点。当卢 的值很大时，使e ( v ) 取极小值的闭合曲线是一个圆，非闭合曲线是一条直线。 e 0 ( v ) 代表曲线的外部能量，其值在我们感兴趣的特征处应较小。当曲线被用于 山东大学硕士学位论文 寻找图像边缘时，常定义为如下形式： = 一i v g + j “圳 其中，“y ) 为图像，q 为标准偏差是口的二维商斯函数，v 是梯度算子。 等式( 3 - 1 ) 可以写成如下离散形式： e ( 功= ( o ) 十( f ) ) 着哆= ( 墨，砖) = ( x q h ) ，y q h ) ) ，o ) 可写作如下形式 点k o ) = l q 一叶一1 1 2 2 h 2 + 属i 吁一，一2 v j + 吩。1 2 2 h 4 当口o ) = 口，卢( s ) = ，均 为实数时，最小化等式( 3 - i ) 中的能量函数可以得到如下两个独立的欧拉等式： 删，+ 肛+ 擎；o ，o f v + f l y ( 4 ) + 阜：o ( 3 屹) 其中嘶令埘= 等，删= 等。上面的欧拉等式可写为 砒叱卜：魏冀麓氙磊揣磐0 。2 ”s ，+ 届“( q 一2 q + 1 + “2 ) + ( 五( j ) ，工( ，) ) = ( 3 _ 3 ) 写成矩阵腻协始蓦：，脯对角艨 a = cb 口 口b bcba4 口bcba abcb 口 a 口bcb 6a dbo 卟系， 如果将v 看作s 和时间t 的函数v ( s ，0 ，我们使用迭代的方法解上述两个方程， 因为每次迭代，外力的导数都会改变彳，所以为加快迭代的速度，我们假设工，工 在一个步长内是不变的。 4 + z ( k 。，) = 一，( t 一墨。) ，以+ 五( 曩，靠。) = 一y ( 咒一”1 ) ，为步长 山东大学硕士学位论文 迭代公式如下： 墨：似+ ) 一1 ( y 一l - l ( x , _ l ，妇。) ) ，咒= ( a 十) 一1 ( y 靠l 一工( k l ，肛。) ) ( 3 4 ) 3 2g v f a ) 原始图像，初始点和迭代结果 b ) 梯度图像，初始点和迭代结果 图3 1s n a k e 实例 ( a ) 传统s n a k e 模型中轮廓演变的过程。蓝 ( b ) 传统s m k e 模型中的外力示意图 色线代表初始轮廓，绿色线代表形变过程中 的轮廓，红色线代表最终得到的结果。 图3 - 2 传统s n a k e 模型 正如文献 1 9 2 0 中指出的那样，传统的s n a k e 模型，有以下两个缺点，见 图3 2 ： ( 1 ) 外力场的捕获范围很小，因而初始曲线必须接近真实物体边缘。 ( 2 ) 难以收敛到凹腔边界。 针对第一个问题，文献 2 4 提出了压迫力( p r e s s u r ef o r c e s ) ，文献 3 4 提出了潜在距离( d i s t a n c ep o t e n t i a l s ) ，文献 4 0 提出了多分辨率方法 ( m u l t i r e s o l u t i o n m e t h o d s ) 等方法。这些方法的基本思路都是扩大外部力的 山东大学硕士学位论文 捕获范围。 针对第二个问题，可以使用前面提到的压迫力( p r e s s u r ef o r c e s ) ，文献 3 8 提出的域适应( d o m a i n a d a p t i v i t y ) ，文献 3 9 提出的控制点( c o n t r o l p o i n t s ) ，和文献 4 1 提出的方向吸引力( d i r e c t i o n a la t t r a c t i o n s ) 。 但前面提到的这些方法都有很大的局限性，会带来一系列的问题。以压迫 力为例，如果力太弱，曲线就无法进入深度凹陷区域。太强，曲线就会越过弱边 界，这两方面是对立的，很难协调。因此，在很多情况下，难以找到，甚至不存 在这样一个合适的值。 a ) g v f 中轮廓演变的过程b ) g v f 场中的外力示意图( c ) 局部放大图。在用蓝色框图围 起的部分，梯度有向下的分量 图3 - 3g v f 为解决前述的两个问题，文献 1 9 提出了了梯度矢量流( g r a d i e n tv e c t o r f l o w ，g 、，f ) 模型，该模型相比以前提出的改进有以下几个优势：1 ) 该模型对 初始位置不敏感，可以在物体外部，内部，甚至穿越物体。2 ) 该模型不需要预 先指定扩展还是收缩曲线或曲面。3 ) 扩大了s n a k e 模型的捕捉范围。在离边界 较远的情况下，初试曲线依然可以寻找到边界。并使轮廓能很好地进入目标的 凹陷区，见图3 3 。但需要在整幅图像上迭代求解一个偏微分方程组，计算量很 大。 为图像，定义g v f 场为矿 y ) = m 旺，y ) ，v ，力】 s = j 弘( + + + v ；) + i 夥 2 卜一夥1 2 姗， ( 3 - 5 ) 使上式最小的r ( x ，y ) 就是我们要求的g v f 场。对这个隐式方程，可以用迭 带法求解，相当耗时，对分辨率高的图像，实用性不高。 山东大学硕士学位论文 第4 章水平集方法 l e v e ls e t 方法是s e t h i a n 在研究曲线以曲率相关的速度演化时提出来的“”， 用于描述曲线或曲面的演化过程，是处理封闭界面在演化过程中几何拓扑变化的 有力工具。在分割复杂解剖结构时有着很大的优势。最近几年在医学图像处理、 晶体生长模拟“”以及中心路径提取等领域得到了广泛的应用。l e v e ls e t 方法 的优点是嘲：形变自由度大，可以分割出相当复杂的物体边界；具有很强的 改变拓扑的能力；具有较强的鲁棒性等m 。 4 1 原理 首先，简要介绍一下l e v e ls e t 方法的原理。r ( t ) ：【o ，佃) _ r 叶表一个封 闭界面，行为维数，当刀= 2 时，r ( f ) 为二维平面上的一条曲线，万= 3 时，为三 维空间中的一个曲面。l e v e ls e t 方法的主要思想就是将r q ) 看作高一维函数的 零水平集。 由于所要分割的是乎面图像，我们将把注意力集中在膨= 2 的情况上。给定 平面上的一条初始封闭曲线，以曲线为界，整个平面被划分为曲线内，陆线上和 曲线外三部分。定义平面上的距离函数，z = 庐( ( x ，y ) ，f ) ，( x ，y ) r 2 , t 【o ，+ o o ) ， 当点位于曲线内部时，距离为负，点在外部时，距离为正。f 表示时间。 矿( j ，y ，f = o ) = d ，( j ，j ，) r 2 ( 4 - 1 ) 舒守x ( a ) 2 维平面图( b ) 平面所有点的值构成的空心锥体 图4 1 蓝色圆弧代表零水平集，圆弧内部用黄色表示，红色圆 弧位于蓝色圆弧外 山东大学硕士学位论文 图4 - 1 是平面上一个圆的l e v e ls e t 表示。如果我们将如，平面上所有的点到圆 的距离作为z 值，就构成了三维空间中的一个空心锥体，胛平面与锥体的交线 为圆的轮廓。这样，在任意时刻，z 值为零的点必然位于曲线上，曲线上点的z 值也必然为零。此时的曲线就可以看作是距离函数庐的零水平集( z e r o l e v e ls e t ) 。 因为在演化的过程中，曲线上的点始终都满足下面的方程： 矿( x ，y ，f ) = 0 ( 4 2 ) 式( 4 - 2 ) 两边对t 求导，得： 吮妄+ 哆鲁+ 谚= o ( 4 - 3 ) 即。 ( 蜥) 哼，亳) + 破= 。( 4 - 4 ) 由于曲线在切线方向上的运动对曲线的外形没有影响，因此，我们限定曲线 上各个点是沿着曲线的法线方向，即曲线上各点对x , y 的梯度方向，运动的。这 样，在时刻t ，曲线在点y ) 处的速度f 可表示为： f ( q d ，( 0 ) = ( 毛，咒) 栉 其中，如一尚一是梯度算子，w 嘏缈 那么，整个曲线的演化可以用下面的方程表示： f ( x o ) ，y ( f ) ) i v 矿i 一饵= 0 ( 4 5 ) 以= f ( x o ) ，( ，) ) i v 妒l ( 4 - 6 ) 式( 4 - i ) 和式( 4 - 6 ) 构成了带初值的偏微分方程，比初始问题多了一维( 时 间) ，这样，曲线演化的问题就转化为一个微分方程求解的过程。 我们可以采用相对简单的方法：用对t 的i 阶泰勒展开式近似- - d , 段时间血 后的妒值。 “墨力，f + a f ) “声“五力，f ) + ( a f ) 旃 ( 4 7 ) 山东大学硕士学位论文 4 2 数值解法 依据式( 4 7 ) ，为了得到出时间后平面上各点的庐值，我们需要知道当前平 面各点的妒值和谚。破可通过下式近似： 谚( m a ( f ( j ( f ) y ( f ) ) ，o ) v + + m i n ( f ( x ( o ，( ，) ) ，o ) v 一) ) 其中 v 一= ( 1 l l i n ( 嘎l o ) 2 + n 塌x ( d 髫，o ) 2v + = ( n l a ) 【( d 学，o ) 2 + m i l l ( 口了，o ) 2 + i i l i n ( d 彤，o ) 2 + m a r c o , ：；，o ) 2 ) + m a x c o , ：= ；，o ) 2 + 1 1 1 i n ( d 嚣，o ) 2 ) d 十，d 一分别代表前向，后向差分算子，表达式如下： 叼= 警一华骨学一华 也，几分别代表x , y 方向的步长。那式( 4 7 ) 可写为 烈 n t + 们“庐n ，) + o ( r 聊辽h 晚加) ) ，0 矿 ( 4 - 8 ) + n 蛔r 砸x 加) ) ，o y 旷” 由于l e v e ls e l ：方法中，瞌线的演化速度是曲率相关的，所以速度f 还可以写成 矿( r ) ，r 代表曲率，曲率可由下式计算得到： r ：叁生2 _ 竺芝+ ：必2 ( 髭+ 刃) 恐 4 3 曲线演化的步骤 ( 1 ) 构造初始曲线，并计算平面上的点到曲线的距离，作为平面点o = o 时 刻的舻值。 ( 2 ) o = o + a t ，计算曲线上各点的演化速度f ，通过式( 4 - 8 ) 计算下一时 刻曲面上点的函数值。 ( 3 ) 对函数值进行平滑，消除歧义点和冗余点。 山东大学硕士学位论文 (