Bundle adjustment
Encyclopedia
Stereoscopy
Stereoscopy refers to a technique for creating or enhancing the illusion of depth in an image by presenting two offset images separately to the left and right eye of the viewer. Both of these 2-D offset images are then combined in the brain to give the perception of 3-D depth...
, bundle adjustment can be defined as the problem of simultaneously refining the 3D coordinates
Coordinate system
In geometry, a coordinate system is a system which uses one or more numbers, or coordinates, to uniquely determine the position of a point or other geometric element. The order of the coordinates is significant and they are sometimes identified by their position in an ordered tuple and sometimes by...
describing the scene geometry as well as the parameters of the relative motion and the optical characteristics of the camera(s) employed to acquire the images, according to an optimality criterion involving the corresponding
Correspondence problem
The correspondence problem tries to figure out which parts of an image correspond to which parts of another image, after the camera has moved, time has elapsed, and/or the objects have moved around.-Overview:...
image projections of all points.
Bundle adjustment is almost always used as the last step of every feature-based 3D reconstruction algorithm. It amounts to an optimization problem on the 3D structure and viewing parameters (i.e., camera pose
Pose (computer vision)
In computer vision and in robotics, a typical task is to identify specific objects in an image and to determine each object's position and orientation relative to some coordinate system. This information can then be used, for example, to allow a robot to manipulate an object or to avoid moving...
and possibly intrinsic calibration and radial distortion), to obtain a reconstruction which is optimal under certain assumptions regarding the noise pertaining to the observed image features: If the image error is zero-mean Gaussian
Gaussian noise
Gaussian noise is statistical noise that has its probability density function equal to that of the normal distribution, which is also known as the Gaussian distribution. In other words, the values that the noise can take on are Gaussian-distributed. A special case is white Gaussian noise, in which...
, then bundle adjustment is the Maximum Likelihood Estimator
Maximum likelihood
In statistics, maximum-likelihood estimation is a method of estimating the parameters of a statistical model. When applied to a data set and given a statistical model, maximum-likelihood estimation provides estimates for the model's parameters....
. Its name refers
to the bundles
Bundle (mathematics)
In mathematics, a bundle is a generalization of a fiber bundle dropping the condition of a local product structure. The requirement of a local product structure rests on the bundle having a topology. Without this requirement, more general objects can be considered bundles. For example, one can...
of light rays originating from each 3D feature and converging on each camera's
Pinhole camera model
The pinhole camera model describes the mathematical relationship between the coordinates of a 3D point and its projection onto the image plane of an ideal pinhole camera, where the camera aperture is described as a point and no lenses are used to focus light...
optical center, which are adjusted optimally with respect to both the structure and viewing parameters. Bundle adjustment was originally conceived in the field of photogrammetry
Photogrammetry
Photogrammetry is the practice of determining the geometric properties of objects from photographic images. Photogrammetry is as old as modern photography and can be dated to the mid-nineteenth century....
during 1950s and has increasingly been used by computer vision
Computer vision
Computer vision is a field that includes methods for acquiring, processing, analysing, and understanding images and, in general, high-dimensional data from the real world in order to produce numerical or symbolic information, e.g., in the forms of decisions...
researchers during recent years.
Bundle adjustment boils down to minimizing the reprojection error between the image locations of
observed and predicted image points, which is expressed as the sum of squares of a large number of nonlinear, real-valued functions. Thus, the minimization is achieved using nonlinear least-squares algorithms. Of these, Levenberg–Marquardt has proven to be one of the most successful due to its ease of implementation and its use of an effective damping strategy that lends it the ability to converge quickly from a wide range of initial guesses. By iteratively linearizing the function to be minimized in the neighborhood of the current estimate, the Levenberg–Marquardt algorithm involves the solution of linear systems known as the normal equations. When solving the minimization problems arising in the framework of
bundle adjustment, the normal equations have a sparse
Sparse matrix
In the subfield of numerical analysis, a sparse matrix is a matrix populated primarily with zeros . The term itself was coined by Harry M. Markowitz....
block structure owing to the lack of interaction among parameters for different 3D points and cameras. This can be exploited to gain tremendous computational benefits by employing a sparse variant of the Levenberg–Marquardt algorithm which explicitly takes advantage of the normal equations zeros pattern, avoiding storing and operating on zero elements.
Mathematical definition
Bundle adjustment amounts to jointly refining a set of initial camera and structure parameter estimates for finding the set of parameters that most accurately predict the locations of the observed points in the set of available images. More formally, assume that
3D points are seen in 
views and let 
be the projection of the 
th point on image 
. Let 
denote the binary variables that equal 1 if point 
is visible in image 
and 0 otherwise. Assume also that each camera 
is parameterized by a vector 
and each 3D point 
by a vector 
. Bundle adjustment minimizes the total reprojection error with respect to all 3D point and camera parameters, specifically
where
is the predicted projectionCamera matrix
In computer vision a camera matrix or projection matrix is a 3 \times 4 matrix which describes the mapping of a pinhole camera from 3D points in the world to 2D points in an image....
of point
on image 
and 
denotes the Euclidean distance between the image points represented by vectors 
and 
. Clearly, bundle adjustment is by definition tolerant to missing image projections and minimizes a physically meaningful criterion.Software
- sba: A Generic Sparse Bundle Adjustment C/C++ Package Based on the Levenberg–Marquardt Algorithm (CC (programming language)C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
, MatlabMATLABMATLAB is a numerical computing environment and fourth-generation programming language. Developed by MathWorks, MATLAB allows matrix manipulations, plotting of functions and data, implementation of algorithms, creation of user interfaces, and interfacing with programs written in other languages,...
) - ssba: Simple Sparse Bundle Adjustment package based on the Levenberg–Marquardt Algorithm (CC (programming language)C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
) with LGPL license. - OpenCv: Computer Vision library in the contrib module.
- mcba: Multi-Core Bundle Adjustment (CPU/GPU).
See also
- PhotogrammetryPhotogrammetryPhotogrammetry is the practice of determining the geometric properties of objects from photographic images. Photogrammetry is as old as modern photography and can be dated to the mid-nineteenth century....
- StereoscopyStereoscopyStereoscopy refers to a technique for creating or enhancing the illusion of depth in an image by presenting two offset images separately to the left and right eye of the viewer. Both of these 2-D offset images are then combined in the brain to give the perception of 3-D depth...
- Levenberg–Marquardt algorithm
- Sparse matrixSparse matrixIn the subfield of numerical analysis, a sparse matrix is a matrix populated primarily with zeros . The term itself was coined by Harry M. Markowitz....
- Collinearity equationCollinearity equationThe collinearity equation is used in photogrammetry and remote sensing to relate coordinates in a sensor plane to object coordinates ....