SIGSPATIAL 2022 | 无网络的轨迹插补

通过使用支持GPS设备收集大量轨迹数据使无数非常重要的应用成为可能。不幸的是，这些应用的一个主要障碍是采集的轨迹数据的准确性。由于采样率低，每两个连续的采样点之间的空间和时间距离都很大，因此轨迹通常是稀疏的。本次为大家带来GIS领域顶级会议SIGSPATIAL的论文：《Network-less Trajectory Imputation》

一．背景

通过利用由各种GPS设备产生的一连串的GPS时空点表示的轨迹数据，已经实现了无数极其重要的应用和基本操作，如城市计算、交通、地图推理和数据驱动的路由。尽管所有这些轨迹系统、应用和操作都是通过海量的轨迹数据来实现的，但它们都受限于单条轨迹的稀疏性。由于轨迹数据来自于旨在节省电池的设备，轨迹通常是稀疏的，同一轨迹中的连续点之间有很大的空间和时间差距，这严重降低了依赖轨迹数据的应用的准确性。为了解决这种重要的精度差距，最近的一些研究致力于提高收集的轨迹数据的精度，这些方法的主要目标是在每两个连续的轨迹点之间插入人工点，并保证这些人工点与实际读取的轨迹数据一样准确。大多数这类技术都假定基础道路网络的存在。因此，轨迹插补的过程主要是稀疏轨迹点的地图匹配过程，然后插入与底层道路网络匹配的人工点。不幸的是，拥有基础网络的假设并不总是有效，目前的地图并不像它看起来那样准确。由于地图的不精确性，轨迹插补的过程可以看作是先用现有的地图推理算法构建地图，然后再推算出轨迹。然而，这导致了非常低的精度，因为地图推断的精度本身就高度依赖于轨迹的采样率。

论文提出了TrImpute，一种新型的无网络轨迹插补方法。与其他所有的轨迹推算方法不同，TrImpute既不依赖也不建立自己的底层道路网络，因此称为"无网络"。相反，TrImpute依靠群众的智慧，利用邻近的GPS点来指导每个稀疏轨迹的推算过程。TrImpute可作为各种轨迹应用、操作和系统的预处理步骤，以显著提高其准确性。基于真实轨迹数据的广泛的实验结果，即从实际部署的TrImpute在卡塔尔的4000辆出租车上收集的数据进行实验表明：(1)TrImpute可以高度扩展到城市规模的轨迹推算。(2)TrImpute推算的轨迹与最初的原始密集轨迹非常相似，为了实验评估，论文将这些轨迹稀疏化。(3)TrImpute推算的点在与地面真实地图匹配时具有很高的准确性。(4)当TrImpute被用作原始数据和地图推理算法之间的预处理步骤时，它能够显著提高地图推理算法的性能。

二．方法介绍

2.1 总体框架

图1为论文提出的TrImpute框架的结构。TrImpute的输入是一组原始的GPS点，其中每个点P的格式为<TrajID,PointID,latitude,longitude,timestamp>。输出会有同样的格式，但是会有更多的点，因为在同一轨迹的每两个原始点之间会插入更多的人工推算点。在TrImpute中，输入要经过三个主要部分，即预处理、空间插补和时间插补。

图1 总体框架图

2.2 预处理

TrImpute通过两个任务对输入数据进行预处理：

（1）索引构建：论文将输入数据批量加载到两个索引结构中；一个是基于点位置的分层四叉树索引，另一个是轨迹ID的倒排列表，每个轨迹ID指向其时间上有序的GPS点列表。对所有的点进行一次扫描就足以完成这两项批量加载操作。这两种索引结构都将被空间插值过程使用，以合理地检索轨迹数据。

(2)角度和速度推断：TrImpute依靠输入的GPS点的角度和速度信息来指导其推算过程。然而，这种信息并不直接可用。因此，论文利用轨迹倒排列表来推断每个轨迹点的角度和速度，如图2所示。

图2 角度和速度推断示例

2.3 空间插补

空间插补是在每个从P点到Q点的轨迹段上进行的，其目的是在P和Q之间插入一定数量的人工点，以模拟P和Q之间有更准确的真实读数时的情况。TrImpute空间推算的主要思想是将候选点的概念定义为空间中任何给定点的可能的下一个人工点的集合。然后，空间插补过程就变成了找到由一组连续的候选点组成的从P到Q的最短路径的过程。

