Algorithmen zur Erkennung von Bildumrissen

Der Artikel stellt die vier häufigsten Algorithmen zur Schleifenerkennung vor.

Die ersten beiden, nämlich der Algorithmus zum Verfolgen von Quadraten und Verfolgen der Umgebung von Moore, sind einfach zu implementieren und werden daher häufig zur Bestimmung der Kontur eines bestimmten Musters verwendet. Leider weisen beide Algorithmen mehrere Schwächen auf, die es aufgrund ihrer besonderen Art der Nachbarschaft unmöglich machen, die Kontur einer großen Klasse von Mustern zu erkennen.

Diese Algorithmen ignorieren alle „Löcher“ im Muster. Wenn wir beispielsweise ein Muster ähnlich dem in Abbildung 1 gezeigten haben, ist die von den Algorithmen erkannte Schaltung ähnlich der in Abbildung 2 gezeigten (der Umriss wird durch blaue Pixel angezeigt). In einigen Anwendungsbereichen ist dies durchaus akzeptabel, in anderen Bereichen, beispielsweise bei der Zeichenerkennung, ist jedoch die Erkennung der internen Teile eines Musters erforderlich, um alle Räume zu finden, die ein bestimmtes Zeichen unterscheiden. ( Abbildung 3 zeigt den „vollständigen“ Umriss des Musters.)



Um eine vollständige Kontur zu erhalten, ist es daher erforderlich, zuerst den "Lochsuch" -Algorithmus zu verwenden, der die Löcher in einem gegebenen Muster bestimmt, und dann den Konturerkennungsalgorithmus auf jedes Loch anzuwenden.

Was ist Konnektivität?

In digitalen Bildern mit Binärwerten kann ein Pixel einen der folgenden Werte haben: 1 - wenn es Teil des Musters ist, oder 0 - wenn es Teil des Hintergrunds ist, d.h. keine Abstufung von Grau. (Wir gehen davon aus, dass Pixel mit einem Wert von 1 schwarz und Pixel mit einem Wert von 0 weiß sind.)

Um Objekte in einem digitalen Muster zu identifizieren, müssen wir Gruppen von schwarzen Pixeln finden, die miteinander „verbunden“ sind. Mit anderen Worten, die Objekte in einem gegebenen digitalen Muster sind die verbundenen Komponenten dieses Musters.

Im allgemeinen Fall ist eine verbundene Komponente ein Satz schwarzer Pixel P , so dass für jedes Pixelpaar p _i und p _j in P eine Folge von Pixeln p _i , ..., p _{j vorhanden ist,} so dass:

a) alle Pixel in der Sequenz befinden sich in der Menge P , d.h. sind schwarz und

b) Alle 2 Pixel in der Sequenz nebeneinander sind „Nachbarn“.

Eine wichtige Frage stellt sich: Wann können wir sagen, dass 2 Pixel „Nachbarn“ sind? Da wir quadratische Pixel verwenden, ist die Antwort auf die vorherige Frage aus folgendem Grund nicht trivial: Bei der quadratischen Tessellation haben Pixel eine gemeinsame Kante oder einen gemeinsamen Scheitelpunkt oder nichts gemeinsam. Jedes Pixel hat 8 Pixel gemeinsam; solche Pixel bilden die "Moore-Nachbarschaft" dieses Pixels. Sollten wir "Nachbar" -Pixel betrachten, die nur einen gemeinsamen Scheitelpunkt haben? Oder müssen zwei Pixel eine gemeinsame Kante haben, um als „Nachbarn“ betrachtet zu werden?

Es gibt also zwei Arten von Konnektivität: 4-Verbundenheit und 8-Verbundenheit.

4-Verbindung

Wann können wir sagen, dass ein bestimmter Satz schwarzer Pixel 4-fach verbunden ist? Zunächst müssen Sie das Konzept eines 4-Nachbarn (auch als direkter Nachbar bezeichnet ) definieren:

4-Nachbarn-Definition : Ein Pixel Q ist ein 4-Nachbarn eines gegebenen Pixels P, wenn Q und P eine gemeinsame Kante haben. Die 4 Nachbarn des Pixels P (bezeichnet als P2, P4, P6 und P8 ) sind in 2 unten gezeigt.


Definition einer 4-verbundenen Komponente : Die Menge der schwarzen Pixel P ist eine 4-verbundene Komponente, wenn für jedes Paar von Pixeln p _i und p _j in P eine Folge von Pixeln p _i , ..., p _{j vorhanden ist,} so dass:

a) alle Pixel in der Sequenz befinden sich in der Menge P , d.h. sind schwarz und

b) Alle zwei Pixel, die in der Sequenz benachbart sind , sind 4 Nachbarn

Beispiele für 4-verbundene Muster

Die folgenden Diagramme zeigen Beispiele für 4 verbundene Muster:

8-Verbindung

Wann kann ich sagen, dass ein bestimmter Satz schwarzer Pixel mit 8 verbunden ist ? Zunächst müssen wir das Konzept eines 8-Nachbarn (auch indirekter Nachbar genannt ) definieren:

8-Nachbarn-Definition : Ein Pixel Q ist ein 8-Nachbarn (oder nur ein Nachbar ) eines gegebenen Pixels P, wenn Q und P eine gemeinsame Kante oder einen gemeinsamen Scheitelpunkt haben. Die 8 Nachbarn eines gegebenen Pixels P bilden die Moore-Nachbarschaft dieses Pixels.

Definition einer 8-verbundenen Komponente : Die Menge der schwarzen Pixel P ist eine 8-verbundene Komponente (oder nur eine verbundene Komponente ), wenn für jedes Paar von Pixeln p _i und p _j in P eine Folge von Pixeln p _i , ..., p _{j vorhanden ist,} so dass ::

