Spurerkennung

Im folgenden wird beschrieben, wie die Funktion der Spurerkennung realisiert wurde. Dabei wird ebenfalls auf die Hardware eingegangen, die im fertigen Fahrzeug verwendet wird. Auch die Testumgebung, mit der der Algorithmus zur Spurerkennung entwickelt wurde, wird hier beschrieben.

Ein Video zur schnellen Übersicht befindet sich hier

Hilfreiches Kapitel: Kantenerkennung

Autor: Konstantin Wotschel (Diskussion)

Hardware

Als Aufnahmesystem wird das Kameramodul VRmDC-12 COB von der Fa. VRmagic GmbH verwendet. Es besteht aus einem CMOS-Sensor, der mit einer Auflösung von 754 x 480 Pixel und einer Bildrate von 69 fps arbeitet. Es kann sowohl monochrome Bilder als auch Farbbilder aufnehmen. Des Weiteren besitzt es zwei Rechenwerke, die miteinander via Shared Memory kommunizieren können. Zum einen ist als zentrale Einheit ein 300 MHz ARM9 Prozessor verbaut, auf dem ein Linux Betriebssystem läuft. Damit werden u.a. die Schnittstellen des Kameramoduls verwaltet. Als zweite Recheneinheit ist ein 600 MHz C64x+ DSP integriert, der für schnelle digitale Signalverarbeitung konzipiert ist. Als Schnittstellen bietet das Kameramodul:

- einen USB 2.0 Port, zum importieren/exportieren von Daten
- einen 100 Mbit Ethernet-Anschluss mit RJ45-Buchse zur Ansteuerung/Übertragung der Bilddaten
- einen MPE-Garry Micro-T Anschluss für u.a. RS232 und SVideo und
- einen Hirose DF14-15P Anschluss für JTAG (Joint Test Action Group)

Zur deutlicheren Veranschaulichung der beiden letzten Anschlüsse, wird die Pinbelegung aufgezeigt.

Pinbelegung MPE-Garry Micro-T und Hirose DF14-15P. Quelle: VRmagic

Zwar besitzt dieses Kamera-Modul eine optimale Hardware zur Verarbeitung von digitalen Signalen und würde für die Spurerkennung in Frage kommen, doch ist die Programmierung auf dem Linux Betriebssystem aufwendig und wurde daher von der Vorgruppe (SDE 2012) nicht verwendet. Stattdessen wurde das Kameramodul via Ethernet mit dem auf dem Fahrzeug integrierten Motherboard verbunden und so die Bilddaten versendet. VRmagic bietet eine C++-Bibliothek für das Kameramodul an, wodurch die Integration in Visual Studio und somit der Zugriff über C++ auf die Ethernet-Schnittstelle bzw. die Bilddaten vereinfacht wird.

Testumgebung

Damit man nicht auf das Kameramodul angewiesen ist und das Fahrzeug den anderen Gruppen überlassen kann, um so parallel arbeiten zu können, wurde eine Testumgebung erstellt. Die Testumgebung wurde mit Visual Studio entwickelt und ist eine Konsolenanwendung, die zur Visualisierung ein SDL-Fenster erzeugt. Mit dem Programm können Bitmap-Dateien eingelesen und im SDL-Fenster angezeigt werden. Dabei werden die Bilddaten in einem Array zur Weiterverarbeitung gespeichert. Als Bitmap-Dateien wurden Aufnahmen mit dem Kamera-Modul, das sich auf dem Fahrzeug in seiner entsprechenden Position befand, erzeugt, um somit möglichst real-herrschende Bedingungen zu haben. In der Main-Funktion wird lediglich das SDL-Fenster initialisiert und anschließend erfolgt eine Endlos-Schleife, in der das SDL-Fenster mit der Funktion "`ShowImage(info.width, info.height, imageBuffer)"' die Bilddaten anzeigt, die sich in der Variable "`imageBuffer"' befinden. Weiterhin befindet sich in der Main-Funktion eine Switch-Case-Abfrage, die bei einem Tastendruck eine bestimmte Aktion ausführt.

" " (Leertaste) => Bilddaten der Bitmap-Datei neu laden
"." (Punkt) => Bilddaten der nächsten Bitmap-Datei laden
"," (Komma) => Bilddaten der vorherigen Bitmap-Datei laden

