基于八叉树的三维室内地图数据快速检索方法

doi:10.11772/j.issn.1001-9081.2018071646

计算机应用 ›› 2019, Vol. 39 ›› Issue (1): 82-86.DOI: 10.11772/j.issn.1001-9081.2018071646

• 2018年全国开放式分布与并行计算学术年会(DPCS 2018)论文 • 上一篇下一篇

基于八叉树的三维室内地图数据快速检索方法

吕宏武¹, 付俊强¹, 王慧强¹, 李冰洋¹, 袁泉², 陈诗军², 陈大伟²

1. 哈尔滨工程大学计算机与科学技术学院, 哈尔滨 150001;
2. 中兴通讯股份有限公司, 广东深圳 518055

收稿日期:2018-07-19 修回日期:2018-08-28 出版日期:2019-01-10 发布日期:2019-01-21
通讯作者: 付俊强
作者简介:吕宏武(1983-),男,山东日照人,讲师,博士,CCF会员,主要研究方向:可用性、性能评价、云计算;付俊强(1994-),男,辽宁沈阳人,硕士研究生,主要研究方向:分布式与并行计算、体系结构;王慧强(1960-),男,黑龙江哈尔滨人,教授,博士,CCF会员,主要研究方向:网络安全、未来网络;李冰洋(1978-),男,黑龙江哈尔滨人,副教授,博士,主要研究方向:可信计算、网络可靠性;袁泉(1962-),男,江西赣州人,高级工程师,博士,主要研究方向:工业自动化;陈诗军(1972-),男,山东烟台人,高级工程师,硕士,主要研究方向:无线定位、MIMO、信道仿真;陈大伟(1984-),男,黑龙江绥化人,高级工程师,硕士,主要研究方向:无线铁路集群、铁路综合数字移动通信系统(GSM-R)、铁路通用移动通信技术的长期演进(LTE-R)。
基金资助:
国家科技重大专项（2016ZX03001023-005）；中央高校基本科研业务费专项（HEUCF100601）；中兴产学研合作项目（2016ZTE01-03-06）；中兴通讯产学研合作论坛项目（2018ZTE）。

Fast retrieval method of three-dimensional indoor map data based on octree

LYU Hongwu¹, FU Junqiang¹, WANG Huiqiang¹, LI Bingyang¹, YUAN Quan², CHEN Shijun², CHEN Dawei²

1. College of Computer Science and Technology, Harbin Engineering University, Harbin Heilongjiang 150001, China;
2. Zhongxing Telecommunication Equipment Corporation, Shenzhen Guangdong 518055, China

Received:2018-07-19 Revised:2018-08-28 Online:2019-01-10 Published:2019-01-21
Supported by:
This work is partially supported by the National Science and Technology Major Project (2016ZX03001023-005), the Fundamental Research Funds for the Central Universities (HEUCF100601), the ZTE Industry, University and Research Cooperation Project (2016ZTE01-03-06), the ZTE Industry, University and Research Cooperation Forum Project (2018ZTE).

摘要/Abstract

摘要： 针对室内三维地图中数据检索效率不高的问题，提出了一种基于八叉树的室内三维地图数据检索方法。首先，根据八叉树的场景分割方法对数据进行存储；然后，对数据进行编码以方便寻址；其次，为数据添加房间隔断约束条件对检索数据进行筛选；最后，对室内地图数据进行检索。与不具有约束条件的搜索方法相比，搜索代价平均降低了25个百分点，且搜索时间更加稳定。所提方法可以显著地提高室内三维地图数据的应用效率。

关键词: 三维室内地图, 地图数据, 八叉树, 邻居搜索, 封闭性约束

Abstract: To solve the low efficiency problem of data retrieval in indoor three-dimensional (3D) maps, an indoor 3D map data retrieval method based on octree was proposed. Firstly, the data was stored according to the octree segmentation method. Secondly, the data was encoded to facilitate addressing. Thirdly, the search data was filtered by adding a room interval constraint to the data. Finally, the indoor map data was retrieved. Compared with the search method without constraints, the search cost of the proposed method was reduced by 25 percentage points on average, and the search time was more stable. Therefore, the proposed method can significantly improve the application efficiency of indoor 3D map data.

