Hochwasserfüllung: Flood Fill: Erkundung des dynamischen Terrains der Computer Vision

Von Fouad Sabry

Was ist Flood Fill

Flood Fill, auch Seed Fill genannt, ist ein Flooding-Algorithmus, der den Bereich bestimmt und ändert, der mit einem bestimmten Knoten in einem mehrdimensionalen Array verbunden ist mit einem passenden Attribut. Es wird im „Eimer“-Füllwerkzeug von Malprogrammen verwendet, um verbundene, ähnlich gefärbte Bereiche mit einer anderen Farbe zu füllen, und in Spielen wie Go und Minesweeper, um zu bestimmen, welche Teile entfernt werden. Eine Variante namens „Boundary Fill“ verwendet dieselben Algorithmen, ist jedoch als der Bereich definiert, der mit einem bestimmten Knoten verbunden ist, der kein bestimmtes Attribut aufweist.

Ihre Vorteile

(I) Einblicke und Validierungen zu den folgenden Themen:

Kapitel 1: Flutfüllung

Kapitel 2: Scanline-Rendering

Kapitel 3: Tiefe -erste Suche

Kapitel 4: Quadtree

Kapitel 5: Graphdurchquerung

Kapitel 6: Beschriftung verbundener Komponenten

Kapitel 7: Watershed (Bildverarbeitung)

Kapitel 8: Labyrinth-Lösungsalgorithmus

Kapitel 9: Ray Casting

Kapitel 10: Box Blur

(II) Beantwortung der häufigsten öffentlichen Fragen zu Flood Fill.

(III) Beispiele aus der Praxis für die Verwendung von Flood Fill in vielen Bereichen.

Für wen dieses Buch gedacht ist

Profis, Studenten und Doktoranden, Enthusiasten, Bastler und diejenigen, die über das Grundwissen oder die Informationen für jede Art von Flood Fill hinausgehen möchten.

 

 

• Sprache: Deutsch
• Herausgeber: Eine Milliarde Sachkundig [German]
• Erscheinungsdatum: 4. Mai 2024

Buchvorschau

Kapitel 1: Flutfüllung

Flood Fill, auch bekannt als Seed Fill, ist ein Flooding-Algorithmus, der den Bereich in einem mehrdimensionalen Array auswählt und ändert, das einem bestimmten Knoten mit einem bestimmten Attribut zugeordnet ist. Es wird in Spielen wie Go und Minesweeper verwendet, um zu bestimmen, welche Teile gelöscht werden, sowie im Eimer-Füllwerkzeug von Malanwendungen, um verbundene, ähnlich gefärbte Bereiche mit einem bestimmten Farbton zu füllen. Der Bereich, der mit einem bestimmten Knoten verbunden ist, aber kein bestimmtes Attribut hat, ist das, was mit der Variation gemeint ist, die als Randfüllung bekannt ist und die gleichen Techniken verwendet.

Beachten Sie, dass beim Füllen von Flächen bestimmte Pixel in spitzeren Ecken fehlen, was es für das Zeichnen von gefüllten Polygonen ungeeignet macht. Aktivieren Sie stattdessen die Ungleich-Null-Regel und die Gerade-Ungerade-Regel.

Für den klassischen Flood-Fill-Algorithmus sind drei Variablen erforderlich: ein Startknoten, eine Zielfarbe und eine Ersatzfarbe. Die Methode wechselt zur Ersatzfarbe für jeden Knoten im Array, der über einen Pfad mit dem Startknoten verbunden ist, der die Zielfarbe darstellt. Anstelle der Zielfarbe wird eine Rahmenfarbe für eine Begrenzungsfüllung bereitgestellt.

Stattdessen werden in den folgenden Beschreibungen zwei Routinen bereitgestellt, um die Methode in der üblichen Weise zu verallgemeinern. Dazu gehören Set, das ein Pixel oder einen Knoten füllt, und Inside, das true für nicht gefüllte Punkte zurückgibt, die sich aufgrund ihrer Farbe innerhalb des gefüllten Bereichs befinden würden. Sobald Set auf einem Knoten aufgerufen wurde, muss er das Inside verlassen.

Es gibt zwei Versionen, je nachdem, ob wir Knoten, die sich an den Ecken berühren, als verbunden zählen oder nicht: Acht-Wege- bzw. Vier-Wege-Knoten.

Im Folgenden finden Sie die früheste bekannte Vier-Wege-Flood-Fill-Implementierung, die implizit stapelbasiert ist:

Flood-Fill (Knoten):

1. Wenn der Knoten nicht Inside  ist, kehren Sie zurück.

2. Festlegen des Knotens

3. Führen Sie Flood-filling einen Schritt südlich des Knotens durch.

4. Führen Sie die Flutfüllung einen Schritt nördlich des Knotens durch

5. Führen Sie Flood-Fill einen Schritt westlich des Knotens durch

6. Führen Sie Flood-Fill einen Schritt östlich des Knotens durch

7. Rückgabe.

In Sprachen und Situationen, in denen der Stapelplatz extrem eingeschränkt ist, ist die Implementierung der oben verwendeten Technik einfach zu verstehen, aber nicht praktikabel (z. B. Mikrocontroller).

Ein Stapelüberlauf wird vermieden, indem die Rekursion in eine Datenstruktur verschoben wird, z. B. in einen Stapel oder eine Warteschlange. Die Wahl der Datenstruktur wirkt sich auf das Proliferationsmuster aus, ähnelt jedoch der einfachen rekursiven Methode, da sie die Knoten zur Nutzung in einen Stapel oder eine Warteschlange schiebt, anstatt rekursive Aufrufe durchzuführen:

Flood-Fill (Knoten):

1. Setzen Sie Q auf die leere Warteschlange oder den leeren Stapel.

2. Fügen Sie den Knoten am Ende von Q hinzu.

3. Solange Q nicht leer ist:

4. Setze n gleich dem ersten Element von Q.

5. Entfernen Sie das erste Element aus Q.

6. Wenn n drin ist:

Setzen Sie die Option n

Fügen Sie den Knoten westlich von n am Ende von Q hinzu.

Fügen Sie den Knoten östlich von n am Ende von Q hinzu.

Fügen Sie den Knoten nördlich von n bis zum Ende von Q hinzu.

Fügen Sie den Knoten südlich von n bis zum Ende von Q hinzu.

7. Wiederholen Sie die Schleife, bis Q erschöpft ist.

8. Rückgabe.

Bevor Sie einen Knoten zum Stapel oder zur Warteschlange hinzufügen, bestimmen Sie seine Pixelfarbe und legen Sie sie fest, um die Größe des Stapels oder der Warteschlange zu minimieren.

Verwenden Sie eine Schleife, um sich in Ost-West-Richtung zu bewegen, während Sie Pixel oben und unten in die Warteschlange stellen (was den Algorithmen zum Füllen von Spannen ähnelt, siehe unten).

Um Out-of-Order-Prozessoren mehr Möglichkeiten zur Parallelisierung zu bieten, verschachteln Sie zwei oder mehr Kopien des Codes mit zusätzlichen Stapeln und Warteschlangen.

Verwenden Sie mehrere Threads, idealerweise mit leicht unterschiedlichen Besuchsplänen, damit sie sich nicht an einem Ort versammeln.

Unkomplizierte Methode, die einfach und fehlerfrei zu erstellen ist.

Speicherintensiv, insbesondere bei Verwendung eines Stacks.

Testet die am häufigsten gefüllten Pixel insgesamt viermal.

Das Füllen von Mustern ist nicht möglich, da die Ergebnisse von Pixeltests geändert werden müssen.

Das Zugriffsmuster für die Warteschlangenvariante ist nicht cachefreundlich.

Schwierig zu optimieren für Bitebenen oder Multi-Pixel-Wörter.

Die Arbeit mit Spannweiten, einer Zeile mit konstantem y, ermöglicht eine weitere Optimierung. Das erste veröffentlichte vollständige Beispiel funktioniert nach dem folgenden Grundsatz:.

Füllen Sie links und rechts nach einem Keimpunkt. Behalten Sie den Überblick über die am weitesten links und ganz rechts gefüllten Punkte, lx bzw. rx. Damit ist die Reichweite festgelegt.

Suchen Sie nach weiteren Startpunkten, indem Sie von lx nach rx oberhalb und unterhalb des aktuellen Startpunkts scannen.

Der Scanvorgang ist so optimiert, dass nur die Seed-Punkte am Anfang der folgenden Spanne neu gestartet werden müssen. Eine Warteschlange untersucht zuerst Spannen, während ein Stapel zuerst Spannen in Bezug auf die Tiefe untersucht.

Obwohl die am meisten gefüllten Pixel insgesamt dreimal überprüft werden, ist dieser Ansatz in Bezug auf Implementierungen und Zitate der gebräuchlichste.

fn fill(x, y):

wenn nicht Inside(x, y), dann return

let s = neuer leerer Stack oder neue Warteschlange

Addieren Sie (x, y) zu s

während s nicht leer ist:

Entfernen eines (x, y) aus s

let lx = x

while Inside(lx - 1, y):

Satz(lx - 1, y)

lx = lx - 1

while Inside(x, y):

Satz(x, y)

x = x + 1

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

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

Fn-Scan (lx, rx, y, s):

let span_added = false

für x in lx .. rx:

wenn nicht Inside(x, y):

span_added = falsch

Andernfalls, wenn nicht span_added:

Addieren Sie (x, y) zu s

span_added = wahr

Im Laufe der Zeit wurden folgende Verbesserungen vorgenommen:

Ein neuer Scan müsste nicht in die Warteschlange gestellt werden, wenn er sich vollständig innerhalb einer übergeordneten Spanne befände, da er nur gefüllte Pixel erkennen würde.

Darüber hinaus müssen nur die Überhänge (U-Turns und W-Turns) gescannt werden, wenn ein neuer Scan eine übergeordnete Spanne kreuzt.

Sie können sich bei der Suche nach Samen satt machen.

fn fill(x, y):

wenn nicht Inside(x, y), dann return

let s = neue leere Warteschlange oder neuer Stack

Addieren Sie (x, x, y, 1) zu s

Addieren Sie (x, x, y - 1, -1) zu s

während s nicht leer ist:

Entfernen Sie ein (x1, x2, y, dy) aus s

Sei x = x1

if Inside(x, y):

while Inside(x - 1, y):

Satz(x - 1, y)

x = x - 1

Wenn x < x1:

Addiere (x, x1-1, y-dy, -dy) zu s

während x1 <= x2:

while Inside(x1, y):

Satz(x1, y)

x1 = x1 + 1

Addiere (x, x1 - 1, y+dy, dy) zu s

Wenn x1 - 1 > x2:

Addiere (x2