최소 대응점 수와 해법

최소 대응점 수

기본 행렬(Fundamental Matrix)은 두 이미지 간의 점 대응 관계를 정의하는 3x3 행렬이다. 이 행렬을 계산하기 위해서는 최소한 7개의 대응점이 필요하다. 그러나 일반적으로 8개의 대응점을 사용하는 8-point 알고리즘이 더 많이 사용되며, 이는 계산적으로 안정적이고 직관적이다.

기본 행렬은 다음과 같은 선형 방정식을 만족시킨다.

$\mathbf{x'}^\top \mathbf{F} \mathbf{x} = 0$

여기서, - $\mathbf{x}$ 는 첫 번째 이미지에서의 대응점 $(x, y, 1)^\top$ 을 나타내는 3차원 동차 좌표(homogeneous coordinates)이고, - $\mathbf{x'}$ 는 두 번째 이미지에서의 대응점 $(x', y', 1)^\top$ 을 나타낸다. - $\mathbf{F}$ 는 3x3 기본 행렬이다.

이 식은 각 대응점 쌍마다 하나의 방정식을 제공한다. 기본 행렬의 각 성분들은 자유도가 8이므로, 이를 구하려면 최소한 8개의 대응점이 필요하게 된다.

해법: 8-point 알고리즘

1. 방정식 구성

두 이미지에서의 대응점 $\mathbf{x}_i = (x_i, y_i, 1)^\top$ 와 $\mathbf{x'}_i = (x'_i, y'_i, 1)^\top$ 에 대해 다음과 같은 방정식을 구성할 수 있다.

$x'_i (f_{11} x_i + f_{12} y_i + f_{13}) + y'_i (f_{21} x_i + f_{22} y_i + f_{23}) + (f_{31} x_i + f_{32} y_i + f_{33}) = 0$

이를 보다 간단히 표현하면:

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

여기서, - $\mathbf{f} = (f_{11}, f_{12}, f_{13}, f_{21}, f_{22}, f_{23}, f_{31}, f_{32}, f_{33})^\top$ 는 기본 행렬 $\mathbf{F}$ 의 9개의 성분을 벡터로 나타낸 것이다. - $\mathbf{A}$ 는 대응점 정보로 구성된 $N \times 9$ 행렬이다.

2. 선형 방정식 풀기

이제 최소 대응점 수인 8개의 점을 사용하면, 방정식 시스템은 과잉 결정(over-determined)되고, 다음과 같은 형태의 선형 방정식을 얻는다.

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

여기서 $\mathbf{A}$ 는 8개의 대응점으로부터 얻어진 $8 \times 9$ 행렬이고, $\mathbf{f}$ 는 9개의 성분을 포함한 벡터이다.

이 방정식을 풀기 위해서는 보통 SVD(Singular Value Decomposition)를 사용하여 근사 해를 구한다. $\mathbf{A}$ 에 대해 SVD를 수행하면,

$\mathbf{A} = \mathbf{U} \mathbf{\Sigma} \mathbf{V}^\top$

여기서, $\mathbf{U}$ 와 $\mathbf{V}$ 는 직교 행렬, $\mathbf{\Sigma}$ 는 대각 행렬이다. 이 때, $\mathbf{f}$ 는 $\mathbf{V}$ 의 마지막 열벡터로 근사할 수 있다.

3. 기본 행렬의 제약 조건

계산된 $\mathbf{F}$ 는 일반적으로 순위가 3인 행렬이다. 그러나 기본 행렬은 본질적으로 순위가 2여야 하므로, 순위를 2로 제한하는 추가적인 단계가 필요하다. 이를 위해, 기본 행렬을 다시 SVD 분해하여 순위를 조정할 수 있다.

기본 행렬 $\mathbf{F}$ 를 SVD로 분해하면 다음과 같다:

$\mathbf{F} = \mathbf{U} \mathbf{\Sigma} \mathbf{V}^\top$

여기서, $\mathbf{\Sigma}$ 는 대각 행렬로, 세 개의 특이값(singular values)이 있다. 이 중 가장 작은 특이값을 0으로 설정하여 $\mathbf{F}$ 의 순위를 2로 만든다. 즉,

$\mathbf{\Sigma}' = \text{diag}(\sigma_1, \sigma_2, 0)$

이 수정된 $\mathbf{\Sigma}'$ 를 사용하여 새로운 기본 행렬 $\mathbf{F'}$ 를 계산한다:

$\mathbf{F'} = \mathbf{U} \mathbf{\Sigma}' \mathbf{V}^\top$

4. 결과 정규화

마지막으로, 계산된 기본 행렬 $\mathbf{F'}$ 를 정규화한다. 이는 행렬의 마지막 성분 $f_{33}$ 를 1로 만들기 위해 각 성분을 $f_{33}$ 로 나누는 과정이다. 이렇게 하면 기본 행렬이 다음과 같이 정규화된다:

$\mathbf{F'} = \frac{\mathbf{F'}}{f_{33}}$

이 과정을 통해 8-point 알고리즘에 의해 계산된 기본 행렬은 두 이미지 간의 대응점을 설명하는 최종적인 행렬이 된다.