최근 3차원 지상 레이저 스캐너의 성능이 고도로 향상됨에 따라 취득된 측점들로 구성된 포인트 클라우드의 용량도 급격히 증가하고 있다. 본 연구는 3차원 지상 레이저 스캐너로부터 취득한 대용량 포인트 클라우드로부터 옥트리를 생성하고 측점을 질의하기 위한 선행 연구의 파일 참조 옥트리 방식을 개선하는 것을 목표로 한다. 이를 위하여 메인 메모리에 구현된 옥트리의 리프 노드에는 첫 번째 측점의 파일 포인터만을 저장하였다. 아울러 동일한 리프 노드에 속하는 측점들이 연속적으로 기록되도록 포인트 클라우드 파일을 재구성하였다. 약 3억 개의 측점으로 구성된 포인트 클라우드로부터 옥트리를 생성하고 일련의 측점 주위로 일정 반경 안에 존재하는 측점들에 대한 질의 시간을 측정하였다. 결과적으로 옥트리의 생성 시간, 저장과 복원 시간, 질의 시간 및 메모리 사용량 등 모든 면에서 제안한 방식이 기존 방식에 비하여 향상된 성능을 나타내었다. 특히 질의 속도는 2배 이상, 메모리 효율성은 4배 이상 증가하였다. 따라서 본 연구는 선행 연구의 방식을 명백히 향상시켰다고 판단할 수 있다. 아울러 메인 메모리의 크기를 크게 상회하는 초대용량 포인트 클라우드로부터 옥트리를 구성하고 측점을 질의하는 것이 가능할 것으로 판단된다.
최근 3차원 지상 레이저 스캐너의 성능이 고도로 향상됨에 따라 취득된 측점들로 구성된 포인트 클라우드의 용량도 급격히 증가하고 있다. 본 연구는 3차원 지상 레이저 스캐너로부터 취득한 대용량 포인트 클라우드로부터 옥트리를 생성하고 측점을 질의하기 위한 선행 연구의 파일 참조 옥트리 방식을 개선하는 것을 목표로 한다. 이를 위하여 메인 메모리에 구현된 옥트리의 리프 노드에는 첫 번째 측점의 파일 포인터만을 저장하였다. 아울러 동일한 리프 노드에 속하는 측점들이 연속적으로 기록되도록 포인트 클라우드 파일을 재구성하였다. 약 3억 개의 측점으로 구성된 포인트 클라우드로부터 옥트리를 생성하고 일련의 측점 주위로 일정 반경 안에 존재하는 측점들에 대한 질의 시간을 측정하였다. 결과적으로 옥트리의 생성 시간, 저장과 복원 시간, 질의 시간 및 메모리 사용량 등 모든 면에서 제안한 방식이 기존 방식에 비하여 향상된 성능을 나타내었다. 특히 질의 속도는 2배 이상, 메모리 효율성은 4배 이상 증가하였다. 따라서 본 연구는 선행 연구의 방식을 명백히 향상시켰다고 판단할 수 있다. 아울러 메인 메모리의 크기를 크게 상회하는 초대용량 포인트 클라우드로부터 옥트리를 구성하고 측점을 질의하는 것이 가능할 것으로 판단된다.
Recently, the size of point cloud is increasing rapidly with the high advancement of 3D terrestrial laser scanners. The study aimed for improving a file-referring octree, introduced in the preceding study, which had been intended to generate an octree and to query points from a large point cloud, ga...
Recently, the size of point cloud is increasing rapidly with the high advancement of 3D terrestrial laser scanners. The study aimed for improving a file-referring octree, introduced in the preceding study, which had been intended to generate an octree and to query points from a large point cloud, gathered by 3D terrestrial laser scanners. To the end, every leaf node of the octree was designed to store only one file-pointer of its first point. Also, the point cloud file was re-constructed to store points sequentially, which belongs to a same leaf node. An octree was generated from a point cloud, composed of about 300 million points, while time was measured during querying proximate points within a given distance with series of points. Consequently, the present method performed better than the preceding one from every aspect of generating, storing and restoring octree, so as querying points and memorizing usage. In fact, the query speed increased by 2 times, and the memory efficiency by 4 times. Therefore, this method has explicitly improved from the preceding one. It also can be concluded in that an octree can be generated, as points can be queried from a huge point cloud, of which larger than the main memory.
Recently, the size of point cloud is increasing rapidly with the high advancement of 3D terrestrial laser scanners. The study aimed for improving a file-referring octree, introduced in the preceding study, which had been intended to generate an octree and to query points from a large point cloud, gathered by 3D terrestrial laser scanners. To the end, every leaf node of the octree was designed to store only one file-pointer of its first point. Also, the point cloud file was re-constructed to store points sequentially, which belongs to a same leaf node. An octree was generated from a point cloud, composed of about 300 million points, while time was measured during querying proximate points within a given distance with series of points. Consequently, the present method performed better than the preceding one from every aspect of generating, storing and restoring octree, so as querying points and memorizing usage. In fact, the query speed increased by 2 times, and the memory efficiency by 4 times. Therefore, this method has explicitly improved from the preceding one. It also can be concluded in that an octree can be generated, as points can be queried from a huge point cloud, of which larger than the main memory.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
따라서 본 연구는 Han(2014b)의 방식을 개선하여 색인 가능한 포인트 클라우드의 용량을 늘리고 질의 성능을 향상시키는 것을 목표로 한다. 이를 위하여 각 리프 노드에 저장되는 파일 포인터의 수를 1개로 제한하고 동일한 리프 노드에 속하는 측점들이 연속적으로 기록되도록 포인트 클라우드 파일을 재구성함으로써, 옥트리 생성에 필요한 메인 메모리의 크기와 측점에 대한 질의 시간을 줄일 수 있는 방식을 제안하였다.
본 연구에서는 3차원 지상 레이저 스캐너로부터 취득한 대용량 포인트 클라우드로부터 옥트리를 생성하고 측점을 질의하기 위한 선행 연구의 파일 참조 옥트리 방식을 개선하였다. 이를 위하여 메인 메모리에 구현된 옥트리의 리프 노드에는 첫 번째 측점의 파일 포인터만을 저장하고, 동일한 리프 노드에 속하는 측점들이 연속적으로 기록되도록 포인트 클라우드 파일을 재구성하였다.
제안 방법
본 연구에서 제시한 방식을 3차원 지상 레이저 스캐너로 터널에서 취득한 포인트 클라우드에 적용하여 옥트리 생성과 저장 및 복원, 질의 성능 등을 Han(2014b)의 방식과 비교하였다. 포인트 클라우드의 제원은 Table 1과 같으며 처리 시스템의 사양은 Table 2와 같다.
본 연구에서는 포인트 클라우드 파일을 재구성하여 Fig. 2 와 같이 동일한 리프 노드에 속하는 측점들을 파일 상의 연속한 위치에 기록하고 리프 노드에는 첫 번째 측점에 대한 파일 포인터만을 저장하는 방식을 제안한다. 이를 위하여 리프 노드의 변수는 Fig.
것을 목표로 한다. 이를 위하여 각 리프 노드에 저장되는 파일 포인터의 수를 1개로 제한하고 동일한 리프 노드에 속하는 측점들이 연속적으로 기록되도록 포인트 클라우드 파일을 재구성함으로써, 옥트리 생성에 필요한 메인 메모리의 크기와 측점에 대한 질의 시간을 줄일 수 있는 방식을 제안하였다.
개선하였다. 이를 위하여 메인 메모리에 구현된 옥트리의 리프 노드에는 첫 번째 측점의 파일 포인터만을 저장하고, 동일한 리프 노드에 속하는 측점들이 연속적으로 기록되도록 포인트 클라우드 파일을 재구성하였다. 결과적으로 옥트리의 생성 시간, 저장과 복원 시간, 질의 시간 및 메모리 사용량 등 모든 면에서 제안한 방식이 향상된 성능을 나타내었다.
주어진 좌표 또는 주위에 존재하는 측점을 질의하기 위해 먼저 주어진 좌표를 포함하는 리프 노드를 질의한다. 해당 리프 노드에 속하는 측점의 수 nPoint에 맞게 배열을 생성하고 첫 측점의 파일 포인터 offset_begin가 가리키는 위치로부터 측점들을 일괄적으로 읽어 배열에 저장한다.
포인트 클라우드의 제원은 Table 1과 같으며 처리 시스템의 사양은 Table 2와 같다. 질의 성능을 평가하기 위해 일련의 측점 주위로 일정 반경 안에 존재하는 측점들에 대한 질의 시간을 측정하였다. Han(2014b)의 연구에서는 옥트리를 구성하는 자식 노드의 분화 심도를 나타내는 목표 단계(level)와 노드 리프의 형상 비율(tl: 가로, 세로, 높이 중 최대, 최소의 비율) 에다양한 값을 적용했지만, 본 연구에서는 Han(2014b)의 연구에서 비교적 우수한 질의 성능과 메모리 사용량을 나타낸 목표 단계 10과 형상 비율 3으로만 실험을 진행하였다.
2 파일 재구성’의 두 가지 단계를 수행한다. 파일재구성이 완료되면 ‘2.2.3 측점의 질의’와 같이 옥 트리로부터 측점을 질의하는 방식을 제안한다.
포인트 클라우드 파일을 재구성하기 위하여 기존의 포인트 클라우드 파일과 동일한 용량의 빈 파일(null file)을 생성한다. 다음으로 포인트 클라우드의 각 측점이 속하는 리프 노드를 모의 옥트리로부터 질의하여 offset_begin 값과 offset 값을 받아 Eq.
대상 데이터
전체 포인트 클라우드의 0.01%에 해당하는 30, 053개의 측점으로부터 반경 0.05m 내부에 존재하는 측점을 질의하였으며 Han(2014b)과 본 연구에서 제안한 방식이 동일하게 17, 554, 511개의 측점을 찾아내었다. 옥트리 생성과 파일 재구성 시간, 옥트리 저장 및 복원 시간, 질의 시간과 메인 메모리사용량을 측정하였으며 그 결과는 Table 3과 같다.
성능/효과
이를 위하여 메인 메모리에 구현된 옥트리의 리프 노드에는 첫 번째 측점의 파일 포인터만을 저장하고, 동일한 리프 노드에 속하는 측점들이 연속적으로 기록되도록 포인트 클라우드 파일을 재구성하였다. 결과적으로 옥트리의 생성 시간, 저장과 복원 시간, 질의 시간 및 메모리 사용량 등 모든 면에서 제안한 방식이 향상된 성능을 나타내었다. 특히 질의 속도는 2 배 이상, 메모리 효율성은 4배 이상 증가하였다.
44초로 34%가 단축되었고, 옥트리 저장 시간과 복원 시간은 각각 88%와 84%가 단축되었다. 기존 방식은 모든 측점에 대한 파일 포인터를 옥트리의 리프 노드에 저장하므로 옥 트리 생성 시간이 길고 옥트리 자체의 크기가 커서 저장 및 복원 시간이 많이 소요되었으나 제안한 방식은 리프 노드 당 1 개의 파일 포인터만을 저장하므로 상기와 같은 결과가 나타났다고 볼 수 있다. 질의 시간은 기존 방식이 546.
한편, Han(2014a)과 Han(2014b)의 연구에서는 매 측점에 서로 다른 파일 포인터를 이용하여 접근했을 뿐만 아니라 읽은 측점들을 임시 연결 리스트(linked list)에 저장하였다. 따라서 본 연구에서 제안한 방식은 파일에 저장된 측점들을 읽는 시간과 메모리에 저장된 개별 측점을 질의하기 위한 시간을 함께 감소시키는 효과가 있다.
그러나 파일 재구성은 1 회만 수행하는 과정으로서, 옥트리의 복원과 질의를 반복한다고 가정할 경우 제안한 방식이 유리하다고 볼 수 있다. 또한 질의 시간은 전체 포인트 클라우드의 0.01%인 30, 053개의 측점을 기준으로 측정한 것으로 그의 100배인 1%의 측점을 기준으로 질의를 수행한다면 Han(2014b)과 제안한 방식이 대략 54, 700초와 25, 500초를 소요할 것으로 예상할 수 있으며 그 차이는 29, 200초로서 파일 재구성 시간을 충분히 극복할 수 있음을 알 수 있다.
메인 메모리의 사용량은 기존 방식이 4, 409MB, 제안한 방식이 1, 025MB로 77%가 감소되어 메모리 효율성도 4배 이상 증가하였음을 확인할 수 있다. 추가적인 실험은 진행하지 않았지만, 제안한 방식은 포인트 클라우드의 용량이 증가하더라도 리프 노드에 저장되는 파일 포인터가 1개로 유지되므로 목표 단계와 리프 노드의 형상 비율을 유지한다면 메인 메모리의 사용량은 유사하게 유지될 것으로 판단된다.
이는 공간적으로 인접한 측점을 근거리에 재배치함으로써 HDD 내부에서 발생하는 원거리 접근이 상당 부분 억제된 결과라고 볼 수 있다. 반면, 제안한 방식은 파일 재구성 시간이 4, 726.13초가 소요되어 옥트리 구성 시간 등 다른 과정에 비해 많은 시간이 소요되었음을 확인할 수 있다. 그러나 파일 재구성은 1 회만 수행하는 과정으로서, 옥트리의 복원과 질의를 반복한다고 가정할 경우 제안한 방식이 유리하다고 볼 수 있다.
옥 트리의 생성 시간은 기존 방식이 1, 760.16초, 제안한 방식이 1, 161.44초로 34%가 단축되었고, 옥트리 저장 시간과 복원 시간은 각각 88%와 84%가 단축되었다. 기존 방식은 모든 측점에 대한 파일 포인터를 옥트리의 리프 노드에 저장하므로 옥 트리 생성 시간이 길고 옥트리 자체의 크기가 커서 저장 및 복원 시간이 많이 소요되었으나 제안한 방식은 리프 노드 당 1 개의 파일 포인터만을 저장하므로 상기와 같은 결과가 나타났다고 볼 수 있다.
옥트리의 생성, 저장과 복원, 질의 및 메모리 사용량 등 모든 면에서 제안한 방식이 향상된 성능을 나타내었다. 옥 트리의 생성 시간은 기존 방식이 1, 760.
기존 방식은 모든 측점에 대한 파일 포인터를 옥트리의 리프 노드에 저장하므로 옥 트리 생성 시간이 길고 옥트리 자체의 크기가 커서 저장 및 복원 시간이 많이 소요되었으나 제안한 방식은 리프 노드 당 1 개의 파일 포인터만을 저장하므로 상기와 같은 결과가 나타났다고 볼 수 있다. 질의 시간은 기존 방식이 546.58초, 제안한 방식이 254.58초로 53%가 단축되어 제안한 방식의 질의속도가 2배 이상 향상되었음을 확인할 수 있다. 이는 공간적으로 인접한 측점을 근거리에 재배치함으로써 HDD 내부에서 발생하는 원거리 접근이 상당 부분 억제된 결과라고 볼 수 있다.
후속연구
아울러 메인 메모리의 크기를 크게 상회하는 초대용량 포인트 클라우드로부터 옥트리를 구성하고 측점을 질의하는 것이 가능할 것으로 판단된다. 다만, 포인트 클라우드 파일의 재구성에 상대적으로 많은 시간을 소요되어 개선할 여지가 있으며 향후 연구에서는 전반적인 성능 향상을 위해 병렬처리를 도입하고자 한다.
추가적인 실험은 진행하지 않았지만, 제안한 방식은 포인트 클라우드의 용량이 증가하더라도 리프 노드에 저장되는 파일 포인터가 1개로 유지되므로 목표 단계와 리프 노드의 형상 비율을 유지한다면 메인 메모리의 사용량은 유사하게 유지될 것으로 판단된다. 따라서 메인메모리의 크기를 크게 상회하는 초대용량 포인트 클라우드로부터 옥트리를 구성하고 측점을 질의하는 것이 가능할 것으로 판단된다.
따라서 본 연구는 선행 연구의 방식을 명백히 향상시켰다고 판단할 수 있다. 아울러 메인 메모리의 크기를 크게 상회하는 초대용량 포인트 클라우드로부터 옥트리를 구성하고 측점을 질의하는 것이 가능할 것으로 판단된다. 다만, 포인트 클라우드 파일의 재구성에 상대적으로 많은 시간을 소요되어 개선할 여지가 있으며 향후 연구에서는 전반적인 성능 향상을 위해 병렬처리를 도입하고자 한다.
확인할 수 있다. 추가적인 실험은 진행하지 않았지만, 제안한 방식은 포인트 클라우드의 용량이 증가하더라도 리프 노드에 저장되는 파일 포인터가 1개로 유지되므로 목표 단계와 리프 노드의 형상 비율을 유지한다면 메인 메모리의 사용량은 유사하게 유지될 것으로 판단된다. 따라서 메인메모리의 크기를 크게 상회하는 초대용량 포인트 클라우드로부터 옥트리를 구성하고 측점을 질의하는 것이 가능할 것으로 판단된다.
참고문헌 (13)
Cho, H., Cho, W., Park, J., and Song, N. (2008), 3D building modeling using aerial LiDAR data, Korean Journal of Remote Sensing, Vol. 24, pp. 141-152. (in Korean with English abstract)
Maréchal, L. (2009), Advances in octree-based all-hexahedral mesh generation: handling sharp features, Proceedings of 18th International Meshing Roundtable, Salt Lake City, UT, USA, pp. 65-84.
Han, S. (2013), Design of memory-efficient octree to query large 3D point cloud, Journal of the Korean Society of Surveying, Geodesy, Photogrammetry and Cartography, Vol. 31, No. 1, pp. 41-48. (in Korean with English abstract)
Han, S. (2014a), Implementation of file-referring octree for huge 3D point clouds, Journal of the Korean Society of Surveying, Geodesy, Photogrammetry and Cartography, Vol. 32, No. 2, pp. 109-115. (in Korean with English abstract)
Han, S. (2014b), Enhancing query efficiency for huge 3D point clouds based on isometric spatial partitioning and independent octree generation, Journal of the Korean Society of Surveying, Geodesy, Photogrammetry and Cartography, Vol. 32, No. 5, pp. 481-486. (in Korean with English abstract)
PCL (2015), Module octree, Point Cloud Library, http://docs.pointclouds.org/1.7.1/group__octree.html (last date accessed: 24 October 2015).
RIEGL (2015a), RIEGL VZ-2000 Datasheet, RIEGL Laser Measurement Systems GmbH, http://www.riegl.com (last date accessed: 11 August 2015).
RIEGL (2015b), RIEGL VUX-1 Series Infosheet, RIEGL Laser Measurement Systems GmbH, http://www.riegl.com (last date accessed: 11 August 2015).
Saxena, M., Finnigan, P. M., Graichen, C. M., Hathaway, A. F., and Parthasarathy, V. N. (1995), Octree-based automatic mesh generation for non-manifold domains, Engineering with Computers, Vol. 11, pp. 1-14.
Wang, M. and Tseng, Y.-H. (2004), Lidar data segmentation and classification based on octree structure, Proceedings of XXth ISPRS Congress, ISPRS, Istanbul, Turkey.
Wikipedia (2015), Brute-force search, Wikimedia Foundation, Inc., https://en.wikipedia.org/wiki/Brute-force_search (lastdate accessed: 11 August 2015).
Woo, H., Kang, E., Wang, S., and Lee, K. H. (2002), A new segmentation method for point cloud data. International Journal of Machine Tools and Manufacture, Vol. 42, pp. 167-178.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.