점군 정합

수치해석 컴퓨터 그래픽스 시뮬레이션 마지막 수정: 2026-08-27 04:26:07

1. 개요[편집]

대응만 알면 1초 만에 풀리고, 대응을 모르면 평생 못 푼다.

점군 정합(point cloud registration)은 서로 다른 좌표계에서 측정된 두 점 집합 $\mathcal P = \{p_i\}$ , $\mathcal Q = \{q_j\}$ 를 같은 물체의 서로 다른 관측으로 보고, 둘을 겹치게 만드는 강체변환 $(R, t) \in SE(3)$ 을 찾는 문제다. 3D 스캐너로 여러 방향에서 찍은 조각을 하나의 모델로 합칠 때, 로봇이 라이다 프레임을 이어 붙여 지도를 만들 때, 측정한 형상을 CAD 원본과 비교해 오차를 볼 때 — 전부 같은 문제다.

이 문제의 난이도는 전부 한 곳에서 나온다. 어느 점이 어느 점의 짝인지 모른다. 대응(correspondence)이 주어져 있으면 최적 $(R,t)$ 는 특이값 분해 한 번으로 닫힌 형태로 나오는, 직교 프로크루스테스 문제의 응용 문제일 뿐이다. 그런데 대응이 미지수면 문제는 연속변수(변환)와 이산변수(짝짓기)가 얽힌 혼합 최적화가 되고, 목적함수는 국소 최소로 가득한 비볼록 지형이 된다. 이 문서는 그 지형을 어떻게 헤쳐 나가는지에 대한 이야기다.

2. 문제 정식화[편집]

가장 흔한 목적함수는 대응이 알려졌다고 가정한 제곱합이다.

E(R, t) \;=\; \sum_{i=1}^{N} w_i \,\bigl\| R\,p_i + t - q_{c(i)} \bigr\|^2, \qquad R^{\mathsf T}R = I,\ \det R = +1

여기서 $c(\cdot)$ 이 대응 함수다. 최적화는 $(R,t)$ 와 $c$ 를 동시에 찾아야 하는데, 둘 중 하나를 고정하면 나머지는 쉽다.

$c$ 를 고정하면 → 절대정위(absolute orientation) 문제. 닫힌 해가 있다.
$(R,t)$ 를 고정하면 → 각 점에 대해 가장 가까운 점을 찾는 문제. 최근접 이웃 탐색으로 끝난다.

이 관찰을 그대로 알고리즘으로 만든 것이 ICP다. 교대 최적화(alternating minimization)의 교과서적 사례이고, 그래서 EM 알고리즘이나 k-평균과 구조가 똑같다 — 장점도 단점도 똑같이 물려받는다.

3. 절대정위의 닫힌 해[편집]

대응이 주어진 경우를 먼저 정리하자. 두 점군의 무게중심 $\bar p, \bar q$ 를 빼서 중심화하면 평행이동이 분리되어 $t = \bar q - R\bar p$ 로 나중에 복원되고, 남는 것은 회전뿐이다. 중심화된 좌표로 교차공분산

H \;=\; \sum_i w_i\, \tilde p_i\, \tilde q_i^{\mathsf T} \;=\; U\Sigma V^{\mathsf T}

를 만들어 특이값 분해하면

R^\star \;=\; V\,\mathrm{diag}\bigl(1,\,1,\,\det(VU^{\mathsf T})\bigr)\,U^{\mathsf T}

