Geometry & Recognition

이미지에서 Voronoi diagram으로 영역을 분할할 때 각 픽셀이 어느 Voronoi cell에 포함되는가를 알아야 하는 경우가 있다. 보통은 Voronoi 다이어그램으로 구한 cell을 폴리곤으로 표현하고, 해당 픽셀이 어느 폴리곤에 들어가는 가는 체크 해야 한다. 그러나, 이 과정은 복잡하고 계산이 많이 발생한다. 이미지에 만들어진 Voronoi diagram의 경우 cell mask를 이용하면 해당 픽셀이 어느 cell에 들어있는지를 바로 판단할 수 있다. 특히, cell의 개수가 적은 경우 mask를 gray 이미지로 처리할 수 있어서 메모리 사용도 줄일 수 있다.

Voronoi diagram의 이미지화 과정은 Voronoi 알고리즘을 이용할 필요는 없고 단지 각 cell을 형성하는 픽셀들은 그 cell의 중심까지 거리가 다른 cell보다 가깝다는 사실만 이용한다.

void rasterize_voronoi(std::vector<CPoint>& vorocenter, 
                       BYTE *image, int width, int height) {
    std::vector<BYTE> red(vorocenter.size()), 
                      green(vorocenter.size()), 
                      blue(vorocenter.size());
    for (int i = vorocenter.size(); i-->0;) {
    	red[i]   = rand() % 256;
        green[i] = rand() % 256;
        blue[i]  = rand() % 256;
    }
    for (int y = 0; y < height; y++) {
        for (int x = 0; x < width; x++) {
            int min_id = 0; 
            int dist2_min = INT_MAX;
            for (int k = vorocenter.size(); k-->0;) {
                int dx = x - vorocenter[k].x;
                int dy = y - vorocenter[k].y;
                int dist2 = dx * dx + dy * dy;
                if (dist2 < dist2_min) {
                    dist2_min = dist2;
                    min_id = k;
                }
            }
            *image++ = blue[min_id];
            *image++ = green[min_id];
            *image++ = red[min_id];
        }
    }
    // draw cell center;
}