基于視頻的虛擬人群運(yùn)動仿真方法

劉 艷，張 靜，呂 敏

(天津大學(xué)a．計算機(jī)科學(xué)與技術(shù)學(xué)院;b．軟件學(xué)院，天津300072)

1 概述

虛擬人群仿真是計算機(jī)圖形學(xué)中一個重要的研究課題。虛擬人群仿真在多個領(lǐng)域應(yīng)用廣泛，如電影制作、游戲制作以及虛擬城市等。近些年來，開始有越來越多的人致力于虛擬人群運(yùn)動仿真方法的研究。目前，如何提高人群仿真效果的真實性已經(jīng)成為虛擬人群運(yùn)動仿真方法研究的熱點(diǎn)和難點(diǎn)。

在研究過程中，根據(jù)不同的研究方式，將研究方法主要分為基于模型的方法和基于數(shù)據(jù)驅(qū)動的方法。基于模型的方法是使每個代理人通過一些預(yù)定義的簡單規(guī)則和情形生成最終的動作［1］。文獻(xiàn)［2］提出了一種基于草圖(sketch-based)的虛擬人群方法。用戶通過一個交互界面，輸入幾條路徑，通過輸入的路徑預(yù)估計人群的相關(guān)參數(shù)進(jìn)行模擬。文獻(xiàn)［3］提出了一種基于網(wǎng)格的方法，群組作為一個整體進(jìn)行網(wǎng)格編輯，而代理人之間保持關(guān)系和原始路徑盡可能不發(fā)生大的變化。文獻(xiàn)［4］提出了一種基于動機(jī)理論［5］的人群行為模型，將心理變量納入人群運(yùn)動建模中。為了獲得最終期望的動畫效果，很多規(guī)則參數(shù)需要進(jìn)行調(diào)整，比如初始位置、個體之間的距離及關(guān)系、移動速度等?；谀Ｐ偷姆椒梢钥焖偕纱笠?guī)模的人群動畫效果，但不足之處在于現(xiàn)實中人的行為不能完全被映射到代理人身上，且在調(diào)節(jié)參數(shù)的過程中會產(chǎn)生一些不可估計的后果。

近年來，基于數(shù)據(jù)驅(qū)動的方法被頻繁應(yīng)用于人群動畫生成并且取得了很好的效果，一定程度上彌補(bǔ)了基于模型方法的不足?；跀?shù)據(jù)驅(qū)動的方法通過運(yùn)動捕獲或追蹤視頻獲得數(shù)據(jù)信息驅(qū)動人的行為。文獻(xiàn)［6］在多數(shù)據(jù)庫時空路徑樣本構(gòu)建的應(yīng)用機(jī)器學(xué)習(xí)的代理人行走模型，文獻(xiàn)［7］從真實世界中學(xué)習(xí)行人動態(tài)仿真以及文獻(xiàn)［8］提出的基于人群真實數(shù)據(jù)的人群評價方法都是應(yīng)用基于數(shù)據(jù)驅(qū)動的方法。文獻(xiàn)［9］應(yīng)用數(shù)據(jù)驅(qū)動的方法模擬真實人群展示人的行為，從空中架設(shè)攝像機(jī)拍攝行人的視頻，對行人的行為進(jìn)行標(biāo)記，從人群中提取出每個人的二維移動路徑，從而保證了數(shù)據(jù)來源于視頻中真實的人群。文獻(xiàn)［10-11］同樣應(yīng)用數(shù)據(jù)驅(qū)動的方法，根據(jù)預(yù)先捕獲的實例對行人進(jìn)行仿真。這種方法的特點(diǎn)是數(shù)據(jù)來源于視頻，仿真效果更加真實。雖然基于數(shù)據(jù)驅(qū)動的方法在人群仿真效果上得到了一定提高，但在現(xiàn)實中，拍攝超大規(guī)模人群的視頻具有很大的難度，并且視頻中的人群如果太過密集，將會很難對其進(jìn)行處理，增大采集個體數(shù)據(jù)信息的難度。

針對以上問題，本文引入故事板的概念，將數(shù)據(jù)驅(qū)動的方法與圖像學(xué)的紋理合成算法相結(jié)合，將小規(guī)模人群視頻中的人群信息存儲于樣本故事板中，再利用紋理合成算法生成大規(guī)模故事板，最終通過大規(guī)模故事板人群數(shù)據(jù)信息驅(qū)動生成超大規(guī)模人群動畫。

2 基于視頻關(guān)鍵幀故事板的形成

2．1 技術(shù)路線

