（计算机应用技术专业论文）动作数据的检索技术研究.pdf

浙江大学硕士学位论文 摘要 在角色动画中人物模型是由动作数据驱动的，而动作数据一般通过动作合成 编辑以及动作捕捉技术得到。随着动作数据的急速膨胀，动作数据检索技术变得 尤为重要。本文首先讨论了动作数据记录动作的方法及其参数化表达。检索时通 过动作数据的数值比较定义动作的相似度比较直观，并应用在一个人体击打反应 动作合成系统中。 动作检索也可以通过其他形式如动作标记语言实现。我们设计的算法使得用 户可以通过l a b a i l o t a t i o n 检索动作数据。定义了l a b a i l o 诅t i o n 序列之间的相似性 度量方法之后，系统可以搜索具有相似的l a b 孤描述的动作。算法可以提取出和 部分输入l a b a i l 序列匹配的动作片断。然后通过动态规划这些片断被缝合在一起 构成与查询序列完全匹配的平滑的动作序列。实验结果表明我们的方法可以增强 动作数据的重用。 草图也可以用来直观的描述用户需求的动作。对此我们提出了一个基于草图 的武术动作检索方法。给出分别对应与一个武术招式的起始和终结姿势两幅二维 草图以及特定关节点轨迹，我们设计的m o t i o n m a s t e r 系统通过基于草图的检索 技术可以从数据库中找到原型三维动作序列。该方法可以帮助动画师更多的关注 于动作的编排。 本文第3 ，4 ，5 章分别讨论了上述三种不同形式的动作检索技术。 关键词：动作检索，相似性测度，动作标记语言，时数序列，分段，二维草图， 关键姿势，轨迹比较 浙江大学硕士学位论文 a b s t r a c t f o rc o m p u t e rg e n e r a t e dc h a r a c t e ra j l i m a t i o nt 1 1 ec h a r a c t e rm o d e li sd r i v e nb y m o t i o nd a t a 血i c hg e n e r a l l yi sa c q u i r e dt h r o u g l lm o t i o ns y n t l l e s i s ，e d i t i n ga n dc 印t u r e s i n c et h ev o l u m eo fm o t i o nd a t ag r o w sl a r g e rm o t i o nr e t r i e v a lt e c h n o l o g yb e c o m e sa c 确c a lp a no fc h a r a c t e ra i l i m a t i o n i nt l l i sp 印e rw ef i r s td i s c u s sh o wt h em o t i o ni s r e c o r d e da sm o t i o nd a t aa i l di t sp a r 锄e t 甜z e dr c p r e s e n t 砒i o n a ni n t u i t i v ew a yo f m e a s u r i n gm o t i o ns i m i l 撕t ) ri s t ou s en 砌谢c a lc o m p 撕s o no fm 甜o nd a t aa n di s a p p l i e di na l l i ta i l dr e a c t i o ni n o t i o ns ”n h e s i ss y s t e m m o t i o nr e t r i e v a lc o u l da l s ob ec 痂e do u ti no t l l e rf l 0 n n ss u c ha sm o v e m e n tn o t a t i o n l a n g u a g e w bi m p l e m e n ta 觑i i n e w o r kw h i c ha l l o w st l l e u s e rt or e t r i e v em o t i o n sv i a la _ b a n o t a t i o n as i m i l 矧 母m e t r i cf o rl a b a r l o t a = t i o ns e q u e n c e si sp m p o s e da n du s e dt o s c a r c ht h em o t i o n s 也a th a v es i m i l a rl a b a nd e s c r i p t i o n s o l l rs e a r c ha l g o r i m mi sa b l e t or e 埘e v em o t i o ns c g m e n t st 1 1 a to n l ym a t c hp a r to ft l l eq u 哪7l a b a ns e q u e n c e t h e n b a s e do nd ”l a r n i cp r o g r a m m i n gt 1 1 e s es e g m e n t sa r es t i t c h e dt o g 础e rt of o ma s m o o t l lo u t p u tm o t i o nt h a ti si na i i 叩t i m a ls e n s co fm a t c h i l l gq u e r yl a b a ns e q u e n c e 王泌p e r i m e n t a lr e s l l 重招d e m o n 蛐t eo u rm e m o dc o u l de f l e c t i v e l yi m p r o v et l l eu t i l i z a t i o n o f m o t i o nd a t a s k e t c h d r a 丽n g i sa n o t l l e ri n “t i v ea 1 1 d c o m p r e h e n s i v em e 髓so fc o n v e y i n g m o v e m e n ti d e 鹊w 音p r o p o s e dan o v e ls k e t c h - b a s e da p p m a c ht or e m e v ed e s i r e d k l l n g f i lm o t i o n s g i v e nt w oh u m a nf i g u r es k e t c h e sc o r r c s p o n d i n gt ot l l em “i a la 1 1 d c l o s i n gp o s t i l r eo fak u n g 如f o 埘，a i l dn l e 订a j e c t o r y 捌n g so ns p e c i 6 cm o v i n g j o i m s ，as y s t e mn 锄e dm o t i o n m a s t e rc 趴丘n dp r o t o t y p em o t i o nb ys k e t c h - b a s e d r e t r i e v a li nam 0 6 0 nd a t a b a s e ng r e a t l yh c l p st h ea 血m a t o rf o c u so nt l l em o v e m e n t i d c ad e v e l 叩m e md 面n gt h ee v o l 埘o n a f yp r o c e s so fb u i i d i n gm o t i o nd a t af o r a n i c u l a t e dc h a 船c t e r s t h e s et h r e e 虹n d so fm o t i o nr e m e v a lt e c l l i l i q u e sa r ed i s c u s s e d i n c h a p t c r3 ，4 锄d5r c s p e c t i v d y k e y w o r d s ：m o t i o nr e t r i c v a i ，s i m i l a r i t ym “c ，m o v e m e n tn o 协t i o n ，t i m es e r i e s ， s c 掣n e n t a t i o n ，2 ds k c t c h ，p i v o t a lp o s t i l r c ，t 咧e c t o r yc o m p a r i s o n 浙江大学硕上学位论文 第1 章绪论 随着计算机软硬件技术的迅猛发展，计算机的功能已经远远超出了其产生时 目标一数值计算，以前所未有的势头进入到人类社会的各个领域，在其中掀起了 数字化技术革命。最近2 0 年来娱乐和媒体产业也毫无例外地见证了这场数字技 术革命给产业带来的翻天覆地的变化。这场变革的最大的特点就是将以往基于模 拟的媒体创作方式数字化，从而可以利用计算机强大的处理能力来给人们带来视 觉，听觉，触觉等等多种感官的全新体验。 计算机动画技术是数字化媒体的一个重要的基石，在可预见的将来计算机动 画仍然是人们感知计算机所模拟的真实世界的所必需的途径。计算机动画要实现 的不仅仅是场景和人物在屏幕上的真实再现，还要尽量真实地模拟( 描绘) 运动 的对象。其中对三维角色动画尤其是以人为角色的人体动画的研究在计算机动画 领域更具有特别的意义。人体动画是媒体的重要组成部分，而且在相当的多领域 如娱乐，教育，军事等都有广泛的应用。目前人体动画主要在游戏以及电影特效 中被大量使用，但在其他很多领域也有重要应用，其中包括： _ 医学。人体动画的研究对象一人体动作同样是外科学的研究目标。两者 在步态和动作风格的量化分析等方面的研究有共通之处。 _ 军事。用来实现对士兵的模拟战场训练。 一建筑。实现对建筑设计效果的虚拟体验。 一教育。可以帮助指导工人操作设备或者给学生提供虚拟课堂。 有理由相信在将来对人体动画的需求还会进一步增加。鉴于本文所研究的角 色动画的主体仅局限于人体，因此后续讨论中的角色动画均指人体动画，以免造 成误解。 1 1角色动画中的动作数据 理论上在动画创作过程中动画师只受其想象力的约束，然而在现实中生成动 画却受到多种限制。这些限制既来自于动画师本身创作熟练程度，也取决于动画 师用来创作的工具以及实现这些工具的技术。更大的限制则是出自经济上的考 浙江大学硕士学位论文 虑一一制作复杂的动画产品往往需要投入大量的时间和人力。在动画产品还局限 于二维的时代，很多作品都是动画师手工一帧一帧绘制出来的，这种原始的生产 方式给动画产业的发展带来很大的限制。后来出现了多种技术以提高生产效率， 包括将前景和背景分开的单元格动画阻及先绘制关键帧再补绘中间帧的关键帧 技术等等。这些技术虽然形式不同但有一个共同的核心思想，就是动画素材的重 用和创作流程的简化。这些技术支撑着动画产业的发展，直到二十世纪末计算机 技术提供的强大计算能力和数字化存储在整个产业造成了根本的变革。在这个时 候二维动画已经越来越无法满足人们的需求。然而从二维进化到三维给动画创作 过程造成的变动决不是仅仅增加一个纬度那么简单，三维场景和物体的绘制之复 杂和困难使得以往的技术已经不可行，动画创作只能借助计算机技术的力量才能 完成。 计算机操作的对象是数据，当计算机技术被应用在角色动画当中时，抽象的 数据这时就具体化为动作数据。计算机在绘制动画时总是将绘制的对象定义为一 个个模型，这些模型描述既可以是场景中的静态物体也可以是运动的角色，并可 以从任意的视角和位置进行绘制。对于角色动画而言，计算机需要关注的是角色 的模型以及角色模型状态随时问的变化。角色模型根据时间变化而改变状态的过 程对应于人体动作。 在角色动画中，计算机绘制的模型是由人体骨架层次结构( s k e l e t o nh i e r a r c h y ) 和皮肤网格( s 妊nm e s h ) 构成的，其中骨架结构决定了人体由哪些骨骼如何连接 而成，皮肤网格则作为人体外形的描述和骨架结构关联在一起。显然这种模型是 由人体的生物学构造自然而然得到的，只不过这里的骨架不可能和现实中的完全 一致而是在保留人体基本生理结构的基础上做了很大程度的简化，皮肤网格则可 以看作是包在骨骼外面的体积建模。骨架中各个部分一一骨骼一一之间的相对位 置可以变化( 即相邻的骨骼可以绕连接两者的关节旋转) ，同时与之关联的网格 点( m e s hp o i n t ) 的位置也随之变化。从而骨架结构的状态，包括整个骨架在三 维空间位置和各个关节对应的骨骼的旋转位置，决定了人体的状态或称为姿势 ( p o s t u r e ) 。使用适当的参数化方法，计算机就可以精确记录人体姿势并做运算 处理。 2 浙江大学硕士学位论文 人体动作是一个在时间轴上连续的过程，在计算机里可以通过对其离散化采 样来表示。即每隔固定的时间间隔记录人体的姿势，并用得到的姿势序列来表示 对应的人体动作。由于人体姿势可以用数值精确表示，最终采样的结果是一个参 数序列，我们称之为动作数据。 到此我们已经可以看到，原来作为一个整体对待的角色动画序列已经分解为 模型和动作数据两个部分。相同的角色模型是一致的，只要更改相应的动作数据 就可以生成新的角色动画。这时动画师在创建人体动作时操作的对象实际上是它 的抽象的数学表示，非常适合通过计算机进行运算处理。 有了角色模型和动作数据就可以使用计算机图形学中的渲染绘制技术生成 角色动画序列，并视情况放到整个场景中作为最后完成的结果。这个过程中，动 作数据的生成和获取是关键环节。目前动作捕捉构成了动作数据的主要来源，通 过该技术可以精确地获得人体动作数据，由其生成的角色动画有很高的真实度。 还有很大一部分数据来自于动作数据编辑和合成技术。随着计算机在三维角色动 哂的大量应用，建立庞大和复杂的动作数据库用于角色动画的制作已经逐渐成为 动画产业界不可阻挡的趋势。迅速增长的动作数据给动画师提供了丰富的创作素 材，同时也具有难以管理和控制的特点。目前计算机动画领域对角色动画技术的 研究主要集中以下两个方面： - 如何生成创建满足特定要求的动作数据。除了动作捕捉技术，还可以使 用模拟的方法来生成。动作捕捉的基础是由演员( 被捕捉对象) 来表演 动作，模拟则需要建立合适的模型并用计算机求解以得到合适的动作数 据。这个模型可以是基于运动学，动力学等物理知识，也可以根据人对 动作的感知原理创建。 一如何在已有的动作数据的基础上得到满足新的要求的动作数据。这类技 术包括动作修改，重定向以及数据驱动的动作合成，本质上都属于动作 编辑的定义范畴内。共同点是都需要已有的动作数据为前提，并在上面 建立操作和合成的模型。 1 2 动作数据检索 虽然不同的角色动画技术侧重点不同，但都是以动作数据为核心。当动作数 据不断增加时，这些技术或多或少都面临着同一个问题一一如何在庞大的动作数 浙江大学硕士学位论文 据集中找到需要的动作数据。正如互联网上信息的急速增加凸现对信息检索技术 的迫切需求，动作数据的检索也随着大容量动作数据库的在动画创作领域的普及 而变得越来越重要。 动作检索最直接的应用就是在大量动作数据集中搜索用户需要的动作。检索 对象可以通过关键字描述也可以用动作数据本身作为查询提交以搜索相似的动 作。基于关键字的检索需要对动作数据进行分类标注等预处理，可以手工完成也 可以由计算机自动完成。检索的过程主要是实现关键字的匹配。这种检索技术主 要使用了文本信息检索相关研究成果，对动作数据本身的特征关注较少，和计算 机动画技术关系不大，故不在本文讨论范围之内。 本文主要关注的是基于内容的动作数据检索以及根据特定动画创作技术而 专门设计的动作检索技术。通过基于内容的动作检索，用户可以给出具体的动作 数据作为查询让系统搜索所有包含相似动作的动作数据。查询的形式也不仅仅限 制于动作数据本身，在一些计算机角色动画创作技术中需求动作可能是以其他形 式的信息描述，如动作标记语言，动作草图等。无论哪种都需要分析人体动作数 据的本质特征，动作数据内所包含的动作相关信息，并据此设计高效的检索算法 以达到通过计算机进行角色动画创作的目标。 1 3论文的组织结构 本文其他部分的组织结构如下： 第二章介绍了人体角色动画的技术背景以及目前与动作检索相关的动作数 据重用技术。第三章给出了动作数据的形式化定义，比较了动作数据的多种参 数形式，并介绍了通过动作数据中的数值比较来定义动作相似性度量的方法。给 出了应用结果一一在人体击打反应动作合成系统的实现。第四章和第五章分别介 绍了基于动作标记语言的动作检索和基于二维草图的动作检索及其相应的实现 系统。最后第六章给出总结和对后续研究的展望。 浙江大学硕士学位论文 第2 章技术背景和相关工作 在角色动画中角色模型是由动作数据驱动的。如果不考虑动画序列的绘制和 渲染，动作数据就是计算机角色动画技术最终输出结果。本章首先介绍现有的创 建和获取动作数据的主要技术。越来越多的动作合成技术都是对现有的动作数据 基础上进行重用，而且其中不少需要在动作数据集中搜索合适的动作。因此它们 又称为数据驱动的动作合成技术。实际上本文介绍的3 个系统所使用的技术本质 上都可以看作属于数据驱动的动作合成的范畴。因此本章的第二部分对计算机角 色动画中的动作合成技术做了综述。第三部分则介绍了目前为止已经发表的动作 检索相关研究工作。最后介绍了基于草图的角色动画的相关技术。 2 1创建动作数据 相比其他媒体内容，目前动作数据的获取的代价还是比较昂贵的。比如现在 用家用的数码相机就可以拍到高质量的数字图形。然后要收集高质量的动作数据 或者需要有丰富技术和艺术经验的专业人士创建或者要使用价格高昂的专用设 备。 2 1 1 关键帧动画 手工生成动作数据是目前比较常用的方法。在动画工作室里，动画师经常使 用m a y a 或者3 ds t i l d i om a ) 等专业软件进行创作。在这个过程中，逆向动力学 等技术常常用来提高制作效率，但动画师仍然需要花费大量时间在关键帧中的动 作数据上。这里的关键帧的涵义和传统动画里面的技术是一致的，只不过现在关 键帧之问的那些中间帧可以由计算机插值实现。而在以前中间帧是由初级动画师 绘制的。最早在计算机上应用该原理的过程动画系统是p e r l i n 【1 】实现的，其 中用户手动的构建一些基本动作然后用中间帧插值的方法在这些动作之间过渡。 很多数据驱动的动作合成技术都会遇到中间帧问题，如果需要连接原来分开的两 段动作数据，其中的过渡帧往往通过插值算法生成【2 ，3 ，4 】。最简单的插值算 法是对动作数据中每个关节的旋转角做球面线性插值( s l e i p ) ，并用定义在 o ，1 】 区间的线性或者二次函数控制过渡前后两帧在插值计算中所占的权重【5 】。还有 浙江大学硕士学位论文 人在插值中引入了多路插值的思想【6 ，7 】，在【8 ，9 ，1 0 】人们使用径向基函 数( r b f ) 控制目标帧的权重，插值得到的中间帧用于人体行走动作的连续控制。 后来出现了更为复杂的参数化插值算法，通过对目标动作数据建立统计模型并分 析参数和插值函数之间的映射关系，可以生成符合特定参数要求的插值结果，同 时又保证生成的动作数据的真实度【1 l ，1 2 】。 2 1 2 动作捕捉 动作捕捉技术虽然出现的时间不晚，但以往受技术限制在生成的动作数据时 效果不是很理想。直到近几年随着相关领域的技术进步，动作捕捉生成的动作数 据的效果也有了很大的提高。现在动作捕捉已经是获取高真实感动作数据的首要 方式。不考虑设备使用成本的因素，动作捕捉是获取动作数据最有效最方便快捷 的技术。目前常用的运动捕捉技术主要有机械式、声学式、电磁式和光学式，其 中以电磁式和光学式最为常见，表1 1 给出了这些技术之间的比较。不论哪种捕 捉技术其本质原理就是通过精确记录演员各个身体部位在三维空间中的位置，通 过这些位置得到的动作数据能够真实的还原出人体的姿势，从而达到记录人体动 作的目的。在这篇论文里所有系统的实验动作数据都是通过美国m o t i o n a 且a l y s i s 公司的动作捕捉系统捕获得到的【1 3 】。 捕捉技术成本精度捕捉范围环境要求和灵敏度 机械式捕低较高对表演者的动作阻碍和限制无，可以做到实时测 捉技术很大量 声学式捕较低低声源和接收器间不能有大的受噪声和多次反射等 捉技术遮挡物体的干扰较大，实时性 较差 电磁式捕较低高允许表演范围比光学式要小，对环境要求严格，在 捉技术特别是电缆对表演者的活动表演场地附近不能有 限制比较大，对于比较剧烈的金属物品，否则会造 成电磁场畸变，影响 6 浙江大学硕士学位论文 运动和表演则不适用。精度。速度快，实时性 好 光学式捕高高表演者活动范围大，无电缆、对于表演场地的光 捉技术机械装置等的限制，表演者可照、反射情况有一定 以自由地表演，使用很方便。的要求，实时性好。 2 1 - 3 物理模拟 表2 1 不同种类动作捕捉技术的比较 随着动画师能够使用的计算资源的不断增长，模拟正在逐渐成为角色动画创 建的一个重要途径。b a r a 行和t k i n 在s i g 鲫h1 9 9 7 的课程中对计算机物理模 拟做了很好的概念讲解【1 4 】。该文从模拟的基础一一微分方程不断深入，对基 于物理的角色动画中的两个重要问题一一刚体动力学和约束动力学做了深刻的 回顾。大多数基于物理的角色动画更多地关注人体动作的特定行为。y 趾g 等人 【1 5 】通过物理模拟的方法生成人体游泳动作。游泳角色被看作和液体是完全接 触的，因此模拟的结果可以很好的增加交互性能。h o d 西1 1 s 等人【1 6 】则通过物 理模拟生成具有真实感的运动员的竞技动作，如跑步，自行车比赛等。在他们的 模型中，人体的肢体通过p d s e r v o 来控制，这样人体能够精确的达到预先设置 的位置。f l a t o s o u s 【1 7 】和s h a p i m 等人【1 8 】提出了一个结合了运动学和动力 学的混合模型，从而可以根据环境的限制动态地在不同动画技术之间切换。近年 来不少人试图将物理模拟和可重用的动作数据结合起来，并取得了很好的效果。 z o r d a i l 和h o d 西n s 【1 9 】结合动作捕捉数据和i k ( 逆向运动学) 来驱动物理模拟 中的刚性控制器以生成人体的动态动作。在后续的研究中，z o r d a l l 【2 0 】将类似 的技术应用在人体击打反应动作的合成上，结合物理模拟和动作数据能够根据外 力的大小交互式地生成人体受击打后的自然反应。 2 2数据驱动的动作合成 数据驱动的动作合成技术是很大一类的动作合成算法的总称，是当前计算机 角色动画研究的一个热点。特别是动作捕捉技术使得大容量动作数据库在实践上 浙江大学硕士学位论文 成为可能，更促进了这类技术的发展。顾名思义，该类技术需要事先获得大量现 成的动作数据，本质上它们实现了对动作数据的重用。因而数据驱动的动作合成 总是显式或隐式地使用到了对动作数据的检索组织技术。 前面已经提到，动作捕捉技术能够提供大量具有高真实度的动作数据。目前 数据驱动的动作合成算法使用的动作数据主要来自与动作捕捉技术，但也有一些 来自与关键帧动画，物理模拟甚至是其他的数据驱动的动作合成算法。根据核心 思想，这些算法可以粗略地分为：动作图类、动作混合类、统计模型类。还有一 些算法用信号处理的方法处理动作数据，更偏重与动作数据的编辑，但也可以看 作基于动作数据的合成。 b m d e r l j n 和w i l l i 锄s 【2 1 】开创了用信号处理的方法对动作数据中的单个自 由度进行操作的先河，他们提出的操作包括多级滤波，波形变换和移位映射 ( d i s p l a c e m e n tm a p p i n g ) 。w i t l 【i n 和p o p o v i c 【2 2 】介绍了一种移位映射的变种 称为动作变换( m o t i o nw a r p i n g ) ，g l e i c h e r 【2 3 】则将其应用于对编辑角色在动 作过程中经过路径的交互式编辑。这些算法易于快速高效的实现，但由于它们只 对动作数据中的单个自由度操作，在整体动作协调方面效果不是很好。 有很多动作合成算法都使用图结构来组织动作数据以实现合成新动作的目 标，它们构成了一类基于动作图( m o t i o ng m p h ) 的合成技术。其实在视频游产 业很早就出现了类似的技术，只是到近期才被发表【2 4 】。它们使用的动作图( 或 称为行为树) 往往是用手工方式构建的，需要大量的人工操作。直到近几年出现 了使用计算机生成动作图并据此合成动作的自动算法【2 】【3 】【4 】。这三篇论文 提出了相似的核心思想：在动作数据相似性测度的基础上找出动作序列之间的转 换点，将这些转换点连接起来得到一个图，其中顶点对应于原来的动作数据边则 对应于自动生成的过渡帧，然后在生成的动作图用搜索算法提取出满足用户给出 的约束的动作数据。 还有一些动作合成技术使用统计模型对动作数据进行处理。一些研究者对动 作数据构建基于图的统计模型，其中每个顶点作为姿势生成器而边则表示不同姿 势问的过渡动作【2 5 ，2 6 ，2 7 ，2 8 】。m o l i n a - t a n c o 和h i l t o n 【2 9 】构建了一个 隐式马尔可夫模型( h m m ) ，隐藏状态为动作片断，而跃进概率( 柏i l s i t i o n 8 浙江大学硕士学位论文 p r o b a b i l i t y ) 则取决于要切换的动作在原来的动作数据中是否是连续的。用户可 以确定动作的起始和终结帧，然后使用动态规划算法找到连接动作片断的最大可 能序列。 2 3 搜索动作数据 在上一节中介绍的动作合成算法中，不少都可以看作是在动作数据集中的检 索过程，只不过在结果上和常规的动作搜索不同一一它们输出的动作数据虽然来 自与已有的动作数据但一般是经过处理的，相对原来的数据集是新的动作数据。 常规的动作数据搜索需求是对给定的一段例子要求计算机能够找到类似的动作 片断，输出的是现成的动作数据。因为动作数据本质上是时序数列，因此这是一 个涉及到时序数列检索的问题，在数据库领域有很长的研究历史。然而真正将这 些技术应用在动作数据上，并实现基于例子的查询( 又称基于内容的检索) 的系 统目前并不多。 在数据库领域大部分时序数列检索的方案都是遵从最早由f a l o u t s o s 等人 【3 0 】提出的g e m i n i 框架。给定距离测度和一个查询序列，目标是在数据库 中搜索目标序列使得它们与查询的距离小于预先设定的闽值或者在距离大小排 序结果中排在前面k 位。首先对库中的每个序列提取出一个低维的近似向量，这 可以通过对序列作傅立叶变换【3l 】或者小波变换【3 2 】然后取前面几个系数， 或者使用相邻窗口的平均值【3 3 】或者包围盒【3 4 】。然后用这些低维的近似估 计序列之间真正距离的下限。最后这些低维的信号存放在空间数据结构如r t r e e 【3 5 】中以供检索。c 盯d l e 【3 6 】和k e o g l l 【3 7 】在他们的工作中使用都是这种 g e m i n i 框架的变种。l i u 等人【3 8 】则对动作数据库作c l u s t e r 分析，然后将得 到的簇组织在树结构中，最后的检索转化为在树结构中搜索。需要注意的是，上 述方法不管使用哪种策略裁减检索空间，它们到最后都要计算查询序列和候选序 列之间的相似性，一般使用d t w 或l c s s 度量算法。 上述算法的基础是时序数列之间的距离矩阵，相似性的定义是在序列之间的 l d 范式基础给出的。对于通用的时序数列检索这种假设是自然的，然而在对由 动作数据构成时数序列检索时，结合动作数据特有的属性而设计的算法往往能实 现更好的效果和更高的效率。 9 浙江大学硕士学位论文 m u l l e r 等人【3 9 】将定性的几何特征描述引入到动作数据检索中。根据人体 姿势中肢体之问的相对位置，他们定义了一系列非定量的特征，这样动作数据就 可以转化分割为由特征向量组成的序列。检索时将查询动作数据转换为对应的特 征序列，然后对其应用基于内容的检索技术。由于对特征序列构建索引，并且相 比动作数据参数化比对，特征向量极大地简化了匹配时的计算量，这种方法具有 很高的效率同时也保证了检索结果是相对精确的。图2 1 是他们给出的有代表性 的几种几何特征的定义。 图2 1 在特定姿势中身体不同部位之间的相对空间位置构成了该姿势的一个几 何特征，这些部位在图中有红色和黑色的点标出。( 出自【3 9 】) 与上文的思路类似，f o r b e s 等人【4 0 】也试图通过简化动作数据以提高检索 的效率，不过他们的方法是使用统计学模型对动作数据进行处理。【4 0 】使用加 权p c a 算法对动作数据库中的数据进行分析降维，然后通过提取序列特种点 ( c h a r a c t e r i s t i cp o i n t ) 和序列的d t w 比较算法进行匹配搜索。图2 2 是降维后 动作数据的状态。 图2 2 降维后，动作数据的在3 维空间的可视化表达。( 出自【4 0 】) l o 浙江大学硕士学位论文 s a k a m o t o 等人【4 1 】设计了一个使用图像对动作数据检索的算法。在一个称 为自组织图( s e l f o 唱a l l i z i n g m a p ，s o m ) 的非线性数据降维算法的基础上，系统 自动将数据库中的动作序列其分段并对每一段提出一个关键帧。用户只需提供所 需动作的对应的关键帧图像，系统能够从数据库中找到相应的动作。这种技术方 简化了用户浏览动作数据集的操作，但也限制了用户的查询形式一一提交的查询 帧必须在系统提供的图像选取。 图2 3 m o t i o n m 印系统界面( 出自【4 1 】) 类似与上述研究人员提出的检索系统，我们也试图通过从动作数据中提取关 键信息( 即用户真正感兴趣的信息) ，并设计算法加速对提取出来的关键信息进 行检索。我们尝试使用两种方法将高维的动作数据映射到低维信息上，这样既可 以保留用户在检索时真正感兴趣的内容，同时减少搜速匹配时的计算量。这两种 方法分别是将动作数据转换为动作标记语言和动作的二维姿势草图，分别在第四 和第五章给出具体的描述。 2 4 基于草图的角色动画 本文第5 章介绍了一个基于草图进行武术动作检索和创作的系统一一 m o t i o n m a s t c r 。故在此介绍与之相关的计算机视觉和动画领域的工作。 2 4 1 从单视点恢复三维姿势 浙江大学硕士学位论文 因为缺乏足够的空间信息从单视点恢复三维姿势具有确定性。主要的难点在 于一幅二维的草图可能对应于多个三维姿势。在计算机视觉领域，最早的关于从 单目视频序列重建三维姿势的研究可以追溯到上世纪八十年代【4 2 】。【4 3 】【4 4 】 对这些技术做了很好的总结。大体上主要有两类方法解决该问题，一种是基于模 型的，另一种则是基于学习的。基于模型的方法假设三维骨架结构是预知的，并 用人体的关节模型生成与二维草图匹配的三维姿势。为了获取最好的重建结果可 以用物理，环境和动力学相关的约束筛选合理的三维姿势【4 5 】【4 6 】。而基于学 习的方法，则通过学习推断统计模型过程自动地推断二维图像和三维姿势之间的 对应关系【4 7 】。这种方法需要大容量训练数据集。c l l i u 等人则用样本动作数据 构建了一个人体姿势库，并通过搜索姿势库的方法生成与给定二维姿势图像最相 似的三维动作，然后在用基于约束的方法对搜索得到的三维姿势进行修改使之更 符合其二维投影【4 8 】。本文第五章提出了类似的算法，但我们的算法目标不仅 仅是生成单个三维姿势，而是在动作数据库中找到与二维草图匹配的动作序列。 2 4 2 基于草图界面的动画 早期的动画师都是通过草图进行动画创作的，而当进入计算机动画时代要完 全实现这种创作方式反而比较困难。虽然草图动画给动画师的创作提供了很大的 灵活性和发挥空间，但是目前的技术水平距离让计算机真正识别随意性很大的草 图并完全符合动画师的创作习惯还有很长的路要走。 s a b i s t o n 试图用二维示意图描述姿势，他假设动画师已经了解透视投影的相 关知识，然后通过计算透视缩短的程度决定三维姿势的关节角“9 】。d a “s 等人 【5 0 】提供了一个简单的基于草图的动画创作系统。用户在二维草图上标出骨架， 然后系统重建出一系列与其匹配的姿势，并引导用户进一步筛选不符合要求的姿 势。n o m e 等人则关注高层次的动作，并提出了曲线动作标注来对动作进行约 束。所有的动作都可以用连续的直线，弧和圆环表示【5 l 】。o s h i t a 【5 2 】给出 了用画笔作为交互工具来创作人体动作的系统，其中画笔产生的笔画被映射到动 作的轨迹上。 在基于草图的角色建模方面，i g 撇s h i 等人【5 3 】给出了通过草图界面快速 设计自由形体模型的方法。用户在屏幕上给出二维的自由形笔画系统自动的重构 辑汪大学硕士学位论文 窭穗酝懿三维多边形表嚣。c 蠹黝蘸挂f i 等入【5 4 】疆窭7 在动蘧孛使曩蘩予裁戆 创作技术。他们的方法允许角色模型根据视线方向的变化自动地做出反殿。 1 3 浙江大学硕士学位论文 第3 章动作数据及其相似性测度 前面已经提到，动作数据是本文所关注的动作检索技术的核心。动作检索不 可避免的要涉及到计算动作相似性，即给出两段动作序列如何比较两者之间的相 似程度。因此在深入介绍我们设计的算法之前，有必要给出动作数据的详细定义， 包括它记录三维人体动作的方式，在计算机中的数据参数化形式，以及如何在动 作数据的基础上定义不同动作序列之间的相似性( 即它们之间的距离) 。 在本章，我们讨论的内容包括： 给出了动作数据的数学定义及其原理，以及根据动作数据计算机能够在 屏幕上精确地再现三维人体动作。 给出了动作数据的数值比较方法，讨论了这种方法在确定动作相似性时 的效果。 最后作为上述技术的实际应用，介绍了一个生成人体受击打后反应动作 的系统。该系统使用了结合物理模拟和动作捕捉数据检索，其中使用的 动作检索技术基于动作数据的数值比较方法。 3 1 动作的表达 在绪论中已经提到人物角色动画是通过由关节点连接的骨骼模型表示的。这 些由骨骼连接的关节按照层次关系组成了一个树结构。图3 1 给出了一个常用的 骨架模型，关节点的名称随不同的动画系统可能会有所不同，但大致上的结构是 类似的。每个关节只有一个父节点并且和一个相对其父节点定义的坐标系关联在 一起，而且每个关节都定义了两个分量：旋转( 或称朝向) 和位移。位移定义了 关节和其子节点的空间距离( 对应于相关骨骼的长度，如果系统中骨骼被认为是 不变的刚体) ，而旋转分量则决定了该节点以下所有子骨架( 包括其子节点) 相 对于该关节的朝向。 1 4 浙江大学硕士学位论文 嚣i 瓢却。s 陋j 物g e r t i p s 塾卸。 图3 1 骨架模型示意 一旦某个个关节点对应的朝向发生了变化，则相应地以它为原点定义的局部 坐标系也发生了变化，而它的所有子节点相对位置也随之变化。在数学中朝向的 变化对应于旋转变换( r o 诅t i o n 咖s f o n n a t i o n ) ，可以由一个旋转矩阵表示。一般 而言人体关节的旋转范围是有限制的，在角色动画模型中这种限制表现为关节点 只能绕某些轴旋转，称为为关节的自由度( d o f d e g r e eo f f r e e d o m ) 。从每个关 节点的自由度参数可以得到对应的旋转矩阵。 骨架结构中的变换包括旋转和平移两部分，根据前向动力学可以根据动作数 据中的关节自由度数值计算其空间位置。如图3 2 描绘的关节和骨骼层次结构， 每个关节有一个关联的平移矩阵，表示为t i 。关节的旋转变换矩阵表示为r 。 根节点的旋转和平移变换结合在一起用m 。表示。p i 表示关节点在世界坐标系 下的空间位置坐标。 。；。；。，。，。 w j，r卜阳阳；。0重 浙江大学硕士学位论文 图3 2 关节点旋转和平移变换示例 # = 互尺。鸠 昱= 五r ：墨 b = 互b b ( 3 1 ) 只= 五尺。b 公式( 2 1 ，2 ，3 ，4 ) 给出了计算关节点p i ，p 2 ，p 3 ，p 4 空间位置的方法。 将每个节点的旋转变量记录下来，就得到了一个人体姿势的完整描述( 注意： r o o t 作为骨架结构中的一个特殊节点，不仅需要记录旋转变换而且也要包括其在 空间中的世界坐标，否则无法确定该姿势的位置。其他的节点则只需旋转变换， 而对应的平移变换作为固定的参数是预定的) 。通过选取特定的旋转矩阵参数化 方法，最后可以得到一个表示特定姿势的向量。 这样动作数据可眺形式化为一个定义在时间轴上的多维函数m ( t ) ，每个时间 点上的值对应于描述该时刻人体姿势的向量。 相应的动作数据可以由式子3 - 4 形式化表示。其中d 是r o o t 节点在世界坐标 系下的位置，q i 是第i 个关节点的旋转变换( 关于三维图形变换的数学原理和方 1 6 游瞧大学硕士学位论文 法豹螽绥霹浚参考穗关诗算辍銎澎学教秘) 。 m ( ) = ( p ( f ) ，9 1 ( 吼吼( f ) ) ( 3 2 ) 动俸本质是逐续的，聪在计辣机中只熊离散识表示。因此动作数据爽际是对 连续动作的离散采样。所有采样点上的数据构成了一个时数序列。 3 2 动作数据的参数化表示和褶儆性度量 动捧数据主蘩记录豹蹩关节纛瓣旋转分量。蠢鎏形掌串除了旋转矩黪，还霹 以用其他数据结构表示旋转，而，鼠往往程特定应用场合商更好的效率和效果。使 不同的旋转表这方式对瘦子不同的动作数据参数亿方法。在实际应用中，常觅髂 参数化方法分别是：欧披角表示法，四元数表示法和轴一关节角表示法。 这些不同的参数化方法对应予数学上对旋转矩阵的不间表示，在记录动作的 效栗主燕一致豹。毽是建瘸在不溺靛动佟数据楚壤技术上，翔动体会残，动作梭 索，则表现除不同的稳定性，复杂度和效果等等。特别地，对动作检索技术而言， 参数伍方法最好熊满足蔽下要求； 麓法性。 用尽可能小的空间代价存储动作数据。 - 凭奇异饿 奇异往往往会影确到渤作数瓣沈较静准磕瘦。 l 乎滢插悠 如果需要将动作加遴或延长后再进行匹配，则需要使用插使算法生成中间 顿。诧时高效的平滑插值算法就显得院较熏簧。 甥手抉逮诗算的蜒亵测发 动作检索算法的大部分时间耗费在计算动作序列之问的相似性上。如果能够 浙江大学硕士学位论文 减少动作数据距离测度计算的时间，则可以大幅提高检索的效率。 接下来的3 2 1 3 2 5 介绍了多种参数化方法并讨论它们的优缺点。 3 2 1 欧拉角 根据欧拉旋转原理，任何旋转都可以分解为绕3 个互相垂直的轴的旋转。图 形学里这三个轴对应于欧氏空间的三个坐标轴x y z ，绕这三个轴的旋转分量分 别称为p i t c h ，r o l l ，y a w ，如果分别用巾、o 和1 l r 表示，则这三个分量叠加以后 的旋转矩阵为： rc o s m ：i s i n l o rc 。s 5 f ， i _ s i n 妒 l o 3 2 2 四元数 0 l o o o c o s 秒 1 jl o s i n 目 0l oi - j ( 3 3 ) 四元数( q u a t 锄i o n ) 是对复数的扩展，很早就在数学界被提出来，但直到 上世纪八十年代才被应用在图形学和计算机动画领域【5 】。类似与复数，四元数 由实部和虚部构成，分别对应于一个标量和三维向量： g = v 】- w + 耐+ 剪+ 如( 3 _ 4 ) 其中w 为实部，v 为虚部。i ，j ，k 满足i 2 _ j 2 = k 2 一l ，i 牛j = j k _ k + 矗1 。两个四元数 q 12 【w 1 ，v 1 】_ ( w 1 ，x 1 ，y l ，z 1 ) 和q 2 = 【w 2 ，v 2 】- ( w 2 ，) 【2 ，y 2 ，也) q 2 的叉积定义为： 1，j 秒秒 o 口 s c 矽痧 n 硌o m 嘶0嘶一。咖瞄。 游江丈学硕士学位论文 q l q 2 = ( w l w 2 - v l v 2 ，w l v 2 + 、谨v l + v l v 2 ) ( 3 5 ) 任意个三维向量v 都可以扩展成为个实部为0 的四元数q v = 【o ，v 】，则用 疆元数q 对淘蟹v 的交换蹩逶：遘始下公式( 3 6 ) 实凌豹； 玑= g 一- 吼g ( 3 。6 ) 其中q - 1 楚q 的舱逆，满足遵q 一1 。如果要保疆变换罴线性的，郄不改边囱量 的长度，要求q 为单位四元数，即q 满足 删= 拍呶擘) = 乒i 瓦歹再一l ( 3 7 ) 程动作数据里每个关节点旋转对斑的图元数都燕单位匿冗数，从丽保证了动作数 据对骨架结构的变换是剐性的( 啦：i d ) 。 3 2 3 轴旋转角 任何旋转都可以看作物体绕某个特定的轴旋转了某个角度，用这个角度( 标 爨) 去乘旋转辘霹应豹羯塞( 擎绽岛量) 帮为辘一旋转角表示。实际主黪遴元数 转化为对应的指数映射就可以得到其对成的旋转的轴一旋转角表示。 3 2 4 关节点空间位避 动作捕捉时能够直接得到的数据就怒关节点( m a r k e r ) 的空间位置，然后通 过逆恕运动学( 1 k ) 计算得到关节角，和3 。l 节余绍的起套相比是一个逆过程。 这种记录姿势的方法很赢观，而应用在动作相似性度量上面时也有很好的效果 萋2 】。 3 0 。5 动作数据的相似性度蘸 1 9 巍江太学璇圭学位论文 这里要介绍的是在针对幼作数据本盛的数值比较撼础上定义的相似性度量。 禚这里只要动作数据之间的数值差异比较小，就认为渤作是相似的。 首先要给游计算不同三维人体姿势之闻距离蕊方法。设存两个三维姿势分剐 表示为p l 和p 2 ，它们之间的距离可以定义为： d ( 墨，端) = 妻_ l