Es können hier noch weitere Aktionen angefügt werden.

Bemerkung: Beim Ausführen des Programms werden zwei Fenster geöffnet (SDL-Fenster und Konsole). Die Tasten-Erkennung funktioniert nur, wenn das Konsolen-Fenster aktiv bzw. im Vordergrund ist.

Nach jeder dieser Aktionen wird über die neu generierten Bilddaten die Funktion LaneDetection angewandt. Dieser Funktion werden die Höhe und Breite sowie die Bilddaten der ausgewählten Bitmap-Datei übergeben. Auf diese Bilddaten kann man in der Funktion seinen Algorithmus anwenden. Die Bilddaten werden dann in der Funktion verändert (z.B. indem Kanten eingezeichnet werden) und nach dem Ende der Funktion werden die neuen Bilddaten in der Endlosschleife durch "`ShowImage(info.width, info.height, imageBuffer)"' auf dem SDL-Fenster angezeigt.

Bemerkung: Die Bilddaten werden in der Funktion verändert und bleiben verändert, d.h. sollte man durch erneutes Drücken der Taste "e" die Funktion ausführen, wird der Algorithmus auf die eventuell eingezeichnete Kanten/Spuren angewendet.

Diese Funktion ist ebenfalls in der ersten Version der Online-Spurerkennung implementiert und kann einfach von der Offline-Testumgebung übernommen werden. Es müssen nur die Parameter angepasst werden, da in der Online Spurerkennung als Parameter die eingehenden Bilddaten von der Kamera und die ausgehenden Bilddaten für die Visualisierung auf dem SDL-Fenster übergeben werden.

Kantenextraktion im Kamerabild

Im Folgenden wird der Algorithmus beschrieben, wie die Kanten aus dem Kamerabild extrahiert werden. Als Quellcode wird das Programm aus der Testumgebung gezeigt.

ROI - Region Of Interest

Um Speicher und Rechenaufwand einzusparen, sollen alle folgenden Schritte nur in einem Bereich des Kamerabildes angewendet werden. Der Bereich wird mit den Variablen xstart, xende, ystart und yende beschrieben und errechnet sich aus der Höhe und Breite des gesamten Bildes und der Subtraktion des gewünschten Rahmens, der nicht einbezogen werden soll. Im folgenden Code wird gezeigt, wie der Bereich des Bildes festgelegt wird und im oberen/unteren Bereich 150 Pixel sowie im rechten/linken Bereich 50 Pixel eingespart werden.

// Grenzen für ROI bestimmen
unsigned int xstart = 50;
unsigned int xende = width - 50;

unsigned int ystart = 150;
unsigned int yende = height - 150;

Um weiterhin Rechenzeit zu sparen, wird auch nicht das gesamte Bild in der ROI durchlaufen, sondern nur einige Pixel-Zeilen. Das Intervall, also der Abstand zwischen den Zeilen, kann mit der Konstanten ROW_INTERVALL gewählt werden. Je größer der Wert desto weniger Zeilen werden durchlaufen und es wird Rechenzeit eingespart. Jedoch sinkt damit auch die Genauigkeit der zu erkennenden Spur. Ein Wert von 5 wird hier vorerst festgelegt.

Sobel-Filter und Gradient

Der Sobel-Filter mit der folgenden Filter-Matrix in X- und Y-Richtung

$S_{x} = \begin{bmatrix} 1 & 0 & -1\\ 2 & 0 & -2 \\ 1 & 0 & -1 \end{bmatrix} S_{y} = \begin{bmatrix} 1 & 2 & 1\\ 0 & 0 & 0 \\ -1 & -2 & -1 \end{bmatrix}$

ist ein Filter, der sowohl die Kanten eines Bildes hervorhebt und gleichzeitig das Rauschen unterdrückt, da er alle 8 Nachbarn eines Pixels einbezieht. Obwohl nur eine Zeile durchlaufen wird, werden auch die oberen und unteren Zeilen zur Berechnung des Gradienten einbezogen. Der Gradient ist ein Maß für eine Kante in einem Bild und errechnet sich wie folgt:

$G = \sqrt{G_{x}^2 + G_{y}^2}$

Die Werte $G_{x}$ und $G_{y}$ ergeben sich aus der Faltung der Sobel-Matrizen in X- und Y-Richtung. Der folgende Code zeigt die Faltung mit dem Sobel-Operator und die Erzeugung eines Gradienten-Bildes.

