如何从GPS定位还原公主坟高架桥地图？

作者 | 姜蔚蔚

编辑 | 贾伟

随着打车软件、导航应用的兴起，数字地图在我们的生活中发挥着越来越重要的作用。然而，传统的数字地图采集方式既费时又费力。最近几年来，我们的移动设备收集了大量的GPS轨迹信息，能否利用这些轨迹信息来生成地图呢？这不是一个简单的任务。如图1所示，(a)表示的是北京某一个路口的地图，(b)是采用点云生成的地图，无法区分不同的车道，(c)是通过GPS点连成的线段，会产生大量冗余的路段。

图1. 使用GPS轨迹生成地图的示例。

尽管存在一些挑战，过去的研究中仍然提出了三类从GPS轨迹生成地图的方法：

1）基于聚类的方法，基于距离或方向的相似度对路口进行聚类，然后相连得到路段；

2）基于轨迹合并的方法，将每一段轨迹合并到已经存在的路段或者创建新的路段；

3）基于核密度估计的方法，首先在点云上进行核密度估计，然后再生成轨迹。

前两类方法在GPS采样密度低的时候，会生成大量不存在的“捷径”，而第三类方法则会把大量临近的路段合并成一个。

下载链接：http://urban-computing.com/pdf/AAAI-RuanS.361.pdf

为了解决不同采样频率的轨迹和平行路段带来的问题，西电、京东等单位在发表于AAAI 2020 的这篇论文中，提出了一个名为DeepMG的基于深度学习的地图生成框架，包含了两个模块：

1） 几何变换，从两个视图提取轨迹的特征，并且用一个名为T2RNet的轨迹-路段转换模型基于这些特征预测路段中心线；

2） 拓扑构建，从预测的路段中心线提取图结构，将不同的路段进行更好的连接。

大量实验证明了DeepMG要优于以往的地图生成方法。

一、框架

这篇论文提出的DeepMG框架如图2所示。

图2. DeepMG框架示意图。

1、几何变换

1）特征提取

与以往的研究类似，这篇论文将感兴趣的区域划分为 个网格，并把每个小网格视作一个个样本点，然后从空间视图和转换视图两个角度提取特征。

DeepMG中用到了四类空间特征：（1）点：每个网格中的GPS点密度；（2）线：每个网格中的连线数量；（3）速度：每个网络内的平均移动速度；（4）方向：8个方向上的移动数量，例如东南、东等。这样空间特征可以被表示一个11维的向量，网格的空间视图即 。

DeepMG中也用到了邻近网格的变换视图，即通过二值矩阵来表示是否有出度和入度

的关系。当两个连续的GPS点连接了一个邻居网格与当前网格，那么它们之间的入-矩阵元素值为1，否则为0。类似的，当两个连续的GPS点连接了当前网络与一个邻居网格，那么它们之间的出-矩阵元素值为1，否则为0。由于这两个矩阵往往是稀疏的，因此DeepMG通过参数T来控制邻居网格的大小，即使用一个更低的空间分辨率，由此得到的变换视图可以表示为 ，其中 表示二值矩阵。

2）T2RNet

如图3所示，T2RNet会基于提取的特征预测道路区域。

图3. T2RNet结构。

T2RNet包含4个部分，它们的任务分别是：

（1）Transition Embedding: 用全连接层将稀疏矩阵 转换成一个更加密集的表示 ，其中 k 是嵌入纬度的大小；

（2）Shared Encoder：将特征在不同程度上进行编码；

（3）Road Region Decoder：给定上一步中的编码信息，预测道路区域；

（4）Road Centerline Decoder：同时利用第2步和第3步中的信息，预测道路的中心线。

预测的道路中心线可以通过两个网格之间的0-1变量来表示，即 。类似的，道路区域可以表示为 。为了解决道路中心线预测时 和 正负样本不均衡的问题，DeepMG采用了Dice loss[1]作为损失函数，如下所示：