a) alle Pixel in der Sequenz befinden sich in der Menge P , d.h. sind schwarz und

b) Alle zwei Pixel, die in dieser Sequenz benachbart sind , sind 8 Nachbarn

Hinweis : Alle 4-verbundenen Muster sind 8-verbunden, d. H. 4-verbundene Muster sind eine Teilmenge der vielen 8-verbundenen Muster. Andererseits kann ein 8-verbundenes Muster nicht 4-verbunden sein.

Beispiel für ein 8-verknüpftes Muster

Das folgende Diagramm zeigt ein Muster, das 8-fach, aber nicht 4-fach verbunden ist:

Ein Beispiel für ein nicht mit 8 verbundenes Muster:

Das folgende Diagramm zeigt ein Beispiel eines Musters, das nicht mit 8 verbunden ist, d.h. bestehend aus mehr als einer verbundenen Komponente (das Diagramm zeigt drei verbundene Komponenten):

Square Trace-Algorithmus

Idee

Die Idee hinter dem Square-Tracing-Algorithmus ist sehr einfach. Dies kann auf die Tatsache zurückgeführt werden, dass der Algorithmus einer der ersten Versuche war, die Kontur eines binären Musters zu erfassen.

Um zu verstehen, wie es funktioniert, braucht man ein wenig Fantasie ...

Angenommen, wir haben ein digitales Muster, beispielsweise eine Gruppe schwarzer Pixel auf einem Hintergrund weißer Pixel, d.h. auf dem Gitter; Finde das schwarze Pixel und deklariere es als unser " anfängliches " Pixel. (Das Finden des " anfänglichen " Pixels kann auf viele verschiedene Arten implementiert werden. Wir beginnen in der unteren linken Ecke des Rasters und scannen jede Pixelspalte von unten nach oben, von der linken Spalte nach rechts, bis wir auf ein schwarzes Pixel stoßen. Wir erklären es als " initial ". ".)

Stellen Sie sich nun vor, Sie sind ein Marienkäfer, der auf dem Startpixel steht (siehe Abbildung 1 unten). Um den Umriss eines Musters zu erhalten, müssen Sie Folgendes tun:

, , ,

, , ,

.

Die schwarzen Pixel, die Sie eingekreist haben, bilden den Umriss des Musters.


Ein wichtiger Aspekt des Square-Trace-Algorithmus ist der „Richtungssinn“. Drehungen nach links und rechts werden relativ zum aktuellen Standort ausgeführt, was davon abhängt, wie Sie zum aktuellen Pixel gelangt sind. Um die richtigen Bewegungen auszuführen, müssen Sie daher Ihre Richtung verfolgen.

Algorithmus

Das Folgende ist eine formale Beschreibung des Quadratverfolgungsalgorithmus:

Eingabe: Quadratische Tessellation T , die die verbundene Komponente P der schwarzen Zellen enthält.

Ausgabe: Zeile B (b ₁ , b ₂ , ..., b _k ) von Randpixeln, d.h. Kontur.

Starten Sie

• Definieren Sie B als leere Menge.
• Scannen Sie die Zellen T von unten nach oben und von links nach rechts, bis ein schwarzes Pixel s von P gefunden wird .
• Fügen Sie s in B ein.
• Machen Sie das aktuelle Pixel p zum Anfangspixel s .
• Biegen Sie links ab, d.h. Gehe zum benachbarten Pixel links von p .
• Update p , d.h. es wird das aktuelle Pixel.
• Während p nicht gleich s ist , führen Sie aus
  
  Wenn das aktuelle Pixel p schwarz ist
  
  • füge p in B ein und drehe dich nach links (gehe zum benachbarten Pixel links von p ).
  • Update p , d.h. es wird das aktuelle Pixel.
  
  sonst
  
  • Biegen Sie rechts ab (gehen Sie zum nächsten Pixel rechts von p ).
  • Update p , d.h. es wird das aktuelle Pixel.
  
  Ende des "Bye" -Zyklus

Das Ende

Hinweis: Die Konzepte "links" und "rechts" sollten nicht in Bezug auf die Seite oder den Leser berücksichtigt werden, sondern in Bezug auf die Richtung des Eintritts in das "aktuelle" Pixel während des Scannens.

Demonstration

Das Folgende ist eine animierte Demonstration, wie der Quadratverfolgungsalgorithmus den Umriss eines Musters erkennt. Vergessen Sie nicht, dass sich der Marienkäfer in Pixel bewegt. Beachten Sie, wie sich die Richtung ändert, wenn Sie nach links und rechts abbiegen. Drehungen nach links und rechts werden relativ zur aktuellen Richtung in einem Pixel ausgeführt, d.h. Marienkäfer Orientierung.

Analyse

Es stellt sich heraus, dass die Fähigkeiten des Square-Trace-Algorithmus sehr begrenzt sind. Er ist nicht in der Lage, die Konturen einer großen Familie von Mustern zu erkennen, die in realen Anwendungen häufig auftreten.

Dies ist hauptsächlich auf die Tatsache zurückzuführen, dass Links- und Rechtsdrehungen Pixel nicht berücksichtigen, die sich „entlang“ befinden
Diagonalen “vom aktuellen Pixel.

Schauen wir uns die verschiedenen Muster mit unterschiedlicher Konnektivität an und sehen, warum der Square-Trace-Algorithmus fehlschlägt. Darüber hinaus werden wir Möglichkeiten untersuchen, um die Fähigkeiten des Algorithmus zu verbessern und ihn auch mit Mustern funktionieren zu lassen, die eine besondere Art von Konnektivität aufweisen.

Stoppkriterium

Eine der Schwächen des Algorithmus ist die Wahl eines Stoppkriteriums. Mit anderen Worten, wann hört ein Algorithmus auf, ausgeführt zu werden?

In der ursprünglichen Beschreibung des Quadratverfolgungsalgorithmus besteht die Abschlussbedingung darin, das Anfangspixel ein zweites Mal zu treffen. Es stellt sich heraus, dass der Algorithmus, wenn er von einem solchen Kriterium abhängt, die Konturen einer großen Familie von Mustern nicht erkennen kann.

Das Folgende ist eine animierte Demo, die erklärt, wie der Algorithmus aufgrund der Auswahl eines schlechten Stoppkriteriums die genaue Kontur des Musters nicht erkennen kann:


Wie Sie sehen können, kann die Verbesserung des Stoppkriteriums ein guter Anfang sein, um die Gesamtleistung des Algorithmus zu verbessern. Es gibt zwei effektive Alternativen für ein vorhandenes Abschaltkriterium:

a) Stoppen Sie nur, indem Sie das Startpixel n- mal besuchen, wobei n mindestens 2 ODER ist

