葉志鵬，趙 巍，劉 鵬，唐降龍

（哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院，150001哈爾濱）

元胞駐留視頻群體狀態(tài)預(yù)報方法

葉志鵬，趙 巍，劉 鵬，唐降龍

（哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院，150001哈爾濱）

視頻場景人群狀態(tài)預(yù)報是防止公共場所安全事故的一種重要措施.為此提出了一種視頻場景群體狀態(tài)預(yù)報模型.該模型使用格內(nèi)駐留元胞自動機（inner-grid parking cellular automata，IPCA）模型預(yù)報視頻中群體狀態(tài).首先，通過光流法進行運動跟蹤作為IPCA的輸入特征對場景進行建模，并根據(jù)特征點的運動狀態(tài)自適應(yīng)地調(diào)整其在元胞格內(nèi)的駐留時間以提高預(yù)報精度；其次，通過分析IPCA模型的預(yù)測結(jié)果判斷群體微團間的相互作用得到視頻幀的狀態(tài)信息，從而達到對場景中人群狀態(tài)進行預(yù)報的目的；最后，利用當(dāng)前場景的狀態(tài)信息對該場景的預(yù)報輸出進行反饋校正，使模型能夠及時地反映場景中群體狀態(tài)的變化，該模型不依賴于具體的視頻幀，以微團結(jié)構(gòu)的碰撞作為異常檢測依據(jù).實驗結(jié)果表明，與傳統(tǒng)的檢測方法相比，該預(yù)報模型能夠提前預(yù)報視頻場景中的異常狀態(tài)，并具有較好的準(zhǔn)確性.

視頻處理；元胞自動機；格內(nèi)駐留；狀態(tài)檢測和反饋；狀態(tài)預(yù)報

近年來隨著社會的快速發(fā)展，大規(guī)模人員聚集和運動的情況和場所大量增加，公共場所的大規(guī)模安全事故屢有發(fā)生，造成了人員傷亡和財產(chǎn)損失，給活動的組織管理者和參與者帶來明顯的安全挑戰(zhàn).對人群狀態(tài)預(yù)報可以提前獲知人群運動狀況的變化，提高應(yīng)急措施的效率和效果，將群體危機消除在萌芽狀態(tài)，對防止安全事故的發(fā)生具有重要的意義.

近來，國內(nèi)外學(xué)者通過元胞自動機（cellular automata，CA）模型，研究特定場景下大規(guī)模群體疏散問題.Burstedde等［1］首次提出了基于動態(tài)參數(shù)的地場CA模型；Yamamoto等［2］對CA進行了改進，提出了實數(shù)編碼的CA模型，其最主要的改進是將速度的范圍從整數(shù)擴展到了實數(shù)集合，從而增強了CA在描述群體運動中的靈活性和適應(yīng)性.Hao等［3］提出了用于描述雙向行人流的CA模型，該模型使用動態(tài)參數(shù)形式，將行人的轉(zhuǎn)移收益分解為各參數(shù)之和，提出了行人視場的概念，并描述了實際情況下行人隨大流和躲避擁擠區(qū)域的心理狀態(tài).Wang等［4］提出了一個用于描述室內(nèi)行人行為的CA模型，將行人的運動分為3種形式:向目標(biāo)移動、碰撞和躲避擁塞以及組團，并研究各種行為對應(yīng)的代價函數(shù)對行人轉(zhuǎn)移收益和路徑選擇的影響.這些描述群體狀態(tài)或運動的CA模型側(cè)重于描述群體在場景中的分布和速度間的關(guān)系，存在描述視頻特征困難、不能結(jié)合視頻特征提供CA模型參數(shù)修正方法，導(dǎo)致CA模型缺乏對群體狀態(tài)的預(yù)報能力.

