Pith. sign in

REVIEW 3 major objections 5 minor 29 references

DS-SAC: Density Search for Sample Consensus

T0 review · 3 major / 5 minor · reviewed 2026-07-11 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A deterministic residual-density search finds better geometric models than random sampling, faster.

desk verdict Practical deterministic RANSAC drop-in that wins AUC and speed on the three standard multi-view tasks; density heuristic works on modern matchers but its failure boundary is unmapped. read the letter →

arxiv 2607.03972 v1 pith:2VORCESP submitted 2026-07-04 cs.CV

Suraj Thapa , Muhammad Aminul Islam This is my paper
classification cs.CV
keywords RANSACrobustestimationsampleconsensushomographyfundamentalmatrixessentialdeterministicresidualdensitysearch
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

Robust model fitting from noisy point matches still usually means RANSAC: guess tiny random subsets until one looks good. This paper argues that you can drop the randomness. Start from a model fit to the points you have, then repeatedly shrink and expand the set of nearest residuals (forward and backward search) so the estimate walks into denser regions of residual space; when local search stalls, split the points by the sign of their residuals and recurse on each half. The resulting method, DS-SAC, has polynomial cost in the number of points and, on tens of thousands of real image pairs for homography and epipolar geometry, reports higher pose-recall AUC, competitive or lower median pose error, and lower runtime than standard RANSAC variants under a fixed iteration budget. A sympathetic reader cares because many vision pipelines are bottlenecked by fragile, slow consensus steps; a deterministic, density-driven alternative that is both more accurate and cheaper would change how those pipelines are built.

What carries the argument

Density Search Sample Consensus (DS-SAC): forward/backward percentile residual search plus recursive signed-residual partitioning. It replaces stochastic minimal sampling with deterministic local density refinement and residual-space bipartition so that inlier-dense support sets are located without exhaustive model-space search.

What would settle it

On the same SuperPoint+LightGlue correspondences and fixed-budget protocol, if DS-SAC's AUC at 5/10/20 degrees and median pose error on ScanNet1500, PhotoTourism, LaMAR, 7Scenes, ETH3D, and KITTI fail to beat or match LO-RANSAC and GC-RANSAC for homography, fundamental, and essential matrices, the central empirical claim fails.

Watch

Extended reading notes

Core claim

DS-SAC establishes that high-consensus geometric models can be found deterministically by searching dense residual regions: initialize from all points in a partition, refine by percentile-based forward then backward residual selection plus inlier re-estimation, and globally explore by recursive bipartition on signed residuals until a minimum partition size, finally selecting by inlier count with MSAC tie-break. On large multi-dataset benchmarks this yields higher AUC at 5/10/20 degrees, competitive or better median pose error, and faster runtimes than RANSAC, MAGSAC, LO-RANSAC, and GC-RANSAC for homography, fundamental, and essential matrix estimation.

Load-bearing premise

Inliers of a good model form a dense enough region in residual space that shrinking from a full-set least-squares start, then splitting by residual sign and repeating, will find high-consensus models without exhaustive search.

Editorial extensions

If this is right

  • Homography, fundamental, and essential matrix estimation can use a fixed deterministic search instead of random minimal samples under high outlier ratios.
  • Runtime for consensus on large match sets can drop while pose-recall AUC rises, because search cost is polynomial rather than exploding with outlier rate.
  • Local optimization no longer needs a lucky RANSAC hypothesis as a trigger; residual-density refinement is the whole procedure.
  • MSAC can serve only as a secondary tie-break once inlier count is maximized, keeping the objective aligned with classical consensus.
  • Polynomial complexity (O(N^2) worst case, O(N log N) when balanced) makes the method a practical alternative where exhaustive deterministic consensus is too expensive.

Reading between the lines

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

  • The same residual-density and signed-split pattern may transfer to other algebraic models (e.g., trifocal tensor or plane-and-parallax) that admit a signed residual and a least-squares solver.
  • If percentile step and minimum partition size can be scheduled adaptively from residual histograms, iteration count could fall further without losing the dense-region guarantee.
  • Hybrid use—DS-SAC as a deterministic seed followed by a short LO or graph-cut polish—could combine its global residual exploration with spatial coherence that pure density search does not encode.
  • Failure modes when multiple dense clusters of similar residual magnitude exist (structured outliers) would stress-test whether bipartition alone separates the true consensus set.
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

