貢献

OpenCVの calib3d モジュールに統合された部分は、C++で書かれたRANSACベースの汎用フレームワークUSAC (namespace usac) である。このフレームワークには、サンプリング、検証、局所最適化のためのさまざまな最先端手法が含まれている。このフレームワークの主な利点は、任意の推定問題に対する独立性とモジュール構造である。そのため、新しいソルバや手法を簡単に追加・削除できる。現時点では以下のコンポーネントが含まれている。

Sampling method:
1. Uniform – [94] で提案された標準的なRANSACサンプリングで、最小部分集合を独立かつ一様にランダムに抽出する。提案フレームワークにおけるデフォルトのオプション。
2. PROSAC – 入力データ点が品質順にソートされていることを前提とし、最も有望な点からサンプリングを開始できる手法 [60]。この手法における対応点は、例えばSIFT検出器から得られる最良マッチと2番目のマッチの記述子距離の比でソートできる。この手法は、良いモデルを見つけてはるかに早く終了できるため、使用が推奨される。
3. NAPSAC – 初期点を一様にランダムに取り、最小サンプルの残りの点を初期点の近傍から取るサンプリング手法 [207]。この手法はモデルが局在している場合に潜在的に有用となりうる。例えば平面フィッティングなどである。しかし実際には、退化の問題や最適な近傍サイズの定義に苦労する。
4. Progressive-NAPSAC – NAPSACに似ているが、局所的なサンプリングから始まり徐々に大域的なサンプリングへ収束していくサンプラー [19]。この手法は、局所的なモデルが想定されるがデータの分布が任意でありうる場合に非常に有用となりうる。実装版では、PROSACと同様にデータ点が品質順にソートされていることを前提とする。
Score Method. USAC as well as standard RANSAC finds model which minimizes total loss. Loss can be represented by following functions:
1. RANSAC – 2値の0/1損失。アウトライアには1、インライアには0を割り当てる。できるだけ多くのインライアを見つけることが目的の場合に良い選択肢である。
2. MSAC – 点からモデルへの距離の打ち切り二乗誤差。フレームワークにおけるデフォルトのオプション。RANSACスコアを使う場合ほどインライアは多くならないかもしれないが、より正確になる。
3. MAGSAC – スコアを計算するためのしきい値不要の手法 [20]。ただし、最大シグマ(ノイズの標準偏差)レベルを用いて、点の残差をシグマにわたって周辺化する。点のスコアは、その点がインライアである尤度を表す。手法がしきい値を必要としないため、画像ノイズが未知の場合に推奨されるオプションである。ただし、終了処理自体は誤差がしきい値未満となる点の数に基づくため、少なくとも近似的なしきい値を与えることが依然として推奨される。しきい値に0を与えると、この手法は最大反復回数に達した後にモデルを出力する。
4. LMeds – 二乗誤差距離の最小中央値。フレームワークでは、中央値の探索はクイックソートアルゴリズムを用いて $O(n)$ の計算量で効率的に実装されている。なお、LMedsはインライア比が50%未満の場合には正しく機能するとは限らないが、それ以外の場合にはこの手法は頑健であり、しきい値を必要としない。
Error metric which describes error distance of point to estimated model.
1. 再投影距離 – アフィン行列、ホモグラフィ行列、射影行列に使用される。ホモグラフィについては対称再投影距離も使用できる。
2. Sampson距離 – 基礎行列(Fundamental matrix)に使用される。
3. 対称幾何距離 – 基本行列(Essential matrix)に使用される。
Degeneracy:
1. DEGENSAC – 基礎行列(Fundamental matrix)の推定において、最小サンプル中に支配的な平面上にある点が少なくとも5つあるモデルを効率的に検証・復元する手法 [63]。
2. 共線性テスト – アフィン行列およびホモグラフィ行列の推定において、3点が直線上にないかをチェックする。ホモグラフィ行列については点が平面上にあるため、最小サンプル中の点が、サンプル中の任意の2点を通る任意の直線に対して同じ側にあるかをチェックするテストが適用される(反射は想定しない)。
3. 向き付きエピポーラ制約 – エピポーラ幾何のための手法 [62] で、モデル(基礎行列および基本行列)が、カメラの前方に見える点を持つことを検証する。
SPRT検証 – ランダムにシャッフルした点上でモデルを評価し、インライアの確率、推定にかかる相対時間、出力モデルの平均数などによって与えられる統計的性質を用いてモデルを検証する手法 [190]。すべての点について明示的に誤差を計算することなく、悪いモデルを非常に素早く棄却できるため、フレームワークを大幅に高速化する。
Local Optimization:
1. 局所最適化RANSAC – 非最小推定によって、これまでの最良モデルを反復的に改善する手法 [61]。フレームワークにおけるデフォルトのオプション。この手順は最も高速であり、他の局所最適化手法に劣らない。
2. Graph-Cut RANSAC – これまでの最良モデルを洗練する手法 [18] で、データ点の空間的整合性を利用する。この手順は非常に高精度だが、計算は遅い。
3. Sigma Consensus – 非最小の重み付き推定を適用してモデルを改善する手法 [20] で、重みはMAGSACスコアと同じ論理で計算される。この手法はMAGSACスコアと組み合わせて使用するのが良い。
Termination:
1. Standard – 独立かつ一様なサンプリングのための標準的な式。
2. PROSAC – PROSACのための終了処理。
3. SPRT – SPRTのための終了処理。
Solver. In the framework there are minimal and non-minimal solvers. In minimal solver standard methods for estimation is applied. In non-minimal solver usually the covariance matrix is built and the model is found as the eigen vector corresponding to the highest eigen value.
1. Affine2D行列
2. ホモグラフィ行列 – 最小ソルバにはOpenCVのRHO (ガウスの消去法) アルゴリズムが使用される。
3. 基礎行列(Fundamental matrix) – 7点アルゴリズムでは、SVDの代わりにガウスの消去法(上三角行列への消去と後退代入)を用いて2つのヌルベクトルを求め、次に3次多項式を解く。8点ソルバでもガウスの消去法が使用される。
4. 基本行列(Essential matrix) – ガウスの消去法を用いて4つのヌルベクトルを求める。次に [257] で述べられているGröbner基底に基づくソルバが使用される。基本行列は、複素固有値を伴う固有値分解を必要とするため、LAPACK または Eigen がインストールされている場合にのみ計算できる。
5. Perspective-n-Point – 最小ソルバは古典的な3点法で、最大4つの解を持つ。RANSACにとってサンプルサイズが小さいことは重要な役割を果たす。必要な反復回数が少なくなるためであり、さらに平均してP3Pソルバは約1.39個のモデルを推定する。また、UsacParams を用いた新しいバージョンの solvePnPRansac(...) では、空の内部行列 InputOutputArray cameraMatrix を渡すオプションがある。行列が空の場合、直接線形変換(DLT)アルゴリズム(6点によるPnP)を用いて、フレームワークは回転ベクトルと並進ベクトルだけでなくキャリブレーション行列も出力する。

