아밀 2010.03.11 22:11 전체공개

RANSAC(Random Sample Consensus)

RANSAC(Random Sample Consensus)
RANSAC은 Fischler와 Bolles에 의해 1981년에 제안된 강건한 예측방법으로 전체 데이타 중 에서 모델 인수를 결정하는데 필요한 최소의 데이타를 랜덤하게 샘플링하면서 반복적으로 해를 계산함으로써 최적의 해를 찾는다. 이 방법은 전통적인 데이타 스무딩 (smoothing) 기법과는 반대의 개념을 가진다. 즉, 대부분의 방법들이 초기의 해를 획득하기 위해서 가능한 많은 데이타를 사용하고 그 결과로부터 비유효한 데이타를 제거한다. 반면에 이 방법은 가능한 적은 양의 초기
데이타를 사용해서 일관된 데이타의 집합(consensus set)을 확장시켜가는 방식을 사용한다. 그런데 이러한 RANSAC에는 다음과 같은 문제점이 있다.
첫째, 기존의 RANSAC 알고리즘은 확률통계 이론에 기초하여 수렴 시 까지 매번 복원 랜덤 샘플링을 수행 한다. 그러므로 사전에 정확한 이상치의 비율을 알지 못하면 샘플링시에 진동과 같은 문제점이 발생하면서 최적의 해를 결정할 수 없게 된다. 이러한 문제점이 발생 하는 근본적인 원인은 현재시점의 해를 결정할 때 이전 시점에서 결정된 해에 대한 정보를 사용할 수 없다는 것이다. RANSAC-f는 이 문제점을 해결하기 위해서 매 시점마다 최적의 n개의 해에 대한 순서리스트를 유지하 는 방식을 사용한다. 매시점마다 새롭게 해를 결정하는 것이 아니라 각시점마다 유지되는 리스트로부터 최 상의 해를 평균해서 생성되는 새로운 해가 더 최적의 해가 될 수 있는지를 결정한다. 이런 방식을 사용하여 최종적으로 가장 최적의 해를 도출해 낸다. 또 다른 방 법으로는 중요도 샘플링 기법을 RANSAC에 적용한 IMPSAC이 있다. 이 방법에서는 랜덤하게 샘플링을 수행하는 RANSAC과는 달리 중요도가 높은 샘플을 샘 플링함으로써 해의 정확도를 높인다.
둘째, 기존 방법에서는 정상치와 이상치를 분류하기 위해서 하드분할(hard partitioning)을 사용한다. 이것은 데이타에 따라서 정상치와 이상치로 구별하기가 모호한 데이타까지도 어느 한쪽의 집합으로 소속시킴으로써 수렴의 정확도를 감소시키는 문제점이 있다. 그리고 이때 정상치와 이상치를 판단하기 위해 사용하는 임계값 결 정 역시 잔여오차(residual)의 분포가 카이제곱분포를 따른다는 가정을 만족해야 한다. 따라서 본 논문에서는 통계이론을 기반으로 하는 기존의 RANSAC 알고리즘이 수렴 시 까지 매번 복원 랜덤 샘플링을 수행하기 때문에 모집단의 분포에 따라서 민감한 결과를 보이는 문제점을 보완한 퍼지 RANSAC 알고리즘을 제안한다(이후로 퍼지 RANSAC은 FRANSAC으로 칭함). 제안하는 FRANSAC 알고리즘은 기존 방법의 문제점을 해결하기 위해서 매 반복 수행시마다 퍼지분류(fuzzy classification) 기법을 이용하여 전체 데이타를 좋은 샘플집합(good sample set)과 나쁜 샘플 집합(bad sample set) 그리고 모호한 샘플집합(vague sample set)으로 분류한다. 그런 후에 좋은 샘플집합에서만 샘플링을 해나감으로써 이상치에 대한 제거율과 정확도를 향상 시킨다.
그림을 보면
파란색 대각선 주변의 파란 점들을 참을 일종의 inlier로, 주변의 붉은 점을 outlier로 지정한다. 이렇게 inlier을 좋은 샘플집합으로 규정하고 outlier를 제거함으로서 정확도를 향상시킨다.

0

1

댓글1

    댓글 더보기

    삭제 하시겠습니까? 취소 삭제

    로그인 하시겠습니까? 확인 취소

    댓글을 삭제 하시겠습니까? 확인 취소