RANSAC介绍（Matlab版直线拟合+平⾯拟合） 转载⾃： blog.csdn/u010128736/article/details/53422070
⼀、RANSAC介绍
随机抽样⼀致算法（RANdom SAmple Consensus,RANSAC），采⽤迭代的⽅式从⼀组包含离的被观测数据中估算 随机抽样⼀致算法（RANdom SAmple Consensus,RANSAC） 出数学模型的参数。该算法最早由Fischler和Bolles于1981年提出。RANSAC算法假设数据中包含正确数据和异常数据（或称为噪声）。正确数据记为内点（inliers），异常数据记为外点（outliers）。同时RANSAC也假设，给定⼀组正确的数据，存在可以 核⼼思想就是随机性和假设性，随机性是根据正确数据出现概率去随机选取抽样计算出符合这些数据的模型参数的⽅法。该算法核⼼思想就是随机性和假设性 数据，根据⼤数定律，随机性模拟可以近似得到正确结果。假设性是假设选取出的抽样数据都是正确数据，然后⽤这些正确数据通过问题满⾜的模型，去计算其他点，然后对这次结果进⾏⼀个评分。
直线拟合、平⾯拟合、计算图像或点云间的变换矩阵、计算 RANSAC算法被⼴泛应⽤在计算机视觉领
域和数学领域，例如直线拟合、平⾯拟合、计算图像或点云间的变换矩阵、计算基础矩阵等⽅⾯，使⽤的⾮常多。本⽂将在对RANSAC介绍完后，附两段直线拟合以及平⾯拟合的matlab代码。关于计算机视觉基础矩阵
中基于RANSAC框架的矩阵求解问题，在OpenCV中都有对应的函数接⼝，如果以后有机会再把这个整理出来。
⼆、算法基本思想
如下图所⽰，存在很多离散的点，⽽我们认为这些点构成了⼀条直线。当然，⼈眼能很清晰地拟合出这条直线，到外点。但要让计算机到这条直线，在很久之前是很难的，RACSAC的出现是通过数学之美解决这⼀难题的重要发明。
通过实例对算法基本思想进⾏描述：
（1）⾸先，我们知道要得到⼀个直线模型，我们需要两个点唯⼀确定⼀个直线⽅程。所以第⼀步我们随机
随机选择两个点。
（2）通过这两个点，我们可以计算出这两个点所表⽰的模型⽅程y=ax+b。
（3）我们将所有的数据点套到这个模型中计算误差。
（4）我们到所有满⾜误差阈值的点，第4幅图中可以看到，只有很少的点⽀持这个模型。
（5）然后我们再重复（1）~（4）这个过程，直到达到⼀定迭代次数后，我们选出那个被⽀持的最多的模型，作为问题的解。如下图所⽰：
以上是对RANSAC算法的基本思想的介绍，我们可以发现，虽然这个数据集中外点和内点的⽐例⼏乎相等，但是RANSAC算法还是能到最合适的解。试想⼀下，这个问题如果使⽤最⼩⼆乘法进⾏优化，由于噪声数据的⼲扰，我们得到的结果肯定是⼀个错误的结果，如下图所⽰。这是由于最⼩⼆乘法是⼀个将外点参与讨论的代价优化问题，⽽RANSAC是⼀个使⽤内点进⾏优化的问题。经实验验证，对于包含80%误差的数据集，RANSAC的效果远优于直接的最⼩⼆乘法。
三、RANSAC的数学推导
我们假设内点在整个数据集中的概率为t，即：
确定该问题的模型需要n个点，这个n是根据问题⽽定义的，例如拟合直线时n为2，平⾯拟合时n=3，求解点云之间的刚性变换矩阵时n=3，求解图像之间的射影变换矩阵是n=4，等等。k表⽰迭代次数，即随机选取n个点计算模型的次数。P为在这些参数下得到正确解的概率。为⽅便表⽰，我们可以得到，n个点都是内点的概率为 ，则n个点中⾄少有⼀个是外点的概率为
表⽰k次随机抽样中都没有到⼀次全是内点的情况，这个时候得到的是错误解，也就是：
内点概率t是⼀个先验值，可以给出⼀些鲁棒的值。同时也可以看出，即使t给的过于乐观，也可以通过增加迭代次数k，来保证正确解的概率P。同样的，我们可以通过上⾯式⼦计算出来迭代次数k，即我们假设需要正确概率为P（例如我们需要99%的概率取到正确解），则：
四、利⽤RANSAC拟合直线
clc;clear all;close all;
%%%⼆维直线拟合
%%%⽣成随机数据
%内点
mu=[0 0]; %均值
S=[1 2.5;2.5 8]; %协⽅差
data1=mvnrnd(mu,S,200); %产⽣200个⾼斯分布数据
%外点
mu=[2 2];
S=[8 0;0 8];
data2=mvnrnd(mu,S,100); %产⽣100个噪声数据
%合并数据
data=[data1',data2'];
iter = 100;
拟合直线
%%% 绘制数据点
figure;plot(data(1,:),data(2,:),'o');hold on; % 显⽰数据点
number = size(data,2); % 总点数
bestParameter1=0; bestParameter2=0; % 最佳匹配的参数
sigma = 1;
pretotal=0; %符合拟合模型的数据的个数
for i=1:iter
%%% 随机选择两个点
idx = randperm(number,2);
sample = data(:,idx);
%%%拟合直线⽅程 y=kx+b
line = zeros(1,3);
x = sample(:, 1);
y = sample(:, 2);
k=(y(1)-y(2))/(x(1)-x(2)); %直线斜率
b = y(1) - k*x(1);
line = [k -1 b]
mask=abs(line*[data; ones(1,size(data,2))]); %求每个数据到拟合直线的距离
total=sum(mask<sigma); %计算数据距离直线⼩于⼀定阈值的数据的个数
if total>pretotal %到符合拟合直线数据最多的拟合直线
pretotal=total;
bestline=line; %到最好的拟合直线
end
end
%显⽰符合最佳拟合的数据
mask=abs(bestline*[data; ones(1,size(data,2))])<sigma;
hold on;
k=1;
for i=1:length(mask)
if mask(i)
inliers(1,k) = data(1,i);
k=k+1;
plot(data(1,i),data(2,i),'+');
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 end
end
%%% 绘制最佳匹配曲线
bestParameter1 = -bestline(1)/bestline(2);
bestParameter2 = -bestline(3)/bestline(2);
xAxis = min(inliers(1,:)):max(inliers(1,:));
yAxis = bestParameter1*xAxis + bestParameter2;
plot(xAxis,yAxis,'r-','LineWidth',2);
title(['bestLine: y = ',num2str(bestParameter1),'x + ',num2str(bestParameter2)]);
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议