SBA

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

SBA: A software package for generic sparse bundle adjustment

Full text

Pdf (1.70 MB)

Source

ACM Transactions on Mathematical Software (TOMS) archive
Volume 36 , Issue 1 (March 2009) table of contents

Article No. 2

Year of Publication: 2009

ISSN:0098-3500

Authors

Manolis I. A. Lourakis	Foundation for Research and Technology—Hellas
Antonis A. Argyros	Foundation for Research and Technology—Hellas

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 66, Downloads (12 Months): 280, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1486525.1486527 What is a DOI?

ABSTRACT

Bundle adjustment constitutes a large, nonlinear least-squares problem that is often solved as the last step of feature-based structure and motion estimation computer vision algorithms to obtain optimal estimates. Due to the very large number of parameters involved, a general purpose least-squares algorithm incurs high computational and memory storage costs when applied to bundle adjustment. Fortunately, the lack of interaction among certain subgroups of parameters results in the corresponding Jacobian being sparse, a fact that can be exploited to achieve considerable computational savings. This article presents sba, a publicly available C/C++ software package for realizing generic bundle adjustment with high efficiency and flexibility regarding parameterization.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Patrick R. Amestoy , Enseeiht-Irit , Timothy A. Davis , Iain S. Duff, Algorithm 837: AMD, an approximate minimum degree ordering algorithm, ACM Transactions on Mathematical Software (TOMS), v.30 n.3, p.381-388, September 2004 [doi>10.1145/1024074.1024081]
	2	E. Anderson , Z. Bai , C. Bischof , L. S. Blackford , J. Demmel , Jack J. Dongarra , J. Du Croz , S. Hammarling , A. Greenbaum , A. McKenney , D. Sorensen, LAPACK Users' guide (third ed.), Society for Industrial and Applied Mathematics, Philadelphia, PA, 1999
	3	Barrett, R., Berry, M., Chan, T. F., Demmel, J., Donato, J., Dongarra, J., Eijkhout, V., Pozo, R., Romine, C., and der Vorst, H. V. 1994. Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, 2nd ed. SIAM, Philadelphia, PA. http://www.netlib.org/linalg/html_templates/report.html.
	4	Paul A. Beardsley , Philip H. S. Torr , Andrew Zisserman, 3D Model Acquisition from Extended Image Sequences, Proceedings of the 4th European Conference on Computer Vision-Volume II, p.683-695, April 15-18, 1996
	5	G. Le Besnerais , M. Sanfourche , F. Champagnat, Dense height map estimation from oblique aerial image sequences, Computer Vision and Image Understanding, v.109 n.2, p.204-225, February, 2008 [doi>10.1016/j.cviu.2007.07.003]
	6	Gerald Bianchi , Christoph Jung , Benjamin Knoerlein , Gabor Szekely , Matthias Harders, High-fidelity visuo-haptic interaction with virtual objects in multi-modal AR systems, Proceedings of the 2006 Fifth IEEE and ACM International Symposium on Mixed and Augmented Reality (ISMAR'06), p.187-196, October 22-25, 2006 [doi>10.1109/ISMAR.2006.297813]
	7	Brooks, M., Chojnacki, W., Gawley, D., and van den Hengel, A. 2001. What value covariance information in estimating vision parameters? In Proceedings of the International Conference on Computer Vision. Vol. I. IEEE Press, Los Alamitos, CA, 302--308.
	8	Brown, D. 1958. A solution to the general problem of multiple station analytical stereo triangulation. Tech. rep. 43. RCA-MTP. Feb.
	9	Yanqing Chen , Timothy A. Davis , William W. Hager , Sivasankaran Rajamanickam, Algorithm 887: CHOLMOD, Supernodal Sparse Cholesky Factorization and Update/Downdate, ACM Transactions on Mathematical Software (TOMS), v.35 n.3, p.1-14, October 2008 [doi>10.1145/1391989.1391995]
	10	Andrew R. Conn , Nicholas I. M. Gould , Philippe L. Toint, Trust-region methods, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
	11	Timothy A. Davis, Algorithm 849: A concise sparse Cholesky factorization package, ACM Transactions on Mathematical Software (TOMS), v.31 n.4, p.587-591, December 2005 [doi>10.1145/1114268.1114277]
	12	James W. Demmel, Applied numerical linear algebra, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1997
	13	James W. Demmel , Stanley C. Eisenstat , John R. Gilbert , Xiaoye S. Li , Joseph W. H. Liu, A Supernodal Approach to Sparse Partial Pivoting, SIAM Journal on Matrix Analysis and Applications, v.20 n.3, p.720-755, July 1999 [doi>10.1137/S0895479895291765]
	14	Dennis, J. 1977. Nonlinear least-squares. In State of the Art in Numerical Analysis, D. Jacobs, Ed. Academic Press, New York, NY, 269--312.
	15	John E. Dennis, Jr. , David M. Gay , Roy E. Walsh, An Adaptive Nonlinear Least-Squares Algorithm, ACM Transactions on Mathematical Software (TOMS), v.7 n.3, p.348-368, Sept. 1981 [doi>10.1145/355958.355965]
	16	J. E. Dennis, Jr. , Robert B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations (Classics in Applied Mathematics, 16), Soc for Industrial & Applied Math, 1996
	17	Andrew W. Fitzgibbon , Andrew Zisserman, Automatic Camera Recovery for Closed or Open Image Sequences, Proceedings of the 5th European Conference on Computer Vision-Volume I, p.311-326, June 02-06, 1998
	18	Gay, D. 1990. Usage summary for selected optimization routines. Tech. rep. 153. AT&T Bell Laboratories, Murray Hill, NJ.
	19	Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
	20	Andreas Griewank , David Juedes , Jean Utke, Algorithm 755: ADOL-C: a package for the automatic differentiation of algorithms written in C/C++, ACM Transactions on Mathematical Software (TOMS), v.22 n.2, p.131-167, June 1996 [doi>10.1145/229473.229474]
	21	Richard I. Hartley, Euclidean Reconstruction from Uncalibrated Views, Proceedings of the Second Joint European - US Workshop on Applications of Invariance in Computer Vision, p.237-256, October 09-14, 1993
	22	Richard Hartley , Andrew Zisserman, Multiple view geometry in computer vision, Cambridge University Press, New York, NY, 2000
	23	K. L. Hiebert, An Evaluation of Mathematical Software that Solves Nonlinear Least Squares Problems, ACM Transactions on Mathematical Software (TOMS), v.7 n.1, p.1-16, March 1981 [doi>10.1145/355934.355935]
	24	Horn, B. 1987. Closed-form solution of absolute orientation using unit quaternions. J. Opt. Soc. Amer. A 4, 4, 629--642.
	25	Irschara, A., Zach, C., and Bischof, H. 2007. Towards wiki-based dense city modeling. In Proceedings of the International Conference on Computer Vision. IEEE Press, Los Alamitos, CA, 1--8.
	26	Kelley, C. 1999. Iterative Methods for Optimization. SIAM Publications, Philadelphia.
	27	Michael Lampton, Damping-undamping strategies for the Levenberg-Marquardt nonlinear least-squares method, Computers in Physics, v.11 n.1, p.110-115, Jan./Feb. 1997 [doi>10.1063/1.168600]
	28	Levenberg, K. 1944. A method for the solution of certain non-linear problems in least squares. Quart. Appl. Math. 2, 2 (Jul.), 164--168.
	29	Manolis I. A. Lourakis , Antonis A. Argyros, Efficient, causal camera tracking in unprepared environments, Computer Vision and Image Understanding, v.99 n.2, p.259-290, August 2005 [doi>10.1016/j.cviu.2005.02.001]
	30	Manolis I. A. Lourakis , Antonis A. Argyros, Is Levenberg-Marquardt the Most Efficient Optimization Algorithm for Implementing Bundle Adjustment?, Proceedings of the Tenth IEEE International Conference on Computer Vision, p.1526-1531, October 17-20, 2005 [doi>10.1109/ICCV.2005.128]
	31	David G. Lowe, Distinctive Image Features from Scale-Invariant Keypoints, International Journal of Computer Vision, v.60 n.2, p.91-110, November 2004 [doi>10.1023/B:VISI.0000029664.99615.94]
	32	Chien-Ping Lu , Gregory D. Hager , Eric Mjolsness, Fast and Globally Convergent Pose Estimation from Video Images, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.6, p.610-622, June 2000 [doi>10.1109/34.862199]
	33	Madsen, K., Nielsen, H., and Tingleff, O. 2004. Methods for non-linear least squares problems. Technical University of Denmark. Lecture notes. http://www.imm.dtu.dk/pubdb/views/edoc_download.php/3215/pdf/imm3215.pdf.
	34	Marquardt, D. 1963. An algorithm for the least-squares estimation of nonlinear parameters. SIAM J. Appl. Math. 11, 2 (Jun.), 431--441.
	35	Moré, J. 1977. The Levenberg Marquardt algorithm: implementation and theory. In Numerical Analysis, G. Watson, Ed. Lecture Notes in Mathematics, vol. 630. Springer Verlag, Berlin, Germany, 105--116.
	36	Moré, J., Garbow, B., and Hillstrom, K. 1980. User guide for MINPACK-1. Tech. rep. ANL-80-74. Argonne National Laboratory, Argonne, IL.
	37	Moré, J. and Sorensen, D. 1983. Computing a trust region step. SIAM J. Sci. Statist. Comput. 4, 553--572.
	38	Joseph L. Mundy , Andrew Zisserman, Appendix—projective geometry for machine vision, Geometric invariance in computer vision, MIT Press, Cambridge, MA, 1992
	39	Nielsen, H. 1999. Damping parameter in Marquardt's method. Tech. rep. IMM-REP-1999-05. Technical University of Denmark, Aarhus, Denmark. http://www.imm.dtu.dk/~hbn.
	40	Nocedal, J. and Wright, S. 1999. Numerical Optimization. Springer, New York, NY.
	41	Marc Pollefeys , Luc Van Gool , Maarten Vergauwen , Frank Verbiest , Kurt Cornelis , Jan Tops , Reinhard Koch, Visual Modeling with a Hand-Held Camera, International Journal of Computer Vision, v.59 n.3, p.207-232, September-October 2004 [doi>10.1023/B:VISI.0000025798.50602.3a]
	42	Prasolov, V. 1994. Problems and Theorems in Linear Algebra. American Mathematical Society, Providence, RI.
	43	Semple, J. and Kneebone, G. 1952. Algebraic Projective Geometry. Oxford University Press, Oxford, U.K.
	44	Shi, J. and Tomasi, C. 1994. Good features to track. In Proceedings of the International Conference on Computer Vision and Pattern Recognition. IEEE Press, Los Alamitos, CA, 593--600.
	45	Shum, H.-Y., Ke, Q., and Zhang, Z. 1999. Efficient bundle adjustment with virtual key frames: a hierarchical approach to multi-frame structure from motion. In Proceedings of the International Conference on Computer Vision and Pattern Recognition. Vol. 2. IEEE Press, Los Alamitos, CA, 538--543.
	46	Slama, C. 1980. Manual of Photogrammetry, ed. American Society of Photogrammetry, Falls Church, VA.
	47	Noah Snavely , Steven M. Seitz , Richard Szeliski, Photo tourism: exploring photo collections in 3D, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
	48	Sünderhauf, N., Konolige, K., Lacroix, S., and Protzel, P. 2005. Visual odometry using sparse bundle adjustment on an autonomous outdoor vehicle. In Autonome Mobile Systeme 2005, P. Levi, M. Schanz, R. Lafrenz, and V. Avrutin, Eds. Informatik Aktuell. Springer Verlag, Berlin, Germany, 157--163.
	49	Szeliski, R. and Kang, S. 1994. Recovering 3D shape and motion from image streams using nonlinear least squares. J. Vis. Comm. Im. Repr. 5, 1, 10--28.
	50	Templeton, T., Shim, D., Geyer, C., and Sastry, S. 2007. Autonomous vision-based landing and terrain mapping using an MPC-controlled unmanned rotorcraft. In Proceedings of the IEEE ICRA'07. 1349--1356.
	51	Bill Triggs , Philip F. McLauchlan , Richard I. Hartley , Andrew W. Fitzgibbon, Bundle Adjustment - A Modern Synthesis, Proceedings of the International Workshop on Vision Algorithms: Theory and Practice, p.298-372, September 21-22, 1999
	52	Leandra Vicci, Quaternions and Rotations in 3-Space: The Algebra and its Geometric Interpretation, University of North Carolina at Chapel Hill, Chapel Hill, NC, 2001
	53	Le Xin , Qiang Wang , Jianhua Tao , Xiaoou Tang , Tieniu Tan , Harry Shum, Automatic 3D Face Modeling from Video, Proceedings of the Tenth IEEE International Conference on Computer Vision, p.1193-1199, October 17-20, 2005 [doi>10.1109/ICCV.2005.40]
	54	Zhengyou Zhang , Rachid Deriche , Olivier Faugeras , Quang-Tuan Luong, A robust technique for matching two uncalibrated images through the recovery of the unknown epipolar geometry, Artificial Intelligence, v.78 n.1-2, p.87-119, Oct. 1995 [doi>10.1016/0004-3702(95)00022-4]
	55	Zhang, Z. and Shan, Y. 2003. Incremental motion estimation through modified bundle adjustment. In Proceedings of the International Conference on Image Processing. Vol. 2. 343--346.