丁超_基于局部投影的点云去噪算法研究 27页

'题目基于局部投影的点云去噪算法研究英文DenoisingPointCloudsbasedon题目LocalProjectionOperators院系数学系姓名丁超学号PB09206064导师刘利刚日期2013年5月 中国科学技术大学本科毕业论文目录摘要........................................................................................................................2Abstract..................................................................................................................3第一章绪论.......................................................................................................41.1引言....................................................................................................41.2相关工作概述........................................................................................51.3本文工作................................................................................................8第二章局部最优投影.......................................................................................92.1算法描述................................................................................................92.2求解步骤..............................................................................................102.3算法性能..............................................................................................11第三章加权局部最优投影.............................................................................173.1算法描述..............................................................................................173.2求解步骤..............................................................................................183.3算法性能..............................................................................................19第四章总结与展望.........................................................................................234.1总结......................................................................................................234.2展望......................................................................................................23参考文献..............................................................................................................24致谢......................................................................................................................261 中国科学技术大学本科毕业论文摘要随着3D技术的飞速发展，各个行业对高精度3D模型的需求越来越高。纯手工建模因为效率低下，价格高昂而逐步被淘汰。恰逢3D扫描技术的迅猛发展，快速，廉价的3D点云数据的获取变得可能。针对点云这一新型数据的处理方法由此产生。而本文着重关注点云处理的第一步，点云去噪。点云去噪在过去的二十年里积累了大量优秀的方法。本文的第一部分就介绍了一类，基于构造局部平面的方法。这类方法首先用局部平面拟合点云的局部，然后将得到的拟合平面拼接成整体模型。当点云数据比较复杂时，这类方法会得到奇异的结果。点云去噪的过程也可以理解成：寻找一组点云，使其很好的拟合原始点云。为了拟合质量，同时要求该点云的点分布也较为均匀。本文在第二部分介绍的方法新方法——局部最优投影法就是将这两点划归成能量函数，通过优化能量函数去噪。上述方法对初始点云分布稀疏程度依赖很高。我们在第三部分介绍了改进方法——加权局部最优投影法。它通过对每个采样点定义密度权重的方式来达到均匀点云分布的目的。本文比较了这两种方法的优劣。关键词：点云去噪局部最优投影2 中国科学技术大学本科毕业论文AbstractWiththerapiddevelopmentof3Dtechnology,theneedsofvariousindustriesonthehighaccuracyofthe3Dmodelisbecomesincreasinglyhigher.Manualmodelingisgraduallyeliminatedduetopoorefficiencyandhighprices.Coincideswiththerapiddevelopmentof3Dscanningtechnology,cheapaccessto3Dpointcloudsdatabecomespossible.Themethodforthisnewdataformhasbeenborn.Thispapermainlyfocusesonthefirststepofpointcloudprocessing,pointcloudsdenoising.Therehavebeenlargenumbersofgoodmethodsfordenoisinginthepasttwentyyears.Thefirstpartofthispaperintroducesakindofmethodbasedonlocalplane.Thismethodfirstusesthelocalplanefittingpointclouds,andobtainsawholemodelwithsmallplane.Whenthepointcloudsdataiscomplicated,thismethodwillfail.Theprocessofpointcloudsdenoisingcanalsobeunderstoodas:lookingforasetofpointscloudswhichfitstheoriginalpointcloudswell.Itmustbeuniformforgooddistributionquality.Basedonaboveweintroducethelocaloptimalprojectionmethodinthesecondsection.Itusesenergyfunctiontosimulatetheprocess.Themethodishighlydependentontheinitialpointcloudssparsedegree.Weintroduceanimprovedmethod--weightedlocallyoptimalprojectionmethodinthethirdpart.Itachievesuniformpointcloudsdistributionbasedonthedefinitionofeachsamplingpointdensity.Thispaperputsgreatemphasisonthecomparisonbetweenthetwomethods.Keyword:denoisingpointcloudslocaloptimalprojection3 中国科学技术大学本科毕业论文第一章绪论1.1引言计算机图形学作为一个年轻的学科在近20年得到了突飞猛进的发展，在可见的未来，社会对该学科的需求依然十分巨大。图形学借助计算机作为研究工具，第一步就需要将研究的模型数字化。传统的方法是为模型建立三角网格，用网格去表达模型。但是近些年，由于人们对于网格的精细程度需求的增加，恰逢三维扫描技术的成熟，人们可以较为方便快捷的获得大数据量的精细点云信息。点云因为数据结构简单，方便存取，蕴含了大量信息而越来越受到大家的关注。但也因为数据量巨大给处理带来挑战。迎接这种挑战，以点云为数据对象方应运而生，并大量使用在医疗可视化，自然人机交互，文物保护等方方面面。点云数据的获取有两种方式。一种是通过人工构造的方式。可以用一个具有面信息的模型作为输入，通过类似Geomagic的软件，得到带有噪声的模型。另一种是通过激光扫描仪对实体模型进行扫描，获取相应的点云数据。第一种方法是用计算机模拟第二种方法，效果和速度都不及第二种方法，所以实际中大多采取第二种方法获取点云数据。获取的点云数据一般都是含有噪声的。噪声的产生是不可避免的，成因也很复杂，我们简单的分析，大致有三个原因。其一，测量使用的物理设备存在误差，由于设备的分辨率，相机精度，震动等原因，测量得到的点云信息是不准确的。其二，测量使用的物理模型也存在误差。我们假设物理模型是光滑的。但是，实际中是不存在绝对光滑的物体，这里的光滑指的是二阶可导曲面。物理模型表面必定存在凹凸，纹路等问题。其三，测量系统是存在误差的。首先，测量时，采集设备和物理模型不可能绝对静止，它们的位置变化会带来误差。其次，要获得整体的模型数据，至少在不同位置获得多帧数据。不论是位置变化所需的注册算法，还是多帧数据必定存在的系统误差，都会带来误差。再次，用激光采集的方法得到的数据，在模型表4 中国科学技术大学本科毕业论文面有自遮挡的情况下，是不能采集到被遮挡部分的数据的。这样，采集到的模型就有大片的缺失，可能改变其拓扑性质。所以，将噪声去除对于点云处理算法至关重要。1.2相关工作概述1.2.1局部平面法第一种方法是对模型表面进行合理的假设，例如假设模型是光滑的，然后将这种性质局部化。然后对每个采样点P，取其点云邻域，用采样点P及其邻域点去拟合带有假设性质的面。最后，从这些离散的拟合面出发，拼接处一个符合假设的整体的模型。其中最常见的假设是，采样点采样自一个处处光滑的表面，不含有尖锐特征。因此表面上的点都可以用它周围的点很好的拟合。对于每个采样点P，及其点云邻域构成了一个局部平面。问题就转化为如何拟合局部平面，以及如何拼接缝合这些离散局部平面。而关于拟合局部平面，根据不同的最佳平面意义有着不同的选取方法。图1-1典型PCA去噪算法5 中国科学技术大学本科毕业论文最早提出有效算法的Hoppe等[2]，这也是目前使用最为广泛的方法。如图1-1，基于上述假设，他定义了最优拟合平面是法向量满足kPnd(,)npargmind()2(1)i(,)ndi1的平面。算法不仅在点云去噪方面高效和稳定，而且可以在无任何其他信息的情况下迅速求得每个点的法向量，从而将点云去噪问题同法向量问题联系在一起。该方法受到广泛使用，对它的改进也接踵而至。其中比较好的改进是Gross[17]。他为采样点P的每个邻域点，根据其与P点的距离，附加了一个高斯权重，k2Pnd(,)npargmindpp()()ii(2)(,)ndi1这样，与P点距离较近的点权重较大，对拟合平面影响大，与P点距离较远的点权重较小，对拟合平面的影响小。这不仅符合人们的常识，而且实际效果也十分好。还有很重要的一点是，由于高斯项()pp的存在，它的衰减速度很i快，对于较远的点()pp的值很小。也就是说，对于较远的点p，它对P的ii贡献很小，可以忽略。这就起到了一个局部化的作用不需要再额外去求K邻域点。图1-2典型MLS去噪算法源于[3]6 中国科学技术大学本科毕业论文Pauly等[3]，类似的提出了基于MLS（MoveLeastSquare）最小二乘移动方法，见图1-2。他的方法在使用高斯权重的时候，并非直接使用邻域点p与采样i0点P的距离，而是先将邻域点p投影到拟合平面上，得到p，然后使用投影点ii0p与采样点P的距离作为高斯函数的参数，即ik20Pnd(,)npargmindpp()()ii(3)(,)ndi1可以使得拟合平面在角度上更可信。1.2.2局部平面法的缺点从信号处理的角度说，局部平面法的原理是低通滤波。它利用噪声的高频性质，将高频信号滤掉，达到去噪的目的。但是，高频信号中还包括点云的尖锐表面等细节特征，这些特征都会被当做噪声被滤掉。(a)厚点云(b)不一致(c)近表面(d)薄表面图1-3复杂点云情况源于[21]除此以外，局部平面对于特殊的点云处理的结果也会产生歧义。1、厚表面。上述的法平面的方法，需要点云较薄，这样，K个邻接点就能反映出改点的法向量信息，如图1-3中（a）所示，如果表面太厚，那么选取最近的K个点的时候，就选取的是加厚的多层表面，这样计算出来的法平面就会偏向法向量的方向，而不是法向量的垂直方向。2、不一致。上述的法平面的方法，需要点云在表面的各个方向分布相对均匀。这样加权平均后，才能反映应有的法向量方向。如图1-3中（b）所示，如果点云具有各向异性，在表面的某个方向的分布较密集，那么法向量就会偏向这个方向，导致法平面不准确。3、近表面。上述方法要求周围的K个邻接点是局部连通的，也就是说，P点连通K个邻接点是原模型的片元，如图1-3中（C）所示如果有两个7 中国科学技术大学本科毕业论文面很接近，那么在这个近表面附近的点，它的K领域可能在另外的一个面上，这样求的的法平面必然不准确。4、薄表面。在薄表面附近的点中，只有少量的点对法向量有贡献。对于固定了K，薄表面附近的K个邻接点中含有大量的对法向量没有贡献的点，如图1-3中（d）所示，导致薄表面附近的点的局部平面不准确。1.3本文工作本文介绍了一类关于点云去噪的新算法——局部最优投影算法。3它将去噪的过程看作：将目标点云QqR{}投影到原始点云iiI3P{}pR上，使得投影得到的点云Q不含有噪声。那么，考量投影好坏的jjJ判定标准很自然的是原始点云P同结果点云Q之间的拟合程度。但与此同时，我们也要考虑到点云Q的质量，即Q分布要尽量均匀，这样利于下一步的处理。本文重点测试了局部最优投影算法的性能，比较了该算法同其改进算法的优劣。并提出来改进方向。8 中国科学技术大学本科毕业论文第二章局部最优投影2.1算法描述局部最优投影（LocalOptimalProjection）——LOP，是一种基于投影的去噪算法。它的具体算法如下：3(0)(0)3对原始点云PpR{}，LOP以任意点集X{}xR开始，将jjJiiI(0)X投影到P上，进行能量方程的优化(1)ii()(4)XGX()其中GC()argmin{(,,)EXPCEXC(,)}(5)12Xx{}iiIEXPC1(,,)xipj(cipj)(6)iIjJEXC2"(,)""x(c)cciiiii(7)iI"{"}iIirh22/(/4)1()re,()r(8)33r3该迭代过程的不动点QGQ()，QqR{}就是所要求的目标点云。iiI下面仔细分析能量函数GC()argmin{(,,)EXPCEXC(,)}。12Xx{}iiIEXPC(,,)项表示的能量是目标点云Q同初始点云P之间的拟合程度。仔细1考量E的能量公式，可以看到，这里的能量是将目标点云中的每个点都与初始点1云的每个点的L1范数的高斯加权和计算一遍。可以看作是考量目标点云中每个点与初始点云的拟合程度。但是由于高斯范数的存在，除了目标点的邻接点以外的点，其高斯权重很低，可以忽略。所以，E项其实是表示目标点云Q中每个点1与其周围局部的初始点云P的拟合程度。这再一次说明是个局部算法。9 中国科学技术大学本科毕业论文EXC(,)项表示的能量是目标点云Q之间的斥力。我们目标中的点云应当是2均匀的分布在初始点云P形成的空间中。那么E就是保证点云分布较为均匀。考2察E的公式，对每个目标点qQ，求对于其他不同点的距离的高斯加权和。类2i似与E，由于高斯权重的存在，实际上求和项中只有q的邻接点起作用。我们可1i以把E理解为对于过近点的罚项，如果有两个点X，Y距离很近，那么就会导致2E的能量很大，E的存在可以有效的避免这种情况的存在。22在EXC(,)中，有个重要的参数。E，E分别考虑的是目标点云和初始2i"12点云的拟合程度以及目标点云分布均匀程度。如果单独考虑E，E。那么我们12得到的点云应当是分布不均匀的点或者离初始点云非常远的点。这都不是我们想要的。那么，要这两种能量以一定的比例进行配比，既考虑点云分布的与原始点云的拟合，又防止点云分布不均匀。我们的做法是在E的前面加上一个参数，通2过调整参数，得到不同质量的点云。参数设置的越小，点云均匀性越差，参数设置的越大，点云拟合程度越差。2.2求解步骤考察目标能量函数，能量函数的两项都带有高斯项且E中关于目标点云是2一个二次函数。对于这样的非线性系统，很难给出显示解，我们需要采用优化能量函数的方法来求解。我们采用的是迭代的方法求解。(1)(1)Xx{}iiI(0)pjj()pix"(1)jJxi"(0)()pxji"jJ()(p)xx()kxkk()()(9)ii"k"()k()jii""i,()(9)xxjjii()kkk()()"pxxxrjii""ii"i"(kkk1)()()jixipj""iixxii""()jJjiiIi{"}jJiIi{"}(0)考虑(5)式，我们首先在原始点云中选取X的大小的点作为初始的目标点云，然后将原来E中的X替换成上一步的X值，这样能量函数就得到了简化。我们2可以得到如（9）所示的显示解，逐步迭代就可得到所需答案。10 中国科学技术大学本科毕业论文最后得到的稳定点就是要求的目标点云。唯一需要证明的是迭代的收敛性。事实上上述迭代方法关于h具有二阶收敛性。文献[1]中给出了详细的证明，这里就不再赘述。2.3算法性能2.3.1去噪效果(a)原始点云(b)MLS去噪(c)LOP去噪图2-1LOP算法同传统算法去噪效果的比较源于[1]本文在第一部分提到：面对复杂的点云情况，传统的基于局部平面的方法效果不理想。如图2-1所示，MLS法不能很好的规避外点对模型的影响，去噪的结果不好。而LOP方法可以很好的将少量的外点从初始点云中去除。可见LOP在面对复杂点云时，性能优于传统方法。但是，类似于传统方法，LOP算法的本质也是低通滤波。它将高频噪声去除的同时，也将同属高频的细节信息一并滤去。所以，LOP也会在去噪的同时，丢失模型的细节信息。2.3.2运行效率22rh/(/4)LOP是一种局部算法。由于高斯项()re的存在，在和式中，距离P点较远的点都可以忽略，实际编程中也是设立一个阈值，当r时，忽略该点。3并且在通过对初始点云P{}pR建立查找树，我们可以迅速的找到某采样jjJ点P的邻接点。经测试，对于10000级别的点云，迭代一步的时间小于0.5s。在11 中国科学技术大学本科毕业论文单步速度很快的同时，LOP的收敛速度也很快。即使输入很差（输入没有很均匀的分布在模型上），一般5-10步迭代就可以得到很好地结果。2.3.3鲁棒性(0)(0)3LOP的对初始输入点云XxR{}的依赖性不大。对于差的输入（例iiI(0)(0)3如XxR{}分布在点云的局部），LOP算法最后也能成功的将点云发散iiI到整个模型表面。实验表明，差的输入只会增加少数的迭代步骤，最终也会将点云X分布到P表面。从这个意义上说，LOP在速度上也是鲁棒的。(a)初始点云(b)10步迭代(c)40步迭代(d)160步迭代图2-2LOP算法对初始输入的鲁棒性上图是我们做的实验，对于均匀环状点云，我们以局部点作为输入，分别迭代10,40,160步。最后点云会均匀分布在模型表面。12 中国科学技术大学本科毕业论文2.3.4参数依赖在LOP算法中，最关键的两个参数是h,。其中，h决定了高斯权重的影响范围，h越大，高斯函数衰减越慢，对和式起作用的点的半径越大，h越小，高斯函数衰减越快，只有少数点对和式其作用。h和邻域正相关。(a)0,25h(b)1h(c)4hh为默认邻域大小图2-3LOP算法对参数h的依赖上图是对同一兔子头模型在不同h下迭代50步的结果。过小的h使得点分布不均匀，过大的h使得算法会崩溃。13 中国科学技术大学本科毕业论文参数决定了拟合能量E同分布能量E的配比关系。越大，分布能量E122所占的比重越大，LOP算法处理后的点云分布的越均匀，但是对原始点云3PpR{}拟合越差。越小，分布能量E所占的比重越大，LOP算法处理jjJ13后的点云对原始点云PpR{}拟合越好，但分布可能不均匀。所以合适的jjJ参数设定对最后的结果至关重要。一般h取作一个全局的经验值，取0~0.5之间的任意值。对于不同模型，人工尝试微调，达到一个好的结果。u的取值(a)0.0(b)0.5(c)1.0图2-4LOP算法对参数u的依赖14 中国科学技术大学本科毕业论文上图是对同一兔子头模型在不同下迭代50步的结果。过小的使得点分布不均匀，过大的使得模型本身的形状信息丢失。2.3.5收敛性二阶收敛性无法保证。前面虽然证明了LOP有二阶收敛性，但是其收敛条件是h0。但是实际操作中，h取的是一个不为0的定值，且h不能太小。若h太小，那么高斯权值函数衰减太快，邻域内不含点或含少量点，算法会崩溃。实际中，我们观察到的情况是：LOP算法在有限步迭代后，点云会产生微小震荡。在数值上，几乎所有点都不收敛，但变化都很小。我们将每步结果都可视化后发现，在视觉上，巨大部分的点都稳定，只有少部分点局部震荡。2.3.6点云密度依赖(a)初始点云(b)LOP算法去噪后点云图2-5LOP算法对初始点云疏密的依赖15 中国科学技术大学本科毕业论文对点云的疏密程度依赖很大。在LOP能量函数中，拟合能量E表示的是目1()tt()33标点云XxR{}同原始点云P{}pR的拟合程度。这种程度是通iiIjjJ过点与点的作用加权求和而来。而局部邻域的大小是一个全局值h。所以，目标点云拟合的是原始点云的位置，那么当原始点云不能很好的反映模型的表面信息时，这种拟合就是不可信的。最直接的影响就是，当原始点云疏密程度不一致的时候，LOP处理后的点云也疏密不一致。这显然不是我们想看到的。16 中国科学技术大学本科毕业论文第三章加权局部最优投影3.1算法描述3.1.1算法思想3在第二章的末尾我们提到，LOP算法对初始点云PpR{}中采样点jjJ3p的分布有很强的依赖性。也就是说，处理后的点云Q{}qR的分布在初jiiI3始点云PpR{}所处的空间内，且在Pp{}分布密集的地方，jjJjjJQq{}的分布也相对密集。反之，在分布Pp{}稀疏的地方，Qq{}iiIjjJiiI的分布也相对稀疏。这是因为，LOP中用来表示目标点云Qq{}同初始点云Pp{}拟合iiIjjJ程度的项——能量函数GC()中的第一项E，具体的表达式是对Qq{}，1iiIPp{}两两加权距离求和。这样，原始点云Pp{}中点分布密集的部分jjJjjJ对于目标点云Qq{}的吸引力就大。所以当初始点云采样不均匀时，LOP处iiI理结果也会不均匀。一个朴素的想法是：立足于LOP的算法，在点云分布密集的地方减少能量的贡献，在点云稀疏的地方加大能量的贡献。这样就相当我们获得了一个简单采样的均匀初始点云。3.1.2算法步骤加权局部最优投影——WLOP，就是采用了上述的思想。对于任意初始点云中的点pPj，WLOP定义了全局密度，vpjjjp1()"。同理，对于任jJ"{}j()tt()kk意过程点云中的点xXi，WLOP定义了全局密度wi1(ii")，其中iIi"{}kkkxx。iii""i同时，WLOP方法改进了LOP方法中的罚项。由于高斯权重的存在，负三阶的罚函数会导致罚能量衰减迅速，较远的点对于中心的影响太小。而我们对LOP的改进从某种意义上说就是疏远所有点，那么有必要加大罚函数的值。我们将其设为负一阶。17 中国科学技术大学本科毕业论文具体算法如下：3(0)(0)3对原始点云PpR{}，WLOP以任意点集XxR{}开始，将jjJiiI(0)X投影到P上，进行能量方程的优化XGX(1)ii()()(10)其中QGQ()GC()EXPCargmin{(,,)EXC(,)}(11)XxiI{}i12EXPC1(,,)x(p)c(11)pvijijj(12)iIjJkEXC2""(,)"x(c)(ccw)iiiiii(13)iI"{"}iIi22()re,()rrrh/(/4)(14)3该迭代过程的不动点QGQ()，QqR{}就是所要求的目标点云。iiI3.2求解步骤考察目标能量函数，类似于LOP，能量函数的两项都带有高斯项且E中关于2目标点云是一个二次函数。对于这样的非线性系统，很难给出显示解，我们需要采用优化能量函数的方法来求解。我们采用的是迭代的方法求解。(0)我们首先在原始点云中选取X的大小的点作为初始的目标点云，然后将原来E中的X替换成上一步的X值，这样能量函数就得到了简化。我们可以针对2这个式子求出显示解。我们逐步迭代，(1)(1)Xx{}iiIkkk/vwkk1ijji""iixpijkii"kk(12)jJij/vwjiIi"{}i""ii(15)jJiIi"{}kkk()()"()kkijii""iiwhereijkkandii"ijii"18 中国科学技术大学本科毕业论文最后得到的稳定点就是要求的目标点云。为了保证算法的可行性，需要证明这个迭代是收敛的。对于每一步迭代，WLOP都只在LOP的表达式中加入常数项，不影响其收敛性。所以由LOP的收敛性可得到WLOP的收敛性。3.3算法性能3.3.1去噪效果在2D情况下，有一类以散点的疏密传递信息的图——点阵图。我们说的去噪方法适用于此类图。如前面所述，LOP会根据原始点云的分布情况重新布点，WLOP则会将点平均散布到除去空洞外的所有部分。图3-12D下LOP算法同WLOP算法的比较源于[21]在3D情况下，WLOP能在一定程度上将点云均匀的散布到整个模型表面。但是，当点云的稀疏程度差距过大时，WLOP不仅无法产生点云分布均匀化的效果，反而会使得密集部分的点云更加密集，并且同稀疏部分的间隔变大。从能量函数的表达式中可以找到原因。由于高斯密度函数的存在，目标点云中的每()t个点X只跟自己的邻接点相关。那么，对于高密度区域内部的点而言，WLOP的i权重几乎处处相同，不产生任何影响。所以，权重只影响点云密度稀疏相间的部分。对于高密度区域的边界点而言，如果稀疏程度差距过大，边界点的邻接点中，高密度区域的内点数量远大于稀疏部分，WLOP的权重无法抵消数量优势，所以高密度点对边界点的吸引力大，最终造成密集部分更加密集的效果。19 中国科学技术大学本科毕业论文也就是说，WLOP的均匀化点云分布的能力是有阈值的。如果局部内闭区域与其邻接区域点云分布密度差距过大，就起不到均匀点云分布的作用。但是对于大部分实际噪声模型，一般不会超过阈值，所以WLOP较为鲁棒。(a)初始点云(b)LOP去噪点云(c)WLOP去噪点云图3-2LOP算法同WLOP算法对初始点云疏密敏感程度的比较20 中国科学技术大学本科毕业论文与此同时，WLOP与LOP不同的罚函数也起到了作用。罚函数的选取都是启发式的。LOP的罚函数在实际使用过程中，对于较远的点产生的斥力较小，这样不能很好的均匀化处理后的点云。为了加大这种斥力，我们将LOP中的罚函数1()r改进为()rr。33r3.3.2运行效率通过对比WLOP与LOP的具体迭代步骤可以发现，WLOP相对于LOP，在算法初始化中需要计算关于初始点云Pp{}数量级的密度值。在单步迭代中需jjJ()tt()要多计算关于目标点云Xx{}数量级的密度值。iiI所以运行效率的对比中，对于同样的参数设定，同样规模的输入输出，WLOP比LOP耗费的时间长。且当迭代步骤足够多时，WLOP耗时比LOP多的原因主要()tt()来自于目标点云Xx{}数量级的密度值的计算。iiI2.3.3鲁棒性如图3-2所示，从对输入的鲁棒性的角度说，如同LOP，对于差的点云输入(0)(0)(0)(0)Xx{}，WLOP可以在有限的步骤内将点云Xx{}通过迭代，逐步iiIiiI传播到整个初始点云Pp{}的表面。jjJ从去噪的鲁棒性的角度说，WLOP只能处理常规点云。而对于点云中含有成片的密度异常点集的情况，WLOP不仅不会起到均匀点云分布的情况，反而会使得点云分布密度两级分化。2.3.4参数依赖类似于LOP，WLOP的处理结果强依赖于h,参数的选取。参数h决定了WLOP算法中邻域的选取范围。h越大，对每个采样点p的邻j域越大，去噪后的模型越光滑，细节信息保持越差；h越小，对每个采样点p的j邻域越小，细节信息保持越好，但是同时可能产生奇异解。且当h过小时会失去去噪效果，甚至算法崩溃。21 中国科学技术大学本科毕业论文参数决定了拟合能量E同分布能量E的配比关系。越大，分布能量E122所占的比重越大，LOP算法处理后的点云分布的越均匀，但是对原始点云3PpR{}拟合越差。越小，分布能量E所占的比重越大，LOP算法处理jjJ13后的点云对原始点云PpR{}拟合越好，但分布可能不均匀。jjJ22 中国科学技术大学本科毕业论文第四章总结与展望4.1总结点云去噪是点云处理领域最基本的问题，多年来积累了大量优秀的成果。但是，过去的方法的核心都是在点云的局部去拟合法平面，然后将得到的一系列法平面拼接成整体模型。这类方法对于均匀采样的点云数据处理效果很好，但是对于复杂的点云情况就无法取得令人满意的结果。对此，本文主要介绍了局部最优投影算法。该方法将去噪过程划归为向原始点云投影新点的过程，它用两个能量函数分别约束投影点与原始点云的拟合程度，以及投影点的均匀程度。由于投影法没有利用局部平面的性质，所以对于复杂的点云亦能给出较好的结果。但是该方法对于初始点云的疏密程度依赖很大。本文随后介绍了针对于此的改进方法，加权局部最优投影法。它将原始点云和投影点云中的每点赋以密度值，用此密度来归一化点云密度。这样可以使得去噪后的点云拥有良好的一致性。但是，这种改进的方法对于稀疏程度过大的点云会失去作用。更重要的是，这类基于投影的去噪方法有两个关键参数h,是靠人工选择的。而这两个参数又是去噪效果的关键。实际操作中常常要多次调整才能得到较好的结果，所以，自适应的h,厄待解决。4.2展望1、提出自适应的h取值方法。h的选取应当充分考虑到点云局部密度以及点云的曲率变化。所以在原有的全局h取值的基础上，将局部点云的法向量的信息加入进来，在法向量变化快的地方减小h的取值，在法向量变化慢的地方加大h的取值。2、提出自适应的取值方法。的取值应当在考虑目标点云稀疏程度的同时，考虑到对原点云的变形程度。且的取值也可以局部化。可以局部比较目标点同原始点的变形程度，然后根据变形程度的大小选取。23 中国科学技术大学本科毕业论文参考文献[01]Lipman,Y.,Cohen-Or,D.,Levin,D.,&Tal-Ezer,H.(2007,August).Parameterization-freeprojectionforgeometryreconstruction.InACMTransactionsonGraphics(TOG)(Vol.26,No.3,p.22).ACM.[02]Hoppe,H.,DeRose,T.,Duchamp,T.,McDonald,J.,&Stuetzle,W.(1992).Surfacereconstructionfromunorganizedpoints(Vol.26,No.2,pp.71-78).ACM.[03]Pauly,M.,Keiser,R.,Kobbelt,L.P.,&Gross,M.(2003).Shapemodelingwithpoint-sampledgeometry.ACMTransactionsonGraphics(TOG),22(3),641-650.[04]Alexa,M.,Behr,J.,Cohen-Or,D.,Fleishman,S.,Levin,D.,&Silva,C.T.(2001,October).Pointsetsurfaces.InProceedingsoftheconferenceonVisualization"01(pp.21-28).IEEEComputerSociety.[05]Amenta,N.,&Kil,Y.J.(2004).Definingpoint-setsurfaces.ACMTransactionsonGraphics(TOG),23(3),264-270.[06]Amenta,N.,Bern,M.,&Kamvysselis,M.(1998,July).AnewVoronoi-basedsurfacereconstructionalgorithm.InProceedingsofthe25thannualconferenceonComputergraphicsandinteractivetechniques(pp.415-421).ACM.[07]Brown,B.M.(1983).Statisticalusesofthespatialmedian.JournaloftheRoyalStatisticalSociety.SeriesB(Methodological),25-30.[08]Carr,J.C.,Beatson,R.K.,Cherrie,J.B.,Mitchell,T.J.,Fright,W.R.,McCallum,B.C.,&Evans,T.R.(2001,August).Reconstructionandrepresentationof3Dobjectswithradialbasisfunctions.InProceedingsofthe28thannualconferenceonComputergraphicsandinteractivetechniques(pp.67-76).ACM.[09]Kazhdan,M.,Bolitho,M.,&Hoppe,H.(2006,June).Poissonsurfacereconstruction.InProceedingsofthefourthEurographicssymposiumonGeometryprocessing.[10]Levin,D.(2003).Mesh-independentsurfaceinterpolation.Geometricmodelingforscientificvisualization,3,37-49.[11]Ohtake,Y.,Belyaev,A.,Alexa,M.,Turk,G.,&Seidel,H.P.(2005,July).Multi-levelpartitionofunityimplicits.InACMSIGGRAPH2005Courses(p.173).ACM.[12]Pauly,M.,Gross,M.,&Kobbelt,L.P.(2002,November).Efficientsimplificationofpoint-sampledsurfaces.InVisualization,2002.VIS2002.IEEE(pp.163-170).IEEE.[13]Page,D.L.,Sun,Y.,Koschan,A.F.,Paik,J.,&Abidi,M.A.(2002).Normalvectorvoting:creasedetectionandcurvatureestimationonlarge,noisymeshes.GraphicalModels,64(3),199-229.[14]Ohtake,Y.,Belyaev,A.,Alexa,M.,Turk,G.,&Seidel,H.P.(2005,July).Multi-levelpartitionofunityimplicits.InACMSIGGRAPH2005Courses(p.173).ACM.[15]Nehab,D.,Rusinkiewicz,S.,Davis,J.,&Ramamoorthi,R.(2005,July).Efficientlycombiningpositionsandnormalsforprecise3Dgeometry.InACMTransactionsonGraphics(TOG)(Vol.24,No.3,pp.536-543).ACM.[16]Mitra,N.J.,&Nguyen,A.(2003,June).Estimatingsurfacenormalsinnoisypointclouddata.InProceedingsofthenineteenthannualsymposiumonComputationalgeometry(pp.322-328).ACM.24 中国科学技术大学本科毕业论文[17]GrossM,PfisterH.Point-basedgraphics[M]/TheMorganKaufmannSeriesinComputerGraphics.SanFrancisco:MorganKaufmannPublishersInc,2007[18]Ma,W.C.,Hawkins,T.,Peers,P.,Chabert,C.F.,Weiss,M.,&Debevec,P.(2007,June).Rapidacquisitionofspecularanddiffusenormalmapsfrompolarizedsphericalgradientillumination.InProceedingsofthe18thEurographicsconferenceonRenderingTechniques(pp.183-194).EurographicsAssociation.[19]Lehtinen,J.,Zwicker,M.,Turquin,E.,Kontkanen,J.,Durand,F.,Sillion,F.X.,&Aila,T.(2008,August).Ameshlesshierarchicalrepresentationforlighttransport.InACMTransactionsonGraphics(TOG)(Vol.27,No.3,p.37).ACM.[20]Dey,T.K.,&Sun,J.(2006).Normalandfeatureapproximationsfromnoisypointclouds.InFSTTCS2006:FoundationsofSoftwareTechnologyandTheoreticalComputerScience(pp.21-32).SpringerBerlinHeidelberg.[21]Huang,H.,Li,D.,Zhang,H.,Ascher,U.,&Cohen-Or,D.(2009,December).Consolidationofunorganizedpointcloudsforsurfacereconstruction.InACMTransactionsonGraphics(TOG)(Vol.28,No.5,p.176).ACM.25 中国科学技术大学本科毕业论文致谢光阴荏苒，岁月如梭，转眼大学四年的时光已经过去。回首这些岁月，有开心，有失落，有迷茫，有进取，但无论如何，对我来说都是非常有意义的四年。在这里我不仅要感谢学校的老师对我的殷切教导，悉心关怀。还要感谢同学们对我的帮助鼓励，我的成长离不开大家的帮扶助力。我特别要感谢我的导师刘利刚老师。在我最迷茫的大三，是他的一次讲座让我领略到计算机图形学的魅力，这之后，刘老师花费了很多宝贵的时间和心血，耐心的给予我训练和指导，把我从一个门外汉慢慢拉进了这门神奇的学科，也在这个过程中逐步的提升了自己的编程能力和分析问题的水平。在毕业论文的准备过程中，从选题、到每周的进度汇报、再到结题时的修改和意见，导师一直悉心指导，他认真负责、科学严谨的治学态度都将成为我未来科研道路上的鞭策动力。我还要感谢我的同窗好友单文，帮助我解决了许多实际的编程难题。并在与他的讨论中，也加深了对自己课题的认识程度。希望在以后同窗的日子里会有更多的合作和交流，可以互相学习。同时我还要感谢在实验室的另外六位同学，他们也都在我遇到诸多问题时给予了耐心的解答。最后，感谢答辩的专家、老师，凭借我浅显的知识，文中肯定还有很多问题和不足，还请你们包涵和赐教。二零一三年五月于科大26'