一种地图匹配算法的设计与实现

李殿茜,王 翌,刘 垒,刘 辉

(北京自动化控制设备研究所,北京100074)

一种地图匹配算法的设计与实现

李殿茜,王 翌,刘 垒,刘 辉

(北京自动化控制设备研究所,北京100074)

设计一种面向定位定向导航系统的地图匹配算法,首先通过网格划分和建立路段连通性拓扑关系表对电子地图数据进行预处理；然后根据车辆的行驶状态采取不同的候选路段确定方法, 计算各候选路段的匹配度,取值最大的作匹配路段；最后采用垂直投影法求取匹配点。通过跑车数据进行仿真试验,验证了该算法具有良好的准确性和实时性。

地图匹配；网格划分；拓扑关系；匹配度；候选路段；正交投影

0 引言

随着车载导航技术的发展,各种导航定位技术在车载导航系统中都得到了成功的应用,例如GPS定位技术、惯性导航技术(Inertial Navigation System,INS)、航位推算技术(Dead Reckoning,DR)、无线电技术等,但每一种技术都有其无法克服的局限性。而采用地图匹配技术(Map Matching)提升定位定向系统导航精度,具有不需要增添新的硬件、成本低、能有效抑制误差发散等优点。因此,对地图匹配相关技术展开研究具有重要意义。

地图匹配是一种基于软件技术的定位误差修正技术,依靠精确的电子地图和完善的地图匹配算法实现道路信息与车辆定位信息之间的匹配。然后根据匹配结果,校正系统的定位输出,从而获取车辆正确的位置信息[1]。图1所示为地图匹配原理图。

图1 地图匹配原理图Fig.1 Map matching principle diagram

一个完整的地图匹配算法一般包括3个过程：一是确定误差区域,找出车辆附近的所有候选路段；二是从所有候选路段中确定车辆当前所在路段,即匹配路段；三是确定车辆在当前路段上的具体位置,即匹配点。现有的一些地图算法中,算法简单的,匹配精度低,准确性差；匹配准确性较好的算法,结构复杂,计算量大,匹配实时性差[2]。因此,在保证相对较高的匹配精度的同时,最大程度提高匹配效率将成为地图匹配算法研究的重点。

本文以车载导航系统提供的车辆位置姿态信息为样本,以shapefile格式电子地图道路信息为模板,提出一种综合车辆位置、航向信息以及路段拓扑关系的地图匹配算法,具有良好的实时性和准确性。

1 地图数据预处理

在上述提到的地图匹配3个过程中,确定候选路段的范围是影响匹配效率的主要因素。尤其在匹配开始阶段,因为没有历史信息可以利用,也不知道大致范围,所以在寻找车辆当前所在路段时要遍历搜索大量的路段,大大影响匹配效率。另外,候选路段数量如果很大,匹配出错的概率也会增加,从而影响匹配精度。因此,为了快速准确地确定候选路段,在匹配开始前对电子地图数据进行预处理,具体做法是地图网格区域划分和建立路段间连通性拓扑关系表。

1.1 地图网格划分

将电子地图自左而右、自下而上按固定步长划分成M×N个网格区域,并且每个网格都有唯一的编号,其中M、N分别代表网格的行数和列数。如图2所示,设电子地图左下角顶点和右上角顶点坐标分别为(X1,Y1)和(X2,Y2),则网格划分时纬度和经度方向的步长分别为hx、hy以及定位点(xo,yo)所在网格编号A由式(1)确定。

(1)

其中,[ ]为取整。

图2 地图网格划分及编号Fig.2 Map mesh division and mesh number

判断路段与网格关系,将位于网格内以及与网格边界相交的路段都认为属于该网格。建立网格-路段索引表,使得通过网格编号可以快速索引出属于该网格的所有路段的编号[3]。因此,在匹配初始时刻确定候选路段时,只要确定定位点所在网格就可以从属于该网格的路段中进行筛选,不需要遍历电子地图中所有的路段,从而大大减少了算法的计算量,提高算法效率。

1.2 建立拓扑关系表

Shapefile格式电子地图是一种无拓扑的矢量数据结构,即只存储了路段的位置信息和属性信息,并没有表示路段与路段之间的拓扑关系[4]。我们认为,由于车速是有限的,所以在一定时间范围内,车辆离开上一匹配路段后,只能行驶在与之相连的路段,而不可能在其他路段上行驶。所以,本文根据电子地图道路数据建立了路段间的连通性拓扑关系表(见表1)。

表1 路段间连通性拓扑关系格式

当车辆离开上一时刻的匹配路段时,利用路段节点,从拓扑关系表中找到对应的路段作为候选路段进行匹配,从而节省了寻找候选路段的搜索时间,并且可以减少误匹配现象的出现。

2 算法的设计与实现

2.1 候选路段的确定

根据车辆行驶状态的不同,候选路段的选取准则也不同,可分为下面3个状态：

1)初始状态,初始时刻没有历史信息可以利用,此时确定定位点所在网格,取网格内所有路段作候选路段。

2)跟踪状态,若此刻车辆没有离开上一时刻确定的匹配路段,则该路段即为此刻车辆的候选路段也就是匹配路段。相较于上一时刻,匹配路段没有变化。

3)更新状态,若车辆离开上一时刻的匹配路段,则查询拓扑关系表,找到和上一路段相连通的所有路段作为候选路段,匹配结果将是对上一时刻匹配路段的更新[5]。

