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

doi:10.11772/j.issn.1001-9081.2017061489

计算机应用 ›› 2018, Vol. 38 ›› Issue (1): 146-151.DOI: 10.11772/j.issn.1001-9081.2017061489

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

赵尔平, 刘炜, 党红恩

西藏民族大学信息工程学院, 陕西咸阳 712082

收稿日期:2017-06-16 修回日期:2017-08-31 出版日期:2018-01-10 发布日期:2018-01-22
通讯作者: 赵尔平
作者简介:赵尔平(1976-),男,陕西彬县人,副教授,硕士,主要研究方向:数据库、数据融合;刘炜(1978-),男,陕西咸阳人,副教授,博士,主要研究方向:数据库、地理信息系统;党红恩(1978-),男,陕西合阳人,讲师,硕士,主要研究方向:数据库。
基金资助:
国家自然科学基金资助项目（61762082）；西藏自治区自然科学基金资助项目（12KJZRYMY07）。

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

ZHAO Erping, LIU Wei, DANG Hong'en

College of Information Engineering, Xizang Minzu University, Xianyang Shaanxi 712082, China

Received:2017-06-16 Revised:2017-08-31 Online:2018-01-10 Published:2018-01-22
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61762082), the Natural Science Foundation of Tibet (12KJZRYMY07).

摘要/Abstract

摘要： 针对3D模型中海量点云数据压缩与空间索引低效问题和漫游过程中相邻两次查询窗口重叠是大概率事件问题，提出邻点差值渐进压缩和基于裁剪重叠区域进行冗余处理的R树空间索引方法。首先，利用八叉树对3D模型进行空间剖分，借助Morton码对每个叶节点管理的点云数据排序，按照R树叶节点的外接立方体大小对数据进行分块，计算块内相邻点数据差值，以块为单位渐进压缩差值，批量读取这些数据块创建R树；其次，借助上次查询窗口范围计算本次查询有效范围；最后，给出基于R树索引的点云数据查询方法。该方法使点云数据压缩率提高了26.61个百分点，并能实现流式传输，同时减少了I/O开销，使其查询性能提高了35.44%，数据冗余减少了16.49个百分点。实验结果表明，所提方法在3D虚拟旅游、数字城市等系统具中有明显优势。

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

Abstract: 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.

Key words: virtual tourism, 3D point cloud data, difference compression, dynamic indexing, R-tree

中图分类号:

TP392

赵尔平, 刘炜, 党红恩. 海量3D点云数据压缩与空间索引技术[J]. 计算机应用, 2018, 38(1): 146-151.

ZHAO Erping, LIU Wei, DANG Hong'en. Data compression and spatial indexing technology for massive 3D point cloud[J]. Journal of Computer Applications, 2018, 38(1): 146-151.

参考文献

