3-D Scan Registration Using Normal Distributions Transform with Supervoxel Segmentation

Abstract

모바일(mobile) 로봇이 탐사, 구조, 감시, 군사 등 다양한 응용분야에 사용되기 위해서는, 가장 기본적으로 자율 주행 능력이 필요하다. 자율 주행을 위해서 가장 중요한 문제 중 하나가 로봇 스스로 주위 환경에 대한 지도를 작성하고, 그 지도안에서 자신의 위치를 파악하는 것, 즉 simultaneous localization and mapping (SLAM)이다. SLAM의 알고리즘에서 이용하는 주위 환경에 대한 정보는 희소한(sparse) 특징 점(feature)과 조밀한(dense) 점 군(point cloud), 두 가지가 있는 데, 로봇이 자신이 가진 지도를 이용해서, 구체적인 경로 계획(path plan-ning)이나 충돌 회피(collision avoidance)를 수행하기 위해서는 조밀한 점 군을 이용한 지도가 필요하다. 그리고 다양한 형태의 로봇이 폭 넓은 임무를 수행하기 위해서는 반드시 지도가 3차원이어야 한다. 따라서 3차원 조밀한 점 군을 이용한 SLAM 알고리즘이 필요한데, 그것의 성능을 보장하기 위해서는 반드시 강력한 3차원 스캔 정합(scan reg-istration) 알고리즘이 요구된다. 본 논문에서는 3차원 normal distributions transform(NDT)의 성능을 크게 향상시킨 새로운 3차원 정합 알고리즘인 supervoxel-NDT (SV-NDT)를 제안하였다. 3차원 NDT는 모델 스캔(model scan)을 분할할 때, 3차원 정규격자를 이용한다. 하지만 3차원 정규격자는 모델 스캔의 국소적(local) 표면 구조와 관련된 정보를 전혀 이용하지 않기 때문에, 3차원 정규격자를 이용한 정규분포 생성은 큰 정보손실을 야기한다. 하나의 정규분포로 가장 잘 모델링 할 수 있는 면(스캔의 구성요소)의 형태는 평면이다. SV-NDT는 분할단계에서 슈퍼복셀(supervoxel) 생성 알고리즘을 사용함으로써 정보손실을 줄였다. 추가적으로, 데이터 스캔(data scan)의 각 점을 자신에 대응되는(corresponding) 정규분포에 연결시킬 때, 기존의 유클리드 거리(Euclidean distance)대신 유클리드 거리와 데이터 스캔의 국소적 구조를 함께 사용한 함수로 바꿈으로써 데이터 스캔의 국소적 표면의 구조 정보도 함께 이용하도록 하였다. 슈퍼복셀 생성 알고리즘을 이용하여 생성한 정규분포들의 모델링 정확도(modeling accuracy)가 향상되고, 제안한 3차원 정합 알고리즘이 기존의 3차원 NDT와 그 외 널리 사용되는 다른 알고리즘들과 비교하여 강인성(robustness)와 속도 측면에서 더 우수하였음을 합성 데이터 집합(synthetic dataset)과 실제 데이터 집합(real-world dataset)을 이용한 실험을 통해 입증하였다. 추가적으로 대응관계 형성 시 사용되는 함수를 바꾼 효과가 정합 능력에 긍정적인 효과를 끼쳤다는 것도 확인하였다.

In order to use mobile robots in various applications, such as exploration, rescue, surveillance, and military, the most fundamental required capability is an autonomous navigation. Moreover, one of the most important problem of autonomous navigation is that a robot should build a map of its surroundings and identify its location on its own map, i.e., a simultaneous localization and mapping (SLAM) problem. The information about the surroundings of a robot, which is used in SLAM algorithms, has two types, sparse features and dense point clouds. However, in order to perform a detailed path planning and colli-sion avoidance, a map with dense point clouds is necessary because dense point clouds have rich information on the surrounding obstacles. Also, the map has to be three-dimensional (3-D) so that various shapes of robots carry out wide-ranging tasks. Therefore, the SLAM algorithms using dense point clouds are required for an autonomous navigation, but in order to guarantee the performance of SLAM, a high performance 3-D scan registration algorithm is essential. This thesis presents what is termed the supervoxel normal distributions transform (SV-NDT), a novel three-dimensional registration algorithm which improves the performance of the three-dimensional normal distributions trans-form (3-D NDT) significantly. The 3-D NDT partitions a model scan using a 3-D regular grid. However, generating normal distributions using the 3-D regular grid causes considerable information loss because the 3-D regular grid does not use any information pertaining to the local surface structures of the model scan. The best type of surface (the constituent unit of each scan) for modeling with one normal distribution is known to be the plane. The SV-NDT reduces the loss of information using a supervoxel-generating algorithm at the parti-tioning stage. In addition, it uses the information of the local surface structures from the data scan by replacing the Euclidean distance with a function that uses local geometries as well as the Euclidean distance when each point in the data scan is matched to the corresponding normal distribution. Experiments demonstrate that the use of the supervoxel-generating algo-rithm increases the modeling accuracy of the normal distributions and that the proposed 3-D registration algorithm outperforms the 3-D NDT and other wide-ly used 3-D registration algorithms in terms of robustness and speed on both synthetic and real-world datasets. Additionally, the positive effect of changing the function to create correspondences on the performance of registration is also verified.