Geometry & Recognition

$$\text{distance measure}:~\text{Manhattan distance}=|x_2 - x_1 | + |y_2 - y_1|$$

Grassfire 알고리즘을 써서 최단경로를 찾는 문제는 DFS로도 구현할 수 있으나 비효율적이고(왜 그런지는 쉽게 알 수 있다) BFS로 구현하는 것이 더 적합하다. 

void grassfire(CPoint q, int **map, int w, int h, int **dist) {
    // left-top-right-bottom;
    const int dx[] = {-1,  0, 1, 0};
    const int dy[] = { 0, -1, 0, 1};
    for (int y = 0; y < h; y++) 
        for (int x = 0; x < w; x++) 
            dist[y][x] = INF;  //unvisited cells;

    std::queue<CPoint> Q;
    dist[q.y][q.x] = 0;     //start( or end) position: distance = 0;
    Q.push(q);
    while (!Q.empty()) {
        CPoint p = Q.front(); Q.pop();
        int distance = dist[p.y][p.x];
        // 4-way search;
        for (int i = 0; i < 4; i++) {
            CPoint q = CPoint(p.x + dx[i], p.y + dy[i]);
            if (q.x < 0|| q.y < 0|| q.x >= w|| q.y >= h) continue;
            if (map[q.y][q.x] == 0 && dist[q.y][q.x] == INF) {
                dist[q.y][q.x] = distance + 1;
                Q.push(q);
            }
        }
    }
};
// back tracking;
CPoint back_track(CPoint p, int **dist, int w, in h) {
    // left-top-right-bottom;
    const int dx[] = {-1,  0, 1, 0};
    const int dy[] = { 0, -1, 0, 1};
    int depth = dist[p.y][p.x]; 
    if (--depth < 0) return p;
    for (int i = 0; i < 4; i++) {
        CPoint q = CPoint(p.x + dx[i], p.y + dy[i]);
        if (q.x < 0 || q.y < 0 || q.x >= w || q.y >= h) continue; // out of ROI;
        else if (dist[q.y][q.x] == depth)
            return q;
    }
    return p; // never hit;
}

// 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;
};

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_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를 검출하는 과정>

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

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

<Percolation Experiment>