章東平,錢樂義

(中國(guó)計(jì)量大學(xué) 信息工程學(xué)院,浙江 杭州 310018)

基于結(jié)構(gòu)化學(xué)習(xí)的小群體主導(dǎo)者檢測(cè)方法

章東平,錢樂義

(中國(guó)計(jì)量大學(xué) 信息工程學(xué)院,浙江 杭州 310018)

人群分析在模式識(shí)別和機(jī)器學(xué)習(xí)領(lǐng)域內(nèi)是一個(gè)非常有趣的課題.人群小群體成員之間的主從關(guān)系檢測(cè)為視頻監(jiān)控和計(jì)算機(jī)視覺領(lǐng)域打開了新的視野.同時(shí),小群體主導(dǎo)者的檢測(cè)也是人群分析的重要組成部分.文章提出一種結(jié)構(gòu)化SVM的學(xué)習(xí)框架,并結(jié)合行人的時(shí)間滯后分析特征和行人位置關(guān)系特征對(duì)小群體主導(dǎo)者進(jìn)行預(yù)測(cè).實(shí)驗(yàn)結(jié)果表明,本方法在人群分析數(shù)據(jù)集下取得了很好識(shí)別效果.

人群分析;主導(dǎo)者檢測(cè);時(shí)間滯后分析;結(jié)構(gòu)化SVM

隨著智能視頻監(jiān)控技術(shù)[1]的發(fā)展,過(guò)去的幾年里,人們對(duì)于人群場(chǎng)景下的行人行為的分析和理解的興趣越來(lái)越高.小群體的主導(dǎo)者檢測(cè)有利于人們對(duì)視頻監(jiān)控系統(tǒng)下人群分析和安全問題的場(chǎng)景理解和宏觀的認(rèn)識(shí).然而,小群體的主導(dǎo)者檢測(cè)是一個(gè)熱門的并且未徹底解決的問題.

精確檢測(cè)出人群場(chǎng)景里的小群體主導(dǎo)者對(duì)公共安全非常有利.在高密度的人群場(chǎng)景下,比如示威游行或者體育活動(dòng),安保人員就可以側(cè)重關(guān)注人群里面的主導(dǎo)者,而不是分析整個(gè)人群的行為.此外,在封閉的環(huán)境里面,比如監(jiān)獄,小群體的主導(dǎo)者檢測(cè)技術(shù)將非常有利于去識(shí)別監(jiān)獄里面最有影響力的囚犯.

近幾年來(lái),研究者對(duì)人群分析進(jìn)行了大量的研究,但是對(duì)于小群體的主導(dǎo)者檢測(cè)的研究比較少.文獻(xiàn)[2]中提到,在一個(gè)團(tuán)隊(duì)中,主導(dǎo)者在這個(gè)團(tuán)隊(duì)中是一個(gè)擁有著權(quán)利和地位的一個(gè)角色,團(tuán)隊(duì)里面的其他成員的工作內(nèi)容和方向都是由主導(dǎo)者決定的.在兩個(gè)成員或兩個(gè)以上的團(tuán)隊(duì)里,就每?jī)蓚€(gè)成員之間的關(guān)系而言,主導(dǎo)者對(duì)其他成員的影響力超過(guò)了團(tuán)隊(duì)里面其他任何一個(gè)成員.文獻(xiàn)[3]中Andersson等人認(rèn)為在一個(gè)小群體中如果某個(gè)行人沒有跟隨任何人并且在一定的時(shí)間段內(nèi)他也被一些人追隨著,那么他就可以認(rèn)為是該小群體主導(dǎo)者.文獻(xiàn)[4]Yu等人提出了基于行人距離信息的迭代模塊化聚類的方案.他們的主導(dǎo)者選擇方法是基于在距離信息圖上的中心化計(jì)算.然而,這種方法的適用性主要限于固定的場(chǎng)景.