b) Halten Sie an, nachdem Sie das Startpixel ein zweites Mal getroffen haben, so wie wir es ursprünglich getroffen haben.

Dieses Kriterium wurde von Jacob Eliosoff vorgeschlagen, daher werden wir es das Kriterium nennen, um Jacob aufzuhalten .

Das Ändern des Stoppkriteriums verbessert im Allgemeinen die Effektivität des Quadratverfolgungsalgorithmus, ermöglicht jedoch nicht die Überwindung anderer Schwächen, die es bei Mustern mit speziellen Konnektivitätstypen aufweist.

Der Square Tracing-Algorithmus kann die Kontur einer Musterfamilie mit einer Konnektivität von 8 nicht erkennen, die KEINE Konnektivität von 4 aufweist.

Das Folgende ist eine animierte Demonstration, wie der Square-Trace-Algorithmus (mit Jacobs Stoppkriterium) den korrekten Umriss eines Musters mit Konnektivität 8 ohne Konnektivität 4 nicht erkennt:

Ist dieser Algorithmus völlig nutzlos?

Wenn Sie die obige Analyse lesen, denken Sie wahrscheinlich, dass der Square-Trace-Algorithmus die Umrisse der meisten Muster nicht erkennt. Aber es stellt sich heraus. dass es eine spezielle Familie von Mustern gibt, in denen der Pfad vom Quadratverfolgungsalgorithmus vollständig erkannt wird.

Sei P die Menge schwarzer Pixel mit Konnektivität 4 im Raster. Lassen Sie die weißen Pixel des Gitters, d.h. Die Hintergrundpixel W haben auch eine Konnektivität von 4. Es stellt sich heraus, dass unter solchen Bedingungen des Musters und seines Hintergrunds bewiesen werden kann, dass der Quadratverfolgungsalgorithmus (mit dem Jacob-Stopp-Kriterium) die Bestimmung der Kontur immer erfolgreich handhabt.

Unten ist der Beweis, dass in dem Fall, in dem sowohl das Muster als auch die Hintergrundpixel 4 verbunden sind, der Quadratverfolgungsalgorithmus die Kontur korrekt bestimmt, wenn das Jacob-Stopp-Kriterium verwendet wird.

Beweis
Gegeben : Das Muster P ist derart, dass alle Pixel des Musters (d. H. Schwarz) und die Hintergrundpixel (d. H. Weiß) W eine Konnektivität von 4 haben.

Erste Beobachtung

Da der Satz weißer Pixel W eine Konnektivität von 4 hat, bedeutet dies, dass das Muster keine „ Löcher “ enthalten kann (informell ausgedrückt bedeuten „ Löcher “ Gruppen weißer Pixel, die vollständig von schwarzen Pixeln des Musters umgeben sind).

Das Vorhandensein eines „ Lochs “ im Muster führt zur Trennung der Gruppe weißer Pixel von den verbleibenden weißen Pixeln. Viele weiße Pixel verlieren jedoch die Konnektivität 4.

Abbildung 2 und Abbildung 3 unten zeigen zwei Arten von „ Löchern “, die in einem Muster mit Konnektivität 4 auftreten können:



Zweite Beobachtung

Zwei beliebige schwarze Pixel eines Musters MÜSSEN eine gemeinsame Seite haben.

Angenommen, zwei schwarze Pixel haben nur einen gemeinsamen Scheitelpunkt. Um die Eigenschaft der 4-Verbundenheit des Musters zu erfüllen, muss es einen Pfad geben, der diese beiden Pixel verbindet, so dass alle zwei benachbarten Pixel auf diesem Pfad eine Konnektivität von 4 haben. Dies ergibt jedoch ein Muster ähnlich dem in Abbildung 3 . Mit anderen Worten führt dies zu einer Trennung der weißen Pixel. Fig. 4 unten zeigt ein typisches Muster, das die Annahme erfüllt, dass die Pixel in dem Muster und im Hintergrund 4-fach verbunden sind, d.h. haben keine " Löcher " und alle zwei schwarzen Pixel haben eine gemeinsame Seite:


Es ist nützlich, solche Muster wie folgt darzustellen:

Zuerst betrachten wir die Grenzpixel, d.h. Umriss des Musters. Wenn wir dann jedes Grenzpixel als 4 Kanten mit Einheitslänge betrachten, werden wir sehen, dass einige dieser Kanten mit benachbarten weißen Pixeln gemeinsam sind. Wir werden solche Kanten Grenzkanten nennen .

