Parametrische Segmentbeschreibung und Tracking zur Spurerkennung in Straßenszenen

Inhaltsverzeichnis

1. AUFGABENSTELLUNG

2. EINFÜHRUNG

3. GRUNDLAGEN
3.1 SEGMENTIERUNG
3.1.1 sequentielles Regionenwachstumsverfahren
3.1.2 quasi-paralleles Regionenwachstumsverfahren
3.1.3 paralleles Regionenwachstumsverfahren
3.1.4 Kantenrelaxation
3.1.5 Segmentierung nach Kontur / Konturverfolgung
3.2. INVARIANTEN
3.2.1 Momente
3.2.1.1 Konturmerkmale
3.2.1.2 Formmerkmale
3.2.2 Fourierdeskriptoren
3.3 TRANSFORMATION BILDKOORDINATEN IN WELTKOORDINATEN
3.4 FILTERUNG
3.4.1 Laplace-Filterung
3.4.2 Median-Filter
3.5 ENTWICKLUNGSUMGEBUNG
3.5.1 Hardware
3.5.1.1 Kamera
3.5.2 Software
3.5.3 Grundvoraussetzungen

4. VERFAHREN ZUR STRAßENRANDERKENNUNG
4.1 SEGMENTIERUNG NACH FLÄCHENINHALT (REGION GROWING)
4.1.1 Ausgangsregionen erstellen
4.1.2 Regionen vereinigen
4.1.3 Programmablauf (schematisch)
4.1.4 Ergebnis
4.1.5 Kantenrelaxation
4.2 SEGMENTIERUNG NACH KONTUR
4.2.1 Startpunktsuche
4.2.2 Konturverfolgung
4.2.3 Bildverbesserung durch Grauwertmanipulation
4.2.4 adaptive Bestimmung der Schwellwerte
4.2.5 Programmablauf (schematisch)
4.2.6 Ergebnis
4.3 AUSWERTUNG UND VERGLEICH DER BEIDEN SEGMENTIERUNGS-VERFAHREN
4.4 SEGMENTERKENNUNG
4.4.1 Flächenkriterium
4.4.2 Formkriterium
4.4.3 Fourierdeskriptoren
4.4.4 Konturglättung
4.4.5 Auswertung
4.4.6 Ergebnis der Segmenterkennung
4.5 GRUPPENBILDUNG
4.5.1 Gruppierung im Bildkoordinatensystem
4.5.2 Gruppierung im Weltkoordinatensystem
4.5.3 Auswertung und Ergebnis der Gruppierung

5. ERGEBNIS

6. ZUSAMMENFASSUNG UND AUSBLICK
6.1 ZUSAMMENFASSUNG
6.2 AUSBLICK

7. LITERATURVERZEICHNIS

A ANHANG

A.1 BEDIENUNG DER SOFTWARE

A.2 ABBILDUNGSVERZEICHNIS

1. Aufgabenstellung

Die Straßenranderkennung soll auf der Grundlage der Segmentierung des Bildes erfolgen. Dazu ist das quasi-parallele Wachstumsverfahren aus der Literatur aufzuarbeiten und an die Erfordernisse der Spurerkennung anzupassen. Die zeitliche Verfolgung von Segmenten erfordert neben den Positions- und Lageparametern auch die Nutzung zusätzlicher Formmerkmale. Dafür soll in der Arbeit die Nutzung der Momente und Fourierdeskriptoren als geometrische Invarianten erarbeitet werden und diese Beschreibung für die Spurerkennung verwendet werden.

2. Einführung

Es existieren bereits zahlreiche Lösungen und Lösungsvorschläge zur Straßenranderkennung in Grauwertbildern, so ist z.B. in [RIC95] ein adaptierendes Modell zur Analyse von Straßenszenen beschrieben. In [LAI93] wird ein autonomes Fahrzeug beschrieben, welches automatisch einer Maschine zum Aufmalen der Markierungen auf die Straße folgt. Allerdings läßt sich dieser Ansatz mit den günstigen Randbedingungen dieses Verfahrens (geringe Geschwindigkeit und guter Kontrast der frisch aufgezeichneten Markierungen) schlecht auf komplexere Problemstellungen erweitern.

In dieser Arbeit soll zur Straßenranderkennung zunächst ein Segmentierungsverfahren eingesetzt werden. Dabei wird insbesondere das in [MES89] beschriebene Verfahren des quasi-parallelen Regionenwachstums, als ein vollständiges Segmentierungsverfahren, mit einem in [ZAM95] beschriebenen Verfahren, welches nur ausgewählte Objekte segmentiert, verglichen. Zur Verbesserung des zweiten Verfahrens werden dabei 2 Lösungsvorschläge angegeben und untersucht.

Der zweite entscheidende Teil der Arbeit besteht in der Erkennung, der durch die Segmentierung gefundenen Segmente. Als Besonderheit dieser Arbeit wird dabei eine Kombination von Momenten und Fourierdeskriptoren, als Invarianten der segmentierten Objekte, zur Erkennung eingesetzt. Dadurch wird man in die Lage versetzt eine Aussage zu treffen, ob es sich bei den gefundenen Objekten tatsächlich um Fahrbahnmarkierungen (Straßenränder) handelt.

