基于结构化学习的小群体主导者检测方法

章东平,钱乐义

(中国计量大学 信息工程学院,浙江 杭州 310018)

基于结构化学习的小群体主导者检测方法

章东平,钱乐义

(中国计量大学 信息工程学院,浙江 杭州 310018)

人群分析在模式识别和机器学习领域内是一个非常有趣的课题.人群小群体成员之间的主从关系检测为视频监控和计算机视觉领域打开了新的视野.同时,小群体主导者的检测也是人群分析的重要组成部分.文章提出一种结构化SVM的学习框架,并结合行人的时间滞后分析特征和行人位置关系特征对小群体主导者进行预测.实验结果表明,本方法在人群分析数据集下取得了很好识别效果.

人群分析;主导者检测;时间滞后分析;结构化SVM

随着智能视频监控技术[1]的发展,过去的几年里,人们对于人群场景下的行人行为的分析和理解的兴趣越来越高.小群体的主导者检测有利于人们对视频监控系统下人群分析和安全问题的场景理解和宏观的认识.然而,小群体的主导者检测是一个热门的并且未彻底解决的问题.

精确检测出人群场景里的小群体主导者对公共安全非常有利.在高密度的人群场景下,比如示威游行或者体育活动,安保人员就可以侧重关注人群里面的主导者,而不是分析整个人群的行为.此外,在封闭的环境里面,比如监狱,小群体的主导者检测技术将非常有利于去识别监狱里面最有影响力的囚犯.

近几年来,研究者对人群分析进行了大量的研究,但是对于小群体的主导者检测的研究比较少.文献[2]中提到,在一个团队中,主导者在这个团队中是一个拥有着权利和地位的一个角色,团队里面的其他成员的工作内容和方向都是由主导者决定的.在两个成员或两个以上的团队里,就每两个成员之间的关系而言,主导者对其他成员的影响力超过了团队里面其他任何一个成员.文献[3]中Andersson等人认为在一个小群体中如果某个行人没有跟随任何人并且在一定的时间段内他也被一些人追随着,那么他就可以认为是该小群体主导者.文献[4]Yu等人提出了基于行人距离信息的迭代模块化聚类的方案.他们的主导者选择方法是基于在距离信息图上的中心化计算.然而,这种方法的适用性主要限于固定的场景.

文献[5]中Carmi等人提出了一个更复杂的方法,对小群体中的每个成员的位置和速度信息建立了贝叶斯网络,再通过回归的方法计算出每个成员之间的因果关系，之后，计算出每个成员的因果关系链接的输入和输出之和,即该成员的对整个群体的集体行为的贡献度.此外,文献[6]中Kjaergaard等人和文献[7]中Sanchez-Cortes等人完成了小群体的成员的排名任务.前者建立了一个基于时间滞后的特征的有向图,然后再运用PageRank算法去计算每个节点的得分,即他们的重要性.这个时间滞后分析方法是模仿了Carmi等人提出的时空因果关系概念.然而,后者研究出了一种非语言特征去描述小群体的排名得分从而去确定主导者.

跟以往的方法不同,本文把该问题看作一种监督学习问题,首先我们通过计算得到行人的轨迹和人群小群体的特征信息.对于没有标签的样本,分类模型的输出将会是一个排序,这个排序即反映了小群体里面的各个行人的影响力的一个排名,影响力程度值越大,那么主导这个小群体的可能性就越高.

1 小群体主导者检测的特征分析

1.1 行人时间滞后特征

本文中,我们把行人的轨迹看成是一个二维的时间序列,每个时刻都对应着行人的位置信息,把小群体看成是一些相关行人的集合.我们的目的是去检测社会小群体的主导者,因此我们要从这些轨迹数据信息里面提取有用的特征信息去反映行人之间主从关系.我们采用Anderson等人关于主从关系的定义,这个可以帮助我们去定量衡量两个行人的轨迹之间的相互作用.然后对于一个小群体,我们就可以建立一个带权重的有向图去表示.

如图1,我们可以看到节点A和节点B之间由两个带权重的有向箭头相连,wab表示A跟随B的权重值,wba表示B跟随A的权重值.

