Random sample consensus: Difference between revisions

Revision as of 05:22, 13 November 2024

Latest revision as of 18:48, 13 August 2025

(8 intermediate revisions by 4 users not shown)

Line 3:

'''Random sample consensus''' ('''RANSAC''') is an [[iterative method]] to estimate parameters of a mathematical model from a set of observed data that contains [[outliers]], when outliers are to be {{clarify span|accorded no influence|date=November 2024}} on the values of the estimates. Therefore, it also can be interpreted as an outlier detection method.<ref>Data Fitting and Uncertainty, T. Strutz, Springer Vieweg (2nd edition, 2016).</ref> It is a non-deterministic algorithm in the sense that it produces a reasonable result only with a certain probability, with this probability increasing as more iterations are allowed. The algorithm was first published by Fischler and Bolles at [[SRI International]] in 1981. They used RANSAC to solve the ___location determination problem (LDP), where the goal is to determine the points in the space that project onto an image into a set of landmarks with known locations.

RANSAC uses [[Cross-validation (statistics)#Repeated random sub-sampling validation|repeated random sub-sampling]].<ref>{{cite web |lastlast1=Cantzler |first1=H. |title=Random Sample Consensus (RANSAC) |language=en |publisher=Institute for Perception, Action and Behaviour, Division of Informatics, University of Edinburgh |citeseerx=10.1.1.106.3035 |url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.106.3035&rep=rep1&type=pdf |archive-url=https://web.archive.org/web/20230204054340/http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.106.3035&rep=rep1&type=pdf |archive-date=2023-02-04 |url-status=dead}}</ref> A basic assumption is that the data consists of "inliers", i.e., data whose distribution can be explained by some set of model parameters, though may be subject to noise, and "outliers", which are data that do not fit the model. The outliers can come, for example, from extreme values of the noise or from erroneous measurements or incorrect hypotheses about the interpretation of data. RANSAC also assumes that, given a (usually small) set of inliers, there exists a procedure that can estimate the parameters of a model optimally explaining or fitting this data.

==Example==

Line 225:

* [[Resampling (statistics)]]

* Hop-Diffusion Monte Carlo uses randomized sampling involve global jumps and local diffusion to choose the sample at each step of RANSAC for epipolar geometry estimation between very wide-baseline images.<ref>{{cite journal |last1=Brahmachari |first1=Aveek S. |last2=Sarkar |first2=Sudeep |title=Hop-Diffusion Monte Carlo for Epipolar Geometry Estimation between Very Wide-Baseline Images |journal=IEEE Transactions on Pattern Analysis and Machine Intelligence |date=March 2013 |volume=35 |issue=3 |pages=755–762 |doi=10.1109/TPAMI.2012.227|pmid=26353140 |s2cid=2524656 }}</ref>

* [[FSASAC]] (RANSAC based on data filtering and [[simulated annealing]])<ref>W. Ruoyan and W. Junfeng, "[https://ieeexplore.ieee.org/document/9648331 FSASAC: Random Sample Consensus Based on Data Filter and Simulated Annealing]," in IEEE Access, vol. 9, pp. 164935-164948, 2021, doi: 10.1109/ACCESS.2021.3135416.</ref>

== See also ==