RANSAC stands for RANDOM SAMPLE CONSENSUS. This algorithm was established by Fischler and Bolles in 1981. Since then, there have been multiple variants proposed for using the RANSAC algorithm. Some of these variants were used by Nardinocci et al(2001) and Forlani et al (2003) for extraction of planar features or to put in simply to extract buildings using LiDAR data.
A brief description of the RANSAC algorithm could be found at WikiPedia. You might sneer at me for giving a reference to Wikipedia, but believe me, it makes the understanding of the algorithm simpler. Can I make it more simpler? Yes, I could. Just keep on reading.
Let us assume that we are just talking about extracting planes. Further, let us assume that we are given a set of N points, where N > 3 . Let us also assume that our data contains at least one plane. Now, for a point to belong to a plane, it should be within a certain distance from it. We have to ask the user of the algorithm regarding that distance. Let this distance "threshold" be t.
It is a well known fact that to define a plane, we need just 3 points. So, what do we do? Pick 3 points randomly from the set. This will define the plane. But, is this the right plane? We will have to find the distances of the remaining points from this plane. The points that would "belong" to the plane (points that are within a distance of t from the plane) are called "inliers". Record the three points and its number of inliers. Let us call this record as best_model.
Let us do another iteration of this. Pick another set of 3 points, defining a plane. Find the inliers for the plane. If the number of inliers are greater than those in the best_model, delete the record maintained earlier and save this one.
Now, we shall keep on doing this for a certain number iterations k.
You might argue that if N is the given number of points, and every time we have to extract 3 points from the set, then the right number of iterations would be C(N,3)! Turns out to be a fairly huge number if one were to do this for all the points! Fear not, there is an algorithm coded by Peter Kovesi where these problems are solved! In fact, the Wikipedia page also gives a hint of the process.
Now that we have solved the problem of the number of iterations, we must now concentrate on how do determine the exact threshold t for fitting the plane. Fischler and Bolles (1981) suggest that this can be achieved either by experiment or by analytical methods. There is a book titled Topographic Laser Scanning and Ranging in which Chapter Number 14 deals with determination of the threshold for a set a set of points. This chapter has been written by Frederic Bretar. Bretar uses an icosahedron to "collect" the normals of the points to find out the right threshold. I am however, not convinced by the method but he has claimed in his paper Bretar and Roux (2005) that this works.
A brief description of the RANSAC algorithm could be found at WikiPedia. You might sneer at me for giving a reference to Wikipedia, but believe me, it makes the understanding of the algorithm simpler. Can I make it more simpler? Yes, I could. Just keep on reading.
Let us assume that we are just talking about extracting planes. Further, let us assume that we are given a set of N points, where N > 3 . Let us also assume that our data contains at least one plane. Now, for a point to belong to a plane, it should be within a certain distance from it. We have to ask the user of the algorithm regarding that distance. Let this distance "threshold" be t.
It is a well known fact that to define a plane, we need just 3 points. So, what do we do? Pick 3 points randomly from the set. This will define the plane. But, is this the right plane? We will have to find the distances of the remaining points from this plane. The points that would "belong" to the plane (points that are within a distance of t from the plane) are called "inliers". Record the three points and its number of inliers. Let us call this record as best_model.
Let us do another iteration of this. Pick another set of 3 points, defining a plane. Find the inliers for the plane. If the number of inliers are greater than those in the best_model, delete the record maintained earlier and save this one.
Now, we shall keep on doing this for a certain number iterations k.
You might argue that if N is the given number of points, and every time we have to extract 3 points from the set, then the right number of iterations would be C(N,3)! Turns out to be a fairly huge number if one were to do this for all the points! Fear not, there is an algorithm coded by Peter Kovesi where these problems are solved! In fact, the Wikipedia page also gives a hint of the process.
Now that we have solved the problem of the number of iterations, we must now concentrate on how do determine the exact threshold t for fitting the plane. Fischler and Bolles (1981) suggest that this can be achieved either by experiment or by analytical methods. There is a book titled Topographic Laser Scanning and Ranging in which Chapter Number 14 deals with determination of the threshold for a set a set of points. This chapter has been written by Frederic Bretar. Bretar uses an icosahedron to "collect" the normals of the points to find out the right threshold. I am however, not convinced by the method but he has claimed in his paper Bretar and Roux (2005) that this works.
