Robustes Feature Tracking

Inhaltsverzeichnis

1 Einführung
1.1 Definitionen
1.2 Hauptziel
1.3 Schwierigkeiten

2 Kanade-Lucas-Tomasi
2.1 Feature-Extraktion
2.2 KLT-Algorithmus
2.3 KLT-Erweiterungen
2.3.1 Background Compensation
2.3.2 X84: Rückweisungsregel für Ausreißer
2.4 Open-CV

3 Bidirektionales-Matching-Verfahren
3.1 Moravec-Operator
3.1.1 Erweiterungen des Moravec-Operators
3.2 Feature-Korrelation
3.2.1 Positionskorrelation
3.2.2 Korrelation der lokalen Struktur
3.2.3 Kombination beider Ansätze
3.3 Bidirektionales Matching
3.3.1 Stream-Fortsetzung
3.3.2 Stream-Ende
3.3.3 Stream-Entstehung
3.3.4 Geister
3.3.5 Rauschen

4 Condensation-Algorithmus
4.1 Ablauf des Condensation Algorithmus
4.2 Fazit zum Condensation Algorithmus

Literatur

1 Einführung

1.1 Definitionen

Feature sind man bestimmte Merkmale, die in einem Bild auftauchen können. Das sind sowohl markante Punkte (Abb. 1.1 links), aber auch Kanten von Objekten in Form von Linien (Abb. 1.1 Mitte), Kurven, Kreisen oder Ellipsen (Abb. 1.1 rechts) sein. Auch Farben können Merkmale als Bildinformation darstellen. Unter Feature Tracking versteht man dann das Verfolgen dieser extrahierten Merkmale innerhalb einer Bildfolge. Dabei müssen die Featureinformationen logisch miteinander verknüpft werden. Aufeinanderfolgende Merkmale, die von Bild zu Bild übereinstimmen, bilden den sogenannten Featurestream (Merkmalsstrom).

Abbildung in dieser Leseprobe nicht enthalten

Abb. 1.1: Beispiele ausgewählter Feature

1.2 Hauptziel

Mit Hilfe von Feature Tracking ist es also möglich, ein oder mehrere Objekte durch eine Videosequenz zu verfolgen. Voraussetzung für jeden Algorithmus ist eine effiziente Analyse der Bildinformationen, das heisst, dass die Verarbeitung der Informationen in Echtzeit läuft. Besitzt dieser Algorithmus auch noch eine hohe Fehlertoleranz, ist er robust.

1.3 Schwierigkeiten

Bei der Objektverfolgung können einige Schwierigkeiten auftreten, die die Robustheit des Algorithmus negativ beeinflussen können.

1. Umgebungsveränderungen

Man kann bei der Verfolgung von Objekten nicht immer von einer idealen Um- gebung ausgehen. Oft wechseln die Hintergrundverhältnisse oder das zu ver- folgende Objekt ist dem Hintergrund sehr ähnlich wie das Blatt in Abbildung 1.1. Auch Veränderungen der Beleuchtung stellen große Anforderungen an den Algorithmus. Es werden auch Merkmale erkannt, die in der realen Welt keine sind. Dazu gehören insbesondere Schatten- oder Lichteinfall. Wie einfach es ist, dass ein Algorithmus ein falsches Merkmal auswählen kann, ist in Abbildung 1.2 dargestellt. Reflexionen auf glänzenden Oberflächen liefern ebenso falsche 3D- Merkmale die sich auch in ihrer 3D-Position mit der Kamerabewegung ändern. Daher beschränken sich einige Algorithmen auf einfache Umgebungsverhältnisse, um eine gewisse Robustheit zu wahren.

2. Objektveränderungen

Noch größere Schwierigkeiten stellen die Veränderungen am Objekt selbst dar. Es ist klar, dass sich während der Videosequenz die Lage und Position des Objektes ändern. Bei zu großen Sprüngen innerhalb der Bildfolge können Features verloren gehen. Ebenso wenn Teile des Objektes verdeckt werden, oder sogar für kurze Zeit ganz verschwindet.

Wenn es ein Verfahren bzw. Algorithmus gibt, der die Probleme der Umgebungs- und Objektveränderungen löst, kann man von einem robusten Feature Tracking System sprechen.

Abbildung in dieser Leseprobe nicht enthalten

Abb. 1.2: Beispiel einer falschen Merkmalsauswahl

2 Kanade-Lucas-Tomasi

Der Algorithmus von Kanade-Lucas-Tomasi (KLT) bildet seit 1981 die Grundlage viele guter Verfahren zur Objektverfolgung [1; 2]. Auch wenn dieser Algorithmus nicht allzu robust ist, hat er aufgrund seiner Einfachheit bis heute überlebt und ist in einigen Softwaresystemen eingebettet, so zum Beispiel in der Grafikbibliothek OpenCV von Intel.

2.1 Feature-Extraktion

