五种快速的 Flood Fill 算法
4.32/5 (6投票s)
5 种 Flood Fill 算法的基准测试
引言
几年前，我在这里写了一个 floodfill 程序。后来，我发现它在所有可能的形状填充上都不能正常工作。现在我带回了一个改进的版本，Border Trace。还有一个算法，CrissCross。
我将比较我的 floodfill 代码与其他一些声称可以执行快速 floodfill 的算法。我将比较我的方法的三个算法是
五种 Flood Fill 算法
我的代码的三个竞争者共享一个基本思想：从左到右将源颜色像素填充为目标颜色，同时检查每个像素的上下是否有源颜色像素；这些像素被推送到堆栈中稍后处理。每种方法都有不同的优化：因为基本上一个像素可能需要多次检查其颜色。Quickfill 算法在第二个“已访问”堆栈中检查已处理过的像素。Linear Queue 有一个额外的数组来标记已检查的像素。Efficient Fill 仅依赖于检查源颜色。这确实很有效，在纯填充的情况下，只需一种颜色被另一种颜色替换。但 Flood Fill 还有另一个用途，当源颜色被图像替换时。因为在这种情况下，替换源颜色的图像可能包含相同的颜色，Efficient Fill 无法执行图像填充。
我自己的 flood fill BorderTrace 标记源颜色区域的边界，这是一个不同的方法。最初，我使用目标颜色来标记边界。但这会在某些情况下导致 flood fill 失败。我现在所做的是将边界的每个顶部像素推送到堆栈，并将第二个 2D 数组中的每个底部像素标记。然后弹出所有顶部像素并向下填充一条线直到标记的底部。棘手的部分是源颜色区域内的“岛屿”，其中包含另一种颜色，并且不得填充。在填充过程中遇到岛屿，它们的边界以相同的方式标记。区别在于这些边界现在部分可能具有目标颜色。这使得我的算法不适合用图像填充。我的解决方法：我首先跟踪所有边界，包括岛屿边界，并在找到所有边界后开始填充。这意味着我访问堆栈两次。
我的算法 CrissCross 是前三个算法的变体。不同之处在于它在四个方向上而不是两个方向上填充线条：向上、向下、向左和向右。
调整
为了对算法进行基准测试，我对三个竞争对手中的每一个都进行了一些调整，以使基本情况相同。我从 Efficient Fill 中移除了递归，而是使用堆栈。对于图像填充，我使用第二个数组。我完全重写了 QuickFill，实现了我认为是其基本思想，跳过了所有不必要的附加功能。我跳过的一件事是堆栈的排序。另一个是第二个“已访问”堆栈，所有弹出项都转到其中，并且在每次推送时都会在此处搜索重复项。仅在图像填充时需要它，为此，我现在使用 2D 数组来标记已访问的像素：效率更高。这与我用于除边界跟踪之外的所有算法的技术相同。而且，对于颜色替换，Linear 不需要额外的“已检查”数组，所以只在图像替换版本中使用它。
加速技巧
- 我直接处理所有算法都需要访问的堆栈。我通过循环遍历堆栈而不是弹出。因为已访问的条目没有被移除，所以堆栈大小需要足够大：图像宽度 * 高度 * 每个“推送”的条目绰绰有余。为了可读性或更小的
stacksize，可以参考带有推送和弹出功能的版本。这意味着性能会略有下降。 - 在进行基准测试时，我多次使用辅助 2D 数组，因此每次都必须将其初始化为 0。一种快速的方法是使用
std::fill，但这仅适用于 1D 数组。所以我将 1D 指针 sB6 分配给 2D 数组 sB5 并填充该指针byte sB5[WI][HI], *sB6 = &sB5[0][0];
- 我直接写入锁定的位图数据。通常，那是一个 24 位位图。数据是每像素 3 字节，如果图像宽度不是 4 的倍数，则每行末尾可能会有一些填充字节。填充意味着“每 3 字节一个像素”对于每行都是有效的，但不是整体。我确实使用了一个“
color”struct，包含 3 个字节：每行的指针是解决方案，在一个指向“color”的指针数组中。因此，我可以寻址每个像素，使用tB[y][x]（而不是 `[x][y]`！） 。
现在我必须将像素颜色与源颜色进行比较。一个名为“Same(color1, color2)”的函数可以做到这一点。但这有点慢。比较整数更快。所以，从我的数据数组“tB”中，我读取整数而不是 color struct。这意味着我需要一个额外的字节。我只使用下一个像素的第一个字节，然后通过这样做来忽略它
int *(&tB[y][x]) && 0xFFFFFF
所以：颜色数组给出第一个字节的位置，但我读取 4 个字节而不是 3 个字节。这快多了！但有一个问题：如果没有填充字节，因为图像宽度是 4 的倍数，我将读取超出位图数据 1 个字节！我也找到了解决方案：我复制位图数据的最后一行，增加一个字节，然后指向该副本的指针进入我的数组 tB，即最后一行。算法完成后，我将其复制回位图数据。
//s1 = Stride : width, in bytes, of bitmap data
//including eventual padding
Byte* LastLine = new Byte[s1 + 1];
memcpy(LastLine, tB[hi1 - 1], s1);
color* ktB = tB[hi1 - 1];
tB[hi1 - 1] = (color*)LastLine;
//Do some algorithm
TestOne();
memcpy(ktB, LastLine, s1);
delete[] LastLine;
我承认这是一种快速粗糙的解决方案。它确实对性能有相当大的影响，但请谨慎使用！当然，如果使用 32 位颜色数据，这一切都不需要了，只需比较整数即可。
基准测试
我测试了 10 种算法：5 种不同的思路，每种思路都有 2 个版本，一种用于颜色替换，一种用于图像填充。后者，如上所述，通常需要一个额外的数组来跟踪已访问的内容。我们不能仅依赖源颜色，因为源颜色也可能存在于图像中。我还用一些复杂程度不同的区域测试了所有这些。实际时间当然与我的 CPU 有关。但它们能给人一种哪种更快的感觉。我给出时间，以微秒为单位，仅运行一次。但实际上，我运行了 10000 次以获得平均值。给出了我遇到的最小和最大时间。读取位图数据所需的时间不包括在内。对于图像填充，我使用单色位图，只是为了重复运行测试。在实际使用中，任何图像都可以。（我之前也用彩色图像测试了所有算法）。并且在这个测试中，图像填充位图与原始位图大小相同，以便保持简单。
测试结果
Image 1 : Simple area
A : color replacement
193-301 Border Trace
213-217 CrissCross
217-284 Efficient
221-242 Quickfill
420-543 Linear
B : image fill
250-349 Border Trace
270-275 CrissCross
302-464 Efficient
308-324 Quickfill
519-583 Linear
Image 2 : Complex with lots of islands
A : color replacement
515=771 Border Trace
601-611 CrissCross
616-770 Quickfill
800-1021 Efficient
1010-1274 Linear
B : image fill
637-811 Border Trace
743-752 CrissCross
799-893 Quickfill
1044-1081 Efficient
1297-1376 Linear
Image 3 : Complex area that includes the edges
A : color replacement
440-514 Border Trace
466-473 CrissCross
490-544 Quickfill
638-737 Efficient
653-680 Linear
B : image fill
455-463 Border Trace
530-540 CrissCross
576-591 Quickfill
799-838 Efficient
863-930 Linear
结论
Border Trace 在某些时候表现最佳。在所有情况下，最小和最大值之间都存在巨大差距。有些人不喜欢 Border Trace。我认为这个不一样，它不填充边界。确实，这是一个有点复杂的算法。
第二好的是 CrissCross。它不难理解。它的性能非常稳定，最小值和最大值之间的差异很小。这意味着它经常，但不总是，在测试中名列前茅。这更多地取决于 Border Trace 是否有一个好的运行。在我的下一个项目中，我将选择 CrissCross。
Quickfill 自发布以来一直受到好评，并且性能相当不错。我见过一些衍生的版本。原始版本需要改造。
我称之为 Efficient 的算法，也不是很好，但我喜欢这个想法。而且它的性能优于 Linear Queue。
Linear Queue 是编码最优雅的，但性能不是很好。似乎用得很多。
注释
算法可以改编为替换范围内的颜色，而不是单个颜色。在这种情况下，可以调整“Same”函数。这不包括在基准测试中。
最初，我包括了不进行边缘检查的版本，以防要填充的区域不接触任何边缘。这使得运行速度略有提高。我曾考虑在每侧添加 1 像素来实现此效果。但由于我直接写入位图数据，所以我放弃了这个想法。
我在下载中包含了未优化的版本，这些版本也有注释来解释细节。它们提供了更具可读性的算法表示。
新更新
我对 CrissCross、Border Trace 和 QuickFill 进行了一些调整。但最好的消息是，我受到了关于堆栈使用问题的启发。我又开发了一种算法。我称之为 FillFall，因为它让我想起了瀑布，它向下（和向上）级联，越来越宽。它比其他五种算法需要更少的堆栈。而且它更快！总堆栈使用量分为 3 部分。其中两个是整数数组，每个数组的大小与图像的宽度相同。它们分别存储当前行和下一行中连续源颜色像素的第一个和最后一个像素的 x 值。第三个是常规堆栈，它存储与级联方向相反方向的第一个源颜色像素的 x 和 y 值。感谢两个图像宽度数组，堆栈仅在少数情况下使用。
一些数字：FillFall 在我的三个测试图像上的速度 1A 226-279 2A 523-702 3A 397-414 我添加了第四个测试：随机噪声图像（1/5 像素为黑色，这对算法来说是艰苦的工作）
- Fill Fall 1699-1728
- Quick Fill 1996-2064
- Border Trace 2072-2100
- Criss Cross 2504-2575
- Fill Fall 在该图像上的堆栈使用量：615 + 2*511 个整数 = 3482 字节。
void FillFallN(int x, int y, color fillcolor)
{
int x1, x2, x3, x4, y1, y2, y3, y4, z, p;
color oldcolor = tB[y][x];
stackPointer = 0;
int tArr0[WI], t1Arr0[WI];
int* tArr = tArr0;
int* t1Arr = t1Arr0;
int* between;
int tPt = 0, pPt = 0, t1Pt = 0;
if (Same(fillcolor, oldcolor)) return;
//push a pixel with source color
push3(x, y, 1);
while (pop3(x, y, z))
{
//fill to the left and right of pixel (x, y) that has source color
x2 = x;
while (x2 < w && Same(oldcolor, tB[y][x2]))
{
tB[y][x2] = fillcolor;
x2++;
}
x1 = x - 1;
while (x1 > -1 && Same(oldcolor, tB[y][x1]))
{
tB[y][x1] = fillcolor;
x1--;
}
x1++;
// no filling took place, usually because the pixels
// were filled by an earlier stack entry
if (x1 > x2) continue;
tPt = 0;
// secondary stacks : store the x1 and x2 that mark
// an uninterrupted sequence of just filled pixels
tArr[tPt] = x1;
tPt++;
tArr[tPt] = x2;
tPt++;
if (z == 1) //going down
{
//check the row above this first row and push first pixel
//if we find source color pixels
y4 = y - 1;
if (y4 > -1)
{
x = x1;
while (x < x2)
{
while (x < x2 && !Same(oldcolor, tB[y4][x])) x++;
if (x < x2) push3(x, y4, -1);
while (x < x2 && Same(oldcolor, tB[y4][x])) x++;
}
}
for (y1 = y + 1; y1 < h; y1++) // going down rows
{
pPt = 0;
t1Pt = 0;
while (pPt < tPt)
{
//get next pair of x coordinates in that row that mark
//a sequence of source color pixels
x3 = tArr[pPt];
pPt++;
x4 = tArr[pPt];
pPt++;
x2 = x3;
x1 = x3 - 1;
//check left
while (x1 > -1 && Same(oldcolor, tB[y1][x1]))
{
tB[y1][x1] = fillcolor;
x1--;
}
x1++;
y4 = y1 - 1;
//if we went further left, may have to push pixels in the row above
x = x1;
while (x < x3)
{
while (x < x3 && !Same(oldcolor, tB[y4][x])) x++;
if (x < x3) push3(x, y4, -1);
while (x < x3 && Same(oldcolor, tB[y4][x])) x++;
}
while (x1 < x4) //check going right,
//if we find a sequence of source color pixels,
//fill them and store the first and
//last x of that sequence
{
while (x2 < w && Same(oldcolor, tB[y1][x2]))
{
tB[y1][x2] = fillcolor;
x2++;
}
//store them in the auxiliary array for the next row
t1Arr[t1Pt] = x1;
t1Pt++;
t1Arr[t1Pt] = x2;
t1Pt++;
while (x2 < x4 && !Same(oldcolor, tB[y1][x2])) x2++;
x1 = x2;
}
y4 = y1 - 1;
//if we went further right, may have to push pixels in the row above
x = x4;
while (x < x2)
{
while (x < x2 && !Same(oldcolor, tB[y4][x])) x++;
if (x < x2) push3(x, y4, -1);
while (x < x2 && Same(oldcolor, tB[y4][x])) x++;
}
}
if (t1Pt == 0) break;
//swap the two auxiliary arrays
between = tArr;
tArr = t1Arr;
t1Arr = between;
tPt = t1Pt;
}
}
else
{
y4 = y + 1;
if (y4 < h)
{
x = x1;
while (x < x2)
{
while (x < x2 && !Same(oldcolor, tB[y4][x])) x++;
if (x < x2) push3(x, y4, 1);
while (x < x2&& Same(oldcolor, tB[y4][x])) x++;
}
}
for (y1 = y - 1; y1 > -1; y1--)
{
pPt = 0;
t1Pt = 0;
while (pPt < tPt)
{
x3 = tArr[pPt];
pPt++;
x4 = tArr[pPt];
pPt++;
x2 = x3;
x1 = x3 - 1;
while (x1 > -1 && Same(oldcolor, tB[y1][x1]))
{
tB[y1][x1] = fillcolor;
x1--;
}
x1++;
y4 = y1 + 1;
x = x1;
while (x < x3)
{
while (x < x3 && !Same(oldcolor, tB[y4][x])) x++;
if (x < x3) push3(x, y4, 1);
while (x < x3 && Same(oldcolor, tB[y4][x])) x++;
}
while (x1 < x4)
{
while (x2 < w && Same(oldcolor, tB[y1][x2]))
{
tB[y1][x2] = fillcolor;
x2++;
}
t1Arr[t1Pt] = x1;
t1Pt++;
t1Arr[t1Pt] = x2;
t1Pt++;
while (x2 < x4 && !Same(oldcolor, tB[y1][x2])) x2++;
x1 = x2;
}
y4 = y1 + 1;
x = x4;
while (x < x2)
{
while (x < x2 && !Same(oldcolor, tB[y4][x])) x++;
if (x < x2) push3(x, y4, 1);
while (x < x2 && Same(oldcolor, tB[y4][x])) x++;
}
}
if (t1Pt == 0) break;
between = tArr;
tArr = t1Arr;
t1Arr = between;
tPt = t1Pt;
}
}
}
return;
}
附加
要使 Visual Studio 解决方案正常工作，您需要更改项目属性。启动 .sln 文件。在打开的解决方案中，选择 **项目** -> **属性** -> **高级** -> **C++/CLI 属性** -> **通用语言运行时支持** -> **通用语言运行时支持** (/clr)。这假定您已安装 C++/CLI 模块。它启用了托管代码，该程序使用它来进行位图访问。另一个选项是使用您自己的位图数据访问，通过重写函数 DoTest。
历史
- 2021 年 9 月 7 日：初始版本