本文提出的虛擬人群運(yùn)動仿真方法主要分為3個部分:

(1)將位置、站位方向、狀態(tài)以及動作等人群信息提取出來集成到樣本故事板中;

(2)將樣本故事板作為紋理合成的輸入數(shù)據(jù)合成超大規(guī)模的故事板;

(3)應(yīng)用數(shù)據(jù)驅(qū)動的方法，結(jié)合從大規(guī)模故事板中提取的人群信息，生成最終的動畫效果。

該方法的整個流程如圖1所示。

圖1 基于視頻的虛擬人群運(yùn)動仿真方法流程

2．2 故事板介紹

故事板是圖形組織者通過插圖或者照片的形式以預(yù)先可視化為目的展示的一系列運(yùn)動圖像、動畫效果、動作圖片和交互媒體。故事板在影視制作、媒體交互以及軟件制作等領(lǐng)域應(yīng)用廣泛。故事板是一種有效的低保真原型工具，提供一個可視化的布局事件，利用故事板的特點(diǎn)，將視頻關(guān)鍵中的個體信息存儲于故事板中，達(dá)到圖形化的效果，為群體虛擬仿真提供數(shù)據(jù)。

2．3 關(guān)鍵幀中的信息提取

現(xiàn)實中的人具有差異性，性別、身高、行為、動作、膚色、年齡、心理狀態(tài)等因素的組合使得每個個體都不一樣，個體所構(gòu)成的群體又使得個體具有群體的共性。對于一個超大規(guī)模人群，定義體現(xiàn)小群體共性的年齡、性別、膚色和狀態(tài)等集合對人群進(jìn)行分組，集合表示如下:

根據(jù)年齡可以將人群分為老年人、青年人、小孩，其中，Oa代表老年人;Ya代表青年人;Ca代表小孩。

根據(jù)性別可以將人群分為男人和女人，M代表男人，F(xiàn)代表女人。

根據(jù)膚色可以將人群分為白種人、黃種人和黑種人，其中，Wc代表白種人;Yc代表黃種人;Bc代表黑種人。

根據(jù)狀態(tài)可以將人群分為著急群體和閑散群體，其中，Ws代表著急群體;Fs代表閑散群體。

本文依據(jù)個體的狀態(tài)對人群進(jìn)行分組，對同一組別的個體賦予相同的三維模型和動作信息。關(guān)鍵幀的處理過程、個體的位置信息、站位方向、狀態(tài)以及動作信息通過手動方式進(jìn)行標(biāo)記。通過標(biāo)記過的關(guān)鍵幀手動繪制小規(guī)模樣本故事板，實驗過程中自動對樣本故事板的信息以數(shù)學(xué)表達(dá)方式提取到文本中。

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

2．4．1 故事板定義

故事板作為一種視頻總結(jié)技術(shù)，成為了重要的輔助工具，被廣泛應(yīng)用于網(wǎng)絡(luò)視頻瀏覽與搜索領(lǐng)域。為了更好地仿真人群行為，本文設(shè)計一個簡單易用的故事板。

去除背景，并且對每個人物用著色點(diǎn)與箭頭進(jìn)行標(biāo)記，手動地將人物信息集成到故事板中。整個過程如圖2所示。

圖2 故事板繪制過程

首先，定義一個集合來表示人群運(yùn)動的狀態(tài)，包括位置、方向和當(dāng)前狀態(tài)，表示如下:

其中，P表示人物在關(guān)鍵幀中的位置;D代表代理人的當(dāng)前方向。例如，在地鐵站或十字路口，人群會向固定方向行進(jìn)。人群的初始方向應(yīng)當(dāng)最先給出，方向作為初始信息獲取之后，將代理人置于場景中。Cs是動態(tài)信息，代表個體的當(dāng)前狀態(tài)。本文設(shè)計的故事板，可以簡單直接地描述上述人群運(yùn)動信息。

