= Flood fill
<Flood fill> finds the region reachable from a seed <pixel> through allowed neighboring <pixels> that satisfy a membership rule, often replacing the values in that region. A paint program's fill operation is a familiar application. The seed, membership rule and <pixel connectivity> together specify what will be filled.
Consider the image
$$
I=\begin{pmatrix}
1&1&0\\
1&0&1\\
0&1&1
\end{pmatrix}.
$$
Start at the upper-left <pixel>, select values equal to one, and allow only horizontal or vertical steps. Exactly three <pixels> are reachable, giving replacement by nine as
$$
\begin{pmatrix}
9&9&0\\
9&0&1\\
0&1&1
\end{pmatrix}.
$$
With diagonal steps also allowed, all six ones are reachable and replaced. The fill is a connectivity computation, not a rule to replace every matching value everywhere.
An iterative implementation keeps pending positions in a <stack>, takes one position and adds eligible unvisited neighbors. Marking a position when it enters the pending collection prevents repeated insertion. This is a <depth-first search> of the implicit <graph>. For a fixed neighborhood, visiting a region of $R$ <pixels> takes $O(R)$ <time complexity>, excluding initialization or copying of a whole image. Explicit pending and visited storage avoids relying on a deeply nested recursive call for a large region.
Membership need not require exact equality. The scikit-image `flood_fill` API can accept values within a specified tolerance of the original seed value, with connectivity or a supplied neighborhood footprint controlling adjacency. Comparing each candidate to the seed is different from allowing a chain of small local changes to drift arbitrarily far from the seed value.<flood_fill in the scikit-image documentation>[flood_fill, seed_point, tolerance, footprint and connectivity parameters]{ref}
Record visited positions independently when necessary: replacing a value by itself must not make the algorithm revisit it forever. Repeated <flood fills> with fresh region labels can implement <connected-component labeling>.
Back to article page
