（计算机软件与理论专业论文）动画自动生成系统中布局规划的研究.pdf

摘要 随着计算机动画和人工智能技术的发展，计算机在动画片制作方面的应用 从最初的动画片后期制作逐步发展到动画片制作全过程的自动化生成。中科院 数学所陆汝钤院士提出了全过程计算机辅助动面生成的设想，从文学剧本出发， 经过自然语言理解、导演规划、分镜头剧本的定量转换、三维动画生成等一系 列过程，最终生成一个计算机三维动画片。 出陆汝钤院士领导的小组从1 9 9 0 年，r 始，已经着手研究如何基j ：全过脞汁 算机辅助动画生成技术生成动画，该计划被称为天鹅。经过十多年的努力， 天鹅已经初具规模，它生成的动画片三兄弟也曾在中央电视台中播出。 布局规划( 1 a y o u tp l a n n i n g ) 是动画自动生成中的一个重要环节，它的任务是 为故事中出现的每一个场景确定所有角色和物体的初始位置。本课题研究如何 根据动画自动生成系统的实际需要，基于约束求解机制，运用本实验室研制的 b p u c l p ，设计和实现出一个布局规划系统。在动画自动生成系统中，布局规 划系统具有独立的知识库和通用推理机，能根据故事中的各种情节和场景的描 述，结合知识库中的各种常识和约束，运用通用推理机对场景中出现的人物和 物体规划合理的初始位置。 本文介绍了基于约束求解机制的布局规划系统的总体设计思想和各模块的 基本实现原理以及约束求解系统b p u c l p 的基本功能和实现原理。重点研究 了如何基于约束求解机制，用b p u c l p 程序表示布局规划系统知识库中的知 识，以及如何构建布局规划系统的通用推理机，借助这些知识求解布局规划问 题。并且，本文将基于约束求解机制的布局规划系统与本课题组提出的其他布 局规划系统进行比较。同时，本文还在上述理论基础上提出了动画自动生成系 统中的布局规划系统的开放性框架，并利用此框架实现了一个布局规划原型系 统，表明该框架是一个具有可扩展性的开放性系统平台。 关键词：动画自动生成；布局规划；约束求解；b p u c l p a b s t r a c t a st h ed e v e l o p m e n to ft h et e c h n o l o g yo fc o m p u t e ra i d e da n i m a t i o na i l da i ，也e a p p l i c a t i o no fc o n m u t e rt e c h n o l o g yi na n i m a t e df i l mp r o d u c t i o ni sa l s om a k i n gg r e a t p r o g r e s s 行o mt h eo r i 百n a lp a r t so fp r o c e s s i n gs u c ha sm o d e l i n g ，m o t i o na n dc a m e r a d e s i g n i n 蜀a n i m a t e dp i c t u r eg e n c r a t i n g ，t ot u 曲o u tt h ee n t i r ea u t o m a t i cg e n e r a t l o n o fa n i m a t i o nf i l i l l t h ea u t o m a t i cg e n e r a t i o no fc o m p u t e ra n i m a t i o n ，ap r 蜘e c t w h i c hi sp u tf j n a r db ya c a d e m i c i a i ll ur u q i a l l 疔0 mt h ei i l s t i m t eo fm a c h 啪a t i c s ， c h i n e s ea c a d e m yo fs c i e n c e s ，p l a i l st 0e s t a b l i s hs u c has y s 协nt h a tm a n i p u l a t e s t h r o u 曲o u tt h ep r o c e d u r eo fa n j m a t e df l l l nm a k j n g ：t a k i n gas t o r ya si n p u t ，n a t u r e l a n g u a g eu n d e r s t a i l d i n g a n p m c e s s i n 岛 d 油c t o rp l 锄i n g ， q u a n t i t a t i v e d a t a g e n e r a t i n g 知ms h o o t s c r i p t ， a i l i m a t e d p i c t u r eg e n e r a t i n 岛 m e nt h ef i n a l 3 一d i m e n t i o n a la n i m a t e df i l i l l f m m1 9 9 0 ，a 目o u p1 e a db ya c a d e m i c i a l ll ur u q i a l ls c ta b o u tr e s e a r c h i n ga 工l i m a t i o n b a s eo na s s u m eo ft h ea u t o m a t i cg e e r a t i o no fc o m p u t e ra n i m a t i o n ，n 锄e d s w a n ，t h m u g ht c ny e a r s e f f o n ，s w a nh a v ed e v e l o p e dam u 曲p r o t o t y p e ，a c a n o o n p r o d u c e db ys w a n ， c a l l e d“t h et h r e e b r o m e r s ”， w a ss h o w t lo n c c t v ( c h i n e s ec e n t r a it e l e “s i o ns t a t i o n ) l a y o u t p l 籼i n gi so n eo ft h ek e ys t 印si nt h i sp r o c e d u r e ，w h o s et a s ki st oc a l c u l a t e t h eo r 嘻n a lp o s i t i o n so fa um l e sa n da l lo b j e c t s 印p e 撕n gi ne a c hs c e n e mt h i s p 印e r ，o u r r e s e a r c hf o c u s e s o nh o wt od e s i g i la 1 1 dd e v e l o pa1 a y o u t p 1 姗i n gs y s t e m ， b a s e do n 1 ec o n s t r a i n tp r o g r 帅m i n gs t r a t e g yt h el a y o u t _ p l a n n i n gs y s t e mu s e st 1 1 e b p u c l p a c c o r d i n gt o t h 。r e a lr e q u i 咒m e n t so ft h ea u t o m a t i cg e n e r a t i o no f c o m p u t e ra n i m a t i o n i nt h i ss y s t e m ，l a y o u t p l a r u l i n gs y s t e mc o n t r o l s i t so w n k n o w i e d g e b a s ea i l dr e a s o n i n gs t r a t e g yn h a sa ni n p u to fl i m i t e df a i r ys t o r ya i l dc a n g e tt h er e a s o n a b l ei n i t i a lp o s i t i o n so ft h ep e r s o n sa n do b j e c t si nt h i ss c e n e ，w j t ha 1 1 t h ec o m m o ns e n s e sa n dc o n s t r a i n t si ni t sk n o w l e d g e b a s e ， i nt h i sp 印e r w ew i l li n t r o d u c et h ed e s i g no f l a y o u t - p l a n n i n gs y s t e ma n dt h em a i n t h e o r yo fe a c hm o d u l ei nt h i ss y s t e m ，b a s e do nt h ec o n s t r a i n tp r o g r a m m i n g s t r a t e g y a l s ow ew i n t m d u c et h eb a s i cf 宅a t u r e sa n ds 仃a t e g yo fb p u c l p ，ac o n s n a i n t p r o 掣嬲m i n gs y s t 锄b a s e do nt h ec o n s t r a i n tp r o 舒锄n i n gs 渤t e 甄w em a i n l y f o c u so nh o wt oe x p r e s st h ek 1 1 0 w l e d g ew i 血m eb p u - c l pi nm e k n o w l e d g e b a s eo f t h el a y o u t p l a l l l l i n gs y s t e ma 1 1 dh o wt oc o n s t r u c tt 1 1 e g e n e r a lr e a s o n i n gm a c h i n et o s o l v et h el a y o u tp r o b l e mw i t hi nt t l e 1 a y o u t p l 锄i n gs y s t e m i n l i sp a p e r w e c o m p a r et h el a y o u t p l a n n i n gs y s t e mb a s e do nc o n s n 面mp r o f a r i l m i r 培w i t l lo t l l e r l a y o u t p l a n n i n gs ) ，s t e n l sb yo l l rr e s e a r c hg m u p f i n a l l y ，w ed e s i 鲫e da no p 肌 a r c h i t e c t u r ef o rl a y o u t p l a n n i gs y s t e mi nt h ea u t o m a t i cg e n e r a t i o no fc o m 口u t e r a n i m a t l o n a n db a s e do nt h i sa r c h i t e c t u r e ，w e d e v e l o p e d a p 1 - o t o t y p c 。f l a y o u t p l a n n i n gs y s t e m t h ee x p e r i m e n t ss h o wt h a tt h es o l u t i o no f1 a y o u t p l a n n i n g p r o b k 盯la n dt h ea r c h j t e c n i i ei ss u c c e s s 如1 k e yw o r d s ： a u t o m a t i cg e n e r a t i o no fc o m p u t e ra n i m a t i o n ； l a y o u tp l a 皿i n g c o n s t r a i n tp m 伊a m m i n g ；b p u c l p v 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：翌旦】茎嘲翌鱼亟圈 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 繇丝赫桦 日期：兰! l 垒旦至日 1 1 课题研究背景和意义 第1 章绪论 本课题一动画自动生成系统中布局规划的研究，是动画自动生成系统的 一个重要组成部分。在本节中，我们主要介绍动画自动生成系统的研究背景和 意义。 1 1 1 研究背景 计算机动画是计算机图形学和艺术相结合的产物，它是伴随着计算机硬件 和图形算法高速发展起来的一门高新技术，它综合利用计算机科学、艺术、数 学、物理学和其它相关学科的知识在计算机上生成绚丽多彩的连续的虚拟真实 喊面给人们提供了一个充分展示个人想象力和艺术刊能的新天地。在过去几 十年星，计算机动画一直是人们研究的热点，但是传统的动画制作过程是一个 非常繁琐的过程，要求动作制作者手工绘制出动画中的每一帧画面，因此使得 动画的生成数量和质量受到很大限制。把计算机技术应用于动画制作是动面生 成的一大突破。利用计算机强大的计算能力，只需给出角色运动的一些关键状 态，计算机便可自动生成中间状态，从而大大减轻动画制作者的负担，而随着 计算机三维图形处理技术的日新月异的发展，人们开始模拟在三维空间中自由 移动的摄像机，从不同的位置，不同的角度拍摄在三维空间中移动的物体。 计算机动画的研究课题包括动画硬件和软件、计算机辅助动面、绘酾系统、 动作控制、关键帧动面、图形模拟、基于力学的动画、合成角色、动画中的图像 r e n d e r 、动画语言和系统、动画者界面、电影实例研究、路径规划、三维医学图 像、分子图形学、飞行模拟器、语音合成、视频动画、应用于计算机动画的传统 动画技术、科学可视化中的动画、工程中的动画、基于人工智能的动画、动衄q ， 的机器人学方注、特殊效果、实时动画、录像录音技术、场景制作、故事图板生 成、数字化音乐和声音等等，其中，基于人工智能的动画研究如何将人工智能技 术用于计算机动画、从而提高动画制作的自动化程度和智能性。 由中国科学院陆汝钤院士提出的全过程计算机辅助动画片自动生成f 2 1 是计 算机动面技术一个崭新的课题，它是人工智能技术与电影艺术图形学的结合 算机动面技术”一个崭新的课题，它是人工智能技术与电影艺术图形学的结合 北尿下业人学t 学坝七掌位论文 是以底层图形学技术为支撑，在上层运用人工智能技术以及电影艺术实现的一个 全新的领域。整个过程是一条动画片生产自动化的技术路线，它的目标是只要有 了一个适当的故事，以受限自然语言的形式把它输入计算机罩，从此时开始，直 到最终尘成动画，每一步都是在计算机辅助下完成的。 1 1 2 研究意义 全过程计算机辅助动画片自动生成不仅具有创新性，同时，对动画电影产业 的发展和科研有着重要的意义。我们可以从以下两个方面来看f 2 】： 从产业发展来看，动画片的自动生成技术可以缩短动面生产过程的周期性。 有资料显示，动画片的制作周期很长，一般需要三年左右，而其成本则每分钟5 0 0 0 元到8 0 0 0 元。因此，如何在时间上获取优势，一直是各个动画片片制造商们关注 的问题。基于现实生活中电影制作的种种问题，我们采用人工智能技术，让计算 机成为电影制作的核心，而人只是辅助地做一些工作，从而缩短制作过程的周期， 这是十分具有意义的。 从科研角度来看，它是人工智能技术重要的试金石。许多人对计算机的计算 和推理能力给予了肯定，但是想要在全局把握的能力上超过人脑是不可能的。多 年来，人工智能技术得到了一定程度的应用，如人机对战，专家系统等。那么， 该课题为其发展丌辟了一个新的应用。同时，由于该课题是多个领域知识的综合， 它也有助于相关学科的发展。 布局规划是动画自动生成系统中的重要部分。它规划了每个场景中物品和 角色的初始摆放位置，为以后的动画生成做准备。我们研究的布局规划系统是 自动的，它不需要人工干预，可以根据导演的意图产生不同的布局，这样既可 以避免产生千篇一律的动画，又可以体现出动画自动生成的智能性。 1 2 国内外相关研究现状 目前，计算机动画已进入实用阶段，国际上涌现了许多优秀的动画软件。用 于图形工作站上成熟的商品化动画软件主要有美国的w a v e f r o n t 、加拿大的 s o f t 蹦a g e 和a l a s 、法国的t d i 等。一些动画领域新的研究成果得到了迅速 的应用，如粒子系统、群体运动、f f d 变形技术、动力学模型、关节运动、二 维m o r p h i n g 技术等都可从这些优秀软件中见到。这些动画软件由于各自的特色和 第1 带绪论 优势，都拥有广阔的市场，并都在不断推陈出新，逐步完善和改进。 近几年浙江大学、北方工业大学、中国科学院软件研究所等单位相继从国 外引进了商用动画软件，并在电视片头、动画广告设计方面取得了很好的成效。 浙江大学用a l 认s 和s o f ti m a g e 软件进行兵马俑的动画设计，中国科学院软 件研究所利用t d i 的e x 口1 0 r e 软件设计了第1 1 届北京亚运会片头，北方t 、i p 人学存 齐东旭教授的主持下研制了我国第一部全部用计算机编程制作的科教电影片相 似。 1 2 1 基于人工智能技术的动画研究现状。1 基于人工智能的动画研究如何将人工智能技术用于计算机动画，从而提高动 画制作的自动化程度和智能性。在本节中，我们将介绍这一领域的研究成果。 ( 1 ) 自然语言指令驱动的动画 自然语占指令驱动的动画技术研究如何由自然语占指令和其它高级任务规 范说明来产生虚拟人类a g e n t 完成任务的动画模拟。这方面的系统有如下几个： a u l y s s e 【3 】是一个使用户可以用自然语言在虚拟现实环境中漫游浏览a g e m ， 它主要包括一个语法分析器、语义模块、语言到虚拟实体的映射器、几何推理器 等，u l y s s e 使用规划规则来构造动画，并能和语音识别系统交互。u l y s s e 的研制 者目前的工作是研究如何从语言文本来生成场景。 b 微软的p e r s o n a 项目 4 】致力于产生能够和用户进行自然语音对话的拟人格 化的动画角色，该项目基于微软开发的一个独立于谈话者的连续语音识别系统和 一个覆盖面广的英语理解系统，p e r s o n a 采用拟人化的对话机制，角色说话时还 有动作相配合。 c 美国海军研究室致力于研究面向浸入式虚拟现实环境的自然语言和语音 理解界面n a u t i l u s 项目【5 】通过使用口头命令，用户可以在模拟的三维环境中漫 游、移动或隐臧虚拟物体、控制模拟回放等，一个包含有关虚拟世界和物体信息 的知识库支持了这些功能的实现。 d 美国宾州大学对基于指令的动画生成技术已经进行了十多年的研究，研制 成功了许多系统，他们的a n i m n l ( a n i m a t i o n 疗o m n a t u r a l l a i l g u a g e i n s t n j c t i o n s ) 北京丁业人学t 学坝i 学位论文 项i p 1 1 】的f 1 标是生成真实的动而束表现人执行f 1 然i 等。讨旨令所嘲州的任务的 过程，它的功能流程一般说束包括自然语苦语法分析、语义分析、规划推理、规 划、模拟和人物动画：a n i r i 】n l 支持对指令的语义和语用理解，以及这种理解随 着动作的演化：a n i 啪l 所生成的动画不仅包括人的一般肢体动作，还有人的面 部表情、手势、和语音合成；a n i m n l 提供了各种知识库以支持各部分的功能。 ( 2 ) 知识驱动的人体跑步动作的动画生成 文献【1 2 怫1 介绍了生成各种实时人体跑步动作的动画高层控制技术。所谓高层 控制是相对传统的低层关键帧技术而言的，是通过采用有关人类跑步的知识来实 现的，该系统中的知识分为若干类：关于跑步动作参数之| 8 j 关系的实验知u ，川 于计算人体运动轨迹的物理知识，关于跑步时肢干协调性的知以等等。在这种基 于知识的控制机制的支持下，用户可以交互式地调整高层参数以实时地得到满意 的跑步动作效果。 ( 3 ) 模拟人类对话的动画形象 美国m i t 媒体实验室的手势和叙事语言小组一直在研究和构造用于对话的 逼真的动画形象 旧】，基于对人类语言、认知和社交能力的深层理解，他们的 动画形象能够模拟人类和用户对话，包括语音、语调、手势、面部表情、头部运 动、眼神等。他们的系统的主要特点包括多模式输入和多模式输出、实时、命题 性和交互性信息的理解与合成及具有诸如转折等对话能力。系统的静态知识库、 动态对话知识库、规划模型和对话模型等支持了这些功能的实现。他们已经研制 了若干能和人对话的动画角色，例如a v a t a r s ，g a l l d a l f ，r c a 等。 ( 4 ) 一系列相关事件描述到角色语音和面部表情的自动生成 b y m e 系统【2 0 】以r o b o c u p 模拟器的输出为输入，基于角色的个性、情感状态 和比赛情形来产生角色富有感染力的言语和面部表情，b y m e 的输入是关于一场 模拟足球比赛的当时状念和最近动作的一系列相关事件描述，每一个事件描述都 被预赋予个相关值，事实上b y m e 的动画和语音自动生成是基于比赛分析和事 d 笫 辛绪论 件相关性计算都己完成的假定的，这大大减少了它的处理复杂性。b y m e 的主要 子系统包括情感生成、情感行为生成、文本和语音标记生成、表情标记生成等， 它基于一组情感结构生成规则、评球员角色的个性、组合规则等。b y m e 的一个 重要特点是它大量使用了有关语音合成、面部表情和自然语言语义语用处理和生 成等的各种系统标准。此外还有m a i o c c h i 关于“自动演员”的工作刚。 ( 5 ) 交互式故事系统 一般交互式故事或游戏系统有故事图和模拟世界两种类型，前者的交互性太 差，而后者的行为时间相关性太差，难于成为故事。面向兼顾交互性和情节控制 的目标 2 2 】，描述了一个支持交互式情节的动态产生、管理和冲突解决的计算框架， 它让用户充当故事的主角束确定当前的行为，同时根掘角色的说明、关系、目标 等来控制角色的行为。该框架的核心模块是一个情节管理器，它的输入是一系列 初始情节条件，输出是角色动作序列，该系统目前己在网上发布运行。 ( 6 ) 自然语言故事到计算机动画的翻译 m u l t r a n f 2 3 】是一个从自然语占( 同文) 写的故事到计算机动画的翻洋器， 其主要步骤包括：从故事篇章中推导出脚本、角色动作生成、动画环境构造和虚 拟摄像机定位。m u l t r a n 的特点在于：中间表达由事件和事件问的约束组成； 能够生成一个动画脚本，它是时间估算的一个最优解：调度执行的过程中角色可 以估算自己动作的时间。m u l t r a n 的研制者期望他们的工作可以支持自然语言 处理中的对话理解和篇章的二义性排除。 ( 7 ) 交互式故事图板生成 故事图扳( s t o 啪o a r d ) 是指电影、动画片、电视节目或商业广告等的情节串连 图板，主要用于设计镜头效果和指导拍摄。现行的故事例板生成系统一般都是变 互式的，由用户利用系统所提供的功能操作和库逐个图进行画面设计，每个图可 以附加标题和脚本文字说明。以s t o r y b o a r dq u i c k l 2 5 2 6 1 为例，它是为导演、作家、 制片人、摄影师、电视录像制作人所设计的用于前期可视化的实用软件，在制作 北京t 业人学f 。学坝f j 掌位论义 每幅画面时用户可进行的操作主要包括：从系统所提供的库中调入角色、选择角 色的动作和方向、放大或缩小角色、添加背景图或图像、从系统所提供的库中调 入道具和各种图示符号、添加文字说明等等；s t o r y b o a r dq u i c k 的目标是简单易 学，便于用户对有关镜头的想法进行快速可视化和交流。还有的交7 ：式敝lc 蚓板 生成软件可以为画面附加声音效果、把画面输出到视频设备等 2 7 2 8 1 。 1 ，2 2 动画自动生成及布局规划研究现状 ( 1 ) 动画自动生成研究现状 运用全过程计算机辅助动画片自动生成技术，我们计划参考中科院陆汝钤院 士领导的研究小组的研究成果2 3 研制一个动画自动生成系统。它完成从受限自然 语言故事文本到最终动面生成的过程，其中每步都可以看成是动画语音+ 的逐步 细化。总的来说，我们可以将该流程分为如下几步： 对受限自然语言形式的儿章故事进行自然语言理解，并将它转换成我们 规定的脚本语言格式g f ； 进行故事理解和故事分析，并将分析的结果加入g f ； 进行情节规划： 进行场景规划； 进行布局规划； 摄像规划： 光色规划： 定量计算，包括；路径计算、摄像计算、光色计算、动作计算； 生成动画。 本课题所傲的工作主要是流程中的第五步：布局规划。 ( 2 ) 布局规划研究现状 布局规划是动画自动生成系统的重要组成部分，是一个在现实世界中常见 的问题，例如家居句局【2 9 】，电路设计【3 0 】，办公室布局叫，工厂布局，厨房布局 j 2 。 弟l 蕈鲔论 p f e t e r k o m 在 2 9 】中定义了空| b j 靠局规划问题，描述如下： 已知： ( 1 ) 很多物体，例如家具 ( 2 ) 一个限制区域，例如一个房间 ( 3 ) 约束限制 求： 如何在满足约束限制的条件下，将物体在该限制区域中摆放好。一般情况下， 物体和该限制区域都是长方形或复杂多边形。 c b a y c a n 【3 3 】提出将空削布局规划形式化地描述为一个析取约束的满足问题， 一些变量，一些原子约束，一些析取约束。变量可以是直线，维数和摆放物的朝 向，原子约束是在这些变量上的代数等式和不等式，一个析取约束是一个布尔值 的原子约束的组合，析取约束定义了空问的设置，析取约束来自于问题需求，特 殊的接触，距离和其它的物体问的关系。 由于布局规划问题十分复杂，所以人们运用很多技术，例如整数规划和基于 规则的技术，尝试解决布局规划问题。但是这些技术在解决布局规划时，都会 产生新的组合爆炸问题。因此，h o n d a 等在【3 4 中引入约束程序设计技术，希望 能简化布局规划需要的形式表达和计算量，并实现了一个二维的空间布局规划 系统。 1 3 本课题的研究内容 本课题研究如何根据动画自动生成系统的实际需要，基于约束求解机制， 运用本实验室研制的b p u c l p ，设计和实现出一个布局规划系统。在动画自动 生成系统中，布局规划系统具有独立的知识库和通用推理机，能根据故事中的 各种情节和场景的描述，结合知识库中的各种常识和约束，运用通用推理机对 场景中出现的人物和物体规划合理的初始位置。 本文介绍了基于约束求解机制的布局规划系统的总体设计思想和各模块的 基本实现原理，以及约束求解系统b p u c l p 的基本功能和实现原理。重点研究 了如何基于约束求解机制，用b p u c l p 程序表示加局规划系统知u l 库一0 j = u 北京t 业人学t 学坝1 ：学位论义 识，以及如何构建布局规划系统的通用推理机，借助这些知识求解布局规划问 题。并且，本文将基于约束求解机制的布局规划系统与本课题组提出的其他布 局规划系统进行比较。同时，本文还在上述理论基础上提出了动画自动生成系 统中的布局规划系统的开放性框架，并利用此框架实现了一个布局规划原型系 统，表明该框架是一个具有可扩展性的开放性系统平台。 1 4 本文的组织方式 本文是按如下方式组织的： 第一章“绪论”部分首先分析课题的研究背景和意义，然后总结动画自动 生成系统中布局规划的研究现状，最后介绍本课题的研究内容及论文的安排。 第二章“动面自动生成系统”部分概述动画自动生成系统的理论和技术框 架： 第三章“b p u c l p 系统”部分首先介绍与本文相关的c l p 技术及其约束 求解算法，然后介绍本实验室研制的b p u c l p 系统 第四章“布局规划的研究”部分首先概述动画自动生成中的布局规划，然 后介绍本课题组提出的两种布局规划的研究思路，最后介绍基于b p u ，c l p 的布 局规划。包括与布局规划系统相关的产生式系统的基本工作原理，布局规划l 、口j 题的解决思路概述，布局规划系统的知识库和通用推理机； 第五章“御局规划系统的设计及实现”部分首先从整体上概述布局规划系 统的设计思路，然后介绍布局规划系统每个模块的地位及作用，重点介绍知识 库模块，最后进行相关实验，给出实验结果数据和结论。 最后一章“结论”部分对全文工作进行总结，并对今后的工作进行展望。 最后，给出了参考文献及致谢。 1 5 本章小结 本章是论文的“绪论”部分，首先介绍了动画自动生成系统中旬局规划的 研究意义和课题背景，然后分析了动画自动生成的研究现状和动画自动生成小 布局规划的研究现状，最后介绍了本课题的研究内容等。 第2 章动画自动生成系统 2 1 计算机动画自动生成概述 中国科学院数学研究所计算机科学研究室在陆汝钤院士的带领下，自1 9 9 2 年至1 9 9 5 年完成了一项中科院院长特别基金资助课题：全过程计算机辅助动 画制作。其目的是将人工智能技术用于计算机动画，从而提高动画制作的自动 化程度和智能性。 这个课题所奉行的是一条动画片生产全过程自动化的技术路线。它的目标 是只要有了一个适当的故事，以受限自然语言的形式把它输入计算机里，从此 时开始，直到最终生成动画，每一步都是在计算机辅助下完成的。粗略说来， 这些步骤【2 是： 第一步：对故事文本作自然语言理解。 第二步：故事情节理解。 第三步：把故事改编为分镜头剧本。 第四步：根据分镜头剧本作动画设计，包括角色，背景，动作，道具等设 计，其中体现了时间、空间规划。 第五步：根据上述设计和规划，利用事先构造好的动画素材库和声音库， 生成完整的动画。 陆汝钤院士带领的早期动画小组沿着这条技术路线研制了软件系统天 鹅。虽然该系统初步实现了这条路线，但是“有些局部模块的实现方法至今 不很理想，其中有相当一部分是准备重新实现的新方案”f2 1 。在陆汝钤院士的 指导下，我们j 下在重新实现这条路线。重新实现不仅仅是再次验证理论的过程， 而是采用新技术，对原有方法进行局部修f ，使得动画自动生成逐步成熟与完 善。 9 2 动画自动生成系统的流程幢 在动画自动生成系统中，系统对自然语言输入的中文故事脚本，先通过故 事理解中的分词系统做基本文本处理，然后用浅方法进行故事初步分析，获得 g f l 。然后，系统利用深方法进行故事理解得到故事的梗概和一些备用信息， 产生g f 2 。将g f 2 作为情节规划的输入，通过情节展开，生成有原子动作组成 的情节脚本。在场景规划中对情节脚本进行处理，重新划分场景，产生d p r s 的基本场景信息，并填充必要的附加成分。布局规划，摄像机规划通过已有的 d p r s 进行各自操作，并将结果重新填入d p r s ，获得a d l 。根据a d l ，系统 进一步得到c a l 。到此为止，系统已经可以对摄像机进行驱动，最后就是利用 c a l 完成动l 画片的拍摄。如图2 1 所示。 ( 1 ) 故事理解 故事理解模块研究如何将输入的受限的中文儿章故事转换成动画自动生成 系统可以处理的信息。我们采用中科院分词系统对受限的自然语言的中文儿童故 事进行初步词法分析，它基本上可以句子中的词语以词性为标准，划分为名词、 形容词、动词等。然后，我们将分词结果填入g f l 中，然后在g f l 的基础之上进 一步分析，将语义分析后的结果以g f 2 格式描述。 ( 2 ) 情节规划 情节规划模块研究如何将故事中的抽象情节转换成具体情节。我们采用两次 情节规划的方式，每次情节规划算法是一样的，但是展开的程度不相同。第一次 情节规划展开的程度较粗略，第二次情节展开的程度是较为详细的，它的结果是 最终的原子事件流。第一次情节规划的输入是经过故事理解后的g f 语言，输出 是经过一次细化的情节流。第二次情节规划在场戏分割的基础上进行细化，其结 果是最终的原子事件。 ( 3 ) 场景规划 0 场景规划模块研究如何把故事中的信息按场景提取出来并分类排列。场景 规划首先给每个片断所描述的基本场景分类，编制场景队列。然后为每个场景 填充附加成分信息，即给每个已经分类的片段场景加上其特有的信息。 蚓2 1 动画臼动生成系统流鞋幽 f i g u r e2 1 t h cp r o c e d u r eo f a u t o m a t i co e n e r a t i o no f c o m p u t e ra n i m a t i o nc h a r t ( 4 ) 布局规划 布局规划模块研究如何给出一个场景中物品和人物的初始摆放情况。布局 规划作为联系定性层和定量层的一座桥梁，发挥着非常关键的作用。它由通过 故事理解、情节分析、场景分析后得到的d p r s 序列中提取场景和物体的定性 信息，然后联系场景库、物体知识库，经过布局规划算法得到定量的物体布局 位置，最后将布局结果输出。 ( 5 ) 摄像机规划 摄像机规划模块的主要任务是对场景规划得到的结果迸行分析，与知识库 中指定模块相匹配，一旦匹配成功，则载入相应的摄像原语框架，并进行细节 匹配以填充该框架。当摄像原语被添加到从上至下的生成文本后，即得到了对 应的a d l 文件。 摄像机规划模块的输出直接与上级的情节规划，场景规划，布局舰划的结 果相关联，该结果中出现的一些标签是本模块唯一的输入信息。针对这些输入 信息，摄像机规划匹配数据库中该标签对应的摄像原语解释，最后输出a d l 语 2 3 本章小结 本章是论文的“动画自动生成系统”部分，首先概述了动画自动生成系统， 然后分故事理解模块，情节规划模块，场景规划模块，布局规划模块和摄像机 规划模块介绍了动画自动生成系统的工作流程。 第3 章b p u c l p 系统 b p u c l p 系统【 s j 是北京工业大学计算机学院多媒体与智能软件北京市重点 实验室刘椿年教授领导的研究小组研制的一个多重论域的约束逻辑程序设计系 统。 我们的布局规划系统中运用了约束求解系统b p u c l p ，所以在本节中，我们 将简要介绍b p u - c i j p 系统。我们先介绍b p u c l p 系统的理论基础c l p ，再介绍 b p u c l p 系统。 3 1c l p 技术啪 31 1c l p 简介 约束逻辑程序设计( c o n s t r a i m1 0 西cp r o 乒a m m i n g ，简称c l p ) 是将逻辑程序设 计( 1 0 9 i c p m g r a m m i n g ，简称l p ) 和人工智能领域中的约束满足问题结合起来的研 究领域。 约束是一个覆盖广泛的概念。直观地，约束可以被看作在可能性空间上的限 制。数学约束( 如x + y z ) 是几个未知量( 变量x ，y ，z ) 之间的可精确说明的关系， 从而限制变量可能取值的范围，由此表达了变量的( 部分) 信息。约束具有几个独 特的性质： ( 1 ) 约束可能只说明部分信息( 变量的取值范围而非具体的值) ： f 2 ) 约束可以步进地给出( 最终的结果与约束的次序无关，完全取决于它们的 合取) ： ( 3 ) 约束之间常常不是相互独立的( 有的约束被其他约束所蕴含) ； ( 4 ) 约束是无方向的( x ，y ，z 三个变量之间的一个约束x + y z 可以分别导 出对x ，y ，z 的取值范围的约束) ： ( 5 ) 约束是说明性的( 只况明必需成立的关系而不是描述使该关系成立所需 的计算过程) 。 约束满足问题( c o n s t r 新n ts “s f a c t i o np r o b 】e m s ，简称c s p ) 的一般表达是：给定 变量的一个有穷集i = x 1 x 2 ，x 。) 和这些变量之间的一组约束s 。c s p 的个解 变量的一个有穷集i = x 】，x 2 ，x 。 和这些变量之间的一组约束s 。c s p 的一个解 1 1 北京t 业大学丁学硕卜学位论文 是i 中各个变量的一种取值，使s 中所有的约束得到满足。c s p 的任务是判定s 是 否有解( 即s 是否可满足) ，并在有解的情况下求出一个解，或所有的解，或使某 目标函数f ( x i ，x 2 ，x 。) 达到极值的最优解。 早在1 9 7 8 年，j j a f f 打和j 一ll a s s e z 就在文献中提出了c l p 方案并初步 给出了它的形式语义框架。经过1 0 年的研究积累，直到1 9 8 8 年，j j a f f a t 等人 在文献中第一次给出完整的c l p 语义。c l p 语义是逻辑程序设计语义的推广。 c l p 的关键思想是：腊赶麒叼磁厨等式约荐i 宅簪矗既然如此，将归结法则 换成另一个论域上的约束求解就立即得到一个约束逻辑程序设计语占。除了约 束求解，这些语言的操作行为均与逻辑程序设计一致。这样，在保持l p 严密 理论基础和解决问题能力的同时，c l p 丌创了新的程序设计风格，增强了l p 解决问题的能力，特别适合于各种优化问题的建模和求解。c l p 中约束求解的 方法依赖于具体的约束论域，但其基本思想是通过对解空间的不断压缩来进行 问题求解。从l p 到c l p 这一步推广极大地扩展了基于逻辑语占的应用范围， 为九十年代在某种意义上处于困境的逻辑程序设计打开了一片新天地。 1 9 9 6 年1 2 月，a c m 将c l p 定为今后1 9 个计算机重点研究方向之一。 c l p 方案依赖于被称为约束论域的参数c ，c l p ( c ) 实际上是一族语言，给 定一个c 就得到一个具体的c l p ( o 语言。 一个约束论域c 包含以下成分： 瓯即n m 地三常数函数i 胃词符号集，包括特殊二元谓词= ； 在三上可以按通常方式构造珊口一阶二公或 二霉鲶黾一组闭l 孓公式：三中各符号的一个解释称为一个占筹苟： 约荣集厶上的成员称为爹9 荣j 是一个予定义的一阶二公式。上的性质有： 上的成员( 约束) 作为二公式，其中出现的常数，函数和谓嘲均有 本意解释。 三需包括从= 构造的所有原子公式，永远可满足公式打w p 和永远不可 满足公式向b p ；形如原子公式的约束( 当然是从预定义谓词构造的) 秣炙初等约束。 4 第3 章b p u c l p 系统 上在变量重新命名，存在量化和合取操作下封闭。 劳黝砑d ：对约束进行本意解释的“+ 个二结构；特别地，d 需要将= 解释为恒等。 约荣理蕾n 描述约束的逻辑语义的一个二理论；特别地，r 需包括通 常描述= 的公理。 约嘉戎织器5 台如：三斗口d 口，u n 加口，n 。勋如不受变量重新命名的影 注意，d ，l 肋如不是相互独立的，我们要求d ，r ，勋加三j 手_ 考敢即： | d 是r 的一个模型， 对每一个约束c 工， 若曲f v ( c ) = 扣b e ，则z - 1 j c ( j c 表示c 的存在闭包) ； 若。勤( c ) = 知如p ，则丁b3 c 。 一致性要求表明，约束求解器的能力最多达到约束理论丁的能力。允许约 束求解器的能力小于r ，即允许勋f v 返回“n 砌o w h ，这样的约束求解器称为刁f 芜咨的。 在上面的c 的定义中，已经给出了约束的三种语义：删v 给出了操作语义， d 给出了代数语义，丁给出了逻辑语义。关于c l p 的语义( 操作语义、逻辑语 义、代数语义、定点语义) 可以参考文献和文献。 一个c l p 程序是一个规则的有穷集。一条规则形如：h b ，其中h 是原了公 式，称为头部：b 是原子公式或初等约束的( 可能为空的) 有穷序列，称为体。 原子公式形如p ( t 】，t 2 ，t 。) ，其中p 为用户定义的谓词，t i 为项。初等约束的定义已经 包含在上面的约束领域的定义中了。原子公式或初等约束统称为文字( 1 i t e r a l ) 。 用户定义的谓词p 在c l p 程序p 中的定义d e f ( p ) 是p 中头部形如p ( s 1 ，s 2 ，s 。) 的规则集。为了绕过变量重新命名的问题，我们约定：每当d e f ( p ) 被调用时， 它均返回使用互不相同新变量的变体。 3 1 2c l p 的约束求解算法 c l p 所研究的约束论域有：h e r b r a l l d 项，布尔论域，有穷论域，实数论域， 北京下业大学t 学坝十学位论文 表，有穷集合等。h e r b r 姐d 项即是传统的i l p 所研究的论域。表和有穷集合等 论域目前研究的还不多，应用范围也比较小。下面主要介绍布尔论域，有穷论 域和实数论域的约束求解算法。 ( 1 ) 布尔论域 布尔论域的约束可以看成有穷论域的特例，只含两个值o 和1 ( 如c l p ( b n ) 和c l p ( f d ) ) ，也可以为之设计专用的