轨迹相似度计算方法汇总

简介

轨迹相似度的计算有很多种方法，他们之间没有优劣之分，每种方法都有适合其发挥的使用场景。从思想上划分，轨迹的相似度计算大概可以分为三种：

结合路网信息的轨迹相似度计算
基于轨迹点匹配的计算方法
基于轨迹形状的计算方法

基于路网信息的轨迹相似度计算

这类计算方法都假设了知道路网信息的先验知识，并且轨迹点都很好的和路网信息相匹配。普适性较差，但适合特异性场景。

基于轨迹点匹配的相似度计算

最基础的基于轨迹点的轨迹度量方式，例如欧拉距离和曼哈顿距离等，其计算方式是轨迹之间的点一对一计算差异值，再累加起来。在轨迹长度不一致或者轨迹点采集频率不一致的情况下，都受到了限制。

为了解决在上述场景受限的问题，人们提出了轨迹扭曲距离的计算方式，直白点说就是两条轨迹相乘，组成一个矩阵，从矩阵的左上角到右下角找到一条路径，使其代价满足最大或最小，这个代价就用来描述轨迹的相似程度。这类思想的经典计算方法有DTW、LCSS、EDR、ERP等，他们之间的差异就是损失值的计算方式不一样。

上述4个方法，都可以对抗时间序列不统一的问题
LCSS和EDR都是计算满足距离满足某个范围的相匹配的轨迹点对的数量。通过设置范围，算法具有一定的鲁棒性，但范围的选择对最终结果的影响也很大。
ERP和DTW都是根据轨迹点之间的实际距离调节权重分配，将一条轨迹转变成（或者近似成）另一条轨迹。在这种语境下，这种思想要比LCSS和EDR要好。
ERP是四种方式中唯一的Metric度量方式（这种方式的具体度量的特点，见备注部分），对于正则化的序列，具有很好的度量效果，但对于轨迹路径并不是很适合。

这四种度量方式最主要的贡献就是可以在序列长度不一致的情况下使用，并且可以对抗时间序列不一致的情况。但他们也有自己的局限：

相比较的两个序列需要比较平衡，不容易体现出序列的更多特征，例如加速减速等
受道路轨迹上的噪音影响，这些轨迹度量方式的效率受到很大限制

基于轨迹形状的相似度计算

这些轨迹的相似度计算方式是期望捕捉轨迹的形状特征，最为知名的算法就是Hausdorff距离和Frechet距离了。

Hausdorff

表述的是两个度量空间之间的距离，如下图所示，X，Y分别属于两个度量的空间。最简单的例子，就是两个度量空间都是点集，那么此时Hausdorff的思路就和基于轨迹点匹配的思路相似了。但是Hausdorff允许我们使用更复杂的度量空间，例如X是轨迹的点集，Y是轨迹的边集。需要注意的是Hausdorff为了达到最小，两个度量空间之间的元素匹配是任意的。

Frechet

Frechet最通俗的理解，就是人牵着狗散步，目标就是找到所需的最短的绳索长度。公式表示如下，需要找到两条轨迹之间最佳的对应规则，在这个规则下对应点（或者对应段）之间距离的最大值就是Frechet距离。因为需要找到最佳的匹配规则，所以Frechet算法的时间复杂度也比较高On^2log(n^2)。

Discrete Frechet

因为Frechet距离的时间复杂度很高，因此提出了discrete Frechet距离，他简化了寻找最优匹配规则，使用了在轨迹扭曲距离里面的思想，生成轨迹矩阵W在W中计算discrete Frechet距离。

One Way Distance

OWD算法通过遍历一条轨迹中的轨迹点和另一条轨迹之间的距离的和的方式来进行计算。比较类似于求两条轨迹之间面积对应轨迹长度的平均值。算法思想如下图所示

算法的一种具体实现方式如下图所示，其时间复杂度是n^2logn

此外OWD算法也有一种基于网格的计算方式OWDg，时间复杂度会比上述的实现方式小很多。

总结

Frechet和Discrete Frechet 距离都是满足metric类型的度量方式，满足三角不等式。他们在轨迹段之间的相似度度量是比较优异的，但是不适合做整体轨迹之间的相似度比较，（容易受到某个极端最大距离之间的干扰）。
Discrete Frechet比Frechet距离的计算性能更优，但是它不是metric类型的度量。
OWD算法可以将轨迹作为一个整体考虑进去，包括轨迹的形状和物理距离。算法的复杂度也比较高；OWD网格算法的时间复杂度低很多，但同时也受到了网格大小对最终结果的影响明显的问题。