冪級数展開近似を活用した大規模BA（Bundle Adjustment）の最新動向と手法

本発表では、大規模Bundle Adjustment(BA)を効率化する2つの手法を紹介します。
Power Bundle Adjustment(PoBA) [CVPR 2023 ] は、Schur補完の逆行列を冪級数展開で近似する新しいinverse expansion方式であり、高精度を維持しつつ高速化を実現します。
一方、Power Variable Projection(PoVar) [ECCV 2024 ]は、初期値不要なVariable Projectionにリーマン多様体最適化を導入し、大規模BAでも安定した収束を達成します。

Transcript

1. Spatial AI勉強会 11/27/2024 株式会社エクサウィザーズ ⾦⽥綾乃
2. Power Bundle Adjustment for Large-Scale 3D Reconstruction (CVPR 2023) Power Variable Projection for Initialization- Free Large-Scale Bundle Adjustment (ECCV 2024) Todayʼs topic: Bundle adjustment
3. Power Bundle Adjustment for Large-Scale 3D Reconstruction (PoBA) Simon Weber, Nikolaus Demmel, Tin Chon Chan, Daniel Cremers 逆⾏列計算を避けべき級数の有限項で近似することで効率化したBA CVPR 2023 Power Variable Projection for Initialization-Free Large-Scale Bundle Adjustment (PoVar / Ri PoBA) Simon Weber, Je Hyeong Hong, Daniel Cremers べき級数展開とリーマン多様体最適化を活⽤した初期化不要な⼤規模BA ECCV 2024 Todayʼs topic: Bundle adjustment
4. Bundle Adjustment ? 𝒙𝒑 ∶ カメラパラメタ 𝒙𝒍 ∶ ランドマーク テイラー展開の⼀次までの項 𝐽# ∶ カメラパラメタに対するJacobian 𝐽$ ∶ ランドマークに対する Jacobian 𝐷# ∶ カメラパラに関する damping mat 𝐷$ ∶ ランドマークに関する damping mat 正則化 𝐹 𝒙 = 1 2 𝑟 𝒙 ! ! = 1 2 ' 𝑟" 𝒙 ! ! 𝒙 = (𝒙# , 𝒙𝒍 ) 𝒓 𝒙 ≈ 𝒓% 𝒙 + 𝑱𝒑 ∆𝒙𝒑 + 𝑱𝒍 ∆𝒙𝒍 min ∆𝒙𝒑,∆𝒙𝒍 1 2 𝒓, + 𝑱𝒑 𝑱𝒍 ∆𝒙/ ∆𝒙0 1 1 + 𝜆 𝑫/ 𝑫0 ∆𝒙/ ∆𝒙0 1 1
5. Bundle Adjustment Normal equation Hessian SPD カメラパラメタのみに依存 SPD ランドマークのみに依存 Schur Complement Back substitution Reduced system 𝑼2 𝑾 𝑾3 𝑽2 ∆𝒙/ ∆𝒙0 = − 𝒃/ 𝒃0 min ∆𝒙𝒑,∆𝒙𝒍 1 2 𝒓, + 𝑱𝒑 𝑱𝒍 ∆𝒙/ ∆𝒙0 1 1 + 𝜆 𝑫/ 𝑫0 ∆𝒙/ ∆𝒙0 1 1 𝑺 ∆𝒙/ = −5 𝒃 ∆𝒙0 = −𝐕2 4𝟏(−𝒃0 + 𝑾3∆𝒙/ ) 𝒃𝝀 = 𝑱# '𝒓% , 𝒃$ = 𝑱$ '𝒓% 𝑼𝝀 = 𝑱# '𝑱# + 𝜆 𝑫# '𝑫# 𝑽𝝀 = 𝑱𝒍 '𝑱$ + 𝜆 𝑫$ '𝑫$ 𝑾 = 𝑱# '𝑱$ 𝑺 = 𝑼( − 𝑾𝑽( )*𝑾' ? 𝒃 = 𝒃( − 𝑾𝑽( )*𝒃$ ＊計算の軽量化の⼯夫
6. Schur Complementの変換について • システムがブロック⾏列の形で表現できること。 • Dが正則（可逆）であること Schur Complement Jacobian Hessian 𝑴 = 𝑨 𝑩 𝑪 𝑫 𝑺 = 𝑨 − 𝑩𝑫!"𝑪 ⼤規模な連⽴⼀次⽅程式や最適化問題を効率的に解くのに有効 ブロック⾏列の⼀部を消去して (eliminate) ⼩さめの次元のシステムに帰着 𝑼2 𝑾 𝑾3 𝑽2 ∆𝒙/ ∆𝒙0 = − 𝒃/ 𝒃0 SPD 今回の⾏列 𝑺 = 𝑼( − 𝑾𝑽( )*𝑾' ? 𝒃 = 𝒃( − 𝑾𝑽( )*𝒃$ 𝑺 ∆𝒙# = −+ 𝒃
7. What is new? Normal equation Hessian Schur Complement Back substitution Reduced system 𝑼2 𝑾 𝑾3 𝑽2 ∆𝒙/ ∆𝒙0 = − 𝒃/ 𝒃0 min ∆𝒙𝒑,∆𝒙𝒍 1 2 𝒓, + 𝑱𝒑 𝑱𝒍 ∆𝒙/ ∆𝒙0 1 1 + 𝜆 𝑫/ 𝑫0 ∆𝒙/ ∆𝒙0 1 1 𝑺 ∆𝒙/ = −5 𝒃 ∆𝒙0 = −𝐕2 4𝟏(−𝒃0 + 𝑾3∆𝒙/ ) Reduced systemでも計算量が⼤きい 冪級数展開近似の導⼊ 𝑺 = 𝑼( − 𝑾𝑽( )*𝑾' ? 𝒃 = 𝒃( − 𝑾𝑽( )*𝒃$
8. 冪級数展開近似 解きたい問題 Mが正⽅⾏列かつ を満たすとき 命題 収束半径 𝑴 𝑀の収束半径が1以下である場合、上記の命題を適⽤可能 m は任意の数であることに注意 →ちゃんと真値に収束するの︖
9. 収束性についての確認 解きたい問題 命題が論⽂中で⽰されている これよりの代わりに 𝑺!𝟏の代わりに 冪級数での近似をかけるだけで計算可能 どうやって打ち切り定数 𝒎 を決めるのか︖ 停止条件 冪級数の第 m 項までを⽤いて計算した近似解 現在の近似解 𝑥(𝑚) と前回の近似解 𝑥(𝑚 − 1) の差が、 現在の近似解の⼤きさに⽐べて⼗分に⼩さい
10. データセットと設定 • BALデータセット︓ • 全97の問題を含み、カメラ数が数⼗から数千、観測数が数万から数百万に及ぶ。 • 問題の種類︓Ladybug、Venice、Trafalgar、Dubrovnik、Finalの5つ • ソルバーの⽐較対象︓ • PoBA-32/64︓提案⼿法のシングル/ダブル精度版 • √BA-32/64︓最新の平⽅根バンドル調整法 • Ceres Solver（ceres-explicit/implicit）︓⼀般的な最適化ライブラリ • 評価基準︓ • 計算時間︓各問題を解くのに要した総時間。 • 精度︓最終的な⽬的関数値および、指定のトレランス τ に対する達成度。 • メモリ使⽤量︓各ソルバーが問題を解く際に消費したメモリの量。
11. 既存⼿法 Shur Jacobi との⽐較 - Shur Jacobi は、理論的には条件数を下げられるが、⼤規模・疎⾏列・⾮線形最適化を含む BA 問題に適⽤すると、前 処理作成・適⽤の計算コストが⼤きくなりすぎる. - Shur Jacobiは、より⾼次の多項式を使うと計算コストの⾯で悪化. - PoBAでは、前処理ではなくシュア補完の逆⾏列そのものを直接冪級数展開して右辺に適⽤ Shur Jacobi︓冪級数展開を⼤規模問題の前処理として使う [Q. Zheng et al. 2021] Q. Zheng et al. 2021. A power Schur complement low-rank correction preconditioner for general sparse linear systems. *Condition numberは⼩さいほど反復法の収束が早い
12. パフォーマンスプロファイルによる評価 横軸︓相対的な実⾏時間 𝑎（最速のソルバーの時間を1とした⽐率） 縦軸︓指定の τ 以下で問題を解決した割合 (精度) τ = 0.1, 0.01 では PoBA-64 が他⼿法を 上回る速度と精度 τ = 0.003 でもほぼ全域で PoBA-64 が優 勢 (⾼精度でも早い) τ = 0.001 のように⾼精度では √BA-32 と拮抗するが、全体的には PoBA- 32/64 が優位
13. メモリ使⽤量の⽐較 メモリ使⽤量が⼤幅に少ない √BAの約5分の1 Ceres Solverの約半分 問題サイズが⼤きいほど、この差は顕著
14. 個別の問題での⽐較 : 収束性について カメラ台数 PoBA-32 / PoBA-64 が短時間・少反復で⾼精度に到達する.
15. STBA（Stochastic Bundle Adjustment）との統合 STBA : BA問題をクラスターに分割して並列処理する⼿法 PoST : PoBAをSTBAのサブプロブレムソルバーとして統合 time (s) time (s) •PoBAの⼿法は既存の分散型BAフレームワークに統合可能 •PoSTにより⼤規模BA問題のさらなる⾼速化が実現
16. まとめ Power Bundle Adjustment for Large-Scale 3D Reconstruction (PoBA) ⽬的︓通常のバンドル調整（BA）問題を、⼤規模なスケールで効率的に解く 誤差関数: 通常のBA問題の標準的な射影誤差関数 シュル補⾏列の逆⾏列を冪級数展開で近似することで、計算効率を向上させる Power Variable Projection for Initialization-Free Large- Scale Bundle Adjustment (PoVar / RiPoVar) ⽬的︓初期化が不要な状態から、⼤規模なバンドル調整問題を解く 誤差関数: 可分な⾮線形最適化問題を射影カメラモデルで解く 変数射影法 (VarPro) にパワー級数展開を適⽤ この展開をリーマン多様体最適化に結び付ける
17. まとめ Power Bundle Adjustment for Large-Scale 3D Reconstruction (PoBA) ⽬的︓通常のバンドル調整（BA）問題を、⼤規模なスケールで効率的に解く 誤差関数: 通常のBA問題の標準的な射影誤差関数 シュル補⾏列の逆⾏列を冪級数展開で近似することで、計算効率を向上させる Power Variable Projection for Initialization-Free Large- Scale Bundle Adjustment (PoVar / RiPoVar) ⽬的︓初期化が不要な状態から、⼤規模なバンドル調整問題を解く 誤差関数: 可分な⾮線形最適化問題を射影カメラモデルで解く 変数射影法 (VarPro) にパワー級数展開を適⽤ この展開をリーマン多様体最適化に結び付ける
18. Power Variable Projection for Initialization-Free Large-Scale Bundle Adjustment の流れ 1. 分離可能な⾮線形最適化を⽤いた初期解の取得 カメラパラメタ と3Dランドマークパラメタ を初期値なしの状態から推定 冪急数展開近似を⽤いた逆⾏列計算の効率化 2.リーマン多様体最適化を⽤いた解の精密化 第⼀段階で得られた初期解を精密化 カメラパラメタとランドマークパラメタが同次座標上にあるのでリーマン多様体最適化 3.メトリックアップグレード（ユークリッド解への変換） 得られたパラメータを実際のカメラのSE(3)（3次元の回転と並進）パラメータに変換するための補正を⾏う 制約を満たすようなラグランジュ⽅程式をリーマン多様体最適化を⾏う PoVar RiPoBA 1本⽬の論⽂と同様に逆⾏列の計算回避
19. Step 1 :分離可能な⾮線形最適化を⽤いた初期解の取得 Initialization free [pOSE より] C. Zach et al. 2018, pOSE: Pseudo Object Space Error for Initialization-Free Bundle Adjustment モデル空間での最適化 アフィン空間での最適化 Nonlinear separatable problem 線形パラメータ（ランドマークパラメタ）と ⾮線形パラメータ（カメラパラメタ）に分離 線形パラメータ（ランドマークパラメタ）と ⾮線形パラメータ（カメラパラメタ）に分離
20. 変数射影（Variable Projection) を⽤いた変数消去 固定された𝑥# に対して𝑥$ を最適化する 擬似逆⾏列 を𝑥# の関数として 代⼊ * 𝐺 は 𝑥$ に対する線形演算⼦ 𝑥# のみの関数
21. 先ほどと同様に逆⾏列の計算回避 Normal LM VarPro Damping 項が含まれない Semi SPD Schur Complement Schur Complement Mが正⽅⾏列 かつ を満たすとき Power series expansion 𝑴 (𝑆&)'( = 𝐼 − '( 𝑴 Power series expansion PoBA(1本⽬の論⽂) PoVar(今回の論⽂) 𝑼% 𝑾 𝑾& 𝑽' ∆𝒙# ∆𝒙( = − 𝒃# 𝒃( 𝑼% 𝑾 𝑾& 𝑽% ∆𝒙# ∆𝒙( = − 𝒃# 𝒃( 𝑺 = 𝑼2 − 𝑾𝑽2 4G𝑾3 𝑺𝑽 = 𝑼2 − 𝑾𝑽H 4G𝑾3 𝑺 ∆𝒙/ = 𝒃2 − 𝑾𝑽2 4G𝒃0 𝑺𝑽 ∆𝒙/ = 𝒃2 − 𝑾𝑽, 4G𝒃0 冪級数近似
22. Step2 :リーマン多様体最適化を⽤いた解の精密化 接空間(Tangent Space) 同次座標系 :カメラの数 : ランドマークの数 基底 Schur Complement 局所的なスケールの⾃由度を制限したい 4 次元空間の単位球⾯ 𝑆+上に存在 12次元空間の単位球⾯ 𝑆**上に存在 iterative
23. Step3:メトリックアップグレード（ユークリッド解への変換） プロジェクティブカメラ⾏列と3Dランドマークを、実際の物理的なスケールや形状を持つユークリッド空間上 のカメラパラメータと3Dポイントに変換する射影変換⾏列Hを求める 各カメラについて変換後のカメラ⾏列が物理的な制約を満たす スケールの不定性を考慮するための 各カメラに対するスケール定数 Provar で 𝒂𝒊 の消去 𝑯 を⽤いて変換 ラグランジュ関数 (明記なしなので間違ってるかも) 16 次元空間の単位球⾯ 𝑆*-上に存在 リーマン多様体最適化
24. パフォーマンスプロファイルによる評価 : 第⼀段階のprojective カメラモデルでのBA 低精度 (τ が⼤きい) では PoVar と PoBA がほぼ拮抗しつつ⾼速 ⾼精度 (τ をさらに⼩さくする) では PoVar が PoBA を上回るケースが多く、また他の⼿法よりも効率よく収束 横軸︓相対的な実⾏時間 𝑎 （最速のソルバーの時間を1とした⽐率） 縦軸︓指定の τ 以下で問題を解決した割合（精度）
25. コスト推移について : 第⼀段階のprojective カメラモデルでのBA このグレーの破 線が⽬標コスト (許容誤差) τ = 0.01, 0.003, 0.001 PoVar は序盤から安定的にコストを下げる。PoBA は⾼精度な領域に⼊る前に⼀時的に収束が遅くなる場合もある🤔。 iterative (PCG) 系は計算時間が⻑く、direct factorization は⼤規模になるほど計算負荷が⾼い。
26. パフォーマンスプロファイルによる評価 横軸︓相対的な実⾏時間 𝑎 （最速のソルバーの時間を1とした⽐率） 縦軸︓指定のτ 以下で問題を解決した割合 : 第⼀段階のprojective カメラモデルでのBA + 第⼆段階のリーマン多様体最適化を⽤いた解の精密化 PoVar + RiPoBA が最も⾼い曲線を描き、全体的に最速かつ最終的な精度も⾼い。 RiPoBA ではなく RiPCG を使う組み合わせ(PoVar + RiPCG) は、特に⾼精度領域で劣る direct factorization は⼤規模になるほど遅い
27. PoVar + RiPoBA を使うと、他⼿法より速く、より低いコストまで到達している。 特に Venice-1672（右図: カメラ台数が多い）のような⼤きい問題で, RiPoBA (⻘とオレン ジ) が収束が早い。 コスト推移について :第⼆段階のリーマン多様体最適化を⽤いた解の精密化 このグレーの破 線が⽬標コスト (許容誤差) τ = 0.01, 0.003, 0.001 カメラ台数
28. まとめ Power Bundle Adjustment for Large-Scale 3D Reconstruction (PoBA) ⽬的︓通常のバンドル調整（BA）問題を、⼤規模なスケールで効率的に解く 誤差関数: 通常のBA問題の標準的な射影誤差関数 シュル補⾏列の逆⾏列を冪級数展開で近似することで、計算効率を向上させる Power Variable Projection for Initialization-Free Large- Scale Bundle Adjustment (PoVar / RiPoVar) ⽬的︓初期化が不要な状態から、⼤規模なバンドル調整問題を解く 誤差関数: 可分な⾮線形最適化問題を射影カメラモデルで解く 変数射影法 (VarPro) にパワー級数展開を適⽤ この展開をリーマン多様体最適化に結び付ける