赵卓峰 , 卢帅 , 韩燕波
北方工业大学 大规模流数据集成与分析技术北京市重点实验室, 北京 100144

收稿日期: 2016-06-28
基金项目: 国家自然科学基金重点项目（61033006）；北京市自然科学基金项目（4162021）
作者简介: 赵卓峰(1977-), 男, 副研究员。E-mail:edzhao@ncut.edu.cn


摘要：车牌识别数据是一种具有数据量大、时空相关、位置可测等特征的车辆监测数据，基于此类数据的相似轨迹查询面临着诸多问题。该文给出一种基于“点伴随关系”的车辆相似轨迹定义，提出了一种多级任务并行的相似轨迹查询方法，并给出了基于MapReduce迭代计算模型的方法实现，可支持在海量车牌识别数据集中利用分布计算环境高效地完成相似轨迹查询。基于近千万条真实车牌识别数据的实验表明，相对于传统方法，该方法在保证相似轨迹查询结果准确的前提下具有更好的查询性能。
关键词： 相似轨迹 车牌识别数据 点伴随 多级任务并行
Similar trajectory query method based on massive vehicle license plate recognition data
ZHAO Zhuofeng, LU Shuai, HAN Yanbo
Beijing Key Laboratory on Integration and Analysis of Large-Scale Stream Data, North China University of Technology, Beijing 100144, China


