Canvas - floodfill leaves white pixels at edges for PNG images with transparent

Question

Now, I tried to perform flood fill algorithm to fill up the transparent PNG images using flood fill algorithm from the article How can I avoid exceeding the max call stack size during a flood fill algorithm? which use non recursive method along with Uint32Array to handle color stack with work quite well.

However, this flood fill algorithm has left the white (actually the light grey edge or anti-alias edges) which remain unfilled. Here is my code:

 var BrushColorString  = '#F3CDA6'; // skin color 
canvas.addEventListener('mousedown', function(e) {
        
        const rect = canvas.getBoundingClientRect()
        CanvasMouseX = e.clientX - rect.left;
        CanvasMouseY = e.clientY - rect.top;
        
        if (mode === 'flood-fill')
        {
            // test flood fill algorithm
            paintAt(context,  CanvasMouseX,CanvasMouseY,hexToRgb(BrushColorString));
            
        }
    });
function paintAt(ContextOutput,startX, startY,curColor) {
//function paintAt(ctx,startX, startY,curColor) {   
    // read the pixels in the canvas
    
    const width = ContextOutput.canvas.width, 
    height = ContextOutput.canvas.height,pixels = width*height;
    const imageData = ContextOutput.getImageData(0, 0, width, height);
    var data1 = imageData.data;
    const p32 = new Uint32Array(data1.buffer);  
    const stack = [startX + (startY * width)]; // add starting pos to stack
    const targetColor = p32[stack[0]];
    var SpanLeft = true, SpanRight = true; // logic for spanding left right
    var leftEdge = false, rightEdge = false; 
     
    // proper conversion of color to Uint32Array  
    const newColor = new Uint32Array((new Uint8ClampedArray([curColor.r,curColor.g, curColor.b, curColor.a])).buffer)[0];
    // need proper comparison of target color and new Color
    if (targetColor === newColor || targetColor === undefined) { return } // avoid endless loop
    

    while (stack.length){  
    
        let idx = stack.pop();
        while(idx >= width && p32[idx - width] === targetColor) { idx -= width }; // move to top edge
        SpanLeft = SpanRight = false;   // not going left right yet 
        leftEdge = (idx % width) === 0;          
        rightEdge = ((idx +1) % width) === 0;
        while (p32[idx] === targetColor) {
            p32[idx] = newColor;
            if(!leftEdge) {
                if (p32[idx - 1] === targetColor) { // check left
                    if (!SpanLeft) {        
                        stack.push(idx - 1);  // found new column to left
                        SpanLeft = true;  // 
                    } else if (SpanLeft) { 
                        SpanLeft = false; 
                    }
                }
            }
            if(!rightEdge) {
                if (p32[idx + 1] === targetColor) {
                    if (!SpanRight) {
                        stack.push(idx + 1); // new column to right
                        SpanRight = true;
                    }else if (SpanRight) { 
                        SpanRight = false; 
                    }
                }
            }
            idx += width;
        
        }
        
    
    } 
    
 
    clearCanvas(ContextOutput);
    ContextOutput.putImageData(imageData,0, 0); 
     
    
    
};
function hexToRgb(hex) {
        var result = /^#?([a-f\d]{2})([a-f\d]{2})([a-f\d]{2})$/i.exec(hex);
        return result ? {
              r: parseInt(result[1], 16),
              g: parseInt(result[2], 16),
              b: parseInt(result[3], 16),
              a: 255
        } : null;
    }; 

So far, I have tried using the following suggestion:

1. using matchOutlineColor function using RGBA value mentioned in Canvas - floodfill leaves white pixels at edges
2. When I tried to implemented "Restrict fill area based on intensity gradient changes instead of simple threshold " mentioned in Canvas - floodfill leaves white pixels at edges which is considered as the most promising algorithm, I still have no clue how to implement this algorithm with minimum change on existing algorithm to handle the anti-alias edge issue for the cases of images with transparent.
3. When I take a look at the example on how to apply a tolerance and a toleranceFade mentioned in Canvas flood fill not filling to edge, I still have no clue how implement such a tolerance and a toleranceFade in my case.
4. Color Difference method (colorDiff function) within mentioned tolerance in Canvas Javascript FloodFill algorithm left white pixels without color and so far still not working. Similar thing can be said to colorsMatch function to be within Range Square (rangeSq) mentioned in How can I perform flood fill with HTML Canvas? which still unable to solve the anti-alias edge problem.

