Geometry & Recognition

Otsu 알고리즘은 이미지를 이진화시키는데 기준이 되는 값을 통계적인 방법을 이용해서 결정한다. 같은 클래스(전경/배경)에 속한 픽셀의 그레이 값은 유사한 값을 가져야 하므로 클래스 내에서 픽셀 값의 분산은 되도록이면 작게 나오도록 threshold 값이 결정되어야 한다. 또 잘 분리가 되었다는 것은 클래스 간의 거리가 되도록이면 멀리 떨어져 있다는 의미이므로 클래스 사이의 분산 값은 커야 함을 의미한다. 이 두 가지 요구조건은 동일한 결과를 줌을 수학적으로 보일 수 있다.

이미지의 이진화는 전경과 배경을 분리하는 작업이므로 클래스의 개수가 2개, 즉, threshold 값이 1개만 필요하다. 그러나 일반적으로 주어진 이미지의 픽셀 값을 임의의 개수의 클래스로 분리할 수도 있다. 아래의 코드는 주어진 이미지의 histogram을 Otsu의 아이디어를 이용해서 nclass개의 클래스로 분리하는 알고리즘을 재귀적으로 구현한 것이다. 영상에서 얻은 히스토그램을 사용하여 도수를 계산할 수 있는 0차 cumulative histogram($\tt ch$)과 평균을 계산할 수 있는 1차 culmuative histogram($\tt cxh$)을 입력으로 사용한다. 

$$ thresholds= \text {argmax} \left( \sigma^2_B = \sum_{j=0}^{nclass-1} \omega_j m_j^2 \right)$$

* Otsu 알고리즘을 이용한 이미지 이진화 코드: kipl.tistory.com/17

* 좋은 결과를 얻으려면 히스토그램에 적당한 필터를 적용해서 smooth하게 만드는 과정이 필요하다.

// 0 <= start < n;
double histo_partition(int nclass, double cxh[], int ch[], int n, int start, int th[]) {
    if (nclass < 1) return 0;
    if (nclass == 1) {
        int ws; double ms;
        if (start == 0) {
            ws = ch[n - 1];
            ms = cxh[n - 1] / ws;
        } else {
            ws = ch[n - 1] - ch[start - 1];             // start부터 끝까지 돗수;
            ms = (cxh[n - 1] - cxh[start - 1]) / ws;    // start부터 끝까지 평균값;
        }
        th[0] = n - 1;
        return ws * ms * ms;                            // weighted mean;
    }

    double gain_max = -1;
    int *tt = new int [nclass - 1];
    for (int j = start; j < n; j++) {
        int wj; double mj;
        if (start == 0) {
            wj = ch[j]; 
            mj = cxh[j];                    //mj = cxh[j] / wj;
        }
        else {
            wj = ch[j] - ch[start - 1];     //start부터 j까지 돗수;
            mj = (cxh[j] - cxh[start - 1]); //mj = (cxh[j] - cxh[start - 1]) / wj;
        }
        if (wj == 0) continue;
        mj /= wj;                           //start부터 j까지 평균;
        double gain = wj * mj * mj + histo_partition(nclass - 1, cxh, ch, n, j + 1, tt);
        if (gain > gain_max) {
            th[0] = j;
            for (int k = nclass - 1; k > 0; k--) th[k] = tt[k - 1];
            gain_max = gain;
        }
    }
    delete [] tt;
    return gain_max;
};

trimodal 분포의 분리;

class0: 0~th[0]

class1: (th[0]+1)~th[1],

class2: (th[1]+1)~th[2]=255

