中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 中科院软件所  > 中科院软件所
题名:
三维网格拓扑压缩技术的研究
作者: 刘迎
答辩日期: 2007-06-07
授予单位: 中国科学院软件研究所
授予地点: 软件研究所
学位: 博士
关键词: 网格 ; 拓扑压缩 ; 霍夫曼编码 ; 算术编码 ; 解码 ; 外存模型
其他题名: Study on Connectivity Compression Techniques for 3D Meshes
摘要: 随着计算机图形学技术在现实生活中的普及,计算机图形学的研究领域越来越广泛。近些年,越来越多的大规模三维网格数据在各应用领域,如电子商务、医疗、科学计算可视化、工程分析和游戏等领域随处可见。对于规模巨大的三维网格数据,如果其庞大的数据量在运算时无法一次全部被装入到通用的计算机的内存中,我们称这类超大规模的三维数据模型为外存模型;能够一次全部被装入到内存中的三维网格模型,我们称其为内存模型。不论是外存模型还是内存模型,三维网格模型都具有数据量庞大的特点。三维网格数据的庞大数据量,使得网格压缩算法研究在计算机图形学领域的地位越来越重要。 如果从三维网格模型的数据类型来分类,则三维网格数据可分为几何数据(如顶点坐标)、拓扑数据(顶点间是否有边连接等信息)和属性数据(如颜色、法向量、纹理等信息)。对这些类型的数据作高效的压缩是三维网格压缩领域各算法研究的内容。对于目前的三维网格压缩算法,用于压缩几何数据的算法被称为几何压缩算法;因为属性数据和几何数据性质相似,目前都采用几何压缩方法来压缩属性数据;对拓扑数据作压缩的算法被称为拓扑压缩算法。所以,对目前所有的三维网格压缩算法,如果按处理数据类型来分类,则只分为几何压缩算法和拓扑压缩算法。有的网格压缩算法能够同时压缩所有类型数据,在分类上一般就把该算法同时归为两类。 本文研究的所有算法都属于三维网格拓扑压缩算法。各种三维网格拓扑压缩算法的压缩处理流程总体上可分成两大部分:1)采用某种网格遍历方法得到三维网格模型的拓扑(信息)流;2)采用某种熵编码方法压缩1)步骤得到的拓扑流。本文针对三维网格拓扑压缩的这两个部分分别展开了深入的研究。 本文主要贡献和创新点具体表现为如下工作:(在本文中,如果没有特别指出,压缩算法都是只针对内存模型而言。) 1. 完成了基于上下文的熵编码算法,该算法可普遍适用于各种三维网格拓扑压缩算法中的熵编码部分。新的算法在各种网格遍历算法基础上,提出了一种具有普遍性的熵编码方法,也就是说我们尝试提出一种适合所有三维网格拓扑压缩算法的熵编码方法。现有的三维网格拓扑压缩算法的熵编码部分多采用霍夫曼编码(早几年)或算术编码(近几年),且算术编码的结果要好于霍夫曼编码结果。本文的熵编码算法不是霍夫曼编码,也不是算术编码,而是二者的组合:先霍夫曼编码,再利用基于上下文的算术编码来编码霍夫曼编码结果。采用新算法分别压缩各种三维网格拓扑压缩算法中的拓扑流,其压缩比要好于各自直接采用自适应算术编码得到的压缩比,更好于各自用霍夫曼方法得到的压缩比。 2. 完成了基于模版的高效新颖的熵编码算法。该算法针对三角网格模型作拓扑压缩,算法首先遍历三角形网格模型的每个三角形,得到操作符序列(拓扑流);然后对得到的操作符序列的每个操作符作基于可变模版的自适应算术编码。在编码过程中,根据当前编码操作符的一个计算得到的模版来确定当前操作符的编码表示(一个二进制串);然后对当前编码操作符的这个二进制表示的每个比特作自适应算术编码。该算法尽可能地利用网格遍历特点来预测当前编码操作符,使得三角网格拓扑信息的压缩效果非常好,对大多数网格模型,得到的压缩结果比目前公认的压缩比最好的算法的压缩结果还要好。 3. 完成了两种网格遍历方法的改进。对于目前的三维网格拓扑压缩算法,其大多数网格遍历方法中存在着“分割”网格模型的操作,而这个“分割”操作非常影响最终的压缩比和网格解码的高效性。针对于此,本文提出了两种改进网格遍历的方法:1)提出了一种自适应网格遍历方法,使得到的拓扑流中尽量少地出现“分割”操作符,可有效提高最终的压缩比;2)用“跳”操作来替代“分割”操作,使得网格解码可一次遍历完成,实现三维网格编码/解码的并行操作,提高了解码的效率。 4. 完成基于Marching Cubes重组的外存模型渐进压缩算法。该算法是针对外存模型的一种渐进压缩方法,能高效地压缩外存模型,并进行多分辨率的传输和显示。目前的外存模型压缩算法都是单一分辨率的,而我们的这个算法是第一个多分辨率(渐进式)压缩外存模型的算法。该算法对外存模型先做基于Marching Cubes的重组;对重组结果作分块和基于八叉树的层次化组织;最后广度优先遍历全局八叉树并采用基于上下文的算术编码方法完成外存模型渐进压缩。试验表明,该方法对外存模型的压缩比达到了与处理内存模型相似的压缩比,高于目前的外存模型压缩方法,是第一个能渐进压缩外存模型的方法。
英文摘要: Due to the popularization of Computer Graphics in our life, the research on Computer Graphics becomes of more significance. In recent years, there are lots of 3D mesh data in all kinds of application fields, such as electronic commerce, medicine, science visualization, engineering analysis and game industry. One feature of 3D mesh data is its large size. The large size of data makes the research on mesh compression technique very important. According to the type of 3D mesh data, there exist geometry data (vertex coordinates etc.), connectivity data (the connection between vertexes) and attribute data (color, normal, texture etc.). By the mesh compression, we mean the compression to the data as mentioned above. The existing mesh compression algorithms used to compress geometry data are called geometry compression algorithms. The characters of attribute data are similar to those of geometry data. So geometry compression methods can be used to compress attribute data. The mesh compression algorithms used to compress connectivity data are called connectivity compression algorithms. In terms of the type of data to compress, all existing 3D mesh compression algorithms can be classified as geometry compression algorithms and connectivity compression algorithms. Some mesh compression algorithms, which can be used to compress both geometry and connectivity data, belong to both categories. All algorithms proposed in this article belong to 3D mesh connectivity compression methods. Each 3D mesh Connectivity compression algorithm includes two parts. One is to obtain operator series by using some kind of mesh-traversal method, and the other is to compress the operator series by using certain kind of entropy coding method. In this article, we profoundly study both parts. The thesis focuses on the study on 3D mesh connectivity compression algorithms. Its contributions and research novelties are mainly in the following aspects: 1. We present a general efficient algorithm for entropy encoding connectivity information of mesh. On the basic of mesh-traversing method, an efficient entropy encoding method is proposed. The new method can be applied to almost all the existing connectivity compression methods. In other words, we propose a general entropy encoding method for mesh connectivity compression. All the current connectivity compression algorithms use Huffman coder (in early years) or arithmetic coding method (in recent years) to compress operator series. The result of arithmetic coding method is better than the one by Huffman coder. Our entropy coding method is neither Huffman coder nor arithmetic coding method, but the combination of the two methods. First, Huffman coder is used to compress operator series. Then context-based arithmetic coding method is used to compress the result from the Huffman coder. The compression ratio by using our entropy encoding method is better than the one by directly using arithmetic coding method or Huffman coder. 2. We present an efficient and novel entropy compression algorithm for encoding the connectivity information of triangular meshes. By the method, all triangles are traversed first to obtain operator series. Then a variable code-mode based arithmetic coder is applied to encode the operator series. For every currently encoded operator, a code-mode is calculated first and a binary strand representing this operator is obtained according to its code-mode. When the binary strands for all the operators in the operator series are obtained, an adaptive arithmetic coder is employed to encode all the bits. This algorithm exploits the property of mesh-traversal method to predict the operator currently encoded, so the compression performance is excellent, with its ratio higher than the one by the best algorithm in the aspect of compression ratio. 3. We propose two methods for improving mesh-traversal process. For most connectivity algorithms, the mesh-traversal methods in these algorithms use “split” operators, which entail the usage of memory in mesh decoding and affect the final compression ratio. For settling this question, two methods of improving mesh traversal were proposed in this article. One is an adaptive mesh-traversal method applied to make “split” operators to occur as less as possible, to improve the final compression ratio. The other method is to replace the “split” operations by “jump” operations. The scheme allows the decoding process to be completed in one pass and the parallel encoding and decoding process to be realized for on-line applications. 4. We present a progressive out-of-core compression method based on reconstruction with Marching Cubes. To our knowledge, all the existing out-of-core compression algorithms are in single resolution, which does not allow a progressive compression to be conducted. In this aspect, we proposed a novel algorithm to progressively compress out-of-core models in high efficiency and transmit/render the models in multi-resolution. By the method, first, mesh is reconstructed by using a Marching-Cube based method. Then a layered organization is formed on the basis of uniformly dividing the box of model and octree technique. Finally, the nodes of the octree of the whole model can be traversed progressively from coarse (top) to fine (bottom) and compress the traversed result by using a context based arithmetic coding method. Experimental results show that this new method can compress the out-of-core models in similar compression ratio as the advanced method to compress the in-core models. It is also superior to the existing methods for compressing out-of-core models and is the first method for performing progressive compression for out-of-core models
语种: 中文
内容类型: 学位论文
URI标识: http://ir.iscas.ac.cn/handle/311060/7306
Appears in Collections:中科院软件所

Files in This Item:
File Name/ File Size Content Type Version Access License
10001_200318015003117刘迎_paper.pdf(3974KB)----限制开放-- 联系获取全文

Recommended Citation:
刘迎. 三维网格拓扑压缩技术的研究[D]. 软件研究所. 中国科学院软件研究所. 2007-06-07.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[刘迎]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[刘迎]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2017  中国科学院软件研究所 - Feedback
Powered by CSpace