CrowdTracker一种基于移动群智感知的目标跟踪方法

景 瑶 郭 斌 陈荟慧 岳超刚 王 柱 於志文

(西北工业大学计算机学院 西安 710072)

面向目标跟踪问题提出一种基于移动群智感知的解决方案CrowdTracker.不同于基于视频监控的目标跟踪方法,通过基于群智的多人协作拍照方式实现对移动目标的轨迹预测和跟踪,其优化目标为在保证准确实时地对目标进行跟踪的同时尽可能地减少用户激励的成本(假设激励与完成任务的参与者人数和参与者完成任务所移动的距离成正比).为实现该目标,提出了目标移动性预测的方法MPRE和任务分配的方法T-centric,P-centric.T-centric是以任务为中心的参与者选择方法,而P-centric是以人为中心的任务选择方法.MPRE通过分析大量的车辆历史轨迹建立城市里车辆的移动模型以预测目标下一步的位置.在预测的区域内通过T-centric或P-centric方法进行跟踪任务分配.通过一个大规模的真实数据集对移动性预测方法MPRE和2种任务分配算法进行实验评估,实验结果表明:CrowdTracker能有效地在实现目标实时跟踪的同时降低激励成本.

关键词 移动群智感知;拍照;目标跟踪;目标移动性预测;任务分配

一直以来,公共安全问题是城市生活面临的一大挑战,移动目标跟踪技术作为公共安全领域中的一项重要技术更是研究者们关注的热门课题.城市发生突发状况后,政府和警察常常通过各种数据来追踪可疑车辆和人,其中视频监控是最常用的数据.现有的对于移动目标跟踪的研究主要基于网络视频监控数据方式[1-2].该类研究主要针对如何部署摄像头达到最大化道路覆盖以及基于图像的运动目标检测算法设计.这种基于网络视频监控的方法需要预先在广泛的城市区域内部署大量的摄像头,设备成本高且覆盖范围有限.随着可内嵌多种传感器的智能手机的快速普及和应用,移动群智感知技术[3]作为一种新的感知模式逐步发展起来,它依赖大量普通用户的移动设备及其具备的丰富的感知能力来完成大规模、复杂的城市与社会感知任务[4-5].大量的用户通过智能手机随时随地感知着城市生活的韵律,这为解决城市生活中的公共安全问题带来了新的思路.人们可以随时随地使用智能手机拍摄视频、照片,并在一定法律约束范围内作为证据使用.如果将人们手中的智能手机看做移动的监控摄像头,那么这就可以实现一种新的基于群智感知的视频监控系统.

基于该思路,本文面向目标跟踪问题提出一种基于移动群智感知的解决方案CrowdTracker:通过多人协作拍照方式实现对移动目标的轨迹预测和跟踪.本文主要针对移动目标中的车辆进行群智跟踪.CrowdTracker的示例如图1所示.城市发生公共安全事件后,警察和政府在CrowdTracker平台上发布待跟踪的目标车辆信息,包括车辆颜色、型号、车牌号码等.CrowdTracker平台上的用户A在网格区域n1内发现目标车辆,对该车辆拍照并上传照片信息以及位置信息,启动对该目标的跟踪任务.CrowdTracker服务器端通过分析城市中大量的车辆轨迹数据,预测出该目标车辆下一步可能往区域n2移动,并提前在n2内通知平台参与者等待目标出现.当参与者BC再次发现目标时同样进行拍照并上传信息,如此循环,得到目标车辆出现过的网格序列n1-n2-n3-n4即为车辆的移动轨迹,最终实现基于群智感知的移动目标跟踪.

Fig. 1 A scenario of CrowdTracker
图1 CrowdTracker示例

为了实现这个目标,本文提出了预测目标移动模型的方法MPRE(movement prediction)和任务分配的方法T-centric,P-centric.MPRE首先通过分析大量的车辆历史轨迹建立城市里车辆位置的移动概率模型.当目标出现在城市某位置时,通过该移动模型找到目标下一步移动概率最大的位置区域,进而在该区域内预先安排参与者.本文提出的T-centric和P-centric方法以实现在跟踪任务下的参与者优选和任务地点优选,要求达到参与者与任务地点最佳匹配,使参与者能在一定时间约束内到达指定任务点的同时,所移动的距离最短,激励成本最少.T-centric是以任务为中心的参与者选择方法,而P-centric是以人为中心的任务选择方法.本文通过成都市二环内1个月的出租车轨迹数据集对以上3种算法进行实验评估,实验结果表明,本文提出的CrowdTracker能有效地实现目标实时跟踪.

