DE69230704T2

DE69230704T2 - Verfahren und Einrichtung zur Kompression von sich bewegenden Videobildern mit adaptiver Bitzuordnung und Quantisierung

Info

Publication number: DE69230704T2
Application number: DE69230704T
Authority: DE
Inventors: Cesar Augusto Gonzales; Eric Viscito
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1991-11-08
Filing date: 1992-10-23
Publication date: 2000-08-31
Anticipated expiration: 2012-10-24
Also published as: US5231484A; EP0959627B1; CN1035593C; JP2818340B2; TW221085B; CN1072554A; CA2077058C; KR930011724A; DE69233411D1; EP0540961B1; JPH05252507A; EP0540961A2; EP0959628A2; EP0959627A2; EP0959628A3; EP0540961A3; DE69230704D1; EP0959627A3; DE69233411T2; KR960007264B1

Description

Die vorliegende Erfindung betrifft die Datenkomprimierung und speziell ein Verfahren und ein System zur Komprimierung von sich bewegenden, digitalen Videosignalen mit Algorithmen, die mit bei dem aufkommenden MPEG-Standard, der von der International Standards Organization's Moving Picture Experts Group (MPEG) vorgeschlagen wurde, in Einklang stehen.
Technische Fortschritte in digitalen Übertragungsnetzwerken, digitale Speichermedien, hochintegrierte Bauelemente und die digitale Verarbeitung von Video- und Audiosignalen tragen gemeinsam dazu bei, daß die Übertragung und Speicherung von digitalen Videosignalen in vielen Bereichen wirtschaftlich wird. Da die Speicherung und Übertragung digitaler Videosignale der zentrale Punkt vieler Anwendungen ist und da eine nicht komprimierte Darstellung eines Videosignals sehr viel Speicher beansprucht, ist der Einsatz von Verfahren zur Komprimierung digitaler Videodaten von höchster Bedeutung für diesen aufstrebenden Bereich. In dieser Hinsicht haben sich in den letzten zehn Jahren mehrere internationale Standards zur Komprimierung digitaler Videosignale entwickelt, und weitere werden derzeit entwickelt. Diese Standards betreffen Algorithmen für die Übertragung und Speicherung digitaler Videodaten in verschiedenen Anwendungen wie z. B. Übertragungen über Bildtelefone sowie Telekonferenzen; digitale Fernsehübertragung hoher Qualität über Koaxial- und Glasfasernetzwerke sowie Rundfunk über terrestrische Anlagen oder direkte Rundfunksatelliten; und interaktive Multimedia-Produkte auf CD-ROM, DAT-Bändern und Festplattenlaufwerken.
Einige dieser Standards beinhalten Algorithmen auf der Basis eines gemeinsamen Kerns von Komprimierungsverfahren, z. B. CCITT (Consultative Committee on International Telegraphy and Telephony) Recommendation II.120, CCITT Recommendation II.261, und ISO/IEC MPEG-Standard. Der MPEG-Algorithmus wurde von der Moving Pictures Experts Group (MPEG), einem Teil eines gemeinsamen technischen Komitees der International Standards Organization (ISO) und der International Electrotechnical Commission (IEC), entwickelt. Das MPEG-Komitee hat einen Standard für die komprimierte Darstellung von Video- und zugehörigen Audiosignalen im Multiplexbetrieb entwickelt. Der Standard definiert die Syntax des komprimierten Bitstroms und das Decodierungsverfahren, läßt aber reichlich Freiraum für neue Entwicklungen und Vielfalt in dem Algorithmus, der im Codierer verwendet wird.
Da die vorliegende Erfindung in Verbindung mit einem solchen Codierer verwendet werden kann, sollen im folgenden einige wichtige Aspekte des MPEG-Videokomprimierungsalgorithmus kurz erläutert werden, damit die Erfindung besser zu verstehen ist. Es sei aber angemerkt, daß die Erfindung auch auf andere Videocodierungsalgorithmen angewendet werden kann, die ebenfalls einige Merkmale des MPEG-Algorithmus besitzen.

Der MPEG-Videokomprimierungsalgorithmus

Die Komprimierung eines beliebigen Datenobjekts, z. B. einer Textseite, eines Bildes, einer Sprachsequenz oder einer Video sequenz kann man sich bekanntlich als eine Abfolge mehrerer Schritte vorstellen, u. a. 1) die Aufgliederung des Objekts in eine Sammlung von Tokens; 2) die Darstellung dieser Tokens in Form von Binärziffernfolgen, die in irgendeinem Sinn eine Minimallänge besitzen; und 3) die Verkettung der Binärziffernfolgen in einer festgelegten Reihenfolge. Schritt 2 und 3 sind verlustfrei, d. h. die ursprünglichen Daten können originalgetreu rekonstruiert werden, und Schritt 2 wird als Entropiecodierung bezeichnet. (Siehe beispielsweise T. BERGER, Rate Distortion Theory, Englewood Cliffs, NJ: Prentice-Hall, 1977; R. McELIECE, The Theory of Information and Coding, Reading, MA: Addison-Wesley, 1971; D. A. HUFFMAN, "A Method for the Construction of Minimum Redundancy Codes", Proc. IRE, S. 1098- 1101, September 1952; G. G. LANGDON, "An Introduction to Arithmetic Coding," IBM J. Res. Develop., Bd. 28, S. 135-149, März 1984). Schritt 1 kann im allgemeinen entweder verlustfrei oder mit einem Verlust behaftet sein. Bei den meisten Videokomprimierungsalgorithmen geht aufgrund strenger Anforderungen an die Bitrate Information verloren. Ein erfolgreicher verlustbehafteter Komprimierungsalgorithmus eliminiert redundante und irrelevante Information, indem er relativ große Fehler zuläßt, wo sie wahrscheinlich nicht auffallen, und Aspekte einer Sequenz, die ein menschlicher Betrachter sehr differenziert wahrnimmt, sehr genau wiedergibt. Die im MPEG-Algorithmus verwendeten Verfahren für Schritt 1 können als vorhersagende/interpolierende, bewegungskompensierte, hybride DCT/DPCM-Codierungsverfahren bezeichnet werden. Die Huffman-Codierung, die auch als Codierung mit variabler Länge bezeichnet wird (siehe oben zitierte Veröffentlichung von HUFFMAN 1952), kommt in Schritt 2 zum Einsatz. Zwar ist der MPEG-Standard eigentlich eine Spezifikation des Decoders und der Syntax des komprimier ten Bitstroms, die folgende Beschreibung der MPEG-Spezifikation geht aber der einfacheren Darstellung wegen in erster Linie vom Standpunkt eines Codierers aus.
Der MPEG-Videostandard definiert eine codierte Darstellung von Videodaten für digitale Speichermedien wie in ISO-IEC JTC1/SC2/WG11 MPEG CD-11172, MPEG Committee Draft, 1991 festgelegt. Der Algorithmus ist für den Betrieb mit Komponentenvideo im Non-Interlaced-Modus entwickelt worden. Jedes Bild besteht aus drei Komponenten: Luminanz (Y), Rotwertdifferenz (Cr) und Blauwertdifferenz (Cb). Die Cr- und Cb-Komponenten haben sowohl in horizontaler als auch in vertikaler Richtung jeweils halb so viele Abtastungen wie die Y-Komponente. Abgesehen von dieser Festlegung des Eingangsdatenformats gibt es keine Einschränkungen bezüglich des Umfangs oder der Art der Vorverarbeitung, der die Quellenvideosequenzen als Vorbereitung auf die Komprimierung unterzogen werden können. Verfahren für eine solche Vorverarbeitung sind eine der Aufgaben der vorliegenden Erfindung.

Mehrschichtiger Aufbau einer MPEG-Sequenz

Ein MPEG-Datenstrom besteht aus einem Videostrom und einem Audiostrom, die zusammen mit Systeminformationen und möglicherweise mit anderen Bitströmen in einen Systemdatenstrom gepackt sind, der als mehrschichtig betrachtet werden kann. Innerhalb der Videoebene des MPEG-Datenstroms sind die komprimierten Daten weiter in mehreren Schichten oder Ebenen angeordnet. Eine Beschreibung der mehrschichtigen Struktur trägt zum besseren Verständnis der Erfindung bei. Die einzelnen Schichten oder Ebenen der MPEG-Video-Ebenenstruktur sind in in Fig. 1-4 dargestellt. Im einzelnen haben die Zeichnungen folgenden Inhalt:
Fig. 1: Beispiel für ein Paar Bildergruppen (GOPs).
Fig. 2: Beispiel für die Unterteilung eines Bildes in Makroblöcke (MBs).
Fig. 3: Beispiel für die Unterteilung eines Bildes in Ausschnitte.
Fig. 4: Unterteilung eines Makroblocks.
Die Ebenen gehören ebenso zur Funktionsweise des Komprimierungsalgorithmus wie die Zusammensetzung eines komprimierten Bitstroms. Die höchste Ebene ist die Videosequenzebene, die Steuerinformationen und Parameter für die gesamte Sequenz enthält. Auf der nächsten Ebene wird eine Sequenz in Gruppen aufeinanderfolgender Bilder, die sog. Bildergruppen (GOPs) unterteilt. Der allgemeine Aufbau dieser Ebene ist in Fig. 1 dargestellt. Die Decodierung kann am Anfang einer beliebigen GOP beginnen, im wesentlichen unabhängig von den vorausgehenden GOPs. Die Anzahl der Bilder in einer GOP ist nicht begrenzt, und es müssen auch nicht alle GOPs gleich viele Bilder enthalten.
Die dritte Ebene oder Bildebene ist ein Einzelbild. Der allgemeine Aufbau dieser Ebene ist in Fig. 2 dargestellt. Die Luminanzkomponente jedes Bildes wird in 16 · 16 Bereich aufgeteilt; die Farbdifferenzkomponenten werden in 8 · 8 Bereiche aufgeteilt, die sich räumlich mit den 16 · 16 Luminanzbereichen decken. Zusammengenommen bilden diese deckungsgleichen Luminanz- und Farbdifferenzbereiche die fünfte Ebene, den sog. Makroblock (MB). Makroblöcke in einem Bild werden beginnend mit Makroblock 1 in lexikographischer Reihenfolge durchnumeriert.
Zwischen der Bildebene und der MB-Ebene liegt die vierte Ebene, die Ausschnittebene. Jeder Ausschnitt besteht aus der gleichen Anzahl aufeinanderfolgender MBs. Ausschnitte müssen weder innerhalb eines Bildes noch von Bild zu Bild die gleiche Größe haben. Sie können nur aus einigen wenigen Makroblöcken bestehen oder mehrere MB-Reihen umfassen wie in Fig. 3.
Schließlich bestehtt, jeder MB aus vier 8 · 8 Luminanzblöcken und zwei 8 · 8 Farbdifferenzblöcken (Fig. 4). Wenn die Breite jedes Luminanzbildes (in Bildelementen oder Pixeln) mit C und die Höhe mit R bezeichnet wird (C für Spalten, engl. columns; R für Zeilen, engl. rows), ist ein Bild CMR = C/16 MBs breit und RMR = R/16 MBs hoch. Entsprechend ist es CR = C/8 Blöcke breit und RR = R/8 Blöcke hoch.
Die Sequenz-, GOP-, Bild- und Ausschnittebene sind jeweils mit Kopfdaten versehen. Die Kopfdatenabschnitte beginnen mit an Bytegrenzen ausgerichteten Startcodes und enthalten Informationen über die in der betreffenden Ebene enthaltenen Daten.
Innerhalb einer GOP können drei Arten von Bildern vorkommen. Das Unterscheidungsmerkmal zwischen den Bildtypen ist das verwendete Komprimierungsverfahren. Im ersten Typ werden Intramode-Bilder oder I-Bilder unabhängig von allen anderen Bildern komprimiert. Zwar gibt es keine feste Obergrenze für den Abstand zwischen I-Bildern, es wird aber erwartet, daß sie in einer Sequenz häufig vorkommen, um einen direkten Zugriff und andere spezielle Betriebsarten zu erleichtern. Jede GOP muß mit einem I-Bild beginnen und kann weitere I-Bilder enthalten. Die anderen beiden Bildtypen, vorhersagend bewegungskompensierte Bilder (P-Bilder) und bidirektional bewegungskompensierte Bilder (B-Bilder) werden weiter unten im Zusammenhang mit der Bewegungskompensation erläutert.
Für die Anzahl und Reihenfolge von I-, P- und B-Bildern in einer GOP gibt es bestimmte Regeln. I- und P-Bilder werden kollektiv als Anker-Bilder bezeichnet, und eine GOP muß mindestens ein Ankerbild enthalten, sie kann aber auch mehrere enthalten. Außerdem können zwischen zwei benachbarten Ankerbildern null oder mehr B-Bilder vorkommen. Eine typische GOP ist in Fig. 5 dargestellt.

