# RANSAC을 통한 추정

RANSAC(Random Sample Consensus)은 데이터의 외란 또는 노이즈가 있는 환경에서 모델을 추정하는 강력한 방법론 중 하나이다. 특히, 기본 행렬(Fundamental Matrix)을 계산할 때 자주 사용되며, 외란점(outlier)을 효과적으로 제거하면서 좋은 모델을 추정하는 데 유용하다. RANSAC을 적용하는 과정을 단계적으로 설명하겠다.

#### 1. RANSAC 알고리즘 개요

RANSAC은 일련의 반복(iteration)을 통해 외란점을 가진 데이터에서도 안정적인 모델을 추정한다. 알고리즘은 다음과 같은 절차로 진행된다:

1. **랜덤 샘플 선택**: 전체 데이터 중 임의로 소수의 샘플(일반적으로 7\~8개의 대응점)을 선택한다.
2. **모델 추정**: 선택된 샘플을 바탕으로 기본 행렬 $\mathbf{F}$을 추정한다.
3. **합치 점수 계산**: 추정된 모델에 따라 나머지 데이터 점들이 모델에 얼마나 잘 맞는지 평가한다. 이를 위해 모델이 예측한 에피폴라 제약식에 따라 에러를 계산하고, 에러가 특정 임계값 이하인 데이터 점들을 합치(inlier)로 간주한다.
4. **최적의 모델 선택**: 위의 절차를 여러 번 반복하여, 가장 많은 합치점을 가지는 모델을 최종 모델로 선택한다.

이 과정에서 기본 행렬 $\mathbf{F}$의 추정이 핵심이 되며, 에피폴라 기하학적 제약을 기반으로 모델을 평가하게 된다.

#### 2. 기본 행렬 추정에 사용되는 에피폴라 제약식

두 이미지 좌표계에서 대응점 $\mathbf{x}\_i = \[x\_i, y\_i, 1]^T$와 $\mathbf{x}\_i' = \[x\_i', y\_i', 1]^T$는 기본 행렬 $\mathbf{F}$에 대해 다음과 같은 에피폴라 제약식을 만족한다:

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

이 식은 두 대응점이 에피폴라 선 위에 있어야 한다는 제약을 나타낸다. 즉, 대응점 쌍 $\mathbf{x}\_i$와 $\mathbf{x}\_i'$는 기본 행렬 $\mathbf{F}$에 대해 직선적으로 관련되어야 한다.

#### 3. RANSAC을 위한 초기값 선택

RANSAC 알고리즘에서 중요한 단계 중 하나는 기본 행렬을 추정하기 위한 최소한의 대응점 세트를 선택하는 것이다. 일반적으로 기본 행렬을 추정하려면 7\~8쌍의 대응점이 필요하다. 선택된 대응점들에 대해 위에서 설명한 에피폴라 제약식을 사용하여 기본 행렬 $\mathbf{F}$를 계산한다.

#### 4. RANSAC 반복 절차

RANSAC 알고리즘은 여러 번의 반복(iteration)을 통해 최적의 기본 행렬을 찾는다. 각 반복에서는 다음과 같은 과정을 거친다:

1. **랜덤으로 8쌍의 대응점 선택**: 샘플링된 데이터에서 8쌍의 대응점을 선택하여 기본 행렬을 계산한다.
2. **기본 행렬 계산**: 선택된 대응점으로부터 기본 행렬 $\mathbf{F}$를 추정한다. 기본 행렬 추정 방법은 선형적인 8-point 알고리즘이나 비선형 최적화 방법을 사용할 수 있다.
3. **합치(inlier) 검증**: 추정된 기본 행렬 $\mathbf{F}$에 대해 모든 대응점 쌍에 에피폴라 제약을 적용하여 합치 여부를 평가한다. 에러가 일정 임계값 이하인 대응점은 합치로 간주되고, 나머지는 외란점(outlier)으로 처리된다.
4. **최적의 모델 선택**: 여러 번의 반복 중에서 가장 많은 합치점을 가진 기본 행렬 $\mathbf{F}$을 최종 모델로 선택한다.

#### 5. 에피폴라 제약을 통한 오차 계산

