REVIEW 4 major objections 6 minor 34 references
Accelerating SfM-based Pose Estimation with Dominating Set
T0 review · 4 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read Replacing an SfM model with a dominating set of its reference-image graph speeds pose estimation by 1.5 to 14.48 times across multiple matchers while keeping accuracy close.
desk verdict A simple, honest heuristic paper: dominating-set pruning of SfM models gives real speedups and beats random sampling on accuracy, but the accuracy-retention claim is weaker than the abstract suggests and the transfer-coverage assumption needs scrutiny. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the directed reference-image graph built by Algorithm 2: vertices are the SfM reference images and a directed edge $x_i \to x_j$ is added when estimating $x_j$'s pose using $x_i$ as the reference yields a localization error below $0.05\,d$, where $d$ is the longest diagonal of the object's bounding box. On this graph the paper runs a randomized greedy dominating-set algorithm (Algorithm 1) many times, keeps the smallest dominating set found, and constructs the reduced SfM model $S'$ by keeping exactly those 3D points whose observing reference images intersect the dominating set. The point filter is what shrinks the point cloud, and the edge threshold is what encodes 'one view can reliably localize another'.
What would settle it
Evaluate the preprocessing on query videos filmed from the hemisphere opposite to the SfM training views: if the transfer-coverage assumption fails, accuracy should collapse specifically on frames whose visible object region overlaps only with reference images the dominating set removed, while random sampling the same number of images should not show the same concentrated failure.
Extended reading notes
Core claim
The paper's central claim is that the pose-estimation utility of an SfM model is concentrated in a small set of reference images: an approximately minimum dominating set of the directed graph defined by mutual pose-estimation success. Every reference image is either in the dominating set or has its pose accurately estimated by one that is, so queries that could be localized against the full model should remain localizable against the subset. The authors emphasize that the preprocessing is agnostic to the downstream feature matcher, and they support the claim by comparing against random sampling of the same number of reference images, which performs markedly worse; the dominating-set selection nearly preserves the accuracy of OnePose, OnePose++, and exhaustive SuperPoint-SuperGlue and SuperPoint-LightGlue matching while multiplying frames per second.
Load-bearing premise
The load-bearing premise is that an edge between two reference images--one view can estimate the other's pose within $0.05d$ of the bounding-box diagonal--predicts that the chosen dominating set will also cover the query images actually seen at runtime; the paper acknowledges in its limitations that queries overlapping mainly with removed boundary frames lose accuracy.
Editorial extensions
If this is right
- Any existing SfM-based pose estimator can use the dominating-set model as a drop-in replacement, because the preprocessing sits between SfM construction and the feature matcher.
- Reference-image counts fall by factors of 17-23 and point clouds by factors of 2.27-4, so per-frame feature matching and memory footprint shrink with them.
- Random subsets of equal size do not retain the same accuracy, indicating that the coverage structure of the dominating set, not merely fewer images, is what preserves pose estimates.
- With a mean dominating-set size near four reference images per object in the OnePose data, most objects appear to be localizable from a very small model, making the approach relevant for embedded or real-time settings.
Reading between the lines
- Implicit in the result is that the dominating set could act as a fast first stage inside a tracker: estimate from the small model, and call the full model only when the estimate is uncertain, recovering some of the small accuracy loss.
- Systematically varying the $0.05d$ edge threshold across objects would map the speed-accuracy frontier and let practitioners predict how many reference images can be removed for a given object and camera path.
- The coverage assumption is validated only on queries similar to the training views; the paper's own limitation section warns that boundary frames can be removed, so a direct test on queries from an untrained hemisphere would quantify how far the dominating set generalizes.
- The same graph could be combined with retrieval-based localization: match a query to the dominating-set cluster by global descriptor, then verify with local features.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes a preprocessing method for SfM-based object pose estimation. A directed graph is built over the reference images, with an edge from u to v if estimating v's pose using u as the reference succeeds within a 0.05d localization-error threshold. A small (approximately minimum) dominating set D is then found with a randomized greedy algorithm, and the optimized SfM model keeps only the reference images in D and the 3D points observed by D. The method is evaluated on the OnePose dataset with OnePose, OnePose++, and exhaustive SuperPoint+SuperGlue / SuperPoint+LightGlue matching. The paper reports speedups of 1.5-14.48x, reference-image reductions by factors of 17-23, point reductions by factors of 2.27-4, and states that accuracy is retained without significant loss.
Significance. If the accuracy-retention claim were fully established, the contribution would be practically useful: a matcher-agnostic offline pruning step that substantially improves speed, with a clear advantage over random sampling of the same number of reference images. The reported speedup and reduction numbers are internally consistent with Table 1, and the random-sampling control is a sensible baseline. The main weakness is that accuracy retention is only partially demonstrated: several accuracy drops in Table 1 are large, and the coverage argument is not validated on held-out query images. The paper does provide a concrete, simple algorithm and a reproducible experimental setup modulo the measurement details noted below.
major comments (4)
- [Section 3 / Algorithm 2 / Section 4.5] The dominating set is selected using edges defined only between reference images, but the method is deployed on held-out query images. No argument or experiment connects reference-set dominance to query-image coverage, and the paper's own limitation paragraph concedes that queries overlapping mainly with removed boundary frames suffer low accuracy. The scale of the loss is visible in Table 1: for Exhaustive SuperPoint+LightGlue, ADD-0.1d drops from 94.24 to 83.46 and 1deg-1cm accuracy from 61.05 to 51.59. To support the 'without losing significant accuracy' claim, the authors should report per-object/per-query accuracy conditioned on whether the query's visible region overlaps the surviving dominating set, and quantify how often the conceded failure mode occurs.
- [Section 4.4 / Section 4.3] The graph edges are defined using SuperPoint+SuperGlue at a 0.05d threshold, while the evaluation uses OnePose, OnePose++, and LightGlue and stricter metrics (1deg-1cm, ADD-0.1d). A 0.05d edge certifies only coarse localizability under one matcher; it does not by itself imply that the selected D will be sufficient for other matchers at the reported accuracy thresholds. The paper should verify transfer either by reconstructing the graph with each matcher/metric or by reporting query-side coverage statistics that directly test whether D covers held-out queries.
- [Section 4.1 / Equation (4)] For OnePose and OnePose++, 3D point descriptors are computed as averages over the reference images that observe each point. After pruning to S', which changes the reference set to D, these descriptor averages change. The graph used to select D was built from the original model, and the paper does not analyze whether the reference-reference edges that justify D persist after the descriptors are recomputed on D. The authors should clarify how OnePose/OnePose++ descriptors are handled after pruning and report whether this changes the accuracy results.
- [Table 1 / Section 4.4] The FPS measurements are not sufficiently specified to be reproduced: it is unclear whether the reported FPS includes feature extraction, matching, PnP, or the full pipeline; whether times are averaged per video or per object; and what GPU details besides the A6000 are relevant. There are no error bars or per-sequence breakdowns, which is important because the dominating set sizes range from 1 to 35 and accuracy may vary substantially across objects. Please provide the measurement protocol and per-object variability.
minor comments (6)
- [Abstract / Conclusion] The phrase 'without losing significant accuracy' is too strong given the drops in Table 1, e.g., 8-11 point losses in ADD-0.1d for the exhaustive methods; suggest rewording to 'with a moderate accuracy cost' or presenting the result explicitly as a speed-accuracy trade-off.
- [Section 2.3] The paper defines dominating sets for undirected graphs, but Algorithm 2 produces directed edges; please specify that the algorithm computes an out-dominating set and define the domination direction consistently with the directed edge semantics.
- [Figure 2 caption] The caption refers to 'Figures 2b and 2c' with inconsistent formatting; also, the subfigure labels are not visible in the text version.
- [Algorithm 1 / Section 4.4] The number of randomized greedy iterations (1000) appears only in the text; consider moving it into the algorithm description or a table for reproducibility.
- [Section 4.2] The sentence 'comprises 80 distinct objects and 301 videos for validation purposes' is slightly confusing because the next sentence says only the last video per object is used; clarify the total number of test videos actually evaluated.
- [Equation (8)] The geodesic error formula should state that the argument to arccos is clamped to [-1,1] and that it represents the rotation angle between the estimated and ground-truth rotations.
Circularity Check
No significant circularity: the accuracy-retention claim is empirically tested on held-out video, and the speedups are measured consequences of input reduction, not derived from the selection criterion.
full rationale
The paper's central claim is that a dominating-set-based preprocessing of an existing SfM model speeds up pose estimation without significant accuracy loss. No circular step is present in the claimed derivation chain. The graph in Algorithm 2 is constructed from reference-image-to-reference-image pose estimates, and the dominating set is selected from that graph. However, the accuracy retention is not derived from that graph by construction; it is measured on the OnePose test split using the last video of each object, while the SfM model and reference graph are built from the first video (Section 4.2). This is a held-out evaluation, so the accuracy numbers are empirical predictions rather than fitted outputs. Each pose estimator (OnePose, OnePose++, exhaustive SuperPoint-SuperGlue, exhaustive SuperPoint-LightGlue) is evaluated both with and without the dominating set, and the dominating set is also compared against random sampling of the same number of reference images. That random-sampling baseline is an independent control showing that the selected set, not just the cardinality reduction, drives the accuracy retention. The speedup figures are direct FPS measurements after reducing reference images and points; they are not derived from a fitted parameter or from the edge-definition equation, so they cannot be circular. The paper contains no load-bearing self-citations: the references to prior dominating-set SfM work ([10], [13]) are used to contrast the present contribution, not to justify the central result. Finally, Section 4.5 explicitly concedes a failure mode when query images overlap mainly with removed boundary reference images, which confirms that the transfer-coverage assumption is an empirical risk rather than a tautological guarantee. Overall, the manuscript is self-contained against an external benchmark and does not reduce to its own inputs.
Assumptions & free parameters
free parameters (2)
- localization error threshold for edge construction =
0.05 (ratio to bounding-box diagonal)
- number of randomized greedy iterations =
1000
assumptions (4)
- standard math The randomized greedy algorithm (Algorithm 1) finds a near-minimum dominating set.
- domain assumption If a reference image u can estimate the pose of another reference image v within the threshold, then the dominating set covering all reference images also covers unseen query images.
- domain assumption Filtering SfM points to those observed by the dominating set images (Equation 4) retains the 2D-3D correspondences needed for accurate matching.
- domain assumption The OnePose dataset's first video per object for SfM and last video for validation provides independent training and test views.
Cite this review
Pith. "Pith review of Accelerating SfM-based Pose Estimation with Dominating Set." pith.science (2026). https://pith.science/paper/MK56WWMB
@misc{pith2026250603667,
author = {Pith},
title = {Pith review of: Accelerating SfM-based Pose Estimation with Dominating Set},
year = {2026},
howpublished = {\url{https://pith.science/paper/MK56WWMB}},
note = {Machine review of arXiv:2506.03667}
}
read the original abstract
This paper introduces a preprocessing technique to speed up Structure-from-Motion (SfM) based pose estimation, which is critical for real-time applications like augmented reality (AR), virtual reality (VR), and robotics. Our method leverages the concept of a dominating set from graph theory to preprocess SfM models, significantly enhancing the speed of the pose estimation process without losing significant accuracy. Using the OnePose dataset, we evaluated our method across various SfM-based pose estimation techniques. The results demonstrate substantial improvements in processing speed, ranging from 1.5 to 14.48 times, and a reduction in reference images and point cloud size by factors of 17-23 and 2.27-4, respectively. This work offers a promising solution for efficient and accurate 3D pose estimation, balancing speed and accuracy in real-time applications.
Figures
Figures from the paper (3 more)
Reference graph
Works this paper leans on
-
[1]
Herbert Bay, Tinne Tuytelaars, and Luc Van Gool. 2006. SURF: Speeded Up Robust Features. In Computer Vision – ECCV 2006 , Aleš Leonardis, Horst Bischof, and Axel Pinz (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 404–417
work page 2006
-
[2]
O. Booij, Z. Zivkovic, and B. Kröse. 2009. Efficient data association for view based SLAM using connected dominating sets. Robotics and Autonomous Systems 57, 12 (2009), 1225–1234. https://doi.org/10.1016/j.robot.2009.06.006 Inside Data Association
-
[3]
Prabhat Kumar Chand, Anisur Rahaman Molla, and Sumathi Sivasubramaniam
-
[4]
Daniel DeTone, Tomasz Malisiewicz, and Andrew Rabinovich. 2018. SuperPoint: Self-Supervised Interest Point Detection and Description. arXiv:1712.07629 [cs.CV]
arXiv 2018
-
[5]
Abdol-Hossein Esfahanian. [n.d.]. Connectivity Algorithms. http://www.cse.msu. edu/~cse835/Papers/Graph_connectivity_revised.pdf Accessed: Jan 22, 2024
work page 2024
-
[6]
Martin A. Fischler and Robert C. Bolles. 1981. Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography. Commun. ACM 24, 6 (jun 1981), 381–395. https://doi.org/10.1145/ 358669.358692
arXiv 1981
-
[7]
Pierre Gleize, Weiyao Wang, and Matt Feiszli. 2023. SiLK – Simple Learned Keypoints. arXiv:2304.06194 [cs.CV]
arXiv 2023
-
[8]
S. Guha and S. Khuller. 1998. Approximation Algorithms for Connected Dominat- ing Sets. Algorithmica 20, 4 (1998), 374–387. https://doi.org/10.1007/PL00009201
Show all 34 references
-
[9]
Richard Hartley and Andrew Zisserman. 2004. Multiple View Geometry in Com- puter Vision (2 ed.). Cambridge University Press, Cambridge, UK
2004
-
[10]
Michal Havlena, Akihiko Torii, and Tomas Pajdla. 2010. Efficient Structure from Motion by Graph Optimization, Vol. 6312. 100–113. https://doi.org/10.1007/978- 3-642-15552-9_8
2010 doi
-
[11]
Xingyi He, Jiaming Sun, Yuang Wang, Di Huang, Hujun Bao, and Xiaowei Zhou
-
[12]
Bradski, and Nassir Navab
Stefan Hinterstoißer, Vincent Lepetit, Slobodan Ilic, Stefan Holzer, Kurt Konolige, Gary R. Bradski, and Nassir Navab. 2012. Model Based Training, Detection and Pose Estimation of Texture-Less 3D Objects in Heavily Cluttered Scenes. InAsian Conference on Computer Vision . http...
2012
-
[13]
San Jiang, Qingquan Li, Wanshou Jiang, and Wu Chen. 2022. Parallel Structure From Motion for UAV Images via Weighted Connected Dominating Set. IEEE Transactions on Geoscience and Remote Sensing 60 (2022), 1–13. https://doi.org/ 10.1109/tgrs.2022.3222776
2022
-
[14]
Vincent Lepetit, Francesc Moreno-Noguer, and Pascal Fua. 2009. EPnP: An Accurate O(n) Solution to the PnP Problem. International Journal of Computer Vision 81, 2 (2009), 155–166. https://doi.org/10.1007/s11263-008-0152-6
2009 doi
-
[15]
Philipp Lindenberger, Paul-Edouard Sarlin, and Marc Pollefeys. 2023. LightGlue: Local Feature Matching at Light Speed. In ICCV
2023
-
[16]
Yuan Liu, Yilin Wen, Sida Peng, Cheng Lin, Xiaoxiao Long, Taku Komura, and Wenping Wang. 2022. Gen6D: Generalizable Model-Free 6-DoF Object Pose Estimation from RGB Images. In ECCV
2022
-
[17]
David G. Lowe. 2004. Distinctive Image Features from Scale-Invariant Keypoints. International Journal of Computer Vision 60 (2004), 91–110. https://api.semantic scholar.org/CorpusID:174065
2004
-
[18]
Cristanel Razafimandimby, Valeria Loscrì, Anna Maria Vegni, and Abderrahim Benslimane. 2019. NeuroDominating Set Scheme for a Fast and Efficient Robot Deployment in Internet of Robotic Things. Ad Hoc Networks 86 (2019), 36–45. https://doi.org/10.1016/j.adhoc.2018.08.016 hal-01864325
2019 doi
-
[19]
Paul-Edouard Sarlin, Cesar Cadena, Roland Siegwart, and Marcin Dymczyk. 2019. From Coarse to Fine: Robust Hierarchical Localization at Large Scale. In CVPR
2019
-
[20]
Paul-Edouard Sarlin, Daniel DeTone, Tomasz Malisiewicz, and Andrew Rabi- novich. 2020. SuperGlue: Learning Feature Matching with Graph Neural Net- works. arXiv:1911.11763 [cs.CV]
2020 arXiv
-
[21]
Johannes Lutz Schönberger and Jan-Michael Frahm. 2016. Structure-from-Motion Revisited. In Conference on Computer Vision and Pattern Recognition (CVPR)
2016
-
[22]
Johannes Lutz Schönberger, Enliang Zheng, Marc Pollefeys, and Jan-Michael Frahm. 2016. Pixelwise View Selection for Unstructured Multi-View Stereo. In European Conference on Computer Vision (ECCV)
2016
-
[23]
Jamie Shotton, Ben Glocker, Christopher Zach, Shahram Izadi, Antonio Criminisi, and Andrew Fitzgibbon. 2013. Scene Coordinate Regression Forests for Camera Relocalization in RGB-D Images. In 2013 IEEE Conference on Computer Vision and Pattern Recognition. 2930–2937. https://do...
2013 doi
-
[24]
Stojmenovic, M
I. Stojmenovic, M. Seddigh, and J. Zunic. 2002. Dominating sets and neigh- bor elimination-based broadcasting algorithms in wireless networks. IEEE Transactions on Parallel and Distributed Systems 13, 1 (2002), 14–25. https: //doi.org/10.1109/71.980024
2002 doi
-
[25]
Jiaming Sun, Zehong Shen, Yuang Wang, Hujun Bao, and Xiaowei Zhou. 2021. LoFTR: Detector-Free Local Feature Matching with Transformers. CVPR (2021)
2021
-
[26]
Jiaming Sun, Zihao Wang, Siyu Zhang, Xingyi He, Hongcheng Zhao, Guofeng Zhang, and Xiaowei Zhou. 2022. OnePose: One-Shot Object Pose Estimation without CAD Models. CVPR (2022)
2022
-
[27]
Alemu Leulseged Tesfaye. 2020. Constrained Dominant sets and Its applications in computer vision. arXiv:2002.06028 [cs.CV]
2020 arXiv
-
[28]
Alzoubi, and Ophir Frieder
Peng-Jun Wan, Khaled M. Alzoubi, and Ophir Frieder. 2002. Distributed construc- tion of connected dominating set in wireless ad hoc networks. Mobile Networks and Applications 9, 2 (2002), 141–149
2002
-
[29]
Feng Wang, Erika Camacho, and Kuai Xu. 2009. Positive Influence Dominating Set in Online Social Networks. In Combinatorial Optimization and Applications, Ding- Zhu Du, Xiaodong Hu, and Panos M. Pardalos (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 313–321
2009
-
[30]
He Yisheng, Wang Yao, Fan Haoqiang, Chen Qifeng, and Sun Jian. 2022. FS6D: Few-Shot 6D Pose Estimation of Novel Objects. CVPR (2022)
2022
-
[31]
Jiguo Yu, Nannan Wang, Guanghui Wang, and Dongxiao Yu. 2013. Connected dominating sets in wireless ad hoc and sensor networks – A comprehensive survey. Computer Communications 36, 2 (2013), 121–134. https://doi.org/10.101 6/j.comcom.2012.10.005
2013
-
[32]
Feng Zou, Xu Li, Deying Kim, Weili Wu, and Ding-Zhu Du. 2011. A survey on algorithms for dominating set problems in wireless sensor networks.International Journal of Distributed Sensor Networks 7, 1 (2011), 1–12
2011
-
[2022]
In Advances in Neural Information Processing Systems
OnePose++: Keypoint-Free One-Shot Object Pose Estimation without CAD Models. In Advances in Neural Information Processing Systems
-
[2023]
arXiv:2309.02200 [cs.DC]
Run for Cover: Dominating Set via Mobile Agents. arXiv:2309.02200 [cs.DC]
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.