基于八叉树的三维室内地图数据快速检索方法
|
摘要
针对室内三维地图中数据检索效率不高的问题,提出了一种基于八叉树的室内三维地图数据检索方法。首先,根据八叉树的场景分割方法对数据进行存储;然后,对数据进行编码以方便寻址;其次,为数据添加房间隔断约束条件对检索数据进行筛选;最后,对室内地图数据进行检索。与不具有约束条件的搜索方法相比,搜索代价平均降低了25个百分点,且搜索时间更加稳定。所提方法可以显著地提高室内三维地图数据的应用效率。
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.
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.
引文
[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 2017 12th 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]GMEZ-PAU, BALADO L, FIGUERAS J. Detectability of structural defects using octree encoding[C]//Proceedings of the2017 32nd Conference on I/Design of Circuits and Integrated Systems. Piscataway, NJ:IEEE, 2017:1-6.
[11]UMMENHOFER B, BROX T. Global, dense multiscale reconstruction for a billion points[C]//Proceedings of the 2015 IEEE International Conference on Computer Vision. Piscataway, NJ:IEEE, 2015:1341-1349.
[12]STEINBRCKER F, STURM J, CREMERS D. Volumetric 3D mapping in real-time on a CPU[C]//Proceedings of the 2014IEEE 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 Rtree[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.)
[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 2017 12th 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]GMEZ-PAU, BALADO L, FIGUERAS J. Detectability of structural defects using octree encoding[C]//Proceedings of the2017 32nd Conference on I/Design of Circuits and Integrated Systems. Piscataway, NJ:IEEE, 2017:1-6.
[11]UMMENHOFER B, BROX T. Global, dense multiscale reconstruction for a billion points[C]//Proceedings of the 2015 IEEE International Conference on Computer Vision. Piscataway, NJ:IEEE, 2015:1341-1349.
[12]STEINBRCKER F, STURM J, CREMERS D. Volumetric 3D mapping in real-time on a CPU[C]//Proceedings of the 2014IEEE 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 Rtree[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.)