Geometry & Recognition

이진 영상에서 전경의 경계를 저장하는 함수다. 전경의 최외각을 8-방향 연결성을 체크하면서 추적하도록 설계되었다(chain code를 참조하면 된다). 전경의 두께가 1 픽셀이더라도 항상 닫힌 윤곽선을 형성하게 만들었다(다르게 행동하도록 바꿀 수 있다). 전경에 서로 연결되지 않은 blob가 여러 개 있는 경우도 쉽게 처리할 수 있게 출력은 벡터 컨테이너를 사용했다.

struct Cntr {
   int x, y ; //position;
   int idirn ;//chain-code;
   Cntr() {} 
   Cntr(int x_, int y_, int idirn_)  : x(x_), y(y_), idirn(idirn_){}
};
typedef std::vector<Cntr> CntrVector;
#define FGVAL   255
#define BGVAL   0
#define VISITED 33          /* pixel value on accepted contour */
int GetNextCntr (BYTE** image, int *x, int *y, int *idirn);

int ContourTrace (BYTE** image/*binary image(FGVAL,BGVAL)*/, int width, int height,
                 std::vector<CntrVector* > &CntList) {
    /* CAUTION:: one-pixel border should have BGVAL!!!!*/
    for (int x = width; x-->0;)  image[0][x] = image[height-1][x] = BGVAL;
    for (int y = height; y-->0;) image[y][0] = image[y][width-1] = BGVAL;
    
    for (int y = height-1; y-->1;) {
        for (int x = width-1; x-->1;) {
            if (image[y][x] == FGVAL && image[y][x - 1] == BGVAL) {
                CntrVector *pCntrVec = new CntrVector ;
                int idirn = 2;
                int xStart = x, yStart = y;
                pCntrVec->push_back(Cntr(x, y, idirn));
                do {
                    image[y][x] = VISITED;  /* set the default value to VISITED */
                    GetNextCntr (image, &x, &y, &idirn);
                    pCntrVec->push_back(Cntr(x, y, idirn));
                } while (!(x == xStart && y == yStart));
                CntList.push_back(pCntrVec);
            }
        }
    }
    return CntList.size();
};

/* 다음 픽셀을 검사. 체인 코드; */
int GetNextCntr (BYTE** image, int *x, int *y, int *idirn);

더보기

void GetNextCntr (BYTE** image, int *x, int *y, int *idirn) {
    /*idirn::direction from last pixel on contour */                 
    int i, j;
    BYTE ring[16];
    /* find neighborhood ring of pixels */
    ring[0] = ring[ 8] = image[*y - 1][*x    ];
    ring[1] = ring[ 9] = image[*y - 1][*x + 1];
    ring[2] = ring[10] = image[*y    ][*x + 1];
    ring[3] = ring[11] = image[*y + 1][*x + 1];
    ring[4] = ring[12] = image[*y + 1][*x    ];
    ring[5] = ring[13] = image[*y + 1][*x - 1];
    ring[6] = ring[14] = image[*y    ][*x - 1];
    ring[7] = ring[15] = image[*y - 1][*x - 1];
    
    i = (*idirn + 4 + 1) % 8;
    if (i == 0) i = 8;              /* this never happens */
    for (j = 0; j < 8; j++, i++)
        if (ring[i] != BGVAL && ring[i - 1] == BGVAL) break;

    if (j == 8) return;         /* isolated pixel */
    *idirn = i % 8;
    
    switch (i) {
    case 1:
    case 9:
        *x = *x + 1; *y = *y - 1;
        break;
    case 2:
    case 10:
        *x = *x + 1;
        break;
    case 3:
    case 11:
        *x = *x + 1; *y = *y + 1;
        break;
    case 4:
    case 12:
        *y = *y + 1;
        break;
    case 5:
    case 13:
        *x = *x - 1; *y = *y + 1;
        break;
    case 6:
    case 14:
        *x = *x - 1;
        break;
    case 7:
    case 15:
        *x = *x - 1; *y = *y - 1;
        break;
    case 8:
    case 0:
        *y = *y - 1;
        break;
    default:
        break;
    }    
};