// Sobel Matrix Gx
int gx[3][3] =
{
	{ 1, 0, -1 },
	{ 2, 0, -2 },
	{ 1, 0, -1 }
};

// Sobel Matrix Gy
int gy[3][3] =
{
	{  1,  2,  1 },
	{  0,  0,  0 },
	{ -1, -2, -1 }
};

// Puffer-Speicher für die Gradientenwerte anlegen
unsigned char *gradient;
gradient = new unsigned char[(xende - xstart + 1) * int((yende - ystart) / ROW_INTERVALL)];

float grad; // Zwischenspeicher für den aktuell errechneten Gradienten

// Alle Zeilen durchlaufen und Sobel-Filter anwenden
for (unsigned int r = 0; r < (yende - ystart) / ROW_INTERVALL; r++)
{
	// Alle Pixel der Zeile im ROI abarbeiten
	for (unsigned int x = xstart + 1; x < xende - 1; x++)
	{
		float sumX = 0; // Sobelwert in X-Richtung
		float sumY = 0; // Sobelwert in Y-Richtung

		// Doppelte For-Schleife für die Faltung des Sobel-Kerns über die benachbarten Pixel
		for(int hw = -1; hw < 2; hw++)
		{
			for(int wi = -1; wi < 2; wi++)
			{
				sumX += gx[hw+1][wi+1] * (int)p_gray_src_img.mp_buffer[(r*ROW_INTERVALL + ystart + hw) * p_gray_src_img.m_pitch + (x * 4 + wi) + 3];
				sumY += gy[hw+1][wi+1] * (int)p_gray_src_img.mp_buffer[(r*ROW_INTERVALL + ystart + hw) * p_gray_src_img.m_pitch + (x * 4 + wi) + 3];
			}
		}

		// Zusammensetzen und Gradientwer errechnen + Fehlerkorrektur bei über-/unterschreitung eines usigned char Wertes
		grad = sqrt( sumX * sumX + sumY * sumY);
		if(grad > 255.0f) grad = 255.0f;
		if(grad < 0.0f) grad = 0.0f;

		// Aktuellen Gradientenwert in Pufferspeicher einfügen
		gradient[r * (xende - xstart) + (x - xstart)] = (unsigned char)grad;

		if (DRAW_GRADIENT) // In die Bilddaten einzeichnen falls Flag gesetzt ist
		{
			p_gray_out_img.mp_buffer[(r*ROW_INTERVALL + ystart) * p_gray_out_img.m_pitch + (x * 4) + 0] = (unsigned char)grad;
			p_gray_out_img.mp_buffer[(r*ROW_INTERVALL + ystart) * p_gray_out_img.m_pitch + (x * 4) + 1] = (unsigned char)grad;
			p_gray_out_img.mp_buffer[(r*ROW_INTERVALL + ystart) * p_gray_out_img.m_pitch + (x * 4) + 2] = (unsigned char)grad;
			p_gray_out_img.mp_buffer[(r*ROW_INTERVALL + ystart) * p_gray_out_img.m_pitch + (x * 4) + 3] = 255;
		}
	}
}

Die Abbildung Bild:1_Gradient.png zeigt die Gradienten-Werte, die zeilenweise in das Originalbild eingezeichnet wurden. Da eine Spur zwei Kanten hat, einmal von Schwarz (Straße ) auf Weiß (Spur) und wieder von Weiß auf Schwarz, sind auch zwei hellere Stellen um die Spur zu erkennen, an denen der Gradienten-Wert hoch ist.

Schwellenwert-Begrenzung

Zur Vereinfachung der Daten, sollen die Gradienten-Werte mit einem einfachen Schwellenwert auf entweder Weiß (255) oder Schwarz (0) gesetzt werden. Die Gradienten-Werte bewegen sich im Bereich von 0 bis 255. Der Schwellenwert kann mit der Konstanten GRADIENT_THRESHOLD definiert werden. Der Wert wurde auf 120 festgelegt. Der folgende Code zeigt die Schwellenwert-Begrenzung und in Abbildung Bild:2_Schwellwert.png ist zu sehen, wie die Gradienten nun zu binären Werten umgewandelt wurden.

