一种基于空间语义特征的浮动车轨迹匹配技术

罗跃军，宋向勃，郑　莉

(1. 武汉大学资源与环境学院，湖北 武汉 430079； 2. 武汉光庭信息技术有限公司，湖北 武汉 430073；

3. 武汉大学测绘学院，湖北 武汉 430079)

Probe Vehicle Track-matching Algorithm Based on Spatial Semantic Features

LUO Yuejun，SONG Xiangbo，ZHENG Li



一种基于空间语义特征的浮动车轨迹匹配技术

罗跃军1，2，宋向勃2，郑莉3

(1. 武汉大学资源与环境学院，湖北 武汉 430079； 2. 武汉光庭信息技术有限公司，湖北 武汉 430073；

3. 武汉大学测绘学院，湖北 武汉 430079)

Probe Vehicle Track-matching Algorithm Based on Spatial Semantic Features

LUO Yuejun，SONG Xiangbo，ZHENG Li

摘要：针对浮动车轨迹数据挖掘中的空间语义分析问题，阐述了传统的电子导航地图匹配方法用于浮动车轨迹地图匹配时的主要问题，提出了基于空间语义特征的浮动车轨迹匹配算法，并结合实际数据进行了试验验证，本文提出的基于空间语义特征的全局路径匹配方法取得了很好的匹配效果，并可还原浮动车轨迹经由的真实路径。

关键词：空间语义特征；浮动车轨迹；空间数据挖掘

一、引言

随着城市化进程的不断加快和经济的飞速发展，汽车在人们的生活中迅速普及。随着汽车市场的蓬勃发展，大量问题也随之出现，浮动车技术作为一种新的高级导航数据采集方式，为解决上述问题提供了更多可能。浮动车也称为GPS探测车，是近年来国际智能交通系统(ITS)中所采用的获取城市道路交通状态的重要途径和有效方式[1]，也是一种先进的道路交通信息采集技术[2]。浮动车技术的数据范围能够遍布整个地区，能全天候24 h进行数据采集，利用无线实时传输、中心式处理大大提高信息采集效率；同时，利用现有的GPS和通信网络资源，也使得采集设备维护和安装成本较低[3]。综上，浮动车技术是比较经济、高效的方法。

为了利用浮动车技术进行空间数据挖掘，需要尽可能准确地还原浮动车轨迹经由的真实路径，实现浮动车轨迹数据和真实道路网数据的空间配准。由于浮动车轨迹数据存在采样间隔大、有位置噪声等数据特点，导致传统电子地图匹配方法不适用于浮动车轨迹的路径匹配，从而导致针对浮动车轨迹的空间数据挖掘难以进行。

二、传统的道路匹配算法存在的问题

传统的导航地图匹配方法主要以接收到的GPS位置信息，计算当前车辆所在位置，进而利用点线距离或轨迹曲线距离实现车辆在道路网上的匹配。由于GPS存在噪声误差，往往通过历史轨迹和车辆运动信息对匹配结果进行修正，以在一定程度消除GPS噪声的影响[1-5]。

由于GPS采样点的间隔仅为1 s，因此上述的导航地图匹配算法比较容易获得准确的轨迹曲线作为匹配样本，能够实现基于轨迹曲线的线到线的地图匹配。然而，对于车辆浮动车轨迹，由于采样间隔较大，一般在几十秒到数分钟才上传一个GPS点数据。时速40 km/h的浮动车，每分钟频率的GPS点前后相差约600 m，而这个距离内可能存在多种路径。前后两点间的相关性差决定了浮动车系统无法采用线到线的地图匹配方法。若仍沿用传统导航地图匹配方法，可能导致错误的路径匹配，甚至整个轨迹无法匹配出一条可通行路径(如图1所示)。可见，传统的导航地图匹配算法不能直接应用于浮动车系统[6]。图1中，浅灰色为电子地图道路网，深灰色为浮动车轨迹点连线，黑色为轨迹匹配结果。

图1　浮动车轨迹及其真实路径和道路网

三、基于空间语义特征的全局匹配模型

传统导航地图匹配问题模型只是根据GPS接收点的位置及其附近时间段内的车辆位置和车辆行为来进行匹配，相对于整个行驶路径而言，是一种局部路径匹配。对于浮动车轨迹而言，由于采样间隔过大，相邻采样点之间的相关性较差，因此不能通过历史位置点对GPS噪声进行修正。同时，每个采样的GPS位置点都受到噪声影响，单纯利用局部位置点进行路径匹配，很可能匹配到错误的道路上去，最终导致整个轨迹匹配到错误的路径上。文献[7—8]提出了轨迹点模糊匹配的方法，在一定程度上可以减轻噪声的影响，但仍然是在局部进行最优路径选择。

针对浮动车轨迹离线地图匹配[9]，从信息融合的角度[10]，可以同时考察整个行驶轨迹上的所有采样点的位置信息，这些不同的采样点之间存在可通达、通达时间受限等一些行为相关性。因此，可以考虑面向浮动车轨迹整体进行全局的最优轨迹匹配。

基于上述分析，本文提出用于浮动车轨迹的基于空间语义特征的全局路径匹配方法，具体如下：

1) 将每个轨迹点看作一条对轨迹的真实路径还原的证据信息。

2) 每个轨迹点在道路网上进行一定范围内的模糊匹配。