（1）候选点：为了确保准确地插补，论文的目标是找到满足以下四个属性的候选点：候选人数量N；人群比例阈值α；角度阈值β；距离阈值d。算法1给出了生成任何给定点P到目的点Q的候选点集的伪代码。除了P和Q之外，该算法还将四个参数N、α、β和d作为输入，以确保候选点集中的所有点都满足上述四个属性。该算法首先使用两个参数N和d来建立一个由N个桶组成的直方图H，其中每个桶i包括与P的距离在以内的点的集合，其角度在和的范围内。然后，论文使用参数α和β排除那些不符合第二和第三项属性的桶，即那些人群比例小于或其平均角度不在P的角度之内的桶。对于剩下的桶，论文在桶角度的方向上，在距离P的距离d内，为每个桶生成一个候选点。论文将该候选点的角度设定为目标点Q的方向。

图3给出了三个例子，说明如何找到P点的候选点集合，作为计算P和Q之间轨迹段的第一步。例子显示了三种不同的道路拓扑结构，直路、T型交叉口和环岛，其中点P和Q被描绘成黑色圆圈，点P的角度分别为 32°,315°和310°。图的下半部分描述了位于P点周围半径为d的圆内的点的角度直方图，这表示论文将考虑的轨迹点。以图3(a)为例，距离P的距离d内有12个点，其中6个点落在第一个直方图桶内，平均角度为10°，一个点落在第二个桶内，角度为70°，5个点落在第六桶内，平均角度为355°。这意味着只有第一桶和第六桶高于人群比例阈值0.2。论文为每个桶生成一个候选点（描述为虚线圆），在距离P的距离和每个水桶角度的方向上。

图3 候选点示例

（2）空间插补：算法2给出了空间插补过程的伪代码，输入是起始点P和目的点Q，输出是由一组候选点组成的路径。首先通过起始点和目的点初始化访问点集合，该集合将用于存储所有候选路径的访问点，当前的候选路径只有一条由起始点组成的长度为1的路径，以及空的路径集合。对于每个迭代i，考虑那些长度为i的候选点的路径。在每次迭代中，对每条路径调用一次候选点算法（算法1），使用当前候选路径列表中每条路径的最后一个点。然后，论文调用一个名为FilterCandPoints的程序：（a）从候选点集合中删除那些与任何先前访问过的点有距离的点；（b）用候选点集合中与目的地Q有距离的点的集合填充一个新的列表P_Final。因此，生成新的|CandPaths|候选路径，为候选点集合中的每一个候选点生成一条路径，用候选点增加当前的i个点的路径，形成一条有i+1个点的新路径。同时，如果P_Final不是空的，就可以知道有一条可能的插补路径。因此，算法形成一个FinalPath集合，由|P_Final|路径组成，每条路径都是由P_Final中的每一个点对当前路径进行增强而形成的。该算法的结果是返回FinalPath中的最短路径。

图4给出的直路、T型交叉口和环岛的从P到Q的完整推断路径。以直路的情况为例（图4(a)），第一次迭代将在P点上执行，其中返回两个候选点P₁₁和P₁₂（用黄色描述）。现在，论文在第二次迭代中有两条可能的路径需要考虑，即[P, P₁₁]和[P, P₁₂]。对这些路径中的每一条应用候选点程序，都会为第一条路径返回两个候选点，为第二条路径返回一个候选点（以绿色显示）。到目前为止，论文有三条可能的路径：[P, P₁₁, P₂₁], [P, P₁₁, P₂₂]和[P, P₁₂, P₂₄]。按照同样的方法，第三次迭代得到四个候选点（红色显示），第四次迭代得到五个候选点（蓝色显示），这样论文就有五个可能的路径。没有必要进行第六次迭代，因为论文已经有两个候选点P₄₁和P₄₂与Q的距离在d之内，这给了论文两个可能的推断路径，论文选择其中最短的路径。[P, P₁₁, P₂₁, P₃₁, P₄₂, Q]。

图4 空间插补过程

2.4 时间插补

算法3给出了论文的时间插补程序的伪代码。该算法的输入是P和Q之间的空间插补路径，其中第一个点是P，路径的最后一个点是Q。该算法对给定路径中的所有点进行两次迭代。第一次迭代从给定路径的第二个点到最后一个点，对于每个点，论文计算：时间戳，即前一个点的时间戳加上两点之间的距离除以前一个点的速度，以及速度，这是基于与目标点Q的距离和时间差。然后，论文将误差率定义为论文在Q的实际值与第一次迭代的最后一个点估计值之间的时间差。然后，论文将δ_ts计算为平均分配给所有路径段的误差。第二次迭代将这个误差幅度部署在估算点上，其中第一个估算点将通过增加δ_ts来调整。接下来，第二个估算点将通过增加两倍的δ_ts来调整，除了考虑第二段的误差外，还考虑到第一段的误差。一般来说，第i个估算点将通过增加i*δ_ts来调整。

三．实验

