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

简述

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

定义

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

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

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

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

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

很容易看出来，这个单向距离不具有对称性，即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)