이미지에서 동일한 색깔의 픽셀을 순회하는 방법?
글쓴이: lacovnk / 작성시간: 토, 2005/10/22 - 12:48오후
이미지에서, 동일한 색깔의 픽셀을 순회하는 방법을 찾고 있습니다.
(대각선은 가지 않는다고 가정하지요~)
visit(pixel(x,y)) - (x,y)의 pixel과 같은 색깔을 순회하는 함수
visit(pixel(x,y))
{
if(아래것과 색깔 같으면) visit(pixek(x,y+1);
// 왼쪽, 위, 오른쪽에도 동일하게
}
그러나 이렇게 하면 갔던 녀석을 또 갈테니..
visit(pixel(x,y)) - (x,y)의 pixel과 같은 색깔을 순회하는 함수
visit(pixel(x,y))
{
if(!flag)
{
set flag on pixel(x,y)
if(아래것과 색깔 같으면) visit(pixek(x,y+1);
// 왼쪽, 위, 오른쪽에도 동일하게
}
else return;
}
이렇게 하면 해결이 되겠지요? 음음. (과..과연)
그런데, recursive하지 않게 이 문제를 해결할 수 있는 방법은 없을까요? 궁금합니다. 어떻게 보면 굉장히 얽힌 graph문제 같은데..
Forums:
예전에 재귀적으로 구현된 정점 페인트 알고리즘이라 비슷하군요..그때
예전에 재귀적으로 구현된 정점 페인트 알고리즘이라 비슷하군요..
그때 자바의 함수 스택 깊이가 한참 모자라서 이터레이티브하게 바꿨었는데..
지금은 기억이 안나므로 패스!
ㅡ_ㅡ;
이런방법은 어떨까요. 스텍에 방문할곳을 쌓아두면서 방문하는 방법입니다
이런방법은 어떨까요. 스텍에 방문할곳을 쌓아두면서 방문하는 방법입니다
set startpoint = (x,y); if(아래것과 색깔 같으면) push_point((x,y+1)); // 왼쪽, 위, 오른쪽에도 동일하게 while(stack_length!=0){ pop_point(); set flag on current point; if(아래것과 색깔 같으면) if((x,y+1) is not set flag) //(그 아래것이)방분해본적이 없는 점이면 push_point((x,y+1)); // 왼쪽, 위, 오른쪽에도 동일하게 }스택대신 링크드리스트를 쓰는 방법도 있겠네요.
이경우 스택의 최대길이를 어떻게 잡느냐
(메모리 문제가 안된다면 그냥 그림크기만큼 잡아버림 되겟죠)
하는 문제는 생각 안해도 되니까요
음. 참고로 파티셔닝하는 방법을 둡니다.
int count_partition_color(const Image& image,bool checkBlack) { const int MAX_PARTITION = count_nonWhitePixel(image); int label_ref[MAX_PARTITION]; for(int i=0;i<MAX_PARTITION;i++){label_ref[i] = 0;} // init label int label[image.getWidth()][image.getHeight()]; for(unsigned int y=0;y<image.getHeight();y++){for(unsigned int x=0;x<image.getWidth();x++){label[x][y] = -1;}} int number_of_label = 0; for(unsigned int y=0;y<image.getHeight();y++) { for(unsigned int x=0;x<image.getWidth();x++) { if(true == checkBlack) { if(true == pixelIsWhite(image.getPixel(x,y))){continue;} } else { if(false == pixelIsWhite(image.getPixel(x,y))){continue;} } int label_up = -1; int label_left = -1;; if(y > 0){label_up = label[x][y-1];} if(x > 0){label_left = label[x-1][y];} // both is not labeled if(-1 == label_up && -1 == label_left) { label[x][y] = number_of_label; label_ref[number_of_label] = number_of_label; number_of_label++; } // only one is labeled else if((-1 == label_up && -1 != label_left) || (-1 != label_up && -1 == label_left)) { label[x][y] = (label_up == -1)?(label_ref[label_left]):(label_ref[label_up]); } // both is labeled else { // same label if(label_ref[label_up] == label_ref[label_left]) { label[x][y] = label_ref[label_up]; } // different label else { int target = MIN(label_ref[label_up],label_ref[label_left]); // update other label_ref for(int k=0;k<number_of_label;k++) { if(label_ref[k] == label_ref[label_up] || label_ref[k] == label_ref[label_left] || label_ref[k] == label_up || label_ref[k] == label_left){label_ref[k] = target;} } label[x][y] = label_ref[label_up] = label_ref[label_left] = target; } } } } // if you want to see label... uncomment below part /* for(unsigned int y=0;y<image.getHeight();y++) { for(unsigned int x=0;x<image.getWidth();x++) { label[x][y] = label_ref[label[x][y]]; printf("%2d",label[x][y]); } cout << endl; } */ int result = 0; for(int i=0;i<number_of_label;i++){if(label_ref[i] == i){result++;}} return result; }label을 불여서 partitioning을 했습니다. 이후, 색칠할 픽셀과 같은 파티션인 녀석만 칠해주면 되겠지요~
대략 언뜻 O(n^2)는 넘는 것 같은데.. 다른 label일 경우 일치하게 해 주는 부분이 얼마나 걸릴지 모르겠네요. (으으)
Re: 이미지에서 동일한 색깔의 픽셀을 순회하는 방법?
위키백과를 참고하세요. 보통 일반적인 Flood fill을 하면서 가로로 최대한 확장하는 방법을 쓰는 것 같습니다. (세로로 확장할 수도 있는데 일반적으로 이미지는 가로로 배열하니까...)
- 토끼군
댓글 달기