一种面向高架区域的GPS导航地图匹配算法

叶泰航　张书浆　徐建军

摘 要： 对于包含高架的城市路网，传统的GPS导航地图匹配算法准确率较低。为了弥补传统算法的不足，提出了一种面向高架区域的地图匹配算法。同时为了保证算法实时性，提出了一种常数时间网格索引方法，快速返回导航点邻域的路段集合；为了提高高架区域的导航匹配精度，提出了采用夹角、距离、高程、可达性四种输入参数的模糊推理方法。该算法通过在杭州市中河高架区域的实验结果表明，其相对于基准方法表现出更高的精度。

关键词： 地图匹配； 网格索引； 模糊推理； 智能交通系统

中图分类号：TP391 文献标志码：A 文章编号：1006-8228（2014）04-37-03

Abstract： Traditional GPS map-matching algorithms perform poorly in areas with viaducts. In order to make up for this shortcoming， a new algorithm is proposed in this paper. For the real-time computation， a new grid index method is designed to return road segments around an observed positioning point in O（1） time. For improving the accuracies in handling viaduct areas， an algorithm based on fuzzy inference is introduced， which takes four input parameters into account， including angles， projecting distances， the elevations and the reachability. The experiments as applying in the area of Zhong-he viaduct of Hangzhou city shows that the proposed algorithm performs better than the benchmark algorithm.

Key words： map matching； grid index； fuzzy inference algorithm； intelligent transportation system

0 引言

GPS导航地图匹配是交通工程领域研究的关键技术。随着基于浮动车定位的实时路况监测技术的推广，以及大量基于位置的服务的涌现，常用的GPS匹配算法已不能满足精度要求，尤其在高架与路面重叠、交叠、平行等情形下，难以给出高精度的匹配结果。

已有的地图匹配方法可粗略概括为：距离匹配法、拓扑匹配法、概率匹配法、高级匹配法四类。距离匹配法利用导航观测点与道路之间的邻近关系，如Bernstein[1]提出的点-点匹配法。拓扑匹配法基于地理实体之间的空间关系，例如 Greenfield[2]提出的基于拓扑的匹配算法。概率匹配法在观测点的周围扩展一个误差区域（椭圆或者矩形），若多条路出现在该区域，则综合运用行车方向、距离、连通性等因素决定正确的匹配，如Ochieng[3]提出的快速概率匹配算法。高级匹配法指的是Obradovic[4]提出的卡曼滤波，El Najjar[5]等提出的DS证据理论，以及Gustafsson等[6]提出的状态空间模型和粒子过滤理论等。

传统地图匹配方法一般是初始匹配加后续匹配。初始匹配的目的是确定第一个置信度较高的匹配点。后续匹配基于初始匹配，综合考虑其他因素来决定后续导航点的匹配路段。但若在高架与地面道路重叠和交叠的区域，初始匹配的正确匹配率较低，可能误导后续匹配。

本文力图从两个方面提升匹配效果：①针对传统方法实时性低的问题，设计一种常数时间网格索引方法提升实时性；②针对传统方法在处理高架与路面重叠、交叠等复杂情形时的不足，通过合理利用高程信息提升精度。

1 算法框架

本文的算法框架包括四个部分：①常数时间网格索引方法；②基于模糊推理的高架区域匹配算法，对任何一个待匹配的导航点，通过模糊推理从候选匹配路段中决定最佳匹配路段；③可达性判定，以此来过滤掉候选匹配路段中不合理的匹配路段；④算法转折点的决定，当算法满足转折条件时，启动②、③相结合的算法模式。下面详细介绍各个关键步骤。

1.1 建立常数时间网格索引

建立地图索引是快速提取每个导航观测点附近候选匹配路段的最有效手段。传统的四叉树索引和网格索引的查找时间均为对数时间量级，考虑到高并发情形下的实时性要求，我们提出一种新型的常数时间网格索引。

本索引技术比起传统的网格索引技术有两点改进：传统方法采用二分搜索法查找待匹配点所在的网格，时间开销为对数量级，而本索引技术采用哈希映射法，可以在O（1）时间查找到目标网格；传统的缓冲区法作以待匹配点为质心的缓冲区，计算哪些路段落在该缓冲区，而本索引技术在建立索引阶段就对待匹配点所在网格的缓冲区中路段进行存储，当查找到该网格时，无需计算就可确定候选匹配路段。这两点改进大大提高了算法的实时性。

图1所示为划分了25个网格的网格划分区域，每个网格的经度范围是0.006，纬度范围是0.004，虚线和最小网格之间的部分是最小网格的缓冲区。对待匹配点P，只需用其经度减去边界经度119.698，然后除以0.006后取整即P所在网格的列号，同理，将其纬度减去边界纬度30.564，除以0.004便获得P所在网格的行号。在建立网格索引时，每个网格将该网格及其缓冲区内所有路段的ID存储下来，缓冲区的选择需要保证P的正确匹配路段一定在该网格或者其缓冲区中。

