728x90

사진 속에 포함된 물체를 판별하기 위해서는 보통 이미지를 이진화시켜 binary 이미지를 만들고, conneted component labeling 등을 이용하여 영상에서 겹치지 않는 다수의 물체들을 분리해 낸다. 분리된 물체의 외각을 감싸는 convex hull을 구하기 위해서는 우선 경계점들을 추적하여 폴리곤을 형성한 다음 이들의 convex hull 알고리즘을 이용함으로써 구할 수 있다. convex hull 알고리즘 중에서 chain-hull이나 Melkman 알고리즘은 점들이 일정한 규칙에 의해서 정렬되어 있다는 사실을 이용하여 빠르게 convex hull을 찾을 수 있게 한다.

 

이미지를 읽는 raster-scan 방식은 물체의 경계점들을 일정하게 정렬된 순서로 읽게 되므로(chain-hull에서도 동일한 순서가 들어오지만, 전체 점들을 다 얻은 다음에 다시 분류작업을 해야 하므로, 읽은 즉시 바로 convex  hull을 구성하는 알고리즘은 제공하지 못한다) on-site 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에 따라서 처리해야 한다.
*/ 
int RasterHull(BYTE *image, int w, int h, CPoint H[/* 2xh */]) { 
    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++) { 
        for (x = 0; x < w; x++)
            if (image[y * w + 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 - 1; x >= 0; x--) //x=-1 never occurs; 
            if (image[y * w + 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에서 중복점을 완전히 제외하고 싶으면 이를 체크하는 부분이 필요;
    for (int i = 0; i <= ll; i++) H[i] = L[i]; //left hull;
    // remove bottom degeneracy; 
    if (H[ll] == R[rr]) rr--;
    for (int j = rr; j >= 0; j--) H[i++] = R[j];//right hull; 
    //remove top degeneracy;
    if (i > 1 && H[0] == H[i - 1]) i--;
    return (i); 
};

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

 

data matrix 코드를 포함하는 이미지를 이진화시킨 후 connected component labeling을 하여 작은 blob을 제거하면 거의 코드만 남길 수 있다. 그 후 위의 알고리즘으로  convex hull(붉은색 라인)을 구성한 것을 보인 것이다.

C네이버 블로그에서 이전

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

Posted by helloktk

댓글을 달아 주세요