6.45 SVD의 컴퓨터 비전 및 점 구름 정합 응용

1. 도입

컴퓨터 비전과 3차원 점 구름 처리에서 특이값 분해는 가장 빈번하게 사용되는 수치 도구 중 하나이다. 영상에서 추출된 특징점 사이의 기하학적 관계를 추정하는 문제, 다중 시점 영상으로부터 카메라 자세를 복원하는 문제, 그리고 점 구름들 사이의 강체 변환을 추정하는 문제 등은 모두 직사각 또는 특이 행렬에 대한 분석을 요구하며, 특이값 분해가 그 분석의 핵심 도구로 작용한다. 이 절에서는 SVD가 컴퓨터 비전과 점 구름 정합에서 어떻게 활용되는지를 체계적으로 다룬다.

2. 점 구름 정합 문제의 정식화

두 점 집합 $\{\mathbf{p}_i\}_{i=1}^{N}$ 과 $\{\mathbf{q}_i\}_{i=1}^{N}$ 가 주어지고, 두 집합의 대응 관계가 알려져 있다고 하자. 정합 문제는 다음의 최소 제곱 문제

$\min_{R, \mathbf{t}} \sum_{i=1}^{N} \| (R\mathbf{p}_i + \mathbf{t}) - \mathbf{q}_i \|^2$

를 풀어서 회전 행렬 $R \in SO(3)$ 와 병진 벡터 $\mathbf{t} \in \mathbb{R}^3$ 를 결정하는 문제이다. 여기서 $R$ 이 회전 행렬이라는 제약은 $R^\top R = I$ 이고 $\det R = +1$ 임을 의미한다.

3. 카브쉬 알고리듬

점 구름 정합 문제의 닫힌 형식 해를 제공하는 가장 우아한 방법은 카브쉬 알고리듬(Kabsch algorithm)이다. 이 알고리듬은 다음의 단계로 구성된다.

중심 계산: 각 집합의 중심을 계산한다.

$\bar{\mathbf{p}} = \frac{1}{N}\sum_{i=1}^{N} \mathbf{p}_i, \qquad \bar{\mathbf{q}} = \frac{1}{N}\sum_{i=1}^{N} \mathbf{q}_i$
중심 이동: 각 점에서 중심을 빼서 중심화된 점들을 만든다.

$\tilde{\mathbf{p}}_i = \mathbf{p}_i - \bar{\mathbf{p}}, \qquad \tilde{\mathbf{q}}_i = \mathbf{q}_i - \bar{\mathbf{q}}$
교차 공분산 행렬 구성: 두 점 집합의 교차 공분산 행렬을 계산한다.

$H = \sum_{i=1}^{N} \tilde{\mathbf{p}}_i \tilde{\mathbf{q}}_i^\top \in \mathbb{R}^{3 \times 3}$
특이값 분해: $H = U\Sigma V^\top$ 를 계산한다.
회전 행렬 추출: 다음과 같이 최적 회전 행렬을 구성한다.

$R = V \, \mathrm{diag}(1, 1, \det(VU^\top)) \, U^\top$

대각 행렬에서 $\det(VU^\top)$ 가 등장하는 이유는 회전 행렬의 행렬식이 양수가 되도록 보정하기 위함이다. 이 보정이 없으면 결과가 거울 반사를 포함할 수 있다.

병진 벡터 계산:

$\mathbf{t} = \bar{\mathbf{q}} - R\bar{\mathbf{p}}$

4. 카브쉬 알고리듬의 정당성

카브쉬 알고리듬이 최적 정합을 제공함은 다음과 같이 증명된다. 중심 이동 후의 비용 함수는

$J(R) = \sum_{i=1}^{N} \|R\tilde{\mathbf{p}}_i - \tilde{\mathbf{q}}_i\|^2 = \sum_i \|\tilde{\mathbf{p}}_i\|^2 + \sum_i \|\tilde{\mathbf{q}}_i\|^2 - 2 \, \mathrm{tr}(R H^\top)$

로 전개된다. 첫 두 항은 $R$ 에 의존하지 않으므로 비용을 최소화하는 것은 $\mathrm{tr}(R H^\top)$ 을 최대화하는 것과 동일하다. SVD $H = U\Sigma V^\top$ 를 대입하고 트레이스의 순환 성질을 활용하면

$\mathrm{tr}(R H^\top) = \mathrm{tr}(R V \Sigma U^\top) = \mathrm{tr}(\Sigma U^\top R V)$

이 된다. 직교 행렬 $M = U^\top R V$ 에 대하여 $|M_{ii}| \leq 1$ 이며, 이로부터

$\mathrm{tr}(\Sigma M) = \sum_{i=1}^{3} \sigma_i M_{ii} \leq \sum_{i=1}^{3} \sigma_i$

가 얻어진다. 등호는 $M = I$ 일 때, 즉 $R = VU^\top$ 일 때 성립한다. 회전 행렬의 행렬식 조건을 만족시키기 위하여 마지막에 보정 행렬이 곱해지며, 이로써 알고리듬이 완성된다. $\blacksquare$

5. 거울 반사 문제와 보정

$\det(VU^\top) = -1$ 인 경우는 두 점 집합이 거울 대칭에 가까운 분포를 가질 때 발생한다. 이 경우 보정 없이 단순히 $R = VU^\top$ 를 사용하면 행렬식이 $-1$ 인 직교 행렬, 즉 거울 반사를 얻게 된다. 이는 물리적으로 회전이 아니므로 받아들일 수 없다.

보정 행렬 $\mathrm{diag}(1, 1, \det(VU^\top))$ 는 가장 작은 특이값에 대응하는 방향을 반전시킴으로써 행렬식을 양수로 만든다. 이 선택은 최적성을 거의 손상시키지 않는데, 가장 작은 특이값 방향에서의 보정은 가장 작은 비용 변화를 의미하기 때문이다.

6. 본질 행렬과 카메라 자세 복원

스테레오 시각 또는 단일 카메라의 시간 변화 영상으로부터 카메라 자세를 복원하는 문제는 본질 행렬(essential matrix)과 밀접한 관계를 가진다. 두 정규화된 영상 좌표 $\hat{\mathbf{x}}_1$ 과 $\hat{\mathbf{x}}_2$ 사이에는 에피폴라 제약

$\hat{\mathbf{x}}_2^\top E \hat{\mathbf{x}}_1 = 0$

이 성립하며, 본질 행렬 $E$ 는 두 카메라 사이의 회전 $R$ 과 병진 $\mathbf{t}$ 에 의하여 $E = [\mathbf{t}]_\times R$ 로 정의된다. 본질 행렬은 다음의 핵심 성질을 가진다.

랭크가 정확히 $2$ 이다.
두 영이 아닌 특이값이 서로 같다.

본질 행렬을 추정한 후 그로부터 회전과 병진을 복원하는 과정에서 SVD가 핵심적으로 사용된다. $E = U\Sigma V^\top$ 에서 다음과 같이 $R$ 과 $\mathbf{t}$ 를 추출한다.

$W = \begin{pmatrix} 0 & -1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix}$

$R = U W V^\top \quad \text{또는} \quad R = U W^\top V^\top, \qquad [\mathbf{t}]_\times = U W \Sigma U^\top$

이 분해는 네 가지 가능한 해를 산출하며, 그 중 정확한 해는 추가적인 양의 깊이 조건(positive depth condition)을 통하여 선택된다.

7. 본질 행렬의 정사영

추정된 본질 행렬은 잡음으로 인하여 정확한 본질 행렬의 성질을 만족하지 않을 수 있다. 즉, 두 영이 아닌 특이값이 서로 다르거나 가장 작은 특이값이 정확히 영이 아닐 수 있다. 이를 보정하기 위하여 추정된 행렬을 본질 행렬의 부분 다양체로 정사영한다. SVD $E_{\text{est}} = U\Sigma_{\text{est}} V^\top$ 에서

$E_{\text{proj}} = U \, \mathrm{diag}(1, 1, 0) \, V^\top$

또는 두 특이값의 평균을 사용한 형태로 보정한다. 이 정사영은 본질 행렬의 정의를 정확히 만족하는 가장 가까운 행렬을 제공한다.

8. 기본 행렬과 8점 알고리듬

본질 행렬의 일반화된 형태인 기본 행렬(fundamental matrix)은 카메라 내부 매개 변수를 알 수 없는 일반적인 경우에 사용된다. 기본 행렬은 두 영상 좌표 사이의 에피폴라 제약 $\mathbf{x}_2^\top F \mathbf{x}_1 = 0$ 을 만족하는 $3 \times 3$ 랭크 2 행렬이다. 기본 행렬을 추정하는 표준적인 방법은 8점 알고리듬(eight-point algorithm)이며, 이 알고리듬의 핵심은 SVD이다.

