（计算机应用技术专业论文）基于视觉特征的三维网格数字水印算法(1).pdf

山东大学硕士学位论文 摘要 随着计算机图形处理技术的飞速发展和互联网的迅速普及，三维模型正在 被广泛地应用并带来可观的经济收益，并且已经成为知识产权保护的重要对象 而三维网格数字水印技术正是在这种需求下产生、发展起来的。它将版权信息 以水印的形式隐藏到目标模型中，对使用者不可见且不影响数据的正常使用， 在需要的时候，又能够方便快捷地从模型中提取出水印信息，从而实现版权的 验证等功能。 1 9 9 7 年，o h b u c h i 等第一次提出了三维网格数字水印技术的概念，为三维 网格模型和数字水印的研究提供了新的思路和方法。经过了近十年的发展，三 维网格数字水印技术已经形成了以水印嵌入与提取、水印的攻击、水印评估等 几个方面为主要内容的研究领域，并获得了初步的发展。三维网格数字水印技 术主要包括水印嵌入、水印评估、水印攻击等几个方面。按照其嵌入域不同可 将三维网格数字水印分为空域水印和频域水印；按照应用领域的不同可分为用 于版权保护的鲁棒性水印和用于内容认证的脆弱水印算法；按照水印提取过程 是否需要原始数据可将水印分为私有水印与公开水印。水印的攻击方法主要有 鲁棒性攻击，解释攻击，法学攻击等。对于水印性能的评估，目前主要使用受 试者工作特征曲线r o c 、水印位出错率、模型形变量、信噪比s n r 和峰值信噪 比等方法。本文第二章按照嵌入域分类法，着重研究了一批具有代表性的三维 水印算法。 本项研究的主体部分，着眼于探索如何在不影响视觉效果和可用性的基础 上，完成三维网格水印嵌入。由于三维网格模型的特殊性，三维网格水印算法 的最终实现都是以网格顶点位置的微小改变为根本，并且这种改变不影响几何 模型的视觉效果和功能特性。物体形状的微变如何尽可能减少对视觉的影响， 如何不影响物体的可用性，这个问题对于增加或攻击水印信息都有非常重要的 指导意义。 三维网格数字水印算法的目标是以较小的网格变化来实现较多的水印信息 的嵌入，而三维网格中具有较好的视觉隐藏特性的区域能够在发生改变时不易 被察觉，能较少的影响几何模型的视觉效果和功能特性，这种特性非常的符合 山东大学硕士学位论文 三维网格数字水印的需求，能够实现大强度、鲁棒性的水印算法。 本项研究的主要贡献，在于以三维网格的曲率为基础，通过分析曲率及区 域内曲率变化对于模型视觉特征的影响，提出了一种使用曲率及曲率变化相结 合的三维数字水印算法。首先，计算三维网格中的点的曲率，然后根据点的邻 接点信息计算出网格中各个区域的平均曲率及区域内曲率的变化来，以视觉特 征来选取合适的区域：然后，采用插值的方式将水印信息嵌入到所选区域中去， 越靠近区域中间的点拥有较高的扰动强度，越靠近边界的点施加越小的扰动， 这样能使区域在发生变化后仍然能够与周围区域保持视觉上的平滑特性。实验 结果表明算法易实现大容量水印的嵌入及提取，能有效的保证模型的视觉特征， 并对多种攻击都有很好的鲁棒性。 关键词：三维网格；数字水印；视觉特征；曲率；曲率变化；插值算法 i i 山东大学硕士学位论文 a b s t r a c t i nr e c e n ty e a r s t h r e e d i m e n s i o n a lm o d e li sb e i n gw i d e l ya p p l i e d , 、) l ，i mt h er a p i d d e v e l o p m e n to ft h ec o m p u t e rg r a p h i c sa n dt h ep o p u l a r i z a t i o no ft h ei n t e m e t t h r e e d i m e n s i o n a lm o d e lh a sb e c o m ea l li m p o r t a n to b je c to fi n t e l l e c t u a lp r o p e r t y p r o t e c t i o n i nt h i sw a y , t h r e e - d i m e n s i o n a ld i s t a lw a t e r m a r k i n gh a sb e e nw i d e l y r e s e a r c h e d 嬲锄e f f e c t i v es o l u t i o nf o rc o p y r i g h tp r o t e c t i o na n da u t h e n t i c a t i o no f t h r e e d i m e n s i o n a lm o d e l s t h ei n f o r m a t i o ne m b e d d e di n t ot h em o d e li sn o tv i s i b l e t ot h eu s e r , i ta l s od o e sn o ta f f e c tt h ef u n c t i o no ft h em o d e l ，i tc o u l db ee a s i l y d e t e c t e df r o mt h em o d e la n du s e df o rc o p y r i g h tp r o t e c t i o na n da u t h e n t i c a t i o n t h ef i r s tw a t e r m a r k i n gm e t h o do ft h r e e - d i m e n s i o n a lm o d e l sw a sp r e s e n t e db y o h b u c h ii n1 9 9 7 ，i tp r o v i d e dan e wm e t h o df o rt h er e s e a r c ho fd i g i t a lw a t e r m a r k i n g o v e rt h el a s td e c e n n i u m , t h r e e d i m e n s i o n a ld i g i t a lw a t e r m a r k i n gh a sr e s u l t e di nt h e f o l l o w i n ga r e a so fr e s e a r c h ：w a t e r m a r ke m b e d d i n ga n de x t r a c t i o n ，t h ew a t e r m a r k a t t a c k s , w a t e r m a r ka s s e s s m e n te t c a c c o r d i n gt h ed o m a i nt h ew a t e r m a r kw a s e m b e d d e d ，t h r e e d i m e n s i o n a ld i g i t a lw a t e r m a r k i n gc a l lb ed i v i d e di n t ot w op a r t s ： t r a n s f o r md o m a i nw a t e r m a r k i n ga n ds p a t i a ld o m a i nw a t e r m a r k i n g i na c c o r d a n c e 谢mt h ed i f f e r e n ta p p l i c a t i o na r e a s ，w a t e r m a r k i n gc a nb ec l a s s i f i e di n t ot w o p a r t s ： t h er o b u s t n e s sw a t e r m a r k i n gf o rc o p y r i g h tp r o t e c t i o na n dt h ef r a g i l ew a t e r m a r k i n g w a t e r m a r k i n gc a na l s ob ed i v i d e di n t ot w op a r t s ：p r i v a t ew a t e r m a r k i n ga n dp u b l i c w m e r m a r k i n g w a t e r m a r ka t t a c km e t h o d sh a v et h ef o l l o w i n g ：r o b u s t n e s sa t t a c k s ， i n t e r p r e t a t i o na t t a c k s ，l e g a la t t a c k s w a t e r m a r kp e r f o r m a n c ea s s e s s m e n th a st h e f o l l o w i n gc a t e g o r i e s ：r e c e i v e ro p e r a t i o nc h a r a c t e r i s t i cc u r v e ( r o c ) ，b i te r r o r r a t e s ( b e r ) ，m o d e ls h a p e v a r i a b l e ，s i g n a l t o - n o i s e r a t i o ( s s r ) a n d p e a k s i g n a l - t o - n o i s er a t i o ( p s n r ) e t c c h a p t e r2o ft h i sa r t i c l er e v i e w st h ec u r r e n t w a t e r m a r k i n gt e c h n i q u e sf o rt h r e e - d i m e n s i o n a lm o d e l s 1 1 1 i ss t u d yf o c u s e do nt h er e l a t i o n s h i pb e t w e e nt h ew a t e r m a r ka n dt h ev i s u a l c h a r a c t e r i s t i c so ft h em o d e l c o l o r , s h a d i n g ，t e x t u r e ，o ro t h e ra t t r i b u t e sm a yb ee a s i l y c h a n g e do rr e m o v e d d u et ot h es p e c i f i c i t yo ft h r e e d i m e n s i o n a lm o d e l ，v e r t e x c o o r d i n a t e sa r et h em o s ts u i t a b l ef e a t u r e st ob eu s e df o rw a t e r m a r k i n gg r a p h i c a l o b j e c t s t h em a i no b j e c t i v eo f3 dm e s hw a t e r m a r k i n gi st om a x i m i z et h ew a t e r m a r k 1 1 【ij 东大学硕士学位论文 s t r e n g t hw h i l em i n i m i z i n gt h ev i s u a ld i s t o r t i o n t h er e g i o n sh a v i n gb e t t e rv i s u a l m a s ka b i l i t yi nt h em o d e lc o u l dm e e tt h en e e d so ft h r e e - d i m e n s i o n a lw a t e r m a r k i n g v e r yw e l l i nt h i sp a p e r , w ep r o p o s ean o v e lr o b u s t3 dw a t e r m a r k i n gs c h e m eb a s e do nt h e a n a l y s i so fc u r v a t u r ea n df l u c t u a t i o no fc u r v a t u r e ，w h i c hu s e dt oe v a l u a t et h ev i s u a l d i s t o r t i o no ft h em o d e l w ea n a l y z et h er e g i o n sm e a l lc u r v a t u r ea n df l u c t u a t i o no f c u r v a t u r e ，a n dt h e nc h o o s et h ea p p r o p r i a t er e g i o n sw i t hh i g hv i s u a lm a s k i n gd e g r e e ， i no r d e rt oe m b e dt h ew a t e r m a r kb yu s i n gt h ei n t e r p o l a t i o na l g o r i t h m w es p e n d l e s sv i s u a ld i s t o r t i o nt oe m b e d d i n gh i g h e rw a t e r m a r ks t r e n g t h e x p e r i m e n t a lr e s u l t s p r o v e dt h a tt h ea l g o r i t h mw a si n v i s i b l ea n dr o b u s ta g a i n s tv a r i e t ya t t a c k sw e l l ，s u c h a sr o t a t i o n ，s c a l i n g ，c r o p p i n g ，n o i s ea n ds m o o t h k e yw o r d s ：3 0m e s h ：w a t e r m a r k i n g ；v i 8 u 8 im a s k ：c u r v a t u r e ： i n t e r l a o i a l ：i o na i g o r i t h m i v 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立 进行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含 任何其他个人或集体己经发表或撰写过的科研成果。对本文的研究做出 重要贡献的个人和集体，均已在文中以明确方式标明。本声明的法律责 任由本人承担。 论文作者签名：日期：至竺! 互幺蔓 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保 留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅；本人授权山东大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或其他复制手段保存论文和汇编本 学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：扭导师签名：土啦日 期：兰型 山东大学硕士学位论文 量曼曼曼曼量曼曼曼曼蔓曼詈曼曼曼曼曼曼曼曼量曼量曼曼曼曼曼曼曼曼鼍u m 皇曼皇曼曼! 曼曼曼曼曼曼曼皇曼璺量! 曼皇鼍曼曼曼舅 第一章绪论 1 1 课题研究背景和意义 随着计算机硬件的飞速发展，三维测量技术、g p u 等技术的广泛应用，计算 机三维图形图像技术也取得的巨大的进步，三维模型已经广泛应用于各种不同的 领域，如医疗、电影、视频游戏、工业制造、虚拟现实等，并且成为各领域三维 形状描述的必不可少的信息形式。伴随着互联网的飞速发展，各种三维模型数据， 如卡通造型、产品模型等呈现在网络上，被浏览、下载或传播。数据交流的便利， 极大地促进了三维模型数据的应用、共享和开发，然而，这也使得盗版者能以极 低廉的成本来复制及传播未经授权的三维模型数据，严重损害着知识原创者的权 益。如何有效地保护这些三维模型数据的知识产权，不仅关系着三维模型技术的 发展前景，更加关系着互联网知识经济能否健康发展。在这一背景下，三维数字 水印技术应运而生。 数字水印技术是指在数字化的数据内容中嵌入不明显的记号或标记比特。被 嵌入的记号对观察者来说通常是不可见或不可感知的，但是通过一些计算操作可 以被检测或者被提取。这些被嵌入的记号被称为水印。水印与源数据( 如图象、 音频、视频、模型数据) 紧密结合并隐藏其中，成为源数据不可分离的一部分， 并可以经历一些不破坏源数据使用价值或商用价值的操作而存活下来。三维模型 数字水印是在数字化的几何模型数据内容中嵌入不明显的记号或标记比特。它是 水印技术的一个应用分支。本文中提到的三维几何模型如果没有特别的说明均指 三角形网格模型。 尽管目前存在着对三维模型知识产权的多种保护手段，但三维网格数字水印 技术无疑是最简单、快速、客观和令人信服的。它的最大特点是，将版权信息以 水印的形式隐藏在目标模型数据中，当需要时，可以提取模型数据中的水印信息， 以供验证版权；而在使用过程中，使用者不可见这些隐藏的版权信息，该“水印” 也不影响目标模型数据的正常使用。经过近十年的发展，三维网格数字水印技术 形成了以水印嵌入与提取、水印的攻击、水印评估等几个方面为主要内容的研究 领域，并获得了初步的发展。 山东大学硕士学位论文 由于三维网格的特殊性，三维网格水印算法的最终实现都是网格顶点位置 的微小改变为根本，并且这种改变不影响几何模型的视觉效果和功能特性。用 s 表示物体形状，v 表示三维网格的顶点集合，f 表示他们之间的映射关系，那 么水印嵌入技术可以概括为如下的形式：s + a s = f 缈+ a v ) ，当稍微改动网格 顶点位置( av ) 时，原则上物体的形状都会有相应的变化( as ) ，而我们希 望这种变化限制在一个不易察觉的范围内，这是三维数字水印技术的实质。 攻击水印信息的方法是对已经加载了水印信息的三维网格数据进行有限的 修改，破坏水印信息，同时又不会损坏物体形状和可用性。它与水印的嵌入是 相生相克的，从原理上讲，水印的攻击方法和嵌入方法都依赖于对物体形状和 数据点微小改动( as ，v ) 以及他们之间关系的深入研究。 物体形状的微变s 如何尽可能减少对视觉的影响，如何不影响物体的可用 性，这个问题对于增加或攻击水印信息都有非常重要的指导意义。在增加或攻 击水印信息时，我们首先应该清楚的是三维物体能够承受多大的微变s 。网格 顶点位置的改变v 应该限制在什么样的范围，这直接影响着水印信息的容量 和鲁棒性。空域方法将水印嵌入到一个或若干个相邻的网格顶点上，而频域方 法则将其加载到整个网格上。以一种统一的、定量的方法研究他们嵌入水印的 效果具有重要的价值。 因此，研究物体外形的微变、网格顶点的微变，以及他们之间的关系是一 个涉及到三维网格数字水印技术的一个基础问题。解决好该问题，将为水印信 息的加载、攻击方法、水印效果的评估，以及鲁棒性水印的研究提供新的理论 和方法。三维网格建模技术主要研究如何通过顶点集合来表示三维物体的形状， 即s ：f ( v ) 。从这个意义上讲，数字水印技术进一步推动了对三维模型的深入 研究。 1 2 三维网格数字水印的研究进展 数字水印技术作为一种数字产品的版权保护技术始于在二十世纪九十年代 中期，并很快得到了广泛的研究与应用。数字水印技术的最初目标是为了保护二 维图像和视频，但随着三维网格模型的广泛应用与互联网的飞速发展，数字水印 2 山东大学硕士学位论文 技术也得到了相应的扩展，发展出了三维网格数字水印技术。 正是由于二维水印对于三维网格水印的重要借鉴意义，在讨论三维网格数字 水印算法之前有必要回顾一下二维水印方面的重要工作。文献n 1 是第一篇在主要 会议上发表的关于数字水印的文章，此算法首先把一个密钥输入一个m 一序列 ( m a x i m u m - l e n g t hr a n d o ms e q u e n c e ) 发生器来产生水印信号，然后排列成2 维水 印信号，按像素点逐一插入到原始图像像素值的最低位( l s b ：l e a s ts i g n i f i c a n t b i t s ) 。n i k o l a i d i s 瞳1 利用像素的统计特征将信息嵌入像素的亮度值中。黄继武 等钔提出一种d c t 域数字水印算法：该算法对选定的d c t 系数进行微小变换以满 足特定的关系，来表示一个比特的信息。b e n d e r 暗1 的p a t c h w o r k 算法是将水印信 息嵌入像素的统计特征。 三维网格水印方面的研究，最早出现在1 9 9 7 年，o h b u c h i 等3 针对三角形网格， 根据网格替换、拓扑替换和可见模式等概念提出了几种水印算法。b e n e d e n s 在论 文口3 中提出了调整网格曲面法向量的水印算法，在文章噙9 1 0 1 中又相继提出了多种 水印算法，每种算法适于特定应用并对特定攻击具有鲁棒性。在文献n 1 1 2 1 中，局 部统计被用来向三维对象嵌入水印。p r a u n 在他1 9 9 9 年的文章呻1 中，已经考虑了 用于网格水印的多分辨率滤波器和插值表面基函数的联系，文献n 钔则讨论了与基 于金字塔算法的联系。由于n u r b s 曲面的广泛应用，有学者提出采用改变控制点 的方式n 朝或利用重新参数化n 引，在n u r b s 曲面中嵌入数字水印信息。文献盯使 用多边形的小波分解来进行三维水印嵌入。文献n h 妇提出了在网格的频域利用拉 普拉斯图进行水印嵌入的算法。 国内浙江大学c a d & c g 实验室的研究人员也较早地进行了相关研究，发表了基 于g u s k o v 分解的三角形网格数字水印算法【恐2 3 1 ，基于球面参数化和调和分析的三 维模型水印算法等一系列重要研究成果。 尽管三维网格数字水印己近在多个方面取得了巨大的进展，但仍然远未达到 应用的要求。由二维水印的发展可以来看，在s t i r m a r k 标准和v o l o s h y n o v s k i y 标准出现之后，几乎所有之前的水印算法在新标准下都变得不堪一击。因此，接 下来亟需建立一套三维网格水印的强壮性评估标准，用来对水印算法的好坏提供 客观的评价。可以预见的是，随着新的三维网格数字水印评估方法的出现，过去 的所谓鲁棒的算法都将面临巨大的考验，水印评价混乱的局面也将被彻底终结。 3 山东大学硕士学位论文 解决好上述问题可以提高三维网格数字水印的鲁棒性和效率，为三维网格数据的 使用、传播提供新理论和方法。 1 3 本文的主要工作及创新点 本文研究的主体部分，着眼于探索如何在不影响视觉效果和可用性的基础 上，完成三维网格水印嵌入。由于三维网格模型的特殊性，三维网格水印算法 的最终实现都是以网格顶点位置的微小改变为根本，并且这种改变不影响几何 模型的视觉效果和功能特性。物体形状的微变如何尽可能减少对视觉的影响， 如何不影响物体的可用性，这个问题对于增加或攻击水印信息都有非常重要的 指导意义。 三维网格数字水印算法的目标是以较小的网格变化来实现较多的水印信息 的嵌入，而三维网格中具有较好的视觉隐藏特性的区域能够在发生改变时不易 被察觉，能较少的影响几何模型的视觉效果和功能特性，这种特性非常的符合 三维网格数字水印的需求，能够实现大强度、鲁棒性的水印算法。 本项研究的主要贡献，在于以三维网格的曲率为基础，通过分析曲率及区 域内曲率变化对于模型视觉特征的影响，提出了一种使用曲率及曲率变化相结 合的三维数字水印算法。实验结果表明算法易实现大容量水印的嵌入及提取， 能有效的保证模型的视觉特征，并对多种攻击都有很好的鲁棒性。 1 4 各章节安排 本文第二章阐述了三维网格数字水印技术的基本原理及特点，并对三维网 格数字水印技术进行了分类，着重研究了其中具有代表性的算法。 第三章对三维网格数字水印技术中的视觉特征的研究进行了概括，然后提 出了一种能有效保证视觉特征的三维网格数字水印算法。算法基于对三角网格 曲率及曲率变化的分析，挑选模型中具有较高视觉隐藏特性的区域，并将水印 嵌入到这些区域中去，以此来实现大强度、高鲁棒性的水印算法。实验证明这 个算法对多种攻击具有较好的鲁棒性，并具有较高的可操作性。 第四章分析了当前三维网格数字水印技术的现状，并对三维网格数字水印 技术的发展进行了展望。 4 山东大学硕士学位论文 i i 皇 _ i 皇曼曼曼曼曼曼曼 第二章三维网格数字水印技术的研究现状及相关理论 2 1 数字水印的基本概念及特点 数字水印( d i g i t a lw a t e r m a r k ) 技术，是指在数字化的数据内容中嵌入不 明显的特殊信息一水印( w a t e r m a r k ) ，这种被嵌入的水印可以是一段文字、标识、 序列号等。被嵌入的水印对使用者或是观察者来说通常是不可见或不可感知的， 但是通过一些计算操作可以被检测或者被提取。水印与源数据( 如图象、音频、 视频、三维模型数据) 紧密结合并隐藏其中，成为源数据不可分离的一部分，并 可以经历一些不破坏源数据使用价值或商用价值的操作而存活下来。三维模型数 字水印是在数字化的几何模型数据内容中嵌入不明显的记号或标记比特。 根据信息隐藏的目的和技术要求，三维模型数字水印应该具有以下基本特性 川 1 容量：水印系统应该容许植入有意义的数据。植入识别购买者或受权者 身份的序列号至少需要3 2 位容量。证明所有者关系需要足以储存一个散列值的容 量，例如m d 5 需要1 2 8 位，s h a 需要1 6 0 位。在公有水印系统中植入水印的容量从一 个全局模型注册号3 2 位到一个能从中获得版权和授权相关信息的u r l ( 可能需要 2 5 6 位或更多) 不等。 2 透明性( 隐藏性) ：经过一系列隐藏处理，目标模型数据必须没有明显的 降质现象，而隐藏的数据无法人为地看见或听见。 3 鲁棒性( 强壮性) ：指抗拒各种处理和攻击操作而不导致隐藏信息丢失的 能力。所谓的操作包括：旋转，平移和均匀放缩；多边形简化( 经常是为了获得 足够快的绘制速度) ；顶点随机排序；网格重建( 重新三角形网格化) ，产生边长 和面大小形状相同的块；网格光滑操作；部分裁剪操作在背面剔除操作中移 去部分模型；局部变形。由于其他的一些更复杂的几何操作( 如裁剪，沿任意轴 的非均匀放缩，投影，全局变形等) 可能降低模型的视觉质量和可用性。因此一 个三维模型水印系统明显不需要对上述操作提供强壮性要求。 山东大学硕士学位论文 4 隐藏位置的安全性：指将欲隐藏的信息藏于目标模型数据的内容之中， 而非文件头等处，防止因格式变换而遭到破坏。 除了以上基本特性外，三维模型数字水印还可以具有以下一些额外属性，这 样水印算法的功能会更加完善川： 1 后台处理和适当的运行速度：水印的植入和提取过程应该尽可能不需要 用户的交互。用机器人( a g e n t s ) 在w e b 站点和数据库中搜寻水印是监控合法或 非法拷贝使用和加强版权保护的一个重要应用。这方面的最终目的是实时监控。 但是这对水印算法的执行速度和存储需求将有很高的要求。 2 尽可能少的先验数据知识：一个理想的水印系统提取过程仅仅需要知道 模型数据和一个密钥。这个密钥是模型的创建者，模型类，模型和被授权使用者 专用的，所有必需的参数例如随机数发生器的种子数都是由这个密钥产生的。在 公有水印系统中，创建者的所有模型都共享唯一一个密钥，或者系统可能对所有 的创建者都采用同一个密钥。遗憾的是，水印的提取过程往往需要更多的先验数 据知识： ( 1 ) 模型本身的知识，特别是为了避免同步问题需要知道在模型中植入水印 的位置信息。 ( 2 ) 重定向，重新调节和与水印模型的比较过程中需要知道原始模型数据或 至少部分数据( 比如说特征向量) 。 由于水印提取过程削弱了算法的监控和后台处理能力，使得水印的分散检索 过程变得复杂了，特别是当访问数据库中的大量模型数据时情况更糟。 3 尽可能少的预处理开销：理想的水印系统应该允许直接访问加入了水印 的模型数据而不需要其他的预处理数据信息。预处理过程包括模型表达方式的 转换，模型识别，校正表面法向校正，重定位和放缩等。 2 2 三维网格数字水印技术的分类 基于不同的分类原则，三维模型数字水印算法可以分为不同的类别，通常的 分类如下： 按照嵌入对象域的不同分为空域算法和频域算法。空域水印算法主要通过修 改三维模型的几何特性、拓扑结构及模型纹理信息来嵌入水印信息，如顶点的坐 6 l ji 东大学硕士学位论文 标、多边形面积、表面法向量等；与空域的方法不同，频域水印算法先将三维数 据变换到频域中，在频域数据上做微小的改动，加载水印信息，然后再将频域数 据变换到空域。 按照应用领域的不同分为用于版权保护的鲁棒性水印和用于内容认证的脆 弱水印算法。用于版权保护的鲁棒性水印算法是用来解决产品的所有权归属问 题，在这一应用中，嵌入到原始模型中的水印信息通常是版权所有者的数字签名 或是数字认证，并要求水印能够抵抗各种类型的操作和攻击；用于内容认证的脆 弱水印是用来检验被保护模型数据的完整性，在这一应用中，当模型数据遭到篡 改时，嵌入到模型中的水印应该遭到破坏或是丢失，并能够对被修改的数据进行 定位。 按照水印提取过程是是否需要原始数据可将水印分为私有水印与公开水印。 私有水印在水印提取是需要原始对象或其它不能公开的参数，这一缺点大大限制 了私有水印的应用范围。相比之下，公开水印算法在提取水印时仅需要少量的参 数，并且这些参数均可公开获取，因此公开水印是三维模型数字水印技术发展的 必然要求。 在本文中，我们将从空域与频域两个方面来分析近些年来的一些具有代表性 的三维模型数字水印算法。 2 3 三维网格数字水印算法分析 1 9 9 7 年，o h b u c h i 等在a c mm u l t i m e d i a9 7 国际会议上发表了一篇三维网格 数字水印的文章 6 1 ，这篇文章被公认为是第一篇在国际上公开发表的关于3 d 网格 模型数字水印技术的文章，代表着三维网格数字水印技术研究的正式开始。随后， 三维网格数字水印技术的研究进入了飞速发展时期，国内外的学者都对其发展起 到了巨大的推动作用，取得了不少的成果。下面我们根据按照嵌入对象域的不同 分为空域算法和频域算法来进行介绍： 2 3 1 空域三维网格数字水印算法 1 t s o 算法 t s q 算法6 ，批7 1 利用相似三角形的概念，使用二元组p 口，h c ) 表示一组相似 7 山东大学硕士学位论文 三角形，如图2 1 ，将相邻的4 个三角形作为一个宏嵌入单元( m a c r o e m b e d d i n g p r i m i t i v e ，m e p ) ，如图2 2 ，每个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 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 中，4 个三角形分别用m ，s ，d 1 和d 2 表示，这些 三角形中分别存储m a r k e r ，s u b s c r i p t ，d a t a l $ f l d a t a 2 的值。 图2 1 - - 元f f i b l a ，h c j 图2 2 把p 中的4 的相似三角形 水印嵌入过程如下：首先遍历所有的网格，寻找一个合适的m e p ，通过对中间 的三角形m 的三个坐标值进行微小的调整，使该三角形与给定三角形相似，从而嵌 入m a r k e r 的值：然后改变v 0 ，v 3 ，v 5 - - - 个顶点的坐标值，分别将s u b s c r i p t ， d a t a l 和d a t a 2 的值嵌入在二元组 e 0 2 e 0 1 ，h o e 1 2 ) ， e 1 3 e 3 4 ，h 3 e 1 4 ) 和 e 4 5 e 2 5 ，h 5 e 2 4 ) 中，重复上述过程，直至嵌入所有数据。 水印的提取过程如下：根据给定的一个二元组的值，即m a r k e r ，从嵌有水印 的网格中找到与之匹配的皿p ；提取s u b s c r i p t ，d a t a l 和d a t a 2 的值；重复上述过 程，直至提取所有数据；根据s u b s c r i p t 的值将所有的d a t a l 和d a t a 2 进行排序，从 而得到水印数据。 t s q 水印算法可以以抵抗平移、旋转、一致放缩等几何操作攻击，如果采用 重复植入水印的方法则可抵抗裁剪和局部变形的攻击，但是这种算法不能抵抗网 格重建和顶点随机序列化的攻击。 2 t v r 算法 t v r 算法【6 2 啦5 ，2 刀利用了一个仿射变换不变量，即四面体的体积比。其网格水印 嵌入过程如下：给定一个初始条件，即给定初始顶点和初始遍历方向，根据三角形 网格寻找一个顶点生成树k ，具体方法是：在给定的顶点处，逆时针方向扫描与之 山东大学硕士学位论文 连接的边，找到一条在圪中不存在的边，并且这条边不能指向在k 中己扫描过的 顶点，如果找到这样的边，就将该顶点加入杉中然后，计算并寻找两个相邻三角 形的共同边，使得围成的四面体体积最大，将该共同边作为初始边。将k 转变为一 个三角形序y u t r i s ，先构造一个三角形约束边链表( t b e ) ，该链表初始为连接形中 一系列顶点的边。可以这样构造这个链表：从根节点处扫描k ，遍历所有顶点，在 每一顶点处顺时针扫描所有与之相连的边，如果该边不在t b e 中，将其加入其中? 如果有一个三角形的三边在t b e 中第一次出现，且t r i s 中不包含该三角形，则将 该三角形加入蛰j t r i s 中，如图2 3 所示。该算法在水印容量、执行速度和监控能力 这些方面具有近似最佳优化的特点，主要缺点在于不能抵抗网格重采样、多边形 简化和顶点的随机序列化等攻击操作。 4321 5 i j 俐。j 夕磁夕纠 67 8 9 1 ：初始顶点 1 - 9 ：初始遍历方向 ：三角形序列中的元素 z ：三角形约束边 图2 3 顶点生成树k 和三角形序列t r i s 的构造过程 3 t s p s 算法 三角形条带剥离符号序列( t s p s ) 算法1 6 , 2 6 , 2 7 ，是一种基于拓扑结构变动的公 开的网格水印算法中提出的一种修改网格拓扑属性植入水印的算法。原始网格模 型是有方向的三角形网格模型，水印数据是一个二值序列，算法从选定的一条边 开始，按照水印位串值构造三角形条带，从而植入水印信息，然后将植入水印信 息的三角形条带从网格中剥离，构成一个带缝隙的水印网格模型，由于形成的缝 隙足够小，所以在视觉上察觉不出来。这种算法由于是基于拓扑结构的调整，因 此可以抵抗几何变换的攻击，如实现水印的多次嵌入也可以抵抗剪切攻击，但是 9 山东大学硕士学位论文 对一些拓扑操作攻击如采用边折叠的网格简化操作抵抗不足，另外可嵌入的水印 信息容量也比较低。水印提取过程中不需要原始网格模型的信息，适用于公有水 印系统。该算法的空间利用率比较低。 4 m d p 嵌入算法 m d p 嵌入算法6 惩明通过调整三角形网格的大小，在给定的三角形网格上嵌入 在线框显示方式下可见的模式信息。该算法可以抵抗一定的几何变换，但抵抗网 格简化和其他拓扑操作能力很差。 5 顶点束算法( v f a ) 和三角形束算法( t f a ) v f a 和t f a 【9 1 是两种大容量公有水印算法。v f a 算法首先在模型中选定指定三角 形，按网格模型顶点到指定三角形质心的距离划分顶点集合，然后修改各个顶点 集合中的顶点坐标植入水印信息：t f a 算法首先在模型中选定指定三角形，然后 找出与给定三角形共边的所有三角形，按照非共享顶点到共享边的距离( 三角形 高度) 大小排序存放三角形，重复上述步骤，生成一棵以三角形为元素的树，遍 历生成树，修改各个三角形的高度值植入水印。这两种算法仅仅改变网格模型的 几何信息而且对网格模型没有什么特殊的要求，具有植入水印信息容量大，植入、 提取水印过程速度快，提取水印过程中不需要原始网格模型信息等特点，适用于 公有水印算法，两种算法都能抵抗一般的几何变换攻击，例如旋转，平移，整体 放缩等网格变换，但是不能抵抗仿射变换这类攻击。 6 b e n e d e n s 强壮水印算法 b e n e d e n s 7 , 8 提出了调整网格曲面法向矢量分布的隐秘水印算法。三维模型对 象可以视为大小不一且有一定方向的曲面的集合，而曲面又可以用一系列网格构 成的平面片来表示或逼近，特殊情况下可以用三角面片来表示。如果嵌入水印后 网格顶点发生变化，相应地就会引起网格曲面的法向量分布发生变化，但这样得 到的网格较之原始网格的拓扑关系或邻接关系没有发生变化。该算法首先根据质 点中心和三角面片中心构造一致的曲面法向量，然后确定嵌入水印信息的基本几 何单元一一b i n 的法向量( 在前期处理时，首先将模型根据法向量划分为不同的集 合b i n ，一个b i n 是一个曲面的集合，可以用于嵌入l b i t 的水印信息) ，最后水 印嵌入是通过沿一定方向移动b i n 的质心，即平均法向量，如果有n 个比特的水印 信息，就要移动r 1 个b i n 的质心。移动过程是通过替换网格顶点进行的，这样也就改 1 0 山东大学硕士学位论文 变了三角面片的法向量，从而改变了这些法向量所属的b i n 的质心。该算法对数据 点的随机化、网格重构造和网格简化具有较好的鲁棒性。 7 w a g n e r 强壮水印算法 w a g n e r 2 8 埽0 用图象水印中将水印加入到象素值较低位这种简单水印技术思 想，构造一组对各种变换操作不变的参数向量空间，通过修改每个向量的相对长 度值植入水印。实验证明这种算法对各种几何变换和仿射变换具有较好的抗攻击 性。算法的水印提取过程不需要原始网格模型的信息，适用于公有水印系统。算 法对输入网格模型的拓扑结构没有特殊的要求，可以处理任意结构的网格模型。 但对于重建网格等攻击操作算法抵抗性不足。 8 t o u b 算法 t o u b 【2 9 1 提出了一种有效的加入授权信息的水印算法。算法在不改变网格连通 性的条件下对原始网格模型顶点坐标进行互为相反方向的扰动，生成两个扰动网 格模型a 和b ，然后按照水印信息位数对原始网格模型顶点集合进行划分，当水印 位为1 时，相应顶点集合的坐标采用模型a 中的坐标，当水印位为0 时采用模型b 中的坐标，这样就构成了一个水印网格模型。该算法能够抵抗平移，旋转，均匀 放缩，裁剪和顶点随机排序等操作攻击。水印提取过程需要扰动网格模型的信息， 适用于私有水印系统。 9 b o r s 等的盲水印算法 图2 4 包围椭球 b o r s 等 3 0 3 1 1 提出了一种基于邻接区域信息的三维网格盲水印算法。首先定义 山东大学硕士学位论文 一个点到其邻接点的距离函数，计算出模型中所有点的函数值，然后根据此距离 函数值对点进行排序，然后从小到大的挑出邻接区域不重叠的点，将这些点作为 水印的嵌入位置。水印的嵌入过程提供了两种方案：一种是平行平面嵌入法，根 据邻接点的法向量计算出这个区域的法向量，然后对中间点在这个区域法向量上 施加扰动，以此来实现水印信息的嵌入；另一种方式的包围椭球嵌入法，这种方 法是根据邻接点的信息确定一个包围椭球，如图2 4 ，然后以此椭球为标准扰动 中点的坐标，以此来实现水印信息的嵌入。这种水印算法的优点是在提取时不需 要提供原始模型数据，实现起来方便、快捷，但也存在着鲁棒性不高，易受到针 对性攻击等缺点。 2 3 2 频域三维网格数字水印算法 1 多分辨率小波变换算法 k a n a i 和d a t e 等1 1 7 1 首次应用变换域内的信号处理技术，提出了一种基于多分 辨率小波分解的三角网格的隐秘数字水印算法。该算法首先多次应用小波变换， 将原始网格v o 分解为多分辨率表示，得到一组针对不同分辨率的小波系数矢量 w 1 ，w 2 ，w 6 和粗糙的网格逼近模型v d ，通过修改小波系数矢量的模嵌入水印数 据，再用这些修改过的小波系数矢量“w 1 ，w 2 ，“w 8 进行小波反变换，就得到 嵌有水印的网格v o 。嵌入过程如图4 所示，该算法的水印提取过程比较简单，通 过计算经过小波变换后嵌有水印的网格和原始网格得到不同分辨率的小波系数 矢量的偏差，就可以确定嵌入的水印信息。这种水印算法类似于图象水印中的频 域算法，优点是通过选择较大的小波系数向量来植入水印可使得水印有更好的不 可见性；水印可以植入到模型的不同分辨级别中，增加了算法的抗攻击能力。缺 点是算法只能严格适用于具有一分四子分连通性的网格模型；植入和提取过程的 计算量大。 2 p r a u n 算法 p r a u n 等【”i 提出了一种鲁棒性水印算法。该方法将变换域水印应用在网格水 印，把传统的扩展频谱的思想应用到了三维水印上。他们利用多分辨率分析的思 想，对网格顶点构造一组标量基函数，并把基函数作为权值，对网格的顶点坐标 进行加权的轻微扰动。该算法的优点是对多种攻击具有鲁棒性，但是也存在着计 算量大，需要进行复杂的多分辨率分析等缺点，对于复杂的三维模型实现起来比 1 2 山东人学硕士学位论文 较困难，水印信息是实数序列而不是二值序列。 3o h b u e h l 频域算法 该算法n 9 采用对三维