Queue-Linear Flood Fill: A Fast Flood Fill Algorithm

• Download source files and demo - 492 Kb
• Download demo project - 453 Kb

Introduction

In a previous article I wrote several years ago, Floodfill Algorithms in C# and GDI+, I presented several different flood fill algorithms, and described the differences between them. In this article, I present a single, highly optimized flood fill algorithm, which I call the Queue-Linear algorithm.

This algorithm combines the strengths of both the Queue and Linear algorithms, but has none of the weaknesses. It is very fast, and at the same time, does not succumb to stack overflows, no matter how big the bitmap being processed is. In my tests, my optimized implementation filled an area covering most of a 12.5 megapixel bitmap in about 750ms on a 1.67 GHZ Athlon processor, faster than any other flood fill implementation that I have seen in action.

The Algorithm

The Queue-Linear algorithm is implemented in two parts. The first part, contained in the FloodFill() method in the sample code, prepares all necessary data, and then calls the second part, contained in the QueueLinearFloodFill4() method, for the first time, passing it the coordinates of the starting point.

The QueueLinearFloodFill4() method finds the furthest extent of the flood fill area to the left and right of the x coordinate passed to it, on the scanline specified by the y coordinate. As it checks to the left and right, it fills the area it has checked. It then adds this horizontal range to a queue of ranges to branch up and down from, and returns.

After the FloodFill() method calls LinearFill() for the first time, it enters a loop. The code in the loop dequeues the next flood fill range off the queue, and moves from left to right along the horizontal range, checking each pixel directly above and below the range. For each pixel that matches the starting color closely enough, it calls LinearFill(), which builds a flood fill range starting from that pixel and adds it to the queue, as detailed previously. This process is repeated until the queue is empty.

Since this implementation does not restrict the fill to pixels that exactly match the starting pixel, but instead fills all pixels that are within an adjustable tolerance range, we cannot assume that if a pixel exactly matches the start color, that pixel has already been processed. Therefore, we must keep track of which pixels have already been processed, and treat those pixels as if they are not within the tolerance range, to prevent an endless loop. The best way to do this is via a one-dimensional boolean array, whose length is equal to the number of pixels in the bitmap. (A bit array could be used; however, it would cause a significant decrease in speed.)

Implementation

Just as with the previous article, the sample application for this article allows you to open a bitmap, adjust the fill tolerance, set the fill color, fill anywhere in the bitmap, and save the resulting bitmap to a file. You can also watch the fill occurring in real time. I have not implemented 8-directional fill in this article's sample, but it would be simple to add should you desire it.

There are two flood filler classes in this sample. UnsafeQueueLinearFloodFiller uses the LockBits() method and pointers to perform the image manipulation, and QueueLinearFloodFiller uses the method detailed in my article, Fast Pointerless Image Manipulation in .NET. This allows you to compare the speed of the two methods. Switch between methods via the combo box on the top left corner of the form.

The Code

The following is the code for the algorithm. The FloodFill() method fills an area starting from a given point. The LinearFill() method is used by the FloodFill() method to get the furthest extent of the color area on a given horizontal scanline, filling as it goes, and then add the horizontal range to the queue.

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

Optimization

I have implemented many optimizations in my code to increase performance. These optimizations are useful in other image processing routines as well, so I will discuss some of them here.

Cache bitmap properties

Most properties on the Bitmap class directly or indirectly call the GDI+ API via P/Invoke. If you need to reference these properties often in a performance-critical operation, your code will take a serious performance hit. Therefore, you should cache these properties at the beginning of the operation, and reference the cached version only during the operation.

Store non-call-specific data at class level

Reduced stack space means better performance, so this can be very helpful if your class will not be accessed by multiple threads simultaneously.

Pass value-type arguments to methods by reference where possible

When you repeatedly call a method with value-type parameters passed 'byval', space is allocated for those parameters and the parameters are copied on each call. When I was experimenting with my old 'linear' flood fill algorithm, I found that by passing all possible parameters by reference, I gained a 15% speed increase.

Use a profiler to help you pinpoint bottlenecks

A profiler can catch many things that you may not recognize as bottlenecks. For example, I had originally used a struct with properties to store the tolerance values for the flood filler, but when I checked my code with VS.NET 2005's built-in profiler, I discovered that it caused a 10% performance decrease compared to a simple byte array. A profiler can also save you time in a different way – by helping you to not waste time optimizing in places where it isn't really needed.

Pay attention to the performance implications of everything you do

Sadly, since .NET frees you up from many low-level aspects of programming, many .NET developers do not pay enough attention to the performance and memory aspects of their code. .NET is plenty fast enough for performance-critical code in most cases, as long as developers pay attention to how they code. So even if you don't have to think about the performance implications of what your code does, do it anyway – it's worth it! This article is a good read to start with.

Notes

To see the highest performance in the demo, use the release configuration, not the debug configuration. The "binaries" download contains binaries built with the release configuration.

You haven't properly seen the flood fill algorithm in action until you try it out with a large bitmap. A large bitmap is not included in the download in order to reduce download speed, but you can try it with a picture from a good-quality digital camera if you have one available.