迭代最近点算法综述上课讲义.doc
《迭代最近点算法综述上课讲义.doc》由会员分享,可在线阅读,更多相关《迭代最近点算法综述上课讲义.doc(11页珍藏版)》请在咨信网上搜索。
1、迭代最近点算法综述精品文档迭代最近点算法综述摘要:三维点集配准问题是计算机技术中的一个极其重要的问题,作为解决三维点集配准问题的一个应用较为广泛的算法,ICP算法得到了研究者的关注,本文以一种全新的思路从配准元素的选择、配准策略的确定和误差函数的求解等3个方面对三维点集配准的ICP算法的各种改进和优化进行了分类和总结。关键词:三维点集;迭代最近点;配准1 引言在计算机应用领域,三维点集配准是一个非常重要的中间步骤,它在表面重建、三维物体识别、相机定位等问题中有着极其重要的应用1。对于三维点集配准问题,研究者提出了很多解决方案,如点标记法、自旋图像、主曲率方法、遗传算法、随机采样一致性算法等等,
2、这些算法各有特色,在许多特定的情况下能够解决配准的问题。但是应用最广泛的,影响最大的还是由Besl和Mckay在1992年提出的迭代最近点算法2(Iterative Closest Point,ICP),它是基于纯粹几何模型的三维物体对准算法,由于它的强大功能以及高的精确度,很快就成为了曲面配准中的主流算法。随着ICP算法的广泛应用,许多研究者对ICP算法做了详细的研究,分析了该算法的缺陷和特点,提出了许多有价值的改进,推动了这一重要算法的发展。本文着眼于ICP算法的发展历程,详细介绍了ICP算法的基本原理,总结其发展和改进的过程,对于该算法的各个阶段的发展和变化做了简单的论述。2 ICP算法
3、原理2.1 ICP算法原理ICP算法主要用于三维物体的配准问题,可以理解为:给定两个来至不同坐标系的三维数据点集,找出两个点集的空间变换,以便它们能进行空间匹配。假定用表示空间第一个点集,第二个点集的对齐匹配变换为使下式的目标函数最小3。ICP算法的实质是基于最小二乘法的最优匹配算法,它重复进行“确定对应关系点集计算最优刚体变换”的过程,直到某个表示正确匹配的收敛准则得到满足。ICP 算法的母的是找到目标点集与参考点之间的旋转R和平移T变换,使得两匹配数据中间满足某种程度度量准则下的最优匹配。假设目标点集P的坐标为及参考点集Q的坐标为,在第k次迭代中计算与点集P的坐标相对应的对应点坐标为,计算
4、P与之间的变换矩阵并对原变换进行更新,直到数据间平均距离小于给定值,即满足式(1)最小。具体步骤4:(1) 在目标点集P中取点集;(2) 计算参考点集Q中对应点,使;(3) 计算旋转矩阵与平移向量,使得;(4) 计算;(5) 计算;(6) 如果不小于给定的返回到(2),直到或迭代次数大于预设的最大的迭代次数为止。对于ICP的每次迭代,最小化对应点的均方差使得点集更接近,而是在的最近点。这样,每一次迭代就使得更接近于。基于这样的思想,Besl等人证明了ICP算法的收敛性。2.2 ICP算法特性分析在三维点集配准的各种应用中,ICP算法的使用非常广泛,这是由于ICP算法有以下优点:l 可以获得非常
5、精确的配准效果;l 可以处理三维点集、参数曲面等多种形式表达的曲面,也就是说该算法对曲面表示方法独立5;l 不必对待处理的点集进行分割和特征提取;l 在较好的初值情况下,可以得到很好的算法收敛性6。虽然其得到了广泛的应用,但是对于最初的ICP算法,存在很多的不足之处,主要表现在:l 算法假设其中一个点集是另一个点集的子集,也就是说,一个点集必须含在另一个点集中,这一要求在很多时候难以满足;l 该算法在搜索对应点的过程中,计算代价非常的大;l 在基本的ICP算法中,在寻找对应点的时候,认为欧氏距离最近的点就是对应点,这种假设是比较武断的,它会产生一定数量的错误对应点7。针对上面的一些问题,许多研
6、究者提出了ICP算法的各种改进版本。为了说明ICP算法的不同改进版本,有必要将ICP算法分成几个阶段来讨论,在各个阶段的划分,国内外的研究学者也提出了自己的看法。主要的划分方法有,在Rusinkiewicz8的文章中,将ICP算法的进行分成了六个阶段,分别为:点集的选择、对应点对的配准、点对的权重确定、特定点对的剔除、误差矩阵的建立、误差矩阵最小化的求解;伍毅9则将其分为四个阶段:重采样、空间查找及距离度量、目标度量函数最小化和算法的迭代;Nishino10认为,不同的改进方法的差异不过体现在三个方面:配准策略、配准元素和误差度量。通过比较国内外学者提出的各种ICP算法的改进算法,可以知道,N
7、ishino的划分方法可以很好的反应算法所做改变的各个阶段。所以,在本文中将围绕ICP算法配准元素的选择、配准策略的确定和误差函数的求解等三个方面做的改进来展开。3 配准元素的选择在标准ICP算法中,选用点集中的所有点来计算对应的点,但是通常用于配准的点集元素数量都是非常巨大的,通过这些点集来计算,所消耗的时间也是很长的。所以在后来的研究当中,提出了各种各样的方法来选择配准元素,这些算法的主要目的无一例外的是为了减小点集元素的数目,即对匹配点集进行采样。既然涉及到采样,就有多种采样方法被尝试使用。Turk使用了一致采样方法11,Masuda12使用的式随机采样方法,而且在每一的迭代过程中都要进
8、行随机采样获取不同的采样点进行计算。也有一些学者提出了一些新的采样方法,这些方法主要特点是会利用点集的特征信息来减少点的数目,运用一些具有明显特征的点集来进行配准。比如,Weik13在文献中提到的,利用图像的梯度信息来选择符合要求的点,再用这些点来完成配准。Sappa14则是采用了另外一种策略,直接选取边缘点作为配准的选择点,这样就可以大大的减小配准点的数目。通过上面的分析可以发现,配准元素的选择的改进,主要集中在如何减小配准点的数目方面,即如何用最少的点来表征原始点集的全部特征信息。4 配准策略的确定上面介绍了ICP算法在配准元素选择方面做得一些改进,而更多的改进集中在配准策略方面。具体的配
9、准策略包括特征度量的选取和搜索策略的选取方面。4.1 特征度量的选取要寻找对应点对,就必须寻找场景数据点和模型数据点的特征差异,这就需要对特征进行度量。在利用特征度量获得对应点以后,还需要利用特征度量建立迭代优化的目标函数,为误差函数的求解奠定基础15。ICP算法被提出来时,采用的是欧氏距离作为特征度量,所以在这一阶段的改进方面,主要是围绕距离展开,很多研究者在这方面提出了自己的改进想法,当然有一些也并没有采用距离作为特征度量,在下面会做详细的介绍。4.1.1点到点的距离在标准ICP算法中,Besl和McKay直接采用的是点到点的欧氏距离。首先利用点到点的最小欧氏距离得到点到集合的距离,从而寻
10、找到对应点,再对这些对应点到集合的距离进行求和得到求解刚体变换的目标函数,如(1)式所示。简而言之,标准ICP算法使用的是点到点(point-to-point)的距离。4.1.2点到平面的距离Chen16利用的是场景点集中的点的法线与模型点集合的交点来确定对应点,得到对应点后,目标函数则采用的是点到面(point-to-plane)的距离,点到面的距离是指,场景数据集中的点到模型数据集合中的经过对应点的切平面的距离,如图l所示。场景点P中的点,它的法线与模型点集X的交点就被选择为的对应点。在建立目标函数时,使用的并不是到的距离,而是到模型点集X过的切平面的距离。图1 点到平面的距离点到平面的距
11、离减少了迭代次数,能够以更快的速度收敛到给定的阈值。Pulli对点到点的方法和点到面的方法进行了对比讨论17,他们指出与点到点的ICP算法相比,运用点到平面的距离的方法大大减少了计算量以及迭代次数,但是该方法的鲁棒性并不是太好。与上面的度量标准相类似的还有点到三角形的距离,它运用点与点之间的邻接信息,将三维点集三角化,以点到三角形表面的距离作为特征度量,与点到面的距离有一些相似,主要由张鸿宾和谢丰在文献中提出18。4.1.3豪斯多夫(Hausdorff)距离Hausdorff距离19作为一种距离测度,常用于衡量两个点集之间的相似程度。由于使用Hausdorff距离作为距离测度时无需考虑两个点集
12、中的点与点之间的对应关系,因此可以有效解决当图像中存在噪声和目标被部分遮挡时的识别问题。Ezra20研究了使用Hausdorff距离在ICP中的一些理论结果,还没有进行配准的实际应用。4.1.4几何特征严格的说,距离也是一种几何特征,这里指的几何特征是指除距离以外的几何特征。主要有法相量21、曲率等特征。加入几何特征更多的是为了在确定点对时加入限制条件,尽量减小误差点的数目。Pulli在文献中就加入了给定点对的限制条件,其中一个是每个点对对应的法向矢量差不能超过45度,而Godin22则是通过曲率来构造候选兼容点集。图2就是通过原始ICP算法和加入法相限制条件后获取的点对情况,其中空心箭头表示
13、法相矢量方向,黑色箭头表示找到的对应点对。(a) (b)图2 对应点对(a)通过传统ICP方法获得(b)中加入了法矢限制条件通过加入几何特征的限制条件,可以进一步的降低找到错误点对的概率,同时加入几何特征后,可以非常迅速的确定候选点集,可以大大的提高搜索速度。4.2 搜索策略在对应点的选取,也就是构造各对应点的过程中,需要进行大量的搜索过程,这是传统ICP算法的瓶颈,为了提高ICP算法的效率,提高搜索速度是很有必要的,所以如何改进搜索策略也是ICP算法研究的热点。Zhang在其论文中采用了多维二元搜索树23(K-D Tree),该算法可以自动的踢出异常值,可以处理非完全对应的点集合。Green
14、span分析了该树的特性,提出了近似多维二元搜索树24(AK-D Tree),达到了近似的效果,并提高了效率。另一种方法是依靠金字塔原理提出来的分级收缩算法25,大大加快了搜索速度。该方法通过评估目标区域距离值的方差和均匀拓扑映射来选择区域,在点集中进行逐级的收缩,先进行粗略定位,最后获取准确地对应点,对于搜索效率有很大的提高。投影的方法也被应用到ICP算法中来,Blais和Neugbeuaer采用反向定标26(Reverse Calibration)技术,就是使用的投影搜索算法。Benjemaa27则采用了具有多个投影平面的Z-buffer方法进行投影搜索。5 误差函数求解误差函数的求解,也
15、就是目标函数的最小化,是ICP算法的最后一个阶段。在求得目标函数后应该采用什么样的方法来求解目标函数,使其值能最快最准的的收敛到最小,也是一个比较重要的问题。传统的ICP算法的目标函数是通过点对点的距离建立的,其求解方法有基于奇异值分解的方法、四元数方法、正交矩阵法28和双四元数方法29。Eggert30评估了上述四种方法的精确性和稳定性,并且说明了这些方法存在的差异。由于基于奇异值分解的方法和四元数方法应用的更加广泛,所以,在下面将对这两种方法的实现方式做具体的介绍。5.1 基于奇异值分解的方法用奇异值分解法(SVD方法)来求解ICP算法过程中的几何参数最初是由ARUN31等提出来的,其并没
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 最近 算法 综述 上课 讲义
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【a199****6536】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【a199****6536】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。