![]() | This article is rated C-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||||
|
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)
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)
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)
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)
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)
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)
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 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(:,:).
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)
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)
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)
![]() | This article is rated C-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||||
|
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)
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)
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)
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)
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)
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)
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 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(:,:).
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)
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)
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)