Global Structure-from-Motion Revisited

In plain words

Structure-from-motion takes a pile of photos of one scene and works out where the camera was for each photo, plus a cloud of 3D points on the scene. There are two main families of methods. Incremental methods add one camera at a time and are the accurate, robust choice that most people use today, but they get slow on large collections. Global methods solve for all cameras at once, which is fast and scales well, but they have historically been less accurate and less robust.

The weak spot of global methods is a middle step that first estimates where each camera sits from pairwise direction hints, and only afterwards places the 3D points. Those direction hints are noisy, get unreliable when the lens settings are unknown, and break down when the camera moves in a nearly straight line, as in a video. This paper removes that middle step. It places cameras and points in one joint optimisation that uses the camera rays directly, which makes the solution less fragile. The result is a general-purpose global pipeline that is meant to match the accuracy of the standard incremental tool while keeping the speed of global methods.

TL;DR

GLOMAP is an open-source global structure-from-motion system (BSD-3-Clause code from the COLMAP authors). It replaces translation averaging and separate triangulation with one global positioning step that estimates camera centres and points together from normalized ray-direction errors, followed by several rounds of bundle adjustment. The authors report accuracy on par with or above COLMAP on average across ETH3D, LaMAR, IMC 2023 and MIP360, with speed-ups over COLMAP between about 1.6x (MIP360) and about 29x (LaMAR) on those averages. Results are author-reported. Some scenes still fail, notably those with rotational symmetry, because rotation averaging collapses there.

Problem

Global SfM estimates all camera rotations and positions at once from the view graph of pairwise two-view geometries §2.2. Rotations can be averaged robustly, but camera positions are usually obtained by translation averaging, which is ill-posed §1. Relative translations from two views are known only up to scale, so reliable positions need triplets of directions, and skewed triplets amplify noise §1. Relative translations also require accurate camera intrinsics, which unordered internet photos often lack §1 §3.2. Nearly co-linear motion, common in sequences, makes the problem degenerate §1 §2.2. Translation averaging also works poorly when the view graph is weakly connected §2.2. The authors argue that these problems are why global pipelines have been less accurate and robust than incremental ones §1 §5.

Method

Overview §3.5 fig. 2. Correspondence search uses COLMAP's implementation with RootSIFT features and bag-of-words retrieval to find candidate pairs, then verifies them with robust estimation of a homography, a fundamental matrix and an essential matrix §2.1 §3.5. Geometrically infeasible matches are removed. View-graph calibration updates the intrinsics §3.5. Relative poses are then estimated, global rotations are obtained by rotation averaging, and edges whose relative rotation disagrees with the global rotations are filtered §2.2 §3.5. Feature tracks are built from the surviving inlier matches §3.1. The core step, global positioning, estimates camera centres and 3D points jointly §3.2. Global bundle adjustment follows §3.3. Structure refinement (retriangulation plus further bundle adjustment) and camera clustering are optional §3.5 §3.4.

Rotation averaging §2.2 eq. 1 is a robust least-metric problem over the absolute rotations R_i, penalising how far each relative rotation R_{ij} deviates from R_j R_i^\top under a distance d with exponent p. The paper uses Chatterjee et al.'s scalable approach, implemented by the authors §2.2.

\arg\min_{R} \sum_{i,j} \rho\left( d\left( R_j^\top R_{ij} R_i, I \right)^p \right) eq. 1

# GLOMAP pipeline  [§3.5] [fig. 2]
# Input:  images
# Output: intrinsics, rotations, camera centres, 3D points

def glomap(images):
    # 1. Features, matching and two-view geometry  [§2.1] [§3.5]
    matches = match_candidate_pairs(extract_rootsift(images))
    two_view = verify_two_view(matches)   # F, E and H per pair
    # 2. Drop geometrically infeasible matches  [§3.5]
    two_view = drop_infeasible(two_view)
    # 3. View-graph calibration updates the intrinsics  [§3.5]
    intrinsics, view_graph = calibrate_view_graph(two_view)
    # 4. Relative poses from the calibrated pairs  [§3.5]
    view_graph = relative_poses(view_graph, intrinsics)
    # 5. Global rotations, then drop edges that disagree  [§2.2] [§3.5]
    rotations = rotation_average(view_graph)
    view_graph = filter_by_rotation(view_graph, rotations)
    # 6. Feature tracks from the inlier matches  [§3.1]
    tracks = build_tracks(view_graph)
    # 7. Joint camera-centre and point estimation  [§3.2] [eq. 3]
    centres, points, scales = global_positioning(tracks, rotations)
    # 8. Bundle adjustment rounds with track filtering  [§3.3] [eq. 2]
    centres, points = global_bundle_adjustment(centres, points)
    # 9. Optional: retriangulation and more rounds  [§3.5]
    # 10. Optional: camera clustering for unordered sets  [§3.4]
    return intrinsics, rotations, centres, points

