우리가 고등학교때 배우는 원, 타원, 포물선, 쌍곡선은 모두 conic section이라고 불리는 원뿔곡선 도형들이다.

원뿔곡선(Conic Section)

아이스크림 콘과 같은 원뿔 형태의 도형을 다양한 각도에서 잘 잘라보면 원, 타원, 포물선, 쌍곡선 단면을 얻을 수 있기 때문에 이들 도형을 conic section이라고 부르고 우리말로는 원뿔곡선이라 한다. section은 절단면을 의미한다.

<그림출처: Wikipedia>

콘의 밑면과 수평인 평면으로 자르면 원(circle)이 나오고, 이 평면을 조금 기울여서 자르면 타원(ellipse)이 나온다. 평면을 점점 세워가다보면 원뿔의 측면과 수평이 되는데 이 때의 단면이 포물선(parabola)이다. 그리고 여기서 평면을 더 세우면 쌍곡선(hyperbola)이 된다. 즉, 포물선은 타원과 쌍곡선의 경계에 있는 도형이다.

이심률(eccentricity)

이러한 원뿔곡선 도형들을 구분짓는 파라미터로 이심률(eccentricity)이 있다. 이심률은 원뿔곡선이 원에서 얼마나 동떨어졌느냐를 나타내는 값이다. 한자어로는 離心率 인데 중심에서 이탈한 정도, 또는 중심이 이탈한 정도를 나타내는 말로 풀이될 수 있을 것 같다.

어쨌든, 이심률은 e로 표현하는데 원의 이심률은 e = 0이고, 타원의 이심률은 0<e<1, 포물선의 이심률은 e = 1, 쌍곡선의 이심률은 e>1이다.

<그림출처: Wikipedia>

이심률의 계산은 e = (두 초점 사이의 거리)/(주축과 만나는 양 끝점 사이의 거리)로 계산할 수 있다. 원의 경우 중심(center)과 초점(focus)이 일치하므로 e = 0임을 알 수 있는데, 포물선은 왜 e = 1인 것일까?

초점(focus)

광학쪽에서 보면 초점은 빛이 모이는 점이다. 위 원뿔곡선들도 각각 초점을 가지고 있다. 원과 포물선은 초점이 하나이고 타원, 쌍곡선은 초점이 2개이다.

이러한 원뿔곡선들은 초점과 관련하여 재미있는 특성들을 가지고 있다.

포물선은 주축과 수평으로 들어온 빛들이 모두 초점으로 모이고, 타원은 한 초점에서 쏜 빛이 항상 다른 초점으로 모인다. 또한 쌍곡선은 어느 한 초점을 향해 들어온 빛들이 다른 하나의 초점으로 모인다.

이러한 원뿔곡선의 특징은 실생활에도 많이 활용된다.

전파망원경에 포물선의 원리가 이용된다는 것은 많이들 알고 있을 것이다. 전파원에서 들어오는 신호를 한 점으로 모으기 위해 전파망원경은 포물면을 이용한 접시형태의 반사체를 사용하고 초점 위치에 수신안테나를 설치한다. 반사체(접시)가 큰 경우에는 완벽한 포물면이 아닐 수 있기 때문에 초점 부근에 쌍곡선 면의 반사체를 설치하여 한번 더 신호를 모아준다고 한다.

KVN(한국우주전파관측망) - 그림출처: 한국천문연구원

또한 포물선 원리는 태양열 발전소에서 태양열을 한 점으로 모으기 위한 목적으로도 사용된다. 만일 포물면으로 된 거울을 만들어서 태양을 향하게 하면 돋보기처럼 초점 부근에서 발화가 일어날지도...

<스페인 PS10 태양열 발전소>

영국 런던의 세인트 폴 대성당(성 바오르 대성당)에 있는 속삭이는회랑(whispering gallery)에 가면 한쪽 복도에서 벽에 대고 속삭이면 건너편 복도에서 뚜렷이 잘 들린다고 한다. 이는 속삭이는회랑이 타원형의 둠 형태의 구조를 가지기 때문에 한쪽 초점에서 말한 소리가 사방에 펴졌다가 다른 초점에 모이기 때문이라고 한다.

그런데 타원이 아닌 구 중심에 서서 큰 소리를 내면 어떻게 될까?

원뿔곡선의 도형 방정식과 초점 구하기