針對以上CA模型的局限性，本文將群體中的微團結(jié)構(gòu)作為研究對象.微團結(jié)構(gòu)是群體中具有相似運動特征的個體的集合.除了自主運動以外，微團之間的相互作用是影響群體狀態(tài)的主要因素.本文研究認(rèn)為微團中個體自主運動的目的性和微團之間相互作用的隨機性導(dǎo)致了群體成為確定性和隨機性并存的系統(tǒng).本文提出了格內(nèi)駐留元胞自動機（inner-grid parking CA，IPCA）群體狀態(tài)預(yù)報模型.首先通過光流法獲取場景中群體的運動狀態(tài)參數(shù)，然后將群體運動速度矢量作為模型的輸入對IPCA模型進行初始化并根據(jù)特征點的速度設(shè)置其在元胞格內(nèi)的駐留時間來完成場景的建模.運動特征點的駐留時間在特征點移出場景前會一直存在并根據(jù)不同的檢測結(jié)果自適應(yīng)地調(diào)整.本文提出了基于檢測-校正的群體預(yù)報模型，檢測視頻中微團之間的相互作用，并將檢測結(jié)果作為校正模型參數(shù)的依據(jù)，對群體狀態(tài)進行預(yù)報.實驗結(jié)果表明，本文提出的檢測方法更具靈活性，檢測-校正的參數(shù)調(diào)節(jié)使模型具有自適應(yīng)能力，取得了良好的預(yù)報效果.

1 CA模型

CA是一種通用的建模方法，也是動力學(xué)系統(tǒng)中有關(guān)秩序、混沌、非對稱等系統(tǒng)整體行為與復(fù)雜現(xiàn)象的一種有效研究手段.一個標(biāo)準(zhǔn)的元胞自動機A由元胞、元胞狀態(tài)、鄰域和狀態(tài)更新規(guī)則構(gòu)成.用數(shù)學(xué)表示為［5］

式中:L為元胞空間；d為元胞自動機內(nèi)元胞空間的維數(shù)；S為元胞有限的、離散的狀態(tài)集合；N為某個鄰域內(nèi)所有元胞的集合；f為局部映射或局部規(guī)則．在二維CA中常見的鄰域有馮·諾伊曼鄰域和摩爾鄰域.圖1中實心圓代表特征點當(dāng)前位置，在每個時間步特征點可以通過計算其周圍8個元胞格的轉(zhuǎn)移收益進行特定方向的移動，如圖1所示.

圖1 二維CA的鄰域

對CA中元胞轉(zhuǎn)移收益的計算采用動態(tài)參數(shù)模型［3］，如

式中Pij為目標(biāo)向其鄰域內(nèi)第i行第j列的元胞格移動的轉(zhuǎn)移收益值．每個參數(shù)的意義及取值如下:

1）方向參數(shù)Dij反映了行人根據(jù)其當(dāng)前運動方向選擇下一個方向的代價為

其中a∈（0，1）且a∈R．其意義為目標(biāo)優(yōu)先移向其正前方的元胞．

2）空參數(shù)Eij反映元胞格是否被占用為

3）前向參數(shù)Fij反映行人躲避擁塞的意愿為

在現(xiàn)實中通常表現(xiàn)為行人不愿向人多可能造成擁塞的地區(qū)運動.其中:S1為市場中空元胞數(shù)目；S2為被占用的元胞數(shù)目；R為行人視場大小，即特征點視場范圍內(nèi)元胞數(shù)目．

4）內(nèi)容參數(shù)Cij反映行人希望隨著和自己同方向行進的人一同行走的意愿，在現(xiàn)實中常表現(xiàn)為“隨大流”為

式中:S3為空元胞和場景中與當(dāng)前行人運動方向相容的行人數(shù)之和；S4為場景中與當(dāng)前行人運動方向不相容的行人數(shù)之和；R為行人視場大小．本文將CA相容方向集定義為:｛左上，左下，水平向左｝、｛右上，右下，水平向右｝、｛左上，垂直向上，右上｝和｛左下，垂直向下，右下｝.同時，各方向和自身也是相容的.

2 IPCA的視頻場景群體狀態(tài)預(yù)報方法

