Geometry & Recognition

참고:  ndevilla.free.fr/median/median/src/optmed_bench.c

/*
 * Optimized median search on 9 values
 */
#define PIX_SORT(a,b) { if ((a) > (b)) PIX_SWAP((a), (b)); }
#define PIX_SWAP(a,b) { BYTE temp = (a); (a) = (b); (b) = temp; }
BYTE opt_med9(BYTE p[9]) {
    PIX_SORT(p[1], p[2]) ; PIX_SORT(p[4], p[5]) ; PIX_SORT(p[7], p[8]) ; 
    PIX_SORT(p[0], p[1]) ; PIX_SORT(p[3], p[4]) ; PIX_SORT(p[6], p[7]) ; 
    PIX_SORT(p[1], p[2]) ; PIX_SORT(p[4], p[5]) ; PIX_SORT(p[7], p[8]) ; 
    PIX_SORT(p[0], p[3]) ; PIX_SORT(p[5], p[8]) ; PIX_SORT(p[4], p[7]) ; 
    PIX_SORT(p[3], p[6]) ; PIX_SORT(p[1], p[4]) ; PIX_SORT(p[2], p[5]) ; 
    PIX_SORT(p[4], p[7]) ; PIX_SORT(p[4], p[2]) ; PIX_SORT(p[6], p[4]) ; 
    PIX_SORT(p[4], p[2]) ; return(p[4]) ;
}

BYTE opt_med25(BYTE p[]) { 
    PIX_SORT(p[0], p[1]) ;   PIX_SORT(p[3], p[4]) ;   PIX_SORT(p[2], p[4]) ;
    PIX_SORT(p[2], p[3]) ;   PIX_SORT(p[6], p[7]) ;   PIX_SORT(p[5], p[7]) ;
    PIX_SORT(p[5], p[6]) ;   PIX_SORT(p[9], p[10]) ;  PIX_SORT(p[8], p[10]) ;
    PIX_SORT(p[8], p[9]) ;   PIX_SORT(p[12], p[13]) ; PIX_SORT(p[11], p[13]) ;
    PIX_SORT(p[11], p[12]) ; PIX_SORT(p[15], p[16]) ; PIX_SORT(p[14], p[16]) ;
    PIX_SORT(p[14], p[15]) ; PIX_SORT(p[18], p[19]) ; PIX_SORT(p[17], p[19]) ;
    PIX_SORT(p[17], p[18]) ; PIX_SORT(p[21], p[22]) ; PIX_SORT(p[20], p[22]) ;
    PIX_SORT(p[20], p[21]) ; PIX_SORT(p[23], p[24]) ; PIX_SORT(p[2], p[5]) ;
    PIX_SORT(p[3], p[6]) ;   PIX_SORT(p[0], p[6]) ;   PIX_SORT(p[0], p[3]) ;
    PIX_SORT(p[4], p[7]) ;   PIX_SORT(p[1], p[7]) ;   PIX_SORT(p[1], p[4]) ;
    PIX_SORT(p[11], p[14]) ; PIX_SORT(p[8], p[14]) ;  PIX_SORT(p[8], p[11]) ;
    PIX_SORT(p[12], p[15]) ; PIX_SORT(p[9], p[15]) ;  PIX_SORT(p[9], p[12]) ;
    PIX_SORT(p[13], p[16]) ; PIX_SORT(p[10], p[16]) ; PIX_SORT(p[10], p[13]) ;
    PIX_SORT(p[20], p[23]) ; PIX_SORT(p[17], p[23]) ; PIX_SORT(p[17], p[20]) ;
    PIX_SORT(p[21], p[24]) ; PIX_SORT(p[18], p[24]) ; PIX_SORT(p[18], p[21]) ;
    PIX_SORT(p[19], p[22]) ; PIX_SORT(p[8], p[17]) ;  PIX_SORT(p[9], p[18]) ;
    PIX_SORT(p[0], p[18]) ;  PIX_SORT(p[0], p[9]) ;   PIX_SORT(p[10], p[19]) ;
    PIX_SORT(p[1], p[19]) ;  PIX_SORT(p[1], p[10]) ;  PIX_SORT(p[11], p[20]) ;
    PIX_SORT(p[2], p[20]) ;  PIX_SORT(p[2], p[11]) ;  PIX_SORT(p[12], p[21]) ;
    PIX_SORT(p[3], p[21]) ;  PIX_SORT(p[3], p[12]) ;  PIX_SORT(p[13], p[22]) ;
    PIX_SORT(p[4], p[22]) ;  PIX_SORT(p[4], p[13]) ;  PIX_SORT(p[14], p[23]) ;
    PIX_SORT(p[5], p[23]) ;  PIX_SORT(p[5], p[14]) ;  PIX_SORT(p[15], p[24]) ;
    PIX_SORT(p[6], p[24]) ;  PIX_SORT(p[6], p[15]) ;  PIX_SORT(p[7], p[16]) ;
    PIX_SORT(p[7], p[19]) ;  PIX_SORT(p[13], p[21]) ; PIX_SORT(p[15], p[23]) ;
    PIX_SORT(p[7], p[13]) ;  PIX_SORT(p[7], p[15]) ;  PIX_SORT(p[1], p[9]) ;
    PIX_SORT(p[3], p[11]) ;  PIX_SORT(p[5], p[17]) ;  PIX_SORT(p[11], p[17]) ;
    PIX_SORT(p[9], p[17]) ;  PIX_SORT(p[4], p[10]) ;  PIX_SORT(p[6], p[12]) ;
    PIX_SORT(p[7], p[14]) ;  PIX_SORT(p[4], p[6]) ;   PIX_SORT(p[4], p[7]) ;
    PIX_SORT(p[12], p[14]) ; PIX_SORT(p[10], p[14]) ; PIX_SORT(p[6], p[7]) ;
    PIX_SORT(p[10], p[12]) ; PIX_SORT(p[6], p[10]) ;  PIX_SORT(p[6], p[17]) ;
    PIX_SORT(p[12], p[17]) ; PIX_SORT(p[7], p[17]) ;  PIX_SORT(p[7], p[10]) ;
    PIX_SORT(p[12], p[18]) ; PIX_SORT(p[7], p[12]) ;  PIX_SORT(p[10], p[18]) ;
    PIX_SORT(p[12], p[20]) ; PIX_SORT(p[10], p[20]) ; PIX_SORT(p[10], p[12]) ;
    return (p[12]);
}

