RANSAC算法详解

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

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

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

4、可参考下图：关于算法的源代码，Ziv Yaniv曾经写一个不错的C+版本，我在关键处增补了注释：C代码白#in elude#in eludeLi neParamEstimator.hLineParamEstimator: LineParamEstimator (double delta ) : m_deltaSquared (delta * delta ) */* Compute the line parameters n_x,n_y,a_x,a_y*通过输入的两点来确定所在直线，采用法线向量的方式来表示，以兼容平 行或垂直的情况*其中n_x,n_y为归一化后，与原点构成的法线向量，a_x,a

5、_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(nx/norm);parameters.push_back(ny/norm);parame

6、ters.push_back(data 0-x);parameters.push_back(data 0-y); _/*/* Compute the line parameters n_x,n_y,a_x,a_y*使用最小二乘法，从输入点中拟合出确定直线模型的所需参量*/ &data ,stdvector ¶meters )double meanX, meanY, nx , ny , norm ;double covMatll , covMat12 , covMat21 , covMat22 ; / The entr ies of the symmetric covari nace m

7、atrixint i , dataSize = data . size ();parameters . clear ();if (data . size () x;meanY +=data i - y;covMatll+=data i -x* datai- x;covMat12+=data i -x* datai- y;covMat22+=data i -y* datai- y;meanX /= dataSize ;meanY /= dataSize ;covMat11-= dataSize* meanX meanXcovMat12-= dataSize * meanX mea nYcovMa

8、t22-= dataSize*mea nY*mea nYcovMat21= covMat12;if (covMatll 1e-12 ) nx=1.0 ;ny=0.0 ;else /lamdal is the largest eige nvalue of the covaria nee matrix/and is used to compute the eig ne-vector corresp onding to the smallest/eige nv alue, which isnt computed explicitly.double lamdal = (covMatll + covMa

9、t22 + sqrt ( covMatll - covMat22 )*( covMatll - covMat22 ) + 4*covMat12 *covMat12 ) / 2.0 ;nx = - covMat12 ;ny= lamdal- covMat22 ;norm = sqrt (nx*nx + ny *ny);nx/= n orm;ny/= norm;parameters.push_back(nx);parameters.push_back(ny);parameters.push_back(meanX);parameters . push_back (meanY); _/*/* Give

10、 n 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*通过与已知法线的点乘结果，确定待测点与已知直线的匹配程度；结果越 小则越符合，为*零则表明点在直线上*/bool LineParamEstimator: agree (std : vector parameters,Point2D &data )double signedDistanee= parameters 0*( data . x-parameters 2)+ parameters 1*( data .

11、y- parameters 3);return( signedDistanee*signedDistanee) m_deltaSquared );RANSAC寻找匹配的代码如下：C代码离/*/template double Ransac: compute (std : vector ¶meters , Paramete rEsitmator * paramEstimator , std : vector &data , int numForEstimate )std : vector leastSquaresEstimateData ;int numDataObjects= data

12、. size ();int num VotesForBest= -1;int *arr = new int numForEstimate ;/ numForEstimate 表示拟合模型所需要的最少点数，对本例的直线来说，该值为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

13、model, otherwise zero/there are less data objects than the minimum required for an exact fitif (numDataObjects numForEstimate )return 0;/计算所有可能的直线，寻找其中误差最小的解。对于100点的直线拟合来说，大约需要100*99*0.5=4950次运算，复杂度无疑是庞大的。一般米用随机选取子集的方式。computeAIIChoices ( paramEstimator , data , numForEstimate , bestVotes, curVotes

14、, numVotesForBest , 0, data . size(), numForEstimate , 0, arr );/compute the least squares estimate using the largest sub setfor (int j =0; j leastSquaresEstimate (leastSquaresEstimateD ata , parameters );deletearr ;deletebestVotes ;deletecurVotes ;return( double ) leastSquaresEstimateData . size ()/( double ) numDataObjects;在模型确定以及最大迭代次数允许的情况下，RANSAC总是能找到最优解。经过我的实验，对于包含 80%误差的数据集，RANSAC的效果远优于直接的最小 二乘法。RANSAC可以用于哪些场景呢？最著名的莫过于图片的拼接技术。优于镜头 的限制，往往需要多张照片才能拍下那种巨幅的风景。在多幅图像合成时，事先会在待合成的图片中提取一些关键的特征点