타원은 원뿔을 평면으로 잘랐을 때 생기는 곡선 중의 하나로 다음 이차 형식(quadratic form)으로 표현된다.

$$\text{conic eq: }   ax^2 + bxy + cy^2 +d x+ ey + f=0$$.

이차 형식의 계수를 구하기 위해서는 타원 위의 서로 다른 5개의 점이 필요하다 (타원이기 위해서는 $b^2 - 4a c < 0$). 주어진 5개의 평면상의 점 $\{(x_i, y_i)|i=1,2,..,5\}$가 결정하는 타원은

\begin{gather}  ax_1^2 + bx_1 y_1 + c y_1^2 + d x_1 +e y_1 + f =0 \\  ax_2^2 + bx_2 y_2 + c y_2^2 + d x_2 +e y_2 + f =0 \\  ax_3^2 + bx_3 y_3 + c y_3^2 + d x_3 +e y_3 + f =0 \\ ax_4^2 + bx_4 y_4 + c y_4^2 + d x_4 +e y_4 + f =0 \\ ax_5^2 + bx_5 y_5 + c y_5^2 + d x_5 +e y_5 + f =0 \end{gather}

이를 만족시키는 해는 다음 행렬식으로 쓰인 방정식의 해와 같다:

$$ \begin{pmatrix}x_1^ 2& x_1 y_1 & y_1 ^2 & x_1 & y_1 & 1\\x_2^ 2& x_2 y_2 & y_2 ^2 & x_2 & y_2 & 1\\ x_3^ 2& x_3 y_3 & y_3 ^2 & x_3 & y_3 & 1\\ x_4^ 2& x_4 y_4 & y_4 ^2 & x_4 & y_4 & 1\\ x_5^ 2& x_5 y_5 & y_5 ^2 & x_5 & y_5 & 1   \end{pmatrix} \begin{pmatrix} a\\b\\c\\d\\e\\f  \end{pmatrix}=0 $$

또는 간단히

$$ \mathbf{A}.\mathbf{x} =\mathbf{0}$$

의 형태로 쓰여진다. 6개의 conic-parameters를 결정해야 하므로, $\mathbf{A}$는 마지막 행을 0으로 채워서 $6\times6$ 행렬로 만들어서 사용한다.  이 경우 $\mathbf{A}_{6\times 6}$는 determinant가 0인 singular 행렬이 되고 적어도 null 공간의 차원은 1 이상이다(1인 경우만 의미있는 해를 준다). $\mathbf{A}$의 singular value decomposition(SVD)을 이용하면위 방정식의 nontrivial한 해를 얻을 수 있다. SVD에 의해 $\mathbf{A}$는 다음처럼 쓸 수 있다( singular value 중 1개가 0인 경우). 

$$\mathbf{A}= \mathbf{U}. \text{diag}(w_0,w_1, w_2, w_3, w_4, 0).\mathbf{V}^T= \mathbf{U}.\begin{pmatrix}  w_0 \mathbf{v}_0^T \\ w_1 \mathbf{v}_1^T\\  w_2 \mathbf{v}_2^T\\ w_3 \mathbf{v}_3^T\\ w_4 \mathbf{v}_4^T\\ 0\end{pmatrix}. $$ 

행렬 $\mathbf{V}$의 각 열벡터 $\{\mathbf{v}_i\}$는 6차원 벡터 공간의 기저를 형성한다. 그리고 $\mathbf{U}$는 orthogonal 행렬이므로 오른쪽에서 곱해지는 벡터의 크기를 변화시키지 않고 단지 회전만 시킨다. singular value가 $0$에 해당하는 $\mathbf{V}$의 열벡터 $\mathbf{v}_5$를 대입하면

$$ \mathbf{A} \cdot \mathbf{v}_5    =   \mathbf{U}. (0,0,0,0,0)^T  = 0$$

이어서 $\mathbf{A}.\mathbf{x}=0$의 nontrivial solution이 됨을 알 수 있다. 물론 singular value가 0인 경우가 여럿이 생기면 해당하는 열벡터의 선형결합도 해가 되므로 원하는 답이 아니다. 이 경우는 주어진 5개의 점들의 일부가 일직선상에 있는 경우에 해당한다(또는 겹치는 경우). 이때는 다시 5개의 점을 선택해야 한다.

 