/*---------------------------------------------------------------------------
   Function :   kth_smallest()
   In       :   array of elements, # of elements in the array, rank k
   Out      :   one element
   Job      :   find the kth smallest element in the array
   Notice   :   use the median() macro defined below to get the median. 
                Reference:
                  Author: Wirth, Niklaus 
                   Title: Algorithms + data structures = programs 
               Publisher: Englewood Cliffs: Prentice-Hall, 1976 
    Physical description: 366 p. 
                  Series: Prentice-Hall Series in Automatic Computation 
 ---------------------------------------------------------------------------*/
#define SWAP(a, b) {BYTE t = (a); (a) = (b); (b) = t; }
BYTE kth_smallest(BYTE a[], int n, int k) {
    int l = 0, m = n - 1 ;
    while (l < m) {
        BYTE x = a[k] ;
        int i = l, j = m ;
        do {
            while (a[i] < x) i++ ;
            while (x < a[j]) j-- ;
            if (i <= j) {
                SWAP(a[i], a[j]) ;
                i++ ; j-- ;
            }
        } while (i <= j) ;
        if (j < k) l = i ;
        if (k < i) m = j ;
    }
    return a[k] ;
}
#define median(a, n) kth_smallest(a, n, (((n) & 1) ? ((n) / 2) : (((n) / 2) - 1)))

더보기

Neighborhood Map;

[0 1 2]

[7 8 3]

[6 5 4]

