（应用数学专业论文）基于双边过滤的网格光顺法.pdf

论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果论文中 除了特别加以标注秘致谢的地方外，不包含其他人或其它机构已经发表或撰写 过的研究成果其他同志对本研究的启发和所做的贡献均已在论文中作了明确 的声明并表示了谢意 融名：啦喃翻蝉 论文使用授权声明 本入完全了解复旦大学有关保留、使用学位论文的规定即：学校有权保 留送交论文的复印停允许论文被查阅和借阗：学校可以公布论文的全部或部 分内容可以采用影印、缩印或其它复制手段保存论文保密的论文在解密后 遵守此规定 日期：塑z 兰翌 摘要 图像和图形的光顺在实际应用中非常重要和广泛，在逆向工程和计算机图形 学中，由于扫描的图形数据会出现噪点，一般在使用前需要对其进行光顺处理， 以提高网格模型的质量。如何在光顺时保持网格模型的特征成为提高光顺质量的 一个关键问题。上世纪九十年代末，人们提出了关于图像的双边光顺法，结合了 相近性函数和相似性权函数，构成了双边光顺法，由于其只是应用在二维图像上， 不能满足人们关于三维立体图形的光顺需求，于是在本世纪初，研究人员提出了 关于图形的双边光顺方法，通过顶点及其邻域构造过顶点的切平面，计算出顶点 的邻域点到平面的距离，对其进行加权平均，得到点迭代的光顺公式。由于使用 平面逼近顶点的局部区域有一定的局限性，故丽本文希望能够通过曲面逼近，在 双边网格光顺法的基础上，用网格顶点及其邻域点进行曲面拟合，构造抛物线， 计算出抛物线与z 轴的交点坐标，求出该交点到原点的距离，用其取代原方法中 点到平面的距离，得到改进的点迭代光顺公式。通过改进的方法与原来的方法相 比可知，改进的方法能够更好的保留原图形的特征。并且能够达到更好的光顺效 果。 关键词：各向异性；网格光顺；双边过滤：特征保留：曲面拟合。 4 a b s t r a c t t h es m o o t h i n gm e t h o do fi m a g e sa n dm e s h e si sv e r yi m p o r t a n ta n d e x t e n s i v ei no u rl i f e ，a n dt h es c a n n e dm e s h d a t am a yb en o i s e di nt h e r e v e r s ee n g i n e e r i n ga n dc o m p u t e rg r a p h i c s ，s oi ts h o u l db ef i l t e r e dt o i m p r o v et h eq u a lit yo ft h ei m a g ea n dm e s hf o rt h ef u r t h e rp r o c e s s i n g h o w t op r e s e r v et h ef e a t u r eo ft h ei m a g ea n dm e s hw h i l es m o o t h i n gi sak e y p r o b l e mt oi m p r o v et h eq u a l i t yo ft h ei m a g ea n dm e s h ，a tt h e9 0 so fl a s t c e n t u r y ，t h er e s e a r c h e r sg a v et h eb il a t e r a ls m o o t h i n gm e t h o do fi m a g eb y c o m b i n i n gt h ec l o s e n e s sf u n c t i o na n ds i m i l a r i t yf u a c t i o n b u tt h i sm e t h o d i s1i m it e dt o2 - d i m e n s i o ni m a g e ，n o tu s e f u lt ot h e3 - d i m e n s i o nm e s h s o i nt h ee a r l yo ft h i sc e n t u r y ，t h er e s e a r c h e rs o l v e dt h ep r o b l e mb yf i t t i n g ap l a n et h r o u g ht h ev e r t e xa n di t sn e i g h b o r s ，a n dc a l c u l a t i n gt h ew e i g h t e d d i s t a n c eb e t w e e nt h en e i g h b o rp o i n t sa n dt h ep l a n e ，t h e ng e t t i n ga s m o o t h i n gp o i n t i t e r a t i n gf o r m u l a b e c a u s eu s i n gap l a n et oa p p r o p r i a t e as m a l ls u r f a c ei sn o tv e r yu s e f u ls o m e t i m e s ，u s i n gh i g h e ro r d e rs u r f a c e t oa p p r o p r i a t et h es m a l ls u r f a c em a yb eb e t t e rt h a nt h ep l a n e t h i sp a p e r i sb a s e do nt h eb i l a t e r a lf i l t e r i n gm e t h o d ，a n dt h em a i ni d e ao ft h i sp a p e r i sf i t t i n gas u r f a c eb yt h ev e r t e xa n di t sn e i g h b o r sa n dc o n s t r u c t i n ga p a r a b o l at oc o m p u t et h en e wd i s t a n c ef r o mt h ei n t e r s e c tp o i n to fp a r a b o l a a n dza x i st ot h eo r i g i n a lp o i n t t h en e wf o r m u i ai sg a i n e db yu s i n gt h e n e wd i s t a n c et or e p l a c et h eo r i g i n a ld i s t a n c e t h en e wf o r m u l ac a n p r e s e r v et h ef e a t u r eb e t t e ra n dg e tb e t t e rs m o o t he f f e c tt h a nt h eo r i g i n a l f o r m u l at h r o u g ht e s t s k e yw o r d s ：a n i s o t r o p i c ：m e s hs m o o t h i n g ：b i l a t e r a lf i l t e r i n g ：f e a t u r e p r e s e r v i n g = s u r f a c ef i t t i n g 5 前言 随着科学技术突飞猛进的发展，计算机辅助设计与制造( c a d c a m ) 与计 算机辅助几何设计( c a g d ) 的技术运用得越来越广泛，在计算机图形学和逆向 工程中都有广泛的应用。由于测量过程中测锝的是离散点数据，缺乏必要的特征 信息，往往存在数字化误差，需要对曲面和曲线进行光顺。光顺是一个工程上的 概念，包括光滑和顺眼两方面的含义。光滑是指空间曲线和曲面的连续阶，数学 上一阶导数连续的曲线即为光滑的蛆线；而顺眼是人的主观感觉评价。随着用于 坐标测量的硬件设备的迅速发展，运用各种工具能够测得几十万、上百万甚至更 多的海量数据。但在运用各种工具进行测量的过程中都会或多或少地受到各种噪 声和扰动的影响，这样就会在模拟的形体中出现一些十分狭长的三角片而造成形 体走样，为了满足形体的几何精度有必要对数据进行光顺处理。 在8 0 年代对曲面光顺的研究上，人们一般的想法是通过对控制点的插值拟 合等手段来构造需要的曲面，这种曲面一般都可以用具体的数学表达式表示出 来，或者是可以构造出满足一定的连续性的曲面( 见【l 】，【2 】) 。但是随着时间的发 展，在实际应用中许多曲面并不一定都是可以显式表达出来的，也并不一定需要 其满足某种连续性，为了满足人们的这种要求，在9 0 年代研究人员就较少考虑 通过控制点构造曲面，而是对整体控制点提出了一些具体的方法，例如通过用 l a p l a c e 算子得到的偏微分方程构造点的迭代公式：通过对信号的处理，过滤掉 其中的高频部分，得到新的改进后的数据( 见 1 2 】) ：通过雨伞算子构造递归的 迭代公式( 见 6 】) ；通过求最小的体积变化和曲率整体积分的最小值来进行光顺 ( 见 1 4 1 ，【1 5 】) ；还有m c f ( 平均曲率流) 法进行过滤等( 见【3 】，【刀，【1 7 】) 随着人们对图形要求的提高，9 0 年代的网格过滤由于较少的考虑到网格的特征， 因此光顺后的图形不一定能够满足用户的需求，于是在9 0 年代后期研究人员就 开始寻找保特征的网格光顺法，到目前为止，已经取得了不小的成绩。例如 j o n e s e t a le ”在2 0 0 3 年提出了非迭代保特征的网格过滤法，该方法利用了顶点的 邻域点到三角片所在平面的距离进行加权平均，构造出点的迭代公式，与以往的 点迭代公式不同的是，该方法只需要进行一次迭代就可以达到很好的效果，而不 需要多次迭代，尤其是对于浮雕类扫描图形的效果更好。f l e i s h m a a e t a l t s i 提出了 6 双边网格去噪法，该方法是关于灰度和色彩图像的双边过滤法的引申，把图像过 滤法从二维扩展到三维图形，同时通过引入保特征因子，使双边去噪法在对三维 图形光顺的同时能够很好地保留原有图形的特征。双边去噪法是通过计算顶点的 邻域点到过顶点且垂直于顶点法方向的平面的距离，对其进行加权平均来构造点 迭代公式。这种方法的运算速度很快，而且对曲面的去噪能够达到很好的效果。 c h u n y e n c h e n e t a l l 6 1 于2 0 0 5 年通过研究提出了基于面法向量的光顺算法，一 般光顺文章中的法向量都是采用的顶点法向，所得到的光顺公式也都是基于顶点 法向量的，而c h u n - y o n c h e r t e t a l 则是通过定义面邻域对面法向量进行加权，缛 到面法向量，同时定义一个关于面法向量的权函数，利用网格图形的特征，使其 在特征明显即曲率变化大的地方权函数接近l ，在特征不明显的地方即曲率变化 小的地方，权函数接近0 ：通过点的迭代公式进行光顺，当达到用户的要求时， 停止迭代，此时得到的网格就是比较光顺的网格；这种方法的速度快而且效果很 好，对绝大多数图形都可以达到很好的效果，是近年来网格光顺研究中比较有价 值的方法之一。本文余下部分安排如下： 本文在第一章中介绍了c t o m a s i 和r m a n d u c h i 在1 9 9 8 年所提出的图像 双边光顺法，给出了关于区域光顺( d o m a i nf i l t e r i n g ) 和范围光顺( r a n g e f i l t e r i n g ) 的概念，二者的结合构成了图像的双边光顺法，并结合例子说明图像 的双边过滤法对图像光顺的效果。 本文在第二章中简单介绍了s h a c h a rf | e i s h m a n 和i d d od r o r i 等于2 0 0 3 年在 图像双边光顺法的基础上给出的图形双边过滤法。图形双边过滤法是对图像双边 过滤法的扩展，图像的双边过滤法是对二维图像的光顺，而图形的双边过滤法是 在图像的双边过滤法的基础上进行改进，进而提出针对三维网格的双边光顺方 法。 本文第三章中主要介绍了在网格双边过滤法基础上的改进，通过顶点及其邻 域点拟合曲面局部逼近原图形，在拟合的曲面上计算每一个邻域点的切平面，对 每一个切平面，可以构造出一条抛物线，对于该抛物线可以计算出一个距离；对 每一个邻域点可以得到一个距离，对所有顶点邻域点得到的距离加权平均，就可 以得到点迭代公式。最后，由例子可以看出，此公式可以很好地对网格图形进行 光顺并保留其特征 7 第一章图像的双边光顺 这一章主要介绍了有关图像的双边光顺法，图像的双边光顺法是在对图像区 域过滤和范围过滤研究的基础上提出来的。单独地使用区域过滤和范围过滤对图 像进行光顾虽然都能达到一定的光顾效果，但不是很理想。c t o m a s i 和 r m a n d u c h i 发现把二者结合起来对图像进行光顺能够得到二者单独光顺所没有 的效果，而且通过理论分析证明二者的结合能够很好的对图像进行光顺，因而提 出了图像的双边光顾法。 1 1图像的区域过滤与范围过滤 设f ( x ) 表示图像在x 处的值，由于扫描的图像是由象素点构成的，故当x 取 所有的象素点时，灭x ) 就表示了一张2 维的图像，用c ( 磊x ) 表示x 的相邻点善 与z 在几何距离上的相近关系，即f 与x 的距离越近，孝对x 的影响就越大。 当把图像( x ) 通过过滤器后，就会产生输出的图像。用h ( x ) 来表示输出图像， 其表达式如下： i l ( 朋= 掣( ，( 和g ，加西 ( 1 1 1 ) 其中巧1 ( ) 为正规化因子，其表达式如下： 毛( 加= c ( 善，z ) d 善 ( 1 1 2 ) 由( 1 1 1 ) 、( 1 1 2 ) 可以知道，矗( 石) 只是对x 点附近的点的值进行了平均处理， 把它称为几何上的紧密性，把c 僧，肖) 叫做区域性函数，把应用公式( 1 1 i ) 、( 1 1 2 ) 的过滤器称为区域性的过滤器( d o m a i nf i l t e r i n g ) 。 一般来说，离图像x 越近的点对j 的影响越大，在图像处理中不但要考 虑到z 点处，( x ) 的值即图像的灰度值，对于彩色图片，还要考虑到z 点处的 光度值。与公式( 1 i i ) ( 1 1 2 ) 相似，关于对光度相似性的公式如下： ( ) = f ( x ) 厂( 毋s o q o ，( j o ) 苗 ( 1 1 3 ) 其中 七，= j u ，厂( 烤 ( 1 1 4 ) 为正规化因子，j ( 厂( f ) ，( x ) ) 表示在j 的邻域点善处的光度相似性，也把它叫做 范围函数，把( i i 3 ) 、( 1 1 4 ) 两式组成的过滤器称为范围过滤器o r a n g e f i l t e r i n g ) 。 因此，可以知道函数j ( ，( 0 ，( x ) ) 是对图像在光度方面的处理，使输出的图像在 色彩上看起来不会出现很大的差别，不会出现很明显的色差。 1 2 图像的双边过滤与离散化 由上对图像的区域过滤与范围过滤可知，( 1 1 1 ) 、( i 1 2 ) 两个式子是对图像距 离几何上的处理，( 1 1 3 ) 、( 1 1 4 ) 两个式子是对图像光度上的处理，是从人的视 觉角度出发的，把几何上的光顺和光度上的光顺结合起来，称为关于图像的双边 光顺法。结合起来的光顺公式可以如下表示： j i l ( z ) ：k - i ( x ) f = f = ( 善) c g ，x ) j ( ( o ，( x ) ) 苗 ( 1 2 1 ) 七( 柳= ，( 毋c ( 善，j 。j u ( o ，( 烤 ( 1 2 2 ) 由( 1 2 1 ) 、( 1 2 2 ) 可以看出，象素点x 的值是由它周边象素点的值和光度相似 度的平均值决定的。在光滑的区域，较小范围内的象素点在距离和亮度上都非常 接近，故k q s 的值接近于l ，因此，当某一区域出现噪点时，通过( 1 2 1 ) 、( 1 2 2 ) 式子的作用，会使由噪点引起的不同象素值之间的差别缩小，起到光顺的作用。 下面给出关于图像的双边过滤法的一些实例。考虑变化比较大的区域，例如 出现尖边的地方，一边是较暗的，一边是比较亮的，如图l ( a ) 所示，当中心 点在比较亮的一边时，相似性函数s 接近于l 在比较亮的区域，而在比较暗的区 域趋近于0 ；图l ( b ) 所示，选取相似性函数s 的支集区域为2 3 2 3 的象素点域， 对所有的象素点来说，正规化因子保证了所有的系数和为1 ，那么较亮的象素点 的象素值则由其周边较亮的象素点的值平均得到，而其较暗的象素点由于s 接近 于0 ，其影响可以忽略不计同样的，当象素点在较暗的一边时，较亮的象素点 9 的影响也可以忽略不计。图l ( c ) 所示，由于过滤器的区域性，边界可以达到 很好的效果，由于亮度的关系，边界的曲边( c r i s pe d g e ) 被很好的保留了下来。 ( i ) ( c ) 图( n ) 为经过盯= 1 0 的c r o w s 加噪处堡的结果：图( b ) 所选区域 为2 3 x 2 3 的点邻域，结合了相似性权函数c ( f ，x ) s u ( 孝) ，( x ) ) 对图像( a ) 光顾后的结果；圉( c ) 所选区域为5 x5 韵点邻域，通过 双边过滤的效果可以看出，区域较小时效果越好 公式( 1 i 1 ) ( 1 2 2 ) 中的积分下标都是从一到 3 0 的，在实际应用中。一 般只对所选择区域内的点有意义，对区域外的点来说权函数一般取为0 ，即公式 可以写为离散的形式，例如公式( 1 工1 ) 来说，其离散的表达式如下： 居( 加= 七。1 ( 柳厂( 专弦( 磊，柳j ( ，( 毒) ，厂( 幻) ( 1 2 3 ) 七( 柳= 吣，朋j ( 厂( 当) ，厂( x ) ) ( 1 “2 ) l e n 其中j 为所选取的x 点的邻域，六为札内的点，用户可以根据需要选取自己想 要的邻域大小，一般来说，邻域越小，效果越好；也可以自己调节参数达到想要 的效果。 1 3区域过滤与范围过滤结合的必要。陛 前面讲了把区域性函数和范围函数结合起来，组成双边光顺的过滤器。下 面给出理论证明来说明这种结合是非常必要的。为了概念上的简单起见，只对黑 白图像进行讨论，对彩色图像来说，类似的结论也成立。若只对图像应用深度过 滤器，可以看出它只改变了图像的灰度映射，这给人直观上的感觉是过滤后的图 1 0 像缺乏空间立体感。令v ( ) 为输入图像的灰度频率分布函数。在离散的情况下， v ( 加是一个灰度直方图：妒一般为0 到2 5 5 之闻的整数，“彩是灰度值为的象 素点的函数；在连续的情况下，v ( ) 彩是关于图像区域的函数，其区域象素点的 灰度值在到+ d 之间。为了与前面的概念一致，下面仍然考虑连续的情况。 为了简单起见，把象素点的空问区间设置为【o ，+ ) ，与公式( 1 2 1 ) ，( i 2 2 ) 相似，深度光顺表达式可以写为如下形式： = f 矿t ( 妒，力d ( 1 3 1 ) 其中： t ( 蟊，) ：堕q 丛盟一 ( 1 3 2 ) lj ( 以，) l ，( 可以看出公式( 1 3 2 ) 是对灰度图像的简单变换。映射核函数t ( 妒，力为一个密度 函数，是非负的并且lt ( 矽，门和= 1 。由于t ( 妒，力为密度函数，故而方程( 1 3 1 ) 代表了一个平均值，因此可以得出下面的结论： 深度过滤器只改变输入图像的灰度映射，改变的灰度值等于以灰度值为的 象素点为中心其周围象素点直方图的加权的平均值，权函数为深度相似性函数 j ，其中心灰度值也为厂。 在讨论双边过滤器的时候，对灰度映射转换的分析还是很重要的。一般来说， 它会压缩图像的直方图。考虑简单的单峰的直方图，如下图( a ) 所示，考虑输 入值为以，为中心的对称曲线，故而相似性函数也是对称的，乘积卵就会产生 一个偏斜密度函数，左边的密度会向右边偏斜，右边的也会向左边偏斜。由于转 换值函数h 为偏斜密度的平均值，由于在左边h ，故而直方图 向中间压缩。 可以看到，深度过滤的结果是一个简单的深度映射，而且看起来效果并不好。 但是当深度过滤与区域性过滤结合起来组成双边过滤器时，光顺的效果就起了 圈( a ) 实线表示单峰图像的直方图，虚线表示相似性函数s ，点线表示 正规化乘子r 可看出其向右馆斜：田( b ) 中表示光顾不同步的图像实 线表示圈i ( a ) 的直方圈，虚线表示图l ( c ) 的直方田 很大的变化。假设，区域过滤函数c 只在一个小窗口处为常数，其它地方为0 ， 那么双边过滤器在这个窗口上就只是一个深度过滤器，那么光顺的效果也只是灰 度值的一个简单映射，但有趣的是，在不同的点的灰度映射是不同的。如上图的 ( b ) ，显示了光顺不同步的直方图的情形。实线表示图l ( a ) 直方图，可以看 出压缩的效果是显然的，虚线表示对图l ( c ) 光顺后的直方图。 第二章网格的双边光顺 随着需求的提高，有时需要对三维的网格进行光顺，图像的光顺已经不能满 足人们的需要。因此，s h a c h a rf l e i s h m a a 和i d d od r o r i 等在研究了图像双边光顺 法的基础上，提出了关于三维网格的双边过滤法，其思想主要是通过对项点构造 一张平面，利用所有邻域点到平面的距离计算出加权平均距离，进而构造出关于 网格的双边过滤法。可以知道，这种方法是对图像双边光顺法的扩展，把其应用 从二维扩充到了三维。 2 1 顶点的法向量计算 对于扫描的网格图形来说，顶点的法向量有多种表达方法，最简单的就是 对顶点相邻的每一个面，求出垂直于面的单位法向量，然后对所有的单位法向量 加权平均求出最后的法向量。 设s 表示无噪点的曲面，肘表示扫描仪对样本s 扫描后的输入曲面，由 于扫描仪和人员操作等的关系，肘带有一些额外的噪点。g ，表示v 点的邻域点， ( f = 0 ，l ，坍) 如图( 1 ) 所示，v 点有5 个相邻的面，对每一个面利用两条边的向 量叉乘后单位化，既可以得出此邻面的法向量；一，表示v 点的法向量，n ( v ) 表 示v 点的邻域，h i , 表示邻面厂。的法向量，则顶点的表达式可以写为： w ，刀，j 驴昔 图( 1 ) 1 3 ( 2 1 i ) 为其权函数；最简单的情形，取为常数1 ，若要在后面的光顺中得到更好 的效果，可以取a 球，) ，即三角形的面积， 例如文章【9 】所用的 擎1 竺孥五些：州 上一l j 卜i 一 卿“z ) 篓毹等5 。喜黼i q , i h i q 酬台| 2 | | g 1 2 台i 川0 公式( 2 1 2 ) 、( 2 1 3 ) 处为了方便起见，经过了坐标平移， 为顶点的点法线，f 为使其等式成立的系数。 2 ，2 切平面及加权平均距离 ( 2 1 2 ) ( 2 1 ，3 ) 把v 点作为坐标原点， 令v e m 为膨的一个顶点，以表示点v 至j j m 的带有方向的距离，即若点y 在 曲面s 的内部，则磊方向指向s 外侧，若d o 在s 的外部，则磊的方向指向s 的 内侧，由于v 离s 比较近，所取的距离也是v 到s 的一个局部小片的距离，表 示曲面s 上到点v 距离最小的点的法向量。由于无噪点曲面s 的未知性，故而以、 也是未知的，因此用扫描的网格吖的法向量来代替曲面s 的法向量，用根据 肘得到的距离d 来代替或。 下面根据公式( 2 i 2 ) 或( 2 1 3 ) 中的法方向来计算切平面，求出一个新的偏 差d ，即点到切平面的距离。由于s 是未知的，定义s c s 是曲面s 上距离顶点 v 最近的曲面片，用y 点所有邻域点 9 0 的偏差来估计v 点的偏差。图( 2 ) 表示v 点的一环邻域，用由( v 疗) 定义的切平面作为对曲面片s ，的逼近，邻域点吼的偏 差为其到切平面的距离，如图( 3 ) 所示，即过v 点傲垂直于方向，l 的平面。对每 一个顶点，都可以得到一个切平面；同样，对每一个顶点，用所有邻域点的偏差 1 4 进行加权平均表示顶点 i f 的加权平均距离；那么，有多少个顶点，就可以得到多 少个加权平均距离。 v 电农 2 3 网格的双边过滤法 上面对每一个顶点求出了切平面和加权平均距离，下面就可以构造点迭代公 式对已有的网格点求新的v 点，其公式如下： v = ，- i - d 疗( 2 j i ) a 其中 1 1 表示迭代后新的顶点，d 表示关于v 点的加权平均距离，是通过点到平面 的距离计算出来的，n 表示顶点v 的法向量。 由上式可以看出，每次只迭代一个顶点，计算出每次迭代的位移，更新顶点 位置。参考关于图像的双边过滤法，设图形为l ( u ) 。建立坐标系材= ( x , y ) ，位移 按照如下定义： 形d p 一“d 形硼，( 一，( p 咖，( p ) 砸卜鼍氯再砺丽而矿 q 3 可以看出公式( 2 3 2 ) 是离散的表达形式，其中( “) 表示甜的邻域， w o 硼p - , , i b 为关于几何距离的光顺函数， w 。( x ) = e x p ( - x 2 2 吒2 ) 时，此时为关 于参数吒的标准g a u s s 过滤器；保特征的权函数，也叫相似性权函数 形( 刁= x p ( - - x 2 2 一) 是作为惩罚函数出现的，通过参数c r j 对亮度差别较大的地 方进行光顺。实际中，( “) 由点列 g 。) 构成，吼满足：肛一酬 p = 1 2 巳l 。 由上可知，知道该方法的主要是通过，用过顶点的平面来局部逼近曲面，一 方面这是个很好的局部逼近，另一方面可以保留图形的特征，对曲面光顺方法的 一般要求是首先可以对曲面进行很好的光顺，其次在光顺的基础上很好的保留曲 面的特征。因此，利用顶点邻域的法线加权平均来计算顶点的法线，有时候也选 取顶点邻域三角形的面积作为权。对邻域的选取可以很好的达到局部光顺的效 果。使用曲面的邻域的平均值进行光顺，只可能使顶点的局部变得平滑，而不会 产生过度的光顺效果，例如对拼接的曲面，即一个曲面是有很多曲面片拼合的， 在拼接处的顶点，其周围的法向量变化是很大的，使用局部平均的光顺可以使拼 接处显得更加自然。 对切平面来说，两点问的距离测量应该用测地线来计算，由于使用了局部 的逼近，为了方便起见，用欧基里德距离来代替测地线距离。但也有缺点，就是 在某些特殊的情况下，如尖边处，欧基里德距离很短，测地线却有可能很长。另 外，由微分几何可知，一个点的邻域并不总是可以由过该点的切平面来近似逼近 的。但是，由于引入了相似性权函数，也可以叫惩罚函数，它的变量为邻域点到 切平面的距离，即使出现了上面两种情况中的一种，如若，与q 间的测地线很长， 那么吼对，点的影响应该很小的，但v 与吼的几何距离有可能很小，故而 形0 i v q ，d 会产生很大的影响；可是由于邻域点叮，到切平面的距离与其它邻域点 相比却可能很大，那么相似性权函数这时就发挥了作用，即彬0 l ，( v ) 一，( p ) 移比较 小，故而使吼对v 的影响降低了，所以上面两种情况对双边网格算法并不能产生 大的影响。 2 4 参数的选取 关于参数的选取，公式( 2 3 2 ) 中包含两个参数：盯。、盯，还有关于邻域大 小的选取参数p 和迭代的步数。用户可以根据自己的需要设置所有的参数，并调 1 6 节参数直至得到自己想要的结果，参数吒、矿，是可以交互分配的，当用户选择 了需要光顾的网格上的一个点时，那么这个点的邻域就可以定义下来。一般来说， 把半径参数p 设置为和c r c 有关一般设置p = 2 吒，巳的设置就是所选邻域关 于偏差的标准偏离值。 当选取较大的o r c 时，在迭代的过程中就可以进行比较少的步骤，当仃。的选 取较小时，也叫做窄带过滤器，则需要进行比较多的迭代步骤对以取较大值 时，迭代的步骤少，出现的效果一般比较租糙，而且由于邻域选取的比较大，每 一步迭代的计算也比较耗时间；其次，由于邻域的范围大，对特征的保留就无法 起到较好的效果；所以一般选取比较小的以，由于邻域选取的较小，每一步迭 代计算上更快，而且也更精确，每一步迭代对特征的保留也更好。 有关区域的选择，也可以选取顶点的l 一环邻域，但有时由于噪点的影响， 用l 一环邻域来计算顶点的法向量，会出现不稳定的情况，这时也可以选取2 - - 环邻域来计算顶点的点法向量：对于噪点及其严重的情况，则需要选取更大的区 域，例如顶点的k - - 环邻域，( k = 3 ，4 ) 。 2 5网格双边光顺法举例 下面显示的图形是用网格的双边过滤法光顺的。除了m a x p t a n c k 是用2 - - 环 邻域计算点的法向量的，其余都是用l 一环邻域来计算顶点的法向量的。通过对 图形的比较，可以看出根据图像双边过滤法提出的网格光顺法在对图形的光顺上 也能够起到很好的效果，说明网格的双边过滤法很好的继承了图像双边过滤法的 优点，其主要也是通过对权函数的继承来实现的。 下面的例子分别显示了双边过滤法对图形的光顺结果。第一幅图显示了双边 过滤法作用在图形上得到的光顺结果，可以看出效果还是很好的。第二幅图主要 显示了双边过滤法对网格作用产生的收缩效果，由于是通过平面来逼近网格邻 域，所以会出现一定的收缩效应。第三幅图也显示了其对网格的光顺效果，并且 通过曲率进行显示，迸一步说明了网格光顺法对网格光顾其效果的明显性。第四 幅图显示了网格双边光顺法对网格光顺时的特征保留情况。 图( a )图( b ) 光顾效果；田( a ) 为输入的严重带臻的图形；田( b ) 为阿格的双边过滤法 光顾5 次的结果可以看出网格的双边过滤法可以起到很好的光顺效果 ( a )c o )( c ) 收缩问题：图( a ) 为m 戤p l a n c k 模型，其有很多噪点图( b ) 为双边同格 光腰4 次后的结果可以看出图( b ) 比图( a ) 要产生轻微的收缩圈( c ) 为 m 践p l a n 吐模型的鼻子，可以看出双边光顾法是同格变的光滑 ( a )( b )(c)(d) 圈( a ) 为扫描的带嗓点的输入图形：图( b ) 为网格双边去噪法光腰 5 次后的结果：圈( c ) 和圉( d ) 分别是图( 8 ) 和( b ) 的通过平均 曲率显示；可看出罔格的双边去噪法效果还是很好的 1 8 圈( b )圈( c ) 特征的保留：田( a ) 为输入的带嘬点图形，田( b ) 为通过同格双边过滤 法光冁5 次后的结果；图( c ) 为匿的局部表示，可以看出月格的双 边过滤法肘特征的保留也起到了很好的作用 由上面的图形可以看出，网格双边过滤法对图形的光顺还是可以达到很好的 效果，同时也说明了关于图像的双边过滤法权函数结合的正确性。下一章我们将 说明在双边网格光顺的基础上改进的光顺法。 1 9 第三章改进的网格双边光顺法 本章主要介绍了在对网格双边过滤法研究的基础上，提出用拟合曲面代替原 有的平面来逼近局部的邻域，通过构造抛物线来计算距离，取代原有的点到平面 的距离，计算出加权平均距离，模仿网格的双边过滤法构造新的点迭代公式，并 通过例子和原有的网格双边过滤法进行比较来说明这种改进是有意义的。 3 1 网格双边光顺法分析 由于网格的双边光顺法是通过选取过顶点的切平面来逼近s 的，那么过顶点 的切平面就是选取的一个很重要的元素，如果把平面放在所有邻域点偏移的平均 值处，将会对网格的双边光顺起到很大的改进但是，这样做会否认相似性权函 数，即惩罚函数的作用故而，希望能够用一个更高阶的函数，比如低阶的多项 式来计算邻域点的偏离值，这样更能够减小收缩影响。但由实际经验知道，找到 这样的高阶函数很困难。下面将尝试通过拟合曲面和构造抛物线的方法来计算减 小顶点邻域偏离值对顶点的影响，从而达到更好的效果。 网格双边过滤法的思想主要是切平面的选取以及顶点沿着法线方向的移 动，然而这种移动有时候会导致噪点网格的自交，当把算法应用到一条边的两个 顶点上时，每一个顶点都向内侧移动，对尖边来说，在几步迭代后会产生自交。 由上可知。关于双边过滤法首先是研究人员对二维图像光顾的研究，提出了 区域过滤与深度过滤结合的方法，并在实践中证明是很有效的由于其仅限于对 图像的光顺。并不能满足人们的对于三维光顺的需求于是，相似于图像的双边 过滤，又提出了关于图形的双边过滤法，其主要通过计算顶点的法向量，构造垂 直于顶点法向量的平面，利用顶点邻域点到平面的距离得到加权平均距离，进而 构造出基于图像双边过滤的网格双边过滤公式。但是，由于其利用了平面来逼近 顶点邻域，也有其一定的局限性，并不是平面都能够很好地局部逼近曲面的。那 么，可不可以用曲面来局部逼近曲面呢? 如果可以的话，逼近以后要怎样利用逼 近曲面的性质，怎样才能与网格的双边过滤法结合起来，对其进行很好的改进? 这些都是我们需要思考的问题。 3 2三次曲面的构造 设m 为扫描的网格图形，v m 为其一个顶点，屹，y z ，码为y 的一环邻域点，如点的邻域图所示。由于光顺的目的不光是为了去掉噪点，还要 尽可能的保留原有图形的特征。为了得到改进的光顺公式，下面将要对点进行局 部的曲面拟合，用拟合的曲面表示该点附近原有的曲面。一般来说，双变量的多 项式逼近能够较好的近似该点附近的原有曲面，见文章【5 】。由于目前已有很多 关于如何从图形中提取网格特征的方法，这些方法通过拟合曲面，对阀值设定来 控制所提取特征的显著性。此处为了得到较好的保特征的效果，所拟合的曲面采 用了【8 】中的三次曲面。具体做法如下：以v 点为坐标圆点，引入局部坐标( x ， y ，z ) ，用i ，和v i ，屹，v 3 v 。拟合一个过坐标圆点的三次曲面z = 力， 其表达式如下： 1 h ( x ， = ( 6 0 一+ 2 b i x y + b 2 y 2 ) + ( 岛z 3 + 工2 y + 3 c 2 x y 2 - i c ，j ，) ( 3 2 1 2 ) 二 u 其中b o ，b ，b 2 ，c 。，c ，c 2 , 白为多项式的系数根据文章 8 可知，用上述方法拟合 的曲面可以较好地提取原来图形的特征，并且在后面的处理中能够对图形特征的 保留起到好的效果。 3 3抛物线的构造 上面得到了关于顶点的拟合曲面，有了这个曲面，就可以在曲面的基础上求 出相应的邻域点的切线，进而可以在所选的平面内构造一条抛物线，通过抛物线 与z 轴的交点计算出新的距离，对新的距离加权平均后就可以得到改进的公式。 设v 。- v ：，v 3 在曲面 ( 工，力上对应的投影点分别为“，t ， v ；t ，在拟合的曲面上对v ：，v ：，v ；t 分别求相应的切平面，用过v ：， 也，嵋t 点的切平面来近似表示过叶tv ：，屹的切平面。把过v ：， t ，t v ：点求出的相应切平面，记为c 1 ，g ，c 3 q 2 1 为了叙述的方便，下面只对切平面c l 进行说明，其它平面类似。对切平面c i ， 设其表达式为：a o x + a l y + a 2 z + 吩= 0 ，其中口o ，口l ，口2 ，a 3 为相关系数；连 接点，和嵋，由线段y h 和z 轴可以确定一个平面，记为d ，设其表达式为： 口：石+ 口：j ，= 0 其中瓦，a i 为相关系数，由于过2 轴和原点，故：对应的系数和 常数项为0 。设，为平面c i 和q 的交线，可求出i t 为： 。a 。o 。x + 。a 。! y ，一+ 。a 2 z + 。码。 ( ，：。) 称为过点v ：在vv i 方向的切向量，则可求出，l 的表达式为： 等2号2-xh，(x,y)-yhy(x,y) ( 3 3 2 ) 一工 一y 点的郐域图 抛物线与z 轴相交 其中o ，y ，z ) 为q 点的坐标，以( x ，y ) ，机( 工，j ，) 表示对x 和y 的偏导数，对其余切 平面同样处理。下面在平面内构造一条抛物线，通过构造抛物线可以求出其 与z 轴交点的坐标，进而得到在法线方向新的距离，也就是z 轴的坐标数。做法 如下：以v 为原点在原坐标系内进行坐标变换，由于 ，为坐标原点，且后面计算 所用到的参数都是在线段vv t 上取的，设垂直于z 轴的坐标轴为1 1 轴，故其变换 公式可以写为下式： f z = 2 t ：、：可 ( 3 3 3 ) 其抛物线为： z = b o u 2 + 6 l “+ 6 2 ( 3 3 4 ) 其中b o ，6 l ，b ：为相关系数，由于存在三个未知数，要决定一条抛物线，必须 使其满足相应的条件，为了得到好的光顾效果，现构造抛物线使其满足下面三个 条件： 抛物线过v ：点； 抛物线在v ：点的切向量为0 2 + y 2 ，x j + y 以) ； 1 在点 + ( v - v 1 ) 处的切向量与( v 一“) 平行； j 有了上述三个条件就可以唯一的决定一条抛物线。条件和的切向量有可 能一样，但是在实际中这样的情况不多，可以忽略不记。下面可以求出该抛物线 与z 轴的交点，记为( o ，0 ，d ：) ，用d ：代替公式( 2 2 1 ) 中的吐，若所求的d ：不小 于公式( 2 2 2 ) 中的( p ) ，就令d l ；，( p ) 。可知对每一个顶点，它的一环邻域有 多少个点，就可以得到多少个新的距离t ，见图( 抛物线与z 轴相交) 。 3 4利用曲面求出光顺公式 由上可知，对v 的所有邻域点可以求出新的距离以，对其进行加权平均，可 以得到新的加权平均距离。记为j ( v ) ，公式如下： 1 ( v ) k 以一弗咖。- p d 正 = 自 h k 积一巾彬咖。- p ；移 i i l 同样，新的光顺公式变为： 1 ，。= v + i ( v ) n 其中| h | 表示两点间的距离， ( 3 4 1 ) ( 3 4 2 ) k ( 力= e 一，7 研，w a x ) = p 。7 研 ( 3 4 3 ) 为标准的g a u s s 函数。 吒和分别为用户进行调节的参数a 文中的例子和公式都是采用了一环邻 域来计算和表述的，在实际中用户可以根据自己的需要定义邻域，例如可以定义 为： ，啊- 2 万1 尉，叫 ， 为到v 点的平均距离，表示v 点的邻域个数，满足条件 | | ，一v ，i j ，町， ( 3 4 5 ) 的点为其邻域点，形为用户自己定义的参数。同时也可以用二环邻域进行曲面 的拟合，并且公式( 3 4 1 ) 中的邻域大小也可以调节，下面的例子都是用一环邻 域拟合得到的结果。 由于抛物线的确定需要三个条件，本文虽然给出了三个条件来确定抛 物线，但是并没有给出为什么选择这三个条件的理由，只是在试验中发现选择在 v ：+ 鲁( y 一“) 处的切向量与( v v ：) 平行能够达到比较好的效果，如果在线段vv ： 间选择其他的点，在点迭代的过程中，网格的顶点产生自交的可能性比较大，即 该顶点移动到网格的内部。如下图所示： 带噪点的图形产生自交的图形 不带噪点的图形 可以看出中间的图形是由于产生了自交点，左边和右边的图形分别表示噪点 图形和不带噪点的图形。在对噪点图形进行处理时，发现对参数吒和c r i 进行调 整，得出的图形只是影响光顺的效果，只有对中点的选取对图形的影响较大， 若选取的点不恰当，得出的图形差别就很大，产生自交的可能性也就很大，因此， 对条件 的选取要谨慎。 许多扫描的网格，扫描的数据点并不是封闭的。网格点相连组成的图形中间 存在空洞，即存在边界点，这些点对网格的光顺有很大影响。对于边界点来说， 一些邻域点是没有定义的，通常的方法是在边界上定义一个虚拟的邻域点，把关 于虚拟点的权函数设置为0 ，那么关于边界点也可以很好的进行光顺了。 3 5实例分析 本节运用新的方法，对一些图形进行了光顺，并且和原来的方法进行了比 较。图4 a 表示带有噪点的图形，图铀是用网格双边过滤法光顾8 次得到的效果， 图4 c 是用改进的网格双边过滤法光顺8 次得到的效果，图4 d 表示原来的图形。 可以看处网格双边过滤法对图形的处理具有展平的效果，容易使图形失真，而改 进的网格双边过滤法由于在迭代过程中所选取的距离对每一次迭代来说，其变化 都不大于网格双边过滤法中所选取的距离，故而改进的网格双边过滤法在一定某 种程度阻止了这种展平。图5 a ，图5 b ，图5 c ，图5 d 分别表示带噪点的图形， 网格双边过滤法光顺8 次的图行，改进的网格双边过滤法光顺8 次的图形和不带 噪点的图形。可以看到在松鼠的手臂弯的地方，其变化最明显，网格双边过滤法 基本上没有起到保特征的效果，而改进的网格双边过滤法则起到了保特征的效 果，这主要是由于拟合曲面在手臂弯处与平面相比可以得到好的效果。图6 a ， 图6 b ，图6 c 表示带噪点的八面体图形，网格双边过滤法光顺6 次的结果和改进 的网格双边过滤法光顺6 次的结果，可以看出在八面体的棱角处改进的网格双边 圈4 a图4 b田4 c 圈4 d 圈4 a 袭示扫描的带有严重噪点的图形；圈4 b 表示利用方法同格 的双边过滤法光顺8 次的到的圈形：田4 c 表示利用改进的罔格光 顾法光顾8 次得到的结果；圈4 d 表示不带噪点的图形 图5 a圈5 b圈5 c圈5 d 图5 a 表示带噪点的图形；圈5 b 表示同格双边过滤法光顾 b 次得到的图形；图5 c 表示改进的同格双边过滤法光顾8 次得到的图形；圈5 d 表示不带噪点的田形即标准圈： 圉曲田6 b 田6 c 圈6 a 表示带噪点的八面体田形i 圈6 b