Schnitterkennung
Als Schnitterkennung bezeichnet man im Fachgebiet Multimediatechnik der Informatik das automatische Erkennen von Schnitten in einem digitalen Video.
Anwendungszweck
Schnitterkennung ist ein nützliches Hilfsmittel bei der Nachbearbeitung von Filmmaterial am Computer, denn sie erspart dem Anwender das zeitraubende Suchen nach Schnitten von Hand. Die Schnitterkennung bildet aber auch einen der Grundpfeiler der automatischen Archivierung von Videomaterial. Ziel dabei ist es, für große Videoarchive automatisch Indexe anzufertigen; die Schnitterkennung kann hier sowohl bei der Klassifizierung eines Videos als auch bei der Auswahl von Vorschaubildern helfen.
Harte und weiche Schnitte
In der Schnitterkennung unterscheidet man harte Schnitte (engl. hard cut, in der Filmkunst „Schnitt“ genannt) und weiche Schnitte (engl. soft cut, in der Filmkunst „Blende“ genannt). Bei einem harten Schnitt geht eine Filmszene plötzlich und übergangslos in eine andere über. Im Gegensatz dazu geht bei einem weichen Schnitt eine Szene allmählich in eine andere über.
Während bei harten Schnitten mit modernen Algorithmen zur Schnitterkennung ausgezeichnete Ergebnisse erzielt werden, stellen weiche Schnitte nach wie vor eine Herausforderung dar. Der ruckhafte Wechsel des gesamten Bildinhalts bei einem harten Schnitt ist bereits mit recht einfachen Methoden der Bildverarbeitung – siehe z. B. „Histogramm-Differenzen“ unter Verfahren – gut erkennbar. Die allmähliche Veränderung des Bildinhalts bei einem weichen Schnitt wird von bisherigen Algorithmen aber recht häufig als Bewegung der gefilmten Objekte fehlinterpretiert und der Schnitt deswegen nicht erkannt.
Verfahren
Verfahren zur Schnitterkennung arbeiten nach einem zweistufigen Prinzip:
- Bewertung. Alle Bilder des digitalen Videos werden mit dem direkt nachfolgenden Bild verglichen. Dabei wird jedem Bilderpaar ein Wert zugewiesen, der möglichst hoch sein sollte, wenn vermutlich ein Schnitt vorliegt, und möglichst niedrig, wenn vermutlich kein Schnitt vorliegt.
- Filterung. Anschließend werden alle Bilderpaare mit einem Schwellenwert gefiltert (auch „Schwelle“ oder „Grenzwert“, engl. threshold). Dabei werden alle Bilderpaare aussortiert, deren Wert unter der Schwelle liegt. Zwischen den jeweils zwei Bildern der verbliebenen Bilderpaare liegt vermutlich ein Schnitt.
Diese Vorgehensweise ist anfällig für Fehler. Da bereits geringfügige Schwellenüberschreitungen als Schnitt interpretiert werden, muss die Schwelle sehr sorgfältig gewählt werden. In der Regel wird ihr Wert mit statistisches Methoden aus einer großen Anzahl von Testläufen ermittelt.
Ein Verfahren zur Schnitterkennung besteht somit aus zwei Teilen, die unabhängig voneinander optimiert werden können. Die Bewertung sollte so optimiert werden, dass sie die Werte möglichst weit streut, also der Unterschied zwischen den Werten für Schnitt und Nicht-Schnitt möglichst groß ist. Die Filterung kann toleranter gestaltet werden, so dass weiche Schnitte nicht als mehrere Schnitte hintereinander fehlgedeutet werden.
Bewertungsverfahren
Die Optimierung der Bewertung ist keine einfache Aufgabe. Bis heute wurden zahlreiche Algorithmen entwickelt, die mehr oder weniger zuverlässige Ergebnisse liefern.
Die Summe der absoluten Differenzen (SAD) ist der wohl offensichtlichste Ansatz zur Ermittlung des Unterschiedes zweier Bilder: Die Farbwerte der Bilder werden Bildpunkt für Bildpunkt voneinander abgezogen und betragsweise aufsummiert. Das Ergebnis ist die SAD, eine positive Zahl, die angibt, wie stark sich die Bildpunkte der Bilder insgesamt voneinander unterscheiden. Die SAD reagiert bereits auf kleine Änderungen des Bildinhaltes sehr empfindlich und vermutet daher oftmals Schnitte, wo in Wirklichkeit keine vorliegen; besonders häufig werden schnelle Kamerafahrten, Explosionen oder das Anschalten eines Lichts in einer zuvor dunklen Szene falsch ausgelegt. Andererseits reagiert die SAD auf die meisten weichen Schnitte überhaupt nicht, da die Änderungen zu langsam voranschreiten und den Wert nicht stark genug anheben. Dass das Verfahren trotzdem häufig angewandt wird, verdankt es der Tatsache, dass es alle sichtbaren harten Schnitte mit absoluter Sicherheit erkennt und darüber hinaus auch noch sehr schnell ist.
Die Histogramm-Differenz (HD) ist eine geringfügige Veränderung der Summe der absoluten Differenzen. Anstatt die Bilder Punkt für Punkt miteinander zu vergleichen, werden stattdessen die Histogramme der beiden Bilder miteinander verglichen. Ein Histogramm enthält für jede Farbe eines Bildes die Anzahl der Bildpunkte, die diese Farbe haben. Die Histogramm-Differenz untersucht also nicht direkt, wie sehr sich die Bildinhalte voneinander unterscheiden, sondern wie sehr sich die Farben der beiden Bilder unterschieden. Dies kann zum Manko werden, denn es ist durchaus möglich, dass zwei völlig verschiedene Bilder identische Histogramme haben – man denke etwa an ein Bild mit Meer und Strand und eines mit Getreidefeld und Himmel. Es gibt daher keine Garantie, dass harte Schnitte mit Sicherheit erkannt werden. Andererseits ist die Histogramm-Differenz aber weniger anfällig für kleinere Veränderungen des Bildinhaltes, wie Bewegung und Kamerafahrt.
Die Edge Change Ratio (ECR, engl. „Kantenänderungsverhältnis“) versucht, den tatsächlichen Bildinhalt zweier Bilder miteinander zu vergleichen. Dazu werden zunächst die Umrisse aller Objekte in den beiden Bildern gesucht und sogenannte Kantenbilder erzeugt. Anschließend werden die beiden Kantenbilder miteinander verglichen und der Anteil der Kanten ermittelt, der aus dem ersten Bild verschwindet und der Anteil, der im zweiten Bild dazukommt; es soll also bestimmt werden, wie stark sich die abgebildeten Objekte in den beiden Bildern unterscheiden. Die Edge Change Ratio ist einer der zuverlässigsten Indikatoren für das Auftreten eines Schnitts. Sie reagiert empfindlich auf harte Schnitte und ist in der Lage, einige Formen von weichen Schnitten mit großer Sicherheit zu bestimmen. Dennoch stößt auch die Edge Change Ratio an ihre Grenzen, wenn es um die Erkennung von Trickblenden – z. B. schwarze Balken, die das Bild „wegwischen“ – geht.
Eine weitere Möglichkeit bietet sich mit der Kombination verschiedener Verfahren.
Filterungsverfahren
Die einfache Schwellenwert-Filterung kann erweitert werden, um mehrere eng beieinander liegende Überschreitungen des Schwellenwertes zu einer einzelnen Überschreitung zusammenzufassen. Dazu wählt man sich einen Mindestabstand, den zwei Überschreitungen voneinander haben müssen, um als zwei einzelne Schnitte interpretiert zu werden und wählt innerhalb eines solchen Rahmenbereichs immer nur eine Überschreitung – in der Regel diejenige mit dem höchsten Wert – aus.
Qualitätsmaße
Es gibt drei Maße, die zur Beurteilung der Qualität von Schnitterkennungsverfahren verwendet werden. Bezeichnet C die Anzahl der korrekt erkannten Schnitte, M die Anzahl der nicht erkannten Schnitte und F die Anzahl der falsch erkannten Schnitte, so ergeben sich für die Qualitätsmaße folgende Formeln:
- Precision. Die Wahrscheinlichkeit, mit der ein erkannter Schnitt wirklich ein Schnitt ist.
- Recall. Die Wahrscheinlichkeit, mit der ein echter Schnitt erkannt wird.
- F1. Eine Kombination der anderen beiden Qualitätsmaße, die nur dann hohe Werte ergibt, wenn sowohl Precision als auch Recall hohe Werte aufweisen.
Die Qualitätsmaße nehmen als echte mathematische Maße nur Werte zwischen 0 und 1 an, für alle drei gilt: Je höher der Wert, desto besser das Verfahren.
Literatur
- R. Steinmetz: Multimedia-Technologie. Springer, Berlin, Juli 2000. ISBN 3-540-67332-6.