Ähnlichkeitssuche über Videosequenzen anhand von Bewegungsvektoren

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

Eine andere Möglichkeit Featurevektoren zu vergleichen ist das distanzbasierte Ähnlichkeitsmaß. Hier definieren Abstands- oder Distanzfunktionen die Unähnlichkeit der Objekte, wobei ein geringer Abstand der Vektoren für eine hohe Ähnlichkeit spricht. Durch Transformationen können Distanzfunktionen zu Ähnlichkeitsfunktionen umgewandelt werden. [1]

2.1 Distanzfunktionen

Distanzfunktionen haben die formalen Eigenschaften der Selbstidentität, der positiven Definitheit, der Symmetrie und der Erfüllung der Dreiecksungleichung. Je nach Art der Distanzfunktion können auch nur einige der Bedingungen erfüllt sein. Distanzfunktionen sollten invariant gegenüber Translation, Skalierung und Rotation sein. Die am häufigsten eingesetzte Distanzfunktion ist die Minkowski-Distanzfunktion (Abbildung ) bzw. deren Spezialfälle für die jeweilige Wertbelegung von p. Im folgenden werden einige dieser speziellen Distanzmaße vorgestellt. Auf tiefere mathematische Hintergründe kann im Rahmen dieser Arbeit jedoch leider nicht eingegangen werden.

Abb. 1: Minkowski - Distanz

Euklidische Distanz: Sie bezeichnet das natürliche Distanzmaß zweier Punkte, die durch eine Gerade miteinander verbunden sind. Ihr Einheitskreis ist kreisförmig und somit immer rotationsinvariant. Sie ist ein Spezialfall der Minkowskisumme für den Wert p=2.

Abb. 2: Euklidische Distanz

Gewichtete Euklidische Distanz: Durch Vergabe von Gewichten für einzelne Dimensionen wird eine achsenparallele Streckung oder Stauchung erreicht. Der Einheitskreis hat die Form einer Ellipse.

Abb. 3: Gewichtete Euklidische Distanz

Manhattan Distanz: Der wichtigste Unterschied zum euklidischen Abstand ist, dass die einzelnen Differenzen nicht quadriert werden. Bei einer Quadrierung gehen große Differenzen stärker in die Abstandsberechnung mit ein als kleine. Die Manhattan-Distanz hat einen rechteckigen Einheitskreis und ist ein Spezialfall der Minkowskisumme für den Wert p=1. Für den Vergleich von Binärcodes wird die L1-Metrik als Hamming-Abstand bezeichnet.

6