一种利用网格划分及方向加权的地图匹配算法

廖 佳，俞荐中，李俊峰

(1. 宁波市测绘设计研究院，浙江 宁波 315042； 2. 宁波市规划与地理信息中心，浙江 宁波 315042)

一种利用网格划分及方向加权的地图匹配算法

廖 佳1，俞荐中2，李俊峰1

(1. 宁波市测绘设计研究院，浙江 宁波 315042； 2. 宁波市规划与地理信息中心，浙江 宁波 315042)

地图匹配算法目的是将偏离道路的点纠正到正确位置上。本文基于传统的点到线的地图匹配算法，通过引入网格划分的概念来确认候选匹配道路，并且加权了方向因素来计算点到线的匹配程度。试验表明，改进后的算法能够提高其准确性，并且一定程度上提高了算法的效率，具有一定的实用价值。

网格划分；方向加权；地图匹配

随着移动定位技术的发展及移动定位终端的普及，每时每刻都积累着大量的定位数据。但由于定位精度的问题，必须将有误差的数据进行纠正，使其重新定位到正确的位置。地图匹配算法正是为了解决这一问题而出现的。由于定位数据一般规模较大、道路数据也相对复杂，地图匹配算法在准确度与效率上很难达到理想的效果。本文通过网格划分的思想，并加入方向权重，对传统的点到线的匹配算法进行改进，成功提高了算法准确度及效率。

1 地图匹配基本理论

地图匹配就是将偏离图上道路的轨迹点数据纠正后，使其重新定位到正确的道路上的过程。由于出租车GPS采集到的位置点数据存在精度误差，因此，轨迹点很可能偏离道路，落在不合理的地方，如道路旁的建筑物、广场甚至河流湖泊等。而这样的误差对后期的数据挖掘工作有很大影响。因此，有必要对采集后的轨迹点数据进行地图匹配。

地图匹配算法的一般步骤为：①确定车辆轨迹点所在的路段；②确定车辆轨迹点在该路段的具体位置。其中，确定车辆轨迹点所在路段最为关键。通常确定的原理是，在轨迹点的一定邻域范围内搜索候选的待匹配道路，然后计算轨迹点与这些待匹配道路的匹配度(也称为相似度)，最后选择匹配度最大的路段作为匹配道路。典型的地图匹配方法主要有以下几种：

1.1 几何分析法

几何分析法又分为以下几类：点到点的匹配，点到线的匹配，线到线的匹配。点到点的匹配，即搜索路网数据中所有的点，计算所有点与带匹配点的距离，用距离最近点的坐标替换带匹配点原有的坐标。点到点的匹配非常简单便捷，几乎是所有匹配算法中最简单的。但是点到点的匹配与路段之间点的密集程度密切相关，当出现路段长度较长且路段之间的点分布不多时，该算法的匹配精度大大降低。如图1所示，P点应该匹配到MN道路上，但是由于MN之间并没有许多能够匹配的点，而附近有一条相距更远的道路AG，并且P到点D上的距离最短，因此，按照点到点匹配算法，该点P将被匹配到AG道路上的D点位置上，由此产生了错误匹配。

图1 点到点匹配缺陷

点到线的匹配即计算待匹配点到候选匹配道路之间的距离，由最近距离确定匹配道路，而该点到道路的投影点即为匹配点。

该方法虽然与道路中间点的多少无关，但如果出现点到几条道路距离相等，或十分接近的情况，也很难判断应该匹配到哪条道路上。如图2所示，待匹配点P到道路A、B的距离相同，则无法判断P应该匹配到哪条道路上。

图2 点到线匹配缺陷

线到线的匹配就是利用一段时间内产生的点连成的轨迹线，与道路进行拟合。拟合的标准是计算轨迹点连成的线与道路线之间的距离。而线与线的距离，通常有多种计算方法：①计算连续点之间的距离，求平均值；②两条线函数相减求积分得到，公式如下

