Pith. sign in

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 →

arxiv 2506.03667 v1 pith:MK56WWMB submitted 2025-06-04 cs.CV cs.AI

classification cs.CVcs.AI MSC 05C6968T4568R10
keywords Structure-from-Motionposeestimationdominatingsetgraphtheory6DobjectfeaturematchingOnedatasetreal-timeAR
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper argues that a Structure-from-Motion (SfM) model for object pose estimation contains many redundant reference images, and that an offline-chosen subset--a dominating set of the reference-image graph--can stand in for the entire model. The authors build a directed graph whose edge from $u$ to $v$ means image $u$ can estimate image $v$'s pose within a small error threshold, then keep only a small dominating set of images and the 3D points those images observe. On the OnePose benchmark they report pose-estimation throughput gains of 1.5 to 14.48 times across three matching pipelines, with reference-image counts down by factors of 17-23 and point clouds down by factors of 2.27-4, at a small accuracy cost. The practical significance is that speed-critical AR, VR, and robotics systems could preprocess the model once and drop a smaller model into their existing matcher.

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.

Watch

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

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 6 minor

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)
  1. [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.
  2. [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.
  3. [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.
  4. [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)
  1. [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.
  2. [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.
  3. [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.
  4. [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.
  5. [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.
  6. [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

0 steps flagged · score 0.0 of 10

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 2 free parameters · 4 assumptions · 0 invented entities

The central claim rests on two hand-set hyperparameters (the 0.05 edge threshold and the 1000-iteration budget), a coverage-transfer assumption between reference and query images, and the choice of a single dataset. No new entities are postulated. The free parameters are not tuned against the test split in the paper, but their insensitivity is not demonstrated either.

free parameters (2)
  • localization error threshold for edge construction = 0.05 (ratio to bounding-box diagonal)
    Algorithm 2 defines an edge when error(estimate_pose(ref=xi, query=xj)) < 0.05*d. This single threshold controls the entire graph structure and thus the dominating set. No sensitivity analysis is provided.
  • number of randomized greedy iterations = 1000
    Section 4.4: 'selecting 1000 iterations for optimal results'. The choice is arbitrary and no analysis of convergence is shown.
assumptions (4)
  • standard math The randomized greedy algorithm (Algorithm 1) finds a near-minimum dominating set.
    Relies on the known approximation property of greedy dominating set (Guha and Khuller [8]); used to compute D in Section 3.
  • 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.
    Core coverage-transfer premise stated in Section 3 and acknowledged as fragile in the Limitations section (Section 4.5), where boundary frames removed by the DS can hurt queries.
  • domain assumption Filtering SfM points to those observed by the dominating set images (Equation 4) retains the 2D-3D correspondences needed for accurate matching.
    Assumes points visible only from pruned images are not needed for pose estimation; the experiments test this but provide no theoretical justification.
  • domain assumption The OnePose dataset's first video per object for SfM and last video for validation provides independent training and test views.
    Standard practice from OnePose [26], but the paper does not verify view coverage; the Limitations section notes coverage issues.

how reviews work

0 comments
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 reproduced from arXiv: 2506.03667 by the authors.

Figure 1
Figure 1. Impact of applying the dominating set on Structure from Motion (SfM). Each reference image is depicted along with [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 3
Figure 3. figure 3. Our preprocessing method sits between initial SfM and [PITH_FULL_IMAGE:figures/full_fig_p002_3.png] view at source ↗
Figure 2
Figure 2. Illustration of a graph with a dominating set. The [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figures from the paper (3 more)
Figure 3
Figure 3. Figure 3: A generalized SfM-based pose estimation pipeline. Our preprocessing method sits between initial SfM and matcher, [PITH_FULL_IMAGE:figures/full_fig_p004_3.png]
Figure 4
Figure 4. Figure 4: Visualization of the dominating set of SfM repre [PITH_FULL_IMAGE:figures/full_fig_p004_4.png]
Figure 5
Figure 5. Figure 5: A frame in which the detected pose is visualized as [PITH_FULL_IMAGE:figures/full_fig_p006_5.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

34 extracted references · 24 canonical work pages

  1. [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

  2. [2]

    Booij, Z

    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. [3]

    Prabhat Kumar Chand, Anisur Rahaman Molla, and Sumathi Sivasubramaniam

  4. [4]

    Daniel DeTone, Tomasz Malisiewicz, and Andrew Rabinovich. 2018. SuperPoint: Self-Supervised Interest Point Detection and Description. arXiv:1712.07629 [cs.CV]

  5. [5]

    Abdol-Hossein Esfahanian. [n.d.]. Connectivity Algorithms. http://www.cse.msu. edu/~cse835/Papers/Graph_connectivity_revised.pdf Accessed: Jan 22, 2024

  6. [6]

    Fischler and Robert C

    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

  7. [7]

    Pierre Gleize, Weiyao Wang, and Matt Feiszli. 2023. SiLK – Simple Learned Keypoints. arXiv:2304.06194 [cs.CV]

  8. [8]

    Guha and S

    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
  1. [9]

    Richard Hartley and Andrew Zisserman. 2004. Multiple View Geometry in Com- puter Vision (2 ed.). Cambridge University Press, Cambridge, UK

  2. [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

  3. [11]

    Xingyi He, Jiaming Sun, Yuang Wang, Di Huang, Hujun Bao, and Xiaowei Zhou

  4. [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...

  5. [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

  6. [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

  7. [15]

    Philipp Lindenberger, Paul-Edouard Sarlin, and Marc Pollefeys. 2023. LightGlue: Local Feature Matching at Light Speed. In ICCV

  8. [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

  9. [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

  10. [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

  11. [19]

    Paul-Edouard Sarlin, Cesar Cadena, Roland Siegwart, and Marcin Dymczyk. 2019. From Coarse to Fine: Robust Hierarchical Localization at Large Scale. In CVPR

  12. [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]

  13. [21]

    Johannes Lutz Schönberger and Jan-Michael Frahm. 2016. Structure-from-Motion Revisited. In Conference on Computer Vision and Pattern Recognition (CVPR)

  14. [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)

  15. [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...

  16. [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

  17. [25]

    Jiaming Sun, Zehong Shen, Yuang Wang, Hujun Bao, and Xiaowei Zhou. 2021. LoFTR: Detector-Free Local Feature Matching with Transformers. CVPR (2021)

  18. [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)

  19. [27]

    Alemu Leulseged Tesfaye. 2020. Constrained Dominant sets and Its applications in computer vision. arXiv:2002.06028 [cs.CV]

  20. [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

  21. [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

  22. [30]

    He Yisheng, Wang Yao, Fan Haoqiang, Chen Qifeng, and Sun Jian. 2022. FS6D: Few-Shot 6D Pose Estimation of Novel Objects. CVPR (2022)

  23. [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

  24. [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

  25. [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

  26. [2023]

    arXiv:2309.02200 [cs.DC]

    Run for Cover: Dominating Set via Mobile Agents. arXiv:2309.02200 [cs.DC]

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.