海量3D点云数据压缩与空间索引技术  

Data compression and spatial indexing technology for massive 3D point cloud

作　　者：赵尔平[1] 刘炜[1] 党红恩[1] 

机构地区：[1]西藏民族大学信息工程学院,陕西咸阳712082

出　　处：《计算机应用》2018年第1期146-151,193,共7页journal of Computer Applications

基　　金：国家自然科学基金资助项目(61762082);西藏自治区自然科学基金资助项目(12KJZRYMY07)~~

摘　　要：针对3D模型中海量点云数据压缩与空间索引低效问题和漫游过程中相邻两次查询窗口重叠是大概率事件问题,提出邻点差值渐进压缩和基于裁剪重叠区域进行冗余处理的R树空间索引方法。首先,利用八叉树对3D模型进行空间剖分,借助Morton码对每个叶节点管理的点云数据排序,按照R树叶节点的外接立方体大小对数据进行分块,计算块内相邻点数据差值,以块为单位渐进压缩差值,批量读取这些数据块创建R树;其次,借助上次查询窗口范围计算本次查询有效范围;最后,给出基于R树索引的点云数据查询方法。该方法使点云数据压缩率提高了26.61个百分点,并能实现流式传输,同时减少了I/O开销,使其查询性能提高了35.44%,数据冗余减少了16.49个百分点。实验结果表明,所提方法在3D虚拟旅游、数字城市等系统具中有明显优势。Concerning the problems that compression and spatial index for point cloud data in 3D model are inefficient and overlapping of two adjacent query windows is a large probability event in the process of roaming, the methods of Adjacent Point Difference Progressive Compression （APDPC） and R-tree spatial index for processing redundants based on trimming overlapped regions were proposed. Firstly, spatial subdivision of 3D model was done by an octree, the point cloud data managed by each leaf node was sorted by means of Morton codes, the data was partitioned according to outer cube size of R- tree leaf node, the data difference between adjacent points in the block was calculated, the difference was progressively compressed by using blocks as units, reading the data blocks in batches to create the R-tree. Secondly, the valid range of this query was calculated with the scope of the last query window. Finally, the query method of point cloud data based on R-tree index was given. This method improved the compression rate of point cloud data by 26.61 percentage points, and could realize streaming transmission. Meanwhile, it effectively reduced I/O overhead, the query performance was improved by 35.44%, and data redundancy was reduced by 16.49 percentage points. The experimental results show that the proposed methods have obvious advantages in 3D virtual travel, digital city and other systems.

关 键 词：虚拟旅游 3D点云数据 差值压缩 动态索引 R树 

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