[논문 리뷰] A Method for Registration of 3-D Shapes (ICP)

  • 논문: A Method for Registration of 3-D Shapes
  • 저자: Paul J. Besl, Neil D. McKay (General Motors Research Laboratories)
  • 학회: IEEE TPAMI, Vol. 14, No. 2, 1992

한 줄 요약

측정한 점마다 모델 위에서 가장 가까운 점을 찾고, 그 짝으로 최소제곱 회전·이동을 한 번에 푸는 과정을 반복해 두 3D 형상을 맞추는 ICP(Iterative Closest Point) 논문. 반복할 때마다 평균제곱오차가 줄어서 가까운 지역 최솟값으로 반드시 수렴한다는 것을 증명했다. 전역 최솟값을 찾으려고 초기 회전 후보를 여러 개 두고 돌리는 방법까지 다룬다.

배경

3D 센서로 잰 점들은 센서 좌표계에 있고, CAD 같은 모델은 자기 좌표계에 있다. 둘을 비교하려면 먼저 데이터를 모델 위에 겹쳐 놓는 회전과 이동을 구해야 한다. 이 문제를 정합(registration)이라고 부르고, 이 논문은 6자유도 전체를 다루는 일반적인 방법을 찾는다.

짝(대응점)을 이미 알면 문제는 쉽다. 짝지은 점 사이 거리 제곱합을 최소로 만드는 회전·이동은 닫힌 형태로 바로 나온다. 어려운 건 짝을 모를 때다. 기존 방법들은 곡률 같은 특징을 먼저 뽑아 짝을 만들었는데, 매끈한 자유곡면에는 쓸 만한 특징이 별로 없다.

논문이 노린 응용은 검사(inspection)다. 지그로 고정하지 않은 부품을 측정하고, 측정 점들을 모델에 맞춘 뒤 얼마나 벗어났는지 본다. 그래서 특징 추출도, 곡면 미분도, 스무딩 같은 전처리도 필요 없는 방법을 목표로 했다.

제안 방법

무엇을 최소화하나

데이터 점 집합 $P = \lbrace \vec p_i \rbrace$를 모델 $X$에 맞춘다. 모델은 점 집합, 선분, 삼각형 메시, 음함수·매개변수 곡선과 곡면 중 무엇이든 된다. 조건은 하나뿐이다. 어떤 점이 주어지면 모델 위에서 가장 가까운 점을 구할 수 있어야 한다.

점 $\vec p$와 모델 사이 거리는 모델 위 가장 가까운 점까지의 거리로 정의한다.

\[d(\vec p, X) = \min_{\vec x \in X} \lVert \vec x - \vec p \rVert\]

짝을 알 때는 쿼터니언으로 한 번에

짝 $(\vec p_i, \vec y_i)$가 정해졌다면, 회전 $R$과 이동 $\vec q_T$는 아래 평균제곱오차를 최소로 만들어야 한다.

\[f(\vec q) = \frac{1}{N_p} \sum_{i=1}^{N_p} \lVert \vec y_i - R(\vec q_R)\,\vec p_i - \vec q_T \rVert^2\]

여기에는 Horn의 단위 쿼터니언 방법을 쓴다. 두 점 집합의 무게중심을 빼고 교차공분산 행렬 $\Sigma_{py}$를 만든다. 이걸로 4×4 대칭 행렬을 만들면, 가장 큰 고윳값의 고유벡터가 최적 회전 쿼터니언이다. 이동은 $\vec q_T = \vec\mu_y - R\,\vec\mu_p$로 바로 나온다.

계산량은 $O(N_p)$로 가볍다. 결론에서는 이 단계를 SVD 방법으로 바꾸면 n차원으로도 일반화된다고 적었다.

ICP 반복