1 相关工作

目前常用的目标跟踪方法主要是通过预先部署的网络视频监控系统进行[1-2].现有的技术主要针对如何部署摄像头达到最大化道路覆盖、如何调用摄像头来追踪目标以及基于图像的目标检测算法设计等[6-8].与传统的预先部署固定的网络视频监控系统不同的是,本文旨在利用群智的思想将人们手中智能手机的摄像头看作移动的监控摄像头,提出基于群智的多人协作拍照的方式对移动目标进行实时跟踪.下面就本文的相关工作进行介绍.

1.1 移动群智感知

基于移动群智感知的工作包括数据采集、管理、分析到最终提供服务等.移动群智感知的数据包括2种产生方式:移动群智感知和移动社交网络数据.移动群智感知就是利用人们手中的智能手机感知周边的信息.比如“哥本哈根车轮”项目在自行车车轮里安装一些传感器,并通过用户手机将收集的数据发送至后台服务器,这样依靠群体的力量就可以感知整个城市不同角落的温度、湿度和CO2浓度;利用手机拍照发现城市中被污染的河流[9]、损坏的建筑物[10]、感知生活中的社会热点事件[11]、帮助城市进行灾难救援等[12].与本文工作不同的是,这些感知任务主要关注静态的目标.CrowdTracker是利用多人协作拍照的方式对移动目标进行实时跟踪,需要对群智参与者的行为进行时间约束,在时间序列下,多个参与者完成拍照任务的位置序列即为目标的移动轨迹.

1.2 移动轨迹预测

CrowdTracker旨在保证准确实时地对目标进行跟踪的同时尽可能地减少用户激励的成本.减少激励成本首先要缩小跟踪任务的范围,减少参与者数量.因此需要通过目标的当前位置信息,预测目标下一步的移动模型.现有的很多研究通过分析城市车辆的轨迹数据挖掘车辆移动的规律,预测车辆行驶的目的地.Xu等人[13]用纯数据驱动的方式分析城市车辆的轨迹数据进行目的地预测.与本文工作不同的是,文献[13]研究的是长距离的最终目的地预测,本文的移动预测旨在通过目标上一状态预测下一时刻位置状态.Xue等人[14]和Gambs等人[15]用基于概率模型的Markov链进行下一站预测.Xue等人[14]将轨迹序列网格化的思想也为本文工作提供了思路.

1.3 群智感知任务分配

任务分配是移动群智感知的关键挑战之一,如何进行任务分配对数据采集的全面性、任务完成率和数据采集质量等都具有重要影响.面向移动群智感知的参与者选择是以物理空间位置为基础进行选择,任务的类型分为单个群智感知任务和多个并发感知任务2种.在单任务分配问题中,Papadias等人[16]研究在已知给定集合点的情况下,寻找其他的点使其到给定集合点的距离最小;Reddy等人[17]主要研究在考虑空间位置、时间要求以及参与者行为习惯的情况下,选择出合适的参与者完成任务;Cardone等人[18]考虑在参与者个数一定的情况下,最大限度地提高感知任务的空间覆盖范围.Li等人[19]研究团队形成问题,即寻找一个有特定技能的专家小组,每个人完成一个给定的任务,同时最小化团队之间的交流成本.Liu等人[20]研究了移动群智感知中面向多任务并发的参与者选择问题,不同于其他参与者选择问题,该文选择出的参与者不再局限于只能完成1个任务,参与者可以在规定时间内尽可能的完成多个任务,由此降低群智平台的成本.

本文提出的CrowdTracker首先对目标下一步的移动进行预测,然后在预测的区域内进行跟踪任务分配.在该区域内的每一个任务点的任务是同时进行且有时间限制的,每个参与者只能在规定的时间内在1个任务点等待目标的出现.因此,本文的任务分配是一个并发的单任务分配问题.针对该问题,CrowdTracker提出了T-centric和P-centric方法实现在跟踪任务下的参与者优选和任务地点优选,使参与者能在一定时间约束内到达指定任务点的同时所移动的距离最短.

2 CrowdTracker系统框架

CrowdTracker的系统框架如图2所示,主要包括客户端APP和服务器端2部分.客户端APP主要用于任务启动者和任务执行者采集数据.服务器端对客户端上传的数据进行一系列分析处理后通知被选择的参与者并给出下一步任务执行的指示,保证跟踪任务的持续执行.

Fig. 2 The framework of CrowdTracker
图2 CrowdTracker系统框架

