Flood Fill: Flood Fill: Exploring Computer Vision's Dynamic Terrain

By Fouad Sabry

What is Flood Fill

Flood fill, also called seed fill, is a flooding algorithm that determines and alters the area connected to a given node in a multi-dimensional array with some matching attribute. It is used in the "bucket" fill tool of paint programs to fill connected, similarly-colored areas with a different color, and in games such as Go and Minesweeper for determining which pieces are cleared. A variant called boundary fill uses the same algorithms but is defined as the area connected to a given node that does not have a particular attribute.

How you will benefit

(I) Insights, and validations about the following topics:

Chapter 1: Flood fill

Chapter 2: Scanline rendering

Chapter 3: Depth-first search

Chapter 4: Quadtree

Chapter 5: Graph traversal

Chapter 6: Connected-component labeling

Chapter 7: Watershed (image processing)

Chapter 8: Maze-solving algorithm

Chapter 9: Ray casting

Chapter 10: Box blur

(II) Answering the public top questions about flood fill.

(III) Real world examples for the usage of flood fill in many fields.

Who this book is for

Professionals, undergraduate and graduate students, enthusiasts, hobbyists, and those who want to go beyond basic knowledge or information for any kind of Flood Fill.

• Language: English
• Publisher: One Billion Knowledgeable
• Release date: May 4, 2024

Book preview

Chapter 1: Flood fill

Flood fill, also known as seed fill, is a flooding algorithm that chooses and modifies the region in a multidimensional array associated to a specific node with a particular attribute. It is used in games like Go and Minesweeper to determine which pieces are cleared as well as in paint applications' bucket fill tool to fill connected, similarly colored areas with a distinct hue. The region connected to a given node but lacking a specific attribute is what is meant by the variation known as border fill, which employs the same techniques.

Keep in mind that flood filling will miss certain pixels in more acute corners, making it unsuitable for drawing filled polygons. Instead, check the Nonzero Rule and the Even-Odd Rule.

Three variables are required by the classic flood-fill algorithm: a start node, a target color, and a replacement color. The method switches to the replacement color for every node in the array that is connected to the start node by a path that is the target color. Instead of the target color, a border color would be provided for a boundary-fill.

Instead, two routines will be provided in the following descriptions in order to generalize the method in the usual manner. Among these are Set, which fills a pixel or node, and Inside, which returns true for unfilled points that, based on their color, would be inside the filled area. Once Set has been called on a node, it must leave the Inside.

There are two versions depending on whether we count nodes touching at the corners as connected or not: eight-way and four-way, respectively.

Following is the earliest known four-way flood-fill implementation that is implicitly stack-based:

Flood-fill (node):

1. If node is not Inside return.

2. Set the node

3. Perform Flood-fill one step to the south of node.

4. Perform Flood-fill one step to the north of node

5. Perform Flood-fill one step to the west of node

6. Perform Flood-fill one step to the east of node

7. Return.

In languages and situations where stack space is extremely constrained, the implementation of the technique used above is simple to grasp but unworkable (e.g. Microcontrollers).

A stack overflow is avoided by moving the recursion into a data structure, such as a stack or queue. The choice of data structure affects the proliferation pattern, but it is similar to the simple recursive method in that it pushes the nodes into a stack or queue for consumption rather than making recursive calls:

Flood-fill (node):

1. Set Q to the empty queue or stack.

2. Add node to the end of Q.

3. While Q is not empty:

4. Set n equal to the first element of Q.

5. Remove first element from Q.

6. If n is Inside:

Set the n

Add the node to the west of n to the end of Q.

Add the node to the east of n to the end of Q.

Add the node to the north of n to the end of Q.

Add the node to the south of n to the end of Q.

7. Continue looping until Q is exhausted.

8. Return.

Before adding a node to the stack or queue, determine and set its pixel color to minimize the size of the stack or queue.

Utilize a loop to move in an east-west direction while queuing pixels above and below (making it similar to the span filling algorithms, below).

To provide out-of-order processors more opportunities to parallelize, interleave two or more copies of the code with additional stacks and queues.

Use several threads, ideally with slightly different visitation schedules so they don't congregate in one place.

Straightforward method that is simple to create bug-free.

memory intensive, especially when using a stack.

tests the most filled pixels four times in total.

Pattern filling is not possible since it needs the results of pixel tests to change.

Access pattern for the queuing variation is not cache-friendly.

difficult to optimize for bitplanes or multi-pixel words.

Working largely with spans, a row with constant y, allows for further optimization. The first published complete example operates according to the following fundamental tenet:.

Fill left and right after a seed point. Keep track of the leftmost and rightmost filled points, lx and rx, respectively. This establishes the range.

Search for more seed points by scanning from lx to rx above and below the current seed point.

The scan process is optimized so that only the seed points at the beginning of the following span must be restarted. A queue explores spans first, while a stack investigates spans first in terms of depth.

Despite checking the most filled pixels three times in total, this approach is the most common in terms of implementations and citations.

fn fill(x, y):

if not Inside(x, y) then return

let s = new empty stack or queue

Add (x, y) to s

while s is not empty:

Remove an (x, y) from s

let lx = x

while Inside(lx - 1, y):

Set(lx - 1, y)

lx = lx - 1

while Inside(x, y):

Set(x, y)

x = x + 1

scan(lx, x - 1, y + 1, s)

scan(lx, x - 1, y - 1, s)

fn scan(lx, rx, y, s):

let span_added = false

for x in lx .. rx:

if not Inside(x, y):

span_added = false

else if not span_added:

Add (x, y) to s

span_added = true

The following improvements were made over time:

A fresh scan wouldn't need to be queued if it were wholly within a grandparent span because it would only detect filled pixels.

Furthermore, only the overhangs (U-turns and W-turns) must be scanned when a new scan crosses a grandparent span.

You can fill up while looking for seeds.

fn fill(x, y):

if not Inside(x, y) then return

let s = new empty queue or stack

Add (x, x, y, 1) to s

Add (x, x, y - 1, -1) to s

while s is not empty:

Remove an (x1, x2, y, dy) from s

let x = x1

if Inside(x, y):

while Inside(x - 1, y):

Set(x - 1, y)

x = x - 1

if x < x1:

Add (x, x1-1, y-dy, -dy) to s

while x1 <= x2:

while Inside(x1, y):

Set(x1, y)

x1 = x1 + 1

Add (x, x1 - 1, y+dy, dy) to s

if x1 - 1 > x2:

Add (x2 + 1, x1 - 1, y-dy, -dy) to s

x1 = x1 + 1

while x1 < x2 and not Inside(x1, y):

x1 = x1 + 1

x = x1

quicker than the pixel-recursive technique by 2–8 times.

Friendly to cache and bitplane access patterns.

Rather than