INHALTSVERZEICHNIS

Inhaltsverzeichnis   

1  Einf uhrung  1

1.1  Definitionen  1

1.2  Hauptziel  1

1.3  Schwierigkeiten  1

2  Kanade-Lucas-Tomasi  3

2.1  Feature-Extraktion  3

2.2  KLT-Algorithmus  4

2.3  KLT-Erweiterungen  4

2.3.1  Background Compensation  5

2.3.2  X84: R uckweisungsregel f ur Ausreißer  6

2.4  Open-CV  8

3  Bidirektionales-Matching-Verfahren  9

3.1  Moravec-Operator  9

3.1.1  Erweiterungen des Moravec-Operators  10

3.2  Feature-Korrelation  13

3.2.1  Positionskorrelation  13

3.2.2  Korrelation der lokalen Struktur  13

3.2.3  Kombination beider Ans atze  14

3.3  Bidirektionales Matching  15

3.3.1  Stream-Fortsetzung  16

3.3.2  Stream-Ende  16

3.3.3  Stream-Entstehung  17

3.3.4  Geister  17

3.3.5  Rauschen  18

4  Condensation-Algorithmus  19

4.1  Ablauf des Condensation Algorithmus  20

4.2  Fazit zum Condensation Algorithmus  23

Literatur   24

Hauptseminar  Thomas M unzberg  i

1 Einf¨ uhrung

1.1 Definitionen

Feature sind man bestimmte Merkmale, die in einem Bild auftauchen k¨ onnen. 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¨ onnen Merkmale als Bildinformation darstellen. Unter Feature Tracking versteht man dann das Verfolgen dieser extrahierten Merkmale innerhalb einer Bildfolge. Dabei m¨ ussen die Featureinformationen logisch miteinander verkn¨ upft werden. Aufeinanderfolgende Merkmale, die von Bild zu Bild ¨ ubereinstimmen, bilden den sogenannten Featurestream (Merkmalsstrom).

1.2 Hauptziel

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

1.3 Schwierigkeiten

Bei der Objektverfolgung k¨ onnen einige Schwierigkeiten auftreten, die die Robustheit des Algorithmus negativ beeinflussen k¨ onnen.

Hauptseminar Thomas M¨ unzberg 1

1. Umgebungsver¨ anderungen

Man kann bei der Verfolgung von Objekten nicht immer von einer idealen Umgebung ausgehen. Oft wechseln die Hintergrundverh¨ altnisse oder das zu verfolgende Objekt ist dem Hintergrund sehr ¨ ahnlich wie das Blatt in Abbildung 1.1. Auch Ver¨ anderungen der Beleuchtung stellen große Anforderungen an den Algorithmus. Es werden auch Merkmale erkannt, die in der realen Welt keine sind. Dazu geh¨ oren insbesondere Schatten- oder Lichteinfall. Wie einfach es ist, dass ein Algorithmus ein falsches Merkmal ausw¨ ahlen kann, ist in Abbildung 1.2 dargestellt. Reflexionen auf gl¨ anzenden Oberfl¨ achen liefern ebenso falsche 3D-Merkmale die sich auch in ihrer 3D-Position mit der Kamerabewegung ¨ andern. Daher beschr¨ anken sich einige Algorithmen auf einfache Umgebungsverh¨ altnisse, um eine gewisse Robustheit zu wahren.

2. Objektver¨ anderungen

Noch gr¨ oßere Schwierigkeiten stellen die Ver¨ anderungen am Objekt selbst dar. Es ist klar, dass sich w¨ ahrend der Videosequenz die Lage und Position des Objektes ¨ andern. Bei zu großen Spr¨ ungen innerhalb der Bildfolge k¨ onnen Features verloren gehen. Ebenso wenn Teile des Objektes verdeckt werden, oder sogar f¨ ur kurze Zeit ganz verschwindet.

Wenn es ein Verfahren bzw. Algorithmus gibt, der die Probleme der Umgebungs- und Objektver¨ anderungen l¨ ost, kann man von einem robusten Feature Tracking System sprechen.

2 Hauptseminar Thomas M¨ unzberg