Solche Begrenzungskanten können als Kanten eines Polygons betrachtet werden. Auf dem Bild
In 5 unten wird diese Idee am Beispiel eines Polygons demonstriert, das dem Muster aus 4 oben entspricht:


Wenn wir alle möglichen „Konfigurationen“ von Grenzpixeln betrachten, die in solchen Mustern auftreten können, werden wir sehen, dass es zwei einfache Fälle gibt, die in Abbildung 6 und Abbildung 7 unten dargestellt sind.

Die Grenzpixel können Vielfache dieser Fälle oder andere Anordnungen sein, d.h. die Drehungen und Wendungen dieser beiden Fälle. Grenzrippen sind blau als E1, E2, E3 und E4 markiert.


Dritte Beobachtung

In den beiden oben genannten Fällen wird der Square-Trace-Algorithmus unabhängig von dem von uns gewählten Anfangspixel und in die Richtung, in die er fällt , niemals "zurückgehen" (Backtrack) , sondern niemals zweimal durch die Grenzkante "gehen" (Backtrack). nur wenn es den Rand kein zweites Mal verfolgt) und niemals die Grenzkante verfehlt. Probieren Sie es aus!

Hier müssen zwei Konzepte geklärt werden:

a) Der Algorithmus "geht zurück" , wenn er vor dem Verfolgen des gesamten Randes zurückkehrt, um ein bereits besuchtes Pixel zu besuchen, und

b) Für jede Begrenzungsrippe gibt es zwei Möglichkeiten, „durch sie hindurchzugehen“ , nämlich „nach innen“ und „nach außen“ (wobei „nach innen“ die Bewegung des entsprechenden Polygons nach innen und „nach außen“ - nach außen des Polygons bedeutet).

Wenn der Algorithmus außerdem "nach innen" durch eine der Grenzkanten geht, geht er "nach außen" durch die nächste Grenzkante, d. H. Der Square-Trace-Algorithmus sollte nicht in der Lage sein, zwei aufeinanderfolgende Kanten auf dieselbe Weise zu durchlaufen.

Letzte Beobachtung

Jedes Muster hat eine gerade Anzahl von Begrenzungskanten .

Wenn Sie sich das Polygon aus Abbildung 5 ansehen, sehen Sie Folgendes:

Wenn wir von dem im Diagramm markierten Scheitelpunkt S ausgehen und den Grenzkanten folgen möchten, bis wir wieder S erreichen, stellen wir fest, dass wir dabei eine gerade Anzahl von Grenzkanten überschreiten. Wir können jede Grenzkante als „Schritt“ in eine separate Richtung betrachten. Dann muss es für jeden „Schritt“ rechts einen entsprechenden „Schritt“ links geben, wenn wir in die Ausgangsposition zurückkehren möchten. Gleiches gilt für vertikale „Stufen“. Daher müssen die „Schritte“ entsprechende Paare haben, und dies erklärt, warum jedes dieser Muster eine gerade Anzahl von Grenzkanten aufweist.

Wenn der Algorithmus zum Verfolgen von Quadraten ein zweites Mal durch die anfängliche Grenzkante (des anfänglichen Pixels) eintritt, wird er dies in der gleichen Richtung wie beim ersten Mal tun.

Der Grund dafür ist, dass der Algorithmus zum zweiten Mal auf die gleiche Weise wie in die anfängliche Grenzkante durchläuft, da es zwei Möglichkeiten gibt, durch die Grenzkante zu gehen, und der Algorithmus sich abwechselnd nach innen und außen bewegt und es eine gerade Anzahl von Grenzkanten gibt erster.

Fazit

Im Fall eines 4-verbundenen Musters und Hintergrunds erkennt der Quadratverfolgungsalgorithmus den gesamten Rand, d.h. Kontur, Muster und hört nach einer einzelnen Spur auf zu arbeiten, d.h. es wird nicht erneut verfolgt, da es beim zweiten Erreichen der anfänglichen Grenzkante auf dieselbe Weise wie beim ersten Mal eingegeben wird. Folglich bestimmt der Quadratverfolgungsalgorithmus mit dem Stoppkriterium von Jacob den Zähler eines Musters korrekt, vorausgesetzt, dass sowohl das Muster als auch der Hintergrund 4-fach verbunden sind.

Verfolgung der Umgebung von Moore

Idee

Die Idee hinter der Moore-Neighbor-Verfolgung ist einfach; Bevor wir es erklären, müssen wir ein wichtiges Konzept erklären: die Moore-Nachbarschaft eines Pixels.

Die Nachbarschaft von Moore

Die Moore-Nachbarschaft eines Pixels P ist ein Satz von 8 Pixeln mit einem gemeinsamen Scheitelpunkt oder einer gemeinsamen Kante mit diesem Pixel. Solche Pixel, nämlich P1, P2, P3, P4, P5, P6, P7 und P8 , sind in Fig. 1 gezeigt .

Das Viertel Moore (auch 8-Nachbarn oder indirekte Nachbarn genannt ) ist ein wichtiges Konzept, auf das in der Literatur häufig Bezug genommen wird.


Jetzt sind wir bereit, uns mit der Idee vertraut zu machen, die der Spur der Umgebung von Moore zugrunde liegt.

