#define insideROI(x, y) ((x) >= 0 && (x) < w && (y) >= 0 && (y) < h)
#define BACKGND 0xFF
int watershed(float *distMap, int w, int h, int *rgnMap) {
const int xend = w - 1, yend = h - 1;
const int nx[] = {-1, 0, 1, -1, 0, 1, -1, 0, 1};
const int ny[] = {-1, -1, -1, 0, 0, 0, 1, 1, 1};
// processing image;
std::vector<float> wbuffer(w * h);
std::vector<float* > procImg(h);
for (int y = 0; y < h; y++)
procImg[y] = &wbuffer[y * w];
// presmooth; 10 iterations;
mean_filter(distMap, w, h, 10, procImg);
// 입력 영상에서 경계는 global maximum으로 설정;
for (int y = 0; y < h; y++ ) procImg[y][0] = procImg[y][xend] = BACKGND;
for (int x = 0; x < w; x++ ) procImg[0][x] = procImg[yend][x] = BACKGND;
// find local minima for each pixel;
int minCnt = 1;
for (int y = 0, pos = 0; y < h; y++) {
for (int x = 0; x < w; x++, pos++) {
float minVal = procImg[y][x];
if (minVal == BACKGND) {
rgnMap[pos] = 1; // background(white);
continue;
}
int minIdx = 4; //current position;
for (int k = 0; k < 9; k++) {
int xx = x + nx[k], yy = y + ny[k];
if (insideROI(xx, yy) && procImg[yy][xx] <= minVal) {
minVal = procImg[yy][xx];
minIdx = k;
}
}
if (minIdx == 4) rgnMap[pos] = ++minCnt; // center(x, y) is a new local minimum;
else rgnMap[pos] = -minIdx; // direction of local-min = "-(dir)"
}
}
// follow gradient downhill for each pixel;
// reset rgnMap to have the id's of local minimum connected with current pixel;
for (int y = 1, pos = y * w; y < yend; y++ ) {
pos++;
for (int x = 1; x < xend; x++, pos++ ) {
int minpos = pos;
while ( rgnMap[minpos] <= 0 ) { //it is not a local minimum.
switch ( rgnMap[minpos] ) {
case 0: minpos += -w - 1; break; // top-lef = downhill direction;
case -1: minpos += -w; break; // top
case -2: minpos += -w + 1; break; // top-right;
case -3: minpos--; break; // left;
case -5: minpos++; break; // right;
case -6: minpos += w - 1; break; // bot-left;
case -7: minpos += w; break; // bot;
case -8: minpos += w + 1; break; // bot-right;
}
}
// speed-up: use a stack to record downhill path.
//assign the id of a local min connected with current pixel;
rgnMap[pos] = rgnMap[minpos];
}
pos++;
}
// rgnMap는 각 픽셀과 연결되는 국소점의 id을 알려주는 lookup table이다;
return ( minCnt );
}
(1) cell image : 원본 영상을 이진화(Otsu-알고리즘)시킨 결과다. 두 군데서 셀이 겹쳤다. 단순히 connected component labeling을 적용해서는 이를 분리할 수 없다.
(2) distance transform : distance 변환 결과에 blurring을 추가한 결과다. distance 변환은 셀 외부는 셀로부터의 거리를, 셀 내부는 배경으로부터의 거리의 음의 값을 취한 후 전체적으로 다시 리스케일한 것이다. blurring은 watershed 알고리즘이 보다 정확히 동작하는데 필요하다.
(3) watershed segmentation: 분할된 영역의 label이 나온다(경계 label=0). 이 label을 가지고 false coloring을 한 결과다. 이 알고리즘은 논문 "The Watershed Transform: Definitions, Algorithms and Parallelization Strategies", Jos B.T.M. Roerdink and Arnold Meijster의 내용을 구현한 것이다. 8-방향 픽셀 연결성을 이용했다.
(4) final result; watershed 결과를 mask로 이용해서 이미지를 분할한 것이다. 겹친 cell이 분리되었다.
