Queue-Linear Flood Fill: A Fast Flood Fill Algorithm

, 15 Nov 2006
 Rate this:
A super-fast flood fill algorithm and implementation, plus helpful optimization tips for image processing.
[Images in the demo are copyrighted by the author of the article - please do not publish or redistribute outside of CodeProject without permission.]

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 `return`s.

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.

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.

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

Web Developer
United States
My main goal as a developer is to improve the way software is designed, and how it interacts with the user. I like designing software best, but I also like coding and documentation. I especially like to work with user interfaces and graphics.

I have extensive knowledge of the .NET Framework, and like to delve into its internals. I specialize in working with VG.net and MyXaml. I also like to work with ASP.NET, AJAX, and DHTML.

 First Prev Next
 Bug in code -- here is fix GuavamanX 14-Feb-14 21:09
 Nice work diponsust 30-Dec-13 9:21
 vs2012 Member 1521119 12-Jun-13 17:43
 solution to sliderpicker problem.... Reeshabh Choudhary 3-Apr-13 0:24
 Problem Reeshabh Choudhary 2-Apr-13 23:46
 Code license mr.cal 13-Feb-12 16:16
 Re: Code license Lea Hayes 6-Jun-12 14:14
 A visual basic version Stef Cas 9-Feb-12 9:51
 My vote of 5 Ditmar 4-Feb-12 10:24
 My vote of 1 robertjb20 27-Jan-12 10:08
 Missing Slider component and therefore cannot test it. He seems not to respond to messages posted here concerning it. (15 days ans counting0.
 Re: My vote of 1 Daniele Rota Nodari 10-May-12 0:07
 Unable to find component "SliderPicker" robertjb20 17-Jan-12 7:38
 HELP!!! IzualDAn 14-Jun-11 14:20
 Re: HELP!!! robertjb20 8-Nov-11 6:45
 Use of pixelsChecked array?? Sreyan32 17-Dec-10 10:18
 My vote of 5 Mrinny 20-Jul-10 12:57
 What about Alpha Pixels? Visionator 10-Feb-10 3:04
 Missing and improper namespaces mbender 18-Dec-09 12:29
 Thanks, great article and algorithm, adding a Java port Ozone77 19-Jun-08 19:14
 Nice work bulupe 12-Sep-07 5:48
 Something to consider for the unmanaged code reinux 26-Aug-07 13:05
 A Little Bug hankhuf 7-Aug-07 11:30
 Re: A Little Bug GuavamanX 14-Feb-14 21:07
 Awesome Article! STLMike 13-Jul-07 22:17
 Re: Awesome Article! ttxT 14-Oct-07 18:41
 Control the Threashold fcis2007 6-Feb-07 6:22
 License Jonas Beckeman 23-Jan-07 22:31
 Very nice! Thanks a lot!! eliran1 21-Nov-06 4:03
 I'm awestruck reinux 15-Nov-06 23:03
 Re: I'm awestruck J. Dunlap 16-Nov-06 3:44
 Re: I'm awestruck reinux 16-Nov-06 9:09
 Re: I'm awestruck J. Dunlap 16-Nov-06 21:47
 I'm less impressed Kodieropa 16-Aug-07 5:23
 Re: I'm less impressed reinux 26-Aug-07 13:00
 Different hardware [modified] Kodieropa 30-Aug-07 10:20
 Re: Different hardware reinux 30-Aug-07 17:32
 Re: I'm awestruck Frank Hileman 16-Nov-06 4:42
 Re: I'm awestruck J. Dunlap 16-Nov-06 4:55
 Last Visit: 31-Dec-99 18:00     Last Update: 22-Jul-14 3:05 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web04 | 2.8.140718.1 | Last Updated 15 Nov 2006
Article Copyright 2006 by J. Dunlap