A Comparison of 3D R-tree and Octree to Index Large Point Clouds from a 3D Terrestrial Laser Scanner

Abstract

본 연구에서는 3차원 지상 레이저 스캐너로부터 취득된 대용량 포인트 클라우드로부터 효과적인 포인트 탐색을 수행하기 위한 인덱싱 방법으로서 3D R-tree와 옥트리를 비교하였다. 포인트 클라우드의 각 포인트로부터 일정 거리 이내의 포인트를 조회하는 방식으로 탐색을 수행하였으며, 탐색 시간 및 메모리 사용량을 측정하였다. 실제 건물과 석탑을 대상으로 취득된 포인트 클라우드에 적용한 결과, 옥트리는 3D R-tree에 비하여 생성 및 탐색 속도가 우수하며 3D R-tree는 보다 메모리 효율적임을 확인할 수 있었다. 3D R-tree는 인덱스 용량과 리프 용량이, 옥트리는 계층 수가 탐색 성능을 좌우함을 확인하였으며, 주어진 자료에 대한 최적의 수치를 도출할 수 있었다. The present study introduces a comparison between 3D R-tree and octree which are noticeable candidates to index large point clouds gathered from a 3D terrestrial laser scanner. A query method, which is to find neighboring points within given distances, was devised for the comparison, and time lapses for the query along with memory usages were checked. From tests conducted on point clouds scanned from a building and a stone pagoda, it was shown that octree has the advantage of fast generation and query while 3D R-tree is more memory-efficient. Both index and leaf capacity were revealed to be ruling factors to get the best performance of 3D R-tree, while the number of level was of oetree.