RANSAC Fitting

本系列文章由 @YhL_Leo 出品，转载请注明出处。
文章链接： http://blog.****.net/yhl_leo/article/details/73294793

---

RANSAC 算法是一种常用的估计模型参数的方法，相关的算法介绍网上有很多，这里不再累述，主要介绍如何利用RANSAC 方法进行 2D 直线以及 3D 平面拟合。

Source code (python version): Github/yhlleo/RANSAC-fit

---

1 拟合模型

之所以要自己去实现算法，主要是由于可以直接使用的代码程序和函数库，对于直线以及平面方程一般使用：

• lines: y=ax+b
• planes: z=ax+by+c

这样不通用的表达方式，对于自然情景中的很多线性回归问题，一般没什么问题，但是对于一些简单的应用情景，比如本文提到的直线、平面拟合问题，就不具有绝对的通用性，比如斜率不存在的line : x=n, n∈R，上述的直线方程就无法拟合，同理平面拟合也存在类似问题。因此，采用下面的方法更具有一般性：

• lines: ax+by+c=0
• planes: ax+by+cz+d=0

对于 2D 直线采用两点式方程，给定直线上任意不同两点p(x1,y1), q(x2,y2)，则有：

展开为点积式：

进而可以得到：

在对直线进行归一化处理：

同时，如果 a≠0，令 a>0, 否则令 b>0。

3D 平面则采用三点式直线方程，给定平面上任意不共线的三点{pi(xi,yi), i=1,2,3.}， 则有：

对等式左边行列式按照第一行，进行行展开可得：

进而可得：

同样进行归一化处理：

拟合过程中，判断inlier 和 outlier的判别函数，分别采用点到直线、平面的距离公式：

• point to line: d=|ax0+by0+c|
• point to plane: d=|ax0+by0+cz0+d|

注： 因为对直线和平面都已经进行了归一化处理，所以计算距离部分的分母都略去。

迭代过程如图：

2 优化拟合模型

通过简单的迭代获得的模型，可以满足inliers 数量最大，但是并不一定最优，可以根据inliers的特征值以及特征向量进行优化，这里把测试的结果图展示如下：

---

• References:
  
  • https://en.wikipedia.org/wiki/Random_sample_consensus
  • Robust linear model estimation using RANSAC
  • Performance Evaluation of RANSAC Family