Floodfill

Floodfill bzw. Flutfüllung ist ein Begriff aus der Computergrafik. Es ist ein einfacher Algorithmus, um Flächen zusammenhängender Pixel einer Farbe in einem digitalen Bild zu erfassen und mit einer neuen Farbe zu füllen.

Ausgehend von einem Pixel innerhalb der Fläche werden jeweils dessen Nachbarpixel darauf getestet, ob diese Nachbarpixel auch die alte Farbe enthalten. Jedes gefundene Pixel mit der alten Farbe wird dabei sofort durch die neue Farbe ersetzt.

Zwei Varianten des Algorithmus sind gängig:

4-connected oder 4-Neighbour

Es werden jeweils die vier benachbarten Pixel unten, links, oben und rechts vom Ausgangspunkt untersucht (Koordinatenursprung ist links-oben im Eck).

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 oder 8-Neighbour

Es werden jeweils die acht benachbarten Pixel oben, unten, links, rechts, oben-links, oben-rechts, unten-links und unten-rechts vom Ausgangspunkt untersucht (Koordinatenursprung ist links-oben im Eck).

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

Bei gleichen Ausgangsbedingungen füllt die 8-connected-Variante üblicherweise einen größeren Bereich als die 4-connected-Variante, da sie „durch feine Ritzen kriecht“. Je nach Anwendungsfall kann dies gewünscht sein oder auch nicht.

Der Algorithmus in der rekursiven Form ist zwar einfach zu formulieren und zu verstehen, eignet sich jedoch nur bedingt für nicht-triviale Anwendungen. Der Algorithmus ist überaus rekursiv. Daher besteht ein hohes Risiko, dass der Algorithmus zu einem Stack-Überlauf führt. Ebenso benötigen die möglichen vielen Stack-Operationen durch die Rekursionen im Vergleich zu den eigentlichen Operationen des Algorithmus relativ viel Zeit.

Nicht zuletzt sind viele Rekursionsaufrufe des Algorithmus unnötig, da dabei unnötigerweise Pixel getestet werden, die kurz zuvor bereits auf die neue Farbe gesetzt wurden. Jede Rekursion trifft mindestens auf ein solches Pixel, jenes Pixel, welches gerade im darüberliegenden Rekursionslevel markiert wurde.

Iterative Flutfüllung

Mit Hilfe eines Stapelspeichers oder einer ähnlichen Datenstruktur ist auch eine iterative Implementierung möglich. Dabei werden die Nachbarpixel-Koordinaten gespeichert und dann nacheinander abgearbeitet. Die Reihenfolge, in der die Koordinaten aus der Datenstruktur ausgelesen werden, spielt dabei keine Rolle. Durch das hohe Risiko eines Stack-Überlaufs bei der rekursiven Flutfüllung ist die iterative Version in der Regel die bessere Wahl zur Implementierung des Verfahrens.

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)

Dieses Beispiel entspricht dem rekursiven Algorithmus mit vier Nachbarn. Derjenige mit acht Nachbarn wird entsprechend analog implementiert.

Anstatt auf dem Stack die als nächstes zu testenden Positionen zu speichern, ist es möglich, die vorherigen Positionen und Richtungen zu speichern. Der Stack enthält dadurch nur den Pfad zur derzeitigen Position, was den Algorithmus speichereffizienter macht.

Teiliterative Flutfüllung (Span Flood Fill)

Bei teiliterativer Flutfüllung besteht der Algorithmus aus einem iterativen Teil, der immer weiterläuft und sich immer in eine bestimmte Richtung wendet, zum Beispiel immer linksherum. Wenn der iterative Teil keine Pixel mehr zum Einfärben findet, wird der rekursive Teil gestartet, der nun deutlich weniger tief in die Rekursion geht. Somit ist ein Stack-Überlauf weniger wahrscheinlich.