Wie in allen Feature-Tracking-Verfahren findet am Anfang jeder Verfolgung die Merk- malsauswahl im Bild statt. Wie schon erwähnt, benötigt KLT (und natürlich jeder an- dere auch) markante Bildpunkte. Der KLT-Algorithmus sucht demzufolge nach auffälli- gen Punkten (in Farbe und/oder Kontrast). Hohe Farb- und Kontrastunterschiede fin- det man vorallem in Anfangs- und Endpunkten von Kanten, sowie in Eckpunkten von Flächen. In diesen Punkten ist die Wahrscheinlichkeit am höchsten, dass sie im Folge- bild wiedergefunden werden. Dies ist Voraussetzung zur Bildung des Featurestreams bzw. der späteren Objektverfolgung.

Bei der Merkmalsauswahl wird ein vordefiniertes Fenster (z.B. 5x5) über das Bild ge- schoben, wobei in jedem Fenster die Pixel auf Farbunterschiede ausgewertet werden:

1. Für jeden Pixel P(x,y) wird der Gradient gx,gy berechnet (Abb. 2.1).

Abbildung in dieser Leseprobe nicht enthalten

Abb. 2.1: Berechnete Gradienten im Fenster

2. Berechnung des Mittelwertes und der Kovarianzmatrix mit Hilfe der Gradienten.

3. Berechnung der Eigenvektoren und Eigenwerte λ1, λ2 . Sie beinhalten die Farb- informationen der Pixel (Abb. 2.2).

Abbildung in dieser Leseprobe nicht enthalten

Abb. 2.2: Der Unterschied zwischen beiden Eigenwerte wächst vom linken zum rechten Bild

4. Wenn min(λ1, λ2) größer als ein vordefinierter Schwellwert ist, herrschen im Fens- ter hohe Kontrastunterschiede. Der Featurepunkt kann somit gesetzt werden.

2.2 KLT-Algorithmus

Mit Hilfe der Merkmalsauswahl aus Abschnitt 2.1 findet und setzt KLT die erfor- derlichen Featurepunkte, wo im Bild hohe Kontrastunterschiede (Ecken und Kanten) vorherrschen. In flachen, einfarbige Wänden werden keine Merkmalspunkte gesetzt, da hier der Kontrast nur schwach variiert. Die Auswahl wird nun für jedes Bild der Video- aufnahme durchgeführt. Als Ergebnis erhält man korrespondierende Punkte zwischen dem ersten und dem letzten Bild des Videos (Merkmalsspur). Bei 25 bis 30 Bildern je Sekunde ändert sich die Kameraposition nur geringfügig von Bild zu Bild. Aufeinan- derfolgende Bilder sind somit ziemlich ähnlich, wobei die Merkmalspunkte immer an etwa der gleichen Stelle liegen. Die Verfolgung der gefundenen Merkmalspunkte kann somit quer durch das Video erfolgen. Quellcode und Handbuch sind erhältlich unter: http://robotics.stanford.edu/∼ birch/klt/

2.3 KLT-Erweiterungen

Wie schon erwähnt, ist KLT ein einfacher Algorithmus. Daher beschränkt er sich meist auf einfache geometrische Objekte mit gut sichtbaren Ecken und Kanten, wobei sich das Objekt noch möglichst gut vom Hintergrund abhebt. Abbildung 2.3 zeigt ein mögliches Szenario mit einem hellen Treppenmodel auf schwarzem Hintergrund. Die Verfolgung des Objektes stellt dem Algorithmus vor nicht allzu große Schwierigkeiten. Allerdings ist KLT relativ anfällig auf Objekt- und Umgebungsänderungen (Reflektionen, Überde- ckungen, ...), wobei dann viele Features verloren gehen und den Prozeß instabil machen können.

Abbildung in dieser Leseprobe nicht enthalten

Abb. 2.3: Mögliches KLT-Szenario mit ausgewählten Merkmalen

2.3.1 Background Compensation

Enthält die Videosequenz Schwierigkeiten der Objekt- und Umgebungsveränderungen, kann KLT nicht immer Echtzeitfähigkeit gewährleisten. Durch background compen- sation lässt er sich verbessern. Dabei werden zwei Folgebilder miteinander verglichen (Substraktion). Ergibt sich kein Unterschied im Ergebnis, ist auch kein bewegtes Ob- jekt in beiden Bilder vorhanden(Abb. 2.4 linke Spalte). Eine Suche nach 2.1 über das gesamte Bild ist somit nicht nötig und es können gleich die nächsten beiden Bilder betrachtet werden. Ein Objekt, dass seine Position und Lage im Bild verändert, kann durch die Substraktion zweier Folgebilder gefunden werden. Der ”unbewegte” Hinter- grund kann vernachlässigt werden und die Merkmalssuche beschränkt sich somit nur auf das bewegte Objekt (Abb.2.4 mittlere und rechte Spalte).

Abbildung in dieser Leseprobe nicht enthalten

