Abstract
We propose the Generalized Subgraph Preconditioners (GSP) to solve large-scale bundle adjustment problems efficiently. In contrast with previous work using either direct or iterative methods alone, GSP combines their advantages and is significantly faster on large datasets. Similar to [12], the main idea is to identify a sub-problem (subgraph) that can be solved efficiently by direct methods and use its solution to build a preconditioner for the conjugate gradient method. The difference is that GSP is more general and leads to more effective preconditioners. When applied to the βbalβ datasets [2], our method shows promising results.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Agarwal, S., Snavely, N., Simon, I., Seitz, S., Szeliski, R.: Building rome in a day. In: IEEE 12th International Conference on Computer Vision, pp. 72β79 (2009)
Agarwal, S., Snavely, N., Seitz, S.M., Szeliski, R.: Bundle Adjustment in the Large. In: Daniilidis, K., Maragos, P., Paragios, N. (eds.) ECCV 2010. LNCS, vol.Β 6312, pp. 29β42. Springer, Heidelberg (2010)
Alon, N., Karp, R., Peleg, D., West, D.: A graph-theoretic game and its application to the k-server problem. SIAM Journal on ComputingΒ 24(1), 78β100 (1995)
BjΓΆrck, A.: Numerical Methods for Least Squares Problems. SIAM Publications (1996)
Boman, E., Chen, D., Parekh, O., Toledo, S.: On factor width and symmetric h-matrices. Linear Algebra and its ApplicationsΒ 405, 239β248 (2005)
Boman, E., Hendrickson, B.: Support theory for preconditioning. SIAM Journal on Matrix Analysis and ApplicationsΒ 25(3), 694β717 (2003)
ByrΓΆd, M., Γ strΓΆm, K.: Bundle adjustment using conjugate gradients with multiscale preconditioning. In: British Machine Vision Conference (2009)
ByrΓΆd, M., Γ strΓΆm, K.: Conjugate Gradient Bundle Adjustment. In: Daniilidis, K., Maragos, P., Paragios, N. (eds.) ECCV 2010. LNCS, vol.Β 6312, pp. 114β127. Springer, Heidelberg (2010)
Chen, Y., Davis, T., Hager, W., Rajamanickam, S.: Algorithm 887: CHOLMOD, supernodal sparse Cholesky factorization and update/downdate. ACM Transactions on Mathematical SoftwareΒ 35(3), 1β14 (2009)
Davis, T.: Algorithm 915, SuiteSparseQR: multifrontal multithreaded rank-revealing sparse QR factorization. ACM Transactions on Mathematical SoftwareΒ 38(1) (2011)
Dellaert, F., Kaess, M.: Square root sam: Simultaneous localization and mapping via square root information smoothing. International Journal of Robotics ResearchΒ 25(12), 1181β1203 (2006)
Dellaert, F., Carlson, J., Ila, V., Ni, K., Thorpe, C.E.: Subgraph-preconditioned conjugate gradient for large scale slam. In: IEEE/RSJ International Conference on Intelligent Robots and Systems (2010)
Frahm, J.-M., Fite-Georgel, P., Gallup, D., Johnson, T., Raguram, R., Wu, C., Jen, Y.-H., Dunn, E., Clipp, B., Lazebnik, S., Pollefeys, M.: Building Rome on a Cloudless Day. In: Daniilidis, K., Maragos, P., Paragios, N. (eds.) ECCV 2010. LNCS, vol.Β 6314, pp. 368β381. Springer, Heidelberg (2010)
Jeong, Y., Nister, D., Steedly, D., Szeliski, R., Kweon, I.: Pushing the envelope of modern methods for bundle adjustment. In: IEEE Conference on Computer Vision and Pattern Recognition, pp. 1474β1481 (2010)
Jian, Y.D., Balcan, D.C., Dellaert, F.: Generalized subgraph preconditioners for large-scale bundle adjustment. In: IEEE 13th International Conference on Computer Vision (2011)
Konolige, K., Garage, W.: Sparse sparse bundle adjustment. In: Proc. of the British Machine Vision Conference (2010)
Lourakis, M., Argyros, A.: SBA: A software package for generic sparse bundle adjustment. ACM Transactions on Mathematical SoftwareΒ 36(1), 1β30 (2009)
MacKay, D.: Information theory, inference, and learning algorithms. Cambridge Univ. Press (2003)
Ni, K., Steedly, D., Dellaert, F.: Out-of-core bundle adjustment for large-scale 3D reconstruction. In: IEEE 11th International Conference on Computer Vision (2007)
Olson, E., Leonard, J., Teller, S.: Fast iterative alignment of pose graphs with poor initial estimates. In: Proceedings of IEEE International Conference on Robotics and Automation, pp. 2262β2269 (2006)
Saad, Y.: Iterative methods for sparse linear systems. Society for Industrial Mathematics (2003)
Snavely, N., Seitz, S.M., Szeliski, R.S.: Skeletal graphs for efficient structure from motion. In: IEEE Conference on Computer Vision and Pattern Recognition (2008)
Snavely, N., Seitz, S., Szeliski, R.: Modeling the world from internet photo collections. International Journal of Computer VisionΒ 80(2), 189β210 (2008)
Spielman, D.A.: Algorithms, graph theory, and linear equations. In: International Congress of Mathematicians (2010)
Trefethen, L., Bau, D.: Numerical linear algebra, vol.Β 50. Society for Industrial Mathematics (1997)
Triggs, B., McLauchlan, P.F., Hartley, R.I., Fitzgibbon, A.W.: Bundle Adjustment β A Modern Synthesis. In: Triggs, B., Zisserman, A., Szeliski, R. (eds.) ICCV-WS 1999. LNCS, vol.Β 1883, pp. 298β372. Springer, Heidelberg (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
Β© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Jian, YD., Balcan, D.C., Dellaert, F. (2012). Generalized Subgraph Preconditioners for Large-Scale Bundle Adjustment. In: Dellaert, F., Frahm, JM., Pollefeys, M., Leal-TaixΓ©, L., Rosenhahn, B. (eds) Outdoor and Large-Scale Real-World Scene Analysis. Lecture Notes in Computer Science, vol 7474. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-34091-8_6
Download citation
DOI: https://doi.org/10.1007/978-3-642-34091-8_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-34090-1
Online ISBN: 978-3-642-34091-8
eBook Packages: Computer ScienceComputer Science (R0)