（计算机应用技术专业论文）2d角色动画变形.pdf

浙江犬学硕l 论文 2 d 角色动国变彤 摘要 汁算机动画是计算机图形学和艺术相结合的产物一二维多边形形体渐变是 二维计算机动画中的一项基本技术，它是指从源多边形形体到目标多边形形体 的视觉光滑过渡。二维形体渐变的研究包含两个问题：顶点对应问题和顶点插 值路径问题。在过去的几1 年罩，人们针。对这两个问题陆续提出了许多算法， 用以实现二维形体之间的光滑过渡；本文在分析和比较已有的二：维多边形形体 渐变算法的基础上，提出了基于视觉特征的平面形体的渐变方法，并在此基础 上给出了一个2 d 角色动画变形方法，可以实现包含多区域的形体的变形。 基于视觉特征的平面形体渐变提出了一个新的方法来建立两个平面形体特 征点之间的对应。算法从源和目标形体中抽取特征点，利用以特征点为中心的 矩形区域图像信息以及特征点之间的距离，给出一个新的特征点相似度的度 量。利用动态编程方法找到特征点之间的优化的对应关系。 2 d 角色动画变形方法可以对由多个封闭区域组成的形体进行变形。该方法 主要包括四个部分：区域分段模块，该模块将用户输入的轮廓线表示的动域角 色分解成各个部分，以便后面使用；区域匹配模块，该模块将起始帧和终止帧 分解出来的区域对应起来；对应区域插值模块，在该模块中使用基于视觉特征 的平面形体渐变方法插值生成每对区域中间渐变区域；区域调整和组合模块， 这一模块将前面生成的各个中间帧渐变区域调整、组合成最终的中间帧，并输 出。 关键词：二维平面形体渐变，视觉特征，区域匹配，插值，动画 浙江大学硕l 论文2 d 角色动1 日i l 变形 a b s t r a c t c o m p m e ra n i m a t i o ni sr e s u l to fc o m b i n a t i o no fc o m p u t e rg r a p h i c sa n da r t 2 d s h a p eb l e n d i n gi se l e m e n t a r yt e c h n i q u ei n2 dc o m p u t e ra n i m a t i o n 2 ds h a p e b l e n d i n gi sav i s u a l l ys m o o t ht r a n s f o r m a t i o nf r o ms o u r e es h a p et od e s t i n a t i o ns h a p e i th a sb e e nw i d e l yu s e di n2 dc h a r a c t e ra n i m a t i o n ，p a t t e r nm a t c h i n g ，a n dg e o m e t r i c m o d e l i n g t h e r ea r et w op r o b l e m si n2 ds h a p eb l e n d i n g ：v e r t e xc o r r e s p o n d e n c ea n d v e r t e xi n t e r p o l a t i o np a t h i np a s ts e v e r a ld e c a d e s ，m a n ya l g o r i t h m sw e r ep r o p o s e dt o a c h i e v es m o o t h2 ds h a p eb l e n d i n g ，i nt h i sd i s s e r t a t i o n ，t h ep l a n a rs h a p eb l e n d i n g a l g o r i t h mb a s e do nv i s u a lf e a t u r ei sp r o p o s e d ，a n dt h e2 dc h a r a c t e ra n i m a t i o n b l e n d i n gm e t h o db a s e do nt h i sa l g o r i t h mi sp r e s e n t e d w h i c hc a nd e a lw i t l ls h a p e s c o m p o s e do fs e v e r a lc l o s e dr e g i o n s an o v e la p p r o a c hf o re s t a b l i s h i n gv e r t e xc o r r e s p o n d e n c eb e t w e e nt w op l a n a r s h a p e si sp r e s e n t e di np l a n a rs h a p eb l e n d i n ga l g o r i t h mb a s e d o nv i s u a lf e a t u r e t h e m e t h o de x t r a c t sf e a t u r ep o i n t sf r o ms o u r c ea n dt a r g e ts h a p e s ，an e ws i m i l a r i t ym e t r i c b e t w e e nt w of e a t u r ep o i n t si sd e f i n e du s i n gt h er e c t a l l g u l a rr e g i o nc e n t r a l i z e do nt h e m a n dd i s t a n c eb e t w e e nf e a t u r ep o i n t s t h eo p t i m a lc o r r e s p o n d e n c ei sf o u n db yd y n a m i c p r o g r a m m i n gt e c h n i q u e 2 dc h a r a c t e ra n i m a t i o nb l e n d i n gc a nd e a lw i t hs h a p e sc o m p o s e do fs e v e r a l c l o s e dr e g i o n s t h em e t h o dc o n s i s t so ff o u rp a r t s ，n a m e l y ，r e g i o nd e c o m p o s i t i o n m o d e l ，i nw h i c hi n p u ts h a p e sa r ed e c o m p o s e dt od i f f e r e n tr e g i o n s ；r e g i o nm a t c h i n g m o d e l ，w h i c he s t a b l i s h e sc o r r e s p o n d e n c eb e t w e e nr e g i o n s ；r e g i o ni n t e r p o l a t i n gm o d e l ， i nw h i c hc o r r e s p o n d i n gr e g i o n sa r ei n t e r p o l a t e dt op r o d u c eb l e n d i n gr e g i o n s ；r e g i o n a d j u s t m e n ta n dc o m b i n a t i o nm o d e l ，w h i c ha d j u s t si n t e r m e d i a t eb l e n d i n gr e g i o n sa n d c o m b i n e st h e mt of i r m lr e s u l t k e y w o r d s ：p l a n a ri m a g eb l e n d i n g ，v i s u a lf e a t u r e ，r e g i o nm a t c h i n g ，i n t e r p o l a t i o n ， a n i m a t i o n 1 1 浙江人学硕士论文2 1 ) 角色动嘶变形 1 1 引言 第一章绪论 在过去的几十年里，随着计算机技术在电影，电视等领域的普及应用，人 们对各种电脑特技已经屡见不鲜。例如，迪期尼公司出品的众多动画片，日本 的卡通动画片。至于影片指环王、后天中的壮观场面，看过这些影片 的人应该都印象深刻。计算机动画则是用于生产这些电脑特技一项专门的技 术。在2 l 世纪的今天，计算机动画已经渗透进人们生活的每一方而。 单纯从字面上来看，“动两”可以理解为运动的画稿，或者是运动的画 面。著名动画大师约翰哈拉斯有句名言：“动画的本质在于运动”，的确“运 动”是动画的根本属性。动画是利用人眼睛的一种错觉而产生的。人类的视觉 具有暂留的特性。在人的眼睛看到某个物体以后，此物体的影像在人的视觉里 作短暂的停留，至少要延迟1 2 4 秒。如果快速地播放系列连续的丽面，在前 一幅画面还没有在入的视觉里消失时播放下一幅画面，就可以造成种连续变 化的视觉效果。 计算机动画是计算机图形学和艺术相结合的产物，它是伴随着计算机硬件 和图形算法高速发展而发展起来的一门高新技术，它综合利用计算机科学、艺 术、数学、物理学和其它相关学科的知识在计算机上生成绚丽多彩的连续的虚 拟真实画面，给人们提供了一个充分展示个人想象力和岂术才能的新天地。简 单地讲，计算机动画是指用绘制程序， 三成系列的景物画面，其中当前帧画商 是对前一帧画面的部分修改。计算机动画所扛成的是一个虚拟的世界，画面中 的物体并不需要真正去建造，物体、虚拟摄像机的运动也不会受到什么限制， 动画师可以随心所欲地创造他的虚幻世界。 1 2 计算机动磊的发展历史及其意义 美国是最早发展计算机动画的地方，在上个世纪七十年代末便利用电脑模 拟人物活动。 浙江大学硕士论文 2 d 伯色动i 瓠变形 传统的动画是由画师先在画纸上手绘真人的动作，然后再复制于卡通人物 之上。直至2 0 世纪7 0 年代后期，电脑技术发展迅速的纽约技术学院的电脑 绘图实验室导师丽蓓卡亚伦女士将录像带 ：的舞蹈员影像投射在电脑显示器 ：，然后利用电脑绘图记录影像的动作，然后描摹轮廓。 1 9 8 2 年左右，荚围 麻省理工学院及纽约技术学院同时利用光学追踪技术记录人体动作：演员身体 的各部份都被安上发光物体，在指定的拍摄范围内移动，同时有数部摄影机拍 摄其动作，然后经电脑系统分析光点的运动，再产生立体的活动影像。 1 9 8 3 年，麻省理工的g i n s b e r g 和m a x w e i l 发展了一套系统( g r a p h i c a m a r i o n e t t e ) ，利用计算机语言控制卡通的动作。但受到当时计算机硬件速度 的限制，一个简单的电脑动画往往需要花费很k 的时间。随着计算机硬件及动 画软件的迅速发展，以及越来越多的研究机构及商业机构加入到电脑动画领 域，电脑动画的制作水平也随之f i f 新月异。动画 ；= = l 益形成一个重要的产业，在 美国、f j 本、英国和荷兰这些动画片的制作强国，动画产业在国民生产总值。p 占有非常重要的地位，日本的动画产业更是国民经济六犬支柱产_ p 之一。 在过去几十年罩，计算机动画一直是人们研究的热点。在全球的图形学盛 会s i g g r a p h 上，几乎每年都有计算机动画的论文和专题。计算机动画每年度 的学术会议c o m p u t e ra n i m a t i o n 和学术期刊j o u r n a o fv i s u m iz a t i o na n d c o m p u t e ra n i m a t i o n 为专业人士观摩和交流这方面的研究成果提供了进一步 的机会。目前，计算机动画已形成个巨大的产业，并有进一步壮大的趋势。 1 3 计算机动画的分类 根据其应用领域的不同，计算机动画呵分为：三维动画和二维动画。i 维 动画的研究对象为三维空间中的形体，二维动画其研究对象为平面图像或者- z 维形体。 按其实现的技术来分； 计算机动画大致可分为：关键帧动画、变形物体动 画、过程动画、关节动画和人体动画、基于物理的动画几个方面。 浙江大学硕 论空2 d 角色动卿l 变形 1 4 本文的研究目标 本文的研究目标是提出一个自动的2 d 角色动画变形系统，以减少动画制 作中的乏味的工作量。该系统中提出了一个新的基于视觉特征的平磁形体渐变 算法。用户只需要将动画中角色的关键帧输入到系统，系统会自动插值生成渐 变中间帧，从而形成一个完整的动画序列。本文中系统的特点在j ： 新的基于视觉特征的平面形体渐变方法能简单有效地建立特征点之间的划 应关系，能很好地保留平面形体的视觉特征。 整个的动画序列生成过程完全自动，用户只需要事先设定几个相关参数、 输入图像，然后不用任何的干预，系统会自动生成结果。 系统可以处理的对象不但可以是单个区域形体或者多边形，还可以是多个 封闭区域组成的复杂形体。 系统中所使用的插值算法在处理源和目标图像特征点的对应关系时是以人 的视觉观察为标准的，因而系统所生成的渐变结果更合理。 1 5 本文的篇章结构 为了对计算机动画有个基本的认识，本文的第一章解释了计算机动画及其 相关的技术。在正式介绍本文的算法及系统之前，先对本文的篇章结构做一个 简要的概述： ( 1 ) 第一章2 d 形体渐变技术介绍。在这章内容中，我们介绍了二维形体渐 变技术，对前人在这一领域的研究成果进行了总结，并在此基础上提出了我们 系统中的新的基于视觉特征的平面形体渐变的思想。 ( 2 ) 第三章基于视觉特征的平面形体的渐变。该部分主要介绍了。个新 ；l 勺平 面形状渐变的思想。先介绍了当前的一些相关工作，然后讲述了从源和目标图 形抽取出视觉特征点，给出了一个有效的特征点相似的度量，利用d y n a m i c p r o g r a m m i n g ( d p ) 方法建立两组特征点之问的最优对应，在插值路径的计算中， 通过两次插值保证了最终结果形体的光滑。 ( 3 ) 第四章2 d 角色动画变形概要。该部分概括地介绍了本文系统的框架， 并对每个模块部分的功能和算法进行了简要地介绍。 浙江大学硕十论文2 d 珀色功l 田l 变形 ( 4 ) 第五章2 d 角色动画变形算法。在这章里，我们详细地介绍了2 d 动画角 色变形系统的各个模块功能的算法，主要包括：区域分段模块，浚模块将用户 输入的用轮廓线表示的动画角色分解成各个部分，然后对每个部分分别进行处 理。区域匹配模块，该模块将起始帧和终止帧分解出来的区域栩啊：对应起来， 以便后面分别对这些对应区域插值生成中间帧区域。对应区域插值模块，在该 模块中，使用了一种新的基于视觉特征的平面形体渐变算法，插值生成每对区 域中间渐变区域。区域调整和组合模块，这一模块将在前一模块中生成的各个 中问帧渐变区域组成最终的中问输出帧。 ( 5 ) 第六章2 d 角色动画变形实验结果。本章介绍了本文系统的主要功能和 操作方法，并给出几个实验结果，并把它同以前插值方法作了。一些比较。 ( 6 ) 第七章总结和展望。 第七章对本文工作进行了总结，主要说明了我们 的工作在几个方面取的进展，以及工作中存在的螋问题和未来的发展方向。 浙江大学砸l 论空 ! i 角色动【口【蹙形 2 1 引言 第二章二维形体渐变技术 根据应用领域的不| 司，计算机动画可分为：二维动厕和二维动厕。三维动 确的研究对象为三维空间中的形体，傩动画其研究对象为平面图像或者一雏 形体。按其实现的技术来分； 计算机动画人敛可分为：关键帧动画、变形物年水 动画、过程动画、关节动诋和人体动画、基于物理的动画几个方面。在2 1 ) 变形 物体动画中使用了一项变形的技术，称为二维形体渐变( 2 1 ) s h a p eb je n d i n g 或者2 ds h a p em e t a m o r p h o s i s ) ，指的是在二维形体之间的自然过渡，它在 维角色动蛳、几何造型、医学和娱乐等领域有着重要的应用。在过去几十年 里，人们陆续地提出了渚多二维形体渐变相关算法 f h 9 8 ，c , 9 8 。所有这些算法 主要用来解决一个问题， 个是如何实现二维形体之叫的对应，它被镌为顶点 对应问题；另一个是如何解决过渡形体的位置，它被称为顶点路径问题。 在下面的章节中，我们将介绍i 维形体渐变的概念，其需要解决的问题， 以及对前人的研究成果进行总结，并提出了我们的维形体渐变思想。， 2 2 二维多边形形体渐变 在：维角色动回( 2 dc h a r a c t e ra n i m a t i o n ) 中，经常会碰到这样的蝴 题：给定一个初始和最终的形体( s h a p e ) 我们称之为关键帧形体，求从初 贻形体光滑过渡到终止形体的中问渐变形体。如图ll 所示t 给定了 ：、右两 边的马和大象形体，中问的三个形体不需要手动交互，自动 ； _ i 算法产牛。这个 操作被称为维形体渐变( 2 1 ) s h a p eb l e n d i n g 、2 ds t l a p ci n t e r p o c i t i o n 或 2 ds h a p em e t a m o r p h o s i s ) ，它不仅在计算机动画中，而且在模式识别、曲面 重建和i 维造型中也具有重要意义。在许多商业软件中 a s 0 5 ，c s c 0 4 j 一维形 体颟变均被加入，作为其中的项功能。 体渐变均被加入，作为其中的项功能。 浙江大学硕f j 论史2 d 角色动画变形 2 1 引言 第二章二维形体渐变技术 根据应用领域的_ 不同，计算机动画可分为：三维动蕊秘二维动画。三维动 颤的研究对象为三维空间中的形体，_ 二维动画其研究对象为平面图像或者一：维 形体。按其实现的技术来分；计算机动画大致可分为：关键帧动厕、变形物体 动画、过程动画、关节动画和人体动画、基于物理的动厕几个方面。在2 n 变形 物体动画中使用了一项变形的技术，称为：二维形体渐变( 2 0s h a p eb l e n d i n g 或者2 ds h a p em e t a m o r p h o sjs ) ，指的是在二维形体之阳_ | 的自然过渡，它在二 维角色动画、几何造型、医学和娱乐等领域有着熏要的应用。在过去几卜年 晕，人们陆续地提出了诸多：二维形体渐变柜关算法 f a 9 8 ，6 9 8 。所有这些算法 主要用来解决二个问题，一个是如何实现二维形体之间的对应，它被称为顶点 对应蠲题；另一个是如何解决过渡形体的位置，它被称为顶点路径_ i j l 题。 在f 面的章节中，我们将介绍二维形体渐变的概念，其需要解决的问题， 以及对前人的研究成果进行总结，并提出了我们的二维形体渐变思想。 2 2 二维多边形形体渐交 在二维角色动画( 2 dc h a r a c t e ra n i m a ti o n ) 中，经常会碰到这样的问 题：给定一个初始和最终的形体( s h a p e ) 我们称之为关键帧形体，求从初 始形体光滑过渡到终止形体的中问渐变形体。如图1 1 所示，给定了左、右两 边的马和大象形体，中间的三个形体不需要手动交互，自动由算法产生。这个 操作被称为：维形体渐变( 2 ds h a p eb l e n d i n g 、2 ds h a p ei n t e r p n a t i o n 或 2 ds h 8 d em e t a m o r p h o s i s ) ，它不仅在计算机动画中，而主在模式识剐、 i ；| i 面 重建和三维造型中也具有重要意义。在许多商业软件中 a s 0 5 ，c s c 0 4 ，二。维形 体渐变均被加入，作为其中的一一项功能。 浙江大学硕_ j 论文 2 d 角色动画变形 邸帮帮翩铜 图2 1 马到大象的形体渐变 对于二二维形体渐变来说，有如下问题值得研究：渐变算法如何避免产生混 乱的中间过渡形体、怎样识别关键帧形体上的相似特征、怎样在渐变过程中像 持这些特征。这些问题可以归结到二维形体渐变中的两个基本问题，即顶点对 应问题和顶点插值问题。顶点对应问题，即是如何建立两个关键帧多边形形体 顶点的一对应关系，在两个多边形顶点个数不同时，如何加入新的顶点与如 何建立顶点f j ；j 的对应关系。总的来说，一个好的顶点对应满足如下两个要求： ( 1 ) 两个形体之间最终的顶点个数相同、一一对应，并且顶点对应与顶点排 列顺序是一致的 ( 2 ) 相似特征问的顶点一一对应 二维形体渐变的另一个基本问题是顶点路径问题。顶点路径问题用来解决 源形体上的各顶点如何运动到目标形体上的对应顶点。最简单的方法就是线性 插值，假设源、目标形体只、趣中的各个顶点，、一，( i = 0 ，l ，v - 1 ) ， 在某一时刻l ，中间形体各顶点按如下公式计算： = = = ( 卜t ) p ；+ 砖 ( i = o ，1 ，n 1 ) 不辛的是，线性插值方法会带来收缩( s h r i n k a g e ) 和扭结现象( k i n k ) ，特别是 源、目标形体间主要进彳亍刚性运动( 旋转、平移) 时，表现得尤为明显。为了 解决这个问题，人们提出了各种解决顶点路径得算法，例如，边角插值方法 s g w m 9 3 、模糊集( f u z z ys e t ) 方法 z h a 9 6 、基于特征分解的二维形体渐变方 法 y f j p r 0 4 、星形骨架方法 s r 9 5 以及咀完全刚性插值( a s r j g i d - a s p o s s i b l es h a p ei n t e r p o l a t i o n ) a c o l 0 0 为代表诸多基于三角变化的插值方 法。在这些方法中，边角插值算法通过把形体的顶点笛卡儿坐标转换到以内在 参数：边长和角度，来表示，通过他们来对形体运动进行旋转和平移捅值，该 方法可有效避免收缩，但常常会发生内部区域扭益现象。基于特征分解的方法 先通过人工地取出特征点，并把它们对应起来，再利用边角插值对轮廓多边形 6 浙江人学硕十论史2 d 栩芭动峨变水 插值，最后对每个顶点在相对轮廓边上进行线性插值，这种方法可以得到较好 的效果，但是在特征提取和对应时需要过多的人一t 。f 预。而其他方法，他们的 摹本思想，均是把形体运动中的刚性运动抽取出来，进行单独的角度、位置插 值，这螋方法- 巧有效避免线性插值的收缩现象。但由于在真实世界中，以旋转 为代表的刚性运动基本都是以一个视觉特征为单位进行的，所以常常两个形体 间的刚性运动需要多组分支运动来代表，并且每组刚性运动常发生在两个相似 特征之间。在上面的算法中，要么他们的刚性运动由个单独的全局旋转、平 移变换来代表，要么这些刚性运动并不发生在对应的相似特征之间，i 矧此，这 些方面常常也会产生一些视觉效果不好的渐变序列。在下一小节中，我们将详 细介绍、分析前人在形体渐变领域中的成果。 2 3 二维多边形渐变的研究现状及意义 在二维多边形渐变中，需要解决两个基本问题：顶点对应和顶点插值路 径。顶点对应建立起两个多边形顶点之间的对应关系；顶点插值路径确定渐变 过程中各个顶点的位置，产生中间多边形。一个好的二维多边形渐变算法应当 满足：( 1 ) 源多边形形体光滑地过渡到目标多边形形体； ( 2 ) 中间过渡多边 形形体不发生自交、收缩、内部区域扭曲等不自然现象； ( 3 ) 中问过渡多边形 形体应当保留源和目标多边形上的视觉特征。 在顶点对应方面，人们提出许多自动建立顶点对应的方法。s e d e r b e r g 和 g r e e n w o o d 引入了基于物理模型的顶点对应方法 s ( ；9 2 ，其核心思想是将两个 多边形看作线框，源多边形变换到目标多边形，相当于源线框扭曲到目标线 框，需要对其进行做功，他们建立了相应的扭曲做功计算公式，于是顶点对应 问题变成了求解消耗功最少的最优问题；z h a n g 提出了基于最相似三角片的方 法建立顶点对应关系 z h a 9 6 ，他依据源、目标多边形上对应的三个顶点创建一一 对对应三角形，并为每对三角形建立了一个相似性评估，同样地，源、目标多 边形上顶点对应问题也变成了寻找整体最相似三角形对的最优问题：这种方法 同s e d e r b e r g 的方法很相似，只不过这里用的是相似函数而不是功函数。 c a r m e l 等人根据多边形上的特征点 c c 0 9 7 ，通过变形建立源多边形和目标多 边形的顶点对应。r a n j a n v a 9 6 通过圆的集合来表达对象。顶点之问的对应关 浙江人学硕十论文 2 d 角色动蹴变形 系的建立是通过计算圆的大小和相对位置，中间渐变对象通过渐变对应的圆来 产生。m o r t a r a 和s p a g n u o l o 肭0 1 使用个近似骨架来表达形状，通过计算形 状的近似骨架的合理的匹配来建立顶点之间的对应。l i u l w z * 0 4 利用平面形体 上特征点附近领域点的集合所构成的协方差矩阵，通过计算浚矩阵的特征谴和 特征向量给出特征点相似代价，顶点的最佳对应问题被转换成使得对应的总体 相似代价最低的最优问题。s e d e r b e r g 和z h a n g 的方法忽略了多边形的视觉特 征，仅根据多边形的几何的集合属性，如边长、角度、三角形面积等来自动寻 找源、目标多边形的摄佳顶点对应，难以得到源、目标多边形间视觉特征的对 应。l i u 的方法也存在类似的问题，在计算时仅仅包含特征点周围的轮廓点， 而没有考虑到平面形体内部的特征。c a r m e l 的方法中存在一个多变形形变过 程，计算量较大且变形过程难以控制，因而也不是1 个令人非常满足的顶点对 应力法。 在曲线形状变形中，s e d e r b e r g t e 9 5 扩展了基于物理的方法 t e 9 2 ，建立 封闭的b 样条节点之间的对应。c o h e n s g r 9 7 利用动态编程来近似解出两个曲 线的离散的采样顶点集。h u i 和l 。i h l 9 8 提出了计算曲线形状特征点的技术， 这些特征点表达形状，然后再建立这然特征点之间的对应。s e b a s t i a n t p b 0 3 介绍了一种曲线对齐的方法，这种方法通过给出要对齐的曲线一种标识来实现 对齐。 想对于顶点对应问题，顶点插值路径问题的相关研究则较多。线性插值是 最简单的顶点插值方法，但用此方法得到的中问多边形可能会发生自相交或收 缩，效果不自然。当多边形进行刚体运动时，此问题尤其明显。s e d e r b e r g 等 人提出了一种基于多边形内在几何属性( 边长和角度) 的插值方法 s g w m 9 3 ， 该方法可以得到较好的视觉效果。但中间多边形容易产生内部区域扭曲。在 c a r m e l 等人和z b a n g 提出的方法中 c c 0 9 7 ，z h a 9 6 ，插值路径被分成两部分： 刚性部分和弹性部分。刚性部分通过全局的旋转和平移实现。对于弹性部分， c a r m e l 等人通过顶点问的变形过程实现。而在z h a n g 方法中，先找到满足目标 函数最佳的一对三角片，并基于此建立对应仿射标架，然后将源和目标多边形 变换到两个仿射标架中。通过在仿射标架之间进行刚体变换，并对对应顶点的 局部坐标进行线性插值，得到中间多边形。他们的方法不足之处在于，单个的 8 浙江大学硕， j 论文2 1 ) 角色动嘶变彤 旋转和平移通常并不能反映出两个多边形的朝向及位置变化趋势，不一定能够 得到光滑的渐变效果。 上述顶点插值方法仅考虑了多边形的边界，丽没有考虑多边形的内部区 域。s h a p r i a 和r a p p o r t 提出了种基于多边形啦部区域的插值方法【5 r 9 5 ， 他们先将源和目标多变形进行同构星形骨架分解，然后再把源和目标多边形以 极坐标形式表示到相应的骨架中，通过插值对应的骨架和极坐标得到顶点位 置。该方法能很好地避免中间多边形的自交，但当两个多边形较复杂和离异 时，星形骨架的同构分解变得不确定。a l e x a 等把源和目标多边形进行同构= i 角化 a c o l 0 0 ，他们定义了一对三角片的最佳变换，通过逼近每队三角片之问 的局部最佳变换，得到所有对应三角片之间的全局最佳变换。该方法能得到较 好的插值效果，并能实现多边形内部纹理的光滑过渡。由于在计算每一对三角 片的最佳变换时需要进行q s 分解，考虑到分解带来的误差，若同构二三角化中存 在不规则的三角片，则会产生不光滑的渐变效果，不辛的是，要产生规则的嘲 构三角化需要较多的时间化费，有时不得不进行人j r 交互。g o t s m a n 和 s u r a z h s k y 以及s u r a z h s k y 和g o t s m a n 也通过插值同构三三角化来完成顶点插值 路径 g s 0 1 ，s g 0 1 ，他们的方法可保证中间多边形不发牛自交。但在插值之蓟， 源和目标多边形需要被两凸多边形封闭起来，当源、目标多边形差别比较大 时，中间多边形不可避免地会发乍扭曲。 y a n 等介绍了一种基于“张力场( s t r a i nf i e l d ) ”插值的形体渐变技术。 他们使用物理学上的“张力”概念来解析地描述形体变形的好坏，并基f “张 力场”的插值来得到自然的形体过渡 y h m 0 4 。y a n g 提出了慕于特征分解的方 法 y f j p r 0 4 1 ，先通过人工地取出特征点，并把它们对应起来，再利用边角插值 对特征点组成的轮廓多边形插值，最后对每个顶点相对予轮廓多边形的边进行 线性插值，这种方法可以得到较好的效果，但是在特征点提取和对应时需要过 多的人工干预。另外，在文章 c y w 0 4 ，d m 9 8 ，s s b t o i 中，作者均提出了对不同拓 扑形体的渐变算法，在它们的实现中，输入得二维形体不再是简单得涮胚于圆 得多边形，而是复杂得、带孔得、具有拓扑的多边形形体。对于不同拓扑形体 的渐变，主要需要解决以下问题：1 ) 如何建立两形体间的对应；2 ) 如何在形体 渐变过程中，解决拓扑突变带来锝过渡不自然问题 浙t i 大学硕l 沦空 2 d 角色动画变形 i 二面介绍得顶点路径算法，只能适用于两个多边形之间得渐变。对于多个 多边形之问得渐变，a 】e x a 在他得篇综述文章中谈论到了相关问题 a 1e 0 2 ， 并在文章 3 1 e 0 3 中介绍了一种融合形体局部特征得算法；另外地，c h e n 和 p a t e n 、r o s s i g n a c 、m i c h i k a w a 等分别设计了相关算法去驱动多个多边形之间 得渐变 c p 8 9 ，r k 9 4 ，m k f c 0 1 。然而，这些算法均存在局限性，要么不能实现局 部控制，要么不能产生很好得效果。因此，在文章 j n 0 3 中，j o h a n 和n h h t a 提出了一个专门针对二维多个多边形渐变得算法，他们得算法允许用户进行局 部控制，并且即使形体间形状相差较大时电能够产生较好得渐变效果。不辛的 是，他们算法中的交互对用户来蜕不是很直观，而这一点在进行局部特征控制 时非常重要。 2 4 小结 在本章，我们介绍了二维形体渐变的概念，其需要解决的问题，以及对前 人的研究成果进行总结。通过分析以前的算法，我们发现在解决特征点对应问 题时，以前的算法不是没有考虑到2 d 形体内部就是计算太复杂，要么就是人工 干预过多。我们提出了一个基于视觉特征的平面形体渐变方法，它即考虑剑了 平面形体轮廓又考虑到了平面形体区域的内部，而且这种方法是完全自动的。 在第三章草，我们将详细地介绍这种方法。 在多个多边形形体渐变方面，已有的算法要么不能实现局部控制，不能产 生很好得效果，要么用户的交互过于复杂，不直观。我们提出了一个对多个封 闭区域的形体渐变的方法，不但可以得到很好的效果，且整个变形过程是自动 进行的。这种方法将在第四、五、六章旱被详细介绍。 浙2 ：大学颀l 论殳2 d 角色动域，垒形 3 1 引言 第三章基于视觉特征的平丽形状渐变算法 在这章中，我们给出一个新的方法来建立两个平而形状特征点之间的对 应。这蝗特征点是从源、目标形状中抽取m 来的。我们提出个新的方法来衡 量两个特征点之间相似度。通过使用有效的动态编程的方法找出特征点之间的 优化的对应关系。试验结果显示，这种方法简单、快速，有效地保留了原始形 体上的特征。在试验结栗中，我们对本文算法与原有的算法进行了比较，并进 行了优缺点分析。 我们的方法主要解决的问题是为平面形体渐变建立特征点之间的对应。2 d 多边形形体特征点之间的对应是变形主要研究目标之。已有许多人在自动建 立顶点对应上做出了大量的研究。s e d e r b e r g 和g r e e n w o o d $ 6 9 2 提出了一个基 于物理的方法，通过最小化工作函数来确定多边形顶点间的对应。z b a n g z h a 9 6 j 给出了。个模糊对应方法，它最小化顶点之间的相似函数。这个方法同基j 二物 理的方法相似，但不是使用工作函数而是使用一个相似函数。r a n j a n v a 9 6 通 过圆的集合来表达对象。顶点之间的对应关系的建立是通过计算圆的大小和棚 对位罱，中间渐变对象通过渐变对应的圆来产生。m o r t a r a 和s p a g n u o l o m m 0 1 使用一个近似骨架来表达形状，通过计算形状的近似骨架的合理的匹配来建立 顶点之间的对应。l i u l w z * 0 4 利用平面形体t 特征点附近领域点的集合所构成 的协方差矩阵，通过计算矩阵的特征值和特征向量给出特征点相似代价，顶点 的最佳对应问题被转换成使得总体相似代价最低的最优问题。 此外，在曲线形状变形中，s e d e r b e r g t e 9 5 扩展了基于物理的方法 t e 9 2 ，建立封闭的b 样条节点之间的对应。c o h e n s g r 9 7 利用动态编程柬近 似解出两个曲线的离散的采样顶点集。h u i 和l i t t l 9 8 提出了计算曲线形体特 征点的技术，用这些特征点束表达形状，然后再建立这些特征点之间的对应。 s e b a s t i a n t p b 0 3 介绍了一种曲线对齐的方法，这种方法通过给出对齐曲线 种标识来实现。 浙江大学硕1 论文 2 d 角色础嘶盘彤 在我们的研究中，一一个平面彤体是阳些连续的曲线或者直线段组成。 源、目标形体被缩放到相同的尺寸，以免平面形体的相对尺寸影响到对应关 系。在以前大多数方法中，表达源、目标形状的两组顶点的对应关系是通过计 算顶点之间的相似性来建立的。为了在渐变过程中保持视觉上的一致性，对 源、目标形状应该建立的是它们的视觉特征之间的对应关系而不是顶点之州的 对应关系 l w z * 0 4 。例如：如图3 2 ，个人的不同动作的源、目标形状，他 的头、胳膊和腿都应该是各自对应的，这样的对应才符合人的视觉要求。如果 将手同脚对应起来仅从图形数据角度来看可能没有问题，但这种对应不符合 人视觉习惯，结果自然也不好。如果源、目标形状的各个有视觉意义的部分是 对应的，那么它们渐变的中间形状也会符合人的视觉要求。 一个形状可以被看成由一些不同的在视觉上有意义的部分维成。特征点就 是将这些有意义的视觉部分分割开来，这些点在人的形状察觉中发挥重要的作 用。如果这些特征点被正确地识别出来并被正确地对应，那么就可以保证有视 觉意义的特征部分被对应起来，最后渐变的结果也将会符合人的视觉要求。 3 2 特征点的计算 由于我们的输入是平面形体图像，在进行变形之前我们需要将平瞬图像的 特征点检钡8 出来。特征点检测在许多科学领域是一个被深入研究的主题，包括 计算机视觉，医学图像和计算流体动力学。在这里，我们要求的特征点即是平 面曲线上那些高曲率的点或角点。这些点在人的视觉观察中发挥重要的作用。 对于一个给定的平面形体p ，我们计算它的高曲率点，凸出点，变形点。 对于多边形，它的所有顶点都被看作特征点。我们使用文献f l w z * 0 4 中的方法 抽取特征点。 这个算法分两步来计算平面曲线的角点。设曲线是密集采样的点序列的集 合p ，在我们的应用中是以像素为单位来采样的t 第一步，算法先扫描整个点 序列，选出候选角点。第二步，去除多余的候选角点。 第一步：算法在每个曲线采样点处都去搜索满足如f 约束条件的三三角形( 如图 3 1 所示) ( p ，p ，p + ) ： d 2 - i p p + j 2 。 浙江大学硕士论文 2 d 珀色动国变形 。- ( p v ) ( 如图 3 1 ( b ) 所示) ，那么说明p 。比p 更尖锐，p 就被抛弃掉。p 的邻域内的点是指 所有到达p 的距离在定范围内的点，即满足：| p p 、f 2 ，d 。2 。或者 l p p 。1 2 玉d 2 。 氏一矗。，口。是这个算法的参数，在我们的系统中，吐。2 7 ， 靠。= 氏。+ 2 ，口。= 1 s 0 度。当然这些参数随着输入的不同而有所变化。 经过这步处理，我们可以将平面图形记为一些特征点序列p ，i = 0 ，1 ， n 。只为平面图形的特征点。如图3 2 所示： 浙江大学硕士论史 图3 2 一个人形状的两个关键帧，特征点被标记出柬 3 2 1 特征点补丁块 我们定义平面图形上以一特征点为中心，以w 为高宽的矩形区域为该特征 点的补r 块 d j j 0 4 ，如图3 。3 ； 出厂毡 ( a ) 特征点补丁块( b ) ( a ) 中的补丁块放大之后的结粜 图3 3 特征点的补丁块 在特征点的局部形状属性计算中，许多研究主要使用点局部邻域丰要部件 分析方法 s w r 0 1 ，m r m 0 3 。l i u l w z * 0 4 利用特征点附近一些采样点所构成的协 方差矩阵的特征值和特征向量的统计和几何属性来度量该特征点的形状属性。 我们提出个基于图像的方法，通过对特征点补j 所包含的图像信息的统计丽 得到该特征点附近的形状信息。如图3 3 中所示，我们设定平面图形轮廓内部 的区域点取值为l 、外部为0 ( 轮廓线可取0 或1 ) ，那么特征点的形状信息就 可由此特征点的补丁块所对应高宽为w 矩阵来表示 儿 。 只，= 0 ：当岛为外部点时： p ，= l ，当岛为内部点时； 4 浙i = ：夫学颀j ：论史 2 d 角色动恻变形 i w ，j w 3 3 特征点对应 我们将源平面形状和日标平面形状分别表示为：s = s fj = 0 ，i ，i n ， d2 哆；j 2 0 ，l ，n ，其中s 和哆分别表示源形状s 和目标形状d 的特 征点。如果形状s ( 或者d ) 是封闭的，则瓯= s ( 或者q 2d 0 ) 。 3 3 1 特征点的相似度 在这一节中，我们给出一个基于特征点补丁的特征点相似度量。闲为我们 通过观察可以看出，从源到目杯形体的渐变中，有视觉意义的局部特征是基本 保持不变的。所以源、目标形状对应特征点的补f 所包含的区域内部的点和区 域外部的点个数变化很小，也就是说它们相似。如图3 3 ( b ) 所示，j p 和尸。的矩 形区域所包含的点分布是很接近的。这种相似，我们称之为特征点形状相似。 此外特征点与特征点之间沿轮廓的相对距离的变化也是较小的。如图3 3 ( a ) 所 示，p 和只之闻的距离相对与整个源轮廓的比率与p 和只之间的距离相对与整 个目标轮廓的比率也是很接近的。这种相似，我们称之为特征点距离相似。幽 此源和目标特征点之间的相似度包含两个部分，形状相似和相对距离相似。 定义源特征点s 与目标特征点d ，之间形状相似代价为： 鼢c f ( s ，哆) = ，毛( 旧一乓i ) ， o s l 蔓w ，o j w ， 弓，巧分别为特 征点墨，d 的特征点补丁矩阵。即两点之间的形状相似代价为他们对应的特征 点补丁矩阵不相同的元素的个数。它表达了这两个特征点附近区域的差异，差 异越小，这两个点越相似。 定义源特征点s i 与目标特征点d ，之间距离相似代价为： 删批引，2 p 等卜吣一捌蒯巨 离，l s 为源轮廓长度，d jq 为目标特征点d ，b 之问的距离，l 为目标轮 浙江犬学颂十论文 2 d 角色动俩变形 廓长度。这里，在按这个公式计算距离相似代价时，假定r s 与d 是相对应 j ， 的，并且他们是沿起始特征点方向上分别离s 和d ，最近的特征点。如图文4 ， 图3 f 4 s ，d 为起始相对应的特征点，s l 对应d 1 ，s 2 对应d 2 ，那么在计算s 3 与i 】3 之问的距离相似代价时，离他们最近的且相互对应的特征点分别为s 2 ，d 2 ，所 以这时的距离相似代价为：s 2 沿轮廓到s ：距离除以整个源形状轮廓 乏度，d 2 沿轮廓到d 3 距离除以整个目标形状轮廓长度，这两个商之差的绝对值即为 s 3 ，d 3 的距离相似代价。 定义源特征点s 与目标特征点d 。之间相似代价为： s i m c o s t ( s ，d ，) = s s i m c o s t ( 墨，d ，) + w * l s i m c o s t ( s ，d ，) ；其中w 表示权重。特征点间的相似代价取值依赖与特征点补r 块宽度w 和权重w 的选 择。如