Floodfill
Floodfill or flood filling is a term used in computer graphics . It is a simple algorithm for capturing areas of contiguous pixels of one color in a digital image and filling them with a new color.
Starting from a pixel within the area, its neighboring pixels are tested to determine whether these neighboring pixels also contain the old color. Every pixel found with the old color is immediately replaced by the new color.
Two variants of the algorithm are common:
4-connected or 4-neighbor
.gif)
The four neighboring pixels below, left, above and right of the starting point are examined (the origin of the coordinates is in the upper left corner).
def fill4(x, y, alteFarbe, neueFarbe):
if getPixel(x, y) == alteFarbe:
setPixel(x, y, neueFarbe)
fill4(x, y + 1, alteFarbe, neueFarbe) # unten
fill4(x, y - 1, alteFarbe, neueFarbe) # oben
fill4(x + 1, y, alteFarbe, neueFarbe) # rechts
fill4(x - 1, y, alteFarbe, neueFarbe) # links
8-connected or 8-neighbor
.gif)
The eight neighboring pixels top, bottom, left, right, top-left, top-right, bottom-left and bottom-right of the starting point are examined (the origin of the coordinates is left-top in the corner).
def fill8(x, y, alteFarbe, neueFarbe):
if getPixel(x, y) == alteFarbe:
setPixel(x, y, neueFarbe)
fill8(x , y + 1, alteFarbe, neueFarbe) # unten
fill8(x , y - 1, alteFarbe, neueFarbe) # oben
fill8(x + 1, y, alteFarbe, neueFarbe) # rechts
fill8(x - 1, y, alteFarbe, neueFarbe) # links
fill8(x + 1, y + 1, alteFarbe, neueFarbe) # rechts unten
fill8(x + 1, y - 1, alteFarbe, neueFarbe) # rechts oben
fill8(x - 1, y + 1, alteFarbe, neueFarbe) # links unten
fill8(x - 1, y - 1, alteFarbe, neueFarbe) # links oben
With the same starting conditions, the 8-connected variant usually fills a larger area than the 4-connected variant, as it "creeps through fine cracks". Depending on the application, this may or may not be desired.
Although the algorithm in the recursive form is easy to formulate and understand, it is only suitable to a limited extent for non-trivial applications. The algorithm is extremely recursive. Therefore, there is a high risk that the algorithm will cause a stack overflow . The many possible stack operations due to the recursions also require a relatively long time compared to the actual operations of the algorithm.
Last but not least, many recursion calls to the algorithm are unnecessary, since pixels are unnecessarily tested that were previously set to the new color. Each recursion hits at least one such pixel, the pixel that was just marked in the recursion level above.
Iterative flood fill
An iterative implementation is also possible with the help of a stack memory or a similar data structure . The neighboring pixel coordinates are saved and then processed one after the other. The order in which the coordinates are read from the data structure does not matter. Due to the high risk of a stack overflow with the recursive flood filling, the iterative version is usually the better choice for implementing the method.
def fill4(x, y, alteFarbe, neueFarbe):
stack.push(x, y)
while stack.isNotEmpty():
(x, y) = stack.pop
if getPixel(x, y) == alteFarbe:
setPixel(x, y, neueFarbe)
stack.push(x, y + 1)
stack.push(x, y - 1)
stack.push(x + 1, y)
stack.push(x - 1, y)
This example corresponds to the recursive algorithm with four neighbors. The one with eight neighbors is implemented analogously.
Instead of storing the positions to be tested next on the stack, it is possible to save the previous positions and directions. The stack only contains the path to the current position, which makes the algorithm more memory-efficient.
Partial iterative flood fill
In the case of partially iterative flood filling, the algorithm consists of an iterative part that keeps running and always turns in a certain direction, for example always to the left. When the iterative part no longer finds any pixels to color, the recursive part is started, which now goes much less deeply into the recursion. This makes a stack overflow less likely.