Feature tracks §3.1 fig. 2. Only inlier matches from two-view verification are kept. For each pair, the model that best explains the matches (homography, essential or fundamental matrix) determines which inlier test is used. A cheirality test removes matches that imply points behind a camera. Matches near an epipole or with a small triangulation angle are removed to avoid unstable triangulations. The surviving pairwise matches are then chained into tracks.

Global positioning §3.2 fig. 3. Rotations are fixed. For every track observation, the camera ray in the world frame should point from the camera centre towards the 3D point. The paper uses a scaled residual with one normalising factor per observation, and drops the relative-translation terms that classical translation averaging relies on. The residual is minimised with a Huber robustifier and Levenberg-Marquardt in Ceres §3.2.

\arg\min_{X, c, d} \sum_{i,k} \rho\left( \lVert v_{ik} - d_{ik} (X_k - c_i) \rVert_2 \right), \quad d_{ik} \ge 0 eq. 3

Here v_{ik} is the globally rotated camera ray that observes point X_k from camera centre c_i, and d_{ik} is the normalising factor §3.2. Centres and points start from a uniform random draw, and every d_{ik} starts at 1 §3.2. Terms for cameras whose intrinsics are unknown are weighted by one half §3.2. The angular error at the optimal factor is bounded to the range from 0 to 1, so an outlier term has limited influence §3.2:

\begin{cases} \sin\theta & \text{if } \theta \in [0, \pi/2) \\ 1 & \text{if } \theta \in [\pi/2, \pi] \end{cases} eq. 4

In eq. 4, \theta is the angle between v_{ik} and X_k - c_i at the optimal d_{ik} §3.2. The authors attribute convergence from random starts to the bilinear form of the objective, and they describe the objective as initialisation-free §3.2.

# Global positioning of cameras and points  [§3.2] [eq. 3]
# Input:  tracks k with observations (i, v_ik); rotations R_i (fixed)
# Output: camera centres c_i, points X_k, normalising factors d_ik

def global_positioning(tracks, rotations, has_focal_prior):
    # 1. Random start for centres and points in [-1, 1]  [§3.2]
    centres = uniform(-1, 1, size=(num_cameras, 3))
    points = uniform(-1, 1, size=(num_points, 3))
    # 2. Every normalising factor starts at 1  [§3.2]
    scales = ones(num_observations)
    terms = []
    for each track k in tracks:
        for each observation (i, v_ik) in track k:
            # Camera ray rotated into the world frame  [§3.2]
            ray = rotations[i].transpose() @ v_ik        # (3,)
            # Ray should point from centre c_i to point X_k  [§3.2] [eq. 3]
            residual = ray - scales[obs] * (points[k] - centres[i])
            # Cameras without known intrinsics count half  [§3.2]
            weight = 1.0 if has_focal_prior[i] else 0.5
            terms.append((residual, weight))
    # 3. Huber loss, Levenberg-Marquardt, keep scales >= 0  [§3.2] [eq. 3]
    centres, points, scales = solve_huber_lm(terms, scales_min=0)
    return centres, points, scales

Global bundle adjustment §3.3 eq. 2. A standard reprojection objective is minimised with Levenberg-Marquardt and a Huber loss over intrinsics, extrinsics and points:

\arg\min_{\pi, P, X} \sum_{i,k} \rho\left( \lVert \pi_i(P_i, X_k) - x_{ik} \rVert_2 \right) eq. 2

Each round first keeps rotations fixed and then optimises jointly §3.3. Before the first round, 3D point observations are pre-filtered by angular error, with a larger allowance for uncalibrated cameras §3.3. After each round, tracks are filtered by reprojection error in image space. Rounds stop once the fraction of tracks removed falls below 0.1% §3.3.