(1)

1.2 拓扑分析法

基于道路网的拓扑分析方法首先需要的是建立道路网的拓扑关系。而所谓道路网的拓扑关系就是指节点、道路线、面之间的关系。拓扑分析法首先根据道路的拓扑关系及待匹配点的空间位置确定候选的匹配道路集合，然后通过历史数据分析得到匹配道路。

1.3 基于概率统计算法

基于概率统计算法的基本思想是：根据对象的定位信息，将对象的实际位置确定在某一置信区间，根据接收到的GPS数据，将当前对象所在位置确定在某一置信区域内，依据已有的匹配结果的概率统计，经过判断后，确定GPS数据在这一置信区域内的匹配道路。

2 网格及方向权重引入

本文研究的地图匹配算法为几何分析法中的点到线的匹配算法，该算法的匹配精确度并不高，且当处理的数据集非常大时，匹配的效率也有一定问题。本文首先通过加入方向信息提高算法的匹配精确度，然后通过引入网格划分的思想提高算法的效率。

2.1 结合方向信息的匹配度计算

传统的点到线的匹配算法只考虑距离因素，而当加入方向信息后，则能够避免图2中的错误。引入匹配度概念，匹配度即表示点与道路的匹配程度，如图3所示。

图3 匹配度计算

匹配度的计算公式如下

M=φD+μL

(2)

式中，M表示匹配点与道路的匹配度；D表示标准化距离因子；L表示标准化后方向因子；φ表示距离权重；μ表示方向权重，权重范围都在0～100%之间。

标准化距离因子的计算公式如下

(3)

式中，DT表示GPS一般最大误差距离，本文取50 m(主要考虑到GPS的定位误差一般不超过50 m)；DO表示匹配点到道路的距离。

标准化方向因子的计算公式如下

L=cos(θO-θT)

(4)

式中，θO表示道路方向角；θT表示匹配点速度方向角。

2.2 基于网格的候选匹配道路确定

使用网格首先需要对数据进行预处理，使每一个待匹配点及道路节点都对应一个网格编号。网格的划分采用均匀的方格网格，并顺序编号。主要原理如图4所示：根据待匹配点P的坐标，选择一定长度L的搜索范围，与搜索范围框有交集的网格作为候选网格，而在候选网格内有节点的道路均作为候选匹配道路。网格的使用大大减少了需要进行匹配道路的数目，从而大大提高了算法的效率。

图4 候选道路确定原理

3 算法实现及试验效果

改进后的匹配算法具体为：

(1) 读取所有待匹配轨迹点，包括经纬度坐标及网格编号。

(2) 判断待匹配点在网格的什么位置。如果所在网格不是边界网格，且位置在左上，则候选网格为所在网格，以及左边相邻、上边相邻、左上4个网格，依次类推位置在左下、右上、右下的候选网格；如果所在网格是边界网格，则根据判断的所在的是哪一边相应去掉那一边的候选网格。

(3) 搜索在候选网格中的节点，根据节点查找节点所在的道路，得到候选道路集，并初始化匹配度(为0)及初始投影点坐标。

(4) 选择一条候选道路，计算待匹配点到道路的距离，以及待匹配点速度方向与道路速度方向的夹角。

(5) 根据步骤(4)计算得到的距离与方向夹角，按照公式计算得到匹配度。与前一个匹配度比较，若大于前一个匹配度，则更新匹配度。

(6) 计算待匹配点到道路的投影点坐标。若投影点在道路上，则返回投影点坐标；若投影点坐标不在道路上(投影到道路延长线上)，则还需要判断投影点到道路起点的距离与到终点的距离，选择距离较短的点返回坐标。

(7) 判断匹配度有没有更新，若有更新，则更新投影点坐标；若未更新，则不更新投影点坐标；重复步骤(2)—(7)，直到所有候选道路都进行匹配。

