Abstract
This paper is a survey of the theory and methods of photogrammetric bundle adjustment, aimed at potential implementors in the computer vision community. Bundle adjustment is the problem of refining a visual reconstruction to produce jointly optimal structure and viewing parameter estimates. Topics covered include: the choice of cost function and robustness; numerical optimization including sparse Newton methods, linearly convergent approximations, updating and recursive methods; gauge (datum) invariance; and quality control. The theory is developed for general robust cost functions rather than restricting attention to traditional nonlinear least squares.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
F. Ackermann. Digital image correlation: Performance and potential applications in photogrammetry. Photogrammetric Record, 11(64):429–439, 1984.
F. Amer. Digital block adjustment. Photogrammetric Record, 4:34–47, 1962.
E. Anderson, Z. Bai, C. Bischof, S. Blackford, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenney, and D. Sorensen. LAPACK Users’ Guide, Third Edition. SIAM Press, Philadelphia, 1999. LAPACK home page: http://www.netlib.org/lapack.
C. Ashcraft and J. W.-H. Liu. Robust ordering of sparse matrices using multisection. SIAM J. Matrix Anal. Appl., 19:816–832, 1998.
K. B. Atkinson, editor. Close Range Photogrammetry and Machine Vision. Whittles Publishing, Roseleigh House, Latheronwheel, Caithness, Scotland, 1996.
W. Baarda. S-transformations and criterion matrices. Netherlands Geodetic Commission, Publications on Geodesy, New Series, Vol. 5, No. 1 (168 pages), 1967.
W. Baarda. Statistical concepts in geodesy Netherlands Geodetic Commission Publications on Geodesy, New Series, Vol. 2, No. 4 (74 pages), 1967.
W. Baarda. A testing procedure for use in geodetic networks. Netherlands Geodetic Commission Publications on Geodesy, New Series, Vol. 2, No. 5 (97 pages), 1968.
E. P. Baltsavias. Multiphoto Geometrically Constrained Matching. PhD thesis, ETH-Zurich, 1992.
R. Barrett, M. W. Berry, T. F. Chan, J. Demmel, J. Donato, J. Dongarra, V. Eijkhout, R. Pozo, C. Romine, and H. van der Vorst. Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods. SIAM Press, Philadelphia, 1993.
Åke Björck. Numerical Methods for Least Squares Problems. SIAM Press, Philadelphia, PA, 1996.
J. A. R. Blais. Linear least squares computations using Givens transformations. Canadian Surveyor, 37(4):225–233, 1983.
P. T. Boggs, R. H. Byrd, J. E. Rodgers, and R. B. Schnabel. Users reference guide for ODRPACK 2.01: Software for weighted orthogonal distance regression. Technical Report NISTIR 92-4834, NIST, Gaithersburg, MD, June 1992.
P. T. Boggs, R. H. Byrd, and R. B. Schnabel. A stable and efficient algorithm for nonlinear orthogonal regression. SIAM J. Set Statist. Comput, 8:1052–1078, 1987.
R. J. Boscovich. De litteraria expeditione per pontificiam ditionem, et synopsis amplioris operis, ac habenturplura ejus ex exemplaria etiam sensorum impressa. Bononiensi Scientarum et Artum Instituto Atque Academia Commentarii, IV:353–396, 1757.
D. C. Brown. A solution to the general problem of multiple station analytical stereotriangulation. Technical Report RCA-MTP Data Reduction Technical Report No. 43 (or AFMTC TR 58-8), Patrick Airforce Base, Florida, 1958.
D. C. Brown. Close range camera calibration. Photogrammetric Engineering, XXXVII(8), August 1971.
D. C. Brown. Calibration of close range cameras. Int. Archives Photogrammetry, 19(5), 1972. Unbound paper (26 pages).
D. C. Brown. The bundle adjustment — progress and prospects. Int. Archives Photogrammetry, 21(3), 1976. Paper number 3-03 (33 pages).
Q. Chen and G. Medioni. Efficient iterative solutions to m-view projective reconstruction problem. In Int. Conf. Computer Vision & Pattern Recognition, pages II:55–61. IEEE Press, 1999.
M. A. R. Cooper and P. A. Cross. Statistical concepts and their application in photogrammetry and surveying. Photo grammetric Record, 12(71):637–663, 1988.
M. A. R. Cooper and P. A. Cross. Statistical concepts and their application in photogrammetry and surveying (continued). Photo grammetric Record, 13(77):645–678, 1991.
D. R. Cox and D. V. Hinkley. Theoretical Statistics. Chapman & Hall, 1974.
P. J. de Jonge. A comparative study of algorithms for reducing the fill-in during Cholesky factorization. Bulletin Géodésique, 66:296–305, 1992.
A. Dermanis. The photogrammetric inner constraints. J. Photogrammetry & Remote Sensing, 49(1):25–39, 1994.
I. Duff, A. M. Erisman, and J. K. Reid. Direct Methods for Sparse Matrices. Oxford University Press, 1986.
O. Faugeras. What can be seen in three dimensions with an uncalibrated stereo rig? In G. Sandini, editor, European Conf. Computer Vision, Santa Margherita Ligure, Italy, May 1992. Springer-Verlag.
A. W. Fitzgibbon and A. Zisserman. Automatic camera recovery for closed or open image sequences. In European Conf. Computer Vision, pages 311–326, Freiburg, 1998.
R. Fletcher. Practical Methods of Optimization. John Wiley, 1987.
W. Förstner. Evaluation of block adjustment results. Int. Arch. Photogrammetry, 23-III, 1980.
W. Förstner. On the geometric precision of digital correlation. Int. Arch. Photogrammetry & Remote Sensing, 24(3): 176–189, 1982.
W. Förstner. A feature-based correspondence algorithm for image matching. Int. Arch. Photogrammetry & Remote Sensing, 26(3/3): 150–166, 1984.
W. Förstner. The reliability of block triangulation. Photogrammetric Engineering & Remote Sensing, 51(8): 1137–1149, 1985.
W. Förstner. Reliability analysis of parameter estimation in linear models with applications to mensuration problems in computer vision. Computer Vision, Graphics & Image Processing, 40:273–310, 1987.
D. A. Forsyth, S. Ioffe, and J. Haddon. Bayesian structure from motion. In Int. Conf. Computer Vision, pages 660–665, Corfu, 1999.
C. F. Gauss. Werke. Königlichen Gesellschaft der Wissenschaften zu Göttingen, 1870–1928.
C. F. Gauss. Theoria Combinationis Observationum Erroribus Minimis Obnoxiae (Theory of the Combination of Observations Least Subject to Errors). SIAM Press, Philadelphia, PA, 1995. Originally published in Commentatines Societas Regiae Scientarium Gottingensis Recentiores 5, 1823 (Pars prior, Pars posterior), 6, 1828 (Supplementum). Translation and commentary by G. W. Stewart.
J. A. George. Nested dissection of a regular finite element mesh. SIAM J. Numer. Anal. 10:345–363, 1973.
J. A. George, M. T. Heath, and E. G. Ng. A comparison of some methods for solving sparse linear least squares problems. SIAM J. Set Statist. Comput., 4:177–187, 1983.
J. A. George and J. W.-H. Liu. Computer Solution of Large Sparse Positive Definite Systems. Prentice-Hall, 1981.
J. A. George and J. W.-H. Liu. Householder reflections versus Givens rotations in sparse orthogonal decomposition. Lin. Alg. Appl., 88/89:223–238, 1987.
P. Gill, W. Murray, and M. Wright. Practical Optimization. Academic Press, 1981.
P. E. Gill, G. H. Golub, W. Murray, and M. Saunders. Methods for modifying matrix factorizations. Math. Comp., 28:505–535, 1974.
G. Golub and C. F. Van Loan. Matrix Computations. Johns Hopkins University Press, 3rd edition, 1996.
G. Golub and R. Plemmons. Large-scale geodetic least squares adjustment by dissection and orthogonal decomposition. Linear Algebra Appl., 34:3–28, 1980.
S. Granshaw. Bundle adjustment methods in engineering photogrammetry. Photogrammetric Record, 10(56):181–207, 1980.
A. Greenbaum. Behaviour of slightly perturbed Lanczos and conjugate-gradient recurrences. Linear Algebra Appl., 113:7–63, 1989.
A. Greenbaum. Iterative Methods for Solving Linear Systems. SIAM Press, Philadelphia, 1997.
A. Grün. Accuracy, reliability and statistics in close range photogrammetry. In Inter-Congress Symposium of ISP Commission V, page Presented paper. Unbound paper No.9 (24 pages), Stockholm, 1978.
A. Grün. Precision and reliability aspects in close range photogrammetry. Int. Arch. Photogrammetry, 11(23B):378–391, 1980.
A. Grün. An optimum algorithm for on-line triangulation. In Symposium of Commission III of the ISPRS, Helsinki, 1982.
A. Grün. Adaptive least squares correlation — concept and first results. Intermediate Research Report to Helava Associates, Ohio State University. 13 pages, March 1984.
A. Grün. Adaptive kleinste Quadrate Korrelation and geometrische Zusatzinformationen. Vermessung, Photogrammetrie, Kulturtechnik, 9(83):309–312, 1985.
A. Grün. Algorithmic aspects of on-line triangulation. Photogrammetric Engineering & Remote Sensing, 4(51):419–436, 1985.
A. Grün and E. P. Baltsavias. Adaptive least squares correlation with geometrical constraints. In SPIE Computer Vision for Robots, volume 595, pages 72–82, Cannes, 1985.
R. Gupta and R. I. Hartley. Linear pushbroom cameras. IEEE Trans. Pattern Analysis & Machine Intelligence, September 1997.
M. S. Gyer. The inversion of the normal equations of analytical aerotriangulation by the method of recursive partitioning. Technical report, Rome Air Development Center, Rome, New York, 1967.
R. Hartley. Euclidean reconstruction from multiple views. In 2 nd Europe-U.S. Workshop on Invariance, pages 237–56, Ponta Delgada, Azores, October 1993.
R. Hartley. An object-oriented approach to scene reconstruction. In IEEE Conf. Systems, Man & Cybernetics, pages 2475–2480, Beijing, October 1996.
R. Hartley. Lines and points in three views and the trifocal tensor. Int. J. Computer Vision, 22(2): 125–140, 1997.
R. Hartley, R. Gupta, and T. Chang. Stereo from uncalibrated cameras. In Int. Conf. Computer Vision & Pattern Recognition, pages 761–4, Urbana-Champaign, Illinois, 1992.
R. Hartley and A. Zisserman. Multiple View Geometry in Computer Vision. Cambridge University Press, 2000.
R. I. Hartley and T. Saxena. The cubic rational polynomial camera model. In Image Understanding Workshop, pages 649–653, 1997.
F. Helmert. Die Mathematischen und Physikalischen Theorien der höheren Geodäsie, volume 1 Teil. Teubner, Leipzig, 1880.
B. Hendrickson and E. Rothberg. Improving the run time and quality of nested dissection ordering. SIAM J. Set Comput., 20:468–489, 1998.
K. R. Holm. Test of algorithms for sequential adjustment in on-line triangulation. Photogrammetria, 43:143–156, 1989.
M. Irani, P. Anadan, and M. Cohen. Direct recovery of planar-parallax from multiple frames. In Vision Algorithms: Theory and Practice. Springer-Verlag, 2000.
K. Kanatani and N. Ohta. Optimal robot self-localization and reliability evaluation. In European Conf. Computer Vision, pages 796–808, Freiburg, 1998.
H. M. Karara. Non-Topographic Photogrammetry. Americal Society for Photogrammetry and Remote Sensing, 1989.
G. Karypis and V. Kumar. Multilevel k-way partitioning scheme for irregular graphs. J. Parallel & Distributed Computing, 48:96–129, 1998.
G. Karypis and V. Kumar. A fast and highly quality multilevel scheme for partitioning irregular graphs. SIAM J. Scientific Computing, 20(1):359–392, 1999. For Metis code see http://www-users.cs.umn.edu/karypis/.
I. P. King. An automatic reordering scheme for simultaneous equations derived from network systems. Int. J. Numer. Meth. Eng., 2:479–509, 1970.
K. Kraus. Photogrammetry. Dummler, Bonn, 1997. Vol.1: Fundamentals and Standard Processes. Vol.2: Advanced Methods and Applications. Available in German, English & several other languages.
A. M. Legendre. Nouvelles méthodes pour la détermination des orbites des comètes. Courcier, Paris, 1805. Appendix on least squares.
R. Levy. Restructuring the structural stiffness matrix to improve computational efficiency. Jet Propulsion Lab. Technical Review, 1:61–70, 1971.
M. X. Li. Hierarchical Multi-point Matching with Simultaneous Detection and Location of Breaklines. PhD thesis, KTH Stockholm, 1989.
Q.-T. Luong, R. Deriche, O. Faugeras, and T. Papadopoulo. On determining the fundamental matrix: Analysis of different methods and experimental results. Technical Report RR-1894, INRIA, Sophia Antipolis, France, 1993.
S. Mason. Expert system based design of close-range photogrammetric networks. J. Photogrammetry & Remote Sensing, 50(5): 13–24, 1995.
S.O. Mason. Expert System Based Design of Photogrammetric Networks. Ph.D. Thesis, Institut für Geodäsie und Photogrammetrie, ETH Zürich, May 1994.
B. Matei and P. Meer. Bootstrapping a heteroscedastic regression model with application to 3D rigid motion evaluation. In Vision Algorithms: Theory and Practice. Springer-Verlag, 2000.
P. F. McLauchlan. Gauge independence in optimization algorithms for 3D vision. In Vision Algorithms: Theory and Practice, Lecture Notes in Computer Science, Corfu, September 1999. Springer-Verlag.
P. F. McLauchlan. Gauge invariance in projective 3D reconstruction. In Multi-View Modeling and Analysis of Visual Scenes, Fort Collins, CO, June 1999. IEEE Press.
P. F. McLauchlan. The variable state dimension filter. Technical Report VSSP 5/99, University of Surrey, Dept of Electrical Engineering, December 1999.
P. F. McLauchlan. A batch/recursive algorithm for 3D scene reconstruction. In Int. Conf. Computer Vision & Pattern Recognition, Hilton Head, South Carolina, 2000.
P. F. McLauchlan and D. W. Murray. A unifying framework for structure and motion recovery from image sequences. In E. Grimson, editor, Int. Conf. Computer Vision, pages 314–20, Cambridge, MA, June 1995.
P. F. McLauchlan and D. W. Murray. Active camera calibration for a Head-Eye platform using the Variable State-Dimension filter. IEEE Trans. Pattern Analysis & Machine Intelligence, 18(1): 15–22, 1996.
P. Meissl. Die innere Genauigkeit eines Punkthaufens. Österreichische Zeitschrift für Vermessungswesen, 50(5): 159–165 and 50(6): 186–194, 1962.
E. Mikhail and R. Helmering. Recursive methods in photogrammetric data reduction. Photogrammetric Engineering, 39(9):983–989, 1973.
E. Mittermayer. Zur Ausgleichung freier Netze. Zeitschrift für Vermessungswesen, 97(11):481–489, 1962.
J. J. Moré and S. J. Wright. Optimization Software Guide. SIAM Press, Philadelphia, 1993.
D. D. Morris and T. Kanade. A unified factorization algorithm for points, line segments and planes with uncertainty. In Int. Conf. Computer Vision, pages 696–702, Bombay, 1998.
D. D. Morris, K. Kanatani, and T. Kanade. Uncertainty modelling for optimal structure and motion. In Vision Algorithms: Theory and Practice. Springer-Verlag, 2000.
J. Nocedal and S.J. Wright. Numerical Optimization. Springer-Verlag, 1999.
M. Okutomi and T. Kanade. A multiple-baseline stereo. IEEE Trans. Pattern Analysis & Machine Intelligence, 15(4):353–363, 1993.
D. W. Proctor. The adjustment of aerial triangulation by electronic digital computers. Photogrammetric Record, 4:24–33, 1962.
B. D. Ripley. Pattern Recongition and Neural Networks. Cambridge University Press, 1996.
D. Rosenholm. Accuracy improvement of digital matching for elevation of digital terrain models. Int. Arch. Photogrammetry & Remote Sensing, 26(3/2):573–587, 1986.
S. Roy and I. Cox. A maximum-flow formulation of the n-camera stereo correspondence problem. In Int. Conf. Computer Vision, Bombay, 1998.
Y. Saad. On the rates of convergence of Lanczos and block-Lanczos methods. SIAMJ. Numer. Anal., 17:687–706, 1980.
C. C. Slama, editor. Manual of Photo grammetry. American Society of Photogrammetry and Remote Sensing, Falls Church, Virginia, USA, 1980.
R. A. Snay. Reducing the profile of sparse symmetric matrices. Bulletin Géodésique, 50:341–352, 1976. Also NOAA Technical Memorandum NOS NGS-4, National Geodetic Survey, Rockville, MD.
R. Szeliski, S.B. Kang, and H. Y. Shum. A parallel feature tracker for extended image sequences. Technical Report CRL 95/2, DEC Cambridge Research Labs, May 1995.
R. Szeliski and S.B. Kang. Shape ambiguities in structure from motion. In European Conf. Computer Vision, pages 709–721, Cambridge, 1996.
R. Szeliski and H.Y Shum. Motion estimation with quadtree splines. In Int. Conf. Computer Vision, pages 757–763, Boston, 1995.
B. Triggs. A new approach to geometric fitting. Available from http://www.inrialpes.fr/movi/people/Triggs, 1997.
B. Triggs. Optimal estimation of matching constraints. In R. Koch and L. Van Gool, editors, 3D Structure from Multiple Images of Large-scale Environments SMILE’98, Lecture Notes in Computer Science. Springer-Verlag, 1998.
G. L. Strang van Hees. Variance-covariance transformations of geodetic networks. Manuscripta Geodaetica, 7:1–20, 1982.
X. Wang and T. A. Clarke. Separate adjustment of close range photogrammetric measurements. Int. Symp. Photogrammetry & Remote Sensing, XXXII, part 5:177–184, 1998.
P.R. Wolf and C.D. Ghilani. Adjustment Computations: Statistics and Least Squares in Surveying and GIS. John Wiley & Sons, 1997.
B.P. Wrobel. Facets stereo vision (FAST vision) — a new approach to computer stereo vision and to digital photogrammetry. In ISPRS Intercommission Conf. Fast Processing of Photogrammetric Data, pages 231–258, Interlaken, Switzerland, June 1987.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Triggs, B., McLauchlan, P.F., Hartley, R.I., Fitzgibbon, A.W. (2000). Bundle Adjustment — A Modern Synthesis. In: Triggs, B., Zisserman, A., Szeliski, R. (eds) Vision Algorithms: Theory and Practice. IWVA 1999. Lecture Notes in Computer Science, vol 1883. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44480-7_21
Download citation
DOI: https://doi.org/10.1007/3-540-44480-7_21
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67973-8
Online ISBN: 978-3-540-44480-0
eBook Packages: Springer Book Archive