'이진화'에 해당되는 글 2건

  1. 2010.01.28 Otsu-알고리즘의 새로운 해석
  2. 2008.07.01 EM : Binarization

제대로 세그먼트된 그레이 영상은 원래의 영상이 나타내고자 하는 전경이 제대로 표현이 된 것이다. 이것은 원래 영상과 세그먼트된 영상의 상관관계가 높아야 함을 의미한다. 따라서 세그먼트를 위한 임계값의 기준으로 이 상관계수를 최대로 하는 임계값을 찾는 것도 좋은 기준중의 하나가 될 수 있다.

 

여기서 사용할 상관계수는 원래의 영(A)과 전경과 배경을 그들의 평균 그레이값으로 대체한 세그먼트된 영상(B)간의 상관계수를 사용한다. 세그먼트된 영상 B는 임계값이 T인 경우에

B(i, j) =  m0   if A(i, j) <= T

            m1    otherwise ;

로 정의된다. 여기서 m0는 배경부분의 평균 그레이값이고, m1은 전경부분의 평균 그레이값을 의미한다. 이 값은 임계값 T에 따라서 달라진다. 임계값이 높으면 m0는 커지고, 반대로 m1은 작아진다.

임계값이 T일 때, 배경의 픽셀수 비를 p 라고 하고, 전경의 픽셀수 비를 q(=1- p) 라고 하면

E(A) = E(B) = m = 그레이_평균 = p*m0 + q*m1;

V(A) = 그레이_분산 = T-값에 무관하게 일정;

V(B) = p*m02 + q*m12 – m2 = p*q*(m0 – m1)2;

E(A, B) = p*m02 + q*m12 ;

이므로,

Correlation(A, B)

= (E(A,B) – E(A)*E(B))/sqrt(V(A)*V(B))

= sqrt(p*q*(m0 – m1)2) / sqrt(V(A));

= sqrt(p*q*(m0 – m1)2) up to constant factor;

= interclass variance;

= Otsu’s criteria

, 원래의 그레이영상 A와 전경과 배경을 각각의 평균값으로 대체한 영상간의 상관계수는 전경과 배경 두 클래스간의 분산이 최대일 때, 가장 크게 나타난다. 이 기준은 Otsu 알고리즘에서 사용한 기준과 같다.

참고: Otsu Algorithm 구현 예.

Posted by helloktk

이미지의 히스토그램을 이용하여서 전경과 배경을 분리하는 이진화 과정은 가우시안 mixture model을 이용하여서 EM 알고리즘을 적용하기에 좋은 예다. 전경에 해당하는 픽셀값의 분포와 배경에 해당하는 픽셀값의 분포는 히스토그램상에 섞여서 나타나는데. 이것을 두 가우시안의 혼합으로 생각할 때  em 알고리즘은 각각의 믹싱정도와 각 가우시안의 평균 및 표준편차를 추정한다. mixing parameter πa (a=1, 2,..., nclass)로 표시하는 경우에 특정한 픽셀값에 대한 posterior는


로 쓸수 있다. 여기서 f(x; θ)는 정규분포를 의미한다. 

posterior 정보를 이용하면 mixing parameter πa와 평균, 분산은 다음식으로 갱신이 된다. H[i]는 이미지의 히스토그램을 나타낸다.


   


log-likelihood:

여기서 a는 클래스 인덱스이고, i는 히스토그램 bin 인덱스이다.



// mixing 클래스를 기술하는 클래스;

struct mixclass {
    double prob ;               //mixing parameter;
    double mean ;               // mean
    double var ;                //variance;
} ;
// N(mean, var);

double gauss1d(double x, double mean, double var) {

// posterior; Pr(Zi = c | xi, Theta);
// 주어진 관측값 x이 클래스 cid에 속할 posterior;
double classprob(double x, int nclass, mixclass*  mclass, int cid) {

// posterior (class_prob[i][c]) table 만들기;
void update_class_prob(int nbins, double * hist, int nclass, mixclass* mclass, double ** class_prob) {
// E-step;  pi[c] = mixture parameter for class c;
// posterior를 이용해서 특정클래스의 mixing 정도를 계산;==> next prior;
void update_prob(int nbins, double * hist, int nclass, mixclass* mclass, double ** class_prob) {
// mu[c]; 클래스의 평균;
void update_mean(int nbins, double * hist, int nclass, mixclass* mclass,  double ** class_prob) {
// var[c]; 클래스의 분산;
void update_var(int nbins, double * hist, int nclass, mixclass* mclass, double ** class_prob) {
// M-step; 
void update_parameters(int nbins, double * hist, int nclass, mixclass* mclass, double ** class_prob) {
// initialization;
void init_em(int nbins, double * hist, int nclass, mixclass* mclass) {
// calculate log-likelihood;
double mixLLK(int nclass, mixclass* mclass) { 
// check termination condition;
bool check_tol(double llk, double llk_p, double  eps) {
// 입력은 이미지의 히스토그램;
double em(int nbins/*=256*/, double hist[/*256*/],
    int nclass/*=2*/, mixclass mclass[/*=2*/], double eps/*=1.e-10*/) {
    double llk = 0, prev_llk = 0;
    // allocate memory buffers for the posterior information;
    double ** class_prob = (double**)malloc(sizeof(double*) * nbins);
    class_prob[0] = (double*)malloc(sizeof(double) * nbins * nclass) ;
    for (int i = 1; i < nbins; i++) class_prob[i] = class_prob[i - 1] + nclass;

    // initialization of algorithm;
    init_em(nbins, hist, nclass, mclass);
    //
    do {
        prev_llk = llk;
        // E-step ;
        update_class_prob(nbins, hist, nclass, mclass, class_prob);
        // M-step;
        update_parameters(nbins, hist, nclass, mclass, class_prob);
        llk = mixLLK(nclass, mclass);
        // TRACE("mean1=%f, mean2=%f\n", mclass[0].mean, mclass[1].mean);
        TRACE("log-likelihood=%e\n", llk);
    } while (!check_tol(llk, prev_llk, eps));
    // clean ;
    free(class_prob[0]);
    free(class_prob) ;
    return llk;
};
  • 적색 : 히스토그램 
  • 청색, 녹색 : posterior(membership); 
  • Otsu 알고리즘을 쓰는 경우에 100에서 threshold 값이 결정되고 EM은 110 정도임.

사용자 삽입 이미지

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

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
Shuffling  (0) 2008.06.21
Bayesian Decision Theory  (1) 2008.06.17
Posted by helloktk