If you have any idea on how to deal with anti-alias edge problems of the flood-fill algorithm, please response as soon as possible.

Updated:

Here is the revised code on paintAt fucntion from the suggestion that takes tolerance into account:

<div id="container"><canvas id="control" >Does Not Support Canvas Element</canvas></div>
 <div><label for="tolerance">Tolerance</label>
<input id="tolerance" type="range" min="0" max="255" value="32" step="1" oninput="this.nextElementSibling.value = this.value"><output>32</output></div>
var canvas = document.getElementById("control");
var context = canvas.getContext('2d');
var CanvasMouseX =  -1; var CanvasMouseY = -1;
var BrushColorString  = '#F3CDA6'; // skin color

 
 canvas.addEventListener('mousedown', function(e) {
        
        const rect = canvas.getBoundingClientRect()
        CanvasMouseX = e.clientX - rect.left;
        CanvasMouseY = e.clientY - rect.top;
         
        // testing 
        
        
        if (mode === 'flood-fill')
        {
            // test flood fill algorithm
            paintAt(context,CanvasMouseX,CanvasMouseY,
hexToRgb(BrushColorString),tolerance.value);
             
            
        }
    });
function hexToRgb(hex) {
    var result = /^#?([a-f\d]{2})([a-f\d]{2})([a-f\d]{2})$/i.exec(hex);
    return result ? {
          r: parseInt(result[1], 16),
          g: parseInt(result[2], 16),
          b: parseInt(result[3], 16),
          a: 255
    } : null;
};
function clearCanvas(ctx) {
    ctx.clearRect(0, 0,ctx.canvas.width,ctx.canvas.height);
    
}; 
function colorDistance(index, R00,G00,B00,A00, data0)
{
    var index1 = index << 2; // multiplyed by 4
    const R = R00 - data0[index1 + 0];
    const G = G00 - data0[index1 + 1];
    const B = B00 - data0[index1 + 2];
    const A = A00 - data0[index1 + 3];      
    return Math.sqrt((R * R) + (B * B) + (G * G) + (A * A));
}

