ICP 알고리즘 이용 3D 거리 영상 정합 Reading & Summary

  SLAM(stimultaneous localization and mapping) 과 관련하여 큰 관련을 갖는 지도 정합을 통한 3D지도 작성 기술과 관련한 논문 한편을 요약하면서 알아야 할 개념들을 소개하고 정리하겠습니다. :) 

ICP 알고리즘 이용 3D 거리 영상 정합[1]

 

  로봇이 주어진 작업을 진행하기 위해 작업의 위치까지 이동할 수 있는 능력이 필요하다. 따라서 로봇의 자신 위치를 알기 위한 방법이 필요하며 지도를 작성함과 동시에 위치 추정 기술은 로봇의 중요한 연구 주제가 되었다. 

 

  기존의 연구에서는 2D 스캐너 데이터를 통한 EKF, 파티클 필터를 적용하여 환경에 대한 특징을 찾아 알고리즘을 수행한다. 하지만 3차원 환경에서는 특징점을 찾는데 문제가 많아서 알고리즘을 그대로 적용할 수 없게 되었고, 3 자유도에서 6자유도로 확장되면서 알고리즘의 수평적인 적용은 좋은 결과를 가져오기 어렵다. 자율주행 자동차가 주행하는 실외 환경에서는 구조적인 환경이 상대적으로 적어 신뢰할 수 있는 특징점을 찾기가 더욱 어렵다. 

 

  하지만 ICP 알고리즘을 적용하면서 지도 작성에서의 Matching 능력이 향상되었다. 2009년 당시 프라운 호퍼 연구서에서는 ICP알고리즘을 용한한 스캔 매칭을 바탕으로 3차원 지도를 생성하였고 Thrun은 주로 확률 모형을 이용하여 지도를 자겅하였고 성공적인 결과를 얻어냈다. 

 

※ 정합의 개념

  3차원 지도를 작성하기 위해서는 기준좌표계를 설정하는것부터 이루어 져야 한다. 처음으로 획득한 3차원 거리 영상의 좌표계가 기준 좌표계가 되며 이후의 거리 영상은 모두 기준 좌표계로 표현된다. 이 과정을 우리는 '정합 ' (registration)이라고 한다. 

 

1. ICP(Iterative Closest Point) 알고리즘이란?

  기존의 데이터셋에 현재 데이터를 '정합 '시키는 방법중의 하나로, 각 데이터들의 가장 가까운점을 이용하여 연관성을 찾고 그에 맞게 현재데이터를 이동 및 회전을 시켜 기존데이터셋에 추가하는 방법이다[2]. 두 데이터 간의 대응관계를 알지 못할 때,

(예를 들어 자율주행자동차에서 D-GPS를 이용하여 현재의 정확한 위치를 수신할 수 있지만, 그러한 정보 데이터가 없을때, ICP와 같이 두개의 독립적인 데이터들의 상관관계를 이용하여 전 위치로부터 현 위치까지의 차이에서 오는 거리값 혹은 Heading값 등의 정보를 추출할 수 있다.)

모델 데이터와 입력 데이터 사이에서 E(R,T)를 최소를 만드는 회전변환R과 병진이동행렬T를 구하는것이다. 

식(1) E(R,T)

Nm : 모델 데이터의 개수, Ni : 입력 데이터의 개수, mi :모델데이터, dj : 입력데이터

입력데이터의 j번째 데이터는 모델데이터에서 i번째 데이터와의 유클리드 거리가 가장 작으며 따라서 대응관계가 성립한다.

 

1.1 ICP알고리즘의 적용 순서

① 두 데이터간 유클리드 거리를 구해 최소 거리에 있는 관계를 두 데이터간 대응관계라 한다.

② 대응관계가 결정된 두 데이터 집합에서 식(1)을 만족하는 R과 T를 계산할 수 있다. (여기서 R과 T는 horn의 방법을 사용하여 구할 수 있다.)

③ R 과 T를 이용하여 입력데이터 d를 변경한다.