Abstract:Vehicle license plate recognition data provides a kind of traffic monitoring data that is a large spatial-temporal stream with fixed positions. Similar trajectory queries of such data face several problems. This paper presents a similar trajectory query method based on site companions with multistage task parallelization based on the MapReduce computing model. This method gives more efficient similar trajectory queries in a distributed computing environment for massive license plate recognition data. Tests show that this method can correctly query similar trajectories more efficiently than traditional stand-alone methods based on tests with almost ten million real vehicle license plate data points.
Key words: similar trajectoryvehicle license plate recognition datasite companionmultistage task parallelization
相似轨迹查询是以移动对象运动轨迹相似性为主题的查询，是移动对象数据管理领域中的一个热点问题。相似轨迹是指不同移动对象的运动轨迹具有较高的相似性，比如候鸟的迁徙轨迹、军队训练运动轨迹、车辆行驶轨迹等。轨迹的相似性可以仅仅是空间位置上的相似，也可以是时间与空间两重属性上的相似。由于很多涉车业务应用大都是面向具体车辆的分析(如公安业务中犯罪嫌疑车辆分析)，因此对车辆相似轨迹的查询往往要求时间和空间两重属性上的相似。
车牌识别技术是近年来新兴的一种城市通行车辆信息采集技术，它通过对部署在城市道路摄像头所采集的车辆图像信息进行识别来提取车辆的车牌信息，并在此基础上形成包含车辆标识和车辆时间、空间属性的车牌识别数据信息。随着车牌识别技术的完善以及车牌捕获率与识别率的显著提高，基于车牌识别数据的车辆出行信息采集手段在很多城市被广泛部署应用。相比于浮动车等车辆信息采集技术，基于车牌识别数据的车辆信息采集技术具有工作连续性强、数据精确度高、检测样本量大、覆盖车辆范围广等优点^[1]。因此，基于车牌识别数据的车辆相似轨迹查询成为当前移动对象轨迹分析研究中的热点，对其的研究具有重要的学术意义和应用价值^[2]。
由于车牌识别数据来源于对城市道路行驶车辆的实时监测，因此其包含车辆标识、监测时间、地理位置等时间、空间以及车辆对象相关的信息，具有典型的时空相关、时序连续、位置可测的特征。基于车牌识别数据可以满足更加灵活的车辆相似轨迹查询的需求，即可以针对任意历史或当期时间段以及不同的相似性界定约束条件来查询车辆相似轨迹。为此，需要设计一种有效的针对车牌识别数据集的相似轨迹查询方法。此外，考虑到随着车牌识别数据采集技术的大范围应用，车牌识别数据集的规模将大大超过传统采样方法获得的数据，这对海量车牌识别数据上相似轨迹查询方法的性能也提出了更高的要求。
目前针对相似轨迹查询问题的很多研究工作^[3-5]在对时空数据特征的利用和大规模连续数据的处理方面仍存在一定的不足。近年来，研究者结合不同的移动对象数据特征，从相似轨迹模式的角度提出了“护航”、“群体迁移”等分析模式，并考虑了实际情况中采样点丢失以及降低计算量等因素^[6-7]。在这些模式基础上，文[8]对确定数量的移动车辆对象进行跟踪记录，提出一种基于网络树的移动对象轨迹(trajectory of moving objects on network tree，简称为TMN-Tree) 查询方法对车辆轨迹数据进行处理，这种树形结构大大提高了相似轨迹的查询效率。文[9]提出一种基于车牌识别数据的伴随车辆检测方法(accompanying cars recognition method，简称为ACR方法)，该方法通过对识别数据进行整理，构建节点过车序列，进一步通过对节点过车序列进行对比分析，发现其最长公共序列，最终整合最长公共序列，根据条件阈值，得出符合要求的车辆相似轨迹。文[10-11]针对以浮动车数据为例的流式数据，提出了一种基于“旅行伴侣数据结构”的相似轨迹发现方式，由于其中的“旅行伴侣数据结构”只是存储各对象之间的关系，相对于以往的轨迹分析要保存每个采样点的坐标、采样时间等信息，可大幅度地减少计算量，从而提升相应的查询性能。文[12]针对出租车GPS数据提出一种基于网格的聚集索引模型来支持在线的频繁路径挖掘，可实现分布计算环境下对实时轨迹数据的在线分析。频繁路径在概念上与相似轨迹有一定的类似，也可以理解为更宏观层次的相似轨迹聚类。
然而，上述工作所采用的相似轨迹模式大都要求能对特定采样范围的移动对象进行数据监测，并不适合位置可测但车辆对象不定的车牌识别数据。此外，这些工作也没有从分布式计算的角度来考虑提高相似轨迹的查询性能，在应对亿级海量数据时由于中间结果规模的放大，存在响应时间长甚至不可处理的问题。针对这些问题，本文在对海量车牌识别数据集上相似轨迹查询的分析基础上，利用车牌识别数据的时空相关、位置可测等特征，给出一种基于点伴随的车辆相似轨迹定义以支持车辆轨迹的时空相似性度量，并提出一种基于多级任务并行模式的相似轨迹查询处理方法。该方法通过将基于车牌识别数据的查询处理过程进行任务分解并以多级任务并行的方式来优化查询处理。此外，该方法还采用了基于Hash B树的数据结构来存储查询处理过程中涉及的车辆轨迹数据，该结构具有查询高效、适于并行划分及伸缩的特征。
1 问题描述1.1 基于点伴随的车辆相似轨迹定义本节根据车牌识别数据特征，给出一种基于点伴随关系的相似轨迹定义，并在此基础上描述基于车牌识别数据的相似轨迹查询问题。
定义1 ??受测路网：受测路网指由部署在城市道路上监测点及其之间涉及的路段构成的道路结构, 可表示为R=(N, S)。其中：N为道路监测点集合，S为路段集合。
定义2 ??车牌识别数据集：车牌识别数据集L是指受测路网上各监测点捕获的所有车辆信息数据。一条车牌识别数据I_i∈L可表示为(v_i, t_{i, k})。其中：v_i表示车牌号码(可唯一代表一个车辆)，t_{i, k}表示车辆v_i经过监测点k的时间。
定义3 ??车辆轨迹：车辆轨迹Tr_i是车辆v_i在一个时间范围内按顺序经过一组监测点的时间序列集合，表示为：Tr_i={t_{i, 1}, t_{i, 2}, …, t_{i, n}}，对任意p < q, 有t_{i, p}＜t_{i, q}。Tr_i中包含的监测点数目称为轨迹的长度，记为l_i。
定义4 ??点伴随关系：点伴随关系是指两车辆v_i和v_j在一定时间范围阈值t_th内先后经过某监测点n的一种关系，即在满足条件|t_{i, n}-t_{j, n}|≤t_th时，车辆v_i和v_j具有点伴随关系，记为sim_n(v_i, v_j)=1。
由点伴随关系的定义可以看出车辆轨迹的时间和空间两方面属性被用来判断点伴随关系。
定义5 ??轨迹相似度：轨迹相似度是指两条车辆轨迹的相似程度。假定两辆车v_i和v_j的轨迹长度分别为l_i和l_j，而两辆车轨迹中途经的符合定义4的点伴随关系的监测点数目为m，则它们的轨迹相似度定义为