// 주어진 점에서 타원까지의 대수적 거리: conic-eq의 좌변의 값;

static double fitting_error(double conic_params[6], double x, double y);

더보기
static double fitting_error(CfPt q, double conic_params[6]) {
     double x = q.x, y = q.y;
     return conic_params[0] * x * x +
            conic_params[1] * x * y +
            conic_params[2] * y * y +
            conic_params[3] * x + 
            conic_params[4] * y + 
            conic_params[5];
}

//

static int ransac_sample_number(int ndata, int ngood, double prob, int ntry);

더보기
static int ransac_sample_number(int ndata, int ngood, double prob, int ntry) {     
      if (ndata == ngood) return 1;
      return (int)(log(1. - prob)/log(1. - pow((double)ngood/ndata, ntry)));
}
int ransac_ellipse_fitter(std::vector<CPoint>& points, int width, int height,
                          double ellipse_params[5],/*(a, b, cx, cy, theta)*/
                          std::vector<int> &best_index) {
    if (points.size() < 5) return 0;
    // 안정적인 conic fitting을 위해서 데이터를 (-1,1)구간으로 normalize함;
    std::vector<CfPt> nor_pts(points.size());
    double ellipse_scale; //원점에서  타원점들까지의 평균거리;
    CfPt ellipse_center;  //타원의 중심 예측;
    normalize_points(points, nor_pts, &ellipse_scale, &ellipse_center);
    //
    best_index.resize(nor_pts.size());
    // inverse_scale을 기준으로 만들어졌음;
    const double dist_threshold = sqrt(3.84) / ellipse_scale;
    double best_params[5];
#define MAX_ITERATION (1500)
    int sample_num = 1000; //number of sample
    int ransac_iter = 0;
    int max_inliers = 0;
    while (sample_num > ransac_iter) {
        int rand_idx[5];
        // 5개 점을 랜덤하게 선택;
        random_quintet((nor_pts.size() - 1), rand_idx);
        // 5개 점을 이용해서 conic parameter estimate;
        double conic_params[6];
        get_conic_params(nor_pts, rand_idx, conic_params);
        // conic parameter를 이용해서 inlier 후보들을 모음;
        std::vector<int> inliers; // inlier index을 저장;
        for (int i = nor_pts.size(); i-->0;) {
            double error = fitting_error(nor_pts[i], conic_params);
            if (fabs(error) < dist_threshold) inliers.push_back(i);
        }
        if (inliers.size() > max_inliers) {
            if (conic_to_ellipse(conic_params, ellipse_params)) {
                get_real_params(ellipse_params, ellipse_scale, ellipse_center, ellipse_params);
                // 주어진 영역안의 정상적인 타원만 선택함;
                if (regular_ellipse(ellipse_params, width, height, 0.5, 2.0)) {
                    max_inliers = inliers.size();
                    //이 단계에서 inliers를 이용해서 다시 타원을 예측한다;
                    //if (inliers.size() >= 6) { 
                    //   std::vector<CfPt> pts(inliers.size());
                    //   for (int i = inliers.size(); i-->0;) pts[i] = nor_pts[inliers[i]];
                    //   EllipseFit(pts, conic_params);
                    //   conic_to_ellipse(conic_params, ellipse_params);
                    //   get_real_params(ellipse_params, ellipse_scale, ellipse_center, ellipse_params);
                    //}
                    for (int i = 0; i < 5; i++) best_params[i] = ellipse_params[i];
                    for (int i = inliers.size(); i-->0;) best_index[i] = inliers[i];
                    sample_num = ransac_sample_number(nor_pts.size(), inliers.size(), 0.99, 5);
                }
            }
        }
        ransac_iter++;
        if (ransac_iter > MAX_ITERATION) {
            TRACE("Error! ransac_iter exceeds!\n");
            max_inliers = 0;
            break ;
        }
    }
    if (best_params[0] > 0 && best_params[1] > 0)
        for (int i = 0; i < 5; i++) ellipse_params[i] = best_params[i];
    else
        max_inliers = 0;
    best_index.resize(max_inliers); 
    return best_index.size();
}

 
 
 
 
 
728x90
Posted by helloktk
,

