（信号与信息处理专业论文）三维网格的多描述编码研究.pdf

摘要 摘要 3 d 模型在工业，医学及娱乐领域的应用曰趋广泛，因此寻求合适的构造模 型以及有效的压缩模型的方法是十分必要的。本文对应用最为广泛的3 d 模型 表示方法三角网格进行深入研究，根据不同3 d 网格数据的结构特点，提出具 体的3 d 网格的多描述编码方案。 首先，对当前三维模型压缩方法进行综合分析与归纳。 其次，针对当前网络异构性和差错性两大问题，讨论了基于边塌缩的渐进 网格结构特点，分析了基础网格中顶点分裂树的构造方法与多描述分配方法对 重建网格误差的影响，提出三维网格的分层多描述编码方法( l m d c ) ，本方法 结合了分层编码与多描述编码的优点，分别有效的抗击了异构性和差错性两大 问题，仿真结果验证了该方法能获得较高的压缩率，并在有丢包的情况下能有 效的保护并恢复出可接受的基本层网格。 最后，研究了使用小波变换处理三维网格的方法，分析了三维网格小波系 数结构与二维图像小波系数结构的差异性以及三维网格小波系数的误差模型， 提出一种基于加权小波的三维网格多描述编码方法，该方法对小波系数进行加 权处理，使其更加适合随后的s p i h t 算法，利用s p i h t 码流分层内嵌特性将小 波系数分组形成多个描述，可以很好的适应网络带宽的变化和丢包率，仿真结 果验证该方法具有较高的压缩率和抗误码能力，具有更小的重建误差。 关键词：3 d 网格多描述编码分层编码顶点分裂树小波变换，s p i h t a b s t r a c t a b s t r a c t 3 dg r a p h i c sd a t aa r em o r ea n dm o r ew i d e l yu s e di nv a r i o u sa p p l i c a t i o n s ， i n c l u d i n ge n g i n e e r i n gd e s i g n ，m e d i c a ld i a g n o s i n ga n dv i d e og a m i n g i nt h i sp a p e r w eu s et h et r i a n g l em e s ht or e p r e s e n tt h e3 dm e s hm o d e l ，a n dc o n c e n t r a t eo nt h e c o m p r e s s i o no fc o r m e c t iv i t ya n dg e o m e t r yd a t a f i r s t ，w es u r v e yt h em a i ni d e a so f3dm e s hc o m p r e s s i o nc o d i n g s e c o n d ，a st h e r ea r eal o to fe r r o r , p a c k e t sl o s i n gi nt h ei n t e r n e ta n dt h ei n t r a n e t ， w ea n a l y z et h es t r u c t u r eo ft h ev e r t e xs p a n n i n gt r e ea n dt h ea f f e c ta c c o r d i n gt ot h e d i s t r i b u t i o no ft h ev e r t e xi nt h ev e r t e xs p a n n i n gt r e e t h e nw ep r o p o s et h el m d c ( l a y e r e dm u l t i p l ed e s c r i p t i o nc o d i n g ) m e t h o d ，w h i c hc o m b i n i n gt h ea d v a n t a g e so f b o t hl a y e r e da n dm u l t i p l ed e s c r i p t i o nc o d i n g ，i sm o r ea p p r o p r i a t et ot h ec u r r e n t n e t w o r ko fr e a l t i m em e s ht r a n s m i s s i o na n dt h ep u r s u i to fh i g h e r q u a l i t y t h e s i m u l a t i o n sh a v ep r o v e dt h a tt h em e t h o dc a ng e tah i g hc o m p r e s s i o nr a t i oa n dc a n s t i l lr e s t o r ea na c c e p t a b l em e s hi nt h ec a s eo f p a c k e tl o s s + i nt h ee n d ，w es t u d yt h e3 dm e s hc o m p r e s s i o nm e t h o d sb a s e dw a v e l e tt r a n s m i t a n a l y z et h ed i f f e r e n c eb e t w e e nt h ec o e f f i c i e n t sf r o m3 dm e s ha n d2 di m a g e ，a l s o d e e p l ya n a l y z et h es t r u c t u r eo ft h ee r r o rm o d e li n3 dm e s hc o e f f i c i e n ta r r a y f u l l y a n a l y z e da sa b o v e ，t h ew w m d c ( w e i g h t e dw a v e l e tm u l t i p l ed e s c r i p t i o nc o d i n g ) m e t h o di sp r o p o s e d ，i nw h i c ht h ew a v e l e tc o e f f i c i e n t sw e r es c a l e du pb e f o r eu s i n g t h ee m b e d d e dc h a r a c t e ro fs p i h tt od e r i v em u l t i p l ed e s c r i p t i o n so ft h em e s h ，w h i c h t h en u m b e ro fd e s c r i p t i o n sa n dr e d u n d a n tc a l l v a r ya c c o r d i n gt o t h ec h a n g eo f c h a n n e lb a n d w i d t ha n dt h ep l r ( p a c k e tl o s sr a t e ) t h ee x p e r i m e n t a lr e s u l t ss h o w t h a tt h ep r o p o s e dm e t h o d sh a sb e t t e r a b i l i t y t o a d a p tt h ec o m p l e xn e t w o r k e n v i r o n m e n ta n de r r o rr e s i l i e n t ，a n da l s ol o w e rr e c o n s t r u c t i o ne r r o r k e yw o r d s ：3 d m e s h ，m d c ，l a y e r e dc o d i n g ，v e r t e xs p a n n i n gt r e e ，w a v e l e t ，s p i h t 中国科：学技术人学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的 成果。除己特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或 撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作 了明确的说明。 作者签名：蚕盗墼签字同期：丝! 盗鱼丛：塑 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学 拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构 送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入中 国学何论文全文数据库等有关数据库进行检索，可以采用影印、缩印或扫描等复 制手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的内容相 一致。 保密的学位论文在解密后也遵守此规定。 囱，从开口保密( 年) 作者签名： 菌旋i 拯 签字日期：鲨! 嗑鱼鲤堡 导师签名：互量生 签字日期：么望： 第1 章绪论 1 1引言 第l 章绪论 由于视觉信息与其他形式的信息相比较更加的直观、形象和生动，因此人 类开始不满足于传统的文本和语音数据的通信方式，包含图像视频特别是3 d 图 像的视觉信息逐渐受到越来越广泛的关注。 5 0 年代，第一台图形显示器诞生。该显示器用一个类似子示波器的阴极射 线管( c r t ) 来显示一些简单的图形。6 0 年代，出现“计算机图形学”概念。 7 0 年代，光栅显示器诞生，图形学进入兴盛时期，并产生了真实感图形学和实 体造型技术。构造3 d 模型的研究大量涌现，其中最简单的方法利用表面信息构 造模型。与文字信息不同，3 d 模型信息需要相当大的存储容量和很宽的传输信 道，而目前互联网和无线通信网结构各异，丢包差错严重，成为限制网络实时 技术发展的瓶颈，因此大量的3 d 模型的压缩算法也同益涌现：包括d e e r i n g 、 t u r b i n 和b a j a j 等人提出的单分辨率压缩算法( d e e r i n g1 9 9 5 ：t a u b i na n d r o s s i g n a c1 9 9 8 ：b a j a j ，p a s c u c c ie ta 1 1 9 9 9 ) 和h o p p e 、p a j a r o l a 等人在 前人的基础上提出的多分辨率压缩方法( h o p p e1 9 9 6 ：p a j e r o l aa n dr o s s i g n a c 2 0 0 0 ) ，随着多分辨率压缩的诞生，将描述编码方法应用到3 d 模型的方法应运 而生。多描述编码理论( g o y a l2 0 0 1 ) 将信源信息分解为多个重要性相同的子集， 每个子集作为一个描述不分优先级的在不同的独立的信道中传输。由于每个子 集都是原始3 d 模型的粗糙近似，这样在接收端，接收端任意一个描述均可恢复 出视觉上可接收的粗糙模型，并且随着收到描述的数量增多，重建模型的精度 也随之逐步提高，这样便有效的解决了传统信源编码在不可靠网络中遭遇丢包 和延迟导致质量下降的问题。 多描述编码的历史可以追溯到2 0 世纪7 0 年代，当时b e l l 实验室为了在电 话网上提供不问断的电话业务，将来自一个通话的信号进行奇偶分离成两路信 号，并在两个分离的信道上传输。当时该问题被b e l l 实验室称为信道分离问题。 多描述编码被正式提出是在1 9 7 9 年9 月的s h a n n o n 理论研究会上，当时g e r s h o 、 o z a r o w 、w i s t e n h u s e n 、w o l f 、w y n e r 和z i v 等人提出了如下的问题：假如将一 个信源用两个单独的描述所表示，这些描述分开或者联合起来时对于信源的重 建质量将会有怎样的影响? 这个问题被称为多描述问题。这个领域中，最初的 基本理论是由上述的研究人员以及a h l s w e d e 、b e r g e r 、c o v e r 、g a m a l 、z h a n g 等人在2 0 世纪8 0 年代提出的。早期的研究主要集中于两信道三解码器的多描 第1 章绪论 述编码所产生的五元函数( r ，尺，d 。，n ，d ，) 的问题。在1 9 7 9 年9 月的s h a n n o n 理论研究会上，w y n e r 与w i t s e n h a u s e n 、w o l f 及z i v e 等人给出了二元信源在 h a m m i n g 失真下的m d c 的初步理论。对于任意无记忆信源和有界失真度量下的 给定失真矢量( d 。，d 1 ，d ，g a m a l 和c o v e r 给出了可达到的率区域( 尺。，r ，) ， r z a r o w 证明了上述区域对于无记忆高斯信源和平方差下是严紧的。随后 a h l s w e d e 提出“无剩余码率”理论，即当足+ r ，= r ( d 。) 时，上述的g a m a l c o v e r 限j 是严紧的。z h a n g 和瞻r g e r 证明了当d 。 d ( r ；+ 尺，) 时，上述边界并不膈 紧，上面结论都是针对高斯信源而进行的研究，对于非高斯信源的率失真边界 还不能完全知道。z i m i r 针对非离散的无记忆信源在均方误差下的多描述编码， 给出了率失真范围，它其实是对率失真函数下的s h a n n o n 边界的扩展。对于五 元函数( 足，尺，战，d i ，d ，) 的可达区域进行研究，主要的工作是集中在h a m m in g 失真下的无记忆二元对称信源。 多描述编码在早期主要进行的是理论研究，自v a i s h a m p a y a n 给出了第一个 使用的多描述编码方法( m d s q ，m u l t i p l ed e s c r i p t i o ns c a l a rq u a n t i z a t i o n ) 后，多描述编码的研究开始由理论研究向构造实用的多描述编码系统转变，到 1 9 9 8 年左右，多描述编码已经成为众多学者研究热点，许多新的多描述图像编 码方法出现，如基于亚采样的多描述编码、基于量化的多描述编码和基于相关 变换的多描述编码等。国际上多描述视频编码的研究主要从1 9 9 9 年- 丌始，目前 尚处于初步阶段。现有的多描述视频编码多数是基于块的运动估计和运动补偿 的编码方案。 综上分析，在复杂的网络环境下，为可靠地传输3 d 模型，不仅需要考虑压 缩性能，同时也需要兼顾传输的可靠性，因此多描述编码作为一种效率高容错 性强的编码，将之应用于3 d 模型的压缩传输上是十分有意义的。例如n o r k i n ， b i c i 等人提出基于p g c 的m d c 方法已经初步证明该结合的可行性与有效性。 近年来，国内的许多学者也丌始对多描述编码产生了兴趣，在多描述图像 编码方面，计文平等利用m o j e t t e 变换实现一种图像多描述编码方法；张楠等 提出了一种基于方向提升小波变换的多描述图像编码方法；肖嵩等提出了一种 感兴趣区域的多描述s p i h t 编码方法；陈婧等提出了基于x 树非平衡保护多描 述子带编码等。在多描述视频编码方面也展开了深入的研究，如朱红等针对 i n t e r n e t 视频通信中面临的随机丢包问题，提出了一种基于视觉感知片组的多 描述视频编码方案；范晨等提出了一种基于棋盘式分割的多描述视频版面算法； 郁梅等在块基编码的基础上，提出了一种基于宏块分裂的多描述编码方法、相 应的冗余度控制策略以及误匹配控制方法；柳薇等提出了基于平衡小波图像变 换的视频多描述编码；王养利等提出了基于网格( m e s h ) 的多描述编码方案： 2 第1 章绪论 张朝鹏等结合分层编码和多描述编码构造了一种适用于差错网络视频传输的联 合编码结构。由此看来，国内学者对2 d 图像压缩技术研究十分丰富且深入，但 是对3 d 网格的压缩编码技术甚少，本文主要以此为切入点，着重讨论具体的 3 d 网格的多描述压缩编码方法。 1 2 论文的研究内容和组织结构 本文在前人的基础上，重点讨论3 d 网格的多描述编码压缩方法。本文主要 内容包括以下几个章节： 第一章，简要概括了3 d 网格及多描述编码理论的国内外研究情况，引出 3 d 网格多描述编码的研究意义和研究内容； 第二章，综合阐述了3 d 网格压缩的相关理论和技术： 第三章，阐述将分层编码与多描述编码相结合应用到3 d 网格压缩的一个具 体编码方案； 第四章，阐述了基于小波变换的3 d 网格多描述编码方法； 第五章，工作总结与展望，总结了本文工作的创新与不足，提出进一步的 研究工作。 第2 章3 d 网格压缩原理 第2 章3 d 网格压缩原理 2 13 d 网格压缩理论发展过程 3 d 网格数扼在视频游戏、工程设计、建筑演练、虚拟现实、电子商务和科 学可视化等领域内的应用越来越广泛。三角网格是所有3 d 模型表示方法中最为 有效的一种，它主要通过连通性信息、几何信息和属性信息来描述个3 d 网格。 其中，连通性信息描述的是两个顶点之间的连接属性，几何信息描述顶点的几 何位置信息，而属性信息描述网格的法向向量、纹理坐标等信息。由于属性信 息大都与顶点坐标相关，因此本文只讨论连通性信息和几何信息的压缩。 通过模型软件或者3 d 扫描仪得到的3 d 模型往往十分复杂，初始数据需要 很大的存储空间和很宽的传送带宽。3 d 数据随着模型的复杂程度快速增长，资 源问题就集中在存储空间、计算能力和带宽上，而需要实时交互的图形应用往 往使得网络带宽成为这三个资源问题中的瓶颈，因此及时有效的网格数掘压缩 是必不可少的。在九十年代初期，该问题被广泛关注，并在近二十年内得到快 速的发展。 早期3 d 网格压缩主要集中在单分辨率压缩，单分辨率压缩将连通性信息 与几何信息整个进行编码与解码，显卡只有接收到全部的b i t 流才能渲染网格。 随着因特网的发展流行，渐进压缩( 也称为多分辨率压缩) 与传输理论兴起， 在渐进几何压缩中，解码器可根据已经接收到的b i t 流逐渐的重构网格，接收 的b i t 流越多，网格就越精细。由于用户可以根据自己的处理能力和已经下载 的网格精细程度随时终止传输，因此渐进几何压缩也可提高交互能力。 目前，已经形成几个3 d 网格压缩的国际标准：v r m l ( 1 9 9 7 ) 建立了3 d 模型 在网络中传输的标准( a s c i i 格式) 以及t a u b i n e ta 1 建立的压缩二进制格式， 其中压缩二进制格式相对于a s c i i 格式可达5 0 ：l 的压缩率。m p e g 一4 ( 2 0 0 2 ) 作 为i s o i e c 国际多媒体标准也包含了3 d 网格的压缩编码标准。r o s s i g n a c 在文 献( r o s s i g n a c1 9 9 9 ) 中简要介绍了几种顶点数据压缩和连通性数据压缩方法； t a u b i n 在文献( t a u b i n2 0 0 1 ) 中主要介绍了i p e g 一4 标准中的拓扑分割压缩方法 和渐进树分裂压缩方法；s h i k h a r e 的综述( s h i k h a r e2 0 0 0 ) 将几种3 d 网格压缩 方法进行分类并逐一阐述。 4 第2 犟3 d 网格乐缩原理 2 2 单分辨率压缩算法 通常一个典型的网格压缩算法是将连通性信息与几何信息分别进行编码， 而早期的压缩方法主要集中在对连通性信息的压缩编码上，对几何数据的编码 顺序取决于底层连通性的编码。由于几何信息的数据量远大于连通性信息的数 据量，因此后续研究更偏向于如何增加几何信息的编码效率。 2 2 圣连通性信息编码 现存的单分辨率连通性信息压缩算法大概分为六种：索引面集合方法、三 角形带方法、分裂树方法、分层分解方法、顶点价态驱动方法和三角形浸染方 法。 1 、索引面集合方法 在v r m la s c i i 格式标准中，一个包含检索面集合的三角网格是用坐标序列 和面序列来描述的，坐标序列列出所有顶点的坐标，面序列列出每个三角形三 个顶点的检索序列，如图2 1 所示的一个网格和面序列。 v o v 4 v l v 2 i n d e xf a c e 0 ( o ，l ，4 ) l ( 1 ，3 ，4 ) 2 ( 1 ，2 ，3 ) 图2 1网格与面序列 2 、三角形带方法 三角形带方法的主要思想是将一个网格分解为长长的三角形带，然后对这 些三角形带进行编码。因为大部分的显卡都支持三角形带，因此该方法可以减 少数据从c p u 到显卡之间转换时间，但是相对于索引面集合方法来说，该方法 并没有显著的提高压缩率。 图2 2 ( a ) 所示为狭义三角形带，( b ) 为三角形扇，( c ) 为广义三角形带。 从图中看出，每个新增三角形都是由原来序列中已有的两个顶点与一个新的顶 点构成，因此分解网格得而到的三角形带越长，压缩率也就越大。但是由于网 格中三角形的数量大约为顶点数的两倍，因此在广义三角形带中，顶点可能被 重复检索，从而造成对存储空间的浪费。为了解决该问题，d e e r i n g 首次提出 使用顶点缓存器( d e e r i n g1 9 9 5 ) ，使用先进先出( p i f o ) 的顶点缓存器存储最近 第2 章3 d 网格乐缩原建 使用的1 6 个顶点，若一个顶点存储在顶点缓存中那么就由缓存序列俭索，这样 使用的bj t 数远小于在全部顶点序刊中检索， ( a )( b ) 图22 三角 i 耋带示意图 v 2v 4 ( c ) 在d e e r in g 的基础上，c h o w 提出了一种适用于实时渲染的压缩算法( c h o w 1 9 9 7 ) ，他提出一种网格分解方法，如图23 所示，首先找到一条边界边的集合 f 图23a ) ，然后找到与边界边相邻的边组成的三角形扇( 图23b ) ，并将这 些三角形标记为以遍历，于是产生新的边界边( 图23c ) ，如此往复，知道遍 历到所有的三角形。 黪黪黪 b c 圉23c h o w 方法示意图 3 、顶点分裂树方法 根据t u r a n 的研究。一个平面网格的连通性信息可用顶点分裂树和三角形 分裂树进行编码。在此理论基础上t a u b i n 和r o s s i g n a c 提出使用拓扑分割的 方法对网格的连通性信息进行编码，该方法的主要思想是选择一系列剪切边将 一个网格分解为一个e i - - - - - 角形带组成的平面拓扑结构，这样一个网格的连通性 信息就可以用这个剪切边( 即顶点分裂树) 和平面几何拓扑( 三角形分裂树) 来表示，如图24 所示。圆24a 是一个八面体网格，首先将图24b 所示的 顶点分裂树做分剪切边将网格分割成图24c 所示的三角形分裂树，三角形分 裂树中的每个顶点都对应一个三角形，当且仅当对应的三角形公用一边时两个 鎏矜 一 第2 章3 d 网格压缩原理 节点d 相连。 。：。，焱 圈24 顶点分裂树示意图 定义两个节点之间的分段为个游程，然后将顶点分裂树和三角形分裂树 进行游程编码。对于顶点分裂树柬晚，使用两个标l a 位b 录每个游程的长度， 第一位标已下一个游程与本游程是否是同一个分支，第二位标已本游程是否为 叶子节点。以图24b 为例，第一个游程的长度为l ，所以第一位编码为1 ： 下一个游程与第一个游程不是出于一个节点，所以第二位编码为0 ；该游 程不是叶子节点所以第三位编码为0 。因此第一个游程便编码为0 , o ，0 1 。由此 推出整个顶点分裂树的编码为： ( 1 , 0 ，0 1 0 ，1 ，l l o ，0 ，o l o ，1 ，l l ( 1 ，0 ，1 ) 而三角形分裂树是二进制的，因此编码器只需记录每个游程的长度和是否 为叶子节点即可。 由于游程是顶点分裂树和三角形分裂树的基本单位，因此编码效率与分裂 树中的游程数量是对应的，所以如何构造网格的分裂树是决定编码效率的关键 因素。t a u b i n 和r o s s i g n a c ( t a u b i na n dr o s s i g n a c1 9 9 8 ) 提出了基于层分解的 方法来构造顶点分裂树，该方法的主要思想是将网格像剥橘子一样分解为平面 三角形带，最大程度的增加每个游程的长度从而减少整个分裂树的游程数量。 4 、层分解方法 b a j a j 等人提出利用顶点分层结构对网格进行编码的方法，该方法将三角 形分解为环形的顶点分层结构，然后通过相邻顶点分层构造三角形分层结构。 所有顶点分层结构、顶点分层的排列和三角形分层的排列便完全可以用来表示 网格的连通性信息。显然，不同顶点分层是不允许交错的，每个三角形分层便 为个广义三角形带这样，对顶点分层数量、每个顶点分层的顶点数量、每 个三角形分层的广义三角形带的编码即为对连通性信息的编码。 第2 章3 d 网洛压缩原理 实际f 往往由于分支顶点、二角形气泡和三角形扇的存在而必 贯使用额外 的b i t 来描述这些信息分支顶鱼如图25a 所示它是顶点分居自己出现交 叉时的交点，分支顶点将一个顶点分层分解为几个被定义为轮廓的片段+ 在对 一个顶点分层进行编码的同时，也必须对分支顶点信息和轮廓信息进行编码。 一如图258 d 所示，每个三角形分层只可能出现如下三种情况： 狭义三角形带，即所有三角形的二个顶点都在该三角形分层两侧的顶点 分层上j 三角形气泡，即每个三角形的三个顶点都在同一侧项点分层上： 三危形扇，即在每个三角形分层上的三角形的三个顶点分别在2 、3 个轮 廓上。 与t a u b i n 和r o s s l g n a c 利用顶点分裂树将厨格分解为广义三角形带的方 法( t a u b i na n dr o s s i g n a c1 9 9 8 ) 不同，r a j a j 提出的方法( 8 a j a j ，p a s e u e e ie t a l1 9 9 9 ) 并不是将顶点分裂树作为顶点分层，也不需要大容量的缓存存储遍历 的顶点。在他提出的分层方法中每一个三角形分层都依赖相邻的两个顶点分 层，而每个顶点分层也依赖于相邻的两个三角形分层，因此对顶点分层和三角 形分层分别进行编码可以有效提高网格传输的容错能力。 * 支顶 a 三角气泡 c b 三角撂扇 图25 屡分解示童图 d 第2 犟3 d 网格乐缅原理 5 、顶点价态驱动方法 顶点价态驱动方法的主要思想是：选择一个“种子三角形”。它的每个边初 始化为初始边缘，该边缘将网格分解为两个部分：边缘内部( 已处理) 和边缘 外部( 未处理) ，然后该边缘逐渐向外扩张，直到所有三角形都被处理完为止， 最后输出可重构原始网格的顶点价态b i t 流。 t o u m a 和g o t s m a n 提出的方法( t o u m aa n dg o t s m a n1 9 9 8 ) 是随机选择一个 三角形，将该三角形的三个顶点放入一个定义为激活序列的堆栈中然后从激 活序列中弹出一个顶点，接着遍历所有与该点相连的边并得到新的顶点入栈， 对每个已处理的顶点输出其价念。该方法在编码之前，需要加入一个虚拟顶点 并将该顶点与整个边界环连接( 如图2 6a 所示) 以保证整个拓扑是闭合的。 图2 6 表示了整个编码过程，加粗的线条和顶点表示激活序列，灰色原点表示 虚拟顶点。 图2 6a 一个输入网格； 图2 6b 加入一个虚拟顶点( 图示灰色顶点) ； 图2 6c 输出起始三角形三个顶点价态分别为：6 ，7 ，4 ； 图2 6d 扩张激活列表，输出新增顶点价念：4 ； 图2 6e 扩张激活列表，输出新增顶点价态：7 ： 图2 6f 扩张激活列表，输出新增顶点价念：5 ； 图2 6g 扩张激活列表，输出新增顶点价态：5 ； 图2 6h 选择下一个目标顶点； 图2 6i 扩张激活列表，输出新增顶点价态：4 ； 图2 6j 扩张激活列表，输出新增顶点价态：5 ： 图2 6k 分裂激活序列，将新的激活序列加入堆栈； 图2 6l 选择下个目标顶点； 图2 6m 扩张激活列表，输出新增顶点价态：4 ； 图2 6n 选择下一个目标顶点和虚拟顶点，输出虚拟顶尖价态：5 ； 图2 6o 将新入栈的激活列表弹出堆栈； 图2 6p 扩张激活列表，输出新增顶点价态：4 ； 图2 6q 关闭下一个目标顶点； 图2 6r 关闭下一个目标顶点； 图2 6q 整个网格全部遍历完毕。 9 幕2 章3 d 网梧乐缩曛理 幕灞 。澎圆蔼日 孺俪瓣 巡w 炒炒 囤26 顶点价态编码方法示例 对于一般网格来说，顶点的平均价态为6 ，可以使用算术编码对顶点价态 信息进行编码，但是该方法只适用于定向网格和流形网格。a 1 l i e z 和 d e s b r u n ( s c h in d l e r1 9 9 8 ：a i l i e za n dd e s b r u n2 0 0 1 ) 在此方法的基础上提出 改进算法，由于在t o u m a 和g o t s m a n 提出的算法中，对分裂点，分裂分支和虚 拟顶点的编码占用了大量的b i t 数，因此使用一个通用的虚拟顶点与输入网格 的所有边进行连接。同时在改进算法中使用启发式方法选择自由边最少的顶点 取代激活序列中的顶点作为下一个处理顶点，并且去除激活序列中与当前处理 顶点相连但却无分解能力的顶点，将激活序列中剩下的顶点按照与当前处理顶 点的距离进行升序排列。同样，该改进算法也只适用于定向网格和流形网格 6 、三角形浸染法 与项点价态方法相似，三角形浸染方法也始于一个随机选择的原始边缘， 醣边缘将整个网格分解为浸染过区域和未浸染区域两个部分，遍历过程就是将 网格中的三角形一个一个的插入浸染过区域。与顶点价忐方法最大的不同点是 v 一 。醪 。一一够 。簿。诬。 第2 章3 d 网格币笳原理 珐万往输出的是三角形的建设过程而非丁页点的价态。 g u m h o l d 和s t r a b e r ( g u m h o l da n ds t r a b e r1 9 9 9 ) 首次提出三角形浸染算法， 使用包含“新顶点”、“向前”、“向后”、“分裂”、“关闭”五个建设过程向浸染 过匡域插入三角形，并使用h u f f m a n 编码方法对建设过程进行编码该方法适 用于定向和非定向流形网格。 r o s s i n a c 等提出另外一种三角形浸染方法( r o s s i g n a c1 9 9 9 ) ，诙方法与切 割变价机制相似，但并不是对分裂过程中龅分支数据进行编码而是使用如图27 所示的边界上不控制三角形的遍历。将未处理的边界环入栈，定义目标边界r 司= 的边界门为激活门。首先，对每个相连的部分都定义一个边界环，如果设部分 投有物理边缘，那么就将两个合并为一个边作为边界环( 如图27b 所示) 。接 下柬算法浸染激活门对应的三角形，并且更新当前边界环和新的激话门，在浸 染的每一步输出一个操作码。图28 表示了整个编码过程。 未漫染区域 圉27 门激活方法示意图 假设每个正在浸染的三角形都由一个顶点v 和一个檄堰门g 表示那么图 28a 表示了五种可能出现的操作码：c ( 浸染) ，即项点v 不在边界环上： l ( 向左) ，即v 在边缘环上且在激活门之前：r ( 向右) ，即顶点v 紧接着 激活门g ；e ( 结束) ，即遍历完毕：s ( 分裂) ，其他情况。图2 8b 表示 v 国。了忿蟛 第2 章3 d 网格压缩原理 了一个编码过程，箭头和数字表示三角形浸染的顺序，不同的浸染方式对应了 不同的操作码，在这个例子中，输出的操作码序列应该是：c c r s r l l r s e e r l r e 。 滴匿 cl r 开始 图2 8 三角形浸染法编码过程 c 7 、小结 在所有单分辨率压缩方法中，t o u m a 和g o t s m a n 提出的算法( t o u m aa n d g o t s m a n1 9 9 8 ) 被认为是最先进的单分辨率压缩算法，a 1 1 i e z 和d e s b r u n ( a 1 l i e z a n dd e s b r u n2 0 0 1 ) 在其基础上进行改进达到更高的压缩率。索引面集合方法、 三角形带方法和分层分解方法可对任意拓扑结构的网格进行编码，而分裂树方 法、顶点价态驱动方法和三角形浸染方法只能对流形网格进行编码。例如顶点 价念驱动方法只能对定向的流形网格进行编码。若想使用分裂树方法、顶点价 态驱动方法和三角形浸染方法对网格进行编码可先对网格使用s z y m c z a k 等人 提出的方法( s z y m c z a k ，k i n ge ta 1 2 0 0 0 ) 进行预处理。 表l 给出上述几种方法的简单比较 v 、 一 ，、 grt-l 一i八牛 第2 章3 d 网格乐缩原理 表1单分辨率压缩方法比较 分类算法b i t 率( b p v ) 索引面集合方法 v r m la s c i i 格式( 1 9 9 7 ) 6 l 0 9 2v 三角形带方法 d e e r i n g ( d e e r i n g1 9 9 5 ) l1 t a u b i n 和 分裂树方法r o s s i g n a c ( t a u b i na n d 2 4 8 - 7 0 r o s s i g n a c1 9 9 8 ) b a j a j 等( b a j a j ， 层分解方法 1 4 0 - 6 0 8 p a s c u c c ie ta 1 1 9 9 9 ) t o u m a 和g o ts m a n ( t o u m a 顶点价态驱动方法 。0 2 - 2 4 a n do o t s m a n1 9 9 8 ) o u m h o l d 和 s t r a b e r ( g u m h olda n d 3 2 2 - 8 9 4 三角形浸染方法 s t r a b e r19 9 9 ) r o s s i n a c ( r o s s i g n a c 4 1 9 9 9 ) 2 2 2 几何压缩算法 由于连通性信息仅几个b p v ，并且连通性信息压缩己几乎达到极致，所以 几何信息压缩直到它成为影响网格压缩的主要因素，近来才引起人们的重视， 在单分辨率压缩算法中，由于连通性信息是离散的网格属性，因此对连通性信 息压缩都是无损压缩，而对几何信息压缩便进行有损压缩。为了得到顶点位置 间的相关性，大多数单分辨率压缩算法对几何信息的压缩都分三个步骤：对顶 点位置进行预量化，预测量化位置，对预测残差进行商编码。 1 、标量量化 对未压缩的网格来说，每个顶点的坐标信息需要i e e e3 2 b i t 浮点型数据表 示，然而在大多数应用中，这个精度远大于人眼的分辨率，因此可以在不影响 视觉的情况下适度量化顶点的坐标信息以达到压缩目的。量化技术可分为均匀 量化和非均匀量化两种( b h a t ta n ds h a h2 0 0 2 ) ，均匀量化的每个量化单元都是 相同的长度，均匀量化比非均匀量化简单并且计算效率高，但失真率大于非均 匀量化。大多数几何信息编码方法将顶点信息量化为8 1 6 b i t ( d e e r i n g1 9 9 5 ： t a u b i na n dr o s s i g n a c1 9 9 8 ：t o u m aa n dg o t s m a n1 9 9 8 ：b a j a j ，p a s c u c c ie t a 1 1 9 9 9 ) 。 第2 章3 d 网格甩堆原理 ! 、 _ 1 _ 。 列l 丽序的坐标信邑进行量亿后对顶点的位置进行预测编码，预测编码利 用相2 e 项点之间的相关性进行编码，鹾方法往往可以减少大量的几何数掘。 个好的预测策略可以产生高度不均衡分却的预测误差，接着使用h u f f m a n 编码 或者算术编码方法等熵编码万洼对预测误差进行编码。预测方法包括预测、 线性预删、平行四边形预测和二阶预测等。如果选择合适的系数，所有的预测 方2 去最后都可转换为简单的线性预测。 预测相邻的两个顶点坐标值相差甚微( 即值很小) 在 d e e r in g ( d e e r i n g1 9 9 5 ) 和c h o w ( c h o wt 9 9 7 ) 的算法中，都是根据值的直方圈 使用不同长度的码长对值进行编码。 线性预测一t a u b i n 和8 0 s s i g n a c ( t a u b j na n dr o s s i g n a c1 9 9 8 ) 提出了线 性预测方法，该方法是基于顶点分裂树的，每个顶点的位置是通过该顶点的祖 f 先节点进行预测的，用公式表示为：v ，= 丑v 。+ ( h ) ，其中 ，z ：， 的 选择依据是均方误差f 忙( 。l i2 卜, i t v 。一( j v ) n 最小。 i iil _ 平行四边形预测t o u m a 和g o t s m a n ( t o u m aa n d6 0 t s m a n1 9 9 8 ) 中使用的 一种预测策略。如图29 所示：为预测目标顶点r ，首先将图中己编码的三角 形f “，n ，) 放入激活列表，平行四边形预测法就是假设顶点r ，“，v ，w 构成一 个平行四边形这样顶点r 就可以用公式一= v + 一w 来预测，然而该方法只有 在四个项点几乎在同一平面式才有效，因此为提高预测的准确性可将两个三 角形( 虬v 。w ) 和虬v ) 之间的夹角口作为预测依据。 激活列表 f i g 29 平行四边形与4 策略示意图 r r 、 第2 章3 d 网格压缩原理 二阶预测分支顶点的坐标直接编码，而轮廓上的顶点通过二次预测编 码，该方法共分两步：第一步，计算、量化相邻两个顶点坐标间的差值，这一 步相当于预测：第二步，计算不同量化编码差异。实验证明二阶预测比预 测更为有效。 3 、矢量量化 矢量量化( v q ) 与传统方法的不同之处在于，传统的量化方法是首先使用 括量量化器进行预量化，然后对量化后的坐标进行预测编码，而矢量量化是首 先预测顶点的位置，然后将三部分的预测残差共同进行压缩编码，这样，就可 以充分利用不同顶点坐标之间的相关成分。与标量量化相比，矢量量化的优点 在于它具有更高r d 率，并且量化单元的选择更加自由。 2 3 多分辨率压缩算法 多分辨率压缩又称渐进压缩，它是在带宽有限的网络中传输复杂网格的必 然趋势。渐进网格先传输粗糙网格，接着传输细化信息，在接收端可利用细化 信息逐步细化网格，直到恢复的网格达到它原始的分辨率或者用户终止传输为 止，即渐进网格压缩有不同的细节层( l o d ) ，且压缩率与细节层数此消彼长。 总的来说，由于多分辨率压缩不能像单分辨率压缩那样充分利用顶点之间的相 关性，因此多分辨率压缩效率要小于单分辨率压缩。 想要对3 d 网格进行渐进压缩编码，首先要将网格进行简化处理，使用 ( h e c k b e r ta n dg a r l a n d1 9 9 7 ：c i g n o n i ，m o n t a n ie ta 1 1 9 9 8 ：l u e b k e2 0 0 1 ) 简化方法将网格简化为基础网格( 即粗糙网格) ，并且记录下每一步简化操作( 即 细节信息) ，这样在接收端就可以根据已记录的简化操作将网格逐步恢复成原始 网格，因此渐进压缩编码可以看成是对基础网格和对简化操作的编码。 在许多渐进压缩方法中，对几何信息和连通性信息的压缩方法与单分辨率 压缩方法类似，然而新提出的渐进压缩算法的连通性信息与几何压缩相关联的， 因此可将渐进压缩方法分为连通性驱动和几何驱动两种。 2 3 1 连通性驱动压缩算法 l 、渐进网格( p m ) h o p p e 首次提出渐进网格( p m ) 的概念( h o p p e1 9 9 6 ) ，该方法将给定的定 向流形网格进行连续的边塌缩操作，如图2 1 0 所示。当发生边塌缩时，塌缩边 的两个顶点合并为一个顶点，塌缩边对应的两个三角形面被移除，所有与塌缩 边顶点相邻的顶点都与合并后的顶点v 。相邻。边塌缩的逆操作便是顶点分裂。 第2 章3 d 网格乐缩原理 图2 1 0 边塌缩与顶点分裂示意图 一个原始的网格m = m r 经过k 次连续的边塌缩操作后被简化为基础网格 m 。，每一次边塌缩将m ，简化为m 川，( i = 1 , 2 ，k ) ，由于每个边塌缩操作都 是可逆的，因此可以使用一个基础网格和一系列顶点分裂操作来表示一个网格， 而每一次顶点分裂操作可将m 一恢复为m ，( f _ 1 , 2 ，k ) ，这样就可以用 ( m o ，v 础f 1 ，v 枷f 2 ，v s p l i t k ) 来表示一个渐进网格。 在渐进网格的构造过程中，每一次边塌缩都要谨慎选择塌缩边，h o p p e 在 ( h o p p e1 9 9 9 ) 中的算法中引入方程e 计算距离精度、属性精度、j 下规化和结构 面曲线等。首先将网格的所有边放入一个优先级序列，该序列中每条边的优先 级值分别是他们的估计能量开销丝，初始化时，先计算每一条边的优先级，然 后选择优先级值最小的一条边e 塌缩，接着更新e 的相邻边的优先级值。 基础网格m 。可用单分辨率编码方法进行编码，图2 1 0 可用分裂顶点v 。和 所有两边相邻顶点v 一口v ，来表示，如果当前网格m ，有v ，个顶点，那么可使用 l 0 9 2v ，个b i t 对分裂顶点1 ，的索引值进行编码，使用l o g ：( p ( p 1 ) ) b i t ( 其中， 为与1 ，。的相邻的顶点数) 对v ，和，的索引值进行编码。由于一般网格每个顶 点的平均价态大约为6 ，因此v ，和，的索引值使用大约5 ( l o g ，( 6 乖5 ) ) b i t 即可，那么整个网格就需要( 1 0 9 ，1 ，。+ 5 ) b i t 来表述顶点分裂操作。总体上说， 拥有v 个顶点的p m 需