Random sample consensus(RANSAC)

Article(2900 words) 

Random sample consensus - Wikipedia

 

f:id:tom0930:20180602001813p:plain

Fitted line with RANSAC; outliers have no influence on the result.

 0. Abstract

  • Random sample consensus(RANSAC)は,outliers(ノイズ)を含む一連の観測値から数学的モデルのパラメータを推定するための反復法である.(outliersが,推定値に影響を与えないとき.)
  • それゆえ,outliers検出手法としても解釈される.
  • 基本的な仮定は,データがinliersで構成されている,ということ.
  • RANSACは,inliersのデータが与えられると仮定すると,最適にデータを説明・適合するモデルのパラメータを推測することができる手順が存在する.

 

1. Example

  • ある集合が,inliers(=直線に近似できるデータ)outliers(=直線に近似できないデータ)の両方を含むと仮定する.
  • 最小二乗法は,outliersを含む全点に対して最適な直線を近似してしまうため,一般にうまくいかない.
  • 一方,RANSACは計算処理において,outliersを除き,inliersだけを含む直線モデルを見つけようとする.
  • データに対してランダムにサンプリングを行い,直線モデルをフィットさせる.最終的に,最もよくフィットした直線モデルを返す.
  • inliersとoutliersがランダムに混合されたものより,inliersだけの方が直線との関連性が強くなるため,完全に(entirely)正常値からなるランダムなサブセットが,最も良く直線モデルにフィットする.
  • 実際には(In practice),inliersのサブセットがランダムにサンプリングされる保証はない.
  • このアルゴリズムが成功する確率は,データにおけるinliersの割合(proportion),およびいくつかのパラメータの選択に依存する.

 

2. Overview

  • RANSACは,観測値のランダムサンプリングによってモデルのパラメータを推定する学習技術である.
  • inliersとoutliersの両方を含むデータ集合が与えられていれば,RANSACは,最適にフィットする結果を探すために,投票方式(voting scheme)を使う.
  • この投票方式は,以下の2つの仮定に基づいている.
    1. ノイズが多い特徴は,単一モデル(few outliers)に対して一貫して投票しない.
    2. 良いモデル(few missing data)に合意するための十分な特徴が存在する.
  • RANSACアルゴリズムは,反復的に繰り返される以下の2つのステップで構成される.
  1. 最小のデータ項目(直線モデルを推定するなら2点)を含むサンプルサブセットを,入力データの中からランダムにサンプリングする.合致・一致するモデルパラメータは,このサンプルサブセットの要素のみを使うことで計算される.サンプルサブセットの基数は,モデルパラメータを決定するのに最小の数である.
  2. 全体のデータのうちのどの要素がStep1. で取得した推測モデルパラメータによってインスタンス化されたモデルと一致するかをチェックする.ノイズの効果に起因する最大偏差を定義する誤差閾値内の推測モデルパラメータのセットによってインスタンス化されたフィッティングモデルに合致しないならば,データ要素をoutliersとみなす.
  • フィッティングモデルのために取得したinliersのセットはconsensusセットと呼ぶ.
  • RANSACアルゴリズムは,取得したconsensusセットが十分なinliersを得るまで,上記の2ステップを反復的に繰り返す.
  • RANSACが以下のステップを繰り返すことで,目標へと近づいていく.
  1. 元データからランサムサブセットを選択する.このサブセットをhypothetical inliersと呼ぶ.
  2. モデルは,hypothetical inliersのセットにフィットされる.
  3. すべての他のデータはフィットしたモデルに対してテストされる.推定モデルに良くフィットする点群は,consensus setとみなす.
  4. 推定モデルは,十分多くの点がconsensus setとして分類されていれば,理論的にgood.
  5. モデルは,consensus setのすべてのメンバーを使う再推定によって改善できるかもしれない.
  • この手順は,あらかじめ決めた回数だけ繰り返される.

f:id:tom0930:20180602141416p:plain

RANSAC: Inliers and Outliers.

 

3. Algorithm

5. Parameters

6. Advantages and disadvantages

7. Applications

8. Development and improvements

9. Related methods

 

References

RANSAC (Random Sampling Consensus)

ロバスト推定 (robust estimation)

最小二乗法 (least squares method)