文獻(xiàn)[5]中Carmi等人提出了一個(gè)更復(fù)雜的方法,對(duì)小群體中的每個(gè)成員的位置和速度信息建立了貝葉斯網(wǎng)絡(luò),再通過(guò)回歸的方法計(jì)算出每個(gè)成員之間的因果關(guān)系，之后，計(jì)算出每個(gè)成員的因果關(guān)系鏈接的輸入和輸出之和,即該成員的對(duì)整個(gè)群體的集體行為的貢獻(xiàn)度.此外,文獻(xiàn)[6]中Kjaergaard等人和文獻(xiàn)[7]中Sanchez-Cortes等人完成了小群體的成員的排名任務(wù).前者建立了一個(gè)基于時(shí)間滯后的特征的有向圖,然后再運(yùn)用PageRank算法去計(jì)算每個(gè)節(jié)點(diǎn)的得分,即他們的重要性.這個(gè)時(shí)間滯后分析方法是模仿了Carmi等人提出的時(shí)空因果關(guān)系概念.然而,后者研究出了一種非語(yǔ)言特征去描述小群體的排名得分從而去確定主導(dǎo)者.

跟以往的方法不同,本文把該問題看作一種監(jiān)督學(xué)習(xí)問題,首先我們通過(guò)計(jì)算得到行人的軌跡和人群小群體的特征信息.對(duì)于沒有標(biāo)簽的樣本,分類模型的輸出將會(huì)是一個(gè)排序,這個(gè)排序即反映了小群體里面的各個(gè)行人的影響力的一個(gè)排名,影響力程度值越大,那么主導(dǎo)這個(gè)小群體的可能性就越高.

1 小群體主導(dǎo)者檢測(cè)的特征分析

1.1 行人時(shí)間滯后特征

本文中,我們把行人的軌跡看成是一個(gè)二維的時(shí)間序列,每個(gè)時(shí)刻都對(duì)應(yīng)著行人的位置信息,把小群體看成是一些相關(guān)行人的集合.我們的目的是去檢測(cè)社會(huì)小群體的主導(dǎo)者,因此我們要從這些軌跡數(shù)據(jù)信息里面提取有用的特征信息去反映行人之間主從關(guān)系.我們采用Anderson等人關(guān)于主從關(guān)系的定義,這個(gè)可以幫助我們?nèi)ザ亢饬績(jī)蓚€(gè)行人的軌跡之間的相互作用.然后對(duì)于一個(gè)小群體,我們就可以建立一個(gè)帶權(quán)重的有向圖去表示.

如圖1,我們可以看到節(jié)點(diǎn)A和節(jié)點(diǎn)B之間由兩個(gè)帶權(quán)重的有向箭頭相連,wab表示A跟隨B的權(quán)重值,wba表示B跟隨A的權(quán)重值.

圖1 小群體有向圖Figure 1 The oriented graph of small group

傳統(tǒng)的軌跡時(shí)間序列信息無(wú)法反映出行人之間的主從關(guān)系信息.為了計(jì)算主從關(guān)系權(quán)重值,我們采用Kjrgaard等人提出的時(shí)間滯后分析法進(jìn)行計(jì)算.圖2為時(shí)間滯后特征的計(jì)算過(guò)程示意圖.a和b分別表示行人a和行人b的軌跡時(shí)間序列,向量vab表示經(jīng)過(guò)計(jì)算后得到的特征向量,它的每個(gè)元素是通過(guò)相應(yīng)的時(shí)間滯后值i對(duì)軌跡做出相應(yīng)的平移,再對(duì)平移后的軌跡做計(jì)算.其中i∈[-z,…,z],這里的z表示的是軌跡時(shí)間滯后值的范圍.因此特征向量vab的長(zhǎng)度,即為2z+1,如下圖,如果i>0,那么b相對(duì)a向右平移;如果i<0,那么b相對(duì)a向左平移,所以vab的每個(gè)元素的值可表示為vab(i)=f(a,b+i),其中陰影部分為函數(shù)f的計(jì)算的軌跡有效區(qū)間.

圖2 時(shí)間滯后分析示意圖Figure 2 Schematic diagram of time-lag analysis

這里的函數(shù)f有三種計(jì)算方式,下面詳細(xì)介紹.