1.2 基于模糊推理的高架区域匹配算法

以下“夹角”指车头方向与路段方向之间的夹角，路段为有向路段，方向由允许车辆行驶的方向决定，双向行驶路段包含两条有向路段；“距离”指导航观测点到路段的垂直距离；“高程”是地面路段和高架路段的高度数据；“可达性”指从上一时刻的匹配路段出发，下一时刻能到达候选匹配路段的可能性。运用上述参数，设计了如图2所示模糊推理系统。

⑴ 模糊化

根据定义的隶属函数，将夹角、距离、高度差等信息映射成隶属度值。本文所用的隶属度函数为如图3所示的钟形和梯形函数，并根据100个典型样本训练得到夹角和距离的隶属度函数的参数，具体细节如下。

1.3 可达性的判定

当某定位点确定被匹配正确，算法开始结合可达性信息。具体做法是：当检测到某条路段不可达时，从候选路段中去掉不可达路段。不可达性的评估主要是检查当前路段的邻接后继路段和两跳后继路段中是否有该候选路段，若无，则认为该路段不可达。

1.4 算法转折点的判定

前面提到，只有当某一定位点确信无疑被正确匹配后，才启动非高架匹配法2和高架匹配法2，这意味着算法进入一个更加可靠的匹配阶段。有两种情况可判定为必然匹配正确：①缓冲区只有一条路段；②缓冲区中有两条路段，但C1-C2=90，其中C1和C2分别表示这两条路段经过模糊推理之后的输出值。C1对应的路段必然匹配正确。

2 实验评估

本文采用最短投影距离法作为实验比较对象，即将该方法当作基准方法。最短投影距离法指将观测点投影到投影距离最短的路段上。

匹配优势举例1（高架交叠问题）：

本文方法在处理高架交叠情形的匹配问题时有明显的效果。由于考虑了车头方向，即图中箭头所指方向，可以有效地避免在交叉路口处的错误匹配。如图4所示，采用本文的算法，P2会正确地匹配到转盘，而基准方法则会将P2匹配到其他路段。

匹配优势举例2（高架与地面路平行问题）：

本文方法对于高架路段和地面路段平行甚至重叠的情形可以处理得很好。如图5所示，H表示高程值，采用本文的技术，P5、P6、P7的正确匹配路段为地面路段2，然而，基准方法将这三个点匹配到高架路段2。本文所用高程数据均为基于手机定位模块驾车采集而得。

3 结束语

本文提出了一种面向高架区域的GPS导航地图匹配算法，针对传统方法实时性低的问题，设计了一种常数时间网格索引方法来提升算法的实时性；针对传统方法在处理高架与路面重叠、交叠等复杂情形时的不足，通过合理利用高程信息来提升算法的精度；为了提高高架区域的导航匹配精度，提出了采用夹角、距离、高程、可达性四种输入参数的模糊推理方法。本文方法具有如下两点优势：①为一种O（1）时间网格索引，查找速度极快，可以节约查询所需的时间开销，提高了算法的实时性；②着重考虑解决高架附近的导航匹配问题，针对高架与地面重叠、交叠等实际情形，合理地引入高程信息达到提高匹配精度的目的。实验结果表明，本文方法在处理高架区域的地图匹配时具有较高的精度。下一步我们需要研究面向高并发场景的GPS导航地图匹配方法。

参考文献：

[1] Bernstein D.， Kornhauser A.. An Introduction to Map Matching for Personal Navigation Assistants[A]. National Research Council （US）. Transportation Research Board. Meeting[C]. Washington： Preprint CD-ROM，1998.

[2] Greenfeld， J. S.. Matching GPS Observations to Locations on a Digital Map[A]. National Research Council （US）. Transportation Research Board. Meeting[C]. Washington： Preprint CD-ROM，2002.

[3] Ochieng， W. Y.， Quddus， M. A.， Noland， R. B.. Map-matching in Complex Urban Road Networks[J]. Revista Brasileira de Cartografia，2004.2（55）：1-18

[4] Obradovic， D.， Lenz， H.， Schupfner， M.. Fusion of Map and Sensor Data in A Modern Car Navigation System[J]. Journal of VSLI Signal Processing，2006.45（2）：112-122

[5] E1 Najjar， M. E.， Bonnifait， P.. A Road-matching Method for Precise Vehicle Localization using Kalman Filtering and Belief Theory[J]. Autonomous Robots，2005.19（2）：173-191

[6] Gustafsson， F.， Gunnarsson， F.， Bergman， N.. Particle Filters for Positioning， Navigation， and Tracking[J]. IEEE Transactions on Signal Processing，2002.50（2）：425-437