复杂路网改进的投影地图匹配算法研究

付小雪，罗赞文，刘振东

(1.上海健康医学院 信息管理中心，上海 201318；2.上海交通运输研究中心大数据研究院，上海 200031)

有关智慧交通的应用大多基于车辆轨迹，其核心是对道路上车辆的GPS轨迹数据进行精确定位，即地图匹配[1]。典型的GPS轨迹是一系列顺序的轨迹点，每个GPS点由纬度、经度和时间戳信息组成。由于GPS自身的局限性，GPS数据的采样和计算过程以及定位数据的接收和返回的过程都有可能出现误差，从而导致GPS数据不准确[2]。因此，需要对原始数据进行处理后在路网上使用，也就是地图匹配。地图匹配算法的输入应该是GPS点标记的位置信息、道路网的邻接信息和车辆的其他行驶信息。最关键问题是如何通过综合各方面信息，快速准确地推断出车辆的行驶路线。地图匹配算法主要包括：基于几何的地图匹配算法[3]、拓扑地图匹配算法[4-5]、概率地图匹配算法[6]和其他地图匹配算法(比如机器学习匹配算法、卡尔曼滤波匹配算法、模糊逻辑模型匹配算法和隐马尔科夫模型(HMM)的地图匹配算法等)。这些先进的匹配算法虽然准确率较高，但是对低频采样数据准确性明显下降。其中基于隐马尔科夫模型(HMM)的地图匹配算法虽然对处理离线的高频采样的行驶数据具有较高的匹配准确率，但是在线路网匹配准确率不高。在线地图匹配算法中最常用的是基于时间窗口的地图匹配算法[7], 由于推断的延迟，影响了立即更新输出。

近期有学者针对在线地图匹配算法进行了相关研究:Mohamed等[8]提出了基于隐马尔科夫模型的在线地图匹配算法(Novel incremental hidden markov model (HMM)-based map matching algorithm, OHMM),该算法利用机器学习方法进行概率转移矩阵的计算，同时考虑了道路的限速和路宽信息，进行观测概率矩阵的计算，地图匹配的过程利用了维特比算法；Hou等[9]提出了INC-RB算法，该算法是基于增量推理和回溯策略的地图匹配算法；郑诗晨等[10]提出的基于粒子滤波的在线行车轨迹路网匹配方法基于粒子滤波(Particle filter，PF)理论进行了行车轨迹与道路网络之间的匹配，准确率只有85%，并且当研究区域较大时，实时运算能力较差，效率较低；陈良健等[11]提出了一种基于GRU模型的在线路网匹配算法,该算法虽然不需要通过对路网建立索引和搜索多条候选路径，地图匹配过程可以加快，但是没有考虑速度和方向信息，算法的匹配准确率较低，会出现匹配错误的情况；黄振锋等[12]提出了一种改进的曲线拟合算法，该算法考虑了移动对象的速度、道路的限速和方向等因素，具有较高的匹配准确率和计算效率，然而在城市复杂路网的真实情景下，算法的容错性、稳定性和效率均不高；滕志军等[13]提出了基于D-S证据理论的自适应地图匹配算法，该算法虽然改进了传统D-S证据理论地图匹配算法准确率低的问题，但是当候选区域存在多条候选路段时，算法的效率和准确率均会受到影响，算法性能降低。现有的地图匹配算法虽然匹配准确率较高，但是在城市复杂路网的实际应用场景中，或者当轨迹数据急剧增加时，算法效率往往较低，而对于算法效率较高的匹配算法，由于没有考虑车辆角度、速度和方向角等因素，算法的匹配准确率会受到一定影响。因此，笔者提出了一种改进的自适应投影地图匹配算法，将城市复杂路网中的道路分为平行道路、交叉道路、立交桥道路和组合道路4种路段类型，对不同的道路类型进行反复实验测试，确定权重系数，即使在复杂的实际应用场景下以及轨迹数据量急剧增加时，依然能够保持较高的地图匹配准确率和匹配效率，实现了城市复杂路网下精准和快速的地图匹配。

1 算法设计

1.1 建立网格索引

Open street map(OSM)地图是一种开放街道地图，所有地图数据都是由全球志愿者提供的，均可直接从官网下载使用。OSM地图数据主要有Node(节点)、Way(道路)和Relation(关系) 3种类型。为了提高单点定位的匹配速度，笔者采用Hash Map网格索引算法。在对地图进行网格划分之前，首先需要对城市OSM地图的完整度进行分析校验，将OSM地图上缺失的道路增加到地图数据库中。传统四叉树索引算法的缺点是对象的空间分布越不均匀，构建的四叉树越不平衡，从而引起空间查询的效率急剧低下，采用Hash网格索引算法可以有效地避免四叉树严重不平衡的情况，通过对地图进行2次网格划分(图1)，更加准确地找到待匹配点的所属匹配范围，减少大量无效的匹配计算，大大提升了匹配的效率和准确率。由图1(b)可以看出：待匹配点P的匹配范围为1，3，4区，大大缩小了待匹配点P的所属区域，提高了匹配准确率。在对地图进行Hash网格划分时，网格的边长设置为100 m，网格的大小可以根据实际情况进行适当调整。

