Structure from Motion

Structure from Motion（SfM）は、複数の 2D image から、各 image の camera pose と sparse な 3D point cloud を同時に復元する method です。Photogrammetry や 3D Reconstruction pipeline の中心的な component です。直感的には、「同じ点が複数の写真のどこに写っているか」を手がかりにして、camera がどこから見ていたのかと、その点が三次元空間のどこにあるのかを同時に整合させます。

入力と出力

SfM の入力は、同じ scene を異なる viewpoint から撮影した複数 image です。出力は、主に次の二つです。

• 各 image の camera pose
• Feature point に対応する sparse 3D point cloud

より数式寄りに書くと、image $I_i$ における feature observation を $\mathbf{u}_{ij} = (u_{ij}, v_{ij})^\top$ とし、それが world coordinate 上の 3D point $\mathbf{X}_j$ に対応しているとします。Camera $i$ の intrinsics を $\mathbf{K}_i$、rotation を $\mathbf{R}_i$、translation を $\mathbf{t}_i$ とすると、理想的な投影は次のように書けます。

$$\hat{\mathbf{u}}_{ij} = \Pi_i(\mathbf{X}_j) = \pi\left(\mathbf{K}_i(\mathbf{R}_i\mathbf{X}_j + \mathbf{t}_i)\right)$$

ここで、$\Pi_i$ は camera $i$ による pixel への projection function です。$\pi([x, y, z]^\top) = (x/z, y/z)^\top$ は homogeneous coordinate を通常の 2D coordinate に戻す操作です。$\mathbf{R}_i\mathbf{X}_j + \mathbf{t}_i$ は、world coordinate の点 $\mathbf{X}_j$ を camera coordinate に移す部分です。

この式の気持ちは、「三次元点を camera 座標に持ってきて、camera intrinsics を通して画像平面に投影すると、観測された feature の位置に来てほしい」というものです。SfM は、この希望ができるだけ多くの観測で同時に成り立つように、camera pose と 3D point を推定します。

Typical pipeline

SfM の典型的な pipeline は次の通りです。

この pipeline は、次のように「対応点を作る段階」と「幾何を整合させる段階」に分けて理解すると見通しが良くなります。

段階	何をしているか	代表的な数式・制約
Feature extraction / matching	複数 image の間で同じ 3D point に由来しそうな feature を対応付けます。	Descriptor 距離、ratio test
Geometric verification	見かけの一致ではなく、二 view geometry と整合する match だけを残します。	$\tilde{\mathbf{u}}_j^\top\mathbf{F}_{ji}\tilde{\mathbf{u}}_i = 0$
Camera registration	既存の sparse map に対して、新しい image の pose を推定します。	PnP の再投影誤差最小化
Triangulation	複数 view の viewing ray から 3D point を作ります。	$\tilde{\mathbf{u}}_{ij} \times (\mathbf{P}_i\tilde{\mathbf{X}}_j)=\mathbf{0}$
Bundle adjustment	すべての camera と 3D point を同時に微調整します。	再投影誤差の総和最小化

SfM の全体 objective

SfM の中心にある最適化は、観測された feature position と、推定した camera・3D point から再投影した位置との差を小さくすることです。観測集合を $\mathcal{O}$ とすると、典型的な objective は次のように書けます。また、intrinsics $\mathbf{K}_i$ は既知として固定する場合もありますし、焦点距離や distortion を含めて最適化する場合もあります。

$$\min_{\{\mathbf{K}_i,\mathbf{R}_i,\mathbf{t}_i\},\{\mathbf{X}_j\}} \sum_{(i,j)\in\mathcal{O}} \rho\left( \left\|\mathbf{u}_{ij} - \Pi_i(\mathbf{X}_j)\right\|_{\mathbf{\Sigma}_{ij}^{-1}}^2 \right)$$

各記号の意味は次の通りです。

• $\mathcal{O}$ は、どの camera $i$ がどの 3D point $j$ を観測しているかを表す集合です。
• $\mathbf{u}_{ij}$ は、image $i$ 上で観測された feature の 2D position です。
• $\Pi_i(\mathbf{X}_j)$ は、現在の camera parameter で $\mathbf{X}_j$ を image $i$ に再投影した position です。
• $\mathbf{\Sigma}_{ij}$ は、観測 noise の大きさや信頼度を表す covariance です。単純化する場合は単位行列として扱います。
• $\rho$ は robust loss です。誤対応や動的物体による外れ値の影響を抑えるために、Huber loss や Cauchy loss が使われます。

この objective では、見えていない点は和に入りません。つまり、すべての camera がすべての 3D point を観測している必要はありません。実際の SfM の observation graph は疎であり、この疎性が後段の Bundle Adjustment を効率化する重要な構造になります。

この式の気持ちは単純で、「すべての写真で、観測された点と再投影された点ができるだけ重なるようにしたい」ということです。ただし、実際の match には outlier があるため、単純な二乗誤差だけではなく robust loss を入れることが重要です。

二 view geometry による verification

Feature descriptor だけで matching すると、repetitive pattern や似た texture によって誤対応が多く入ります。そのため、SfM では RANSAC と epipolar geometry によって match を検証します。

Calibrated camera の normalized image coordinate を $\mathbf{x}_i = \mathbf{K}_i^{-1}\tilde{\mathbf{u}}_i$、$\mathbf{x}_j = \mathbf{K}_j^{-1}\tilde{\mathbf{u}}_j$ とします。二つの camera の relative pose が rotation $\mathbf{R}_{ji}$ と translation direction $\mathbf{t}_{ji}$ で表されるとき、対応点は essential matrix $\mathbf{E}_{ji}$ によって次の制約を満たします。

$$\mathbf{x}_j^\top \mathbf{E}_{ji} \mathbf{x}_i = 0, \qquad \mathbf{E}_{ji} = [\mathbf{t}_{ji}]_\times \mathbf{R}_{ji}$$

ここで、$[\mathbf{t}_{ji}]_\times$ は cross product を matrix として表す skew-symmetric matrix です。この式の気持ちは、「camera center、二つの image point に対応する ray、そして 3D point は同じ epipolar plane 上にある」ということです。式の値が 0 に近い match は幾何的に自然であり、大きく外れる match は outlier である可能性が高いです。

実装では、RANSAC で $\mathbf{E}$ または fundamental matrix $\mathbf{F}$ を推定し、その model に合う inlier match だけを残します。これにより、後段の pose estimation と triangulation が安定します。

Initial pair と cheirality check

Incremental SfM では、最初に信頼できる image pair から reconstruction を開始します。良い initial pair には、十分な number of inlier matches と、十分な baseline が必要です。Baseline が小さすぎると、triangulation による depth が不安定になります。

Essential matrix を分解すると、relative rotation と translation direction の候補が複数得られます。どの候補が正しいかは、triangulated point が両方の camera の前方に来るかどうかで選びます。この条件は cheirality condition と呼ばれます。

$$Z_i(\mathbf{X}_j) > 0, \qquad Z_k(\mathbf{X}_j) > 0$$

ここで、$Z_i(\mathbf{X}_j)$ は camera $i$ の coordinate で見たときの depth です。この式の気持ちは、「復元した点は camera の後ろではなく、実際に撮影された前方に存在してほしい」というものです。

Triangulation の位置づけ

Camera projection matrix を $\mathbf{P}_i = \mathbf{K}_i[\mathbf{R}_i \mid \mathbf{t}_i]$ とします。Image $i$ における homogeneous pixel coordinate を $\tilde{\mathbf{u}}_{ij}$ とすると、3D point $\mathbf{X}_j$ は理想的には次の式を満たします。

$$\tilde{\mathbf{u}}_{ij} \times (\mathbf{P}_i\tilde{\mathbf{X}}_j) = \mathbf{0}$$

$\times$ は cross product です。$\tilde{\mathbf{X}}_j$ は homogeneous coordinate の 3D point です。この式は、「投影された点 $\mathbf{P}_i\tilde{\mathbf{X}}_j$ と観測点 $\tilde{\mathbf{u}}_{ij}$ は、同じ画像上の方向を指してほしい」という意味です。

複数 view の式を積み重ねると、$\mathbf{A}\tilde{\mathbf{X}}_j = \mathbf{0}$ という linear system が得られます。実際には観測 noise があるため、完全には 0 になりません。そのため、最小二乗的に最も整合する $\tilde{\mathbf{X}}_j$ を求めます。これが linear triangulation の基本です。

ただし、triangulation は baseline と視線の交差角に強く依存します。視線の交差角が小さいと、画像上の小さな error が depth の大きな error に変換されます。Stereo geometry では、depth $Z$ と disparity $d$ の関係が $Z = fB/d$ であり、誤差伝播はおおよそ次のようになります。

$$\sigma_Z \approx \frac{Z^2}{fB}\sigma_d$$

ここで、$f$ は focal length、$B$ は baseline、$\sigma_d$ は disparity error、$\sigma_Z$ は depth error です。この式の気持ちは、「遠い点ほど、また baseline が短いほど、同じ pixel error でも depth が大きく揺れる」ということです。

Camera registration と PnP

既に sparse map がある状態で新しい image を追加する場合、新しい image 上の 2D feature と既存の 3D point を対応付け、Perspective-n-Point（PnP）によって camera pose を推定します。

$$\min_{\mathbf{R},\mathbf{t}} \sum_{j\in\mathcal{V}} \rho\left( \left\|\mathbf{u}_j - \pi\left(\mathbf{K}(\mathbf{R}\mathbf{X}_j + \mathbf{t})\right)\right\|^2 \right)$$

ここで、$\mathcal{V}$ は新しい image から見えている既存 3D point の集合です。この式の気持ちは、「新しい camera pose を仮定したときに、既存の 3D point が新しい image の feature 位置にきちんと重なるようにしたい」ということです。

