队列式线性填充算法：一种快速的洪水填充算法

• 下载源文件和演示 - 492 Kb
• 下载演示项目 - 453 Kb

[演示中的图像受文章作者版权保护 - 未经许可，请勿在 CodeProject 外部发布或分发。]

引言

在我几年前写的一篇名为《C# 和 GDI+ 中的填充算法》的文章中，我介绍了几种不同的填充算法，并描述了它们之间的区别。在本文中，我介绍一种单一的、高度优化的填充算法，我称之为队列-线性算法。

该算法结合了队列和线性算法的优点，但没有任何缺点。它速度非常快，同时，无论要处理的位图有多大，都不会发生堆栈溢出。在我的测试中，我的优化实现可以在 1.67 GHz 的 Athlon 处理器上，在大约 750 毫秒内填充一个覆盖 12.5 兆像素位图大部分区域的区域，比我见过的任何其他填充算法都要快。

算法

队列-线性算法分为两部分实现。第一部分包含在示例代码的 FloodFill() 方法中，它准备所有必要的数据，然后第一次调用第二部分，即 QueueLinearFloodFill4() 方法，并将起始点的坐标传递给它。

QueueLinearFloodFill4() 方法在指定的 y 坐标的扫描线上，找到从传入的 x 坐标向左和向右延伸的最远填充区域。在向左和向右检查的同时，它会填充已检查的区域。然后，它将此水平范围添加到用于从上方和下方分支的范围队列中，并 `return`。

在 FloodFill() 方法第一次调用 LinearFill() 后，它会进入一个循环。循环中的代码将下一个填充范围从队列中出队，然后沿着水平范围从左到右移动，检查范围正上方和正下方的每个像素。对于每个与起始颜色足够接近的像素，它都会调用 LinearFill()，该方法会从该像素开始构建一个填充范围，并将其添加到队列中，如前所述。重复此过程，直到队列为空。

由于此实现不限于填充与起始像素完全匹配的像素，而是填充在可调容差范围内的所有像素，因此我们不能假设如果一个像素完全匹配起始颜色，那么该像素已经被处理过了。因此，我们必须跟踪哪些像素已经被处理过，并将这些像素视为不在容差范围内，以防止无限循环。最好的方法是使用一个一维布尔数组，其长度等于位图中的像素数量。（可以使用位数组；然而，这会导致速度显著下降。）

实现

与上一篇文章一样，本文的示例应用程序允许您打开位图，调整填充容差，设置填充颜色，在位图中的任何位置进行填充，并将结果位图保存到文件。您还可以实时观看填充过程。我在这篇文章的示例中没有实现 8 方向填充，但如果您需要，可以很容易地添加。

此示例中有两个填充类。UnsafeQueueLinearFloodFiller 使用 LockBits() 方法和指针来执行图像处理，而 QueueLinearFloodFiller 使用我在文章《.NET 中无指针图像处理》中详细介绍的方法。这允许您比较两种方法的速度。通过窗体左上角的组合框在方法之间切换。

代码

以下是该算法的代码。FloodFill() 方法从给定点开始填充区域。LinearFill() 方法由 FloodFill() 方法使用，用于在给定的水平扫描线上获取颜色区域的最远边界，在填充的同时进行，然后将水平范围添加到队列中。

