Union-Find Connected Component Labeling

Union-Find 알고리즘을 이용하여 이진 영상의 Connected Component Labeling을 구현한 코드이다. 영상의 배경은 0으로 두고, 0이 아닌 픽셀은 모두 전경으로 처리한다.

각 전경 픽셀은 처음에는 독립된 집합의 root로 초기화한다. Union-Find의 parent 정보는 label 배열에 저장하며, 픽셀 위치를 pos라고 할 때 초기값은 \(\texttt{label[pos]=pos}\)로 둔다.

영상을 왼쪽 위에서 오른쪽 아래 방향으로 스캔하면서 현재 픽셀과 이미 조사된 이웃 픽셀의 연결관계를 확인한다. 4방향 연결에서는 왼쪽과 위쪽 픽셀을 조사하고, 8방향 연결에서는 여기에 위-왼쪽과 위-오른쪽 픽셀을 추가한다. 현재 픽셀과 전경 이웃이 연결되어 있으면 두 픽셀이 속한 집합의 root를 찾은 뒤, 하나의 집합으로 합병한다. 예를 들어 두 root 가운데 번호가 작은 쪽이 부모가 되도록 합병할 수 있다.

모든 픽셀을 조사한 뒤의 label 배열은 Union-Find 트리의 parent 정보를 담고 있다. 따라서 각 픽셀의 최종 연결요소를 얻으려면 FIND 연산을 통해 최종 root를 구해야 한다. 이 과정에서 경로 압축(path compression)을 적용하면 이후의 탐색을 빠르게 수행할 수 있다.

각 연결요소에는 하나의 root가 존재하지만, root 번호는 합병 과정 때문에 연속적이지 않을 수 있다. 예를 들어 연결요소의 root 번호가 3, 17, 42로 남을 수 있다. 순차적인 레이블이 필요하면 서로 다른 root에 1, 2, 3, …의 새 번호를 할당한 대응표를 만든 뒤, 각 전경 픽셀의 최종 root를 해당 번호로 변환한다.

이 방법은 연결관계를 구성하기 위한 영상 스캔을 한 번만 수행할 수 있다는 장점이 있다. 다만 모든 픽셀에 최종적이고 연속적인 연결요소 번호를 기록한 레이블 영상을 만들려면, 일반적으로 각 픽셀에 대해 FIND와 번호 변환을 수행하는 추가 순회가 필요하다. 따라서 연결관계의 구성은 한 번의 스캔으로 가능하지만, 완성된 레이블 영상을 생성하는 전체 과정은 구현 방식에 따라 두 번의 픽셀 순회를 포함할 수 있다.

#define CCL_BG           (-1)
static int Find(int v, int* parent) {
    if (v == parent[v]) return v;
    return parent[v] = Find(parent[v], parent);
}
static void Union(int a, int b, int *parent) {
    a = Find(a, parent);
    b = Find(b, parent);
    if (a > b) parent[a] = b;
    else parent[b] = a;
}
int ConnectedComponentLabel(BYTE *image, int w, int h, int label[]) {
    BYTE *q = &image[0] ;
    for (int y = 0, pos = 0; y < h; y++) {
        for (int x = 0; x < w; x++, pos++) {
            if (*q++) {                     // Foreground;
                label[pos] = pos;           // 초기 root = 현위치             
                if ((y > 0) && q[-w]) 
                    Union(pos, pos-w, label);         
                if ((x > 0) && q[-1]) 
                    Union(pos, pos-1, label);
#if defined (_EIGHTCONN_)
                if ((x + 1 < w) && (y > 0) && q[1-w]) 
                    Union(pos, pos+1-w, label);
                if ((x > 0) && (y > 0) && q[-w-1]) 
                    Union(pos, pos-1-w, label);
#endif // _EIGHTCONN_
            } else 
                label[pos] = CCL_BG;        // BACKGROUND;
        }
    }
    // 합병과정에서 빈 레이블이 생길 수 있으므로 순차적 레이블을 같도록 정리(선택 사항);
    // label = -1은 배경임;
    int curlab = 0;                                // 0-부터 시작;
    for (int pos = 0 ; pos < w * h; pos++) {
        int r = label[pos];
        if (r == CCL_BG)   continue;               // background;
        else if (r == pos) label[pos] = curlab++;  // root: assign a new label;
        else               label[pos] = label[r];  // assign renewed parent's label.
    }  
    return (curlab);                               //배경 제외;
};

 

<CCL을 이용하여 DataMatrix-code를 검출하는 과정>

이진화된 QR 코드 이미지

 

<20000 성분의 체스보드에 대한 4-방향 연결 테스트;>

출력은 정수형으로 바꾸어야 한다.  8-방향 연결로 하면 1개 성분만 나온다.

8 방향 연결 조건에서는 1개

<Percolation Experiment>

percolation simulator에 사용된 예: 위쪽이나 아래쪽에서 연결된 경로를 표시했다.