実用上は、誤対応が混じるため、PnP solver と RANSAC を組み合わせます。RANSAC では、少数の対応から pose hypothesis を作り、それに合う inlier の数や再投影誤差を評価します。

Incremental SfM

Incremental SfM は、最初に信頼できる image pair から reconstruction を開始し、新しい image を一枚ずつ追加していく approach です。

1. 初期 image pair を選び、relative pose を推定します。
2. 対応点を triangulation して sparse map を作ります。
3. 既存 map に対して新しい image の pose を PnP で推定します。
4. 新しい point を triangulate します。
5. Bundle adjustment で camera pose と 3D point を最適化します。

Incremental SfM の強みは、各段階で局所的に検証しながら reconstruction を成長させられる点です。一方で、登録順序が悪い場合や、初期 pair が不安定な場合には、誤差が後段へ伝播します。そのため、view selection、triangulation angle、reprojection error、track length などの heuristic が重要になります。COLMAP は、この方向の代表的な実装です。

Global SfM との違い

Global SfM は、最初に image graph 全体から pairwise relative pose を推定し、それらをまとめて global camera pose に整合させます。Rotation averaging と translation averaging を使うことが多く、概念的には次のような問題になります。

$$\min_{\{\mathbf{R}_i\}} \sum_{(i,k)\in\mathcal{E}} \rho\left(d_R(\mathbf{R}_{ki}, \mathbf{R}_k\mathbf{R}_i^\top)^2\right)$$

ここで、$\mathcal{E}$ は image graph の edge、$\mathbf{R}_{ki}$ は image pair から推定された relative rotation、$d_R$ は rotation 間の距離です。この式の気持ちは、「pairwise に見た回転関係と、全体で割り当てた camera rotation がなるべく矛盾しないようにしたい」ということです。

Global SfM は大規模 data で効率的になることがありますが、pairwise relative pose の outlier に敏感です。Incremental SfM と Global SfM は、どちらが常に優れているというより、data の規模、overlap、outlier の量、必要な頑健性によって使い分けます。

Gauge freedom と scale ambiguity

単眼画像だけから SfM を行う場合、reconstruction の absolute scale は決まりません。たとえば、すべての camera translation と 3D point を同じ倍率で拡大しても、画像上の投影は変わりません。また、world coordinate の原点や向きも任意です。

この自由度は gauge freedom と呼ばれます。実装では、最初の camera pose を固定したり、一部の parameter に prior を入れたりして、最適化問題が不定にならないようにします。Metric scale が必要な場合は、known baseline、GPS / IMU、ground control point、既知サイズの object などを使って scale を決めます。

Bundle adjustment との関係

SfM の最終品質は、Bundle Adjustment（BA）に大きく依存します。BA は、camera pose、intrinsics、3D point をまとめて最適化し、reprojection error を最小化します。SfM の graph を見ると、camera と 3D point が node であり、feature observation がそれらを結ぶ edge です。

この graph 構造が sparse であるため、BA では Schur complement を使って効率的に解くことができます。詳しくは Bundle Adjustment を参照してください。

SfM の難所

SfM は、次のような場合に難しくなります。

• Texture が少ない scene
• Repetitive pattern が多い scene
• Motion blur や rolling shutter
• Lighting change
• Dynamic object
• Image overlap が少ない場合
• Wide baseline すぎる場合

これらは単なる経験則ではなく、数式上の制約が弱くなったり、誤った観測が objective に混ざったりすることとして理解できます。Textureless な領域では feature observation が少なくなります。Repetitive pattern では epipolar constraint を満たす outlier が残りやすくなります。Dynamic object は、同じ $\mathbf{X}_j$ が全 view で同じ位置にあるという静的 scene の仮定を破ります。

SfM と MVS

SfM は camera pose と sparse point cloud を復元します。Dense な surface を得るためには、その後に Multi-View Stereo を行うことが一般的です。MVS では、SfM で得た camera pose を固定または強い prior として使い、pixel 単位の depth や surface を推定します。

関連ページ

• Feature Matching
• Epipolar Geometry
• Triangulation, PnP, and ICP
• Bundle Adjustment
• Multi-View Stereo

主なソース

• COLMAP documentation: https://colmap.readthedocs.io/en/stable/
• Schönberger and Frahm, “Structure-from-Motion Revisited”, CVPR 2016: https://openaccess.thecvf.com/content_cvpr_2016/papers/Schonberger_Structure-From-Motion_Revisited_CVPR_2016_paper.pdf
• Snavely et al., “Photo Tourism”, SIGGRAPH 2006: https://phototour.cs.washington.edu/Photo_Tourism.pdf
• Hartley and Zisserman, “Multiple View Geometry in Computer Vision”: https://www.robots.ox.ac.uk/~vgg/hzbook/
• Szeliski, “Computer Vision: Algorithms and Applications”: https://szeliski.org/Book/