가 최적해다. 마지막 $\det$ 보정이 반사(거울상)를 제거하는 한 줄이고, 이걸 빼먹으면 데이터가 거의 평면일 때 스캔이 뒤집혀 붙는 유명한 사고가 난다. 다만 이 보정이 실제로 «발동»하는 곳은 대응이 외부에서 주어지는 절대정위 쪽이다. 대응을 최근접점으로 매번 다시 긋는 ICP 안에서는 짝이 국소적이라 $\det H$ 가 좀처럼 음수가 되지 않는다 — 아래 시뮬의 커널로 초기 회전 0~180°를 1° 간격으로 잡음·절단률을 바꿔가며 전수 조사했을 때 정상 구간에서는 발동이 한 번도 없었고, 절단률을 70 % 이상으로 올려 살아남은 대응을 짧은 호에 몰아넣어야 비로소 음수가 나왔다.¹ 유도와 함정은 직교 프로크루스테스 문제 문서가 자세히 다루므로 여기서는 결과만 쓴다. 호른(1987)의 사원수 기반 닫힌 해도 같은 답을 주며, 4×4 대칭행렬의 최대 고유벡터를 구하는 형태라 회전행렬의 직교성을 자동으로 만족한다는 이점이 있다.

핵심은 이것이다. 정합의 절반은 이미 40년 전에 완전히 풀렸다. 남은 절반이 대응이다.

4. ICP — 최근접점 반복[편집]

베슬과 맥케이(1992)가 정식화한 ICP(Iterative Closest Point)는 놀랄 만큼 단순하다.²

현재 변환으로 $\mathcal P$ 를 옮긴다.
옮긴 각 점에 대해 $\mathcal Q$ 에서 가장 가까운 점을 찾아 대응으로 삼는다.
그 대응으로 절대정위를 풀어 변환을 갱신한다.
수렴할 때까지 반복.

수렴성은 보장된다 — 2단계는 대응을 바꿔 목적함수를 줄이거나 유지하고, 3단계는 변환을 바꿔 역시 줄이거나 유지한다. 단조 비증가 수열이 아래로 유계이므로 반드시 수렴한다. 다만 수렴하는 곳이 전역 최소라는 보장은 전혀 없다. 이 문장이 ICP의 모든 것이다.

두 점군을 2D ICP 로 맞춘다 — 매 반복 최근접 대응을 다시 긋고, H=Σ(p−μ_p)(q−μ_q)ᵀ 의 2×2 SVD 로 R=V·diag(1,det VUᵀ)·Uᵀ 와 t=μ_q−Rμ_p 를 닫힌 해로 구한다. 소스의 22.8%(52점)는 겹침 밖이라 짝이 없고, 절단 30% 가 그중 51개를 걸러 초기 회전 35° 에서 13 반복만에 RMS 0.0113 까지 내린다. θ₀ 가 61° 를 넘으면 지역최소에 걸려 θ₀=120° 에서 RMS 0.046·각오차 124° 로 정체한다.

수렴 속도의 관점에서 ICP는 나쁘다. 정답 근처에서도 선형 수렴이고, 특히 평면이나 원통처럼 접선 방향으로 미끄러져도 잔차가 별로 안 줄어드는 형상에서는 오차가 한 자릿수 줄어드는 데 수십 번 반복이 필요하다. 관측 잡음이 있으면 대응이 매 반복 요동쳐 마지막에 미세하게 진동하기도 한다.

5. point-to-plane — 판을 바꾼 한 줄[편집]

첸과 메디오니(1991)는 잔차를 점 사이 거리가 아니라 목표 점군의 국소 접평면까지의 거리로 바꿨다.³

E \;=\; \sum_i \Bigl(\bigl(R p_i + t - q_{c(i)}\bigr)\cdot n_{c(i)}\Bigr)^2

$n_{c(i)}$ 는 대응점에서의 법선이다. 이 한 줄이 수렴 속도를 극적으로 바꾼다. 이유는 기하학적이다. 접평면 방향의 미끄러짐에 벌점이 없다. 두 스캔이 같은 평평한 벽을 보고 있으면 벽을 따라 옆으로 미끄러지는 것은 물리적으로 정보가 없는 자유도인데, point-to-point 목적함수는 “가장 가까운 점”이라는 인위적 짝짓기 때문에 이 자유도에 가짜 복원력을 걸어 지그재그를 만든다. point-to-plane은 그 힘을 0으로 만들어, 실제로 구속된 방향만 정렬한다.

푸는 방법도 다르다. 목적함수가 회전에 대해 비선형이므로 소각 근사 $R \approx I + [\boldsymbol\omega]_\times$ 로 선형화하면 미지수 6개짜리 정규방정식

