A Method for Registration of 3D shape

이 페이지는 A method for registration of 3D Shape 논문 리뷰를 위해 작성했습니다.

2007년즈음으로 기억한다. 선배가 Stereo Vision을 이용해서 이동속도와 회전속도를 판단하는 알고리즘을 내게 보여준 적이 있었다. 그때 제일 먼저 궁금했던건, 좀전의 이미지에서 보이는 특징점이 그 다음 이미지의 특징점과 어떻게 매칭이 되는지였다. 그때도 아마 ICP라는 용어를 그 선배가 내게 설명했을법 한데, 알고리즘의 큰 의미는 이해했지만, 그것이 어떻게 세부적으로 돌아가는지에 대해서 당시에는 내가 이해할 능력이 못되었나보다.

SLAM, 즉 로봇이 자신의 센서정보를 바탕으로 하여 현 시점의 환경정보와 Map을 생성했을때, 이를 가지고 있는 지도데이터와 비교하는 과정에서 ICP는 매우 핵심적인 역할을 한다. 현재의 지도를 천천히 이동/회전을 시켜 원래의 지도와 맞는 이동거리/회전을 구해준다. 이를 통해 원래 지도에서 나의 위치가 어디있는지 추정할 수 있는 수단을 제공한다.

문득 실제 지도를 볼때 쓰는 방법과 비슷하다는 생각을 했다. 실제 지형을 보고, 지도를 빙빙 돌려가면서 내 위치를 찾는 방법 아닐까.

이제 처음 SLAM관련 기본 논문을 읽어보는 입장에서, 이 이후에 얼마나 많은 발전이 있었을지 가늠할 수 없지만, 적어도 이 논문이 작성된 1998년도부터, 2000년대 초반까지는 매우 중요한 이정표같은 것이리라 생각이 든다.

이미지 Registration(정합)예시
출처 : https://kr.mathworks.com/discovery/image-registration.html

이제 논문을 자세히 읽어내려가보자.

논문의 목차

1. Introduction
2. 문헌 리뷰 (요새 이런걸 메타 연구라고 하나보다.)
3. Preliminaries. (수학적 선수학습내용)
   3.1. 거리 계산을 위한 기본공식들 3.1.1. 특정점과 점들간의 거리
   3.1.2. 특정점과 선들과의 거리
   3.1.3. 특정점과 삼각형들과의 거리 (Triangle을 계산하지만, 후에는 Polygon이 될듯)
   3.1.4. 특정점과 함수객체와의 거리를 최소화(최적화)하는 방법 (Newton minimaztion approch를 사용함)
   3.1.5. 특정점과 암시적(후보의)객체와의 거리 계산. 즉 위의 뉴턴 최소화방법을 사용한다. 3.2. 포인트셋의 정합

4. ICP 알고리즘
   4.1. 알고리즘의 설명
   : 1,2,3,4 를 오차 tolerance $τ$ 가 특정값 이하로 내려갈때까지 반복한다. a. Compute Closest point / 결과 : 최근접점 집합 b. Compute Registration / 결과 : 변환벡터 c. Apply Registration d. Iteration 종료조건의 계산

   4.2. 수렴정리 (Convergence Theorem)
   4.3. 다른 최소화 접근법들 a. Accelerated ICP : 보간법의 사용 (Line search 및 parabolic interpolation)
   4.4. 다른 최소화 접근법 : 몇가지 제안이 있지만, 결국 ACC ICP가 유리하더라.

5. Set of Initial Registration

   ICP알고리즘을 통해 평행이동한 결과가 Local minimum에 수렴함은 증명하였지만, 이 지점이 Global Minimum임을 보장하진 못한다. 따라서, 초기상태를 잘 설정해야 한다.

   1. ICP의 Local minima problem 증명? 예시
   2. Global minima을 찾기 위한 초기상태 선택방법
      1. 초기상태 집합을 만들어야 한다. 그리고 그 집합에 글로벌 최소값이 들어가도록 구성해야 한다. (어떻게?)
      2. 단위 Shpere 쿼ㅓ니언을 조밀하고 균일하게 샘플링하고, 평행이동 벡터를 조밀하게 샘플링하면, 그 확율을 낮출수 있다.
      3. 하지만 말만 들어봐도 계산량 (Cost)가 많아 보인다.
      4. 이에 본 논문에서는 나름의 전략을 제시한다. 이게간단하다고?
         1. 각 점 셋트의 질량중심과 공분산을 이용하여, 부등식 조건을 만족해야 함. (수식44)
         2. 그러면 이 수식을 만족하는 셋트만 골라 초기값 셋트로 사용한다는 이야기구나.
         3. 이게 2~4회정도 세이브 해준다고.
         4. 아래는 GPT 요약

         1. 초기 평행 이동 상태의 중요성 ICP는 평행 이동 초기 상태에 둔감하지만, 적절한 초기 평행 이동을 사용하면 반복 횟수를 줄이는 데 도움이 됩니다.따라서, 질량 중심을 맞추는 것이 일반적으로 유리합니다.
         2. 초기 회전 상태 선택 전략 행렬 $Σ_𝑝$ 와 $Σ_𝑥$ 의 고유값을 분석하여 초기 회전 상태를 결정할 수 있습니다. 대부분의 경우, 주축 회전(principal axis rotation)만으로도 충분합니다.
         3. 균일한 샘플링 전략 정규 다면체 회전 그룹을 사용하면 효율적으로 초기 회전 상태를 샘플링할 수 있습니다. 복잡한 경우에는 더 조밀한 샘플링이 필요할 수 있습니다.
         4. 실용적인 권장 사항
            • 간단한 객체: 기본 40개 회전 상태 사용.
            • 복잡한 객체: 312개 이상의 회전 상태 사용.
            • 고유값이 유사한 경우: 균일한 쿼터니언 샘플링 수행.
         5. 반례 이런 어프로치로도 안되는 곳이 있다.
            1. 작은 돌기가 있는 모양 (돌기의 길이차이가 올바르게 정렬되지 않는다)
            2. 성게모양, 행성모양 : 공분산 행렬 $Σ_x$ 의 고유값이 거의 동일하다는 특징
            3. 물론 초기회전상태의 개수를 늘리면 된다.

6. 실험 결과
7. 결론
8. 향후 방향