基于初始位置的高速公路快速地图匹配算法

滕志军，曲兆强，何义昌，佟育春，徐春雨，张丽伟

（1. 东北电力大学 信息工程学院，吉林 132012；2. 国网吉林供电公司 信息通信分公司，吉林 132000）

基于初始位置的高速公路快速地图匹配算法

滕志军1，曲兆强1，何义昌1，佟育春2，徐春雨2，张丽伟2

（1. 东北电力大学 信息工程学院，吉林 132012；2. 国网吉林供电公司 信息通信分公司，吉林 132000）

针对车辆行驶在高速公路过程中，传统地图匹配算法存在大量冗余检索时间，且消除垂直误差后仍存在水平误差等问题，设计了一种基于初始定位信息的快速地图匹配算法。该算法首先利用初始定位点到候选路段的距离与夹角确定车辆所行驶道路，然后考虑道路网拓扑结构和连通性，将后续定位点直接投影到初始确定的道路上，减少检索道路的时间；同时为提高算法的精确度，在引用初始定位信息时，通过设置距离阈值剔除定位数据漂移点，并利用一元线性方程建立HP模型以消除水平误差。经理论计算和实际测试表明，该算法利用初始获得的7个连续定位点，能准确检索出车辆正在行驶的道路，节省36%的检索时间，借助HP模型可以减少定位点与车辆实际位置之间45%的投影误差。因此，与连续匹配算法和垂直投影方式相比，该算法具有检索过程简单、检索准确率高、误差消除大的优势。

高速公路；初始信息；地图匹配；距离阈值；水平误差

地图匹配（Map Maching，MM）是一种新兴的通过软件来矫正定位误差的方法。该方法把车载端获得的定位信息与高精度的电子地图数据相结合，通过一定的匹配算法确定车辆所行驶的实际道路并将车辆位置准确显示在可视化地图上[1-2]。高速公路路网与城市街道路网相比，具有结构简单、交叉路口少、长距离单线行驶的特点。传统的基于权重、D-S证据推理、模糊识别、卡尔曼滤波的地图匹配算法在高速公路路网中都具有较好的性能[3-6]，但是基于D-S证据推理、模糊识别等的算法存在计算复杂程度高、匹配实时性偏低的缺陷，而基于距离和方向的地图匹配算法识别过程较简单，实时性强[7]，因此本文结合高速公路路网结构比较简单，车辆行驶连续性较强的特点，提出一种基于初始位置信息的高速公路快速地图匹配算法。

该算法主要利用车辆进入新路段的初始定位信息来确定车辆行驶道路。行驶道路确定后，若不出现交叉道路，对后续定位点不做匹配处理，直接将其投影到前一阶段所确定的道路上。到达交叉路口时，重新启动该算法完成路段确定。同时为了保证初始定位信息所确定候选道路的准确性，根据高速公路限速指标和定位误差设置阈值剔除定位漂移值。最后利用车辆的方向角和定位点坐标作线性方程消除水平误差保证车辆在水平移动过程中的精准性。

1 地图匹配基本原理

地图匹配技术中车辆行驶道路的确定要满足两个先决条件，一是待匹配的车辆正行驶在道路上，二是用作显示的电子地图精度要高于车辆定位误差。第一个条件在一般情况下是满足的；由于电子地图误差在5 m左右，北斗民用定位误差在15 m左右，第二个条件也是满足的。地图匹配完成两个主要过程：首先根据定位信息检索出车辆正在行驶的道路；其次就是矫正车辆定位点，将接收机接收的定位点显示在车辆所行驶的道路[8-10]。

为了更形象地描述地图匹配问题，假设车辆在道路A1行驶后经交叉路口驶入道路A2，车载接收设备获得的定位点为“○”，车辆实际位置为“●”，由图1可以看出，定位点集合为车辆实际位置为地图匹配算法就是通过一定规则确定车辆所行驶的道路，并将U··投影到U上。传统投影过程是直接做道路垂线，垂足为车辆显示位置，该方法只是消除了垂直误差，本文提出一种根据定位角度做斜线的投影方法来消除水平误差，而且由于各种误差原因，导致的定位漂移点（如点4·）可根据车辆速度、角度、硬件误差建立的阈值范围进行剔除，并根据定位信息进行插值（插值点为★）弥补缺失定位点。

图1 匹配原理示意图Fig.1 Schematic diagram of matching principle

2 算法实现框架

