SigSys15 Start- und Stopplinienerkennung

Autor: Tim Salinski
Betreuer: Prof. Schneider

Motivation

Eine Aufgabe beim Carolo Cup ist der "Rundkurs mit Hindernissen". Hierbei ist eine Startlinie zu überfahren und an eienr Stopplinie zu halten.

Ziel

Die Start- und Stoppline soll robust erkannt und unterschieden werden.

Aufgabe

Zeichnen Sie die Kamerasicht eines Rundkurses auf.
Lesen Sie diesen als Endlosschleife in Matlab ein.
Identifizieren Sie während der virtuellen Fahrt Start- und Stopplinien mit Matlab.
Vermeiden Sie Fehler ("false-positives").
Optimieren Sie die Rechenzeit Ihres Algorithmus.

Lösungen

Vorverarbeitende Maßnahmen

Video in einzelne Frames aufteilen

Video-Dateien belegen in Matlab sehr viel Arbeitsspeicher. Um während der eigentlichen Bildverarbeitung für Entlastung zu sorgen, ist es allerdings möglich das Video in seine einzelnen Frames zu zurlegen und diese jeweils abzuspeichern. Diese Bilder können dann während der Verarbeitung geladen werden. Auf diese Weise wird bei der Verarbeitung nicht mehr Speicher benötigt als für diesen Durchlauf erforderlich. Unter realen Bedingungen spielen diese Umstände allerdings keine Rolle, da es unsinnig wäre von der Kamara aufgenommene Bilder erst zwischenzuspeichern, um sie anschließend wieder zu laden. Hierbei könnten die Bilddaten direkt verarbeitet werden.

Der Arbeitsschritt das Video in Bilder zu teilen wird durch die Funktion Video2Img.m durchgeführt. Diese Funktion übernimmt dabei zusätzlich die Aufgabe den einzelnen Frames Namen zu geben anhand derer sie während der noch folgenden Schritte identifiziert werden können. Diese Namen setzen sich aus einer Zeichenkette zusammen deren Elemente "Frame_" und eine fortlaufende vierstellige Nummer z.B. "0001" sind.

Bild für die Verarbeitung vorbereiten

Bevor mit der eigentlichen Bildverarbeitung begonnen werden kann sind noch einige Schritte nötig. Dazu gehört auch das nächste zu verarbeitende Bild auszuwählen und zu laden. Dies geschieht anhand der fortlaufenden Nummerieriung die zuvor durchgeführt wurde.

Im Anschluss daran wird das Bild mit Hilfe der Kameraparameter VRM_Calib_15_05_14 entzerrt. Damit ist sicher, dass horizontale Linien im Bild auch wirklich horizontal sind und nicht durch die Verzerrung der Kamera gewölbt dargestellt sind. Der Effekt tritt zwar in den Randbereichen des Bildes stärker auf als in der Bildmitte, jedoch lässt sich auf diese Weise ausschließen, dass die Verzerrung einen Einfluss auf die weiteren Ergebnisse hat. Dieser Schritt kann bei älteren Matlab Versionen als 2014b zu Komplikationen führen, da diese womöglich die verwendete Funktion nicht bereitstellen.

Die Frames liegen zunächst im RGB-Format vor, welches für das weitere Vorgehen nicht benötigt wird. Die Aufgabenstellung erfordert das Suchen von weißen Linien auf schwarzem Hintergrund. Die überflüssigen Information, die ein Farbbild enthält, werden zunächst durch eine Konvertierung in ein Graustufenbild reduziert. Danach folgt eine Reduktion der Daten durch die Funktion Gray2BW.m, die die Konvertierung von Graufstufen zu einem Schwarz-Weiß-Bild vornimmt. Das Fahrzeug selbst ist im unteren Drittel des Bildes nach diesem Schritt immer noch zu sehen. Um "mitfahrende weiße Linien" zu verhindern, wird der Teil des Bildes, der durch das Fahrzeug verdeckt wird ausmaskiert. Dies geschieht mit Hilfe des Bildes Maske_Fahrzeug. Zuletzt werden durch Anwenden des Sobel-Operators die Kanteninformationen aus dem Bild gewonnen.

Einlesen in Endlosschleife

Die Aufgabenstellung erfordert, dass die Daten in einer Endlosschleifen eingelesen werden. Dies wird durch die hier aufgeführten Codeabschnitte umgesetzt. Die Funktion Start_und_Stopplinienerkennung beginnt nach einigen Initialisierungen mit einer while-Schleife, die niemals enden kann. Der nächste Frame wird anschließend geladen bevor die Bildverarbeitung stattfindet, die im Folgenden näher beschrieben wird.