Makroblock-Codierung in I-Bildern

Ein sehr nützliches Bildkomprimierungsverfahren ist die Transformationscodierung. (Siehe N. S. JAYANT and P. NOLL, Digital Coding of Waveforms, Principles and Applications to Speech and Video, Englewood Cliffs, NJ: Prentice-Hall, 1984, und A. G. TESCHER, "Transform Image Coding", in W. K. Pratt, Hrsg., Image Transmission Techniques, S. 113-155, New York, NY: Academic Press, 1979.) In MPEG und einigen anderen Komprimierungsstandards ist die gewählte Transformation die diskrete Kosinustransformation (DCT). (Siehe K. R. RAO and P. YIP, Discrete Cosine Transform, Algorithms, Advantages, Applications, San Diego, CA: Academic Press, 11990, und N. AHMED, T. NATARAJAN, und K. R. RAO, "Discrete Cosine Transform", IEEE Transactions on Computers, S. 90-93, Januar 1974.) Die Komprimierung eines I- Bildes erfolgt in drei Schritten: 1) Anwendung der DCT auf Pixelblöcke, 2) Quantisierung der DCT-Koeffizienten und 3) Huffman-Codierung des Ergebnisses. In MPEG konvertiert die DCT- Operation einen Block aus n · n Pixeln in einen n · n Satz von Transformationskoeffizienten. Wie auch einige der internationalen Komprimierungsstandards verwendet der MPEG-Algorithmus eine DCT-Blockgröße von 8 · 8. Die DCT-Transformation selber ist verlustfrei und kann innerhalb der Präzisionsgrenzen des Computers und des Algorithmus, mit dem sie durchgeführt wird, wieder rückgängig gemacht werden.
Der zweite Schritt, die Quantisierung der DCT-Koeffizienten, ist die primäre Verlustquelle im MPEG-Algorithmus. Die Elemente der zweidimensionalen Matrix der DCT-Koeffizienten werden mit cmn bezeichnet, wobei m und n eine Zahl zwischen 0 und 7 ist; abgesehen von Abschneide- oder Rundungskorrekturen erfolgt die Quantisierung durch Division jedes DCT-Koeffizienten cmn durch wmn · QP, wobei wmn ein Gewichtungsfaktor und QP der Quantisierungsparameter ist. QP wird auf jeden DCT-Koeffizienten angewendet. Der Gewichtungsfaktor wmn ermöglicht eine gröbere Quantisierung der optisch weniger wichtigen Koeffizienten. Es kann zwei Gruppen dieser Gewichtungen geben, eine für I-Bilder und die andere für P- und B-Bilder. Auf der Videosequenzebene können benutzerspezifische Gewichtungen übermittelt werden, oder es können Standardwerte verwendet werden. Der Quantisierungsparameter QP ist in MPEG das primäre Mittel, um Qualität und Bitrate gegeneinander abzuwägen. Es ist wichtig zu wissen, daß QP innerhalb eines Bildes von MB zu MB unterschiedlich sein kann. Diese Eigenschaft, die adaptive Quanti sierung (AQ), ermöglicht es, daß verschiedene Teile jedes Bildes mit unterschiedlicher Schrittgröße quantisiert werden kann, und kann zum Versuch einer Egalisierung (und Optimierung) der visuellen Qualität innerhalb des Bildes und von einem Bild zum anderen verwendet werden. Der MPEG-Standard erlaubt zwar die adaptive Quantisierung; Algorithmen, die aus Regeln für die Verwendung der AQ zur Verbesserung der visuellen Qualität bestehen, unterliegen aber nicht der Standardisierung. Eine Klasse von Regeln für die AQ ist ein Ziel der vorliegenden Erfindung.
Nach der Quantisierung werden die DCT-Koeffizientendaten für jeden MB organisiert und mittels eines Hoffman-Codesatzes codiert. Da die Details dieses Schrittes nicht unbedingt für das Verständnis der Erfindung erforderlich und außerdem in Fachkreisen allgemein bekannt sind, wird hier nicht näher darauf eingegangen. Weitere Informationen zu diesem Thema finden sich in der oben genannten Veröffentlichung von HUFFMAN 1952.

Bewegungskompensation

Die meisten Videosequenzen weisen einen hohen Grad der Korrelation zwischen aufeinanderfolgenden Bildern auf. Ein nützliches Verfahren zum Entfernen dieser Redundanz vor der Codierung eines Bildes ist die "Bewegungskompensation". Für die Bewegungskompensation wird ein Mittel zum Modellieren und Abschätzen der Bewegung in einer Szene benötigt. In MPEG ist jedes Bild in Makroblöcke (MBs) unterteilt, und jeder MB wird mit 16 · 16 Bereichen an der gleichen räumlichen Position in einem oder mehreren Vorhersagebildern verglichen. Der Bereich im Vorhersagebild bzw. in den Vorhersagebildern, der auf ir gendeine Weise am besten mit dem MB übereinstimmt, wird als Vorhersage verwendet. Der Unterschied zwischen der räumlichen Position des MB und der des Vorhersagebereichs wird als Bewegungsvektor bezeichnet. Die Ausgabe der Bewegungsabschätzung und -kompensation für einen MB sind also Bewegungsvektoren und ein bewegungskompensierter Makroblock. In komprimierter Form benötigen diese in der Regel weniger Bits als der ursprüngliche MB selber. Bilder, die anhand eines einzigen Vorhersagebildes vorhersagend bewegungskompensiert werden, werden als P- Bilder bezeichnet. Diese Art der Vorhersage wird in MPEG auch als Vorwärts-Vorhersage bezeichnet.
Wie bereits erwähnt kann das Zeitintervall zwischen einem P- Bild und seinem Vorhersagebild größer als ein Bildintervall sein. Bei Bildern, die zwischen P-Bilder oder zwischen ein I- Bild und ein P-Bild fallen, kann zusätzlich zur Vorwärtsvorhersage auch eine Rückwärtsvorhersage verwendet werden (siehe Fig. 5). Solche Bilder werden als bidirektional bewegungskompensierte Bilder oder B-Bilder bezeichnet. Bei B-Bildern ist zusätzlich zur Vorwärts- und Rückwärtsvorhersage außerdem eine interpolierende Kompensation erlaubt, bei der das Vorhersagebild ein Durchschnitt aus einem Block des Vorwärtsvorhersagebildes und einem Block des Rückwärtsvorhersagebildes ist. In diesem Fall sind zwei Bewegungsvektoren erforderlich.
Die Verwendung der bidirektionalen Bewegungskompensation führt zu einer aus zwei Ebenen bestehenden Bewegungskompensationsstruktur (siehe Fig. 5). Die Pfeile sind so gezeichnet, daß die Spitze das Vorhersagebild berührt und das hintere Ende das Bild, das zur Vorhersage verwendet wird. Alle P-Bilder werden mit Hilfe des vorausgehenden Ankerbildes (I- oder P-Bild) be wegungskompensiert. Alle B-Bilder werden mit Hilfe der Ankerbilder unmittelbar vor und nach dem betreffenden B-Bild bewegungskompensiert. In MPEG ist weder eine Obergrenze für den Abstand zwischen den einzelnen Ankerbildern noch eine Grenze für den Abstand zwischen I-Bildern festgelegt. Diese Parameter müssen nicht einmal über die gesamte Sequenz gleich bleiben. Wenn der Abstand zwischen I-Bildern mit N und der Abstand zwischen P-Bildern mit M bezeichnet wird, hat die in Fig. 5 dargestellte Sequenz (N, M) = (9,3). Beim Codieren der drei Bildtypen sind unterschiedliche Mengen komprimierter Daten notwendig, um eine ähnliche Qualität des rekonstruierten Bildes zu erreichen. Die genauen Verhältnisse sind von vielen Faktoren abhängig, u. a. von der Menge räumlicher Details in der Sequenz und von der Menge und Kompensierbarkeit der Bewegung in der Sequenz.
Es ist deshalb klar, daß eine MPEG-1 Sequenz aus einer Reihe von I-Bildern besteht, zwischen denen null oder mehr P-Bilder eingeschoben sein können. Zwischen den verschiedenen I- und P- Bildern können entweder null B-Bilder oder ein oder mehrere B- Bilder eingeschoben sein; im letzteren Fall dienen diese als Ankerbilder.

Makroblockcodierung in P-Bildern und B-Bildern

Wie bereits erwähnt gibt es drei Arten der Bewegungskompensation, die auf MBs in B-Bildern angewendet werden können: die Vorwärtskompensation, die Rückwärtskompensation und die interpolierende Kompensation. Der Codierer muß eine dieser Kompensationsarten auswählen. Bei einigen MBs ergibt keine der Bewegungskompensationsarten eine genaue Vorhersage. In solchen Fällen kann der MB genauso verarbeitet werden wie ein Makroblock in einem I-Bild, d. h. als Intramode-MB). Dies ist ein anderer möglicher MB-Modus. Es gibt also mehrere MB-Modi für P- und B-Bilder.
Abgesehen von der Notwendigkeit, Nebeninformationen zu codieren, die den zur Codierung jedes MB verwendeten MB-Modus und eventuelle Bewegungsvektoren für diesen Modus betreffen, ist die Codierung bewegungskompensierter Makroblöcke fast gleich wie die von Intramode-MBs. Trotz eines geringen Unterschiedes bei der Quantisierung gilt das Modell der Division durch wmn · QP auch hier. Außerdem kann eine adaptive Quantisierung (AQ) verwendet werden.

Steuerung der Bitrate

Der MPEG-Algorithmus ist primär für die Verwendung in Speichermedien mit fester Bitrate konzipiert worden. Die Anzahl der Bits in den einzelnen Bildern ist aber wegen den unterschiedlichen Arten der Bildverarbeitung sowie der inhärenten zeitlichen Variation der räumlich-zeitlichen Komplexität der zu codierenden Szene nicht exakt konstant. Der MPEG-Algorithmus verwendet eine pufferbasierte Ratensteuerungsstrategie, um der zulässigen Variation der Bitrate sinnvolle Grenzen zu setzen. Ein Videopufferprüfer (VBV) wurde in Form eines virtuellen Puffers konzipiert, dessen einzige Aufgabe darin besteht, die Anzahl der zur Codierung der einzelnen Bilder verwendeten Bits zu begrenzen, so daß die Gesamt-Bitrate der Sollzuordnung entspricht und die kurzzeitige Abweichung vom Sollwert begrenzt ist. Dieses Schema der Bitratensteuerung kann wie folgt erklärt werden. Angenommen ein System besteht aus einem Puf fer, auf den ein hypothetischer Decoder folgt. Der Puffer wird mit konstanter Bitrate mit komprimierten Daten in einem Bitstrom vom Speichermedium gefüllt. Sowohl die Puffergröße als auch die Bitrate sind Parameter, die im komprimierten Bitstrom übermittelt werden. Nach einer anfänglichen Verzögerung, die ebenfalls aus Informationen im Bitstrom abgeleitet werden, entfernt der hypothetische Decoder sofort alle Daten des ersten Bildes aus dem Puffer. Danach entfernt der Decoder in Intervallen, die mit der Bildrate der Sequenz identisch sind, alle Daten des frühesten Bildes aus dem Puffer. Damit der Bitstrom die MPEG-Anforderungen an die Steuerung der Bitrate erfüllt, müssen alle Daten jedes Bildes zu dem Zeitpunkt im Puffer verfügbar sein, an dem sie vom Decoder benötigt werden. Diese Anforderung kommt einer Ober- und Untergrenze (UVRV und IVRV) der zulässigen Bitanzahl in den einzelnen Bildern gleich. Die Ober- und Untergrenze für ein bestimmtes Bild ist von der Anzahl der in allen vorhergehenden Bildern verwendeten Bits abhängig. Die Funktion des Codierers besteht darin, Bitströme zu erzeugen, die diese Forderung erfüllen. Es wird nicht erwartet, daß die Decoder tatsächlich wie beschrieben konfiguriert werden oder funktionieren. Der hypothetische Decoder und der zugehörige Puffer sind einfach ein Mittel, berechenbare Grenzen für die Größe der komprimierten Bilder zu setzen.
Eine wichtige Funktion eines MPEG-Codierers ist es, sicherzustellen, daß der erzeugte Video-Bitstrom diese Grenzen einhält. Es gibt keine weiteren Einschränkungen bezüglich der Anzahl der zum Codieren der Bilder in einer Sequenz verwendeten Bits. Dieser Spielraum kann dafür genutzt werden, die Bits so zuzuordnen, daß die visuelle Qualität der resultierenden rekonstruierten Bilder möglichst gleich (und optimal) ist. Die Lösung dieses Bitzuordnungsproblems ist ein weiteres Ziel der vorliegenden Erfindung.