Eine abschließende Gruppierung der ausgewählten Segmente bezüglich ihrer Lage zu einander ermöglicht es dann, die einzelnen Segmente jeweils einer bestimmten Fahrspurmarkierung zu zuordnen. Dafür wurde das in [RIC95] beschriebene Verfahren angewendet und um die Gruppierung in Weltkoordinaten erweitert. Durch eine Transformation der im Bild gefundenen Segmente in das Weltkoordinatensystem kann, man noch zusätzlich in der Welt unrealistische Segmente herausfiltern, welche im Bild sonst schwer zu erkennen sind.

3. Grundlagen

3.1 Segmentierung

Die Aufgabe der Segmentierung von Bildern ist es, das Bild in Bereiche gleicher bzw. ähnlicher Eigenschaften zu unterteilen. Dabei kann dann oft davon ausgegangen werden, daß die zu einem Bereich zusammengefaßten Gebiete auch zu ein und dem selben Objekt gehören. Im Idealfall wird ein Objekt mit homogenen Eigenschaften auch nur als ein Gebiet segmentiert.

Dabei wird klassisch in 3 Verfahrensansätze unterschieden:

- Ausgehend von kleinsten atomaren Regionen werden diese mit anderen zu größeren Regionen zusammengefaßt (Regionenwachstum bzw. region growing).

- Ein Regionenteilungsverfahren bzw. region splitting stellt das Gegenstück dazu dar. Hierbei werden grobe Regionen oder das ganze Bild (als eine Region) in kleinere Regionen zerteilt. Dieses Verfahren wird jedoch praktisch laut [MES89] nicht angewendet. Zumindest konnte in der Literatur keine Anwendung dieses Verfahrens gefunden werden.

- Eine Mischung aus den ersten beiden Verfahren ist das „split-and-merge“-Verfahren. Hier werden Regionen sowohl geteilt als auch verschmolzen. Dabei wird das Bild zunächst in gleich große Blöcke unterteilt. Erfüllt ein Block ein gefordertes Homogenitätskriterium nicht, wird er weiter zerteilt (split-Operation). Ist ein Block einem benachbarten Block ähnlich wird er mit diesem verschmolzen (merge- Operation). Der entscheidende Nachteil dieses Verfahrens liegt jedoch darin, daß auf Grund dieser Vorgehensweise zwischen den Regionen fast immer grobe „treppenförmige“ Grenzen entstehen. Die Ursache hierfür ist, daß die Regionengrenzen nicht einer Kante sondern fest vorgegebenen Linien folgen. Im Folgenden sollen nun in Anlehnung an [MES89] 3 unterschiedliche Segmentierungsalgorithmen, basierend auf dem Wachstumsverfahren, näher betrachtet werden. Außerdem soll als viertes noch eine vollkommen andere Möglichkeit vorgestellt werden, welche nur bestimmte Elemente „heraussegmentiert“:

3.1.1 sequentielles Regionenwachstumsverfahren

Die einfachste Möglichkeit ist es sequentiell alle Regionen der Reihe nach mit ihren Nachbarregionen zu vereinigen. Bei diesem sequentiellen Verfahren läßt man eine Region mit ihrer Nachbarregion verschmelzen (wachsen), d.h. es werden immer mehr Pixel zu der Region hinzu genommen, bis ein vorgegebenen Differenzwert (Homogenitätskriterium) nicht mehr eingehalten wird. Dann wird mit der nächsten Region genauso verfahren. Dadurch kann es aber vorkommen, daß schon Regionen verschmolzen werden, welche besser mit einer anderen (nächsten) Region hätten verschmolzen werden können (Schwelle für Homogenitätskriterium zu hoch). Wählt man hingegen die Schwelle zu niedrig, kann es passieren, daß manche Bildpunkte gar nicht verschmolzen werden.

3.1.2 quasi-paralleles Regionenwachstumsverfahren

Für dieses in [MES89] beschriebene Verfahren wird zur Beurteilung der Ähnlichkeit zweier Regionen ein sog. Likelihood Ratio Test oder Hypothesentest herangezogen: Dabei bestehen zwei benachbarte Regionen RA und RB aus NA bzw. NB Bildpunkten. Die einzelnen Merkmalswerte (Grauwerte) der Regionen werden zu einem Datenvektor [Abbildung in dieser Leseprobe nicht enthalten] bzw. [Abbildung in dieser Leseprobe nicht enthalten] mit NA bzw. NB Komponenten zusammengefaßt. Die Merkmalswerte der beiden Regionen werden dabei als Zufallsprozesse betrachtet, deren Verteilungsdichtefunktion ( [Abbildung in dieser Leseprobe nicht enthalten] ) bzw. ( [Abbildung in dieser Leseprobe nicht enthalten]) ist.

Hierfür werden die folgenden beiden Hypothesen aufgestellt und verglichen:

- Nullhypothese H0: beide Regionen entstammen ein und dem selben Prozeß
- Gegenhypothese H1: beide Regionen entstammen unterschiedlichen Prozessen

