Inhaltsverzeichnis

INHALTSVERZEICHNIS   1

1.  AUFGABENSTELLUNG  3

2.  EINFÜHRUNG.  3

3.  GRUNDLAGEN.  4

3.1  SEGMENTIERUNG  4

3.1.1  sequentielles Regionenwachstumsverfahren  4

3.1.2  quasi-paralleles Regionenwachstumsverfahren  5

3.1.3  paralleles Regionenwachstumsverfahren  8

3.1.4  Kantenrelaxation.  8

3.1.5  Segmentierung nach Kontur / Konturverfolgung  11

3.2.  INVARIANTEN  13

3.2.1  Momente.  13

3.2.1.1  Konturmerkmale  16

3.2.1.2  Formmerkmale.  19

3.2.2  Fourierdeskriptoren.  20

3.3  TRANSFORMATION BILDKOORDINATEN IN WELTKOORDINATEN  28

3.4  FILTERUNG  29

3.4.1  Laplace-Filterung  29

3.4.2  Median-Filter.  30

3.5  ENTWICKLUNGSUMGEBUNG.  32

3.5.1  Hardware  32

3.5.1.1  Kamera  32

3.5.2  Software  33

3.5.3  Grundvoraussetzungen  33

4.  VERFAHREN ZUR STRAßENRANDERKENNUNG.  34

4.1  SEGMENTIERUNG NACH FLÄCHENINHALT (REGION GROWING)  34

4.1.1  Ausgangsregionen erstellen  34

4.1.2  Regionen vereinigen.  35

4.1.3  Programmablauf (schematisch)  37

4.1.4  Ergebnis  38

4.1.5  Kantenrelaxation.  39

4.2  SEGMENTIERUNG NACH KONTUR  40

4.2.1  Startpunktsuche.  40

4.2.2  Konturverfolgung  40

4.2.3  Bildverbesserung durch Grauwertmanipulation  42

4.2.4  adaptive Bestimmung der Schwellwerte  44

4.2.5  Programmablauf (schematisch)  45

4.2.6  Ergebnis  46

4.3  AUSWERTUNG UND VERGLEICH DER BEIDEN SEGMENTIERUNGS-VERFAHREN.  51

4.4  SEGMENTERKENNUNG  52

4.4.1  Flächenkriterium  52

4.4.2  Formkriterium  53

- 1 -

4.4.3  Fourierdeskriptoren.  55

4.4.4  Konturglättung  59

4.4.5  Auswertung.  60

4.4.6  Ergebnis der Segmenterkennung  61

4.5  GRUPPENBILDUNG  62

4.5.1  Gruppierung im Bildkoordinatensystem  64

4.5.2  Gruppierung im Weltkoordinatensystem.  64

4.5.3  Auswertung und Ergebnis der Gruppierung.  65

5.  ERGEBNIS.  67

6.  ZUSAMMENFASSUNG UND AUSBLICK  71

6.1  ZUSAMMENFASSUNG  71

6.2  AUSBLICK  72

7.  LITERATURVERZEICHNIS  73

A  ANHANG.  74

A.1  BEDIENUNG DER SOFTWARE.  74

A.2  ABBILDUNGSVERZEICHNIS  76

- 2 -

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 -

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.

- 4 -

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 R A und R B aus N A bzw. N B Bildpunkten. Die einzelnen Merkmalswerte (Grauwerte) der Regionen werden zu einem Datenvektor

y bzw. B y mit N A bzw. N B Komponenten zusammengefaßt. Die Merkmalswerte der

A

beiden Regionen werden dabei als Zufallsprozesse betrachtet, deren bzw. ( ) Verteilungsdichtefunktion ( )

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

• Nullhypothese H 0 : beide Regionen entstammen ein und dem selben Prozeß

• Gegenhypothese H 1 : 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:

( )

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 y i des Datenvektors

r { }

= =

i , y y i

Die multidimensionale Verteilungsdichte (Verbundverteilungsdichte) des gesamten σ : Datenvektors lautet bei einem gegebenen Wert von m y und 2

σ die Maximum-Likelihood-Setzt man für die unbekannten Parameter m y und 2

y

Schätzungen für Mittelwert und Varianz ein:

So ergibt sich:

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

• H 0 :

mit N C = N A + N B (Region C ist die Vereinigung der Regionen A und B) σ ist der Maximum-Likelihood-Schätzwert der Varianz der Zusammenfassung ² ˆ

C

beider Regionen

• H 1 :

( ) { } ( ) ) { } r r (

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

wie folgt:

r r ( )

Mit N C = N A + N B folgt daraus:

Gleichung 3.1: Hypothesentest

Zum Verfahren:

Zu Beginn dieses Verfahrens sollte zunächst eine Sequenz von ansteigenden Grauwertdifferenzschwellen t max1 ... t maxn festgelegt werden. Begonnen wird mit t max1 , was durchaus 0 gewählt werden kann, um zunächst alle benachbarten Pixel des gleichen Grauwertes zu verschmelzen. t maxn 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 t max ist, wird die Distanz (verallgemeinertes Likelihood-Verhältnis / Hypothesentest - Gleichung 3.1) der beiden Regionen berechnet. Falls diese wiederum kleiner als d max 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 t max auf den nächsten Wert erhöht und die Prozedur beginnt mit dem Aufstellen der Hypothesen von vorn, bis t maxn 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)

- 7 -

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.

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

- 8 -

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:

( ) ( ) ( ) ( ) D

⁺ ) steht für die Likelihoodfunktion der Region R i bei Hinzunahme des Punktes L(R i

^- L(R i ) steht für die Likelihoodfunktion der Region R i ohne den betreffenden Punkt n B , n C , n D und n E 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:

Der Logarithmus der Funktion beträgt dann:

Bezeichnet N die Größe der Region R i 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:

Daraus ergibt sich:

Somit ergibt sich die Gesamtfunktion zu:

Gleichung 3.2: Kantenrelaxation

- 9 -

Bestimmung der Cliquenzahlen n B , n C , n D und n E :

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:

• n B ... Anzahl der horizontalen & vertikalen 2er Cliquen mit gleichem Wert

• n C ... Anzahl der horizontalen & vertikalen 2er Cliquen mit unterschiedlichem Wert

• n D ... Anzahl der diagonalen 2er Cliquen mit gleichem Wert

• n E ... 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:

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):

• n B = 1

• n C = 3

• n D = 2

• n E = 2

• Punkt gehört zu Region 2 (Label muß geändert werden):

• n B = 3

• n C = 1

• n D = 2

• n E = 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.

Tabelle 3.1: Standardabweichungen der Regionen

- 10 -

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

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

Mit B = -2 ergeben sich dann folgende Ergebnisse:

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 r 1 , r 2 , ...,r i , ..., r N 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.“

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

- 11 -

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)

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.

- 12 -

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 M pq 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:

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. ⎡

∫∫

⎢

⎣

F

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

Eine Lösungsmöglichkeit ist durch die Wahl

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

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

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:

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.

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

- 14 -

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: x ⋅ ^{q p} y

i i

Somit erhält man abschließend folgende Formel:

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 r i der Wert des Konturcodes der von dem Punkt wegführt und r i-1 ist der Wert der zu dem Punkt hinführt.

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

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

- 15 -