图2中的数据采集模块展示了使用客户端进行数据采集的基本流程.城市发生共公共安全事件后,警察和政府在CrowdTracker平台上发布待跟踪的目标车辆信息,包括车辆的颜色、型号和车牌号码等.CrowdTracker平台上的用户在城市某一位置发现目标,立即对其拍摄1张照片用pic来表示.pic中保存了用户拍照时刻的图像、GPS位置坐标和时间戳等信息,用一个五元组(id,img,lon,lat,t)表示.id是拍照用户的唯一标识,img代表图像信息,lonlat分别表示用户当前位置的经纬度,也代表了目标当前的位置信息,t表示拍照时间.上传该五元组信息至服务器端,启动该目标的跟踪任务.服务器对客户端发起的任务请求分析处理后,给出该跟踪任务下一步的计划,并通知CrowdTracker平台上被选中执行下一步任务的参与者.参与者按照任务指示在一定的时间内到达指定任务地点,等待目标出现,在一定时间内发现目标后对目标进行拍照并再次上传信息,完成该步跟踪任务.

具体地,CrowdTracker群智跟踪方法的详细内容将在第4节进行介绍.

3 群智跟踪方法实现

图2中的群智跟踪方法模块展示了服务器端对客户端上传的数据进行分析的基本流程.该模块主要分为3个部分:目标车辆移动预测模型、群智跟踪任务分配以及最终的任务推送.

3.1 预测目标车辆移动模型

客户端上传数据中的经纬度信息代表了目标当前的位置.基于该位置信息,预测目标下一步的移动,进而有针对性地在预测的区域内进行跟踪任务分配,准确跟踪目标的同时减少平台的激励成本.

城市中车辆的移动看似杂乱无序,实则存在潜在的模式.例如上班高峰期的车辆大都由住宅区流向商业区,而下班高峰期的车辆大都由商业区流向住宅区.这种规律对于预测车辆的移动模型具有一定的意义.本文提出了基于移动Markov链(mobility Markov chain, MMC)的MPRE方法来预测车辆移动.Markov链是数学中具有Markov性质的离散时间随机过程.在该过程中,在给定当前知识或信息的情况下,过去(即当前以前的历史状态)对于预测将来(即当前以后的未来状态)是无关的.X1,X2,…描述了Markov链中的一种状态序列,Xn的值表示在时刻n的状态,如果Xn+1对于过去状态的条件概率分布仅是Xn的一个函数,则Xn+1时刻的状态见式(1):

P(Xn+1=x|X1=x1,X2=x2,…,Xn=xn)=
P(Xn+1=x|Xn=xn).

(1)

移动Markov链是模型化地将用户或者车辆等的移动行为转化为一系列离散随机过程,如图3所示,也就是Markov链中的状态序列{n1,n2,…},每个状态节点对应一个位置区域.由Markov性质可得,从一个状态ni到另一个状态nj的转移概率Pi j是条件概率,只取决于状态ni.利用MMC进行下一状态预测时,重要的是获取转移矩阵的参数,也就是不同位置状态间的移动概率Pi j,式(2)中Ni表示所有包含节点ni的轨迹数目,Ni,j表示从节点ninj的轨迹数目.Ni,jNi的商即为转移概率Pi j的值.

.

(2)

Fig. 3 Mobility Markov chain
图3 移动Markov链模型

具体地,基于MMC的思想,本文提出MPRE的方法对车辆的移动进行预测.在进行MPRE之前首先对城市区域进行网格化处理,如图4所示:

Fig. 4 Grid on the example
图4 城市区域网格化

将城市区域分为大小为g×g(单位m2)的单元格,每个单元格ni代表MMC中的一个位置状态.进一步,为了更好地发现城市中车辆的移动规律,构建MMC中各个位置状态之间的转移概率矩阵,本文对大量的原始车辆轨迹序列进行网格化处理.车辆的原始轨迹信息由一系列时间连续的GPS点形成,对这些轨迹信息进行网格化即判断每一个GPS点属于哪一个网格区域,若连续时间的GPS点序列在同一网格位置,则记为1个网格位置.最终,网格序列即为轨迹序列Gi={n1,n2,…}.大量轨迹进行网格化后得到轨迹序列集合G={G1,G2,…}.同样地,当目标出现在城市某位置时,将经纬度数据转化为网格位置ni.车辆轨迹序列集合G和目标位置ni作为MPRE的输入.MPRE算法具体流程见算法1.

算法1. MPRE.

输入:轨迹序列集合G、目标位置ni

