大規模 3D 重建的Power Bundle Adjustment

筆者個人理解

我們知道BA問題本質上是求解增量線性方程的方程，在BA中H矩陣有著其特殊的結構

其中B，C是對角塊矩陣，C的規模遠大于B，對角塊矩陣求逆的難度遠小于普通矩陣，故而我們可以將其簡化為

這樣第一行方程就變為與xp無關的項

求解出，代入到第二個方程，利用C矩陣易于求逆的性質，快速求解出。

很明顯，在整個過程中耗時最多的便是求解Schur 補消元后的第一個方程。在這篇論文中作者提出了利用冪級數的方法來加速求解第一個方程，下面可以和筆者一起來看一下具體的實現方式。

摘要

我們引入 Power Bundle Adjustment 作為一種擴展型算法，用于解決大規模BA問題。它基于逆 Schur 補的冪級數展開，構成了我們稱之為逆展開方法的新求解器家族。我們從理論上證明了冪級數的使用是正確的，并且證明了我們方法的收斂性。使用真實世界的 BAL 數據集，我們表明所提出的求解器挑戰了最先進的迭代方法，并顯著加快了法方程的求解速度，即使達到了非常高的精度。這個易于實施的求解器還可以補充最近提出的分布式BA框架。我們證明，使用建議的power BA作為子問題求解器可以顯著提高分布式優化的速度和準確性

1、介紹

BA （BA） 是一個經典的計算機視覺問題，它構成了許多 3D 重建和運動結構 （SfM） 算法的核心組成部分。它指的是通過最小化非線性重投影誤差來聯合估計相機參數和 3D 地標位置。最近出現的大規模互聯網照片集 ［1］ 提出了對在運行時和內存方面可擴展的 BA 方法的需求。為增強現實或自動駕駛等應用構建準確的城市比例地圖使當前的 BA 方法達到了極限

由于正規方程的求解是 BA 中最耗時的步驟，因此通常采用 Schur 補技巧來形成縮減相機系統（RCS）。這個線性系統只涉及位姿參數并且明顯更小。通過使用 QR 因式分解，僅導出 RCS 的矩陣平方根，然后求解代數等價問題 ［4］，可以進一步減小其大小。RCS 及其平方根公式通常通過迭代方法求解，例如針對大規模問題的流行預處理共軛梯度算法，或通過直接方法（例如針對小規模問題的 Cholesky 分解）求解

在下文中，我們將依靠逆 Schur 補的迭代逼近來挑戰這兩個求解器系列。特別是，我們的貢獻如下：

? 我們為高效的大規模 BA 引入了power BA （PoBA）。我們稱之為逆擴展方法的這一新技術系列挑戰了建立在迭代和直接求解器上的最先進的方法。

? 我們將boundle adjustment問題與冪級數理論聯系起來，我們提供了證明這種擴展合理的理論證明，并建立了求解器的收斂性。

? 我們對BAL 數據集上提出的方法進行了廣泛的評估，并與幾個最先進的求解器進行了比較。我們強調了 PoBA 在速度、準確性和內存消耗方面的優勢。圖 1 顯示了 97 個評估的 BAL 問題中的兩個的重建。

? 我們將我們的求解器合并到最近提出的分布式 BA 框架中，并在速度和準確性方面顯示出顯著的改進。

? 我們將求解器作為開源軟件發布，以促進進一步研究。

2、相關的工作

由于我們提出了一種求解大規模BA的新方法，我們將回顧BA和傳統求解方法，即直接法和迭代法的工作。我們還提供了一些關于冪系列的背景知識。關于級數擴展的一般介紹，我們請讀者參考［14］。

