HiSfM: Disambiguating Structure-from-Motion via Scaffold-Anchored Hierarchical Reconstruction
Ziding Zhao, Hainan Cui, Peilin Tao, Shuhan Shen
cs.CV
2026-09-04
HiSfM verifies only inter-community bridges. On Trafalgar it registers 4,703 images in 170 minutes, about 17× faster than Doppelgangers++.
Incremental structure-from-motion still collapses on repeated facades and symmetric landmarks. A wrong match can survive RANSAC, enter the view graph, and then poison pose estimation and triangulation. The usual wreckage is a duplicated building or a hallucinated wing.
Runtime is the other constraint. Bundle adjustment gets expensive as cameras pile up, and internet photo collections add near-duplicate images plus an over-dense set of pairwise edges. Prior work sits at two poles. Learned disambiguators such as Doppelgangers++ score huge numbers of candidate pairs and scale badly on large sets. Sparsifiers such as CamTrip drop the few bridges that actually hold the scene together, so the reconstruction splits.
The useful question is which edges deserve the expensive check.
HiSfM, from the Institute of Automation at the Chinese Academy of Sciences, splits the view graph into local support and global propagation.
Locally, each image keeps only its strongest neighbor by inlier count (top-1). Connected components of that sparse graph become communities. Intra-community edges are treated as mutually supporting and are not sent to the disambiguator.
Globally, edges that cross communities are bridges. On the community quotient graph the method packs K edge-disjoint spanning trees, still weighted by inliers. Candidates are scanned in Kruskal order. A bridge is kept only if it joins two DSU components, the community pair has not been used in an earlier tree, and Doppelgangers++ scores it at least τ=0.8. K is set to about one tree per 300 images. Packing K trees gives edge-connectivity at least K, so one failed bridge still leaves a backup path.
Leaf images inside each community are then attached to skeletal nodes without a second disambiguation pass. Reconstruction is two-stage: COLMAP on the verified skeleton first, then PnP registration and triangulation along intra-community edges, with a final global bundle adjustment.
The disambiguator is unchanged. What changes is the call site: only bridges that can move an error across communities.
All methods share COLMAP, features, and matches. Hardware is an i7-14700K and an RTX 3090.
On the Heinly and Yan ambiguity suites, vanilla COLMAP is wrong on every scene. CamTrip is fast and often incomplete or oversplit. DG++ is more reliable and about an order of magnitude slower. HiSfM is usually correct and in the same runtime band as CamTrip:
| Scene | COLMAP | CamTrip | DG++ | HiSfM |
| Berliner Dom | fail, 180 min | fail | 1606 imgs / 598.8 min | 1606 imgs / 17.9 min |
| Big Ben | fail | 365 / 2.4 min | 396 / 89.6 min | 394 / 3.1 min |
| Cereal | fail | 14 / 0.3 min | wrong model / 1.4 min | 25 correct / 0.2 min |
| Cup | fail | fail | 64 / 8.8 min | 64 / 0.4 min |
On Cereal, CamTrip registers about 56% of images and DG++ returns an incorrect model; HiSfM registers all 25 and is the fastest. On Big Ben the registered count matches DG++ while runtime is about 1/29, which the paper rounds to "over 25 times". All four methods fail on Oats. Brandenburg Gate, Church on Spilled Blood, and Radcliffe Camera still produce split models.
On 1DSfM and Photo Tourism, CamTrip fails on Trafalgar (5058 images) and Montreal Notre Dame. On Trafalgar, DG++ registers 3485 images in 3035 minutes; HiSfM registers 4703 in 170 minutes, about 17×. Piccadilly is 1894 images in 56 minutes against DG++ at 1860 / 550. On Roman Forum, raising K from 4 to 5 adds 15% runtime for 4 extra images, so the n/300 rule is enough for completeness.
Anyone building maps for localization or SLAM already knows the two failure modes: repeated structure wrecks the graph, and pairwise disambiguation is too slow to run everywhere. HiSfM is a scheduling answer. Spend the robustness budget on community bridges, freeze a scaffold, then pour the remaining cameras in. Code is released.
This is graph selection, not a new matcher. DG++ still judges the bridges; the call count drops from near-quadratic toward O(Kn). If the top-1 partition puts a truly ambiguous pair inside one community, those edges are never checked. Oats is the reminder.
The ablation only sweeps K. There is no systematic test of top-k=2 or 3. The local heuristic treats high inlier count as true geometry, which is exactly what repeated shelves and symmetric rooms produce. Bridge-level verification cannot clean contamination that already sits inside a community.
The DG++ threshold τ=0.8 is copied from the original paper, with no study of how it interacts with K. Quality is proxied by registered count, reprojection error, and track length, without an independent pose-error benchmark. Figure 1 quotes Trafalgar as 4706 images in 146 minutes; Table II quotes 5058 images and 170 minutes. Use the table.
CamTrip remains faster on many mid-size scenes. HiSfM is the better default when completeness matters. If the goal is a cheap sparse graph, sparsification is still in the race.