Select Git revision
implementation.tex 39.35 KiB
\chapter{Fahrspurerkennung} \label{chap: implementation}
Dieses Kapitel thematisiert, wie die Erkennung der Fahrspurmarkierungen umgesetzt wird. Begonnen wird mit einer konzeptionellen Version in
Python, mit der der Ablauf des Algorithmus geplant und getestet wird. Danach wird die Logik in einer \gls{C++} \gls{ROS Node} umgesetzt, um die
bestmögliche Performance zu erhalten.
\begin{figure}
\includegraphics[page=1,scale=.85]{svg/Topics_makerDetection.pdf}
\caption{Zusammenhang der Fahrspurmarkierung-Erkennungs-\gls{ROS Node} mit den bestehenden \glspl{ROS Node}}
\label{fig: topics marker detection}
\end{figure}
Wie diese neuen \glspl{ROS Node} mit den bestehenden \glspl{ROS Node} in Beziehung stehen soll, ist in \autoref{fig: topics marker detection}
grafisch dargestellt. Neu ist dabei, dass diese \gls{ROS Node} das korrigierte Schwarz-Weiß Bild von der in \autoref{sec: undistort Node}
beschriebenen entzerrer \gls{ROS Node} abonniert und das eigene Ergebnis als neues \gls{Topic} zur Verfügung stellt.
\section{Konzeptionierung in Python}
Die Entwicklung und Konzeptionierung des Algorithmus erfolgt in \gls{python}. Diese Sprache muss nicht kompiliert werden und hat eine sehr
einfache Syntax, wodurch das Testen beschleunigt wird und sie generell einfacher zu verwenden ist.
Der Algorithmus lässt sich in mehrere Einzelschritte aufteilen, welche in den folgenden Unterkapiteln beschreiben im Einzelnen beschrieben
sind. Zur Übersicht ist aber der gesamte Ablauf in \autoref{fig: PAP} skizziert. Angefangen wird dort mit dem Erhalten des Bildes,
womit sowohl manuelles Laden eines Beispielbildes, als auch das Erhalten des Bildes über ein \gls{Topic} gemeint ist.
\begin{figure}
\includegraphics[scale=.85]{svg/PAP_marker_erkennung.pdf}
\caption{Ablauf des Algorithmus zur Erkennung von Fahrspurmarkierungen}
\label{fig: PAP}
\end{figure}
Während einer Testfahrt des \glspl{JetBot} wurden von der entzerrer \gls{ROS Node} veröffentlichte Bilder abgespeichert, sodass sie zum
lokalen Testen zur Verfügung stehen. Diese wurden unter \cite{git:dataset-strassen} abgelegt. In \autoref{fig: beispiel bild} ist eines dieser
Bilder gezeigt, mit dem im Folgenden die Einzelschritte demonstriert werden.
\begin{figure}
\includegraphics[width=.6\textwidth]{img/Marks_original.png}
\caption{Beispielbild an dem der Ablauf demonstriert wird}
\label{fig: beispiel bild}
\end{figure}
\pagebreak
\subsection{Kantenerkennung mittels Canny-Edge-Detektor}
Begonnen wird mit der Detektion von Kanten im Bild. Dazu wird das Bild zuerst mit \gls{OpenCV} geladen.
Um kleine Störungen im Bild, welche bestehende Kanten verzerren oder als falsche Kante erkannt werden könnten, zu reduzieren, wird das
Bild mit einem \glslink{gauss-filter}{Gaußschen Filter} geglättet. Es wird ein $3\!\times\!3$ \gls{Kernel} mit einer Normalverteilung von
$\sigma=1,5$ verwendet. \gls{OpenCV} stellt hierzu die Funktion \lstinline{GaussianBlur()} zur Verfügung, der das geladene Bild, die
Kernelgröße und der Wert für $\sigma$ übergeben wird.
Die eigentliche Kantenerkennung wird mittels eines \glspl{canny} durchgeführt. Dabei handelt es sich um einen von John Canny 19983
entwickelten und in \cite{Canny:computationAlapproachEdgeDetection} veröffentlichten Algorithmus. Dieser bestimmt für jeden \gls{Pixel} den
Gradientenbetrag der Gradienten in $x$ und $y$-Richtung. Dann werden diejenigen \gls{Pixel} unterdrückt, welche entlang der Gradientenrichtung kein
Maximum darstellen. Zum Abschluss wird das Bild mit einem Hysterese-Schwellwert binarisiert. Das bedeutet, dass alle \gls{Pixel} über einem
initialen, oberen Schwellwert als Kanten gesetzt werden und mittels eines zweiten, niedrigeren Schwellwerte, Lücken zwischen diesen Pixeln
geschlossen werden. \cite{Nischwitz:Computergrafik2}
Auch dieser Algorithmus ist in \gls{OpenCV} bereits implementiert und wird für den ersten Entwurf verwendet. Die Funktion bekommt das
geladene und geglättet Bild sowie die beiden Hysterese-Schwellwerte übergeben. Diese ist auch in \autoref{code: canny} gezeigt.
\begin{lstlisting}[
float,
style=example,
caption={Laden, Glätten eines Bildes und Durchführen der Kantenerkennung mit \gls{OpenCV}},
label=code: canny,
language=Python
]
# load image (should be gray, so convert)
img = cv2.imread("./image.png") img = cv2.cvtColor(img, cv2.COLOR_RGB2GRAY)
# edge detection
img = cv2.GaussianBlur(img, (3,3), 1.5)
canny = cv2.Canny(img, 180, 40)
\end{lstlisting}
Wird dieser Code auf das Beispielbild \ref{fig: beispiel bild} angewendet und das Ergebnis des \glspl{canny} ausgegeben, ergibt sich
\autoref{fig: canny edges}. Im Gegensatz zu Alternativen, wie einer reinen Gradientenbetrachtung, liefert der \gls{canny}
Kantenmarkierungen, hier in Weiß, die nur einen \gls{Pixel} breit sind. Dies ermöglicht die in den folgenden Unterkapiteln
beschriebenen Schritte.
\begin{figure}
\includegraphics[width=.6\textwidth]{img/Marks_cannyedges.png}
\caption{Vom Canny-Edge-Detector gefundene Kanten}
\label{fig: canny edges}
\end{figure}
\subsection{Klassifizierung der Kantenpixel}
Nur die Identifikation von Pixeln als Kantenpixeln reicht nicht aus, um Linienmarkierungen zu erkennen. Menschen fällt es zwar
leicht in \autoref{fig: canny edges} die gesuchten Linien zu identifizieren, für den Algorithmus handelt es sich aber nur um eine
scheinbar zufällige Ansammlung von weißen Pixeln. Es werden weitere Informationen benötigt.
Deshalb wird jedem Kantenpixel eine Klasse entsprechend seiner Orientierung zugeordnet. Um die Datenmenge gering und die Laufzeit
schnell zu halten, werden lediglich die vier Klassen \emph{Vertikal}, \emph{Horizontal}, \emph{Diagonal 1} und \emph{Diagonal 2}
verwendend. Zusätzlich wird noch die Richtungsinformation als Vorzeichen abgespeichert.
Die Klassifizierung erfolgt anhand der \gls{Gradientenorientierung} eines Pixels. Dazu werden mit $3\!\times\!3$ Sobel-\glspl{Kernel} die
Gradienten $d_x$ und $d_y$ bestimmt. Mit der \lstinline{atan2()} Funktion kann aus diesen beiden Größen der Winkel des Gradientenvektors
$\vec{G}$ berechnet werden. Mit diesem Winkel kann nun entsprechen der \autoref{fig: gadienten orientierung} die Klasse bestimmt werden.
Dabei ist zu beachten das $\vec{G}$ immer orthogonal auf der eigentlichen Kante steht, deshalb ist die Klasse \emph{Vertikal} auch auf der
links-rechts Achse der Abbildung zu finden.
\begin{figure}
\includegraphics[width=.4\textwidth]{svg/CannyEdge_Orientation.pdf}
\caption{Klassifizierung der Gradientenorientierung (nach \cite{Homann:VorlesungBildverarbeitung})}
\label{fig: gadienten orientierung}
\end{figure}
\pagebreak
Die Klassifizierung wird in einer 8-Bit Variable abgespeichert, da so ein normales Graustufen-Bild als Datenstruktur verwendet werden
kann. Jeder Klasse wird dabei ein Bit wie folgt zugeordnet:
\begin{table}
\caption{Zuordnung der Klassen zu Bits}
\begin{tabular}{r l}
Bit & Klasse \\
1 & \emph{Vertikal} \\
2 & \emph{Diagonal 1} \\
3 & \emph{Diagonal 2} \\
4 & \emph{Horizontal} \\
5 & Vorzeichen-Bit \\
\end{tabular}
\end{table}
Um die Klassifizierung in \gls{python} durchzuführen, wird zuerst ein weiteres, leeres 8-Bit Bild mit identischer Größe angelegt. Dann
wird erneut über alle \gls{Pixel} des Bildes iteriert. Da allerdings die meisten \gls{Pixel} schwarz und damit uninteressant sind, können
diese direkt verworfen werden. Für alle verbleibenden, weißen \gls{Pixel} wird die Klassifizierung durchgeführt.
\begin{lstlisting}[
float,
style=example,
caption={Schleife über das vom \gls{canny} gelieferte Bild},
language=Python
]
for (u, v), e in np.ndenumerate(canny[1:-1, 1:-1]):
if not e:
continue u += 1
v += 1
\end{lstlisting}
\begin{equation}\label{eq: dx dy}
\begin{split}
d_x &=
\begin{bmatrix}
p_{\text{-}1\text{-}1} & p_{\text{-}10} & p_{\text{-}11} \\
p_{0\text{-}1} & p_{00} & p_{01} \\
p_{1\text{-}1} & p_{10} & p_{11} \\
\end{bmatrix}
\circ
\begin{bmatrix}
0 & 0 & 0 \\
-1 & 0 & +1 \\
0 & 0 & 0 \\
\end{bmatrix}
\\
d_y &=
\begin{bmatrix}
p_{\text{-}1\text{-}1} & p_{\text{-}10} & p_{\text{-}11} \\
p_{0\text{-}1} & p_{00} & p_{01} \\
p_{1\text{-}1} & p_{10} & p_{11} \\
\end{bmatrix}
\circ
\begin{bmatrix}
0 & -1 & 0 \\
0 & 0 & 0 \\
0 & +1 & 0 \\
\end{bmatrix}
\end{split}
\end{equation}
Dazu werden zuerst die Gradienten $d_x$ und $d_y$ ermittelt. Dazu wird die $3\!\times\!3$ \gls{Pixelnachbarschaft} des aktuellen Pixels
elementweise mit dem jeweiligen Sobel-\gls{Kernel} multipliziert und die Summe der Ergebnismatrix gebildet (siehe \autoref{eq: dx dy}).
Das Pythonpaket \lstinline{numpy} stellt hierfür sehr hilfreiche Funktion zum Arbeiten mit Matrizen zur Verfügung. Dadurch lässt sich
diese Operation in wenigen Zeilen durchführen, wie \autoref{code: dx dy} gezeigt.
\begin{lstlisting}[
float,
style=example,
caption={Bestimmung der Gradienten $d_x$ und $d_y$},
label=code: dx dy,
language=Python
]
nh = img[u-1:u+2, v-1:v+2]
dx = np.sum(nh * SOBEL_X)
dy = np.sum(nh * SOBEL_Y)
\end{lstlisting}
Mit diesen wird nun die \lstinline{atan2(dy,dx)} Funktion aufgerufen. Diese gibt einen Winkel in rad zurück, welcher zur besseren
Nachvollziehbarkeit in Grad umgerechnet wird.
Durch eine Folge von Bedingungen wird nun die Klasse des aktuellen Pixels bestimmt. Zuerst wird das Vorzeichen bestimmt und im 5. Bit
abgespeichert. Dies vereinfacht die folgenden Abfragen, da für die \emph{Vertikal} und \emph{Horizontal} Klasse der Betrag des Winkels
ausreicht.
Ist die Klasse bestimmt, wird das entsprechende Bit des Pixels gesetzt. Die Umsetzung in Python ist in
\autoref{code: python Klassifizierung} gezeigt.
\begin{lstlisting}[
float,
style=example,
caption={Durchführen der Klassifizierung mittels des bestimmten Winkels},
label=code: python Klassifizierung,
language=Python
]
arc = atan2(dy, dx) / pi * 180
if arc < 0:
pixel_info[u, v] |= 0x10
arc = abs(arc)
if arc >= 157.5 or 22.5 > arc:
pixel_info[u, v] |= V
elif 22.5 <= arc < 67.5:
pixel_info[u, v] |= D1 if not pixel_info[u, v] else D2
elif 67.5 <= arc < 112.5:
pixel_info[u, v] |= H
elif 112.5 <= arc < 157.5:
pixel_info[u, v] |= D2 if not pixel_info[u, v] else D1
\end{lstlisting}
Wurde jeder Kantenpixel klassifiziert, ist der Vorgang beendet. Zur Veranschaulichung wurde ein Bild erstellt, in dem jeder Klasse und
Vorzeichen eine eindeutige Farbe zugeordnet ist. So ist genau zu erkennen, welche Kanten derselben Klasse zugeordnet wurden. Diese Bild
ist in \autoref{fig: classified edges} gezeigt.
\begin{figure}
\includegraphics[width=.6\textwidth]{img/Marks_classification.png}
\caption{
Klassifizierte Kanten mit farblicher Markierung der unterschiedlichen Klassen
(Farben sind nicht identisch mit \autoref{fig: gadienten orientierung})
}
\label{fig: classified edges}
\end{figure}
\subsubsection{Genauigkeit der Klassifizierung} \label{sub: genauigkeit klassifizierung}
Die Klassifizierung erfolgt nicht immer völlig zuverlässig. Gut klassifizierte Kanten haben für die gesamte Länge der Linie
dieselbe Klasse erhalten, wie es im vergrößerten Bildausschnitt \autoref{fig: gute kante} zu sehen ist. Im Gegensatz dazu haben
unzuverlässig klassifizierte Kanten mehrere Klassen in einem engen Bereich und wechseln häufig sogar mehrfach zwischen mehreren
Klassen, wie das Beispiel in \autoref{fig: schlechte kante} zeigt.
\begin{figure}
\subfigure[Beispiel guter Kantenklassifizierung]{
\label{fig: gute kante}
\includegraphics[scale=4]{img/Marks_classification_cut1.png}
}
\subfigure[Beispiel schlechter Kantenklassifizierung]{
\label{fig: schlechte kante}
\includegraphics[scale=4]{img/Marks_classification_cut2.png}
}
\caption{Vergleich von gut und schlecht klassifizierten Bildbereichen}
\end{figure}
Durch Störungen und generell schlechtere Bildqualität in weiter von der Kamera entfernten Bildbereichen weisen vor allem die äußeren
Linien viele dieser Ungenauigkeiten auf. Das führt dazu, dass die nachfolgende Logik viele einzelne, kleine Linien anstatt der
vollständigen, durchgängigen Linie, erkennt.
Die zentralen Linienmarkierungen der eigenen Spur werden aber zuverlässig genug klassifiziert.
\subsection{Linienbildung} \label{sec: linien finden}
Mit den Informationen über die Kantenklasse kann nun der eigentliche Prozess der Linienerkennung erfolgen. Dieser gliedert sich in zwei
Schritte, das Zusammenfassen von gleich klassifizierten Kantenpixeln zu durchgängigen Linien und das Zusammenfassen von Linien zu einer
Fahrspurmarkierung.
Für den ersten Schritt ist es ein weiteres Mal nötig, über das gesamte Bild zu iteriert. Auch diesmal können wieder alle schwarzen Pixel
übersprungen werden. Wird ein klassifiziertes \gls{Pixel} gefunden, muss überprüft werden, ob es sich um ein Startpixel handelt. Startpixel sind
Pixel, die keine Nachbarn in der ihrer Klasse entsprechenden Ursprungsrichtung haben. Zum Beispiel wäre ein \gls{Pixel} der \emph{Vertikal}
Klasse ein Startpixel, wenn sich direkt oder diagonal über ihm keine weiteren \gls{Pixel} derselben Klasse befinden.
Ist ein Startpixel gefunden, wird es für später abgespeichert. Nun wird der Linie zu ihrem Ende gefolgt. Dazu wird der nächste
Nachbarpixel gesucht. Da die grobe Richtung entsprechend der Klasse bekannt ist, müssen hier nicht alle Nachbarpixel überprüft werden.
Beim Beispiel mit der \emph{Vertikal} Klasse müssten die \gls{Pixel} direkt und diagonal unterhalb betrachtet werden. Existiert ein
Nachbar wird dieser ausgewählt und der Prozess wiederholt. Dabei werden alle bereits besuchten \gls{Pixel} aus dem Bild gelöscht, damit
sich nicht noch einmal untersucht werden.
\begin{lstlisting}[ float,
style=example,
caption={Verfolgen einer Linie vom Start- zum Endpunkt},
label=code: follow line,
language=Python
]
start = (u, v)
relevant_nh *= -1
while True:
pixel_info[u, v] = 0
for x, y in relevant_nh:
if e == pixel_info[u+x, v+y] & 0x0f:
u, v = u+x, v+y
break
else: # no more neighbours
break
l = Line(start, (u, v), info)
if l.length > 5:
lines.append(l)
\end{lstlisting}
Hat ein \gls{Pixel} keine weiteren Nachbarn, ist er der Endpunkt dieser Linie. Start- und Endpunkt werden in ein Linienobjekt
zusammengefasst und abgespeichert. Zusätzliche wird ebenfalls die Orientierungsklasse mit abgespeichert.
Mittels Start- und Endpunkt kann außerdem die Länge der Linie bestimmt werden. Da durch die in \autoref{sub: genauigkeit klassifizierung}
beschriebenen Störungen viele kurze Linien gefunden werden, deren Berücksichtigung zu viel Rechenzeit in Anspruch nehmen würde, werden
Linien unter einer Minimallänge von 5 Pixeln vernachlässigt.
Akzeptierte Linien werden ihrer Orientierung entsprechen in einzelnen Listen abgespeichert, sodass am Ende eine Liste für jede
Orientierungsklasse entstanden ist.
\medskip
Da ein Linienmarker immer aus einer linken und einer rechten Kante besteht, kann dieser durch Bilden von Linienpaaren gleicher
Orientierung, aber unterschiedlichem Vorzeichen, die in geringem Abstand zueinander liegen, identifiziert werden.
Dazu werden die Elemente der entsprechenden Listen nacheinander miteinander verglichen, bis ein passendes Paar gefunden wurde. Ein
Beispiel ist in \autoref{code: find pairs} für Linienmarkierungen der Orientierung \emph{Diagonal 1} gezeigt. Es wird für jeden Kandidaten
aus der ersten Liste ein Partner in der zweiten Liste gesucht. Ein solcher ist gefunden, wenn die Start- und Endpunkte beider Linien
innerhalb bestimmter Bereiche liegen.
\begin{lstlisting}[
float,
style=example,
caption={Finden von Linienpaaren in Python},
label=code: find pairs,
language=Python
]
for a in left_D1_edges:
for b in right_D1_edges:
if (
(a.start[0] - 20) < b.start[0] < (a.start[0] + 20) and
a.start[1] < b.start[1] < (a.start[1] + 30) and
(a.end[0] - 20) < b.end[0] < (a.end[0] + 20) and
a.end[1] < b.end[1] < (a.end[1] + 20)
):
markings_found.append(LineMarking(a,b, "left"))
right_D1_edges.remove(b)
break
\end{lstlisting}
Die gefundenen Linienpaare werden zu einem Linienmarker Objekt zusammengefasst. In diesem wird der Umriss bestehend aus den vier
Linienpunkten abgespeichert. Außerdem wird der Mittelwert der beiden Start- und Endpunkte gebildet und somit die Mittellinie des
Linienmarkers angenähert.
So gefundene Linienmarker lassen sich wieder im Beispielbild markieren, wodurch sich \autoref{fig: found markings} ergibt. Wie man dort
sehen kann, wurden die Linienmarker der eigenen linken und rechten Fahrspurbegrenzung erfolgreich identifiziert. Weitere Markierungen
anderer Spuren konnten aufgrund der unzuverlässigen Klassifizierung nicht erkannt werden.
\begin{figure}
\includegraphics[width=.6\textwidth]{img/Marks_found-lines.png}
\caption{Umrisse und Mittellinien der gefundenen Fahrspurmarkierungen}
\label{fig: found markings}
\end{figure}
\subsubsection{Komplexere Szenen}
Nicht jede Situation, auf die der Roboter treffen kann, führt zu so guten Ergebnissen wie das gezeigte Beispiel. Daher sind in
\autoref{fig: vergleich szenen} einige weitere Beispiele und die darin detektierten Markierungen im direkten Vergleich gezeigt.
In \ref{subfig: demo C} sind die Linienbegrenzungen nahe am Fahrzeug durchgezogen und werden erst in größerer Entfernung gestrichelt.
Hier war die Erkennung der durchgezogenen Teile sehr gut möglich, jedoch kam es zu einer unpräzisen Identifizierung im oberen Teil der
rechten Linie, da sich zwei Liniensegmente unterschiedlicher Linien zu nahe aneinander befanden.
Bei der Szene \ref{subfig: demo A} handelt es sich um eine Kurve. Dies erschwert die Erkennung deutlich, da eine durchgängige
Klassifizierung einer Kante nicht garantiert ist. Daher sind auch nicht alle Spurmarkierungen identifiziert.
Der letzte Vergleich \ref{subfig: demo B} zeigt eine Szene mit vollständig durchgezogener Linie. Dies ist aus dem Grund schwierig,
dass die Wahrscheinlichkeit einer Störung durch die hohe Pixelanzahl sehr groß ist. Daher wurde die rechte Kante der Linie auch nicht
durchgängig erkannt und der gefunden Marker wirkt verzehrt.
\begin{figure}
\subfigure[lange Linien]{ \label{subfig: demo C}
\includegraphics[width=.23\textwidth]{img/demo_org_C.png}
\includegraphics[width=.23\textwidth]{img/demo_found_C.png}
}
\subfigure[leichte Kurve]{ \label{subfig: demo A}
\includegraphics[width=.23\textwidth]{img/demo_org_A.png}
\includegraphics[width=.23\textwidth]{img/demo_found_A.png}
}
\subfigure[durchgezogene Linie]{ \label{subfig: demo B}
\includegraphics[width=.23\textwidth]{img/demo_org_B.png}
\includegraphics[width=.23\textwidth]{img/demo_found_B.png}
}
\caption{Ergebnisse bei komplexeren Szenen im Vergleich}
\label{fig: vergleich szenen}
\end{figure}
\section{Implementierung in eine ROS Node}
Um den Algorithmus zur Erkennung von Spurmarkierungen auf jedes Kamerabild anwenden zu können, wird er in einer \gls{ROS Node} umgesetzt. Da
der Python-Code bereits auf einem leistungsfähigen Entwickler-PC Laufzeiten von $>0,25\,\s$ hat, wird die Programmiersprache \gls{C++} für die
\gls{ROS Node} gewählt. Dadurch sollte sich die Performance deutlich verbessern.
\subsection{Erstellung des Quellcodes}
Die Beziehung der neuen \gls{ROS Node} zu den bestehenden \glspl{ROS Node} wurde bereits in \autoref{fig: topics marker detection} skizziert.
Dort sieht man, dass für die \gls{ROS Node} der Namen \lstinline{lane_marker_detection} gewählt wird. Außerdem wird das \gls{Topic}
\lstinline{/img/gray} von der Entzerrer-\gls{ROS Node} abonniert, um jedes Schwarz-Weiß Bild zu bekommen. Das Bild mit den eingezeichneten,
detektierten Spurmarkierungen wird nach Durchlauf des Algorithmus auf dem eigenen \gls{Topic} \lstinline{/img/lanemarkings} veröffentlicht.
Beim Abonnieren des \lstinline{/img/gray} Topics wird die \gls{Callback} \lstinline{callback_image()} angehängt, sodass diese von \gls{ROS}
für jedes Bild aufgerufen und das Bild an sie übergeben wird. Da dieses in einem \gls{ROS} eigenen Bild-Datentyp übergeben wird, \gls{OpenCV}
diesen aber nicht verwenden kann, ist es nötig das Bild zuerst einmal in einen anderen Datentyp umzuwandeln. Hierzu wird wieder das ROS-Paket
\lstinline{cv_bridge} und dessen Funktion \lstinline{toCvCopy()} verwendet.
\subsubsection{Kantenerkennung und Klassifizierung}
Das so konvertierte Bild kann nun an die Funktion \lstinline{edgeDetectionClassification()} übergeben werden, welche die Erkennung und
Klassifizierung der Kanten durchführt. Wie bereits in der \gls{python}-Version wird wieder der \gls{canny} aus \gls{OpenCV} verwendet. Dadurch
können die Parameter einfach übernommen werden. Der \autoref{code: canny c++} zeigt den Aufruf. Das Ergebnis mit den detektierten Kanten wird
in der Variable \lstinline{canny} abgespeichert.
\begin{lstlisting}[
float, style=example,
caption={Aufruf des \gls{canny} in \gls{C++}},
label=code: canny c++,
language=C++
]
cv::Mat canny;
cv::Canny(image, canny, 180, 50);
\end{lstlisting}
Die Implementierung der Kantenklassifizierung in \gls{C++} läuft im Groben sehr ähnlich zur \gls{python}-Version, die wichtigsten
Unterschied sind die For-Schleifen für beide Dimensionen des Bildes, welche explizit einzeln verwendet werden müssen, und die Beachtung
von Datentypen.
Die Erstellung des benötigten, leeren Bildes und die For-Schleifen sind in \autoref{code: schleifen klassifizierung} zu sehen. Auch hier
werden wieder aller leeren \gls{Pixel} übersprungen.
\begin{lstlisting}[
float,
style=example,
caption={Inizialisieren des leeren Bildes und iterieren über jenes.},
label=code: schleifen klassifizierung,
language=C++
]
cv::Mat classified_edges = cv::Mat::zeros(cv::Size(image.cols,image.rows), CV_8U);
for (int u=1; u < image.rows-1; u++) {
for (int v=1; v < image.cols-1; v++) {
if ( ! canny.at<uint8_t>(u,v) )
continue;
\end{lstlisting}
Die Bestimmung der Gradienten mittels Sobel wirkt in \gls{C++} deutlich komplizierter, da hier vieles manuell gemacht werden muss, was in
\gls{python} von \lstinline{numpy} erledigt wurde. Mit zwei For-Schleifen wird über die $3\!\times\!2$ \gls{Pixelnachbarschaft} iteriert, die
Elemente mit dem \gls{Kernel} multipliziert und aufsummiert, wie in \autoref{code: sobel c++} zu sehen.
\begin{lstlisting}[
float,
style=example,
caption={Bestimmung der Gradienten mittels Sobel},
label=code: sobel c++,
language=C++
]
uint8_t e;
int dx=0, dy=0;
for (int y=0; y<3; y++) {
for (int x=0; x<3; x++) {
e = image.at<uint8_t>(u+y-1,v+x-1);
dx += SOBEL_X[y*3+x] * e;
dy += SOBEL_Y[y*3+x] * e;
}
}
\end{lstlisting}
Die eigentliche Klassifizierung ist praktisch identisch zur \gls{python}-Version. Lediglich die Überprüfung der Winkelbereiche ist etwas
langwieriger, da nicht mehrere Vergleiche direkt nacheinander möglich sind. Die Codierung der Klassen Erfolg wieder über die einzelnen Bit
des Bytes der einzelnen Pixel.
Die Umsetzung ist in \autoref{code: klassen c++} dargestellt.
\begin{lstlisting}[
float,
style=example,
caption={Bestimmung der Gradienten mittels Sobel},
label=code: klassen c++,
language=C++
]
double arc = atan2(dy,dx) / 3.1415 * 180.0;
uint8_t clsif = 0;
if (arc < 0)
clsif = 0x10;
arc = fabsf(arc);
if (arc<=22.5f || arc>157.5f ) {
clsif |= V;
} else if ( 67.5f<=arc && arc<112.5f ) {
clsif |= H;
} else if (( !clsif && arc<67.5f )||( clsif && 112.5f<=arc )) {
clsif |= D1;
} else if (( clsif && arc<67.5f )||( !clsif && 112.5f<=arc )) {
clsif |= D2;
}
classified_edges.at<uint8_t>(u,v) = clsif;
\end{lstlisting}
Das Ergebnisbild mit den klassifizierten Pixeln wird von der Funktion zurückgegeben und dort weiterverarbeitet.
\subsubsection{Linienbildung}
Mit dem klassifizierten Bild kann nun dieselbe Methodik zur Identifizierung zusammenhängender Linien wie in Python angewendet werden.
Allerdings ist in \gls{C++} das Definieren und Testen der relevanten \gls{Pixelnachbarschaft} nicht so übersichtlich möglich wie in Python.
Daher müssen viele lange \lstinline{if}-Bedingungen verwendet werden, welche in den folgenden Codebeispielen zur Übersichtlichkeit verkürzt
sind.
Begonnen wird wieder mit einer doppelten \lstinline{for}-Schleife über das gesamte Bild, wie in \autoref{code: loop for lines c++} zu sehen. Dabei
werden wieder alle leeren \gls{Pixel} vernachlässigt.
\begin{lstlisting}[
float,
style=example,
caption={\lstinline{for}-Schleifen über alle klassifizierten Pixel},
label=code: loop for lines c++,
language=C++
]
for (int u=1; u < classified_edges.rows-1; u++) {
for (int v=1; v < classified_edges.cols-1; v++) {
uint8_t clsif_org = classified_edges.at<uint8_t>(u,v);
if ( ! clsif_org )
continue;
\end{lstlisting}
Für jeden \gls{Pixel} wird wieder überprüft, ob er ein Startpixel ist. Genau wie in \gls{python} ist hierfür wieder der Klasse entsprechend eine
\gls{Pixelnachbarschaft} relevant. Ist dort ein Nachbar gleicher Klasse vorhanden, wird mit dem nächsten \gls{Pixel} weitergemacht. Dies ist in
\autoref{code: test start c++} gezeigt.
\begin{lstlisting}[
float,
style=example,
caption={Überprüfen, ob ein \gls{Pixel} ein Startpixel ist},
label=code: test start c++,
language=C++
]
// get only classification without direction:
uint8_t clsif = 0x0f & clsif_org;
bool has_neighbour = false;
switch (clsif) {
case V:
if ( /* any of the relevant neighbours */ )
has_neighbour = true;
case D1:
if ( /* any of the relevant neighbours */ )
has_neighbour = true;
case H:
if ( /* any of the relevant neighbours */ )
has_neighbour = true;
case D2:
if ( /* any of the relevant neighbours */ )
has_neighbour = true;
}
if ( has_neighbour )
continue; \end{lstlisting}\todo{Zusammenkürzen, wie auch später gemacht?}
Ist ein Startpixel gefunden, wird er gespeichert und wieder so lange der nächste Nachbar ausgewählt, bis kein Nachbar mehr vorhanden ist.
Dann ist die gesamte Linie nachverfolgt. Dabei werden alle besuchten \gls{Pixel} aus dem Bild gelöscht. Siehe dazu \autoref{code: follow c++}.
\begin{lstlisting}[
float,
style=example,
caption={Line verfolgen, bis keine Nachbarn mehr existieren},
label=code: follow c++,
language=C++
]
pnt start(v,u);
// follow line to its end
do {
classified_edges.at<uint8_t>(u,v) = 0;
has_neighbour = false;
switch (clsif) {
case V:
if ( /* any neighbour exists */ )
// u+-;v+-; change u,v to new coordinates
has_neighbour = true;
case D1:
if ( /* any neighbour exists */ )
// u+-;v+-; change u,v to new coordinates
has_neighbour = true;
case D2:
if ( /* any neighbour exists */ )
// u+-;v+-; change u,v to new coordinates
has_neighbour = true;
}
case H:
if ( /* any neighbour exists */ )
// u+-;v+-; change u,v to new coordinates
has_neighbour = true;
}
} while ( has_neighbour );
\end{lstlisting}\todo{Zusammenkürzen, wie auch später gemacht?}
\pagebreak
Die so gefunden Linien werden wieder auf ihre Länge überprüft und als Objekte abgespeichert. Dabei werden einzelne Listen für jede Klasse
angelegt, sodass diese später verglichen werden können.
Besonders wichtig ist es, dass im Gegensatz zu \gls{python} die Schleifenvariablen \lstinline{u, v} manuell wieder auf die
Startkoordinaten zurückgesetzt werden müssen.
\subsubsection{Paarbildung}
Auch die Bildung von Linienpaaren aus einer rechten und linken Linie erfolgt analog zu \gls{python}. Hier gibt es auch keine großartigen
Unterschiede in der Umsetzung, wie \autoref{code: pairing c++} zu sehen ist.
Auch hier wird mit den gefundenen Paaren wieder ein Linienmarker-Objekt erzeugt und zur oberen Nutzung abgespeichert.
\begin{lstlisting}[
float,
style=example,
caption={Line verfolgen, bis keine Nachbarn mehr existieren},
label=code: pairing c++,
language=C++
]
for(const Line& a : left_D1_edges) {
for(auto it = right_D1_edges.begin(); it != right_D1_edges.end(); it++ ) {
const Line b = *it;
if (
( a.start.y - 10 < b.start.y && b.start.y < a.start.y + 10 ) &&
( a.start.x < b.start.x && b.start.x < a.start.x + 25 ) &&
( a.end.y - 10 < b.end.y && b.end.y < a.end.y + 10 ) &&
( a.end.x < b.end.x && b.end.x < a.end.x + 25 )
) {
markings_found.push_back(LineMarking(a,b, D1)); left_D1_edges.erase(it);
break;
}
}
}
\end{lstlisting}
Da noch nicht klar ist, wie genau die gefundenen Daten potenziell zukünftigen Prozessen zu Verfügung gestellt werden sollen, werden diese
zurzeit nicht veröffentlicht. Stadtmessen wird analog zur Python-Implementierung ein Bild mit eingezeichneten Spurmarkern erzeugt und als
visuelles Ergebnis zur Verfügung gestellt. Dieses kann unter dem \gls{Topic} \lstinline{/img/temp} abgerufen und live angeschaut werden.
\bigskip
\todo{pagebreak?}
\subsection{Performance Betrachtung}
Mit dieser zusätzlichen \gls{ROS Node} ist es erneut interessant, wie sich diese auf die Performance auswirkt. Aus \autoref{sec: intrinsic}
ist bereits die Performance mit laufender Kamera- und Entzerrer-Node bekannt. Zum Vergleich wurde wieder die Systemauslastung mit dem
Programm \lstinline{jtop} aufgenommen und die Durchlaufzeit nach Erhalt eines Bildes gemessen.
\begin{figure}
\includegraphics[width=.6\textwidth, trim={0 0 12px 31px}, clip]{img/jtop_cameraUndistortDetection.png}
\caption{CPU Auslastung des JetBots mit laufender Kamera, Entzerrung und Markierungserkennung}
\label{fig: jtop markings}
\end{figure}
Ein Screenshot von \lstinline{jtop} ist in \autoref{fig: jtop markings} abgebildet. Mit der zusätzlichen neuen \gls{ROS Node} ist die CPU
Auslastung nur geringfügig auf ca. $37,5\,\percent$ gestiegen, auch dies ist dank starker Fluktuation in der CPU Nutzung praktisch
vernachlässigbar.
Die Laufzeit-Performance der \gls{C++} implementiert ist wie erwartet deutlich besser als bei der \gls{python}-Version. Vom Erhalt des
Bildes bis zur Veröffentlichung des Ergebnisses mit den gefundenen Linienmarkierungen dauert es $\approx 3,46\,\ms$.
\begin{table}
\caption{Gemessene Laufzeit bei 10 Durchläufen der \gls{Callback}}
\begin{tabular}{r|S}
Durchlauf Nr. & \multicolumn{1}{c}{gemessene Laufzeit} \\\hline
1 & 5,049744 \,\ms \\
2 & 5,049744 \,\ms \\
3 & 5,186416 \,\ms \\
4 & 6,229117 \,\ms \\
5 & 5,328923 \,\ms \\
6 & 5,231026 \,\ms \\
7 & 6,762161 \,\ms \\
8 & 5,631071 \,\ms \\
9 & 5,309235 \,\ms \\
10 & 4,862289 \,\ms \\
\end{tabular}
\end{table}
\section{Optimierung\todo{oder "Versuchte Optimierung" ??} durch eigene Implementierung des Canny-Edge-Detectors}
Im Folgenden wird untersucht, ob eine eigene Implementierung des \gls{canny} einen Vorteil gegenüber der Verwendung von \gls{OpenCV} bietet.
Da die Bibliotheksfunktionen viel potenziell nicht benötigte Zusatzfunktionen und Schutzmechanismen enthalten, welche Zeit
und Performance benötigen und für deren Verwendung eine Datenumwandlung notwendig ist, kann eine eigene Implementierung hier Vorteile bieten.
Außerdem führt der \gls{canny} intern bereits eine Sobel-Filterung durch und es ließe sich die Klassifizierung dort direkt mit durchführen.
Das eliminiert die Notwendigkeit zweimal über das Bild zu integrieren.
\subsection{Anpassung des Quellcodes}
Da ohne \gls{OpenCV} das Bild nicht mehr in eine praktische Matrixform umgewandelt wird, muss ein eigener Datentyp definiert werden.
Dieser speichert die Daten im selben Format wie der verwendete \gls{ROS} Datentyp, sodass keine Umwandlung notwendig ist. Der Datentyp
ermöglicht lediglich den Zugriff auf die Daten über $x$ und $y$ Koordinaten.
\autoref{code: image class} zeigt die Umsetzung mit dem Namen \lstinline{Image}. Initialisiert werden kann eine Instanz entweder nur mit
Höhe und Breite, wodurch ein neues, leeres Bild erzeugt wird, oder mit einem existieren Bild, wobei dessen Daten übernommen werden.
Um auf die Bilddaten zuzugreifen, werden die Operatoren \lstinline{[]} überladen, sodass ein Punkt bestehen aus einer $x$ und einer $y$
Koordinate übergeben werden kann. Das entsprechende Pixel wird dann zurückgegeben oder beschreiben.
\begin{lstlisting}[
float,
style=example,
caption={Eigener Datentyp zum Ablegen von Bildern},
label=code: image class,
language=C++
]
class Image {
public:
std::vector<uint8_t> data;
int width; int height;
Image(int width, int height): data(width*height, 0), width(width), height(height) {};
Image(sensor_msgs::Image img): data(img.data), width(img.width), height(img.height) {};
uint8_t& operator[](pnt const& p) { return data[p.y*width + p.x]; }
const uint8_t& operator[](pnt const& p) const { return data[p.y*width + p.x]; }
};
\end{lstlisting}
Die \gls{Callback} \lstinline{callback_image()} verläuft völlig analog zur Implementierung mit \gls{OpenCV}. Der Unterschied liegt in der
Funktion \lstinline{edgeDetectionClassification()}. Diese führt nun die drei Schritte des \gls{canny} durch: Gradienten Bestimmung,
Unterdrücken von Nicht-Lokalen-Maxima und Hysterese-Grenzwertbildung (siehe \cite{Canny:computationAlapproachEdgeDetection}).
Zusätzlich wird außerdem die Klassifizierung durchgeführt. Da im ersten Schritt die Sobel-Gra\-di\-enten ohnehin berechnet werden, können hier
ohne viel Zusatzaufwand auch die Gradientenwinkel mit bestimmt werden. Der \autoref{code: own canny 1} zeigt diesen Schritt.
\begin{lstlisting}[
float,
style=example,
caption={Bestimmung der Sobel-Gradienten im \gls{canny}},
label=code: own canny 1,
language=C++
]
// Compute gradient magnitude and orientation
for (int u=1; u < image.height-1; u++) {
for (int v=1; v < image.width-1; v++) {
int dx=0, dy=0;
for (int y=0; y<3; y++){
for (int x=0; x<3; x++){
dx += SOBEL_X[y*3+x] * image[pnt(v+y-1,u+x-1)];
dy += SOBEL_Y[y*3+x] * image[pnt(v+y-1,u+x-1)];
}
}
gards[pnt(v,u)] = static_cast<int>(sqrt(dx*dx+dy*dy));
agls[pnt(v,u)] = static_cast<float>(atan2(dy,dx) / 3.1415*180.0);
}
}
\end{lstlisting}
Im zweiten Schritt werden nun zusätzlich zur Unterdrückung von Pixeln, welche kein lokales Maximum sind, auch die Klassen bestimmt und
abgespeichert. Da dieser Code sehr viele verschachtelte und gedoppelte \lstinline{if}-Abfragen aufweist, wird er in
\autoref{code: own canny 2} vereinfach gezeigt.
\begin{lstlisting}[
float,
style=example,
caption={Klassifizierung und Unterdrückung von Nicht-Lokalen-Maxima},
label=code: own canny 2,
language=C++
]
// Non-maximum suppression and classification
for (int u=1; u < image.height-1; u++) {
for (int v=1; v < image.width-1; v++) {
int grad = gradients[pnt(v,u)]; int arc = angles[pnt(v,u)];
if (arc < 0)
uint8_t negative = 0x10;
arc = fabsf(arc);
if ( /* is in a specific angle range */ ) {
canny_edges[pnt(v,u)] = negative|/* CLASSIFICATION */;
if ( /* is not local maximum */)
gradients[pnt(v,u)] = 0;
}
}
}
\end{lstlisting}
Der letzte Schritt der Hysterese-Grenzwertbildung wurde für diese Anwendung zu einem simplen Grenzwert vereinfacht. Dies erzeugt
ausreichend gute Ergebnisse.
Wichtig ist außerdem, dass im Gegensatz zu einem herkömmlichen \gls{canny} kein Binarisiertes Bild, mit nur völlig weißen oder völlig
schwarzen Pixelwerten, zurückgegeben wird. Stadtmessen enthalten alle detektierten Kantenpixel bereits den Wert, der ihre Klasse
repräsentiert.
\begin{lstlisting}[
float,
style=example,
caption={Grenzwertbildung und Ergebnissrückgabe},
label=code: own canny 3,
language=C++
]
// thresholding
uint8_t T1 = 40;
for (int u=1; u < image.height-1; u++)
for (int v=1; v < image.width-1; v++) {
pnt p(v,u);
canny_edges[p] = gradients[p] < T1 ? 0 : canny_edges[p];
}
return canny_edges;
\end{lstlisting}
\subsection{Performance Betrachtung}
Die wichtigste Frage ist nun, wie sich diese Implementierung im Gegensatz zum Ansatz mit \gls{OpenCV} verhält. Dazu wurden wieder die
CPU-Auslastung mittels \lstinline{jtop} erfasst und die Durchlaufzeit des Algorithmus für jedes Bild gemessen.
\begin{figure}
\includegraphics[width=.6\textwidth, trim={0 0 12px 31px}, clip]{img/jtop_cameraUndistortDetection_own.png}
\caption{CPU Auslastung des JetBots mit laufender Kamera, Entzerrung und Markierungserkennung mit eigener Implementierung}
\label{fig: jtop markings own}
\end{figure}
Wie aus \autoref{fig: jtop markings own} abzulesen ist, ist die CPU-Auslastung mit durchschnittlichen $37.75\,\percent$ exakt identisch
zur Implementierung mit \gls{OpenCV}. Das ist wenig überraschen, da der Algorithmus Grunde immer noch dieselbe Arbeit verrichtet.
\pagebreak[3]
Die Messung der Laufzeit zeigt allerdings, dass die eigene Implementierung deutlich weniger performant ist. Mit einer Durchlaufzeit von
$\approx 22,58\,\ms$ ist diese Version um mehr als Faktor 6 größer. Hier gleichen die Vorteile durch das Kombinieren von Einzelschritten
die Leistungsfähigkeit einer stark optimierten Bibliotheksfunktion also leider nicht mal annähern aus.
\begin{table}
\caption{Gemessene Laufzeit bei 10 Durchläufen der \gls{Callback}}
\begin{tabular}{r|S}
Durchlauf Nr. & \multicolumn{1}{c}{gemessene Laufzeit} \\\hline
1 & 22,266302 \,\ms \\
2 & 22,063851 \,\ms \\
3 & 22,126713 \,\ms \\
4 & 22,595543 \,\ms \\
5 & 23,369521 \,\ms \\
6 & 22,278288 \,\ms \\
7 & 24,207147 \,\ms \\ 8 & 22,546738 \,\ms \\
9 & 22,096768 \,\ms \\
10 & 22,201099 \,\ms \\
\end{tabular}
\end{table}