728x90

segmentation result

1. 경계영역 처리를 보완해야 한다.

2. distance-map을 충분히 smooth하게 만들어야 한다: mean-filter 반복 적용.

3. 참고: imagej.net/Distance_Transform_Watershed의 구현보다 단순하지만 성능은 떨어진다.

#define insideROI(x, y) ((x) >= 0 && (x) < w && (y) >= 0 && (y) < h)
#define BACKGND 0xFF
int watershed(float *distMap, int w, int h, int *rgnMap) {
    const int xend = w - 1, yend = h - 1;
    const int nx[] =  {-1, 0, 1, -1, 0, 1, -1, 0, 1};
    const int ny[] =  {-1, -1, -1, 0, 0, 0, 1, 1, 1};
    // processing image;
    float **procImg = new float * [h];
    procImg[0] = new float [h * w];
    for (int y = 1; y < h; y++) procImg[y] = procImg[y - 1] + w;
    // presmooth; 10 iterations;
    float **pp = new float* [h];
    for (int y = 0; y < h; y++) pp[y] = &distMap[y * w];
    mean_filter(pp, w, h, 15, procImg); 

    // 입력 영상에서 경계는 global maximum으로 설정;
    for (int y = 0; y < h; y++ ) procImg[y][0] = procImg[y][xend] = BACKGND;
    for (int x = 0; x < w; x++ ) procImg[0][x] = procImg[yend][x] = BACKGND;
    // find local minima for each pixel;
    int minCnt = 1;
    for (int y = 0, pos = 0; y < h; y++) {
        for (int x = 0; x < w; x++, pos++) {
            float minVal = procImg[y][x];
            if (minVal == BACKGND) {
                rgnMap[pos] = 1;	// background(white);
                continue;
            }
            int minIdx = 4; //current position;
            for (int k = 0; k < 9; k++) {
                int xx = x + nx[k], yy = y + ny[k];
                if (insideROI(xx, yy) && procImg[yy][xx] <= minVal) {
                    minVal = procImg[yy][xx];
                    minIdx = k;
                }
            }
            if (minIdx == 4) rgnMap[pos] = ++minCnt; // center(x, y) is a new local minimum;
            else             rgnMap[pos] = -minIdx;  // direction of local-min =  "-(dir)"
        }
    }
    // follow gradient downhill for each pixel;
    // reset rgnMap to have the id's of local minimum connected with current pixel;
    for (int y = 1, pos = y * w; y < yend; y++ ) {
        pos++;
        for (int x = 1; x < xend; x++, pos++ ) {
            int minpos = pos;
            while ( rgnMap[minpos] <= 0 ) { //it is not a local minimum.
                switch ( rgnMap[minpos] ) {
                case  0: minpos += -w - 1; break; // top-lef = downhill direction;
                case -1: minpos += -w;	   break; // top
                case -2: minpos += -w + 1; break; // top-right;
                case -3: minpos--;         break; // left;
                case -5: minpos++;         break; // right;
                case -6: minpos += w - 1;  break; // bot-left;
                case -7: minpos += w;      break; // bot;
                case -8: minpos += w + 1;  break; // bot-right;
                }
            }
            // speed-up: use a stack to record downhill path.
            rgnMap[pos] = rgnMap[minpos]; //assign the id of a local minimum connected with current pixel;
        }
        pos++;
    }
    // rgnMap는 각 픽셀과 연결되는 국소점의 id을 알려주는 lookup table이다;
    delete [] procImg[0]; delete [] procImg;
    delete [] pp;
    return ( minCnt );
}

 

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

Watershed Segmentation  (0) 2021.02.27
Local Ridge Orientation  (0) 2021.02.21
Contrast Limited Adaptive Histogram Equalization (CLAHE)  (0) 2021.02.15
Fixed-Point Bicubic Interpolation  (0) 2021.01.19
Distance Transform  (0) 2021.01.16
FFT 알고리즘의 재귀적 구현  (0) 2021.01.14
Posted by helloktk