function paintAt(ContextOutput,startX, startY,curColor,tolerance) {
    // read the pixels in the canvas
    
    const width = ContextOutput.canvas.width, 
          height = ContextOutput.canvas.height, pixels = width*height;
        
    const rightEdgeNum = width - 1, bottomEdgeNum = height - 1; 
    const imageData = ContextOutput.getImageData(0, 0, width, height);
    var data1 = imageData.data;
    const p32 = new Uint32Array(data1.buffer);  
    const stack = [startX + (startY * width)]; // add starting pos to stack
    const targetColor = p32[stack[0]];
    
    var SpanLeft = true, SpanRight = true; // logic for spanning left right
    var leftEdge = false, rightEdge = false, IsBlend = false; 
    const DistancesArray = new Uint16Array(pixels);  // array distance value  
    var R=-1,G=-1,B=-1,A = -1,idx =0,Distance=0; 
    var R0 = data1[(4*(startX + (startY * width)))+0],
        G0 = data1[(4*(startX + (startY * width)))+1], 
        B0 = data1[(4*(startX + (startY * width)))+2],
        A0 = data1[(4*(startX + (startY * width)))+3];
    var CalculatedTolerance = Math.sqrt(tolerance * tolerance * 4);

    const BlendR = curColor.r |0, BlendG = curColor.g |0, 
          BlendB = curColor.b |0, BlendA = curColor.a|0; 
    // color variable for blending 
    const newColor = new Uint32Array((new Uint8ClampedArray([BlendR,BlendG,BlendB,BlendA])).buffer)[0];  

    if (targetColor === newColor || targetColor === undefined) { return } 
    // avoid endless loop
    
        while (stack.length){  
            idx = stack.pop();

            while (idx >= width && 
            colorDistance(idx - width,R0,G0,B0,A0,data1) <= CalculatedTolerance) { idx -= width }; // move to top edge
            SpanLeft = SpanRight = false;   // not going left right yet 
            leftEdge = (idx % width) === 0;          
            rightEdge = ((idx +1) % width) === 0;

            while ((Distance = colorDistance(idx,R0,G0,B0,A0,data1)) <= CalculatedTolerance) {
                DistancesArray[idx] = (Distance / CalculatedTolerance) * 255 | 0x8000; 
                p32[idx] = newColor; 
                if(!leftEdge) {

                    if (colorDistance(idx - 1,R0,G0,B0,A0,data1) <= CalculatedTolerance) { // check left
                        if (!SpanLeft) {        
                            stack.push(idx - 1);  // found new column to left
                            SpanLeft = true;  // 
                        } else if (SpanLeft) { 
                            SpanLeft = false; 
                        }
                    }
                }
                if(!rightEdge) {
                    if (colorDistance(idx + 1,R0,G0,B0,A0,data1) <= CalculatedTolerance) { 
                        if (!SpanRight) {
                        stack.push(idx + 1); // new column to right
                        SpanRight = true;
                        }else if (SpanRight) { 
                            SpanRight = false; 
                        }
                    }
                }
                idx += width;
    
            }
        }    
        idx = 0;
        while (idx <= pixels-1) {
            Distance = DistancesArray[idx];
            if (Distance !== 0) {
                if (Distance === 0x8000) {
                    p32[idx] = newColor;
                } else {
                     IsBlend = false;
                    const x = idx % width;
                    const y = idx / width | 0;
                    if (x >= 1 && DistancesArray[idx - 1] === 0) { IsBlend = true }
                    else if (x <= rightEdgeNum -1 && DistancesArray[idx + 1] === 0) { IsBlend = true }
                    else if (y >=1 && DistancesArray[idx - width] === 0) { IsBlend = true }
                    else if (y <=bottomEdgeNum-1 && DistancesArray[idx + width] === 0) { IsBlend = true }
                    if (IsBlend) {
                        // blending at the edge 
                        Distance &= 0xFF;             
                        Distance = Distance / 255;        
                        const invDist = 1 - Distance; 
                        const idx1 = idx << 2;    
                        data1[idx1 + 0] = data1[idx1 + 0] * Distance + BlendR * invDist;
                        data1[idx1 + 1] = data1[idx1 + 1] * Distance + BlendG * invDist;
                        data1[idx1 + 2] = data1[idx1 + 2] * Distance + BlendB * invDist;
                        data1[idx1 + 3] = data1[idx1 + 3] * Distance + BlendA * invDist;
                    
                    } else {
                        p32[idx] = newColor;
                    }
                }
            }
            idx++;
        }
    // this recursive algorithm works but still not working well due to the issue stack overflow!
    clearCanvas(ContextOutput);
    ContextOutput.putImageData(imageData,0, 0); 
   // way to deal with memory leak at the array. 
    DistancesArray = [];

    newColor = [];
    p32 = [];
    
};

However, the results of flood fill have been found wanting as shown in the transition tolerance as shown here:'

How can I deal with this kind problem when tolerance has become too much. Any alternative algorithm would be appreciated.

Answer 1

Double pass Flood fill in the 4th dimension

I am the Author of the accepted answers for How can I avoid exceeding the max call stack size during a flood fill algorithm? and Canvas flood fill not filling to edge

Unfortunately there is no perfect solution.

The following method has problems.

• Setting the tolerance so that it gets all edge aliasing will often fill unwanted areas.
• Setting the tolerance too low can make the edges look even worse than the standard fill.
• Repeated fills will result in harder edge aliasing.
• Uses a simple blend function. The correct blend function can be found at W3C Compositing and Blending Level "blending normal" Sorry I am out of time to complete this answer.
• Does not easily convert to gradients or pattern fills.