本文將視頻場景劃分為多個正方形元胞格.場景的建模過程將光流法獲取的每個運動特征點依據(jù)其在視頻幀中的位置放置于相應(yīng)的元胞格中，對每個特征點以元胞格的大小與速度幅值之比作為其在該元胞格內(nèi)的駐留時間，表示特征點經(jīng)過多少時間后可以移出該元胞格.本文利用IPCA的轉(zhuǎn)移規(guī)則描述群體未來的運動情況.

2.1 IPCA建模

視頻場景中所有特征點組成的集和P定義為

對所有Pi∈P，將其位置（xi，yi）和速度矢量vt輸入IPCA，構(gòu)建初始狀態(tài)S0；依據(jù)預(yù)先設(shè)定的轉(zhuǎn)移規(guī)則驅(qū)動模型預(yù)測S1到Sn的狀態(tài)．其過程如圖2所示．

圖2 IPCA建模過程

2.1.1 IPCA參數(shù)計算方法

針對以往CA的研究不能很好地描述視頻場景的不足，本文通過對行人視場、消除建模誤差、參數(shù)計算和獲取方面做了相應(yīng)的改進，得到IPCA模型.

1）行人的視場形狀由矩形改為三角形，這更加符合人類視野的扇形描述，如圖3所示.

3）前向參數(shù)Fij計算方法為

式中:Rc為目標(biāo)當(dāng)前視場大小；R為圖2所示的視場大?。粢粋€區(qū)域內(nèi)空元胞較多，則Fij較大，使特征點傾向于向該區(qū)域移動；反之會使特征點趨于躲避該區(qū)域，因此Fij描述了行人躲避擁塞意愿的強烈程度．根據(jù)視場大小計算Fij可以避免因視場不足由不完整數(shù)據(jù)導(dǎo)致的計算誤差，同時也簡化了計算過程．

4）通過對視頻幀的光流分析和計算得到運動特征點的速度幅值和方向，具有更好的客觀性.

圖3 三角形視場示意

2.1.2 IPCA轉(zhuǎn)移規(guī)則

當(dāng)前元胞中特征點在下一時刻的轉(zhuǎn)移狀態(tài)依據(jù)其近鄰元胞的當(dāng)前狀態(tài)，其合理程度直接影響了CA描述結(jié)果的準(zhǔn)確性.本文提出的轉(zhuǎn)移規(guī)則如下:

1）特征點傾向于向轉(zhuǎn)移收益最大的元胞格移動；

2）當(dāng)發(fā)生沖突時，如多個特征點試圖同時移向一個元胞，則隨機選擇一個特征點進行移動，其他特征點保持原地不動；

3）對每個特征點的駐留時間t，若當(dāng)前特征點已駐留等待的時間小于t，則該特征點停留在所在元胞格不動，否則根據(jù)規(guī)則1）進行移動，移動后其tw置零重新進入等待狀態(tài)；

4）日常生活中，人們總是傾向于最快地到達目的地，因此本文假設(shè)特征點不執(zhí)行后退移動.

由轉(zhuǎn)移規(guī)則可以看出，IPCA在保持了原始模型簡潔性的同時仍能夠模擬復(fù)雜的現(xiàn)象.

本文使用K-means聚類算法將場景中不同位置的運動特征點劃分為不同的微團.因此對場景中行人的異常狀態(tài)的檢測轉(zhuǎn)換為對每個微團的狀態(tài)進行檢測.異常判別標(biāo)準(zhǔn)為微團間發(fā)生碰撞或重疊，以表達行人間的相互撞擊和推擠.

2.2 群體狀態(tài)檢測

