Article

Bundle adjustment in the large

Authors:

Sameer Agarwal,

Steven M. Seitz,

Richard SzeliskiAuthors Info & Claims

ECCV'10: Proceedings of the 11th European conference on Computer vision: Part II

Pages 29 - 42

Published: 05 September 2010 Publication History

Abstract

We present the design and implementation of a new inexact Newton type algorithm for solving large-scale bundle adjustment problems with tens of thousands of images. We explore the use of Conjugate Gradients for calculating the Newton step and its performance as a function of some simple and computationally efficient preconditioners. We show that the common Schur complement trick is not limited to factorization-based methods and that it can be interpreted as a form of preconditioning. Using photos from a street-side dataset and several community photo collections, we generate a variety of bundle adjustment problems and use them to evaluate the performance of six different bundle adjustment algorithms. Our experiments show that truncated Newton methods, when paired with relatively simple preconditioners, offer state of the art performance for large-scale bundle adjustment. The code, test problems and detailed performance data are available at http://grail.cs.washington.edu/projects/bal.

References

[1]

Snavely, N., Seitz, S.M., Szeliski, R.: Skeletal graphs for efficient structure from motion. In: CVPR, pp. 1-8 (2008)

[2]

Li, X., Wu, C., Zach, C., Lazebnik, S., Frahm, J.: Modeling and recognition of landmark image collections using iconic scene graphs. In: Forsyth, D., Torr, P., Zisserman, A. (eds.) ECCV 2008, Part I. LNCS, vol. 5302, pp. 427-440. Springer, Heidelberg (2008)

Digital Library

[3]

Agarwal, S., Snavely, N., Simon, I., Seitz, S.M., Szeliski, R.: Building Rome in a day. In: ICCV (2009)

[4]

Triggs, B., McLauchlan, P., Hartley, R.I., Fitzgibbon, A.: Bundle Adjustment - A modern synthesis. In: Vision Algorithms 1999, pp. 298-372 (1999)

Digital Library

[5]

Lourakis, M., Argyros, A.A.: SBA: A software package for generic sparse bundle adjustment. TOMS 36, 2 (2009)

Digital Library

[6]

Mouragnon, E., Lhuillier, M., Dhome, M., Dekeyser, F., Sayd, P.: Generic and real-time structure from motion using local bundle adjustment. Image and Vision Computing 27, 1178-1193 (2009)

Digital Library

[7]

Steedly, D., Essa, I.: Propagation of innovative information in non-linear leastsquares structure from motion. In: ICCV, pp. 223-229 (2001)

[8]

Ni, K., Steedly, D., Dellaert, F.: Out-of-core bundle adjustment for large-scale 3d reconstruction. In: ICCV (2007)

[9]

Steedly, D., Essa, I., Dellaert, F.: Spectral partitioning for structure from motion. In: ICCV, pp. 996-1003 (2003)

Digital Library

[10]

Hartley, R.I., Zisserman, A.: Multiple View Geometry in Computer Vision. Cambridge University Press, Cambridge (2003)

Digital Library

[11]

Nocedal, J., Wright, S.: Numerical optimization. Springer, Heidelberg (2000)

[12]

More, J.: The Levenberg-Marquardt algorithm: implementation and theory. Lecture Notes in Math. 630, 105-116 (1977)

[13]

Björck, A.: Numerical methods for least squares problems. SIAM, Philadelphia (1996)

[14]

Madsen, K., Nielsen, H., Tingleff, O.: Methods for non-linear least squares problems (2004)

[15]

Brown, D.C.: A solution to the general problem of multiple station analytical stereotriangulation. Technical Report 43, Patrick Airforce Base, Florida (1958)

[16]

Trefethen, L., Bau, D.: Numerical linear algebra. SIAM, Philadelphia (1997)

[17]

Chen, Y., Davis, T., Hager, W., Rajamanickam, S.: Algorithm 887: CHOLMOD, Supernodal Sparse Cholesky Factorization and Update/Downdate. TOMS 35 (2008)

