基于Frobenius范数奇异值分解的快速ICP算法.pdf
《基于Frobenius范数奇异值分解的快速ICP算法.pdf》由会员分享,可在线阅读,更多相关《基于Frobenius范数奇异值分解的快速ICP算法.pdf(8页珍藏版)》请在咨信网上搜索。
1、第 21 卷 第 10 期2023 年 10 月Vol.21,No.10Oct.,2023太赫兹科学与电子信息学报Journal of Terahertz Science and Electronic Information Technology基于Frobenius范数奇异值分解的快速ICP算法许可a,顾尚泰*a,元志安a,万建伟a,马燕新b,王玲a(国防科技大学 a.电子科学学院;b.气象海洋学院,湖南 长沙 410073)摘要:迭代最近点法(ICP)及其变体是三维点云刚性配准的典型方法,但此类通过迭代计算逐点距离矩阵实现点云配准的方式,严重制约了点云的配准效率。本文提出一种快速 ICP
2、算法,利用 Frobenius 范数表示待配准的两幅点云之间的误差函数,获得误差值最小点位置,并对此位置进行奇异值分解,从而得到旋转矩阵和平移向量,极大压缩了迭代次数和配准时间。在 Standford数据集和 3DMatch 数据集上进行试验,与传统 ICP 算法及其变体、3 种基于学习的点云配准算法进行对比,本文方法配准效率最优;在达到相近的配准精确度时,提出的快速 ICP 方法的迭代次数仅为传统 ICP 算法的 0.2 倍,在 Standford 数据集上配准所需时间为传统 ICP 算法的 1/4,在 3D Match 数据集上配准所需时间为传统 ICP 算法的 1/8 倍。本文提出的快速
3、 ICP 算法在数据量大的点云场景下,具有更高的效率。关键词:三维计算机视觉;点云数据处理;点云配准;快速迭代最近点法;Frobenius范数;奇异值分解中图分类号:TN914.42 文献标志码:Adoi:10.11805/TKYDA2021369A fast ICP method based on Frobenius norm singular value decompositionA fast ICP method based on Frobenius norm singular value decompositionXU Kea,GU Shangtai*a,YUAN Zhiana,WAN
4、 Jianweia,MA Yanxinb,WANG Linga(a.College of Electronic Engineering,b.College of Meteorology and Oceanography,National University of Defense Technology,Changsha Hunan 410073,China)AbstractAbstract:Although Iterative Closest Point(ICP)algorithm and its variant are the basic method for 3D point cloud
5、rigid body registration,the point cloud iteration-based registration method get low convergence efficiency,severely constraining registration efficiency.In this paper,the Frobenius norm property is employed to represent error function between source point cloud and target point cloud,and due to the
6、property of the Frobenius norm,the closest distance between 2 point clouds can be converted into a single calculation form to get transformation matrix.This method greatly reduce iteration times and registration time.The experiment in this paper is compared with three classical ICP algorithms and th
7、ree learning-based algorithms on the Standford dataset and 3DMatch dataset respectively,and the registration time of fast ICP is less than that of other algorithms.When the registration accuracy is similar,the fast ICP method only has 20%of the iteration times of the traditional ICP algorithm,and 1/
8、4 times the registration time on the Standford dataset,1/8 times on the 3DMatch dataset of the traditional ICP algorithm.The fast ICP algorithm is more efficient when the amount of points is large.KeywordsKeywords:3D computer vision;point cloud data processing;point cloud registration;fast iterative
9、 closest point method;Frobenius norm;Singular Value Decomposition(SVD)随着三维数据获取方法和计算机算力不断提升,智慧城市建设逐渐深化,三维点云数据处理技术逐渐成为计算机感知外部世界,实现智能化处理的重要手段。三维模型重建、三维目标跟踪和位姿估计等应用都促进了点云配准技术的发展1。点云配准是为原始点云寻求一个最佳的刚体变换,实现与目标点云匹配和连接的过程,是计算机视觉中最基础性的问题。配准精确度越高,则三维重建后模型效果越好;配准速度越快,越有利于配文章编号:2095-4980(2023)10-1263-08收稿日期:2021
10、-10-15;修回日期:2021-12-26基金项目:国家自然科学基金创新研究群体资助项目(61921001)*通信作者:顾尚泰 email:太赫兹科学与电子信息学报第 21 卷准技术的应用。迭代最近点(ICP)算法2-3是解决点云配准问题的最经典的方法,通过交替进行最近点查询和最小化点云距离误差,实现对应点之间的匹配,保证达到局部最优的效果。但 ICP 算法在实际应用中难以达到理想效果,存在需要相对准确的初始位置,收敛速度慢,容易陷入局部最优等缺点4-5。为解决以上问题,对 ICP 算法的改进一直都是点云配准算法中的研究热点:a)利用局部点云曲率、法向量夹角6、栅格划分7去除点云冗余度,但这
11、些单一的精简策略常导致点云出现空洞或失去点云细节,从而降低配准精确度;b)构建有序拓扑关系,加速邻近点查找:通过体素化网格、八叉树加速最近点搜索过程,从而提高云配准效率;c)特征点提取与局部特征描述8,提高配准鲁棒性:依据刚体变换的旋转不变性提取点云表面法向量、曲率、几何特征或更高维特征,对所得特征进行匹配从而获取对应点。这种方法虽能有效改善配准精确度,但特征提取非常耗时,严重影响配准速度。基于上述问题和思路,本文提出一种快速 ICP 算法,在经典 ICP 算法的基础上,利用 Frobenius 范数性质,提出了可以直接旋转矩阵和平移向量闭合解的方法。相对于传统 ICP 方法,缩短了单次迭代的
12、时间;在 Frobenius范数表示的点云矩阵上进行奇异值分解(SVD),在实现理想的点云配准精确度的情况下,提高了点云配准效率。本文在 Standford 数据集9-10和 3DMatch 数据集11上,对比了 3 种基于学习的点云配准方法和 4 种传统的点云配准方法,本文提出的方法在配准时间和精确度方面具有更优的性能。1经典 ICP 算法ICP 算法本质上是基于最小二乘法的最优配准方法,该算法用迭代的方式选择最近点对,计算最优变换矩阵,直到满足正确配准的收敛精确度要求。ICP 算法的目的是通过迭代的方式获取待配准点云数据与参考点云数据之间的变换矩阵,使两幅点云数据之间满足最佳的度量准则,实
13、现配准,如图 1 所示。该方法需要待配准的 2 个点云有较好的初始位置,两者的重叠区域大致对齐。从目标点云中查询原始点云中所有数据点在另一片点云中的最近的位置作为对应点,利用所有点对求解出旋转和平移矩阵,再根据旋转平移矩阵调整待配准点云的位置,不断迭代前述过程,使点云之间的误差越来越小,直至满足阈值要求。给定原始点云P=pii=12n和目标点云Q=qii=12m,点云配准的关键问题是如何确定三维空间刚体变换中旋转矩阵 R 和平移向量 t,使得 Q 经过变换后与 P 的距离最小,如式(1)所示:Rt=argminRti=1mqi-()Rpi+t2(1)式中:pi P为qi Q的对应点;m为目标点
14、云的点数。按照以下步骤进行迭代:1)在 Q 中查询每一个点 pi所对应的距离最近的点;2)估计点对之间关系的变换矩阵 Rk和 tk,并记录此时的误差函数k=1mi=1mqi-Rkpi-tk2;3)将求解得到的旋转矩阵 Rk和平移向量 tk用于点云 Pk,得到变换后的点云 Pk+1;4)用 Pk+1代替原始点云 Pk重复上述步骤,直至达到预先设定的迭代次数或|k-k-1|小于预先设定的阈值D。K Arun1等在 1987 年提出了利用 SVD 方法估计两幅具有平移和旋转关系的点集之间相对关系,该方法对 2 个点集之间的欧氏距离进行奇异值分解,可估计出待配准点集之间的旋转矩阵和平移向量的闭合解。P
15、 J Besl 等2在 1992 年首次提出了 ICP 的计算流程和思路,通过迭代的方式交替进行两点云之间的变换矩阵的估计和误差函数的计算,最终收敛到阈值范围内。本文所对比的传统 ICP 算法是在 ICP 的经典计算框架下,利用 SVD 估计旋转矩阵和平移向量实现点云配准的方法。2基于 Frobenius 范数奇异值分解的快速 ICP本文提出的基于 Frobenius 范数的快速 ICP 算法,将矩阵范数引入刚体变换矩阵的求解过程中,通过计算原始点云矩阵和目标点云矩阵的代数运算特性,直接估计两点云之间的旋转矩阵和平移矩阵。Fig.1 Schematic diagram of ICP图1 ICP
16、算法原理示意图1264第 10 期许可等:基于Frobenius范数奇异值分解的快速ICP算法2.1 矩阵 Frobenius 范数及其性质Frobenius 范数是一种矩阵范数,简称 F-范数,通常记为 F,该范数定义为矩阵中每项数的平方和开方值。设A=aijm n为一个m n矩阵,则式(2)即为矩阵 A 的 Frobenius 范数表示。AF=defi=1mj=1n|aij2=tr()ATA(2)式中tr()为矩阵的迹。Frobenius 范数具有以下性质:A+B2F=A2F+B2F+2 ABF(3)ABF=tr(ABT)(4)2.2 Frobenius 范数推导和奇异值分解经典 ICP
17、算法通过迭代误差函数的最小化估计点云之间的旋转矩阵和平移矩阵,因此需要大量的运算存储资源,耗时长,不利于对目标的实时处理。本文利用 Frobenius 范数和奇异值分解直接估计出旋转和平移矩阵,在提升点云配准效率的同时,增强对噪声的鲁棒性。点云配准实质上是最小化原始点云和目标点云之间的误差函数的过程。在经典ICP算法流程中,迭代步骤2)步骤3)可以表示为式(5):Rk+1tk+1=argminRt1mi=1mqi-Rkpi-tk2(5)上述过程可拓展成 Procrustes 变换问题,误差函数可改写为:k+1=1mi=1mqi-Rpi-t2=Q-(RkPk+tk1T)2F(6)Q 在迭代过程中
18、始终不变,Pk为原始点云 P 经过 k 轮旋转平移后得到的点云矩阵,根据式(3),式(6)可化简为:k+1=Q-RkPk2F+-tk1T2F+2()Q-RkPk()-tk1TF(7)继而根据式(4)得:k+1=Q-RkPk2F+mtTt-2tr(Q-RkPk)1tT)(8)当式(8)的一阶导数为 0 时,k+1取得最小值。令k+1t=0,根据矩阵求导公式:()ATXxij=()AXTxij=aij=Aij(9)误差函数的一阶导数可以写成:k+1t=2mt-2(Q-RkPk)1=0(10)因此当t=1m(Q-RP)1时,取得最小值,将其代入误差函数式(8),则化简得:k+1=i=1m()qi-q
19、-R()pi-p2(11)式中p和q分别为原始点云 P 和目标点云 Q 的均值,p=1mi=1npi、q=1mi=1mqi。如果令qi=qi-q和pi=pi-p,则式(11)可进一步化简为:k+1=i=1mqi-Rkpi2=Q-RkPk2F=Q2F+RkPk2F-2 QRkPkF(12)1265太赫兹科学与电子信息学报第 21 卷由于旋转矩阵 R 不会影响范数的长度,根据 Frobenius 范数内积的性质,则式(12)可继续化简为:k+1=Q2F+Pk2F-2tr(RkPkQ)(13)将PkQ进行奇异值分解成VUT,则有:k+1=Q2F+Pk2F-2tr(RkVUT)=Q2F+Pk2F-2t
20、r(T)(14)其中Q2F和Pk2F与旋转矩阵Rk无关,若使误差函数为最小值,则需tr(T)为最大值。由于T=UTRkV为正交矩阵,Tii 1,因此若要取得最大值,则要求Tii=1,即 T 为单位对角阵。由此可得出结论,若使误差函数最小,必须满足以下 2 个条件:Rk+1=UVTtk+1=1m()Q-Rk+1Pk1(15)2.3 快速 ICP 算法依据上一节的理论推导,给定原始点云P和目标点云 Q,经典 ICP 算法可以改进为:1)在 Q 中查找P中每一个pi所对应的距离最近的点;2)计算Rt=argminRt1mi=1mqi-Rkpi-tk2:a)计算中心矩p=1mi=1npiq=1mi=1
21、mqi;b)对点云进行初始位置归一化处理:P=pi-p|piPi=12nQ=qi-q|qiQi=12m(16)c)计算PkQT并进行奇异值分解得 U 和 V;d)计算Rk=UVT和tk=q-Rkp。3)将 求 解 得 到 的 旋 转 矩 阵 Rk和 平 移 向 量 tk用 于 Pk,得 到 变 换 后 的 点 云 Pk+1,分 别 计 算k+1=i=1mqi-Rkpi-tk2,DR=Rk-Rk-1,Dt=tk-tk-1,若k+1小于阈值或DR、Dt小于阈值,则停止迭代;否则用Pk+1代替原始点云 Pk,重复上述步骤。3实验结果与分析为验证本文提出的快速 ICP 方法的效率和配准精确度,本文分别
22、在 Standford 数据集和 3DMatch 数据集上进行对比实 验,试 验 平 台 为:CPU 为 2.2 GHz 的 Core i7-8750H,RAM 为 32 GB,计算机系统为 64 bit Microsoft Windows 10,软件为 Matlab。3.1 Standford 3D Scanning Repository 数据集配准实验实验一:利用 The Standford 3D Scanning Repository 数据集中的Standford bunny、Happy Buddha、Dragon、Armadillo、Lucy 进 行 配 准 实 验,除 Lucy 以
23、外 的 4 个 模 型 均 使 用Cyberware 3030 MS 扫描仪采集数据,Lucky 则采用斯坦福米开朗基罗项目9开发的斯坦福大雕塑扫描仪。5 个点云模型作为实验材料,将模型点云的方位角、俯仰角、横滚角分别旋转 30、50、40;随机增加 10%离群点;对所有点叠加均值为 0、方差为 0.2 倍平均最小点距离的噪声作为原始点云,通过算法计算原始点云和模型点云之间的旋转变换矩阵实现点云的配准。首先将本文提出的算法与经典 ICP 算法进行比较。本实验使用的点云为 7 万至 8 万点,点的分布较为密集。实验中设置误差迭代阈值为Fig.2 Diagram of the number of
24、iteration on Happy Buddha图2 Happy Buddha 配准迭代次数对比图1266第 10 期许可等:基于Frobenius范数奇异值分解的快速ICP算法0.1 10-3,步进误差为 0.110-6,得到传统 ICP 和快速 ICP 在 Happy Buddha 模型上的迭代次数对比图(图 2)、配准效率一览表(表 1)和可视化配准效率对比图(图 3)。由图 2 和表 1 可以看出,应用在 Standford 数据集上的快速 ICP算法,在取得相同配准精确度的情况下,能够以更少的迭代时间和迭代次数实现点云配准,本文所提方法的配准效率相对于传统的 ICP 算法,提高了大
25、约 3 倍;且由表 1 可看出,本文提出的配准算法并不会因为配准效率的提升而损失精确度。由图 3 可直观发现,传统 ICP 算法(每个分图的左边)和快速 ICP 算法(每个分图的右边)在配准过程中会稍有不同,但由图 3(f)的配准细节可以看出,传统 ICP 方法和快速 ICP 方法都可以完成较为精确的点云配准,图中待配准的红色原始点云在细节处都能与蓝色的目标点云相匹配。3.2 Standford 数据集配准精确度实验为更深入探讨本算法与传统 ICP 算法在配准精确度和迭代次数的差异,实验二利用 Standford 数据集中的Happy Buddha 点云数据作为实验材料,将本文提出的快速 IC
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 Frobenius 范数 奇异 分解 快速 ICP 算法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。