int Thinning_2pass(BYTE *image, int w, int h) {
    const int xmax = w - 1, ymax = h - 1;
    const int nn[9] = {-w - 1,- w, -w + 1, 1, w + 1, w, w - 1, -1, 0};//clockwise;
    const BYTE FG = 255, BG = 0;
    bool *flag = new bool [w * h];
    int pass = 0, ok = 0;
    int nb[9];
    while (!ok) {
        ok = 1; pass = (pass + 1) % 2;
        for (int i = w * h; i-->0; ) flag[i] = false;
        for (int y = 1, pos = w; y < ymax; y++) {
            pos++;//x=0;
            for (int x = 1; x < xmax; x++, pos++) {
                if (image[pos] == FG) { //fg;
                    // condition 1; 
                    int count = 0;
                    for (int k = 0; k < 8; k++) 
                        if (image[pos + nn[k]] == FG) count++;
                    if (count >= 2 && count <= 6) {
                        for (int k = 0; k < 8; k++) nb[k] = image[pos + nn[k]];
                        nb[8] = nb[0]; //cyclic;
                        // condition 2;
                        int trans = 0;
                        for (int k = 0; k < 8; k++)
                            if (nb[k] == BG && nb[k + 1] == FG) trans++;
                        if (trans == 1) {
                            // condition3: top&&left=bg || bot=bg || right=bg
                            if (pass == 0 && (nb[3] == BG || nb[5] == BG ||	
                                (nb[1] == BG && nb[7] == BG))) {
                                    flag[pos] = true; ok = 0;
                            } else { // condition4: bot&&right=bg || top=bg || left=bg 
                                if (pass == 1 && (nb[1] == BG || nb[7] == BG ||	
                                    (nb[3] == BG && nb[5] == BG))) {
                                        flag[pos] = true; ok = 0;
                                }
                            }
                        }
                    }//(2<=count<=6);
                }
            }//for_x;
            pos++;//x = w - 1 skip;
        } //for_y;
        // remove flaged pixels;
        for (int y = 1, pos = w; y < ymax; y++) {
            pos++;//x = 0;
            for (int x = 1; x < xmax; x++, pos++) 
                if (flag[pos]) image[pos] = BG;
            pos++; //x=w-1;
        }
    }
    delete [] flag;
    return 1;
}

n이 양수일 때 n 과 n-1은 짝홀/홀짝의 짝이므로 2의 파워가 아니면 이진수로 표현할 때 한 곳에서 비트 차이가 난다. 따라서 AND연산을 하면 0이 아니다.  그런데 n이 2의 파워이면 최상위 비트만 1이고, n-1은 n의 최상위 비트를 제외한 하위비트 모두가 1로 구성되므로 AND 연산을 하면 0이다.

예:   n=6 = 110,  6-1=101 -->  6 & 5 = 100;

       n=8 = 1000, 8-1=0111 --> 8 & 7=0000