图1 基于Hash Map算法的网格划分示意图Fig.1 Meshing diagram of the Hash Map algorithm

1.2 候选道路集合

对地图进行2次网格划分之后，进一步确定待匹配点所在实际道路的大概区域，一般使用误差椭圆的方式确定此区域，其中误差椭圆的计算式分别为

(1)

(2)

(3)

式中：a为椭圆的长半轴；b为椭圆的短半轴；σX，σY，σXY分别为车辆经纬度的标准差及协方差；σ0=1；φ为椭圆长半轴与正北方向的夹角。

由式(1～3)可以看出：误差椭圆的计算方式比较复杂，故通过误差圆[14-15]的方式进行计算可降低计算工作量,误差圆的计算式为

(4)

通过误差圆的计算，可以确定候选路段集合D={R1,R2,…,Ri,…,Rn|i=1,2,…,n}。

1.3 构造基本概率函数

1.3.1 投影距离概率计算

车辆定位点到道路的投影距离是地图匹配中一个非常重要的指标[16-19]，其投影示意图如图2所示。定位点到附近某条道路的投影距离越小，真实位置就越有可能在该条道路上[20-22]。

图2 定位点到道路的投影示意图Fig.2 Projection diagram from anchor point to road

投影距离的计算方式如下：

1) 定位点S1到路段PQ的最短距离为d1，其计算式为

(5)

2) 定位点S2到路段PQ的投影在路段PQ的延长线上，S2到路段PQ的最短距离为d2，其计算式为

(6)

假设从误差圆中获取的候选道路集合为D={R1,R2,…,Ri,…,Rn|i=1,2,…,n}，那么距离的概率p1(Ri)计算式为

(7)

式中λ为误差圆半径R与定位点到路段的投影距离d之比。

1.3.2 车辆道路夹角概率计算

在车辆位于交叉路口或者车辆周围有多条候选道路的情况下，车辆方向是对车辆进行准确定位的一个重要标准。假设车辆方向与道路方向的夹角为θi，其示意图如图3所示。

图3 车辆与道路的夹角示意图Fig.3 Diagram of the angle between road and vehicle

假设Q点的坐标为(x，y)，O为坐标原点(0，0)，那么道路上的路段OQ与北方方向夹角γi的计算式为

(8)

如果x=0，y<0，那么γi=π；如果x=0，y>0，那么γi=0，由此可以推导出θi的计算式为

(9)

假设从误差圆中获取的候选道路集合为D={R1，R2，…,Ri，…，Rn|i=1，2，…，n}，那么方向角概率p2(Ri)的计算式为

(10)

1.3.3 车辆高程概率计算

城市复杂道路还包括高架路段，城市高架路错综复杂[23-26]，尤其是分叉口比较多的路段是地图匹配中最为复杂的情况。除了投影距离、方向和车速等指标外，还需要考虑高程信息[27-28]。

假设待匹配点的高程为h，路网的高程为Hi，那么高程概率p3(Ri)的计算式为

(11)

1.3.4 计算候选路段概率

分别计算了投影距离、方向和高程的概率后，对于非高架路段，采用距离与方向结合的方式计算候选路段的综合概率。针对高架路段，采用距离、方向和高程结合的方式计算路段的综合概率。对于非高架路，候选路段的综合概率计算式为

p0=μ1p1p2+μ2p1p2+μ3p1p2+μ4p1p2

(12)

式中每一项依次为距离和方向都能匹配到道路Ri的概率。

对于高架路，加入了高程信息，候选路段综合概率的计算式为

p0=μ1p1p2+μ2p1p2+μ3p1p2+
μ4p1p2+μ5p1p3

(13)

式中最后一项为根据高程匹配到候选路段Ri的概率。

1.4 算法流程

步骤1利用Hash Map网格索引算法对地图进行网格划分。

步骤2采用误差圆方法确定候选区域。

步骤3针对不同道路类型，根据投影距离、方向和高程等信息确定概率计算公式。

步骤4根据不同道路类型，自适应确定权重参数。

步骤5根据融合结果选取概率最大的路段为匹配路段。

改进的基于投影的地图匹配算法流程如图4所示。

图4 改进的基于投影的地图匹配算法流程 Fig.4 Flowchart of improved matching algorithm basedon projection

2 算法实验验证及评价

2.1 实验验证

