Edge Change Fraction

Die Edge Change Ratio (Abkürzung ECR, englisch für „Kantenänderungsverhältnis“) ist ein Maß, das die Unterschiedlichkeit zweier aufeinanderfolgender Bilder in einem digitalen Video misst und von Algorithmen zur Schnitterkennung verwendet wird. Gelegentlich wird auch ein solcher Algorithmus selbst als Edge Change Ratio bezeichnet.

Entwicklung

Die ursprüngliche Idee für die ECR stammt von Mitarbeitern der Dublin City University in Irland, die 1998 in [1] das Maß Edge Change Fraction (Abkürzung ECF, englisch für „Kantenänderungsbruch“) zur Erkennung und Klassifizierung von Szenenübergängen in digitalem Videomaterial und einen dazu gehörigen Algorithmus vorstellten. Es folgten Arbeiten weiterer Forscher mit dem Ziel, den ursprünglichen Algorithmus zu verbessern; so stellten beispielsweise Mitarbeiter der Cornell University in Ithaca (USA) 1999 in [2] einen Algorithmus vor, der zusätzlich die Kamerabewegung kompensiert und durch Einbindung der Hausdorff-Distanz Szenenübergänge zuverlässiger erkennen kann.

Mathematische Definition

Die Edge Change Fraction ist definiert als:

ECF = max(rho_in, rho_out)

wobei rho_in die Anzahl der Kantenpixel ist, die im zweiten Bild hinzu kommen und rho_out die Anzahl der Kantenpixel, die aus dem ersten Bild verschwinden.

Die ECR verändert diese Definition geringfügig zu:

ECR_i = max(rho_in / s_i, rho_out / s_i+1)

wobei s_i die Anzahl aller Kantenpixel im ersten Bild und s_i+1 die Anzahl aller Kantenpixel im zweiten Bild bezeichnet.

Funktionsweise der Algorithmen

Edge Change Ratio ermittelt für je zwei aufeinanderfolgende Bilder den Anteil der „fernen“ verschwindenden und der erscheinenden Kanten.

1. Zwei aufeinanderfolgende Bilder des digitalen Videos werden ausgewählt und vorbereitet:
   1. Die Bilder werden in Grauwert-Bilder konvertiert; für die weitere Bearbeitung ist nur die Helligkeit der Bildpunkte von Bedeutung. So wird der Speicherbedarf gesenkt und die Bearbeitungszeit verkürzt.
   2. Neuere Algorithmen führen zusätzlich eine Kompensation der Kamerabewegung durch. Durch Berechnung des durchschnittlichen Bewegungsvektors (motion vector) wird die wahrscheinlichste Kamerabewegung ermittelt. Anschließend werden diejenigen Randbereiche, die das Bild aufgrund der vermuteten Kamerabewegung verlassen oder betreten, weggeschnitten.
2. A und B werden zu (monochromen) Kantenbildern A' und B' umgewandelt. Die Umwandlung erfolgt in der Regel durch Filterung mit einem Hochbandfilter.
   1. Zusätzlich zum Hochbandfilter verwenden einige Algorithmen weitere Algorithmen, die eventuelles Rauschen unterdrücken sollen.
3. Aus A' und B' werden die dilatierten Bilder A* und B* berechnet. Die Dilatation verbreitert die sichtbaren Umrisse. Der optimale Wert für den Parameter der Dilatation wird durch empirische Versuchsreihen ermittelt.
4. A* und eine invertierte Version des Bildes B' werden XOR-verknüpft, ebenso B* und eine invertierte Version des Bildes A'. In den so entstehenden Bildern A und B wird jeweils die Anzahl aller gefärbten Pixel gezählt. Das Ergebnis sind zwei Zahlen, die Anzahl E_ein der eintretenden Kantenpixel und die Anzahl E_aus der austretenden Kantenpixel.
5. E_aus wird durch die Anzahl der Kantenpixel im Kantenbild A' geteilt, E_ein durch die Anzahl der Kantenpixel im Kantenbild B'. Das Ergebnis ist das Kanteneintrittsverhältnis rho_aus und das Kantenaustrittsverhältnis rho_ein.
6. Das Maximum der Werte rho_aus und rho_ein entspricht der ECF.

1. Kantenbilder

Bild 1. Das Ursprungsbild, ein Ferrari 360.

Der wichtigste Schritt zur Bestimmung der ECR zweier Bilder ist das Erstellen von Kantenbildern. Ein „gutes“ Kantenbild ist ein zweifarbiges Bild, das nicht mehr und nicht weniger als die Umrisse aller Objekte im Ursprungsbild enthält. Ausgangsbasis zur Erstellung von Kantenbildern sind die unter Kantendetektion beschriebenen mathematischen Filter. Prinzipiell ermitteln diese, wie stark die Farbwerte zweier benachbarter Bildpunkte voneinander abweichen und zeichnen die Stärke dieser Abweichung in ein Grauwertbild ein (siehe Bild 2).

Bild 2. Das Ursprungsbild wurde mit einem Hochpassfilter gefiltert; nur eine von mehreren Möglichkeiten, um die Kanten zu ermitteln. Die ermittelten Kanten sind in der verkleinerten Darstellung kaum erkennbar; klicken Sie auf das Bild um es in Originalgröße zu betrachten.

Quellen

• [1] Aidan Totterdell: An Algorithm for Detecting and Classifying Scene Breaks in MPEG Video Bit Streams. School of Computer Applications, Dublin City University. Technical report [98-05], 21 September 1998
• [2] Ramin Zabih, Justin Miller, Kevin Mai: A feature-based algorithm for detecting and classifying production effects. In: Multimedia Systems Vol. 7, S. 119-128, Springer-Verlag 1999