$d\left({{\rm{T}}{{\rm{r}}_i}, {\rm{T}}{{\rm{r}}_j}} \right)=\frac{{2m}}{{{l_i}+{l_j}}}.$

定义6 ??相似轨迹:给定轨迹相似度阈值d_th和轨迹长度阈值l_th，若在给定时间范围内的两条车辆轨迹Tr_i和Tr_j满足以下条件则称它们为相似轨迹：
1) 轨迹Tr_i和Tr_j的相似度d(Tr_i, Tr_j)≥d_th；
2) 轨迹Tr_i和Tr_j的轨迹长度l_i≥l_th，l_j≥l_th。
符合定义6的两条相似轨迹被记为s(Tr_i, Tr_j)=1，否则s(Tr_i, Tr_j)=0。其中，引入轨迹长度阈值的目的是避免对一些伴随距离较短的车辆轨迹作出相似轨迹的误判，同时也可利用该值对一些无效数据进行过滤以提高查询性能，2.2节将会对此进一步具体描述。
1.2 海量车牌识别数据下相似轨迹查询的挑战考虑到车牌识别数据具有的海量、时空相关、面向对象等特征，基于车牌识别数据的车辆相似轨迹查询需要应对以下几方面挑战：
车辆轨迹数据的合理组织。要求设计一种能够快速建立并提供有效时空索引的数据结构来组织数以百万级的车辆轨迹数据，以支持进行以时空相关的点伴随判定为核心的相似轨迹查询。
车牌识别数据的有效性处理。要求在进行相似轨迹查询前对原始车牌识别数据进行有效性处理以减少由于监测摄像头分布不合理、采集不精确而产生不全面的轨迹数据，从而降低查询代价。
相似轨迹查询处理的并行化。要求根据相似轨迹查询问题定义，设计相应的并行化模式和并行化算法，以实现相似轨迹查询处理过程中相关环节的并行化，并可根据不同的查询条件(涉及不同的数据规模) 来灵活控制并行化程度。
2 基于多级任务并行的相似轨迹查询方法针对1.2节中提出的海量车牌识别数据中相似轨迹查询问题，本文提出一种基于多级任务并行的相似轨迹查询方法(multistage task parallelization method for similar trajectory query，简称为MPST方法)。该方法将基于车牌识别数据的查询处理过程分解为轨迹创建与筛选、点伴随判定、轨迹相似性计算等任务并以多级任务并行的方式进行处理，同时利用基于Hash B树的结构来存储查询处理过程中涉及的车辆轨迹数据。
2.1 基于Hash B树的车辆轨迹数据结构基于车牌识别数据的车辆轨迹数据在内存中采用Hash B树结构存储。把按照地理位置划分的区域编号作为Key，将相同区域编号下的测点获取的车牌识别数据采用B树组织，给定车辆ID的单车车辆轨迹数据在Hash B树的叶节点用链表组织。
2.2 车辆轨迹数据预处理受摄像头部署数量、范围等影响，基于车牌识别数据建立的车辆轨迹数据并不一定完整，有大量的车辆轨迹数据只具有片段性的轨迹数据，即车辆轨迹中所捕获监测点数据有限。这些数据在车辆相似轨迹判定中很难发挥作用。
因此，在相似轨迹定义中设置了轨迹长度阈值的概念。基于给定的轨迹长度阈值l_th，可以对已建立的车辆轨迹数据结构中叶节点链表进行过滤以删除长度小于阈值的叶节点，即要求轨迹Tr_i的轨迹长度l_i≥l_th，通过基于轨迹长度阈值的预处理，可以将原始车辆轨迹中仅包含较少监测点的数据删除，从而避免此类数据由于监测点过少而导致轨迹相似度计算不准确的情况，还可以提高后续处理效率。
2.3 基于MapReduce迭代计算的流水线式处理基于车牌识别数据的查询处理过程可分解为轨迹创建与筛选、点伴随判定、轨迹相似性计算等多级任务。根据任务间的关联关系，可以以多级任务流水线式处理的方式进行相似轨迹的查询处理。
1) 车辆轨迹创建与筛选。
针对输入的车牌识别数据记录，按数据采集时间对其进行分组，然后以车牌号码作为Key并通过Map和Reduce函数得到所有的车辆轨迹，并进一步按照Hash B树的数据结构建立所有车辆的轨迹数据。
2) 点伴随判定。
基于第1次MapReduce处理后得到的可用于相似轨迹判定的车辆轨迹数据，本步骤再通过异常MapReduce处理来对所有轨迹数据交叉进行1.1节定义4的“点伴随关系”判定，并最终得到具有“点伴随关系”的结果集。该步骤的伪码见图 1。

