基于道路信息的智能地图匹配算法

李磊磊，陈家斌，杨黎明，尹静源，胡鸣凯，高宏斌

（1. 北京理工大学 自动化学院，北京 100081；2. 华北光学仪器有限公司，北京100053；3. 北京机电工程总体设计部，北京100039）

基于道路信息的智能地图匹配算法

李磊磊1，陈家斌1，杨黎明2，尹静源3，胡鸣凯1，高宏斌1

（1. 北京理工大学 自动化学院，北京 100081；2. 华北光学仪器有限公司，北京100053；3. 北京机电工程总体设计部，北京100039）

针对军用车辆长时间、长距离高精度自主导航需求，提出了一种基于道路信息的智能地图匹配算法。传统地图匹配算法在单独使用时，都会存在一些不足之处。智能地图匹配算法比较不同算法的优缺点，选择三种特点鲜明、互补性强的地图匹配算法作为基础算法，以惯性导航系统提供的导航信息为基础，对车辆正在行驶的道路进行识别和判断，根据道路构成情况自动选择合适的算法，完成地图匹配；并结合车辆行驶的航向和速度信息选择椭圆形道路搜索区域。试验车进行5 h约240 km跑车试验，地图匹配定位精度约为10.33 m（CEP）。试验结果证明该算法能够适应不同的道路状况，有效抑制惯性导航误差发散。

地图匹配；惯性导航；航迹推算；电子地图

导弹发射车需要具备远距离奔袭作战能力，这就要求为其装备的导航系统能够长时间、长距离保持较高定位精度。传统的惯性导航系统由于惯性器件误差发散，无法满足要求。在不考虑卫星导航辅助情况下，运用地图匹配技术[1-2]，以惯性导航信息为基础，搜索车辆周围的路径信息，确定车辆正在行驶的道路，并通过地图数据库中道路坐标信息对车辆位置进行修正，从而抑制导航误差发散，以满足长时间高精度定位要求。

现在常用的地图匹配算法有基于投影的匹配算法[3-5]、基于相关性的匹配算法[6]、基于模糊逻辑的匹配算法[7-8]、基于网络拓扑关系的匹配算法[9-10]以及基于D-S证据推理[11-13]地图匹配算法等。这些匹配算法在单独使用时，都会有一些不足之处。基于投影的匹配算法逻辑简单、速度快、实时性好，但在道路密集、道路形状复杂和交叉路口等情况下，匹配准确率较低；基于相关性的匹配算法在匹配路段特征比较明显时才具有较好匹配效果；基于模糊逻辑的匹配算法准确率高，但算法复杂，所需时间较长，计算量较大，很难满足车辆定位的实时性要求；基于网络拓扑关系的匹配算法能减少匹配道路搜索范围，但其匹配效果有时会受到空间拓扑关系质量的影响等等。

因此，本文提出了一种基于道路信息的智能地图匹配算法。地图匹配是以惯性导航系统提供的导航信息为基础，对车辆正在行驶的道路进行识别和判断，车辆所在大概位置是已知的，可充分利用该信息对车辆周围的道路情况进行预判，根据不同的道路场景选择合适的地图匹配算法，提高匹配的实时性和准确度。

1 地图匹配系统组成

地图匹配系统由惯性寻北仪、方位保持仪、高程计、里程计、导航显示器、导航计算机和电子地图组成，如图1所示。其中，惯性寻北仪、方位保持仪、高程计和里程计组成航迹推算系统（DR系统）。惯性寻北仪在载体静止的工作条件下自动完成北向基准和载体姿态角的测量，为系统提供初始方位角；方位保持仪完成北向方位基准的记忆，并敏感载体运动时航向角的变化；里程计敏感载体行驶距离，为导航解算提供里程信息；高程计测量载体的高程信息，使系统具有三维定位功能。航迹推算系统完成导航解算后，与电子地图数据相结合，实现匹配导航。

图1 地图匹配系统Fig.1 Map matching system

2 智能匹配算法

2.1 道路搜索区域

