Friday, April 15, 2011

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.  


2 comments:

  1. Good stuff. Peter kovesi's code seems really fast. But indeed as you have noted; all the code is only intended for "educational" purposes. You can really see by the structure of the code that it corresponds with the original RANSAC algorithm when invented. A reference to that paper here would be complementary i think.

    ReplyDelete