JUST 技术：提升基于 GPS 轨迹的路网推测精确度
路网数据对于城市中的很多应用，比如车载导航和线路优化等，都非常重要。传统的道路数据采集方法依赖于采集车，消耗大量的人力物力。随着 GPS 设备的普及，海量轨迹数据在城市里产生，使我们能够用轨迹数据去生成路网。这个问题在近十年中已经有了广泛的研究，但是其中很多方法的精确度（precision）并不高，特别是上下道路，平行道路等地方。由于轨迹数据在城市内并不是均匀分布的，对于那些车辆频繁通行的地方，我们有没有办法进一步提高这些区域路网推测的精确度呢？
本文将介绍美国麻省理工学院(MIT)与卡塔尔哈马德-本-哈利法大学(HBKU)联合在国际地理信息领域顶会 ACM SIGSPATIAL 2018 上发表的论文《RoadRunner: Improving the Precision of Road Network Inference from GPS Trajectories》，使得在提高路网推测精确度的同时，不损失覆盖率（或召回率，recall）。本文将路网推测的问题分为两阶段，先用本文提出的 RoadRunner 算法在高轨迹密度区域推测出高精确度地图，然后与传统的轨迹推测路网方法结合，满足召回率的要求。RoadRunner 的核心思想是利用每条轨迹的连通性来判断相交的轨迹是行驶在同一条道路上，还是平行的两条路上。
一、问题背景
从轨迹中推测路网是一个非常有挑战的问题。图 1 左侧两栏给出了基于概率密度估计（KDE）和 k-Means 聚类的两类传统算法在三个城市（洛杉矶、波士顿、芝加哥）上的表现。生成的地图有三个问题：
1）上层道路会与下层道路连接；
2）实际不相交的邻接道路会连通；
3）详细的拓扑很难识别，例如高速路的交叉口。
本文提出了 RoadRunner，该方法利用增量的方式基于轨迹的流构建路网。在每一次迭代中，RoadRunner 通过一个轨迹过滤算子，考虑前驱相同的子轨迹集合来生成路段。这种方法对于除去相邻路段的干扰非常重要，并且对于 GPS 的噪声和道路拓扑较为鲁棒。虽然 RoadRunner 精确度较高，但是过滤操作会导致轨迹较少的区域丢失道路。为了进一步提高路网推测的召回率，本文提出了一种合并操作将 RoadRunner 推测的结果与传统方法推测的结果整合。图 1 右侧一栏展示了文本提出的方法的效果。
二、RoadRunner
RoadRunner 的算法流程如图 2 所示。算法的输入是一个初始的路网，可以来自于现有路网或者用别的方法推测得到的路网。我们先把初始路网中所有的顶点加入队列 Q，队列中的顶点称为 active 顶点（第 2-3 行）。在每一轮迭代中，RoadRunner 从队列中挑选一个 active 顶点 v，通过 Trace 操作提取轨迹在顶点 v 处的流出方向（第 5-6 行）。对于每个流出方向θ，我们加入一条从 v 出发，方向为θ，距离为固定长度 d 的小路段来扩展当前路网（第 7-11 行）。然后通过 Merge 操作，尝试将该小路段的另一个顶点 u 合并到现有路网。如果合并失败，我们将 u 加入 Q 用于下一轮迭代（第 12-14 行）。当 Q 为空时，算法停止，并返回当前路网。
值得注意的一点是，为了有效地进行 Trace 和 Merge，在每一次迭代中，RoadRunner 只保留一部分和当前路段相关的子轨迹集合用于路网的生成。图 3 是某处的卫星地图和对应的轨迹数据分布。假设我们现在要从图 3 下图蓝色顶点处扩展路网。由于三条高亮的路在该处空间距离非常接近，而且它们的朝向也近乎相同，如果我们考虑所有轨迹数据，我们可能会将红色的路与绿色的路相连，或者把红色的路和蓝色的路合并。但是通过排除不在当前正在扩展的路段附近的轨迹，我们能够得到一个干净得多的子轨迹集合（只覆盖红色道路的轨迹）。我们将这个轨迹过滤操作称为路径过滤算子（way path filter）。实现方式如下：给定一个圆心沿着路段的圆序列（半径代表道路宽度），路径过滤算子只保留按顺序通过这些圆的轨迹。对于一个 active 顶点，我们可以基于当前路网，计算一条长度为 k 的路径（以 active 顶点为结束），然后沿着这条路径生成圆序列（每个圆的半径可以通过轨迹数据动态估计），来构造过滤条件。
接下来，我们简单介绍一下 Trace 和 Merge 操作的具体实现。
1，Tracing
Trace 操作的目的是为了提取轨迹在顶点 v 处的主要流出方向。如图 4 上图所示，我们要提取轨迹在蓝色顶点处的方向。我们首先应用路径过滤算子得到经过蓝色顶点之前的路径的子轨迹集合（绿色显示），我们发现轨迹在交叉路口处明显分为了三组。我们以蓝色顶点为圆心，D 为半径画一个圆（如粉色圆所示），然后在顶点处生成 72 个角度用于等分圆周。再以每一个角度与圆的交点为圆心，r 为半径，构造一个小圆（如黄色圆所示）。然后再次利用路径过滤去筛选得到经过之前路径以及经过该小圆的轨迹 T'
。最后，该角度的轨迹数量记录为
，其中 M 为一个常数，用于滤噪。我们将每个角度的轨迹条数都计算出，并存储在一个 72 维的向量中，再利用高斯核对该向量进行平滑，然后检测局部峰值。图 4 下图可视化了平滑后的计数值的分布，算法检测得到三个方向的局部峰值。
2，Merging
当我们生成一条路段后，需要将它和已有路网合并。但是这并不容易，合并的过程中，需要确保上下关系，平行关系以及多层级关系等等。为了克服这些挑战，本文只有在通过路段的轨迹未来的分布匹配的情况下，才会合并两个路段。图 5 中，我们展示了经过蓝色和绿色的路径的轨迹未来的分布情况。我们可以很明显发现，在例子(a)中两者的分布并不一致，但是在例子(b)中两者的分布几乎一样。
Merge 操作具体实现如图 6 所示。对于一个要合并的顶点 v，我们计算经过 v 的路径的轨迹未来的分布，然后我们找到 v 周围的顶点 u，如果经过 u 的路径的轨迹未来分布和 v 的一致，我们加入路段（u,v），并返回 True；如果 v 的分布与周围顶点都不同，则返回 False。
三、两阶段路网推测
RoadRunner 虽然有较高的精确度，但是由于路径过滤算子对轨迹的筛选，很多低频访问区域的路段会丢失。所以在第二阶段，为了提高召回率，需要将 RoadRunner 的结果与其他路网推测算法结果合并。
假设 G1 为 RoadRunner 推测的路网，G2 为其他能够捕捉低频通行路段的路网生成算法输出的结果。我们首先删除 G2 中距离 G1 中路段 Rmerge 范围内的路段得到 G2'，因为这些路段路段 RoadRunner 已经成功推测完成了。然后我们将 G1 与 G2'放在一起得到 G。然而，从 G2'中加入的路段和其余路段并不连通。为了连通这些道路，对于 G 中每一个度为 1 的顶点 v，我们在满足以下两个条件时，让其与周围路段(u,w)连通：1）v 到
(u,w)的距离小于 Rmerge；2）经过路径 v → p → u 或者 v → p → w 的轨迹超过一定阈值，其中 p 为 v 在路段(u,w)上的投影点。
四、实验结果
本文在 4 个城市（洛杉矶、波士顿、芝加哥、纽约）上验证了提出的方法的有效性，每个城市选择了一块 4kmx4km 的区域，轨迹数据累计约有 6 万条。OpenStreetMap 被当作真实路网用于验证。
图 7 给出了不同方法在不同参数设定下，错误率和召回率的变化曲线（越接近左上角性能越好，不同数据集结果取平均）。实验结果显示，RoadRunner+KDE 的方法(RR-2+BE-2)比只用 KDE 的方法（BE-2）有 33.6%的错误率降低，RoadRunner+kMeans 的方法(RR-2+Kharita-20)比只用 kMeans 的方法（Kharita-20）有 60.7%的错误率降低。
五、小结
本文提出了一个两阶段的路网推测框架，能够在不损失召回率的情况下，提升精度。本框架中的核心模块是 RoadRunner，它利用轨迹数据的连接性来生成准确的路网，面对复杂的路况，与现有相比有很好的表现。
推荐阅读：
欢迎点击【京东智联云】，了解开发者社区
更多精彩技术实践与独家干货解析
欢迎关注【京东智联云开发者】公众号
版权声明: 本文为 InfoQ 作者【京东科技开发者】的原创文章。
原文链接:【http://xie.infoq.cn/article/dc6e445f4537e1e415196a897】。文章转载请联系作者。
拥抱技术，与开发者携手创造未来！ 2018.11.20 加入
我们将持续为人工智能、大数据、云计算、物联网等相关领域的开发者，提供技术干货、行业技术内容、技术落地实践等文章内容。京东科技开发者社区官方网站【https://developer.jdcloud.com/】，欢迎大家来玩
评论