path: root/doc/documentation.txt

= Automatisierte Erkennung von Werbeblöcken
:author: Jan Klemkow, Benjamin Franzke
:lang: de
:imagesdir: image

== Einleitung

Werbung in Fernsehübertragungen sind für den Zuschauer lästige
Unterbrechungen.
Bei Aufzeichnungen von Sendungen stört Werbung nicht nur beim späteren
Schauen, es belegt auch einen nicht unwesentlichen Teil des Aufnahmemediums.
Tobias Kramer hat 1995 wohl als erster mit dem Thema auseinandergesetzt und mit
seiner Erfindung am Jugendforscht-Wettbewerb teilgenommen.

.Reklame ade -- Der Videorekorder, der Werbung erkennt
____
Über Werbeblocks in aufgezeichneten Spielfilmen ärgert sich Tobias Kramer schon
lange.  Der 19-Jährige griff jetzt zur Selbsthilfe und baute ein elektronisches
Gerät, das -- zwischen Fernseher und Videorekorder geschaltet -- bei den
Aufnahmen den Rekorder stoppt, sobald die Reklame beginnt.  Herzstück ist eine
Elektronik, die die linke obere Ecke des Fernsehbildes, in der das Senderlogo
den Beginn der Werbeunterbrechung markiert, digitalisiert.  Byte für Byte wird
dieses Signal mit dem aktuellen Videosignal verglichen, das Gerät erkennt so
Beginn und Ende des Werbeteils.
____
Seither gab es eine Reihe weitere Arbeiten in diesem Umfeld.
Einige dieser Lösungen sind in das VDR-Projekt (Video Disk Recorder) integriert
worden.
Eine vorausgegangene Arbeiten zu diesem Thema ist unter anderem eine Studienarbeit
von Andreas Regel zum Thema ``Entwicklung und Implementierung von Methoden zur
Erkennung von Werbeblöcken im digitalen Fernsehen''.
//In dieser Arbeit von 2003 wird ein Verfahren beschrieben.

== Grundladen

=== Methoden zur automatischen Erkennung von Werbungsendungen

Es gibt einige Indikatoren zur Erkennung von Werbung.
Das auffälligste ist das Senderlogo, welches in Produktwerbung nicht
eingeblendet wird.
Eine Ausnahme ist hier die Eigenwerbung der Sender.
Wirbt ein Sender am Ende eines Werbeblocks für eigene Sendungen,
Internetangebote oder andere eigene Produkte, wird das Senderlogo mit
eingeblendet.

Ein weiterer Indikator ist das Seitenverhältnis.
Werbung wird heutzutage fast ausschließlich im Seitenverhältnis 16:9
ausgestrahlt.
Fernsehproduktionen werden ebenfalls in diesem Format ausgestrahlt, aber Filme,
welche für das Kino produziert haben, verwenden anderen Formate (z.B. 21:9).
Alte Fernsehsendungen welche noch im Format 4:3 Produziert wurden werden heute
Teilweise auch noch in diesem ausgestrahlt.
Beim Wechsel von Film zur Werbung findet dann auch ein Wechsel des
Seitenverhältnisses statt.
Gut zu Erkennen Anhand der veränderten schwarzen Balken im Bild Oben und Unten,
sowie auch Links und Recht beim 4:3 Seitenverhältnis.

Die Tonspur erlaubt in einigen Fällen ebenfalls das Erkennen von
Werbeblöcken.
So wird Fernsehwerbung in der Regel in Stereo ausgestrahlt.
Viele Kinofilme hingegen verwenden Mehrkanal-Tonspuren.
Ein weiteres Beispiel sind ältere Filme, welche nur mit einer Monotone-Tonspur
produziert wurden.

=== Video-Bibliothek-libav

Für das verarbeiten von Videos wird in dieser Arbeit die in der
Programmiersprache ``C'' geschriebenen Bibliothek ``libav'' (audio/video library)
verwendet.
Da die Bibliothek sehr Low-Level angelegt und somit für etwas unhandlich ist,
wurde im Rahmen dieser Arbeit eine Abstraktionsschicht dafür entwickelt.
Diese ermöglicht den Programmen, welche im Folgenden beschrieben
werden, einen einfachen Zugriff auf Videodaten.

In der Initialisierungsfunktion wird ein Objekt zu Video-Dekodierung durch
Übergabe eines Dateipfades zu einem Video erstellt, aus dem nun jedes Bild
einzeln extrahiert werden kann. Dies enthält die eigentlichen Daten, Breite,
Höhe, Stride und aktuellen Zeitpunkt.
Desweiteren bietet die Abstraktion die Möglichkeit zu einem bestimmten Zeitpunkt
zu springen, dabei muss aber berücksichtigt werden, dass nur direkt zu Keyframes
gesprungen werden kann und somit der tatsächliche Sprungpunkt zeitlich früher
liegen kann, als der angefragte.

== Schnitt Erkennung

Zur Erkennung von Schnitten in Videoaufzeichnungen wurde im Rahmen dieser
Arbeit ein Verfahren entwickelt.

Der erste Ansatz bestand in der Annahme, dass sich die durchschnittliche
Helligkeit des Bildes während einer Szene nicht stark verändert.
Aus diesem Grund wurde ein Algorithmus implementiert, welcher für jeden
Frame die durchschnittlichen Y-Wert berechnet.

.Durchschnittlicher Y-Wert über das Heute-100sec-Video
image::avg.svg[]

Dabei wird eine Video, Frame für Frame durchlaufen und zwischen jeweils zwei
aufeinander folgender Frames eine durchschnittliche Pixeldifferenz berechnet.
Die Pixeldifferenz wird ausschließlich anhand des Y-Kanals berechnet.

.Frame-Differenzwerte innerhalb des Heute-100sec-Videos
image::cuts.svg[]

Bei Betrachtung des Graphen, welcher aus diesen Werten entsteht, lassen sich
Schnitte gut anhand der Peeks erkennen.
Da diese Peeks allerdings nicht immer die gleiche Amplitude und auch
andere Wertebereiche haben, kann es sein, dass Bereiche in denen kein Schnitt
vorhanden ist, trotzdem die gleiche Amplitude ergeben, wie andere Peeks,
sodass anhand dieser Werte, Schnitte nicht automatisiert erkannt werden können.
Aus diesem Grund muss über diese Reihe von Werten noch der Anstieg berechnet
werden, welcher zu folgendem Graphen führt.

.Anstieg der Differenzwerte des Heute-100sec-Videos
image::cuts_diff.svg[]

Bei der nun entstehenden Wertereihe lassen sich mit einem Schwellwert
automatisiert und zuverlässig Schnitte erkennen.
Dieses Verfahren wurden im Rahmen dieser Arbeit in dem Programm ``cuttime''
implementiert.
Es analysiert eine Video-Datei und gibt zu jedem erkannten Schnitt dessen
Zeitstempel innerhalb des Videos aus.
Diese Zeitstempel können dann dazu genutzt werden, Verfahren wie die
automatische Senderlogo-Erkennung zu unterstützen.
Sollte ein Logo innerhalb eines Schnittes erst eingeblendet werden, so kann man
den Schnittpunkt auf den Anfang des Schnittes legen, um so beim automatischen
Schneiden, nicht mehr Informationen zu verlieren, als nötig.
Zudem können die Zeitstempel mit dem Shell-Script ``cutting.sh'' dazu genutzt
werden, um eine Video-Datei einzelne Schnitte aufzuteilen.
Innerhalb des Shell-Scripts wird die Ausgabe von ``cuttime'' als Parameter für
das Programm ``ffmpeg'' verwendet.

.Einen Schnitt mittels ffmpeg extrahieren
[source,sh]
----
ffmpeg -i INPUT_VIDEO -ss START_ZEIT -t DAUER OUTPUT_VIDEO
----

== Erkennung von Überlappungen

