Point cloud :: KdTree와 KNN

K-dimensional Tree는 K 차원으로 공간상의 점들을 정리하는 자료구조 중 하나이다.

이진트리(binary tree)의 종류인데, 제약조건이 추가 됐을 뿐이다. K-d Tree는 range나 nearset neighbor 탐색에 매우 유용하다. Kd tree는 그 공간의 차원에 제한 되는데, 포인트 클라우드는 일반적으로 3차원이므로 여기서 사용하는 kdTree의 차원은 3차원이다.

​

kd tree는 기본적으로 x축을 기준으로 yz 평면에 평행하게 한번, y축 기준으로 한번, z축 기준으로 한번 나누어 이를 Tree 형식으로 만드는 원리이다. 이렇게 계속 나눠서 이진 트리 형태의 구조가 된다.

​

출처 : PCL tutorial page

사진에서는 KdTree를 이용해서 Nearest-Neighbor 방법이 적용되는 모습을 볼 수 있다.

Point cloud tutorial에서는 2가지 방법을 보여준다.

​

1. K nearest neighbor search

2. Neighbors within radius search

​

1번 KNN은 초기에 설정한 점의 갯수를 기준으로 주변 점을 탐색하여 갯수를 만족할 때까지 영역을 탐색하고

2번은 처음 탐색 시작점을 기준으로 반경에 있는 모든 포인트를 탐색하게 된다. 탐색한 영역만큼과 나머지 영역으로 나눠져서 분류되게 된다. 이러면 내가 원하는 영역만 segemetation 같이 할 수 있다.

​

좌 : 일반 Point cloud , 우 : KNN으로 나눠진 Point cloud (pcl_viewer)

 

시작 포인트를 설정하는 방법은 2가지가 있다.

​

1. 시작 포인트 좌표의 값으로 설정해주는 방법.

pcl::PointXYZRGB searchPoint; 
searchPoint.x = -0.006; 
searchPoint.y = 0.098; 
searchPoint.z = 0.503;

2. 포인트클라우드에서 몇번째 포인트인지 설정해주는 방법

pcl::PointXYZRGB searchPoint = cloud->points[3000];

pptk viewer

​

2번이야 그냥 할 수 있다지만, 1번의 경우 쉽지 않을 수 있다. 이럴 경우 포인트 클라우드를 PCD 파일로 만들어서

pptk를 이용해서 시각화하게 되면, 마우스 클릭으로 내가 누르는 부분의 포인트 클라우드 위치를 확인 할 수 있다.