RANSAC

RANSAC (Random Sample Consensus) は、Fischler & Bollesによって1981年に導入され、SLAMとマルチビュー幾何学において支配的なロバスト推定手法である。パラメトリックモデル(essential matrix、homography、カメラの姿勢、平面、…)を、外れ値(誤った特徴マッチ、遮蔽、動く物体)によって汚染されたデータにフィッティングする。小さなランダムサンプルから繰り返しモデルを仮説として立て、合意によってスコア付けすることで実現する。

アルゴリズム

$s$ 個の対応点からなる最小サンプル $S$ を一様ランダムに引く( $s$ = モデルを決定する最小の数: essential matrixには5点、homographyには4点、P3Pには3点、線形8点法によるfundamental matrixには8点)。
サンプルにモデル $\theta_S$ をフィッティングする。
インライアを数える。誤差閾値 $\epsilon$ (例えば数ピクセルのSampson距離や再投影誤差)以内で $\theta_S$ と整合するデータ点。
$N$ 回反復し、最大のインライア集合を持つモデルを保持する。
任意選択で、すべてのインライアに対して最小二乗法でモデルを再フィッティングする(そしてしばしば再フィッティングを反復する)。

重要な洞察: 外れ値が50%であっても、十分な試行の後には全インライアの小さなサンプルが合理的な確率で引かれ、正しいモデルは汚染されたサンプルにフィッティングされたモデルよりもはるかに多くの合意を集める。

反復回数はどれくらい必要か

インライア比を $w$ とする。 $s$ 点のサンプル1つが全インライアである確率は $w^s$ であるため、 $N$ 個のサンプルの少なくとも1つが全インライアである確率は

P(\text{success}) = 1 - (1 - w^s)^N

$P(\text{success}) \geq 1 - \eta$ (例えば信頼度99%のために $\eta = 0.01$ )を要求すると、

N = \frac{\log \eta}{\log(1 - w^s)}

が得られる。 $w = 0.5$ 、 $\eta = 0.01$ の場合の例:

ソルバー	$s$	$N$
5点essential matrix	5	$\approx 145$
8点fundamental matrix	8	$\approx 1177$

反復回数はサンプルサイズに対して指数関数的に増大する — これがまさに、RANSACの内部で最小ソルバー(5点E、P3P)がより大きな線形ソルバーよりも好まれる理由である。

Adaptive RANSACは $N$ を事前に固定しない。これまでに見つかった最良のインライア集合から $w$ を再推定し、 $N$ を再計算し、現在の推定値に対して十分なサンプルが引かれた時点で早期に終了する — 通常、簡単な場面でははるかに少ない反復で済む。

実践上の注意点

閾値 $\epsilon$ は計測雑音(ピクセル単位)を反映すべきである。厳しすぎると良いデータを排除し、緩すぎると外れ値を許容する。
退化サンプル(あるモデルにおける同一直線上/同一平面上の点)は検出して再抽出する必要がある。
変種: PROSAC(品質ランク付けされたマッチを先にサンプリングする)、LO-RANSAC(有望なモデルの局所最適化)、MLESAC(インライア数ではなく尤度でスコア付けする)、そしてMaxCon合意最大化などの大域的に最適な代替手法。
RANSACの後、残っている小さな誤差は、非線形精密化の内部でM推定量/ロバストカーネルによって処理される。

SLAMにおける意義

特徴ベースのパイプラインにおけるあらゆる幾何推定ステップはRANSACの内部で実行される。初期化と2D–2Dモーションのためのessential/fundamental matrix、平面的な場面のためのhomography、トラッキングと再ローカライゼーションのためのPnP、ICPの対応点の枝刈り、そしてループクロージャの検証などである。
記述子マッチングだけでは、20〜50%の誤ったマッチが日常的に発生する。RANSACなしでは、最小二乗推定値は任意に汚染される(最小二乗法は外れ値に対する破綻許容度がゼロである)。
場所認識からのループクロージャ候補は、姿勢グラフに追加される前にRANSACで幾何学的に検証される — 1つの偽ループ制約がマップ全体を破壊しうる。

ハンズオン

RANSAC ハンズオン