3장 에지 검출 - RANSAC (Random Sample Consensus)

RANSAC

- 1981년 Fischler&Bolles이 제안 [Fischler81]

- 인라이어를 찾아 어떤 모델을 적합시키는 기법이다.

- 난수 생성하여 인라이어 군집을 찾기 때문에 임의성 지닌다.

인라이어와 아웃라이어가 혼합되어 있는 샘플 집합이 주어진 상황에서 인라이어를 찾아 어떤 모델을 적용시키는 일반적인 기법이다. 이 기법은 무작위로 수를 생성하여 인라이어 군비을 찾아내는 과정을 반복하므로 임의성을 지닌다.

 

선분 검출에 적용

모델은 직선의 방정식 y=ax+b

 

- 이때 에지 화소의 집합이 샘플 집합이 된다

- 모델은 직선의 방정식이 y = ax+b이다.

- RANSAC은 이 모델의 매개변수 a와 b를 추정해 준다.

 

step1. 난수를 생성하여 임의로 두 개의 샘플을 선택한다. (그림에서 점선으로 연결된 빨간색 두 점이 선택된 점이다.)

step2. 직선의 방정식, 기울기 a와 절편 b를 계산한다.

step3. 나머지 샘플들에 대해 이모델에 적합한, 즉 이 직선 상에 있는 점들을 구한다.(약간의 오차 허용하고 매개변수 t로 조절한다.

step4. 이 점들을 인라이어(inlier), 나머지를 아웃라이어(outlier) 이다.

 

한사람이 소득이 얼마 정도인가 추정할 때,

중간에 이재용 회장이 끼어 들면 평균이 말이 안되게 바뀐다. <-- outlier 이재용

이때는 median 소득을 구하는 것이 더 낫다. 

암튼 outlier 제거하는 것이 중요하다.

 

- 위 알고리즘은 구체성이 결여된 곳과 직선 검출이라는 문제의 특수성을 추가로 이용할 여지가 있는 곳이 있다.

- 3행에서 에지 화소를 임의로 선택하고 있는데, 에지 강도와 에지 방향을 추가로 사용한다면 성능을 높일 수 있다.

- 예를들어, 에지 강도가 높은 화소와 에지 방향이 비슷한 화소 쌍이 선택될 가능성을 높이는 방안을 사용할 수 있다.

- 9행에서 inlier의 샘플을 가지고 l을 구한다. 이때 l상에 존재하지 않으므로 적합오차가 발생한다.

- 10행에서 이 적합 오차가 임계값보다 큰 경우 l을 버린다.

- 13행에서 가장 좋은 직선을 최종 선택하는 과정인데, 좋은 정도를 판단하는 기준을 세워야한다. inlier의 크기가 클수록 & 직선 l의 적합 오차가 작을 수록 신뢰도가 높으므로 두 기준을 가지고 좋은 정도를 측정하는 함수를 작성해야한다.

 

 

RANSAC 알고리즘의 특성은 비결정성(non-determinism)이다. 

이전의 다른 알고리즘들은 여러번 실행시켜도 같은 결과가 나오지만

이것은 임의의 두 샘플을 선택하는 과정이 포함되므로 수행할 때마다 다른 결과를 얻는다.

n(반복횟수)를 크게하면 더 좋은 결과를 얻을 가능성이 있다. / 하지만 품질과 속도 사이의 길항 관계를 가진다.

여러개의 직선을 찾고싶으면 inlier에 해당하는 샘플을 제외하고 반복한다.