Labyrinth Lösungsalgorithmus II: Unterschied zwischen den Versionen

Aus HSHL Mechatronik
Zur Navigation springen Zur Suche springen
(Die Seite wurde neu angelegt: „Autoren: Marcus Irmer<br /> Betreuer: Prof. Schneider = Aufgabenstellung = Aufgabenstellung ist es, …“)
 
Keine Bearbeitungszusammenfassung
 
(4 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 1: Zeile 1:
Autoren: [[Benutzer:Marcus Irmer|Marcus Irmer]]<br />
Autor: [[Benutzer:Marcus Irmer|Marcus Irmer]]<br />
Betreuer: [[Benutzer:Ulrich_Schneider| Prof. Schneider]]
Betreuer: [[Benutzer:Ulrich_Schneider| Prof. Dr.-Ing. Ulrich Schneider]]
 
[[Datei:Lösungsweg_Bild1.png|250px|thumb|right|Abb.1: Labyrinth Lösungsalgorithmus]]
 
= 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 =


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.
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 (s. Abb.1: Labyrinth Lösungsalgorithmus). 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 =
= 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
 
[[Datei:Zwischenschritte_Bild1.png|1000px|Abb.2: Zwischenschritte Lösungsalgorithmus]]
 
== Umwandlung in Grauwertbild ==
 
Nachdem das Bild eingelesen wurde, wird dieses, sofern es sich um ein Farbbild handelt, in ein Grauwertbild gewandelt, indem das resultierende Intensitätsbild bestimmt und gegebenenfalls eine Grauwertspreizung durchgeführt wird, falls der globale Kontrast zu niedrig ist.
 
<source lang="matlab">
%% Bild einlesen
[filename, pathname] = uigetfile({'*.png'; '*.jpg'}, 'Please select image file'); % Öffnen der Dialogbox zur Auswahl einer Datei
if pathname == 0 % Falls Variable pathname gleich Null, wurde keine Datei zuvor angegeben
disp('Es wurde keine Datei angegeben'); % Graphische Rückmeldung über Fehler
return; % Terminierung, da keine Datei angegeben
end
 
oldFolder = cd(pathname); % Wechseln des aktuellen Ordners zu angegebenen Ordner
originalImage = imread(filename); % Einlesen des Bilds und Speicherung in Matrix
 
[rows cols numberOfColorBands] = size(originalImage); % Bestimmen der Größe der Matrix
 
if numberOfColorBands > 1 % Falls Bild aus mehr als einem Farbanteil besteht, Bestimmung des resultierenden Intensitätsbilds
monoImage = uint8(sqrt(double(originalImage(:,:,1)).^2 + double(originalImage(:,:,2)).^2 + double(originalImage(:,:,3)).^2)/3);
else % Falls Bild Grauwertbild
monoImage = originalImage;
end
 
if islogical(monoImage) == 1 % Falls das Bild bereits ein Binärbild ist
  monoImage = uint8(monoImage); % Umwandlung in 8-Bit Grauwertbild
end
 
%% Grauwertspreizung
minGrayvalue = min(min(monoImage)); % Minimaler Grauwert
maxGrayvalue = max(max(monoImage)); % Maximaler Grauwert
 
if (maxGrayvalue - minGrayvalue) < 100 % Falls nicht der gesamte Grauwertbereich benutzt wird
  for i = 1:rows % Grauwertspreizung über alle Pixel
      for j = 1:cols
          monoImage(i,j) = (monoImage(i,j) - minGrayvalue) * (255/(maxGrayvalue - minGrayvalue));
      end
  end
 
  imshow(monoImage); % Ausgabe des Grauwertbilds in einer Figur
else
  imshow(originalImage); % Ausgabe des originalen Bilds in einer Figur
end
</source>
 
== Konvertierung in Binärbild ==
 
Das Grauwertbild wird nachfolgend in ein Binärbild konvertiert und invertiert.  Durch die Invertierung sind nun alle Wände des Labyrinths, die im originalen Bild dunkel sind, durch eine 1, also weiß dargestellt und die Wege durch das Labyrinth, welche vorher hell waren, durch eine 0, also schwarz.
Darüber hinaus wird das Bild direkt bereinigt, indem alle Objekte am Bildrand sowie alle zu kleinen Artefakte gelöscht werden.
 
<source lang="matlab">
%% Bild in Schwarz-Weiß-Bild wandeln und invertieren
binaryImage = ~(im2bw(monoImage, graythresh(monoImage))); % Konvertierung und Invertierung des Bilds in Schwarz-Weiß-Bild
binaryImage = bwareaopen(imclearborder(binaryImage), round(rows*cols/1000)); % Löschen der Blobs, die am Rand oder zu klein sind
</source>
 
== Ermittlung der Regionen ==
 
Die zuvor angesprochene Invertierung wurde durchgeführt, da nun alle Regionen detektiert werden sollen. Eine Region ist dabei ein Bereich unter z.B. vierer Nachbarschaft, welcher einen homogenen Wert ungleich 0 besitzt. Dies sind somit genau die gesuchten Wände des Labyrinths.  Die zusammenhängenden Gebiete können mithilfe von integrierten MATLAB-Funktionen ermittelt werden.
 
<source lang="matlab">
%% Einzelne Blobs des Bildes ermitteln
[labeledImage numberOfBlobs] = bwlabel(binaryImage, 4); % Finden aller zusammenhängender Gebiete unter 4er-Nachbarschaft
if numberOfBlobs < 2 % Falls weniger als zwei zusammenhängende Gebiete gefunden wurden
disp('Es wurden zu wenig Blobs gefunden'); % Graphische Rückmeldung über Fehler
return; % % Terminierung, da zu wenig Gebiete zur weiteren Verarbeitung vorhanden sind
end
 
coloredLabels = label2rgb (labeledImage, 'hsv', 'k', 'shuffle'); % Wandeln der Matrix mit Gebieten in Falschfarbenbild
</source>
 
== Ermittlung der Wände des Labyrinths ==
 
Nun wird eruiert, welche der eben detektierten Gebiete sich sowohl in der Nähe des angegebenen Start- und Endpunktes befinden. Die beiden Hauptwände des Labyrinths erfüllen genau dieses Kriterium. Sie stellen eine direkte Verbindung zwischen dem Ein- und Ausgang des Labyrinths dar (siehe zum Beispiel „Rechte-Hand-Algorithmus“: http://de.wikipedia.org/wiki/L%C3%B6sungsalgorithmen_f%C3%BCr_Irrg%C3%A4rten). Dazu wird eine Region um den Start- und Endpunkt gebildet und verglichen, ob sich eine Region mit beiden Regionen überschneidet, sodass dadurch die beiden Hauptwände gefunden und separat in zwei Matrizen gespeichert werden.
 
<source lang="matlab">
%% Hauptwände des Labyrinths finden: Hauptwand gleich Gebiet, dass sich in Nähe des Start- und Endpunktes gefindet
findWall = 0; % Variable zum Anzeigen, ob und wie viele Hauptwände des Labyrinths gefunden wurden
 
for currBlob = 1:numberOfBlobs % Schleife läuft über alle Gebiete des bereinigten Binärbildes
binaryImage2 = (labeledImage == currBlob); % Betrachtung eines einzigen Gebiets, alle anderen Werte sind gleich null
findStartPoint = 0; % Flag zum Anzeigen, ob Startpunkt in der Nähe des Gebiets liegt
findEndPoint = 0; % Flag zum Anzeigen, ob Endpunkt in der Nähe des Gebiets liegt
    for mStart = 1:rows % Schleife läuft über alle Zeilen der Bildgröße
        for nStart = 1:cols % Schleife läuft über alle Spalten der Bildgröße
            if StartPointImage(mStart, nStart) == 1 && binaryImage2(mStart, nStart) == 1 % Vergleich, ob Startpunkt-Matrix und Gebiet sich überlappen
                findStartPoint = 1; % Falls Überlappung, Flag zum Anzeigen, das Startpunkt in der Nähe des Gebiets liegt
break; % Terminierung der inneren for-Schleife
            end
        end
if findStartPoint == 1 % Falls Überlappung gefunden wurde
break; % Terminierung der äußeren for-Schleife
end
    end
 
if findStartPoint == 1; % Falls Startpunkt in Nähe des aktuellen Gebiets liegt
for mEnd = 1:rows % Schleife läuft über alle Zeilen der Bildgröße
for nEnd = 1:cols % Schleife läuft über alle Spalten der Bildgröße
if EndPointImage(mEnd, nEnd) == 1 && binaryImage2(mEnd, nEnd) == 1 % Vergleich, ob Endpunkt-Matrix und Gebiet sich überlappen
findWall = findWall + 1; % Falls Überlappung, Index findWall erhöhen
if findWall == 1 % Falls erste Wand gefunden wurde
binaryImage3 = binaryImage2; % Matrix mit Gebiet abspeichern
end
findEndPoint = 1; % Flag zum Anzeigen, das Endpunkt in der Nähe des Gebiets liegt, setzen
break; % Terminierung der inneren for-Schleife
end
end
if findEndPoint == 1 % Falls Überlappung gefunden wurde
break; % Terminierung der äußeren for-Schleife
end
end
if findWall == 2 % Falls zweite Wand gefunden wurde
break; % Terminierung der for-Hauptschleife: Alle benötigten Wände gefunden
end
end
end
 
if findWall < 2 % Falls Index zum Anzeigen der gefundenen Hauptwände kleiner zwei ist
disp('Es wurden keine zwei Wände in unmittelbarer Nähe zum Start- und Endpunkt gefunden'); % Graphische Rückmeldung über Fehler
return; % Terminierung, da nicht genügend Hauptwände zur weiteren Verarbeitung gefunden wurden
end
</source>
 
== Ermittlung des Weges zwischen Wänden ==
 
Der Weg zwischen den beiden Hauptwänden wird abschließend mithilfe von morphologischen Operationen ermittelt. Durch Dilatation wird eine Wand so lange erweitert, bis sie sich mit der zweiten Wand überschneidet, sodass der gesamte Weg des Labyrinths zwischen den beiden Wänden dilatiert wurde. Anschließend werden mit der Closing-Operation Löcher innerhalb des dilatierten Gebietes aufgefüllt. Nachfolgend wird das aufgefüllte Gebiet um den gleichen Wert erodiert um den es dilatiert wurde. Der Weg zwischen den beiden Hauptwänden und damit durch das Labyrinth ergibt sich dann aus der Subtraktion des aufgefüllten Bildes und des erodierten Bildes.
 
<source lang="matlab">
%% Zuvor gefundene Hauptwand, welche in der Nähe des Start- und Endpunktes liegt, wird um ein paar Pixel dilatiert
dilationAmount = 1; % Anzahl an Pixel zum Dilatieren und Erodieren
dilatedImage = binaryImage2; % Dilatiertes Gebiet auf Basis des zuvor ausgewählten Gebiets
loopCounter = 1; % Variable zum Steuern der nachfolgenden while-Schleife
 
while loopCounter == 1 % Solange Schleifenvariable gleich eins
    dilatedImage = imdilate(dilatedImage, ones(3)); % Dilatation des Gebiets: ein weißes Pixel wird 3x3 groß
    dilationAmount = dilationAmount + 2; % Erhöhen der Anzahl an Pixel, die dilatiert wurde
    for m = 1:rows % Schleife läuft über alle Zeilen der Bildgröße
        for n = 1:cols % Schleife läuft über alle Spalten der Bildgröße
            if dilatedImage(m, n) == 1 && binaryImage3(m, n) == 1 % Vergleich, ob dilatierte erste Wand und zweite Wand sich überlappen
                loopCounter = 0; % Setzen der Variable zum Steuern der while-Schleife gleich null
break; % Terminierung der inneren for-Schleife
            end
        end
if loopCounter == 0 % Falls Überlappung gefunden wurde
break; % Terminierung der äußeren for-Schleife
end
    end   
end
 
subplot(234); % Festlegen der Position der Grafik in aktueller Figur
imshow(dilatedImage); % Visualisierung der Ergebnisse des dilatierten Gebiets
title('Dilatation der Wand'); % Hinzufügen des Titels
 
%% Dilatation plus Auffüllung wieder erodieren
filledImage = imfill(dilatedImage, 'holes'); % Löcher innerhalb des Gebietes auffüllen
erodedImage = imerode(filledImage, ones(dilationAmount)); % Erosion um den gleichen Pixelwert wie Dilatation
</source>


= Dokumentation =
= Dokumentation =


/
Link zum Youtube-Video:
 
[http://youtu.be/5jokNfi7ZsY Labyrinth Lösungsalgorithmus]


= Fazit und Ausblick =
= Fazit und Ausblick =


/
Das angestrebte Ziel, dass der Weg durch ein beliebiges Labyrinth, welches auf einem Foto abgebildet ist, gefunden wird, wurde mithilfe der kennengelernten Methoden der Bildverarbeitung erreicht.  Ergänzend lassen sich noch Erweiterungen vornehmen, sodass der Eingang und der Ausgang des Labyrinths automatisch gefunden werden, sodass der Algorithmus völlig autonom ohne Interaktion abläuft und zum Beispiel ein Live-Bild einer Kamera in MATLAB eingebunden werden kann, auf welchem in Echtzeit der Weg durch das Labyrinth zu sehen ist.
 
= Weiterführende Informationen zu den benutzten MATLAB-Funktionen =
 
{| class="wikitable"
|-
! Funktionsnamen !! Hyperlink
|-
| bwareaopen || http://de.mathworks.com/help/matlab/ref/bwareaopen.html]
|-
| bwlabel || http://de.mathworks.com/help/matlab/ref/bwlabel.html]
|-
| cat || http://de.mathworks.com/help/matlab/ref/cat.html]
|-
| cd || http://de.mathworks.com/help/matlab/ref/cd.html]
|-
| clc || http://de.mathworks.com/help/matlab/ref/clc.html]
|-
| clear || http://de.mathworks.com/help/matlab/ref/clear.html]
|-
| close || http://de.mathworks.com/help/matlab/ref/close.html]
|-
| disp || http://de.mathworks.com/help/matlab/ref/disp.html]
|-
| getrect || http://de.mathworks.com/help/matlab/ref/getrect.html]
|-
| imclearborder || http://de.mathworks.com/help/matlab/ref/imclearborder.html]
|-
| imdilate || http://de.mathworks.com/help/matlab/ref/imdilate.html]
|-
| imerode || http://de.mathworks.com/help/matlab/ref/imerode.html]
|-
| imfill || http://de.mathworks.com/help/matlab/ref/imfill.html]
|-
| imread || http://de.mathworks.com/help/matlab/ref/imread.html]
|-
| imshow || http://de.mathworks.com/help/matlab/ref/imshow.html]
|-
| islogical || http://de.mathworks.com/help/matlab/ref/islogical.html]
|-
| label2rgb || http://de.mathworks.com/help/matlab/ref/label2rgb.html]
|-
| logical || http://de.mathworks.com/help/matlab/ref/logical.html]
|-
| msgbox || http://de.mathworks.com/help/matlab/ref/msgbox.html]
|-
| ones || http://de.mathworks.com/help/matlab/ref/ones.html]
|-
| round || http://de.mathworks.com/help/matlab/ref/round.html]
|-
| size || http://de.mathworks.com/help/matlab/ref/size.html]
|-
| sprintf || http://de.mathworks.com/help/matlab/ref/sprintf.html]
|-
| subplot || http://de.mathworks.com/help/matlab/ref/subplot.html]
|-
| title || http://de.mathworks.com/help/matlab/ref/title.html]
|-
| uigetfile || http://de.mathworks.com/help/matlab/ref/uigetfile.html]
|-
| uint8 || http://de.mathworks.com/help/matlab/ref/uint8.html]
|}


Aufruf am 13.06.16


= 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]]

Aktuelle Version vom 22. Juni 2016, 09:09 Uhr

Autor: Marcus Irmer
Betreuer: Prof. Dr.-Ing. Ulrich Schneider

Abb.1: Labyrinth Lösungsalgorithmus

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 (s. Abb.1: Labyrinth Lösungsalgorithmus). 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

Abb.2: Zwischenschritte Lösungsalgorithmus

Umwandlung in Grauwertbild

Nachdem das Bild eingelesen wurde, wird dieses, sofern es sich um ein Farbbild handelt, in ein Grauwertbild gewandelt, indem das resultierende Intensitätsbild bestimmt und gegebenenfalls eine Grauwertspreizung durchgeführt wird, falls der globale Kontrast zu niedrig ist.

%% Bild einlesen
[filename, pathname] = uigetfile({'*.png'; '*.jpg'}, 'Please select image file'); % Öffnen der Dialogbox zur Auswahl einer Datei
if pathname == 0 % Falls Variable pathname gleich Null, wurde keine Datei zuvor angegeben
	disp('Es wurde keine Datei angegeben'); % Graphische Rückmeldung über Fehler
	return; % Terminierung, da keine Datei angegeben
end

oldFolder = cd(pathname); % Wechseln des aktuellen Ordners zu angegebenen Ordner
originalImage = imread(filename); % Einlesen des Bilds und Speicherung in Matrix

[rows cols numberOfColorBands] = size(originalImage); % Bestimmen der Größe der Matrix

if numberOfColorBands > 1 % Falls Bild aus mehr als einem Farbanteil besteht, Bestimmung des resultierenden Intensitätsbilds
	monoImage = uint8(sqrt(double(originalImage(:,:,1)).^2 + double(originalImage(:,:,2)).^2 + double(originalImage(:,:,3)).^2)/3);
else % Falls Bild Grauwertbild
	monoImage = originalImage;
end

if islogical(monoImage) == 1 % Falls das Bild bereits ein Binärbild ist
   monoImage = uint8(monoImage); % Umwandlung in 8-Bit Grauwertbild
end

%% Grauwertspreizung
minGrayvalue = min(min(monoImage)); % Minimaler Grauwert
maxGrayvalue = max(max(monoImage)); % Maximaler Grauwert

if (maxGrayvalue - minGrayvalue) < 100 % Falls nicht der gesamte Grauwertbereich benutzt wird
   for i = 1:rows % Grauwertspreizung über alle Pixel
      for j = 1:cols
          monoImage(i,j) = (monoImage(i,j) - minGrayvalue) * (255/(maxGrayvalue - minGrayvalue));
      end
   end
   
   imshow(monoImage); % Ausgabe des Grauwertbilds in einer Figur
else
   imshow(originalImage); % Ausgabe des originalen Bilds in einer Figur
end

Konvertierung in Binärbild

Das Grauwertbild wird nachfolgend in ein Binärbild konvertiert und invertiert. Durch die Invertierung sind nun alle Wände des Labyrinths, die im originalen Bild dunkel sind, durch eine 1, also weiß dargestellt und die Wege durch das Labyrinth, welche vorher hell waren, durch eine 0, also schwarz. Darüber hinaus wird das Bild direkt bereinigt, indem alle Objekte am Bildrand sowie alle zu kleinen Artefakte gelöscht werden.

%% Bild in Schwarz-Weiß-Bild wandeln und invertieren
binaryImage = ~(im2bw(monoImage, graythresh(monoImage))); % Konvertierung und Invertierung des Bilds in Schwarz-Weiß-Bild
binaryImage = bwareaopen(imclearborder(binaryImage), round(rows*cols/1000)); % Löschen der Blobs, die am Rand oder zu klein sind

Ermittlung der Regionen

Die zuvor angesprochene Invertierung wurde durchgeführt, da nun alle Regionen detektiert werden sollen. Eine Region ist dabei ein Bereich unter z.B. vierer Nachbarschaft, welcher einen homogenen Wert ungleich 0 besitzt. Dies sind somit genau die gesuchten Wände des Labyrinths. Die zusammenhängenden Gebiete können mithilfe von integrierten MATLAB-Funktionen ermittelt werden.

%% Einzelne Blobs des Bildes ermitteln
[labeledImage numberOfBlobs] = bwlabel(binaryImage, 4); % Finden aller zusammenhängender Gebiete unter 4er-Nachbarschaft
if numberOfBlobs < 2 % Falls weniger als zwei zusammenhängende Gebiete gefunden wurden
	disp('Es wurden zu wenig Blobs gefunden'); % Graphische Rückmeldung über Fehler
	return; % % Terminierung, da zu wenig Gebiete zur weiteren Verarbeitung vorhanden sind
end

coloredLabels = label2rgb (labeledImage, 'hsv', 'k', 'shuffle'); % Wandeln der Matrix mit Gebieten in Falschfarbenbild

Ermittlung der Wände des Labyrinths

Nun wird eruiert, welche der eben detektierten Gebiete sich sowohl in der Nähe des angegebenen Start- und Endpunktes befinden. Die beiden Hauptwände des Labyrinths erfüllen genau dieses Kriterium. Sie stellen eine direkte Verbindung zwischen dem Ein- und Ausgang des Labyrinths dar (siehe zum Beispiel „Rechte-Hand-Algorithmus“: http://de.wikipedia.org/wiki/L%C3%B6sungsalgorithmen_f%C3%BCr_Irrg%C3%A4rten). Dazu wird eine Region um den Start- und Endpunkt gebildet und verglichen, ob sich eine Region mit beiden Regionen überschneidet, sodass dadurch die beiden Hauptwände gefunden und separat in zwei Matrizen gespeichert werden.

%% Hauptwände des Labyrinths finden: Hauptwand gleich Gebiet, dass sich in Nähe des Start- und Endpunktes gefindet
findWall = 0; % Variable zum Anzeigen, ob und wie viele Hauptwände des Labyrinths gefunden wurden

for currBlob = 1:numberOfBlobs % Schleife läuft über alle Gebiete des bereinigten Binärbildes
	binaryImage2 = (labeledImage == currBlob); % Betrachtung eines einzigen Gebiets, alle anderen Werte sind gleich null
	
	findStartPoint = 0; % Flag zum Anzeigen, ob Startpunkt in der Nähe des Gebiets liegt
	findEndPoint = 0; % Flag zum Anzeigen, ob Endpunkt in der Nähe des Gebiets liegt
	
    for mStart = 1:rows % Schleife läuft über alle Zeilen der Bildgröße
        for nStart = 1:cols % Schleife läuft über alle Spalten der Bildgröße
            if StartPointImage(mStart, nStart) == 1 && binaryImage2(mStart, nStart) == 1 % Vergleich, ob Startpunkt-Matrix und Gebiet sich überlappen
                findStartPoint = 1; % Falls Überlappung, Flag zum Anzeigen, das Startpunkt in der Nähe des Gebiets liegt
				break; % Terminierung der inneren for-Schleife
            end
        end
		
		if findStartPoint == 1 % Falls Überlappung gefunden wurde
			break; % Terminierung der äußeren for-Schleife
		end
    end 

	if findStartPoint == 1; % Falls Startpunkt in Nähe des aktuellen Gebiets liegt
		for mEnd = 1:rows % Schleife läuft über alle Zeilen der Bildgröße
			for nEnd = 1:cols % Schleife läuft über alle Spalten der Bildgröße
				if EndPointImage(mEnd, nEnd) == 1 && binaryImage2(mEnd, nEnd) == 1 % Vergleich, ob Endpunkt-Matrix und Gebiet sich überlappen
					findWall = findWall + 1; % Falls Überlappung, Index findWall erhöhen
					if findWall == 1 % Falls erste Wand gefunden wurde
						binaryImage3 = binaryImage2; % Matrix mit Gebiet abspeichern
					end
							
					findEndPoint = 1; % Flag zum Anzeigen, das Endpunkt in der Nähe des Gebiets liegt, setzen
					break; % Terminierung der inneren for-Schleife
				end
			end
					
			if findEndPoint == 1 % Falls Überlappung gefunden wurde
				break; % Terminierung der äußeren for-Schleife
			end
		end	
		
		if findWall == 2 % Falls zweite Wand gefunden wurde
			break; % Terminierung der for-Hauptschleife: Alle benötigten Wände gefunden
		end
	end
end

if findWall < 2 % Falls Index zum Anzeigen der gefundenen Hauptwände kleiner zwei ist 
	disp('Es wurden keine zwei Wände in unmittelbarer Nähe zum Start- und Endpunkt gefunden'); % Graphische Rückmeldung über Fehler
	return; % Terminierung, da nicht genügend Hauptwände zur weiteren Verarbeitung gefunden wurden
end

Ermittlung des Weges zwischen Wänden

Der Weg zwischen den beiden Hauptwänden wird abschließend mithilfe von morphologischen Operationen ermittelt. Durch Dilatation wird eine Wand so lange erweitert, bis sie sich mit der zweiten Wand überschneidet, sodass der gesamte Weg des Labyrinths zwischen den beiden Wänden dilatiert wurde. Anschließend werden mit der Closing-Operation Löcher innerhalb des dilatierten Gebietes aufgefüllt. Nachfolgend wird das aufgefüllte Gebiet um den gleichen Wert erodiert um den es dilatiert wurde. Der Weg zwischen den beiden Hauptwänden und damit durch das Labyrinth ergibt sich dann aus der Subtraktion des aufgefüllten Bildes und des erodierten Bildes.

%% Zuvor gefundene Hauptwand, welche in der Nähe des Start- und Endpunktes liegt, wird um ein paar Pixel dilatiert
dilationAmount = 1; % Anzahl an Pixel zum Dilatieren und Erodieren
dilatedImage = binaryImage2; % Dilatiertes Gebiet auf Basis des zuvor ausgewählten Gebiets
loopCounter = 1; % Variable zum Steuern der nachfolgenden while-Schleife

 while loopCounter == 1 % Solange Schleifenvariable gleich eins
    dilatedImage = imdilate(dilatedImage, ones(3)); % Dilatation des Gebiets: ein weißes Pixel wird 3x3 groß
    dilationAmount = dilationAmount + 2; % Erhöhen der Anzahl an Pixel, die dilatiert wurde
	
    for m = 1:rows % Schleife läuft über alle Zeilen der Bildgröße
        for n = 1:cols % Schleife läuft über alle Spalten der Bildgröße
            if dilatedImage(m, n) == 1 && binaryImage3(m, n) == 1 % Vergleich, ob dilatierte erste Wand und zweite Wand sich überlappen
                loopCounter = 0; % Setzen der Variable zum Steuern der while-Schleife gleich null
				break; % Terminierung der inneren for-Schleife
            end
        end
		
		if loopCounter == 0 % Falls Überlappung gefunden wurde
			break; % Terminierung der äußeren for-Schleife
		end
    end    
 end

subplot(234); % Festlegen der Position der Grafik in aktueller Figur
imshow(dilatedImage); % Visualisierung der Ergebnisse des dilatierten Gebiets
title('Dilatation der Wand'); % Hinzufügen des Titels

%% Dilatation plus Auffüllung wieder erodieren
filledImage = imfill(dilatedImage, 'holes'); % Löcher innerhalb des Gebietes auffüllen
erodedImage = imerode(filledImage, ones(dilationAmount)); % Erosion um den gleichen Pixelwert wie Dilatation

Dokumentation

Link zum Youtube-Video:

Labyrinth Lösungsalgorithmus

Fazit und Ausblick

Das angestrebte Ziel, dass der Weg durch ein beliebiges Labyrinth, welches auf einem Foto abgebildet ist, gefunden wird, wurde mithilfe der kennengelernten Methoden der Bildverarbeitung erreicht. Ergänzend lassen sich noch Erweiterungen vornehmen, sodass der Eingang und der Ausgang des Labyrinths automatisch gefunden werden, sodass der Algorithmus völlig autonom ohne Interaktion abläuft und zum Beispiel ein Live-Bild einer Kamera in MATLAB eingebunden werden kann, auf welchem in Echtzeit der Weg durch das Labyrinth zu sehen ist.

Weiterführende Informationen zu den benutzten MATLAB-Funktionen

Funktionsnamen Hyperlink
bwareaopen http://de.mathworks.com/help/matlab/ref/bwareaopen.html]
bwlabel http://de.mathworks.com/help/matlab/ref/bwlabel.html]
cat http://de.mathworks.com/help/matlab/ref/cat.html]
cd http://de.mathworks.com/help/matlab/ref/cd.html]
clc http://de.mathworks.com/help/matlab/ref/clc.html]
clear http://de.mathworks.com/help/matlab/ref/clear.html]
close http://de.mathworks.com/help/matlab/ref/close.html]
disp http://de.mathworks.com/help/matlab/ref/disp.html]
getrect http://de.mathworks.com/help/matlab/ref/getrect.html]
imclearborder http://de.mathworks.com/help/matlab/ref/imclearborder.html]
imdilate http://de.mathworks.com/help/matlab/ref/imdilate.html]
imerode http://de.mathworks.com/help/matlab/ref/imerode.html]
imfill http://de.mathworks.com/help/matlab/ref/imfill.html]
imread http://de.mathworks.com/help/matlab/ref/imread.html]
imshow http://de.mathworks.com/help/matlab/ref/imshow.html]
islogical http://de.mathworks.com/help/matlab/ref/islogical.html]
label2rgb http://de.mathworks.com/help/matlab/ref/label2rgb.html]
logical http://de.mathworks.com/help/matlab/ref/logical.html]
msgbox http://de.mathworks.com/help/matlab/ref/msgbox.html]
ones http://de.mathworks.com/help/matlab/ref/ones.html]
round http://de.mathworks.com/help/matlab/ref/round.html]
size http://de.mathworks.com/help/matlab/ref/size.html]
sprintf http://de.mathworks.com/help/matlab/ref/sprintf.html]
subplot http://de.mathworks.com/help/matlab/ref/subplot.html]
title http://de.mathworks.com/help/matlab/ref/title.html]
uigetfile http://de.mathworks.com/help/matlab/ref/uigetfile.html]
uint8 http://de.mathworks.com/help/matlab/ref/uint8.html]

Aufruf am 13.06.16

Literatur

  • Tönnies, Klaus D.: Grundlagen der Bildverarbeitung. München: Pearson Studium, 2005.

→ zurück zum Hauptartikel: DSB SoSe2016