[1] MIRK D, HLAVACS H. Virtual tourism with drones:experiments and lag compensation[C]//Proceedings of the First Workshop on Micro Aerial Vehicle Networks, Systems, and Applications for Civilian Use. New York:ACM, 2015:40-45.
[2] NING X J, ZHANG X P, WANG Y H, et al. Segmentation of architecture shape information from 3D point cloud[C]//VRCAI09:Proceedings of the 8th International Conference on Virtual Reality Continuum and Its Applications in Industry. New York:ACM, 2009:127-132.
[3] MERRY B, GAIN J, MARAIS P. Fast in-place binning of laser range-scanned point sets[J]. ACM Journal on Computing and Cultural Heritage, 2013, 6(3):1-19.
[4] MORELL V, ORTS S, CAZORLA M, et al. Geometric 3D point cloud compression[J]. Pattern Recognition Letters, 2014, 50(2014):55-62.
[5] SMITH J, PETROVA G, SCHAEFER S. Full progressive encoding and compression of surfaces generated from point cloud data[J]. Computers & Graphics, 2012, 36(5):341-348.
[6] HUANG Y, PENG J L, KUO J, et al. A generic scheme for progressive point cloud coding[J]. IEEE Transactions on Visualization & Computer Graphics, 2008, 14(2):440-453.
[7] CAI K Y, JIANG W F, MA T, et al. Probability model-adaptive coding of point clouds with octree decomposition[C]//Proceedings of SIGGRAPH Asia 2011 Posters. New York:ACM, 2011:Article No. 33.
[8] COHEN R A, TIAN D, VETRO A. Point cloud attribute compression using 3-D intra prediction and shape-adaptive transforms[C]//DCC'16:Proceedings of 2016 Data Compression Conference. Piscataway, NJ:IEEE, 2016:141-150.
[9] DAI C Q, CHEN M, FANG X Y. Compression algorithm of 3D point cloud data based on octree[J]. The Open Automation and Control Systems Journal, 2015, 7(8):879-883.
[10] SONG W W, CAI S L, YANG B, et al. A reduction method of three-dimensional point cloud[C]//BMEI2009:Proceedings of the 20092nd International Conference on Biomedical Engineering and Informatics. Piscataway, NJ:IEEE, 2009:1-4.
[11] CHOVANEC P, KRATKY M, WALDER J. Lossless R-tree compression using variable-length codes[C]//Proceedings of the 5th International Conference for Internet Technology and Secured Transactions. Piscataway, NJ:IEEE, 2010:1-8.
[12] GUTTMAN A. R-trees:a dynamic index structure for spatial searching[C]//SIGMOD'84:Proceedings of the 1984 ACM SIGMOD International Conference on Management of Data. New York:ACM, 1984:47-57.
[13] CHALLA J S, GOYAL P, NIKHIL S. A concurrent k-NN search algorithm for R-tree[C]//Proceedings of the 8th Annual ACM India Conference. New York:ACM, 2015:123-128.
[14] PATEL P, GARG D. Perfect hashing base R-tree for multiple queries[C]//Proceedings of 2014 IEEE International Advance Computing Conference. Piscataway, NJ:IEEE, 2014:636-640.
[15] HE Z W, WU C L, WANG C. Clustered sorting R-tree:an index for multi-dimensional spatial objects[C]//ICNC2008:Proceedings of 2008 Fourth International Conference on Natural Computation. Piscataway, NJ:IEEE, 2008:348-351.
[16] NOLEN M, LIN K I. Approximate high-dimensional nearest neighbor queries using R-forests[C]//Proceedings of the 17th International Database Engineering & Applications Symposium. New York:ACM, 2013:48-57.
[17] SHARIFZADEH M, SHAHABI C. VoR-tree:R-trees with Voronoi diagrams for efficient processing of spatial nearest neighbor queries[C]//Proceedings of the 36th International Conference on Very Large Data Bases. Singapore:VLDB Endowment, 2010:1231-1242.
[18] PATEL P, GARG D D. Perfect hashing base R-tree for multiple queries[C]//IACC2014:Proceedings of the 2014 IEEE International Advance Computing Conference. Piscataway, NJ:IEEE, 2014:636-640.
[19] GONG J, ZHANG H W. A method for LOD generation of 3D city model based on extended 3D Rtree index[C]//FSKD2011:Proceedings of the 2011 Eighth International Conference on Fuzzy Systems and Knowledge Discovery. Piscataway, NJ:IEEE, 2011:2004-2008.
[20] 邓红艳,武芳,翟仁健,等.一种用于空间数据多尺度表达的R树索引结构[J].计算机学报,2009,32(1):177-184.(DENG H Y, WU F, ZHAI R J, et al. R-tree index structure for multi-scale representation of spatial data[J]. Chinese Journal of Computers, 2009,32(1):177-184.)
[21] DRAISMA J, HOROBE E, OTTAVIANI G. The Euclidean distance degree[C]//Proceedings of the 2014 Symposium on Symbolic-Numeric Computation. New York:ACM, 2014:9-16.
[22] LEE K C, LE W C, ZHENG B H, et al. Z-SKY:an efficient skyline query processing framework based on Z-order[J]. The VLDB Journal, 2010, 19(3):333-362.
[23] WITTEN I H, NEAL R M, CLEARY J G. Arithmetic coding for data compression[J]. Communications of the ACM, 1987, 30(6):520-540.
[24] ZHANG R, QI J Z, STRADLING M, et al. Towards a painless index for spatial objects[J]. ACM Transactions on Database Systems, 2014, 39(3):19-41.
[25] YI K. The priority R-tree[J]. SIGSPATIAL Special, 2012, 4(2):8-12.
[26] 宋杰,李甜甜,朱志良,等.MapReduce连接查询的I/O代价研究[J].软件学报,2015,26(6):1438-1456.(SONG J, LI T T, ZHU Z L, et al. Research on I/O cost of MapReduce join[J]. Journal of Software, 2015, 26(6):1438-1456.)

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

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	段宗涛, 龚学辉, 唐蕾, 陈柘. 共享交通的时空轨迹检索与群体发现[J]. 计算机应用, 2019, 39(1): 220-226.
[2]	侯海耀, 钱育蓉, 英昌甜, 张晗, 卢学远, 赵燚. 基于Hilbert-R树分级索引的时空查询算法[J]. 计算机应用, 2018, 38(10): 2869-2874.
[3]	李松, 李林, 王淼, 崔环宇, 张丽平. RTC树的构建与不确定近邻关系查询方法[J]. 计算机应用, 2015, 35(1): 115-120.
[4]	梁银董永权. 基于对象集合的空间关键词查询[J]. 计算机应用, 2014, 34(7): 1992-1996.
[5]	刘维群李元臣. 时延约束的链路选择平衡优化组播路由算法[J]. 计算机应用, 2011, 31(04): 925-927.
[6]	肖晖李清泉. 移动对象数据库索引研究综述[J]. 计算机应用, 2010, 30(4): 1064-1067.
[7]	杨春德康欢丁亚南. 新的基于MPH的时延约束Steiner树算法[J]. 计算机应用, 2010, 30(11): 3056-3058.
[8]	李元臣刘维群. 时延受限组播路由的最短路径加速算法求解[J]. 计算机应用, 2010, 30(05): 1176-1178.
[9]	李元臣刘维群. 基于共享边的时延约束组播路由算法[J]. 计算机应用, 2009, 29(11): 2901-0903.
[10]	杨璇刘怡光唐振营刘浩. Hilbert packed R树在空中交通管制GIS显示中的研究与应用[J]. 计算机应用, 2009, 29(09): 2589-2592.
[11]	王元佶陈闳中. MSCR树：一种移动终端电子地图索引结构[J]. 计算机应用, 2008, 28(10): 2561-2564.
[12]	梁银4 张虹. 一种多路空间距离连接查询处理方法[J]. 计算机应用, 2008, 28(1): 155-158.
[13]	吴春婧秦继林* 郑明春 . 传感器网络中一种基于数据融合树的低功耗路由算法[J]. 计算机应用, 2006, 26(8): 1793-1795.
[14]	陈云亮杨捷康立山 . 求解动态组播路由问题的混合优化遗传算法[J]. 计算机应用, 2006, 26(8): 1947-1949.
[15]	赵宗渠，庄雷，李建春. 利用索引的动态分布改善JXTA网络中查询效率[J]. 计算机应用, 2005, 25(02): 289-290.