His­to­gr­amm­bas­ierte Sze­nen-Er­ken­nung für Vi­deos

Einführung: Wie der Algorithmus funktioniert

Der Algorithmus arbeitet auf sog. Farb-Histogrammen, welche die Anzahl an Pixel mit einer gewissen rot, grün- und blau-Intensität zählen. Digitalkameras zeigen oft Helligkeits-Histogramme an um eine optimale Belichtung aussuchen zu können. Die einfachste Möglichkeit ist es für den Vergleich der Histogramme zweier aufeinanderfolgender Bilder einfach die Anzahl an Pixeln für eine gewisse Intensität an derselben Stelle voneinander abzuziehen. Das tragt aber dem Umstand, daß Differenzen für Zahlwerte ähnlicher Intensitäten sich ausgleichen können, keine Rechnung.

Einen Ausgleich zwischen ähnlichen Intensitätswerten für Pixel kann man nun durch eine gewichtete Durchschnittsbildung schaffen. Statt individuelle Intensitätswerte voneinander abzuziehen kann man den Durchschnitt einer ganzen Region voneinander abziehen. Intensitätswerte in der Nähe des fraglichen Pixels werden dabei stätker einbezogen, wobei die Gewichtungen rund um diesen Intensitätswert die Form eines Halbkreises annehmen.

Das alleine wäre aber noch recht ineffizient, da dabei viele ähnliche Werte des einen Bildes von vielen ähnlichen Werten des anderen Bildes abezogen würden. Der Algorithmus läßt sich dadurch verbessern, indem man den genauen Intensitätswert des einen Bildes vom Durchschnitt an derselben Stelle des anderen Bildes abzieht. Das wird kreuzweise gemacht und dann wird das Maximum der beiden Werte genommen.

Damit nun steile Kanten im Histogramm nicht einen von Haus aus zu großen Einfluß auf das Endergebnis haben wird von diesem kreuzweisen Differenzwert noch einmal das Maximum der Eigenvarianzen beider Bilder abgezogen. Unter Eigenvarianz versteht man hier die Differenz eines Intensitätswertes von dem gewichteten Durchschnitt seiner Umgebung.

Es gäbe sicher noch viele Dinge, die man am Algorithmus verbessern könnte. Beispielsweise könnte man statt die Differenzwerte des rot-, grün und blau-Histogramms einfach zu addieren von Haus aus ein dreidimensionales Histogramm schaffen. Eine andere Idee wäre statt nur Farbwerte herzunhemen auch Kanten über einen Convolution-Filter in die Szenenwechsel-Erkennung miteinzubeziehen. - oder man gewichtet solche Deskriptoren nach der Bildregion, in der sie vorkommen. Trotz allem funktioniert der hier vorgestellte Algorithmus gut genug für den praktischen Einsatz.

Etwas gewöhnungsbedürftig ist wohl die Implementierung in Javascript, welche eine Vorgabe dieses Lehrver­anstaltungs­projektes war. Das Problem mit Javascript ist, daß der Browser nach dem Ansteuern eines neuen Frames immer eine Zeit wartet, bis er es wirklich zeigt (seeked-event) und dieses verarbeitet werden kann, wodurch eine Analyse die schneller als das Abspielen ist kaum möglich ist.

Download / Live Test

Benutzerhandbuch

Um die Video Shot Boundary Detection zu aktivieren brauchen Sie im Prinzip nur ein Video mit „Load Video“ zu laden. Für das „Load Video“ Feature darf ihr Browser PopUp-Fenster nicht blockieren. Ansonsten müßten sie das standardmäßig geladene Video im source-Tag innerhalb des HTML video-Tags in index.html händisch ändern. Dann drücken Sie auf den Button „Analyze Video“. Daraufhin erscheint eine Meldung „Please Wait - I am analyzing your video!“ und ein Button „stop analyzing“ um die Analyse zu unterbrechen. Diese kann danach jederzeit wieder an der Stelle, an der sie unterbrochen worden ist, durch erneutes Klicken auf „Analyze Video“ fortgesetzt werden. Sie sehen die aktuelle Position, bis zu der analysiert wurde, im Slider „Analyzation Start Time“, nachdem die Analyse unterbrochen worden ist.

