基于视频的虚拟人群运动仿真方法

刘 艳，张 静，吕 敏

(天津大学a．计算机科学与技术学院;b．软件学院，天津300072)

1 概述

虚拟人群仿真是计算机图形学中一个重要的研究课题。虚拟人群仿真在多个领域应用广泛，如电影制作、游戏制作以及虚拟城市等。近些年来，开始有越来越多的人致力于虚拟人群运动仿真方法的研究。目前，如何提高人群仿真效果的真实性已经成为虚拟人群运动仿真方法研究的热点和难点。

在研究过程中，根据不同的研究方式，将研究方法主要分为基于模型的方法和基于数据驱动的方法。基于模型的方法是使每个代理人通过一些预定义的简单规则和情形生成最终的动作［1］。文献［2］提出了一种基于草图(sketch-based)的虚拟人群方法。用户通过一个交互界面，输入几条路径，通过输入的路径预估计人群的相关参数进行模拟。文献［3］提出了一种基于网格的方法，群组作为一个整体进行网格编辑，而代理人之间保持关系和原始路径尽可能不发生大的变化。文献［4］提出了一种基于动机理论［5］的人群行为模型，将心理变量纳入人群运动建模中。为了获得最终期望的动画效果，很多规则参数需要进行调整，比如初始位置、个体之间的距离及关系、移动速度等。基于模型的方法可以快速生成大规模的人群动画效果，但不足之处在于现实中人的行为不能完全被映射到代理人身上，且在调节参数的过程中会产生一些不可估计的后果。

近年来，基于数据驱动的方法被频繁应用于人群动画生成并且取得了很好的效果，一定程度上弥补了基于模型方法的不足。基于数据驱动的方法通过运动捕获或追踪视频获得数据信息驱动人的行为。文献［6］在多数据库时空路径样本构建的应用机器学习的代理人行走模型，文献［7］从真实世界中学习行人动态仿真以及文献［8］提出的基于人群真实数据的人群评价方法都是应用基于数据驱动的方法。文献［9］应用数据驱动的方法模拟真实人群展示人的行为，从空中架设摄像机拍摄行人的视频，对行人的行为进行标记，从人群中提取出每个人的二维移动路径，从而保证了数据来源于视频中真实的人群。文献［10-11］同样应用数据驱动的方法，根据预先捕获的实例对行人进行仿真。这种方法的特点是数据来源于视频，仿真效果更加真实。虽然基于数据驱动的方法在人群仿真效果上得到了一定提高，但在现实中，拍摄超大规模人群的视频具有很大的难度，并且视频中的人群如果太过密集，将会很难对其进行处理，增大采集个体数据信息的难度。

针对以上问题，本文引入故事板的概念，将数据驱动的方法与图像学的纹理合成算法相结合，将小规模人群视频中的人群信息存储于样本故事板中，再利用纹理合成算法生成大规模故事板，最终通过大规模故事板人群数据信息驱动生成超大规模人群动画。

2 基于视频关键帧故事板的形成

2．1 技术路线

本文提出的虚拟人群运动仿真方法主要分为3个部分:

(1)将位置、站位方向、状态以及动作等人群信息提取出来集成到样本故事板中;

(2)将样本故事板作为纹理合成的输入数据合成超大规模的故事板;

(3)应用数据驱动的方法，结合从大规模故事板中提取的人群信息，生成最终的动画效果。

该方法的整个流程如图1所示。

图1 基于视频的虚拟人群运动仿真方法流程

2．2 故事板介绍

故事板是图形组织者通过插图或者照片的形式以预先可视化为目的展示的一系列运动图像、动画效果、动作图片和交互媒体。故事板在影视制作、媒体交互以及软件制作等领域应用广泛。故事板是一种有效的低保真原型工具，提供一个可视化的布局事件，利用故事板的特点，将视频关键中的个体信息存储于故事板中，达到图形化的效果，为群体虚拟仿真提供数据。

