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.

Rekursive Implementierung

Es gibt zwei Varianten der rekursiven Implementierung.

4-connected oder 4-Neighbour

Schema

Es werden jeweils die 4 benachbarten Pixel unten, links, oben und rechts vom Ausgangspunkt untersucht. Der Koordinatenursprung ist die Ecke links oben.

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

Schema

Es werden jeweils die 8 benachbarten Pixel oben, unten, links, rechts, oben-links, oben-rechts, unten-links und unten-rechts vom Ausgangspunkt untersucht. Der Koordinatenursprung ist die Ecke links oben.

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 Overflow 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 Implementierung

Programmierung

Mit Hilfe einer Warteschlange, 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 Overflow bei der rekursiven Implementierung ist die iterative Version in der Regel die bessere Wahl zur Implementierung des Verfahrens.

C#

Das folgende Programm in der Programmiersprache C# verwendet zwei verschachtelte while-Schleifen für eine Breitensuche der Pixel mit derselben Farbe.

using System; using System.Collections.Generic; using System.Drawing; namespace FloodFill {  class Program  {  // Diese Methode gibt true zurück, wenn die beiden Farben gleich sind, sonst false  private static bool ColorMatch(Color replacementColor, Color targetColor)  {  return replacementColor.ToArgb() == targetColor.ToArgb();  }    // Diese Methode füllt alle zusammenhängenden Pixel, die dieselbe Farbe wie das Startpixel haben, mit der neuen Farbe  private static void FloodFill(Bitmap bitmap, Point point, Color replacementColor)  {  Color targetColor = bitmap.GetPixel(point.X, point.Y); // Speichert die Farbe des Startpixels  Queue<Point> queue = new Queue<Point>(); // Warteschlange der Pixel für die Breitensuche  queue.Enqueue(point); // Fügt das Startpixel der Warteschlange hinzu  while (queue.Count != 0) // So lange die Warteschlange nicht leer ist  {  Point point1 = queue.Dequeue(); // Entfernt das erste Pixel aus der Warteschlange  if (!ColorMatch(bitmap.GetPixel(point1.X, point1.Y), targetColor)) // Wenn die Farbe des aktuellen Pixels gleich dem Startpixel ist, wird die nächste Iteration der äußeren while-Schleife ausgeführt  {  continue;  }  Point point2 = new Point(point1.X + 1, point1.Y); // Speichert das Pixel rechts vom aktuellen Pixel  while (point1.X >= 0 && ColorMatch(bitmap.GetPixel(point1.X, point1.Y), targetColor)) // So lange das aktuelle Pixel nicht links vom Rand ist und die Farbe des Startpixels hat  {  bitmap.SetPixel(point1.X, point1.Y, replacementColor); // Setzt das aktuelle Pixel auf die neue Farbe  if (point1.Y > 0 && ColorMatch(bitmap.GetPixel(point1.X, point1.Y - 1), targetColor)) // Wenn das aktuelle Pixel nicht am linken Rand ist und die Farbe des Startpixels hat  {  queue.Enqueue(new Point(point1.X, point1.Y - 1)); // Fügt das Pixel über dem aktuellen Pixel der Warteschlange hinzu  }  if (point1.Y < bitmap.Height - 1 && ColorMatch(bitmap.GetPixel(point1.X, point1.Y + 1), targetColor)) // Wenn das aktuelle Pixel nicht am rechten Rand ist und die Farbe des Startpixels hat  {  queue.Enqueue(new Point(point1.X, point1.Y + 1)); // Fügt das Pixel unter dem aktuellen Pixel der Warteschlange hinzu  }  point1.X--; // Verschiebt das aktuelle Pixel um 1 nach links  }  // Die folgende while-Schleife wiederholt den Ablauf mit dem Pixel rechts vom aktuellen Pixel  while (point2.X <= bitmap.Width - 1 && ColorMatch(bitmap.GetPixel(point2.X, point2.Y), targetColor))  {  bitmap.SetPixel(point2.X, point2.Y, replacementColor);  if (point2.Y > 0 && ColorMatch(bitmap.GetPixel(point2.X, point2.Y - 1), targetColor))  {  queue.Enqueue(new Point(point2.X, point2.Y - 1));  }  if (point2.Y < bitmap.Height - 1 && ColorMatch(bitmap.GetPixel(point2.X, point2.Y + 1), targetColor))  {  queue.Enqueue(new Point(point2.X, point2.Y + 1));  }  point2.X++; // Verschiebt das aktuelle Pixel um 1 nach rechts  }  }  }    // Hauptmethode, die das Programm ausführt  public static void Main(string[] args)  {  Bitmap bitmap = new Bitmap("UnfilledCircle.png"); // Weist den Inhalt der Bilddatei mit dem angegebenen Dateinamen der Variablen der Klasse Bitmap hinzu  FloodFill(bitmap, new Point(200, 200), Color.Red); // Aufruf der Methode mit den Parametern für Startpixel und Farbe  bitmap.Save("FilledCircle.png"); // Speichert das geänderte Bitmap als Bilddatei mit dem angegebenen Dateinamen  }  } } 

Python

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 iterative 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 Implementierung

Bei teiliterativer Implementierung 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 Overflow weniger wahrscheinlich.

Einzelnachweise

1. Rosetta Code: Bitmap/Flood fill
2. GeeksforGeeks: Flood fill Algorithm
3. Tiefensuche von zusammenhängenden Nodes in Minetest