如何判断两条轨迹（或曲线）的相似度？

比如上图，虽然它们的重合度不高，但是它们的结构是一样的，应当认为它们是很相似的，请问如何量化的判断呢？有什么好的算法？

有关回应 · 2021-5-14 21:02:07

判断两条轨迹的相似性方法有很多
基于点方法： EDR，LCSS，DTW等
基于形状的方法： Frechet， Hausdorff
基于分段的方法：One Way Distance, LIP distance
基于特定任务的方法：TRACLUS， Road Network，grid等
附上本人总结的Trajectory Distance slides：

有关回应 · 2021-5-14 21:02:08

有这么个距离度量...叫
时间翘曲距离(Canonical Warping Distance)
一个点集经过平移,旋转,放缩后得到的点集与原来的点集的距离为0(时间翘曲意义下).
也就是具有平移不变性,旋转不变性,标度不变性

--------------------------------------------------------------------------------
虽然这个名字取得很科幻,但是思想很简单
从1维情况说起:有两个时间序列比如:
A:{1, 2, 3, 5, 8, 13, 21, 34, 55, 89}
B:{0, 1, 1, 2, 3, 5, 8, 13, 21, 34}

从欧几里得距离上看不知差到哪边去了
但是实际上这两个曲线极其相似(本来就是同一个)...
什么情况下这两个时间序列才能相似呢?
时间扭曲
A从1-5花了3时间,B花了5时间..
所以只要扭曲下A在t=1-3时的时间标度就能对齐了!

一维情景大概相当于语音识别中用到的DTW(DynamicTimeWarping)动态时间规划算法,用于判断不同音长,不用音高,不同音调的声音是否是同一个音节...

二维情景复杂得多,不过也类似看成存在一种时空扭曲使得两个点集相似就行了...
当然也能作用于更高维度...

有关回应 · 2021-5-14 21:02:09

谢瑶。。。 @Macrofuns果然验证了你没有看我paper的method。。。

做过一个小研究是关于判断曲线的相似性的，点赞答案1已经基本上解决了题主的问题。使用归一化后的Fréchetdistance即可。另外也可使用Hausdorff distance，但是使用效果不如前者。
推荐几篇论文仅供参考：
Alt H, Godau M (1995) Computing the Fréchetdistance between two polygonal curves International Journal of ComputationalGeometry & Applications 5:75-91. doi:10.1142/S0218195995000064
Fréchet MM (1906) Sur quelques points ducalcul fonctionnel Rendiconti del Circolo Matematico di Palermo (1884-1940)22:1-72. doi:10.1007/BF03018603

此外，可以使用离散化的方法使用Fréchet distance，以便于实际编程计算，同推荐一篇离散化的文章供参考，里面有该方法的伪代码，另matlab也有现成的package，搜搜即可。

Eiter T, Mannila H (1994) Computing discreteFréchet distance See Also

最后推荐一个应用该方法的实例，为了解决Fréchet distance中阈值的问题对其进行了标准化从而得到一个相似指数。

Wang J, Xu C, Tong S, Chen H, Yang W (2013)Spatial dynamic patterns of hand-foot-mouth disease in the People's Republic ofChina Geospatial health 7:381-390

了解有限，对于该方法的代码实现问题我也存在疑虑，如有问题和了解欢迎探讨。

有关回应 · 2021-5-14 21:02:10

可以使用Fréchet distance 特别是如果你已经有了trajectory.
当然了不会是纯粹的Fréchet distance. 要先normalize一下再使用...

有关回应 · 2021-5-14 21:02:11

类聚问题和模式识别问题会讲到。
不知道别人会怎么处理：我的方式是曲线离散化，然后通过计算Hausdor distance评价其匹配度。当然参数设置可能引起评价结果的不同，但是只要能将相似的图形从一大堆图形库中跳出来，目的就达到了。

如何判断两条轨迹（或曲线）的相似度？

5 个回复

浏览过的版块