'Robust Estimation'에 해당되는 글 2건

  1. 2008.07.08 Robust Line Fitting
  2. 2008.05.24 RANSAC Algorithm

이미지에서 관찰된 점들이 {(xi, yi) | i = 1, 2,..., N}이 있다. 이 점들을 직선 y = a + b*x 로 피팅을 하고 싶을 때, 보통 최소 자승법을 이용하는 데,  원리는 직선의 방정식이 예측한 y값과 실제 관찰한 y값의 차이의 제곱(=square deviation)을 최소화시키는 직선의 파라미터 a, b를 찾는 것과 동일하다:


확률적으로는, 데이터를 얻는 과정인 측정에서 측정값 yi 는 랜덤에러를 가지게 되고, 이 에러는 참값 y(x) 근방에서 정규분포의 모양을 가지게 된다고 가정을 한다. 만약에 모든 측정의 에러가 동일한 표준편차 σ를 갖게 된다면, N개의 관측데이터가 나타날 확률(likelihood)는 (개별측정은 IID조건을 만족한다고 전제)
     

의 형태가 된다. 따라서 최소자승방법은 이 likelihood를 최대화시키는 파라미터를 찾는 방법이 된다. 이 최소 자승법은 피팅 파라미터를 주어진 데이터를 이용해서 표현할 수 있는 장점이 있지만, outliers에 대해서 매우 취약하다 (아래의 결과 그림을 참조). 이것은 적은 수의 outlier도 χ2 에 큰 기여를 할 수 있기 때문이다. 따라서 피팅을 좀더 robust하게 만들기 위해서는 이들 outlier들이 likelihood에 기여하는 정도를 줄여야 한다. 그러기 위해서는 likelihood의 지수인자가 큰 에러에서 덜 민감하게 반응하는 꼴로 바뀌어야 한다. 이런 형태 중에서 가장 간단한 것 중의 하나가 square deviation 대신에 absolute deviation을 이용하는 것이다:


그러나 이 식을 이용하는 경우에는 최소자승법과는 달리, 파라미터 a, b를 주어진 데이터 {(xi, yi)}로 표현할 수 없고, 반복적인 방법을 이용해서 찾는 수 밖에 없다. 


주어진 수열 {c
i}와 a 와의 차이의 절대값의 합
i |ci - a| 는 a가 이 수열의 median 값인 경우에 최소된다는 사실을 이용하면 (증명: 극값을 구하기 위해서 a에 대해서 미분하면, 0 = (i 1) - (i 1) : 합은 a가 ci 보다 큰 경우와 작은 경우로 분리=> 따라서 0이 되기 위해서는 작은 경우와 큰 경우의 수가 같아야 한다 => 즉, a = median{ci}), 고정된 b값에 대해서 위 absolute deviation을 최소화 시키는 a값은

 


임을 알 수 있다. 그리고 absolute deviation 식을 b에 대해서 미분을 하여서


을 얻는데 위의 a 값을 대입해서 위의 식을 만족시키는 b값을 bracketing and bisection 방법을 이용해서 얻을 수 있다(불연속함수여서, 일반적으로 근을 구하는 방법을 사용하는 것은 위험하다). 아래의 코드는 이를 구현한 것이다.


참고 : Numerical Recipes. 

// qsort-comparator; 