2 KANADE-LUCAS-TOMASI

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 ¨ uberlebt 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 Merkmalsauswahl im Bild statt. Wie schon erw¨ ahnt, ben¨ otigt KLT (und nat¨ urlich jeder andere auch) markante Bildpunkte. Der KLT-Algorithmus sucht demzufolge nach auff¨ alligen Punkten (in Farbe und/oder Kontrast). Hohe Farb- und Kontrastunterschiede findet man vorallem in Anfangs- und Endpunkten von Kanten, sowie in Eckpunkten von Fl¨ achen. In diesen Punkten ist die Wahrscheinlichkeit am h¨ ochsten, dass sie im Folgebild wiedergefunden werden. Dies ist Voraussetzung zur Bildung des Featurestreams bzw. der sp¨ ateren Objektverfolgung.

Bei der Merkmalsauswahl wird ein vordefiniertes Fenster (z.B. 5x5) ¨ uber das Bild geschoben, wobei in jedem Fenster die Pixel auf Farbunterschiede ausgewertet werden:

1. F¨ ur jeden Pixel P(x,y) wird der Gradient g x ,g y berechnet (Abb. 2.1).

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

3 Hauptseminar Thomas M¨ unzberg

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

Abb. 2.2: Der Unterschied zwischen beiden Eigenwerte w¨ achst vom linken zum rechten Bild

4. Wenn min(λ 1 , λ 2 ) gr¨ oßer als ein vordefinierter Schwellwert ist, herrschen im Fenster 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 erforderlichen Featurepunkte, wo im Bild hohe Kontrastunterschiede (Ecken und Kanten) vorherrschen. In flachen, einfarbige W¨ anden werden keine Merkmalspunkte gesetzt, da hier der Kontrast nur schwach variiert. Die Auswahl wird nun f¨ ur jedes Bild der Videoaufnahme durchgef¨ uhrt. Als Ergebnis erh¨ alt man korrespondierende Punkte zwischen dem ersten und dem letzten Bild des Videos (Merkmalsspur). Bei 25 bis 30 Bildern je Sekunde ¨ andert sich die Kameraposition nur geringf¨ ugig von Bild zu Bild. Aufeinanderfolgende Bilder sind somit ziemlich ¨ ahnlich, 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¨ altlich unter: http://robotics.stanford.edu/ ^∼ birch/klt/

2.3 KLT-Erweiterungen

Wie schon erw¨ ahnt, ist KLT ein einfacher Algorithmus. Daher beschr¨ ankt er sich meist auf einfache geometrische Objekte mit gut sichtbaren Ecken und Kanten, wobei sich das Objekt noch m¨ oglichst gut vom Hintergrund abhebt. Abbildung 2.3 zeigt ein m¨ ogliches Szenario mit einem hellen Treppenmodel auf schwarzem Hintergrund. Die Verfolgung

4 Hauptseminar Thomas M¨ unzberg

des Objektes stellt dem Algorithmus vor nicht allzu große Schwierigkeiten. Allerdings ist KLT relativ anf¨ allig auf Objekt- und Umgebungs¨ anderungen (Reflektionen, ¨ Uberdeckungen, ...), wobei dann viele Features verloren gehen und den Prozeß instabil machen k¨ onnen.

2.3.1 Background Compensation

Enth¨ alt die Videosequenz Schwierigkeiten der Objekt- und Umgebungsver¨ anderungen, kann KLT nicht immer Echtzeitf¨ ahigkeit gew¨ ahrleisten. Durch background compensation l¨ asst er sich verbessern. Dabei werden zwei Folgebilder miteinander verglichen (Substraktion). Ergibt sich kein Unterschied im Ergebnis, ist auch kein bewegtes Objekt in beiden Bilder vorhanden(Abb. 2.4 linke Spalte). Eine Suche nach 2.1 ¨ uber das

gesamte Bild ist somit nicht n¨ otig und es k¨ onnen gleich die n¨ achsten beiden Bilder betrachtet werden. Ein Objekt, dass seine Position und Lage im Bild ver¨ andert, kann durch die Substraktion zweier Folgebilder gefunden werden. Der ”unbewegte” Hinter-grund kann vernachl¨ assigt werden und die Merkmalssuche beschr¨ ankt sich somit nur auf das bewegte Objekt (Abb.2.4 mittlere und rechte Spalte).

Hauptseminar Thomas M¨ unzberg 5