目次 — 知りたいところから読む
前提と読み方

前提知識 ベクトル・行列とカメラ投影の基礎。

入門 · 原理・構成・判断のための解説です。

Structure from MotionやVisual-SLAMが三角測量やPnPで求めるカメラ姿勢と3D点は、あくまで線形近似や逐次処理から得た粗い初期値にすぎない。画像1枚ごとのノイズ、対応点の量子化誤差、逐次推定の伝播誤差が積み重なり、そのままでは全体として矛盾のある復元になっている。バンドル調整（Bundle Adjustment、BA）は、すべてのカメラパラメータとすべての3D点を同時に動かし、全観測点の再投影誤差の総和を最小化することで、この矛盾を解消する最終仕上げの最適化である。名前の「バンドル（束）」は、各3D点から各カメラへ伸びる光線の束を、観測位置に一致するよう同時に調整することに由来する。

0. 30秒要約

  • バンドル調整は、カメラの内部・外部パラメータと3D点座標を未知数とし、全観測の再投影誤差の二乗和を最小化する非線形最小二乗問題である。
  • Gauss-Newton法やLevenberg-Marquardt（LM）法で反復的に解く。LMは、収束が不安定なGauss-Newtonと、遅いが安定な最急降下法の間をパラメータ \lambda で滑らかに補間する。
  • 1台のカメラは自分が見た点としか結びつかないため、ヤコビアンとヘッセ近似はカメラ×点のブロック構造を持つ疎行列になる。この疎性が大規模化を可能にする鍵である。
  • Schur補行列トリックは、3D点のブロックが互いに独立（ブロック対角）であることを利用し、点を先に消去してカメラだけの小さな「reduced camera system」を解く。これにより数万点・数千カメラ規模の問題が現実的な時間で解ける。
  • バンドル調整はSLAMのPose Graph最適化と親戚関係にあるが、未知数に3D点そのものを含む点が異なる。SfMの最終仕上げ、SLAMの局所/大域最適化の両方で使われる共通基盤技術である。

1. 何を入力し、何を求めるのか

入力は、SfMやVisual-SLAMの途中結果として得られる、次の3つの初期推定である。

  • カメラ姿勢の初期値 \{K_i, R_i, \mathbf{t}_i\}（i=1,\dots,m、多くは内部パラメータ K_i は既知または固定）
  • 3D点の初期値 \{\mathbf{X}_j\}（j=1,\dots,n、三角測量から得られる粗い座標）
  • どのカメラがどの点を観測したかという対応関係、すなわち各観測に対応する画像座標 \mathbf{u}_{ij}（カメラ i が点 j を見た画素位置）

出力は、これらすべてを同時に微調整した、全観測に対してより整合的なカメラ姿勢と3D点である。バンドル調整はゼロから解を作る手法ではなく、既に「だいたい合っている」初期値を局所的に磨き上げる仕上げの最適化だという点が、後述する収束性の議論で効いてくる。

2. コスト関数：再投影誤差

ある3D点 \mathbf{X}_j をカメラ i に投影した位置と、実際に観測された画像座標 \mathbf{u}_{ij} とのズレを再投影誤差と呼ぶ。カメラ i の姿勢を R_i, \mathbf{t}_i、投影関数を \pi(\cdot)（同次座標を画素座標へ変換する非線形写像）とすると、1本の観測に対する残差は

r_{ij} = \pi\big(K_i(R_i\mathbf{X}_j + \mathbf{t}_i)\big) - \mathbf{u}_{ij}

で書ける。バンドル調整は、観測されたペアの集合 \mathcal{O}=\{(i,j)\} すべてについて、この残差の二乗和を最小化する。

\min_{\{K_i,R_i,\mathbf{t}_i,\mathbf{X}_j\}}\sum_{(i,j)\in\mathcal{O}}\rho\left(\|r_{ij}\|^2\right)

\rho はHuber損失などのロバスト損失関数で、誤対応による大きな外れ値1本が最適化全体を歪めるのを防ぐ。この式自体はSfM入門で既に見た形と同じであり、バンドル調整はこの最小化問題を実際にどう解くかという計算上の核心を扱う。

3. 非線形最小二乗として解く：Gauss-NewtonからLevenberg-Marquardtへ

