Content deleted Content added
| (11 intermediate revisions by 6 users not shown) | |||
Line 1:
{{Short description|Statistical method}}
{{Machine learning bar}}
'''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 |
==Example==
Line 172:
plt.show()
</syntaxhighlight>
[[File:RANSAC applied to 2D regression problem.png|alt=A scatterplot showing a diagonal line from the bottom left to top right of the figure. A trend line fits closely along the diagonal, without being thrown off by outliers scattered elsewhere in the figure.|center|thumb|Result of running the <code>RANSAC</code> implementation. The orange line shows the least
== Parameters ==
Line 201:
==Advantages and disadvantages==
{{refimprove section|date=September 2014}}
An advantage of RANSAC is its ability to do [[robust statistics|robust estimation]]<ref>Robust Statistics, Peter. J. Huber, Wiley, 1981 (republished in paperback, 2004), page 1.</ref> of the model parameters, i.e., it can estimate the parameters with a high degree of accuracy even when a significant number of [[outlier]]s are present in the data set. A disadvantage of RANSAC is that there is no upper bound on the time it takes to compute these parameters (except exhaustion). When the number of iterations computed is limited, the solution obtained may not be optimal, and it may not even be one that fits the data in a good way. In this way RANSAC offers a trade-off; by computing a greater number of iterations, the probability of a reasonable model being produced is increased. Moreover, RANSAC is not always able to find the optimal set even for moderately contaminated sets, and it usually performs badly when the number of inliers is less than 50%. Optimal RANSAC
RANSAC can only estimate one model for a particular data set. As for any one-model approach when two (or more) model instances exist, RANSAC may fail to find either one. The [[Hough transform]] is one alternative robust estimation technique that may be useful when more than one model instance is present. Another approach for multi
==Applications==
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 ==
| |||