RANSAC算法（附RANSAC直线拟合C++与Python版本） ⽂章⽬录
RANSAC算法简介
RANSAC(RANdom SAmple Consensus，随机采样⼀致)算法是从⼀组含有“外点”(outliers)的数据中正确估计数学模型参数的迭代算法。“外点”⼀般指的的数据中的噪声，⽐如说匹配中的误匹配和估计曲线中的离点。所以，RANSAC也是⼀种“外点”检测算法。RANSAC是⼀个⾮确定性算法，在某种意义上说，它会产⽣⼀个在⼀定概率下合理的结果，其允许使⽤更多次的迭代来使其概率增加。RANSAC算最早是由Fischler和Bolles在SRI上提出⽤来解决LDP(Location Determination Problem，位置确定问题)问题的。 对于RANSAC算法来说⼀个基本的假设就是数据是由“内点”和“外点”组成的。“内点”就是组成模型参数的数据，“外点”就是不适合模型的数据。同时RANSAC假设：在给定⼀组含有少部分“内点”的数据，存在⼀个程序可以估计出符合“内点”的模型。 RANSAC算法基本思想和流程
RANSAC的思想⽐较简单，主要有以下⼏步：
给定⼀个数据集***S***，从中选择建⽴模型所需的最⼩样本数（空间直线最少可以由两个点确定，所以最⼩样本数是2，空间平⾯可以根据不共线三点确定，所以最⼩样本数为3，拟⼀个圆时，最⼩样本数是3），记选择数据集为***S1***
使⽤选择的数据集***S1***计算得到⼀个数学模型***M1***
⽤计算的模型***M1*去测试数据集中剩余的点，如果测试的数据点在误差允许的范围内，则将该数据点判为内点(inlier)，否则判为外点(outlier)，记所有内点组成的数据集为S1，S1 称作 ***S1***的⼀致性集合
⽐较当前模型和之前推出的最好的模型的“内点”的数量，记录最⼤“内点”数量时模型参数和“内点”数量
重复1-4步，直到迭代结束或者当前模型已经⾜够好了(“内点数⽬⼤于设定的阈值”)；每次产⽣的模型要么因为内点太少⽽被舍弃，要么因为⽐现有的模型更好⽽被选⽤
以RANSAC直线拟合为例，如下图所⽰，⾸先在点集中随机选择两个点，求解它们构成的直线参数，再计算点集中剩余点到该直线的距离，距离⼩于设置的距离阈值的点为内点，统计内点个数；接下来再随机选取两个点，同样统计内点个数，以此类推；其中内点个数最多的
点集即为最⼤⼀致集，最后将该最⼤⼀致集⾥⾯的点利⽤最⼩⼆乘拟合出⼀条直线。
迭代次数推导
根据上⾯RANSAC基本原理的介绍，在这算法流程中存在两个重要的参数需要设置，迭代次数（采样次数）和距离阈值。
迭代的次数我们应该选择多⼤呢？这个值是否可以事先知道应该设为多少呢？还是只能凭经验决定呢？ 这个值其实是可以估算出来的。下⾯我们就来推算⼀下。
假设内点在数据中的占⽐为t:
那么我们每次计算模型使⽤n个点的情况下，选取的点⾄少有⼀个外点的概率为：
那么，在迭代k次计算模型都⾄少采样的⼀个外点的概率为：
$ (1-t k$
那么，能采样到正确的n个内点去计算出正模型的概率就是：
t =n +n inliers outliers
n inliers
1−t n
n)P =1−(1−t )n k
上式等效为：
然后，对上式的两边取对数，得到：
内点的概率t通常是⼀个先验值。然后P 是我们希望RANSAC得到正确模型的概率。如果事先不知道t 的值，可以使⽤⾃适应迭代次数的⽅法。也就是⼀开始设定⼀个⽆穷⼤的迭代次数，然后每次更新模型参数估计的时候，⽤当前的内点⽐值当成t 来估算出迭代次数。RANSAC 与最⼩⼆乘区别
最⼩⼆乘法尽量去适应包括外点在内的所有点。因此，最⼩⼆乘法只适合与误差较⼩的情况。试想⼀下这种情况，假使需要从⼀个噪⾳较⼤的数据集中提取模型（⽐⽅说只有20%的数据时符合模型的）时，最⼩⼆乘法就显得⼒不从⼼了。例如下图，⾁眼可以很轻易地看出⼀条直
线（模式），但算法却错了。
相反，RANSAC能得出⼀个仅仅⽤内点计算出模型，并且概率还⾜够⾼。但是，RANSAC并不能保证结果⼀定正确，为了保证算法有⾜够⾼的合理概率，必须⼩⼼的选择算法的参数（迭代次数，点与模
型之间误差阈值）。经实验验证，对于包含80%误差的数据集，RANSAC 的效果远优于直接的最⼩⼆乘法。
RANSAC 直线拟合代码（C++及Python 版本）
C++版本代码
结合OpenCV库实现了RANSAC直线拟合，在主函数中给出了⼀个例⼦，仅供⼤家参考。
//====================================================================//
//Program:RANSAC 直线拟合，并与最⼩⼆乘法结果进⾏对⽐
//Data:2020.2.29
//Author:liheng
//Version:V1.0
//====================================================================//
#include <iostream>
拟合直线#include <opencv2/opencv.hpp>
//RANSAC 拟合2D 直线
//输⼊参数：points--输⼊点集
1−P =(1−t )n k
k =log (1−t )
n log (1−P )
// iterations--迭代次数
// sigma--数据和模型之间可接受的差值，车道线像素宽带⼀般为10左右
// （Parameter use to compute the fitting score）
// k_min/k_max--拟合的直线斜率的取值范围.
// 考虑到左右车道线在图像中的斜率位于⼀定范围内，
/
/ 添加此参数，同时可以避免检测垂线和⽔平线
//输出参数:line--拟合的直线参数,It is a vector of 4 floats
// (vx, vy, x0, y0) where (vx, vy) is a normalized
// vector collinear to the line and (x0, y0) is some
// point on the line.
//返回值：⽆
void fitLineRansac(const std::vector<cv::Point2f>& points,
cv::Vec4f &line,
int iterations = 1000,
double sigma = 1.,
double k_min = -7.,
double k_max = 7.)
{
unsigned int n = points.size();
if(n<2)
{
return;
}
cv::RNG rng;
double bestScore = -1.;
for(int k=0; k<iterations; k++)
{
int i1=0, i2=0;
while(i1==i2)
{
i1 = rng(n);
i2 = rng(n);
}
const cv::Point2f& p1 = points[i1];
const cv::Point2f& p2 = points[i2];
cv::Point2f dp = p2-p1;//直线的⽅向向量
dp *= 1./norm(dp);
double score = 0;
if(dp.y/dp.x<=k_max && dp.y/dp.x>=k_min )
{
for(int i=0; i<n; i++)
{
cv::Point2f v = points[i]-p1;
double d = v.y*dp.x - v.x*dp.y;//向量a与b叉乘/向量b的摸.||b||=1./norm(dp) //score += exp(-0.5*d*d/(sigma*sigma));//误差定义⽅式的⼀种
if( fabs(d)<sigma )
score += 1;
}
}
if(score > bestScore)
{
line = cv::Vec4f(dp.x, dp.y, p1.x, p1.y);
bestScore = score;
}
}
}
int main()
{
cv::Mat image(720,1280,CV_8UC3,cv::Scalar(125,125,125));
//以车道线参数为(0.7657,-0.6432,534,548)⽣成⼀系列点 double k = -0.6432/0.7657;
double b = 548 - k*534;
std::vector<cv::Point2f> points;
for (int i = 360; i < 720; i+=10)
{
cv::Point2f point(int((i-b)/k),i);
}
//加⼊直线的随机噪声
cv::RNG rng((unsigned)time(NULL));
for (int i = 360; i < 720; i+=10)
{
int x = int((i-b)/k);
x = rng.uniform(x-10,x+10);
int y = i;
y = rng.uniform(y-30,y+30);
cv::Point2f point(x,y);
}
//加⼊噪声
for (int i = 0; i < 720; i+=20)
{
int x = rng.uniform(1,640);
int y = rng.uniform(1,360);
cv::Point2f point(x,y);
}
int n = points.size();
for (int j = 0; j < n; ++j)
{
cv::circle(image,points[j],5,cv::Scalar(0,0,0),-1);
}
//RANSAC 拟合
if(1)
{
cv::Vec4f lineParam;
fitLineRansac(points,lineParam,1000,10);
double k = lineParam[1] / lineParam[0];
double b = lineParam[3] - k*lineParam[2];
cv::Point p1,p2;
p1.y = 720;
p1.x = ( p1.y - b) / k;
p2.y = 360;
p2.x = (p2.y-b) / k;
cv::line(image,p1,p2,cv::Scalar(0,255,0),2);
}
/
/最⼩⼆乘法拟合
if(1)
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议