2．3 关键帧中的信息提取

现实中的人具有差异性，性别、身高、行为、动作、肤色、年龄、心理状态等因素的组合使得每个个体都不一样，个体所构成的群体又使得个体具有群体的共性。对于一个超大规模人群，定义体现小群体共性的年龄、性别、肤色和状态等集合对人群进行分组，集合表示如下:

根据年龄可以将人群分为老年人、青年人、小孩，其中，Oa代表老年人;Ya代表青年人;Ca代表小孩。

根据性别可以将人群分为男人和女人，M代表男人，F代表女人。

根据肤色可以将人群分为白种人、黄种人和黑种人，其中，Wc代表白种人;Yc代表黄种人;Bc代表黑种人。

根据状态可以将人群分为着急群体和闲散群体，其中，Ws代表着急群体;Fs代表闲散群体。

本文依据个体的状态对人群进行分组，对同一组别的个体赋予相同的三维模型和动作信息。关键帧的处理过程、个体的位置信息、站位方向、状态以及动作信息通过手动方式进行标记。通过标记过的关键帧手动绘制小规模样本故事板，实验过程中自动对样本故事板的信息以数学表达方式提取到文本中。

2．4 基于故事板的人群描述方法

2．4．1 故事板定义

故事板作为一种视频总结技术，成为了重要的辅助工具，被广泛应用于网络视频浏览与搜索领域。为了更好地仿真人群行为，本文设计一个简单易用的故事板。

去除背景，并且对每个人物用着色点与箭头进行标记，手动地将人物信息集成到故事板中。整个过程如图2所示。

图2 故事板绘制过程

首先，定义一个集合来表示人群运动的状态，包括位置、方向和当前状态，表示如下:

其中，P表示人物在关键帧中的位置;D代表代理人的当前方向。例如，在地铁站或十字路口，人群会向固定方向行进。人群的初始方向应当最先给出，方向作为初始信息获取之后，将代理人置于场景中。Cs是动态信息，代表个体的当前状态。本文设计的故事板，可以简单直接地描述上述人群运动信息。

在故事板中，每个代理人用4个像素表示，3个像素位于同一行，一个像素在另一行表示方向。用一个T型表示和描述一个任务。在图2中，状态、方向和动作信息包含在帧中，即图2(a)。图2(b)用圆点和箭头来表示所有信息。图2(c)为最终的小规模故事板，人群的信息集成于故事板，图2(d)中T形中间标记0的地方表示之前提到的人物状态。标记1的部分用来表示不同的个体。标记2表示每个人物的方向。其次，不同颜色代表不同信息。对于标记0，当人物漫步时，用橙色着色，当人物遇到紧急情况或匆忙行走时，用红色着色。对于标记2，绿色代表代理人步行，黄色表示跑步，粉色代表交谈，红色代表跳跃。对于标记1，颜色用来根据行为共性进行分组。用户可以自行定义颜色的含义。这些对应于状态集。P是标记0对应的坐标位置，D是标记2表示的方向，Cs表示标记0的颜色。例如，在图2(b)中，绿色箭头表示它的方向为下方且动作为行走。红色和橙色的着色点为当前状态。图2(d)中的方向为向下，而图2(e)中的方向为右下。故事板的T型定义如表1所示。

表1 故事板T型定义

2．4．2 方向定义

在判断每个代理人的方向时，对于每一个代理人，定义一个3×3像素的方格，外层3个方格与中心方格所组成的T形，决定了代理人的方向，共有8个方向。将外层8个像素从左上角开始顺时针进行编号，分别为 1，2，4，8，16，32，64，128，如图 3 所示。这样，在外层8个像素中任意选取任意多个像素，每种组合的编号之和都是唯一的，如果像素方向合法，对像素进行一次扫描后便可得到代理人的方向。例如图3(b)所示，其着色像素编号为8，16，64，其和为8+16+64=88，说明代理人方向为Down。

