Labyrinth Lösungsalgorithmus II: Unterschied zwischen den Versionen
(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: | ||
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 ( | 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
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
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:
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
Aufruf am 13.06.16
Literatur
- Tönnies, Klaus D.: Grundlagen der Bildverarbeitung. München: Pearson Studium, 2005.
→ zurück zum Hauptartikel: DSB SoSe2016