M4-T7 — Bundle Adjustment

Learning objectives

After this lesson, you should be able to:

• Write the reprojection error for a pinhole camera and the bundle-adjustment objective.
• Describe the parameters, the Jacobian blocks and the sparse structure of the normal equations.
• Explain the Schur complement trick and estimate its savings.
• List the gauge freedoms (including scale) and the role of robust costs.

The problem and the intuition

Two people photograph a statue from different spots. Each marks the same spot on the nose in their photo. If we know where each camera stood and how it was turned, each mark defines a ray in space, and the rays should meet at the nose. They almost never meet exactly, because the marks are off by a pixel and the camera poses are guesses. Bundle adjustment wiggles all the cameras and all the 3D points at once until the rays pass as close to each marked pixel as possible. The name is old: the “bundle” is the bundle of light rays.

Reprojection error is measured in the image, in pixels: the units in which the sensor’s noise is actually known.

The algorithm: bundle adjustment

Problem. Given pixel observations u_ik of 3D points X_k in cameras i, estimate the camera poses T_i = (R_i, t_i) and the points X_k (and optionally the intrinsics) that minimise the total reprojection error.

Assumptions. The correspondences (which pixel in which image is which point) are known; the camera model (pinhole plus distortion) is calibrated or included in the unknowns; noise in pixels is roughly Gaussian; an initial estimate (from tracking and triangulation) is available.

(R_i, t_i)

camera i’s pose: 6 degrees of freedom.

X_k

the 3D position of point k: 3 unknowns.

f_x, f_y, c_x, c_y

intrinsics: focal lengths and principal point, in pixels.

ρ

a robust loss (Huber or Cauchy); wrong feature matches are common (M4-T6).

Structure: why it is fast

One residual depends on exactly one camera and one point. The Jacobian row has two non-zero blocks: 2×6 for the camera and 2×3 for the point. The normal equations have the form

C is block diagonal: points do not interact directly, so inverting it costs only one 3×3 inversion per point. Eliminating the points gives the reduced camera system (the Schur complement):

The reduced system has only 6 unknowns per camera, however many thousands of points there are. Solving it, then back-substituting for the points, is the standard algorithm (Triggs et al., 2000; Lourakis and Argyros, 2009).

Gauge freedoms

• Monocular: the whole reconstruction can be translated, rotated and scaled without changing any reprojection error: 7 degrees of freedom. Fix the first camera pose and the distance to a second camera (or one scale); an IMU or stereo supplies the metric scale (Module 6).
• Stereo or RGB-D fix the scale: 6 degrees of freedom remain (rigid motion).
• Without fixing these, the system is singular, exactly as an unanchored pose graph.

Local and global bundle adjustment

Tracking runs local BA on a window of recent keyframes and the points they see (ORB-SLAM, VINS-Mono): fast, keeps the pose current. Global BA over all keyframes is run after a loop closure or offline (COLMAP), and is the benchmark for accuracy. Between the two lies the pose-graph optimisation of M4-T4, which is cheaper than global BA but loses the point information.

A worked example: one observation, and the size of the problem

1. One observation. A camera with f = 500 px and principal point (320, 240) sees a point at P = (0.2, −0.1, 2.0) in its own frame. The projection is u = 500 × 0.2 / 2 + 320 = 370, v = 500 × (−0.1) / 2 + 240 = 215. The detected pixel is (372, 214): the reprojection error is (+2, −1) px: 2.2 px long.
2. Derivatives for the point. ∂u/∂X = f/Z = 250 px/m, ∂u/∂Z = −fX/Z² = −25 px/m, ∂v/∂Y = 250, ∂v/∂Z = −fY/Z² = +12.5. Moving the point 1 cm in X moves the projection by 2.5 px: a pixel is worth 4 mm of lateral position at 2 m. Depth is much weaker: 1 cm of depth moves it by only 0.25 px, so depth is the poorly determined direction, and wide baselines between cameras are what make it well determined.
3. Problem size. A local window with 10 keyframes and 2,000 points seen in about 5 of them each has 6 × 10 + 3 × 2,000 = 6,060 unknowns and 10,000 observations (20,000 residuals).
4. Without the trick the normal matrix is 6,060 × 6,060 with 36.7 million entries, and a dense solve takes about (6,060)³/3 ≈ 7 × 10¹⁰ operations.
5. With the Schur complement: invert 2,000 blocks of 3 × 3 (about 54,000 operations), form the 60 × 60 reduced camera matrix, solve it (a few thousand operations) and back-substitute. In total well under 10⁷ operations: a thousand times faster, which is why BA runs in real time inside SLAM.
6. Scale. Monocular BA has no scale: if you multiply all coordinates by 2 and all translations by 2, every reprojection error stays the same. A system that starts with a depth guess of 1 m for the first points fixes its own arbitrary unit.