输出:Pmax对应的位置点nj.

① 基于式(2),从G中学习出各个位置状态间的转移矩阵P

② 逐行搜索矩阵P,定位到目标位置ni

③ 在ni对应的行里,查找出转移概率最大的Pmax对应的下一步位置nj

④ 输出Pmax对应的位置点nj,即为目标下一步可能移动的位置;

⑤ 结束.

MPRE通过分析大量的车辆历史轨迹序列计算出城市各个位置间的的转移概率,迁出位置间的转移概率矩阵P=(Pi j).如图4所示,当目标出现在城市某位置n5时,搜索矩阵P,找到目标下一步移动概率最大P56对应的位置区域n6,即为目标下一步可能移动的位置,进而在该区域内预先安排参与者.

3.2 群智跟踪任务分配方法

通过预测车辆移动模块中的MPRE方法确定出目标下一步移动的位置范围,在该区域内预先安排参与者.每一个区域内都有多条路,且1条路覆盖一定的范围,如何在1条路上进行任务地点选择是首先需要思考的问题.分析路网的拓扑结构,路网是由多条路连接形成,而每条路是由路网节点(起始点、终止点)连接形成,路网节点就是形成整个道路网络的关键位置.因此,本文考虑将OpenStreetMap路网数据中的节点数据作为1条路上的任务点,达到最大化道路覆盖.在此基础上,本文提出T-centric和P-centric方法以实现在跟踪任务下的参与者优选和任务地点优选,使参与者能在一定时间约束内到达指定任务点的同时所移动的距离最短.T-centric是以任务为中心的参与者选择方法,而P-centric是以人为中心的任务选择方法.

对于每一步跟踪任务T,即1个网格内的任务分配问题定义如下:城市网格化的步长为g(单位m),每个g×g(单位m2)的网格内的路网节点数量为s,则设定s个并发任务T={t1,t2,…,ts}.每个任务ti需要1个人来完成,任务的位置为lti,每个网格的候选者集合C={c1,c2,…,cj,…},候选者的位置为lci.ui表示完成任务ti的参与者,完成任务ti的参与者ui需要移动的距离为di(见式(3)),完成1步跟踪任务T,所有参与者所移动的总距离为DT.假设每个用户移动平均速度为Vu(单位mmin),城市中车辆移动的平均速度为Vc(单位mmin).该问题的目标函数是安排参与者与任务的最佳匹配,使参与者能在一定时间约束内(目标进入网格区域之前)到达指定任务点的同时所移动的距离di最短,即所有参与者移动的总距离DT最短(见式(4)),时间约束见式(5).具体地,针对该任务分配问题,考虑系统的2个核心要素任务和人,分别提出以任务为中心的参与者选择方法T-centric和以人为中心的任务选择方法P-centric.

di=|lti-lci|,

(3)

(4)

满足

.

(5)

3.2.1 T-centric任务分配算法

T-centric是以任务为中心的参与者选择方法,采用贪心启发算法的思想.首先在任务集合T中随机选择1个任务作为初始任务,然后从侯选者集合C中选出满足时间约束的参与者集合.若该参与者集合为空,则表明没有能够完成该任务的参与者;若不为空,则存在能够完成该任务的参与者,进一步在该参与者集合中选出与任务点距离最短的参与者,形成1个参与者与任务点的最佳匹配.在原任务集合以及候选参与者集合中剔除掉已经形成匹配的参与者和任务,接着对下一个任务进行参与者选择,以此类推,按照该方法,直到任务集合中的每一个任务都找到1个最佳的参与者.详见算法2.

算法2. T-centric.

输入:任务集合T、候选参与者集合C

输出:能被覆盖的任务点集合t以及相应的参与者集合u.

① 随机选取初始任务ti

C中能在(单位min)内到达该任务点的参与者集合ui.={ui1,ui2,…};

③ 若集合ui.为空,则该任务点无法被覆盖;若|ui.|≥1,则在该集合中选择离任务距离最近的参与者ui覆盖该任务点;

④ 在任务集合T中剔除ti,在参与者集合C中剔除ui对应的ci

⑤ 在剩余任务集合中随机选取任务ti+1

⑥ 循环执行②~⑤步,直至所有任务执行完;

⑦ 输出能被覆盖的所有任务点ti以及相应的参与者ui

⑧ 结束.

3.2.2 P-centric任务分配算法