A^{\mathsf T}A\,\begin{pmatrix}\boldsymbol\omega \\ t\end{pmatrix} = A^{\mathsf T}b, \qquad A_i = \bigl(p_i \times n_i,\ \ n_i\bigr)

가 되고, 6×6 대칭 행렬 하나 푸는 것으로 한 반복이 끝난다. 사실상 가우스-뉴턴법 한 스텝이고, 그래서 정답 근처에서 이차 수렴에 가까운 거동을 보인다. 실무에서 point-to-plane ICP가 point-to-point보다 수 배에서 한 자릿수 빠르게 수렴하는 것은 이 때문이다.

$A^{\mathsf T}A$ 의 조건수를 보는 것은 형상이 정합을 구속하는지 진단하는 공짜 도구다. 평면 하나만 보면 3개 자유도가 풀리지 않아 이 행렬이 특이해지고, 원통은 축 방향 병진과 축 회전이 풀린다. 고윳값이 작은 방향이 곧 “이 스캔으로는 결정할 수 없는 운동”이며, 라이다 오도메트리에서 터널이나 긴 복도가 악명 높은 이유가 정확히 이것이다. 이 진단을 무시하고 나온 변환을 그대로 믿으면, 벽을 따라 지도가 스르륵 미끄러진다.⁴

세갈 등의 Generalized-ICP(2009)는 양쪽 점군 모두에 국소 공분산을 붙여 point-to-point와 point-to-plane을 하나의 확률적 정식화로 통합했고(plane-to-plane), 파라미터 튜닝에 덜 민감하다는 평가를 받는다.

6. 실패 모드와 처방[편집]

ICP가 실패하는 방식은 몇 가지로 정형화돼 있다.

국소 최소. 초기 자세가 나쁘면 엉뚱한 곳에 안착한다. 대칭성이 있는 물체(원통, 구, 반복 무늬 벽)에서는 전역 최소조차 여러 개다. 경험칙으로 초기 회전 오차가 대략 30° 를 넘으면 point-to-plane ICP도 자주 실패한다.
부분 겹침. 실측 스캔은 겹치는 영역이 일부뿐인데, 겹치지 않는 점들도 억지로 최근접점을 찾아 대응을 만들어낸다. 이 가짜 대응이 변환을 끌어당긴다.
이상치와 잡음. 제곱합은 이상치에 대해 붕괴한다 — 잘못된 대응 하나가 잔차 제곱으로 들어오면 나머지 전부를 이긴다.

처방은 결국 “대응을 믿지 마라”로 수렴한다.

처방	하는 일
거리 임계 거부	대응 거리가 어떤 값(예: 잔차 중앙값의 몇 배)을 넘으면 버린다
트림드 ICP	잔차가 작은 상위 $\alpha$ 비율만 써서 절대정위를 푼다
로버스트 손실	제곱 대신 후버·코시·저먼-맥클루어 손실. 큰 잔차의 영향력을 포화시킨다
점진적 비볼록화	로버스트 손실의 폭을 크게 시작해 서서히 좁힌다. 수렴 반경을 넓히는 표준 트릭
법선 일치 검사	대응점의 법선 사이 각이 크면 버린다. 앞뒷면이 짝지어지는 사고를 막는다
겹침 비율 추정	겹침이 낮다고 판단되면 아예 전역 정합으로 되돌아간다

7. 가속 — 최근접점 탐색이 병목이다[편집]

한 반복의 비용은 사실상 최근접점 탐색이 결정한다. 무식하게 하면 $O(N M)$ .

