RANSAC(RANdom SAmple Consensus)을 이용한 Line Fitting Example

http://blog.daum.net/pg365/62

지금까지 로봇 분야에서 일해오면서 RANSAC이라는 말은 여러 번 들은것 같은데, 제대로 파악을 못하고 있다가 SIFT 알고리즘을 분석하면서 자세히 알게되었습니다. 그래서 여기에 간단한 예제와 함께 소개하도록 하겠습니다.

 

기본개념:

RANSAC ("RANdom SAmple Consensus") 알고리즘은 측정 노이즈가 심한 원본 데이터로부터 모델 파라미터를 예측하는 방법으로Fischler 과Bolles에 의해서 제안되었다.

RANSAC은 전체 원본 데이터 중에서 모델 파라미터를 결정하는데 필요한 최소의 데이터를 랜덤하게 샘플링하면서 반복적으로 해를 계산함으로써 최적의 해를 찾는다. 이 방법은 전통적인 통계적 방법과는 반대의 개념을 가진다. 즉, 대부분의 방법들이 초기의 해를 획득하기 위해서 가능한 많은 데이터를 사용하고 그 결과로부터 유효하지 않은 데이터를 제거한다. 반면에 이 방법은 가능한 적은 양의 초기 데이터를 사용해서 일관된 데이터의 집합(consensus set)을 확장시켜가는 방식을 사용한다.

 

내용:

수식들 때문에 블로그로 적기 어려운 점이 있습니다. 정리한 내용을 pdf로 첨부합니다. 그리고 VS2008로 컴파일 가능한 소스코드도 첨부합니다.

 

 RANSAC.pdf

 

 RANSAC_LineFitting.zip

 

 

 

2011.6.24 RANSAC 알고리즘에서 샘플을 취하는 방식을 수정하였습니다. 모집합에서 무작위로 샘플을 취하게 되면 중복되는 샘플이 선택될 수 있습니다. 수정된 소스에서는 중복된 샘플이 선택되지 않도록 검사하는 코드가 추가되었습니다.

---

좋은 설명 자료 감사합니다. 
소스를 분석하면서 한가지 궁금한 점이 있어서 글을 남깁니다.
distance_threadhold 값은 어떤 기준으로 설정하신건지 궁금합니다.

---

모델이 되는 직선으로부터 한 점이 떨어진 거리의 threshold 값을 결정합니다. 이 threshold 값 안에 들어오면 점은 inlier가 되고 threshold 값을 벗어나면 outlier가 됩니다. inlier가 된 점들은 직선 모델을 새로 계산하는데 포함이 됩니다. 

threshold 값이 크면 노이즈가 모델에 많이 포함될 수가 있습니다. 반대로 threshold 값이 작으면 올바른 데이터가 모델을 계산하는데서 제외됩니다. 그러니까 데이터의 표준편차 값과 threshold 값이 비례한다고 보면 될것같습니다.

---

데이터 값들이 어떤 특징점을 중심으로 모여 있을 때 outlier 값을 필터링 하려고 하는데요.

직선 모델을 이용해서 필터링을 하면 outlier 값이 inlier 그룹으로 부터 멀리 떨어져 있어도
inlier값에 계산된 직선과의 거리가 임계치 안에 있을때는 필터링이 안되는 현상이 발생하는데,

혹시 RANSAC 을 이용해서 데이터 그룹과 동떨어진 곳에 있는 outlier 값을 추출할 수 있는
다른 방법이 있는지 알고 싶습니다.

---

특징점을 중심으로 모여있다면, 직선 모델을 사용하는 대신 점 모델을 사용하면 될 것같습니다. RANSAC은 정형화된 수행 절차이기 때문에 다양한 모델을 사용할 수 있습니다. 점, 직선, 원, 포물선, 사인곡선 등등... 시간이 되면 점 모델을 사용한 랜섹을 올려보겠습니다. 감사합니다.

---

소스 분석중에 질문 드립니다.

직선을 그리기 위한 점들은 sline에 저장 되어 있는 건가요?..

sline의 점들을 이어주면 되는건지 모르겠습니다.

---

예, sline에 저장되어있습니다. 하지만 (mx, my)와 (sx, sy)가 선분의 두 끝점은 아닙니다. 다음 소스코드를 참고하시기 바랍니다.

    if (100. < cost) {
        pDC->MoveTo((int)(line.sx-500*line.mx), (int)(line.sy-500*line.my));
        pDC->LineTo((int)(line.sx+500*line.mx), (int)(line.sy+500*line.my));
    }

---