地图匹配中候选道路搜索区域选择非常重要，区域过大可能会增加搜索道路的计算量，区域过小则可能漏掉正确的道路。传统道路搜索区域是选定以车辆当前位置为中心的圆形或矩形区域，本文结合多年积累的试验数据，选择以行车方向为长轴的椭圆形区域作为道路搜索区域，具体如图2所示。

Fig.2 道路搜索区域示意图Fig.2 Road searching area

图2中，a为椭圆形道路搜索区域长半轴，b为短半轴，Ψ为椭圆形区域长半轴与北向夹角，即车辆行驶方向。基于航迹推算系统定位误差和车辆行驶速度考虑，选取椭圆长半轴a和短半轴b为

2.2 匹配算法

在不同道路场景中，有效的地图匹配算法也不相同。在传统算法中选取几种特点鲜明、互补性强的地图匹配算法作为基础算法，根据车辆正在行驶区域的道路信息，自动选择合适的匹配算法。本文选取的基础算法包括基于投影的匹配算法、基于相关性的匹配算法和基于模糊逻辑的匹配算法。

2.2.1 基于投影的匹配算法

基于投影的匹配算法设计简单，实时性好，适合道路情况比较简单的区域。算法原理如图3所示。

图3中，P点为待匹配的定位点，L1、L2表示定位点附近的道路。在投影匹配算法中，把待匹配的定位点向附近所有道路做投影，计算定位点与各道路间的投影距离ri及车辆行驶方向与道路间的夹角θi。 选出ri、θi值小于给定阈值的所有道路，并根据公式(4)计算各候选道路的距离度量值Ri：

Fig.3 基于投影的地图匹配算法Fig.3 Map-matching algorithm based on projection

式中：Wr、Wθ分别是投影距离和方向夹角的权值。

在所有候选道路中，选择距离度量值最小的作为匹配道路，即认为车辆正在该道路上行驶。最后将车辆在匹配道路上的投影点作为车辆的当前位置。

2.2.2 基于相关性的匹配算法

相关性地图匹配算法是将采集到的车辆位置点按照顺序组成定位轨迹，并将定位轨迹与数字地图中的路段曲线轨迹进行计算获得两者的相关系数，依据相关系数来判定轨迹与路段的相似性。

设航迹推算车辆行驶的轨迹为s，待确定的道路轨迹为li(i=1,2,…,n)。采用相关性算法计算出航迹推算轨迹与待确定道路轨迹的相关性系数ρi：

式中：k为采样点，σs和分别为道路轨迹序列s（k）的标准差。ρi值较大则表明车辆行驶轨迹和该路段相关性比较高，车辆很可能正在该段道路行驶。基于相关性的地图匹配算法适合具有比较明显道路信息特征的路段，比如岔路口拐弯处或角度变化比较大的曲线路段。

2.2.3 基于模糊逻辑的匹配算法

基于模糊逻辑的地图匹配算法引入模糊逻辑评判规则，然后在评判规则的基础上定义模糊隶属度函数，最后依据模糊隶属度函数，评判候选路段是否是车辆所行驶的路段。地图匹配算法是对不确定的问题进行定性决策，因此使用基于模糊逻辑的地图匹配算法较几何运算具有更好的鲁棒性。匹配算法的模糊推理系统示意图如图4所示。

Fig.4 模糊推理系统示意图Fig.4 Schematic of fuzzy inference system

车辆位置距离该路段的隶属函数为

车辆航向与路段方向的差异的隶属函数为

式中：MF1是车辆位置距离该路段的隶属度；MF2是车辆航向与该路段方向之间的差异的隶属度。规则 2只有在规则1的输出超过设定的阈值时才评估，否则重复执行这一步直到相似性超过设定的阈值。

规则 2：如果该路段与当前行驶路段相似性在连续的几个时间点中都很高，那么可以认为该路段是当前行驶路段。

2.3 匹配流程

智能地图匹配算法首先根据航迹推算提供的基础坐标，结合车辆正在行驶的航向和速度信息，确定候选道路搜索的区域；然后，分析搜索区域内道路构成情况，选择合适的地图匹配算法；最后，通过选定的匹配算法完成地图匹配，并对导航坐标进行修正。

