Bundle Adjustment

Bundle adjustment's defining feature is its simultaneous refinement of all unknown parameters. It does not alternate between fixing camera poses to update 3D points and vice-versa. Instead, it optimizes a single, unified cost function over the complete parameter vector θ = [P1, P2, ..., Pm, X1, X2, ..., Xn], where P represents camera parameters (extrinsic pose and often intrinsic calibration) and X represents 3D point coordinates. This joint optimization correctly accounts for the coupling between all parameters, preventing error accumulation and sub-optimal solutions that plague sequential or decoupled methods.

The objective function is the sum of squared reprojection errors. For a 3D point X_j observed in camera i at pixel coordinates u_ij, the reprojection error is the difference between the observed pixel and the projected pixel: e_ij = u_ij - π(P_i, X_j), where π is the camera projection function. Bundle adjustment solves: θ = argmin_θ Σ_ij || e_ij ||^2*. This geometric error is statistically optimal under the assumption of Gaussian image noise. Minimizing this non-convex cost function requires iterative nonlinear optimization techniques like the Levenberg-Marquardt algorithm.

The Jacobian and Hessian matrices in bundle adjustment exhibit a highly sparse block structure due to the problem's topology: each 3D point is observed by only a few cameras. The Hessian H = J^T J has a block structure where off-diagonal blocks are zero if two parameters are not connected by a measurement. This enables the use of the Schur Complement Trick (or Marginalization). By ordering parameters as cameras then points, the linear system H δθ = -b can be partitioned and solved efficiently by first eliminating the 3D point parameters, solving a much smaller system only for camera parameters, and then back-substituting. This reduces complexity from O((m+n)^3) to roughly O(m^3 + m^2 n).

Real-world data contains outliers from incorrect feature matching, occlusions, or reflections. Using a standard squared-error loss (L2 norm) makes the optimization highly sensitive to these outliers. Therefore, robust M-estimators like Huber loss or Cauchy loss are employed. These functions reduce the influence of large residuals. The optimization often incorporates an iteratively reweighted least squares (IRLS) scheme, where weights are recomputed each iteration based on the current residuals. Advanced pipelines may integrate RANSAC at the front end for gross outlier removal before bundle adjustment refines the inliers.

Bundle adjustment suffers from gauge freedom: the cost function is invariant to certain transformations of the entire parameter set (e.g., a global translation, rotation, or scale). This makes the Hessian matrix singular. To obtain a unique solution, the problem must be gauge-fixed. Common approaches include:

• Anchor a subset: Fix the pose of one camera and the position of one 3D point.
• Use a prior: Add soft constraints (e.g., a weak prior on a camera's position).
• Use the Moore-Penrose pseudoinverse during linear solve. Proper parameterization is also critical, especially for camera rotation. Using quaternions or angle-axis representations avoids singularities present in Euler angles.

Bundle adjustment has two primary operational modes:

• Global (Full) Bundle Adjustment: Optimizes over all cameras and points in the entire dataset. This provides the most accurate result but is computationally expensive, typically used as a final refinement step in Structure-from-Motion (SfM).
• Incremental (Local) Bundle Adjustment: A key technique in visual SLAM systems. To maintain real-time performance, only a sliding window of recent camera poses and the points observed within them are optimized. Older states are marginalized out of the optimization window but their information is retained as a prior on the remaining states, a process formalized in sliding window filter approaches. This balances accuracy with computational tractability for online operation.

A factor graph is a bipartite graphical model that represents the factorization of a complex probability distribution. In robotics and computer vision, it provides the underlying data structure for bundle adjustment and SLAM problems.

• Nodes represent variables (e.g., 3D point positions, camera poses).
• Factors represent constraints or measurements (e.g., reprojection error of a 2D image feature).
• Solving the graph via nonlinear least squares optimization (like Levenberg-Marquardt) directly performs bundle adjustment. This formulation makes the sparsity of the problem explicit, enabling efficient solution of large-scale reconstructions with thousands of cameras and millions of points.

Maximum A Posteriori (MAP) estimation is the probabilistic foundation for bundle adjustment. It seeks the most probable configuration of unknown variables (structure and motion) given the observed data (image features) and prior knowledge.

• Bundle adjustment formulates the reprojection error as a negative log-likelihood.
• Minimizing the sum of squared reprojection errors is equivalent to performing MAP estimation under the assumption of Gaussian measurement noise.
• This framework naturally incorporates priors (e.g., on camera motion smoothness or known 3D point locations) as additional terms in the optimization, moving from a Maximum Likelihood Estimation (MLE) to a full Bayesian estimate.

Visual-Inertial Odometry (VIO) is a real-time state estimation technique that fuses camera and IMU data. Bundle adjustment often serves as its back-end optimization module.

• Front-end: Tracks sparse features and pre-integrates IMU data to provide a high-frequency motion estimate.
• Back-end: A sliding-window bundle adjustment optimizes the poses and landmarks over a recent set of frames, correcting drift from the front-end. This is sometimes called Visual-Inertial Bundle Adjustment.
• Systems like OKVIS and VINS-Mono use tightly-coupled, optimization-based VIO where the bundle adjustment cost function includes IMU residual terms, jointly optimizing for visual reprojection and inertial dynamics consistency.

Bundle adjustment is the global optimization engine in modern feature-based Visual SLAM and Structure-from-Motion (SfM) pipelines.

• In SLAM, it is used for pose-graph optimization and full bundle adjustment after loop closure. The ORB-SLAM system, for example, performs local BA in a co-visibility graph and global BA after a loop is detected.
• In SfM (e.g., COLMAP), incremental or hierarchical bundle adjustment is used to progressively refine the 3D model as new images are registered.
• The key difference from pure odometry is BA's joint optimization over both map and trajectory, reducing accumulated error by distributing it across all parameters.

Bundle adjustment is fundamentally a large-scale sparse nonlinear least squares problem. Efficient solvers are critical for performance.

• The objective function is the sum of squared reprojection errors.
• Levenberg-Marquardt is the most widely used algorithm, adapting between gradient descent and Gauss-Newton by using a damping parameter.
• The sparsity pattern of the problem's Hessian matrix (Schur complement) allows for efficient solving. Libraries like Google Ceres Solver and g2o are specifically designed to exploit this sparsity for bundle adjustment and related graph-based optimization problems in robotics.

Triangulation is the geometric process of determining a 3D point's location from its 2D projections in two or more images. It provides the initialization for the 3D points later refined by bundle adjustment.

• Linear triangulation (via Direct Linear Transform) provides an initial estimate, assuming perfect camera pose knowledge.
• This initial estimate is often noisy due to measurement noise and errors in the estimated camera poses.
• Bundle adjustment's role is to jointly refine these noisy triangulated points and the camera poses by minimizing the collective reprojection error, correcting for biases and inconsistencies in the initial estimates.