P-centric是以人为中心的任务选择方法.首先在候选参与者集合C中随机选择1个参与者,然后从任务集合T中选择出该参与者能在一定时间约束内到达的任务集合.若该任务集合为空,则表明该参与者没有能力完成任何一个任务;若不为空,则存在能够完成的任务,进一步在该任务集合中选出与参与者距离最短的任务,形成1个参与者与任务点的最佳匹配.在原任务集合以及候选参与者集合中剔除掉已经形成匹配的参与者和任务,接着对下一个参与者进行任务选择,以此类推,按照该方法,直到对于参与者集合中的每一个人都找到最佳的任务点,详见算法3.

算法3. P-centric.

输入:任务集合T、候选参与者集合C

输出:能被覆盖的任务点集合t以及相应的参与者集合c.

① 随机选取候选参与者集合C中的1个ci

② 选择参与者ci能在(单位min)内到达的任务集合ti.={ti1,ti2,…};

③ 若集合ti.为空,则该用户无法覆盖任何任务点;若|ti.|≥1,则在该集合中选择离参与者距离最近的任务点ti去完成;

④ 在候选参与者集合中剔除ci,在任务集合T中剔除ti

⑤ 在剩余的候选参与者集合中随机选取参与者ci+1

⑥ 循环执行②~⑤步,直至所有任务执行完;

⑦ 输出能被覆盖的所有任务点ti以及相应的参与者ci

⑧ 结束.

4 实验评估

本文提出的基于群智的多人协作拍照方式实现对移动目标的实时跟踪,旨在保证准确实时地对目标进行跟踪的同时尽可能地减少用户激励的成本.为了实现这个目标,提出了预测目标移动模型的方法MPRE和任务分配的方法T-centric和P-centric.本节分别对每一个方法进行实验验证.

4.1 MPRE方法评估

为了验证MPRE方法的精度,本文对成都市的出租车轨迹数据进行了分析.表1展示了实验数据集的基本统计信息.本文选取了1个月内成都市二环内13 605辆出租车从6点到23点的GPS点序列.原始数据中包含车辆ID、经纬度、载客状态(1表示载客,0表示空车)以及时间戳信息.根据原始轨迹数据中车辆载客状态的变化,将每辆车1天内连续的GPS点分割为多条轨迹.当车辆状态由0变为1则表明一条轨迹的开始,车辆状态由1变为0则表明这条轨迹结束.将城市区域分为大小为g×g(单位m2)的单元格,对每一条原始车辆轨迹进行网格化,总共有大约4 010 960条轨迹,其中104条轨迹用于测试集,其余用做组建训练集.从训练集中学习出各个位置状态间的转移矩阵P.1条测试轨迹Gi={n1,n2,…}总共有|Gi|个位置状态,对于除了最后一个位置状态外的每一个ni,从转移矩阵中得到概率最高的位置即为MPRE预测的下一位置.对于这条测试轨迹,预测正确的位置状态数量mi占轨迹中|Gi|-1个位置数量的比率即为MPRE对该条轨迹预测的正确率.所有测试轨迹的正确率求平均得到MPRE预测的正确率Acc

.

(6)

Table 1 Taxi Trajectory Dataset in Chengdu
表1 成都市出租车轨迹实验数据集

AreaPeriod∕monthTimeNumber of VehiclesSize of Dataset∕GBNumber of Trajectories10km×10km1 6:00—23:0013605154010960

Fig. 5 The result of MPRE
图5 MPRE结果

图5展示了不同测试集、不同网格步长情况下的实验结果.由于大量的训练集更能反映整体数据的规律,在同一网格粒度下,训练集数量越多,可能MPRE的准确率越高.本文首先设置了4个不同大小的训练集.训练集1中有106条轨迹数据,训练集2有2×106条,训练集3有3×106条,训练集4中有4×106条轨迹数据.在同一训练集下,改变网格粒度,对104条轨迹数据进行测试.一方面,1个粗的网格粒度(例如g=500 m),由于每个网格覆盖的面积较大,可能会使预测精度降低.另一方面,由于覆盖面积大,训练数据中更多的原始GPS轨迹点会落入相同的网格区域,匹配到的轨迹数目可能更高,从而提高MPRE的准确率.因此,需要找到一个平衡的网格粒度使得MPRE的准确率达到最佳.图5中的实验结果表明,随着数据量的增加,MPRE的准确率越来越高.在训练集4中,网格粒度在g=200 m和g=400 m下表现出较高的预测准确率,能达到70%左右.对比MPRE算法在2种粒度下的运行时间,越细粒度的网格,网格数量越多,算法的时间复杂度越高.因此,综合考虑下本文选择g=400 m的网格粒度,以下的实验如果没有特别说均在g=400 m的网格粒度下进行.