图 1 点伴随关系判定伪码

图选项

3) 轨迹相似性判定。
利用第2次MapReduce得到的具有“点伴随关系”的结果集，本步骤再次通过MapReduce完成1.1节定义5的轨迹相似度计算和定义6的相似轨迹判定。其中，用于轨迹相似度计算的点伴随次数统计部分的伪码如图 2所示。

图 2 点伴随次数统计伪码

图选项

在具体实现中，基于MapReduce计算模型并采用文[13]中的多次MapReduce迭代的方式来实现多级流水线式并行。此外，根据实际的业务应用经验，在具体实现中分别把点伴随时间阈值默认值设置为1 min，轨迹长度阈值默认值设置为10个监测点，轨迹相似度阈值默认值设置为75%。
3 实验与分析3.1 实验环境与实验数据为验证本文提出的基于海量车牌识别数据的相似轨迹查询方法，搭建了由3台服务器构成的Hadoop集群环境来进行测试。其中: Master节点服务器配置为4核CPU、4 GB内存、80 GB外存，同时Master节点也被用作计算节点运行Datanode服务；两台Slave节点服务器配置为2核CPU、4 GB内存、80 GB外存。
实验中采用的数据为北京市2012-11-13全天采集的真实车牌识别数据，数据记录共约970万余条，大小0.94 GB。这组数据涉及的车牌数量(即车辆数) 约230万，道路监测点为1 794个。
利用以上实验环境和实验数据，从性能、正确性和阈值参数影响分析等角度对本文提出的MPST方法进行默认设置下的验证。同时，还在与Master节点同配置的服务器上，利用同样的实验数据，对文[8]的TMN-Tree和文[9]的ACR方法两个单机方法进行了测试以作对比。
3.2 实验结果3.2.1 性能测试在性能测试实验中，分别针对1 h、3 h、8 h、24 h等时间范围(t_c) 下不同规模的车牌识别数据进行了车辆相似轨迹查询性能测试。详细查询时间结果如表 1所示。
表 1 不同时间范围的数据规模下查询耗时对比

查询方法	查询耗时/min
	tc=1 h (41万条)	tc=3 h (155万条)	tc=8 h (370万条)	tc=24 h (970万条)
TMN-Tree	1.67	7	26	88
ACR	0.33	2	6	45
MPST	0.18	0.43	0.75	4

表选项