Es sei ein digitales Muster vorhanden, d.h. eine Gruppe schwarzer Pixel auf einem Hintergrund weißer Pixel, d.h. auf dem Gitter; Finden Sie das schwarze Pixel und deklarieren Sie es zum " anfänglichen " Pixel. (Es gibt verschiedene Möglichkeiten, das „ anfängliche “ Pixel zu finden, aber wir beginnen wie zuvor in der unteren linken Ecke und scannen alle Pixelspalten der Reihe nach, bis wir das erste schwarze Pixel finden, das wir als „ initial “ deklarieren.)

Stellen Sie sich nun erneut vor, Sie sind ein Marienkäfer, der auf dem Startpixel steht (siehe Abbildung 2 unten). Ohne Verlust der Verallgemeinerung erkennen wir den Umriss, indem wir uns im Uhrzeigersinn um das Muster bewegen. (Egal für welche Richtung wir uns entscheiden, die Hauptsache ist, sie ständig im Algorithmus zu verwenden).

Die allgemeine Idee ist folgende: Jedes Mal, wenn wir zum schwarzen Pixel P gelangen, kehren wir zu dem weißen Pixel zurück, in dem wir zuvor standen. Dann gehen wir um das Pixel P im Uhrzeigersinn herum und besuchen jedes Pixel in seiner Nähe von Moore, bis wir zum schwarzen Pixel gelangen. Der Algorithmus wird beendet, wenn das Startpixel das Startpixel ein zweites Mal erreicht.

Diese schwarzen Pixel, die der Algorithmus besucht hat, bilden den Umriss des Musters.

Algorithmus

Das Folgende ist eine formale Beschreibung des Moore-Nachbarschaftsverfolgungsalgorithmus:

Eingabe: Quadratische Tessellation T, die eine verbundene Komponente P schwarzer Zellen enthält.

Ausgabe: Zeile B (b ₁ , b ₂ , ..., b _k ) von Grenzpixeln, d.h. Kontur.

Bezeichne mit M (a) die Moore-Nachbarschaft von Pixel a .

Sei p das aktuelle Randpixel.

Sei c das aktuell betrachtete Pixel, d.h. c ist in M (p) .

Starten Sie

• Definieren Sie B als leere Menge.
• Scannen Sie die Zellen T von unten nach oben und von links nach rechts, bis wir ein schwarzes Pixel s von P finden.
• Fügen Sie s in B ein.
• Wir setzen den Punkt s als den aktuellen Grenzpunkt p , d.h. p = s
• Gehen wir zurück, d.h. Gehen wir weiter zu dem Pixel, von dem wir zu s gekommen sind .
• Sei c das nächste Pixel im Uhrzeigersinn in M (p) .
• Während c nicht gleich s ist , führen Sie aus
  
  
  • wenn c schwarz ist
    
    • Fügen Sie c in B ein
    • wir setzen p = c
    • gehe zurück (verschiebe das aktuelle Pixel c zu dem Pixel, von dem wir zu p gekommen sind )
    
    sonst
    
    • Bewegen Sie das aktuelle Pixel c in M (p) zum nächsten Pixel im Uhrzeigersinn.
    
    Ende des Tschüss-Zyklus

Das Ende

Demonstration

Das Folgende ist eine animierte Demonstration, wie Moores Nachbarschaftsspur die Musterkonturerkennung durchführt. (Wir haben beschlossen, den Umriss im Uhrzeigersinn zu verfolgen.)

Analyse

Die Hauptschwäche bei der Verfolgung der Umgebung von Moore liegt in der Wahl der Stoppkriterien.

In der ursprünglichen Beschreibung des Algorithmus zum Verfolgen der Umgebung von Moore besteht das Stoppkriterium darin, das Anfangspixel ein zweites Mal zu treffen. Ähnlich wie beim Quadratverfolgungsalgorithmus stellt sich heraus, dass die Verfolgung der Umgebung von Moore unter Verwendung dieses Kriteriums die Konturen einer großen Familie von Mustern nicht erkennen kann.

Das Folgende ist eine animierte Demo, die erklärt, warum der Algorithmus aufgrund der Auswahl eines schlechten Stoppkriteriums den genauen Umriss des Musters nicht finden kann:


Wie Sie sehen können, kann die Verbesserung des Stoppkriteriums ein guter Anfang sein, um die Gesamtleistung der Ablaufverfolgung zu verbessern. Es gibt zwei effektive Alternativen für das Abschaltkriterium, ähnlich dem Jacob-Abschaltkriterium.

Die Verwendung des Jacob-Kriteriums verbessert die Effektivität der Verfolgung der Umgebung von Moore erheblich und macht es zum besten Algorithmus zur Bestimmung der Kontur eines Musters, unabhängig von seiner Konnektivität.

Der Grund dafür liegt hauptsächlich darin, dass der Algorithmus die gesamte Moore-Nachbarschaft des Grenzpixels überprüft, um nach dem nächsten Grenzpixel zu suchen. Im Gegensatz zum quadratischen Trace-Algorithmus, der sich nur nach links und rechts dreht und die Pixel "diagonal" verfehlt, kann die Nachbarschaftsspur von Moore immer die äußere Grenze einer verbundenen Komponente erkennen. Der Grund ist folgender: Für jedes 8-verbundene (oder einfach verbundene ) Muster liegt das nächste Randpixel in der Moore-Nachbarschaft des aktuellen Randpixels. Da die Nachbarschaftsspur von Moore jedes der Pixel in der Nachbarschaft von Moore des aktuellen Grenzpixels überprüft, muss sie das nächste Grenzpixel erkennen.

Wenn die Verfolgung der Nachbarschaft von Moore das erste Pixel ein zweites Mal auf dieselbe Weise wie beim ersten Mal erreicht, bedeutet dies, dass eine vollständige Außenkontur des Musters erkannt wurde, und wenn der Algorithmus nicht gestoppt wird, erkennt er erneut dieselbe Kontur.