RANSAC에서 각 반복마다 기본 행렬을 추정할 때, 모델의 성능을 평가하기 위해 에피폴라 제약을 사용한 오차를 계산해야 한다. 이는 다음과 같은 방식으로 계산된다:

$$
d(\mathbf{x}\_i', \mathbf{F}, \mathbf{x}\_i) = |\mathbf{x}\_i'^\top \mathbf{F} \mathbf{x}\_i|
$$

이때, $d(\mathbf{x}\_i', \mathbf{F}, \mathbf{x}\_i)$는 대응점 쌍 $\mathbf{x}\_i$와 $\mathbf{x}\_i'$ 사이에서 기본 행렬 $\mathbf{F}$에 의한 에피폴라 제약을 위배하는 정도를 나타낸다. 이 값이 임계값 $\epsilon$ 이하일 경우 해당 대응점은 합치로 간주된다.

#### 6. 합치(inlier)와 외란점(outlier)의 정의

RANSAC에서 모델의 성능을 평가하기 위해 합치와 외란점을 구분한다. 앞서 설명한 에피폴라 제약을 기반으로, 대응점 쌍 $\mathbf{x}\_i$와 $\mathbf{x}\_i'$가 모델에 잘 맞는지 판단할 수 있다. 합치 여부를 판단하는 기준은 에피폴라 제약식에서 계산된 오차 $d(\mathbf{x}\_i', \mathbf{F}, \mathbf{x}\_i)$가 임계값 $\epsilon$ 이하인지 여부이다.

* **합치**: 대응점 쌍이 에피폴라 제약을 만족하고, 오차가 임계값 이하인 경우
* **외란점**: 대응점 쌍이 에피폴라 제약을 위반하고, 오차가 임계값을 초과하는 경우

합치와 외란점을 구분하는 것은 RANSAC 알고리즘의 성능에 큰 영향을 미친다. 너무 작은 임계값을 설정하면, 외란점이 너무 많이 포함될 수 있으며, 너무 큰 임계값을 설정하면 노이즈나 외란점이 합치로 잘못 판단될 수 있다.

#### 7. 모델의 반복 횟수 결정

RANSAC의 성능은 알고리즘이 실행되는 반복 횟수에 크게 좌우된다. 반복 횟수 $N$는 다음과 같은 식으로 결정될 수 있다:

$$
N = \frac{\log(1 - p)}{\log(1 - (1 - e)^s)}
$$

여기서:

* $p$는 성공 확률 (일반적으로 99%로 설정)
* $e$는 외란점(outlier)의 비율
* $s$는 한 번의 반복에서 선택되는 샘플 수 (기본 행렬의 경우 $s = 8$)

이 식을 통해 반복 횟수를 설정함으로써 RANSAC 알고리즘이 외란점이 많은 환경에서도 성공적인 모델을 추정할 수 있다.

#### 8. 최종 모델 선택

RANSAC 알고리즘이 모든 반복을 마친 후, 가장 많은 합치 점을 가지는 모델이 최종 기본 행렬 $\mathbf{F}$로 선택된다. 최종적으로 선택된 $\mathbf{F}$는 외란점에 민감하지 않으며, 전체 데이터에서 가장 많은 대응점 쌍과 일치하는 모델이 된다. 이때 선택된 모델은 이후의 삼각측량이나 3D 복원과 같은 후속 처리에 사용된다.

#### 9. RANSAC 알고리즘의 장단점

**장점**:

* 외란점이 많은 데이터에서도 강력한 성능을 발휘한다.
* 계산 복잡도가 비교적 낮으며, 큰 데이터셋에서도 실시간 적용이 가능한다.

**단점**:

* 외란점 비율이 매우 높을 경우, 반복 횟수가 증가하여 계산 시간이 길어질 수 있다.
* 임계값 설정이 성능에 중요한 영향을 미치므로, 경험적인 조정이 필요할 수 있다.

RANSAC을 이용한 기본 행렬 추정은 외란점이 존재하는 현실적인 상황에서도 안정적인 결과를 제공한다. 이 알고리즘을 통해 추정된 기본 행렬은 스테레오 비전, 다중 뷰 기하학 등 다양한 컴퓨터 비전 문제에 적용될 수 있다.