Flood-Fill and Connected Component Labeling

Flood-Fill을 이용한 Connected Component Labeling(CCL) 은 이진 영상에서 서로 연결된 픽셀들을 하나의 객체로 식별하여 동일한 레이블(label)을 부여하는 알고리즘이다. Flood-Fill은 한 픽셀에서 시작하여 동일한 값을 갖는 인접 픽셀들을 재귀적 또는 반복적으로 방문하면서 하나의 연결 성분을 모두 탐색하는 방식으로 동작한다.

알고리즘은 영상을 순차적으로 스캔하면서 아직 레이블이 부여되지 않은 객체 픽셀을 발견하면 새로운 레이블을 할당한다. 이후 Depth-First Search(DFS), Breadth-First Search(BFS) 또는 stack, queue를 이용한 Flood-Fill을 수행하여 현재 픽셀과 연결된 모든 픽셀을 방문하고 동일한 레이블을 부여한다. 이 과정을 영상 전체에 대해 반복하면 모든 연결 성분이 서로 다른 레이블을 갖게 된다.

Flood-Fill 기반 CCL은 구현이 직관적이고 연결 관계를 쉽게 파악할 수 있다는 장점이 있다. 특히 객체의 개수가 많지 않거나 영상의 크기가 비교적 작은 경우 효과적이다. 그러나 큰 영상에서는 탐색 과정에서 많은 메모리가 필요할 수 있으며, recursion를 이용한 구현은 스택 오버플로우가 발생할 수 있으므로 실제 구현에서는 명시적인 스택이나 큐를 사용하는 iterative 방식이 주로 사용된다.

// labeling using depth-first search; non-recursive version;
int GetConnectedComponents(BYTE *image, int w, int h, int *table) {
    int label = 0;    // starting label = 1;
    std::vector<int> stack(w * h);
    // initialize the table;
    for (int k = w * h; k-->0;) 
        table[k] = image[k] ? -1: 0;  // Foreground = -1; Background = 0;

    for (int pos = w * h; pos-->0;) {
        if (table[pos] == -1) { // Foreground;
            ++label;            // assign next label;
            int top = -1;       // stack initialization;
            stack[++top] = pos;
            while (top >= 0) {
                int adj = stack[top--];
                int xx = adj % w;
                int yy = adj / w;
                if (table[adj] == -1) {// Foreground;
                    table[adj] = label;
                    // check 4-way connectivity;
                    if (xx + 1 < w) stack[++top] = adj + 1; //RIGHT;
                    if (yy + 1 < h) stack[++top] = adj + w; //BOTTOM;
                    if (yy > 0)     stack[++top] = adj - w; //TOP;
                    if (xx > 0)     stack[++top] = adj - 1; //LEFT;
                }
            }
        }
    }
    return label;    // total # of CCs;
};