DE69809289T2

DE69809289T2 - Verfahren zum hierarchischen zusammenfassen und schnellen durchsehen einer digitalen videosequenz

Info

Publication number: DE69809289T2
Application number: DE69809289T
Authority: DE
Inventors: Krishna Ratakonda
Original assignee: Sharp Corp
Current assignee: Sharp Corp
Priority date: 1997-12-19
Filing date: 1998-12-17
Publication date: 2003-08-28
Anticipated expiration: 2018-12-18
Also published as: JP2001527304A; US5995095A; WO1999032993A1; EP1040429B1; EP1040429A1; US5956026A; JP3719933B2; DE69809289D1

Description

Umfeld der Erfindung

Diese Erfindung bezieht sich auf ein Verfahren zum Bestimmen der Darstellung einer digitalen Videosequenz durch einen Stapel von Standbildern in einem hierarchischen Zusammenfassen von Applikationen, wie zum Beispiel (i) visuelle Identifizierung des Videoinhalts; (ii) Videoindexierung (iii) Videosurfen; und (iv) Videoeditierung. Die digitale Videosequenz können komprimierte MPEG-Dateien (Moving Pictures Experts Group) sein, und die Darstellung kann unter minimalem Decodieraufwand der Bitstrom-Kompression bestimmt werden.

Hintergrund der Erfindung

Wesentlich bei einer kompakten Videodarstellung sind die Abfrage vieler Informationen und der Abruf der Applikationen. Die Beispiele für solche Applikationen rangieren vom Multimedia-Datenbankzugang bis zum schnellen Durchsehen (bzw. schnellen Vorwärtsspielen) eines Videoclips. Die jüngsten Lösungsansätze haben sich hauptsächlich auf die Unterteilung eines vorhandenen Videosegments in "Schüsse" konzentriert. Jeder Schuss wird durch einen Key-Frame dargestellt, der den Schuss zusammenfasst. Somit kann man diese darstellenden Rahmen anstelle einer schnellen Durchsicht durch die gesamte Videosequenz betrachten. Die Schusserfassung kann mit einer sehr hohen Genauigkeit (> 90%) und wenigen Verfehlungen (< 5%) erreicht werden. Auf Histogramme (Schaubilder) basierende Lösungsansätze gehören ebenso zu den erfolgreichsten Schusserfassungsstrategien als auch zur geringsten computertechnischen Berechnungsaufwandsanforderung. Ein Vergleich zwischen verschiedenen Schusserfassungsstrategen kann auch in einschlägiger Literatur gefunden werden. Viele dieser Schemen können auch einige spezielle Interessensituationen berücksichtigten: Kameraschwenk (Pan), Zoom, Bildauflösung und Ein-/Ausblendung beim Bestimmen dar Videoschussgrenzen.
Die bekannten Techniken konzentrieren sich im Allgemeinen auf das Erfassen der Schussgrenzen oder Szenenänderungen und verwenden eine Kollektion, die aus einem einzigen Rahmen aus jedem Schuss als Key-Frames hergestellt ist und stellen die Videosequenz dar. Das Zuteilen von mehr als einem Key-Frame auf jeden Schuss stellt bessere Zusammenfassungen zur Darstellung des Videoinhalts zur Verfügung. Solche bekannten Verfahren der Zusammenfassung von Daten sind jedoch mit nur einer einzigen Ebenenzusammenfassung ahne jegliche Flexibilität ausgestattet.
Andere bekannten Techniken verwenden Farbhistogramme (Farbschaubilder) und beschreiben diverse Verfahren zum Ausbilden von Histogrammen aus MPEG-Bitströmen (zum Beispiel Histogramme von DC-Koeffizienten eines 8 · 8 Block-DCT). Obwohl dies relativ geradeausprojektiert für I-Rahmen (innercodiert) ist, gibt es mehr als eine Art des Wiederverwertens der DC- Koeffizienten (Nullfrequenz) eines P-Rahmens (Prädiktionsrahmens/Vorhalterahmens) oder B-Rahmens (bidirektional vorhaltend) unter einem minimalen Decodieraufwand seines Vergleichsbildes.
Bekannte Vergleichsverfahren, die eine diskrete/digitale Kosinus- Transformation der (DCT)-Videokompression aufweisen, sind jedoch nicht hinsichtlich sämtlicher, praktischer Aspekte eines Betriebssystems ausgerichtet. Nachdem Key-Frames zum Beispiel identifiziert worden sind, müssen sie zur visuellen Darstellung decodiert werden. Keines der bekannten Vergleichsverfahren spezifiziert einen effizienten Mechanismus zum Decodieren der Key-Frames, der an einer beliebigen Stelle des Bitstromes positioniert sein kann, ohne die gesamte Videosequenz zu decodieren.
Eine beträchtliche Einschränkung der vorgenannten Schemen besteht dahingehend, dass alle Schüsse gleichwertig behandelt werden. In den meisten Situationen könnte es nicht ausreichend sein, den gesamten Schuss durch nur einen Rahmen darstellen zu wollen. Dies führt zu der Idee der Zuteilung einiger Key-Frames pro Schuss, die von der Menge der "interessanten Aktion" in dem Schuss abhängig ist. Der gegenwärtige Stand der Technik des Videosurfsystems teilt daher eine Videosequenz in ihre Komponentenschüsse auf und stellt jeden Schuss durch einige Repräsentativ-Key-Frames dar, wobei die Darstellung als "die Zusammenfassung" bezeichnet wird.
Die vorliegende Erfindung verbessert und erweitert die offengelegten Verfahren von L. Lagendijk, A. Hanjalic, M. Ceccarelli, M, Soletic, und E. Persoon gemäss der Offenlegungsschrift "Visual Search in SMASH System", dem Sitzungsprotokoll der Internationalen Konferenz über Bildverarbeitung, Seite 671-674, Lausanne, 1996; nachstehend bezeichnet als "Lagendijk".

Zusammenfassung der Erfindung

Die vorliegende Erfindung ist ein Verfahren zum hierarchischen Zusammenfassen und schnellen Durchsehen einer digitalen Videosequenz und weist in seiner Grundform das Eingeben eines digitalen Videosignals für eine digitale Videosequenz und Generieren einer hierarchischen Zusammenfassung auf, welcher die Key-Frames der Videosequenz zugrunde gelegt ist. Zusätzliche Schritte umfassen das computertechnische Berechnen der Histogramme (Schaubilder) für die digitale Videosequenz, das Erfassen der Schussgrenzen innerhalb der digitalen Videosequenz, das Bestimmen der Anzahl der Key- Frames zur Zuteilung innerhalb eines jeden Schusses, das Lokalisieren der tatsächlichen Position eines jedes Key-Frame innerhalb eines jeden Schusses, das Identifizieren der Key-Frame-Positionen nach dem größten konsekutiven Differenzkriterium, das Ausschneiden der Key-Frames für einen Schuss mit bedeutungsloser Aktion, das effiziente Extrahieren der Key-Frames im Falle einer Videosequenzkompression und das schnelle Durchsehen (Surfen) der Schüsse unter Verwendung der hierarchischen Key-Frame-Zusammenfassung.
Die "Videosequenz-Zusammenfassung von Daten" bezeichnet das Bestimmen der überhängendsten Rahmen einer vorhandenen Videosequenz, die als Repräsentant/Charakteristikum für die Videosequenz verwendet werden. Ein Verfahren des hierarchischen Zusammenfassens wird zum Konstruktionsaufbau einer hierarchischen Zusammenfassung in vielfachen Abstufungen offengelegt, wobei die Abstufungen im Verhältnis zum Detail variieren (zum Beispiel der Anzahl der Rahmen). Die gröbste bzw. kompakteste Abstufung stellt die überhängendsten Rahmen zur Verfügung und enthält die geringste Anzahl an Rahmen.
Ein Ziel der Erfindung ist es, ein Verfahren zur Erzeugung einer hierarchischen Multiabstufungszusammenfassung zur Verfügung zu stellen, wobei jede Abstufung zu einem unterschiedlichen Abstufungsdetail korrespondiert.
Ein weiteres Ziel der Erfindung ist es, ein Verfahren zur Verbesserung der Key-Frame-Auswahl zur Verfügung zu stellen.
Ein weiteres Ziel der Erfindung ist es, den Bewegungsinhalt einer Szene, insbesondere der Zoom- und Kameraschwenkszene, zu erfassen und zu nutzen, und sie dem Anwender zusammen mit der hierarchischen Rahmenzusammenfassung zu präsentieren.
Ein weiteres Ziel der Erfindung ist es, ein Verfahren zur Erzeugung einer hierarchischen Multiabstufungszusammenfassung einer MPEG-2 Videosequenzkompression zur Verfügung zu stellen, wobei jede Abstufung zu einem unterschiedlichen Abstufungsdetail korrespondiert.
Noch ein weiteres Ziel der Erfindung ist es, ein Verfahren zur Verfügung zu stellen, das für eine MPEG-2 Videosequenzkompression zum Konstruktionsaufbau von Histogrammen (Schaubildern) und zum Generieren einer hierarchischen Zusammenfassung unter minimalem Decodieraufwand des Bitstromes direkt angewendet werden kann.
Ein weiteres Ziel der Erfindung ist es, ein vollständig effizientes System für das Generieren von Zusammenfassungen einer MPEG-2- Videosequenzkompression zur Verfügung zu stellen.
Jedoch noch ein weiteres Ziel der Erfindung ist es, eine effiziente Art und Weise der Handhabung der Histogrammberechnung (Schaubildberechnung) für MPEG-Bitstrome zur Verfügung zu stellen.

Kurzbeschreibung der Zeichnungen

Fig. 1 zeigt eine Darstellung der hierarchischen Struktur einer Videosequenzzusammenfassung für drei Abstufungen.
Fig. 2 zeigt ein Blockdiagramm des ersten Ausführungsbeispiels des Verfahrens gemäß der Erfindung.
Fig. 3 zeigt ein Blockdiagramm eines automatischen Kameraschwenk- /Zoomverarbeitungsmoduls gemäß der Erfindung.
Fig. 4 zeigt ein Blockdiagramm eines Feinabstufungs-Key-Frames- Auswahl-Algorithmus gemäß der Erfindung.
Fig. 5 zeigt ein Blockdiagramm des hierarchischen Zusammenfassens gemäß der Erfindung.
Fig. 6 zeigt eine Abbildung kumulativer Aktionsmaße (C(x)), Verteilung der Key-Frames (kj) und korrespondierende Schusssegmente (tj-1, tj).
Fig. 7 zeigt ein Blockdiagramm eines Abschnitts des zweiten Ausführungsbeispiels gemäß der Erfindung zur Anwendung einer MPEG-2 Eingangs- Videosequenz-Kompression.
Fig. 8 zeigt eine Darstellung der Daten, die verwendet werden können, um die Key-Frames beim hierarchischen Zusammenfassen zu decodieren.
Fig. 9 zeigt eine grafische Darstellung der Bewegungskompensation.
Fig. 10 zeigt eine Abbildung des Unterschiedes zwischen dem Bewegungskompensationsalgorithmus zum Definieren von Fall (a) und Fall (b).

Detaillierte Beschreibung der bevorzugten Ausführungsbeispiele

