A Hybrid Spatial Indexing Structure of Massive Point Cloud Based on Octree and 3D R*-Tree
Source abstract
Abstract
The spatial index structure is one of the most important research topics for organizing and managing massive 3D Point Cloud. As a point in Point Cloud consists of Cartesian coordinates (x,y,z), the common method to explore geometric information and features is nearest neighbor searching. An efficient spatial indexing structure directly affects the speed of the nearest neighbor search. Octree and kd-tree are the most used for Point Cloud data. However, octree or KD-tree do not perform best in nearest neighbor searching. A highly balanced tree, 3D R*-tree is considered the most effective method so far. So, a hybrid spatial indexing structure is proposed based on octree and 3D R*-tree. In this paper, we discussed how thresholds influence the performance of nearest neighbor searching and constructing the tree. Finally, an adaptive way method adopted to set thresholds. Furthermore, we obtained a better performance in tree construction and nearest neighbor searching than octree and 3D R*-tree.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: 3D Shape Modeling and Analysis · Data Management and Algorithms · Remote Sensing and LiDAR Applications
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
College of Computer Science and Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, China
School of Advanced Manufacturing Engineering, Chongqing University of Posts and Telecommunications, Chongqing 400065, China
Advanced Manufacturing and Automatization Engineering Laboratory, Chongqing University of Posts and Telecommunications, Chongqing 400065, China
Funding
National Natural Science Foundation of China
References (36)
Show source-provided references
1. Imad, M., Doukhi, O., and Lee, D.J. (2021). Transfer Learning Based Semantic Segmentation for 3D Object Detection from Point Cloud. Sensors, 21.10.3390/s21123964 ↗
2. Qi, C.R., Su, H., and Mo, K. (2017, January 21–26). PointNet: Deep Learning on Point Sets for 3D Classification and Segmentation. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Honolulu, HI, USA.
3. Gang, Z., Wang, M., and Yi, X. (2017, January 10–12). Research on spatial index structure of massive point clouds based on hybrid tree. Proceedings of the 2017 IEEE 2nd International Conference on Big Data Analysis (ICBDA), Beijing, China.10.1109/ICBDA.2017.8078792 ↗
4. Oct-trees and their use in representing three-dimensional objects10.1016/0146-664X(80)90055-6 ↗
5. Multidimensional binary search trees used for associative searching10.1145/361002.361007 ↗
6. Guttman, A. (1984, January 18–21). R-trees: A dynamic index structure for spatial searching. Proceedings of the 1984 ACM SIGMOD International Conference on Management of Data, Boston, MA, USA.10.1145/602259.602266 ↗
7. Miltiadou, M., Grant, M., Campbell, N.D., Warren, M., and Hadjimitsis, D. (2021). Open source software DASOS: Efficient accumulation, analysis, and visualisation of full-waveform lidar. Remote Sens., 13.
8. Quad trees a data structure for retrieval on composite keys10.1007/BF00288933 ↗
9. Dricot, A., and Ascenso, J. (2019, January 2–6). Hybrid Octree-Plane Point Cloud Geometry Coding. Proceedings of the 2019 27th European Signal Processing Conference (EUSIPCO), Coruna, Spain.10.23919/EUSIPCO.2019.8902800 ↗
10. Dricot, A., Pereira, F., and Ascenso, J. (2018, January 7–10). Rate-Distortion Driven Adaptive Partitioning for Octree-Based Point Cloud Geometry Coding. Proceedings of the 2018 25th IEEE International Conference on Image Processing (ICIP), Athens, Greece.10.1109/ICIP.2018.8451172 ↗
11. Massive Point Cloud Space Management Method Based on Octree-Like Encoding10.1007/s13369-019-03968-7 ↗
12. Beckmann, N., and Kriegel, H.-P. (1990, January 23–25). The R*-Tree: An efficient and robust access method for points and rectangles. Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, Atlantic, NJ, USA.10.1145/93597.98741 ↗
13. Sellis, T.K., and Roussopoulos, N. (1987, January 1–4). The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. Proceedings of the 13th International Conference on Very Large Data Bases, San Francisco, CA, USA. Available online: http://hdl.handle.net/1903/4541.
14. Kamel, I., and Faloutsos, C. (1994, January 12–15). Hilbert R-Tree: An improved R-tree using fractals. Proceedings of the 20th International Conference on Very Large Data Bases, San Francisco, CA, USA. Available online: http://hdl.handle.net/1903/5366.
15. A method of organizing point clouds based on linear KD tree
16. Robinson, J.T. (May, January 29). The K-D-B-tree: A search structure for large multidimensional dynamic indexes. Proceedings of the 1981 ACM SIGMOD International Conference on Management of Data, New York, NY, USA.10.1145/582319.582321 ↗
17. A New Method of Hybrid Index for Mobile LiDAR Point Cloud Data
18. Sun, Y., Zhao, T., and Yoon, S. (2021). A Hybrid Approach Combining R*-Tree and k-d Trees to Improve Linked Open Data Query Performance. Appl. Sci., 11.10.3390/app11052405 ↗
19. Geological tetrahedral model-oriented hybrid spatial indexing structure based on octree and 3D R*-tree
20. OctreeNet: A Novel Sparse 3-D Convolutional Neural Network for Real-Time 3-D Out-door Scene Analysis10.1109/TASE.2019.2942068 ↗
21. Data compression and spatial indexing technology for massive 3D point cloud
22. Database-oriented storage based on LMDB and linear octree for massive block model10.1016/S1003-6326(16)64377-7 ↗
23. Manipulating images by using run-length Morton codes10.1142/S0218001497000408 ↗
24. Linear transformation of pictures represented by quad trees10.1016/0146-664X(79)90008-X ↗
25. Representations for space planning10.1145/362258.362281 ↗
26. Geometric modeling and computer vision10.1109/5.5966 ↗
27. Yang, S.N., and Lin, T.W. (1991, January 27–30). A new linear octree construction by filling algorithms. Proceedings of the 10th Annual International Phoenix Conference on Computers and Communications, IEEE Computer Society, Scottsdale, AZ, USA.
28. 3-D shape measurement based on complementary Gray-code light10.1016/j.optlaseng.2011.06.024 ↗
29. Knott, G.D. (1971, January 1–2). A balanced tree storage and retrieval algorithm. Proceedings of the 1971 International ACM SIGIR Conference on Information Storage and Retrieval, College Park, MD, USA.10.1145/511285.511305 ↗
30. R-trees for organizing and visualizing 3D GIS databases10.1002/1099-1778(200007)11:3<129::AID-VIS227>3.0.CO;2-T ↗
31. Brakatsoulas, S., Pfoser, D., and Theodoridis, Y. (2002, January 8–11). Revisiting R-Tree Construction Principles. Proceedings of the East European Conference on Advances in Databases and Information Systems, Bratislava, Slovakia.10.1007/3-540-45710-0_13 ↗
32. Moten, D. (2019, October 13). 3D R-Tree in Java. Available online: https://github.com/davidmoten/rtree-3d.
33. (2013, September 02). table_scene_lms400. Available online: https://raw.github.com/PointCloudLibrary/data/master/tutorials/table_scene_lms400.pcd.
34. Hierarchical octree and kd tree grids for 3D radiative transfer simulations10.1051/0004-6361/201322593 ↗
35. Jaillet, F., and Lobos, C. (2021). Fast Quadtree/octree adaptive meshing and re-meshing with linear mixed elements. Eng. Comp., 1–18.10.1007/s00366-021-01330-w ↗
36. Roussopoulos, N., Kelley, S., and Vincent, F. (1995, January 22–25). Nearest neighbor queries. Proceedings of the 1995 ACM SIGMOD International Conference on Management of data, San Jose, CA, USA.10.1145/223784.223794 ↗