3 major / 5 minor

Summary. The paper proposes DS-SAC, a deterministic robust estimator for geometric models (homography, fundamental matrix, essential matrix). Instead of RANSAC-style random minimal sampling, it initializes a model by least-squares on the current point set, then performs forward search (shrinking percentile support and re-fitting) and backward search (expanding from the local best), with recursive bipartition of the support by the sign of a model residual (Algorithms 1–4). Model selection uses inlier count with MSAC as tie-breaker, plus a final multi-threshold post-tuning stage. The authors give a binary-tree complexity argument of O(N²) worst-case and O(N log N) balanced, and report higher pose AUC, competitive/lower median pose error, and lower wall-clock time than OpenCV RANSAC, MAGSAC, LO-RANSAC, and GC-RANSAC on 39,592 SuperPoint+LightGlue pairs from six public datasets (Tables 2–4), with sensitivity and ablation studies (Figs. 1–2, Table 5).

Significance. If the empirical gains hold under broader conditions, DS-SAC is a practically useful deterministic alternative to stochastic consensus methods for standard multi-view geometry tasks: it avoids iteration-count tuning, has polynomial (not exponential-in-outlier-ratio) cost, and is faster than strong LO/GC-RANSAC baselines while improving AUC. Strengths that should be credited include the large multi-dataset, multi-model evaluation protocol aligned with IMC-style pose AUC, the explicit complexity analysis, the ablation of backward search and post-tuning, and the commitment to release code. The work sits between LO-style residual refinement and expensive global consensus maximizers; that positioning is clear and of interest to the geometric vision community.

major comments (3)
  1. [§3, Algorithm 2, Tables 2–4] §3 (motivating observation) and Algorithm 2: the method starts from θ_init = arg min_θ Σ_{x_i∈S} d²(x_i,θ) on the full current partition, then shrinks percentiles of residual-ordered points. The central claim that density search reliably finds high-consensus models therefore depends on the residual landscape of this (possibly heavily contaminated) least-squares start still having a dense inlier basin that percentile shrinking can track. The manuscript never measures the inlier-ratio regime in which this holds: all 39,592 pairs use SuperPoint+LightGlue, and neither synthetic outlier sweeps nor weaker matchers appear. Without such stress tests (or a bound), the superiority in Tables 2–4 may not generalize beyond the tested residual-density regime, which is load-bearing for presenting DS-SAC as a general alternative to RANSAC.
  2. [§5.2, Tables 2–4] §5.2 Experimental Setup: stochastic baselines are fixed at 1000 iterations while DS-SAC runs an adaptive number of full least-squares refits (~465–490 reported). Wall-clock times favor DS-SAC, which is useful, but the accuracy comparison is not an equal-compute or equal-hypothesis budget study, and MAGSAC’s reported times (0.278–0.402 s) are outliers relative to the others. A short equal-time or equal-iteration-cost protocol (or reporting of inlier-ratio stratified results) is needed to support the claim of consistently higher AUC at lower cost.
  3. [§4] §4 Computational Complexity: the O(N²) worst-case derivation sets Δp = 1/N and builds an extremely unbalanced tree of height N−1. Operating parameters are Δp = 0.03 and p_min = 0.2, under which the number of refits is far smaller and roughly linear in the number of partitions. The analysis should be restated for the actual parameter regime used in experiments (and ideally matched to the observed ~480 iterations), so that the “polynomial and efficient” claim is not left resting on an unrealistic step size.
minor comments (5)
  1. [Table 1, Algorithms 2–3] Notation table and Algorithms 2–3: P vs X vs S is used inconsistently for the full set vs current partition; Algorithm 2 writes ∀x_i ∈ P while the input is S. Unify symbols.
  2. [§3.3, Algorithm 4] Algorithm 4 exception handling for partition boundary outside the current space is described in text but omitted from the pseudocode; a short note or branch would aid reproducibility.
  3. [§5.3–5.6] Figs. 1–2 and Tables 2–4 report point estimates only; even simple per-dataset standard deviations or bootstrap intervals on AUC would strengthen the multi-dataset average claim.
  4. [§2] Related work could more explicitly contrast residual-percentile search with PROSAC’s quality-ordered sampling and with LO-RANSAC’s inlier re-estimation, to clarify novelty beyond “deterministic LO-style refinement.”
  5. [Throughout] Minor typos/grammar: “bases on the sign” (Alg. 1), “Nist´ er”, “re-scan the space in the forward direction without the inlier optimization step” could be tightened for clarity.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: DS-SAC is a self-contained algorithmic procedure whose empirical claims rest on external public benchmarks, not on definitions or self-fitted quantities.

full rationale

The paper proposes a deterministic search procedure (forward/backward residual-percentile refinement plus signed-residual bipartition, Algorithms 1–4) motivated by the observation that inliers form dense residual regions. Complexity bounds (O(N^{2}) worst-case, O(N log N) balanced) are derived directly from the binary-tree structure of the partitions and the fixed step size Δp; they are not identities of free parameters. Model selection uses the standard maximal-consensus objective with MSAC tie-breaking; no parameter is fitted to a data subset and then re-presented as a prediction. All experimental claims (higher AUC, competitive median error, lower runtime on Tables 2–4) are obtained by running the fixed-parameter algorithm against public datasets and standard baselines (OpenCV RANSAC, MAGSAC, LO-RANSAC, GC-RANSAC) under a common 1000-iteration budget; the numbers are therefore external measurements, not algebraic consequences of the method’s own definitions. There are no load-bearing self-citations, uniqueness theorems imported from the authors, or renamed known results. The derivation chain is therefore free of the six circularity patterns.

Assumptions & free parameters 3 free parameters · 3 assumptions · 0 invented entities

The central performance claim rests on a small set of hand-chosen search hyperparameters, the domain assumption that inliers are dense in residual space, and standard least-squares / consensus machinery; no new physical entities are postulated.

free parameters (3)
  • percentile step size Δp = 0.03
    Fixed to 0.03 after sensitivity analysis on the evaluation tasks; controls how finely the residual kernel shrinks/expands and directly affects iteration count and accuracy.
  • minimum partition size pmin = 0.2
    Fixed to 0.2 after the same sensitivity study; stops recursion and therefore bounds both accuracy and runtime.
  • noise scale σ for inlier thresholds = 0.3
    Set to 0.3 so that T = 3.84σ² (epipolar) or 5.99σ² (homography); chosen by the authors rather than estimated per image pair.
assumptions (3)
  • domain assumption Inliers of a good model form a dense region in residual space that can be reached by successive percentile shrinking from a full-set least-squares fit.
    Stated as the motivating observation opening §3; without it the forward-search trajectory has no reason to improve consensus.
  • ad hoc to paper Signed residual bipartition of the current support yields two subspaces that together cover the interesting high-consensus models.
    Introduced in §3.3 and Algorithm 4; the paper supplies no formal guarantee that the split does not discard the global optimum.
  • domain assumption Maximal consensus (inlier count, MSAC tie-break) is the appropriate objective for geometric model selection.
    Standard in the RANSAC literature the paper cites; used throughout scoring and model selection.

how reviews work

0 comments
Cite this review

Pith. "Pith review of DS-SAC: Density Search for Sample Consensus." pith.science (2026). https://pith.science/paper/2VORCESP

@misc{pith2026260703972,
  author       = {Pith},
  title        = {Pith review of: DS-SAC: Density Search for Sample Consensus},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2VORCESP}},
  note         = {Machine review of arXiv:2607.03972}
}
read the original abstract

Robust geometric model estimation is a fundamental problem in computer vision. RANSAC and its variants remain widely used for this task; however, they rely on stochastic minimal sampling. In this article, we propose Density Search Sample Consensus (DS-SAC), a deterministic robust estimation framework, that avoids repeated random sampling by searching dense regions. Starting from an initial model estimated from the available points, the method performs local exploration via forward and backward search. To facilitate global exploration, DS-SAC recursively partitions the point set using signed residuals and searches each valid partition for high-consensus models. We show that DS-SAC has polynomial complexity with respect to the number of points, making it an efficient alternative to stochastic consensus-based methods. Experiments on large-scale real-world datasets for homography, fundamental matrix, and essential matrix estimation show that DS-SAC achieves higher AUC scores, competitive or lower median pose errors, and faster runtime compared with widely used robust estimators, including RANSAC, MAGSAC, LO-RANSAC, and GC-RANSAC.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

29 extracted references · 5 canonical work pages

  1. [1]

    Commu- nications of the ACM24(6), 381–395 (1981)

    Fischler, M.A., Bolles, R.C.: Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography. Commu- nications of the ACM24(6), 381–395 (1981)

    1981

  2. [2]

    Computer vision and image understanding78(1), 138–156 (2000)

    Torr, P.H., Zisserman, A.: Mlesac: A new robust estimator with application to estimating image geometry. Computer vision and image understanding78(1), 138–156 (2000)

    2000

  3. [3]

    2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’05)1, 220–2261 (2005)

    Chum, O., Matas, J.: Matching with prosac - progressive sample consensus. 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’05)1, 220–2261 (2005)

    2005

  4. [4]

    In: Michaelis, B., Krell, G

    Chum, O., Matas, J., Kittler, J.: Locally optimized ransac. In: Michaelis, B., Krell, G. (eds.) Pattern Recognition, pp. 236–243. Springer, Berlin, Heidelberg (2003) 19

    2003

  5. [5]

    In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (2018)

    Barath, D., Matas, J.: Graph-cut ransac. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (2018)

    2018

  6. [6]

    In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) (2019)

    Barath, D., Matas, J., Noskova, J.: Magsac: Marginalizing sample consensus. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) (2019)

    2019

  7. [7]

    In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) (2020)

    Barath, D., Noskova, J., Ivashechkin, M., Matas, J.: Magsac++, a fast, reliable and accurate robust estimator. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) (2020)

    2020

  8. [8]

    In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (2015)

    Chin, T.-J., Purkait, P., Eriksson, A., Suter, D.: Efficient globally optimal con- sensus maximisation with tree search. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (2015)

    2015

Show all 29 references
  1. [9]

    In: Proceedings of the European Conference on Computer Vision (ECCV), pp

    Cai, Z., Chin, T.-J., Le, H., Suter, D.: Deterministic consensus maximization with biconvex programming. In: Proceedings of the European Conference on Computer Vision (ECCV), pp. 685–700 (2018)

    2018

  2. [10]

    In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp

    Le, H., Chin, T.-J., Suter, D.: An exact penalty method for locally convergent maximum consensus. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 1888–1896 (2017)

    2017

  3. [11]

    In: 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp

    Chin, T.-J., Purkait, P., Eriksson, A., Suter, D.: Efficient globally optimal con- sensus maximisation with tree search. In: 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 2413–2421 (2015). https://doi.org/ 10.1109/CVPR.2015.7298855

    2015 doi

  4. [12]

    In: 2009 IEEE 12th International Conference on Computer Vision, pp

    Li, H.: Consensus set maximization with guaranteed global optimality for robust geometry estimation. In: 2009 IEEE 12th International Conference on Computer Vision, pp. 1074–1080 (2009). IEEE

    2009

  5. [13]

    1825–1832 (2011)

    Zheng, Y., Sugimoto, S., Okutomi, M.: Deterministically maximizing feasible sub- system for robust model fitting with unit norm constraint, pp. 1825–1832 (2011). https://doi.org/10.1109/CVPR.2011.5995640

    2011 doi

  6. [14]

    Computer Vision and Image Understanding78(1), 138–156 (2000) https://doi.org/10.1006/cviu.1999.0832

    Torr, P.H.S., Zisserman, A.: Mlesac: A new robust estimator with application to estimating image geometry. Computer Vision and Image Understanding78(1), 138–156 (2000) https://doi.org/10.1006/cviu.1999.0832

    2000 doi

  7. [15]

    In: 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp

    Dai, A., Chang, A.X., Savva, M., Halber, M., Funkhouser, T., Nießner, M.: Scannet: Richly-annotated 3d reconstructions of indoor scenes. In: 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 2432–2443 (2017). https://doi.org/10.1109/CVPR.2017.261

    2017 doi

  8. [16]

    In: Proceedings of the IEEE/CVF 20 Conference on Computer Vision and Pattern Recognition (CVPR) (2020)

    Sarlin, P.-E., DeTone, D., Malisiewicz, T., Rabinovich, A.: Superglue: Learning feature matching with graph neural networks. In: Proceedings of the IEEE/CVF 20 Conference on Computer Vision and Pattern Recognition (CVPR) (2020)

    2020

  9. [17]

    Association for Computing Machinery, New York, NY, USA (2023)

    Snavely, N., Seitz, S.M., Szeliski, R.: Photo tourism: exploring photo collections in 3D, 1st edn. Association for Computing Machinery, New York, NY, USA (2023). https://doi.org/10.1145/3596711.3596766

    2023 doi

  10. [18]

    International Journal of Computer Vision129(2), 517–547 (2020) https://doi.org/10.1007/ s11263-020-01385-0

    Jin, Y., Mishkin, D., Mishchuk, A., Matas, J., Fua, P., Yi, K.M., Trulls, E.: Image matching across wide baselines: From paper to practice. International Journal of Computer Vision129(2), 517–547 (2020) https://doi.org/10.1007/ s11263-020-01385-0

    2020

  11. [19]

    In: Avidan, S., Brostow, G., Ciss´ e, M., Farinella, G.M., Hassner, T

    Sarlin, P.-E., Dusmanu, M., Sch¨ onberger, J.L., Speciale, P., Gruber, L., Larsson, V., Miksik, O., Pollefeys, M.: Lamar: Benchmarking localization and mapping for augmented reality. In: Avidan, S., Brostow, G., Ciss´ e, M., Farinella, G.M., Hassner, T. (eds.) Computer Vision ...

    2022

  12. [20]

    In: 2013 IEEE International Symposium on Mixed and Augmented Reality (ISMAR), pp

    Glocker, B., Izadi, S., Shotton, J., Criminisi, A.: Real-time rgb-d camera relo- calization. In: 2013 IEEE International Symposium on Mixed and Augmented Reality (ISMAR), pp. 173–179 (2013). https://doi.org/10.1109/ISMAR.2013. 6671777

    2013 doi

  13. [21]

    In: 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp

    Sch¨ ops, T., Sattler, T., Pollefeys, M.: Bad slam: Bundle adjusted direct rgb- d slam. In: 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 134–144 (2019). https://doi.org/10.1109/CVPR.2019. 00022

    2019 doi

  14. [22]

    Geiger, A., Lenz, P., Stiller, C., Urtasun, R.: Vision meets robotics: The kitti dataset. Int. J. Rob. Res.32(11), 1231–1237 (2013) https://doi.org/10.1177/ 0278364913491297

    2013

  15. [23]

    arXiv preprint arXiv:2506.04803 (2025)

    Barath, D.: Superansac: One ransac to rule them all. arXiv preprint arXiv:2506.04803 (2025)

    2025 arXiv

  16. [24]

    In: Blockeel, H., Kersting, K., Nijssen, S., ˇZelezn´ y, F

    Boyd, K., Eng, K.H., Page, C.D.: Area under the precision-recall curve: Point estimates and confidence intervals. In: Blockeel, H., Kersting, K., Nijssen, S., ˇZelezn´ y, F. (eds.) Machine Learning and Knowledge Discovery in Databases, pp. 451–466. Springer, Berlin, Heidelberg (2013)

    2013

  17. [25]

    IEEE Transactions on Pat- tern Analysis and Machine Intelligence19(6), 580–593 (1997) https://doi.org/10

    Hartley, R.I.: In defense of the eight-point algorithm. IEEE Transactions on Pat- tern Analysis and Machine Intelligence19(6), 580–593 (1997) https://doi.org/10. 1109/34.601246

    1997

  18. [26]

    In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) Workshops (2018) 21

    DeTone, D., Malisiewicz, T., Rabinovich, A.: Superpoint: Self-supervised inter- est point detection and description. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) Workshops (2018) 21

    2018

  19. [27]

    In: Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), pp

    Lindenberger, P., Sarlin, P.-E., Pollefeys, M.: Lightglue: Local feature matching at light speed. In: Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), pp. 17627–17638 (2023)

    2023

  20. [28]

    1, 2nd edn

    Hartley, R., Zisserman, A.: Multiple View Geometry in Computer Vision (2nd Ed) vol. 1, 2nd edn. Cambridge University Press, United Kingdom (2003)

    2003

  21. [29]

    IEEE Transactions on Pattern Analysis and Machine Intelligence26(6), 756–770 (2004) https://doi.org/10.1109/TPAMI.2004.17 22

    Nister, D.: An efficient solution to the five-point relative pose problem. IEEE Transactions on Pattern Analysis and Machine Intelligence26(6), 756–770 (2004) https://doi.org/10.1109/TPAMI.2004.17 22

    2004 doi

Pith tools

Reviewed July 11, 2026 · model on record in the stance chip above.