// Einfache Schwellenwertbegrenzung -> Schwache Kanten entfernen, alle anderen auf 255 setzen
for (unsigned int r = 0; r < (yende - ystart) / ROW_INTERVALL; r++) // Alle Zeilen durchgehen
{
	for (unsigned int x = xstart + 1; x < xende - 1; x++)
	{
		// Über dem Schwellenwert? -> Gradientenwert = 255; Ansonsten -> Gradientenwert = 0
		if(gradient[r * (xende - xstart) + (x - xstart)] > GRADIENT_THRESHOLD)
		{
			gradient[r * (xende - xstart) + (x - xstart)] = 255;
			if (DRAW_THRESHOLD) // In die Bilddaten einzeichnen falls Flag gesetzt ist
			{
				p_gray_out_img.mp_buffer[(r*ROW_INTERVALL + ystart) * p_gray_out_img.m_pitch + (x * 4) + 0] = 255;
				p_gray_out_img.mp_buffer[(r*ROW_INTERVALL + ystart) * p_gray_out_img.m_pitch + (x * 4) + 1] = 255;
				p_gray_out_img.mp_buffer[(r*ROW_INTERVALL + ystart) * p_gray_out_img.m_pitch + (x * 4) + 2] = 255;
				p_gray_out_img.mp_buffer[(r*ROW_INTERVALL + ystart) * p_gray_out_img.m_pitch + (x * 4) + 3] = 255;
			}
		}
		else
		{
			gradient[r * (xende - xstart) + (x - xstart)] = 0;
			if (DRAW_THRESHOLD) // In die Bilddaten einzeichnen falls Flag gesetzt ist
			{
				p_gray_out_img.mp_buffer[(r*ROW_INTERVALL + ystart) * p_gray_out_img.m_pitch + (x * 4) + 0] = 0;
				p_gray_out_img.mp_buffer[(r*ROW_INTERVALL + ystart) * p_gray_out_img.m_pitch + (x * 4) + 1] = 0;
				p_gray_out_img.mp_buffer[(r*ROW_INTERVALL + ystart) * p_gray_out_img.m_pitch + (x * 4) + 2] = 0;
				p_gray_out_img.mp_buffer[(r*ROW_INTERVALL + ystart) * p_gray_out_img.m_pitch + (x * 4) + 3] = 255;
			}
		}
	}
}

Lücken schließen

Wie bereits in Kapitel "Sobel-Filter und Gradient" erwähnt, erzeugt eine Spur quasi zwei erkannte Kanten. Da man aber nur den Mittelpunkt der Spur benötigt, wird die Lücke zwischen diesen Kanten geschlossen. Es wird dabei so vorgegangen, dass bei einem Wert von 255 (Kante) die Zeile entlanggelaufen wird und sobald sich der Wert des betrachteten Pixels auf 0 (Lücke) ändert, wird ein Zähler hochgezählt, bis wieder ein weißes Pixel in der Zeile erscheint. Ist der Zähler kleiner als der Schwellwert, der in der Konstanten MAX_GAP festgelegt wird, so wird die Lücke geschlossen, also die Pixel von 0 auf 255 gesetzt. Der folgende Code zeigt dieses Vorgehen und Abbildung Bild:3_Luecke.png das jeweilige Resultat.

// Kleine Lücken zwischen Kanten schließen, da eine Spurlinie zwei Kanten erzeugt
for (unsigned int r = 0; r < (yende - ystart) / ROW_INTERVALL; r++) // Alle Zeilen durchgehen
{
	for (unsigned int x = xstart + 1; x < xende - 1; x++)
	{
		// Einer erkannten Kannten entlanglaufen und beenden wenn Kante aufhört
		while(gradient[r * (xende - xstart) + (x - xstart)] == 255 && x < xende - 1)
		{
			x++;
		}
		unsigned int counter = 0;
		// Einer Lücke entlanglaufen und die Größe der Lücke hochzählen bis wieder eine Kante entdeckt wird
		while(gradient[r * (xende - xstart) + (x - xstart)] == 0 && x < xende - 1)
		{
			counter++;
			x++;
		}

		// Wenn die Lücke klein genug ist, dann soll sie geschlossen werden
		if(counter <= MAX_GAP)
		{
			for (unsigned int x2 = x - counter; x2 <= x; x2++)
			{
				gradient[r * (xende - xstart) + (x2 - xstart)] = 255;
				if (DRAW_GAP) // In die Bilddaten einzeichnen falls Flag gesetzt ist
				{
					p_gray_out_img.mp_buffer[(r*ROW_INTERVALL + ystart) * p_gray_out_img.m_pitch + (x2 * 4) + 0] = 255;
					p_gray_out_img.mp_buffer[(r*ROW_INTERVALL + ystart) * p_gray_out_img.m_pitch + (x2 * 4) + 1] = 255;
					p_gray_out_img.mp_buffer[(r*ROW_INTERVALL + ystart) * p_gray_out_img.m_pitch + (x2 * 4) + 2] = 255;
					p_gray_out_img.mp_buffer[(r*ROW_INTERVALL + ystart) * p_gray_out_img.m_pitch + (x2 * 4) + 3] = 255;
				}
			}
		}
	}
}