由表 1可见，MPST方法在处理1 h、3 h、8 h时间范围下的车牌识别数据时查询耗时均在1 min以内，在处理24 h时间范围下的数据时查询耗时扩大为4 min，但各时间范围下的查询性能均优于其他两种方法。MPST方法的性能约为ACR方法的2~10倍。具体的实验结果分析可参见文[14]。
3.2.2 正确性测试与分析为验证MPST方法的正确性，通过在相同实验数据集上分别用MPST方法和代表传统相似轨迹查询的ACR方法进行车辆相似轨迹查询计算，以对比不同方法下查到的查询结果，来验证本文算法的查全性和查准性。实验中所取的点伴随时间阈值为1 min，轨迹长度阈值为10，轨迹相似度阈值为80%，具体测试结果如表 2所示。
表 2 不同时间范围的数据规模下查询得到的相似轨迹数量对比

查询方法	查询得到的相似轨迹数量
	tc=1 h	tc=3 h	tc=8 h	tc=24 h
ACR	1	41	132	873
MPST	1	41	132	873

表选项






通过表 2的测试结果可以看出，本文MPST方法查询结果与传统相似轨迹查询ACR方法得到的相似轨迹数量完全相同，由此说明本文算法在通过并行处理提高查询性能的同时，可以保证查询结果的正确性不会受到影响。
3.2.3 阈值参数影响测试由于上述实验中相似轨迹判定涉及的阈值均采用基于经验的默认值，但随着应用种类的增加，这些阈值参数需要进行调整，因此需要了解阈值参数对相似轨迹查询的性能影响。
本测试实验使用了2012-11-13全天的车牌识别数据，分别测试了1 min、2 min、3 min 3个点伴随时间阈值和70%、75%、80%、85%、90% 5个轨迹相似度阈值情况下相似轨迹查询的性能。
通过图 3所示的实验结果可以看出，增大时间间隔阈值会降低查询性能，而增大轨迹相似度阈值则会提高查询性能。在轨迹相似度阈值较高时，时间间隔阈值的变化对性能的影响会变小。具体的实验结果分析可参见文[14]。

图 3 不同阈值下的查询性能变化[14]

图选项

4 结束语本文为实现基于海量车牌识别数据的车辆相似轨迹查询，给出一种基于点伴随关系的车辆相似轨迹定义，并提出一种多级任务并行的相似轨迹查询处理方法和基于MapReduce迭代计算的流水线式处理实现过程。该方法通过将基于车牌识别数据的查询处理过程进行任务分解并以多级任务并行的方式来优化查询处理性能。此外，该方法还采用了基于Hash B树的数据结构来存储查询处理过程中涉及的车辆轨迹数据，该数据结构具有查询高效、适于并行划分及伸缩的特征。本研究结果对于公安办案中犯罪嫌疑车辆分析及城市车辆出行规律分析等业务具有较好的应用价值。下一步的研究工作将包括多级任务流水线并行处理中涉及中间结果的缓存优化以及进行更加全面的实验测试。

参考文献