DAS PROBLEM

Nach den obigen Ausführungen zum MPEG-Algorithmus ist deshalb klar, daß der Zweck des MPEG-Standards darin besteht, die Syntax des komprimierten Bitstroms und die zu seiner Decodierung verwendeten Verfahren zu definieren. Dem Entwickler des Codiereralgorithmus und der Hardware bleibt ein beträchtlicher Spielraum, die Systeme an die speziellen Anforderungen der jeweiligen Anwendung anzupassen. Es kann ein Kompromiß zwischen dem Komplexitätsgrad im Codierer und der visuellen Qualität bei einer bestimmten Bitrate gefunden werden, der für die betreffende Anwendung am günstigsten ist. Ferner ist ein breites Spektrum komprimierter Bitraten und Bildgrößen möglich. Auf diese Weise kann Anwendungen von Bildtelefonen mit geringer Bitrate bis hin zu bildschirmfüllenden Multimediapräsentationen, deren Qualität mit Aufzeichnungen auf VHS-Videokassetten vergleichbar ist, Rechnung getragen werden. Das Problem, das in der vorliegenden Erfindung angegangen wird, ist folglich die Komprimierung digitaler Videosequenzen nach dem MPEG- Standard unter Verwendung von Verfahren wie den oben beschriebenen, die eine adaptive Quantisierung und Bitratensteuerung auf eine Weise verwenden, die die visuelle Qualität der komprimierten Sequenz optimiert und gleichzeitig sicherstellt, daß der Bitstrom die MPEG-Forderung einer festen Bitrate erfüllt.

STAND DER TECHNIK

In der frei zugänglichen Literatur sind verschiedene Konzepte aufgetaucht, die auf bestimmte Aspekte des Problems der adaptiven Quantisierung und der Bitratensteuerung eingehen. So beschreiben beispielsweise W. H. CHEN und W. K PRATT in ihrem Artikel "Scene Adaptive Coder," IEEE Trans. Communications, Bd. COM-32, S. 225-232, März 1984, die Idee eines bitratengesteuerten Quantisierungsfaktors für Transformationskoeffizienten. Die hier verwendete Strategie der Bitratensteuerung wird in Algorithmen zur Bild- und Videokomprimierung häufig eingesetzt, um die bei der Codierung erzeugte variable Bitrate an einen Kanal mit fester Bitrate anzupassen. In diesem Fall wird jedes Bild der Sequenz so behandelt, als wäre es ein stehendes Bild, und es wird im wesentlichen angestrebt, für alle Bilder in der Sequenz eine konstante Bildbitzuordnung zu erreichen. Weitere Detailinformationen über solche Verfahren finden sich in dem oben erwähnten Buchkapitel von TESCHNER 1979.
In dem Artikel von CHEN und PRATT 1984 geht es um die Bildcodierung, die beschriebenen Ideen eignen sich aber auch für die Videocodierung. In diesem Ansatz gibt es aber keinen Mechanismus für die Anpassung des Quantisierungsfaktors an die Art der Bilder selber.
C. H. CHEN und D. I. LeGALL beschreiben in ihrem Artikel "A K-th Order Adaptive Transform Coding Algorithm for Image Data Compression," SPIE Bd. 1153, Applications of Digital Image Processing XII, Bd. 1153, S. 7-18, 1989, ein adaptives Schema zur Auswahl des Quantisierungsfaktors anhand des DCT-Koeffizienten mit der k-ten Größe.
H. LOHSCHELLER schlägt in "A Subjectively Adapted Image Communication System," IEEE Trans. Communications, Bd. COM-32, S. 1316-1322, Dezember 1984, ein Verfahren zur Klassifizierung von Blöcken vor. Dieses Verfahren hängt mit der adaptiven zonalen Abtastung und der adaptiven Vektorquantisierung zusammen.
K. B. NGAN, K. S. LEONG, und H. SINGH schlagen in "A HVWweighted Cosine Transform Coding Scheme with Adaptive Quantization," SPIE Bd. 1001 Visual Communications and Image Processing, Bd. 1001, S. 702-708, 1988, ein Schema zur Transformationscodierung von Bildern mit adaptiver Quantisierung vor, in dem ein Bitratensteuerpuffer und der Kontrast des CD- Terms jedes Blocks zu seinem nächsten Nachbarn in der Reihenfolge der Rasterabtastung gemeinsam zur Anpassung des Quantisierungsfaktors herangezogen werden.
H. HOELZLWIMMER beschreibt in "Rate Control in Variable Transmission Rate Image Coders," SPIE Bd. 1153 Applications of Digital Image Processing XII, Bd. 1153, S. 77-89, 1989, eine kombinierte Bitraten- und Qualitätssteuerung. Zur Steuerung des Rekonstruktionsfehlers und der Bitrate werden zwei Parameter verwendet, die Quantisierungsschrittgröße und die räumliche Auflösung. Die Steuerung erfolgt anhand der gewichteten mittleren Fehlerquadrate einer räumlichen Domäne.
In der gleichzeitig anhängige US-Patentanmeldung Nr. 705,234, angemeldet am 24. Mai 1991 durch die Erfinder des vorliegenden Patents, wird das Problem der adaptiven Quantisierung behandelt. Die beschriebenen Verfahren können als eines der Subsysteme in der vorliegenden Erfindung verwendet werden, und zwar als Bildcodierer mit adaptiv quantisierender Bitratensteuerung (AQ/RC).
In der US-Patentschrift 5 051 840 wird eine Bildsignalcodierungsvorrichtung beschrieben, die die Bilddaten in mehrere Blöcke aufteilt und die einzelnen Bilddatenblöcke einer orthogonalen Transformation, einer Normalisierung und einer Codierung unterzieht. Wie speziell in Spalte 3, Zeile 26-32 beschrieben wird, betrifft die Komprimierungscodierung STANDBILDDATEN. Wieviel Daten den einzelnen Blöcken zugeordnet werden wird auf der Grundlage der Verhältnisse der Aktivitäten der einzelnen Blöcke zu den Aktivitäten von Block zu Block bestimmt, wodurch die Ausgabe des einzelnen Blocks codierter Daten beschränkt ist. Die Datenmenge wird proportional zu den Frequenzkomponenten der einzelnen Blöcke zugeordnet. Außerdem wird die Anzahl der dem gesamten Bild zugeordneten Bits konstant gehalten.

AUFGABE DER ERFINDUNG

Anders als bei den bisher genannten, dem Stand der Technik entsprechenden Systemen und Algorithmen hat die vorliegende Erfindung die Aufgabe, ein Verfahren und ein System zum Zuordnen von Bits in komprimierten Bildern in einem MPEG II-Datenstrom zu liefern, das Videokomprimierungsalgorithmen betrifft, die einen komprimierten Datenstrom mit fester Bitrate erzeugen sollen.

Kurzbeschreibung der Erfindung

In der vorliegenden Erfindung werden ein Verfahren und ein System zur Ausführung einer Bildbitzuordnung nach Anspruch 1 bzw. 6 beschrieben.
Verfahren und System sind auf Videokomprimierungsalgorithmen anwendbar, die einen komprimierten Datenstrom mit fester Bitrate erzeugen sollen, und in denen eine Bewegungskompensation durchgeführt wird.
Das vorliegende Verfahren zum Zuordnen von Bits zu den aufeinanderfolgenden Bildern in einer Videosequenz führt zu einer für jedes Bild einzeln berechneten visuellen Qualität und erfüllt gleichzeitig die Bitraten-Vorschriften des MPEG-Videopufferprüfers (VBV).

Kurzbeschreibung der Zeichnungen

In Fig. 1 bis 4 sind Ebenen komprimierter Daten innerhalb der Videokomprimierungsebene des MPEG-Datenstroms dargestellt. Dabei zeigt Fig. 1 einen exemplarischen Satz von Bildergruppen (GOPs), Fig. 2 eine exemplarische Aufteilung eines Bildes in Makroblöcke, Fig. 3 eine exemplarische weitere Unterteilung eines Bildes in Ausschnitte, und Fig. 4 die Unterteilung eines Makroblocks in einzelne Blöcke.
In Fig. 5 ist die in MPEG verwendete zweistufige Bewegungskompensation zwischen Bildern in einem GOP dargestellt.
Fig. 6 ist ein Blockdiagramm eines MPEG-Codierers, der aus drei Komponentensubsystemen zur Implementierung der erfindungsgemäßen Verfahren besteht.
In Fig. 7 sind die Codierungsschwierigkeitsfaktoren für die gesamte Bildersequenz in einer Videosequenz dargestellt. Dabei handelt es sich um zwei im MPEG-Standard verwendete Testsequenzen, die aus den ersten 60 Bildern der Blumengartensequenz, gefolgt von den ersten 60 Bildern der Tischtennissequenz, gefolgt von 30 Wiederholungen des 61. Bildes der Tischtennissequenz (zur Simulation eines Standbildes) bestehen und in der gesamten Beschreibung zur Erläuterung der erfindungsgemäßen Verfahren verwendet werden.
In Fig. 8 sind die für jedes Bild der Sequenz aus Fig. 7 berechneten Bitzuordnungen dargestellt.
In Fig. 9 sind die Soll-Bitrate und die Ist-Bitrate für jedes Bild der Sequenz aus Fig. 7 dargestellt.
Fig. 10 ist ein Diagramm der zum Codieren der Sequenz aus Fig. 7 verwendeten Quantisierungsfaktoren (QP-Faktoren).
Fig. 11 ist ein Blockdiagramm, in dem das AQ/RC-Bildcodierungssubsystem aus Fig. 6 detaillierter dargestellt ist.
Fig. 12 zeigt typische Klassenverteilungen für I- und P- Bilder aus den Blumengarten- und Tischtennissegmenten der MPEG-Testsequenzen.
In Fig. 13 und 14 ist die Leistungsfähigkeit der erfindungsgemäßen QP-Zuordnungs- und Aktualierungsstrategien bei der Steuerung der Bitrate dargestellt. Dabei ist in Fig. 13 QPloW und der durchschnittliche QP-Wert in jeder Bilderreihe 16, 22, 61 und 67 einer Testsequenz dargestellt, und in Fig. 14 sind die erzeugten Bits sowie die Vorgabewerte jeweils für eine Zeile dargestellt.
Fig. 15 zeigt die Details des in Fig. 6 dargestellten QPadaptiven Vorprozessors.
Fig. 16 zeigt drei mögliche Filterzustände (FS) des in Fig. 15 dargestellten QP-adaptiven Vorprozessors.

AUSFÜHRLICHE BESCHREIBUNG DER BEVORZUGTEN AUSFÜHRUNGSFORMEN

