当我着色时，绘画算法在边缘留下白色像素
Paint algorithm leaving white pixels at the edges when I color
我正在创建绘图应用程序。当我 select 一种非常深的颜色并在熊猫的脸上画画时，边缘是白色的。我希望我的代码为边界内的整个区域着色。这是LINK。这些是我在 javascript 中使用的函数。我怎样才能让他们变得更好？
function matchOutlineColor(r, g, b, a) {
return (r + g + b < 75 && a >= 50);
};
function matchStartColor(pixelPos, startR, startG, startB) {
var r = outlineLayerData.data[pixelPos],
g = outlineLayerData.data[pixelPos + 1],
b = outlineLayerData.data[pixelPos + 2],
a = outlineLayerData.data[pixelPos + 3];
// If current pixel of the outline image is black
if (matchOutlineColor(r, g, b, a)) {
return false;
}
r = colorLayerData.data[pixelPos];
g = colorLayerData.data[pixelPos + 1];
b = colorLayerData.data[pixelPos + 2];
// If the current pixel matches the clicked color
if (r === startR && g === startG && b === startB) {
return true;
}
// If current pixel matches the new color
if (r === curColor.r && g === curColor.g && b === curColor.b) {
return false;
}
return true;
};
function colorPixel(pixelPos, r, g, b, a) {
colorLayerData.data[pixelPos] = r;
colorLayerData.data[pixelPos + 1] = g;
colorLayerData.data[pixelPos + 2] = b;
colorLayerData.data[pixelPos + 3] = a !== undefined ? a : 255;
};
function floodFill(startX, startY, startR, startG, startB) {
document.getElementById('color-lib-1').style.display = "none";
document.getElementById('color-lib-2').style.display = "none";
document.getElementById('color-lib-3').style.display = "none";
document.getElementById('color-lib-4').style.display = "none";
document.getElementById('color-lib-5').style.display = "none";
change = false;
var newPos,
x,
y,
pixelPos,
reachLeft,
reachRight,
drawingBoundLeft = drawingAreaX,
drawingBoundTop = drawingAreaY,
drawingBoundRight = drawingAreaX + drawingAreaWidth - 1,
drawingBoundBottom = drawingAreaY + drawingAreaHeight - 1,
pixelStack = [
[startX, startY]
];
while (pixelStack.length) {
newPos = pixelStack.pop();
x = newPos[0];
y = newPos[1];
// Get current pixel position
pixelPos = (y * canvasWidth + x) * 4;
// Go up as long as the color matches and are inside the canvas
while (y >= drawingBoundTop && matchStartColor(pixelPos, startR, startG, startB)) {
y -= 1;
pixelPos -= canvasWidth * 4;
}
pixelPos += canvasWidth * 4;
y += 1;
reachLeft = false;
reachRight = false;
// Go down as long as the color matches and in inside the canvas
while (y <= drawingBoundBottom && matchStartColor(pixelPos, startR, startG, startB)) {
y += 1;
colorPixel(pixelPos, curColor.r, curColor.g, curColor.b);
if (x > drawingBoundLeft) {
if (matchStartColor(pixelPos - 4, startR, startG, startB)) {
if (!reachLeft) {
// Add pixel to stack
pixelStack.push([x - 1, y]);
reachLeft = true;
}
} else if (reachLeft) {
reachLeft = false;
}
}
if (x < drawingBoundRight) {
if (matchStartColor(pixelPos + 4, startR, startG, startB)) {
if (!reachRight) {
// Add pixel to stack
pixelStack.push([x + 1, y]);
reachRight = true;
}
} else if (reachRight) {
reachRight = false;
}
}
pixelPos += canvasWidth * 4;
}
}
};
// Start painting with paint bucket tool starting from pixel specified by startX and startY
function paintAt(startX, startY) {
var pixelPos = (startY * canvasWidth + startX) * 4,
r = colorLayerData.data[pixelPos],
g = colorLayerData.data[pixelPos + 1],
b = colorLayerData.data[pixelPos + 2],
a = colorLayerData.data[pixelPos + 3];
if (r === curColor.r && g === curColor.g && b === curColor.b) {
// Return because trying to fill with the same color
return;
}
if (matchOutlineColor(r, g, b, a)) {
// Return because clicked outline
return;
}
floodFill(startX, startY, r, g, b);
redraw();
};
您正在为 dithered/smoothed/antialiased/lossy_compressed 图片使用精确的颜色填充。这使得即使颜色略有不同的像素也没有着色（边框），从而产生伪像。有两种简单的补救方法：
匹配接近的颜色而不是完全匹配
如果你现在有 2 RGB 颜色 (r0,g0,b0) 和 (r1,g1,b1)（如果我没看错的话）你的检查是这样的：
if ((r0!=r1)&&(g0!=g1)&&(b0!=b1)) colors_does_not_match;
你应该这样做：
if (((r0-r1)*(r0-r1))+((g0-g1)*(g0-g1))+((b0-b1)*(b0-b1))>treshold) colors_does_not_match;
其中 treshold 是您允许的最大填充距离^2 常数。如果使用的阈值太低，则会保留伪影。如果使用过高的阈值，则填充也会渗出到附近的类似颜色 ...
如果你想要视觉效果更好的东西，那么你可以.
使用封闭边框填充
它与泛色填充基本相同，但您重新着色所有不包含边框颜色的像素，而不是仅包含起始颜色的像素。这将填充该区域，但边界中会有伪影（会有点锡）但不会像您当前的方法那样在视觉上令人不快。
我有时会用同色填充
这个非常适合编辑由于光线或其他原因而颜色变暗的照片。所以我像在洪水填充中一样填充颜色，但如果颜色与大阈值的起始位置不太远并且同时与小阈值的最后填充位置不远，则考虑颜色匹配。通过这种方式，我通常通过重新着色为普通颜色并使用一些喷涂工具渐变图案模糊该区域来修复拼接照片中的天空伪影...
[Edit1] C++ 示例
它使用VCL封装的GDI位图所以重写图像访问你的风格。你也可以忽略 window 的东西（我留下它只是为了展示如何使用它......）。我实现了两种方法 #1,#2 所以选择你想要的。您的边界不清晰，因此阈值很大 (223^2)，使 #2 选项不稳定。 static 变量只是为了简化堆堆栈垃圾处理，所以如果你想多线程处理它，你需要将其删除...
//---------------------------------------------------------------------------
// 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
}
//---------------------------------------------------------------------------
gfx 结果：
[Edit2]迭代分段洪水填充
标准递归洪水填充的问题在于它具有潜在的危险，并且经常导致堆栈溢出以进行更大或更复杂的填充（例如尝试使用许多螺丝的螺旋......）更不用说它通常很慢。洪水填充所需的内存量大约是填充像素数的倍数（因此，将您使用的所有变量和操作数乘以以像素为单位的图像大小，很快就会达到巨大的数字）。
为避免这种情况，您可以通过使用线段而不是像素来大量限制递归层。这将加快一切并大大限制内存使用。这种方法也可以迭代完成，在这种情况下更好，所以算法是这样的：
有一个线段列表seg[]
我选择了水平线，所以每个段都有 x0,x1,y 和一些标志变量 done 供以后使用。从一开始列表是空的。
从填充开始位置添加新段x,y
所以只需水平扫描x,y前后的所有像素，以覆盖左侧x0和右侧x1的所有后续起始颜色（col0）并添加带有标志 done=0.
用done=0
循环所有片段
设置它的 done=1 并扫描它附近的所有像素 x=<x0,x1> 和 y={y-1,y+1} 如果找到尝试添加新的段（就像 #2) 但在添加它之前测试所有其他段是否重叠。如果发现任何重叠段，请使用新找到的段将其放大并设置其 done=0 否则添加新段。这样段数就不会太高。
在进行任何更改后循环 #3
为了加快速度，您可以使用索引表 idx[][]，它将在特定 y 坐标处保存段的所有索引。我set/use所以segment[idx[y][?]].y=y
循环所有片段并对像素重新着色
这里是我的 C++ 代码：
//---------------------------------------------------------------------------
// 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;
}
//---------------------------------------------------------------------------
color_equal只是将颜色与阈值进行比较（而且它应该是一个宏而不是一个函数以获得更快的速度）。
我也使用我的动态列表模板：
List<double> xxx; 等同于 double xxx[];xxx.add(5); 将 5 添加到列表末尾 xxx[7] 访问数组元素（安全）xxx.dat[7]访问数组元素（不安全但直接访问速度快）xxx.num是数组实际使用的大小xxx.reset()清空数组，设置xxx.num=0xxx.allocate(100) 为 100 项预分配 space
这里有一些东西可以比较：
左边是源图像 720x720 像素螺旋，右边是从左下角填充后的结果它花了 40 ms 代码而不使用 idx[] 和使用数组范围检查取而代之的是 440 ms。如果我使用标准的洪水填充，它会在几秒钟后因堆栈溢出而崩溃。另一方面，对于较小的填充，标准递归洪水填充通常比这更快。
我正在创建绘图应用程序。当我 select 一种非常深的颜色并在熊猫的脸上画画时，边缘是白色的。我希望我的代码为边界内的整个区域着色。这是LINK。这些是我在 javascript 中使用的函数。我怎样才能让他们变得更好？
function matchOutlineColor(r, g, b, a) {
return (r + g + b < 75 && a >= 50);
};
function matchStartColor(pixelPos, startR, startG, startB) {
var r = outlineLayerData.data[pixelPos],
g = outlineLayerData.data[pixelPos + 1],
b = outlineLayerData.data[pixelPos + 2],
a = outlineLayerData.data[pixelPos + 3];
// If current pixel of the outline image is black
if (matchOutlineColor(r, g, b, a)) {
return false;
}
r = colorLayerData.data[pixelPos];
g = colorLayerData.data[pixelPos + 1];
b = colorLayerData.data[pixelPos + 2];
// If the current pixel matches the clicked color
if (r === startR && g === startG && b === startB) {
return true;
}
// If current pixel matches the new color
if (r === curColor.r && g === curColor.g && b === curColor.b) {
return false;
}
return true;
};
function colorPixel(pixelPos, r, g, b, a) {
colorLayerData.data[pixelPos] = r;
colorLayerData.data[pixelPos + 1] = g;
colorLayerData.data[pixelPos + 2] = b;
colorLayerData.data[pixelPos + 3] = a !== undefined ? a : 255;
};
function floodFill(startX, startY, startR, startG, startB) {
document.getElementById('color-lib-1').style.display = "none";
document.getElementById('color-lib-2').style.display = "none";
document.getElementById('color-lib-3').style.display = "none";
document.getElementById('color-lib-4').style.display = "none";
document.getElementById('color-lib-5').style.display = "none";
change = false;
var newPos,
x,
y,
pixelPos,
reachLeft,
reachRight,
drawingBoundLeft = drawingAreaX,
drawingBoundTop = drawingAreaY,
drawingBoundRight = drawingAreaX + drawingAreaWidth - 1,
drawingBoundBottom = drawingAreaY + drawingAreaHeight - 1,
pixelStack = [
[startX, startY]
];
while (pixelStack.length) {
newPos = pixelStack.pop();
x = newPos[0];
y = newPos[1];
// Get current pixel position
pixelPos = (y * canvasWidth + x) * 4;
// Go up as long as the color matches and are inside the canvas
while (y >= drawingBoundTop && matchStartColor(pixelPos, startR, startG, startB)) {
y -= 1;
pixelPos -= canvasWidth * 4;
}
pixelPos += canvasWidth * 4;
y += 1;
reachLeft = false;
reachRight = false;
// Go down as long as the color matches and in inside the canvas
while (y <= drawingBoundBottom && matchStartColor(pixelPos, startR, startG, startB)) {
y += 1;
colorPixel(pixelPos, curColor.r, curColor.g, curColor.b);
if (x > drawingBoundLeft) {
if (matchStartColor(pixelPos - 4, startR, startG, startB)) {
if (!reachLeft) {
// Add pixel to stack
pixelStack.push([x - 1, y]);
reachLeft = true;
}
} else if (reachLeft) {
reachLeft = false;
}
}
if (x < drawingBoundRight) {
if (matchStartColor(pixelPos + 4, startR, startG, startB)) {
if (!reachRight) {
// Add pixel to stack
pixelStack.push([x + 1, y]);
reachRight = true;
}
} else if (reachRight) {
reachRight = false;
}
}
pixelPos += canvasWidth * 4;
}
}
};
// Start painting with paint bucket tool starting from pixel specified by startX and startY
function paintAt(startX, startY) {
var pixelPos = (startY * canvasWidth + startX) * 4,
r = colorLayerData.data[pixelPos],
g = colorLayerData.data[pixelPos + 1],
b = colorLayerData.data[pixelPos + 2],
a = colorLayerData.data[pixelPos + 3];
if (r === curColor.r && g === curColor.g && b === curColor.b) {
// Return because trying to fill with the same color
return;
}
if (matchOutlineColor(r, g, b, a)) {
// Return because clicked outline
return;
}
floodFill(startX, startY, r, g, b);
redraw();
};
您正在为 dithered/smoothed/antialiased/lossy_compressed 图片使用精确的颜色填充。这使得即使颜色略有不同的像素也没有着色（边框），从而产生伪像。有两种简单的补救方法：
匹配接近的颜色而不是完全匹配
如果你现在有 2 RGB 颜色
(r0,g0,b0)和(r1,g1,b1)（如果我没看错的话）你的检查是这样的：if ((r0!=r1)&&(g0!=g1)&&(b0!=b1)) colors_does_not_match;你应该这样做：
if (((r0-r1)*(r0-r1))+((g0-g1)*(g0-g1))+((b0-b1)*(b0-b1))>treshold) colors_does_not_match;其中
treshold是您允许的最大填充距离^2 常数。如果使用的阈值太低，则会保留伪影。如果使用过高的阈值，则填充也会渗出到附近的类似颜色 ...如果你想要视觉效果更好的东西，那么你可以
使用封闭边框填充
它与泛色填充基本相同，但您重新着色所有不包含边框颜色的像素，而不是仅包含起始颜色的像素。这将填充该区域，但边界中会有伪影（会有点锡）但不会像您当前的方法那样在视觉上令人不快。
我有时会用同色填充
这个非常适合编辑由于光线或其他原因而颜色变暗的照片。所以我像在洪水填充中一样填充颜色，但如果颜色与大阈值的起始位置不太远并且同时与小阈值的最后填充位置不远，则考虑颜色匹配。通过这种方式，我通常通过重新着色为普通颜色并使用一些喷涂工具渐变图案模糊该区域来修复拼接照片中的天空伪影...
[Edit1] C++ 示例
它使用VCL封装的GDI位图所以重写图像访问你的风格。你也可以忽略 window 的东西（我留下它只是为了展示如何使用它......）。我实现了两种方法 #1,#2 所以选择你想要的。您的边界不清晰，因此阈值很大 (223^2)，使 #2 选项不稳定。 static 变量只是为了简化堆堆栈垃圾处理，所以如果你想多线程处理它，你需要将其删除...
//---------------------------------------------------------------------------
// 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
}
//---------------------------------------------------------------------------
gfx 结果：
[Edit2]迭代分段洪水填充
标准递归洪水填充的问题在于它具有潜在的危险，并且经常导致堆栈溢出以进行更大或更复杂的填充（例如尝试使用许多螺丝的螺旋......）更不用说它通常很慢。洪水填充所需的内存量大约是填充像素数的倍数（因此，将您使用的所有变量和操作数乘以以像素为单位的图像大小，很快就会达到巨大的数字）。
为避免这种情况，您可以通过使用线段而不是像素来大量限制递归层。这将加快一切并大大限制内存使用。这种方法也可以迭代完成，在这种情况下更好，所以算法是这样的：
有一个线段列表
seg[]我选择了水平线，所以每个段都有
x0,x1,y和一些标志变量done供以后使用。从一开始列表是空的。从填充开始位置添加新段
x,y所以只需水平扫描
x,y前后的所有像素，以覆盖左侧x0和右侧x1的所有后续起始颜色（col0）并添加带有标志done=0. 的列表的新段
用
循环所有片段done=0设置它的
done=1并扫描它附近的所有像素x=<x0,x1>和y={y-1,y+1}如果找到尝试添加新的段（就像 #2) 但在添加它之前测试所有其他段是否重叠。如果发现任何重叠段，请使用新找到的段将其放大并设置其done=0否则添加新段。这样段数就不会太高。在进行任何更改后循环 #3
为了加快速度，您可以使用索引表
idx[][]，它将在特定y坐标处保存段的所有索引。我set/use所以segment[idx[y][?]].y=y循环所有片段并对像素重新着色
这里是我的 C++ 代码：
//---------------------------------------------------------------------------
// 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;
}
//---------------------------------------------------------------------------
color_equal只是将颜色与阈值进行比较（而且它应该是一个宏而不是一个函数以获得更快的速度）。
我也使用我的动态列表模板：
List<double> xxx;等同于double xxx[];xxx.add(5);将5添加到列表末尾xxx[7]访问数组元素（安全）xxx.dat[7]访问数组元素（不安全但直接访问速度快）xxx.num是数组实际使用的大小xxx.reset()清空数组，设置xxx.num=0xxx.allocate(100)为100项预分配 space
这里有一些东西可以比较：
左边是源图像 720x720 像素螺旋，右边是从左下角填充后的结果它花了 40 ms 代码而不使用 idx[] 和使用数组范围检查取而代之的是 440 ms。如果我使用标准的洪水填充，它会在几秒钟后因堆栈溢出而崩溃。另一方面，对于较小的填充，标准递归洪水填充通常比这更快。