1)動(dòng)態(tài)時(shí)間歸整:動(dòng)態(tài)時(shí)間歸整是一個(gè)廣泛運(yùn)用于計(jì)算兩個(gè)時(shí)間序列的最優(yōu)匹配距離的經(jīng)典算法.如式(1)所示,函數(shù)dtw的返回值即為兩個(gè)時(shí)間序列的運(yùn)用動(dòng)態(tài)時(shí)間歸整算法得到的最優(yōu)匹配距離,所以軌跡a和軌跡b之間的相似度可根據(jù)式(1)計(jì)算:

vab=dtw(a,b).

(1)

2)歐式距離:歐氏距離是一個(gè)很基本的相似度衡量計(jì)算方法,已經(jīng)被廣泛運(yùn)用于各個(gè)領(lǐng)域,比如空間關(guān)系檢測(cè)[8-9].如式(2),函數(shù)ed的返回值即為兩個(gè)軌跡時(shí)間序列之間的歐式距離,所以vab的每個(gè)元素的值可以根據(jù)式(2)計(jì)算:

(2)

3)方向角距離:基于兩個(gè)二維的軌跡時(shí)間序列,我們另外構(gòu)建一個(gè)關(guān)于角度的時(shí)間序列,每個(gè)時(shí)刻的角度即為該時(shí)刻的行人的運(yùn)動(dòng)方向與水平方向的夾角.然后我們?cè)龠\(yùn)用動(dòng)態(tài)時(shí)間歸整算法去處理這兩個(gè)時(shí)間序列.如式(3),函數(shù)ang的返回值即為關(guān)于角度的時(shí)間序列,再對(duì)他們做動(dòng)態(tài)時(shí)間歸整.

vab=dtw(ang(a),ang(b)).

(3)

得到特征向量vab后就可以根據(jù)式(4)計(jì)算主從關(guān)系值F,我們計(jì)算特征向量的倒數(shù)的加權(quán)平均值來(lái)作為有向圖的權(quán)值.

(4)

根據(jù)式(4)的計(jì)算可以得到F的值,如果F>0,那么我們認(rèn)為行人a跟隨行人b;如果F<0,那么行人a就主導(dǎo)行人b.

1.2 行人位置關(guān)系特征

在The Crowd[10]一書中,Le Bon認(rèn)為人群的主導(dǎo)者能夠?yàn)槿巳禾峁┱w的方向并且促進(jìn)整體的穩(wěn)定性.因此人群的主導(dǎo)者在人群中充當(dāng)著一個(gè)向?qū)ё饔?人群中的其他成員則是根據(jù)主導(dǎo)者的意愿作出相應(yīng)的反應(yīng).所以我們認(rèn)為主導(dǎo)者應(yīng)該走在他的跟隨者的前面,跟隨者應(yīng)該走在他的主導(dǎo)者的運(yùn)動(dòng)方向的后面.

圖3 行人的位置關(guān)系Figure 3 The position relationship of pedestrians

(5)

2 結(jié)構(gòu)化學(xué)習(xí)