Auf Grund der gegenwärtigen Technologie zum automatischen Einfangen/Festhalten des semantischen Oberhangs ist diese noch nicht voll entwickelt/ausgereift, damit sich Verfahren der Videosequenzzusammenfassung von Daten auf Niedrigabstufungsbild-Programmfunktionen verlassen können, wie zum Beispiel Farbhistogramme (Farbschaubilder). Eine Videosequenz- Zusammenfassung ist eine Art und Weise des Bestimmens der überhängendsten Rahmen einer vorhandenen Videosequenz, was als Repräsentant/Charakteristikum der Videosequenz verwendet werden kann. Es ist möglich, dass ein spezieller Rahmen mit wichtigen Informationen nicht in einer einzigen Zusammenfassung enthalten sein kann, die eine vorher spezifizierte Anzahl von Rahmen aufweist.
Unter Bezugnahme auf Fig. 1 kann eine hierarchische Multiabstufungszusammenfassung 20, die durch das hierarchische Zusammenfassungsverfahren von Daten gemäß der Erfindung generiert wird, eine detaillierte Feinabstufungszusammenfassung mit einer ausreichend großen Anzahl von Rahmen zur Verfügung stellen, so dass wichtige Inhaltsinformationen nicht verloren gehen, jedoch gleichzeitig sind die Zusammenfassungen bei gröberen Abstufungen weniger detailliert ausgestattet, um die Nutzung einer groben oder kompakten Zusammenfassung zum schnellen Durchsehen (Surfen) und Identifizieren der Videosequenz nicht zu behindern. Die hierarchische Multiabstufungszusammenfassung 20 umfasst eine kompakteste Zusammenfassung 22, bei der gröbsten Abstufung, welche solange ausreichen sollte, bis detailliertere Informationen als notwendig erachtet werden und die feineren Abstufungszusammenfassungen abgerufen werden, wie zum Beispiel die Grobzusammenfassung 24 und die Feinstzusammenfassung 26. Obwohl drei Abstufungen der Summation in Fig. 1 dargestellt sind, sollte begrüßt werden, dass die hierarchische Zusammenfassung gemäß der Erfindung von jeglicher Anzahl von Abstufungen Gebrauch machen kann, die größer als eine andere ist.
Die Zusammenfassung 20 erleichtert auch das schnelle Durchsehen (Surfen) durch eine Datenbank von Videosequenzen, wobei das schnelle Durchsehen auf Basis der kompaktesten Zusammenfassung durchgeführt werden kann. Eine progressive Verfeinerung der Zusammenfassung auf detailliertere Abstufungen kann auf Abruf des Anwenders durchgeführt werden.
Die hierarchische Multiabstufungszusammenfassung von Daten erleichtert die effektive Art der visuellen und interaktiven Darstellung der Videosequenzzusammenfassung für den Anwender. Der Anwender kann mit der Zusammenfassung über eine grafische Anwenderschnittstelle bei der Verfeinerung der Zusammenfassung interaktiv vorgehen, mit der Visualisierung unterschiedlicher Abstufungen der Zusammenfassung und mit dem Abspielen/Rückspielen der Videosequenz zwischen zwei Key-Frames und mit der Zusammenfassung bei irgendeiner Abstufung. Anwender des hierin offengelegten Verfahrens können die maximale Anzahl der Key-Frames in der Zusammenfassung und die Anzahl der Abstufungen der Hierarchie spezifizieren. Somit ist das System bezüglich einer begrenzten Speicherkapazität und Ressourceanwendungen kontrollierbar.
Das hierin offengelegte Verfahren ist sowohl bei einer unkomprimierten (bzw. dekomprimierten) als auch bei einer auf DCT-basierenden (auf einer diskreten/digitalen Kosinus-Transformation basierenden) Videosequenzkompression anwendbar, wie zum Beispiel bei einer MPEG- Videosequenzkompression oder bei sonstigen, auf Bewegungskompensation, vorhaltebedingte/prädiktive Videosequenzkompression. Im Falle einer MPEG Videosequenzkompression wird die Zusammenfassung von Daten unter minimalem Decodieraufwand des Bitstromes und mit einer effizienten Art des Decodierens der Key-Frames durchgeführt, was zu reduzierten Computerberechnungs- und Speicherkapazitätsanforderungen führt. Die hierin enthaltenen Beispiele gehen von einer MPEG-2 Videosequenzkompression aus aber wie schon vorher erwähnt, sind sie auf irgendeine auf DCT-basierende Videosequenzkompression anwendbar. Der Fachmann versteht, dass ein Vergleich zu einer MPEG-Videoseuyenz ein Vergleich mit einer Videostromkompression ist, außer etwas anderes wird erwähnt.
Bei der hierin offengelegten hierarchischen Zusammenfassung von Daten wird das Erfassen von Spezialeffekten, wie zum Beispiel Überblendungen, über eine Nachbearbeitung unterstützt. Segmente, die solche Effekte enthalten, weist der Zusammenfassungsprozess der Daten nicht auf, um nicht nachteilig deren Genauigkeit zu beeinflussen. Vorkehrungen bezüglich des Verfahrens des Erfassens von Kameraschwenk- und Zoomsegmenten für kompakteste und ausdrucksstarke Darstellung in der Zusammenfassung werden ebenso ermöglicht.
Eine Videosequenz kann auf Basis ihrer Zusammenfassungsrahmen unter Verwendung von für Standbilder entwickelten Techniken indexiert werden. Multiple Abstufungen bieten Flexibilität in Richtung Indexierung bei wechselnder Detailabstufung.
Der hierarchische Lösungsweg gemäß der Erfindung ermöglicht dem Anwender ein schnelles Durchsehen (Surfen) durch eine Ansammlung von Videosequenzen auf Grund des Betrachtens von deren kompaktesten Zusammenfassungen 22 mit einer Möglichkeit eines Zugangs zu einer feineren Zusammenfassung 24, 26, falls der Inhalt der kompaktesten Zusammenfassung tatsächlich interessant erscheint. Ein Anwender des Verfahrens gemäß dieser Erfindung hat die Flexibilität, die Zusammenfassung der ausgewählten Segmente der Videosequenz zu verfeinern.
Wenn das Zusammenfassen einer MPEG-Videosequenz angewandt wird, werden zwei Komponenten bereitgestellt, welche als "Bitstromindex- Tabellengenenator" und "Decodermanager" bezeichnet werden. Diese Komponenten sind zur effizienten Decodierung der Key-Frames notwendig, um eine visuelle Zusammenfassung und ein anschließendes, schnelles Durchsehen durch die Videosequenz zu generieren, ohne das ein Decodieren ihrer Gesamtheit erforderlich wird.
Das gesamte Verfahren der Erfindung ist allgemein unter 30 in Fig. 2 zusammengefasst. Das Verfahren dient der Absicht, um auf einer Videokamera und einem Recorder/Aufzeichnungsgerät, wie zum Beispiel einem Camcorder betrieben werden zu können, oder auf einem Computersystem, das die Kapazität aufweist, zu einem Minimum Videosequenzen aufzunehmen und idealerweise große Mengen von Videodaten abspeichern zu können, wobei die Videosequenzdaten als Videosequenzeingangsmaterial 32 dienen. Der Mechanismus, welchen das Verfahren gemäß der Erfindung aufweist, wird hierin als "System" bezeichnet. Das Videosequenzeingangsmaterial 32 wird zunächst dahingehend verarbeitet, um Rahmen zu erfassen und zu entfernen, die in Spezialeffekten enthalten sind, wie zum Beispiel Ein- oder Ausblendung 34, weil die Einblend- /Ausblendrahmen zu falschen Schussgrenzen und Key-Frames führen. Solche Rahmen werden als globale Bewegungsvorgänge eingestuft und werden nachfolgend von der weiteren Verarbeitung ausgeschlossen. Der nächste Schritt ist die Histogramm-Computerberechnung 36. Farbbildhistogramme, das heißt Farbverteilungen, bilden repräsentative Charakteristikvektoren der Videosequenzrahmen und werden bei der Schussgrenz-Erfassung 38 und Key-Frame- Auswahl verwendet. Die Schussgrenz-Erfassung 38 wird unter Verwendung einer Schwellenmethode durchgeführt, wobei Unterschiede zwischen Histogrammen von aufeinanderfolgenden Rahmen verglichen werden.
In Anbetracht einer Gesamtanzahl von Key-Frames (Anwender spezifiziert) 40 wird jeder Schuss einer von der "Aktion" innerhalb des Schusses abhängenden Anzahl von Key-Frames 42 entsprechend der allgemein bekannten Technik zugeteilt. Die Feinstabstufungs-Key-Frame-Auswahl 44 wird unter Verwendung einer verbesserten Version der Lagendijk-Technik durchgeführt. Die hierin offengelegte Implementierung umfasst eine verbesserte Version dieser Technik durch Integrieren zusätzlicher, neuer Schritte, wie in Fig. 4 dargestellt ist, die später hierin detaillierter beschrieben werden, wobei eine Erweiterung des Feinstabstufungs-Key-Frame-Auswahlverfahren zur Verfügung gestellt wird.
Unter nochmaliger Bezugnahme auf Fig. 2 sind die automatische Kameraschwenk-/Zoomverarbeitung 46, die zur Generierung eines Bildmosaiks führt, sowie eine Zoom-Zusammenfassung 52, optionale Schritte und werden hierin später erklärt. Der nächste Schritt ist das neue Verfahren zur Generierung einer Key-Frame-Hierarchie 48, das heißt ein Zusammenfassen bei gröberen Details als bei der Feinstabstufungszusammenfassung. Dieser Prozess wird auch später hierin in den Einzelheiten beschrieben. Er basiert auf einer Variation des Themas der Vektorquantisierung. Nachdem die Feinst- und Grobabstufungszusammenfassungen für einen vorhandenen Schuss bestimmt werden, wird der Prozess für andere Schüsse in der Videosequenz, Block 50, wiederholt. Zusätzliche Schritte umfassen das schnelle Durchsehen der hierarchischen Zusammenfassung, Block 53, und Beendigung des Prozesses, Block 54.

Automatische Kameraschwenk-/Zoornverarbeitung

Die Schritte der automatischen Kameraschwenk-/Zoomverarbeitung 46 werden in Fig. 3 dargestellt, welche das Erfassen der Kameraschwenk- und Zoomvorgänge in der digitalen Videosequenz aufweisen. Rahmen, die globale Bewegung enthalten, werden erfasst 56. Dies ist ein Pre-Screening-Verfahren mit dem Ziel, jene Rahmen zu identifizieren, welche globalen Bewegungen unterliegen. Diese Rahmen können unter Verwendung eines Bildmosaiks kompakt (raumsparend) dargestellt werden, wenn die globale Bewegung auf Grund eines Kameraschwenks erfolgt, wie zum Beispiel durch einen Kameraschwenk-Detektor 58 oder durch eine Zoom-Zusammenfassung 52, das heißt hiervon des ersten und letzten Rahmens einer Zoom-In oder Zoom-Out-Sequenz, wie dies durch den Zoom-Detektor 60 erfasst und durch den Zoom-Auswerter 66 kompiliert worden ist. Folglich wird ein Mosaikaufbau 62 nur für jene Rahmen versucht, die eine globale Kameraschwenkbewegung manifestieren und welche zu einem Bildmosaik 51 führen. Rahmen, die im Bildmosaik 51 beteiligt sind oder in einer Zoom-In oder Zoom-Out-Sequenz werden von der Feinstabstufungszusammenfassung, Block 64, ausgeschlossen, da die Feinstabstufungszusammenfassung weiter verarbeitet wird, um die gröberen, kompakteren (raumsparenderen) Abstufungen zu bilden.
In einem alternativen Ausführungsbeispiel kann die Kameraschwenk- /Zoomverarbeitung 46 vorzugsweise interaktiv als automatisch ausgeführt werden. Der Anwender kann aus der ausgewählten Feinst-Key-Frame- Zusammenstellung 44 jene Key-Frames auswählen, welche den Start und das Ende einer Kameraschwenksequenz bilden, und das System kann als Reaktion ein Bildmosaik 51 konstruieren und es dem Anwender präsentieren. Der Anwender kann Rahmennummern K und L identifizieren oder markieren, das heißt zwischen zwei Key-Frames dazwischen befindet sich ein Kameraschwenk. Der Bild- Mosaik-Aufbauer 62 betrachtet Rahmen zwischen Rahmennummer K-n und L+n beim Aufbau als Mosaik, wobei "n" eine vorher festgelegte Offseteinstellung darstellt. Ein Bild-Mosaik-Aufbauer 62 kann entsprechend den dem durchschnittlich begabten Fachmann bekannten Bildmaschentechniken implementiert werden.
Beim Zoomen ebenso wie beim Kameraschwenken kann der Anwender manuell den Anfang und das Ende der Rahmen spezifizieren oder ein automatischer Zoomerfassungsalgorithmus kann eingesetzt werden, welcher wiederum ein Algorithmus ist, der dem durchschnittlichen Fachmann sehr wohl bekannt ist.
Eine Form des hierarchischen Zusammenfassens wird in Fig. 5 dargestellt sowie allgemein unter Bezugsziffer 70. Das hierarchische Zusammenfassen ist in hierarchische Key-Frame-Abstufungen unterteilt. Dem Anwender kann als erstes die kompakteste (gröbste) Abstufungszusammenfassung 72 präsentiert werden, das heißt die kompakteste Zusammenfassung möglicherweise zusammen mit Bildmosaik 51 und Zoom-Zusammenfassung 52. Dann kann der Anwender einen Vorgängerrahmen markieren und den/die Nachfolgerrahmen in der feineren Abstufung sehen, hierin als Grobabstufung 74 bezeichnet. Das Markieren der Rahmen in der Feinstabstufung 76 resultiert in ein Playback/Abspielen der Videosequenz; zum Beispiel, wenn der j-th-Key-Frame bei der Feinstabstufung markiert wird, werden die Rahmen zwischen den j th und (j+1) st Key-Frames abgespielt/zurückgespult. Bei einer tatsächlichen GUI- Einlaufzeit (Implementierung) kann die Nachfolger-Vorgänger-Beziehung explizit während der Anzeige indiziert werden. Der hierin verwendete Begriff "Markieren" oder "Markierung" kann zugleich das Identifizieren eines besonderen Objektes auf einem Computermonitor sein, wie das Klicken auf einen besonderen Rahmen. Die Key-Frames beim hierarchischen Zusammenfassen können räumlich in Layout-Strukturen (Verkleinerung für Kontrollzwecke) stichprobenartig zur kosteneffektiven Speicherung zusammengefasst und unterteilt werden sowie- zum schnellem Abruf und zur Anzeige der Zusammenfassung. Das normale Playback einer Videosequenz wird bei der Feinstabstufung ausgeführt, jedoch kann das Playback auch bei einer gröberen Abstufung ausgeführt werden.

UNKOMPRIMIERTES VIDEOEINGANGSMATERIAL

