Union-Find 알고리즘을 이용한 영역분할

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

$$\tt \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)에 잘 구현이 되어 있다.

struct Universe {
    int n;
    std::vector<int> sizes;
    std::vector<int> sums;
    std::vector<int> parent;
    Universe(int n, BYTE *image) {
        this->n = n;
        parent.resize(n, -1);  // all nodes are root;
        sizes.resize(n, 1); 
        sums.resize(n);
        for (int i = 0; i < n; i++)
            sums[i] = image[i];
    }
    int Find(int node) { // find root node;
        if ( parent[node] < 0 ) return node;	 // root-node;
        return parent[node] = Find(parent[node]);
        // 찾음과 동시에 depth을 줄인다;   
    }
    bool Predicate(int root1, int root2, int thresh) {
        double diff = double(sums[root2]) / sizes[root2] 
                      - double(sums[root1]) / sizes[root1];
        return fabs(diff) < thresh;
    }
    void Merge(int root1, int root2) {
        sums[root2]  += sums[root1];
        sizes[root2] += sizes[root1];
        parent[root1] = root2;			 // r2 트리로 합병함;
    }
};
// root 노드는 분할영역의 픽셀 갯수와 픽셀 값의 합을 저장한다.
// 처음 각 픽셀이 root 이고, 픽셀 갯수는 1, 픽셀값은 자신의 픽셀값을 저장;
BOOL UnionFindAverage(BYTE *image, int width, int height, int thresh) {
    Universe *UF = new Universe(width * height, image);
    // 4-connectivity:
    // 첫행; LEFT 픽셀이 속한 영역의 평균값과 차이가 thresh 내이면 left로 합병;
    for (int x = 1; x < width; x++ ) {
        int left = UF->Find(x - 1);
        int curr = UF->Find(x);
        if (UF->Predicate(curr, left, thresh))
            UF->Merge(curr, left);
    }
    //Flatten(y=0);
    for (int x = 0; x < width; x++) UF->Find(x);
    for (int y = 1, pos = y * width; y < height; y++ ) {
        // x = 0; TOP 픽셀이 속학 영역과 합병 체크;
        int up   = UF->Find(pos - width);
        int curr = UF->Find(pos);
        if (UF->Predicate(curr, up, thresh))
            UF->Merge(curr, up);
        pos++;
        // TOP-LEFT 픽셀 영역과 합병 체크;
        for (int x = 1; x < width; x++, pos++ ) {
            int left = UF->Find(pos - 1);
            int curr = UF->Find(pos);
            // left와 합병이 되면 left가 up과 합병이 되는지 확인;
            if (UF->Predicate(curr, left, thresh)) {
                UF->Merge(curr, left);
                curr = left;
            }
            int up = UF->Find(pos - width);
            if ((curr != up) && (UF->Predicate(curr, up, thresh))) 
                UF->Merge(curr, up);
        }
        // Flatten(y>0)
        for (int x = 0; x < width; x++) UF->Find(x + y * width);
    }

    // 평균 이미지 생성;
    for (int k = width*height; k-->0;) {
        int root = UF->Find(k);
        int avg = int(double(UF->sums[root]) / UF->sizes[root] + 0.5);
        image[k] = avg > 255 ? 255 : avg;
    }
    delete UF;
    return TRUE;
};

네이버 블로그 이전

statistical region merge 알고리즘을 적용한 결과