论文从QARTA[1]系统的实际部署中获得的真实数据，广泛地评估了TrImpute框架，该系统在卡塔尔的所有出租车上运行。由于论文的数据已经很密集了，论文对数据进行了自稀疏，根据稀疏长度对每条轨迹的数据进行抽样。除非另有说明，论文使用20万条轨迹（2300万个GPS点），轨迹总长度为766,000Km，横跨卡塔尔多哈市64Km²的区域。论文将间隔长度（两个连续轨迹点之间的空间间隔）设定为1Km。TrImpute的参数是：候选点的数量N = 12，人群比例阈值α = 0.01，角度阈值β = 120°，距离阈值d = 40米。

3.1 轨迹相似性

图5(a)描述了从500米到2,000米稀疏长度对TrImpute和线性插值的精度的影响。正如预期的那样，准确度随着稀疏长度的增加而降低，因为推算轨迹的难度大大增加。然而，这里有两件重要的事情需要注意。(1)在所有的稀疏长度中，TrImpute都比线性插值准确，(2)TrImpute和线性插值之间的性能差距随着稀疏长度增加而显著增加。这表明TrImpute可以维持较高的稀疏度，而线性插值在1,500米稀疏度的情况下，其精度急剧下降到30%。图5(b)和5(c)对TrImpute和线性插值之间的性能差距进行了更仔细的观察，其中精度是基于将不同拼接长度的路段分别归为直线和曲线。论文使用原始轨迹数据来识别弯曲的路段，即一组5个连续点的角度差异超过一定的阈值。如果这些连续点的角度大致相同，论文就认为该段是直线。否则，该段被认为是弯曲的。图5(b)比较了只考虑直线段时TrImpute和线性插值的精度。虽然，TrImpute在所有的稀疏长度中仍然持续优于线性插值，但线性插值的表现并不差。事实上，线性插值仍然工作得很好，特别是对于低疏散度值，500米疏散度的准确率达到90％以上。这是意料之中的，因为线性插值对直路来说是一个可以接受的解决方案。线性插值在2,000米间距的准确度为30%，这是因为道路上的车道变化，线性插值不能捕捉到这一点，而TrImpute仍然能够得到它。这显示了TrImpute对高稀疏长度的稳健性。图5(c)专门对弯曲的路段进行了同样的实验。很明显，即使是在最低的500米的间隔长度上，线性插值也明显失败，只有2%的精度。同时，TrImpute仍然保持着较高的精度，但随着拼合度的提高，精度会越来越低。

图5 TrImpute与线性插值对比

3.2 OMS精度

图6评估了TrImpute和线性插值的OSM精度。在这种情况下，匹配标准是通过寻找离每个GPS点最近的片段来完成的。匹配度越高越好，因为它表明推断的点是真实的点。作者认为，如果一个点在50米的公差距离内，那么它与地图的匹配度就很高。图6(a)给出了公差值从10米到75米变化的影响。作为参考，作者还绘制了原始轨迹数据的OSM准确性，显然，即使原始数据在任何容差下都不是100%匹配。这是由于任何此类收集到的真实数据的固有噪声所预期的。显然，如果有更多的容差，TrImpute和线性插值都会做得更好。然而，我们可以看到，TrImpute的表现一直优于线性插值，而且随着容差值的增加，差距实际上在扩大。图6(b)给出了拼合距离从750米到2000米变化的影响。更多的疏散距离会使精度大大降低。然而，我们可以看到，与线性插值的趋势相比，TrImpute的精度下降是合理的。特别是，即使有1500米的稀疏，TrImpute仍然能够得到80%的精度，是线性插值40%精度的两倍。

图6 OSM精度

四．总结

本文介绍了TrImpute，一个新颖的轨迹推算框架，它有能力推算稀疏的轨迹数据，而不需要了解底层道路网络，因此它被认为是一个无网络的轨迹推算框架。由于缺乏对道路网络的了解，TrImpute依靠附近的人群智慧来指导其推断过程。基本上，对于空间中的每一个点，都会提出一个候选点的列表，其中任何一个都可能是下一个插值的点。然后，TrImpute将每个轨迹段的空间推算过程正式化为：找到轨迹段终点之间最短的连续候选点集合。TrImpute接着进行时间插补，空间插补的点由遵循轨迹段端点的时间戳信息来注释。基于真实数据和部署的大量实验结果表明，TrImpute具有高度的可扩展性和准确性，并能极大地提高轨迹应用的性能。

参考文献

[1]S. Abbar, R. Stanojevic, M. Musleh, M. M. Elshrif, and M. F. Mokbel. A Demonstration of QARTA: An ML-based System for Accurate Map Services. PVLDB, 14(12), 2021.