Das erste Ausführungsbeispiel gemäß der Erfindung wird hierin als eine "Pixel-Domain" bezeichnet, ein Losungsansatz zum hierarchischen Zusammenfassen und schnellen Durchsehen einer digitalen Videosequenz, welcher bei einem unkomprimierten, digitalen Videoeingangsmaterial 32 erforderlich wird.
Es wird davon ausgegangen, dass die Gesamtanzahl der zu verwendenden Key-Frames für die gesamte Videosequenz vorhanden ist (was normalerweise von den Speicherplatzanforderungen diktiert wird). Die Technik Lagendijks weist drei Hauptschritte auf:
1. Erfassen der Schussgrenzen;
2. Bestimmen der Anzahl der jedem Schuss zuzuteilenden Key-Frames und
3. Lokalisieren der Positionen der Key-Frames innerhalb eines jeden Schusses.
Die in dieser Erfindung verwendete Technik wird allgemein unter 80 in Fig. 4 dargestellt und umfasst ein 3-Schritt-Iterativ-Verfahren 82. Das Erfassen der Schussgrenzen, Block 38, Fig. 2, wird unter Verwendung eines Histogrammes ausgeführt, welches auf einem dynamischen Schwellenansatz basiert. Es wird davon ausgegangen, dass die ersten "n", typischerweise n = 3, Rahmen der Sequenz nicht mit den Schussgrenzen korrespondieren. Das mittlere Aktionsmaß Am und die Standardabweichung des Aktionsmaßes Asd werden durch Errechnen der mittleren und der standardisierten Abweichung der Aktionsmaße jeweils bestimmt, welche später hierin definiert werden, über die ersten n-Rahmen. Der Schwellenwert wird bis Am +αAsd gesetzt. Erst nachdem eine Grenze nach diesem Schwellenwert erfasst ist, wird ein neuer Schwellenwert für den nächsten Schuss in der gleichen Art und Weise unter Verwendung der ersten n-Rahmen für diesen neuen Schuss festgelegt. Typischerweise wird der Parameterwert α bis 10 festgesetzt.
Das Aktionsmaß (A(.,.)) zwischen zwei Histogrammen (h&sub1; und h&sub2;) wird bestimmt zur (l&sub1; Norm)
A(h1,h&sub2;) = Σi h&sub1;(i) - h&sub2; (i)
Das kumulative Aktionsmaß (C(.)) für einen Schuss (s) mit n-Rahmen s&sub1;, ..., sn wird bestimmt zu:
C(x) = Σs1s1 ix s1 A(hs,hs, i-1), (x s n)
Das kumulative Aktionsmaß für jeden Schuss und die Summe der kumulativen Aktionsmaße für jeden Schuss wird somit festgestellt. Die Anzahl der zugeteilten Key-Frames zu einem speziellen Schuss "s", Block 42, wird auf die relative Menge des kumulativen Aktionsmaßes innerhalb dieses Schusses proportioniert.
Lokalisieren der tatsächlichen Positionen der Key-Frames innerhalb des Schusses kann als ein l&sub1; Minimierungsproblem angesehen werden. Jeder Key-Frame repräsentiert (und ersetzt) einen aneinandergrenzenden Satz von Videosequenzrahmen. Der Verbund dieser aneinandergrenzenden Sätze von Videorahmen stellt den gesamten Schuss dar. Da jeder dieser aneinandergrenzenden Sätze von Videorahmen durch einen einzigen Key-Frame repräsentiert wird, möchte man sicherstellen, dass die Menge der Aktion innerhalb eines aneinandergrenzenden Satzes von Videorahmen klein ist. Der Hintergrund dieser Sache ist der, dass, falls es zuviel "Aktion" innerhalb eines aneinandergrenzenden Satzes von Videorahmen gibt, ein einziger Key-Frame nicht imstande ist, die Aktion vollständig darstellen zu können. Somit wird eine einem einzigen Schuss (welcher der gleiche ist wie die Anzahl der aneinandergrenzenden Sätze, in welche der Schuss aufgeteilt ist) zugeteilte, vorhandene Gesamtanzahl von Key-Frames einem Minimierungsverfahren unterzogen, welches die Key-Frames feststellt und welche die "Aktion" innerhalb der korrespondierenden, angrenzenden Sätze der Videorahmen minimiert. Unter der Annahme, dass K Key-Frames innerhalb eines Schusses s positioniert werden sollen, wird die Lokalisierung der Key-Frames auf kj (j = 1, ..., K) belassen. Ferner wird kj-1, ..., tj-1 der angrenzende Satz von Videosequenzrahmen durch den Key-Frame bei kj repräsentiert. Mit anderen Worten [tj-1, tj-1] ist das Schusssegment, welches durch den Key-Frame h dargestellt wird. Das nachfolgende Kostenkriterium muss über alle möglichen tj minimiert werden (kj wird bestimmt durch Auswahlen tj, das heißt kj = (tj + t1-1)/2)):
g(k&sub1;, ...,kK,t&sub1;, ..., tK-1) = Σ j=k j=1 tj tj-1 C(x)-C(kj) dx
Es ist zu beachten, dass t&sub0; und tk der erste und der letzte Rahmen des Schusses sind (und folglich die Konstanten sind) Erst wenn kj = (tj + kj-1 )/2 in vorgenanntem Kostenkriterium ersetzt worden sind, wird eine zufriedenstellende, optimale Lösung erreicht 2C(ti) - C(ki) ≤ C(ki+1).
Um die Minimierung auszuführen, werden folgende Schritte in einer iterativen Art durchgeführt, welche sich von der Technik Lagendijk unterscheidet.
1. Setzen k1 = 1 (vorausgesetzt, dass t&sub0; = 0 und der zweite Rahmen als Kandidat für den ersten Rahmen gewählt worden ist).
2. Für 1 = 1 durch K-1
ti = 2ki - ti-1.
Definieren von ti+1 als ersten. Videosequenzrahmen (das heißt den Videosequenzrahmen mit dem kleinsten Folgewert/tiefgestellten Indexwert, n, das heißt größer als t1), wofür 2C(ti) - C(ki) ≤ C(ki+1) gilt.
3. Für i = K, Errechnen von t' K = 2kK - tK-1. Falls tK > 2kK - t K-1 = t' K' gilt, Inkrementieren von k&sub1; um 1 und Übergehen zu Schritt 2; ansonsten Beibehalten der Ergebnisse der vorhergehenden Iteration, Addieren eines Offset zu sämtlichen kis, so dass tK = t'K' gilt, und Stoppen.
Die Minimierung kann mit einer endlichen Zahl dez Schritte ausgeführt werden wie in Fig. 6 dargestellt ist. Ein kumulativer Fehler ist eine nicht mindernde Funktion innerhalb eines Schusses. Folglich hat das vorgenannte Minimierungsverfahren das Herausfinden jener Key-Frames, kj, zum Ziel, welche die beste Treppenapproximation (bestens im Sinne von 11) zur kumulativen Fehlerkurve 90 ergibt. Dies resultiert in eine Verteilung der Key- Frames kj, welche anpassungsfähig an die Menge der "Aktion" im Schuss variiert. Das zu minimierende Feld, wie durch die Integration in Eq. 3 zum Ausdruck gebracht, wird bei 92 dargestellt.
Der Inhalt des dritten, vorgenannten Schrittes ist wie folgt: Der letzte Key-Frame des Schusses sollte so nahe wie möglich zum Mittepunkt zwischen tK-1 und t = tK sein. Inkrementieren von k&sub1; und Schritt 2 und 3 solange wiederholen, bis dieser Mittepunkt zum ersten Mal darüber hinausgeht. Dann nimmt man die Ergebnisse der vorhergehenden Iteration und gleicht sie so aus, dass der Letzte Key-Frame mit dem Mittepunkt übereinstimmt, das heißt tk = 2kK - tK-1, und der t'x, der durch das 3-Schritt-Iterativ-Verfahren bestimmt wird, stimmt mit tk überein.
Eine weitere Neuheit, die bezüglich des früheren Algorithmus-vorgestellt wurde, bezieht sich auf Fälle, wobei man die Schussgrenze selbst mit k1 = 1 überschießt auf Grund einer ausreichend großen Anzahl von Key-Frames, die diesem speziellen Schuss zugeteilt sind. In diesem Fall wird ein einfaches Schema angewandt, um die Key-Frames in einer solchen Art und Weise zu verteilen, dass sie in gleichen Abständen angeordnet sind. In diesem einfachen Schema wird, falls ein Schuss zuzuteilende n-Rahmen und K-Rahmen aufweist, jeder (n/K)th Rahmen als ein Key-Frame selektiert.

Verbesserung bei der Key-Frame-Selektierung

Bei der Technik Lagendijks wird der Key-Frame für ein Schusssegment [tj-1,tj -1] ergibt tj-1 und tj-1, immer bei kj = (tj + tj-1)/2 lokalisiert. Mit anderen Worten, der Key-Frame wird immer so ausgewählt, dass er in der Mitte des Segments als Repräsentant/Charakteristikum der Rahmen in dem Segment steht. Jedoch wenn man auf die Definition des kumulativen Fehlers zurückkommt, ist der kumulative Fehler nur von der absoluten Änderung zwischen aufeinanderfolgende Rahmen abhängig. Folglich könnte ein Key-Frame in der Mitte eines Segmentes nicht repräsentativ für die tatsächliche Änderung zwischen zwei Rahmen sein, die durch mehr als einen Rahmen getrennt sind. Betrachten wir eine Videosequenz, wobei ein Reporter spricht. Wir nehmen an, dass es da zwei Rahmen gibt, die zum Beispiel 10 Rahmen auseinander liegen, und dass beide Rahmen den Reporter mit einem offenen Mund zeigen. Infolgedessen tritt bei den beiden Rahmen eine sehr geringe Änderung bzw. "Aktion" auf. Jedoch die kumulative Änderung zwischen den beiden Rahmen könnte groß sein, da die kumulative Änderung die Summe der absoluten Änderungen zwischen aufeinanderfolgenden Rahmen darstellt. Es ist möglich, dass diese beiden Rahmen unter jenen als Key-Frames ausgewählten sich befinden können, falls die "Mitte des Segments" -Regel angewandt wird. Folglich könnte ein blindes Auswählen der "Mitte des Segments" -Rahmen als den Key- Frame zu einer fehlerhaften Selektion der Key-Frames führen.
Bei diesem Ausführungsbeispiel wird das resultierende Setzen der Breakpoints/Programmstops innerhalb jeden Schusses, (t&sub0;, t&sub1;, ...,tk), die man durch das 3-Schritt-Iterativ-Verfahren erhält, in Betracht gezogen. Jener Rahmen in dem Segment (tj-1,tj-1), welcher am unterschiedlichsten (im Verhältnis zum Aktionsmaß A(.)) zum vorhergehenden Key-Frame (kj-1) ist, wird als der Key-Frame ausgewählt, der bei k2 lokalisiert wird. Diese Strategie nimmt die größte Differenz zum vorhergehenden Key-Frame und wird hierin als das "größte konsekutive Differenz" -Kriterium, Block 84, bezeichnet. Der erste Key-Frame, (k&sub1;), wird als der eine von dem 3-Schritt-Iterativ- Verfahren Bestimmte erfasst. Dieses Verfahren stellt sicher, dass die aufeinanderfolgenden. Key-Frames sich ausreichend voneinander unterscheiden, so dass die Redundanz/der Überhang so weit als möglich reduziert wird.

Reduzieren der Anzahl der Key-Frames in Schusssegmenten mit bedeutungsloser Aktion

Da die Technik Lagendijks insgesamt auf einen kumulativen Fehler basierend ist, wie vorstehend beschrieben, könnte sie über große Fehler zwischen zwei Rahmen Bericht erstatten, die aber in der Tat sehr eng zusammen sind. Obwohl die vorstehend vorgestellte Technik gut für das Auswählen des interessantesten Rahmens in einem vorhandenen Schusssegment ist, löst es nicht die Situation, in der das gesamte Schusssegment "uninteressant" vom Standpunkt der Aktion innerhalb des Schusssegmentes ist. Zum Beispiel kann es eine Akkumulation von Fehlern auf Grund einer leichten Kamerabewegung geben, die nicht zu einer sehr bedeutungsvollen Änderung zwischen aufeinanderfolgenden Key-Frames führen.
Um Schüsse mit bedeutungsloser Aktion zu überspringen/ignorieren, werden diese Schüsse identifiziert und die Key-Frames für diese Schüsse ausgeschnitten, Block 86, was die Feinstabstufung der Key-Frames hinterlässt, Block 44. Dies wird durch Bewertung der mittleren und der standardisierten Abweichung des Aktionsmaßes zwischen aufeinanderfolgenden Videosequenzrahmen ausgeführt, welche zwischen zwei vorhandenen Key-Frames liegen und die bestimmt und analysiert werden. Falls ausreichend "bedeutungsvolle Aktion" zwischen zwei Key-Frames vorhanden ist, dann ist das Aktionsmaß zwischen aufeinanderfolgenden Rahmen in der Original-Videosequenz entscheidend, das heißt der Key-Frame wird entsprechend des grölten konsekutiven Differenzkriteriums, Block 84, identifiziert.
Folglich: wenn Am das mittlere Aktionsmaß zwischen Key-Frames ki und ki-1, und Asd die Standardabweichung des Aktionsmaßes ist:
(s/β)*Asd + Am < A(kn ki-1)
falls der Inhalt zwischen zwei Key-Frames interessant ist, wobei "s" die Anzahl der Videosequenzrahmen zwischen den beiden Key-Frames ki und ki-1 ist. Falls das Schusssegment im vorgenannten Sinne uninteressant ist, wird dieser spezielle Key-Frame gelöscht und das Schusssegment wird mit dem nächsten Schusssegment verschmolzen.
Der Parameter β nach der vorherigen Ausdrucksweise ist eine Konstante. Falls β weniger als 1 ist, werden nur die Key-Frames mit großen Unterschieden überleben, was zu einem exzessiven Ausschneiden führen kann. Als Wert von β wird 2,0 für die hierin berichteten Simulationen gewählt. Die Quantität (s/β) erhöht sich, wenn die Anzahl der den Schüssen zugeteilten Key-Frames gering ist, da sich die Entfernung zwischen den Key-Frames erhöht und folglich die Anzahl der Rahmen zwischen den Key-F rames, "s", sich erhöht, wenn die Anzahl der den Schüssen zugeteilten Key-Frames gering ist. Der maximale Wert, der (s/β) erreicht werden kann, wird als α festgelegt, wobei α der verwendete Faktor zum Definieren des Schwellenwertes für die Schussgrenzerfassung ist, um die Menge des Ausschneidens der Key-Frames zu limitieren.
Weitere Experimente brachten hervor, dass das lineare Schwellenschema zu einer ungleichmäßigen Key-Frame-Zuteilung bei mancher Auswahl der Gesamtanzahl der Key-Frames führen könnte. Um dieses Problem zu beheben, wird ein Grenzwert MAXERASE = 0,3 auf eine maximale Prozentzahl der Gesamtanzahl der Key-Frames festgelegt, der durch das vorgenannte Ausschneidevertähren gelöscht werden könnte. Im Falle der Limitierung werden die überschüssigsten 30 Prozent der Rahmen entfernt, die mit MAXERASE = 0,3 korrespondieren. Die Bedeutung von "überschüssiqsten" wird auch in dem Sinne verwendet, dass A(ki,ki-1) der kleinste für den überschüssigsten Key-Frame ist. In diesem Fall wird ki der überflüssige, zu entfernende Key-Frame.
Diese Technik, wenn sie bei einer High-Motion-Sequenz angewendet wird, produziert keine Änderung, wie erwartet wurde, da die Bewegung äußerst konstruktiv ist, das heißt Eq. (4) wird bei sämtlichen, gelöschten Key-Frames erfüllt und folglich gibt es keine Redundanz.

Hierarchisches Zusammenfassen und schnelles Durchsehen

