计算机科学 ›› 2017, Vol. 44 ›› Issue (10): 171-176.doi: 10.11896/j.issn.1002-137X.2017.10.032

• 软件与数据库技术 • 上一篇    下一篇

虚拟旅游中海量3D点云数据的细节层次索引技术研究

赵尔平,党红恩,刘炜   

  1. 西藏民族大学信息工程学院 咸阳712082,西藏民族大学信息工程学院 咸阳712082,西藏民族大学信息工程学院 咸阳712082
  • 出版日期:2018-12-01 发布日期:2018-12-01
  • 基金资助:
    本文受国家自然科学基金(41361044),西藏自治区自然科学基金(12KJZRYMY07)资助

Research on Detail Level Index Technology of Massive 3D Point Cloud Data in Virtual Tourism

ZHAO Er-ping, DANG Hong-en and LIU Wei   

  • Online:2018-12-01 Published:2018-12-01

摘要: 虚拟旅游中的3D点云数据特别庞大,批量索引成为了当今的研究热点。许多索引树存在兄弟结点空间区域重叠、不能实现细节层次索引、索引效率低等问题。为此,将点数据反射强度和细节层次技术引入R树,在改进R树的基础上提出LODR树。建树前,将点云数据进行排序、分组、去除空间重叠等预处理。树的每层设有不同反射强度阈值,把叶结点中满足阈值条件的索引记录沿父-祖父-曾祖父的家谱关系上移,并插入对应的非叶结点,利用该方法创建细节层次索引树。利用反射强度控制数据冗余,棱锥裁剪技术实现查询优化。实验结果表明,LODR树在细节层次索引、查询效率等方面具有明显优势。

关键词: 虚拟旅游,3D点云数据,细节层次,索引结构

Abstract: D point cloud data in virtual tourism are particularly huge and the batch index has become a research hotspot.There are some problems in many index trees,such as spatial overlap of sibling node,not achieving level of detail index and low indexing efficiency.Therefore,point data reflection intensity and level of detail technology were introduced into R-tree,and LODR-tree was presented based on improved R-tree.Before establishing this tree,point cloud data needs to be pre-processed,such as sorting,grouping,removing spatial overlap and so on.The index records which meet the thre-shold conditions in the leaf nodes are inserted into the homologous non-leaf nodes along the parent-grandfather-great grandfather family relationship,and LOD index tree is created by this method.Data redundancy is controlled by reflected intensity,and query optimization is achieved by pyramid cutting technology.Finally,experiments show that LODR-tree has obvious advantages in LOD index and query efficiency.

Key words: Virtual tourism,3D point cloud data,Level of detail,Index structure