Kanten extrahieren

Die Spuren haben nun nicht mehr zwei erkannte Kanten, sondern eine Lange Weiße Kante. Um nun den Mittelpunkt der Spur zu detektieren, werden die langen weißen Striche zu einem Mittelpunkt zusammengefügt. Dabei werden auch falsche Kanten im Hintergrund oder bei Lichtreflexionen einbezogen. Damit die falschen Kanten nicht zu einem Mittelpunkt zusammen geführt werden und damit für Spurkanten gehalten werden, wird die Länge der Kante mit dem Schwellenwert MAX_EDGE_LENGTH verglichen. Ist die Kante zu lang, dann wird die nicht zu einem Mittelpunkt zusammengeführt und nicht als potentielle Spurkante in Betracht gezogen. Die Mittelpunkte werden in der Variable edgeCoord abgespeichert und im späteren Verlauf sollen diese Punkte zu einer Spur zusammen geführt werden. Der folgende Code zeigt das Anlegen der Arrays für die Kanten. Die Größe des Arrays ist durch die Konstanten EC_ROWS und EC_COLS bestimmt. Es werden erstmal alle Werte auf "nicht gesetzt" (is_set = false) eingestellt und dann, nur wenn eine Kante eingefügt wird, wird dieses Flag auf true gesetzt. Die connected Variable wird im späteren Verlauf für die Spurerkennung benötigt und wird ebenfalls standardmäßig auf false gesetzt. Weiterhin zeigt der Code das Zusammenfügen einer langen Kante zu einem Mittelpunkt, solange die Kante nicht zu lang ist.

// Kanten in einem Array abspeichern
coord_T edgeCoord[EC_ROWS][EC_COLS]; // max Anzahl der Kanten pro Zeile

for (int i = 0; i < EC_COLS; i++) // Alle Kanten einer Zeile durchgehen
{
	for (int j = 0; j < EC_ROWS; j++)
	{
		edgeCoord[j][i].is_set = false; // Alle erstmal als false setzen
		edgeCoord[j][i].connected = false;
	}
}

int edgeCounter = 0; // Laufvariable einer erkannten Kante in einer Zeile

// Lange Kanten zu einem Mittelpunkt zusammenführen
// Sollte die lange Kante zu lang sein, dann ist es wohl keine Spurlinie -> also löschen
for (unsigned int r = 0; r < (yende - ystart) / ROW_INTERVALL; r++) // Alle Zeilen durchgehen
{
	edgeCounter = 0;
	for (unsigned int x = xstart + 1; x < xende - 1; x++)
	{
		// Kannte gefunden?
		if (gradient[r * (xende - xstart) + (x - xstart)] == 255)
		{
			unsigned int kantenstart = x;
			// Kannte entlanglaufen bis keine Kannte mehr da ist
			while(gradient[r * (xende - xstart) + (x - xstart)] == 255 && x < xende - 1)
			{
				x++;
			}
			// Die lange Kannte löschen
			for (unsigned int x2 = kantenstart; x2 <= x; x2++)
			{
				gradient[r * (xende - xstart) + (x2 - xstart)] = 0;
			}

			// Mittelpunkt als Kante hinzufügen, falls die Kante nicht zu lang ist
			if ( x - kantenstart <= MAX_EDGE_LENGTH)
			{
				gradient[r * (xende - xstart) + (((unsigned int)((x - kantenstart)/2) + kantenstart) - xstart)] = 255;

				// vllt durch dyn Speicher verbessern
				edgeCoord[r][edgeCounter].x = ((unsigned int)((x - kantenstart)/2) + kantenstart);
				edgeCoord[r][edgeCounter].y = unsigned int(ystart + ROW_INTERVALL * r);
				edgeCoord[r][edgeCounter].is_set = true;
				edgeCounter++;

				// Die Differenz zwischen Start- und Endpunkt errechnen und da eine Kante einzeichnen
				if (DRAW_EDGE) // In die Bilddaten einzeichnen falls Flag gesetzt ist
				{
					DrawRect(&p_gray_out_img, r*ROW_INTERVALL + ystart - 1, ((unsigned int)((x - kantenstart)/2) + kantenstart) - 1, r*ROW_INTERVALL + ystart + 1, ((unsigned int)((x - kantenstart)/2) + kantenstart) + 1, rot);

				}
			}
		}
	}
}

