Bundle Adjustment — A Modern Synthesis
Lecture notes in computer sciencePublished 1 January 2000Open access
Bill Triggs, Philip F. McLauchlan, Richard Hartley, Andrew Fitzgibbon
Citations3,748
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
International audience
Keywords
Computer ScienceEngineering
Cambridge University Press eBooksMultiple View Geometry in Computer Vision
20,788 Citations2004Richard Hartley, Andrew Zisserman
Numerical Optimization
9,247 Citations1999Jorge Nocedal, Stephen J. Wright
Cambridge University Press eBooksPattern Recognition and Neural Networks
6,468 Citations1996B. D. Ripley
Practical Methods of Optimization
6,403 Citations2000R. Ian Fletcher
SIAM Journal on Scientific ComputingA Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
5,588 Citations1998George Karypis, Vipin Kumar
This work presents a new coarsening heuristic (called heavy-edge heuristic) for which the size of the partition of the coarse graph is within a small factor of theSize of the final partition obtained after multilevel refinement, and presents a much faster variation of the Kernighan--Lin (KL) algorithm for refining during uncoarsening.
Society for Industrial and Applied Mathematics eBooksTemplates for the Solution of Linear Systems: Building Blocks for Iterative Methods
3,433 Citations1994Richard Frederick Barrett, Michael Berry +8 more
This book presents both historical development and state-of-the-art methods for solving some of the most challenging computational problems facing researchers as some of these new approaches mature and become the state-of-the-art.
Society for Industrial and Applied Mathematics eBooksLAPACK Users' Guide
2,215 Citations1999E. Anderson, Z. Bai +9 more
Journal of Parallel and Distributed ComputingMultilevelk-way Partitioning Scheme for Irregular Graphs
1,680 Citations1998George Karypis, Vipin Kumar
Direct Methods for Sparse Matrices
1,612 Citations2017Iain Duff, A. M. Erisman +1 more
This book aims to be suitable also for a student course, probably at MSc level, and the subject is intensely practical and this book is written with practicalities ever in mind.
Texts in applied mathematicsIterative Methods for Solving Linear Systems
1,038 Citations2006Alfio Quarteroni, Riccardo Sacco +1 more
SIAM Journal on Numerical AnalysisNested Dissection of a Regular Finite Element Mesh
1,033 Citations1973Alan D. George
This paper presents an unusual numbering of the mesh (unknowns) and shows that if the authors avoid operating on zeros, the $LDL^T $ factorization of A can be computed using the same standard algorithm in $O(n^3 )$ arithmetic operations.
IEEE Transactions on Pattern Analysis and Machine IntelligenceA multiple-baseline stereo
938 Citations1993Masatoshi Okutomi, Takeo Kanade
Lecture notes in computer scienceWhat can be seen in three dimensions with an uncalibrated stereo rig?
833 Citations1992Olivier Faugeras
This paper addresses the problem of determining the kind of three- dimensional reconstructions that can be obtained from a binocular stereo rig for which no three-dimensional metric calibration data is available, and shows that even in this case some very rich non-metric reconstructions of the environment can nonetheless be obtained.
Mathematics of ComputationMethods for modifying matrix factorizations
581 Citations1974Philip E. Gill, Gene H. Golub +2 more
Several methods are described for modifying Cholesky factors and a new algorithm is presented for modifying the complete orthogonal factorization of a general matrix, from which the conventional QR factors are obtained as a special case.
A maximum-flow formulation of the N-camera stereo correspondence problem
479 Citations2002Sébastien Roy, Ingemar J. Cox
A new algorithm for solving the N-camera stereo correspondence problem by transforming it into a maximum-flow problem that provides a more accurate and coherent depth map than the traditional line-by-line stereo.
Lecture notes in computer scienceVision Algorithms: Theory and Practice
469 Citations2000Bill Triggs, Richard Szeliski +1 more
This paper proposes an experimental comparison of several different stereo algorithms, using real imagery, and explores two different methodologies, with different strengths and weaknesses.
Stereo from uncalibrated cameras
432 Citations2003Richard Hartley, Rajiv Gupta +1 more
The problem of computing placement of points in 3-D space, given two uncalibrated perspective views, is considered and it is possible to determine projective invariants of3-D geometric configurations from two perspective views.
IEEE Transactions on Pattern Analysis and Machine IntelligenceLinear pushbroom cameras
417 Citations1997Rajiv Kumar Gupta, Richard Hartley
Lecture notes in computer scienceAutomatic camera recovery for closed or open image sequences
397 Citations1998Andrew Fitzgibbon, Andrew Zisserman
Progress in completely automatically recovering 3D scene structure together with 3D camera positions from a sequence of images acquired by an unknown camera undergoing unknown movement is described.
Close range photogrammetry and machine vision
390 Citations1996K. B. Atkinson
Theory of close-range photogrammetry, M.A.R. Cooper and S. Robson fundamentals of digital photograms, and El-Hakim least squares matching - a fundamental measurement algorithm.
SIAM Journal on Scientific and Statistical ComputingA Stable and Efficient Algorithm for Nonlinear Orthogonal Distance Regression
366 Citations1987Paul T. Boggs, Richard H. Byrd +1 more
This paper describes a method for solving the orthogonal distance regression problem that is a direct analog of the trust region Levenberg-Marquardt algorithm, and proves the algorithm to be globally and locally convergent, and performs computational tests that illustrate some differences between ODR and OLS.
Lecture notes in computer scienceEuclidean reconstruction from uncalibrated views
346 Citations1994Richard Hartley
A practical algorithm for Euclidean reconstruction from several views with the same camera is given and is shown to behave very robustly in the presence of noise giving excellent calibration and reconstruction results.
The Photogrammetric RecordDIGITAL IMAGE CORRELATION: PERFORMANCE AND POTENTIAL APPLICATION IN PHOTOGRAMMETRY
280 Citations1984F. Ackermann
A procedure for digital image correlation is described which is based on least squares window matching and first results of calibration and performance of the system allow optimistic conclusions as to the further development and practical application of digital image processing in photogrammetry.
International Journal of Computer VisionLines and Points in Three Views and the Trifocal Tensor
278 Citations1997Richard Hartley
It is shown in this paper, that the trifocal tensor is essentially identical to a set of coefficients introduced by Shashua to effect point transfer in the three view case, which means that the 13-line algorithm may be extended to allow for the computation of the Trifocal Tensor given any mixture of sufficiently many line and point correspondences.
SIAM Journal on Numerical AnalysisOn the Rates of Convergence of the Lanczos and the Block-Lanczos Methods
239 Citations1980Yousef Saad
Theoretical error bounds are established, improving those given by S. Kaniel, and similar inequalities are found for the eigenvectors by using bounds on the acute angle between the exact eigenvesctors.
The Photogrammetric RecordBUNDLE ADJUSTMENT METHODS IN ENGINEERING PHOTOGRAMMETRY
238 Citations1980Stuart I. Granshaw
Adjustment Computations: Statistics and Least Squares in Surveying and GIS
233 Citations1987Paul R. Wolf, Charles D. Ghilani
User's reference guide for ODRPACK version 2.01:
207 Citations1992Paul T. Boggs, Richard H. Byrd +2 more
The algorithm implemented is an efficient and stable trust region Levenberg-Marquardt procedure that exploits the structure of the problem so that the computational cost per iteration is equal to that for the same type of algorithm applied to the nonlinear ordinary least squares problem.
Linear Algebra and its ApplicationsBehavior of slightly perturbed Lanczos and conjugate-gradient recurrences
156 Citations1989Anne Greenbaum
It is shown that the Chebyshev error bound holds (to a close approximation) for slightly perturbed conjugate-gradient recurrences, and that a sharper error bound can be expressed in terms of the minimax polynomial on a set of small intervals about the eigenvalues of the matrix.
On determining the fundamental matrix : analysis of different methods and experimental results
148 Citations1993Quang-Tuan Luong, Rachid Deriche +2 more
This paper defines precisely this matrix and shows clearly how it is related to the epipolar geometry and to the essential matrix introduced earlier by Longuet-Higgins, and shows that this matrix, defined up to a scale factor, must be of rank two.
SIAM Journal on Scientific ComputingImproving the Run Time and Quality of Nested Dissection Ordering
141 Citations1998Bruce Hendrickson, Edward Rothberg
An approach to the reordering problem that produces significantly better orderings than prior methods is described, a hybrid of nested dissection and minimum degree ordering, and combines an assortment of different algorithmic advances.
International Journal for Numerical Methods in EngineeringAn automatic reordering scheme for simultaneous equations derived from network systems
125 Citations1970Ian P. King
Computer Vision Graphics and Image ProcessingReliability analysis of parameter estimation in linear models with applications to mensuration problems in computer vision
123 Citations1987Wolfgang Förstner
Three examples, namely template matching and absolute and relative orientation of cameras, demonstrate that the measures make intuitive evaluation precise and that they seem to besuitable for automatic quality control of mensuration problems encountered in computer vision.
Die mathematischen und physikalischen Theorieen der hoheren Geodasie.
118 Citations1962Friedrich Robert. Helmert
A unified factorization algorithm for points, line segments and planes with uncertainty models
116 Citations2002Daniel Morris, Takeo Kanade
This formulation leads to a weighted least squares motion and shape recovery problem which is solved by an efficient quasi-linear algorithm and the statistical uncertainty model enables us to recover uncertainty estimates for the reconstructed three dimensional feature locations.
A unifying framework for structure and motion recovery from image sequences
114 Citations2002Philip F. McLauchlan, David W. Murray
A statistical framework that enables 3D structure and motion to be computed optimally from an image sequence, on the assumption that feature measurement errors are independent and Gaussian distributed is proposed.
Mathematics of ComputationMethods for Modifying Matrix Factorizations
102 Citations1974Philip E. Gill, Gene H. Golub +2 more
Linear Algebra and its ApplicationsLarge-scale geodetic least-squares adjustment by dissection and orthogonal decomposition
99 Citations1980Gene H. Golub, Robert J. Plemmons
It is shown how a block-orthogonal decomposition method can be used in conjunction with a nested dissection scheme to produce an algorithm for solving very large scale matrix problems which combines efficient data management with numerical stability.
SIAM Journal on Matrix Analysis and ApplicationsRobust Ordering of Sparse Matrices using Multisection
91 Citations1998Cleve Ashcraft, Joseph W. H. Liu
A robust reordering scheme for sparse matrices relies on the notion of multisection, a generalization of bisection, to have consistently good performance in terms of fill reduction when compared with multiple minimum degree and generalized nested dissection.
Journal of GeodesyReducing the profile of sparse symmetric matrices
58 Citations1976Richard A. Snay
Tests on normal equation matrices encountered in adjustments of geodetic networks by least squares demonstrate that the algorithm produces significantly lower profiles than the widely used reverse Cuthill-McKee algorithm.
IEEE Transactions on Pattern Analysis and Machine IntelligenceActive camera calibration for a head-eye platform using the variable state-dimension filter
54 Citations1996Philip F. McLauchlan, David W. Murray
A new technique for calibrating a camera mounted on a controllable head/eye platform that uses the trajectories of an arbitrary number of tracked corner features to improve the calibration parameter estimates over time, utilizing a novel variable state dimension form of recursive filter.
A batch/recursive algorithm for 3D scene reconstruction
47 Citations2002Philip F. McLauchlan
The main theoretical advance here is showing how to adjust the system information matrix when scene/camera parameters are removed from the reconstruction, and thus how to achieve an efficient recursive solution to the reconstruction problem.
Linear Algebra and its ApplicationsHouseholder reflections versus givens rotations in sparse orthogonal decomposition
44 Citations1987Alan D. George, Joseph W. H. Liu
The Photogrammetric RecordSTATISTICAL CONCEPTS AND THEIR APPLICATION IN PHOTOGRAMMETRY AND SURVEYING
43 Citations1988M. A. R. Cooper, Paul Cross
The following topics are covered: functional and stochastic models; the least squares process; statistical testing; optimal design methods; and numerical examples in the design of a horizontal control network and of a close range photogrammetric survey.
Efficient iterative solution to M-view projective reconstruction problem
42 Citations2003Qian Chen, Gérard Medioni
An efficient solution to the general M-view projective reconstruction problem, using matrix factorization and iterative least squares, which runs much faster than the often-used non-linear minimization method, while preserving the accuracy of the latter.
Lecture notes in computer scienceUncertainty Modeling for Optimal Structure from Motion
41 Citations2000Daniel Morris, Kenichi Kanatani +1 more
A Geometric Equivalence Relationship is derived with which covariances under different parametrizations and gauges can be compared, based on their true geometric uncertainty, and it is shown that the uncertainty of gauge invariants exactly captures the geometric uncertainty of the solution, and hence provides useful measures for evaluating the uncertaintyof the solution.
Bayesian structure from motion
40 Citations1999David Forsyth, Sergey Ioffe +1 more
This workulates structure from motion as a Bayesian inference problem and uses a Markov-chain Monte Carlo sampler to sample the posterior on this problem, resulting in a method that can identify both small and large tracker errors and yields reconstructions that are stable in the presence of these errors.
The Cubic Rational Polynomial Camera Model
40 Citations2001Richard Hartley, Tushar Saxena
It is empirically demonstrated that a SAR sensor is very accurately approximated by a cubic camera, but not by any linear camera model, and an algorithm for estimating the parameters of the cubic camera is outlined, given a set of image to world correspondences.
ISPRS Journal of Photogrammetry and Remote SensingExpert system-based design of close-range photogrammetric networks
37 Citations1995Scott Mason
Investigations into the feasibility of an expert system solution to the automation of high-accuracy photogrammetric measurement in industrial applications report on recommendations for the representation of network design expertise, network topology and spatial information, and the appropriate architecture for an expertSystem-based tool.
SIAM Journal on Scientific and Statistical ComputingA Comparison of Some Methods for Solving Sparse Linear Least-Squares Problems
36 Citations1983Alan D. George, Michael T. Heath +1 more
Numerical experiments show that the method of normal equations should be considered when the observation matrix is sparse and well conditioned, and for ill-conditioned problems, the algorithm based on Givens rotations is preferable.
Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIEAdaptive Least Squares Correlation With Geometrical Constraints
32 Citations1986Armin Gruen, Emmanuel P. Baltsavias
Lecture notes in computer scienceOptimal Estimation of Matching Constraints
29 Citations1998Bill Triggs
A numerical library for estimating multi-image matching constraints, or more precisely the multi-camera geometry underlying them, designed to be modular and open-ended, so that new feature types or error models, new constraint types or parametrizations, and new numerical resolution methods are relatively easy to add.
Gauge invariance in projective 3D reconstruction
28 Citations2003Philip F. McLauchlan
It is shown that a simple pre-conditioning step removes the effect of the choice of coordinate frame, and together with a set of enforced constraints on the reconstruction, achieves along with this invariance greatly increased convergence speed over existing methods.
ISPRS Journal of Photogrammetry and Remote SensingThe photogrammetric inner constraints
27 Citations1994Athanasios Dermanis
Lecture notes in computer scienceDirect Recovery of Planar-Parallax from Multiple Frames
25 Citations2000Michal Irani, P. Anandan +1 more
Lecture notes in computer scienceGauge Independence in Optimization Algorithms for 3D Vision
22 Citations2000Philip F. McLauchlan
A bundle adjustment algorithm is formulated whose results are independent of both the coordinate frame chosen to represent the scene and the ordering of the images, which is more efficient that existing approaches to the problem in photogrammetry.
Motion estimation with quadtree splines
20 Citations2002Richard Szeliski, Heung‐Yeung Shum
This paper presents a motion estimation algorithm based on a new multiresolution representation, the quadtree spline, which combines the advantages of adaptively-sized correlation windows with the speedups obtained with hierarchical basis preconditioners.
A parallel feature tracker for extended image sequences
17 Citations2002Richard Szeliski, Sing Bing Kang +1 more
This paper presents a feature tracker for long image sequences based on simultaneously estimating die motions and deformations of a collection of adjacent image patches that achieve greater stability than independent patch trackers by sharing common corner nodes.
Lecture notes in computer scienceShape ambiguities in structure from motion
15 Citations1996Richard Szeliski, Sing Bing Kang
The Photogrammetric RecordTHE ADJUSTMENT OF AERIAL TRIANGULATION BY ELECTRONIC DIGITAL COMPUTERS
12 Citations1962D. W. Proctor
The trials suggest considerable economy without loss of accuracy when compared with the Jerie Analogue Computer at present in use.
The Canadian SurveyorLinear Least-Squares Computations Using Givens Transformations
11 Citations1983J. A. R. Blais
The Photogrammetric RecordSTATISTICAL CONCEPTS AND THEIR APPLICATION IN PHOTOGRAMMETRY AND SURVEYING (CONTINUED)
11 Citations1991M. A. R. Cooper, Paul Cross
A New Approach to Geometric Fitting
10 Citations1996Bill Triggs
This paper describes a new, more direct approach to geometric fitting, formulating it as the explicit recovery of a coherent, statistically optimal set of estimates of the “underlying data points” that gave rise to the observations, together with the estimated constraints which these points exactly verify.
PhotogrammetriaTest of algorithms for sequential adjustment in online phototriangulation
6 Citations1989Knut Ragnar Holm
In the test, the Givens transformations algorithm appears to be up to four times faster than the Triangular Factor Update for updating the factorized normal equation system.
Lecture notes in computer scienceOptimal robot self-localization and reliability evaluation
5 Citations1998Kenichi Kanatani, Naoya Ohta
This work discusses optimal estimation of the current location of a robot by matching an image of the scene taken by the robot with the model of the environment and gives a method that attains that bound.
An object-oriented approach to scene reconstruction
5 Citations2002Richard Hartley
A program is described for carrying out least-squares camera modelling and scene reconstruction from a set of image and scene measurements of geometric features, easily extendible to include very general types of camera, image feature or measurement.
Journal of GeodesyA comparative study of algorithms for reducing the fill-in during Cholesky factorization
4 Citations1992Paul J. de Jonge
The results show that ordering the unknowns yields a considerable decrease of the cpu time for computing the Cholesky factor, and that in general the minimum degree and Snay's banker's ordering perform best.
City Research Online (City University London)Separate adjustment of close range photogrammetric measurements
3 Citations1998Wang, X.
…