RANSAC算法详解

1、给定两个点pl与p2的坐标,确定这两点所构成的直线,要求对于输入的任意点 p3,都可以判断它是否在该直线上.初中解析几何知识告诉我们,判断一个点在 直线上,只需其与直线上任意两点点斜率都相同即可.实际操作当中,往往会先根 据的两点算出直线的表达式点斜式、截距式等等,然后通过向量计算即可 方便地判断p3是否在该直线上.生产实践中的数据往往会有一定的偏差.例如我们知道两个变量X与Y之间呈线性关系,Y=aX+b ,我们想确定参数a与b的具体值.通过实验,可以 得到 一组X与Y的测试值.虽然理论上两个未知数的方程只需要两组值即可确认,但 由于系统误差的原因,任意取两点算出的a与b的值都不尽相同.我们希

2、望的是,最后计算得出的理论模型与测试值的误差最小.大学的高等数学课程中,详细 阐述了最小二乘法的思想.通过计算最小均方差关于参数a、b的偏导数为零时的值.事实上,在很多情况下,最小二乘法都是线性回归的代名词.遗憾的是,最小二乘法只适合与误差较小的情况.试想一下这种情况,假使 需要从一个噪音较大的数据集中提取模型比方说只有20%的数据时符合模型的时,最小二乘法就显得力不从心了.例如下列图,肉眼可以很轻易地看出一条直 线模式,但算法却找错了.Least squares fitRANSAC算法的输入是一组观测数据往往含有较大的噪声或无效点,一个用于解释观测数据的参数化模型以及一些可信的参数.RANS

3、AC通过反复选择数据中的一组随机子集来达成目标.被选取的子集被假设为局内点,并用下述方 法进行验证：?有一个模型适应于假设的局内点,即所有的未知参数都能从假设的局内点计算得 出.?用1中得到的模型去测试所有的其它数据,如果某个点适用于估计的模型,认为它 也是局内点.?如果有足够多的点被归类为假设的局内点,那么估计的模型就足够合理.?然后,用所有假设的局内点去重新估计模型譬如使用最小二乘法,由于它仅仅 被初始的假设局内点估计过.?最后,通过估计局内点与模型的错误率来评估模型.?上述过程被重复执行固定的次数,每次产生的模型要么由于局内点太少而被舍弃, 要么由于比现有的模型更好而被选用.整个过程可参

4、考下列图： Selwl: Miple om points nt 丽dm,CalcuLatc model panmjgs 止阅1 fil Ilie data in lh.e santple* Sekcl ianipk of ni pcionss al fandom* Cakulatc model闪海皿103 lLj! fil Lhd data iti itLe *七甲】e* 1. HkiihLE1 elliH fujnun Ibr icliduh pome* Scteci data that mppm cureiit hypotbesis* sc led Munpk of mi m* * J r

5、andom .* Cakuiaic mdcl paranKlers.Umi fii 由c &伍 in 也e sanipk,、, Cabmhle errar lunclioc. for. eacl) djita |JoijiL* Stlt dari that fciippd* rai l nl: hv|M)fhf*h4 Sded gamp肋of第情匕林 FMidnllii* CiilciiihEc ijamJcI pwaiucioi dim fit die 必为 io tlK sajnpk Caknilat error fbincii 口n 由Echd3场 pnwit* Scled da俯 th

6、前?npptnrr eiitTutnhyim 也即遇* RrpeiE miplkiig5关于算法的源代码,Ziv Yaniv曾经写一个不错的C+版本,我在关键处增补了注 释：C代码#include #include LineParamEstimator.hLineParamEstimator 二 LineParamEstimator (double delta ) : m_deltaSquared (delta * delta ) */* Compute the line parameters n_x,n_y,a_x,a_y*通过输入的两点来确定所在直纭 泵用京线而量的方式来表示,以兼容平行或

7、垂直的情况*其中n_x,n_y为归一化后,与原点构成的法线向量,a_x,a_y为直线上任 意一点*/void LineParamEstimator : estimate (std : vector &datastd : vector ¶meters )(parameters . clear ();if (data . size () y- data 0- y;doubleny= data 0- x- data 1- x;/原始直线的斜率为K,那么法线的斜率为-1/kdouble norm = sqrt ( nx* nx + ny * ny);parameters.push_back(n

8、x/ norm);parameters.push_back(ny/ norm);parameters.push_back(data 0-x);parameters.push_back(data 0-y);)./*/* Compute the line parameters n_x,n_y,a_x,a_y* 使用最小二乘法,从输入点中血合6确如直荻模型的所需参量* /void LineParamEstimator : leastSquaresEstimate (std : vector &data ,std: vector ¶meters )(double meanX, meanY, n

9、x , ny , norm ;double covMatll , covMat12 , covMat21 , covMat22 ; / The entr ies of the symmetric covarinace matrixint i , dataSize = data . size ();parameters . clear ();if (data . size () 2) return ;meanX = meanY = 0.0 ;covMat11 = covMat12 = covMat21 = covMat22 = 0;for (i =0; i x;meanY +=data i -

10、y;covMat11+=datai-x*data i-x;covMat12+=datai-x*data i-y;covMat22+=datai-y*data i-y;meanX /= dataSize ;meanY /= dataSize ;covMat11-= dataSize* mean* meanXcovMat12 -= dataSize * mean* meanYcovMat22-= dataSize* meanY* meanYcovMat21= covMat12;if (covMat11 1e-12 ) nx = 1.0 ;ny= 0.0 ;else /lamda1 is the l

11、argest eigenvalue of the covariance matrix/and is used to compute the eigne-vector corresponding to the smallest/eigenvalue, which isnt computed explicitly.double lamda1 = (covMat11 + covMat22 + sqrt ( covMat11 - covMat22 )*( covMat11 - covMat22 ) + 4* covMat12 *covMat12 ) / 2.0 ;nx = - covMat12 ;ny

12、= lamda1- covMat22 ;norm = sqrt ( nx* nx + ny *ny);nx/= norm;ny/= norm;parameters.push_back(nx);parameters.push_back(ny);parameters.push_back(meanX);parameters . push_back (meanY);)./*/* Given the line parameters n_x,n_y,a_x,a_y check if* n_x, n_y dot data.x-a_x, data.y-a_y m_delta* 疝过号法线的点命结果,确名寺测点

13、北直线的匹配程度；结果越 小那么越符合,为* 零那么说明点在直线上* /bool LineParamEstimator : agree (std : vector ¶meters,Point2D &data )(double signedDistance = parameters 0*( data . x-parameters 2) + parameters 1*( data . y- parameters 3);return ( signedDistance *signedDistance ) m_deltaSquared );)RANSAC寻找匹配的代码如下：C代码产*/templ

14、ate double Ransac: compute (std : vector ¶meters , Paramete rEsitmator * paramEstimator , std : vector &data , int numForEstimate )(std : vector leastSquaresEstimateData ;int numDataObjects = data . size ();int numVotesForBest = -1;int * arr = new int numForEstimate ;/ numForEstimate 表示拟合模型所需要的最

15、少点数,对本例的直线来说,该值为 2short *curVotes = new short numDataObjects ; /one if datai agrees with the current model, otherwise zeroshort *bestVotes = new short numDataObjects ; /one if datai agrees with the best model, otherwise zero/there are less data objects than the minimum required for an exact fitif (n

16、umDataObjects numForEstimate )return 0;/计算所有可能的直线,寻找其中误差最小的解.对于100点的直线拟合来说,大约需要100*99*0.5=4950次运算,复杂度无疑是庞大的.一般采用随机选取子集的方式.computeAllChoices ( paramEstimator , data , numForEstimate , bestVotes, curVotes , numVotesForBest , 0, data . size(), numForEstimate , 0, arr );/compute the least squares estima

17、te using the largest sub setfor (int j =0; j leastSquaresEstimate (leastSquaresEstimateD ata , parameters );delete 口 arr ;delete 口 bestVotes ;delete 口 curVotes ;return ( double ) leastSquaresEstimateData . size ()/( double ) num DataObjects ;在模型确定以及最大迭代次数允许的情况下,RANSAC总是能找到最优解.经过我的实验,对于包含 80%误差的数据集,RANSAC的效果远优于直接的最小 二乘法.RANSAC可以用