Bundle Adjustment到底是什麼？

12-28

Adjustment computation最早是由geodesy的人搞出來的。19世紀中期的時候，geodetics的學者就開始研究large scale triangulations了。20世紀中期，隨著camera和computer的出現，photogrammetry也開始研究adjustment computation，所以他們給起了個名字叫bundle adjustment，bundle的意思我不知道中文怎麼解釋好，大家意會吧。20世紀下半段，computer vision community開始興起reconstruction，也開始研究bundle adjustment，一開始重複造輪子，後來triggs的modern synthesis及時出現。21世紀前後，robotics領域開始興起SLAM，最早用的recursive bayesian filter，後來把問題搞成個graph然後用least squares方法解。

這些東西歸根結底就是Gauss大神「發明」的least squares method。當年天文學家Piazzi整天閑得沒事看星星，在1801年1月1號早上發現了一個從來沒觀測到的星星，再接下來的42天里做了19次觀測之後這個星星就消失了。當時的天文學家為了確定這玩意到底是什麼絞盡了腦汁，這時候Gauss出現了，（最初）只用了3個觀察數據，就用least squares算出了這個小行星的軌道，接下來天文學家根據Gauss的預測，也重新發現了這個小行星（雖然有小小的偏差），並將其命名為Ceres，也就是穀神星。Google的ceres-solver就是根據這個來命名的。
ref: How Gauss Determined the Orbit of Ceres

關於究竟是誰發明了Least Squares歷史上有爭論，Legendre是最早publish這個方法的（1805），但是幾年後（1809）Gauss跳出來說：「你太naive了，我1795年就開始用least squares了，微不足道」。雖然有人認為Gauss這樣的大神沒必要說謊來和Legendre這種小叼絲（相對，長了一副反派臉）搶成果，但是至今沒有definitive的證據證明確實是Gauss最早發明Least Squares。有人認為least squares的方法對Gauss來說太簡單以至於Gauss根本沒覺得有必要把它publish出來（hehe）。

Gauss

Legendre

ref: Gauss and the Invention of Least Squares

我們再來看看19，20世紀連電腦都沒有的情況下，geodesy的人們面對的是什麼樣的問題吧。1927年的North American Datum有25000個觀測塔，1983年的NAD有270000個觀測塔。再來看看robotics community，最大的real-world SLAM datasets有21,000個pose[Johannsson13]，最大的simulation datasets有200,000個pose[Grisetti10]。看看時間，都是2010年以後的。拿NAD83來說，雖然1983年已經有電腦了，但是優化這樣一個network，需要解1,800,000個equations。也就是說如果如果用Least Squares的話，每一步的normal equation J^T * J * x = J^T y 或者Ax = b，裡面這個A的dimension是900,000 x 900,000。用dense method光是存這麼一個matrix就要3000 Gb[Agarwal14]。

Bundle adjustment優化的是sum of reprojection error，這是一個geometric distance（為什麼要minimize geometric distance可以參考[Hartley00]），問題可以formulate成一個least squares problem，如果nosie是gaussian的話，那就是一個maximum likelihood estimator，是這種情況下所能得到的最優解了。

這個reprojection error的公式是非線性的，所以這個least squares problem得用iterative method來求解。最簡單的是Newton，但是要算Hessian，並不是很好算，所以pass。接下來是Gauss-Newton，用J^T J 來近似Hessian，但是convergence速度不給力，也pass。再下來是Levenberg-Marquardt，是一個damping method，改一個lambda來控制到底是偏向steepest descent還是偏向Gauss-Newton，如果算出來更渣的一步就不接受，改個lambda重算，這樣一來做了很多無用功，所以也pass。再下來還有Powell"s dogleg，是一個trust region method，在這個小區間內搞一個新的function來近objective function，不論好壞都走一步，但是步幅不會超過所謂的trust region，再根據表現調整這個region，總的來說在large scale問題上比Levenberg-Marquardt的表現要好。再往後問題再大就得用前面所說的演算法的sparse版本，再大下去得換conjugate gradient方法，這塊我就不怎麼了解了。

