（计算机软件与理论专业论文）二维物体若干变形技术研究.pdf

论文题目： 专业： 硕士生： 指导教师： 二维物体若干变形技术研究 计算机软件与理论 赖志豪( 签名) 康宝生( 签名) 摘要 物体变形( m o r p l , _ i n g ) ，亦称作物体渐变( m e t a m o r p h o s i s ) ，是指将一给定的 初始物体( 这里的物体包括数字图像、多边形、自由曲线曲面、网格、多面体等) ， 在视觉上光滑、连续、自然的变化到目标物体。随着计算机技术的迅速发展，物 体变形技术广泛应用于计算机图形学、工业产品设计、计算机动画、虚拟现实、 影视特技制作等领域。二维物体变形是物体变形的重要组成部分，不仅在关键帧 动画、模式识别，而且在曲面重建和三维造型中也有重要意义。 二维物体变形的研究包含两个问题；顶点对应问题和顶点插值路径问题。在 过去的几十年里，人们针对这两个问题陆续提出了许多算法，用以实现二维物体 之间的光滑过渡。本文首先简要介绍了二维物体变形技术的历史及研究现状，指 出该领域内各种方法的特点、不足及遗留问题。然后，在分析和比较己有的二维 物体变形算法的基础上，提出了一种基于变形点检测的图形顶点对应方法。所给 算法简单快速、对应效果自然合理，相比于已有的算法，它的适用范围更广 最后，本文提出一种基于插值初始多边形和目标多边形对应边向量及其旋转 变换矩阵的多边形变形方法，并给出了具体的算法流程该算法简单直观，计算 量较小，运行速度较快，能够实时实现。数值实验表明，本文所给算法变形效果 较流畅、自然。 关键词：顶点对应；仿射变换：多边形逼近：插值；变形：形状融合 m a s t e rd e g r e ed i s s e r t a t i o n o nt h e2 ds h a p em o r p h i n ga n di m p l e m e n t l a jz h i h a o ( i x - p a r m m t o f i n f o r m a t i o n s c i e n c ea n d t e c h n o l o g y , n o r t h w e s t u n i v e r s i t y , x i n l l7 1 0 0 6 9 ) s u p e r v i s o r ：p r o f e s s o rk a n gb a o s h c n g a b s t r a c t m o r p h i n g , a l s ok n o w na sm e t a m o r p h o s i s ，i st h ec o n t i n u o u s ，s m o o t ha n dn a t u r a l t r a n s f o r m a t i o nf r o mas o u r c eo b j e c ti n t oat a r g e to b j e c t ，w h e r et h eo b j e c tc a nb e d i g i t a li m a g e s ，p o l y g o n s ，f r e e f o r mc u r v e sa n ds u r f a c e s ，m e s h e s ，p o l y h e d r o n se t c a l o n gw i t ht h es p e c d yd e v e l o p m e n to fc o m p u t e rt e c h n o l o g y , m o r p m n g i sb e c o m i n g p o p u l a ri nm a n ya 1 - 戌1 5 ，s u c ha sc o m p u t e rg r a p m c s ，m d u s t r i md e s i g n , c o m p u t e r a n i m a t i o n , v i r t u a lr e a l i t ya n df i l ms t u n t s h a p em o r p h i n go fp l a n a rp o l y g o n , t h a ti s s h a p eb l 删n g i sa l s oa t t r a c t i v e ，w h i c hh a sg r e a ts i g n i f i c a n c ei nk e yf l a m ea n i m a t i o n , p a t t e r nr e c o g n i t i o n , s u r f a c er e c o n s t r u c t i o na n dt h r e e - d l m e u s i o n a lm o d e l i n g t h e r ea g ot 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 dv e r t e x i n t e r p o l a t i o n 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 b 目t - ep r o p o s e dt o a c h i e v e s 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 , w ei n t r o d u c et h eh i s t o r ya n dt h e c u r r e m td e v e l o p m e n ti nt h ea r e ao f2 ds h a p eb l e n d i n gc o n c i s e l y , a n dp o i mo u t r e s p e c t i v e l yt h ec h a r a c t e r i s t i c sa n di t si n s u f f i c i e n c i e so ft h em a i nm e t h o d si nt h i s r e s e a r c ha r e aa sw e l la si t so p e nq u e s t i o n s b a s e do nt h ei n f l e c t i o np o i n td e t e c t i o n , a v e r t e xc o r r e s p o n d e n c ea l g o r i t h mi sp r o p o s e di nt h ed i s s e r t a t i o n t h ea l g o r i t h mi sf a s t a n dr o b u s t , o f w h i c ht h ee f f e c ti sn a t u r a la n dt h ea d a p t e rr a n g ei sm o r ee x t e n s i v et h a n t h ef o r m e r s f i n a l l y , b a s e do nt h ee d g ev e c t o rr 印m s e n t a t i o mo fp l a n a rp o l y g o n , w ea l s o p r e s e n ta n e wm a h o df o rp o l y g o nm o r p l l i n gb yi n t e r p o l a t i n gt h ec o r r e s p o n d i n ge d g e v e c t o r sa n dt h e i rr o t a t i o nm a t r i x e so ft h ei n i t i a lp o l y g o na n dt h et a r g e tp o l y g o n t h e a l g o r i t h mi ss i m p l ea n dh a sl o wc o m p u t i n gc o m p l e x i t ya n dr u n sf a s tt h a tc a l lb ed o n e r e a lt i m e t h es p e c i f i cp r o c e d u r ei sg i v ea tl a s t s e v e r a le x a m p l e ss h o wo u ra l g o r i t h m sa r ev a l i da n df e a s i b l e ，a n dn a t u r a l m e s h i n g e f f e c t sa r ep e r f o r m e d k e y w o r d s ：v e r t e xc o r r e s p o n d e n c e ；a f f i n ei n v a r i a n t ；p o l y g o na p p r o x i m a t i o n ； i n t e r p o l a t i o n ；m o r p h i n g ；s h a p eb l e n d i n g i 西北大学学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻 读学位期间论文工作的知识产权单位属于西北大学。学校有权保留并 向国家有关部门或机构送交论文的复印件和电子版。本人允许论文被 查阅和借阅。学校可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学 位论文。同时，本人保证，毕业后结合学位论文研究课题再撰写的文 章一律注明作者单位为西北大学。 墨差萎妻纂萎蓁雪? 望指导教师签名：翌至兰尘l学位论文作者签名：旋兰，益指导教师签名：! ：! 矽7 年钥夕日h q 年g 月多日 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，本论文不包含其他人已经发表或撰写过的研究成果，也不包含 为获得西北大学或其它教育机构的学位或证书而使用过的材料。与我 一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 学位论文作者签名：旋篙，篆 钞7 年占月夕日 第一章绪论 1 1 概述 变形( m e t a m o r p h o s i s 或m o i p h i n g ) ，亦称作形状渐变或融合( s h a p e b l e n d i n g ) 、形状平均( s h a p ea v e r a g i n g ) 等，是指从初始物体到目标物体的连 续、光滑、自然的过渡( 这里的物体可以是数字图像、多边形、多面体等) 它 综合利用计算机图形学、图像处理、计算数学及其它学科的知识来研究计算机变 形动画，是近年来兴起的一个新的研究领域，具有很重要的实用价值和学术价值。 变形技术的基本思想和电视、电影技术一样，利用了人眼的视觉暂留原理。 对给定的两幅画面，计算机自动生成介于两者之间的一系列画面，每两幅画面之 间仅存在微小的差别。在这种微小的过渡中，第一幅画面变成了第二幅画面。当 连续演播这一系列中问画面时，由于视觉暂留原理，感觉上人们就会看到初始画 面光滑平稳地变成了最终画面。变形通常需要解决两个关键性问题，第一是建立 初末两物体的元素( 如顶点、边等) 之间的对应关系：称为对应问题 ( c o r r e s p o n d e n c ep r o b l e m ) ；第二是在变形过程中研究对应元素的变形轨迹， 称为轨迹问题( t r a j e c t o r y p r o b l e m ) 但是，不同的变形轨迹是由插值不同的变 量产生，因此轨迹问题也称为插值问题( i n t e r p o l a t i o n p r o b l e m ) 目前，国内外 已有许多有关变形的研究成果，给出了解决变形问题的比较有效的算法。但是， 由于变形是一种视觉效果，与人的审美观密切相关，主观因素很大。因此，对于 以上两大关键性问题都没有成功的解决方案，也没有正式明确的定义然而，从 用户角度来看，我们可以根据实际经验、视觉效果和应用场合来判断一个变形过 程的好坏，因而适当的用户干预是必不可少的。研究人员普遍认为令人满意的变 形则应该满足以下几个条件： 1 ) 变形过程中产生的中间图形对象的一些特征，如边长、夹角、面积等应 保持单调平滑的变换。 2 ) 中间图形对象的边界应尽量保持光滑，并且能保证初末图形的拓扑结构， 不产生自交现象。 3 ) 初末物体所共有的一些特征在变形过程中应该保留。 4 ) 用户干预少，交互手段简单直观，易于操作， 二十世纪8 0 年代以来，计算机变形技术已在许多领域得到了广泛应用，其 中最为人们熟知和印象深刻的就是影视和广告制作中的变形特技在计算机图形 学领域，变形技术作为图形图像处理工具和形状分析工具，已被广泛应用于计算 机动画技术、艺术模拟、影视广告等领域，创造了令人叹为观止的奇特效果。在 工业设计领域，变形作为形状生成工具，通过融合同一产品在不同时期的造型或 相近产品在同一时期的外形轮廓造型，计算机辅助生成新的形状，并将其作为未 来产品的造型雏形，满足了设计创新的要求在医学领域，变形技术可以模拟病 变情况，供医生观察以确定治疗方案。同时也可以辅助外科整形手术。在教育领 域，变形技术用来作为一种新的形象生动的教学工具在气象预报中，对气象卫 星传送的气象云图应用变形技术可以生成连续的卫星云图，以便描述云图的运动 状态。在地理信息系统中，变形技术应用于数字地形模型的生成中，把一幅二维 遥感图像叠加到一个三维的地形图上。在刑侦系统中，变形技术用来描述人物脸 部特征，构造人脸模型总之，随着变形技术和其它各门应用科学的发展，变形 技术在这些应用领域的渗透也会越深越广 1 2 变形技术研究现状 近年来，二维物体变形技术在工业模拟、虚拟现实、科学计算可视化、生物 医学工程、广告娱乐等领域获得了快速的发展对应于上述提到的变形的两大关 键性问题，其国内外的有关研究可分为两类：对应和插值。相对于顶点对应问题， 插值问题的研究在早期更为广泛。研究者一般根据已有的顶点对应算法或是采取 手动对应的方式建立顶点之间的匹配关系，再设计插值路径问题的解决方案。而 随着图形匹配技术的发展，变形的对应问题已越来越受到人们的重视，特别是近 几年，一些较为有效的图形顶点对应算法陆续出现。下面，我们就相关研究成果 的主要思想作一介绍，并对各种算法的优劣进行简要分析。 1 2 1 对应问题 目前，解决图形顶点对应问题的算法主要包括以下几类： 1 ) 基于边界顶点自身简单的几何或物理信息来建立对应的方法i m 】。 2 c o h e n l l 瞎提出基于切矢匹配的对应方法，利用对应顶点的切矢内积构造单 位切矢内积矩阵，建立相似度量函数，从而得到顶点之间的最优对应；z h a n 岔刁 从模糊数学的角度提出了基于最相似三角面片的方法建立顶点对应关系，他依据 初末多边形上对应的顶点构造对应的三角形，并为每对对应的三角形按照顶点邻 边和夹角等几何信息建立相似度量函数，将顶点对应问题转化为寻找整体最相似 三角形对的优化问题，通过使初始多边形到目标多边形的相似度达到最大建立两 者间的对应关系：s c d e d a e r g 等【3 瞧出基于物理做功的方法，其核心是将两个多 边形看作线框，初末多边形之间的渐变过程被看作初始线框变化到目标线框的过 程，而线框之间的变化做功可分为伸缩和弯曲做功两部分，通过最小化做功函数 来建立顶点对应关系。前两种方法的不足是忽视了多边形的视觉特征，仅根据多 边形的几何属性，如边长、角度等自动寻找初始、目标多边形的最佳顶点对应，难 以得到多边形视觉特征的对应。后一种方法由于考虑到物体在变化过程中的物理 做功，因此比较符合物体在实际变形过程中相关几何量的变化，对应效果较好， 但是算法过于复杂，而且不能保证初末多边形特征相似区域的对应 2 ) 基于特征点匹配的对应方法，提取初始和目标图形边界的特征点，对得 到的初末多边形的特征点集进行匹配，面对应特征点之间的相似度量函数则采用 特征点近邻域内点的相关信息来建立。l i u t 6 利用图形特征点近邻域点的集合所 构成的协方差矩阵，通过计算矩阵的特征值和特征向量给出特征点的相似度量函 数，顶点对应问题被转换为使得总体相似代价函数最小的最优问题；黄家水【玎 从初始图形和目标图形中抽取特征点，利用以特征点为中心的矩形区域图像信息 以及特征点之间的距离，给出一个新的特征点相似度的度量。利用动态编程方法 找到特征点之问的优化的对应关系l ，i u 的方法包含了丰富的边界信息，对应效 果比较理想，且该方法具有旋转不变性，可以较好地处理变形中旋转部分的对应。 黄家水方法同样包含了较为丰富的边界信息，而且操作简单易行这两种方法都 能较好的建立初末多边形中特征相似区域的顶点对应关系。l i u 的方法的不足是 在使用动态规划方法的复杂度较高，而且动态规划求解不易控制。其次，在确定 特征点集中一部分对应特征点和不对应的特征点时要掺入一些人为因素，不具有 自适应性。黄家水的方法虽然表面上可以自动完成，但由于在算法中要引入两个 参数：相似度参数和旋转角度参数。同样也掺入了人为因素。特别是角度参数， 如果选择不当，将导致旋转部分的对应效果不佳 h u i 掣8 1 的思路与l i u 的方法和黄家水的方法类似：他们先根据曲线曲率的 变化构造一个判别函数来确定对应的物体( 一般采用曲线表示) 变化较大的顶点 作为特征分段点，从而将曲线分成若干段，再根据这些分段点自身的一些信息( 一 般是几何信息) 和相邻分段点之间弦的几何信息来建立这些分段点之间的对应。 对已经建立匹配关系的子曲线段则按照弧长比例致的原则完成整体顶点对应， 其缺点是采用几何信息不能很好地描述点的特征。 3 ) 基于图形骨架的轮廓顶点对应方法。前述方法处理的都是物体的边界信 息，缺少内部信息，而骨架能够很好地提取出物体的内部信息。m o r t a r t 等1 1 0 】使 用一种近似骨架来描述图形形状对初末物体进行近似骨架剖分，将得到的近似 骨架按照一定的相似度量函数建立节点之间的对应，然后再映射到轮廓上确定初 末图形的对应顶点，这些顶点一般都是特征点。在相邻的特征点之间通过添加新 顶点来完成整体顶点的匹配。该方法对顶点数目较少、形状较为简单的图形比较 有效。但是，由于近似骨架提取方法的局限性，该算法不适合用于复杂的图形。 1 2 2 插值问题 解决平面图形顶点插值路径问题的方法主要有以下两种： 1 ) 采用顶点自身的一些简单的几何或物理信息插值【1 1 - 2 6 1 线性插值是最简单的插值方法：假设彳为初始多边形，b 为目标多边形， 4 ，b , ( i - - ，n ) 为多边形的顶点，则到b 的变形定义如下： c o ) = ( 1 一f ) 彳+ 口= 【( 1 一f ) 4 + i s , ，( 1 一f ) 4 + e 】= 【c j ( f ) ，c ：( f ) 】f e 【q i l 这种算法简单且生成速度快，但变形中可能引起边界的非正常萎缩，产生自 交，效果非常不自然，当多边形进行刚体运动时，此问题尤其明显。另外，一些 简单的几何特征如长度、角度等在变形过程中不能一致的变化。原因是各个顶点 及其他几何信息在变化中缺乏联系，其路径是互相独立的。 1 9 9 3 年，s e d e r b e r g 等【1 1 l 提出一种基于多边形的内在几何属性( 边长和角度) 的插值方法，线性插值相邻边的旋转角度和边的长度，并采用优化的方法避免断 口现象。该方法能体现多边形的结构特征，生成速度快，对很多变形实例取得了 很好的效果，且能在一定程度上避免萎缩和扭结现象，但当初始多边形和目标多 4 边形包含较多短边时中间多边形形状可能会发生较严重的畸变。 为了克服上述方法存在的问题，s h a p i m 和r a p p o p o r t 2 l 提出一种星形骨架 ( s t a rs k e l e t o n ) 方法。该方法首先构造初始多边形和目标多边形的同构星形骨 架，再通过星形骨架将多边形分为对应的几个子多边形。对该同构星形骨架变形， 利用骨架节点和子多边形顶点的关系线性插值对应的元素如边长、角度等，最后 重组得到中间的关键帧多边形由于该算法既考虑到多边形的边界，也考虑到其 内部联系，故减少了产生自交的可能性，变形效果比较自然。由于初末多边形的 同构星骨架提取比较困难，特别是对顶点个数较多的复杂多边形，所以算法的复 杂度很高。与上述方法类似，杨文武等【。3 】提出一种基于视觉特征对应的2 - d 多 边形渐变方法，该方法把初始多边形和目标多边形按照视觉特征进行同构特征分 解。得到若干对对应的特征子多边形，在渐变过程中，每个初始特征子多边形光 滑地过渡到目标特征子多边形，通过引入特征分解点，灵活直观改变特征子多边 形，控制多边形的渐变。该方法可以得到光滑的多边形渐变序列，而且可以实现 多边形的特征对应和特征保留，但用户手工劳动量较多，且不能避免边界自交现 象 1 9 9 6 年，汪国昭等【1 4 1 将平面多边形的每一条边按照向量的形式进行表示， 然后针对每一组对应的边向量建立一条满足向量模长单调变化的变形轨迹，在此 基础上可以简单直接地生成中间关键帧多边形。该方法的优点在于：因为前面介 绍的工作都未能很好地解决刚体运动时边长变化不单调地问题，而将多边形的边 按照向量形式进行处理，就可以入为的构造满足向量模长单调变化的参数曲线作 为边向量的变形轨迹。这样在变形过程中，多边形的边长能够保持单调变化，较 好地避免了中问形状的萎缩扭曲，因而更符合人们通常的审美取向和事物变化的 一般规律该方法采用b 6 z i e r 曲线构造变形轨迹，算法简单易行，且具有一定 的交互功能。缺点是中间参数的设定要满足向量模长单调变化的充分条件和中间 帧多边形的封闭调整条件，有时合理的参数不一定存在而鉴于b 6 z i 盯曲线的 缺点，该方法不能处理等模长的向量变化白宝钢提出基于非均匀有理b 样 条技术的向量混合方法，通过将物体的运动变化分解为变形与刚体运动两个既独 立又联系的部分，再对顶点运动轨迹进行控制，较好地解决了保持单调性的问题。 但是，该方法所讨论的两个多边形必须具有相同的顶点数或边向量数，如遇传统 5 意义上的顶点数不相等，则需要人为干预，使其顶点数相等，且一一对应。 2 0 0 2 年，s u r a z h s k y 和e l b e r y l l 6 魄出了对平面参数曲线的曲率插值来实现变 形的一种方法。该方法基于微分几何理论，即一条以弧长为参数的平面曲线，它 的形状完全由其曲率函数所决定，只是所在位置顶多差一个刚体运动变换。该方 法利用曲线的内在量曲率变形，效果良好。但对于一般的非弧长参数曲线，若用 该方法变形需重新弧长参数化，这不仅增加了运算量，而且一般情况下可能没有 解析解，无法继续施行，故该方法通用性较差。宋伟杰1 1 7 l 针对该方法的缺点和 不足，提出了平面多边形的离散曲率插值变形方法，该方法利用了离散曲率内在 的形状特征，在给出多边形的离散曲率插值变形算法的基础上提出了局部修改算 法。可以根据用户需求对待修改部分进行修改，而保持未修改部分相对不变，达 到了局部修改的目的。 2 ) 将初始图形进行同构三角剖分，将多边形变形问题转化为两个同构三角 网格的变形问题 2 7 - 3 7 1 1 9 9 9 年，f l o a t e r 和g o t s m a n 2 ；5 基于平面三角网格的内顶点的凸组合表示方 法，提出了具有相同凸边界的同构三角网格的变形方法。该方法首先对初始和目 标多边形进行同构三角网格剖分，保证生成的中间关键帧三角网格始终与初末三 角网格同构。在此基础上，计算每个内部节点关于相邻节点的凸组合系数，通过 线性插值初末多边形上对应内节点的凸组合系数计算中间多边形相应内节点的 系数，然后重构中间多边形该方法能保证变形生成的中间关键帧图形不产生自 交现象，且连续光滑。受f l o a t e r 和g o t s m a n 明的启发，g o t s m a n 和s u r a z h s k y l 2 8 1 给出了可避免自交的平面简单多边形的变形方法，该方法将初末多边形分别嵌入 到两个具有相同凸边界的同构平面三角网格中，通过采用f l o a t e r 和g o t s m a n 方 法【2 7 1 首次彻底解决了平面多边形在渐变过程中产生自交的问题，并且应用于图 像变形时，也可以保证中间图像不产生折叠 s u r a z h s k y 和g o t s m a n 在后来的的研究中提出了基于二维图形s t i c kf i g u r e s 表示的变形方法，可控制的同构平面三角网格的变形方法嗍，基于同构三角 网格的内在变形方法【3 l 】，对这种基于同构三角网格变形的方法进行完善，在同 构三角网格的内在变形方法1 3 1 】中，他们采用均值坐标计算内部节点的凸组合系 数，然后用线性插值夹角和边长再计算均值坐标的方法代替直接线性插值凸组合 6 系数。由于考虑了多边形网格的一些内在信息，因此该算法的变形效果有了较大 的改善，也使得这种基于同构三角网格的变形方法得到了迸一步的改善。但是， 这种嵌入相同凸边界的同构平面三角网格的变形方法没有考虑初始和目标多边 形或更一般的s t i c kf i g u r e 的几何形状和相互间的联系，因而变形效果未必令人满 意。特别当同构三角剖分的网格形态较差时，渐交的效果差强人意。因此，高质 量的同构三角网格剖分方法是采用网格思想有效解决多边形变形的一个重要基 础。然而，由于在同构剖分时使用的额外顶点较多，计算中问关键帧多边形时需 要解大型方程组，因此算法的复杂度相当大。 2 0 0 0 年，a l e x a 等人【3 2 j 在s i g g r a p h 会议上提出了基于同构平面三角网格 剖分的方法，该方法将初末物体分解成同构的单纯复形，在两个对应的单纯形之 问定义仿射变换，并将其表示成旋转变换和伸缩变换的复合，然后将这两种变换 线性插值得到期望的仿射变换，再通过使中间物体在最小二乘意义下逼近该期望 的仿射变换，达到扭曲最小的效果。该方法考虑了物体的内部变形具有刚性， 因而效果比较自然，且中间过程不易产生自交，缺点是总体形状扭曲效果未必是 最佳的 宋伟杰1 3 3 对于具有不同凸边界的同构平面三角网格的变形，证明了当初末多 边形均为凸多边形时，采用内在解变形方法可以保证变形产生的中间关键帧多边 形也为凸多边形，称之为保凸性，将其应用在具有凸边界的同构三角网格变形上 可以取得较好的变形效果此外，对于不同边界的初始和目标多边形，可以将其 分别嵌入到各自的最小凸包中，通过对凸包做内在解变形，并采用凸组合的方法 计算内部网格顶点坐标完成初末多边形的渐变过程。该方法相比于嵌入具有相同 边界的平面三角网格的方法，简化了网格的复杂度，减少了添加的内部顶点个数， 相应的算法复杂度也降低了，而且变形流畅自然。但存在额外顶点数目多，运算 复杂等问题。 第二类方法中采用图形同构三角网格剖分的思想对初始图形进行渐变处理 时，同构三角网格剖分质量的好坏将直接影响变形的效果和复杂度。目前，有关 同构三角网格的割分方法主要有b o r i sa r o n o v 【蚓、c r a i gg o t s m a n 和j ，v i t a l y s u r a z h s k y l 2 8 】以及g o t s m a n 2 9 魄出的算法，这里不再介绍。平面图形同构三角网 格剖分技术的相关知识和算法将在第二章进行介绍。 1 3 本文的研究内容及章节安排 本文就二维物体变形技术中的对应问题和插值问题进行了研究。在分析总结 已有变形算法优劣的基础上，针对平面多边形的变形作了以下几方面的工作： ( 1 ) 提出了基于变形点检测的图形顶点对应方法，该算法简单快速，对应 效果自然合理，相比于已有的算法，其适用范围更广。 ( 2 ) 研究了平面多边形变形的向量方法。汪国昭【1 4 】等人提出多边形变形的 向量方法具有算法直观，计算量较小等特点，但其给出的二次b 6 z i e r 插值算法 需要反复设定阈值，显得比较繁琐，且有时不能保证中间多边形的封闭性。本章 提出一种插值初始多边形和目标多边形的对应边向量及其旋转变换矩阵的有效 易行算法，得到令人满意的变形结果。 全文分为五章，具体安排如下： 第一章是本文的绪论，概述了变形技术的研究内容和现状。第二章就已有的 二维物体变形算法进行了总结与评述。第三章给出了一种基于变形点检测的图形 顶点对应方法，所给算法简单快速，对应效果自然合理。相比于已有的算法，其 适用范围更广。第四章研究了平面多边形变形的向量方法，提出了一种插值初始 多边形和目标多边形的对应边向量及其旋转变换矩阵的变形算法。第五章对全文 作了总结，并提出今后进一步研究的方向。 第二章变形的基本理论与方法 针对变形技术中的对应问题和插值路径问题，国内外的学者进行了大量的研 究，取得了不少成果。如s e d e r b e r g 等1 1 1 提出的基于多边形的内在几何属性的变 形算法，c o h e n - o r 和c a r m e l “1 提出的基于d f i 的二维多边形变形方法，a l e x a 等3 2 1 提出的基于同构平面三角网格，保持变形刚性的变形方法，以及s u r a z h s k y 和g o t s m a n 2 8 1 给出的可避免自交的平面简单多边形的变形方法，都是具有代表性 的典型算法，下面就各种变形方法简要作以介绍 2 1 图形的对应问题 2 1 1 采用顶点自身的一些简单的几何或物理信息建立对应 1 采用顶点处的近似切矢建立对应 c o h e n 1 】首先估计顶点处的近似切矢，然后采用对应顶点的切矢内积构造相 似性度量函数，确定顶点之间的最优对应。 定义2 1 若曲线在其参数域内所有的一阶导矢均为非零矢量，则称该曲线是 正则曲线 定义2 2 参数曲线的自交点是指曲线上同一个点对应不同的参数值。 设，0 ) “e ，】和g ( 一，v e v o ，m 】是两条正则的c l 平面参数曲线，即： l | ，( “) 1 1 ) - o k ) l ，o ，则其单位切矢分别为： 圳= 蹴，= 蹦 旺) 若) “) = l ，则弓k ) = “) 假设存在参数变换：，：f “和矿：，寸v 使得“= “( f ) ，v = 砸) 是正则参数化， 即：”，( f l ，( f ) o ，则定义曲线的完全匹配如下 定义2 3 若v f e 【f o ，f 。l ，q ( f ) ) 晰) ) = l ，即曲线p 0 ( f ) ) 与g d ( f ) ) 的切矢在整 个参数区域内平行，则称，0 ( f ) ) 与g o ( f ) ) 完全匹配，如图2 1 所示 9 ，0 ) “y ) 图2 1 曲线的完全匹配 假设曲线以( f ) ) 与g ) ) 完全匹配，则对v s e o , 1 ，它们的中间插值曲线 c ( f ) = ( 1 一s ) ，0 ( f ) ) + 凹( v ( f ) ) 也与，g ( f ) ) 、g ( v ( f ) ) 完全匹配因为 p ( f ) = ( 1 一，妒0 ( f m ( r ) + s g 0 ( f 咖7 ( f ) = ( 1 一s 坨o ( f 瑚p q ( f m ，( f ) + s ( v ( f 溯g ( 砸湖v 母) = ( 1 一s 珥o ，囊舡7 ( f ) 十s ( f 耵( v 洳7 ( f ) = ( ( 1 一s 和0 舡，( f ) + s k ( v 驴( f ) 疋( f ) 这里，利用了( f ) = 易0 ( f ) ) = ( 锄 定义2 4 若v t v e u 0 ，】，g ) ( 如) ) o ，则称在此参数域上曲线以) 和 g ) ) 建立了有效的匹配。 定义2 5 对坼r ，s e o , t ，r e t b f + 】，f 足够小若c ( o = ( 1 一s ) ，( f ) + 明不 自交，则称中问变形曲线c o ) = ( 1 一，如o ) + 钾( f ) 局部不自交 定义2 6 对v s ，“，s e o , 1 ，若c 0 ) = ( 1 一，扣0 ) + 凹) ) 不自交，则称中间变形 曲线c 全局不自交 引理2 1 如果v = 七) 是一个有效匹配，即以v 满足q ) l ) ) 0 ，则生成 的中间变形曲线c 0 ) = ( 1 一，b 0 ) + 蹭0 0 ) ) ，s e o , 1 ，是局部不自交的 由此可见，只要在两参数曲线之间建立一个有效的匹配，则通过使 0 ) ( 以) ) 达到最大就可以减少中间变形曲线的自交。 根据上述理论，c o h e n 给出了自由型曲线的匹配算法： 求可行的正则参数变换v = 以) ，使两自由曲线在整个参数域上的切矢内积达 0 到最大，即求解下列带约束的优化问题： 错c 似) ( 咄) 胁= 胁 ( 2 1 2 ) s j “h o ) = v o ，v ( u 1 ) = h 使两曲线以) 和g ( v ) 达到最佳匹配，其中约束条件是让两曲线的端点分别对应。 注意对于闭曲线可以去掉上述约束条件 由此，可以将自由曲线的变形问题简化。给定两条待融合的平面自由曲线 以) 、q ( 0 ，利用c o h e n 的自由型曲线匹配算法，找到两自由曲线的参数之间的 对应关系，使参数所对应的点处的单位切矢尽可能方向平行，从而也就是建立了 两曲线上点的对应。 2 1 2 提取初始和目标图形的特征点建立对应 提取初始和目标图形的特征点( 一般是从图像上通过像素扫描提取较为密集 的物体轮廓数据，通过现有的提取特征点的方法确定特征点) ，对得到的初末多 边形的特征点集进行匹配，而对应特征点之间的相似度量函数则采用特征点近邻 域内点的相关信息来建立。黄家水【7 1 采用区域像素构造的矩阵来建立相似度量函 数给出一个新的方法来建立两个平面形状特征点之间的对应。 一个平面形体是由一些连续的曲线或者直线段组成源、目标形体被缩放到 相同的尺寸，以免平面形体的相对尺寸影响到对应关系。 1 特征点计算 对于一个给定的平面形体p ，计算它的高曲率点，凸点和变形点。对于多边 形，它的所有顶点都被看作特征点。使用“u 方法 6 1 抽取特征点。 该算法分两步来计算平面曲线的角点设曲线是密集采样的点序列的集合 p ，在该应用中是以像素为单位来采样的第一步，算法先扫描整个点序列，选 出候选角点。第二步，去除多余的候选角点 经过以上两步处理，可以将平面图形记为一些特征点序列p s ，i = o ，l ，月a 为 平面图形的特征点，如图2 2 所示。 2 特征点对应 设初始图形和目标图形分别为：s = 强i f - - 0 , 1 ，m ，d = d ，i ，= o l ，吣， 其中s 和1 7 分别表示初始形状s 和目标形状d 的特征点。如果形状s ( 或者d ) 是封闭的，则晶= s o ( 或者见= 风) 图2 2 一个人形状的两个关键帧，特征点被标记出来 3 特征点的相似厦 定义初始特征点墨与目标特征点d ，之问形状相似代价为： s s i m c o s t ( s l ，易) = 妻( b 一弓，o f gw ，o j s w ( 2 1 3 ) 其中，弓，弓分别为特征点墨，b 的特征点补丁矩阵，即两点之间的形状相似代 价为它们对应的特征点补丁矩阵不相同的元素的个数。它表达了这两个特征点近 邻区域的差异，差异越小越相似。 定义初始特征点s 与目标特征点d ，之间距离相似代价为： l s i m c o s t ( s 。圳= 巨一习 旺1 4 ) 其中，巧写为初始特征点而，蜀之间的距离，岛为源轮廓长度，巧巧为目标特 征点d ，皿之间的距离，厶为目标轮廓长度这里，在按这个公式计算距离相 似代价时，假定了最与d ，是相对应的，并且它们是沿起始特征点方向上分别离墨 和d ，最近的特征点，如图2 3 图2 3 假定特征点相对应 s ，d 为起始相对应的特征点，蜀对应n ，岛对应趣那么在计算马与见之 间的距离相似代价时，离它们最近的且相互对应的特征点分别为s ：，d 2 ，所以这 时的距离相似代价为：是沿轮廓到岛距离除以整个初始形状轮廓长度，见沿轮 廓到见距离除以整个目标形状轮廓长度，这两个商之差的绝对值即为墨，见的距 离相似代价 定义初始特征点蜀与目标特征点d ，之间相似代价为： s i m c o s t ( $ j ，q ) = s s i m c o s t ( $ i ，b ) + w + l s i m c o s t ( $ ，q ) ( 2 1 5 ) 其中，w 表示权重。特征点间的相似代价取值依赖于特征点补丁块宽度矿和权重 w 的选择如果两个点越相似，相似代价就越小 4 对应关系的代价函数 特征点对应就是要将源初始目标形状的视觉上相似的特征点对应起来。根据 特征点之间相似代价函数定义所有初始和目标特征点对应的整体相似代价函数。 假定，是初始特征点到目标特征点的一种对应，：俩叶 d ，) ，定义对应f 的相 似代价函数为： s i m c o s t ( s ，d d = s i m c o s t ( $ i ，珥) ( 2 1 6 ) o 通过解这个函数得到一个f 并且使得s i m c o s t ( s ，d ，) 最小，那么，就是一个 满足视觉要求的最佳对应 2 1 3 通过图形骨架的匹配建立轮廓顶点的对应 上述几种方法一般处理的都是边界信息，缺少内部信息，而骨架能够很好的 提取出物体的内部信息。骨架的对应可以看作是一种动态形式的对应，因为骨架 能够准确的描绘图形局部的萎缩、旋转和凹凸。而基于边界信息的对应算法更像 是一种静态形式的对应。基于物理做功原理的对应方法也算是一种动态的对应方 法，m o r t a r t 等【l o i 使用一种近似骨架来描述图形形状，对初末物体进行近似骨架 剖分，对得到的近似骨架按照一定的相似度量函数建立节点之间的对应，然后再 映射到轮廓上确定初末图形的对应顶点，这些顶点一般都是特征点。在相邻的特 征点之间通过添加新顶点来完成整体顶点的匹配。 定义2 7 给定多边形s ，它的边界多边形为p ；旧e r 2 , f = l ，2 ，n ，设 ( p ) 是基于s 边界的一个d e l a u n a r y 三角剖分， 则s 的近似骨架由图 a s ( s ) = ( ，彳) 来表示。其中节点集n = 亿i 五e r o ( p ) ，正没有约束边或者有两条约 束边 ，弧集_ = 饵，弓) 在t o ( p ) 的正，乃之间有中间路径) 。 如果我们要计算一个复杂多边形的骨架的话，这个提取近似骨架的算法需要 稍微做一些改进，一个以两条边界边为多边形边的三角形也许并不存在如果存 在一个三角形的三条边都不是多边形的边界，近似骨架的构建可以从这个3 级分 枝结点( 3 级节点是指与这个点相关的弧有三条，2 级是指与这个点相关的弧有 2 条，依此类推) 开始，朝三角形的三个方向递归的进行；否则，如果近似骨架 的构建从任何一个以一条边为多边形边的三角形开始，就必须建立一个2 级的伪 结点，伪结点在骨架完成后删除。近似骨架的提取算法的复杂度是很理想的：选 择初始三角形最多需要傲r 次测试( lr o ( 一中的三角形的个数；这样，骨架的 构建只需要对每个被访问的三角形做简单的操作，而且每个三角形只需要访问一 次。因此该算法的时问复杂度为d ( 乃 近似骨架的分解能很好地分辨出多边形的分枝和凸出的部分。参考图2 4 ( a ) ， 可以看出，每一个以终点结束的弧能分辨出图形凸起部分的特征( 图中的灰色多 边形部分) ；每个在两个分枝结点的弧决定了多边形的内部特征。 因此，近似骨架能够更有效地用于描述一个多边形的特征，只需要它符合它 描述部分的恰当的标准。进一步说，每个弧都关联于它所处部分的区域、对应中 间路径的长度和连接线段两点所构成弧部分的“方向均值”( 图2 4 ( 6 ) ) 根据最 终结构的比例，很容易按等级来组织由近似骨架所分解的图形； 1 4 图2 4 近似骨架的结构分解 ( 灰色表示凸起部分，浅灰色表示内部结构( 6 ) 虚线代表与之关联的弧 近似骨架的分枝节点可以看作是物体形状的核心，所以在比较过程中我们必 须首先考虑分枝结点。由于以分枝节点开始的弧特征部分所表现的几何属性对多 边形的形状产生很大的影响。因此，我们首先定义弧相似的标准，这些标准是基 于弧的大小和相对方位的几何量的组合值。然后，定义分枝点的相似度，找出其 所关联的弧，取它们相似度和的最大值这样，图形之间的匹配问题被转化为寻 找骨架中最相似的分枝节点从这些匹配的节点出发，逐步访问骨架中的相似弧 直到终点。这样，位于图形边界的一级节点的对应关系也就确定了。弧的相似度 可以其一些几何属性相加来得到。 定义2 8 ( 弧相似度) 设6 和e z 为两个相似骨架的两段弧，则它们的相似度 s i r e a 编，e 2 ) 定义为： s i m o ( 龟，乞) = 州咖( 岛，e o + j 日瓯刚( 6 ，e o + 岱o ( 5 ，乞) + ，6 0 。( q ，岛) ( 2 1 7 ) 其中： 1 ) k 心，e 2 ) = 0 8