本文的方法是將小群體的主導(dǎo)者檢測(cè)看成是一個(gè)結(jié)構(gòu)化分類問題.在機(jī)器學(xué)習(xí)領(lǐng)域中,結(jié)構(gòu)化SVM[11]即為結(jié)構(gòu)化支持向量機(jī)(Support Vector Machine,SVM),它是一種很常見的結(jié)構(gòu)化學(xué)習(xí)方法,是對(duì)傳統(tǒng)的二分類SVM的一種擴(kuò)展.對(duì)應(yīng)樣本的類別并不是簡(jiǎn)單的屬于{-1,1},也不屬于{1,2,3,…,k},而是其他任意形式,比如說(shuō)可以為一個(gè)字符串,一個(gè)序列,一顆樹或者一個(gè)圖.本文選擇結(jié)構(gòu)化SVM主要因?yàn)樗撵`活性,用戶可以根據(jù)具體的問題去定義特定的函數(shù).

對(duì)于結(jié)構(gòu)化學(xué)習(xí)的訓(xùn)練集D={x1,x2,…,xn},它是由n個(gè)訓(xùn)練樣本構(gòu)成的,每個(gè)訓(xùn)練樣本xi是一個(gè)有向圖向量,有向圖包含了該小群體的成員,以及每個(gè)成員之間的主從關(guān)系特征值,即為該有向圖的各成員之間的權(quán)重.由第一部分內(nèi)容可知,這里的有向圖的權(quán)重是一個(gè)四維的向量.

分類的輸出是一個(gè)k維的向量,例如y={y(1),y(2),…,y(k)},這里k是該小群體成員的數(shù)目,y(j)表示該小群體的第j個(gè)成員在這個(gè)小群體的排序.

如圖4,左邊是該小群體的行人軌跡示意圖,右邊的是輸出的行人排序,即10號(hào)行人排第一,是這個(gè)小群體的主導(dǎo)者.

圖4 行人排序示意圖Figure 4 Schematic diagram of pedestrians ordering

對(duì)于結(jié)構(gòu)化SVM,我們需要定義一個(gè)輸入x和輸出y之間的兼容性函數(shù),即Feature Map,輸出的yi和真實(shí)標(biāo)簽yj之間的差距定義為損失函數(shù).

2.1 PageRank算法

由于我們表示小群體成員之間的跟隨關(guān)系用的是帶權(quán)重的有向圖的方法,因此,我們需要用一個(gè)工具去對(duì)輸入的有向圖的節(jié)點(diǎn)做一個(gè)排序.

PankRank的Page可以認(rèn)為是網(wǎng)頁(yè),表示網(wǎng)頁(yè)排名,曾是Google發(fā)家致富的法寶.PageRank算法計(jì)算每一個(gè)網(wǎng)頁(yè)的PageRank值,然后根據(jù)這個(gè)值的大小對(duì)網(wǎng)頁(yè)的重要性進(jìn)行排序.它的思想是模擬一個(gè)悠閑的上網(wǎng)者,上網(wǎng)者首先隨機(jī)選擇一個(gè)網(wǎng)頁(yè)打開,然后在這個(gè)網(wǎng)頁(yè)上呆了幾分鐘后,跳轉(zhuǎn)到該網(wǎng)頁(yè)所指向的鏈接,這樣無(wú)所事事、漫無(wú)目的地在網(wǎng)頁(yè)上跳來(lái)跳去,PageRank就是估計(jì)這個(gè)悠閑的上網(wǎng)者分布在各個(gè)網(wǎng)上的概率.

(6)

2.2 結(jié)構(gòu)化SVM

現(xiàn)在我們的結(jié)構(gòu)化學(xué)習(xí)問題的預(yù)測(cè)目標(biāo)是找到該小群體的成員的一個(gè)最優(yōu)的排序組合,并且使式(7)的判別函數(shù)得分最大.

(7)

(8)

參數(shù)w是需要通過(guò)結(jié)構(gòu)化學(xué)習(xí)來(lái)獲得.結(jié)構(gòu)化SVM同樣也是把它當(dāng)作一個(gè)最大間隔問題,如下式:

(9)

式(9)中:δψi(y)=ψ(xi,yi)-ψ(xi,y),yi是正確的排序標(biāo)簽,εi是用來(lái)容納錯(cuò)誤樣本的松弛變量,Δ(yi,y)是損失函數(shù).我們需要最大化正確的序列和錯(cuò)誤的序列之間的間隔.C是一個(gè)常量,用于平衡最大化間隔和最小化分類錯(cuò)誤.wTδψi(y)≥Δ(yi,y)-εi即為每個(gè)樣本的約束條件,所以它對(duì)應(yīng)著|Y|-1個(gè)約束條件,那么所有的樣本就有n|Y|-n個(gè)約束條件.面對(duì)如此大規(guī)模的約束條件下會(huì)導(dǎo)致高難度的計(jì)算問題.觀察公式(9)會(huì)發(fā)現(xiàn):對(duì)于任意一個(gè)約束s.t.?y∈Y(xi)yi都有n!-1種排列的可能,因此對(duì)于大量的約束問題,結(jié)構(gòu)化SVM采用了割平面算法[13]去解決此類問題.具體算法如下:

①輸入(x1,y1),(x2,y2),…,(xn,yn),C,ε

②fori=1,2,…,ndo

③Wi←φ

④end for

⑤Repeat

⑥fori=1,2,…,ndo

⑦H(y,w)=Δ(yi,y)-wTδΨi(y)

3 實(shí)驗(yàn)結(jié)果與分析

本文所有的實(shí)驗(yàn)均在MATLAB R2014a環(huán)境下進(jìn)行,電腦配置為Intel(R) Core(TM) i7-5500U CPU @2.40 GHz,內(nèi)存12.00 GB.

我們選擇的數(shù)據(jù)集是UCY計(jì)算機(jī)圖形實(shí)驗(yàn)室數(shù)據(jù)集,名為“University Student”.這段視頻序列持續(xù)4分多鐘,里面包含434個(gè)行人,有115個(gè)小群體,這里的小群體是包含兩個(gè)或兩個(gè)以上的行人的集合體.為了衡量算法的效果的好壞,我們定義了兩個(gè)指標(biāo),分別是LossAccurary和LeadAccurary,其中LossAccurary是衡量預(yù)測(cè)的成員序列的準(zhǔn)確性,LeadAccurary只考慮預(yù)測(cè)小群體主導(dǎo)者的準(zhǔn)確性.

如圖5,特征權(quán)重的柱形圖,表示的是各個(gè)特征對(duì)行人主從關(guān)系表示的貢獻(xiàn)值的權(quán)重比例.由圖5可知,行人的歐式距離特征(ed)和位置關(guān)系特征(position)的貢獻(xiàn)值非常明顯,說(shuō)明在整個(gè)結(jié)構(gòu)化學(xué)習(xí)的小群體主導(dǎo)者檢測(cè)算法中,行人的歐氏距離特征和位置關(guān)系特征扮演者很重要的角色,更能反映行人之間主從關(guān)系.

圖5 不同特征的權(quán)重Figure 5 Weight of different features

對(duì)于給定的數(shù)據(jù)集樣本,我們隨機(jī)從中抽取作為訓(xùn)練樣本,如表1,依次選取10%到50%的樣本作為訓(xùn)練集,剩下的作為測(cè)試集,此過(guò)程重復(fù)五次,然后再對(duì)兩個(gè)指標(biāo)分別取平均值.根據(jù)表1的實(shí)驗(yàn)數(shù)據(jù)可知,本文的算法相對(duì)于文獻(xiàn)[6]和傳統(tǒng)的SVM,在我們定義的兩個(gè)評(píng)價(jià)指標(biāo)LossAccurary和LeadAccurary上都有了明顯的提高,并且隨著訓(xùn)練樣本的數(shù)目的增加,三種算法的識(shí)別率也在隨著增加.如圖6,實(shí)驗(yàn)的效果圖,我們能看到被圈出的小群體以及他們的主導(dǎo)者,有原點(diǎn)標(biāo)注的行人即為該群體的主導(dǎo)者.

圖6 實(shí)驗(yàn)效果圖Figure 6 Graph of simulation experiment

表1 不同方法的LossAccurary和LeadAccurary的均值

4 結(jié) 語(yǔ)

本文中,我們運(yùn)用了結(jié)構(gòu)化學(xué)習(xí)的方法對(duì)小群體的主導(dǎo)者進(jìn)行了有效的檢測(cè).在基于行人軌跡的基礎(chǔ)上,提取了行人時(shí)間滯后特征和行人位置關(guān)系特征,再結(jié)合結(jié)構(gòu)化SVM進(jìn)行學(xué)習(xí)訓(xùn)練.實(shí)驗(yàn)結(jié)果表明，本文的算法對(duì)小群體的主導(dǎo)者檢測(cè)起到了一個(gè)很好的效果,相對(duì)于文獻(xiàn)[6]的方法和傳統(tǒng)的SVM,結(jié)構(gòu)化學(xué)習(xí)的方法對(duì)于小群體的主導(dǎo)者檢測(cè)有著很好的魯棒性.

[1] HUANG K Q, CHEN X T, KANG Y, et al. Intelligent visual surveillance: A review[J].Chinese Journal of Computer,2015,38(6):1093-1115.

[2] STEIN R T, HELLER T.An empirical analysis of the correlations between leadership status and participation rates reported in the literature[J].Journal of Personality and Social Psychology,1979,37(11):1993-2002.

[3] ANDERSSON M, GUDMUNDSSON J, LAUBE P, et al. Reporting leaders and followers among trajectories of moving point objects[J].GeoInformatica,2008,12(4):497-528.

[4] YU T, LIM S N, PATWARDHAN K, et al. KRAHNSTOEVER.Monitoring,recognizing and discovering social networks[C]//Conference on Computer Vision and Pattern Recognition. USA: IEEE Press,2009:1462-1469.[5] CARMI A, MIHAYLOVA L, SEPTIER F, et al. Mcmc-based tracking and identification of leaders in groups[C]//IEEE International Conference on Computer Vision Workshops. Barcelona: IEEE Press,2011:112-119.

[6] KJARGAARD M B, BLUNCK H, WUSTENBERG M, et al. Time-lag method for detecting following and leadership behavior of pedestrians from mobile sensing data[C]//2014 IEEE International Conference on Pervasive Computing and Communications. San Diego: IEEE Press, 2013:56-64.

[7] SANCHEZ-CORTES D, ARAN O, MAST M, et al. A nonverbal behavior approach to identify emergent leadersin small groups[J].IEEE Transactions on Multimedia,2012,14(3):816-832.

[8] KRUMM J, HINCKLEY K. The nearme wireless proximity server[J].Lecture Note in Computer Science,2004,3205:283-300.

[9] PHUNG D, ADAMS B, TRAN K, et al. High accuracy context recovery using clustering mechanisms[C]//IEEE International Conference on Pervasive Computing & Communications.[s.l.]: IEEE,2009:1-9.

[10] GUSTAVE L. The Crowd: A Study of the Popular Mind[M].New York: Macmillan,1897:734-735.

[11] TSOCHANTARIDIS I, JOACHIMS T, HOFMANN T, et al. Large margin methods for structured and interdependent output variables[J].Journal of Machine Learning Research,2005,6(2):1453-1484.

[12] PAGE L , BRIN S, MOTWANI R, et al. The pagerank citation ranking: Bringing order to the web[J].Technical report,1999,9(1):22-26.

[13] JOACHIMS T, FINLEY T, YU C N. Cutting-plane training of structural SVMs[J].Machine Learning,2009,77(1):27-59.

An leadership detection algorithm in small groups based on structural learning

ZHANG Dongping, QIAN Leyi
(College of Information Engineering, China Jiliang University, Hangzhou 310018, China)

Crowd analysis is an interesting theme in pattern recognition and machine learning. In particular, the opportunity of leadership detection in small groups opens up to new perspectives in video surveillance and other computer vision fields. Meanwhile, leadership detection in small groups is also an important part of crowd analysis. In this paper, we proposed a structural SVM learning framework and a new feature model based on pedestrians, position analysis and time-lag analysis. Results show that the method is effective in the dataset of crowd analysis.

crowd analysis; leader identification; time-lag analysis; structural SVM

2096-2835(2017)01-0057-06

10.3969/j.issn.2096-2835.2017.01.010

2016-12-18 《中國(guó)計(jì)量大學(xué)學(xué)報(bào)》網(wǎng)址：zgjl.cbpt.cnki.net

浙江省自然科學(xué)基金資助項(xiàng)目(No.LY15F020021),浙江省公益性項(xiàng)目(No.2016C31079).

章東平(1970- ),男,江西省鄱陽(yáng)人,教授,主要研究方向?yàn)闄C(jī)器學(xué)習(xí).E-mail:silenttree_zju@cjlu.edu.cn

TP391

A