Degree-Equalized View-Graph Selection under Tight Pair Budgets
Authors: Minhyeok Im, Jongseong Brad Choi
Organizations: Department of Computer Science, State University of New York, Stony Brook, NY, United States · Department of Mechanical Engineering, State University of New York, Korea, Incheon, South Korea · Department of Computer Science, State University of New York, Korea, Incheon, South Korea · Department of Mechanical Engineering, State University of New York, Stony Brook, NY, United States
Fully matching all image pairs in Structure-from-Motion is quadratic in the number of images, so practical pipelines pass a budgeted subset to the final matching and reconstruction backend. One-shot selectors score candidates with image retrieval, cheap geometric probes, or a learned prior and finalize B pairs before full matching. Their priorities do not account for the degree already allocated to each image, which can concentrate edges on a few images. Across nine large 1DSfM internet photo collections at B=2N, the coverage top-B selector leaves 54% of covered images with realized degree at most two. Reconstruction can then fail even when the selected graph is nearly connected and almost fully verified. Our training-free greedy rule, Degree-Equalized Allocation (DEAL), exponentially downweights pairs whose endpoints are already well covered. On these collections, DEAL improves the one-shot selector built on the same prior (from 0.776 to 0.929) and matches the mean registered-image ratio of an SfM-supervised edge prior under the shared backend (0.929 vs 0.930), without training. On the largely saturated 38-scene standard benchmark suite, DEAL gives the highest mean among the evaluated training-free selectors (0.875 vs 0.858 one-shot).
Figures & tables
Figure 1: Yorkminster at B=2N with the same prior. Top- B allocation concentrates verified edges and registers 3% of images. DEAL spreads them across under-covered images and registers 93% . Red marks degree at most two.
selector
adds
mean ratio
DINOv2 top- B
appearance ranking
0.525
+ max-similarity MST
connectedness
0.710
+ mid-rank band fill
rank statistics
0.727
vocab-tree (SIFT-verified)
geometric verification
0.819
coverage top- B
geometric probe scoring
0.858
Wei et al. (learned prior)
learned global context
0.919
Table 1: Selection quality at B=2N , as mean registered-image ratio over 38 scenes. Rows below the midrule alter multiple factors.
Figure 2: DEAL overview. The prior scores each candidate pair once. DEAL selects by Equation 4 , matches the pick, and updates the graph. Degree decay lets an under-covered pair ( s=0.6 ) outrank a covered pair ( s=0.9 ). Red marks degree at most two.
Method
DTU
ETH3D
T&T
IMC
ALL
ALL ∖ IMC
fail
DINOv2 top- B
0.738
0.426
0.285
0.486
0.525
0.534
2/38
NetVLAD top- B
0.818
0.585
0.292
0.457
0.603
0.635
1/38
vocab-tree
0.986
0.730
0.966
0.573
0.819
0.875
4/38
coverage top- B
0.995
0.839
0.891
0.612
0.858
0.913
1/38
Wei et al. [ 43 ]
0.997
0.863
0.997
0.820
0.919
0.941
0/38
DEAL (DINOv2 prior)
1.000
0.757
0.979
0.563
0.834
0.895
2/38
Table 2: Mean registered-image ratio on 38 scenes at B=2N . Rows above the divider allocate by rank. ‘fail’ counts scenes below 0.1 , and bold marks the best training-free selector.
Figure 3: Realized Yorkminster view graphs at B=2N . Red marks degree at most two. DINOv2 top- B shows the full graph, and the other panels show the largest component. DEAL distributes verified edges more evenly than rank-based selectors.
top- B
learned
DEAL
Scene
DINOv2
coverage
Wei et al.
DINOv2
coverage
Alamo
0.323
0.938
0.947
0.950
0.950
Ellis Island
0.304
0.883
0.930
0.856
0.940
Gendarmenmarkt
0.195
0.919
0.947
0.956
0.971
Madrid Metropolis
0.302
0.940
0.947
0.933
0.956
Montreal Notre Dame
0.413
0.720
0.880
0.729
0.736
Table 3: Registered-image ratio on nine 1DSfM collections at B=2N . Values are three-repeat medians except DINOv2 top- B , and W/T/L uses unrounded values with the 0.01 tie rule. Bold marks the best per scene.
deg ≤ 2
Selector
selected
realized
deg ≥ 8
comp.
λ2
DINOv2 top- B
0.67
0.35
0.39
26.8
0.100
coverage top- B
0.54
0.54
0.15
2.6
0.007
Wei et al.
0.34
0.35
0.08
3.2
0.027
DEAL (DINOv2)
0.03
0.06
0.02
1.0
0.010
DEAL (coverage)
0.06
0.04
0.05
3.1
0.045
Table 4: Mean view-graph structure over nine 1DSfM scenes at B=2N . ‘selected’ and ‘realized’ report degree at most two before and after verification. Degree fractions use covered images, and λ2 uses the largest component.
1DSfM (9)
suite (38)
Variant
mean
min
mean
coverage top- B
0.776
0.030
0.858
hard threshold κ=4
0.897
0.716
0.840
hard threshold κ=2
0.925
0.731
0.861
DEAL, γ=0 (no decay)
0.793
0.027
0.839
DEAL, β=1 (no bridge multiplier)
0.946
0.882
0.875
Table 5: Ablation at B=2N , as three-repeat median registered-image ratios. ‘Min’ is the worst 1DSfM scene. Threshold controls use one assumed-success batch and still spend all B pairs.
Selector
DTU
ETH3D
IMC
ALL
DINOv2
0.718
0.420
0.379
0.529
NetVLAD
0.785
0.584
0.324
0.608
vocab-tree
0.953
0.694
0.377
0.729
coverage top- B
0.952
0.792
0.414
0.775
Wei et al.
0.961
0.791
0.553
0.807
DEAL (DINOv2 prior)
0.959
0.683
0.442
0.741
Table 6: Completeness-weighted rotation mAA at B=2N on 33 scenes with pose ground truth. Unregistered images count as failures. The five Tanks & Temples Advanced scenes are excluded because their reference camera poses are not public. The IMC reference is a COLMAP model.
Figure 4: Mean registered-image ratio over 38 scenes versus pair budget. DEAL and the 2N coverage top- B and Wei et al. points are three-repeat medians. The other points are single runs.
The pose graph is a core component of Structure-from-Motion (SfM), where images act as nodes and edges encode relative poses. Since geometric verification is expensive, SfM pipelines restrict the pose graph to a sparse set of candidate edges, making initialization critical. Existing methods rely on image retrieval to connect each image to its k nearest neighbors, treating pairs independently and ignoring global consistency. We address this limitation through the concept of edge prioritization, ranking candidate edges by their utility for SfM. Our approach has three components: (1) a GNN trained with SfM-derived supervision to predict globally consistent edge reliability; (2) multi-minimal-spanning-tree-based pose graph construction guided by these ranks; and (3) connectivity-aware score modulation that reinforces weak regions and reduces graph diameter. This globally informed initialization yields more reliable and compact pose graphs, improving reconstruction accuracy in sparse and high-speed settings and outperforming SOTA retrieval methods on ambiguous scenes. The ode and trained models are available at https://github.com/weitong8591/global_edge_prior.
Tong Wei, Giorgos Tolias, Jiri Matas +1
Visual Recognition Group, FEE, Czech Technical University in Prague · Computer Vision and Geometry Group, ETH Zurich · HUN-REN SZTAKI
Visual aliasing, also known as the doppelganger problem, remains a key challenge for structure-from-motion (SfM): visually similar but physically distinct surfaces can produce incorrect image matches and degrade reconstruction quality. Previous work mitigates this issue with geometry-aware foundation-model features, but places a heavy transformer classifier on top of the backbone, making large-scale disambiguation expensive. We introduce XDG, an efficient visual disambiguation model designed for scalable SfM. Our key observation is that a 3D foundation model already performs the cross-view geometric reasoning necessary for visual disambiguation, so doppelganger classification should adapt the backbone representation directly rather than relearn pair reasoning in a separate heavy decoder. XDG fine-tunes Depth Anything 3 with lightweight LoRA adapters and repurposes its camera tokens as compact pair-level classification tokens. A compact MLP head predicts whether a candidate image pair observes the same 3D surface. Extensive experiments show that XDG provides a favorable accuracy-efficiency tradeoff: it remains competitive with the state-of-the-art disambiguation method across pairwise and reconstruction benchmarks and delivers more than a 3x inference speedup. On individual LaMAR scenes containing thousands of images, XDG saves more than 10 hours of visual disambiguation processing. Code is available at https://github.com/xtcpete/xdg.
Gonglin Chen, Ben Southall, Hanyuan Xiao +8
1USC Institute for Creative Technologies · University of Southern California · 3SRI International
Global Structure-from-Motion (SfM) is an efficient paradigm for recovering camera poses and sparse 3D structure from unordered images. However, its reliance on scale-ambiguous epipolar geometry makes global positioning sensitive to noisy baseline estimates and weak view-graph constraints, while false edges from visually ambiguous pairs can further degrade reconstruction. We propose DGSfM, a depth-aware global SfM pipeline that uses monocular depth maps as a scalable prior while preserving explicit multi-view optimization. For each image pair, we use a depth-aware relative pose solver to convert scale-ambiguous epipolar constraints into scale-aware relative pose constraints. We further improve robustness through view-graph filtering and depth-consistency-based correspondence pruning, which suppress false edges and matches that remain plausible under epipolar geometry alone. Finally, global scale averaging and depth-guided pose-point initialization align monocular depth maps into a common reconstruction scale and provide stable initialization for global positioning and bundle adjustment. Experiments on ETH3D and IMC2021 show that DGSfM consistently improves over strong global SfM baselines across sparse and dense matching front-ends, achieving substantial gains in pose accuracy. Code and project page: https://dgsfm.github.io/.
Sithu Aung, Viktor Kocur, Yaqing Ding +2
VRG, FEE, Czech Technical University in Prague · FMPH, Comenius University in Bratislava · Southeast University +1