Bundle Adjustment

Bundle adjustment's defining feature is its simultaneous refinement of all unknown parameters in a reconstruction system. Unlike sequential methods, it optimizes:

• 3D point coordinates (the 'structure')
• Camera poses (extrinsic parameters: rotation and translation)
• Camera intrinsics (focal length, principal point, distortion coefficients)

This joint approach minimizes error propagation and yields a globally consistent solution where all parameters are mutually informed by the entire dataset.

The objective function of bundle adjustment is the sum of squared reprojection errors. For each observed 2D image feature, the error is the Euclidean distance between its actual location and where the current 3D point estimate projects onto the image plane given the current camera parameters.

The optimization aims to find the parameter set that minimizes this total error, formally a non-linear least squares problem. This geometric cost function is directly tied to the observable data, making it physically meaningful and robust.

The Jacobian matrix in the bundle adjustment least-squares system exhibits a block-sparse structure. This arises because each 3D point is observed by only a subset of cameras, and each camera sees only a subset of points.

This sparsity is exploited via the Schur Complement Trick (or Marginalization), which allows for efficient solving by first eliminating the 3D point parameters. This reduces a massive, dense problem into a much smaller, manageable system involving only camera parameters, enabling the reconstruction of large-scale scenes from thousands of images.

Bundle adjustment problems are solved iteratively using non-linear optimization algorithms. The Levenberg-Marquardt algorithm is the industry standard, as it effectively interpolates between:

• Gradient Descent (stable when far from the minimum)
• Gauss-Newton (fast convergence when near the minimum)

It requires computing the Jacobian (partial derivatives of reprojection errors) and approximating the Hessian matrix. The algorithm's adaptive damping parameter ensures robust convergence from poor initial estimates, which are common in structure-from-motion pipelines.

Real-world image data contains mismatches and noise. Standard least squares is highly sensitive to these outliers. Therefore, practical bundle adjustment implementations incorporate robust cost functions (or loss functions).

Common choices include:

• Huber Loss: Lessens the influence of moderate outliers.
• Cauchy Loss: Strongly down-weights severe outliers.

These functions replace the squared error term, preventing a few bad correspondences from corrupting the entire reconstruction. This is often combined with pre-filtering using algorithms like RANSAC.

For a set of images with unknown intrinsics, the reconstruction solved by bundle adjustment has an inherent scale ambiguity—the entire scene and camera motions can be scaled arbitrarily while producing the same 2D projections.

This is part of a broader gauge freedom, meaning the problem has seven degrees of freedom that do not affect the reprojection error: three for translation, three for rotation, and one for scale. The solution is therefore defined only up to a similarity transformation (rotation, translation, scale). To obtain a unique solution, gauge constraints (or gauge fixation) must be applied, such as fixing the pose of one camera.

Structure from Motion (SfM) is the overarching photogrammetry pipeline for reconstructing 3D scenes from 2D images. It is the primary application domain for bundle adjustment.

• Pipeline Stages: Typically involves feature detection, matching, geometric verification (e.g., using the Fundamental Matrix), initial pose estimation (e.g., Perspective-n-Point), sparse Triangulation, and finally, Bundle Adjustment for joint refinement.
• Output: Produces a sparse 3D point cloud and the estimated camera poses for each input image.
• Key Difference: SfM is the full pipeline; bundle adjustment is the critical optimization subroutine within it that minimizes global error.

Reprojection error is the scalar cost function that bundle adjustment minimizes. It measures the discrepancy between observed features and predicted projections.

• Calculation: For a 3D point (X) and camera with pose (P), the reprojection error is the Euclidean distance in the image plane between the observed 2D point (x) and the projected point (P(X)).
• Role in BA: The total non-linear least squares problem solved by bundle adjustment is the sum of squared reprojection errors across all cameras and points.
• Significance: A low average reprojection error (e.g., < 0.5 pixels) indicates a highly consistent and accurate reconstruction.

Perspective-n-Point (PnP) is the problem of estimating the pose of a calibrated camera given a set of n 3D-to-2D point correspondences. It provides initial poses for bundle adjustment.

• Minimal Solutions: Requires a minimum of 3 points (P3P) for a finite number of solutions. Direct Linear Transform (DLT) can be used for n≥6.
• Robust Variants: Often solved robustly using RANSAC to handle outlier correspondences before refinement.
• Relationship to BA: PnP solves for a single camera pose given known 3D points. Bundle adjustment jointly refines many camera poses and the 3D points themselves.

Triangulation is the process of computing the 3D coordinates of a point given its 2D projections in two or more images and the known poses of the cameras. It creates the initial 3D structure refined by bundle adjustment.

• Linear Methods: Can be solved via Singular Value Decomposition (SVD) of a system built from camera projection matrices.
• Midpoint Method: A common approach finds the point that minimizes the distance to the back-projected rays from each camera.
• Noise Sensitivity: Triangulation is highly sensitive to noise in camera poses and pixel measurements, which is why the initial triangulated points are imprecise and require the global optimization of bundle adjustment.

The Levenberg-Marquardt (LM) algorithm is the standard non-linear least squares optimizer used to solve the bundle adjustment problem due to its efficiency and robustness.

• Hybrid Approach: Interpolates between Gradient Descent (stable but slow) and the Gauss-Newton method (fast near the minimum).
• Sparsity Exploitation: The Jacobian matrix in bundle adjustment is highly sparse (each point affects only cameras that see it). LM implementations (e.g., in Ceres Solver, g2o) use sparse linear algebra (like Cholesky decomposition) for solving the normal equations, enabling optimization of very large problems (thousands of cameras, millions of points).

Visual Odometry (VO) and Simultaneous Localization and Mapping (SLAM) are real-time, sequential counterparts to offline SfM. They use local bundle adjustment (often called local BA or windowed BA).

• Visual Odometry: Estimates incremental camera motion. Often uses a sliding window of recent frames where bundle adjustment refines the poses and map points within that window.
• Visual-Inertial Odometry (VIO): Fuses camera data with IMU measurements. Bundle adjustment cost functions are extended to include IMU prediction error terms.
• Full SLAM vs. Front-end: In SLAM systems like ORB-SLAM, a global bundle adjustment may run in a separate thread to periodically refine the entire map and trajectory.