④ 수렴할 때까지 순서 ①에서 ③까지 반복한다.

 

2. ICP알고리즘의 시간적 한계

ICP의 수행시간은 O(N^2)으로 데이터가 많을 수록 수행시간은 기하급수적으로 증가하게 된다. 데이터를 줄이는 방법으로 알고리즘의 수행시간을 줄일 수 있다.

 

2.1 시간적 한계를 극복하기 위한 데이터 서브샘플링

  <ICP방법을 이용한 3D 거리 영상의 정합>에서는 수직 수평방향으로 매 3번째의 데이터만 사용하는 서브샘플링을 이용하였다.  원본 데이터와 서브샘플링 데이터는 정확성에 있어서는 크게 차이가 나지 않으나 수행시간에서는 크게 줄어들었다. (실제 수행하는데 쓰인 데이터의 개수는 120,600 개였고 sub sampling을 통하여 13,400개의 데이터로 데이터를 줄였다.)

 

2.2 KD-Tree

  ICP 알고리즘은 결론적으로 R과 T의 값을 이용하여 d값을 구하는 알고리즘이다. 하지만 모든 데이터에 대하여 비교를 하면서 R과 T를 구할 수 없기 때문에 KD-Tree 검색 방법을 이용한다. KD-Tree는 버켓(Bucket)이라는 변수(parameter)를 가지는데, 두 데이터를 정합하는 과정에서 어떤 데이터가 모델에서 어떤 데이터와 일치하는지의 오차율을 정하는 변수이다. 이 버켓값을 너무 크게 할 시 잘못된 데이터들의 대응관계를 고려할 확률이커지고 반대로 너무 작게 설정할 시 옳게 대응되는 데이터들의 수가 줄어들어 ICP의 결과에 나쁜 영향을 가져올 수 있다. 

 

식(2) Bucket을 고려한 ICP 

wj : 버켓에 의한 가중치

  여기서 가중치는 두 데이터 사이의 유클리드 거리가 문턱값보다 작을 경우 1이며, 그 반대는 0의 값을 가진다. 

 

이와 같은 연속적인 데이터의 정합을 multiple scan registration이라고 불리며 pairwise 방법에 의한 차원 지도 작성이라고 불린다.

 

※ 실험 순서

0. 3차원 모델 데이터 생성 (비교할 대상이 필요하기 때문에 정지한 상태로 얻은 모델)

1. 연속적인 3차원 거리 영상 획득 (Raw Data parsing) 

2. 3차원 거리영상의 정합 (Data manufacturing)

3. 3차원 지도의 작성 (Creation of map)

4. 모델 데이터와 정합 데이터의 비교를 통한 결과 확인

 

 

3. 결론

ICP의 수행시간을 줄이기 위해서는 검색시간을 줄여야 하기 때문에 데이터의 서브샘플링기법과 KD-Tree 검색방법의 사용으로 검색시간을 줄였다. 넓은 환경에서의 3D 지도작성에 있어서 ICP 알고리즘은 누적되는 오차에 따른 평지에서의 내리막길과 같은 큰 오차는 수정하고 개발되어야 할 부분이다. 

 

 

현재 이용되고 있는 오차 수정의 방법으로는 INS, IMU(현재위치추정장치)를 이용한 오차 수정과 같은 방법들이 있습니다. 그러한 방법들은 추후 다른 논문을 통해 다뤄보도록 하겠습니다. 

 

 

 

 

<참고문헌>

[1] 신용득 등 5명, ICP방법을 이용한 3D 거리 영상의 정합, 제어로봇시스템학회 국내학술대회 논문집 , 2009.

(www.dbpia.co.kr/journal/articleDetail?nodeId=NODE02036705)

[2] 하루하루, 네이버 블로그, 2016. (https://m.blog.naver.com/PostView.nhn?blogId=tlaja&logNo=220666876033&proxyReferer=https:%2F%2Fwww.google.com%2F) (2020.07.15.)