Stable and Scalable Bundle Adjustment of Holistic 3D Structures

AI summary

Overview

Research area: 3D computer vision, specifically structure-from-motion (SfM) and bundle adjustment (BA) with geometric primitives and structural constraints. Technical level: Advanced (the paper relies on Schur complement elimination, Hessian sparsity structure, Fisher information, and Plücker line parameterization). Scope: a single paper proposing a unified bundle adjustment framework that jointly optimizes points, lines, cameras, and higher-order structural groups while preserving the block-diagonal sparsity that makes classical point-based BA efficient.

What This Paper Is About

Classical bundle adjustment is fast and scalable because 3D landmarks are mutually independent, which keeps the landmark Hessian block-diagonal and enables cheap Schur complement elimination. Real scenes contain richer structure (parallel lines, coplanar surfaces, point-line junctions), but adding these relations either couples features together, destroying the block-diagonal structure, or requires 3D regularization terms that mix metric residuals with pixel residuals and suffer from scale ambiguity. The paper's goal is to incorporate these richer structures into BA while keeping the runtime and conditioning of classical point-only BA.

Key Contributions

1. A taxonomy of sparse 3D structures that separates features (points and lines, which have direct 2D measurements) from groups (vanishing points, planes, spheres, cylinders, cuboids, conics, object priors, which encode higher-order relations among features), showing that groups can be modeled as camera-like entities placed in the non-eliminated block of the normal equations.
2. A group-induced reprojection error formulated in pixel space (Eq. 7 for points, Eq. 8 for lines) that replaces direct 3D point-to-plane penalties and implicitly weights each structural constraint by the Fisher information of the involved features, giving a Mahalanobis-distance interpretation.
3. A cross-feature reprojection error for wireframes (Eq. 11 point-to-line, Eq. 12 line-to-point) in which one feature is an optimization variable and the other enters only through its fixed 2D observation, so point-line junctions no longer create off-diagonal blocks in the feature Hessian.
4. An end-to-end incremental SfM pipeline built on the framework, released at https://github.com/cvg/limap and fully compatible with the COLMAP ecosystem, with sparsity analysis showing the reduced system's structure (including camera–group coupling in H_cg) is unchanged relative to 3D formulations.

Main Findings

• Asymptotic complexity is preserved. On synthetic problems scaling from 100 to 2000 images, Point, Point-Line, Groups, and Holistic configurations all scale similarly: approximately n^(1.6–1.9) under SPARSE_SCHUR and approximately n^(2.6–2.8) under DENSE_SCHUR.
• Groups behave like cameras in the normal equations. Under DENSE_SCHUR, where runtime is determined by the size of the reduced system, Point and Point-Line have nearly identical cost, as do Groups and Holistic.
• 2D wireframe residuals beat 3D endpoint-distance residuals. With SPARSE_SCHUR the 2D formulation is moderately faster; with DENSE_SCHUR the gap widens because the 3D formulation produces significantly denser fill-in in the reduced system.
• Runtime overhead is modest in a full SfM pipeline. Across the three 1DSfM scenes, overall pipeline runtime is approximately 1.3× the point baseline, substantially lower than the 2–4× overhead over COLMAP reported in prior work. Per-iteration times are higher for Holistic SfM (for example 214.0 ms/iter versus 132.5 ms/iter for the point baseline on Tower of London), and iterations per BA call rise (11.8 versus 4.8 on Tower of London) because structural constraints need more iterations to converge.
• Comparable reprojection error and more registered images. On 1DSfM, the Holistic pipeline registers 963/1322 images on Tower of London versus 909/1322 for the point baseline, with mean reprojection errors of 1.03 versus 1.04 pixels.
• Richer reconstructions. The framework optimizes thousands of lines alongside groups (117 groups on Tower of London, 42 on Madrid Metropolis, 91 on Gendarmenmarkt) while keeping point counts comparable to the baselines.
• Improved geometry on Hypersim (8 scenes). Point inlier percentage at 1mm rises from 9.3 (per-point/per-line refinement) to 11.5 with group constraints and 11.9 with group and wireframe constraints; median point error drops from 15.10 mm to 13.80 mm and then 13.55 mm. Line precision at 1mm rises from 21.3 to 27.3 to 27.3.
• Improved point reconstruction on ETH3D (13 scenes). Accuracy at 1cm rises from 45.17 to 47.05; completeness at 1cm from 0.14 to 0.15; F1 at 1cm from 0.29 to 0.30, with consistent gains at 2cm, 5cm, and 10cm.
• Improved camera poses. On Hypersim (8 scenes), Holistic SfM reaches AUC@3°/5°/10° of 92.5/93.4/94.2 versus COLMAP's 89.3/90.4/92.2. On ScanNet++ (20 scenes), it reaches 87.4/89.4/90.6 versus COLMAP's 84.0/86.0/87.5. The ETH3D (11 scenes) and 7Scenes (7 scenes) results are not present in the available content.

Methodology in Plain English