8쌍 이상의 대응점 $\{(\mathbf{x}_1^{(i)}, \mathbf{x}_2^{(i)})\}$ 이 주어지면 각 대응으로부터 $F$ 의 원소들에 대한 선형 방정식이 얻어진다. 이를 모아 동차 선형 시스템

$A \mathbf{f} = \mathbf{0}$

을 형성한다. 여기서 $\mathbf{f}$ 는 $F$ 의 원소들을 벡터화한 것이며, $A$ 는 $N \times 9$ 행렬이다. 이 시스템의 최소 제곱 해는 $A$ 의 SVD에서 가장 작은 특이값에 대응하는 우특이벡터로 주어진다. 이렇게 얻어진 $F$ 는 일반적으로 랭크가 정확히 $2$ 가 아니므로, 다시 SVD를 통하여 가장 작은 특이값을 영으로 만드는 정사영을 수행한다.

9. 호모그래피 추정

평면 위의 점들에 대한 두 영상 사이의 변환은 호모그래피(homography) 행렬 $H$ 로 표현된다.

$\mathbf{x}_2 \sim H \mathbf{x}_1$

여기서 $\sim$ 는 동차 좌표에서의 등호를 의미한다. 4쌍 이상의 대응점으로부터 $H$ 를 추정하는 직접 선형 변환(direct linear transform, DLT) 알고리듬도 SVD를 활용한다. 각 대응으로부터 두 개의 선형 방정식이 얻어지며, 이를 모아 동차 시스템을 형성한 후 가장 작은 특이값에 대응하는 우특이벡터로부터 $H$ 를 추출한다.

10. 카메라 행렬의 분해

투영 행렬 $P = K[R \mid \mathbf{t}]$ 로부터 내부 매개 변수 행렬 $K$ , 회전 $R$ , 그리고 병진 $\mathbf{t}$ 를 분해하는 문제는 RQ 분해 또는 QR 분해를 통하여 해결된다. 이 분해 과정에서도 SVD가 직간접적으로 활용되며, 분해의 안정성을 보장한다.

11. 점 구름 정합의 견고한 변형

기본 카브쉬 알고리듬은 모든 대응이 정확하다고 가정하지만, 실제 점 구름 정합에서는 일부 대응이 잘못된 외부치(outlier)일 수 있다. 이를 처리하기 위한 견고한 변형들이 개발되어 있다.

11.1 RANSAC 기반 정합

RANSAC(random sample consensus) 기법은 무작위로 선택된 부분 집합을 사용하여 카브쉬 알고리듬을 반복적으로 적용하고, 그 결과에 부합하는 내부치(inlier)의 수를 평가한다. 가장 많은 내부치를 가지는 가설이 최종 정합 결과로 채택된다. 각 RANSAC 반복에서 SVD가 핵심 단계로 사용된다.

11.2 가중 최소 제곱

각 대응에 신뢰도 가중치를 부여하여 가중 최소 제곱 문제로 정식화하는 변형도 있다. 가중치를 반영한 교차 공분산 행렬

$H = \sum_{i=1}^{N} w_i \tilde{\mathbf{p}}_i \tilde{\mathbf{q}}_i^\top$

에 대하여 동일한 SVD 절차가 적용된다.

11.3 M-추정자 기반 변형

M-추정자(M-estimator)는 큰 잔차에 대한 영향을 줄이는 손실 함수를 사용함으로써 외부치에 견고하다. 반복 가중 최소 제곱(iteratively reweighted least squares) 형태로 구현되며, 매 반복에서 SVD를 통한 가중 정합이 수행된다.

12. 반복 최근점 알고리듬

대응 관계가 사전에 알려지지 않은 경우 반복 최근점 알고리듬(iterative closest point, ICP)이 사용된다. ICP는 다음의 두 단계를 반복한다.

최근점 매칭: 현재 변환 추정 하에서 각 점에 가장 가까운 대응점을 찾는다.
변환 갱신: 대응 관계를 고정한 상태에서 카브쉬 알고리듬(또는 그 변형)을 사용하여 변환을 갱신한다.

