Labyrinth Lösungsalgorithmus II
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