4.2 任务分配的方法评估

通过预测车辆移动模块中的MPRE方法确定出目标下一步移动的位置范围,在该区域内预先安排参与者.在进行任务分配之前,首先,确定区域内的任务位置.本文从OpenStreetMap中得到成都市路网数据,将路网数据中的节点作为一条路上的任务点.其次,确定用户位置.本文有成都市出租车的载客状态数据,考虑到出租车由载客状态1转变为空车状态0则表明该位置有乘客下车,即可以认为该位置有用户.因此,本文使用出租车载客状态发生变化时的位置作为候选参与者的位置.本文提出了T-centric和P-centric方法以在网格内进行参与者和任务点的优选.T-centric是以任务为中心进行参与者选择,而P-centric是以人为中心进行任务的选择.2种方法的解决思路不同,选出的参与者与任务的最佳匹配也不同,因此需要通过实验验证2种方法的性能.为了降低CrowdTracker平台的用户激励成本,在任务分配中要求参与者能在一定时间约束内到达指定任务点的同时所移动的距离最短.因此对比2种方法所选出的参与者的平均移动距离.在任务个数以及参与者人数一定的情况下,选出的参与者与任务的最佳匹配数量越多,说明能够完成的任务越多.因此,另一个需要对比的指标是任务的覆盖率.最后针对该问题选择出性能较好的算法.

以下的实验均在400 m×400 m的网格粒度下进行(g=400 m).由于该实验主要研究不同地点的任务对参与者选择的影响,所以希望保持每个参与者完成任务的移动方式相同,即本文认为参与者都是通过步行的方式完成任务,每个参与者移动的速度为60 mmin即Vu=60 mmin,车辆移动的平均速度是30 kmh即Vc=500 mmin,则参与者要在(单位min)的时间约束内能到达任务地点,即参与者与任务的距离约束在48 m以内.考虑到实验的准确性,以下的实验数据都是通过多次实验平均而来.

在任务分配问题中,有2个因素对分配结果影响较大.一个是任务个数,另一个是候选者人数.由于路网中节点的数量和位置是一定的,也就是说任务的个数以及任务地点是一定的,因此本次实验主要研究不同候选参与者人数下的2种算法的性能.将成都市二环内10 km×10 km范围(625个网格)的1 017个路网节点作为任务地点.保持其他因素不变,将完成任务的时间设为10:00—10:10,对于这625个网格中的每一个网格,以该段时间出现在区域内的用户为候选者,所有网格总共有40 700个候选者.改变候选者人数的总量,在每一个网格区域内进行任务分配,最终对每个网格得到一系列参与者与任务地点的最佳匹配.每个网格内任务的覆盖率定义为形成最佳匹配的任务点的个数与该网格所有任务点数量的比值,对所有网格的任务完成率求均值得到平均任务完成率.对所有参与者完成任务所移动的距离DT求均值得到平均移动距离,平均移动距离越小,CrowdTracker平台用户激励成本越小.

Fig. 6 Average task coverage
图6 候选参与者人数与平均任务覆盖率的关系

图6展示了候选参与者人数与平均任务覆盖率的关系.实验结果表明,随着候选参与者人数的增加,T-centric和P-centric的平均任务覆盖率均呈现增长趋势.该结果说明了群智任务中的一个典型问题,在一定程度上,参与者人数的多少决定了群智任务的完成率.对比2种算法的结果,同等参与者人数下,P-centric比T-centric的任务覆盖率相对较高,但差别不是很大.图7展示了算法对参与者平均移动距离的影响,明显看出,同等参与者人数下,P-centric比T-centric的平均移动距离大.本文研究的问题中,候选参与者的人数比任务的数量多,P-centric是以人为中心去选择在时间约束内且距离最近的任务,对于参与者来说选出的任务是距离其最近的,但是对于任务来说选出的参与者不一定是最近的,因此,P-centric的移动距离较大.但是在算法运行时间上如图8所示,同样的原因,由于候选参与者的人数比任务的数量要多,T-centric在以任务为中心选择参与者时需要计算的参与者数据量大,计算时间长.因此,针对本文的问题,为了更好地反映算法的性能,以参与者平均移动距离与计算时间的乘积大小作为衡量算法性能的指标,乘积越小,算法性能越好.如图9所示,P-centric比T-centric的平均乘积小,P-centric以人为中心的方法更适合本文的任务分配问题.

Fig. 7 Average traveled distance
图7 算法对参与者平均移动距离的影响

