（应用数学专业论文）点模型的光顺去噪和重采样.pdf

浙江大学硕 学位论立 摘要 作为一种新的i 维几何表示方式，点模型正在受到越来越多的关注。由于其 获取直接，结构简单等特点，点模型已经在医学辅助诊断，工业设计，地理信息 系统，物理仿真，数宁娱乐，电予商务，文化遗产数字化保护等领域得到广泛地 应用。本文在点模型的光顺去噪和重采样两方面提出新算法。 本文提出了一种点模型上的非局部( n o n - l o c a l ，n l ) 光顺去噪算法。b 猷往 三维模型上局部光顺去噪算法不同，新算法更着重于的模型整体的几何信息分 布，通过对噪音模举整体几何特征的统计，r i 动估计出噪音模型的特征分布和噪 音分布。实验表明，新算法具有保特征，保体积等其同类局部算法不具有的优点。 本文第三章提出了+ 种面向小尺度几何修复的点模型重采样算法。该算法首 先判断模型卜漏洞和裂缝区域，然后根据漏洞和裂缝区域附近的几何信息产生新 的采样点覆盖漏洞和裂缝。该算法具有普适性，适用于各种小尺度但是分布广的 空洞区域几何修复。通过实验，重采样后的模型能够和匣有模型保持几何信息一 致。 关键词：点模型，数字几何处理，非局部，光顺去噪，重采样 2 浙江大学碗。1 学位论文 a b s t r a c t p o i n ts e t sarer e c e i v i n gag r o w i n ga m o u n to fa t t e n t i o na sa r e p r e s e n t a t i o no fm o d e l si nc o m p u t e rg r a p h i c s t h ee m e r g e n c e o fa f f o r d a b l ea n da c c u r a t es c a n n i n gd e v i c e sa n di t ss i m p l e d a t as t r u c t u r ed r i v et h ep o i n ts e t sm o v ef o r w a r d p o i n ts e t s areb e i n ga p p l i e do nm a n yf i e l d sa sm e d i c a l ， e n g i n e e r i n g ， t o p o g r a p h y ，s i m u l a t i o n ，g a m e m o v i e ，e c o m m e r c ea n d a r t h i s t o r y t h et h e s i sp r e s e n t st w on e wa l g o r i t h m so n d e n o s i n ga n du p s a m p l i n go np o i n ts e t s d i f f e r e n tf r o mo t h e rl o c a ld e n o i s i n ga l g o r i t h m so n3 ds h a p e s ， w ep r o p o s e dan o n l o c a l ( n 1 ) d e n o i s i n ga l g o r i t h m w h i c h f o c u s e s o nt h eg l o b a lg e o m e t r yf e a t u r ed i s t r i b u t i o n a c c o r d i n gt ot h e s t a t i s t i co ft h en o i s ym o d e l ，t h ea l g o r i t h mc a nd i s t i n g u i s h t h ef e a t u r ea n dn o i s ea u t o m a t i c a l l y f e a t u r ep r e s e r v a t i o na n d a n t i s h r i n k a g ea rep o s e db yo u ra l g o r i t h m o u rn o v e lu p s a m p l i n ga l g o r i t h ma i m e da th o l e s c o v e r i n go f p o i n ts e t s w ef i r s t l yf i n dt h eb o u n d a r yo ft h eh o l e s ，a n d t h e nr e s a m p l en e wp o i n t sneart h eb o u n d a r yp o i n t sa l o n gt h e d i r e c t i o nt ot h eh o l e t h em e t h o dcanb ea p p l i e df o rh o l e f r e e i nm a n ycasesa se d i t e dm o d e l ，t h em o d e ls c a n n e df r o m3 d s c a n n i n gd e v i c ea n ds oo n a f t e ro u ru p s a m p l i n g ，t h em o d e l h o l d st h es a m eg e o m e t r ya st h eo r i g i n a1m o d e l k e y w o r d s ：p o i n ts e t s ，d i g i t a lg e o m e t r yp r o c e s s i n g ( d e p ) ， n o n l o c a l ，d e n o i s i n g ，u p s a m p l i n g ，r e s a m p l i n g 浙江大学顿：上学位论文 第一章绪论 1 1 数字几何处理 多媒体技术已经经历了三次技术革命：声音、图像和视频的信号数字化处理 与传播。现在我们i e 存见证第四次技术革命：三维数字几何信号的处理与传播。 计算机工业，储存技术，以及信号传输等推动着多媒体不断发生新的革命。 随着摩尔定律的廊验。我们见证了2 0 世纪7 0 年代的数字音频，8 0 年代的数字 图像，9 0 年代的数字视频。，现在，三维数字几何正向我们扑面走来。 三维数字儿何一般是指三维几何数据。在计算机图形学中，网格模型和点模 型是二维几何数据最常用的表现形式。而数字几何处理是以三维几何数据为处理 对象的各种技术，包括：几何数据获取，盥面重建，离散微分几何，模型的光顺 去噪，模型简化，几何编码，曲面参数化，曲面编辑与变形，曲面分片等等。 三维数字几何无处不在，不仅在好莱坞的大片中，在医学辅助诊断，工业设 计，地理信息系统，物理仿真，数字娱乐，电子商务，文化遗产数字化保护等领 域，数字几何也得到越来越广泛的应用。同时，数学，物理，计算机等学科的不 断发展，给数字几何的发展提供了理论支持和实践指导。 1 2 数字几何的获取 数字几何的获取分为正向t 程和逆向工程。正向t 程是指直接利用计算机平 台对几何模型进行设计，譬如a u t o c a d 中几何零件设计，优点是对于几何简单的物 体而言该方法更加灵活。而对于具有精致的表面细节和几何信息丰富的物体，单 纯依靠用户设计无疑十分繁琐，工作量巨大。相比较而言，逆向工程利用激光测 距三维扫描仪来获取真实物体表面复杂的王维数字模型是当前最为合理且有效 的方法。 浙扛人学硕士学位论且= 图1 - 1 图1 1 ，s t a n f o r db u n n y 数宁几何模型与实物模型 实物模型 i lc a d ，图形建模 l f模型重建 图1 - 2逆向工程流程罔 1 3 基于点的数字几何处理 数字几何处理对象般有网格模型和点模型。三角网格住许多数字几何应用 领域中是最通用的曲面表示a 式。由于它的简单和灵活，在一些注重处理性能的 应用中，三角网格取代了传统的c a d 曲面表示，如n u r b s 曲面。 虽然三角网格比n u r b s 灵活，但它在某些应用中也存存着限制和不足。网 格模颦除了位置和法向信息之外，还包括了点，线，面之间的拓扑信息。如何维 护拓扑信息是处理网格模型时候必须考虑的问题。比如在网格模型编辑和形变 中，当网格的顶点位置发牛大规模改变的时候，就需要重构大量的拓扑信息。而 点模型只包括点的位置信息( 有时候会包括法向信息) ，和 目格模型相比，其表 示就更加灵活。 浙扛太学砸1 学位论文 从模型的表现力米讲，点模型比网格模型更能表现复杂和不规则的物体，i 司 时可以获得理想的绘制速度和良好的绘制质量。 点采样对象无需存储与维护伞局一致的拓扑信息，斟此，与三角阿格相比 在处理高度复杂、动态几何变形的模型时具有更大的灵活性。 1 4 基于点的数字几何处理的一般流程 【s c h r o d e r2 0 0 1 】将基丁点的数字几何处理分为i 个流程：数据获取，处 理与建模，模型的绘制。 数据获取；近几年来计算机硬件的高速发展和高精度的3 d 扫描仪出现，使 得现实模型到几何数据的转化变得更方便更经济，这也是点模型近几年获得快速 发展得到广泛应用的原因。同时，通过图像获得3 d 几何数据的研究得到充分研 究，特别是大型的简单的建筑物的儿何形状获取和估计具有较大应用价值 处理与建模：对获取的几何数据进行修改，完善，是点模型数字几何处理的 重要一部分，诸如编辑变形，布尔运算，点云简化等等。 g u o2 0 0 4 在三维空 间中拟合出距离场方程，再此基础上作f f d 编辑。 p a u l y2 0 0 3 a 】在对点模 型进行混合曲而建模的基础上做布尔运算、f f d 和动态重采样。 p a u l y2 0 0 2 】 提出了点云的简化操作。【h u2 0 0 5 b 对点模型的光顺去噪作了大量讨论，等等。 模型绘制：点模型的研究始于点模型的绘制，现在其绘制依然是点模型数宁 几何处理中的+ 个热点问题。点模型的绘制依旧包括绘制的基本问题，光照计算， 可见计算，纹理计算等等。另外，由于点模型是采样模型，在高分辨率下需要更 大的采样密度，如何在高分辨率下绘制点模型也是点模型绘制的特殊问题。在原 有点云的拟合曲面七重新采样是解决该问题的重要方法。 a l e x a 2 0 0 1 提出利 用m l s 作为点云的拟合曲面。 c a r r 2 0 0 1 利用r b f 曲面作为点云的拟合曲面。另 外，通过点点插值增加采样点的方法也得到很好的效果 k a n a m o r i 2 0 0 5 。 浙江大学碗十学位- 出文 1 5 本文工作意义 本文的工作着重在点模型光顺去噪算法和重采样算法。这两剥一算法都属于处 理流程的第二步，处理与建模，它们都是点模型数字几何处理的基础操作。光顺 去噪和重采样都可以看作是曲面重建的另+ 形式，它们的主要问题都是集中在如 何在带有错误和不确定因素的几何信息中抽取h i 正确的几何信息。 1 5 1 点模型光顺和去嗓算法意义 点模型是实物模型转化为数据模型的最早的表现形式。虽然现在的三维扫描 硬件正在向着高精度发展，但人为因素的干扰或者扫描仪本身的缺陷使得生成三 维数据不町避免地带有噪声。因此在对获取的骧始三维数据进行相关数字几何处 理之前进行光顺和剔除噪声成为一个必不可少的过程。 广义上讲，三维几何光顺去噪的目标是：有效剔除夹杂在三维模型中的各种 形式的噪音，在模型变得光顺的同时保持模型固有的儿何特征，处理中防止体积 收缩，防止模型变形，具有较低的时间复杂度和j 空间复杂度。近年来，各种网格 和点模型光顺去噪算法不断涌现，但是仍不能同时实现以上几个i i 标。可以说， 三维几何的光顺去噪在今后一段时期内将仍是数字几何处理研究的一个热点。 1 5 2 点模型重采样的意义与应用 与网格模型不同，点模型并没有严格定义模型的曲面。作为一种采样模型， 在绘制中只要满足输出设备的分辨率的要求，都可以被正确绘制。但是作为一个 已经采样完成的点模型无法满足用户任意增大分辨率的需求。当点模型的采样密 度不能满足显示分辨率的需求时，就需要对点模型表面进行重采样。 4 浙江大学硕士学位论文 ( a ) ( b ) 图1 - 8 图l 一8 h a n d 的点模型绘制( b ) 分辨率高于( a ) 。和( a ) 相比，( b m 曲面已经变得不连 续。 点模型重采样的另外的一个应用是修复或者弥补点模型丢失的几何信息。当 实物模型被扫描仪转化成点模型，或者点模型被编辑、形变以后，都会发生不同 程度的几何信息的丢失。 ( a )( b ) 图1 - 9 图l 一9 丢失几何信息i 的维纳斯，b u n n y 模型 ( a ) 是对维纳斯实物模型扫描的结果，由于扫描角度的原凶，模型下巴部分 和右脸侧信息丢失。( b ) 是模型b u n n y 右耳朵拉拽的结果。由于耳朵长度变长， 原有的采样点已不能完整表现拉拽后耳朵的信息。 浙江夫学硕士学位论文 很多点模型和网格模型上的修复算法都可以作为重采样算法。几何修复也是 近年来数字几何处理中的个热点问题。在目前已有的研究文献中， d a v i s 2 0 0 2 】利用体积测度扩散法( v o l u m e t r i cd i f f u s i o n ) 以体积测度的方法表 示数据，然后在构造有向距离函数的基础上，利用逐步扩散的方法使得漏洞得以 修复。 c a r r 2 0 0 1 1 提出了基于r b f 隐式曲面重建的方法对上述采样不足的数 据模型进行插值修补。 s h a r f 2 0 0 4 】提出了一种基于上下文的采样点模型表面 修复的方法。类似于二维图像上的纹理合成算法，该方法基于邻域相似原则，在 采样点模型的其它位置寻找与待修补空洞周围几何匹配程度最高的采样点几何 块，作为_ i = | j 于填补空洞的材料。 但是我们常常会遇到小尺度且频繁的几何信息丢失，比如说b u n n y 耳朵拉拽 之后，耳朵上会出现细小的裂缝和小洞，如果对这种情况使用以上修复算法那就 显得费时。所以就出现一些面向此类小尺度几何缺损的重采样( 修复) 算法。 1 6 三维模型的光顺去噪算法相关工作 1 6 1l a p l a c e 方法 在三维流型中，l a p l a c e 算子表示为： = 咖。v = 等+ 导+ 等 仆， t a u b i n1 9 9 5 a 】提出种基于信号处理的三角网格光顺方法：在三角网格 上提出离散l a p l a c e 算子。该离散l a p l a c e 算予表现为顶点几何的线性关系，所以 无论从运行时间和内存空间来讲，该光顺算法都是快速和有效的，特别对于大规 模的三角网格模型来说该优势特j j 【f 明届。 在三角网格上，点v 离散l a p l a c e 算子依赖于v 的邻域点( f ) ，定义为 毒= ( v ) = u 一了1 v j ( 1 - 2 ) ，儿何意义非常直观，见图i - 3 。 “j ) e n ( i ) 6 浙江夫学硕l 学位论文 图1 3 然后我们可以根据该算予的计算结果移动顶点： 吲瑚鲁_ 舡( 吐( i - 3 ) 我们只要定义点模型邻域点集，该离散算子可以直接移植到点模型的光顺 上。 t a u b i n1 9 9 5 a 基于该方法给出了三角网格上的频率的一种定义：离散 l a p l a c e 算了定义于三角网格上的循环矩阵k 的特征向量可以作为频率的一种表 示。所以，l a p l a c e 光顺方法就可以看作通过扩散高频几何信息来达到光顺目的， 实际上是一种各向同性的光顺算法。我们对点模型l 操作该算法，发现虽然该算 法速度快，但是当迭代次数多了之后，顶点有可能沿切平面移动，会出现顶点漂 移以及特征磨损的情况。 1 6 2 平均曲率流光顺 由于l a p l a c e 光顺会造成顶点漂移，所以d e s b r u n 于1 9 9 9 年提出了基于甲均 曲率流的i 角网格光顾算法：根据估计出的曲率，顶点在法向上移动恰当的距离。 在 d e s b r u n1 9 9 9 巾，提出平均曲率方向的估计方式( 1 - 4 ) ，其中“为平均曲 率。 日( v j ) = 如珥= 一万v a = 一石1 ，磊) ( c o t 哆+ c o t f l a ( x ，一) ( 1 4 ) 图1 4 图1 - 4 中勺= r ，一，q ，只是在相邻两个三角形中的对角，a 是围绕的 浙江大学硕士学位论文 三角型面积。 平均曲率流办法解决了顶点漂移，从图l - 5 中可以看出，虽然左右两边采样 稀疏程度不同，但是没有产生小自然的形变。 图l - 5 图i - 6 是运用l a p l a c e 方法光顺的结果，模型形状出现异化。 图l 一6 由于该方法是以曲率为光顺速度，所以对于特征的磨损也是十分明显。所以， x i a o2 0 0 6 等通过对光顺速度加上调节项，得到各项异性的曲率流光顺。 鲁- - g “啊，0 - 5 ) 一般地，g ( 1 1 ) = 1 + c k 一, v 2 ，曲率大的地方可以恰当降低光顺速度，曲率小的地 方则可以提高光顺速度，但是经过实验，由于该方法严重依赖模型 ：的曲率估计， 所以当噪音过大时仍得不到理想的结果。 浙江 学颤士学位论文 1 6 3 邻域滤波方法 该类方法直接来源_ r 图像的去噪算法，与图像类似， 型上常用的光顺和去噪算法。 图像上的高斯滤波器( 1 6 ) ： i ，一。0 2 九 ) = e2 4 2 ，( 力， p e n ( ) i ( u ) 表示p 点像素值，i ) 表示滤波以后的像素值。 高斯滤波的权值被领域点的空问位置决定。 图像上的双边滤波器( 1 - 7 ) ： 一i 生一坦凹噬 p2 砰g2 j ( p ) ，( 甜) = 型l 1 了面i 矿 ye2 一e 2 一 p e n ( u ) 高斯滤波是网格和点模 ( 1 6 ) ( 1 7 ) 双边滤波比高斯滤波增加了像素相似权，如果邻域点与中心点像素值相似， 那么权值高，反之亦然。 2 0 0 3 年 f l e i s h m a n2 0 0 3 提出种三角网格模型上的双边滤波器光顺 和去噪算法。他结合网格模型的特点，巧妙地通过沿法向移动顶点使得阿格光顺。 由于嵌入三维空间的二维流型上很难定义体现几何特征而且统尺度的标量场 ( 图像町以看作定义在平面上的标量场) ，【f l e i s h m a n2 0 0 3 通过在顶点切 平面作为局部的基平面，以邻域点与此基平面的有向距离作为图像上相对应的像 素值，然后引用双边滤波的思路，得到该顶点的+ 个有向高度值。 ( 1 - 8 ) 上式中，h 为点v 的法向，v ( v ) 是指点v 的邻域，啦o ) 是光顺高斯权，指以o c 为 标准差的高斯核：彬。) ：p 一吒越大，m 被光顺程度越大，反之亦然。形( x ) 一r 2 是保特征高斯权，指以t 为标准差的高斯核：睨( 曲= p7 “，吒越小，局部 9 浙江大学硕士学位论文 特征表现越强，反之办然。 与此力法类似，我们可以得到网格【：的高斯滤波的光顺与去噪算法。我们同 样在点模型上碰用双边滤波算法，选取适当的点模犁邻域即可实现该算法。 1 6 4 点模型m l s 曲面光顺去嗓算法 m l s 曲而是指移动最d - - 次( 拟合) 曲而，这是对点云曲面拟合的典型方法。 点模型m l s 曲面光顺去噪算法就是将点移动到局部拟合的m l s 曲面上来达到去 噪光顺的效果。类似于去噪方法的一般思路：本方法先从噪音模型中恢复出模型， 然后根据恢复的模型对噪音进行剔除。 l a n c a s t e r l 9 8 1 】提出m l s 方法。这个想法来源于加权最4 - - 乘方法 ( l s ) ，m l s 与w l s 不同的地方在于它将w l s 中固定点推广到整个定义域。一般 的，对于m l s 意义下的拟合函数f ( x ) 的定义为： ，( 功= 正，“磐z o ( 1 l z 一- , b l l s ( - , ) 一s , 1 1 2 ( 1 - 9 ) l l 兀：表示d 元i 1 1 次多项式的集合。 l e v i n l 9 9 8 】巾证明了f ( x ) 是连续可微的当且仅当权函数是连续可微的。 l e v i n2 0 0 1 】提出一种对离散点云进行m l s 拟合的步骤，使之可以被计 算机实现。 a l e x a2 0 0 1 利用m l s 拟合点模型| l f 面，并且应用m l s 于点模型的 重采样和简化，其中提出了简略的实现过程， a l e x a2 0 0 3 补充了 a l e x a2 0 0 1 的实现过程，提供了更多的细节。 0 浙江大学碘1 。学位论文 ( a )( b ) 图1 7 ( c ) 图1 7 是对点模型m l s 去嗓的效果。同样，该算法严重依赖邻域点的选择。 ( a ) 是噪声模型，( b ) 和( c ) 是6 次光顺以后的效果，( b ) 邻域半径大于( c ) 。 1 7 点模型重采样的相关工作 1 7 1 基于m l s 蓝面和v o r o n o i 图的重采样算法 和点模型m l s 曲面光顺去噪算法类似，该算法也是m l s 曲面的一个直接应用 【a l e x a2 0 0 1 】a 我们得到点模型局部的m l s 曲面以后，就相当于定义了一个拟合该点模型的 连续隐式曲面，然后在通过对邻域点在拟合平面上的投影作v o m n o i 罔量化点云 不同位置的稀疏程度，然后根据稀疏程度选择加点的优先级，然后在需要加点区 域里面将新采样点投影到m l s 上。 该算法的优点是加点均匀，町保持局部几何特征，但是依赖点的切平面和 v o r o n o i 图，耗时较人，无法满足实时绘制的需要。 1 7 2 基于r b f 隐式曲面的重采样算法 类似地，在m l s 曲面之前，利用r b f 隐式曲面重构点模型的方法已经被深入 研究。对点模型进行曲面重构本身就是一个重采样的过程 c a r r 2 0 0 1 。但是全 局r b f 重建速度慢， o h t a k e2 0 0 3 】， t o b o r2 0 0 4 】讨论了局部重建r b f 方 浙江大学碗十学位论文 法，但是计算量仍i h 昂贵。 以上两种算法都是在提取拟合曲面的基础上进行重采样，g f l l 既可用于高分 辨率绘制，又可用于几何信息的修复。它们的优点是能够保持数据点云的连续性 和原始模型的几何特征，但是计算量大，特别是应用大规模的数据点云的时候， 时间耗费过人。 1 7 3 动态面元集修复算法 g u e n n e b a u d2 0 0 4 】提出一种动态而元集修复算法。该算法是一种局部 点元插值算法，优点是速度快，可用于实时绘制。 该算法首先根据空间位置和法向一致性找出与点口几何信息相似的邻域点 集卉。，然后对邻域点集进行筛选得到目标邻域点集，使得点集分布均匀，最 后拟合p 和。中各点的插值多项式曲线，在曲线上根据需要作重采样。 见图l - l o ，( a ) 中，p 是中间的红点，周围五个白色的点是。，( b ) 是插值出来的点。 然后( c ) 、( d ) 不断插值。 图1 1 0 浙江大学碗十学位沦文 1 7 4 面向点模型f f d 的动态重采样算法 为了修复表面变形以后出现的空洞和裂缝，【p a u l y2 0 0 3 a 提出了面向点 模型f f d 的动态晕采样算法。该算法和f f d 联系紧密，它通过判定模型形变的方 向来判断点云稀疏的方向( 作为一种显式的形变方法，这点是町以达到的) 。 首先，存采样点切平面上建立一个正交坐标系，通过形变前后坐标系的变化 刻画点云的形变程度，进而判断是否要重采样，并且在需要的地方加上点，然后 通过势能最小原理使得采样点分布均匀。 器忒溉 图1 - 1 l 动态重采样算法图示 图l l l 1 7 5 快速的点模型重采样算法 k a n a m o r i2 0 0 5 针对点模型小尺度的几何信息的丢失提出一种快速的 点模型重采样( 修复) 算法，目的在于修复和恢复点模掣的几何细节。 该算法通过面元之间的覆盖关系判断重采样的位置和方向，即将点p 的邻 域点集投影到p 的切平面上，然后检查邻域点集的面元能否覆盖p 面元，如果不 能，找出还未覆盖的方向，并且在该方向上加点。 见图l 1 2 ，( a ) 说明重采样的策略，标为q 的面元皆为p 的邻域点，则，角度 内是需要晕采样的位置。中图和右图为该算法修复维纳斯点模型前后的效果 图。 浙 i 大学顿i 学位论文 ( a )( b ) 图1 1 2 ( c ) 该算法简洁直观但是依赖于点元半径，如果点元半径足够大足以弥补掉这些 小洞和缝隙，该算法就可能失效。 4 浙江大学坝 学位论文 1 8 本文工作及组织结构 1 8 i 本文贡献 本文基于 b u a d e s2 0 0 5 】和 t u r k1 9 9 2 a ， p a u l y2 0 0 3 a 等文献的 算法基础上，对点模型的去噪光顺和重采样两个关键问题进行探讨。总体来说， 本文贡献主要有以r 两点。 i 与以往局部的三维模型光顺去噪算法不同，本文提出一种非局部的去噪光 顺算法。该算法通过对原始噪音模型进行统计分析，自动提取噪音与特征信 息，其有自我预测判定的特点，具有保特征，保体积等同类局部算法不具有 的良好性质。 2 本文提出一种更具普适性的面向小尺度几何修复的重采样算法。该重采样 算法基于点切平面上的协方差分析和排斥力驱动的点均匀算法。能够保证修 复前后的几何信息保持一致。我们将此算法应用于点模型拉普拉斯编辑后模 型，3 d 扫描仪实测模型和拉普拉斯光顺后模型，均得到满意的效粜。 1 8 2 本文结构 本文第一章介绍了点扫描技术的意义和当前三维扫描点云数据几何处理的 相关技术。第二章介绍了我们的点模型非局部的去噪光顺算法。第三章介绍了。 种新的而向小尺度几何修复的重采样算法。第四章对本文工作作了总结而且对未 来的工作作一展望。 浙江太学硕士学位论文 第二章点模型上的n l 光顺去噪算法 2 1 引言 在信号处理理论中，噪声常被认为是一种随机高频信号，其频率大于某个人 为设定的闲值，并可通过各种窄域和频域滤波器对其进行平滑滤波，该概念办经 常在图像处理中出现，图像去噪的过程即为剔除夹杂在原始图像中噪声的过程。 而光顺是一个t 程上的概念，包括光滑和顺眼两方晦的含义。光滑是指空问曲线 和曲面的连续阶，数学上一阶导数连续的曲线即为光滑的曲线，而顺眼是人的主 观感觉评价。对于平面曲线，光顺需要满足以下几点：曲线c 2 连续，没有多余 拐点，曲率变化均匀。曲面的光顺更要求曲面上每一条曲线都是光顺的。在数学 上，判断曲面是否满足上述条件的依据是曲率信息。而对于离散数字模型，我们 难以严格要求其满足光顺条件，只是认为当模型的曲面曲率变化比较均匀时即为 光顺。数字几何处理中的去噪、滤波和光顺都是针对三维点模型和三维网格模型 的，三者概念略有差异，具体方法上亦有所不同，但目的都是一致的，即消除隐 含在三维模型中的噪声，让处理后的模型最真实地体现实物模型。 实际上，噪声和特征都是三维数字模型的某种几何属性。从不同的理论层面， 噪声和特征的区分具有不同的标准。类似图像处理，对于三维模型我们亦可通过 阈值来区分高频信息和低频信息。 基于局部信息保留低频凡何信号就是三维模型上的光顺去噤算法一大类。该 类算法通过卷积滤波的方法剔除设定闽值之上几何高频信号，其典型代表就是双 边滤波器。 本章提出的n l 去噪算法在噪音模型f ：自动提取噪音和特征信息，她对噪音 模型进行全局统计自动区分噪音和特征。与局部滤波类去噪光顺算法不同，新算 法更着眼于模型整体的几何信号分布来进行预测和判定。 浙扛大学坝i 学位沦文 2 2 相关知识和背景知识 2 2 1p c a 分析 p c a 原是数据统计中的一种数据分析方法。在三维点模型中，协方差分析用于估 计点模型表面的局部性质，例如法向量，和曲面变分等。 h o p p e1 9 9 2 ， s h a f f e r2 0 0 1 已经对p c a 方法在三维模型上的应用作了深入探讨。 存点模型i ：，点p 的协方差矩阵可以定义为： 定义一个点集p ；( p ) 是以点p 为中心的一个邻域，r ，玳或e n ( p ) ，其中芦是 点集p 的重心。由于矩阵c 是对称半正定的矩阵，其三个特征值五( i ：0 ，l ，2 ) 为非 负的实值，所对应的三个特征向量q ( i = 0 ，1 ，2 ) 组成一个正交基。假设九兰 t ， 用平面o 一声) = 0 i , j , - 乘拟合邻域点集，使得邻域点到此平面的距离和为最 小，此平面可以看成是点集p 的切平面。采样点p 的法向为，其曲面变分为 叽( ，) = 九( 五+ + 五) ，通过芦点以为法向量可以建立采样点p 处的一张切 甲面“一p ) v o = 0 。见图( 2 2 ) ： k 甜i 图2 一l 利用p c a 估计法向对于大规模点模型来说是快速有效的，但是由于其数学意义 的限制，当曲面曲率高而且没有足够的采样密度的话，法向会发生较大的偏差。 p a u l y2 0 0 3 b 中，p a u l y 等通过计算表明曲而变分吒( p ) 可以有效地作为曲而 曲率的一个估计。显然该估计依赖邻域的选取， p a u l y2 0 0 3 b 中利用控制邻 浙江大学坝十学位| 仑立 域达到对曲面局部滤波的效果。 2 2 2 图像上的n l 去噪算法 最近【b l l a d e 82 0 0 5 1 提出了一种新的图像去噪算子优劣的评价方法，即 所谓方法噪卢( m e t h o dn o i s e ) ，获得了广泛的关注。 设“为图像，n 为过滤算，h 为滤波参数，方法噪声定义为原始图像和已 滤波图像之问的差一q ”，该方法认为一种好的滤波算子不应该改变不带噪声 的图像，当滤波带有噪声的图像时，方法噪声中尽可能不包含原图像的结构。为 此他们提出了一种非局部化( n o n - l o c a lm e a n s ) 的图像去噪算法，我们简称其 为n l m e a n s ，该算法基于以下的简单的数学原理。设q 为图像，则图像中每个 像素滤波之后的灰度值为： 1( 吒f t ) 一o + 斧m o ) n l ( 州加赤p t “( y ) d y ( 2 - 2 ) “i h h n u + f 其中x n ，c ( = p t 方( 2 3 ) 为归一化常量玩为高斯核， h 为滤波参数。 该算法的数学含义是像素点x 去噪后的灰度值为所有与x 有相似高斯邻域 的点的灰度平均值。n l m e a n s 方法与局部滤波算了和基于频域滤波的算子的主 要区别为其系统地用到了图像中所有可能的自我预测的性质，文中已证明， n l ( u ) 0 ) 收敛于像素x 的基于其邻域像素对其的条件期望值。这种性质也用在了 图像的纹理合成中 h u2 0 0 5 。 2 3 点模型上的n l 去噪算法 2 3 1 算法概观 在采用非局部邻域光顺点模型的方法中。我们根据协方差分析方法计算出各 个点的切平面，采用双边滤波器算子计算出各个点“几何灰度值”，对各个点v 的 邻域点集( v ) 的几何灰度值进行相似度比较。通过然后采用n l m e a n s 方法计算 出该点最终的几何灰度值n l v 1 ，并在采样点沿其法向移动相应距离重建出该点 浙江人学蛾 学位沦文 的几何信息。 2 3 2 点模型上灰度值的定义 双边滤波器原用于网格模犁的光顺去噪 f l e i s h m a n2 0 0 3 】，也可将其赢 接推广到点模型的去噪中，我们通过如下方式计算 i i 每个点的离散坐标值6 0 ： = 避劣筹群 ( 2 - 4 ) 上式中，”为点v 的法向( v ) 是指点v 的邻域，形( z ) 是光顺高斯权，指 一， d lc r o 为标准差的高斯核：w a x ) = p ，t 越大，m 被光顺程度越大，反之亦 然。噬( x ) 是保特征高斯权，指以t 为标准差的高斯核：睨( 砷：f ，以越 小，c o 局部特征表现越强，反之亦然。 2 3 3 相似度比较 为了方便邻域之问相似度的比较，我们将邻域( v ) 投影到v 的切平面得 。( v ) ，再以v 为中心建立一个”x 栅格g v ( 所有不同采样点的邻域栅格都用统一 的问距h 且栅格的大小，即n ，取相同的值；该栅格包含在参数点之中，如图 2 所示1 。我们根据协方差分析方法计算各个点的切平面。 由于j v ( v ) 巾每个点与n ( v ) 相对应都有一个灰度值，我们可以通过插值方 法得到栅格每个格点灰度值。具体计算格式为：对q 中的每个格点，取其周围 的采样点进行插值。如图2 - 2 中所示，获得与点，相邻四个单元格r 卜皿的采样 参数点，取各采样点灰度值的高斯加权平均( 2 5 ) ，即为格点，的几何灰度值。 q 图2 2 浙江人学硕士学位论文 w = e x p ( 一慷一，2 )t ，= w 。( e ) + 她 ( 2 5 ) v ，e j ) 4 如果格点，相邻四个单元格中没有采样点，刚该点予以标记，在下续的邻 域相似性匹配计算中，该格点不用于计算，从而减小相似性匹配误差。值得注意 的是与点v 直接对应的，直接赋点v 的几何灰度值。 通过这种方法，我们就可以将每个采样点的邻域中每个点的几何灰度值转 化为其对应栅格g 每个格点。，的儿何灰度值。那么两个采样点_ 和_ 邻域之问 的相似度比较可以定义为其对应栅格q 和g j 之间的比较，如将q 其定义转为 n 月维变量r ( u ) ，则得下式： ：。帆协 ( 2 6 ) 其中4 7 “) 一r ( 叶) 。为高斯加权欧氏距离函数，a 是高斯核的标准方差。与_ 具 有高相似性度量的采样点v j 其相似度墨，_ 有较大的值。如图( 2 3 b ) 所示，图中p 与岛有较高的相似度，与p ：之间的相似度次之，与p l 之间的相似度最小。 ( a )( b ) 图2 3 邻域相似性比较。( a ) p l a n c k 模型，( b ) p l a n c k 模型点得几何灰度值得可 视化图。其中红色表示几何灰度值人的点，绿色的点几何灰度值最小，蓝绿色表 示介_ 丁两者之间。 浙江大学硬学位论文 2 3 4 灰度值调整 i ：述的采样点之间相似性的度量是我 f n l m e 柚s 方法的基础。为每个点邻 域建立一个局部的栅格后，我们采n l - m e a n s 方法对点模型中每点的邻域进行全 局的相似性匹配计算，通过对相似度值进行加权平均计算出该点最终的几何灰度 值n z ( o ，即： 眦【一】= g ( i , j ) o u f f j ) ( 2 7 ) t “ 其中权卢( f ，) 依赖于采样点v j ，o 相似度，满足条件o p ( f ，) 蔓l ，芦( i ，) = 1 ， 这些权定义为： g ( i ，) _ s v t 。z ( v ) ( 2 - 8 ) 其中z ( v ) 为归化常量，= ( q ) = s 。其中吖为点模型所有的点。由上式 t e ， 可知，对相似度小的采样点v 和v ，其影响权值卢u ，) 几乎为零；对相似度大的 采样点v ，和叶，赋予较大的影响权值卢( f ，) ，对v i 的最终灰度值z h 】有较大的 影响。 由于n l m e a n s 方法不仪考虑单个点的几何信息，而且比较整个模型的各采 样点的邻域之间几何信息( 如图2 3 b ) ，因此该方法较基于邻域的局部滤波算子 更加鲁棒。 斟为n l ( v ) 表示了在v 点的“灰度值”期望，即经过n l - m e a d s 方法我们估计 出了该点一个新的几何信息。假设v 的法向及其邻域内点位置不变，我们要沿v 法 向移动使得该点的“灰度值”成为n l ( v ) ，因为“灰度值”是v 邻域点到v 切平 面有向高度的加权平均，所以我们可以通过调整v 切平面的位置来调整邻域内点 到该点切平面有向高度，进而使得“灰度值”成为e ( v ) 。 在实际操作中，为了简化计算，我们在法线方向上移动( w ( v ) 一n l ( v ) ) 以达到该 效果。 寻= v + ( w ( v ) 一n l ( v ) ) y n ( 2 1 9 ) 由于我们的方法是沿法向方向移动采样点，凶此有效地避免了顶点漂移的情况。 我们的算法通常迭代一到两次即可获得满意的结果。在第二次迭代时需重新计算 浙江人学碟士学位论文 出各个点之间的相似度，并采用协方差重建出每个点的法向。图2 - 5 9 是我们采 用本文提出的方法获得的玄噪结果，迭代次数为二次。 2 4 实验结果 我们对点模型的n l m e a n s 去噪方法与其它的点模型去噪方法进行了全而的 比较。 在图2 - 4 中我们采用不同方泫对原始的光滑p l a n c k 模型( 图2 - 3a ) 进行光顺处 理，获得相应的m e t h o dn o i s e 的可视化结果。设点模型的原始点位置为v ，经过 非局部方法去噪后得到的几何位置为v 。，那么该点的m e t h o dn o i s e 定义为这两点 的欧式距离，即8 r 一川a 为了突 不同方法m e t h o dn o i s e 的差异，在对m e t h o d n o i s e 可视化之前，我们需要对膨j ，i = o 一1 作标准化。 删产 = 忆一_ 5 m ，是。经过第i 种去噪方法后得到新的顶点。 1 首先求出 日ei i = o m 一1 的均值和均方差。 m 即：。繁衙一2 2 对 朋mi i = o m 1 ) 作标准化。 m 噶= 芋t ( 2 1 0 ) ( 2 1 1 ) m 呓是标准化以后的m e t h o dn o i s e ，k 是尺度系数，用束调整可视化的效果，我们 这里取k = 1 5 m e t h o dn o i s e 大的点我们将其可视化为红色，次之为绿色，最小的为蓝色。 l a p l a c i a n 方法由于是局部几何信号的平均，在迭代过程中将出现特征被磨光的 情况；平均曲率流方法是点沿法向订向以该点的曲率的速率进行移动；这两种方 法都是各向同性的方法。它们的m e t h o dn o i s e 的可视化体现出原始模型的几何特 征( 图2 - 4 曲) 。各向异性方法所得到的m e t h o d n o i s e 的可视化亦含有原始模型的 几何特征( 图2 - 4c ) ，在这些方法中，双边滤波器方法( 图2 - 4d ) 是最接近我们 浙江大学砸士学位论文 n l - m e a n s 方法的结果，但光滑后的m e t h o dn o i s e 的可视化还是能表现出 些几 何特征。我们的n l - m e a n s 方法( 图2 - 4e ) 的m e t h o dn o i s e 的可视化结粜几乎看不 出模型的几何特征。图2 - 4f 中我们对原模型的曲率进行了可视化。不同点模型 去噪方法的m e t h o dn o i s e 可视化结果与图像去噪方法m e t h o dn o i s e 的可视化结果 2 0 1 类似。证明了我们方法的正确性。 图2 5 是我们分别用不同方法对人工加入随机噪声的p l a n c k 模型去噪的结 果，所有方法所用的采样点的邻域半径相同。l a p l a e i a n 方法h 现特征磨光现象， 且由于点小在法向方向进行移动将出现顶点漂移，导致光顺模型出现裂缝的情况 f 图2 - 5b ) 平均曲率流方法是点沿法向方向以该点的曲率的速率进行移动，为各 向同性的方法，因此亦出现特征磨光现象，但是没有出项顶点漂移的情况( 图2 - 5 c ) 。各向异性方法在迭代光顺中保留模型的特征同时剔除模型的噪声，但该算法 会使模型平坦区域或者局部的细节出现过度磨光的现象，甚至会出现退化的情 况，同时由于点模型是离散点组成，将出现过滤结果不光滑的情况( 图2 - 5d ) 。 m l s 方法由于是采用基于优化的局部多项式曲面拟合，通过将噪声点移至所逼 近曲面上达到去噪的目的，因此计算量大且计算且不鲁棒，难以保持点模型的特 征( 图2 5e ) ；另外m l s 方法最终依靠多项式曲面拟合，所以在某些点处会出 现顶点漂移。在这些方法中双边滤波器方法( 图2 - 5f ) 最接近我们的结果( 图 2 5ch ) 该算法处理稍大的噪声时会引起过光顺而不能有效地保持模趟的细小 特征，而且由于该算法仅仅利用单个点的局部信息，在处理稍大的噪声模型时计 算不稳定。从图中可咀看出我们的方法特征保留的更好，去噪结果更接近初始模 型( 图2 5 i ) 。 图2 6 是不同方法对扫描获得的噪声模型直接去噪所得结果的比较。该模型 是采用浙江大学c a d & c g 国家重点试验室所购置的手持式j 维扫描仪扫描所获 得。山图中结果可以看出，我们的方法比双边滤波器方法更好地保持了特征，并 且有效地剔除了模型的噪声。而l a p l a c i a n 方法所获得的结果由于顶点漂移而出 现了裂缝。图2 - 6e ，f ，g ，h 分别是对a ，b , e ，e 采用多尺度r b f 重建的结果，我们 采用y u t a k ao h t a k e 个人主页上提供的代码，并且所有重建结粜都采用同样的参 数。 本文提出的点模型n l - m e a n s 去噪算法通常迭代- - n 两次即可获得满意的 浙江大学顾f 学位论卫 结果。由于该算法需要