In
photogrammetry
Photogrammetry is the science and technology of obtaining reliable information about physical objects and the environment through the process of recording, measuring and interpreting photographic images and patterns of electromagnetic radiant ima ...
and
computer stereo vision
Computer stereo vision is the extraction of 3D information from digital images, such as those obtained by a CCD camera. By comparing information about a scene from two vantage points, 3D information can be extracted by examining the relative positi ...
, bundle adjustment is simultaneous refining of the 3D
coordinates
In geometry, a coordinate system is a system that uses one or more numbers, or coordinates, to uniquely determine the position of the points or other geometric elements on a manifold such as Euclidean space. The order of the coordinates is sig ...
describing the scene geometry, the parameters of the relative motion, and the optical characteristics of the camera(s) employed to acquire the images, given a set of images depicting a number of 3D points from
different viewpoints.
Its name refers to the ''
geometrical bundles'' of
light ray
In optics a ray is an idealized geometrical model of light, obtained by choosing a curve that is perpendicular to the ''wavefronts'' of the actual light, and that points in the direction of energy flow. Rays are used to model the propagation o ...
s originating from each 3D feature and converging on each
camera's optical center, which are adjusted optimally according to an optimality criterion involving the
corresponding image projections of all points.
Uses
Bundle adjustment is almost always used as the last step of every feature-based
3D reconstruction
In computer vision and computer graphics, 3D reconstruction is the process of capturing the shape and appearance of real objects.
This process can be accomplished either by active or passive methods. If the model is allowed to change its shape ...
algorithm. It amounts to an optimization problem on the 3D structure and viewing parameters (i.e., camera
pose 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
Carl Friedrich Gauss (1777–1855) is the eponym of all of the topics listed below.
There are over 100 topics all named after this German mathematician and scientist, all in the fields of mathematics, physics, and astronomy. The English eponym ...
, then bundle adjustment is the
Maximum Likelihood Estimator
In statistics, maximum likelihood estimation (MLE) is a method of estimating the parameters of an assumed probability distribution, given some observed data. This is achieved by maximizing a likelihood function so that, under the assumed statis ...
.
Bundle adjustment was originally conceived in the field of
photogrammetry
Photogrammetry is the science and technology of obtaining reliable information about physical objects and the environment through the process of recording, measuring and interpreting photographic images and patterns of electromagnetic radiant ima ...
during the 1950s and has increasingly been used by
computer vision
Computer vision is an interdisciplinary scientific field that deals with how computers can gain high-level understanding from digital images or videos. From the perspective of engineering, it seeks to understand and automate tasks that the human ...
researchers during recent years.
General approach
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
The method of least squares is a standard approach in regression analysis to approximate the solution of overdetermined systems (sets of equations in which there are more equations than unknowns) by minimizing the sum of the squares of the res ...
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 termed the
normal equations
In statistics, ordinary least squares (OLS) is a type of linear least squares method for choosing the unknown statistical parameter, parameters in a linear regression model (with fixed level-one effects of a linear function of a set of explanatory ...
. When solving the minimization problems arising in the framework of
bundle adjustment, the normal equations have a
sparse 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
projection of point
on image
and
denotes the Euclidean distance between the image points represented by vectors
and
. Because the minimum is computed over many points and many images, bundle adjustment is by definition tolerant to missing image projections, and if the distance metric is chosen reasonably (e.g., Euclidean distance), bundle adjustment will also minimize a physically meaningful criterion.
See also
*
Adjustment of observations Least-squares adjustment is a model for the solution of an overdetermined system of equations based on the principle of least squares of observation residuals. It is used extensively in the disciplines of surveying, geodesy, and photogrammetry—th ...
*
Stereoscopy
Stereoscopy (also called stereoscopics, or stereo imaging) is a technique for creating or enhancing the illusion of depth in an image by means of stereopsis for binocular vision. The word ''stereoscopy'' derives . Any stereoscopic image i ...
*
Levenberg–Marquardt algorithm
In mathematics and computing, the Levenberg–Marquardt algorithm (LMA or just LM), also known as the damped least-squares (DLS) method, is used to solve non-linear least squares problems. These minimization problems arise especially in least sq ...
*
Sparse matrix
In numerical analysis and scientific computing, a sparse matrix or sparse array is a matrix in which most of the elements are zero. There is no strict definition regarding the proportion of zero-value elements for a matrix to qualify as sparse b ...
*
Collinearity equation
The collinearity equations are a set of two equations, used in photogrammetry and computer stereo vision, to relate coordinates in a sensor plane (in two dimensions) to object coordinates (in three dimensions). The equations originate from the ...
*
Structure from motion
Structure from motion (SfM) is a photogrammetric range imaging technique for estimating three-dimensional structures from two-dimensional image sequences that may be coupled with local motion signals. It is studied in the fields of computer visio ...
*
Simultaneous localization and mapping
Simultaneous localization and mapping (SLAM) is the computational problem of constructing or updating a map of an unknown environment while simultaneously keeping track of an agent's location within it. While this initially appears to be a chi ...
References
Further reading
* A. Zisserman
Bundle adjustment CV Online.
External links
Software
{{see also, Photogrammetry software, Structure from motion#Software
Apero/MicMac, a free open source photogrammetric software. Cecill-B licence.
sba A Generic Sparse Bundle Adjustment C/C++ Package Based on the Levenberg–Marquardt Algorithm (
C (programming language), C,
MATLAB
MATLAB (an abbreviation of "MATrix LABoratory") is a proprietary multi-paradigm programming language and numeric computing environment developed by MathWorks. MATLAB allows matrix manipulations, plotting of functions and data, implementat ...
). GPL.
cvsba An OpenCV wrapper fo
sbalibrary (
C++
C++ (pronounced "C plus plus") is a high-level general-purpose programming language created by Danish computer scientist Bjarne Stroustrup as an extension of the C programming language, or "C with Classes". The language has expanded significan ...
). GPL.
ssba Simple Sparse Bundle Adjustment package based on the Levenberg–Marquardt Algorithm (C++). LGPL.
OpenCV Computer Vision library in th
module. BSD license.
mcba Multi-Core Bundle Adjustment (CPU/GPU). GPL3.
libdogleg General-purpose sparse non-linear least squares solver, based on Powell's dogleg method. LGPL.
ceres-solver A Nonlinear Least Squares Minimizer. BSD license.
General Graph Optimization (C++) - framework with solvers for sparse graph-based non-linear error functions. LGPL.
The program DGAP implement the photogrammetric method of bundle adjustment invented by Helmut Schmid and Duane Brown. GPL.
Bundler A structure-from-motion (SfM) system for unordered image collections (for instance, images from the Internet) by Noah Snavely. GPL.
COLMAP A general-purpose Structure-from-Motion (SfM) and Multi-View Stereo (MVS) pipeline with a graphical and command-line interface. BSD license.
Theia A computer vision library aimed at providing efficient and reliable algorithms for Structure from Motion (SfM). New BSD license.
*
Ames Stereo Pipeline The NASA Ames Stereo Pipeline (ASP) is an open-source software package for photogrammetry. It can create digital elevation models and ortho images from stereo planetary data acquired with NASA spacecraft, including for the Moon, Mars, and all ot ...
has a tool for bundle adjustment (Apache II licence).
Geometry in computer vision
Geodesy
Photogrammetry
Surveying
Cartography