Bundle Adjustment: A Modern Synthesis

What they do

A survey of photogrammetric bundle adjustment written for computer vision implementors. Bundle adjustment refines a reconstruction so that 3D structure and camera pose and calibration are jointly optimal under a cost on the prediction (reprojection) error. The authors argue that most of the theory already exists in photogrammetry and geodesy. They also argue against common vision claims such as “bundle adjustment is slow”, which they attribute to general-purpose optimizers that ignore the problem’s sparsity.

How it works

• Cost. The cost is a sum of independent contributions. Ideally it is the negative log likelihood of the total (inlier + outlier) error distribution. Gaussian tails are unrealistically small, so they recommend long-tailed models such as Cauchy or inlier/outlier mixtures.
• Parametrization. Steps are taken in well-conditioned local coordinates: quaternions or incremental rotations instead of Euler angles, and homogeneous coordinates for distant points.
• Sparse Newton. 3D features couple only to cameras, so the structure block of the Hessian is block diagonal. A Schur complement eliminates it, leaving the reduced camera system of Brown’s 1958 method. Alternatively, sparse Cholesky can be used with a good variable ordering. Kalman filtering is framed as only the first half-iteration of a full nonlinear optimization.
• Gauge and quality control. The freedom to choose the coordinate frame (7 dof Euclidean, 15 projective) makes covariances frame-dependent. Outlier tests, reliability measures and model selection check the result.

Results

• Newton methods reach 1e-16 from O(1) in about 5 iterations. Linearly convergent methods need 16, 350 or 3700 iterations at per-step error reductions of 0.9, 0.1 or 0.01.
• On a small ill-conditioned problem, Gauss-Newton takes 11 steps (1.2e6 flops). Resection-intersection takes 71 steps with a line search and 200 without.
• On a synthetic ‘strip’ (each feature seen in about 3 images), resection-intersection is slower even than dense Cholesky that ignores sparsity. On a well-conditioned ‘spherical cloud’, all methods converge quickly.

Limitations

The authors call their recommendations very provisional. The solver comparisons use synthetic problems. Initialization is not covered, and network design gets only rules of thumb. The asymptotic Gaussian covariance may be a poor approximation for small vision problems and weak networks.