There is a much better solution but it is 1000+ lines long and the code alone would not fit in the 32K answer limit.

This answer is a walk through of how to change your function to reduce edge aliasing using a tolerance and simple edge blending.

Note

• The various snippets in the answer may have typos or wrong names. For the correct working code see example at bottom.

Tolerance

The simplest method to detect edges is to use a tolerance and fill pixels that are within the tolerance of the pixel color at the fill origin.

This lets the fill overlap the aliased edges that can then be detected and blended to reduce the artifacts due to anti-aliasing.

The problem is that to get a good coverage of the aliasing requires a large tolerance and this ends up filling areas you intuitively would not want colored.

Calculating color distance

A color can be represented by the 3 values red, green, blue. If one substitutes the names with x, y, z it is easy to see how each color has a unique position in 3D space.

Event better is that the distance between any two colors in this 3D space directly correlates to perceived difference in color. We can thus us simple math to calculate the difference (Pythagoras).

As we need to also consider the alpha channel we need to step up one dimension. Each color and its alpha part have a unique point in 4D space. The distance between any of these 4D colors directly correlates to perceived difference in color and transparency.

Lucky we do not need to imagine 4D space, all we do is extend the math (Pythagoras works in all euclidean dimensions).

Thus we get the function and prep code you can add to your flood fill function.

var idx = stack[0] << 2; // remove let first line inside while (stack.length){ 
const r = data1[idx] ;
const g = data1[idx + 1] ;
const b = data1[idx + 2];
const a = data1[idx + 3]
function colorDist(idx) {  // returns the spacial distance from the target color of pixel at idx
    idx <<= 2;
    const R = r - data1[i];
    const G = g - data1[i + 1];
    const B = b - data1[i + 2];
    const A = a - data1[i + 3];      
    return (R * R + B * B + G * G + A * A) ** 0.5;
}

To the function declaration we add an argument tolerance specified as a value 0 to 255

The function declaration changes from