Wie bereits erwähnt ist ein wichtiges Merkmal des ISO/IEC MPEG-Standards, daß nur die Syntax des komprimierten Datenstroms und das Verfahren zu seiner Decodierung detailliert spezifiziert sind. Es kann also verschiedene Codierer geben, von denen jeder einen Bitstrom erzeugt, der mit der in Standard definierten Syntax kompatibel ist. Diese Bitströme können unterschiedlich komplex sein und haben zur Folge, daß die visuelle Qualität bei einer vorgegebenen Bitrate nicht konstant ist. Der MPEG-Standard gilt hauptsächlich, aber nicht ausschließlich, Situationen, in denen die durchschnittliche Bitrate des komprimierten Datenstroms vorgegeben ist. Die MPEG- Spezifikation enthält eine präzise Definition des Begriffs "feste Bitrate". Obwohl die durchschnittliche Rate konstant sein muß, kann die Anzahl der Bits, die den Bildern in einer MPEG-Videosequenz zugeordnet sind, aber durchaus von Bild zu Bild verschieden sein. Auch die Bitzuordnung innerhalb eines Bildes muß nicht gleichmäßig sein. Die Herausforderung bei der Entwicklung eines Codierers, der qualitativ hochwertige Sequenzen bei niedrigen Bitraten liefert, besteht zum Teil darin, ein Verfahren zu entwickeln, das die insgesamt zur Verfügung stehenden Bits zwischen den Bildern und innerhalb der Bilder verteilt.
Noch ein weiteres wichtiges Codierungsmerkmal des MPEG-Standards, die adaptive Quantisierung (AQ) darf nicht vergessen werden. Dieses Verfahren ermöglicht es, verschiedene Bereiche jedes zu codierenden Bildes unterschiedlich originalgetreu zu codieren. Damit kann bei der Komprimierung von Bildern und Videosequenzen versucht werden, die visuelle Qualität der einzelnen Ausschnitte innerhalb eines Bildes und die Qualität von Bild zu Bild anzugleichen (und zu optimieren). Obwohl der MPEG-Standard eine adaptive Quantisierung erlaubt, werden darin keine Algorithmen beschrieben, die aus Regeln für die Verwendung der AQ zur Verbesserung der visuellen Qualität bestehen.
Eine weitere Klasse von Verfahren, die in einem MPEG- oder anderen Codierer verwendet werden kann, ist die sog. Vorverarbeitung. Jede Art der Vorverarbeitung einer digitalen Videosequenz, bei der die fundamentalen räumlichen Beziehungen der Abtastpunkte zueinander nicht verändert werden, kann in einen MPEG-kompatiblen Codierer integriert werden, um die visuelle Qualität der komprimierten Sequenz zu verbessern. Beispiele hierfür sind die lineare oder nichtlineare Vorfilterung.
In Fig. 6 ist ein Blockdiagramm eines MPEG-Codierers abgebildet, der aus drei Komponentensubsystemen zur Implementierung der erwähnten erfindungsgemäßen Verfahren besteht. Wie in dem Diagramm zu sehen ist, kommen Bilddaten Pk, die für das k-te Bild in einer Sequenz repräsentativ sind, in einem Subsystem, dem QP-adaptiven Vorprozessor 3, an, wo gegebenenfalls eine Vorverarbeitung stattfindet. Die Art der Vorverarbeitung wird durch die Quantisierungsebenen (QPprev) zuvor codierter Bilder, die zuvor bei der Codierung der Datensequenz aus dem bitratengesteuerten Bildcodierer 1 mit adaptiver Quantisierung (AQ/RC) übertragen wurden, gesteuert. Die vom Subsystem 3 ausgegebenen, eventuell vorverarbeiteten Bilddaten Fk kommen in das nächste Subsystem, AQ/RC Bildcodierer 1, wo eine Bewegungsabschätzung und eine MB-Einteilung stattfindet. Einige Resultate dieser Operationen im AQ/RC Bildcodierer 1 (Dk) werden an das verbleibende Subsystem, das Bildbitzuordnungs-Subsystem 2, weitergeleitet, und ein Sollwert für die Anzahl der Bits für die Bilddaten Fk wird an den AQ/RC Bildcodierer 1 zurückgesendet (Ak, Sk, und Ck). Dann wird die Codierung fortgesetzt wie weiter unten beschrieben. Schließlich werden die komprimierten Daten für die Bilddaten Fk, CDk aus dem AQ/RC Bildcodierer 1 ausgegeben. Zusätzlich werden Daten über die Anzahl der zum Codieren benötigten Bits Fk (Bk) und den Rekonstruktionsfehler (Ek) an das Bildbitzuordnungs-Subsystem 2 übermittelt, und die vorherige Quantisierungsebene QPprev, die ein Durchschnittswert QPavg sein kann, wird an das QP-adaptive Vorprozessor-Subsystem 3 weitergeleitet, wo sie für die Verarbeitung zukünftiger Bilder verwendet werden kann.
Zum Zweck der Funktionsbeschreibung der drei Subsysteme wird zuerst die Funktionsweise des Bild-zu-Bild-Bitzuordnungs-Sub systems 2 beschrieben, dann die des AQ/RC-Bildcodierer-Subsystems 1 und zuletzt die des QP-adaptiven Vorprozessorsystems 3. Zum besseren Verständnis der Beziehung zwischen der Erfindung und dem MPEG-Videokomprimierungsalgorithmus sei auf die oben erwähnte Veröffentlichungen MPEG CD-11172 und ISO-IEC JTC1/SC2/WG11 MPEG 91/74, MPEG Video Report Draft, 1991, oder auf D. LeGALL, "MPEG: A Video Compression Standard for Multimedia Applications", Communications of the ACM, Bd. 34, April 1991, verwiesen.

Bitzuordnung von Bild zu Bild

In Videokomprimierungsalgorithmen wird die Bewegungskompensation dazu benutzt, die zur Darstellung der einzelnen Bilder in einer Videosequenz benötigte Datenmenge zu reduzieren. Algorithmen mit fester Bitrate müssen zwar insgesamt eine durchschnittliche Bitrate einhalten, die in etwa einem Vorgabewert entspricht, oft bleibt aber noch etwas Spielraum bei der Anzahl der Bits für das einzelne Bild. Wenn jedem Bild exakt die gleiche Anzahl von Bits zugeordnet wird, entsteht eine komprimierte Sequenz, deren Qualität zeitlichen Schwankungen unterworfen ist. Dies wird vom Betrachter aber als störend empfunden. Das Bildbitzuordnungs-Subsystem 2 besitzt Prozeduren zum Zuordnen von Bits zu den komprimierten Bildern in einer Videosequenz. Es eignet sich vor allem für Videokomprimierungsalgorithmen, die einen Datenstrom mit fester Bitrate erzeugen sollen, und in denen eine Bewegungskompensation stattfindet, z. B. im ISO/IEC MPEG-Videokomprimierungsstandard.
Im Idealfall ordnet ein Bildzuordnungssystem jedem Bild eine bestimmte Anzahl von Bits so zu, daß die empfundene visuelle Qualität der codierten Sequenz von Bild zu Bild gleich bleibt und einem bei der vorgegebenen Bitrate möglichen Optimum entspricht, wobei die durch die Regeln für feste Bitraten auferlegten Beschränkungen beachtet werden müssen. Im allgemeinen müßte ein solches System den Inhalt der gesamten Sequenz kennen, bevor das erste Bild oder Halbbild codiert wird. Außerdem müßte die visuelle Qualität, die die rekonstruierten Bilder bei der Codierung mit einer festen Bitzuordnung haben würde, im voraus bekannt sein. Die erste Forderung ist wegen der möglicherweise großen Speicheranforderung und Verzögerung praktisch nicht zu erfüllen. Die zweite ist derzeit sehr schwierig, da noch kein einfach zu handhabendes mathematisches Modell für die empfundene visuelle Qualität der codierten visuellen Daten bekannt ist, selbst wenn die codierten und die Originalbilder bekannt sind.
Das erfindungsgemäße Bitzuordnungssubsystem bietet eine praktische Lösung für dieses Problem, indem ein Maß für die Schwierigkeit der Codierung von Bildern jedes Typs in unmittelbarer Vergangenheit aufgezeichnet wird. Dieses Maß, die Codierungsschwierigkeit, hängt von der räumlichen Komplexität eines Bildes und von dem Ausmaß, in dem die Bewegungskompensation den Inhalt eines Bildes vorhersagen kann, ab. Die Bits werden den drei Bildtypen in Abhängigkeit von der relativen Codierungsschwierigkeit der drei Typen zugeordnet. Außerdem sind die drei Zuordnungen, die bei jedem Bild berechnet werden (für jeden Bildtyp eine Zuordnung) so, daß bei einer Codierung einer gesamten Bildergruppe (GOP) mit diesen Zuordnungen die Anzahl der benötigten Bits der vorgegebenen Bitrate entspricht.
In Fig. 6 bestimmt das Bildzuordnungssubsystem 2, wieviele Bits dem Bild k zugeordnet werden, nachdem die Daten Fk für das Bild im AQ/RC-Bildcodierer 1 analysiert worden sind und der Codierungsschwierigkeitsfaktor des Bildes vom AQ/RC-Bildcodierer 1 an das Bildbitzuordnungssubsystem 2 übermittelt worden ist, aber bevor das Bild codiert wird. Das Bildbitzuordnungssubsystem 2 verwendet auch Informationen über die zuvor codierten Bilder, von denen angenommen wird, daß der AQ/RC-Bildcodierer 1 sie bereits an das Bildbitzuordnungssubsystem 2 weitergeleitet hat. Diese Information besteht aus Bk, der Anzahl der zum Codieren des vorhergehenden Bildes jedes Typs verwendeten Bits (aufgesplittet in Transformationskoeffizientenbits und Nebeninformationsbits), und Ek, dem Rekonstruktionsfehler der zwei vorausgehenden Ankerbilder. Bei der Abschätzung der Bitanzahl, die einem bestimmten Bild zugeordnet werden soll, muß zuerst eine feste Anzahl aufeinanderfolgender Bilder in der unmittelbaren Zukunft, d. h. eine aus einer festen Anzahl von I-Bildern (nI), P-Bildern (nP) und B-Bildern (nB) bestehende Gruppe von Bildern in der Sequenz, die noch nicht codiert werden müssen, ausgewählt und betrachtet werden. Sinnvollerweise sollte die Anzahl und Zusammensetzung der Bilder in der in diesem Schritt zur Betrachtung ausgewählten Gruppe mit der identisch sein, welche für die für jedes Bild in der Sequenz ausgeführte Bildbitzuordnungsprozedur benutzt wird; dies ist aber nicht zwingend notwendig. Notwendig ist allerdings, daß der Durchschnittswert der resultierenden Bitzuordnungen über die Zeit mit dem Sollwert für die durchschnittliche Bildbitzuordnung übereinstimmt.
Die hier beschriebene Zuordnungsoperation beginnt mit der Betrachtung einer Zuordnung für die ausgewählte Bildergruppe, auch wenn das Endergebnis aus drei Bildbitzuordnungen, nämlich einer für jeden Bildtyp, besteht, und nur die Bildbitzuordnung für den Bildtyp, der dem zu codierenden Bildtyp entspricht, verwendet wird. Der Prozeß beginnt also mit der Berechnung einer Gesamtbitzuordnung Bset für die Gruppe von Bildern, die der durchschnittlichen Bitzuordnung, die mit der vorgegebenen Bitrate konsistent ist, entspricht. Die Formel für die Berechnung lautet
Bset = (nI + nP + nB) · Bavg,
wobei Bavg die mit der vorgegebenen Bitrate konsistente durchschnittliche Bildbitzuordnung ist. In der bevorzugten Ausführungsform, die in diesem Abschnitt der Beschreibung als Beispiel angeführt wird, können die Bits, die den Bildergruppen zugeordnet werden, und diejenigen, die den einzelnen Bildern zugeordnet werden, in zwei Klassen unterteilt werden: Nebeninformationsbits (S) und Koeffizientenbits (C). Hier wird S für alle codierten Daten genommen, die keine codierten Transformationskoeffizientendaten sind. Durch Subtraktion eines Schätzwertes der zur Codierung der Nebeninformationen in der Bildergruppe benötigten Bits (Sset) von der Gesamtbitzuordnung Bset erhält man eine Transformationskoeffizientenbitzuordnung für die Bildergruppe, Cset. Die für die Codierung der Transformationskoeffizienten des Bildes zugeordnete Anzahl der Bits ist dann ein Bruchteil von Cset, dessen Größe vom Schätzwert für die Codierungsschwierigkeit des Bildes abhängt. Ein exemplarisches Verfahren zur Berechnung der Zuordnung anhand der Codierungsschwierigkeit wird im folgenden ausführlich beschrieben.

