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

概要

フレシェ距離で二つの曲線同士の距離を測る。 離散的な点列の場合では離散フレシェ距離を求めるDTWが有名である. 連続的な曲線においてはボトルネック距離となる.
Facebookシェア Twitterツイート LINEで送る このエントリーをはてなブックマークに追加
この章を学ぶ前に必要な知識
0
条件
  • ある方向に二つの点が曲線を動くことを想定
  • 点は常に一方向にしか動けないものとする
効果
  • 二曲線を二つの点が最小の距離になるように動くときの最大値を距離とする
ポイント
  • ハウスドルフ距離では交差するギザギザに対応できないが、フレシェ距離では可能
  • ボトルネック距離なので、ノイズに弱い

解 説

フレシェ距離は、二つの点がそれぞれの曲線上を始点から終点までに 二つの距離がなるべく小さくなるように動かしたときの最大の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 \}}$$
曲線A, B上を移動するときの2点間の最短距離の最大距離(Wikipediaより)
離散フレシェ距離の場合は、二つの点列のn,m個のとき、 時間計算量が O(nm)O(nm)となるDynamic Time Warpingというアルゴリズムが知られている. このとき、全体の最小のコストになるような組み合わせを求めるため, 誤差の合計値になる。ボトルネック距離と比べてノイズに強い
DTWとの関係
この章を学んで新たに学べる
Comments

Reasons
>>隠す