フレシェ距離で曲線同士の距離を測る

フレシェ距離は、二つの点がそれぞれの曲線上を始点から終点までに 二つの距離がなるべく小さくなるように動かしたときの最大の2点間距離 をだす.

連続フレシェ距離においては、以下のような曲線A, B上の2点の最小距離の最大を求めることになるため、ボトルネック距離となる. そのためノイズに弱い距離となる。 式は以下に示される.

$$F(A,B)=\inf _{\alpha ,\beta }\,\,\max _{t\in [0,1]}\,\,{\Bigg \{}d{\Big (}A(\alpha (t)),\,B(\beta (t)){\Big )}{\Bigg \}}$$

離散フレシェ距離の場合は、二つの点列のn,m個のとき、 時間計算量が $O\left(nm\right)$となるDynamic Time Warpingというアルゴリズムが知られている. このとき、全体の最小のコストになるような組み合わせを求めるため, 誤差の合計値になる。ボトルネック距離と比べてノイズに強い