设车辆定位坐标为(xo,yo),某一路段的起止节点用(x1,y1)和(x2,y2)表示。由式(2),当满足0<η<1且d<ε(ε为设定的阈值,文中取30m)时,认为车辆没有离开该路段。

(2)

2.2 匹配路段的确定

设某一时刻定位点到候选路段的距离为di,车辆行驶航向与路段方向夹角为Δθi,则定义匹配度fi,有

(3)

其中,wd、wθ分别表示距离因素和方向因素在匹配度中的权重系数,满足wd+wθ=1(本文中均取0.5)。由式(3)可知,定位点到路段的距离越小,车辆行驶航向和路段方向夹角越小则匹配度越大,说明该路段是当前车辆所在道路的可能性就越大[6]。因此,在匹配过程中,求出定位点对于各个候选路段的匹配度,取匹配度最大的候选路段为车辆的匹配路段。

2.3 路段上匹配点的确定

匹配路段确定后,将车辆定位点向匹配路段上做投影,投影点作为车辆在路段上的匹配点[7]。匹配点(xp,yp)求取如下：

(4)

2.4 算法步骤和流程

图3 地图匹配算法流程图Fig.3 Map matching algorithm flow chart

算法的流程如图3所示。算法的实现步骤如下：

步骤1：载入电子地图,对地图数据进行预处理。

步骤2：读入导航系统提供的定位数据。

步骤3：判断上一时刻匹配是否成功,若成功,利用式(2)计算η和d；否则跳转至步骤6。

步骤4：判断车辆是否离开了上一时刻匹配路段,如果是,索引拓扑关系表,找到候选路段；否则匹配路段没变,跳转至步骤8。

步骤5：判断拓扑关系表中候选路段数目N,若N=1,则该路段就是匹配路段,跳转至步骤8；若N>1,这N条路段为候选路段。

步骤6：利用式(1)确定定位点所在网格区域,取网格内所有路段为候选路段。

步骤7：利用式(3)求取各候选路段的匹配度,比较匹配度大小确定匹配路段。

步骤8：向匹配路段上做正交投影,投影点作为车辆的匹配点。

3 试验验证

利用定位定向导航系统跑车数据在Matlab仿真工具上对地图匹配算法进行仿真试验验证。图4～图7所示为匹配结果的图像显示,蓝点代表车辆的定位点,红点代表匹配点。

图4 全程匹配效果图Fig.4 Full matching effect chart

图5 单/双行线变换路段匹配效果图Fig.5 Transformation between single line and double line

图6 转弯匹配效果图Fig.6 Intersection turn matching effect chart

图7 平行路段匹配效果图Fig.7 Parallel section matching effect chart

从表2可以看出,匹配成功率为99.5%,匹配正确率达到97.2%,表明该算法具有较好的匹配准确性。表3所示为在初始状态、跟踪状态和更新状态下匹配单个定位点用的时间,以及整个匹配总时间。不难看出该匹配算法可以满足一定的准确性和实时性要求。

表2 匹配准确性统计表

表3 匹配时间统计表

4 结论

确定候选路段时所遍历的路段数目的多少直接影响地图匹配算法的效率,通过对道路电子地图进行网格划分并且建立路段间连通性拓扑关系,可以快速地确定出候选路段的范围。引入匹配度计算,综合考虑车辆和路段之间的距离因素和方向因素,可以准确地确定匹配路段。将定位点往匹配路段做正交投影,取投影点作匹配点,有效地消除了垂直与道路方向上的定位误差,提高了匹配精度。

[1] 刘兴权,金美含.地图匹配算法综述[J].科技信息,2014(4):64-65.

[2] Miwa T, Kiuchi D, Yamamoto T, et al. Development of map matching algorithm for low frequency probe data [J]. Transportation Research Part C Emerging Technologies, 2012,22(5): 132-145.

[3] 李英飞.车载导航系统中数据处理与地图匹配技术研究[D].哈尔滨工程大学,2012.

[4] 周长英,陈颖.空间数据库索引技术发展概况[J].黑龙江科技信息,2010(31)：84.

[5] 梁贞.基于权重的线到线地图匹配算法的研究[D].北京交通大学,2006.

[6] 苏海滨,徐俊红,程志冲.基于权重的改进综合地图匹配算法[J].中南大学学报,2011(9):773-777.

[7] Karimi H A, Conahan T, Roongpiboonsopit D.A methodology for predicting performances of map-matching algorithms[C]//International Symposium on Web and Wireless Geographical Information Systems. Springer Berlin Heidelberg, 2006: 202-213.

The Design and Implementation of a Map Matching Algorithm

LI Dian-xi, WANG Yi, LIU Lei, LIU Hui

(Beijing Institute of Automatic Control Equipment,Beijing 100074,China)

A map matching algorithm based on orientation navigation system is designed. The data of the electronic map is preprocessed by mesh division and building the topological relations between the sections. Then, according to driving state of the vehicle, a method of determining different candidate sections is designed. The calculated maximum of matching degree is taken as the matching section, and the projection point is used as the matching point. By using the data of vehicle experiment, the map matching algorithm is proved to have good accuracy and real-time performance.

Map matching; Mesh division; Topological relation; Matching degree; Ortho-perspective

2016-11-15；

2017-02-01

解放军总装备部预先研究项目(51309030104)

李殿茜(1989-),男,硕士,主要从事面向定位定向的地图匹配技术方面的研究。E-mail: lidianxii@126.com

10.19306/j.cnki.2095-8110.2017.02.006

U666.1

A

2095-8110(2017)02-0031-04