Real bundle adjusters add robust kernels (the 2.2 px error above is fine, a 40 px error is probably a wrong match) and update the rotations on the manifold.

Engineering implications and limitations

Engineering implications

• Initialise well. BA is non-convex: triangulate points from good tracking and use pose estimates from PnP or odometry. A poor initial guess leads to local minima and cameras that flip.
• Use robust costs and outlier checks. After the first iterations, remove observations with large reprojection error (for example above the 95% chi-square threshold in pixels), then re-optimise.
• Keep the window small for real-time operation and marginalise old keyframes (or fix them) instead of discarding their information; fixed-lag smoothing in visual-inertial systems.
• Mind the geometry. Points far from the cameras or in a pure rotation of the camera have no depth information; low parallax leaves depth uncertain and BA ill-conditioned. Choose keyframes with enough baseline.
• Handle the gauge. Fix the first camera and one scale, or use priors from an IMU or GPS.
• Use a library (Ceres, g2o, GTSAM, SBA, COLMAP) for the numerics; the effort goes into the front end and the data selection.

Limits

BA assumes known correspondences, a calibrated camera model and a static scene. Moving objects, rolling shutter, motion blur, and unmodelled lens distortion all enter as systematic errors that no amount of optimisation removes. Global BA is too costly for long sequences without sparsity tricks, and a pose graph or submap structure is used instead.

Common misconceptions

Engineering takeaways

1. Bundle adjustment minimises pixel reprojection errors over all camera poses and 3D points.
2. Each residual involves one camera and one point, so the normal matrix is sparse with a diagonal point block.
3. The Schur complement eliminates the points exactly and reduces the problem to the cameras: orders of magnitude faster.
4. Monocular reconstructions have a 7-degree gauge including scale; stereo or inertial data fix the scale.
5. Robust costs and good initial estimates are essential; depth is weakly determined without baseline.

References and further reading

Primary papers and authoritative documentation.

• Triggs, B., McLauchlan, P., Hartley, R. and Fitzgibbon, A. (2000). Bundle adjustment: a modern synthesis. Vision Algorithms: Theory and Practice, Springer LNCS 1883.
• Hartley, R. and Zisserman, A. (2004). Multiple View Geometry in Computer Vision, 2nd ed., Cambridge University Press, appendix 6: iterative estimation methods.
• Lourakis, M. I. A. and Argyros, A. A. (2009). SBA: A software package for generic sparse bundle adjustment. ACM Transactions on Mathematical Software 36(1).
• Agarwal, S., Snavely, N., Seitz, S. M. and Szeliski, R. (2010). Bundle adjustment in the large. ECCV.
• Mur-Artal, R., Montiel, J. M. M. and Tardós, J. D. (2015). ORB-SLAM: a versatile and accurate monocular SLAM system. IEEE Transactions on Robotics 31(5).

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

What’s next

Pose graphs and bundle adjustment are two instances of one structure. The last lesson of the module names it, the factor graph, and shows how its solution is kept up to date as measurements arrive.

Related content

Nothing below is required to finish this lesson.

• Before
  M4-T6: Robust Optimization and Outlier Handling

  Use robust kernels, switchable constraints and consistency checks to survive bad edges.

• Lab
  M4-L4: Compare Trajectories Before and After Optimization

  Quantify the optimisation with error metrics, and check what a good chi-squared and residual profile looks like.