通过2 000多辆常州市出租车采集的实时定位信息对改进的自适应投影匹配算法进行实验验证，每辆车的位置、方向和速度信息均通过车辆车载终端的定位设备获取，采样时间间隔为10 s，图5为笔者算法在一块区域的匹配结果。由图5可以看出：车辆的每一个定位点都能很好地匹配到道路上，在交叉路口也能有极高的匹配准确率。

图5 车辆轨迹数据匹配效果Fig.5 Road matching of vehicles trajectory

除了在一块区域对算法的匹配效果进行实验验证之外，还对同一辆车在一段道路上的匹配效果进行了实验验证，匹配结果如图6所示。由图6可知：车辆的原始定位信息基本没有定位在道路上，经过匹配算法进行匹配之后，车辆的行驶轨迹基本匹配在相应的道路上。当进行大批量浮动车数据的匹配计算时，依然有很好的匹配效果，其匹配效果如图7所示。

图6 同一浮动车的道路匹配效果Fig.6 Road matching of the same floating vehicle

图7 大规模轨迹数据匹配效果Fig.7 Diagram of matching thousands of data points

2.2 评 价

将改进的自适应投影地图匹配算法分别与最新提出的基于GRU模型的路网匹配算法[8-11]、复杂环境下精确实时地图匹配中提出的OHMM 算法和在《基于低频采样GPS数据还原行驶路线的快速在线地图匹配算法研究》一文中提出的INC-RB算法进行匹配准确率和单点匹配时间两个方面的比较。将城市复杂道路划分为平行道路、交叉道路、立交桥道路和组合道路4种类型。上述4种算法的匹配准确率对比如图8所示，在平行路段，改进的投影地图匹配算法和INC-RB算法匹配准确率最高，原因在于待匹配点到道路的投影距离在平行道路的情况下是最重要的参考指标，待匹配点到平行道路中某条道路的投影距离越近，越有可能位于该道路。在交叉路段的情况下，笔者算法的匹配准确率约为97%，匹配准确率最高，在交叉路段的情形下，由于改进的自适应投影匹配算法同时考虑投影距离和方向角2个变量进行候选道路概率的计算，车辆在交叉路口的定位不会只根据投影距离最近的原则进行路网匹配。而OHMM算法是通过计算实际观测概率和计算转移概率相结合的方式计算候选道路的最终匹配概率，在复杂交叉路口的实际应用场景下，准确率受到一定程度的影响。在组合路段下，匹配算法准确率最高，改进的自适应投影算法主要是针对不同路段得出的一种计算方法，根据不同的道路类型，选择不同的权重系数和变量计算候选道路的概率，最适用于组合路段的情况，故改进的自适应投影匹配算法在组合路段情形下匹配准确率最高。

图8 4种算法的匹配准确率对比Fig.8 Comparison of the matching accuracy ofthe four algorithms

对匹配算法的评价，除了计算4种不同算法的匹配准确率之外，还分别计算了4种算法的单点匹配时间。单点匹配时间是指将待匹配点匹配到确定路段所用的平均时间，图9为4种算法分别在2，3，4，5条候选道路下的匹配时间。由图9可以得出：当候选道路为2条时，笔者所提出的算法匹配时间为3.8 ms；当候选道路为5条时，匹配时间约为5.5 ms；随着候选道路的增加，4种算法的单点匹配时间虽然均有所增加，但是笔者算法的匹配时间均低于其他3种算法，其单点匹配时间大约可以降低1.5 ms，具有较好的实时性。

图9 4种不同算法对应的单点匹配时间Fig.9 Single point matching time of the four different algorithms

3 结 论

针对城市复杂道路的不同类型，提出一种改进的自适应投影地图匹配算法，无论在平行路段还是在交叉路段、高架路段以及组合路段，该算法都有较高的地图匹配准确率。对于平行路段，投影距离最近原则可以实现大部分的地图匹配，在十字路口或者交叉路段，引入了方向角参数，更加精确地定位车辆所在的实际道路，不会因为仅仅根据投影距离将车辆定位在错误的道路上；在高架路段，结合了方向角和高程，确定车辆实际所在位置，解决了普通地图匹配算法无法实现的高架道路定位的问题。在车载终端设备定位信号不稳定和不连续时，系统接收到的车辆定位信息存在一定的误差，导致最后的地图匹配结果产生误差，后续可以通过GPS漂移点检测算法将不准确的定位点去除，进一步提高地图匹配的准确率。采用Hash Map网格索引对地图进行了网格划分，提高了初始匹配效率，利用误差圆方法确定了误差区域，缩小了候选区域，大幅减少了匹配时间。根据不同的道路类型，构造了不同的综合概率计算方法，并且自适应调整权重参数，以常州市出租车运行数据进行实验验证。结果表明：改进的算法提高了地图匹配的准确率，缩短了单点匹配时间，实现了城市复杂道路下的精准地图匹配。