MFC를 써서 폴리곤의 내부를 칠하기 위해서는 윈도  GDI region을 다루는  CRgn  클래스의 CRgn::CreatePolygonRgn() 메쏘드를 써서 해당 폴리곤으로 bound 된 영역을 만든 이후에 CDC::FillRgn() 함수를 이용하여서 원하는 색으로 칠할 수 있다. 직접  raster에 칠하려고 할 때는 이러한 방법이 너무 불편하다 (물론 라스터(DIB)를 윈도 비트맵으로 변환한 후에 위의 방법대로 칠하고, 다시 윈도 비트맵을 라스터로 바꾸는 작업을 하면 되는데 번거롭다).

쉽게 생각할 수 있는 방법은  point_in_polygon()  방법을 써서 각각의 픽셀이 주어진 폴리곤 내부점인지를 확인하면서 작업을 할 수 있다. 그러나 이 방법은 한 픽셀을 검사하기 위해서 주어진 폴리곤의 모든 에지를 다 건들어야 하는 낭비를 하게 된다. 보다 효율적인 방법은 point_in_polygon 알고리즘을 구현할 때 사용하는 원리를 이용하면 적어도 한 스캔라인의 모든 픽셀에 대해서는 딱 한 번만 전체 폴리곤의 에지를 검사하게 만들 수 있다. inclusion 테스트는 해당점에서 출발하는 수평 반직선이 폴리곤과 몇 번 교차하는지를 세서 내부점인지 외부점인지를 판별한다. 이것을 생각하면 수평선이 폴리곤과 교차하는 점들을 모두 구하여서(한번 폴리곤의 전체 에지 검사가 필요) 크기의 순서대로 정렬할 때, 짝수번째 구간(0->1, 2->3,.....)에 들어가는 스캔라인의 픽셀들은 모두 폴리곤의 내부점이 된다는 것을 알 수 있다.

알고리즘 순서:

1. 각각의 스캔라인에 대해서 교차점들을 구한다:
   꼭짓점 i와 꼭짓점 j(=i-1)를 연결하는 직선의 방정식이 x = x[i] + (x[j] - x[i])*(y - y[i]) / (y[j] - y[i]) 이므로 현재의 scanline 위치에서 y값이 두 꼭지점의 y값 (y[i], y[j]) 사이에 있으면, 교차점의 x-좌표는 윗식의 좌변 값이 된다.
2. 교차점들을 크기의 순서대로 정렬한다.
3. 짝수번째 구간에 들어가는 스캔라인상의 픽셀들은 해당 색깔로 칠한다.

/*sample code;*/
void FillPolygon(const std::vector<CPoint>& poly,
                 DWORD color,
                 BYTE *image, int width, int height, int bpp) {
    std::vector<int> nodeX(poly.size()); //never exceeds npoly;
    for (int y = 0; y < height; y++) {
        // find intersection nodes;
        int nodes = 0;
        for (int i = 0, j = poly.size()-1; i < poly.size(); j = i++)
            if (poly[i].y < y && poly[j].y >= y || poly[j].y < y && poly[i].y >= y) {
                // 수평인 에지는 그리지 않는다(부등식을 자세히 보라)
                nodeX[nodes++] = (int)(poly[i].x + double(y - poly[i].y) * double(poly[j].x \
                                 - poly[i].x) / double(poly[j].y - poly[i].y) + .5); 
                                 // round to integer!!.
            }
            
        // sort nodes (ascending order);
        std::sort(nodeX.begin(), nodeX.begin() + nodes);
        // fill the pixels between node pairs.
        for (int i = 0; i < nodes; i += 2) {
            if (nodeX[i + 0] >= width) break;
            if (nodeX[i + 1] > 0) {
                if (nodeX[i + 0] < 0)     nodeX[i + 0] = 0 ;
                if (nodeX[i + 1] > width) nodeX[i + 1] = width;
                for (int x = nodeX[i]; x < nodeX[i + 1]; x++) 
                    SetPixel(x, y, color, image, width, height, bpp); 
                    //SetPixel()은 다른 프로토타입을 가질 수 있다.
            }
        }
    } 
};

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