Bundle adjustment


Bundle adjustment



right|thumb|A sparse matrix obtained when solving a modestlysized bundle adjustment problem. This is the sparsity pattern of a 992x992 normal equations(i.e. approximate Hessian) matrix. Black regions correspond to nonzero blocks.Given a set of images depicting a number of 3D points from different viewpoints,bundle adjustment can be defined as the problem of simultaneously refining the 3D
coordinates describing the scene geometry as well as the parameters ofthe relative motion and the optical characteristics of the camera(s) employed to acquire theimages, according to an optimality criterion involving the correspondingimage 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 and possibly intrinsic calibration and radial distortion),to obtain a reconstruction which is optimal under certain assumptions regarding the noisepertaining to the observed image features: If the image error is zero-mean Gaussian,then bundle adjustment is the Maximum Likelihood Estimator. Its name refersto the "bundles" of light rays originating from each 3D feature and converging on each camera'soptical center, which are adjusted optimally with respect to both the structure and viewing parameters.Bundle adjustment was originally conceived in the field of photogrammetry during 1950s andhas increasingly been used by computer vision 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 ofnonlinear, real-valued functions. Thus, the minimization is achieved using nonlinear least-squares algorithms,from which Levenberg-Marquardt has proven to be one of the most successful due to its ease of implementationand its use of an effective damping strategy that lends it the ability to converge quickly from awide 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 equationshave a sparse block structure owing to the lack of interaction among parameters for different3D points and cameras. This can be exploited to gain tremendous computational benefits by employing a sparsevariant of the Levenberg-Marquardt algorithm which explicitly takes advantage of the normal equationszeros pattern, avoiding storing and operating on zero elements.

Mathematical definition

Bundle adjustment amounts to jointly refining a set of initial camera and structure parameter estimatesfor finding the set of parameters that most accurately predict the locations of the observed points inthe set of available images. More formally, assume that n 3D points are seen in mviews and let mathbf{x}_{ij} be the projection of the i-th point on imagej. Let displaystyle v_{ij} denote the binary variables that equal 1 if pointi is visible in image j and 0 otherwise. Assume also that each cameraj is parameterized by a vector mathbf{a}_j and each 3D point iby a vector mathbf{b}_i. Bundle adjustment minimizes the total reprojection error withrespect to all 3D point and camera parameters, specifically

:min_{mathbf{a}_j, , mathbf{b}_i} displaystylesum_{i=1}^{n} ; displaystylesum_{j=1}^{m} ; v_{ij} , d(mathbf{Q}(mathbf{a}_j, , mathbf{b}_i), ; mathbf{x}_{ij})^2,

where mathbf{Q}(mathbf{a}_j, , mathbf{b}_i) is the predicted projectionof point i on image j and d(mathbf{x}, , mathbf{y})denotes the Euclidean distance between the image points represented by vectors mathbf{x}and mathbf{y}. Clearly, bundle adjustment is by definition tolerant to missing imageprojections and minimizes a physically meaningful criterion.

References

* cite conference
title=Bundle Adjustment — A Modern Synthesis
author=B. Triggs
coauthors=P. McLauchlan and R. Hartley and A. Fitzgibbon
booktitle=ICCV '99: Proceedings of the International Workshop on Vision Algorithms
pages=298-372 | id=ISBN 3-540-67973-1
publisher=Springer-Verlag
year=1999

*cite book
author=R.I. Hartley and A. Zisserman
title=Multiple View Geometry in computer vision
publisher=Cambridge University Press
edition=2nd ed.
year=2004
id=ISBN 0521540518

ee also

*Photogrammetry
*Stereoscopy
*Levenberg-Marquardt algorithm
*Sparse matrix

External links

* [http://lear.inrialpes.fr/pubs/2000/TMHF00/Triggs-va99.pdf B. Triggs, P. McLauchlan, R. Hartley and A. Fitzgibbon, "Bundle Adjustment — A Modern Synthesis", Vision Algorithms: Theory and Practice, 1999]
* [http://www.ics.forth.gr/~lourakis/sba/ M. Lourakis, "sba: A Generic Sparse Bundle Adjustment C/C++ Package Based on the Levenberg-Marquardt Algorithm", 2004]


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Scale-invariant feature transform — Feature detection Output of a typical corner detection algorithm …   Wikipedia

  • Photogrammetry — is the first remote sensing technology ever developed, in which geometric properties about objects are determined from photographic images. Historically, photogrammetry is as old as modern photography itself, and can be dated to mid nineteenth… …   Wikipedia

  • SCBA (disambiguation) — SCBA refers to: *Types of breathing apparatus: **Self contained breathing apparatus, but usually not for sets used underwater. **Two types of naval diving rebreather which Siebe Gorman in England used to make: ***Swimmer Canoeist s Breathing… …   Wikipedia

  • List of computer vision topics — This is a list of computer vision and image processing topics Contents 1 Image enhancement 2 Transformations 3 Filtering, Fourier and wavelet transforms and image compression …   Wikipedia

  • Microsoft Live Labs Photosynth — Infobox Software name = Microsoft Live Labs Photosynth caption = Photosynth technology preview showing Piazza San Pietro, Rome developer = Microsoft latest release version = 2.0.1403.12 latest release date = release date and age|2008|09|08 latest …   Wikipedia

  • Structured Light 3D Scanner — Principle Projecting a narrow band of light onto a three dimensionally shaped surface produces a line of illumination that appears distorted from other perspectives than that of the projector, and can be used for an exact geometric reconstruction …   Wikipedia

  • Visual odometry — In robotics and computer vision, visual odometry is the process of determining the position and orientation of a robot by analyzing the associated camera images. It has been used in a wide variety of robotic applications, such as on the Mars… …   Wikipedia

  • Фотограмметрия — (от фото..., др. греч. γράμμα запись, изображение и ... метрия) технология дистанционного зондирования Земли, позволяющая определять геометрические, количественные и другие свойства объектов на поверхности земли по фотографическим изображениям,… …   Википедия

  • Collinearity equation — The collinearity equation is used in photogrammetry and remote sensing to relate coordinates in a sensor plane (in two dimensions) to object coordinates (in three dimensions). The most obvious use of these equations is for images recorded by a… …   Wikipedia

  • Photosynth — This article is about the software application. For the action of plants, see photosynthesis. Microsoft Photosynth …   Wikipedia