Source-linked AI summary
HiSfM: Disambiguating Structure-from-Motion via Scaffold-Anchored Hierarchical Reconstruction
Ziding Zhao, Hainan Cui, Peilin Tao, Shuhan Shen
TL;DR
SfM remains vulnerable to visual ambiguity and computational redundancy. HiSfM addresses both through selective verification, a scaffold-anchored hierarchy, and efficient image attachment, achieving robust, complete reconstructions with lower runtime.
Problem
SfM can fail under repeated or symmetric structures and incur heavy computational overhead from redundant cameras and constraints.
Method
HiSfM forms local communities, builds an edge-disjoint spanning-tree skeleton with selective bridge verification, reconstructs a scaffold, and attaches remaining images efficiently.
Results
HiSfM achieves robust, complete reconstructions with lower runtime than exhaustive disambiguation methods and higher completeness than aggressive sparsification approaches; on Cereal, it recovers full registration while CamTrip registers about 56%.
Takeaways & Limitations
A verified scaffold anchors reconstruction while selective global verification and reduced graph redundancy mitigate ambiguity-induced drift and improve efficiency.
Abstract
from arXiv · showhide
Structure-from-Motion (SfM) is a fundamental tool for sparse 3D reconstruction with broad impact in robotics and vision, supporting mapping, localization, and large-scale scene modeling. However, conventional pipelines often fail under hard visual ambiguity caused by repeated or symmetric structures, and incur heavy computational cost due to redundant cameras and constraints. We present HiSfM, a hierarchical coarse-to-fine SfM framework that improves robustness and efficiency through scaffold construction. HiSfM first forms strong local communities using geometrical induced heuristics, then connects communities with a compact yet strong skeleton by packing edge-disjoint spanning trees (EDST) while verifying skeletal edges with a two-view disambiguator. We reconstruct a stable scaffold on this verified skeleton, serving as an anchor to capture the essence of the scene, and subsequently absorb remaining images via efficient registration and triangulation for further refinements. Experiments on ambiguity-focused benchmarks and general datasets show that HiSfM prevents ambiguity-induced failures while substantially reducing runtime compared to previous methods, and improves completeness over aggressive sparsification methods. Code is available at https://github.com/3dv-casia/HiSfM.
I. INTRODUCTION
SfM must withstand visually ambiguous correspondences while avoiding the computational burden of redundant cameras and graph constraints. HiSfM addresses both by allocating disambiguation to globally important connections and reconstructing around a compact scaffold.
- SfM estimates camera poses and sparse 3D points, supporting map building, visual SLAM, and 6-DoF localization.
- Repeated or symmetric structures can create geometrically plausible but incorrect correspondences that propagate into hallucinated or duplicated reconstructions.
- Redundant cameras and edges increase reconstruction cost, with bundle adjustment often described as scaling cubically, O(n^3), in dense settings.
- HiSfM separates local community formation from globally critical connectivity, applying expensive disambiguation selectively to inter-community bridges.
- HiSfM forms local communities, packs edge-disjoint spanning trees into a skeleton, verifies critical bridges, and reconstructs a scaffold before attaching remaining images.
II. RELATED WORK
Prior SfM work improves either ambiguity robustness or computational efficiency, but each direction has important costs or risks. HiSfM combines selective disambiguation with structured sparsification to retain globally important connectivity.
- HiSfM combines selective disambiguation on globally critical connections with a compact coarse-to-fine reconstruction schedule.
- Prior methods address ambiguity through hypothesis reasoning, visibility or track context, higher-order consistency, and contextual graph cues.
- Broadly applied triplet, cycle, global-selection, post-hoc, and learned disambiguation methods can require substantial computation.
- Efficiency-oriented systems reduce problem size or restructure reconstruction through skeletal subsets, key subsets, coarse-to-fine schedules, and randomized or local-to-global strategies.
- Pure sparsification can remove globally important connections, causing oversplitting or reduced completeness when retained constraints are insufficient or ambiguous.
III. METHODOLOGY
HiSfM partitions the view graph into strong local communities, then uses those communities to guide a compact reconstruction structure. The method preserves local support while reducing weak or redundant relations before later reconstruction stages.
- HiSfM separates dense local connectivity from global structure to address ambiguity propagation and redundancy-driven bundle-adjustment cost.
- The input view graph contains image nodes and edges weighted by the number of geometrically verified inliers.
- Local Community Partitioning: Top-k filtering keeps each image’s strongest neighbors, and connected components of the resulting sparse graph define the community partition.
- Local Community Partitioning: In the cup visualization, the first image’s top-1 and top-3 neighbors are marked to illustrate match-count-based neighbor selection.
- Local Community Partitioning: HiSfM sets k = 1 because top-1 filtering yields communities with stronger mutual support and limits unnecessary early edge redundancy.
B. Skeletal Subgraph Building
HiSfM builds a compact, robust community-level skeleton by packing edge-disjoint spanning trees and selectively verifying globally critical bridges. The resulting redundancy preserves connectivity while limiting expensive disambiguation and supporting incremental reconstruction.
- HiSfM defines bridges as inter-community edges and constructs a community-level multigraph whose bridge weights are inherited from the original graph.
- The skeleton is formulated as a maximum-weight packing of edge-disjoint spanning trees at the community level.Each selected tree spans the community graph, while edge-disjointness provides redundant global routes.
- A greedy Kruskal-style procedure processes bridges by descending weight and retains candidates only when they connect distinct community components, satisfy diversity constraints, and pass DG++ thresholding.This concentrates expensive two-view verification on selected inter-community bridges.
- Packing K spanning trees provides controlled edge redundancy and supports robustness to bridge failures during incremental reconstruction.The figure states that 2-edge-connectivity keeps the graph connected after at most one edge failure.
- The construction may add top-weight or verified backup bridges to densify connectivity and protect low-weight connections.These additional inter-community bridges are verified because they may be ambiguous.
C. Leaf Nodes Attachment
After constructing the verified skeleton, HiSfM attaches remaining images through lightweight intra-community edges. Skeletal nodes anchor leaf images, while local support avoids costly global densification and repeated disambiguation.
- Leaf nodes are images outside the skeletal vertex set and are attached using a small number of high-weight intra-community neighbors.Edges to already-selected skeletal nodes are prioritized to anchor each leaf onto the scaffold.
- HiSfM does not apply DG++ to intra-community attachment edges because communities are formed from strong local connectivity with large inlier counts.
- The hierarchical graph combines the verified global scaffold with intra-community attachment edges for efficient absorption of remaining images.The scaffold supplies global structure, while leaf edges provide lightweight local support.
D. Coarse-to-Fine Reconstruction
HiSfM follows its hierarchy during reconstruction: it first solves a compact, verified scaffold and then registers remaining images through local support, followed by triangulation and refinement. This coarse-to-fine schedule targets ambiguity-prone global links while reducing redundant optimization.
- The reconstruction uses two stages: scaffold reconstruction on Gs followed by attachment of leaf images through Eℓ.The sparse model contains estimated camera poses and triangulated 3D points.
- COLMAP first reconstructs the skeletal subgraph to obtain a stable scaffold with reliable propagation across communities.Selective bridge verification improves the scaffold’s robustness to hard ambiguity, while compact optimization reduces early problem size.
- Remaining images are registered using intra-community neighbors, robust PnP, new triangulation, and local bundle adjustment.The process repeats until the number of registered cameras stops increasing, then applies global bundle adjustment.
- The coarse-to-fine schedule reconstructs globally critical ambiguity-prone connections first and absorbs remaining images through reliable local community support.The paper states that this mitigates ambiguity-induced drift while reducing redundant back-end computation.
IV. EXPERIMENTS
The experiments compare HiSfM with CamTrip and DG++ under matched feature, matching, and COLMAP back-end settings. Runtime includes both disambiguation inference and reconstruction, with hardware and solver settings specified for reproducibility.
- HiSfM is compared with CamTrip and DG++ using the same COLMAP back end and identical feature extraction and matching outputs.The comparison therefore varies view-graph selection and verification rather than the shared reconstruction back end.
- Experiments use an Intel i7-14700K CPU, an NVIDIA RTX 3090 GPU, and 128GB RAM with CUDA-accelerated bundle adjustment.All methods use identical bundle-adjustment solver settings.
- HiSfM recommends setting the number of spanning trees K proportional to image-set size, approximately one tree per 300 images.The supplied experimental description identifies this as the recommended connectivity setting; its ablation is discussed separately.
- Reported runtimes include both disambiguation inference and reconstruction.
A. Evaluation on Ambiguous Datasets
On ambiguity-focused benchmarks, HiSfM is evaluated against CamTrip and DG++ for reconstruction correctness, completeness, geometric quality, and runtime. It combines strong completeness with low runtime by verifying only inter-community bridges before completing the reconstruction.
- CamTrip is typically fast but may register fewer images and oversplit scenes, whereas DG++ performs better but incurs substantially higher runtime from evaluating many candidate pairs.
- The evaluation measures registered images, triangulated 3D points, mean reprojection error, mean track length, and runtime including inference.
- HiSfM achieves strong completeness while keeping runtime low by verifying inter-community bridges and reconstructing a compact scaffold before attaching remaining images.This design is intended to prevent ambiguity-induced drift without exhaustive verification.
- On Cereal, DG++ fails to produce a correct reconstruction, CamTrip registers about 56% of images, and HiSfM achieves correct full registration while being fastest.
- Across ambiguous scenes, HiSfM achieves comparable or better accuracy metrics than CamTrip and DG++ while substantially reducing runtime.Accuracy is assessed through triangulation statistics under a shared pipeline.
B. Evaluation on General Datasets
On larger Internet photo collections from 1DSfM and Photo Tourism, HiSfM improves completeness over CamTrip on most scenes while remaining much faster than DG++. The results indicate generalization beyond ambiguity-focused benchmarks.
- The evaluation uses larger, less curated Internet photo collections from 1DSfM and Photo Tourism, with quantitative results reported in Table II.
- HiSfM consistently improves completeness over CamTrip on most general-dataset scenes while remaining much faster than DG++.
- DG++ can incur extremely high runtime on large image sets because broad pairwise disambiguation may approach O(n2) when many candidate pairs are evaluated.
- HiSfM generalizes effectively from ambiguity-prone benchmarks to standard Internet photo collections while maintaining reconstruction completeness and structural integrity.
C. Ablation Studies
The ablation varies the number of edge-disjoint spanning trees K across ambiguous and general scenes. Larger K generally registers more images but increases runtime, with diminishing completeness gains beyond the recommended setting.
- The ablation compares scenes from ambiguous and general datasets with image sets of roughly 300, 600, 900, and 1200 images.
- Increasing K leads to more registered images but also incurs higher runtime across representative scenes.The study uses K ∈{1, 2, 3, 4, 5} and measures completeness by registered-image count.
- For Roman Forum, increasing K from 4 to 5 adds 15% runtime but yields only 4 additional images.
V. CONCLUSION
HiSfM addresses ambiguity and redundancy through hierarchical reconstruction: it builds a verified scaffold from local communities and edge-disjoint spanning trees, then attaches remaining images. Experiments report robust, complete reconstructions with lower runtime than exhaustive disambiguation and higher completeness than aggressive sparsification.
- HiSfM partitions the view graph into local communities, constructs a compact skeleton with edge-disjoint spanning trees, and verifies critical inter-community bridges.
- The method reconstructs a verified scaffold first and then attaches remaining images to prevent ambiguity-induced drift while reducing redundant optimization.
- Experiments on ambiguous benchmarks and large Internet photo datasets report robust and complete reconstructions with significantly lower runtime than exhaustive disambiguation methods.
- HiSfM achieves higher completeness than aggressive sparsification approaches.