Frechet

作者: Yung968 | 来源:发表于2019-01-31 22:00 被阅读2次

    面临的问题

    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对噪声也非常敏感。

    但是假如做了噪声匹配会怎么样呢?

    其实结果也不是最好,因为最终它还是去了一个极值——所有匹配值中的最大值。显然这样取舍会导致丢失很多的重要信息,甚至可能把不重要的信息选作一个代表值。

    相关文章

      网友评论

        本文标题:Frechet

        本文链接:https://www.haomeiwen.com/subject/qoglsqtx.html