최소 대응점 수와 해법

최소 대응점 수

기본 행렬(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 알고리즘에 의해 계산된 기본 행렬은 두 이미지 간의 대응점을 설명하는 최종적인 행렬이 된다.