Bundle Adjustment

Bundle adjustment simultaneously refines all unknown variables in a 3D reconstruction problem. This includes:

• 3D point coordinates of all scene features.
• Camera poses (extrinsic parameters: rotation and translation) for each image.
• Camera intrinsic parameters (e.g., focal length, principal point, lens distortion coefficients). By optimizing these parameters together, it ensures they are mutually consistent, correcting errors that accumulate from sequential estimation steps like feature matching and triangulation.

The core objective function is the sum of squared reprojection errors. For each observed 2D image feature, the error is the Euclidean distance (in pixels) between its detected location and the projection of its corresponding estimated 3D point back into the image plane using the estimated camera parameters.

The optimization algorithm (typically Levenberg-Marquardt) iteratively adjusts parameters to minimize this global cost: min Σ || x_observed - π(P, X) ||², where π is the projection function, P is the camera matrix, and X is the 3D point.

The Hessian matrix (or its approximation, the information matrix) of the bundle adjustment problem has a characteristic sparse block structure. This arises because each 3D point is independent of others, and each camera parameter block is only connected to the points it observes.

This sparsity is exploited by the Schur complement trick (or Marginalization), which allows for efficient solving of the large linear system within each optimization iteration. Libraries like Google Ceres Solver and g2o are designed to leverage this sparsity for performance.

Initial feature matches contain false correspondences (outliers) that can severely distort the optimization. Bundle adjustment incorporates robust cost functions (or loss functions) to mitigate their influence.

Common functions include:

• Huber Loss: Quadratic for small errors, linear for large errors.
• Cauchy Loss: Reduces the influence of very large residuals.
• Tukey's Biweight: Completely rejects residuals beyond a threshold. These functions down-weight the contribution of potential outliers, preventing them from pulling the solution away from the correct minimum.

Bundle adjustment is fundamentally a non-linear least squares (NLLS) problem. The relationship between 3D points, camera parameters, and 2D image coordinates is non-linear (involving rotations and perspective projection).

The Levenberg-Marquardt algorithm is the standard solver, as it adaptively blends Gradient Descent (stable when far from the minimum) and the Gauss-Newton method (fast convergence near the minimum). It requires computing the Jacobian matrix of the reprojection error with respect to all parameters.

Bundle adjustment is not a standalone technique but the final refinement step in pipelines like Structure from Motion (SfM) and Visual SLAM.

Typical Pipeline:

1. Feature Detection & Matching: Find correspondences across images.
2. Geometric Verification: Use algorithms like RANSAC with fundamental/essential matrices to filter outliers.
3. Incremental or Global SfM: Obtain an initial estimate of camera poses and 3D points.
4. Bundle Adjustment: Refine all parameters to produce a metrically accurate, globally consistent reconstruction. It is often run repeatedly, with increasing numbers of parameters, as the reconstruction grows.

Structure from Motion (SfM) is the foundational pipeline that precedes bundle adjustment. It is a computer vision technique that simultaneously estimates the 3D structure of a scene (a sparse point cloud) and the camera poses from a set of unordered 2D images.

• Process: SfM first detects and matches keypoint features across images, then uses epipolar geometry to estimate initial camera poses and a 3D point cloud.
• Output: The result is a preliminary, often noisy, reconstruction that serves as the initial guess for the subsequent bundle adjustment optimization.
• Key Difference: While SfM provides the initial estimates, bundle adjustment is the non-linear refinement step that minimizes the total reprojection error to produce the final, accurate reconstruction.

Reprojection error is the fundamental cost function or objective that bundle adjustment seeks to minimize. It quantifies the discrepancy between where a 3D point should appear in an image and where it was actually observed.

• Calculation: For a 3D point (X) and a camera with pose (P), the error is the Euclidean distance in pixels between the projected point (P(X)) and its measured 2D feature (x) in the image.
• Role in Optimization: Bundle adjustment adjusts all camera parameters (intrinsics and extrinsics) and 3D point coordinates to minimize the sum of squared reprojection errors across all images and all points.
• Significance: A low overall reprojection error indicates a geometrically consistent and accurate reconstruction, aligning the 3D model perfectly with the original 2D image evidence.

Camera pose (extrinsics) and camera calibration (intrinsics) are the primary parameters optimized during bundle adjustment.

• Camera Pose: This defines the position and orientation (translation (t) and rotation (R)) of the camera in the world coordinate system for each image.
• Camera Calibration (Intrinsics): These are the internal properties of the camera, including focal length ((f_x, f_y)), principal point ((c_x, c_y)), and lens distortion coefficients ((k_1, k_2, p_1, p_2)).
• Bundle Adjustment's Role: The optimization jointly refines both sets of parameters. Accurate intrinsics are often estimated in a separate step but can be tightly coupled in the adjustment, especially for datasets with varying zoom or multiple cameras.

Bundle adjustment is formulated and solved as a large-scale non-linear least squares (NLLS) optimization problem. The goal is to find the parameter vector (θ) (containing all 3D points and camera parameters) that minimizes the sum of squared reprojection errors.

• Mathematical Form: ( \min_θ \sum_i \sum_j || x_{ij} - proj(P_i, X_j) ||^2 ), where (x_{ij}) is the observed 2D feature and (proj) is the camera projection function.
• Solvers: Due to the problem's sparse structure (each error term depends on only one camera and one point), specialized solvers like Levenberg-Marquardt are used with sparse linear algebra (e.g., Schur complement trick) for efficiency.
• Challenges: The problem is non-convex and can converge to a local minimum, making a good initial guess from SfM critical.

Bundle adjustment operates on sparse feature points, but its output enables dense reconstruction.

• Sparse Reconstruction (SfM + BA): Produces a cloud of distinct 3D keypoints and camera poses. This is the direct output of bundle adjustment.
• Dense Reconstruction (MVS): Uses the calibrated camera poses from bundle adjustment as fixed, accurate input for Multi-View Stereo (MVS) algorithms. MVS then performs dense matching for every pixel, generating a complete point cloud, mesh, or depth maps.
• Pipeline Relationship: Bundle adjustment is the geometric backbone. Its accurate camera parameters de-risk the dense matching step, ensuring the final dense model is globally consistent and scale-aware.

Visual SLAM (Simultaneous Localization and Mapping) is the real-time, sequential counterpart to the offline batch processing of SfM and bundle adjustment. Many modern Visual SLAM systems perform local or global bundle adjustment as a key back-end optimization module.

• Online vs. Offline: While traditional bundle adjustment processes all images offline, Visual SLAM performs incremental bundle adjustment or pose-graph optimization in real-time as new frames arrive.
• Loop Closure: When a SLAM system recognizes a previously visited location (loop closure), it triggers a global bundle adjustment to correct the accumulated drift in the map and trajectory.
• Unified Principle: Both fields rely on minimizing reprojection error to achieve consistency between the estimated map (3D points) and the estimated agent/camera path.