CODEWITHSUNDEEP
c++opencvsignal-processingpoint-cloud-libraryransac
Doombot
Doombot

Reputation: 573

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:

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

Upvotes: 13

Views: 20040

Answers (4)

AlAhm
AlAhm

Reputation: 11

Might be too late, but I have found the RANSAC implementation from Theiasfm to be very efficient, well written and easy to implement. The author of the library documents how to also include your own estimator module in the documentation. It might be an overkill to get the whole library for such a small requirement, but I am posting this here since it works super well. One thing is that it uses Eigen v3.3.7 and Ceres v1.14. To get a feel of how it works, you could check the unit tests that the author has for RANSAC. Moreover, it implements several version of RANSAC for example: USAC, PROSAC etc...

Upvotes: 0

trig-ger
trig-ger

Reputation: 1205

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());

enter image description here

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

Upvotes: 3

Srinath Sridhar
Srinath Sridhar

Reputation: 1002

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

enter image description here

Upvotes: 22

Thalisson.ns
Thalisson.ns

Reputation: 55

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;

}

Upvotes: 1

Related Questions