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