Key words: 3D indoor map, map data, octree, neighbor search, closedness constraint

中图分类号:

TP391

吕宏武, 付俊强, 王慧强, 李冰洋, 袁泉, 陈诗军, 陈大伟. 基于八叉树的三维室内地图数据快速检索方法[J]. 计算机应用, 2019, 39(1): 82-86.

LYU Hongwu, FU Junqiang, WANG Huiqiang, LI Bingyang, YUAN Quan, CHEN Shijun, CHEN Dawei. Fast retrieval method of three-dimensional indoor map data based on octree[J]. Journal of Computer Applications, 2019, 39(1): 82-86.

参考文献

[1] 张永玉,马劲松.3DGIS中线性八叉树空间索引的建立与查询算法研究[J].计算机工程与科学,2009,31(2):61-63.(ZHANG Y Y, MA J S. Research on establishment and query algorithm of linear octal tree spatial index in 3DGIS[J]. Computer Engineering and Science, 2009, 31(2):61-63.)
[2] MEAGHER D. Geometric modeling using octree encoding[J]. Computer Graphics and Image Processing, 1982, 19(2):129-147.
[3] MEAGHER D. The octree encoding method for efficient solid modeling[D]. Troy, NY:Rensselaer Polytechnic Institute, 1982.
[4] AIZAWA K, TANAKA S. A constant-time algorithm for finding neighbors in quadtrees[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009, 31(7):1178-1183.
[5] VO A V, TRUONG-HONG L, LAEFER D F, et al. Octree-based region growing for point cloud segmentation[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2015, 104:88-100.
[6] VESPA E, NIKOLOV N, GRIMM M, et al. Efficient octree-based volumetric SLAM supporting signed-distance and occupancy mapping[J]. IEEE Robotics and Automation Letters, 2018, 3(2):1144-1151.
[7] WANG K, FU H, PENG S, et al. A RDF data compress model based on octree structure[C]//Proceedings of the 201712th IEEE Conference on Industrial Electronics and Applications. Piscataway, NJ:IEEE, 2017:990-994.
[8] WONG H T T, HUANG Y, TSANG S C, et al. Real-time model slicing in arbitrary direction using octree[C]//Proceedings of the ACM 44th International Conference on Computer Graphics and Interactive Technique. New York:ACM, 2017:Article No. 9.
[9] PAVEZ E, CHOU P A. Dynamic polygon cloud compression[C]//Proceedings of the 2017 IEEE International Conference on Acoustics, Speech and Signal Processing. Piscataway, NJ:IEEE, 2017:2936-2940.
[10] GÓMEZ-PAU Á, BALADO L, FIGUERAS J. Detectability of structural defects using octree encoding[C]//Proceedings of the 201732nd Conference on I/Design of Circuits and Integrated Systems. Piscataway, NJ:IEEE, 2017:1-6.
[11] UMMENHOFER B, BROX T. Global, dense multiscale recon-struction for a billion points[C]//Proceedings of the 2015 IEEE International Conference on Computer Vision. Piscataway, NJ:IEEE, 2015:1341-1349.
[12] STEINBRVCKER F, STURM J, CREMERS D. Volumetric 3D mapping in real-time on a CPU[C]//Proceedings of the 2014 IEEE International Conference on Robotics and Automation. Piscataway, NJ:IEEE, 2014:2021-2028.
[13] WANG P S, LIU Y, GUO Y X, et al. O-CNN:octree-based convolutional neural networks for 3D shape analysis[J]. ACM Transactions on Graphics, 2017, 36(4):72.
[14] SCHRACK G. Finding neighbors of equal size in linear quadtrees and octrees in constant time[J]. CVGIP:Image Understanding, 1992, 55(3):221-230.
[15] NAMDARI M H, HEJAZI S R, PALHANG M. MCPN, octree neighbor finding during tree model construction using parental neighboring rule[J]. 3D Research, 2015, 6(3):29.
[16] 王永志,杨路生,廖丽霞,等.八叉树与三维R树集成的激光点云数据存储结构[J].地球信息科学学报,2017,19(5):587-594.(WANG Y Z, YANG L S, LIAO L X, et al. Laser point cloud data storage structure integrated with octree and 3D R-tree[J]. Journal of Earth Information Science, 2017, 19(5):587-594.)
[17] 付仲良,刘思远,田宗舜,等.基于多级R-tree的分布式空间索引及其查询验证方法研究[J].测绘通报,2012(11):42-46.(FU Z L, LIU S Y, TIAN Z S, et al. Research on distributed spatial index and its query verification method based on multi-level R-tree[J]. Bulletin of Surveying and Mapping, 2012(11):42-46.)
[18] 肖怡,李佳田,张文靖,等.一种自然邻近关系查询的空间索引结构[J].地理信息世界,2018,25(1):32-38.(XIAO Y, LI J T, ZHANG W J, et al. A spatial index structure of natural neighbor relational query[J]. Geomatics World, 2018, 25(1):32-38.)

基于八叉树的三维室内地图数据快速检索方法

Fast retrieval method of three-dimensional indoor map data based on octree

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	钟文彬, 孙思, 李旭瑞, 刘光帅. 结合密度阈值和三角形组逼近的点云压缩方法[J]. 计算机应用, 2020, 40(7): 2059-2068.
[2]	赵宏, 刘向东, 杨永娟. 基于RGB-D图像的室内机器人同时定位与地图构建[J]. 计算机应用, 2020, 40(12): 3637-3643.
[3]	席志红, 王洪旭, 韩双全. 基于ORB-SLAM2系统的快速误匹配剔除算法与地图构建[J]. 计算机应用, 2020, 40(11): 3289-3294.
[4]	杜振林, 唐卫清, 覃力, 李士才. 基于八叉树的大规模流程工厂模型细节裁剪算法[J]. 计算机应用, 2017, 37(9): 2626-2630.
[5]	刘晙, 袁培燕, 李永锋. 基于完整可见性模型的改进鲁棒OctoMap[J]. 计算机应用, 2017, 37(5): 1445-1450.
[6]	林辉灿, 吕强, 王国胜, 张洋, 梁冰. 基于VSLAM的自主移动机器人三维同时定位与地图构建[J]. 计算机应用, 2017, 37(10): 2884-2887.
[7]	彭伟李建新闫镔童莉陈健管士勇. 基于最优化分块的大规模数据体绘制加速方法[J]. 计算机应用, 2011, 31(08): 2221-2224.
[8]	马晓晨孔小利. 基于深度八叉树的三维数据场LOD可视化[J]. 计算机应用, 2010, 30(1): 47-49.
[9]	甘建红彭强戴培东张天宇王正敏. 基于元胞自动机的肿瘤生长形态动态模拟[J]. 计算机应用, 2009, 29(07): 1906-1909.
[10]	黄淼张海朝李超. 基于八叉树空间分割的k近邻搜索算法[J]. 计算机应用, 2008, 28(8): 2046-2048.
[11]	王文玺肖世德孟文董鸿. 一种基于八叉树空间剖分技术的光线跟踪算法[J]. 计算机应用, 2008, 28(3): 656-658.
[12]	王元佶陈闳中. MSCR树：一种移动终端电子地图索引结构[J]. 计算机应用, 2008, 28(10): 2561-2564.
[13]	智明郑姨婷. HLODs模型在场景快速绘制中的应用[J]. 计算机应用, 2007, 27(9): 2126-2128.
[14]	王嘉苏红旗. 基于数据包络的点模型简化方法的研究[J]. 计算机应用, 2007, 27(2): 355-357.
[15]	吕广宪潘懋王占刚丛威青. 面向体数据的虚拟八叉树模型研究[J]. 计算机应用, 2006, 26(12): 2856-2859.