%% In Endlosschleife über Bilder laufen 
while 1                                                                    % Endlosschleife über alle Frames ohne Ende
    
    Frame_Name = ['Frame_',num2str(Frame_Counter(1)), ...                  % Bildname bestimmen
                  num2str(Frame_Counter(2)),num2str(Frame_Counter(3)), ... % Zusammensetzung aus Elementen des Arrays "Frame_Counter"
                  num2str(Frame_Counter(4))];

Nach der Bildverarbeitung wird ein Zähler für die Frames inkrementiert. Dieser besteht aus 4 Variablen, da ebensoviele zuvor für die Indentifikation des Frames verwendet wurden. Zwar ließe sich dies auch durch eine Variable erledigen, jedoch würde dies den Verlust der führenden Nullen im Namen des Frames bedeuten. Wenn der letzte Frame erreicht wurde, wird der Zähler für die Frames zurückgesetzt, sodass beim nächsten Schleifendurchlauf wieder das erste Bild geladen wird.

    %% Frame hochzählen
    Frame_Counter(4) = Frame_Counter(4) + Zeitschritte;                    % z.B. '+2': 2*(1/30) Sekunden zwischen den Bildern, da 30 Frames/sek
    if Frame_Counter(4) == 10                                              % Auswirkung von letzter Stelle prüfen, daher nur Zeitschritte 1;2;5;10 erlaubt
        Frame_Counter(4) = 0;                                              % Letzte Stelle resetten
        Frame_Counter(3) = Frame_Counter(3) + 1;                           % Dafür 3. Stelle inkrementieren
        if Frame_Counter(3) == 10                                          % Auswirkung auf 2. Stelle prüfen
            Frame_Counter(3) = 0;                                          % 3. Stelle resetten
            Frame_Counter(2) = Frame_Counter(2) + 1;                       % 2. Stelle inkrementieren
            if Frame_Counter(2) == 10                                      % Auswirkung auf 1. Stelle prüfen
                Frame_Counter(2) = 0;                                      % 2. Stelle resetten
                Frame_Counter(1) = Frame_Counter(1) + 1;                   % 1. Stelle inkrementieren
            end
        end
    end
    
    %% Zurücksetzen wenn alle Frames durchlaufen wurden 
    if Frame_Counter(1) * 1000 + Frame_Counter(2) * 100 + ...              % Wenn alle Frames durchlaufen wurden
       Frame_Counter(3) * 10 + Frame_Counter(4) >= 2331
        Frame_Counter(1) = 0;                                              % alle Zähler zurücksetzen und von vorne beginnen
        Frame_Counter(2) = 0;
        Frame_Counter(3) = 0;
        Frame_Counter(4) = 0;
    end

Algorithmus zur Linienerkennung

Der Algorithmus zur Linienerkennung beginnt in jedem Zyklus damit Schwarz-Weiß-Übergänge zu suchen, da diese nach Anwendung des Sobel für mögliche zu erkennende Linien stehen. Wo diese Suche stattfindet hängt vom vorherigen Frame ab. Wurde keine Linie beim letzten Zyklus gefunden beginnt die Suche in einer festgelegten Bildzeile. Wurde jedoch eine Linie gefunden, findet die Suche in der Nähe der gefunden Linie statt. Auf diese Weise ist es möglich Linien zu tracken.

Da die zu findenen Linien horizontal im Bild liegen müssen, ist es sinnvoll spaltenweise von oben nach unten nach ihnen zu suchen. Die entsprechenden Spalten sind vor Betreten der Endlosschleife festgelegt worden und befinden sich mittig im Bild, da dort auch die Linien erwartet werden. Dieses Vorgehen nutzt aus, dass das Fahrzeug mittig in der rechten Spur fährt und sich etwaige Start- oder Stopplinien von oben nach unten durch das Bild bewegen. Wie tief eine Spalte durchsucht wird ist ebenfalls vor betreten der Endlosschleife als "Prüftiefe" definiert worden. Hierbei wird jeweils gespeichert ob in der betreffenden Spalte ein Farbwechsel stattgefunden hat und wenn ja in welcher Tiefe dieser lag bezogen auf Startzeile.