高速公路的路网不会存在复杂交叉路段，车辆会长时间在一条道路上行驶，因此地图匹配出现误匹配的情况很少发生。在基于传统高速公路地图匹配算法上，本文以基于距离和方向的地图匹配算法为基础，主要以提高算法效率和匹配精度两方面进行研究和改进。本文算法框架主要包括三个主要部分：①确定定位数据阈值范围，利用前一点角度和速度信息进行插值弥补剔除的定位点；②利用基于距离和角度的匹配算法，确定车辆行驶道路；③考虑有效定位点角度信息，确定车辆行驶方向，利用修正定位角度和坐标值作车辆投影点消除水平误差。下面详细介绍各个步骤。

2.1 设置阈值剔除漂移点并插值

目前的接收机具有修正部分随机误差的功能。对于由相对论效应、大气层延迟、多径效应引起的误差目前已有相应的解决方法，而且由于高速路处于较空旷地带，大型建筑物、密集树林半透明物体等干扰因素较弱。但是由于卫星瞬间失锁，或者高速路附近大型电力设备的影响，车辆接收的数据会出现突变的波动，即出现数据漂移现象，如图2所示，会有个别定位点不符合定位轨迹特性，出现远离道路的现象，设置阈值就是为了找出漂移点并做插值处理。

图2 定位数据漂移特征Fig.2 Positioning data drift characteristics

漂移值的主要特征是车辆定位点中的速度和经纬度信息出现异常，出现远离道路的异常情况，因此本文采用门限技术对漂移值进行甄别，通过设置一个距离阈值，对距离外的定位点剔除并插值，距离的阈值由速度和定位误差决定。首先得出浮动车的速度上限Vmax：

式中，Vmax为车辆速度显示上限，Vhmax为高速公路最高限速，Vs为卫星瞬时速度误差。故在速度限制下车辆最大距离偏移量为

其中：Δt为两个相邻定位点的时间间隔，由Vs带来的误差范围用误差圆来描述；r为一定置信水平下定位数据的误差圆半径，由此可得下一定位点的距离阈值，如图3所示。

图3 阈值范围示意图Fig.3 Schematic diagram of threshold range

距离阈值由两部分组成：

当出现漂移值时，利用车辆前一点速度和车辆方向进行插值，如图4所示。由于车辆获取定位点的频率较高，当车辆在弧线路段行驶时可以将道路看作短距离的直线路段，因此插值后定位点坐标为：

图4 插值原理图Fig.4 Interpolation principle

2.2 基于距离和方向的快速地图匹配算法

对缺失的定位点补全后，进行候选路段的确定，其中候选道路是在一定范围内选择的，该范围内包括的道路应包含车辆正在行驶的路段，令分别为车辆向东方向与向北方向定位误差的标准差，是方差，是协方差，则误差圆的半径R为：

如图5所示，pi为车辆定位点，虚线范围为误差圆。可以看出，在误差区域内存在三条候选道路而剔除掉三条道路，定位点在三条道路的投影点为，投影距离为di（i=1,2,3），通过投影距离以及车辆方向与道路方向夹角判断车辆所行驶的道路。

图5 误差圆示意图Fig.5 Error circle

一般车辆接收设备每隔 1～5 s接收一次定位点，由于车辆在高速公路行驶速度较快，车辆连续7个定位点的行驶距离所占候选道路的比重能保证算法的准确性，因此本文通过7个定位点的平均匹配程度来确定车辆行驶道路。假设iθ为道路方向与车辆方向夹角，为定位点到候选道路的距离，α和β是两个因素的权重，考虑高速公路道路弧度较小，可近似看作直线，因此本文地图匹配算法的综合评价函数为：

当车辆进入高速公路后，车载接收设备会在t1时刻获得第一个定位点。首先计算第一个定位点到各个候选路段的综合评价函数值，并将定位点暂时投影到匹配程度最高，也就是W值最低的路段；之后进行t2时刻定位点的匹配，从实际情况可以知道，t2时刻定位点所确定的候选范围内的道路与t1时刻所确定的候选路段差别不大，如果t2时刻出现新道路，可令t1时刻对该道路的匹配程度为 0，同时并将该时刻定位点投影到评价函数值最低的路段，同理对时刻定位点做相同处理；最后得出每条道路的平均匹配程度，选择最高平均匹配程度的道路，即W最低的路段作为车辆行驶道路。值计算公式为式(7)，选择

道路作为车辆正在行驶道路。路段确定后，将前7个点位点矫正投影到所确定道路上，之后的定位点不做匹配处理，直接将定位点投影到该条道路上，当出现交叉路口时，重新启动该算法，确定下一阶段要匹配的道路。

2.3 HP模型建立