当道路搜索区域道路构成比较简单时，选择基于投影的匹配算法进行匹配；当搜索区域道路信息有比较明显的信息特征时，选择基于相关性地图匹配算法进行匹配；当搜索区域道路信息比较复杂时，选择基于模糊逻辑地图匹配算法进行匹配。匹配算法流程如图5所示。

模糊推理系统使用的规则如下：

规则 1：如果车辆位置距离该路段很近并且当前车辆航向与该路段方向之间的差异很小，那么这条路段与当前行驶路段相似性由下式给出：

Fig.5 匹配算法流程Fig.5 Flowchart of matching algorithm

3 试验验证

3.1 算法效果匹配

选择三种具有代表性的路段对匹配算法进行验证。三种路段分别是简单直行路段、转弯路段和较为复杂路段。智能算法会自动选择基于投影匹配算法、基于相关性匹配算法和基于模糊逻辑匹配算法，匹配效果如图6～8所示。

Fig.6 直行路段匹配效果Fig.6 Matching effect in straight line section

Fig.7 转弯路段匹配效果Fig.7 Matching effect in turning section

Fig.8 复杂路段匹配效果Fig.8 Matching effect in complex section

3.2 导航试验

为了验证地图匹配算法长时间对惯导误差的抑制效果，设计了沿北京市三环路线的跑车试验。沿途停靠8个位置点，分别是苏州桥、新兴桥、丰益桥、木樨园桥、十里河桥、国贸桥、三元桥和马甸桥。在每个停靠点记录匹配坐标。以车上装载的高精度实时差分GPS作为基准，计算匹配坐标误差。试验连续绕行三环主路5圈，试验持续时间超过5 h，行驶里程约240 km。跑车路线图如图9所示，匹配坐标误差见表1。

导航坐标系选用东北天坐标系，X、Y分别表示北向和东向。通过表1数据计算地图匹配系统定位精度为 10.33m（CEP）。从误差分布来看，导航误差并没有因为跑车时间和跑车距离的增加而呈现出明显发散趋势，说明地图匹配算法对惯性误差积累起到很好的抑制作用。

Fig.9 试验路线图Fig.9 Experiment roadmap

表1 定位误差试验数据Tab.1 Positioning error test data

4 结 论

为适应导弹发射车长航时高精度自主导航要求，提出了一种基于道路信息的智能地图匹配算法。该算法根据航迹推算获取的坐标确定车辆所在大致区域，基于此区域道路构成状况自动选择合适的地图匹配算法，并在确定道路搜索范围时，考虑航向和速度信息选择椭圆形搜索区域。跑车实验结果证明，该算法能够适应不同的道路状况，可以较好抑制导航误差发散，具有重要工程实用价值。

（References）：

[1] Hashemi M, Karimi H. A critical review of real-time map-matching algorithms: Current issues and future directions[J]. Computers, Environment and Urban Systems, 2015, 11: 153-165.

[2] Chen W, Li Z, Yu M, et a1. Effects of sensor errors on the performance of map matching[J]. Journal of Navigation, 2005, 58(02): 273-282.

[3] Bierlaire M, Chen J, Newman J. A probabilistic map matching method for smartphone GPS data[J]. Transportation Research Part C: Emerging Technologies, 2013, 2: 78-98.

[4] 王忠民, 王青, 张荣, 等. 一种基于位置点的地图匹配改进算法[J]. 计算机应用研究, 2013, 30(11): 3318-3323. Wang Zhong-min, Wang Qing, Zhang Rong, et al. Improved map-matching algorithm based on position points[J]. Application Research of Computers, 2013, 30(11): 3318-3323.

[5] 孙永荣, 黄斌, 王丽娜, 等. 抗尺度变换的矢量地图匹配导航方法[J]. 中国惯性技术学报, 2013, 20(1): 89-92. Sun Yong-rong, Huang Bin, Wang Li-na, et al. Vector map matching navigation method with anti-scale transformation[J]. Journal of Chinese Inertial Technology, 2013, 20(1): 89-92.

