RANSAC-like implementation for arbitrary 2D sets

Question

TL;DR : Is there a C++ implementation of RANSAC or other robust correspondence algorithms that is freely usable with arbitrary 2D point sets?

I know that many implementations exist that include or make use of correspondence algorithms such as RANSAC (Random Sampling Consensus). They are often used in computer vision applications and found in libraries such as OpenCV, PCL, etc. The general algorithm is well known and various site lists the different steps.

Now, all the "advanced" implementations (done for OpenCV, PCL, etc.) I have found are for specific types of problem with an underlying set of assumptions. In OpenCV, you want to find the homography matrix between a first image and a portion of a second image (this example). In PCL, you are in the realm of 3D point clouds and you are (to my knowledge) only able to match specific, already defined shapes (a line, a sphere, etc.).

What I "simply" want to do is to take an arbitrary 2D set of points (which may contain some noise) and find a correspondence in a bigger set of 2D points (which contain some noise and other points too). It has to require no specific model training other than inputting the two sets of points. I am in the process of implementing it myself in C++, but:

• I am by no mean an experienced programmer and I need the whole thing to executed quite fast; previous implementation done by myself of well known algorithms (edge detection, Gaussian blurring, etc.) have proven to be significantly slower (>10x) than proven implementation.

• Simply ripping off an already existing open source implementation (such as OpenCV's) have proven to be beyond my current capabilities (too much dependencies and virtual implementation-template and else...)

So, if anyone knows of a freely usable (BSD like) and proven C++ implementation that I have missed...

Solution 1

It's surprisingly hard to find a popular, lightweight, generic C++ implementation of RANSAC. I just released my generic RANSAC implementation under the MIT license.

https://github.com/drsrinathsridhar/GRANSAC

GRANSAC is generic, templated, header-only, and multithreaded. The user has to implement a class that inherits the AbstractModel. RANSAC estimation can then be done for any kind of model (eg.: 2D lines, 3D planes).

I have tested this only for 2D line fitting but should work for other problems too. Would be happy to add more features (such as automatically choosing number of iterations, etc.)

Solution 2

A good-looking RANSAC, LMedS, MSAC, MLESAC C++ implementation for Windows and Linux is here: https://github.com/sunglok/rtl.

RTL: RANSAC Template Library RANSAC Template Library (RTL) is an open-source robust regression tool especially with RANSAC family. RTL aims to provide fast, accurate, and easy ways to estimate any model parameters with data contaminated with outliers (incorrect data). RTL includes recent RANSAC variants with their performance evaluation with several models with synthetic and real data. RTL is written in generic programming style (template in C++) for its further applications with user-defined models. RTL is distributed under Simplified BSD License.

The basic class is RANSAC:

template <class Model, class Datum, class Data>
class RANSAC;

Other classes are inherited from it:

template <class Model, class Datum, class Data>
class MLESAC : virtual public RANSAC<Model, Datum, Data>
...

The usage is simple (an example from README):

// Find the best model using RANSAC
LineEstimator estimator;
RTL::RANSAC<Line, Point, std::vector<Point> > ransac(&estimator);
Line model;
double loss = ransac.FindBest(model, data, data.size(), 2);

// Determine inliers using the best model if necessary
std::vector<int> inliers = ransac.FindInliers(model, data, data.size());

The paper: https://sites.google.com/site/sunglok/files/Choi09_bmvc.pdf?attredirects=0

Solution 3

I was looking for something like that and then I found this.

The code is in c++ at bottom part.

The function below was originaly extracted from this class.

cv::Mat ransacTest(const std::vector<cv::DMatch>& matches, const std::vector<cv::KeyPoint>& keypoints1,const std::vector<cv::KeyPoint>& keypoints2, std::vector<cv::DMatch>& outMatches) {

   // Convert keypoints into Point2f
   std::vector<cv::Point2f> points1, points2;
   cv::Mat fundemental;

   for (std::vector<cv::DMatch>::const_iterator it= matches.begin(); it!= matches.end(); ++it) {
       // Get the position of left keypoints
       float x= keypoints1[it->queryIdx].pt.x;
       float y= keypoints1[it->queryIdx].pt.y;
       points1.push_back(cv::Point2f(x,y));
       // Get the position of right keypoints
       x= keypoints2[it->trainIdx].pt.x;
       y= keypoints2[it->trainIdx].pt.y;
       points2.push_back(cv::Point2f(x,y));
   }

   // Compute F matrix using RANSAC
   std::vector<uchar> inliers(points1.size(),0);

   if ( points1.size() > 0 && points2.size() > 0 ){

      cv::Mat fundemental= cv::findFundamentalMat(
            cv::Mat(points1),cv::Mat(points2), // matching points
            inliers,       // match status (inlier or outlier)
            CV_FM_RANSAC,  // RANSAC method
            3.0,           // distance to epipolar line
            0.99);         // confidence probability

      // extract the surviving (inliers) matches
      std::vector<uchar>::const_iterator itIn= inliers.begin();
      std::vector<cv::DMatch>::const_iterator itM= matches.begin();

      // for all matches
      for ( ;itIn!= inliers.end(); ++itIn, ++itM) {
         if (*itIn) { // it is a valid match
            outMatches.push_back(*itM);
         }
      }

      // The F matrix will be recomputed with all accepted matches
      // Convert keypoints into Point2f for final F computation

      points1.clear();
      points2.clear();

      for (std::vector<cv::DMatch>::const_iterator it= outMatches.begin(); it!=outMatches.end(); ++it) {
        // Get the position of left keypoints
        float x= keypoints1[it->queryIdx].pt.x;
        float y= keypoints1[it->queryIdx].pt.y;
        points1.push_back(cv::Point2f(x,y));
        // Get the position of right keypoints
        x= keypoints2[it->trainIdx].pt.x;
        y= keypoints2[it->trainIdx].pt.y;
        points2.push_back(cv::Point2f(x,y));
     }

     // Compute 8-point F from all accepted matches
     if( points1.size() > 0 && points2.size() > 0){
        fundemental= cv::findFundamentalMat(
        cv::Mat(points1),cv::Mat(points2), // matches
        CV_FM_8POINT); // 8-point method
     }

   }

   return fundemental;

}

Comments

[Srinath Sridhar]

Not sure what you mean by two arbitrary point sets. Do you mean to ask if it would fit two separate models for the two point sets?

[Doombot]

Well, I mean that instead of fitting an arbitrary line to a point sets, I would like to fit a first point set A to a second point set B. Of course, there would be outliers in both sets, but it is the point of RANSAC of rejecting outliers. Is that precise enough?

[Srinath Sridhar]

RANSAC is an estimation method used when you know what the mathematical model of your observations are. In the above example, we know that the points roughly form a line. So unless you have a parametric representation of the model you cannot use RANSAC. The problem you describe seems to be more of a matching problem best solved by optimization or perhaps Procrustes: en.wikipedia.org/wiki/Procrustes_analysis

[Doombot]

Ah, thanks for the Procrustes terminology, didn't know that. Actually, RANSAC-like algorithms are used the way I described it in Computer Vision, such as in the section 3.2 of this paper vision.ece.ucsb.edu/sites/vision.ece.ucsb.edu/files/… . It is often used as an intermediary step in the process of computing an homography.

[Srinath Sridhar]

Sure, estimating homographies is the most common RANSAC application and my implementation can be used for this. In this case, a mathematical model is already defined (homography parametrized by 4 points). The output would be a "best" homography and point correspondences that are inliers to this homography. But this is not really aligning point sets, is it?

[Srinath Sridhar]

Adding to the above comment. I realize that alignment/fitting usually means finding a rigid transform between the point sets. A homography is a projective transform (a superset containing rigid transforms). So you could do the same but with a rigid transform matrix. But remember that RANSAC only gives a model that has most of the input as inliers (aka removes outliers). You would have to run something on top of the inliers to get your final model. This could be a least squares fit for example or Procrustes (which IIRC is equivalent to the least squares solution for point set matching).

[Doombot]

Thanks for the precision :)

[Humam Helfawi]

this post should take more attention

[geisterfurz007]

A link to a solution is welcome, but please ensure your answer is useful without it: add context around the link so your fellow users will have some idea what it is and why it’s there, then quote the most relevant part of the page you're linking to in case the target page is unavailable. Answers that are little more than a link may be deleted.

[CognitiveRobot]

Hello @trig-ger, I am looking for python implementation of MSAC, MLESAC, can't find them. Do you know any? Thanks.