// recursive histo-partition 테스트;
// 0--t[0];--t[1];...;--t[nclass-2];t[nclass-1]=255=n-1;
// nclass일 때 threshold 값은 0---(nclss-2)까지;
double GetThreshValues(int hist[], int n, int nclass, int th[]) {
    if (nclass < 1) nclass = 1;
    // preparing for 0-th and 1-th cumulative histograms;
    int *ch = new int [n];          // cdf;
    double *cxh = new double [n];   //1-th cdf;
    ch[0] = hist[0];
    cxh[0] = 0; // = 0 * hist[0]
    for (int i = 1; i < n; i++) {
        ch[i] = ch[i - 1] + hist[i] ;
        cxh[i] = cxh[i - 1] + i * hist[i];
    }
    // nclass=1인 경우도 histo_partition()내에서 처리할 수 있게 만들었다.
    double var_b = histo_partition(nclass, cxh, ch, n, 0, th);
    delete [] ch;
    delete [] cxh;
    return var_b;
}

책상에 세워둔 연필이 넘어져서 바닥에 닿는데 걸리는 시간은 어떻게 될까? 대략 경험적으로 보면 연필 길이가 길수록 넘어지는데 시간이 오래 걸린다. 왜 그럴까? 넘어지는데 걸리는 시간은 연필의 운동을 결정하는 물리량과 관련 있는데, 우선 크기와 관련 있는 길이$(L)$가 있고, 넘어지려면 토크를 작용해야 하는데 이는 중력(가속도: $g$)과 관련이 있다.(마찰/수직 항력은 회전축에 걸리므로 무관하다). 물론 질량에도 의존할 수 있는데, 중력 가속도, 길이, 질량의 물리량으로 시간의 단위를 만들 수 있는 조합은 $\text{const} \times\sqrt { L /g}$ 밖에 없다. 즉, 넘어지는데 걸리는 시간은 길이에 제곱근에 비례한다. 

구체적으로 얼마나 걸리는지 계산을 시도해 보자. 연필이 넘어지면 수직과 이루는 각 $\theta$가 증가한다: $0\rightarrow \pi/2$. 뉴턴 방정식을 이용하면 $\theta$가 만족해야 할 미분방정식을 얻을 수 있지만, 실질적으로 일하는 힘이 중력밖에 없으므로 역학적 에너지가 보존된다는 사실을 이용하는 것이 좀 더 수월하다. 연필을 균일한 막대로 근사하면 넘어지는 과정은 연필심에 대한 회전운동이다. 역학적 에너지 보존식을 쓰면

$$\frac {1}{2} I_{tip} \Big(\frac {d\theta}{dt}\Big)^2 + \frac {1}{2} MgL \cos \theta = \text {const} = \frac {1}{2} MgL.$$ 여기서 각속도를 구하면

$$ \\ \frac{d\theta}{dt} = \sqrt { \frac {3g}{L}  (1- \cos \theta ) } = \sqrt {\frac {6g}{L}} \sin \frac {\theta}{2},$$

이고, 적분하여 수직 상태에서 바닥에 도달하는데 걸리는 시간을 구하면,

$$T= \sqrt { \frac {L}{6g}} \int_0^{\pi/2} \frac {d \theta }{\sin \frac {\theta}{2} } \rightarrow \infty.$$

기대(?)와는 다르지만 이 결과는 구체적으로 계산하지 않더라도 예상할 수 있다. 왜냐면 완전히 똑바로 서 있으면 회전의 시작에 필요한 토크를 생성하는 힘이 없기 때문이다. 연필에는 중력이 작용하고 끝에 마찰력이나 수직 항력이 있긴 하지만 토크를 만들지는 못한다. 따라서 연필을 넘어뜨리기 위해서는 처음에 약간의 충격을 주던지(속도 제공) 아니면 약간 기울인 상태에서 시작해야 한다. 처음 $\theta_0$의 각도에서 시작하였다면 걸리는 시간은 위 적분식에서

$$ T = \sqrt{\frac {2L}{3g} }\log \frac { \tan \frac {\pi}{8}}{\tan \frac {\theta_0}{4} }.$$

$\theta_0\rightarrow 0$이면 시간은 $T\sim -\sqrt { \frac {2L}{3g}} \log \theta_0 \rightarrow \infty$이고, 유한할 때는 길이의 제곱근에 비례함도 확인할 수 있다.

youtu.be/oowAdPjDY5M