【优秀硕士博士论文】散乱点云三角网格化技术研究与实现

硕士学位论文散乱点云三角网格化技术研究与实现REASEARCHANDAPPLICATIONOFTECHNIQUESON3DPOINTCLOUDNOISEREDUCINGANDSAMPLING学科专业机械电子工程论文题目散乱点云三角网格化技术研究与实现学科专业机械电子工程摘要随着三维光学扫描技术的发展，已经能够获得高精度的点云数据，然而如何高效地通过点云数据得到逼真的曲面模型是当前逆向工程和产品质量检测中的一个难题。在各种曲面建模表现方式中，三角网格模型以其结构简单，便于计算，能够高精度的逼近原始曲面等优点，成为参数曲面的标准表示方法。本文针对逆向工程中的点云三角网格化技术，对散乱点云的三角剖分，建模之后的网格简化和网格平滑技术进行了深入的研究，主要内容和成果有1设计并实现了针对三维光学测量系统的点云三角化系统方案，首先对散乱点云进行三角网格剖分，接着对三角剖分后的网格模型进行简化处理，最后将网格模型光顺处理，得到完整优化的曲面模型由于逆向设计和产品的质量检测。2研究了海量点云的三角剖分技术。提出并实现了一种基于空间分割的曲面拟合三角化算法，对没有拓扑结构的海量点云数据进行空间划分，求取每一个采样点的K个邻域点，计算点的切平面之后,构建空间点到切平面的距离函数进行插值，最后通过步进立方体的算法生成网格模型。该算法提高了海量数据的处理效率，改善了曲面边界及尖锐区域的重建效果。3研究并实现了网格模型的精简技术，通过计算边折叠代价实现了基于曲率的边折叠简化算法，将曲率作为判断基准进行边折叠的更新操作，达到网格简化的目的，能够在减少数据数据量的同时保持模型上的细小特征。4研究并实现了网格模型的光顺技术，采用基于法失的自适应双边滤波算法进行滤波，首先根据邻域点估算点的法失，其次在二阶邻域点内计算滤波因子，最后计算出点的新坐标值。该方法能较好保持几何特性并实现曲面光顺。经过试验和分析，并结合在三维光学测量系统中的应用，结果表明本系统能够实现散乱三维点云的三角网格重建，效果良好。关键词网格重建；三角化；包围盒划分；网格简化；网格光顺论文类型应用研究TITLEREASEARCHANDAPPLICATIONOFTECHNIQUESONPOINTCLOUDNOISEREDUCINGANDSAMPLINGSPECIALITYMECHANICALELECTRONICENGINEERINGAPPLICANTHUANGWANGSUPERVISORASSOCVICEPROFJINLIANGABSTRACTWITHTHETHREEDIMENSIONALOPTICALSCANNINGTECHNOLOGY,HASBEENABLETOOBTAINHIGHPRECISIONPOINTCLOUDDATA,BUTHOWTOEFFICIENTLYTHROUGHTHEPOINTCLOUDSURFACEDATAAREREALISTICMODELISTHECURRENTREVERSEENGINEERINGANDPRODUCTQUALITYTESTINGINAPROBLEMINAVARIETYOFMANIFESTATIONSOFSURFACEMODELING,TRIANGULARMESHMODELOFITSSIMPLESTRUCTURE,EASYCALCULATION,HIGHPRECISIONAPPROXIMATIONTOTHEORIGINALSURFACE,ETC,TOBECOMETHESTANDARDPARAMETRICSURFACEREPRESENTATIONINTHISPAPER,THEPOINTCLOUDREVERSEENGINEERINGTRIANGULARMESHTECHNOLOGY,THESCATTEREDPOINTCLOUDTRIANGULATION,MODELINGTHEGRIDAFTERTHEGRIDSMOOTHINGTECHNIQUETOSIMPLIFYANDCONDUCTEDINDEPTHRESEARCH,THEMAINCONTENTSANDRESULTSARE1DESIGNANDIMPLEMENTATHREEDIMENSIONALOPTICALMEASUREMENTSYSTEMFORPOINTCLOUDTRIANGULATIONGRIDDINGPROGRAM,FIRSTOFALLPAIRSOFSCATTEREDPOINTCLOUDFORTRIANGULATION,ANDTHENRIGHTAFTERTHETRIANGULATIONMESHSIMPLIFIEDMODEL,ANDFINALLYNETWORKLATTICEMODELSMOOTHINGTREATMENT,GETACOMPLETESURFACEMODELOPTIMIZATIONDUETOREVERSETHEDESIGNANDPRODUCTQUALITYTESTING2STUDYOFTHEMASSPOINTCLOUDTRIANGULATIONTECHNIQUESPROPOSEDANDIMPLEMENTEDASPACEBASEDSEGMENTATIONOFTHESURFACEFITTINGTRIANGULATIONALGORITHM,THEREISNOTOPOLOGICALSTRUCTUREOFMASSIVEPOINTCLOUDDATAINTOSPACETOSTRIKEASAMPLEPOINTFOREACHNEIGHBORHOODOFAPOINTOFKTOCALCULATEPOINTSTANGENTPLANE,THECONSTRUCTIONOFSPACEPOINTSTOTHETANGENTPLANEDISTANCEFUNCTIONINTERPOLATION,THEFINALADOPTIONOFMARCHINGCUBESALGORITHMGENERATESMESHMODELTHEALGORITHMIMPROVESTHEEFFICIENCYOFMASSDATAPROCESSINGANDIMPROVETHESURFACERECONSTRUCTIONOFTHEREGIONBOUNDARIESANDSHARPEFFECT3STUDYANDIMPLEMENTATIONOFTHEGRIDMODELTOSTREAMLINETHETECHNOLOGYANDTHEPRICEACHIEVEDBYCALCULATINGTHEEDGECOLLAPSEBASEDONTHECURVATUREOFTHEEDGECOLLAPSESIMPLIFICATIONALGORITHM,THECURVATUREOFEDGECOLLAPSEASABENCHMARKTOJUDGETHEUPDATEOPERATION,TOACHIEVETHEPURPOSEOFMESHSIMPLIFICATION,CANBEREDUCEDATAAMOUNTOFDATAWHILEMAINTAININGASMALLMODELFEATURES4STUDYANDIMPLEMENTATIONOFTHEGRIDMODELSMOOTHINGTECHNIQUES,LOSSBASEDMETHODOFADAPTIVEBILATERALFILTERINGALGORITHMFORFILTERING,THEFIRSTNEIGHBORHOODOFPOINTSUNDERTHEPOINTESTIMATESOFTHEFRENCHLOSS,FOLLOWEDBYSECONDORDERNEIGHBORHOODSPOTSINTHECALCULATIONOFFILTERFACTORANDFINALLYCALCULATETHENEWCOORDINATESOFPOINTSTHISMETHODCANMAINTAINTHEGEOMETRICPROPERTIESANDTOACHIEVESURFACESMOOTHNESSTHROUGHTESTINGANDANALYSIS,COMBINEDWITHTHREEDIMENSIONALOPTICALMEASUREMENTSYSTEMAPPLICATIONRESULTSSHOWTHATTHESYSTEMCANACHIEVETHESCATTERED3DPOINTCLOUDOFTHETRIANGULARMESHRECONSTRUCTION,GOODEFFECTKEYWORDSGRIDRECONSTRUCTIONTRIANGULATIONBOUNDINGBOXDIVISIONMESHSIMPLIFICATIONMESHSMOOTHINGTYPEOFTHESISAPPLICATIONRESEARCH目录1绪论111引言112三维点云三角化技术1121研究背景1122国内外研究现状213课题来源与研究意义5131课题来源5132研究意义514研究内容与技术路线6141研究内容6142技术路线615本文结构安排72散乱点云三角网格重建方案921引言922XJTUOM系统及网格重建环节9221XJTUOM三维光学扫描系统介绍9222点云三角网格重建所处的环节1023点云网格重建关键技术分析11231点云三角化11232网格简化13233网格光顺1424点云网格重建系统方案设计15241点云网格重建系统设计原则15242针对三维光学测量的点云三角化方案15243点云三角化目标的制定1625本章小结163点云三角网格划分1731引言1732MARCHINGCUBES算法原理17321基本定义17322基本原理与步骤18323三角形顶点位置和法向计算1933基于空间分割的三角网格划分20331空间划分及邻域计算20332点云切平面计算22333场函数定义24334算法实现2434实验结果及分析2635本章小结294三角网格的简化与光顺3041引言3042网格基础30421网格表示的数据结构30422三维网格中的基本定义3143网格简化32431简化算法的分类及评价32432基于曲率的边折叠简化算法32433实验效果及分析3644网格光顺38441常用网格光顺算法38442点的法向量的计算39443基于法失调整的双边滤波网格光顺算法40444实验效果及分析4245本章小结455系统实现及应用4651引言4652点云网格重建系统方案的实现46521软件的实现46522功能模块46523点云网格建模过程4853应用实例5354本章小结556结论与展望5661结论5662展望56致谢58参考文献59附录62攻读学位期间取得的研究成果63声明CONTENTS1PREFACEX11DRIPIRRIGATIONTECHNOLOGYX111DRIPIRRIGATIONSYSTEMSX2RAPIDDEVELOPMENTOFLABYRINTHDRIPIRRIGATIONEMITTERSX21STRUCTURALDESIGNOFLABYRINTHDRIPIRRIGATIONEMITTERSX211THEORYX26BRIEFSUMMARYX12CONCLUSIONSANDSUGGESTIONSXACKNOWLEDGEMENTSXREFERENCESXAPPENDICES（单个附件用APPENDIX）XACHIEVEMENTSXDECLARATIONEQUATIONCHAPTER1SECTION1MERGEFORMAT111绪论11引言随着计算机图形学的发展，很多领域都出现了对“实体数字化”技术的强烈要求，越来越多的企业、研究机构甚至个人迫切地需要得到实体的高精度数字化模型，而利用传统的几何造型技术进行设计不仅费时而且不能得到物体真实的几何信息。正是在这样的应用背景下，三维光学测量技术实现了飞速的发展。三维扫描能获得物体表面点的三维坐标信息，它属于一种立体测量技术。与传统测量技术相比，它能够完成对复杂物体的测量，特点是非接触、精度高、速度快，能大幅节约时间和成本，并且其测量数据通用性比较强。这些优势使三维扫描技术得到了广泛的应用，并且在某些特殊场合，三维扫描技术还具有独特的、不可替代的作用。比如测量比较柔软的物体，用传统的接触测量方法，很可能在测量时使物体变形，从而使测量结果不准确，而三维扫描技术以光为测量媒质，不会引起物体表面的形变和损伤。三维扫描技术在众多领域内的广泛应用。其中最为重要的并且最为代表性的应用领域为逆向工程和质量检测。三维光学扫描仪采用非接触的测量方法，直接得到真实物体表面的采样点，即点云数据，利用点云数据即可以重构出任意曲面。如何快速的讲点云数据转变化为实体模型是逆向工程中需要解决的重要问题。本章首先介绍了点云三角化技术的研究背景、国内外研究状况，然后阐述了本课题的来源和研究意义，最后说明了本文的主要研究内容和技术路线。12三维点云三角化技术121研究背景计算机辅助设计与制造（CAD/CAM）技术是计算机应用最重要的领域之一，是先进制造技术的重要组成部分，它是指利用计算机技术完成设计过程中的信息检索、分析、计算、综合、修改及文件编制工作。上个世纪90年代以来，随着激烈的市场竞争，对产品研发的时间和产品的更新换代速度提出了越来越高的要求，因此，逆向工程技术1（REVERSEENGINEERING）应运而生。通过三维激光扫描得到的点云数据，需要建立起三维模型。早期，三维模型大多是从三维视图和照片用手工建立起来的，这类建模方法通常和某些软件结合在一起，常用的如3DSTUDIO、AUTOCAD、3DSMAX等。这样的方法在概念上有严格的数学描述，对几何形体有精确表达，可控制形状的平滑并有很多基于物理的高级建模工具。但这种方法需要物体的参数表达，模型不连续且在扑结构上不灵活。目前最流行的方式是用多边形网格来描述和绘制三维模型，它把三维模型表面的点连接成以多边形为单位的网格，是一种简单而高效的表达方式。它可以表达复杂的表面，提供很强的适应性，其中尤以三角网格的使用最为广泛。相对于早期手工建模，三角形网格的方法采用了分段线性拟合的思想，可以在物体表面不规则地采集样本点并完全不需要对物体进行参数化。因为上述的这些优点，三角形作为为三维模型的基本要素已经被广泛地接受，三角形网格绘制的方法也获得了大部分计算机硬件的支持。三维扫描中采集到的点云数据具有数据庞大的特点，并且由于采集中不可避免的会有噪声的存在，因此在对点云进行网格重建后，需要对网格模型进行后续的精简和关顺操作，这些点云处理技术就是本文研究的重点。122国内外研究现状三角网格自动剖分技术的研究起源于20世纪70年代，主要为了满足航空、数学、地质等领域解决实际问题的需要。20世纪80年代三角网格剖分在众多领域引起了广泛的关注，世界各国的学者和研究机构从不同的需求出发，对三角网格剖分进行深入的研究。目前，点集的网格剖分的主要研究集中在曲面网格剖分以及边界的一致性问题问题，散乱点云的网格重建技术2,3,4成为图形学中一个活跃的研究方向,目前主要包括有以下几个研究方向1）基于德劳内（DELAUNAY）准则的方法DELAUNAY准则的方法主要应用VORONOI图对散乱点云进行DELAUNAY三角化，其主要思想是对每个采样点在各个方向探索所有邻域，寻找可能的邻近点来计算曲面。1972年，LAWSON5提出了三角化的最大内角最小化原则，符合这一原则的三角化称为局部均匀的。随后SIBON29证明了DELAUNAY三角化是符合这一原则的唯一形式。紧接着GREENANDSIBONL实现了二维空间的VORONOI图的计算及DELAUNAY三角化。BOWYER和WATSON把结果推广到任意维。随后出现了大量的文献，用各种不同的方法去实现VORONOI图和DELAUNAY三角化。由于DELAUNAY三角剖分后的结果是一个三角形二维或四面体三维的凸包，并不表示真正的原物体表面，其中包含许多冗余的三角形或四面体。常用的DELAUNAY准则方法主要有增量法和分治算法。增量法通过遍历所有离散点，求出点集包围盒，再将点集中的点依次逐点插入。增量法如图11所示，首先找出包含新顶点的三角形，然后再做局部的修改和优化，直至所有点均插入为止。该方法理论严密，唯一性好，且易满足DELAUNAY三角化的空外接圆特性。二维BOWYER/WATSON算法先生成给定点区域的大三角化，然后递增地向其中插入新点。新插入点落在一些现有三角片的外接圆内时，这些三角片图中深色部分就不再是DELAUNAY三角片了，首先将其删除。由于剩余三角片依然还都是DELAUNAY三角片，只需在插入点周围形成的空多边形内增加新的三角片，分别连接插入顶点与空多边形各顶点，即可形成新的DELAUNAY三角化。重复上述操作直至所有顶点均插入到三角化当中。分治算法，将点集分成规模相当的两部分，对形成的两部分再进行分割，如此递归处理，然后对两部分作拼合计算，直至最后全部完成。LEWIS和ROBINSON在1977年首先提出分治算法，并将分治算法的基本思想应用于DELAUNAY三角网格的构建。其思路是采用递归分割点集直至每个子集中仅含三个离散点而形成三角形的办法，经过自下而上逐级合并生成最终的三角网。图11BOWYER/WATSON算法示意图DELAUNAY算法的优点就是重建曲面网格的复杂性和输入采样点的复杂性成正比，而且采样浓度未知也能够界定重建质量。其主要缺点就是计算DELAUNAY三角形需要较大的内存开销和时间，对于大规模的点云，这些方法就显得力不从心。2）基于区域增长的方法区域增长的方法基本原理是从一种子三角形开始，基于某种准则，不断选择新点并加入当前的区域边界，生成新三角形，更新边界，直到遍历所有点，将所得数据集的初始剖分优化后，获取逼近被测面的三角网格。算法的关键是按照怎样的规则在点云中选择新的点。如图12所示BOISSOLMAT中率先介绍了这种算法，并以三角形张角最大为选点准则。CHOFI43的三角形递增基于以下假设存在某个三维点，由该点可看到被测面上所有散乱点，并V可定义以为锥顶的凸锥，使之包含所有散乱点。初始三角剖分后，以最小内角最大V和光顺性准则优化网格。该算法具有可直接处理凸封闭曲面和开曲面的优点，尽管如此，因受凸锥顶角的角度限制，所建曲面可能存在不稳定区域。GOPI等人基于低维DELAUNAY三角剖分技术，快速实现每个数据点的局部拓扑重建，自动矫正局部数据点的非法连接关系，算法效率高，能处理大规模数据点云。CROSSNO基于螺旋边准则，即从初始三角网格的边界开始，对边界上的每个点按最小内接圆准则得到新的三角形，更新边界，直至覆盖整个数据点云，该法在数据分布均匀时效率很高。BEMARDINI47的滚球法，又称BPA算法BALLPIVOTINGALGORITHM是基于即E理论，利用半径为的球在数据点云中的滚动建立网格。滚球遵循的基本原则是若该球接R触到3个点，且不含其它点，则该点形成一个三角形。该法继承了的各种优良性能，并具有概念简单、直观、参数设置少、执行时间为线性、存储要求低、鲁棒性好、能处理简单模型等优点，可惜因难以确定滚球半径而致算法效率低。此外，文献中的方法，对于每一条活动边，分别将与这条边的两个端点距离最近的个点投影到这条边K所在的三角面片决定的平面上，从这些投影点中选择一点，这一点所对应的点云中的点与这条边形成一个新的三角面片。ABCD图12三角网格生长算法基于区域生长的方法能处理大规模数据点云，可直接处理凸封闭曲面和开曲面情况，然而，该类方法通常需人为对数据点云预先划分区域，不可靠，也降低了自动化程度，对于噪音则显得无能为力。3）基于隐士曲面拟合的方法隐式曲面拟合方法是使用隐函数曲面拟合数据点，然后在零等值面上提取三角形网格的一类方法。这些隐函数通常为径向基函数或多项式函数，而提取三角形网格的方法，主要以MATCHINGCUBE和BLOOMENTHAL多边形化这两种方法为代表。曲面拟合方法可用一个函数解析表达式完全表达被测表面的曲面方程，广泛应用于计算机视觉、模式识别等邻域，但整体逼近的方式致使逼近精度往往不高否则导致解大规模的线性方程，如径向基函数拟合法，因此常常需要进行局部细微特征的拟合。1996年，FLOATER使用分层结构的紧支撑径向基函数，首先使用DELAUNAY三角剖分计算数据子集的嵌套序列，每层基函数的尺度由来自三角化信息的当前层的点云浓度所决定。这个方法大大降低了传统径向基函数插值/逼近散乱点的时间效率问题。2001年，CARR等人提出了一种通过贪婪选择过程减少基函数中心的快速算法，叫快速多极方法。快速多极方法能够对几十万个点，使用一个简单的RBF函数来实现快速的拟合，同时对缺失的点云能够实现很好的修补，弥补了紧支撑径向基函数的主要缺点。同年，MORSE等人利用高斯函数来作为紧支撑径向基函数，获得稀疏插值矩阵。2003年，OHTAKE通过对点云分层建立八叉树，每层构造紧支撑径向基函数来实现对散乱点的插值/逼近。这种由粗至精的方法能够很好恢复大片的残缺点云数据，而且对点云的疏密不敏感。同年，在单位分解法思想的基础上，OHTAKE提出了MPU方法MULTILEVELPARTITION。RUNITY，为了获取曲面局部的细节特征，使用系数不同的分段二次多项式函数来逼近局部点云，同时权函数混合这些多项式函数。对于局部形状的复杂程度不同，八叉树相应进行不同程度的细分来充分表示物体表面特征，比如表面细节、边和角等尖锐特征。规则的隐式曲面一般用多边形化法来绘制，可以满足任意精度的要求。存在的问题是曲面上一些曲率较大的部分要用许多多边形才能精确表达出来，绘制效率很低；还有对于一些隐式曲面，比如自相交（SELFINTERSECTING）隐式曲面是很难用多边形化法绘制出来。（A）原始点云（B）MARCHINGCUBES输出（C）重建效果图13隐士曲面拟合的重建效果13课题来源与研究意义131课题来源对企业进行了深入的调研和需求分析，陕汽集团、西飞集团、四川德阳二重、河南奔马集团、天津汽车模具有限公司、美国CAOGROUPE,INC都对得到工件完整的实体数字模型有着极大的需求。本课题研究成果将应用于天津汽车模具有限公司泡沫实型的检测、模具的表面检测和制件的检测以及美国CAOGROUPE,INC牙模点云采集及点云预处理。本课题得到国家863项目“大型复杂曲面产品的反求和三维快速检测系统研究”和江苏省科技支撑计划（工业部分）的支持。研究成果将应用于天津汽车模具有限公司泡沫实型的检测、模具的表面检测和制件的检测。132研究意义点云网格重建如图14所示，其过程在于寻找某种数学描述形式，构造一个带有顶点和相互连接拓扑关系的三角形网格模型，并以此为依据对网格本身进行分析、优化改和绘制。复杂物体扫描获取的点云数目己经超过几百万个，甚至上亿，给曲面重建技术带来新战和困难L由于这些技术产生大量的体数据，需要有效地被存储和处理2不精确的照相机定位，图像扭曲和配准误差使得点云产生大量噪音和离群点加大了曲面重建的难度，同时导致细节特征丢失。3扫描光照的不完善、材料表面的低反射率和遮挡导致物体表面的数据丢失，从而在点云中产生空洞，导致原始表面特征恢复难度加大。针对这些问题，许多研究者提出了多种解决方案，但是对超大规模而且带有大量噪音的点云，推测物体表面几何结构形式，并非易事。图14散乱点云三角化模型从近几年来的点云网格重建方法中可以看出，快速鲁棒地对点云进行曲面重建仍然是广大研究者不断努力的目标，除了基于点的造型、CAD中的NURBS曲面外，散乱点云曲面重建几乎都集中网格重建。散乱数据的曲面重建一直以来只是函数逼近论的一个重要研究内容，但是随着激光测距扫描等三维数据采样技术和硬件设备的日益完善。以往难以满足取样密度的散乱数据点集的障碍现在不再是曲面重建的瓶颈。散乱数据的曲面重建作为一种能代表将来发展趋势的新造型技术得到了广泛的研究，特别自从九十年代以来，HOPPE等人对基于散乱数据点集的任意拓扑重建算法进行了开创性的研究，散乱数据点的曲面重建越来越成为图形学界的研究热点之一。该技术具有广泛的应用前景，它的发展将会在科学研究和工程上很多的应用领域，其中包括三维扫描、边缘数据的曲面重建、艺术品及考古文物复制、游戏影视制作等发挥极大的作用。对散乱数据点集的曲面重建研究将会有力地促进造型和可视化等技术的高速发展。因此对散乱数据的曲面重建研究具有重要的理论和现实意义。14研究内容与技术路线141研究内容本文针对无拓扑结构的三维散乱点云，主要的研究工作有1提出针对研究所自主研发的XJTUOM三维光学面扫描系统点云三角网格重建方案。2点云三角化算法的研究与实现，针对无拓扑结构的散乱点云，根据邻域信息构建隐函数，采用MARCHINGCUBE算法输出三角面片。3为了保证存储的速度，对三角化后的点云进行光顺处理。4为了保证模型得匹配精度，对三角化后的点云进行光顺处理。5对点云三角化、网格简化和网格光顺等模块分别进行实验和分析。并将其应用于XJTUOM三维光学面扫描系统中，对其点云处理效果进行验证和分析。142技术路线本文首先简要介绍了XJTUOM三维光学面扫描系统的基本原理、组成、应用领域，指明了点云网格重建在逆向工程和产品检测所处的环节。在针对天汽模模具检测、北京CAOGROUPE，INC公司点云采集和国家863课题“大型复杂曲面产品的反求和三维快速检测系统研究”进行了需求分析后提出了可行的开发方案，接着按照点云网格重建三个关键技术模块三维散乱点云三角化、网格简化和网格光顺。点云三角网格划分模块主要是对隐士曲面拟合得算法上得改进，采用基于步进立方体的算法生成三角网格。网格简化主要通过局部简化算法中的边折叠算法来实现；网格平滑通过基于法矢的网格调整。然后采用MICROSOFTVISUALC60软件和OPENGL开放式图形库为开发工具，运用面向对象程序设计OBJECTORIENTEDPROGRAMMING，OOP思想，完成了点云网格重建系统设计。最后，对实现的点云网格重建处理数据量的能力、处理速度、处理效果方面对点云网格重建方案进行试验和分析，并将其应用到实际，最后根据试验和应用结果得出点云三角网格重建系统的结论，并在此基础上对进一步的发展完善方面提出展望。从总体上讲，点云网格重建所采用的技术路线如图15所示。图15本文技术路线15本文结构安排第二章先简要介绍XJTUOM三维光学面扫描系统的原理和组成，针对点云数据特点和研究所在企业横向课题以及国家863项目中遇见的问题提出了三维点云网格重建方案。第三章介绍散乱点云三角网格划分和步进立方体（MARCHINGCUBES）算法原理，对HOPPE等人提出的三维重建算法上进行改进，提出并实现了基于空间立方体分割的曲面拟合三角化方法。建立了三角化数据结构，提出了对海量数据进行空间划分的算法，并对其进行实验分析。第四章阐述了网格的简化和光顺方法，实现了基于法向量的双边滤波网格光顺算法和基于曲率的边折叠简化算法。第五章对点云网格重建进行了实验和分析，包括对点云三角化、网格简化和网格光顺三个模块分别进行精度和速度的分析，并介绍了三维点云处理系统的应用实例。第六章在总结全文和创新点的基础上，指出了本文算法的进一步研究内容，明确今后的研究方向。EQUATIONCHAPTER2SECTION12散乱点云三角网格重建方案21引言曲面重建是指从去曲面上的部分采样信息恢复原始曲面的几何模型。随着三位扫描设备精度的提高，获得的点云数据越来越庞大。点云的曲面重建方案必须满足海量点云数据快速、准确和高效的需求。本章首先简要介绍了XJTUOM三维光学面扫描系统，进而阐述了针对XJTUOM三维光学面扫描系统的散乱点云曲面重建方案，针对三角化后的网格进行简化和光顺技术的研究，实现网格的优化目标。22XJTUOM系统及网格重建环节221XJTUOM三维光学扫描系统介绍1）系统原理三维光学测量系统采用结构光非接触式照相测量原理，如图21XJTUOM三维扫面系统原理所示，它结合结构光、相位测量、计算机视觉等技术于一体，通过光栅投影装置投影数幅特定编码的结构光到待测物体上，并由成一定夹角的两个摄像头同步采集相应图像，然后对图像进行解码和相位计算，并利用匹配技术和三角形测量原理，计算出两个摄像机公共视区内像素点的三维坐标，从而实现物体的三维信息数字化和测量。所谓照相测量，就是类似于照相机对视野内的物体进行照相，不同的是照相机摄取的是物体的二维图像，而三维光学测量系统获得的是物体的三维信息。图21XJTUOM三维扫面系统原理2）硬件组成XJTUOM三维光学面扫描系统分为硬件和软件两部分。其扫描头部分如图22所示，硬件部分主要包括镜头、投影仪、两个工业相机、横梁、云台、三脚架、高性能计算机等，软件部分实现的主要功能有图像采集、图像预处理、相机标定、立体匹配和三维重建。图22XJTUOM系统硬件组成面扫描系统采用结构光非接触式照相测量原理，通过光栅投影装置投影数幅特定编码的结构光到待测物体上，由成一定夹角的两个摄像头同步采集相应图像，然后对图像进行解码和相位计算，并利用外差式多频相移三维光学测量技术，利用空间频接近的多个投影条纹莫尔特性的解相方法，计算出两个摄像机公共视区内像素点的三维坐标，从而实现物体的三维信息数字化和测量。3）应用领域XJTUOM三维光学面扫描系统主要应用领域1逆向设计快速获取零件的曲面点云数据，建立三维数模，达到快速设计产品的目的。2产品检测生产线产品质量控制和形位尺寸检测、特别适合复杂曲面的检测，可以检测铸件、锻件、冲压件、模具、注塑件、木制品等产品。3其它应用文物扫描和三维显示、牙齿及畸形矫正、整容等。222点云三角网格重建所处的环节面扫描系统可以在短时间内扫描到大量的点云数据，由于所获得的点云只包含有点的三维坐标信息，没有明确的拓扑结构，为了应用到逆向设计和产品的质量检测中，需要对获得的散乱点云进行三角网格建模及三角化处理。建模后的点云包含大量的三角网格信息，而且由于设备本身的因素，也不可避免得含有很多噪声信息，为了得到更精确得曲面模型，减少硬件存储空间，有必要对三角化后的点云模型进行光顺和简化处理，得到更加优化的网格模型。将XJTUOM系统采集得到的点云应用于实际中，要对其进行点云的网格重建。本文所提到的针对XJTUOM系统的点云处理技术在其整个测量流程中所处环节如图23所示。产品模型三维扫描获得点云数据点云三角化网格简化网格光顺逆向设计产品检测其它应用点云网格重建图23点云网格重建在测量流程中所处环节23点云网格重建关键技术分析231点云三角化对于点云数据而言，由于数据本身除了点的空间坐标之外不包含其它附加信息，因此对其进行网格化的过程实际就是进行三角剖分的过程，即对所给点集，用互不相交的三角形来近似表示点集形成的曲面，三角形的集1,2,PPN合即为该曲面的三角剖分。本文采用基于曲面拟合的方法实现网格重建。给定一组分布于曲面上的点云，隐式曲面拟合技术的主要思想就是建立一个函数，的零3IXXRYFXF水平集逼近或者插值点云,描述了某个物体的半空间，则描述物体X0FX0的边界。在判断一个点在曲面上哪一侧，及进行曲面求交时，隐式化表示给这些操作带来了极大的方便。隐式曲面允许一个复杂的形状通过一个单一的公式处理，它统一了曲面和体模型。在这样的隐式模型中，许多复杂的曲面编辑操作变得较为容易。在隐式曲面构造中，使用最多的是径向基函数RADIALBASISFUNCTIONS，RBF，它是几何数据分析、模式识别、神经网络的标准工具，在各种数学文献中得到了广泛的研究，此外二次多项式隐函数也有较多的应用。KFX1X2MXM12输入层输出层隐层图24基向径函数示意图如果要插值或者逼近给定的一组散乱点云，径向基函数，定义为X3FR1NIIFXPXMERGEFORMAT21式中是低维的多项式，是基函数，区间分布为，这里的通常被看做0,IX径向基函数的中心，公示表明，径向基函数由基函数的线性组合及线性多项式F组成，基函数通常有多种选择，比如THINPLANE线条，高斯函数，P2EPCR或等。R3R在构建某个点的函数时，需要用到该点的邻域点，也就是在空间中距离该顶点欧式距离最近的点。目前常用的空间搜索算法主要有八叉树、空间单元格ERRORREFERENCESOURCENOTFOUND和KDTREE法。其中KDTREE是由BENTLEY于1975年提出来并发展成为一种多维空间树状搜索索引结构，它特别适合空间点的搜索，具有快速查找邻近的特性，其典型应用是求点的K个最近点，本文就是采用这种结构来组织三维数据点的。图25KDTREE法划分二维平面及离散点的二叉树存储对于一个包含离散点的二维空间来说，如图25，KDTREE的生成过程就是平面被X轴和Y轴连续递归划分的过程，平面的划分深度就是KDTREE的深度，若用D表示，则KDTREE上节点的总数为2D或2D1。假设水平方向为X轴，竖直方向为Y轴，则具体的划分过程如下首先按X轴寻找分割线，即计算所有点X值的平均值，以此平均值将平面分成两部分；然后在分成的子平面中按Y值划分，分割好的子平面再按X值分割，依此类推，直到最后分割的区域内只有一个点。这样的分割过程就对应了一个二叉树，二叉树的分支节点对应一条分割线，而每个叶子节点就对应一个数据点。由上面的介绍，可以得出KDTREE的三个特点第一，每个节点代表一个矩形区域；第二，每个节点对应一个坐标轴上的划分，它的子节点就对应着这个划分；第三，节点所对应的分割线与深度对应。此外，KDTREE还具有点分布均匀的特点，所以搜索的效率比较高。232网格简化通常,3D模型需要上百万的三角面片对其进行渲染,这使得计算机硬件处理能力已不能满足现在3D计算的要求。在协同设计领域,复杂的模型影响了计算机硬件的处理能力。因此,可以在保持模型几何外观和允许误差范围内,采用适当的简化操作,减少原始模型的几何特征包括面片数、边数和顶点数,达到需要的简化速度和质量。分析归纳现有的多边形网格简化算法的基础上,以3D图形图像处理的实际需要为依据,可以将简化算法分为局部简化算法和全局简化算法。局部简化算法是指简化过程中仅考虑物体的某个局部区域的特征,应用一组局部规则对其进行简化。包括了顶点删除，边折叠以及面折叠等方法。顶点删除VERTEXDECIMATION的思想很简单在单个顶点上进行操作,首先根据这个点到平面距离的阀值来判断它是否与周围的三角面片共面,如果共面,且删除这个顶点后不会改变局部的拓扑结构,那么算法将删除这个顶点。同时,所有与该顶点相邻的面均被删除,然后通过局部三角化填补所产生的孔洞,操作反复进行,直到网格达到用户的简化要求为止。SCHROEDER等在1992年首先提出了顶点删除算法。该算法简化效率较高,简化质量好,并且实现和应用简单,可应用于大规模网格模型上。但只适用于流形模型,不能简化输入模型上非流形的顶点面折叠操作是将三角面的三个顶点聚合到一个顶点,原始三角化面退化成一个点和相邻面退化成线段。最终,一次面折叠操作将会从模型中删除四个三角面片。边折叠的思想为首先采用一组选择准则,选择一对合适的顶点对即一条边,然后将这条边折叠成一个顶点,其次更新所有与这这条边相连的边。在一个没有边界的流形网格上,每一个边折叠操作会刚好折叠两个面。顶点删除面删除顶点聚类图26常用简化操作一个好的网格简化算法应该在减少网格三角面和顶点数目的同时尽量保持原始模型的拓扑结构、边界和尖锐棱边之类的形状特征。以往的简化算法大多采用几何距离度量作为简化准则的。如GARLNAD提出的二次误差矩阵，实际也是计算新点到邻近面的距离平方和，GUEZIE提出的体积变动最小原则也是一个类似距离的度量。用几何距离度量作为简化准则能较好地控制简化后的网格与原始网之间的空间距离误差，但它很难保持网格的形状细节。例如网格有些地方曲率变化较大，但因为顶点与其邻点的距离较近，用几何距离来度量的话将被简化。SUNJOCNG考虑了网格的离散曲率，提出了以网格曲率变动最小作为一个简化时的折叠顺序准则。但同样的，如果处理的网格折叠的边长较大时，可能局部的曲率变动较小，但在空间距离误差上会有较大的变动。233网格光顺由于各种因素的影响,由测量数据直接得到的三角网格模型往往存在大量的噪声。为满足后续处理的要求,需对这种三角网格模型进行光顺处目前,用于三角网格模型光顺的主流算法有两类，能量法和拉普拉斯光顺法。能量法是用全部顶点作参数对原始网格模型定义一个全局能量函数,通过求解这个函数的约束最小解来调整网格顶点。能量法不仅计算量大,且难以对局部形状进行控制。拉普拉斯光顺法是通过对每个顶点定义一个拉普拉斯算子来确定调整方向,然后沿此方向以一定的速度移动顶点达到调整网格的目的。该方法能有效调整网格至规则形状,网格密度与形状都趋于均匀。为了构造一种整体光顺效果好,且变形小,模型原有特征得到充分保留的三角网格模型光顺方法，首先需判断出模型中的特征区域与非特征区域,然后分别采用KUWAHARA滤波算子与拉普拉斯算子进行法矢调整。在三角片法矢调整后,再调整顶点位置,即可完成模型光顺过程。顶点的位置调整可以分解为法向和切向两个正交分量来进行。沿着网格顶点的法向以平均曲率速度调节顶点的位置，能够明显地改善顶点的局部区域的几何变形，如果在切平面上移动顶点，则不能达到去噪的效果。实际上，在曲面论中，极小曲面的充要条件是平均曲率处处为零，通过在法向方向以平均曲率的速度移动可以达到光顺的目的，采用了顶点估计公式其中为平均曲率。HK1COTT24IHIJJJIJAMVKNXMERGEFORMAT22IXJXIJEIXJX1J1JXJJ图27平均曲率流算法图示如图27所示，为三角形的两个顶点，是在相邻IJIJJIEXJJIJE两个三角形中的对角，当的值大于的时候将导致为负值，JJCOTTJJ因此有时候模型的部分区域会在光顺中出现畸变。为了解决这个问题，在曲率大的地方可以适当降低光顺速度，而在曲率小的地方可以适当加大光顺速度。平均曲率流的方法能解决顶点漂移，但是该算法对曲率的依赖程度很大，光顺的效果与三维模型的曲率估计精确关系很大。24点云网格重建系统方案设计241点云网格重建系统设计原则该系统面向对象为企业横向课题和国家863项目部分，具有较强的实际应用需求，在系统设计时应遵循以下原则1具备处理大数据量的能力一般情况下，单次扫描获取得到的点云有上千万个点，软件系统需要能同时处理大数据量的点云，实现海量点云的网格重建。2具有快速的处理速度无论在于逆向设计还是产品的检测，都要满足系统的实时性。3高精度的处理结果三角化后的曲面保持原始曲面得几何特征。4较好的系统稳定性。242针对三维光学测量的点云三角化方案根据上面对系统的分析，本文制定了点云处理系统方案，如图28所示，首先加载XJTUOM系统采集得到的点云，然后计算每个点的法向量，再搜索点的邻域，计算点的场函数，根据步进立方体算法输出三角网格。对得到的初始网格进行简化和光顺处理，进一步节省存储空间，保持曲面的几何特征。加载点云数据计算邻域和切平面计算场函数MC算法输出三角面片计算离散曲率网格简化网格光顺结束点云三角化图28点云网格重建方案243点云三角化目标的制定1首先能快速的初始化点云包括去除孤立点、计算法向量、计算点云权值等。2快速的判断多幅点云的重叠区域。3融合重叠区域。4最终获得高质量的能够用于检测和逆向建模设计的点云模型。25本章小结本章主要介绍了XJTUOM三维光学面扫描系统的组成和应用领域，对本文所设计到的点云三角化的方案进行了分析和设计，对点云点云网格重建的关键技术进行研究，并根据点云曲面重建系统的设计原则提出了针对XJTUOM三维光学面扫描系统点云三角化方案。EQUATIONCHAPTERNEXTSECTION13点云三角网格划分31引言本文是针对密集点云的三角化，应用在后续的逆向设计和产品检测中，要求重建后的曲面严格的逼近原始模型，而且点云数据量庞大，点云的拓扑结构不明确。需要在保证精度的前提下，尽可能的提高处理速度。为此本文在HOPPE等人提出的三维重建算法上进行改进，提出了对海量数据进行空间划分的算法，首先取每一个采样点的K个邻域点,，计算点的近似切平面,求出切平面的法向量，确定了切平面后,构建空间点到切平面的距离函数进行插值，通过步进立方体的算法生成网格进而生成曲面。32MARCHINGCUBES算法原理321基本定义基于分割的MC（MARCHINGCUBES）算法以图像分割作为三维重构的基础,分割的目的是将三维图像序列二值化。三维重构用图像分割的结果作为输入,进行等值面的提取。图像分割的结果组成三维规则数据场,作为MC算法的输入。三维规则数据场可以用下式表示,1,1,IJKIJKXYZFXYZINJKNMERGEFORMAT31式中定义为，定义为X轴，Y轴，Z轴各方向上的,IJK,IJKFXYZ数据点，给出以下定义定义1已知区域内的场函数,则等值面可由隐函数来定义RS,|,RSXYZZC为常数定义2称为等值点,为正点,为负点。CPF（）|PF（）C|PF（）是面检测参数。定义3MC算法中的体元可以如图31所示体元实际上是体数据中包含相邻八个采样点的最小立方体,其八个数据点位于该体元的八个角点上。图31体元示意图322基本原理与步骤MC算法以数据场中的相邻两层上的各四个像素为顶点组成的立方体为最小的等值面搜索单元也称为体元。其基本思想是逐个处理数据场的体元，分类出与等值面相交的体元，采用线性插值计算出与等值面相交的体元的棱边上的交点，根据体元8个顶点与等值面的相对位置，将这些交点按一定方式连接成三角面，作为等值面在体元内的逼近表示，所有体元中的等值面构成整个数据场的等值面。等值面中各三角片顶点处的法向量的计算，一般先采用中心差分计算出体元顶点处的梯度，再用线性插值计算等值点处的梯度值作为该点的法向量。计算等值点的过程比较简单，首先对体元的8个顶点进行分类，以判定该顶点是位于等值面内还是等值面外。再根据8个顶点的状态，确定等值面在体元内部的连接方式。假定等值面的值为C。则顶点分类规则为（1）如果体元顶点的数据场值C0，则定义该顶点位于等值面之外，标记为1；（2）如果体元顶点的数据场值C0，则定义该顶点位于等值面之内，标记为0；（3）对于一个体元而言,如果它所有顶点的索引值都为1,则表示该体元位于表面内如果所有顶点的索引值都为0,则表示该体元位于表面外除此之外的索引值的其它情况,则表示该表面穿过此体元。（4）在此基础上定义体元中表面的拓扑结构,以后根据具体的数据确定切点的位置由于每个体元有八个角点,每个角点可能有0,1两种状态,因此每个体元与等值面相交的情况有256种状态。这些状态具有对称性,即互补对称性和旋转对称性1互补对称性将一个体元的八个角点的状态都加以改变，1变为0，0变为1,得到的体元与等值面的相交状态与原体元状态一致。经过这种对称性变换,体元的状态可以简化为128种。2旋转对称性如果某一体元经过旋转变换后与另一状态的体元一致,即顶点位置和及其状态值相同,那么这两种状态可以合并为一种状态。根据旋转对称性,体元的最后以减少到减少15种。图3215种体元相交状态323三角形顶点位置和法向计算对于每一种相交模式,可以基于各顶点的状态建立它的索引,索引设8位,每一位代表一个顶点的状态,如所示此索引值作为查询情况表的指