ICDE 2020 | 华东师范大学×滴滴：利用轨迹数据自动校准道路交叉口拓扑信息

基础路网数据是网约车路线规划和运营管理最重要的数据。路网数据的快速更新能够使线上服务更快地感知物理世界的快速变化，对于提升导航可靠性和用户出行体验至关重要。滴滴作为领先的一站式移动出行平台，拥有海量轨迹数据，结合司乘上报数据、车载图像数据等丰富的数据来源，持续提升自动化、精准更新路网拓扑信息的能力。

本文解读华东师范大学数据科学与工程学院毛嘉莉研究组与滴滴地图与公交事业部技术团队合作完成的工作《Automatic Calibration of Road Intersection Topology using Trajectories》，该论文被ICDE 2020收录。

IEEE ICDE（IEEE International Conference on Data Engineering）数据工程国际会议是数据库与数据挖掘领域顶会之一，CCF A类会议。大会涵盖了数据科学，数据流系统和传感器网络，性能建模和调整，分布式，并行和P2P数据管理等多个领域。

01

简介

作为数字道路地图的关键部分，道路交叉口是多条相互连接道路的交汇处，其几何特征和拓扑属性的精确性在移动导航和其他位置服务中起着重要作用。另一方面，GPS轨迹序列数据是用户在实际道路上的观测，蕴含了实际路网的拓扑信息。基于此，滴滴和华东师范大学数据学院创新性地提出了一种交叉路口三阶段校准算法框架-CITT。CITT首先将道路交叉口检测问题扩展为道路交叉口影响区的拓扑校准问题。与现有的道路交叉口更新方法不同，该方法不仅确定道路交叉口核心区的中心位置和覆盖范围，同时挖掘出路口与邻接路段的转向路径，之后与现有路网进行匹配，找出整个影响区内的错误或缺失的转向模式。大量的基于滴滴实际数据和公开数据的对比实验表明，CITT方法具有很强的稳定性和鲁棒性，并且明显优于现有方法。

02

技术方案

CITT的技术框架图如上，包含三个核心模块：轨迹质量提升，路口核心区域检测和影响区拓扑结构校准模块。
原始轨迹数据可能受设备故障、信号不佳等因素影响导致采集到的定位信息存在漂移甚至异常，我们根据前后轨迹点的距离和时间间隔进行轨迹段的分割，保证同一轨迹段在时空上具有连续性；此外，车辆在路口一般会因为等红绿灯或交通拥堵停留，导致在短距离范围内产生大量具有不同方向的位置信息（噪声），不仅增加了路口检测的计算开销，还给检测精度带来较大影响。针对这一问题，我们基于轨迹点的空间密度进行数据过滤，并结合Douglas Peucker算法压缩轨迹，在保留轨迹转向特征的同时，对数据实现了压缩。因此，通过轨迹分段、去噪、压缩的预处理，实现了对原始轨迹数据的质量提升。

为了检测道路交叉口影响区内的详细拓扑信息，首先需要识别道路交叉口的核心区域，即路口位置和覆盖范围。考虑到不同路口大小不一，并且路口范围内轨迹通常具有减速、转向等特征，我们设计了一套基于四叉树空间划分和Mean-shift的自适应路口位置检测算法。在搜索道路交叉口单元的过程中，将四叉树的最小边长设置为25米，并从200米大小边长开始的层（即从四叉树底部开始的第四层）搜索道路交叉口单元。由于交叉口中心位置的轨迹往往比路段具有更多的转向与较低的转速，我们对每个网格单元中的所有特征点（轨迹压缩获得）执行速度分析和基于方向的DBSCAN聚类，筛选潜在的道路交叉口网格单元。随后，我们提出了基于方向的聚类算法识别路口的中心位置。

鉴于不同路口其形状有较大差异，如何更通用地基于轨迹数据确定路口的核心区范围？实质上道路交叉口的中心位置附近并不总是具有相对于路段区域更多转向行为，例如，环岛和立交桥。本文中我们利用环状几何模型逐层检测路口覆盖范围。对于一个路口而言，越到核心区边缘的环包含的转向点密度越低、速度越大，因此该路口模型适于不同形状路口的范围提取。

