RANSAC Algorithm - Some Outputs

It is time to give you a glimpse of how the algorithms mentioned in the previous post perform. I would like to acknowledge Optech for providing this data, and I am taking liberties to show some output on a small "cutout" of the same.

From an aerial photograph, the object containing multiple planes is given below:

Screenshot of the object with multiple planes

Now, as we know, the real picture is never seen from an aerial photograph, so we also give you a screenshot of the data corresponding to this cutout.

LiDAR data for the corresponding object

The RANSAC algorithm basically requires an input regarding the threshold for finding the inliers to the planes. But are all detected planes or best_models acceptable? One who is working with LiDAR data would often say no. Therefore, we add another restriction to the RANSAC algorithm. We accept a result only if it contains more than a certain number of points.

We therefore, make some assumptions regarding the thresholds as follows:

1. The minimum number of points in a plane should be 40. 
2. The threshold for finding inliers would be say 0.20m. 

I am not mentioning here how we have selected these numbers. Maybe we could discuss them later. But the moot point of the discussion is that we should get similar results if we use the same thresholds.

Peter Kovesi's algorithm will always find out one best plane from the data set. So what I did is to follow an approach mentioned in Chapter 14 of the book titled Topographic Laser Scanning and Ranging which is authored by F. Bretar. To explain in brief, we find out one plane, remove the inliers from the dataset, find out a second plane, remove the inliers again and so on. We do this until we are not able to find a plane, or the number of remaining points is less than or equal to 3.

Output using Peter Kovesi's algorithm is shown in the following figure:

Detected planes (denoted by different colors) using the Peter Kovesi's algorithm

There were 9 planes detected, and  the program took about 10-15 seconds to execute. This code has been written in MATLAB and 10-15 seconds is a fairly good time for a code to execute. However, the results generated are not satisfactory, as it seems that the RANSAC algorithm preferably selects horizontal planes than the tilting ones. There are two mildly sloping planes in this dataset which do not touch but have parallel center lines. However, their slopes are not in the same direction. The algorithm detects the midriffs of both the planes as belonging to one!

Our next goal is to test the output using the Mobile Robot Programming Toolkit (MRPT), I have already provided you with the link of the demo code. MRPT is easily installable on the Ubuntu platforms using Synaptic. Just find mrpt and select all the installable software from the displayed list. I just customised the demo code to read the data (shown above) and execute the program.

The output given is as follows:

OpenGL screenshot (basic API of MRPT) to display the detected planes and point cloud

The program took 500 milliseconds to execute and it detected 12 planes (Remember! The thresholds are the same). However, the base display of planes is not proper and a study of the TPlane structure in the code is required.

Let us now go to Tim Zaman's code in MATLAB given on his website. What is appreciable is that Tim Zaman with all his humility does accept that his code is slow, but argues that it needs to be structured and readable. I agree with him. However, let us see how his code has performed with our data. Unfortunately Tim Zaman's code needs to be tuned further to be used for detecting multiple planes, and I am therefore providing you the elementary output (of detecting a single plane). Remember, the thresholds are always the same.

Output found with Tim Zaman's code (www.timzaman.nl)

Tim Zaman's code in MATLAB took more than 10 minutes to find out something like the above figure. I have been interacting with Tim to figure out the problems with the code.  

RANSAC Algorithm - Introduction

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.