地图匹配算法实践

bluesky 发布于2019-08-02 10:13 / 1518人阅读

摘要：在实际应用中，采样信号的质量会严重影响地图匹配结果采样频率的降低定位误差的加大信号的丢失，都会使匹配的不准确性增加。年首次设立的竞赛，其内容就是地图匹配。地图匹配算法综述以使用到的信息来划分现有的算法可被分成四类几何拓扑概率高级。

1 背景

如下图所示，1、2、3 这三个点是汽车的GPS定位结果，尽管汽车是在道路上，但定位结果与道路存在偏差。地图匹配（Map Matching）是指将行车轨迹的经纬度采样序列与数字地图路网匹配的过程，其本质上是平面线段序列的模式匹配问题（ Alt等，2003）。

在实际应用中，GPS采样信号的质量会严重影响地图匹配结果：采样频率的降低、定位误差的加大、信号的丢失，都会使匹配的不准确性增加。这些情况在实际应用中经常出现。如何在这些情况下仍能保持较高的路径匹配准确率是个值得研究的问题。

2012年ACM SIGSPATIAL首次设立的竞赛，其内容就是地图匹配。三年前本人有幸和国防科大的杨岸然博士一同参加了该竞赛，收获良多。

2 地图匹配算法综述 2.1 以使用到的信息来划分

现有的算法可被分成四类：几何、拓扑、概率、高级。
a）基于几何的算法考虑GPS点与道路的几何信息，如距离、角度等；
b）基于拓扑的算法使用道路拓扑信息来控制；
c）概率方法通过考虑GPS点的概率；
d）高级的算法往往综合考虑使用全面信息，有卡尔曼滤波、模糊逻辑模型、隐式马尔可夫模型等等。

2.2 以考虑采样点的范围来划分

根据考虑采样点的范围，可分成局部/增量算法、全局算法。
a）局部/增量算法是贪婪算法，每次确定一个匹配点，下个点从已经确定的匹配点开始。这些方法根据距离和方向相似性来找到局部最优点或边。（在线匹配）
b）全局算法是要从路网中找到一条与采样轨迹最接近的匹配轨迹。为了测量采样轨迹和匹配轨迹的相似性，大多数算法使用“Frechet距离”或者是“弱Frechet距离”。还有时空匹配算法、投票算法等。（离线匹配）

2.3 以采样点的频率来划分

根据轨迹数据的采样频率，现有的地图匹配算法可分成：
a）高频采样算法（所有局部算法、部分全局算法如Frechet距离判别法等）
b）低频采样算法（ST-matching算法、IVVM算法

一般认为30s及其以上为低频采样，1s～10s为高频采样。

3 我们的训练数据

a）路网数据： Washington State U.S.A.（有128万条边）
b）GPS数据：采样频率为1～30s，

4 采用的算法

使用ST-Matching算法（Lou等，2009），该算法是一种全局算法，能综合几何信息（ GPS点与道路的距离）、道路拓扑信息（最短路径）、道路属性信息（每条道路的限速），具有精度高，稳定性好等优点。

4.1 准备候选集

4.2 确定权重

a）空间因素权重（Fs）

b）时间因素权重（Ft）

5 实验结果

6 技术实现要点 6.1 地图投影问题

问题：原始道路网数据的坐标与轨迹点的坐标并不在一个坐标体系下，不能直接进行计算！

解决方法：使用PRJ4地图投影库将两个数据投影到统一坐标下。

6.2 大路网信息数据量的读取

问题：该路网有128万条边，我们采用C++，如果读取每条边都进行new和delete操作，将执行128万次，效率极低！

解决方法：使用内存池技术。

6.3 最短路径算法的选择

问题：候选集不同层次的候选点之间都要计算最短路径，使用最常用的Dijkstra最短路径算法效率极低！

解决方法：使用启发式最短路径算法：A-star算法。

6.4 索引

问题：由于竞赛真实测试会使用很多不同的路网数据，所以建立索引没必要，但是计算某一GPS点的候选集时路网所有数据会参与计算，效率很低；

解决方法：计算某一GPS点的候选集时，先进行切片过滤，比如以该GPS点为中心，生成200m的正方形框，然后在该框里建立新的道路网，这时计算候选集时只需要与该框内的道路网数据计算。

GPU云服务器云服务器字典匹配算法字段匹配算法字符匹配算法最大匹配算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/52203.html

地图匹配算法实践

摘要：在实际应用中，采样信号的质量会严重影响地图匹配结果采样频率的降低定位误差的加大信号的丢失，都会使匹配的不准确性增加。年首次设立的竞赛，其内容就是地图匹配。地图匹配算法综述以使用到的信息来划分现有的算法可被分成四类几何拓扑概率高级。 1 背景如下图所示，1、2、3 这三个点是汽车的GPS定位结果，尽管汽车是在道路上，但定位结果与道路存在偏差。地图匹配（Map Matching）是指将行...

nihao 2019-08-22 16:22 评论0 收藏0
机器学习在美团配送系统的实践：用技术还原真实世界

摘要：可以说，美团要建设的就是配送系统的超级大脑。美团超脑配送系统目前互联网技术，很大部分还是针对线上产品和系统研发，整个流程可以在线上全部完成，而这也正是配送技术最大的不同和挑战。在2018 AI开发者大会（AI NEXTCon）上，美团配送AI方向负责人何仁清，分享了美团在即时配送领域中机器学习技术的最新进展，以及如何通过大数据和机器学习手段，建立对线下真实世界各种场景的感知能力，还原...

hearaway 2019-06-26 18:40 评论0 收藏0
GitChat · 人工智能 | 自动驾驶的技术架构和生态发展

摘要：目前每年全球有万人死于车祸，损失，相关于很多国家的，自动驾驶可以很大效率的减少车祸，拯救生命。美国汽车工程师协会和美国高速公路安全局将自动驾驶技术进行了分级。特定场所的高度自动驾驶。这叫基于规则的一种自动驾驶，简单的。来自 GitChat 作者：刘盼更多IT技术分享，尽在微信公众号：GitChat技术杂谈进入 GitChat 阅读原文我们先以汽车在现代科技领域的演进来开始这次的ch...

X1nFLY 2019-06-26 18:16 评论0 收藏0