Kantenerkennung

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 \verb|xstart|, \verb|xende|, \verb|ystart| und \verb|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 \verb|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}\label{subsec:sobelGradient

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 \ref{fig:1_Gradient} 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. \begin{figure}[h] \centering \includegraphics[width=1.0\textwidth]{Bilder/OSE_Bilder/Spurerkennung/1_Gradient.png} \caption{Gradienten Zeilenweise im Originalbild} \label{fig:1_Gradient} \end{figure}

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 \verb|GRADIENT_THRESHOLD| definiert werden. Der Wert wurde auf 120 festgelegt. Der folgende Code zeigt die Schwellenwert-Begrenzung und in Abbildung \ref{fig:2_Schwellwert} 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; } } } }

\begin{figure}[h] \centering \includegraphics[width=1.0\textwidth]{Bilder/OSE_Bilder/Spurerkennung/2_Schwellwert.png} \caption{Schwellenwert-Begrenzung auf Gradienten-Werte} \label{fig:2_Schwellwert} \end{figure}

Lücken schließen

Wie bereits in Kapitel \ref{subsec:sobelGradient} 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 \verb|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 \ref{fig:3_Luecke} 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; } } } } }

\begin{figure}[h] \centering \includegraphics[width=1.0\textwidth]{Bilder/OSE_Bilder/Spurerkennung/3_Luecke.png} \caption{Lücke zwischen Kanten schließen} \label{fig:3_Luecke} \end{figure}

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 \verb|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 \verb|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 \verb|EC_ROWS| und \verb|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 \verb|true| gesetzt. Die \verb|connected| Variable wird im späteren Verlauf für die Spurerkennung benötigt und wird ebenfalls standardmäßig auf \verb|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 \ref{fig:4_Kanten} 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.

\begin{figure}[h] \centering \includegraphics[width=1.0\textwidth]{Bilder/OSE_Bilder/Spurerkennung/4_Kanten.png} \caption{Mittelpunkt der Spur erkannt und andere Störkanten} \label{fig:4_Kanten} \end{figure}