车辆所行驶道路确定后，将定位点投影到所确定道路上，传统投影方式如图 6(a)所示，根据道路角度和车辆行驶角度将定位点PM投影到与道路的垂点P。该方式仅仅消除了车辆与道路间的垂直误差，车辆与道路间水平误差仍然存在，因此本文提出一种两直线相交的方式确定车辆在道路的准确位置，即建立一种水平投影（Horizontal Projection，HP）模型，如图6(b)所示，将车辆定位点所在直线与道路所在直线交点作为车辆的实际位置。

图6 垂直和水平投影示意图Fig.6 Schematic of vertical and horizontal projection

图6(b)中iθ和hθ分别是车辆行驶方向和道路方向与正北方向的夹角，由于高速公路道路角度波动较小，和iθ做车辆定位点所在直线方程YM，利用与之相近道路点可以将长距离道路近似为一条直线，若进入弧线道路，可通过较少数量路点构建直线方程，具体投影过程为：利用定位点和hθ做道路所在直线方程YG，先求联立方程：

在坐标系下，所求道路一般都与正北方向存在夹角，即斜率存在，因此所求交点即为方程组(10)的唯一解。求得位置参数后建立方程组：

求得解P(x,y)为两直线交点，

通过前7个定位点确定候选道路后，未出现交叉等判别路口时，便一直将该路段作为车辆行驶道路，仅仅将接收或修正的定位点水平投影到道路上，不用额外判断车辆行驶在哪一条道路。

3 算法测试

3.1 实测验证

为了验证本文算法的实际性能，选取吉林市绕城高速部分道路作为测试路线，车载定位模块采用北斗UM220模块，设定采样间隔为 2 s，地图为 MapInfo格式的吉林省道路数据，比例尺为 1︰200，两个权重分别设置为0.5，车辆首先进入岔口1，此时在候选区域内存在的三条候选道路从下向上记为经过岔口 2时将候选道路按照从下向上记为经过岔口3时将候选道路从左到右记作图7为车辆定位轨迹，可以看出，定位点分布于车辆行驶道路的两侧，有些定位点离不同道路距离很相近，单纯靠1个定位点匹配值确定实际行驶道路容易出现误差。

图7 车辆轨迹图Fig.7 Vehicle track

图8 匹配效果图Fig.8 Matching effect

图8为车辆匹配效果图，其中表1、2、3分别是前7个定位点在岔口1、2、3候选道路上匹配值。由表1看出，在t1时刻，定位点在A3道路匹配程度最高，但是7个定位点中，1A道路平均匹匹配值最低，故1A应是车辆行驶道路；在表2中，候选道理B1匹配值最低，即B1为车辆行驶道路；在表3中，从平均匹配值中可以看出C2道路为候选道路，从单点匹配值中也能得出相应结果，但从平均匹配值可以消除靠单点来确定道路的不确定性。

3.2 仿真比较

为了验证本文算法的快速性和误差消除情况，对三种算法进行仿真比较。仿真条件设置为候选道路条数固定，固定为三条，前1000 m是本文算法初始确定车辆行驶道路阶段。仿真结果如图9所示。可以看出，在前1000 m内本文算法相对其它算法匹配时间相当，这是因为本文算法在水平投影过程中要复杂些，但是车辆驶出1000 m后，由于本文算法不需重新检索道路，单点平均匹配时间降至 3.6 ms，而其它两种算法均在5.5 ms左右，相对于其它算法节省36%的冗余时间。系统的误差包括车辆定位点到车辆实际位置的垂直误差和水平误差。由图10可以看出，仅通过垂直投影只能消除30%左右的定位误差，通过水平方式的投影可以消除车辆实际行驶位置与匹配点之间大约45%的误差，相对其他算法匹配准确度有较明显提高，因此本文算法不仅具有时间上的快速匹配特点，还可以最大限度地消除定位误差，保证车辆在道路行驶的连续性。

图9 时间比较Fig.9 Time comparison

图10 误差消除仿真Fig.10 Simulation on error elimination

表1 岔口1候选道路匹配值Tab.1 Candidate road matching values at Fork 1

表2 岔口2候选道路匹配值Tab.2 Candidate road matching values at Fork 2

表3 岔口3候选道路匹配值Tab.3 Candidate road matching values at Fork 3

4 结 论

针对高速公路结构简单的特点，本文提出一种基于车辆初始定位信息的高速公路快速地图匹配算法。该算法在通过初始定位信息确定候选道路后，若不出现交叉道路，则将后续定位点直接投影到所确定的道路上，大大节省了不必要的匹配时间。同时，该算法通过设置阈值降低检索候选道路的时间和建立HP模型减少了水平误差。实测结果表明，该算法能准确地确定车辆的行驶道路，节省了车辆直线行驶时不必要的检索道路所需的时间。