Die gefundenen Schwarz-Weiß-Übergänge müssen nun dahingehend verifiziert werden, ob es sich dabei um eine Start- oder Stopplinie handeln kann, um false-positive-Fehler zu minimieren. Damit eine Linie weiterverarbeitet wird müssen 3 Kriterien erfüllt sein:

- Alle Spalten müssen einen S-W-Übergang detektiert haben
- Die Differenz der maximalen und minimalen gespeicherten Tiefe, in der der Übergang stattfand, darf einen festen Wert nicht überschreiten
- Es darf sich um keine "Zick-Zack"-Linie ergeben, wenn die Übergänge miteinander verbunden wären.

Ist eines dieser Kriterien nicht erfüllt, behandelt der Algorithmus diese Linie so als wäre sie keine Start- oder Stoplinie. Sollten alle 3 Punkt zutreffen muss im nächsten Schritt die Art der Linie bestimmt werden. Die einzige Ausnahme für dieses Verhalten gilt, wenn zuvor eine Linie gefunden wurde und diese nun getrackt wird. In diesem Fall gelten die letzten beiden Punkte nicht und es ist bereits ausreichend, dass nur alle überprüften Spalten einen S-W-Übergang detektiert haben.

Um herauszufinden, ob es sich um eine Start- oder Stoplinie handelt, wird ausgenutzt welche Eigenschaften eine Stoplinie erwartungsgemäß besitzt. Diese erstrecken sich nämlich im Gegensatz zur Startlinie nur über die Hälfte der Fahrbahn und haben somit ein linkes Ende nach dem gesucht werden kann. Der Algorithmus folgt also der Linie nach links indem er stets die linken Nachbarn des aktuell äußersten Punktes überprüft. Hat er den äußersten Punkt der Linie gefunden, wird eine Transformation in Weltkoordinaten angewendet. Dies geschieht durch die Funktion bild_zu_welt.m nach dem Grundsatz der Zentralperspektive. Da davon ausgegangen wird, dass das Fahrzeug mittig in der rechten Spur fährt, würde eine Stoplinie eine halbe Spurbreite links vom Fahrzeug enden. Da bekannt ist, dass eine Fahrspur eine Breite von 400mm besitzt, kann darauf geschlossen werden, dass eine Stoplinie ca. 200mm und eine Startlinie ca. 600mm links vom Fahrzeug enden würde.

Nachdem die Art der Linie bestimmt wurde, wird die Entfernung zu dieser Linie berechnet. Dies geschieht wieder unter Anwendung der Zentralpersoektive durch die Funktion bild_zu_welt.m.

Damit ist die Bildverarbeitung abgeschlossen. Die Ergebnisse werden anschließend durch die Funktion Ausgabe.m dargestellt und nehmen dabei die Form an, die in obiger Abbildung zu sehen ist. Sollte der Frame keine Start- oder Stoplinien aufweisen, wird lediglich der Frame als Graustufenbild angezeigt. Wenn eine Linie gefunden wurde, wird diese durch einen roten Strich im Bild markiert. In der oberen linken Bildecke wird außerdem ausgegeben, welche Art von Linie gefunden wurde und wie weit diese noch vom aktuellen Standpunkt aus entfernt ist. Außerdem wird jeder Frame, der durch Ausgabe.m ausgegeben wurde, als Bild abgespeichert. Diese Daten werden später im Kapitel "Nachverarbeitende Maßnahmen" benötigt.

Laufzeitbetrachtung

Die Abbildung zeigt eine Laufzeitmessung bei der Ausführung der Funktion Start_und_Stopplinienerkennung.m, die die wesentliche Bildverarbeitung durchführt. Hierbei wurde die in Matlab integrierte Funktion für Laufzeitmessungen verwendet. Da die Bildverarbeitung in einer Endlosschleife ausgeführt wird, musste das Programm manuell gestoppt werden, um zu diesem Ergebnis zu gelangen. Anhand einiger markanter Funktionen, die nur einmalig während eines Schleifendurchlaufs aufgerufen werden, lässt sich allerdings erkennen, wie viele Frames in dieser Zeit verarbeitet wurden.