Um eine Entscheidung für eine der beiden Hypothesen treffen zu können, ist es, wie in der Entscheidungstheorie üblich, erforderlich folgende Entscheidungsregel aufzustellen:

Abbildung in dieser Leseprobe nicht enthalten

Somit wird bei Überschreiten bzw. Unterschreiten der Schwelle C entweder die eine oder die andere Hypothese angenommen. Durch C wird ebenfalls festgelegt, wie hoch der mögliche Fehler bei der Entscheidung für die jeweilige Hypothese werden kann. Die Randverteilungsdichte einer beliebigen Komponente yi des Datenvektors[Abbildung in dieser Leseprobe nicht enthalten]

Abbildung in dieser Leseprobe nicht enthalten

Die multidimensionale Verteilungsdichte (Verbundverteilungsdichte) des gesamten Datenvektors lautet bei einem gegebenen Wert von my und σ

Abbildung in dieser Leseprobe nicht enthalten

Setzt man für die unbekannten Parameter my und σ Schätzungen für Mittelwert und Varianz ein:

Abbildung in dieser Leseprobe nicht enthalten

So ergibt sich:

Abbildung in dieser Leseprobe nicht enthalten

Somit lauten die Likelihood-Funktionen für die beiden Hypothesen wie folgt:

- H0:

Abbildung in dieser Leseprobe nicht enthalten

- H1:

Abbildung in dieser Leseprobe nicht enthalten

Das verallgemeinerte Likelihood-Verhältnis λ, für diese beiden Hypothesen lautet dann

wie folgt:

Abbildung in dieser Leseprobe nicht enthalten

Gleichung 3.1: Hypothesentest

Zum Verfahren:

Zu Beginn dieses Verfahrens sollte zunächst eine Sequenz von ansteigenden Grauwertdifferenzschwellen tmax1 ... tmaxn festgelegt werden. Begonnen wird mit tmax1, was durchaus 0 gewählt werden kann, um zunächst alle benachbarten Pixel des gleichen Grauwertes zu verschmelzen. tmaxn entspricht der maximalen im Bild auftretenden Grauwertdifferenz an den Regionengrenzen. Es können dann noch beliebige Zwischenwerte eingeführt werden. Allerdings sollten es nicht allzu viele werden um die Bearbeitungszeit in einem erträglichen Rahmen zu halten.

Nun werden die (Grauwert-) Differenzen benachbarter Bildpunkte (bzw. Regionenkanten) bestimmt und falls diese kleiner als tmax ist, wird die Distanz (verallgemeinertes Likelihood-Verhältnis / Hypothesentest - Gleichung 3.1) der beiden Regionen berechnet. Falls diese wiederum kleiner als dmax ist, wird das Regionenpaar in einer Liste (Punkte und Distanz) abgespeichert. Die Liste enthält dann eine Menge von Hypothesen welche Regionen verschmolzen werden können. Anschließend wird die Liste von kleinen nach großen Distanzwerten sortiert.

Die Liste wird nun sequentiell, mit der kleinsten Distanz beginnend, abgearbeitet. Somit werden zuerst die Regionen mit der geringsten Distanz verschmolzen und es ist weitestgehend ausgeschlossen, daß Regionen miteinander vereinigt werden, welche besser mit einer anderen Region hätten vereint werden können.

Da sich aber schon mit der Verschmelzung der ersten beiden Regionen, die Parameter für die Region verändert haben, muß dieser Hypothesentest, ob die Regionen noch vereinbar sind, vor jeder Verschmelzung neu durchgeführt werden. Durch die sortierte Abarbeitung der Liste beginnen „quasi-parallel“ im ganzen Bild Regionen zu wachsen.

Danach wird tmax auf den nächsten Wert erhöht und die Prozedur beginnt mit dem Aufstellen der Hypothesen von vorn, bis tmaxn erreicht ist.

Anschließend können die Regionen noch jeweils mit dem Mittelwert ihrer Grauwerte aufgefüllt werden um die Segmentierung zu visualisieren.

Abb. 3.1: Infrarotbild: links: original; rechts: segmentiert (Regionen mit ihrem Mittelwert aufgef ü llt)

Abbildung in dieser Leseprobe nicht enthalten

3.1.3 paralleles Regionenwachstumsverfahren

Im Gegensatz zu dem quasi-parallelen Verfahren lassen sich echte parallele Verfahren jedoch nur auf Mehrprozessor-Systemen durchführen, in dem dort jeder Prozessor einen Teil des Bildes bearbeitet. Dabei kommt es aber dann an den Grenzen der Bildbereiche wieder zu Problemen mit den Regionen die in die Bereiche mehrerer Prozessoren fallen. Dies kompensiert dann vermutlich wieder den Vorteil der durch die Parallelisierung entstanden ist.

3.1.4 Kantenrelaxation

Im Anschluß an eines der vorangegangenen Segmentierungsverfahren kann eine in [MES89] beschriebene Kantenrelaxation noch zur Verbesserung des Ergebnisses führen. Sie ist dabei besonders empfehlenswert, wenn das segmentierte Bild noch Mängel aufweist, wie:

- Fehler an den Rändern der gefundenen Segmente (Fehlzuordnung einzelner
Bildpunkte zur falschen Region)
- Grobe und „ausgefranste“ Regionengrenzen zwischen Regionen, die nicht durch eine genau lokalisierbare Kante von einander getrennt sind (langsame Grauwertübergänge)

Die Grundidee des hier vorgestellten Verfahrens besteht darin, durch Veränderung der Regionengrenzen, die sog. Verbund-Likelihood-Funktion zu erhöhen. Diese Verbund- Likelihood-Funktion besteht dabei einerseits aus der schon im obigen Kapitel vorgestellten Likelihood-Funktion der jeweiligen Regionen und einem zweiten Term, welcher aus einem Regionenformmodell hervorgeht. Dazu wird für das gesamte Bild nacheinander jeder Punkt, der am Rand einer Region liegt, betrachtet. Dabei wird für jeden dieser Randpunkte überprüft, ob durch Zuweisung dieses Punktes zu einer anderen (benachbarten) Region eine Erhöhung der Verbund-Likelihoodfunktion eintritt. Dabei sollen stets nur solche Änderungen durchgeführt werden, welche die Anzahl der Regionen nicht erhöht und nicht die vorausgesetzte Korrektheit der Regionen zerstört. Dies bedeutet, daß die Regionen nur ihre Form verändern und 1-Pixel-Regionen verschwinden können. Besonders ist darauf zu achten, daß Regionen nicht in mehrere Teile zerfallen, wenn ein Bildpunkt an einer ein Pixel breiten Stelle einer anderen Region zugewiesen wird. Dies ist genau dann der Fall, wenn:

1. in der 8er Nachbarschaft des Punktes weitere Punkte das Label dieses Punktes tragen und gleichzeitig
2. ein Umlauf über die 8 Nachbarn des Punktes mehrere nicht zusammenhängende Teilsequenzen mit dem gleichen Label wie der Punkt ergibt.

In diesem Fall darf das Label des Punktes, wie z.B. in Abb. 3.2, nicht verändert werden, d.h. er darf keiner anderen Region zugewiesen werden.

Abbildung in dieser Leseprobe nicht enthalten

Abb. 3.2: Ein Bildpunkt X, dessen Label nicht ge ä ndert werden darf

Ein Bildpunkt kann entweder sein Label behalten oder einer anderen Region zugeordnet werden. Somit kommen immer mindestens 2 Label (inklusive des eigenen) für den Punkt in Frage (da er am Rand der Region liegen muß). Höchstens kommen 5 Label in Frage, da nur die 4er Nachbarn für eine Zuweisung in Frage kommen, da sonst Regionen zerteilt werden können.

Es wird für jede in Frage kommende Nachbarregion der folgende Term bestimmt und der Bildpunkt wird dann der Region zugewiesen, für die dieser Ausdruck maximal wird:

Abbildung in dieser Leseprobe nicht enthalten

L(Ri+) steht für die Likelihoodfunktion der Region Ri bei Hinzunahme des Punktes

L(Ri-) steht für die Likelihoodfunktion der Region Ri ohne den betreffenden Punkt

nB, nC, nD und nE sind die Cliquenzahlen der Cliquen an denen der Punkt beteiligt ist

Die Parameter B und D bestimmen die Eigenschaften und den Einfluß, gegenüber der Likelihoodfunktion, des Regionenformmodells. Experimentell läßt sich ermitteln, daß man bei einem Wertebereich für B von ca. -0,25 bis -3 einen guten Kompromiß zwischen Glättungsfähigkeit und Formtreue erhält. D sollte dafür in etwa halb so groß wie B gewählt werden. Nähere Informationen zu Regionenformmodellen findet man unter anderem in [MES89].

Bestimmung der Likelihoodfunktionen:

Wie schon in „3.1.2 quasi-paralleles Regionenwachstumsverfahren“ beschrieben, bestimmt sich die Maximum-Likelihoodfunktion wie folgt:

Abbildung in dieser Leseprobe nicht enthalten

Der Logarithmus der Funktion beträgt dann:

Abbildung in dieser Leseprobe nicht enthalten

Bezeichnet N die Größe der Region Ri ohne Hinzunahme des betreffenden Punktes, sowie σ- den Schätzwert der Standardabweichung ohne bzw. σ+ mit Hinzunahme des Punktes, so berechnen sich die Likelihoodfunktionen L+ mit Hinzunahme des Punktes und L- ohne Hinzunahme des Punktes wie folgt:

Abbildung in dieser Leseprobe nicht enthalten

Daraus ergibt sich:

Abbildung in dieser Leseprobe nicht enthalten

Somit ergibt sich die Gesamtfunktion zu:

Abbildung in dieser Leseprobe nicht enthalten

Gleichung 3.2: Kantenrelaxation

Bestimmung der Cliquenzahlen nB, nC, nD und nE:

Als Cliquen bezeichnen wir hier ausschließlich Wertepaare, welche in unmittelbarer Nachbarschaft zueinander liegen. Es werden hier nur 2er Cliquen betrachtet. Dabei besteht eine 2er Clique immer aus einem Bildpunkt und einem Punkt aus dessen 8er Nachbarschaft. Die zu vergleichenden Werte sind hier die Regionenindizes. Die Cliquen werden dann einfach nach folgendem Schema abgezählt:

- nB ... Anzahl der horizontalen & vertikalen 2er Cliquen mit gleichem Wert
- nC ... Anzahl der horizontalen & vertikalen 2er Cliquen mit unterschiedlichem Wert
- nD ... Anzahl der diagonalen 2er Cliquen mit gleichem Wert
- nE ... Anzahl der diagonalen 2er Cliquen mit unterschiedlichem Wert

Nach Abb. 3.5 aus dem nächsten Kapitel sind dabei die horizontalen & vertikalen Cliquen die Wertepaare des Punktes mit einem Nachbarn mit einem geradzahligen Richtungscode. Die diagonalen Cliquen sind die Paare mit ungeradzahligen Richtungscode.

In folgendem abstrakten Beispiel mit 2 Regionen soll die Wirkungsweise noch einmal verdeutlicht werden:

Abbildung in dieser Leseprobe nicht enthalten

Abb. 3.3: Ergebnis der Segmentierung mit Label der Regionen (Ausschnitt) (Ausgangsbild f ü r Kantenrelaxation)

Betrachten wir nun den mittleren Bildpunkt aus Abb. 3.3 und bestimmen zunächst die Cliquenzahlen:

- Punkt gehört zu Region 1 (Label braucht nicht geändert zu werden):
- nB = 1
- nC = 3
- nD = 2
- nE = 2
- Punkt gehört zu Region 2 (Label muß geändert werden):
- nB = 3
- nC = 1
- nD = 2
- nE = 2

Weiterhin nehmen wir an, daß Region 1 aus 100 Bildpunkten und Region 2 aus 80 Bildpunkten besteht. Die Standardabweichungen der Regionen gehen aus Tabelle 3.1 hervor.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 3.1: Standardabweichungen der Regionen

Somit ergibt sich Gleichung 3.2 für den Fall, daß der Punkt in der Region 1 bleibt:

Abbildung in dieser Leseprobe nicht enthalten

Und für den Fall das er zu Region 2 kommt:

Abbildung in dieser Leseprobe nicht enthalten

Mit B = -2 ergeben sich dann folgende Ergebnisse:

Abbildung in dieser Leseprobe nicht enthalten

Der Punkt sollte also besser der Region 2 zugeordnet werden (größerer Wert).

3.1.5 Segmentierung nach Kontur / Konturverfolgung

Definition: Kontur [ZAM95]: „Die Kontur eines Objektes ist die Menge aller Objektpunkte, die mindestens einen Punkt in der 4er-Nachbarschaft im Hintergrund besitzen. Verfolgt man die Kontur von einem beliebigen Anfangspunkt an bis zum gleichen Punkt zurück, so erhält man eine Folge von Schritten, jeder Schritt in eine aus acht möglichen Richtungen (einen aus 8-benachbarten Punkten bestehenden Pfad). Die Richtungen der Schritte können durch die Zahlen 0 bis 7, z.B. wie in Abb. 3.5 angegeben, dargestellt werden. Somit kann die Kontur eines Objektes bzw. seine Form durch eine Zahlenfolge r1, r2, ...,ri, ..., rN mit 0 ≤ ri ≤ 7, 1 ≤ i ≤ N, fehlerfrei beschrieben werden. Die zusätzliche Angabe der absoluten Koordinaten eines Konturpunktes (z.B. des Anfangspunktes) erlaubt es, auch die Lage des Objektes im Bildraster zu spezifizieren.“

Abbildung in dieser Leseprobe nicht enthalten

Abb. 3.5: Codierung der Schritte in einer 8-Nachbarschaft (Freeman code)

Das Ziel dieses Verfahrens ist es helle Objekte auf dunklem Untergrund zu finden und zu segmentieren. Dabei werden alle hellen Objekte umrandet und deren Kontur abgespeichert. Der übrige dunkle Hintergrund kann dann als ein großes Hintergrundobjekt angesehen werden. Dieses in [ZAM95] beschriebene Verfahren gliedert sich in 2 Teilschritte:

1. Objektfindung (Anfangspunktsuche): In diesem Schritt wird das Bild Pixel für Pixel untersucht, ob der Grauwert eines Pixels einen vorgegebenen Schwellwert überschreitet und zugleich das vorhergehende Pixel einen zweiten Schwellwert unterschreitet. Auf diese Art und Weise wird ein recht zuverlässiger Startpunkt für eine Kontur eines hellen Objektes gefunden.

2. Konturverfolgung: Hier wird dann von diesem Startpunkt ausgehend die Kontur des Objektes verfolgt, d.h. daß jeweils die 8er-Nachbarschaft des Pixels untersucht wird, welcher nächste Bildpunkt zum Rand des Objektes gehört. Diese Verfolgung geht dann von da aus weiter bis der Anfangspunkt der Kontur wieder erreicht ist. Die Erzeugung einer geschlossenen Kontur ist dabei sichergestellt, da auch im Extremfall bei 1 Pixel breiten Konturen auf der Kontur selbst wieder zurück gegangen wird um den Anfangspunkt der Kontur zu erreichen.