（References）：

[1]李清泉, 胡波, 乐阳. 一种基于约束的最短路径低频浮动车数据地图匹配算法[J]. 武汉大学学报（信息科学版), 2013, 38(7): 805-808.Li Qing-quan, Hu Bo, Le Yang. A data map matching algorithm based on constrained shortest path low frequency floating car[J]. Geomatics and Information of Wuhan University, 2013, 38(7): 805-808.

[2]Yang Xin-yong, Huang Sheng-guo. Quick road choice method in map matching algorithms[J]. Journal of South China University of Technology, 2016, 32(2): 62-66.

[3]Ma Chun-yang, Zhang Xin, Gao Peng. Space-map-matchingbased candidate selection for GPS map matching[C]//2016 IEEE International Conference on Service Operations and Logistics, and Informatics. 2016: 77-82.

[4]Peker A U, Tosun O, Akin H L, et al. Fusion of map matching and traffic sign recognition[C]//IEEE Intelligent Vehicles Symposium. 2014: 867-872.

[5]Berry J W, Fleischer L, Hart W E, et al. Sensor placement in municipal water networks[J]. Journal of Water Resources Planning & Management, 2005, 131(3): 237-243.

[6]王新龙, 于洁. 基于矢量跟踪的SINS/GPS深组合导航方法[J]. 中国惯性技术学报, 2009, 17(6): 710-717.Wang Xin-long, Yu Jie. Deeply SINS/GPS integrated navigation method based on vector tracking[J]. Journal of Chinese Inertial Technology, 2009, 17(6): 710-717.

[7]Komiya K, Miyashita S, Maruoka Y, et al. Control of autonomous mobile robot using map matching with optimized search range[J]. Electrical Engineering in Japan,2015, 190(4): 66-75.

[8]Li Liang, Quddus M, Zhao Lin. High accuracy tightlycoupled integrity monitoring algorithm for map-matching[J]. Emerging Technologies, 2013, 36(3): 13-26.

[9]Su Hai-bin, Wang Guang-zheng, Wang Ji-dong. Map matching algorithm based on fuzzy neural networks[J].Journal of University of Science and Technology Beijing,2012, 34(1): 43-47.

[10]孟阳, 高社生, 高兵兵, 等. 基于UFK的INS/GNSS/CNS组合导航最优数据融合方法[J]. 中国惯性技术学报, 2016, 24(6): 746-751.Meng Yang, Gao She-sheng, Gao Bing-bing, et al. UFK-based optimal data fusion method for integrated INS/GNSS/CNS[J]. Journal of Chinese Inertial Technology,2016, 24(6): 746-751.

Fast map-matching algorithm for highway based on initial position

TENG Zhi-jun1, QU Zhang-qiang1, HE Yi-chang1, TONG Yu-chun2, XU Chun-yu2, ZAHNG Li-wei2
(1. Department of Information Engineering, Northeast Dianli University, Jilin 132012, China;2. Communication Branch, State Grid JiLin Power Supply Company, Jilin 132011, China)

The traditional map-matching algorithms have large amount of redundant retrieval time, and the horizontal error still exists after eliminating the vertical error. To solve these problems, a fast map-matching algorithm based on initial location information is designed for the vehicle traveling in the expressway. First,the algorithm uses the distance and the angle between the initial positioning point and the candidate road section to determine the vehicle’s running road. Then, considering the road network topology and connectivity, the subsequent positioning point is directly projected onto the initial determined road to reduce the time of searching the road. In order to improve the accuracy of the algorithm, when the initial location information is referenced, the drifting data is removed by setting the distance threshold, and the HP model is established by using the univariate linear equation to eliminate the horizontal error. Theoretical calculation and actual test show that, the proposed algorithm can accurately retrieve the road where the vehicle is traveling and save 36% of the retrieval time by using the seven consecutive positioning points, and the HP model can reduce 45% of the projection error between the positioning point and the actual position of the vehicle.Compared with traditional map-matching algorithms, the proposed algorithm has the advantages of simple retrieval process, high retrieval accuracy, and significant reduction of horizontal error.

express way; initial information; fast map matching; threshold of distance; horizontal error

1005-6734(2017)04-0461-05

10.13695/j.cnki.12-1222/o3.2017.04.007

P208

A

2017-04-17；

2017-07-25

国家自然科学基金项目（51277023）

滕志军（1973—），男，教授，研究方向为无线通信技术。E-mail: 753731087@qq.com