6.150 특징점 매칭과 RANSAC의 행렬 연산

로봇 비전 시스템에서 두 이미지 사이의 기하학적 관계(기본 행렬, 본질 행렬, 호모그래피 등)를 추정하려면, 먼저 이미지 간의 점 대응(point correspondence)을 확보해야 한다. 특징점 매칭(feature matching)으로 얻어진 대응에는 필연적으로 오매칭(outlier)이 포함되므로, 이를 효과적으로 처리하는 강건 추정(robust estimation) 기법이 필수적이다. 본 절에서는 특징점 매칭의 행렬 연산과 RANSAC(RANdom SAmple Consensus) 알고리즘의 선형대수학적 구조를 다룬다.

1. 특징점 기술자와 매칭의 행렬 표현

이미지에서 검출된 N개의 특징점에 대하여 각 특징점의 기술자(descriptor)를 \mathbf{d}_i \in \mathbb{R}^D라 하자. 전체 기술자 집합은 다음의 행렬로 표현된다.

\mathcal{D} = \begin{bmatrix} \mathbf{d}_1^\top \\ \mathbf{d}_2^\top \\ \vdots \\ \mathbf{d}_N^\top \end{bmatrix} \in \mathbb{R}^{N \times D}

두 이미지의 기술자 행렬이 \mathcal{D}_1 \in \mathbb{R}^{N_1 \times D}, \mathcal{D}_2 \in \mathbb{R}^{N_2 \times D}일 때, 모든 쌍 사이의 거리 행렬(distance matrix) \mathcal{M} \in \mathbb{R}^{N_1 \times N_2}를 구성한다. 유클리드 거리의 경우 다음과 같다.

\mathcal{M}_{ij} = \lVert \mathbf{d}_{1,i} - \mathbf{d}_{2,j} \rVert_2

유클리드 거리의 제곱은 다음과 같이 행렬 연산으로 효율적으로 계산할 수 있다.

\mathcal{M}_{ij}^2 = \lVert \mathbf{d}_{1,i} \rVert^2 + \lVert \mathbf{d}_{2,j} \rVert^2 - 2 \mathbf{d}_{1,i}^\top \mathbf{d}_{2,j}

이를 행렬 형태로 쓰면 다음과 같다.

\mathcal{M}^2 = \mathbf{s}_1 \mathbf{1}^\top + \mathbf{1} \mathbf{s}_2^\top - 2 \mathcal{D}_1 \mathcal{D}_2^\top

여기서 \mathbf{s}_1 \in \mathbb{R}^{N_1}은 (\mathbf{s}_1)_i = \lVert \mathbf{d}_{1,i} \rVert^2이고, \mathbf{s}_2 \in \mathbb{R}^{N_2}는 (\mathbf{s}_2)_j = \lVert \mathbf{d}_{2,j} \rVert^2이다. 핵심 연산은 행렬 곱 \mathcal{D}_1 \mathcal{D}_2^\top이며, O(N_1 N_2 D)의 계산 복잡도를 가진다.

2. 최근접 이웃 매칭과 비율 검정

각 특징점 \mathbf{d}_{1,i}에 대하여 거리 행렬의 i번째 행에서 최소값을 가지는 인덱스를 찾으면 최근접 이웃(nearest neighbor) 매칭이 된다.

j^* = \arg\min_j \mathcal{M}_{ij}

Lowe의 비율 검정(ratio test)은 최근접 거리와 차근접(second nearest) 거리의 비율로 매칭 신뢰도를 평가한다. i번째 행에서 가장 작은 두 거리를 d_1 \leq d_2라 하면 다음과 같다.

\frac{d_1}{d_2} < \tau

여기서 \tau는 임계값(통상 0.7 \sim 0.8)이다. 비율이 \tau보다 작으면 매칭이 모호하지 않다고 판단하여 채택한다.

3. RANSAC 알고리즘의 개요

RANSAC은 아웃라이어가 포함된 데이터에서 모델 파라미터를 강건하게 추정하는 반복적 알고리즘이다. 기하학적 모델 추정 문맥에서 RANSAC의 절차는 다음과 같다.

입력: N개의 점 대응 \{(\tilde{\mathbf{p}}_{1,i}, \tilde{\mathbf{p}}_{2,i})\}_{i=1}^N, 모델에 필요한 최소 점 수 s, 인라이어 임계값 \epsilon, 반복 횟수 K

절차:

1. N개의 대응 중에서 s개를 무작위로 선택한다.
2. 선택된 s개의 대응으로 최소 해(minimal solution)를 구한다.
3. 나머지 모든 대응에 대하여 모델과의 오차를 계산하고, 인라이어(오차 < \epsilon인 대응)를 결정한다.
4. 인라이어 수가 이전 최대값보다 크면 현재 모델을 최적 모델로 갱신한다.
5. K번 반복한다.
6. 최적 모델의 인라이어 집합으로 모델을 재추정(refinement)한다.

4. RANSAC에서의 행렬 연산

4.1 최소 해 구하기

각 반복에서 s개의 대응으로부터 모델을 추정하는 과정은 선형 시스템의 풀이에 해당한다.

호모그래피 (s = 4): 4개의 대응으로부터 8 \times 9 행렬 A를 구성하고, A의 영공간을 SVD로 구한다.

기본 행렬 (s = 7 또는 8): 7점 알고리즘은 영공간의 선형 결합과 \det 조건으로 3차 다항식을 풀고, 8점 알고리즘은 8 \times 9 행렬의 SVD를 사용한다.

본질 행렬 (s = 5): 5점 알고리즘은 영공간의 기저로부터 다항식 시스템을 풀어 최대 10개의 해를 구한다.

4.2 오차 계산의 행렬화

N개의 대응 전체에 대한 오차를 한꺼번에 계산하면 벡터화된 연산이 가능하다.

호모그래피의 경우: 전달 오차(transfer error)는 다음과 같다.

e_i = \lVert \tilde{\mathbf{p}}_{2,i} - \frac{1}{(H \tilde{\mathbf{p}}_{1,i})_3} H \tilde{\mathbf{p}}_{1,i} \rVert^2

전체 대응에 대한 변환을 행렬 곱으로 수행한다.

\tilde{P}_2' = H \tilde{P}_1

여기서 \tilde{P}_1 = [\tilde{\mathbf{p}}_{1,1}, \dots, \tilde{\mathbf{p}}_{1,N}] \in \mathbb{R}^{3 \times N}이다.

기본 행렬의 경우: 삼선 오차(Sampson distance)는 에피폴라 제약의 1차 근사를 이용한 기하학적 거리이다.

e_i^2 = \frac{(\tilde{\mathbf{p}}_{2,i}^\top F \tilde{\mathbf{p}}_{1,i})^2}{(F \tilde{\mathbf{p}}_{1,i})_1^2 + (F \tilde{\mathbf{p}}_{1,i})_2^2 + (F^\top \tilde{\mathbf{p}}_{2,i})_1^2 + (F^\top \tilde{\mathbf{p}}_{2,i})_2^2}

여기서 하첨자 1, 2는 벡터의 첫째, 둘째 성분을 의미한다.

5. RANSAC의 반복 횟수 결정

인라이어 비율을 w, 최소 표본 크기를 s, 원하는 성공 확률을 p라 하면, 필요한 반복 횟수 K는 다음과 같다.

K = \frac{\ln(1 - p)}{\ln(1 - w^s)}

(표: p = 0.99에서의 필요 반복 횟수)

최소 표본 크기 s가 작을수록 반복 횟수가 급격히 줄어들므로, 5점 알고리즘을 RANSAC과 결합하는 것이 8점 알고리즘보다 효율적이다.

6. 가중 최소 제곱 재추정

