【优秀硕士博士论文】光学三维快速检测系统中的点云融合技术研究与应用

硕士学位论文光学三维快速检测系统中的点云融合技术研究与应用POINTCLOUDINTEGRATIONIN3DFASTMEASURINGSYSTEM学科专业机械制造及其自动化2009年01月论文题目光学三维快速检测系统中的点云融合技术研究与应用学科专业机械制造及其自动化摘要针对现有点云融合方法融合数据速度慢、占用内存大、不能适用于光学三维快速检测的问题，在深入研究国内外已有点云融合理论的基础上，结合面结构光扫描技术的特点以及快速检测的工程实际需求，本文对光学三维快速检测中的点云融合技术进行深入研究。主要内容和成果如下1设计并实现了针对光学三维快速检测系统的点云融合方案，即首先对点云进行预处理去除孤立点、计算法向量、计算点云权值、减小边界点权值、精简数据等。然后融合多层点云数据，获得单层完整的点云数据，用于比对检测或逆向设计。2设计并实现了单面法融合点云数据的方法。首先确定基准点云，然后根据给定的误差带确定并去除非基准点云中的重叠点，最后将不包含重叠点的多幅点云合并为单层的一幅点云。该方法的优点是效率高，可以很好的应用于快速检测中，但该方法融合后的表面光滑度不好，不能很好的应用于逆向设计中。3设计并实现了中点法融合点云数据的方法。首先去除每幅点云中的孤立点，其次搜索两幅点云中的对应点对，为了加快搜索速度，本文采用KDTREE空间邻域搜索策略。最后用点对的中值代替点对中的两个点，从而实现去除冗余点。该方法相对于单面法表面光滑度有所改善，但融合效率比单面法慢。4实现了聚类法融合点云数据的方法，并对该方法进行了改进首先提出了结构光扫描技术中点云权值计算的理论，实现了结构光扫描技术中点云权值的计算；其次对KD_TREE空间邻域搜索方法进行了改进，实现了一种高效的空间近邻点云搜索策略，有效提高了点云数据融合的速度；最后提出按包围盒等间距分割点云数据的方法，分块多次融合点云，解决了融合海量点云数据时内存不足的问题。该方法融合效率比单面法低但比中点法高，融合后表面光滑，可以很好的应用于快速检测和逆向设计中。经过试验、分析及工程应用，结果表明本文提出的方法在保证点云数据融合精度的同时，提高了点云融合的效率，满足了三维快速检测的工程实际需求，效果良好。关键词光学三维快速检测；点云融合；单面法；中点法；改进的聚类法；论文类型应用研究TITLEPOINTCLOUDINTEGRATIONIN3DFASTMEASURINGSYSTEMSPECIALITYMECHANICALENGINEERINGAPPLICANTBAOQUANSHISUPERVISORVICEPROFLIANGJINABSTRACTTHEPOINTCLOUDINTEGRATIONTECHNIQUEOF3DOPTICALRAPIDDETECTIONISINDEPTHSTUDIEDINTHEPAPER,BASEDONTHETHEORYOFPOINTCLOUDINTEGRATIONATHOMEANDABROADHAVEBEENRESEARCHEDINDEPTH,FORTHEEXISTINGPOINTCLOUDINTEGRATIONMETHODSWITHSLOWEFFICIENCY,TAKEMUCHMEMORY,CANNOTBEAPPLIEDTO3DOPTICALRAPIDDETECTIONTHESURFACESTRUCTUREOPTICALSCANTECHNIQUEANDTHENEEDSOFRAPIDDETECTIONPROJECTARECOMBINATEDTOCONSIDEREDTHEMAINCONTENTSANDACHIEVEMENTSARELISTEDASFOLLOWS1THEPOINTCLOUDINTEGRATIONPROGRAMFOR3DOPTICALRAPIDDETECTIONSYSTEMISDESIGNEDANDIMPLEMENTEDTHATIS,ATFIRST,EXECUTETHEPOINTCLOUDPREPROCESSING,REMOVETHEISOLATION,CALCULATETHEVECTORANDVALUEOFPOINTS,DECREASETHEWEIGHTOFTHEBORDER,SAMPLINGTHEDATA,ANDTHENINTEGRATEPOINTCLOUDDATA,REMOVEREDUNDANTPOINTSATLASTCONTRASTTHEPOINTCLOUDDATAANDCADMODEL2THEMETHODOFHOLDONELAYERAMONGMULTIOVERLAPLAYERSISREALIZEDFINDTHEBASEPOINTCLOUDFIRSTLYTHENACCORDINGTOTHEERRORBAND,DELETETHEOVERLAPPOINTSINNONBASEPOINTCLOUDATLASTALLPOINTCLOUDSAREMERGEDTOGETHERTOBEONESINGLELAYERPOINTCLOUDTHISMETHODHAVEAHIGHINTEGRATIONSPEED,HOWEVERTHEINTEGRATEDSURFACEISROUGH3THEMETHODOFINTERPOLATIONBETWEENTWOLAYERSISREALIZEDFIRSTOFALL,REMOVEEACHISOLATEDPOINT,SEARCHTHECORRESPONDINGPOINTSINTWOPOINTCLOUDS,USINGKDTREESPACENEIGHBORHOODSEARCHSTRATEGYTOSPEEDUPTHESEARCHEFFICIENCY,TAKETHEMEDIANOFCORRESPONDINGPOINTSINSTEADOFTHEMTOREMOVEPOINTSREDUNDANCYCOMPAREDWITHTHEMETHODOFHOLDONELAYERAMONGMULTIOVERLAPLAYERS,THISMETHODISSMOOTHERININTEGRATIONSURFACE,BUTLOWERININTEGRATIONSPEED4THECLUSTERINGINTEGRATIONMETHODISREALIZEDANDIMPROVEDATFIRST,THETHEORYOFTHERINGHTSOFPOINTSINSTRUCTUREOPTICALSCANTECHNIQUEISPUTFORWARD,ANDCALCULATETHERINGHTSOFPOINTSTHENTHEKD_TREESEARCHMETHODISIMPROVEDANDACHIEVEAHIGHLYEFFICIENTSPACENEIGHBORSSEARCHSTRATEGIESTOINCREASETHESPEEDOFPOINTCLOUDINTEGRATIONFINALLY,DIVIDETHERESEARCHISFUNDEDBYNATIONAL863PLAN（2007AA04Z124）J1搜索重叠区域SEARCHOVERLAPAREA（I,J）删除第J幅点云上的重叠区域DELETEOVERLAPAREAJ合并两幅点云至I中MERGEI,JJN1结束NOYESJ多幅点云N图32单面法技术路线图34单面法关键技术由图32中的技术路线可知，单面法融合点云的关键技术为搜索重叠区域和删除非基准点云中的重叠点。341三维空间邻域搜索技术目前常用的空间搜索算法主要有八叉树2425、空间单元格2627和KD_TREE28法。其中KDTREE是由BENTLEY于1975年提出来并发展成为一种多维空间树状搜索索引结构，它特别适合空间点的搜索，具有快速查找邻近的特性，其典型应用是求点的K个最近点，本文就是采用这种结构来组织三维数据点的。下面将详细介绍KDTREE的生成过程。KDTREE是一个针对K维度空间所设计的二元搜索树，其本质是一个二叉树。对于一个K维度的欧氏空间，被一个正交于任意一个K维坐标轴的超平面（K1维）递归分割为两个子空间，直到每个子空间所包含的数据个数不超过给定的值为止，且每个子空间中至少包含一个数据。对于一个包含离散点的二维空间来说，如图33，KDTREE的生成过程就是平面被X轴和Y轴连续递归划分的过程，平面的划分深度就是KDTREE的深度，若用D表示，则KDTREE上节点的总数为2D或2D1。假设水平方向为X轴，竖直方向为Y轴，则具体的划分过程如下首先按X轴寻找分割线，即计算所有点X值的平均值，以此平均值将平面分成两部分；然后在分成的子平面中按Y值划分，分割好的子平面再按X值分割，依此类推，直到最后分割的区域内只有一个点。这样的分割过程就对应了一个二叉树，二叉树的分支节点对应一条分割线，而每个叶子节点就对应一个数据点。AKDTREE法划分二维平面B离散点的二叉树存储图33KDTREE法划分二维平面及离散点的二叉树存储由上面的介绍，可以得出KDTREE的三个特点第一，每个节点代表一个矩形区域；第二，每个节点对应一个坐标轴上的划分，它的子节点就对应着这个划分；第三，节点所对应的分割线与深度对应。此外，KDTREE还具有点分布均匀的特点，所以搜索的效率比较高。KDTREE的一个典型应用就是查询空间中距离一个输入点最近的一点29。这里采用一种回溯的算法来搜索最近两点，对于一个输入顶点P，首先找到P所在的区域，然后计算与P所相邻区域内所有点的最小距离，然后用这个最小距离和P到当前分割线的距离进行比较，如果最小距离小于等于P到分割线的距离则搜索结束；如果最小距离大于P到分割线的距离，则说明距离P最近的点有可能存在于分割线的另一侧区域，向分割线的另一侧回溯直到找到的最小距离小于P到当前分割线的距离。在KDTREE建立之后，某点的K邻域搜索就成了基于KDTREE划分的二叉树搜索问题了。通过空间划分的方法使K邻近点的搜索都从树的底层开始，也就是空间的小区域开始，然后逐渐再向树的上层大空间区域搜索，从而达到提高搜索速度的效果。因为大部分最近点的搜索都在树的底层完成，所以运用KDTREE查找两片点云之间最近点的时间复杂度大约是，在大数据量的情况下，比原始搜索算法的LOGPQN快的多。因此，运用KDTREE这种数据结构可以在很大程度上提高空间搜PQN索效率。下面给出KDTREE的部分C代码CLASSCKD_TREEPUBLICSTRUCTBOX_RANGEFLOATLO3FLOATHI3CKD_TREEVIRTUALCKD_TREECKD_TREEKDARRAYPA,INTN,INTDD,INTBS10VOIDSEARCHKDCOORDQ,INTK,KDINDXNN_INDX,KDCOORDDD,DOUBLEEPSPRIVATEINTDIMINTN_PTSKDARRAYPTSKDINDXPIDXCKD_NODEROOTBOX_RANGEBND_BOXVOIDINITKD_TREEINTN,INTDD,INTBSVOIDBOXRANGEKDARRAYPA,KDINDXPIDX,INTN,INTDDFLOATMAXDISTANCEKDARRAYPA,KDINDXPIDX,INTN,INTDFLOATBOXDISTANCECONSTKDCOORDP,CONSTBOX_RANGEBND_BOX,INTDIMVOIDGETMINMAXVALKDARRAYPA,KDINDXPIDX,INTN,INTCUT_DIM,FLOATCKD_NODECREATKD_TREEKDARRAYPA,KDINDXPIDX,INTN,INTDIM,INTBSP,BOX_RANGEBND_BOXVOIDGETSPLITNUMKDARRAYPA,KDINDXPIDX,INTN,INTCUT_DIM,FLOATCUT_VAL,INTVOIDSPLITKDARRAYPA,KDINDXPDIX,INTN,INTDIM,INT342去除非基准点云中的重叠点两幅点云PT1和PT2，我们以其中比较大的一幅点云（点云个数较多的点云）为基准点云（PT1），另外一幅点云为待融合点云（PT2）。那么通过建立KDTREE树，进行邻域搜索确定重叠点BUILD_KDTREEPTS2FOREACHPOINTINPTS11NODEIPTSSEARCHNEARESTPOINTNODEI当获得基准点云重叠区域的最近点后，就可以根据搜索半径（R）判断是否是重叠点，如公式（31）所示。31,TRUEIFNARESTDIRNODEILTFLS去除非基准点云中的重叠点的部分代码如下SEARCH_NEAREST_NEIGHBOR04,4,GPOINTA0,GPOINTA1IFCMPGPOINTA0LEN,GPOINTA1LENFORI0IN1结束YESJ图42中点法技术路线图44中点法关键技术由图43中点法的技术路线可知，中点法的关键技术为去除孤立点、搜索重叠区域、计算中值、去除非基准点云中未被计算的重叠点、去除密集点。搜索重叠区域的技术在前面的章节中讨论过了，在此不再论述。中值计算方法也在本章的42节中论述过，也不再分析。441去除孤立点单幅点云中的孤立点定义为与其最近点的欧氏距离41远远大于扫描间隔的那些点。造成孤立点的原因，如图43，主要是因为被扫描面的法向与扫描方向的夹角较大，造成扫描间距较大。这些点的可信度较低，偏离真实值的程度远远大于其它点。（A）扫描方向和侧面法向夹角较大（B）扫描后点云侧面图43孤立点产生的原因为了剔除孤立点对最终融合效果的影响，在融合前，本文首先去掉点云中的这些孤立点，如图44所示在点云预处理软件中用红色的圈画出来的部分是去除孤立点的参数设置，给定阀值，判断出孤立点。去除孤立点的部分代码VOIDCPOINTSMODELDELETESINGLEPOINT_POINTPT,INTK_NEIGHBOR,FLOATVAL,FLOATKEYVALUEINTISEARCH_NEAREST_NEIGHBORPT,K_NEIGHBOR,VALFORI0ILENIIFPTPOINTNODEIK_NEAREST_DISTANCENULLCONTINUEELSEIFPTPOINTNODEIK_NEAREST_DISTANCE0KEYVALUEPTPOINTNODEISELECTEDTRUE图44去除孤立点442去除非基准点云中的无对应点的重叠点造成无对应点的重叠点的原因主要有三个，下面逐一分析。首先使用面结构光扫描仪器扫描点云时，扫描栅格线不均匀，其横坐标轴的扫描间隔和纵坐标轴的扫描间隔不相同。如图45，两幅点云重叠时，栅格线互相交叉，造成第I幅点云上的某几个点可能同时对应于第J幅点云上的同一个点。由图45可以得出，两幅点云I和J上的点的对应关系并不是一一对应，有可能是一对多，或多对一，这样造成中值计算的非对应性。比如第I幅点云中的点1同时对应第J幅点云中的点2和点3，那么在计算中值时只计算点1和其最近的一个点2的中值，而点3则未参与运算。图45两幅点云中的最近点对对于上述情况，如果保留点3的话，那么会造成最终的表面更加粗糙，如图46（A）所示，所以采取直接去除点3的办法，最后形成图46（B）所示的结果。用灰色的点代表新计算得到的点，绿色代表目标点上的非重叠点。图中只画了第I幅点云中的第一条扫描线上的点云融合后的情况。可以看出，如果不去除点3的话，表面会变的像波浪形一样，不平滑。图46用中值代替原始点第二种情况，用光学扫描仪器扫描点云时，有漏扫的点云，从而造成最近点对对应错误的问题，扫描点云时点云有漏洞的情况如图47所示点1用紫色的圆圈标记出来，为漏扫的点，从而造成点2，点3属于重叠点，但不能参与运算。图47漏扫点云时最近点对匹配错误情况最后一种情况，当点云融合一次后，点距就极其不规则，从而造成最近点对一对多和多对一的情况。443去除密集点密集点产生的原因主要是因为在计算中值的时候有多对一的情况如图48所示。点1和点2同时对应点3，那么融合后的点1和点2就会靠近很多，如图中的灰色点，这样经过多次融合以后就可能造成两个点的坐标相同。为此需要去除太靠近的点对。为了避免出现上述情况，我们采用去除密集点的方法。去除密集点的方法有两种第一种，给定一个较小的阀值KJHXR7）LJHKRJXH（58）KD树加点云空间包围盒判断的搜索方法基本思想如下KD树的邻域搜索包括两个阶段第一个阶段是建树即将点云压入二叉树结构中，这个过程相比第二个阶段，要快的多，一般以MS为单位，所以对第一个阶段我们就采用常规KD建树的策略；第二个阶段是点云搜索阶段，这个阶段最消耗时间，其时间复杂度为NLOGN，所以本文对这个阶段进行改进。对于两幅没有重叠区域的点云，我们只要判断其包围盒是否相交就可以了，如果包围盒不相交，那么直接返回。对于有部分区域重叠的两幅点云，我们以压入KD树的点云的包围盒为基准，那么另一幅点云中未落入该包围盒的点不参与运算，这样相当于减少了点云的个数即减小了N。当扫描的实物比较大的时候，使用该方法可以显著提高点云的融合速度。KDTREE空间邻域搜索算法建树（点云PT1，包含N1个点）所需的时间为N1LOGN1。那么（点云PT2）N2个点搜索邻近点需要的总时间为N2N1LONGN1。令两幅点云的包围盒分别为BBOX1和BBOX2，PT1中的点落在BBOX2内的点个数记为121MINSIDEBBOXPTI，I1,2,N1；PT2中的点落在BBOX1内的点个数记为2J，J1,2,N2；那么在建树的过程中只把M1个点压入KD树，而PT2在搜索的过程中只对M2个点进行搜索，其余的点不参与运算。这时整个搜索算法的时间为M2M1LONGM1，对于两幅重叠部分较少的点云（M1N1，M2N2,M2M1LONGM1N2N1LONGN1）可以极大的减小搜索时间。而实际的点云数据重叠的部分往往比较少，所以该方法能有效提高点云处理的速度。558融合第K块点云聚类法融合点云数据依据聚类的原理，把三维空间点按照其法向量和空间欧式距离的相似性聚在不同的聚类核内，然后迭代聚类核直至稳定，最后用稳定的聚类核中心代替那些核内的点。该算法的目的在于最小化所有的数据点与其相关聚类核之间的差异，最终得到目标函数公式（59），其中是点与其所归属的聚类核2JIJXCJIX中心的距离。这个距离反映了该数据点与核中心的相似程度。为了评估融合后的表JC面与原始各幅点云表面之间的非相似性，目标函数J可以改进为公式（510）的形式，其中，J就代表了在原始各幅点云表面上的N个相关点与融合面上的对2IJJORNEWP应点的非相似性。聚类法的目的就是使目标函数最小化。（521KNJIJJIJXC9）（521IJKNJORNEWJIJP10）56软件框架聚类法的实验平台建立在单面法和中点法的基础上，并进行了改进，由于有了法向量，点云中的点可以真彩色显示。这时点云处理的软件上升为V62版本，基本界面如图511所示，软件具有的功能为全局匹配、聚类法删除点云重叠面、平滑降噪、去除局外点、测量点距、显示单个点坐标等功能。图511点云预处理软件V6257本章小结本章主要介绍了聚类法的基本原理、改进聚类法的技术路线、改进聚类法的关键技术。改进的聚类算法解决了面结构光扫描测量中点云权值计算的问题，提高了点云融合的速度，减小了融合过程中内存的占用，具有融合速度快、融合精度高、可处理大数据量点云的特点。可以满足逆向设计及三维快速测量系统的需求。EQUATIONCHAPTERNEXTSECTION16点云融合系统的实验分析及应用本文提出的算法用VC60在西安交通大学信息机电研究所自主开发的XJTUOM点云预处理软件中实现，并在实际的三维快速测量中得到应用，取得良好的效果。本文实验用计算机处理器配置均为AMD642X4400，2G内存。用到的点云均由XJTUOM三维光学密集点云采集系统扫描获得。本章从五个方面对三种点云融合方法进行实验分析融合的效果，融合的效率，融合算法的时间复杂度，融合算法的空间复杂度，融合精度。61点云融合的效果图61图65为用单面法、中点法、改进的聚类算法融合表61中某人头模型数据、某花瓶数据、某航空叶轮数据、某车门数据和某翼虎点云数据的过程。其中每组数据中的A、D、G为单面法、中点法、改进聚类法融合后的点云数据，改进的聚类法在显示的时候使用了真彩色显示。每组数据中的B、E、H为融合后的数据三角化的结果，这组数据主要是为了比较融合后模型的表面光滑程度。每组数据中的C、F、I为局部放大图，为了更清晰的比较三种方法融合后的表面。由实验结果可以得出以下结论1单面法融合的最终效果很大程度的依赖于点云的匹配精度，如果匹配的精度足够高，融合后的光滑程度越高，那么单面法可以用于逆向设计中。如果匹配精度不高，那么在多幅点云的交界处有明显的棱存在，整个模型不光滑，融合以后的模型不能很好的应用于逆向设计中。2中点法在多幅点云的交界处，对融合结果有所改进，棱的高度变为原来的一半。但没有彻底消除棱。融合后的表面的粗糙度增大，这个主要是因为经过运算后，有可能把噪声叠加在一起，所以在融合表面会出现波浪形的凸起。3改进的聚类算法克服了单面法和中点法的不足，融合后消除了边界交界处的棱，并且保持融合表面的光滑性。可以满足逆向设计的要求。A单面法融合后B单面法融合后三角化C左眼局部放大（D）中点法融合后（E）中点法融合后三角化（F）左眼局部放大（G）改进聚类法融合后（H）改进聚类法融合后三角化（I）左眼局部放大图61某人头模型用三种方法融合后效果A单面法融合后B单面法融合后三角化C凸缘局部放大（D）中点法融合后（E）中点法融合后三角化（F）凸缘局部放大（G）改进聚类法融合后（H）改进聚类法融合后三角化（I）凸缘局部放大图62某花瓶模型用三种方法融合后效果A单面法融合后B单面法融合后三角化C凸缘局部放大（D）中点法融合后（E）中点法融合后三角化（F）凸缘局部放大（G）改进聚类法融合后（H）改进聚类法融合后三角化（I）凸缘局部放大图63某叶轮模型用三种方法融合后效果A单面法融合后B单面法融合后三角化C车窗局部放大（D）中点法融合后（E）中点法融合后三角化（F）凸缘局部放大图（G）改进聚类法融合后（H）改进聚类法融合后三角化I）车窗局部放大图64某车门模型用三种方法融合后效果A单面法融合后B单面法融合后三角化C虎身局部放大（D）中点法融合后（E）中点法融合后三角化（F）虎身局部放大（G）改进聚类法融合后（H）改进聚类法融合后三角化（I）虎身局部放大图65某翼虎模型用三种方法融合后效果62点云融合速率分析对某人头点云数据、某花瓶数据、某航空叶轮数据、某车门数据和某翼虎点云数据在相同的计算机配置下进行融合，融合速率如表61及图66所示。由表61和图66可以得出，单面法的融合速度远远高于中点法及改进的聚类法，一般为它们两者的35倍，所以单面法为所有点云融合方法中效率最高的，最适用于三维快速检测。由于增加了孤立点的去除以及密集点的去除，中点法融合的效率低于单面法和改进的聚类算法的效率。表61单面法、中点法和改进聚类法的融合效率图的编号点云幅数点云数目/个单面法融合所需时间/秒中点法融合所需时间/秒改进聚类法所需时间/秒图615231309283340图6212635762344231104图6319139337186135图6482276392239471图65817025168653105010015020025013933711702516227639223130926357623点云数目/个融合所需的时间/秒单面法中点法改进聚类法图66单面法、中点法及聚类法融合效率表62及图67为原始聚类算法21和改进的聚类算法在融合效率方面的比对。由表可知，改进的聚类算法的融合效率在数据量较大的情况下，远远高于原聚类算法的效率。原聚类算法因为融合速率较慢，所以无法应用于快速检测中。表62原始聚类法与改进聚类法融合效率对比实物点云幅数点云中点个数/个原聚类法融合需时间/分钟改进聚类法融合所需时间/分钟某航空叶轮191393371078058某牙模12225179610095某车门12635762341173某面包车部分3217080308960817某大型叶片4036036228无法处理内存耗尽2000204060801001201393371225179663576231708030836036228点云数目/个融合时间/分钟改进聚类法原始聚类法图67原始聚类法与改进聚类算法融合效率63在检测中的应用实例本节以某花瓶为例说明点云融合技术在快速检测中的应用过程，如图68AH所示。A导入初始点云数据B融合完成后（融合时间14S）C将融合后的点云数据与CAD模型导入GEOMAGICQUALIFY软件中D将点云数据与CAD模型对齐E3DCOMPAREF截线分析G截面形状显示H截面偏差分析图68某花瓶点云数据与CAD模型的快速检测过程64本章小结本章主要对三种融合算法进行了比对和分析，对比了三种算法的融合效果，融合速率，并且分析了三种融合算法的时间复杂度，空间复杂度，以及融合的精度。最后以一个实例说明快速检测的整个流程。EQUATIONCHAPTERNEXTSECTION17结论与展望71结论针对企业需求、国家863课题需求及现有点云融合方法融合数据速度慢、占用内存大、不能适用于光学三维快速检测的问题，在深入研究国内外已有点云融合理论的基础上，结合面结构光扫描技术的特点以及快速检测的工程实际需求，本文对光学三维快速检测中的点云融合技术进行深入研究。提出了点云融合方案，设计并实现了单面法、中点法，改进了聚类法。最后进行了实验和分析，并应用于工程实际中，取得了较好的效果。本文得出以下主要结论1设计并实现了针对光学三维快速检测系统的点云融合方案，即首先对点云进行预处理去除孤立点、计算法向量、计算点云权值、减小边界点权值、精简数据等。然后融合多层点云数据，获得单层完整的点云数据，用于比对检测或逆向设计。2设计并实现了单面法融合点云数据的方法。首先确定基准点云，然后根据给定的误差带确定并去除非基准点云中的重叠点，最后将不包含重叠点的多幅点云合并为单层的一幅点云。该方法的优点是效率高，可以很好的应用于快速检测中，但该方法融合后的表面光滑度不好，不能很好的应用于逆向设计中。3设计并实现了中点法融合点云数据的方法。首先去除每幅点云中的孤立点，其次搜索并确定两幅点云中重叠区域的对应点对，为了加快搜索速度，本文采用KDTREE空间邻域搜索策略，最后用点对的中值代替点对中的两个点，从而实现冗余点的去除。该方法相对于单面法表面光滑度有所改善，但融合效率比单面法慢。4实现了聚类法融合点云数据的方法，并对该方法进行了改进首先提出了结构光扫描技术中点云权值计算的理论，实现了结构光扫描技术中点云权值的计算；其次对KD_TREE空间邻域搜索方法进行了改进，实现了一种高效的空间近邻点云搜索策略，有效提高了点云数据融合的速度；最后提出按包围盒等间距分割点云数据的方法，分块多次融合点云，解决了融合海量点云数据时内存不足的问题。该方法融合效率比单面法低但比中点法高，融合后表面光滑，可以很好的应用于快速检测和逆向设计中。5改进的聚类算法解决了面结构光扫描测量中点云权值计算的问题，提高了点云融合的速度，减小了融合过程中内存的占用，具有融合速度快、融合精度高、可处理大数据量点云（以千万为单位）的特点。可以满足逆向设计及三维快速测量系统的需求，已经在实际的塑料泡沫检测、铸件检测、叶片检测、模具检测以及工程反求应用中取得良好的效果。72展望单面法是所有融合方法中效率最高的，如果能对其融合后的表面的光滑度进行改进，那么单面法能很好的应用于检测与逆向设计中。而聚类法的融合效率也有进一步改进的空间，如果其融合速率能达到单面法的速率，那么将是一种理想的融合方法。目前的研究主要是针对研究所自主研发的面扫描系统获取的点云数据。这种点云是按扫描线有序排列的，而用其他一些扫描仪器获取的点云数据并不一定有扫描线信息，因此本文的算法并不是通用的算法。而实际应用中点云数据的格式往往变化不定，但不论哪种数据格式，都会包含最基本的3D坐标即XYZ值。所以点云融合应该能处理只包含XYZ信息的点云，这样算法将可以处理各种扫描仪器获取得到的点云数据。EQUATIONCHAPTERNEXTSECTION1致谢首先，我要感谢我的导师梁晋副教授，正是在他的悉心指导和严格要求下本文才得以完成，其中梁老师对论文的总体方向进行了严格的把握，就论文的写作以及本课题的关键技术、方案设计等诸多方面进行了细致耐心的指导。三年来，梁老师从学习、生活和科研工作上给予了作者无私的关怀和帮助，使作者受益匪浅。梁老师严谨求实、谦逊博学的作风将继续鞭策着作者奋发上进。在此，再次向梁老师致以衷心的感谢另外，感谢信息机电研究所的师兄弟们以及一直关心我的亲朋好友，是他们陪伴我度过硕士的三年珍贵时光。最后，我要特别感谢家人对作者最深切的关怀和莫大的支持，他们是我坚持不懈地投入学业的精神支柱。参考文献1SAZERNIKOV,AFISCHEREMERGINGNONCONTACT3DMEASUREMENTTECHNOLOGIESFORSHAPERETRIEVALANDPROCESSINGJVIRTUALANDPHYSICALPROTOTYPING,2008,3285912KSAITO,TMIYOSHINONCONTACT3DDIGITIZINGANDMACHININGSYSTEMFORFREEFORMSURFACEJANNALSOFTHECIRP,1991,404834863周伦彬逆向非接触测量技术浅析J中国测试技术,2005,31525274邵伟,杨军良,郭俊杰,方海燕非接触式测量机器人J仪器仪表学报,2003,2441711725JMHUNTLEYOPTICALSHAPEMEASUREMENTTECHNOLOGYPAST,PRESENTANDFUTUREAPROCEEDINGSOFSPIEC,2000,407611621736PSHUANGA,SZHANGB3DOPTICALMEASUREMENTUSINGPHASESHIFTINGBASEDMETHODSAPROCEEDINGSOFSPIEC,2005,600012127NDAPUZZOOVERVIEWOF3DSURFACEDIGITIZATIONTECHNOLOGIESINEUROPEAPROCEEDINGSOFSPIEC,2006,605611138YDLI，PHGU，FREEFORMSURFACEINSPECTIONTECHNIQUESSTATEOFTHEARTREVIEWJCOMPUTERAIDEDDESIGN，2004,36139514179SSON，HPARK，KHLEE，AUTOMATEDLASERSCANNINGSYSTEMFORREVERSEENGINEERINGANDINSPECTIONJMACHINETOOLSANDMANUFACTORY，2002,4288989710KWOLF,DROLLER,DSCHAFERANAPPROACHTOCOMPUTERAIDEDQUALITYCONTROLBASEDON3DCOORDINATEMETROLOGYAMATERIALPROCESSINGTECHNOLOGYC,2000,1079611011GTURK,MLEVOYZIPPEREDPOLYGONMESHESFROMRANGIMAGESAPROCEEDINGSOFSIGGRAPHC,1994,31131812MGOPI,SKRISHNAN,CSILVASURFACERECONSTRUCTIONBASEDONLOWERDIMENSIONALLOCALIZEDDELAUNAYTRIANGULATIONAPROCEEDINGSOFEUROGRAPHICSC,2000,19346747813DFWATSONCOMPUTINGTHENDIMENSIONALDELAUNAYTESSELLATIONWITHAPPLICATIONTOVORONOIPOLYTOPESJTHECOMPUTERJOURNAL,1981,24216717214姜寿山,杨海成,候增选用空间形状优化标准完成散乱数据的三角剖分J计算机辅助设计与图形学报,1995,7424124915吕震反求工程CAD建模中的特征技术研究D杭州浙江大学,200316FBERNARDINI,JMITTLEMAN,HRUSHMEIER,ETALTHEBALLPIVOTINGALGORITHMFORSURFACERECONSTRUCTIONJIEEETRANSVISUALCOMPUTGRAPH1999,534935917BCURLESS,MLEVOYAVOLUMETRICMETHODFORBUILDINGCOMPLEXMODELSFROMRANGEIMAGESAPROCEEDINGSOFSIGGRAPHC,1996,43844618CROCCHINI,PCIGNONI,FGANONELLI,ETALTHEMARCHINGINTERSECTIONSALGORITHMFORMERGINGRANGEIMAGESJVISUALCOMPUT,2004,14916419WELORENSEN,HECLINEMARCHINGCUBESAHIGHRESOLUTION3DSURFACECONSTRUCTIONALGORITHMAPROCEEDINGSOFSIGGRAPHC,1987,16316920HHILTON,AJSTODDART,JILLINGWORTHETALMARCHINGTRIANGLESRANGEIMAGEFUSIONFORCOMPLEXOBJECTMODELLINGAPROCEEDINGSOFICIPC,1996,38138421YHLIU,HZHOUACCURATEINTEGRATIONOFMULTIVIEWRANGEIMAGESUSINGKMEANSCLUSTERINGJSCIENCEDIRECT,2008,15217522CXFENGINTERNETBASEDREVERSEENGINEERINGJTHEINTERNATIONALJOURNALOFADVANCEDMANUFACTURINGTECHNOLOGY,2003,21213814423吕国刚,谌永祥,李永桥反求工程测量技术简述J机械研究与应用,2006,1947824KSUNGADDAOCTREETRAVERSALALGORITHMFORRAYTRACINGAEUROGRAPHICS91PROCEEDINGSOFTHEEUROPEANCOMPUTERGRAPHICSCONFERENCEANDEXHIBITIONC,FHPOSTANDWBARTHEDS,PP7385,NORTHHOLLAND,199125刘春明,方漪寻找三维散乱数据点拓扑结构的一种算法J青岛大学学报,2003,183202426HHOPPEPROGRESSIVEMESHESAPROCEEDINGSOFSIGGRAPHCOMPUTERGRAPHICSC,NEWYORKACM,1996,9910827MECK,TDEROSE,TDUCHAMP,ETALMULTIRESOLUTIONANALYSISOFARBITRARYMESHESAPROCEEDINGSOFSIGGRAPHCOMPUTERGRAPHICSCNEWYORKACM,1995,829028JLBENTLEYMULTIDIMENSIONALBINARYSEARCHTREESUSEDFORASSOCIATIVEDSEARCHINGACOMMUNICATIONSOFTHEACMC,197518950951729WANDREWMOOREANINTRODUCTORYTUTORIALONKDTREESRTECHNICALREPORT,COMPUTERLABORATORY,UNIVERSITYOFCAMBRIDGE,199130RSWRIGHT,BLIPCHAKOPENGLSUPERBIBLE3RDEDITIONMSAMSPUBLISHING,200531YDLI,PHGUFREEFORMSURFACEINSPECTIONTECHNIQUESSTATEOFTHEARTREVIEWJCOMPUTERAIDEDDESIGN2004,361395141732SSON,HPARK,KHLEE,AUTOMATEDLASERSCANNINGSYSTEMFORREVERSEENGINEERINGANDINSPECTIONJMACHINETOOLSANDMANUFACTORY2002,4288989733KWOLF,DROLLER,DSCHAFERANAPPROACHTOCOMPUTERAIDEDQUALITYCONTROLBASEDON3DCOORDINATEMETROLOGYJ,MATERIALPROCESSINGTECHNOLOGY2000,1079611034BJBROWN,RSZYMONNONRIGIDGLOBALALIGNMENTUSINGTHINPLATESPLINESASKESTCHESOFACMSIGGRAPH2005C35MITRANJ,GELFANDN,POTTMANNH,ETALREGISTOFPOINTCLOUDDATAFROMAGEOMETRICOPTPERSPECTIVEAGEOMETRYPROCESSINGC,2004233236RSZYMON,BBROWN,MKAZHAN3DSCANMATCHINGANDREGISTRATIONCICCV2005SHORTCOURSE37TVRADY,RMARTIN,JCOXREVERSEENGINEERINGOFGEOMETRICMODELSANINTRODUCTIONJCOMPUTERAIDEDDESIGN,1997,29425526838钱锦锋逆向工程中的点云处理D杭州浙江大学，200539MGOPI,SKRISHNAN,AFASTANDEFFICIENTPROJECTIONBASEDAPPROACHF