댓글을 달아 주세요

728x90
#define PIX_SORT(a,b) { if ((a) > (b)) PIX_SWAP((a), (b));} 
#define PIX_SWAP(a,b) { BYTE tmp = (a); (a) = (b); (b) = tmp;} 
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]); 
}
double ImageSharpness(BYTE *img, int w, int h) {
    const int npixs = w * h;
    const int xend = w - 1, yend = h - 1;
    const int nn[] = {-w - 1, -w, -w + 1, -1, 0, 1, w - 1, w , w + 1};
    const int sobelX[] = {-1, 0, 1, -2, 0, 2, -1, 0, 1};
    const int sobelY[] = {-1, -2, -1, 0, 0, 0, 1, 2, 1};
    //median filter;
    BYTE arr[9];
    BYTE *medimg = new BYTE [npixs];
    memset(medimg, 0, npixs);
    for (int y = 1, pos = y * w; y < yend; y++) {
        pos++;
        for (int x = 1; x < xend; x++, pos++) {
            for (int k = 0; k < 9; k++) arr[k] = img[pos + nn[k]];
            medimg[pos] = opt_med9(arr);
        }
        pos++;
    }
    // Tenenbaum gradient;
    double sharpness = 0;
    for (int y = 1, pos = y * w; y < yend; y++) {
        pos++;
        for (int x = 1; x < xend; x++, pos++) {
            double gx = 0, gy = 0;
            for (int k = 0; k < 9; k++) {
                int v = medimg[pos + nn[k]];
                gx += sobelX[k] * v;
                gy += sobelY[k] * v;
            }
            sharpness += gx * gx + gy * gy;
        }
        pos++;
    }
    delete [] medimg;
    return sharpness;
}

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

Poisson Noise  (0) 2021.03.06
Grassfire Algorithm  (0) 2021.03.05
Image Sharpness  (0) 2021.02.25
Selection Sort  (0) 2021.02.25
Bubble Sort  (0) 2021.02.24
Insertion Sort  (0) 2021.02.24
Posted by helloktk

댓글을 달아 주세요

728x90

void selection_sort(BYTE data[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int jmin = i;
        for (int j = i + 1; j < n; j++)
            if (data[j] < data[jmin]) jmin = j;
        if (jmin != i) SWAP(data[jmin], data[i]);
    }
}

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

Grassfire Algorithm  (0) 2021.03.05
Image Sharpness  (0) 2021.02.25
Selection Sort  (0) 2021.02.25
Bubble Sort  (0) 2021.02.24
Insertion Sort  (0) 2021.02.24
Optimized Median Search  (0) 2021.02.24
Posted by helloktk

댓글을 달아 주세요

728x90

#define SWAP(a, b) {BYTE tmp = (a); (a) = (b); (b) = tmp;}
void  bubble_sort(BYTE data[], int n) {
    for (int i = n - 1; i > 0; i--) {
        for (int j = 0; j < i; j++) {
            if (data[j] > data[j + 1]) 
                SWAP(data[j], data[j + 1]);
        }
    }
}

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

Image Sharpness  (0) 2021.02.25
Selection Sort  (0) 2021.02.25
Bubble Sort  (0) 2021.02.24
Insertion Sort  (0) 2021.02.24
Optimized Median Search  (0) 2021.02.24
Zhang-Suen Thinning Algorithm  (0) 2021.02.18
Posted by helloktk

댓글을 달아 주세요

728x90

void insertion_sort ( BYTE *data, int n ) {
    int j;
    for (int i = 1; i < n; i++ ) {
        BYTE remember = data[(j = i)];
        while ( --j >= 0 && remember < data[j] ) {
            data[j + 1] = data[j];
            data[j] = remember;
        }
    }
}

 

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