Abb. 3.5: gefundene Kontur (wei ß ) eines grauen Objektes auf schwarzem Grund (teilweise 1 Pixel breite Kontur)

Abbildung in dieser Leseprobe nicht enthalten

Anschließend kann dann die gefundene Kontur z.B. in einer Datei im Freeman code zusammen mit ihrem Startpunkt und ggf. der Länge der Kontur abgespeichert werden.

3.2. Invarianten

Für eine Objekterkennung in Bilddaten ist es erforderlich, daß für die zu erkennenden Objekte sog. Invarianten gefunden werden. Diese Invarianten sind Eigenschaften der Objekte, welche in allen möglichen Erscheinungsformen dieser Objekte gleich sind. Dies gilt besonders bezüglich:

- ihrer Lage Æ translationsinvariant
- ihrer Größe Æ skalierungsinvariant
- ihrer Drehung Æ rotationsinvariant
- und der Verschiebung des Startpunktes ihrer Konturbeschreibung Æ startpunktinvariant

Diese Invarianten sollen hier später eingesetzt werden, um eine möglichst sichere Aussage zu treffen, ob ein gefundenes Segment eine Fahrbahnmarkierung ist oder nicht.

Im Folgenden sollen 2 Möglichkeiten gezeigt werden, wie man solche Eigenschaften der Objekte bestimmen kann:

3.2.1 Momente

Zu den wichtigsten Regionenmerkmalen eines Segmentes gehören die statischen Momente. Dabei entspricht das 0-te Moment der Segmentfläche, die beiden ersten Momente den Koordinaten des Segmentschwerpunktes und aus den drei zweiten Momenten lassen sich unter anderem die Orientierung des Segmentes und die Ausdehnung des Segmentes um die Orientierungsachse bestimmen. Die Berechnung der Momente Mpq der Ordnung p+q erfolgt normalerweise unter Verwendung aller Pixel, die zum Segment gehören und läßt sich wie folgt auch in die Summenform übertragen:

Abbildung in dieser Leseprobe nicht enthalten

Dabei bezeichnet g(x, y) den Grauwert des Pixels an der Stelle (x, y). Für Binärbilder gilt, für Pixel die zum Segment gehören: g(x, y) = 1.

Um die Berechnung der Momente bezüglich der Rechenzeit möglichst einfach zu machen, soll diese im Folgenden aus der äußeren Kontur des Segmentes erfolgen. Mögliche Hohlflächen (Löcher) der Segmente werden dabei nicht berücksichtigt. Im Gegensatz zu [RIC95] kann das Flächenintegral der Momente nur über den Gaußschen Integralsatz in ein Kurvenintegral für die äußere Kontur des Segmentes, wie z.B. auch in [VOS95] beschrieben, überführt werden.

Abbildung in dieser Leseprobe nicht enthalten

Der Integrand des Flächenintegrals zur Berechnung der Momente läßt sich für Binärbilder wie folgt angeben:

Abbildung in dieser Leseprobe nicht enthalten

Eine Lösungsmöglichkeit ist durch die Wahl

Abbildung in dieser Leseprobe nicht enthalten

für die Funktionen P und Q gegeben. Somit erhalten wir:

Abbildung in dieser Leseprobe nicht enthalten

Dieses Integral kann man näherungsweise für diskrete Momente zunächst wie folgt ausdrücken:

Abbildung in dieser Leseprobe nicht enthalten

Für die Definition des Momentenintegral als Momentensummation für den Übergang zum Kurvenintegral sollte man allerdings besser die Bildpixel als Zwischenpunkte betrachten. Somit sollte man bei dem Kurvenintegral, wegen der Genauigkeit, in der horizontalen Richtung die Zwischengitterverschiebung berücksichtigen. Wobei das Vorzeichen der Verschiebung extra zu beachten ist. So sieht die Gleichung für das Kurvenintegral entlang der Kontur des Objektes, laut dieser Überlegung, folgendermaßen aus:

Abbildung in dieser Leseprobe nicht enthalten

Der Wert von ∆y legt fest, ob der Wert abgezogen oder dazugezählt wird und hängt davon ab, ob es sich bei dem Konturpunkt um einen Eintrittspunkt (∆y = -1) oder einen Austrittspunkt (∆y = +1) handelt. An den Zwischenpunkten der Kontur findet keine Summation statt (∆y = 0).

Für den Fall, daß ein freistehender Konturpunkt (C) (gleichzeitig Ein- und Austrittspunkt aus der Kontur) vorliegt, ist eine gesonderte Berechnung erforderlich. Die unterschiedlichen Arten von Punkten und deren Werte für ∆y sind in die folgende Beispielkontur der Abb. 3.6 eingetragen.

Abbildung in dieser Leseprobe nicht enthalten

Abb. 3.6: Ein- / Austrittspunkte einer Objektkontur (Werte f ü r ∆ y)

Für die Punkte, welche in der Abb. 3.6 mit C bezeichnet sind, kann man jedoch diese Formel nicht anwenden, weil sie gleichzeitig Ein- und Austrittspunkt sind, aber nur einmal durchlaufen werden („Wendepunkte“ in der Konturbeschreibung). Da diese Punkte aber auch nicht vernachlässigt werden sollen, ist eine gesonderte Berechnung erforderlich. Man kann in diesem Fall davon ausgehen, daß an diesen Stellen Kontur gleich Fläche ist. Deshalb muß man für diese Punkte den Term in der Momentensumme durch den Term aus der ursprünglichen flächenbasierten Momentenformel ersetzen:

Abbildung in dieser Leseprobe nicht enthalten

Somit erhält man abschließend folgende Formel:

Abbildung in dieser Leseprobe nicht enthalten

Gleichung 3.3: konturbezogene Momentenformel

Die in der Abb. 3.6 mit Z bezeichneten Punkte, werden in der Konturbeschreibung zweimal durchlaufen. Sie werden dabei einmal als Eintrittspunkt und das andere Mal als Austrittspunkt betrachtet. Daher ist keine gesonderte Behandlung solcher Punkte nötig.

Welche Art von Konturpunkt gerade vorliegt, läßt sich aus dem Konturcode nach Abb.

4.6 ableiten und ist in Tabelle 3.3 zusammengestellt. Dabei ist ri der Wert des Konturcodes der von dem Punkt wegführt und ri-1 ist der Wert der zu dem Punkt hinführt.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 3.3: Bestimmung von ∆ y anhand der Art des Konturpunktes (Ein- / Austrittspunkt) [VOS95]

Für den ersten Konturpunkt ergibt sich ri-1 aus der Richtung welche vom Endpunkt zum Anfangspunkt der Kontur führt. Genauso verhält es sich am Endpunkt der Kontur mit ri. Diese Richtung ist in der Regel in der Konturbeschreibung nicht enthalten und muß erst berechnet werden.

3.2.1.1 Konturmerkmale

Konturlänge:

Die Länge L der Kontur ist hier a priori bekannt, da diese zusammen mit der Konturinformation bei der Segmentierung abgespeichert wird.

Fläche:

Wie schon eingangs erwähnt, entspricht die Fläche des Segmentes dessen 0-ten Moment und berechnet sich somit wie folgt:

Abbildung in dieser Leseprobe nicht enthalten

Eine weitere schnelle und einfache Methode (ohne Verwendung der Momente), welche die Fläche direkt aus dem Konturcode (s. Abb. 3.5) berechnet, ohne alle Pixel des Segmentes aufsummieren zu müssen, wird in [JÄH02] beschrieben. Dieser Algorithmus arbeitet dabei ähnlich einer numerischen Integration. Wir stellen uns eine horizontale Basislinie in einer beliebigen vertikalen Position im Bild vor. Dann beginnen wir die Integration der Fläche am obersten Pixel des Objektes. Die Entfernung dieses Punktes zur Basislinie bezeichnen wir mit B. Zu Beginn wird die Fläche eins gesetzt. Dann folgen wir dem Objektrand und erhöhen die Fläche des Objektes entsprechend den Angaben in Tabelle 3.5.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 3.5: Berechnung der Fl ä che eines Objektes aus dem Konturcode

Bewegen wir uns beispielsweise nach rechts (Code 0) nimmt die Fläche um B zu. Bewegen wir uns nach oben rechts (Code 1), nimmt die Fläche ebenfalls um B zu, aber B muß auch um 1 erhöht werden, weil sich die Entfernung zwischen dem Randpixel und der Basislinie erhöht hat. Bei allen Bewegungen nach links wird die Fläche um B - 1 verringert. Auf diese Weise subtrahieren wir die Fläche zwischen dem unteren Rand des Objektes und der Basislinie, welche zunächst bei der Flächenberechnung während der Bewegung nach rechts fälschlicherweise addiert wurde.

Diese Methode arbeitet allerdings nicht exakt, da hier genau wie bei den Momenten die Zwischengitterverschiebung noch mit beachtet werden müßte. So wird beispielsweise nach dieser Methode ein Bereich, welcher 4 Bildpunkte breit ist, mit nur 3 Konturschritten durchlaufen und deshalb wird auch nur 3mal aufsummiert. So ist die berechnete Fläche in der Regel immer zu klein.

Schwerpunkt:

Der Segmentschwerpunkt errechnet sich wie folgt aus den ersten Momenten:

Abbildung in dieser Leseprobe nicht enthalten

Die ersten Momente berechnen sich aus der Objektkontur folgendermaßen:

Abbildung in dieser Leseprobe nicht enthalten

Orientierung und Ellipsenradien:

Die Orientierung eines Segmentes entspricht der Richtung der längere Hauptträgheitsachse des Segmentes. Zur Berechnung der beiden Hauptträgheitsachsen wird das Segment durch eine Ellipse angenähert, welche die gleiche Orientierung und das gleiche Seitenverhältnis wie das Segment besitzt. Die beiden Radien der Ellipse repräsentieren dann die längere und die kürzere Hauptträgheitsachse des Segmentes.

Die Richtung der längeren Hauptträgheitsachse entspricht dabei der Richtung des Eigenvektors mit dem größten Eigenwert der Matrix M:

Abbildung in dieser Leseprobe nicht enthalten

