时间戳

首页 > 解决方案 > 画布 - 填充在边缘留下白色像素，用于透明的 PNG 图像

javascript - 画布 - 填充在边缘留下白色像素，用于透明的 PNG 图像

问题描述

现在，我尝试使用文章中的洪水填充算法执行洪水填充算法来填充透明 PNG 图像如何避免在洪水填充算法期间超过最大调用堆栈大小？它使用非递归方法和 Uint32Array 来处理颜色堆栈，效果很好。

但是，这种泛光填充算法留下了未填充的白色（实际上是浅灰色边缘或抗锯齿边缘）。这是我的代码：

 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;
    };

到目前为止，我已经尝试使用以下建议：

  1. 使用 Canvas 中提到的使用 RGBA 值的 matchOutlineColor 函数- 泛洪填充在边缘留下白色像素
  2. 当我尝试实现 Canvas 中提到的“根据强度梯度变化而不是简单阈值限制填充区域”时- Floodfill 在边缘留下白色像素，这被认为是最有前途的算法，我仍然不知道如何以最小的方式实现该算法更改现有算法以处理透明图像情况下的抗锯齿边缘问题。
  3. 当我查看有关如何应用Canvas Flood fill not fill to edge中提到的容差和容差Fade 的示例时，我仍然不知道如何在我的情况下实现这样的容差和容差。
  4. 在 Canvas Javascript FloodFill 算法中提到的容差范围内的色差方法（colorDiff 函数）留下没有颜色的白色像素，到目前为止仍然无法正常工作。类似的事情可以说是 colorsMatch 函数在如何使用 HTML Canvas 执行洪水填充中提到的 Range Square (rangeSq) 内？这仍然无法解决抗锯齿边缘问题。

如果您对如何处理flood-fill算法的抗锯齿边缘问题有任何想法，请尽快回复。

Javascript 中的 Flood-Fill 算法的抗锯齿边缘问题

更新：

这是从考虑到容差的建议中修改后的paintAt函数代码：

<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 = [];
    
};

但是，已发现洪水填充的结果不理想，如此处所示的过渡容差所示：' 过渡时公差点的结果 当公差变得太大时，在过渡时的公差点处产生结果

当容忍度变得太大时，我该如何处理这种问题。任何替代算法将不胜感激。

标签： javascripthtml5-canvasflood-fill

解决方案

第四维中的双通洪水填充

我是如何避免在洪水填充算法期间超过最大调用堆栈大小的已接受答案的作者？和画布洪水填充不填充到边缘

不幸的是，没有完美的解决方案。

下面的方法有问题。

  • 设置容差以使其获得所有边缘锯齿通常会填充不需要的区域。
  • 将容差设置得太低会使边缘看起来比标准填充更差。
  • 重复填充将导致更硬的边缘锯齿。
  • 使用简单的混合功能。正确的混合功能可以在 W3C合成和混合级别“混合正常”中找到。 抱歉，我没有时间完成这个答案。
  • 不容易转换为渐变或图案填充。

有一个更好的解决方案，但它有 1000 多行，单独的代码不适合 32K 答案限制。

这个答案是关于如何更改函数以使用容差和简单边缘混合来减少边缘锯齿的演练。

笔记

  • 答案中的各种片段可能有拼写错误或错误的名称。有关正确的工作代码，请参见底部的示例。

宽容

检测边缘的最简单方法是使用容差并填充填充原点处像素颜色容差范围内的像素。

这可以让填充与锯齿边缘重叠，然后可以检测和混合这些锯齿边缘，以减少抗锯齿造成的伪影。

问题是要获得良好的锯齿覆盖率需要很大的容差，这最终会填充您直观地不希望着色的区域。

计算颜色距离

颜色可以用红、绿、蓝三个值来表示。如果将名称替换为 x、y、z，则很容易看出每种颜色在 3D 空间中的独特位置。

更好的是，这个 3D 空间中任意两种颜色之间的距离与感知的颜色差异直接相关。因此，我们可以通过简单的数学来计算差异（毕达哥拉斯）。

由于我们还需要考虑 Alpha 通道，因此我们需要提升一维。每种颜色及其 alpha 部分在 4D 空间中都有一个独特的点。这些 4D 颜色之间的距离与颜色和透明度的感知差异直接相关。

幸运的是，我们不需要想象 4D 空间，我们所做的只是扩展数学（毕达哥拉斯适用于所有欧几里得维度）。

因此，我们得到了可以添加到洪水填充函数的函数和准备代码。

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;
}

在函数声明中，我们添加一个参数容差，指定为 0 到 255 的值

函数声明从

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

至

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

作为tolerance可选参数。

  • 0 的Atolerance只填充targetColor
  • 255的 Atolerance应填充所有像素

我们需要将容差从通道值转换为 4D 距离值，以便 255 覆盖 4D 色彩空间中两种颜色之间的最大距离。

将以下行添加到函数的顶部paintAt

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

我们现在需要更改像素匹配语句以使用容差。您拥有 p32[idx] === targetColor或类似的任何地方都需要替换为colorDist(idx) <= tolerance. 例外是内部 while 循环，因为我们需要使用 4D 颜色距离

 while (checkPixel(ind)) {

变成

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

双通解决方案

为了对抗锯齿，我们需要按照与颜色距离成比例的量来混合填充颜色。

对所有像素执行此操作意味着如果颜色距离不为 0 且小于容差，则远离填充边缘的像素将获得错误的颜色。

我们只想混合位于填充边缘的像素，不包括画布边缘的像素。对于许多像素，当我们遇到它们时，无法知道像素是否位于填充边缘。我们只有在找到所有填充像素时才能知道。

首先通过洪水填充

因此，我们必须保留一个数组来保存所有填充像素的颜色距离

在函数的顶部创建一个缓冲区来保存像素颜色距离。

const distances = new Uint16Array(width*height);

然后在内部循环中连同设置像素颜色一起设置匹配位置距离。

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

为了跟踪填充了哪些像素，我们设置了距离值的最高位。这意味着对于所有要填充的像素，距离将保持一个非零值，对于要忽略的像素，距离将保持为零。这是通过| 0x8000

填充的主要部分没有完成。在我们开始下一个通道之前，我们让填充完成它的工作。

第二遍边缘检测和融合

在外部循环退出后，我们一次一个地遍历每个像素。检查是否需要填写。

如果需要填充，我们提取颜色距离。p32如果为零，则在数组中设置像素颜色。如果距离不为零，我们将检查它周围的 4 个像素。如果 4 个相邻像素中的任何一个被标记为不填充distances[idx] === 0并且该像素不在画布边界之外，我们就知道它是一个边缘并且需要混合。

// 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++;
}

现在只需将新的像素阵列放到画布上。

例子

这个例子是你的代码的修改版本的一个简单的包装器。它可以确保我没有犯任何算法错误，并在使用此方法时突出显示质量或质量不足。

  • 单击第一个按钮添加随机圆圈。
  • 使用滑块设置公差 0 - 255
  • 单击清除以清除画布。
  • 单击画布以在鼠标位置填充随机颜色。

画布已缩放 2 以使工件更加明显。

该功能floodFill取代了你的paintAt和太大，应该分成两部分，一个用于填充通道，另一个用于边缘检测和混合。

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>

推荐阅读