Random sample consensus (RANSAC)

 RANSAC(Random Sample Consensus)은 노이즈가 있는 데이터에서 원하는 데이터의 수학적 모델을 뽑기 위한 반복적 방법이다. RANSAC은 일정한 확률로 적절한 결과를 생성할 수 있고, 반복 횟수(Iteration)를 증가할수록 위 확률이 증가한다는 점에서 비 결정적 알고리즘(non-deterministic algorithm)으로 볼 수 있다.

 RANSAC 알고리즘은 다음의 두 단계의 반복으로 구성된다.

1. 초기 데이터 집합에서 임의로 서브 데이터 집합을 선택한다. 선택한 서브 데이터 집합에 맞는 모델 및 모델 파라미터를 계산한다. 이 때 서브 데이터 집합의 데이터 수는 모델 및 모델 파라미터를 계산하기 위해 필요한 최소한의 데이터 수 보다는 많아야 한다.

2. 위 방법으로 산출된 모델 파라미터가 전체 데이터들과 얼마나 일치하는지 검사한다. 이 때 데이터가 피팅 모델과 일치하지 않으면 노이즈(outlier) 간주하고 피팅 모델과 일치하면 유효한 데이터로 간주한다.

피팅 모델에서 얻어진 유효한 데이터들의 집합을 콘센선스 집합(consensus set)이라고 한다. RANSAC알고리즘은 충분히 많은 유효한 데이터를 갖는 콘센선스 집합을 얻을 때 까지 위의 두 가지 순서를 반복한다.

이차원 데이터들의 집합 중 데이터들을 가장 잘 나타내는 라인 모델을 만드는 예시를 보자. 이 데이터들은 유효한 데이터(inlier)와 노이즈(outlier)를 모두 포함한다고 가정한다.

<그림 1> 2차원 상의 데이터

리스트 스퀘어(least square) 같은 간단한 방법을 이용하여 라인 모델을 만들 수 있지만 노이즈가 포함된 데이터 에서는 좋은 모델을 만들기 어렵다. 반면 RANSCAN 알고리즘은 모델을 선택할 때 올바른 파라미터를 설정한다면 높은 확률로 좋은 모델을 생성할 수 있다는 장점이 있다.

<그림 2> RANSAC을 이용한 라인 피팅