Die folgende Abbildung Bild:4_Kanten.png zeigt das Ergebnis der Mittelpunkt-Bestimmung und zeigt, dass die Mittelpunkte (rote Quadrate) der Spur gut detektiert wurden. Aber es werden auch im Hintergrund Kanten detektiert, die nicht als Spurkanten gewertet werden dürfen.

Spurerkennung aus den Kanten und Bewertung

In diesem Abschnitt wird beschrieben, wie aus den gewonnenen Mittelpunkten der Spurlinien (unter Berücksichtigung der Störkanten) eine Spur extrahiert wird und nach ihrer Ähnlichkeit zu einer realen Spur bewertet wird. Es folgt daher erst die Erkennung sämtlicher Spuren, die als Fahrbahnmarkierung in Frage kommen und anschließend wird der Bewertungsalgorithmus erläutert.

Extraktion der Spurlinien aus den gewonnenen Kanten

Neben den Mittelpunkten der Spurlinien werden auch Kanten im Hintergrund erkannt, die nicht als mögliche Spur in Betracht gezogen werden dürfen (vgl. Abb. Bild:4_Kanten.png). Daher muss ein Algorithmus die Kanten des Spurmittelpunktes von den anderen unterscheiden. Der Ansatz ist recht trivial und kann kurz zusammengefasst werden:

Suche im unteren Bereich (Nur bis zu der Zeile MAX_ROW_SEARCH, da im oberen Bereich keine Spuren beginnen) des Bildes nach einer Kante und verfolge diese das Bild aufwärts. Markiere jeweils eine Kante in der nächst höheren Zeile als dazugehörige Spurkante, falls diese nicht zu weit entfernt ist oder der Winkel zu ihr zu groß ist. Ist in der darüber liegenden Zeile keine passende Kante, so gehe weitere Zeilen hoch, bis der Abstand zu groß wird. Wiederhole dies und beachte nur noch die Kanten, die noch nicht markiert wurden.

PAP Spurerkennung

Im Programmablaufplan ist der Algorithmus nochmal veranschaulicht.

Der Gedanke dahinter entstand durch die Annahme, dass eine Spurlinie keinen plötzlichen 90 ° Knick hat, sondern eine kontinuierliche Kurve aufweist oder lediglich eine Gerade ist. Verfolgt der Algorithmus also eine Spur, dann vergleicht er die Differenz zwischen dem Winkel der letzten beiden Kanten und den aktuellen Kanten mit dem Schwellwert ANGLE_THRESHOLD, der mit 30 ° festgelegt wurde. Ist der Winkel größer als der Schwellwert, so wird die Kante ignoriert.

Für die maximale Distanz zwischen zwei Kanten ist ebenfalls ein Schwellwert (MAX_EDGE_DIST) definiert. Die Distanz ist die euklidische Entfernung zweier Kanten und wird mit dem Satz des Pythagoras ermittelt. Der minimale Schwellwert darf nicht kleiner als der abgetastete Zeilenabstand (ROW_INTERVALL) sein und sollte auch etwas größer gewählt werden, da der gleiche Wert beider Konstanten nur Kanten, die vertikal zueinander lägen, einbeziehen würde. Dies ist schon bei einer Geraden sehr unwahrscheinlich und wird bei einer Kurve keine Spur erkennen lassen. Der Wert von MAX_EDGE_DIST wird auf 30.0\footnote{Datentyp float, weil der Satz des Pythagoras einen reellen Wert liefert} festgelegt. Für die Spuren wurde der Datentyp lane_T erstellt, der in einem Array alle Koordinaten der Kanten beinhaltet und die Anzahl der beinhalteten Kanten. Des Weiteren ist auch das Rating im Datentyp implementiert.