Transformationskoeffizienten- und Nebeninformationszuordnung

Die zugeordneten Nebeninformationsbits enthalten die Kopfdaten des Bildes und alle Nebeninformationen, z. B. die Angabe des Bewegungskompensationsmodus, Bewegungsvektoren und Daten über die adaptive Quantisierung. Koeffizientendaten sind nur in den Bits enthalten, die zur Codierung der Transformationskoeffizienten der Pixeldaten selber (bei I-Bildern) oder der Pixeldifferenzdaten (bei P- und B-Bildern) verwendet werden. Wenn Ar, AP und AB die Bitzuordnungen für I-, P- und B-Bilder sind, ist AI = SI + CI, AP = SP + CP, und AB = SB + CB (wobei S und C die Nebeninformations- bzw. Koeffizientenbits sind). In der bevorzugten Ausführungsform wird die Nebeninformationsbitzuordnung für das nächste zu codierende Bild mit der tatsächlich zur Codierung der Nebeninformation im vorausgehenden Bild des gleichen Typs in der Sequenz gleichgesetzt. Alternativ kann die Nebeninformationsbitzuordnung auch anhand des Durchschnittswertes aller vorausgegangenen Bilder des gleichen Typs in der Sequenz berechnet werden. Ferner besteht bei diesem Verfahren die Möglichkeit, die Nebeninformationszuordnungen zu ignorieren und die Bildbitzuordnungen ausschließlich anhand der Transformationskoeffizientenbitzuordnung zu berechnen. Dieser letztere Ansatz kann, im Kontext der folgenden Erläuterung, realisiert werden, indem angenommen wird, daß alle Variablen der Nebeninformationszuordung, Sx, gleich null sind.
Ein Mittel zur Berechung des Schwierigkeitsfaktors für ein Bild wird im folgenden beschrieben. Zuvor sei aber zum Zweck der Beschreibung darauf hingewiesen, daß der Codierungsschwierigkeitsfaktor für das vorhergehende Bild jedes Typs nach seiner Berechnung im Bildbitzuordnungssubsystem 2 gespei chert und das folgende Verfahren zur Berechnung der Transformationskoeffizientenzuordnung für das aktuelle Bild verwendet wird. Zuerst wird die Nebeninformationszuordnung für die Bildergruppe nach der Formel (Sset = nISI + nPSP + nBSB) abgeschätzt. Dieser Wert wird von der Gesamtanzahl der für die Gruppe zugeordneten Bits, Bset, subtrahiert. Dies ergibt die Transformationskoeffizientenzuordnung für die Bildergruppe, nämlich
Cset = Bset - Sset
Dann werden CI, CP und CB als einzige Lösung der folgenden Gleichungen ermittelt:
Cset = nICI + nPCP + nBCB,
Die ursprüngliche Gleichung (für Cset) in dieser Gruppe sorgt dafür, daß der Gesamtdurchschnitt für die Gruppe stimmt. Er ist der Durchschnitt der mittleren absoluten Fehler der vorausgehenden und nachfolgenden rekonstruierten Ankerbilder, und die Gewichtungsterme WP und WB haben die Aufgabe, die P- und B- Bildzuordnungen gegenüber den anderen stärker zu gewichten. Abgesehen von diesen Gewichtungen ordnen die letzteren beiden Gleichungen (für CP und CB) der Gruppe den P- und B-Bildern Bits proportional zu dem Ausmaß zu, in dem ihre Schwierigkeit den mittleren absoluten Fehler im (rekonstruierten) Vorhersagebild bzw. den Vorhersagebildern überschreitet.
Das obige Verfahren ist nützlich, da es die räumliche Komplexität der Sequenz durch die drei Codierungsschwierigkeitsfaktoren DI, DP und DB, den Erfolg der Bewegungskompensation durch DP und DB, die vorgebene Bitrate durch die Forderung der ersten Gleichung für Cset und die Qualität der zuletzt codierten Bilder durch Er und E'r berücksichtigt.
Gelegentlich führt die obige Bitzuordnungsstrategie zu einer Zuordnung, bei der UVBV überschritten oder LVBV unterschritten wird. Die Häufigkeit, mit der dies vorkommt, hängt von der Größe des VBV-Puffers und der Art der Sequenz ab. Ein typisches Szenario liegt vor, wenn der VBV-Puffer relativ klein ist (z. B. sechs Durchschnittsbilder oder weniger), und die Bewegungskompensation sehr erfolgreich ist. In einer solchen Situation versucht die Zuordnungsstrategie, praktisch alle Transformationsbits für eine Gruppe den I-Bildern zu geben, was dazu führt, daß die Zuordnung für ein einzelnes Bild größer ist als die VBV-Puffergröße. In der bevorzugten Ausführungsform werden die I-Bilder in diesem Fall so beschnitten, daß sie gerade noch innerhalb des betreffenden VBV-Grenzwertes liegen, und die vom I-Bild weggenommenen Bits werden dem B- Bild zugeordnet. Dieser letztere Schritt ist wichtig, da die durchschnittliche Bitrate absinkt, wenn keine explizite Neuzuordnung vorgenommen wird. Dies führt schließlich zu VBV-Überlaufproblemen, in der Regel, wenn LVBV beginnt, die B-Bildzuordnungen zu überschreiten. Das Nettoergebnis davon ist eine implizite Neuzuordnung zu B-Bildern, was in der Regel eine insgesamt schlechtere Bildqualität zur Folge hat. Ein zusätzlicher Vorteil der expliziten P-Bild-Neuzuordnung ist die schnellere Konvergenz zu einer extrem hohen Bildqualität bei Standbildern. Falls eine P- oder B-Bildzuordnung die VBV- Grenzwerte über- bzw. unterschreitet, erfolgt keine Neuzuordnung der Bits.
Die Zuordnungsstrategie kann auch angewendet werden, wenn keine B-Bilder vorhanden sind. In diesem Fall wird einfach nB = 0 gesetzt und die Gleichung, die bei der Berechnung der Zuordnungen CB setzt, ignoriert wird. Entsprechend kann sie auch verwendet werden, wenn keine P-Bilder vorhanden sind. Außerdem kann die Unterscheidung zwischen Koeffizienten- und Nebeninformation ignoriert werden, indem der Schätzwert für die Codierungsschwierigkeit zum Zuordnen aller Bits eines Bildes verwendet wird. In einem solchen Fall könnte der Schätzwert für die Codierungsschwierigkeit direkt in die Schwierigkeit der Codierung von Nebeninformationen übernommen oder die Nebeninformation ganz ignoriert werden.
Zwei der in den MPEG-Standards verwendeten Testsequenzen, die Blumengartensequenz und die Tischtennissequenz, wurden benutzt, um die Effektivität der erfindungsgemäßen Verfahren zu testen. Im speziellen Fall wurde in der vorliegenden Beschreibung zur Illustration der Verfahren eine Videosequenz verwendet, die aus den ersten 60 Halbbildern der Blumengartensequenz, gefolgt von den ersten 60 Halbbildern der Tischtennissequenz, gefolgt von 30 Wiederholungen des 61. Halbbildes der Tischtennissequenz (um ein Standbild zu simulieren), besteht. Bei diesen Sequenzen handelt es sich um YUV-Testsequenzen mit 352 · 240 Pixeln. Die Codierung erfolgte mit 1,15 Mbit/s bei einem Abstand zwischen den I-Bildern von N = 15 und einem Abstand zwischen den Ankerbildern von M = 3. In Fig. 7 sind die Codierungsschwierigkeitsfaktoren für die gesamte Sequenz dargestellt, und in Fig. 8 die für die einzelnen Bilder berechneten Bitzuordnungen.
An dieser Stelle sei darauf hingewiesen, daß die drei Bitzuordnungen für jedes Bild in der Sequenz genau diejenigen vor der Codierung des betreffenden Bildes sind, daß aber nur eine dieser Zuordnungen tatsächlich benutzt wird. Die aus dem Zuordnungsverfahren resultierende vorgegebene Bitrate ist zusammen mit den tatsächlichen Bitraten für die Sequenz in Fig. 9 dargestellt.
Die Stabilität beim, Szenenwechsel (Halbbild 61) und die Konvergenz der tatsächlichen Bitrate für P- und B-Bilder zu praktisch null ist im Standbildsegment (Halbbilder 121-151) zu erkennen. Die zum Codieren der Sequenz verwendeten Quantisierungsfaktoren (QP) sind in Fig. 10 zu sehen. I- und P-Bilder werden in der Regel mit einer feineren Schrittgröße codiert als B-Bilder.

AQ/RC-Bildcodierer

Das AQ/RC-Bildcodierersubsystem 1 beinhaltet Prozeduren für die adaptive Quantisierung (AQ) der aufeinanderfolgenden Bilder einer Videosequenz, um eine bessere visuelle Qualität zu erzielen und gleichzeitig sicherzustellen, daß die zum Codieren der einzelnen Bilder verwendeten Bitanzahl einem vorgegebenen Sollwert möglichst nahe kommt. Es werden Prozeduren für I-Bilder, P-Bilder und B-Bilder ausgeführt. In diesen Prozedu ren werden die Bereiche, aus denen ein Bild besteht, mit Hilfe einer Bereichsklassifizierungsstrategie behandelt, die mit folgenden Komponenten zusammenarbeitet:
Bewegungsabschätzung;
einem adaptiven Modell der zum Codieren einer Bildregion benötigten Bitanzahl in Abhängigkeit vom Quantisierungsfaktor QP und gemessenen Merkmalen des Bereichs; und ein Schema für die Anpassung der Quantisierungsebene bei der Codierung eines Bildes, um sicherzustellen, daß die Gesamtanzahl erzeugter Bits dem vorgegebenen Sollwert nahe kommt.
Zum Zweck der Beschreibung werden hier die Bildbereiche als MPEG-Makroblöcke (MB) behandelt; das beschriebene Verfahren kann aber selbstverständlich auch auf Bereiche unterschiedlicher Größe und Form angewendet werden.
In Fig. 11 sind die Komponenten des AQ/RC-Bildcodierers 1 allgemein dargestellt. Die Funktionsweise dieses Subsystems häng von der Art des zu codierenden Bildes ab. Wie in der Zeichnung zu sehen ist, kommt ein Videobildsignal Fk für ein Bild k, das im QP-adaptiven Vorprozessor 3 vorverarbeitet worden sein kann, in einer Bewegungsabschätzuncrs- und MB-Klassifizierungseinheit 14 an. Hier wird das Signal analysiert und jeder MB nach den im folgenden beschriebenen Verfahren klassifiziert. Wenn es sich um ein P-Bild oder ein B-Bild handelt, wird auch eine Bewegungsabschätzung vorgenommen. Die Ergebnisse dieser Operationen werden in Form eines Codierungsschwierigkeitsfaktors Dk an das Bildbitzuordnungssubsystem 2 weitergeleitet, wo sie wie oben beschrieben verwendet werden. Das Bildbitzuordnungssubsystem 2 sendet dann ein Bitzuordnungssignal Ck für Bild k zurück. Dieses Bitzuordnungssignal wird von einer QP-Ebenen-Festlegungseinheit 15 zusammen mit Infor mationen von der Bewegungsabschätzungs- und MB-Klassifizierungseinheit 14 dazu verwendet, Anfangswerte für den Quantisierungsfaktor QP zu bestimmen, die dann bei der Codierung von Makroblöcken verwendet werden. Außerdem berechnet die QP- Ebenen-Festlegungseinheit 15 einen Schätzwert für die Anzahl der Bits, die zum Codieren jeder MB-Zeile im Bild benötigt wird. Diese Quantisierungsfaktoren und Zeilensollwerte werden an den ratengesteuerten Bildcodierer 1 weitergeleitet, der mit der Codierung des Bildes fortfährt und dabei auch Informationen verwendet, die ihm von der Bewegungsabschätzungs- und MB- Klassifierungseinheit 14 übergeben worden sind. Da die Funktion des AQ/RC-Bildcodierers 1 unter drei Untereinheiten aufgeteilt ist, ist auch die nachstehende Beschreibung so aufgeteilt, wobei vor allem auf Fig. 11 Bezug genommen wird.

Bewegungsabschätzungs- und MB-Klassifierungseinheit

