# 최소 대응점 수와 해법

#### 최소 대응점 수

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