Camera clustering §3.4 (optional). Internet collections can contain several disjoint scenes that were wrongly glued together. The covisibility graph counts shared visible points per image pair. Pairs with fewer than 5 points are dropped. The median of the remaining counts sets an inlier threshold τ §3.4. Strongly connected components are formed from pairs above τ. Two components merge when at least two pairs between them exceed 0.75τ. The merge repeats until nothing changes, and each connected component is output as its own reconstruction §3.4.

Structure refinement §3.5 (optional). Points are retriangulated with the estimated poses, followed by further bundle-adjustment rounds §3.5.

Hyperparameters

Values in the paper are cited to the paper. Code values come from the official repository at code_commit and are cited by path and line. "not stated" means the paper gives no value.

Results

Author-reported. Setup: each row is an average over the sequences or scenes the paper lists §4. Baselines are OpenMVG and Theia with their recommended default settings, and COLMAP §4; GLOMAP uses fixed settings §4. All methods receive the same feature matches, so correspondence search is excluded from the timings §4. Hardware is not stated in the source.

ETH3D SLAM, training sequences, averaged by prefix tab. 1 §4.1:

ETH3D MVS rig, average over scenes tab. 2 §4.1:

ETH3D MVS DSLR, average over scenes tab. 3 §4.1:

LaMAR, scenes LIN, HGE and CAB, averaged tab. 4 §4.1:

For LIN, GLOMAP ran without structure refinement because of memory limits tab. 4. OpenMVG has no values ("-") in the source table tab. 4.

IMC 2023 training sets, averaged over scenes tab. 5 §4.2:

The ground truth for IMC is built with COLMAP on held-out imagery, so it is biased towards COLMAP §4.2.

MIP360, seven scenes, averaged tab. 6 §4.2:

The MIP360 reference is a COLMAP model that is treated as pseudo ground truth; COLMAP was re-run on the same matches as the other methods §4.2.

Novel view synthesis, Instant-NGP on MIP360, averages tab. S4 app. S3:

Strecha, average camera position error in mm tab. S3 app. S1. The first row is marked in the source as taken from the LiGT paper; the other two rows are the authors' runs:

Ablation on global positioning constraints tab. 7 §4.3. "pt" is the points-only mode used by GLOMAP; "cam" uses relative translations and "pt+cam" adds points:

The third DSLR column is headed "AUC @ 3°" in the source, a likely typo for 5°, which matches the other tables tab. 7.

Robustness to point noise, synthetic reprojections without global BA tab. S5 app. S5: with 0 px noise, scores lie between 98.1 (facade) and 100.0. At 64 px noise they range from 42.5 (office) to 90.8 (facade).

Limitations §4.4. Failures come mainly from rotation averaging collapsing on symmetric structure, for example the exhibition hall scene in ETH3D DSLR (GLOMAP 25.5 vs COLMAP 85.4 at 1°) tab. 3. Poor matching caused by large appearance or viewpoint change also degrades results §4.4.

Other per-scene results to keep in mind: COLMAP scores higher on several ETH3D SLAM sequences, including camera, reflective and sofa tab. 1. On IMC 2023 the bike scene favours COLMAP (77.9 vs 35.0 at 3°) tab. 5. On LaMAR, CAB is poor for all methods tab. 4.

Appendix HSfM comparison app. S1, S2: HSfM is comparable on ETH3D MVS rig and DSLR, but fails on SLAM and LaMAR and falls well behind on IMC and MIP360, which the authors attribute to coarse intrinsics app. S1. The values are in the supplementary tables and were not transcribed here.

Paper vs code

Code at commit 99806d0869f802fad218516a2e027793e7ca687d, repository colmap/glomap, BSD-3-Clause LICENSE. Paths below are relative to the repository root.

