（计算机应用技术专业论文）率失真优化的渐进几何压缩.pdf

摘要 摘要 近年来，随着计算机图形学中三维建模和三维扫描技术的进步，数字化三维图 形数据大量涌现，并己广泛地应用到各行各业中。三维模型的数据量一般都比较庞 大，必须要进行有效地压缩，以减少它们对存储空间和网络带宽的需求。三维模型 数据压缩技术的理想目标是不仅要具有高教的压缩性能还要能够提供灵活的位流 结构以适应网络传输的需要。 本文在分析以往压缩算法的基础上，针对网格细节信息分布的局部性以及网上 传输三维数据的特点，提出了种率失真优化的渐进几何压缩算法。该算法首先 对半规则网格进行分块，而后对各块信息独立编码以便分析各块信息的率- 失真特 性；最后以率失真特性为标准区别对待各块，保证细节丰富的信息尽量位于渐进 位流的前端，从而使解码端尽早得到这些信息，进而使重构网格的质量尽快得到改 善。本文的具体工作如下： 1 大部分网格细节信息的分布是不均匀的，而且在实际应用中用户对各块的关注 程度也不同。在渐进压缩方法中，细节信息的传输次序将直接影响低位率下重 构网格的质量。本文采用三维网格分块独立编码方法，根据各块编码后位流的 率一失真特性，以一定位率下使重构网格失真最小为准则，将各块独立编码后 位流组装成最终的码流，这种位流具有较强的灵活性，能够根据备块位流的特 点确定传输顺序。 2 传统的度量三维网格失真的方法是采用豪斯道夫距离( h a u s d o f f d i s t a l l c e ) ，但 是这种方法的计算量很大。为了减少率一失真优化过程的计算量，本文根据渐 进几何压缩方法的特点提出一种新的几何失真的计算方法。该方法从编码过程 中可能引入失真的各个环节入手进行分析，找到了一个简单快捷的计算各截断 后的位流段对重构网格质量贡献的方法。 3 本文提出的率失真优化的渐进几何压缩方法也为实现三维网格感兴趣区域编 码提供了新的思路。通过优先传输网格中感兴趣区域中的数据，有效地实现了 三维网格感兴趣区域编码的效果，较好地满足了用户个性化远程浏览三维模型 的需求。 关键词率一失真优化：渐进压缩；小波变换：三维网格压缩 n a b s t r a c t a b s t r a c t r e c e n 廿y ，w j t l lt l l ed e v c 】o p m e n to f m o d e l i l l ga n d3 ds c 锄j n gt 。血1 i q u ei nc o m p u 把r 聊h i c s ，m o r e 锄dm o r c3 dg r a p h i cd 砒a 盯ee m e 曙i n 岛a i l d 谢d e l yu s e di nm a n ya r e a so f s c i e n c ea n dt e c h n o l o g y is m c e3 dg m p h i cd a t au s l l a l l yp o s s e s sh u g ea m o u n to fs i z e ，t l l e y s h o u l db cc o m p r e s s e de m c i e m l yt or c d u c et l l es t o r a g c 锄d 订狮姗i s s i o nc o s t t h ei d e a l 仃i 孤g l em e s hc o m p r e s s i o nt e c l l i l o l o g yw l dn o to n l yr 髓c hh i g h e rc o m p r e s s i o nr a t i o b u t a 】s op r o v i d ea 矗e 妇b 】eb i t s t r e 锄s t 兀l c t u r et om f o r 臼髓s m i m n go n 妇1 en e “v d r k a f t e ra i l a l y z i n gt l l ec o n v e n t i o n a l c o m p r e s s i o na l g o r i t l l m s ，au n 墒e ds c h e m et o o p t h n j z ep r o g r c s s j v eg e o m e 姆c o m p r e s s j o ni sp p o s e da c c o f d i n gt 0t h en o n i i l 】j f o 册 d i s 雠b u t i 叽o ft l l ed e t a i l sa l l dt h er e q u i r e m e n to ft r a n s m 嘶n g3 dd a t ao nn e 柳o r k 1 1 1 e 卸mm o d e l i sp 甜h i e di n t 0b i o c k s ，w h i c ha r e 也饥c o d e dj n d 印e n d 吼t l y t h ee n c o d e d b i t - s 竹朗m so f b l o c l 【sa r ea s s 锄b l e di n t oac o d e s 仃e a mb a s e do nr - 【) o p t i l i l i z a d o n ，w h i c h e n s u r ct h eb l o c kw i 山f i c hd e t a “b e 衄m 锄m c d 髂s o o na sp o s s i b l e s p e c i f i c a l l y ，、em a k e t l l ef o l l o w i i l gc o n 证m u t i o n s ： 1 1 1 1 ed e t a i l so f3 dm o d e l su s u a l l yd i s t r i b u t en o n - u n i f o r n l l y i nt l l e a p p l i c a t i o n ，t h e d i f f b r e n td 郫c so f i n t e r e 啦a r ep a i dt od j 丘白锄ta r e a so f t l l e3 dm o d e l - d u m g p m g r c s s v e 忱m s m i s s i o no f3 dg e o m e 舡ym o d e l s ，t 1 1 e 仃a t l s m i s s i o no r d e ro ft h ed e t a i l s a td i 饪b r c n t 坤g i o nh 嬲g r e a te a b c t so nt h eq u a i i t yo fr c c o n s 仃u c t c dm o d e i sa tl o w b i t r a t c t h e r e f o r e ，i n 血i sp a p e r t 1 1 ei n p u tm e s hi sp a r t h i o n e di r 曲s e v e r a lb l o c k s ， w h i c ha r et h e ne n c o d e di n d e p e n d c n t l y t h eb t - s t r c 咖so f b l o c l ( sa r ea s s e m b l e di n t oa c o d e - s t r e 锄b a s e do nr _ do p t i m i z a t i o n ，w h i c he n s u r et h eb l o c k 、) l ，i t hr i c hd e t a i lb e t r a n s m i 位e da ss o o na sp o s s i b l e 1 1 l ep r o p o s e da l g o r i t mp m d u c e st l l ec o d e s t r 韵m w i mt l l en e x b l es 仇l c t i l l 嗡w l l i c hp l a c e st 士l en a s m i s s i o no r d e ra c c o r d i n gt 0 t l l e c h a r a c t e r i s t i c so f e a c hb i t 。s t r e 锄 2 。t h ec o n v 肋t i o n a ln l l el om e a s u r et 1 1 eg e 1 e h yd i s t o n j o ni sm eh a u s d o r f r d i 对如c c ， b u ti tr c q u i r e sc o m p l e xc o m p u t a t i o n i i lo r d e rt or e d u c em ec o m p u 诅t i o n a lc o m p l c x 毋 o f 廿l eo p t i m i z a t i o np m c e s s ，w ep m p o s e daw a yt oe s t i m a t e 廿l er c d u 吐i o no ft h e h i d i s t o n i o nb a s c do nt l ep r o c e s s i n go ft l l ep r o g r e s s i v eg e o m e h yc o m p r e s s i o n 触e r 锄a l y z m ge a c h3 t e p 诎l i c hb r 洫g sd i s t o n i o ni n 廿l ee n c o d 试gp r o c e s s ，强e f f i c i e n tw a y i s p r o p o s e dt oc o m p u t e m ec o n 订i b u t i o nt or e c o n s n l l c t e dm o d e l 3 t h es c h e m ep r o v i d e san e ws c h e m et 0r e a l i z er e g i q no fi n t c r e s t ( r o i ) c o d i n go f3 d m e s h e se m c i e n t l y t h eq u a l i t yo fr o ic a i lb ei m p m v e d 髂s o o n 船p o s s i b l eb y 椭l i l s m m i n gt l l ed e t a i l si nr o ip r e f b 砌m a l l y w h i c hs a t i s 黟u s e r st ob r o w s e3 dm e s h i t l d i v i d u a l l y k e yw o r d sr 砒e - d 魂o r t i o no p 恤n i z a t i o n ；p r o g r e s s i v em e s hc o 【叩他s s i o n ；、v a v e l e t a n s f b r m ；3 dm e s h c o m p r 骼s i o n i v 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构的学位 或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文 中作了瞻确的说明并表示了谢意。 签名：碰垒垡日期：显型：f 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权保 留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内 容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：缮垒i 璺导师签名：3 盈妊醢，日期：甚碰 第l 章绪论 1 1 引言 第1 章绪论 从上世纪7 0 年代以来，多媒体技术的发展已经历了声音( 1 d ) 、图像( 2 d ) 和视频( 3 d ) 三种数据类型。到上世纪9 0 年代后期我们又迎来了第4 种数字化 媒体一三维几何模型。( 近年来多媒体发展历程如下图i - 1 所示) 舀1 1 多媒体技术发展历程 f i g u r el - 1t h e d e v e i 叩m 蹦t c 伽幅eo f m u i t i n l e d i a t e c l 】n 0 1 0 盱 三维几何模型，从它诞生到现在，凭借以往媒体无可比拟的逼真性和交互性在 许多领域扮演着越来越重要的角色，发挥越来越重要的作用。其应用领域涵盖了科 学探索、工程设计、机械制造、模拟仿真、医药卫生、城市规划、环境保护、文物 保护、教育培训、艺术创造、以及游戏娱乐等许多方面。近年来，计算机图形学及 其相关理论和技术的发展相当快”司，三维模型的建模能力不断增强，所使用的三维 几何数据的规模和复杂程度也在不断地急剧增长。特别是随着k t c m e t 的发展与普 及，人们通过i m c m e t 来共享三维图形数据的需求越来越强。因此，当前迫切需要 提高三维数据的压缩技术，以减少存储空间需求和节约网络带宽。 自从1 9 9 5 年d e e r _ m g 发表第一篇几何压缩的论文以来，有关三维网格压缩和 传输的研究已经取得了较大的进展。根据压缩目的的不同，当前三维图形压缩的研 传输的研究己经取得了较大的进展。根据压缩目的的不同，当前三维图形压缩的研 北京工业大学工学硕士学位论文 究5 ，6 一般可分为渐进压缩( p m g r c s s i v cc o m p r e s s i o n ) 和非渐进压缩( n o n - p r o g r e s s i v e c o m p r e s s i v e ) 。非渐进压缩是指等到接收到所有的压缩数据后，才能进行解码的压 缩方法，非渐进压缩的目的是要获得较高的压缩比以减少存储空间需求和节约网络 带宽。渐进压缩则是将网格压缩成适宜于渐进传输的形式，即先传输表示模型大致 轮廓的基网格再逐渐传输一系列细节信息，随着这些细节信息逐渐到达解码端，重 构网格上面的细节信息将越来越丰富，其质量将越来越接近于原始网格。渐进压缩 方法对于处理那些细节信息丰富、采样密集的模型很有效：首先，这种方法可以减 少交互时用户的初始等待时问，在基网格传输并显示后，用户就可以开始与之交互； 其次，系统可以根据接收端的实际条件，在压缩位流的任意一点停止接收位流，并 能从已经接收的位流中重构出某一个细节层次( 1 e v e lo fd e t a i l ) 的几何模型，从而 有效地节约了网络带宽和存储空间。重构模型的质量将由已经得到的位流的长度决 定，解码端接收到的位流长度越长，重构出的网格质量就越高，其失真就越小，这 种特性称为算法的率一失真性能。在对不同的渐进压缩方法评价时，不仅要考虑压缩 率，而且还要衡量它们的率失真性能。 在三维网格中，细节信息分布一般都是不均匀的，有些区域的细节信息比较丰 富，这说明这些细节信息对重构网格质量的贡献比较大；而有些区域的细节信息则 相对比较平缓，这部分信息对重构网格质量的贡献相对比较少。因此在渐进压缩中， 细节信息的传输顺序将极大地影响重构网格的质量。若能够根据细节信息的率失真 特性优化调整其传输顺序，将能有效地提高低位率下重构网格的质量。基于率失真 优化的压缩技术在图像、音频以及视频压缩中已经比较成熟，然而在三维图形压缩 中相应的研究则较少。本文将主要研究率失真优化的渐进几何压缩技术。 1 2 课题研究现状 1 2 1 三维网格压缩和传输的研究现状 三维图形数据的压缩和传输的研究是涉及计算机图形学、多媒体压缩技术和 计算机网络等学科的交叉性课题，近年来三维模型的压缩和传输的研究已经取得 2 第l 苹绪论 了很大的进展。 三维模型压缩方法的研究主要集中在多边形网格模型，这是因为这样会使该 表面非常易于构造、存储和绘制。在这些用于表示的多边形中三角形最为常用， 这主要因为三角形的面总是平的( 而其他多边形用于该表面之前总要检测其平坦 性) 。此外，由于许多图形a p i 和硬件都是针对三角形进行操作的，所以图形系统 一般都是将多边形和曲面转化为一系列的三角形，而后再进行渲染。使用三角网 格可以大大减少转化的时间。因此，一般都把三角网格作为三维模型表示的标准， 因此本课题将主要集中于研究三角网格压缩的相关问题。 网格的基本信息包括连接信息和属性信息。连接信息描述顶点间的连接关系， 而属性信息则主要描述顶点的各类属性，其中主要是顶点的几何信息，还有法线、 颜色、纹理坐标等其他属性信息。其他属性也可以用与顶点坐标相似的方式进行 压缩。 下面分别介绍非渐进压缩方法( n o n - p r o g m s s i v ec o m p 糟s s i o n ) 和渐进压缩方法 ( p r o g 佗s s i v ec o m p r c s s i v e ) 的研究现状： 非渐进压缩方法 非渐进压缩方法是指当解码端接收到全部的压缩数据后才能开始解码的 压缩方法。其主要目的是为了要获得较高的压缩比，以减少存储空间和节约 网络带宽。典型的非渐进压缩方法主要有：t s ( t 0 p o l o g i c a ls u r g e r y ，拓扑手 术) 【9 】、e d g e b r e a 妇r 1 1 q 1 ”、1 g 【1 2 1 等。这类方法适合于数据量相对比较小的三 维网格，其目的是获得比较高的压缩比。由于非渐进压缩方法处理的几何对 象是那些只含有一种层次细节的多边形网格，所以通常也称为单一分辨率压 缩方法( s i l l g l c r e s o l u t i o nc o m p r e s s i o n ) 。这些方法一般都是以某种方法逐个遍 历网格中的元素( 如面、边或顶点) 来记录网格中各个元素的连接关系，而 后沿遍历顺序对各个顶点坐标进行预测，最后再对预测误差进行熵编码。 渐进压缩方法 渐进压缩是指当用户接收完基网格后就可以开始解码的压缩方法。首先 北京工业大学工学硕士学位论文 用户将得到一个网格的粗糙模型，而后随着细节信息的到达，重构网格的质 量将逐步逼近原始网格。由于在传输过程中，只要用户得到基网格就可以开 始交互，因而这种方法特别适合于处理数据量大、连接关系复杂的三维网格。 渐进压缩方法的目的是为了减少用户的等待时间，并适应不同接受能力终端 的需要。由于渐进压缩方法针对的是具有多个层次细节的网格，因此通常也 将其称为多分辨率压缩( m u n i s 0 1 u t i o nc 响p s s i o n ) 方法。 目前的网格渐进压缩方法主要可以分为基于网格简化和基于小波变换两 大类。 其中典型的基于网格简化的渐进压缩方法有：聊的渐进网格 ( p 删弘s s i v em e s h e s ，p m ) 【1 3 l 、j i 锄l c l ml i 【1 4 1 、t a u b i l l 的p f s ( p r o g m s s i v ef o r e s t s p l i t ) 【1 ”、b a j 面等【1 6 】、删a l d l a 和r 0 s s i g n a c 的c p m ( c 锄p m s s c dp m 辨s s i v e m e s h e s ) 【m 、c 0 h o r n 扪、a l l i c 2 和d e s b 眦 1 9 】。这些方法的基本思想是先将 原始网格逐层简化，得到基网格和一系列简化操作( 其逆过程为细化操作) ， 然后用非渐进压缩方法对基网格进行压缩，并将其放入到位流前部；而对简 化操作中的连接信息和几何信息则将分别进行压缩，并将其依次放入到传输 位流的后面，这样得到的位流具有渐进性。 基于小波变换的渐进压缩是另外一类渐进压缩方法，其代表方法有：p g c ( p r o g s s i v eg e o m e 时c 叫l p m s s i o n ) 瑚】、法向网格( n o n 舱lm e s h ) 口1 肄。 这些方法的基本思想是先对原始网格进行重新网格化( r c 珈【c s h i n g ) 处理，得 到与原始网格几何形状相同的半规则网格，从而去掉了原始网格中大部分的 连接信息，然后在这个半规则网格上进行小波变换，得到一个基网格和一系 列表示细节信息的小波系数。其中基网格将采用非渐进压缩方法进行压缩， 而对小波系数将参照图像压缩方法中的一些压缩小波系数的方法进行压缩。 基于小波变换的渐进压缩方法是目前压缩效率最高的渐进压缩方法之一。由 于这种方法在重新网格化过程中去除了网格的连接信息，只需要处理几何信 息即可，因此这种方法也称为渐进几何压缩方法。本文将在第二章对渐进几 第l 苹绪论 何压缩方法的步骤进行详细介绍。 除了要提高三维网格压缩算法的压缩效率外，还应该使网格的压缩数据适应网 络应用环境对网格压缩提出的要求。比如，考虑使压缩数据具有可扩展性，以适应 网络的带宽异构性、时变性和各种终端图形处理能力的差异；使网格压缩能够支持 交互浏览的随机访问特性；按照用户对三维网格的个性化定制实现三维网格感兴趣 区域编码；对于带有纹理的三维网格，实现网格和纹理的同步传输等。作者所在的 实验室在提高三维网格压缩性能方面做了大量相关的工作2 6 】。 1 2 2 率一失真理论基本概念 早在1 9 4 8 年，几乎还没有任何有损压缩方案提出的时候，香农就开创性地提 出了具有保真性的信源编码理论( m em ”r yo fs o u r c ec o d m gw n han d c l 姆 c m e r i o n ) ，后来该理论也被称为率失真优化理论h ”。现在率失真优化理论已经成 为评价有损压缩性能的标准，并广泛地应用于音频、图像、以及视频等各种压缩技 术中。 无损压缩的目标是要达到尽可能高的压缩率。然而在许多实际应用中，人们并 不要求完全无失真地得到原来的数据；而无失真的传输要花费的代价十分巨大，有 时由于传输条件的限制这种传输根本不可能实现。为了提高通信的效率，可以对有 待传输或存储的大量数据进行有损压缩。率失真理论研究的正是在保证一定压缩率 的情况下，尽可能地减少压缩过程中产生的失真；或者理解为保证有一定量失真的 情况下，使压缩率尽可能地提高。 对于给定信源 。；) _ 。盖，。乏，：。志， ，信道输出的信号为 r = “乃咒) ，信源发送信号而，而用户接收到的信号为乃r 引起的失真用 d “，一) ( f = 1 ，2 ，m，= l z ，来表示，简记为如n 将所有的嘞列出来，可以 得到失真的测度矩阵： 【明= 匾。碣： 如如 叱如 丸 屯 ： 屯 寻找信道，设该信道转移概率的矩阵为p = 【p o ，i 葺) 】，使其满足： 万= 口( 薯) p ( 乃i 再) 由d ( 1 - 2 ) ， j 其中，d 是预先给定的失真限度。式( 1 - 2 ) 被称为保真度准则。 在信源固定的情况下，平均互信息量，( x ；r ) 是信道转移概率p o ，i 石) 的u 形凸 函数。这就意味着可以关于p ( ) ，i 曲对平均互信息量，( 盖；d 求出极小值，定义这个 极小值满足率失真函数r ( d ) ，即： r ( d ) 皇嬲3 j ( x ；】，) ：d d ) ( 1 _ 3 ) 率失真函数r d ) 是以失真d 为自变量来描述传输的信息量，它是信息论中一 个重要的物理量。引入r c d ) 是为了解决在允许一定失真度d 前提下，对信源进行 有损压缩到底能压缩到什么程度的问题，它给出了一定保真度条件下信源信息可以 被压缩的最低程度。 根据信源的传输量与失真的程度之间的关系可知，率- 失真函数r c d ) 在定义域 内r ( d ) 有上限和下限，并且该函数具有连续性、单调递减性和下凸性。由率- 失真 函数的上述性质可以绘出率失真函数丑( d ) 的曲线( 如下图1 - 2 所示) ： 瓣l 豢 魂溉 “ 鬈一黪撇 |，蒸 糕 图l - 2 r 归曲线 f i g u r e l 21 1 r ( d ) _ dc u r v e 由上述分析可见，当规定了允许的失真d ，又找到了适当的失真函数，就可以 6 第l 章绪论 找到该失真条件下的最小信息量r ( d ) ，这个最小的信息量是一个极限值。因此该方 法可以用于满足一定保真准则的前提下发现不同压缩方法的压缩潜力。 同理，也可以用一定量的传输数据量r 为自变量来描述保真程度，即可以用率 - 失真函数d ( r ) 来表示信源的传输量与失真的程度之间的关系。此时，率失真函数 d 在定义域内也有上限和下限，且该函数在定义域内具有连续性、单调递减性和 下凸性。因此，该方法可用于满足一定信息量条件下，优化配置最终传输码流使解 码端得到模型的保真程度最好。 1 3 本文研究内容及方法 本文注意到，大部分网格细节信息的分布是不均匀的，即有些区域的细节信息 起伏比较丰富而有些区域细节信息起伏则相对比较少，其中细节起伏丰富的区域对 重构网格的质量影响更大，因此可以根据局部细节信息分布的特点来提高低位率下 重构网格的质量。另一方面，在实际应用中用户可能只对局部区域感兴趣，比如希 望这些区域的失真比其他区域的更小；在码流渐进传输给客户时，希望这些区域的 质量能以最快的速度被改善。因此可以通过优化码流结构来改善低位率下重构网格 的质量。 本文根据三维网格细节信息分布的不均匀性，提出一种率失真优化的渐进几何 压缩方法。本文首先对网格分块并对每一块独立编码，以便有效地分析局部信息； 编码后得到的各段位流中的每一位信息均能对率失真产生贡献，本文根据渐进几何 压缩方法的特点，在位流上选取可行截断点，并在各个可行截断点处将位流截断为 若干小段：而后依照率- 失真优化原则，将各段位流组合为最终码流。在解码端接收 到基网格信息后，将会优先得到对率失真性能改变较大的细节信息，此时，无论在 哪一点截断都能得到一个与原始网格更接近的重构网格。 此外，本文将率失真优化渐进几何压缩方法的思想用于三维网格感兴趣区域编 码中，提出通过优先传输感兴趣区域相关数据来实现三维感兴趣区域编码。 北京工业大学工学硕士学位论文 1 4 论文组织 本文主要研究率失真优化的渐进几何压缩。通过分析渐进几何压缩方法的特 点，我们将提出一种高效便捷的计算几何失真变化量的方法，该方法将能大大减轻 率失真优化过程的计算量。此外，我们提出的率失真优化渐进几何压缩方法也为 实现三维网格感兴趣区域编码提供了新的思路。最后，作者讨论了进一步研究的几 个方向。本文组织如下： 第一章绪论 主要对国内外关于三维网格压缩的研究现状进行了综述，介绍了信息论中率- 失真理论的一些基本概念，并大致介绍了本文的研究内容和基本的研究方法。 第二章渐进几何压缩 介绍了目前压缩性能较好的渐进几何压缩方法的基本思想，介绍了如何对三维 网格进行小波变换，如何组织小波系数等，并指出了渐进几何压缩方法仍然存在的 一些问题。 第三章率失真优化的渐进几何压缩 根据第二章分析的渐进几何压缩存在的问题，提出了率一失真优化的渐进几何压 缩方法，并且给出了相关的实验验证了算法的有效性。实验结果显示，该方法取得 了比著名的p g c 方法更好的率失真性能。 第四章三维网格几何失真模型 通过逐一分析渐进几何压缩方法中的各步骤，提出一种适合率- 失真优化过程需 要的计算几何失真变化量的方法，这种方法减轻了率- 失真优化过程的计算量。 第五章基于率失真优化的三维网格感兴趣区域编码 将第三章提出的率失真优化的渐进几何压缩算法的思想应用于三维感兴趣区 域的编码中，提出了一种新的三维网格感兴趣区域编码方法。 最后结论部分对本文的主要工作和创新点进行了总结，并介绍了下一步将要从 事的一些工作。 第2 章渐进几何压缩 2 1 引言 第2 章渐进几何压缩 在对音频、图像以及视频信号的处理过程中，利用小波变换技术进行数据压缩 的应用已经相当成熟和普遍【2 7 珈l ，然而小波变换在三维网格的压缩和处理中的应用 尚处于初级阶段。对图像而言，平面上的像素之间的连接关系是固定的；对于三维 网格而言，几何曲面可能会具有任意的拓扑结构，顶点的连接关系一般是不规财的。 三维网格顶点连接关系的不规则性，使得在网格处理中利用传统的小波变换变得很 困难。例如，在图像压缩中普遍使用的二维小波通常是从单变量小波的张量内积椅 造出来的，由于张量内积小波构造方法要求函数是定义二维平面或二维平面的周期 表示( 如圆柱面或圆环面) 上，因此这种方法不适用于一般的流形表面。而其他的 方法构造出来的小波也不适用于定义在一般模型表面的函数。 l o 吼s b e r y 提出的基于多分辨率的思想首次将小波分析推广到任意拓扑表面的 研究中，开创了在半正规网格上的小波分析p 1 ，3 2 1 。由于小波变换的强去相关能力， 使得基于小波变换的渐进压缩方法提供了比其他方法更高的压缩率。在本章中我们 将介绍这类基于小波变换的渐进几何压缩方法。 首先，我们先对下文要出现的一些相关的概念和术语进行定义：而后，我们将 介绍基于小波变换的多分辨率分析方法的思路；接下来我们将逐一分析基于小波变 换的渐进几何压缩方法的各个步骤，最后我们将指出目前渐进几何压缩方法中存在 的问题。 顶点的度：网格中所有和该顶点相连接的顶点的个数。若一个顶点的度为6 ， 则称该顶点为规则顶点( r c g l l l a r v e r t 既) ，否则称之为额外顶点( e x h r d i l l a l y v e m x ) 。 根据顶点的度可以将网格分为三类： 规则网格( r e g l l l a rm e s h ) ：网格中的每个顶点的度都是6 ，即网格中不含额外 顶点： 不规则网格( i r r e g l l l 盯m e s h ) ；网格中顶点的度可以为任意数。 半规则网格( s e m i - r e g u l a r m e s l l ) ：从一个粗糙的不规则网格开始，通过不断地 一分四划分( q u a d r i s e c t ) ( 如图2 1 所示) 获得的网格，这种网格具有细分连接性 ( s u b d i v i s i o nc o i l l l e c t i v 时) 。在半规则网格中，除了粗糙网格中的顶点有额外顶点外， 其他所有顶点都是规则顶点。 图2 1 网格一分四划分效果( a ) 初始三角形( b ) 一次四等分( c ) 两次四等分 f i g u m2 - 11 1 l co 勘一f 0 ws u b d i v i s i 吼( a ) 也e 州g i n a l 啊锄西e n ”f i r s to n e - l o - f 0 如b d i v i s i ( c ) 也es e c o n d 衄e 她f 如翻n x u v i s i o 2 2 基于小波变换的多分辨率分析 基于小波变换的渐进压缩方法实质上来源于多分辨率分析的思想 ( m u m r e s o l 嘣o na n a l y s i s ，m r a ) 。按照这种方法，输入的网格将先被分解为基网格 和一系列小波系数，基网格的分辨率最低，它是原始网格最简单的近似，而网格细 节则可由一系列的小波系数重构出来。 多分辨率分析的基本思想是把一个复杂的函数分解为一个简单的低分辨率部 分加上一系列细节信息。分解过程如下图2 _ 2 所示： 图2 _ 2i 棚d 蛔细分小波 f 姆m 2 _ 2l o s b e r ys u b d i v i s i 伽、v e l e t 如图2 _ 2 所示，原始网格经过小波分解后，得到了一个基网格( c ) 和一系列的 l o 第2 革渐进儿侗压缩 小波系数，其中基网格构成了原始网格的低频近似部分，而小波系数则构成了原始 网格不同分辨率级的高频细节部分，表达了相邻层次问的差别。在分解过程中，( b ) 中的顶点都是由( a ) 中的顶点加权平均计算出来的。这种加权平均的本质体现了一 个低通的滤波器a 。细节部分对应于图中定点的加权差值，即小波系数。这些加权 求差过程的本质是一个高通滤波器b 。这个分析过程可以继续下去，直到表示为 最粗层次的网格( 基网格) 为止。最后原始网格可以表示为一个基网格和一系列的 小波系数。合成是分解的逆过程，从最粗层次开始，通过为每条边的中点引入新的 顶点实现对三角形一分四的划分，而后利用小波系数对新引入的顶点坐标进行修 正。 利用小波变换最大的好处是可以把一个复杂的数据集用一系列幅值很小的小 波系数来准确表示，这在很大程度上去除了原始数据之间的相关性。在三维网格中， 相邻顶点之间有很大的相关性，网格小波变换实质是把复杂的网格数据用一个基网 格和一系列的小波系数来表示，与原始网格的复杂数据相比，小波系数的幅值要小 得多，利用网格小波变换可以有效地提高压缩效率。 k h o d a k o v s 姆等人提出的p g c ( p m g m s s i v eg e o m e 时c o m p r e s s i o n ) 算法例是 基于小波变换的三维网格的渐进压缩方法的典型代表。这类方法的实现过程大致相 似，一般包括重新网格化、小波变换、零树编码等几个步骤，以下将依次介绍这三 个步骤。 2 3 重新网格化 通常原始网格都是不规则网格，这种爵格不便于处理，因此需要将其转换成半 规则网格或规则网格，这个过程称为重新网格化( r e - m e s h i i l g k 重新网格化后的新 网格由于具有细分连接性，使得小波分析、信号处理处理方法可以推广应用到网格 数据中。 重新网格化的基本过程如下：首先对原始网格进行简化，得到一个最粗糙的基 网格( b 嬲em e s h ) ；在简化的同时，对原始网格进行参数化o a m m e t e r i z a t i o n ) ，建立从 北京工业大学工学硕士学位论文 原始网格到基网格的映射；对基网格进行一分四的划分，并将每个新引入的顶点反 映射到原始网格表面，得到重采样后的点。由于新引入顶点的度都是6 ，所以获得 的网格具有细分连接性的，便于在其上进行小波变换以及其他处理方式。已有的重 新网格化的方法有很多，具有代表性的工作有m a p s o 讧u m - r e s o l u t i o na d a p t i v e 咖r i z a t i o no f s l f a c e s ，m a p s ) 方法【3 3 1 、法向网格( n o 咖a lm e s h e s ) 【3 4 1 等。下 面简要介绍一下这两种重新网格化的方法。 姒p s 方法 m a p s 方法的基本思想是将原始网格参数化到一个基域上，然后在基域上进行 规则采样，并用已经得到的参数化方法求出这些参数域上的采样点在原始网格表面 上的对应点。由于通常网格只能局部参数化到平面上，因此各种网格参数化方法都 要先将网格表面划分为片，然后将每一片单独参数化到一个平面上。m a p s 方法将 网格简化得到的基网格作为基域，将网格表面的一定区域参数化到一个基三角形 上。在简化过程中，每删除一个顶点就要对留下的洞进行三角划分，同时，应采用 共形映射将该被删除顶点参数化到简化网格上。随着简化过程的进行，每个被删除 顶点的参数化不断被复合起来，最终。每个被删除的原始网格上的顶点都被映射到 某个三角形上，从而建立起原始网格的参数化。在重采样阶段，对每个基三角形做 多级的一分四划分，在利用原始网格与基网格之间的映射关系。将由一分四划分引 入的新顶点映射到原始网格上，从而得到重新网格化后新顶点的位置。此外，为了 使重新网格化后得到的网格与原始网格的几何误差控制在一定的范围内，m a p s 采 用了自适应的一分四划分，即在细节信息丰富的区域，划分的级数比较多，而在平 坦区域划分的级数则比较少。 法向网格( n o r 腿im s h ) 在重新网格化设计时，该方法尽量使每个小波系数沿法向方向分布，这样每个 小波系数在局部坐标系中基本上只用一个法向分量表示就可以了，而两个切向分量 基本为零。因此，原始网格就可以用一个最粗糙的基网格和一系列的法向分量来表 示，这样就把原来的三维表示方法简化为一维表示了。由于网格的数据量一般都很 第2 章渐进几何压缩 大，而n o 咖a lm e s h e s 把复杂的三维计算转换成简单的一维计算，大大减少了数据 量。除了将三维坐标的表示形式变为一维表示外，法向网格的其他做法几乎与姒p s 方法完全一致。 2 4 三维网格的小波变换 经过重新网格化后可以在半规则网格上进行小波变换。小波变换可以将细节信 息表示为一系列小波系数，小波系数表示了两个相邻层次之间的差异。由于在变换 过程中需要分片处理；因此相邻顶点之间存在很大的相关性。然而经过小波变换后， 各顶点对应小波系数的幅值都很小，基本都分布在零附近。因此利用小波变换可以 有效地去除顶点之间的相关性。 常用的三维网格上的小波变换主要有b 1 1 t t e r f l y 小波d 5 】和l 0 0 p 小波。下面将 对它们分别进行简单的介绍： l o o 口小波： k h o d a k o v s 虹在基于l o 叩细分方案 3 日提出了l 0 0 p 小波【2 0 】。l o o p 细分方案是 一种近似的( a p p r o x i l a t i l l g ) 方案，即原有的顶点在细分后其坐标也会发生变化，从 而使细分后的网格表面更光滑。也正是由于这个原因，使用l o o p 小波分解后得到 的网格尽管压缩效率和用b u _ t t e r f l y 小波差不多，但是视觉质量会更好一些。l o o p 细分的重构公式如下： = 【p 啦 ( 2 - 1 ) 式( 2 - 1 ) 中，为第f 层的顶点坐标，为f 层的小波系数。低通滤波器p 由l 0 0 p 细分确定，而高通滤波器q 则由p 根据正交镜像滤波器法( q 瑚d 阳t u r em i 啪r c o n s t r u c t i o n ，q 砌f ) 【3 7 1 来构造。 相应的小波分解过程实质是由精细网格得到较一个粗糙的网格以及一系列的 小波系数。比如在( 2 1 ) 式中，己知升l 层的顶点坐标p “，求解出第f 层的顶点坐标 ，和小波系数的过程，这一过程可以利用求解稀疏方程式的方法进行求解。 b u 钍e r n y 小波： b u 蛐小波是根据b u n e r n y 细分方案提出的。b u t t e 棚y 细分是一种基于插值 ( m t e r p o l a t n g ) 的细分方案，即原有的顶点在细分后坐标值( 即尺度系数) 将保持 不变。b u n e m y 细分模板如下图2 3 所示： 图2 - 3b u 位e r n y 细分 f i 础- 3 也e 髓c 订o f b 删锄垮b d m s i 蛆 b 删枷y 小波的分解过程很直观，即利用周围的顶点对新引入顶点进行预测，预测 误差就是新引入点的小波系数。重构过程则与上述分解过程相反。如图2 - 3 所示， 当采用b u 仕e m y 进行小波分解时，第什l 层的顶点v 处的小波系数等于顶点v 的坐 标与第f 层中8 个顶点( v l ，v 2 ，正，五，旬，屯，e 3 ，“) 坐标值的加权平均之差。 小波重构过程与上述分解过程相反。进行小波重构时，先对每个三角形进行一分四 的划分，在每条边引入一个新顶点，每个新顶点的坐标等于模板中8 个顶点的坐标 的加权值与小波系数之和。 上述，j 、波分解和重构的过程可以用式( 2 2 和( 2 - 3 ) 来描述，其中圾1 ) 为层次珀q 尺度系数( 即顶点坐标) 的集合，题o 为层次f 的小波系数的集合。 小波分解： i j i ，( f )= k w 1 七置a )艿啦= 巧“；一s 山。巧， ( 2 。2 ) l i e ( i ) 小波重构： 1 4 第2 章渐进几何压缩 i - ，e ，( f )= k ， 七置( f )巧+ i = 4 i + 墨 i 巧， ( 2 3 ) l t e j ( 1 ) 9 6 年，s c h r o d e r 和s w e l d e n s 又提出了基于提升( 1 i f i i n g ) 的双正交小波构造方 案【3 8 1 ，该方法也是在半正规网格上进行的。与非提升的方案相比，该方案在小波变 换过程中增加了提升的环节。提升过程可以分为分裂、预测、更新三个步骤。提升 过程如下图2 - 4 所示： f i g u r c2 4l h el i f t i n gw a v e l e t 订a n g f 0 1 强 分裂：利用懒惰小波( 1 配y 、v a v e l e t ) 对。空间中网格的顶点进行下采样 ( m l b s a m p l i n g ) 2 预测：为了消除第一步分裂后的冗余，给出更紧密的数据表示，将由下采样后 一空间的点对其余顶点进行预测，预测值由b l m e r n y 方案求出，得到的预测误差就 是小波系数。由于巧空间的顶点和巧。的其他顶点之间有很大的相关性，因此小波 系数具有很低的能量分布； 提升：为了保持原始数据的某些全局性质不变，最后将用小波系数d 对那些保 留的顶点的坐标( 即尺度系数) 进行修正，即提升。 依次重复上述步骤，可以将网格中的原始顶点分解为一系列的尺度系数和小波 系数，于是形成了不同尺度( 分辨率) 下原始数据的近似表示和细节信息。由此可 知，提升小波的思想与其他小波变化的思想一致，其中选择分裂方式以及预测器相 当于选取了不同的滤波器组。 基于提升的小波变换的逆过程与上述过程相反，依次包括：恢复提升、反预测、 合并。反变换过程如下图2 5 所示： 2 5 零树结构 图2 5 提升小波逆变换 f i g i 】雌2 - 5 血c 咒v e r s e 订锄s 向mo f t h el m