基于視頻的虛擬人群運動仿真方法

劉 艷，張 靜，呂 敏

(天津大學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．