현재 위치

홈 ›› Forums ›› 공부 ›› 프로그래밍 QnA

이미지에서 동일한 색깔의 픽셀을 순회하는 방법?

lacovnk의 이미지
글쓴이: 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: 
프로그래밍 QnA
tinywolf의 이미지

글쓴이: tinywolf / 작성시간: 토, 2005/10/22 - 7:12오후

예전에 재귀적으로 구현된 정점 페인트 알고리즘이라 비슷하군요..
그때 자바의 함수 스택 깊이가 한참 모자라서 이터레이티브하게 바꿨었는데..
지금은 기억이 안나므로 패스!

ㅡ_ㅡ;

아르아의 이미지

글쓴이: 아르아 / 작성시간: 토, 2005/10/22 - 9:34오후

이런방법은 어떨까요. 스텍에 방문할곳을 쌓아두면서 방문하는 방법입니다

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));
    // 왼쪽, 위, 오른쪽에도 동일하게
}

스택대신 링크드리스트를 쓰는 방법도 있겠네요.
이경우 스택의 최대길이를 어떻게 잡느냐
(메모리 문제가 안된다면 그냥 그림크기만큼 잡아버림 되겟죠)
하는 문제는 생각 안해도 되니까요
lacovnk의 이미지

글쓴이: lacovnk / 작성시간: 금, 2005/11/04 - 4:37오후 

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일 경우 일치하게 해 주는 부분이 얼마나 걸릴지 모르겠네요. (으으)

lifthrasiir의 이미지

글쓴이: lifthrasiir / 작성시간: 토, 2005/11/05 - 6:58오전

위키백과를 참고하세요. 보통 일반적인 Flood fill을 하면서 가로로 최대한 확장하는 방법을 쓰는 것 같습니다. (세로로 확장할 수도 있는데 일반적으로 이미지는 가로로 배열하니까...)

- 토끼군

둘러보기