Union-Find 알고리즘을 이용하여 영역 분할 과정이다. 각각의 픽셀에서 4방향으로 연결된 픽셀이 속한 영역 merge 할 수 있는지를 시도한다. merge 조건은 현재 픽셀의 그레이 값과 인접 영역의 평균 그레이 값의 차이가 주어진 임계값보다 작은 경우다.

$$\text{merge 조건: }\quad | 그레이 값- \text{인접 영역 평균값}| < threshold$$

컬러 영상의 경우에는 RGB 채널에 조건을 부여하거나 gray level만 이용해서 판단할 수 있다. root node 수만큼의 분할 영역이 만들어지고, 임계값이 클수록 분할된 각 영역의 사이즈가 커진다.  

gray = 0.2989 * r + 0.5870 * g + 0.1140 * b ;

같은 평균 픽셀값을 가지고 있더라도 4-방향으로 서로 연결된 영역이 아니면 합병되지 못하고 서로 다른 영역으로 남는다. 이를 하나의 영역으로 만들려면 분할된 영역을 다시 검사를 하는 과정이 필요하다. 자세한 과정은 Statistical Region Merge(SRM) 알고리즘(kipl.tistory.com/98)에 잘 구현이 되어 있다.

int FindCompress(int node, int *parent) {  // find root node;
    if (parent[node] < 0) return node;     // root-node;
    else return parent[node] = FindCompress(parent[node], parent); //찾음과 동시에 depth을 줄인다;      
}
BOOL Predicate(int r1, int r2, int thresh, int *sum, int *sizes) {
    double diff = double(sums[r2]) / sizes[r2] - double(sums[r1]) / sizes[r1];
    return fabs(diff) < thresh;
}
// root가 r1인 집합(단일픽셀)을 root가 r2인 집합으로 합병한다;
// 전체 픽셀합과 픽셀수를 update한다;
void Merge(int r1, int r2, int *sums, int *sizes, int *parent) {
    sums[r2]    += sums[r1];
    sizes[r2]   += sizes[r1];
    parent[r1]   = r2;
    return TRUE;
}
// root 노드는 분할영역의 픽셀 갯수와 픽셀 값의 합을 저장한다.
// 처음 각 픽셀이 root 이고, 픽셀 갯수는 1, 픽셀값은 자신의 픽셀값을 저장;
BOOL UnionFindAverage(BYTE *image, int width, int height, int thresh) {
    int npixs   = width * height;
    int* parent = new int [npixs];    // parent table;
    int* sums   = new int [npixs];  
    int* sizes  = new int [npixs];
    // initial setting;
    for (int pos = 0; pos < npixs; pos++) {
        parent[pos] = -1;                // 각 픽셀이 root임;
        sums[pos]   = image[pos];
        sizes[pos]  = 1;
    }
    // 첫행; LEFT 픽셀이 속한 영역의 평균값과 차이가 thresh 이내이면 left로 합병함;
    for (int x = 1; x < width; x++) {
        int left = FindCompress(x - 1, parent);
        int curr = FindCompress(x, parent);
        if (Predicate(curr, left, thresh, sums, sizes))
            Merge(curr, left, sums, sizes, parent);
    }
    //Flatten(y=0);
    for (int x = 0; x < width; x++) FindCompress(x, parent);
    for (int y = 1, pos = y * width; y < height; y++) {
        // x = 0; up 픽셀이 속학 영역과 합병 체크;
        int up   = FindCompress(pos - width, parent);
        int curr = FindCompress(pos, parent);
        if (Predicate(curr, up, thresh, sums, sizes))
            Merge(curr, up, sums, sizes, parent);
        pos++;
        // UP-LEFT 픽셀 영역과 합병 체크;
        for (int x = 1; x < width; x++, pos++) {
            int left = FindCompress(pos - 1, parent);
            int curr = FindCompress(pos, parent);
            // left와 합병이 되면 left가 up과 합병이 되는지 확인; 안되면 up과 합병시도;
            if (Predicate(curr, left, thresh, sums, sizes)) {
                Merge(curr, left, sums, sizes, parent);
                curr = left;
            }
            int up = FindCompress(pos - width, parent);
            if ((curr != up) && (Predicate(curr, up, thresh, sums, size)))
                Merge(curr, up, sums, sizes, parent);
        }
        // Flatten(y>0);
        for (int x = 0; x < width; x++) FindCompress(x + y * width, parent);
    }
    // 평균 이미지를 만듬(input is overwritten);
    for (int pos = 0; pos < npixs; pos++) {
        // Find root;
        int node = pos;
        while (parent[node] >= 0) node = parent[node];
        int a = int(double(sums[node]) / sizes[node] + 0.5);
        image[pos] = a > 255 ? 255 : a;
    };
    delete [] parent;
    delete [] sums;
    delete [] sizes;
    return TRUE;
};

네이버 블로그 이전
statistical region merge 알고리즘을 적용한 결과

728x90

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

Octree Quantization  (0) 2021.01.12
Median-Cut 컬러 양자화  (0) 2021.01.12
Multilevel Otsu Thresholding  (0) 2021.01.09
Binary Image에서 Convex Hull  (0) 2021.01.06
Kuwahara Filter  (2) 2020.12.28
Posted by helloktk
,