Flood filling C++

Question

I have a problem with implementation of flood filling.
The task is to ask user to click on the white part of the image (indicating seed point), he want to fill with black.
The operation should be done on the binary images.
I'm using CImg library.
I can't use recursive algorithm.
I've came up with something but it is not working properly (the gap becomes black only in the seed point). I am not familiar with the queues at all, so maybe the problem is in their implementaion.

void floodfill(int x, int y, int c, int b, CImg <unsigned char>image)
{
    //c-black
    //b-white
    CImg<unsigned char> kopia(image.width(),image.height());

    for (int p=1; p<image.height()-1; p++)
    {
        for (int q=1; q<image.width()-1; q++)
        {
            kopia(p,q)=255; //setting kopia2 all white
        }
    }

    queue <pair<int,int> > a;
    int p;
    if(image(x, y) == c)
    {
        cout<<"Already black"<<endl;
        return;
    }
    else
    {
        a.push(make_pair(x, y));
        while(!a.empty())
        {
            a.pop();
            p=image(x+1, y);
            if((p == b) && (x < image.width()))
            {
                a.push(make_pair(x+1, y));
                kopia(x+1, y)=c;
                image(x+1, y)=c;
            }
            p = image(x-1, y);
            if((p == c) && (x > 0))
            {
                a.push(make_pair(x-1, y));
                kopia(x-1, y)=c;
                image(x-1, y)=c;
            }
            p=image(x, y+1);
            if((p == b) && (y < image.height()))
            {
                a.push(make_pair(x, y+1));
                kopia(x, y+1)=c;
                image(x, y+1)=c;
            }
            p=image(x, y-1);
            if((p == b) && (y > 0))
            {
                a.push(make_pair(x, y-1));
                kopia(x, y-1)=c;
                image(x, y-1)=c;
            }
        }
        saving(kopia);
    }
}

void hole (CImg <unsigned char>image)
{
    CImgDisplay image_disp(image,"Click a point");

    int c_x=0; //coordinates
    int c_y=0;

    while (!image_disp.is_closed())
    {
        image_disp.wait();
        if (image_disp.button())
        {
            c_x=image_disp.mouse_x();  //reads coordinates indicated by user
            c_y=image_disp.mouse_y();
        }
    }

    floodfill(c_x, c_y,0,255,image);
}

I've got a question, how did you make the code looking like in the compiler (colored types and so on)? — sashafierce, Nov 30 '11 at 01:19
@sashafierce Put four spaces before code or surround in `` or click the code button to get syntax highlighting. — Joe McGrath, Nov 30 '11 at 08:29

Mooing Duck · Accepted Answer · 2011-11-30T00:33:32.593

1

1)

    while(!a.empty())
    {
        x = a.front().first; //fixed as per ChristianRau's code
        y = a.front().second; //fixed as per ChristianRau's code
        a.pop();

You just popped the current x,y coordinates off the stack without looking at what they were.

2)

        p = image(x-1, y);
        if((p == c) && (x > 0))

Did you mean to check if it was white, like you did with the other directions?

3) The caller passes in black and white, what happens if part of the image is blue? Better would be to pass in the filling color (black), and wherever you have white, replace that with not-black.

edited Nov 30 '11 at 00:33

answered Nov 30 '11 at 00:15

Mooing Duck

64,318
19
100
158

ad. 2) yes, it should be if((p == b) && (x > 0)) – sashafierce Nov 30 '11 at 00:22
ad. 3) We have specified images that we can process in this task, and they are binary black and white. – sashafierce Nov 30 '11 at 00:27
1

For safety, I would only use one color anyway. – Mooing Duck Nov 30 '11 at 00:28

score 1 · Answer 2 · answered Nov 30 '11 at 00:18

1

Don't you realize that you are working with the same x and y all the time and that a.pop() doesn't return anything? std::queue::pop only pops the front of the queue, but doesn't return it. You have to query it beforehand using std::queue::front. So just add

x = a.front().first;
y = a.front().second;

right before a.pop() inside the while loop.

And by the way, you might also want to set image(x, y) (and maybe kopia(x, y)) to c at the beginning of the else block before pushing the initial pair, although it might also get set by its neighbours' iterations.

answered Nov 30 '11 at 00:18

Christian Rau

45,360
10
108
185

Thank you so much, that was very helpful! – sashafierce Nov 30 '11 at 00:31
wait, `queue` pops the front? (checks) oops! (fixes answer) – Mooing Duck Nov 30 '11 at 00:34
OK, almost everything is ok. The plane I choose is filled, but not in black colour as I want to, but in blue. I don't have any idea why is that. Any suggestions? – sashafierce Nov 30 '11 at 00:53
it is ok, when I rewrite the black pixels to kopia – sashafierce Nov 30 '11 at 00:57

score 1 · Answer 3 · answered Nov 30 '11 at 08:26

1

Also, there is a built-in function in CImg that does what you want : CImg::draw_fill().

answered Nov 30 '11 at 08:26

Pastiflore

41
2

Flood filling C++

3 Answers3