3) 按照某种路径探索方法，将所有轨迹点的模糊匹配结果依次连通，得到所有可能的全局匹配路径。

4) 按照某种空间语义评价标准，在全局匹配路径中寻找一条全局最优的匹配路径。

为了评价所选路径的优劣，本文提出了以{长度，道路种别的变化数，转弯数，道路数，经过的轨迹点数}在描述的路径的空间语义特征Φ={L,K,C,M,N}，即路径pt的空间语义特征为Φt={Lt,Kt,Ct,Mt,Nt}。

四、基于空间语义特征的浮动车轨迹路径还原方法

根据上述基于空间语义特征的全局匹配模型和选用的空间语义特征，本文提出了基于空间语义特征的浮动车轨迹路径还原方法。

1. 浮动车轨迹点模糊路径匹配

2. 轨迹点间路径探索

在相邻两个轨迹点所匹配的所有link间进行路径探索，探索出每对道路间的路径。如在第i个轨迹点和第i+1个轨迹点之间进行探索时，对于lij(j=1,2,…,mi)和li+1,k(k=1,2,…,mi+1)的任一组合

(lij,li+1,k)j∈{1,2,…,mi}，k∈{1,2,…,mi+1}

利用Dijkstra算法在一定道路数阈值s0内探索一条可通行路径rijk(lij,lin1,…,lini,li+1,k)，其中ni≥0。如果在阈值范围内找不到可通行路径，则放弃该组合。

3. 基于空间语义特征的全局最优路径选择

图2　全局完整路径生成流程

五、试验验证

利用本文所述方法，对实车采集轨迹随机抽样300条进行了路径匹配还原试验。在本试验中，轨迹点模糊匹配阈值r0为50 m，Dijkstra算法路径探索道路数目阈值s0为15条。

经过处理，300条轨迹都匹配出了完整的行驶路径，经过目视检查，轨迹的路径还原比较理想的有269条，占总路径的89.66%，图3—图5分别为一些轨迹的实际匹配结果。图中，浅灰色为电子地图道路网，灰色为浮动车轨迹点连线，黑色为轨迹匹配结果。

图3　轨迹1匹配的整体图和局部放大图

图4　轨迹2匹配的整体图和局部放大图

图5　轨迹3匹配的整体图和局部放大图

六、结束语

本文针对浮动车轨迹数据挖掘中的空间语义分

析问题，阐述了传统的电子导航地图匹配方法用于浮动车轨迹地图匹配时存在的主要问题，并提出了基于空间语义特征的浮动车轨迹匹配技术。通过实际数据，对本文提出的匹配方法进行了试验验证。结果表明，本文提出的匹配方法得到了较好的匹配效果，并还原了浮动车轨迹经由的真实路径。由于本文提出的方法需要在整个浮动车轨迹的所有可能路径集合中进行比较运算，以便选择最优路径，因此运算量偏大，对硬件资源的消耗较大，因此当浮动车轨迹中包含的轨迹点比较多的时候，在算法性能上需要进一步调优。

参考文献：

[1]耿小峰，王山东，季军．浮动车快速道路匹配算法[J]．水利与建筑工程学报，2013，11(1)：122-125．

[2]郝勇刚，吴广君，周双全．1种基于浮动车数据的多车车速融合算法[J]．交通信息与安全，2012，30(169)：56-61．

[3]诸彤宇，郭胜敏．浮动车信息处理技术研究[J]．中国图象图形学报，2009，14(7)：1230-1237．

[4]苏洁，周东方，岳春生．GPS车辆导航中的实时地图匹配算法[J]．测绘学报，2001，30(3)：252-256．

[5]唐进君，曹凯．一种自适应轨迹曲线地图匹配算法[J]．测绘学报，2008，37(3)：308-315．

[6]王美玲，程林．浮动车地图匹配算法研究[J]．测绘学报，2012，41(1)：133-138．

[7]KIMS，KIMJH．AdaptiveFuzzy-network-basedC-measureMap-matchingAlgorithmforCarNavigationSystem[J].IEEETransactionsonIndustrialElectronics，2001，48(2)：432-441.

[8]KIMS，KIMJH．Q-factorMapMatchingMethodUsingAdaptiveFuzzyNetwork[C]∥IEEEInternationalFuzzySystemsConferenceProceedings．Seall：IEEE，1999．

[9]PEREIRAFC，COSTAH，PEREIRANM．AnOff-lineMap-matchingAlgorithmforIncompleteMapDatabases[J].EuropeanTransportationResearchReview，2009，1(3)：107-124．

[10]BRAKATSOULASS．OnMapmatchingVehicleTrackingData[C]∥Proceedingofthe31stVLDBConference．[S.l.]:[s.n.],2005.

引文格式： 罗跃军，宋向勃，郑莉. 一种基于空间语义特征的浮动车轨迹匹配技术[J].测绘通报，2015(3)：108-110.DOI:10.13474/j.cnki.11-2246.2015.0090

作者简介：罗跃军(1978—)，男，博士，高级工程师，研究方向为地图学与空间数据处理。E-mail： lingfengyang@aligun.com

基金项目：国家863计划(2013AA12A202)；数字制图与国土信息、应用工程国家测绘地理信息局重点实验室开放研究基金

收稿日期：2014-01-29

中图分类号：P208

文献标识码：B

文章编号：0494-0911(2015)03-0108-03