![RANSAC算法详解_第1页](http://file3.renrendoc.com/fileroot_temp3/2022-1/17/b42310ba-d987-4b38-8882-693dfe0c7185/b42310ba-d987-4b38-8882-693dfe0c71851.gif)
![RANSAC算法详解_第2页](http://file3.renrendoc.com/fileroot_temp3/2022-1/17/b42310ba-d987-4b38-8882-693dfe0c7185/b42310ba-d987-4b38-8882-693dfe0c71852.gif)
![RANSAC算法详解_第3页](http://file3.renrendoc.com/fileroot_temp3/2022-1/17/b42310ba-d987-4b38-8882-693dfe0c7185/b42310ba-d987-4b38-8882-693dfe0c71853.gif)
![RANSAC算法详解_第4页](http://file3.renrendoc.com/fileroot_temp3/2022-1/17/b42310ba-d987-4b38-8882-693dfe0c7185/b42310ba-d987-4b38-8882-693dfe0c71854.gif)
![RANSAC算法详解_第5页](http://file3.renrendoc.com/fileroot_temp3/2022-1/17/b42310ba-d987-4b38-8882-693dfe0c7185/b42310ba-d987-4b38-8882-693dfe0c71855.gif)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
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可以用
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 七年级道德与法治上册 第三单元 师长情谊 第六课 师生之间 第1框《走近老师》说课稿 新人教版
- DB21-T 3974-2024 露天矿地质灾害治理植被生态修复技术规范
- DB14-T 3056-2024 电子政务标准体系
- 2024-2034年中国补肾丸行业发展潜力预测及投资战略研究报告
- 吉林省双辽市八年级地理下册 10中国的地理差异教案 (新版)新人教版
- 八年级物理上册 第六章 质量与密度 第1节 质量教案 (新版)新人教版
- 《STM32技术及应用》教学大纲
- 湖北省武汉市武昌区C组联盟市级名校2024-2025学年初三数学试题全国三卷模拟卷2含解析
- 八年级道德与法治上册 第二单元 遵守社会规则 第四课 社会生活讲道德 第2框《以礼待人》教案 新人教版
- 暑假作业08阅读理解(原卷版)
- 快递收发登记表Excel模板
- 译林江苏版小学英语六年级上册知识点汇总
- 下肢动脉硬化闭塞课件
- 安全标准化培训课件341
- 植物妈妈有办法-说课稿(共21张PPT)
- 六年级上册语文习题课件 - 第二单元素养提升卷 人教部编版(共22张PPT)
- 厂房拆除方案5篇
- 宫腔镜手术并发气体栓塞抢救流程
- 露天工程爆破课件
- 三字经1-36课教案
- 冰片安全技术说明书(msds)
评论
0/150
提交评论