Digital Library

[18]

Wright, S.J., Holt, J.N.: An inexact Levenberg-Marquardt method for large sparse nonlinear least squares. J. Austral. Math. Soc. Ser. B 26, 387-403 (1985)

[19]

Saad, Y.: Iterative methods for sparse linear systems. SIAM, Philadelphia (2003)

Digital Library

[20]

Elsner, L.: A note on optimal block-scaling of matrices. Numer. Math. 44, 127-128 (1984)

Digital Library

[21]

Mandel, J.: On block diagonal and Schur complement preconditioning. Numer. Math. 58, 79-93 (1990)

Digital Library

[22]

Mathew, T.: Domain decomposition methods for the numerical solution of partial differential equations. Springer, Heidelberg (2008)

Digital Library

[23]

Dennis Jr., J., Gay, D., Welsch, R.: Algorithm 573: NL2SOLan adaptive nonlinear least-squares algorithm {E4}. TOMS 7, 369-383 (1981)

Digital Library

[24]

Goto, K., Van De Geijn, R.: High-performance implementation of the level-3 blas. TOMS 35, 1-14 (2008)

Digital Library

[25]

Snavely, N., Seitz, S.M., Szeliski, R.: Photo Tourism: Exploring photo collections in 3D. TOG 25, 835-846 (2006)

Digital Library

[26]

Engels, C., Stewenius, H., Nister, D.: Bundle adjustment rules. Photogrammetric Computer Vision 2 (2006)

[27]

Lourakis, M., Argyros, A.: Is Levenberg-Marquardt the most efficient optimization algorithm for implementing bundle adjustment. In: ICCV, pp. 1526-1531 (2005)

Digital Library

[28]

Byröd, M., Åström, K., Lund, S.: Bundle adjustment using conjugate gradients with multiscale preconditioning (2009)

Cited By

Pineda LFan TMonge MVenkataraman SSodhi PChen ROrtiz JDeTone DWang AAnderson SDong JAmos BMukadam MKoyejo SMohamed SAgarwal ABelgrave DCho KOh A(2022)TheseusProceedings of the 36th International Conference on Neural Information Processing Systems10.5555/3600270.3600545(3801-3818)Online publication date: 28-Nov-2022
https://dl.acm.org/doi/10.5555/3600270.3600545
Liu WYu BGan YLiu QTang JLiu SZhu Y(2021)Archytas: A Framework for Synthesizing and Dynamically Optimizing Accelerators for Robotic LocalizationMICRO-54: 54th Annual IEEE/ACM International Symposium on Microarchitecture10.1145/3466752.3480077(479-493)Online publication date: 18-Oct-2021
https://dl.acm.org/doi/10.1145/3466752.3480077
Mara MHeide FZollhöfer MNießner MHanrahan P(2021)Thallo – Scheduling for High-Performance Large-Scale Non-Linear Least-Squares SolversACM Transactions on Graphics10.1145/345398640:5(1-14)Online publication date: 24-Sep-2021
https://dl.acm.org/doi/10.1145/3453986
Show More Cited By

Recommendations

A scalable parallel preconditioned conjugate gradient method for bundle adjustment
Abstract
Bundle adjustment is a fundamental problem in computer vision, with important applications such as 3D structure reconstruction from 2D images. This paper focuses on large-scale bundle adjustment tasks, e.g., city-wide 3D reconstruction, which ...
A compressed matrix sequence method for solving normal equations of bundle adjustment
Abstract
Bundle adjustment is a least squares method-based algorithm for minimizing the global reprojection error and has provided an effective solution for structure from motion (SfM). The Levenberg–Marquardt algorithm provides a feasible and convenient ...
Multidirectional Conjugate Gradients for Scalable Bundle Adjustment
Pattern Recognition
Abstract
We revisit the problem of large-scale bundle adjustment and propose a technique called Multidirectional Conjugate Gradients that accelerates the solution of the normal equation by up to 61%. The key idea is that we enlarge the search space of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

