Ähnlichkeitssuche über Videosequenzen

anhand Bewegungsvektoren

Martin Denzel, Younes Alj

Lehr- und Forschungseinheit für Datenbanksysteme

Ludwig-Maximilians-Universität München

Zusammenfassung

Diese Arbeit beschäftigt sich mit der Objekterkennung in Videosequenzen anhand der

Ähnlichkeit der enthaltenen Bewegungsvektoren. Nachdem die Grundlagen und

Prinzipien verschiedener Ähnlichkeitsmodelle behandelt werden, wird näher auf die

Ähnlichkeitssuche bei Videodaten eingegangen. Dazu gehört eine Einführung in die

Funktionsweise von Videokompression und ein kurzer Überblick über den

Videostandard MPEG-4. Anschließend wird erklärt wie Featuremerkmale ­ in unserem

Fall Bewegungsvektoren ­ aus Videos extrahiert und zur Ähnlichkeitssuche verwendet

werden können.

2

Inhaltsverzeichnis

1. Einleitung 5

2. Ähnlichkeitsmodelle 5

2.1 Distanzfunktionen 6

2.2 Datentypabhängige Ähnlichkeitssuche 7

2.3 Ähnlichkeitssuche über Videodaten 8

3. Videogrundlagen 8

3.1 Videokompression 8

3.1.1 Bewegungskompensation (motion compensation) 9

3.1.2 Bewegungsschätzung (motion estimation) 10

3.1.3 Berechnung von Bewegungsvektoren 11

3.2 MPEG ­ 4 12

3.2.1 Dekodiervorgang 12

3.2.2 Verschiedene Frame-Typen 13

4. Featureextraktion ­ Gewinnung von Bewegungsvektoren .. 13

4.1 Frameworks aus Bild- und Videobearbeitung

13

4.2 Implementierung ,,VideoTracker" 14

5. Auswertung der gewonnen Daten 17

5.1 Vorbereitungen 17

5.2 Benutzung der Software ,,TTime"

18

5.3 Average-Precision Wert

18

6. Zusammenfassung

19

7. Literatur

20

3

Abbildungsverzeichnis

[1-5] Böhm, C. : Skript zur Vorlesung Datenbanksysteme II, 2006, Kapitel 5, LMU

München.

[6-8] Knorr, W.: ,,Motion Estimation ­ Motion Compensation", 2005

[9]

Patrick-Emil Zörner, GNU-License, besucht am 10.04.2008 unter:

http://de.wikipedia.org/wiki/Bild:MPEG-4_ASP_Dekoder_Blockschaltbild.png

[10]

Alj, Denzel: Screenshot der Software VideoTracker

[11] Alj, Denzel: Screenshot: Makroblöcke mit der jeweiligen Verschiebung X und Y

[12] Alj, Denzel: Screenshot des VLC-Player im Bewegungsvektormodus

[13] Alj, Denzel: Screenshot: Häufigkeit der Winkel Pro Frame und Dimension

[14] Alj, Denzel: Screenshot der TTime Software

[15] Alj, Denzel: Screenshot: Precision/Recall Analyse mit der Software TTime

4

1 Einleitung

Die rasanten technologischen Entwicklungen der letzten Jahre haben es möglich gemacht,

große Mengen von Bild- und Videomaterial in sogenannten ′Multimediadatenbanken′

elektronisch abzuspeichern und gleichzeitig Millionen von Nutzern zum Abruf zur Verfügung

zu stellen. Jüngste Beispiele der Internetgeschichte sind Videocommunities wie

YouTube

oder

MyVideo

, die Ihren Nutzern Webspace und Serverleistung zur Speicherung und Abrufbarkeit

der Videoaufnahmen anbieten.

Mit der Fortsetzung dieses Trends gewinnt allerdings auch das Problem der effizienten Suche

in zunehmend unüberschaubaren Datenmengen immer mehr an Bedeutung. Traditionelle

Techniken wie die Suche über z.B. den Dateinamen oder das Entstehungsdatum machen bei

großen Datenmengen oder mehreren neu hinzugefügten Videos pro Sekunde keinen Sinn.

Auch die aufwändige Indexierung mit Metadaten oder die Vergabe von Schlüsselbegriffen für

jedes Multimedia-Objekt ist nur begrenzt effektiv und genau. Schon eher eine Lösung

scheinen daher inhaltsbezogene Suchsysteme zu bieten. Sie benötigen keine zusätzlich

generierten Informationen, sondern extrahieren aus der tatsächlichen Datenrepräsentation

geeignete Merkmale (Features) heraus, die für die Unterscheidung oder die Klassifikation der

Multimedia-Objekte relevant sind. Für jede Art von Daten können sich hierbei

unterschiedliche Features als geeignet erweisen. Bei Zeichnungen können z.B. Höhe, Breite

und Kurvatur entscheidend sein, bei Bildern die Farbwerte der Pixel und bei Texten die

Begriffshäufigkeiten. Man könnte jetzt denken, dass eine Suchanfrage, die sich für die

Farbwerte eines Bildes interessiert sehr selten und ungewöhnlich ist. Das ist richtig, allerdings

sind Anfragen wie ,,Finde alle Bilder, die ebenfalls einen Sonnenuntergang enthalten" schon

wahrscheinlicher und können dann anhand der ähnlichen Farbverteilungen eventuell

beantwortet werden.

Fasst man alle Features eines Objektes zusammen erhält man als Ergebnis einen sog.

′Feature-Vektor′. Unter Einsatz von Distanzfunktionen können diese Vektoren verwendet

werden, um die Ähnlichkeit zwischen Objekten zu bestimmen. Die Ähnlichkeit zweier

Objekte ist dann durch den Abstand der jeweiligen Feature-Vektoren definiert, und zwar so,

dass je geringer der Abstand der Feature-Vektoren ist, umso ähnlicher sich die Objekte sind.

[1]

Im Rahmen dieser Arbeit konzentrieren wir uns auf Videodateien und versuchen anhand des

Features ′Bewegungsvektor′ ähnliche Videos bzw. Videos mit ähnlichen Objekten zu

bestimmen. Die Frage ist, ob Bewegungsvektoren als unterscheidendes Merkmal geeignet

sind und vor allem ob sie als alleiniges Merkmal ausreichen, um brauchbare Klassifizierungen

und Ähnlichkeiten herauszuarbeiten.

Bevor diese Frage beantwortet werden kann, werden wir im Folgenden noch näher auf

unterschiedliche Ähnlichkeitsmodelle eingehen sowie zum Verständnis notwendige

Grundlagen der Videokompression und des Videostandards MPEG-4 betrachten.

2 Ähnlichkeitsmodelle

Wie bereits in der Einleitung erwähnt werden Objekte anhand ihrer charakterisierenden

Merkmale in Form von Featurevektoren dargestellt. Um Feststellungen bzgl. der Ähnlichkeit

zweier Objekte bzw. ihrer Featurevektoren treffen zu können, müssen Kriterien definiert

werden, die festlegen warum ein Objekt A einem Objekt B mehr ähnelt als einem Objekt C.

Es muss also eine Ähnlichkeitsfunktion existieren, die ein Maß für die Ähnlichkeit zweier

Objekte angibt. Das Ergebnis dieser Funktion gibt dann Aufschluss über den

Ähnlichkeitsgrad. In der Regel deutet ein Wert nahe 1 auf eine hohe und ein Wert gegen 0 auf

geringe Ähnlichkeit hin.

5