Zu diesen Funktionen zählen Ausgabe.m und Gray2BW.m. Beide wurden bei dieser Messung 47 mal aufgerufen. Demzufolge wurden 47 Frames bis zu diesem Zeitpunkt verarbeitet. Bei einer Laufzeit von ca. 98 Sekunden erscheint dies relativ wenig, jedoch muss beachtet werden, dass nur ein Teil des Codes die wesentliche Bildverarbeitung durchführt. Dieser Code ist in Start_und_Stopplinienerkennung.m selbst enthalten und kann daher keiner Unterfunktion zugeordnet werden. Die Zeit, die das Programm nicht auf Unterfunktionen verwendet, ist in der Abbildung als "Self Time" aufgeführt und beträgt in diesem Fall 0,243 Sekunden. Der Algorithmus, der nach den Linien sucht kann bei der Laufzeitbetrachtung folglich vernachlässigt werden, da sich hier eine durchschnittliche Ausführzeit pro Frame von 0,243 / 47 = 0,005 Sekunden ergibt. Größter "Zeitfresser", der zwingend nötig ist, ist die Funktion Gray2BW.m mit 7,6 Sekunden.

Die Ausgabe hingegen dient nur dazu die Ergebnisse zu veranschaulichen. Ihre Ausführung hat keinen Einfluss darauf ob und wo Linien gefunden werden. Ohne diese Funktion blieben von den 98 Sekunden Gesamtzeit gerade einmal ca. 12 Sekunden übrig. Dies würde pro Frame immer noch eine Zeit von 0,25 Sekunden beanspruchen. Dieser Wert liegt zwar immer noch über der Zeit zwischen 2 Frames, würde aber wahrscheinlich schon ausreichen, um Linien während der Fahrt erkennen zu können. Hierbei würden zwar einige Frames ungenutzt bleiben, aber da eine Linie im schlimmsten Fall mit einer Verspätung von 0,25 Sekunden erkannt wird, könnte immer noch mit dem Anhalten des Fahrzeugs darauf reagiert werden.

Darüber hinaus sollte noch erwähnt werden, dass es sich bei dieser Messung um Matlab Code handelte. Matlab bietet zwar dem Benutzer eine sehr intuitive Sprache an, jedoch ist diese im Hinblich auf Laufzeit nicht optimal. Würde stattdessen C-Code zum Einsatz kommen, könnte damit noch eine wesentlich Beschleunigung erzielt werden, sodass deutlich weniger oder womöglich gar keine Frames mehr ungenutzt bleiben, wie bei der zuvor beschriebenen Ausführzeit pro Frame von 0,25 Sekunden.

Außerdem sollte beachtet werden, dass eine Start- und Stopplinienerkennung meinst gemeinsam mit einer Fahrspurerkennung zum Einsatz kommt. Diese wiederum gewinnt ihre Ergebnisse aus denselben Daten wie die Linienerkennung. Es ist daher möglich bestimmte Schritte der Bildverarbeitung nur einmal durchzuführen und anschließend für beide Anwendungen zu benutzen. Auf diese Weise kann die Zeit sehr effektiv genutzt werden. Sollte die Spurerkennnug bereits in angemessener Geschwindigkeit funktionieren, stellt die Start- und Stopplinienerkennung kein Problem mehr dar, weil die Zeit in diesem Fall nur die "Self Time" hinzukommt und diese wie oben erläutert sehr gering ist.

Nachverarbeitende Maßnahmen

Da die gleichzeitige Ausführung von Bearbeitung und Ausgabe der Ergebnisse die Laufzeit des Programms massiv beeinflusst wie dem Kapitel "Laufzeitbetrachtung" zu entnehmen ist, werden diese beide Kompenenten in diesem Schritt voneinander getrennt.

Mit Hilfe der Im2Vid.m Funktion können die Frames, die durch die Ausgabe abgespeichert wurden, nacheinander gelesen werden. Die erzeugte Struktur "mov" kann Frames der passenden Größe und Colormap aufnehmen. Legt man die einzelnen Frames nacheinander als Elemente dieser Struktur ab, kann der Inhalt dieser Struktur in Matlab als Video wiedergegeben werden.

Die Funktion Spiele_Video.m bewirkt diese Ausgabe. Die Framerate mit der das Video abgespielt werden soll, ist hierbei frei wählbar und hängt nicht mit der Berechnungszeit für einen Frame zusammen. Auf diese Weise können die Ergebnisse so betrachtet werden als wenn alle unter "Laufzeitbetrachtung" erwähnten negativen Einflüsse auf die Laufzeit eleminiert wären.

Weblinks

Carolo Cup 2012 - Spatzenhirn (Uni Ulm)

→ zurück zum Hauptartikel: Signalverarbeitende Systeme SoSe2015