function paintAt(contextOutput, startX, startY, curColor) {

To

function paintAt(contextOutput, startX, startY, curColor, tolerance = 0) {

With tolerance as an optional argument.

• A tolerance of 0 only fills the targetColor
• A tolerance of 255 should fill all pixels

We need to convert the tolerance from a channel value to a 4D distance value so that the 255 covers the greatest distance between two colors in the 4D color space.

Add the following line to the top of the function paintAt

 tolerance = (tolerance * tolerance * 4) ** 0.5; // normalize to 4D RGBA space

We now need to change the pixel match statements to use the tolerance. Anywhere you have p32[idx] === targetColor or similar needs to be replaced with colorDist(idx) <= tolerance. The exception is the inner while loop as we need to use the 4D color distance

 while (checkPixel(ind)) {

becomes

 // declare variable dist at top of function
 while ((dist = colorDist(idx)) <= tolerance) {

Double pass solution

To combat the aliasing we need to blend the fill color by an amount proportional to the color distance.

Doing this for all pixels means that pixels away from the edge of the fill will get the wrong color if the color distance is not 0 and less than tolerance.

We only want to blend pixels if they are at the edge of the fill, excluding those at the edge of the canvas. For many of the pixels there is no way of knowing if a pixel is at the edge of the fill as we come across them. We can only know when we have found all filled pixels.

First pass the flood fill

Thus we must keep an array that holds the color distance for all pixels filled

At the top of the function create a buffer to hold pixel color distances.

const distances = new Uint16Array(width*height);

Then in the inner loop along with setting the pixel color set the matching locations distance.

 while ((dist = colorDist(idx)) <= tolerance) {
     //Must not fill color here do in second pass p32[idx] = newColor;
     distances[idx] = (dist / tolerance) * 255 | 0x8000; 

To track which pixels are filled we set the top bit of the distance value. That means that distances will hold a non zero value for all pixels to fill and zero for pixels to ignore. This is done with the | 0x8000

The main part of the fill is no done. We let the fill do its thing before we start on the next pass.

Second pass edge detect and blend

After the outer loop has exited we step over each pixel one at a time. Check if it needs to be filled.

If it needs filling we extract the color distance. If zero set that pixels color in the p32 array. If the distance is not zero we then check the 4 pixels around it. If any of the 4 neighboring pixels is marked as do not fill distances[idx] === 0 and that pixel is not outside the canvas bounds we know it is an edge and needs to be blended.

// declare at top of function
var blend, dist, rr, gg, bb, aa;

// need fill color's channels for quickest possible access.
const fr = curColor.r | 0;
const fg = curColor.g | 0;
const fb = curColor.b | 0;
const fa = curColor.a | 0;


// after main fill loop.
idx = 0;
const rightEdge = width - 1, bottomEdge = height - 1; 
while (idx < width * height){
    dist = distances[idx];
    if (dist !== 0) {
        if (dist === 0x8000) {
            p32[idx] = newColor;
        } else {
            blend = false;
            const x = idx % width;
            const y = idx / width | 0;
            if (x > 0 && distances[idx - 1] === 0) { blend = true }
            else if (x < rightEdge && distances[idx + 1] === 0) { blend = true }
            else if (y > 0 && distances[idx - width] === 0) { blend = true }
            else if (y < bottomEdge && distances[idx + width] === 0) { blend = true }

            if (blend) { // pixels is at fill edge an needs to blend
                dist &= 0xFF;             // remove fill bit
                dist = dist / 255;        // normalize to range 0-1
                const invDist = 1 - dist; // invert distance

                // get index in byte array
                const idx1 = idx << 2;    // same as idx * 4 
                
                // simple blend function (not the same as used by 2D API)
                data[idx1]     = data[idx1    ] * dist + fr * invDist;
                data[idx1 + 1] = data[idx1 + 1] * dist + fg * invDist;
                data[idx1 + 2] = data[idx1 + 2] * dist + fb * invDist;
                data[idx1 + 3] = data[idx1 + 3] * dist + fa * invDist;

            } else { 
                p32[idx] = newColor;
            }
       }
    }
    idx++;
}

And now just put the new pixel array onto the canvas.

Example

This example is a bare bones wrapper around a modified version of your code. It is there to make sure I did not make any algorithmic mistakes and to highlight the quality or lack of quality when using this method.

• Click first button to add random circle.
• Use slider to set tolerance 0 - 255
• Click clear to clear canvas.
• Click canvas to fill random color at mouse pos.

Canvas has been scaled by 2 to make artifacts more visible.

The function floodFill replaces your paintAt and is too big and should be broken into two parts, one for the fill pass, and another for edge detect and blend.

const ctx = canvas.getContext("2d");
var circle = true;
test();
canvas.addEventListener("click", e => {circle = false; test(e)});
toggleFill.addEventListener("click",e => {circle = true; test(e)});
clear.addEventListener("click",()=>ctx.clearRect(0,0,500,500));
function randomCircle() {
    ctx.beginPath();
    ctx.strokeStyle = "black";
    ctx.lineWidth = 4;
    const x = Math.random() * 100 | 0;
    const y = Math.random() * 100 | 0;
    ctx.arc(x, y, Math.random() * 25 + 25, 0 , Math.PI * 2);
    ctx.stroke();
    return {x,y};
}

function test(e) {
    if (circle) {
        toggleFill.textContent = "Click canvas to fill";
        randomCircle();
    } else {
        toggleFill.textContent = "Click button add random circle";
        const col = {
            r: Math.random() * 255 | 0,
            g: Math.random() * 255 | 0,
            b: Math.random() * 255 | 0,
            a: Math.random() * 255 | 0,
        };
        floodFill(ctx, (event.offsetX - 1) / 2 | 0, (event.offsetY -1) / 2| 0, col, tolerance.value);
    }
}

// Original function from SO question https://stackoverflow.com/q/65359146/3877726
function floodFill(ctx, startX, startY, curColor, tolerance = 0) {
    var idx, blend, dist, rr, gg, bb, aa, spanLeft = true, spanRight = true, leftEdge = false, rightEdge = false;
    const width = ctx.canvas.width,  height = ctx.canvas.height, pixels = width*height;
    const imageData = ctx.getImageData(0, 0, width, height);
    const data = imageData.data;
    const p32 = new Uint32Array(data.buffer);  
    const stack = [startX + (startY * width)]; 
    const targetColor = p32[stack[0]];
    const fr = curColor.r | 0;
    const fg = curColor.g | 0;
    const fb = curColor.b | 0;
    const fa = curColor.a | 0;  
    const newColor = (fa << 24) + (fb << 16) + (fg << 8) + fr;     
    if (targetColor === newColor || targetColor === undefined) { return } 

    idx = stack[0] << 2; 
    const rightE = width - 1, bottomE = height - 1; 
    const distances = new Uint16Array(width*height);   
    tolerance = (tolerance * tolerance * 4) ** 0.5; 
  
    const r = data[idx] ;
    const g = data[idx + 1] ;
    const b = data[idx + 2];
    const a = data[idx + 3]
    function colorDist(idx) {  
        if (distances[idx]) { return Infinity }
        idx <<= 2;
        const R = r - data[idx];
        const G = g - data[idx + 1];
        const B = b - data[idx + 2];
        const A = a - data[idx + 3];      
        return (R * R + B * B + G * G + A * A) ** 0.5;
    }

    while (stack.length) {  
        idx = stack.pop();
        while (idx >= width && colorDist(idx - width) <= tolerance) { idx -= width }; // move to top edge
        spanLeft = spanRight = false;   // not going left right yet 
        leftEdge = (idx % width) === 0;          
        rightEdge = ((idx + 1) % width) === 0;
        while ((dist = colorDist(idx)) <= tolerance) {
            distances[idx] = (dist / tolerance) * 255 | 0x8000; 
            if (!leftEdge) {
                if (colorDist(idx - 1) <= tolerance) { 
                    if (!spanLeft) {        
                        stack.push(idx - 1); 
                        spanLeft = true;   
                    } else if (spanLeft) { 
                        spanLeft = false; 
                    }
                }
            }
            if (!rightEdge) {
                if (colorDist(idx + 1) <= tolerance) {
                    if (!spanRight) {
                        stack.push(idx + 1); 
                        spanRight = true;
                    }else if (spanRight) { 
                        spanRight = false; 
                    }
                }
            }
            idx += width;
        }
    } 
    idx = 0;
    while (idx < pixels) {
        dist = distances[idx];
        if (dist !== 0) {
            if (dist === 0x8000) {
                p32[idx] = newColor;
            } else {
                blend = false;
                const x = idx % width;
                const y = idx / width | 0;
                if (x > 0 && distances[idx - 1] === 0) { blend = true }
                else if (x < rightE && distances[idx + 1] === 0) { blend = true }
                else if (y > 0 && distances[idx - width] === 0) { blend = true }
                else if (y < bottomE && distances[idx + width] === 0) { blend = true }
                if (blend) {
                    dist &= 0xFF;             
                    dist = dist / 255;        
                    const invDist = 1 - dist; 
                    const idx1 = idx << 2;    
                    data[idx1]     = data[idx1    ] * dist + fr * invDist;
                    data[idx1 + 1] = data[idx1 + 1] * dist + fg * invDist;
                    data[idx1 + 2] = data[idx1 + 2] * dist + fb * invDist;
                    data[idx1 + 3] = data[idx1 + 3] * dist + fa * invDist;
                } else { 
                    p32[idx] = newColor;
                }
            }
        }
        idx++;
    }

    ctx.putImageData(imageData,0, 0); 
}

canvas {
  width: 200px;
  height: 200px;  
  border: 1px solid black;
}

<label for="tolerance">Tolerance</label>
<input id="tolerance" type="range" min="0" max="255" value="32" step="1"></input>
<button id ="toggleFill" >Click add random circle</button>
<button id ="clear" >Clear</button><br>
<canvas id="canvas" width="100" height="100"></canvas>