// n이 양수이고, n-1과 겹치는 비트가 없으면 된다;
bool IsPowerOf2(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

n>1 일 떄 2로 나누기를 계속할 때 1을 제외한 홀수가 나오면 안됨; 

bool IsPowerOf2(int n) {
    if (n == 1) return true;
    if (n == 0 || n & 1) return false;
    return IsPowerOf2(n >> 1);
} // n == 0;

x보다 크기 않은 2^i을 구한 후 x와 같은가 체크;

bool IsPowerof2(int x){
    int i = 0;
    while ((1 << i) < x) i++;
    if (x == (1 << i)) return true;
    return false;
}

2의 파워이면 log_2(n) = 자연수 이므로 ceil과 floor가 같다.

bool IsPowerOf2(int n) {
   if (n == 0) return false;
   return (ceil(log2(n)) == floor(log2(n)));
}

주어진 자연수보다 작지 않은 최소의 2^n;

int NextPowerOf2(int n) { //32-bit;
    n--;
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    n++;
    return n;    
} // NextPowerOf2(5) -> 8; NextPowerOf2(8) -> 8;

// labeling using depth-first search; non-recursive version;
int GetConnectedComponents(BYTE *image, int w, int h, int *table) {
    int label = 0;    // starting label = 1;
    std::vector<int> stack(w * h);
    // initialize the table;
    for (int k = npixs; k-- > 0;) 
        table[k] = image[k] ? -1: 0;  // Foreground = -1; Background = 0;

    for (int pos = w * h; pos-- > 0;) {
        if (table[pos] == -1) { // Foreground;
            ++label;            // assign next label;
            int top = -1;       // stack initialization;
            stack[++top] = pos;
            while (top >= 0) {
                int adj = stack[top--];
                int xx = adj % w;
                int yy = adj / w;
                if (table[adj] == -1) {// Foreground;
                    table[adj] = label;
                    // check 4-way connectivity;
                    if (xx + 1 < w) stack[++top] = adj + 1; //RIGHT;
                    if (yy + 1 < h) stack[++top] = adj + w; //BOTTOM;
                    if (yy > 0)     stack[++top] = adj - w; //TOP;
                    if (xx > 0)     stack[++top] = adj - 1; //LEFT;
                }
            }
        }
    }
    return label;    // total # of CCs;
};

이미지 처리 과정에서 미분에 해당하는 그래디언트 필드(gradient field: $g_x$, $g_y$ )를 이용하면 이미지 상의 특징인 corner, edge, ridge 등의 정보를 쉽게 얻을 수 있다. 이미지의 한 지점이 이러한 특징을 가지는 특징점이 되기 위해서는 그래디언트 필드의 값이 그 점 주변에서 (3x3나 5x5정도 크기의 window) 일정한 패턴을 유지해야 한다. 이 패턴을 찾기 위해서 그래디언트 필드에 PCA를 적용해보자. 수평과 수직방향의 그래디언트 field인 $g_x$와 $g_y$ 사이의 covariance 행렬은 다음 식으로 정의된다:

$$ \Sigma = \left [ \begin {array}{cc} < g_x^2 > & < g_x g_y > \\    <g_x g_y> & <g_y^2 > \end {array}\right] =\left [ \begin {array}{cc} s_{xx} & s_{xy} \\ s_{xy} & s_{yy}\end {array}\right];$$

$<...> = \int_{W}(...) dxdy$는 픽셀 윈도에 대한 적분을 의미한다. $\Sigma$의 eigenvalue는 항상 음이 아닌 값을 갖게 되는데 (matrix 자체가 positive semi-definitive), 두 eigenvalue이 $λ_1$, $λ_2$면

$$λ_1 + λ_2 = s_{xx} + s_{yy} \ge 0, \quad \quad    λ_1  λ_2 = s_{xx} s_{yy} - s_{xy}^2 \ge0 $$

을 만족한다 (완전히 상수 이미지를 배제하면 0인 경우는 없다). eigenvalue $λ_1$, $λ_2$는 principal axis 방향으로 그래디언트 필드의 변동(분산)의 크기를 의미한다. edge나 ridge의 경우는 그 점 주변에서 잘 정의된 방향성을 가져야 하고, corner의 경우는 방향성이 없어야 한다. edge나 ridge처럼 일방향성의 그래디언트 특성을 갖거나 corner처럼 방향성이 없는 특성을 서로 구별할 수 있는 measure가 필요한데, $λ_1$과 $λ_2$를 이용하면 차원이 없는 measure을 만들 수 있다. 가장 간단한 차원이 없는 측도(dimensionless measure)는  eigenvalue의 기하평균과 산술평균의 비를 비교하는 것이다.

$$ Q = \frac { {λ_{1} λ_{2}} }{ \left( \frac {λ_{1}+λ_{2}}{2} \right)^2} = 4\frac { s_{xx} s_{yy} - s_{xy}^2}{(s_{xx} + s_{yy})^2};$$

기하평균은 산술평균보다도 항상 작으므로

$$ 0 \le Q \le 1 $$

의 범위를 갖는다. 그리고 $Q$의 complement로

$$P = 1-Q = \frac{(s_{xx}-s_{yy})^2 + 4 s_{xy}^2}{(s_{xx}+s_{yy})^2};$$를 정의할 수 있는 데 $0 \le P \le 1$이다. $Q$와 $P$의 의미는 무엇인가? 자세히 증명을 할 수 있지만 간단히 살펴보면 한 지점에서 $Q \rightarrow 1$이려면 $λ_{1} \approx λ_{2}$이어야 하고, 이는 두 주축이 동등하다는 의미이므로 그 점에서는 방향성이 없는 코너의 특성을 갖게 된다. 반대로 $Q \rightarrow 0$이면 강한 방향성을 갖게 되어서 edge(ridge) 특성을 갖게 된다.

실제적인 응용으로는 지문 인식에서 지문 영역을 알아내거나 (이 경우는 상당이 큰 윈도를 사용해야 한다) 또는 이미지 텍스쳐 특성을 파악하기 위해서는 이미지를 작은 블록으로 나누고 그 블록 내의 미분 연산자의 균일성을 파악할 필요가 있는데 이 차원이 없는 측도는 이미지의 상태에 상관없이 좋은 기준을 주게 된다.

참고 논문:

Image field categorization and edge/corner detection from gradient covariance
Ando, S.
Pattern Analysis and Machine Intelligence, IEEE Transactions on
Volume 22, Issue 2, Feb 2000 Page(s):179 - 190

** 네이버 블로그 이전;