PHP 中的泛洪填充算法研究

如果你用过绘图程序，那大概率已经体验过泛洪填充算法了。它是一种能给图像区域填充不同颜色的机制，通常用倾倒颜料的油漆桶图标来表示。

用于填充图像空间的泛洪填充算法广为人知，且在各种系统中运用了数十年，并非仅限于图形处理程序。在Drupal开发、Drupal模块开发以及Drupal升级等项目中，若涉及图像相关处理，也可能会用到泛洪填充算法。比如说Drupal11版本，若后续有图像方面的功能拓展，该算法或许就会起到关键作用。

在研究用 PHP 绘制抛物线时，我发现有资料探讨过使用泛洪填充算法填充曲线内部空间。我对 PHP 函数 imagefill() 有一点了解，但更想弄清楚泛洪填充算法的核心原理和工作方式。

本文将研究两种用 PHP 实现的泛洪填充算法，然后拓展一下，看看如何用阈值来控制图像的填充范围。

一、创建测试图像

为测试这些算法，我打算创建一个简单的测试图像。这个图像会包含一组直线和曲线，用它们围成一个区域，进而对该区域进行泛洪填充。

为此，我写了下面这段代码：

$height = 100;
$width = 100;
$img = imagecreatetruecolor($width, $height);
// 创建颜色。
$black = imagecolorallocate($img, 0, 0, 0);
$white = imagecolorallocate($img, 255, 255, 255);
$red = imagecolorallocate($img, 255, 0, 0);
// 绘制两个同心圆。
$length = $height / 2;
imageellipse($img, $height / 2, $width /2, $length, $length, $white);
imageellipse($img, $height / 2, $width /2, $length / 2, $length / 2, $white);
// 绘制一个形状。
$points = [
  10,10,
  $width - 10, 20,
  $width - 10, $height / 2,
  $width / 2, $height / 2,
  $height / 2, $height - 10,
  10, 10
];
imageopenpolygon($img, $points, $white);

这段代码生成了一个可用于测试泛洪填充算法的图像。

这是个特意设置的小图像，目的是在不占用大量系统资源处理大图像的情况下，展示泛洪填充算法的实际应用。为了更清晰地展示，我把图像稍微放大了一些。

用这段代码能轻松生成更大的图像来验证算法能否正常运行。现在测试图像有了，咱们来看看第一个算法。

二、递归泛洪填充

从实现角度看，最简单的泛洪填充算法当属递归泛洪填充算法。在这个算法里，要填充区域内的每个像素都会被检查，接着递归地检查与之相连的四个像素。一旦到达形状的边缘或者图像的边缘，递归就会停止。

“边缘”是由所选背景颜色和像素处的颜色变化来确定的。要是把填充颜色设为红色（在上面创建图像的代码里已定义），背景设为黑色，那么在遍历图像时，测试形状的白色很容易就能被检测出来。

要是还没到达图像边缘，并且颜色和当前像素不同，就填充当前像素，然后在四个基本方向（南、北、东、西）继续递归，直到递归停止。

该算法在填充可用空间方面表现得很不错，但问题是递归栈可能会变得特别大，尤其是处理大图像的时候。这意味着算法虽能正常运行，但在资源有限的系统上可能很快就会耗尽内存。

下面是该算法的实现代码，还对每个部分的步骤做了说明：

/**
 * 使用递归算法进行填充。
 *
 * @param resource $img
 *   当前图像资源。
 * @param int $x
 *   起始 x 坐标。
 * @param int $y
 *   起始 y 坐标。
 * @param int $background
 *   背景颜色。
 * @param int $colour
 *   填充颜色。
 */
function fill_recurse($img, $x, $y, $background, $colour) {
  if ($x === -1 || $y === -1 || $x === imagesx($img) || $y === imagesy($img)) {
    // x 或 y 为 -1 或者图像尺寸为零。
    return;
  }

  if (imagecolorat($img, $x, $y) !== $background) {
    // 颜色与背景不同，这意味着我们要么到达了边缘，要么是一个有颜色的区域。
    return;
  }

  // 设置该像素的颜色
  imagesetpixel($img, $x, $y, $colour);

  // 向南递归。
  fill_recurse($img, $x + 1, $y, $background, $colour);
  // 向北。
  fill_recurse($img, $x - 1, $y, $background, $colour);
  // 向东。
  fill_recurse($img, $x, $y + 1, $background, $colour);
  // 向西。
  fill_recurse($img, $x, $y - 1, $background, $colour);
}