Ein verbreitetes Phänomen ist, nach einem Werbeblock einige Sekunden des Films
von vor dem Werbeblock zu wieder holen.
Schneidet man nun die Werbung heraus, erhält das resultierende Video eine
Wiederholung von einigen Sekunden.
Ähnlich dem Springen eines Schallplattenspielers.
Um diesem Problem zu begegnen wurde das Programm +overlap+ entwickelt.
Dieses Programm vergleicht den letzten Frame eines Videos mit allen Frames
vom Anfang eines anderen Videos.
Ausgegeben wird der Zeitpunkt des Frames mit der größten Übereinstimmung.
Ab diesem Zeitpunkt fährt der Film dann ohne einen störenden Übergang fort.

.Last-Frame-Differenz von Video-1 über Video-2
image::overlap.svg[]

Der obere Graph zeigt, die Differenz des letzten Frames von Video-1 über
die erste Minute von Video-2.
Dabei wird nach ca. sechs Sekunden der kleinste Wert ermittelt.
Dieses Minimum ist auch genau der Punkt, an dem die Überlappung endet.
Beim Zusammenschneiden der beiden Videoteile können also von Video-2 die ersten
sechs Sekunden übersprungen werden.

== Entfernen bekannter Szenen

Eine semiautomatische Methode Werbung aus Aufzeichnungen zu entfernen ist es
bekannte Werbeszenen zu sammeln und diese gezielt heraus zu schneiden.
Für dieses Lösungsansatz wurde das Programm ``findcut'' im Rahmen dieser
Arbeit implementiert.

.Ubereinstimmungen einer Szene innerhalb des Heute-100sec-Videos
image::findcut.svg[]

Die fünf negativen Peeks zeigen jeweils die Zeitpunkte, zu denen die gesuchte
Szene beginnt.
Zusammen mit den Informationen über die Länge der Schnitte auf dem Programm
``cuttime'' können diese nun automatisch entfernt werden.

Das Shell-Script ``cutint.sh'' kann mit den Daten der vorherigen Programm,
ein Video neu zusammenstellen und dabei ungewollte Szenen herrauslassen.
Dabei werden die gewollten Szenen in einzelne temporäre Video-Dateien
geschrieben.
Später werden dann alle Szenen zu einem Video wieder zusammen gefasst.
Dies ist nun von allen ungebliebten Szenen befreit.

.Einen Schnitt mittels ffmpeg extrahieren
[source,sh]
----
cutint.sh VIDEO OUTPUT 00:00:00.000 00:02:12:050 00:05:00:000 00:03:00.000
----

Der Obere Befehl extrahiert aus dem Ursprungsvideo die ersten zwei Minuten und 12
Sekunden zusammen mit den letzten 3 Minuten heraus und erstellt damit ein neues
Video.

== Fazit

Eine vollkommen automatischer Algorithmus zum Unterscheiden von Werbung oder
Sendungen ist nicht möglich.
Es lassen sich Werbeblöcke jeweils nur Anhand von Indizien erkennen.
Diese Indizien sind unzureichend genau, um mittels eines automatischen
Verfahrens den Beginn und das Ende eines Werbeblocks zu erkennen. 
Allerdings lassen sich mit semiautomatischen Verfahren das Herausschneiden von
Werbung für den Benutzer wesentlich vereinfachen.

== Literatur

* Thorsten Janke and Markus Koppers, ``Optimierung und Implementierung
  eines Systems zur Unterdrückung von Werbeblöcken bei Aufzeichnungen
  mit dem Videorecorder'', September 1999.
* Andreas Regel, ``Entwicklung und Implementierung von Methoden zur
  Erkennung von Werbeblöcken im digitalen Fernsehen'', 2003
* Beschreibung des Programms ``noad'' im VDR-Wiki, +
  http://www.vdr-wiki.de/wiki/index.php/Noad
* Homepage des noad-Projektes, http://noad.net23.net/
* Jugend-Forscht-Projekt von Tobias Kramer, +
  http://www.jugend-forscht.de/projektdatenbank/der-videorekorder-der-werbung-erkennt/1995/6/Bayern.html

// vim: ft=asciidoc textwidth=80: