Ähnlichkeitssuche über Videosequenzen anhand von Bewegungsvektoren

Inhaltsverzeichnis

1. Einleitung

2. Ähnlichkeitsmodelle
2.1 Distanzfunktionen
2.2 Datentypabhängige Ähnlichkeitssuche
2.3 Ähnlichkeitssuche über Videodaten

3. Videogrundlagen
3.1 Videokompression
3.1.1 Bewegungskompensation (motion compensation)
3.1.2 Bewegungsschätzung (motion estimation)
3.1.3 Berechnung von Bewegungsvektoren
3.2 MPEG - 4
3.2.1 Dekodiervorgang
3.2.2 Verschiedene Frame-Typen

4. Featureextraktion - Gewinnung von Bewegungsvektoren ..
4.1 Frameworks aus Bild- und Videobearbeitung
4.2 Implementierung „VideoTracker“

5. Auswertung der gewonnen Daten
5.1 Vorbereitungen
5.2 Benutzung der Software „TTime“
5.3 Average-Precision Wert

6. Zusammenfassung

7. Literatur

Abbildungsverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

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.

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.

Abbildung in dieser Leseprobe nicht enthalten

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.

Abbildung in dieser Leseprobe nicht enthalten

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.

Abbildung in dieser Leseprobe nicht enthalten

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.

Abbildung in dieser Leseprobe nicht enthalten

Abb. 4: Manhattan Distanz

Quadratische Distanzfunktionen: Sie wird mittels einer Matrix dargestellt und erlaubt die gemeinsame Gewichtung verschiedener Dimensionen.

Abbildung in dieser Leseprobe nicht enthalten

Abb. 5: Quadratische Distanzfunktion

2.2 Datentypabhängige Ähnlichkeitssuche

Je nach Art des Multimedia-Objektes und dessen charakterisierenden Merkmalen können verschiedene Vorgehensweisen zur Ähnlichkeitssuche angewandt werden. Im Folgenden werden mögliche Ähnlichkeitsmodelle für Sequenzdaten, Bilder und 3D-Daten vorgestellt.

Sequenzdaten bezeichnen die Abbildung einer Indexmenge {1, … ,n} in einen gewissen Wertebereich. Anhand des Wertebereiches kann zwischen nominalen Sequenzdaten, wie z.B. DNA-Sequenzen, und kontinuierlichen Sequenzdaten, wie z.B. Aktienkurse, unterschieden werden. Je nach Länge der Sequenzen können sich verschiedene Anfragen ergeben. So könnte man bei einer Vollsequenzsuche alle Aktien mit einem ähnlichen Kursverlauf ermitteln wollen oder für Teilsequenzen alle Firmen ausfindig machen, die eine ähnliche Umsatzbilanz für die letzten zwei Monate aufweisen.

Die Umsetzung solch einer Anfrage basiert auf der Diskreten Fourier Transformation. Sie kann die Sequenzen vom Zeitbereich in den Frequenzbereich abbilden. In der Praxis enthalten die tiefsten Frequenzen die größte Bedeutung weshalb die hohen Sequenzen gekürzt werden dürfen. Die Anwendung der Diskreten Fourier Transformation auf gekürzte Sequenzen kann also lange Zeitreihen durch kurze Sequenzen von Frequenzen darstellen. Die Abbildung hochdimensionaler Sequenzen auf niedrigdimensionale Frequenzen ermöglicht nach dem Satz von Parseval die Distanzen im Frequenzraum anstatt im Zeitbereich zu berechnen. Parseval bewies, dass die Energie eines Signals im Zeitbereich mit der Energie des Signals im Frequenzbereich übereinstimmt, wodurch auch die euklidische Distanz im Zeit- und Frequenzbereich identisch ist.

Bei der Teilsequenzsuche wird über jede Sequenz eine Art Fenster geschoben. An jeder Fensterposition wird die sichtbare Teilsequenz mit der Diskreten Fourier Transformation kodiert und ergibt einen Featurepunkt im Frequenzraum. Über diesen Featurepunkten kann dann eine Suche gestartet oder Distanzen berechnet werden.

Bei Bildern können verschiedene Parameter wie z.B. Farbe, Farbverteilungen, Farbkomposition, Formen oder Texturen zur inhaltsbasierten Suche verwendet werden. Eine häufig verwendete Methode ist die Ähnlichkeitssuche über Farbhistogramme. Für jedes Bild wird also die Häufigkeit der auftretenden Pixelfarben in einem Histogramm festgehalten. Die Histogramme können mittels einer Distanzfunktion, wie z.B. der euklidischen Distanz, auf Ähnlichkeit untersucht werden. Idealerweise werden quadratische Distanzfunktionen eingesetzt, da sie Querbezüge der einzelnen Dimensionen berücksichtigen können, indem sie individuell anpassbare Ähnlichkeitsmatrizen benutzen. So können Ergebnisse aus der

Wahrnehmungsforschung benutzt werden, um Farben als ähnlich zu bewerten, die vom menschlichen Auge ebenfalls als ähnlich betrachtet werden.

Eine andere Methode ist die formbasierte Ähnlichkeitssuche. Hier werden zu einem Anfragebild die jeweiligen Differenzen zu den Ergebnisbildern und die Distanzwerte berechnet.

Bei der Suche nach ähnlichen Formen im 3D-Raum können Formhistogramme verwendet werden. Dabei sind die 3D-Objekte wie Moleküle oder CAD-Zeichnungen als eine Menge von Oberflächenpunkten zu verstehen. Nach verschiedenen Partitionierungsstrategien kann der 3D-Raum in Zellen aufgeteilt werden und das Vorkommen der Oberflächenpunkte pro Zelle in einem Histogramm abgebildet werden. Die Ähnlichkeitsmatrix beschreibt dann die Ähnlichkeit der einzelnen Zellen der Raumpartitionierung.2

2.3 Ähnlichkeitssuche über Videodaten

Da Videodaten nichts anderes sind als kurz aufeinanderfolgende Einzelbilder kommen auch bei Videostreams Parameter aus dem Ähnlichkeitsmodell von Bildern in Frage. Ebenso wie bei Bildern kann über Farbe, Formen oder Texturen versucht werden, Distanzen und Ähnlichkeiten zu berechnen. Problematisch ist die Menge der auflaufenden Daten, insbesondere bei hohen Auflösungen und hohen Frameraten. Diese Menge gilt es zu reduzieren und wenn möglich die technische Vorgehensweise der Videokompression (siehe Kapitel 3) dabei auszunutzen. Diese basiert im Wesentlichen darauf nur sich verändernde Inhalte zu kodieren und Redundanzen von Frame zu Frame zu reduzieren. Deshalb empfiehlt sich die Verwendung der bereits zur Videokodierung verwendeten und existierenden Bewegungsvektoren, denn sie enthalten nur einen Wert, wenn sich die Region des Bildes im Videoverlauf auch tatsächlich geändert hat. Somit können mit einem Bruchteil aller Informationen dennoch die meisten relevanten Änderungen untersucht werden.

In dieser Arbeit werden aus den extrahierten Vektoren mit einer mathematischen Funktion die entsprechenden Winkel berechnet. Jeder Makroblock besitzt Bewegungsvektoren bzw. bewegt sich in einem bestimmten Winkel weiter. Die Häufigkeiten dieser Bewegungen in eine Richtung und in einem gewissen Winkelgrad können in einem Winkelhistogramm festgehalten werden. Mit Distanzfunktionen können die Winkelhistogramme dann auf Ähnlichkeiten untersucht werden. In der Praxis könnte man diese Art der Ähnlichkeitssuche dazu verwenden, um Videos mit ähnlichen Bewegungen oder identischen Bewegungsabläufen aufzuspüren. In einer Multimediadatenbank mit Sportvideos könnten z.B. als Ergebnis auf die Anfrage „Liefere mir alle Videosequenzen aus der Datenbank, die ähnlich zu dieser Fussballszene sind“ Videos mit ähnlichem Bewegungsablauf geliefert werden. Die Wahrscheinlichkeit, dass bei einer gesuchten Strafstosssituation auch Sequenzen mit Strafstosssituationen gefunden werden, ist aufgrund des typischen Bewegungsprofils der Szene sehr wahrscheinlich. Schwer zu finden wären eventuell untypische Bewegungsabläufe oder Situationen, in denen gar keine Bewegung stattfindet.

3 Videogrundlagen

3.1 Videokompression

Im Zuge immer höherer Auflösungen und besserer Videoqualität steigen auch die Anforderungen an Speicherkapazität und Bandbreite zur Übertragung der gewachsenen Datenmenge. Umso wichtiger ist daher eine Videokompression, die eine hohe Videoqualität garantiert und gleichzeitig die Datenmenge auf das Nötigste reduziert. In den meisten

modernen Videocodecs (z.B. MPEG-4) ist das Prinzip der Bewegungskompensation (motion compensation) und der Bewegungsschätzung (motion estimation) integriert. Das Grundprinzip dieser Verfahren basiert darauf, dass nicht jedes einzelne Frame eines Videos komplett codiert wird, sondern nur die Veränderungen zum jeweiligen Vor- oder Nachfolgerframe. Durch die Tatsache, dass in Videos in der Regel nur einzelne Bereiche bewegungsaktiv sind (z.B. ein Objekt bewegt sich vor gleich bleibendem Hintergrund), können erstaunlich hohe Kompressionsraten bei fast identischer Qualität erreicht werden.

3.1.1 Bewegungskompensation (motion compensation)

Bewegungskompensation beschreibt die Technik zur Beseitigung von temporaler Redundanz in Video-Sequenzen. Zwei aufeinander folgende Frames einer Sequenz ähneln sich sehr stark, sie enthalten somit viel (temporal) redundante Informationen, die nicht mit jedem Frame neu abgespeichert werden müssen.

Abbildung in dieser Leseprobe nicht enthalten

Abb. 6: Zeitliche Redundanz

(Baum ist zeitlich redundant und muss nicht neu codiert werden)

Bewegungskompensation berücksichtigt für die Redundanzreduktion daher nur die Veränderungen in den Bewegungen einzelner, gleicher Framekomponenten. Im Schritt der Bewegungsschätzung werden diese Veränderungen in Form von Bewegungsvektoren ermittelt. Die Bewegungsschätzung bildet mittels dem Frame im Videospeicher und dem aktuellen Frame (Bild N+1) die Bewegungsvektoren und liefert diese an die Bewegungskompensation. Diese setzt mittels des Frames im Videospeicher und den ihr gegebenen Vektoren das Frame zusammen. Letztendlich wird eine Differenz zwischen dem aktuellen und dem zusammengesetzten Frame gebildet, um dann kodiert und effizient übertragen werden zu können.

Wird die Bildinformation eines aktuellen Frames durch einen Vergleich mit einem vorherigen Referenzframe über die Bestimmung der Bewegungsvektoren festgehalten, so ist das Resultat ein P-Frame. Werden auch Informationen aus einem folgenden Frame zur Kodierung des aktuellen Frames benutzt, entsteht ein bidirektional kodiertes B-Frame. In gewissen Abständen wird ein Frame wieder vollständig kodiert (I-Frame) und die nächsten Frames beziehen sich dann darauf. Bei MPEG-4 ist die Reihenfolge abhängig vom verwendeten Codec und folgt meist dem Schema: IFrame/ P-Frame/ B-Frame .. BFrame/ P-Frame/ IFrame/.

[...]