JUST技术:提升基于GPS轨迹的路网断定精确度

路网数据对于城市中的很多应用,比如车载导航和线路优化等,都非常重要。传统的路途数据采集方式依赖于采集车,消耗大量的人力物力。随着GPS设备的普及,海量轨迹数据在城市里产生,使我们能够用轨迹数据去天生路网。这个问题在近十年中已经有了广泛的研究,但是其中很多方式的精确度(precision)并不高,特别是上下路途,平行路途等地方。由于轨迹数据在城市内并不是均匀分散的,对于那些车辆频繁通行的地方,我们有没有办法进一步提高这些区域路网断定的精确度呢?

路网数据对于城市中的很多应用,比如车载导航和线路优化等,都非常重要。传统的路途数据采集方式依赖于采集车,消耗大量的人力物力。随着GPS设备的普及,海量轨迹数据在城市里产生,使我们能够用轨迹数据去天生路网。这个问题在近十年中已经有了广泛的研究,但是其中很多方式的精确度(precision)并不高,特别是上下路途,平行路途等地方。由于轨迹数据在城市内并不是均匀分散的,对于那些车辆频繁通行的地方,我们有没有办法进一步提高这些区域路网断定的精确度呢?

本文将介绍美国麻省理工学院(MIT)与卡塔尔哈马德-本-哈利法大学(HBKU)联合在国际地理信息领域顶会ACM SIGSPATIAL 2018上发表的论文《RoadRunner: Improving the Precision of Road Network Inference from GPS Trajectories》,使得在提高路网断定精确度的同时,不损失覆盖率(或召回率,recall)。本文将路网断定的问题分为两阶段,先用本文提出的RoadRunner算法在高轨迹密度区域断定出高精确度地图,然后与传统的轨迹断定路网方式结合,满足召回率的要求。RoadRunner的核心思想是利用每条轨迹的连通性来判断相交的轨迹是行驶在同一条路途上,还是平行的两条路上。

JUST技术:提升基于GPS轨迹的路网断定精确度

一、问题背景

从轨迹中断定路网是一个非常有挑战的问题。图1左侧两栏给出了基于概率密度估计(KDE)和k-Means聚类的两类传统算法在三个城市(洛杉矶、波士顿、芝加哥)上的表现。天生的地图有三个问题:

1)上层路途会与下层路途连接;

2)实际不相交的邻接路途会连通;

3)详细的拓扑很难识别,例如高速路的交叉口。

本文提出了RoadRunner,该方式利用增量的方式基于轨迹的流构建路网。在每一次迭代中,RoadRunner通过一个轨迹过滤算子,考虑前驱相同的子轨迹集合来天生路段。这种方式对于除去相邻路段的干扰非常重要,并且对于GPS的噪声和路途拓扑较为鲁棒。虽然RoadRunner精确度较高,但是过滤操纵会导致轨迹较少的区域丢失路途。为了进一步提高路网断定的召回率,本文提出了一种分开操纵将RoadRunner断定的结果与传统方式断定的结果整合。图1右侧一栏展示了文本提出的方式的效果。

JUST技术:提升基于GPS轨迹的路网断定精确度

二、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为空时,算法停止,并返回当前路网。

JUST技术:提升基于GPS轨迹的路网断定精确度▲图2. RoadRunner算法框架▲

值得注意的一点是,为了有效地进行Trace和Merge,在每一次迭代中,RoadRunner只保留一部分和当前路段相关的子轨迹集合用于路网的天生。图3是某处的卫星地图和对应的轨迹数据分散。假设我们现在要从图3下图蓝色极点处扩展路网。由于三条高亮的路在该处空间距离非常接近,而且它们的朝向也近乎相同,如果我们考虑所有轨迹数据,我们可能会将红色的路与绿色的路相连,或者把红色的路和蓝色的路分开。但是通过排除不在当前正在扩展的路段附近的轨迹,我们能够获得一个干净得多的子轨迹集合(只覆盖红色路途的轨迹)。我们将这个轨迹过滤操纵称为门路过滤算子(way path filter)。实现方式如下:给定一个圆心沿着路段的圆序列(半径代表路途宽度),门路过滤算子只保留按顺序通过这些圆的轨迹。对于一个active极点,我们可以基于当前路网,计算一条长度为k的门路(以active极点为结束),然后沿着这条门路天生圆序列(每个圆的半径可以通过轨迹数据动态估计),来构造过滤条件。