图3 对像素进行编号和Down方向的像素图

方向编码唯一性证明如下。

外层8个像素的编号分别对应着二进制编码串:

001-00000001，002-00000010，004-00000100，

008-00001000，016-00010000，032-00100000，

064-01000000，128-10000000

每个像素不会重复着色，且各像素的二进制编码中非零位互不相同，因此，任意多个不同像素编码之和在二进制编码中不会产生进位，其和唯一确定一种着色组合。所以方向的标识组合是唯一的。

8个合法方向的像素和如下:

Top=26，Left=74，Down=88，Right=82，

Top Left=37，Top Right=133，Left Down=161，

Right Down=164

方向二进制编码对应表如图4所示。其中，Y所示的为扫描到的非白色像素点对应的编码值;Sum为代表某个方向的所有值的和。

图4 方向编码表

3 大规模故事板的生成

3．1 纹理合成算法

本文应用文献［12］算法，该算法简单，而且得到的接缝误差最小，视觉上也更加平滑。完整的算法描述如下:

(1)按照扫描线顺序合成图像。

(2)对于每一个位置，搜索输入的纹理图的块集合，查找符合匹配条件的纹理块，并随机选取一块Bi(i=0，1，…)。

(3)把新选择的块复制输出图像后再在输入样图中查找Bi+1，当把Bi+1放入输出图时Bi+1与前一块已合成的Bi要有一定的边界重叠，然后在重叠区域找出一条误差最小的路径作为Bi+1边缘，把Bi+1复制到输出图中，返回步骤(2)继续执行，直到获得合成纹理图。

本文采用对输入样本进行逐个块复制的合成方法，通过这种合成方法创建的片形状不规则，使人群仿真效果显得更自然。

3．2 纹理合成过程

结合具体实例对纹理合成大规模人群信息图，进而完成人群静态站位的整个过程进行说明。在本次实验中，主要场景是模拟地铁站的甬道，地铁站的人群规模为500人左右。

所用的视频如图5所示，由于所用视频的要求为顶视图，且人群规律性尽量明显，这样的视频很难从网络或者现实中取得，自行拍摄也费时费力，本文中应用的视频是由文献［13］中使用的自行拍摄的一组公开视频。其中包括群体聊天、演讲、排队等车等诸多人群模式，非常符合本文实验对于视频的要求。

图5为第1帧经过中间的处理过程，最终得到小规模故事板过程。

图5 小规模故事板处理过程

图6表示了通过输入甬道模型的顶视图的目标图像和故事板(图6(a)中打圈的部分)，得到最终的大规模故事板至最终将代理人排布到场景中成功站位。

图6 大规模代理人模型生成过程

4 基于视频数据驱动的人群动画

4．1 数据驱动

近年来，数据驱动方法已经成为模拟复杂人群行为的重要方法。数据驱动的方法［14］数据信息来源于2种途径。一种是运动捕获数据，另一种是追踪视频。通过捕获或者追踪到的数据信息驱动人的行为。

同时，通过真实的视频进行观察追踪个体信息应用越来越广泛，这种方法能够真实再现视频中的多种场景，如谈话、听演讲、看演唱会等人的状态，可以具体到肢体动作。其过程描述如下，追踪视频中的每个个体，将每个个体的数据存储在相应文档或数据库中，在虚拟仿真过程中，通过查找的方式获得每个代理人的数据。

通过衡量这2种数据驱动方法的利弊，选择基于视频的数据驱动方法。

4．2 故事板数据驱动人群

本文数据驱动的方法基于视频追踪并结合手动提取一小段时间路径向量信息。主要思想是从原始视频的关键帧中半自动提取人物位置信息组成连续的路径向量信息，生成代理人根据得到的这些路径向量序列生成各自的运动路径。生成路径的方式考虑到2种，一种是严格按照原始人物的路径向量序列中元素的顺序生成新路径，另一种是每类代理人在原始人物的路径向量序列中随机挑选某一位置的元素迭代生成新路径。2种方式各有优缺点，但考虑到原始人物路径向量序列中各元素的差异性可能过大，并且随机挑选元素可能会造成新代理人不能很好体现出原始人物特性的因素，因此选择前者生成代理人的路径。