짝을 모를 때는 “지금 위치에서 가장 가까운 점”을 짝으로 삼는다. 처음 짝은 틀리지만, 맞춘 뒤 다시 가까운 점을 찾으면 조금 더 나은 짝이 된다. 알고리즘은 네 단계를 반복한다.

  1. 가장 가까운 점 찾기: $Y_k = \mathcal{C}(P_k, X)$. 최악 $O(N_p N_x)$, 평균 $O(N_p \log N_x)$.
  2. 정합 계산: $(\vec q_k, d_k) = \mathcal{Q}(P_0, Y_k)$. 위의 쿼터니언 방법이다.
  3. 적용: $P_{k+1} = \vec q_k(P_0)$.
  4. 종료: 평균제곱오차 변화 $d_k - d_{k+1}$이 정해 둔 값 $\tau$보다 작으면 멈춘다.

정합은 매번 처음 데이터 $P_0$를 기준으로 계산하므로, 마지막 $\vec q_k$가 그대로 전체 변환이 된다. 시간이 가장 많이 드는 건 1단계다.

수렴 정리

핵심 정리는 ICP가 평균제곱오차 기준으로 지역 최솟값에 단조 수렴한다는 것이다. 증명은 두 부등식으로 끝난다.

  • 2단계의 최소제곱 정합은 현재 짝에 대한 오차 $e_k$를 늘리지 않는다($d_k \le e_k$). 아무것도 안 하는 항등 변환도 후보 중 하나이기 때문이다.
  • 1단계는 점마다 거리를 늘리지 않는다. 새로 찾은 점이 이전 짝보다 멀다면 “가장 가까운 점”이라는 정의에 어긋난다. 그래서 $e_{k+1} \le d_k$다.

두 부등식을 이으면 $0 \le d_{k+1} \le e_{k+1} \le d_k \le e_k$다. 오차는 음수가 될 수 없고 줄기만 하니 어떤 값으로 수렴한다.

실험에서는 처음 몇 번은 빠르게 줄고 최솟값 근처에서 느려졌다. 30~50번 반복하면 오차가 모델 크기의 약 0.1%까지 내려갔다고 한다.

가속 ICP

느려지는 구간에서는 정합 벡터(쿼터니언 4개와 이동 3개, 7차원)가 거의 같은 방향으로 조금씩 움직인다. 논문은 최근 세 번의 이동 방향이 서로 10° 안쪽이면 방향이 일정하다고 본다. 그때 오차를 직선과 포물선으로 근사하고, 그 최솟점까지 한 번에 건너뛴다.

너무 멀리 뛰지 않도록 최대 이동 거리도 정해 둔다. 이렇게 하면 기본 ICP로 50번 넘게 걸리던 것이 보통 15~20번으로 줄었다.

경사하강 같은 일반 최적화와도 비교한다. 수치 기울기 하나를 구하려면 가장 가까운 점 계산을 최소 7번 해야 한다. ICP는 반복 한 번에 한 번이면 되고, 오차가 더 큰 쪽을 탐색하느라 계산을 쓰지도 않는다.

초기 자세 문제

수렴 정리가 보장하는 건 가까운 지역 최솟값까지다. 출발점이 나쁘면 엉뚱한 자세에 갇힌다. 논문은 이 문제에 한 절을 따로 쓴다. 방법은 단순하다. 서로 다른 초기 회전 여러 개에서 ICP를 돌리고 오차가 가장 작은 결과를 고른다.

  • 이동은 크게 신경 쓰지 않아도 된다. 데이터가 모델의 상당 부분을 덮으면 이동 후보를 여러 개 둘 필요가 없다. 무게중심만 미리 맞춰 두면 보통 20번쯤 하던 반복이 2~4번 준다.
  • 주축이 뚜렷한 형상은 회전 4개면 된다. 공분산 고윳값 세 개가 충분히 다르면 항등 회전과 세 주축에 대한 180° 회전으로 대부분 맞는다.
  • 그렇지 않으면 정다면체 회전군을 쓴다. 정사면체군 12개, 정육면체·정팔면체군 24개, 정이십면체군 60개 회전을 초기값으로 쓴다. 쿼터니언 성분을 조합해 40개나 312개 회전을 만드는 방법도 소개한다.