Obzwar die vorgenannte Offenlegung ein intelligentes "Video- Indexierungssystem" beschreibt, stellt ein solches System nur eine fixierte Sequenz von Videorahmen zur Verfügung, welche mehr eine kompaktere Darstellung des Videoinhalts ist als die Originalvollsequenz der Videorahmen. In den meisten Situationen ist diese Darstellung immer nach unangemessen, da die Interessensabstufung in einer Videosequenz variiert, da man sich entlang der Sequenz und den Inhaltsänderungen bewegt. Auch kann die Interessensabstufung in einem speziellen Videoinhalt nicht vorhergesehen werden. Betrachten wir eine Videosequenz, bei der ein Mädchen eine Katze streichelt: Die Kamera schwenkt von dem Mädchen zur Katze. Eine Person könnte die Katze näher sehen wollen, aber nicht das Mädchen, wogegen eine andere Person das Mädchen nah sehen möchte und nicht die Katze, jedoch eine weitere Person wiederum möchte alle beide sehen. Ziel ist es, die Anzahl der "uninteressanten Rahmen" zu minimieren, die irgendjemand von diesen vorgenannten Personen ansieht.
Um diverse Sichtanforderungen bei dem gleichen Videoindexierungssystem zu vereinbaren und zu erfüllen, wird ein Multi-Bildauflösungs- Videobrowser, Black 53, Fig. 2, zur Verfügung gestellt, weicher es dem Anwendet ermöglicht, die hierarchische Zusammenfassung durch Selektieren einer speziellen Abstutungszusammentassung schnell durchzusehen. Dies ist ein Browser anstelle eines reinen Indexierungssystems. Ein Zuschauer könnte bei einer Grobabstufung für das Detail beginnen und das Detail mit einem Mausklick erweitern, und zwar an jenen Stellen der Key-Frame-Sequenz, die für den Zuschauer interessanter erscheinen. Mehr als eine Detailabstufung ist erforderlich, so dass der Zuschauer bei einem selektierten Tempo, dem Zuschauer entsprechend, schnell durchsehen kann. Die Feinstabstufungs-Key- Frames können immer noch erfasst werden. Bei einer gröberen Abstufung werden ähnliche Key-Frames bei Feinabstufungen zusammen gebündelt, und jedes Bündel wird durch einen repräsentativen Key-Frame dargestellt.
Um dieses Bündelproblem zu lösen, wird eine Modifizierung des ganz bekannten Linde-Buza-Gray (LBG) Algorithmus (oder Lloyd Algorithmus oder K- Mittel-Algorithmus) vorgeschlagen. Es ist zur Kenntnis zu nehmen, dass es erstrebenswert ist, ähnliche Bilder zusammenzugruppieren. Es wird davon ausgegangen, dass Bilder durch deren Histogramme dargestellt werden und dass ähnliche Bilder ähnliche Histogramme aufweisen. Indem man jedes Histogramm als einen Charakteristikvektor seines zugeteilten Rahmens behandelt, findet man (N/r)- repräsentative Histogramme in der Grobabstufung, um die N-Histogramme in der Feinstabstufung ersetzen zu können, wobei N die Anzahl der Key-Frames in der Feinstabstufung darstellt. Der Parameter "r" ist das Komprimierungsverhältnis und ist ein an das Programm des Zuschauers gelieferter Parameter. In der nachfolgenden Erörterung werden die Key- Frames im Verhältnis zu deren Histogrammvektoren zum Ausdruck gebracht.
Diese Erörterung ist zu den regelmäßigen Gruppierungs- /Bündelproblemen unterschiedlich, da gewünscht wird, einen repräsentativen Vektor zum Ersatz auszuwählen/aufzupicken, zum Beispiel "p" konsekutive Vektoren (zeitentsprechend/rechtzeitig). Im normalen LGB-Fall gibt es keine "Konsekutivitätseinschränkung" bei den Vektoren, die bei einem repräsentativen Vektor quantisiert sind. Die nachfolgende Iteration, die der normalen LGB-Iteration ähnlich ist, wird immer konvergieren. Dieses neue 3-Stufen- Iterativ-Verfahren wird hierin als "paarweise" LBG oder PLBG -Iteration bezeichnet. Es muss angemerkt werden, dass die PLBG die gleichen lokalen Minimierungsprobleme hat wie die LBG: Glücklicherweise kann eine "Clean-Up- Stufe" nach den Iterationen angewandt werden, um sich diesem Problem schnell anzunehmen Zu Beginn starten Sie mit einer gleichmäßig beabstandeten Sequenzpartition der Histogrammvektoren. Zum Beispiel enthält bei einem Komprimierungsverhältnis von 3 jeder partitionierte Satz 3 Histogrammvektoren (außer möglicherweise der letzte Satz oder die letzten beiden Sätze). Dann gehen Sie durch die nachfolgenden Schritte für das PLBG-Verfahren:
1. Zuteilen des Schwerpunkts- (oder des mittleren) Histogramms als repräsentativen Vektor für jeden Satz Vektoren;
2. Starten mit der ersten Partition, Justieren jeder Partition so, um die gesamte l&sub2;-Nnrm für die benachbarten Sätze an beiden Seiten der Partition zu minimieren (dabei im paarweisen Verhältnis).
Mathematisch: Falls Hi-1 der repräsentative Vektor für die Vektoren im Satz (ti-1,t&sub1;) und Hi der repräsentative Vektor für die Vektoren im Satz (ti, ti+1) ist, ti so justieren, dass die Gesamtsumme der rechteckigen/quadratischen Entfernungen der Vektoren in jedem Satz zu dem korrespondierenden, repräsentativen Vektor minimiert wird.
3. Falls nach erfolgter Justierung für eine Partition ti = ti+1 gilt, Hi vom repräsentativen Satz der Vektoren löschen. Falls ti-1 = ti gilt, Hi-1 vom Satz der repräsentativen Vektoren löschen.
4. Übergehen zu Schritt 1.
Das Stoppkriterium kann entweder auf einer Mengenreduzierung in der Verwerfung/Verzerrung oder auf eine fixierte Anzahl der Iterationen basieren. Wie bereits festgestellt wurde, nach 10 Iterationen stoppen. Bei jeder Iteration wird die Verwerfung (l&sub2;-Norm zwischen dem repräsentativen Vektor jeden Satzes und den korrespondierenden Vektoren in dem Satz) reduziert. Folglich bildet die gesamte Verwerfung bei jeder Iteration eine reduzierende Sequenz. Außerdem ist die Verwertung immer großer als oder gleich Null. Hierbei hat die Sequenz ein Limit durch eine elementare Realanalyse. Fragen wie zum Beispiel "Gibt es ein lokales Minimieren (und hierbei einen fixierten Punkt) für die Iteration"? sind rein akademisch und der Leser sollte sich auf die Literatur für derartige Diskussionspunkte beziehen. Der Löschschritt (Schritt 3) könnte tatsächlich zu einer leicht geringeren Anzahl von Key-Frames führen als ursprünglich erwartet oder selektiert wurde.
Bei dem vorgenannten Verfahren wird nach dem Stoppen der Rahmen in der ersten Gruppierung, deren Histogramm dem repräsentativen Vektor am nächsten kommt, als erster Key-Frame selektiert. Key-Frames für aufeinenderfolgende Gruppierungen können auf die gleiche Art und Weise bestimmt werden. Bessere Ergebnisse werden erzielt, wenn Key-Frames innerhalb aufeinanderfolgender Gruppierung entsprechend der "größten Differenz zu dem vorhergehenden Key-Frame-Kriterium" selektiert werden, wobei die Differenz im Verhältnis zum Aktionsmaß ausgedrückt wird.
Bei der Formulierung der vorgenannten Iteration gibt es die Möglichkeit, dass der letzte Satz nicht adäquat dargestellt wird, da die letzte Partition immer an den letzten Vektor in der Sequenz fixiert ist. Das gleiche könnte für den ersten Rahmen des Schusses genannt werden, jedoch wurde eine solche Situation nicht bei den hierin berichteten Experimenten beobachtet. Folglich wird ein weiterer Schritt nach der Vervollständigung der Iteration zur Verfügung gestellt, um dieses Problem zu lösen. In dieser Endstufe ist zu testen, ob ein repräsentativerer Vektor am Ende der Darstellung addiert werden muss. Insbesondere sehen Sie das Addieren des letzten Vektors als den neuen Repräsentanten an. Falls die Differenz zwischen dem letzten Vektor und dem vorhergehenden, repräsentativen Vektor weniger als 0- X (bedeutet die Differenz zwischen sämtlichen anderen Paaren der aufeinanderfolgenden repräsentativen Vektoren) ist, wird der letzte Vektor möglich. Wählen Sie 0- als 0,75 während den Simulationen. Beachten Sie, dass 0- zwischen 0 und 1 variieren kann.
Der Basislösungsansatz (Lagendijk) lässt die Szene aus, welche ein Merkmal des Interesses aufweist, falls 3 Key-Frames spezifiziert werden und dieser Basisweg auf einer Videosequenz angewandt wird. Die Ergebnisse sind von minderer Qualität in Bezug auf die kompakteste (gröbste) Abstufung der Multiabstufungs-Hierarchie mit 3 Key-Frames, die unter Anwendung des vorgenannten Verfahrens generiert worden sind. Ferner ist es weitaus effizienter, den vorgeschlagenen, herarchischen Lösungsweg zu nutzen als mehrfach den Basisalgorithmus, um eine unterschiedliche Anzahl von Key-Frames zu erhalten und eine Multiabstufungszusammenfassung zu generieren.

Block-Histogramm-Aktionsmaß

Ein auf ein Histogramm basierendes Aktionsmaß ist nicht in allen Situationen adäquat. Zum Beispiel, wenn ein schwarzes Objekt gegen einen weißen Hintergrund adaptiert wird, würde das auf ein Histogramm basierende Aktionsmaß die Bewegung nicht registrieren. In Situationen, in denen es erstrebenswert ist, die Feinmotorik einzufangen, zum Beispiel Handgestikulationen oder Kopfbewegungen, ist es vorteilhaft, ein besseres Aktionsmaß zu haben.
Block-Histogramme sind für die Schusserfassung vorgestellt worden. Jedoch kam man zu dem Schluss, dass Block-Histogramme für die Schusserfassung zu empfindlich waren und Anlass zu einer Reihe von Fehlalarmen gaben. Die Idee hinter Block-Histogrammen ist es, das Bild in einige Blöcke aufzuteilen (4 oder 16 für gewöhnlich) und das Aktionsmaß als Summe der absoluten Histogramm-Differenzen über jeden Block zu bestimmen. Es kann leicht verstanden werden, dass Block-Histogramme gegenüber Bewegung heikler/empfindlicher sein würden, welche nicht durch einen auf einem einfachen, allgemeinen Histogramm basierenden Lösungsansatz erfasst wurde. Block-Histogramme wurden experimentell nur für die Feinstabstufungs-Key- Frames angewandt, wie in dem 3-Stufen-Iterations-Verfahren in Fig. 4 dargestellt ist. Der Nachteil bei der Verwendung von Block-Histogrammen ist, dass sie rechnerisch und speichermäßig intensiver zu handhaben sind, da es erforderlich ist, mit 4 oder 16 Histogrammen pro Videorahmen anstelle mit nur einem zu arbeiten. In Experimentierreihen jedoch wurde festgestellt, dass der Block-Histogramm-Ansatz nicht zu beträchtlichen Leistungsverbesserungen führte.

Anwendung von Bewegungscharakteristiken für die Zusammenfassung von Daten

Die interessanten Spezialfälle, wie zum Beispiel Kameraschwenk oder Zoom, sind bisher noch nicht betrachtet worden. Im Falle eines Kameraschwenks sollte ein intelligenter Browser die Rahmen mit einem Schwenk (a) erfassen und eine Option für die in ein Bildmosaik zu Anschauungszwecken zu konvertierenden Schwenkrahmen zur Verfügung stellen (b). Da die Erfassung von Kameraschwenk und Zoom jeweils zu berechnende Bewegungsvektoren umfassen, kann die Zoomerfassung mit gleichzeitiger Schwenkerfassung ohne viel zusätzliche Computerüberlastung erzielt werden.
Da das Herausfinden der Bewegungsvektoren für jeden Rahmen in einer Sequenz computertechnisch anspruchsvoll beim Errechnen ist, ist ein Pre- Screening-Verfahren entwickelt worden, das zunächst sämtlichen, möglichen Sequenzen von Rahmen mit dominanter, bzw. globaler, Bewegung erfasst. Da dominante Bewegung auch durch einen (a) Kameraschwenk oder durch einen (b) Zoomvorgang oder durch einen (c) anderen Spezialfilmschnitteffekt verursacht werden kann, wird die erfasste Sequenz näher überprüft, um das Vorhandensein eines Kameraschwanks oder Zoomvorgangs festzustellen.

Pre-Screening einer Dominanzbewegung

Dominanzbewegung setzt voraus, dass jedes Pixels innerhalb des Videorahmens eine Änderung in der Intensität erfährt. Diese Änderung in der Intensität wird normalerweise durch Zoom oder Kamerabewegung verursacht. Diese Änderung wird am ehesten in den Randpixels des Videorahmens wahrnehmbar.
Der Lösungsweg ist, jedes Pixel anzusehen und zu bestimmen, ob es sich um einen Randpixel handelt und falls ja, den Unterschied zwischen dem aktuellen Pixel und dem Pixel an der gleichen Stelle im vorhergehenden Rahmen herauszufinden. Falls der absolute Wert des Unterschiedes auf einem Randpixel größer als ein Schwellenwert (PZ_THRESH = 15) ist, wird das Pixel so spezifiziert, als ob es eine Bewegung aufweist. Um zu bestimmen, ob das Pixel ein Randpixel ist, wird der durch den Sobel -Randerfassungsermittler erzielte Wert auf diesem Pixel mit einem Schwellenwert (PZ_THRE5H1 = 50) verglichen. Wenn PZ-THRESH reduziert wird, könnte man einen Fehlalarm erhalten. Wenn PZ_THRESH1 reduziert wird, könnte vielleicht keine bedeutsame Änderung auf derartigen Pixel vorhanden sein, da sie nicht zu starken Rändern gehören; Bewegung könnte nicht viel Intensitätsvariation verursachen. Um zu bestimmen, ob ein besonderer Rahmen ein Kameraschwenkrahmen ist, gilt der Schwellenwert auf das Ratio (Schwenkratio) zwischen der Anzahl der Pixel, die als Bewegungsstufe klassifiziert werden und der Gesamtanzahl der Randpixel (PZ- THRESH2 = 0,9). Ein weiterer notwendiger Schritt, um sicherzustellen, dass der Ratio konstant PZ_THRESH2 über den ganzen Kameraschwenk überschreitet, ist das Ausfüllen/Beschicken der benachbarten Umgehung. Mit anderen Worten, ein Randpixel weist Bewegung auf, wenn die Intensitätsvariation irgendeines Pixeis innerhalb einer NEIGH · NEIGH größer als PZ_THRESH ist, wobei NEIGH = 5 gilt.
Sequenzen der Rahmen, die kürzer als eine spezielle Anzahl sind, werden verworfen:
(TOO_MANY_FRAMES_NOT_PANZOOM = 5). Nachsampling/nochmalige Durchmusterung kann angewandt werden, um die Computerüberlastung weiter zu verringern.

Kameraschwenk-Erfassung

Der Lösungsweg der Kameraschwenkerfassung ist eine Variation bekannter Techniken. Um einen Kameraschwenk zu erfassen, sieht man auf die Bewegungsvektoren auf die Pixelstellen des Nachsampling (SPACING = 24). Das angewandte Verfahren zur Bestimmung des Bewegungsvektors ist einfacher Block- Abgleich (BLKSIZE = 7 · 7, SEARCHSIZE = 24 · 24). Man variiert die Suchgroße unter Zugrundelegung des Kameraschwenkvektors des vorhergehenden Rahmens: Die Suchgröße wird halbiert, wenn der vorhergehende PCameraschwenkvektor kleiner ist als (SEARCHSIZE/2)-2; die Originalgröße (größer) wird wieder hergestellt, wenn der vorhergehende Kameraschwenkvektor größer ist als (SEARCH- SIZE/2)-2. Diese Variation führt zu keinem Leistungsqualitätsverlust.
Für die Kameraschwenkerfassung ist bereits vorgestellt worden, alle Bewegungsvektoren, die parallel zum modalen (am häufigsten auftretenden) Bewegungsvektor innerhalb einer Toleranzgrenze sind, herauszufinden. Wenn die Anzahl derartiger Bewegungsvektoren größer als ein spezieller Schwellenwert ist, wird ein Kameraschwenk erfasst. Jedoch im Falle eines Kameraschwenks sind nicht nur die Bewegungsvektoren parallel verlaufend, sie haben ebenso ungefähr die gleiche Größenordnung. Deshalb wird eine kleine benachbarte Umgebung des modalen Bewegungsvektors überprüft anstatt auf sämtliche, parallelen Bawegungsvektoren zu schauen. Falls eine Verknüpfung in dem Wert eines modalen Bewegungsvektors auftritt, wird eine willkürliche Entscheidung getroffen. Die Größe der benachbarten Umgebung wird durch VARN (= 4) kontrolliert. Größere Werte bezüglich VARN würden zu einer kleineren, benachbarten Umgebung rund um den modalen Bewegungsvektor (VARN = 4 in unserem Fall impliziert eine Sx3 benachbarte Umgebung) führen. Die PANRATIO (= .5) bestimmt den Schwellenwert des Verhältnisses zwischen der Anzahl der Bewegungsvektoren innerhalb der benachbarten Umgebung und der Gesamtzahl der Bewegungsvektoren. Selbst wenn einige Rahmen in einer Sequenz von Kameraschwenk-/PAN-Rahmen unter die Schwellenwerte fallen, wird die Kontinuität des Kameraschwenkvorganges sichergestellt, wenn die Öffnung nicht größer als 3 (TOO_BIG_A_HOLE = 3) ist.