static int comp(const void *a, const void * b) { 

    double d = *((double *)a) - *((double *)b);

    return d > 0 ? 1 : d < 0 ? -1 : 0; 

// 기울기(bb)가 주어진 경우에 y-절편(median = aa)값을 추정하고, 이 때 AD값을 얻는다. 

double RhoFunc(double *x, double* y, int n, 

               double bb, double *aa, double *abdev) { 

    double *h = new double [n];

    for (int i = 0; i < n; i++)  h[i] = y[i] - bb * x[i];

    qsort(h, n, sizeof(double), comp); 

    // median; 

    *aa = (n & 1) ? h[n / 2] : (h[n / 2] + h[n / 2 - 1]) / 2;

    

    double sum = 0;  

    *abdev = 0; 

    for (i = 0; i < n; i++) { 

        double d = y[i] - (bb * x[i] + (*aa)); 

        *abdev += fabs(d); 

        // sign-함수의 원점에서 모호함을 없애기 위해서 증폭을 시킴; 

        if (y[i] != 0.) d /= fabs(y[i]);

        if (fabs(d) > DBL_EPSILON) // sign 함수의 모호함에서 벗어나면,

            sum += (d >= 0 ? x[i] : -x[i]); 

    } 

    delete [] h;

    return sum; // return sum{xi * sign(yi - (b * xi + a))} 

}; 

// 최소자승법을 이용한 라인추정: 

// return (sigma[dy] / sigma[x]);

double FitLine_LS(double *x, double *y, int n, double *a, double *b) { 

    double sx = 0, sy = 0, sxx = 0, sxy = 0; 

    for (int i = 0; i < n; i++) { 

        sx += x[i]; 

        sy += y[i]; 

        sxx += x[i] * x[i] ; 

        sxy += x[i] * y[i] ; 

    }; 

    double det = n * sxx - sx * sx; 

    if (det == 0.) return -1;                   // vertical line;

    *a = (sxx * sy - sx * sxy) / det; 

    *b = (n * sxy - sx * sy) / det;  

    double chi2 = 0;  

    for (i = 0; i < n; i++) { 

        double t = y[i] - (*a + *b * x[i]); 

        chi2 += t * t; 

    }  

    det /= n; // det -> var(x) * n; 

    // chi2 = var(dy) * n;

    // (dy vs x의 편차비)

    return  sqrt(chi2 / det);  ; 

}

// y = a + b * x ; 

// Least Absolute Deviation: 

void FitLine_MAD (double *x, double *y, int n, 

                  double *a, double *b, double *mad) 

    // least square esimates for (aa, bb);      

    double aa, bb; 

    double sigb = FitLine_LS(x, y, n, &aa, &bb); 

    double b1 = bb; 

    double abdev; 

    double f1 = RhoFunc(x, y, n, b1, &aa, &abdev); 

    /* bracket 3-sigma away in the downhill direction; */ 

    double b2 = fabs(3 * sigb); 

    b2 = bb + (f1 < 0 ? -b2 : b2); 

    double f2 = RhoFunc(x, y, n, b2, &aa, &abdev); 

    

    // if conditional added to take care of the case of a

    // line input into this function. It is needed to avoid an

    // infinite loop when (b1 == b2) (within floating point error)

    if (fabs(b2 - b1) > (sigb + 0.005)) { 

        // bracketing;

        while ((f1 * f2) > 0) { 

            bb = 2 * b2 - b1; 

            b1 = b2;

            b2 = bb;

            f1 = f2;  

            f2 = RhoFunc(x, y, n, b2, &aa, &abdev) ; 

        } 

    } 

    // refine until the error is a negligible number of std; 

    sigb *= 0.01; 

    while (fabs(b2 - b1)> sigb) { 

        // bisection; 

        bb = (b1 + b2) / 2.; 

        if ((bb == b1) || (bb == b2)) break ; 

        double f = RhoFunc(x, y, n, bb, &aa, &abdev) ; 

        if ((f * f1) >= 0) { 

            f1 = f; 

            b1 = bb; 

        } 

        else { 

            f2 = f; 

            b2 = bb; 

        } 

    } 

    *a = aa; 

    *b = bb; 

    *mad = abdev / n; 

}

// 붉은 선--> 최소자승법에 의한 피팅.: outlier에 매우 취약한 구조.
// 파란 선--> least absolute deviation을 이용한 피팅: outlier에 매우 robust하다.

"사용자

'Image Recognition' 카테고리의 다른 글

RANSAC : Circle Fit  (0) 2008.07.21
KMeans Algorithm  (0) 2008.07.19
Robust Line Fitting  (0) 2008.07.08
Bayesian Spam Filtering  (0) 2008.07.03
EM : Binarization  (0) 2008.07.01
EM Algorithm : Line Fitting 예  (0) 2008.06.29
Posted by helloktk

댓글을 달아 주세요

RANSAC Algorithm

Image Recognition 2008. 5. 24. 09:02

어떤 현상을 설명하는 이론 모델을 만들고자 하면 현상에서 관측데이터를 모아야한다. 그런데 관측 데이터에는 모델에 대한 잘못된 가정이나 측정장비의 오차등에서 생기는 여러가지 형태의 노이즈가 들어있게 마련이다. 이러한 노이즈는 모델을 정확히 예측하는 것을 방해한다. 이처럼 모델파라미터의 예측을 방해하는 데이터(outliner)가 들어 있는 관측데이터로부터 어떻게 하면 모델을 구축할 수 있는가라는 질문에 대한 한 대답을 RANSAC ("RANdom SAmple Consensus")  알고리즘이 제공한다. 이 알고리즘은 1981년 Fischler 과Bolles에 의해서 제안되었다.

