Press "Enter" to skip to content

如何从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.

Be First to Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注