三维重建：SFM中BA的并行化
?????? SFM，運動中結構重建。SFM是一種離線重建方法，SFM未得到原始數據中的幀間關系，因此在前期處理與SLAM有所不同。SLAM方法依據視覺里程算法，構建狀態數據序列即圖結構，僅需要解決累計誤差問題。而SFM需要使用匹配和優化方法，重建數據的圖結構，需要優化方法，SFM過程比SLAM過程更加復雜。
??????? BA：光束平差法，利用非線性最小二乘法求取相機位姿，三維點坐標。Bundle adjustment is almost always used as the last step of every feature-based 3D reconstruction algorithm. It amounts to an optimization problem on the 3D structure and viewing parameters (i.e., camera pose and possibly intrinsic calibration and radial distortion), to obtain a reconstruction which is optimal under certain assumptions regarding the noise pertaining to the observed[1] image features：在僅給定相機內部矩陣的條件下，對四周物體進行高精度重建。Bundle Adjustment的優化目標依舊是最小化重復投影誤差。作為三維重建的最后一步，可以處理數據丟失情況并提供真正的最大似然估計。
?????????????? 重投影誤差平差
?????????????? 圖片：https://www.cnblogs.com/Jessica-jie/p/7739775.html
?????? BA的由來：光束平差法由Bundle Adjustment譯得，即對所有光束進行平差。有兩層釋義：1.對場景中任意三維點P，由從每個視圖所對應的的攝像機的光心發射出來并經過圖像中P對應的像素后的光線，都將交于P這一點，對于所有三維點，則形成相當多的光束（bundle）；2. 實際過程中由于噪聲等存在，每條光線幾乎不可能匯聚與一點，因此在求解過程中，需要不斷對待求信息進行調整（adjustment），來使得最終光線能交于點P。對n幀，含k個特征點的目標函數如下：
??????
- k為三維空間點個數；
- n為成像平面個數；
- mij表示第i個三維點在第j$ 個成像平面對應的特征點坐標；
- vij表示點 i 在成像平面 j 上是否有投影，如果有 vij=1，否則vij=0;
- Pi表示每個成像平面對應的外參數向量；
- Mi表示每個三維點的坐標向量；
- Q(aj,bi)是重投影函數，將三維點 Mi映射到成像平面；
- d(x,y)為距離度量函數，一般為歐式距離函數。
?????? 這是一個非凸問題。以上便是光束平差法目標函數的原理。由于場景中特征點往往較多，該問題是一個巨大的高維非線性優化問題。接下來，需要對上述式子進行求解，這是光束平差法的核心內容。
??????? BA解法：通用優化方法。一階方法，即對問題的目標函數進行泰勒一階展開后進行迭代求解的方法。對雅克比矩陣使用梯度下降法是一階方法之一。二階優化方法，即會將目標函數展開至泰勒二階項然后進行優化求解，有牛頓法、LM方法、LBFGS方法等。LM方法易于實現，且效果較好，應用廣泛。
?????? 詳細公式推理和優化推導過程（一個或者兩個相機）：機器人視覺-光束法平差。wiki：https://en.wikipedia.org/wiki/Bundle_adjustment。Bundle Adjust優化方法-LM方法的Code：https://blog.csdn.net/micro_msdn/article/details/78584484。
??
0.SLAM中的BA
? ? ? ? SLAM中的BA服務于重建。光束平差法定義性的闡述應用于相機和共同觀測點的優化，在SLAM中，不同的位姿觀察到不完全重復的點集，形成一個大的稀疏圖。BA中的SLAM方法涉及了位姿的變化，對位姿和地圖點進行同時優化。
?????? 在SLAM過程中方程與三維重建中BA定義過程有所區別，對每一幀進行計算觀測誤差，對所有幀進行共同優化，公式為：
???????????????
??? ?? 對m幀，每一幀有N個觀測點的共同最小二，求這個最優解。
?
1. BA在重建中的作用
???????? 借鑒于運動中重建的方法，BA引入SLAM過程，而傳統的濾波方法引入BA是跟隨閉環檢測出現，假設每一次BA過程即形成一個閉環。
1.1 BA在濾波方法中的嵌入
?????????? PTAM分離了跟蹤和建圖過程，使其并行完成，只進行數據交互。引入關鍵幀的機制，構建稀疏性，使用BA獨立線程優化局部地圖和全局地圖，因此可以達到實時性，突破了傳統濾波算法的地圖規模限制。
?
1.2 BA在閉環檢測之后的應用
?????????? 在三維重建檢測到閉環之后，則可以根據匹配結果，計算出總誤差，并把誤差平均到閉環之內的每一選定幀。
?
2. BA的并行化
????????? 借鑒于運動中重建，把所有的誤差平均到每一個選定的關鍵幀里，對于幀數較多時，可以使用數據并行化。
????????? 數據并行化是方法并行化的必要條件，多幀數據進行平差的方法天然可適合并行處理。
?
Project Code: http://grail.cs.washington.edu/projects/mcba/
?
并行BA：Multicore Bundle Adjustment
?????? In this project, we consider the design and implementation of new inexact Newton type Bundle Adjustment algorithms that exploit hardware parallelism for efficiently solving large scale 3D scene reconstruction problems
????????? 即是 BA in the Large
????????? Recent work in Structure from Motion has demonstrated the possibility ofreconstructing geometry from large-scale community photo collections. Bundle adjustment, the joint non-linear refinement of camera and point parameters, is a key component of most SfM systems, and one which can consume a significant amount of time for large problems. As the number of photos in such collections continues to grow into the hundreds of thousands or even millions, the scalability of bundle adjustment algorithms has become a critical issue.
????????? In this project, we consider the design and implementation ofa new Inexact Newton type bundle adjustment algorithm, which usessubstantially less time and memory than standard Schur complementbased methods, without compromising on the quality of the solution. Weexplore the use of the Conjugate Gradients algorithm for calculatingthe Newton step and its performance as a function of some simple andcomputationally efficient preconditioners. We also show that the use of the Schur complementis not limited to factorization-based methods, how it can be used as part of the Conjugate Gradients (CG) method without incurring the computational cost of actually calculating and storing it in memory, and how this use is equivalent to the choice of a particular preconditioner.
?
Paper
??? Bundle Adjustment in the Large
??? Sameer Agarwal, Noah Snavely, Steven M. Seitz and Richard Szeliski
?
創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎總結
以上是生活随笔為你收集整理的三维重建：SFM中BA的并行化的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 公对公转账流程
- 下一篇： 三维重建：闭环检测-相机闭环