图1 小群体有向图Figure 1 The oriented graph of small group

传统的轨迹时间序列信息无法反映出行人之间的主从关系信息.为了计算主从关系权重值,我们采用Kjrgaard等人提出的时间滞后分析法进行计算.图2为时间滞后特征的计算过程示意图.a和b分别表示行人a和行人b的轨迹时间序列,向量vab表示经过计算后得到的特征向量,它的每个元素是通过相应的时间滞后值i对轨迹做出相应的平移,再对平移后的轨迹做计算.其中i∈[-z,…,z],这里的z表示的是轨迹时间滞后值的范围.因此特征向量vab的长度,即为2z+1,如下图,如果i>0,那么b相对a向右平移;如果i<0,那么b相对a向左平移,所以vab的每个元素的值可表示为vab(i)=f(a,b+i),其中阴影部分为函数f的计算的轨迹有效区间.

图2 时间滞后分析示意图Figure 2 Schematic diagram of time-lag analysis

这里的函数f有三种计算方式,下面详细介绍.

1)动态时间归整:动态时间归整是一个广泛运用于计算两个时间序列的最优匹配距离的经典算法.如式(1)所示,函数dtw的返回值即为两个时间序列的运用动态时间归整算法得到的最优匹配距离,所以轨迹a和轨迹b之间的相似度可根据式(1)计算:

vab=dtw(a,b).

(1)

2)欧式距离:欧氏距离是一个很基本的相似度衡量计算方法,已经被广泛运用于各个领域,比如空间关系检测[8-9].如式(2),函数ed的返回值即为两个轨迹时间序列之间的欧式距离,所以vab的每个元素的值可以根据式(2)计算:

(2)

3)方向角距离:基于两个二维的轨迹时间序列,我们另外构建一个关于角度的时间序列,每个时刻的角度即为该时刻的行人的运动方向与水平方向的夹角.然后我们再运用动态时间归整算法去处理这两个时间序列.如式(3),函数ang的返回值即为关于角度的时间序列,再对他们做动态时间归整.

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

(3)

得到特征向量vab后就可以根据式(4)计算主从关系值F,我们计算特征向量的倒数的加权平均值来作为有向图的权值.

(4)

根据式(4)的计算可以得到F的值,如果F>0,那么我们认为行人a跟随行人b;如果F<0,那么行人a就主导行人b.

1.2 行人位置关系特征

在The Crowd[10]一书中,Le Bon认为人群的主导者能够为人群提供整体的方向并且促进整体的稳定性.因此人群的主导者在人群中充当着一个向导作用,人群中的其他成员则是根据主导者的意愿作出相应的反应.所以我们认为主导者应该走在他的跟随者的前面,跟随者应该走在他的主导者的运动方向的后面.

图3 行人的位置关系Figure 3 The position relationship of pedestrians

(5)

2 结构化学习

本文的方法是将小群体的主导者检测看成是一个结构化分类问题.在机器学习领域中,结构化SVM[11]即为结构化支持向量机(Support Vector Machine,SVM),它是一种很常见的结构化学习方法,是对传统的二分类SVM的一种扩展.对应样本的类别并不是简单的属于{-1,1},也不属于{1,2,3,…,k},而是其他任意形式,比如说可以为一个字符串,一个序列,一颗树或者一个图.本文选择结构化SVM主要因为它的灵活性,用户可以根据具体的问题去定义特定的函数.

对于结构化学习的训练集D={x1,x2,…,xn},它是由n个训练样本构成的,每个训练样本xi是一个有向图向量,有向图包含了该小群体的成员,以及每个成员之间的主从关系特征值,即为该有向图的各成员之间的权重.由第一部分内容可知,这里的有向图的权重是一个四维的向量.

分类的输出是一个k维的向量,例如y={y(1),y(2),…,y(k)},这里k是该小群体成员的数目,y(j)表示该小群体的第j个成员在这个小群体的排序.

如图4,左边是该小群体的行人轨迹示意图,右边的是输出的行人排序,即10号行人排第一,是这个小群体的主导者.

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