JUST技术:提升基于GPS轨迹的路网断定精确度▲图3. 引入门路过滤算子的动机▲

接下来,我们简单介绍一下Trace和Merge操纵的具体实现。

1,Tracing

Trace操纵的目的是为了提取轨迹在极点v处的主要流出偏向。如图4上图所示,我们要提取轨迹在蓝色极点处的偏向。我们首先应用门路过滤算子获得经过蓝色极点之前的门路的子轨迹集合(绿色显示),我们发现轨迹在交叉路口处明显分为了三组。我们以蓝色极点为圆心,D为半径画一个圆(如粉色圆所示),然后在极点处天生72个角度用于等分圆周。再以每一个角度与圆的交点为圆心,r为半径,构造一个小圆(如黄色圆所示)。然后再次利用门路过滤去筛选获得经过之前门路以及经过该小圆的轨迹T’

 。最后,该角度的轨迹数量记录为

JUST技术:提升基于GPS轨迹的路网断定精确度

,其中M为一个常数,用于滤噪。我们将每个角度的轨迹条数都计算出,并存储在一个72维的向量中,再利用高斯核对该向量进行平滑,然后检测局部峰值。图4下图可视化了平滑后的计数值的分散,算法检测获得三个偏向的局部峰值。

JUST技术:提升基于GPS轨迹的路网断定精确度▲图4. Trace操纵举例▲

2,Merging

当我们天生一条路段后,需要将它和已有路网分开。但是这并不容易,分开的过程中,需要确保上下关系,平行关系以及多层级关系等等。为了克服这些挑战,本文只有在通过路段的轨迹未来的分散匹配的情况下,才会分开两个路段。图5中,我们展示了经过蓝色和绿色的门路的轨迹未来的分散情况。我们可以很明显发现,在例子(a)中两者的分散并不一致,但是在例子(b)中两者的分散几乎一样。 

JUST技术:提升基于GPS轨迹的路网断定精确度▲图5. Merge操纵举例▲

Merge操纵具体实现如图6所示。对于一个要分开的极点v,我们计算经过v的门路的轨迹未来的分散,然后我们找到v周围的极点u,如果经过u的门路的轨迹未来分散和v的一致,我们加入路段(u,v),并返回True;如果v的分散与周围极点都不同,则返回False。

JUST技术:提升基于GPS轨迹的路网断定精确度▲图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%的错误率降低。

JUST技术:提升基于GPS轨迹的路网断定精确度▲图7. 实验结果▲

 五、小结

本文提出了一个两阶段的路网断定框架,能够在不损失召回率的情况下,提升精度。本框架中的核心模块是RoadRunner,它利用轨迹数据的连接性来天生准确的路网,面对复杂的路况,与现有相比有很好的表现。

推荐阅读:

如何使用ClickHouse实现时序数据管理和挖掘?

拥有20 万辆商用车的车联网平台究竟长什么样?

NLP带来的“科幻感”超乎你的想象 – ACL2020论文解读(一)

原创文章,作者:京东科技开发者,如若转载,请注明出处:https://www.iaiol.com/news/just-ji-shu-ti-sheng-ji-yu-gps-gui-ji-de-lu-wang-duan-ding/

(0)
上一篇 2021年 4月 6日 下午2:44
下一篇 2021年 4月 7日 下午3:25