Bewertung der Spurlinien

Wenn alle Kanten des Bildes untersucht und daraus Spuren erzeugt wurden, müssen diese nun bewertet werden. Die Bewertung der Spuren ist insofern notwendig, da auch falsche Spuren erkannt werden können, die sich außerhalb der Fahrbahn befinden. Der Hauptindikator für die Bewertung ist die Anzahl der Kanten, die eine Spur beinhaltet. Kommt es außerhalb der Fahrbahn zu falschen Spuren, ist die Wahrscheinlichkeit, dass diese Spur viele Kantenpunkte beinhaltet, gering, da der Algorithmus für die Spurerkennung dafür sorgt, dass nur Kanten hinzugefügt werden, die zu einer Spur-ähnlichen Kontur führen. Die Spur der Mittellinie wird ebenfalls wenig Kantenpunkte beinhalten, da ihre Lücken nicht als Spur erkannt werden können.

Die Spurlinie mit der besten Bewertung wird dann herausgesucht und entschieden, ob es die linke oder die rechte Spurbegrenzung ist. Da sich das Fahrzeug auf der rechten Spur befindet, wird eine Spurlinie, die ihren Ursprung (Damit ist der unterste Kantenpunkt gemeint) im linken Drittel hat, als linke Spurbegrenzung angenommen. Befindet sich der Ursprung in den anderen zwei Drittel wird die Spur als rechte Spurbegrenzung angenommen. Der Grund dafür, dass nur eine Spur für die Spurführung gewählt wird, liegt daran, dass man die anderen Spuren durch Parallel-Transformation erzeugen kann, da die Spuren parallel zueinander liegen.

Das Ergebnis des Algorithmus aus Abschnitt "Extraktion der Spurlinien aus den gewonnenen Kanten" kann in der Abb. Bild:5_Spuren.png gesehen werden. In diesem Beispiel wurden drei Spuren erkannt und ihre Bewertung mit einer Farbe (grün = gut; braun = schlecht) zur Visualisierung dargestellt. Hier ist zu erkennen, dass die Mittelspur eine schlechtere Bewertung erhält, da sie wegen der Lücken weniger Kanten enthält.

Der vollständige Algorithmus für die Spurführung und die Bewertung ist im Folgenden aufgezeigt:

// Variable für Spuren initialisieren
lane_T lanes[LANE_COUNT];
for (int i = 0; i < LANE_COUNT; i++)
{
 	lanes[i].rating = 0; // Schlechtestes Rating als Standard-Wert 
	lanes[i].coord = new pos_T[int((yende - ystart) / ROW_INTERVALL)];
}

int lane_index = 0;		// Index der Spuren im Array
int first_rating_id = -1;	// Der Index der besten Spur
int second_rating_id = -1;	// Der Index der zweitbesten Spur
int best_rating = 0;		// Der Wert des besten Ratings

