RANSAC拟合直线

RANSAC是“RANdom SAmple Consensus（随机抽样一致）”的缩写。它可以从一组包含“局外点”的观测数据集中，通过迭代方式估计数学模型的参数。它是一种不确定的算法——它有一定的概率得出一个合理的结果；为了提高概率必须提高迭代次数。该算法最早由Fischler和Bolles于1981年提出。核心思想就是随机性和假设性，随机性用于减少计算，循环次数是利用正确数据出现的概率。所谓的假设性，就是说随机抽出来的数据都认为是正确的，并以此去计算其他点，获得其他满足变换关系的点，然后利用投票机制，选出获票最多的那一个变换。

RANSAC的基本假设是：
（1）数据由“局内点”组成，例如：数据的分布可以用一些模型参数来解释；
（2）“局外点”是不能适应该模型的数据；
（3）除此之外的数据属于噪声。
局外点产生的原因有：噪声的极值；错误的测量方法；对数据的错误假设。

1.1算法实现

本文以拟合三维空间直线为例说明RANSAC拟合过程，同理可以拟合平面直线，空间平面等；步骤如下：

步骤一：从数据中选择建立模型所需的最小样本数（空间直线最少可以由两个点确定，所以最小样本数是2，空间平面可以根据不共线三点确定，所以最小样本数为3），从样本中选择两个点，计算数学模型参数，即两点确定的直线的方向向量。

步骤二：计算所有其他点到该直线的距离d,通过设置阈值Td, 所有d<Td的点成为内点，统计内点的个数。

步骤三：重复以上步骤，选择内点个数最多的以此作为最优结果。

具体实现过程需要考虑自己的数据设置具体的阈值Td,以及循环的次数。

2、实现过程

本文以空间三维直线的RANSAC拟合为例，显示MATLAB代码：

function [paraN,point,data_line,inLier_Index]=RANSAC_line(data)

%输出参数分别为拟合的直线的方向向量，经过的点，所有的内点，以及内点的索引号
num_points=size(data,1);
pretotal=0;
Threshold=0.3;
Max_Iter=5000;
for i=1:Max_Iter
    idx = randperm(num_points,2);
    sample=data(idx,:);%随机选择两个点
    x=sample(:,1);
    y=sample(:,2);
    z=sample(:,3);
    %判断距离是否过近 排除距离过近的情况
    n12=[x(1)-x(2),y(1)-y(2),z(1)-z(2)];
    dist12=norm(n12);
    if dist12<0.01
        continue
    end
    %拟合直线
    %计算点到直线的距离
    p_p0=data-[x(1) y(1) z(1)];
    n12=n12/norm(n12);%归一化
    nAll=repmat(n12,num_points,1);
    cross_value=cross(p_p0,nAll);
    Distance=sum(cross_value.*cross_value,2);
    inLierIndex=find(Distance<Threshold);
    total=size(inLierIndex,1);
    if total>pretotal
        pretotal=total;
        paraN=n12;
        point=[x(1) y(1) z(1)];
        inLier_Index=inLierIndex;
        data_line=data(inLier_Index,:);
    end
end
% figure;
% plot3(data_line(:,1),data_line(:,2),data_line(:,3),'r+');
% grid on;
% hold on;
% X=[point(1)-20*paraN(1) point(1)+20*paraN(1)];
% Y=[point(2)-20*paraN(2) point(2)+20*paraN(2)];
% Z=[point(3)-20*paraN(3) point(3)+20*paraN(3)];
% plot3(X,Y,Z,'b');grid on;
end

3、和最小二乘的比较及其优缺点

RANSAC与最小二乘区别：最小二乘法尽量去适应包括局外点在内的所有点。相反，RANSAC能得出一个仅仅用局内点计算出模型，并且概率还足够高。但是，RANSAC并不能保证结果一定正确，为了保证算法有足够高的合理概率，必须小心的选择算法的参数（参数配置）。经实验验证，对于包含80%误差的数据集，RANSAC的效果远优于直接的最小二乘法。

RANSAC可以对局外点进行剔除，这一点是比较好的，但它也并不是完美的，当它对于拟合两条平近似平行直线分布的点时，拟合出来的结果并不是最好的，甚至可以说拟合的结果是不对的。因为最终的正确结果有可能并不是经过所给的数据点的，如下图所示：

当我们要从如图所示的数据点中拟合出一条直线的时候（即把两条离得较近的近似的平行的线当做一条线来拟合），理想的情况是红线所示，但实际情况会如蓝线所示，因为红线所示的点并没有经过数据点中的两个点，RANSAC是从给的数据点中进行拟合选择内点最多的情况，而实际情况可能理想直线并不经过数据点，这是这个算法的局限所在。可以考虑将RANSAC和最小二乘结合进行，这样可以结合二者的优势，得到较为理想的结果。

最小二乘也有其局限性，一是它没有剔除局外点，拟合的是全局最优的，当局外点误差过大时，会极大的影响结果得到不正确的结果；

二是最小二乘对于近似垂直分布的点进行最小二乘拟合得到的结果是不正确的，因为最小二乘的原理是求得理想Y值与实际y值差的平方和的最小，当直线近似垂直时，很小的偏差都会导致很大的理想与实际y差值。对于这种情况拟合结果是不正确的。需要注意！！！

本博文参考一下文献，在此一并感谢：

https://www.cnblogs.com/dverdon/p/4579544.html

http://blog.****.net/u010128736/article/details/53422070