基于局部最小生成树的点模型快速无损压缩算法  

A Fast and Lossless Compression Algorithm for Point-Based Models Based on Local Minimal Spanning Tree

作　　者：王鹏杰[1,2] 潘志庚[1] 徐明亮[1,3] 刘勇奎[2] 

机构地区：[1]CAD＆CG国家重点实验室浙江大学杭州310027 [2]大连民族学院计算机科学与工程学院辽宁大连116600 [3]郑州大学信息工程学院郑州450001

出　　处：《计算机研究与发展》2011年第7期1263-1268,共6页Journal of Computer Research and Development

基　　金：国家“八六三”高技术研究发展计划重点基金项目(2009AA062704);中央高校基本科研业务专项基金项目(DC10040113,DC10040111)

摘　　要：点模型数据往往非常庞大,需要对这些数据高效压缩以方便进行存储和网络传输.提出了一个高效快速的点模型无损压缩算法.首先将点模型表面切分成多个小面块;以每个块为单位,生成最小生成树并按宽度优先顺序对树形结构进行编码,同时沿树形结构预测.最后,将预测值与真实值分解成符号位、指数和尾数3个部分,分别做差并在各自的上下文中用算数编码压缩.算法在压缩时间和压缩率两项指标上超过以往的点模型无损压缩算法.可以作为点模型压缩算法的一个有益补充,用来对精度要求高的工程数据进行压缩.Point-based graphics has become one of the hottest topics in 3D computer graphics recently. Since point-based models are often too large to be stored and transferred in limited hardware and bandwidth easily, it is necessary to design effective compression methods. We propose an efficient and fast lossless geometry compression algorithm for point-based models. Firstly, point-sampled surface is split into many equal sized surface patches. Over the points of each patch, a minimal spanning tree is constructed and encoded in breadth first order. During this process, each point is predicted from its father in the spanning tree. Then both predicted and actual positions are broken into sign, exponent and mantissa, and their corrections are separately compressed by using arithmetic coding in the different contexts. The achieved bit-rate and time usage in our algorithm outperforms the previous lossless compression methods of point-based models. Our algorithm nicely complements those lossy compression algorithms of point-based models, and it can be used under the situation where lossy compression is not preferred.

关 键 词：基于点的图形学 算术编码 最小生成树 无损压缩 线性预测 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]