The authors start from the observation that classical BA is fast only because each 3D point couples to its observing cameras alone, which keeps the landmark part of the Hessian block-diagonal and allows the points to be cheaply eliminated with the Schur complement. They then classify geometric entities by how they should be treated computationally. Points and lines are "features" because they have direct 2D measurements and are numerous, so they go into the eliminated block. Planes, vanishing points, and similar constructs are "groups" because they encode relationships among features and are relatively few, so they are added alongside cameras in the non-eliminated block. Because each residual then touches at most one feature, the feature Hessian stays block-diagonal.

To avoid the problems of 3D penalties (scale drift, ad hoc weighting between metric and pixel terms), the authors write every structural constraint as a difference between two 2D reprojections. For a group constraint, they project a point or line onto the group's surface in 3D and measure how much the 2D projection changes; the residual vanishes when the feature already lies on the surface. For a wireframe constraint between a point and a line, they use one feature's 2D observation as a fixed measurement to constrain the other feature, so the two features are never coupled directly. They show that this weighting is equivalent to a Mahalanobis distance using the feature's own triangulation covariance, so well-observed features anchor the structure and poorly observed ones contribute little. The implementation uses ALIKED and DeepLSD for point and line detection, LightGlue and GlueStick for matching, JLinkage for vanishing points, and a custom plane segmentation method fitting planes to MoGe-2 predicted depth and surface normals; the optimizer is built on Ceres with analytical Jacobians and follows the COLMAP SfM pipeline, with constraints instantiated only when more than three images support them and optimized with a robust Cauchy loss.

Why This Matters

This work suggests that richer geometric structure in 3D reconstruction does not have to come with the dramatic runtime and stability penalties that prior formulations accepted. By keeping the algebraic structure of classical BA intact, it makes holistic reconstruction practical in existing solvers and pipelines.

Real-world applications:

• Urban mapping and city-scale reconstruction, where building facades, parallel edges, and planar surfaces dominate the scene.
• Augmented and mixed reality, where stable camera tracking and planar surface understanding are needed for placing content.
• Robotics and autonomous navigation using visual SLAM, where the Schur complement structure is also exploited and Manhattan-world structure is common.
• Cultural-heritage and architectural documentation, where accurate wireframe and planar geometry matters more than raw point density.

Industry relevance: the code release is integrated with the COLMAP ecosystem via the existing LIMAP repository, which lowers the barrier for adoption by teams already using COLMAP, Ceres, or similar sparse solvers. The reported approximately 1.3× overhead relative to a point baseline is a much easier cost to justify in production than the 2–4× overhead previously associated with line-based systems.

Future Directions

• Improving the reliability and confidence estimation of upstream structural associations, since the paper explicitly identifies dependence on good-quality associations as a practical limitation and treats model selection as outside its scope.
• Handling features with degenerate viewing geometry, which the 2D reprojection formulation cannot pull onto a group surface; the authors argue such cases matter little for camera accuracy but the limitation remains.
• Extending the same sparsity analysis and Schur elimination strategy to global positioning in global SfM, which the authors note shares the identical computational structure.
• Broadening the taxonomy to additional group types and to 2D measurements of groups themselves (such as monocular plane normals), which the framework already accommodates by contributing only to the H_aa block.

Target Audience

Researchers and engineers working on structure-from-motion, SLAM, and large-scale 3D reconstruction who are already comfortable with bundle adjustment, the Schur complement, and sparse nonlinear least squares. It is also relevant to practitioners building on COLMAP, Ceres, or LIMAP who want richer structural output without a large efficiency penalty. Readers without a background in sparse optimization will find the mathematical sections demanding, though the taxonomy and the experimental comparison are accessible at a higher level.

Authors’ abstract

Bundle Adjustment (BA) is a cornerstone of 3D computer vision and has benefited from decades of advances in sparse optimization and numerical methods. It was originally developed for jointly optimizing camera intrinsics, poses and sparse 3D points. While extensions incorporate lines and other primitives, integrating richer geometric structures such as parallelism, coplanarity, or wireframes often introduces significantly increased computational cost and reduced numerical stability. In this paper, we propose a unified framework that extends bundle adjustment to jointly optimize geometric features and higher-order relations. We first introduce a taxonomy that distinguishes scalable geometric features with direct 2D measurements (e.g., points and lines), from groups encoding higher-order relations (e.g., coplanarity, parallelism, etc.), where we show that groups can be modeled as camera-like entities within the bundle adjustment framework. Building on this formulation, we propose that both group constraints and cross-feature relations (i.e., point-line associations) can be expressed through 2D reprojection measurements. By formulating group-induced and cross-feature reprojection errors, we preserve the sparsity structure of classical point-based BA under Schur elimination, while avoiding direct 3D regularization that degrades the conditioning and stability. Experiments on both real-world and synthetic datasets demonstrate runtime performance comparable to classical point-only bundle adjustment, while producing significantly richer 3D structures and improved geometric accuracy.