[6] 龚柏春, 罗建军, 李岁劳, 等. 基于移动相关的最小二乘地图匹配新算法[J]. 中国惯性技术学报, 2012, 20(4): 435-439. Gong Bai-chun, Luo Jian-jun, Li Sui-lao, et al. Novel map-matching algorithm based on moving-related least squares[J]. Journal of Chinese Inertial Technology, 2012, 20(4): 435-439.

[7] He Z, Xi-wei S, Zhuang L, et al. On-line map-matching framework for floating car data with low sampling rate in urban road networks[J]. IET Intelligent Transport Systems, 2013, 7(4): 404-414.

[8] Quddus M, Washington S. Shortest path and vehicle trajectory aided map-matching for low frequency GPS data[J]. Transportation Research Part C: Emerging Technologies, 2015, 6: 328-339.

[9] 赵东保, 刘雪梅, 郭黎. 网格索引支持下的大规模浮动车实时地图匹配方法[J]. 计算机辅助设计与图形学学报, 2014, 26(9): 1550-1556. Zhao Dong-bao, Liu Xue-mei, Guo Li. Real time map matching algorithm of floating car in support of spatial grid index[J]. Journal of Computer Aided Design & Computer Graphics, 2014, 26(9): 1550-1556.

[10] 韩萍, 桑威林, 赵爱军, 等. 基于单向无迹卡尔曼滤波的飞机姿态算法[J]. 中国惯性技术学报, 2014, 22(5): 629-633. Han Ping, Sang Wei-lin, Zhao Ai-jun, et al. Simplex unscented Kalman filter for aircraft attitude algorithm[J]. Journal of Chinese Inertial Technology, 2014, 22(5): 629-633.

[11] Huang J, Qie JH, Liu CW, et a1. Cloud computingbased map-matching for transportation data center[J]. Electronic Commerce Research and Applications, 2015, 14(6): 431-443.

[12] Kim K, Seol S, Kong S H, et a1. High-speed train navigation system based on multi-sensor data fusion and map matching algorithm[J]. International Journal of Control Automation and Systems, 2015, 13(3): 503-512.

[13] 肖维丽, 岳春生, 奚玲. 基于高程的改进D-S证据理论地图匹配算法[J]. 计算机应用与软件, 2015, 32(7): 262-265. Xiao Wei-li, Yue Chun-sheng, Xi Ling. Improved D-S evidence theory map matching algorithm based on elevation information[J]. Computer Applications and Software, 2015, 32(7): 262-265.

Intelligent map-matching algorithm based on map information

LI Lei-lei1, CHEN Jia-bin1, YANG Li-ming2, YIN Jing-yuan3, HU Ming-kai1, GAO Hong-bin1

(1. School of Automation, Beijing Institute of Technology, Beijing, 100081 China; 2. Huabei Optical Instrument Co., LTD, Beijing 100053, China; 3. Beijing Electro-mechanical Engineering System Design Department, Beijing 100039, China)

In view of the military vehicle’s long-time, long-distance and high-precision autonomous navigation requirements, an intelligent map-matching algorithm based on road information is proposed. Traditional map-matching algorithms have some shortcomings when used alone. Three distinct characteristics and highly complementary map matching algorithms are picked out as the basic algorithms for intelligent map-matching algorithm by comparing the advantages and disadvantages of them. The road information is identified and judged based on inertial navigation information. An appropriate algorithm is automatically selected for map matching according to the road conditions. And the elliptical path search area is selected based on the vehicle's heading and speed information. The map matching positioning accuracy is 10.33 m (CEP) while the vehicle test is carried out by more than 5 h over approximate 240 km. Experimental results show that the algorithm can be adapted to different roads, and can effectively restrain the inertial navigation error’s diverges.

map-matching; inertial navigation; dead reckoning; electronic map

U666.1

A

1005-6734(2016)02-0170-05

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

2015-12-02；

2016-03-18

国防预研基金（9140A09050313BQ01127）；国家自然科学基金（91420203）

李磊磊（1978—），男，博士，讲师，研究方向导航、制导与控制。E-mail: lileilei@bit.edu.cn