RANSAC 알고리즘에 들어가는 입력은 관측된 데이터값과, 관측결과를 피팅하거나 설명할 수 있는 모델파라미터, 그리고 신뢰성을 나타내는 파라미터를 필요로 한다.

RANSAC알고리즘은 주어진 원본데이터에서 반복적으로 일부를 임의로 선택하는 과정을 반복하여서 최적의 파라미터를 예측하는 프로시져의 형태를 가진다. 전체의 관측데이터가 M개 있고, 모델파라미터를 예측하는데 N개의 데이터가 필요한 경우에, 알고리즘은 :

     1. 임의로 관측데이터에서 N개의 서브데이터를 선택한다.
     2. 이 데이터를 (가상의) inlier로 생각하고 모델을 예측한다.
     3. 원본데이터중에서 예측된 모델에 잘 맞는가를 체크한다. 잘 맞는 데이터 수를 K라고 한다.
     4. 만약에 K가 충분하면, 이 모델을 확정하고 알고리즘을 종료한다.
     5. 모델이 좋지 않으면 1-->4과정을  L 번  반복한다.
     6. 충분히 반복후에도 좋은 모델을 찾지 못하면 모델예측에 실패한 것으로 간주한다.

1. 임계값 K 는 모델이 얼마나 잘 맞는가에 대한 사용자입력으로부터 결정이 된다. 그러나 대략적으로 주어진 샘플에서 inlier의 비율 Pg 이라고 생각되는 정도를 잡으면 된다 :
 
   K = M * (1- P
g)

2. 얼마나 많은 반복을 해야하는가? 주어진 관측데이터에서 inlier일 확률이 Pg인 경우에 L번의 모델예측시도가 실패할 확률을 계산하여서 이것이 주어진 설정값, pfail 보다도 작은 경우에 모델예측의 실패로 처리하므로,

  pfail   = L번의 모델예측 실패확률
          = (한번 시도가 실패할 확률)L
          = (1 - 한번 시도가 성공할 확률))L
          = (1 - (랜덤데이터가 모델을 예측할 확률)N))L
          = (1- (Pg) N)L

이 사실로 부터 최대 반복횟수는 
    
   L = log(pfail)/log(1-(Pg)N)

로 주어진다.
inlier가 반이 섞인 경우 Pg (=주어진 데이터중에서 inlier일 확률)
= 0.5,
p
fail = 0.01 인 경우, 만약에, N = 3 (세 점만 있으면 모델구성이 가능한 원의 피팅이 한 예임) 일 때, 최대 반복횟수는 윗 식에 적용하면,
     
                   L = 35 회


RANSAC알고리즘은 주어진 관측데이터에 많은 outlier가 존재하더라도 매우 정확히 모델파라미터를 예측할 수 있는 능력이 있는 robust한 알고리즘이지만, 얼마나 많은 반복을 해야하는가에 대한 상한값이 제공되지 않는다(사용자가 pfail 를 설정한다). 따라서 사용자 설정에 의한 상한값은 최적의 모델이 아닐 수 있다.

"The RANSAC procedure is opposite to that of conventional smoothing techniques: Rather than using as much of the data as possible to obtain an initial solution and then attempting to eliminate the invalid data points, RANSAC uses as small an initial data set as feasible and enlarges this set with consistent data when possible".

Martin A. Fischler and Robert C. Bolles (June 1981). "Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography". Comm. of the ACM 24: 381–395.

예제코드:
ransac을 이용한 라인 피팅: http://blog.naver.com/helloktk/80029006029
ransac을 이용한 원 피팅: http://kipl.tistory.com/32

'Image Recognition' 카테고리의 다른 글

Gaussian Mixture Model  (2) 2008.06.07
Rasterizing Voronoi Diagram  (0) 2008.05.26
RANSAC Algorithm  (0) 2008.05.24
Contour Tracing  (0) 2008.05.22
Gausssian Scale Space  (0) 2008.05.22
Watershed Algorithm 적용의 예  (2) 2008.05.21
Posted by helloktk

댓글을 달아 주세요