Fig. 8 Running time
图8 算法运行时间对比

Fig. 9 The product of average distance traveled
and running time
图9 算法参与者平均移动距离与计算时间的乘积对比

5 总结与展望

本文主要研究了基于移动群智感知的目标跟踪,提出了一种新的解决方案CrowdTracker:通过基于群智的多人协作拍照方式实现对移动目标的实时跟踪.CrowdTracker在保证准确实时地对目标进行跟踪的同时尽可能地减少用户激励的成本.为了实现这个目标,本文提出了预测目标移动模型的方法MPRE和任务分配的方法T-centric,P-centric.T-centric是以任务为中心的参与者选择方法,而P-centric是以人为中心的任务选择方法.MPRE首先通过分析大量的车辆历史轨迹建立城市里车辆位置的移动模型,进而预测移动目标下一步的位置范围,在该位置范围内通过T-centric或P-centric方法进行跟踪任务分配.最后,通过大规模的真实数据集对3种算法进行实验评估,综合考虑实验结果,MPRE在g=400 m的网格粒度下能保证预测准确率较高且算法运行时间较短,因此本文选择在g=400 m的网格粒度下分配跟踪任务.结果表明以人为中心的任务选择方法P-centric更适合本文提出的跟踪任务分配问题,保证任务覆盖率的同时用户激励成本较小且算法的运行时间更短,能有效地实现目标实时跟踪.

未来的工作主要包括2方面:1)考虑基于固定部署摄像头与基于移动群智感知的目标跟踪方法相结合,更好地利用城市中现有的资源,降低目标跟踪的成本;2)要结合图像处理方法来辅助用户快速定位目标,降低用户参与负担.

参考文献

[1]Liu Liang, Zhang Xi, Ma Huadong. Dynamic node collaboration for mobile target tracking in wireless camera sensor networks[C] Proc of the 28th IEEE Int Conf on Computer Communications. Piscataway, NJ: IEEE, 2009: 1188-1196

[2]Li Yiming, Bhanu B. Utility-based dynamic camera assignment and hand-off in a video network[C] Proc of the 2nd ACMIEEE Int Conf on Distributed Smart Cameras. Piscataway, NJ: IEEE, 2008: 1-9

[3]Guo Bin, Yu Zhiwen, Zhou Xingshe, et al. From participatory sensing to mobile crowd sensing[C] Proc of the 12th IEEE Int Conf on Pervasive Computing and Communications Workshops. Piscataway, NJ: IEEE, 2014: 593-598

[4]Goldman J, Shilton K, Burke J, et al. Participatory sensing: A citizen-powered approach to illuminating the patterns that shape our world[J]. Ethics in Science & Engineering National Clearinghouse, 2009, 4(2): 117-134

[5]Merlino G, Arkoulis S, Distefano S, et al. Mobile crowdsensing as a service: A platform for applications on top of sensing clouds[J]. Future Generation Computer Systems, 2016, 56(2): 623-639

[6]Dan Jiang, Yuan Yu. A multi-object motion-tracking method for video surveillance[C] Proc of the 8th Acis Int Conf on Software Engineering, Artificial Intelligence, Networking, and ParallelDistributed Computing. Piscataway, NJ: IEEE, 2007: 402-405

[7]Serby D, Kollermeier E, Gool L V. Probabilistic object tracking using multiple features[C] Proc of the 17th Int Conf on Pattern Recognition. Piscataway, NJ: IEEE, 2004: 184-187

[8]Wang Yong, Wang Dianhong, Fang Wu. Automatic node selection and target tracking in wireless camera sensor networks[J]. Computers & Electrical Engineering, 2014, 40(2): 484-493

[9]Kim S, Robson C, Zimmerman T, et al. Creek watch: Pairing usefulness and usability for successful citizen science[C] Proc of the 19th Special Interest Group on Computer-Human Interaction Conf on Human Factors in Computing Systems. New York: ACM, 2011: 2125-2134

[10]Uddin M Y S, Wang Hongyan, Saremi F, et al. PhotoNet: A similarity-aware picture delivery service for situation awareness[C] Proc of the 32nd Real-Time Systems Symp. Piscataway, NJ: IEEE, 2011: 317-326

[11]Chen Huihui, Guo Bin, Yu Zhiwen, et al. Toward real-time and cooperative mobile visual sensing and sharing[C] Proc of the 35th IEEE Int Conf on Computer Communications. Piscataway, NJ: IEEE, 2016: 1-9