Radialer Scan

Der Radial Sweep-Algorithmus ist ein Konturerkennungsalgorithmus, der in einigen Büchern diskutiert wird. Trotz des komplexen Namens ist die zugrunde liegende Idee sehr einfach. Tatsächlich stellt sich heraus, dass der Radial-Sweep-Algorithmus mit der Spur von Moores Umgebung identisch ist . Man könnte fragen: "Warum erwähnen wir ihn überhaupt?"

Wenn Sie die Umgebung von Moore verfolgen, suchen Sie in der Nähe von Moore nach dem aktuellen Grenzpixel in einer bestimmten Richtung (wir haben die Richtung im Uhrzeigersinn gewählt), bis ein schwarzes Pixel gefunden wird. Sie deklariert dieses Pixel dann als aktuelles Grenzpixel und fährt fort.

Der Radial-Scan-Algorithmus macht dasselbe. Andererseits bietet es eine interessante Möglichkeit, das nächste schwarze Pixel in der Moore-Nachbarschaft eines bestimmten Grenzpixels zu finden.

Die Methode basiert auf der folgenden Idee:

Jedes Mal, wenn wir ein neues Grenzpixel finden, machen Sie es zum aktuellen Pixel P und zeichnen Sie ein imaginäres Liniensegment , das P mit dem vorherigen Grenzpixel verbindet. Dann drehen wir das Segment relativ zu P im Uhrzeigersinn, bis es auf ein schwarzes Pixel in der Moore-Nachbarschaft von Pixel P stößt. Die Drehung der Linie ist identisch mit der Überprüfung jedes Pixels in der Nähe von Moore P.

Wir haben eine animierte Demonstration erstellt, wie der Radial-Scan-Algorithmus funktioniert und wie es aussieht, als würde man die Umgebung von Moore nachzeichnen.


Und wann stoppt der Radial-Sweep-Algorithmus?

Lassen Sie uns das Verhalten des Algorithmus anhand der folgenden Stoppkriterien erklären ...

Stoppkriterium 1

Lassen Sie den Radial-Scan-Algorithmus abgeschlossen, wenn er das erste Pixel ein zweites Mal besucht.

Unten finden Sie eine animierte Demo, aus der hervorgeht, warum das Unterbrechungskriterium korrekt geändert wird.


Es ist auch erwähnenswert, dass bei Verwendung dieses Stoppkriteriums in beiden Algorithmen die Wirksamkeit des Radial-Scan-Algorithmus mit der Verfolgung der Umgebung von Moore identisch ist.

Im Square-Trace-Algorithmus und im Moore-Nachbarschafts-Trace haben wir festgestellt, dass die Verwendung des Jacob-Stop-Kriteriums die Leistung beider Algorithmen erheblich verbessert.

Jacob Stop - Kriterium erfordert , dass die Ausführung des Algorithmus angehalten , wenn Besuch Anfangspixel zum zweiten Mal in der gleichen Richtung wie die erste Zeit.

Leider können wir das Jacob-Stop-Kriterium nicht im Radial-Sweep-Algorithmus verwenden. Der Grund ist, dass der Radial-Scan-Algorithmus das Konzept nicht definiertDie "Richtung", in der es auf das Grenzpixel trifft . Mit anderen Worten, es ist nicht klar, in welche „Richtung“ der Algorithmus in das Grenzpixel gefallen ist (und seine Definition ist nicht trivial).

Daher müssen wir ein anderes Stoppkriterium vorschlagen, das nicht von der Richtung abhängt, in der ein bestimmtes Pixel getroffen wird, wodurch die Effektivität des Radial-Scan-Algorithmus verbessert werden kann ...

Stoppkriterium 2

Angenommen, jedes Mal, wenn der Algorithmus ein neues Grenzpixel P _i erkennt , wird es in eine Reihe von Grenzpixeln eingefügt : P ₁ , P ₂ , P ₃ , ..., P _i ; und als aktuelles Randpixel deklariert. ( P _{1 betrachten} wir das anfängliche Pixel). Dies bedeutet, dass wir das vorherige Randpixel P _i-1 jedes aktuellen Randpixels P _{i kennen} . (Für das Startpixel wird P _{0 angenommen}ist ein imaginäres Pixel, das keinem der Pixel auf dem Gitter entspricht, das dem Anfangspixel in der Reihe der Grenzpixel zugewandt ist .

Angesichts der obigen Annahmen können wir die Abbruchkriterien bestimmen , wie folgt:

Die Ausführung des Algorithmus wird beendet , wenn:

a) der aktuelle Grenzpixel P _i wurde zuvor als ein Pixel erfüllt P _j (wobei j <i ) in der Reihe der Randpixel, und

b) P _{i- 1} = P _j-1 .

Mit anderen Worten, der Algorithmus beendet die Ausführung, wenn er das Grenzpixel P in der Sekunde besuchtMal, wenn das Grenzpixel vor P (in der Reihe der Grenzpixel) zum zweiten Mal dasselbe Pixel ist, das vor P war, als P zum ersten Mal besucht wurde.

Wenn die Bedingung des Stoppkriteriums erfüllt ist und der Algorithmus nicht heruntergefahren wird, erkennt der Radial-Scan-Algorithmus die gleiche Grenze ein zweites Mal.

Die Leistung des Radial-Sweep-Algorithmus mit diesem Stoppkriterium ähnelt der Leistung der Verfolgung der Moore-Nachbarschaft mit dem Jacob-Stoppkriterium.

Theo Pavlidis Algorithmus

Idee