Abb. 2.4: background compensation an zwei aufeinander folgenden Bildern

2.3.2 X84: Rückweisungsregel für Ausreißer

Um ein Objekt erfolgreich verfolgen zu können, müssen mindestens 8 Merkmale aus- gewählt werden. KLT nimmt dazu die besten Feature, die über einer Schwelle liegen (mit der größten Differenz der Eigenwerte, wobei Anzahl und Schwellwert vorher festge- legt wurden) und speichert sie in einer sogenannten Featureliste. Durch Veränderungen des Objektes oder der Umgebung ändern sich Eigenwerte und somit auch die Featu- reliste. Die Anzahl der anfangs gefundenen und gesetzten Feature wird immer kleiner. Daher ist ein Eingriff notwendig, um die falschen Merkmale zu entfernen und wieder eine Stabilität zu erreichen. Die Visualisierung der Verbindung zwischen korrespondie- renden Merkmalen (durch Linien) ermöglicht eine leichte Identifikation der falschen Merkmale. Sie müssen manuell vom Benutzer entfernt werden.

Eine weitere Verbesserung des KLT-Algorithmus ist X84, eine Rückweisungsregel für Ausreißer³. Hier werden mit Hilfe des Median, dessen Eigenschaft Robustheit gegenüber Ausreißer im Gegensatz zum Mittelwert hier zugute kommt, diese Ausreißer aufgespürt und zurückgewiesen. Durch das Residuum (Abweichung vom Schätzwert) kann eine Schwellwertberechnung der Intensitäten (Grauwerte) durchgeführt werden. Die Qualität jedes einzelnen Punktes kann somit durch das Residuum gemessen werden. Abbildung 2.5 und 2.6 sollen dies nochmals verdeutlichen.

Abbildung in dieser Leseprobe nicht enthalten

Abb. 2.5: Rückweisung einiger Feature mittels X84

Der Schwellwert wird von der Regel jetzt automatisch gesetzt. Feature, die zu stark vom Schätzwert abweichen und die Schwelle überschreiten (Abb. 2.6), können somit zurückgewiesen werden. In Abbildung 2.5 kommt es zur Überlagerung von Feature 21, 26, 30 und 32 mit anderen ausgewählten Merkmalen. Sie werden zurückgewiesen und können durch bessere Feature ersetzt werden, um eine Stabilität im Verfahren zu gewährleisten.

Demobeispiele zum KLT-Algorithmus und X84 findet man unter: http://www.ece.eps.hw.ac.uk/∼ costas/Demos/trademo/

Abbildung in dieser Leseprobe nicht enthalten

Abb. 2.6: 4 Feature werden durch zu starker Abweichung vom Residuum und bei Schwell- wertüberschreitung zurückgewiesen

2.4 Open-CV

OpenCV ist eine Open-Source Bibliothek, welche Funktionen für den Bereich Computer Vision enthält, wie zum Beispiel den KLT-Algorithmus. Das Softwarepaket wurde von Intel im Jahr 2000 veröffentlicht. Zielsetzung dieser Bibliothek ist die Grundlage für einen breiten Einsatz von Personal Computern im Bereich der Computer Vision zu schaffen. Die Bibliothek beinhaltet Routinen aus einem breiten Spektrum der Computer Vision. Open-CV ist verfügbar unter:

3 Bidirektionales-Matching-Verfahren

Das Verfahren des Bidiktionale Matching besteht aus 3 Teiloperationen⁵:

1. Moravec-Operator
2. Feature-Korrelation (Struktur, Position)
3. Bidirektionales Matching

3.1 Moravec-Operator

Als grundlegende Methode für die Feature-Extraktion wird der sogenannte MoravecOperator verwendet. Dazu werden auftretender Grauwerte über einem n x n Faltungskern (Bildausschnitt) auswertet. Dabei werden die Varianzen der Grautöne, die entlang der 4 Hauptrichtungsachsen (Horizontale, Vertikale und die zwei Hauptdiagonalen) des Faltungskerns auftreten, betrachtet und die Grauwertdifferenzen aufsummiert. Formeln für diese Berechnung lauten:

Abbildung in dieser Leseprobe nicht enthalten

Die aktuelle Pixelposition wird durch (x,y) beschrieben. Liegt eine (im Bild befindli- che) Kante entlang einer der vier Hauptrichtungen, so ist die entsprechende Summe null. Nun folgt eine lokale Maximumsuche innerhalb des Faltungskerns. Dabei sollte der Grauwert des Features nicht nur ein lokales Maximum sein, sondern auch über einem festen Schwellwert liegen. Lokale Grauwertmaxima, die durch spezielle Ober- flächenstrukturen (z.B. Marmorierungen) auftreten können, werden dadurch herausge- filtert. Die Ergebnisse der Grundform des Moravec-Operators sind nur sehr begrenzt zuverlässig. Aus diesem Grunde werden Erweiterungen des Operators eingeführt, um dieses Problem zu vermindern.

[...]