代理人路径计算过程简述如下:视频以每一秒作为时间间隔设置时间点，每个时间点位置截取相应的关键帧，从关键帧中手动标注个体的位置信息，自动提取位置信息。通过相邻2个关键帧中获得的位置信息计算出时间段内个体的运动路径向量，利用此向量与生成代理人的起点位置信息计算得出代理人的终点位置。

例如，视频中第i个人的路径向量信息可以表示为:

其中，向量Pij的信息通过如下方式获得:视频中个体i在第j-1秒关键帧中的位置为(m，n)，在j秒关键帧中的位置为(p，q)。那么个体i在这一秒内运动路径的向量表示为:

通过上述计算公式，可以获得视频中所有个体的路径向量信息，组成一系列向量集合，存储在相应格式的文档中。代理人进行路径规划的时候，只需要知道他当前的位置以及下一秒所对应的向量信息，通过下述方法获得终点位置。例如代理人A是由视频中的个体i获得的，假设当前代理人A在第j-1秒的初始位置为 Pstartj=(a，b)，终点位置设为Pendj=(c，d)，通过查找文档找到其相应的向量Pij，通过方程式解(c-a，d-b)=Pij，计算得到c和d的值，从而获得终点位置。代理人获取到终点位置，在第j秒时间段内将一直朝向求得的终点位置前进，此时代理人的面部方向可能一直在变化，但一直是朝向计算得到的终点。

4．3 碰撞躲避

从初始点走到终点的过程中，个体与个体之间会产生碰撞，为了使人群中的每个代理人能够顺利到达各自终点，需要对碰撞进行检测并采取相应避免的措施。

本文的碰撞检测算法基于行为心理学［15］。人类会有一个自身认可的安全距离，在安全距离的范围内会检查他人或障碍物是否存在与自己发生碰撞的可能。根据安全距离概念，结合包围盒的思想，本文实验中给定代理人一个以最小安全距离为半径的圆柱体作为包围盒，当包围盒发生相交时，也就是代理人与代理人发生碰撞时，代理人会瞬时调整自己的速度方向，随机选择在凝视角度范围内的一个角度，改变运动速度及方向。

代理人i的碰撞躲避算法流程如图7所示。

图7 碰撞躲避算法流程

算法并不复杂，但在实际应用中效果甚佳。在走廊场景中生成大规模的人群，他们在穿越走廊的运动仿真中可以轻易避开即将发生的碰撞，没有任何因卡死而导致代理人停止运动的情况发生。

5 实验及结果分析

本次实验在地铁通道场景中进行，主要对视频中的地铁通道场景中的人群进行虚拟运动仿真。

将小规模故事板通过纹理合成方式合成大规模故事板，实现了以较小规模的视频完成大规模虚拟人群运动仿真的目标，并且实验中生成的虚拟人群运动效果与视频中人群的运动效果具有较高的一致性。视频帧序列如图8所示，实验效果如图9～图11所示。

图8 视频帧序列

图9 人群运动近景图

图10 100人运动效果

图11 200人运动效果

同时，还对不同规模的人群做了相关实验，采集到的数据如表2所示。表2中第1列为单次实验人群规模，第2列～第4列分别表示单次实验中代理人静态站位消耗时间、代理人从初始点到达目的地消耗时间以及单次实验消耗总时间。

表2 不同规模代理人的数据采集信息

