2D-2D correspondence

2枚の画像間の特徴点マッチングが与えられている(まだ3D情報は存在しない)とき、2D-2D幾何は相対的なカメラ運動を推定する。主力となる3つのモデルは基本行列(essential matrix)、基礎行列(fundamental matrix)、**ホモグラフィ(homography)**であり、それぞれ最小解法または線形解法をRANSACでラップして推定される。

基本行列に対する5点アルゴリズム

カメラが校正済みであれば、基本行列 $E$ は5組の対応点から推定できる(Nister, 2004)。制約は以下の通り:

エピポーラ制約: $\mathbf{x}_2^T E\,\mathbf{x}_1 = 0$ ( $E$ の9個の要素に関して線形)。
内部制約: $\det(E) = 0$ と $2EE^TE - \mathrm{trace}(EE^T)E = 0$ (3次多項式)。

結果として最大10個の実数解が得られ、追加の点によって曖昧性が解消される。RANSACと組み合わせることで、5点アルゴリズムは実際には基本行列推定の第一選択となっている。最小サンプル数が小さいほど、同じ内点率でもRANSACの反復回数が大幅に少なくなるからである。

基礎行列に対する8点アルゴリズム

基礎行列 $F$ は7自由度を持つ。8組以上の対応点があれば、8点アルゴリズム(Longuet-Higgins, 1981; Hartley, 1997)はSVDを用いて線形同次系 $A\mathbf{f} = 0$ ( $\mathbf{f} = \mathrm{vec}(F)$ )を解く。Hartleyは、解く前に点座標を正規化(平均ゼロ、分散1)すると数値的な条件数が劇的に改善することを示した ―― 実際に誰もが使っているのは「正規化8点アルゴリズム」である。解いた後、推定された $F$ の最小特異値をゼロにすることでランク2制約を課す。

ホモグラフィのための直接線形変換

シーンが平面である、あるいは運動が純粋な回転である場合、ホモグラフィ $H$ が対応関係を説明する。各対応 $\mathbf{x}' \sim H\mathbf{x}$ は $H$ の8自由度に対して2つの線形方程式を与える。 $N \geq 4$ 組の対応があれば、DLTは $2N \times 9$ の行列を積み重ねてSVDにより $A\mathbf{h} = 0$ を解く。ここでも正規化が重要である。

最小解法が重要な理由: RANSACの反復回数

特徴点マッチングには外れ値が含まれるため、上記のすべての解法はRANSAC内部で実行される: 最小サンプルを抽出し、モデルを当てはめ、内点数を数え、繰り返す。内点率を $w$ 、サンプルサイズを $s$ とすると、 $N$ 回の反復のうち少なくとも1回が全内点サンプルとなる確率は $1 - (1 - w^s)^N$ であり、成功確率 $1 - \eta$ を要求すると

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

が得られる。 $w = 0.5$ の場合、8点アルゴリズム( $s = 8$ )は $N \approx 1177$ 回の反復を必要とするのに対し、5点アルゴリズム( $s = 5$ )はわずか $N \approx 145$ 回で済む。 $s$ に対する指数的な依存性こそが最小解法を用いる理由のすべてであり、3D情報が存在するようになった時点でP3P(s = 3)が好まれる理由でもある。

モデルから運動へ

RANSACが内点上で最良のモデルを選択した後:

$E$ はSVDによって4つの候補姿勢 $[R|\pm\mathbf{t}]$ に分解され、キラリティチェック(三角測量した点が両カメラの前方にあること)によって正しいものが選ばれる。並進はスケールを除いて(up to scale)復元される。
$H$ も同様に、回転、平面法線、スケール付き並進に分解できる(こちらも複数解の曖昧性を持つ)。
その後、内点となった対応点が三角測量され、最初のランドマークが作られる。

モデルの選択

退化した構成には注意が必要である: 平面シーンや純粋な回転は $F$ / $E$ の推定を不良設定にし、一般的な3Dシーンはホモグラフィの仮定を破る。ORB-SLAMは単眼初期化の際に両方のモデルを当てはめ、モデルごとのスコアによって勝者を決めることで有名である。

よくある落とし穴

8点アルゴリズムやDLTの前に正規化を省略すること: 生のピクセル座標(数百から数千)は $A$ を破滅的に条件の悪いものにする。
純粋な回転下で $E$ を推定すること: $\mathbf{t} \to \mathbf{0}$ になると基本行列は退化する。この場合を検出する(あるいはホモグラフィを当てはめる)べきであり、ゴミのような姿勢を信頼してはならない。
内点数だけを信頼すること: シーンが3Dであっても、支配的な平面上でホモグラフィが多数の内点を集めることがある。生の内点数ではなく、モデルごとのスコアリング/モデル選択を用いること。

SLAMにおける意義

2D-2D対応は単眼SLAMの入口である: マップが存在する前に最初の相対姿勢(スケールを除く)をブートストラップし、その後三角測量によってランドマークが作られ、パイプラインは2D-3D(PnP)トラッキングに切り替わる。同じ解法群は、ループクロージング候補を幾何的に検証する際にも用いられ、COLMAPのようなStructure-from-Motionパイプラインの基盤にもなっている。

ハンズオン

エピポーラ幾何ハンズオン