RANSAC
- 別名: Random Sample Consensus
- カテゴリ: Sensing › Perception outputs
- タグ: robust-estimation, computer-vision, point-cloud-processing, outlier-rejection, model-fitting
Random Sample Consensus。データの小さなランダム部分集合にモデルを繰り返しフィットさせ、最も多くの点と一致するモデルを残すことで外れ値を無視する、ロバストなフィッティング手法。
定義
RANSAC(Random Sample Consensus)は、1981 年に Fischler と Bolles が導入した手法で、外れ値を多く含むデータからモデルのパラメータを推定する。最小二乗法によるフィッティングはすべての点を使うため、少数の大きな誤差だけで結果が真値から大きくずれることがある。RANSAC は代わりに単純なループを繰り返す。モデルを定めるのに必要な最小数の点(直線なら 2 点、平面なら 3 点、カメラの位置姿勢や基礎行列なら少数の決まった数)を抽出し、それらにモデルをフィットさせ、全データ点のうちいくつがモデルからしきい値以内にあるかを数える。それらの点がコンセンサス集合、すなわちインライアである。何回か反復した後、コンセンサス集合が最大のモデルを残し、通常はそのインライアすべてに最小二乗法でフィットし直す。
反復回数は確率から決まる。w をインライアの割合、s をサンプルサイズとすると、ランダムなサンプルがインライアだけを含む確率は wˢ であり、信頼度 p で少なくとも 1 つのきれいなサンプルを引くのに必要な反復回数 k は k = log(1 − p) / log(1 − wˢ) となる。この値はインライアの割合が下がるかサンプルサイズが増えると急速に大きくなる。5 点法による相対姿勢推定のように、少ない点で済む最小ソルバーがビジョンで重要なのはこのためである。インライアのしきい値はもう 1 つの重要なパラメータで、真のインライアに予想されるノイズに合わせ、測っている残差の単位で設定しなければならない。
基本のループを改良した変種は多い。MSAC と MLESAC は生のインライア数ではなくロバストなコストで仮説を評価し、PROSAC は最も有望な対応から先にサンプリングし、LO-RANSAC は良い仮説を局所的に改良し、適応型の版はインライアの割合が推定されるにつれて k を更新する。ロボット工学では、RANSAC は点群における平面やプリミティブのセグメンテーション、視覚オドメトリと SLAM での特徴対応のフィルタリング、Perspective-n-Point による姿勢推定、特徴対応からの点群位置合わせ、キャリブレーションに使われる。手順がランダムなので、乱数シードを固定しない限り、実行ごとに結果が異なることがある。
重要な理由
実際のセンサーデータは外れ値だらけである。誤った特徴対応、反射、動く物体、別の面に属する点などがある。RANSAC はそれらがあっても幾何モデルをフィットさせる標準的な方法であり、ほとんどの視覚オドメトリ、SLAM、キャリブレーション、点群セグメンテーションのパイプラインの中に組み込まれている。
主な用途
- 点群における平面、円柱、球のセグメンテーション
- 視覚オドメトリと SLAM における特徴対応の外れ値除去
- Perspective-n-Point によるカメラの位置姿勢推定
- 基礎行列、基本行列、ホモグラフィ行列の推定
- 特徴対応からの大域的な点群位置合わせ
- ノイズのあるセンサーデータへの直線やキャリブレーションモデルのフィッティング
実際の使われ方
モバイルマニピュレータが物体を置く前に、深度カメラの点群からテーブル面を見つける必要がある。ソフトウェアは点群をダウンサンプリングし、RANSAC による平面フィッティングを実行する。3 点を選んでそれらを通る平面を計算し、センサーの深度ノイズよりわずかに大きく設定した距離しきい値以内にある点を数える、という処理を繰り返す。インライアが最も多い平面を最小二乗法でフィットし直し、そのインライアを取り除いて、平面より上に残った点を物体ごとにクラスタリングする。視野に大きな壁や床があると RANSAC がその面を返すことがあるため、エンジニアは平面の法線がおおむね上を向いているかを確認し、結果を再現できるようテストでは乱数シードを固定する。
よくある誤解
- RANSAC は最適なモデルを見つける — 返すのはたまたまサンプリングした中で最良の仮説なので、結果は確率的であり、実行ごとに異なりうる
- 反復を増やせばしきい値の悪さを補える — しきい値は何を一致とみなすかを決めるので、選び方が悪いと、何回反復しても結果に偏りが生じる
- RANSAC はどんな割合の外れ値にも対処できる — 必要な反復回数はインライアの割合が下がると急速に増え、インライアがごく少ないと失敗したり見せかけの構造に捕らわれたりする
- RANSAC は 1 つのモデルしか見つけられない — 基本のアルゴリズムが見つけるのは 1 つだが、逐次型や複数モデル型の変種はインライアを取り除いて繰り返すことで複数の構造を抽出する
知っておくべき人
- 知覚とコンピュータビジョンのエンジニア
- SLAM と視覚オドメトリの開発者
- マニピュレーションのために点群を処理するエンジニア
- キャリブレーションと計測のエンジニア
関連技術
- 最小二乗フィッティング(Least-Squares Fitting)
- M 推定(M-Estimators)
- MSAC と MLESAC
- PROSAC
- ハフ変換(Hough Transform)
- Point Cloud Library
関連用語
- Point Cloud
- Perspective-n-Point
- Visual Odometry
- Iterative Closest Point
- Bundle Adjustment
- Extrinsic Calibration
関連プロジェクト
- pySLAM: Hybrid Python/C++ visual SLAM pipeline with classic and deep-learning front-ends
- AprilTag: The standard visual fiducial marker system for robot localization and pose estimation
- MRPT: Comprehensive C++ toolkit for mobile robotics, SLAM, and sensor-based navigation
- PULP-Dronet: Visual navigation for nano-drones with CNN inference onboard a PULP processor.
- OpenWeedLocator: Low-cost Raspberry Pi weed detector that uses computer vision for precision spot spraying
動画
- RANSAC - 5 Minutes with Cyrill: Cyrill Stachniss
- Dealing with Outliers: RANSAC | Image Stitching: First Principles of Computer Vision