# Progressive NAPSAC: sampling from gradually growing neighborhoods

arXiv: https://arxiv.org/abs/1906.02295 · HTML: https://mlsanity.com/paper/1906.02295/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Jun 2019.

## Built on by (most cited first, 16 of 16)

- [MeshLoc: Mesh-Based Visual Localization](https://mlsanity.com/paper/2207.10762/) (2022)
- [Visual Localization using Imperfect 3D Models from the Internet](https://mlsanity.com/paper/2304.05947/) (2023)
- [VSAC: Efficient and Accurate Estimator for H and F](https://mlsanity.com/paper/2106.10240/) (2021)
- [Finding Geometric Models by Clustering in the Consensus Space](https://mlsanity.com/paper/2103.13875/) (2021)
- [Efficient and Robust Point Cloud Registration via Heuristics-guided Parameter Search](https://mlsanity.com/paper/2404.06155/) (2024)
- [SupeRANSAC: One RANSAC to Rule Them All](https://mlsanity.com/paper/2506.04803/) (2025)
- [BANSAC: A dynamic BAyesian Network for adaptive SAmple Consensus](https://mlsanity.com/paper/2309.08690/) (2023)
- [Visual SLAM with Graph-Cut Optimized Multi-Plane Reconstruction](https://mlsanity.com/paper/2108.04281/) (2021)
- [RLSAC: Reinforcement Learning enhanced Sample Consensus for End-to-End Robust Estimation](https://mlsanity.com/paper/2308.05318/) (2023)
- [USACv20: robust essential, fundamental and homography matrix estimation](https://mlsanity.com/paper/2104.05044/) (2021)
- [RANSAC Scoring Done Right](https://mlsanity.com/paper/2606.27385/) (2026)
- [Pentagon-Match (PMatch): Identification of View-Invariant Planar Feature for Local Feature Matching-Based Homography Estimation](https://mlsanity.com/paper/2305.17463/) (2023)
- [FLIGHT: Fibonacci Lattice-based Inference for Geometric Heading in real-Time](https://mlsanity.com/paper/2602.23115/) (2026)
- [Efficient Minimal Solvers for Visual-Inertial Relative Pose Estimation in Multi-Camera Systems](https://mlsanity.com/paper/2606.09477/) (2026)
- [Efficient Minimal Solvers for Relative Pose Estimation in Autonomous Driving Applications](https://mlsanity.com/paper/2606.09569/) (2026)
- [DiffSAC: Diffusion-guided Sampling for Consensus-based Robust Estimation](https://mlsanity.com/paper/2608.30603/) (2026)

## Abstract (arXiv)

We propose Progressive NAPSAC, P-NAPSAC in short, which merges the advantages of local and global sampling by drawing samples from gradually growing neighborhoods. Exploiting the fact that nearby points are more likely to originate from the same geometric model, P-NAPSAC finds local structures earlier than global samplers. We show that the progressive spatial sampling in P-NAPSAC can be integrated with PROSAC sampling, which is applied to the first, location-defining, point. P-NAPSAC is embedded in USAC, a state-of-the-art robust estimation pipeline, which we further improve by implementing its local optimization as in Graph-Cut RANSAC. We call the resulting estimator USAC*. The method is tested on homography and fundamental matrix fitting on a total of 10,691 models from seven publicly available datasets. USAC* with P-NAPSAC outperforms reference methods in terms of speed on all problems.