KD-트리. 3차원 점 $M$ 개를 축 정렬 초평면으로 재귀 분할해 질의당 평균 $O(\log M)$ . 정합 코드의 기본값. 트리 구축은 $O(M\log M)$ 이고 목표 점군이 고정이면 한 번만 하면 된다. 이웃 개념의 자료구조라는 점에서 경계 볼륨 계층이나 반스-헛 알고리즘의 옥트리와 사촌 관계다.
투영 기반 대응. 두 점군이 모두 거리영상(range image)이면, 변환한 점을 목표 센서의 영상 평면에 투영해 그 화소의 점을 대응으로 삼는다. 질의당 $O(1)$ 이라 실시간 RGB-D 정합(KinectFusion 계열)이 이 방식을 쓴다. 정확한 최근접점은 아니지만 반복 안에서 어차피 고쳐진다.
샘플링. 전부 쓰지 않는다. 루신키에비치와 레보이(2001)가 정리한 ICP 변형 비교에서 특히 유용한 것이 법선 공간 균등 샘플링 — 법선 방향이 골고루 섞이도록 점을 고르면, 평평한 면이 압도적으로 많은 장면에서도 구속이 약한 방향의 정보가 살아남아 수렴이 빨라진다.
복셀 다운샘플. 격자 한 칸당 한 점(무게중심)으로 줄인다. 가장 싸고 가장 자주 쓰이며, 격자 크기가 사실상 정합 정확도의 하한을 정한다.

8. 전역 정합 — 초기값을 만드는 문제[편집]

ICP는 국소 정련기다. 초기값은 따로 만들어야 하고, 그 방법은 크게 셋이다.

특징 기반 + RANSAC. 각 점 주변의 기하를 서술자로 요약해 두 점군 사이에서 유사한 서술자끼리 짝을 짓는다. 루수 등의 FPFH(Fast Point Feature Histogram, 2009)가 대표로, 점과 이웃들 사이의 법선 각도 관계를 히스토그램으로 만들되 이웃의 히스토그램을 가중 합산해 $O(nk)$ 로 낮춘 물건이다. 이렇게 얻은 대응 후보는 오대응이 절반을 훌쩍 넘는 것이 정상이라 RANSAC으로 거른다 — 3쌍을 무작위로 뽑아 변환을 만들고, 그 변환이 설명하는 대응(inlier) 수를 세고, 가장 많은 것을 채택한다. 저우 등의 Fast Global Registration(2016)은 RANSAC 대신 로버스트 손실 + 점진적 비볼록화로 같은 일을 훨씬 빠르게 하고, TEASER++(2021)는 이상치가 99%여도 최적성을 인증하는 해를 낸다.

분지한정. 양 등의 Go-ICP(2013)는 분지한정법으로 $SE(3)$ 전체를 탐색해 전역 최적을 증명 가능하게 찾는다. 회전 공간은 각축 표현의 반지름 $\pi$ 인 공을 감싸는 정육면체로, 병진 공간은 또 다른 정육면체로 나누고, 각 상자에 대해 그 안의 어떤 변환도 넘을 수 없는 오차 하계를 유도해 상계보다 나쁜 상자를 통째로 쳐낸다. 상계 계산에는 그냥 ICP를 돌린다 — 국소 정련을 분지한정의 심장에 넣은 구조라 이름이 Go-ICP다. 전역 최적을 보장하는 대신 느리고, 점 수와 요구 정밀도에 비용이 민감하다. 오프라인 검증에는 훌륭하고 실시간에는 못 쓴다가 공정한 평가다.⁵

사전 정보. 실무에서 가장 자주 쓰이는 방법이기도 하다. 로봇의 주행거리계, IMU, 턴테이블 각도, 이전 프레임의 자세 — 초기값을 공짜로 주는 센서가 있으면 위의 모든 고민이 사라진다. SLAM 프론트엔드가 ICP를 이렇게 쓴다.

9. NDT — 대응을 아예 만들지 않는다[편집]

비버와 슈트라서(2003)의 NDT(Normal Distributions Transform)는 다른 길을 간다. 목표 점군을 복셀로 나누고 각 복셀 안의 점들을 정규분포 $\mathcal N(\mu_k, \Sigma_k)$ 로 적합해, 점군을 조각별 연속인 확률밀도로 바꾼다. 그다음 원본 점군을 변환해 이 밀도 위에서의 점수