未知数全体を1本のベクトル \mathbf{x}（全カメラ姿勢と全3D点を並べたもの）にまとめ、残差全体を \mathbf{r}(\mathbf{x}) と書くと、最小化対象は \|\mathbf{r}(\mathbf{x})\|^2 である。\mathbf{r} は非線形なので、現在の推定値 \mathbf{x}_k の周りで1次のテイラー展開 \mathbf{r}(\mathbf{x}_k+\Delta\mathbf{x})\approx \mathbf{r}(\mathbf{x}_k)+J\Delta\mathbf{x} を使う。J=\partial \mathbf{r}/\partial \mathbf{x} はヤコビアンである。これを代入して \Delta\mathbf{x} について解くと、Gauss-Newton法の正規方程式

(J^\mathsf{T}J)\,\Delta\mathbf{x} = -J^\mathsf{T}\mathbf{r}

が得られる。H=J^\mathsf{T}J はヘッセ行列の近似（Gauss-Newton近似、2次項を無視）である。この式で \Delta\mathbf{x} を求め \mathbf{x}_{k+1}=\mathbf{x}_k+\Delta\mathbf{x} と更新する操作を、残差が収束するまで繰り返す。

Gauss-Newton法は初期値が解に近いとき高速に収束するが、初期値が悪いと発散しやすい。Levenberg（1944年）とMarquardt（1963年）が独立に提案したLevenberg-Marquardt（LM）法は、正規方程式に減衰項を加えることでこれを緩和する。

(J^\mathsf{T}J + \lambda D)\,\Delta\mathbf{x} = -J^\mathsf{T}\mathbf{r}

D は通常 J^\mathsf{T}J の対角成分（またはそれに準じるスケーリング行列）、\lambda は減衰係数である。\lambda が小さいときはGauss-Newton法に近く速く収束し、\lambda が大きいときは最急降下法に近い小さく安全なステップになる。反復ごとにコストが減れば \lambda を小さくして加速し、コストが増えてしまえば \lambda を大きくしてステップを縮め棄却する、という適応制御によって、Gauss-Newtonの速さと最急降下法の安定性の橋渡しをする。バンドル調整のほぼすべての実務実装（後述のCeres Solver、g2o、SBAなど）は、このLM法か近縁の信頼領域法を採用している。

4. なぜヤコビアンは疎になるのか

バンドル調整の未知数は、カメラ姿勢6自由度（回転3＋並進3、内部パラメータを固定する場合）× m 台と、3D点3自由度 × n 点であり、合計 6m+3n 次元にもなる。観測数が数万を超える実SfM問題では、この J^\mathsf{T}J を素朴に密行列として扱うと O((6m+3n)^3) の計算量になり、現実的な時間では解けない。

ここで効くのが、再投影誤差 r_{ij} が「カメラ i のパラメータと点 j のパラメータにしか依存しない」という構造である。カメラ k\neq i や点 l\neq j に関する偏微分は恒等的にゼロになる。

\frac{\partial r_{ij}}{\partial \mathbf{x}_{\text{camera }k}} = 0 \ (k\neq i), \qquad \frac{\partial r_{ij}}{\partial \mathbf{X}_l} = 0 \ (l\neq j)

つまり1本の観測が生むヤコビアンの行は、対応するカメラのブロックと点のブロックにしか非ゼロ値を持たない。観測数に比例して行が増えるだけで、各行の非ゼロ要素数は一定（カメラ6＋点3、内部パラメータを含めればもう少し多い程度）にとどまる。この疎性が、J^\mathsf{T}J を見ると次のブロック構造として表れる。

J^\mathsf{T}J = \begin{pmatrix} B & E \\ E^\mathsf{T} & C \end{pmatrix}
  • B：カメラパラメータ同士の相互作用。カメラ i とカメラ k が共通の点を観測しない限りゼロなので、疎なブロック構造を持つ。
  • C：3D点パラメータ同士の相互作用。ある点 j の3自由度は他の点とは一切結びつかないため、ブロック対角行列になる。これが次節のSchur補行列トリックの前提になる。
  • E：カメラと点の相互作用（観測 (i,j) ごとに非ゼロブロックが立つ）。

5. 基本パイプライン

図1 · ボタンで表示を切り替え
Camera姿勢と3D点から再投影残差と疎Jacobianを作り、Schur補行列とLM更新を反復して全変数を共同調整するBundle Adjustment
図2 · ボタンで表示を切り替え
r_{ij} を計算 疎ヤコビアンカメラ×点のブロック構造 Schur補行列で点を消去しreduced camera system LM法で\lambda を調整し\Delta\mathbf{x} を更新 収束判定→ 再修正

反復のたびに再投影誤差を計算し直し、疎ヤコビアンを組み立て、Schur補行列でカメラだけの縮約系を解き、LM法のステップ制御で更新する。これをコストの変化が閾値を下回るまで、あるいは最大反復回数に達するまで繰り返す。