微團是由空間內(nèi)相鄰運動特征點所組成的結(jié)構(gòu).某一時刻場景中共存在兩種狀態(tài)的微團:正常微團和異常微團.本文認(rèn)為處于正常狀態(tài)的微團結(jié)構(gòu)不與其他任何微團重疊；反之，則為異常微團，此時對于高強度行人流來說，人群將變得非常擁擠接近堵塞，人員的聚集風(fēng)險將大大增加［6］.本文采用一種基于微團碰撞的異常狀態(tài)檢測（micell state detection，MSD）方法.將微團分為上、下、左、右4個子微團.對每個子微團，若與其他鄰近微團發(fā)生重疊，則該微團當(dāng)前處于異常狀態(tài)，否則處于正常狀態(tài).

通常情況下光流法提取的特征點不可避免的受到來自環(huán)境中噪聲的影響而產(chǎn)生錯誤的結(jié)果，從而影響異常檢測結(jié)果的準(zhǔn)確性.因此，在最終的異常判斷中，通過設(shè)置異常幀在檢測半徑內(nèi)所占百分比s對進行結(jié)果平滑，s又稱為敏感系數(shù)．對于同一幀視頻場景的預(yù)報結(jié)果，若檢測到的異常次數(shù)t與預(yù)報半徑m滿足則判斷當(dāng)前幀為異常幀.

2.3 群體狀態(tài)預(yù)報方法

本文提出的群體狀態(tài)預(yù)報方法通過獲取一定時間內(nèi)的歷史狀態(tài)信息，利用IPCA模型對處于預(yù)報半徑m內(nèi)的未來某一時刻的群體狀態(tài)進行預(yù)測，根據(jù)檢測結(jié)果得到關(guān)于群體未來狀態(tài)的預(yù)報值.在預(yù)報時刻到來時，利用對當(dāng)前場景的特征檢測結(jié)果反饋更新模型對當(dāng)前時刻的預(yù)報輸出.其過程如

圖4 人群狀態(tài)預(yù)報

對視頻場景特征點集中任意兩點X1（x1，y1）、X2（x2，y2），若其歐式距離ρ（x，y）≤T，則認(rèn)為特征點X1與X2是相鄰的．定義兩個集合的和運算為

式中:M為合并兩幀中所有近鄰點集組成的集合；UM為非近鄰點組成的集合．特別地，若Pn= φ，則Pn⊕Pn+1=Pn+1，初始狀態(tài)Result=φ，P0為第0幀視頻的特征點集合．

反饋⊕過程如下:對近鄰點集M?Result，執(zhí)行1次特征點集更新.

其中，特征點集更新算法如下:

2.4 自適應(yīng)預(yù)報參數(shù)修正

視頻場景通常是不斷變化的.CA模型的預(yù)測輸出值會隨時間推移與實際情況有較大偏差；同時，光流法提取的特征點由于攝像機抖動等因素存在誤差，這兩個因素會影響IPCA預(yù)報的準(zhǔn)確度.本文提出方法的回饋階段主要解決以上問題.

利用當(dāng)前狀態(tài)的檢測結(jié)果更新上一狀態(tài)的預(yù)報值，如

式中:c為更新速率；Fn-1為前n-1幀對當(dāng)前幀的預(yù)報初值，模型以此輸出值作為預(yù)報起點，向后預(yù)報一定時間步內(nèi)場景的狀態(tài)，該時間長度作為預(yù)報半徑m．因此，對于變化較為劇烈的場景，較小的c可以令模型的輸出值更趨向于當(dāng)前檢測結(jié)果，使模型增強模型容忍場景變化的能力；對于變化較為平緩和連續(xù)的場景，較大的c可以更多的保留場景中一定時間步內(nèi)的歷史信息，使模型的更新過程更為準(zhǔn)確．

2.5 IPCA預(yù)報方法的特點

本文提出的IPCA視頻場景群體狀態(tài)預(yù)報方法具有兩個特點:

1）使用IPCA模型作為預(yù)報的基礎(chǔ)描述真實視頻場景.與傳統(tǒng)的CA模型相比，IPCA模型能夠接受運動跟蹤結(jié)果自適應(yīng)地設(shè)置其初始狀態(tài)；通過引入元胞格內(nèi)駐留時間，使對特征點運動的描述更加準(zhǔn)確，降低了場景的建模誤差從而能使模型更好地描述視頻場景的狀態(tài)；