[12]Hua Yu, He Wenbo, Liu Xue, et al. SmartEye: Real-time and efficient cloud image sharing for disaster environments[C] Proc of the 34th IEEE Int Conf on Computer Communications. Piscataway, NJ: IEEE, 2015: 1616-1624

[13]Xu Mengwen, Wang Dong, Li Jian. DESTPRE: A data-driven approach to destination prediction for taxi rides[C] Proc of the 28th ACM Int Joint Conf on Pervasive and Ubiquitous Computing. New York: ACM, 2016: 729-739

[14]Xue A Y, Zhang Rui, Zheng Yu, et al. Destination prediction by sub-trajectory synthesis and privacy protection against such prediction[C] Proc of the 28th Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2013: 254-265

[15]Gambs S, Killijian M O, Cortez M N D P. Next place prediction using mobility Markov chains[C] Proc of the 1st Workshop on Measurement, Privacy, and Mobility. New York: ACM, 2012: 3

[16]Papadias D, Shen Qiongmao, Tao Yufei, et al. Group nearest neighbor queries[C] Proc of the 19th Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2004: 301-312

[17]Reddy S, Estrin D, Srivastava M. Recruitment framework for participatory sensing data collections[C] Proc of the 8th Int Conf on Pervasive Computing. New York: ACM, 2010: 138-155

[18]Cardone G, Foschini L, Bellavista P, et al. Fostering participaction in smart cities: A geo-social crowdsensing platform[J]. IEEE Communications Magazine, 2013, 51(6): 112-119

[19]Li Chengte, Shan M K. Team formation for generalized tasks in expertise social networks[C] Proc of the 2nd IEEE Int Conf on Social Computing. Piscataway, NJ: IEEE, 2010: 9-16

[20]Liu Yan, Guo Bin, Wang Yang, et al. TaskMe: Multi-task allocation in mobile crowd sensing[C] Proc of the 28th ACM Int Joint Conf on Pervasive and Ubiquitous Computing. New York: ACM, 2016: 403-414

CrowdTracker: Object Tracking Using Mobile Crowd Sensing

Jing Yao, Guo Bin, Chen Huihui, Yue Chaogang, Wang Zhu, and Yu Zhiwen

(School of Computer Science, Northwestern Polytechnical University, Xian 710072)

Abstract This paper proposes CrowdTracker, a novel object tracking system based on mobile crowd sensing (MCS). Different from other studies that are based on video surveillance, CrowdTracker recurits people to collaboratively take photos of the object to achieve object movement prediction and tracking. The optimization objective of CrowdTracker is to effectively track the moving object in real time and minimize the cost of user incentives. The incentive is determined by the number of workers assigned and the total distance that workers move to complete the task. In order to achieve the objective, CrowdTracker proposes an algorithm MPRE to predict the object moving pattern, and two task allocation algorithms, namely T-centric and P-centric, are proposed. T-centric selects workers in a task-centric way, while P-centric allocates tasks in a people-centric manner. By analyzing a large number of historical vehicle trajectories, MPRE builds a moving model of vehicle to predict the object’s next position. In the predicted regions, CrowdTracker selects an optimal set of workers for the tracking task by utilizing T-centric or P-centric. Experiments are conducted on a large-scale real-world dataset. The experimental results show that CrowdTracker can effectively track the object in real time and reduce the incentive cost at the same time.

Key words mobile crowd sensing; photo taking; object tracking; object movement prediction; task allocation

(jy_jingyao@163.com)

中图法分类号 TP391

收稿日期20171025;

修回日期:20180316

基金项目国家自然科学基金项目(61332005,61772428,61402369);国家“九七三”重点基础研究发展计划基金项目(2015CB352400)

This work was supported by the National Natural Science Foundation of China (61332005, 61772428, 61402369) and the National Basic Research Program of China (973 Program) (2015CB352400).

通信作者郭斌(guob@nwpu.edu.cn)

Jing Yao, born in 1994. Master candidate. Her main research interest is mobile crowd sensing.

Guo Bin, born in 1980. Professor, PhD supervisor. His main research interests include ubiquitous computing, mobile crowd sensing, and HCI.

Chen Huihui, born in 1979. PhD. Her main research interest is mobile crowd sensing.

Yue Chaogang, born in 1994. Master candidate. His main research interest is mobile crowd sensing.

Wang Zhu, born in 1983. Associate professor. His main research interests include pervasive computing, social network analysis, and healthcare.

Yu Zhiwen, born in 1977. Professor, PhD supervisor. Member of CCF. His main research interests cover ubiquitous computing and HCI.