最終更新:2014-04-01 (火) 02:29:33 (2289d)  

RANSAC
Top / RANSAC

RANdom SAmple Consensus

ノイズが混じっているデータからもっともらしいデータを抽出することが出来るアルゴリズム

アルゴリズム

  • 総データ個数がU個あるデータから、ランダムでn個のデータを取り出します。
  • 取り出したn個のデータから、パラメータを求めます。
    • (取り出すデータの個数ですが、これは求めるべきパラメータの数に比例するようです)
  • 求めたパラメータを、総データ点数から取り出したn個のデータを除いたものに式を当てはめ、
    • 観測されたデータと2.で求めたパラメータの誤差を計算します。
  • 誤差が許容範囲内であれば、パラメータに対して投票を行います。
    • 1~4を繰り返し、投票数が一番多かったパラメータをひとまず採用します。(これを仮パラメータとします)
  • 仮パラメータを使ってすべてのデータに再度式を適用し、誤差が許容範囲内のものを抽出します。(この時点で雑音データがほぼ取り除かれます)
  • 抽出したデータを元に、再度パラメータを求めます。
  • 求まったパラメータがこのデータのもっともらしいパラメータとなります。

関連

  • PROSAC?
  • MLESAC?
  • M推定?

参考