원의 방정식은 알고 있지만 막상 도형이 방정식이 무슨 의미인지는 사람들이 잘 모르는 경우가 많다. 좌표계 공간에서 도형이란 어떤 조건을 만족시키는 점 (x, y)들의 집합을 의미하고 이걸 수식으로 나타낸 것이 도형의 방정식이다.

[원]

원은 한 점에서 같은 거리에 있는 점들의 자취(집합)이다. 따라서, 원의 중심을 (a, b), 중심에서의 거리를 r이라 하면 원은

을 만족시키는 점 (x, y)들의 집합이다.

[포물선]

포물선은 한 점과 한 직선에서 같은 거리에 있는 점들의 자취이다. 이 점이 앞서 말한 초점이 되고 직선은 준선이라고 부른다. 예를 들어, 초점이 (p, 0), 준선이 x = -p인 포물선의 방정식은

이며, 이를 정리하면

가 된다.

y = ax²+bx+c 또는 x = ay²+by+c가 포물선의 방정식임은 다 알 것이다. 그렇다면 이 포물선의 초점의 위치는 어디일까? 위 기본식을 이용하면 포물선 꼭지점으로부터 |1/(4a)| 떨어진 곳에 초점이 존재함을 알 수 있다.

[타원과 쌍곡선]

타원은 두 초점으로부터 거리의 합이 일정한 점들의 자취이고, 쌍곡선은 두 초점으로부터 거리의 차가 일정한 점들의 자취이다.

두 초점을 (-p,0), (p,0), 거리의 합을 2a라 하면 타원의 방정식은

가 되고, 이 식을 좀 복잡하긴 하지만 잘 정리해 보면

가 된다. 여기서 우리는 두 초점에서의 거리의 합이 바로 타원의 장축의 길이가 됨을 알 수 있다.

쌍곡선의 경우, 두 초점을 (-p,0), (p,0), 거리의 차를 2a라 하면 쌍곡선의 방정식은

가 되고, 마찬가지로 잘 정리해 보면

가 나온다.

by 다크 프로그래머

고등학교 수학에서 조건부 확률이라는 걸 배운다. 그런데 그게 나중에 가면 베이지안 확률이라는 이름으로 불리면서 사람을 엄청 햇갈리게 한다.

1. 베이즈 정리