咱们用这个算法来填充测试图像的一部分。选中心点稍微偏左的一个点，用红色填充最里面的圆。

fill_recurse($img, ($width / 2), ($height / 2) -1, $black, $red);

这样会生成相应的图像。

这个算法效果挺好，能沿着我们绘制的形状边缘很好地填充。

把泛洪填充的起始点稍微向左移到两个同心圆之间，用下面的代码：

fill_recurse($img, ($width / 2) - 19, ($height / 2) -1, $black, $red);

这也会生成对应的图像。

可以看到，就算是锯齿状的对角线对这个算法来说也不是问题，它能完美地填充所选区域。

三、扫描式泛洪填充

和递归算法不同，还有一种使用填充和扫描方法的算法。这个系统采用相同的边缘查找技术，不过在这种情况下，我们用两个函数的组合来实现填充效果。

第一个函数 called filled_wth_scan() 接收和 recursive_fill() 函数相同的参数。我们从给定的坐标开始，使用一个垂直点的数组。

从起始点开始，先填充可用的颜色，然后尝试扫描该点的左侧，每次发现可用的像素就填充颜色。接着对图像的右侧执行相同的操作。

经过这两个循环后，应该会得到一条横跨可用区域从左到右的线。之后进入算法的扫描部分，该部分用于向垂直像素数组中添加更多的点。

/**
 * 使用填充和扫描算法填充一个区域。
 *
 * @param resource $img
 *   当前图像资源。
 * @param int $x
 *   起始 x 坐标。
 * @param int $y
 *   起始 y 坐标。
 * @param int $background
 *   背景颜色。
 * @param int $colour
 *   填充颜色。
 */
function fill_with_scan($img, $x, $y, $background, $colour) {
  $a = [];

  // 添加第一个要扫描的点。
  $a[] = ['x' => $x, 'y' => $y];

  // 遍历数组中的像素。
  while (count($a) > 0) {
    // 从数组中取出下一个像素并设置颜色。
    $point = array_pop($a);
    imagesetpixel($img, $point['x'], $point['y'], $colour);

    // 从 x 像素找到下一个要使用的点。
    $lx = $point['x'];
    while($lx > 0 && imagecolorat($img, $lx - 1, $point['y']) === $background) {
      // 设置该点的像素。
      imagesetpixel($img, $lx - 1, $point['y'], $colour);
      // 向后查找。
      $lx = $lx - 1;
    }
    while($point['x'] + 1 = 0 && $point['y'] + 1 = 0 && $point['y'] - 1 >= 0) {
      scan($img, $background, $lx, $point['x'] - 1, $point['y'] - 1, $a);
    }
  }
}

第二个函数，也就是扫描函数，接收两个 x 坐标和一个 y 坐标，这个 y 坐标总是设置在 fill_and_scan() 函数中当前线的上方或下方。

然后它遍历该线在两个 x 坐标之间的像素，向像素数组中添加额外的点，这些点可用于填充该区域。

/**
 * 扫描图像。
 *
 * @param resource $img
 *   图像资源。
 * @param int $background
 *   背景颜色。
 * @param int $lx
 *   左 x 坐标。
 * @param int $rx
 *   右 x 坐标。
 * @param int $y
 *   y 位置。
 * @param array $as
 *   像素数组。
 */
function scan($img, $background, $lx, $rx, $y, &$a) {
  $spanAdded = false;
  for ($x = $lx; $x  $x, 'y' => $y];
      $spanAdded = true;
    }
  }
}

这个函数比递归填充函数稍微难理解一些，本质上它先填充一条线，然后“扫描”这条线的上方和下方，看是否还有其他需要填充的地方。如果有，就添加一个像素，函数继续执行。这个函数的小缺点是，如果要填充的区域非常复杂，扫描可能会多次经过同一个像素，以确保所有区域都被填充。不过，它对复杂形状也能正常工作，并且不像递归系统那样占用大量内存，因为像素数组实际上不会变得很大。

