（计算机应用技术专业论文）三维网格压缩.pdf

摘要 ! ! 曼曼曼! ! ! 舅! 苎! ! 曼曼曼曼! ! ! ! ! ! ! 皇詈i i i 一= = ；= i 一一 一 = i 曼曼曼! 皇! ! 曼曼曼曼皇 摘要 随着计算机科学技术的发展，人们对于信息表达需求不再局限于文字、音频、 图像以及视频这些表现形式，人们需要更加丰富的信息，更加自由的交互。而计 算机三维图形学领域相关研究的发展以及相关硬件技术的成熟使得三维模型开 始出现在诸多应用领域中。随着技术的进步，三维扫描设备的精度不断提高，获 得的三维模型的精度也越来越高，相对应存储模型所需要的空间也越来越大，受 时间空间以及带宽的制约，如何高效地将三维模型的数据进行压缩，以便于储存 和传输，成为一个急需解决的问题。 在这篇文章中提出了一种新的基于二叉树结构的几何驱动渐进压缩算法。该 方法通过构造一棵与网格几何信息相对应的二叉树，然后对其进行压缩，以实现 对网格几何信息的压缩，在压缩连接信息的过程中利用渐近网格压缩中的边消除 操作对网格的连接信息进行压缩。该方法对几何信息压缩位率为平均1 3 6 3 1 比 特每顶点，对连接信息的压缩位率为平均8 0 2 2 比特每顶点，在压缩性能方面优 于一些经典的传统算法。此外该方法很容易推广到任意拓扑性质的三角网格，甚 至是多边形网格的压缩上。 此外本文还提出了一种利用三维h i i b e r t 曲线压缩网格几何信息的方法，并 取得了不错的压缩效果。该方法的思路可以与基于二叉树的几何驱动压缩算法进 行组合，也可用于体素模型等其他三维模型的几何信息压缩。 最后本文还对三维网格压缩的进一步发展方向进行了讨论。 关键词网格；几何压缩；二叉树；渐进压缩；h i l b e r t 曲线 a b s t r a c t a b s t r a c t 、斩t ht h ed e v e l o p m e n to fc o m p u t e rs c i e n c ea n dt e c h n o l o g y , t oc o m m u n i c a t ew i t h t e x t ，s o u n d ，i m a g e ，v i d e o c a nn o tf i t p e o p l e sr e q u i r e m e n t i tr e q u i r e s c o m m u n i c a t i o nb em o r ea n dm o r ef r e e l ya n d r i c ho fi n f o r m a t i o n t h ed e v e l o p m e n to f t h er e s e a r c ha n ds t u d yo ft h et h r e e d i m e n s i o n a l ( 3 d ) c o m p u t e rg r a p h i c sa n dt h e m a t u r a t i o no fr e l a t e dh a r d w a r et e c h n o l o g i e sl e a dt h e3 dm o d e l sb e c o m ew i d e l yu s e d i nm o r ea n dm o r ef i e l d s w i t h a d v a n c e si n t e c h n o l o g y , t h ea c c u r a c y o f t h r e e d i m e n s i o n a ls c a n n i n gd e v i c ec o n t i n u o u s l yi m p r o v e ，a n dt h e3 dm o d e l sb e c o m e b i g g e ra n dm o r ea c c u r a t e ，a n dh o w t oc o m p r e s st h em o d e l se f f i c i e n t l yt of i tt h el i m i t s o ft i m e ，s t o r a g ea n db a n d w i d t hb e c o m ea ni s s u e i nt h i sp a p e r , w ep r o p o s e dap r o g r e s s i v eg e o m e t r y - d r i v e n3 dt r i a n g l em e s h e s a l g o r i t h mw h i c hi sb a s e do nt h eb i n a r y t r e es t r u c t u r e i tf i r s tt r a n s f o r mt h eg e o m e t r y o fm e s hi n t oab i n a r y t r e ea n dt h e nc o m p r e s si t ，a tt h es a m et i m ei t u s et h ee d g e c o l l a p s ep r o p o s e di np r o g r e s s i v em e s ht oc o m p r e s s t h ec o n n e c t i v i t yo fm e s h i t c o m p r e s st h eg e o m e t r yo n 13 6 31b p va v e r a g e l y , a n dc o n n e c t i v i t yo n8 0 2 2 b p v a v e r a g e l y , i ts h o w sab e t t e rp e r f o r m a n c et h a ns o m ec l a s s i c a la l g o r i t h m sw h i c hh a v e b e e np r o p o s e d ，a n dc a nb ee a s i l ye x t e n d e dt on o n m a n i f o l dm e s hc o m p r e s s i o na n d p o l y g o nm e s hc o m p r e s s i o n w ep r o p o s e dam e t h o dt oc o m p r e s st h eg e o m e t r yo fm e s hb y3 dh i l b e r tc u r v e ， a n di ts h o w sag o o dp e r f o r m a n c eo nt h ec o m p r e s s i o n t h i sm e t h o dc a nu s ei nt h e a l g o r i t h ma b o v ea st h en u m b e r i n gf u n c t i o n ，a n dc a na l s ob eu s e di nt h ec o m p r e s s i o n o ft h eg e o m e t r yo fo t h e rt y p e s3 dm o d e l s a tl a s t ，s o m ef u t u r er e s e a r c hd i r e c t i o n so f3 dm e s hc o d i n ga r ep r o p o s e d k e y w o r d sm e s h ；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 ec o m p r e s s i o n ；h i l b e r tc u r v e 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名： 关于论文使用授权的说明 日期：掣吆 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名。样导师签名：砻j 啦日期：垒学上巫 第1 帝绪论 i ii| 第1 章绪论 1 1 研究意义和内容 随着计算机科学技术的发展，人们对于信息表达需求不再局限于文字、音频、 图像以及视频这些表现形式，人们需要更加丰富的信息，更加自由的交互。而计 算机三维图形学领域相关研究的发展以及相关硬件技术的成熟使得三维模型开 始出现在诸多应用领域中。 在医学领域，通过x 光或核磁共振等成像技术，可以构建出病人的血管，内 脏等器官的三维模型，由此医生可以更加直观的诊断病情；在工业设计领域，成 熟的c a d 技术将人们从繁琐的手工画图作业中解放出来，不但降低了成本，也使 得设计工作更加高效。在文化领域，精美的三维模型和动画，也极大丰富了人们 的想象力，并给人们以极大的视觉冲击力。与网络技术的结合，使得人们足不出 户，也可以有身临其境的感觉。 随着技术的进步，三维扫描设备的精度不断提高，借助c a d 技术产生的三维 模型的复杂程度不断提升，得到的三维模型原始数据的数据量也成倍的上升。网 络技术的发展和互联网技术的广泛普及，使得人们可以从互联网上方便地获得很 多高分辨率的三维网格，甚至可以与这些模型进行在线的实时互动。可是受时间 空间以及带宽的制约，如何高效地将三维模型的数据进行压缩，以便于储存和传 输，便成为一个亟待解决的问题，而这也是数字几何处理( d i g i t a lg e o m e t r y p r o c e s s ) 中的一个重要课题。 1 2 相关背景 1 2 1 三维模型数据的组织形式 出于对三维物体不同的理解方式，三维模型数据的组织形式也各有不同，如 点云模型( p o i n tc o u l dm o d e l ) ，网格模型( m e s hm o d e l ) 等。 点云模型通过定义一组浓密的点集来描述三维物体。其数据主要记录采样点 的三维坐标信息，法向方向以及采样点的颜色、反射率、材质等属性信息。点云 模型的数据压缩主要是将注意力放在对采样点几何信息的压缩。 网格模型通过定义三维物体表面的点，边，面描述三维物体。其中，采样点 在空间的三维坐标信息，这些信息用于描述采样点的空间位置，决定模型大致的 几何形状，被称为几何信息( g e o m e t r yd a t a ) 。边与血用于描述采样点之f h j 的邻 接关系，被称为连接信息( c o n n e c t i v i t yd a t a ) ，很多文献中也被称其为拓扑信 北康t 业、。t 掌1 学位论义 息( t o p o l o g yd a t a ) 。此外每个面的纹理，材质等属性，被称为属性信息( p r o p e r t y d a t a ) 。 网格模型依照面的形状的不同，可分为三角形网格( t r i a n g l em e s h ) 和多 边形网格( p o l y g o nm e s h ) 。型如其名，三角形网格的每个面由三角形组成，而 多边形网格的面由多边形构成，并非单一的三角形。不过多边形网格可以通过加 边的方式，转化为三角形网格，三角形网格是一种非常通用的网格数据表述方式， 而且三角形网格模型被绝大多数的绘制算法与硬件所支持n 、1 。因此众多的网格 压缩算法中，绝大多数的算法为针对三角形网格的压缩算法。出于同样的理由， 本文中提及算法的研究对象也主要放在三角网格模型上。下图展示了一个三角网 格： 图i - i 三角形网格 f i g 1 1at r i a n g l em e s h 1 2 2 三角形网格的数据存储格式 一个三角形网格由一组三角形拼接而成，其数据结构可用一个顶点数组 v e r t i c e s 和一个三角形数组t r i a n g l e s 来描述： ：f l o a t v x ，y ，z ：i n t f v 0 ，v 1 ，v 2 这两个数组均为二维数组，其中v e r t i c e s 数组中的每一行的三个分量x ，y ， z 用于表示顶点的三个坐标分量，每个三角形由它的三个顶点确定，v o ，v l ，v 2 为这三个顶点在顶点数组v e r t i c e s 中的索引。v ，f 分别为网格顶点数与三角彤 数。标准的v r m l 砸1 文件使用的便是这干叶，存储方式。同样的，在科研中常见的p l y ， o f f 等格式的文件也是按照这种方式存储数据的。此外，网格所包含的属性信启、， 包括描述顶点的法向、颜色、纹理q ! 切；等。法向、纹理坐标等属性可以用与顶点 坐标类似的方式进行压缩。因此本文后面将主要研究i 角形网格的连接信启、和几 1 j qu oj 1 j r l v 1 j fl t r l a t o n 1 i 1 f s s e e 1 c g 1 n t a r l 1 e r v t 织1 章纬论 何信息的压缩。 1 2 3 压缩编码 对三角形网格数据的压缩在流程上可大体分为两个过程。首先是变换，其次 是编码。从理论上讲，即使不进行任何变换也是可以进行编码的，不过由于三角 形网格模型数据中存在着大量的冗余信息，为了实现高效的压缩效率，对数据进 行适当的变换以降低冗余是必不可少的步骤。而这也是决定压缩效率魄关键。完 成对数据的变换后，为了进一步提升数据的压缩效率，还要对变换后的数据进行 进一步的压缩，通常在这一步会采用无损的通用数据压缩算法。而常用的算法有 熵编码的h u f f m a n 编码，算数编码以及字典压缩算法的l z 7 7 ，l z w 等算法。h u f f m a n 编码事被理论证明的熵最小编码，算术编码通过构造映射将任意序列同 0 ，1 区间上的一个实数一一对应，从而实现较高的压缩效率，是使用最为广泛的熵编 码技术。可以说在编码这一个环节上，很难比较出优劣。因此性能比较的关键也 就主要集中在变换的过程上。 1 3 本文主要研究内容 本文主要研究的是三维网格的数据压缩，由于基于拓扑驱动的工作已经接近 理论的极限，因此主要研究的是基于几何驱动的网格压缩算法，除了追求较高的 数据压缩性能外，还力求使得算法可以适用于网络传输和交互。最后，作者讨论 了网格压缩的进一步研究方向。 1 4 本文组织结构 本文组织结构如下： 第1 章绪论简单地介绍了本课题的研究背景，意义，背景知识，并介绍了 本文的研究内容和本文组织结构 第2 章三角网格压缩技术综述从三个方面较为系统地介绍了现有的各种 压缩技术。 第3 章基于二又树结构的三角网格渐进式压缩提出一种新的基于几何驱 动的三角网格压缩算法，并对该方法的性能进行了分析试验，并讨 论了垓方法的适朋性，陔方法很容易推广一到多边形网格以及非流彤 网格的压缩。 北京l 业人亨二t 掌坝i 辱：1 一论文 第4 章基于h i i b e r t 曲线的几何信息压缩提出了一种新的对三维几何信息 进行压缩的方法，该方法可以适用于任何类型的三维模型。并且作 为一种编码方式可以与第3 章的算法相结合。 结论部分对本文的主要工作和创新进行了总结，并介绍了本领域以及本课题 今后的研究方向和工作的重点。主要包括利用预测技术降低拓扑信息的压缩 位率，设计与h ii b e r t 编码相匹配的高效拓扑信息压缩算法等。 筇2 章三角h 晰f i 缩手上术综述 第2 章三角网格压缩技术综述 同以往的数字信号处理的对象不同，三维网格压缩处理的对象并非采样点上 的振幅，颜色，能量等信息。而是要对采样点本身以及其邻接关系进行处理。而 且由于网格不规则的任意性，对其的采样也是不规则的，这就使得一些经典的数 字信号处理技术不能直接应用在三维网格压缩上，同时也成就了一批新的方法出 现在三维网格压缩领域中。 这些方法可以大体分成两类：单一位率压缩( 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 ec o m p r e s s i o n ) 。单一位率压缩也即静态压缩，要求用户 需要接收到压缩后的全部数据后才对其进行解码的工作，目的是为了得到更高的 压缩比，以节省存储空间，减少数据在网络上传输所需要的时间。渐进式压缩则 是出于减少交互的等待时间的目的，先传输并显示一个有着和原网格形似但缺少 细节的基网格，待用户接收完成基网格后，便可开始进行交互，在交互的同时传 输网格的细节信息，不断丰富网格的细节。 然而无论是单一位率压缩还是渐进压缩，都要考虑如何压缩网格的连接信息 和几何信息。基于不同的出发点，这些方法又可分为两大类：基于拓扑驱动的压 缩和基于几何驱动的压缩。单一位率压缩的绝大部分方法都方法都是基于拓扑驱 动的压缩。 2 1 基于拓扑驱动的单一位率压缩 这类方法通常先对连接信息( 拓扑信息) 进行编码，这类方法通常是按照某 种事先约定好的遍历方法对网格进行遍历，将遍历时遇到的不同情形用符号序列 进行记录，待遍历完成后，将该符号序列进行编码，以实现对连接信息的压缩。 在遍历过程中，算法还会记录遇到顶点的次序，依次各个顶点的坐标进行编码。 2 1 1 三角条带法( t ria n g ies trip ) 该方法试图将三维网格分解为一系列的长的三角条带，然后对这些条带再进 行编码。其主要的意图在于减少c p u 和显卡问的数据传输量。因为对于绝大多数 的显卡，三角条带都足被支持的。不过这种方法虽然节省了空问，减轻了系统带 宽的负荷，从压缩的性能来说并非十分有效。 北京t 、i k ：学t 学顺l 学f 一论文 a v l v 3v 5v 7 刍 屹飞y ly 2v o 屹 图2 1 三角条带 f i g 2 一iat r i a n g l es t r i p 上图2 - 1 的a 中，每个顶点通过和顶点序列中前两个顶点构成一个三角形。 b 中，每个顶点通过和顶点序列中前一个顶点以及第一个顶点构成一个三角形。 c 则是a ，b 情况的混合，被称为广义三角条带( g e n e r a l i z e dt r i a n g l es t r i p ) 。 可以看出除去第一个三角形需要由三个顶点确定外。其余的三角形只需要有一个 顶点便可确定。这比索引面中每个面由三个点确定已经是一个不小的进步的。特 别当三角形条带很长的时候基本上一个三角形就可用一个点的索引的确定。不过 根据拓扑学的欧拉公式，在一个三角网格中，面的数量大约是点的两倍。因此用 三角条带来表示三角网格必然有很多点的索引会重复使用。而索引的储存所需的 开销是很大的。 d e e r i n g 口3 最先提出了广义三角条带这一概念。他利用一个先进先出( f i f o ) 的顶点缓存记录最近访问过的1 6 个顶点索引。如果一个顶点位于缓存中，则它 可以利用它在缓存中的索引来记录，而这样通常来讲会比全局索引所需要的位少 一些。不过d e e r i n g 并未提出一个很好的办法将网格分解为广义三角条带。基于 d e e r i n g 的工作，c h o w 聃1 提出了一个有效将网格分解为广义三角条带的方法。使 得缓存的中的点尽可能地被复用。使得压缩效率得到提高。 三角条带可用于具有任意拓扑结构的三角网格，但是只有在网格可以被分解 为很长的条带时才能体现出比较高的压缩效率。该方法对几何信息压缩时使用的 是预测编码技术。 2 1 2 生成树法( s p a n nin gt r e e ) t u r a n 发现一个平坦图的连接信息码的是可以通过利用两棵生成树( 一棵顶 点生成树，一棵面生成树) 以一个常位率进行编码。基于这一思路t a u b i n 和 r o s s i g n a c 提出了拓扑手术方法( t o p o i o g i c a ls u r g e r y ) 对网格的连接信息进 行编码。这一方法的基本思路将别格按照项点生成树切分成个平坦的网格，然 和产生陔刚格的面生成树，之后对其进行压缩。 讲2 甲一加州f ”而坎术练述 i | i ii ilq_ t a u b i n 和r o s s i g n a c 阳1 之后又对他们的算法进行了改进，使得其算法可以适 应于任意的流形网格，不过他们算法还是不能直接应于非流形网格，需要将非流 形网格进行切分为若干子流形网格才可应用。在实验效果上，该算法对网格拓扑 信息的压缩效率大约为2 4 8 7 o b p v 。时间和空间复杂度也均是线性级的。不过 这个方法在解压时需要一个容量很大缓存用于全局的顶点访问。t a u b i n 和 r o s s i g n a c 的拓扑手术方法是m p e g 4s n h c 中的几何编码标准以及v r m l 数据压缩 标准的基础。 2 1 3 层分解法( l a y e r e dd e c o m p o sitio n ) 这种方法由b a j a j n 们提出，其基本思想是将网格分解为一系列的同心顶点层。 利用相邻的顶点层构造三角形层。通过顶点层的层数，每一顶点层的布局以及每 个三角形层的布局来描述网格的拓扑信息。此方法的对拓扑信息的压缩效率大约 为1 4 0 6 0 8 b p v 。 2 1 4 基于遍历的连接信息编码方法 这是一大类方法，可大致分为基于面、基于边和基于点的方法三类。 基于面的方法有e d g e b r e a k e r 1 、c u t - b o r d e r n 2 等。 基于边的方法主要有f a c ef i x e r 等。 基于点的方法有t g 方法n 3 1 ，a 1 l i e za n dd e s b r u n n 4 3 提出方法等。 r o s s i g n a c 的e d g e b r e a k e r 方法和g u m h o l d 和s t r a s s e r 的c u t b o r d e r 方法。 大体思路一样。均是对三角形的面进行遍历。针对遍历时的不同情况设计了一组 操作码集，遍历后得到一组操作码序列，之后对这组操作码进行编码。 e d g e b r e a k e r 中提供了5 种操作码：c ( c e n t e r ) ，l ( l e f t ) ，r ( r i g h t ) ，s ( s p l i t ) ，e ( e n d ) 当从一条边访问一个新的三角形的时候，将记录一个c ，并 记录孩三角形已经被访问过。其他的情况将根据左右两个相邻三角形被访问情 况，分别输出l ，r ，s ，e 等四个符号中的一个，标记该三角形为己访问，并采 取相应的下一个操作：访问右边，访问左边，分又或结束。通常情况下这5 种符 号的概率分布很不均衡，c 的分布率基本在0 5 左右。这也是e d g e b r e a k e r 能够 高效的一个重要原因。存最坏的情况下，这种方法可以得到4 b p v 的压缩比。不 过这方法不适用流处理，解压时的复杂度是平方级的。下图2 - 2 给出了一个遍 历的示意： 北京t 业j ：学t 学顺i 学位论文 ( 0 ( i )( m ) 图2 2e d g eb r e a k e r f i g 2 - 2e d g eb r e a k e r k i n g n 胡和r o s s i g n a c n 印改进了e d g e b r e a k e r 方法使得对于简单网格在最坏情 况下的压缩率下降到3 6 7 b p v 而随后g u m h o l d 将这个上限降低到3 5 2 2 b p v 。j r o s s i g n a c 和a s z y m c z a k n 7 1 8 1 在解码时的时间和空间复杂度也被降到线性级再 后来s z y m c z a ke ta 1 对e d g e b r e a k e r 进行进一步优化，对于大型的半正则网格 其最坏得压缩效果也可以是1 6 2 2b p v 。 t o u m a 和g o t s m a n 提出的t g 方法是一种基于点的方法，首先从网格上的任意 一个三角形开始，将这三个点放入活动列表( a c t i v el i s t ) ，然后从该列表中一 次取出一个顶点，然后遍历所有和该点相连的所有为处理过的三角形，并输出该 顶点的度，并把新的顶点加入列表尾部。有时候需要根据情况将列表分裂或合并。 对于很规则的网格，绝大多数顶点的度都集中在6 附近，该方法可以得到很高的 压缩效果。对拓扑信息的压缩效果平均是在l j5 b p v 。不过这个方法只是适用于 流形网格。下图2 - 3 给出了一个t g 方法的处理流程： 笫2 章王角m 恪h i 缩技术综述 ! 曼 i 一一一= _ i i i i 皂皇! ! 曼! ! 曼! 寰曼! ! 曼曼蔓曼! 曼寰! 曼曼皇曼苎! ! ! 曼曼 画卿画回 m 画画画回 厨画画画 图2 - 3t g 方法 f i g 2 3m e t h o ds u p p o r t e db yt o u m aa n dg o t s m a n a l l i e z 和d e s b r u n 改进了t g 算法，采用启发式算法选择自由边数最小的点 作为下一个处理的顶点以减小对表进行分裂的次数，从而提高了t g 算法的效率， 特别是对非规则网格压缩的效率。 2 1 5 对几何信息的压缩 上述的基于拓扑驱动压缩方式。都是先编码连接信息，然后再对几何信息进 行压缩。对几何信息的压缩，主要采取的方法有量化和预测以及谱方法。 顶点的坐标通常是使用3 2 位的浮点数表示的，在很多的情况下，远远超过 了应用中需要精度。斟此有很多的位存在着冗余。通过均匀量化，将精度降低可 以提高位的使用效率。这种方法首先确定一个网格的外切长方体，将这个长方体 按照量化等级沿三个坐标方均匀划分。再将各顶点的坐标映射到距离其最近的划 北京t 业人学t 学7 i ! j i 。学位论文 分长方体所得到格点上，从而实现量化的过程。 通常来说，被处理的网格多数都具有很好的连续性，其顶点坐标之间存在着 很强的相关性。可以通过预测的方式去除这种相关性，如果预测准确的话，预测 误差将集中在0 附近，从而便于编码。在拓扑手术的方法中，利用顶点生成树上 前k 个顶点的线性组合来对顶点的坐标进行预测，并选择最优预测系数以使平均 预测误差最小。即求解下式中的最优化问题： 。l lk1 1 2 ( ，q ) = a r g r a i n | v ：厂a j v i - j l i = k + x l l ，一1 0 这个问题可以通过最4 , - 乘法来解决，通常来说k 取3 就可有不错的效果。 另外一种常用的预测器是平行四边形预测器，其初衷的假设相邻的两个三角 形构成一个平行四边形。通过已知的三个顶点来预测另外一个顶点的坐标。在 e d g e b r e a k e r 方法中，就是使用的这种预测方法。 谱方法则利用了类似信号处理的方法对坐标进行压缩。将各顶点的x 分量，y 分量，z 分量分别抽取出来分别组成新的向量z ，y ，z 。预测误差占分别由 s ，占：表示，在解码的时候需要解如下三个线性方程。 d x n x = s ，v y n y = 占，d z n z = s ： 其中d 是一个对角矩阵，d 中每一个对角元素为对应顶点的入度，其余元素为o 。 中的元素当两点相邻的时候定义为1 ，不相邻或是自身的情况下定义为0 。设 = d n ，e 为三对应的特征值对角矩阵。是以的特征向量作为行构成的 矩阵。则有啦= e y ，并且有g t l x = 炉。代换得到e l z t x = 咿。 这意味着了畛和炉之间的关系是很简单的。因此对x 使用少进行变换在解 决上述问题时是有效的。记x = 盼，则x 中将会有很多的o 元素，这样对其进 行编码便可得到很高的压缩效率。以上便是谱方法的由来。不过这种方法最大问 题在于计算特征值和特征向量的复杂度为立方级的，而且对于每一个网格都要进 行这样的计算使得执行时的效率不是很高。针对这一问题可采取的办法是将网格 分成若干小片，以降低运算时的复杂度。不过，谱方法目前是对几何信息压缩效 率最高的方法之一。 o 第2 币三角i j 格j k 缩技术综述 曼蔓! 曼! 曼蔓! 曼曼! i i i i 一 一 一一i 曼 2 2 渐进压缩 基于拓扑驱动的压缩方法发展到今日其压缩效率已经日益接近其理论极限。 而随着互联网技术的发展，近些年来的研究焦点集中在了渐进压缩上。 渐进压缩的意义如前文所说，主要是为了减少用户交互时的初始等待时间。 只要用户接收完一个初始网格便可以进行交互。随着细节信息不断传过来，渐渐 地还原出网格的原貌。这类方法的基本思想是先将网格简化，得到简化网格以及 一些可逆的操作。对简化网格用单一位率的方法进行编码，将其放在文件头部， 再将细节部分编码按层次方在位流中，这样就可体现出渐进的特点。 渐进压缩的方法也可分成拓扑驱动和几何驱动两类。 2 2 1 基于拓扑驱动的压缩 拓扑驱动的方法有h o p p e n 们的渐进网格( p r o g r e s s i v em e s h e s ) 、t a u b i n 啪3 的p f s ( p r o g r e s s i v ef o r e s ts p l i t ) 、p a j a r o l a 和r o s s i g n a c 口玎的c p m ( c o m p r e s s e dp r o g r e s s i v em e s h e s ) 、a l l i e z 和d e s b r u n 口2 1 的入度驱动编码等。 渐进网格的基本思路如同前面所提到的。该方法不断对流形网格进行消除边 的操作( e d g ec o l l a p s e ) 将该边的两个端点合并，与原来两个点相关的点都连 接到新的点上。其逆操作点分裂( v e r t e xs p l i t ) 则是将一个点以及其相关的边 和三角形加入网格。 翮_ 嚣- 佩_ 图2 - 4 边消除与点分裂操作 f i g 2 - 4e d g ec o l l a p s ea n dv e r t e xs p l i t 假设对初始的网格m 进行了k 次边消除操作，用数学式子描述出来便是： 北尿i 业人字t 掌坝i 掌位论义 m = m 女= m i i + e c o l z m 一i = m 女一2 + e c o l 2 m i = m o + e c o l k 则初始网格就可以表示为m 。e c o l k e c o l , 小，e c o l i 组成的序列 设对每一个逆操作有e c o l 小f = v s p l i t f 则还原网格时就可以通过 m l = m o + v s p l i t l m 2 = m l + v s p l i t 2 m 一l = m t 一2 + v s p l i t i 一1 m = m t = m t l + v s p l i t t 的方式重构出来，这种方法作为渐进网格压缩的起点，效率并非很好。后来h o p p e 通过改变v s p l i t 操作的顺序来提高压缩比，用大约1 0 4 位表示一个v s p l i t 操 作。不过这个方法之能应用于流形网格。 针对这些问题p o p o v i c 和h o p p e 提出了p s c ( p r o g r e s s i v es i m p li c i a l c o m p l e x ) 方法，通过引入一种广义的v s p l i t 操作，使得该方法可以应用于任何 拓扑性质的网格。上述两种方法对几何信息的压缩采用的都是平行四边形预测。 t a u b i n 的p f s ( p r o g r e s s i v ef o r e s ts p l i t ) 也只能应用于流形网格，和p m 方法类似，其中引入了一种f o r e s ts p l i t 操作，这种方法可以使网格三角形的数 量增加一倍，因此比其p m 方法可以有更加高的压缩效率。编码一个有4 5 层细 节的网格，p f s 大约需要7 一l o b p v 对连接信息进行压缩，而6 位量化的几何信息 需要2 0 - 4 0 b p v 。p f s 也是m p e g 43 d m c 中的一种可选网格编码方式 图2 5p f s 方法 f i g 2 5p r o g r e s s i v ef o r e s ts p l i t p a j a r o l a 和r o s s i g n a c 瞳。1 的c p m 方法是对p m 方法的一种改进，主要是对其 压缩效率的改进。c p m 将v s p l it 分组利川一些标志位对注明其属于哪。一组，对 其几何信息在每次边消除的时生成的新顶点使用的是两端点的中点。并对两端点 丕一 盔 量n。辽 c 公叁 b 丕一 叁 粥! 帝王拜j 网恪f l j 缩找术综述 坐标的差进行预测，最后对预测误差进行编码。c p m 对拓扑信息的压缩效率大约 是7 o b p v 而对采取8 - 1 2 位量化的几何信息的压缩效率为1 2 - 1 5 b p v ，总体来说 其性能大约是p f s 的一倍。 入度驱动编码由a l l i e z 和d e s b r u n 提出，针对拓扑信息他们采用顶点消除 的办法，消除网格中度数小于等于6 的顶点，以得到一个多分辨率网格，并将这 些被消除的点的度输出进行熵编码。对于几何信息，他们采用了重心预测以及 f r e n e t 局部框架等方法进行编码，对于拓扑信息得到了2 - s b p v 的压缩效果，平 均在3 7 b p v 。对于几何信息对于1 0 - 1 2 位的量化信息可以用1 0 1 6 b p v 得到。而 对于高度规则的网格通常不用l o b p v 。 2 2 2 基于几何驱动的压缩 除去上述的基于拓扑驱动的各算法，还有一大类算法是基于几何驱动的算 法，即先处理网格的几何信息，然后再处理网格的拓扑信息。如k d 树，八叉树， 基于小波分析的网格分析，法向网格以及几何图像等方法。 k d 树乜钔的方法由d e v i l l e r s 和g a n d o i n 提出。其主要流程是首先不考虑拓 扑信息对几何信息进行编码，利用k d 树对网格的包围盒进行细分，每一次都将 体元一分为二，然后对各个体元中的顶点数进行编码，反复进行直到每个体元至 多包含有一个顶点。然后再对两个相邻的细节层间的拓扑变化进行编码。这种方 法也是适用于任何的网格的。性能上来说该方法对拓扑信息的压缩大约为 3 5 b p v ，1 0 - 1 2 位量化的几何信息可得到1 5 7 b p v 的压缩效率。 2 2 2 2 八叉树 p e n g 和k u o 乜副提出的八义树的压缩方法是一种渐进的无损的网格编码。该方 法首先通过递归分割网格包幽盒的方法构造出一棵八叉树，然后采用自顶向下的 方式编码每个节点局部变化信息。编码时只编码该节点是否为空，也使得编码相 当的简洁，这种方法可应用于任何拓扑性质的网格，而且很容易扩展到多边形网 格上。 北京t 业人学t 学顺卜￥f z 论文 2 2 2 3 几何图像 g u 他6 】于2 0 0 2 年提出了一种新编码方式，几何图像的方法。首先将网格切开 然后参数化到一个单位正方形中，而后其顶点的坐标等参数可均匀采样为图像， 之后利用经典的图像处理办法进行压缩。后来h o p p e n l2 蝴由提出了将其参数化到 三维球面的方法，并获得了较好的效果。2 0 0 5 年g a b r i e lp e y r e ，s t e p h a n e m a l l a t 1 在s i g g r a p h 上发表的论文将b a n d e l e t 等新的小波函数应用于几何图像 上的压缩得到了不错的效果。 2 2 2 4 基于小波的方法 基于小波的方法由l o u n s b e r y 1 开创，他建立起了半正则网格( 网格上绝大 多数点的入度为6 ) 上的小波分析。他证明了通过网格细分技术，可以在定义于 任何拓扑性质的函数族上建立起多分辨率分析。他称其为细分小波( s u b d i v i s i o n w a v e l e t s ) ，从而将网格分解为一个基网格和一组小波系数。k h o d a k o v s k y 在后 期的研究中，首先对网格使用m a p s 算法进行重新网格化使其成为一个半正则网 格，而这也同时意味着这种方法中对拓扑的压缩时有损的。然后使用l o o p 小波 对其分析得到一个基网格和一组小波系数，这些系数反映出了不同细节层的差 别，然后再用改进了的s p i h t 算法对l o o p 小波的系数进行编码。后来该方法运 用了b u t t e r f l y 小波进行变换获得了更好的效果。不过上述方法还只是停留在半 正则网格上。刘波口别等人将小波的方法应运于单一位率的压缩也获得很好的效 果。 2 0 0 4 年s e b a s t i e nv a l e t t e 和r e m yp r o s t o 珀t3 4 3 在t v c g 上发表的两篇论文推 广了l o u n s b e r y 的理论，建立起在非规则网格上的小波分析，并将其应用于网格 压缩( w a v e m e s h ) 。从而不需要对网格重新进行半f 则化，便可进行小波分析。 l o u n s b e r y 的理论中一个三角形被一分为四，而在s e b a s t i e nv a l e t t e 和r e m y p r o s t 的方法中他们针对每个面不同的情况把一个三角形分解为卜4 个共1 1 种 情况。并通过约定三类操作，实现了对网格细分和重构，其论文中结果对于一些 简单的同胚于球的网格可以简化为一个四面体。在其理论中两层细节之间可由公 式：c i 一：a , c i ，d i 一= b i c7 决定 其中彳7 ，b7 为分析滤波器， c 7 为第j 层细节顶点坐标组成的矩阵，d7 则为 第j 一1 层的小波系数。在还原的刚+ 候通过综合滤波器p7 ，q7 ，第层的细节可山 公式c7 = p7 c7 一+ q7 d h 柬还原。 4 第2 幸一t 角m 各啭缩技术综述 2 3 本章小结 在这章中，系统地介绍的各种三维网格压缩技术，从单一位率压缩到渐进 式压缩，从拓扑驱动压缩到几何驱动压缩，从两个角度三个方面介绍了各种网格 压缩技术的主要思想与压缩性能。 基于拓扑驱动的方法通常先对连接信息( 拓扑信息) 进行编码，这类方法通 常是按照某种事先约定好的遍历方法对网格进行遍历，将遍历时遇到的不同情形 用符号序列进行记录，待遍历完成后，将该符号序列进行编码，以实现对连接信 息的压缩。在遍历过程中，算法还会记录遇到顶点的次序，依次各个顶点的坐标 进行编码。基于拓扑驱动的压缩方法发展到今日其压缩效率已经日益接近其理论 极限。而随着互联网技术的发展，近些年来的研究焦点集中在了渐进压缩上。 渐进压缩方法的基本思想是先将网格简化，得到简化网格以及一些可逆的操 作。对简化网格用单一位率的方法进行编码，将其放在文件头部，再将细节部分 编码按层次方在位流中，这样就可体现出渐进的特点。渐进压缩的方法也可分成 拓扑驱动和几何驱动两类。而且基于几何驱动的算法都体现出对几何信息压缩采 取压缩顶点空间位置存在性的特点。 在后面的二章中，将基于这一思路提出两个原创的基于几何驱动的网格压缩 算法。其中一个算法在压缩性能方面达到了和目前同类方法相媲美的压缩效率。 而一个方法则给网格几何信息的压缩提供了一个新思路。 第3 幸幕卡一：叉树结掬的二i f f j 嗍恪渐进式f j 缩 第3 章基于二叉树结构的三角网格渐进式压缩 3 1 引言 在研究中我们发现量化后的几何信息中包含有大量的冗余，以二进制数据组 0 0 0 ，1 0 0 ，1 0 1 ，1 1 0 ，1 1 1 ) 为例，可以观察看出在数据的高位出现的冗余的频率的 比低位要高。 对于 1 0 0 ，1 0 1 ，1 1 0 ，1 1 1 而言，最高位的1 出现了4 次，可实际上只需要出 现一次即可。对于 1 0 0 ，1 0 1 第2 位的o 出现了2 次，而其实也只需要出现一次 就足够了，相似地 1 l o ，1 1 1 ) 第2 位的1 也只需要出现一次。而在这1 5 位的数据 中，有3 + 1 + 1 = 5 位的数据是冗余的。在二进制表示下，两个数据如果有着相同的 高位，可以将这两个数据想象为两个结点，而这两个结点有着共同的祖先，这个 祖先中储存的信息便是重复了的高位部分，出于这种考虑，对于上述共计1 5 位 的信息就可以用图3 1 表示的二叉树唯一表示，这样的一组信息即使不再进一步 处理也最多只需要1 0 位去表示。 而且我们可以发现对于任何至少需要三位量化的数据组，按照上述办法构造 的与之对应的二叉树在第一层以上的结构都是一样的，是一棵完全二叉树。若需 要从第一层开始恢复数据组只需顺序知道第一层的两个节点拥有孩子节点的情 况( 共3 种情况：只有左孩子，只有右孩子，有两个孩子节点) 即可顺序恢复出 第2 层节点的信息。同理只要顺序知道了第2 层各节点的拥有孩子节点的情况， 即可顺序恢复出第3 层节点的信息，即原数据。 幽3 一l 0 0 0 ，1 0 0 ，1 0 1 ，1 1 0 ，1 1 1 的二义树 f i g 3 1b i n a r y t r e eo f d a t a s