Tarjan의 Union-Find algorithm을 이용해서 (이진) 이미지의 Connected Component Labeling을 구현한 코드이다. 이미지의 배경은 검정(0)으로 하고 전경은 0이 아닌 값이면 된다. 처음 각 전경에 해당하는 픽셀은 모두 root node로 만든다: parent 정보는 배열 label에 저장되고, root node에 대해서는 label[pos] = pos). 4방향 연결을 기준으로 하면 왼쪽(LEFT)이나 위쪽(TOP)의 픽셀과 연결이 되어 있으면 parent가 더 작은 root 번호를 갖도록 합병한다(UNION).  8-방향 연결인 경우에는 위-왼쪽(TOPLEFT), 위-오른쪽(TOPRIGHT)도 합병한다. 전체 픽셀에 대해서 조사가 끝나면 배열 label에는 각 픽셀의 root 번호가 저장된다. 자신의 위치 값이 label의 값과 같은 경우는 root 노드로 새로운 blob의 시작을 나타낸다.  label 배열에 기록된 root 번호는 합병과정에서 중간 번호가 빠질 수 있을 수 있다. 순차적 레이블링이 필요한 경우에는 배열 label을 다시 스캔해서 번호가 순차적으로 할당되도록 만든다. 

보통의 connected component labeling 알고리즘이 이미지를 두 번 스캔을 해야 하는데 반해 이 알고리즘은 한 번의 스캔만 필요하다. 물론 순차적인 레이블링을 원하면 parent table을 다시 조사해야 한다.

 

#define CCL_LEFT         (-1)
#define CCL_TOP          (-w)
#define CCL_TOPLEFT      (-1 - w)
#define CCL_TOPRIGHT     (1 - w)

#define CCL_BG            (-1)
// 두 노드 (a,b)를 합병함; find(and compress)와 union을 동시에;
#define UNION(a, b, label) {                    \
    int r0 = (a), r1 = (b), p;                  \
    while ((p = label[r0]) != r0) { r0 = p; }   \
    label[(a)] = p;                             \
    while ((p = label[r1]) != r1) { r1 = p; }   \
    label[(b)] = p;                             \
    if (r0 > r1)  label[r0] = r1;               \
    else          label[r1] = r0;               \
}                  
static int FindRoot(int node, int* parent) {
    if (node != parent[node]) parent[node] = FindRoot(parent[node], parent);
    return parent[node];
}
static void Union(int node1, int node2, int *parent) {
    int root1 = FindRoot(node1, parent);
    int root2 = FindRoot(node2, parent);
    if (root1 > root2) parent[root1] = root2;
    else parent[root2] = root1;
}
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[CCL_TOP]) 
                    UNION(pos, pos + CCL_TOP, label);         
                if ((x > 0) && q[CCL_LEFT]) 
                    UNION(pos, pos + CCL_LEFT, label);
#if defined (_EIGHTCONN_)
                if ((x + 1 < w) && (y > 0) && q[CCL_TOPRIGHT]) 
                    UNION(pos, pos + CCL_TOPRIGHT, label);
                if ((x > 0) && (y > 0) && q[CCL_TOPLEFT]) 
                    UNION(pos, pos + CCL_TOPLEFT, 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);                               //배경 제외;
};

blog.naver.com/helloktk/ 에서 옮겼고, 출력 부분을 바꿈;

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

이진화된 QR 코드 이미지

 

connected component labeling with colors

 

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

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

 

8 방향 연결 조건에서는 1개
4 방향 연결 조건에서는 W * H / 2개
percolation simulator에 사용된 예: 위쪽이나 아래쪽에서 연결된 경로를 표시했다.

 

 

728x90
Posted by helloktk
,