RANSAC
読み: らんさっく
Random Sample Consensus の略。外れ値を含むデータからモデルパラメータを頑健に推定する反復アルゴリズム。画像のホモグラフィ推定や 3D 点群のフィッティングに不可欠な手法である。
RANSAC (Random Sample Consensus) は、1981 年に Fischler と Bolles が提案した頑健推定アルゴリズムである。データに多数の外れ値 (アウトライア) が含まれる状況で、正しいデータ点 (インライア) のみに基づくモデルを推定する。最小二乗法のように全データを均等に扱う手法では外れ値に引きずられるが、RANSAC はこの問題を回避する。
アルゴリズムの手順は単純である。まずデータからモデル推定に必要な最小数の点をランダムに選択し、仮モデルを構築する。次に全データ点と仮モデルの距離を計算し、閾値以内の点をインライアとしてカウントする。この操作を繰り返し、最もインライア数が多いモデルを最終結果とする。
- 反復回数の決定: インライア率
w、必要サンプル数n、成功確率pからk = log(1-p) / log(1-w^n)で必要反復回数を算出する。インライア率 50%、4 点ホモグラフィ、成功確率 99% の場合は約 72 回 - 閾値設定: インライア判定の距離閾値はノイズレベルに依存する。ピクセル単位で 1〜3 程度が一般的。閾値が小さすぎるとインライアが減り、大きすぎると外れ値を取り込む
- 改良版: MSAC (M-estimator SAC) はインライアの距離に応じたスコアリングを行い、PROSAC は対応点の品質順にサンプリングして収束を高速化する
画像処理では特徴点マッチング後のホモグラフィ推定や基礎行列推定に RANSAC が標準的に使われる。OpenCV の cv2.findHomography() は内部で RANSAC を実行し、外れ値マスクを返す。