• Initialisation range differs. Paper: uniform in [-1, 1] §3.2. Code: 100 × uniform in [-1, 1] for both centres and points global_positioning.cc global_positioning.cc.
• Rotation averaging runs twice, not three times. A comment says three global_mapper.cc. The code runs one filtering pass and a final pass, with the rotation filter set to 10° between them global_mapper.cc. The paper describes a filter on relative poses but no value §3.5.
• Structure refinement is optional in the paper §3.5. In code, bundle adjustment (3 rounds) and one retriangulation round run by default global_mapper.h global_mapper.cc.
• Track-filter stopping rule. Paper: halt once fewer than 0.1% of tracks are filtered §3.3. Code: the reprojection threshold is scaled by 3, 2 and 1 across rounds, and the inner loop accumulates filtered counts before the 0.1% test global_mapper.cc.
• Camera clustering is off by default. The paper describes it as a post-process that can be applied §3.4 §3.5. In code it is PruneWeaklyConnectedImages, and the default options set skip_pruning = true global_mapper.h. The code also builds a frame-level graph with one reference image per frame reconstruction_pruning.cc.
• Clustering threshold. Paper: τ is the median of pair counts §3.4. Code: τ = max(median − MAD, 20) over pair weights reconstruction_pruning.cc.
• Clustering merge comment. The code comment says "more than 3 pairs", while the condition is at least 2 view_graph_manipulation.cc. The paper's "at least two" matches the code, not the comment.
• Uncalibrated down-weight. Paper: factor 2 §3.2. Code: ScaledLoss by 0.5, which is the same factor global_positioning.cc. Consistent.
• Uncalibrated angular allowance. Paper: a larger allowance, no value §3.3. Code: twice the calibrated angle, i.e. 2° vs 1° track_filter.cc types.h.
• Positioning mode. Paper uses points only §3.2. Code has other modes, but the mapper returns an error for anything except points global_mapper.cc.
• Positioning objective. Code residual: track observation minus scale times (point − centre), with the Huber loss applied to the residual cost_function.h. This matches eq. 3.
• Pair type forced to essential matrix. When the intrinsics look good, the code forces the essential-matrix pair type before relative pose estimation global_mapper.cc. The paper does not describe this preprocessing step §3.5.

Pitfalls

• Several values the paper does not state are needed for a faithful build: the Huber thresholds, the reprojection and angle thresholds, the solver limits, the edge filters and the epipolar thresholds. The code values are listed in the table above and should be treated as the working defaults.
• The random init range is a silent difference. The paper says [-1, 1] but the code uses 100 × that. The effect is not tested in the source.
• Camera clustering is needed, by the paper's account, when internet images glue together disjoint scenes §3.4. The code default skips it. Whoever runs the pipeline on unordered collections should enable pruning explicitly.
• Rotation averaging is the failure point. The paper names its failure as the major cause of errors, with symmetric structure as the example §4.4. The DSLR exhibition hall scene shows the collapse tab. 3.
• Metric choice matters on sequences. For sequential data the paper reports camera-position error after robust alignment, because relative error misses scale drift §4. Scores on sequences are therefore not comparable with the unordered-set AUC scores.
• Runtime comparisons depend on hardware, which is not stated. The code defaults to GPU use global_positioning.h. Compare timings only on the same machine and configuration.
• The paper calls GLOMAP's runtime on the rig dataset only slightly higher than the global baselines. The table shows GLOMAP at 793.8 s against Theia at 350.5 s, about 2.3 times, which is a larger gap than that wording suggests tab. 2.
• The ablation's DSLR table has a mislabelled third column (see Results).
• The IMC ground truth and MIP360 pseudo ground truth both come from COLMAP, so COLMAP-favouring bias is possible §4.2.
• The HSfM and LiGT comparisons are not default baseline settings. HSfM was run through Theia with an added final triangulation and full bundle adjustment, and LiGT through OpenMVG's implementation app. S1. Treat those rows as the authors' configuration.
• Reproducibility: the seed is fixed at 1 in code global_positioning.h, but the paper does not state seeds, so repeated runs need that seed to match.

Lineage

• Builds on: the normalized direction-difference objective of BATA (Zhuang et al.) §3.2, with the relative-translation terms removed and only camera-ray constraints kept. Rotation averaging follows Chatterjee et al. §2.2. The two-view and matching pipeline is COLMAP's §2.1.
• Compared against: OpenMVG, Theia (with LUD translation averaging), COLMAP §4; HSfM and LiGT in the appendix app. S1, S2.
• Superseded by: not stated in this wiki.