Zoomerfassung

Beim Überprüfen der alleräußersten Randzone der Bewegungsvektoren in einem Bild, das heißt der Bewegungsvektoren am Rande des Bildes, sollten die Zoomkonditionen erfasst werden. Bewegungsvektoren an den diametrisch gegenuberliegenden Stellen der Randzone sollten in die Gegenrichtungen zeigen. Der Schwellenwert (ZOOMRATIO = .7) im Verhältnis zu den Bewegungsvektoren zeigt gleichzeitig in die gegenüberliegenden Richtungen die Gesamtzahl der Bewegungsvektoren. Nur die Bewegungsvektoren an der äußeren Randzone werden verwendet, da die Mitte des Zooms irgendwo innerhalb des Bildes lokalisiert sein könnte. Folglich sind die Bewegungsvektoren an der äußeren Randzone die besten Indikatoren für das Vorhandensein eines Zooms. Hinzu kommt, dass es nicht viel Vordergrundbewegung an den Bildrändern gibt.

Farbverarbeitung

In diesem Abschnitt der Offenlegung werden die früher offengelegten Verfahren um die Farbsequenzen erweitert. Zwei unterschiedliche Ausführungsbeispiele werden beschrieben. In dem ersten Ausführungsbeispiel wird ein verkettetes Histogramm verwendet, da aus einem 256-bin Y Histogramm und zwei 128-bin U und V Histogrammen besteht In dem zweiten Ausführungsbeispiel wird ein einfaches 256-bin Y Histogramm verwendet. Bezüglich einiger Experimentiersequenzen wurden keine bedeutenden Änderungen in den Ergebnissen beobachtet. In beiden Fällen wird das Aktivitätsmaß wie das in Eq. 1 definiert. Jedoch in einigen Sequenzen, bei denen ein Farbhistogramm verwendet wird, kann das Erfassen der Änderung zwischen zwei Videorahmen entscheidend sein, das heißt die Bildhelligkeit bleibt nahezu gleich, jedoch der Chromwert verändert sich.

Zusammenfassung des unkomprimierten Videosequenzeingabeverfahrens

Ein Block-Diagramm der hierarchischen Zusammenfassung und Verfahren zum schnellen Durchsehen wird in Fig. 2 dargestellt. Das Modul für Bildauflösung, Ein-/Ausblendung, Entfernung wird in der angeführten, diesbezüglichen Applikation erläutert und ist hierin mittels Bezugsziffern enthalten und offenbart ein Bildauflösungserfassungsverfahren. Das Modul wird verwendet, um eine Bildauflösung in einen abrupten Szenenübergang durch Entfernen der Übergangsrahmen aus der Videosequenz zu konvertieren. Der Feinstabstufungs-Key-Frame-Erfassungs-Block wird in Fig. 4 erweitert, wobei wesentliche Schritte dargestellt werden. Das automatische Kameraschwenk-/Zoom- Autoprozess-Modul wird in Fig. 3 im Detail dargestellt. Es (a) erfasst automatisch und baut ein Mosaikbild (Panorama) auf, falls es einen Kameraschwenk (PAN) gibt, erfasst und bestimmt den ersten und den letzten Rahmen einer Zoomsequenz. Es schließt auch die Kameraschwenk/Zoom bezogenen Key- Frames aus den Feinstabstufungs-Key-Frames aus, so dass nur Nichtkameraschwenk- und Nichtzoomrahmen in dem hierarchischen Key-Frame-Generierungs- Prozess beteiligt sind. Diese Beseitigung und automatische Kameraschwenk- /Zoomverarbeitung ist optional und kann interaktiv nur bei gewissen Abschnitten des Videoclips durch den Anwender ermöglicht werden, falls dies gewünscht wird. Das GUI-Modul ermöglicht es dem Anwender, das schnelle Durchsehen der Videosequenz bei einer bestimmten Abstufung der Zusammenfassung (unter den durch den hierarchischen Browser generierten verschiedenen Abstufungen) zu starten. Zum Beispiel kann die gröbste Zusammenfassung zusammen mit Mosaikbildern und der Zoom-Zusammenfassung zuerst präsentiert werden. Dann kann der Anwender interaktiv Rahmen auf einer feineren Hierarchieabstufung abrufen/ab- oder rückspielen. Mit Klicken auf eine Schaltfläche kann der Anwender auf beide Vorgänger-/Nachfolgerrahmen des Key-Frame, der momentan angesehen wird, zugreifen. Das Auswählen des Vorgängerrahmens führt zu einem Ersatz von einer Gruppe von Key-Frames in der aktuellen Abstufung durch einen einzigen Key-Frame, der deren Vorgänger ist. Das Auswählen des Nachfolgerrahmens findet sämtliche Nachfolger-Key-Frames, die mit dem aktuellen Key-Frame korrespondieren. Fig. 5 veranschaulicht diesen Begriff der Vorgänger- und Nachfolger-Key-Frames. Auf der Feinstabstufung führt die nochmalige Erweiterung dazu, das heißt der Nachfolgerrahmen auf der Feinstabstufung, dass der Videoclip zwischen bestimmten Key-Frames gespielt wird. Während der Zeit, wenn das Video gespielt wird, kann die Musik/der Sound, die/der mit diesem Teil des Videoclips korrespondiert, auch synchron gespielt werden. Diese Funktion des Spielens des Videoclips kann auch auf einer gröberen Abstufung der Hierarchie zur Verfügung gestellt werden.
Das hierin beschriebene Verfahren zum schnellen Durchsehen von Videosequenzen kann auch Anwendungen aufweisen, die darüber hinausgehen, nur einfach eine effektive Anwenderschnittstelle für Multimedia-Handhabung zur Verfügung stellen zu wollen. Es schafft ein Verständnis des temporalen Inhaltes der Videosequenz, die potentiell in zweiter Generation der Videocodiersysteme eingesetzt werden kann und ruft Erinnerungen an die zweite Generation der Bildcodiersysteme wach. Die zur Handhabung eines MPEG-2 Bitstromes entwickelten Codiereinrichtungen adaptieren blind ein IBBP oder IBBBP Format zum Beispiel. Jedoch eine Hierarchie von Key-Frames kann auch zur Entwicklung von Codiereinrichtungen verwendet werden, die intelligenterweise und was noch wichtiger ist, computertechnisch effizient, sich der Beschaffenheit des temporalen Videostromes anpassen, und so eine höhere Qualität unter Ausnutzung geringerer Ressourcen bieten. Informationsmaterial über die Ausnutzung einer Hierarchie von Videorahmen unter Verbesserung der Kompression ist als Literatur erhältlich, wobei die Multi-Skalen- Beschaffenheit einer Algorithmus-Segmentierung ausgewertet/ausgenutzt wird, um eine verlustfreie Standbildkompression zu erzielen. Ein entscheidender Unterschied zwischen den Bildcodiersystemen der zweiten Generation und den Videocodiersystemen der zweiten Generation ist, dass die früheren Systeme eine fundamentale Änderung im Codiermechanismus benötigten und folglich keine großen Auswirkungen hatten, während die letzteren innerhalb sämtlicher, bestehender Videocodierstandards integriert werden können.

Computertechnische Rechenleistung

Die computertechnische Rechenleistung des Key-Frame- Generierungsverfahrens hängt stark vom schnellen Zugang zur Speicherfestplatte des verwendeten Computers ab, um das Verfahren gemäß der Erfindung anwenden zu können. In der nachfolgenden Erörterung bedeutet "Realzeitverarbeitung"/"Real Time Processing" die Fähigkeit, 30 Rahmen pro Sekunde bei einer vorgegebenen Bildauflösung zu verarbeiten. In Bezug auf eine allgemein übliche 300 Rahmenquadratmittelformat (QCLF) -Farbsequenz (176 · 144 Bildauflösung) wurde festgestellt, dass der Konstruktionsaufbau des Histogramms 11 Sekunden beanspruchte, wahrend der Rest der Verarbeitung weniger als eine Sekunde auf einem SUN® Ultra SPARC-2® System in Anspruch nahm. Folglich sollte es leicht sein, vorausgesetzt, dass die Histogramm- Errechnung in Realzeit erreicht werden kann, die hierarchische Key-Frame- Generierung in Realzeit zu erzielen. Es sollte auch beachtet werden, dass die Verarbeitung nach der Errechnung der Histogramme von der tatsächlichen Rahmenbildauflösung unabhängig ist. Folglich ist die beanspruchte Zeit, um eine 300 Rahmen QCIF-Sequenz zu verarbeiten, die gleiche wie diejenige bei der Verarbeitung einer Sequenz bei einer 1024 · 780 Bildauflösung, vorausgesetzt, dass die Histogramme eines jeden Rahmens vorausberechnet worden sind.
Gegenwärtig kann die globale Bewegungserfassung in Realzeit ausgeführt werden. Jedoch auf Grund der großen Computerberechnungsbelastung, die mit dem Blook-Abgleich-Algorithmus verbunden ist welche für die Kameraschwen-k/Zoom-Erfassung erforderlich ist, kann die Kameraschwenk-/Zoom- Verarbeitung nicht in Realzeit in einer Softwareimplementierung ausgeführt werden.

ROMPRESSION DES VIDEOEINGANGSMATERIALS