Sie können natürlich auch händisch eine „Analyzation Start Time“ (i.e. Startzeitpunkt für die Analyse) wählen. Haben Sie im Video zu einem Zeitpunkt navigiert, an dem Sie die Analyse starten wollen, so drücken Sie zuerst „M0“ um diese Position intern zu merken und danach „R“ für Restore. „M1“ merkt sich hingegen nicht die Position vom Videospieler sondern die Position des Analyzation Start Time – Schiebereglers. Wenn Sie eine Szene mehrmals mit verschiedenen Parametern analysieren wollen sind „R“ und „Clear List“ praktisch, welches bereits erkannte Szenen oder Shots wieder aus der Szenenliste löscht. „Reset“ positioniert hingegen die Analyzation Start Time ganz am Anfang und löscht gleichzeitig alle bisher erkannten Szenen.

Der wohl wichtigste Einstellungsparameter ist der „Threshold“. Wird der Threshold für den aktuell berechneten Differenzwert überschritten, so wird ein neues Bild für den Szenenwechsel hinzugefügt. Für den Threshold gibt es zwei Einstellungs-Handles: „Upper Bound für Threshold“ legt die Obergrenze und damit den verfügbaren Wertebereich für den „Threshold“ - Slider ganz oben fest. Das war notwendig, da abhängig von der Sliding Average Size sehr unterschiedliche Werte für den Threshold gebraucht werden und eine Einstellungsmöglichkeit bis hinunter zu hundertstel Prozentpunkten möglich ist.

Der zweitwichtigste Parameter ist die Sliding Average Size. Die Pixelzahl für einen gewissen Farbwert des einen Bildes wird stets vom Mittelwsert des anderen abgezogen. Der Mittelwsert wird deshalb berechnet um ähnliche Werte im Farb-Histogramm miteinander zu verknüpfen. Die Sliding Average Size gibt dabei den Radius an mit dem entsprechend weit entfernte Stellen im Histogramm noch in die Analyse einbezogen werden. An den Rändern wird der zusätzliche Wert allerdings nur sehr schwach in den Mittelwsert aufgenommen. Das Histogramm unterscheidet dabei 256 verschiedene Helligkeitswerte für Rot, Grün und Blau sodaß 128 einen Pixel am Rand gerade noch mit einem in der Mitte (und umgekehrt) verknüpft.

Je kleiner die Sliding Average Size desto höher kann man den Threshold ansetzen. Bei größeren Sliding Average Sizes mitteln sich die Differenzwerte eher aus und sind daher kleiner. Sollen benachbarte Helligkeitswerte überhaupt nicht in Relation gesetzt werden, so kann die Checkbox „Use Sliding Average“ abgehakt werden oder 1 als Größe angegeben werden (einfache Histogramm-Subtraktion).

Ein weiterer Einstellungsparameter ist die „Inter-Frame Gap“, die man für optimale Ergebnisse auf die Framerate des Videos einstellen kann (also bspw. 40ms für 25fps – 1000/25). Eine höhere Inter Frame Gap macht die Analyse für Testzwecke schneller. Es können Werte bis zu etwa 2000ms also 2 Sekunden sinnvoll sein. Höhere Werte kann man bei langsamen Landschaftsaufnahmen oder bei sich kontinuierlich bewegenden Zeichentrickfilmen einsetzen. Actionszenen hingegen, bei denen sich im Bild von einem Frame auf das andere schon recht viel ändert, sind hingegen nicht für einen höheren Inter-Fram Gap geeignet außer man würde einen sehr hohen Threshold verwenden, was aber wieder etliche Szenenwechsel unerkannt bleiben ließe.

Ein Nachteil einer kleinen Inter-Frame Gap ist, daß kontinuierliche Änderungen wie Überblendungen dann nicht erkannt werden können, da sich da von einem auf das andere Frame nicht viel ändert. Für Überblendungen von und auf Schwarz gibt es aber die Checkbox „Recognize Black Frames“, die hier Abhilfe schaffen kann. Um Überblendungen zu überspringen reicht für gewöhnlich eine Inter-Frame Gap von 1000ms, da diese kaum länger als eine Sekunde dauern.

Ein weiteres Feature das zusätzlich zur Histogrammanalyse angefordert werden kann und dann vor dieser berechnet wird ist „Align Lucidity“ - der Helligkeitsausgleich. Bei dunkleren Bildern konzentriert sich das gesamte Histogramm auf der linken Seite, der Seite für geringere Helligkeitswerte. Align Lucidity nimmt nun diesen Bereich, in dem sich der Hauptteil des sichtbaren Histogramms befindet und dehnt diesen auf die gesamte Breite aus. Das funktioniert natürlich nur wenn der auszudehnende Bereich groß genug ist, da sonst nicht genug Informationen verfügbar sind und das resultierende Histogramm sehr blockig wäre. Auf die Histogrammanalyse hat der Helligkeitsausgleich normalerweise einen positiven Effekt, da hier immer nur Werte an derselben Helligkeitsstelle verglichen werden. Der Schwellwert unter dem nicht relevante Teile des Histogramms links und rechts abgeschnitten werden ist in der Variable lucidity_threshold gespeichert und kann derzeit nur manuell im Programm geändert werden.