2）不斷利用場景的最新信息對模型參數(shù)進行反饋調(diào)整以提高預(yù)報的準(zhǔn)確度.反饋過程使模型能夠及時地反映場景中群體的狀態(tài)變化.

傳統(tǒng)的CA模型將所有特征點的速度均設(shè)置為一個固定值1，沒有考慮不同人群行進速度不同的特點.本文針對CA的局限性，引入了與人群行進速度密切相關(guān)的元胞格內(nèi)駐留時間，進而改進了傳統(tǒng)CA的轉(zhuǎn)移規(guī)則，提出了IPCA模型. IPCA模型通過對場景人群狀態(tài)的建模，根據(jù)人群行進速度各不相同的特點，將元胞內(nèi)特征點移動速度的取值范圍和方式進行建模，并通過駐留時間消除行進中的位置誤差，從而達到預(yù)報群體狀態(tài)的效果.

3 結(jié)果與分析

本文使用了3個數(shù)據(jù)集:PETS09（幀尺寸768 ×576，正常情形）、WEB Dataset（幀尺寸1 280×720，異常情形）以及作者在校園內(nèi)拍攝的視頻Self Dataset（幀尺寸1 280×720，正常異常情形交替出現(xiàn)），其中，UCF的WEB Dataset中同方向奔跑的群體狀態(tài)識別是具有挑戰(zhàn)性的.實驗中取反饋更新速率c=0.7，敏感系數(shù)s=0.5，檢測半徑r=10，預(yù)報半徑m=15，前向參數(shù)Dij中a=0.7．本文將所提出的基于IPCA的檢測方法與近幾年的主流檢測方法（文獻［7-12］）進行了比較.實驗結(jié)果如表1所示.表2為CA與IPCA作為預(yù)報模型，采用MSD檢測方法的結(jié)果.表中:數(shù)據(jù)左側(cè)為漏報率；右側(cè)為誤報率.

表1 各方法比較結(jié)果%

表2 IPCA與CA的預(yù)報精度比較%

從表1可以看出，與其他檢測方法相比，IPCA與MSD的預(yù)報方法具有最優(yōu)性能.這是由于以往的方法局限于當(dāng)前場景異常狀態(tài)的檢測，忽視了異常狀態(tài)的發(fā)生是一個漸進過程，而本文模型不僅獲取當(dāng)前場景的狀態(tài)，而且利用之前一段時間內(nèi)場景的狀態(tài)作為預(yù)報的知識參與模型的反饋修正過程后再進行狀態(tài)檢測，因此具有較好效果.

從表2結(jié)果可以看出，在采用相同檢測方法的前提下，本文提出的IPCA與傳統(tǒng)CA相比具有較高的預(yù)報精度.與傳統(tǒng)CA相比，IPCA的格內(nèi)駐留特點不僅結(jié)合實際視頻場景改進了CA的轉(zhuǎn)移規(guī)則與元胞格參數(shù)的計算，同時根據(jù)人群行進速度不同的特點引入駐留時間使群體狀態(tài)的建模更為準(zhǔn)確，從而提高了整體模型針對群體狀態(tài)預(yù)報的精度.

4 結(jié) 論

1）通過結(jié)合光流法獲取的運動特征，自適應(yīng)地設(shè)置每個特征點在元胞格內(nèi)的駐留時間.

2）采用微團場景狀態(tài)建模方法對場景中人群狀態(tài)進行檢測和預(yù)報.

3）利用當(dāng)前場景的最新信息對模型綜合歷史信息給出的預(yù)報值進行反饋校正，以達到盡早發(fā)現(xiàn)并防止發(fā)生安全事故的目的.實驗結(jié)果表明，本文方法具有較好的群體狀態(tài)預(yù)報能力.

［1］BURSTEDDE C，KLAUCK K，SCHADSCHNEIDER A et al.Simulation of pedestrian dynamics using a twodimensional cellular automaton［J］.Physica A: Statistical Mechanics and its Applications，2001，295（3）:507-525.