[1]	Journal of Central South University(Science and Technology), 41(2):649-654.-->柴华骏, 李瑞敏, 郭敏. 基于车牌识别数据的城市道路旅行时间分布规律及估计方法研究[J]. 交通运输系统工程与信息, 2012, 12(6): 41–47.CHAI Huajun, LI Ruimin, GUO Min. Travel time distribution and estimation of urban traffic using vehicle identification data[J]. Journal of Transportation Systems Engineering and Information Technology, 2012, 12(6): 41–47. (in Chinese)
[2]	Journal of Central South University(Science and Technology), 41(2):649-654.-->姜桂艳, 常安德, 牛世峰. 基于车牌识别数据的交通拥堵识别方法[J]. 哈尔滨工业大学学报, 2011, 43(4): 131–135.JIANG Guiyan, CHANG Ande, NIU Shifeng. Traffic congestion identification method based on license plate recognition data[J]. Journal of Harbin Institute of Technology, 2011, 43(4): 131–135. (in Chinese)
[3]	Journal of Central South University(Science and Technology), 41(2):649-654.-->丁锐, 孟小峰, 杨楠. 一种高效的移动对象相似轨迹查询方法[J]. 计算机科学, 2003, 30(10): 386–403.DING Rui, MENG Xiaofeng, YANG Nan. An efficient solution about similarity queries for moving object trajectories[J]. Computer Science, 2003, 30(10): 386–403. (in Chinese)
[4]	Journal of Central South University(Science and Technology), 41(2):649-654.-->Jensen C S, Lin D, Ooi B C. Continuous clustering of moving objects[J]. IEEE Transactions on Knowledge and Data Engineering (TKDE), 2007, 19(9): 1161–1174. DOI:10.1109/TKDE.2007.1054
[5]	Journal of Central South University(Science and Technology), 41(2):649-654.--> Yang D, Rundensteiner E A, Ward M O. Neighbor-based pattern detection for windows over streaming data[C]//Proceedings of the 12th International Conference on Extending Database Technology (EDBT09). Saint Petersburg, Russia, 2009:529-540.
[6]	Journal of Central South University(Science and Technology), 41(2):649-654.--> Jeung H, Yiu M, Zhou X. Discovery of convoys in trajectory databases[C]//Proceedings of the 36th International Conference on Very Large Data Bases (VLDB08). Auckland, New Zealand, 2008:1068-1080.
[7]	Journal of Central South University(Science and Technology), 41(2):649-654.--> Xiong Y, Zhu Y. Mining peculiarity groups in day-by-day behavioral dataset[C]//Proceedings of the 9th International Conference on Data Mining (ICDM09). Miami, FL, USA, 2009:578-587.
[8]	Journal of Central South University(Science and Technology), 41(2):649-654.--> Chang J, Song M, Um J. TMN-tree:New trajectory index structure for moving objects in spatial networks[C]//Proceedings of the 10th IEEE International Conference on Computer and Information Technology. Bradford, UK, 2010:1633-1638.
[9]	Journal of Central South University(Science and Technology), 41(2):649-654.-->赵新勇, 安实. 伴随车检测技术应用研究[J]. 交通运输系统工程与信息, 2012, 12(3): 36–40.ZHAO Xinyong, AN Shi. Research on accompanying cars recognition in practical application[J]. Journal of Transportation Systems Engineering and Information Technology, 2012, 12(3): 36–40. DOI:10.1016/S1570-6672(11)60203-1(in Chinese)
[10]	Journal of Central South University(Science and Technology), 41(2):649-654.--> Tang L, Zheng Y, Yuan J, et al. On discovery of traveling companions from streaming trajectories[C]//Proceedings of the 28th IEEE International Conference on Data Engineering (ICDE12). Arlington, VI, USA, 2012:186-197.
[11]	Journal of Central South University(Science and Technology), 41(2):649-654.-->Tang L, Zheng Y, Yuan J, et al. A framework of traveling companion discovery on trajectory data streams[J]. ACM Transactions on Intelligent Systems and Technology, 2013, 5(1): 3-1–3-34.
[12]	Journal of Central South University(Science and Technology), 41(2):649-654.-->Zheng K, Zheng Y, Yuan J, et al. Online discovery of gathering patterns over trajectories[J]. IEEE Transactions on Data and Knowledge Engineering, 2014, 26(8): 1–14.
[13]	Journal of Central South University(Science and Technology), 41(2):649-654.--> Ekanayake J, Li H, Zhang B, et al. Twister:A runtime for iterative MapReduce[C]//Proceedings of the 19th ACM International Symposium on High Performance Distributed Computing. Chicago, IL, USA, 2010:810-818.
[14]	Journal of Central South University(Science and Technology), 41(2):649-654.-->赵卓峰, 丁维龙, 韩燕波. 基于云架构的交通感知数据集成处理平台[J]. 计算机研究与发展, 2016, 53(6): 1332–1341.ZHAO Zhuofeng, DING Weilong, HAN Yanbo. An intergrated processing platform for traffic sensor data based on cloud architecture[J]. Journal of Computer Research and Development, 2016, 53(6): 1332–1341. (in Chinese)