포인트 탐색과 배경제거 (60%)
본 챕터에서에서는 Octee 구조체를 이용한 배경제거에 대하여 알아 보겠습니다. 배경은 벽, 기둥, 바닥, 나무, 전봇대, 책상 등 고정된 물체라고 보면 됩니다. 1장에서 살펴본 바닥제거는 배경제거의 한 부분입니다. 바닥제거에서는 일반적으로 평면으로 가정하고 RANSAC의 모델을 이용하여 제거 하거나, Z좌표에서 최하단 부분을 관심영역 필터링으로 제거 할 수 있습니다. 하지만, 나무나 책상 등은 이러한 기법을 이용하여 제거 하기 어렵습니다.
 |
 |
|---|---|
| 바닥제거 대상 | 배경제거 대상 |
가장 이상적인 배경제거는 배경에 해당하는 물체를 모델링 하거나 인식기술을 사용하는 것입니다. 하지만 여기에서는 Octree를 학습을 목표로 하기 때문에 약간의 편법을 통해 배경을 제거해 보겠습니다.
기본적인 아이디어는 간단 합니다. 탐지 하고자 하는 물체가 없는 상태 즉, 빈방에 있는 모든것을 배경 점군으로 정의 합니다. 그리고 탐지 하려고 하는 물체가 추가 된다면 여기에서 배경 점군을 찾아내어 제거 하면 됩니다.
하지만 이때 문제가 하나 있습니다. 센서의 특성상 동일한 물체의 x,y,z좌표는 매 측정시마다 같지 않을 확률이 큽니다. {1.00, 2.00, 3.00}으로 탐지된 물체를 배경 점군으로 지정 하였지만 다음번 센서 스캔시에는 {1.01, 2.1, 2.98}으로 탐지될 가능성이 크기 때문입니다. 이때 활용할 수 있는 방법이 Octree기반 탐색 입니다.
점군 탐색을 위해서 PCL에서는 Kd-Tree기반 검색 방법도 제공 합니다.
Octree 구조체
먼저 Octree 구조체에 대하여 살펴 보겠습니다. Octree(팔진트리)는 컴퓨터 과학분야에서 많이 사용되는 이진트리(binary tree)자료 구조를 3D 환경에 적용하기 위하여 확장한 개념입니다. 2개의 자식 노드를 가진은 이진트리와 비교하여 8개의 자식 노드를 가진다는 특징을 빼고는 기본 동작원리는 같습니다.
정의 : 옥트리는 3D데이터 처리를 위한 트리형태의 데이터 구조체이다.
 |
 |
|---|---|
Octree 구조체 검색
PCL에서는 옥트리를 구조체를 생성할때 먼저 1장에서 다룬 Voxelization을 먼저 수행 합니다. 따라서 각 octree 노드는 Voxel이라고 부르기도합니다.
[트리는 여덟 개의 복셀과 다섯 개의 레벨을 가지고 있다. (각 레벨은 서로 다른 색으로 표현된다. )]
자세한 설명은 [라이푸]님의 글로 대체 하겠습니다.
위의 그림은 자료 구조가 메모리(왼쪽)와 그것의 삼차원 공간 표현(오른쪽) 사이에서 어떻게 대응되는지를 보여준다. 트리는 여덟 개의 복셀과 다섯 개의 레벨을 가지고 있다. 각 레벨은 서로 다른 색으로 표현된다. 옥트리의 마지막 레벨에 저장되는 여덟 개의 레벨은 분홍색으로 표현된다. 위의 그림의 표는 마지막 셀에 있는 다섯번 째 복셀(index 4)의 좌표를 보여준다. 그것의 좌표는 : 31, 30, 30이며, 후에 오른쪽에서 이진 형식으로 보여진다. 마지막으로 각 좌표 비트와 연관된 각 열도 옥트리의 레벨과 관련이 있다. 각 열의 비트를 합치면, 관련 레벨을 위한 셀의 각 요소에 대한 (테이블의 마지막 열에 나온) 인덱스를 획득하게 된다. 그리고 이것은 트리를 순회하고 검색된 복셀을 찾는 데 사용된다. 이것이 옥트리에서 주어진 복셀을 검색하는 원리이다.
Octree 구조체와 PCL 점군 검색
PCL에서는 Octree 구조체를 이용하여서 총 3가지의 포인트 검색 방법을 제공하고 있습니다.
octree.voxelSearch: 사용자 정의 기준점이 속해 있는 Voxel내 모든 점군을 검색 합니다.- `octree.nearestKSearch: 사용자 정의 기준점에서 가까운 N(사용자 정의)개의 점들을 검색 합니다.
octree.radiusSearch: 사용자 정의 기준 기준점에서 반경(사용자 정의)내 점들을 검색 합니다.
결과 값은 포인트의 x,y,z좌표가 아니라 인덱스 정보입니다. 그리고 nearestKSearch와 radiusSearch는 기준점까지의 거리 정보도 같이 반환 입니다.