Selection Sort  (0) 2021.02.25
Bubble Sort  (0) 2021.02.24
Insertion Sort  (0) 2021.02.24
Optimized Median Search  (0) 2021.02.24
Zhang-Suen Thinning Algorithm  (0) 2021.02.18
Is Power of 2  (0) 2021.02.12
Posted by helloktk

댓글을 달아 주세요

728x90

참고:  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)))

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

Bubble Sort  (0) 2021.02.24
Insertion Sort  (0) 2021.02.24
Optimized Median Search  (0) 2021.02.24
Zhang-Suen Thinning Algorithm  (0) 2021.02.18
Is Power of 2  (0) 2021.02.12
Flood-Fill Algorithm을 이용한 Connected Component Labeling  (1) 2021.02.10
Posted by helloktk

댓글을 달아 주세요

728x90

지문에서 ridge의 방향(orientation)은 gradient에 수직한 방향이다(그런데 벡터인 gradient와는 달리 ridge의 방향은 모호함이 있다. 시계방향 또는 반시계방향으로 90도 회전이 모두 동일한 ridge의 방향이다).  gradient의 방향각이 $\alpha$일 때 ridge의 방향각은 $\theta =\frac{\pi}{2} + \alpha$로 정의하자. 방향각을 주어진 gradient 성분 $\nabla I = (g_x, g_y)$로 표현하기 위해서

$$ \sin 2\alpha = 2 \sin \alpha \cos \alpha = 2 \frac{g_x}{\sqrt{g_x^2 + g_y^2}}\frac{g_y}{\sqrt{g_x^2 + g_y^2}}$$

$$\cos 2\alpha = \cos^2 \alpha - \sin^2\alpha = \frac{g_x^2}{g_x^2 + g_y^2} -\frac{g_y^2}{g_x^2 +g_y^2}$$ 

임을 이용하자. $$\tan 2\alpha = \frac{ 2g_x g_y}{ g_x^2 - g_y^2}$$로 쓸 수 있으므로 ridge의 방향각은

$$ \theta =\frac{\pi}{2} + \frac{1}{2} \arctan \frac{2g_x g_y}{g_x^2 - g_y^2}$$

임을 알 수 있다. $(g_x, g_y) \rightarrow (-g_x, -g_y)$이더라도 ridge의 방향은 동일하므로 $\theta$의 범위는 $0\le \theta < \pi$로 제한된다.

 

이미지의 한 지점에서 ridge의 방향은 그 점을 중심으로 하는 적당한 크기의 윈도 평균값으로 추정한다. gradient 성분은 Sobel 연산자나 Prewitt 연산자를 convolution해서 얻을 수 있다. 따라서 지문 이미지 상의 픽셀 좌표 $(i,j)$에서 ridge의 방향은

$$\theta_{ij} = \frac{\pi}{2} +\frac{1}{2}\arctan \frac{2 G_{xy}}{G_{xx} - G_{yy}}$$

$$ G_{xy} = \sum_{W} \text{gradX}_{ij} \times \text{gradY}_{ij}$$

$$ G_{xx} = \sum_{W} \text{gradX}_{ij} \times \text{gradX}_{ij}$$

$$ G_{yy} = \sum_{W} \text{gradY}_{ij} \times \text{gradY}_{ij}$$

아래 결과는 5x5 크기의 Gaussian filter를 적용한 지문 이미지에 17x17 크기의 윈도를 겹치지 않게 잡아서 평균을 계산한 결과다. $G_{xx}+G_{yy}$가 최대값의 $20\%$보다 작은 영역은 방향을 표시하지 않았다 (red:0~45, yellow:45~90, magenta: 90~135, cyan: 135~180).

