이미지에서 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;
}
728x90
'Image Recognition' 카테고리의 다른 글
| EM Algorithm: Line Fitting (0) | 2008.06.29 |
|---|---|
| Gaussian Mixture Model (2) | 2008.06.07 |
| RANSAC Algorithm (0) | 2008.05.24 |
| Contour Tracing (0) | 2008.05.22 |
| Gausssian Scale Space (0) | 2008.05.22 |