对于结构化SVM,我们需要定义一个输入x和输出y之间的兼容性函数,即Feature Map,输出的yi和真实标签yj之间的差距定义为损失函数.

2.1 PageRank算法

由于我们表示小群体成员之间的跟随关系用的是带权重的有向图的方法,因此,我们需要用一个工具去对输入的有向图的节点做一个排序.

PankRank的Page可以认为是网页,表示网页排名,曾是Google发家致富的法宝.PageRank算法计算每一个网页的PageRank值,然后根据这个值的大小对网页的重要性进行排序.它的思想是模拟一个悠闲的上网者,上网者首先随机选择一个网页打开,然后在这个网页上呆了几分钟后,跳转到该网页所指向的链接,这样无所事事、漫无目的地在网页上跳来跳去,PageRank就是估计这个悠闲的上网者分布在各个网上的概率.

(6)

2.2 结构化SVM

现在我们的结构化学习问题的预测目标是找到该小群体的成员的一个最优的排序组合,并且使式(7)的判别函数得分最大.

(7)

(8)

参数w是需要通过结构化学习来获得.结构化SVM同样也是把它当作一个最大间隔问题,如下式:

(9)

式(9)中:δψi(y)=ψ(xi,yi)-ψ(xi,y),yi是正确的排序标签,εi是用来容纳错误样本的松弛变量,Δ(yi,y)是损失函数.我们需要最大化正确的序列和错误的序列之间的间隔.C是一个常量,用于平衡最大化间隔和最小化分类错误.wTδψi(y)≥Δ(yi,y)-εi即为每个样本的约束条件,所以它对应着|Y|-1个约束条件,那么所有的样本就有n|Y|-n个约束条件.面对如此大规模的约束条件下会导致高难度的计算问题.观察公式(9)会发现:对于任意一个约束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环境下进行,电脑配置为Intel(R) Core(TM) i7-5500U CPU @2.40 GHz,内存12.00 GB.

我们选择的数据集是UCY计算机图形实验室数据集,名为“University Student”.这段视频序列持续4分多钟,里面包含434个行人,有115个小群体,这里的小群体是包含两个或两个以上的行人的集合体.为了衡量算法的效果的好坏,我们定义了两个指标,分别是LossAccurary和LeadAccurary,其中LossAccurary是衡量预测的成员序列的准确性,LeadAccurary只考虑预测小群体主导者的准确性.

如图5,特征权重的柱形图,表示的是各个特征对行人主从关系表示的贡献值的权重比例.由图5可知,行人的欧式距离特征(ed)和位置关系特征(position)的贡献值非常明显,说明在整个结构化学习的小群体主导者检测算法中,行人的欧氏距离特征和位置关系特征扮演者很重要的角色,更能反映行人之间主从关系.

图5 不同特征的权重Figure 5 Weight of different features

对于给定的数据集样本,我们随机从中抽取作为训练样本,如表1,依次选取10%到50%的样本作为训练集,剩下的作为测试集,此过程重复五次,然后再对两个指标分别取平均值.根据表1的实验数据可知,本文的算法相对于文献[6]和传统的SVM,在我们定义的两个评价指标LossAccurary和LeadAccurary上都有了明显的提高,并且随着训练样本的数目的增加,三种算法的识别率也在随着增加.如图6,实验的效果图,我们能看到被圈出的小群体以及他们的主导者,有原点标注的行人即为该群体的主导者.

图6 实验效果图Figure 6 Graph of simulation experiment

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

4 结 语

本文中,我们运用了结构化学习的方法对小群体的主导者进行了有效的检测.在基于行人轨迹的基础上,提取了行人时间滞后特征和行人位置关系特征,再结合结构化SVM进行学习训练.实验结果表明，本文的算法对小群体的主导者检测起到了一个很好的效果,相对于文献[6]的方法和传统的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 《中国计量大学学报》网址：zgjl.cbpt.cnki.net

浙江省自然科学基金资助项目(No.LY15F020021),浙江省公益性项目(No.2016C31079).

章东平(1970- ),男,江西省鄱阳人,教授,主要研究方向为机器学习.E-mail:silenttree_zju@cjlu.edu.cn

TP391

A