In der vorangehenden Erörterung wurden nur unkomprimierte bzw. dekomprimierte Bitströme in Betracht gezogen und in den Experimenten angewendet. Jedoch die meisten erhältlichen Videoströme weisen eine Formatkompression zur Kompaktspeicherung auf. Das Verfahren nach Fig. 4 kann auf einer Bitstromkompression derart erweitert werden, um so die Key-Frames unter Ausführung einem minimalen Decodieraufwandes zu extrahieren. Es wird allgemein geschätzt werden, dass ein höllisch grobes Verfahren zur Handhabung einer Videosequenzkompression einfach sein kann, um den gesamten Videostrom zu dekomprimieren, nachdem die hierin beschriebenen Techniken bezüglich unkomprimiertar Videosequenzen angewendet werden.
Dieser Abschnitt der Offenlegung behandelt eine Variation der hierarchischen Zusammenfassung und des Verfahrens zum schnellen Durchsehen einer digitalen Videosequenz, wie sie anhand von MPEG-2 Bitströmen angewendet werden kann. Das Ganzheitsschema wird in dem vorhandenen Flussdiagramm in Fig. 7 zusammengefasst. Eine Neuheit des Errechnens von Histogrammen wird offengelegt. Histogramme der DC-Koeffizienten der 8 · 8 Blöcke werden angewendet. Der Prozess beginnt mit einem Eingangs-Bitstrom 132. Die Histogramm-Computerberechnung 134 für I-Bilder ist daher richtungsweisend durch Verfahren, die dem durchschnittlich begabten Fachmann allgemein bekannt sind. Die Histogramm- Computerberechnung bezüglich Vorhaltebilder (P und B Rahmen), ohne vollständiges Decodieren ihrer Vergleichsrahmen, wird ausgeführt, wie hierin später offengelegt wird, und führt zu einer erhöhten Genauigkeit bei den Histogrammen und folglich der Key-Frame-Auswahl 136. Die hierarchische Key-Frame-Auswahl 136 bestimmt die Identität der Key- Frames der hierarchischen Zusammenfassung, zum Beispiel das Verhältnis ihrer temporalen Anzeigereihenfolge und stellt diese zusammenfassenden Informationen einem Decodier-Manager zur Verfügung, der später hierin beschrieben wird. Erst wenn die Histogramme der DCT-Koeffizienten generiert werden, wird die hierarchische Key-Frame-Auswahl durchgeführt, wie in Verbindung mit Fig. 4 erläutert wird.
Es sollte zur Kenntnis genommen werden, dass ein Mechanismus zum Erfassen der Bildauflösungsbereiche in der Videosequenz ein solcher ist, wie der offengelegte in meinem gleichzeitig gestellten Antrag: "Erfassen der Bildauflosungsbereiche in Videosequenzen", wie auch weiter oben aufgeführt ist. Der Mechanismus kann leicht in einen Verarbeitungsblock 134 in Fig. 7 integriert werden, welcher dann eine Histogramm-Computerberechnung und die BIT-Generierung durchführt. Demzufolge können in einem Bildauflösungsbereich enthaltene Rahmen innerhalb einer BIT gekennzeichnet und in dem aufeinanderfolgenden Key-Frame-Auswahl-Prozess übersprungen werden. Andernfalls können Rahmen innerhalb des Bildauflösungsbereiches Anlass zu fehlerhaften Key-Frames geben.
Das Verfahren erzeugt eine Aufzeichnung des Bitstromes, die einhergeht mit der Histogramm -Computerberechnung 134 und enthält Informationen über jedes Bild, wie zum Beispiel über ihre Byte-Offset-Stelle im Datenstrom, über deren Vergleichsrahmen und die verwendete Quantisierungsmatrix bei der Quanitisierung der DCT-Blöcke. Bei der gegenwärtigen Erfindung wird eine Tabelle erzeugt, die als "Bitstromindex-Tabelle" (BIT) bezeichnet wird. Die Inhalte der HIT 138 und das Verfahren dar BIT-Generierung werden im Detail später hierin erläutert.
Ein Zweck der BLT 138 dient dazu, die wesentlichen Parameter des Bitstromes zu erfassen, um das Decodieren der Key-Frames zum Generieren einer visuellen Zusammenfassung, ohne die Notwendigkeit eines Decodierens oder eines Analysierens des gesamten Bitstromes, zu ermöglichen. Das Analysieren macht es notwendig, dass das System auf jedes Bit in dem Videostrom schaut, ungeachtet dessen, ob der Videostrom decodiert ist oder nicht. Hinzu kommt, dass die HIT-Tabelle, oder eine abgespeckte Version der BIT, zusammen mit dem Originalbitstrom zur Verfügung gestellt wird, sowie die Identität der Zusammenfassung, wie in Fig. 8 dargestellt ist, zum effizienten, schnellen Durchsehen des Anwenders, wenn zum Beispiel der Anwender die Zusammenfassung visuell anzeigen oder das Video zwischen zwei Key-Frames abspielen möchte. Später wird hierin ein spezifisches Ausführungsbeispiel des Verfahrens beschrieben, wobei dem Anwender eine Zusammenfassung präsentiert und etwas Interaktivität zur Verfügung gestellt wird. Beachten Sie, dass in Fig. 8 der Bitstrom in einem Speicher, der an einem anderen physikalischen Platz als dem der BIT-Tabelle und der Identität der zusammenfassenden Rahmen abgespeichert sein kann. Zum Beispiel können Bitströme in einer Serverdatenbank abgespeichert sein und die Zusammenfassung sowie die BIT-Tabelle können auf einem lokal unabhängigen Gerät abgespeichert sein. Alternativ können alle drei Arten von Daten im gleichen Medium abgespeichert sein, wie zum Beispiel einer DVD-Disk oder einem sonstigen großen Speicherkapazitätsmedium. Verfahren zur weiteren Komprimierung (oder Reduzierung) der BIT werden in dem Abschnitt mit dem Titel "Generieren einer reduzierten Bitstromindex-Tabelle zur kompakten Speicherung" erläutert. Man sollte auch zu schätzen wissen, dass, nachdem die BIT generiert worden ist und entschieden wird, die Größe der BIT zu "reduzieren", eine Reihe von Techniken angewandt werden kann, um die BIT-Größe herunterzufahren. Nur ein einziges Beispiel wird hierin erwähnt. Es sollte auch zur Kenntnis genommen werden, dass es möglich ist, überhaupt keine BIT auszubilden und abzuspeichern, aber den gesamten Bitstrom zu analysieren und zu decodieren, und zwar jedes Mal, wenn ein Key-Frame decodiert werden muss.
Nochmaliger Bezug auf Fig. 7: Während der Generierung der hierarchischen Zusammenfassung 140 wird die in der BIT enthaltene Information vom Decoder-Manager 142 benutzt, um selektiv die Key-Frames zu decodieren, welche an einen MPEG-2 Decoder 144 weitergegeben werden, und wenn die Decodierung ausgeführt ist, wird die hierarchische Zusammenfassung 140 ausgebildet. Der Decoder-Manager 142 führt während der Präsentationsstufe eine ähnliche Aufgabe durch, wie der Anwender dies wünscht, um durch die Videosequenz durch Abspielen zwischen den Key-Frames schnell durchzusehen. Die Funktionsprinzipien des Decoder-Managers (der zum Beispiel durch ein. Computerprogramm implementiert werden kann) werden nachstehend erläutert.
Die Erfindung kann innerhalb einer Videokamera implementiert werden, welche MPEG-2 komprimierte Videos nach erfolgter Aufzeichnung speichert. In diesem Fall kann die zusammenfassende Information und die BIT-Tabelle in einem Speichersystem abgespeichert werden, oder sie werden in einem Arbeitsspeicher abgespeichert, der mit dem Videostrom in einer gut definierten Konfiguration verknüpft ist. Die hierarchische Zusammenfassung selbst, die Key-Frames enthält, oder deren nachüberprüfte Versionen durch Sub- Sampling, können ebenso in einem Speichersystem für unmittelbaren Zugang abgespeichert werden. Eine Kamera-Schnittstelle kann zur Identifizierung des in der Kamera gespeicherten Videoinhalts zur Verfügung gestellt werden, auf Band oder auf irgendeinem anderen Speichermedium unter Zugrundelegung der hierarchischen Zusammenfassung.
Alternativ können Bitströme von einer Kamera auf einen Computer heruntergeladen werden, wobei der Zusammenfassungaprozass ausgeführt wird. In diesem Fall kann die Zusammenfassung auf das Band oder auf irgendein anderes Speichermedium, welches die Videodaten festhält, zurückkopiert werden, oder auf einen ganz anderen Arbeitsspeicher, der mit einer gut definierten Verknüpfung mit den Video-Bitstrom verknüpft ist. Zum Beispiel sind Kameras, die direkt komprimierte MPEG-Ströme aufzeichnen, derzeit erhältlich (z. B. Hitachi MP-EG1A Kamera), wobei Bitströme dann auf einen PC heruntergeladen werden können. Das System der gegenwärtigen Erfindung kann verwendet werden, um solche Bitströme auf einer PG-Plattform zu verarbeiten.
Die nachfolgenden Probleme müssen angegangen und gelöst werden, um die hierarchische Videosequenzzusammenfassung effizient mit MPEG-2 Bitströme arbeiten zu lassen:
1. Generieren einer Key-Frame-Hierarchie während eines minimalen Decodierens des MPEG-2 Bitstromes.
2. Einrichten eines Verfahrens zum Decodieren der selektierten Key-Frames aus den MPEG-2 Bitströmen, ohne sämtliche Rahmen decodieren zu müssen.
3. Entwickeln einer Strategie zum Decodieren einer Rahmenstrecke zwischen zwei vorgegebenen Key-Frames.
Dieser Lösungsansatz funktioniert bei einer Histogrammabstufung. Ein Verfahren wird offengelegt, das ein Farbhistogramm für jeden Rahmen während eines minimalen Decodieraufwands des MPEG-2 Bitstromes computertechnisch errechnet.
Histogramm -Computerberechnung und konsequentes, aufeinanderfolgendes Verarbeiten ist unempfindlich bezüglich der Nachüberprüfung durch einen Faktor von 8 in jede Dimension. Nachdem man einen Schritt weitergegangen ist, wurde festgestellt, dass computertechnisch errechnete Histogramme unter Verwendung nur einer DC-Komponente der DCT 8 · 8 Blöcke, das heißt dem Mittelwert der 8 · 8 Blöcke, für praktische Zwecke ausreichend waren. Bezüglich Bewegung kompensierender Bilder wird vorgeschlagen, dass eine etwaige Bewegungskompensation verwendet werden könnte, um die Computerberechnung zu reduzieren, wobei man einen unbedeutenden Qualitätsverlust in der Leistung erhält. Nach dem in dem MPEG Standard verwendeten Block-Abgleich- Schema, kann sich ein 16 · 16 Makroblockbewegungsvektor überlappen, meistens in vier anderen 16 · 16 Makroblöcken zu dem Vergleichsrahmen, von dem aus die Prädiktion/der Vorhalterahmen kompensierter Bewegung ausgeführt wird. Ähnlich verhält es sich mit jeweils 8 · 8 Unterblöcken innerhalb der 16 · 16 Makroblocküberlappungen meistens bei vier anderen 8 · 8 Unterblöcken. Folglich wurde vorgeschlagen, dass jeder 8 · 8 Unterblock durch einen gewichteten Durchschnittswert den Werten der jeweils 8 · 8 Unterblöcke angenähert wird, die sich überlappen. Die zugeteilten Gewichte für jeden einzelnen Block könnten proportional zum Bereich der Überlappung erfolgen. Unter Bezug auf die Fig. 9 beträgt der Mittelwert der 8 · 8 Unterblöcke wie folgt:
(α)(b)(m&sub1;) + (8-α)(b)(m&sub3;) + (α)(8-b)(m&sub2;) + (8-α)(8-b)(m&sub4;) + ΔDCT)/64
wobei ΔDCT 8mal die DC Komponente der verbleibenden DCT Komponente für den Block ist (der Faktor von 8 kommt daher, weil die DC Komponente der verbleibenden DCT Komponente für den verwendeten Block in dem MPEG-2 Standard ein Achtel des Mittelwertes des abweichenden Fehlwertes des Blockes ist). Histogramme werden durch Aktualisieren des Histogrammvektors mit dem Mittelwert jedes 8 · 8 Blockes innerhalb des Bildes erzielt, das als Eq. 5 festgestellt wurde. Das vorgenannte Verfahren des Erzielens von Histogrammen birgt gewisse Probleme in sich, welche an einem möglichen Qualitätsverlust der Leistung führen. Eine der Verbesserungen des Verfahrens gemäß der Erfindung ist es, einen besseren Weg der Handhabung der Histogramm - Computerberechnung bezüglich MPEG Bitströme aufzustellen.
MPEG Bitströme integrieren komplizierte Codierstrategien, welche Decodierinformationen aus anderen Teilen des Bitstromes notwendig machen, bevor man versankt, einen speziellen Rahmen am decodieren. Eine erfolgreiche Videostrategie des schnellen Durchsehens muss sich auch dem Problem des Decodierens speziellen Videorahmen bei einem minimalen Zeitaufwand widmen.

Computerberechnung von Histogrammen aus MPEG Bitströmen