RANSAC 알고리즘을 써서 주어진 2차원 점집합에서 원을 추정한다. 원을 만들기 위해서는 최소한 3점이 필요하고, 또 일직선에 있지 않아야 한다. 이렇게 만들어진 원은 세 점을 꼭짓점으로 하는 삼각형의 외접원이다. 주어진 외접원에서 크게 벗어나지 않는 inliers를 찾고, 이 inliers에 대해 최소자승법으로 원의 중심과 반지름을 다시 추정한다. 무작위로 선택된 세 점에 대해 위의 과정을 반복 시행해서 구한 원 중에서 inliers의 벗어남 편차가 최소인 것을 결과로 선택한다.
// 참고: http://en.wikipedia.org/wiki/RANSAC 
//

 

// [0, max_num) 사이에서 3개의 숫자를 무작위로 선택함;
void GetRandomTriplet(int max_num, int triplet [3]);

// 세 점의 외접원을 구함;
int CircumCircle(double tx[3], double ty[3], double cparams[4]) ;

// 3x3 선형 방정식을 푼다: A * x = b;
bool SolveLinearEQ3x3(double A [9], double bb [3], double x [3]) ;

// x^2 + y^2 + A*x + B*y + C = 0;
// Least square fit for A, B, C;(참조: kipl.tistory.com/207)
int CircleFit_LS(std::vector<double>& xp, std::vector<double>& yp, double cparams[4]) ; 

// 주어진 원에서 임계 거리 이내의 데이터만 골라냄;

double findInlier(std::vector<double>& xp, std::vector<double>& yp,
                double cparams[4], double dist_th,
                std::vector<double>& inlierx, std::vector<double>& inliery) {
    inlierx.clear(); inliery.clear();    
    double var = 0;           // variance of distance deviation;
    double cx = cparams[0], cy = cparams[1], rad = cparams[2];
    for (int k = xp.size(); k-->0;) {
        double dist = sqrt(SQR(xp[k] - cx) + SQR(yp[k] - cy));
        double distdeviate = fabs(dist - rad) / rad ;
        if (distdeviate <= dist_th) {  //collect maybe_inliers;
            inlierx.push_back(xp[k]);
            inliery.push_back(yp[k]);
            var += SQR(dist - rad);
        }
    }
    return sqrt(var / inlierx.size());
}

 

 

