CODEWITHSUNDEEP
algorithmpseudocode
Prashant Cholachagudda
Prashant Cholachagudda

Reputation: 13092

How can I improve the performance of my flood-fill routine?

I'm implementing the four way flood fill in my application, pseudo code given below

Flood-fill (node, target-color, replacement-color):
 1. If the color of node is not equal to target-color, return.
 2. Set the color of node to replacement-color.
 3. Perform Flood-fill (one step to the west of node, target-color, replacement-color).
    Perform Flood-fill (one step to the east of node, target-color, replacement-color).
    Perform Flood-fill (one step to the north of node, target-color, replacement-color).
    Perform Flood-fill (one step to the south of node, target-color, replacement-color).
 4. Return

It's kind of slow and sometimes fills the call stack! And I'm really failed to calculate the complexity of this algorithm.

Can anyone suggest better algorithm to implement it, please?

Upvotes: 2

Views: 5879

Answers (5)

bandybabboon
bandybabboon

Reputation: 2346

You can try implementing this routine, it fills 4 million pixels per second.

On an I7 from 2017, that's equivalent to 9 million flooded pixels per second, so a 1024x1024 pixel image can be processed in about 0.1 seconds,using 10-15MB memory:

https://www.youtube.com/watch?v=4hQ1wA4Sl4c&feature=youtu.be

http://unity3dmc.blogspot.com/2017/02/ultimate-3d-floodfill-scanline.html?m=1

Upvotes: 0

rwong
rwong

Reputation: 6162

The current state-of-the-art floodfill algorithm (since 2006 or so) is based on finding the contour (the outermost boundary) of the connected component, converting the contour into horizontal pixel runs (and detecting and removing of internal holes from the connected component), then fill the pixel runs. The benefits are vastly reduced memory requirements (and/or stack level) as well as being faster (interior pixels are guaranteed to be read exactly once and written once). However the algorithm is not trivial. You'll need to read some research papers in order to implement it.

Upvotes: 4

guiman
guiman

Reputation: 1334

it think that what your dealing with is a graph and as i come to uderstand you should change the color of each node and replace it with another only if the target-color matches.

The complexity of this algorithm expressed in Big O is O( 4^n ) so i would recommend you try to implement a BFS algorithm, this way you might avoid leaving an unconneted node without changind and also avoid passing more than once on any vertice. That way you should be able to perfom in something like O( | E | + | V | ) where |E| is the number of edges and |V| is the number of vertices.

Here its a link to wikipedia explanation, and its quite simple so check this out!

PS: If you need a had with the algorithm i'd be more than happy to help you!

Upvotes: 1

user180247
user180247

Reputation:

It may be possible to reduce the number of items you typically need on the stack, by using larger items - horizontal lines rather than single pixels.

Each time you get a line from the stack/queue, scan the full length of this line one-pixel-north and one-pixel-south to form a number of additional horizontal lines to add to the stack. The eastmost and westmost of these lines may be able to grow east/west further than the bounds of the original line, so do this. Then add all these additional lines to the stack/queue.

The start point should also be extended to a line east and west before being added to the queue.

Coding will be a little trickier than a pixel-at-a-time flood-fill, but there are typically far fewer horizontal lines to worry about than pixels. There are perverse cases, though.

Upvotes: 1

GrandmasterB
GrandmasterB

Reputation: 3455

I cant help you with C# since I've only done this in Delphi, but I can help you with the call stack problem. The trick is to not use a recursive algorithm. Rather, use a stack based approach by maintaining a stack of points that need to be reviewed.

Basically, you add the 'start point' to the stack (and change its color). Then while the stack is not empty, take the last point off the stack (ie, Pop it). Do your comparisons for all 4 directions (left, right, up, down). If any of the neighboring pixels need to flip to the new color, do the flip, and then add that neighboring point to the stack. On your next loop through, there should be more points then on the stack. Continue looping until the stack is empty.

Upvotes: 4

Related Questions