（计算机软件与理论专业论文）点云模型的光顺去噪研究.pdf

浙江大学硕士学位论文摘要 摘要 近几年来三维模型获取的软硬件技术正不断深入，人们可以通过多种数据采 样方法来获取现实物体的计算机表示，并对之进行预处理，加工，分析和应用。 这种通过逆向： 程来获取的三维数据主要包括c t 数据( 计算机断层成像) 、m r i 数据( 核磁共振成像) 以及三维非规则点模型和网格模型数据等。而本文主要研究 对象是用三维扫描仪获取的三维点模型，及其所涉及的光顺去噪问题。 在获取数据的过程中，因为人为的扰动或者扫描仪本身的缺陷使得生成三维 数据往往带有噪声，从而使所获得的测量数据与实物存在定的偏差。因此在对 实测三维数据进行相关数字几何处理和应用之前必须对其进行去噪光顺。通常， 光顺处理可以直接针对点数据，也可以针对经过网格化后的多边形数据。光顺的 目标是在剔除噪声重建光滑表而的同时，保持采样表面原有的拓扑特征和几何特 征小变，比如保证光顺过程中模型不收缩且无过光顺现象等。本文对点模型的去 嗓) 匕j i n 技术进行深入的研究，提出了些创新的算法。主要内容包括： 介绍了一些经典的三维离散数据模型的去噪光顺方法，着重分析了近年 来提出的新方法，总结归纳了这些方法的基本原理以及它们的优缺点， 结合作者在本领域的研究工作，对今后三维数据的去噪光顺的研究重点 作一些分析。 针对现有模型，进行人为噪声分析，提出r 一种实用噪声模型的高斯算 法，通过该算法可以产生各种情况f 的模型，能满足各种实验需求，从 而为研究创造了条件。 在三维m e a n s h i f l 过程的点模型去噪算法的基础上，提出了基于噪声度的 保特征保体积的去噪算法。主要考虑点具有的噪声度，通过噪声度来控 制点移动速度，保持模型的体积，通过速度差来加快m e a n s h i f l 过程寻找 到模式点，并进行自适应聚类和邻域的自适应选取，在进行去噪的同时 有效地保持了特征。 关键词点模型，去噪，光顺，滤波，特征保持，双边滤波器，噪声度，m e a n s h i f t 过程 浙江大学硕士学位论文 a b s 订a c t a b s t r a c t s o f t w a r ef o rp r o c e s s i n g3 dd a t a ，p e o p l em a yo b t a i nr a wd a t ar e p r e s e n t a t i o n so f r e a lo b j e c t sw i t hc o m p l e xs h a p ev i aav a r i e t yo fw a y s ，t h e na n a l y z ea n dp r o c e s st h e m 1 1 1 i sk i n dm e t h o do fa c q u i r i n ga n dp r o c e s s i n gd a t ai sc a l l e dr e v e r s ee n g i n e e r i n g ，a n d t h eo b t a i n e dd a t aa r em a i n l yc l a s s i e di n t oc td a t a ，m r id a t a ，a n di r r e g u l a r3 d p o i n t - b a s e dd a t a d u et oav a r i e t yo fp h y s i c a lf a c t o r so ft h ea c q u i s i t i o np r o c e d u r e ，t h ed e r i v e dr a w m o d e l sa l w a y sa r ep r o n et ov a r i o u sk i n d so fu n d e s i r a b l en o i s ea n dd i s t o r t i o n s t h e p u r p o s eo f3 dd e n o i s i n gi s t or e m o v et h ee f f e c t sc a u s e db yi s o l a t e dn o i s e sf r o mt h e d e r i v e ds u r f a c ew h i l s tp r e s e r v i n gt h ea p p e a r a n c eo fg e o m e t r i c a l l ys h a r pf e a t u r e sa n d m i n i m i z i n gd i s t o r t i o nl o c a l l yo rg l o b a l l y i nt h i sp a p e r ，w ef o c u so nt h er e s e a r c ho nd e n o i s i n ga n ds m o o t h i n go f3 d g e o m e t r ya n dp r o p o s ean u m b e ro fn o v e la l g o r i t h m s o ns m o o t h i n g d e n o i s i n gf o r p o i n t b a s e dm o d e l s a n dm a i nc o n t r i b u t i o n si n c l u d e ： ai n t r o d u c t i o nt oc l a s s i c a l3 ds m o o t h i n ga l g o r i t h m sa sw e l la ss o m en e w s m o o t h i n g d e n o i s i n g m e t h o d si nt h er e c e n t y e a r si sp r e s e n t e d a f t e r a n a l y z i n ga n ds u m m a r i z i n gt h ef i m d a m e n t a lt h e o r i e s ，t h ed i s a d v a n t a g e sa n d a d v a n t a g e so fd i f f e r e n t m e t h o d sa r ei n d u c e d a n db r i e fc o m p a r i s o n s b e t w e e nv a r i o u sa l g o r i t h m so nt h e i rt h e o r e t i c a ib a s i s ，a p p l i e de n v i r o n m e n t s a n dn u m e r i c a li m p l e m e n t a t i o n sa r ep r e s e n t e d a sf o rt h ee x i s t i n gm o d e l s ，t oa r t i f i c i a l l ya p p e n dt h en o i s e ，an o i s em o d e l b a s e dg a u s sa l g o r i t h mw a sp r o p o s e d ，m a n yp r a c t i c a l l yn o i s em o d e lu n d e r d i f f e r e n tc o n d i t i o n sc a nb eg e n e r a t e du s i n gt h ea l g o r i t h m ，t h er e q u i r e m e n to f t h ee x p e r i m e n tc a l lb es a t i s f i e d t h er e l i a b i l i t ya n dr o b u s t n e s so ft h et r i n a a l g o r i t h mc a nb ev a l i d a t e d ，a n ds u p p o r tc o r r e s p o n d i n gc o n d i t i o n sf o rt h e r e s e a r c h o nt h ep o i n t b a s e dm o d e ln o i s ei n t e n s i t ya l g o r i t h mf o r3 dm e a n s h i f i t p r o c e s s ，an o i s ei n t e n s i t ya l g o r i t h m b a s e do nt h ee n h a n c e dk e e p i n g c h a r a c t e r sa n dv o l u m eo f t h en o i s ew a s p r o p o s e d a g l o b a lkd o m a i nb a s e d n o i s ew a su s e dt or e s t r i c ta n da d j u s tt h ef i l t e rd i r e c t i o n ，t on l a k et h eb u d g e d i r e c t i o no fm c a n s h i f tb ec l o s et ot h en o n n a lo fp o i n t f o r c et h ee x c e s s v o l u m es h r i n k ，w h i c hm a k e st h ep o i n tu n i f o r m l yd i f f u s e dt ot h ec l u s t i n g d o m a i n ，e f f e c t i v e l yp r e v e n tt h ep r o b l e mo f v e r t e xs h i f t k e y w o r d s p o i n t b a s e dm o d e l ，d e n o i s i n g ，f e a t u r e p r e s e r v a t i o n ，s m o o t h i n g ， f i l t e r i n g b i l a t e r a lf i l t e r ，n o i s ei n t e n s i t y ，m e a ns h i f tp r o c e d u r e 浙江大学硕士学位论文图目录 图目录 图1 1 点模型的计算机三维计算机生成流程。2 图1 2 法向量估计( 二维示意) 8 图1 3 点云法向图1 - 4 曲面上某点的单位法向9 图2 1 拉普拉斯光顺效果1 4 图2 2 平均曲率流失败的例子。1 5 图2 3 图像的双边滤波多尺度去噪效果1 7 图2 4 噪声点正态分布2 0 图2 5 高斯噪声法参数面板2 1 图2 - 6 移动原始点产生的h e a d e r 噪声模型2 2 图2 7 在原始模型上增加点产生的b u n n y 噪声模型。2 3 图2 8 不同仃值产生的噪声模型效果，其中a = 0 2 ，b = 0 6 ，e - - - o 8 ，d _ 1 0 ，e = 1 5 ， 仁2 0 2 3 图2 - 9 对图2 7 噪声模型进行光顺后的对比结果2 4 图3 1 平面拟合标准比较了p 到拟合平面h 的距离d 与p 2 8 图3 2 最小球标准示意图。通过一个最小来拟合2 9 图3 3 最近邻域示意图。噪声点与5 最近邻域点( q o ，q 4 ) 3 0 图3 _ 4 对于三种方法给定阈值测得噪声度的示意图3 0 图3 5 点的m e a ns h i f t 迭代轨迹。3 2 图3 - 6 不同的k 邻域对聚类的影响3 5 图3 7 噪声度对m e a n s h i f t 点移动方向的影响3 6 图3 8 保体积的m e a n s h i f t 的物理模型3 7 图3 - 9 对于三种噪声度分量分别给定阈值的区分3 9 图3 1 0 对噪声模型三种分量分别给定闽值测得的噪声度3 9 图3 1 l 对图3 - 1 0 分别用不同的方法与我们的方法去噪效果比较3 9 图3 1 2 带有高频和噪声簇的噪声模型滤波4 0 图3 1 3 滤波后模型法向、顶点和曲率变化图4 1 图3 1 4f a n d i s k 本文方法滤波效果4 2 1 1 1 浙江大学硕士学位论文 表目录 表目录 表2 1 各种算法的总结和分析1 8 表3 1 滤波统计结果3 8 浙江大学硕士学位论文第1 章绪论 第1 章绪论 随着计算机图形学理论和技术的快速发展，继以三角网格模型为研究对象的 网格数字几何处理后，以离散点为表面表达方式的点云模型( 简称为“点模型”) 由于其数据获取方便、数据结构简单等优点，成为计算机图形学中的一个新的热 门研究邻域。同时计算机图形学的应用领域已遍及科学探索、工程设计、机械制 造、模拟仿真、医药卫生、文物保护、以及游戏娱乐等许多方面，与之相应的特 点之一是广泛使用三维几何数据来描述场景，所表现场景的规模和复杂程度也在 急剧地增长，也极大的促进了点模型的研究与发展。点模型的数字几何处理的深 入研究和广泛应用，呼唤从理论到实践的升华、呼唤对新概念的确切理解和学术 认同来获取成熟实用的新算法、新技术。然而作为新的几何曲面表达形式，与传 统的数字图像处理和视频处理等相当成熟的学科相比，点模型的数字几何处理尚 处在一个发展的初级阶段。本文主要工作是针对点模型预处理之一，对原始模的 光顺和去噪，从而为后续工作打下一个良好的基础。 1 1 点模型处理流程 无论是网格模型还是点云模型的处理，最终的目的就是要把结果应用到实际 的工程中去，通常有两种方式获取三维数字几何，一种方法是通过交互的曲面造 型软件和算法构建i l l ：另一种方法即采用三维扫描仪对物理模型进行数字采样。 随着所需三维几何模型越来越复杂，第一种方法由于耗时且难以构建现实世界中 的物理模型，使第二种方法逐渐占有主导地位。如今各种低档和高档三维扫描仪 的三维几何获取能力以及数据质量已足以满足实际应用的要求。 点模型数字几何处理主要包涵以下几个过程：获取数据的前期预处理、几何 表示、曲面特征分析、光顺去噪、分割、形状匹配、参数化、曲面重建、压缩传 输、编辑、几何造型、变形和动画等；再通过纹理映射、纹理合成、表面着色等 方法给模型表面赋予顶点颜色、光泽度和透明度等属性值，可以让计算机生成的 物体达到以假乱真的真实感效果。本文主要研究点模型数字几何处理中的光顺去 噪环节。 浙江大学硕士学位论文第1 章绪论 a 原始物理模型b 原始扫描数据c 重建曲面表示e 绘制结果 图1 1 点模型的计算机三维计算机生成流程。 1 2 点模型数据采集 随着三维扫描仪硬件设备和处理软件的不断更新，以三维扫描仪为硬件基础 的三维数据获取系统既可获取几何信息又可获得表面纹理颜色信息，另一方面硬 件价格的不断下降，为三维扫描技术的推广和普及带来了机遇。对于具有精致的 表面细节和几何信息丰富物体的几何获取和重建，利用激光测距三维扫描仪来获 取其三维点云模型是当前最为合理和有效的方法。 从测量学的观点看，非接触式测量可真正实现“零接触力测量”，这样有效 避免了高精度测量中测量力带来的系统误差和随机误差，且可方便实现对软质和 超薄物体表面形状的测量。便对于获取的数据进行c a d 反求建模时，由于多方面 原因，譬如被测对象表面的粗糙度、波纹以及其他一些表面缺陷等，还有测量系 统本身产生的影响，在数据采样过程中，不可避免地在真实数据点中混有不合理 的噪声点，其结果将导致重构曲线、曲面不光滑。因此，对于获得的数据必须处 理噪声点1 2 j 。 产生噪声点的因素是多方面的，主要可分为两类【3 】：一类是被测对象表面因 素产生的误差，如表面粗糙度、波纹等缺陷；另一类是由测量系统本身引起的误 差，如测量设备的精度、c c d 摄像机的分辨率、振动等。激光测量中对捕捉到的 二维图像象素进行转换处理后，提取第三维信息而得到一系列被测对象的空间坐 标值，可表示为点集“= f ( x ，y j ，z ，) ix l ，只，z ，ee 3 。f ( x 。，y j ，刁) 一般由被测量对 象的数值g ( t ，只，) 和测量误差p ( x ，y ，z ，) 组成。其中g ( ，只，z ) 由确定性分量 g q ( x ，y ，z ，) 和随机性分量9 5 ( x ，只，z ，) 两部分组成；测量误差e ( x ，y t ，z ，) 可分为 系统测量误差c o ( x , ，只，z ，) 和系统随机误差p ( x ，只，z ，) 。 则测量点表示为： 2 浙江大学硕士学位论文 第1 章绪论 八，只，互) = g ( x l ，只，z ) + p ( t ，只，z ，) = g q ( 五，y l ，) + g s ( 一，y ，z j ) + ( 1 1 ) 盯( ，y l ，z 。) + p ( x ，只，z ，) 式中，g q ( t ，y ，z ，) 表示被测曲面的理想数值；g s ( 一，只，z ) 表示被测曲面由 于存在表面粗糙度、波纹以及其他一些表面缺陷而产生的与曲面理想数值的偏 差；a ( x j ，y t ，五) 表示由测量系统本身产生的确定性误差，并且这个确定性误差具 有一定的规律；( ，y s ，z 。) 表示由于测量系统电噪声、热噪声等因素引起的随机 测量误差。 1 3 点模型基本概念 1 3 1 点云概念 三维数据( 点云) 【4 】就是使用各种三维数据采集仪采集得到的数据，它记录 了有限体表面在离散点上的各种物理参量。它包括的最基本的信息是物体的各离 散点的三维坐标、大小和法向量等，其它的可以包括物体表面的颜色、透明度、 纹理特征等等。 为了有效的处理各种形式的点云，1 5 】根据点云中点的分布特点( 如排列方式、 密度等) 将点云可分为： 散乱点云：测量点没有明显的几何分布特征，呈散乱无序状态。随机扫描方 式下的c m m 、激光点测量等系统的点云呈现散乱状态。 扫描线点云：点云由一组扫描线组成，扫描线上的所有点位于扫描平面内。 c m m 、激光点三角测量系统沿直线扫描的测量数据和线结构光扫描测量数据呈现 该特征。 网格化点云：点云中所有点都与参数域中一个均匀网格的顶点对应。将c m m 、 激光扫描系统、投影光栅测量系统及立体视差法获得的数据经过网格化插值后得 到的点云即为网格化点云。 多边形点云：测量点分布在一系列平行平面内，用小线段将同一平面内距离 最小的若干相邻点依次连接可形成一组有嵌套的平面多边形。莫尔等高线测量、 工业c t 、层切法、磁共振成像等系统的测量点云呈现多边形特征。 此外，测量点云按点的分布密度可分为高密度和低密度点云。c m m 的测量点 云为低密度点云，通常在几十到几千个点。而测量速度及自动化程度较高的光学 法和断层测量法获得的测量数据为高密度点云，一般可达几百万点。 浙江大学硕士学位论文第l 章绪论 1 3 2 光顺去噪与滤波 在信号处理理论中，噪声常被认为是一种随机高频信号，其频率大于某个人 为设定的阈值，并可通过各种空域和频域滤波器对其进行平滑滤波，该概念亦经 常在图像处理中出现，图像去噪的过程即为剔除夹杂在原始图像中噪声的过程。 而光顺是一个工程上的概念，包括光滑和顺眼两方面的含义。光滑是指空间曲线 和曲面的连续阶，数学上一阶导数连续的曲线即为光滑的曲线，而顺眼是人的主 观感觉评价。对于平面曲线，光顺需要满足以下几点：曲线c 2 连续，没有多余 拐点，曲率变化均匀。曲面的光顺更要求曲面上每一条曲线都是光顺的。在数学 上，判断曲面是否满足上述条件的依据是曲率信息。而对于离散数字模型，我们 难以严格要求其满足光顺条件，只是认为当模型的曲面曲率变化比较均匀时即为 光顺。本文所指的去噪、滤波和光顺都是针对三维点模型的，三者概念略有差异， 具体方法上亦有所不同，但目的都是一致的，即消除隐含在三维模型中的噪声， 让处理后的模型最真实地体现实物模型。 1 3 3 点元邻域 在点模型中，采样点的邻域用以估算采样点的各种属性。如：估算采样点的 法向、曲率等局部几何特性。 通常采样点邻域可以采用二种方式构造，即：欧氏距离e 构造出的局部邻域 和k 个最近点构造出的局部邻域。欧氏邻域将所有在以采样点e l 为中心，半径为 占一球内的所有采样点定义为该采样点的邻域点，这种方式适合于规则采样表面， 这是因为对于不规则采样表面，在占一球内可能包含过多或过少的点。除此之外， 欧氏邻域对于即使均匀规则采样但其局部特征尺寸小于占的采样点分布的邻域估 算也会不可靠，如：对于二个非常接近且又是分开的表面在其局部特征尺寸小于 s 时，邻域估算会不可靠。而对于欧氏邻域不能处理的不规则采样表面，k 个最 近点邻域提供了一种自适应邻域估算的方法。h m e n t a 6 1 和a n d e r s s o n j 7 】指出：如果 采样点满足一定的采样规则( 如对局部特征尺寸的自适应) ，则能保证邻域估算 的可靠性。基于k 个最近点构造的局部邻域具有类似于多边形网格的采样点数的 线性复杂度。 对于采样点p p ，定义其邻域n b h a ( p ) 为一个索引集，即 n b h d ( p ) c i n d e x ( p ) 。对于任何p ，i n b h a ( p ) ，只位于邻域内。特别地，每个 采样点的邻域n b h d ( p ) 只跟p 相关，跟邻域内任何别的采样点的邻域 n b h d ( p ，) ，i n b h d ( p ) 无关。 4 浙江大学硕士学位论文 第1 章绪论 k 一最近邻域( k - n e a r e s tn e i g h b o r ：k n n ) n b h d ( p ) 定义为与采样点p 最近 的k 个采样点的索引集合( 如果p p 则包含其自身) ，这里采用的距离为欧氏距 离设盯为满足下列条件的置换算子： p 州) - 4 i = o 并且 p 州厂p i - l p 州+ 1 ) - p h i 1 ，n - 1 ，则 n b h d ( p ) = 盯( 1 ) ，盯( 2 ) ，盯( 七) ( 1 2 ) n b h a ( p ) 定义了一个中心位于p 、半径为哆= 0 以( ”- p 6 的球j ：，当且仅当 f n b h d c p ) 时p 。位于s ：内。 k n n 的求解是一个传统问题，最近，j a g a n 等人【8 j 基于外存提出了一种超大规 模点云的k n n 求解算法。由于此过程不是我们工作的重点，故在本系统中，我们 采用k d 树搜索只的n b h d ( p ，) ，k d 树的优势在于，给定一个点数m ，它能以 o ( m l g 功( ”为模型中点的个数) 的时间复杂度，快速地查找到点p ，的m 个最近点。 本文邻域的大小可以根据点模型中的点数做自适应性的调整，一般来说，k 的取 值在 9 ，2 5 之间。 无论是欧氏邻域还是k 个最近点邻域都能采用采样点的层次空间剖分技术 ( 如：k d 树，b s p 树和八叉树等) 有效地计算。和三角网格邻域的显式表达相 对应，在点采样几何的某些应用( 如：采样点模型的变形、拉伸等) 中，也需要 对采样点局部邻域进行动态重计算。在本文中主要是利用k _ d 树来构建k - 最近邻 域。 1 3 4 法向计算 采样点的法向在点模型的处理中是非常有用的信息，所以，已有很多文献对 采样点的法向估算进行了探讨。设点模型外表面上任一采样点p ，对应的法向为哺 及其k n n 为( p 1 1 ，p m ，) ，则估算法向的具体方法有： 1 ) 最小二乘法 对只及其k n n 拟合出一个平面，用此平面的法向作为p 。的法向。这种方法既 简单又自然的方法。 最小二乘方法通常是通过求得目标函数f ( x ，y ，z ) 的最小残差平方和即 e = ( f ( ，只，z 。) ) 2 = m i n ( 1 3 ) t - i 来解决超定方程组问题，残差平方和对各参数的偏微分方程组称为法方程。 浙江大学硕士学位论文第1 章绪论 2 ) 移动最d x - - 乘法( m l s ) 9 1 1 1 0 1 移动最小二乘法是最为精确的法向估算方法。 n i n aa m e n t a 等在文献【1 1 】中指出，采样点模型的m l s 隐式曲面函数可以表示 成二个分量：一个能量场和一个法向量场。对于采样点模型表面附近任意一点， 用m l s 表面能量最小法可求出该点的法向。但运用该方法在某些地方会产生不理 想的法向( 如：距离表面较远的地方和表面附近有明显特征的地方) 【1 2 】。为此， 他们又提出了另外二种表面能量定义方式，即：通过邻域采样点加权重心的能量 函数以及利用线积分计算的能量函数，用这二种能量定义方式估算模型表面附近 的法向场时可以改进法向场的分布，但这两种方法都是针对没有法向的采样点模 型，而且需费时求解非线性方程。 通过采用局部高阶多项式为一组给定的离散采样点提供了一个逼近或插值 曲面，a l e x a 等首次将其应用于基于点模型上。给定点集p ，其m l s 曲面s m l s ( p ) 是根据m l s 投影算子：b 斗r 3 隐式地被定义的，该投影算子将s m l s ( p ) 定义域 b 附近的点投影到该曲面上，由所有投影后的点定义s m l s ( p ) ，即 甄# 缸b ：缈( 曲= x ) = r a n g e ( u ) ( 本文取b 为输入点h 的n b h d ( p f ) ) 。投影 的计算，卜y ( r ) 分成以下三步： ( 1 ) 对任意具有甩= 胛( g ) = 名的n , q i r 3 ，找到局部参考平面 l | ，一硎 日= 伽e i r 3 ：甩7 x = n r q ) 并使如下非线性能量函数最小： 巧。( g ，珂) - ( 只- - n 7 9 ) 2 0 ( 1 l p ，- q l b ( 1 4 ) f 其中0 ：i r 斗i r 是一个光滑的，单调递减的正值权函数。 ( 2 ) 通过对点只的邻域点g 进行加权最小二乘拟合，找到局部双变量多项式 逼近g ：h ，寸1 r 3 。设g f 是见到珥上的正交投影，( x t ，y ，) 是它的局部二维坐标， z # i i q - p , l l 撇h ，的高度，则使如下误差最小： ( g ( t ，只) 一，) 9 ( 1 p ，- q l b ( 1 5 ) ( 3 ) r 的投影最后被定义成：( ，) - q + g ( o ，0 ) n 。 递减权函数一般选择高斯函数o ( d ) = e 。1 ”，这样产生的m l s 曲面将是c ” 连续的，其中权函数中的高斯参数h 对应于全局估算采样空问距离，并能控制 m l s 曲面的光顺度。在本文中，我们局部地确定该参数，动态地取h = r 3 ，其 中r 是肼的缸最近邻域包围球的半径，如此仅仅缸最近邻域中的采样点对式( 1 5 ) 6 故计算开销大，a l e x a 和a d a m s o n 等人1 5 1 对该投影算子进行了改进使得求解变得 删# 黼 m 6 ， n ( x ) ：= a r g r a i n 忤。n 7 ( x - p 巾( 卜只d ( 1 7 ) 其重复叠代投影过程的具体算法见【1 5 】，该方法可简便地求出采样点在岛以p ) 3 ) 协方差分析( 主元分析p c a ：p r i n c i p a lc o m p o n e n ta n a l y s i s ) 胪南磊研 o 8 c 饲2 料坼 9 ， 浙江大学硕士学位论文第l 章绪论 既然c 是对称正定矩阵，所以所有的特征值是实数、特征向量是正交的。根 据，点a 到中心点的平方距离和总的变化可由下式表示： e i p ；一p - 1 2 = 厶+ + 五 ( 1 1 1 ) i e n 1 法向估计 假设矗五如，则下式： t ( x ) ：( x 一劢v o = 0 ( 1 1 2 ) 可得v 。可近似邻域小面在点p 处法向1 。，而v ，和v ：则是切平面在点p 处的二个 伸展方向。 2 法向方向 根据协方差矩阵可计算出每个点的法向，但是各个点的法向朝向各不相同， 有点向内，有的向外。d 6 提出了用最小生成树的方法规整化所有点的法向。算法 是通过具有最大z 坐标的点开始，考虑在最小生成树上的点，相邻点的法向之间 的夹角大于万2 则需要反向。如图1 - 2 b 遍历所有点后，法向即可规整。 查谒球范围 面 ( a ) 协方差计算切平n ( q u e r yb a l l 为点的查询球，为c o v a r i a n c ee l l i p s o i d ) ( b ) 最小生成树法法向归一化( 因为与相邻的法向夹角大于石2 ，所以红色的箭头需要反向) 图1 - 2 法向量估计( 二维示意) 3 邻域小面变化 九定量的反应了邻域小面的法向变化，而面变化则表示点偏离切平面的程度。 可定量的定义具有 个邻域点的点p 的面的变化定义为： c r n ( p 卜焘 o 1 3 ) 8 浙江大学硕士学位论文第1 章绪论 面变化的最大值为1 3 表示点的分布完全各向同性。当面变化为0 时则表示所有 的点在同一个平面上。 下图1 - 3 是在试验性平台上计算实现的点云法向( 方向未归一化) ： 图l - 3 点云法向图l - 4 曲面上某点的单位法向 1 4 点模型光顺处理 由于三维几何扫描仪的广泛使用和对扫描所得模型的数据规模和精度需求 不断增长，鲁棒和有效的几何处理变得越来越重要。尽管现有的三维扫描硬件具 有高精度，但人为因素的干扰或者扫描仪本身的缺陷使得生成三维数据不可避免 地带有噪声。类似地，从c t 设备中获得的体数据中抽取几何模型也通常含有一 定数量的噪声。因此在对获取的原始三维数据进行相关数字几何处理之前进行光 顺和剔除噪声成为一个必不可少的过程。点模型光顺作为点模型数字几何处理的 基础性工作，近年来也成为数字几何处理的一个研究热点。 由三维扫描获取的原始数据不可避免地包含有噪声、浮游点，或者由于模型 表面的自遮挡以及表面材料等原因，使得扫描得到的模型存在大块的空隙，这就 需要对模型进行修复，即对点模型的数据进行前期处理 1 7 1 0 实际上，噪声和特征都是三维数字模型的某种几何属性。从不同的理论层面， 噪声和特征的区分具有不同的标准。类似图像处理，对于三维模型我们亦可通过 阈值来区分高频信息和低频信息，而在曲面论中，极小曲面的充要条件是平均曲 率处处为零，通过在法向方向以平均曲率的速度移动可以达到曲面光顺的目的， 在这过程中噪声自动被扩散消除。由于网格顶点的离散平均曲率只与一阶邻域顶 点相关【1 8 l 【l9 】，为此，网格上的局部小扰动是噪声，而具有一定的局部连贯性且表 现为整体轮廓的信息视为特征。特别地，对于三角网格来讲，只牵涉到一阶邻域 9 浙江大学硕士学位论文第1 章绪论 三角形的局部几何变形的孤立顶点扰动为噪声，将给予剔除。若顶点及其一阶邻 域顶点在同一方向上的扰动，涉及n - - 阶邻域三角形变形，我们认为它表达一定 的整体信息，为三角网格的特征，给予保持甚至增强。 三维模型去噪的目标是在剔除噪声获取离散曲面更高阶光滑性的同时，尽量 防止模型产生收缩和过光顺。我们认为，一个好的三维几何去噪光顺算法除了能 有效地效剔除夹杂在三维模型中的各种形式的噪声外，还应有如下主要特点：1 在模型变得光顺的同时保持模型固有的几何特征；2 处理中防止体积收缩，防止 模型扭曲变形；3 防止在光顺过程中所出现的顶点漂移情况，曲面上顶点漂移会 使模型出现裂缝，导致采样均匀模型变得不均匀；4 较低的算法时间复杂度和空 间复杂度。近年来数字几何研究者提出了多种网格和点模型光顺算法，但如何在 剔除噪声的同时保持模型的几何特征然仍是一个具有挑战性的问题。到目前为 止，现有的算法都难以满足以上要求，或者说尚不能很好地同时解决以上问题。 本文将主要围绕这四个基本目标展开讨论并提出解决方案。 网格模型的去噪算法已经有了广泛深入的研究，但点模型的去噪算法较少。 好的点模型的去噪算法除了需要剔除噪声外，还需要有效地保持模型的特征，防 止顶点漂移以及保体积等。通过低通滤波技术可以减少一部分噪声。p a u l y 等1 2 0 j 通过将采样点模型表面先分成块，然后对每一块通过局部高度场逼近进行重采 样，从而把图像中基于f o u r i e r 的光谱分析方法应用于采样点几何。该方法通过对 点模型进行光谱分析和滤波，达到去噪的目的。a l e x a 等【2 1 墚用m l s 方法逼近原 始点集模型，然后将点移到其对应的曲面上来消除噪声，但由于求解m l s 曲面 需要解一非线性优化问题，因此该方法的效率不高。f l e i s h m a n 等【2 2 j 等将图像双 边滤波去噪函数拓展到用于二维流形表面上，提出了保特征的网格去噪算法，由 于该算法不需拓扑连接关系，因此可推广到点模型上。 1 5 本章小结 本文的主要研究内容为点模型的光顺去噪处理，针对现有点模型的光顺去噪 算法进行深入的分析研究，了解其不足提出新的解决方法。 本文共分四章： 第一章主要讲述点云数据的基本概念，以及点云数据获得方法及设备和目前 国内外关于点云模型光顺去噪处理的研究情况。 第二章介绍了经典的三维离散模型的去噪光顺方法，并分析了近年来提出的 1 0 浙江大学硕士学位论文 第l 章绪论 新的去噪光顺方法，总结归纳了这些方法的基本原理以及它们的优缺点，最后结 合作者在本领域的研究工作，对今后三维数据的去嗓光顺的研究重点作一些分 析。并结合实际的研究工作，提出了一种利用高斯分布产生噪声模型的方法。 第三章介绍并引入了m e a ns h i f t 算法，分析其基本原理，在三维m e a n s h i f i 过程的点模型去噪算法的基础上，提出了基于噪声度的增强保持特征和保体积的 去噪算法。在本算法中我们用一个基于全局七邻域噪声度来约束并调整滤波方向， 使m e a n s l l i f l 移动方向更接点的法向方向，强制过度的体积收缩，使点在收敛过 程中均匀的扩散到聚类邻域中，有效的防止了顶点漂移的问题，这种情况尤其适 用于高频孤立大噪声和噪声簇。 第四章在总结全文的工作和创新点的基础上，指出了点云数据处理中的进一 步研究内容。 浙江大学硕士学位论文 第2 章点云模型去噪算法与噪声模拟 第2 章点云模型去噪算法与噪声模拟 基于点的计算机图形学近年来已经成为计算机图形学的一个重要的研究领 域，三维几何模型的点表示已成为具有复杂表面几何的三维物体的主流表示方法 之一。在通过三维扫描仪或激光测距仪等仪器获取三维数据时，难免会因为人 为扰动或者扫描仪本身的缺陷使之带有噪声。因此，在对点模型进行相应的绘制 和数字几何处理之前，带有噪声的模型会给几何处理造成极大的困难；同时点模 型编辑造型过程中，也需要去掉三维点模型的一些噪声。因此点模型的光顺去噪 已成为三维数字几何处理的一个基础性研究问题。 目前网格的光顺算法已经获得的广泛的研究，但由于点模型本身缺乏拓扑连 接信息，已有的网格的光顺算法不能简单的推广到点模型上来，点模型去噪变得 相对比较困难，相应的光顺去噪的算法较少。但无论是对网格还是点模型，去噪 算法有以下3 种分类方法。从算法复杂性角度分析，可分为基于l a p l a c e 算子的 光顺方法，简单的非迭代方法以及基于最优化的方法等。根据特征保持性和噪声 在各个方向上的扩散方式，可以分为各向同性算法和各向异性算法。根据去噪算 子的连续与否，可分为基于曲面拟合的去噪算法，通过选取光滑曲面对离散点进 行拟合重建达到去噪的目的：对三维模型采样点进行离散几何分析，直接在三维 空间对点数据进行估计处理，这类方法绕过了曲面拟合重建等复杂费时的过程， 在算法复杂度和运算效率上都很有优势。 所有这些去噪算法都有一个共同特点，即都依赖于采样点的邻域点集的几何 信息和拓扑，是一种基于局部几何信息的光顺算法。 2 1 引言 网格的光顺去噪算法已获得了广泛的研究。将图像处理中的l a p l a c e 滤波技 术引入到3 d 网格光顺中，t a u b i n l 2 4 1 提出了一种基于l a p l a c e 流的网格信号处理 方法。d e s b r u n 等人1 2 5 j 运用隐式的l a p l a c i a n 算子，得到一种更加稳定、快速的 算法，他提出了一种基于三角网格的曲率法向算子，利用平均曲率流方程处理网 格光顺问题，将顶点的移动方向限制在法向方向，很好地解决了顶点漂移的问题。 然而，这些方法都是各项同性的，网格模型噪声点和特征点都不加区分的统一处 理，结果是在光顺的过程中，一些重要的特征模糊了。此外，由于基于l a p l a c e 滤波的网格光顺算法本质上是一种曲面能量的极小化问题，因此将不可避免地产 生模型收缩现象，导致模型变形。由于各向同性的网格光顺算法有如上所述缺点， 1 2 浙江大学硕士学位论文第2 章点云模型去噪算法与噪声模拟 人们提出了各向异性的网格光顺算法。该算法的主要思想同样来源于图像处理， p e r o n a 等人【2 6 】修改了传统的线性几何流的图像去噪方法，提出了一种非线性的各 向异性的扩散方程用于图像的边缘检测和噪声剔除，该方法的基本思想是在图像 的边缘处削弱光顺强度，从而在剔除噪声的同时有效的保持图像的边缘特征。文 献 2 7 1 1 2 8 1 1 2 9 3 0 3 1 1 将此各向异性思想推广到三角网格上，提出了各向异性几何流的 网格光顺算法。这些算法虽然获得了保特征的效果，但通常采用高阶几何流，算 法的复杂度较高，且不保体积。近年来一种比较成功的网格光顺算法为双边滤波。 f l e i s h m a n 等人【3 2 j 和j o n e s 等人吲将图像处理中双边滤波器的思想【3 4 1 ，推广到三 维网格模型，其基本思想是将g a u s s 滤波和保特征权函数结合起来，有效地保持 光顺过程中模型的特征。然而这些算法虽然有保几何特征的效果，但是不保体积， 在有些情况下会造成网格模型的变形和扭曲，并且在处理稍大的噪声时会引起过 光顺而不能有效地保持网格的细小特征。 所有这些方法都需要建立一个局部的拓扑结构或者一个局部的参数化信息。 注意到点模型本身不具备这些信息，一方面由于散乱点的重建、三角化以及参数 化工作并不容易，代价也相当大：另一方面，如果散乱点本身带有噪声，则会不 可避免地影响重建和参数化的精度和效果。因此对带有噪声的点模型进行去噪处 理，然后再进行光顺去噪更有意义。相比较网格来说，点模型去噪算法较少。p a u l y 等人【3 5 1 将l a p l a c i a n 算子应用到点模型上，但该算法会出现特征被磨光的情况， 且由于点不在法向方向进行移动将出现顶点漂移：为防止顶点漂移，肖春霞等人p 川 通过采用协方差分析方法获取点模型的点的平均曲率，提出了基于平均曲率流的 点模型去噪算法，但该算法仍然是各向同性的。c l a r e n z 3 6 l 通过在点模型上解一 个离散的各向异性的几何扩散方程，提出了各向异性的点模型去噪算法。p a u l y 和g r o s s 等人借助点模型的切割和分片平面参数化技术，把傅立叶变换和谱分析 技术引入到点模型中，进行点模型的去噪处理1 3 刀；a l e x a 等人【3 8 】基于迭代优化方 法，为点集曲面建立一个移动最j 、- - 次曲面( m l s ) ，通过将噪声点移至所逼近的 二次曲面上来达到去噪的目的，该方法计算量大，计算不鲁棒，且难以保持点模 型的特征。下面我们介绍一些经典的去噪光顺方法。 2 2 去噪算介绍 2 2 1 拉普拉斯方法 拉普拉斯光顺方法是一种最常见的也是最简单的一种光顺算法，它的基本原 理是对模型上的每个顶点应用拉普拉斯算子。拉普拉斯算子为： 浙江大学硕士学位论文 第2 章点云模型去曝算法与噪声模拟 ( a ) 原始模型 = v 2 = 等+ 罢a y + 等 缸2 2 2 ( b ) 1 0 次迭代效果 ( c ) 2 0 次迭代效果 图2 - 1 拉普拉斯光顺效果 设p 。= ( t ，j ，。z 。) 为顶点，则在一个三维模型上进行磨光过程可以看作成一 个扩散过程： 勿 = 舡( p ，) 通过在时间轴上的积分，曲面上细小的起伏、噪声能量很快地扩散到它的邻 域中，使整个曲面变得光滑。如果采用显式的欧拉积分方法，即为； ”= ( 1 + _ 成工) p ? 该方法对每个顶点进行估计，逐步调整到其邻域的几何重心位置： 工( 只) = a + 名姿争：警一只) ，= 1 ，2 ，“，后 ( 2 1 ) 其中窖表示只的k 个邻域点，五值为一个小正数。拉普拉斯光顺方法是通过 一致扩散高频几何噪声达到光顺目的，虽然算法简单，但是随着迭代次数的增加， 网格的体积快速收缩，并容易产生过光顺而使模型的凹凸特征变模糊，如图2 一