Edge Change Ratio

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 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 dazugehö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 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:

$\mathrm {ECF} =\max(\rho _{\text{in}},\rho _{\text{out}})$

wobei $\rho _{\text{in}}$ die Anzahl der Kantenpixel ist, die im zweiten Bild hinzu kommen und $\rho _{\text{out}}$ die Anzahl der Kantenpixel, die aus dem ersten Bild verschwinden.

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

$\mathrm {ECR} _{\text{i}}=\max \left({\frac {\rho _{\text{in}}}{s_{\text{i}}}},{\frac {\rho _{\text{out}}}{s_{\text{i}}+1}}\right)$

wobei $s_{\text{i}}$ die Anzahl aller Kantenpixel im ersten Bild und $s_{\text{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 Grauwertbilder 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 AND-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_{\text{ein}}$ der eintretenden Kantenpixel und die Anzahl $E_{\text{aus}}$ der austretenden Kantenpixel.
5. $E_{\text{aus}}$ wird durch die Anzahl der Kantenpixel im Kantenbild A' geteilt, $E_{\text{ein}}$ durch die Anzahl der Kantenpixel im Kantenbild B'. Das Ergebnis ist das Kanteneintrittsverhältnis $\rho _{\text{out}}$ und das Kantenaustrittsverhältnis $\rho _{\text{in}}$.
6. Das Maximum der Werte $\rho _{\text{out}}$ und $\rho _{\text{in}}$ entspricht der ECF.

Kantenbilder

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.