RANSAC-like implementation for arbitrary 2D sets

问题:

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...

回答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.)

回答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

回答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;

}