圖 1. Power Bundle Adjustment （PoBA） 是一種針對大規模 BA 問題的新型求解器，它比現有求解器速度快得多，內存效率更高。（a） 具有 1197 個姿勢的瓢蟲 BAL 問題的優化 3D 重建。PoBA-32（分別為 PoBA-64）比最佳競爭求解器快 41%（分別為 36%）以達到 1% 的成本容差。（b） 具有 1102 個姿勢的 Venice BAL 問題的優化 3D 重建。PoBA-32（分別為 PoBA-64）比最佳競爭求解器快 71%（分別為 69%）以達到 1% 的成本容忍度。PoBA 的內存消耗是√BA（resp. Ceres）的五倍（resp.兩倍）。

2.1可擴展的boundle adjustment

boundle adjustment的詳細調查可以在 ［16］ 中找到。Schur 補碼 ［20］ 是利用 BA 問題稀疏性的普遍方法。分辨率方法的選擇通常由正規方程的大小決定：隨著大小的增加，稀疏和密集 Cholesky 分解 ［15］ 等直接方法的性能優于不精確牛頓算法等迭代方法。具有數萬張圖像的大規模BA問題通常通過共軛梯度法 ［1， 2， 8］ 來解決。已經設計了一些變體，例如可以擴大搜索空間 ［17］ 或可以使用基于可見性的預調節器 ［9］。最近一系列關于平方根BA的工作建議用零空間投影 ［4、5］ 代替 Schur 補碼來消除地標。它導致顯著的性能改進，并在速度和準確性方面成為boundle adjustment問題的最佳性能求解器之一。盡管如此，這些方法仍然依賴于傳統的求解器來解決減少的相機系統問題，即用于大規模 ［4］ 的預處理共軛梯度法 （PCG） 和用于小規模 ［5］ 問題的 Cholesky 分解，此外還有一個重要的成本內存消耗術語。即使使用 PCG，求解正規方程仍然是瓶頸，找到數千個未知參數需要大量的內部迭代。其他作者試圖通過關注高效并行化 ［13］ 來提高 PCG BA 的運行時間。最近，隨機 BA ［22］ 被引入以將減少的相機系統隨機分解為子問題，并通過密集分解求解較小的正規方程。這導致了具有改進的速度和可擴展性的分布式優化框架。通過將一般冪級數理論封裝到線性求解器中，我們建議同時提高這些現有方法的速度、準確性和內存消耗。

2.2冪級數求解器。

雖然冪級數展開常用于求解微分方程 ［3］，但據我們所知，它從未用于求解BA問題。最近的一項工作 ［21］ 將 Schur 補碼與 Neumann 多項式展開聯系起來，以構建一個新的預條件器。盡管這種方法對某些物理問題（例如對流擴散或大氣方程）給出了有趣的結果，但它對于BA問題仍然不能令人滿意（見圖 2）。相反，我們建議直接應用逆 Schur 補的冪級數展開來解決 BA 問題。因此，我們的求解器屬于擴展方法的范疇——據我們所知——從未應用于 BA 問題。除了是一個易于實現的求解器之外，它還利用 BA 問題的特殊結構來同時提高現有方法的權衡速度精度和內存消耗

圖 2. 盡管 ［21］ 探討了使用冪級數作為某些物理問題的預條件子，但它受到 BA 公式的特殊結構的影響。給定預處理器 M -1 和 Schur 補碼 S，條件數 κ（M -1S） 與共軛梯度算法的收斂性相關聯。（a） 說明了 LM 算法針對實際問題 Ladybug-49 的第 10 次迭代的行為，其中具有來自 BAL 數據集的 49 個姿勢，并且對于用作 CG 算法預條件子的冪級數展開 （22） 的不同階數 m 。與流行的 Schur-Jacobi 預條件子相關的條件數通過這個冪級數預條件子減少了，這通過 CG 算法更好的收斂和更少的 CG 迭代次數 （b） 來說明。然而，由于冪級數預條件器的應用涉及 4m 矩陣向量乘積，因此每個補充階 m 在運行時方面的成本更高，而 Schur-Jacobi 預條件器可以有效地存儲和應用。（c） 導致求解正規方程 （6） 時的總運行時間增加。

3、冪級數

我們簡要介紹矩陣的冪級數展開。令 ρ（A） 表示方陣 A 的譜半徑，即最大絕對特征值，并用‖A‖ = ρ（A） 表示譜范數。以下命題成立

命題 1. 令 M 為 n × n 矩陣。若M的譜半徑滿足‖M‖《1，則

其中誤差矩陣

滿足

附錄給出了證明，圖5給出了實際問題的說明

4、power BA

我們考慮具有 np 個位姿和 nl 個地標的BA的一般形式。令 x = （xp， xl） 為包含所有優化變量的狀態向量，其中長度為 dp*np 的向量 xp 與所有姿勢的外部和（可能）內部相機參數相關聯，長度為 3*nl 的向量 xl 與所有地標的 3D 坐標。如果只有外部參數未知，則 dp = 6 用于每個攝像機的旋轉和平移。對于評估的 BAL 問題，我們另外估計內在參數和 dp = 9。目標是最小化總BA能量

其中向量 r（x） = ［r1（x）， 。..， rk（x）］ 包含捕獲模型和觀察之間差異的所有殘差。

4.1.最小二乘問題

這種非線性最小二乘問題通常使用 Levenberg-Marquardt （LM） 算法求解，該算法基于當前狀態估計值 x0 = （x0 p， x0 l ） 的一階泰勒近似 r（x）。通過添加正則化項來提高收斂性，最小化變成

其中

λ 是阻尼系數，Dp 和 Dc 是位姿和地標變量的對角阻尼矩陣。這個阻尼問題導致相應的正規方程

這里

Uλ、Vλ 和 H 是對稱正定的 ［16］

4.2.舒爾補

由于直接反演大小為（dpnp+3nl）2的系統矩陣H對于大規模問題往往代價過高，因此通常使用Schur補碼技巧進行約簡。其想法是形成約簡相機系統

同時

然后求解 （12） 的 Δxp。最優的 Δxl 是通過回代獲得的

4.3.power BA

用分塊矩陣 Uλ 對 （13） 進行因式分解

導致將逆 Schur 補表示為

為了將 （17） 展開為命題 1 中詳述的冪級數，我們需要將的光譜半徑限制為 1

通過利用 BA 問題的特殊結構，我們證明了一個更強大的結果：

引理 1. 令 μ 為的特征值。然后

證明： 一方面， 是對稱正半定的，因為 Uλ 和 Vλ 是對稱正定的。則其特征值大于 0。由于 與 》 相似，

另一方面， 與 S 和 Uλ 一樣是對稱正定的。因此，由于 的相似性，U ?1 λ S 的特征值都嚴格為正。作為

它遵循

證明結束。

假設

并且

對于 m ≥ 0。以下命題證實了近似值確實隨著 m 的遞增階數收斂：

命題2

證明。我們表示 P = 。由于引理 1

與 （6） 關聯的逆 Schur 補允許冪級數展開：

這里

滿足

由此得出

譜范數相對于矢量范數的一致性意味著：

從（24）、（27）和（29）我們得出證明

所以

該收斂結果證明：

? 將（22） 應用于（12） 的右側可以直接獲得Δxp 的近似值；

? 這種近似的質量取決于階數 m 并且可以根據需要盡可能小

圖 3. 所有 BAL 問題的性能概況顯示解決給定精度公差 τ ∈ {0.1， 0.01， 0.003， 0.001} 和相對運行時間 α 的問題的百分比。我們提出的求解器 PoBA 使用 Schur 補數的級數展開顯著優于所有競爭求解器，精度可達 τ = 0.003。

冪級數展開是迭代導出的，需要終止規則。

通過類比不精確的牛頓法 ［11， 12， 18］ 這樣共軛梯度算法我們設置了一個停止標準

對于給定的。該標準確保當通過將逆 Schur 補碼擴展為補充順序來更新位姿的細化時，冪級數擴展停止

達到同階時遠小于平均細化

圖 4. 所有 BAL 問題的內存消耗。所提出的 PoBA 求解器（橙色和藍色點）的內存消耗比 √BA 求解器少五倍

5、實現

我們直接在 ［4］ 的公開可用實現 1 上以單 （PoBA-32） 和雙 （PoBA-64） 浮點精度在 C++ 中實現我們的 PoBA 求解器。這個最近的求解器通過使用具有里程碑意義的雅可比行列式的 QR 因式分解，表現出出色的性能來解決boundle adjustment。它尤其與流行的 Ceres 求解器競爭。我們還添加了與 Ceres 的稀疏 Schur 補碼求解器的比較，類似于 ［4］。Ceres-explicit 和 Ceres-implicit 使用由 Schur-Jacobi 預調節器預處理的共軛梯度算法迭代求解 （12）。第一個將 S 作為塊稀疏矩陣保存在內存中，第二個在迭代期間即時計算 S。√BA 和 Ceres 提供了非常有競爭力的性能來解決boundle adjustment問題，這使得它們與 PoBA 相比非常具有挑戰性的基線。我們在 MacOS 11.2 上運行實驗，配備 Intel Core i5 和 4 個內核，頻率為 2GHz。

高效存儲

我們利用 BA 問題的特殊結構并設計了內存高效存儲。我們按地標對雅可比矩陣和殘差進行分組，并將它們存儲在單獨的密集內存塊中。對于具有 k 個觀察值的地標，所有與觀察到地標的姿勢相對應的大小為 2 × dp 的雅可比位姿塊被堆疊并存儲在大小為 2k × dp 的內存塊中。連同大小為 2k × 3 的地標雅可比塊和長度為 2k 的殘差也與地標相關聯，單個地標的所有信息都有效地存儲在大小為 2k × （dp + 4） 的內存塊中。此外，（15）和（23）中涉及的操作使用內存塊并行化。

圖 5. 兩個 BAL 問題的第一次 LM 迭代的命題 1 中的不等式 （3） 的圖示：（a） 具有 49 個姿勢的瓢蟲和 （b） 具有 193 個姿勢的特拉法加。當 m 《 20 時，誤差矩陣 R 的譜范數以綠色繪制。以藍色繪制的不等式右側表示誤差矩陣譜范數的理論上限，并且取決于所考慮的 m 和譜M 的范數 = U ?1 λ W V ?1 λ W 》。對于光譜庫 ［23］，ρ（M） 取值 （a） L-49 的 0.999858 和 （b） T-193 的 0.999879。兩個值都小于 1，并且 ρ（R） 始終小于 ρ（M ）m+1/（1 ? ρ（M ）），如引理 1 中所述。

性能概況

為了比較一組求解器，用戶可能對兩個因素感興趣，即運行時間更短和精度更高。性能配置文件 ［6］ 對兩者進行聯合評估。設 S 和 P 分別是一組求解器和一組問題。令 f0（p） 為初始目標，f （p， s） 為求解器 s ∈ S 在求解問題 p ∈ P 時達到的最終目標。S 中求解器針對問題 p 達到的最小目標是 f ?（p） = mins∈S f （p， s）。給定公差 τ ∈ （0， 1），問題 p 的目標閾值由下式給出

求解器達到這個閾值所需的運行時間被記錄為T√（p， s）。很明顯，對于給定問題p，最有效的求解器s*達到閾值時，運行時T運行時T會用（p， s*）=min 2 2 S T會用（p， s）。然后，相對運行時α的求解器的性能文件被定義為

在圖形上，給定求解器的性能概況是解決問題的百分比快于 x 軸上的相對運行時間 α

5.1.實驗設置

圖 6. 來自具有 1197 個姿勢的 BAL 數據集的 Ladybug-1197（左）和來自具有 1102 個姿勢的 BAL 數據集的 Venice-1102（右）的收斂圖。圖 1 顯示了針對這些問題的 3D 地標和相機姿勢的可視化。虛線對應于公差 τ ∈ {0.1， 0.01， 0.003， 0.001} 的成本閾值