［2］YAMAMOTO K，KOKUBO S，NISHINARIK.Simulation for pedestrian dynamics by real-coded cellular automata（RCA）［J］.Physica A:Statistical Mechanics and its Applications，2007，379（2）:654-660.

［3］HAO Y，GUAN Hongzhi，ZHANG Juan，etal.Study on bi-direction pedestrian flow using cellular automata simulation［J］.Physica A:Statistical Mechanics and its Applications，2010，389（3）:527-539.

［4］WANG Dalong，KWOK N M，JIA Xiuping，et al.A cellular automata based crowd behaviormodel［C］／／IEEE Conference on Artificial Intelligence and Computational Intelligence.Sanya:IEEE，2010:218-225.

［5］AMOROSO S，YALE N P.Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures［J］.Journal of Computer and System Sciences，1972，6（5）:448-464.

［6］MA J，LO SM，SONGW G，etal.Modeling pedestrian space in complex building for efficient pedestrian traffic simulation［J］.Automation in Construction，2013，30: 25-36.

［7］MEHRAN R，OYAMA A，SHAH M.Abnormal crowd behavior detection using social force model［C］／／IEEE Conference on Computer Vision and Pattern Recognition. Miami:IEEE，2009:935-942.

［8］MORRIS B，TRIVEDIM.Learning trajectory patterns by clustering:Experimental studies and comparative evaluation［C］／／IEEE Conference on Computer Vision and Pattern Recognition.Miami:IEEE，2009:312-319.

［9］JUNSEOK K，LEE K M.A unified framework for event summarization and rare event detection［C］／／IEEE Conference on Computer Vision and Pattern Recognition. Providence:IEEE，2012:1266-1273.

［10］YANG Cong，YUAN Junsong，LIU Ji.Sparse reconstruction cost for abnormal event detection［C］／／IEEE Conference on Computer Vision and Pattern Recognition.Colorado:IEEE，2011:3449-3456.

［11］NATARAJAN P，WU Shuang，VITALADEVUNIS，et al.Multimodal feature fusion for robust event detection in web videos［C］／／IEEE Conference on Computer Vision and Pattern Recognition.Providence:IEEE，2012:1298-1305.

［12］朱海龍，劉鵬，劉家鋒，等.人群異常狀態(tài)檢測的圖分析方法［J］.自動化學(xué)報，2012，38（5）:742-750.

（編輯張 紅）

Inner-ellular automata method for video pedestrian state forecasting

YE Zhipeng，ZHAOWei，LIU Peng，TANG Xianglong
（School of Computer Science and Technology，Harbin Institute of Technology，150001 Harbin，China）

Forecasting pedestrian states with the help of video analysis is a significant mean to prevent accidents in public places.An improved Inner-grid Parking Cellular Automata（IPCA）model is proposed to forecast pedestrian state.Motion tracking and scenario modeling are firstly achieved by optical flow method，and then motion states of pedestrian are used to adjust parking time in cellular adaptively to improve forecasting accuracy.Here，the state of an incoming video frame is acquired by analyzing the interaction between micelles，which is provided by the forecasting result of IPCA.After that，a feedback algorithm is employed to revise the forecasting result so that themodel could reflect precisely the change of pedestrian state in the scenario.A criterion is also proposed to judge the abnormal state of a video frame，which is collision between twomicelles.Compared to other traditional detection methods，IPCA based model has a good ability in predicting the abnormal state ahead of time and obtaining better accuracy.

video processing；cellular automata；inner-grid parking；state detection and feedback；state forecasting

TP391.4

A

0367-6234（2014）09-0025-06

2013-10-21.

國家自然科學(xué)基金資助項目（61171184，61201309）.

葉志鵬（1989—），男，博士研究生；唐降龍（1960—），男，教授，博士生導(dǎo)師.

唐降龍，tangxl＠hit.edu.cn.