共计 3388 个字符，预计需要花费 9 分钟才能阅读完成。
路网数据对于城市中的很多利用，比方车载导航和线路优化等，都十分重要。传统的路线数据采集办法依赖于采集车，耗费大量的人力物力。随着 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 为空时，算法进行，并返回以后路网。
▲图 2. RoadRunner 算法框架▲
值得注意的一点是，为了无效地进行 Trace 和 Merge，在每一次迭代中，RoadRunner 只保留一部分和以后路段相干的子轨迹汇合用于路网的生成。图 3 是某处的卫星地图和对应的轨迹数据分布。假如咱们当初要从图 3 下图蓝色顶点处扩大路网。因为三条高亮的路在该处空间间隔十分靠近，而且它们的朝向也近乎雷同，如果咱们思考所有轨迹数据，咱们可能会将红色的路与绿色的路相连，或者把红色的路和蓝色的路合并。然而通过排除不在以后正在扩大的路段左近的轨迹，咱们可能失去一个洁净得多的子轨迹汇合（只笼罩红色路线的轨迹）。咱们将这个轨迹过滤操作称为门路过滤算子（way path filter）。实现形式如下：给定一个圆心沿着路段的圆序列（半径代表路线宽度），门路过滤算子只保留按程序通过这些圆的轨迹。 对于一个 active 顶点，咱们能够基于以后路网，计算一条长度为 k 的门路（以 active 顶点为完结），而后沿着这条门路生成圆序列（每个圆的半径能够通过轨迹数据动静预计），来结构过滤条件。
▲图 3. 引入门路过滤算子的动机▲
接下来，咱们简略介绍一下 Trace 和 Merge 操作的具体实现。
1，Tracing
Trace 操作的目标是为了 提取轨迹在顶点 v 处的次要流出方向。 如图 4 上图所示，咱们要提取轨迹在蓝色顶点处的方向。咱们首先利用门路过滤算子失去通过蓝色顶点之前的门路的子轨迹汇合（绿色显示），咱们发现轨迹在交叉路口处显著分为了三组。咱们以蓝色顶点为圆心，D 为半径画一个圆（如粉色圆所示），而后在顶点处生成 72 个角度用于等分圆周。再以每一个角度与圆的交点为圆心，r 为半径，结构一个小圆（如黄色圆所示）。而后再次利用门路过滤去筛选失去通过之前门路以及通过该小圆的轨迹 T ’
。最初，该角度的轨迹数量记录为
，其中 M 为一个常数，用于滤噪。咱们将每个角度的轨迹条数都计算出，并存储在一个 72 维的向量中，再利用高斯核查该向量进行平滑，而后检测部分峰值。图 4 下图可视化了平滑后的计数值的散布，算法检测失去三个方向的部分峰值。
▲图 4. Trace 操作举例▲
2，Merging
当咱们生成一条路段后，须要将它和已有路网合并。然而这并不容易，合并的过程中，须要确保高低关系，平行关系以及多层级关系等等。为了克服这些挑战，本文只有在通过路段的轨迹将来的散布匹配的状况下，才会合并两个路段。图 5 中，咱们展现了通过蓝色和绿色的门路的轨迹将来的散布状况。咱们能够很显著发现，在例子 (a) 中两者的散布并不统一，然而在例子 (b) 中两者的散布简直一样。
▲图 5. Merge 操作举例▲
Merge 操作具体实现如图 6 所示。对于一个要合并的顶点 v，咱们计算通过 v 的门路的轨迹将来的散布，而后咱们找到 v 四周的顶点 u，如果通过 u 的门路的轨迹将来散布和 v 的统一，咱们退出路段（u,v），并返回 True；如果 v 的散布与四周顶点都不同，则返回 False。
▲图 6. Merge 操作▲
三、两阶段路网揣测
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% 的错误率升高。
▲图 7. 试验后果▲
五、小结
本文提出了一个两阶段的路网揣测框架，可能在不损失召回率的状况下，晋升精度。本框架中的外围模块是 RoadRunner，它利用轨迹数据的连接性来生成精确的路网，面对简单的路况，与现有相比有很好的体现。
举荐浏览：
- 如何应用 ClickHouse 实现时序数据管理和开掘？
- 领有 20 万辆商用车的车联网平台到底长什么样？
- NLP 带来的“科幻感”超乎你的设想 – ACL2020 论文解读（一）
欢送点击【京东智联云】，理解开发者社区
更多精彩技术实际与独家干货解析
欢送关注【京东智联云开发者】公众号
