路径匹配之单向距离OWD算法

mythsman

发布于 2022-11-14 14:10:29

2.2K0

** OWD(One Way Distance)**算法也是一种描述两个路径之间相似度的方法，最早大概提出于06年左右。最朴素的OWD算法的思路也非常简单，就是把路径之间的距离转化为点到路径的距离再加以处理。这里只对这种算法做简要介绍，至于深层次的理论有空再研究论文。

在定义路径间的距离D_{owd}之前，我们先定义点到路径的距离D_{point}：

对于点p和一个由多个点组成的路径T，定义他们之间的距离为

D_{point}(p,T)=min_{q \in T} D_{Euclid}(p,q)

其中D_{Euclid}(p,q)表示p.q之间的欧式距离。

然后，我们定义路径T_1到路径T_2的单向距离D_{owd}(T_1,T_2)为:

D_{owd}(T_1,T_2)=\frac1{|T_1|}(\sum_{p\in T_1}D_{point}(p,T_2))

（对于非离散的路径，我们可以把他看成是一个积分过程）

很容易看出来，这个单向距离不具有对称性，即D_{owd}(T_1,T_2)与D_{owd}(T_2,T_1)不一定相等。那么为了得到一个对称的结果，我们定义一个新的度量标准：

D(T_1,T_2)=\frac12(D_{owd}(T_1,T_2)+D_{owd}(T_2,T_1))

这就是OWD距离中最终用来判定路径相似度的标准。

从OWD距离计算的方式就可以看出，他能够很好的对不同长度的路径间距离进行归一化，而且对于噪声敏感度比较低。

Bin Lin, Jianwen Su, One Way Distance: For Shape Based Similarity Search of Moving Object Trajectories. In Geoinformatica (2008)

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除