(8) 重复步骤(1)—(7)，直到所有待匹配点都匹配。

地图匹配算法的流程如图5所示。

图5 匹配算法流程

本文试验部分使用的数据为北京市部分出租车轨迹数据及路网数据，通过对其进行预处理后(如网格划分等)适用于本算法。本文算法在Visual Studio 2010平台上，使用C#语言实现，并调用存储于SQL Server 2008数据库中的位置数据和路网数据。最终的匹配结果如图6、图7所示(图中圈内的点表示找不到候选匹配道路，算法将其作为噪声删除)。

图6 匹配前轨迹点分布

图7 匹配后轨迹点分布

4 结 语

地图匹配算法能够在一定程度上纠正GPS定位的误差，为数据挖掘工作提供更准确的数据支持，具有一定的研究价值。本文对传统的点到线的地图匹配算法进行改进，一定程度上提高了算法的匹配精度和效率，具有一定的实用价值。

[1] 李沛.车辆导航系统中地图匹配的研究[D].北京：北京交通大学, 2008.

[2] 夏州. GPS车辆导航中的数据处理与地图匹配研究[D].北京：北京交通大学, 2009.

[3] 张振辉. 车辆导航中地图匹配算法与应用研究[D].郑州：信息工程大学, 2006.

[4] 王庆祎.地图匹配算法及软件系统研究[D].天津：天津大学, 2005.

[5] 袁正午,褚静静,邓思兵，等.移动终端定位技术发展现状与趋势[J]. 计算机应用研究, 2007,24(11):1- 14.

[6] 刘春,杨超,范业明.基于流动车数据的道路车速匹配与实时发布[J]. 武汉大学学报(信息科学版), 2010,35(4):394- 398.

[7] 李洋,张晓冬,鲍远律.多权值概率论实时地图匹配[J].电子测量与仪器学报. 2012,26(2):166- 170.

[8] 朱丽云,郭继孚,温慧敏,等.一种适用于复杂城市路网的浮动车实时地图匹配技术[J]. 交通与计算机，2007,25(6):81- 84.

[9] VELAGA N R, QUDDUS M A ,BRISTOW A L. Developing an Enhanced Weight- based Topological Map- matching Algorithm for Intelligent Transport Systems[J]. Transportation Re- search Part C(Emerging Technologies)，2009,17(6)：672- 683.

[10] CHENG L, WANG M. A New Path Planning Algorithm Based on Partitioned Urban Transportation Network[C]∥Proceedings of 2010 International Conference on Computer Application and System Modeling(ICCASM 2010). Taiyuan: IEEE, 2010: 13- 17.

A Map Matching Algorithm Based on Meshing and Direction Weighting

LIAO Jia1,YU Jianzhong2,LI Junfeng1

(1. Ningbo Institute of Surveying and Mapping, Ningbo 315042, China; 2. Ningbo Urban Planning & Geographic InformationCenter, Ningbo 315042, China)

Map- matching algorithm is to correct the point that deviated from the road to the correct location. The candidate matching road is confired through leading the concept of grid division and the degree of matching about a point to a line is calculated through weighting factors of the direction based on traditional point- to- line map- matching algorithm. The test shows that the improved algorithm can improve the accuracy of the algorithm and the efficiency of the algorithm to a certain extent. This Algorithm has some practical value.

meshing; weighted direction; map matching

2016- 07- 19 作者简介： 廖 佳(1980—)，男，硕士，高级工程师，研究方向为地理信息、航测遥感和三维数字城市建设。E- mail：5664266@qq.com 通信作者： 李俊峰。E- mail: 553078256@qq.com

廖佳，俞荐中，李俊峰.一种利用网格划分及方向加权的地图匹配算法[J].测绘通报，2017(3)：124- 127.

10.13474/j.cnki.11- 2246.2017.0100.

P208

A

0494- 0911(2017)03- 0124- 04