I use pcl's SampleConsensusPrerejective method and it works well. I use it as described in the tutorial. But I don't fully understand how the RANSAC algorithm works. The features are computed with FPFH.
As I understood the algorithm takes random features from the input-cloud and from the target-cloud and projects the input cloud on the computed pose at the target cloud. Then calculating a consensus set and after some iteration take the pose with the biggest consensus set. So far so good.
But how are these features compared and the pose computed? I don't understand yet how the feature histograms based on the points quadrupel <α, ϕ, θ, d> really help. What exactly happens after picking e.g. three example features from input and target cloud?
Can anyone explain in simple words what happens next? Thank you so much!
I am not too familiar with this library but I can explain what RANSAC does in general as well as can provide some ideas as to what their algorithm might be doing as I have a lot of experience in related optimization algorithms.
RANSAC is a very general optimization algorithm designed to find the solution in presence of outliers. Imagine you are given a linear equation a*x_i+b=y_i and you need to find a and b for given x_i and y_i. Normally simple least squares solves the problem but in presence of outliers least squares method fails miserably - resulting in a completely wrong solution.
With RANSAC one one can take two random indexes i,j find best a and b, draw the line and check how well this given line approximates the set of points (x_i,y_i). Then after a sequence of attempts you pick the best one and call it the solution or given the best sample set select the total inliers with their solution and make a best fit with them. This methodology should filter out any outliers given enough samples or result in failure - one just needs to check the final result for common sense.
One can also play with the "how well the line approximates the set of points". User decides the criteria. Maximize inlier amount given threshold or minimize error of the median. Whatever as long as it makes sense.
You can apply RANSAC to almost any optimization process, given an error functions and an optimization mechanism.
How does their optimization works? I don't know. Ask their developers, read their code or documentation. But I can provide you with some ideas how it might be working.
Given feature points (A,B,C) in original cloud and three matching features in the target cloud (X,Y,Z) one can determine positive orthogonal affine transformation (rotation + shift) that maps (A,B,C) to (X,Y,Z) - or make a best fit if they don't exactly match. One will need four points if you also consider also negative orthogonal transformations (reflection + rotation + shift) and not just positive ones. This is just a classic linear algebra. Four points might be preferable in any case for better accuracy of the solution as data is surely noisy.
After finding a solution candidate one can match whole clouds to see if they fit each other with the given solution - this is the error function (check out their implementation to see the exact criteria).
If you simply randomize features A, B, C, X, Y, Z randomly, you'll eventually find the solution but it will take a ridiculous amount of time making it impractical. Therefore, I believe they have some methods to narrow down the required number of tests. Say, if they had a function f, possibly a very erroneous one, that for each feature in original cloud fits a match in target cloud. Then you can simply check sets of points (A,B,C) vs (f(A),f(B),f(C)). But they might have something more complex and tricky for better robustness.
Hope it gives you some understanding of such algorithms.