また、フレームワークは並列に実行することもできる。並列化は、複数のRANSACを作成し、それらが2つのアトミック変数 bool success と int num_hypothesis_tested を共有する方法で行われる。これらの変数によって、すべてのRANSACがいつ終了しなければならないかが決定される。いずれかのRANSACが成功裏に終了すると、他のすべてのRANSACも終了する。最後に、すべてのスレッドから最良モデルが同期される。PROSACサンプラーを使用する場合、サンプリングは逐次的に行われるため、スレッドは同じサンプラーを共有しなければならない。ただし、フレームワークのデフォルトオプションを使用する場合、並列RANSACは各スレッドの実行頻度に依存するため決定的ではない。決定的にする最も簡単な方法は、SPRTと局所最適化を使わず、かつ基礎行列(Fundamental matrix)用ではない形でPROSACサンプラーを使用することである。これらは内部で乱数生成器を使用するためである。

NAPSAC、Progressive NAPSAC、Graph-Cutの各手法では、近傍グラフを構築する必要がある。フレームワークではそれを行う3つのオプションがある。

NEIGH_FLANN_KNN – OpenCVのFLANN K近傍法を用いて近傍グラフを推定する。KNNのデフォルト値は7である。KNN法はサンプリングには良く機能するが、GC-RANSACには適していない。
NEIGH_FLANN_RADIUS – 前の場合と同様に、距離が20ピクセル未満の近傍点を見つける。
NEIGH_GRID – ハッシュテーブルを用いて、セル内のタイル点から点の近傍を探索する。この手法は [19] で説明されている。NEIGH_FLANN_RADIUS より精度は劣るが、大幅に高速である。

