Tarjan의 Union-Find algorithm을 이용한 이미지상의 Connected Component Labeling 코드이다. 이미지의 배경은 검정(0)으로 하고 전경은 0이 아닌 값이면 된다. 
이 코드 자체는 좀 더 최적화를 시킬 수 가 있다. 예를 들면, 4-방향연결에서 LEFT와 TOP이 전경이면, 이 코드에서는 UNION을 두 번 호출한다. 그러나 생각해보면, 현위치의 라벨링을 LEFT와 같게 만들고 TOP과 UNION을 한 번만 호출하여도  TOP, LEFT,  현위치가 같은 parent를 갖음을 알 수 있다.

 

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

#define CCL_BG            (-1)

 

#define UNION(x, y, label) {                    \
    int r0 = (x), r1 = (y), p;                        \
    while((p = label[r0]) != r0) { r0 = p; }    \
    r0 = p ;                                              \
                                                            \
    while((p = label[r1]) != r1) { r1 = p; }     \
    r1 = p ;                                              \
    if (r0 > r1)  label[r0] = r1;                     \
    else          label[r1] = r0;                     \
}                  

// #include <vector>  
int ConnectedComponentLabel(BYTE *image, int w, int h, int *out)
{
    /* 
    ** Computes "Connected Components" using Tarjan's Union-Find algorithm;
    ** the result is returned in the same buffer as gray_level image with values
    ** equal to the label of the component.
    ** Returns: the number of connected components 
    */

    /* if image !=0, it's FG */

    std::vector<int> label(w * h) ; 
    BYTE *q = &image[0] ;
    for (int i = 0, curpos = 0; i < h; i++) {
        for (int j = 0; j < w; j++, q++, curpos++) {
            if (*q) {
                label[curpos] = curpos;             
                if ((i > 0) && q[CCL_TOP]) {
                    UNION(curpos, curpos + CCL_TOP, label);         
                }
                if ((j > 0) && q[CCL_LEFT]) {
                    UNION(curpos, curpos + CCL_LEFT, label);
                }
#if defined (_EIGHTCONN_)
                if ((j+1 < w) && (i > 0) && q[CCL_TOPRIGHT]) {
                    UNION(curpos, curpos + CCL_TOPRIGHT, label);
                }
                if ((j   > 0) && (i > 0) && q[CCL_TOPLEFT]) {
                    UNION(curpos, curpos + CCL_TOPLEFT, label);
                }
#endif // _EIGHTCONN_
            }      
            else {
                label[curpos] = CCL_BG;     //BACKGROUND;
            }
        }
    }
    int curlab = 1; //출력용.1부터 시작한다; 0 은 bg;

    /* 라벨을 순차적으로 정리한다; 출력을 정수형으로 하는 경우에는 실제로 out이 필요없고, 

    ** label를 그대로 내보내도 된다. 단, CCL_BG 값을 갖는 픽셀을 0 으로 처리해야 한다;*/
    for (int pos = 0 ; pos < w * h; pos++) {
        int r = label[pos];
        if (r == CCL_BG ) {         // background ;
            out[pos] = 0;
        }
        else if (r == pos) {
            out[pos]  = curlab;
            label[pos] = curlab++;
        } 
        else { 
            label[pos] = label[r];
            out[pos]  = label[r];
        }
    }  
    return (curlab-1);
} ;

//http://blog.naver.com/helloktk/80026521024 에서 옮김.

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

 

 


20000 성분의 체스보드에 대한 4-방향 연결테스트; 출력은 정수형으로 바꾸어야 한다; 물론 8-방향 연결로 하면 1개 성분만 나온다.

 

 

Posted by helloktk