最终的优化目标为：

其中 是不同目标之间的权重系数。

2、拓扑构建

几何变换模块预测的道路中心线还存在不连续和断裂的情况，并不能称得上是地图。为了解决这个问题，拓扑构建模块会连接断裂的路段，并且同时推断道路的行驶方向。

1）图提取

首先利用前人的合成方法[2]生成一个初始的无向地图。

2）连接生成

在这一步，DeepMG会利用启发式算法1，来生成所有路段之间的连接。在两种情况下会为某一个边的端点 在半径 内生成一个新的连接：（1）这条边从端点 延伸出去会与另一条边相交，此时会生成新的结点 ，以及 与 之间的连接；（2）交点不存在，但是 与离 最近的结点 之间有一个平滑的连接，例如夹角不超过90度，此时也会在 和 之间形成新的连接。如图4(a)所示， 和边 的 、边 的 点之间都会形成新的连接，但是不会跟边 形成新的连接。

算法1. 连接生成的启发式算法流程。

图4. (a) 连接生成的过程示意；(b)不希望的捷径示意。

3）地图精炼

这一步中，那些不被经常经过的边和生成的连接会被删除。直接通过地图匹配[3]的方式会产生如图4(b)所示的捷径的问题，因为一般的地图匹配算法会倾向于使用最短路径，即图4(b)中的Path 1，而Path 2更像是一条真实的路径，因为它经过了更多的边。为了减少对这种捷径的选取，作者们对生成的连接乘以一个大于1的惩罚系数 ，使得地图匹配算法更多地利用已有的边，而不是生成的连接。

二、实验

这篇论文使用了两种不同采样频率的GPS数据集，如表1所示，其中TaxiBJ来自于T-Drive[4]，而TaxiJN来自于济南政府的非公开数据集。公开的OpenStreetMap被用作真实的基准值。

表1. 数据描述。

这篇论文衡量了生成的地图与OpenStreetMap之间的准确率，主要以平均的F1分数为指标。由于准确率会取决于几何和拓扑，这篇论文采用了跟以往工作[5]类似的评估方法，即从道路上的一个随机位置出发，找到一个最大半径内可以达到的网格。可以到达的网格标记为1，否则为0。在评估时，网格的大小被取为5米到20米，随机采样200个起始点，并且在最大半径设为2千米。

这篇论文将DeepMG与5个地图重建的基准方法进行了比较：Edelkamp [6], Chen [7], Kharita [8], Cao [9], Biagionai [10]。前三个基准方法是基于聚类的，第四个方法是基于轨迹合并的，第五个方法是基于核密度估计的。作者们也比较了不包含拓扑构建的DeepMG，记作DeepMG-nt.

图5中给出了不同方法的F1分数。相对于表现最好的基准方法，DeepMG在TaxiBJ和TaxiJN上分别取得了32.3%和6.5%的提升。由于北京市的GPS轨迹采样频率更低，DeepMG在TaxiBJ取得了更大的提升。DeepMG-nt与DeepMG的比较也显示了拓扑构建的贡献。

图5. 不同方法的F1分数。

图6给出了公主坟附近的地图构建的结果比较，可以直观地看到DeepMG的结果更加合理，能够在不产生冗余的情况下生成平行的路段。

‍ ‍p‍图6. 公主坟的地图构建结果比较。

‍

这篇论文也对不同模块分别进行了评估。首先在几何变换模块中，作者们将T2RNet中的编码-解码部分替换成另外6种网络结构：FCN [11], LinkNet [12], DeepLabV3+ [13], UNet [14], D-LinkNet [15], LinkNet + 1D Decoder [16]。结果如表2所示，从F1分数来看，FCN表现最差，而T2RNet好于其他所有方法。

表2. 不同数据集上的模型比较。

作者们也比较了优化目标中的权重系数 的影响，结果如图7所示，当 为0.2时效果最好。

图7. 的影响评估。