/// <summary>
/// Fills the specified point on the bitmap with the currently selected 
/// fill color.
/// </summary>
/// <param name="pt">The starting point for the fill.</param>
public override void FloodFill(System.Drawing.Point pt)
{
    //***Prepare for fill.
    PrepareForFloodFill(pt);

    ranges = new FloodFillRangeQueue(((bitmapWidth+bitmapHeight)/2)*5;
    //***Get starting color.
    int x = pt.X; int y = pt.Y;
    int idx = CoordsToByteIndex(ref x, ref y);
    startColor = new byte[] { bitmap.Bits[idx], bitmap.Bits[idx + 1], 
                        bitmap.Bits[idx + 2] };

    bool[] pixelsChecked=this.pixelsChecked;

    //***Do first call to floodfill.
    LinearFill(ref x, ref y);

    //***Call floodfill routine while floodfill ranges still exist 
    //on the queue
    while (ranges.Count > 0)
    {
        //**Get Next Range Off the Queue
        FloodFillRange range = ranges.Dequeue();

        //**Check Above and Below Each Pixel in the Floodfill Range
        int downPxIdx = (bitmapWidth * (range.Y + 1)) + range.StartX;
                    //CoordsToPixelIndex(lFillLoc,y+1);
        int upPxIdx = (bitmapWidth * (range.Y - 1)) + range.StartX;
                    //CoordsToPixelIndex(lFillLoc, y - 1);
        int upY=range.Y - 1;//so we can pass the y coord by ref
        int downY = range.Y + 1;
        int tempIdx;
        for (int i = range.StartX; i <= range.EndX; i++)
        {
            //*Start Fill Upwards
            //if we're not above the top of the bitmap and the pixel 
        //above this one is within the color tolerance
            tempIdx = CoordsToByteIndex(ref i, ref upY);
            if (range.Y > 0 && (!pixelsChecked[upPxIdx]) && 
                    CheckPixel(ref tempIdx))
                LinearFill(ref i, ref upY);

            //*Start Fill Downwards
            //if we're not below the bottom of the bitmap and 
        //the pixel below this one is
            //within the color tolerance
            tempIdx = CoordsToByteIndex(ref i, ref downY);
            if (range.Y < (bitmapHeight - 1) && (!pixelsChecked[downPxIdx]) 
                        && CheckPixel(ref tempIdx))
                LinearFill(ref i, ref downY);
            downPxIdx++;
            upPxIdx++;
        }

    }
}

/// <summary>
/// Finds the furthermost left and right boundaries of the fill area
/// on a given y coordinate, starting from a given x coordinate, 
/// filling as it goes.
/// Adds the resulting horizontal range to the queue of floodfill ranges,
/// to be processed in the main loop.
/// </summary>
/// <param name="x">The x coordinate to start from.</param>
/// <param name="y">The y coordinate to check at.</param>
void LinearFill(ref int x, ref int y)
{
   //cache some bitmap and fill info in local variables for 
   //a little extra speed
   byte[] bitmapBits=this.bitmapBits;
   bool[] pixelsChecked=this.pixelsChecked;
   byte[] byteFillColor= this.byteFillColor;
   int bitmapPixelFormatSize=this.bitmapPixelFormatSize;
   int bitmapWidth=this.bitmapWidth;

    //***Find Left Edge of Color Area
    int lFillLoc = x; //the location to check/fill on the left
    int idx = CoordsToByteIndex(ref x, ref y); 
                //the byte index of the current location
    int pxIdx = (bitmapWidth * y) + x;//CoordsToPixelIndex(x,y);
    while (true)
    {
        //**fill with the color
        bitmapBits[idx] = byteFillColor[0];
        bitmapBits[idx+1] = byteFillColor[1];
        bitmapBits[idx+2] = byteFillColor[2];
        //**indicate that this pixel has already been checked and filled
        pixelsChecked[pxIdx] = true;
        //**screen update for 'slow' fill
        if (slow) UpdateScreen(ref lFillLoc, ref y);
        //**de-increment
        lFillLoc--;     //de-increment counter
        pxIdx--;        //de-increment pixel index
        idx -= bitmapPixelFormatSize;//de-increment byte index
        //**exit loop if we're at edge of bitmap or color area
        if (lFillLoc <= 0 || (pixelsChecked[pxIdx]) || !CheckPixel(ref idx))
            break;

    }
    lFillLoc++;

    //***Find Right Edge of Color Area
    int rFillLoc = x; //the location to check/fill on the left
    idx = CoordsToByteIndex(ref x, ref y);
    pxIdx = (bitmapWidth * y) + x;
    while (true)
    {
        //**fill with the color
        bitmapBits[idx] = byteFillColor[0];
        bitmapBits[idx + 1] = byteFillColor[1];
        bitmapBits[idx + 2] = byteFillColor[2];
        //**indicate that this pixel has already been checked and filled
        pixelsChecked[pxIdx] = true;
        //**screen update for 'slow' fill
        if (slow) UpdateScreen(ref rFillLoc, ref y);
        //**increment
        rFillLoc++;     //increment counter
        pxIdx++;        //increment pixel index
        idx += bitmapPixelFormatSize;//increment byte index
        //**exit loop if we're at edge of bitmap or color area
        if (rFillLoc >= bitmapWidth || pixelsChecked[pxIdx] || 
                        !CheckPixel(ref idx))
            break;

    }
    rFillLoc--;

   //add range to queue
   FloodFillRange r = new FloodFillRange(lFillLoc, rFillLoc, y);
   ranges.Enqueue(ref r);
}

优化

我在代码中实现了许多优化以提高性能。这些优化在其他图像处理例程中也很有用，因此我将在下面讨论其中一些。

缓存位图属性

Bitmap 类的大多数属性直接或间接通过 P/Invoke 调用 GDI+ API。如果您需要在性能关键的操作中频繁引用这些属性，您的代码将承受严重的性能损失。因此，您应该在操作开始时缓存这些属性，并在操作期间仅引用缓存的版本。

将非调用特定的数据存储在类级别

减少堆栈空间意味着更好的性能，因此如果您的类不会同时被多个线程访问，这将非常有帮助。

尽可能通过引用传递值类型参数给方法

当您反复调用一个带有按“byval”（按值传递）传递的值类型参数的方法时，会为这些参数分配空间并在每次调用时复制参数。在我实验旧的“线性”填充算法时，我发现通过按引用传递所有可能的参数，我获得了 15% 的速度提升。

使用性能分析器来帮助您精确定位瓶颈

性能分析器可以捕获许多您可能没有意识到的瓶颈。例如，我最初使用一个带有属性的结构来存储填充器的容差值，但当我使用 VS.NET 2005 的内置性能分析器检查我的代码时，我发现与简单的字节数组相比，它导致了 10% 的性能下降。性能分析器还可以以另一种方式为您节省时间——通过帮助您避免在不需要的地方浪费时间进行优化。

注意您所做的一切的性能影响

可悲的是，由于 .NET 让您从许多低级编程方面解脱出来，许多 .NET 开发人员不再足够关注代码的性能和内存方面。在大多数情况下，只要开发人员注意他们的编码方式，.NET 的速度对于性能关键的代码来说就足够了。所以即使您不必考虑您代码行为的性能影响，也要这样做——这是值得的！本文是一个不错的开始阅读材料。

注释

为了在演示中看到最高性能，请使用发布配置，而不是调试配置。“binaries”下载包含使用发布配置构建的二进制文件。

直到您尝试使用大型位图，您才真正看到填充算法的实际效果。下载中不包含大型位图，以减少下载速度，但如果您有高质量的数码相机，您可以尝试使用其中的图片。