Abstract
Bundle adjustment for multi-view reconstruction is traditionally done using the Levenberg-Marquardt algorithm with a direct linear solver, which is computationally very expensive. An alternative to this approach is to apply the conjugate gradients algorithm in the inner loop. This is appealing since the main computational step of the CG algorithm involves only a simple matrix-vector multiplication with the Jacobian. In this work we improve on the latest published approaches to bundle adjustment with conjugate gradients by making full use of the least squares nature of the problem. We employ an easy-to-compute QR factorization based block preconditioner and show how a certain property of the preconditioned system allows us to reduce the work per iteration to roughly half of the standard CG algorithm.
Chapter PDF
Similar content being viewed by others
References
Agarwal, S., Snavely, N., Simon, I., Seitz, S.M., Szeliski, R.: Building rome in a day. In: Proc. 12th Int. Conf. on Computer Vision, Kyoto, Japan (2009)
Snavely, N., Seitz, S.M., Szeliski, R.: Modeling the world from Internet photo collections. Int. Journal of Computer Vision 80, 189–210 (2008)
Mordohai, A.F.: Towards urban 3d reconstruction from video (2006)
Cornelis, N., Leibe, B., Cornelis, K., Gool, L.V.: 3d urban scene modeling integrating recognition and reconstruction. Int. Journal of Computer Vision 78, 121–141 (2008)
Hartley, R.I., Zisserman, A.: Multiple View Geometry in Computer Vision, 2nd edn. Cambridge University Press, Cambridge (2004)
Triggs, W., McLauchlan, P., Hartley, R., Fitzgibbon, A.: Bundle adjustment: A modern synthesis. In: Triggs, B., Zisserman, A., Szeliski, R. (eds.) ICCV-WS 1999. LNCS, vol. 1883, p. 298. Springer, Heidelberg (2000)
Lourakis, M.I.A., Argyros, A.A.: Sba: A software package for generic sparse bundle adjustment. ACM Trans. Math. Softw. 36, 1–30 (2009)
Byröd, M., Åström, K.: Bundle adjustment using conjugate gradients with multiscale preconditioning. In: Proc. British Machine Vision Conference, London, United Kingdom (2009)
Young, D.M.: Iterative solution of large linear systems. Academic Press, New York (1971)
Nielsen, H.B.: Damping parameter in marquardt’s method. Technical Report IMM-REP-1999-05, Technical University of Denmark (1999)
Hestenes, M.R., Stiefel, E.: Methods of conjugate gradients for solving linear systems. Journal of Research of the National Bureau of Standards 49, 409–436 (1952)
Golub, G.H., van Loan, C.F.: Matrix Computations, 3rd edn. The Johns Hopkins University Press, Baltimore (1996)
Fletcher, R., Reeves, C.M.: Function minimization by conjugate gradients. The Computer Journal 7, 149–154 (1964)
Björck, Å.: Numerical methods for least squares problems. SIAM, Philadelphia (1996)
Paige, C.C., Saunders, M.A.: Lsqr: An algorithm for sparse linear equations and sparse least squares. ACM Trans. Math. Softw. 8, 43–71 (1982)
Nocedal, J., Wright, S.J.: Numerical optimization, 2nd edn. Springer, Berlin (2006)
Golub, G.H., Manneback, P., Toint, P.L.: A comparison between some direct and iterative methods for certian large scale godetic least squares problems. SIAM J. Sci. Stat. Comput. 7, 799–816 (1986)
Reid, J.K.: The use of conjugate gradients for systems of linear equations possessing “property a”. SIAM Journal on Numerical Analysis 9, 325–332 (1972)
Snavely, N., Seitz, S.M., Szeliski, R.: Modeling the world from internet photo collections. International Journal of Computer Vision 80, 189–210 (2007)
Snavely, N., Seitz, S.M., Szeliski, R.: Skeletal sets for efficient structure from motion. In: Proc. Conf. Computer Vision and Pattern Recognition, Anchorage, USA (2008)
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
Byröd, M., Åström, K. (2010). Conjugate Gradient Bundle Adjustment. 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_9
Download citation
DOI: https://doi.org/10.1007/978-3-642-15552-9_9
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)