（计算机应用技术专业论文）四边形面片压缩及渐进传输算法的研究.pdf

四边形面片压缩及渐进传输算法的研究y 1 9 8 6 2 稳 论文题目：四边形面片压缩及渐进传输算法的研究 专业：计算机应用技术 硕士生：林煜超 指导教师：罗笑南教授周凡讲师 摘要 随着计算机浮点运算能力和图形加速能力的飞速提升，应用实践对三维模型 的真实感和细腻度的要求越来越高，导致了三维几何模型的拓扑信息和几何信息 急剧增长，从而为模型数据的传输和存储带来了严峻的考验。本文所研究的几何 模型压缩和渐进传输算法，有利于减少几何模型数据信息的冗余，提高模型的传 输速度，加速模型的显示。因此，本课题对于三维技术的推广和应用具有十分重 要的现实意义。 本文以四边形面片为基本研究对象，根据几何模型拓扑信息和几何信息的不 同特点，分别研究拓扑信息的简化和几何信息的数据压缩两个方面内容，并结合 这两方面的研究建立一个完整的四边形面片压缩和渐进传输算法框架。在拓扑信 息的简化上，本文主要研究基于细分小波的面片简化。文章运用提升算法和 k o b b e l t 提出的细分模型建立四边形插值细分小波，再利用该细分小波对面片进 行简化，达到拓扑信息简化的目的。在面片简化的同时，部分几何信息会转化为 小波系数，方便了后续几何信息的压缩。在几何信息的压缩上，本文主要研究小 波系数的量化和零树构建两方面内容。文章首先根据各简化层次面、边的对应关 系，提出小波系数的组织方式，构建出基于浮点数域的四叉树。接着，本文参照 e z w 算法提出浮点形式的逐次逼近量化，给出量化阈值的计算公式，从而结合 熵编码技术对四叉树进行量化编码，实现几何信息的数据压缩。最后，本文综合 上述几何压缩、数据压缩的研究内容，结合面片重构、熵编码等算法，给出一个 面向四边形面片的压缩和渐进传输算法框架，并对框架的部分算法实现进行阐 述。通过对实际模型的试验，该算法有较高的压缩比，同时支持渐进传输和显示， 达到了预期的目的。随着三维图形显示的推广，本文的成果将会有较好的应用前 景。 关键词：几何压缩、渐进传输、细分小波、系数量化、零树构建 四边形面片压缩及渐进传输算法的研究 t i t l e ：g e o m e t r yc o m p r e s s i o na n dm u l t i - r e s o l u t i o ne x p r e s s i o no f q u a d r i l a t e r a lm e s h m a j o r ：c o m p u t e r a p p l i c a t i o nt e c h n o l o g y n a m e ：l i ny u c h a o s u p e r v i s o r ：p r o f e s s o rl u ox i a o n a n i n s t r u c t o rz h o uf a n a b s t r a c t w i t ht h ed r a m a t i cg r o w t ho f f l o a t i n g - p o i n to p e r a t i o na n dg r a p h i c sa c c e l e r a t i o n , h i g h l y r e a l i s t i ca n ds m o o t ht h r e ed i m e n s i o n a lm o d e l sa r er e q u i r e db yv a r i o u sa p p l i c a t i o n s t h i si n c r e a s i n gr e q u i r e m e n tl e a d st ot h eh i g hd e m a n do f c o m p l v x i t yo ft o p o l o g i c a l i n f o r m a t i o na n dg e o m e t r i ci n f o r m a t i o n , a n d c o n s e q u e n t l yp u tf o r w a r dg r e a t c h a l l e n g e st ot h es t o r a g ea n dt r a n s m i s s i o no fm o d a ld a t a i nt h ef o l l o w i n gt h e s i s , w e w i l ld i s c u s st h e g e o m e t r yc o m p r e s s i o na n dm u l t i - r e s o l u t i o ne x p r e s s i o nf o r q u a d r i l a t e r a lm e s h e s ，a n di tw i l lh e l pt or e d u c et h er e d u n d a n c yo f m o d e ld a t aa n dt o i m p r o v et h et r a n s m i s s i o ns p e e da n dr e n d e r i n gs p e e do ft h r e ed i m e n s i o n a lm o d e l s t h e r e f o r e , t h i st h e s i s i so fg r e a tp r a c t i c a ls i g n i f i c a n c ef o rt h ep r o m o t i o na n d a p p l i c a t i o no f t h r e ed i m e n s i o n a lt e c h n o l o g i e s f o c u s i n go nq u a d r i l a t e r a lm e s h , t h i st h e s i sd i s c u s s e sa b o u th o wt os i m p l i f yt h e t o p o l o g i c a li n f o r m a t i o na n dt h ew a y t oc o m p r e s sg e o m e t r i ci n f o r m a t i o na c c o r d i n gt o t h ec h a r a c t e r i s t i c so ft o p o l o g i c a la n dg e o m c t r i ci n f o r m a t i o n t h i st h e s i sa l s o c o m b i n e st h e s et w oa s p e c t st oe s t a b l i s ha ni n t e g r a t ef r a m e w o r kf o rg e o m e t r y c o m p r e s s i o na n dm u l t i - r e s o l u t i o ne x p r e s s i o no fq u a d r i l a t e r a lm e s h e s i no r d e rt o s i m p l i 分t o p o l o g i c a li n f o r m a t i o n , t h i st h e s i sc o n s b - u c t s a l li n t e r p o l a t e ds u b d i v i s i o n w a v e l e tf o rq u a d r i l a t e r a lp a t c h e sb a s e do nt h es u b d i v i s i o ns c h e m ea d v a n c e db y k o b b c l ta n dl i f t i n ga l g o r i t h m w i t ht h i ss u b d i v i s i o nw a v e l e t , w ec a ne a s i l ys i m p l i f y a n yr e g u l a rq u a d r i l a t e r a lm e s ha n dc o n s e q u e n t l ya r c h i v eo u ra i m 砒t o p o l o g i c a l i n f o r m a t i o nr e d u c t i o n t h es i m p l i f y i n gp r o c e s sa l s ot u r n ss o m eo fg e o m e t r i c i n f o r m a t i o ni n t ow a v e l e tc o e f f i c i e n t sa n dt h i sw i l lf a c i l i t a t et h ef o l l o w - u pg e o m e t r i c c o m p r e s s i o n i ng e o m e t r i cc o m p r e s s i o n , t h i st h e s i sf o c u s e s0 1 1q u a n t i z a t i o no f w a v e l e t e o e f f i c i e n t sa n dt h ec o n s t r u c t i o no fz e r o - t r e e1 _ 1 l e p r o p e r t i e so fw a v e l e tc o e f f i c i e n t so fd i f f e r e n ts i m p l i f i e dl e v e la n dt h ec o r r e l a t i o n s b e t w e e nt h e mi no r d e rt op r o p o s eac o n v e n i e n tw a yf o rt h et r a v e r s eo fw a v e l e t c o e f f i c i e n t sa n dc o n s t r u c t i o no fq u a d t r e eb a s e0 1 1f l o a t i n g - p o i n td o m a i n a n dt h e n , t h i st h e s i sp r o p o s e sas u c c e s s i v e - a p p r o x i m a t i o nq u a n t i z a t i o nb a s eo nf l o a t i n g - p o i n t d o m a i nt ot h ew a v e l e tc o e f f i c i e n t si nt h el i g h to fe z w , a n dp r e s e n t st h ec o m p u t a t i o n f o r m u l af o rt h r e s h o l d w i t hs u c c e s s i v e - a p p r o x i m a t i o nq u a n t i z a t i o na n de n t r o p y c o d i n g , w cc a ne a s i l ya p p l yd a t ac o m p r e s s i o nt ot h ez e r o - t r e et oa c h i e v et h eg o a lo f g e o m e t r i ci n f o r m a t i o nc o m p r e s s i o n i nt h e l a s t p a r t ，t h i st h e s i sp u tf o r w a r da f r a m e w o r kf o r g e o m e t r yc o m p r e s s i o n a n dm u l t i - r e s o l u t i o n e x p r e s s i o n f o r q u a d r i l a t e r a lm e s h e sb a s e do nt h ea b o v ed i s c u s s i o n sa n dr e m e s h i n ga n dz e r o - t r e e c o m p r e s s i o na l g o r i t h m i m p l e m e n to ft h ek e yf l g o f i t h m sa r ea l s op r e s e n t e di nt h i s p a r t w eh a dt r i e do u tt h ef r a m e w o r ko ns o m ea c t u a lm o d e l sa n da c h i e v e dt h ed e s i r e d r e m f l t ss u c ha sh i 班c o m p r e s s i o nr a t i oa n ds u p p o r t i n gp r o g r e s s i v et r a n s m i s s i o n w i t h t h ep r o m o t i o no ft h r e e - d i m e n s i o n a lg r a p h i cd i s p l a y , t h er e s u l t so ft h i sp a p e rw i l lb ea b e t t e rp r o s p e c t k e y w o r d s ：g e o m e t r yc o m p r e s s i o n ，p r o g r e s s i v et r a n s m i s s i o n , s u b d i v i s i o nw a v e l e t , q u a n t i z a t i o n , c o n s t r u c t i o no fz e r o - t r e e 1 1 1 四边形面片压缩及渐进传输算法的研究前言 前言 随着三维处理技术的日新月异，三维建模已经在工程设计、机械制造、模拟 仿真、游戏娱乐等各个领域中得到广泛应用d 2 。应用的需求带动了采集技术的发 展，相应的模型也越来越精细，但也导致了模型数据的急剧增长。例如斯坦福大 学的d i g i t a lm i c h e l a n g e l op r o j e c t 项目，最大的雕塑模型数据量竞超过了3 2 g ，而 普通的模型数据量也十分可观【卅。而另一方面，计算机的存储和网络传输能力却 相对有限，特别是网络传输带宽，远远不能满足模型数据的实时传输。为了解决 上述矛盾，满足应用的需求，我们需要研究模型数据的压缩和传输，从而尽可能 地利用目前已有的存储和传输能力。 本文的研究以四边形面片模型为基本考察对象，研究四边形模型拓扑信息简 化和几何信息压缩的相关技术，同时研究模型的渐进传输和显示。在本文中，我 们暂时不涉及模型的纹理、质感等方面的研究。全文的主要研究在于以下三个方 面的内容： ( 1 )四边形面片的简化。本文研究如何应用提升算法，结合k o b b e l t 提出的 四边形插值细分模型，构建四边形插值细分小波。利用该小波，我们可 以对四边形面片进行简化，形成基网格和一系列的小波系数，达到简化 与渐进传输的目的。同时，简化形成的小波系数符合一定的统计特性， 十分方便做进一步压缩处理。 ( 2 )小波系数的量化与零树构造。面片简化后的细分小波系数同样为浮点数 值，在存储上占用了较大的空间，同时不方便于后续的压缩。为了对小 波系数做进一步压缩，我们将采用一定的策略将小波系数构建成一棵四 叉树，再利用零树压缩算法进行量化压缩。本文根据小波系数之间的层 次关系，提出构建零树的方法，并研究如何利用逐次逼近量化对小波系 数进行浮点系数量化。量化后的小波系数在一定程度上降低了存储的要 求，同时还非常适合采用熵编码对量化结果做进一步的压缩。 四边形面片压缩及渐进传输算法的研究前言 ( 3 ) 四边形面片压缩和渐进传输算法框架。综合上述的研究，结合面片重构、 熵编码等算法，本文将提出一个完整的四边形面片压缩和渐进传输算法 框架，用于对几何模型进行拓扑简化和几何信息压缩，达到压缩模型数 据的目的。同时该框架还支持渐进传输和显示，具备较高的实用意义。 本文的章节结构如下： 第1 章，介绍本课题的研究背景和相关基础理论，特别是本文重点研究的细 分小波、小波系数量化、压缩编码等方面的相关理论； 第2 章，研究细分小波在几何模型简化中的应用，给出四边形插值细分小波 的构造方法和各个算子的构建过程； 第3 章，研究小波系数的特点和层次对应关系，根据面边对应关系给出零树 构建的方法并提出小波系数的量化方法： 第4 章，综合上述研究，给出四边形面片压缩和渐进传输算法的总体框架， 并给出部分模块的具体实现； 第5 章，总结本文的研究工作，指出研究中的不足和后续研究的方向。 四边形面片压缩及渐进传输算法的研究 第1 章综述 第1 章综述 本章概括性地论述几何面片压缩及渐进性传输的研究背景、发展现状及主要 研究内容，简略地介绍现有各种拓扑信息压缩技术、几何信息压缩技术的基本思 想和优缺点，并着重对渐进式几何压缩涉及的各种编码方法进行介绍，从而方便 后续章节的展开。 1 1 研究背景 计算机图形学和硬件技术的发展，为人们带来视觉上的革命。随着技术发展， 传统二维的表现方式已经不再满足人们的需求，人们对计算机的交互能力和表现 能力提出了更高的要求，采用三维技术来表现各种的场景已经是大势所趋。同文 字、图像、视频等二维媒体表现形式相比，三维图形显示因具有真实感更强、直 观性更好和交互更为灵活的特点，已经开始在各个领域中受到广泛应用。特别是 在强调直观性和交互能力的场合，如工程设计、机械制造、模拟仿真、城市规划、 文物修复以及游戏娱乐等方面，三维显示技术起到了不可替代的作用】。 但是，三维显示技术的发展和推广受到了传输带宽和存储空间的限制，因为 三维模型所能容纳的信息量远远超出了二维形式所能容纳，对这些模型的存储和 传输需要大量的空间和带宽，这一点超出了目前硬件和网络的发展水平。图卜l 是文献( 3 4 ) 中提到的s k e l e t o nh a n d 模型，该模型由3 2 7 3 2 3 个顶点、6 5 4 6 6 6 个面组成，压缩前的p l y 格式文件占用了3 2 6 m b 的空间。图卜2 是f u h u ac h e n 在其个人网站。上给出的工程模型，即使是这样简单的一个模型，也需要由2 7 2 7 个顶点和2 7 0 1 个面组成，采用t i t 文件格式简单记录各项点的坐标和面的顶点 序号，也需要占据1 9 6 k 的空间。 在实际的应用中，特别是在三维动画、文物修复等应用环境下，图卜2 这样 的粗糙模型已经无法满足操作的需求，只有图卜1 这样的模型才能满足人物造 。h t 叫肌y w w c 锄弘u b c d u c l l 妒t r 鲫l l t 娼u b d i “s i s u 响。c “蛐h h 州 四边形面片压缩及渐进传输算法的研究第1 章综述 型、文物三维重构的要求；但在这种精度要求下，一个完整模型所需要的存储空 间可想而知。 图i - is k e l e t o n h a n d 模型( 摘自文献( 3 4 ) ) 图l - 2 飞机模礁 存储只是一个方面的限制，网络传输才是更大的瓶颈。按照目前的网络情况 而言，网络带宽通常为1 2 m b s ，这就意味着传送s k e l e t o nh a n d 模型至少需要 1 6 秒，而正常应用的场景下，还需要增加背景图案和其它模型，再加上计算机 运算和渲染的时间，一个p c 用户需要等待2 、3 分钟才能见到一个完整的场景， 这完全超出了用户的承受限度。 为此，考察三维模型的压缩和渐进传输相关技术，研究如何在压缩模型数据、 提高存储效率的同时，提高模型的传输和显示速度，有着广阔的发展前景和应用 意义。 1 2 几何压缩概述 应用的需求，为理论研究的发展提供了强大的推动力，人们开始研究如何对 模型进行简化和数据压缩，以适应实际应用的需求。1 9 9 5 年，s u n 公司的d e e r i n g 发表了g o o m c t r y c o m p r e s s i o n l 2 3 一文，揭开了三维几何压缩的序幕。在这之后， 相关的压缩算法不断被提出，进行了各种改进和提高，各种工程化的技术也不断 地被提出【1 7 强2 引。 在研究中，通常把网格模型所包含的信息划分为三个部分：第一部分为拓扑 信息( t o p o l o g i c a li n f o r m a t i o n ) ，主要描述网格模型中顶点与面片之间的邻接关 四边形面片压缩及渐进传输算法的研究第l 章综述 系；第二部分为几何信息( g e o m e t r i ci n f o r m a t i o n ) ，用于描述网格模型顶点的坐 标位置，几何信息一般都以单精度的浮点数形式存放，因此所占用的空间相对比 较大；第三部分为属性信息，包括颜色、法线向量以及纹理坐标等信息【蜘。 在p r o g r e s s i v eg e o m e t r yc o m p r e s s i o n 2 】一文中，k _ h o d a k o v s k y 等人对几何信息 做了迸一步的分析，将参数信息( p a r a m e t e ri n f o r m a t i o n ) 从几何信息中剥离出来， 缩小了几何信息的内涵。从直观上理解，我们可以简单地将几何信息理解为顶点 坐标沿法向方向的分量，这个量对于面片的拟合程度有较大的影响；参数信息则 可以理解为顶点坐标沿切线方向的分量，该分量对面片拟合程度的影响较小。在 下文中，我们将不详细区分几何信息这个概念；在与参数信息一起使用的时候， 几何信息是狭义上的几何信息，其它情况下一般都指广义上的概念。 网格模型不同信息的划分，带来了不同的压缩途径。研究人员针对拓扑信息 和几何信息提出了多种不同的算法，促进了几何模型压缩的发展。 1 2 1 拓扑信息压缩技术 对于一个几何模型而言，它的顶点通常采用一个浮点数组来表达，而边、面 则是用顶点的数组下标来表达。通常，几何模型边和面的数量都是相当庞大的。 所以，拓扑信息压缩的目的就是尽量减少模型中所需记录的顶点数目。或者是尽 量避免同一个顶点序号在拓扑信息中多次出现。目前的拓扑信息压缩技术分为以 下五种类型： ( 1 )基于三角形带的压缩 这类压缩算法的基本思想为建立带状的三角形结构来组织几何模型，使得同 一顶点在某个三角形带中最多只出现一次，从而减少同一个顶点序号在不同三角 形拓扑信息中出现的次数2 】。这类算法的实质，是利用了相邻三角形具有一条共 边、两个共同顶点的特性，只记录一次共边上的顶点，从而达到减少拓扑信息的 目的。 o 分类方法参照了学术报告几何模型压缩( 作者：王文成，中国科学院软件研究所) h t t p ：w w w c a d 萄u 。d u m 瑚辨删i l i c 蛐啊曲印0 n 忙g s y n l p l o s i u t l l 0 5w 抽g w 舶g c h 舶最_ 9 m c p d f 一5 一 i i i l 边形面片压缩发渐进传输算法的研究第1 章综述 ，凝s o ? ，彩 ? | 、蔷j 、， ， ，一7 、4 前一一落7 图1 - 3 三角形带示例 如图卜3 所示，三角形岛与s 。之间存在着邻边丽，所以在记录& 、蜀时， 可以只记录一次k ，从而减少拓扑信息的记录；在绘制三角形带时，则通过设 置缓冲器暂存公共顶点，减少后续数据的传输量。比如说在绘制s o 、墨时，可 以先绘制三角形氐，然后通过顶点缓冲器记录顶点k 和，绘制s 。时就可以只 传送巧。 根据三角形带形状的不同，常用的三角形带有星形三角形带( s t a rt r i a n g l e s t r i p ) 、锯齿三角形带( z i g - z a gt r i a n g l es t r i p ) 、广义三角形带( g e n e r a l i z e dt r i a n g l e s t r i p ) 三种。 ( 2 )基于度驱动的压缩 这类算法的基本思想是以一个三角形开始，根据每个点的度不同逐步处理各 个点；当点的度用完时，再对相关的点进行处理。简单一点来说，该类算法是利 用了图论中顶点度的概念，通过入度出度值对网格的拓扑信息进行编码。 这类算法的典型代表为文献( 8 ) 中提出的入度编码法。该文指出，在接近 规则网格的情况下，网格顶点的入度是一个均值为6 的概率分布，越靠近6 ，入 度值出现的概率越大。因此，如果采用熵编码对顶点的入度值进行压缩，该网格 的顶点入度编码可以获得小于l b v 、甚至0 2 b v 的编码结果。 ( 3 )基于区域扩张的压缩 该类算法的基本思路与基于度驱动的压缩的方法类似，它从一个种子三角形 开始，逐渐地扩张所处理的三角形，直到覆盖整个网格模型。但与后者不同的是， 这类算法输出的是拓扑变化，二恧不是点的度。 四边形面片压缩及渐进传输算法的研究第l 章综述 该类算法的典型方法为r o s s i g n a c 提出的e d g e b r e a k e r 1 8 1 算法。该编码方法是 目前最好的编码方法之一，具有编解码速度快、便于硬件实现的特点。它还有一 个最坏情况下的编码效率的估计值，该估值为4 b v 。 该算法的基本操作为：以一条边作为入口，以边对应的顶点环绕一周的边作 为一个顶点环，从入口开始按照相邻关系对网格上的三角形依次进行遍历。对每 个遍历三角形而言，会有两个顶点位于顶点环的入口，然后根据它的第三个顶点 的各种不同情况输出一个不同的操作码，最后所有操作码形成一个码串，称之为 操作码历史。 图l - 4 算法遍历过程的五种不同情况，下方字母为输出的操作码( 摘自文献( 1 8 ) ) ( 4 )基于分割的压缩 该类算法的基本思想为沿着边，将模型剖分并展开成平面，然后再将边、展 开的多边形形成树状结构，再对这些树进行压缩编码。该类算法的目的同样是为 了减少顶点在拓扑信息中的冗余记录，再利用数据压缩中的压缩算法对数据做进 一步的压缩操作。 拓扑手术算法( t o p o l o g i c a ls u r g e r y ) 【1 卅是该类算法的典型代表。该类算法采 用了树状结构进行存储，可以利用数据压缩相应的算法做进一步的压缩，具有一 定的优越性；但是这类算法的压缩过程中，需要同时维护两棵树，一个是顶点展 开树，另一个是三角形展开树，同时它是基于全局处理的，所以解码过程中需要 较大的存储空间，带来了一定程度的不足。 ( 5 )基于模型简化的渐进式方法 前述的几种算法都是非渐进性传输算法，也就是说，这些算法只能一次性地 四边形面片压缩及渐进传输算法的研究 第1 章综述 把整个模型数据传送，等全部数据接收完整后，才能构造出模型的形状。这样的 压缩方式，需要较长的网络延迟，不太适合模型的网络传输和即时显示。为此， 研究人员提出了渐进式的压缩方式，以适应网络传输和实时显示的需要。 渐进式方法的基本思想是对模型进行简化，通过一系列规范的操作使复杂模 型变换为简单模型和一系列层次细节，从而减少简单模型的拓扑信息。这类拓扑 压缩的实质，在于采用一个规范的操作，如点聚类分裂、边折叠、细分等等， 来替代模型中点、边、面的拓扑关系；也就是说，它是一种利用操作的复杂度替 换模型拓扑复杂度的方式。 渐进式方法比较典型的算法有渐进网格( p r o 伊e s s i v e m e s h e s ) 1 1 5 1 6 1 、c o h e n o r 提出的着色( c o l o r i n g ) 【7 1 编码方法、t a u b i n 提出的森林剖分方法( p r o g r e s s i v e f o r e s ts p l i t ) 1 3 1 、层分解5 1 、c p m 方法【2 川和基于细分小波的面片简化等等。 本文主要研究四边形面片压缩及渐进传输算法，其基本思路便是采用细分小 波对面片进行拓扑结构的简化和渐进传输，所以属于渐进式传输算法的研究范 畴。对于基于细分小波的面片简化，将在下面做较为详细的说明。 1 2 2 几何信息压缩技术 与拓扑信息类似，顶点坐标信息是几何模型的基本属性之一。网格模型中的 顶点坐标通常表示为三个带8 位指数的3 2 b i ti e e e 浮点数。这样表示的顶点坐标 所能表示的空间范围非常广阔，可以大到1 5 0 亿光年，小到一个原子的半径；但 是在实际的中我们并不需要如此大的范围，稍加研究我们发现用浮点数记录三维 物体的顶点坐标是非常浪费的，其中存在大量的冗余p 2 】。 几何信息的压缩技术，则是研究如何减少信息的冗余度，缩小顶点坐标的表 示范围，然后用相对较小的空间来存储坐标数据，从而达到数据压缩的目的。几 何信息的压缩主要是针对数据信息进行的，所以通常会带来一定的数据精度丢 失，导致模型整体的失真率提高。目前，几何信息压缩方面的研究发展相对比较 缓慢，主要可以分为以下几种： 四边形面片压缩及渐进传输算法的研究 第1 章综述 ( 1 )坐标量化 如上所述，顶点坐标采用浮点数表示存在着浪费，那么一种直观的考虑便是 截取浮点数中有用的字节，映射到一个相对比较紧凑的长度空间来表示，然后再 用较少的字节空间来保存数据。 图1 5 量化函数 表1 - 1 量化示例表 浮点数据量化结果 1 2 5 8 4l 1 3 4 0 02 1 7 6 0 0 6 1 6 0 0 05 如图卜5 、表1 - 1 所示，如果浮点数据处于区问 1 2 1 8 ) 之间，那么我们 可以将它映射到区间 0 6 ，再采用3 个b i t 来存储，这样就可以用3 个b i t 的空 间来表示原来需要3 2 b i t 的数据，大大减少了存储的空间。 但是，我们也应该注意到第一个数据的量化是一个不可恢复的过程。当我们 从存储空间上拿到量化结果1 的时候，我们只能将其恢复到 1 2 1 3 ) 之间的 某个数值( 通常采用中间值，在这里为1 2 5 ) ，而无法恢复到精确的浮点数。所 以，如果量化的级数比较简单的话，会造成数据的丢失；如果采用较多的量化级 数，则会带来存储空间的增大，降低压缩效率。 ( 2 ) 预测编码 预测编码是应用最为广泛的几何信息压缩技术之一，它根据拓扑信息压缩过 程中处理顶点的顺序，利用已处理的顶点坐标信息来预测未处理的顶点的坐标， 然后将预测值与实际值的差减操作，再对结果进行编码。 预测编码实际上是与坐标量化、拓扑信息压缩紧密结合在一起的。首先，我 们可以把它看作坐标量化的辅助操作，因为它的目的是为了将顶点数据移植到更 为集中的区域上，提高坐标量化的效率；其次，它也可以将它看作是拓扑信息的t 二 四边形面片压缩及渐进传输算法的研究 第1 章综述 补充操作，因为预测编码过程通常是与拓扑压缩过程结合在一起进行的，预测点 值的计算模型通常也就是拓扑压缩模型。 d e e r i n g 在g e o m e t r yc o m p r e s s i o n 【2 3 】一文中就使用了一阶的线性预测器对项 点的坐标进行预测编码。t a u b i n 等人在g e o m e t r i cc o m p r e s s i o nt h r o u g h t o p o l o g i c a ls u r g e n 1 4 2 刀中将其方法做了推广，使用高阶的线性预测器对顶点坐 标进行预测【3 2 1 。k h o d a k o v s k y 在p r o g r e s s i v eg e o m e t r yc o m p r e s s i o n t 2 l 文中则是 采用了细分小波作为预测器进行顶点预测和几何压缩，本文的研究也采用了相似 方法。 ( 3 )基千几何图像的压缩 与前几种几何信息压缩技术相比，基于几何图像的压缩采用截然不同的一种 压缩思路。该压缩算法的基本思想是通过参数化，将几何模型映射到平面上，然 后再将顶点的坐标映射为平面上对应点的色彩值。这样，我们就能运用比较成熟 的图象压缩的方法做进一步的压缩。 从思想上看，这种压缩方式确实十分独特，因为它跳出了三维框架的思想约 束，利用降维的方式，试图从二维的角度来解决三维的问题。但是从实际研究上 看，这种方法的计算开销较大，误差也比较大，压缩效率并不太理想。 几何图像法向图 图1 6 基于几何图像的压缩( 摘自文献( 2 9 ) ) 1 3 细分小波与面片的简化和渐进传输 1 9 7 8 年，c a t m u l l 和c l a r k 提出了著名的c a t m u l l c l a r k 细分模式n 】，标志着 细分方法正式成为曲面建模的手段。在这之后，细分方法得到了迅速的发展和广 四边形面片压缩及渐进传输算法的研究第l 章综述 泛的工程应用。特别地，随着第二代小波分析、多分辨率传输框架理论研究的深 入，细分模式逐渐与多分辨率分析、小波分析紧密结合，这使得细分曲面在几何 压缩领域备受关注【3 0 1 。 1 3 1 曲面细分 从简单意义上来说，曲面细分就是从给定的基网格肼。出发，递归地调用某 一细分规则对网格进行操作，使得满足【3 3 1 m “= s m ( 1 1 ) 从而形成一系列的网格m o ，膨1 ，m ，使得初始网格最终变成细密的控制 网格。( k = l ，2 ) 础疆 磁 图1 7 细分过程示意图 其中，就叫细分模式，是细分方法的核心。为了使最终的细密网格满足连 续、收敛等性质，细分模式需要满足一定的条件，具体的性质内容和证明过程， 请参考文献( 3 3 ) 中的介绍。 根据应用对象的不同，常用的细分模式可分为三角网格细分模式、四边形网 格细分模式两种。三角网格细分模式常见的有l o o p 细分【6 】、蝶形细分【删、；细 分4 1 l ，四边形网格常见的细分模式则有c a t m u l l c l a r k 模式【1 、d o o - s a b i n 模式 4 2 1 以及k o b b e l t 提出的四边形插值模型2 1 1 等等。 在四边形网格的细分模式中，d o o - s a b i n 模式、c a t m u l l c l a r k 模式均为逼近 模式，不太适合于工程模型的应用，所以本文并不准备深入研究。本文对四边形 网格模型的细分模式主要基于k o b b e l t 提出的四边形插值模型。在第二章的论述 四边形面片压缩及渐进传输算法的研究 第1 章综述 中，我们将会详细介绍该细分模型的具体内容。 1 3 2 基于提升算法的细分小波构造方法 以细分造型技术为基础，s w e l d c n 构建出了基于提升算法的球面细分小波并 给出了提升算法构造小波的理论基础，开创了第二代小波 2 0 淄4 3 , 4 4 。利用提升 算法，我们可以不依赖于傅立叶变换直接构建双正交小波，从而可以快速地构建 基于细分模型的小波变换。 采用提升算法来构造细分小波，通常需要涉及四个算子： ( 1 ) 分裂( s p l i t ) 分裂算子主要的作用是采用某种方式将原始的信息c “分解为两个互不相交 的信息子集c 一一和d “，其中c “为新的信息集，d “则是小波集，其意义类似小 波分析中的小波系数集。分裂算子主要用于提升小波分解过程的构造上。 分裂算法可以采用多种实现方式，比较简单的可以采用l a z y 小波、h a a r 小 波，也可以采用其它复杂的小波函数来处理。复杂的小波函数可能会方便后续预 测、更新算子的处理，提高算法的整体效果，但也容易带来效率上的问题。 ( 2 ) 合并( m e r g e ) 合并算子是与分裂算子相逆的算法过程，它的主要作用是利用合适的方式， 将得到的信息子集c ”1 和d “合并起来，还原出原始的信息集c ”，从而达到信息 重构的目的。 合并算子主要用于提升小波重构过程的构造上，它的实现需要与分裂算子一 一对应。因此，在构造分裂算子的同时，我们也得考虑该分裂算法能否构建出相 应的合并算子。无法构建合并算子的话，再好的分裂算子也是没有意义的，所以 这分裂、合并算子通常是合在一起考虑的。 四边形面片压缩及渐进传输算法的研究第1 章综述 ( 3 )预测( p r e d i c t ) 经过第一步的分裂，原始的信息集被分解为两个部分，这两个部分具有较 高的相关性。为了使构造的结果具有小波的特性，我们需要模拟小波变换的过程， 在信息子集c “和d ”1 之间建立一种预测关系，使得两部分转换成为小波变换中 的低频和高频部分。 以细分模型作为基础的话，我们可以将细分模型作为一个预测器，作用到e “ 上，并将其结果作为d ”的预测结果，从而建立了两者的预测关系。对于预测值 与d ”1 的差值，通常称为细节，或者仿照小波变换称为小波系数。 ( 4 ) 耍瓤( u p d a t e ) 在第一步的分裂过程中，信息集的分裂是采用抽样方式来处理的，也就是说， 我们是采羽某一固定的选择模式从c 月中抽取e “和d “，而不会考虑c 。本身的特 性。在这种方式下，可能会出现大量的信息特征给抽取到d ”1 之中，使得e ”1 无 法保持屏有信息集特征的情况。 为此，我们需要一个操作来将d “中的部分特征信息转移到c ”中，使得原 有信息集中的特征在c “能够得到保留，这个操作就是更新算子。对于更新算子 的实现，通常采用信息量平衡的法则来构建。采用s p l i t 、m e r g e 、p 、u 分别表 示上述四个算子，则我们可以按照以下的方式构建小波的分解和重构过程【3 6 1 ： 分解过程： 重建过程： f ”，d “ - - - s p t ( c “) d ”1 一= e ( c ”1 ) lc ”1 + = v ( d ”。) l e ”1 一= v ( d “) d - j + = p ( c “) i c “：= m e r g e ( c ”。，d ”一1 ) ( 1 2 ) ( 1 3 ) 网边形面片压缩及渐进传输算法的研究第1 章综述 在上述的分解和重构过程中，我们能够以细分模型为基础构建相应的算子， 构建出相应的第二代小波，从而能将细分造型技术和小波分析的相关技术连接起 来，更好地利用双方的优点和现有的研究成果。 1 3 3 细分小波在面片压缩和渐进传输中的应用 正如上面所提到的，通过提升算法的应用，我们可以将曲面细分和小波分析 的相关技术结合在一起，再利用它们各自在几何压缩和渐进传输中的应用，形成 更好的压缩和渐进传输框架。 对于小波分析而言，它有着坚实的理论基础和完美的多分辨率分析的数学框 架，是构造多分辨率模型最有力的工具i 捌。而对于曲面细分而言，我们可以从它 的操作过程看出，它的正向过程是一个从简到繁的渐变；当我们把原始的网格模 型看作是最终细分的结果，把初始的网格看作是结果的话，则它就是一个十分典 型的面片压缩过程。通过提升算法作为桥梁，则我们可以把两者结合起来，形成 统一的面片压缩和渐进传输框架。 1 4 重网格化 上一小节中，我们给出了基于细分算法的面片简化过程。在这过程中，我们 一直假设每一个简化层次的网格都具有细分连接性，都能满足简化过程中细分拓 扑信息的变化规律，不会出现冲突的情况。但是，在实际模型的产生过程中，由 于模型外观的不规则性，通常产生的网格都是不具有细分连续性的散乱网格，需 要做一定的规整处理后，才能使网格真正支持拓扑信息简化操作。我们通常将该 规整操作称为重网格化( r e m e s h i n g ) 。 在目前的研究中，重网格化技术大多是先进行参数化( p a r a m e t e d z a t i o n ) ，然 后利用半规整的网格进行重采样，从而建立一个具有细分连续性的新网格 5 4 1 。目 前，在这方面的研究比较著名的方法为文献( 1 、3 、4 8 、4 9 、5 5 、5 6 ) 中提到的 重网格化方法。 在本文中，我们采用文献( 4 9 ) 中提出的重网格化技术对初始的扫描网格进 - 1 4 - 四边形面片压缩及渐进传输算法的研究 第1 章综述 行处理，形成一个半i e 贝m j 四边形面片网格。其中，处于面片中间的网格项点全部 为度为四的正则顶点，边界一圈的网格顶点则为非正则的。在非正则顶点中，只 有面片四个角上的顶点的度为2 ，其它的非正则顶点均为度为3 的顶点。 图1 - 8b l e e k 面片模型的重网格化 我们采用文献( 4 9 ) 中提到的算法对b l e e k 模型进行重网格化，并将原始模 型、重网格化的模型和重网格化后形成的四边形网格进行显示，得到了结果图 卜8 国。 1 5 零树压缩编码 1 9 9 2 年，l e w i s 介绍了一种树形结构用于表示小波变换后的系数。1 9 9 3 年 s h a p i r o 将该数据结构叫为“零树( z e r o t r e e ) ”，并且开发了一个效率很高的算法 用于熵编码，称为嵌入式零树小波算法( e z w ) ，从而开创了基于零树结构的小 波图像压缩编码技术【6 l l 。后来，研究人员对其进行了大量的研究和改进，其中比 较著名的有算法s p h q t t 4 一o l 。目前，e z w 、s p i h t 正在逐渐被e b c o t 9 所代替。 小波图像编码的基本框架如图1 - 9 所示。框架分为三个部分，其中量化模块 是整个框架的压缩基础，也是数据损失的来源，我们一般将该模块的算法称为零 量化 i 撇变换卜 e z w 中的