저자들은 반례도 직접 만들어 보인다. 구 표면에 초기 회전 축마다 가는 가시를 붙이고, 다른 자리에 조금 더 긴 가시를 붙인다. 그러면 어떤 초기 회전 집합을 정해 두어도 그 집합으로는 못 맞추는 “성게” 모양이 나온다. 공분산 고윳값이 거의 같고 작은 특징만 있는 물체가 ICP에 가장 어렵다는 뜻이다.

실험 결과

아래는 모두 논문에 실린 실험이다. 저자들은 실험 프로그램을 C로 짰고, 1992년 당시 1.6 Mflops급 단일 프로세서 컴퓨터에서 시간을 쟀다.

  • 점 8개를 점 11개 집합에 짝 정보 없이 맞췄다. 6번 반복, 1초 안쪽에 끝났고 RMS 오차는 0.44 mm였다.
  • 잡음이 큰 점 138개를 삼각형 450개짜리 곡면에 맞췄다. 정밀도는 떨어졌지만 항등 변환에 가까운 답이 나왔다. 데이터가 이 정도로 잡음이 많고 특징이 없는데도 맞아서 놀랐다고 적었다.
  • 가면을 레이저로 찍은 거리 영상(삼각형 8,442개)에 점 2,546개를 맞췄다. 초기 회전 24개에서 6번씩 돌리고, 가장 좋은 것으로 끝까지 돌렸다. 90 mm 크기 물체를 어떻게 놓아도 약 10분 안에 정답으로 갔고 RMS 오차는 0.59 mm였다.
  • 같은 가면을 Bezier 곡면 97개로 만든 모델에 맞추자 RMS가 기대한 약 1.2 mm보다 큰 3.4 mm였다. 측정 점은 있는데 곡면이 없는 부분이 있었기 때문이다.
  • 점과 곡면 사이 벡터가 법선과 몇 도 이상 어긋나는 점을 빼자 기대한 오차로 돌아왔다. 측정 점 30%를 지운 데이터도 제대로 맞았다.
  • 지형 데이터 점 13,655개를 초기 회전 24개로 맞추는 데 약 1시간이 걸렸다.

한계

논문이 직접 꼽은 약점들이다.

  • 큰 이상치에 약하다. 최소제곱이라 튀는 점 몇 개가 결과를 끌고 간다. 이상치 제거는 전처리로 따로 해야 한다.
  • 분할을 해 주지 않는다. 두 물체의 점이 섞여 있으면 정합이 틀리고 오차도 커진다.
  • 부분 정합은 비싸다. 데이터가 모델의 작은 부분만 덮으면 이동 후보까지 늘려야 한다. 비용이 $O(N_t N_q N_p N_x)$로 커진다.
  • 가장 가까운 점 탐색에 k-d 트리를 쓰는 방법은 다루지 않고 앞으로 할 일로 남겼다.

느낀 점

  • 증명이 생각보다 짧았다. “최소제곱 정합은 오차를 늘리지 않는다”와 “가장 가까운 점은 더 멀어질 수 없다”를 이으면 끝난다. 다만 보장하는 범위가 가까운 최솟값까지라서, 논문의 상당 부분이 초기 자세에 들어간 이유를 알 것 같았다.
  • 30년도 더 된 논문인데 지금 쓰는 구조가 거의 다 들어 있다. 무게중심 맞추기, 회전 후보 여러 개, 법선과 어긋나는 짝 버리기가 이미 실험 안에 있다.
  • 같은 시기 Chen과 Medioni는 가장 가까운 점이 아니라 그 점의 접평면까지 거리를 줄이는 point-to-plane 방식을 냈다. 보통 점-점 방식보다 적은 반복으로 수렴해서 지금도 많이 쓴다. 뼈대는 그대로 두고 부품 하나를 바꾼 셈이다.
  • 한계로 꼽은 “분할을 해 주지 않는다”는 지금 봐도 핵심이다. 상자에 같은 부품이 쌓인 장면이라면 ICP만으로는 안 된다. 물체를 하나씩 떼어 내고, 대략적인 자세를 먼저 잡아 주는 단계가 앞에 있어야 한다.