一种改进的浮动车地图匹配算法

丁闪闪 刁含楼

摘 要：为提高浮动车地图匹配精度，提出一种改进的浮动车地图匹配算法，综合利用道路拓扑关系和车辆定位误差，缩小候选路段范围，采用基于距离与方向的要素加权方法确定最终匹配点，减少正确匹配路段被剔除的概率。依托南京市局部路网以及浮动车定位数据进行实例分析，结果表明，该方法具有较好的精度和实时性。

关键词：浮动车;地图匹配;道路拓扑;要素加权

中图分类号：P228.4 文献标识码：A

0 引言

随着智能交通系统的应用发展，安装车载定位设备的车辆越来越多，浮动车数据采集技术开始广泛应用于城市路况信息获取、道路建设和出行规划上[1]。地图匹配是浮动车技术的重要组成部分，由于路网环境、电子地图误差和定位设备误差的影响，浮动车采集的定位点会随机分布在道路两侧一定宽度范围内，只有将这些定位点修正到其行驶的道路上，才能开展相关应用。

目前，国内外学者研究的地图匹配算法主要包括几何匹配算法、概率统计匹配算法、相关性匹配算法、基于要素加权的匹配算法、模式识别匹配算法等[2]。其中，基于要素加权的地图匹配算法具有逻辑简单、速度快、实时性好等优点，得到较为广泛的应用。邹珍提出一种改进的基于权重的地图匹配算法[3]，将权重模型与交通规则约束、最短路径算法相结合。曾嘉郦等提出一种出租车地图匹配算法[4]，基于定位点到路段的距离、以及车辆行驶方向与道路方向的夹角确定候选路段，根据距离和方向的综合权重进行轨迹点匹配。在对以往的研究进行分析后发现，充分利用道路拓扑和多个要素可以进一步提高浮动车地图匹配精度。

本文从这一角度出发，综合利用道路拓扑关系和车辆定位误差，缩小候选路段范围，然后采用基于距离与方向的要素加权方法确定最终的匹配点，以期能够提高浮动车地图匹配精度，并确保匹配的实时性。

1 理论基础

1.1 基于网格法的误差区域初步确定

在算法设计时，默认车辆总是行驶在道路上，由此可知误差区域以一定的范围包含着车辆的实际位置，通过确定误差区域，可以排除大量不相关的路段，减少算法的复杂度。

本文采用网格法确定误差区域，在栅格地图基础上建立网格，利用折半查找法快速寻找出浮动车轨迹点所在的候选区域。由于定位接收机接收到的数据误差95%都在20 m以内，而数据投射到电子地图上的误差为15 m左右。综合考虑，取每个网格的边长为40 m。

根据浮动车定位点的经纬度数据，可以确定定位点在哪个网格块，选取定位点所在网格及其周边的8个网格作为误差区域。

1.2 基于道路拓扑的误差区域缩小

在电子地图中，道路拓扑关系是指节点与弧段之间的相互关系，在道路联通的情况下，一定时间范围内，由于车辆的行驶速度有限，因此存在着一个最远能够到达的距离。如图1所示，假设此时车辆行驶在道路1上，当前匹配点确定为，则由于行驶速度的限制，下一时刻，车辆最远只能到达、或点，即下一匹配点的位置只能存在于图中黑色实线部分的路段上。

传统的考虑道路拓扑关系的地图匹配算法中，通常是在确定误差区域后，将定位点向误差区域内的所有候选路段做投影，确定多个虚拟匹配点，然后将车辆无法到达的匹配点所在的路段去除，对剩余的虚拟匹配点，根据多要素计算综合匹配度，确定最终的匹配位置。如图2所示，为当前定位点，和为候选路段2和3上的虚拟匹配点，考虑道路拓扑关系后，认为点无法到达，因此将候选路段2去除，候选路段3成为最终的匹配路段，而成為最终的匹配点。但是从图中下一匹配点的位置可以判断，为错误匹配点。

针对以上可能出现的错误匹配情况，本文做了一定程度改进，在采用网格法确定候选路段后，并不急于将定位点向各路段进行投影，而是先根据前一匹配点的位置和道路拓扑性，另外确定一个匹配点可能存在的误差区域。将该误差区域与网格法确定的误差区域叠加，得到最终误差区域。将最终误差区域内路段上的每一个点均作为虚拟匹配点，以避免图2将路段2整条去除、造成错误匹配的情况。

1.3 基于要素加权的最终匹配点确定

对于每一个虚拟匹配点，首先判断其与定位点的直线距离是否超过阈值，如果超过阈值则剔除，如果在阈值范围内，则进一步采用基于要素加权的方式计算其综合匹配度。对所有能够获取的、并且对地图匹配精度产生影响的因素进行分析，最终选取距离和方向作为考虑要素。第个虚拟匹配点的综合匹配度计算公式为：

式中：——距离的权重系数;

——距离匹配度;

——方向匹配度;

——距离阈值，设置为40 m;

——定位点方向;

——虚拟匹配点所在路段;

——定位点与虚拟匹配点之间的直线距离;

——定位点方向与虚拟匹配点所在路段方向的夹角，。

对于每一个虚拟匹配点均计算一个综合匹配度，最后选取综合匹配度最大的点作为最终匹配点。

1.4 完整算法的流程图

2 实例分析

选取一小部分南京市城市路网作为研究对象，浮动车数据采样间隔为30 s，通过实现匹配过程，并将匹配路段分为普通路段和交叉口，结果如图4、5所示：

图中，“。”代表的是浮动车定位数据，“*”为浮动车地图匹配点。由图可知，普通路段共16个定位点，均准确匹配到道路上，匹配准确度100%，交叉口共7个定位点，其中6个准确匹配到道路上，匹配准确度85.7%。普通路段和交叉口的匹配时间分别为0.3 s和0.7 s，具有较好的响应速度。

3 结束语

本文提出一种改进的浮动车地图匹配算法，通过综合考虑要素加权与路网拓扑确定匹配路段，主要结论如下：

（1）基于网格法初步确定误差区域，提高了算法的运行效率，虽然网格范围较大，可能包含了与定位点距离超过阈值的点，但这些点可在后续步骤中快速判断和删除。

（2）对于存在前一匹配点的情况，根据道路拓扑关系缩小误差区域，同时完整保留匹配点可能存在的范围，减少了匹配到错误路段的概率。

（3）选取不同的权重系数会对结果产生不同影响，本文中采用了固定的权重系数，下一步将研究根据道路特征、车辆运行状态等动态调整权重系数，以期进一步提高算法精度。

参考文献：

[1]丁闪闪，王维锋，季锦章，等.一种城市快速路主辅道的浮动车地图匹配方法[P].中国发明专利，ZL201510259876.2，2015-05-20.

[2]孙棣华，张星霞，张志良.地图匹配技术及其在智能交通系统中的应用[J].计算机工程与应用，2005，42（20）：225-228.

[3]邹珍.基于GPS的浮动车数据与实地图匹配的算法研究[D].武汉理工大学，2013.

[4]曾嘉郦，孙立双，王晓明.北京出租车GPS轨迹数据地图匹配算法研究[J].北京测绘，2019，33（03）：255-260.