Der Helligkeitswert, ab dem das Histogramm hell genuger Bilder gespreizt wird, kann hingegen schon unter „Spread-Lucidity Minimum Threshold“ eingestellt werden. 256 würde erst ab einem ganz weißen Bild spreizen, sodaß Align Lucidity keinen Effekt hätte. Nun gibt es aber im Video beim Dimmen einen ruckartigen Übergang ab dem gespreizt wird. Soll dabei die automatische Erkennung einer neuen Szene verhindert werden können die beiden Checkboxen „Ignore Lucidity Transgression“ mit „to black“ - hinunterdimmen und „from black“ - hellerdimmen angehakt werden. Es gibt davon eine kleine Ausflucht über den „No Ignore Threshold“, der standardmäßig auf 100% gestellt ist. Stellt man diesen auf einen kleineren Wert so wird beim Übergang von schwarz oder sehr dunkel auf normale Helligkeit und umgekehrt trotzdem eine neue Szene erkannt falls der Helligkeitsunterschied zwischen benachbarten Frames groß genug ist.

Beim Dimmen kann die Black-Frame Recognition aber versagen, wenn es kein Frame gibt das ganz schwarz ist, beispielsweise weil dazwischen noch ein weißer Text in der Mitte angezeigt wird. Dann empfiehlt es sich statt „Recognize Black Frames“ den Haken unter „Ignore Lucidity Transgression“ für etwa „from black“ zu lösen.

„Stabilize Lucidity below Δ“ macht, daß links und rechts vom Histogramm immer dieselbe Anzahl an Werten ohne nennenswerte Anzahl abgeschnitten werden, da hier eine Änderung zur Erkennung zahlreicher fälschlicher Szenenwechsel führen würde. Beim Hinunter- und Hinaufdimmen muß sich dieser Wert allerdings ändern. Während „Spread-Lucidity Minimum Threshold“ verhindert, daß ein zu kleiner Bereich auf das gesamte Histogramm ausgedehnt wird macht „Cut-Lucidity Threshold“, daß links und rechts nur Bereiche abgeschnitten werden, die 1/16 unter dem Mittelwsert für den Pixel-Anzahl Eintrag liegen.

Wird ein höherer Inter-Frame Gap eingesetzt also beispielsweise 500ms oder 1000ms, so kann man den Szenenbeginn trotzdem noch mit höherer Genauigkeit feststellen, indem man einen geringeren Wert in ms für die „Accuracy“ angibt. Es wird dann nach Erkennung eines Szenenwechsels noch zusätzlich der Beginn der Szene über binäre Suche „Binary Search“ oder sequentielle Suche „Sequential Search“ gesucht. Es ist nicht bekannt, daß die langsamere sequentielle Suche besser abschneidet als die binäre Suche obwohl sich diese tatsächlich alle Zwischenbilder anschaut.

Wenn Sie auf eine Szene klicken, springt das Video an deren Beginn. Das jeweils nächste und vorhergehende Frame können Sie mit den Buttons „<“ und „>“ direkt rechts neben dem Video ansteuern. Die Auflösung mit der von einem zum nächsten oder vorhergehenden Frame gesprungen wird, wird wiederum mit der Accuracy festgelegt. Das gesamte Video wiederum kann durch Ziehen mit der Maus größer oder kleiner gezogen werden, indem Sie die Maus zuerst rechts oder unterhalb des Videobildes positionieren bis der Maus-Cursor die Möglichkeit zur Größenänderung anzeigt. Auch die Größe der Vorschaubilder für die Szenen kann über „Icon Size“ eingestellt werden.

Ein weiterer Kniff ist die Minimum Shot Length. Diese legt fest wie lange eine Szene mindestens zu dauern hat. Fast alle Szenen dauern länger als eine Sekunde (i.e. Einstellung auf 1000ms) obwohl es beispielsweise im Big Buck Bunny Film eine Szene gibt die nur einen einzigen Frame lang dauert (also etwa 40ms). Durch Festlegen einer Minimum Shot Length kann verhindert werden, daß in gewissen Szenen, für welche der Threshold eigentlich zu nieder ist, unzählige Szenenwechsel erkannt werden. So wird dann maximal jede neue Sekunde ein Bild für einen neuen Szenenwechsel eingefügt.