int RidgeOrientaion(BYTE *img, int w, int h, int bsz/*17*/, int *omap) {
    const int nn[] = {-w - 1, -w, -w + 1, -1, 0, 1, w - 1, w, w + 1};
    const int sobelX[] = {-1, 0, 1, -2, 0, 2, -1, 0, 1};
    const int sobelY[] = {-1, -2, -1, 0, 0, 0, 1, 2, 1};
    const int xmax = w - 1, ymax = h - 1;
    int *buffer = new int [2 * w * h];
    memset(buffer, 0, sizeof(int) * 2 * w * h);
    int *gradx = &buffer[0];
    int *grady = gradx + (w * h);
    for (int y = 1, pos = w; y < ymax; y++) {
        pos++; //x = 0;
        for (int x = 1; x < xmax; x++, pos++) {
            int sx = 0, sy = 0; 
            for (int k = 0; k < 9; k++) {
                int v = img[pos + nn[k]];
                sx += sobelX[k] * v;
                sy += sobelY[k] * v;
            }
            gradx[pos] = sx;
            grady[pos] = sy;
        }
        pos++; // x = xmax;
    }
    const int ny = h / bsz;
    const int nx = w / bsz;
    for (int iy = 0; iy < ny; iy++) {
        for (int ix = 0; ix < nx; ix++) {
            int sxy = 0, sxx = 0, syy = 0; 
            int pos = (iy * w + ix) * bsz; //starting position of block(ix, iy)
            int *dx = &gradx[pos];
            int *dy = &grady[pos];
            for (int jj = 0; jj < bsz; jj++) {
                for (int ii = 0; ii < bsz; ii++) {
                    int gx = dx[jj * w + ii];
                    int gy = dy[jj * w + ii];
                    sxy += gx * gy;
                    sxx += gx * gx;
                    syy += gy * gy;
                }
            }
            omap[iy * nx + ix] = 0.5 * (PI + atan2(double(2.0 * sxy), double(sxx - syy)));
        }
    }
    //...find fingerprint regions and draw orientational flow;
    delete[] buffer;
    return 1;
}

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

Watershed Segmentation  (0) 2021.02.27
Local Ridge Orientation  (0) 2021.02.21
Contrast Limited Adaptive Histogram Equalization (CLAHE)  (0) 2021.02.15
Fixed-Point Bicubic Interpolation  (0) 2021.01.19
Distance Transform  (0) 2021.01.16
FFT 알고리즘의 재귀적 구현  (0) 2021.01.14
Posted by helloktk

댓글을 달아 주세요

728x90

더보기
비교: Rosenfeld Algorithm(Graphics Gem IV)
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 y = 1, pos = w; y < ymax; y++) {
            pos++; //x=0;
            for (int x = 1; x < xmax; x++, pos++) flag[pos] = false;
            pos++; //x=w-1;
        }
        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;
                    int count = 0;
                    for (int k = 0; k < 9; k++) 
                        if (image[pos + nn[k]] == FG) count++;
                    if (count > 2 && count < 8) {
                        for (int k = 0; k < 8; k++) nb[k] = image[pos + nn[k]];
                        nb[8] = nb[0]; //cyclic;
                        int trans = 0;
                        for (int k = 0; k < 8; k++)
                            if (nb[k] == BG && nb[k + 1] == FG) trans++;
                        if (trans == 1) {
                            if (pass == 0 && (nb[3] == BG || nb[5] == BG ||	
                                (nb[1] == BG && nb[7] == BG))) {
                                    flag[pos] = true; ok = 0;
                            } else {
                                if (pass == 1 && (nb[1] == BG || nb[7] == BG ||	
                                    (nb[3] == BG && nb[5] == BG))) {
                                        flag[pos] = true; ok = 0;
                                }
                            }
                        }
                    }//(2 <count<8);
                }
            }//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;
}

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

Insertion Sort  (0) 2021.02.24
Optimized Median Search  (0) 2021.02.24
Zhang-Suen Thinning Algorithm  (0) 2021.02.18
Is Power of 2  (0) 2021.02.12
Flood-Fill Algorithm을 이용한 Connected Component Labeling  (1) 2021.02.10
Gradient Covariance  (0) 2021.01.27
Posted by helloktk

