DE69628282T2

DE69628282T2 - Verfahren zur kompression mehrerer videobilder

Info

Publication number: DE69628282T2
Application number: DE69628282T
Authority: DE
Inventors: Subutai Ahmad
Original assignee: Interval Research Corp; Palo Alto Research Center Inc
Current assignee: Interval Research Corp; Palo Alto Research Center Inc
Priority date: 1995-09-15
Filing date: 1996-09-13
Publication date: 2004-03-11
Anticipated expiration: 2016-09-14
Also published as: AU7070896A; WO1997010564A1; DE69628282D1; US6259817B1; JPH10509298A; ATE241179T1; US6009204A; EP0804774B1; EP0804774A1; EP0804774A4

Description

Die vorliegende Erfindung betrifft ein Verfahren zum Komprimieren einer Sequenz von Videobildern.
Es ist hinlänglich bekannt, dass ein Videobild, wenn es digitalisiert ist, eine große Menge Speicherplatz benötigt. Eine Sequenz von Videobildern (nachfolgend als "Videoszene" bezeichnet), wie z. B. ein Kinofilm, würde Hunderte von Megabyte oder sogar Gigabyte Speicherkapazität benötigen, wenn sie nicht komprimiert würde.
Verfahren zum Komprimieren einer Videoszene sind in der Technik hinlänglich bekannt. Ein bekanntes Verfahren besteht darin, einen Bildwert durch eine Analyse der Hauptkomponenten für alle Bilder der Videoszene abzuleiten. Nehmen wir einmal an, jedes Videobild habe N Pixel. Danach wird ein Bildwert auf der Basis eines für eine Hauptkomponentenanalyse gewählten Parameters für jedes der Videobilder bestimmt. Somit wäre der resultierende Speicherbedarf für einen Parameter ein Bild voll mit Komponentenwerten für diesen Parameter (oder N Werten) und ein Bildwert in Verbindung mit jedem Videobild. Wenn mehr als ein Parameter für die Videobilder gewählt wird, dann würde sich der benötigte Gesamtspeicherbedarf entsprechend vervielfachen. Beispiele für die Anwendung einer Hauptkomponentenanalyse sind in "Facial-feature Image Coding Using Principal Components" auf den Seiten 2066 und 2067 in Electronics Letters, 1992, Bd. 28, Nr. 22, von W. J Welsh und D. Shah, sowie in "Computer Graphics Animation of Talking Faces Based on Stochastic Models" auf den Seiten 73 bis 76 in der 1994 International Symposium Speech, Image Processing Networks Proceedings, Bd. 1, von N. M. Brooke und S. D. Scott beschrieben.
Aber selbst bei diesem Verfahren wäre, wenn die Videoszene viele Videobilder hat, wie bei einem Kinofilm, der für einen einzelnen Parameter in Verbindung mit jedem der Videobilder benötigte Speicherplatz immer noch groß. Da Videobilder mit einer recht hohen Geschwindigkeit angezeigt werden, z. B. dreißig Mal pro Sekunde, würde ein zweistündiger Videofilm 216.000 Videobilder (2 × 60 × 60 × 30) bei einem standardmäßigen TV-Format 50 Gigabyte Speicherplatz benötigen. Daher würde auf der Basis dieses Verfahrens für einen Parameter jedes Videobild immer noch N Komponentenwerte für eine Hauptkomponentenanalyse und 216.000 Bildwerte mit einem Bildwert für jedes der Videobilder ergeben. Ferner würde, obwohl der benötigte Speicherplatz durch Komprimieren jedes Videobildes mit diesem Verfahren reduziert wird, diese Videoszene zum Betrachten oder Durchlaufen ihrer Videobilder immer noch die Anzeige der gesamten Sammlung von Bildern erfordern, z. B. 216.000 Bilder. Für einen Benutzer wäre das Betrachten oder Durchsuchen der gesamten Kollektion angezeigter Bilder ineffizient und aufwändig. Das Durchlaufen oder Überfliegen der gesamten Kollektion von Videobildern der Videoszene würde eine beträchtliche Menge an Zeit und Aufwand erfordern.
Ein weiteres bekanntes Kompressionsverfahren besteht darin, einige der Bilder aus einer Videoszene als Referenzrahmen auszuwählen. Als Referenzrahmen wird jeder n-te in der Sequenz gewählt. Nachfolgende oder vorangehende Bilder werden mit den Referenzrahmen verglichen, und die Differenzen oder Änderungen werden gespeichert. Somit brauchen nur Daten für die Referenzrahmen und die Änderungen daran gespeichert zu werden.
Die US 5 265 180 offenbart ein weiteres Verfahren zum Codieren einer Sequenz von Bildern eines digitalen Bewegtbild-Videos, wobei Informationen über zukünftige Bilder in der Bildsequenz anhand einer anfänglichen Analyse der Bilddaten vor der Kompression erhalten werden. Durch die anfängliche Analyse werden Informationen über Variationen der Komplexität zwischen Bildern für das Kompressionssystem gewonnen. Anhand dieser Informationen wird die Einstellung eines Kompressionscontrollers ermittelt. Anhand dieser Einstellung werden andere Kompressionssystem-Schwellenwerte und -Quantifizierer skaliert. Darüber hinaus gibt die anfängliche Analyse qualitative Informationen über Events wie z. B. Szenenänderungen, kurze Perioden mit schnellen Bewegungen, Auflösungen, rollende Schnitte (Wipes) sowie das Aussehen eines einzelnen anomalen Bildes.
Da sich die Verwendung von Videobildern zum Erfassen von Informationen immer weiter in den Vordergrund drängt, muss ein Verfahren gefunden werden, um die Mehrzahl von Videobildern oder die Videoszene auf effiziente Weise zu speichern, anzuzeigen und zu durchsuchen. Die Kollektion der angezeigten Videobilder muss auf eine Weise kategorisiert werden, die ein rasches Suchen zulässt. So ist die Kompression der Videobilder nicht nur wichtig, um Speicherplatz minimal zu halten, sondern das Verfahren muss auch Anzeige und schnelle Suche der komprimierten Videobilder noch mehr erleichtern.
Somit befasst sich die vorliegende Erfindung mit den Problemen der Videokompression, um den Speicherbedarf minimal zu halten und um ein effizienteres Verfahren zum Anzeigen und Durchsuchen von Videobildern aus einer Videoszene zuzulassen.
Die vorliegende Erfindung ist im beiliegenden Anspruch 1 definiert, auf den nunmehr Bezug genommen werden sollte.
In einer Ausgestaltung der vorliegenden Erfindung wird eine Mehrzahl von Videobildern komprimiert. Jedes Bild ist durch eine Mehrzahl von Pixeln gekennzeichnet und wird auf der Basis von wenigstens einem Pixelparameter komprimiert. Die Kompression kann auf der Basis einer Hauptkomponentenanalyse erfolgen. Ein Bildwert wird für jedes Videobild für diesen einen Parameter ermittelt. Ein Bildwert in Verbindung mit jedem Videobild wird mit einem Bildwert verglichen, der mit einem anderen Videobild assoziiert ist, um eine Differenz zu ermitteln. Die Differenz wird mit einem Schwellenwert verglichen, der fest oder adaptiv sein kann. Für den Fall, dass die Differenz unterhalb des Schwellenwertes liegt, wird nur einer der Bildwerte gespeichert. Die den gespeicherten Bildwerten entsprechenden Videobilder können angezeigt und durchsucht werden.
Das oben erwähnte Verfahren kann zum Komprimieren einer Videodatenbank mit einer Mehrzahl von Videobildern verwendet werden. Ein oder mehrere "Schlüssel"-Videobilder werden mit dem oben beschriebenen Verfahren ausgewählt. Alle anderen Videobilder der Videodatenbank werden mit den "Schlüssel"-Videobildern verglichen, und die Differenzen werden gespeichert. Die "Schlüssel"-Videobilder an sich, oder die bei der Hauptkomponentenanalyse ermittelten Bilder und Parameterwerte werden ebenfalls gespeichert. Auf der Basis dieser Kompression können alle Videobilder der Videodatenbank getreu reproduziert werden.
In einer anderen Videodatenbank, die eine Mehrzahl von Datenbankelementen hat, wobei jedes Datenbankelement eine Videoszene ist, wird jede Videoszene auf der Basis des oben offenbarten Kompressionsverfahrens komprimiert. Die Videodatenbank wird durchsucht, um eine Übereinstimmung mit einer anfragenden Videoszene zu finden, die ebenfalls eine Mehrzahl von Videobildern umfasst. Die anfragende Videoszene kann ebenfalls mit dem oben offenbarten Kompressionsverfahren komprimiert werden. Die gespeicherten Bildwerte in Verbindung mit der anfragenden Videoszene werden mit den gespeicherten Bildwerten in Verbindung mit jeder Videoszene aus der Videodatenbank verglichen, um eine Übereinstimmung zwischen der anfragenden Videoszene und einer der Videoszenen aus der Videodatenbank zu finden.
KURZE BESCHREIBUNG DER ZEICHNUNGEN
1 ist ein schematisches Diagramm des Verfahrens des Standes der Technik zum Komprimieren von Videobildern auf der Basis einer Hauptkomponentenanalyse.
2 ist ein schematisches Diagramm des verbesserten Verfahrens der vorliegenden Erfindung, nachdem eine Mehrzahl von Videobildern mit dem Hauptkomponentenanalyseverfahren des Standes der Technik komprimiert wurde.
3 ist ein schematisches Diagramm des Verfahrens der vorliegenden Erfindung zum Komprimieren und Speichern einer Mehrzahl von Videobildern wie beispielsweise eines Kinofilms.
4 ist eine schematische Ansicht eines Verfahrens zum Durchsuchen einer Videodatenbank, um eine Übereinstimmung zwischen einer anfragenden Videoszene und einem der Elemente der Videodatenbank zu ermitteln, die jeweils eine Videoszene umfassen.
5 ist eine bildliche Anzeige des Verfahrens der vorliegenden Erfindung, um eine Kollektion von Videobildern aus einer Videoszene auf effiziente und schnelle Weise anzuzeigen und zu durchsuchen.
6 ist eine Ablauftabelle des Verfahrens der vorliegenden Erfindung zum Ermitteln von Videobildern mit Schlüsselbildparametern gemäß dem Verfahren der vorliegenden Erfindung.
7 ist eine Ablauftabelle des Verfahrens der vorliegenden Erfindung zum Komprimieren einer Mehrzahl von Videobildern unter Verwendung von Videobildern mit Schlüsselbildparametern (oder Referenzbildern), ermittelt gemäß dem in 6 gezeigten Verfahren.
8 ist eine Übersicht über die verschiedenen Verfahren der vorliegenden Erfindung und deren Anwendungen.
AUSFÜHRLICHE BESCHREIBUNG DER ZEICHNUNGEN
1 zeigt eine schematische Ansicht des Verfahrens zum Komprimieren einer Videoszene des Standes der Technik. Die Videoszene umfasst eine Mehrzahl von Videotildern oder Videorahmen, mit F₁ ... F_M bezeichnet. Jedes der Videobilder hat eine Mehrzahl von Pixeln, die mit P₁ ... P_N bezeichnet sind. Die Kollektion von Videobildern wird als Videoszene bezeichnet.
Im Stand der Technik ist es bekannt, das Verfahren der Hauptkomponentenanalyse zum Ableiten eines Hauptkomponentenparameterwertes für die Videoszene anzuwenden. Bei dem Verfahren wird ein Parameter für die Mehrzahl von Videobildern F₁ ... F_M gewählt. Beispiele für Parameter sind unter anderem Intensität oder ein(e) bestimmte(r) Farbe oder Farbton oder Raumfrequenz usw. Dann wird ein Bild voll mit Komponenten, z. B. N Komponenten, für diesen einen gewählten Parameter abgeleitet. So werden die Komponentenwerte C₁ ... C_N abgeleitet. Dann wird jedes der Videobilder F₁ ... F_M durch Ermitteln eines Bildwertes I₁ ... I_M für jedes Videobild für die gewählte Parameterkomponente C ermittelt. Der Bildwert I_k wird abgeleitet auf der Basis von:
wobei J ein Index zur Pixelnummer, P_kJ der wert des J-ten Pixels im Rahmen F_k ist.
Aus dem oben Gesagten wird ersichtlich, dass eine M Videobilder umfassende Videoszene ein Videobild voll mit Daten (oder N Werten) für die Komponente umfasst, die mit der Hauptkomponentenanalyse gewählt wurde, und M Bildwerte, mit einem mit jedem Videobild F_k assoziierten Bildwert I_k. Wie zuvor erwähnt, ergeben sich in dem Fall, dass die Videoszene lang ist, z. B. ein Kinofilm von zwei Stunden, und jedes der Videobilder 1/30 Sekunde lang angezeigt wird, 216.000 Videobilder (2 × 60 × 60 × 30). Somit würde selbst unter Anwendung der bekannten Methode der Hauptkomponentenanalyse zum Komprimieren einer Videoszene mit einer Mehrzahl von Videobildern eine erhebliche Menge Speicherplatz, wo die Videoszene lang ist, für jeden von der Nauptkomonentenanlayse abgeleiteten Parameter benötigt. Darüber hinaus würde das Anzeigen, Betrachten oder Durchsuchen der 216.000 Videobilder trotz der Reduzierung des Speicherbedarfs einen erheblichen Aufwand erfordern.
2 zeigt schematisch ein bevorzugtes Verfahren der vorliegenden Erfindung. Das bevorzugte Verfahren der vorliegenden Erfindung reduziert den Speicherbedarf des Komprimierens einer Videoszene unter Verwendung des Verfahrens der Hauptkomponentenanalyse. Bei dieser Hauptkomponentenanalyse wird entweder lokal für verschiedene Regionen desselben Videobildes ein anderer Parameter verwendet, oder es wird global derselbe Parameter über das gesamte Videobild verwendet. Es ist jedoch ersichtlich, dass das Verfahren der vorliegenden Erfindung nicht durch die Technik der Hauptkomponentenanalyse begrenzt ist. So können beispielsweise auch von einer diskreten Kosinustransformation abgeleitete Bildwerte, Gabor-Filter und Wavelets verwendet werden. Mit dem Hauptkomponentenanalyseverfahren werden jedoch ein oder mehrere Parameter erzeugt. Zunächst konzentriert sich die Erörterung auf das Verfahren der vorliegenden Erfindung, das auf einen Parameter angewendet wird. Es ist jedoch klar, dass das Verfahren der vorliegenden Erfindung auf Kompression auf der Basis einer Mehrzahl von Parametern angewendet werden kann, die durch Hauptkomponentenanalyse abgeleitet werden.
Wie zuvor sei angenommen, dass durch die Anwendung des Kompressionsverfahrens auf der Basis der Hauptkomponentenanalyse M Bildwerte erhalten werden. Dies ist dargestellt als I₁, I₂, I₃... I_M.
Danach wird jeder mit einem Videobild F_k assoziierte Bildwert I_k mit einem Bildwert I_k+1 verglichen, der mit einem Videobild F_k+1 assoziiert ist, der sich zeitlich unmittelbar neben dem Videobild F_k befindet. Der Absolutwert der Differenz zwischen den beiden Bildwerten wird erhalten und mit einem Schwellenwert verglichen. Wenn die Differenz zwischen den beiden Bildwerten kleiner ist als ein Schwellenwert, d. h. Ik – Ik+1| ≤ T dann wird entweder der Bildwert I_k oder der Bildwert I_k+1 verworfen. Der verbleibende Bildwert wird gespeichert. Es ist ersichtlich, dass der Schwellenwert T ein fester Schwellenwert oder ein adaptiver Schwellenwert sein kann.
Dies geht aus dem folgenden Beispiel hervor. Das Verfahren der vorliegenden Erfindung beginnt mit dem Vergleichen von I₁ mit I₂. Wenn der Absolutwert der Differenz zwischen den beiden Bildwerten geringer ist als der
Schwellenwert, dann sei angenommen, dass I₁ behalten wird.
Der behaltene Bildwert I₂ wird dann mit dem Bildwert I₃ verglichen, der mit dem Videobild F₃ assoziiert ist, der sich zeitlich unmittelbar daneben befindet. Auch hier verwirft das Verfahren, wenn der Absolutwert der Differenz geringer ist als ein vorbestimmter Schwellenwert, entweder I₁ oder I₃. Auch hier sei wieder angenommen, dass I₁ behalten wird. Diese Technik wird fortgesetzt, bis I₁ mit allen übrigen Bildwerten verglichen ist, d. h. I₂ ... I_M.
Das Verfahren wird mit dem Wählen des nächsten Bildwertes I_k fortgesetzt, der nicht verworfen wurde. Man nehme an, dass I₄ der nächste Bildwert unmittelbar neben I₁ ist, der gespeichert oder behalten wurde. I₄ wird dann mit jedem der verbleibenden Bildwerte I_J verglichen, bis alle verbleibenden Bildwerte mit I₄ verglichen sind. Dieser Prozess wird so lange fortgesetzt, bis alle verbleibenden Bildwerte miteinander verglichen sind.
Wenn ein besonderer Bildwert, z. B. I_k, der mit einem anderen Bildwert verglichen wurde, z. B. I_J größer ist als der Schwellenwert, dann wird keiner der Bildwerte verworfen. Der Vergleich wird fortgesetzt, indem I_k genommen und mit dem Bildwert von I_J+1 verglichen wird, der mit dem Videobild assoziiert ist, das sich dann zeitlich unmittelbar daneben befindet.
Aus dem oben Gesagten geht hervor, dass nur Bildwerte I_k behalten werden, die eine größenmäßige Veränderung von mehr als dem Schwellenwert haben. Eine weitere Kompression der Mehrzahl von Bildwerten wird durch Verwerfen derjenigen Bildwerte erhalten, deren Werte sehr nahe an den zeitlich unmittelbar benachbarten Bildwerten liegen.
Das obige Verfahren wurde zwar mit Bezug auf das Vergleichen eines Bildwertes I_k mit einem anderen Bildwert I_k+1 beschrieben, der mit Videobildern assoziiert ist, die sich zeitlich unmittelbar daneben befinden, aber es ist leicht ersichtlich, dass das Verfahren der vorliegenden Erfindung nicht darauf begrenzt ist. Der Bildwert I_k braucht nicht mit einem Bildwert I_k+1 verglichen zu werden, der mit einem zeitlich unmittelbar benachbarten Videobild assoziiert ist.
I_k kann beispielsweise mit I_k+2 oder sogar mit I_k+3 verglichen werden, die Bildwerte repräsentieren, die sich zeitlich nicht unmittelbar daneben befinden.
Ferner kann das Verfahren der vorliegenden Erfindung mit dem Hauptkomponentenanalyseverfahren des Standes der Technik angewendet werden, wo eine Mehrzahl der unterschiedlichen Parameter durch das Hauptkomponentenanalyseverfahren abgeleitet wird. So kann beispielsweise die die Videobilder F₁ ... F_M umfassende Videoszene mittels einer Hauptkomponentenanalyse komprimiert werden, um eine Mehrzahl von Parametern C_k abzuleiten (wobei k Werte von 1, 2 usw. haben kann). Für jeden der Parameter C_k würde ein Bildwert für jedes Videobild F₁ ... F_M abgeleitet. So würde z. B. dann, wenn drei Parameter abgeleitet würden, die Videoszene der Videobilder F₁ ... F_M wie folgt komprimiert:

(1) Ein Bild voll mit den werten C₁₁ ... C_1N von einer Komponente und einem Bildwert I₁₁ ... I_1M in Verbindung mit einem der Videobilder F₁ ... F_M;
(2) Ein Bild voll mit Werten C₂₁ ... C_2N von einer Komponente und einem Bildwert I₂₁ ... I_2M in Verbindung mit einem der Videobilder F₁ ... F_M;
(3) Ein Bild voll mit Werten C₃₁ ... C_3N einer Komponente und einem Bildwert I₃₁ ... I_3M in Verbindung mit einem der Videobilder F₁ ... FM.

Wo eine Mehrzahl von Parametern mit der Hauptkomponentenanalyse abgeleitet wird, da komprimiert das Verfahren der vorliegenden Erfindung diese Mehrzahl von Parametern weiter durch Berechnen der Differenz der Bildwerte in Verbindung mit zeitlich unmittelbar benachbarten Videobildern gemäß:
Dabei ist k ein Index auf die Mehrzahl von Parametern,
P ist die Gesamtzahl der Parameter,
I_ik ist der k-Parameter von Bildwert I_i,
I_jk ist der k-Parameter von Bildwert I_j.
W_k ist ein Gewichtungsfaktor für Parameter k.
Für alle Parameter kann W_k gleich oder unterschiedlich sein, wobei jeder Parameter anders gewichtet ist. Ferner kann, wie oben erörtert, jeder der Bildwerte I_i und I_j mit Videobildern F_i und F_j assoziiert sein, die sich zeitlich unmittelbar daneben befinden oder die sich zeitlich nicht unmittelbar daneben befinden.
Die obige Gleichung wird zwar für die weitere Kompression mit einer Mehrzahl von Parametern offenbart, aber das Verfahren der vorliegenden Erfindung kann auch mit einem beliebigen anderen Algorithmus angewendet werden, der die Differenz von zwei Bildwerten berechnet, unabhängig davon, ob die Bildwerte durch Hauptkomponentenanalyse abgeleitet werden oder nicht.
Ferner wird infolge der Berechnung der oben erörterten Differenz in dem Fall, dass die Differenz geringer ist als ein vorbestimmter Schwellenwert, einer der Videobildwerte gespeichert, während der andere Bildwert nicht gespeichert wird. Das Ergebnis ist eine weitere Kompression des Stroms von Videobildwerten.
Wie zuvor erörtert, kann der Schwellenwert T fest oder adaptiv sein. Die Beschreibung des obigen Verfahrens bezieht sich auf einen festen Schwellenwert. Alternativ stellt das Verfahren der vorliegenden Erfindung einen adaptiven Schwellenwert bereit, so dass der Benutzer (oder ein Computer) die Anzahl der zu speichernden Bildwerte (und dementsprechend die Anzahl der Videobilder) vorgeben kann. Der Benutzer oder der Computer kann die Anzahl der zu speichernden Bildwerte entweder direkt vorgeben oder er kann indirekt die Zeitdauer zum Anzeigen der Videobilder vorgeben, deren Bildwerte gespeichert werden. Im letzteren Beispiel kann der Benutzer beispielsweise ein Fünf-Minuten-Segment von anzuzeigenden Bildwerten für einen zweistündigen Videofilm vorgeben. So würden (5 × 60 × 30 = 9000) Bildwerte gespeichert.
Das Verfahren fährt dann zunächst mit dem Vergleichen der Bildwerte aller aufeinander folgenden Videobilder fort, um eine Differenz davon zu ermitteln. Unter Verwendung des vorherigen Beispiels werden die Bildwerte mit I₁, I₂, I₃ ... I_M bezeichnet. Danach wird jeder mit einem Videobild F_k assoziierte Bildwert I_k mit einem Bildwert I_k+1 verglichen, der mit einem Videobild F_k+1 assoziiert ist, das sich zeitlich unmittelbar neben dem Videobild F_k befindet. Der Absolutwert der Differenz zwischen den beiden Bildwerten wird ermittelt, d. h. D₁(= |I₁ – I₂|), D₂(= |I₂ – I₃|), D₃ ... D_M–1(= |I_M– 1 – I_M |), wobei D die Differenz ist. Die kleinste Differenz D wird dann gewählt, und einer dieser entsprechenden Bildwerte wird behalten. So wird z. B. dann, wenn D₂ die kleinste Differenz ist, entweder I₂ oder I₃ behalten. Nehmen wir einmal an, dass I₃ behalten wird.
Dann wird aus den übrigen Differenzen D die nächstkleinste Differenz, d. h. D₃, gewählt, und einer der Bildwerte wird verworfen.
Alternativ werden die Differenzen zwischen aufeinander folgenden verbleibenden Bildwerten I neu berechnet, und die kleinste Differenz wird gewählt. So werden beispielsweise für das obige Beispiel die folgenden Differenzen berechnet: D₁(= I₁ – I₃|), D₃ (= |I₃ – I₄|), D₄ ... D_M–1 (= |I_M–1 – I_M|) Die kleinste Differenz wird gewählt, einer der Bildwerte wird behalten.
In jedem Fall wird dieser Prozess wiederholt, bis die gewünschte Anzahl an Videobildern verbleibt. So wird das Problem des Vorspezifierens eines Schwellenwertes eliminiert, und der Schwellenwert kann adaptiv auf der Basis des Videoinhalts der Videoszene gewählt werden. Dies ist aus 5 ersichtlich, wo eine Videoszene neunundvierzig (49) Videobilder umfasst, und mittels des Kompressionsverfahrens der vorliegenden Erfindung, wobei der Benutzer ein gewünschtes Ergebnis von vier (4) Videobildern vorgibt, werden so vier (4) Videobilder ermittelt.
6 zeigt eine Ablauftabelle eines Verfahrens zum Ermitteln von Videobildern mit Schlüsselbildparametern, oder der Auswahl von "Schlüssel"-Bildern, gemäß dem oben beschriebenen Verfahren der vorliegenden Erfindung.
wie aus dem oben Gesagten hervorgeht, reduziert das Kompressionsverfahren der vorliegenden Erfindung den Speicherbedarf für eine Videoszene erheblich. Darüber hinaus ergibt das Verfahren, was noch wichtiger ist, jedoch eine reduzierte Zahl von Videobildern, die leicht angezeigt, durchlaufen oder durchsucht werden können. Die gewählten Videobilder, die angezeigt werden, enthalten Videoinformationen, die die größte Menge an "Änderung" in einem Strom von Videobildern demonstrieren. Die angezeigten gewählten Videobilder sind analog zu Indexen oder einer Inhaltstabelle für eine Textdatei. Auf diese Weise können Durchsuchen oder Durchlaufen einer Videoszene stark vereinfacht werden.
Es ist zu bemerken, dass die Anzeige von "Schlüssel"-Videobildern, die die größte Menge an Änderung des Videoinhalts in einer Videoszene repräsentieren, nicht auf Videobildern zu basieren braucht, die mit der Hauptkomponentenanalyse komprimiert wurden. So kann das Verfahren beispielsweise auf anderen Methoden basieren, die ein oder mehrere Parameter für jedes Videubild ermitteln. Danach wird mit dem Verfahren des Vergleichens aufeinander folgender Bildwerte und des Verwerfens von einem der Bildwerte, wenn die Differenz klein ist (mit einem festen Schwellenwert oder einem adaptiven Schwellenwert), wie oben beschrieben, eine Reihe von "Schlüssel"-Bildwerten berechnet. Die den "Schlüssel"-Bildwerten entsprechenden Videobilder können dann angezeigt werden.
Nach dem Ermitteln der "Schlüssel"-Bildwerte können die diesen "Schlüssel"-Bildwerten entsprechenden Videobilder als Indexbilder zum Komprimieren einer Mehrzahl von Videobildern (wie z. B. ein Kinofilm) in komprimierte Daten verwendet werden, von denen die unkomprimierte Mehrzahl von Videobildern ohne erheblichen Treueverlust reproduziert werden kann.
3 zeigt ein schematisches Diagramm eines Verfahrens der vorliegenden Erfindung zum Komprimieren und Speichern einer Mehrzahl von Videobildern, z. B. ein Kinofilm. Wenn wir einmal annehmen, dass der Kinofilm Z Rahmen umfasst, dann gäbe es eine Anzahl von F₁ ... F_C ... F_J ... F_M... F₂ Videobildern oder Rahmenbildern. Die Rahmen F_C, F_J, F_M und F_Z sind die Indexbilder, d. h. diejenigen Videobilder, deren Schlüsselbildwerte mit dem oben beschriebenen Verfahren ermittelt wurden. Danach wird jedes Videobild, das näherungsweise einem der Indexbilder entspricht, verglichen. So werden
|F₁ – F_C| ... |F_C–1 – F_C|, F_C, |F_C+1 – F_J|, ...
berechnet. Dies ist wie beim Verfahren des Standes der Technik, da die Differenz zwischen verschiedenen Videobildern und den Indexbildern "Pixel für Pixel" berechnet wird. Diese Differenz wird dann zusammen mit den Indexbildern gespeichert. Alternativ wird die Differenz zusammen mit den die Indexbilder und das Hauptkomponentenanalysebild repräsentierenden "Schlüssel"-Bildwerten gespeichert. Mit dieser Kompressionstechnik können alle Videobilder der Videobank getreu reproduziert werden. 7 zeigt eine Ablauftabelle dieses Verfahrens.
Aus dem oben Gesagten geht hervor, dass im Gegensatz zum Verfahren des Standes der Technik, bei dem Referenzrahmen auf der Basis von jedem Satz von N Rahmen gewählt werden, das Kompressionsverfahren für eine Videodatenbank der vorliegenden Erfindung die Wahl der Referenz- oder Indexbilder nicht auf bestimmte zeitliche Positionen begrenzt. Der Vorteil des erfindungsgemäßen Verfahrens lässt sich anhand des nachfolgenden Beispiels ersehen. Man nehme an, dass es siebzehn Videobilder wie folgt gibt:
I₁, I₂, I₃, I₄, ... I₁₇
Man nehme ferner an, dass zwischen Bildern I₄ und I₅ sowie zwischen den Bildern I₁₂ und I₁₃ die größte Änderung vorliegt (z. B. eine abrupte Szenenänderung von einer zur anderen durch die Umschaltung von einer Kamera auf eine andere). Zwischen I₁ und I₄ befindet sich Kamera 1 an einem festen Ort oder "schwenkt", wobei die Differenz zwischen den Bildern minimal ist. Ebenso sei angenommen, dass die Änderungen zwischen den Bildern I₅ und I₁₂ minimal sind. Schließlich sei angenommen, dass auch zwischen I₁₃ und I₁₇ minimale Änderungen vorliegen. Daher gibt es drei Videobilder, die die Bilder I₁–I₄, I₅–I₁₂ und I₁₃ –I₁₇ umfassen.
Mit dem Verfahren der vorliegenden Erfindung werden Bilder I₁, I₅ und I₁, als Indexbilder oder Referenzbilder ermittelt, d. h. als Bilder, deren "Schlüssel"-Bildwerte mit dem oben beschriebenen Verfahren ermittelt wurden. Die Kompression der Bilder I₁–I₁₇ bestünde darin, die Differenz zwischen I₁ und jeweils I₂ ... I₄ zu finden, diese Differenz zu speichern, die Differenz zwischen I₅ und jeweils I₆ ... I₁₂ zu finden und zu speichern, und die Differenzen zwischen I₁₃ und jeweils I₁₄ ... I₁₇ zu finden und zu speichern. Darüber hinaus werden natürlich I₁, I₅ und I₁₃ entweder als Bilder oder die Hauptkomponentenanalyse gespeichert, von der sie abgeleitet wurden.
Im Gegensatz zum Verfahren des Standes der Technik wird eine festgelegte Anzahl von Bildern als Referenzbild gewählt. Wenn beispielsweise jeder achte (8.) Rahmen, d. h. I₁, I₉ und I₁₇ als Index- oder Referenzbilder gewählt wird, dann würde die Differenz zwischen I_l und I₅ eine riesige Differenz ergeben, weil eine große Änderung der Videobilddaten vorliegt. Ebenso würde die Differenz zwischen I₉ und I₁₃ eine große Änderung der Videodaten erfordern.
Im Gegensatz dazu kann unter Verwendung der Bilder mit der größten Änderung als Referenzbilder die Kompression optimiert werden.
Mit dem Verfahren der vorliegenden Erfindung wird es durch eine weitere Komprimierung der Videobilder und durch Reduzieren des Speicherbedarfs in einem weiteren Verfahren der vorliegenden Erfindung möglich, eine Videodatenbank zu durchsuchen. Die Videodatenbank hat eine Mehrzahl von Datenbankelementen, wobei jedes Datenbankelement eine Videoszene mit einer Mehrzahl von Videobildern ist. Jedes Videodatenbankelement wird mit dem Verfahren der vorliegenden Erfindung wie oben beschrieben komprimiert. Es ist jedoch, ähnlich wie in der vorherigen Erörterung, nicht mehr notwendig, einen oder mehrere Parameter für jedes Videobild von der Hauptkomponentenanalyse abzuleiten. Eine anfragende Videoszene umfasst auch eine Mehrzahl von Videobildern. Das Verfahren der vorliegenden Erfindung erlaubt eine Durchsuchung der Videodatenbank, um eine Übereinstimmung zwischen der anfragenden Videoszene und den Videoszenen der Videodatenbank zu finden. Die anfragende Videoszene kann mit dem oben beschriebenen Verfahren der vorliegenden Erfindung komprimiert werden.
Um zu ermitteln, ob eine Übereinstimmung zwischen der anfragenden Videoszene und einem der Videodatenbankelemente vorliegt, werden die mit der anfragenden Videoszene assoziierten gespeicherten Bildwerte mit den gespeicherten Bildwerten verglichen, die mit jedem Datenbankelement assoziiert sind, um eine Übereinstimmung zwischen den Bildwerten zu finden. Ein Verfahren zum Vergleichen der Übereinstimmungen besteht darin, eine exakte Übereinstimmung zu finden. Dies ist jedoch oft nicht möglich. Eine weitere Technik besteht darin, eine statistische Übereinstimmung zwischen den Videobildwerten der anfragenden Videoszene und den Videobildwerten jeder der Videoszenen der Videodatenbank zu finden. So kann beispielsweise der folgende Vergleich angestellt werden:
Dabei ist k ein Index zur Mehrzahl von Parametern und i ein Index zur Mehrzahl von gespeicherten Bildwerten;
P ist die Gesamtzahl der Parameter; L ist die Gesamtzahl der gespeicherten Bildwerte,
VI_1k ist der k-Parameter von Bildwert I₁ aus der Videodatenbank,
I_1k ist der k-Parameter von Bildwert I₁ aus der anfragenden Videoszene,
W_k ist ein Gewichtungsfaktor für Parameter k.
Für den Fall, dass der berechnete Wert unterhalb eines Schwellenwertes liegt, wird eine Übereinstimmung deklariert. Mit diesem erfindungsgemäßen Verfahren wird es dann möglich, auf der Basis eines "Videoclips" die Quelle oder das Videodatenbankelement zu ermitteln, von der/dem das "Videoclip" kam.
Die Videodatenbank braucht natürlich nicht vorkomprimiert zu werden. So können die Videodatenbankdaten zur selben Zeit komprimiert werden wie die anfragenden Videobilder.
Alternativ kann das Durchsuchen einer Videodatenbank, die eine Mehrzahl von Datenbankelementen umfasst, von denen jedes eine Videoszene ist, auf der Basis einer adaptiven Technik wie folgt durchgeführt werden. Wenn wir annehmen, dass ein Benutzer bereit ist, eine Zeitperiode T lang auf die Bearbeitung einer Suche nach einer Übereinstimmung mit einem der Videodatenbankelemente zur warten und der Prozessor eine bekannte Geschwindigkeit/Kapazität hat, dann kann die Zeitperiode T in einen Vergleich von S Videobildern umgesetzt werden. Unter Anwendung des oben beschriebenen adaptiven Vergleichsverfahrens kann jede Videoszene der Videodatenbank in S Videobilder und S Bildwerte komprimiert werden. Dann erfolgt ein Vergleich zwischen den Bildwerten der anfragenden Videoszenen und der Anzahl S von Bildwerten für jedes der Videodatenbankelemente. Das Videodatenbankelement mit der geringsten Gesamtdifferenz wäre dann die nächstliegende Übereinstimmung zwischen der anfragenden Videoszene und dem gewählten Videodatenbankelement. Die anfragende Videoszene könnte, müsste aber nicht in dieselbe Anzahl von Videobildern des Videodatenbankelementes komprimiert werden. Ferner kann jeder beliebige Suchalgorithmus des Standes der Technik zum Vergleichen der anfragenden Videoszene mit den komprimierten Videobildern angewendet werden.
Aus dem oben Gesagten wird ersichtlich, dass mit dem Verfahren der vorliegenden Erfindung eine Videoszene aus einer Mehrzahl von Videobildern stark komprimiert werden kann, um den Speicherbedarf zu verringern. Ferner wird es mit einer Reduzierung des Speicherbedarfs möglich, eine anfragende komprimierte Videoszene zu einer Videodatenbank zum Durchsuchen der Datenbank effizient anzuzeigen und zu durchsuchen, um ein Videodatenbankelement zu ermitteln, das mit der anfragenden Videoszene übereinstimmt.
In der bevorzugten Ausgestaltung wird das Verfahren der vorliegenden Erfindung mit einem Computerprogramm ausgeführt, das auf einer Silicon Graphics Workstation von Silicon Graphics. Inc. aus Mountain View, Kalifornien läuft. Eine Kopie dieses Programms ist in Anhang A dargestellt. Eine Übersicht über die verschiedenen Methoden der vorliegenden Erfindung sind in 8 dargestellt.

