（计算机软件与理论专业论文）三维几何网格模型压缩算法的研究.pdf

硕士论文 三维几何两格模型压缩算法的研究 摘要 本文主要讨论了三维几何网格模型的几何压缩算法的现状。并针对目前拓扑压 缩算法大都仅适用于三角形网格的现状，提出一种新型的无损压缩算法以及其实现 方法。该算法的特点如下： 1 以四边形为单元对模型进行抽象。应用于相同三角形规模的模型，用四边形 作为抽象单元的算术编码方式比以三角形为单元的编码方式效率高近2 倍。 2 就以四边形为单元抽象后的模型提出了按比特存储单元信息的方法。该方法 解决了由一个字节存储一个单元信息所造成的资源浪费，大大提高了压缩 率。 3 本文针对多组模型进行了不同压缩算法的实验。在对实验数据的分析和比较 后，得出结论，在相同的压缩算法复杂度的算法集中，本文所提出的压缩算 法编码简单，压缩率较高，是一种实用的无损压缩算法。 关键字：三维几何网格，几何压缩，算术编码 硕士论文 兰维几何网格樽型压缩算法的研究 a b s t r a c t s u b j e c tr e s e a r c h e dt h ee x i t i n gg e o m e t r yc o m p r e s s i o na l g o r i t h m sf o ru i a n g u l a r m e s h e s f u r t h e r m o r e ，u n l i k em o s te x i s t i n g0 1 1 e s ，an c x nu n - r e d u c c dc o m p r e s sa l g o r r h l m a n di t sa p p l i c a t i o na r eg i v e 也t h ef e a t u r eo f t h i sa l g o r i t h i mi sa sf o l l o w s ： 1 t h em e t h o dr e f o r m st h em o d e li np o l y g o n m s l l a c c o r d i n gt oo t h e rm e t h o d sw h o r e f o r mt h es a m em o d e lw i t ht r i a n g e s ，t h ef i r s to n eh a st w i c ee f f i c i e n c yb yt h e s e c o n d 2 t h em e t h o dm c m e r i e st h ec o m p r e s s e di n f o r m a t i o nb yb i t s i ts a v e st h em e m o r y s p a c e w h i c hi sw a s t e db yt h em e t h o dm e m o r y i n gau n i o ni no n e b y t e a f t e r a l l ，i t i m p r o v e st h ec o m p r e s s i n ge f f i c i e n c yo b v i o u s l y 3 s u b j e c tf r i e dd i f f e r e n tf e a t u r et e m p l a t ea n ds h o w e dt h ec o n t r a s td a t a i ts h o w e d t h a tw i t h i no t h e rc o m p r e s s i n gm e t h o d sw h oh a v et h es a m ec o m p l e x ，o u r si sa s i m p l e , h i g hc o m p r e s s i n ge f f i e c e n tu n - r e d u c e dm e t h o d k e yw o r d s ：p o l y g o n m s l l ，g e o m e t r yc o m p r e s s i o n , a r i t h r n e t i ce n c o d i n g 声明尸明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在本 学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发表或 公布过的研究成果，也不包含我为获得任何教育机构的学位或学历而使 用过的材料。与我一同工作的同事对本学位论文做出的贡献均已在论文 中作了明确的说明。 研究生签名： 雀鱼q 加厶年口钥刀日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅或 上网公布本学位论文的部分或全部内容，可以向有关部门或机构送交并 授权其保存、借阅或上网公布本学位论文的部分或全部内容。对于保密 论文，按保密的有关规定和程序处理。 研究生签名：垄堑堡年衫月7 日 硬士论文 兰维几何网堵模型压缩算法的研究 1 引言 1 1 研究背景及意义 1 1 1 背景 三维计算机图形学是c a d 、计算可视化和虚拟现实等技术的基础理论科学。随着 计算机技术的提高，三维图形学已经取得了飞速的发展。三维几何图形压缩编码是三 维计算机图形学的一个分支。近年来，大量的研究使得该领域取得了长足的进步，并 获得了一些有实用价值的研究成果。不过，三维几何图形的编码本身还是有一些关键 问题有待解决，研究的空间还是很大 随着三维模型获取手段的不断丰富，创建和编辑软件功能的不断强大，三维模 型在计算机图形学诸多应用颁域中使用的范围越来越广泛，使用的层面越来越深入。 从简单的增强视觉效果到利用其直观性进行人机交互，三维模型在工业制造、产品设 计、建筑设计、模拟仿真以及娱乐业等诸多领域中扮演着日益重要的角色。近年来，因 特网的发展速度和规模远远超出人们的预期，网络已经深入到人们日常工作、生活的 方方面面，通过网络远程获取和访问三维模型已经变得司空见惯尽管p c 机图形显 示卡的数据处理能力和网络带宽都已经取得长足的进步，但与三维模型日益精细所 带来的数据量和复杂程度的急剧增长相比，仍显得捉襟见肘。在这样的背景下，寻 找新的算法来更有效地表达三维模型，从而减少三维几何数据的存储量，相应地降 低其在网上传输所需的带宽，具有十分重要的意义。 1 1 2 重要性 研究三维几何图形的压缩编码的原因有三第一，为了获取更快的绘制速度和 更逼真的绘制效果，三维场景变得越来越复杂，从而三维场景的数据也变得越来越 庞大，使得计算机的运算和图形处理能力不能满足大规模复杂的三维几何模型的绘 制需求；第二，互联网正在成为虚拟现实和可视化系统的主流平台，由于带宽等限 制，目前的网络远远不能满足大规模三维集合模型实时传输的需求；第三，近年来 嵌入式系统的兴起及相关技术的飞速发展，越来越多的技术被其应用采纳，三维几 何图形的应用也在其中。由于嵌入式系统通常固有资源较小，实时性要求较高，大 规模的数据量的存储和传输时间成为了其应用的瓶颈。 硕士论文 三维几何网格模型压缩算法的研究 正是基于以上的原因，研究新的占用空间小，绘制速度快等特点的三维几何数 据表示方法有着十分重要的意义。 三维几何数据的通常表示形式是一些多边形网格，即一个标有一些属性的多边 形的集合。这些属性包括位置坐标、颜色、法线向量以及纹理坐标等。作为一种原 始的数据格式，多边形网格可以用几张表格来描述，其中的每一张表格对应着上面 的一种属性。虽然那些通用的压缩算法和工具也可以用来减少存放三维几何的数据 量，但是效率并不理想。而且通用压缩算法的压缩格式有时候对一些特定的应用来 说是不合适的。因此需要专门地为三维几何数据研究专门压缩算法。 1 2国内外现状分析 近年来，国内外的研究人员提出了许多编码三角网格拓扑信息的算法。这些算 法的基本框架是类似的，其中大部分方法都要动态地维护一个由顶点组成的循环链 表，在编码过程中每次删去一个与当前活化边相邻的尚未编码的三角形：同时根据 该三角形与循环链表之间的拓扑关系产生一个操作码，并相应地更新循环链表在 整个编码过程中，实质上进行了一次三角网格的遍历解码过程根据编码过程产生 的操作码，按照与编码过程完全相同的方式遍历网格，每次恢复一个三角形，最终 重建出原始网格不同的算法进行的遍历方式有所不同，e d g e b r e a k e r 算法 6 对三 角网格进行深度优先方式的遍历，而在g u m h o l d 等 4 提出的算法中进行的则是广 度优先方式的遍历此外，各个算法中区分出的当前编码三角形与循环链表之间拓 扑关系的不同情况也不完全一致。i t a i 等 1 提出4 种情形，在e d g e b r e a k e r 算法 中将这4 种情形分别记为，斤，s ，d 此外补充了新的情形叵而在g u m b ol d 等 4 的方法中则增加了当前编码三角形到达网格边界的情形t o u n l a 等 5 只考虑了 文献 1 方法中的后两种情形，为了能够完整地描述其它情形，t o u m a 等 5 编码了 各个顶点的入度，即与每个顶点相邻的所有边的条数，用以自动地确认其它情形。 对于非流形三角网格，刘新国 8 放宽了对网格边界只能是封闭的限制，允许开放边 界的存在，并据此将合并操作区分为4 种不同情形，从而解决了非流形三角网格的 拓扑编码问题i s e n b u r g 等提出的f a c ef i x e r 算法 9 采用直接的方式对多边形网 格连接关系进行编码，并且可以有效地扩展到对顶点属性具有结构化特征的多边形 网格进行编码在k r o n r o d 等 1 0 提出的非三角网格拓扑编码的方法中，基于任意 给定边数的多边形与循环链表之间的交互方式是确定的有限种情形这一事实，指出 三角形与c u z 2 b o r d e r 的交互方式共有类似于e d g e b r e a k e r 算法中提出的5 种情形； 而四边形与c u t b o r d e r 的交互方式则有1 3 种情形，这样就可以将三角网格拓扑编码 方式直观的推广到非三角网格。 2 硕士论文三维几何网格模型压缩算法的研究 1 3 研究内容及目标 任何的压缩算法都分为有损压缩和无损压缩两种。有损压缩是以牺牲压缩品质 的来获得比较高的压缩率的。本文所要研究的压缩算法是一种无损压缩算法，即不 以压缩品质为代价来谋取高压缩率，而把着眼点放在降低压缩算法的复杂度上。 目前的三维网格模型压缩算法中，大多数是以三角形为单位进行编码，且多是 按照一个三角形占一个字节的方式。 本文中将试图将模型的编码方式从以三角形为单位为基础进行拓展，设计一种 更为便捷高效率的模型抽象化法则，并在此基础上产生一种新型的模型编码与无损 压缩算法。 1 4论文的安排 本文的总体安排如下： 第一章阐述研究三维几何网格模型压缩算法的背景，意义以及重要性。分析了 三维几何网格模型压缩算法的发展现状。介绍本文的研究内容与目标。 第二章主要介绍本文所涉及到的计算机图形学中的基本概念，包括图论，遍历 算法，编码等。 第三章主要介绍目前国内外现存的编码与压缩算法，以及三维几何模型的编码 分类等。 第四章详细描述了一种新的三维几何模型编码规则与压缩算法。包括对模型的 抽象化法则，对三角形带尾端的处理，编码信息的存储等，给出了算法的伪代码并 讨论了理论压缩率。最后，基于所提出的算法进行一系列的实验，讨论了实验结果。 第五章对该算法进行了总结和进一步研究方向的展望。 硕士论文 三维几何同格模型压缩算法的研究 2 计算机图形学中的几何 2 1 计算机图形学简述 计算机图形处理核心部分流程如图2 1 所示，主要包括几何数据输入、动画、坐 标变换、视域裁剪、取景变换、绘制渲染、直到最后输出合成图像。可以看到，三维 几何数据是计算机图形学中不可或缺的一个重要部分，它给出了目标场景的一个立体 描述。一个典型的三维场景描述由一些三维几何模型组成，有时候还会附加一些结构 信息。本文不涉及基于图像的建模的内容。 图2 i 三维计算机图形处理的核心部分流程图 几何模型的形状描述了物体所占据的空间。在计算机图形学中，描述物体形状的 方法有很多，如体素表示法( v o x e lr e p r e s e n t a t i o n ) 、c s g 树表示法以及边界表示 法( b o u n d a r y r e p r e s e n t a t i o n ) 等等。其中边界表示法是应用最为广泛的一种方法。 在边界表示法中，物体的形状信息是通过它的表面来描述的。而物体的表面又可以有 各种各样的表示方法，如参数曲面、代数曲面、隐函数曲面以及多边形网格等等。 而几何模型的外观则描述的了物体上的入射光线和出射光线之间的相互作用关 系。本质上它是物体本身固有的一种物理性质但是在计算机图形学中，我们常用一 些易于理解的光照明量来描述，如颜色( c o l o r ) 、光泽度( s h i n i n e s s ) 、以及透明 度( t r a n s p a r e n c y ) 等等。在真实世界中，有的物体表面细节极为丰富，光照特性极 4 硕士论文三维几何碍格模型压缩算法的研究 其复杂。为了描述这些复杂的物体表面，针对不同类型的物体，人们研究了多种更复 杂的外观表示方法，如双向反射函数( b r d f jb i - d i r e c t i o n a r e f l e c t i o n d i s t r i b u t i o nf u n c t i o n ) 、纹理映射( t e x t u r em a p p i n g ) 、凹凸纹理映射( 茸u m p t e x t u r em a p p i n g ) 、双向纹理函数( 曰7 rb i - d i r e c t i o n a lt e x t u r ef u n c t i o n ) 等 等。 目前绝大多数的计算机辅助设计和计算机动画造型软件都支持c s g 和n u r b s 表示的几何模型，而且这些造型系统常常输出一些t r i m e d 自由曲面。t r i m m e d 自 由曲面是一种高层表示( h i g hl e v e lr e p r e s e n t a t i o n ) ，用来描述光滑曲面，或者 光滑曲面的一部分。从硬件绘制的角度看，这些曲面在进入绘制硬件之前通常要事先 离散为三角形网格。即使是支持n u r b s 的绘制硬件也一样。另外，用自由曲面表示 几何模型的主要优点并不在于用它来进行实时显示，而是在于用它来完成其它一些特 定任务，如：机械加工( m a c h y n i n g ) 、物理分析( p h y s i c a l a n a l y s i s ) 、相互交换 ( i n t e r c h a n g e ) 等等。再者表示一张t r i m m e d 自由曲面还是需要相当多数据的。所 以从数据压缩的角度来看，t r i m m e d 自由曲面并不比离散的三角形网格模型要紧致多 少，尤其是当我们只要求物体显示精度的时候。另外，并不是所有物体表面都适合用 自由曲面表示。例如像牙齿、鞋等这类在计算机动画造型和制作中经常遇到一些物体 表面，它们不像机械工程中的那些汽车顶棚，涡轮机叶片那样可以用一块、或者几块 光滑的曲面拼接而成。也就是说用自由曲面表示这些不规则、不光滑的物体没有任何 优势。因此，一方面自由曲面将仍旧在造型领域中广泛应用，另一方面对于很多应用 和很多类型物体，三角形网格模型将比自由曲面更加实用方便。 从三维光栅图形学发展的早期阶段开始，人们就使用多边形表示的几何模型。一 个典型的多边形模型通常表示为顶点、边、面的链表，例如大家熟知的翼边结构 ( w i n g e de d g es t r u c t u r e ) ，这主要是为编辑显示而设计的。在一些三维数据格式 中，如w a v e f r o n to b j ，我们可以看到这种多边形表示的影子，而且为了可读性它们 通常采用文本存储方式。另外，多边形表示一般都支持任意的边多边形。早期的 绘制硬件还接受这种边多边形，但是出于速度考虑，几乎今天所有的绘制硬件都 要求这些多边形在提交之前必须分解为三角形。即使有些绘制硬件能够接受四边形， 那也是隐含着这些四边形在绘制之前可以由系统任意地分解为两个三角形。 基于上述理由，几何压缩研究主要集中在对多边形网格模型，尤其是在三角形 的网格模型的压缩上。所谓的多边形网格就是一个标有一些属性的多边形的集合 在一个典型的由多边形网格表示的三维几何模型中，这些属性包括位置坐标、颜色、 法线向量以及纹理坐标等。作为一种原始的数据格式，多边形网格可以用几张表格 硕士论文 三维几何网格模型压缩算法的研究 来描述，其中的每一张表格对应着上面的一种属性。一个多边形网格模型所表达的 信息通常分为两部分内容：第一部分叫做拓扑信息，用于描述多边形网格中各顶点 和面片之间的相互连接关系；第二部分叫做几何信息，用于描述多边形网格的位置 坐标、以及附着在网格上的其它信息，包括颜色、法线向量以及纹理坐标等。这些 几何信息一般都以单精度的浮点数形式存放。因此一个三角形有时候可能要占用上 百个字节( b y t e ) 的空间。本文主要讨论对于拓扑信息的压缩算法的研究。 2 2 图论 多边形网格模型中顶点之间的相互连接关系，即拓扑信息，可以用一个图( g r a p h ) 来表示。图2 2 给出了一个简单的四面体模型及其拓扑图。所以图论中的一些结果 可以用于对多边形网格模型的拓扑信息进行编码。下面对图论中的一些基本概念和基 本算法作一个简要的介绍。 2 (a)(b) 圈2 2 用图表示网格模型中的拓扑信息( a ) 是个简单的四面体模型：是个圈， 表示( a ) 中四面体的拓扑信息( b ) 中图的顶点和四面体模型上的顶点一一对应 2 3 图论的基本概念 在图论中，一个图g 定义为一个二元组：g = 以e ) ，其中r 是图的有限非空顶 点( v e r t e x ) 集合；f 是图的边( e d g e ) 集合，每一个元素由v 中的两个顶点构成。 在有多个图的时候，我们通常用r ( g ) 和e ( g ) 分别表示图g 的顶点集合和边集合 以示区别。构成一条边的两个顶点都称为边的端点( e n dv e r t e x ) ，该边也同时称为 6 硕士论文三维几何网格模型压缩算法的研究 端点的入边( i n c i d e n te d g e ) 。个顶点y 的入边数目称为顶点的入度( d e g r e e ) ， 记作d e g ( v ) 如果两个顶点之间有一条边连接，那么称它们是相邻的( a d j a c e n t ) 。 如果两条边有一公共顶点，那么也称它们是相邻的。一个顶点r 所有相邻顶点所组 成的集合记为彳谚( v ) 。在本文中我们假设一个图没有环( 1 l p 任何两条边的顶点都不完 全相同) ，因此顶点的入度也等于它相邻顶点的数目。 设 ，蜥) 是图中的一个顶点序列，如果该序列中任何两个相继的 顶点之间都有一条边相连，而且除了n 和纷可能相同之外再没有重复的顶点，那 么称该序列为连接班，玢的一个路径( p a t h ) 如果h 和功是相同的顶点，那么 称这个路径是循环的( c y c l i c ) ，或者封闭的，否则称它为非循环的( a c y c i c ) ， 或者开的。如果一个图中任何两个顶点之间都有一条路经相连，那么称这个图是连通 的。一个不包含循环路径的连通图称为一棵树( t r e e ) 图的极大连通子图( m 珏i m u m c o n n e c t e d s u b g r a p h ) 称为分支( c o m p o n e n t ) 。如果一个图的所有分支都是一棵树， 那么称该图为森林( f o r e s t ) 。 设是另一个图，如果矿( 哪c y ( g ) 并且烈日) e ( g ) ，那么称为g 的子图 ( s u b g r a p h ) 。再如果p ( 日) = 矿( g ) ，那么称为口的展开子 ( s p a n n i n g s u b g r a p h ) 。 再如果是一棵树，那么称为扩的展开树( s p a n n i n gt r e e ) 用构造法可以证 明，每一个连通子图都包含一个展开树。 如果一个图可以在一个平面内画出来，而且任何两个彼此不相邻的两条边都不相 交，那么称这个图是可平面嵌入的( e m b e d d a b l e 妇t h ep l a n e ) ，或者称它是一个 平面图( p l a n a rg r a p h ) 给定一个平面图以及该图的一个平面嵌入，图的区域 ( r e g i o n ) 指平面上这样的一块极大区域：在该区域内的任意两个点之间都可以用一 条不跨过图的任何一条边的曲线相连。区域可以分为两类：一类称为内部区域 ( i n t e r i o rr e g i o n ) ，它由图的一些边所包围；另一类称为外部区域( e x t e r i o r r e g i o n ) ，它一直延伸到平面的无穷远处。任何一个平面图都有且仅有一个外部区域。 在一个平面图中，根据e u l e r 公式，平面图中区域刀的个数与图的顶点个数、边的 个数有如下关系：i 矿l i e i + l r t = 2 。 对平面图岔可以用下面的方法构造一个新的图六称为图口的对偶图：对偶 7 硕士论文三维几何网格模型压缩算法的研究 图中的每一个顶点一一对应于原图中的一个区域，原图中共用一条边的两个区域在对 偶图中所对应的两个顶点连成对偶图中的一条边。可以证明，平面图的对偶图也是一 个平面图，而且一个图的对偶图的对偶图是它自身。给定个平面图岔如果找不到 另外一个平面图g ，g 是g f 的展开子图，那么称图口是一个极大平面图。可以 证明，一个极大平面图的所有区域都由三条边围成。因此极大平面图也称为三角化的 平面图。 2 4 遍历算法 一个图中的顶点也能够排序和编号。比如，我们可以遍历一个图的所有顶点，然 后按照遍历的先后对图中的所有顶点排序。常见的遍历算法有广度优先遍历 ( b r e a d t h 干f 灌tt r a v e r s e ) 算法和深度优先遍历( d e p 拍下f 瑙tt r a v e r s e ) 算法。 对于一个连通图，广度优先算法遍历的过程如下： 1 从图中任选一个顶点，放入一个等待遍历的顶点队列口中。 2 重复下面的步骤直到顶点队列p 为空： 2 1 取出顶点队列口的第一个元素，记为“ 2 2 如果顶点y 没有遍历过，那么； 2 2 1 标记顶点p 为“已经遍历”。 2 2 2 将t t d i ( v ) 中的顶点逐个放入顶点队列口中。 深度优先算法和广度优先算法的遍历过程几乎相同，唯一的差别是：在深度优 先的算法中用一个顶点堆栈s 代替广度优先算法的顶点队列仉对于非连通的图， 我们可以对它的每一个分支用深度优先或者广度优先的算法分别遍历。在设计广度 优先和深度优先遍历算法的时候还有两个自由度：一个是初始顶点的选择，另外一 个是a a j 0 , ) 中顶点的顺序。在遍历平面图的时候，4 西( v ) 中的顶点往往按照固定 的逆时针，或者顺时针顺序排列。 2 5 编码表示 一个图通常表示为一个边的链表，而每一条边又描述为两个顶点的下标。假设图 中一共有 r 个顶点，那么表示一个顶点下标需要g ( ) 1 个比特。所以表示一条边 8 硕士论文 三维几何网格模型压缩算法的伊究 需要2 l o g ( n ) 个比特。通过三角化平面图可以证明，一个具有个顶点的平面图最 多包含2 n - 4 个区域，3 n 一6 条边。因此，表示一个平面图最多需要2 n ( 3 n 一6 ) l o g ( n ) 个比特。 t u r a n 证明，任何一个具有 ，个顶点的平面图都可以用少于1 2 n 个比特进行 编码。在这以前的方法中，顶点的平均比特数都是l 0 9 2 ( 聊的倍数。而在t u r a n 这 个结果中，顶点平均比特数是一个常数，明显优于前人的方法，尤其是当网格顶点数 很大的时候。t u r a n 的方法是用构造顶点展开树，并且用它来表示拓扑结构多边形。 一方面顶点展开树有2 n 一2 条边，可用4 一4 个比特进行编码。另一方面至多有 2 n 一5 条边不属于顶点展开树，对于每一条这样的边可以用4 个比特编码。因此， 编码总共需要1 2 n 一2 4 个比特。下面对t u r a n 的编码方法做一个简要的介绍。 8 图2 3t u t a n 平面图编码实例( a ) 是一个具有s 个顶点的平面图g ，图的顶点分别标号为i 8 ， 圈中的粗线所表示的子图是该平面图的一个展开树，它的根为顶点1 ( b ) 沿着展开树的边将原平面 图剪开，得到个导出圈g 该导出圈的每个顶点都有两个标号，第一个标号是该顶点在原图中 的标号，第二个标号是该顶点在导出图中是第几次出现 设g 是一个平面图，且不妨假设f 是连通的。，是g 的一个展开树，的根 顶点是婚。从巧出发以深度优先的顺序遍历展开树兀遍历时候确定了一个长为 2 n 一3 的循环顶点链表。该链表中相继两个顶点都构成图丁的一个边，共计2 n 一2 条边而且，的每一条边都出现两次。如图所示的例子中，遍历产生的顶点序列为 1 ， 2 ，3 ，2 ，4 ，2 ，l ，5 ，6 ，7 ，8 ，7 ，5 ) 。沿着多边形把原图剪开，导出一个新图g ， 如图2 3 所示。前面的循环顶点序列对应于导出图g 的边界多边形 l ( 1 ) ，2 ( 1 ) ， 3 ( 1 ) ，2 ( 2 ) ，4 ( 2 ) ，2 ( 3 ) ，1 ( 2 ) ，5 ( 1 ) ，6 ( 1 ) ，7 ( 1 ) ，8 ( 1 ) ，7 ( 2 ) ，5 ( 2 ) 。t u r a n 采 用四个符号 + ，、c ) 对平面图口进行编码。具体方法如下： 9 硕士论文 三维几何网格模型压缩算法的研究 从顶点1 ( 1 ) 出发，遍历g 的边界多边形上的顶点和边。对每一个访问中的边 k ，) ，如果在展开树，上k 的深度大于的深度，那么将其编码为“+ ”，否 则将其编码为“一”。如果在g 中还有内部边入射到顶点，那么按照逆时针的顺 序遍历这些内部边。对每一条内部边“，v c ) ，如果圪是一个没有遍历过的顶点，那 么将其编码为“( ”，否则将其编码为“) ”对于图1 - 3 中的例子，t u r a n 的编码 结果是： + + c c - + ( ( 卜+ ) + ) ) ( - + 卜) 一- ) 一 值得注意的是，g 中的每一条内部边都编码两次。在图占的导出图g 中的边 界多边形的边的个数为2 n 一2 ，内部边最多有( 3 一6 ) 一( 一1 ) = 2 n 一5 。而上述的每一 个符号都需要两个比特，因此t u r a n 的编码最多需要 2 x c 2 x c 2 n 一5 ) + ( 一1 ) ) = 1 2 n 一2 4 1 2 n 个比特。t u r a n 方法可以用来对任意的平面图编 码。如果将其应用到三角化的网格上，那么编码的结果大概相当于6 ( 比特三角形) 1 0 硕士论文三维几何羁培模型压缩算法的研究 3 几何压缩 3 1 几何压缩的概述 几何压缩在计算机图形学应用范围日益扩大，作用日益增加的同时，人们对计算 机图形合成质量也在不断地提出新的要求。但是要合成高质量的画面，往往需要有足 够精细的几何模型。因此在计算机图形学的许多应用中使用的三维几何数据的数量和 复杂不断地急剧增长着。新的造型工具和模型重建技术的出现也促成了这一发展趋 势。如何实时有效地处理这些日益增多和日渐复杂的三维几何数据成为计算机图形学 发展中的一个巨大挑战。再者，随着网络图形学的发展，越来越多地需要通过网络， 特别是国际互联网，来存取那些贮放在异地的三维几何数据。这些日益增多和日渐复 杂的三维几何数据也使得本以十分有限的网络带宽带变得更加的紧张。 总之，计算机图形学应用的特点之一是广泛地使用三维几何数据。而且随着计算 机图形学及其相关理论和技术的快速发展，这些在数量规模和复杂程度还在日益增长 三维几何数据在不断满足需求的同时，也给我们带来了许多问题和巨大挑战，概括的 讲包括以下三个方面的内容： 图形适配器因为没有足够的内存完全装栽巨大的模型，或者受限于数据传 输瓶颈而不充分地能够发挥其图形处理的性能。 在三维c a d 系统中的模型变得越来越复杂，大大地增加了处理这些模型 的所需的内存代价和辅助外存的代价。 如今的许多应用，如协同设计( c o l l a b o r a t i v ed e s i g n ) 、网络游戏、快 速成型、虚拟交互等等，都需要发布传输三维的几何模型。但是现有的网 络带宽严重限制和阻碍7 这些发布传输。 为了解决上述的这些问题，我们可以通过升级和提高图形处理的性能，增加网络 带宽等硬件方面的办法来解决。但是仅仅这样是不够的，还需要软件算法方面措施， 如： 在下载和绘制几何模型的时候，选择性的处理那些潜在可见的部分。 在适当的时候使用图像代替复杂的几何模型。 对远距离处的物体使用多分辨率的、简化的几何模型，当几何物体慢慢的 走进的时候，渐进式的细化地分辨率的几何细节。 使用几何压缩方法，设计几何模型的紧致表示，减少它的存储空间和传输 时间，使得它适合于利用硬件进行快速绘制。 硕士论文 三维几何舟恪模型压缩算法的研究 人们已经在上面的这些方向上作了许多的工作，如基于图像的建模和绘制方法 ( i m a g eb a s e dm o d e l i n ga n dr e n d e r i n g ) 、层次细节方法( l e v e lo fd e t a l l ) 和几 何压缩( g e o m e t r yc o m p r e s s i o n ) 等等。 几何压缩是计算机图形学中一个新兴的研究方向。最早的关于几何压缩方面的工 作可以追溯到1 9 9 5 年m 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 的研究论 文。m d e e r i n g 几何压缩方法的目的是压缩几何数据，减少c p u 和图形卡之 间的数据传输，从而加快图形处理的速度。在该方法中引入了一个网格缓存器，用来 存储1 6 个曾经使用过的旧顶点。然后通过重用网格缓存中的旧顶点来减少需要传输的 顶点数据。同时对需要的传送的顶点几何数据进行量化和增量编码进行压缩。在此之 后人们开始关注几何压缩问题，并且做了大量的杰出工作。这些方法目的也从加速绘 制扩展到减少存储，方便网络传输等方面 与几何压缩密切相关的一个领域是数据压缩。在数字信息理论和数字通信技术 的发展过程中，人们为保存获取的数据资料研究了各种各样的压缩编码方法，尤其 是对图像和视频数据。它们大致可以分为： ( 1 ) 预测法：通常指的是线性预测法，其中最常用的是差值脉冲编码调制法 ( d p c m ) 、增量调制法( a f ) 。此外还有非线性预测法。 ( 2 ) 变换法：即正交变换法，通常采用的正交变换有f o u r i e r 变换、 w a l s h - h a d a m a r d 变换、h a a r 变换、s 1 a n t 变换( 斜变换) c o s i n e 变换 ( 余弦变换) 、s i n e 变换( 正弦变换) h o t e l l i n g 变换( 即离散的 k a r h u n e n - l o e v e 变换) 等等。 ( 3 ) 平均信息法：有熵编码法和利用消隐时间法等。常用的熵编码法有 h u f f m a n 编码、算术编码、线性码、对数码等等。 ( 4 ) 内插法：有低抽样率法( s u b n y q u i s ts a m p l i n g ) 、亚抽样法 ( s u b s a m p l i n g ) 、亚行法( s u b l i n e ) 、亚场法( s u b f i e l d ) 、压帧法 ( s u b - f r 鲫e ) 等等。 ( 5 ) 运动补偿法( m o t i o nc o m p e n s a t i o n ) z 这是针对运动图像中运动景物采 取的帧间编码方法。主要有运动补偿内插法和位移估值法( d i s p l a c e m e n t e s t i m a t i o n ) 。而后者包括块匹配法( b l o c km a t c h i n g ) 和像素递归法 ( p i x e lr e c u r s i v e ) 。 此外还有一些其它编码方法，包括：方块截尾编码法( b l o c kt r u n c a t i o n 硕士论文三维几何网格模塑压缩算法的研究 c o d i n g ) 、矢量量化法( v e c t o ro u a n t i z a t i o n ) 、综合高频法( s y n t h e t i c - h i g h ) 、 游程编码法( r u nl e n g t hc o d i n g ) 、轮廓编码法( c o n t o u rc o d i n g ) 等等。这些压 缩编码方法大多数都应用在图像处理之中，我们不再做进一步阐述。 3 2 基于字典技术的无损编码技术 3 2 1 游程编码 最简单的基于字典技术的压缩技术是游程编码( r l e ：r u nl e n g t he n c o d i n g ) 。 在那些由很少几个符号组成的消息中，经常连续出现一些相同的符号。那些连续出 现的相同符号组成的序列，称为一个游程。表示一个游程只需要记录游程中的符号 编码和该游程的长度就足够了这就是游程编码的基本思想。如果一个消息中的游 程数目越少，游程长度越长，那么游程编码的效率越高。反之，游程数目越多，游 程长度越短，那么游程编码的效率越低。 3 2 2l z w 编码 l z 编码是由l e m p l e 和z i w 最早提出来的无损压缩技术m “1 它由t a w e l c h 加以充实而形成了应用广泛的受专利保护的l 珊算法。与游程编码类似， 它也是对字符串进行编码从而实现压缩。然而与游程编码不同的是，它在对文件进 行编码的同时，声明了一些特定的字符串表以及它们对应的编码每当字符串表中 没有的字符串第一次出现的时候，它就被原样地保存起来，同时将给它分配一个代 码。之后当这个字符串再次出现的时候，将只保存上次分配给它的代码。这样实现 减少文件中的冗余信息。在l z w 算法中，不但字符串表是在压缩过程中动态生成 的，而且字符串表也不必保存在最终的压缩文件中。因为在解压缩的过程中可以重 构它们。 3 3 信息论和熵编码 熵( e n t r o p y ) 是信息论( i n f o r m a t i o nt h e o r y ) 中最基本概念之一，用来衡量 一条消息( m e s s a g e ) 中有多少组织规律或冗余信息。如果消息中有很多的规律性东 西，那么它的熵数小；反之如果消息呈现高度杂乱无章性，那么它的熵数大。在理想 的情况下，一条消息编码后的长度应该等于它的熵，因此熵和数据压缩的关系十分密 1 3 硕士论文 三维几何网格模型压缩算法的研究 切。然而熵的度量也具有不确定性，因为它依赖于对消息中可能出现符号( s y m b 0 1 ) 的所估计的概率分布函数。 假设一条消息由一组可能出现的符号 西i1 = 0 ，1 ，2 ， l 1 ) 组成， 符号自出现的概率为p ( o ，所有符号的概率和为1 ，即：，( 毋) 。i 。这条消息的 熵描述了该消息出现时平均有多少种可能的选择，或者该消息出现时有多少不确定的 因素。s h a n n o n 在他开创信息论的研究工作中指出，熵必须满足以下三个条件： 熵是符号概率p ( 彩的连续函数。 如果每一个符号具有相同的出现概率，那么熵是符号个数 ，的一个单调 递增函数。 如果可以分阶段地选择消息中的符号，那么消息的熵应该是各个阶段熵 加权之和，权值为相应阶段的概率。 s h a n n o n 证明，满足上述条件的熵函数是唯一的，即： e ( q ，4 i ，口) = p ( 岛) l o g ( p ( q ) ) j i i 其中，k 是一个与熵单位相关的正比例常数。通常熵的单位是位( 比特数) ，于是 i = 1 ，而且上式中的对数底数为2 。很容易知道，熵总是非负的数值，而且当所有 的符号出现的几率都相等时，熵取得最大值。 设有一个由7 个符号组成的消息肛。是第k 个符号在肜中出现的次数。那 么消息埘的熵为： e ) = 一i m 哮南l o g ( 却 其中，j 矧表示消息中包含的符号个数。 熵编码通常指根据熵的一些基本原理将消息转化为一串二进制码的过程。按照 某种编码方法编码后仍留在消息中的冗余量，等于该编码的平均码长与熵之间的 差，即： r = e 工 ，( 吼) 一以q ，q ”，口) 其中，( 匐用来代表符号m 韵码字长度( 以位为单位) 。如果某种编码方法产生 的平均字长等于消息的熵，那么它必定除去了所有冗余的信息。这也是可以实现的， 只要我们能够设计一种编码，使得符号岛的编码字长为： 1 4 硕士论文 三维几何同格模型压缩算法的研究 k c a d = 一l o g ( r ( a d ) 这个公式指出了平均字长的下限对于二迸制编码来说，只有当所有的符号的几率 均为2 的负整数次幂的时候，例如0 5 、0 2 5 、 、等，才能够达到这个水平。 下面我们简单地介绍三种常见的熵编码方法：s h a n n o n - f a n o - e l i a s 编码、 h u f f m a n 编码和算术编码。 3 3 is h a n n o n - f a n o - e l i a s 编码 s h a n n o n 和f a n o 差不多是在相同时间各自独立地发现了这个利用概率进行编 码的方法，该方法的具体编码过程如下： 把所有符号按照它们概率的递增顺序排列。 把它们分组为概率几乎相同的两个部分。 为第一组中的符号的编码分配一个0 ，为第二组中的符号的编码分配一 个1 。 递归处理这两组符号，直到每一小组指包含一个符号为止。 可以证明，s h a n n o n - f a n o - e l i a s 编码的平均码长位于区间暇，日+ l l 之中，其 中是消息的熵。但是在s h a n n o n - f a n o - e l i a s 编码方法中，有可能为一个大概率符 号产生一个比小概率还要长的编码。显然，在这种情况下我们只要交换这两个符号的 编码辑可获得更好的压缩效果。因此s h a n n o n - f a n o - e l i a s 编码并不是最好的编码策 略。 硕士论文三维几何网格模型压缩算法的研究 3 3 2h u f f m a n 编码 0 1 50 1o 0 8o 0 9o 3o 2 8 图3 1i - - h t h m 编码树每一个符号在圈中都对应于树上的一个节点，符号的概率标注在相 应节点下方，符号的编码标注在相应节点右侧 e u f f m a n 编码利用消息中符号的概率分布，h u f f m a n 发现了一个更好的压缩编 码方法。具体是： 依次排列所有的符号。 找到概率最小的两个符号 将这两个符号合并为一个复合符号，其概率为两个符号的概率之和。 重复上述过程，直至剩下一个符号为止。 如图3 1 所示，上述过程可以用一棵二叉树来表达。二叉树上叶节点是消息中 的符号，中间节点是复合符号根据则棵树可以很容易得给各个符号编码。从树的根 节点到树的每一个叶节点都有一条唯一的路径，这条路经可以用一串二进制码来表 示：0 表示走节点的左子树，1 表示走节点的右子树。到达树的叶节点时候所得到的 路径码就是对应符号的h u f f m a n 编码。 h u f f m a n 编码方法还可以采用自适应模型，根据已经编码的符号频率决定下一个 符号的编码。这时，我们无需为解压缩预先保存任何信息，整个编码是在压缩和解压 缩过程中动态创建的，而且自适应编码由于其符号频率是根据信息内容的交化动态得 到的，更符合符号的局部分布规律，因此在压缩效果上比静态模型好许多。但是，采 用自适应模型必须考虑编码表的动态特性，即编码表必须可以随时更新以适应符号频 率的变化。对于h u f f m a n 编码来说，我们很难建立能够随时可快速更新的二叉树， 所以使用标准h u f f m a n 编码仍是个不错的选择。 h u f f m a n 编码的特点是赋予大概率消息以较短的编码，而赋予小概率消息以较长 的编码。可以证明，在给定消息的概率分布的情况下，l t u f f m a n 编码冗余信息最少， 1 6 硕士论文三维几何同格模型压缩算法的研究 消息平均码长最短。在这个意义上我们说h u f f m a n 编码是最优的。但是实际的情况 并非如此，其中的原因是每一个消息的h u f f m a n 编码都需要整数个比特。假设消息 中某个符号的出现概率为9 0 ，根据熵理论该消息只需要一l 0 9 2 ( o 9 ) - - 0 1 5 2 ( 位) 比 特来编码，但在h u f f m a n 编码中分配给它的编码一定会是一位0 或一位l 。于是， 整个信息的9 0 5 在压缩后几乎相当于理想长度的1 1 0 1 5 2 = 6 6 7 倍左右，其中的冗余 数据可想而知。 3 3 3 算术编码( a r i t h m e t i cc o d i n g ) 和l t u f f m a n 编码方法相比较，虽然算术编码的方法比较难懂一些，但是它的基 本思想并不复杂。可是这样的一个优秀、有用的编码方法直到7 0 年代才被人们发现， 到8 0 年代受到人们的重视。 在算术编码方法中，任何一条消息都被表示为0 到1 之间的一个实数区间。消 息越长，这个区间越小