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 .
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
Snavely, N., Seitz, S.M., Szeliski, R.: Skeletal graphs for efficient structure from motion. In: CVPR, pp. 1–8 (2008)
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)
Agarwal, S., Snavely, N., Simon, I., Seitz, S.M., Szeliski, R.: Building Rome in a day. In: ICCV (2009)
Triggs, B., McLauchlan, P., Hartley, R.I., Fitzgibbon, A.: Bundle Adjustment - A modern synthesis. In: Vision Algorithms 1999, pp. 298–372 (1999)
Lourakis, M., Argyros, A.A.: SBA: A software package for generic sparse bundle adjustment. TOMS 36, 2 (2009)
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)
Steedly, D., Essa, I.: Propagation of innovative information in non-linear least-squares structure from motion. In: ICCV, pp. 223–229 (2001)
Ni, K., Steedly, D., Dellaert, F.: Out-of-core bundle adjustment for large-scale 3d reconstruction. In: ICCV (2007)
Steedly, D., Essa, I., Dellaert, F.: Spectral partitioning for structure from motion. In: ICCV, pp. 996–1003 (2003)
Hartley, R.I., Zisserman, A.: Multiple View Geometry in Computer Vision. Cambridge University Press, Cambridge (2003)
Nocedal, J., Wright, S.: Numerical optimization. Springer, Heidelberg (2000)
More, J.: The Levenberg-Marquardt algorithm: implementation and theory. Lecture Notes in Math. 630, 105–116 (1977)
Björck, A.: Numerical methods for least squares problems. SIAM, Philadelphia (1996)
Madsen, K., Nielsen, H., Tingleff, O.: Methods for non-linear least squares problems (2004)
Brown, D.C.: A solution to the general problem of multiple station analytical stereotriangulation. Technical Report 43, Patrick Airforce Base, Florida (1958)
Trefethen, L., Bau, D.: Numerical linear algebra. SIAM, Philadelphia (1997)
Chen, Y., Davis, T., Hager, W., Rajamanickam, S.: Algorithm 887: CHOLMOD, Supernodal Sparse Cholesky Factorization and Update/Downdate. TOMS 35 (2008)
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)
Saad, Y.: Iterative methods for sparse linear systems. SIAM, Philadelphia (2003)
Elsner, L.: A note on optimal block-scaling of matrices. Numer. Math. 44, 127–128 (1984)
Mandel, J.: On block diagonal and Schur complement preconditioning. Numer. Math. 58, 79–93 (1990)
Mathew, T.: Domain decomposition methods for the numerical solution of partial differential equations. Springer, Heidelberg (2008)
Dennis Jr., J., Gay, D., Welsch, R.: Algorithm 573: NL2SOLan adaptive nonlinear least-squares algorithm [E4]. TOMS 7, 369–383 (1981)
Goto, K., Van De Geijn, R.: High-performance implementation of the level-3 blas. TOMS 35, 1–14 (2008)
Snavely, N., Seitz, S.M., Szeliski, R.: Photo Tourism: Exploring photo collections in 3D. TOG 25, 835–846 (2006)
Engels, C., Stewenius, H., Nister, D.: Bundle adjustment rules. Photogrammetric Computer Vision 2 (2006)
Lourakis, M., Argyros, A.: Is Levenberg-Marquardt the most efficient optimization algorithm for implementing bundle adjustment. In: ICCV, pp. 1526–1531 (2005)
Byröd, M., Åström, K., Lund, S.: Bundle adjustment using conjugate gradients with multiscale preconditioning (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Agarwal, S., Snavely, N., Seitz, S.M., Szeliski, R. (2010). Bundle Adjustment in the Large. In: Daniilidis, K., Maragos, P., Paragios, N. (eds) Computer Vision – ECCV 2010. ECCV 2010. Lecture Notes in Computer Science, vol 6312. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-15552-9_3
Download citation
DOI: https://doi.org/10.1007/978-3-642-15552-9_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-15551-2
Online ISBN: 978-3-642-15552-9
eBook Packages: Computer ScienceComputer Science (R0)