[1] MERRY B,GAIN,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.
[2] LIN J H,NOOSHABADI S,AHMADI M.Parallel Randomized KD-tree Forest on GPU Cluster for Image Descriptor Matching[C]∥ Proceedings of 2016 IEEE International Symposium on Circuits and Systems.New York:IEEE Press,2016:582-585.
[3] RIZKI P N M,PARK J,OH S,et al.STR-Octree IndexingMethod for Processing LiDAR Data[C]∥ Proceedings of IEEE SENSORS 2015.New York:IEEE Press,2015:1-4.
[4] YANG H,QI W T,GAO X F.Efficient R-Tree Based Indexing Scheme for Server-Centric Cloud Storage System[J].IEEE Transactions on Knowledge and Data Engineering,2016,8(6):1503-1571.
[5] HE Z W,WU C L,WANG C.Clustered Sorting R-tree:An Index for Multi-Dimensional Spatial Objects[C]∥ Proceedings of 2008 Fourth International Conference on Natural Computation.New York:IEEE Press,2008:348-351.
[6] SUN W B,WANG Z P,LIU X L,et al.The Method for Indexing Global-scale 3D Vector Data with R-tree Based on Approxi-mate Prism[C]∥ Proceedings of The 18th International Confe-rence on Geoinformatics:GI-Science in Change.New York:IEEE Press,2010:1-4.
[7] SHARIFZADEH M,SHAHABI C.VoR-Tree:Rtrees with Vo-ronoi Diagrams for Efficient Processing of Spatial Nearest Neighbor Queries[J].VLDB Journal,2010,3(1):1231-1242.
[8] OSMANKOVIC D,SUPIC H,VELAGIC J.Performance andquality assessment of R-tree based nearest neighbour search in the scalar field mapping technique[C]∥Proceedings of the 2013 39th Annual Conference of the IEEE Industrial Electronics So-ciety.New York:IEEE Press,2013:2455-2459.
[9] ACHAKEEV D,SEEGER B,WIDMAYER P.Sortbased Query-adaptive Loading of R-trees[C]∥ Proceedings of 2012 the 21st ACM International Conference on Information and Knowledge Management.New York:ACM,2012:2080-2084.
[10] ZHANG J,PAN H,YUAN Z M.A Novel Spatial Index for Case based Geographic Retrieval[C]∥Proceedings of 2009 International Conference on Interaction Sciences.New York:ACM,2009:342-347.
[11] PATEL P,GARG D.Perfect Hashing Base R-tree for Multiple Queries[C]∥ Proceedings of 2014 IEEE International Advance Computing Conference.New York:IEEE Press,2014:636-640.
[12] GONG J,ZHANG H W.A Method for LOD Generation of 3D City Model Based on Extended 3D RTree Index[C]∥ Procee-dings of 2011 Eighth International Conference on Fuzzy Systems and Knowledge Discovery.New York:IEEE Press,2011:2004-2008.
[13] LI J,JING N,SUN M Y.A Mechanism of Implementing Visuali-zation with Level of Detail at Multiscale[J].Journal of Software,2002,3(10):2037-2043.(in Chinese) 李军,景宁,孙茂印.多比例尺下细节层次可视化的实现机制[J].软件学报,2002,3(10):2037-2043.
[14] 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,2(1):177-184.(in Chinese) 邓红艳,武芳,翟仁健,等.一种用于空间数据多尺度表达的 R 树索引结构[J].计算机学报,2009,2(1):177-184.
[15] ACHAKEEV D,SEIDEMANN M,SCHMIDT M,et al.Sort-based Parallel Loading of R-trees[C]∥ Proceedings of the 1st ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data.New York:ACM,2012:62-70.
[16] YOU S M,ZHANG J T,GRUENWALD L.Parallel SpatialQuery Processing on GPUs Using R-Trees [C]∥Proceedings of the 2nd ACM Sigspatial International Workshop on Analytics for Big Geospatial Data.New York:ACM,2013:23-31.
[17] TAO Y F,YANG Y,HU X C,et al.Instance level worst-case query bounds on R-trees[J].The VLDB Journal,2014,3(4):591-607.
[18] YIN K X,HUANG H,ZHANG H,et al.Morfit:InteractiveSurface Reconstruction from Incomplete Point Clouds with Curve-Driven Topology and Geometry Control[J].ACM Transa-ctions on Graphics,2014,33(6):1-12.
[19] SONG J,LI T T,ZHU Z L.Research on I/O Cost of MapReduce Join[J].Journal of Software,2015,6(6):1438-1456.(in Chinese) 宋杰,李甜甜,朱志良.MapReduce连接查询的I/O代价研究[J].软件学报,2015,6(6):1438-1456.
[20] WANG C K,MENG X F.Relational Query Techniques for Distributed Data Stream:A Survey[J].Chinese Journal of Compu-ters,2016,39(1):80-96.(in Chinese) 王春凯,孟小峰.分布式数据流关系查询技术研究[J].计算机学报,2016,39(1):80-96.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75, 88 .
[2] 夏庆勋,庄毅. 一种基于局部性原理的远程验证机制[J]. 计算机科学, 2018, 45(4): 148 -151, 162 .
[3] 厉柏伸,李领治,孙涌,朱艳琴. 基于伪梯度提升决策树的内网防御算法[J]. 计算机科学, 2018, 45(4): 157 -162 .
[4] 王欢,张云峰,张艳. 一种基于CFDs规则的修复序列快速判定方法[J]. 计算机科学, 2018, 45(3): 311 -316 .
[5] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 .
[6] 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究[J]. 计算机科学, 2018, 45(4): 83 -88 .
[7] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 .
[8] 刘琴. 计算机取证过程中基于约束的数据质量问题研究[J]. 计算机科学, 2018, 45(4): 169 -172 .
[9] 钟菲,杨斌. 基于主成分分析网络的车牌检测方法[J]. 计算机科学, 2018, 45(3): 268 -273 .
[10] 史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法[J]. 计算机科学, 2018, 45(4): 94 -99, 116 .