Bundle adjustment

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 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. 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 ${\displaystyle n}$ 3D points are seen in ${\displaystyle m}$ views and let ${\displaystyle {\mathbf{x}}_{ij}}$ be the projection of the ${\displaystyle i}$th point on image ${\displaystyle j}$. Let ${\displaystyle {\displaystyle v_{ij}}}$ denote the binary variables that equal 1 if point ${\displaystyle i}$ is visible in image ${\displaystyle j}$ and 0 otherwise. Assume also that each camera ${\displaystyle j}$ is parameterized by a vector ${\displaystyle {\mathbf{a}}_j}$ and each 3D point ${\displaystyle i}$ by a vector ${\displaystyle {\mathbf{b}}_i}$. Bundle adjustment minimizes the total reprojection error with respect to all 3D point and camera parameters, specifically

${\displaystyle \underset{{\mathbf{a}}_j,{\mathbf{b}}_i}{min}{\displaystyle \sum _{i=1}^n{\displaystyle \sum _{j=1}^m{v}_{ij}d(\mathbf{Q}({\mathbf{a}}_j,{\mathbf{b}}_i),{\mathbf{x}}_{ij}{)}^2,}}}$

where ${\displaystyle \mathbf{Q}({\mathbf{a}}_j,{\mathbf{b}}_i)}$ is the predicted projection of point ${\displaystyle i}$ on image ${\displaystyle j}$ and ${\displaystyle d(\mathbf{x},\mathbf{y})}$ denotes the Euclidean distance between the image points represented by vectors ${\displaystyle \mathbf{x}}$ and ${\displaystyle \mathbf{y}}$. 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.