implementation.tex

\chapter{Fahrspurerkennung} \label{chap: implementation}

	Dieses Kapitel thematisiert, wie die Erkennung der Fahrspurmarkierungen umgesetzt wir. 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
	best möglichst 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 die eigenen Ergebnis als neues \gls{Topic} zur Verfügung stellt.

	\section{Konzeptionierung in Python}

		Die Entwicklung und Konzeptionierung des Algorithmus Erfolg in \gls{python}, da diese Sprache nicht kompiliert werden muss, was das Testen
		beschleunigt, und generell einfacher zu verwenden ist.

		Der Algorithmus lässt sich in mehre Einzelschritte aufteilen und wird daher in den folgen Unterkapitel beschreiben. Zur Übersicht
		ist aber der gesamte Ablauf in \autoref{fig: PAP} vereinfacht 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{Ein Beispiel Bild 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 Kante im Bild. Dazu wird das Bild zuerst mit \gls{OpenCV} geladen. \todo{Absatz Ja/Nein?}

			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} stell hierzu die Funktion \lstinline{GaussianBlur()} zur Verfügung, der das geladene Bild, die
			Kegelgröß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 Pixel den
			Gradientenbetrag der Gradienten in X- und Y-Richtung. Dann werden diejenigen Pixel unterdrückt, welche entlang der Gradientenrichtung kein
			Maximum darstellen. Zum Abschluss wird das Bild mit einem Hysterese-Schwellwert binarisiert. Das bedeutet, dass alle 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 Grabentenbetrachtung, liefert der \gls{canny}
			Kantenmarkierungen (hier in weiß) die nur ein\todo{einen?} 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 bereits Linienmarkierungen zu erkennen. Uns 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
			"zufällige"\todo{"zufällige" OK?} Ansammlung von weißen Pixeln. Es werden weiter Informationen benötigt.

			Deshalb werden 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 Klassifizierte 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, leere 8-Bit Bild mit identischer Größe angelegt. Dann wird
			erneut über alle Pixel des Bildes iteriert. Da allerdings die meisten Pixel schwarz und damit uninteressant sind, können diese direkt
			verworfen werden. Für alle verbleibenden, weißen 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}

			Zuerst die Gradienten $d_x$ und $d_y$ ermittel. Dazu wird die $3\!\times\!3$ 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 zu 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 werden 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.

			Nun werden durch eine Folge von Bedingungen 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{Vertikale} und \emph{Horizontale} 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 mittel 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, wo 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}

				Die Klassifizierung erfolgt leider 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 gut und schlecht klassifizierte Bildbereiche}
				\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, das 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}

			\begin{figure}
				\includegraphics[width=.6\textwidth]{img/Marks_found-lines.png}
				\caption{Umrisse und Mittellinien der gefundenen Fahrspurmarkierungen}
				\label{fig: found markings}
			\end{figure}


		\subsection{Performance Betrachtung}

			sehr schlecht offensichtlich...


	\section{Implementierung in eine ROS Node}

		\subsection{Performance Betrachtung}


	\section{Optimierung durch eigene Implementierung des Canny-Edge-Detectors}

		\subsection{Performance Betrachtung}