在影响区拓扑结构的校准阶段，我们基于检测的路口中心位置和核心区范围向外扩展，根据预设的半径阈值获得影响区的范围，同时获取交叉路口影响区内的全部轨迹。我们对这些轨迹进行转向簇提取与中心线拟合，并将拟合的转向路径与基准路网进行地图匹配。

Frechét距离适于评测曲线之间的相似性，但是对于复杂形状的路口以及路口邻接路段间朝向偏差较小的情况，Frechét表现不佳。鉴于此，我们将方向权重引入相似性评测中。对于任意两条轨迹序列，分别计算起点与终点间的方向差，并结合Frechét距离生成轨迹集合的距离矩阵。基于该矩阵结合DBSCAN聚类实现路口范围内的转向簇提取。

在提取转向簇后，需要对各簇轨迹进行拟合，我们采用基于Force attraction的聚类方法获取各簇对应的转向路径。Force attraction方法首先随机采样簇中的一条轨迹作为参考轨迹，随后使用同簇内其余轨迹对参考轨迹中点的位置进行迭代调整。在调整过程中，Force attraction算法假定任意轨迹点上有吸引力和排斥力作用，通过搜索两个力达到平衡的位置来获得参考轨迹对应点的新位置。由于随机采样轨迹容易导致拟合得到的中心线不精准，特别是当随机采样的参考轨迹远离实际道路中心时，拟合偏差较大。因此，我们引入基于Frechét的采样策略。具体来说，我们从簇中随机采样k条轨迹作为候选参考轨迹，并分别计算每个候选者与该簇的其余轨迹之间的Frechét距离。将具有最小距离和的候选轨迹视为参考轨迹。

在获得转向路径后，我们采用经典的HMM算法结合基准路网进行地图匹配。为加速匹配过程，我们基于每个路口的转向路径集生成凸包再与路网空间关联。

03

应用效果

在路口位置检测任务中，我们与业界三种路口探测方法（CBTP，Ahmed2012，Kharita）进行了对比实验，在精确率和F值指标上CITT都取得了最优的效果。
在转向路径形态拟合上，我们与HyMU方法进行了对比实验，以验证我们中心线拟合的稳定性。HyMU采用Sweeping算法推断缺失道路的中心线。可以看到，我们生成的转向路径与基准道路数据之间的偏差明显小于HyMU。
在最终的路口拓扑结构校准部分，为了评估我们解决方案的有效性，我们利用滴滴的车辆轨迹和路网数据检测两类错误拓扑：转向路径缺失和转向路径偏移。根据评估结果，我们的方法其精确率能够达到70%，转向路径缺失和偏移的比例在1 : 5。两个典型案例如下图所示（路网以淡灰色线表示，轨迹以深蓝色点表示，校准的转向路径以红色带箭头的线条突出显示）。

04

展望

CITT针对道路交叉口拓扑的不精准问题提供了一种全新解决方案（由核心区域检测和转向路径校准组成）。根据轨迹数据的方向差和速度变化特性，我们的方法可以准确识别道路交叉口的位置和覆盖范围。此外，结合基于Frechét距离的DBSCAN聚类和混合中心线拟合策略，可以有效甄别道路交叉口影响区域内的转向路径。尽管校准方法需要处理大规模的GPS轨迹，但结合滴滴分布式计算平台的优势，因此时间开销较小。在后续研究工作中，为实现更精确的导航地图服务，我们会进一步将道路交叉口的拓扑校准框架实现车道级别的细化；同时，结合校准结果和基准路网实现自动化的差分融合，形成自动化的道路拓扑修改方案。

05

论文核心贡献者

赵俐晟

华东师范大学硕士研究生

  研究方向包括地图更新，

旅行时间预测，道路封闭检测。

濮敏

华东师范大学硕士研究生

  研究方向为基于位置的服务。

毛嘉莉

华东师范大学研究员

研究方向包括时空/

情境数据管理、

   面向智慧城市应用的智能服务。

刘国平

滴滴地图与公交事业部

资深算法工程师

温翔

滴滴地图与公交事业部

高级专家工程师

06

直播预告

推荐阅读

更多阅读

做学术界最值得

信赖的合作伙伴