댓글을 달아 주세요

728x90

/* "Graphics Gems IV" 의 code를 수정함;*/
int CLAHE ( BYTE* image, int width, int height,
            BYTE gMin/*0*/, BYTE gMax/*255*/, int rgn_nx/*16*/, int rgn_ny/*16*/,
            int bins/*256*/, double fcliplimit )
{
    int* map_array	= new int [ rgn_nx * rgn_ny * bins ];
    int rgn_xsz		= width / rgn_nx;
    int rgn_ysz		= height / rgn_ny; 
    int rgn_area	= rgn_xsz * rgn_ysz;
    int clipLimit	= int( fcliplimit * ( rgn_xsz * rgn_ysz ) / bins );
    clipLimit = ( clipLimit < 1 ) ? 1 : clipLimit;
    //  
    /* calculate greylevel mappings for each contextual region */
    for (int iy = 0; iy < rgn_ny; iy++) {
        for (int ix = 0; ix < rgn_nx; ix++) {
            int *hist = &map_array[bins * ( iy * rgn_nx + ix )];
            int start = (iy * rgn_ysz) * width + ix * rgn_xsz;
            RgnHistogram (&image[start], width, rgn_xsz, rgn_ysz, hist, bins);
            ClipHistogram ( hist, bins, clipLimit );
            //convert hist to cuimulative histogram normalized to [gMin=0, gMax=255]
            MapHistogram ( hist, gMin, gMax, bins, rgn_area );
        }
    }

    /* bilinearInterp greylevel mappings to get CLAHE image */
    int szx, szy, ixl, ixr, iyt, iyb;
    BYTE *pimg = image;
    for (int iy = 0; iy <= rgn_ny; iy++ ) {
        if ( iy == 0 ) {					 
            szy = rgn_ysz / 2; iyt = iyb = 0;
        } else if ( iy == rgn_ny ) {				 
            szy = rgn_ysz / 2; iyt = rgn_ny - 1; iyb = iyt;
        } else {
            szy = rgn_ysz; iyt = iy - 1; iyb = iyt + 1;
        }
        for (int ix = 0; ix <= rgn_nx; ix++ ) {
            if ( ix == 0 ) {				 
                szx = rgn_xsz / 2; ixl = ixr = 0;
            } else if ( ix == rgn_nx ) {			 
                szx = rgn_xsz / 2; ixl = rgn_nx - 1; ixr = ixl;
            } else {
                szx = rgn_xsz; ixl = ix - 1; ixr = ixl + 1;
            }
            // cumulative histogram data;
            int *LU = &map_array[bins * ( iyt * rgn_nx + ixl )];
            int *RU = &map_array[bins * ( iyt * rgn_nx + ixr )];
            int *LB = &map_array[bins * ( iyb * rgn_nx + ixl )];
            int *RB = &map_array[bins * ( iyb * rgn_nx + ixr )];
            BilinearInterp (pimg, width, LU, RU, LB, RB, szx, szy );
            pimg += szx;			  
        }
        pimg += ( szy - 1 ) * width;
    }
    delete [] map_array;				
    return 0;						 
}
더보기
void ClipHistogram ( int* hist, int gLevels, int clipLimit ) {
    int excess = 0;
    for (int i = 0; i < gLevels; i++ ) { /* calculate total number of excess pixels */
        int diff =  hist[i] - clipLimit;
        if ( diff > 0 ) excess += diff;	 /* excess in current bin */
    };

    /* clip histogram and redistribute excess pixels in each bin */
    int incr = excess / gLevels;		/* average binincrement */
    int upper =  clipLimit - incr;		/* bins larger than upper set to cliplimit */
    for (int i = 0; i < gLevels; i++ ) {
        if ( hist[i] > clipLimit ) hist[i] = clipLimit; /* clip bin */
        else {
            if ( hist[i] > upper ) {			/* high bin count */
                excess -= hist[i] - upper;
                hist[i] = clipLimit;
            } else {							/* low bin count */
                excess -= incr;
                hist[i] += incr;
            }
        }
    }

    while ( excess ) { /* redistribute remaining excess  */
        int start = 0;
        while ( excess && start < gLevels) {
            int step = gLevels / excess;
            if ( step < 1 ) step = 1;		 /* step size at least 1 */
            for (int i = start; i < gLevels && excess; i += step) 
                if (hist[i] < clipLimit) { 
                    hist[i]++; excess--;
                }
            start++;
        }
    }
}

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