Claims

Verfahren zum Komprimieren einer Sequenz von Videobildern, wobei jedes Bild durch eine Mehrzahl von Pixeln gekennzeichnet ist, wobei das genannte Verfahren die folgenden Schritte umfasst: Komprimieren jedes der genannten Videobilder auf der Basis von wenigstens einem Pixelparameter, um einen Bildwert für jedes Videobild für den genannten wenigstens einen Pixelparameter zu ermitteln; Vergleichen jedes der Bildwerte mit dem Bildwert eines anderen Bildes, um eine Differenz zu ermitteln; Verwerfen eines Bildwertes aus jedem Paar verglichener Bildwerte, wenn die davon ermittelte Differenz einen Schwellenwert nicht überschreitet; und Speichern der nicht verworfenen Bildwerte und der Differenzen zwischen den gespeicherten Bildwerten und den verworfenen Bildwerten.
Verfahren nach Anspruch 1, dadurch gekennzeichnet, dass der genannte Schwellenwert fest ist.
Verfahren nach Anspruch 1, dadurch gekennzeichnet, dass der genannte Schwellenwert adaptiv eingestellt wird.
Verfahren nach Anspruch 3, dadurch gekennzeichnet, dass der Schritt des Verwerfens Folgendes umfasst: Verwerfen eines der Bildwerte in Verbindung mit der geringsten Differenz; und Fortfahren mit dem genannten Verwerfungsschritt, bis die Anzahl der verbleibenden Videobildwerte gleich einer vorbestimmten Zahl ist, die kleiner ist als die Mehrzahl von Videobildern in der genannten Sequenz.
Verfahren nach Anspruch 1 oder 4, dadurch gekennzeichnet, dass die Videobilder, für die die Bildwerte ermittelt und miteinander verglichen werden, in der genannten Sequenz von Videobildern unmittelbar nebeneinander liegen.
Verfahren nach Anspruch 1 oder 4, dadurch gekennzeichnet, dass das Komprimieren der Videobilder durch eine Hauptkomponentenanalyse auf der Basis einer Mehrzahl verschiedener Pixelparameter beeinflusst wird.
Verfahren nach Anspruch 6, dadurch gekennzeichnet, dass die genannte Hauptkomponentenanalyse lokal mit einem anderen Pixelparameter für einen anderen Teil jedes Videobildes erfolgt.
Verfahren nach Anspruch 6, dadurch gekennzeichnet, dass die genannte Hauptkomponentenanalyse global mit demselben Pixelparameter durchgeführt wird, der für die Gesamtheit jedes Videobildes verwendet wird.
Verfahren nach Anspruch 8, dadurch gekennzeichnet, dass bei dem Kompressionsschritt eine Mehrzahl von Bildwerten für jedes Videobild ermittelt wird, wobei ein Bildwert mit einem Pixelparameter assoziiert ist.
Verfahren nach Anspruch 9, dadurch gekennzeichnet, dass bei dem genannten Vergleichsschritt die genannte Differenz gemäß der folgenden Formel errechnet wird:
wobei k ein Index auf die Mehrzahl von Parametern ist, P die Gesamtzahl der Parameter ist, I_ik der k-Parameter von Bildwert I_i von Bild i ist, I_jk der k-Parameter von Bildwert I_j von Bild j ist, W_k ein Gewichtungsfaktor für Parameter k ist.
Verfahren nach Anspruch 10, dadurch gekennzeichnet, dass jeder der genannten Gewichtungsfaktoren W_k für alle Parameter k gleich ist.
Verfahren nach Anspruch 10, dadurch gekennzeichnet, dass I_i und I_j Bildwerte sind, die mit Videobildern unmittelbar neben der genannten Sequenz von Videobildern assoziiert sind.
Verfahren nach Anspruch 1 oder 4, dadurch gekennzeichnet, dass der Schritt des Komprimierens jedes Videobildes durch diskrete Kosinustransformation erfolgt.
Verfahren nach Anspruch 1 oder 4, dadurch gekennzeichnet, dass der Schritt des Komprimierens jedes Videobildes mit Hilfe von Gabor-Filtern erfolgt.
Verfahren nach Anspruch 1 oder 4, dadurch gekennzeichnet, dass der Schritt des Komprimierens jedes Videobildes mit Hilfe von Wavelets durchgeführt wird.
Verfahren nach Anspruch 4, dadurch gekennzeichnet, dass die genannte vorbestimmte Zahl von einem Computer vorgegeben wird.
Verfahren nach Anspruch 4, gekennzeichnet durch den folgenden Schritt: Anzeigen oder Ausdrucken der Videobilder, die den nach dem Verwerfungsschritt verbleibenden Bildwerten entsprechen.
Verfahren zum Suchen in einer Videodatenbank mit einer Mehrzahl von Videoszenen, wobei jede Szene eine Mehrzahl von Videobildern hat, wobei jedes der genannten Videobilder durch eine Mehrzahl von Pixeln gekennzeichnet ist, um eine bereinstimmung mit einer ersten Mehrzahl von Videobildern zu finden, wobei das genannte Verfahren die folgenden Schritte umfasst: Komprimieren der Videobilder jeder Videoszene der genannten Videodatenbank mit einem Verfahren nach Anspruch 1; Vergleichen der mit der genannten ersten Mehrzahl von Videobildern assoziierten Bildwerte mit den genannten gespeicherten Bildwerten, die mit jeder Videoszene assoziiert sind, um eine Übereinstimmung zwischen der genannten ersten Mehrzahl von Videobildern und einer der genannten Videoszenen zu finden.
Verfahren nach Anspruch 1 oder 18, dadurch gekennzeichnet, dass der Schritt des Komprimierens jedes Videobildes durch Hauptkomponentenanalyse erfolgt.
Verfahren zum Suchen in einer Videodatenbank mit einer Mehrzahl von Videoszenen, wobei jede Szene eine Mehrzahl von Videobildern hat, wobei jedes der genannten Videobilder durch eine Mehrzahl von Pixeln gekennzeichnet ist, um eine Übereinstimmung mit einer ersten Mehrzahl von Videobildern zu finden, wobei das genannte Verfahren Folgendes umfasst: Komprimieren der Videobilder jeder Videoszene der genannten Videodatenbank mit einem Verfahren nach Anspruch 4 oder 5; und Vergleichen der Bildwerte in Verbindung mit der genannten ersten Mehrzahl von Videobildern mit den genannten gespeicherten Bildwerten, die mit jeder Videoszene assoziiert sind, um eine Übereinstimmung zwischen der genannten ersten Mehrzahl von Videobildern und einer der genannten Videoszenen zu finden.
Verfahren nach Anspruch 20, dadurch gekennzeichnet, dass der Schritt des Komprimierens jedes Videobildes durch Hauptkomponentenanalyse erfolgt.
Verfahren nach Anspruch 20, gekennzeichnet durch die folgenden Schritte: Komprimieren der genannten ersten Mehrzahl von Videobildern zu einer geringeren vorbestimmten Zahl von Schlüsselbildern, wobei die genannte vorbestimmte Zahl von Schlüsselbildern von einem Benutzer vorgegeben wird, mit einem Verfahren gemäß Anspruch 4; Speichern der verbleibenden Bildwerte und von deren zugehörigen Videobildern aus der genannten ersten Mehrzahl von Videobildern.
Verfahren nach Anspruch 22, dadurch gekennzeichnet, dass jedes Videobild der genannten ersten Mehrzahl durch diskrete Kosinustransformation oder mit Gabor-Filtern oder Wavelets komprimiert wird.
Verfahren nach Anspruch 4, gekennzeichnet durch die Schritte des Vergleichens jedes Videobildes mit einem der Videobilder mit einem verbleibenden Bildwert, um eine Mehrzahl von Videodifferenzen zu ermitteln; und Speichern der genannten Videodifferenzen und der Videobilder mit verbleibenden Bildwerten.