Paint algorithm leaving white pixels at the edges when I color [duplicate]

Solution 1:

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 treshold is 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:

example

[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,y and some flag variable done for later use. From start the list is empty.
add new segment from filling start position x,y

So just scan all the pixels before and after x,y horizontally to cover all consequent start colors (col0) to the left x0 and right x1 and add new segment to the list with flag done=0.
loop all segments with done=0

Set its done=1 and scan all pixels neighboring it x=<x0,x1> and y={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 its done=0 otherwise 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 specific y coordinate. I set/use it so segment[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 as double xxx[];
xxx.add(5); adds 5 to end of the list
xxx[7] access array element (safe)
xxx.dat[7] access array element (unsafe but fast direct access)
xxx.num is the actual used size of the array
xxx.reset() clears the array and set xxx.num=0
xxx.allocate(100) preallocate space for 100 items

Here something to compare to:

example

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.

Paint algorithm leaving white pixels at the edges when I color [duplicate]

Solution 1:

Related

Recent Posts