ECCV'10: Proceedings of the 11th European conference on Computer vision: Part II

September 2010

813 pages

ISBN:3642155510

Editors:
Kostas Daniilidis
GRASP Laboratory, University of Pennsylvania, Philadelphia, PA
,
Petros Maragos
National Technical University of Athens, School of Electrical and Computer Engineering, Athens, Greece
,
Nikos Paragios
Ecole Centrale de Paris, Department of Applied Mathematics, Chatenay-Malabry, France

Sponsors

Adobe
Google Inc.
Microsoft Research: Microsoft Research
INRIA: Institut Natl de Recherche en Info et en Automatique
IBM: IBM

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 05 September 2010

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

27
Total Citations
View Citations
3
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Pineda LFan TMonge MVenkataraman SSodhi PChen ROrtiz JDeTone DWang AAnderson SDong JAmos BMukadam MKoyejo SMohamed SAgarwal ABelgrave DCho KOh A(2022)TheseusProceedings of the 36th International Conference on Neural Information Processing Systems10.5555/3600270.3600545(3801-3818)Online publication date: 28-Nov-2022
https://dl.acm.org/doi/10.5555/3600270.3600545
Liu WYu BGan YLiu QTang JLiu SZhu Y(2021)Archytas: A Framework for Synthesizing and Dynamically Optimizing Accelerators for Robotic LocalizationMICRO-54: 54th Annual IEEE/ACM International Symposium on Microarchitecture10.1145/3466752.3480077(479-493)Online publication date: 18-Oct-2021
https://dl.acm.org/doi/10.1145/3466752.3480077
Mara MHeide FZollhöfer MNießner MHanrahan P(2021)Thallo – Scheduling for High-Performance Large-Scale Non-Linear Least-Squares SolversACM Transactions on Graphics10.1145/345398640:5(1-14)Online publication date: 24-Sep-2021
https://dl.acm.org/doi/10.1145/3453986
Shaikhha AFitzgibbon AVytiniotis DPeyton Jones S(2019)Efficient differentiable programming in a functional array-processing languageProceedings of the ACM on Programming Languages10.1145/33417013:ICFP(1-30)Online publication date: 26-Jul-2019
https://dl.acm.org/doi/10.1145/3341701
Kapoor ALarco HKiveris RTeredesai AKumar VLi YRosales RTerzi EKarypis G(2019)NostalginProceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining10.1145/3292500.3330743(2565-2575)Online publication date: 25-Jul-2019
https://dl.acm.org/doi/10.1145/3292500.3330743
Hadfield SLebeda KBowden R(2019)HARD-PnPIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2018.280644641:3(768-774)Online publication date: 1-Mar-2019
https://dl.acm.org/doi/10.1109/TPAMI.2018.2806446
Wei MYan QLuo FSong CXiao C(2019)Joint bilateral propagation upsampling for unstructured multi-view stereoThe Visual Computer: International Journal of Computer Graphics10.1007/s00371-019-01688-535:6-8(797-809)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1007/s00371-019-01688-5
Labrie-Larrivée FLaurendeau DLalonde J(2019)Depth texture synthesis for high-resolution reconstruction of large scenesMachine Vision and Applications10.1007/s00138-019-01030-y30:4(795-806)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1007/s00138-019-01030-y
Hepp BNießner MHilliges O(2018)Plan3DACM Transactions on Graphics10.1145/323379438:1(1-17)Online publication date: 14-Dec-2018
https://dl.acm.org/doi/10.1145/3233794
Liu LXia XSun HShen QXu JChen BHuang HXu K(2018)Object-aware guidance for autonomous scene reconstructionACM Transactions on Graphics10.1145/3197517.320129537:4(1-12)Online publication date: 30-Jul-2018
https://dl.acm.org/doi/10.1145/3197517.3201295
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents