pith. sign in

arxiv: 2604.22518 · v1 · submitted 2026-04-24 · 💻 cs.CV

Non-Minimal Sampling and Consensus for Prohibitively Large Datasets

Seong Hun Lee , Patrick Vandewalle , Javier Civera This is my paper

Pith reviewed 2026-05-08 12:24 UTC · model grok-4.3

classification 💻 cs.CV
keywords non-minimal samplingconsensusrobust estimationoutlier rejectionRANSACcamera pose estimationpoint cloud registrationmodel fitting
0
0 comments X

The pith

NONSAC scales robust geometric model fitting to arbitrarily large noisy datasets by using non-minimal samples and hypothesis scoring.

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

The paper introduces NONSAC as a framework that draws non-minimal subsets from very large datasets containing noise and outliers, runs a robust estimator on each subset to produce candidate models, and then selects the final model with a scoring rule. This setup is designed to work with any existing estimator and to plug into algorithms such as RANSAC. A sympathetic reader would care because standard minimal-sampling methods become impractical or inaccurate once data sizes grow without bound, while NONSAC aims to keep both speed and accuracy. The authors test the approach on relative camera pose estimation, Perspective-n-Point, and point cloud registration, including a version that hypothesizes all-to-all correspondences without prior matches.

Core claim

NONSAC repeatedly samples non-minimal subsets of data and generates model hypotheses using a robust estimator, producing multiple candidate models. The final model is selected based on a predefined scoring rule that evaluates hypothesis quality. The framework is estimator-agnostic and can be integrated with existing geometric fitting algorithms such as RANSAC to improve both scalability and robustness to outliers on arbitrarily large contaminated datasets.

What carries the argument

Non-minimal subset sampling followed by robust hypothesis generation and quality scoring to select the best model.

If this is right

  • Robust estimation becomes practical for datasets too large for traditional minimal-sampling techniques.
  • Existing algorithms such as RANSAC gain improved scalability and outlier tolerance when wrapped inside the framework.
  • The same procedure applies to relative camera pose estimation, Perspective-n-Point, and point cloud registration.
  • Correspondence-free registration is enabled by generating hypotheses over all-to-all possible matches.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The method may allow vision pipelines to avoid aggressive data downsampling or outlier pre-filtering steps.
  • Scoring rules tuned to particular sensor modalities or noise statistics could further improve results on specific tasks.
  • The non-minimal sampling idea might transfer to incremental or streaming settings where data arrives continuously.

Load-bearing premise

The scoring rules can reliably identify a high-quality model from the hypotheses produced by applying the robust estimator to non-minimal subsets drawn from arbitrarily large contaminated data.

What would settle it

A large dataset with high outlier ratio on which every scoring rule selects a model whose error is markedly higher than the ground-truth model or the best hypothesis generated.

Figures

Figures reproduced from arXiv: 2604.22518 by Javier Civera, Patrick Vandewalle, Seong Hun Lee.

Figure 1
Figure 1. Figure 1: NONSAC pipeline: From the original correspondence dataset, we randomly draw m non-minimal samples. Due to randomness, some samples are likely to contain more inliers than others. In this example, Sample 3 has the highest number of inliers. For each sample, we apply an off-the-shelf estimator to compute the model parameters, residuals, inlier counts, and related values. We then aggregate the results from al… view at source ↗
Figure 2
Figure 2. Figure 2: [Correspondence-free point cloud registration] view at source ↗
read the original abstract

We introduce NONSAC (Non-Minimal Sampling and Consensus), a general framework for robust and scalable model estimation from arbitrarily large datasets contaminated with noise and outliers. NONSAC repeatedly samples non-minimal subsets of data and generates model hypotheses using a robust estimator, producing multiple candidate models. The final model is selected based on a predefined scoring rule that evaluates hypothesis quality. Our framework is estimator-agnostic and can be integrated with existing geometric fitting algorithms such as RANSAC to improve both scalability and robustness to outliers. We propose and evaluate various scoring rules for NONSAC on relative camera pose estimation, Perspective-n-Point, and point cloud registration. Furthermore, we showcase the applicability of NONSAC to correspondence-free point cloud registration by hypothesizing all-to-all correspondences.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The paper introduces NONSAC, a general framework for robust and scalable model estimation from arbitrarily large datasets contaminated with noise and outliers. NONSAC repeatedly samples non-minimal subsets, applies a robust estimator to each to generate model hypotheses, and selects the final model using one of several proposed scoring rules. The framework is presented as estimator-agnostic and integrable with existing algorithms such as RANSAC. It is evaluated on relative camera pose estimation, Perspective-n-Point, point cloud registration, and correspondence-free point cloud registration.

Significance. If the empirical claims hold, NONSAC would offer a practical, scalable alternative to minimal-sampling consensus methods for very large contaminated datasets in geometric computer vision. The estimator-agnostic design and the extension to correspondence-free registration are potentially useful strengths. The approach could improve both runtime and outlier robustness when integrated with existing robust estimators.

major comments (1)
  1. Abstract: The central claim that the scoring rules reliably select a high-quality model from hypotheses generated on non-minimal subsets is load-bearing, yet the manuscript supplies no analysis or quantitative results showing how these rules behave when the underlying robust estimator is applied only to non-minimal blocks drawn from data with arbitrarily high outlier fractions. The non-minimal size can amplify residual contamination inside each block, and the evaluation on three tasks does not address this regime.
minor comments (1)
  1. The abstract lists tasks and claims but contains no quantitative results, error bars, or ablation details; these should be summarized with key metrics (e.g., success rates, runtime scaling) to allow readers to assess the reported improvements.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their constructive feedback on our manuscript. We address the major comment point by point below and outline the revisions we will implement.

read point-by-point responses

  1. Referee: Abstract: The central claim that the scoring rules reliably select a high-quality model from hypotheses generated on non-minimal subsets is load-bearing, yet the manuscript supplies no analysis or quantitative results showing how these rules behave when the underlying robust estimator is applied only to non-minimal blocks drawn from data with arbitrarily high outlier fractions. The non-minimal size can amplify residual contamination inside each block, and the evaluation on three tasks does not address this regime.

    Authors: We acknowledge that a dedicated quantitative analysis of scoring-rule behavior under arbitrarily high outlier fractions would strengthen support for the central claim. Our current evaluations on relative camera pose estimation, PnP, and point cloud registration include challenging outlier levels and show that NONSAC with the proposed scoring rules yields more accurate and robust models than minimal-sampling baselines; however, these experiments do not systematically isolate the effect of non-minimal subset size on residual contamination at extreme outlier ratios. In the revision we will add a new experimental subsection that varies outlier fraction from 50% to 95%, applies the robust estimator to non-minimal blocks, and reports the selection accuracy of each scoring rule. This will directly quantify robustness to amplified contamination and allow us to update the abstract accordingly. revision: yes

Circularity Check

0 steps flagged

No circularity: NONSAC is an algorithmic proposal with design-choice scoring rules evaluated empirically.

full rationale

The paper introduces NONSAC as a sampling-and-selection framework that repeatedly draws non-minimal subsets, applies an existing robust estimator to each, and chooses the final model via one of several explicitly proposed scoring rules. These rules are presented as design choices that are then evaluated on three tasks rather than derived from equations or fitted to the target output. No self-definitional loop, fitted-input-renamed-as-prediction, or load-bearing self-citation chain appears in the described method; the framework remains estimator-agnostic and integrates with external algorithms such as RANSAC without reducing its central claim to its own inputs by construction. The derivation chain is therefore self-contained as an algorithmic construction whose validity rests on empirical performance rather than on any internal reduction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The framework rests on the domain assumption that non-minimal subsets can be drawn efficiently and that a scoring rule can be defined to rank hypotheses without introducing new free parameters beyond those already present in the base estimator.

axioms (1)
  • domain assumption A robust estimator exists that can produce a model hypothesis from any non-minimal subset.
    Invoked when the paper states that NONSAC generates model hypotheses using a robust estimator on sampled subsets.

pith-pipeline@v0.9.0 · 5423 in / 1247 out tokens · 34503 ms · 2026-05-08T12:24:27.028831+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

50 extracted references · 2 canonical work pages · 1 internal anchor

  1. [1]

    In: IEEE Conf

    Bai, X., Luo, Z., Zhou, L., Chen, H., Li, L., Hu, Z., Fu, H., Tai, C.L.: Pointdsc: Robust point cloud registration using deep spatial consistency. In: IEEE Conf. Comput. Vis. Pattern Recog. pp. 15859–15869 (2021)

    2021

  2. [2]

    IEEE Trans

    Barath, D., Matas, J.: Graph-cut ransac: Local optimization on spatially coherent structures. IEEE Trans. Pattern Anal. Mach.44(9), 4961–4974 (2022)

    2022

  3. [3]

    In: IEEE Conf

    Baráth, D., Noskova, J., Ivashechkin, M., Matas, J.: MAGSAC++, a fast, reliable and accurate robust estimator. In: IEEE Conf. Comput. Vis. Pattern Recog. pp. 1301–1309 (2020)

    2020

  4. [4]

    In: IEEE Conf

    Briales, J., Kneip, L., Gonzalez-Jimenez, J.: A certifiably globally optimal solution to the non-minimal relative pose problem. In: IEEE Conf. Comput. Vis. Pattern Recog. pp. 145–154 (2018)

    2018

  5. [5]

    arXivabs/2401.13357(2024)

    Cai, Q., Li, X., Wu, Y.: Linear relative pose estimation founded on pose-only imaging geometry. arXivabs/2401.13357(2024)

    work page arXiv 2024

  6. [6]

    Campbell, D., Liu, L., Gould, S.: Solving the blind perspective-n-point problem end-to-end with robust differentiable geometric optimization. In: Eur. Conf. Com- put. Vis. pp. 244–261 (2020)

    2020

  7. [7]

    IEEE Trans

    Chen, H., Tian, W., Wang, P., Wang, F., Xiong, L., Li, H.: EPro-PnP: Generalized end-to-endprobabilisticperspective-n-pointsformonocularobjectposeestimation. IEEE Trans. Pattern Anal. Mach.47(11), 9413–9425 (2025)

    2025

  8. [8]

    In: IEEE Conf

    Chen, W., Li, H., Nie, Q., Liu, Y.H.: Deterministic point cloud registration via novel transformation decomposition. In: IEEE Conf. Comput. Vis. Pattern Recog. pp. 6338–6346 (2022)

    2022

  9. [9]

    In: IEEE Conf

    Chen, Z., Sun, K., Yang, F., Tao, W.: SC2-PCR: A second order spatial compat- ibility for efficient and robust point cloud registration. In: IEEE Conf. Comput. Vis. Pattern Recog. pp. 13211–13221 (2022)

    2022

  10. [10]

    In: Pattern Recog- nition

    Chum, O., Matas, J., Kittler, J.: Locally optimized RANSAC. In: Pattern Recog- nition. pp. 236–243. Springer Berlin Heidelberg (2003)

    2003

  11. [11]

    In: SIGGRAPH

    Curless, B., Levoy, M.: A volumetric method for building complex models from range images. In: SIGGRAPH. pp. 303–312. ACM (1996)

    1996

  12. [12]

    Springer International Publishing (2021)

    Devore, J.L., Berk, K.N., Carlton, M.A.: Modern Mathematical Statistics with Applications. Springer International Publishing (2021)

    2021

  13. [13]

    Enqvist, O., Josephson, K., Kahl, F.: Optimal correspondences from pairwise con- straints. In: Int. Conf. Comput. Vis. pp. 1295–1302 (2009)

    2009

  14. [14]

    IEEE Trans

    Fan, A., Ma, J., Jiang, X., Ling, H.: Efficient deterministic search with robust loss functions for geometric model fitting. IEEE Trans. Pattern Anal. Mach.44(11), 8212–8229 (2022)

    2022

  15. [15]

    Communi- cations 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. Communi- cations of the ACM24(6), 381–395 (1981)

    1981

  16. [16]

    In: IEEE Conf

    Fredriksson, J., Larsson, V., Olsson, C., Kahl, F.: Optimal relative pose with un- known correspondences. In: IEEE Conf. Comput. Vis. Pattern Recog. pp. 1728– 1736 (2016)

    2016

  17. [17]

    Garcia-Salguero, M., Gonzalez-Jimenez, J.: Fast and robust certifiable estimation of the relative pose between two calibrated cameras. J. Math. Imaging Vis.63(8), 1036–1056 (2021)

    2021

  18. [18]

    In: IEEE Conf

    Hartley, R., Aftab, K., Trumpf, J.: L1 rotation averaging using the weiszfeld algo- rithm. In: IEEE Conf. Comput. Vis. Pattern Recog. pp. 3041–3048 (2011) 16 S. H. Lee et al

    2011

  19. [19]

    Cam- bridge University Press, 2 edn

    Hartley, R., Zisserman, A.: Multiple View Geometry in Computer Vision. Cam- bridge University Press, 2 edn. (2003)

    2003

  20. [20]

    In: IEEE Conf

    Huang, T., Peng, L., Vidal, R., Liu, Y.H.: Scalable 3d registration via truncated entry-wise absolute residuals. In: IEEE Conf. Comput. Vis. Pattern Recog. pp. 27477–27487 (2024)

    2024

  21. [21]

    In: IEEE Conf

    Jiang, H., Dang, Z., Wei, Z., Xie, J., Yang, J., Salzmann, M.: Robust outlier re- jection for 3d registration with variational bayes. In: IEEE Conf. Comput. Vis. Pattern Recog. pp. 1148–1157 (2023)

    2023

  22. [22]

    Jin, Y., Mishkin, D., Mishchuk, A., Matas, J., Fua, P., Yi, K.M., Trulls, E.: Im- age matching across wide baselines: From paper to practice. Int. J. Comput. Vis. 129(2), 517–547 (2021)

    2021

  23. [23]

    In: Brit

    Kukelova, Z., Bujnak, M., Pajdla, T.: Polynomial eigenvalue solutions to the 5-pt and 6-pt relative pose problems. In: Brit. Mach. Vis. Conf. pp. 56.1–56.10 (2008)

    2008

  24. [24]

    Lee, S.H., Civera, J.: Robust single rotation averaging revisited. In: Eur. Conf. Comput. Vis. Worksh. pp. 30–42 (2025)

    2025

  25. [25]

    Lee, S.H., Civera, J., Vandewalle, P.: PCR-99: A practical method for point cloud registration with 99 percent outliers. In: Eur. Conf. Comput. Vis. Worksh. pp. 14–29 (2025)

    2025

  26. [26]

    P3P Made Easy

    Lee, S.H., Vandewalle, P., Civera, J.: P3P made easy. CoRRabs/2508.01312 (2025)

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  27. [27]

    IEEE Trans

    Liu, C., Yuen, J., Torralba, A.: SIFT Flow: Dense correspondence across scenes and its applications. IEEE Trans. Pattern Anal. Mach.33(5), 978–994 (2011)

    2011

  28. [28]

    IEEE Robotics and Automation Letters10(7), 6856–6863 (2025)

    Long, C., Hu, Q., Jiang, C., Li, D., Ouyang, Z.: BnB-based robust pnp pose estima- tion method for outliers. IEEE Robotics and Automation Letters10(7), 6856–6863 (2025)

    2025

  29. [29]

    Luong, Q., Faugeras, O.D.: The fundamental matrix: Theory, algorithms, and sta- bility analysis. Int. J. Comput. Vis.17(1), 43–75 (1996)

    1996

  30. [30]

    Advances in Neural Information Processing Systems37, 101529–101551 (2024)

    Moran, D., Margalit, Y., Trostianetsky, G., Khatib, F., Galun, M., Basri, R.: Con- sensus learning with deep sets for essential matrix estimation. Advances in Neural Information Processing Systems37, 101529–101551 (2024)

    2024

  31. [31]

    IEEE Transactions on Pattern Analysis and Machine Intel- ligence31(5), 783–794 (2009)

    Olsson, C., Kahl, F., Oskarsson, M.: Branch-and-bound methods for euclidean registration problems. IEEE Transactions on Pattern Analysis and Machine Intel- ligence31(5), 783–794 (2009)

    2009

  32. [32]

    IEEE Trans

    Parra Bustos, A., Chin, T.J.: Guaranteed outlier removal for point cloud registra- tion with correspondences. IEEE Trans. Pattern Anal. Mach.40(12), 2868–2882 (2018)

    2018

  33. [33]

    In: Proceedings of the IEEE/CVF Conference on Com- puter Vision and Pattern Recognition (CVPR)

    Peng, L., Kümmerle, C., Vidal, R.: On the convergence of IRLS and its variants in outlier-robust estimation. In: Proceedings of the IEEE/CVF Conference on Com- puter Vision and Pattern Recognition (CVPR). pp. 17808–17818 (June 2023)

    2023

  34. [34]

    IEEE Trans

    Raguram, R., Chum, O., Pollefeys, M., Matas, J., Frahm, J.M.: USAC: A universal framework for random sample consensus. IEEE Trans. Pattern Anal. Mach.35(8), 2022–2038 (2013)

    2022

  35. [35]

    In: IEEE Conf

    Rydell, F., Torres, A., Larsson, V.: Revisiting Sampson Approximations for Ge- ometric Estimation Problems . In: IEEE Conf. Comput. Vis. Pattern Recog. pp. 4990–4998 (2024)

    2024

  36. [36]

    very scattered

    Sampson, P.D.: Fitting conic sections to “very scattered” data: An iterative refine- ment of the bookstein algorithm. Computer Graphics and Image Processing18(1), 97–108 (1982)

    1982

  37. [37]

    In: IEEE Conf

    Sun, J., Shen, Z., Wang, Y., Bao, H., Zhou, X.: LoFTR: Detector-free local feature matching with transformers. In: IEEE Conf. Comput. Vis. Pattern Recog. pp. 8918–8927 (2021) Non-Minimial Sampling and Consensus for Prohibitively Large Datasets 17

    2021

  38. [38]

    IEEE Robotics and Automation Letters9(4), 3100–3107 (2024)

    Sun, Q., Zhang, T., Zhang, G., Wang, K., Zhu, D., Li, J., Zhang, X.: Efficient solution to pnp problem based on vision geometry. IEEE Robotics and Automation Letters9(4), 3100–3107 (2024)

    2024

  39. [39]

    Teed, Z., Deng, J.: RAFT: Recurrent all-pairs field transforms for optical flow. In: Eur. Conf. Comput. Vis. p. 402–419 (2020)

    2020

  40. [40]

    Terzakis, G., Lourakis, M.: A consistently fast and globally optimal solution to the perspective-n-point problem. In: Eur. Conf. Comput. Vis. pp. 478–494 (2020)

    2020

  41. [41]

    In: IEEE Conf

    Tirado-Garín, J., Civera, J.: From correspondences to pose: Non-minimal certifi- ably optimal relative pose without disambiguation. In: IEEE Conf. Comput. Vis. Pattern Recog. pp. 403–412 (2024)

    2024

  42. [42]

    In: Proceedings of the British Machine Vision Conference (BMVC)

    Victor Fragoso, Christopher Sweeney, P.S., Turk, M.: ANSAC: Adaptive non- minimal sample and consensus. In: Proceedings of the British Machine Vision Conference (BMVC). pp. 43.1–43.11. BMVA Press (September 2017)

    2017

  43. [43]

    IEEE Robotics and Automation Letters9(11), 9287–9294 (2024)

    Xie, X., Zou, D.: Depth-based efficient pnp: A rapid and accurate method for camera pose estimation. IEEE Robotics and Automation Letters9(11), 9287–9294 (2024)

    2024

  44. [44]

    IEEE Transactions on Image Processing 34, 6838–6851 (2025)

    Xu, C., Guo, T., Huang, Y., Cheng, L.: A hough voting-based 2-point ransac solu- tion to the perspective-n-point problem. IEEE Transactions on Image Processing 34, 6838–6851 (2025)

    2025

  45. [45]

    Pattern Recognition Letters11(5), 331–338 (1990)

    Xu, L., Oja, E., Kultanen, P.: A new curve detection method: Randomized Hough transform (RHT). Pattern Recognition Letters11(5), 331–338 (1990)

    1990

  46. [46]

    IEEE Robotics and Automation Letters (RA-L)5(2), 1127–1134 (2020)

    Yang, H., Antonante, P., Tzoumas, V., Carlone, L.: Graduated non-convexity for robust spatial perception: From non-minimal solvers to global outlier rejection. IEEE Robotics and Automation Letters (RA-L)5(2), 1127–1134 (2020)

    2020

  47. [47]

    IEEE Transactions on Robotics37(2), 314–333 (2021)

    Yang, H., Shi, J., Carlone, L.: TEASER: Fast and certifiable point cloud registra- tion. IEEE Transactions on Robotics37(2), 314–333 (2021)

    2021

  48. [48]

    In: IEEE Conf

    Yi, K.M., Trulls, E., Ono, Y., Lepetit, V., Salzmann, M., Fua, P.: Learning to find good correspondences. In: IEEE Conf. Comput. Vis. Pattern Recog. pp. 2666–2674 (2018)

    2018

  49. [49]

    In: IEEE Conf

    Zhang, X., Yang, J., Zhang, S., Zhang, Y.: 3D registration with maximal cliques. In: IEEE Conf. Comput. Vis. Pattern Recog. pp. 17745–17754 (2023)

    2023

  50. [50]

    IEEE Trans

    Zhao, J.: An efficient solution to non-minimal case essential matrix estimation. IEEE Trans. Pattern Anal. Mach.44(4), 1777–1792 (2022)

    2022