Dabei bezeichnen m20, m11 und m02 die sog. zentrierten (oder zentralen) zweiten Momente, die im Gegensatz zu den aus obiger Gleichung ableitbaren Momente von der Segmentposition unabhängig sind (translationsinvariant), da sie auf den Segmentschwerpunkt bezogen sind. Die zentrierten zweiten Momente berechnen sich im flächenbezogenen Fall wie folgt:

Abbildung in dieser Leseprobe nicht enthalten

Für den Übergang zur konturbezogenen Bestimung der zentralen 2. Momente

substituieren wir zunächst[Abbildung in dieser Leseprobe nicht enthalten] und wenden wieder die Gleichung 3.3 an:

Abbildung in dieser Leseprobe nicht enthalten

Die Berechnung der Eigenwerte der Matrix M ist z.B. in [ZUR64] erläutert und führt auf ein Polynom 2. Grades, dessen Lösungen Imax, min im Fall von m11 ≠ 0 wie folgt aussehen:

Abbildung in dieser Leseprobe nicht enthalten

Damit ist die Richtung der längeren Hauptträgheitsachse bzw. die Orientierung des Segmentes bekannt:

Abbildung in dieser Leseprobe nicht enthalten

Aus den Momenten Imax und Imin, sowie der Fläche F des Segmentes lassen sich dann der längere Radius ra und der kürzere Radius rb derjenigen Ellipse berechnen, die die gleiche Orientierung und das gleiche Seitenverhältnis wie das Segment hat:

Abbildung in dieser Leseprobe nicht enthalten

Noch aussagekräftiger sind diese beiden Radien, wenn sie bzgl. der Fläche des Segmentes normiert werden, d.h. wenn das betrachtete Segment und die dazugehörige Ellipse flächengleich sind. Die Radien werden dann mit Ra und Rb bezeichnet und berechnen sich wie folgt:

1. Bedingung: Segmentfläche gleich Ellipsenfläche:[Abbildung in dieser Leseprobe nicht enthalten]

2. Bedingung: Achsenverhältnis bleibt gleich: [Abbildung in dieser Leseprobe nicht enthalten]

Aus der 2. Bedingung ergibt sich für Ra: R [Abbildung in dieser Leseprobe nicht enthalten]

Aus der 1. Bedingung ergibt sich für Rb: R [Abbildung in dieser Leseprobe nicht enthalten]

Damit erhält man nach Einsetzen der ersten Bedingung in die zweite:

Abbildung in dieser Leseprobe nicht enthalten

Nach dem Radizieren erhält man unter Beachtung eines Ausnahmefalls:

Abbildung in dieser Leseprobe nicht enthalten

3.2.1.2 Formmerkmale

Die folgenden Merkmale sind aus [RIC95] entnommen:

Anisometrie:

Die Anisometrie A eines Segmentes mißt die Langgestrecktheit eines Segmentes und ist als das Verhältnis der längeren zur kürzeren Halbachse der Segmentellipse definiert. Für kreisförmige Segmente gilt A = 1, sonst A > 1:

Abbildung in dieser Leseprobe nicht enthalten

Ein Maß für die Sperrigkeit eines Segmentes ist der Formfaktor B:

Abbildung in dieser Leseprobe nicht enthalten

Kompaktheit:

Die Kompaktheit mißt die Glattheit der äußeren Kontur. Für einen Kreis gilt C = 1. Für weniger glatte Außenkonturen gilt C > 1:

Abbildung in dieser Leseprobe nicht enthalten

Diese Formmerkmale sind dabei weitestgehend translations-, skalierungs und rotationsinvariant.

3.2.2 Fourierdeskriptoren

Eine zweite Möglichkeit Invarianten eines Segmentes zu erhalten ist mittels der sog. Fourierdeskriptoren möglich. Dazu wird das Objekt (oder genauer die Kontur des Objektes) mittels einer Fouriertransformation in den Frequenzbereich überführt. Dieses Spektrum entspricht dann den Fourierdeskriptoren des Objektes.

Die Vorteile die für den Einsatz der Fourierdeskriptoren sprechen sind:

1. sie können direkt aus der Kontur des gefundenen Objektes berechnet werden
2. sie lassen sich sehr einfach translations- und skalierungsinvariant machen
3. ihre Beträge sind rotations- und startpunktinvariant

Dadurch stellen sie nahezu ideale Invarianten zur Segmenterkennung dar.

Die Fourierdeskriptoren eines Objektes lassen sich bestimmen, in dem man eine Fourier-Transformation über alle Bildpunkte der Kontur dieses Objektes ausführt. Wenn die Anzahl der Bildpunkte eine 2er Potenz darstellt, kann dafür auch eine FFT verwendet werden.

Formel DFT:

Abbildung in dieser Leseprobe nicht enthalten

Eine Umsortierung der Werte in die Form:

Abbildung in dieser Leseprobe nicht enthalten

liefert dabei die unten abgebildeten Darstellungen mit N = 1024. Dargestellt sind allerdings nur die ersten 32 Werte und der schon nullgesetzte 0. Deskriptor (Darstellung von k = -16 bis k = +16).

Translationsinvarianz (Normierung der Lage):

Z(0) = 0 bewirkt ein Verschieben des Schwerpunktes der Kontur in den Ursprung des Koordinatensystems.

[...]