int RansacCircleFit(std::vector<double>& xp, std::vector<double>& yp,
                    int sample_th,      // # of inliers; >= 50% of data(N), 66%; 
                    double dist_th,     // 25% of radius;   |dist-rad|/rad< dist_th
                    int max_iter,
                    double cparams[4]) {    
    double pr = double(sample_th) / double(xp.size());
    double trials99 = log(1. - 0.99)/log(1. - pow(pr, 3));
    int iter = min(max_iter, trials99);
    int found = 0;   
    double min_dev = 1.e+10, sdev;
    if (sample_th < 3) sample_th = 3;
    while (iter--) { 
        int tri[3]; 
        double tx[3], ty[3];
        GetRandomTriplet(xp.size(), tri);
        for (int i = 0; i < 3; i++) {
            tx[i] = xp[tri[i]]; ty[i] = yp[tri[i]];
        }
        double cx, cy, rad;
        if (!CircumCircle(tx, ty, cparams)  
            // if three points are degenerate or on a line, discard them!
            continue ;
        std::vector<double> consensusx, consensusy;
        sdev = findInlier(xp, yp, cparams, dist_th, consensusx, consensusy);
        if (consensusx.size() >= sample_th) {          
            // estimate model params using the maybe-inliers;
            if (!CircleFit_LS(consensusx, consensusy, cparams)) 
                continue; // least-square fitting fails;
            // collect real-inliers;
            sdev = findInlier(xp, yp, cparams, dist_th / 2, consensusx, consensusy); 
            if (consensusx.size() < sample_th) continue;
            // estimate model params using inliers again;
            if (!CircleFit_LS(consensusx, consensusy, cparams)) continue;            
            TRACE("circle infos: cx = %f, cy = %f, rad=%f\n", cparams[0], cparams[1], cparams[2]);
            if (sdev < min_dev) {
                min_dev = sdev;
                found = 1;
                // we need more elaborate termination conditions;
#if _DEBUG
#endif
            }
        }
    }
    return found;
};
  • sample_th = 2 * N / 3;
  • dist_deviate_th = 0.25;
  • 파란색: 최소자승법을 이용한 피팅 (outlier의 영향을 많이 받음);
  • 붉은색: RANSAC 피팅 결과 (2017.01.04 수정)

see also http://blog.naver.com/helloktk/80029898273

 
 
 
 
728x90

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

Chamfer Match  (0) 2008.08.01
Retinex Algorithm  (2) 2008.07.26
KMeans Algorithm  (0) 2008.07.19
Robust Line Fitting  (0) 2008.07.08
EM: Binarization  (0) 2008.07.01
Posted by helloktk
,

이미지에서 관찰된 점집합이 $\{(x_i, y_i)| i = 1, 2,\dots, N\}$이 있다. 이 점집합을 직선 $y = a + bx$ 로 피팅을 하고 싶을 때, 보통 최소자승법을 이용하는데, 원리는 직선의 방정식이 예측한 $y$값과 실제 관찰한 $y$값의 차이의 제곱(=square deviation)을 최소화시키는 직선의 기울기 $a$와 절편 $b$를 찾는 것이다:

$$\chi^2(a, b) = \sum_i |y_i - (b x_i +a) |^2 $$

데이터를 얻는 측정 과정에서 측정값 $y_i$는 랜덤 노이즈를 포함하게 되고, 이 노이즈는 참값 $y(x)$ 근방에서 정규분포를 한다고 가정을 할 수 있다. 만약 모든 측정의 노이즈가 동일한 표준편차 $\sigma$를 갖게 된다면, $N$개의 관측 데이터가 나타날 확률(likelihood)은 (개별 측정은 IID 조건을 만족한다고 전제)

$$P = \prod_{i} e^{ -\frac{ | y_i -  (bx_i + a)|^2 }{2\sigma^2 }  }$$

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

$$\text{absolute deviation} = \sum _i | y_i - (bx_i + a)|   .$$

그러나 이 식을 사용하는 경우에는 최소자승법과 다르게 기울기 $a$와 절편 $b$를 주어진 데이터 $\{(x_i, y_i)\}$로 표현할 수 없고, 반복적인 방법을 이용해서 찾아야 한다. 


수열 $\{c_i\}$에 대해
합 $\sum_{i} |c_i - a|$
은 $a$가 수열의 median 값일 때 최솟값을 갖는다는 사실을 이용하면 (증명: 극값을 구하기 위해서 $a$에 대해서 미분하면, $0=(\sum_{c_i > a} 1)-(\sum_{c_i < a} 1)$: 합은 $a$가 $c_i$ 보다 큰 경우와 작은 경우로 분리. 따라서 0이 되기 위해서는 작은 경우와 큰 경우의 수가 같아야 한다. 고로, $a = \text{median}\{c_i\}$ q.e.d.). 고정된 절편 $b$에 대해서 absolute deviation을 최소로 만드는 기울기 $a$는

$$a= \text{median} \{ y_i - b x_i\}$$

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

$$0 = \sum_i \text{sign} \left( y_i - (bx_i +a) \right)$$

을 얻는데, 위에서 구한 기울기 $a$를 대입한 후 bracketing and bisection 방법을 이용하면 절편 $b$를 얻을 수 있다(불연속 함수이므로 일반적으로 근을 구하는 방법을 사용하는 것은 위험하다). 아래의 코드는 이를 구현한 것이다.

 

double FitLine_LS(std::vector<double>& x, std::vector<double>& y, double *a, double *b);

더보기
// 최소자승법을 이용한 직선 추정:
// return (sigma[dy] / sigma[x]);
double FitLine_LS(std::vector<double>& x, std::vector<double>& y, double& a, double& b) {
    double sx = 0, sy = 0, sxx = 0, sxy = 0;
    for (int i = x.size(); i-->0;) {
        sx  += x[i];        sy  += y[i];
        sxx += x[i] * x[i]; sxy += x[i] * y[i];
    };
    const int n = x.size();
    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 (int i = x.size(); i-->0;) {
        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);
}
// 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(std::vector<double>&x, std::vector<double>& y,
               double bb, double& aa, double& abdev) {
    std::vector<double> h(x.size());
    for (int i = x.size(); i-->0;) h[i] = y[i] - bb * x[i];
    qsort(&h[0], h.size(), sizeof(double), comp);
    // median;
    const int med = h.size()/2;
    aa = (h.size() & 1) ? h[med] : (h[med] + h[med-1])/2;

    double sum = 0;
    abdev = 0;
    for (int i = x.size(); i-->0;) {
        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]);
    }
    return sum; // return sum{xi * sign(yi - (b * xi + a))}
};
// y = a + b * x ;
// Least Absolute Deviation:
double FitLine_MAD (std::vector<double>& x, std::vector<double>& y,
                    double& a, double& b) {
    // least square esimates for (aa, bb);
    double aa, bb, abdev;
    double sigb = FitLine_LS(x, y, aa, bb);   // estimate: y=aa + bb*x;
    double b1 = bb;
    double f1 = RhoFunc(x, y, 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, 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, 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, bb, aa, abdev) ;
        if ((f * f1) >= 0) {
            f1 = f; b1 = bb;
        } else {
            f2 = f; b2 = bb;
        }
    }
    a = aa; b = bb; 
    return (abdev/x.size());
}

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

 

 
 
 
 