在故事板中，每個代理人用4個像素表示，3個像素位于同一行，一個像素在另一行表示方向。用一個T型表示和描述一個任務(wù)。在圖2中，狀態(tài)、方向和動作信息包含在幀中，即圖2(a)。圖2(b)用圓點(diǎn)和箭頭來表示所有信息。圖2(c)為最終的小規(guī)模故事板，人群的信息集成于故事板，圖2(d)中T形中間標(biāo)記0的地方表示之前提到的人物狀態(tài)。標(biāo)記1的部分用來表示不同的個體。標(biāo)記2表示每個人物的方向。其次，不同顏色代表不同信息。對于標(biāo)記0，當(dāng)人物漫步時，用橙色著色，當(dāng)人物遇到緊急情況或匆忙行走時，用紅色著色。對于標(biāo)記2，綠色代表代理人步行，黃色表示跑步，粉色代表交談，紅色代表跳躍。對于標(biāo)記1，顏色用來根據(jù)行為共性進(jìn)行分組。用戶可以自行定義顏色的含義。這些對應(yīng)于狀態(tài)集。P是標(biāo)記0對應(yīng)的坐標(biāo)位置，D是標(biāo)記2表示的方向，Cs表示標(biāo)記0的顏色。例如，在圖2(b)中，綠色箭頭表示它的方向為下方且動作為行走。紅色和橙色的著色點(diǎn)為當(dāng)前狀態(tài)。圖2(d)中的方向為向下，而圖2(e)中的方向為右下。故事板的T型定義如表1所示。

表1 故事板T型定義

2．4．2 方向定義

在判斷每個代理人的方向時，對于每一個代理人，定義一個3×3像素的方格，外層3個方格與中心方格所組成的T形，決定了代理人的方向，共有8個方向。將外層8個像素從左上角開始順時針進(jìn)行編號，分別為 1，2，4，8，16，32，64，128，如圖 3 所示。這樣，在外層8個像素中任意選取任意多個像素，每種組合的編號之和都是唯一的，如果像素方向合法，對像素進(jìn)行一次掃描后便可得到代理人的方向。例如圖3(b)所示，其著色像素編號為8，16，64，其和為8+16+64=88，說明代理人方向為Down。

圖3 對像素進(jìn)行編號和Down方向的像素圖

方向編碼唯一性證明如下。

外層8個像素的編號分別對應(yīng)著二進(jìn)制編碼串:

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

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

064-01000000，128-10000000

每個像素不會重復(fù)著色，且各像素的二進(jìn)制編碼中非零位互不相同，因此，任意多個不同像素編碼之和在二進(jìn)制編碼中不會產(chǎn)生進(jìn)位，其和唯一確定一種著色組合。所以方向的標(biāo)識組合是唯一的。

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

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

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

Right Down=164

方向二進(jìn)制編碼對應(yīng)表如圖4所示。其中，Y所示的為掃描到的非白色像素點(diǎn)對應(yīng)的編碼值;Sum為代表某個方向的所有值的和。

圖4 方向編碼表

3 大規(guī)模故事板的生成

3．1 紋理合成算法

本文應(yīng)用文獻(xiàn)［12］算法，該算法簡單，而且得到的接縫誤差最小，視覺上也更加平滑。完整的算法描述如下:

(1)按照掃描線順序合成圖像。

(2)對于每一個位置，搜索輸入的紋理圖的塊集合，查找符合匹配條件的紋理塊，并隨機(jī)選取一塊Bi(i=0，1，…)。

(3)把新選擇的塊復(fù)制輸出圖像后再在輸入樣圖中查找Bi+1，當(dāng)把Bi+1放入輸出圖時Bi+1與前一塊已合成的Bi要有一定的邊界重疊，然后在重疊區(qū)域找出一條誤差最小的路徑作為Bi+1邊緣，把Bi+1復(fù)制到輸出圖中，返回步驟(2)繼續(xù)執(zhí)行，直到獲得合成紋理圖。

本文采用對輸入樣本進(jìn)行逐個塊復(fù)制的合成方法，通過這種合成方法創(chuàng)建的片形狀不規(guī)則，使人群仿真效果顯得更自然。

3．2 紋理合成過程

結(jié)合具體實例對紋理合成大規(guī)模人群信息圖，進(jìn)而完成人群靜態(tài)站位的整個過程進(jìn)行說明。在本次實驗中，主要場景是模擬地鐵站的甬道，地鐵站的人群規(guī)模為500人左右。

所用的視頻如圖5所示，由于所用視頻的要求為頂視圖，且人群規(guī)律性盡量明顯，這樣的視頻很難從網(wǎng)絡(luò)或者現(xiàn)實中取得，自行拍攝也費(fèi)時費(fèi)力，本文中應(yīng)用的視頻是由文獻(xiàn)［13］中使用的自行拍攝的一組公開視頻。其中包括群體聊天、演講、排隊等車等諸多人群模式，非常符合本文實驗對于視頻的要求。

圖5為第1幀經(jīng)過中間的處理過程，最終得到小規(guī)模故事板過程。

圖5 小規(guī)模故事板處理過程