베이즈 정리(Bayes's theorem) 또는 베이즈 룰(rule), 베이즈 법칙(law)라고 불리는 이 녀석은 결국 다음과 같은 조건부 확률 계산식이다 (x: 모델, z: 관측).

베이지언 확률은 사후확률(posterior probability)을 사전확률(prior probability)과 likelihood를 이용해서 계산할 수 있도록 해 주는 확률 변환식이다. 베이지안 확률은 영상처리에서 classification 문제, detection 문제가 나오면 거의 빠지지 않고 나오는 약방의 감초같은 존재로서, 사람들이 자신의 방법론에 대해 무언가 수학적 모델이 필요할 경우에 1차적으로 생각하는게 바로 베이지언 확률이다.

☞ likelihood: p(z|x), 어떤 모델에서 해당 데이터(관측값)이 나올 확률

☞ 사전확률(prior probability): p(x), 관측자가 관측을 하기 전에 시스템 또는 모델에 대해 가지고 있는 선험적 확률. 예를 들어, 남여의 구성비를 나타내는 p(남자), p(여자) 등이 사전확률에 해당한다.

☞ 사후확률(posterior probability): p(x|z), 사건이 발생한 후(관측이 진행된 후) 그 사건이 특정 모델에서 발생했을 확률

2. ML와 MAP

확률을 이용해서 classification 문제를 푸는 방법은 크게 2가지가 있다.

바로 ML(Maximum Likelihood) 방법과 MAP(Maximum A Posteriori) 방법이다.

관측값을 z, 그 값이 나온 클래스(또는 모델)를 x라 하자. 예를 들어, 바닥에 떨어진 머리카락의 길이(z)를 보고 그 머리카락이 남자 것인지 여자 것인지 성별(x)을 판단하는  문제를 생각해 보자.

• ML(Maximum Likelihood) 방법: ML 방법은 남자에게서 그러한 머리카락이 나올 확률 p(z|남)과 여자에게서 그러한 머리카락이 나올 확률 p(z|여)을 비교해서 가장 확률이 큰, 즉 likelihood가 가장 큰 클래스(성별)를 선택하는 방법이다.
• MAP(Maximum A Posteriori) 방법: MAP 방법은 z라는 머리카락이 발견되었는데 그것이 남자것일 확률 p(남|z), 그것이 여자것일 확률 p(여|z)를 비교해서 둘 중 큰 값을 갖는 클래스(성별)를 선택하는 방법이다. 즉, 사후확률(posterior prabability)를 최대화시키는 방법으로서 MAP에서 사후확률을 계산할 때 베이즈 정리가 이용된다.

머가 다른 것인지 정말 햇갈린다 (사실 본인도 얼마 전까지는 그랬다).

그런데, ML과 MAP 차이는 남녀의 성비를 고려하면 명확해진다. 만일 인구의 90%가 남자고 여자는 10% 밖에 없다고 하자. ML은 남녀의 성비는 완전히 무시하고 순수하게 남자중에서 해당 길이의 머리카락을 가질 확률, 여자중에서 해당 길이의 머리카락을 가질 확률만을 비교하는 것이다. 반면에 MAP는 각각의 성에서 해당 머리카락이 나올 확률 뿐만 아니라 남녀의 성비까지 고려하여 최종 클래스를 결정하는 방법이다.

MAP로 머리카락이 여자것일 확률을 베이즈 정리를 이용해 구해보면 다음과 같다.

정리하면, ML보다는 MAP 방법이 보다 정확한 classification 방법임을 알 수 있다. 하지만 많은 경우, 사전확률(prior probability)인 p(남), p(여)를 모르는 경우가 대부분이기 때문에 단순하게 p(남) = p(여)로 놓고 문제를 푸는 경우가 많은데, 이 경우 MAP는 ML과 같게 된다.

3. 피부색 검출 예제

베이지안 방법이 영상처리에 사용되는 한 예로 영상에서 피부색을 검출하는 문제를 살펴보자.

영상에서 피부색을 검출하는 문제는 결국, 영상의 각 픽셀이 피부색인지 아닌지 여부를 결정하는 classification 문제로 볼 수 있다.

피부색 검출을 위해서는 먼저 샘플 영상들을 열심히 수집해서 피부색 DB와 일반 색상 DB를 구성해야 한다. DB구성이 끝나면 이제 입력 영상의 각 픽셀값이 피부색인지 여부를 베이지언 방법으로 판단해 보기로 하자. 입력 픽셀값이 z라 하면 p(z|피부색)은 피부색 DB에 있는 데이터들 중에서 z와 같은 색을 가진 데이터의 비율을 세면 된다. 또한 p(z|일반색)은 일반색 DB에 있는 데이터들 중에서 z와 같은 색을 가진 데이터의 비율이다.

만일 ML로 피부색 검출을 한다면 p(z|피부색)과 p(z|일반색)을 비교해서 확률이 큰 값을 선택하면 될 것이다.

그런데, 이 문제를 MAP로 풀면 어떻게 될까? 수집된 DB에 있는 데이터의 개수를 이용하여 p(피부색) = |피부색DB|/(|피부색DB|+|일반색DB|), p(일반색) = |일반색DB|/(|피부색DB|+|일반색DB|)라 놓고 MAP를 적용하면 되는 것일까?

대답은 NO!

p(피부색)은 세상에 존재하는 모든 이미지 색상들 중에서 피부색이 얼마나 되느냐를 나타내는 말이다. 따라서, 자신이 수집한 피부색 DB와 일반색 DB의 크기만을 가지고 이 확률을 추정하는 것은 무리가 있다. 오히려 일반색 DB에 있는 데이터들 중에서 피부색 DB에 있는 색과 같은 색을 갖는 데이터들의 비율을 p(피부색)이라 잡는 것이 보다 합리적일 것이다.

이와 같이 prior 확률 p(x)를 구하는 것은 쉬운 문제가 아니기 때문에 현실적으로는 MAP 대신 ML이 사용되는 경우도 많다.

☞ 이 글은 http://lucypark.tistory.com/59 글에 대한 엮인글(트랙백)로 작성한 글입니다.

☞ 베이지언(Bayesian) 확률에 대한 보다 기본적인 이해를 위해서는 베이지언 확률(Bayesian Probability) 글을 참고하시면 좋습니다.

by 다크 프로그래머

영상처리나 컴퓨터 비전을 하면서 RANSAC을 모르면 간첩일 정도로 RANSAC은 너무나 유명한, 그리고 널리 사용되는 방법이다.

RANSAC이 유명한 만큼 이미 인터넷에 관련된 글들이 꽤 있다. 그럼에도 또 이렇게 RANSAC에 대한 글을 쓰는 건 무언가 다른 플러스 알파(?)가 있기 때문일 것이다. 그 플러스 알파가 무엇인지는 이어지는 글을 살펴보도록 하자 ^^

RANSAC 자체는 특정 분야에 국한되지 않는 일반적인 방법론이다. 하지만 본 블로그가 주로 영상처리에 관련된 주제를 다루기 때문에 영상처리 관점에서 이야기를 풀어가고자 한다.

1. RANSAC의 필요성

2. RANSAC의 이해

3. Inlier와 Outlier

4. RANSAC 알고리즘

5. RANSAC의 활용예

6. RANSAC 알고리즘의 파라미터

7. RANSAC과 robust 파라미터 추정

8. RANSAC에 대한 생각 

1. RANSAC의 필요성

RANSAC의 개념을 설명하기 전에 RANSAC이 왜 필요한지 살펴보겠다. 아래 왼쪽 그림과 같이 관측된 데이터들이 있다고 하자. 이 데이터들을 최소자승법을 이용하여 포물선으로 근사(fitting)시키면 오른쪽 그림과 같은 결과가 나온다. 참고로, 최소자승법이란 모델(여기서는 포물선)과의 ∑residual²을 최소화하도록 모델 파라미터를 정하는 방법을 말한다. 최소자승법에 대한 자세한 내용은 여기를 참조하기 바란다.

그런데, 실제 관측 데이터가 위와 같이 깨끗하게 나오는 경우는 현실 세계에서는 별로 없다. 측정오차나 노이즈(noise) 등으로 인해 아래 왼쪽 그림 같은 경우가 일반적일 것이다. 이때도 최소자승법을 적용하면 오른쪽 그림과 같이 훌륭한 결과를 얻을 수 있다.

그런데, 만일 아래 왼쪽 그림과 같이 약간의 노이즈 정도가 아니라 데이터 자체가 완전히 틀어져 버린 경우는 어떻게 될까? 이렇게 정상적인 분포에서 벗어난, 이상한 데이터들을 이상점(outlier)라고 부르는데, 데이터에 outlier(아웃라이어)가 끼어 있으면 최소자승법은 오른쪽 그림처럼 엉망이 되어 버린다.

그런데, 이것을 RANSAC을 이용해 근사시키면 아래 그림과 같이 깨끗한 결과를 얻을 수 있다.

2. RANSAC의 이해

RANSAC이 왜 필요한지, 그리고 어디에 쓰는 놈인지는 대략 감을 잡았을 것으로 생각한다. 그러면 이제 RANSAC이 무엇인지 좀더 구체적으로 살펴보자.

일단, RANSAC은 영어로 RANdom SAmple Consensus의 대문자들을 딴 약자이다. 글자 그대로 해석해 보면 무작위로 샘플 데이터들을 뽑은 다음에 최대로 컨센서스가 형성된 녀석을 선택한다는 의미이다. 

최소자승법(least square method)은 데이터들과의 ∑residual²을 최소화하도록 모델을 찾지만, RANSAC은 컨센서스가 최대인, 즉 가장 많은 수의 데이터들로부터 지지를 받는 모델을 선택하는 방법이다.

위 포물선 예제에서 최소자승법이 선택한 모델과 RANSAC이 선택한 모델을 비교해 보면 어떤 경우가 좀더 많은 데이터틀로부터 지지를 받는지, 즉 근사된 모델(포물선) 근방에 있는 데이터들이 어느 쪽이 많은지 확인해 보면 된다.

결국, RANSAC과 최소자승법의 차이는 무엇을 기준으로 모델의 파라미터를 찾는가의 차이이다. 이 시점에서 한 가지 짚고 넘어가자. 그건, RANSAC의 기준을 사용하면 관측 데이터에 이상한 애들(outlier)이 많더라도 데이터 근사가 가능하다는 점이다. 그렇지! 하고 고개가 끄떡여지지 않는다면 음... 처음부터 다시 한번 읽어 주시기 바란다..

3. Inlier와 Outlier

RANSAC 알고리즘을 설명하기 전에, 먼저 inlier와 outlier 개념을 정확히 잡고 넘어갔으면 한다. RANSAC과 관련된 여러 미묘한 문제들은 결국 inlier와 outlier의 구분 문제이기 때문이다.

Wikipedia에 보면 Outlier(이상점)는 데이터의 분포에서 현저하게 벗어나 있는 관측값으로 정의되어 있다. 현실 세계에서 관측된 데이터들이 완벽한 경우는 거의 없으며 약간씩의 오차, 편차, 노이즈 등이 있는 경우가 대부분이다. 그렇다면, 오차(에러)가 크면 outlier, 그렇지 않으면 inlier, 이렇게 구분하는 것일까? 대답은 NO! 아니라고 생각한다. 단지 편의상, 또는 별다른 방법이 없기 때문에 그렇게 할 뿐이다.

예를 들어, 일개미들의 특성을 파악하고 싶어서 실험을 했는데 거기에 병정개미의 데이터가 끼어들었다고 하자. 그렇다면 일개미의 데이터는 inlier이고 병정개미의 데이터는 outlier이다. 그런데 일개미의 데이터라 할지라도 조금씩 차이가 있기 때문에 어떤 놈은 편차가 클 것이고 어떤 놈은 편차가 작을 것이다. 그렇더라도 이들은 모두 inlier들이다. 한편, 병정개미 데이터의 경우 어떤 놈은 일개미들과 매우 유사한 값을 가질 수 있다. 하지만 아무리 유사하더라고 그건 여전히 outlier이다.

4. RANSAC 알고리즘

RANSAC 알고리즘은 위에서 설명한 컨센서스가 최대인 모델을 뽑기 위한 절차적 방법을 말한다.

그 방법은 일단 무작위로 샘플 데이터 몇 개를 뽑아서 이 샘플 데이터들을 만족하는 모델 파라미터를 구한다. 이렇게 구한 모델과 가까이에 있는 데이터들의 개수를 세어서 그 개수가 크다면 이 모델을 기억해 둔다. 이러한 과정을 N번 반복한 후 가장 지지하는 데이터의 개수가 많았던 모델을 최종 결과로 반환한다.

이제 위에서 예로 든 포물선 근사 문제를 RANSAC으로 풀어보도록 하자.

관측된 데이터 값들은 (x1, y1), ..., (xn, yn), 포물선의 방정식은 f(x) = ax² + bx + c, 포물선을 결정하기 위해 뽑아야 할 샘플의 개수는 최소 3개이다.

1. c_max = 0 으로 초기화한다.
2. 무작위로 세 점 p1, p2, p3를 뽑는다.
3. 세 점을 지나는 포물선 f(x)를 구한다.
4. 이렇게 구한 f(x)와의 거리 ri = |yi-f(xi)|가 T 이하인 데이터의 개수 c을 구한다.
5. 만일 c가 c_max보다 크다면 현재 f(x)를 저장한다 (과거에 저장된 값은 버린다)
6. 2~5 과정을 N번 반복한 후 최종 저장되어 있는 f(x)를 반환한다.
7. (선택사항) 최종 f(x)를 지지하는 데이터들에 대해 최소자승법을 적용하여 결과를 refine한다.

실제 문제에 따라서, 수식 등은 조금씩 바뀔 수 있지만 기본적인 RANSAC 알고리즘의 구조는 위와 동일하다. 참고로, 위 포물선 예제에 대한 RANSAC matlab 코드는 다음과 같다.

5. RANSAC의 활용예

A. local feature matching을 이용하여 영상에서 특정 물체를 찾을 때

B.Visual Odometry (인접한 영상프레임에서 카메라 모션을 추정할 때)

C. 위치인식을 위해 scene matching을 수행할 때

D. 물체 추적을 위해 인접한 영상프레임에서 이동체의 모션을 추정할 때

6. RANSAC 알고리즘의 파라미터

RANSAC 알고리즘을 돌리기 위해서는 크게 2가지의 파라미터를 결정해야 한다. 샘플링 과정을 몇 번 (N) 반복할 것인지, 그리고 inlier와 outlier의 경계를 (T) 어떻게 정할 것인지이다.

RANSAC이 성공하기 위해서는 N번의 시도 중 적어도 한번은 inlier들에서만 샘플 데이터가 뽑혀야 한다. 이러한 확률은 N을 키우면 키울수록 증가할 것이지만 무한정 RANSAC을 돌릴 수는 없기 때문에 보통은 확률적으로 반복 횟수를 결정한다. RANSAC 반복회수를 N, 한번에 뽑는 샘플 개수를 m, 입력 데이터들 중에서 inlier의 비율을 α라 하면 N번 중 적어도 한번은 inlier에서만 샘플이 뽑힐 확률 p는 다음과 같다.

 --- (1)

예를 들어, 위 포물선 근사 예에서 inlier 비율이 80%라고 했을 때, RANSAC 성공확률을 99.9%로 맞추려면 필요한 반복횟수는 다음과 같이 계산된다.

 --- (2)

수학적 확률이긴 하지만 RANSAC을 10번만 돌려도 99.9% 확률로 해를 찾을 수 있다는 얘기이다. 생각보다 숫자가 작아서 p를 99.99%로 놓고 계산해 봐도 N = 12.8378이 나온다.

이 시점에서 RANSAC의 첫 번째 파라미터 N과 관련된 몇 가지 생각할 질문을 던져본다.

1. 실제로 위 matlab 예제 코드를 돌려보면 N = 100으로 놓고 돌려도 가끔 엉뚱한 해를 찾는다. 수학적 확률은 거의 100%일텐데.. 왜일까?
2. 포물선을 결정하기 위해서는 최소 3개의 점이 필요하다. 하지만 굳이 샘플의 개수를 m = 3으로 맞출 필요가 있을까? 예를 들어, 매 반복에서 샘플을 4개씩 뽑아서 최소자승법으로 포물선을 구할 수도 있을 것이다. 그렇다면 한번에 샘플의 개수를 많이 뽑는게 좋은가 아니면 최소한으로 뽑는게 좋은 것인가? 또한 샘플의 개수에 따라 필요한 반복횟수 N은 어떻게 되는가?
3. RANSAC 반복횟수를 확률적으로 결정하기 위해서는 inlier 비율을 알고 있어야 한다. 그런데, inlier 비율을 모르고 있거나 혹은 입력 데이터마다 inlier 비율이 변할 수 있다면 어떻게 해야 하는가?

RANSAC의 반복회수 N에 대한 내용은 이정도로 하고, 두번째 파라미터인 T에 대해 살펴보자. 사실 N보다는 T가 RANSAC에서 훨씬 중요하고 어려운 파라미터이다.

RANSAC은 지지하는 데이터 개수가 가장 많은 모델을 뽑는 파라미터 추정 방법이다. 지지하는 데이터는 추정된 모델과 가까이 있는 데이터들을 말한다. 그렇다면 얼마나 가까워야 그 모델을 따르는 데이터라고 간주하는 것일까?

RANSAC 알고리즘에서는 데이터 (xi, yi)와 모델 f와의 거리 ri = |yi - f(xi)|가 T 이하이면 그 모델을 지지하는 데이터로 간주한다. 그런데 이 파라미터 T를 우리가 결정해줘야 한다는게 문제이다. 만일 T를 너무 크게하면 모델간의 변별력이 없어지고 T를 너무 작게하면 RANSAC 알고리즘이 불안정해진다.

T를 선택하는 가장 좋은(일반적인) 방법은  inlier들의 residual 분산을 σ2이라 할때, T = 2σ 또는 T = 3σ 정도로 잡는 것이다. 즉, 먼저 RANSAC을 적용하고자 하는 실제 문제에 대해서 inlier들로만 구성된 실험 데이터들을 획득하고, inlier 데이터들에 대해서 최소자승법을 적용하여 가장 잘 근사되는 모델을 구한다. 이렇게 구한 모델과 inlier들과의 residual (ri = yi-f(xi))들을 구한 후, 이들의 분산(또는 표준편차)을 구해서, 이에 비례하게 T를 결정한다. inlier들의 residual이 정규분포를 따른다고 가정했을 때, T = 2σ로 잡으면 97.7%, T = 3σ로 잡으면 99.9%의 inlier들을 포함하게 된다.

T를 정하는데 있어서 정말 어려운 문제는 inlier들의 분산이 동적으로 변하는 경우이다. 이러한 경우에는 T를 데이터마다 유동적으로 결정해주어야 하는데 RANSAC에서는 이러한 문제를 adaptive threshold 또는 adaptive scale 문제라고 부르며, RANSAC에서 주요 연구 이슈중의 하나이다. 참고로, RANSAC에서 adaptive란 용어를 사용하는 경우는 2가지인데, 하나는 N을 adaptive하게 하는 것이고 다른 하나는 T를 adaptive하게 하는 것이다.

7. RANSAC과 robust 파라미터 추정

사실 RANSAC은 robust parameter estimation 방법들 중 하나이다. 어떤 방법 또는 알고리즘이 데이터 중에 outlier가 있어도 처리가 가능하면 이를 robust하다 라고 한다.

Robust한 파라미터 추정(estimation) 방법으로는 RANSAC 외에도, M-estimator, LMedS 등이 있다. 이러한 robust 파라미터 추정 방법들은 Loss 함수에 따라 구분지을 수 있는데, 일단 아래 그림을 살펴보자.

그림출처: Sunglok Choi, "Performance Evaluation of RANSAC Family", BMVC 2009.

우리가 흔히 알고 있는 최소자승법 (Least Square Method)는 그림의 보라색 점선과 같이 Loss 함수가 ρ(r) = r²으로 정의되는 함수이다 (단, ri = yi - f(xi)는 데이터 (xi, yi)의 residual). 반면, RANSAC은 Loss 함수가 위 그림의 초록색 선처럼 residual이 T보다 작으면 0, T보다 크면 1로 정의된다. 즉, RANSAC에서는 residual이 T보다 작으면 에러가 없는 것으로 간주하고, T보다 큰 경우에는 그 크기에 관계없이 모두 1로 간주하는 것이다.

RANSAC을 좀더 개선한 방법으로 MLESAC(Maximum Likelhood SAC)이라는 것이 있다. RANSAC은 T 이내에만 들어오면 에러가 없는 것으로 치기 때문에 Gaussian이나 정규분포처럼 T 내에서도 모델에 가까울수록 데이터들이 좀더 밀집되는 형태는 잘 반영하지 못한다. 하지만, MLESAC에서는 위 붉은색 선처럼 데이터가 모델에 가까울수록 에러를 적게 줌으로써, 데이터들이 가장 밀집된 곳을 찾을 수 있도록 해 준다.

LMedS(Least Median of Squares)는 RANSAC 계열과는 조금 다른 방법으로 robust하게 모델을 추정하는 방법이다. LMedS에서는 residual들의 median (residual들을 순서대로 정렬했을 때 순서상 가운데에 있는 값)이 최소화되는 모델을 찾는다. 단, LMedS는 outlier 비율이 50% 이하일 경우에만 적용할 수 있는 방법이다.

8. RANSAC에 대한 생각 

RANSAC은 데이터에 포함된 outlier 비율에 관계없이 적용할 수 있는 매우 강력하면서도 효과적인 파라미터 추정 방법이지만 random성으로 인한 몇몇 문제점을 가진다.

1. 동일한 입력 데이터에 대해서도 RANSAC 결과가 매번 달라질 수 있다.
2. 아무리 N을 늘려도 해를 못찻을 수 있다. 수학적 확률은 수학적 확률일 뿐이다.
3. outlier들이 random하게 분포되어 있지 않고 structure를 갖는다면 outlier들의 분포를 근사해 버릴 수도 있다.
4. 몇개 샘플만으로 모델을 구하는 방식은 문제에 따라 위험할 수도 있다. 위 포물선 예에서 점 3개를 뽑으면 포물선이 결정된다. 하지만 3 점이 모두 inlier라 할지라도 점 자체에 약간씩의 오차가 포함되어 있기 때문에 결과적으로 여기서 계산된 포물선도 오차를 갖게 된다. 그런데, 이 점들이 서로 인접해 있다면 이 오차가 매우 커질수 있다. 포물선의 한쪽 면에서 뽑힌 인접한 점 3개만 보고 포물선이 어디에서 꺾일지 알 수 있는지 생각해 보기 바란다.

RANSAC을 사용하면서 RANSAC의 장점 뿐만 아니라 이와 같은 한계도 같이 고려하면서 사용한다면 RANSAC을 좀더 잘 사용할 수 있을 것이다.

☞ 이상으로 RANSAC에 대한 정리를 마칩니다. 글 첫머리에 말씀드린 플러스 알파는 글을 충실하게 써 보자는 나름의 다짐, 또는 낚시성(?) 멘트 정도로 해석해 주시면 감사하겠습니다 ^^

by 다크 프로그래머