Das Decodieren eines MPEG Bitstromes umfasst zwei computertechnisch intensive rechnerische Schritte:
1 Erzielen eines DCL Gegenstroms der 8 · 8 Blöcke
2. Bewegungskompensation mit 16 · 16 Makroblöcken im Falle von MPEG-2 Bitströmen; die Blöcke können kleiner sein oder nur gleiche/ungleiche Felder aufweisen.
Zuvor wurde aufgezeigt, dass das Ersetzen eines 8 · 8 Blockes durch seinen Mittelwert keine große Auswirkung auf das Histogramm des Bildes hat. Bei dieser Praxis wird jeder 8 · 8 Block durch 8 · (DC Wert des DCT Koeffizienten) ersetzt. Aus der Formel für DCT Gegenstrom -Computerberechnung ist ersichtlich, dass dies die Mittelwerte des Blockes ergibt, genau übereinstimmend mit der Kompression bezüglich des Quantisierungsfehlwertes.
Um den nächsten Schritt zu verstehen, wird ein kurzer Überblick über die Codierstrategie bereitgestellt, die in einem MPEG Bitstrom angewendet wird. Ein typischen MPEG Bitstrom hat drei Arten von Rahmen:
I (intra-codierter Rahmen),
B (bidirektionaler Vorhalterahmen), und
P (Prädiktions-/Vorhalterahmen).
Der I-Rahmen enthält nur DCT Daten (es wird keine Bewegungskompensation durchgeführt), Folglich deckt die Verwendung des DC Wertes des DCT Koeffizienten zur Errechnung eines Histogramms vollständig das Problem des minimalen Decodieraufwands bei T Rahmen. B und P-Rahmen weisen den zusätzlichen Schritt des Verwendens von Blockbewegungsvektoren zur Prädiktion des aktuellen Rahmens aus vorher decodierten Vergleichsrahmen auf. Somit muss die angewandte Strategie bei den Decodierung den R und P-Rahmen sorgfältig beachtet werden. In der nachfolgenden Erläuterung bezieht sich Fall (a) auf ein Bewegungskompensationsschema, das bereits existiert und in der Literatur allgemein vorkommt. Fall (b) bezieht sich auf ein neuartiges Bewegungskompensationsschema, daß hierin offengelegt wird.
Um die Bewegungskompensation zu vereinfachen, verwenden die meisten bekannten Verfahren das im vorherstehenden Abschnitt genannte Schema, wobei jeder 8 · 8 Unterblock durch einen gewichteten Durchschnittswert der 8 · 8 Unterblöcke ersetzt wird, den überlappt. Betrachten wir zwei Szenarien: Fall (a) ersetzt den 8 · 8 Unterblock mit dem gewichteten Durchschnittswert der überlappenden Blöcke in dem teilweise decodierten Vergleichsrahmen und Fall (b) ersetzt den 8 · 8 Unterblock mit der genauen Pixelzahl aus dem teilweise decodierten Vergleichsrahmen. Im Fall (a) wird ersichtlich, dass der gesamte 8 · 8 Block in dem bewegungskompensierenden Vorhalterahmen einen einzigen Wert aufweist. Im Fall (b) kann der 8 · 8 Block möglicherweise unterschiedliche Werte aufweisen (das heißt die enthaltenen Pixel können unterschiedliche Wette aufweisen. Um dies noch weiter zu veranschaulichen, betrachten wir ein Beispiel eines 8 · 8 Blockes, das die Fälle (a) und (b) durchläuft. Fig. 10 veranschaulicht dies. Bei Fig. 10 wird angenommen, dass der Vorhalteblock aus einem I-Rahmen erhalten wird, das heißt, jeder 8 · 8 Block hat einen einzigen Wert den mit diesem in den Vorhalterahmen verbunden ist. Fall (a) führt zu einem 8 · 8 Block in dem aktuellen Rahmen, der nur einen einzigen u Wert aufweist. Fall (b) führt zu einen 8 · 8 Block in dem aktuellen Rahmen, der möglicherweise vier unterschiedliche Werte aufweist.
Dies verursacht keine große Differenz in den wenigen, ersten bewegungskompensierten Rahmen (P oder B-Rahmen), die auf einen intra-codierten Vergleichsrahmen (bzw. I Rahmen) nachfolgen. In der Tat erscheint es auf Grund der Unempfindlichkeit der Histogramm-Computerberechnung zum Durchschnitt und zur Nachprüfung/Nachabtastung, als ob die beiden Verfahren gleich effektiv zur Histogramm Computerberechnung seien. Jedoch sollte dem Fall (a) der Vorzug gegeben werden, da hier wenig Computerberechnung und Speicherplatzverbrauch erforderlich wird. Dies ist deshalb der Fall, da in jedem vorgegebenen Rahmen- (I oder P oder B), der wie im Fall (a) bewegungskompensiert durchgeführt wird, nur ein einziger Wert für jeden 8 x 8 Block erhalten wird. Somit wird 8mal- weniger Kapazität in jede Dimension benötigt, das heißt, möglicherweise 64mal (8 · 8) weniger Arbeitsspeicher als zum Speichern der gesamten Rahmen. Jedoch könnte Fall (a) zu einem exzessiven Qualitätsverlust führen, wie nachstehend erläutert wird, und stellt somit keine durchführbare Alternative dar.
Da sich die Anzahl der aneinandergrenzenden, bewegungskompensierten Rahmen erhöht, das heißt ohne eine Intervention des I' Rahmens, erhöht sich auch die Differenz zwischen Fall (a) und Fall (b). Zurückkommend auf Fig. 3 betrachten wir, was geschieht, wenn ein Vorhalterahmen von einem bereits bewegungskompensierten Rahmen in Versuchung gebracht wird, zum Beispiel von einem P-Rahmen zu einem B-Rahmen, oder von einem. 2 Rahmen zu einem anderen P-Rahmen zu wechseln. Wenn im Fall (a) die gewichtete Durchschnittsfunktion auf die vier Blöcke angewandt wird, überlappt der Vorhalteblock, wobei jeder einen einzigen Wert aufweist, und endet mit einem einzigen Wert für den gesamten 8 · 8 Vorhalteblock. Im Fall (b) kann der aktuelle Vorhalteblock, da jeder Block in dem Vorhalterahmen möglicherweise vier (oder mehr) verschiedene Werte aufweisen kann, eine große Anzahl verschiedener Werte haben. Nun sollte man die Hauptdifferenz bemerken, die zwischen Fall (a) und (b) entsteht, da diese Kette von Vorhalterahmen aus bereits bewegungskompensierten Rahmen groß wird. Indem man eine ausreichend lange Sequenz von bewegungskompensierten Rahmen bereitstellt, erwartet man, dass Fall (a) einen einzigen Wert für den gesamten Rahmen auswirft, vorausgesetzt, dass es ausreichend Bewegung zwischen den Rahmen gibt, wie später hierin beschrieben wird. Dies geschieht jedoch nicht im Fall (b).
Um dieses Phänomen gründlicher zu erläutern, betrachten wir das Ersetzen eines jeden 8 · 8 Blockes in dem I-Rahmen durch seinen Mittelwert, um eine kleinere Version des Originalbildes zu produzieren. Nun, die Bewegungskompensation, wie im Fall (a) implementiert, benötigt wiederholt eine rekursive Applikation eines 2 · 2 mittelwertbildenden Filters auf diesem kleinen Bild. Mit der elementaren Fourier-Analyse kann leicht dargelegt werden, dass wiederholte Anwendung eines mittelwertbildenden Filters zu einem gleichförmigen Bild an der Abgrenzung führen würde und Randauswirkungen vernachlässigt werden.
In der Praxis konnte beobachtet werden dass die vorgenannten Betrachtungen der Wahrheit entsprechen. In Bezug auf typische MPEG-2 Sequenzkompressionen beträgt der Abstand zwischen zwei I-Rahmen 15. Es wurde festgestellt, dass dies zu einem sehr beachtlichen Qualitätsverlust in der Leistung führt, wenn die Bewegungskompensation entsprechend Fall (a) durchgeführt wird. Das Bewegungskompensations-Schema von Fall (a) erzeugt eine stark periodische Abweichung in den Histogrammen, was zu einer falschen Key-Frame-Erfassung führt. Folglich wurde Fall (b) für die Implementierung verwendet. Die computertechnische Errechnung der Histogramme unter Verwendung eines Decodierverfahrens mit minimalem Aufwand senkt die Geschwindigkeit der Histogramm-Errechnung um die Hälfte der QCIF Sequenz, obgleich der größere Vorteil einer höheren Bildauflösung festgestellt wurde. Gegenwärtig wird ein 512-dimensionaler Histogrammvekton angewandt, und er wird ausgebildet durch Verketten eines 256 bin Grauskala-Histogramms (Y-Komponente) mit einem 128 bin U-Komponenten-Histogramm und einem 128 bin V-Komponenten- Histogramm. Es sollte beachtet werden, dass die vorgenannte Erläuterung auf die Y, U und V-Komponenten eines Rahmens individuell anwendbar ist - ungeachtet des Chromformats.

Extrahieren spezieller Rahmen aus einem MPEG-2 Bitstrom

Das Extrahieren spezieller Rahmen aus einem MPEG-2 Bitstrom in dem hierin beschriebenen Ausführungsbeispiel besteht aus einem Verfahren aus zwei Schritten. Heim ersten Schritte den gleichzeitig mit der Histogramm- Kalkulation ausgeführt wird, wird eine "Bitstromindex-Tabelle" erzeugt, welche die notwendigen Informationen zum schnellen Decodieren eines willkürlich herausgepickten Rahmens aus dem MPEG-2 Bitstrom enthält. Sobald die Key-Frame-Hierarchie generiert ist, das heißt die Identitäten in der hierarchischen Zusammenfassung der zu definierenden Key-Frames, müssen nur die Key-Frames auf der Feinstabstufung der Hierarchie decodiert werden; Rahmen auf einer Grobabstufung der Hierarchie sind eine Teilmenge der Rahmen auf der Feinstabstufung. Der zweite Schritt in dem Verfahren des Key-Frame- Extrahierens wird durch den Decoder-Manager ausgeführt, wie nachstehend erläutert wird, der die im ersten Schritt generierte Bitstromindex-Tabelle benutzt.
Der Vorteil des vorgenannten Zwei-Schritt-Verfahrens bezüglich des direkten Decodierens relevanter Abschnitte des Bitstromes ist eine Ersparnis der Zeit, die erforderlich wäre, um den gesamten Bitstrom des Rahmens von Interesse zu überprüfen. Um Rahmennummer 1350 von einem 1400 Rahmen MPEG-2 Bitstrom ahne eine Bitstromindex-Tabelle zu decodieren, ist es notwendig, den gesamten Bitstrom bis zum Rahmen Nummer 1350 zu analysieren, obwohl er nicht vollständig decodiert sein könnte. Dies beansprucht einen beträchtlichen Zeitaufwand. Falls eine Bitstromindex-Tabelle zur Verfügung steht, kann man direkt zum relevanten Abschnitt des Bitstromes übergehen; folglich ist nur ein Minimalaufwand für das Analysieren und Decodieren erforderlich.
Die nachfolgenden Informationen werden benötigt, um einen willkürlich herausgepickten Rahmen aus einen MPEG-2 Bitstrom zu decodieren, der hierin als aktueller Rahmen bezeichnet wird:
1. Aktuellster Sequenzverteilerkopf der Vergangenheit (sein Byte Offset);
2. Byte Offset des aktuellen Rahmens in dem Bitstrom;
3. Aktuellstes Quantisierungs-Matrix-Reset (falls vorhanden) der Vergangenheit. (sein Byte Offset)
4. Vergleichsrahmen (I-P/I-T/P-P), die mit dem aktuellen Rahmen korrespondieren, falls der aktuelle Rahmen ein B-Rahmen ist (deren Byte Offsets);
5. Aktuellster I-Rahmen (welcher der Vergleichsrahmen zum P-Rahmen ist), falls der aktuelle Rahmen ein P-Rahmen ist (sein Byte Offset).
Es ist anzumerken, das im Fall von B/P-Rahmen mehrere andere Rahmen als der/die Vergleichsrahmen für das Decodieren erforderlich sein können, um den/die Vergleichsrahmen korrekt zu decodieren. Eine allgemeine Datenstruktur ist entwickelt worden, die vorgenannte Informationen beinhaltet, um den Informationsaustausch zwischen zwei Schritten zu erleichtern, das heißt (1) Generieren der Bitstromindex-Tabelle und (2) Verwenden der Bitstromindex-Tabelle des Rahmenextrahierverfahrens durch den Decoder- Manager, wie später hierin beschrieben wird. Das nachfolgende Segment des C-Codes verkörpert die unterschiedlich verwendeten Flags bei der Verfassung/Formulierung der Bitstromindex-Tabelle, obgleich verstanden werden soll, dass dies rein ein Beispiel ist und dass die BIT-Tabelle irgendeine Anzahl von unterschiedlichen Syntaxformen aufweisen kann:
Spezifizierter Indexarchivstand (enum IndexFileState) {
K_SEQUENCE_HEADER = 0,
K_PICTURE_IFRAME,
K_PICTURE_BFRAME,
K_PICTURE_PFRAME,
K_QUANT_MATRIX_EXTENSTON,
K_END_OF_DATA,
K_OFFSET
}:
Das K_OFFSET Flag wird addiert an irgendein Byte Offset, um es von anderen vorher definierten Flags differenzieren zu können. Somit wurde ein Byte Offset von 15 auf 15+ K_OFFSET (= 21) im Verhältnis zu unserer Darstellung übertragen. K_END_OF_DATA- wird verwendet als Delimiter/Abgrenzer zwischen unterschiedlichen Ereignissen/Vorgängen (zum Beispiel Sequenzverteilerkopf und I-Rahmen, oder I-Rahmen und B-Rahmen etc.) Um zu verstehen, wie die generierte Bitstromindex-Tabelle zustande kommt, wird hier angenommen, dass die folgende Sequenz von Ereignissen zum Codieren benötigt wird:
1. Sequenzverteilerkopf startet bei 0 Bytes
2. I Bild bei 150 Bytes
3. P Bild bei 3000 Bytes
4. B Bild bei 4200 Bytes
5. B Bild bei 5300 Bytes
6. Quant-Matrix-Reset bei 5400 Bytes
7. P Bild bei 620% Bytes
Diese Sequenz wird in folgende Darstellung konvertiert:
K_END_OF_DATA_ K SEQUENCE HEADER K_OFFSET+0 K_END_OF_DATA
K_PICTURE_IFRAME K_OFFSET+150 K_END_OF_DATA
K_FICTURE_PFRAME K OFFSET+3000 K_END_OF_DATA
K_ELGTUBE_BERAME
K_OFFSET+4200 K_END_OF_DATA K PICTURE BFRAME K_OFFSET+5300
K_QUANT_MATRIX_EXTENSION K_OFFSET+5400 K_END_OF_DATA
K_PICTURE_PFRAME K_OFFSET+6200 K_END_OF_DATA
Dies wiederum wird eine Byte-Darstellung unter Verwendung der oben angegebenen C-Daten-Struktur ergeben von:
5 0 6 5 1 156 5 2 3006 5 3 4206 5 3 5306 4 5406 5 2 6206 5
Die Abstände in der vorgenannten byteweisen Darstellung sind für den Decoder notwendig, um den Bitstrom analysieren zu können. Nehmen Sie zur Kenntnis, dass das K_END_OF_DATA Flag streng genommen überflüssig ist. Wie immer dieses Flag auch angewendet werden mag, um falsch erzeugte Daten auszuschneiden (auf Grund Fehler in den Bitströmen), es macht den Algorithmus fehlerresistent. Das Flag dient als ein "Synchronsignal", um falsche Daten zu entfernen; zum Beispiel ein Sequenzverteiler, dem kein Byte Offset folgt (auf Grund eines Fehlers im Bitstrom), wird ausrangiert.
Der Decoder-Manager, der die oben erzeugte "Bitstromindex-Tabelle" benutzt, funktioniert wie folgt:
1. Initialisieren der letzten decodierten Rahmen-Nummer (ldf) auf -1
2. Für jeden zu decodierenden (ftd) Rahmen:
Feststellen des Rahmens, bei dem das Decodieren begonnen werden soll (sdf)
Falls "ftd" ein I-Rahmen ist, dann "sdf=ftd";
Falls "ftd" ein P-Rahmen ist, dann sdf=jüngster I-Rahmen vor dem "ftd";
Falls "ftd" ein B-Rahmen ist, dann sdf=jüngster I-Rahmen vor den beiden Ankerrahmen, die zu "ftd" korrespondieren;
Falls das erhaltene, obige "sdf" weniger als ldf+1 ist, Setzen von sdf=ldf+1. Folglich, wenn sdf < ldf+1 ist, sind einige der erforderlichen Rahmen bereits decodiert.
Für i = ldf+1 zu sdf
Feststellen des jüngsten Sequenzverteilers (rsh);
Feststellen des jüngsten Quant-Matrix-Reset (qmr), falls "qmr" größer als "rsh" ist (falls vorhanden).
Decodieren rsh, qmr in der Reihenfolge, wie sie in dem Bitstrom auftreten;
Decodieren sämtlicher I- und P-Rahmen sequentiell, angefangen von sdf bis ftd-1.
Decodierens "ftd".
Um eine Strecke von Rahmen zu decodieren, den ersten Rahmen (ftd) decodieren nach dem vorher erwähnten Decoder-Manager Verfahren. Die restlichen Rahmen werden sequentiell decodiert bis zum Ende der Strecke.
Feldbilder müssen als Spezialfall angesehen werden, im Bedarfsfall. Man kann möglicherweise die Histogramme der gleichen/ungleichen Felder verwenden, was immer auch zuerst decodiert wird. Das andere Feld kann im Falle von H-Bildern nicht decodiert werden, oder es kann im Falle von P- und I- Bildern mit einer minimalen Decodierstrategie decodiert werden. Die Histogramme müssen mit einem Faktor von 2 skaliert/angesetzt werden, falls nur ein Feld decodiert wird. Es kann auch möglich sein, dass das extra decodierte Feld nicht Im der Computerberechnung der Histogramme bezüglich P/I-Rahmen verwendet werden kann. In diesem Fall müssen die Histogramme nicht skaliert werden, da sämtliche Rahmen nur ein Feld haben, das im Histogramm beteiligt ist. Um Felder von Rahmen differenzieren und angemessene Schritte unternehmen zu können, stellen die MPEG-2 Bitströme zwei Informationsteile vom Bildverteiler und von der Bildcodier-Erweiterung zur Verfügung:
1. Temporaler Bezugsvergleich Ein dem Bildverteiler) stellt die Rahmennummer zur Verfügung, die aktuell decodiert wird. Beachten Sie, dass der temporale Bezugsvergleich ein Reset/eine Neueinstellung zu Beginn jeder Bildgruppen-Verteilung hat.
2. Die Bildstruktur (in der Bildcodiererweiterung) stellt die oben/unten Feldinformationen bereit.

Generieren einer ausgeschnittenen Bitstrom-Index-Tabelle zur kompakten Speicherung

Ein wichtiges Thema in implementierender Hinsicht ist die kompakte Darstellung der BIT, um Speicherplatz auf einer Festplatte, DVD oder Diskette zu sparen Auf den ersten Blick könnte das vielleicht nicht als wichtig erachtet werden, da die Bitstromindex-Tabelle nur ungefähr 8-10 Bytes an Speicherplatz für jeden Rahmen in Anspruch nimmt im Vergleich zu dem großen Speicherplatz, der durch die MPEG Videosequenz belegt wird. Der Overhead an Belastung kann durch die nachfolgenden Schritte reduziert werden:
1. Verwenden von inkrementellen Byte Offsets, vorzugsweise als absolute Byte Offsets. Dies führt zu einer Menge an Ersparnis in Bezug auf große Sequenzen.
2. Verwenden eines einfachen Textkomprimierungs-Algorithmus, wie zum Beispiel "qzip" auf Unix-Plattformen oder "pkzip" auf PCs.
3. Entfernen des END_OF_DATA Flag.
4. Ausschneiden der Bitstromindex-Tabelle, um nur eine minimale Menge an notwendiger Information zu speichern, und um die Key-Frames mit minimalem Decodiar- und Analysieraufwand des Bitstromes zu decodieren.
Beachten Sie, dass der letzte Punkt nur den Zugang zu den Key-Frame- Positionen ermöglichen wird und dem Anwender später nicht die Positionen der Key-Frames ändern lässt. Es darf auch angemerkt werden, dass (1) und (4) nicht vollständig kompatibel sind. Wenn inkrementelle Byte Offsets angewendet werden sollen, sollte der Ausschneidealgorithmus von (4) die Byte Offsets ändern, damit die veränderte Reihenfolge der Rahmen reflektiert wird. Bei der aktuellen Implementierung wird eine Ausschnitts-Bitstrom- Index-Tabelle, wie nachstehend beschrieben, generiert. Der Decoder-Manager benutzt diese ausgeschnittene Version der Tabelle anschließend. Die Entscheidung, eine ausgeschnittene Bitstromtabelle zu benutzen, hängt von der Funktionsaufgabe des verfügbaren Speicherplatzes und der zu erzielenden Geschwindigkeit am Wenn genügend Speicherplatz verfügbar ist, gibt es keine Notwendigkeit, die Bitstromtabelle auszuschneiden, da es Platz für die ganze Tabelle gibt und der Abruf und die Bedienung viel schneller sind.