圖6表示了通過輸入甬道模型的頂視圖的目標(biāo)圖像和故事板(圖6(a)中打圈的部分)，得到最終的大規(guī)模故事板至最終將代理人排布到場景中成功站位。

圖6 大規(guī)模代理人模型生成過程

4 基于視頻數(shù)據(jù)驅(qū)動的人群動畫

4．1 數(shù)據(jù)驅(qū)動

近年來，數(shù)據(jù)驅(qū)動方法已經(jīng)成為模擬復(fù)雜人群行為的重要方法。數(shù)據(jù)驅(qū)動的方法［14］數(shù)據(jù)信息來源于2種途徑。一種是運(yùn)動捕獲數(shù)據(jù)，另一種是追蹤視頻。通過捕獲或者追蹤到的數(shù)據(jù)信息驅(qū)動人的行為。

同時，通過真實的視頻進(jìn)行觀察追蹤個體信息應(yīng)用越來越廣泛，這種方法能夠真實再現(xiàn)視頻中的多種場景，如談話、聽演講、看演唱會等人的狀態(tài)，可以具體到肢體動作。其過程描述如下，追蹤視頻中的每個個體，將每個個體的數(shù)據(jù)存儲在相應(yīng)文檔或數(shù)據(jù)庫中，在虛擬仿真過程中，通過查找的方式獲得每個代理人的數(shù)據(jù)。

通過衡量這2種數(shù)據(jù)驅(qū)動方法的利弊，選擇基于視頻的數(shù)據(jù)驅(qū)動方法。

4．2 故事板數(shù)據(jù)驅(qū)動人群

本文數(shù)據(jù)驅(qū)動的方法基于視頻追蹤并結(jié)合手動提取一小段時間路徑向量信息。主要思想是從原始視頻的關(guān)鍵幀中半自動提取人物位置信息組成連續(xù)的路徑向量信息，生成代理人根據(jù)得到的這些路徑向量序列生成各自的運(yùn)動路徑。生成路徑的方式考慮到2種，一種是嚴(yán)格按照原始人物的路徑向量序列中元素的順序生成新路徑，另一種是每類代理人在原始人物的路徑向量序列中隨機(jī)挑選某一位置的元素迭代生成新路徑。2種方式各有優(yōu)缺點(diǎn)，但考慮到原始人物路徑向量序列中各元素的差異性可能過大，并且隨機(jī)挑選元素可能會造成新代理人不能很好體現(xiàn)出原始人物特性的因素，因此選擇前者生成代理人的路徑。

代理人路徑計算過程簡述如下:視頻以每一秒作為時間間隔設(shè)置時間點(diǎn)，每個時間點(diǎn)位置截取相應(yīng)的關(guān)鍵幀，從關(guān)鍵幀中手動標(biāo)注個體的位置信息，自動提取位置信息。通過相鄰2個關(guān)鍵幀中獲得的位置信息計算出時間段內(nèi)個體的運(yùn)動路徑向量，利用此向量與生成代理人的起點(diǎn)位置信息計算得出代理人的終點(diǎn)位置。

例如，視頻中第i個人的路徑向量信息可以表示為:

其中，向量Pij的信息通過如下方式獲得:視頻中個體i在第j-1秒關(guān)鍵幀中的位置為(m，n)，在j秒關(guān)鍵幀中的位置為(p，q)。那么個體i在這一秒內(nèi)運(yùn)動路徑的向量表示為:

通過上述計算公式，可以獲得視頻中所有個體的路徑向量信息，組成一系列向量集合，存儲在相應(yīng)格式的文檔中。代理人進(jìn)行路徑規(guī)劃的時候，只需要知道他當(dāng)前的位置以及下一秒所對應(yīng)的向量信息，通過下述方法獲得終點(diǎn)位置。例如代理人A是由視頻中的個體i獲得的，假設(shè)當(dāng)前代理人A在第j-1秒的初始位置為 Pstartj=(a，b)，終點(diǎn)位置設(shè)為Pendj=(c，d)，通過查找文檔找到其相應(yīng)的向量Pij，通過方程式解(c-a，d-b)=Pij，計算得到c和d的值，從而獲得終點(diǎn)位置。代理人獲取到終點(diǎn)位置，在第j秒時間段內(nèi)將一直朝向求得的終點(diǎn)位置前進(jìn)，此時代理人的面部方向可能一直在變化，但一直是朝向計算得到的終點(diǎn)。

4．3 碰撞躲避