// Spuren aus den Kanten extrahieren -> Kanten von unten nach oben durchgehen und die nahe Kanten mit ähnlichem Vorwinkel verbinden
for (unsigned int start_zeile = EC_ROWS; start_zeile > (yende - ystart) / ROW_INTERVALL - MAX_ROW_SEARCH; start_zeile--)
{
 	for (int start_spalte = 0; start_spalte < EC_COLS; start_spalte++) // Alle Kanten einer Zeile durchgehen, von unten nach oben
 	{
		if (edgeCoord[start_zeile][start_spalte].is_set == true && edgeCoord[start_zeile][start_spalte].connected == false) 
		{ 
			edgeCoord[start_zeile][start_spalte].connected = true; // Kante deaktivieren, damit sie nicht nochmal als Spur erkannt werden kann
			int i = 0;
			lanes[lane_index].coord[i].x = edgeCoord[start_zeile][start_spalte].x;
			lanes[lane_index].coord[i].y = edgeCoord[start_zeile][start_spalte].y;


			// Den Spuren eine ID zuordnen -> linke Spur = 0; rechte Spur = 1
			if (lanes[lane_index].coord[i].x> (2.0 / 5.0 * (xende - xstart)))
				lanes[lane_index].id = 1;
			else
				lanes[lane_index].id = 0;

			i++; // nachste Koordinate

			float newAngle, oldAngle = -1;

			for (int zeile = start_zeile - 1; zeile >= 0; zeile--) // Den nächst gelegen Punkt suchen
			{
				long xDist; // hoher unwahrscheinlicher wert
				long yDist; // hoher unwahrscheinlicher wert
				float minDistance = 1000; // hoher unwahrscheinlicher wert
				float minValue = 1000;
				int minID = -1;

				for (int spalte = 0; spalte < EC_COLS; spalte++)
				{
					if(edgeCoord[zeile][spalte].is_set == false) // Abbrechen falls die nachfolgenden Arraywerte keine Kanten sind
					{
						break;
					}
					if(edgeCoord[zeile][spalte].connected == true) // Abbrechen falls die nachfolgenden Arraywerte keine Kanten sind
					{
						continue;
					}
					
					// Entfernung und Winkel zwischen aktueller und vorheriger Kante berechnen
					xDist = abs(long(edgeCoord[zeile][spalte].x - lanes[lane_index].coord[i-1].x));
					yDist = abs(long(edgeCoord[zeile][spalte].y - lanes[lane_index].coord[i-1].y));

					// Winkel angleichen
					if ( edgeCoord[zeile][spalte].x > lanes[lane_index].coord[i-1].x )
					{
						newAngle = 180.0f - (180.0f/PI) * atan((float)yDist / (float)xDist);
					}
					else
					{
						newAngle = (180.0f/PI) * atan((float)yDist / (float)xDist);
					}

					float Distance = sqrt(pow(float(xDist), 2) + pow(float(yDist), 2));
					float Angle_diff = abs(newAngle - oldAngle);

					// Passt die untersuchte Kante besser als die vorherige? Winkel und Abstand vergleichen.
					if ( Distance < minDistance )
					{
						if ( i == 1 || (Angle_diff < ANGLE_THRESHOLD || (Angle_diff >= ANGLE_THRESHOLD && Distance < ROW_INTERVALL * 1.5)) )
						{
							minID = spalte;
							minDistance = sqrt(pow(float(xDist), 2) + pow(float(yDist), 2));
						}
					}
				}

				if(minID != -1 && minDistance < MAX_EDGE_DIST) // Den nächsten Punkt gefunden
				{
					edgeCoord[zeile][minID].connected = true; // Kante deaktivieren, damit sie nicht nochmal als Spur erkannt werden kann

					lanes[lane_index].coord[i].x =  edgeCoord[zeile][minID].x;
					lanes[lane_index].coord[i].y =  edgeCoord[zeile][minID].y;
					xDist = abs(long(lanes[lane_index].coord[i].x - lanes[lane_index].coord[i-1].x));
					yDist = abs(long(lanes[lane_index].coord[i].y - lanes[lane_index].coord[i-1].y));

					// Winkel angleichen
					if ( lanes[lane_index].coord[i].x > lanes[lane_index].coord[i-1].x )
					{
						oldAngle = 180.0f - (180.0f/PI) * atan((float)yDist / (float)xDist);
					}
					else
					{
						oldAngle = (180.0f/PI) * atan((float)yDist / (float)xDist);
					}

					//DrawLine(&p_gray_out_img, lanes.coord[i].x, lanes.coord[i].y, lanes.coord[i-1].x, lanes.coord[i-1].y, rot);
					i++;
				}
			}

			// Wenn Rating der Spur gut ist, dann keine weitere Spur suchen
			lanes[lane_index].coord_count = i;
			lanes[lane_index].rating = int(((float)i / ((float)(yende - ystart) / (float)ROW_INTERVALL - 1)) * 100);

			// Beste Ergebnis suchen und index der Spur speichern
			if ( lane_index > 0 && lanes[lane_index].rating > best_rating )
			{
				second_rating_id = first_rating_id;
				first_rating_id = lane_index;
				best_rating = lanes[lane_index].rating;
			}

			// Index der Spur hochzählen
			if(lane_index < LANE_COUNT - 1)
			{
				lane_index++;
			}
		}
	}
}