なお、NEIGH_FLANN_RADIUS と NEIGH_GRID は、3次元のオブジェクト点が存在するためPnPソルバには使用できない。

新しいフラグ:

USAC_DEFAULT – 標準的なLO-RANSACを持つ。
USAC_PARALLEL – LO-RANSACを持ち、複数のRANSACを並列に実行する。
USAC_ACCURATE – GC-RANSACを持つ。
USAC_FAST – 局所最適化ステップの反復回数を少なくしたLO-RANSACを持つ。RANSACスコアを用いてインライア数を最大化し、より早期に終了する。
USAC_PROSAC – PROSACサンプリングを持つ。なお、点はソートされている必要がある。
USAC_FM_8PTS – LO-RANSACを持つ。8点ソルバによる基礎行列に対してのみ有効である。
USAC_MAGSAC – MAGSAC++を持つ。

すべてのフラグはSPRT検証を使用する。そして最後に、これまでで最良のモデルが、見つかったすべてのインライアの非最小推定によって磨き上げられる。

その他の重要な引数いくつか:

randomGeneratorState – OpenCVのすべてのUSACソルバは決定的である（すなわち、同じ点と引数に対して同じ結果を返す）ため、新しい状態を与えることで新しいモデルを出力する。
loIterations – 局所最適化（Local Optimization）法の反復回数。デフォルト値は10である。loIterations を増やすと出力モデルはより正確になりうるが、計算時間も増加する可能性がある。
loSampleSize – 局所最適化のための最大サンプル数。デフォルト値は14である。なお、loSampleSize を増やすとモデルの精度が向上しうるが、計算時間も増加する。ただし、値は100未満に保つことが推奨される。少ない点数での推定の方が高速かつロバストだからである。

サンプル:

opencv/samples ディレクトリに3つの新しいサンプルファイルがある。

epipolar_lines.cpp – main 関数の入力引数は2枚の画像へのパスである。次にSIFT検出器を用いて対応点が求められる。基礎行列は仮の対応点からRANSACを用いて求められ、エピポーラ線が描画される。
essential_mat_reconstr.cpp – 入力引数は、画像名と単一の内部行列を含むデータファイルへのパスと、これらの画像が置かれているディレクトリである。対応点はSIFTを用いて求められる。基本行列はRANSACを用いて推定され、回転と並進に分解される。次に、射影行列を持つ2つの相対姿勢を構築することで、画像点が三角測量によりオブジェクト点に変換される。3次元平面フィッティングを伴うRANSACを実行することで、オブジェクト点と対応点が平面にクラスタリングされる。
essential_mat_reconstr.py – .cppファイルと同じ機能を持つが、点を平面にクラスタリングする代わりに、オブジェクト点の3次元マップが描画される。


原著者	Maksym Ivashechkin
互換性	OpenCV >= 4.0

目次

貢献

新しいフラグ:

その他の重要な引数いくつか:

サンプル: