BA簡介
BA疊代步長的數學推導
稀疏BA疊代步長的算法求解過程
1.BA簡介
錄影機在靜态環境中移動，得到不同時刻拍攝的多幅圖像。假設這些圖像是同一剛性物體的投影，則可由圖像特征對應關系估計出錄影機的運動參數。在計算機視覺中 ，這一過程稱為運動分析或由運動重建物體結構(structure frommotion)。
Bundle Adjustment即光束平差法，作為SFM這種多視重建視覺算法的最後一步，它利用LM算法使得觀測的圖像點坐标與預測的圖像點坐标之間的誤差最小。若給定圖像特征點的對應關系及初始三維點，BA可以同時精化這些特征點對應的3D坐标及相應的相機參數。
Bundle Adjustment的名字由來于空間中每個物點和相機光學中心“發射”出的光束，人們可以根據這些光束對結構和視角參數進行調節，獲得空間結構及視角參數的最優解。
2.BA疊代步長的數學推導
以下推導來自對希臘人論文的翻譯：”The Design andImplementation of a Generic Sparse Bundle Adjustment Software Package Based onthe Levenberg-Marquardt Algorithm”
假設空間中有n個三維物點，現在圍繞這些物點拍攝了m張照片，則第j張圖檔上看到的第i個物點為xij。Bundle adjustment旨在優化初始多個相機與結構的參數估計，以便于找到合理的參數使得我們能夠精确計算出m張照片中n個物點的空間坐标。更具體的說，每個相機j用向量aj表示(内參和外參)，每個三維物點i用向量bi表示。為了簡化問題，假設現在所有的圖檔中能看到所有物點(不看到也沒關系，後邊的矩陣相應位置為0呗)。BA的核心問題就是最小化下面的重投影誤差函數(非線性)：
函數Q(aj,bi)表示物點bi在相機aj下的投影坐标，也是我們的預測值。函數d(x,y)表示觀測的圖像坐标與預測的圖像坐标之間的歐氏距離。
現在我們用向量P代表m個投影矩陣和n個三維物點所有參數：
J是關于投影關系f的雅各比矩陣，是疊代步長，使得我們擷取合理的P讓殘差函數最小(阻尼因子的處理見後文)。上述方程同之前LM算法那篇文章裡的疊代公式幾乎一樣(因為此處的協方差矩陣是機關矩陣)。此外由于各個照片與三維物點之間的參數沒有交集，我們發現上述公式其實是非常稀疏的。簡便期間，我們舉個簡單的例子：
假設現在有m=3張照片拍攝了n=4個物點，即觀測坐标X與參數幾何P分别為：
由于各個照片與三維物點之間的參數沒有交集，比如對于不屬于目前相機的二維圖像坐标的偏導數為0，對于不屬于目前三維物點投影的二維圖像坐标的偏導數為0
那麼對于投影函數關系X’=f(P)，它的偏導數集合，也就是雅可比矩陣J可以寫成：
觀測矩陣X的協方差矩陣是對角塊結構的：
将協方差矩陣和雅可比矩陣代入LM的疊代方程，方程的左邊将是如下形式：
若定義：
則LM疊代公式的左側可以寫成：
LM疊代公式的右邊為：
完整的LM疊代公式如下：
再次簡化，如果定義：
那麼疊代方程可以進一步簡化成：
将U*,W,V*代入(1)，那麼(1)的左邊為：
反過來倒過去的定義，隻是為了公式更清晰的展示，發現規律：我們發現對于任意數量的n物點和m照片均可以求解 LM的疊代步長。如果點k沒有在照片l中出現，那麼Akl=0并且Bkl=0.接下來我們介紹下基于LM的稀疏BA的疊代步長的算法流程。
3.稀疏BA疊代步長的算法求解過程
算法輸入：
m個初始相機參數aj，j=1,…,m；n個初始三維物點坐标bi，i=1,…,n，觀測的特征點坐标xij(第j張圖第i個點)，LM算法的阻尼因子μ
算法輸出：
基于LM的稀疏BA的疊代步長的解
算法流程：
計算偏導數矩陣，Q表示投影函數，i=1,…,n，j=1,…,m
将Uj和Vi的主對角線元素上加上阻尼因子μ，我們得到Uj*和Vi
計算Yij=WijVi*-1
按照(1)(2)式計算LM疊代步長：
現在有了疊代步長，我們把疊代步長的計算步驟嵌入标準的LM算法流程使得重投影殘差最小。至于阻尼因子是否要用信頼域的方法，随便吧，已經夠麻煩的了，反正代碼用現成的接口opencv和openmvg都有。
下面是我的想法：
BA的目标是幫我們求得相機參數和三維坐标，每次LM疊代修改的都是參數集合P(由相機内外參數和三維點坐标組成)，而觀測向量X每次都是恒定的。這裡初始參數P0作用和LM博文中函數拟合的初始參數一樣。
而初始參數P0是怎麼擷取的呢？
當空間物體結構參數未知時，SFM問題可以分為兩類：單目視覺下的二維特征對應和多目視覺下的三維特征對應。
采用二維特征對應關系估計相對運動需要給定先驗的空間尺度資訊, 這為單目視覺裡程計的實作帶來一定的不便(就是拿個相機對着某個物體不同角度拍N張照片，計算的3D點都是假的)。如果相機已經标定，可以利用各個照片上特征點的對應關系，并在極幾何性質幫助下，求出相機的外部參數R是真的，T隻是方向，反推的3D點也是up-to-scale的。咱就利用這些東西作為初始P0.
三維特征對應關系下求解運動估計問題的一般方法為: 首先采用雙目或多目錄影機三維重建得到空間物體的三維資料; 然後由二維圖像特征對應關系建立空間物體的三維特征對應, 進而進行三維運動問題求解. 三維資料的資訊量遠高于二維圖像, 是以三維運動估計問題的求解大為簡化. 但是, 由于立體視覺中三維重建過程對像素誤差有放大作用, 三維運動估計的結果對圖像點誤差非常敏感, 需要采取一定的措施對三維重建結果進行優化以提高運動估計精度。我認為雙目測距由于baseline已知，咱可以根據disparity恢複出真正的3D坐标。然後各個相機之間的RT，同樣利用之前的極幾何性質，可以求出來。然後把相機參數和3D坐标作為初始值P0.
另外，BA所使用的每張圖檔的二維特征點和圖檔像素比起來是稀疏的，是以最終還原的三維空間也是稀疏的，隻能看個大概。