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

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

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

$$ th= \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

th[0]=103, th[1]=172  (th[2]=255)
th[0]=88, th[1]=176, th[2]=255

 

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

Median-Cut 컬러 양자화  (0) 2021.01.12
Union-Find 알고리즘을 이용한 영역분할  (0) 2021.01.11
Multilevel Otsu’s Thresholding  (0) 2021.01.09
Binary Image에서 Convex Hull  (0) 2021.01.06
Kuwahara Filter  (2) 2020.12.28
Moving Average을 이용한 Thresholding  (0) 2020.11.26
Posted by helloktk

댓글을 달아 주세요

728x90

http://www.lix.polytechnique.fr/~nielsen/tpami04-nn.pdf

Abstract—This paper explores a statistical basis for a process often described in computer vision: image segmentation by region merging following a particular order in the choice of regions. We exhibit a particular blend of algorithmics and statistics whose segmentation error is, as we show, limited from both the qualitative and quantitative standpoints. This approach can be efficiently approximated in linear time/space, leading to a fast segmentation algorithm tailored to processing images described using most common numerical pixel attribute spaces. The conceptual simplicity of the approach makes it simple to modify and cope with hard noise corruption, handle occlusion, authorize the control of the segmentation scale, and process unconventional data such as spherical images. Experiments on gray-level and color images, obtained with a short readily available C-code, display the quality of the segmentations obtained. 

인간은 영상을 보면 매우 쉽게 비슷한 픽셀 값을 갖는 영역으로 분리해서 인식을 한다. 우리가 보는 영상이 여러 개의 균일한 영역으로 나누어진 기본 영상에 랜덤 노이즈가 추가되어 만들어졌다고 생각해보자. 영상의 픽셀 값이 기본 영상의 픽셀 값에 일정 구간(Q)에서 값을 취하는 랜덤 변수가 더해져서 만들어졌다고 보면, 영상에서 다른 두 영역($R, R'$)의 픽셀 평균값의 차이 $(\overline{R}-\overline{R'})$와 기본 영상에서 랜덤 변수에 의한 통계적 기댓값의 차이 $(E(\overline{R}-\overline{R'}))$는 주어진 $0 < δ < 1$ 에 다음식을 만족함을 보일 수 있다.

따라서, 두 영역 $R$과 $R'$에 대해서 우변의 값이 이 부등식을 만족하지 않으면 두 영역은 하나로 인식될 수 있다.

 

#region count = 576; 많은 영역이 1픽셀로 구성이 되었있다;
#region count > 1 = 302;
#region count > 2 = 222;
#region count > 3 = 179;
#region count > 4 = 140;

 

 

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

RANSAC Ellipse Fitting  (1) 2012.10.07
Autofocus Algorithm  (0) 2012.06.03
Statistical Region Merging  (2) 2012.03.25
Local Histogram Equalization  (0) 2012.03.10
2차원 Savitzky-Golay Filters 응용  (0) 2012.02.28
webcam용 QR code detector  (0) 2012.02.19
Posted by helloktk

댓글을 달아 주세요

  1. 올림 2013.07.31 01:52  댓글주소  수정/삭제  댓글쓰기

    국내 모 대학에서 석사 공부하고 있는 학생인데...
    최근에 srm 공부하면서 paper 가 잘 이해가 안 되서 인터넷 검색하다가 이 글을 보게 되었습니다. paper 에 보면 Q 가 랜덤 변수이고 구간은 g/Q 라고 되어 있는 것 같은데, 맞는지요?

    위에서 말씀하신 "기본 영상의 균일한 영역에서 랜덤변수는 일정한 구간에서 값을 취하여, 영역의 픽셀 값과 더해져서 실제영상의 픽셀값을 만든다" 이 부분을 자세히 좀 설명해 주실 수 있는지요.

    미리 감사합니다.

    • helloktk 2013.08.01 17:53 신고  댓글주소  수정/삭제

      오래되고 자료도 없고, 요즘은 이 분야에 관심을 둘 여유가 없어서 자세한 답은 할 수가 없군요. Q가 랜덤변수가 아니고 각 영상의 채널을 몇 개의 구간으로 분할 할 것인가에 대한 외부값일 것입니다. Q=1이면 원래의 영상으로 나오겠지요. Q=2이면 [0,127][128,255]두 개의 그레이값의 영역으로 구별이 되고 ([0,127]-->0, [128,255]-->128인 두 기본영역) 실제 이 영상은 이 기본영상에 [0,127]사이의 값을 가지는 랜덤변수가 더해서진 결과로 표현된다는 의미일 것입니다.

728x90

(1) cell image : 원본 영상을 이진화(Otsu-알고리즘)시킨 결과다. 두 군데서 셀이 겹쳤다. 단순히 connected component labeling을 적용해서는 이를 분리할 수 없다.

사용자 삽입 이미지

(2) distance transform : distance 변환 결과에 blurring을 추가한 결과다. distance 변환은 셀 외부는 셀로부터의 거리를, 셀 내부는 배경으로부터의 거리의 음의 값을 취한 후 전체적으로 다시 리스케일한 것이다.  blurring은 watershed 알고리즘이 보다 정확히 동작하는데 필요하다.

사용자 삽입 이미지

 

(3) watershed segmentation: 분할된 영역의 label이 나온다(경계 label=0). 이 label을 가지고  false coloring을 한 결과이다. 이 알고리즘은 "The Watershed Transform: Definitions, Algorithms and Parallelization Strategies", Jos B.T.M. Roerdink and Arnold Meijster에 따라서 구현이 된 것이다. 픽셀 연결성은 8방향을 이용하였다.

사용자 삽입 이미지

(4) final result; watershed 결과를  mask로 이용하여서 이미지를 분할한 것이다. 겹친 cell이 분리되었다.

사용자 삽입 이미지

다른 예:

사용자 삽입 이미지

 

사용자 삽입 이미지

 

사용자 삽입 이미지

/**
** http://blog.naver.com/helloktk/80051779331 에서 옮긴 자료.
*/

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

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

댓글을 달아 주세요

  1. 2013.06.26 11:24  댓글주소  수정/삭제  댓글쓰기

    비밀댓글입니다

  2. helloktk 2013.06.27 23:28 신고  댓글주소  수정/삭제  댓글쓰기

    컴퓨터가 망가지는 통에 요 몇년간 작업한 내용은 다 사라진 상태입니다. 이 예제는 여러가지 알고리즘을 조합해서 쓰긴 했지만, 이 블로그와 네이버블로그를 보면 아마 필요한 부분은 다 찾을 수 있을 것입니다.