대용량 포인트 클라우드 데이터에 대한 분산 및 병렬 OC-Tree 색인 방법 : Distributed and Parallel OC-Tree Indexing Method for Massive Point Cloud Data

다국어 초록 (Multilingual Abstract)

Abstract
Title : Distributed and Parallel OC-Tree Indexing
Method for Massive Point Cloud Data

Point clouds are often too large to fit into memory as a whole and therefore have to be processed using out-of-core algorithms. One possible out-of-core option is to split the data into multiple tiles and process one or a few tiles at a time. This approach works well for processing, but for visualizations it is often desired to display the whole data set and not only a few tiles at a time. Storing various levels of detail of the original model in a hierarchical space-partitioning data structure allows a point cloud renderer to quickly load and display the relevant parts of a point cloud. Regions that are close to the camera are rendered at a higher level of detail than distant regions, and regions that are outside of the view frustum are discarded entirely.
Variations of OC-tree and Kd-tree are two popular space-partitioning structures for the rendering of large point clouds. Some variations store subsamples of the original point cloud. Others store the original data in leaf nodes and down sampled averages or the bounding volume of a subtree in inner nodes. We have chosen a structure that subsamples the original point cloud, because it does not create new points that require additional disk space, and because it allows users to do point picking and measurements on original, unaltered, data at any zoom level, without the need to wait until a leaf node is loaded.
Problems of existing indexing methods are single system based algorithms, limits of storage and processing time. In this paper, we propose a fast indexing method for large amount of point cloud data in distributed and parallel environments. In order to obtain maximum parallelism, chunking is performed on the 3D point cloud. Then each chunk is distributed to multiple nodes, and indexing is performed on each chunk in parallel. Finally, the global index is constructed by merging the indexes for each created chunk. We implement the proposed indexing method based on Spark-Yarn and evaluate its performance through experiments.
Contributions of this dissertation are first we want to perform Fast indexing method for large amount of point cloud data in Distributed and Parallel environments. Distributed and Parallel indexing and search method was implemented based on Apache Spark. Finally experiments have to show scalability.
We compared single system method to our proposed method that distributed and parallel method. The experiment was done with 2.7 billion point cloud data on “Affandi” museum. We have shown that it is possible to generate fast OC-tree indexing for large 3D point clouds on the Distributed and Parallel environment, and over 3 billion points was executed in 9.6 minutes with high quality random sampling method. 10 thousand random point position search execution was over 3 minute.

목차 (Table of Contents)

• I. Introduction 1
• 1. 3D point cloud and applications 1
• 2. LOD 5
• 3. Problems of existing indexing methods of 3D point cloud 7
• 4. Approaches of proposed method and contribution 12
• 5. Organization of dissertation work 12
• II. Related work 14
• 1. Sort Algorithms 14
• 2. Point cloud LOD structure 19
• 3. OC-tree indexing method 21
• 4. Distributed and Parallel computing 31
• 5. Apache Spark on Hadoop 35
• III. Proposed Distributed and Parallel OC-tree Indexing Method 37
• 1. Architecture of Proposed Method 37
• 2. Chunking manager 38
• 3. Z-ordering manager 41
• 4. Merge manager 43
• 5. Indexing manager 45
• 6. Subsampling manager 48
• 7. Search manager 51
• IV. Performance Evaluation 53
• 1. Experimental environment 53
• 2. Experimental result 55
• V. Conclusion 64
• References 66
• Appendix 72
• Appendix 78
• Acknowledgement 82

참고문헌 (Reference)

1 C. Scheiblauer, "Interactions with Gigantic Point Clouds ,", vol 9-11/186, 2014

2 T. M. Chan, "Further Results on Colored Range Searching ,", pp . 28:1-28:15 ,, 2020