面临的问题

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

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

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