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.