可以选图像中心稍偏的一个点来运行这个函数，代码如下：

fill_with_scan($img, ($width / 2), ($height / 2) -1, $black, $red);

这会生成对应的图像。

这两种算法都能很好地填充图像的一个区域。看到它们的实际运行效果，我就在想能不能对它们进行增强，在填充算法中引入一个阈值。通过为要填充的颜色添加一个阈值，就可以在不同的背景颜色上填充所选颜色，前提是这些背景颜色低于该阈值。

四、创建阈值

目前我们研究的算法只能把颜色的简单变化当作区域的边界。要是颜色和背景不匹配，就认为是要填充形状的边缘。这对于非常简单的区域还行，但当我们想填充一幅图片的某个区域时，就会出现问题。

更好的办法是创建一个阈值，不光关注一种颜色，还关注一种颜色与下一种颜色之间的阈值。如果两种颜色之间的差异小于阈值，就认为该颜色在形状内部，可以进行更改。

下面是用于将背景颜色与当前颜色（相对于阈值）进行比较的函数：

/**
 * 比较背景颜色和要设置的颜色。
 *
 * @param int $colour
 *   要检查的颜色。
 * @param int $background
 *   背景颜色。
 * @param int $threshold
 *   颜色比较阈值。
 *
 * @return bool
 *   如果颜色与背景之间的差异小于设定的阈值，则返回 true。
 */
