面临的问题
Frechet算法简介
一个人在遛狗,他们走在各自的道路上。他们可能有着不同的速度,但是都不能往回走。最终的目的,就是求满足要求的绳子的最小长度。
Frechet距离是衡量两个轨迹之间相似度的方法,它考虑到了位置和时间上的顺序。通常它要比原始的Hausdorff距离表现的好。
该方法原先用于连续曲线的匹配,在连续曲线匹配的领域,通常Frechet的表现要比Hausdorff好。
A为主人行走轨迹,B为狗的运动轨迹,在此情况下可知Fréchet距离为0.25时刻或者0.75时刻人和狗之间的距离。
显然连续算法不适用于离散的时空轨迹,因此该算法需要离散化。
离散Frechet距离:
离散Fréchet距离是连续Fréchet距离的近似,当曲线所选取的离散点足够多时离散Fréchet距离近似等于连续Fréchet距离。
图3中
(a)部分是在两条曲线离散轨迹点较少的情况,可知此时得到的离散Fréchet距离为a2和b2之间的欧拉距离。
(b)部分则表示两条曲线的离散轨迹点较多的情况,而此时的离散Fréchet距离为a2和b之间的欧拉距离。
两种情况下的连续Fréchet距离都为a2和O之间的欧式距离,故随着曲线的离散轨迹点的数量的增加而离散Fréchet距离将逐渐接近于连续Fréchet距离。但是相应的也会增加计算复杂度。
Frechet会试图去匹配所有的点(算法中的min是在做匹配),允许重复,因此对于采样率和轨迹长度没有要求。之后对于所有的匹配长度排序,找一个最大的长度。作为最终的结果。
其实本质上和DTW是一个思想——重复使用某些点,来适应local time shifting。只是DTW把距离都加起来,而Frechet选取一个最大的匹配的距离。
算法:
Frechet优缺点
Frechet和Hausdorff方法一样,都是模式识别领域借鉴而来的算法。其提出时间比较早,实际效果不会很好。
与DTW相比,他们匹配的基本思想是一样的——重复使用某些点。但是在代表点的选取(或者计算)上是不同的。DTW把距离都加起来,而Frechet选取一个最大的匹配的距离。显然Frechet对噪声也非常敏感。
但是假如做了噪声匹配会怎么样呢?
其实结果也不是最好,因为最终它还是去了一个极值——所有匹配值中的最大值。显然这样取舍会导致丢失很多的重要信息,甚至可能把不重要的信息选作一个代表值。
网友评论