Binary Image에서 Convex Hull

사진 속에 포함된 물체를 판별하기 위해서는 일반적으로 이미지를 이진화시켜 binary 이미지를 만들고, conneted component labeling 등을 이용하여 영상에서 겹치지 않는 다수의 물체들을 분리해 내는 과정을 거친다. 이렇게 분리된 각 물체의 외각을 감싸는 convex hull을 찾으려면 먼저 물체의 경계를 추적해서 폴리곤을 만들고, 그다음 이 폴리곤의 convex hull을 찾는 알고리즘을 적용하면 된다. 이때 얻어진 폴리곤은 일정한 규칙에 의해서 정렬이 되어 있으므로 convex hull 알고리즘들 중에 chain-hull이나 Melkman 알고리즘 이용하면 빠르게 결과를 얻을 수 있다.

 

Raster-scan 방식은 물체의 경계점들을 일정하게 정렬된 순서로 읽게 되므로 on-site convex hull 찾기가 가능하게 된다 (chain-hull에서도 동일한 순서가 들어오지만, 전체 점들을 다 얻은 다음에 다시 분류작업을 해야 하므로, 읽은 즉시 바로 convex  hull을 구성하는 알고리즘은 제공하지 못한다). 아래의  코드는 binary raster image를 스캐닝하면서 경계의 convex hull을 찾는 과정을 보여준다.

#define bg     0x00             /* foreground color (black) */ 
#define fg     0xFF             /* background color (white) */
//cross(AB, AC) > 0 if C is lying on the left side of edge(AB);
#define CCW(A,B,C) ((B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x))

/* find a convex hull of foreground object in a binary image; */ 
/* in some case L[0] = R[0], or L[ll] = R[rr] if first line or last line of object 
** is composed of a single point (수정본:: 배경 체크 부분);
** convex hull이 중복점을 갖는 경우를 허용하지 않을 때는 comment에 따라서 처리해야 한다.
*/ 
std::vector<CPoint> RasterHull(BYTE *image, int w, int h) {
    std::vector<CPoint> H(2 * h);
    CPoint *L = &H[0]; //stack of left-side hull; 
    CPoint *R = &H[h]; //stack of right side hull; 
    int rr = -1, ll = -1, x; 
    CPoint q; 
    for (int y = 0 ; y < h; y++) {
        BYTE *scanline = &image[y*w]
        for (x = 0; x < w; x++)
            if (scanline[x] != bg) break; 
        if (x == w) continue; 
        q = CPoint(x, y);
        while (ll > 0) {
            // q가 이전 edge의 오른쪽이면 convex hull의 꼭지점이 됨;
            if (CCW(L[ll - 1], L[ll], q) < 0) break; 
            else ll--; 
        } 
        L[++ll] = q; 
        for (x = w; x-- > 0;) //x=-1 never occurs; 
            if (scanline[x] != bg) break; 
        // 행에 싱글 픽셀 있는 경우 왼쪽과 오른쪽이 점이 중복이 되는 경우가
        // 생긴다. 이 중복을 없애고 싶으면
        if (x <= q.x) continue ;
        q = CPoint(x, y); 
        while (rr > 0) { 
            // q가 이전 edge의 왼편에 있으면 convex hull의 꼭지점이 됨;
            if (CCW(R[rr-1], R[rr], q) > 0) break; 
            else rr--; 
        } 
        R[++rr] = q; 
    } 
    // 왼쪽 처음에 점과 오른쪽 처음 점유 중복될 가능성이 있다(싱글 픽셀)
    // 왼쪽 마지막 점과 오른쪽 마지막 점이 중복이 되는 경우도 있다(싱글 픽셀) 
    // convex hull에서 중복점을 완전히 제외하고 싶으면 이를 체크하는 부분이 필요;
    // copy right hull to H;
    int n = ll + 1; // # of pts within left hull;
    // remove bottom degeneracy; 
    if (H[ll] == R[rr]) rr--;
    for (int j = rr; j >= 0; j--) H[n++] = R[j];//right hull; 
    //remove top degeneracy;
    if (n > 1 && H[0] == H[n - 1]) n--;
    H.resize(n);
    return H;
};

위 함수는 픽셀 값이 bg가 아닌 것은 모두 전경으로 처리하도록 작성하였다. Connected component를 구한 상태에서 특정 component의 convex hull을 구하려는 경우에는 if-문의 조건을 image[y * w + x] == index로 바꾸어야 한다 (여기서 index는 connected component label이다. 그리고 labeling 이미지는 일반적으로 정수 이미지이므로 그에 맞게 수정을 해야 한다.) 

 

Data matrix 코드를 포함하는 이미지에서 코드 영역을 찾아 보자. 영상을 이진화시킨 후 connected component labeling을 사용하여 사이즈가 작은 blob을 제거하면 거의 코드 영역만 남길 수 있다. 그림은 코드 영역(yellow)을 감싸는 convex hull(red)을 찾은 것을 보여준다.

네이버 블로그에서 이전

Convex hull 알고리즘은 아래에서 찾을 수 있다.

• Chain hull: kipl.tistory.com/109 
• Quick hull: kipl.tistory.com/108  
• Brute Force Algorithm: kipl.tistory.com/106