基本RANSAC的原理

本文主要参考以下几篇博文以及提供的源代码，在此感谢原作者： 1、https://www.cnblogs.com/xrwang/p/SampleOfRansac.htm 2、https://blog.csdn.net/weixin_40023317/article/details/90215182 3、https://grunt1223.iteye.com/blog/961063 4、https://www.cnblogs.com/littlepear/p/10129861.html

RANSAC为Random Sample Consensus的缩写，它是根据一组包含异常数据的样本数据集，计算出数据的数学模型参数，得到有效样本数据的算法。它于1981年由Fischler和Bolles最先提出 。该算法在计算机视觉中广泛应用。

RANSAC算法的基本假设是样本中包含正确数据(inliers，可以被模型描述的数据)，也包含异常数据(outliers，偏离正常范围很远、无法适应数学模型的数据)，即数据集中含有噪声。这些异常数据可能是由于错误的测量、错误的假设、错误的计算等产生的。同时RANSAC也假设，给定一组正确的数据，存在可以计算出符合这些数据的模型参数的方法。 因此，RANSAC通过反复选择数据中的一组随机子集来达成目标。被选取的子集被假设为局内点，并用下述方法进行验证：

基本RANSAC算法流程：

随机抽取部分数据认为选中的数据是inliers, 并构建数学模型。用1中得到的模型去测试所有的其它数据，如果某个点适用于估计的模型，认为它也是局内点，否是就是局外点。统计1中模型的局内点数目。重复1~3给定的次数，维护全局最值，认为局内点最多的模型为我们最终需要的模型。

直线拟合案例讲解：

接下来以直线拟合为例，首先在给定的n个观测点中，随机选取2个点，然后计算出一条直线：y=ax+b; 然后计算其余点到这条直线的距离，如果距离小于给定的阈值，那么这个点就是一个局内点，统计出所有的 局内点数目，接下来反复选取2个点，计算直线方程，再次统计局内点数目。最终得到最多局内点的直线方程认为是观测点的模型。如下图所示：

事实上，在很多情况下，最小二乘法也可以拟合直线。 但是，遗憾的是，最小二乘法只适合与误差较小的情况。试想一下这种情况，假使需要从一个噪音较大的数据集中提取模型（比方说只有20%的数据时符合模型的）时，最小二乘法就显得力不从心了。例如下图，肉眼可以很轻易地看出一条直线（模式），但算法却找错了。 比如下面的情况就很明显： RANSAC的算法步骤可以参看下图： RANSAC核心代码如下所示：

private void btnGetLine_Click(object sender, EventArgs e){ //用RANSAC方法获取最佳直线 points = GetSamplePoints(); Line bestLine = null; //最佳直线 double bestInliersCount = 0; //最佳模型的局内点数目 Random random = new Random(); for (int idx = 0; idx < nudIterCount.Value; idx++){ //反复迭代测试 int idx1, idx2; GetRandomInliersPoints(random, out idx1, out idx2); //随机选取2个点 int inliersCount = 2; Line line = new Line(points[idx1], points[idx2]); for (int i = 0; i < points.Count; i++){ if (i != idx1 && i != idx2){ if (line.GetDistance(points[i]) <= (double)nudMinDistance.Value) inliersCount++; //点到直线距离小于阈值则局内点数目++ } } if (inliersCount >= nudMinPointCount.Value){ //维护全局最多局内点数目 if (inliersCount > bestInliersCount){ bestLine = line; bestInliersCount = inliersCount; } } } //显示最佳直线 if (bestLine != null) { lblFormula.Text = string.Format("方程:{0}\r\nA:{1}\r\nB:{2}\r\nC:{3}\r\n局内点数目:{4}", bestLine.ToString(), bestLine.A, bestLine.B, bestLine.C, bestInliersCount); DrawLine(bestLine); } else lblFormula.Text = "没有获取到最佳直线。"; }

RANSAC代码中还可以拟合圆，当然点到圆的距离定义为：点到圆周的距离。 详细代码参见：https://share.weiyun.com/52AD5qr

计算机视觉中常用于匹配图片的关键点并用于后续的相机位姿估计或图片拼接，下图展现了图片拼接的案例：