s(R,t) \;=\; \sum_i \exp\!\left(-\tfrac{1}{2}\,(x_i-\mu_{k(i)})^{\mathsf T}\Sigma_{k(i)}^{-1}(x_i-\mu_{k(i)})\right), \qquad x_i = Rp_i + t

를 최대화한다. 목적함수가 매끄럽고 해석적 1·2차 도함수가 있으므로 뉴턴법이나 신뢰영역법을 그대로 쓴다.

장점이 셋이다. 최근접점 탐색이 없다(복셀 인덱스 계산이 $O(1)$ ). 목적함수가 미분 가능해 반복마다 대응이 바뀌며 생기는 불연속이 없다. 그리고 복셀을 크게 잡으면 밀도가 넓게 퍼져 수렴 반경이 넓어진다 — 굵은 복셀에서 시작해 가늘게 줄이는 다중해상도 전략이 자연스럽다. 단점은 복셀 크기라는 손잡이에 결과가 민감하고, 이산화 인공물이 남는다는 것. 라이다 오도메트리 쪽에서 ICP 계열과 나란히 표준으로 쓰인다.

10. 실무 체크리스트[편집]

중심화가 먼저, 회전이 나중. 무게중심을 안 맞춘 채 회전만 최적화하면 전혀 다른 답이 나온다.
$\det$ 보정을 확인한다. 데이터가 거의 평면이면 부호가 실행마다 뒤집힌다.
잔차 히스토그램을 본다. 평균 잔차 하나만 보면 절반이 엉뚱하게 붙었어도 모른다. 봉우리가 두 개면 오대응이 뭉쳐 있다는 뜻.
$A^{\mathsf T}A$ 의 고윳값을 찍어 본다. 구속이 약한 방향을 알아야 결과를 얼마나 믿을지 정할 수 있다.
다중 스캔은 쌍별 ICP를 이어 붙이지 않는다. 오차가 누적돼 마지막에 안 닫힌다. 모든 스캔의 자세를 동시에 푸는 전역 최적화(포즈 그래프, 번들 조정)로 마무리한다.
정합 오차와 측정 오차를 혼동하지 않는다. RMS 0.05 mm가 나왔다고 스캐너 정밀도가 0.05 mm인 것은 아니다 — 겹침이 좁으면 그냥 좁은 영역만 잘 맞춘 것이다.

11. 관련 문서[편집]

더 얄궂은 것은, 그렇게 억지로 발동시킨 구간에서 보정을 «빼면» 최종 RMS가 오히려 낮게 나온다는 점이다(0.019 대 0.038). 거울상은 점을 더 잘 맞춘다. 더 잘 맞추는 답이 틀린 답이라는 사실이 정합 문제의 성격을 요약한다. ↩
베슬과 맥케이의 1992년 논문은 점·선분·삼각형·매개변수 곡면까지 포괄하는 일반적 정식화였는데, 세상이 기억하는 것은 “가장 가까운 점 찾아서 반복”이라는 네 줄뿐이다. 아이디어가 단순할수록 인용은 늘고 논문은 안 읽힌다. ↩
point-to-plane 아이디어는 사실 첸-메디오니 논문에서도 주인공이 아니었다. 여러 거리 영상을 합쳐 물체 모델을 만드는 시스템 논문의 한 구성요소였는데, 그 구성요소만 살아남아 30년째 현역이다. ↩
이 “미끄러진다”는 감각은 시추공이나 터널 스캔을 해 본 사람이면 몸으로 안다. 화면상으로는 완벽하게 겹쳐 보이는데 길이 방향으로 몇 미터가 밀려 있고, 그 사실은 지도를 다 만들고 나서 시작점과 끝점이 안 맞을 때에야 드러난다. ↩
Go-ICP는 “ICP를 전역 최적화한다”가 아니라 “ICP의 목적함수를 전역 최적화한다”이다. 즉 ICP가 찾던 그 비볼록 함수의 진짜 최소를 찾아준다는 뜻이지, 정합이 물리적으로 옳다는 보장은 아니다. 데이터가 대칭이면 전역 최소도 여러 개다. ↩