（计算机软件与理论专业论文）snake模型在轮廓提取中的应用.pdf

摘要 图像分割是图像处理、计算机视觉、模式识别中的核心问题，对 它们的发展有非常大的影响。目标轮廓提取是图像分割中的重要研究 内容，在图像识别与图像分析中占有重要地位，已广泛应用于军事、 医学等许多领域，取得了很多有价值的研究成果。s n a k e 模型是由k a s s 等人首次提出的算法，广泛地应用于计算机视觉及图像处理中的各个 领域，如边缘检测、图像分割、运动跟踪等，特别应用于图像中感兴 趣目标轮廓的提取。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 模型，轮廓提取，直交s n a k e 模型 i m a g es e g m e n t a t i o n i sac e n t r a lp r o b l e mo fc o m p u t e rv i s i o n c o n t o u re x t r a c t i o ni so n eo ft h em o s ti m p o r t a n ta s p e c t so fi m a g e s e g m e n t a t i o n , e x t e n s i v e l ya p p l i e di ni m a g ea n a l y s i s ，a n dh a sag r e a t s i g n i f i c a n c ei nb o t ht h e o r e t i c a lr e s e a r c ha n di n d u s t r i a la p p l i c a t i o n s s n a k e m o d e l ，w h i c hw a sf i r s ti n t r o d u c e db yk a s s ，h a sb e e nu s e de x t e n s i v e l y i nm a n ya p p l i c a t i o n so fc o m p u t e rv i s i o na n di m a g ep r o c e s s i n g ，s u c ha s e d g ed e t e c t i o n ，i m a g es e g m e n t a t i o na n dm o t i o nt r a c k i n g , p a r t i c u l a r l yt o e x t r a c to b j e c tb o u n d a r i e s w i t ht h ei n t r o d u c t i o no fh i g hl e v e li n f o r m a t i o n ， s n a k em o d e lh a sm o r es a t i s f a c t o r ye f f e c t st h a nw h a tg a i n e db yt h e t r a d i t i o n a lm e t h o dw h e n d e a l i n gw i t hd i s c o n n e c t e de d g e si nt h ei m a g e m a n yi m p r o v e m e n t si ns n a k em o d e lh a v eb e e nm a d es i n c et h e y w e r ei n t r o d u c e df i r s tb yk a s s ，h o w e v e r , t h e r ea r em a n ys n a k em o d e l w h i c hi si n a d e q u a t e ，e s p e c i a l l yf o ri t sl e s sc o m m o nm i n i m u me n e r g y s t a b i l i t ya n dt h es l o wp a c eo fc o n v e r g e n c e ，w h i c hl i m i t e do nt h e a p p l i c a t i o n t h ei m p r o v e m e n ta l g o r i t h mo fs n a k em o d e lb a s e do nt h e b r i l l l 【c o n t o u re x t r a c t i o n s i su s e dt ot r a c k i n gt h ec e n t e rc o o r d i n a t e so f t a r g e tc o n t o u r ，w h i l em a i n t a i n i n gt h eo r i g 妇lc l o s e di m a g e sr e l a t e d c h a r a c t e r i s t i c sb yu s i n gr e l a t i o n s h i pb e t w e e nt h ec e n t e rc o o r d i n a t e sa n d o u t l i n et h ec o n t o u ro ft h eo b j e c t i v e s i nt h i sw a y , t h em t eo fc o n t o u r e x t r a c t i o ni sg r e a t l ya c c e l e r a t e d e k e yw o r d ：s n a k em o d e l ，c o n t o u re x t r a c t i o n , o r t h o g o n a ls n a k em o d e l 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外， 本论文不含任何其他个人或集体已经发表或撰写过的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标 明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：葫， 谤加吖年月】叶日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅。本人授权湖南师范大学可以将本学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密回。 ( 请在以上相应方框内打“ ”) 作者签名： 导师签名： 日期：年 日期：司年 ， 月 日 g 月彩日撕 s n a k e 模型在轮廓提取中的应用 1 1 研究背景 第一章绪论 f l - - 十世纪六十年代图像处理与计算机视觉成为一门独立的工 程学科以来，尤其是多媒体技术和数字图像处理及分析理论的成熟， 图像作为更直接更丰富的信息载体，正在成为越来越重要的研究对 象。图像分析主要是对图像感兴趣的目标进行监测和测量，以获得 客观信息从而建立对图像的描述。图像分割是图像分析的重要内容， 为了识别和分析图像中的目标，需要将有关区域分离出来，在此基 础上才能对目标进一步利用，这样特征提取和测量才有可能，这个过 程即所谓图像分割。图像分割的目的是把图像空间分割成一些有意 义的区域。这里“有意义”的内涵随着解决问题的不同而不同。 图像分割是图像处理、计算机视觉、模式识别中的核心问题， 对它们的发展有非常大的影响。而目标轮廓提取又是图像分割的重 要研究内容，在图像识别与图像分析中占有相当重要的地位，已广 泛应用于军事、医学图像分析等许多领域，取得了令人瞩目的研究 成果在传统的计算机视觉领域，底层的一些处理任务，如边缘检 测、轮廓提取等，被广泛地认为是自主的自底向上的过程。7 0 年代 后期，m i t 人工智能实验室的专家m a r r 提出了计算机视觉理论【1 1 ， 他将人类视觉任务分为由低到高的三个阶段，第一阶段的主要功能 硕士学位论文 是把一些有关平面影像的重要信息清楚表现出来，主要处理边缘、 线条、角点、零交叉点等：第二阶段主要处理二维半的信息，如曲 面的方向、曲面方向及深度的不连续性等；第三阶段，三维立体模 型。这种分层计算理论对计算机视觉领域产生了深远的影响，他认 为计算机视觉领域底层的任务只能依赖于从图像本身获得的信息进 行，不能使用高层信息。以 m a r t 的计算机视觉理论为基础，人们提 出了许多图像分割方法，如经典的边缘检测算子和图像分割算法等。 但是，m a r r 的这种严格的顺序研究方法将视觉任务分成几个独立的 阶段。在使任务变得简单的同时，也将底层的误差传播到了高层，并 且没有修正的机会。 为了解决这一问题，人们提出了依赖于高层信息的图像分割的 新理论。其中最引人注目、最富有代表性的是k a s s 等人提出的基 于目标轮廓曲线能量泛函的s n a k e 模型( 或主动轮廓模型) 。他们试 图设计这样一个能量函数：其局部极值组成了可供高层视觉处理进 行选择的方案，从该组方案中选择最优的一种是由能量项的叠加来 完成。这样，在寻找显著的图像特征时，模型可以通过将图像特征 推向一个适当的局部极值点而引入高层机制。s n a k e 是内力约束和 外力引导的能量极小化样条，它可以充分利用高层信息( 轮廓曲线的 光滑性等) 。s n a k e 模型是经典力学中粒子运动的最小作用原理在目 标轮廓提取中的应用 3 1 。由最小作用原理和变分法可得到类似于牛顿 定律的偏微分方程，即力的平衡式。其申，内力对s n a k e 的形状所 产生约束，克服由于噪声等对于轮廓所造成的影响；而外力，唧图 2 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 模型最吸引人之处在于它 对于一系列应用广泛的视觉问题给出了一个统一的理论框架，在近 十几年中，已经被越来越多的研究者成功地应用于计算机视觉的多 个领域，如边缘提取、图像分割和分类、运动跟踪、3 d 重建、立体 视觉匹配等【4 】。 s n a k e 模型的提出给传统的计算机视觉理论及应用研究带来了 新的观点和思维模式。尽管关于s n a k e 模型的理论研究还很不完善， 应用研究还刚刚起步，但是它所提出的新思想及其广泛的应用已经 证明了它的价值。高层机制的引入使其区别于传统的视觉模型。对 s n a k e 模型理论的进一步研究，在计算机视觉及图像理解领域中都具 有重要的意义。 1 2 国内外研究现状 自从s n a k e 模型被提出以来，它越来越广泛地被应用于图像理 解和计算机视觉领域等多个方面： 一、应用于静态图像处理。在静态图像处理领域，s n a k e 主要用 来检测图像边缘、区域分割、轮廓提取等 5 1 1 6 。由于s n a k e 模型在处 硕士学位论文 理局部间断的边缘时常常能够得到很好的整体结果，所以逐渐在更 多的场合中得到了应用。 二、应用于序列图像处理。使用s n a k e 模型对序列图像进行目 标跟踪的思想源于k a s s ，他利用s n a k e 模型来跟踪人的唇动。此后， 从动力学的角度对s n a k e 模型的研究工作取得了很大的进 展：s z l o l i s k i 等人将s n a k e 动态模型作为k a l m a n 滤波器的系统模型， 同时考虑了系统噪声和观测噪声模型，提出了k a l m a ns n a k e 跟踪模 型用；t e r z o p o u l o s 和w a t e r s 利用多个s n a k e 模型跟踪脸部特 征；c u r w e n 等人利用s n a k e 模型跟踪三维物体的闭合轮廓线嘲。这些 应用表明s n a k e 模型很适合跟踪非刚体的运动。 三、变形模板的应用。基于s n a k e 模型的变形模板方法是s n a k e 模型的一个重要应用分支。变形模板的概念随着w i d r o w 提出的橡皮 模板阴和f i s c h l e r 的弹性模板而进入计算机视觉领域，而s n a k e 模 型的提出，正是对变形模板思想的进一步完善。在k a s s 创造性地提 出s n a k e 模型之后，变形模板算法开始真正地得到大家的认同和欢 迎。在己知目标轮廓的先验形状信息条件下，s n a k e 模型发展为更一 般化的技术一变形模板技术f l i 】。由于自然物体形状的多样性、复杂 性以及图像噪声等复杂因素的影响，在使用刚性模型提取图像轮廓 时遇到了极大的困难。基于s n a k e 模型的变形模板方法，为解决这 问题展现了令人鼓舞的前景，在轮廓提取、边缘检测、图像分割 、 ， 和分类中都获得了广泛应用。相对于刚性模板来说，变形模板使自 己发生变形以匹配到显著的图像特征。从数学角度来看，这可以解 s n a k e 模型在轮廓提取中的应用 释为有两项组成的目标函数，其中一项测量变形模板与理想轮廓的 偏差，另一项衡量变形模板与相应的图像特征的匹配程度。于是， 轮廓提取变成了使目标函数最大化或者最小化的最优化问题。变形 模板不但能够检测出目标特征，而且能够给出目标的描述，从而将 其用于分类和匹配中 四、应用于医学图像处理。对于医学图像而言，由于人体器官 形状的多样性、图像质量的改变、成像条件及噪声等因素影响，使 用传统的图像分割、轮廓提取等技术进行医学图像处理时，往往不 能取得令人满意的效果。s n a k e 模型的“高度可变形”特点，使得其 特别适合生物医学组织结构的特点，因而在各种生物医学图像解释 领域获得了广泛应用。 五、应用于三维目标重建。c o h e n 等人将s n a k e 模型进行推广 应用于三维重建领域，从磁共振( m a g n e t i cr e s o n a n c e ) 像中对左右 心室进行重建；m e n e t 等人用相似的方法对航空照片中的高架建筑， 如桥梁、楼房等进行了立体匹配，都取得了很好的效果。 国内对s n a k e 模型应用方面的研究还比较少。清华大学博士周 彦博等人使用s n a k e 模型和变分法从医学图像中提取红细膨1 2 l ；浙 江大学生物医学工程研究所的贾春光等人将遗传算法用于s n a k e 模 型，从m r 图像中提取大脑皮层外轮廓线和左侧脑室【1 3 】，都取得了 一定的效果。 硕士学位论文 1 3 本文的研究内容 s n a k e 模型的提出给传统的计算机视觉理论及应用研究带来 了新的观点和思维模式，其受到的广泛关注足以说明它的价值。但 是s n a k e 模型也存在一些固有的缺陷，例如：s n a k e 模型对畸形物体 的轮廓无法很好地提取，尤其是凹陷目标的轮廓。对此，有学者提 出了一种直交型s n a k e 模型 2 1 ，通过强调高层视觉和底层信息之间的 相互联系在曲线演化过程中的作用，使得信息的处理流程处于闭环状 态。该模型的最大优点就是计算方法简单易行，且对有凹型的物体的 轮廓也能提取出来，在一定程度上克服了传统s n a k e 模型不能提取凹 型物体的弊端。 本文首先讨论了直交s n a k e 模型的不足之处，比如：该方法的图 像处理效果仍然和传统s n a k e 模型提出的方法一样，其最终处理效果 受到初始轮廓的影响，甚至当初始轮廓偏离目标轮廓较远且迭代点集 的活动范围不够大时，会出现不连续且与目标轮廓不一致的伪轮廓； 对文献2 给出的直交s n a k e 模型公式中，目标轮廓的能量取决于包括 内部能量和外部能量等6 个分量的值，然而这6 个分量的取值的完全 是凭经验，且对不同的目标轮廓，它们的取值完全不同；当目标轮廓 曲线包含多个封闭曲线且各曲线间距离较小时，该方法由于在迭代过 程中作用区域面积较大，很难确保迭代的最终结果会与目标轮廓一致 而不受相邻曲线的影响，在提取最内轮廓曲线的过程中，使用该算法 所得到的曲线必受到相邻曲线的干扰。 为克服直交s n a k e 模型的上述不足和改善其边缘检测的性能， s n a k e 模型在轮廓提取中的应用 本文提出了一种改进的直交s n a k e 模型的方法，其基本思想是： 1 当轮廓图像存在多封闭的曲线时，选取目标轮廓的灰度值，并对 原图像进行预处理，将图像中所有灰度值与目标轮廓的灰度差超过一 个范围的像素点的像素值设为零( 如采用取模运算等) ，从而得到一个 新的关于原图像的新矩阵m 2 ； 2 基于m 2 的图像中进行目标轮廓的检测之前且在初始轮廓形 成时，设定一个自动确定更为准确的准初始轮廓点列其实现思想是 在对初始轮廓进行迭代前，找出轮廓点列的中心点坐标v 蚪，在每个初 始轮廓点与中心点v 疗连线上，求出在该方向上的灰度差的最大值从 而得到较为接近目标轮廓的初始轮廓点列：在得到较准确的初始轮 廓点列后，再进行迭代运算，从而求出与目标轮廓尽量一致的曲线点 列来。 1 4 论文结构安排 论文的结构安排如1 第一章是绪论，介绍了选题背景和意义，总结了国内外对s n a k e 模型的研究现状，并介绍了本文的研究内容。 第二章是s n a k e 模型。首先介绍了本文用到的数学预备知识， 然后简单介绍了轮廓提取方法，再对s n a k e 模型进行了综述。 第三章是一种基于m a k e 模型的边缘轮廓提取的改进算法。首 先分析了直交s n a k e 模型的优缺点，再提出了一种改进的直交 s n a k e 模型。 硕士学位论文 第四章是结束语，对本文所做的工作进行了总结，同时，对进 一步的研究工作进行了展望。 l s n a k e 模型在轮廓提取中的应用 2 1 预备知识 第二章s n a k e 模型综述 在推导s n a k e 模型时，需要用到很多数学知识，如变分法、 欧拉拉格朗日方程，b 样条函数等，下面给出这些知识的基本介绍。 2 1 1 变分法 变分法【1 4 ( v a r i a t i o n a lm e t h o d s ) 也称变分学，是1 7 世纪末开始发 展起来的数学分析的一个分支，它是研究依赖于某些未知函数的积 分型泛函极值的普通方法。简而言之，求泛函极值的方法称为变分 法，求泛函极值的问题称为变分问题( v a r i a t i o n a lp r o b l e m ) 。下面给出 变分法的基本定义： 设f = y ( x ) ) 是给定的某一函数类，r 为实数集合。如果对于函 数类f 中的每一个函数y ( x ) ，在r 中变量j 都有一个确定的数值按 照一定的规律与之对应，则称为函数y ( x ) 的泛函，记为j = j 队x ) 】或 j j 明。函数y 仅) 称为泛函j 的宗量，函数类f 称为泛函j 的定义 域，换句话说，泛函是以函数类为定义域的实值函数。 定义：设泛函 ，【y 】= 上f ( x ，y ，少协(21)0日 、7 硕士学位论文 且在区间，x l 】上f c - ，y c t ，表达式( 助+ e 7 7 1 ) 出称为泛函j m 在y = y x 】处的变分，记为= i ( 勖+ 弓田凼，其中刁o ) 是函数y ( 曲 的改变量，为方便起见，将，7 称为函数y g ) 变分，记为毋( x ) ，即 ，7 ( 力= 歹( 力一y ( 力= 砂( 功其中歹( 功，y ( x ) e c l ，而】 于是叩= 罗协) 一j ，( x ) = 缈( x ) 则泛函的变分( 2 - 1 ) 可改写为： 8 j = e ( c + ，) d x ( 2 - 2 ) 2 1 2 欧拉拉格朗日方程 设函数y ( x ) e c 2 x o ，五j ，对于泛函，陟】= 上。f ( x ，y ，y m x 在边 界条件y ( x o ) - - y o ，y ( x 1 ) = 7 l 下的极值问题，根据定理，等价于问题对于 任意函数万y ( x ) e c 2 ，而】，毋) = 以五) = o ，其变分 = e ( o + e ) 硪= 0 。由于砂= ( ，将第二项分部积分，则 甜= 【哆瓯毪+ e ( o 一丢o 哆凼= o ，由条件缈( ) = 砂( 而) = o 及缈的任 意性，由引理，得出欧拉一拉格朗日方程 ( e 一磊df ，)=o(2-3) 由于丢5 2 t ，+ + c ，“于是( 2 3 ) 还可以写成： f r y i 七f ，+ f ，t f ，= 0 ( 2 - 4 ) s n a k e 模型在轮廓提取中的应用 2 2 轮廓提取 2 2 1 引言 在基于边缘的图像分割方法中，经常使用边缘、边界及目标轮 廓三个概念，虽然在许多场合它们的含义相近，可以互换使用，但 是，严格地讲，它们还是有区别的。 图像的边缘( e d g e ) 是图像中一些特定像素的集合。图像的灰度在 这些点有显著变化，即在那些地方图像的梯度取得较大的值。图像 边缘检测和提取常常通过边缘检测算子如梯度、s o b e l 算子等结合 门限化方法进行。图像的边缘是图像处理中的一个底层概念，由一 些无序的点构成，并且对噪声比较敏感。因此，有些边缘点可能只 是由于噪声而产生，没有什么实际意义。而边界 b o u n d a r y ) 是图像的 一种特征，它是由图像的部分边缘点连接起来的几何图形，用来表 示图像中某一目标的形状。在数字图像处理领域，边界与目标轮廓 没有什么本质的区别，它们均是高层概念，含有目标的高层信息。 目标轮廓一般情况下是封闭的，它的离散模型可以用一些有序的离 散点来表示( 其余的点可通过插值求得) ，连续模型可以用参数方程或 隐式方程表示。本论文研究的轮廓提取就是要提取目标区域的边界。 2 2 2 轮廓提取的三类典型方法 传统的轮廓提取是在完成边缘检测的基础上，对于感兴趣目标 在外轮廓上进行初步的表述n 6 1 。传统轮廓提取对检测出的边缘点按 硕士学位论文 照一定的准则进行跟踪，进一步将同属于一个目标轮廓的边缘点连 接成轮廓线。在确定轮廓点之后，为进一步的图像分析、目标描述 等任务做准备，需要进行相应的轮廓跟踪。轮廓跟踪的基本方法是： 先根据某些严格的“探测准则”找到目标轮廓上的像素点，再根据 这些点的某些特性用一定的“跟踪准则”找出目标轮廓上的其他点。 目前，边缘轮廓提取的方法大致可分为三种类型： i 用边缘检测算子或高通滤波法来提取图像的边缘。 边缘检测算子利用了一阶、二阶微分算子，如罗伯特算子，拉 普拉斯算子等。这些方法都有一个明显的缺点，噪声影响大，因此 图像边缘处的噪声，会引导跟踪到与轮廓无关的方向，造成跟踪无 效的结果。 2 对图像二值化，然后作边缘跟踪。 当图像中物体与背景有明显灰度差别时，在直方图中灰度分布 就会有峰值。选取较适当的灰度阈值，使物体和背景分离，并成为 二值图像，最后用边缘跟踪算法得到物体的边缘。 3 基于图像编码的树( 图) 的搜索方法。 运用图论中深度优先，广度优先和启发式搜索法，能够克服物 7 体边缘轮廓中某些区域出现灰度模糊，回避在边缘处噪声造成的跟 踪“迷路”。对噪声不敏感也是树搜索方法的主要特点。 2 2 3 基于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 模型的独特性在于：它可以通过 综合利用从图像数据中得到的限制( 自底向上) 和各种先验知识( 自 上向下) ，把几何、估计理论、高层知识约束联系起来，保证提取出 的目标轮廓是连续光滑的闭合曲线。 2 3s n a k e 模型 2 3 1 s n a k e 模型的基本思想 s n a k e 模型f 2 1 1 又称为主动轮廓线模型( a c t i v ec o n t o u rm o d e l ) ，其 硕士学位论文 基本思想是依据图像信息进行曲线( 曲面) 演化，使其最终找到目标物 体的边界。这种方法将分割问题转化为最优化问题，利用闭合曲线 ( 或曲面) 形变的特定规律，定义度量闭合曲线( 曲面) 形变的能量函 数，通过最小化能量函数使曲线( 曲面) 逐渐逼近图像中目标物体的边 缘。 s n a k e 模型能量函数的设计原则是：有利属性要能导致能量缩 小。有利属性包括曲线( 曲面) 连续、平滑、与高梯度区域的接近以及 其他一些具体的先验知识。这样，活动轮廓在取值范围内移动时， 就能在能量函数的指导下收敛到局部边界，而且能保持曲线( 曲面) 的连续和平滑。s n a k e 模型是在曲线( 曲面) 本身的内力和图像数据的 外部约束力作用下的移动的变形轮廓。作用在s n a k e 模型上的力依 据轮廓所在的位置及其形状决定如何在空间局部的变化。内力和外 力的作用是不同的：内力起平滑约束作用，外力则引导s n a k e 模型向 图像特征移动。 2 3 2s n a k e 模型的数学模型 s n a k e 模型是在内部约束力和外部约束力作用下移动的变形轮 廓线。它可以表示为定义在s 【o ，1 】上的参数曲线，即：“s ) = ( x ( s ) ， y ( s ) ) 。与模型相关的能量函数记为e 。a k c 。e 。a k c 定义如下： e 咄= f e 岫( v ( j ) ) 丞= ”+ 吒( v o ) ) ( 2 5 ) 为s n a k e 模型的内部能量函数，定义为： 艮( 和) ) = c 位l v ( j ) 1 2 + p l v ( a ) 1 2 ) d s ( 2 - 6 ) 1 4 s n a k e 模型在轮廓提取中的应用 昱二为s n a k e 模型的外部能量函数，定义为： k ( “呦= 点纛( “呦+ 吃。岫( v ( 呦 ( 2 7 ) 在内部能量公式( 2 - 6 ) 中，s ) 、v n ( s ) 分别为曲线的一阶导数和 二阶导数。墨。定义了一个可伸长和可弯曲的轮廓( v ( s ) ) 的内部交形能 量，它包括两个参数：口控制轮廓的“应力”，它是施加于s n a k e 轮廓 曲线上相邻两点的连续约束项系数，作用是调节s n a k e 的伸缩力；声 控制轮廓的刚度。这些参数操纵着模型的物理行为和局部连续性， 点0 体现了对s n a k e 轮廓曲线连续性和平滑性的约束。内部能量函数 中加权系数口和声的选择，与图像噪声分布有关，噪声越大，盯和卢 的值也应该越大，以使s n a k e 轮廓曲线可以跨越噪声所造成的局部 极小值位置。同时，口和口的相对分布又决定着轮廓收敛的性能。由 于口控制着轮廓曲线一阶导矢模分量，口越大，轮廓收缩的速度越快； 而控制着轮廓曲线二阶导矢模分量，p 越大，轮廓越平滑。当选择 口卸时，允许s n a k e 轮廓曲线出现间断点，即不连续的轮廓曲线。 因此，通过合理地选择q 和多的值，可以使轮廓收敛至图像中比较合 理的位置。 公式( 2 7 ) 定义的e 二是外部能量函数，它决定着s n a k e 轮廓曲线 的移动方向，不同的外部能量函数引导s n a k e 轮廓曲线收敛到图像 不同的特征区域。一般而言，外部能量函数主要由两部分组成：图像 能和约束力能也一。 表示由图像力产生的图像能，它与图像特性有关，在图 像的非边缘处具有较大数值，而在边缘处数值较小。这样，由此图 硕士学位论文 像能构成的s n a k e 模型能量函数在最小化的过程中，很容易使离散 化的s n a k e 控制点到达边缘时便不再离开边缘，完成对目标轮廓的 精确定位。控制能。缸表示外部约束力能，只有在解决某种具体 问题时才予以考虑。 2 3 3s n a k e 模型的工作原理 s n a k e 模型是一条参数化的曲线，用来表征某种显著的图像特征 ( 如：感兴趣的目标轮廓等) 。模型的工作原理是：在对s n a k e 模型进行 适当的初始化之后，轮廓曲线在来自模型自身的内力和来自模型以 外的外力的共同约束下，进行“主动”地变形和位移。其中内力约 束轮廓曲线的形状特性，外力指导曲线的行为，将其拖向显著的图 像特征。模型与某一恰当定义的能量函数相关联，在模型向显著图 像特征收敛的过程中，通过实现此能量函数的最小化来实现提取显 著图像特征的任务。s n a k e 模型的运动过程就是寻找z 。f e d , 值的过 程。对于s n a k e 能量函数： = f 口i v 协) 1 2 + i v 飞s ) f ) + p ( v ( s ) ) ) 凼 ( 2 - 8 ) 当点二。达到最小化时，使用欧拉一拉格朗日方程进行求解，可以得到 如下方程： 删弋s ) 一加_ ( s ) 一v p ( v ( s ) ) = o( 2 9 ) 从这个角度上看，能量最小化方程还可以视为力平衡方程： 丘=匕(2-10) 其中，见表示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 轮廓曲线的移动而变化，最终内外力之和为零，达到平 衡状态。此时，s n a k e 轮廓曲线就停留在真实的目标轮廓上，完成提 取目标轮廓的任务。 2 3 4s n a k e 模型的两种算法实现 一、动态规划算法 在s n a k e 模型的实现方法中，最一般的方法是将求解变量积分 函数的最优问题转化为求解相应的欧拉拉格朗日方程的问题。但是 在使用欧拉拉格朗日方程方法来求解能量函数时，在最小化过程中 由于能量函数存在多个局部极小值，不能保证s n a k e 轮廓曲线收敛 到全局极值。动态规划算法( d p 算法) 以其动态灵活的特点，成为实 现s n a k e 模型的较好选择。a m i n i 等人提出使用动态规划来最小化 s n a k e 能量函数。 d p 算法是解决多阶段决策过程最优化问题的一个有效而快速 的方法。对s n a k e 能量模型的最小化可看作是一个离散的多阶段决 策处理过程。因此，最小化问题也就转化为有限阶段( 1 ，2 n ) 中每 个阶段的最小化，从一组有限的可能策略中作出决策。因此，离散 化的能量函数化为： 硕士学位论文 置“( h ，屹，以) = 置( q ，v 2 ，码) + 易( v 2 ，码，) + ， ( 2 1 1 ) 其中， 置一。( 。，v l ，e 。) = 。巨。( b 。，h ，q 。) + e 二( v j )( 2 - 1 2 ) 每个决策阶段中有v 小v i 、v 件l 三个控制点，其中v i 表示第i 个决策 阶段的阶段变量( v i 1 、v j + l 在第i 个决策阶段作为定值) ，且每个变量 只允许有m 个可能值。这种离散d p 算法的复杂度是o ( n m 3 ) 。d p 算法包括生成优化函数序列 墨 ：，在第i 个阶段进行最小化，得到 每个s i 。d p 最小化s n a k e 的能量，采用下式的s n a k e 模型： 。 s ( e “，q ) = m i i l 。 墨。“，一- 1 ) + 巨( v f 。，v f ，q 。) ( 2 1 3 ) 能量矩阵对应于优化函数 s i ，位置矩阵则存放最小化( 2 1 3 ) 的v i 。采 用d p 顺推算法求得的最小轮廓为： e m = r a i n 艮。n ，吒4 ) ( 2 - 1 4 ) 逆向跟踪位置矩阵，从而得到优化轮廓。为了发现最优化轮廓，我 们可以进行迭代处理。具体算法如下： 1 、采用( 2 11 ) 、( 2 1 2 ) 求得最小的e 协嗡l ； 2 、如果e o 忸l 与上一次迭代结果相同，停止； 3 、将s n a k e 控制点移到新的计算位置： 4 、转到步骤1 ； + 二、贪心算法( c , r e x d y 算法) 由e d i j k s t r a 提出的贪心算法是重要的算法设计方法，主要用于 求取问题的最佳解，其经典应用是解决最短路径问题。作为一种常 用的求解最优化问题的简单、迅速的方法，贪心算法总是作出在当 s n a k e 模型在轮廓提取中的应用 前看来最好的选择。它所作的每一个选择都是在当前状态下某种意 义的最好选择，即贪心选择，并希望通过每次所作的贪心选择最终 得到问题的最优解。 a m h f i 用时延离散动态规划算法进行s n a k e 能量函数的最小化， 使获得的解具有稳定性。但d p 算法的收敛速度太慢，其时间复杂 度为o ( n m 3 ) 。针对d p 算法的低效性，w i l l i a m s 使用贪心算法来实 现s n a k e 能量函数的局部最优解，时间复杂度仅为o ( m n ) 。g r e e d y 算法将总体能量的下降化为s n a k e 轮廓曲线上每个控制点能量的局 部下降，并忽略了它们之间的关联，从而减少了运算量。具体的算 法如下t 此算法对每一个控制点执行如下步骤： ( 1 ) 找到当前点( x i ，y i ) 邻近区域内各像素点的梯度值的最大值和 最小值，并赋值给m a x 和m i n a ( 2 ) 计算当前点瓴，y i ) 邻近区域内各像素点的能量值e 。l 硎。、 ，e 堍和e 瞰。 ( 3 ) 将这些能量值标准化。 ( 4 ) 在当前点o c i y i ) 邻近区域内找到能量最小的像素点。 ( 5 ) 将控制点( x i ，y i ) 更新到上一步找到的能量最小点的位置。 ( 6 ) 重复以上步骤处理下一个控制点。 2 3 5s 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 轮廓曲线放置在目标附近，作为目标轮廓 的初始估计；然后，通过构造内部能量函数和外部能量函数引入知 识约束，并最终完成对目标轮廓的提取。整个图像特征提取过程将 图像数据、初始估计、形状约束和目标轮廓融合在一起。 第二、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 模型自1 9 8 7 年由k a s s ，w i t k i n 等人提出后，给传统计算 机视觉领域带来新的思维模式，成为一种重要的目标轮廓提取方法， 受到了很多专家、学者的关注。但是对模型的理论研究还不完善， 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 轮廓曲线都有吸引作用， 分别将s n a k e 轮廓曲线拖向各自边缘，导致s n a k e 模型无法正确地 提取目标轮廓。 第四、s n a k e 模型对于凹陷目标轮廓的提取效果较差，不能检测 出凹陷部分的轮廓。当初始化轮廓的位置距离感兴趣目标轮廓较远 时，对于带有凹陷轮廓的目标，传统的s n a k e 模型不能提取出目标 2 1 ：堡主堂垡堕苎一 - _ l _ - _ _ - _ _ _ _ - _ _ _ - _ - - _ - - _ _ l _ _ _ _ - _ _ _ - _ _ - i _ _ _ _ _ _ _ _ - 一一一 轮廓。 s n a k e 模型在轮廓提取中的应用 第三章一种基于s n a k e 模型的边缘轮廓提取的改进算法 3 1 引言 使用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 模型的不足和改善 其边缘检测的性能，本章提出了一种改进的直交s n a k e 模型的方法。 3 2 轮廓提取方法概述 边缘轮廓提取在医学图像处理和计算机视觉及图形学中占有重 要作用。当前轮廓边缘提取大致可分为三种基本类型： a 基于传统灰度梯度算子( 如r o b e r t ，p r e w i t t e ，l a p l a c e 算子) 来 提取目标图像边缘： 硕士学位论文 b 基于形态学的图像处理方法( 如分水岭算法，区域填充算法等) 分离目标图像轮廓，然后采用图像阀值法进行目标轮廓的提取 c 基于图像的编码的树( 图) 的搜索方法； 在以上方法中，方法a 因算法简单，运算量小等特点受到广泛使 用和国内外专家的研究，同时，也提出了各种基于灰度梯度算子的新 方法和模型。k a s s 提出的基于s n a k e 模型的能量最小化的动态轮廓 模型在提取凸形物件轮廓有明显效果，但也存在不足之处，主要表现 在其效果受初始轮廓的影响以及局部能量最小取代全局能量最小 等问题。为此a m i n i 提出了动态轮廓程序设计算法 1 实现动态轮廓 模型以获得全局能量最小，并使解有稳定性。文献 2 】实际上是文献 【1 8 卜一种实现方法，它用数值计算方法中差