선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 본 연구는 대용량 3차원 포인트 클라우드의 탐색을 위한 옥트리의 구현시 메모리를 효율적으로 사용하는 옥트리를 설계하는 것을 목표로 한다. 이를 위하여, 옥트리를 C++ 언어로 구현시 메모리 사용량에 영향을 미칠 수 있는 옥트리 노드 클래스의 구성 변수와 트리 생성 방식을 분석하고 개선 방안을 제시하였다.
- 본 연구는 대용량 3차원 포인트 클라우드의 탐색을 위한 메모리 효율적인 옥트리를 설계하는 것을 목표로 하였다. 이를 위하여 C++ 언어로 구현된 옥트리 노드의 구성요소 중 최소 경계 입방체 좌표 변수와 단계 저장 변수를 제거하는 대신, 부모 노드에서 자식 노드 접근 시 최소 경계 입방체 좌표를 계산하여 전달하는 방식을 채택하였다.
제안 방법
- 본 연구는 대용량 3차원 포인트 클라우드의 탐색을 위한 옥트리의 구현시 메모리를 효율적으로 사용하는 옥트리를 설계하는 것을 목표로 한다. 이를 위하여, 옥트리를 C++ 언어로 구현시 메모리 사용량에 영향을 미칠 수 있는 옥트리 노드 클래스의 구성 변수와 트리 생성 방식을 분석하고 개선 방안을 제시하였다. 실제 대용량 3차원 포인트 클라우드에 적용하여 옥트리를 구성하는데 소요되는 시간과 메모리의 크기, 인접 포인트 탐색에 소요되는 시간 등을 측정하고 분석하였다.
- 이를 위하여, 옥트리를 C++ 언어로 구현시 메모리 사용량에 영향을 미칠 수 있는 옥트리 노드 클래스의 구성 변수와 트리 생성 방식을 분석하고 개선 방안을 제시하였다. 실제 대용량 3차원 포인트 클라우드에 적용하여 옥트리를 구성하는데 소요되는 시간과 메모리의 크기, 인접 포인트 탐색에 소요되는 시간 등을 측정하고 분석하였다.
- 여기서 노드는 클래스 CNode로 정의하고 최소 경계 입방체는 클래스 외부에 구조체(struct) MBH로 정의하였다. CNode 내부에는 MBH형 변수와 노드의 단계를 저장할 정수형 변수 mbh, 자식 노드를 참조할 포인터 변수 pChild, 노드가 리프 노드일 경우를 위하여 C 언어 Standard Template Library(STL) 의 vector형 변수 ptList를 정의하였다. CNode의 내부 함수로는, 포인트를 입력 받아 재귀적으로 트리를 생성하기 위한 함수 AddPoint, 포인트의 좌표와 최소 경계 입방체의 좌표를 이용하여 자식 노드의 ID를 결정하기 위한 함수SelectChildUsing, 자식 노드들의 최소 경계 입방체의 좌표를 결정하기 위한 함수CalcMBHUsing을 정의하였다.
- CNode 내부에는 MBH형 변수와 노드의 단계를 저장할 정수형 변수 mbh, 자식 노드를 참조할 포인터 변수 pChild, 노드가 리프 노드일 경우를 위하여 C 언어 Standard Template Library(STL) 의 vector형 변수 ptList를 정의하였다. CNode의 내부 함수로는, 포인트를 입력 받아 재귀적으로 트리를 생성하기 위한 함수 AddPoint, 포인트의 좌표와 최소 경계 입방체의 좌표를 이용하여 자식 노드의 ID를 결정하기 위한 함수SelectChildUsing, 자식 노드들의 최소 경계 입방체의 좌표를 결정하기 위한 함수CalcMBHUsing을 정의하였다. 포인트 입력을 통한 트리 생성 코드는 Figure 3과 같다.
- 그러나 작은 크기의 메모리를 반복적으로 동적 할당하는 과정에서 메모리가 추가적으로 소요됨을 실험을 통해 확인할 수 있었다. 따라서 실제 트리 생성에 앞서 수도 트리(pseudo tree)를 생성하여 모든 부모 또는 자식 노드의 수와 리프 노드의 수를 산정하여 배열로 선언한 후 정식 트리를 생성하는 방법을 구현한다. 즉, Figure 6의 AddPoint_Counting 함수는 Figure 4의 AddPoint 함수와 마찬가지로 트리 구조를 생성하기는 하지만 실제로 리프 노드에 포인트를 추가하지는 않고 부모 또는 자식 노드의 수 nNode와 리프 노드의 수 nLeaf를 산정한다.
- 이를 위하여 Figure 7에서는 AddPoint_Counting 함수를 통해 수도 트리를 생성하여 노드의 수를 산정한 후 수도 트리를 메모리에서 제거한다. 다음으로 노드와 포인트 저장 구조체 전체를 각각 배열 nodeArray와 ptListArray로 선언하고 AddPoint 함수를 통해 정식 트리를 생성한다. 이러한 이중 과정을 통해 트리 생성 시간은 다소 증가될 수 있지만 메모리 효율성을 높일 수 있다.
- 2.1 단원에서 설명한 기본적인 옥트리 생성 방식 중 최소 경계 입방체 좌표 변수로 단밀도 실수형(float)을 사용한 방식(이후 M1_Float 방식)과 배밀도 실수형(double)을 사용한 방식(이 후 M2_Double 방식), 2.2 단원에서 제시한 최소 경계 입방체 변수를 노드에서 제거한 방식(이 후 M3_MBHfree 방식), 2.3 단원에서 제시한 배열을 이용한 방식(이 후 M4_Array 방식) 등 네 가지 방식을 실제 터널 내부에서 취득한 포인트 클라우드에 적용하여 성능을 평가하였다. 성능 평가는 총 다섯 목표 단계(7, 8, 9, 10, 11)에 대한 트리 생성 시간, 메모리 사용량, 탐색 시간을 측정하고 분석함으로써 수행하였다.
- 3 단원에서 제시한 배열을 이용한 방식(이 후 M4_Array 방식) 등 네 가지 방식을 실제 터널 내부에서 취득한 포인트 클라우드에 적용하여 성능을 평가하였다. 성능 평가는 총 다섯 목표 단계(7, 8, 9, 10, 11)에 대한 트리 생성 시간, 메모리 사용량, 탐색 시간을 측정하고 분석함으로써 수행하였다. 탐색은 Figure 8처럼 임의의 포인트로부터 주어진 반경 안에 존재하는 포인트의 수를 산정하는 방식을 사용하였으며(Han 등, 2012) 검색 반경은 15㎝로 설정하였다.
- 성능 평가는 총 다섯 목표 단계(7, 8, 9, 10, 11)에 대한 트리 생성 시간, 메모리 사용량, 탐색 시간을 측정하고 분석함으로써 수행하였다. 탐색은 Figure 8처럼 임의의 포인트로부터 주어진 반경 안에 존재하는 포인트의 수를 산정하는 방식을 사용하였으며(Han 등, 2012) 검색 반경은 15㎝로 설정하였다. 실험에 사용한 자료의 제원과 처리 환경은 각각 Table 1과 Table 2와 같다.
- 본 연구는 대용량 3차원 포인트 클라우드의 탐색을 위한 메모리 효율적인 옥트리를 설계하는 것을 목표로 하였다. 이를 위하여 C++ 언어로 구현된 옥트리 노드의 구성요소 중 최소 경계 입방체 좌표 변수와 단계 저장 변수를 제거하는 대신, 부모 노드에서 자식 노드 접근 시 최소 경계 입방체 좌표를 계산하여 전달하는 방식을 채택하였다. 아울러 자식 노드 생성 및 리프 노드의 포인트 저장용 벡터 구조체 생성시마다 new 연산자를 사용하는 대신, 수도 트리와 정식 트리를 생성 하는 이중적인 과정을 통해 노드 및 벡터 구조체를 배열로 미리 선언함으로서 메모리 효율성을 더욱 개선하였다.
- 이를 위하여 C++ 언어로 구현된 옥트리 노드의 구성요소 중 최소 경계 입방체 좌표 변수와 단계 저장 변수를 제거하는 대신, 부모 노드에서 자식 노드 접근 시 최소 경계 입방체 좌표를 계산하여 전달하는 방식을 채택하였다. 아울러 자식 노드 생성 및 리프 노드의 포인트 저장용 벡터 구조체 생성시마다 new 연산자를 사용하는 대신, 수도 트리와 정식 트리를 생성 하는 이중적인 과정을 통해 노드 및 벡터 구조체를 배열로 미리 선언함으로서 메모리 효율성을 더욱 개선하였다. 실제 포인트 클라우드를 대상으로 인접 포인트 탐색을 수행한 결과, 제안한 방식이 트리 생성 및 탐색 속도 면에서 비교군에 근접하거나 다소 떨어지나 메모리 효율성 면에서는 우수하여 대용량 포인트 클라우드에 적용할 수 있는 대안임을 확인할 수 있었다.
성능/효과
- Han 등(2012)은 가상격자(virtual grid)와 해시(hash)를 접목한 해시기반 가상격자(hash-based virtual grid)를 제안하여 가상격자 및 옥트리와 성능 비교를 수행하여 해시기반 가상격자가 탐색 속도 및 메모리 사용량 면에서 절충안임을 언급하였다. 즉, 탐색 속도는 가상격자, 해시기반 가상격자, 옥트리의 순서로 빠르고 메모리 사용량은 옥트리, 해시기반 가상격자의 순서로 적게 기록되었다. 상기 두 연구에 의하면 적절한 탐색 속도를 유지하면서 메모리 효율성에 보다 큰 비중을 둘 경우 옥트리가 합리적인 선택이라 판단되며, 이미 지상 및 항공 레이저 스캐닝 포인트 클라우드의 처리와 관련된 다양한 연구에서 옥트리를 사용하고 있다(Saxena 등, 1995; Woo 등, 2002; Wang 등, 2004; Schnabel 등, 2007; Cho 등, 2008; Marechal, 2009).
- 메모리 동적 할당 또는 동적 메모리 할당은 컴퓨터 프로그래밍에서 실행 시간 동안 사용할 메모리 공간을 할당하는 것으로 프로그램이 실행되기 전 컴파일 단계에서 미리 프로그램이 사용할 메모리 크기를 계산하여 변수의 배치가 이루어지는 스택 등의 정적 메모리 할당과 대조적이다(Wikipedia, 2012). 그러나 작은 크기의 메모리를 반복적으로 동적 할당하는 과정에서 메모리가 추가적으로 소요됨을 실험을 통해 확인할 수 있었다. 따라서 실제 트리 생성에 앞서 수도 트리(pseudo tree)를 생성하여 모든 부모 또는 자식 노드의 수와 리프 노드의 수를 산정하여 배열로 선언한 후 정식 트리를 생성하는 방법을 구현한다.
- Table 5는 앞에서 생성한 옥트리에서 367,535(전체 포인트 클라우드의 1/50)개의 포인트를 중심으로 반경 15㎝내에 존재하는 포인트를 탐색하는데 소요된 시간이다. 네 가지 방식 모두 목표 단계가 증가함에 따라 탐색 시간이 감소하여 목표 단계 9에서 가장 작은 탐색 시간을 기록하였다. 이 후, 목표 단계가 증가함에 따라 탐색 시간이 다시 증가하는 양상을 나타내는 데, 그 이유는 다음과 같이 설명할 수 있다.
- 각 목표 단계에서의 포인트 탐색 속도는 포인트 포인트의 수와 포인트 분포의 균질성에 영향을 받는다. 즉, 본 실험보다 많은 포인트의 포인트 클라우드에 적용하면 개별 리프 노드당 포인트 수도 증가하여 목표 단계를 높여 검색 영역을 축소시키는 것이 유리하며 반대의 경우엔 목표 단계를 낮추어 경로를 짧게 하는 것이 유리하다. 그러나 포인트가 일부 리프 노드에 집중되는 경우엔 목표 단계를 더욱 높여야 하는 상황이 발생할 수 있다.
- 한편, 각 방식별 탐색 시간을 비교하면, 목표 단계 7에서 8까지는 M1_Float, M2_Double 방식이 M3_MBHfree, M4_ Array 방식과 비교하여 유사하거나 약한 작게 측정되었으며 메모리 사용량 면에서는 반대의 경향이 나타났다. 최적 목표 단계 9에서는 M3_MBHfree 방식의 속도가 M1_Float 방식의 89%, M2_Double 방식의 84% 수준이며, M4_Array 방식의 속도는 M1_Float, M2_Double 방식의 94%, 89% 수준으로 나타났다.
- 한편, 각 방식별 탐색 시간을 비교하면, 목표 단계 7에서 8까지는 M1_Float, M2_Double 방식이 M3_MBHfree, M4_ Array 방식과 비교하여 유사하거나 약한 작게 측정되었으며 메모리 사용량 면에서는 반대의 경향이 나타났다. 최적 목표 단계 9에서는 M3_MBHfree 방식의 속도가 M1_Float 방식의 89%, M2_Double 방식의 84% 수준이며, M4_Array 방식의 속도는 M1_Float, M2_Double 방식의 94%, 89% 수준으로 나타났다. 반면 메모리 사용량은 M3_MBHfree 방식이 M1_Float, M2_Double 방식의 72%, 56% 수준, M4_Array 방식이 M1_Float, M2_Double 방식의 67%, 52% 수준인 것으로 나타났다.
- 최적 목표 단계 9에서는 M3_MBHfree 방식의 속도가 M1_Float 방식의 89%, M2_Double 방식의 84% 수준이며, M4_Array 방식의 속도는 M1_Float, M2_Double 방식의 94%, 89% 수준으로 나타났다. 반면 메모리 사용량은 M3_MBHfree 방식이 M1_Float, M2_Double 방식의 72%, 56% 수준, M4_Array 방식이 M1_Float, M2_Double 방식의 67%, 52% 수준인 것으로 나타났다. 목표 단계 10 이상에서는 그 격차가 더욱 벌어졌으나 메모리 사용량의 격차가 속도의 격차보다 크게 벌어짐을 확인할 수 있다.
- 결과적으로, 탐색 속도와 메모리 사용량 간에는 트레이드 오프(trade off)가 명백히 존재함을 확인할 수 있다. 트리를 생성하는데 소요되는 시간은 모든 목표 단계에서 M1_Float, M2_Double 방식이 M3_MBHfree, M4_Array 방식보다 적게 측정되었지만 그 차이는 수 초 이내이며 트리 생성이 실제 어플리케이션에서 빈번히 발생하는 과정이 아니라는 점을 감안하면 방식 선택 기준으로서 큰 영향은 미칠 수 없다고 판단된다.
- 결과적으로, 탐색 속도와 메모리 사용량 간에는 트레이드 오프(trade off)가 명백히 존재함을 확인할 수 있다. 트리를 생성하는데 소요되는 시간은 모든 목표 단계에서 M1_Float, M2_Double 방식이 M3_MBHfree, M4_Array 방식보다 적게 측정되었지만 그 차이는 수 초 이내이며 트리 생성이 실제 어플리케이션에서 빈번히 발생하는 과정이 아니라는 점을 감안하면 방식 선택 기준으로서 큰 영향은 미칠 수 없다고 판단된다. 인접 포인트 탐색 실험에서 본 연구에서 사용한 포인트 클라우드에 대한 최적 목표 단계인 9단계까지는 네 가지 방식이 수 초 이내의 차이를 기록한 가운데 M1_Float, M2_Double 방식이 약간의 우세를 보였다.
- 트리를 생성하는데 소요되는 시간은 모든 목표 단계에서 M1_Float, M2_Double 방식이 M3_MBHfree, M4_Array 방식보다 적게 측정되었지만 그 차이는 수 초 이내이며 트리 생성이 실제 어플리케이션에서 빈번히 발생하는 과정이 아니라는 점을 감안하면 방식 선택 기준으로서 큰 영향은 미칠 수 없다고 판단된다. 인접 포인트 탐색 실험에서 본 연구에서 사용한 포인트 클라우드에 대한 최적 목표 단계인 9단계까지는 네 가지 방식이 수 초 이내의 차이를 기록한 가운데 M1_Float, M2_Double 방식이 약간의 우세를 보였다. 10단계 이상에서는 그 격차가 심화되어 충분한 메모리가 확보된다면 M1_ Float, M2_Double 방식이 유리할 것으로 판단된다.
- 아울러 자식 노드 생성 및 리프 노드의 포인트 저장용 벡터 구조체 생성시마다 new 연산자를 사용하는 대신, 수도 트리와 정식 트리를 생성 하는 이중적인 과정을 통해 노드 및 벡터 구조체를 배열로 미리 선언함으로서 메모리 효율성을 더욱 개선하였다. 실제 포인트 클라우드를 대상으로 인접 포인트 탐색을 수행한 결과, 제안한 방식이 트리 생성 및 탐색 속도 면에서 비교군에 근접하거나 다소 떨어지나 메모리 효율성 면에서는 우수하여 대용량 포인트 클라우드에 적용할 수 있는 대안임을 확인할 수 있었다. 향후, 본 연구에서 제안한 옥트리 방식과 병렬처리를 접목한 초대용량 3차원 포인트 클라우드의 처리에 관한 연구를 수행하고자 한다.
후속연구
- 아울러, M1_Float의 경우 목표 단계에 따라 탐색된 포인트의 수가 달라지는 결과가 도출되었으므로 고도의 정확도를 요구하는 어플리케이션에는 적합하지 않을 것으로 판단된다. 따라서 본 연구에서 제안한 M3_MBHfree 방식 또는 M4_Array 방식은 메모리가 제약된 전산 환경에서 대용량 3차원 포인트 클라우드에 적용할 수 있는 현실적인 대안으로 사료된다.
- 실제 포인트 클라우드를 대상으로 인접 포인트 탐색을 수행한 결과, 제안한 방식이 트리 생성 및 탐색 속도 면에서 비교군에 근접하거나 다소 떨어지나 메모리 효율성 면에서는 우수하여 대용량 포인트 클라우드에 적용할 수 있는 대안임을 확인할 수 있었다. 향후, 본 연구에서 제안한 옥트리 방식과 병렬처리를 접목한 초대용량 3차원 포인트 클라우드의 처리에 관한 연구를 수행하고자 한다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.