6. Schur補行列トリック：疎性を計算量削減に変える

前節のブロック構造を使い、正規方程式 (J^\mathsf{T}J+\lambda D)\Delta\mathbf{x}=-J^\mathsf{T}\mathbf{r} を、カメラの更新量 \Delta\mathbf{c} と点の更新量 \Delta\mathbf{p} に分けて書くと

\begin{pmatrix} B' & E \\ E^\mathsf{T} & C' \end{pmatrix} \begin{pmatrix} \Delta\mathbf{c} \\ \Delta\mathbf{p} \end{pmatrix} = \begin{pmatrix} v \\ w \end{pmatrix}

となる（B', C' は減衰項を加えた後のブロック）。C' は3D点ごとに独立なブロック対角行列なので、各3×3ブロックを個別に逆行列計算でき、コストはほぼ点数 n に比例する。この C'^{-1} を使って \Delta\mathbf{p} を消去すると、カメラのみに関する縮約系（reduced camera system）

\left(B' - E C'^{-1}E^\mathsf{T}\right)\Delta\mathbf{c} = v - E C'^{-1}w

が残る。左辺の B'-EC'^{-1}E^\mathsf{T} をSchur補行列と呼ぶ。この行列のサイズは 6m\times 6m（カメラ数のみに依存し、点数 n に依存しない）であり、\Delta\mathbf{c} を解いた後は

\Delta\mathbf{p} = C'^{-1}\left(w - E^\mathsf{T}\Delta\mathbf{c}\right)

で各点の更新量を安価に復元できる。典型的なSfMでは点数 n がカメラ数 m の何十倍にもなるため、6m+3n 次元の連立方程式を素朴に解く代わりに、6m 次元のSchur補行列だけを扱えばよくなる。これがバンドル調整を数万点規模でも実用的に解けるものにしている核心のアイデアであり、Triggsらの"Bundle Adjustment — A Modern Synthesis"（2000年）が理論的に整理し、Ceres Solverやg2oなど現行ライブラリの標準的な内部実装になっている。

Ceres Solverは、この縮約系の解き方だけでも複数の選択肢を用意している。密行列として解くDENSE_SCHUR（カメラ数が数百程度まで）、疎性を生かした並べ替えで解くSPARSE_SCHUR（カメラ数が数千規模）、共役勾配法をSchur補行列に適用するITERATIVE_SCHUR（さらに大規模な問題向け）である。問題の規模に応じてこれらを使い分けるのが実務上の勘所になる。

7. ゲージ自由度：解が一意に決まらない方向

バンドル調整には、コスト関数の値を変えずにパラメータ全体を動かせる自由度が残っている。全カメラと全3D点を同じ回転・並進・スケールで一斉に動かしても、再投影誤差はまったく変化しない（単眼のみの場合、絶対スケールも同様に不定である）。この自由度をゲージ自由度（gauge freedom）と呼ぶ。ゲージ自由度を放置すると J^\mathsf{T}J が特異（ランク落ち）になり、正規方程式が解けない、あるいは数値的に不安定になる。

実務上は、最初の2台のカメラの姿勢や1本の基線長を固定する、あるいはLM法の減衰項 \lambda D 自体がこの特異方向を暗黙に正則化する、といった対策で回避する。GPSやIMUなど絶対スケール・絶対姿勢の情報が使える場合は、それらを追加の拘束としてゲージを固定するのが自然である。

8. Pose Graph最適化との違い

Loop Closure入門で扱ったPose Graph最適化も、\mathrm{Log}写像を使った残差をロバスト損失で最小化する非線形最小二乗という点でバンドル調整と同じ数学的枠組みに属する。違いは未知数の中身にある。

観点 バンドル調整 Pose Graph最適化
未知数 全カメラ姿勢＋全3D点座標 全カメラ（ノード）姿勢のみ
残差 3D点の再投影誤差（画像空間） 相対姿勢観測との差（SE(3)空間）
疎性の由来 どのカメラがどの点を見たか どのノード同士が拘束で結ばれているか
計算コスト 点数が多いと高いが、Schur補行列で抑制 ノード数（キーフレーム数）に応じて元々小さめ
主な用途 SfMの最終仕上げ、局所/全体地図の精密化 SLAMの大域ドリフト補正（ループ閉合後）

実際のVisual-SLAMシステムでは、フレームごとに3D点を含む局所バンドル調整（local BA）でキーフレーム周辺を精密化し、ループ閉合が検出されたときは3D点を陽に持たない軽量なPose Graph最適化で大域的な軌跡を素早く補正する、という役割分担がよく使われる。3D点まで含めた全体バンドル調整（global BA）はより正確だが計算コストが高く、リアルタイム性が求められる場面では頻繁には回せない。

