Talk:Random sample consensus

interpretation of output

Does the algorithm's output (assuming convergence, etc) have a well-defined interpretation in terms of some bayesian (or other) model of the data and outliers? I believe it does, but I don't know what it is. -- David W. Hogg 00:23, 1 June 2007 (UTC)

Iteration?

Does this algorithm iteratively converge on a result? As it is described, it sounds like it just repeatedly selects a random set. It seems like it could do better by selecting a random set, then adding extra points that fit well and excluding points that don't fit well until that converges. 155.212.242.34 19:19, 17 October 2007 (UTC)

About convergence. Your question on convergence is not easy to answer since it depends on what we mean by convergence. The algorithm iteratively seeks to improve its current solution, i.e, any time is selects a new solution it is a better solution than the previous one, which means that if it is allowed to continue its search indefinitely, it will "converge" to the global optimum. However, in practice it cannot iterate indefinitely, typically it iterates a fix number of times. This means that there is a small but non-zero probability that it does not find even a close-to-optimal solution. The algorithm is often characterized as "indeterministic" since it provides reasonable results only with a certain probability, and this probability increases with the number of iterations which are allowed. --KYN 11:01, 18 October 2007 (UTC)

About improving the algorithm. What you are proposing may or may not be a good idea, depending on the application. It is, however, not how the basic RANSAC algorithm works. On the other hand, there are plenty of extensions of the original algorithm which can be found in the literature, and your proposal could probably be one of them. --KYN 11:01, 18 October 2007 (UTC)

Thanks for the clarification. It sounds almost too simple to make much headway, but I guess it works. 155.212.242.34 16:08, 18 October 2007 (UTC)

You are assuming that the solution you want to improve upon is within the global minimum basin. However, in RANSAC this is often not true. In the article's example it would be hard converge from a candidate line that intersects with the actual line at a steep angle. 132.230.167.126 (talk) 16:00, 3 June 2013 (UTC)

I got misled by the statement that the algorithm is "iterative", too. To me, an "iterative" algorithm would mean that each iteration depends on the result of the previous iteration. On the other hand, RANSAC simply repeats a procedure and picks the best outcome of all the repetitions. The repetitions are mutually independent, and could be implemented in parallel fashion. I wouldn't call this "iterative". MaigoAkisame (talk) 03:55, 9 April 2019 (UTC)

Ondrej Chum source

summary of discussion, transcribed from the article history:

Undid revision 317254705 by 147.32.80.13 —Preceding unsigned comment added by Richie (talk • contribs) 20:43, 1 October 2009 (UTC)

Undid revision 317336763 by Richie (talk) - returning relevant citation —Preceding unsigned comment added by 147.32.80.13 (talk) 14:39, 2 October 2009 (UTC)

revert: no need to cite this application of RANSAC —Preceding unsigned comment added by Richie (talk • contribs) 23:12, 6 October 2009 (UTC)

redo: not an application of RANSAC—Preceding unsigned comment added by 147.32.80.13 (talk) 13:50, 7 October 2009 (UTC)

IP resolves to proxy.felk.cvut.cz – don't add your own work here, it violates Wikipedia policy —Preceding unsigned comment added by Richie (talk • contribs) 21:36, 7 October 2009 (UTC)

Dear Richie, if you know more comprehensive publication on RANSAC, please cite it. If you find something irrelevant on the publication, please be specific. If you cannot do either, leave the reference —Preceding unsigned comment added by 83.208.118.254 (talk) 23:11, 7 October 2009 (UTC)

I apologise, I was judging the source just by its title which did not appear very relevant. The contents, however, appear to be very comprehensive and useful indeed. I would suggest that you edit the article to refer to the source in suitable places, so that it is clear, what the source is about. Thanks for your perseverance in reverting my edits, I now think it is a worthwhile addition to the article :) — Richie 20:17, 9 October 2009 (UTC)

Estimating the number of iterations

Is the formula for estimating the number of iterations really correct? Because k gets smaller as p decreases, meaning when the probability that the RANSAC algorithm selects only inliers decreases, we need LESS number of iterations? Seems kind of counter-intuitive? — Preceding unsigned comment added by 178.83.63.83 (talk) 19:19, 31 October 2012 (UTC)

It is, the meaning is that in less iterations the probability of taking at least one all-inlier sample is lower. We typically want p to reach a user-given probability (the desired confidence of output correctness, e.g. 95 or 99 %). Therefore, smaller required p means we are happy enough with smaller probability of correct result and RANSAC can terminate sooner. 147.32.80.19 (talk) 11:47, 22 November 2012 (UTC)

The first time I read this I was confused as well as both p and w^n seem to be defined using very similar language. In that case the terms 1-p and 1-w^n cancel and k is always one. However, maybe it is meant to say that p is our desired confidence in our algorithm, not the actual probability of finding a solution? — Preceding unsigned comment added by 202.36.134.22 (talk) 02:53, 16 July 2018 (UTC)

published earlier?

This is supposed to be the first publiction: Martin A. Fischler and Robert C. Bolles (June 1981). "Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography". Comm. of the ACM 24 (6): 381–395. doi:10.1145/358669.358692. However, there is this: Martin A. Fischler und Robert C. Bolles: Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography. March 1980. link Anybody know why the first publication was chosen for the article? HMallison (talk) 21:37, 30 April 2014 (UTC)

The second document is not a peer-reviewed paper but an SRI-internal technical memo. It may be the first description of RANSAC, but whether it can be called a publication is doubtful. QVVERTYVS (hm?) 09:20, 1 May 2014 (UTC)

Matlab Algorithm

The Matlab Implementation does not implement the Algorithm described in the previous section. In particular, the section to update the model does not estimate parameter1 and parameter2 using all of the inliers as specified in the Algorithm. Further, the variable names don't match the names in the Algorithm. I would suggest updating the Matlab implementation to (1) reflect the variable names used in the previous section, and (2) compute the model parameters using all of the inliers rather than just sample(:,:).

Ambiguity about the purpose of this technique

This article begins as follows:

Random sample consensus (RANSAC) is an iterative method to estimate parameters of a mathematical model from a set of observed data which contains outliers. Therefore, it also can be interpreted as an outlier detection method.

I'm not convinced this makes sense. Is its purpose simply to identify outliers, or is its purpose to fit a model when it is appropriate to exclude outliers in doing the fit? Those are not exactly the same thing. The second requires the first, but the first does not require the second. For example, an outlier could represent a lode of gold, when that is what is being sought. Michael Hardy (talk) 21:32, 5 September 2016 (UTC)

Minimum Number of Data Points to Estimate Parameters

In most implementations of RANSAC the number of randomly chosen sample points must be the minimum number of data points required to estimate the parameters of the model. This means all the randomly chosen sample points will exactly fit the model without error. These sample points can be excluded from the error computation, because the error is already known to be zero for these points. In addition, the sample points are considered inliers, because their fit error is zero.

For example: The minimum number of data points to define a line is two. This means, when doing a linear fit, two points are randomly sampled from the data to describe a line. Then, the linear fit error is calculated for all the other points not selected as samples, since these points will all have some fit error. The points that meet the minimum error criteria are considered inliers. Likewise, both the sample points are already considered inliers and can be excluded from the error calculation, because they have zero error, since they are exactly on the line.

The Python RANSAC example in the article describes how to use RASAC for doing a linear fit. Since it is a linear fit the number of sample points should only be 2. However the number of points used in the example is 10. In this example, all 10 samples will be considered inliers and will be excluded from the error calculation, but many of these samples are likely to exceed the error criteria and should be categorized as outliers, because none of the points lie exactly on the line.

I recommend modifying the example to set the sample size to 2, and providing a better description in the text of how to set the sample size. MachCtrlEng (talk) 17:05, 21 February 2024 (UTC)

Pseudocode section

According to Fischler & Bolles from their 1981 paper :

"Given a model that requires a minimum of n data points to instantiate its free parameters, and a set of data points P such that the number of points in P is greater than n [#(P) >= n], randomly select a subset S1 of n data points from P and instantiate the model. Use the instantiated model M1 to determine the subset S1* of points in P that are within some error tolerance of M1.

The set S1* is called the consensus set of S1. If #(S1*) is greater than some threshold t, which is a function of the estimate of the number of gross errors in P, use S1* to compute (possibly using least squares) a new model M1*."

The pseudo code section introduces an error "thisErr" that is not clearly described and most importantly is computed after M1*. In the classical RANSAC algorithm, "thisErr" is simply #(S1*). Other -SAC algorithms introduce different kind of error terms.

1) I think the computation of "thisErr" should be put before the computation of the "betterModel" (the error term of the current subset S1* should be computed before computing a new model)

2) Considering the section is stating : "The generic RANSAC algorithm works as the following pseudocode: ". I think it should be made clear that the "thisErr" is the cardinal of the subset S1*. Eventually adding a comment stating that other -SAC algorithms introduce other more robust error terms.

Can someone confirm this so we could modify the Pseudocode section ? 194.199.174.237 (talk) 09:55, 22 May 2024 (UTC)