Queue-Linear Flood Fill: A Fast Flood Fill 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.

Final touches: The Milky Way drawing process had some bugs, but these problems were not the cause of the bad filling of the Milky Way by the GeneralPath.fill method of Java. To solve this I applied the Queue-Linear Flood Fill algorithm by J. Dunlap, firstly implemented in Java by Owen Kaluza. It is not as fast as the Java method, but at least it works very well.

Create an outline which should be filled. Make sure the line has no gaps.
Floodfill1
Select the pattern which you like to use for the fill.
Floodfill2
Select the selection tool.
Floodfill3
Place your pen inside the outline and blow into the microphone.
Floodfill4
The shape is filled now.
Floodfill5

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

生活在西班牙

自己动手丰衣足食

BlueAsteroid

Just another WordPress.com site

Jing's Blog

Just another WordPress.com site

Start from here......

我的心情魔方

天才遠私廚

希望能做一個分享各種資訊的好地方

语义噪声

西瓜大丸子汤的博客

笑对人生,傲立寰宇

Just another WordPress.com site

Where On Earth Is Waldo?

A Project By Melanie Coles

the Serious Computer Vision Blog

A blog about computer vision and serious stuff

Cauthy's Blog

paper review...

Cornell Computer Vision Seminar Blog

Blog for CS 7670 - Special Topics in Computer Vision

datarazzi

Life through nerd-colored glasses

Luciana Haill

Brainwaves Augmenting Consciousness

槑烎

1,2,∞

Dr Paul Tennent

and the university of nottingham

turn off the lights, please

A bunch of random, thinned and stateless thoughts around the Web

%d bloggers like this: