（计算机科学与技术专业论文）基于几何图像的三维网格压缩.pdf

；骂，； 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 签名：鏊! 墅日期丝! 坚垒旦! 塑签名：銎銎日期丝! 坚鱼旦! 丝 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有 权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部 或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) ，r 摘要 摘要 随着三维扫描和建模技术的发展，三维网格成为继声音、图像、视频之后的 一种新型多媒体数据。由于三维网格数据规模和复杂程度的急剧增长，给三维网 格的存储、处理、网络传输以及浏览带来了很大压力。因此，必须对三维网格进 行高效的压缩。 基于几何图像的三维网格压缩方法，是将三维网格经过剖分、参数化、重采 样过程映射为二维图像，并利用图像编码方法压缩三维网格数据。几何图像作为 一种完全规格化的曲面表示形式，一经提出即受到关注，相关的研究工作正方兴 未艾。本文针对基于几何图像的三维网格压缩方法进行研究，期望获得三维网格 在主观和客观水平上的更好的压缩效果。本论文主要研究内容包括以下几方面。 基于几何图像的渐进式三维网格编码。利用支持渐进传输的j p e g 2 0 0 0 图像 标准实现基于几何图像的三维网格渐进式压缩方法，已经能够取得较好的实验结 果。然而，由于j p e g 2 0 0 0 中采用的传统小波变换不适于表达水平和垂直方向以 外的方向特征，会引起重建的三维网格在几何突变处产生失真，影响重建的主客 观质量。为此，采用方向提升小波变换的图像编码方法，针对几何图像和法向量 图像的不同特性，探索了不同的方向选择策略，以提高几何图像和法向量图像的 压缩效率，实现三维网格的主客观质量的提升。 基于几何图像的真实感三维网格编码。法向量图像包含的法向量信息是表现 三维网格绘制的真实感的重要因素。而几何图像和法向量图像的信号之间不具有 较强的相关性，因此直接采用现有的图像编码技术不能获得好的压缩效果。由于 几何图像和法向量图像均源于同一个三维网格，从而几何图像隐含了三维网格的 法向量信息。为此，将预测技术引入基于几何图像的真实感三维网格编码框架， 以便利用几何图像包含的几何信息预测法向量图像。为了提高预测精度，采用几 何拉伸度量提取预测的法向量图像的噪声点，并利用图像修复技术去除噪声。此 外，针对几何图像和法向量预测残差图像的特性，采用方向提升小波变换进行压 缩，通过灵活地选择小波变换的方向来适应几何图像和残差图像的纹理特性，以 保持重建模型的高频几何特性。该编码框架与分别编码几何图像和法向量图像的 方法相比，不仅提高了法向量图像的编码效率，而且大幅度地改善了三维网格的 真实感效果。 几何图像边缘区域的编码及重建。有损压缩导致了重建的三维网格在剖分路 径上出现裂缝，为此，针对三维网格剖分路径对应的几何图像边缘，采用感兴趣 区域编码和边缘修复技术缝合裂缝。 关键词三维网格；压缩编码；几何图像 北京工业大学工学硕士学位论文 ， a b s t r a c t a b s t r a c t w i t l lt 1 1 ed e v e l o p m e n to f3 ds c a n 血n ga n d3 dm o d e l i i l gt e c h n o l o g y 3 dm e s h h 弱b e c o m ean e w 哆p eo fm u l t i m e d i ad a t a ，a r e rm e 机i d i o ，i m a g ea n dv i d e o d u et o t 1 1 ed a t as i z ea n dc o m p l e x i t yo f3 dm e s hc o n t i n u eg r o wr a p i d l y ，g r e a td i m c u l t i e sh a s b e e nb r o u 曲tt 0t h es t o r a g e ，p r o c e s s i n g ，n e t w o r kt r a n s m i s s i o n ，a n db r o w s i n g t h e r e f o r e ，3 dm e s h 拙am u s tb ec o m p r e s s e de m c i e n t l y g e o m e t d ri r r l a g e _ b a s e d3 dm e s hc o m p r e s s i o nm e t h o dc a nm a p3 dm e s ht o2 d i m a g et h 】- 0 u g l lp a n i t i o n ，p 觚吼e t e r i z a t i o n ，a n dr e s 锄p l i n gp r o c e s s t h u s ，i i n a g e c o d i n gm e t h o dc a nb eu s et oc o m p r e s s3 dm e s h g e o m e t r yi m a g ei sac o m p l e t e l y r e g u l a rs t r i j c t u r et or e m e s ha i la r b i 位u ys ur f ：她e ，s oi tr e c e i v e dc o n s i d e r a b l ea n e n t i o n w h e np r o p o s e d ，a n dr e l a t e dr e s e a r c hw o r k sa r ei nt h ea s c e n d a n t i i lt h i sp a p e r l e g e o m e t 巧i m a g eb a s e d3 dm e s hc o m p r e s s i o nm e t h o dh 嬲b e e ns t u d i e d t h et a 唱e ti s t oa c m e v eb e t t e rs u b j e c t i v ea n do b j e c t i v er e c o n s t r u c t i o nq u a l i t yo f3 dm e s h t 1 1 e m a i nc o n t e n t si n c l u d e l ef o l l o w i n g p r o 鲈e s s i v e3 dm e s hc o d 访gb a s e do ng e o m e 时i m a g e u s i n gj p e g 2 0 0 0i i n a g e c o d i n gs 伽1 d a r d ，w m c hs u p p o r t i n gp r o g r e s s i v et r a i l s m i s s i o n ，t 0a c m e v eap r o g r e s s i v c 3 dm e s hc o m p r e s s i o nm e t h o db a s e do ng e o m e t 巧i i i l a g eh a sb e e na b l et oa c m e v e b e t t e rr e s u l t s h o w e v e r ，t h et m d i t i o n a lw a v e l e tt 啪s f o 肌w l l i c ha d o p t e dh lj p e g 2 0 0 0 ， i su n s u i t e dt oe x p r e s sc h a r a c t e r i s t i c sb e s i d e sh o r i z o n t a la n dv e n i c a ld i r e c t i o n n 、扼u l e a dt or e c o n g t n l c t e d3 dm e s hd i s t o r t i o no c c u r smm eg e o m e t r i cm u t a t i o nr e g i o 玛a n d a 雎c tm es u b j e c t i v ea n do b j e c t i v eq u a l i 够f o rt l l i sr e 硒o n ，a d o p 血gd c t i o l l a ll i m n g w a v e l e t 仕龇l s f o m 卜b a s e di r n a g e c o d i n gm e t l l o d ，锄ds e l e c t i n g d i 丘i e r e n td i r e c t i o n s 蚰? a t e g yf o rd i 毹r e n tc h a r a c t e r i s t i c s 自d mg e o m e t 巧i m a g et 0n o 衄a l m 印i m a g e s o 嬲t oh p r o v e 1 ec o m p r e s s i o ne 伍c i e n c yo fg e o m e t r yi m a g ea n di l o n n a l m 印i m a g e ， u l t i m a t e l yt 0a c t l i e v el l i g hs u 切e c t i v e 锄do b j e c t i v eq u a l i t yo f3 dm e s h r e a l i s t i c3 dm e s hc o d 岖b a s e do ng e o m e 蚵i m a g e 7 n l en o n n a lv e c t o r s c o n t a i n e di nn o n n a l - m a p 证l a g ec o n t r i b u t et 0r e a l i s t i cp e r f o m a n c eo f3 dm e s hw h e n r e n d i n g t l l es i 孕1 a l sb e t w e e ng e o m e 衄i i i l a g ea i l dn o m a l - m 印洫a g ed on o th a v e 蛐r o n gc o r r e l a t i o n s ，s ou s en l ee x i s t i n g i i n a g ec o d i n gt e c m q u e sd i i e c t l yc a nn o t o b t a i ng o o dc o m p r e s s i o nr e s u l t s a s 也eg e o m e t 叫i i i l a g ea n dn o 肌a l m a ph a g ea r e g e n e r a t e df i r o mt l l es a m e3 dm e s h ，g e o m e 仃yi m a g ei m p l yn o 肌a lv e c t o ri 州f 0 咖a t i o n o ft h e3 dm e s h w i t hr e g a r dt ot h i s ，t l l ep r e d i c tt e c l l n o l o g yl e a di n t 0 l e 缸吼e w o r ko f r e a l i s t i c3 dm e s hc o d i i l gb 弱e do ng e o m e t r yi l a g e ，觚dg e o m e t r i c 证f o m l a t i o ni i l g e o m e t qi m a g ea r eu s e dt op r e d i c tt h en o m a l m a pi m a g e t bi m p r o v em ep r e d i c t i o n a c c u r a c y g e o m e t r i cs 缸e t c hm e t r i cm e m o di su s e dt oe x 仃a c tt | l en o i s ei n 也ep r e d i c t e d n o 衄a l - m a pi m a g e ，强di i l l a g ei i l p a j n t i n gt e c h n i q u ei su s e dt or e m o v em en o i s e m o r e o v e r ，d i r e c t i o n a ll i r i i l gw a v e l e t 仃a n s f o n ni su t i l i z e dt oc o d i n gg e o m e 缸yi m a g e a n dr e s i d u a lr l o n l l a l m a ph i l a g e a c c o r d i l l gt ot l l e i rf e a n j r e s f o rm a i n t a i n l et l i 曲 i i i 、 北京工业大学工学硕上学位论文 f k q u e n c yg e o m e t r i cc h a r a c t e r i s t i c so ft h er e c o n s t r u c t i o nm o d e l ，s e l e c td i r e c t i o n so f w a v e l e tt r a j l s f o 衄n e x i b i yt oa d a p tt h ed i 船r e n tt e x t u r e c o m p a r et ot h em e t h o d w h i c hc o d i n gg e o m e t r yi i n a g e 锄dn o 肋a l m a pi m a g ed i r e c t l y ，t l l i sc o d i n g 行锄e w o r k n o to n l yi m p r o v e st l l ec o d i n ge f f i c i e n c yo fn o m a l - m 印i m a g e ，a 1 1 da l s oi m p r o v e st l l e r e a l i s t i ce 脏c to f3 dm e s hs i g n i f i c a n t l y c o d i n ga n dr e c o n s t r i j c t i o nf o rg e o m e t r yi m a g ee d g er e g i o n b e c a u s eo ft h el o s s y c o m p r e s s i o n ，t h ec r a c ka p p e a r si nt h es p l i tp a mo fr e c o n s t n j c t e d3 dm e s h f o rm i s r e a s o n ，r e g i o no fi n t e r e s tc o d i n ga n de d g er e p a i rt e c h n o l o g ya r eu t i l i z e dt 0f h s et h e c r a c kf o rt h ee d g eo fg e o m e 时i m a g ew m c hi sc o n e s p o n d i i l gt ot h ep a n i t i o np a mo f 3 dm e s h k e y w o r d s 3 dm e s h ；c o m p r e s s i o n ；g e o m e t 巧i m a g e i v 一 ， ， 目录 目录 摘要i a b s t r a c t i i i 第1 章绪论一l 1 1 研究背景及意义1 1 2 研究现状及前景。2 1 3 课题来源及研究内容3 1 4 本文结构3 第2 章三维网格压缩5 2 1 引言5 2 2 三维网格的数据表示5 2 3 三维网格的压缩方法5 2 3 1 静态网格压缩5 2 3 2 渐进网格压缩7 2 4 几何图像9 2 4 1 几何图像的生成算法lo 2 4 2 几何图像的编码1 3 2 5 本章小结1 4 第3 章基于几何图像的渐进式三维网格编码1 5 3 1 引言15 3 2 编解码框架15 3 3 基于小波变换的图像编码1 7 3 3 1 传统的基于小波变换的图像编码1 7 3 3 2 基于方向提升小波变换的图像编码1 8 3 4 基于方向提升小波变换的几何图像编码2 1 3 4 1 方向的选择2 1 3 4 2 率失真优化2 4 3 5 三维网格的渐进传输2 4 3 6 实验结果及分析2 5 3 7 本章小结3 0 第4 章基于几何图像的真实感三维网格编码3 1 4 1 引言31 4 2 编解码框架3l 4 3 法向量图像的预测3 3 4 3 1 法向量的计算3 3 4 3 2 几何拉伸的度量3 5 4 3 3 几何拉伸奇异点的判断3 7 4 3 4 非奇异点的法向量计算3 9 4 3 5 奇异点的法向量计算3 9 4 3 6 法向量预测图像的平滑过程4 1 4 4 法向量残差图像的计算4 3 v 4 5 图像编解码方法的选择4 5 4 6 实验结果及分析4 5 4 7 本章小结4 8 第5 章几何图像边缘区域的编码及重建4 9 5 1 引言4 9 5 2 几何图像边缘的感兴趣区域编码4 9 5 2 1 几何图像边缘编码存在的问题4 9 5 2 2 感兴趣区域编码4 9 5 2 3 感兴趣区域编码在几何图像的应用5 0 5 2 4 实验结果及分析5 2 5 3 几何图像边缘的重构5 4 5 3 1 几何图像边缘重构存在的问题5 4 5 3 2 获得对应关系5 4 5 3 3 缝合剖分路径5 5 5 3 4 实验结果及分析5 6 5 4 本章小结5 6 结论5 7 参考文献5 9 攻读硕士学位期间发表的学术论文6 1 致 射6 3 v i 第1 章绪论 1 1 研究背景及意义 第1 章绪论 迄今为止，多媒体技术的发展已经历了声音、图像、视频三种数据类型。随 着计算机图形学中三维扫描和三维建模技术的发展，数字化的三维图形数据开始 大量涌现，成为继声音、图像、视频之后的一种新媒体。正如声音、图像、视频 等多媒体数据类型给社会带来了深远的变革一样，三维图形正在而且必将给人类 带来巨大的价值，在商业、制造业、建筑业、教育、医学、娱乐、艺术、军事等 各个领域产生广泛的应用。 在计算机发展初期，人们就开始从事计算机图形的研究，从计算机图形学诞 生发展到现在，其在许多领域扮演着越来越重要的角色。直到计算机硬软件和计 算机图形学高度发达的九十年代，人们发现复杂的数据以视觉的形式表现时是最 易理解的，因而三维图形得以迅猛发展。随着计算机图形学及其相关理论和技术 的快速发展，所使用的三维数据的规模和复杂程度也在不断地急剧增长着。 计算机图形学的特点之一是广泛地使用三维图形数据来描述物体与场景。在 实际应用中，通常采用三角网格模型来表示三维物体。为了尽可能的逼近原始三 维物体，通过三维扫描或三维建模软件获取的三维网格模型的数据量都比较大， 这给存储、处理、网络传输以及浏览带来了很大困难。虽然计算机的数据处理能 力和网络带宽也在迅速发展，但与三维图形的数据量和复杂程度相比，仍然不足。 在这样的背景下，要使三维图形如同普通的声音、图像、视频等各种多媒体信息 样方便的浏览、下载，就目前的网络带宽和速度以及硬件设备性能来说，是非 常困难的，这始终是三维网格广泛应用和发展的瓶颈。因此，必须对三维图形数 据进行高效的压缩，来减少存储空间的需求，节约网络带宽，缩短传输延时。 三维图形有着较强的逼真性和交互性，能给用户带来图像、视频等媒体所不 具有的视觉感受，人们是生活在三维世界中的，逼真的三维图形场景可使用户感 觉就像是处于真实的世界中，并可以以多种方式与场景进行交互，从而给用户带 来身临其境的、沉浸式的体验。三维图形数据压缩和传输技术的发展将把三维图 形世界引入到互联网中，使未来互联网上的三维图形数据像文本、声音、图像、 视频一样普遍，使三维图形的真实性、自然性、交互性和互联网的广域性、普及 性相结合的分布式图形系统成为可能，从而改变人们的工作以及生活方式，产生 较大的社会应用价值。一些具体的应用实例有：分布式虚拟现实、数字博物馆、 网上虚拟商城、网络视频游戏、虚拟空间会议、自然人机接口、分布式协同设计、 地理信息系统、科学计算可视化等。 北京工业大学工学硕士学位论文 1 2 研究现状及前景 三维网格数据压缩的研究是涉及计算机图形学、数据压缩技术等学科的交叉 性课题。相对丁文本、声音、图像、视频等数据压缩的已有的大量研究工作，三 维网格数据压缩的研究还是一个较新的课题。三维网格数据与其它多媒体数据有 很多不同之处。例如，三维网格存在拓扑信息、几何信息、属性信息。拓扑信息 用于描述网格中顶点和面之间的相互连接关系；几何信息用于描述顶点的位簧坐 标；属性信息包括附着在网格上的其他信息，包括颜色、法向量及纹理坐标等。 三维网格的这些信息，使得以往的传统压缩方法不能简单地移植到三维网格数据 上，从而给三维网格压缩的研究带来了新的问题和挑战。 自上世纪9 0 年代以来，三维网格压缩技术得到了快速的发展和应用，在近 些年的s i g g r a p h 大会上，几乎都有关于网格及其压缩技术的内容。另外，三 维网格压缩技术已经被有关国际标准采用：v r m l 【1 】x 3 d 【2 l 制定了三维模型网络 传输的标准；m p e g 4 【3 】融合了拓扑手术和渐进森林分裂两大技术，包含了三维 网格编码算法来对图形数据进行有效的编码。与此同时，一些研究成果也纷纷进 入各大公司的相关产品中，如m i c r o s o r 的d i r e c t 3 d 、s u n 的j a v a 3 d 、i b m 的 h o t m e d i a 、以色列n u e 公司的v i r t u e 3 d ，以及1 1 1 t e l 、h p 的一些产品等【4 。 从发展趋势上看，编码方法逐渐从以前的以拓扑信息驱动的编码方式转为以 几何信息为驱动的编码方式【5 j 。早期的压缩算法主要考虑拓扑信息压缩编码，网 格的几何数据压缩在其基础上进行，称为拓扑信息驱动的压缩。而随着研究的不 断深入，这种依赖性不断减弱，并且拓扑编码以几乎接近理论极限。拓扑压缩的 方法已取得很大的进展，能达到每个顶点只需平均用1 4 个比特来记录拓扑信 息，基本上接近理论熵值【6 j 。但目前几何压缩的效率还不太高，这是三维模型压 缩的瓶颈。由于压缩数据中，几何数据比拓扑数据更多，因此高效的几何压缩方 法对于提高三维模型的压缩效率具有很重要的意义。考虑到几何数据占据了网格 数据的大部分存储空间，最近提出了一些新方法，以几何数据编码为主，拓扑信 息编码在几何编码的驱动下进行，有时为了获得较高的压缩率，甚至改变原始网 格的拓扑连接，称为几何信息驱动的压缩方法。 而从压缩方式来看，三维网格压缩技术分为单一位率压缩( 静态压缩) 和渐 进压缩【5 j 。传统的三维网格数据压缩主要是基于静态的单一位率的压缩方法，静 态压缩方法主要用来解决c p u 和显卡之间的传输瓶颈。在单一位率压缩中，网 格中的拓扑信息和几何数据作为一个整体进行编码压缩、传输和解码，解码端只 有获取整个压缩数据序列后才能进行解码操作。但是由于网络图形的不断应用， 如果使用以前的静态压缩方法，用户需要在所有的网格数据全部传输完成之后才 能看到整个网格，但在网络的带宽有限并且三维网格的数据量非常大的情况下， 用户可能要等待很长的一段时间。因此，该模式已经不被用户所接受。相反，如 第1 章绪论 果使用渐进网格压缩技术，则可以在压缩和传输的过程中，由解码端根据已经接 收的部分数据构造不同近似程度的网格。先传输一个低精度的网格使用户可以很 快的看到一个大致的轮廓，随着传输的不断推进，三维网格的显示精度也越来越 高。这样就可以解决传统静态压缩的不足，所以三维网格的渐进压缩逐渐成为三 维网格压缩领域的研究热点。 今后，三维网格压缩依然是计算机图形学和数据压缩技术领域中的一个热点 研究方向，特别是下面两个方面的进展是可期许的。一是根据不同类型的模型， 探讨其相适应的压缩方法，特别是发掘其共性的几何特征来提高压缩效率。二是 关于几何属性如纹理等的雎缩方法，因为目前关于它们的压缩方法很少，而这些 属性对于模型的成像质量有很大的影响【7j 。 1 3 课题来源及研究内容 本课题来源自国家自然科学基金项目。本课题具体旨在研究继声音、图像、 视频之后的新一种多媒体数据类型三维网格的压缩。三维网格压缩的研究是 一个较新的课题，并且三维网格数据与其它多媒体数据有很大不同。而采用几何 图像的方法，可以将三维网格映射为二维图像，使得可以利用成熟的图像编码方 法压缩三维网格数据，是一个比较前沿且适合应用的技术。 本课题主要开展几何图像和法向量图像的编解码研究。首先研究了基于 j p e g 2 0 0 0 标准的三维网格压缩方法，该方法支持渐进传输；并在此基础之上实 现了采用方向提升小波变换编码图像的方法，针对几何图像和法向量图像的特 性，提高了其图像的编码质量，从而提高了三维网格的编码质量及视觉效果。之 后，设计并实现了由几何图像预测法向量图像，并仅传输法向量残差图像的编解 码框架，该框架利用了几何图像和法向量图像的相关性，研究了在三维网格压缩 中很少被研究的法向量编码问题，并在较低码率下有较好结果。最后，研究了对 于几何图像比较重要的边缘区域的编码方法。 1 4 本文结构 本文主要对基于几何图像的三维网格编码进行了研究，具体内容安排如下： 1 第1 章，绪论。主要介绍课题的研究背景及意义，并简要叙述了三维网格压 缩技术的研究概况，最后阐述本文的研究目标、研究内容和论文结构安排。 2 第2 章，三维网格压缩。对三维网格压缩进行全面详细的介绍，包括三维网 格压缩的数据表示、压缩方法的发展过程、研究现状，以及本文重点涉及的 几何图像的生成算法和图像编解码器的选择。 3 第3 章，基于几何图像的渐进式三维网格编码。介绍了基于j p e g 2 0 0 0 标准 北京r t 业大学工学硕士学位论文 的三维网格渐进压缩方法的框架，并且针对几何图像和法向量图像的特点， 采用了方向提升小波变换的编码方法，从图像编码的角度来提高几何图像和 法向量图像的编码质量，进一步提升三维网格的编码质量。 4 第4 章，基于几何图像的真实感三维网格编码。提出并详细介绍了一种结合 几何图像和法向量图像特点和二者的相关性来提高压缩效率的，由几何图像 预测法向量图像，并仅传输法向量残差图像的编解码框架，其实现了现有三 维网格编码方法很少关注的法向量编码方法，并且改善了三维网格的真实感 渲染效果。 5 第5 章，几何图像边缘区域的编码及重建。几何图像边缘的编解码误差将对 整个三维网格的重构结果产生不利影响。本章分别介绍并实现了两种解决方 案，感兴趣区域的方法比较适合于渐进三维网格传输；而计算边缘对应关系 的方法适合于完全解码后的重构过程。 6 结论。总结本论文研究工作并展望未来工作。 第2 章三维网格压缩 2 1 引言 第2 章三维网格压缩 本章对三维网格压缩技术进行全面详细的介绍，首先介绍三维网格压缩的数 据表示，之后详细介绍三维网格压缩方法的发展过程、研究现状，最后介绍本文 重点涉及的几何图像的生成算法、编码方法。 2 2 三维网格的数据表示 目前，采用的多边形网格主要是三角形网格和四边形网格。其中三角形网 格是目前最常用的三维网格模型表示方式，得到了很多图形库( 如o p e n g l 【引， d i r e c t 3 d 【9 j ) 的支持，大量的图形处理芯片也是针对三角形网格设计的。由于可 以将每一个四边形或多边形剖分成几个三角形，从而将四边形网格或者其它多边 形网格转化为三角形网格，因此本文将主要集中于研究三角形网格的压缩编码。 一个多边形网格所表达的信息通常分为三个部分：几何信息、拓扑信息、属 性信息。几何信息用于描述顶点的位置坐标；拓扑信息又称为连接信息，用于描 述网格中顶点之间的相互连接关系；属性信息包括附着在网格上的其他信息，包 括法向、颜色及纹理坐标等【5 j 。 上述描述方法广泛应用于各种网格文件格式中，如常用的p l y ，o 巧，w r l ， 3 d s ，o 行等格式。 2 3 三维网格的压缩方法 从压缩方式来看，三维网格压缩技术分为单一位率压缩( 静态压缩) 和渐进 压缩。在单一位率压缩中，网格中的拓扑信息和几何数据作为一个整体进行编码 压缩、传输和解码，解码端只有获取整个压缩数据序列后才能进行解码操作；而 渐进网格压缩技术则可以在压缩和传输的过程中，由解码端根据已经接收的部分 数据构造不同近似程度的网格。以下将从这两方面分别介绍。 2 3 1 静态网格压缩 静态压缩方法主要是用来解决c p u 和图形显卡之间的传输瓶颈。最初的压 缩方法是针对三维模型中的拓扑结构信息，之后几何信息的压缩成为研究热点。 静态压缩方法主要有以下两类。 北京工业大学_ t 学硕士学位论文 ( 1 ) 拓扑信息驱动 索引面组 表示网格图形的最简单的方法是v r m la s c i i 格式【l o 】采用的索引面组，它 用一个坐标数组存储三角网格中所有顶点的坐标，用个面数组列出每个三角形 面和它的三个顶点的对应关系，但该方法没有采用任何的压缩技术，是一种原始 的三角形存储结构。 三角形带 d e e 曲g 【l l 】将一个三维网格划分为长三角形带，然后对这些三角形带进行编 码压缩。与索引面组方法相比，三角形带方法提供了一个更为紧凑简洁的表示方 法，当三角形带很长时，使用该方法最为有效。 生成树 t a u b i n 和r o s s i g n a c 【1 2 】提出了著名的拓扑手术方法( t o p o l o g i c a ls u r g e r y ) ，来 对三角网格进行编码，该方法需要使用两棵生成树( s p a n j l i n gt r e e ) ，即顶点生成 树( v e r t e xs p a n m n g1 r e e ，v s t ) 和三角形生成树( t r i a l l g l es p a n i l i n gt r e e ) 。首先为 三角形网格构造一棵v s t ，然后沿v s t 的边剪裁网格，裁剪结果是一个简单多 边形( s i m p l ep o l y g o n ) 和一棵t s t ；之后，对两个生成树进行游程编码( r u nl e n g m e n c o d i n g ) ，对于每个游程，编码器记录其长度和叶子位；在v s t 和t s t 中，编 码代价与游程的个数成正比，即依赖于v s t 的构造方式【5 】。该算法基于层次分 解技术建立v s t ，以获取每个游程长度的最大化和游程个数的最小化，但是由 于在解码状态执行全局随机顶点访问，因此需要的内存缓冲较大。 层次分解 b a j 匈等人【1 3 】介绍了一种基于顶点层次结构的拓扑信息编码方法，该方法将 一个三角形网格分解为几个同轴顶点层，然后在相邻的一对顶点层间，构造三角 层，网格的连接信息就由所有顶点层的个数、每个顶点层的轮廓和每个三角层中 三角形的外形表示。该算法没有将顶点层与v s t 结合在一起，但因为解码时该 算法只访问一小部分顶点，故其解码器不需要较大的内存缓冲区，而且该算法适 用于任意种类的网格拓扑结构。 价驱动 t o 眦a 和g o t s m a i l 【1 4 】以价驱动方法f v 甜e n c e d r i v e n ) 进行三角网格压缩，即 t g 方法。价驱动方法利用顶点的价对网格的的拓扑信息进行编码，其基本思想 是边界扩张，即从一个种子三角形开始，以该三角形的三条边形成初始的边界线， 边界线将整个网格分为两部分，也即已处理完毕的内部和等待处理的外部，这样， 边界线逐渐地向外扩张，直到整个网格被处理完毕。编码的结果为顶点价的输出 流，原始的拓扑信息即可由此重构。该算法的编码效果优异，缺陷是只适用于定 向和流形网格。 三角形遍历 第2 章三维网格压缩 三角形遍历( t r i a i l g l ec o n q u e s d 方法与价驱动方法类似，起始于初始三角形的 边界线，将整个网格分为遍历部分和未遍历部分，并在遍历部分一个个地插入三 角形。与价驱动不同是：三角遍历方法的输出为新三角形的构造过程，而价驱动 方法的输出是新顶点的价。其中最著名的是g 姗曲o l d 和s 衄b e r 提出的c u t - b o r d e r m a c l l i n e 算法【i 引，该算法编解码的速度都非常快，并且能够对定向和非定向的流 形网格进行编码。 ( 2 ) 几何信息驱动 所有的单一位率网格压缩方案在编码拓扑信息数据时，均为无损编码，但几 何数据则一般以有损方式进行编码。为了使用相邻顶点位置间的相关性，一般采 用下面三个过程进行编码压缩：顶点坐标量化，顶点位置预测，预测误差的熵编 码。其中，最重要的是预测技术的准确性，预测越准确，熵越小，编码效率越高。 主要的几何预测方案有d e l t a 预测【1 6 1 ，线性预测【1 7 】，平行四边形预测【1 8 l ，二级预 测i l3 】等，所有这些预测方案通过选择系数都可以看作是特殊的线性预测。 2 3 2 渐进网格压缩 在网络中传输复杂的三维网格，在带宽有限的条件下，对三维网格进行渐进 压缩非常必要。三维网格渐进压缩技术首先传输和渲染一个粗糙网格，然后继续 传输数据，以提高三维网格的质量，直到三维网格完全传输完毕或传输任务被用 户取消。渐进压缩允许传输和渲染三维网格的不同的细节层次。一般情况下，由 于渐进编码压缩不能自由地使用网格数据间的相关性，所以它的编码效率要低于 单一位率压缩算法。 ( 1 ) 拓扑信息驱动 渐进网格 h o p p e 【1 9 j 提出一种连续多分辨率表示- 渐进网格( p r o g r e s s i v em e s h ，p m ) 。 一个几何模型的渐进网格表示由一个基础网格和一系列顶点分裂操作构成。采用 边收缩( e d g ec o l l a p s e ) 的简化方法对任意的三角形网格构造其渐进网格表示，而 且可以使最后的基础网格很小。虽然其压缩效率不如单一位率几何压缩算法，但 渐进网格是一个多分辨率表示，所以非常适合于渐进传榭5 1 。 着色编码 c o h e n o r 等人【2 0 】基于顶点移除技术提出了针对渐进网格压缩的片着色算 法( p a t c hc o l o 血蓟，该算法首先对输入网格的一组顶点通过反复顶点移除 ( d e c i m a t i n 曲进行简化，每次移除一个顶点和它邻接的边，并会产生一个空洞， 需要对其重新三角化，填充该空洞的新的一批三角形称为碎片( p a t c h ) ；通过逆转 简化过程，就获得了一个分级渐进重构过程。但是，其中的重新三角化是一个费 时的操作【5 j 。 北京工业大学丁学硕七学位论文 价驱动遍历 a l l i e z 和d e s b r u i l 【2 1 】针对三维流形网格提出了一个渐进网格编码器，观察得 知，网格连接信息的熵平均信息量依赖于顶点价的分布，将价驱动遍历和移除遍 历成对应用，来获取多分辨率网格，在此过程中，将顶点的价作为输出结果，并 对其进行熵编码。移除遍历( d e c i m a t i n gc o n q u e s t ) 是基于顶点移除的一种网格简 化过程，它只移除价小于或等于6 的顶点，以保持价的统计分布集中于6 的附近， 在移除遍历中，从一片到另一片的遍历一个三维网格，执行的是片的宽度优先遍 历。 嵌入编码 l i 和k u o 【2 2 j 介绍了嵌入编码( e m b e d d e dc o d i n g ) 的概念，以在交织方式 ( i n t e n o v e nm a i u l e r ) 中编码连接信息和几何数据。几何信息和拓扑信息都被渐进 编码，这样，当接收端收到编码数据流，并解码后，不仅在模型中加入新的顶点， 而且每个旧顶点位置的精度也渐进地增加了。该方案适用于任意拓扑结构的三角 网格，并在网格简化中保持了拓扑结构不变性。 层次分解 b a i a i 等人【2 3 j 基于层次分解技术将他们的单一位率网格编码扩展到渐进网格 编码，并适用于任意的网格，算法将输入网格分解为顶点和三角形的层，然后将 网格通过三步进行简化：层内简化，层间简化和普通三角收缩，前两步保持了网 格的拓扑结构，但第三步可能会改变网格的拓扑连接。 ( 2 ) 几何信息驱动 k d 骶e 分解 2 0 0 2 年g a n d o i n 和d e v i l l e r s 【2 4 】打破了传统的拓扑信息驱动几何信息的编码， 提出了一种几何驱动拓扑的新的编码方式，该算法基于子分过程【2 5 】的k d t r e e 分 解，分为两步：只考虑几何数据递进编码；在两个连续的l o d 之间对拓扑结构 变化进行编码。该算法适用任意拓扑结构，特别适合地形数据和密集采样数据， 并能很容易扩展到四面体网格【5 1 。 八叉树分解 2 0 0 5 年p e n g 和k u o 提出的一种基于八叉树( o c 们e ) 的递进无损编码1 2 6 j ，该 算法采用自顶向下的方式编码变化信息，其中几何编码没有在每个c e u 里面编码 顶点的个数，而是编码顶点在c e h 里的存在性，这样编码更加简洁，而拓扑编码 除对非空子树编码外，还对非空子树与父节点的邻节点编码。这种编码方式比 k d t r e e 方法有效且很容易扩展到多边形网格。 频谱编码 在数字图像处理领域，通常通过d f t 或d c t 等变换方法将二维图像转换到 频率域，由于能量通常集中在低频，可以将高频信号忽略而只编码低频信号，这 样能达到很大的压缩比口7 1 ，这种压缩格式非常适合在网络上对几何进行渐进式传 第2 章三维网格压缩 输：即先传几何的低频系数，再传送高频系数。t a u b i n 在1 9 9 5 年s i g 伊印h 会议 上首先提出了三维网格的频谱理论【2 8 】。基于这一理论，k a r n