Schließlich gibt es noch die beiden Checkboxen „View Histogram“ und „View Histogram of previous frame“ welche nach jeder erkannten Szene jeweils drei Histogramme für rot, grün und blau für das vorhergehende und das aktuelle Bild einfügen. So kann man sich die Daten ansehen, aufgrund derer das Programm die Entscheidung für die Erkennung einer neuen Szene getroffen hat. Auf den gezeigten Histogrammen wurde bereits „Align Lucidity“ angewendet. Die Histogramme können unter Umständen eine Erklärung dazu liefern, warum einzelne Szenenwechsel schon oder nicht erkannt werden. Überdies hat das Feature bei der Entwicklung des Algorithmus seinen Einsatz gefunden.

Zu guter letzt möchten Sie wahrscheinlich auch die erkannten Szenen und ihre Startzeitpunkte in einer Liste abspeichern können, was über „Save List of All Shots“ geht. Sie können sich diese auch zuerst über „View List of All Shots“ ansehen. Hier gibt es auch eine Möglichkeit direkt in das Clipboard zu kopieren, welches dann gewöhnlich mit Strg+V in einem Texteditor eingefügt werden kann. Popup-Windows dürfen wieder nicht blockiert werden. Um in der textuellen Videoliste die Übersicht zu bewahren können Sie den einzelnen Szenen mit dem Eingabefeld rechts von „Delete this Shot“ einen textuellen Namen zuweisen. „Create New Shot Here“ und „Delete this Shot“ dienen hingegen zur Ergänzung der automatischen Szenenerkennung, indem hier händisch Szenen eingefügt und gelöscht werden können.

Installationsanleitung

Grundsätzlich ist alles was man zur Installation der Sliding Average Shot Boundary Detection in Javascript braucht ein Webserver, der evtl. auch php-Skripte unterstützen sollte, wenn man sich die händische Eingabe der Videodateinamen am Server sparen will. Legen Sie auf einem lokalen Webserver ein Verzeichnis an (bspw. ShotDetection), kopieren Sie index.html, listdir.php und die Videos hinein und rufen Sie die Seite lokal über einen Browser auf (bspw. http://localhost/ShotDetection).

Es folgt eine kurze Beschreibung für die Konfiguration des Apache Servers, dem unter Linux wohl am weitesten verbreiteten Web Server:

ServerName localhost DocumentRoot "/home/user/public_html" AddHandler application/x-httpd-php5 .php <Directory "/home/user/public_html/"> Options ExecCGI FCGIWrapper /usr/bin/php-cgi AddHandler fcgid-script .php AllowOverride all Order allow,deny Allow from all Require all granted </Directory> NameVirtualHost 127.0.0.1:80 <VirtualHost 127.0.0.1:80> DocumentRoot /home/user/public_html ServerName localhost:80 </VirtualHost> NameVirtualHost ::1:80 <VirtualHost ::1:80> DocumentRoot /home/user/public_html ServerName localhost:80 </VirtualHost>

Unter Debian reicht es obigen Inhalt in eine Datei unter /etc/apache2/sites-enabled/ zu kopieren; unter anderen Distributionen kann eine Aufnahme in httpd.conf / apache2.conf notwendig sein. Zusätzlich müssen Sie noch das Apache Modul für php installieren und aktivieren, was unter Debian mit

cd /etc/apache2/mods-enabled ln -s ../mods-available/php7.0.conf php7.0.conf ln -s ../mods-available/php7.0.load php7.0.load oder a2enmod mod_php möglich ist.

Grundsätzlich gibt es zwei Möglichkeiten um php zu aktivieren. Eine ist über CGI und die andere über ein php-eigenes Apache Modul. Das Programm kann auch ohne php verwendet werden. Will man trotzdem eine Liste zum Auswählen einer Videodatei im Programm verfügbar haben, so empfiehlt sich folgendes:

ls -1 *.webm *.mkv *.mov *.mp4 >listdir.lis sed -i "s#listdir.php#listdir.lis#" index.html

Ersteres bash-Kommando muß nach jeder Installation einer neuen Videodatei erneut aufgerufen werden, zweiteres nur einmal um von php auf eine einfache Listendatei umzustellen (umgekehrt: sed -i “s#listdir.lis#listdir.php#“ index.html). Man könnte den Dateinamen auch direkt mit einem Texteditor in index.html ändern. Jedenfalls müssen alle Videodateien in dasselbe Verzeichnis wie index.html kopiert werden (oder zumindest von dort in ein anderes Apache Directory verlinkt werden, wenn Options SymLinksIfOwnerMatch zusätzlich angegeben wird.).