PROSAC
PROSAC (Progressive Sample Consensus) は、Chum & Matas (2005) によるRANSACの変種であり、通常のRANSACが捨ててしまう事実を活用する。対応点はインライアである可能性が等しくないということであり、通常はそれを予測するマッチごとの品質スコアがある — 記述子距離、あるいはより良い指標として、最近傍と2番目に近い近傍の距離の比であるLoweの比 である。
アイデア
個の仮の対応点を品質の高い順にソートする。すべての個のマッチから均一にサンプリングして最小集合を作る代わりに、PROSACは徐々に成長する部分集合からサンプルを引く。
- 初期の反復では、インライア密度が最も高い上位ランクのマッチ(例えば上位 個、次に上位 個、…)からのみサンプリングする。
- 反復が進むにつれて、サンプリングプールは全体集合に向かって成長し、極限ではPROSACのサンプリング分布はすべてのマッチに対する均一サンプリングに収束する。
形式的には、成長関数によって、プールサイズが から に増加するまでに何回サンプリングを行うかが決まる。各サンプルは、新たに追加されたマッチと、上位 個から引かれた 個のマッチから構成される。設計上の目標は、PROSACがRANSACとほぼ同じサンプルの集合を引くが、品質に基づいた異なる順序で(最も有望なものから先に)引くということである。
アルゴリズムの概略
- 対応点を品質スコアの高い順にソートする。
- 現在のプールサイズ (初期値は )とその成長スケジュールを維持する。
- 各反復で、上記のように上位個のマッチから最小サンプルを構成し、モデルを当てはめ、全ての個の対応点に対して検証する。
- インライア数によって最良のモデルを追跡する。RANSAC式の信頼性基準(非乱択のインライア数と、現在のインライア比推定値に対する十分なサンプル数)が満たされたら停止する。
- 標準的なRANSACと同様に、すべてのインライアに対して最小二乗法で再フィッティングする。
特性
- 速度: 品質ランキングが有益である(上位のマッチが実際にほとんどインライアである)場合、最初の数十回の抽出以内に全インライアのサンプルが見つかり、全体のインライア比が低い場合の均一RANSACよりも桁違いに高速である。全体のインライア比 が非常に悪い(例えば10%)場合でも、上位20個のマッチは90%がインライアである可能性があり、初期プールに対するPROSACの実効的な は劇的に高くなる。
- 最悪の場合でも同じ保証: スコアが有益でない場合、PROSACは標準的なRANSACの動作に緩やかに退化し、同じ停止基準を持つ。
- 同じ検証ステップ: 仮説は依然としてすべての対応点に対するインライアの合意によってスコア付けされるため、偏ったサンプリングプールが最終的なモデル選択を偏らせることはない。
実践上の注意点
- 品質指標が重要である。Lowe比は生の記述子距離よりもはるかに優れたインライア予測子である。
- PROSACはadaptive termination(適応的終了)と自然に組み合わせられる — 最初に見つかった良いモデルが、必要な反復回数を即座に縮小させる。
- OpenCVはUSACフレームワーク(
cv::USAC_PROSAC)にPROSAC式のサンプリングを公開しており、findEssentialMat、findHomography、solvePnPRansacなどで使用できる。 - 初期プールの退化に注意すること。上位ランクのマッチは、しばしば1つの強くテクスチャのあるオブジェクトや平面に集中し、局所的には整合しているがグローバルには誤ったモデル(例えば、essential matrixが欲しいときに、ある1平面のhomographyが得られてしまう)を生じさせることがある。退化チェックは依然として適用すべきである。
SLAMにおける意義
- リアルタイム予算は厳しい。トラッキングは30〜60 Hzで動作し、幾何学的検証はミリ秒単位で完了する必要がある。PROSACは典型的な場面において、より少ない反復回数でRANSAC相当の外れ値除外を実現する。
- SLAMのフロントエンドは、マッチング処理中に必要なマッチスコア(記述子距離、比検定の値)をすでに計算しているため、ランキングは無料で手に入る。
- 候補マッチ集合が大規模かつ強く汚染されており、均一なRANSACであれば数千回の反復を必要とする再ローカライゼーションとループクロージングにおいて特に有用である。