Dieser Algorithmus ist einer der neuesten von Theo Pavlidis vorgeschlagenen Algorithmen zur Schleifenerkennung . Er zitierte es in seinem 1982 erschienenen Buch Algorithmen für Grafik und Bildverarbeitung (Kapitel 7, Abschnitt 5). Es ist nicht so einfach wie der Algorithmus zum Verfolgen von Quadraten oder der Umgebung von Moore, aber es ist nicht so kompliziert (dies ist typisch für die meisten Kantenerkennungsalgorithmen).

Wir werden diesen Algorithmus nicht auf die gleiche Weise erklären, wie es in seinem Buch getan wurde. Unser Ansatz ist leichter zu verstehen und vermittelt eine Vorstellung von der allgemeinen Idee, die dem Algorithmus zugrunde liegt.

Ohne Verlust der Verallgemeinerung haben wir uns entschlossen, die Schleife im Uhrzeigersinn zu durchlaufen, um der Reihenfolge aller anderen im Artikel vorgestellten Algorithmen zu entsprechen. Auf der anderen Seite wählte Pavlidis die Richtung gegen den Uhrzeigersinn. Dies hat keinen Einfluss auf die Leistung des Algorithmus. Der einzige Unterschied ist die relative Richtung der Bewegungen, die wir ausführen, wenn wir die Kontur umgehen.

Kommen wir nun zur Idee ...

Nehmen wir an, wir haben ein digitales Muster, d. H. eine Gruppe schwarzer Pixel auf einem Hintergrund weißer Pixel, d.h. auf dem Gitter; Finden Sie das schwarze Pixel und deklarieren Sie es zum " anfänglichen " Pixel. Sie können auf verschiedene Arten nach dem " Start " -Pixel suchen , beispielsweise wie oben beschrieben.

Um die Initiale zu finden . , , :

,

: , . , , («» , ).

, , Ausgangspixel, wie in gezeigt Abbildung 1 unten. Während der Ausführung des Algorithmus sind wir nur an drei Pixeln vor Ihnen interessiert, d. H. P1, P2 und P3 in Abbildung 1 dargestellt . (Wir werden P2 als das Pixel vor Ihnen bezeichnen, P1 ist das Pixel links von P2 und P3 ist das Pixel rechts von P2 ).


Wie beim Square-Trace-Algorithmus ist das Wichtigste beim Pavlidis-Algorithmus der „Orientierungssinn“. Drehungen nach links und rechts beziehen sich auf die aktuelle Position. Dies hängt davon ab, wie Sie das aktuelle Pixel eingegeben haben. Um die richtigen Bewegungen auszuführen, ist es daher wichtig, Ihre aktuelle Ausrichtung im Auge zu behalten. Unabhängig davon, wie Sie sich befinden, werden die Pixel P1, P2 und P3 wie oben beschrieben bestimmt.

Mit Hilfe dieser Informationen sind wir bereit , um den Algorithmus zu erklären ...

Jedes Mal , wenn Sie auf dem aktuellen Randpixel stehen (das ist die erste anfängliche Pixel), wie folgt vorgehen:

Erstens , überprüfen Sie die Pixel P1 . Wenn P1 schwarz ist, deklarieren Sie P1das aktuelle Grenzpixel und bewegen Sie sich einen Schritt vorwärts und machen Sie dann einen Schritt nach links , um bei P1 zu sein (die Reihenfolge der Bewegungen ist sehr wichtig).

In Figur 2 unten veranschaulicht diesen Fall. Der Weg zu P1 ist blau dargestellt.


Und nur wenn P1 weiß ist, überprüfen wir P2 ...

Wenn P2 schwarz ist, deklarieren Sie P2 zum aktuellen Grenzpixel und gehen einen Schritt vorwärts , um auf P2 zu sein . Dieser Fall ist in Abbildung 3 dargestellt. Der Pfad, dem Sie auf P2 folgen müssen, wird blau angezeigt.


Nur wenn sowohl P1 als auch P2 weiß sind, überprüfen Sie P3 ...

Wenn P3 schwarz ist, deklarieren Sie P3 als aktuelles Randpixel und bewegen Sie sich einen Schritt nach rechts und dann einen Schritt nach links , wie in Abbildung 4 unten gezeigt.


Das ist alles! Drei einfache Regeln für drei einfache Fälle. Wie Sie sehen können, ist es wichtig, bei Kurvenfahrten die Richtung im Auge zu behalten, da alle Bewegungen relativ zur aktuellen Ausrichtung ausgeführt werden. Aber anscheinend haben wir etwas vergessen? Was ist, wenn alle drei Pixel vor uns weiß sind? Dann drehen wir uns (stehen am aktuellen Grenzpixel) um 90 Grad im Uhrzeigersinn, um einen neuen Satz von drei Pixeln vor uns zu sehen. Dann machen wir die gleiche Prüfung für diese neuen Pixel. Sie können immer noch die Frage bleibt: Was passiert , wenn alle diese drei Pixel werden weiß?! Dann drehen wir uns wieder um 90 Grad im Uhrzeigersinn und stehen am selben Pixel. Bevor Sie die gesamte Nachbarschaft von Moores Pixel überprüfen, können Sie dreimal drehen (jedes Mal um 90 Grad im Uhrzeigersinn).

Wenn wir dreimal drehen, ohne jemals schwarze Pixel zu finden, bedeutet dies, dass wir auf einem isolierten Pixel stehen , das mit keinem anderen schwarzen Pixel verbunden ist. Aus diesem Grund können Sie mit dem Algorithmus dreimal drehen und dann die Ausführung abschließen.

