DE69613949T2

DE69613949T2 - Vorrichtung zum Detektieren von Schnitten in einer Videosequenz

Info

Publication number: DE69613949T2
Application number: DE69613949T
Authority: DE
Inventors: Farshid Arman; Shih-Ping Liou; David L. Loching
Original assignee: Siemens Corporate Research Inc
Current assignee: Siemens Corp
Priority date: 1995-12-21
Filing date: 1996-11-19
Publication date: 2001-11-22
Anticipated expiration: 2016-11-20
Also published as: DE69613949D1; ATE203340T1; EP0780776B1; EP0780776A1; US5835163A

Description

Jeden Tag wird zunehmend Video erzeugt. Um Informationen aus solchen Videosammlungen wirksam und effektiv zu benutzen, müssen diese ordnungsgemäß in einer Datenbank indexiert werden. Die grundlegendste und wichtigste Aufgabe ist dabei das Zerlegen des Videos in eine entsprechende Menge von Einheiten, die als Szenen bezeichnet werden. Die meisten gegenwärtigen Ansätze beruhen auf voreingestellten Schwellwerten oder ungeeigneten Annahmen, die ihre Anwendbarkeit auf einen begrenzten Bereich von Videoarten herabsetzen.
Die folgende Beschreibung der vorliegenden Erfindung enthält auch eine mathematische Formulierung der Aufgabe, eine schnelle und robuste Realisierung der mathematischen Formulierung und einen Cut-Browser. Die Leistungsfähigkeit ist an über 149000 Videobildern aufgezeigt worden, zu denen verschiedene Arten von Video wie Sport und Filme gehören.
Zu Videoquelle gehören Verteidigungs-/Zivilsatelliten, wissenschaftliche Experimente, biomedizinische Bilderzeugung, Fingerabdruckvorrichtungen und Heim-Unterhaltungsanlagen. Um die Informationen von solchen Videosammlungen wirkungsvoll und effektiv zu benutzen, müssen die Videos ordnungsgemäß in einer Datenbank indexiert sein. Videoindexierung bietet einen schnellen und genauen Zugriffsweg zu gewünschten Videodaten auf der Basis ihres Inhalts. Die grundlegenste und wichtigste Aufgabe ist dabei die Zerlegung des Videos in eine entsprechende Menge von Einheiten, die Szenen genannt werden.
Bei Video bezieht sich eine Szene auf eine zusammenhängende Aufzeichnung von einem oder mehreren Videobildern, die eine fortlaufende Handlung in der Zeit und im Raum darstellen. In einer Szene könnte die Kamera stationär bleiben oder sie kann eine der charakteristischen Bewegungen wie Schwenken, Neigen oder Nachführung aufweisen. Bei den meisten Videos werden Szenenänderungen oder Cuts absichtlich durch Video-/Filmregisseure erstellt. In den frühen Jahren wurden sie auf einem Schnittgerät und einem optischen Printer durchgeführt und Szenenlisten wurden auf Papierprotokollen, den Zählblättern geführt.
Seit 1985 sind die meisten Szenenänderungen mit modernen Schnittgeräten erzeugt worden. Informationen über jede Einzelszene werden elektronisch in einer Schnitt-Entscheidungsliste (Editing Decision List - EDL) aufbewahrt, die direkt in eine Datenbank indexiert werden kann. Für die meisten Videos/Filme, die vor der Erfindung solcher Einrichtungen hergestellt wurden, sind diese auf Papier aufgezeichneten Informationen unter Umständen nicht mehr zugänglich. Dies trifft gewiß auf Heimvideos und Sportfilmmaterial zu, da Cuts durch Ein- und Ausschalten der Camcorder/Filmkameras erzeugt werden. In beiden Fällen müssen Cuts im Video durch handbetätigte oder automatische Mittel erkannt werden.
Im Gegensatz zu den Behauptungen in der Literatur ist die Auseinandertrennung von Szenen in einem Video keine triviale Aufgabe, wenn man die Komplexität einer Szene und die Wirksamkeit moderner Schneidetechniken in Betracht zieht.
Der Übergang von einer Szene zu einer anderen kann optisch abrupte gerade Schnitte oder Kamerabildunterbrechungen enthalten. Er kann auch solche Trickeffekte wie Auf-, Ab- und Überblendungen, Schiebeblenden, Klappblenden, Überlagerungen, Stopp- oder Standbilder, Vertausch der beiden Seiten, Rückwärtsszenenabläufe, Vergrößerungen, Vorwärtsfahrten, Repositionierungen und Skip-Frame-Verfahren enthalten. Man siehe beispielsweise B. Balmuth, "Introduction to Film Editing" (Einführung in die Filmschneidekunst), Focal Press, 19%.
Da der Zweck der Videoindexierung darin besteht, das Abrufen von gewünschten Videoausschnitten aus einer Datenbank zu unterstützen, ist es wichtig, daß eine Trefferquote von 100% und maximale Präzisionsrate gewahrt wird. Eine Trefferquote wird hier als der Prozentsatz der eigentlichen erkannten Cuts und eine Präzisionsrate als der Prozentsatz der erkannten Cuts, die eigentliche Cuts sind, definiert.
Die meisten gegenwärtigen Ansätze befassen sich mit sehr bestimmten Fällen von wenigen der obigen Übergangsarten und auch dann wird niemals eine Trefferquote von 100% erreicht. Zusätzlich werden sie häufig an wenigen Typen von Videos und wenigen Tausenden von Videobildern geprüft, was nicht ausreicht, um zu einer realistischen Beurteilung der Leistungsfähigkeit einzelner Algorithmen zu kommen. Die meisten bestehenden Algorithmen können nicht mit annähernder Videofrequenz implementiert werden, was dem Bereich von Anwendungen, für die sie benutzt werden können, ernsthafte Beschränkungen auferlegt. Was bedeutender ist, ist daß sie häufig auf voreingestellten Schwellwerten oder unzutreffenden Annahmen beruhen, die ihre Anwendbarkeit auf einen begrenzten Bereich von Arten von Videos herabsetzen.
In Multimedia Systems, Band 1, Nr. 1, 10. Januar 1993, Seiten 10-28, HongJiang Zhang et al.: "Automatic partitioning of full motion video" (Automatische Abtrennung von Bewegtbildvideo) ist ein Algorithmus für Videosegmentierung und -indexierung beschrieben, wo während der Segmentierung die zu vergleichenden Bilder in einer Bildplatte abgetastet werden. Die Erkennung von Übergängen in dem zu segmentierenden Video wird durch Berechnung einer Differenzmetrik auf Grundlage des paarweisen Vergleichs von Pixeln in benachbarten Bildern uncl auch durch Vergleichen von statistischen Eigenschaften zweiter Ordnung in aufeinanderfolgenden Bildern erreicht.
Bezug wird auch auf die nachfolgenden US- Patentanmeldungen genommen, die Material enthalten, das für die vorliegende Anmeldung von großem Interesse ist: US-Patentanmeldung Seriennummer 08/221,227, eingereicht am 31. März 1994 im Namen von Arman et al.; US-Patent US-A-5606655 von Arman et al.; US-Patent US-A-5521841 von Arman et al.; US-Patentanmeldung Seriennummer 08/343,793, eingereicht am 22. November 1994 im Namen von Arman et al.; US-Patent US-A-5574845 von Benson et al.
Darin wird anerkannt, daß ein gutes Cut- Erkennungsverfahren ein solches ist, das
- die maximale Trefferquote und Präzisionsrate für optisch abrupte Cuts und Kamerabildunterbrechungen liefern kann,
- Cuts zum Ablesen des Videos bis zur Ausgabe von Szenenänderungsbildern in der Nähe der Bildfrequenz erkennen kann,
- die nichtstationäre Beschaffenheit der Cut- Erkennungsaufgabe in Betracht zieht,
- einen Rückkopplungsmechanismus aufweist, um eine Trefferquote von 100% zu erreichen, an verschiedenartigen Videos und einer großen Anzahl von Videobildern arbeiten kann, und
- bei Anwendung auf komprimiertes Video unabhängig von den Codierern und verschiedenen Codieralgorithmen ist.
Nach einem Aspekt der Erfindung umfaßt ein Verfahren zur Erkennung eines Cuts in einem Video folgende Schritte: (a) Erfassen von Videobildern von einer Quelle; (b) Ableiten einer pixelbasierenden Differenzmetrik aus den Videobildern; (c) Ableiten einer verteilungsbasierenden Differenzmetrik aus den Videobildern; (d) Messen des Videoinhalts der Videobilder zur Bereitstellung aktueller Prüfkriterien; (e) Kombinieren der pixelhasierenden Differenzmetrik und der verteilungsbasierenden Differenzmetrik unter Berücksichtigung der im Schritt (d) gelieferten aktuellen Prüfkriterien, um ein in Frage kommendes Szenenänderungssignal abzuleiten; und (f) Filtern des in Frage kommenden Szenenänderungssignals, um eine Szenenänderungs-Bildliste zu erzeugen.
Nach einer weiteren Ausführungsform der Erfindung ist die pixelbasierende Differenzmetrik für jedes Bild die Summierung einer absoluten Bilddifferenz, die für den Bildintensitätswert an ausgewählten Pixelstellen in einem Bild repräsentativ ist.
Nach einer weiteren Ausführungsform der Erfindung ist die pixelbasierende Differenztrik für jedes Bild t die Summe einer absoluten Bilddifferenz,
wobei f den Intensitätswert an Pixelstelle (i,j) im Bild t darstellt.
Nach einer weiteren Ausführungsform der Erfindung wird jedes Bild in einer Anzahl von Teilgebieten eingeteilt, wobei die verteilungsbasierende Differenzmetrik eine Kolmogorov-Smirnov- Prüfmetrik ist, mit der Ausnahme, daß jeweils eine darin für das gesamte Bild und auch seine Teilgebiete berechnet wird.
Nach einer noch weiteren Ausführungsform der Erfindung wird jedes Bild gleichmäßig in vier Teilgebiete eingeteilt, wobei die verteilungsbasierende Differenzmetrik eine Kolmogorov-Smirnov-Prüfmetrik ist, mit der Ausnahme, daß jeweils eine darin für das gesamte Bild und auch die vier gleichmäßig eingeteilten Teilgebiete berechnet wird.
Nach einer noch weiteren Ausführungsform der Erfindung bietet der Schritt des Messens des Videoinhalts der Videobilder zur Bereitstellung von aktuellen Prüfkriterien dem Schritt (e) die Fähigkeit, sich automatisch auf verschiedene Videoinhalte einzustellen.
Nach einer noch weiteren Ausführungsform der Erfindung sind die Videobilder Gleichspannungsbilder, die durch die Grundfrequenz in den Koeffizienten der diskreten Cosinustransformation dargestellt werden, die das zugrunde liegende Vollbild kennzeichnet.
Nach noch einer weiteren Ausführungsform der Erfindung umfaßt der Schritt des Messens des Videoinhalts der Videobilder zur Bereitstellung aktueller Prüfkriterien das Sammeln von Statistiken aus jedem Gleichspannungsbild und jedem Paar von Gleichspannungsbildern zur Darstellung des gegenwärtigen Videoinhalts, nämlich einem Bildkontrast und die Bewegungsschätzung. Die Bildkontrastschätzung wird auf Grundlage einer rekursiven Anordnung zur Unterdrückung der Einflüsse plötzlicher Beleuchtungsänderungen berechnet.
Nach noch einer weiteren Ausführungsform der Erfindung stellt das Sammeln von Statistiken aus jedem Gleichspannungsbild und jedem Paar von Gleichspannungsbildern zur Darstellung des gegenwärtigen Videoinhalts eine Bildkontrastschätzung und eine Bewegungsschätzung dar.
Nach noch einer weiteren Ausführungsform der Erfindung wird die Bildkontrastschätzung auf Grundlage einer rekursiven Anordnung zur Unterdrückung der Einflüsse plötzlicher Beleuchtungsänderungen berechnet.
Nach noch einer weiteren Ausführungsform der Erfindung wird die Bildkontrastschätzung nach dem folgenden abgeleitet:
Kontrastt = (1 - τ) Kontrastt-1 + τσt-1,
wobei σt-1 die Intensitätsvarianz-Schätzung des Gleichspannungsbildes zur Zeit t-1 ist.
Nach noch einer weiteren Ausführungsform der Erfindung ist die Bildkontrastschätzung gleich 0,6.
Nach einer weiteren Ausführungsform der Erfindung wird die Bewegungsschätzung wie folgt berechnet:
wobei f der Intensitätswert an Pixelstelle (i,j) des Gleichspannungsbildes zur Zeit t-1 und N die Größe des Bildes ist.
Nach einer weiteren Ausführungsform der Erfindung ist τ gleich 0,6.
Nach noch einer weiteren Ausführungsform der Erfindung werden die Bildkontrast- und Bewegungsschätzungen an einer Fuzzy-Maschine angelegt, um ein neues Signifikanzniveau für die hierarchische Kolmogorov-Smirnov-Prüfung zu berechnen, wobei die Fuzzy-Maschine sich einer quadratischen Zugehörigkeitsfunktion bedient, wobei jede Kontrastmessung in Klassen von niedrig bis hoch eingeteilt wird und jede Bewegungsschätzung in Klassen von langsam bis schnell eingeteilt wird und jedes Signifikanzniveau in Klassen von hoch bis niedrig eingeteilt wird.
Nach einer noch weiteren Ausführungsform der Erfindung wird jede Kontrastmessung in vier Klassen, niedrig, mittel, hoch und äußerst hoch, jede Bewegungsschätzung in drei Klassen, langsam, mittel und schnell, und jedes Signifikanzniveau in fünf Klassen hoch, mittelhoch, mittel, mittelniedrig und niedrig eingeteilt und wobei die Fuzzy-Regeln in einem einfachen WENN/DANN-Format angegeben werden, wobei Werte unter Verwendung von UND (Minimum) oder ODER (Maximum)-Operationen kombiniert werden.
Nach einer noch weiteren Ausführungsform der Erfindung enthält ein Verfahren zur Erkennung eines Cuts in einem Video einen Schritt des Defuzzifizierens der Fuzzy-Regeln zur Erzeugung eines scharfen Endausgabewertes durch Finden des Schwerpunkts der kombinierten Ausgangsform, wodurch sichergestellt wird, daß alle Regeln zum scharfen Endergebnis beitragen.
Nach einer noch weiteren Ausführungsform der Erfindung werden im Schritt (e) des Kombinierens der pixelbasierenden Differenzmetrik und der verteilungsbasierenden Differenzmetrik unter Berücksichtigung der im Schritt (d) bereitgestellten aktuellen Prüfkriterien zur Ableitung eines in Frage kommenden Szenenänderungssignals die pixelbasierenden Differenzmetriken als Zeitreihensignale behandelt, wobei sowohl optisch abrupte Cuts als auch die Verdopplung vor. Bildern Beobachtungsausreißer erzeugen.
Nach einer noch weiteren Ausführungsform der Erfindung wird die pixelbasierende Differenzmetrik als ein Zeitreihensignal behandelt, wobei sowohl optisch abrupte Cuts als auch die Verdopplung ·von Bildern Beobachtungsausreißer erzeugen, die die folgende Gleichung befolgen:
dt = f(dt-r, dt-r+1, ..., dt) + ut wenn t ≠ q
dt = f(dt-r, dt-r+1, ..., dt) + ut + Δ sonst,
wobei t den Zeitindex darstellt, Δ der Ausreißer ist, f(dt-r, dr-r+1, ..., dt) den Trend in der Reihe modelliert,
und
ut = αrdt-r + zt (t = p + 1, ..., n).
Nach einem noch weiteren Aspekt der Erfindung umfaßt eine Einrichtung zur Erkennung eines Cuts in einem Video folgendes: (a) eine Einrichtung zur Erfassung von Videobildern von einer Quelle; (b) eine Einrichtung zum Ableiten einer pixelbasierenden Differenzmetrik aus den Videobildern; (c) eine Einrichtung zum Ableiten einer verteilungsbasierenden Differenzmetrik aus den Videobildern; (d) eine Einrichtung zum Messen des Videoinhalts der Videobilder zur Bereitstellung von aktuellen Prüfkriterien; (e) eine Einrichtung zum Kombinieren der pixelbasierenden Differenzmetrik und der verteilungsbasierenden Differenzmetrik unter Berücksichtigung der im Schritt (d) bereitgestellten aktuellen Prüfkriterien zur Ableitung eines in Frage kommenden Szenenänderungssignals; und (f) eine Einrichtung zum Filtern des in Frage kommenden Szenenänderungssignals zur Erzeugung einer Szenenänderungs-Bildliste.
In einer noch weiteren Ausführungsform enthält die Erfindung eine Einrichtung zur Erkennung eines Cuts in einem Video nach Anspruch 20 einschließlich einer Einrichtung zur Darstellung von zwei Querschnittsbildern der Videobilder, wobei ein horizontales Querschnittsbild in einer horizontalen Richtung und ein senkrechtes Querschnittsbild in einer senkrechten Richtung des Videovolumens liegt.
Nach einer noch weiteren Ausführungsform der Erfindung wird jedes Querschnittsbild durch Abtasten einer Zeile (oder Spalte) aus jedem Bild und Reduzieren der Informationsmenge von einem zweidimensionalen Bild zu zwei eindimensionalen Bildstreifen konstruiert.
Nach einer noch weiteren Ausführungsform der Erfindung werden die horizontalen und senkrechten Querschnittsbilder in ein in zwei Bänder segmentiertes Bild nach einer Liste erkannter Szenen kombiniert, wodurch eine Abstraktionshöhe dargestellt wird, die gerade dazu ausreicht, zu zeigen, ob eine verpaßte oder fehlerkannte Szene vorliegt.
Die Erfindung wird durch die nachfolgende ausführliche Beschreibung bevorzugter Ausführungsformen im Zusammenhang mit der Zeichnung deutlicher verständlich. In der Zeichnung zeigen:
Fig. 1, daß ein herkömmlich benutzter Cut- Erkennungsalgorithmus des Standes der Technik als ein Vorgang eingestuft werden kann, der die vier Schritte Datenerfassung, Differenzmetriksammlung, Erkennung und Entscheidung umfaßt, wobei die gestrichelten Kästen wahlfreie Schritte anzeigen, die in einigen Algorithmen vorkommen und wobei die Verzögerungsschaltung ein Mechanismus zur Verwendung von Informationen aus sowohl vergangenen als auch zukünfigten Bildern ist;
Fig. 2 vier Arten von 3 : 2-Filmtransport;
Fig. 3 ein Histogramm eines typischen Zwischenbild-Differenzbildes, das nicht einer Szenenänderung entspricht;
Fig. 4 eine erfindungsgemätße Browsereinrichtung;
Fig. 5(a) zwei Querschnitte in Videovolumen und Fig. 5(b) ein aus zwei Querschnitten bestehendes Raum-Zeit-Bild, das zum Verständnis der Erfindung nützlich ist;
Fig. 6 Beispiele von Querschnittsmustern nach der Erfindung, wobei Fig. 6(a) optisch abrupte Cuts und Fig. 6(b) allmähliche Szenenübergänge in schwarz und weiß zeigt und Fig. 6(c) und 6(d) dieselben Figuren in Farbe sind.
Fig. 7 ein Flußdiagramm eines erfindungsgemäßen Cut-Erkennungsalgorithmus;
Fig. 8 ein Teil-Flußdiagramm des erfindungsgemäßen Schrittes der Differenzmetriksammlung;
Fig. 9 ein Teil-Flußdiagramm des erfindungsgemäßen Anpassungsschrittes;
Fig. 10 die Zugehörigkeitsfunktion der Kontrastschätzung nach der Erfindung;
Fig. 11 die Zugehörigkeitsfunktion der Bewegungsschätzung nach der Erfindung;
Fig. 12 die Zugehörigkeitsfunktion von Kα, die proportional zur Bedeutungshöhe nach der Erfindung ist;
Fig. 13 ein Teil-Flußdiagramm des erfindungsgemäßen Erkennungsschrittes;
Fig. 14 ein Beispiel der Tendenzschätzung, wobei Fig. 14(a) zeigt, daß ein Beobachtungausreißer des Typs I erkannt wird und Fig. 14 (b) zeigt, daß ein Beobachtungsausreißer des Typs II erkannt wird; und
Fig. 15 eine Cut-Browsereinrichtung mit der Erfindung, wobei 15(a) in schwarz und weiß ist und 15(b) dieselbe Figur in Farbe ist.
Die vorliegende Erfindung betrifft ein automatisches Cut-Erkennungsverfahren und eine Cut- Browsereinrichtung, die allen oben aufgeführten Kriterien genügt. Die Cut-Erkennung wird als Aufgabe einer Erkennung von nichtstationären Zeitreihen- Ausreißern formuliert.
Die Bemühungen zur Cut-Erkennung lassen sich zu D. Coll und G. Choma, "Image Activity Characteristics in Broadcast Television" (Eigenschaften der Bildaktivität im Fernsehrundfunk), IEEE-Trans. on Communiciations, Band 26, S. 1201-1206, 1976 zurückverfolgen, wo die Autoren eine ausführliche experimentelle Untersuchung von Bilddifferenzsignalen unter Verwendung von vier unterschiedlichen Arten von Video, einem Fußballspiel, einem Schauspiel, einer Talkshow und einem Zeichentrickfilm, durchführen. Die Autoren teilen jedes unkomprimierte Videobild in 8 · 8 Blöcke ein, von denen jeder durch seinen durchschnittlichen Grauwert dargestellt wird. In ihrer Untersuchung wird der Durchschnittswert der Größen der Differenzen zwischen entsprechenden Blöcken aufeinanderfolgender Bilder als die Differenzmetrik benutzt. Coll und Choma zeigen, daß ein experimentell bestimmter Schwellwert Szenenänderungen mit einer der Genauigkeit eines menschlichen Beobachters entsprechenden Genauigkeit erkennen kann. Weitere, auf unkomprimiertem Video basierende Szenenänderungs- Erkennungsalgorithmen sind auch in der Literatur über Computer-Sehen anzutreffen. Man siehe beispielsweise I. Sethi, V. Salari und S. Vemuri, "Image Sequence Segmentation using Motion Coherence" (Bildfolgensegmentierung unter Verwendung von Bewegungskohärenz), Proc. First International Conference on Computer Vision), S. 667-671, 1987; Y. Z. Hsu, H.-H. Nagel und G. Pekers, "New Likelihood Test Methods for Change Detection in Image Sequences" (Neue Likelihood- Prüfverfahren für Änderungserkennung in Bildfolgen), CVGIP, 26, S. 73-106, 1984, I. Sethi, V. Salari und S. Vemuri, "Image Sequence Segmentation using Motion Coherence" (Bildfolgensegmentierung unter Verwendung von Bewegungskohärenz), Proc. First International Conference on Computer Vision, S. 667-671, 1987.
Digitales Video läßt sich in komprimierter Form speichern und übertragen. Siehe Joint Photographic Experts Group (JPEG); ISO/IEC JTC1 SC29 WG1, JPEG}, ISO/IEC 10 918; Moving Picture Experts Group (MPEG) ISO/IEC JTC1 SC29 WG11, MPEG-1, ISO/IEC 11 172 und MPEG-2, ISO/IEC 13 818, und International Telegraph and Telephone Consultative Committee (CCITT) CCITT, Empfehlung H.261, Video Codec for Audiovisual Services at px64 kBit/s, Dezember 1990.
Die Durchführung von Cut-Erkennung und Bildverarbeitung an komprimiertem Video erspart unnötigen Dekomprimierungs-Komprimierungs-Aufwand. Dieser Gedanke führte zu vielen Bemühungen bei der Verfolgung von Lösungen, die komprimiertes Video direkt verarbeiten können, so wie sie durch F. Arman et al. in der US-Patentanmeldung Seriennummer 08/221,227 offenbart sind, die gegenwärtig anhängig ist. Arman et al. haben einen Szenenänderungs-Erkennungsalgorithmus für JPEG- und Bewegtbild-JPEG-Video entwickelt, wobei eine Teilmenge von Koeffizienten der diskreten Cosinustransformation (DCT) zur Kennzeichnung des zugrunde liegenden Bildes benutzt wird. Leider ist es schwierig oder unpraktisch, ohne vollständige Decodierung volle DCT-Koeffizienten bei MPEG- oder H.261-Video zu erhalten. Der Grund dafür ist, daß Bewegungsvektoren-Größen im Raumbereich sind, während DCT-Koeffizienten Größen im Frequenzbereich sind.
Andere Forscher schlugen vor, Bewegungsvektoren direkt entweder zum Aussieben von Szenenänderungsbildern oder zum Erkennen von Szenen- Cuts zu benutzen. Siehe beispielsweise H.-C. H. Liu und G. L. Zick, "Scene Decomposition of MPEG Compressed Video" (Szenenzerlegung von MPEG-komprimiertem Video), SPIE Band 2419, Digital Video Compression Algorithms and Technologies, S. 26-37, 1995; J. Meng, Y. Juan und S.-F. Chang, "Scene Change Detection in a MPEG Compressed Sequence" (Szenenänderungserkennung in einer MPEG-komprimierten Videofolge), SPIE Band 2419, Digital Video Compression Algorithms and Technologies, S. 14-25, 1995; und H. Zhang, C. Y. Low und S. W. Smoliar, "Video Parsing and Browsing Using Compressed Data" (Videozerlegung und Browsing unter Verwendung komprimierter Daten), Multimedia Tools and Applications, 1, S. 89-111, 1995.
Sie beruhen oft auf dem Verhältnis der Anzahl von Vorwärtsprediktions-Makroblöcken zu der Gesamtzahl von Makroblöcken. Da es kein Standardkriterium bei der Bestimmung, ob ein gewisser Makroblock während des Codierungsvorgangs zwischenbildcodiert (zeitweilig aus einem vorhergehenden rekonstruierten Bild geschätzt) oder intracodiert (wie ein JPEG-Basisbild) sein sollte, gibt, ist dieser Ansatz sehr für verschiedene Codierer und Arten von Codieralgorithmen empfindlich.
Die meisten Cut-Erkennungsalgorithmen in der Literatur, ob sie unkomprimierte oder komprimierte Videodaten annehmen oder nicht, können als ein Vorgang mit vier Schritten eingestuft werden: Datenerfassung, Differenzmetriksammlung, Erkennung und Entscheidung wie in Fig. 1 dargestellt. Die gestrichelten Kästen zeigen wahlfreie Schritte an, die in einigen Algorithmen anzutreffen sind. Die Verzögerungsschaltung ist ein Mechanismus zur Verwendung von Informationen aus sowohl vergangenen als auch zukünftigen Rahmen.
Während der Datenerfassungsstufe werden bei Ansätzen, die auf komprimiertem Video basieren, häufig DCT-Koeffizienten oder Bewegungsvektoren gewonnen. Siehe beispielsweise die oben angeführte Anwendung von Arman et al.; H. Ishikawa und H. Matsumoto, "Method for Detecting a Scene Change and Image Editing Apparatus" (Verfahren zur Erkennung eines Szenenwechsels und Bildschneideeinrichtung), Europäisches Patent 0-615-245-A2, eingereicht 3. Juli 1994; H.-C. H. Liu und G. L. Zick, "Scene Decomposition of MPEG Compressed Video" (Szenenzerlegung von MPEG-komprimiertem Video), SPIE Band 2419, Digital Video Compression Algorithms and Technologies, S. 26-37, 1995. Es gibt insgesamt 64 DCT-Koeffizienten einschließlich eines Gleichspannungs- (die Grundfrequenz bei den DCT- Koeffizienten) gliedes und 63 Wechselspannungs- (die höheren Frequenzen bei den DCT-Koeffizienten) gliedern. Der Decodierungsaufwand ist unterschiedlich für verschiedene Algorithmen. Einige decodieren nur Gleichspannungsglieder, siehe beispielsweise J. Meng, Y. Juan und S.-F. Chang, "Scene Change Detection in a MPEG Compressed Video Sequence" (Szenenänderungserkennung in einer MPEG-komprimierten Videofolge), SPIE Band 2419, Digital Video Compression Algorithms and Technologies, S. 14-25, 1995, während andere nur die Anzahl vorwärtscodierter und rückwärtscodierter Bewegungsvektoren gewinnen, siehe beispielsweise H.-C. H. Liu und G. L. Zick, "Scene Decomposition of MPEG Compressed Video" (Szenenzerlegung von MPEG- komprimiertem Video), SPIE Band 2419, Digital Video Compression Algorithms and Technologies, S. 26-37, 1995.
Die meisten derartigen Algorithmen versuchen, vollständige Decodierung zu vermeiden, um rechentechnisch wirkungsvoll zu sein. Bei Ansätzen, die unkomprimierte Videodaten benutzen, wird jedes digitalisierte Bild häufig geglättet bzw. unterabgetastet; siehe beispielsweise P. Aigrain und P. Joly, "The Automatic Real-Time Analysis of Film Editing and Transition Effects and its Applications" (Die automatische Echtzeitanalyse von Filmschnitt- und Übergangseffekten und ihre Anwendungen), Computer and Graphics, Band 18, Nr. 1, S. 93-103, 1994.
Nach Erfassung von Videodaten sammeln die meisten Algorithmen in der Literatur eine Differenzmetrik pro Bild außer denjenigen Algorithmen, die ausdrücklich Bewegungsvektorinformationen benutzen. Eine solche Differenzmetrik läßt sich allgemein in pixelbasierende und verteilungsbasierende Typen einstufen.
Bei der pixelbasierenden Kategorie ist die populärste Differenzmetrik die Summe der Differenz im Quadrat, nämlich
wobei f den Intensitätswert an der Pixelstelle (i,j) im Bild t darstellt. Eine alternative Wahl für weniger Rechenaufwand ist die Summe der absoluten Differenz
Beide Differenzmetriken sind für große Kamerabewegungen empfindlich und führen zu zahlreichen falschen Positivwerten bei der Cut-Erkennung. Um dieses Problem zu überwinden, werden die Videobilder von vielen Forschern vor der Gewinnung der pixelbasierenden Differenzen entweder geglättet oder unterabgetastet. Mit diesem zusätzlichen Schritt wird die Genauigkeitsrate der Cut-Erkennungsalgorithmen oft bedeutend verbessert.
Verteilungsbasierende Differenzmetriken werden andererseits durch Kamerabewegungen weniger beeinflußt. In den späteren 70er Jahren wurde zuerst ein Likelihood-Maß vorgeschlagen, das auf dem Mittel und der Varianz der Intensität des gegenwärtigen und des vorhergehenden Bildes basiert. Siehe Y. Z. Hsu, H.-H. Nagel und G. Pekers, "New Likelihood Test Methods for Change Detection in Image Sequences" (Neue Likelihood-Prüfverfahren für die Änderungserkennung in Bildfolgen), CVGIP, 26, S. 73-106, 1984. Wenn ut und Ct zur Darstellung des Mittels bzw. der Varianz der Intensität des Bildes t benutzt werden, läßt sich die Likelihood-basierende Differenzmetrik folgendermaßen definieren:
Andere bestehende verteilungsbasierende Differenzmaße beruhen auf Histogrammen. Das Bildhistogramm des t-ten Bildes wird mit Ht bezeichnet. Ht(j) sei die Pixelzählungen im Bereich j des Histogramms Ht. Wenn die Gesamtzahl von Bereichen N ist, kann entweder:
oder
berechnet werden.
Beide lassen sich als verteilungsbasierende Differenzmetrik benutzen. Die Bereichsgrüße N in beiden Maßen beeinflußt die Empfindlichkeit des Cut- Erkennungsalgorithmus. Je kleiner die Bereichsgröße, desto empfindlicher wird das Histogrammaß sein. Bei den meisten bestehenden Verfahren wird in allen Intensitätsbereichen eine feste Bereichsgröße benutzt.
Vor kurzem ist eine dritte Art verteilungsbasierender Differenzmetrik vorgeschlagen worden. Siehe I. K. Sethi und N. Patel, "A Statistical Approach to Scene Change Detection" (Ein statistischer Ansatz zur Szenenänderungserkennung), SPIE Band 2420, Storage and Retrieval for Image and Video Databases III, S. 329-338, 1995. Diese Metrik basiert auf der empirischen Verteilungsfunktion (empirical distribution function - EDF) des vorhergehenden und gegenwärtigen Bildes. Sie wird als Kolmogorov-Smirnov-Prüfmetrik bezeichnet.
dt = maxj|EDFt(j) - EDFt-1(j)| (4)
Zur Berechnung der empirischer Verteilungsfunktion wird als erstes das Histogramm jedes einzelnen Videobildes konstruiert. Angenommen, das Histogramm für das Bild t wird durch
{Ht(j) j = 1,N} dargestellt. EDFt(j), das die kumulative Verteilungswahrscheinlichkeit des j-ten Intensitätswertes im Bild t darstellt, kann dann durch folgendes definiert werden:
wobei M die Gesamtzahl von Pixeln im Bild ist.
Nach Einsammlung der Differenzmetrik für jedes Bild wenden die meisten Algorithmen einfach einen voreingestellten Schwellwert auf diese Zeitreihe von Differenzmetriken an. Der Algorithmus vergleicht den Wert der Differenzmetrik mit einem globalen Schwellwert. Wenn er oberhalb dieser voreingestellten Zahl liegt, wird ein Szenenwechsel signalisiert. Da es schwierig ist, einen derartigen Schwellwert für ein gesamtes Video zu finden, haben einige Forscher auch die Verwendung von zwei Schwellwerten vorgeschlagen. Siehe beispielsweise H. Zhang, A. Kankanhalli und S. W. Smoliar, "Automatic Parsing of Full-Motion Video" (Automatische Zerlegung von Bewegtbildvideo), ACM Multimedia System, 1, S. 10-28, 1993.
In jüngster Zeit sind rangbasierende Erkennungsanordnungen sehr populär geworden. Siehe beispielsweise P. Aigrain und P. Joly, "The Automatic Real-Time Analysis of Film Editing and Transition Effects and its Applications" (Die automatische Echtzeitanalyse von Filmschnitt- und Übergangseffekten und ihre Anwendungen), Computer and Graphics, Band 18, Nr. 1, S. 93-103, 1994.
Da globale Schwellwerte schwer zu finden sind, besteht das Konzept darin, daß Schwellwerte nur auf Differenzmetriken in einer örtlichen zeitlichen Nachbarschaft angewandt werden sollten. Dieser Ansatz der örtlichen zeitlichen Nachbarschaft wird als der an den Erkennungsschritt in der Fig. 1 angehangene gestrichelte Kasten angedeutet. Damit dies funktionieren kann, wird in dem Erkennungsschritt eine neue Differenzmetrik aus jedem örtlichen zeitlichen Fenster, das um das gegenwärtige Bild zentriert ist, berechnet. Man bezeichne dt als die Differenzmetrik für das Bild t in der Form der Summe der Differenzen zum 15 Quadrat (bzw. Summe absoluter Differenzen) und nehme an, daß die Größe des Zeitfensters 2N+1 beträgt. Wenn die 2N+1 Beobachtungen di, i = t-N, t+N als < < ... < 2N+1 geordnet sind, wird die neue Metrik häufig auf eine der folgenden drei Weisen berechnet:
dt = 0 wenn dt ≠ d2N+1;
dt = d2N+1/d2N = sonst Gl. 5
oder
dt = 0 wenn dt ≠ d2N+1;
dt = d2N+1 - d2N sonst Gl. 6
oder
dt = 0 wenn dt ≠ d2N+1;
dt = d2N+1/ di sonst Gl. 7
Der voreingestellte Schwellwert wird dann an diese Folge von neuen Metriken t angelegt. Die meisten Algorithmen, die Gleichung 5 oder 7 benutzen, benutzen am liebsten N = 2 und eine Zahl zwischen 3 und 4 als die beste Schwellwertwahl.
Alle bislang besprochenen Erkennungsanordnungen beruhen auf voreingestellten Schwellwerten und behandeln die Cut-Erkennung nicht als Hypothese- Prüfaufgabe. Andererseits gibt es einige wenige Cut- Erkennungsalgorithmen, die auf Hypothese- Prüfparadigmata beruhen. Alle diese Algorithmen lassen sich in zwei unterschiedliche Typen einstufen. Die erste Formulierung betrachtet eine Folge von Differenzmetriken als eine Menge von Proben, die aus einer einzigen bekannten Verteilung gezogen werden, wenn sie von Bildern innerhalb derselben Szene abgeleitet sind. Die zweite Formulierung betrachtet sie als eine Menge von Proben, die aus einer einzigen, aber unbekannten Verteilung gezogen werden. Man beachte hier, daß die Differenzmetrik aus jedem Einzelbild oder aus beliebigen zwei benachbarten Bildern berechnet werden könnte. Diese Formulierungen transformieren die Cut-Erkennungsaufgabe in folgende zwei Aufgaben:
Fall 1: Kann man bis zu einem gewissen erforderlichen Signifikanzniveau die Nullhypothese widerlegen, daß die Differenzmetrik eine aus einer bekannten Verteilung gezogene Probe ist?
Fall 2: Kann man bis zu einem gewissen erforderlichen Signifikanzniveau die Nullhypothese widerlegen, daß die vorhergehende und die gegenwärtige Differenzmetrik aus derselben Verteilung gezogene Proben sind?
In beiden Fällen können entweder pixelbasierende oder verteilungsbasierende Differenzmetriken benutzt werden. Die zugrunde liegende Verteilung im zweiten Fall muß jedoch nicht im voraus bekannt sein. Als nächstes wird jede Formulierung ausführlicher erläutert.
Wenn man Fall 1 betrachtet, lassen sich die Arbeiten an der Modellierung von Bilddifferenzsignalen in die 60er Jahre zurückverfolgen. Seyler untersuchte als erster die Beschaffenheit von Bilddifferenzsignalen und zeigte, daß die Gammaverteilung eine gute Passung für die Wahrscheinlichkeitsdichtefunktion des Großteils an Pixeln bietet, deren Änderung über einem Schwellwert liegt. Siehe A. J. Seyler, "Probability Distributions of Television Frame Differences" (Wahrscheinlichkeitsverteilungen von Fernsehbilddifferenzen), Proceedings of the I. R. E. E. Australia, S. 355-366, November 1965. Ein analytischer Ausdruck wird für die Wahrscheinlichkeitsdichtefunktionen abgeleitet, die sich den experimentell aufgezeichneten Bilddifferenzverteilungen nähern und ist einfach folgendes:
wobei der Bruchteil von Pixeln ist, deren Änderung oberhalb eines Schwellwerts liegt, und die Parameter α und β werden durch das berechnete Mittel u und die Standardabweichung σ der experimentellen Verteilung wie folgt gegeben
Es ist jedoch nicht klar, wie empfindlich diese Schlußfolgerung für die Wahl von Schwellwerten ist. Ein alternatives Modell für Bilddifferenzsignale ist, daß die entsprechende Differenz
an Pixelstelle (i,j) einer Gaußschen Verteilung mit Mittelwert Null mit Varianz σ folgt. Der unbekannte Parameter σij kann direkt aus der Bildfolge geschätzt werden. Zur Vereinfachung des Modells wird oft angenommen, daß die Zufallsvariablen unabhängig identisch verteilt (independently identically distributed - i.i.d.) sind und daher ist σi,j = σ für alle (i,j).
Dementsprechend wird in T. Aach, A. Kaup und R. Mester "Statistical Model-Based Change Detection in Moving Video" (Statistische modellbasierende Änderungserkennung in Bewegtbildvideo), Signal Processing, 31, S. 165-180, 1993, gezeigt, daß
einer Verteilung χ² genügt, mit derselben Anzahl von Freiheitsgraden wie der Anzahl von Pixeln im Bild.
dij, kann auch so modelliert werden, daß es einer Laplace-Verteilung genügt, d. h.
p (dij) = γ/2 exp{-γ|dij|}
wobei γ = 2/σ und σ² die Varianz dieser Wahrscheinlichkeitsdichtefunktion ist. In Aach et al. op. cit. wird dann gezeigt, daß p(2Σγ dij einer Verteilung χ² folgt, mit zweimal so vielen Freiheitsgraden wie der Anzahl von Pixeln im Bild.
Unter den verteilungsbasierenden Differenzmetriken basiert die unter Verwendung von Gleichung (1) erstellte Differenzmetrik auf der Annahme, daß Bilder aus N(ut,σt) gezogene Proben sind. Diese Metrik ist im wesentlichen das Maximum-Likelihood-Verhältnis von L(H&sub1;)/L(H&sub0;) wobei L(x) die Wahrscheinlichkeit des Ereignisses x ist und
H&sub0;: Bilder t-1 und t aus derselben Verteilung N(ut-1, σt-1) kommen
H&sub1;: Bilder t-1 und t aus unterschiedlichen Verteilungen N(ut-1, σt-1) und N(ut, σt) kommen.
Für die unter Verwendung von Gleichung (2) und (3) erstellte Differenzmetrik läßt sich auch zeigen, daß beide der Verteilung χ² genügen. Siehe J. D. Gibbons und S. Chakraborti, Nonparametric Statistical Inference, Marcel Dekker, Inc., 1992. Der χ²-Test erkennt, ob eine beobachtete Frequenzverteilung in einer Probe aus der angenommenen theoretischen Verteilung entsteht. Solche Verteilungen könnten eine echt binomiale, eine Poisson-, eine normale oder irgendeine bekannte Art von Verteilung in der Gesamtheit sein. Normalerweise sind die Parameter dieser Verteilung nicht bekannt. Es läßt sich zeigen, daß, wenn s Parameter durch das Maximum-Likelihood- Verfahren geschätzt werden, die Grenzverteilung von
die von χ² mit N-s-1 Freiheitsgraden ist.
Für den Fall 2 ist der am häufigste benutzte statistische Ansatz dieser Art der Kolmogorov-Smirnov- Test. Der Kolmogorov-Smirnov-Test befaßt sich mit der Übereinstimmung von zwei Mengen beobachteter Werte und die Nullhypothese ist, daß zwei Proben aus Gesamtheiten mit derselben Verteilungsfunktion F(x) kommen. Es läßt sich zeigen, daß die Testgröße dt nach Gleichung (4)
Prob(dt > Kα 2/N) = α
genügt, wobei Kα eine Konstante darstellt, die von dem Signifikanzniveau α abhängt und in Tabellenform aus den meisten Statistikbüchern ersichtlich ist. N ist die Größe des Bildes, an dem die Statistik gesammelt wird.
Ungleich dem oben besprochenen Test nimmt der Kolmogorov-Smirnov-Test keine a-priori-Informationen über die Art von Verteilungsfunktionen an.
Die Entscheidungsstufe ist oft so aufgebaut, daß sie erkannte Cuts beseitigt, die aufgrund von Blitzlicht oder langsamer/schneller Bewegung in der Szene falsche Positivwerte sind. Die Liste erkannter Cut-Bilder ist in einem durch den gestrichelten Kasten im Anhang an den Entscheidungsschritt in der Fig. 1 gezeigten Verzögerungsspeicher gespeichert. Das Kriterium gibt gewöhnlich an, daß der Mindestabstand zwischen zwei Cuts größer als eine voreingestellte Zahl sein muß.
Die meisten bestehenden Ansätze beruhen auf voreingestellten Schwellwerten oder unzutreffenden Annahmen, die ihre Anwendbarkeit auf einen begrenzten Bereich von Videoarten herabsetzen. Beispielsweise sind häufig unrichtige Annahmen darüber gemacht worden, wie Szenen in Videos miteinander verbunden sind, die die Realitäten der Herstellung und des Schneidens von Filmen/Videos außer Acht lassen. Oft ist die nichtstationäre Beschaffenheit des Cut-Erkennungsproblems und auch die Tatsache, daß viele Videos von Filmen stammen, in der Auslegung ihres Cut- Erkennungsalgorithmus unberücksichtigt geblieben.
Im folgenden Abschnitt wird die Cut- Erkennungsaufgabe aus mehreren verschiedenen Gesichtspunkten untersucht. Da die meisten Szenen und Szenenänderungen absichtlich von Film-/Videoregisseuren erzeugt werden, ist es sehr wichtig, die gewöhnlich von Film-/Video-Produktions- und Schnittprofis benutzten Verfahren zu verstehen. Man bekommt dann einen Überblick darüber, was für Arten von Szenen und Cuts in Filmen/Videos vorkommen könnten. Auch werden die üblichen Verfahren zur Umwandlung von Filmen in Videos untersucht. Dieses Verständnis ist von großer Bedeutung bei der Entwicklung eines robusten Cut-Erkennungsalgorithmus. Abschließend werden verschiedene, durch bestehende Verfahren gemachten Annahmen erläutert und es wird eine erfindungsgemäße Lösung beschrieben.
Auf dem Gebiet der Film-/Videoproduktion bestehen einige wenige Szenenklassifikationen für Regisseure, Kameraleute und Cutter, so daß sie dieselbe Sprache benutzen, wenn sie über bestimmte Szenen sprechen. In den meisten Filmen/Videos gibt es drei typische Szenen:
- statische Szenen, die ahne Kamerabewegung aufgenommen werden.
Die verschiedenen Arten von statischen Szenen werden in fünf Kategorien eingestuft:
Großaufnahme, Nahaufnahme, halbnah, Halbtotale und Totale. Verschiedene statische Szenen bewirken unterschiedlich große Änderungen von Bild zu Bild. Beispielsweise erzeugt die Bewegung eines Objekts in einer Nahaufnahme bedeutendere Änderungen im Vergleich mit einer halbnahen oder totalen Szene.
- Kamera bewegt sich Zu den verschiedenen Arten von Kamerabewegungen gehören Zoom, Neigungen und Schwenkungen oder eine Mischung dieser. Die Änderung von Bild zu Bild ist eine Funktion der Geschwindigkeit, mit der sich die Kamera bewegt. Beispielsweise bewirkt eine schnelle Kameraschwenkung bedeutendere Änderungen gegenüber einer langsamen Kameraschwenkung.
- Fahraufnahmen, wo die Kamera während der Aufnahme bewegt wird. Zu den beliebtesten Fahraufnahmen gehören Laufaufnahmen, Dollyaufnahmen und Kranaufnahmen. Alle Fahraufnahmen besitzen die Tendenz, Unstetigkeit zu bewirken, besonders wenn sich das verfolgte Objekt zu schnell bewegt. Es ist klar, daß der Änderungsbetrag von Bild zu Bild auch eine Funktion davon ist, wie ruhig die Kamera bei der Verfolgung des Objekts ist.
Da Kamera-Objekt-Bewegung bei verschiedenen Arten von Aufnahmen unterschiedliche Beträge an Intensitätsänderung ergeben, sollte das Kriterium zur Erkennung von Cuts bei der Verarbeitung von unterschiedlichen Arten von Aufnahmen unterschiedlich sein. Sonst könnten viele falsche Positiv- und Negativwerte auftreten und damit die Trefferquote und die Präzisionsrate verringern. Leider sind bei der Art von Aufgabe, an die sich die Offenbarung dieser Erfindung wendet, Szenenarten nicht im voraus bekannt. Die Einstellung der Erkennungskriterien auf unterschiedliche Szenenarten wird daher zu einer der wichtigsten Aufgaben bei der Cut-Erkennung.
Eine weitere wichtige Frage, die betrachtet werden muß, ist, daß viele Vidoes von Filmen übertragen sind, da die beiden mit unterschiedlichen Bildfrequenzen abgespielt werden. Ein üblicher, 3-2- Filmtransport genannter Übertragungsvorgang besteht darin, jedes zweite Filmbild ein wenig länger zu machen. Dieser Vorgang wird oft durch einen Filmgeber durchgeführt und kann viele Cut-Erkennungsalgorithmen beeinflussen. Nach der Fig. 2 gibt es eigentlich vier unterschiedliche Weisen, auf die die 3 : 2-Übertragung stattfinden kann, wie folgt: in der Fig. 2 sind W, X, Y, Z vier Filmbilder, die jeweils zwei Halbbilder enthalten. Durch Manipulation dieser Halbbilder können fünf Videobilder aufgebaut werden. (Oben links) beginnend bei Halbbild 1 alternierend 3 Halbbilder, (oben rechts) beginnend bei Halbbild 1 alternierend 2 Halbbilder, (unten links) beginnend bei Halbbild 2 alternierend 3 Halbbilder, (unten rechts) beginnend bei Halbbild 2 alternierend 2 Halbbilder.
So:
1. beginnend bei Halbbild 1 alternierend 3 Halbbilder, dann 2..3..2..3..2.
2. beginnend bei Halbbild 1 alternierend 2 Halbbilder, dann 3..2..3..2..3.
3. beginnend bei Halbbild 2 alternierend 3 Halbbilder, dann 2..3..2..3..2.
4. beginnend bei Halbbild 2 alternierend 2 Halbbilder, dann 3..2..3..2..3.
Auf jeden Fall bestehen gewisse Videobilder aus zwei Halbbildern mit vollständig anderen (obwohl aufeinanderfolgenden) Bildern darin. Der Digitalisierer kann infolgedessen nur ein Halbbild aus jedem Videobild entnehmen, um gute Bildqualität zu bewahren. Daraus ergeben sich verdoppelte Bilder und beinahe keine Zwischenbilddifferenzen in fünf Bildabständen in allen vier Fällen des 3 : 2-Filmtransports. Für Cut-Erkennungsverfahren, die auf pixelbasierenden Differenzmetriken beruhen, kann dies zu zahlreichen falschen Positivwerten führen. Aus diesem Grund basierten viele bestehende Algorithmen ihre Erkennung auf Differenzmetriken, die im Abstand von fünf oder sieben Bildern um das aktuelle Bild herum zentriert eingesammelt wurden. Man siehe beispielsweise P. Aigrain und P. Joly "The Automatic Real-Time Analysis of Film Editing and Transition Effects and its Applications" (Die automatische Echtzeitanalyse von Filmschnitt- und Übergangseffekten und ihre Anwendungen), Computer and Graphics, Band 18, Nr. 1, S. 93-103, 1994; H. Dubner "Video Logging System and Method Thereof" (Video-Protokollierungssystem und Verfahren dafür), International Patent Classification H04N9/79, 5/76, Anmeldung eingereicht November 1993; T. Koga, "Accurate Detection of a Drastic Change Between Successive Pictures" (Genaue Erkennung einer drastischen Änderung zwischen aufeinanderfolgenden Bildern), US-Patent 5,032,905, 16. Juli 1991. Ein ähnliches Problem tritt in animierten Videos wie Zeichentrickfilmen auf, nur erzeugt es beinahe keine Zwischenbilddifferenzen in beinahe jedem zweiten Bild.
Die meisten Szenenübergänge werden durch Film-/Video-Regisseure erstellt. Vor der Erfindung moderner Schneideeinrichtungen wurde dies häufig auf einem Schnittgerät und einem optischen Printer durchgeführt. Die folgenden sind die häufigsten Arten von Szenenübergängen und Tricks, die durch diese Vorrichtungen erzeugt werden können:
- Aufblenden, die kommende Szene erscheint allmählich aus dem Dunklen
- Abblenden, die abgehende Szene verschwindet allmählich im Dunklen
- Überblenden, umfaßt eine abgehende Szene, die abgeblendet wird und eine kommende Szene, die aufgeblendet wird und die abgehende Szene überlappt
- die kommende Szene wird dazu benutzt, die abgehende Szene buchstäblich mittels einer hartrandigen oder weichrandigen Linie auszuwischen, während die kommende Szene allein und vollständig sichtbar wird
- Klappblende, ein sich verbreitender schwarzer Streifen entweder auf beiden Seiten oder an beiden Oberseiten des Bildrahmens, der die abgehende Szene herausschiebt und gleichzeitig die kommende Szene hereinbringt und damit eine äußerst schnelle Wechsel- oder Drehwirkung erzeugt
- Stoppbild, es wird ein bestimmtes Bild ausgewählt, um es beliebig lange für dramatische oder komödische Wirkung zu wiederholen
- Vertausch der beiden Seiten, ein häufig benutzter Effekt, um Fehlleitung zu berichtigen
- Vorwärts-Rückwärts-Szenenabläufe, das Ende des Cuts wird zum Anfang und der Anfang zum Ende.
- Skip-Frame-Verfahren, das Überspringen von Bildern, um die Handlung zu beschleunigen
- Doppelkopieren, Duplikation von Bildern zum Verlangsamen der Handlung
- Vergrößerung, die Vergrößerung von Bildern zur Beseitigung gewisser unerwünschter Objekte
- Vorwärtsfahrt, die in einer Überblendung in eine andere Fahraufnahme endet
- Repositionierung, Einstellung des ursprünglichen Aufnahmewinkels
- Überlagerung, das Überlappen von zwei oder mehr Szenen, die ungleich denen bei einer Überblendung gleichzeitig von konstanter relativer Dichte sind.
- Montage, eine beliebige Folge von Überlagerungen.
Die moderne Computertechnik ermöglicht noch weitere Arten zur Erzeugung von Szenenübergängen. Die folgenden sind Beispiele:
- Bandschiebeblende, die kommende Szene wird durch horizontale oder senkrechte Balken unter der abgehenden Szene aufgedeckt
- Torblende, die kommende Szene wird von der Mitte aus nach außen unter der abgehenden Szene aufgedeckt
- Mittenübergang, die abgehende Szene spaltet sich in vier Teile und gleitet zur Mitte, um die kommende Szene aufzudecken
- Mittenteilung, die abgehende Szene spaltet sich in vier Teile und gleitet in die Ecke, um die kommende Szene aufzudecken
- Schachbrett, zwei Sätze abwechselnder Kästen werden verschoben, um aufzudecken, wie sich die kommende Szene quer erstreckt, wobei sich die kommende Szene von einem Rand aus erstreckt, so wie die abgehende Szene schrumpft.
Für Übergänge, die durch optisch abrupte gerade Cuts oder Kameraaufnahmeunterbrechungen hergestellt wurden, ist das Cut-Erkennungsproblem eine relativ gut definierte Aufgabe. Die Erkennung von anderen Arten von Übergängen wie beispielsweise Auf- und Abblendungen, Überblendungen, Schiebeblenden, Klappblenden, Überlagerungen, Stopp- oder Standbilder, Vertauschen der beiden Seiten, Vorwärts-Rückwärtsszenenabläufe, Vergrößerungen, Vorwärtsfahrten, Repositionierungen und Skip-Frame-Verfahren sind unter Umständen nicht so einfach. In der Tat können die meisten Szenenübergänge so lang sein, wie ein Regisseur es wünscht, solange wie sie dem Stil, der Stimmung und dem Tempo entsprechen, die in diesem Augenblick im Bild gewünscht werden. Die mit diesen Szenenübergängen verbundenen gesammelten Differenzmetriken sind häufig nicht unterscheidbar von den mit allmählichen Kamerabewegungen verbundenen, es sei denn, man berücksichtigt auch semantische Informationen wie beispielsweise das Bildbewegungsmuster. Man siehe beispielsweise H. Zhang, A. Kankanhalli und S. W. Smoliar "Automatic Parsing of Full-Motion Video" (Automatische Zerlegung von Bewegtbildvideo), ACM Multimedia Systems, 1, S. 10-28, 1993.
Viele gegenwärtige Verfahren versuchen, verschiedene Szenenübergänge zu modellieren. Man siehe beispielsweise P. Aigrain und P. Joly, "The Automatic Real-Time Analysis of Film Editing and Transition Effects and its Applications" (Die automatische Echtzeitanalyse von Filmschnitt- und Übergangseffekten und ihre Anwendungen), Computer and Graphics, Band 18, Nr. 1, S. 93-103, 1994; A. Hampapur, R. Jain und T. Weymouth, "Digital Video Segmentation" (Digitale Video-Segmentierung), Proc. ACM Multimedia Conference, S. 357-363, 1994; J. Meng, Y. Juan und S.-F. Chang, "Scene Change Detection in a MPEG Compressed Video Sequence" (Szenenänderungserkennung in einer MPEG- komprimierten Videofolge), SPIE Band 2419, Digital Video Compression Algorithms and Technologies, S. 14-25, 1995; 3PEG ISO/IEC JTC1 SC29 WG1, JPEG, ISO/IEC 10 918; T. Koga, "Accurate Detection of a Drastic Change Between Successive Pictures" (Genaue Erkennung einer drastischen Änderung zwischen aufeinanderfolgenden Bildern), US-Patent 5,032,905, 16. Juli 1991 MPEG ISO/IEC JTC1 SC2: B.-L-Yeo und B. Liu, "Rapid Scene Analysis on Compressed Video" (Schnelle Szenenanalyse an komprimiertem Video) erscheint noch in IEEE Trans. on Circuits and Systems for Video Technology, 1995. Sie nehmen häufig an, daß sowohl die Eingangsszenen als auch die Ausgangsszenen statische Szenen sind und der Übergang nicht länger als eine halbe Sekunde dauert. Diese Art von Modell ist zu sehr vereinfacht, um allmähliche Szenenübergänge zu modellieren, die häufig in Filmen/Videos vorkommen.
Eine weitere Annahme, die häufig von Forschern gemacht wird, ist, daß das an jedem einzelnen Pixel berechnete Bilddifferenzsignal durch eine stationäre unabhängig identisch verteilte Zufallsvariable modelliert werden kann, die einer bekannten Wahrscheinlichkeitsverteilung wie zum Beispiel der Gaußschen oder der Laplace genügt. Man siehe beispielsweise H. Zhang, A. Kankanhalli und S. W. Smoliar, "Automatic Parsing of Full-Motion Video" (Automatische Zerlegung von Bewegtbildvideo) ACM Multimedia Systems, 1, S. 10-28, 1993. Diese Annahme ist im allgemeinen nicht wahr, wie die Fig. 3 zeigt, die das Histogramm eines typischen Zwischenbild- Differenzbildes zeigt, das nicht einer Szenenänderung entspricht. Man beachte, daß sich die Form von einer langsamen (links) zu einer schnellen (rechts) Kamerabewegung verändert. Weder eine Gaußsche noch eine Laplace-Verteilung paßt gut zu beiden Kurven. Eine Gammafunktion paßt gut zur linken Kurve, aber nicht zur rechten Kurve.
Durch diese Tatsache werden Cut-Erkennungsansätze widerlegt, die auf χ²-Tests basieren, da diese Tests statistisch aus der obigen Annahme abgeleitet sind. Man siehe beispielsweise G. Casella und R. L. Berger, Statistical Inference (Statistische Folgerung), Duxbury Press, 1990.
Zusätzlich nehmen bestehende Verfahren an, daß Zeitreihen-Differenzmetriken stationär sind und lassen die Tatsache vollständig außer Acht, daß derartige Metriken hochkorrelierte Zeitsignale sind.
Es wird hier anerkannt, daß pixelbasierende und verteilungsbasierende Differenzmetriken unterschiedlich auf unterschiedliche Arten von Szenen und Szenenübergängen reagieren. Beispielsweise ist die erstere sehr empfindlich für Kamerabewegungen, aber ein sehr guter Anzeiger für Szenenänderungen. Andererseits sind verteilungsbasierende Metriken relativ unempfindlich für Kamera- und Objektbewegung, können aber wenig Reaktion erzeugen, wenn die beiden Szenen ganz anders aussehen, aber ähnliche Verteilungen aufweisen. Es ist eine Aufgabe der vorliegenden Erfindung, die beiden Maße bei der Cut-Erkennung zu kombinieren.
Ungleich bestehenden Verfahren, die keine Vorstellung von Zeitreihen oder Nichtstationärität aufweisen, behandelt die vorliegende Erfindung eine Folge von Differenzmetriken als nichtstationäre Zeitreihensignale und modelliert die Zeittendenz deterministisch. Die Folge von Differenzmetriken sind ungeachtet ihrer Berechnungsweise genau wie jede anderen ökonomischen oder statistischen Daten, die über die Zeit gesammelt werden. Bei dieser Ansicht werden sowohl Szenenänderungen als auch der 3 : 2- Filmtransportprozeß beide Beobachtungsausreißer in der Zeitreihe erzeugen, während der allmähliche Szenenübergang und allmähliche Kamerabewegungen Innovationsausreißer erzeugen werden. Fox definiert den Beobachtungsausreißer als einen, der durch einen groben Beobachtungsfehler oder Aufzeichnungsfehler verursacht wird und nur eine einzige Beobachtung beeinflußt. Siehe A. J. Fox, "Outliers in Time Series" (Ausreißer in Zeitreihen), Journal of the Royal Statistical Society, Serie B, 34, S. 350-363, 1972.
Ähnlicherweise ist der Innovationsausreißer einer, der der Situation entspricht, bei der eine einzige "Innovation" extrem ist. Diese Ausreißerart beeinflußt nicht nur die bestimmte Beobachtung, sondern auch nachfolgende Beobachtungen. Ein typisches Modell, das Beobachtungsausreißer darstellt (tritt bei t = q auf), ist
dt = f(d-r, dt-r+1, ..., dt) + ut falls t ≠ q Gl. 8
dt = f(dt-r, dt-r+1, ..., dt) + ut + Δ sonst
wobei t t den Zeitindex darstellt, Δ der Ausreißer ist, dt = f(dt-r, dt-r, ..., dt) den Trend in der Reihe modelliert und
ut = αrdt-r + zt (t = p + 1, ..., n) Gl. 9
In der Gleichung (9) sind αI autoregressive Parameter und die {zt} sind unabhängig N(0, σ²z) (normale Verteilung mit Mittelwert Null mit Varianz σ²z.
Das Modell für Innovationsausreißer ist
dc = f(dt-r, dt-r+1, ..., dt) + αrdt-r + Δc + Zt Gl. 10
wobei αr und {zt} wie bei Gleichung (9) definiert sind und der Ausreißer Δt dt und damit nachfolgende Beobachtungen dt+1, dt+2, ..., dn beeinflußt.
Es gibt standardmäßige Verfahren in der Literatur, die beide Ausreißer erkennen. Siehe beispielsweise B. Abraham und A. Chuang, "Outlier Detection and Time Series Modeling" (Ausreißererkennung und Zeitreihen-Modellierung), Technometrics, Band 31, Nr. 2, S. 241-248, Mai 1989; A. J. Fox, "Outliers in Time Series" (Ausreißer in Zeitreihen) der Royal Statistical Society, Reihe B, 34, S. 350-363, 1972; L. K. Hotta und M. M. C. Neves, "A Brief Review of Tests for Detection of Time Series Outliers" (Eine kurze Übersicht über Prüfungen für die Erkennung von Zeitreihenausreißern), ESTADISTICA, 44, 142, 143, S. 103-148, 1992.
Diese Standardverfahren lassen sich jedoch aus den folgenden drei Gründen noch nicht direkt auf das Cut-Erkennungsproblem anwenden. Als erstes erfordern die meisten Verfahren intensive Berechnung, beispielsweise kleinste Quadrate, zum Schätzen von Zeittrend und autoregressiven Koeffizienten. Dieser Rechenaufwand ist allgemein unerwünscht. Zweitens könnten die durch Zeitlupe und den 3 : 2- Filmtransportprozeß erzeugten Beobachtungsausreißer so häufig wie einmal in jeder zweiten Probe auftreten, wodurch die Schätzung des Zeittrends und autoregressiven Koeffizienten zu einem äußerst schwierigen Vorgang wird. Abschließend erfordert die Lokalisierung von allmählichen Szenenübergängen nicht nur Erkennung von Innovationsausreißern sondern auch einen besonderen Kamerabewegungsschätzungsschritt, da allmähliche Szenenübergänge und allmähliche Kamerabewegungen in den meisten Fällen nicht unterscheidbar sind.
In der erfindungsgemäßen Lösung werden ein autoregressives Modell nullter Ordnung und eine stückweise lineare Funktion zur Modellierung des Zeittrends benutzt. Mit dieser Vereinfachung müssen Proben sowohl aus der Vergangenheit als auch der Zukunft zur Verbesserung der Robustheit der Zeittrendschätzung benutzt werden. Mehr als die Hälfte der Proben werden verworfen, da die durch Zeitlupe und den 3 : 2-Filmtransportprozeß erzeugten Beobachtungsausreißer so häufig wie einmal in jeder zweiten Probe auftreten könnten. Glücklicherweise sind diese Arten von Beobachtungsausreißern wertmäßig am kleinsten und könnten daher leicht identifiziert werden.
Nach Beseitigung des Zeittrends wird der übrige Wert gegen eine normale Verteilung N(0,σ) geprüft, wobei σ rekursiv oder im voraus geschätzt werden kann.
Um das Cut-Erkennungsverfahren robuster zu machen, wird der Kolmogorov-Smirnov-Test nochmals angewandt, um falsche Positivwerte zu beseitigen. Dieser Test wird deshalb gewählt, da er keine a-priori- Kenntnis der zugrunde liegenden Verteilungsfunktion annimmt. Die klassische Kolmogorov-Smirnov-Testprozedur vergleicht die berechnete Testmetrik mit einem voreingestellten Signifikanzniveau (normalerweise bei 95%). Es ist von einigen Forschern zur Erkennung von Cuts in Videos benutzt worden. Siehe beispielsweise I. K. Sethi und N. Patel "A Statistical Approach to Scene Change Detection" (Ein statistischer Ansatz zur Szenenänderungserkennung), SPIE Band 2420, Storage and Retrieval for Image and Video Databases III, S. 329-338, 1995. Bei dieser Verwendung eines einzigen vorausgewählten Signifikanzniveaus wird die nichtstationäre Beschaffenheit des Cut-Erkennungsproblems vollständig außer Acht gelassen. Es wird hier anerkannt, daß der Kolmogorov-Smirnov-Test nur dann richtig benutzt wird, wenn er die nichtstationäre Beschaffenheit des Problems berücksichtigt. Anders gesagt sollte das Signifikanzniveau automatisch auf unterschiedliche Arten von Videoinhalt eingestellt werden.
Eine Art zur Darstellung von Videoinhalt besteht in der Verwendung von Messungen sowohl im Raumbereich als auch im Zeitbereich zusammen. Beispielsweise ist der Bildkontrast eine gute Raumbereichsmessung, da der Betrag von Intensitätsänderungen über zwei benachbarte Bilder den Videoinhalt in Zeitbereichen mißt. Die Einstellung sollte so durchgeführt werden, daß
- je höher der Bildkontrast (das heißt, je geringer das Signifikanzniveau) ist, desto empfindlicher sollte der Cut-Erkennungsmechanismus sein, und
- je mehr Änderungen in zwei aufeinanderfolgenden Bildern auftreten, desto unempfindlicher sollte der Erkennungsmechanismus (das heißt, desto höher sollte das Signifikanzniveau) sein.
Auch kann der klassische Kolmogorov-Smirnov- Test nicht zwischen der Totalen und der Nahaufnahme derselben Szene unterscheiden. Um solchen Übergängen vorzubeugen, benutzt die vorliegende Erfindung einen hierarchischen Kolmogorov-Smirnov-Test. Bei diesem hierarchischen Kolmogorov-Smirnov-Test wird jedes Bild in vier rechteckige Gebiete gleicher Größe eingeteilt und der klassische Kolmogorov-Smirnov-Test wird auf jedes Paar von Gebieten und auch auf das gesamte Bild angewandt. Dieser Test erzeugt daher fünf Binärzahlen, die anzeigen, ob eine Änderung im Gesamtbild sowie auch in jedem der vier Teilbilder besteht.
Abschließend wird das Testergebnis nur in einem qualitativen Sinn benutzt, anstatt diese fünf Binärzahlen direkt zur Beseitigung von falschen Positivwerten zu benutzen. Die Signifikanz im Testergebnis des Szenenänderungsbildes wird mit der der benachbarten Bilder verglichen. Man wird diese Abänderungen besser in einem späteren Teil der Beschreibung verstehen.
Trotz vieler Behauptungen und Versuche in der Literatur hinsichtlich der Erkennung von allmählichen Szenenänderungen ist es nicht möglich, zwischen allmählichen Szenenübergängen und allmählichen Kamerabewegungen zu unterscheiden, da die mit beiden Fällen verbundenen Differenzmetriken häufig nicht voneinander zu unterscheiden sind. Zhang et al. stellen einen hybriden Algorithmus vor, der versucht, zwischen allmählichen Szenenübergängen und allmählichen Kamerabewegungen aufgrund einer Kamerabewegungsanalyse zu unterscheiden. Siehe H. Zhang, C. Y. Low und S. W. Smoliar, "Video Parsing and Browsing Using Compressed Data" (Videozerlegung und Browsing unter Verwendung komprimierter Daten), Multimedia Tools and Applications, 1, S. 89-111, 1995. Es ist jedoch zu beachten, daß Kamerabewegungsschätzung mehr als ein Jahrzehnt lang ein aktiver Forschungsbereich im Computer-Sehen gewesen ist und noch kein verläßlicher Bewegungsschätzungsalgorithmus vorliegt. Im Zusammenhang mit der vorliegenden Erfindung wird hier anerkannt, daß, um Zugriff auf fehlerkannte Szenen zu bieten, ein Cut-Browser erforderlich ist, da kein einzelner Cut-Erkennungsalgorithmus eine Trefferquote von 100% liefern kann. Dieser Browser könnte auch zur Identifizierung allmählicher Szenenübergänge benutzt werden. Die herausfordernste Aufgabe bei der Konstruktion eines solchen Geräts ist, wie der Browser den Benutzern Informationen bietet, ohne das gesamte Video abspielen zu müssen.
Um einem Benutzer Informationen zu bieten, der dann verpaßte und fehlerkannte Szenen identifizieren kann, sollte dieser Browser die folgenden drei Eigenschaften besitzen:
Als erstes muß er Informationen bieten, die sich von dem, was der automatische Cut-Erkennungsalgorithmus aus dem Video gewinnt, unterscheiden. Zusätzlich sollte er nicht versuchen, dem Benutzer interpretierte Informationen zu bieten, da alle derartigen Informationen eine Fehlerquelle sein könnten. Abschließend sollte der Browser schnell und prägnant sein und ein anderes Abstraktionsniveau bieten, so daß das Erfordernis zum Abspielen des gesamten Videos vermieden werden kann.
Im Rahmen der vorliegenden Erfindung umfaßt ein Browser einen Video-Player, einen Video-Browser und einen Cut-Browser. Siehe Fig. 4. Die Browsereinrichtung bildet den Gegenstand von EP-A-780844 mit dem Titel CUT BROWSING AND EDITING APPARATUS (Cut-Browser- und Schnittgerät) im Namen der gegenwärtigen Erfinder. Der Video-Browser bildet den Gegenstand von US-Patent US-A-5606655 mit dem Titel REPRESENTING CONTENTS OF A SINGLE VIDEO SHOT USING RFRAMES (Darstellung des Inhalts einer einzigen Videoszene unter Verwendung von R-Bildern) im Namen von Arman et al.
Diese drei Bestandteile bieten drei verschiedene Abstraktionsebenen. Weitere Einzelheiten werden weiter unten geboten, aber in Kürze bietet der Cut-Browser zwei Querschnittsbilder, eines davon in einer horizontalen Richtung und das andere in einer senkrechten Richtung des Videovolumens. Jedes Querschnittsbild wird durch Probenahme einer Zeile (oder Spalte) aus jedem Bild und Verringern der Informationsmenge von einem zweidimensionalen Bild zu zwei eindimensionalen Bildstreifen nach der Darstellung in Fig. 5 aufgebaut, wobei (a) zwei Querschnitte in Videovolumen und (b) ein aus zwei Querschnitten bestehendes Zeit-Raum-Bild zeigt.
Die horizontalen und senkrechten Querschnittsbilder werden im Cut-Browser in ein Bild kombiniert, das entsprechend der Liste erkannter Szenen in zwei Bänder segmentiert ist. Diese Darstellung bietet eine Abstraktionsebene, die gerade dazu ausreicht, zu offenbaren, ob eine verpaßte oder fehlerkannte Szene vorliegt.
Mit dieser Darstellung kann der Benutzer den Inhalt des Videos leicht durchsuchen, um zu entscheiden, ob das Cut-Erkennungsverfahren eine Szene verpaßt oder fehlerkannt haben könnte, und um Cuts in Vorbereitung auf einen Multimedieninhalt zu erstellen oder zu beseitigen.
Dieser bestimmte Satz von drei Abstraktionsebenen wird aus folgenden Gründen gewählt. Als erstes muß dazu das Originalvideo gehören, da es die einzige verfügbare rohe Information ist. Niemand kann sich jedoch leisten, Informationen aus dem Originalvideo direkt zu durchsuchen, da Videowiedergabe eine sehr zeitraubende Aufgabe ist. Das ist ein Grund dafür, die repräsentativen Bilder (R-Bilder) jeder erkannten Szene einzubeziehen. Zur Bereitstellung dieser Abstraktionsebene kann jedes automatische Cut- Erkennungsverfahren benutzt werden. Da zweitens kein Cut-Erkennungsverfahren eine Trefferquote von 100% bietet, wird es immer verpaßte oder fehlerkannte Szenen geben. Um dem Benutzer einen Anhaltspunkt zu bieten, um zu vermeiden, daß er bei der Durchsuchung gewünschter Videoclips durch die Unvollkommenheit eines Cut- Erkennungsverfahrens (oder beliebigen automatischen Verfahrens) beeinflußt wird, sollten zusätzliche Informationen bereitgestellt werden, die die oben erwähnten Eigenschaften besitzen:
- sie müssen vollständig anders sein und unabhängig davon, was der automatische Cut- Erkennungsalgorithmus aus dem Video gewinnt,
- sie sollten rohe Informationen sein, aber nicht das Originalvideo sein,
- sie sollten prägnant sein.
Die Überzeugung ist, daß das Querschnittsbild die beste Wahl ist. Ein Querschnittsbild ist ein direkt aus dem Originalvideo erzeugtes Bild. In der vorliegenden Ausführungsform wird eines in der horizontalen und das andere in der senkrechten Richtung des Videovolumens ausgewählt, obwohl man im allgemeinen eine beliebige Anzahl von Richtungen auswählen kann. Der Vorgang des Aufbauens eines Querschnittsbildes ist in Fig. 5 dargestellt. Das horizontale (senkrechte) Querschnittsbild wird durch Abtasten der mittleren Zeile (oder der mittleren Spalte) aus jedem Bild und Sammeln aller Abtastwerte über die Zeit aufgebaut. Um eine vollständige Ansicht beider Querschnittsbilder herzustellen, werden sie in ein Bild kombiniert und das Bild wird dann in zwei Bänder entsprechend der Liste erkannter Szenen segmentiert.
Diese Darstellungsart bietet eine Abstraktionsebene, die die Kontinuität von Videobildern offenbart. Wenn beispielsweise eine verpaßte Szene vorliegt, die das Ergebnis eines optisch abrupten Cuts oder einer Kameraaufnahmeunterbrechung ist, ist wie in Fig. 6(a) gezeigt ein deutlich diskontinuierliches Muster erkennbar. Bei Cuts, die mit allmählichen Szenenübergängen wie beispielsweise Überblendungen verbunden sind, ist ein verschmiertes diskontinuierliches Muster wie in den unteren zwei Bildern der Fig. 6(b) gezeigt offenbart.
Es werden hier fünf Komponenten verwendet: ein Video-Player, ein Video-Browser, ein Cut-Browser, ein R-Bild-Generator und ein Querschnitts-Generator. Ihr Verhältnis zueinander ist in Fig. 4 dargestellt. In dieser Figur kann die Videoquelle entweder analoges oder komprimiertes Digitalvideo sein und das automatische Cut-Erkennungsmodul kann ein beliebiges automatisches Cut-Erkennungsverfahren sein, solange es eine Liste von Szenen in Bildnummern ausgibt. Der Video-Player, der Video-Browser und der Cut-Browser sind drei Hauptkomponenten, die durch zwei andere Komponenten, den R-Bild-Generator und den Querschnitts- Generator, unterstützt werden. Die Tätigkeiten in allen Komponenten sind vollständig synchronisiert.
Der R-Bild-Generator nimmt die Szenenliste und auch das Originalvideo und erzeugt Miniaturbilder, die jede Szene darstellen. Jedesmal wenn die Szenenliste aktualisiert wird, aktualisiert er die Liste von Miniaturbildern. Der Video-Player spielt das Originalvideo ab und nimmt entweder vom Video-Browser oder vom Cut-Browser kommende Anforderungen entgegen. Die Wiedergabe kann bei jedem Videobild beginnen. Um das gewünschte Videobild zu lokalisieren, wird entweder der Zeitcode oder der Byte-Offset benutzt, je nachdem, ob die Videoquelle ein Analogvideo bzw. ein komprimiertes Digitalvideo ist.
Der Video-Player besitzt auch eine VCR-ähnliche Benutzeroberfläche, die Funktionen wie Kurzstopp, Wiedergabe, Zeitlupe, Schnellvorlauf und Rücklauf implementiert. Auch bietet sie eine Szenensprungfähigkeit, mit der der Benutzer Szenen überspringen kann, die durch das automatische Cut- Erkennungsverfahren erkannt werden.
Der Video-Browser zeigt eine Liste von Miniaturbildern an, die jede erkannte Szene darstellen. Damit kann ein Benutzer schnell ein Video durchsehen, um den interessierenden Ausschnitt zu finden. Der gewünschte wird dann gefunden, wenn er sich in der Liste erkannter Szenen befindet. Der Video-Browser positioniert sich richtig, indem er Informationen entweder vom Video-Player oder vom Cut-Browser entgegennimmt. Wenn ein Video abgespielt wird oder das Querschnittsbild angeklickt wird, wird das repräsentative Bild der zugehörigen Szene hervorgehoben. Wenn das Querschnittsbild durchläuft, läuft die Liste von Miniaturbildern entsprechend durch.
Um Informationen für verpaßte oder fehlerkannte Szenen zu bieten, stellt der Cut-Browser das aus dem rohen Video erzeugte Querschnittsbild dar. In der obigen Beschreibung wurden die Arten von Mustern, die im Querschnittsbild erscheinen könnten, wenn eine Szenenänderung vorkommt, beschrieben und erläutert. Diese Muster von Querschnittsbildern bieten nützliche Informationen für die Handidentifizierung von verpaßten oder fehlerkannten Szenen. Wenn ein Benutzer das Querschnittsbild anklickt, bildet der Cut-Browser die Mausstelle auf eine Bildnummer ab und sendet die Anforderung an sowohl Video-Player als auch Video- Browser. Das Video wird von diesem Bild ab abgespielt und das zugehörige repräsentative Bild im Video-Browser wird hervorgehoben.
Die vorhergehende beispielhafte Ausführungsform ist mit Hinblick auf zwei Querschnittsbilder beschrieben worden; es liegt jedoch im Rahmen der Erfindung, daß eine Mehrzahl solcher Bilder, die größer als zwei sein kann, verwendet werden kann.
Die Benutzeroberfläche der vorliegenden Erfindung ist in Fig. 15 dargestellt. Im Betrieb werden anfangs drei Fenster auf dem Bildschirm angezeigt. Zum Durchsuchen des Inhalts des Videos würde der Benutzer jedes repräsentative Bild im Video-Browser daraufhin untersuchen, ob es die gewünschte Szene ist. Wenn die Liste von Minieturbildern durchläuft, wird der Inhalt des Cut-Browsers aktualisiert, damit er mit dem hervorgehobenen repräsentativen Bild übereinstimmt. Der Benutzer würde deutlich sehen, ob zwischen der aktuellen und der nächsten Szene irgendeine verpaßte Szene ist. Wenn der Benutzer Zweifel hat, kann er einfach die Stellen anklicken, die eine verpaßte Szene im Cut-Browser anfährt, um den Inhalt im rohen Video zu betrachten. Um zu entscheiden, ob das Cut- Erkennungsverfahren eine Szene verpaßt oder fehlerkannt haben könnte, könnte der Benutzer einfach das Querschnittsbild im Cut-Browser untersuchen. Wenn der Benutzer irgendein Muster sieht, das eine verpaßte oder fehlerkannte Szene darstellen könnte, würde der Benutzer dann die Stelle im Cut-Browser anklicken, um sich den Inhalt des rohen Videos anzusehen.
Der Cut-Browser bietet auch die Schnittfähigkeit. Diese Schnittfunktion ist äußerst nützlich zum Verfassen von inhaltsindexierten Multimediastoffen. Sie ermöglicht einem Benutzer, eine beliebige Szene in zwei zu teilen oder beliebige zwei Szenen in eine zu verschmelzen, über Anklicken mit einer Maus oder einem Knopf. Wenn dieses Ereignis geschieht, wird das Querschnittsbild in zwei Bänder umorganisiert und die Szenenliste aktualisiert. Der R- Bild-Generator aktualisiert dann die Liste repräsentativer Bilder.
Beispielsweise ist, wenn sich alle Videobilder in derselben Szene befinden und alle Szenen richtig erkannt worden sind, ein klares fortlaufendes Muster in diesem Querschnittsbild ersichtlich wie oben anhand des in Fig. 6 gezeigten Beispiels erläutert.
Zusätzlich wird keine Interpretation geboten, da sie ebenfalls Rohbilddaten sind, und kein weiterer Fehler könnte daher eingeführt werden.
Die in den vorherigen Abschnitten beschriebene Problemanalyse ist in die vorliegende erfindungsgemäße Lösung der Cut-Erkennungsaufgabe eingebaut, die eine Einteilung eines Videos in eine Menge von Szenen mit optisch abrupten Cuts oder Kameraaufnahmenunterbrechungen umfaßt. Fig. 7 zeigt ein Flußdiagramm eines Cut-Erkennungsalgorithmus entsprechend der Erfindung.
Ungleich den Verfahren des Standes der Technik, die entweder eine pixelbasierende oder verteilungsbasierende Differenzmetrik benutzen, integriert die vorliegende Erfindung beide Informationsarten in ein neues Erkennungsschema. Die Erfindung enthält eine adaptive Maschine, um die Erkennungsanordnung mit der Fähigkeit zu versehen, sich automatisch auf verschiedene Arten von Videoinhalt einzustellen. Das Ergebnis von der automatischen Cut-Erkennung wird dem Benutzer über eine Cut-Browsereinrichtung dargeboten, wo drei Aufgaben durchgeführt werden können: den Inhalt des Videos zu durchsuchen, um zu entscheiden, ob das Cut-Erkennungsverfahren eine Szene verpaßt oder fehlerkannt haben könnte, und um Cuts zu erzeugen oder zu beseitigen.
Die Cut-Erkennung wird hier als ein Problem der Zeitreihen-Ausreißererkennung formuliert. Nach der Darstellung in der Fig. 7 kann das System entweder unkomprimiertes oder komprimiertes fortlaufendes Video als Eingabe annehmen. Experimentell ist mit MPEG-1 komprimiertes Video verwendet und eine Folge von Gleichstrombildern unter Benutzung des bei B.-L. Yeo und B. Liu beschriebenen Ansatzes "On the Extraction of DC Sequence from MPEG Compressed Video" ("Über die Ableitung einer Gleichstromfolge aus MPEG-komprimiertem Video"), Proc. of ICIP, Oktober 1995 erzeugt worden. Sowohl die pixelbasierende als auch die verteilungsbasierende Differenzmetrik werden dann aus diesen Gleichstrombildern berechnet (Differenzmetrik- Sammlung), während Videoinhalte gemessen werden, um aktuelle Testkriterien bereitzustellen (Adaption). Informationen von sowohl der verteilungsbasierenden als auch pixelbasierenden Differenzmetrik werden nach Berücksichtigung der durch den Adaptionsschritt bereitgestellten neuen Testkriterien (Signifikanzniveau) verschmolzen (Erkennung). Abschließend wird eine Liste von in Frage kommenden Szenenänderungsbildern erzeugt und gefiltert, woraus sich die abschließende Szenenänderungs-Bildliste ergibt (Entscheidung).
Gleichstrombilder sind reduzierte Bilder, die aus der Sammlung von skalierten Gleichstromkoeffizienten in zwischencodiertem DCT-komprimiertem Video gebildet werden. Solche Bilder können direkt aus JPEG- oder Bewegtbild-JPEG-Videos konstruiert werden. Für MPEG- und H.261-Videos erfordert eine schnelle Rekonstruierung von Gleichstrombildern aus bewegungskompensierten Bildern einige Annäherungsgrade. Das bei B.-L. Yeo und B. Liu, "On the Extraction of DC Sequence from MPEG Compressed Video" ("Über die Ableitung einer Gleichstromfolge aus MPEG-komprimiertem Video"), Proc. of ICIP, Oktober 1995, beschriebene Verfahren wird hier darauf angewandt, Gleichstrom-Luminanzbilder aus jedem Einzelbild von MPEG-Video zu erzeugen, während die Chrominanzkomponenten einfach verworfen werden. Kurz gesagt gewinnt das Verfahren das bewegungskompensierten Bildern entsprechende Gleichstrombild direkt aus dem komprimierten Strom auf folgende Weise. Das Verfahren lokalisiert zuerst für jeden interessierenden Block vier Originalnachbarblöcke, aus denen der aktuelle interessierende Block abgeleitet wird. Es nähert dann das Gleichstromglied jedes interessierenden Blocks um die gewichtete Summe der Gleichströme der vier Originalnachbarblöcke an, wobei die Gewichte einfach der Bruchteil des vom gegenwärtigen Block belegten Bereichs sind.
Es ist jedoch zu beachten, daß dieses Verfahren zur Realisierung der vorliegenden Erfindung nicht notwendig ist. Als Altenative können unkomprimierte Videobilder genommen und unterabgetastet werden, um dieselbe Größe von Bildern zu erzeugen, mit denen die erfindungsgemäße Einrichtung gespeist werden kann.
In diesem Schritt werden sowohl pixelbasierende als auch verteilungsbasierende Differenzmetriken wie in Fig. 8 gezeigt gesammelt, die das Teildiagramm des Differenzmetriksammlungsschrittes zeigt. Nach der Erfindung ist die pixelbasierende Differenzmetrik für jedes Bild t die Summe der absoluten Bilddifferenz,
wobei f den Intensitätswert an Pixelstelle (i,j) zu dem Bild t t darstellt.
Die verteilungsbasierende Differenzmetrik ist die klassische Kolmogorov-Smirnov-Testmetrik, nur daß jeweils eine hier für das gesamte Bild und auch seine vier gleich eingeteilten Teilgebiete berechnet wird.
Der Zweck dieses Schrittes ist, die Erkennungsanordnung mit der Fähigkeit zu versehen, sich automatisch auf verschiedene Videoinhalte einzustellen. Die Fig. 9 zeigt das Teildiagramm des Adaptionsschrittes. Wie in Fig. 9 dargestellt, werden zuerst Statistiken von jedem Gleichstrombild und jedem Paar von Gleichstrombildern gesammelt, um den aktuellen Videoinhalt darzustellen. Dabei handelt es sich um die Bildkontrast- und Bewegungsschätzung. Die Bildkontrastschätzung wird auf Grundlage eines rekursiven Schemas berechnet, um die Einflüsse plötzlicher Beleuchtungsänderungen zu unterdrücken.
Kontrastt = (1-τ) Kontrastt-1+τσt-1,
wobei Sigma_{t-1} σt-1 die Intensitätsvarianzschätzung des Gleichstrombildes zur Zeit t-1 ist und τ gleich 0,6 ist in der vorliegenden beispielhaften Ausführungsform.
Ähnlicherweise wird die Bewegungsschätzung wie folgt berechnet
wobei f der Intensitätswert an Pixelstelle (i,j) des Gleichstrombildes zur Zeit t-1 ist, N die Bildgröße ist und τ gleich 0,6 in der vorliegenden beispielhaften Ausführungsform ist.
Sowohl Bildkontrast- als auch Bewegungsschätzungen werden dann in eine Fuzzy-Maschine übernommen, um ein neues Signifikanzniveau für den hierarchischen Kolmogorov-Smirnov-Test zu berechnen. Die Fuzzy- Maschine benutzt eine quadratische Zugehörigkeitsfunktion, wobei jede Kontrastmessung in vier Klassen (niedrig, mittel, hoch und äußerst hoch), jede Bewegungsschätzung in drei Klassen (langsam, mittel und schnell) und jedes Signifikanzniveau (Kα) in fünf Klassen (hoch, mittelhoch, mittel, mittelniedrig und niedrig) eingeteilt wird, wie in Fig. 10, 11 und 12 gezeigt, die die Zugehörigkeitsfunktionen der Fuzzy- Maschine nach der Erfindung darstellen. Fig. 10, 11 und 12 zeigen die Zugehörigkeitsfunktionen von Kontrastschätzung, Bewegungsschätzung bzw. Kα, das zum Signifikanzniveau proportional ist.
Auf Definitionen von Zugehörigkeitsfunktionen basierend werden die Fuzzy-Regeln in einem einfachen Format WENN/DANN angegeben, wobei Werte unter Verwendung von UND (Minimum) oder ODER (Maximum)- Operationen kombiniert werden. Alle Regeln sind in der folgenden Tabelle 1 aufgeführt.

TABELLE 1

WENN Kontrast niedrig und Bewegung langsam ist, DANN ist Signifikanzniveau mittelwertig WENN Kontrast mittelwertig und Bewegung langsam ist, DANN ist Signifikanzniveau mittelniedrig WENN Kontrast hoch und Bewegung langsam ist, DANN ist Signifikanzniveau mittelniedrig WENN Kontrast äußerst hoch und Bewegung langsam ist, DANN ist Signifikanzniveau niedrig WENN Kontrast niedrig und Bewegung schnell ist, DANN ist Signifikanzniveau hoch WENN Kontrast mittelwertig und Bewegung schnell ist, DANN ist Signifikanznivesu mittelhoch WENN Kontrast hoch und Bewegung schnell ist, DANN ist Signifikanzniveau mittelwertig WENN Kontrast äußerst hoch und Bewegung schnell ist, DANN ist Signifikanzniveau mittelniedrig WENN Kontrast niedrig und Bewegung mittelwertig ist, DANN ist Signifikanzniveau hoch WENN Kontrast mittelwertig und Bewegung mittelwertig ist, DANN ist Signifikanzniveau mittelhoch WENN Kontrast hoch und Bewegung mittelwertig ist, DANN ist Signifikanzniveau mittelhoch
WENN Kontrast äußerst hoch und Bewegung mittelwertig ist, DANN ist Signifikanzniveau mittelwertig
Da allen Regeln unterschiedliche Werte für das Signifikanzniveau gegeben worden sind, müssen sie aufgelöst oder defuzzifiziert werden, um einen scharfen Endausgangswert zu ergeben. Hier wird das Flächenschwerpunktverfahren von Zadeh et al. dazu benutzt, den Schwerpunkt der kombinierten Ausgangsform zu finden, womit sichergestellt wird, daß alle Regeln zum scharfen Endergebnis beitragen. Siehe L. A. Zadeh und J. Kacprzyk, Fuzzy Logic for the Management of Uncertainty (Fuzzy-Logik zur Handhabung von Ungewißheit), John Wiley & Sons, Inc., 1992 für das Flächenschwerpunktverfahren. Es ist zu bemerken, daß, obwohl die obigen Fuzzy-Zugehörigkeitsfunktionen und -Regeln dem Zweck der Erfindung dienen, diese Zugehörigkeitsfunktionen oder Fuzzy-Regeln nicht optimiert worden sind.
In diesem, im Teildiagramm der Fig. 13 gezeigten Erkennungsschritt werden sowohl pixelbasierende als auch verteilungsbasierende Differenzmetriken unabhängig geprüft und die Ergebnisse verschmolzen, um in Frage kommende Szenenänderungsbilder auszugeben. Pixelbasierende Differenzmetriken werden als Zeitreihensignale behandelt, wo sowohl optisch abrupte Cuts und die Duplizierung von Bildern Beobachtungsausreißer erzeugen, die der Gleichung (8) genügen.
Bei der Zeittrendschätzung wird im Gegensatz zu einem ausgeklügelteren Modell eine stückweise lineare Funktion zum Modellieren des Trends benutzt. Robuste Statistiken werden ebenfalls benutzt, um den Einfluß von Beobachtungsausreißern des Typs II bei der Trendschätzung zu vermeiden (siehe oben angeführte Definitionen). Die mit Bildern aus drei Bildern vor bis drei Bildern nach dem aktuellen Bild verbundenen Differenzmetriken werden sortiert. Man nehme an, daß sie geordnet sind, &sub1; < ... &sub7;. &sub5; und &sub6; werden dazu benutzt, zu einer Linie zu passen. Der interpolierte/extrapolierte Wert am aktuellen Bild ist der Prädiktionswert aus der Trendanalyse.
Dieser Vorgang ist in Fig. 14 dargestellt, die ein Beispiel von Trendschätzung (links) zeigt, wo ein Beobachtungsausreißer des Typs I erkannt wird. Man beachte, daß Beobachtungsausreißer des Typs II in jedem zweiten Bild bestehen, worin zwei Mengen von pixelbasierender Differenzmetrik (beispielsweise Summe der absoluten Differenz gegen Zeit) aufgezeichnet werden. In beiden Beispielen ist das Bild 5 das aktuelle Bild, das mit einem optisch abruptem Cut und einem duplizierten Bild im ersten bzw. zweiten Beispiel verbunden ist.
Zuerst werden Proben von Bild 2 bis Bild 8 gesammelt und in ansteigender Reihenfolge aussortiert. Vier kleinste Werte (Proben von Bild 2, 4, 6, 8 und von Bild 3, 5, 6, 7 im ersten bzw. zweiten Beispiel) werden dann verworfen. Dies geschieht, da in jeder 7-Bild- Periode die meisten Beobachtungsausreißer des Typs II, die auftreten könnten, vier betragen. Zusätzlich wird auch der größte Wert verworfen (Probe von Bild 5 und von Bild 4 im ersten und zweiten Beispiel), da er dem optisch abrupten Cut nach der Darstellung in Fig. 14 entsprechen kann.
Abschließend werden Proben von Bild 3, 7 (im ersten Beispiel) und von Bild 2, 8 (im zweiten Beispiel) gewählt, um zu einer geraden Linie zu passen. Im ersten Beispiel ist der interpolierte Wert am aktuellen Bild viel kleiner als der Istwert (positive Abweichung vom Trend), während im zweiten Fall der interpolierte Wert viel größer als der Istwert ist (negative Abweichung vom Trend). Der Erstere wird als Beobachtungsausreißer vom Typ I im Zusammenhang mit Cut-Erkennung und der Letztere als Beobachtungsausreißer des Typs II definiert.
Nach Schätzung des Zeittrends wird er von der beobachteten Zeitreihe abgezogen und dann die Hypothese H&sub0; : Δ = 0 gegen die Alternative H&sub1; : Δ ≠ 0 in der Gleichung (8) getestet. Eine praktische Lösung wird bei Berücksichtigung eines einfachen Kriteriums der Form
erhalten, wobei die Schätzung der Verlagerung in der q-ten Beobachtung ist und die Schätzung der Varianz von ist. kann durch spektrale Verfahren geschätzt werden (siehe U. Grenander und M. Rosenblatt, Statistical Analysis of Stationary Time Series (Statistische Analyse stationärer Zeitreihen), New York: Wiley, 1966, oder entsprechend der vorliegenden beispielhaften Ausführungsform der Erfindung durch Substituieren der gewöhnlichen Schätzungen von σ² und
αr(r = 1, 2, ..., p) in
Man beachte, daß αr (r = 1, 2, ..., p) und σ² dieselben wie in Gleichung (9) sind. Aus Leistungsgründen in der vorliegenden beispielhaften Ausführungsform der Erfindung wird ein autoregressives Modell nullter Ordnung angenommen und daher ist αr = 0 (r = 1, 2, ..., p).
Abschließend wird für alle Proben, die als Beobachtungsausreißer identifiziert werden, wenn der Prädiktionswert aus dem Trend geringer als beobachtet ist, das Bild als mögliches in Frage kommendes Szenenänderungsbild markiert.

Varianzschätzung

Für diejenigen beobachteten Proben, die weder Beobachtungsausreißer des Typs I noch des Typs II sind, werden sie zur Aktualisierung der Varianzschätzung σz unter Verwendung der folgenden Formel benutzt:
σz = (1 - τ)σ² + τ (Bilddifferenzsignal ohne Trend),
wobei τ gleich 0,6 ist.
Wie in vorhergehenden Abschnitten beschrieben, befaßt sich der Kolmogorov-Smirnov-Test mit der Übereinstimmung von zwei Mengen beobachteter Werte. Die Nullhypothese ist, daß zwei Proben aus Gesamtheiten mit derselben Verteilungsfunktion F(x) F(x)kommen. Es läßt sich zeigen, daß
Prob(dt > Kα 2/N) = α
wobei Kα eine Konstante darstellt, die vom Signifikanzniveau α abhängig ist und in Tabellenform in den meisten Statistikbüchern ersichtlich ist. Siehe beispielsweise J. D. Gibbons und S. Chakraborti, Nonparametric Statistical Inference (Nichtparametrische statistische Folgerung), Marcel Dekker, Inc., 1992. N ist die Größe des Bildes, an dem die Statistik gesammelt wird. dt, das als
maxj|EDFt(j) - EDFt-1(j)|,
definiert wird, ist direkt aus dem Histogramm jedes Gleichstrombildes konstruiert (siehe Gleichung (4)).
In jedem Bild wird ein neues Signifikanzniveau α aus dem Adaptionsschritt erfaßt. α wird in dem Test nicht nur für das Gesamtbild, sondern auch jedes seiner vier gleich eingeteilten Teilbilder benutzt. Angenommen, daß n aus 4 Gebieten Änderungen zeigen. Die integrierte Zählung wird wie folgt definiert:
KSt = n · 2 + 1 wenn die auf dem Gesamtbild beruhenden Statistiken eine Änderung zeigen) (12)
KSt = n · 2 (sonst)
Diese integrierte Zählung gewichtet die aus einem beliebigen von 4 Gebieten erkannte Änderung zweimal mehr als die aus dem Gesamtbild erkannte Änderung.
In dieser Stufe wird die durch den hierarchischen Kolmogorov-Smirnov-Test erzeugte integrierte Zählung zur Beseitigung von falschen Positivwerten benutzt, die durch den Zeitreihen-Ausreißererkennungsprozeß erzeugt werden. Man beachte die durch φt für das Bild t erzeugte integrierte Zählung. Das System beseitigt ein in Frage kommendes Szenenänderungsbild, wenn
Wenn das System diesen Schritt erreicht, werden die meisten falschen Positivwerte beseitigt worden sein. Es könnten jedoch immer noch welche aufgrund von Blitzlicht oder äußerst schneller Kamerabewegung vorkommen. Es kann ein Kriterium aufgestellt werden, um solche falschen Positivwerte zu beseitigen. Die Liste erkannter Cut-Bilder wird wie durch den am Entscheidungsschritt in der Fig. 7 anhängenden gestrichelten Kasten gezeigt in einem Verzögerungsspeicher gespeichert und der Abstand zwischen beliebigen zwei Cuts untersucht. Jeder Cut, der in einem Abstand von weniger als einem voreingestellten Wert auftritt (fünf Bilder in der vorliegenden beispielhaften Ausführungsform) wird beseitigt.
Die vorgeschlagene Cut-Browsereinrichtung enthält drei Grundelemente: den Video-Player, den Video- Browser und den Cut-Browser. Diese drei Elemente bieten Video-Browsing auf drei unterschiedlichen Abstraktionsebenen, Der Video-Player und der Cut-Browser bieten beide nur rohes Videomaterial, obwohl im letzteren Fall die gebotenen Stoffe auf einer anderen Abstraktionsebene liegen. Der Video-Browser stellt jedoch interpretierte Informationen über Szenen im Video dar. Zusammen bieten diese drei Komponenten das beste Werkzeug für einen Benutzer, der die folgenden drei Aufgaben durchführen möchte: den Inhalt des Videos durchsuchen, um zu entscheiden, ob das Cut-Erkennungsverfahren eine Szene verpaßt oder fehlerkannt haben könnte, und um Cuts zu erzeugen oder zu beseitigen.
Die vorgeschlagene Cut-Browsereinrichtung funktioniert wie folgt. Wenn sie angefahren wird, werden wie in der Fig. 15 gezeigt, die die Cut- Browsereinrichtung zeigt, drei Fenster auf dem Bildschirm angezeigt.
Der Video-Browser zeigt alle erkannten Szenen unter Verwendung von repräsentativen Bildern (R- Bildern), während der Cut-Browser das aus dem gesamten Video hergestellte Querschnittsbild anzeigt. Die Aktivitäten in allen drei Fenstern sind vollständig synchronisiert. Wenn beispielsweise der Benutzer die Maus zum Anklicken eines beliebigen Punkts im Cut- Browser benutzt, wird das zugehörige repräsentative Bild im Video-Browser hervorgehoben und der Video- Player beginnt mit der Wiedergabe des Videos von derselben Stelle. Jedes Mal, wenn der Video-Browser durchläuft, läuft das Querschnittsbild entsprechend durch.
Zur Ausführung der ersten Funktion, nämlich dem Durchsuchen des Inhalts des Videos, würde der Benutzer jedes repräsentative Bild im Video-Browser daraufhin untersuchen, ob es die gewünschte Szene ist. Für jede Szene würde der Benutzer auch das entsprechende Querschnittsbild im Cut-Browser daraufhin untersuchen, ob irgendein Muster von verpaßten Szenen besteht. Wenn über irgendeinen Punkt Zweifel besteht, würde der Benutzer den Punkt im Cut-Browser anklicken, um die Wiedergabe des rohen Videos im Video-Player zu betrachten.
Um zu entscheiden, ob das Cut-Erkennungsverfahren eine Szene verpaßt oder fehlerkannt haben könnte, könnte der Benutzer einfach das Querschnittsbild im Cut-Browser untersuchen. Wenn es irgendein Muster von verpaßten oder fehlerkannten Szenen gibt, würde der Benutzer dann den Punkt im Cut-Browser anklicken, um die Wiedergabe des rohen Videos im Video-Player zu betrachten.
Der Cut-Browser bietet auch die Schnittfähigkeit. Ein Benutzer kann eine beliebige Szene in zwei Teile teilen oder beliebige zwei Szenen durch Anklicken mit einer Maus oder einem Knopf in eine verschmelzen. Wenn dieses Ereignis vorkommt, wird das Querschnittsbild unterschiedlich segmentiert und auch die Liste repräsentativer Bilder aktualisiert.
Der erfindungsgemäße Cut-Erkennungsalgorithmus wurde auf 24 Videoclips angewandt, die mehr als 149 000 MPEG-1-PAL- und NTSC-Videobilder enthielten. Diese Videos umfassen eine Vielzahl von Arten einschließlich Filmtrailer, Trickfilme und Sportvideos, wie sie in der folgenden Tabelle 2 aufgeführt sind. Die Tabelle 2 zeigt auch die Anzahl abrupter Cuts (Nc), die Anzahl verpaßter Cuts (N_{m}) (Nm) und die Anzahl falsch erkannter Cuts (Nf): Dies sind experimentelle Ergebnisse von dem erfindungsgemäßen automatischen Cut-Erkennungsverfahren. Diejenigen Szenen, die verpaßt oder fehlerkannt worden sind, zeigen alle klare Muster in Querschnittsbildern und werden daher leicht unter Verwendung der gegenwärtigen Cut-Browsereinrichtung von Hand identifiziert.
Man ist der Überzeugung, daß die vorliegende Erfindung eine Trefferquote und Präzisionsrate von der Größenordnung von 99% bereitstellt und zum Ablesen des Videos bis zur Ausgabe von Szenenänderun gsbildern mit annähernder Videobildfrequenz erkennen kann. Die Cut- Browsereinrichtung ist eine Cut-Browserein richtung, die in der Lage ist, im wesentlichen eine Trefferquote von 100% zu erreichen. Die Erfindung berücksichtigt die nichtstationäre Beschaffenheit des Cut-Erkennungsproblems und ist an einer Vielzahl von Videos und über 149000 Videobildern geprüft worden.
Die vorliegende Erfindung läßt sich deutlich im Zusammenhang mit der Verwendung eines entsprechend programmierten digitalen Rechners unter Verwendung von im Stand der Technik bekannten Programmierverfahren implementieren.
Obgleich die vorliegende Erfindung mit beispielhaften Ausführungsformen beschrieben worden ist, sollen diese nicht begrenzend wirken und dem Fachmann in der Technik, auf die sie zutrifft, werden verschiedene Änderungen und Abänderungen offenbar sein. Beispielsweise können verschiedene Einzelheiten in den Bildschirmen der Browser umgeordnet werden, ohne aus dem Rahmen der beiliegenden Ansprüche zu weichen. Weiterhin können verschiedene alternative Scheibenschneidebenen zur Ableitung von Querschnittsbildern auf der Erfindung entsprechende Weise substituiert werden. Diese und ähnliche Änderungen sollen im Rahmen der Erfindung liegen, die durch die nachfolgenden Ansprüche definiert wird.

Claims

1. Verfahren zur Erkennung eines Cuts in einem Video mit folgenden Schritten:

(a) Erfassen von Videobildern von einer Quelle;

(b) Ableiten einer pixelbasierenden Differenzmetrik aus den Videobildern;

(c) Ableiten einer verteilungsbasierenden Differenzmetrik aus den Videobildern, gekennzeichnet durch folgende Schritte:

(d) Messen des Videoinhalts der Videobilder zur Bereitstellung aktueller Prüfkriterien;

(e) Kombinieren der pixelbasierenden Differenzmetrik und der verteilungsbasierenden Differenzmetrik unter Berücksichtigung der im Schritt (d) gelieferten aktuellen Prüfkriterien, um ein in Frage kommendes Szenenänderungssignal abzuleiten; und

(f) Filtern des in Frage kommenden Szenenänderungssignals, um eine Szenenänderungs- Bildliste zu erzeugen.

2. Verfahren zum Erkennen eines Cuts in einem Video nach Anspruch 1, wobei die pixelbasierende Differenzmetrik für jedes Bild die Summierung einer absoluten Bilddifferenz, die für den Bildintensitätswert an ausgewählten Pixelstellen in einem Bild repräsentativ ist.

3. Verfahren zum Erkennen eines Cuts in einem Video nach Anspruch 1, wobei die pixelbasierende Differenzmetrik für jedes Bild t die Summe einer absoluten Bilddifferenz,

wobei f den Intensitätswert an Pixelstelle (i,j) im Bild t darstellt, ist.

4. Verfahren zum Erkennen eines Cuts in einem Video nach Anspruch 1, wobei jedes Bild in eine Anzahl von Teilgebieten eingeteilt wird, wobei die verteilungsbasierende Differenzmetrik eine Kolmogorov- Smirnov-Prüfmetrik ist, mit der Ausnahme, daß jeweils eine darin für das gesamte Bild und auch seine Teilgebiete berechnet wird.

5. Verfahren zum Erkennen eines Cuts in einem Video nach Anspruch 1, wobei jedes Bild gleichmäßig in vier Teilgebiete eingeteilt wird, wobei die verteilungsbasierende Differenzmetrik eine Kolmogorov- Smirnov-Prüfmetrik ist, mit der Ausnahme, daß jeweils eine darin für das gesamte Bild und auch die vier gleichmäßig eingeteilten Teilgebiete berechnet wird.

6. Verfahren zum Erkennen eines Cuts in einem Video nach Anspruch 1, wobei der Schritt des Messens des Videoinhalts der Videobilder zur Bereitstellung von aktuellen Prüfkriterien dem Schritt (e) die Fähigkeit gibt, sich automatisch auf verschiedene Videoinhalte einzustellen.

7. Verfahren zum Erkennen eines Cuts in einem Video nach Anspruch 1, wobei die besagten Videobilder Gleichspannungsbilder sind, die durch die Grundfrequenz in den Koeffizienten der diskreten Cosinustransformation dargestellt werden, die das zugrunde liegende Vollbild kennzeichnet.

8. Verfahren zum Erkennen eines Cuts in einem Video nach Anspruch 1, wobei der besagte Schritt des Messens des Videoinhalts der Videobilder zur Bereitstellung aktueller Prüfkriterien das Sammeln von Statistiken aus jedem Gleichspannungsbild und jedem Paar von Gleichspannungsbildern zur Darstellung des gegenwärtigen Videoinhalts beinhaltet, nämlich einem Bildkontrast und die Bewegungsschätzung. Die Bildkontrastschätzung wird auf Grundlage einer rekursiven Anordnung zur Unterdrückung der Einflüsse plötzlicher Beleuchtungsänderungen berechnet.

9. Verfahren zum Erkennen eines Cuts in einem Video nach Anspruch 1, wobei das Sammeln von Statistiken aus jedem Gleichspannungsbild und jedem Paar von Gleichspannungsbildern zur Darstellung des gegenwärtigen Videoinhalts eine Bildkontrastschätzung und eine Bewegungsschätzung darstellt.

10. Verfahren zum Erkennen eines Cuts in einem Video nach Anspruch 1, wobei die besagte Bildkontrastschätzung auf Grundlage einer rekursiven Anordnung zur Unterdrückung der Einflüsse plötzlicher Beleuchtungsänderungen berechnet wird.

11. Verfahren zum Erkennen eines Cuts in einem Video nach Anspruch 8, wobei die besagte Bildkontrastschätzung nach dem folgenden abgeleitet wird:

Kontrastt = (1-τ) Kontrastt-1 + στt-1,

wobei σt-1 die Intensitätsvarianz-Schätzung des Gleichspannungsbildes zur Zeit t-1 ist.

12. Verfahren zum Erkennen eines Cuts in einem Video nach Anspruch 8, wobei die besagte Bildkontrastschätzung gleich 0,6 ist.

13. Verfahren zum Erkennen eines Cuts in einem Video nach Anspruch 8, wobei die besagte Bewegungsschätzung wie folgt berechnet wird:

wobei j der Intensitätswert an Pixelstelle (i,j) des Gleichspannungsbildes zur Zeit t-1 und N die Größe des Bildes ist.

14. Verfahren zum Erkennen eines Cuts in einem Video nach Anspruch 11, wobei τ gleich 0,6 ist.

15. Verfahren zum Erkennen eines Cuts in einem Video nach Anspruch 8, wobei die besagten Bildkontrast- und besagten Bewegungsschätzungen an eine Fuzzy- Maschine angelegt werden, um ein neues Signifikanzniveau für die hierarchische Kolmogorov- Smirnov-Prüfung zu berechnen, wobei die Fuzzy-Maschine sich einer quadratischen Zugehörigkeitsfunktion bedient, wobei jede Kontrastmessung in Klassen von niedrig bis hoch eingeteilt wird und jedes Signifikanzniveau in Klassen von langsam bis schnell eingeteilt wird und jede Bedeutungshöhe in Klassen von hoch bis niedrig eingeteilt wird.

16. Verfahren zum Erkennen eines Cuts in einem Video nach Anspruch 15, wobei jede Kontrastmessung in vier Klassen, niedrig, mittel, hoch und äußerst hoch, jede Bewegungsschätzung in drei Klassen, langsam, mittel und schnell, und jedes Signifikanzniveau in fünf Klassen hoch, mittelhoch, mittel, mittelniedrig und niedrig eingeteilt wird und wobei die Fuzzy-Regeln in einem einfachen WENN/DANN-Format angegeben werden, wobei Werte unter Verwendung von UND (Minimum) oder ODER (Maximum)-Operationen kombiniert werden.

17. Verfahren zum Erkennen eines Cuts in einem Video nach Anspruch 16, mit einem Schritt des Defuzzifizierens der besagten Fuzzy-Regeln zur Erzeugung eines scharfen Endausgabewertes durch Finden des Schwerpunkts der kombinierten Ausgangsform, wodurch sichergestellt wird, daß alle Regeln zum scharfen Endergebnis beitragen.

18. Verfahren zum Erkennen eines Cuts in einem Video nach Anspruch 1, wobei im besagten Schritt (e) des Kombinierens der pixelbasierenden Differenzmetrik und der verteilungsbasierenden Differenzmetrik unter Berücksichtigung der im Schritt (d) bereitgestellten aktuellen Prüfkriterien zur Ableitung eines in Frage kommenden Szenenänderungssignals die pixelbasierenden Differenzmetriken als Zeitreihensignale behandelt werden, wobei sowohl optisch abrupte Cuts und Verdopplung von Bildern Beobachtungsausreißer erzeugen.

19. Verfahren zum Erkennen eines Cuts in einem Video nach Anspruch 18, wobei die besagte pixelbasierende Differenzmetrik als ein Zeitreihensignal behandelt wird, wobei sowohl optisch abrupte Cuts als auch die Verdopplung von Bildern Beobachtungsausreißer erzeugen, die die folgende Gleichung befolgen:

dt = f (dt-r, dt-r+1, ..., dt) + ut wenn t≠g

dt = f (dt-r, dt-r+1, ..., dt) + ut + Δ ansonsten,

wobei t den Zeitindex darstellt, Δ der Ausreißer ist, f (dt-r, dt-r+1, ..., dt) den Trend in der Reihe modelliert,

und

ut = αrd-r + zt (t = p + 1, ..., n)

20. Vorrichtung zum Erkennen eines Cuts in einem Video mit folgendem:

(a) einem Mittel zur Erfassung von Videobildern von einer Quelle;

(b) einem Mittel zum Ableiten einer pixelbasierenden Differenzmetrik aus den Videobildern;

(c) einem Mittel zum Ableiten einer verteilungsbasierenden Differenzmetrik aus den Videobildern, gekennzeichnet durch:

(d) ein Mittel zum Messen des Videoinhalts der Videobilder zur Bereitstellung von aktuellen Prüfkriterien;

(e) ein Mittel zum Kombinieren der pixelbasierenden Differenzmetrik und der verteilungsbasierenden Differenzmetrik unter Berücksichtigung der im Schritt (d) bereitgestellten aktuellen Prüfkriterien zur Ableitung eines in Frage kommenden Szenenänderungssignals; und

(f) ein Mittel zum Filtern des in Frage kommenden Szenenänderungssignals zur Erzeugung einer Szenenänderungs-Bildliste.

21. Vorrichtung zum Erkennen eines Cuts in einem Video nach Anspruch 20 mit Mitteln zur Darstellung von zwei Querschnittsbildern der Videobilder, von denen eines ein horizontales Querschnittsbild in einer horizontalen Richtung und das andere ein senkrechtes Querschnittsbild in einer senkrechten Richtung des Videovolumens ist.

22. Vorrichtung zum Erkennen eines Cuts in einem Video nach Anspruch 21, wobei jedes Querschnittsbild durch Abtasten einer Zeile (oder Spalte) aus jedem Bild und Reduzieren der Informationsmenge von einem zweidimensionalen Bild zu zwei eindimensionalen Bildstreifen aufgebaut wird.

23. Vorrichtung zum Erkennen eines Cuts in einem Video nach Anspruch 22, wobei die besagten horizontalen und senkrechten Querschnittsbilder in ein in zwei Bänder segmentiertes Bild nach einer Liste erkannter Szenen kombiniert werden, wodurch eine Abstraktionshöhe dargestellt wird, die gerade dazu ausreicht, zu zeigen, ob eine verpaßte oder fehlerkannte Szene vorliegt.

24. Vorrichtung zum Erkennen eines Cuts in einem Video nach Anspruch 20 mit Mitteln zum Darstellen von mindestens zwei Querschnittsbildern der besagten Videobilder, von denen eines ein horizontales Querschnittsbild in einer horizontalen Richtung und das andere ein senkrechtes Querschnittsbild in einer senkrechten Richtung des Videovolumens ist.

25. Vorrichtung zum Erkennen eines Cuts in einem Video nach Anspruch 24, wobei jedes Querschnittsbild durch Abtasten einer Zeile (oder Spalte) aus jedem Bild und Reduzieren der Informationsmenge von einem zweidimensionalen Bild zu einer Mehrzahl von eindimensionalen Bildstreifen konstruiert wird.

26. Vorrichtung zum Erkennen eines Cuts in einem Video nach Anspruch 25, wobei die besagten mindestens zwei Querschnittsbilder einschließlich der besagten horizontalen und senkrechten Querschnittsbilder in ein Bild kombiniert werden, das in eine Mehrzahl von Bändern nach einer Liste erkannter Szenen segmentiert wird, wodurch eine Abstraktionshöhe dargestellt wird, die dazu ausreicht, zu zeigen, ob eine verpaßte oder fehlerkannte Szene vorliegt.