728x90

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

RANSAC: Circle Fit  (0) 2008.07.21
KMeans Algorithm  (0) 2008.07.19
EM: Binarization  (0) 2008.07.01
EM Algorithm: Line Fitting  (0) 2008.06.29
Gaussian Mixture Model  (2) 2008.06.07
Posted by helloktk
,

아래 그림을 보면 우리는 데이터를 연결하는 두 개의 직선을 생각할 수 있을 것이다.  그럼 두 개의 직선을 어떻게 얻을 것인가? 물론, ICA(independent component analysis)를 이용하는 것이 한 가지 방법이 될 것이다. 여기서는 EM 알고리즘을 이용하여서 두 개의 직선을 기술하는 기울기와 $y$-절편의 값을 구하는 방법을 알아보자.

 

 

사용자 삽입 이미지


직선을 각각 $y=a_1 x + b_1$, $y = a_2  x + b_2$라고 하면, $(a_1, b_1)$, $(a_2, b_2)$를 구하는 문제이다. 만약 각각의 data가 에러가 수반되는 측정에 의해서 얻어졌다고 하자. 에러 분포가 정규분포를 따른다면(여기서는 두 개의 모델 모두 갖은 표준편차를 갖는다고 가정했다) $i$-번째의 데이터가 각각의 직선 모델 1과 2에 속할 확률은 (posterior with equal prior) Bayes 공식에 의해서 

$$ w_1[i] = \frac{ e^{ - \frac{ r_1^2[i]}{2\sigma^2} } } {e^{ - \frac{ r_1^2[i]}{2\sigma^2} } + e^{ - \frac{ r_2^2[i]}{2\sigma^2} } }, \quad w_1[i] = \frac{ e^{ - \frac{ r_2^2[i]}{2\sigma^2} } } {e^{ - \frac{ r_1^2[i]}{2\sigma^2} } + e^{ - \frac{ r_2^2[i]}{2\sigma^2} } }, \quad i = 0,1,2,... $$

로 주어진다. 여기서 $r_1(i)$와 $r_2(i)$는 residual error이다:

$$r_1[i] = a_1 x[i] + b_1 - y[i],\quad r_2[i] = a_2 x[i] + b_2 - y[i], \quad i=0,1,2,...$$

(*이 값 대신에 직선까지 거리=$\frac{|a_k x + b_k - y|}{\sqrt{1+ a_k^2}},~ k=1,2)$로 대체해도 된다)

이제 각각의 데이터에 대해서 posterior를 구하였으므로(E-step) 이 값을 가중치로 하여서 직선의 방정식을 다시 갱신한다. 즉, 각각의 data 점들에 대한 $w_1(i)$를 가중치로 하여서 다시 직선 모델 1의 파라미터를 재계산하고, 동일한 과정을 $w_2(i)$를 가지고 직선 모델 2를 계산하여서 $(a_1, b_1)$, $(a_2, b_2)$를 재계산한다(M-step). 이 갱신된 파라미터를 이용하여서 다시 가중치를 구하는 작업과, 직선의 파라미터를 구하는 작업을 일정하게 수렴할 때까지 반복을 하는 과정을 수행한다.

