You are using exact color fill for dithered/smoothed/antialiased/lossy_compressed image. That leaves pixels with even slightly different color uncolored (borders) creating artifacts. There are 2 easy ways how to remedy it:
-
match close colors instead of exact
if you got 2 RGB colors
(r0,g0,b0)and(r1,g1,b1)right now (if I see it right) your checking is like this:if ((r0!=r1)&&(g0!=g1)&&(b0!=b1)) colors_does_not_match;You should do instead this:
if (((r0-r1)*(r0-r1))+((g0-g1)*(g0-g1))+((b0-b1)*(b0-b1))>treshold) colors_does_not_match;Where
tresholdis you max allowed distance^2 constant for filling. If too low treshold used the artifacts will remain. If too high treshold is used then the fill can bleed also to simila colors nearby …If you want to have something more visually robust then you can compare colors in HSV space.
-
use enclosed border filling
It is basically the same as flood fill but you recolor all pixel not containing border color instead of only those containing start color. This will fill the area but there will be artifacts in the border (will be a bit tinner) but not as visually unpleasing as your current approach.
-
I sometimes use color homogenity fill
This one is good for editing photographs where the colors are shaded due to lighting or whatever. So I fill colors like in flood fill but the color match is considered if the color is not too far from start position by big treshold and not to far from last filled position with small treshold at the same time. This way I usually repair sky artifacts in stitched photos by recoloring to common color and blur the area out with some spray tool gradient patterns…
[Edit1] C++ examples
It uses VCL encapsulated GDI bitmap so rewrite the image access to your style. Also you can ignore the window stuff (I left it only to show how to use this…). I implemented both methods #1,#2 so choose which you want. Your borders are not sharp so the treshold is quite big (223^2) making the #2 option unstable. The static variables are only to ease up heap stack trashing so if you want to multithread this you need to remove it …
//---------------------------------------------------------------------------
// variables
//---------------------------------------------------------------------------
Graphics::TBitmap *bmp=NULL; // your image
union color { DWORD dd; BYTE db[4]; }; // direct RGB channel access
DWORD **pixel=NULL; // direct 32bit pixel access
int xs=0,ys=0; // image resolution
int mx=0,my=0; // mouse position
int treshold=50000; // color match treshold
//---------------------------------------------------------------------------
// Flood fill
//---------------------------------------------------------------------------
DWORD _floodfill_col_fill; // temp storage to ease up recursion heap/stack trashing
DWORD _floodfill_col_start; // temp storage to ease up recursion heap/stack trashing
void _floodfill(int x,int y) // recursive subfunction do not call this directly
{
// variables
static color c;
static int r,g,b;
// color match
c.dd=pixel[y][x]&0x00FFFFFF; // mask out alpha channel just to be sure
if (_floodfill_col_fill==c.dd) return; // ignore already filled parts (exact match)
r=c.db[0]; // r0,g0,b0
g=c.db[1];
b=c.db[2];
c.dd=_floodfill_col_start;
r-=c.db[0]; r*=r; // (r0-r1)^2,(g0-g1)^2,(b0-b1)^2
g-=c.db[1]; g*=g;
b-=c.db[2]; b*=b;
if (r+g+b>treshold) return;
// recolor
pixel[y][x]=_floodfill_col_fill;
// 4 neighboars recursion
if (x> 0) _floodfill(x-1,y);
if (x<xs-1) _floodfill(x+1,y);
if (y> 0) _floodfill(x,y-1);
if (y<ys-1) _floodfill(x,y+1);
}
void floodfill(int x,int y,DWORD col) // This is the main call for flood fill (x,y) start position and col is fill color
{
// init variables
_floodfill_col_start=pixel[y][x]&0x00FFFFFF;
_floodfill_col_fill =col &0x00FFFFFF;
// sanity check
color c;
int r,g,b;
c.dd=_floodfill_col_fill;
r=c.db[0];
g=c.db[1];
b=c.db[2];
c.dd=_floodfill_col_start;
r-=c.db[0]; r*=r;
g-=c.db[1]; g*=g;
b-=c.db[2]; b*=b;
if (r+g+b<=treshold) return;
// fill
_floodfill(x,y);
}
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
// Border fill
//---------------------------------------------------------------------------
DWORD _borderfill_col_fill; // temp storage to ease up recursion heap/stack trashing
DWORD _borderfill_col_border; // temp storage to ease up recursion heap/stack trashing
void _borderfill(int x,int y) // recursive subfunction do not call this directly
{
// variables
static color c;
static int r,g,b;
// color match
c.dd=pixel[y][x]&0x00FFFFFF; // mask out alpha channel just to be sure
if (_borderfill_col_fill==c.dd) return; // ignore already filled parts (exact match)
r=c.db[0]; // r0,g0,b0
g=c.db[1];
b=c.db[2];
c.dd=_borderfill_col_border;
r-=c.db[0]; r*=r; // (r0-r1)^2,(g0-g1)^2,(b0-b1)^2
g-=c.db[1]; g*=g;
b-=c.db[2]; b*=b;
if (r+g+b<=treshold) return;
// recolor
pixel[y][x]=_borderfill_col_fill;
// 4 neighboars recursion
if (x> 0) _borderfill(x-1,y);
if (x<xs-1) _borderfill(x+1,y);
if (y> 0) _borderfill(x,y-1);
if (y<ys-1) _borderfill(x,y+1);
}
void borderfill(int x,int y,DWORD col_fill,DWORD col_border) // This is the main call for border fill (x,y) start position then fill and border colors
{
// init variables
_borderfill_col_fill =col_fill &0x00FFFFFF;
_borderfill_col_border=col_border&0x00FFFFFF;
// sanity check
color c;
int r,g,b;
c.dd=_borderfill_col_fill;
r=c.db[0];
g=c.db[1];
b=c.db[2];
c.dd=_borderfill_col_border;
r-=c.db[0]; r*=r;
g-=c.db[1]; g*=g;
b-=c.db[2]; b*=b;
if (r+g+b<=treshold) return;
// fill
_borderfill(x,y);
}
//---------------------------------------------------------------------------
// Window code
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner):TForm(Owner)
{
// [init event]
// input image
bmp=new Graphics::TBitmap; // VCL encapsulated GDI bitmap rewrite/use to whatever you got instead
bmp->LoadFromFile("test.bmp"); // cropped part of your image
bmp->HandleType=bmDIB; // allow direct pixel access
bmp->PixelFormat=pf32bit; // set 32bit pixels for easy addressing
xs=bmp->Width; // get the image size
ys=bmp->Height;
ClientWidth=xs; // just resize my App window to match image size
ClientHeight=ys;
// direct pixel access
pixel = new DWORD*[ys]; // buffer for pointers to all lines of image
for (int y=0;y<ys;y++) // store the pointers to avoid slow GDI/WinAPI calls latter
pixel[y]=(DWORD*)bmp->ScanLine[y];
}
//---------------------------------------------------------------------------
void __fastcall TForm1::FormDestroy(TObject *Sender)
{
// [exit event]
delete bmp;
delete pixel;
}
//---------------------------------------------------------------------------
void __fastcall TForm1::FormPaint(TObject *Sender)
{
// [on paint event]
Canvas->Draw(0,0,bmp);
}
//---------------------------------------------------------------------------
void __fastcall TForm1::FormClick(TObject *Sender)
{
// [on mouse click event]
floodfill(mx,my,0x00FF0000);
// borderfill(mx,my,0x00FF0000,0x00000000);
Paint(); // shedule repaint event
}
//---------------------------------------------------------------------------
void __fastcall TForm1::FormMouseMove(TObject *Sender, TShiftState Shift, int X,int Y)
{
// [on mouse move event]
mx=X; my=Y; // store actual mouse position
}
//---------------------------------------------------------------------------
And gfx result:
[Edit2] iterative segmented flood fill
The problem with standard recursive flood fill is that it is potentially dangerous and often leads to Stack Overflows for larger or complicated fills (for example try a spiral with many screws …) not to mention it is usually slow. The amount of memory needed for flood fill is a around multiple of filled pixels count (so take all of the variables and operands you use and multiply by image size in pixels and soon you hit huge numbers).
To avoid that you can limit the recursion layers a lot by using line segments instead of pixels. That will speed up everything and limit memory usage a lot. Also this approach can be done iteratively which is better in this case so the algorithm is like this:
-
have a list of line segments
seg[]I chose horizontal lines so each segment has
x0,x1,yand some flag variabledonefor later use. From start the list is empty. -
add new segment from filling start position
x,ySo just scan all the pixels before and after
x,yhorizontally to cover all consequent start colors (col0) to the leftx0and rightx1and add new segment to the list with flagdone=0. -
loop all segments with
done=0Set its
done=1and scan all pixels neighboring itx=<x0,x1>andy={y-1,y+1}if found try to add new segment (just as in #2) but before adding it test all other segments for overlaps. If any overlapping segments are found enlarge it with newly found segment and set itsdone=0otherwise add the new segment. This way the segment count will not be too high. -
loop #3 while any changes has been made
To speed up this you can use index tables
idx[][]that will hold all the indexes of segments at specificycoordinate. I set/use it sosegment[idx[y][?]].y=y -
loop all the segments and recolor pixels
Here the C++ code of my for this:
//---------------------------------------------------------------------------
// variables
//---------------------------------------------------------------------------
Graphics::TBitmap *bmp=NULL; // your image
union color { DWORD dd; BYTE db[4]; }; // direct RGB channel access
DWORD **pixel=NULL; // direct 32bit pixel access
int xs=0,ys=0; // image resolution
int mx=0,my=0; // mouse position
int treshold=50000; // color match treshold
//---------------------------------------------------------------------------
// Color compare with treshold
//---------------------------------------------------------------------------
bool color_equal(DWORD c0,DWORD c1)
{
static color c;
static int r,g,b;
c.dd=c0&0x00FFFFFF; // mask out alpha channel just to be sure
r=c.db[0]; // r0,g0,b0
g=c.db[1];
b=c.db[2];
c.dd=c1&0x00FFFFFF;
r-=c.db[0]; r*=r; // (r0-r1)^2,(g0-g1)^2,(b0-b1)^2
g-=c.db[1]; g*=g;
b-=c.db[2]; b*=b;
return (r+g+b<=treshold);
}
//---------------------------------------------------------------------------
bool color_nonequal(DWORD c0,DWORD c1)
{
static color c;
static int r,g,b;
c.dd=c0&0x00FFFFFF; // mask out alpha channel just to be sure
r=c.db[0]; // r0,g0,b0
g=c.db[1];
b=c.db[2];
c.dd=c1&0x00FFFFFF;
r-=c.db[0]; r*=r; // (r0-r1)^2,(g0-g1)^2,(b0-b1)^2
g-=c.db[1]; g*=g;
b-=c.db[2]; b*=b;
return (r+g+b>treshold);
}
//---------------------------------------------------------------------------
// Flood fill segmented by lines
//---------------------------------------------------------------------------
struct _segment
{
int x0,x1,y;
int done;
_segment(){}; _segment(_segment& a){ *this=a; }; ~_segment(){}; _segment* operator = (const _segment *a) { *this=*a; return this; }; /*_segment* operator = (const _segment &a) { ...copy... return this; };*/
};
void floodfill_segmented(int x,int y,DWORD col) // This is the main call for flood fill (x,y) start position and col is fill color
{
// init variables
int i,j,k,e,ee,x0,x1;
_segment s,*p;
List<_segment> seg; // H-line segments
List< List<int> > idx; // index table seg[idx[y]].y=y to speed up searches
DWORD col0=pixel[y][x]&0x00FFFFFF;
DWORD col1=col &0x00FFFFFF;
// sanity check
if (color_equal(col0,col1)) return;
// prepare segment table and macros
seg.allocate(ys<<3); seg.num=0;
idx.allocate(ys ); idx.num=ys; for (i=0;i<ys;i++) idx.dat[i].num=0;
// add new segment at (x,y)
// scan the line to enlarge it as much as can
// merge with already added segment instead of adding new one if they overlap
// ee=1 if change has been made
#define _seg_add \
{ \
s.x0=x; s.x1=x; s.y=y; s.done=0; \
for (x=s.x0;x>=0;x--) if (color_equal(col0,pixel[y][x])) s.x0=x; else break; \
for (x=s.x1;x<xs;x++) if (color_equal(col0,pixel[y][x])) s.x1=x; else break; \
for (ee=0,k=0;k<idx.dat[s.y].num;k++) \
{ \
j=idx.dat[s.y].dat[k]; p=seg.dat+j; \
if ((p->x0>=s.x0)&&(p->x0<=s.x1)) ee=1; \
if ((p->x1>=s.x0)&&(p->x1<=s.x1)) ee=1; \
if ((p->x0<=s.x0)&&(p->x1>=s.x0)) ee=1; \
if ((p->x0<=s.x1)&&(p->x1>=s.x1)) ee=1; \
if (ee) \
{ \
if (p->x0>s.x0) { p->done=0; p->x0=s.x0; } \
if (p->x1<s.x1) { p->done=0; p->x1=s.x1; } \
s=*p; \
break; \
} \
} \
if (ee) ee=p->done; else { idx.dat[s.y].add(seg.num); seg.add(s); } \
}
// first segment;
_seg_add;
for (e=1;e;)
{
// add new adjacent segments
for (e=0,p=seg.dat,i=0;i<seg.num;i++,p++)
if (!p->done)
{
p->done=1;
y=p->y-1; if (y>=0) for (x=p->x0;x<=p->x1;x++) if (color_equal(col0,pixel[y][x])) { _seg_add; e|=!ee; x=s.x1; p=seg.dat+i; }
y=p->y+1; if (y<ys) for (x=p->x0;x<=p->x1;x++) if (color_equal(col0,pixel[y][x])) { _seg_add; e|=!ee; x=s.x1; p=seg.dat+i; }
}
}
#undef seg_add
// recolor
for (p=seg.dat,i=0;i<seg.num;i++,p++)
for (x=p->x0,y=p->y;x<=p->x1;x++)
pixel[y][x]=col;
}
//---------------------------------------------------------------------------
The color_equal just compares colors with tresholds (and also it should be a macro instead of a function to gain more speed).
I also use mine dynamic list template so:
List<double> xxx;is the same asdouble xxx[];xxx.add(5);adds5to end of the listxxx[7]access array element (safe)xxx.dat[7]access array element (unsafe but fast direct access)xxx.numis the actual used size of the arrayxxx.reset()clears the array and set xxx.num=0xxx.allocate(100)preallocate space for100items
Here something to compare to:
On the left is source image 720x720 pixels spiral and on the right is the result after filling from the bottom left side It took 40 ms Code without using idx[] and using array range checks took around 440 ms instead. If I use standard flood fill it crashes with stack overflow after few seconds. On the other hand for smaller fills the standard recursive flood fill is usually faster then this.