不論GN,LM,DL，中間都要解一個Ax=b形式的linear system，一般情況下演算法的效率就取決於解這個linear system的效率。所以說到底這些nonlinear least squares problem最後也就是解一個linear system。這個linear system你可以直接inverse，也可以用QR，或者Choleskey，或者Schur complement trick來解，愛誰誰。說到這個Choleskey decomposition，當初就是為了Geodetic mapping而發明的。

現實中，並不是所有observation都服從i.i.d. gaussian noise的（或者可以說幾乎沒有），遇到有outlier的情況，這些方法非常容易掛掉，這時候就得用到robust statistics裡面的robust cost (*cost也可以叫做loss, 統計學那邊喜歡叫risk) function了，比較常用的有huber, cauchy等等。

總的來說bundle adjustment這個東西搞了這麼多年也搞得差不多了，不能說state-of-the-art，但是可以算是gold standard。大點的問題諸如earth-scale reconstruction也被google的人搞過了，用了2 billion張谷歌街景，reconstruct了整個地球，真不知道接下來還能reconstruct什麼。

[Triggs00] Bundle Adjustment - A Modern Synthesis, Bill Triggs, et al.
[Hartley00] Multiple View Geometry in Computer Vision, Richard Hartley, Andrew Zisserman
[Johannsson13] H. Johannsson, M. Kaess, M. Fallon, and J. J. Leonard, 「Temporally scalable visual slam using a reduced pose graph,」 in Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), 2013, pp. 54–61.
[Grisetti10] G. Grisetti, R. Kummerle, C. Stachniss, and W. Burgard, 「A tutorial on graph-based SLAM,」 IEEE Transactions on Intelligent Transportation Systems Magazine, vol. 2, pp. 32–43, 2010.
[Agarwal14] A Survey of Geodetic Approaches to Mapping and the Relationship to Graph-based SLAM

機器人導航中，2D的特徵reproject回三維域內，和真正的3D點的位置會有偏差。但是在物理意義上，3D點和投射到攝像機的2D特徵點是同一個點。所以這個誤差出現在計算3D點時攝像機自身旋轉矩陣和位移向量上。
Bundle Adjustment的作用是，通過least square等演算法，去最小化這個偏差，以此得到機器人移動和方向的精確值。這在物理意義上是最精確的，是Visual SLAM問題的state-of-art解決方法。

關於這個演算法的原理和用途上面@立黨講得很清楚，我說一說怎麼解。其實least square problem一般都是用Gauss-Newton 法或者LM演算法迭代求解。bundle adjustment本質也是lm演算法。由於是特定的形式，所以可以化成sparse matrix 的形式，這樣計算量大大減小了。
Sparse Bundle Adjustment in C/C++

靜下心來讀一篇文章，比在知乎提問其實高效得多。
推薦一篇入門級經典文章，visual odometry part 2。裡面有對bundleadjustment和graph optimization的論述。
如果還覺得不過癮可以看看文章里引用的關於ba的文章以及multiple view geometry第十七章N視圖計算方法。

在攝影測量里就是整體平差的意思，就是將誤差「平均」分配到每個觀測值上，以避免誤差累積導致後面的結果比前面的差很多。

Bundle Adjustment簡述

個人感覺寫的挺清楚，適合初學者。

光束法平差

我不知道「光速平差法」這種翻譯是從哪裡傳過來的，如果真正讀了《Bundle Adjustment — A Modern Synthesis》這篇文章的人，當然也具有一些專業知識，應該不會這樣翻譯的。

裡面涉及的內容，主要在於優化，強調「同時」確定圖像點所反應的物體的3D信息、相機位置和內外參數信息。就好像一個方程組，同時優化左邊的參數，以及右邊的結果，讓它們同時達到「和諧」。

所以我覺得還是用類似「捆綁」的詞語比較合適一些。

graph structure non-linear least square solution, Lm演算法求解。見g2o和google ceres 文檔。

我是攝影測量專業，不管怎麼說，你的解釋讓我眼前亮了一下：）
歷史的原因，平差始於大地測量技術，測量中最基礎的就是三角測量（空間交會），大地測量或攝影測量都基於此，觀測數據上規模，有冗餘的情況下，必然牽扯平差，提高測量結果的精度和可靠度。