为了比较不同特征的影响，作者们比较了不同特征组合的影响，即P（仅点特征），L（仅线特征），S（仅空间视图特征）和A（所有特征），结果如表3所示，采用所有特征时能够得到最好的结果。

表3. 不同特征组合的影响。

最后在拓扑构建模块中，作者们评估了不同的惩罚因子 的影响，如图8所示。当 过小时，会生成很多不存在的捷径，而当 过大时，则会遗留很多中断的路段，因此作者们最终采用了 为1.4。

图8. 的影响。

三、结论

这篇论文提出了一个名为DeepMG的基于深度学习的地图生成框架，在真实的北京和济南的GPS数据集上，相对于最优的基准方法，分别取得了32.3%和6.5%的性能提升。大量的实验和参数的分析也表明了DeepMG得到了很好的优化。

参考：

[1] Milletari, F.; Navab, N.; and Ahmadi, S.-A. 2016. V-net: Fully convolutional neural networks for volumetric medical image segmentation. In 3DV, 565–571. IEEE.

[2] Shi, W.; Shen, S.; and Liu, Y. 2009. Automatic generation of road network map from massive gps, vehicle trajectories. In ITSC, 1–6. IEEE.

[3] Yuan, J.; Zheng, Y.; Zhang, C.; Xie, X.; and Sun, G.-Z. 2010b. An interactive-voting based map matching algorithm. In MDM, 43–52. IEEE Computer Society.

[4] Yuan, J.; Zheng, Y.; Zhang, C.; Xie, W.; Xie, X.; Sun, G.; and Huang, Y. 2010a. T-drive: driving directions based on taxi trajectories. In SIGSPATIAL, 99–108. ACM.

[5] Biagioni, J., and Eriksson, J. 2012a. Inferring road maps from global positioning system traces: Survey and comparative evaluation. TRANSPORT RES REC 2291(1):61–71.

[6] Edelkamp, S., and Schr¨odl, S. 2003. Route planning and map inference with global positioning traces. In Computer science in perspective. Springer. 128–151.

[7] Chen, C.; Lu, C.; Huang, Q.; Yang, Q.; Gunopulos, D.; and Guibas, L. 2016. City-scale map creation and updating using gps collections. In SIGKDD, 1465–1474. ACM.

[8] Stanojevic, R.; Abbar, S.; Thirumuruganathan, S.; Chawla, S.; Filali, F.; and Aleimat, A. 2018. Robust road map inference through network alignment of trajectories. In ICDM, 135–143. SIAM.

[9] Cao, L., and Krumm, J. 2009. From gps traces to a routable road map. In SIGSPATIAL, 3–12. ACM.

[10] Biagioni, J., and Eriksson, J. 2012b. Map inference in the face of noise and disparity. In SIGSPATIAL, 79–88. ACM.

[11] Long, J.; Shelhamer, E.; and Darrell, T. 2015. Fully convolutional networks for semantic segmentation. In CVPR, 3431–3440.

[12] Chaurasia, A., and Culurciello, E. 2017. Linknet: Exploiting encoder representations for efficient semantic segmentation. In VCIP, 1–4. IEEE.

[13] Chen, L.-C.; Papandreou, G.; Kokkinos, I.; Murphy, K.; and Yuille, A. L. 2017. Deeplab: Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected crfs. TPAMI 40(4):834–848.

[14] Ronneberger, O.; Fischer, P.; and Brox, T. 2015. U-net: Convolutional networks for biomedical image segmentation. In MICCAI, 234–241. Springer.

[15] Zhou, L.; Zhang, C.; and Wu, M. 2018. D-linknet: Linknet with pretrained encoder and dilated convolution for high resolution satellite imagery road extraction. In CVPR Workshops, 182–186.

[16] Sun, T.; Di, Z.; Che, P.; Liu, C.; and Wang, Y. 2019. Leveraging crowdsourced gps data for road extraction from aerial imagery. In CVPR, 7509–7518.

---