相关推荐

  • Jupyter笔记本实现,慕尼黑工大220页免费书引见鉴于物理的深度进修

    物理常识和深度进修已经成为了解决现实课题的绝佳组合,但如何更有效地将物理模型引入深度进修领域缺少一个全面的综述。慕尼黑工业大学计算机科学副教授 Nils Thuerey 团队编写的这本书对鉴于物理的深度进修展开了详尽的引见。书地址:https://arxiv.org/pdf/2109.05237.pdf项目地址:https://github.com/thunil/Physics-Based-Deep-Learning网站地址:https://www.physicsbaseddeeplearning.org/di

    2021年 9月 16日
  • 斯坦福新书《决议算法》,694页PDF收费下载

    这本书体系引见了不详情性状况下的决议算法,虽然尚未正式出版,但电子版已经开放下载(并将永远开放)。

    2021年 2月 3日
  • 佐治亚理工学院硕士建议:2022年你应该掌握这些呆板进修算法

    2022 年你应该知道的所有呆板进修算法。

    2021年 12月 7日
  • 墨芯携手海潮|稠密化生态释放积极变革力量

    近日,墨芯人工智能与海潮信息签订元脑计谋合营协议。这是在海潮计谋投资墨芯之后,双方进一步计谋合营。 墨芯将携手海潮信息,以超过的稠密化估计技巧和产品,广阔的生态潜能,融合资源与算法,共创全栈AI解决方案,为各行各业AI利用供给强大算力引擎和生态支撑,为企业降本增效,并加速产业的人工智能化进程。AI估计的新锐势力—稠密化估计墨芯人工智能是稠密化估计的全球引领者,供给云端和终端AI加速方案,可广泛利用于互联网、运营商、生物医药等数据中心AI推理场景,并积极致力于稠密化生态建设。 在AI时代算力需求

    2022年 10月 9日
  • ICML2022奖项公布:15篇杰出论文,复旦、厦大、上交大研讨入选

    ICML2022 共评选出 15 篇杰出论文和一篇时间检验奖论文。

    2022年 7月 21日
  • 「声纹辨认」中文课上线:从理论到编程实战,谷歌声纹团队负责人主讲

    对任意一个范畴的进修,如果有人可以指挥你完毕从基本概念、试验方法到体系认知的构建,你的职业发展将事半功倍。声纹辨认范畴,现在就有这样一门课程刚刚上线。

    2022年 8月 16日
  • 目睹太多读博惨案之后,清华姚班助理老师写了个读博决策树

    读博之前请三思。对于部分同窗来说,结业当前读博是顺理成章的人生下一步。但在收获知识、荣誉的同时,你大概也要付出很大代价。最近,清华大学姚班助理老师张焕晨的一篇读博劝退文就在知乎上引起了热议。在文章中,他详细列举了读博之前需要三思的一些成绩,并用决策树的方式呈现了出来。在读完文章后,有人认为焕晨老师把读博之路描写得太痛苦了,劝退之味太浓。但焕晨老师表示,他的本意并非劝退,「故意把话说重是为了让各人认真思考」。他看到的现状是:良多特出的同窗都不在「我适不得当读博」这个重要成绩上进行过认真的思考,由此造成了良多「惨案」

    2021年 6月 24日
  • 关键点检测项目代码开源了!

    作者:闫永强,算法工程师,Datawhale成员 本文通过自建手势数据集,利用YOLOv5s检测,然后通过开源数据集训练squeezenet进行手部关键点预测,最后通过指间的夹角算法来判断具体的手势,并显示出来。文章第四部分为用C++实现整体的ncnn推理(代码较长,可先马后看)一、YOLOV5训练手部检测训练及部署思路类似表情识别,需要将handpose数据集标签改成一类,只检测手部,简化流程,更易上手。此部分数据集来源格物钛  https://gas.graviti.cn/dataset/d

    2022年 3月 30日
  • 详解AI加速器(一):2012年的AlexNet到底做对了什么?

    AI、机器进修、深度进修的概念可以追溯到几十年前,然而,它们在过去的十几年里才真正流行起来,这是为什么呢?AlexNet 的基本结构和之前的 CNN 架构也没有本质区别,为什么就能一鸣惊人?在这一系列文章中,前苹果、飞利浦、Mellanox(现属英伟达)工程师、普林斯顿大学博士 Adi Fuchs 尝试从 AI 加速器的角度为我们寻找这些问题的答案。当代世界正在经历一场革命,人类的体验从未与科技如此紧密地结合在一起。过去,科技公司通过观察用户行为、研究市场趋势,在一个通常必要数月甚至数年时候的周期中优化产品线来改进

    2022年 1月 13日
  • 150页在线书「若干深度进修」上线:利用对称性和不变性解决呆板进修问题

    CNN、GNN、LSTM、Transformer 等深度进修模型之间的共通之处是什么?在这本书里问题得到了解答。

    2021年 4月 30日

发表回复

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