Labyrinth Lösungsalgorithmus II: Unterschied zwischen den Versionen
Keine Bearbeitungszusammenfassung |
Keine Bearbeitungszusammenfassung |
||
| Zeile 11: | Zeile 11: | ||
= Durchführung = | = Durchführung = | ||
Der verwendete Algorithmus basiert darauf, dass ein Labyrinth immer mindestens aus zwei Wänden bestehen muss. Berührt man zum Beispiel dauerhaft mit der rechten Hand die Wand, welche rechts von einem liegt und folgt dieser, dann erreicht man so in einem klassischen Labyrinth den Ausgang. Gleiches gilt ebenfalls für die linke Seite, sodass diese beiden Wände die Hauptwände des Labyrinths darstellen. Diese gilt es zu ermitteln. Wenn sie extrahiert wurden, kann der Weg zwischen den beiden Hauptwänden, welcher genau den Lösungsweg durch das Labyrinth symbolisiert, mithilfe von morphologischen Operationen bestimmt werden. Dazu wird eine der beiden Wände solange dilatiert, bis sich diese Wand mit der zweiten Wand überlappt, sodass um die gesamte Breite des Ganges zwischen den beiden Wänden dilatiert wurde. Wenn das geschehen ist, werden zunächst Löcher innerhalb des dilatierten Gebietes aufgefüllt und anschließend die Wand wieder erodiert. Die Differenz zwischen dem aufgefüllten und dem erodierten Gebiet spiegelt dabei genau den gesuchten und kürzesten Weg durch das Labyrinth wieder. | |||
Um diesen Algorithmus mithilfe des Programms MATLAB zu implementieren, wird wie folgt vorgegangen: | |||
* Bild einlesen und in Grauwertbild umwandeln | |||
* Bild in Binärbild konvertieren und invertieren | |||
* Unterschiedliche Regionen ermitteln | |||
* Hauptwände des Labyrinths ermitteln | |||
* Weg zwischen Hauptwände mithilfe von morphologischen Operationen ermitteln | |||
== Umwandlung in Grauwertbild == | |||
/ | |||
== Konvertierung in Binärbild == | |||
/ | |||
== Ermittlung der Regionen == | |||
/ | |||
== Ermittlung der Wände des Labyrinths == | |||
/ | |||
== Ermittlung des Weges zwischen Wänden == | |||
/ | / | ||
| Zeile 16: | Zeile 45: | ||
= Dokumentation = | = Dokumentation = | ||
Link zu Youtube-Video | |||
= Fazit und Ausblick = | = Fazit und Ausblick = | ||
| Zeile 87: | Zeile 116: | ||
= Literatur = | = Literatur = | ||
* Tönnies, Klaus D.: Grundlagen der Bildverarbeitung. München: Pearson Studium, 2005. | |||
→ zurück zum Hauptartikel: [[DSB SoSe2016|DSB SoSe2016]] | → zurück zum Hauptartikel: [[DSB SoSe2016|DSB SoSe2016]] | ||
Version vom 14. Juni 2016, 10:44 Uhr
Autoren: Marcus Irmer
Betreuer: Prof. Schneider
Einleitung
Dieser Artikel wurde im Rahmen der Lehrveranstaltung Digitale Signal- und Bildverarbeitung verfasst und dokumentiert die Ergebnisse des Projektes "Labyrinth Lösungsalgorithmus II". Die allgemeinen Ziele der Projekte können im Wiki-Artikel DSB SoSe2016 eingesehen werden.
Aufgabenstellung
Aufgabenstellung ist es, einen Algorithmus zu implementieren, der es ermöglicht, ein Bild einzulesen, auf welchem ein klassisches Labyrinth zu sehen ist. Das Labyrinth besitzt einen Eingang und einen Ausgang. Die Wände des Labyrinths sind durch dunkle Striche auf einem hellen Untergrund Symbolisiert (siehe Abbildung: ABBILDUNG EINFFÜGEN). Das Foto wird daraufhin nach den Algorithmen der Bildverarbeitung formatiert, sodass das Labyrinth auf dem Foto gefunden, entzerrt und extrahiert werden kann. Zur Lösung der Aufgabenstellung wird das Programm MATLAB benutzt.
Durchführung
Der verwendete Algorithmus basiert darauf, dass ein Labyrinth immer mindestens aus zwei Wänden bestehen muss. Berührt man zum Beispiel dauerhaft mit der rechten Hand die Wand, welche rechts von einem liegt und folgt dieser, dann erreicht man so in einem klassischen Labyrinth den Ausgang. Gleiches gilt ebenfalls für die linke Seite, sodass diese beiden Wände die Hauptwände des Labyrinths darstellen. Diese gilt es zu ermitteln. Wenn sie extrahiert wurden, kann der Weg zwischen den beiden Hauptwänden, welcher genau den Lösungsweg durch das Labyrinth symbolisiert, mithilfe von morphologischen Operationen bestimmt werden. Dazu wird eine der beiden Wände solange dilatiert, bis sich diese Wand mit der zweiten Wand überlappt, sodass um die gesamte Breite des Ganges zwischen den beiden Wänden dilatiert wurde. Wenn das geschehen ist, werden zunächst Löcher innerhalb des dilatierten Gebietes aufgefüllt und anschließend die Wand wieder erodiert. Die Differenz zwischen dem aufgefüllten und dem erodierten Gebiet spiegelt dabei genau den gesuchten und kürzesten Weg durch das Labyrinth wieder.
Um diesen Algorithmus mithilfe des Programms MATLAB zu implementieren, wird wie folgt vorgegangen:
- Bild einlesen und in Grauwertbild umwandeln
- Bild in Binärbild konvertieren und invertieren
- Unterschiedliche Regionen ermitteln
- Hauptwände des Labyrinths ermitteln
- Weg zwischen Hauptwände mithilfe von morphologischen Operationen ermitteln
Umwandlung in Grauwertbild
/
Konvertierung in Binärbild
/
Ermittlung der Regionen
/
Ermittlung der Wände des Labyrinths
/
Ermittlung des Weges zwischen Wänden
/
Dokumentation
Link zu Youtube-Video
Fazit und Ausblick
/
Weiterführende Informationen zu den benutzten MATLAB-Funktionen
Aufruf am 13.06.16
Literatur
- Tönnies, Klaus D.: Grundlagen der Bildverarbeitung. München: Pearson Studium, 2005.
→ zurück zum Hauptartikel: DSB SoSe2016