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

章東平,錢樂義

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

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

章東平,錢樂義

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

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

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

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

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

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

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

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

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

1.1 行人時間滯后特征

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

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

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

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

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

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

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

vab=dtw(a,b).

(1)

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

(2)

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

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

(3)

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

(4)

根據(jù)式(4)的計算可以得到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)者能夠為人群提供整體的方向并且促進(jìn)整體的穩(wěn)定性.因此人群的主導(dǎo)者在人群中充當(dāng)著一個向?qū)ё饔?人群中的其他成員則是根據(jù)主導(dǎo)者的意愿作出相應(yīng)的反應(yīng).所以我們認(rèn)為主導(dǎo)者應(yīng)該走在他的跟隨者的前面,跟隨者應(yīng)該走在他的主導(dǎo)者的運動方向的后面.

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

(5)

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

本文的方法是將小群體的主導(dǎo)者檢測看成是一個結(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í)方法,是對傳統(tǒng)的二分類SVM的一種擴(kuò)展.對應(yīng)樣本的類別并不是簡單的屬于{-1,1},也不屬于{1,2,3,…,k},而是其他任意形式,比如說可以為一個字符串,一個序列,一顆樹或者一個圖.本文選擇結(jié)構(gòu)化SVM主要因為它的靈活性,用戶可以根據(jù)具體的問題去定義特定的函數(shù).

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

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

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

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

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

2.1 PageRank算法

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

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

(6)

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

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

(7)

(8)

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

(9)

式(9)中:δψi(y)=ψ(xi,yi)-ψ(xi,y),yi是正確的排序標(biāo)簽,εi是用來容納錯誤樣本的松弛變量,Δ(yi,y)是損失函數(shù).我們需要最大化正確的序列和錯誤的序列之間的間隔.C是一個常量,用于平衡最大化間隔和最小化分類錯誤.wTδψi(y)≥Δ(yi,y)-εi即為每個樣本的約束條件,所以它對應(yīng)著|Y|-1個約束條件,那么所有的樣本就有n|Y|-n個約束條件.面對如此大規(guī)模的約束條件下會導(dǎo)致高難度的計算問題.觀察公式(9)會發(fā)現(xiàn):對于任意一個約束s.t.?y∈Y(xi)yi都有n!-1種排列的可能,因此對于大量的約束問題,結(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 實驗結(jié)果與分析

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

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

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

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

圖6 實驗效果圖Figure 6 Graph of simulation experiment

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

4 結(jié) 語

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

[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 《中國計量大學(xué)學(xué)報》網(wǎng)址：zgjl.cbpt.cnki.net

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

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

TP391

A