（计算机应用技术专业论文）基于多分辨率分析的鲁棒网格水印.pdf

摘要 摘要 当前的数字水印技术大多是针对文本、图像，视频、音频等媒体数据类型， 而对三维几何模型的数字水印技术的研究工作相对较少。但是，随着虚拟现实和 w e b 3 d 技术的飞速发展，以及越来越多的基于c a d 的三维数据在互联网上传 播，关于三维几何模型的数字水印技术的研究，正成为数字水印技术研究中的新 热点。三维几何模型一般用多边形网格来表示，所以对三维几何模型的数字水印 技术的研究，一般都是把多边形网格作为水印嵌入对象，本文称之为网格水印。 和图像水印类似，网格水印也可以从空域和变换域两个方面着手。目前，网 格水印大多是在空域进行，鲁棒性较差。本文基于网格多分辨率分析的思想，提 出了一种新的变换域的鲁棒网格水印算法。该算法首先将原始不规则网格重新网 格化，得到一个多分辨率表示的半规则嬲格；然后运用提升方法对此半规则网格 进行小波变换，得到一个最低分辨率的基网格和一系列的小波系数；最后通过修 改小波系数嵌入水印信息。在水印嵌入时，对网格小波系数进行统计分析，选择 较低分辨率的小波系数嵌入水印，并对小波系数的不同分量设计不同的嵌入强 度。 实验表明，本文提出的水印算法满足不可见性，并具有较强的鲁棒性。 关键词网格水印，多分辨率分析，提升方法，网格细分，攻击分析 a b s t r a c t c u r r e n tw a t e r m a r k i n gt e c h n o l o g yf o c u s e so nm e d i at y p e sl i k et e x t ，i m a g e s ，v i d e o a n da u d i os t r e a m s i nc o n t r a s t ，t h ep r o b l e mo f w a t e r m a r k i n g3 d m o d e l sh a sr e c e i v e d l e s sa t t e n t i o nf r o mr e s e a r c h e r s w i t ht h er a p i d d e v e l o p m e n to fv i r t u a lr e a l i t y a n d w e b 3 d ，a n dm o r ea n d1 t t o r e c a d - b a s e d3 dd a t ae n t e r i n gt h ew o r l dw i d ew e b ， w a t e r m a r k i n g f o r g e o m e t r y b a s e d 3 dm o d e l si s b e c o m i n gan e wh o t s p o t i nt h e r e s e a r c ho f d i g i t a lw a t e r m a r k i n g g e o m e t r y - b a s e d 3 dm o d e l sc a n a l w a y s b e r e p r e s e n t e du s i n gp o l y g o nm e s h e s ，s o w a t e r m a r k i n g f o r t h e m ，c a l l e d m e s h w a t e r m a r k i n g i nt h i sa r t i c l e ，a l w a y st a k et h ep o l y g o nm e s h e sa se m b e d d i n gt a r g e t l i k ei m a g ew a t e r m a r k i n g ，m e s hw a t e r m a r k i n gc a nb ec l a s s i f i e da st h es p a t i a l d o m a i n w a t e r m a r k i n ga n d t h et r a n s f o r m e dd o m a i nw a t e r m a r k i n g m o s to ft h ec u r r e n t m e s h w a t e r m a r k i n g i sd o n ei ns p a t i a ld o m a i na n dh a sl e s sr o b u s t n e s s i nt h i sa r t i c l e ，a n e wr o b u s tw a t e r m a r k i n gm e t h o di sp r e s e n t e db a s e do nt h em u l t i r e s o l u t i o na n a l y s i s f o rm e s h e s f i r s t ，t h eo r i g i n a li r r e g u l a rm e s hi sc o n v e r t e di n t oas e m i - r e g u l a rm e s hb y r e m e s h i n g a f t e r w a r d ，t h em e s h i sd e c o m p o s e di n t oac o a r s e s tb a s em e s ha n das e to f w a v e l e tc o e f f i c i e n tv e c t o r sb ya p p l y i n gt h ew a v e l e tt r a n s f o r mb a s e do nl i m n gs c h e m e f i n a l l y ，t h e w a t e r m a r k si s e m b e d d i n g i n t ot h em e s hb ym o d i f i e dt h ew a v e l e t c o e f f i c i e n t , ，e c t o r s a f t e rs t a t i s t i c a la n a l y s i si su s e di nt h ew a v e l e tc o e f f i c i e n tv e c t o r s o fm e s h e s ，t h ew a t e r m a r k sa r ee m b e d d e di nt h ew a v e l e tc o e f f i c i e n tv e c t o r si nt h e l o w - r e s o l u t i o n p a r t s e x p e r i m e n t a lr e s u l t sa n da t t a c ka n a l y s i ss h o w t h a tt h i sn e wa l g o r i t h mh a sm o r e r o b u s t n e s s k e y w o r d s ：m e s hw a t e r m a r k i n g ，m u l f i r e s o l u t i o n a n a l y s i s ，l i f t i n gs c h e m e ，m e s h s u b d i v i s i o n ，a t t a c ka n a l y s i s ，i i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：叠也嘲型乒 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 繇矬聊繇垡! 照嗍 第1 章绪论 1 1 引言 第1 章绪论 随着数字技术和i n t e r a c t 的发展，各种形式的多媒体数字作品( 图像、视频、 音频等) 纷纷以网络形式发表，其版权保护成为一个迫切需要解决的问题。自从 1 9 9 4 年s c h y n d e l t l 】提出数字水印的概念以来，有关数字水印技术的研究，己成为 多媒体信息安全领域研究的一个热点，也是信息隐藏 2 技术研究领域的重要分 支。 当前的数字水印技术大多是针对文本、静态图像、视频流和音频流这些媒体 数据类型的，而对三维几何模型的数字水印技术的研究工作相对较少。但是，随 着虚拟现实和w e b 3 d 技术的飞速发展，以及越来越多的基于c a d 的三维数据 在互联网上传播，我们可以预见，将来用户所购买的不再是一个实物的产品或零 件，而是一个造型的思想或一些数据由点、线、面等构成的三维几何模型， 只有那些被授权的用户才可以对该模型进行复制、修改，这就涉及到如何对其进 行版权保护的问题。数字水印技术提供了一种有效的途径，使得可以在这些三维 几何模型数据中嵌入数字水印。1 9 9 7 年，o h b u c h i 8 发表了第一篇关于三维几何 模型数字水印的文章后，这一研究领域已逐渐成为数字水印研究的新热点，也将 在多媒体版权保护领域具有广泛的应用前景。 三维几何模型一般用多边形网格来表示，所以对三维几何模型的数字水印技 术的研究，一般都是把多边形网格作为水印嵌入对象，本文称之为网格水印。 1 2 数字水印的相关知识 1 2 1 数字水印的基本概念 数字水印是实现版权保护的有效办法，它通过在源数据中嵌入秘密信息 水印来证实该数据的所有权，这种被嵌入的水印可以是一段文字、序列号、图像 等。水印通常是不可见的，它与源数据紧密结合并隐藏其中，成为源数据不可分 离的一部分，并可以经历一些不破坏源数据使用价值或商用价值的操作而保存下 来。举个简单的例子来说明数字水印的概念。 a l i c e 制作了一个3 d 图形，并在网上商店发布。b o b 复制了以后，进行一定 的修改，然后声称是他的作品，也在网上发布。那么，a l i c e 如何证明这个3 d 图形是她的，并要求王宝作出相应的赔偿呢? 数字水印技术可以很好的解决这个 问题，使a l i c e 的版权得到了保护。 a l i c e 首先通过某种特定的水印嵌入算法，在原始的3 d 图形中嵌入了版权信 息( 序列号、文字等) ；当b o b 非法复制并修改后，a l i c e 通过某种特定的水印提 取算法，从可疑的3 d 图形中提取出来水印，即版权信息，就可以证明b o b 非法 复制并修改后的3 d 图形是属于她的，并可以通过法律措施要求b o b 作出赔偿。 数字水印系统的基本模型2 2 1 如图1 1 所示。 ( w t e m 出e m b e d d i n g e 破r a d e d w a e r r n a r k 臣歪蚕 哟w a t e m a r ke x t m d t i o n 图i - 1数字水印系统的基本模型 1 2 2 数字水印的特点 根据信息隐藏的目的和技术要求，数字水印应该具有以下基本特点： ( 1 ) 不可见性( i m p e r c e p t i b i l i t y ) ：水印嵌入到源数据后，人眼无法感知， 而且嵌入水印后的数据必须没有明显的降质现象； ( 2 ) 鲁棒性( r o b u s t n e s s ) ：嵌入水印后的数据，能够抵抗各种处理和攻击 第1 章绪论 而水印信息不会丢失。对于网格来讲，所谓的处理和攻击包括：旋转、平移、比 例缩放、网格简化、随杌噪声、部分裁剪、二次水印等。 除了以上的基本特性外，网格水印还应该具有以下一些额外特性1 3 】，这样， 水印算法的功能会更加完善。这些额外特性包括： ( 1 ) 适当的运行速度：网格的数据量一般比较大，所设计的算法计算量不 能太大，以至影响运行速度； ( 2 ) 尽可能少的先验数据知识：一个理想的水印系统提取过程仅仅需要知 道源数据和个密钥： ( 3 ) 尽可能少的预处理开销：一个理想的水印系统应该允许直接访问嵌入 了水印的模型数据，而不需要对其进行预处理。 1 2 3 数字水印的分类 数字水印的分类方法主要有以下几种： ( 1 ) 按源数据的类型分：文本水印阢32 1 、图像水印即 、视频水印m3 0 】、音 频水印【2 ，2 8 1 、网格水印 8 - 2 7 1 等。 ( 2 ) 按水印的鲁棒性分：鲁棒水印【4 5 ，7 ，1 8 2 2 2 4 2 2 , 2 6 1 、脆弱水e p 6 ，1 9 2 0 1 。鲁 棒水印主要用于版权保护，而脆弱水印主要用于数据完整性验证( 篡改提示) 。 ( 3 ) 按水印检测的方法分：公有水印、私有水印。公有水印检测时需要源 数据，而私有水印则不需要。 ( 4 ) 按水印嵌入的方法分：空域水印 3 8 1 3 1 8 2 1 l 和变换域水e 1 1 4 ，5 t 7 ，2 2 2 4 , 2 ”。 空域水印直接对源数据进行修改，计算简单，效率较高，但鲁棒性较差；而变换 域水印通过对源数据进行一定的变换后再嵌入水印，计算复杂，但鲁棒性较强。 空域水印和变换域水印的系统模型2 2 姗图1 2 所示。 1 2 4 数字水印的攻击分析 数字水印的攻击主要有以下几种： ( 1 ) 鲁棒性攻击：在不损害模型使用价值的前提下减弱、移去或破坏水印 北京工业大学工学硕士学位论文 使所有者无法检查到水印。 ( 2 ) 解释攻击：这种攻击在面对检测到的水印证据时，试图捏造出种种解 释来证明其无效。设源数据为，加入水印的数据为，。= ，+ 。攻击者首 先生成自己的水印，然后创建一个伪造的源数据0 = ，。一，即，。= ，+ 睇， 这就产生无法分辨与解释的情况。防止这一攻击的有效办法就是研究不可逆水印 嵌入算法。 ( 3 ) 法学攻击：这种攻击方法不受技术上或科学上的证据或结论的限制， 需要版权保护等方面的法律制度上的完善才能有效的避免这种攻击a o r i g i n a l d a t a e t e r m a m e d o a 切 ( a ) s p a t i a lo o r n a i nw a 炯a 眦n g m e t h o d o 刊r i g i n a li ，t 赫r a n s f o r m d a t a m o c l i f l c a t i o n o n t h o f r o q u e f l c yd a t a m e d i f i e d f r e q u e n c y r d 刁t a i n v 日r s o t r a n s f or m t o 怕s p a - 自a 10 0 m a i n f f t d c t w a v e l e t f 腑r n 巾lf r g o j e n c vd o m a i nw e t e r m a r k i n am q t h o d 图 - 2 空域水印和变换域水印 1 3 网格水印的研究现状 1 3 1 网格水印的难点和基本思想 w a t o m a 叠d d a t a 与图像水印相比，网格水印的研究工作还刚刚起步。由于网格数据自身的特 点，使得传统的图像水印算法不能简单推广应用于网格水印中。具体来说，网格 水印存在以下一些难点： ( 1 ) 由于网格数据是不规则采样数据集，所以在水印算法设计时，缺乏进 第1 章绪论 行频率分解的有效方法。静止图像可以按照象素点的平面位置排序，音频流和视 频流数据可以按照时间轴来排序，而网格数据没有一个固定的排序标准。所以， 对于网格这种不规则数据，需要将其转换成具有一定特性的半规则数据。 ( 2 ) 网格的数据量十分庞大，在设计水印算法时，必须有效解决算法的效 率问题。 ( 3 ) 水印检测过程中，网格简化等操作和其它的攻击方法可能会改变网格 的拓扑结构。在水印检测前，需要参照原始网格的连接关系对攻击后的网格进行 重采样处理，以便能正确的提取水印信息。 和图像水印一样，网格水印也可从空域和变换域两个方面着手。 空域水印直接修改网格信息，算法设计比较简单，但鲁棒性差。网格信息包 括几何信息、拓扑信息、属性信息三个部分，所以空域水印可以分别把几何信息、 拓扑信息、属性信息作为嵌入目标。 变换域水印先对原始不规则网格进行重新网格化，得到一个半规则网格，然 后基于这个半规则网格设计水印算法。这种算法设计比较复杂，但鲁棒性强。 下面。分别从空域和变换域两个方面对网格水印的研究现状进行简单介绍。 1 3 2 空域网格水印 1 9 9 7 年，o h b u c h i 发表了第一篇网格水印的文章，之后，他又发表了一系列 的网格水印的文章 8 - 1 0 1 。其中，比较有代表性的算法有三角形相似四元组( t r i a n g l e s i m i l a r i t yq u a d r u p l e ，t s q ) 算法、四面体体积比( t e t r a h e d r a l v o l u m er a t i o ，t v r ) 算法、剥离三角形带符号序列( t r i a n g l es t r i pp e e l i n gs y m b o ls e q u e n c e ，t s p s ) 算 法、基于属性调整的算法、网格密度模式( m e s hd e n s i t yp a t t e r n ，m d p ) 算法等。 t s q 算法把网格的几何信息作为嵌入目标。该算法利用了相似三角形的概 念，用二元组 b a ， c 或尥，0 z j 定义了一组相似三角形，如图1 - 3 所示。另外， 将相邻的4 个三角形作为一个嵌入基元( m a c r o e m e b e d d i n gp r i m i t i v e ，m e p ) ，每 个m e p 存储一个四元组 m a r k e r ，s u b s c r i p t ，d a t a l ，d a t a 2 ，分别用m 、s 、d 1 、 d 2 表示，如图1 3 b 所示。m e p 中，m a r k e r 用来唯一标识该m e p ，s u b s c r i p t 为 北京工业大学工学碗士学位论文 索引值，d a t a l 和d a t a 2 为要嵌入的数据符号。水印嵌入时，首先遍历所有网格， 寻找个合适的m e p ，通过先后修改三角形m 、s 、d 1 、d 2 中的二元组 6 q c j 分别嵌入m a r k e r 、s u b s c r i p t 和两个数据，重复这一嵌入过程直到所有的水印数 据嵌入完毕。t s q 算法能够抵抗平移、旋转、比例缩放等攻击，通过重复嵌入 水印后也能抵抗剪切和局部变形的攻击，但该算法不能抵抗网格简化等攻击。 t s p s 算法把网格的拓扑信息作为嵌入目标，嵌入基元为一个三角形带中的 一对三角形的位置邻接关系，如图1 4 所示。该算法的原始网格模型是有方向的 三角形网格，水印数据是一个二值序列，水印被嵌入到一个三角形带中。水印嵌 入时，根据水印数据生成一个三角形带，然后将三角形带从原始网格中剥离出来， 仅保留一条初始边与原始网格相连，原始网格中留下的空洞仍然由三角形条带覆 盖，在视觉上感觉不到变化。这种算法可以抵抗几何变换的攻击，通过多次嵌入 水印，可以抵抗剪切攻击，但不能抵抗网格简化等攻击。再者，该算法能够嵌入 的水印数据的容量比较低。 a 二元缝 b a 。 ，c l hm e p 中的4 个相议三角形 图1 3t s q 算法 瓠 黼淑 图1 _ 4t s p s 算法( 嵌入“1 0 1 0 1 1 0 1 0 1 1 ”) 第1 苹绪论 基于属性调整的算法把网格的属性信息作为嵌入目标。对于存在纹理映射的 多边形网格，可以通过改变纹理映射坐标或每个坐标顶点的属性( 如顶点颜色值) 来嵌入水印。该算法将水印数据比特流中每一个比特位的值( o 或1 ) 调制为纹 理映射中的坐标改变量，实现水印数据的嵌入。 上述o h b u c h i 提出的水印算法为数字水印的研究提供了新思路，但由于算法 设计过于简单，鲁棒性较差，因此无法应用于实际的版权保护。 b e n e d e n s 1 3 - 1 7 1 也提出了一些空域水印算法，如基于法向调整【1 3 1 5 1 的算法、顶 点束算法【1 4 、三角形束算法【1 4 等。前者通过修改三角形面法向嵌入水印，能够 抵抗一定的网格简化的攻击，后两者是用于模型验证的脆弱水印。2 0 0 0 年， b e n e d e n s 和b u s c h 又提出了一种仿射变换不变的网格水印算法【“” ，并基于该 算法开发了g e o m a r k 3 3 1 系统，用于3 d 模型和虚拟场景的数字水印嵌入。 1 3 3 变换域网格水印 1 9 9 8 年，k a n a i 2 2 1 基于l o u n s b e r y 4 3 】提出的网格多分辨率小波分解的思想， 第一次提出了变换域的网格水印算法。该算法首先对原始网格v o 进行多次小波 变换，得到一个粗糙的基网格v 。和一组小波系数形1 ，矿2 ，。，然后通过小波 一1 2 d 系数嵌入水印，再根据基网格v 。和修改后的小波系数矿，进行小波反 0 变换，得到嵌入水印后的网格v 。水印嵌入算法如图1 5 所示。该算法鲁棒性 较强，但只适用于具有细分连接性的半规则网格( 见2 3 2 ) 。 1 9 9 9 年，p r a u n 1 8 1 基于h o p p e 提出的渐进网格表示口6 1 ( p r o g r e s s i v e m e s h e s ， p m ) ，提出了一种鲁棒网格水印。该算法选择一系列在点分裂( v e r t e xs p l i t ，见 2 2 1 ) 操作中引起最大几何变化的点，对这些网格顶点构造一组标量基函数，水 印嵌入则是沿表面法矢方向对网格顶点坐标用基函数进行加权轻微扰动。针对网 格简化和其他改变网格连接关系的攻击，该算法根据原始网格的连接关系，用优 化方法对受攻击的网格进行重采样处理。这种水印技术对一般的网格操作，如平 移、旋转、比例缩放、剪切、平滑、简化等都有较好的鲁棒性。但是，该算法计 算量比较大。 北京工业大学工学硕士学位论文 图1 5 基于多分辨率小波分解的网格水印算法 2 0 0 1 年，o h b u c h i 2 6 3 基于t a u b i n 5 0 3 提出的网格频谱分析的思想，提出了一种 变换域网格水印算法。该算法首先从网格的连接关系中获取拉普拉斯矩阵 5 1 5 2 1 ， 然后对拉普拉斯矩阵进行特征值分解，将网格顶点的坐标投影到拉普拉斯矩阵的 特征向量上，得到一组谱系数，水印的嵌入通过修改谱系数实现。该算法有较好 的鲁棒性，能够抵抗仿射变换、顶点坐标的随机噪声、网格平滑、局部剪切等攻 击，缺点是计算量大，只能处理较小的模型。2 0 0 2 年，o h b u c h i e 2 7 1 对该算法进行 了改进和扩展，新的算法不但提高了水印嵌入的速度，还提高了水印对网格简化 和组合攻击的鲁棒性。 国内学者对数字水印的研究多集中于图像水印，而对网格水印的研究还比较 少，其中有代表性的成果主要集中在浙江大学c a d & c g 国家重点实验室。2 0 0 0 年和2 0 0 1 年，尹康康等分别对v r m l 场景中的纹理水印和鲁棒网格水印2 4 进行了研究。在网格水印方面，他们用一个松弛算子构造一个b u t t a d c l s o n 金字 塔结构，并在最终得到的粗糙网格中嵌入水印。该算法鲁棒性较强，但构造 b u g a d e l s o n 金字塔比较复杂，计算量较大。 1 4 本文主要研究内容 本文基于网格多分辨率分析的思想，提出了一种新的变换域的鲁棒网格水印 算法。该算法首先将原始不规则网格重新网格化，得到一个多分辨率表示的半规 第l 章绪论 则网格：然后运用提升方法对此半规则网格进行小波变换，得到一个粗糙的基网 格和一系列的小波系数；最后最后通过修改小波系数嵌入水印信息。实验表明， 该算法具有较好的鲁棒性。在水印嵌入时，对网格小波系数进行统计分析，选择 较低分辨率的小波系数嵌入水印，并对小波系数的不同分量设计不同的嵌入强 度。 实验表明，本文提出的水印算法满足不可见性，并具有较强的鲁棒性。 1 5 本文结构 本文第一章介绍了数字水印的一些基本知识，分析了网格水印面临的困难及 其基本思想，并对国内外关于网格水印的研究现状进行综述；第二章介绍了网格 多分辨率分析的基本思想，并分析如何对网格进行重新网格化，运用提升方法进 行小波变换等；第三章基于网格多分辨率分析的基本思想，提出了一种新的变换 域的鲁棒网格水印算法，对水印的嵌入、提取算法进行详细设计；第四章给出实 验结果，对水印算法进行攻击分析；最后对课题进行总结，对将来的研究进行展 望。 1 6 小结 本章首先分析了网格水印的研究背景，介绍了数字水印的基本知识，并对网 格水印面临的困难进行分析，总结了网格水印的基本思想。然后，对国内外关于 网格水印的研究现状进行综述。最后，介绍了本文的主要研究内容和本文的结构 安排。 北京工业大学工学硕士学位论文 2 1 引言 第2 章网格的多分辨率分析 三维几何模型在计算机图形学、虚拟现实、计算机辅助设计、地理信息系统、 医学图像系统等领域得到了广泛应用。这些模型数据通常用多边形网格来表示， 而三角形网格表示是三维几何模型表示中最普遍的一种表示方式。由于其它三维 模型表示都可以转换成三角形网格表示，所以本文主要针对三角形网格表示研究 数字水印技术。 图2 1 是一个简单的金字塔网格模型，由四个三角形面和一个四边形面组成。 通常，通过三维扫描设备获取的网格数据都十分庞大，包括数以万计甚至更多的 三角形面。图2 2 中的维纳斯( v e n u s ) 头像就是一个比较复杂的网格模型，它 有1 9 8 ，6 5 8 个顶点，3 9 7 ，3 1 2 个三角形面。 图2 1一个简单的金字塔网格 图2 - 2v e n u s 头像网格 第2 章嗍梧的多分辨翠分析 网格数据一般可分为三个部分：几何数据，拓扑数据，属性数据。几何数据 包括网格中所有点的坐标值，一般用浮点数表示；拓扑数据包括所有的三角形面， 每个三角形面用组成这个面的三个顶点的索引表示；属性数据包括网格的颜色、 纹理、材质等。图2 1 中列出了金字塔网格的几何数据和拓扑数据。本文不考虑 网格的属性数据。 下面对本文涉及的一些概念、术语进行定义。 三角形网格 删：三角形网格埘用( p ，足) 来表示，其中户描述几何数据，k 描 述拓扑数据。几何数据p = 伽( _ ，y ，毛) 月31 1 i ，其中是指网格中顶 点的个数；拓扑数据k 包括所有的三角形面，每个三角形用 f ，j ，七 来表示。 现在，已经有很多不同的文件格式来保存网格数据，立d w a v e f r o n t 的o b j 格式、 v r m l ( v i r t u a l r e a l i t y m o d e l i n g l a n g u a g e ) 的w r l 格式、a n i m a t o r p r o 的p l y 格 式、m i c h a e lg a r l a n d 的s m f ( s i m p l em o d e lf i l ef o r m a t ) 格式、c a l t e e h ( 加州理 工学院) 的d a t 3 卅格式。 顶点的度：网格中所有和该顶点相连接的顶点的个数。如果一个顶点的度是 6 ，则称之为规则顶点( r e g u l a r v e r t e x ) ，否则称之为额外顶点( e x t r a o r d i n a r y v e r t e x ) 。 根据顶点的度，网格可以划分为三类【4 ”。 规则网格( r e g u l a r ) ：网格中每个顶点的度都是6 ，即网格中不含额外顶点。 不规则网格( i r r e g u l a r ) ：网格中顶点的度可以为任意数。 半规则网络( s e m i r e g u l a r ) ：从一个粗糙的不规则网格开始，通过不断的四 等分( q u a d r i s e c t i o n ) 获得的网格，具有细分连接性h 3 1 ( s u b d i v i s i o nc o n n e c t i v i t y ) ， 如图2 3 所示。半规则网格中，除粗糙网格中的顶点有额外顶点外，其它所有顶 点都是规则顶点。 公念 ( a ) 【4 i b )( c ) 图2 3 网格三角形面的四等分 初始三角形面；( b ) 一次四等分：( b ) 两次四等分 1 1 北京工业大学工学硕士学位论文 如果网格中的一条边只属于一个面，则这条边称为边界边( b o u n d a r ye d g e ) ， 而这条边的两个顶点称为边界点( b o u n d a r y v e r t e x ) 。 如果一个网格中，除边界边外，其它所有的边都由两个不同的面共享，则称 之为流形( m a n i f o l d ) 网格，否则称之为非流形( n o n m a m f o l d ) 网格。本文只考 虑流形网格。 由于网格模型变得越来越复杂，三角形面片的数目变得十分庞大，相关的处 理计算十分复杂，传统的网格模型绘制方法采用固定分辨率，并不考虑网格模型 各部分的贡献大小而一视同仁，这种处理方法是十分低效的。为了解决这个问题， 近年来提出了网格的多分辨率表示方法【3 6 ，3 9 。4 3 1 。 事实上，对于离视点较远的部分，许多不重要的细节完全可以忽略而不会影 响整个网格模型的质量，使用较为粗糙的模型进行绘制就可以了。那么，如果对 网格模型进行多分辨率分析( m u l t i r e s o l u t i o n a n a l y s i s ，m r a ) ，根据网格模型的 贡献大小来选择该物体相应分辨率下的简化模型，就可以使得绘制效率大大提 高，而效果完全相同或者差距在给定的范围内。通过这种方法获得的网格表示， 就称为网格的多分辨率表示( m u r k e s o l u t i o nr e p r e s e n t a t i o n ，m r r ) 。 一个网格模型的多分辨率表示是由该模型和所有它的简化模型组成，构造过 程描述如下：以最复杂的原始网格模型作为输入，利用网格简化等方法产生不同 分辨率级的网格模型和细节信息；在显示或其他处理中，根据需要对原始网格模 型的不同部分用不同的分辨率加以描述。 习惯上，以mo 表示最精细( 分辨率最高) 的原始网格，以m 表示比较精细 的网格，以m 川表示比较粗糙的网格。，越大，分辨率越低。 2 2 重新网格化 通常，原始网格都是不规则网格，不便于处理，需要将其转换成半规则网格 或规则网格，这个过程称为重新网格化1 3 9 加，4 ”( r e m e s h i n g ) 。重新网格化后的新 网格由于具有细分连接性，使得小波分析【4 3 l 、信号处理i 删等理论及工具可以推 广应用到网格数据中。特别提出的是，基于提升【删( 1 i f t i n g ) 和细分【3 7 3 8 ，5 4 5 5 】的 第2 荤网梧的多分辨率分析 第二代小波 4 6 , 4 7 在网格压缩【4 8 4 9 3 中已经扮演着很重要的角色。 重新网格化的基本过程描述如下：对原始网格进行简化，得到一个最粗糙的 基网格( b a s em e s h ) ，基网格可以是不规则的，相对原始网格庞大的数据量来讲， 基网格只有很少的顶点和三角形面：在简化的同时，对原始网格进行参数化 ( p a r a m e t e r i z a t i o n ) ，建立从原始网格到基网格( 或其它参数域) 的映射；对基 网格进行连续四等分，并将每个新引入的顶点反映射到原始网格表面，得到重采 样后( r e s a m p l i n g ) 的点。由于新引入的每个顶点的度都是6 ，所以获得的网格 是具有细分连接性的半规则网格或规则网格。 已经有很多种重新网格化的方法提出，如m a p s l 4 1 ( m u l f i r e s o l u t i o na d a p t i v e p a r a m e t e r i z a t i o no f s u r f a c e s ，m a p s ) 方法、n o r m a lm e s h e s 【4 2 】方法等。下面简单 介绍一下网格简化和这两种重新网格化方法。 2 2 1 网格简化 网格简化是指在保持原模型几何形状不变的前提下，采用适当的算法减少该 模型的面片数、边数和顶点数。网格简化的本质是：在尽可能保持原始模型特征 的情况下，最大限度地减少原始模型的三角形和顶点的数目。通常，网格简化方 法分为静态和动态两种。 h o p p e 3 6 1 在s i g g r a p h 9 6 上提出了一种以边收缩( e d g ec o l l a p s e ) 为基本操 作的简化方法，网格重建时，以点分裂( v e r t e xs p l i t ) 为基本操作。原始网格经 过一系列的边收缩操作后，形成一个最粗糙的基网格，和一系列的细节信息。细 节信息记录了网格模型简化过程中原顶点和新顶点位置以及顶点间的连接关系 的变动信息，以便能够根据需要重建出不同分辨率级的网格模型。 基于h o p p e 提出的简化方法所构造的网格多分辨率表示，称为渐进网格 ( p r o g r e s s i v em e s h e s ，p m ) 。p m 表示是一种高效、无损且具有连续分辨率的表示 方法，适用于具有任意拓扑结构的网格模型。 边收缩的关键是收缩的次序以及边收缩后新顶点的位置，h o p p e 5 3 墚用能量 优化的方式来确定边收缩次序和新顶点的位置。虽然用这种方法生成的简化模型 的效果是在所有简化方法中是最好的，但计算复杂，所需时间较长。g a r l a n d 和 北京工业大学工学硕士学位论文 h e c k b e r t 3 5 】在1 9 9 7 年提出了一种基于二次误差测度( q u a d r i ce r r o rm e t r i c ，简称 q e m ) 的简化算法。q e m 算法误差测度是基于顶点到平面的距离平方和，该算 法速度快，简化生成的模型质量仅次于h o p p e 的能量优化方法，是一种非常有 效的简化算法。 2 2 2m a p s m a p s 是一种自适应( a d a p t n e ) 的重新网格化方法，其基本过程描述如下： 对原始不规则网格应用改进的d k 算法进行不断的网格简化，得到一个粗糙的基 网格，把此基网格作为基域( b a s ed o m a i n ) ：在网格简化的同时，应用共形映射 ( c o n f o r m a lm a p ) 将原始网格的每个顶点都映射到基域中( 图2 4 ) ，这样原始 网格就可以理解为是从基域到r 3 的函数，在简化过程中删除的每个顶点都在基 网格的某个三角形中有一个“质心( b a r y c e n t e r ) ”坐标( 图2 5 ，图2 - 6 ) ：对基 网格进行连续四等分，并对引入的每个顶点根据插值【3 9 1 得到的“质心”坐标反映 射到原始网格表面，得到重采样后的顶点；对重采样的网格进行平滑处理，得到 最终的半规则网格。 2 2 3n o r m a im e s h e s n o r m a lm e s h e s 是一种新的网格多分辨率表示方法，它使得较高分辨率级的 网格可以用较低分辨率级网格的法向偏移( n o r m a lo f f s e t ) 来表示。于是，原始 网格就可以用一个最粗糙的基网格和一系列的法向参量来表示，这样就把原来的 三维表示方法简化成一维表示了。由于网格的数据量一般都很大，而n o r m a l m e s h e s 表示把三维图形中复杂的计算转换成微分几何中简单的一维计算，大大 减少了数据量，是一种很好的网格压缩表示。 和m a p s 一样，n o r m a lm e s h e s 把原始不规则网格转换成具有细分连接性的 半规则网格。设网格顶点集只“c 弓，点p i 日弓+ 1 ，由n o r m a lm e s h e s 的定义， p ，只依赖于只+ 。和法向n ，如果p ，不能由弓+ 。和法向n 确定，则称p ，为非法向 第2 章网格的多分辨率分析 图2 4m a p s ( 原始网格中的每个顶点都映射到基网格中某个三角形内的一个点) 图2 - 5m a p s ( 待删除顶点及其邻域通过共形映射从三维空 间映射到一个平面，此顶点删除后，进行重新三角形化) 图2 - 6m a p s ( 重新三角形化后，给刚删除的顶点分配一个“质心”坐标) 1 5 北京工业大学工学砚士学位论文 点( n o n - n o r m a l ) 。在构造n o r m a lm e s h e s 引入新顶点时，需要预测一个基点( b a s e d o i n t ) 和一个法向，然后通过“刺穿”( p i e r c i n g ) 计算法向和原始网格表面的交 点，也就是新引入的顶点。基网格( 巧，k ，) 是由g a r l a n d - h e c k b e 一3 5 提出的半边 收缩的网格简化算法生成，参数化方法采用m a p s 中提出的平滑参数化方法， 基点和法向的预测采用b 甜e m y 【”，3 8 1 细分方法，如图2 - 7 所示。 题 图2 7n o r m a lm e s h e s 中新顶点的引入 ( c ) l e v e l3 i d ) l c v e l6 ( m l m e r l r l g o fi i l m lm e s h ) 图2 - 8n o r m a lm e s h e s 表示的例子 第2 章网格的多分辨率分析 经过n o r m a lm e s h e s 重新网格化后，新网格几乎只依赖于基域，所以基网格 的选取十分重要，而经网格简化获得的粗糙网格只是基域的一个初步假设，所以 有必要需要调整基域。另外，在“刺穿”过程中，有可能出现有多个交点或没有 交点的情况，这时需要计算非法向点，一个好的n o r m a lm e s h e s 重新网格化过程 中，非法向点要尽量少。 图2 8 是n o r m a lm e s h e s 表示的一个例子，图( a ) 是简化后并调整的基网格， 图( b ) 、( c ) 分别是经过一次和三次细分后的网格，图( d ) 是经过六次细分并 经渲染( r e n d e r ) 后形成的最终的半规则网格。基网格有4 2 个点和8 0 个三角形， 而最终的网格有1 6 3 ，8 4 2 个顶点和3 2 7 ，6 8 0 个三角形。 2 3 网格小波变换 2 3 1 介绍 多分辨率分析的基本思想是，把一个复杂的函数分解为一个较简单( 低分辨 率) 的函数和一系列的细节信息，而小波的多分辨率特性使得它和多分辨率分析 完美地结合起来。从信号处理的角度来讲，多分辨率分析是将原始信号通过一个 理想低通滤波器和一个理想高通滤波器，将其分解为低频部分和高频部分，然后 再对分解的低频部分继续分解下去，形成了原始信号的多分辨率表示。般来讲， 信号的低频成分比较重要，它经常包含信号的特征，而高频成分则给出了信号的 细节或差别。 一个一维信号f ( t ) 经小波变换后可以用式( 2 一1 ) 表示： ，( 。2 荟c 鼎伊 ( f ) + 善荟d 让5 f ，扯( 。( 2 - 1 ) 其中，第一项办( f ) 是，( f ) 在分辨率级，下的一种逼近，第二项是厂( f ) 在各个分 辨率级的细节成分。 传统的第一代小波通过对某一特定的母小波进行伸缩、平移得到一族小波基 函数，使得原始信号可以用小波基函数的加权和来表示或逼近。由于小波良好的 北京工业太学t 学硕士学位论文 时频分析和多分辨率特性，使其在信号处理、模式识别、图像处理等很多领域得 到了广泛的应用。但是，第一代小波通常定义在规则数据上，在一些应用环境中， 伸缩、平移是不可能实现的，例如定义在球面h 7 1 上的函数，很难通过伸缩、平移 描述这样的函数族，也就难以用传统的小波变换分析这类函数。 网格数据是不规则采样数据集，其小波变换不能通过伸缩、平移来实现，所 以需要寻找新的处理方法。l o u n s b c r y 5 5 】最早将小波变换和多分辨率分析推广到 具有细分连接性的网格中去，其基本思想与第一代小波类似。由于伸缩、平移不 能在网格表面进行，l o u n s b e r y 以基网格为基域对原始网格进行参数化，并应用 网格细分建立嵌套空间，进而建立小波空间和小波基。设基网格为朋。，则参数 化后的原始网格s ( x ) ，x m 。经过，次小波变换后可以用式( 2 2 ) 表示： s ( 工) = v ? ( z ) + 叫j ( 工) ，工m 。i 式中第一项为反映原始网格基本拓扑结= l 构i 的基网格，是原始网格在分辨率级( 2 - 2 下) 的一种逼近，妒( x ) 为尺度函数，与细分过程有关；第二项是s ( x ) 在各个分辨率 级的细节成分，y ( 功为小波函数，w 为小波系数。 1 9 9 6 年，s w c l d e n s 4 6 1 提出了一种应用范围更广、计算速度更快的新