從初始點(diǎn)走到終點(diǎn)的過程中，個體與個體之間會產(chǎn)生碰撞，為了使人群中的每個代理人能夠順利到達(dá)各自終點(diǎn)，需要對碰撞進(jìn)行檢測并采取相應(yīng)避免的措施。

本文的碰撞檢測算法基于行為心理學(xué)［15］。人類會有一個自身認(rèn)可的安全距離，在安全距離的范圍內(nèi)會檢查他人或障礙物是否存在與自己發(fā)生碰撞的可能。根據(jù)安全距離概念，結(jié)合包圍盒的思想，本文實驗中給定代理人一個以最小安全距離為半徑的圓柱體作為包圍盒，當(dāng)包圍盒發(fā)生相交時，也就是代理人與代理人發(fā)生碰撞時，代理人會瞬時調(diào)整自己的速度方向，隨機(jī)選擇在凝視角度范圍內(nèi)的一個角度，改變運(yùn)動速度及方向。

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

圖7 碰撞躲避算法流程

算法并不復(fù)雜，但在實際應(yīng)用中效果甚佳。在走廊場景中生成大規(guī)模的人群，他們在穿越走廊的運(yùn)動仿真中可以輕易避開即將發(fā)生的碰撞，沒有任何因卡死而導(dǎo)致代理人停止運(yùn)動的情況發(fā)生。

5 實驗及結(jié)果分析

本次實驗在地鐵通道場景中進(jìn)行，主要對視頻中的地鐵通道場景中的人群進(jìn)行虛擬運(yùn)動仿真。

將小規(guī)模故事板通過紋理合成方式合成大規(guī)模故事板，實現(xiàn)了以較小規(guī)模的視頻完成大規(guī)模虛擬人群運(yùn)動仿真的目標(biāo)，并且實驗中生成的虛擬人群運(yùn)動效果與視頻中人群的運(yùn)動效果具有較高的一致性。視頻幀序列如圖8所示，實驗效果如圖9～圖11所示。

圖8 視頻幀序列

圖9 人群運(yùn)動近景圖

圖10 100人運(yùn)動效果

圖11 200人運(yùn)動效果

同時，還對不同規(guī)模的人群做了相關(guān)實驗，采集到的數(shù)據(jù)如表2所示。表2中第1列為單次實驗人群規(guī)模，第2列～第4列分別表示單次實驗中代理人靜態(tài)站位消耗時間、代理人從初始點(diǎn)到達(dá)目的地消耗時間以及單次實驗消耗總時間。

表2 不同規(guī)模代理人的數(shù)據(jù)采集信息

隨著規(guī)模成倍數(shù)的擴(kuò)大，站位時間明顯不是成倍數(shù)增長的。分析原因，由于人在靜態(tài)站位到場景中時，為了使得站位更自然，給每個代理人加了一個靜態(tài)站位的動作，每個人站在原地都有自己的動作，有的左顧右盼，有的抓耳撓腮，有的左晃右晃，當(dāng)人群規(guī)模不斷增大時，需要處理越來越多的靜態(tài)站位動作，造成了時間的不成倍數(shù)增長。從這個過程可以看出，隨著人群密度的增長，時間增長速度隨之增加，其中產(chǎn)生的碰撞躲避過程也隨之增多，影響實驗效率。

6 結(jié)束語

本文提出一種基于數(shù)據(jù)驅(qū)動的、紋理合成故事板的虛擬人群運(yùn)動仿真方法。以故事板來收集視頻中的人群信息，通過紋理合成算法生成超大規(guī)模人群故事板，并在三維場景中提取大規(guī)模人群故事板數(shù)據(jù)信息，指導(dǎo)人群運(yùn)動，生成虛擬人群動畫。實驗結(jié)果證明，大規(guī)模虛擬人群中的個體行為與視頻中對應(yīng)的個體行為相似，提高了大規(guī)模虛擬人群動畫生成的效率。下一步將研究大規(guī)模人群渲染加速和實現(xiàn)實時渲染，并考慮環(huán)境問題對人群運(yùn)動產(chǎn)生的影響，提高虛擬人群運(yùn)動仿真的真實性。

［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ī)理論的人群行為模型［J］．計算機(jī)工程，2013，39(12):290-293．

［5］ 劉 箴，潘志庚．虛擬人動機(jī)驅(qū)動的自主情緒模型研究［J］．中國圖象圖形學(xué)報，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，F(xiàn)itusiE，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］ 王 鑫，孫守遷，侯 易，等．?dāng)?shù)據(jù)驅(qū)動的人群場景動畫合成方法［J］．計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，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．