（机械设计及理论专业论文）基于活动轮廓模型的图像特征提取方法研究.pdf

摘要 摘要 轮廓提取是计算机视觉的重要研究课题，其在虚拟现实、自控车辆、机器人 环境分析、监控系统中的物体跟踪及识别、生物医学图像处理、工业在线自动检 测等方面有着广泛的应用前景。在制造领域，通过对实物或模型的测量构造物体 的几何模型，进而用于改进设计与制造，又称为反求工程技术。反求工程技术。 泛应用于科学研究、工程技术与生物医学等领域，以解决或辅助解决几何尺寸度 量、变形测量、振型测试、损伤测定、产品质量监控、实物仿形、c a d c a m 以 及医学诊断等渚多问题。在用于轮廓提取的技术中，可变形活动轮廓是目前国内 外研究的热点。 可变形活动轮廓模型的提出给传统的计算机视觉理论及应用研究带来了新的 观点和思维方式，并已发展成为计算机视觉与模式识别中最为活跃和成功的研究 领域之一。因此，基于可变形活动轮廓模型的图像处理技术研究在科学研究和工 程应用中有着重要的意义。本文选题于国家自然科学基金资助项目“由一般光照 条件下的图像生成实体形态的理论与方法研究”( 编号：5 9 9 7 5 0 5 7 ) ，系统的分 析了国内外关于可变形模型理论与应用研究的基础上，提出了一种基于动态规划 法的b 样条主动轮廓模型，作为应用例之一，利用它进行人脸图像的处理和提取 断层图像数据建立三维模型。其主要工作和所得到的结论如下： ( i ) 从几何模型、尺度空间、算法实现等三个方面对可变形活动轮廓模型的 理论研究与发展进行了综述；对经典的可变形活动轮廓模型的物理本质和具体求 解过程进行了探讨；指出了经典可变形活动轮廓模型理论上存在的问题及进一步 研究的方向。 ( 2 ) 对活动轮廓模型的尺度空间进行了改进，提出了基于多尺度和多分辨率 的可变形活动轮廓模型，该模型能有效的防止变形活动轮廓模型收敛于局部极小 值，并且提高了变形活动轮廓模型的捕捉能力，由于低分辨率时所需控制点少所 以收敛速度快。 ( 3 ) 提出了一种基于动态规划法的b 样条可变形活动轮廓模型。b 样条方法 是当前自由曲线曲面造型最为常用的方法，动态规划为解决离散最优化问题的有 效手段。该模型采用控制点控制的三次b 样条曲线段来表示活动轮廓，然后将控 制点代入动态规划法求解，从而实现对图像的轮廓提取。该模型结合了b 样条方 广东工业大学工学硕士学位诊文 法和动态规划法的优点，可以快速稳定地收敛到目标轮廓，得到的b 样条轮廓有 利于进一步的表面重建处理。 关键词：活动轮廓：轮廓提取：尺度空间；动态规划法；三维重建 i i a b s t r a c t c o n t o u re x t r a c t i o ni sa ni m p o r t a n tp r o b l e mi ne o m p u t e rv i s i o n ，a n dc a n b eu s e de x t e n s i v e l yi nm a n yf i e l d ss u c ha sv i r t u a lr e a l i t y ，a u t o n o m o u s g u i d e dv e h i c l e s ， r o b o te n v i r o n m e n t a n a l y s i s ，o b j e c tt r a c k i n ga n d r e c o g n i t i o ni nm o n i t o rs y s t e m ，b i o l o g ym e d i e e li m a g ep r o c e s s i n g ，i n d u s t r y o n l i n ea u t o m a t i cc h e c k i n ga n dr e v e r s ee n g i n e e r i n ge t c i nt h ef i e l do f m a n u f a c t u r e ，t h eg e o m e t r i em o d e l sa r ec o n s t r u c t e dt h r o u g hm e a s u r i n gt h e m ， a n dt h e nt h e yw i l lb eu s e dt oa m e l i o r a t et h ed e s i g na n dm a n u f a c t u r e t h i s p r o c e s sisc a l l e dr e v e r s ee n g i n e e r i n g r e v e r s ee n g i n e e r i n gisu s e dw i d e l y i nt h ef i e l do fs c i e n c es t u d y ，t e c h n o l o g y ，b i o m e d i a i n ee t e ，a n di su s e d f o rs e t t i i n gt h ep r o b l e mo fg e o m e t r i cs i z em e a s u r e m e n t ，t r a n s m o g r i f i c a t i o n m e a s u r e m e n t ，s c a t h em e a s u r e m e n t ，s t l r v a i u i n gt h eq u a l i t yo fm a n u f a c t u r e p r o f i l em o d e l i n g ，c a d c a m ，a n dp h y s i cd i a g n o s i se t c i nt h e s et e c h n i q u e s ， t h ed e f o r m a b l ea c t i r em o d e li sah o t p o i n tr e s e a r c h t h ed e f o r m a b l ea c t i r em o d e i s b r i n g an e w v i e w p o i n t t ot r a d i t i o n a l c o m p u t e rv e r s i o n ，a n db e c o m eo n eo ft h em o s ta c t i v ea n ds u c c e s s f u lf i e l d s i nc o m p u t e rv i s i o na n dp a t t e r nr e c o g n i t i o n t h e r e f o r e ，t h er e s e a r c ho f i m a g em a n i p u l a t i o nb a s e do nt h ed e f o r m a b l ea c t i v e m o d e l si s i m p o r t a n t s i g n i f i c a t i o no ft h e o r ya n da p p l i c a t i o n i nt h i sd is s e r t a t i o n ，b a s e do n t h e s y s t e m a t i c a l l ya n a l y s i so ft h e o r ya n da p p l i c a t i o nr e s e a r c ho nt h e d e f o r m a b l ea c t i v em o d e l s ，an e wb - s p l i n ed e f o r m a b l ea c t i r em o d e l sb a s e d o nt h ed pa p p r o a c h e si sp r o p o s e d ，a n dt h e ni ti s a p p l i e dt ot h eh u m a nf a c e d e t e c t i o na n d3 dr e e o n s t r u c t i o nb a s e do n l a y e rd a t a t h em a i nw o r ka n d c o n c l u s i o ni nt h i sd i s s e r t a t i o na r ea sf o l l o w s ： t h er e s e a r c h ，d e v e l o p m e n ta n da p p l i c a t i o no fd e f o r m a b l ea c t i v ec o n t o u r m o d e li sr e v i e w e df r o m g e o m e t r yr e p r e s e n t a t i o n ，s c a l e s p a c e sa n d o p t i m i z a t i o nm e t h o d ；t h ep h y s i c a le s s e n c ea n dt h ei d i o g r a p h i cc a l c u l a t i n g p r o c e s so ft h ec l a s s i c a ld e f o r m a b l ea c t i v ec o n t o u rm o d e la r ea l s od i s c u s s e d a n dt h e e x i s t i n gp r o b l e m sa n dp o s s i b l ef u t u r er e s e a r c ho r i e n t a t i o n sa r e i 1 1 三至三些奎兰三兰丝圭兰篁篁圣 p r e s e n t e d t h es c a l e s p a c e so fd e f o r m a b l ea c t i v ec o n t o u rm o d e lh a sb e e ni m p r o v e d ， a n dan e wm o d e lb a s e do nt h ek s m ri sp r e s e n t e d ，w h i c hc a na v o i dt h el o c a l m i n i m u me f f e c t i v e l ya n de n f o r c et h ec a p t u r ea b i l i t yo ft h ed e f o r m e da c t i v e c o n t o u rm o d e l t h ec o n v e r g e n c es p e e da l s oh a sb e e ni n c r e a s e db e c a u s eo f f e wc o n t r o l p o i n t s a b - s p l i n ed e f o r m e da c t i v e c o n t o u rm o d e lb a s e do nd p a l g o r i t h m is p r e s e n t e d b - s p l i n ei st h em o s tp o p u l a rm e t h o dt op r e s e n tf r e e f o r mc u r v e a n ds u r f a c e ，a n dd pa l g o r i t h mist h ee f f e c t i v ea p p r o a c hf o rs o l v i n gd i s c r e t e o p t i m i z a t i o np r o b l e m s i n t h i s m o d e l ，t h ed e f o r m e da c t i v ec o n t o u ri s r e p r e s e n t e db yt h ec u b i cb - s p l i n ec u r v es e g m e n t sw h i c ha r er e s t r i c t e db y t h ec o n t r o lp o i n t s ，a n dt h ec o n t r o lp o i n t sa r ea p p l i e dt ot h ec a l c u l a t i o n o fd pa l g o r i t h m ，i nt h ee n dt h ec o n t o u r o fi m a g ei sf o u n d e x p e r i m e n tr e s u l t s s h o wt h a tt h i sm o d e lc o u l de f f e c t i v e l yc o m b i n et h em e r i t so fb - s p l i n ea n d d pa l g o r i t h m ，y i e l d i n gs t a b l e ，a c c u r a t ea n df a s t e r c o n v e r g e n c e ，a n di t s r e s u l ti sf a v o r a b l ef o rs u r f a c er e c o n s t r u c t i o n k e y w o r d s ：a c t i r ec o n t o u r ，c o n t o u re x t r a c t i o n ，s c a l e s p a c e s ，d pa l g o r i t h m 3 一dr e c o n s t r u c t i o n 第一章绪论 第一章绪论 1 1 课题研究的背景和意义 边缘轮廓是人类识别物体形状的重要因素，对于一个表面均匀的物体，它的 9 0 以上的特征信息存在于边缘的形状之中，因此对这些特征集合的充分表述不仅 是计算机视觉研究的基础，而且也是医学“1 ，摄影测量”3 ，自动导航”1 ，三维重建 ”1 等实用技术的基础。然而，由于受图像的噪声、投影等诸多复杂因素的影响，传 统的理论和方法无法很好的解决这一经典难题。在这些理论中，m i t 人工智能实验 室的m a r t 的分层计算理论最具有代表性，该理论用三个独立的层次来表达视觉信 息的处理过程，而一直到2 5 维，计算只能依赖于从图像本身获得的信息进行， 不可能使用高层的信息”。这种严格的顺序的研究方法将视觉任务分成几个独立的 阶段，但同时将底层的误差传播到了高层，没有修正的机会，从而限制了它在边 缘提取、图像分割和分类、运动跟踪、3 d 重建、立体视觉匹配等计算机视觉领域 的应用。为了解决这种单向的、模块化的、自上而下的严格分层理论在实际应用 中的局限性，各国学者花费了大量的精力，提出了许多种算法，但都尚未能提供 较为满意的方案，这其中的一个主要原因在于边缘检测中的误差完全的传给了边 缘连接的过程，没有得到修正。 1 9 8 7 年的第一届国际视觉会议上，k a s s 等人提出了活动轮廓模型( a c t i v e c o i l t o l i r m o d e l ) ，根据最小化自身能量时轮廓“滑动”特点，人们又形象的称之 为“蛇”( s n a k e ) 。蛇模型针对m a r r 理论的重大缺陷作了本质上的修改”3 。 蛇模型的基本思想是：通过设计一个由外能和内能组成的能量函数，使得在 寻找显著的图像特征时，高层机制可能通过将图像特征推向一个适当的局部极值 点而与模型进行交互。在这里内能来自于轮廓本身，用于约束轮廓的形状：外能 来自图像特征，引导它的行为，使它向着显著的图像特征滑动。二者作用的结果 是最终将蛇锁定在感兴趣的图像特征的附近，准确地提取需要的数据。蛇模型的 引人之处在于它对于范围广范的一系列视觉问题给出了统一的解决方法。与其它 广东工业大学工学硕士学位论文 特征提取技术相比较，其主要优点是图像数据、初值估计、目标轮廓特征及基于 知识的约束条件都集成在一个特征提取过程中，经过适当的初始化后，它能够自 主的收敛到能量极小值状态。在最近的十多年里，众多学者在这一领域辛勤探索， 在将蛇模型和计算机视觉具体应用相结合方面取得了丰硕的成果。 例如，在医学领域引入蛇模型取得了极佳的效果。从医学图像中分割出目标 结构并获得数学表达式是临床诊断和治疗的关键一步，s i n g h 采用可变形模型1 5 分钟完成左心室( 1 e f tv e n t r i c l e ) 的分割重建，大大少于人工勾画所需的1 5 - 2 小时。针对传统可变形表面无法精确勾画出大脑皮质沟回的不足，x uc h e n g y a n g 提出了建立在g v f ( g r a d i e n tv e c t o rf l o w ) 力场基础上的可变形表面用于大脑皮质 的重建，改善了对大脑皮质沟回的描述83 。鲁爱东等提出了一种用户交互与b 样条 s n a k e ( 又称为b - - s n a k e ) 相结合的半自动分割方法，由超声图像中提取肝瘤轮廓， 并成功的应用于肝肿瘤手术仿真系统中”1 。 第二个应用的方面是脸部特征提取，脸部特征提取是人脸识别、表情识别和 人脸跟踪等人脸感知应用系统的前期工作，在身份证验证、公安档案管理、安全 监视、计算机人机交互接口及可视电话等方面有巨大的应用前景，已成为当前模 式识别领域的个热点研究课题“”“，本文在建立新模型后也将通过脸部轮廓 的提取来证明新模型的有效性。 第三个应用的方面是遥感和航空影像，可用于考古，地面景物提取，军事， 以及矿藏发现等。如武汉测绘科技大学的刘少创进行的航空影像中的湖泊和建筑 物的提取实验“。 第四个应用的方面是三维表面重建，c o h e n 等人从磁共振图像( m a g n e t i c r e s o n a n c e i m a g e s ) 中对左右心室进行了重建，取得了很好的效果“。三维重建 和快速成型相结合在工业上具有比较广阔的应用前景，从目前情况看，在检查导 弹整体装配情况、火药柱密度分布、燃气轮机空心叶片尺寸及缺陷检测、石油岩 心、金属铸件、多层印刷电路板、反应堆燃料元件等方面应用相当成功，在陶瓷 及复合材料等新材料研究方面正在进行大量工作。在一些新的领域如玩具，食品 等方面正在显示其应用价值”】。 综上所述，利用可变形模型进行图像轮廓提取，在科学研究及工程应用中有 着重要的意义。因而，在国家自然科学基金的资助下( n o 5 9 9 7 5 0 5 7 ) ，选择此课 题作为本论文的研究内容。 第一章绪论 1 2 国内外研究现状 s p e r l i n g 的立体模型( s t e r e om o d e l ) 是视觉领域较早的能量最小化模型“， 但这些早期的能量模型由于缺少引导它的交互技术( i n t e r a c t i v et e c h n i q u e ) 而在具体应用方面受到了限制，这种状况直到k a s s 的活动轮廓模型出现后才得到 根本改变。在k a s s 的活动轮廓模型提出以后，被越来越多的研究者成功地应用于 计算机视觉的许多领域，并已发展成为计算机视觉与模式识别中最为活跃和成功 的研究领域之一。许多研究人员结合自己的研究领域，针对s n a k e 模型的一些缺 陷作出了改进，使之更好的应用于实际问题。这些改进主要分为以下几个方面：1 ) 几何模型；2 ) 尺度空间；3 ) 算法实现。本节将对上述三个方面作出简要的回顾。 1 2 1 几何模型 经典的s n a k e 模型采用一组离散点来近似地表达变形轮廓，这将带来三个明显 的不足：第一，在数值计算过程中，用有限差分直接近似表达求导，引起数值不 稳定和精度降低；第二，模型的离散特性使得轮廓上两点间的情况无法确定，模 型缺乏鲁棒性；第三，为了更近似地表达活动轮廓，就必须增加离散点的数目， 这样不仅导致计算量增大，而且在收敛过程中楣邻点之间发生“碰撞”，降低了轮 廓的可操作性。针对以上缺点，不同的几何模型被提了出来，比较有代表性的有 以下几种： 几何变形模型( g e o m e t r i c a l l yd e f o r m e dm o d e l s ) ，简称为g d ms n a k e ，最初 有m “l e re ta l 在1 9 9 1 年提出“。g d ms n a k e 可以看成一个被放置于目标内部 的气球，在局部的几何驱动松弛原理作用下达到目标的边缘，它的能量函数由气 球力、图像域值和拓扑约束三项组成： ( u ) = g 。b a l l o o 一一( v ；) + 口m “靠一“( v ；) + 口，l o g y t o p a l o g y ( v t )( 1 1 ) c o h e n 等人提出了基于有限元法的可变形模型“。有限元模型采用有限个单元 之和来近似表达活动轮廓： n k = 峨仍 一1 ( 1 2 ) 其中，“。为单元结点向量，仍为形函矩阵。与经典的s n a k e 模型相比较，有眼元 ! 童三些查兰三兰堡圭兰堡丝兰 模型的优点在于使用较少的单元结点表达活动轮廓，从而减小了计算量并增加了 收敛稳定性。 s t a i b 等人提出了由傅立叶系数表达的可变形模型“： 以，= 黔卧凇瓣羽 。， 在这里，v ( o 代表轮廓坐标向量，a 。、坑、c 。、d 。为傅立叶系数。傅立叶模型的 优点在于表达紧凑，有利于整体形状性质的分析，并且可以通过谐波分董的选取 来控制轮廓表达的精度。 自m e n e t 等人在1 9 9 0 年将b 样条的概念引入活动轮廓模型( 也称为b - s n a k e ) 表达以来，一直吸引着大量的关注，模型表示为“： 曲) = v , b i ( “) ( 1 4 ) 上式中k 为控制顶点，b ，0 ) 为样条基函数，u 是描述近似曲线的参数。b - s n a k e 的 优点有以下几点：1 ) 局部控制( l o c a lc o n t r 0 1 ) 由于b 样条具有局部支柱性质， 所以改变控制点的位置仅使曲线的部分发生改变：2 ) 连续性控制( c o n t i n u i t y c o n t r 0 1 ) 对于三次b 样条( c u b i cb - s p l i n e ) 而言，由于它具有c 2 连续性，所以 在表示角点时通过对b 样条曲线求导进行，减少了计算量；3 ) 鲁棒性控制 ( r o b u s t n e s sc o n t r 0 1 ) 因为是对连续的曲线段活动轮廓进行最小化而不是对空 间稀疏分布的离散点进行，所以活动轮廓的抗噪性和解的精度都得到极大的提高； 4 ) 时间复杂度控制( t i m ec o m p l e x i t yc o n t r 0 1 ) 因为整个活动轮廓模型仅由少 量控制点控制，所以计算量减少。 1 2 2 尺度空间 k a s s 在经典s n a k e 模型中提到了尺度空间的概念，但并未进行深入的论述， 事实上，多尺度和多分辩率可以较好的解决经典s n a k e 模型的两个主要缺陷：1 ) 模型对噪声敏感，有时会收敛于伪边缘；2 ) 为了防止轮廓收敛于局部极小值，s n a k e 模型的初始位置不能离目标轮廓太远，而使用者往往很难把握这个“近”和“远”， 从而导致应用失败。多尺度方法和多分辨率方法在形式上极为接近，但在实质上 却有着本质的区别，下面我们将分别讨论。 4 第一章绪论 为了减少噪声的影响，增强s n a k e 模型在图像处理中的捕捉能力，经典s n a k e 模型往往采用高斯函数对原始图像进行平滑处理。采用不同带宽的高斯函数与同 一图像卷积，得到的一簇图像称为该图像相对于该平滑函数的尺度空间，这就是 多尺度的基本思想。国内上海交通大学黄海斌等人采用这一方法对膝关节姐r 图像 进行处理，实验结果证明，多尺度s n a k e 具有更好的抗干扰能力，并能有效的跟 踪复杂背景下的凹陷轮廓”。国外j u l i a 也在他的博士论文中对多尺度的思想进 行了较为系统的阐述“。多尺度的具体算法如下： 步骤1 ，采用标准差为o 。的大尺度高斯函数对原始图像作滤波处理。o 。的取 值应该足够大，以滤除大部分图像噪声，并弱化虚假边缘。然后确定初始活动轮 廓模型的位置，用变分法进行迭代求解，得到活动轮廓在该尺度下的最优位置。 在实际应用中，还可以增加外力约束条件以提高s n a k e 的抗干扰能力或对特定目 标的敏感程度。 步骤2 ，减小图像尺度，即以标准差为o 。= oi _ l - - 8o 的高斯函数对原始图像重 新滤波。为了减小计算量，可以只处理当前主动轮廓线邻域内的像素。当8 。= o 5 时，大部分目标边缘的移动量不超过一个像素，主动轮廓线控制点的最大间距应 也可随着图像尺度的减小而减小。 步骤3 ，重复步骤2 操作，直至o 。 d r m 。 那么d ：。d o 一仃2 。 步骤3 ，重复步骤2 操作，直至正 盯。，盯l n i i l 一般可取0 5 或1 。有时根据 实际图像情况采用其它自定义的停止准则。 图( 4 9 ) 至图( 4 i 1 ) 是采用这一方法提取轴承内径得到的实验结果，其中图 ( 4 9 ) 为原始图像，图( 4 1 0 ) 为“模糊”图像上得到的收敛结果，图( 4 1 1 ) 为“清 晰”图像上得到的最终结果。 图4 9 原始图像 f i 9 4 9t h ei n i t i a li m a g ef i g 图4 1 0 粗糙尺度收敛结果 4 1 0t h eo p ti m a ls o l u ti o na tt h ec o a r s e s e a l e 多尺度算法的优点在于：由于采用不同的尺度对原始图像进行平滑处理，较好 的克服了噪声的影响，可以逼近真实轮廓，所以提高了活动轮廓的捕捉能力。 图4 ，l l 最后结果 f i 9 4 。1 1 t h ef i n a ls o l u t i o n 广东工业大学工学硕士学位论文 4 4 基于多分辨率和多尺度( m r - m s ) 的活动轮廓模型 前面我们已经分别对多分辨率和多尺度空间的方法进行了阐述，从前面的析 我们发现这两种方法有相似的地方，主要在于： 第一，两种方法都采用了分层优化，由粗糙到精细的方法。 第二，两种方法都增强了活动轮廓模型的捕捉能力，提高了蛇的作用范围。 当然，这两种方法有着本质的差别，主要体现在： 多尺度方法中，通过选取不同的平滑函数的参数来改变图像，平滑函数的作 用只是低通滤波，参数的改变只决定滤除噪声的情况和轮廓边缘的模糊度；在多 分辨率方法中，图像的分辨率是一个随层而改变大小的量，能量最小化在不同的 分辨率上实现。多尺度方法中，图像特征随着滤波参数的不同而变的模糊；多分 辨率的情况下，图像特征在低分辨率时消失了。 本文中，为了提高活动轮廓模型的实用性能，我们决定将多尺度方法和多分 辨率的方法结合起来，建立基于多尺度和多分辨率的活动轮廓模型。多尺度和多 分辨率的活动轮廓模型的基本思想是：在多尺度的基础上引入多分辨率，这样可 以结合两种方法的优点，既能有效滤除噪声和提高蛇模型的捕捉能力，又能缩短 运行时问。基于多尺度和多分辨率的的活动轮廓模型的具体算法： 步骤1 ，采用标准差为的大尺度高斯函数对原始图像l ( x ，y ) 作滤波处理，得 到图像，y ，c r o ) 。建立以l ( x ，y ，a o ) 为原始图像的图像金字塔，然后调用公式( 4 2 2 ) 中的多分辨率的算法对l ( x ，弘a o ) 进行处理，得到尺度c r n 下的最优解。 步骤2 ，减小图相尺度，即以标准差为盯，= 仃。一曲的高斯函数对原始图像重 新滤波。得到图像t ( x ，弘呒) 。建立以，y ，仉) 为原始图像的图像金字塔，然后调 用公式( 4 2 2 ) 中的多分辨率算法对，( z ，”盯，) 进行处理得到尺度盯，下的最优解。 步骤3 ，重复步骤2 操作，直到吼 ，盯一一般可以取为0 5 或1 ，根据 实际情况亦可以采用其它自定义的停止准则。 篁塑耋茎兰竺! ：竺! ! 竺童鍪丝童堡翌 ( a ) 原始图像( b ) 中问迭代结果( c ) 最终迭代结果 ( a ) t h ei n i t i a li m a g e( b ) t h ei n t e r i mr e s u l t( c ) t h ef i n a ls o l u t i o n 图4 ，1 2 采用多分辨率多尺度方法处理人脑m r i 图像的过程图 f i g4 1 2t h ed e t e c t i o no fm r ib r a i ni t a g eb a s e do nt h em s m rm e t h o d ( a ) 原始图像( b ) 中间迭代结果( c ) 最终迭代结果 ( a ) t h ei n i t i a li m a g e ( b ) t h ei n t e r i mr e s u l t( c ) t h ef i n a ls o l u t i o n 图4 1 2 采用多分辨率多尺度方法处理人脑m r i 图像的过程| 璺| f i g4 1 2t h ed e t e c t i o no fm r ib r a i ni m a g eb a s e do nt h em s m rm e t h o d 4 5 小结 在这一章里我们首先分别对多分辨率和多尺度的问题进行了较为详细的介 绍，然后在此基础上建立了新型的能量场模型基于m r m s 的蛇轮廓模型。由于 到此为止我们还没有论述到d p 算法，所以仅在轮廓由b 样条控制点表示和采用变 分求解的基础上来证明多尺度和多分变率相结合的有效性，在后面论述了d p 算法 后，我们将把它和多尺度和多分辨率进行结合，论述轮廓由b 样条表示和采用d p 算法求解的多尺度和多分辨率。 第五章基于动态规划算法的b 样条主动轮廓模型 5 1 引言 上两章分别介绍了b 样条、b 样条活动轮廓模型初始化及基于m r m s 的活动轮 廓模型。在采用变分法解活动轮廓模型时存在以下缺陷：( 1 ) ，无法引入硬约束； ( 2 ) ，不能保证解的全局优化；( 3 ) ，要求计算离散数据的高阶导数。还有一些方法 也被科研工作者用来求解活动轮廓模型，包括有限元法、贪- t l , 算法、最小二乘法、 l a i 等人提出的m i n m a x 算法等”。而动态规划( d y n a m i cp r o g r a m m i n g 以下简称d p ) 算法用于解视觉领域的变分问题，可以有效的克服经典求解方法的主要不足o “。 所以本文采用动态规划法求解基于l f 【r m s 的b 样条活动轮廓模型。本章结构如下： 首先较为详细的介绍动态规划的相关知识；然后给出采用动态规划法求解基于 m r m s 的b 样条活动轮廓模型的具体过程；最后采用新模型进行人脸识别实验。 5 2 动态规划算法 5 2 1 动态规划算法的发展和基本思想 动态规划是运筹学的一个分支，是求解决策过程( d e c i s i o np r o c e s s ) 最优化 的数学方法“”“”“。2 0 世纪5 0 年代初美国数学家r e b e l l m a n 等人在研究多阶 段决策过程( m u l t i s t e pd e c i s i o np r o c e s s ) 的优化问题时，提出了著名的最优化 原理( p r i n c i p l eo fo p t i m a l i t y ) ，把多阶段过程转化为一系列单阶段问题，逐个 求解，创立了解决这类过程优化问题的新方法一一动态规划“”。 一般来说，只要该问题可以划分成规模更小的子问题，并且原问题的最优解 中包含了子问题的最优解( 即满足最优子化原理) ，则可以考虑用动态规划解决。 动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解 为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决 最优化问题的算法策略。动态规划法所针对的问题有一个显著的特征，即它所对 应的子问题树中的子问题呈现大量的重复。动态规划法的关键就在于，对于重复 出现的予问题，只在第一次遇到时求解，并把答案保存起来，让以后再遇到时直 接引用，不必重新求解。 动态规划开始只是应用于多阶段决策性问题，后来渐渐被发展为解决离散最 优化问题的有效手段，进一步应用于一些连续性问题上。 5 2 2 动态规划算法的基本要素 一个多阶段决策过程最优化问题的动态规划模型( 见图5 1 ) 通常包含以下要 素： 1 阶段阶段( s t e p ) 是对整个过程的自然划分。通常根据时间顺序或空间特 征来划分阶段，以便按阶段的次序解优化问题。阶段变量一般用k = l ，2 ，n 表示。 在图( 5 1 ) 中由a 出发为k = l ，由b ，( i = l ，2 ) 出发为k = 2 ，依此下去从d ( i = l ，2 ，3 ) 出发为k = 4 ，共n = 4 个阶段。 l c i 、 6 、 ，b 1 c 2 一 6 u 1 x d 2 、b 2 8 8 c 3 、 、 ，d 3 d 3 、c 4 - 7 图5 1 一个动态规划问题 f i 9 5 1 a e x a m p l eo fd p 2 状态状态( s t a t e ) 表示每个阶段开始时过程所处的自然状况。它应浚能够 描述过程的特征并且具有无后向性，即当某阶段的状态给定时，这个阶段以后过 程的演变与该阶段以前各阶段的状态无关，即每个状态都是过去历史的一个完整 总结。通常还要求状态是直接或间接可以观测的。 描述状态的变量称状态变量( s t a t ev a r i a b l e ) 。变量允许取值的范围称允许 状态集合( s e to fa d m i s s i b l e s t a t e s ) 。用x k 表示第k 阶段的状态变量，它可以 匠， 广东工业大学工学硕十学位论文 是个数或一个向量。用x 。表示第k 阶段的允许状态集合。在图( 5 1 ) 中x ：可取 b 。，色，x ：= 忙。，b 。) 。n 个阶段的决策过程有n + 1 个状态变量，x 。表示演变的结 果，在图( 5 1 ) 中z ，取e 。 根据过程演变的具体情况，状态变量可以是离散的或连续的。为了计算的方 便有时将连续变量离散化；为了分析的方便有时又将离散变量视为连续的。状态 变量简称为状态。 3 决策当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段 的某个状态，这种选择手段称为决策( d e c i s i o n ) ，在最优控制问题中也称为控制 ( c o n t r 0 1 ) 。描述决策的变量称决策变量( d e c i s i o nv a r i a b l e ) 。变量允许取值的 范围称允许决策集合( s e to fa d m i s s i b l ed e c i s i o n s ) 。用“女( ) 表示第k 阶段处 于状态以时的决策变量，它是瓤的函数，用u 。( x k ) 表示了的允许决策集合。在 图( 5 。1 ) 中“：( 玩) 可取c 。，c ：，c ，。决策变量简称决策。 4 策略决策组成的序列称为策略( p o l i c y ) 。由初始状态置开始的全过程的 策略记作p l 。( z 1 ) ，即： p h ( x 1 ) = 协i ( x i ) ，“2 ( x 2 ) ，“。( ) ，。( 5 1 ) 由第k 阶段的状态札开始到终止状态的后部子过程的策略记作p 。( “) ，即： p h ( x k ) = 恤( 也) ，“t + i ( x 女h ) ，u 。( x 。) ( 5 2 ) 类似地，由第k 到第j 阶段的子过程的策略记作 p 蚵( & ) = 恤女( 工女) ，“k + l ( 工t + 1 ) ，“f ( 上f ) j( 5 3 ) 对于每一个阶段k 的某一给定的状态t ，可供选择的策略p 。( ) 有一定的范围， 称为允许策略集合( s e to fa d m i s s i b l ep o l i c i e s ) ，用墨。( _ ) ，吃( ) ，( 以) 表示。 5 状态转移方程 在确定性过程中，一旦某阶段的状态和决策为己知，下阶 段的状态便完全确定。用状态转移方程( e q u a t i o no fs t a t e ) 表示这种演变规律， 写作： x k + l = 瓦( 气，u ( 也) ) ，k = 1 , 2 ，n( 5 4 ) 在图( 5 1 ) 中状态转移方程为： x = “女( )( 5 5 ) 6 指标函数和最优值函数指标函数( o b j e c t i v e f u n c t i o n ) 是衡量过程优劣 的数量指标，它是关于策略的数量函数，从阶段k 到阶段n 的指标函数用 ( ，p “( & ) ) 表示，k = 1 ，2 ，n 。能够用动态规划解决的问题的指标函数应具有 篁薹塞垂垂呈! 篁鎏篁! 堂丝圭垫墼堡堡型：= = = = = 一 可分离性，即可表为x k , ，k 。的函数，记为： ( 坼，“，魂，x ) = 纯( 以，“ 。畋“。( x ，x ) ) ( 5 6 ， 其中函数纯是一个关于变量k 。单调递增的函数。这一性质保证了最优化原理 ( p r i n c i p l eo fo p t i m a l i t y ) 的成立，是动态规划的适用前提。过程在第j 阶段的 阶段指标取决于状态x j 和决策“，用v j ( x 。，“，) 表示。阶段k 到阶段n 的指标由 v ，( j = k ，k + l ，n ) 组成，常见的形式有以下三种。 阶段指标之和，即： ( 文，“，x n + i ) = v 小，“，) ( 5 7 ) j = k 阶段指标之积，即： v k n ( x k ，“，工。) = n p 如，w ，) ( 5 8 ) j = k 阶段指标之极大( 或极小) ，即： v k n ( x k ) g t k ，, x n + t ) = m a ；x 。_ ( _ ，“少r 醢”廖，“，) ( 5 9 ) 这些形式下第k 到第j 阶段子过程的指标函数为( ，x 。，x + 1 ) 。可以 发现，上述( 3 ) 一( 5 ) 三个指标函数的形式都满足最优性原理。在图( 5 1 ) 中指标函 数为( 3 ) 的形式，其中v f ( x ，u ，) 是边 的权( 边的长度) ，“，“，) 表示从j ， 出发根据决策“，o ) 下一步所到达的节点。根据状态转移方程，指标函数还可 以表示为状态和策略p 。的函数，即 稚，p 。) 。在讯给定时指标函数对p 。的 最优值称为最优值函数( o p t i m a lv a l u ef u n c t i o n ) ，记作 ( x 女) ，即： l ( x k ) = o p ty h ( 工k ，p 蛔) ( 5 1 0 ) p h e 最 ( 3 ) 其中o p t 可根据具体情况取n l a x 或r a i n 。上式的意义是，对于某个阶段k 的某个状 态也，从该阶段k 到最终目标阶段n 的最优指标函数值等于从k 出发取遍所有能 策略p 。所得到的最优指标值中最优的一个。 7 最优策略和最优轨线使指标函数达到最优值的策略是从k 开始的后部 子过程的最优策略，记作 p 二= 色：，。，龆：j ， ( 5 。1 1 ) p i 又是全过程的最优策略，简称最优策略( o p t i m a lp o l i c y ) 。从初始状态 查三些奎兰三兰堡圭兰堡丝圣 x t ( _ z ? ) x l ( = x 1 牢) 出发，过程按照p 二和状态转移方程演变所经历的状态序列 k ：，x ：，工：+ ) 称最优轨线( o p t i m a l t r a j e c t o r y ) 。 5 2 3 动态规划算法的基本定理和基本方程 动态规划发展的早期阶段，从简单逻辑出发给出了所谓最优性原理，然后在 最优策略存在的前提下导出基本方程，再由这个方程求解最优策略。后来在动态 规划的应用过程中发现，最优性原理不是对任何决策过程普遍成立，它与基本方 程不是无条件等价，二者之间也不存在任何确定的蕴含关系。基本方程在动态规 划中起着更为本质的作用。 对于初始状态x ，x ，策略p 二= 恤：卅：j 是最优策略的充要条件是对于任意 的k ，1 k = n ，有 ( 5 1 2 ) 由基本定理可以得到如下推论：若j 口2 p 。( ) 是最优策略，则对于任意的 k ，l k n ，它的子策略p 二对于由x 1 和p i 。确定的以石：为起点的第k 到n 后部子过 程而言，也是最优策略。 上述推论称为最优化原理，它给出了最优策略的必要条件，通常略述为：不 论过去的状态和决策如何，对于前面的决策形成的当前的状态而言，余下的各个 决策必定构成最优策略。 根据基本定理的推论可以得到动态规划的基本方程： j 2 。嚣) 如”t ， + ，+ - 瞳5 2 瓦故，“t ) 2 = 1 2 一(513)u “一【jlb 【 + l ( + 1 ) = 6 ( x ) 其中正+ 、( j 。) = 5 ( x 。) 是决策过程的终端条件，艿为一个已知函数。当工。只取固 定的状态时称固定终端；当+ 可在终端集合x 。中变动时称自由终端。最终要求 的最优指标函数满足公式( 5 1 4 ) ： 叩f 以。) = 叩f 口( x 。) ) e x l (