아래의 그림은 3번 만에 원하는 결과를 얻는 것을 보여준다. 직선의 파라미터에 대한 초기값과 residual error의 표준편차 파라미터에 대한 적절한 값의 선택이 중요하다.

사용자 삽입 이미지

// 코드의 일부...
std::vector<CPoint> data ;                             // data,
std::vector<double> w1(data.size()), w2(data.size());  // weights.
double a1, b1, a2, b2 ;                                // line params;
double sigma ;
// E-step;
void calcWeights() {
    for (int i = data.size(); i-- > 0;) {
        double  x = data[i].x, y = data[i].y ;
        double r1 = a1 * x + b1 - y ;
        double r2 = a2 * x + b2 - y ;
        double n1 = SQR(r1) / SQR(sigma) / 2;
        double n2 = SQR(r2) / SQR(sigma) / 2;
        double p1 = exp( - n1);
        double p2 = exp( - n2);
        w1[i] = p1 / (p1 + p2);
        w2[i] = p2 / (p1 + p2);
    }
};
//  M-step
void estimModels() {
    double s1xx = 0, s1x = 0, s1 = 0, s1y = 0, s1xy = 0;
    double s2xx = 0, s2x = 0, s2 = 0, s2y = 0, s2xy = 0;
    for (int i = data.size(); i-- > 0;) {
        double  x = data[i].x,
                y = data[i].y;
            s1xx += w1[i] * SQR(x);
            s1xy += w1[i] * x * y;
            s1x  += w1[i] * x;
            s1y  += w1[i] * y;
            s1   += w1[i];
            //
            s2xx += w2[i] * SQR(x);
            s2xy += w2[i] * x * y;
            s2x  += w2[i] * x;
            s2y  += w2[i] * y;
            s2   += w2[i];
    };
    double det1 = s1xx * s1 - SQR(s1x);
    double det2 = s2xx * s2 - SQR(s2x);
    a1 = (s1 * s1xy  - s1x * s1y ) / det1;
    b1 = (s1xx * s1y - s1x * s1xy) / det1;
    a2 = (s2 * s2xy  - s2x * s2y ) / det2;
    b2 = (s2xx * s2y - s2x * s2xy) / det2;
}
 
728x90

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

Robust Line Fitting  (0) 2008.07.08
EM: Binarization  (0) 2008.07.01
Gaussian Mixture Model  (2) 2008.06.07
Rasterizing Voronoi Diagram  (0) 2008.05.26
RANSAC Algorithm  (0) 2008.05.24
Posted by helloktk
,

RANSAC Algorithm

Image Recognition 2008. 5. 24. 09:02

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

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

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

     1. 임의로 관측 데이터에서 N개의 부분 데이터를 선택한다.
     2. 선택 데이터를 (가상의) inlier로 생각하고 모델을 예측한다.
     3. 원본 데이터(M) 중에서 예측된 모델에 잘 맞는가를 체크한다. 잘 맞는 데이터 수를 K라고 한다.
     4. 만약에 K가 충분하면, 이 모델을 확정하고 알고리즘을 종료한다.
     5. 모델이 좋지 않으면 14 과정을  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,
pfail = 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

 

RANSAC: Circle Fit

RANSAC 알고리즘을 써서 주어진 2차원 점집합에서 원을 추정한다. 원을 만들기 위해서는 최소한 3점이 필요하고, 또 일직선에 있지 않아야 한다. 이렇게 만들어진 원은 세 점을 꼭짓점으로 하는

kipl.tistory.com

ransac을 이용한 타원 피팅: kipl.tistory.com/110

 

RANSAC Ellipse Fitting

타원은 원뿔을 평면으로 잘랐을 때 생기는 곡선 중의 하나로 다음 이차 형식(quadratic form)으로 표현된다. . 이 이차 형식의 계수를 구하기 위해서는 타원 위의 5개의 서로 다른 점이 필요하다 $(a

kipl.tistory.com

 

728x90

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

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