Ausschnitts-Bitstrom-Index-Tabelle

Es wird die gleiche Struktur wie für die Bitstrom-Index-Tabelle (BIT) angewandt, jedoch mit einer unterschiedlichen Organisationssyntax, um die Ausschnitts-Bitstrom-Index-Tabelle (PBIT) zu entwickeln. Jeder Key-Frame wird als eine Einheit dargestellt (zwischen zwei K_END_OF_DATA Flags) im Gegensatz zu jedem Videorahmen, der als eine Einheit in der BIT Tabelle dargestellt wird. Die folgenden Informationen sind notwendig, um einen spezifischen (aktuellen) Key-Frame ohne Analysieren und Decodieren des gesamten Bitstromes zu decodieren:
1. Der Typ des aktuellen Key-Frame (I/B/P).
2. Der Start-Decodier-Rahmen (sdf), der mit dem aktuellen Key-Frame (Byte Offset) korrespondiert. Beachten Sie, dass der tatsächliche "sdf" im Verhältnis zum Byte Offset (nicht ldf+1, falls sdf< ldf+1) gespeichert werden muss, da der Decoder vielleicht sonst nicht sequentiell arbeiten könnte, um sämtliche Key-Frames zu decodieren, da angenommen wurde, dass dieses in der BIT Version des Decoder- Manager enthalten ist. Für den Fall, dass der Decoder sequentiell arbeitet und sdf< ldf+1 gilt, dann muss das Decodieren von ldf+1 beginnen. Diese Information ist bereits verfügbar, da ldf+1 der Videorahmen nach den vorhergehenden Key-Frame ist, dessen Offset verfügbar ist.
3. Byte Offset des aktuellen Key-Frame.
4. Das jüngste Sequenzverteiler Offset. Es besteht keine Notwendigkeit für das K_SEQUENCE_HEADER Flag, da jeden gültige MPEG-2 Bitstrom einen Sequenzverteilerkopf hat.
5. Falls es jemals irgendein Quantisierungs-Matrix-Reset gegeben hat, muss das Quantisierungs-Matrix-Offset mit dem K_QUANT_MATRIX_EXTENSION Flag abgespeichert werden, da vielleicht kein Quantisierunga-Matrix-Reset in einem gültigen MPEG-2 Bitstrom vorhanden ist. Beachten Sie, dass Quantisierungs-Matrix-Resets nicht gespeichert werden müssen, falls das Reset/die Neueinstellung vor dem Sequenzverteilerkopf auftritt, da das Auftreten des Sequenzverteilers automatisch die Quantisierungs-Matrix auf "Reset" einstellt.
Dar Decoder-Manager benutzt die- sdf-Informationen, den Typ des aktuellen Key-Frame und dessen Byte Offset, wie folgt: Falls der gewünschte, aktuelle Key-Frame Typ I oder P ist, wird der Deccder-Manager bei "sdf" das Decodieren starten, den Bitstrom analysieren und nur nach I- und P-Rahmen suchen. Diese I- und P-Rahmen werden decodiert bis der aktuell gewünschte Key-Frame erreicht wird, der ebenso decodiert wird. Bei dieser Technik hat der Decoder-Manager nicht an überprüfen, um festzustellen, ob irgendein Rahmen ein B-Rahmen ist, und folglich sucht er nur nach I- und P- Rahmenköpfe. Wenn der gewünschte, aktuelle Key-Frame ein Typ B ist, wird der Decoder-Manager in Betracht ziehen, jeden Rahmen von "sdf" aus zu starten, all I- oder P-Rahmen zu decodieren und bei jedem B-Rahmen zu stoppen und zu überprüfen, ob dieser Rahmen der gewünschte Key-Frame ist.
Falls der Key-Frame ein Type B ist, möchte man ihn vielleicht mit seinem jüngsten decodierten Bezugsvergleichsrahmen (I oder P) annähern, um die Notwendigkeit des Analysierens der B-Rahmen auszuschalten.
Angenommen, dass ein B-Rahmen der zu decodierende Key-Frame ist, der bei 53500 Bytes Offset startete muss eine Quantisierungs-Matrix aus 43000 Bytes und ein Sequenzverteilerkopf bei 39000 Bytes gelesen werden. Der Rahmen für den Decodierstart beginnt bei 45000 Bytes. Folglich werden diese Daten kodiert:
K_END_OF_DATA K_PICTURE BFRAME K_OFFSET+4S000
K_OFFSET+53200 K_OFFSET+39000
K_QUANT_MATRIX_EXTENSION K_OFFSET+43000 K_END_OF_DATA
Es sollte klar sein, dass die PBIT zu Lasten der erhöhten Computerberechnungszeit durch das Steigern des Analyseaufwandes noch weiter geschmälert werden kann, den der Decoder-Manager durchführt Demzufolge gibt es einen Kompromiss zwischen der Komplexität des Decoder-Managers und der Größe der PBIT Tabelle. Eine entsprechende Balance kann getroffen werden, welche von den Anwendungsanforderungen abhängt. Zum Beispiel kann die PBIT die "sdf" (Startrahmen) und die Byte Offsets aller I- und P-Rahmen zwischen dem sdf und dem aktuellen Key-Frame und die Byte Offset des aktuellen Rahmens speichern, und den Bedarf in Bezug auf den Decoder-Manager ausschalten, um den Bitstrom zu analysieren. Die Konsequenz jedoch ist eine Erhöhung der Größe bezüglich der PBIT Taballe. Das andere Extrem, nur den sdf bzw. Startrahmen und das Byte Offset des Key-Frame abzuspeichern, führt zur kompaktesten Darstellung der FB-IT, aber es erfordert, dass der Decoder-Manager den Bitstrom zwischen dem Startrahmen und den Key-Frame-Positionen analysiert und die I- und. P-Rahmen decodiert.
Um eine automatische Kameraschwenk-/Zoomerfassung/Extrahierfunktionalität zu integrieren, muss der gesamte Rahmen-Bitstrom decodiert werden.
Infolgedessen wird ein System zur Überprüfung der Key-Frames einer digitalen Videosequenz offengelegt. Der Eingangsvideostrom kann eine konventionelle, digitale Videosequenz oder ein auf DCT basierender Kompressionsstrom sein. Obzwar ein bevorzugtes Ausführungsbeispiel gemäß der Erfindung und verschiedene Variationen hierzu offengelegt werden, sollte geschätzt werden, dass weitere Variationen und Modifikationen hierzu gemacht werden können, ohne von der Bandbreite der Erfindung abzuweichen, wie sie in den anhängenden Patentansprüchen definiert ist.

Claims

1. Verfahren zum hierarchischen Zusammenfassen und schnellen Durchsehen einer digitalen Videosequenz, welche folgende Schritte aufweist:

Eingeben eines digitalen Videosignals für eine digitale Videosequenz;

Berechnen der Histogramme (Flächenschaubilder) für die digitale Videosequenz;

Erfassen dar Schussgrenzen innerhalb der digitalem Videosequenz;

Bestimmen der Anzahl der Key-Frames, die jedem Schuss zugeteilt werden;

Lokalisieren den tatsächlichen Position eines jeden Key-Frame, worin ein Rahmen ein Aktionsmaß umfasst, das sich am meisten vom Aktionsmaß des vorhergehenden Key-Frame unterscheidet und als Key-Frame in der Videosequenz bezeichnet wird;

Ausschneiden ausgewählter Key-Frames aus einem Schuss, worin die ausgewählten Key-Frames diejenigen darstellen, die ein Aktionsmaß festlegen, welches nicht vom Aktionsmaß für den vorhergehenden Key-Frame und dem nachfolgenden Key-Frame durch eine Vorgabe abweicht; und

Generieren einer hierarchischen Key-Frame-Zusammenfassung.

2. Verfahren nach Anspruch 1, welches nach dem erwähnten Generieren das schnelle Durchsehen der Key-Frames unter Verwendung der hierarchischen Key- Frame-Zusammenfassung aufweist.

3. Verfahren nach Anspruch 1, welches nach den erwähnten Eingeben das Erfassen und Entfernen der Überblendvorgänge aufweist.

4. Verfahren nach Anspruch 3, welches nach dem erwähnten Erfassen und Entfernen der Überblendvorgänge das Erfassen vollständiger Bewegungsvorgänge durch Erfassen der Rahmen innerhalb der digitalen Videosequenz aufweist, die Vorgänge beinhalten, die aus einer Gruppe von Vorgängen (Ereignissen) entnommen sind und aus Kameraschwenkvorgängen und Zooomvorgängen bestehen.

5. Verfahren nach Anspruch 4, welches das Erfassen von Kameraschwenkvorgängen und das Aufbauen eines Bildmosaiks aufweist.

6. Verfahren nach Anspruch 4, welches das Erfassen, von Zoomvorgängen und das Berechnen/Bewerten der Zoomstufe in dem Vorgang aufweist sowie das Kompilieren einer Zoom-Zusammenfassung.

7. Verfahren nach Anspruch 4, welches das Ausgliedern globaler Bewegungsvorgänge aus dem hierarchischen Zusammenfassungsprozess aufweist.

9. Verfahren nach Anspruch 1, wobei das erwähnte Generieren der hierarchischen Key-Frame-Zusammenfassung das Unterteilen der hierarchischen Key- Frame-Zusammenfassung in multiple Abstufungszusammenfassungen aufweist, einschließlich einer kompaktesten komprimierten Abstufungszusammenfassung, einer Grobabstufungszusammenfassung und einer Feinstabstufungszusammenfassung.

9. Verfahren nach Anspruch 8, welches das schnelle Durchsehen der Key- Frames durch einen Anwender nach dem Auswählen einer speziellen Abstufungszusammenfassung aufweist.

10. Verfahren nach Anspruch 8, wobei die Key-Frames in der hierarchischen Key-Frame-Zusammenfassung in Layout-Strukturen zur Abspeicherung, zum Abruf oder zur Anzeige räumlich eingeteilt/nachüberprüft werden können.

11. Verfahren nach Anspruch 8, wobei das erwähnte Generieren einer hierarchischen Key-Frame-Zusammenfassung das Gruppieren/Bündeln der Key-Frames und das Generieren der Key-Frames bei einer groberen Abstufungszusammenfassung aufweist.

12. Verfahren nach. Anspruch 11, wobei das erwähnte Gruppieren das Erzeugen eines Komprimierungsverhältnisses nach der Anzahl der Key-Frames in der Grobabstufung aufweist.

13. Verfahren nach Ansprucfr 11, wobei das erwähnte Gruppieren ein paarweißes Gruppieren/Bündeln aufweist.

14. Verfahren nach Anspruch 11, wobei das erwähnte Generieren der Key- Frames einer Grobabstufungszusammenfassung das Generieren von Key-Frames die Verwendung vors größtmöglichen sequentiellem/konsekutiven Unterscheidungskriterien aufweist.

15. Verfahren nach Anspruch 8, welches das Identifizieren der Key-Frames durch Setzen von ki = 1 aufweist, wobei t&sub0; = 0 gilt und der zweite Rahmen als Kandidat tur den ersten Key-Frame ausgewählt wird, Definieren für i = 1 bis K-1 und ti = 2 ki = ti-1, ki-1 als ersten Videosequenzrahmen für welchen 2C(ti) - C(ki) ≤ C(ki+1) gilt; und für i = K, Errechnen von t'K = 2kK - t K-1, und solange tk > 2kK - t K-1 = t' K. Beibehalten der Ergebnisse der vorhergehenden Iteration, Addieren eines Offsets zu sämtlichen kis, so dass tK = t'k' gilt, und Stoppen, ansonsten Inkrementieren von ki um 1 und Übergehen zur erwähnten Bestimmung.

16. Verfahren nach Anspruch 15, wobei das erwähnte Errechnen das Lokalisieren des letzten Key-Frames des benachbarten Schusses zum Mittepunkt zwischen tk-1 und tk aufweist.

17. Verfahren nach Anspruch 15, wobei das erwähnte Identifizieren das Auswählen eines jeden (n/K)th Rahmens als Key-Frame aufweist.

18. Verfahren nach Anspruch 15, wobei das erwähnte Identifizieren das Erfassen uninteressanter Schüsse und das Eliminieren von deren Key-Frames aus der hierarchischen Key-Frame-Zusammenfassung aufweist.

19. Verfahren nach Anspruch 1, wobei die digitale Videosequenz eine digitale Videosequenzkompression darstellt und der Eingabeschritt ferner das Generieren einer Bitstromindex-Tabelle aufweist, und wobei der Errechnungsschritt nur teilweise die digitale Videosequenzkompression decodiert.

20. Verfahren nach Anspruch 19, wobei das erwähnte Zuteilen der Key- Frames innerhalb eines jeden Schusses das vollständige Decodieren des Key- Frames aufweist.

21. Verfahren nach Anspruch 20, wobei das erwähnte vollständige Decodieren des Key-Frames das Decodieren des Key-Frames ohne Analysieren des Videobitstromes und ohne vollständiges Decodieren des Videobitstroms unter Verwendung einer Bitstromindex-Tabelle aufweist.

22. Verfahren nach Anspruch 19, wobei das erwähnte teilweise Decodieren eine DCT-basierende (DCTL = direct-coupled-transistor logic) Videosequenzkompression aufweist unter Verwendung des DC-Wertes- der DCT-Koeffizienten, um ein Histogramm (Flächenschaubild) computertechnisch zu berechnen.

23. Verfahren nach Anspruch 19, wobei das erwähnte teilweise Decodieren nur Key-Frames und deren diesbezügliche Rahmen aufweist.

24. Verfahren nach Anspruch 19, wobei das erwähnte Decodieren das Decodieren durch einen Decoder-Manager aufweist.

25. Verfahren nach Anspruch 24, wobei das erwähnte Decodieren durch einen Decoder-Manager die Verwendung einer Bitstromindex-Tabelle zum Decodieren der Key-Frames mit einem minimalem Decodier- und Analysieraufwand des gesamten Videosequenzbitstromes aufweist.

26. Verfahren nach Anspruch 25, wobei das erwähnte Decodieren durch einen Decoder-Manager das Generieren einer zugeschnittenen Bitstromindex-Tabelle und das Speichern nur dar benötigten Informationen zum Decodieren der Key- Frames ohne Analysieren und Decodieren des gesamten Bitstromes aufweist.