章東平,錢樂義

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

基于結構化學習的小群體主導者檢測方法

章東平,錢樂義

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

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

人群分析;主導者檢測;時間滯后分析;結構化SVM

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

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

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

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

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

1 小群體主導者檢測的特征分析

1.1 行人時間滯后特征

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

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

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

傳統(tǒng)的軌跡時間序列信息無法反映出行人之間的主從關系信息.為了計算主從關系權重值,我們采用Kjrgaard等人提出的時間滯后分析法進行計算.圖2為時間滯后特征的計算過程示意圖.a和b分別表示行人a和行人b的軌跡時間序列,向量vab表示經(jīng)過計算后得到的特征向量,它的每個元素是通過相應的時間滯后值i對軌跡做出相應的平移,再對平移后的軌跡做計算.其中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有三種計算方式,下面詳細介紹.

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)被廣泛運用于各個領域,比如空間關系檢測[8-9].如式(2),函數(shù)ed的返回值即為兩個軌跡時間序列之間的歐式距離,所以vab的每個元素的值可以根據(jù)式(2)計算:

(2)

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

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

(3)

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

(4)

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

1.2 行人位置關系特征

在The Crowd[10]一書中,Le Bon認為人群的主導者能夠為人群提供整體的方向并且促進整體的穩(wěn)定性.因此人群的主導者在人群中充當著一個向導作用,人群中的其他成員則是根據(jù)主導者的意愿作出相應的反應.所以我們認為主導者應該走在他的跟隨者的前面,跟隨者應該走在他的主導者的運動方向的后面.

圖3 行人的位置關系Figure 3 The position relationship of pedestrians

(5)

2 結構化學習

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

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

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

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

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

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

2.1 PageRank算法

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

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

(6)

2.2 結構化SVM

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

(7)

(8)

參數(shù)w是需要通過結構化學習來獲得.結構化SVM同樣也是把它當作一個最大間隔問題,如下式:

(9)

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

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

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

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

圖5 不同特征的權重Figure 5 Weight of different features

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

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

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

4 結 語

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

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

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

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

TP391

A