set zero for inside of a curve

[anhnha]

I am doing some C++ code relating to image processing.
Here is a picture of an image (let's assume it is a gray image). Each small rectangle here is an pixel and it has a value from 0 to 255.
http://postimg.org/image/58axkgy41/

Now I want to set the value of all pixels inside the yellow line to zero.
Assuming that I already know the coordinate of all yellow pixels and their coordinates are stored in an array.

Could you suggest me how to do that in C++? Note that the yellow line here is just
an example. I only know the coordinate of them from that array.

[Peter87]

Have a look at the flood fill algorithm.

http://en.wikipedia.org/wiki/Flood_fill

[anhnha]

Thanks! I am studying and coding for this algorithm. Also, I need some help later.

[anhnha]

I got some problem doing that algorithm.
I used the code here to do that.
http://www.cglabprograms.com/2008/10/boundary-fill-algorithm-fills-region.html

With small boundary such as rectangle (2318, 895, 2331, 910) it runs OK but with large
rectangle ( 2240, 881, 2342, 932) the error "stack overflow exception (0xC00000FD)" comes up.
I tried to increase Stack Reserve Size in Visual Studio 2010 but still crash.
I am using Windows 7 32 bits, RAM 2G.
How can I solve this problem???

[Peter87]

You probably should not implement it as a recursive function because that will use too much stack space. Instead add the coordinates that you call boundary_fill on to a container of some sort, and run a loop as long as the container is not empty.

You might also want to have a look at the alternative implementations:
http://en.wikipedia.org/wiki/Flood_fill#Alternative_implementations

[anhnha]

Thanks for help. I will try that tonight.
By the way, is it possible to fill all region INCLUDING boundary with flood fill?

[anhnha]

I just did the stack based algorithm. It is OK now but really too slow (about 18s with large boundary).
How can I reduce the time?

[Peter87]

Not sure... but have you implemented the optimized version (the second pseudocode block under Alternative implementations)? Make sure you have compiled the program with optimizations turned on. If it's still too slow, use a profiler to see where your program is spending most time and try to optimize those parts.

[anhnha]

Hi, the first time I used recursive algorithm and the error stack overflor. Then I converted from recursion to iteration. It works with large block of image but too slow.
Tonight, I will try that one you mentioned above. It looks complicated and I need more time to study it.
By the way, I see that paint do that flood fill very very fast. What is the algorithm in paint?

PS: I see that the instruction push
in stack takes a lot of time (about 35ms). So the execute time is very large.

[Peter87]

35 ms sounds too much. What kind data structure do you use for the stack?

[anhnha]

Morning,

I referred to the code at the bottom of this page to convert from recursion to iteration.
http://stackoverflow.com/questions/23031087/stack-overflow-error-when-filling-a-shape-with-boundary-fill-algorithm

Here is part of it:

std::stack<CPoint> points;
	CPoint initialPt(initialX, initialY);

	   points.push(initialPt);

           while(!points.empty()) {

        CPoint currentPoint = points.top();
        int x = currentPoint.x;
        int y = currentPoint.y;
		points.pop();
		
		
			COLORREF RGB = getpixel( x, y);
	     
  	 
   if ((getpixel(x, y) != 0) && (x>=x0)&&(x <=x1)&& (y>= y0)&&(y <=y1)) {

	CPoint pt1(x + 1, y);
	CPoint pt2(x - 1, y);
	CPoint pt3(x, y-1);
	CPoint pt4(x, y+1);
	putpixel(x, y);
	points.push(pt1);
	points.push(pt2);
	points.push(pt3);
	points.push(pt4);

    }
	}

[anhnha]

Is there other kind of stack that is much faster than the one above?

[Peter87]

You could try using a vector as the underlying container instead of a deque but I don't think there will be much of a difference.

std::stack<CPoint,std::vector<CPoint>> points;

You are sure it's the stack operations that takes up most of the time and not getpixel/putpixel? On the wiki page they describe an optimized version that doesn't push as much to the stack. I think you should have a look at it.

[anhnha]

Hi, I will try that now.
I tested that instructions, functions below:
1. push : 35ms
2. Get/Set pixel = 1us.

I tried that line at it gave an error: expect a declaration.

[Peter87]

What do you use to measure the speed?

I tried that line at it gave an error: expect a declaration.

Make sure you have included <vector>

[anhnha]

I have just trie. Heckbert algorithm and some errors:

/*
 * A Seed Fill Algorithm
 * by Paul Heckbert
 * from "Graphics Gems", Academic Press, 1990
 *
 * user provides pixelread() and pixelwrite() routines
 */

/*
 * fill.c : simple seed fill program
 * Calls pixelread() to read pixels, pixelwrite() to write pixels.
 *
 * Paul Heckbert	13 Sept 1982, 28 Jan 1987
 */

typedef struct {		/* window: a discrete 2-D rectangle */
    int x0, y0;			/* xmin and ymin */
    int x1, y1;			/* xmax and ymax (inclusive) */
} Window;

typedef int Pixel;		/* 1-channel frame buffer assumed */

Pixel pixelread();

typedef struct {short y, xl, xr, dy;} Segment;
/*
 * Filled horizontal segment of scanline y for xl<=x<=xr.
 * Parent segment was on line y-dy.  dy=1 or -1
 */

#define MAX 10000		/* max depth of stack */

#define PUSH(Y, XL, XR, DY)	/* push new segment on stack */ \
    if (sp<stack+MAX && Y+(DY)>=win->y0 && Y+(DY)<=win->y1) \
    {sp->y = Y; sp->xl = XL; sp->xr = XR; sp->dy = DY; sp++;}

#define POP(Y, XL, XR, DY)	/* pop segment off stack */ \
    {sp--; Y = sp->y+(DY = sp->dy); XL = sp->xl; XR = sp->xr;}

/*
 * fill: set the pixel at (x,y) and all of its 4-connected neighbors
 * with the same pixel value to the new pixel value nv.
 * A 4-connected neighbor is a pixel above, below, left, or right of a pixel.
 */

void fill(x, y, win, nv)
int x, y;	/* seed point */
Window *win;	/* screen window */
Pixel nv;	/* new pixel value */
{
    int l, x1, x2, dy;
    Pixel ov;	/* old pixel value */
    Segment stack[MAX], *sp = stack;	/* stack of filled segments */

    ov = pixelread(x, y);		/* read pv at seed point */
    if (ov==nv || x<win->x0 || x>win->x1 || y<win->y0 || y>win->y1) return;
    PUSH(y, x, x, 1);			/* needed in some cases */
    PUSH(y+1, x, x, -1);		/* seed segment (popped 1st) */

    while (sp>stack) {
	/* pop segment off stack and fill a neighboring scan line */
	POP(y, x1, x2, dy);
	/*
	 * segment of scan line y-dy for x1<=x<=x2 was previously filled,
	 * now explore adjacent pixels in scan line y
	 */
	for (x=x1; x>=win->x0 && pixelread(x, y)==ov; x--)
	    pixelwrite(x, y, nv);
	if (x>=x1) goto skip;
	l = x+1;
	if (l<x1) PUSH(y, l, x1-1, -dy);		/* leak on left? */
	x = x1+1;
	do {
	    for (; x<=win->x1 && pixelread(x, y)==ov; x++)
		pixelwrite(x, y, nv);
	    PUSH(y, l, x-1, dy);
	    if (x>x2+1) PUSH(y, x2+1, x-1, -dy);	/* leak on right? */
skip:	    for (x++; x<=x2 && pixelread(x, y)!=ov; x++);
	    l = x;
	} while (x<=x2);
    }
}

Error: class "Segment" has no member "xl". How can I solve this?

[anhnha]

I measured time with Stewbond's method here:
http://www.cplusplus.com/forum/general/80867/

By the way, I also includeded vector before.

[Peter87]

By the way, I also includeded vector before.

If you use an older compiler maybe you have to put a space between the >>.

std::stack<CPoint,std::vector<CPoint> > points;

Error: class "Segment" has no member "xl". How can I solve this?

Are you sure that is you only error message? Always start with the first error message first. Note that the code is written in old C so you will probably have to change a few things to make it work in C++.

[anhnha]

Hi again,

If you use an older compiler maybe you have to put a space between the >>.

I am using Visual Studio 2010, also I put a space but the error still comes up.

error C2589: '<' : illegal token on right side of '::'
error C2059: syntax error : '::'

Are you sure that is you only error message?

The error above is the one appears when I hover the cursor over it.
Here are errors while building it:

 error C2065: 'xl' : undeclared identifier
 error C2065: 'xr' : undeclared identifier
error C2065: 'dy' : undeclared identifier
error C2143: syntax error : missing ',' before ';'
error C2065: 'y' : undeclared identifier
error C2065: 'win' : undeclared identifier
 error C2065: 'nv' : undeclared identifier
error C2143: syntax error : missing ',' before ')'
error C2065: 'y' : undeclared identifier
...

[Peter87]

I am using Visual Studio 2010, also I put a space but the error still comes up.

I don't understand why it doesn't work but it probably doesn't make a huge difference anyway.

Here are errors while building it: ...

Yeah, as I thought you will have to translate the code into valid C++ code. Line 46-49 could be written as:

void fill(int x, int y, Window* win, Pixel nv)