Ein weiterer Aspekt: Wann schließt der Algorithmus die Ausführung ab?

Der Algorithmus endet in zwei Fällen:

a) wie oben erwähnt. Mit dem Algorithmus können Sie dreimal drehen (jedes Mal um 90 Grad im Uhrzeigersinn), nachdem die Ausführung abgeschlossen und das Pixel als isoliert deklariert wurde.

b) Wenn das aktuelle Grenzpixel das Anfangspixel ist, schließt der Algorithmus die Ausführung ab, indem er „deklariert“, dass er den Musterumriss erkannt hat.

Algorithmus

Das Folgende ist eine formale Beschreibung des Pavlidis-Algorithmus:

Eingabe: Quadratische Tessellation T, die eine verbundene Komponente P von schwarzen Zellen enthält.

Ausgabe: Zeile B (b ₁ , b ₂ , ..., b _k ) von Grenzpixeln, d.h. Kontur.

Definitionen:

• Bezeichne mit p das aktuelle Grenzpixel, d.h. das Pixel, auf dem wir stehen.
• Definieren Sie P1, P2 und P3 wie folgt: (siehe auch Abbildung 1 oben)
• P2 ist das Pixel vor Ihnen, das an das Pixel angrenzt, auf dem Sie stehen, d. H. mit Pixel p .
• P1 — , P2 .
• P3 — , P2 .
• «» .

Starten Sie

• B .
• T , s P (. , )
• s B .
• p s .
• :
  P1
  
  • P1 B
  • p=P1
  • ,
  
  P2
  
  • P2 B
  • p=P2
  • (. 3)
  
  P3
  
  • P3 B
  • p=P3
  • , (. 4)
  
  90 , p
  
  • Beenden Sie das Programm und deklarieren Sie p als isoliertes Pixel
  
  sonst
  
  • um 90 Grad im Uhrzeigersinn drehen und dabei auf das aktuelle Pixel p stehen
  
  Bisher p = s (Ende der Wiederholungsschleife)

Das Ende

Demonstration

Das Folgende ist eine animierte Demonstration, wie der Pavlidis-Algorithmus die Kontur eines bestimmten Musters erkennt. Vergessen Sie nicht, dass wir in Pixeln gehen; Beachten Sie, wie sich die Ausrichtung ändert, wenn Sie nach links oder rechts drehen. Um den Algorithmus so detailliert wie möglich zu erklären, haben wir alle möglichen Fälle aufgenommen.

Analyse

Wenn Sie der Meinung sind, dass der Pavlidis-Algorithmus ideal zum Erkennen von Musterkonturen ist, sollten Sie Ihre Meinung ändern ...

Dieser Algorithmus ist wirklich etwas komplizierter als beispielsweise die Verfolgung der Umgebung von Moore, in der es keine Sonderfälle gibt, die eine separate Verarbeitung erfordern, aber er kann die Konturen eines großen nicht bestimmen Eine Familie von Mustern mit einer bestimmten Art von Konnektivität.

Der Algorithmus funktioniert sehr gut bei 4-verbundenen Mustern. Das Problem tritt auf, wenn einige 8-verbundene Muster verfolgt werden, die nicht 4-verbunden sind. Das Folgende ist eine animierte Demonstration, wie der Pavlidis-Algorithmus den korrekten Umriss eines 8-verbundenen Musters (kein 4-verbundenes) nicht erkennt - er überspringt den größten Teil der Grenze.


Es gibt zwei einfache Möglichkeiten, einen Algorithmus zu ändern, um seine Leistung erheblich zu verbessern.

a) Ersetzen Sie das Stoppkriterium

Anstatt den Algorithmus zu vervollständigen, wenn er das Startpixel ein zweites Mal besucht, können Sie ihn beenden, wenn er das Startpixel ein drittes oder sogar viertes Mal besucht. Dies verbessert die Gesamtleistung des Algorithmus.

ODER

b) Gehen Sie zur Quelle des Problems, nämlich bevor Sie das Startpixel auswählen.

Es gibt eine wichtige Einschränkung hinsichtlich der Richtung, in der die Eingabe in das Startpixel durchgeführt wird. Im Wesentlichen müssen Sie das Startpixel eingeben, damit das Pixel links von Ihnen weiß ist, wenn Sie darauf stehen. Der Grund für die Einführung dieser Einschränkung ist folgender: Da wir immer die drei Pixel vor uns in betrachtenIn einer bestimmten Reihenfolge überspringen wir in einigen Mustern das Grenzpixel, das direkt links vom Anfangspixel liegt.

Es besteht die Gefahr, dass nicht nur das linke Nachbarpixel im Anfangspixel fehlt, sondern auch das Pixel direkt darunter (wie in der Analyse gezeigt). Zusätzlich wird in einigen Mustern ein Pixel übersprungen, das dem Pixel R in 5 unten entspricht. Daher nehmen wir an, dass das Startpixel in einer solchen Richtung getroffen werden muss, dass die Pixel, die den in 5 unten gezeigten Pixeln L, W und R entsprechen , weiß sind.


In diesem Fall werden Muster wie das in der Demonstration gezeigte korrekt erkannt und die Wirksamkeit des Pavlidis-Algorithmus wird erheblich verbessert. Andererseits kann es schwierig sein, ein Anfangspixel zu finden, das diese Anforderungen erfüllt, und in vielen Fällen ist es unmöglich, ein solches Pixel zu finden. In diesem Fall sollten Sie eine alternative Methode zur Verbesserung des Pavlidis-Algorithmus verwenden, nämlich die Fertigstellung des Algorithmus nach dem dritten Besuch des Startpunkts.