任意2D集合的RANSAC实现

Question

TL;DR ：是否有用于任意二维点集的C ++实现的RANSAC或其他强健通信算法可免费使用？

我知道存在许多包括或利用诸如RANSAC（随机抽样一致性）等对应算法的实现。它们经常用于计算机视觉应用程序，并在库中找到，例如OpenCV，PCL等。该通用算法众所周知，并且各个网站列出了不同的步骤。

现在，我找到的所有“高级”实现（针对OpenCV，PCL等完成）都是针对具有潜在假设集的特定类型问题的。在OpenCV中，您希望在第一张图片和第二张图片的一部分之间找到单应矩阵（此示例）。在PCL中，您处于三维点云的领域，并且只能匹配特定的已定义形状（线，球等）。

我“简单”地想要做的是获取任意二维点集（可能包含一些噪声）并在更大的二维点集中找到对应点（其中包含一些噪声和其他点）。它必须不需要特定的模型训练，除了输入两个点集外。我正在使用C ++自己实现它，但：

• 我绝不是经验丰富的程序员，并且需要整个过程快速执行；我自己完成的众所周知算法的先前实现（边缘检测，高斯模糊等）已被证明明显较慢（> 10倍）。

• 仅仅复制一个已存在的开源实现（比如OpenCV）已经超出了我的能力范围（需要太多依赖和虚拟实现模板等...）

所以，如果有人知道我错过了已经被证明可以免费使用（类似BSD的）的C++实现...

- Doombot

---

你想用RANSAC实现类似这样的东西吗？https://dev59.com/NnrZa4cB1Zd3GeqP1l4j#20975486 - Micka

好的！实际上，具体的方法并不是那么重要，但我和这个问题的提问者处于类似的情况。谢谢，这将是一个好的开始！ :) - Doombot

Answer 1

很难找到一种流行的、轻量级的、通用的C++实现RANSAC算法。我刚刚发布了我的通用RANSAC实现，采用MIT许可证。

https://github.com/drsrinathsridhar/GRANSAC

GRANSAC是通用的、模板化的、仅有头文件的，并且支持多线程。用户需要实现一个继承AbstractModel类的类，然后就可以对任何类型的模型进行RANSAC估计（例如：2D线条，3D平面）。

我仅测试了2D线条拟合，但它应该也适用于其他问题。我很乐意添加更多功能（例如自动选择迭代次数等）。

- Srinath Sridhar

---

你说的"two arbitrary point sets"是什么意思？你的意思是问是否需要为这两个点集分别拟合模型吗？ - Srinath Sridhar

RANSAC是一种估计方法，用于当您知道观察结果的数学模型时使用。在上面的例子中，我们知道这些点大致形成一条直线。因此，除非您具有模型的参数表示，否则无法使用RANSAC。您描述的问题似乎更像是一个最优化或Procrustes分析可以解决的匹配问题：https://en.wikipedia.org/wiki/Procrustes_analysis - Srinath Sridhar

啊，谢谢你提供Procrustes术语，我之前不知道。实际上，在计算机视觉中，类似RANSAC的算法就是按照我描述的方式使用的，例如在这篇论文的3.2节中https://vision.ece.ucsb.edu/sites/vision.ece.ucsb.edu/files/publications/05ICIPMarco.pdf。它通常被用作计算单应性过程中的中间步骤。 - Doombot

当然，估计单应性矩阵是最常见的RANSAC应用之一，我的实现可以用于此。在这种情况下，数学模型已经定义好了（由4个点参数化的单应性矩阵）。输出将是一个“最佳”单应性矩阵和与该单应性矩阵相符的内点对应关系。但这并不是真正的点集对齐，不是吗？ - Srinath Sridhar

补充上面的评论。我意识到对齐/适配通常意味着在点集之间找到刚性变换。单应性是一个射影变换（包含刚性变换的超集）。因此，您可以使用刚性变换矩阵来完成相同的操作。但请记住，RANSAC仅提供大部分输入作为内点（也称为去除异常值）的模型。您需要在内点之上运行某些内容以获取最终模型。例如，这可以是最小二乘拟合或Procrustes（如果我没记错的话，它等价于点集匹配的最小二乘解）。 - Srinath Sridhar

Answer 2

这里提供了一个适用于Windows和Linux的RANSAC、LMedS、MSAC、MLESAC C++实现，且外观漂亮，可以在https://github.com/sunglok/rtl中找到。

RTL：RANSAC模板库RANSAC模板库（RTL）是一种开源的强健回归工具，特别适用于RANSAC家族。RTL旨在提供快速、准确和易于估计任何模型参数的方法，即使数据受到异常值（错误数据）的污染。RTL包括最近的RANSAC变体及其在合成和真实数据的多个模型上的性能评估。RTL采用通用编程风格（C++模板）编写，以便将来可用于用户定义的模型。RTL根据简化的BSD许可证进行分发。

基本类是RANSAC：

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

其他类从它继承：

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

使用方法很简单（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());

这篇论文：https://sites.google.com/site/sunglok/files/Choi09_bmvc.pdf?attredirects=0

- trig-ger

---

欢迎提供解决方案的链接，但请确保您的答案即使没有链接也是有用的：在链接周围添加上下文，以便其他用户知道它是什么以及为什么存在，然后引用您链接的页面中最相关的部分，以防目标页面不可用。仅仅是一个链接的答案可能会被删除。 - geisterfurz007

你好 @trig-ger，我正在寻找 MSAC、MLESAC 的 Python 实现，但是找不到。你知道有没有吗？谢谢。 - CognitiveRobot

Answer 3

我正在寻找这样的东西，然后我发现了this。

代码在底部的C++部分。

下面的函数最初是从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;

}

- Thalisson.ns

Answer 4

可能已经晚了，但我发现Theiasfm的RANSAC实现非常高效、代码编写良好且易于实现。该库的作者还记录了如何在documentation中包含自己的估计器模块。为了满足这样一个小需求而获取整个库可能有些过度，但我在这里发布这个消息是因为它非常有效。需要注意的一点是它使用了Eigen v3.3.7和Ceres v1.14。要了解其工作原理，您可以查看作者为RANSAC编写的单元测试。此外，它还实现了多个版本的RANSAC，例如：USAC、PROSAC等...

- AlAhm