圖 7. 使用隨機框架的所有 BAL 問題的性能概況。我們提出的求解器 PoST 在所有精度公差 τ ∈ {0.1， 0.01， 0.003} 方面都優于具有挑戰性的 STBA，無論是在速度還是精度方面，并且在 τ = 0.001 時與 STBA 相媲美

數據集

為了進行廣泛的評估，我們使用了BAL項目頁面上的所有97個boundle adjustment問題。它們被分成五個問題家族。瓢蟲是由以正常速度行駛的車輛拍攝的圖像組成的。威尼斯、特拉法爾加和杜布羅夫尼克的圖像來自Flickr.com，并被保存為骨骼集［1］。用額外的樹葉圖像重組這些問題導致了菲納爾家族。關于這些問題的詳細信息可以在附錄中找到

LM循環

PoBA 符合實施 ［4］ 和 Ceres。從阻尼參數 10?4 開始，我們根據 LM 循環的成功或失敗更新 λ。我們將 LM 迭代的最大次數設置為 50，如果達到 10?6 的相對函數公差，則提前終止。關于（23）和（32），我們將最大內部迭代次數設置為 20，閾值 = 0.01。Ceres 和√BA 對內部 CG 循環使用相同的強制序列，其中最大迭代次數設置為 500。

5.2.分析

圖 3 顯示了具有公差 τ ∈ {0.1， 0.01， 0.003， 0.001} 的所有 BAL 數據集的性能概況。對于 τ = 0.1 和 τ = 0.01，PoBA-64 在運行時間和準確性方面明顯優于所有挑戰者。在高相對時間 α = 4 之前，PoBA-64 顯然仍然是出色精度 τ = 0.003 的最佳求解器。對于更高的相對時間，它與 √BA ? 32 具有競爭力，并且仍然優于所有其他挑戰者。從兩個不同大小的 BAL 問題的收斂圖中可以得出相同的結論（見圖 6）。圖 4 突出顯示了 PoBA 相對于所有 BAL 問題的挑戰者的低內存消耗。無論問題的大小如何，PoBA 的內存消耗都比√BA 和 Ceres 少得多。值得注意的是，它需要的內存比√BA 少近五倍，比 Ceres-implicit 和 Ceres-explicit 少幾乎兩倍的內存

5.3.power 隨機BA （PoST）

隨機BA。

STBA 將簡化的相機系統分解為 Levenberg-Marquardt 迭代內的集群。由于相機集群內部的密集連接，每個集群的線性子問題然后與密集 LL》 分解并行解決。如 ［22］ 所示，這種方法在運行時和擴展到非常大的 BA 問題方面優于基線，它甚至可以用于分布式優化。在下文中，我們展示了用我們的 Power Bundle Adjustment 替換子問題求解器可以進一步顯著提高運行時間

power 隨機BA （PoST）

我們通過結合我們的求解器而不是密集的 LL》 分解來擴展 STBA2。然后使用與第 5.1 節中相同的參數對逆 Schur 補碼進行冪級數展開來求解每個子問題。根據 ［22］，我們將最大簇大小設置為 100，并在 C++ 中用 double 編寫實現

分析

圖 7 顯示了針對不同公差 τ 的所有 BAL 問題的性能配置文件。對于 τ = 0.001，兩種求解器都具有相似的精度。對于 τ ∈ {0.1， 0.01， 0.003}，PoST 在運行時間和準確性方面明顯優于 STBA，尤其是 τ = 0.01。當我們繪制不同大小的 BAL 問題的收斂曲線時，會進行相同的觀察（見圖 8）

六，結論

我們引入了一類新的大規模BA求解器，它利用逆 Schur 補碼的冪展開。我們證明了所提出的近似的理論有效性和該求解器的收斂性。此外，我們通過實驗證實，所提出的逆 Schur 補數的冪級數表示在速度、準確性和內存消耗方面優于競爭迭代求解器。最后但同樣重要的是，我們證明了冪級數表示可以補充分布式BA方法，以顯著提高其在大規模 3D 重建中的性能。

審核編輯 ：李倩