随着规模成倍数的扩大，站位时间明显不是成倍数增长的。分析原因，由于人在静态站位到场景中时，为了使得站位更自然，给每个代理人加了一个静态站位的动作，每个人站在原地都有自己的动作，有的左顾右盼，有的抓耳挠腮，有的左晃右晃，当人群规模不断增大时，需要处理越来越多的静态站位动作，造成了时间的不成倍数增长。从这个过程可以看出，随着人群密度的增长，时间增长速度随之增加，其中产生的碰撞躲避过程也随之增多，影响实验效率。

6 结束语

本文提出一种基于数据驱动的、纹理合成故事板的虚拟人群运动仿真方法。以故事板来收集视频中的人群信息，通过纹理合成算法生成超大规模人群故事板，并在三维场景中提取大规模人群故事板数据信息，指导人群运动，生成虚拟人群动画。实验结果证明，大规模虚拟人群中的个体行为与视频中对应的个体行为相似，提高了大规模虚拟人群动画生成的效率。下一步将研究大规模人群渲染加速和实现实时渲染，并考虑环境问题对人群运动产生的影响，提高虚拟人群运动仿真的真实性。

［1］ Reynolds C W．Flocks，Herds and Schools:A Distributed Behavioral Model［C］//Proceedings of the 14th Annual Conference on ComputerGraphics and Interactive Techniques．New York，USA:ACM Press，1987:25-34．

［2］ Oshita M，Ogiwara Y．Sketch-based Interface for Crowd Animation［C］//Proceedings of the 10th International Symposium on SmartGraphics．Salamanca，Spain:Springer，2009:253-262．

［3］ Kwon T，Lee K H，Lee J，et al．Group Motion Editing［J］．ACM Transactions on Graphics，2008，27(3)．

［4］ 黄 鹏，刘 箴．一种基于动机理论的人群行为模型［J］．计算机工程，2013，39(12):290-293．

［5］ 刘 箴，潘志庚．虚拟人动机驱动的自主情绪模型研究［J］．中国图象图形学报，2009，14(5):773-781．

［6］ Torrens P，Li X，Griffin W A．Building Agent-based Walking Models by Machine-learning on Diverse Databases ofSpace-time Trajectory Samples［J］．Transactions in GIS，2011，15(S1):67-94．

［7］ Scovanner P， Tappen M F． Learning Pedestrian Dynamics from the Real World［C］//Proceedings of the 12th International Conference on Computer Vision．Washington D．C．，USA:IEEE Press，2009:381-388．

［8］ Lerner A，FitusiE，Chrysanthou Y，etal．Fitting Behaviors to Pedestrian Simulations［C］//Proceedings of Symposium on Computer Animation．New Orleans，USA:Institute of Electrical and Electronics Engineers Inc．，2009:199-208．

［9］ Lee K H，Choi M G，Hong Q，et al．Group Behavior from Video:A Data-driven Approach to Crowd Simulation［C］//Proceedings of Symposium on Computer Animation．New York，USA:ACM Press，2007:109-118．

［10］ Lerner A，Chrysanthou Y，Lischinski D．Crowds by Example［J］．Computer Graphics Forum，2007，26(3):109-118．

［11］ 王 鑫，孙守迁，侯 易，等．数据驱动的人群场景动画合成方法［J］．计算机辅助设计与图形学学报，2009，21(2):250-256．

［12］ Efros A A，Leung T K．Texture Synthesis by Nonparametric Sampling［C］//Proceedings of International Conference on Computer Vision．Washington D．C．，USA:IEEE Press，1999:1033-1038．

［13］ Gardner G Y．VisualSimulation ofClouds［C］//Proceedings of the 12th Annual Conference on Computer Graphics and Interactive Techniques．San Francisco，USA:ACM Press，1985:297-304．

［14］ Metoyer R A，Hodgins J K．Reactive Pedestrian Path Following from Examples［J］．The Visual Computer，2004，20(10):635-649．

［15］ Cutting J E，Vishton P M，Braren P A．How We Avoid Collisions with Stationary and Moving Objects［J］．Psychological Review，1995，102(4):627-651．