基于特征的点云配准与拼接技术研究

《基于特征的点云配准与拼接技术研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

基于特征的点云配准与拼接技术研究ResearchonTechnologyofPointCloudRegistrationandMosaicBasedonFeatures学科专业：仪器仪表工程研究生：孙小兵指导教师：钟莹副教授天津大学精密仪器与光电子工程学院二零一五年十二月 独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得天津大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。学位论文作者签名：签字日期：年月日学位论文版权使用授权书本学位论文作者完全了解天津大学有关保留、使用学位论文的规定。特授权天津大学可以将学位论文的全部或部分内容编入有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。（保密的学位论文在解密后适用本授权说明）学位论文作者签名：导师签名：签字日期：年月日签字日期：年月日 摘要随着计算图形学的发展，逆向工程在产品制造、考古研究、虚拟现实等很多领域得到了广泛应用。作为逆向的核心技术，点云配准得到了学者的深入研究。点云配准的两个主要应用领域是工件质量评估和模型拼接。本文以工件质量评估为例，提出基于特征的稀疏点云配准算法；以模型拼接为例，提出了基于特征的点云拼接算法。工件的加工精度对产品的性能有很大影响。三坐标测量机测量精度很高，可以获取工件测量数据。由于获取的点云为稀疏点云且含有很多平面、柱面特征，所以提出基于特征的稀疏点云配准算法。先人工选出待配准区域，删除多余部分，用最小二乘法进行平面特征提取，用Levenberg-Marquardt非线性最小二乘法进行柱面特征提取；使用特征建立局部坐标系，求出两簇点云间的旋转变换矩阵和平移矢量，完成初始配准；最后使用改进的ICP算法完成精确配准。设计了实验验证了本文算法精度的可靠性，最后用提出的算法完成两个零件加工误差的检测。模型拼接的思路一般是在重合区域寻找对应点对，求出刚体变换，完成拼接。本文提出与现有方法不同的拼接算法，对于点云中的每一个点，通过查找邻域计算法矢，通过坐标变换和抛物面拟合来求得每一点的曲率值；设定合适的阈值来挑选出特征点集；构造一个相似度量来确定对应点对；用法矢约束来确定最优配准的三个点对，并由这三个点对求出旋转变换矩阵和平移矢量，完成初始配准；同样使用改进的ICP配准算法完成精确配准。实验表明，提出的算法精度在1μm以内。关键词：逆向工程；点云配准；特征；质量评估；点云拼接； ABSTRACTWiththedevelopmentofcomputergraphics,reverseengineeringhasbeenwidelyusedinmanyfieldssuchasproductmanufacturing,archaeologicalresearch,virtualrealityandsoon.Asthecoretechnology,thepointcloudregistrationhasbeendeeplystudied.Twomainapplicationsofpointcloudregistrationarethequalityevaluationandthemodelmosaic.Aregistrationalgorithmofsparsepointcloudbasedonfeaturesisproposedwithqualityevaluationastheexample.Analgorithmofpointcloudmosaicbasedonfeaturesisproposedwiththemodelmosaicasexample.Themachiningaccuracyoftheworkpiecehasagreatinfluenceontheperformanceoftheproduct.Asthecoordinatemeasuringmachine(CMM)hashighmeasurementaccuracy,itcanbeusedtoacquirethedataofworkpiece.Asthepointcloudacquiredissparseandhasplaneandcylindricalfeatures,aregistrationalgorithmofsparsepointcloudbasedonfeaturesisproposed.First,theareatoberegisteredisselectedbyhandandtheredundantareaisdeleted.Theplanefeatureisextractedusingleastsquareprocedurewhilethecylindricalfeatureisextractedusingnolinear-leastsquaremethodofLevenberg-Marquardt.Thenlocalcoordinatesystemisbuiltbasedonthesefeatures,rotationtransformationmatrixandtranslationvectorbetweentwopointcloudiscalculatedandtheinitialregistrationiscompleted.Last,theimprovedICPalgorithmisappliedforpreciseregistration.Experimentsaredesignedtoverifythereliabilityofthealgorithm.Finally,machiningerroroftwoworkpiecesisdetectedusingthisalgorithm.Theideaofthemodelmosaicistofindthecorrespondingpointsintheoverlapregionandgetrigidtransformmatrix.Analgorithmofmosaicisproposeddifferentfromexistingmethods.Foreachpointinthepointcloud,normalvectoriscalculatedbysearchingtheneighborarea,andthecurvaturevalueofeachpointcanbeobtainedbymeansofcoordinatetransformationandparabolicfitting.Anappropriatethresholdissettoselectthefeaturepointset.Asimilaritymeasureisconstructedtodeterminethecorrespondingpoints.Threepairesofpointsforoptimalregistrationaredeterminedbyusingvectorconstraintandrotationtransformationmatrixandtranslationvectorarecalculatedusingthesethreepairesofpointsandinitialregistrationiscompleted.Similarily,theimprovedICPalgorithmisappliedfor preciseregistration.Experimentsdesignedindicatethatthealgorithmhashighaccuracy.KEYWORDS：reverseengineering,pointcloudregistration,features,qualityevaluation,modelmosaic 目录第一章绪论...........................................................................................................................................11.1课题研究背景及意义.............................................................................................................11.2点云配准技术介绍.................................................................................................................41.3国内外研究现状.....................................................................................................................51.4论文组织结构.........................................................................................................................7第二章点云数据预处理......................................................................................................................82.1点云数据分类.........................................................................................................................82.2点云数据去噪.........................................................................................................................82.3点云精简.................................................................................................................................9第三章基于特征的稀疏点云配准算法...........................................................................................113.1引言........................................................................................................................................113.1.1几种常见几何特征的简介......................................................................................113.1.2基于特征的稀疏点云配准算法的提出思路........................................................143.2配准数学模型.......................................................................................................................143.3基于特征的稀疏点云配准算法的步骤.............................................................................153.3.1特征提取...................................................................................................................153.3.2建立局部坐标系......................................................................................................173.3.3求解初配准变换矩阵.............................................................................................203.3.4局部点云的选取......................................................................................................203.3.5基于特征的稀疏点云配准算法............................................................................233.4实验验证...............................................................................................................................263.4.1误差求取原理..........................................................................................................263.4.2误差的显示方案.....................................................................................................273.4.3算法配准精度测试..................................................................................................283.4.4零件配准实验..........................................................................................................313.5本章小结...............................................................................................................................36第四章基于特征的点云拼接技术...................................................................................................374.1引言........................................................................................................................................374.2基于特征的点云拼接算法步骤..........................................................................................384.2.1曲率计算...................................................................................................................384.2.2提取特征点...............................................................................................................454.2.3找对应点对...............................................................................................................45 4.2.4找最优变换三点对..................................................................................................464.2.5改进的基于特征的拼接算法.................................................................................474.3实验验证...............................................................................................................................494.4本章小结...............................................................................................................................55第五章总结与展望............................................................................................................................565.1全文总结...............................................................................................................................565.2展望........................................................................................................................................56参考文献...............................................................................................................................................58发表论文与科研情况说明..................................................................................................................62致谢...............................................................................................................................................63 第一章绪论第一章绪论1.1课题研究背景及意义随着计算机的普遍应用，计算机图形学得到了迅速发展。计算机图形学是研究如何使用计算机生成、处理和显示图形的一门科学，它可以帮助我们更好地理解客观世界。随着计算机的发展，计算机图形学已经被广泛地应用在计算机游戏、人工智能、电影特效和计算机辅助设计制造等其他领域。计算机辅助设计制造是计算机图形学中非常重要并且应用非常广泛的领域。计算机辅助设计制造可以降低生产成本、缩短开发周期、提高产品质量。作为现代信息技术中的重要一员，计算机辅助设计为企业的创新能力的提高，科研成果的开发与转化，国家经济总量和国防实力等作出了巨大的贡献。在家庭用品、教育行业、建筑设计、电子设计、飞机设计等领域中都可以见到计算机辅助设计的身影。可以说计算机辅助设计制造是帮助企业提高竞争力的强大手段。逆向工程是计算机辅助制造技术的一[1]个重要方向，近年来被越来越多地应用到新产品的研发设计中。在工程设计中，设计人员根据头脑中的想法设计产品的尺寸、参数等，然后被送去加工成成品，这一过程为正向工程，它是一个从无到有的过程；与之相反，逆向工程是一个从有到无的过程，它的原理是对实物进行数据采集，根据数据重[2]构数字化模型，再进行分析、加工和处理。逆向工程的对象可以是机械零件、地貌、建筑物等。逆向工程的应用领域非常广阔，主要应用领域如下：在制造领域中，借助于逆向工程中的视觉检测系统，可以先扫描工件得到数据再与CAD模型进行比对，就可以检测出工件的各部分加工误差情况，从而检测出零件的加工缺陷，与传统方法相比，检测效率得到了很大的提高。在虚拟现实领域，可以使用扫描仪获取某些场景的三维模型，将实地场景转变为数字化漫游，配上专业的眼镜和观察系统，人们就可以在家中可以欣赏到世界各地的风景名胜。在医学领域，CT扫描可以帮助医生对患者的疾病进行分析，传统方法是经验丰富的医生对扫描图进行全面分析，才会得出结论，但这样受局限于医生的经验，且治疗费用很高。现在使用的新方法是先对健康病人扫描建立标准库，然后1 第一章绪论对将病人的扫描图与标准库进行比对，这样可以快速发现疾病所在，大大提高效率和准确率，并节省很多费用。在考古研究领域，在修复破损文物时，可以扫描该文物，再与已经建好的计算机模型进行比较，从而明确文物修复的方案。在其他领域如轿车设计中，先用模型设计出外观，再通过扫描仪获得表面点云，通过逆向工程软件重构三维模型，最后借助数控加工中心可以加工出实物。[1]逆向工程主要包括实物测量，数据处理，三维重构，数据配准，误差分析，流程如图1-1所示。实物测量数据处理三维重构数据配准误差分析图1-1逆向工程流程图关于实物测量，一般情况下可以分为接触式测量和非接触式测量。接触式测量中使用最多的是三坐标测量机,如图1-2所示，它的优点是测量精度很高，可达到纳米级，缺点是不能测量松软物体，测量效率低。因其具有的高精度，在逆向工程中有着广泛的应用；而非接触式测量有激光扫描测量法和投影光栅法，激光扫描法是一种基于三角测量原理的方法，它不与被测物体接触，因而可以测量柔软物体，且测量速度较快；投影光栅法也是一种基于三角测量原理的方法，与激光扫描法不同之处在于投影光栅法基于图像处理法得到图像坐标，在大规模数2 第一章绪论据采集的场合有着广泛的应用。工业CT是利用X射线或γ射线在被测物中的衰减分布情况来获取物体内部的信息，并利用计算机信息技术来显示物体的图像。立体视觉法，其原理是利用两个或多个相机从不同角度对物体进行拍摄，利用视差和相机的相对位置来计算物体的坐标。图1-3为非接触测量设备。图1-2三坐标测量机（a）三维激光扫描仪（b）工业CT图1-3非接触测量设备针对逆向工程的应用需求，市场中出现了一些逆向工程软件，比如RapidForm、CopyCAD、Imageware和GoemagicStudio，以及开源软件Meshlab、Pointshop3D和PointCloudLibrary等。其中最著名的软件是Imageware，它由美国EDS公司开发，采用NURB技术，应用领域广泛；GeomagicStudio由美国Raindrop公司开发，它可以方便地从点云数据重构多边形模型和网络，并自动生成NURBS曲面；CopyCAD是由英国DELCAM公司出品，它能从现有模型中生3 第一章绪论成三维CAD模型，能接受来自坐标测量机的数据。RapidForm由韩国INUS公司出品，可将点云数据实时运算出无接缝的多边形曲面。1.2点云配准技术介绍数据配准是逆向工程中最重要的环节，也是本文研究的核心环节。由于受设备的测量范围限制和被测物外形的约束，在获取被测物表面数据时，一次测量只能获得物体某一部分的数据，若要得到被测物的完整信息，需要从不同角度进行多次测量，而每次测量时点云处在不同坐标系中，它们之间存在旋转和平移，故需要将多次测量的数据统一到同一个坐标系中；在进行物体的误差检测和其他实物和模型比对的情形中，实物的测量数据和标准模型的数据也是处在不同的坐标系之中，因此也需要将两类数据统一起来。所谓点云配准，就是通过旋转平移等操作使不同坐标系中的点云数据统一到同一坐标系中的变换操作。根据维度划分，配准可以分为二维图形配准和三维图形配准，二维配准主要[3]使用灰度值配准而三维配准主要使用几何图形配准。二维图形配准在文字匹配领域应用广泛，其可分为基于几何不变量和局部特征两大类。本文研究的是三维图形配准。三维配准可以分为曲线配准和曲面配准。曲线配准为寻找两条空间曲线的三维变换，使两条曲线可以配准起来，该技术被用在文物的虚拟重构中，大致方法是先扫描不同文物碎片得到轮廓线，然后使用曲线配准将碎片拼接起来。本文研究的是曲面配准，而曲面配准又可分为全局配准和局部配准，全局配准是对两个图形整体对齐，一般用在工件的加工误差检测中，而局部配准主要用在模型拼接中。根据配准过程是否有人员和仪器参与，配准又可分为手动配准、仪器配准和自动配准。手动配准方法采用的是一种人机交互思想，在扫描测量数据之前，先在被测物表面贴上三个或三个以上不共线的标签，一般标签选在平坦光滑的区域，然后[4]在不同视角下得到测量数据，通过对比标签前后位置来实现点云配准。在文献中提出可以通过用鼠标在电脑屏幕上点击得到三个点对，一般是挑选特征明显的点对，然后由三个点对求出变换矩阵实现配准。这种配准方法的优势在于简单高效，缺点是得到的配准结果不精确，受人为因素影响比较大。仪器配准法指的是借助自动旋转平台进行数据采集，将测量设备搭建在旋转仪上，作为整体测量装置。在采集数据时，旋转台以固定的旋转角度旋转，且每旋转一次时，扫描仪就测量一次，这样转台旋转一周后，便得到了被测物的所有4 第一章绪论数据。然后通过旋转角度算出一个旋转矩阵，用该矩阵将相邻的点云拼接起来，用这种方法可以将所有数据拼接起来重构被测物形貌。另外一种仪器配准法称为[5][6]定标球法，该方法主要用在大型场景中，原理是测量前先将定标球放置在场景中，这三个定标球不共线且出现在每次测量的视野中，扫描完成后，将这三个定标球球心作为配准点，求解出变换矩阵，这样场景点云就能实现配准。自动配准指的是使用一些计算机和数学算法，结合物体内在的特征来快速计算两点云间的刚体变换，消除点云间的错位。而通常学者们研究的点云配准就指自动配准。自动配准的核心是将不同坐标系下的点云整合到统一坐标系中，配准技术的关键在于正确求解出刚体变换矩阵。1.3国内外研究现状自20世纪90年代开始，许多学者对点云配准的算法法进行了深入而广泛地[7][8]研究。Besel和McKay以及Chen和Medioni提出了ICP算法，为点云配准算法做了开创性工作，为后续配准算法的发展提供了理论基础和框架。ICP配准算法适应性广泛、配准精度高，因此成为迄今为止最基本、应用最广的点云配准方法。经过20多年的发展，出现了一些改进的迭代算法。[9]Zhang在算法中设立了动态阈值，用法向一致性来删除点间距和方向夹角超过阈值的点对，从而提高配准的准确性，同时，该算法采用k-D树来加快对应点[10]的搜索时间，从而提高算法的运行效率。Turk提出一致采样的方法从点云中选[11]取部分点参与配准过程，减少了算法运行时间，Masuda1996提出随机采样的[12]方法。Jost和Hugli提出多层次ICP算法，随着迭代次数增加而增多采样点数。[13]Sharp等提出了运用不变量特征来搜索对应点的算法，该特征可以是曲率、矩[11]不变量、动量矩等特征。ICP算法中的目标函数中用的是最小平方法，Masuda[8]提出用最小中值平均法来取代最小平方法。Chen用的是点到面的距离函数，而[7][14]Besl用的是点到点的距离函数，Mitra提出了一种能综合Chen和Besl的距离函数，其思想是当点间距较远时，该距离函数退化为点到点间距离，当点间距很小时，该距离函数退化为点到面间距离。[15]精确配准除了ICP配准还有其他一些方法。J.Holland提出了遗传算法，该算法借鉴自然选择理论，在迭代过程中，算法既能保持父代的优良基因，又能在[16]后代中加入变异因子。张学昌提出基于扩展高斯球的配准方法，可以解决配[17]准初始位置问题，但是该算法的精确度不高。Tsin和Kanade提出核心相关算法，该方法把点云表示成概率密度，通过设置两组点云的相似度来减小点云间距[18]离。Gold提出鲁棒点匹配算法，该方法使用退火算法来减小搜索时间。另外，5 第一章绪论[19]Ma和Ellis提出了U粒子滤波法，该方法使用大量的粒子来实现精确的配准。该算法计算复杂度很高，不适用于海量点云配准的场合。本文的研究采用的是应用最广泛的ICP配准法。[17]图1-4扩展高斯球示意图由于ICP算法对点云的初始位置要求很严格，所以在ICP配准前一般都会加上初始配准这一环节。对于本文研究来说，初始配准也是很重要的部分。Chung[20]和Lee提出主成分分析法，该算法的思路是根据点云构建三个特征矢量，并以三个矢量作为坐标轴，以点云重心作为原点来构建坐标系，根据两个点云的坐标[21]系来计算出旋转矩阵和平移矢量，从而进行初始配准；Chen提出了基于随机采样一致性的匹配算法，该算法在第一个待配准的点云数据中随机确定三个点，然后在另一个点云上搜索三点距离与前面三个点一致的三点作为可能对应点对，算法找出所有对应点对，计算出三维变换，将匹配最多的点对的变换作为最终的配准参数。还有一些基于特征的配准方法，其中高维特征有自旋图像（Spin[22][23][24][25]images）、点签名（Pointsignature）等，低维特征有曲率和积分不变量等，它们的思路都是利用物体的内在不变量特征来寻找三个对应点对。[20]图1-5主成分分析法示意图通过长期研究，国内的研究机构和高校在点云配准领域也做出了不错的成果。华中科技大学图像识别与人工智能实验室和北京大学的重离子物理研究所对6 第一章绪论这一问题做了很多研究，浙江大学、上海交通大学、天津大学、南京航空航天大学、大连理工大学、西北大学等其他学校在点云配准问题上做了深入的研究。1.4论文组织结构点云配准的两个应用领域是工件质量评估和模型拼接。本文以工件质量评估和模型拼接为例，研究了点云配准和拼接技术。因为基于特征的点云配准研究得到了广泛应用，所以本文的重点研究的是基于特征的点云配准，而且研究的是低维特征。本文前面部分研究的是零件的质量检测，根据实际零件情况，提出基于特征的点云配准算法，包括根据实际情确定使用哪种方式建立坐标系，接着选出含有平面、柱面特征的区域，用线性最小二乘法提取平面特征，用Levenberg-Marquardt非线性最小二乘法提取柱面特征，建立局部坐标系并进行初始配准；然后用改进的ICP算法进行精确配准；最后进行算法的精度测试，并用三坐标测量机测量两块零件，运用本文的配准算法得到实验结果。本文后面部分研究的是模型拼接技术，提出基于特征的点云拼接算法，为拼接算法提供了新的思路。先计算每个点的曲率值，设定合适的阈值来挑选出特征点集；构造一个相似度量来确定对应点对；用法矢约束来确定最优配准的三个点对，并由这三个点对求出旋转变换矩阵和平移矢量，完成初始配准；同样使用改进的ICP配准算法完成精确配准。设计实验验证了算法了可靠性。本文分为四章讨论了基于特征的点云配准与拼接技术的研究。第一章主要介绍本文的研究背景和意义，介绍了点云配准技术，研究了配准技术的国内外研究现状。第二章介绍了点云数据的分类和一些配准前的准备工作——点云的去噪和精简。第三章主要讨论基于特征的点云配准算法并用来做零件质量检测，详细介绍了算法的实现过程，算法的精度测试，用两个零件做实验得到结果。第四章提出了基于配准的拼接算法，介绍了算法的实现过程，并做了几组实验验证算法的可行性。第五章对本文两个方面的研究内容做了总结和展望。7 第二章点云数据预处理第二章点云数据预处理本章介绍介绍了点云数据的分类，并介绍了点云配准前的准备工作——点云的去噪和精简。2.1点云数据分类本文的研究对象为使用测量设备扫描实物模型后的三维点云，点云数据指的是对模型表面扫描得到的点集。任何物体只要采样点充足，就可将采集的点云作为代表来描述该物体的表面特征。点云数据的元素是空间的离散点，同时用点与点间的拓扑关系来表征模型的表面属性。不同的点云所包含的信息量不同，有些点云只包含物体空间位置信息，而有些点云包含点的大小、空间位置和法向量，其它一些点云包含物体表面的透明度、光照和纹理等信息。点云按照点的稀疏程度可以分为稀疏点云数据和密集点云数据。使用三坐标测量机得到的数据点与点的间距比较大，称为稀疏点云，而使用光学扫描仪得到的点云数量很大且点云很密集，称为密集点云。一般论文对密集点云的研究比较多，对稀疏点云研究比较少，本文的前面部分研究的是稀疏点云的配准，后面介绍的配准更适用于密集型点云。按照点的分布方式，点云又可以分为扫描线点云、多边形点云、网格化点云和散乱点云四类，散乱点云是本文的主要研究对象。2.2点云数据去噪在实际测量过程中，由于受到人为因素和其它随机因素的影响，在真实的点云数据中不可避免地会混入噪声点，为后面的点云配准增加了难度。所以在点云配准前，需进行去噪处理。对于不同的测量设备，噪声产生的缘由不同。对接触式测量设备如三坐标测量机而言，噪声主要由测量带来的随机误差和系统误差产生，受测量设备的灵敏度和测量人员的影响很大。对非接触式设备而言，噪声主要受物体本身的特性影响。在逆向工程中，经常采用光学扫描仪，它能一次性采集大量点云数据。在采集数据过程中，噪声产8 第二章点云数据预处理生的主要因素为被测物表面的纹波和粗糙度等反射特性、被测物的位置、被测物的颜色对比度、测量环境的光照条件以及测量系统的误差等。在2.1节中介绍过点云的分类，其中扫描线点云、多边形点云和网格化点云属于有序点云，可以使用卡尔曼滤波、最小二乘滤波、维纳滤波、邻域平均法、孤立点排异法等进行处理。目前常用的滤波算法为平均滤波、高斯滤波和中值滤波这三种。平均滤波的原理是选取邻域范围内点的平均值代替该点的值，滤波效果比较平均；高斯滤波的原理是是对某点邻域的点进行加权平均，它能在整体上保持原始模型的三维几何形貌特征；中值滤波的原理是取某点邻域的点的中值代替该点的值，它对偏离真实值较大的噪声点的剔除效果非常好，可以较好地消除毛刺。上面的滤波算法对于有序点云很有效，但对于无序点云就会显得无能为力，因为无序点云的点间的拓扑关系没有建立。对于散乱无序的点云，目前还没有通[27]用且有效的方法。近年来，有不少学者对该问题进行了研究。文献中提出最[28]大连通包围盒去噪法，文献提出了k-D树去噪法。虽然针对散乱点云有各种不同的去噪方法，但它们采用的是相同的思路：通过建立一定的数据结构使得点云内部具有一定的拓扑关系。可以使用欧式距离或K邻域这两种方法来构造点云数据的邻域。其中，欧式距离法是以采样点为球心，在一定半径范围球体内的点构成邻域。而K邻域构造法主要采用如下三种思路：1）八叉树法：八叉树为一种特殊结构的数据结构，它的每一节点都有八个子节点，正好可将三维点云划分到八个象限中，重复操作若干次，便可以把所有点都放入一个个小盒子中。2）空间单元格法：该方法与八叉树法类似，不同之处在于八叉树分割法的子空间大小可以自有定义，而空间单元格分割点云法是将空间划分为大小相同的小盒子。在三个坐标轴上平分坐标轴，空间被分为若干单元格，之后的点对搜索在单元格内进行，提高了搜索效率。3）k-D树法：k-D树是特殊的二叉树，它非常适用于空间中点的搜索，可以方便地查找对应点。[29]建立了点云间的拓扑结构后，就可以进行下一步的去噪处理了。文献提出基于k-D树的去噪算法，能够满足常规点云的去噪要求。在后面第三章中基于k-D树并使用欧式距离阈值和阈值的去噪方法可以提高ICP配准的准确度。2.3点云精简9 第二章点云数据预处理前面谈到点云可以分为稀疏点云和密集点云。稀疏点云一般来说点的数量不大，而密集点云点的数量可以达到上万甚至百万，其中很多点都是不必要的，如果不进行点云的精简，点云配准需要大量的空间和时间。第四章中研究对象主要是光学扫描法采集获取的密集点云，本节中讨论点云精简，为配准做准备，提高配准效率。点云精简需遵守一定的原则，应在被测物允许的误差范围内进行，对于特征很明显的地方应注意保留原始特征。[30]国内外很多学者对点云精简做了许多研究。Martin等提出了均匀网格法，但它不能有效地保留被测物的形状，在精简密集型点云时会产生栅格；曲率精简[31]法在减少点的数量的同时可以很好地保持原始模型的外形，但是算法需通过[32]邻域点来计算曲率，在点集数量庞大时要花费很大时间；Chen等提出根据法[33]向量进行精简，但对点云要求比较局限；Listen提出信息熵精简法，但该方法只是简单地将单个点的离散集合信息加权相加，而忽略了不同信息间的优先级[34]与联系；张丽艳提出按给定法向精度简化法，该方法能保持原始外形特征，[35][36]但算法效果依赖于近邻点个数，史保全提出聚类精简算法，但计算量不小。[37-39]还有一些保留边界法、粒子仿真法、包围盒法、随机采样法，保留边界法在点云有明显边界时效果较好；粒子仿真法能很好地控制采样结果，但速度较慢；包围盒法很可能丢失点云在密集处的细节。兼顾精度和效率，本文采用随机采样法进行点云精简。10 第三章基于特征的稀疏点云配准算法第三章基于特征的稀疏点云配准算法本章研究的是全局配准，模型质量评估为例，研究了点云配准的一个重要应用领域。本章中先介绍了本章基于特征的稀疏点云配准算法的提出思路，然后介绍了算法的详细步骤，最后进行算法的精度测试，并用三坐标测量机测量两块零件，运用本文的配准算法得到实验结果。3.1引言3.1.1几种常见几何特征的简介（1）点签名特征[23]点签名特征由Chua（2000）提出。如图3-1所示，对于点云的表面记为S，S上的任意一点p，以p点为球心半径r的球体与S的相交线记为C。根据点p和其邻域点可以拟合出该点的切平面M，C在且平面上的投影记为c。以p为坐标原点，其切平面的法矢n作为一个坐标轴，假设曲线c上离p最远点为Px,1点p到点Px确定坐标轴n，另一个坐标轴nnn，因而可以建立局域坐标系。2312然后以n为起点，按顺时针方向以某个固定角度对c上的点采样，则c上的点可2以用一个向量来表示，该向量值为曲线c上的点到p的距离。向量的维度由采样角度确定，若角度为20，向量维数为18。该向量便称作点签名特征。n1n1n2n2p20°40°S按一定角度等间隔采样曲线C曲线c[4]图3-1点签名特征示意图（2）自旋图像特征11 第三章基于特征的稀疏点云配准算法[22]A.Johnosn（1997）提出自旋图像（Spinimage）这一概念。自旋图像是一种局部表面算子，它根据空间中某一点和其邻域内的点构造二维图像来表征该点的三维几何特征。如图3-2所示，点云中有一点p，根据p的邻域点可以拟合出邻域法矢n和切平面S。p点附近有点Pi，可以计算出Pi到法矢n所在直线距离为，到切平面S距离为。可以创建一个表格，x轴代表的值，y轴代表的值，将表格离散化，每一个格子里存放的落在该区域的点的数量，并将该表归一化为图像，该图像成为自旋图。自旋图像描述了邻域点与目标点的相对位置关系，具有旋转平移不变量的特点。建立了模型和工件的自旋图像之后，按照一定的方法进行匹配，便可以找到特征对应点。PiβnαpS(a)自旋图像定义[22](b)自旋图像三维示意图图3-2自旋图像示意图（3）积分不变量特征12 第三章基于特征的稀疏点云配准算法[25]Manay2004第一次提出积分不变量的概念。与微分不变量相比，积分不变[40]量具有较好的抗噪性，对特征点有较强的识别能力。由于体积积分不变量比其它积分不变量有更好的特性，一般使用体积积分不变量来提取特征点。如图3-3假设三维模型的表面曲面为S，对于S上的任意一点p，以p点为球心，半径r可以做出一个球体Or(p)，则该球体与S相交部分的体积Vr(p)为：VP()gxdx()rOPr()S其中gx()为与模型相关的函数。pS图3-3积分不变量示意图（4）曲率特征[24]曲率是曲面的基本固有特征，不因物体的旋转平移而发生变化，因此很多学者使用曲率特征寻找对应点进行点云配准。过曲面S中某点p的法方向的平面成为法平面，法平面有无数多个，每一个法平面与曲面S形成一条交线，该交线在点p的曲率称作方向曲率。在无数个法向曲率中存在着最小主曲率K1和最大主曲率K2，以及平均曲率H和高斯曲率K。关于曲率特征，在本文第四章将会详细介绍。法向量主曲率方向法平面pS[5]图3-4曲率特征示意图13 第三章基于特征的稀疏点云配准算法（5）其他特征[41]Stamos提出使用直线特征来完成点云配准，在两个点云中提取出直线段特[42]征，通过匹配直线段求取刚体变换，实现配准。Chen改进了基于直线段特征的配准方法，但这类方法只能应用于类似于高楼建筑等存在明显的直线特征的场合。3.1.2基于特征的稀疏点云配准算法的提出思路在现代工业生产领域，零件的加工精度对产品的性能影响很大，尤其是汽车、飞机、火箭、飞船等由大量零件构成的精密系统对零件的精度要求非常高。近几[1-3]年来，用点云配准的方法来求取零件加工误差的做法开始流行起来。在1.1节中谈到点云数据的获取有接触式和非接触式两种，由于接触式测量精度高，本课题中采用三坐标测量机获取零件数据。在这种应用中，点云配准指的是将测量数据点云和零件模型点云进行比对以确定零件的加工误差，但是该测量数据的坐标系为三坐标测量机的坐标系，而零件模型的坐标系与之不同，需通过寻找三维变换使两组点云统一在同一坐标系下。使用三坐标测量机检测零件加工误差时，得到的数据为稀疏且不完整的点云，而且零件中有很多平面、柱面特征存在，上文中提到的配准方法都不适用。非基于特征的方法如PCA主成分分析法在点云稀疏不完整时，点云主轴方向不一致，方法失效；随机采样一致性的算法计算量很大，且在本课题研究情况中会出现局部最优；在基于特征的方法中，因为课题中所测点云数据中含有很多平面、柱面特征，自选图像、点签名特征、积分不变量、曲率等特征计算会失效，至于基于直线特征的方法，课题中所测点云数据不是完整的，不一定测量了零件的边线，所以也不适用。基于上述原因，本文转向研究该类点云的最明显的几何特征：平面和柱面特征，并利用这些特征来完成配准，获得零件的加工误差，提出基于特征的稀疏点云配准算法，主要思路是利用零件中的平面、柱面特征来建立局部坐标系，求解出旋转矩阵和平移矢量，完成初始配准，再使用ICP算法进行精确配准。3.2配准数学模型点云配准指的是对于不同坐标下的点云数据，称为模型点云和数据点云，求出刚体变换矩阵，使得作用在数据点云后，使得两个点云能完全重合。因而，点14 第三章基于特征的稀疏点云配准算法云配准在数学上可以描述为：已知两个点云P和Q，寻找两个点云的最优刚体变换，使得点云间的距离和最小，即：N2FRT,||QRPT||iii1最小，式中，Pi为数据点集，Qi为模型点集中的对应点，R为3×3旋转矩阵，T为3×1平移矢量，刚体变换有R和T共同构成。F(R,T)为数据点云经过刚体变换之后与模型点云之间的距离和。为降低问题的复杂性，一般将点云配准划分为两个步骤：一为初始配准或称作全局配准，使得两个点云大致重合在一起，为下一步作准备；二为精确配准或称作局部配准，通过迭代法得到最优刚体变换矩阵，实现最终结果。3.3基于特征的稀疏点云配准算法的步骤3.3.1特征提取零件中常见的特征为平面和柱面特征，本文分别两种情况详细讨论。（1）平面特征对于平面特征的拟合，一般采取最小二乘法拟合法。最小二乘法是一种数学优化技术，通过最小化误差的平方和来寻找数据的最佳参数。线性最小二乘法有三种变化形式：奇异值分解法、法方程法和特征向量估计法。对于平面点云数据{(,,),xyzi1,2...}n，假设其拟合平面方程为iiiaxbyczd0（3-1）可以用线性最小二乘法中的特征向量估计法来拟合平面方程的参数：平面拟合方程组为Ax0，其中x1y1z11xyz1A222，x(,,,)abcdT（3-2）xyz1nnnT矩阵()AA的特征值对应的特征向量为x(i1,2,3,4)，若绝对值最小，则iij[45]其对应的特征向量x为方程的最小二乘解。j为方便后续计算，方程单位化为abcdxyz0（3-3）mmmm其中15 第三章基于特征的稀疏点云配准算法222mabc故平面的单位法向量abcn{,,}（3-4）mmm（2）柱面特征如图3-5所示，对于圆柱面来说，它可以被看成是一个柱面上的点到中心轴[46]线为常数R的点的集合，由7个参数可以确定一个圆柱，它们是轴线向量[46]k{,,}abc和直线上某一点的坐标P0(x0,y0,z0)，以及圆柱的半径R，由文献得到拟合误差方程为vPPR-i2222(-xx)(-yy)(-)-[(-zzaxx)byy(-)czz(-)]-Ri0i0i0i0i0i0（3-5）Pi(xi,yi,zi)Rk={a,b,c}P0(x0,y0,z0)P图3-5圆柱面示意图本文采用非线性最小二乘法来求解。非线性方程组的求解通常有两种迭代方法，Levenberg-Marquardt和Gauss-Newton法。Gauss-Newton法很常用，但对初始近似要求很严格，若初始值选取不好，迭代将可能不收敛。Levenberg-Marquardt为Gauss-Newton法做了一些赶紧，引入阻尼因子，使迭代更加平稳，故其有时被称为阻尼最小二乘法。故本文采用Levenberg-Marquardt非线性最小二乘迭代[46]法来求解这7项参数，Levenberg-Marquardt算法的计算原理如下：目标：对函数关系yxf(),给定函数关系f()、待观测量y和估计量x。步骤1：给定初始点x0，终止控制常数ε，计算初始00=yxf()，λ0=0.01，参数ω=10,其中λ0和ω的值也可设定为其它值。T步骤2：当前运算次数记为k,计算雅克比矩阵Jk,计算NJJE，其kkkk中E为单位矩阵。16 第三章基于特征的稀疏点云配准算法T步骤3：构造增量方程Nδ=J，求出δ,kkkk（1）如果xf()xkδkk，则令xxk1kδk，若δk,就停止迭代，k输出结果；否则令k+1=，返回至步骤2。（2）如果xxf()kδkk则令kk+1=，返回至步骤2。T在本文拟合圆柱面的情形中，待观测量y(0,0,0,0,0,0,0)，估计量x为Tx=（abcxyzR,,,,,,），初始点x0可以根据如下方法给出：在零件中当孔与一000个平面垂直相交时，平面的法向量理论上与孔的轴向向量平行，用1.1节式（2）和式（3）便可得到该平面法向量，并将其作为(a,b,c)的初始值(af,bf,cf)，计算给定柱面的点云数据的重心作为(x0,y0,z0)的初始值(xf,yf,zf)，将重心到最近点的距离作为R的初始值Rf，这样初始点x0的参数都已给出。为了方便后续计算，经过Levenberg-Marquardt拟合得到的向量单位化为kkek3.3.2建立局部坐标系本文的思路是设法在数据点云P和模型点云Q上利用自身的特征向量建立两个局部直角坐标系O1-x1y1z1和O2-x2y2z2，根据这两个坐标系计算旋转平移矩阵，P和Q就可以配准在一起。本文以三种典型情况进行说明：(1)选择三个平面：如图3-6所示，若零件有三个平面，可以选择零件的三个平面S11、S12和S13，相交于点O1。用3.3.1节的原理分别拟合出平面的方程为S:0axbyczd（3-6）1111111111S:0axbyczd（3-7）1212121212S:0axbyczd（3-8）1313131313由上述方程得到三个平面的单位法向量分别为n{abc,,}，11111111n{abc,,}，n{abc,,}。联立上面三个方程，便可以求得三个平面交1212121213131313点O1的坐标。由于点云有一定误差，三个法向量不会严格正交，所以需对其进行适当处理：令17 第三章基于特征的稀疏点云配准算法Oxn=Oyn=Ozn=n（3-9）111，112，11112再令OyOz=Ox（3-10）111如图3-6所示，用O1和Ox、Oy和Oz便可以在点云P和Q中建立局部坐标111系Op1-Xp1Yp1Zp1和Oq1-Xq1Yq1Zq1。x1n11s11o1z1y1n13n12s13s12图3-6选择三个平面(2)选择两个平面和一个柱面：如图3-7所示，若零件有一个孔E2和两个平面S21和S22，孔与平面S21相交于O2。用3.3.1节中的原理拟合得到其轴线上的某一点Pz2(xe2,ye2,ze2)，轴向向量为k{a,b,c}则轴线所在的直线方程为e2e2e2e2xxyyzze2e2e2t（3-11）e2abce2e2e2选择平面S21拟合出其方程为S:0axbyczd（3-12）2121212121得到S21的法向量为n{abc,,}。联立式（3-11）和（3-12）便可以求得O221212121的坐标。选择平面S22拟合出其方程为S:0axbyczd（3-13）2222222222得到S22的法向量为n{a,bc,}。同第一种情形所述，用式（3-9）和（3-10）22222222的方法对n和n进行处理得到Ox、Oy和Oz。同样地，如图3-7所示，用2122222O2和Ox、Oy和Oz便可以在点云P和Q中建立局部坐标系Op2-Xp2Yp2Zp2和222Oq2-Xq2Yq2Zq2。18 第三章基于特征的稀疏点云配准算法x2z2sy21no2221n22Pz2E2Pz2s22ke2图3-7选择两个平面和一个柱面(3)选择一个平面和两个柱面：如图3-8所示，若零件有两个孔E31与E32和一个平面S3，孔与平面分别相交于O31和O32。选择平面S3拟合出其方程为Saxbyczd:0（3-14）33333得到S3的法向量为n{,,}abc。选择孔E31，用3.3.1节中的原理拟合得到其3333轴线上的某一点Pz31(xe31,ye31,ze31)，轴向向量为k{a,b,c}则轴线所在的e31e31e31e31直线方程为xxyyzze31e31e31t（3-15）e31abce31e31e31同理，选择孔E31，拟合得到其轴线上的某一点Pz32(xe32,ye32,ze32)，轴向向量为k{a,b,c}，则轴线所在的直线方程为e32e32e32e32xxyyzze32e32e32t（3-16）e32abce32e32e32联立式（3-14）和（3-15）便可以求得O31的坐标，联立式（3-14）和（3-16）便可以求得O32的坐标。OO3231由点O31和O32得到向量n。同第一种情形所述，用式（3-9）和（3-10）e3OO3231的方法对n和n处理得到Ox、Oy和Oz。同样地，如图3-8所示，用O31和Ox、3e33333Oy和Oz便可以在点云P和Q中建立局部坐标系Op3-Xp3Yp3Zp3和Oq3-Xq3Yq3Z33q3。对于其他含有平面、柱面特征的情形都可以采用这种类似的思路来处理。19 第三章基于特征的稀疏点云配准算法y3oone3s331o32n3z3Pz31Pz32ke31ke32图3-8选择一个平面和两个柱面3.3.3求解初配准变换矩阵假设由3.3.2节在点云P建立的局部坐标系的坐标轴矢量为e、e和e，pxpypz在Q建立的局部坐标系的坐标轴矢量为e、e和e。旋转矩阵R的计算式qxqyqz为-1TTR=eeeqxqyqzeeepxpypz（3-17）假设局部坐标系的原点分别为Op和Oq，则平移矢量T的计算式为TOROqp（3-18）使用旋转矩阵R和平移矢量T作用在数据点云P上，数据点云便会和模型点云大致配准在一起。但有时会出现坐标轴方向反向的情况，所以可以采用最小包围盒的思想来解决这一问题。本文的做法是可以计算两组点云在给定点间距阈值e下的最近点个数nc，当nc=e。3.3.4局部点云的选取由上文讨论的情况可知，要利用点云数据求取平面、柱面的特征参数，必须提前选定含有平面柱面特征的目标区域。已有的方法分为自动提取和手动提取法。自动提取是基于数据分块的方法，其可细分为基于边和基于面的这两种方法，[48]基于边的分块法，先在点云数据中找到边界点，如曲率突变点、法失突变点等，然后连接边界点，形成边界线，利用封闭线将点云数据分割为不同区域。基[49]于面的分块法，采用区域生长法，用不同类型的曲面拟合区域数据，并按照拟合误差大小确定曲面类型，其可以分为自上而下和自下而上两种方法。在本课[50]题研究背景下，两种方法都有缺点，基于边的分割法，对噪声数据很敏感，容易按错误的延伸方向跟踪，而且不能保证得到的边界线能够形成闭环，从而导20 第三章基于特征的稀疏点云配准算法致分割失败，而且在本课题背景下，因所给数据点云P为稀疏点云，难以得到准确的曲率法矢等特征信息；基于面的分块法中，自上而下的方法计算效率低，应用少，自下而上法同样因本课题研究的是稀疏点云而失效。既然自动提取方法效果不好，那么可以用人工手动提取的方法来选择目标区域。本文配准算法是在VC++平台上结合OpenGL图形库编程的，点云局部区域的选择也是基于OpenGL机制进行的。虽然OpenGL给对象拾取问题提供了一种[51]命中记录和名字堆栈的机制，但该机制是专门为三维图形设计的，对本文中研究的点云有很大限制，例如在拾取过程中，要对最小单位图元建立名字堆栈，当点云数量很大时，堆栈内存会溢出会导致失败。此外OpenGL的选择机制使用[52]时需在选择模式和正常模式间切换，使用不便。在实际选择局部区域时，本文采用的是OpenGL的进行两次绘制的方法。第一次绘制时，选择局部区域时，矩形框范围被记录下来，之后进行第二次绘制，当有点经过投影变换后处在框选范围时，该点被选中，该点的三维坐标由库函数[53]保存。这样的操作存在一个缺点：如图3-9所示，因位于物体前后表面的不同深度的点的二位投影坐标一致，前后面的点都会被选中。图3-9前后面的点都被选中要解决上述问题，可以采用遮挡算法剔除远端点，思路是设定一个深度阈值，若被选点深度大于中间点的深度，则会被剔除。本文编程方法将点的框选判断函数放在鼠标左键的响应函数中。框选判断函数先提取当前投影变换矩阵的参数，根据不同数据类型使用不同函数获得当前视口和变换矩阵。在使用OpenGL中对点进行投影的函数时，应保存点的坐标值、视口保存位置、当前变换矩阵和输出点三维坐标值，同时需要保存输出点的输出信息。因OpenGL的三维坐标系与Windows屏幕坐标系Y轴方向相反，需要进行转化操作：yhy（3-19）1021 第三章基于特征的稀疏点云配准算法其中，y1为屏幕坐标系的y轴坐标，y0为点OpneGL下经投影变换至二维坐标系下的y轴坐标，h为屏幕高度。遮挡算法局部选择效果如图3-10所示。图3-10遮挡算法剔除效果当然除了前后投影点重合问题，在选择时还会多余点存在，需要手动剔除，如图3-11所示。这样可以正确选中所需平面、柱面区域。图3-11删除多余点总结上述基于平面、柱面特征初始配准算法步骤如下：（1）根据实际工件确定使用上述三种情形的哪一种；（2）手动提取出平面或柱面点云。（3）按照1.3节所述方法在P和Q中建立局部坐标系；（4）求解坐标变换矩阵R和T；（5）根据所求R和T作用在P上得到P’；（6）测试P’和Q的重合点数nc是否大于e，满足条件就返回至步骤（7），不满足则返回至第（3）步，反转X轴或Y轴；（7）点云大致重合，初配准结束。基于特征的稀疏点云初始配准算法流程图3-12所示。22 第三章基于特征的稀疏点云配准算法根据实际情况确定方案手动选出平面或柱面点云点云P和Q中在建立局部坐标系求出变换矩阵R和平移矢量T，点云P的X轴或作用在P上得到P’Y轴反向判断P’和Q重合点数否是否达到阈值是初配准结束图3-12基于特征的稀疏点云初始配准算法流程图3.3.5基于特征的稀疏点云配准算法目前最常用的精确配准方法是ICP算法，ICP算法采用迭代最优思想，在每一次迭代中可以分为搜索对应点和求解刚体变换矩阵这两个问题。这两个问题互为输入。首先，当刚体变换矩阵已知时，求解两个点集P和Q的对应点集。当有距离和方程为2(,)PQmin(d(,pq)),i1,2,3......,j1,2,3......（3-20）ij时，使得(,)PQ最小的p和q就是所求。其次，当点集中的对应点对已知时，ij求使式（3-20）最小的刚体变换矩阵F(R,T)。但是ICP算法存在一定的问题，它要求P为Q的子集,或者P中任意一点的对应点集Q中离它最近的点，在这种条件下，可以求出变换矩阵，再作用到点集P，得到新点集，并用新点集和Q继续迭代执行上面的步骤，直至算法收敛或达到最大迭代次数。但实际中的P和Q不一定互为子集且可能相聚很远，导致算法不能实现全局最优，故需对ICP算法23 第三章基于特征的稀疏点云配准算法进行一些改进。本文前面所述的初始配准的目的是拉近点云P和Q之间的距离，为ICP配准提供好的初值。[54]为提高ICP算法的效率，本文结合文献提出的改进的ICP算法，提出基于特征的点云配准算法。改进的ICP算法的思路是使用k-D树查找最近点，提高最近点的查询速度，并使用欧式距离阈值和方向向量阈值来提高ICP算法的准确度。k-D树已在本文2.2节中做了介绍。实际配准过程中，会出现一些噪声点对，会对配准结果产生很大的影响，欧氏距离阈值的思路是是经过初始配准，数据点云和模型点云之间对应点对间的距离很小，否则视为噪声，对于数据点云P中模型点云Q，对P中的任意一点Pi，利用k-D树在Q中搜索最近的三个点，记为m1,m2,m3，计算Pi到这三个点之间的距离，若超过一定阈值th1，则查找失败，否则以Pi到三个点的垂足m0作为Pi的对应点。方向向量阈值的思想是，对应点对在不同坐标系下其法矢应该保持一致。经对应点对在不同坐标系下其法矢应该保持一致。所以可以对数据点集P中的某点Pi找到邻域点集{qj(,xvjj)}(1jK)，构造33矩阵CKTCj1(xjxi)(xjxi)（3-21）可以证明C的最小特征值所对应的特征向量可以看作是Pi法向量n的近似值。i同理可以计算某一可能对应点的法向量n。假设两向量的夹角为，夹角小于j阈值的点对予以保留。所以可以总结为：''（1）经过数据点云P中模型点云Q经过阈值判定后得到两对应点集P和Q，计算出对应点云的法向量ni和nj；（2）计算法向量ni和nj的夹角，大于阈值th2被剔除，否则予以保留。[54]总结文献的改进的ICP算法流程如下：（1）用k-D树法寻找点集P1如在模型点集Q中的最近点集,使用欧氏距离阈值法得到点集Q1；（2）对点集P1和Q1运用方向向量阈值法确定待运算点集Pi1和Qi1；[错误！未定义书签。]（3）应用奇异值分解法求解Pi1和Qi1之间的旋转矩阵R1和平移矢量T1；（4）计算PPii2RT111，即数据点集Pi1经过一次坐标变换后所得到的数据点集Pi2，然后重复(2)~(4)步骤，直到满足条件：24 第三章基于特征的稀疏点云配准算法dd'kk+11N2d||PQ（3-22）ik(1)ik(1)k1Ni1PPRTik(1)kik其中Rk和Tk为第k次迭代求得的旋转矩阵和平移矢量，Qi(k+1)为Pi(k+1)在Q中的最近点集，ε’为阈值，判断迭代是否收敛。输入点云P和Q初始配准使用k-D树和欧式距离阈值寻找近点集使用方向向量阈值确定对应点集使用奇异值分解法求解旋转矩阵R和平移矢量TPik经矩阵变换变为Pi(k+1)否dk-dk+1<ε’是配准结束图3-13基于特征的稀疏点云配准算法流程图25 第三章基于特征的稀疏点云配准算法本文结合基于特征的初始配准算法和改进的ICP算法，提出基于特征的稀疏点云配准算法，其流程如图3-13所示。3.4实验验证从国内外论文可以发现很多学者使用MATLAB和VisualC++作为ICP算法的测试平台。ICP算法中有很多矩阵运算，而矩阵是MATLAB软件的基本数据单元，此外，MATLAB的数学函数库、开发环境和图形处理系统都比较ICP配准。而VisualC++的开发环境比MATLAB有着更好的兼容性、可移植性和稳定性，且在工业中应用广泛，因此，我们选择VisualC++平台来实现ICP配准算法。3.4.1误差求取原理逆向工程中，根据输入数据类型不同，测量数据的误差求取有两个方案：（1）输入的模型和测量数据都是点云数据，这时问题转化为点集间距离的求取，模型点云与零件点云的误差为。该方案增加了获取零件点云过程中的1误差，减少了获取模型点云过程中的误差，而当使用高精度仪器测量时，上述两次测量误差的残差和为零，即0。则此时最终误差为。(1)11（2）输入数据中零件数据为点云，而模型为三角面片或曲面时，选用下面的方案。模型数据以STL文件格式为例，此时，最终误差变为点云相对于三角面片之间的误差，可以将其分解为零件点云与STL模型建的误差和模型点3云数据与STL模型间的误差。同样地，该方案增加了获取零件点云过程中4的误差，减少了获取模型点云过程中的误差，而当使用高精度仪器测量时，上述两次测量误差的残差和为零，即0。则此时最终误差为。(2)3434从上面的描述可知，配准是两个方案的一个必要步骤。零件和模型的数据处在不同的坐标系下，需要统一在一个坐标系下才能进行比对。逆向工程中所讨论的误差来源于六个方面：原型误差：工件的原型存在着与设计之间的误差，该误差记为。但是实际m应用中，模型一般是符合标准的，所以我们可以认为该误差很小，约等于零。测量误差：物体表面数据要用测量设备来采集，这个误差与测量精度有关。补偿误差：测量设备的接触部分需要进行误差补偿。26 第三章基于特征的稀疏点云配准算法数据处理误差：获得物体的三维数据后，需要进行一定的预处理，如第二章所述的进行去噪和精简操作，这样会引入数据处理误差。造型误差：在进行曲面重构时会引入这项误差。制造误差：根据模型加工零件时不可避免会引入该项误差，这也是本文重点研究的部分。在逆向工程中，需要先确定产品和设计模型的误差，判断其是否超过阈值，若是超过就得进行修正，直至小于阈值时才能大规模地生产。传统方法是测量一些关键数据点进行比对，这种方法自动化程度低，且会引入很多认为因素带来的误差，费时费力。上述方案的优势在于使用点云间的误差来代替工件与模型间的误差。虽然看上去引入了测量误差，实际上由于使用高精度的测量设备，测量误差可以忽略不计。点云配准的过程借助了计算机的处理，更加高效便捷。在查找工件点云上某一点在模型点云中的对应点时，一般使用欧氏距离最近点作为对应点，但这只是能在模型点云上找到的距离最近的点，不一定为真实的对应点，因此本文使用点到近邻域所拟合的平面的距离作为该点的加工误差：如图3-14所示对于点集P中的任意一点Pi，在Q中搜寻与欧式距离最近的三个点，用这三个点构造一个平面，然后用Pi到该平面的距离ei作为该点的加工误差。Piei图3-14误差计算示意图3.4.2误差的显示方案本文在VC++平台结合OpenGL图形库实现误差显示。OpenGL是一个跨编程语言和跨平台的专业图形程序接口，是一个调用方便、功能强大的底层图形库。在计算了零件上的每一个点的误差后，需要将其显示出来。一般可以使用表格或文本将每一个点的误差给出，但效果不直观。为直观看出每一个点的误差情况，27 第三章基于特征的稀疏点云配准算法可以使用RGB三种色彩模式来使误差可视化，该模式使用红绿蓝三种颜色的组合来显示各种颜色。光栅显示器屏幕可以看成是由像素构成点阵，每个像素可以发出不同颜色的光。所有像素的颜色值存放在帧缓冲区中，该缓冲区可看作一个二维数组，数组的每个元素和屏幕像素一一对应。在OpenGL中红绿蓝三色用八个位表示，每一个位分别存放在一个位平面中。帧缓冲区由这些平面组成。从三组位平面中取出八位的颜色索引值，并分别装入三个索引寄存器中，在索引地址中查找相应的颜色值。这些颜色值以数字信号表示的，必须转换为模拟信号，最后输入到电子枪中产生三束阴极射线，将色彩显示到屏幕上。在该显示模式中，纯红色为（255,0,0），纯绿色为（0,255,0）。本文的误差显示思路是，误差每多一单位，红色通道加一个单位，绿色通道减一个单位。因此颜色更红表示误差更大，颜色更绿表示误差更小。本文在VC++平台结合OpenGL图形库实现误差显示，误差为零时为纯绿色，最大误差对应纯红色，每个点的误差值和最大误差值的比值与其显示的颜色对应。误差求取和显示的步骤总结如下：''（1）使用本文的算法进行配准后，得到点云P和P；12''（2）对点集P中的任意点p在P中找寻最近三个点，用三个点构造平面，计算12点p到平面的距离，把该距离作为该点处的误差值。（3）求出所有点的误差后，找出最大值，将每点的误差值和最大值比较得到比例，用该比例来做颜色显示，比例为1即为纯红色代表误差最大，比例为0即为纯绿色表示误差为零。这种显示方案可以直观看出零件产品与模型之间误差的分布情况。3.4.3算法配准精度测试算法的配准精度则用两组点云的距离即所有点误差的平均值来表示iN1de=i。为了检验本文的算法的有效性，先进行精度测试，再对三坐标测量Ni1机测量零件得到实验数据，再用上文的算法得到检测结果。为了测试本文算法的精度，如图3-15、图3-16和图3-17所示,根据3.3.2节的三种情形设计三组零件模型A、B和C，并对模型点云进行旋转平移得到数28 第三章基于特征的稀疏点云配准算法据点云。对零件A，使用手动选择法分别在模型点云和数据点云中挑选出平面1、平面2和平面3，进行平面特征提取，建立局部坐标系，求解旋转变换矩阵和平移矢量进行初始配准，然后使用改进的ICP配准法进行精确配准；对于零件B，使用手动选择法分别在模型点云和数据点云中挑选出平面1、平面2和孔，进行平面和柱面特征提取，建立局部坐标系，进行初始配准和精确配准;同样地，对于零件C，使用手动选择法分别在模型点云和数据点云中挑选出孔1、孔2和平面，进行平面和柱面特征提取，建立局部坐标系，进行初始配准和精确配准；每个零件进行8组重复性实验，并使用不同间距的点云，算法配准精度的测试结果如表1所示。由表1可知，对于3.3.2节所述的常见的三种类型的零件，本文算法的配准精度都能保证在1μm之内；对于模型点云中点间距的选择，因点间距越小，点云数据越多，算法所需时间越长，一般选择1mm间距即可满足测量需要。平面1平面1模型点云数据点云平面2平面2平面3平面3平面2平面3平面1图3-15用于精度测试的零件A的模型点云和数据点云29 第三章基于特征的稀疏点云配准算法模型点云平面2数据点云孔平面2平面1孔平面1孔平面2平面1图3-16用于精度测试的零件B的模型点云和数据点云模型点云孔1孔1平面数据点云孔2孔2平面孔1平面孔2图3-17用于精度测试的零件C的模型点云和数据点云30 第三章基于特征的稀疏点云配准算法表1三种零件不同间距配准精度测试结果点云间距A（um）B（um）C（um）(mm)0.20.00.50.20.50.00.60.310.00.30.21.50.00.30.220.00.20.23.4.4零件配准实验如图3-18所示为本实验使用海克斯康公司所生产的三坐标测量机。1号零件3如图3-19（a）所示，外形尺寸为42×20×20mm，2号零件如图3-20（a）所示，3外形尺寸为42×20×20mm。三坐标测量机的测量精度计算公式为：2.3+3.3L/1000μm，在本文中，L为零件的最大外形尺寸，经过计算，测量机对1号零件的测量精度为2.4μm，2号为2.7μm。对于1号零件，其模型点云和数据点云如图3-19（b）所示，模型点间距为1mm，为方便计算，模型点云的斜面做成了完整的平面。对于1号零件进行配准实验，使用的三个平面如图3-19（a）的标注所示，在图3-19（b）中的模型点云和数据点云中分别选出这三个平面，进行特征提取，然后建立局部坐标系求出旋转矩阵和平移矢量，进行初始配准和精确配准，结果如图图3-19（c）所示，带色彩的误差显示图如图3-19（d）所示，图3-19（e）为每个点的误差分布图。经本文配准算法计算，1号零件的加工最大误差为313.4μm,最小误差为1.6μm，平均误差为154.9μm，均方差为158.3μm。31 第三章基于特征的稀疏点云配准算法图3-18三坐标测量机平面1平面2平面3(a)1号零件32 第三章基于特征的稀疏点云配准算法平面1平面3平面2模型点云数据点云平面1平面2平面3(b)配准前平面1平面2平面3(c)配准后平面1平面1平面2平面3(d)配准后带色彩显示的误差33 第三章基于特征的稀疏点云配准算法1号零件0.350.30.250.2mm0.150.10.050050100150200250300350400450点(e)零件误差分布图图3-191号零件实际配准2号零件如图3-20（a）所示，其模型点云和数据点云如图3-20（b）所示，模型点间距为1mm。因实验中只需两个孔，所以模型点云中只设计了两个孔。在本次实验中使用的两个孔和一个平面如图3-20（a）的标注所示，在图3-20(b)中的模型点云和数据点云中分别选出这两个孔和一个平面，进行特征提取，然后建立局部坐标系求出旋转矩阵和平移矢量，进行初始配准和精确配准，结果如图3-20（c）所示，带色彩的误差显示图如图3-20（d）所示，图3-20（e）为每个点的误差分布图。经本文配准算法计算，零件的加工最大误差为971.1μm,最小误差为0.0μm，平均误差为22.4μm，均方差为26.3μm。根据3.4.4节的分析，上述结果精度在1μm之内。孔1孔2平面(a)2号零件34 第三章基于特征的稀疏点云配准算法孔2数据点云孔1平面模型点云孔2孔1平面(b)配准前孔1孔2平面(c)配准后孔1孔2平面(d)配准后带色彩显示的误差35 第三章基于特征的稀疏点云配准算法2号零件10.80.6mm0.40.20050100150200250300350点(e)零件误差分布图图3-202号零件实际配准3.5本章小结本章研究的是点云配准的一个重要的应用领域——质量评估，针对实际零件加工质量的检测，提出了基于特征的配准算法，其主要分为初始配准和精确配准。初始配准根据实际情况确定使用哪种方式建立坐标系，接着选出含有平面、柱面特征的区域，用线性最小二乘法提取平面特征，用Levenberg-Marquardt非线性最小二乘法提取柱面特征，建立局部坐标系并进行初始配准；精确配准使用改进的ICP算法，使用k-D树寻找最近点对，使用欧式距离阈值和方向向量阈值剔除无效点对，再用ICP算法迭代直至最后配准结束，即可算出零件的加工误差。36 第四章基于特征的点云拼接技术第四章基于特征的点云拼接技术本章研究的是点云配准的第二个重要的应用——模型拼接。在物体形貌重构时，一般使用光学扫描仪得到三维数据。而由于光的线性传播特性，三维扫描仪在一个视角下只能得到物体的一部分表面数据，要想得到物体的完整信息，就必须在多个视角下进行扫描，然后将多次扫描的数据拼接起来，统一到同一个坐标系下。本章中使用基于特征的点云拼接算法解决这一问题。本章先介绍提出算法的思路，然后详细介绍了算法的原理步骤，最后进行了实验验证。4.1引言本文3.1.1节中简略介绍了曲率特征，由几何学知识可知，曲率是曲面上某一点的固有特征，不因物体处在哪个坐标系下而发生变化，这里的曲率包括主曲率、高斯曲率和平均曲率。在不同视野下采集的点云数据坐标系不同，且在不同视野下的公共部分数据点的坐标值也不同，但公共区域的数据点云曲率值不变，因而可以将曲率值作为点对匹配的根据。近年来，一些学者对基于曲率特征的配准算法进行了研究。朱延娟提出先计算每个点的曲率值，构造匹配点对，计算每个点对的三维变换，用几何哈希法找[37]出最优变换。戴静兰在使用主成分分析法后，使用曲率特征点寻找对应点，[52]减少了ICP配准的工作量；王蕊提出使用曲率特征搜索曲率极值点集，构造[55]相似度量，剔除无效点对，实现配准；薛耀红等提出的基于曲率特征的配准[56]方法与王蕊相似，引入距离和超线段约束，完成点云配准；马忠玲等提出的方法是先提取局部曲率变换最大的特征点，用Hausdorff距离来提取匹配点对，最后用粒子群优化算法删选出最佳匹配点对。本文在现有研究基础上，新的基于曲率特征的配准方法，思路是：对于自由曲面而言，在曲面光滑部分曲率值小，在突变部分，曲率值大，所以设定阈值挑选出特征点集，与其他学者提出的方法相比，可以减少匹配点对的数量，提高效率。然后可以以曲率特征为依据计算两个点集的相似度，找到可能匹配点对，用三点对求解坐标变换，将数据点云变换到模型点云的坐标系下，以法矢夹角作为判定标准剔除无效变换，找到最佳三个点对，该点对对应的刚体变换为最优变换，数据点云在该变换下与目标点云正确拼接起来。37 第四章基于特征的点云拼接技术4.2基于特征的点云拼接算法步骤4.2.1曲率计算[7]很多文献讨论了曲率计算方法，如Besl在文献中做了详细研究，将三维空间内曲率的计算方法总结为五种：TW（TurtleWalking）法、交叉曲面法、曲面[7]三角化法、正交步进法和坐标转换法。许多学者都使用坐标变换法计算点云的[57,58,60]曲率特性。坐标变换法的思路是对点云中的某点进行局部坐标系拟合得到抛物面方程，然后根据该方程的系数得到四个曲率值。计算流程参见下图4-1计算点的k邻域计算点的法矢并作修正建立邻域坐标系并进行坐标转换对邻域数据进行抛物面拟合计算点的曲率图4-1曲率计算流程图4.2.1.1计算数据点的k邻域待计算数据点p的k邻域指的是在点云数据中搜索到与之最近的k个点。如果直接欧式距离搜索，那么将会需要花费很多时间，本章中使用2.3.1节中使用的k-D树搜索算法。待求点p的邻域记为Nb(p)。搜索过程如下，先建好k-D树，搜索k-D树内所有节点，在点集中搜索离p点最近的节点B，在节点B存储的点集中寻找距离点p最近的k个点，这里的k值可以任意选取，一般选10-20，本文中选14。38 第四章基于特征的点云拼接技术4.2.1.2计算数据点的法矢及修正点云中某点的法矢是通过它的邻域来确定的。法矢计算一般有两种思路，一是三角网格法，先建立点云数据的三角网格模型，再通过点的三角形法矢加权平均来计算法矢；二是微切平面法，确定某点的k邻域后，采用最小二乘法来拟合平面，该平面的法矢可以近似为待求点的法矢。前者计算量大，所以采用后面一种方法，但是这种方法的缺陷是计算出的法矢有两个方向，所以要加以统一调整。Nb(p)内的k个点记为{(,,),xyzi1,2...}n，假设其拟合平面方程为iiiaxbyczd0（4-1）可以用线性最小二乘法中的特征向量估计法来拟合平面方程的参数：平面拟合方程组为Ax0，其中x1y1z11xyz1A222，x(,,,)abcdT（4-2）xyz1nnnT求得矩阵()AA的特征值λi和特征向量xi(i1,2,3,4)，绝对值最小的λj对应的特征向量x即是待求平面参数的最小二乘解。参数a,b,c单位化后便可以得到P的j邻域Nb(p)的法矢。[59]计算得到的法矢需要做一些调整，一般论文中采用法矢传播法，本文采用另一种方法，以简化计算。如图4-2所示，假设点云中有点Pxyz{,,},经过拟合得到该点的法矢为iiiin{,nnnab,}c，该点云的重心为Pxyzo{,oo,}o,则Po指向Pi得到向量n{xxy,yz,z}，需要将所有的n都调整到与n方向一致，方法是：pioioiop计算n与n的点积mnn，当m>=0时，法矢n保持不变，当m<=0时，ppn{n,n,n}。对所有的点都进行上述处理，便完成了法矢的调整。abc39 第四章基于特征的点云拼接技术nPinpPo图4-2法矢调整示意图4.2.1.3建立邻域坐标系并进行坐标变换如图4-3所示建立邻域坐标系，点p在原始坐标系O-xyz中的坐标值为(xyz,,)，在其邻域中，可以以点p为原点，以在上一节中所求的法矢n为hppp轴，u、v为与h相互正交垂直的轴，建立邻域坐标系。p的邻域点Pxyz{,,}在iiii局部坐标系中的坐标为{,,}uvh，得到了在邻域坐标系下的坐标值，就可以为下iii一步拟合抛物面做准备。hnpuzvoyx图4-3邻域坐标系示意图[60]由文献提供的思路，设p点在坐标系O-xyz中的单位法矢为(,xyz,)，p’000点为在xy平面内的投影点pxy'(,,0)，p先平移至p’点，再绕z轴旋转一定角00度，最后绕x轴旋转一定角度，即可变换到新的坐标系中，本文下面的分析就是计算出旋转矩阵Rz和Rx，由于在不同象限中情况不一样，所以需要一一分析。（1）当p点在第一象限即x0>0,y0>0,z0>0时，法矢绕z轴先转β到zy平面，令22y0x0Mxy，cos，sin，则绕z轴的旋转矩阵为00MM40 第四章基于特征的点云拼接技术cossin00sincos00R（4-3）z00100001Op经过旋转后在zy平面内变为Op’，其长度不变222Op'xyzL（4-4）000zM0假设其与z轴夹角为θ，则cos，sin，Op’绕x轴经过旋转后与z轴LL重合，其旋转矩阵为：10000cossin0R（4-5）x0sincos0000122（2）当x0<0,y0>0,z0>0时，法矢绕z轴先转β到zy平面，令Mxy，00yx00cos，sin，则绕z轴的旋转矩阵为MMcossin00sincos00R（4-6）z00100001Op经过旋转后在zy平面内变为Op’，其长度不变，计算式同式（4-4）。zM0假设其与z轴夹角为θ，则cos，sin，Op’绕x轴经过旋转后与z轴LL重合，其旋转矩阵同式（4-5）。22（3）当x0>0,y0>0,z0<0时，法矢绕z轴先转β到zy平面，令Mxy，00yx00cos，sin，则绕z轴的旋转矩阵为MMcossin00sincos00R（4-7）z00100001Op经过旋转后在zy平面内变为Op’，其长度不变其长度不变，计算式同式（4-4）。zM0假设其与z轴夹角为θ，则cos，sin，Op’绕x轴经过旋转后与zLL轴重合，其旋转矩阵为：41 第四章基于特征的点云拼接技术10000cossin0R（4-8）x0sincos0000122（4）当x0<0,y0>0,z0<0时，法矢绕z轴先转β到zy平面，令Mxy，00yx00cos，sin，则绕z轴的旋转矩阵为MMcossin00sincos00R（4-9）z00100001Op经过旋转后在zy平面内变为Op’，其长度不变，计算式同式（4-4）。zM0假设其与z轴夹角为θ，则cos，sin，Op’绕x轴经过旋转后与zLL轴重合，其旋转矩阵同式（4-8）。22（5）当x0>0,y0<0,z0>0时，法矢绕z轴先转β到zy平面，令Mxy，00yx00cos，sin，则绕z轴的旋转矩阵为MMcossin00sincos00R（4-10）z00100001Op经过旋转后在zy平面内变为Op’，其长度不变，计算式同式（4-4）。zM0假设其与z轴夹角为θ，则cos，sin，Op’绕x轴经过旋转后与zLL轴重合，其旋转矩阵为：10000cossin0R（4-11）x0sincos0000122（6）当x0<0,y0<0,z0>0时，法矢绕z轴先转β到zy平面，令Mxy，00yx00cos，sin，则绕z轴的旋转矩阵为MM42 第四章基于特征的点云拼接技术cossin00sincos00R（4-12）z00100001Op经过旋转后在zy平面内变为Op’，其长度不变，计算式同式（4-4）。zM0假设其与z轴夹角为θ，则cos，sin，Op’绕x轴经过旋转后与zLL轴重合，其旋转矩阵同式（4-11）。22（7）当x0>0,y0<0,z0<0时，法矢绕z轴先转β到zy平面，令Mxy，00yx00cos，sin，则绕z轴的旋转矩阵为MMcossin00sincos00R（4-13）z00100001Op经过旋转后在zy平面内变为Op’，其长度不变，计算式同式（4-4）。zM0假设其与z轴夹角为θ，则cos，sin，Op’绕x轴经过旋转后与zLL轴重合，其旋转矩阵为：10000cossin0R（4-14）x0sincos0000122（8）当x0<0,y0<0,z0<0时，法矢绕z轴先转β到zy平面，令Mxy，00yx00cos，sin，则绕z轴的旋转矩阵为MMcossin00sincos00R（4-15）z00100001Op经过旋转后在zy平面内变为Op’，其长度不变，计算式同式（4-4）。zM0假设其与z轴夹角为θ，则cos，sin，Op’绕x轴经过旋转后与zLL轴重合，其旋转矩阵同式（4-14）。平移矩阵T为43 第四章基于特征的点云拼接技术10000100T（4-16）0010xyz1ppp从原始坐标系到局部坐标系的变换矩阵为：W=TRR（4-17）zx对于p的邻域Nb(p)的一点Pxyz{,,}，在局部坐标系下的坐标为Puvh'{,,}，iiiiiiiixixi'yy'令Pi，P'i，则有zz'ii11TTP=PW（4-18）i因而我们得到了p的近邻域中点在局部坐标系中的坐标值。4.2.1.4抛物面拟合由上所述，点p的邻域点集{(,,),xyzi1,2...}k由原始坐标系O-xyz转换到iii局部坐标系p-uvh下的新坐标为{(,,),uvhi1,2...}k。对转换后的点进行局部抛iii22物面拟合，设待拟合的抛物面方程为Suv(,)aubuvcvduevh，将数据点{(,,),uvhi1,2...}k带入该方程得到线性方程组可以解出方程的五个系数iii[50]a,b,c,d,e。设该线性方程组为：AX=B其中，22u1uv11v1u1v1h122uuvvuvhA222222，X(,,,,)abcdeT，B2（4-19）..................22ukuvkkvkukvkhk解方程组可以使用奇异值分解法。4.2.1.5计算曲率解出方程组的五个参数后可以得到点p的曲率：2LNMEN2FMGL高斯曲率：K，平均曲率：H，22EGF2(EGF)222最小主曲率：KHHKac()acb，144 第四章基于特征的点云拼接技术222最大主曲率：KHHKac()acb2其中：2Ed1Fde2Ge122Qde1（4-20）2aLQbMQ2cNQ4.2.2提取特征点在自由曲面中，物体表面有平坦区域，也有一些过渡区域，而过渡区域的曲率一般来说比平坦区域大，所以可以以这种思路来提取特征点，具体步骤如下：（1）计算点云中所有点的曲率，{(,kHkk,,),i1,2...}N；ii12ii（2）以平均曲率，计算所有点的平均曲率的平均值和标准差，N1平均曲率平均值：kkiNi1N12平均曲率()kkiNi1（3）设定阈值k，将所有点的曲率大于的视作特征点，特征点构成特征点集合。4.2.3找对应点对[61]文献中将所有点都视为配准点，在一定程度上提高了配准精度，但同时大大增加了配准所需时间。配准的必要条件是找到正确的对应点对，本文的思路是构造一个相似性度量，在数据点集和模型点集中找到对应点对。因本文使用曲率特征，所以可以以四个曲率特性来构造相似性度量。设经过3.2节筛选后的模型点集的四个曲率为{(smksmH,,,smksmk),i1,2...}M，数据点集的四个曲ii12ii45 第四章基于特征的点云拼接技术率为{(sdksdH,,,sdksdk),j1,2...}N，则模型点集中的任意一点Q和数据jj12jji点集中的任意一点P的相似度S(i,j)定义为:j1Sij(,)Dij(,)（4-21）2222Dij(,)(smkisdkj)(smHisdHj)(smk1isdk1j)(smk2isdk2j)按照上式计算所有可能点对之间的相似度S，设定一个阈值T，当S>T时，说明该点对曲率很相近，是可能的对应点对，添加到点集Smodel和Sdata中，否则予以剔除。4.2.4找最优变换三点对本文的配准使用的是三个对应点对，由三个对应点对计算变换矩阵。在使用相似度量剔除非对应点对后，有模型点集Q1和数据点集P1，它们的点数量是一样的。可以使用投票法则来寻找最优三个对应点。具体思路是：（1）如图4-4所示，在模型点集中选择三个点，并在数据点集中选择与之下标一致的点，记为Qa,Qb,Qc和Pa,Pb,Pc，根据这三个对应点对，求出变换矩阵和平移矢量，由Qa、Qb和Qc构成一个平面，并拟合出该平面法矢量记为n，所用方法与本文3.3.1qx节中拟合平面特征一样。该三点确定一个三角形，三角形重心为Qo,则由Qo指向Qa可以确定矢量n，于是利用向量叉乘可以得到nnn，对三个矢量进qyqzqxqy行单位化处理，以Qo为坐标原点可以建立局部坐标系；同理可以Pa,Pb和Pc成一个平面，并拟合出该平面法矢量记为n，该三点确定一个三角形，三角形重px心为Qo,则由Qo指向Qa可以确定矢量n，于是利用向量叉乘可以得到pynnn，对三个矢量进行单位化处理，以Po为坐标原点可以建立局部坐pzpxpy标系。局部坐标系的坐标轴矢量为e、e和e，在Q建立的局部坐标系的坐pxpypz标轴矢量为e、e和e，旋转矩阵R的计算式为：qxqyqz-1TTR=eeeeee（4-22）qxqyqzpxpypz46 第四章基于特征的点云拼接技术QcnqxPbnqznpxQPonQaoqynpyPoQoPanpzQPcb图4-4局部坐标系示意图记局部坐标系的原点分别为Op和Oq，则平移矢量T的计算式为TORO（4-23）qp经过旋转和平移之后，数据点云和模型点云配准到一个坐标系中。所以可以对数据点集P中的某点Pi找到在P中的邻域点集{qj(,xvjj)}(1jK)，构造33矩阵CKTCj1(xjxi)(xjxi)（4-24）可以证明C的最小特征值所对应的特征向量可以看作是Pi法向量n的近似i值。同理可以计算某一可能对应点的法向量nj。用这种思路可以计算出Qa,Qb,Qc的法矢量nqa、nqb和nqc和Pa,Pb,Pc经过变换之后的法矢量npa、npb和npc。计算出三个对应矢量之间的夹角、和，算出夹角之和S。每一次计算之后abc都会得到夹角之和S，按照大小排序，找到的最小的S所对应的就是最佳三点对，所对应的变换为最优变换，在最优变换矩阵作用下，数据点云和模型点云可以初步配准起来。4.2.5改进的基于特征的拼接算法根据本文第二节的分析，类似地，上面的步骤可以看作是初步配准。总结上面算法，假设经过初始配准之后的数据点集和模型点集分别为P1和Q，则改进的ICP算法可以表示为以下步骤：（1）用k-D树法寻找点集P1在模型点集Q中的最近点集,使用欧氏距离阈值法得到点集Q1；（2）对点集P1和Q1运用方向向量阈值法确定待运算点集Pk1和Qk1；47 第四章基于特征的点云拼接技术（3）应用奇异值分解法求解Pi1和Qi1之间的旋转矩阵R1和平移矢量T1；（4）计算PPRT，即数据点集P经过一次坐标变换后所得到的数据点集kk2111k1P，然后重复(2)~(4)步骤，直到满足条件：k2dd'kk+11N2d||PQ（4-25）ik(1)ik(1)k1Ni1PPRTik(1)kik其中Rk和Tk为第k次迭代求得的旋转矩阵和平移矢量，Q(ik+1)为P(ik+1)在Q中的最近点集，ε’为阈值，判断迭代是否收敛。其流程如图4-5所示。输入点云P和Q计算所有点的曲率值找出特征点集用相似度量来确定对应点对用法矢约束来寻找最佳变换矩阵用所求变换矩阵作用在点云P上完成初始配准改进的ICP配准配准完成图4-5改进的ICP算法流程图48 第四章基于特征的点云拼接技术4.3实验验证本文用马、牛和猫的点云做了拼接实验，先使用马模型进行点云配准实验，配准前模型的左大半部分P和右大半部分Q，如图4-6(a)所示，计算了点云的曲率值之后，挑选出特征点集如图4-6(b)中绿色所示，再用相似度量来确定对应点对，用法矢量约束来找出最终的三个点对，如图4-56(c)所示，由三个点对求解出旋转矩阵和平移矢量，对P进行变换，最终配准完成，如图4-6(d)所示。图4-6(e)为拼接的重合点处每一个点的的配准误差的分布图。（a）拼接前（b）找特征点集（绿色点）49 第四章基于特征的点云拼接技术（c）找最优3点对（绿色点）（d）拼接后马0.350.30.250.2um0.150.10.050020040060080010001200（e）拼接误差分布图4-6马点云拼接过程示意图之后对牛模型点云进行了配准实验，如图4-7所示。50 第四章基于特征的点云拼接技术（a）拼接前（图中为牛的左大半部分和右大半部分）（b）找特征点集（绿色点）（c）找最优3点对（绿色点）51 第四章基于特征的点云拼接技术（d）拼接后-3牛x10432um10020040060080010001200140016001800（e）拼接误差分布在图（b）中挑选出特征点，使用相似度量来确定对应点对，使用法矢约束来选出最优点对得到旋转矩阵和平移矢量，进行初配准和精确配准。图4-7牛点云拼接过程示意图对猫的模型的点云进行了配准实验，如图4-8所示。52 第四章基于特征的点云拼接技术（a）拼接前（图中为猫的左大半部分和右大半部分）（b）找特征点集（绿色点）（c）找最优3点对（绿色点）53 第四章基于特征的点云拼接技术（d）拼接后-3猫x1021.51um0.5005001000150020002500300035004000（e）拼接误差分布在图（b）中挑选出特征点，使用相似度量来确定对应点对，使用法矢约束来选出最优点对得到旋转矩阵和平移矢量，进行初配准和精确配准。图4-8猫点云拼接过程表4-1算法误差性能表模型重合点数最小误差(μm)最大误差(μm)平均误差(μm)马10250.0000.3180.131牛16680.0000.0040.001猫39220.0000.0020.00154 第四章基于特征的点云拼接技术表4-1为实验的误差性能表，实验结果为3组实验的平均值。由该表可知，本章提出的算法的配准误差小于1μm，满足实际需求。4.4本章小结本章详细介绍了点云配准领域中的点云拼接这一重要应用。扫描仪从不同视野下的到了多组数据，这里简化为两个点集——模型点云和数据点云。提出了基于特征的点云拼接算法，算法分为两个步骤：（1）初始配准：计算所有点的四个曲率值，用一定阈值挑选出过渡区域的特征点，之后计算两个点集所有点的相似度，找到曲率相似点，最后用投票法则，计算三个点对变换后的法矢夹角之和，选出最小值即为最优点对，对应的刚体变换为最优变换，在该变换作用下，两个点云大致拼接在一起；（2）精确配准：与第二章所述类似，使用k-D树寻找最近点对，使用欧式距离阈值和方向向量阈值剔除无效点对，再用ICP算法迭代直至最后配准结束，点云拼接完成。设计了三组实验，介绍了拼接过程，验证了本文算法配准精度的可靠性。55 第五章总结与展望第五章总结与展望5.1全文总结点云配准是逆向工程中的关键步骤，点云配准的两个应用领域是工件质量评估和模型拼接。本文以工件质量评估为例，提出基于特征的稀疏点云配准算法；以模型拼接为例，提出了基于特征的点云拼接算法。本文的主要工作如下：（1）针对模型质量评估，提出了基于特征的稀疏点云配准算法。使用人机交互方式选出点云局部区域；用最小二乘法进行平面特征提取，用Levenberg-Marquardt非线性最小二乘法进行柱面特征提取；提出通过平面、柱面特征建立局部坐标系求解刚体变换实现初始配准；再使用改进的ICP进行精确配准；测试了算法的配准精度，标准算法精度满足实际需求；使用本文的配准算法对两个零件进行实验，得到了零件的加工误差。（2）点云配准领域对稀疏点云的研究比较少，本文提出的基于特征的稀疏点云配准算法提供了一点新的思路。（3）针对模型拼接，提出了基于特征的点云拼接算法。通过查找点的近邻域求出点法矢，在该点建立邻域坐标系，将原始坐标都转换到局部坐标系下，再进行邻域抛物面拟合，计算出每个点的曲率；设定合适的曲率阈值挑选出特征点集；构造曲率相似度来确定对应点对；再用法矢约束来确定最佳点对，求出刚体变换，完成初始配准；最后同样使用改进的ICP进行精确配准；进行了拼接实验，验证了算法的精度。5.2展望经实验验证，本文在模型质量评估和模型拼接领域提出配准算法满足实际要求。由于时间有限，本文的研究存在一些待改进的地方。（1）本文在提取平面、柱面特征时，使用的是人工手动的方法选择局部区域，再删选错误点得到的。虽然从理论上论证了自动提取法没有人工提取法高效，并没有设计实验进行对比。下一步中可以进行做进一步研究。56 第五章总结与展望（2）本文针对模型质量检测提出的算法虽然可以对稀疏点云进行配准，但该算法有一定的约束条件，即待配准的点云中必须含有平面或柱面特征。针对没有明显特征的稀疏点云的配准，任然需要进一步的研究。（3）本文提出的基于特征的拼接算法设定合适的曲率阈值挑选出特征点集，该算法要求两个点云的重合区域要有明显的特征。需要设计更通用的算法来改善这一限制条件。57 参考文献参考文献[1]宋林霞.三维点云配准方法的研究[D].济南大学,2013.[2]钱锦锋.逆向工程中的点云处理[D].浙江大学,2005.[3]刘丰华.复杂模型三维点云自动配准技术的研究[D].天津大学,2014.[4]李选富.散乱点云自动配准技术研究[D].哈尔滨工业大学,2010.[5]LaiJY,UengWD,YaoCY.RegistrationandDataMergingforMultipleSetsofScanData[J].InternationalJournalofAdvancedManufacturingTechnology,1999,15(1):54-63.[6]魏江,何明一,熊邦书等.多视点三维数据合并中的定标球球心算法[J].计算机辅助设计与图形学学报,2006,03:416-420.[7]BESLPJ,MCKAYND．Amethodforregistrationof3-Dshapes[J].IEEETransactionsonPatternAnalysisandMachineIntelligence,1992,14(2):239-256.[8]ChenY,MedioniG.ObjectModelingbyRegistrationofMultipleRangeImages.Imageandvisioncomputing,1992,10:145-155[9]ZhangZ.Iterativepointmatchingforregistrationoffree-formcurvesandsurfaces[J].InternationalJournalofComputerVision,1994,13(2):119-152.[10]G.Turk,M.Levoy.ZipperedPolygonMeshesfromRangeImages[C]//Proceedingsofthe21stAnnualConferenceonComputerGraphicsandInteractiveTechniques,1994,311-318.[11]T.Masuda,K.Sakaue,andN.Yokoya:RegistrationandIntegrationofMultiplethRangeImagesfor3-DModelConstruction[C]//Proceedingsofthe13InternationalConferenceonPatternRecognition,1996,1:879-883.[12]JostT,HugliH.Amulti-resolutionschemeICPalgorithmforfastshaperegistration[C]//3DDataProcessingVisualizationandTransmission,2002.Proceedings.FirstInternationalSymposiumon.IEEE,2002:540-543.[13]SharpGC,LeeSW,WeheDK.ICPregistrationusinginvariantfeatures[J].PatternAnalysisandMachineIntelligence,IEEETransactionson,2002,24(1):90-102.[14]MitraNJ,GelfandN,PottmannH,etal.RegistrationofPointCloudDatafromaGeometricOptimizationPerspective.[J].ProceedingsofEurographics,2004:22-31.58 参考文献[15]HollandJH.Adaptationinnaturalandartificialsystems[J].UniversityofMichiganPressAnnArborMich,1992.[16]张学昌,习俊通,严隽琪.基于扩展高斯球的点云数据与CAD模型配准[J].机械工程学报,2007,06:142-148.[17]TsinY,KanadeT.ACorrelation-BasedApproachtoRobustPointSetRegistration[J].LectureNotesinComputerScience,2004,3023:558-569.[18]GoldS,RangarajanA,LuCP,etal.Newalgorithmsfor2Dand3Dpointmatching:Poseestimationandcorrespondence[J].PatternRecognition,1999,31(8):1019-1031.[19]KnorrEM,NgRT,TucakovV.Distance-basedoutliers:algorithmsandapplications[J].VldbJournal—theInternationalJournalonVeryLargeDataBases,2000,8(3-4):237-253.[20]ChungDH,YunID,SangUL.Registrationofmultiple-rangeviewsusingthereverse-calibrationtechnique[J].PatternRecognition,1998,31(4):457–464.[21]ChenCS,HungYP,ChengJB.Afastautomaticmethodforregistrationofpartially-overlappingrangeimages[C]//null.IEEEComputerSociety,1998:242.[22]Johnson.Spin-images:Arepresentationfor3-Dsurfacematching[D].CarnegieMellonUniversity,1997.[23]ChuaCS,JarvisR.Pointsignatures:anewrepresentationfor3dobjectrecognition[J].InternationalJournalofComputerVision,1997,25(1):63-85.[24]FeldmarJ,AyacheN.Rigid,affineandlocallyaffineregistrationoffree-formsurfaces[J].IJCV,1994,18(2):99-119.[25]ManayS,HongBW,YezziAJ,etal.Integralinvariantsignatures[C]//InECCV’04,volumeLNCS2034.2004:87--99.[26]宋景.基于反求工程的贵州少数物质民族文化遗产的保护和开发技术研究[D].贵州大学,2007.[27]张学文.地面三维激光点云处理关键技术与实现[D].北京:北京建筑工程学院,2008.[28]王瑶.从三维点云数据中提取物体特征点的研究[D].兰州大学,2010.[29]戴静兰.海量点云预处理算法研究[D].浙江大学,2006.[30]MartinRR,StroudIA,MarshallAD.Datareductionforreverseengineering[J].TheMathematicsofSurfacesVIIEd.goodmanT.n.t.informationGeometers,1997,10(1):85-100.59 参考文献[31]张连伟,李焱,刘肖琳,史美萍等.基于局部曲面拟合的散乱点云简化方法[J].计算机工程与科学,2010,12:65-68.[32]Y.H.Chen,C.T.Ng,Y.Z.Wang.Datareductioninintegratedreverseengineeringandrapidprototyping[J].InternationalJournalofComputerIntegratedManufacturing,1999,12(2):97-103.[33]LinsenL.Pointcloudrepresentation[M].Univ.,Fak.fürInformatik,Bibliothek,2001.[34]张丽艳,周儒荣,蔡炜斌等.海量测量数据简化技术研究[J].计算机辅助设计与图形学学报,2001,11:1019-1023.[35]史宝全,梁晋,张晓强等.特征保持的点云精简技术研究[J].西安交通大学学报,2010,11:37-40.[36].三维重建中的点云精简研究[D].中北大学,2015.[37]戴静兰,陈志杨,叶修梓.ICP算法在点云配准中的应用[J].中国图象图形学报,2007,03:517-521.[38]贾宁.基于二次曲面逼近的点云模型分割[D].山东大学,2008.[39]DoraiC,WangG,JainAK,etal.Registrationandintegrationofmultipleobjectviewsfor3Dmodelconstruction[J].PatternAnalysisandMachineIntelligence,IEEETransactionson,1998,20(1):83-89.[40]BianZ,TongR.Feature-preservingmeshdenoisingbasedonverticesclassification[J].ComputerAidedGeometricDesign,2011,28(1):50–64.[41]StamosI,LeordeanuM.Automatedfeature-basedrangeregistrationofurbanscenesoflargescale[C]//2012IEEEConferenceonComputerVisionandPatternRecognition.IEEEComputerSociety,2003:555.[42]ChaoC,StamosI.Semi-AutomaticRangetoRangeRegistration:AFeature-BasedMethod[C]//null.IEEEComputerSociety,2005:254-261.[43]陈龙飞.基于逆向工程的曲轴检测技术研究[D].重庆：重庆大学机械工程学院，2013.[44]ErdősG,NakanoT,VánczaJ.AdaptingCADmodelsofcomplexengineeringobjectstomeasuredpointclouddata[J].CIRPAnnals-ManufacturingTechnology,2014,63(1):157-160.[45]吕震.反求工程CAD建模中的特征技术研究[D].浙江大学,2002.[46]张益泽,王解先.初值任意选取的圆柱面拟合方法[J].工程勘察,2012,01:77-80.60 参考文献[47]MarquardtDW.Analgorithmforleast-squaresestimationofnonlinearparameters[J].JournaloftheSocietyforIndustrial&AppliedMathematics,1963,11(2):431-441.[48]MYang,ELee.Segmentationofmeasuredpointdatausingaparametricquadricsurfaceapproximation[J].Computer-AidedDesign,1999,31(7):449–457.[49]PaulJBesl,RameshCJain.Segmentationthroughvariable-ordersurfacefitting[J].IEEETransactionsonPatternAnalysisandMachineIntelligence,1988,10(2):167-192.[50]郑萍.基于三维点云的规则形面自动识别研究[D].北京：首都师范大学，2011.[51]ZhangY,DaF,LiX,etal.NewMethodforLocatingthe3DFacialLandmarkPoints[C]//PatternRecognition,2009.CCPR2009.ChineseConferenceon.IEEE,2009:1-5.[52]李婷.板材多点成形件曲面误差分析方法研究[D].吉林大学,2008.[53]王蕊,李俊山,刘玲霞等.基于几何特征的点云配准算法[J].华东理工大学学报:自然科学版,2009,35(5):768-773.[54]张蒙.基于改进的ICP算法的点云配准技术[D].天津大学,2013.[55]薛耀红,梁学章,马婷,梁英,车翔玖.扫描点云的一种自动配准方法[J].计算机辅助设计与图形学学报,2011,02:223-231.[56]马忠玲,周明全,耿国华,孙家泽,李静.一种基于曲率的点云自动配准算法[J].计算机应用研究,2015,06:1878-1880+1887.[57]SunW,BradleyC,ZhangYF,etal.Clouddatamodellingemployingaunified,non-redundanttriangularmesh[J].Computer-AidedDesign,2001,33(00):183–193.[58]FerrieFP,LagardeJ,WhaiteP.Darbouxframes,snakes,andsuper-quadrics:geometryfromthebottomup[J].PatternAnalysis&MachineIntelligenceIEEETransactionson,1993,15(8):771-784.[59]贺美芳.基于散乱点云数据的曲面重建关键技术研究[D].南京航空航天大学,2006.[60]葛源坤.基于曲率特征信息的散乱点云数据预处理技术研究[D].西南交通大学,2012.[61]朱延娟,周来水,张丽艳.散乱点云数据配准算法[J].计算机辅助设计与图形学学报,2006,04:475-481.61 发表论文与科研情况说明发表论文与科研情况说明发表的论文：1、孙小兵，钟莹.用基于特征的稀疏点云配准算法检测零件的加工误差，《纳米技术与精密工程》，已录用。2、孙一心,钟莹,王向鸿,孙小兵,李醒飞.柔性电容式触觉传感器的研究与实验[J].电子测量与仪器学报,2014,12:1394-1400.参与的科研项目：1、零件误差检测系统软件的开发2、柔性分布电容式触觉传感器及其信号检测电路的设计62 致谢致谢论文写到了这里，近20年的学习生涯将要告一段落，人生走到了新的起点，纵然依依不舍，但未来还有很多事情值得去探索。在天津大学的两年半，我学到了很多。感谢我的导师钟莹副教授，我的论文是在钟老师的悉心指导下完成的；钟老师严谨治学的科研态度让我学习到了怎么从事科学研究，在遇到问题时，老师的指点让我到新的思路；钟老师为人和蔼可亲，乐观开朗，关心我们的生活，就像是一位好朋友一样。感谢实验室李杏华副教授，李老师为实验室营造了轻松自由的科研环境，带领大家完成科研工作，教导我们怎么为人处事，给我们很多启发。感谢裘祖荣教授，裘老师对学生的严格要求和认真的研究态度给我们很多启迪。感谢博士师兄张海涛、苏智琨，他们给我的科研工作提供了指导意见；感谢师兄师姐包括赵禹、孙一心、王向鸿、西蒙、刘佳琛、刘佳、胡淑金、谢波、姚尧、孙立岩、胡毓国等，他们给我们作出了很好的榜样。感谢同一届的路广、周鸿昆、周策策、肖云龙、刘琦、卫雅欣，是他们陪伴我一起学习。感谢师弟江尚良、吴超和师妹杨方、秦国花、陈哲、孙立环、孙芊慧，他们为答辩做了很多准备工作。感谢室友葛华磊、张鑫、孙庚，我们在宿舍谈天论地，互相帮助，一起打篮球，一起学习，有很多美好的回忆。感谢家人的无私关怀和支持，他们让我感受到家庭的温暖，在我的学业上给我很大支持。感谢女朋友唐丽娜，她让我对自己有了更清楚的认识，让我明确了生活的目标，让我充满了生活的动力。感谢好朋友陈凯、梁晓军等，他们总是在我困难的时候无私帮助我，我们永远是志同道合的朋友。再次感谢所有关心我的人！63