Eine Hauptaufgabe der Bewegungsabschätzungs- und MB-Klassifizierungseinheit 14 besteht darin, zu bestimmen, welcher Codierungsmodus m(r, c) zum Codieren der einzelnen MBs in einem Bild verwendet wird. Diese Funktion wird nur bei bewegungskompensierten Bildern verwendet, da es für MBs in I-Bildern (Intramodus) nur einen einzigen Modus gibt. Die Entscheidung für einen Codierungsmodus basiert auf einem Bewegungsabschätzungsprozeß, der auch Bewegungsvektoren und bewegungskompensierte Differenz-MBs erzeugt. Eine weitere wichtige Funktion der Bewegungsabschätzungs- und MB-Klassifizierungseinheit 14 ist die Klassifizierung der einzelnen MBs. Die Klasse cl(r, c) von MB (r, c) bestimmt letztlich den Wert des Quantisierungsfaktors QP(r, c), der zum Codieren dieses Makroblocks verwendet wird. Die Modi und Klassen werden bestimmt, indem jedes Bild analy siert wird und die Bewegung zwischen dem zu codierenden Bild und dem Vorhersagebild bzw. den Vorhersagebildern abgeschätzt wird. Die gleichen Informationen werden auch zur Berechnung des Schwierigkeitsfaktors Dk verwendet, der an das Bildbit- Zuordnungssubsystem 2 übergeben wird.
Das Ziel der Bewegungsabschätzung im MPEG-Videocodierungsalgorithmus ist ein Bewegungsvektor mv (r, c) = (rav, cav) und der zugehörige bewegungskompensierte Differenz-MB Mk(r, c). Der bewegungskompensierte Differenz-MB ist die pixelweise Differenz zwischen dem gerade betrachteten MB und dem Vorhersage-MB. Das exakte Verfahren zur Bildung des Vorhersage-MB hängt vom verwendeten Bewegungskompensationsmodus ab und wird in der oben genannten Veröffentlichung ISO-IEC JTC1/SC2/WG11 MPEG CD- 11172, MPEG Committee Draft, 1991, detailliert beschrieben. Der Bewegungsvektor sollte irgendwie die tatsächliche Bewegung des betreffenden Bildteils angeben. Details über Verfahren zur Bewegungsabschätzung finden sich in A. N. NETRAVALI and B. G. HASKELL, Digital Pictures: Representation and Compression, New York, NY: Plenum Press, 1988.
Zum Zweck der vorliegenden Beschreibung wird angenommen, daß ein Vollsuche-Bewegungsabschätzungsalgorithmus verwendet wurde, der einen Bereich von ± 7 · n Pixeln in horizontaler und vertikaler Richtung abdeckt, wobei n der Abstand in Bildintervallen zwischen dem gerade analysierten Bild und dem Vorhersagebild ist, und wobei die Bewegungsvektoren auf ein halbes Pixel genau sind. Die vorliegende Erfindung umfaßt Verfahren zur Verwendung der Ergebnisse der Bewegungskompensation bei der Codierung von Videosequenzen, ist aber nicht auf irgendein bestimmtes Bewegungsabschätzungsverfahren festgelegt, vorausge setzt, es gibt ein Maß für den Erfolg der Bewegungskompensation (Bewegungskompensationsfehler), das angibt, wie gut die Übereinstimmung zwischen dem kompensierten MB und dem Vorhersagebereich, auf den der Bewegungsvektor weist, ist. Es sei daran erinnert, daß es bei P-Bildern nur eine Art der Bewegungskompensation gibt (die Vorwärtskompensation), und bei B- Bildern drei Arten (die Vorwärtskompensation, die Rückwärtskompensation und die interpolative Kompensation). Der Vorwärtsbewegungsvektor für MB (r, c) kann mit mvf(r, c) und der Rückwärtsbewegungsvektor mit mvb(r, c) bezeichnet werden. Der interpolative Modus verwendet sowohl Vorwärts- als auch Rückwärtsvektoren. Die Vorwärts-, Rückwärts- und interpolativen Bewegungskompensationsfehler können mit Δmc,f(r, c), Δmc,b(r, c) und Δmc,i(r, c) bezeichnet werden.
Zusätzlich zum Bewegungskompensationsfehler bzw. den Bewegungskompensationsfehlern ist ein Maß für die räumliche Komplexität jedes MB erforderlich. Dieses Maß wird hier mit Δ(r, c) bezeichnet. Es ist wichtig, daß Δ(r, c), Δmc,f(r, c), Δmc,b(r, c) und Δmc,i(r, c) gleichartige Maße sind, in dem Sinne, daß ein numerischer Vergleich sinnvoll ist. In der bevorzugten Ausführungsform sind diese Maße alle als mittlere absolute Größen bezeichnet (siehe unten). Die Bezeichnung jedes MB mit seinen Zeilen- und Spaltenkoordinaten (r, c) gibt die Luminanzwerte der vier 8 · 8 Blöcke in MB (r, c) durch yk(i, j), i = 0, ..., 7, k = 0, ..., 3 an, und den Durchschnittswert jedes 8 · 8 Blocks mit dck. Dann wird das Maß für die räumliche Komplexität für MB (r, c) als mittlere absolute Abweichung von DC genommen, nach der Formel
wobei
Der entsprechende Bewegungskompensationsfehler ist der mittlere absolute Fehler. Wenn man die vier 8 · 8 Blöcke im Vorhersage-MB mit pk(i, j), i = 0, ..., 7, j = 0, ..., 7, k = 0, ..., 3 bezeichnet, ist dies definiert durch die Formel
In der bevorzugten Ausführungsform der Erfindung basieren die an das Bildbit-Zuordnungssubsystem 2 übergebenen Codierungsschwierigkeitsfaktoren vollständig auf den obigen Maßen für die räumliche Komplexität und den Bewegungskompensationsfehler. Bei I-Bildern beträgt der Gesamtschwierigkeitsfaktor
Bei P- und B-Bildern wird zuerst entschieden, welcher Codierungsmodus zu verwenden ist, und das diesem Modus zugeordnete Maß wird in einer Aufsummierung wie der obigen verwendet. Folgende Modi sind möglich:
Intramode: m(r, c) = I,
Vorwärts-MC: m (r, c) = mcf,
Rückwärts-MC: m (r, c) = mcb,
Interpolativer MC: m (r, c) = mci,
Die Schwierigkeitsfaktoren werden nach folgenden Formeln berechnet:
und
Für die Entscheidung, welcher Modus zu verwenden ist, können viele mögliche Regeln verwendet werden. In der bevorzugten Ausführungsform wird für P-Bilder folgende Regel verwendet:
m(r, c) = {I Δ(r, c) < βΔmcf(r, c), {mcf Δ(r, c) ≥ βΔmcf(r, c),
Es wird ein Wert von β = 1.0 verwendet. In der bevorzugten Ausführungsform gilt für B-Bilder folgende Modusauswahlregel: zum Codieren des MB wird der Modus mit dem niedrigsten Δ(r, c) verwendet. An dieser Stelle sei darauf hingewiesen, daß zwar in der bevorzugten Ausführungsform mittlere absolute Größen als Maß für die Codierungsschwierigkeit verwendet werden, daß aber auch andere miteinander vergleichbare Maße (z. B. mittlere Quadrate) verwendet werden könnten.
Es ist beabsichtigt, daß die zur Bestimmung der MB-Modi und zur Berechnung der Codierungsschwierigkeiten verwendeten Maße Nebenprodukte der Bewegungsabschätzungsprozedur sein könnten. Dies ist zum Teil deswegen möglich, weil die oben beschriebenen Maße oft in Bewegungsabschätzungsverfahren verwendet werden, um den besten Bewegungsvektor zu finden.
Diese Maße werden auch zur Klassifizierung von Makroblöcken verwendet. In der bevorzugten Ausführungsform werden die MBs wie folgt klassifiziert. Die Klasse aller Intramodus-MBs wird berechnet, indem der Mindestwert von Δk(r, c) für den betreffenden MB quantisiert wird. Wenn ein Schwellenwert t definiert wird, gilt für die Klasse cl(r, c) von MB (r, c) die Formel
Nachdem für bewegungskompensierte MBs ein Bewegungskompensationsmodus ausgewählt worden ist, werden sie nach folgender Formel klassifiziert:
In der bevorzugten Ausführungsform wird der Wert t = 2 verwendet. Man beachte, daß zur Klassifizierung bewegungskompensierter MBs sowohl Intramodus- als auch bewegungskompensierte Maße benutzt werden. Die Modus- und Klasseninformation wird zusammen mit den zugrunde liegenden Maßen von der QP-Ebenen-Festlegungseinheit 15 zum Festlegen einer anfänglichen Quantisie rungsebene und vom RC-Bildcodierer 16 bei der Codierung verwendet.
Typische Klassenverteilungen für I- und P-Bilder aus dem Blumengarten- und dem Tischtennissegment der Sequenz sind in Fig. 12 dargestellt.
Um die Komplexität der Berechnungen gering zu halten, werden in der bevorzugten Ausführungsform die MBs von B-Bildern nicht klassifiziert und die Q-Ebenen-Festlegungseinheit 15 nicht benutzt, und das im RC-Bildercodierer 16 verwendete Codierungsschema ist einfacher als das für I- und P-Bilder verwendete.

QP-Ebenen-Festlegungseinheit

Die Funktion der QP-Ebenen-Festlegungseinheit 15 besteht darin, für jede Klasse einen Anfangswert für die Quantisierungsschrittgröße zu berechnen. Allen MBs in einer bestimmten Klasse wird die gleiche Quantisierungsschrittgröße zugeordnet. In der bevorzugten Ausführungsform wird die Quantisierungsschrittgröße für jede Klasse bezogen auf eine allgemeine Mindestschrittgröße nach folgender Formel zugeordnet:
QP(r, c) = QPlow + ΔQP · cl(r, c).
In der bevorzugten Ausführungsform werden für ΔQP Werte von 5 und 6 verwendet. Der zulässige Bereich für QPlow ist in der bevorzugten Ausführungsform -31, ..., 31, obwohl MPEG nur für QP(r, c) nur ganzzahlige Werte aus dem Bereich 1, ..., 31 vorsieht. Wenn die obige Formel einen Wert über 31 erzeugt, wird dieser auf 31 gekappt, und Werte unter 1 werden auf 1 gesetzt. Es ist vorteilhaft, für QPlow Werte unter 1 zuzulassen, um sicherzustellen, daß die feinsten Quantisierungsschrittgrößen für MBs aller Klassen verwendet werden können, sofern die Bitrate dies gewährleistet. Der Prozeß zur Auswahl des Anfangswertes QP von QPlow wird weiter unten erläutert.
Das zugrunde liegende Modell der menschlichen Wahrnehmung von Codierungsfehlern, das in der bevorzugten Ausführungsform verwendet wird und sich in dem Verfahren zur Berechnung der Klasse cl(r, c) jedes MB und zur Berechnung von QP(r, c) aus cl(r, c) niederschlägt, besagt, daß Fehler gleicher Größenordnung in weniger aktiven Bereichen eines Bildes besser wahrgenommen werden. Dieses Modell ist natürlich stark vereinfacht, stellt aber einen vernünftigen Kompromiß zwischen der visuellen Qualität und dem Rechenaufwand dar. Der Grund dafür, daß für die Klassifizierung nicht das Δ des gesamten Blocks, sondern das minimale Δk über die vier Luminanzblöcke im MB verwendet wird, ist, daß MBs mit stetigen Bereichen eine geringere Quantisierungsschrittgröße zugeordnet werden sollte.
Die MB-Modi m(r, c) und -klassen cl(r, c) werden zusammen mit den Werten von Δ(r, c) und Δmc(r, c) und der Soll-Bitrate für die Bildtransformationskoeffizienten benutzt, um den anfänglichen unteren Quantisierungswert QPlow zu setzen. In der Erfindung wurde ein Modell entwickelt, das die Anzahl der zum Codieren der Transformationskoeffizienten eines MB benötigten Bits anhand des zu verwendeten Quantisierungswertes und des Δ (bei Intramodus-MBs) oder des Δmc (bei bewegungskompensierten Bildern) vorhersagt. Versuchsdaten führen zu einem Modell der Form
BI (QP, r, c) = a&sub1;Δ(r, c)QPbI
für Intramodus-MBs und
Bmc(QP, r, c) = aPΔmc(r, c)QPbP
für bewegungskompensierte MBs. Die Exponenten sind br = -0.75 und bP = -1,50. Diese Werte sind aber in hohem Maße von den verwendeten Gewichtungsfaktoren Wprev für die Quantisierung abhängig und sollten für diese optimiert werden.
Um geeignete Werte für die Parameter a und b abzuschätzen, wurde der folgende experimentelle Ansatz verfolgt. Angenommen, aI und bI soll für I-Bilder abgeschätzt werden. Da die Parameter des Modells zum Verfolgen der Änderungen von einem Bild zum nächsten angepaßt werden müssen, kommt es vor allem darauf an, daß das Modell für ein einzelnes Bild akkurat ist, und nicht so sehr für eine Gruppe von Bildern. Deshalb wird ein repräsentatives Bild mehrmals codiert, wobei in jedem Durchgang ein anderer Wert für die QP-Quantisierungsschrittgröße verwendet wird. Es wird gemessen, wieviele Bits bei jedem QP- Wert zum Codieren jedes MB benötigt werden. Dann wird für jeden QP-Wert der Durchschnittswert der Anzahl der zum Codieren aller MBs mit einem bestimmten Wert Δ benötigten Bits berechnet. Das Ergebnis ist ein zweidimensionaler Datensatz, der die durchschnittliche Anzahl der zum Codieren von MB benötigten Bits in Abhängigkeit vom Δ-Wert des MB und der zu seiner Codierung verwendeten QP-Schrittgröße angibt. Diese Durchschnittswerte können mit B' = B(QPi, Δj) bezeichnet werden. Es ist wünschenswert, diese Meßwerte in eine Gleichung der folgenden Form zu bringen:
B' = aI · Δj · (QPi)bI.
Dies ist eine überbestimmte Gruppe nichtlinearer Gleichungen in aI and bI und kann mit Hilfe nichtlinearer Verfahren der kleinsten Quadrate gelöst werden. Um die Aufgabe zu linearisieren, werden von beiden Seiten der Gleichung die Logarithmen genommen. Dadurch ergibt sich eine leicht lösbare, lineare Kleinste-Quadrate-Aufgabe in log(aI) und bI.
Die linearen Parameter sollten nach der Codierung jedes I- oder P-Bildes angepaßt werden, um sich dynamisch ändernde Eigenschaften der Videosequenz zu verfolgen. Dazu kann ein Verfahren verwendet werden, das weiter unten im Zusammenhang mit dem RC-Bildcodierer 16 ausführlich beschrieben wird. (Für Intramodus-MBs kann dieses Modell verbessert werden, indem ein zusätzlicher Term hinzugefügt wird, der die Anzahl der zum Codieren der DC-Terme im MB benötigten Bits berücksichtigt, da die Codierung für DC-Koeffizienten separat behandelt wird).
Die vorhergesagte Anzahl der zum Codieren der Transformationskoeffizienten für das gesamte Bild benötigten Bits beträgt nach diesen Bitratenmodellen
für I-Bilder und
für P-Bilder, wobei QP(r, c) nach der Formel
QP(r, c) = QPlow + ΔQP · cl(r, c).
berechnet wird.
Als Anfangswert für QPlow wird der QP-Wert genommen, für den B(QP) der dem Bild zugeordneten Transformationskoeffizientenzuordnung C am nächsten kommt:
QP = argQPmin B(QP) - Cn .
In der bevorzugten Ausführungsform wird eine Halbintervallsuche zwischen -31 und 31 durchgeführt, um QP zu finden. Die Rolle der Ober- und Untergrenzen für QP in diesem Verfahren ist schwierig. Eine Obergrenze von 31 reicht aus, daß der Codierer garantiert mit der gröbsten vom Standard erlaubten Quantisierung arbeiten kann; eine höhere Obergrenze ändert aber die Leistungsfähigkeit des Ratensteuerungsalgorithmus, wie weiter unten noch ausführlicher zu sehen sein wird, indem sie ihn empfindlicher für die Überproduktion von Bits macht. Ähnliches gilt für die Untergrenze für QP.
Nach der Ermittlung von QPlow berechnet die QP-Ebenen-Festlegungseinheit 15 die zu erwartende Anzahl Bits, die zum Codie ren von MB-Zeile r mit Hilfe von QPlow benötigt werden, nach der Formel
wobei Nrow die Anzahl der MB-Zeilen ist. Im zweiten Term dieses Ausdrucks wird die Differenz zwischen der vom Modell bei QPlow vorhergesagten und der tatsächlichen Transformationskoeffizientenzuordnung C berücksichtigt, und im dritten Term der Anteil, den jede Zeile an der Nebeninformationszuordung S hat. Die Summe der Sollwerte T(r) über alle Zeilen ergibt die Gesamtbildzuordnung A. Diese erwarteten Werte werden zu den Soll-Bitwerten pro Zeile für den RC-Bildcodierer 16.

RC-Bildcodierer

Die Bildcodierung fährt mit der Indexierung der MBs und der Codierung der einzelnen MBs mit der im vorigen Schritt bestimmten Modus- und Quantisierungsschrittwerte fort. Aufgrund von Nichtübereinstimmungen im Bitratenmodell und der ständigen Änderungen des Inhalts einer Sequenz stimmt die tatsächlich erzeugte Bitanzahl allerdings nicht exakt mit der erwarteten Anzahl überein. Es ist wünschenswert, diese Abweichung zu steuern, nicht nur, um die tatsächliche Anzahl der für das Bild erzeugten Bits möglichst nahe am Sollwert zu halten, sondern auch, um ein Über- bzw. Unterschreitung der VBV-Bitratengrenzen zu verhindern. In der Erfindung wurde eine Ratensteuerungs-Rückkopplungsstrategie entwickelt, die am Ende jeder MB- Zeile QPlow aktualisiert. Die Aktualisierung wird vom mehreren Faktoren bestimmt. Ein Faktor besteht darin, daß die einzelnen MB-Zeilen in einem Bild aufgrund von Variationen in Δ(r, c) and Δmc(r, c) und der zugeordneten Quantisierungsschrittgrößen erwartungsgemäß nicht die gleiche Anzahl von Bits erzeugen. Am Ende jeder Zeile wird die erzeugte Bitanzahl mit der in der QP-Ebenen-Festlegungseinheit 15 berechneten, erwarteten Zahl T(r) verglichen. Ein weiterer Faktor, der bei der Aktualisierung von QPioW eine Rolle spielt, ist, wie nahe die Bildzuordnung und die tatsächlich erzeugte Bitanzahl den VBV-Grenzwerten kommt. Der Vorteil der QPlow Aktualisierung als Funktion von Bitratenabweichungen ist abhängig von der Nähe zu VBV- Grenze in Fehlerrichtung. Kleinere Abweichungen von der vorhergesagten Bitrate haben keine oder nur eine geringfügige Änderung von QPlow zur Folge, während Abweichungen, die die Bildbitrate in die Nähe eines der VBV-Grenzwerte bringen, die maximal mögliche Anpassung von QPlow bewirken. Eine solche Strategie verhindert die Über- bzw. Unterschreitung der VBV-Grenzwerte recht erfolgreich und verhindert somit unerwünschte Aktionen wie die Unterdrückung codierter Daten oder die Einfügung zusätzlicher Bytes in den Bitstrom.
Die nachstehenden Gleichungen beschreiben das in der bevorzugten Ausführungsform der Erfindung implementierte Aktualisierungsverfahren für QPlow. Wenn die Gesamtanzahl der zum Codieren von Zeile m und aller vorausgehenden Zeilen durch B(m) und die Differenz zwischen B(m) und dem kumulativen Sollwert als ΔB(m) bezeichnet wird, ist
ΔB(m) = B(m) - T(r).
Nach der Codierung von Zeile m wird QPlow folgendermaßen aktualisiert, falls ΔB(m) ≠ 0 ist:
wobei Δu und Δl die Differenzen zwischen der Bildzuordnung A und der obere und untere VBV-Grenzwert für Bild n ist:
Δu = UVBV - A,
Δl = max(0, LVBV) - A.
Durch diese Strategie wird QPlow basierend auf dem Gesamtbitzuordnungsfehler bis zur aktuellen Zeile aktualisiert, indem dieser auf den nach dem VBV-Kriterium maximal zulässigen Fehler bezogen wird.
Bei der Codierung jedes I- oder P-Bildes werden neue Bitratenmodell-Parameter (aI und aP) berechnet, so daß das Bitratenmodell mit der Anzahl der tatsächlich erzeugten Transformationskoeffizientenbits (Ca) übereinstimmt. Um dies für den Fall eines I-Bildes zu illustrieren, wird bei der Codierung jedes Bildes die Summe aller Δ(r, c) für mit jedem QP-Wert codierte MBs ermittelt:
SΔ(QP) = Δ(r, c), QP = 1, ..., 31.
Ein Aktualisierungswert von aI wird durch
und
a'I = (1 - α)aI + αa'I
berechnet.
In der Implementierung kann ein Wert von α = 0.667 verwendet werden. Eine ähnliche Strategie wird verwendet, um nach der Codierung eines P-Bildes aI und aP zu aktualisieren. In diesem Fall ist α proportional zum Anteil der MBs, die in dem Modus codiert wurden, der dem zu aktualisierenden Bitratenmodellparameter entspricht.
Schließlich wird die zum Codieren aller Nebeninformationen für das Bild benötigte Bitanzahl gespeichert, damit sie als Wert für die Nebeninformationszuordnung S für das nächste Bild des gleichen Typs verwendet werden kann.
Die Wirkung der Strategien für die QP-Zuordnung und Aktualisierung ist in Fig. 13 und Fig. 14 dargestellt. In Fig. 13 ist QPlow und der QP-Durchschittswert in jeder Zeile der Halbbilder 16, 22, 61 und 67 der Testsequenz dargestellt. Wenn der anfängliche Schätzwert für QPlow und die Bitratenmodelle exakt wären, wäre QPlow in allen Zeilen gleich. Der Durchschnittswert QPavg fluktuiert aber je nach räumlicher Aktivität und Bewegungskompensation der verschiedenen Zeilen in den Bildern. Am QP-Wert für die I-Bilder ist beispielsweise leicht zu erkennen, daß die untere Hälfte der Zeilen des Blumengartensegments eine wesentlich höhere räumliche Komplexität aufweist als die obere Hälfte. Die Ergebnisse für P-Bilder zeigen, daß die Bewegungskompensation die Variation in QPavg reduziert. In Fig. 14 sind die erzeugten Bits in Abhängigkeit von den Sollwerten für die einzelnen Zeilen dargestellt. Es ist zu erkennen, daß die Ergebnisse recht nahe bei den Sollwerten liegen.
Das Ratensteuerungsverfahren für B-Bilder unterscheidet sich von dem für I- und P-Bilder. Hier wurde keine MB-Klassifizierung vorgenommen, und deshalb wird auch nicht versucht, abzuschätzen, wieviel komprimierte Daten jede MB-Zeile erzeugen wird. Am Anfang jedes Bildes wird der Quantisierungsfaktor auf den Wert gesetzt, den er am Ende des vorhergehenden B-Bildes hatte. Nach jeder MB-Zeile wird QP im wesentlichen auf die gleiche Weise aktualisiert wie bei den anderen Bildtypen, wobei aber die Ober- und Untergrenze definiert sind durch
Δu = max(UVBV - A,A),
Δl = max(0, IVBV) - A.
Die obige Beschreibung stellt ein Videocodierungsverfahren vor, das eine adaptive Bitzuordnung und eine Quantisierung verwendet, um robuste, hochwertig codierte Sequenzen über einen Bereich von Quellenmaterialien und Bitraten zu erzeugen. Die codierten Daten entsprechen den Bitratenanforderungen des ISO/IEC MPEG-Videocodierungsstandards. Die für die Implemen tierung der adaptiven Verfahren erforderliche zusätzliche Komplexität des Codierers ist gering, was die Grundoperationen der Bewegungsabschätzung, diskrete Cosinustransformationen, Quantisierung und Huffman-Codierung angeht, die Teil eines einfachen Decoders sind. Diese Funktionen sorgen dafür, daß der Algorithmus für flexible Videocodierungs- und -decodierungsimplementierungen in Echtzeit geeignet ist.

Adaptive Vorverarbeitung von Videosequenzen

Die Funktionsweise des erfindungsgemäßen QP-adaptiven Vorprozessors 3 basiert auf der Beobachtung, daß unter bestimmten Bedingungen mit Codierern mit geringer Bitrate visuell ansprechendere Bilder erzeugt werden, wenn die Eingabebilder so vorverarbeitet wurden, daß Rauschen entfernt und/oder hochfrequente Informationen abgeschwächt wurden, die ineffizient zu codieren, aber visuell weniger wichtig als niederfrequente, rauschfreie Informationen sind. Speziell wenn Sequenzen Bereiche nicht vernachlässigbarer Größe enthalten, die nur eine geringe räumliche Komplexität aufweisen, oder wenn aus irgendeinem Grund ein Rauschen vorhanden ist, ist eine übermäßig große Anzahl Bits erforderlich, um die detailreichen Bereiche und das Rauschen akkurat darzustellen; dies führt aber insgesamt zu einer geringeren visuellen Qualität. Diese Qualitätseinbuße tritt oft in Form visuell störender, flackernder, rauschähnlicher Artefakte auf. Es ist oft ein guter Kompromiß, den Hochfrequenzgehalt durch eine Vorverarbeitung wie die lineare oder nichtlineare Filterung zu reduzieren, die das Bild weniger originalgetreu aussehen läßt, dafür aber eine bessere Wiedergabe der niederfrequenten Information ohne störende Artefakte ermöglicht. Andererseits sind viele Sequenzen so aufgebaut, daß die visuelle Qualität bei niedrigen Bitraten recht akzeptabel ist, ohne daß hochfrequente Informationen und Rauschen reduziert werden müssen. In solchen Fällen bringt die Vorverarbeitung unnötige Qualitätseinbußen. Es ist deshalb wünschenswert, je nach Bedarf entweder eine Vorverarbeitung durchführen oder auf eine solche verzichten zu können.
Ein wichtiger Indikator für die Notwendigkeit einer Vorverarbeitung ist die Quantisierungsebene, die erforderlich ist, um die Sequenz mit der Sollbitrate zu codieren. Der Hauptvorteil der Verwendung von Informationen über den Quantisierungsfaktor zur Steuerung des Vorverarbeitungsumfangs besteht darin, daß er von der Bitrate unabhängig ist. Allgemein ausgedrückt bedeutet dies, daß wenn die Quantisierungsebene die meiste Zeit sehr hoch ist (d. h. wenn die Quantisierung grob und die Rekonstruktion daher relativ schlecht ist), der Grund darin liegt, daß die Szene zu komplex ist, um mit der Sollbitrate akkurat codiert zu werden.
Die allgemeine Funktionsweise des dritten Subsystems der Erfindung wird anhand von Fig. 6 unter Bezugnahme auf die Komponenten des in Fig. 15 allgemein dargestellten QP-adaptiven Vorprozessors 3 und eine in Fig. 16 dargestellte bevorzugte Ausführungsform beschrieben. Wie bereits im Zusammenhang mit der Funktionsweise des AQ/RC-Bildcodierers 1 erläutert wurde, wird bei der Codierung jedes Bildes ein vorhergehender Quantisierungsfaktor QPprev, berechnet, der zur Quantisierung der Transformationskoeffizienten verwendet wird. Diese Quantisierungsebene kann von vielen Dingen abhängen, z. B. von der Anzahl MBs in jedem Bildtyp, der Anzahl der Bits, die dem Bild vom Bildbitzuordnungs-Subsystem 2 zugeordnet wurden, und der Gesamtkomplexität des Bildes. Der durchschnittliche QP zum Codieren eines Bildes ist oft eine gute Größe für QPprev. Nachdem die Codierung eines Bildes abgeschlossen ist, wird QPprev vom AQ/RC-Codierer 1 an den QP-adaptiven Vorprozessor 3 übergeben. Basierend auf den QPprev Werten von möglicherweise mehr als einem vorausgehenden Bild wird einer von mehreren Vorprozessoren ausgewählt, der für alle Bilder ab einem Zeitpunkt in der Zukunft verwendet werden soll, bis ein neuer QPprev Wert aus einem späteren Bild eine erneute Änderung des Vorprozessors verursacht. Wie in Fig. 15 zu sehen ist, wird das QPprev-Signal in einem Implementierungsverzögerungspuffer 31 empfangen und an eine Vorprozessoralgorithmus-Auswahleinheit 32 übergeben, die das Umschalten des Signals auf eine Vorprozessoreinheit 33 steuert.
Die Vorprozessoreinheit 33 kann aus einer Reihe von Filtern, Filter 1, Filter 2, ..., Filter n bestehen. Eine bevorzugte Implementierung der Vorprozessoreinheit 33 ist in Fig. 16 dargestellt, wo die Vorprozessorfilter rein linear sind und es drei mögliche Filterzustände (FS) gibt:
1. FS = 0 Kein Filter.
2. FS = 1 Trennbares 3-teiliges FIR-Filter mit Koeffizienten (1/16, 7/8, 1/16).
3. FS = 2 Trennbares 3-teiliges FIR-Filter mit Koeffizienten (1/8, 3/4, 1/8).
Folgender Algorithmus ist für die Aktualisierung der Filterzustände unter der Steuerung durch die Einheiten 31 und 32 nützlich:
FS ← {min(2, FS + 1) if Qavg > T&sub1;. {max(0, FS - 1) if Qavq < T&sub2;.
Die Aktualisierung des Filterzustands erfolgt nur nach I-Bildern, und der neue Zustand tritt erst beim nächsten I-Bild in Kraft (diese Verzögerung wird als Implementierungsverzögerung bezeichnet). Sinnvolle Werte sind 10 für T&sub1; und 5 für T&sub2;.
Die spezielle Auswahl von Filtern, Filterzuständen, Regeln zur Aktualisierung der Filterzustände und Implementierungsverzögerung ist nur eine von vielen Möglichkeiten innerhalb des Umfangs der Erfindung. Es kann eine beliebige Anzahl von Filtern geben, und die Filter können auch nichtlinear oder räumlich adaptiv sein. Eine weitere wichtige Variation besteht darin, den Filterzustand häufiger zu aktualisieren und gleichzeitig die Implementierungsverzögerung zu verringern. So kann die Aktualisierung des Filterzustands beispielsweise nach jedem P- Bild erfolgen, wobei die Implementierungsverzögerung auf den Abstand zwischen zwei P-Bildern reduziert wird.

Claims

1. Ein Verfahren zum Zuordnen von Bits, die zur Komprimierungscodierung digitaler Datensignale, welche eine oder mehrere Gruppen von Bildern in einer bewegten Videosequenz darstellen, benutzt werden, in Form eines M-PEG II-Datenstroms, bestehend aus folgenden Schritten:

Identifizieren jedes Bildes der Gruppe bzw. Gruppen, die einer Komprimierungscodierung unterzogen werden soll, als zugehörig zu einem der drei Typen I, P, B;

Ermitteln der Gesamtanzahl der Bits (Bset), die bei der Komprimierungscodierung jeder Bildergruppe verwendet werden soll, anhand einer festgelegten Soll-Bitrate für jede Sequenz, wobei die Gesamtanzahl der Bits (Bset) gleich einer durchschnittlichen Bitzuordung (Bavg) multipliziert mit der Gesamtanzahl der I-Bilder (nI), P-Bilder (nP) und B- Bilder (nB) in der Gruppe ist, so daß Bset = (nI + nP + nB) · Bayg ist;

und, nachdem vorzugsweise von der Gesamtanzahl der Bits (Bset) ein Schätzwert (Ssec) für die Anzahl der zum Codieren der Nebeninformation in jeder Gruppe benötigten Bits subtrahiert worden ist, woraus eine modifizierte Gesamtanzahl der Bits (Cset) resultiert, von der Gesamtanzahl der Bits (Cset oder Bset) Bits zur Verwendung bei der Komprimierungscodierung eines Bildes in jeder Gruppe zugeordnet werden, indem vor der Komprimierungscodierung der einzel nen Bilder Zuordnungen (CI, CP, CB) für jeden Bildtyp in der Gruppe bestimmt werden, unter Verwendung

1) des Schwierigkeitsgrades (DI, DP, DB) der Komprimierungscodierung jedes Bildtyps, wobei der Schwierigkeitsgrad der räumlichen Komplexität eines betreffenden Bildes entspricht, so daß die Bitzuordnung (CI, CP, CB) für einen betreffenden Bildtyp mit zunehmendem bzw. abnehmendem Schwierigkeitsgrad (DI, DP, DB) der Komprimierungscodierung zu- bzw. abnimmt, und

2) der Gesamtanzahlen (NI, NP, NB) jedes der drei Bildtypen in jeder Gruppe zur Erzeugung von Zuordnungen, die die feste Soll-Bitrate erfüllen.

2. Ein Verfahren nach Anspruch 1, bei dem der Zuordnungsschritt nach folgenden Gleichungen ausgeführt wird

Cset = nICI + nPCP + nBCB;

and

wobei WP und WB Gewichtungsfaktoren sind, um die Bitzuordnungen von P- und B-Bildern im Vergleich zu den anderen weniger stark zu betonen, und E'r ein durchschnittlicher Bewegungskompensationsfehler ist, der bei der bewegungskompensierten Bildrekonstruktion auftritt.

3. Ein Verfahren nach Anspruch 1, bei dem die Bitzuordnung für jeden Bildtyp proportional zum Schwierigkeitsgrad der Komprimierungscodierung des betreffenden Bildtyps ist.

4. Ein Verfahren nach Anspruch 1, bei dem der Schwierigkeitsgrad der Komprimierungscodierung jedes Bildtyps anhand der Schwierigkeit der Komprimierungscodierung der Pixeldaten des zu codierenden Bildes und mindestens eines bereits codierten Bildes aus der Gruppe ermittelt wird.

5. Ein Verfahren nach Anspruch 1, bei dem der Schwierigkeitsgrad der Komprimierungscodierung jedes Bildtyps anhand der Schwierigkeit der Komprimierungscodierung der Pixeldifferenzdaten des zu codierenden Bildes und mindestens eines bereits codierten Bildes aus der Gruppe ermittelt wird.

6. Ein System zur Zuordnung von Bits, die zur Komprimierungscodierung digitaler Datensignale, welche eine oder mehrere Gruppen von Bildern in einer bewegten Videosequenz darstellen, benutzt werden, in Form eines M-PEG II- Datenstroms, bestehend aus:

Mitteln zum Identifizieren jedes Bildes der Gruppe bzw. Gruppen, die einer Komprimierungscodierung unterzogen werden soll, als zugehörig zu einem der drei Typen I, P, B;

Mitteln 1-3 zur Ermittlung der Gesamtanzahl der Bits (Bset), die bei der Komprimierungscodierung jeder Bildergruppe verwendet werden soll, anhand einer festgelegten Soll-Bitrate für jede Sequenz, wobei die Gesamtanzahl der Bits (Bset) gleich einer durchschnittlichen Bitzuordung (Bavg) multipliziert mit der Gesamtanzahl der I-Bilder (nI), P-Bilder (np) und B-Bilder (nB) in der Gruppe ist, so daß Bset = (nI + nP + nB) · Bavg ist; Mitteln, um vorzugsweise von der Gesamtanzahl der Bits (Bset) einen Schätzwert (Sset) für die Anzahl der zum Codieren der Nebeninformation in jeder Gruppe benötigten Bits zu subtrahieren, woraus eine modifizierte Gesamtanzahl der Bits (Cset) resultiert;

und Mitteln 2, um aus der Gesamtanzahl der Bits (Cset oder Bset) Bits zur Verwendung bei der Komprimierungscodierung eines Bildes in jeder Gruppe zuzuordnen, indem vor der Komprimierungscodierung der einzelnen Bilder Zuordnungen (CI, CP, CB) für jeden Bildtyp in der Gruppe bestimmt werden, unter Verwendung

7. Ein System nach Anspruch 6, bei dem das Zuordnungsmittel 2 folgende Gleichungen erfüllt:

Cset = nICI + nPCP + nBCB;

and