이 두 단계가 수렴할 때까지 반복된다. 두 번째 단계에서 SVD가 핵심적으로 사용되며, ICP의 효율성과 안정성에 결정적인 역할을 한다.

13. 영상 잡음 제거와 저랭크 근사

영상은 종종 행렬로 표현되며, 자연 영상은 본질적으로 저랭크 구조를 가지는 경향이 있다. 측정 잡음이 모든 특이값에 분포하는 반면, 영상의 본질적 정보는 큰 특이값에 집중되어 있다. 따라서 절단 SVD를 적용하여 작은 특이값을 제거하면 효과적인 잡음 제거를 달성할 수 있다.

또한 영상의 패치(patch)들에 대한 그룹 저랭크 근사(group low-rank approximation)는 비국소 자기 유사성(non-local self-similarity)을 활용하는 고급 영상 복원 기법의 토대이다.

14. 점 구름의 표면 법선 추정

점 구름의 각 점 주변의 국소 이웃에 대하여 공분산 행렬을 구성하고 SVD를 수행하면, 가장 작은 특이값에 대응하는 우특이벡터가 표면 법선 방향을 제공한다. 이는 점 구름의 평면성과 곡률을 평가하는 기초적인 도구이며, 표면 재구성, 분할, 그리고 형상 인식에 활용된다.

15. 다시점 기하학과 인수분해

여러 시점에서 관찰된 특징점들의 좌표를 모은 측정 행렬은 일반적으로 큰 직사각 행렬이며, 잡음이 없는 이상적인 경우 정확히 랭크 4(자세 정보 3 + 점 좌표 3, 한 자유도는 동차성으로 흡수됨)이다. 토마시-카나데(Tomasi-Kanade) 인수분해 기법은 이 측정 행렬에 대한 SVD를 통하여 카메라 자세와 3차원 점 좌표를 동시에 복원한다. 이는 구조 복원(structure from motion)의 고전적인 알고리듬이며, 현대적인 변형들의 토대를 제공한다.

16. 로봇공학에서의 통합 응용

16.1 시각 SLAM

시각 동시 위치 추정 및 지도 작성(visual SLAM)에서 SVD는 다음의 여러 단계에서 활용된다.

본질 행렬과 호모그래피 행렬의 추정
키 프레임 사이의 상대 자세 계산
점 구름 기반 루프 클로저 검출
묶음 조정(bundle adjustment)의 부분 단계

이러한 응용에서 SVD의 수치적 안정성은 SLAM 시스템 전체의 신뢰성에 직접적으로 영향을 미친다.

16.2 라이다 기반 측위

라이다 센서로부터 얻어진 점 구름들 사이의 정합은 자율 주행 차량과 모바일 로봇의 측위에서 핵심적이다. ICP와 그 변형들은 카브쉬 알고리듬과 SVD에 의존하며, 매 측정 주기마다 효율적으로 수행되어야 한다.

16.3 객체 인식과 자세 추정

알려진 객체의 모델과 관찰된 점 구름 사이의 정합을 통하여 객체의 자세를 추정하는 문제는 로봇 파지와 조립에 필수적이다. 이는 본질적으로 점 구름 정합 문제이며, SVD가 핵심 도구이다.

16.4 다중 카메라 시스템 보정

다중 카메라 시스템의 외부 보정은 카메라 사이의 상대 자세를 추정하는 문제로 환원되며, 본질 행렬 분해와 SVD를 통하여 해결된다.

참고문헌

Kabsch, W. (1976). A solution for the best rotation to relate two sets of vectors. Acta Crystallographica Section A, 32(5), 922-923.
Hartley, R., & Zisserman, A. (2004). Multiple View Geometry in Computer Vision (2nd ed.). Cambridge University Press.
Szeliski, R. (2022). Computer Vision: Algorithms and Applications (2nd ed.). Springer.
Besl, P. J., & McKay, N. D. (1992). A method for registration of 3-D shapes. IEEE Transactions on Pattern Analysis and Machine Intelligence, 14(2), 239-256.
Tomasi, C., & Kanade, T. (1992). Shape and motion from image streams under orthography: A factorization method. International Journal of Computer Vision, 9(2), 137-154.
Forsyth, D. A., & Ponce, J. (2011). Computer Vision: A Modern Approach (2nd ed.). Pearson.

Version: 1.0