Watershed Segmentation  (0) 2021.02.27
Local Ridge Orientation  (0) 2021.02.21
Contrast Limited Adaptive Histogram Equalization (CLAHE)  (0) 2021.02.15
Fixed-Point Bicubic Interpolation  (0) 2021.01.19
Distance Transform  (0) 2021.01.16
FFT 알고리즘의 재귀적 구현  (0) 2021.01.14
Posted by helloktk

댓글을 달아 주세요

728x90
bool IsPowerOf2(int n) {
    return n && !(n & (n - 1));
    // return n > 0 && (n & (n - 1)) == 0;
}
bool IsPowerOf2(int i) {
    if (i == 1) return true;
    if (i == 0 || i & 1) return false;
    return IsPowerOf2(i >> 1);
} // i == 0; 
bool IsPowerof2(int x){
    int i = 0;
    while ((1 << i) < x) i++;
    if (x == (1 << i)) return true;
    return false;
}
bool IsPowerOf2(int n) {
   if (n == 0) return false;
   return (ceil(log2(n)) == floor(log2(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;

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

Optimized Median Search  (0) 2021.02.24
Zhang-Suen Thinning Algorithm  (0) 2021.02.18
Is Power of 2  (0) 2021.02.12
Flood-Fill Algorithm을 이용한 Connected Component Labeling  (1) 2021.02.10
Gradient Covariance  (0) 2021.01.27
점증적인 cosine/sine 값 계산  (0) 2020.12.28
Posted by helloktk

댓글을 달아 주세요

728x90

 

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

    for (int pos = 0; pos < npixs; pos++) {
        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;
                }
            }
        }
    }
    delete [] stack;
    return label;    // total # of CCs;
};

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

Zhang-Suen Thinning Algorithm  (0) 2021.02.18
Is Power of 2  (0) 2021.02.12
Flood-Fill Algorithm을 이용한 Connected Component Labeling  (1) 2021.02.10
Gradient Covariance  (0) 2021.01.27
점증적인 cosine/sine 값 계산  (0) 2020.12.28
Fast Float Sqrt  (0) 2020.12.27
Posted by helloktk

댓글을 달아 주세요

  1. hgmhc 2021.02.10 22:30 신고  댓글주소  수정/삭제  댓글쓰기

    DSU랑 Flood Fill이랑 시간 같나요?

728x90

빠른 속도의 비행기와 반대방향으로 나는 새가 정면충돌을 한다. 새는 비행기의 앞에 부딪힌 후 비행기와 같이 움직이게 된다(대부분은 중간에 떨어진다). 충돌에 의해서 새의 속도가 반대방향으로 바뀌었으므로 충돌 과정에서 새의 속도가 0인 순간이 있었을 것이다(속도는 시간의 연속함수이고, 방향이 변하면 성분의 부호가 변했음을 의미한다. 따라서 중간에 0이 되는 순간이 있어야 한다). 새의 속도가 0이라는 의미는 비행기도 그 순간 속도가 0이란 의미이므로(비행기가 새를 가르고 지나지 않았으므로) 새가 순간적이나마 비행기를 멈추었음을 의미할 것이다. 정말로 새가 자신보다도 엄청나게 더 무겁고 빠르게 움직이는 비행기를 순간적으로 정지시켰을까?

Posted by helloktk

댓글을 달아 주세요