9. 代表的な実装

  • Ceres Solver：Googleが開発する汎用非線形最小二乗ライブラリで、2010年から実運用されている。Schur系ソルバーを内蔵し、COLMAPをはじめ多くのSfM/SLAM実装のバンドル調整バックエンドとして使われる。
  • g2o：Kümmerleらが2011年のICRAで発表したグラフ最適化フレームワークで、SLAMのPose Graph最適化とバンドル調整の両方を同じ枠組みで扱える。ORB-SLAM系のバックエンドとして広く使われてきた。
  • SBA（Sparse Bundle Adjustment）：LourakisとArgyrosが2009年のACM Transactions on Mathematical Softwareで発表した、疎バンドル調整に特化した初期の公開実装。Schur補行列トリックを明示的に実装した代表例として参照されることが多い。
  • COLMAP内蔵BA：Ceres Solverを内部で利用し、Incremental SfMの各ステップで局所・全体バンドル調整を自動的に使い分ける。

10. 苦手な条件・失敗しやすいケース

  • 初期値が悪い場合：バンドル調整は局所最適化であり、初期値が真の解から大きく外れていると、誤った局所解に収束するか、そもそも発散する。三角測量やPnPで得た初期値の質が最終精度を左右する。
  • 観測数が少ない、または視差が小さい点：ごく少数の画像からしか観測されない点や、視差の乏しい点は、その点に関するヤコビアンが劣条件になりやすく、深度方向にだけ大きな誤差が残ることがある。
  • 外れ値マッチが多い場合：誤対応が多く混入すると、ロバスト損失を使っても完全には吸収しきれず、周辺の正しい点まで引きずられて歪む。
  • 超大規模問題：観測数が数百万を超える都市規模の再構成では、Schur補行列があっても計算・メモリコストが無視できなくなり、問題を分割して並列化する、あるいは近似的な手法（Levenberg-Marquardtの信頼領域を粗くする等）を組み合わせる工夫が必要になる。
  • ゲージ自由度の未処理：前述の通り、固定を忘れると数値的に不安定になり、収束しない、または非物理的な解に迷い込む。

11. 実用上の選び方

  • SfMの最終段階として密な精度が欲しい場合は、Incremental/Globalどちらの戦略でも、最後に必ず全体バンドル調整を通すのが定石である。COLMAPなど既存実装のデフォルト設定に従えば、まず大きく外すことはない。
  • リアルタイムSLAMでは、毎フレームの全体バンドル調整は計算コストが高すぎる。直近のキーフレーム集合だけを対象にした局所バンドル調整と、ループ閉合時のみ発火するPose Graph最適化を組み合わせる設計が現実的である。
  • 自前でパイプラインを組む場合、まずCeres Solverかg2oのようなライブラリに乗せるのが妥当である。Schur補行列の実装をゼロから書くのは、正しさの検証コストに対して得られる学習効果が薄い。
  • 大規模・都市規模の再構成では、単一のバンドル調整に頼らず、問題を地域ごとに分割し、階層的に統合する手法（後述するMulti-View Stereoへつなげる前段としてもよく行われる）を検討する。

12. まとめ

バンドル調整は、再投影誤差を全カメラ・全3D点にわたって同時に最小化する非線形最小二乗問題であり、Levenberg-Marquardt法で反復的に解く。カメラと点の観測関係が疎であることを利用したSchur補行列トリックが、この最適化を数万点規模でも現実的な時間で解けるものにしている。Pose Graph最適化と数学的な枠組みは共有しつつ、3D点を陽に持つかどうかで使い分けが決まり、SfMとSLAM双方の精度を最終的に支える共通基盤技術になっている。

理解を確かめる
再投影誤差が小さければ絶対スケールも正しい？

単眼の再投影だけでは全体のスケールを決められない。ゲージ自由度の固定と、実寸を与える観測を区別する。

参考資料

現在の項目 · 13 / 19 · コンピュータビジョン入門

次に読む

前提を確認するStructure from Motion入門 — バラバラな写真群から3次元と撮影位置を同時に復元するシリーズの次の内容へ進むMulti-View Stereo入門 — 疎な点群を密な3D形状へ埋める同じ分野を別の観点から読む画像の明るさ・輝度 Lab — 露出、ガンマ、クリッピングを比較
#Bundle Adjustment #バンドル調整 #非線形最小二乗 #Levenberg-Marquardt #Schur補行列 #Structure from Motion