function compare_background(int $colour, int $background, int $threshold): bool
{
    // 将颜色转换为各自的单独色调。
    $r1 = ($colour >> 16) & 0xFF;
    $g1 = ($colour >> 8) & 0xFF;
    $b1 = $colour & 0xFF;

    $r2 = ($background >> 16) & 0xFF;
    $g2 = ($background >> 8) & 0xFF;
    $b2 = $background & 0xFF;

    if (abs($r1 - $r2) 

这个函数的作用是从传入的颜色中提取单独的红、绿、蓝值，并将它们与阈值进行比较。为了简单起见，我们的阈值级别只是一个单一的值，所以在不同颜色和阈值之间进行比较。如果差异小于阈值，就认为该颜色在“内部”，并返回 true。

在我们的代码里，要留意这个函数返回 true 的情况，要是发生这种情况，就把像素颜色设置为我们选择的填充颜色。

为了测试这个函数，创建一个新图像很有必要。我们需要一个带有一组边界的图像，以便测试阈值，而不是一堆简单的形状。

看下面的代码：

$height = 100;
$width = 255;
$img = imagecreatetruecolor($width, $height);
for ($i = 0; $i 

这会生成一个从左到右在图像宽度上颜色逐渐变白的图像。

我们可以从图像最左侧尝试填充图像，并提供不同的阈值级别来测试这里的阈值填充算法。思路是，设置一个非常高的阈值级别应该会填充整个图像，因为颜色总是会被认为在“内部”。

五、带阈值的递归泛洪填充

借助 compare_background() 函数，我们能修改递归填充算法，引入阈值级别。

这个算法大部分保持不变，但这里需要额外检查一下，确保颜色还没被设置为所选颜色。要是没有这个检查，设置过高的阈值可能会导致无限递归，这可不是我们想看到的。

/**
 * 使用递归算法进行填充。
 *
 * @param resource $img
 *   当前图像资源。
 * @param int $x
 *   起始 x 坐标。
 * @param int $y
 *   起始 y 坐标。
 * @param int $background
 *   背景颜色。
 * @param int $colour
 *   填充颜色。
 * @param int $threshold
 *   颜色比较阈值。
 */
function fill_recurse($img, $x, $y, $background, $colour, $threshold)
{
    if ($x === -1 || $y === -1 || $x === imagesx($img) || $y === imagesy($img)) {
        // x 或 y 为 -1 或者图像尺寸为零。
        return;
    }

    $currentColour = imagecolorat($img, $x, $y);
    if (compare_background($currentColour, $background, $threshold) === false) {
        // 颜色与背景不同，这意味着我们要么到达了边缘，要么是一个有颜色的区域。
        return;
    }

    if ($currentColour === $colour) {
        // 当前像素的颜色已经被设置。
        return;
    }

    // 设置该像素的颜色
    imagesetpixel($img, $x, $y, $colour);

    // 向南递归。
    fill_recurse($img, $x + 1, $y, $background, $colour, $threshold);
    // 向北。
    fill_recurse($img, $x - 1, $y, $background, $colour, $threshold);
    // 向东。
    fill_recurse($img, $x, $y + 1, $background, $colour, $threshold);
    // 向西。
    fill_recurse($img, $x, $y - 1, $background, $colour, $threshold);
}

由于这段代码的结果和填充和扫描算法的结果相同，我稍后再展示这个算法的结果。咱们先看看带有阈值系统的填充和扫描算法。

六、带阈值的填充和扫描泛洪填充

填充和扫描算法的工作方式几乎完全一样，唯一的区别是我们用对 compare_background() 函数的调用替换了像素比较。

/**
 * 使用填充和扫描算法填充一个区域。
 *
 * @param resource $img
 *   当前图像资源。
 * @param int $x
 *   起始 x 坐标。
 * @param int $y
 *   起始 y 坐标。
 * @param int $background
 *   背景颜色。
 * @param int $colour
 *   填充颜色。
 * @param int $threshold
 *   颜色比较阈值。
 */
function fill_with_scan($img, int $x, int $y, int $background, int $colour, int $threshold)
{
    $a = [];

    // 添加第一个要扫描的点。
    $a[] = ['x' => $x, 'y' => $y];

    // 遍历数组中的像素。
    while (count($a) > 0) {
        // 从数组中取出下一个像素并设置颜色。
        $point = array_pop($a);
        imagesetpixel($img, $point['x'], $point['y'], $colour);

        //echo 'OUTER: '. $point['x'] . ' ' . $point['y'] . PHP_EOL;

        // 从 x 像素找到下一个要使用的点。
        $lx = $point['x'];
        while ($lx > 0 && compare_background(imagecolorat($img, $lx - 1, $point['y']), $background, $threshold) === true) {
            // 设置该点的像素。
            imagesetpixel($img, $lx - 1, $point['y'], $colour);
            // 向后查找。
            $lx = $lx - 1;
        }

        while ($point['x'] + 1 = 0 && $point['y'] + 1 = 0 && $point['y'] - 1 >= 0) {
            scan($img, $background, $lx, $point['x'] - 1, $point['y'] - 1, $a, $threshold, $colour);
        }
    }
}

/**
 * 扫描图像。
 *
 * @param resource $img
 *   图像资源。
 * @param int $background
 *   背景颜色。
 * @param int $lx
 *   左 x 坐标。
 * @param int $rx
 *   右 x 坐标。
 * @param int $y
 *   y 位置。
 * @param array $a
 *   像素数组。
 * @param int $threshold
 *   颜色比较阈值。
 */
function scan($img, int $background, int $lx, int $rx, int $y, array &$a, int $threshold, $colour)
{
    $spanAdded = false;
    for ($x = $lx; $x = $colour || compare_background($currentColour, $background, $threshold) === false) {
            $spanAdded = false;
        } elseif ($spanAdded === false) {
            $a[] = ['x' => $x, 'y' => $y];
            $spanAdded = true;
        }
    }
}

我用不断增加的阈值级别运行了这段代码，然后把所有创建的图像拼接成一个单一的（长）图像，以此展示增加阈值限制的效果。

这很明显地表明，随着填充函数阈值的提高，图像被填充的部分也更多。最终的图像阈值基本上是 100%，所以我们用所选颜色完全填充了整个图像。

这些算法在图形程序之外的很多应用场景中都能发挥作用。例如，我们可以用该算法填充图像中的一个区域，然后计算更改的像素数量，这能让我们得到该图像部分的精确面积。面对复杂形状时，这种方法特别有用，否则很难用这种方式进行测量。

要是你对这方面感兴趣，可以查看维基百科上关于泛洪填充算法的页面，里面详细介绍了本文用到的许多算法。我用了一些伪代码来创建原始算法，但阈值系统在那里没有详细介绍。