（计算机应用技术专业论文）基于小波变换的三维网格压缩技术的研究.pdf

基于小波变换的三维网格压缩技术的研究 徐涛( 计算机应用技术) 指导教师：李宗民教授宫法明副教授 摘要 为了更加真实的表现三维物体，三维网格模型的数据量越来越大， 给存储、处理和网络传输带来了困难，因此有必要对三维图形数据进 行高效的压缩，以减少存储空间，节约网络带宽，缩短传输延时。同 时，有效的压缩还能增强大型三维图形的交互能力。 注意到三维网格顶点坐标间的强相关性和拓扑连接符号表示的集 中性，提出了在三缝网格压缩技术中引入小波变换技术，以利用小波 变换的能量集中性、去相关性以及与多分辨率分析的关系来提高三维 网格的压缩效率和比率。 提出的基于小波变换的单一位率压缩算法中，首先利用m a p s 算 法对初始的非正规网格进行重新网格化处理，得到一个半正规网格， 然后利用小波变换对其进行多分辨率分解，得到一个非正规的粗糙基 网格和表示网格层次细节的小波系数。分别对基网格使用改进的 e d g e b r e a k e f 算法编码，对小波系数量化后进行算术编码，最后将编码 的结果按照设计的文件格式写入统一的文件中，从而达到了单一位率 压缩的目的。通过实验对比，选取伽p 小波变换用于实验压缩比率 优于e d g e b r e a k c r 算法，由于重新网格化和小波变换的原因，压缩耗时 和解码耗时较多。 提出的基于小波变换的渐进压缩算法首先将初始网格的拓扑连接 信息编码压缩，与重新网格化得到的基网格就能重构初始网格的基本 拓扑连接关系。对于网格的层次细节，不仅利用了它们之间的空间相 关性，而且考虑到了它们的时间相关性，即将各层次细节作为不同时 刻的“帧”，提出了针对各层次细节压缩的f - i - 3 d 压缩模式，即使用 一个基于时间提升方案的小波变换用于对各时刻“帧”之间的时间相关 性进行去相关，使用l o o p 提升小波对“帧”内几何细节进行小波系数 表示，对产生的小波系数进行量化编码后加入到传输位流中。实验结 果显示，对于大型的三维模型，该方案获得了较好的压缩率，并在解 码时表现出较为满意的渐进显示。 关键词：三维网格压缩，单一位率压缩，渐进网格压缩，小波变换 e f f i c i e n tc o m p r e s s i o nt e c h n i q u e s f o r3 dm e s h e su s i n gw a v e l e tt r a n s f o r m x u t a o ( c o m p u t e ra p p l i c a t i o nt e c h n o l o g y ) d i r e c t e db yp r o f e s s o rl iz o n g - m i n a n da s s o c i a t ep r o f e s s o rg o n g f a - m m g a b s t r a c t i no r d e rt or e n d e r3 do b j e c t sm o l er e a l i s t i c a l l y , 3 dm e s hm o d e l p r o d u c e sad r a m a t i ca m o u n to f d a t a , w h i c hc o m p r i s e so f ab i gp r o b l e m f o r s t o r a g ea n dw e bt r a n s m i s s i o n as u b s t a n t i a lc o m p r e s s i o ni sh e n c ee s s e n t i a l f o rt h ed a t ao f3 do b j e c t st or e d u c et h es t o r a g e ，s a v en e t w o r kb a n d w i d t h a n ds h o r t e nt r a n s m i s s i o nd e l a y b e s i d e s ，a l le f f i c i e n tc o m p r e s s i o nc a l la l s o s t r e n g t h e nt h ei n t e r a c t i v ec a p a b i l i t yo f3 dg r a p h i c s t a k i n ga c c o u n to f t h es t r o n gc o r r e l a t i o n sa m o n gt h e3 dm e s hv e r t e x c o o r d i n a t e sa n dt h ec o n c e n t r a t i o no ft h es y m b o l sr e f e r e n c i n gt h e c o n n e c t i v i t y , a l l e f f i c i e n tc o m p r e s s i o ns c h e m ef o r3 dm e s h e su s i n g w a v e l e tt r a n s f o r mw a st h e np r o p o s e dt oi m p r o v et h ec o m p r e s s i o nb i t - r a t e o f3 dm e s h e sw i t ht h eh e l po fe n e r g yc o n c e n t r a t i o n , d e c o n e l a t i o na n d m u l t i - r e s o l u t i o nr e l a t i o n t h ef i r s ta l g o r i t h r np r o p o s e dh e r ei st h es i n g l e r a t ec o m p r e s s i o nb a s e do i lt h ew a v e l e tt r a n s f o r m ，w h i c ha p p l i e sa l lm a p s a l g o r i t h mo n t h ei r r e g u l a ro r i g i n a lm e s ht oo b t a i nas e r n i - r e g u l a rm e s hi na p r o c e s so fr e m e s h i n g ，t h e nw a v e l e tt r a n s f o r mw i l lb eu s e dt oe x e c u t ea m u l t i - r e s o l u t i o nd e c o m p o s i t i o ng e n e r a t i n ga ni r r e g u l a rc o a r s em e s h ( b a s e m e s h ) a n das e q u e n c e o fw a v e l e tc o e f f i e i e n t sw i t ht h eh i e r a r c h i c a l g e o m e t r yd e t a i l s a ni m p r o v e de d g e b r e a k e ra l g o r i t h ma n da r i t h m e t i c c o d i n ga r es e p a r a t e l ye m p l o y e dt ot h ec o d i n go ft h eb a s em e s ha n dt h e q u a n t i z a t i o no f w a v e l e tc o e f f i c i e n t s b o t ht h ee n c o d i n gr e s u l t sw i l lf i n a l l y b ew r i t t e ni n t oo n eu n i f i e df i l ew i t l lad e s i g n e df o r m a t b yt e s t e dw i t l lt h e l i f t i n gl o o pw a v e l e t , b u t t e r f l yw a v e l e ta n dt h el i f t i n gb u t t e r f l yw a v e l e t ， t h ec o m p r e s s i o nr a t i oo ft h i sa p p r o a c hs h o w sab e t t e rp e r f o r m a n c et h a n e d g e b r e a k e ra l g o r i t h m h o w e v e rt h et i m ec o s tf o rt h ec o m p r e s s i o na n d d e c o m p r e s s i o ni sl a r g e rd u et ot h er e m e s h i n ga n dw a v e l e tt r a n s f o r m an o v e la l g o r i t h mo fp r o g r e s s i v ec o m p r e s s i o nb a s e do nw a v e l e t t r a n s f o r mp r o p o s e di nt h i sp a p e rd e a l sw i t ht h ec o n n e c t i v i t yo f t h eo r i g i n a l m e s ha n dc o n s e q u e n t l yr e c o n s t r u c t st h eb a s i ct o p o l o g i c a lr e l a t i o n so ft h e r e m e s h e db a s em e s h n o to n l yt h es p a t i a lc o r r e l a t i o n sb e t w e e nt h e d i f f e r e n tl e v e l so fd e t a i l sb u ta l s ot h et i m ec o r r e l a t i o n sa r ee x p l o i t e dt o e n h a n c et h ec o m p r e s s i o nr a t i o ac o n c e p to f “f r a m e ”，w h i c hr e p r e s e n t s d i f f e r e n tl e v e l so fd e t a i la td i f f e r e n tt i m e ，i si n t r o d u c e di n t ot h es t a t i cm e s h ac o m p r e s s i o nm o d eo ff + 3 d ( a3 dm e s hw i t h i nat e m p o r a lf r a m e ) i s t h e na c h i e v e d t h et e m p o r a lc o r r e l a t i o n sa m o n gt h ef r a m e sa td i f f e r e n t t i m ew i l lb ed e c r e a s e db yu s i n gat e m p o r a l b a s e dl i f t i n gw a v e l e t n e i l g e o m e t r yd e t a i l s i naf r a m ew i l lb et r a n s l a t e di n t os e v e r a lw a v e l e t c o e f f i c i e n t sw h i c hw i l lb ej o i n e di n t ot h eb i ts t r e a ma f t e rq u a n t i z a t i o na n d e n c o d i n g e x p e r i m e n t a lr e s u l t ss u g g e s tt h a tt h ea l g o r i t h ma c h i e v eag o o d c o m p r e s s i o nr a t i of o rl a r g e r3 dm o d e l s ，a n dt h a tt h ep e r f o r m a n c eb e s a t i s f a c t o r yi nt h ep r o c e s so f p r o g r e s s i v ed e c o d i n g k e yw o r d s ：3 dm e s hc o m p r e s s i o n ；s i n g l e r a t ec o m p r e s s i o n ；p r o g r e s s i v e c o m p r e s s i o n ；w a v e l e tt r a n s f o r m 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 中国石油大学或其它教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说 明并表示了谢意。 签名：筮：煎a 一年 午月j 日 关于论文使用授权的说明 本人完全了解中国石油大学有关保留、使用学位论文的规定，即： 学校有权保留送交论文的复印件及电子版，允许论文被查阅和借阅； 学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复 制手段保存论文。 ( 保密论文在解密后应遵守此规定) 学生签名 导师签名 4 - 月 厶月 1日 j日 中国石油大学( 华东) 硕士论文第1 章绪论 第1 章绪论 1 1 三维网格压缩技术的研究背景 在计算机发展初期，人们就开始从事计算机图形的开发研究，从 计算机图形学诞生发展到现在，在许多领域扮演着越来越重要的角色。 直到计算机硬软件和计算机图形学高度发达的九十年代，人们发现复 杂的数据以视觉的形式表现时是最易理解的，因而三维图形得以迅猛 发展，计算机图形学的特点之一是广泛地使用三维图形数据来描述物 体与场景。随着计算机图形学及其相关理论和技术的快速发展，所使 用的三维数据的规模和复杂程度也在不断地急剧增长着。 数字化技术和i n t e m e t 的迅速发展，使三维图形技术和互联网紧密 结合起来，并且产生了大量重要、有意义的应用，如数字博物馆，网 上虚拟商城，3 d 网络游戏，虚拟仿真等，另外在c a d c a m 、电子商 务和数据场可视化等领域也有重要的应用。在实际应用中，通常采用 网格模型来表示三维物体，这其中有三角网格，四边形网格，六角形 网格等。为了尽可能的逼近原始三维物体，通过三维建模软件和三维 扫描获取的三维网格模型的数据量都比较大，这给存储、处理和网络 传输以及浏览带来了很大困难，直接存储和传输如此庞大的数据不但 开销很大，而且有时设备也承受不了如此大的负荷。虽然计算机的数 据处理能力和网络带宽也在迅速发展，但与三维图形的数据量和复杂 程度相比，仍然不足。在这样的背景下，要想使三维图形像普通的文 本、图像、视频等各种多媒体信息一样方便的浏览、下载，就目前的 网络带宽和速度以及硬件设备性能来说，是非常困难的。因此，必须 中国石油大学( 华东) 硕士论文第1 章绪论 对三维图形数据进行高效的压缩，来减少存储空间的需求，节约网络 带宽，缩短传输延时。同时，通过有效的压缩，可以充分发挥三位图 形的逼真性和强大的交互性、虚拟性，这对于三维动画和3 d 场景的实 时交互来讲是非常重要的。 自上世纪9 0 年代以来，三维网格压缩技术得到了快速的发展和应 用，在近几年的s i c - g r a p h 大会上，几乎都有关于网格及其压缩技术 的内容“i ，另外，三维网格压缩技术已经被有关国际标准采用：v r m l l 2 1 制定了三维模型网络传输的标准；m p e g - 4 1 3 1 融合了拓扑手术和渐进森 林分裂两大技术，包含了三维网格编码算法来对图形数据进行有效的 编码。 三维网格压缩技术1 4 , 5 , 6 】按照解码方式，分为单一位率压缩和渐进 压缩。在单一位率压缩中，网格中的拓扑连接信息和几何数据作为一 个整体进行编码压缩、传输和解码，解码端只有获取整个压缩数据序 列后才能进行解码操作；而渐进网格压缩技术则可以在压缩和传输的 过程中，由解码端根据正在接收的( 部分) 数据序列构造不同近似程度 的网格。 1 2 小波变换与计算机图形学 在纯科学和应用工程领域中，小波和小波变换的出现越来越多， 计算机图形学由于其众多的计算问题，也需要小波和小波变换的参与。 小波研究的一个迫切问题是如何将小波研究所取得的重要成果变为工 程技术人员所掌握的重要工具，使之尽快应用到工程技术实践中去。 特别是将小波分析很好地用于多媒体图像和信号处理。 当然，将小波技术应用于三维数据压缩也就成为了当前研究的重 2 中国石油大学( 华东) 硕士论文第1 章绪论 点，在s i g g r a p h9 4 和s i g g 心h9 5 以及9 6 年会上都成功的举办了 关于小波的课程讲座【7 1 。在计算机图形学中，多分辨率技术和分层技 术作用重大且研究的时间较长，小波和小波变换的引入更使其获得了 长足的推进和发展。 由于小波和小波变换在信号处理和谐波分析中的成功应用，它们 目前被应用在一些重要的计算机图形学研究领域，并且产生了许多高 效且简单易行的算法。如在图像压缩和处理中，许多高效的压缩算法 都应用了小波变换技术；基于小波变换技术的多分辨率表示，能够对 三维物体进行分级建模，简化并促进了对图形曲线和曲面的编辑工作； 在计算机动画领域中，许多在建模和动画领域固有的受约束的最优化 问题可以使用小波技术快速而健壮的解决；此外还有体数据的渲染和 处理以及图像查询等领域，都用到了小波变换技术。 1 3 基于小波变换的网格压缩技术 这些年来，小波变换在图像处理中得到了广泛的应用，关于小波 变换的图像压缩算法的研究和应用都十分活跃。作为一种优秀的图像 压缩算法，小波变换在三维数据压缩方面具有非常好的应用前景，具 体到三维网格图形方面，小波变换在单一位率压缩和渐进网格压缩中 都有着重要的作用。 目前各种单一位率压缩方法的基本思路都比较类他a t 4 ，即在压缩 连接信息时，首先采用某种遍历方法对网格进行遍历，并将遍历的结 果表示成某种符号序列，然后再对这个符号序列进行熵编码；而在压 缩几何信息时，则先对每个顶点用遍历路径上的相邻顶点来进行预测， 以去掉相邻顶点坐标间的相关性，然后对预测误差进行熵编码。如果 中国石油大学( 华东) 硕士论文第l 章绪论 基于小波变换来做压缩，那么其对连接信息而言，重新网格化可以去 掉大部分连接信息；对几何信息而言，由于小波变换具有很强的去相 关能力，即小波变换后大部分小波系数的值集中在零附近，有利于进 行熵编码，因此，利用小波变换来做非渐进压缩应该可以取得很好的 压缩性能。 三维网格的渐进压缩 4 1 将初始网格进行多分辨率分解，将其转换 为一个简单的粗糙网格和各层次细节的位流序列，并进行相关的压缩 编码和传输。通过解码，网格的连接信息和几何信息可通过此位流序 列重构。渐进压缩主要的优点是提供了对网络传输中的三维物体中间 状态的访问。一个半正规曲面的表示是不同分辨率层次的近似序列， 相应的嵌套细节的序列通过小波变换可以转换为一个包括基网格和小 波系数序列的表示，小波系数表达了连续的网格层次细节之问的差异。 如此，压缩的关键就是如何选择合适的小波去最佳的模拟小波系数的 统计分布，这里“最佳”的意思是对几何信息进行去相关，以获得小 波系数的分布，对其进行高效的压缩。对于模型压缩，小波变换的编 码压缩方案加上初始的半正规网格化操作( 用以生成基网格) ，可以取 得良好的压缩效果，因为基网格最佳的体现了网格的几何信息和重要 特征。所以小波变换的渐进网格压缩技术中的一个重要的问题是如何 产生最佳的基网格。另外一个问题就是小波与小波变换方案的选择， 使其能最佳的去除当前网格中几何信息之问的相关性。 1 4 研究目标和主要研究内容 通过对三维网格的单一位率压缩技术和渐进压缩技术的综述性研 究，利用小波变换的强去相关能力，提出了基于小波变换的三维网格 4 中国石油大学( 华东) 硕士论文第1 章绪论 压缩技术。主要研究内容包括以下几个方面： ( 1 ) 通过对三维网格压缩技术的总结和分析，设计并实现三维网 格单一位率压缩统一框架，并以该框架为实验平台，进行基于小波变 换的三维网格压缩技术方案的实验验证。 ( 2 ) 提出基于小波变换的三维网格单一位率压缩技术方案。通过 改进的e d g e b r e a k e r 算法提高简单网格和基网格的压缩率，利用小波 变换的强去相关能力，降低三维几何坐标间的空间相关性，达到几何 信息的有效压缩。 ( 3 ) 针对静态网格的渐进压缩传输，建立基于小波变换的f + 3 d 压缩模式。对大型三维网格，利用多分辨率分析技术，将静态网格按 照时间提升小波变换进行分帧，对帧间几何信息进行基于小波变换的 编码压缩。该方案不仅利用了几何层次细节之间的空间相关性，而且 考虑到了它们渐进传输时的时间相关性，从而减少传输位流的信息量， 提高渐进压缩的比率。 ( 4 ) 为了提高压缩效率，为基于小波变换的单一位率压缩方案设 计压缩文件格式，针对基于小波变换的渐进压缩设计传输位流的格式， 并根据实验需要进行相关文件格式的转换。 1 5 论文的组织结构 论文的组织结构安排如下： 第1 章绪论部分简单介绍了三维网格压缩技术的研究背景和小波 变换在计算机图形学中的应用，之后介绍了小波变换在网格压缩技术 中的应用方法。 第2 章首先介绍了三维网格压缩中的基本概念术语，主要对单一 中国石油大学 华东) 硕士论文第1 章绪论 位率压缩算法和渐进压缩算法进行综述性介绍，并进行了相应的算法 对比，最后介绍了与压缩密切相关的编码算法。 第3 章主要是关于小波与小波变换的知识，除了基本概念外，主 要阐述了小波变换和多分辨率分析的关系，并就小波交换在计算机图 形学中的应用，以及如何在三维网格压缩中使用小波变换进行了阐述。 第4 章提出了基于小波变换的三维网格单一位率压缩方案，通过 设计的单一位率压缩统一框架平台，应用改进的e d g e b r e a k e r 算法和 l o o p , 波变换，对三维模型进行了实验分析。 第5 章对小波变换在渐进网格压缩中的应用进行了叙述，提出了基 于小波变换的渐渐压缩方案，建立了一个基于静态网格的f + 3 d 的压 缩模式，并进行了实验分析。 第6 章对论文的工作和创新点进行了总结，并给出了进一步研究 的内容。 6 中国石油大学( 华东) 硕士论文第2 章三维网格压缩技术概述 第2 章三维网格压缩技术概述 三维网格压缩技术作为三维图形领域中的重要研究内容，可以将 大型复杂的三维模型进行单一位率压缩和渐进压缩，从而降低所需存 储空间，缩短网络传输延时，加快渲染速度。本章首先介绍了与三维 网格压缩相关的术语和概念，然后将单一位率压缩算法分为连接信息 驱动的算法和几何信息驱动的算法，分别进行了分析和总结，对渐进 网格压缩算法进行了归纳后，介绍了与压缩密切相关的编码算法。 2 1 基本概念 在三维空间中，使用微分的思想，可以将一个三维物体用一系列 的平面多边形来表示，即采用网格模型来表示三维物体，如图2 1 所示。 其中( a ) 为t o r u s ( 圆环面) 的三角形网格表示，( b ) 为t o r u s 的四边形网格 表示。 ( a ) t o r u s 的三角形网格表示( b ) t o r u s 的四边形网格表示 图2 】t o r u s 的三维网格表示 2 1 1 网格与三角形网格 在计算机图形学中，m = ( k ，m ) 称为多边形网格( 简称为网格) ， 7 中国石油大学( 华东) 硕士论文第2 章三维网格压缩技术概述 其中k = ( 矿，五，f ) 为单纯复形，表示网格的拓扑信息，y ，e 和f 分别 为顶点、边和面的集合。o ：v _ 胄3 是顶点到三维空间的单射。如果k 为三角单纯复形，称m 为三角形网格：置为四边形单纯复形，则称m 为四边形网格；k 为六边形单纯复形，则称m 为六角形网格。因为在 许多仿真算法中，把三角形作为标准图形显示的最基本的几何图元， 所以大多数的网格压缩算法集中在三角网格压缩上，论文也基于三角 网格模型进行相关的研究。 2 1 2 流形网格与可定向网格 在一个三维网格中，如果它的每个顶点的邻域与一个打开扇形或 半扇形同胚，就称此网格为流形网格( m a n i f o l dm e s h ) 【6 】。 一个多边形的方向由它的边界顶点的顺序指定，当相邻的多边形 在它们的公共边上方向相反时，称两个多边形方向兼容。在三维网格 图形中，如果存在一个多边形方向的排列，使得每一对相邻的多边形 的方向兼容，就称该三维网格是可定向能j ( o r i e n t a b l e ) 1 6 ) ，否则为不可 定向。 图2 2 显示了三种不同的流形和定向的示例，具体到网格图形，可 以参考图2 3 所示的麦比乌斯带，它是经典的不可定向模型。 渗易 ( a ) 可定向流形 ( b ) 不可定向非流形( c ) 可定向非流形 图2 2 流形与定向网格图形示例 中国石油大学( 华东) 硕士论文第2 章三维网格压缩技术概述 2 1 3 网格的价与亏格 耍 图2 - 3 麦比乌斯带图2 - 4 顶点的价与面的度 亏袼( g e n u s ) ：一个没有边界的连接的可定向流形网格的亏格【6 1 即是它 的柄的数目。例如，球体没有柄，它的亏格为0 ，花环有一个柄，8 字 形网格有两个柄，它们的亏格分别为l 和2 。 ( a ) 球体s p h e r e( b ) 花环t o m s ( c ) 八字形网格e i i g h t - s h a p c dm e s h 图2 - 5 网格的亏格 2 1 4 网格的拓扑关系 一个多边形网格所表达的信息通常分为两部分：拓扑信息和几何 信息。拓扑信息又称为连接信息，用于描述网格中顶点和面之间的相 互连接关系；几何信息用于描述顶点的位置坐标，以及附着在网格上 的其他信息，包括颜色、法向及纹理坐标等。 9 中国石油大学( 华东) 硕士论文第2 章三维网格压缩技术概述 对于一个无边界的连接的可定向流形网格，有以下关系【8 1 ： vp+，=229(2-1) 其中v ，e ，盼别为顶点数，边数和面的数目，g 为网格的亏格。 如果一个三角流形网格中边和三角形的数目足够大，因为通常两 个三角形共享一条边，则边的数目可以近似为： e z 3 f 2c - 2 ) 将公式( 2 2 ) 代入公式( 2 1 ) ，我们得到v z f l 2 2 2 9 ，因为 z 远大于2 2 9 ，可以忽略，于是得到 1 ，* s 2( 2 - 3 ) 由公式( 2 3 ) ，可以得知，在典型的三角网格中，三角形的数目约 为顶点数目的2 倍。 从( 2 - 2 ) 和( 2 3 ) ，我们还可以得到如下关系： p 3 v ( 2 - 4 ) 因为顶点的价( v a l e n c e ) 是与该顶点关联的边的数目，所以，价的 数目为边的数目的2 倍，于是有以下公式： v a l e n c e = 2 e 6 v ( 2 5 ) 一 可以得知，在典型的三角网格中，顶点的价的平均值为6 。其他类 型网格的欧拉关系也可以如上得到。 2 2 三维网格压缩技术的分类 三维网格压缩技术按照解码方式，分为单一位率压缩( s i n g l e - r a t e c o m p r e s s i o n ) 和渐进压缩( p r o g r e s s i v ec o m p r e s s i o n ) 。单一位率压缩又称 0 中国石油大学( 华东) 硕士论文第2 章三维网格压缩技术概述 为非渐进压缩( n o n p r o g r e s s i v ec o m p r e s s i o n ) ，网格中的拓扑连接信息 和几何数据作为一个整体进行编码压缩、传输和解码，解码端只有获 取整个压缩数据序列后才能进行解码操作；而渐进网格压缩技术则可 以在压缩和传输的过程中，由解码端根据正在接收的( 部分) 数据序列 构造不同近似程度的网格。 早期的单一位率压缩算法主要考虑连接信息压缩编码，网格的几 何数据压缩在其基础上进行，称为连接信息驱动的压缩。考虑到几何 数据占据了网格数据的大部分，最近人们提出了一些新方法，以几何 数据编码为主，连接信息编码在几何编码的驱动下进行，有时候为了 获得较高的压缩率，甚至改变原始网格的拓扑连接，称为几何信息驱 动的压缩方法。 2 3 单一位率压缩 2 3 1 连接信息驱动的压缩算法 早期的单一位率压缩算法主要考虑拓扑连接信息的压缩编码，网 格的几何数据压缩在其基础上进行，称为连接信息驱动的压缩算法。 以三角网格为例，在压缩拓扑连接信息时，先以某种数据结构表示网 格拓扑连接信息( 如树形结构) ，然后采用某种遍历方法( 如深度优先遍 历】，遍历网格中的顶点和三角形，将遍历过程表示为某种符号序列， 然后对该符号序列进行编码压缩，解码的过程为其逆过程。压缩几何 数据时，一般先对顶点坐标进行量化，然后采用某种预测方法进行顶 点预测，再对预测误差进行编码压缩。 表示网格图形的最简单的方法是v r m l a s c i i 格式1 2 】采用的索引 面组，它用一个坐标数组存储三角网格中所有顶点的坐标，用一个面 中国石油大学( 华东) 硕士论文第2 章三维网格压缩技术概述 数组列出每个三角形面和它的三个顶点的对应关系。图2 - 6 ( a ) 表示了一 个网格图形，( b ) 为其索引面组表示。 i n d e x f a c e l ( 0 1 , 4 ) 2 ( 1 , 3 ，4 ) 3 ( i ，2 , 3 ) ( a ) 三角网格( b ) 索引面组 图2 - 6 网格图形的索引面组表示 若网格图形中有v 4 n 点，则索引每个顶点的编码需要l o g ：v 位， 一个三角形就需要3 l o g ：v 位来存储它的连接信息。根据公式( 2 - 3 ) ，网 格中三角形数目大约是顶点的数目的2 倍，因此，一个三角网格图形的 连接信息编码需要6 l o g ，v 位。在索引面组表示方法中没有采用任何的 压缩技术，但它提供了一种表示网格图形最简单的方法。 综合目前的单一位率压缩算法和采用的建模结构，针对拓扑连接 信息编码，将连接信息驱动的压缩算法分为以下几类。 ( 1 ) 三角形带方法 在图2 6 中，与顶点v l 邻接的三角形t o 、t l 和t 2 在面数组中索引v l 三次，这种重复的顶点索引降低了连接信息的编码效率。为解决这个 问题，将物体的三角形组织成三角形带( t r i a n g l es a i p ) 的结构进行绘 制。 三角形带方法将一个三维网格划分为长三角形带，然后对这些三 角形带进行编码压缩。图2 - 7 ( a ) 显示了一个三角形扇形( 星形三角形 带) ，一个顶点和它的前一个顶点及第一个顶点组成一个新的三角形， 1 2 中国石油大学( 华东) 硕士论文第2 章三维网格压缩技术概述 为一个锯齿形三角形带，( c ) 则显示了一个广义三角形带，它由一个 锯齿形三角形带和一个三角形扇形组成。与索引面组方法相比，三角 形带方法提供了一个更为紧凑简洁的表示方法，当三角形带很长时， 三角形数目与顶点数目的比率可以接近1 ：1 ，这意味着一个三角形几 乎可以由一个顶点索引表示。 链。啦2 46 达酽。 ( a ) 三角扇形( b ) 锯齿三角带( c ) c 义三角带 图2 _ 7 三角形带的图形示例 d e 鲥n g 【9 1 首先引入了广义三角形网格的概念。一个广义三角形网 格由一个三角形带和一个顶点缓冲区组成，使用一个先进先出( f i r s t i n f i r s t o u t ) 的顶点缓冲队列来存储1 6 个最近访问的顶点的索引值。在顶 点缓冲队列中的顶点，可以利用缓冲队列的索引值表示，相对于全局 ( g l o b a l ) 顶点索引值来讲，这样的表示可以减少存储位。t a u b i n 和 r o s s i g n a c 1 川证明：对较大的网格图形，若每个顶点在缓冲区中只被索 引一次，一个普通三角网格图形大约需要1 1 助v ( b i t p e r v e r t e x ，位顶 点) 来对连接信息进行编码。但是d e e r i n g 没有提出将一个网格分解为 三角形带的方法。 基于d e e r i n g 的工作，c h o w t l l 】提出了一个适合实时表示的网格压 缩方案。在图2 - 8 的网格分解方法中，首先得到一组边界边e 1 、e 2 和 e 3 ，然后得到围绕边界边端点的三角形扇形t 1 t 6 。这些三角形扇形 组合成为一个普通三角形带，里面的三角形标示为已访问。接着，在 未访问三角形和己访问三角形之间产生下一组边界边f a e 8 。类似 中国石油大学( 华东) 硕士论文第2 章三维网格压缩技术概述 的，下一个三角形带t 7 t 1 1 就从新的边界边组中形成了。通过顶点 缓冲区，先前产生的普通三角形带中的顶点可以被再次使用。重复此 处理过程，直到网格中的所有三角形都被访问为止。 ( 2 ) 生成树方法 图2 8 网格分解为三角形带的方法 t u r a n 坨】使用两棵生成树( s p 锄n i n gt r e e ) 对平面图形的连接信息 进行编码，即顶点生成树和三角形生成树。t a u b i i i 和r o s s i 驴a c 【l o 】提出 了著名的拓扑手术方法( t o p o l o g i c a ls u r g e r y ) ，来对三角网格进行编码。 其目的是压缩几何数据，减少几何模型的磁盘空间，从而也可以减少 几何模型在网络上的传输时间。该方法首先为三角形网格构造棵顶 点树，然后沿着顶点生成树的边( 砍边，c u te d g e ) 将网格剪开，变成一 个没有内点的简单多边形( s i m p l ep o l y g o n ) ，使得它可以通过三角形生 成树( t r i a n g l es p a n n i n gt r e c ) 和一些二进制匹配码进行完整的表示。 图2 9 是一个八面体网格。该方法首先构造一个( b ) 图所示的顶点生 成树( v e n e xs p a n n i n gt r e e ，v s l ) ，v s t 中每个节点对应于输入网格中 的一个顶点，然后沿v s t 的边剪裁网格。( c ) 图显示了剪裁结果：一个 平面多边形和三角生成树( t r i a n g l es p a n n i n gt r e e ，t s d 。t s t 中的每 中国石油大学( 华东) 硕士论文第2 章三维网格压缩技术概述 个节点对应于多边形中的一个三角形。 ：众 ( a ) a 面体网格( b ) v s t( c ) t s t 图2 - 9 拓扑手术方法 然后，对两个生成树进行游程编码( r u nl e n g t he n c o d i n g ) 。度不为 2 的两个结点间的树段定义为一个游程。对v s t 中的每个游程，编码器 使用两个附加标志位记录它的长度，第一个标志位是分支结点位，用 以指明当前行程与其随后的行程是否开始于同一个分支结点；第二个 标志位是叶子标志位，指明当前行程是否结束于叶子结点。如图2 - 9 ( b ) 。 编码此v s t 时，以行程索引值标记每条边，第一个行程表示为( 1 ，0 ， 们，因为它的长度为1 ，下一个行程没有与当前行程开始于相同的结点， 并且结束于非叶子结点。以此方式，( b ) 中的v s t 表示为：( 1 ，0 ，o ) ( 1 ， l ，1 ) ( 1 ，0 ，o ) 0 ，1 ，1 ) ( 1 ，0 ，1 ) 。同样，对于t s t q a 的每个游程， 编码器记录其长度和叶子位。 在v s t 和t s t 中，游程是基本的编码单位，编码代价与游程的个 数成正比，即依赖于v s t 的构造方式。t a u b i n 和r o s s i g n a c 群j 算法基于 层次分解技术建立v s t ，以获取每个游程长度的最大化和游程个数的 最小化。实验显示，t a u b i n 和r o s s i g n a c 的算法对网格连接信息的编码 率可以达n 2 4 8 7 o h m 。而且该算法的时间和空间复杂度为d ( ) ， 其中n 为网格中v 、e 、f 数目的最大值。这种方法由于在解码状态执行 全局( g l o b a l ) 随机顶点访问，因此需要的内存缓冲较大。 l s 中国石油大学( 华东) 硕士论文第2 章三维网格压缩技术概述 ( 3 ) 层次分解方法 t a u b i n 茅l l r o s s i g n a c l l0 】在构造v s t 时，即使用了层次分解技术，但 - 与b a j a j 等人【1 3 】的方法有所不同，b a 3 a j 等人介绍了一种基于顶点层次 结构的连接信息编码方法，该方法将一个三角形网格分解为几个同轴 顶点层，然后在相邻的一对项点层间，构造三角层。所有顶点层的数 目就表示了网格的连接信息。网格的连接信息就由所有顶点层的个数、 每个顶点层的轮廓和每个三角层中三角形的外形表示。理想情况下， 顶点层不自相交，一个三角层通常是一个三角形带。这样，连接信息 的编码简化为对顶点层个数、每个顶点层中顶点数和每个三角层中三 角带的编码。但由于分支点和三角扇形的存在，往往需要增加额外的 空间。 b a j a j 等提出的算法没有将顶点层与v s t 结合在一起，但因为解码 时该算法只访问一小部分顶点，故其解码器不需要较大的内存缓冲区， 而且该算法适用于任意种类的网格拓扑结构，而t a u b i i l 和r d s s i 孕1 【1 0 】 的方法则不能直接对非流形网格进行编码。 层次分解方法对连接信息的编码可以达到1 4 0 - 6 0 8 皂，而且每 个三角形最多依赖于两个邻接顶点层，并且每个顶点层至多与两个三 角层相关联。这个特点能使网格数据进行误差复原( e r r o r - r e s i l i e n t ) ， 因为传输误差的影响可以通过对不同顶点和三角层的独立编码而使其 局部化。基于层次分解方法，b a j a j 等k 】还提出了对大型c a d 模型进 行编码的算法，这种算法将层次分解技术进行延伸扩展，使其能压缩 四边形和普通多边形网格。 刘新国提出的增量几何压缩算法【”j6 】也属于层次分解的方法。该 算法先定义了两种基本的层结构，第一种基本层结构称为l - s t r i p ，如 j 6 中国石油大学( 华东) 硕士论文第2 章三维网格压缩技术概述 图2 1 0 ( a ) 所示，l - s t r i p 非常类似于o p e n g l 图形库中的三角形带 ( t r i a n g l es t r i p ) ，区别在于顶点顺序不一样：l s t r i p 的顶点顺序是单向 增长的，而在o p e n g l q a 的三角形带的顶点顺序是双向增长，一个层如 果是l - s t r i p ，那么从与边( v o ，一，) 相连的三角形开始，层中的所有三 角形可以依次排序并编号。而且三角形的顶点在l - s t r i p 的内边界上是 连续排列的。第二种基本层结构称为0 - s t r i p ( 或环形层) ，如图2 - 1 0 ( b ) 所示。一个层结构作为o s t r i p 的条件是：层中的每一个三角形都至少 有一个顶点不在它的内边界上。通过区域增长方式将原三角形网格模 型分解为一系列简单的层结构，任何层都可以分解为这两种基本层结 构的并集。在区域增长的过程中，同时完成对层结构中三角形的编码、 顶点坐标的编码、以及区域增长过程的记录，从而实现对网格模型的 几何压缩。 k o ( a ) l - s t r i p ( b ) o - s t r i p 图2 1 0 增量几何压缩算法中的基本层结构 算法中还设计了非线性几何预测器对模型的几何信息进行压缩。 与以前的算法相比，该算法具有快速和高效的特点，实验表明，其算 法只需平均1 4 2 比特( b i t ) 就可编码一个三角形的拓扑信息，而且所提出 的压缩和解压缩算法仅具线性复杂度，执行速度非常快。 1 7 中国石油大学( 华东) 硕士论文第2 章三维网格压缩技术概述 ( 4 ) 价驱动方法 价驱动方法( v a l e n e e d r i v e n ) 利用顶点的价对网格的的拓扑信息 进行编码，其基本思想是边界扩张，即从一个种子三角形开始，该三 角形的三条边形成初始的边界线，边界线将整个网格分为两部分，也 即已处理完毕的内部和等待处理的外部。这样，边界线逐渐地向外扩 张，直到整个网格被处理完毕。该方法编码的结果为顶点价的输出流， 原始的连接信息即可由此重构。 t o u m a 和g o t s m a n t l 7 首先以价驱动方法进行三角网格压缩，即1 g 方法。该方法在网格上任选一个初始三角形，将其三个顶点放入一个 活动列表q a ( a e t i v el i s t ) ，并且取出其中一个顶点为焦点( f o c u s