RANSAC으로 인라이어 집합 \mathcal{I}가 결정되면, 인라이어만을 사용하여 모델을 재추정한다. 가중 최소 제곱(WLS) 방식으로 재추정하는 경우, 가중 비용 함수는 다음과 같다.

J = \sum_{i \in \mathcal{I}} w_i \, e_i^2

여기서 w_i는 각 대응의 가중치로, 오차가 작을수록 높은 가중치를 부여한다. 행렬 형태로 표현하면 다음과 같다.

A^\top W A \, \mathbf{h} = A^\top W \mathbf{b}

여기서 W = \text{diag}(w_1, w_2, \dots, w_{\vert\mathcal{I}\vert})는 가중 대각 행렬이다.

7. M-추정량과 강건 비용 함수

RANSAC의 이진적(binary) 인라이어/아웃라이어 분류를 완화하여, 연속적인 강건 비용 함수를 사용하는 것이 M-추정량(M-estimator)이다. 대표적인 강건 핵 함수(robust kernel function)는 다음과 같다.

Huber 함수:

\rho(e) = \begin{cases} \frac{1}{2} e^2 & \text{if } \vert e \vert \leq k \\ k \vert e \vert - \frac{1}{2} k^2 & \text{if } \vert e \vert > k \end{cases}

Tukey 이중가중 함수:

\rho(e) = \begin{cases} \frac{k^2}{6} \left[ 1 - \left(1 - \frac{e^2}{k^2}\right)^3 \right] & \text{if } \vert e \vert \leq k \\ \frac{k^2}{6} & \text{if } \vert e \vert > k \end{cases}

M-추정량을 사용한 비용 함수는 다음과 같다.

J = \sum_{i=1}^{N} \rho(e_i)

이를 반복 재가중 최소 제곱(Iteratively Reweighted Least Squares, IRLS)으로 풀면, 각 반복에서 가중 행렬이 갱신되는 가중 최소 제곱 문제로 귀결된다.

w_i^{(k)} = \frac{1}{e_i^{(k)}} \frac{\partial \rho}{\partial e}\bigg\vert_{e = e_i^{(k)}}

8. RANSAC의 변형

기본 RANSAC의 한계를 극복하기 위한 다양한 변형이 제안되었다.

MSAC의 비용 함수는 다음과 같다.

C = \sum_{i=1}^{N} \min(e_i^2, \epsilon^2)

이 비용 함수는 아웃라이어의 오차를 \epsilon^2으로 상한(cap)하여, 큰 오차를 가진 아웃라이어가 비용에 과도한 영향을 미치는 것을 방지한다.

9. 인라이어 집합에서의 최종 모델 추정

RANSAC으로 결정된 인라이어 집합에서의 최종 모델 추정은 과결정 선형 시스템의 최소 제곱 해로 구한다. 호모그래피의 경우, \vert\mathcal{I}\vert개의 인라이어 대응으로 2\vert\mathcal{I}\vert \times 9 행렬 A_{\mathcal{I}}를 구성하고, SVD를 수행한다.

A_{\mathcal{I}} = U \Sigma V^\top

최적 해 \mathbf{h}는 V의 마지막 열이다. 인라이어 수가 충분히 많으면 잡음 평균화 효과(noise averaging)에 의해 최소 해보다 정확한 추정이 가능하다.

참고 문헌

• Fischler, M. A., & Bolles, R. C. (1981). Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography. Communications of the ACM, 24(6), 381-395.
• Hartley, R., & Zisserman, A. (2004). Multiple View Geometry in Computer Vision (2nd ed.). Cambridge University Press.
• Lowe, D. G. (2004). Distinctive Image Features from Scale-Invariant Keypoints. International Journal of Computer Vision, 60(2), 91-110.
• Torr, P. H. S., & Zisserman, A. (2000). MLESAC: A New Robust Estimator with Application to Estimating Image Geometry. Computer Vision and Image Understanding, 78(1), 138-156.

v 0.1