DE69227676T2

DE69227676T2 - Verfahren und gerät zur datenkodierung unter verwendung von vektorquantifizierung und lauflängenkodierung und unter verwendung von adaptiver lauflängenkodierung

Info

Publication number: DE69227676T2
Application number: DE69227676T
Authority: DE
Inventors: Jae S. Winchester Ma 01890 Lim
Original assignee: Massachusetts Institute of Technology
Current assignee: Massachusetts Institute of Technology
Priority date: 1991-12-24
Filing date: 1992-12-18
Publication date: 1999-07-22
Anticipated expiration: 2012-12-19
Also published as: JP3195966B2; US5339164A; EP0572638B1; JPH06508490A; EP0572638A1; KR100261923B1; CA2104287C; ATE173847T1; DE69227676D1; WO1993013497A1; EP0572638A4; CA2104287A1

Description

Die vorliegende Erfindung betrifft allgemein das Gebiet der Signalverarbeitung und insbesondere das Codieren und Komprimieren von Daten. Die Erfindung bezieht sich ganz besonders auf ein Verfahren und eine Vorrichtung zum Codieren und Komprimieren von Daten unter Anwendung der Lauflängencodierung alleine mit einem adaptiven Codebuch und unter Anwendung sowohl der Vektorquantisierung als auch der Lauflängencodierung mit oder ohne adaptives Codebuch. Die betreffenden Daten können in einer, zwei, drei oder mehr Dimensionen sein, die meisten praktischen Anwendungen betreffen jedoch Daten in zwei und drei Dimensionen. Die Erfindung ist praktisch anwendbar auf dem Gebiet der Bildverarbeitung, umfassend Fernsehen, Bildtelefon; Drahtfunkübertragung von Zeitungen; medizinische Abbildungen; Satellitenfoto-Abbildungen und viele andere Bildanwendungen. Die Erfindung ist außerdem anwendbar bei der dreidimensionalen Datenverarbeitung wie etwa bei Bildverarbeitungssystemen, bei der Festkörpermodellierung und dem Erstellen von meteorologischen und geologischen Karten.

Hintergrund der Erfindung

Bei der Verarbeitung von Bildern wird die räumliche Darstellung eines Bildes beispielsweise in zwei Dimensionen charakteristisch in ein Signal umgeformt, das das Bild in einem anderen Datenraum repräsentiert. Unter den Gründen für diese Umwandlung ist die Kompriminierung oder Minimierung der Digitaldatenmenge, die erforderlich ist, um das Bild adäquat zu repräsentieren. Die Verringerung des Datenbedarfs erhöht die Geschwindigkeit, mit der die Daten entlang Kommunikationskanälen mit fester Bandbreite übermittelt werden können, und verringert außerdem den Speicherbedarf, der zum Speichern des Bilds notwendig ist. Ein großer Teil der nachstehend Erörterung des Hintergrunds ist dem ausgezeichneten Artikel von G. Wallace, "The JPEG Still Picture Compression Standard", Communications of the ACM, April 1991, S. 30-43, entnommen.
Im Grundfall eines zweidimensionalen Graustufenbilds werden die kontinuierlichen (in Raum und Amplitude) Graustufenintensitäten über die beiden Dimensionen des Bilds in eine Anordnung von diskreten Bildpunkten umgewandelt, die jeweils eine diskrete Intensität haben, die aus einer Gruppe von typischerweise unveränderlichen Quantisierungspegeln gewählt wird. Ein typisches digitales Bild besteht aus einem Feld von n&sub1; mal n&sub2; (z. B. 512 mal 512) Bildelementen, von denen jedes auf 256 Intensitätspegel quantisiert ist, wobei diese Pegel durch acht Digitalsignalbits repräsentiert werden können. Jeder Pegel wird gewöhnlich mit einer ganzen Zahl bezeichnet, wobei 0 dem dunkelsten und 255 dem hellsten Pegel entspricht.
Die Abtastung des Bilds kann mit vielen Techniken durchgeführt werden. Eine Grundtechnik besteht darin, den gesamten Graustufenintensitätswert in 256 Pegel aufzuteilen, die Intensität an jeder von n&sub1; Stellen über das. Bild und für n&sub2; Zeilen das Bild abwärts zu messen und jedem der Bildelemente in dem Feld denjenigen der 256 Pegel zuzuordnen, der der tatsächlichen gemessenen Intensität am besten entspricht.
Das Ergebnis der Abtastung ist ein digitales Bild, das durch ein Feld aus n&sub1; mal n&sub2; ganzen Zahlen mit Amplituden zwischen 0 und 255 repräsentiert werden kann. Zum Übertragen des Bilds ist es technisch möglich, diese Daten einfach in einem Strom eine Zeile nach der anderen zu übertragen. Eine solche Behandlung würde jedoch die Übertragung einer großen Datenmenge (acht Bits je Bildelement) erfordern. Es ist wohlbekannt, daß signifikante Anteile von Bildern durch Bildelemente dargestellt werden, die einander ähnlich sind und die miteinander korreliert sind. Erhebliche Einsparungen in bezug auf Datenerfordernisse können durch wohlbekannte Techniken erreicht werden, die die Redundanz ausnützen, die sich in vielen Bildern ergibt.
Ein wohlbekanntes Verfahren besteht darin, das Bild aus einem räumlichen Bereich, d. h. einem Bereich, in dem eine Intensitätsamplitude mit einem räumlichen Ort in den n&sub1;- und n&sub2;-Dimensionen korreliert ist, in einen anderen Bereich wie etwa einen räumlichen Frequenzbereich zu transformieren. In dem räumlichen Frequenzbereich ist das Bild durch Amplituden mit räumlichen Frequenzen repräsentiert. Räumliche Frequenzen können als mit dem Grad der Änderung der Intensität von einem Bildelement zum nächsten entlang entweder der horizontalen oder der vertikalen Dimension (oder Kombinationen davon) angesehen werden. Beispielsweise ist ein Bild aus vertikalen Strichen einer bestimmten Breite, die zwischen schwarz und weiß alternieren, durch eine Menge von räumlichen Frequenzen charakterisiert. Im Fall eines gleichartigen Bilds mit schmaleren Strichen ist die Menge von räumlichen Frequenzen verschieden, was auf die höhere Frequenz der Änderung von einem Bildelement zum nächsten hinweist. Ebenso führen Änderungen in der vertikalen Dimension zu gleichartigen Veränderungen. Codiertechniken, die das räumliche Bild in einen anderen Bereich wie etwa einen Frequenzbereich transformieren, werden allgemein als "Transfoirmations"- Codiertechniken bezeichnet.
Eine typische Transformations-Codiertechnik ist als die DCT- oder diskrete Cosinustransformationstechnik bekannt. Der Name leitet sich daraus ab, daß eine Cosinusfunktion auf Signalelemente angewandt wird, die räumlich diskret und kein räumlich kontinuierliches Signal sind.
Die DCT-Komprimierung kann man sich vorstellen als die Komprimierung eines Stroms von t Gesamtabtastblöcken 1021, 1022, 102&sub3;, ..., 102n, ...102t des Originalbilds 104, das in Fig. 1 schematisch gezeigt ist, in n&sub1; und n&sub2;. Jeder Block 102n besteht aus einem Feld von benachbarten Bildelementen 106. Eine typische Blockgröße ist ein Bildelementblock von 8 mal 8 Bildelementen mit einer Gesamtzahl von 64 Bildelementen. In dem in Fig. 1 gezeigten Fall ist t = 4096.
Fig. 2 zeigt die wesentlichen Schritte einer Transformations- Codiertechnik wie etwa einer DCT für eine Einzelkomponente wie etwa eine Graustufenamplitude. Jeder Block 102n von 8 · 8 wird in den Codierer 120 eingegeben. Die Daten werden einem DCT-Operator 122 zugeführt. In dem DCT wird die Transformationsfunktion auf die Daten in jedem Block 102n entsprechend der nachstehenden wohlbekannten Gleichung angewandt:
mit C(k&sub1;), C(k&sub2;) =1/ 2 für k&sub1;, k&sub2; = 0, C (k&sub1;), C (k&sub2;) = 1 im übrigen.
In dem vorstehenden Ausdruck ist F(k&sub1;,k&sub2;) die transformierte Funktion in den Variablen k&sub1; und k&sub2;, und f (n&sub1;,n&sub2;) ist das Amplitudenmuster der ursprünglichen Funktion in dem Block 1022 als eine Funktion von n&sub1; und n&sub2;, den räumlichen Dimensionen. Der DCT 122 kann als ein Oberwellenanalysator angesehen werden, d. h. als eine Komponente, die die Frequenzanteile ihres Eingangssignals analysiert. Jeder 8 · 8-Block 102n ist effektiv ein diskretes Signal mit 64 Punkten, das eine Funktion der zwei räumlichen Dimensionen n&sub1; und n&sub2; ist. Der DCT 122 zerlegt das Signal in 64 orthogonale Grundsignale, von denen jedes eine der 64 eindeutigen zweidimensionalen (2-D) "räumlichen Frequenzen" enthält, die das "räumliche Spektrum" des Eingangssignals umfassen. Das Ausgangssignal des DCT 122 wird hier als ein "Transformationsblock" bezeichnet und ist die Menge von 64 Grundsignalamplituden oder "DCT-Koeffizienten", deren Werte durch das jeweilige 64-Punkte-Eingangssignal, d. h. durch das Muster von Intensitäten in dem Block 102, eindeutig bestimmt sind. Die DCT-Transformation wird zwar hier für die Zwecke der Erläuterung verwendet, aber andere Transformationen einschließlich der Teilbandtransformationen sind anwendbar und können in Verbindung mit der Erfindung angewandt werden.
Die DCT-Koeffizientenwerte können somit als die relativen Werte der räumlichen 2-D-Frequenzen angesehen werden, die in dem 64- Punkte-Eingangssignal 102" enthalten sind. Der Koeffizient mit der Frequenz Null in beiden Dimensionen n&sub1; und n&sub2; wird als "DC- Koeffizient" bezeichnet, und die übrigen 63 Koeffizienten werden als "AC-Koeffizienten" bezeichnet.
Die Erfahrung zeigt, daß bei typischen Bildern 104 Abtastwerte von Bildelement zu Bildelement sich charakteristisch langsam über ein Bild ändern. Somit ist die Datenkomprimierung möglich, indem viele der verfügbaren Bits des Digitalsignals den niedrigeren Raumfrequenzen zugeordnet werden, die dieser langsamen räumlichen Änderung entsprechen. Bei einem typischen Quellenblock 102n haben viele der räumlichen Frequenzen die Amplitude Null oder nahezu Null und brauchen nicht codiert zu werden. Wie Fig. 3 schematisch zeigt, die eine typische grafische Darstellung eines Transformationsblocks 112n ist, der das Ergebnis der Transformation eines Blocks 102n mittels DCT ist, sind Nichtnull-Amplitudenkoeffizienten weiß angegeben, und Null-Amplitudenkoeffizienten sind schraffiert angegeben. Ein kleiner schraffierter Bereich 114, der um den Ursprung herum zentriert ist, ist von einem großen weißen Bereich 116 umgeben. Diese Art von Muster entsteht typischerweise bei jedem 8 · 8- Block.
Nach der Transformation in dem DCT 122 finden mehrere weitere Operationen in dem Quantisierer 124 und dem Codierer 126 statt, wobei diese Operationen nachstehend im einzelnen erläutert werden. Es ist zweckmäßig, diese Operationen jetzt zu erwähnen, damit der Codierer vollständig verstanden wird. Grundsätzlich erfolgt durch diese Operationen eine weitere Transformation und Codierung des transformierten Signals F(k&sub1;,k&sub2;), das von dem DCT abgegeben wird. Von dem DCT-Codierer 120 wird das Signal über einen Kommunikationskanal ausgesandt oder gespeichert oder anderweitig behandelt. Schließlich werden die komprimierten Bilddaten in einen DCT-Decodierer 130 eingegeben, der einen Decodierer 136, einen Entquantisierer 134 und einen inversen DCT ("IDCT") 132 aufweist. Der Entquantisierer 134 und der Decodierer 136 kehren die von dem Codierer 126 bzw. dem Quantisierer 124 bewirkten Effekte um. Das Ausgangssignal des Entquantisierers 134 ist daher eine Funktion in dem transformierten Datenraum (k&sub1;,k&sub2;) und typischerweise ebenfalls in Form eines 8 · 8-Blocks. In dem IDCT 132 wird auf die Daten in jedem Transformationsblock eine inverse Transformation angewandt. Die Transformation soll die Effekte der Vorwärtstransformation, die oben erläutert sind, aufheben, und ihre Charakteristiken sind dem Fachmann auf diesem Gebiet wohlbekannt.
Das Ausgangssignal des IDCT ist eine Rekonstruktion eines 8 · 8- Bildsignals in den räumlichen Dimensionen von n&sub1; und n&sub2;, erzeugt durch Summation der Grundsignale. Mathematisch ist die DCT eine Eins-zu-Eins-Umsetzung von 64 Werten zwischen dem Bild und den Frequenzbereichen. Wenn die DCT und die IDCT mit perfekter Präzision berechnet werden könnten, und wenn die DCT-Koeffizienten nicht wie etwa in dem Quantisierer 124 quantisiert (und daher anschließend entquantisiert) würden, könnte das ursprüngliche 64-Punkte-Signal 102 exakt wiedergewonnen werden. Prinzipiell führt die DCT keine Verluste in die Quellbildabtastwerte ein; sie transformiert sie nur zu einem Bereich, in dem sie effizienter codiert werden können.
Es wird nun wieder auf die Beschreibung der Codierungsphase des Codierprozesses Bezug genommen; nach Abgabe aus dem DCT 122 wird jeder der in diesem Fall 64 DCT-Koeffizienten unter Bezugnahme auf eine Quantisierungs- oder Rekonstruktionswerttabelle quantisiert. Ein Grund für die Quantisierung ist es, Informationen zu entfernen, die visuell nicht signifikant sind. Ein anderer Grund für die Quantisierung ist die Beseitigung der Notwendigkeit für eine unendliche Anzahl von Bits, die vorliegen würde, wenn die Quantisierung nicht angewandt würde. Bei der Quantisierung wird jeder Koeffizient mit den Einträgen in der Quantisierungstabelle verglichen und durch den Eintrag ersetzt, der dem tatsächlichen Koeffizienten am nächsten kommt. Wenn man zum Zweck der Erläuterung annimmt, daß Codewörter gleichförmiger Länge verwendet werden, und wenn 8 Bits verwendet werden, dann kann jeder Koeffizient in den nächstkommenden von 256 Quantisierungs- oder Rekonstruktionsstufen quantisiert werden. Wenn nur 7 Bits verwendet werden, sind nur 128 Rekonstruktionsstufen verfügbar. Charakteristisch haben jedoch die Codewörter keine gleichförmige Länge.
Das Ausgangssignal des Quantisierers 124 kann normalisiert werden. An dem Entquantisierer 134 wird der Effekt jeder Normalisierung umgekehrt. Das Ausgangssignal des Entquantisierers sind die quantisierten Werte, die in der von dem Quantisierer 124 verwendeten Quantisierungstabelle angegeben sind.
Wenn das Ziel eines bestimmten Signalverarbeitungsvorgangs darin besteht, das Bild möglichst weitgehend ohne sichtbare Bildfehler zu komprimieren, dann sollte jede Schrittgröße in der Quantisierungstabelle idealerweise als eine Wahrnehmungsschwelle oder "gerade noch merkliche Differenz" als der visuelle Beitrag ihrer entsprechenden Cosinusgrundfunktion gewählt sein. Diese Schwellenwerte sind auch Funktionen der Quellbildcharakteristiken, der Displaycharakteristiken und des Betrachtungsabstands. Bei Anwendungen, bei denen diese Variablen annehmbar gut definiert werden können, können psychovisuelle Experimente durchgeführt werden, um die besten Schwellenwerte festzulegen. Die Quantisierung ist eine Vielezu-Eins-Umsetzung und daher prinzipiell verlustbehaftet. Sie ist die Hauptquelle von Verlusten bei Codierern auf DCT-Basis.
Nach der Quantisierung wird der DC-Koeffizient charakteristisch separat von den 63 AC-Koeffizienten behandelt, obwohl für die Zwecke der vorliegenden Erfindung die DC-Komponente auch gemeinsam mit den übrigen Koeffizienten betrachtet werden kann. Der DC-Koeffizient ist ein Maß für den Mittelwert der 64 Bildabtastwerte. Da gewöhnlich eine starke Korrelation zwischen den DC-Koeffizienten benachbarter Quellenblöcke 102n vorliegt, wird der quantisierte DC-Koeffizient typischerweise als die Differenz gegenüber dem DC-Term des vorhergehenden Transformationsblocks in der Codierungsreihenfolge codiert. Die Codierungsreihenfolge für die Blöcke 102 ist charakteristisch eine sinusförmige Bahn entlang der n&sub1;-Richtung, die sich um einen Block am Ende einer Reihe von Blöcken nach oben bewegt usw., bis der letzte Block in der letzten Reihe erreicht ist. Das ist durch die Bahn S in Fig. 1 gezeigt. Es sind auch andere Blockcodierungs-Reihenfolgen möglich wie etwa ein vertikales sinusförmiges Muster oder ein sinusförmiges Muster, das zunehmend längere Strecken hat, die sich allgemein unter einem Winkel von 45º zu beiden Achsen erstrecken. Die unterschiedliche Behandlung der DC-Koeffizienten ist vorteilhaft, weil die Differenz zwischen DC-Werten weniger Energie verbraucht als die DC-Werte selber und daher zum Codieren der Differenzen weniger Bits erforderlich sind als zum Codieren der DC-Werte selber.
Nachdem die DC-Koeffizienten codiert sind, wird die Menge von AC-Koeffizienten typischerweise in einem Zickzackmuster geordnet, wie Fig. 4 zeigt. Dieses Ordnen beginnt mit den Komponenten niedriger Raumfrequenz sowohl in der k&sub1;- als auch der k&sub2;- Dimension und setzt sich zu den höherfrequenten Komponenten fort. Wie erwähnt wurde, sind die transformierten Bilder typischerweise durch relativ viele Komponenten großer Amplitude und niedriger Frequenz sowie relativ viele Komponenten kleiner Amplitude und höherer Frequenz charakterisiert. Dieses zickzackförmige Ordnen hilft im Fall der Lauflängencodierung, um eine Codierung der Orte in dem transformierten Bereich der Koeffizienten großer und kleiner Amplitude zu implementieren.
Typischerweise wird die Koeffizientenamplitude mit einem Schwellenwert verglichen. Oberhalb des Schwellenwerts wird die Amplitude als zu codieren ausgewählt. Unterhalb des Schwellenwerts wird die Amplitude nicht für die Codierung ausgewählt und wird auf Null gesetzt. Für die Zwecke der Erläuterung werden Koeffizienten, die Amplituden unterhalb des Schwellenwerts haben, als "nichtausgewählte" Koeffizienten und manchmal als Koeffizienten mit Null-Amplitude bezeichnet, wogegen Koeffizienten mit Amplituden oberhalb des Schwellenwerts als "ausgewählte" Koeffizienten oder als solche mit Nichtnull- Amplitude bezeichnet werden. Es versteht sich jedoch, daß viele der sogenannten Koeffizienten mit Null-Amplitude kleine Nichtnull-Amplituden haben.
Weil viele der Koeffizienten nicht ausgewählt werden, ist es effizienter, die Ortsinformation zu codieren, indem gekennzeichnet wird, welche der 63 AC-Koeffizienten ausgewählt werden sollen, und den Wert ihres quantisierten Koeffizienten zu codieren, anstatt einen Koeffizientenwert für jede der 64 räumlichen Frequenzen digital zu codieren. Die Koeffizienten werden durch ihre Orte in der geordneten Menge, die durch den transformierten Bereich definiert ist, identifiziert. Zwei Techniken sind bekannt, um zu codieren, welche der Koeffizienten Nichtnull-Koeffizienten sind. Die eine Technik bezeichnet man als "Lauflängencodierung", und die andere wird als "Vektorquantisierung" bezeichnet. Die Lauflängencodierung nutzt die Ordnung aus, die den Koeffizienten durch das Zickzackmuster auferlegt ist, während die Vektorquantisierung nur die Ordnung ausnutzt, die in der dimensionsmäßigen Anordnung des transformierten Bereichs inhärent ist.
Bei dem Verfahren der Lauflängencodierung werden die Positionen entlang der Zickzackbahn, die einen ausgewählten Koeffizienten haben, bezeichnet, und zwar auf der Basis ihres Orts relativ zu dem vorher ausgewählten Koeffizienten. Wie Fig. 5 zeigt, werden in dem transformierten Block 112n sechs AC-Koeffizienten ausgewählt. Diese sind der zweite, fünfte, sechzehnte, siebzehnte, vierundzwanzigste und vierzigste entlang der Zickzackbahn, wobei der DC-Koeffizient nicht gezählt wird. Eine Möglichkeit, dies zu codieren, besteht darin, ein digitales Codewort, das die Anzahl von nichtausgewählten Koeffizienten zwischen ausgewählten Koeffizienten (und damit die Orte des ausgewählten Koeffizienten) bezeichnet, gemeinsam mit einem Strom von Codewörtern zu übertragen, die die quantisierten Amplituden der ausgewählten Koeffizienten bezeichnen.
Beispielsweise ist in Fig. 5 eine Zwischen-Codezeichenfolge, die die Anzahl von nichtausgewählten Koeffizienten zwischen ausgewählten Koeffizienten bezeichnet, 1, 2, 10, 0,6, 15, 23 (oder, was typischer ist, "Blockende"). Beginnend mit dem DC-Koeffizienten als einem Ursprung ist vor dem ersten ausgewählten Koeffizienten (dem zweiten in der Zeichenfolge) einer. Die Anzahl von dazwischen befindlichen nichtausgewählten Koeffizienten zwischen dem ersten ausgewählten und dem zweiten Koeffizienten (dem fünften in der Zeichenfolge) ist zwei. Die Anzahl zwischen dem zweiten und dem dritten (dem sechzehnten) ist zehn. Die Anzahl zwischen dem dritten und dem vierten (dem siebzehnten) ist null usw. Nach dem letzten ausgewählten Koeffizienten ergeben sich dreiundzwanzig nichtausgewählte Koeffizienten vor dem Blockende. Es ist möglich, diesen Satz von dreiundzwanzig nichtausgewählten Koeffizienten mit dem Codewort "23" zu bezeichnen. Alternativ und effizienter wird dem Blockende ein spezielles Codewort zugeordnet, um anzuzeigen, daß der Rest der Koeffizienten (nach dem sechsten ausgewählten Koeffizienten) nichtausgewählte Koeffizienten sind. (Eine andere Methode zählt nicht die Anzahl von dazwischen befindlichen nichtausgewählten Koeffizienten, sondern bezeichnet den Ort des nächsten ausgewählten Koeffizienten. Beide Methoden laufen grundsätzlich auf das gleiche hinaus.).
Diese Zwischen-Codezeichenfolge (1, 2,10,0,6,15, Blockende) muß digital repräsentiert sein, und zwar charakteristisch einfach durch Binärcodierung für jede Lauflänge. Die kürzeste mögliche Lauflänge ist Null, und die längste mögliche Lauflänge ist 63, und nach dem einfachsten Schema sind daher sechs Bits erforderlich, um jede Lauflänge zu bezeichnen. Andere Schemata, die ein längenveränderliches Codewort verwenden, um jede Lauflänge zu bezeichnen, sind als "Entropie"-Codierung bzw. statistische Codierung bekannt und werden nachstehend erörtert.
Die vorstehende Codierung codiert nur die Positionen der ausgewählten Koeffizienten entlang der Zickzackbahn. Es ist auch notwendig, die Amplituden der Koeffizienten zu codieren. (Die Erfindung betrifft nur speziell die Codierung der Ortsinformation.) Charakteristisch umfaßt die Information, die die Orte der ausgewählten Koeffizienten kennzeichnet, mehr als die Hälfte der Daten, die zu übertragen sind. Wie bereits gesagt wurde, sind beispielsweise in dem besonderen Fall von gleichförmigen Codewörtern, die oben erläutert wurden, die Amplituden der Koeffizienten zu Codewörtern gleichmäßiger Wortlänge quantisiert worden, und zwar im erörterten Fall zu 8 Bits. Wenn daher gemäß einer Technik die ersten zu sendenden Codewörter diejenigen sind, die die Position (und Menge) der ausgewählten Koeffizienten codieren, kann für die Amplituden ein zweiter Strom von Codewörtern gesendet werden. Bei einem ganz rudimentären Verfahren, wie es beispielsweise in Fig. 5 gezeigt ist, wäre es also erforderlich, sieben Codewörter für die Orte (einschließlich eines für "Blockende") und sechs Codewörter für die Amplituden bei insgesamt dreizehn Codewörtern zu senden.
Bei der statistischen Codierung wird ein Vorteil aus der Erkenntnis der Tatsache erzielt, daß bei typischen Bildern die Wahrscheinlichkeit, daß sich eine bestimmte Lauflänge ergibt, in Abhängigkeit von der Länge veränderlich ist. Beispielsweise ist ein Satz von 62 sehr üblich und bezeichnet einen einzigen ausgewählten Koeffizienten in der ersten Position, während alle anderen Koeffizienten nichtausgewählt sind. Ebenso sind andere lange Sätze wahrscheinlicher als Sätze mäßiger Länge wie etwa 33. Sätze sehr kurzer Länge, z. B. null, eins und zwei, sind ebenfalls höchst wahrscheinlich, weil ausgewählte Koeffizienten die Tendenz haben, am Beginn des Zickzackmusters zusammengeballt zu sein. Bei der statistischen Codierung wird daher eine Schätzung der Wahrscheinlichkeit durchgeführt, daß ein bestimmter Wert, in diesem Fall eine Lauflänge, der Wert ist, der codiert werden soll, und die Werte werden entsprechend der Wahrscheinlichkeit vom höchsten zum niedrigsten geordnet. Als nächstes wird ein Satz von Codewörtern (auch als "Codebuch" bekannt) mit Codewörtern unterschiedlicher Länge (unterschiedlicher Anzahl von Bits) entwickelt. Die Codewörter mit der kürzesten Länge werden den Lauflängen der höchsten Wahrscheinlichkeit zugeordnet, und die Codewörter größerer Längen werden den Lauflängen geringerer Wahrscheinlichkeit zugeordnet. Daher benötigt man charakteristisch weniger Bits, um eine Serie von Sätzen zu bezeichnen, weil die wahrscheinlichsten Sätze mit den kürzesten Codewörtern bezeichnet sind.
Eine Komplikation der Entropiecodierung oder der Codierung mit längenvariablen Codewörtern resultiert daraus, daß die Codewörter nicht alle die gleiche Länge haben. Der Decodierer muß irgendeine Möglichkeit haben, um zu erkennen, wann in einem Strom von "1" und "0" ein Codewort endet und das nächste beginnt.
Wenn sämtliche Codewörter die gleiche Länge haben, beginnt der Decodierer einfach mit der Analyse eines Codeworts am Ende einer festgelegten Anzahl von Bits. In der Praxis werden einige Techniken für die längenvariable Codierung angewandt. Typisch sind die Huffman-Codierung und die arithmetische Codierung. Die Htiffman-Codierung ist im einzelnen von J. S. Lim in Two-Dimensional Signal and Image Processing, Prentice Hall, Englewood Cliffs, New Jersey (1990), S. 613-616, und D. A. Huffman, "A method for the construction of minimum redundancy codes", Proceedings IRE, Vol. 40, 1962, S. 1098-1101, erörtert, die hier beide summarisch eingeführt werden. Die arithmetische Codierung ist von W. B. Pennebaker, J. L. Mitchell et al., "Arithmetic coding articles", *IBM J. Res. Dev. 32, 6 Special Issue (Nov. 1988), 717-774, erörtert, die hier summarisch eingeführt wird. Im vorliegenden Fall wird nur die Huffman-Codierung erörtert, und zwar nur oberflächlich.
Nach einem Huffman-Codierschema wird ein Codebuch erstellt, so daß es bei der Analyse eines Stroms von Bits unzweideutig ist, wann ein Codewort vollständig ist. Beispielsweise könnte ein typischer Bitstrom 100011011101011111 sein. Das Codebuch, aus dem dieser Codestrom konstruiert wurde, ist schematisch in Fig. 6b gezeigt. Zur Erläuterung ist dieses Codebuch sehr klein und weist nur sechs Einträge auf. Es versteht sich jedoch, daß die aufgeführten Codewörter der gesamte Satz von Codewörtern für dieses Codebuch sind. Anders ausgedrückt sind weder 1, 111 noch 10 gültige Codewörter. Bei der Analyse der Folge von Bits von links nach rechts ist daher das erste Bit "1", was kein Codewort ist. Die Kombination des nächsten Bits zum Erhalt von "10" ist immer noch kein gültiges Codewort. Die Kombination des nächsten Bits ergibt "100", was ein gültiges Codewort ist, das die Lauflänge 1 bezeichnet. Beim erneuten Beginn ist das nächste Bit "0", was ein gültiges Codewort ist und eine Lauflänge von 0 bezeichnet. Beim erneuten Beginn ist das nächste Bit 1, kein gültiges Codewort, gefolgt von einer weiteren 1, so daß "11" erhalten wird, was immer noch kein gültiges Codewort ist. Durch Anhängen der nächsten "0" erhält man "110", das Codewort für eine Lauflänge 2. Die Anwendung des gleichen Verfahrens auf die restliche Folge zeigt, daß die Reihenfolge der Lauflängen 1, 0, 2, 4, 3, 5 war.
Die Anwendung der Huffman-Codierung resultiert in Codewörtern sehr großer Länge für diese sehr seltenen Lauflängen. Wenn die Tabelle jedoch richtig konstruiert ist, resultiert sie in der häufigsten Verwendung kurzer Codewörter. Die Huffman-Codierung erfordert, daß die Wahrscheinlichkeit verschiedener Lauflängen bekannt oder zumindest mit einer plausiblen Sicherheit geschätzt ist. Sie erfordert ferner die Speicherung des Codebuchs und die Zugriffsmöglichkeit darauf sowohl durch den Codierer 126 als auch den Decodierer 136, was nicht erforderlich ist, wenn das Codebuch einfach die digitale Darstellung der Lauflänge ist, wie in Fig. 6a angegeben ist. In diesem Fall ist kein Codebuch als solches notwendig, obwohl es immer noch erforderlich ist, Anweisungen sowohl für den Codierer als auch den Decodierer zur Verwendung dieser Art eines Codierschemas vorzusehen.
Die Analyse des Lauflängenverfahrens der Codierung des Orts von ausgewählten Koeffizienten zeigt, daß es hocheffizient ist, wenn die Lauflängen groß sind, und es nur erforderlich ist, den Ort von einigen wenigen Koeffizienten anzugeben. Wenn jedoch die Lauflängen kurz sind und es notwendig ist, den Ort von relativ vielen Koeffizienten zu bezeichnen, ist die Lauflängencodierung nicht sehr effizient, weil sowohl der Ort als auch die Amplituden für viele Werte bezeichnet werden müssen. Außerdem gibt es bei großen Blöcken wie etwa einem 8 · 8-Block eine erhebliche Differenz hinsichtlich der Wahrscheinlichkeit, daß ein bestimmter Lauf auftritt, der an dem zweiten Koeffizienten beginnt, im Vergleich mit dem Beginn an der dreißigsten Komponente. Beispielsweise ist die Wahrscheinlichkeit, daß irgend welche Läufe, die länger als 34 sind, an dem dreißigsten Koeffizienten beginnen, gleich Null, aber die typische Huffman-Codierung berücksichtigt dies nicht und ordnet die kürzeren Codewörter den Lauflängen zu, die die höchste Wahrscheinlichkeit eines Beginns an einem Koeffizienten nahe dem niederfrequenten Bereich des Blocks haben.
Eine andere Methode zum Codieren der Orte ausgewählter Koeffizienten wird ebenfalls angewandt. Diese Methode wird nicht in Verbindung mit der Lauflängencodierung verwendet. Diese Methode ist als "Vektorquantisierung" bekannt, weil sie die Darstellung des in Fig. 5 gezeigten Transformationsblocks 112n als einen zweidimensionalen Vektor behandelt. Anstatt die Unterschiede zwischen Orten ausgewählter Koeffizienten zu bezeichnen, bezeichnet die Vektorquantisierung das Muster ausgewählter Koeffizienten. Jedes mögliche Muster erhält ein eindeutiges Codewort. Das tatsächliche Muster wird mit einer Liste von Mustern in Übereinstimmung gebracht, und das Codewort wird übertragen.
Wie Fig. 7a zeigt, unterscheidet sich beispielsweise das Muster ausgewählter Koeffizienten von dem in Fig. 5 gezeigten Muster. Ebenso unterscheidet sich das in Fig. 7b gezeigte Muster von beiden. Im Fall eines 8 · 8-Blocks gibt es 264 oder ungefähr 1,8 · 1019 verschiedene Muster, was eine sehr große Anzahl ist. Es ist zwar möglich, jedoch umständlich, sämtliche möglichen Muster in einem Codebuch anzugeben, wie das schematisch in Fig. 8 gezeigt ist, und jedem der 264 Muster ein eindeutiges 64-Bit- Codewort zuzuordnen. Die Übertragung der codierten Muster erfordert somit nur das Senden eines einzigen, in diesem Fall 64- Bit-Codeworts und nicht von mehreren Codewörtern, die charakteristisch notwendig sind, um ein Muster unter Anwendung der Lauflängencodierung zu bezeichnen. Unabhängig davon, wie viele ausgewählte Koeffizienten es gibt, gibt es nur ein einziges Codewort, das übertragen wird, um ihr Muster und damit ihren Ort zu bezeichnen. Dies ist eine äquivalente Methode zu der Zuordnung eines Bits zu jedem Koeffizienten, um nur anzuzeigen, ob die Amplitude dieses Koeffizienten nichtnull ist oder nicht. Das Codebuch muß gespeichert und sowohl für den Codierer 126 als auch den Decodierer 136 zugänglich sein. Der erforderliche Speicherplatz zum Speichern des Codebuchs ist sehr groß, wenn man die große Anzahl von Mustern und die hohe Zahl von Bits betrachtet, die erforderlich sind, um jedes Muster zu codieren.
Wie im Fall der Lauflängencodierung ist es möglich und auch eher typisch, ein Codebuch mit längenvariablen Codewörtern anstelle des Buchs mit gleichförmiger Codewortlänge zu verwenden, wie schematisch in Fig. 8 gezeigt ist. In diesem Fall wird die Wahrscheinlichkeit unterschiedlicher Muster bestimmt oder geschätzt, und Muster der höchsten Wahrscheinlichkeit erhalten Codewörter, die die geringste Anzahl von Bits verwenden. Um also Muster hoher Wahrscheinlichkeit zu bezeichnen, muß ein Codewort von nur einigen Bits gesendet werden anstelle der 64 Bits eines Codewortsystems gleichförmiger Länge oder der Anzahl, die bei der Lauflängencodierung erforderlich ist. Es versteht sich ferner, daß dadurch, daß einige mögliche Bitfolgen keine gültigen Codewörter sind, infolge der Notwendigkeit der Bezeichnung der Grenzen zwischen Codewörtern variabler Längen die Codewörter für die Muster mit der geringsten Wahrscheinlichkeit viel mehr als 64 Bits, beispielsweise vielleicht bis zu 160 Bits erfordern.
Die Vektorquantisierung kann zwar in einer sehr effizienten Codierung der meisten Muster resultieren, sie erfordert aber die Erzeugung und Speicherung einer sehr großen Tabelle, um die Fähigkeit zur Codierung aller Muster zu haben, was es notwendig macht, daß die Vorrichtung sehr viel Platz für Speicher und Berechnungen hat, was für viele Situationen impraktikabel ist. Es ist möglich, die 8 · 8-Koeffizienten in mehrere Segmente zu unterteilen, aber dies führt zu einem Verlust an Effizienz, weil die Division des Blocks in Bereiche es erschwert, die Korrelation zwischen Bereichen zu nutzen.
Aus EP-A-0 339 589 ist ein orthogonales Transformations-Codiersystem für Bilder bekannt, das Bilddaten orthogonal in räumliche Frequenzen transformiert. Der Bereich der räumlichen Frequenzen wird in Nieder- und Hochfrequenzkomponenten aufgeteilt, und verschiedene Methoden werden angewandt, um die Transformationskoeffizienten der beiden Frequenzkomponenten zu codieren. Bei einer Ausführungsform zeigt die EP-A-0 339 589 eine Lauflängencodierung in bezug auf die Orte von ausgewählten Transformationskoeffizienten in der Hochfrequenzkomponente.
Daher umfassen die mehreren Aufgaben der Erfindung die Bereitstellung eines Verfahrens und einer Vorrichtung zum Codieren von eindimensionalen und multidimensionalen Signalen einschließlich der Position innerhalb eines Blocks von ausgewählten Koeffizienten wie etwa Transformationskoeffizienten, wobei: keine übermäßig große Speichermenge für die Speicherung von Codewörtern erforderlich ist, wodurch Codewörter einer relativ kleinen Bitrate erleichtert werden; die Zuordnung von unterschiedlichen Codewörtern zu der gleichen Lauflänge in Abhängigkeit von dem Ort des Ausgangskoeffizienten des Laufs erleichtert wird eine höhere Effizienz, ausgedrückt als je Koeffizient verwendete Bits, als bei der Lauflängencodierung erreicht wird; weniger Berechnungen und weniger Speicherbedarf als bei der Vektorquantisierung erforderlich ist; und eine umkomplizierte Implementierung möglich ist.

Kurze Beschreibung der Erfindung

Die vorliegende Erfindung ist in den Ansprüchen 1, 6 und 11 bis 13 angegeben.

Kurze Beschreibung der Zeichnungen

Fig. 1 zeigt schematisch einen Pfad, nach dem ein zweidimensionales Bild in Blöcken von Bildelementen abgetastet wird, und einen Pfad, nach dem die Blöcke geordnet sind.
Fig. 2 zeigt schematisch eine bekannte Vorrichtung zum digitalen Codieren eines zweidimensionalen Quellbilds und zum Decodieren der codierten Daten, um ein rekonstruiertes Bild zu erzeugen.
Fig. 3 zeigt schematisch Koeffizienten für einen Block von transformierten Daten, die einen Block eines zweidimensionales Bilds von Fig. 1 darstellen, wobei "ausgewählte" Koeffizienten großer Amplitude schraffiert bezeichnet sind und Koeffizienten kleiner Amplitude ("nichtausgewählte" Koeffizienten) weiß angegeben sind.
Fig. 4 zeigt schematisch einen Zickzackpfad durch einen Block von Transformationskoeffizienten, nach denen die Lauflängencodierung von Koeffizienten charakteristisch durchgeführt wird.
Fig. 5 zeigt schematisch einen Block von Transformationskoeffizienten, wobei ausgewählte Koeffizienten durch dunkle Quadrate und nichtausgewählte Koeffizienten weiß bezeichnet sind.
Fig. 6a zeigt schematisch einen Bereich eines Codebuchs, das bei der Lauflängencodierung verwendet wird, wobei alle Codewörter gleiche Länge haben.
Fig. 6b zeigt schematisch ein Codebuch, das bei der Lauflängencodierung verwendet wird, mit Codewörtern variabler Länge.
Fig. 7a zeigt schematisch einen Block von Transformationskoeffizienten, wobei ausgewählte Koeffizienten durch dunkle Quadrate und nichtausgewählte Koeffizienten weiß bezeichnet und diese Koeffizienten-Orte von denen in Fig. 5 verschieden sind.
Fig. 7b zeigt schematisch einen Block von Transformationskoeffizienten, wobei ausgewählte Koeffizienten durch dunkle Quadrate und nichtausgewählte Koeffizienten weiß bezeichnet sind und diese Koeffizienten-Orte von denen in Fig. 5 oder 7a verschieden sind.
Fig. 8 zeigt schematisch einen Bereich eines Codebuchs, das bei der Codierung mit Vektorquantisierung verwendet wird, wobei Codewörter konstanter Länge verwendet werden.
Fig. 9a zeigt schematisch einen Block von Transformationskoeffizienten, der zeigt, daß die Orte einer ersten Untermenge von Transformationskoeffizienten nach dem Verfahren der Erfindung unter Anwendung der Vektorquantisierung codiert sind, während die Orte einer zweiten Untermenge unter Anwendung der Lauflängencodierung codiert sind.
Fig. 9b zeigt schematisch einen Block von Transformationskoeffizienten, die ebenfalls sowohl mittels Vektorquantisierung als auch Lauflängencodierung codiert sind, wobei zwischen den Zonen unterschiedlicher Codierung eine andere Grenze im Vergleich mit dem in Fig. 9a gezeigten Block vorhanden ist.
Fig. 10a zeigt schematisch einen Block von Transformationskoeffizienten, die mittels Lauflängencodierung zu codieren sind, wobei Lauflängensegmente für die Durchführung des Verfahrens nach der Erfindung bezeichnet sind, die verschiedene Codebücher für verschiedene Laufsegmente des Blocks in Abhängigkeit von dem Ort des Laufanfangs verwenden.
Fig. 10b zeigt schematisch einen Block von Transformationskoeffizienten, die mittels Lauflängencodierung mit dem Verfahren der Erfindung zu codieren sind, wobei verschiedene Codebücher für verschiedene Laufsegmente verwendet werden, wobei außerdem die Vektorquantisierung für eine Untermenge der Transformationskoeffizienten angewandt wird.
Fig. 11 zeigt schematisch die Zusammensetzung verschiedener Codebücher für verschiedene Laufsegmente eines Transformationsblocks, der vollständig unter Anwendung der Lauflängencodierung codiert ist.
Fig. 12a und b zeigen schematisch eine bevorzugte Ausführungsform der Vorrichtung der Erfindung, wobei Fig. 12a den Codiererteil und Fig. 12b den Decodiererteil zeigt.
Fig. 13a und b zeigen schematisch eine bevorzugte Ausführungsform des Verfahrens der Erfindung unter Anwendung einer Kombination aus Lauflängencodierung und Vektorquantisierung, wobei Fig. 13a den Codiererbereich und Fig. 13b den Decodiererbereich zeigt.
Fig. 14a und b zeigen schematisch eine bevorzugte Ausführungsform des Verfahrens der Erfindung unter Anwendung einer Vielzahl von Codebüchern, wobei Fig. 14a den Codiererbereich und Fig. 14b den Decodiererbereich zeigt.

Genaue Beschreibung bevorzugter Ausführungsformen der Erfindung

Ein Aspekt der Erfindung macht sich den Vorteil der Erkenntnis zunutze, daß für Codierungsverfahren, bei denen der Ort von Transformationskoeffizienten in bezug auf eine gewisse Ordnung codiert werden muß, etwa für eine Transformationscodierung die Lauflängencodierung und die Vektorquantisierung für sich gegen seitig ausschließende Arten von Mustern ausgewählter Koeffizienten erwünscht sind. Die Lauflängencodierung ist effizient im Fall von Mustern mit langen Läufen nichtausgewählter Koeffizienten, sie ist aber nicht sehr wirkungsvoll zur Codierung von Mustern, die einen erheblichen Anteil ausgewählter Koeffizienten haben. Die Vektorquantisierung ist unerwünscht zur Codierung einer großen Anzahl möglicher Muster, und zwar wegen des großen Speicherbedarfs. Sie ist jedoch vorteilhaft zur Codierung einer relativ kleinen Anzahl möglicher Muster, da bei der statistischen Codierung jedes Muster und damit der Ort jedes ausgewählten Koeffizienten mit einer relativ kleinen Anzahl von Bits bezeichnet werden kann. Bei der Vektorquantisierung spielt es keine Rolle, ob es viele oder wenige ausgewählte Koeffizienten gibt.
Das Gesamtverfahren einer bevorzugten Ausführungsform der Erfindung ist schematisch in den Fig. 13a und 13b gezeigt, wobei Fig. 13a den Codiererteil der Erfindung und Fig. 13b den Decodiererteil zeigt. Wie beim Stand der Technik werden Bilddaten bei 1302 abgetastet, und zwar charakteristisch in Form von Bildelementen über eine Horizontalzeile, wobei viele Horizontalzeilen vertikal angeordnet sind. Die Abtastdaten werden bei 1304 in Blöcke getrennt, beispielsweise in Blöcke von 8 · 8 Bildelementen. Eine Vorwärtstransformation, beispielsweise eine Transformation vom DCT-Typ, wird bei 1306 angewandt. Das Verfahren der Erfindung ist bei praktisch jedem Typ von Transformation anwendbar und nicht auf Transformationen vom DCT-Typ beschränkt. Typischerweise ist es für lineare Transformationen anwendbar, es ist aber ebenso bei jeder Art von Transformation anwendbar, die die Bezeichnung von Ortsinformation umfaßt. Die transformierten Daten sind in Form eines zweidimensionalen Spektrums von Koeffizienten, die jeweils eine kontinuierliche Amplitude haben (von denen einige klein sind) und einen Ort in dem Spektrum haben, hier auch als "Transformationsblock" bezeichnet. Kontinuierliche Amplitude bedeutet hier, daß die Amplitude jeden Wert haben kann und noch nicht in diskrete, quantisierte Pegel "quantisiert" worden ist.
Das Verfahren der Erfindung wirkt charakteristisch auf die Amplitudeninformation getrennt von der Ortsinformation. Diese beiden Informationsarten werden bei 1308 getrennt. Diese Trennung kann mit im Stand der Technik wohlbekannten Mitteln durchgeführt werden. Die kontinuierliche Amplitudeninformation wird bei 1310 zu Rekonstruktionswerten quantisiert, und zwar mit im Stand der Technik wohlbekannten Mitteln. Jeder quantisierten Amplitude wird bei 1312 ein Codewort zugeordnet.
Fig. 9a zeigt schematisch einen Block 112n von Koeffizienten eines transformierten Blocks von Bilddaten 102n. Gemäß der vorliegenden Erfindung wird der Block 112n in Schritt 1314 in zwei Bereiche 902 und 904 aufgetrennt. Der Bereich 902 ist in Fig. 9a von einer stark ausgezogenen Grenzlinie eingeschlossen und umfaßt allgemein den DC-Koeffizienten und bei diesem Beispiel die vierzehn niedrigsten Raumfrequenzkoeffizienten. Der Bereich 904 umfaßt die verbleibenden höherfrequenten Koeffizienten des Blocks 112n. Gemäß einer ersten bevorzugten Ausführungsform des Verfahrens der Erfindung erfolgt die Codierung der Orte der ausgewählten Koeffizienten nach zwei Methoden: Der Bereich 902 wird durch eine Vektorquantisierung codiert, und der Bereich 904 wird durch eine Lauflängencodierung codiert.
Die Codierung des Bereichs 902 folgt dem allgemeinen Verfahren der Vektorquantisierung. Das Muster ausgewählter Koeffizienten wird bei 1316 identifiziert und mit einem Muster in einem Codebuch auf Gleichheit geprüft. Der Bereich 902 umfaßt vierzehn AC-Koeffizienten. Daher ist die Gesamtzahl von Mustern ausgewählter Koeffizienten 2¹&sup4; oder 40.768 mögliche Muster. Dies ist zwar eine große Anzahl von möglichen Mustern, aber die Speicherung einer solchen Anzahl von Beziehungen in dem Codebuch liegt gut im Bereich der Fähigkeiten von praktisch verfügbarer Hardware. Beispielsweise ist zum Speichern dieser Zahl von Mustern, wobei jedes Muster durchschnittlich fünf Bits erfordert, die Gesamtmenge von etwa 5 · 2¹&sup4; Speicherbits sehr praktikabel.
Ebenso wie beim Stand der Technik wird bei 1318 dem Muster ein Codewort zugeordnet, und zwar entweder durch ein Festlängencodewort, wie in Fig. 8 gezeigt ist, oder durch statistische Codierung, die charakteristisch effizientere Resultate liefert. Wenn die Festcodierung angewandt würde, wäre das Codewort vierzehn Bits. Bei Anwendung der statistischen Codierung könnten Codewörter für die Muster hoher Wahrscheinlichkeit nur ein einziges Bit sein, während Codewörter für weniger wahrscheinliche Muster bis zu dreißig oder vierzig Bits sein könnten, was von der gewählten statistischen Codierungstechnik abhängig ist. Typischerweise wird die statistische Codierung gewählt, wenn die Erfahrung gezeigt hat, daß sich für den Bildtyp einige Muster mit einer deutlich höheren Wahrscheinlichkeit als andere ergeben.
Die Codierung des Bereichs 904 folgt der allgemeinen Methode der Lauflängencodierung. Der Bereich 904 umfaßt 49 AC-Koeffizienten. Die Lauflängencodierung beginnt mit dem Ursprung an dem Koeffizienten 906, der durch einen dicken Kreis bezeichnet ist. Die Länge des ersten Laufs wird bei 1320 gemessen. Es kann eine Programmkonvention zugeordnet werden, beispielsweise um Läufe so zu messen, als ob der vorhergehende Lauf an dem letzten AC-Koeffizienten in dem Vektorquantisierungsbereich 902 geendet hätte. Bei dem in Fig. 9a gezeigten Beispiel ist somit die Länge des ersten Laufs Eins, da nur ein ausgewählter Koeffizient in diesem Lauf ist. Bei 1322 wird ein Zwischencodewort zugeordnet, das den Lauf bezeichnet. Beispielsweise könnte zweckmäßig das Codewort "1" zugeordnet werden. Bei 1324 wird das Codewort für den ersten Lauf einer Codefolge hinzugefügt, die sämtliche Läufe in der Bahn bezeichnet. Da dies der erste Lauf ist, ist es das erste Codewort.
Bei 1326 wird eine Bedingung geprüft, um festzustellen, ob die gesamte Zickzackbahn durchlaufen wurde. Wenn nicht, springt das Verfahren zu 1320 zurück und mißt die Länge des nächsten Laufs. Nur drei Koeffizienten (der zweite, fünfte und zehnte) bezeichnen ausgewählte Koeffizienten. Die Länge des zweiten Laufs ist zwei, und die Länge des dritten Laufs ist vier. Ein typisches Codewort für diesen Lauf wäre eine binäre Übersetzung der Folge "1, 2, 4" entsprechend den oben erörterten Techniken, wobei entweder Festlängen-Codewörter oder vorteilhafter längenveränderliche Codewörter verwendet werden. Wenn bei 1322 das zugeordnete Codewort das Codewort ist, das das Ende des Laufs bezeichnet, dann ist bei 1326 das gesamte Zickzackmuster durchlaufen worden, und bei 1326 geht das Verfahren der Erfindung zu Schritt 1328 weiter, in dem die Ortscodewörter kombiniert werden.
Nach dem Verfahren der Erfindung könnte, anstatt die Vektorquantisierung nur bei den ersten vierzehn AC-Koeffizienten entsprechend Fig. 9a anzuwenden, die Vektorquantisierung bei einer davon verschiedenen Anzahl von Koeffizienten wie etwa den ersten zwanzig Koeffizienten angewandt werden, wie schematisch in Fig. 9b gezeigt ist. Der Bereich 908 wird mittels Vektorquantisierung und der Bereich 910 mittels Lauflängencodierung codiert, wobei mit dem Koeffizienten 912 als dem Ursprung begonnen wird.
Für den Vektorquantisierungsteil ist alles gleich wie in dem Beispiel von Fig. 9a mit der Ausnahme, daß 2²&sup0; Muster codiert werden müssen und daher das Codebuch 2²&sup0; Einträge anstatt nur, wie oben erörtert, 214 hat. Es können entweder Festlängen-Codewörter oder eine Codierung auf Entropiebasis angewandt werden.
Für die Lauflängencodierung läuft die Codierung wie in dem Beispiel von Fig. 9a ab. Es werden jedoch weniger Koeffizienten ausgewählt, und daher gibt es weniger Läufe. Da ferner die maximale Lauflänge, die an dem 21. Koeffizienten 912 beginnt, nur 43 und nicht 49 oder 63 ist, können in dem Codebuch weniger Einträge vorhanden sein. Diese Einsparung ist nur bedeutsam, wenn die statistische Codierung angewandt wird. Wenn Festlängen-Codewörter verwendet werden, sind die Längen der Codewörter, die in Fig. 9b und 9a (und im übrigen im Stand der Technik) verwendet werden, gleich, und der Speicherplatz, der dadurch eingespart wird, daß sechs Codewörter weniger im Codebuch vorhanden sind, ist vernachlässigbar.
Nachdem die gesamte Bahn durchlaufen ist und Codewörter zugeordnet wurden, um die Lauflängen zu bezeichnen, werden die Lauflängeninformation und die Vektorquantisierungsinformation bei 1328 kombiniert, um die Orte der ausgewählten Koeffizienten komplett zu bezeichnen. Bei 1330 wird die kombinierte Orts-Codierinformation weiterhin mit der in Schritt 1312 erzeugten Amplitudencodierinformation kombiniert, so daß die Amplituden und Orte des Transformationsblocks 112n vollständig bezeichnet sind. Die speziellen Mittel, mit denen die Ortsinformation bei 1328 kombiniert wird und mit denen die Amplituden- und Ortsinformation bei 1330 kombiniert wird, sind für die Erfindung nicht von Bedeutung. Die Kombination bei 1330 kann jeden Bereich zuerst in einer Zeichenfolge anordnen oder die Lauflängeninformation mit der Amplitudeninformation blockweise verschachteln. Tatsächlich wird überhaupt keine Kombination benötigt, die komplizierter ist als das Übertragen eines Informationstyps, der sequentiell auf einen anderen Informationstyp folgt, solange irgendeine Trenntechnik angewandt wird. Diese Trennung kann mit wohlbekannten Methoden erreicht werden, indem etwa ein Satzzeichencode zwischen Komponenten plaziert wird. Es ist nur erforderlich, daß die Decodierkomponenten der Vorrichtung, die das Verfahren der Erfindung implementiert, eine Einrichtung haben, um zu erkennen, welcher Teil des Datenstroms Amplitudeninformation, welcher Musterinformation und welcher Lauflängeninformation ist. Bei 1332 wird die geeignet kombinierte Codewortinformation auf einem geeignet gewählten Kanal übertragen.
Der Empfangsteil einer bevorzugten Ausführungsform des Verfahrens der Erfindung ist schematisch in Fig. 13b gezeigt. Die Codewörter für einen einzelnen Transformationsblock, wie oben erörtert, werden bei 1350 empfangen. Die Amplitudenkomponenten der Codewörter werden bei 1352 von den Ortskomponenten getrennt. Die Mittel zum Trennen sind von den in Schritt 1330 eventuell verwendeten Kombinationsmitteln abhängig. Bei 1354 werden die Amplituden bezeichnenden Codewörter in eine Serie von quantisierten Amplituden einfach dadurch umgewandelt, daß die Gleichheit der Codewörter mit den Quantisierungspegeln in einem Amplitudencodebuch geprüft wird.
Die Muster- und Lauflängenbereiche (Nieder- und Hochfrequenzbereiche) der Orts-Codewörter werden bei 1356 getrennt. Dieser Schritt kann gleichzeitig mit dem Quantisierungsschritt 1354 stattfinden, oder er kann entweder vor oder nach Schritt 1354 stattfinden. Eine parallele Ausführungsform ist in Fig. 12b gezeigt. Das Mustercodewort wird in ein Muster von Orten bei 1358 unter Bezugnahme auf ein Codebuch umgewandelt, das zu dem in Schritt 1318 verwendeten Codebuch für die Zuordnung von Mustercodewörtern in umgekehrter Beziehung steht. Gleichzeitig (oder anschließend) werden die Lauflängencodewörter bei 1360 in Lauflängen umgewandelt unter Bezugnahme auf das Codebuch, das zu dem Codebuch in umgekehrter Beziehung steht, das zur Codierung der Lauflängen in Schritt 1322 verwendet wird. Die Ortsinformation wird mit der Amplitudeninformation bei 1364 kombiniert, und zwar eventuell, nachdem die Musterinformation und die Lauflängeninformation selber bei 1362 miteinander kombiniert wurden in Abhängigkeit davon, ob diese Ortsinformation in dem Codierteil der Operation kombiniert wurde. Das Ergebnis der Kombination der Amplitudeninformation mit der Ortsinformation ist ein Transformationsblock ähnlich dem Block 112, von dem ausgehend die Daten ursprünglich umgewandelt wurden. Der Unterschied dabei ist, daß die Amplituden in dem ursprünglichen Block 112 kontinuierlich waren, während die Amplituden in dem codierten und decodierten Transformationsblock sämtlich quantisiert sind, d. h. sämtlich in diskreten Rekonstruktionswerten vorliegen, wobei zwischen den Rekonstruktionspegeln keine Amplituden liegen.
Der übertragene und rekonstruierte Transformationsblock wird bei 1366 umgekehrt transformiert, um die Wirkungen der Vorwärtstransformation bei 1306 in der Codierphase aufzuheben. Die umgekehrte Transformation muß mit der Vorwärtstransformation wie etwa einer IDCT auf Gleichheit geprüft werden. Das Ergebnis der umgekehrten Transformation ist ein Block von Intensitäten wie etwa Graustufenintensitäten, die in dem Datenraum des Originalbilds angeordnet sind, der charakteristisch einfach ein räumlicher zweidimensionaler Bildraum ist.
Jeder 8 · 8-Bildelementblock des Originalbilds wird der obigen Codierung, Übertragung und Decodierung unterworfen. Bei 1368 werden die umgekehrt transformierten Blöcke sämtlich zu einem Vollbild in dem typischerweise räumlichen Datenraum des Originalbilds kombiniert. Falls gewünscht, wird das Bild bei 1370 angezeigt.
Gemäß einer zweiten und sehr wichtigen Ausführungsform der Erfindung, die in den Fig. 14a und 14b gezeigt ist, wird der Wirkungsgrad der Lauflängencodierung verstärkt durch Anwendung eines jeweils verschiedenen Codebuchs für verschiedene Läufe in Schritt 1422 (und in Schritt 1460), und zwar in Abhängigkeit von dem Ort des vorher ausgewählten Koeffizienten. Dieser Aspekt des Verfahrens der Erfindung kann als adaptive Lauflängencodierung bezeichnet werden. Die Fig. 14a und 14b zeigen eine Ausführungsform der Erfindung, die nur unter Anwendung der Lauflängencodierung implementiert werden kann. Die gezeigten Schritte sind allgemein die gleichen wie die unter Bezugnahme auf die Fig. 13a und 13b erörterten Lauflängencodierschritte, wobei gleiche Schritte mit Bezugszeichen bezeichnet sind, die mit "14" und nicht mit "13" beginnen. Bei bekannten Lauflängencodierverfahren wird in Schritt 1422 nur ein einziges Codebuch verwendet, um Lauflängen entlang der gesamten Querung der Zickzackbahn Codewörter zuzuordnen. (Der entsprechende Kehrwert dieses Codebuchs wird dann in Schritt 1460 entsprechend dem Stand der Technik verwendet.) Die Wahrscheinlichkeit, daß bestimmte Längen von Läufen auftreten, ändert sich jedoch dramatisch entlang der Bahn. Im dramatischsten Fall, der im Fall eines einzelnen ausgewählten Koeffizienten als dem ersten AC- Koeffizienten der Bahn sehr häufig auftritt, ist der Lauf von 62 unmöglich, nachdem der zweite Koeffizient gequert worden ist. Beispielsweise ist ein Codebuch, das nur auf einem Lauf von 62 als dem Maximallauf basiert, nicht sehr effizient für Läufe, deren maximale Möglichkeit nur 15 ist, weil sie relativ nahe dem Ende des Blocks beginnen. Dieses Prinzip gilt für andere Läufe der Länge = RL, die unmöglich werden, nachdem die erforderliche Anzahl von Koeffizienten durchlaufen wurde, z. B. bei einem Block 112n von 64 Koeffizienten, nachdem 64-RL-Koeffizienten codiert worden sind.
Ein Aspekt des Verfahrens der Erfindung minimiert diese Verschwendung durch Anwendung verschiedener Codebücher in Schritt 1422 (und verschiedener umgekehrter Codebücher in Schritt 1460) in Abhängigkeit von dem Ort des vorher ausgewählten Koeffizienten, d. h. des Ankerpunkts für diesen Teil des Laufs. Beispielsweise wird, wie Fig. 10a zeigt, das in Fig. 5 angewandte Beispiel gezeigt. Der Lauf ist jedoch in drei Laufsegmente unterteilt. Das erste Codebuch wird beginnend an dem DC-Koeffizienten verwendet und quert die ersten vierzehn Koeffizienten und endet an dem vierzehnten AC-Koeffizienten, der mit einem dunklen Kreis 1002 bezeichnet ist. Das zweite Codebuch wird be ginnend an dem auf den Koeffizienten 1002 folgenden Koeffizienten verwendet und quert die nächsten zweiundzwanzig Koeffizienten und endet an dem sechsunddreißigsten AC-Koeffizienten 1004. Das dritte Codebuch wird beginnend an dem Koeffizienten, der auf den Koeffizienten 1004 folgt, und weiter bis zum letzten Koeffizienten verwendet.
Das Zusammensetzen der jeweiligen Codebücher für die drei Segmente ist schematisch in Fig. 11 gezeigt. Der Transformationsblock 112 ist in drei Laufsegmente 1120, 1122 und 1124 wie in Fig. 10a unterteilt. Es ist ein erstes Codebuch 1102 vorgesehen, das 63 Einträge zur Verwendung im Zusammenhang mit Läufen hat, die im Laufsegment 1120 beginnen. Den Lauflängen, deren Auftreten am wahrscheinlichsten ist, wenn der Beginn oder Ankerpunkt eines bestimmten Laufs in das Laufsegment 1120 fällt, sind Codewörter mit relativ wenigen Bits zugeordnet, während den weniger wahrscheinlichen Läufen Codewörter mit relativ vielen Bits zugeordnet sind. (Die in Fig. 11 gezeigten Codebücher dienen nur der Erläuterung und reflektieren keine tatsächlichen Wahrscheinlichkeiten oder ordnungsgemäßen statistischen Codierungen.) Der am wenigsten wahrscheinlichen Lauflänge kann ein Codewort zugeordnet sein, das viel mehr als 64 Bits, beispielsweise 160 Bits hat.
Mit der Querung des Zickzackmusters werden Codewörter aus dem Codebuch 1102 für Läufe der Länge eins, zwei und zehn zugeordnet. Der Code für den Lauf, der am Koeffizienten 1108 endet, stammt aus dem ersten Codebuch 1102, da dieser Lauf im ersten Laufsegment an dem sechsten AC-Koeffizienten begann. Die Wahrscheinlichkeit, daß ein Lauf eine bestimmte Länge hat, basiert auf dem Ort des Koeffizienten, der den Lauf beginnt.
Der Lauf, der am Koeffizienten 1112 endet, hat die Länge null, und es wird somit davon ausgegangen, daß er ebenfalls unmittelbar vor dem Koeffizienten 1112 begonnen hat, der in das zweite Laufsegment 1122 fällt. In Schritt 1426 stellt daher das Verfahren der Erfindung fest, daß das gesamte erste Laufsegment 1120 gequert worden ist, und anstatt eines Rücksprungs zu Schritt 1420 zur Messung der Länge des nächsten Laufs wird zu Schritt 1434 weitergegangen, um festzustellen, ob das gesamte Zickzackmuster gequert worden ist. Da dies nicht der Fall ist, geht das Verfahren zu Schritt 1436 weiter, in dem die Verwendung eines neuen Codebuchs, und zwar nunmehr des Codebuchs 1104, beginnt. Das Verfahren springt dann zu Schritt 1420 zurück und mißt die Länge des Laufs.
Um diesem Lauf der Länge null ein Codewort zuzuordnen, nimmt die das Verfahren der Erfindung ausführende Vorrichtung in Schritt 1422 (Fig. 13a) auf das zweite Codebuch 1104 Bezug. Dieses Codebuch ist auf die gleiche Weise wie das Codebuch 1102 aufgebaut mit der Ausnahme, daß es weniger Einträge hat (fünfzig und nicht dreiundsechzig) und die Codewörter auf der Basis der Wahrscheinlichkeit zugeordnet sind, daß ein Lauf einer bestimmten Länge in den letzten fünfzig Koeffizienten auftritt, anstatt der Wahrscheinlichkeit, daß ein Lauf dieser Länge über den gesamten Block auftritt. Da weniger Einträge vorhanden sind, können die längsten Codewörter aus weniger Bits bestehen als die längsten Codewörter des Codebuchs 1102. Außerdem basiert die Auslegung des Codebuchs auf anderen und zweckmäßigeren Wahrscheinlichkeiten als das Codebuch 1102, wodurch es für den Bereich der Läufe, auf die es angewandt wird, effizienter gemacht wird. Dadurch wird hinsichtlich der Anzahl von Bits, die zur Bezeichnung von Läufen und speziell von unwahrscheinlichen Läufen übertragen werden müssen, eine Einsparung erzielt. Bei dem gezeigten Beispiel ist zwar Läufen der Länge null in beiden Codebüchern 1102 und 1104 das Codewort "0" zugeordnet, dies ist aber nicht erforderlich und ist charakteristisch nicht der Fall.
Wenn der Lauf, der an dem Koeffizienten nach dem Koeffizienten 1114 beginnt, gemessen und codiert wird, wird ebenfalls die Anwendung des Codebuchs 1106 in Schritt 1436 initiiert und in Schritt 1422 implementiert, wobei wiederum weniger Einträge vorgesehen sind und den Läufen mit Längen, die mit den Codebüchern 1104 und 1102 übereinstimmen, andere Wahrscheinlichkeiten zugeordnet sind.
Das Verfahren zum Decodieren der Information ist schematisch in Fig. 14b gezeigt, allerdings nicht so im einzelnen wie das Codierverfahren, das in Fig. 14a gezeigt ist. Die Codewörter werden bei 1450 empfangen und in Amplituden- und Ortskomponenten bei 1452 getrennt. Bei 1460 werden die Codewörter in Lauflängen umgewandelt. Dieser Schritt umfaßt zwei Teilschritte, und zwar die Umkehrung der Schritte 1424 und 1422 von Fig. 14a. Die Codezeichenfolge wird in einzelne Codewörter aufgebrochen, eine Lauflänge wird mit dem bestimmten Code identifiziert. Bei 1476 wird die Codezeichenfolge untersucht, um festzustellen, ob ein neues Codebuch verwendet werden sollte. Die Verwendung eines neuen Codebuchs ist durch einen vorher vereinbarten Code bezeichnet, auf den sowohl der Codierer als auch der Decodierer Zugriff haben. Wenn ein neues Codebuch verwendet werden soll, wird es bei 1478 ausgewählt und bei 1460 angewandt. Wenn nicht, wird bei 1474 ein Test angewandt, um festzustellen, ob der gesamte Lauf decodiert worden ist. Wenn nicht, springt das Decodierverfahren zu 1460 zurück, um die nächste Lauflänge zu decodieren, wobei das gleiche Codebuch wie für die vorhergehende Lauflänge verwendet wird. Wenn der gesamte Lauf decodiert ist, geht das Verfahren weiter zu Schritt 1464, um die Amplituden und die Liste der Frequenzen zu kombinieren und einen Block von Koeffizienten mit Amplituden zu erzeugen, die bei 1466 umgekehrt transformiert, bei 1468 kombiniert und bei 1470 gespeichert oder angezeigt werden.
Es versteht sich, daß die Implementierung dieser Ausführungsform des Verfahrens der Erfindung den Einsatz von mehr Speicher erfordert, um die zusätzlichen Codebücher zu speichern. Die Anzahl der eingesetzten Codebücher hängt von den relativen Begrenzungen der speziellen Anwendung in bezug auf Speicher und Bandbreite des Kommunikationskanals ab.
Das Vielfach-Codebuchverfahren der Erfindung kann vorteilhaft nur mit Lauflängencodierung angewandt werden, wie oben erläutert wird. Es kann auch mit der Kombination aus Vektorquantisierungs/Lauflängencodierungs-Verfahren der Erfindung, die oben erörtert wird, verwendet werden, um einen höheren Wirkungsgrad gegenüber dem Stand der Technik, der angegebenen Kombination aus Lauflängecodierung und Vektorquantisierung und der Anwendung des Vielfach-Codebuchverfahrens mit nur Lauflängencodierung zu erzielen. Diese Kombination ist in Fig. 10b schematisch gezeigt, wobei der Transformationsblock 112n erneut in den Vektorquantisierungsbereich 902 und den Lauflängencodierbereich 904 unterteilt ist. Der Lauflängenbereich 904 ist selber in drei Segmente 1030, 1032 und 1034 unterteilt, und die Grenzen zwischen diesen sind stark ausgezogen und haben einen dunklen Kreis entlang der Zickzackbahn am Beginn jedes Segments. Die Längen von Läufen, die in jedem entsprechenden Segment beginnen, werden in Schritt 1322 auf der Basis eines unabhängigen Codebuchs für jeden dieser Abschnitte codiert, wie oben erläutert wurde.
Das Verfahren der Erfindung ergibt auch ohne Vielfach-Codebücher in einem typischen Fall eine verbesserte Gesamtbitrate je übertragenem Koeffizienten gegenüber der Lauflängencodierung und verbesserte Speicher- und Berechnungsanforderungen gegenüber der Vektorquantisierung. Die Implementierung des Vielfachcodebuch-Aspekts der Erfindung verbessert weiterhin die Bitrate gegenüber der herkömmlichen Lauflängencodierung.
Die Vorrichtung der Erfindung ist schematisch in den Fig. 12a und 12b gezeigt. Fig. 12a zeigt den Codiererteil der Vorrichtung, und Fig. 12b zeigt den Decodiererteil. Ein Bild wird in abgetastete zweidimensionale Quellbilddaten 1202 umgewandelt. Die Quellbilddaten werden in Blöcke aufgeteilt, und zwar charakteristisch 8 · 8 Abtastwerte in jedem Block. Die Quellbilddaten werden blockweise einem Vorwärtstransformationsoperator 1204 zugeleitet. Bei einer typischen Transformation wie etwa DCT sind die Daten in einem 8 · 8-Block eines zweidimensionalen Frequenzbereichs, wobei jedes Element des 8 · 8-Blocks eine kontinuierliche Amplitude einer diskreten räumlichen Frequenz darstellt.
Verschiedene Komponenten der Daten werden in den folgenden Stufen der Vorrichtung behandelt. Die Amplitude wird in einem Amplitudenquantisierer 1206 behandelt, und die Positionsinformation (entsprechend der räumlichen Frequenz jeder Amplitude) wird in einem Vektormustercodierer 1212 und einem Lauflängencodierer 1214 behandelt. Es ist für die Erfindung nicht kritisch, welches Modul die Daten zuerst empfängt oder ob die Daten in Serie oder parallel empfangen werden, obwohl die parallele Behandlung schneller ist. Die in Fig. 12a gezeigte Ausführungsform ist nach einer parallelen Architektur angeordnet.
Das Signal wird in Amplitude und zwei Positionskomponenten an einem Multiplexer-Separator 1205 aufgetrennt. Die kontinuierlichen Amplituden werden von einem Amplitudenquantisierer 1206 in diskrete Rekonstruktionswerte quantisiert, die in einem Amlitudenrekonstruktionspegel-Tabellenspeicher 1208 gespeichert sind. Der Amplitudenquantisierer 1206 ordnet jedem Koeffizienten ein Codewort unter Bezugnahme auf einen Amplitudencodebuchspeicher 1207 zu, der ein Codewort mit jedem Rekonstruktionspegel korreliert, der in dem Rekonstruktionspegel-Tabellenspeicher 1208 gehalten ist. Der Ausgangswert des Amplitudenquantisierers 1206 ist ein Block von Codewörtern, die quanti sierte Amplituden darstellen, wobei jede Amplitude einer bestimmten räumlichen Frequenz entspricht.
Die Positionsdaten von dem Multiplexer 1205 können an einem zweiten Separator 1203 weiter in niedrige Raumfrequenz- und hohe Raumfrequenzkomponenten aufgeteilt werden. Der Niederfrequenzbereich des Blocks wird von dem Vektormustercodierer 1212 analysiert. Der Codierer prüft die Gleichheit des Musters von ausgewählten Koeffizientenorten mit Mustern, die in einem Vektormustertabellenspeicher 1216 gespeichert sind. Die Vektormustertabelle setzt jedes Muster in ein Codewort um. Das Codewort kann ein Codewort gleichförmiger Länge oder, was typischer ist, ein längenveränderliches Codewort sein, das nach einer geeigneten Entropiecodierungstechnik erstellt ist. Wenn die Wahrscheinlichkeiten der Muster bestimmt werden können, ergibt typischerweise die Entropiecodierung eine effizientere Gesamtkoeffizientenbitrate als Codewörter gleichförmiger Länge. Unabhängig davon, ob gleichförmige Codierung oder Entropiecodierung verwendet wird, wird eine Vektormustertabelle benötigt, um die Koeffizientenmuster in die Codewörter umzusetzen.
Die Daten für den höheren Frequenzbereich des Blocks werden von dem Positionslauflängencodierer 1214 analysiert. Der Lauflängencodierer 1214 quert die Zickzackbahn durch die Koeffizienten und zählt die Anzahl von nichtausgewählten Koeffizienten zwischen ausgewählten Koeffizienten, wodurch die Längen jedes Laufs zwischen ausgewählten Koeffizienten festgelegt werden. Nach der Messung prüft der Lauflängencodierer 1214 die Gleichheit jeder Länge mit einem Codewort unter Bezugnahme auf ein im Speicher 1218a gespeichertes Lauflängencodebuch. Wiederum können entweder Festlängencodewörter oder längenveränderliche Codewörter verwendet werden in Abhängigkeit von der Auswertung des Speichers und den Überlegungen hinsichtlich der Bandbreite, wie oben erörtert wurde. Wenn die statistische bzw. Entropiecodierung verwendet wird und wenn das Vielfachccdebuchverfahren der Erfindung angewandt wird, dann nimmt der Lauflängencodierer 1214 auf Codebücher 2 bis n Bezug, die in zusätzlichen Speichern 1218b bis 1218n gespeichert sind. Die Ortscodewörter von dem Vektormustercodierer 1212 und dem Positionslauflängencodierer 1214 können fakultativ an einem Multiplexer 1209 kombiniert werden. Dieser Vereinigungsschritt ist nicht notwendig, er kann aber in einigen Situationen zu verbesserten Wirkungsgraden führen. Die Kombination kann ganz einfach sein, wobei die Codewörter in einer bestimmten Reihenfolge verkettet werden. Die quantisierten codierten Amplitudendaten werden mit den codierten Vektorquantisierungsdaten und den codierten Lauflängendaten im Multiplexer 1220 kombiniert, und es wird ein Strom von komprimierten Bilddaten 1222 erzeugt.
Die komprimierten Bilddaten 1222 werden von der schematisch in Fig. 12b gezeigten Vorrichtung in ein rekonstruiertes Bild umgewandelt. Die komprimierten Bilddaten 1222 werden in ihre codierten Amplituden- und Ortskomponenten von einem Demultiplexer aufgeteilt. Die Ortsinformation wird, wenn sie an dem Multiplexer 1209 kombiniert wurde, in Vektorquantisierungs- und Lauflängenkomponenten von einem Multiplexer 1229 getrennt. Wenn in dem Codierteil der Vorrichtung keine Kombination durchgeführt wird, wird jede Komponente einfach zu ihrem jeweiligen Decodierer 1232 oder 1234 geleitet. Der Vektormusterdecodierer 1232 empfängt jedes Vektorcodewort und prüft die Gleichheit des Codeworts mit einem Muster unter Bezugnahme auf den Vektormustertabellenspeicher 1236, der mit dem Vektormustertabellenspeicher 1216 identisch sein kann. Dadurch, daß die Vektormustertabelle 1216 durchsucht werden muß, um Muster auf Gleichheit zu prüfen, und der Vektormustertabellenspeicher 1236 durchsucht werden muß, um einfach Codewörter auf Gleichheit zu prüfen, ist jedoch die Anordnung der Daten in den beiden Speichern häufig verschieden, um die Suchverfahren in jedem zu optimieren. Der Ausgangswert des Musterdecodierers 1232 ist ein Muster von Orten für ausgewählte Koeffizienten. Die Amplituden dieser Koeffizienten werden jedoch von dem Musterdecodierer 1232 nicht festgestellt.
Der Lauflängendecodierer 1234 empfängt jedes Lauflängencodewort und prüft die Gleichheit des Codeworts mit einer Lauflänge unter Bezugnahme auf den Lauflängencodebuchspeicher 1238a. Der Lauflängendecodierer verwendet entweder Festlängen- oder längenveränderliche Codewortdecodierung (unter Verwendung zusätzlicher Codebücher 2 bis n, die in Speichern 1238b bis 1238n gespeichert sind) entsprechend der Technik, die in dem Codierteil des Systems angewandt wird.
Der Amplitudenteil des komprimierten Bilddatenstroms 1222 wird von dem Amplitudendecodierer 1246 unter Bezugnahme auf einen Amplitudencodebuchspeicher 1247 decodiert. Die Einträge in dem Amplitudencodebuchspeicher 1247 passen die Codewörter an die entsprechenden Rekonstruktionswerg analog zu der Umsetzung im Amplitudencodebuchspeicher 1207 an. Die präzisen kontinuierlichen Amplituden der Koeffizienten, wie sie in den Amplitudenquantisierer 1206 eingegeben wurden, können jedoch nicht rückgewonnen werden, weil die Änderungen innerhalb von Rekonstruktionswerten nicht bewahrt wurden, da nur die Zugehörigkeit in einem Rekonstruktionswert aufgezeichnet wurde. Aus diesem Grund (unter anderen, weniger wichtigen Gründen) sind die rekonstruierten Bilddaten nicht exakt gleich wie die Quellbilddaten. Es ist das Ziel von Signalverarbeitungstechniken, die wahrnehmbaren Unterschiede in dem Bild ungeachtet der unvermeidbaren Differenz in den Bilddaten zu minimieren.
An dem Ortsdecodierer 1233 werden die decodierten Ortskomponenten der transformierten Blockdaten, die vom Vektormusterdecodierer 1232 und vom Positionslauflängendecodierer 1234 abgegeben werden, kombiniert, um sämtliche der ausgewählten Positionen in dem transformierten Block zu bezeichnen. An einem Orts- und Amplitudenanpasser 1245 werden die kombinierten Po sitionen auf Gleichheit mit den jeweiligen Amplituden, die von dem Amplitudendecodierer 1246 erzeugt werden, in bezug auf die Orte von ausgewählten Koeffizienten geprüft. Das Ergebnis ist ein transformierter Block, z. B. 8 · 8 bei dem in den Figuren verwendeten Beispiel, von Koeffizienten in den Raumfrequenz-Orten des ursprünglichen Blocks 112n, und zwar mit quantisierten Amplituden. Dieser transformierte 8 · 8-Block wird als Eingang zu dem umgekehrten Transformationsoperator 1244 genutzt, der die Daten von dem Raumfrequenzbereich in den zweidimensionalen Bildbereich transformiert.
Die vorstehende Vorrichtungsbeschreibung richtet sich auf den Durchlauf von Daten, die einen Block 102n von Bildelementdaten repräsentieren, durch die Vorrichtung. Jeder Block 102n von Bildelementdaten durchläuft die Vorrichtung auf die gleiche Weise. Die Vielzahl von rekonstruierten 8 · 8-Blöcken von Bildelementdaten wird rekombiniert (im allereinfachsten Fall einfach dadurch, daß sie nebeneinander in einer Reihenfolge plaziert werden, die der Reihenfolge entspricht, in der sie gebildet wurden), um ein rekonstruiertes Bild 1252 zu bilden.
Bei der Auswahl der Koeffizienten kann anstelle eines festgelegten Schwellenwerts ein veränderlicher Schwellenwert verwendet werden. Ein veränderlicher Schwellenwert wird typischerweise aus zwei Gründen verwendet. Erstens können für verschiedene Blöcke verschiedene Schwellenwerte verwendet werden. Zweitens werden innerhalb desselben Blocks die niederfrequenten Koeffizienten besser unter Verwendung eines niedrigeren Schwellenwerts codiert, und zwar aus wohlbekannten Gründen, die auf den menschlichen Wahrnehmungsmechanismus bezogen sind.
In der vorstehenden Erläuterung wird von einem Bild ausgegangen, das durch Bildelementamplituden entsprechend einer Grauskala charakterisiert ist, also von einem Schwarzweißbild. Die Erfindung ist auch bei Farb- oder Multikanalbildern anwendbar.
Im Fall von Schwarzweißaufzeichnungen von Bildern ist jedes Bildelement ein einzelnes diskretes Element. Im Fall von Farbaufzeichnungen wird für jedes Bildelement eine Gruppe von Kanälen oder Gruppe von Bildelementen verwendet. Beispielsweise in einem Farbwertschema, das als RGB bekannt ist, wird jede Farbe durch eine Kombination von Mengen der Farben rot (R), grün (G) und blau (B) repräsentiert. Ein separater Farb-"Kanal" für jede dieser drei Farben ist vorgesehen. In dem RGB-System hat jeder Kanal die gleiche Anzahl von Bildelementen je Zeile über ein Bild (beispielsweise auf einem Videobildschirm) und die gleiche Anzahl Zeilen in einer Vertikalrichtung. Andere Farbwertsysteme, die nachstehend erörtert werden, können eine davon verschiedene Anzahl von Abtastungen pro Zeile für verschiedene Kanäle haben. Die Bildelemente befinden sich charakteristisch einander benachbart auf der Displayeinrichtung, so daß sie dann, wenn sie gleichzeitig (wie vom Betrachter gesehen) angezeigt werden, sich vereinigen, um die Farben des Originalbilds zu bilden.
Das RGB-Farbwertschema ist für bestimmte Anwendungen brauchbar, es ist aber für die mathematische Manipulation von Farbwerten nicht am zweckmäßigsten. Andere Farbschemata sind nützlicher, und zwar typischerweise diejenigen, die einen Kanal aufweisen, der die Leuchtdichtewerte des Bilds repräsentiert. Die Leuchtdichte wird allgemein als die Intensität von Licht beschrieben, das von einer Oberfläche in einer gegebenen Richtung pro scheinbarer Flächeneinheit emittiert oder reflektiert wird. Im allgemeinen sind ein Dreikanalfarbraum, der durch Leuchtdichte definiert ist, und zwei weitere Dimensionen dem RGB-Farbraum äquivalent. Ein typischer Leuchtdichtefarbraum ist der Y(Leuchtdichte)-, i(kohärent)-, q(Quadratur)-Farbraum, der von dem National Television Standards Committee für Fernsehsendungen in den USA verwendet wird. Andere Leuchtdichtefarbräume umfassen den Y,x,y (Leuchtdichte und zwei Farbwertkanäle) der Commission International de 1'Eclairage (CIE) und seine Varianten, und Y,u,v (ebenfalls Leuchtdichte und zwei Farbwertkanäle) und viele andere.
In Verbindung mit der vorliegenden Erfindung kann das Verfahren der Erfindung vorteilhaft an jedem unabhängigen Kanal eines Multikanalsystems praktiziert werden. Die Daten für jeden Kanal werden separat verarbeitet und nach Codierung und Decodierung mit bekannten Techniken rekombiniert. So kann es vorteilhaft sein, den Vielfachcodebuch-Aspekt der Erfindung anzuwenden, wobei verschiedene Codebücher für einen Kanal im Vergleich mit einem anderen Kanal verwendet werden. Ferner kann die Grenze zwischen der Anwendung des Vektorquantisierungsverfahrens und des Lauflängenverfahrens für jeden gegebenen Block von einem Kanal zu einem anderen verschieden sein. Beispielsweise kann für Farbwertkanäle der Bereich für die Vektorquantisierung viel kleiner sein, weil charakteristisch weniger Koeffizienten zur Codierung in den Farbwertkanälen ausgewählt werden. Tatsächlich ist es nicht erforderlich, überhaupt das gleiche Verfahren von einem Kanal zum nächsten anzuwenden. Die Vektorquantisierung in Kombination mit Lauflängencodierung unter Verwendung von Vielfachcodebüchern könnte für einen Kanal angewandt werden, während ein anderer Kanal codiert wird, indem nur die Lauflängencodierung mit Vielfachcodebüchern angewandt wird, ohne daß die Vektorquantisierung überhaupt angewandt wird.
Die vorstehende Erläuterung beschreibt die Erfindung in bezug auf zweidimensionale Daten vom Bildtyp. Sie ist ebenfalls zur Verarbeitung von Signalen in drei oder mehr Dimensionen anwendbar. Signale dieser Art umfassen Videosignale, bestimmte Arten von Schall- und Radarsignalen, Signale, die dreidimensionale physische Szenen beschreiben wie etwa Hologramme und Festkörpermodelle, usw. Weitere Signale, die physische Eigenschaften wie etwa die Temperatur, das elektrische Feld, das Magnetfeld, die Dichte, die Farbe usw. von dreidimensionalen Einheiten (wie etwa Gebäuden, Tieren, Landschaften) bezeichnen, können in Datenräumen beschrieben werden, die so viele über drei hinausgehende Dimensionen haben, wie physische Eigenschaften angegeben sind. Die Prinzipien sind die gleichen, wobei nur zusätzliche Dimensionen betroffen sind.
Bei Betrachtung einer dreidimensionalen Ausführungsform sind die Quelldaten in drei Dimensionen wie etwa den drei Raumdimensionen vorhanden, wobei eine Intensitätsamplitude für jeden Punkt im dreidimensionalen Raum vorhanden ist. Diese dreidimensionalen Daten werden beispielsweise nach einer Transformation vom DCT-Typ in einen Datenraum transformiert, der durch Koeffizienten in drei räumlichen Frequenzdimensionen charakterisiert ist, wobei jeder Koeffizient eine Amplitude hat. Die Quelldaten werden in dreidimensionalen Klötzen in den Transformationsraum umgewandelt und nicht in zweidimensionalen Blöcken eines zweidimensionalen Systems. Ebenso werden die Daten in dem transformierten Frequenzbereich in dreidimensionalen Klötzen gehandhabt.
Die Identifikation der Orte in dem transformierten Klotz ausgewählter Koeffizienten ist die gleiche wie in zwei Dimensionen mit der Ausnahme, daß es viel mehr mögliche Kombinationen möglicher Muster in bezug auf eine Vektorquantisierung gibt und das Zickzackmuster in drei Dimensionen gequert wird und eine Spiralgestalt annehmen kann, die von dem DC-Koeffizienten ausgeht. Es ist zu beachten, daß weder die Zickzackbahn noch eine spiralförmige Bahn sakrosankt ist. Andere geeignete Bahnen liegen im Bereich der Erfindung.
Die vorstehende Erläuterung versteht sich als erläuternd und in keiner Weise als einschränkend. Die Erfindung wird zwar speziell unter Bezugnahme auf bevorzugte Ausführungsbeispiele gezeigt und beschrieben, für den Fachmann ist jedoch ersichtlich, daß verschiedene Änderungen hinsichtlich Form und Einzelheiten vorgenommen werden können, ohne vom Geist und Umfang der Erfindung gemäß der Definition in den Ansprüchen abzuweichen.
Beispielsweise können anstelle von zweidimensionalen Bilddaten irgendwelche anderen zweidimensionalen Daten gemäß der Erfindung behandelt werden, was das bewegungskompensierte Restsignal einschließt. Der Vielfach- oder adaptive Codebuchlauflängencodier-Aspekt der Erfindung kann entweder alleine oder zusammen mit dem Aspekt der Erfindung angewandt werden, der die Vektorquantisierung und die Lauflängencodierung kombiniert, die ebenso ohne den Vielfachcodebuch-Aspekt der Erfindung angewandt werden kann. Jede Anzahl von Vielfachcodebüchern anstatt der drei, die typischerweise in den Beispielen verwendet werden, kann verwendet werden.
In den erläuterten Beispielen, die sich auf Bilddaten konzentrieren, wird die Vektorquantisierung für die niedrigen Raumfrequenzen angewandt, während die Lauflängencodierung für die hohen Frequenzen angewandt wird. Wenn jedoch der Datentyp am häufigsten durch lange Läufe von nichtausgewählten Koeffizienten in dem niedrigen oder einem anderen Frequenzbereich charakterisiert ist, dann sollte die Lauflängencodierung anstelle der Vektorquantisierung angewandt werden, um dieses Segment des Transformationsblocks zu codieren. Ebenso sollte die Vektorquantisierung angewandt werden, um Teile des Blocks mit relativ kurzen Läufen zu codieren. Anstatt Lauflängen- und Vektorquantisierungs-Codierungsmethoden anzuwenden, umfaßt die Erfindung ferner die Aufteilung des Transformationsblocks in Bereiche und die Anwendung einer Codiertechnik auf jeden Bereich, wobei diese Technik in bezug auf das Muster von ausgewählten Koeffizienten, die in diesem Bereich häufig sind, wirksam ist. Somit wird an die Anwendung anderer Codiertechniken im Rahmen der Erfindung gedacht, wenn die erzielten Vorteile das rechtfertigen.
Ferner wurde die Erfindung zwar in bezug auf die Codierung der Ortsinformation hinsichtlich ausgewählter oder nichtausgewählter Koeffizienten in Abhängigkeit von ihren Amplituden beschrieben, die Erfindung kann aber bei jeder Codiertechnik angewandt werden, bei der bestimmte Elemente einer geordneten Gruppe von Elementen nach Maßgabe irgendwelcher Kriterien ausgewählt sind und die Ortsinformation in bezug auf das Ordnungsprinzip verlangt wird. Die Erfindung bezieht sich nur auf die Bezeichnung der Ortsinformation. Tatsächlich bezieht sich die Erfindung auch auf die Angabe von Ortsinformation, selbst wenn keine Amplitudeninformation betroffen ist.

Claims

1. Verfahren zum Codieren von Ortsinformation, die ein Quellpositionssignal (112n) betrifft, das zum Teil durch Positionen eines Sets von ausgewählten Koeffizienten definiert ist, die in wenigstens einer Dimension geordnet sind, wobei ein allgemein erwartetes Muster von ausgewählten Koeffizienten in diesem Quellsignal vorhanden ist, wobei das Verfahren die folgenden Schritte aufweist:

a. für eine erste Komponente (902) des Positionssignals (112n), Erzeugen eines Signals, das die Orte der ausgewählten Koeffizienten mittels einer ersten Methode codiert, die einen ersten Wirkungsgrad in bezug auf das allgemein erwartete Muster von ausgewählten Koeffizienten in der ersten Komponente (902) hat; und

b. für eine zweite Komponente (904) des Positionssignals (112n), Erzeugen eines Signals, das die Orte der ausgewählten Koeffizienten mittels einer zweiten Methode codiert, die einen zweiten Wirkungsgrad in bezug auf das allgemein erwartete Muster von ausgewählten Koeffizienten in der zweiten Komponente (904) hat,

wobei der zweite Wirkungsgrad höher als der Wirkungsgrad der ersten Methode in bezug auf das allgemein erwartete Muster von ausgewählten Koeffizienten in der zweiten Komponente ist und wobei der erste Wirkungsgrad höher als der Wirkungsgrad der zweiten Methode in bezug auf das allgemein erwartete Muster von ausgewählten Koeffizienten in der ersten Komponente ist.

2. Verfahren zum Codieren von Ortsinformation nach Anspruch 1, wobei:

a. eine von der ersten und der zweiten Methode zum Erzeugen eines Signals, das die Orte der ausgewählten Koef fizienten codiert, weist eine Methode (1316) auf, die die Orte zu einem Muster in wenigstens einer Dimension gruppiert; und

b. die andere von der ersten und der zweiten Methode zum Erzeugen eines Signals, das die Orte der ausgewählten Koeffizienten codiert, weist eine Methode (1320) auf, die die Distanz zwischen den Orten von ausgewählten Koeffizienten mißt.

3. Verfahren zum Codieren von Ortsinformation nach Anspruch 2, wobei:

a. die Methode (1316), die die Orte zu einem Muster in wenigstens einer Dimension gruppiert, Vektorquantisierung aufweist; und

b. die Methode (1320), die die Distanz zwischen den Orten von ausgewählten Koeffizienten mißt, Lauflängencodierung aufweist.

4. Verfahren nach Anspruch 3, wobei der Schritt des Erzeugens eines Signals durch Lauflängencodierung die folgenden Schritte aufweist:

a. für ein erstes Laufsegment der zweiten Komponente des Positionssignals, Codieren (1420) der Orte der ausgewählten Koeffizienten unter Verwendung eines ersten Codebuchs (1218a); und

b. für wenigstens ein zusätzliches Segment der zweiten Komponente des Positionssignals, Codieren (1420) der Orte der ausgewählten Koeffizienten unter Verwendung (1436) von wenigstens einem zusätzlichen Codebuch (1218b).

5. Verfahren nach Anspruch 1, wobei:

a. die erste Methode zum Erzeugen eines Signals zum Codieren der Orte ausgewählten Koeffizienten die Lauflängecodierung (1420) unter Verwendung eines ersten Codebuchs (1218a) aufweist; und

b. die zweite Methode zum Erzeugen eines Signals zum Codieren der Orte der ausgewählten Koeffizienten die Lauflängencodierung (1420) unter Verwendung von wenigstens einem zusätzlichen Codebuch (1218b) aufweist.

6. Verfahren zum Decodieren eines Signals, das ein Quellpositionssignal (112n) codiert, das zum Teil durch Positionen eines Sets von ausgewählten Koeffizienten, die in wenigstens einer Dimension geordnet sind, definiert ist, wobei ein allgemein erwartetes Muster von ausgewählten Koeffizienten in dem Quellsignal vorhanden ist und wobei das Codiersignal durch die folgenden Schritte erzeugt worden ist: für eine erste Komponente des Positionssignals (112n), Erzeugen eines Signals zum Codieren der Orte der ausgewählten Koeffizienten nach einer ersten Methode, die einen ersten Wirkungsgrad in bezug auf das allgemein erwartete Muster von ausgewählten Koeffizienten in der ersten Komponente hat; und für eine zweite Komponente des Positionssignals (112n), Erzeugen eines Signals, das die Orte der ausgewählten Koeffizienten nach einer zweiten Methode codiert, die einen zweiten Wirkungsgrad in bezug auf das allgemein erwartete Muster von ausgewählten Koeffizienten in der zweiten Komponente hat,

wobei der zweite Wirkungsgrad höher als der Wirkungsgrad der ersten Methode in bezug auf das allgemein erwartete Muster von ausgewählten Koeffizienten in der zweiten Komponente ist und wobei der erste Wirkungsgrad höher als der Wirkungssgrad der zweiten Methode in bezug auf das allgemein erwartete Muster von ausgewählten Koeffizienten in der ersten Komponente ist,

wobei das Codierverfahren die folgenden Schritte aufweist:

a. Decodieren (1358, 1360) des die Orte codierenden Signals, das durch die erste Methode erzeugt wurde; und

b. Decodieren (1358, 1360) des die Orte codierenden Signals, das durch die zweite Methode erzeugt wurde.

7. Verfahren zum Decodieren eines Signals, das ein Quellpositionssignal codiert, nach Anspruch 6, wobei das Codiersignal durch die folgenden Schritte erzeugt worden ist: für eine von der ersten (902) und der zweiten (904) Komponente des Positionssignals (112n), Erzeugen eines Signals, das die Orte der ausgewählten Koeffizienten nach einer Methode (1316) codiert, die die Orte zu einem Muster in wenigstens einer Dimension gruppiert; und für die andere von der ersten und der zweiten Komponente des Positionssignals, Erzeugen eines Signals, das die Orte der ausgewählten Koeffizienten nach einer Methode (1320, 1420) codiert, die die Distanz zwischen den Orten ausgewählter Koeffizienten mißt, wobei das Decodierverfahren die folgenden Schritte aufweist:

a. Decodieren (1358) des die Orte codierenden Signals, das nach der Methode erzeugt wurde, die die Orte zu einem Muster in wenigstens einer Dimension gruppiert; und

b. Decodieren (1360) des die Orte codierenden Signals, das nach der Methode erzeugt wurde, die die Distanz zwischen den Orten ausgewählter Koeffizienten mißt.

8. Verfahren zum Decodieren eines Signals, das ein Quellpositionssignal codiert, nach Anspruch 7, wobei die Methode (1316), die die Orte zu einem Muster in wenigstens einer Dimension gruppiert, Vektorquantisierung aufweist; und

wobei die Methode (1320, 1420), die die Distanz zwischen den Orten ausgewählter Koeffizienten mißt, Lauflängencodierung aufweist; wobei das Decodierverfahren die folgenden Schritte aufweist:

a. Decodieren (1360) des die Orte der ausgewählten Koeffizienten codierenden Signals, das durch Lauflängencodierung erzeugt wurde; und

b. Decodieren (1358) des die Orte der ausgewählten Koeffizienten codierenden Signals, das durch Vektorquantisierung erzeugt wurde.

9. Decodierverfahren nach Anspruch 8, wobei der Schritt der Lauflängencodierung (1420) ferner die folgenden Schritte umfaßt: für ein erstes Laufsegment (1122) der zweiten Komponente (904) des Positionssignals, Codieren der Orte der ausgewählten Koeffizienten unter Verwendung eines ersten Codebuchs (1218x); und für wenigstens ein zusätzliches Segment (1124) der zweiten Komponente (904) des Positionssignals, Codieren der Orte der ausgewählten Koeffizienten unter Verwendung (1436) wenigstens eines zusätzlichen Codebuchs (1218b), wobei das Decodierverfahren ferner die folgenden Schritte aufweist:

a. Decodieren (1460) der Orte, die unter Verwendung eines ersten Codebuchs (1218x) codiert wurden, unter Verwendung eines ersten Umkehr-Codebuchs (123%); und

b. Decodieren (1460) der Orte, die unter Verwendung (1478) eines zweiten Codebuchs (1218b) codiert wurden, unter Verwendung (1478) eines zweiten Umkehr-Codebuchs (1238b).

10. Decodierverfahren nach Anspruch 6, wobei das Codiersignal durch die Schritte erzeugt worden ist: für eine erste Kom ponente (1122) des Positionssignals (112n), Erzeugen eines die Orte der ausgewählten Koeffizienten codierenden Signals unter Verwendung von Lauflängencodierung mit einem ersten Codebuch (1218x); und für eine zweite Komponente (1124) des Positionssignals (112n), Erzeugen eines die Orte der ausgewählten Koeffizienten codierenden Signals unter Anwendung von Lauflängencodierung mit wenigstens einem zusätzlichen Codebuch (121%), wobei das Decodierverfahren die folgenden Schritte aufweist:

a. Decodieren (1460) der unter Verwendung eines ersten Codebuchs (1218x) codierten Orte unter Verwendung eines ersten Umkehr-Codebuchs (1238a); und

b. Decodieren (1460) der unter Verwendung eines zweiten Codebuchs (1218b) codierten Orte unter Verwendung (1478) eines zweiten Umkehr-Codebuchs (1238b).

11. Einrichtung zum Codieren von Ortsinformation, die ein Quellpositionssignal (112n) betrifft, das zum Teil durch Positionen eines Sets von ausgewählten Koeffizienten, die in wenigstens einer Dimension geordnet sind, definiert ist, wobei in dem Quellsignal ein allgemein erwartetes Muster von ausgewählten Koeffizienten vorhanden ist, die in wenigstens einer Dimension geordnet sind, wobei die Einrichtung folgendes aufweist:

a. einen Lauflängencodierer (1214) zum Codieren der Orte der ausgewählten Koeffizienten; und

b. mit dem Lauflängencodierer (1214) verbunden sind:

i. ein erster Codebuch-Speicher (1218a) zum Codieren der Orte der ausgewählten Koeffizienten in einem ersten Laufsegment (1122) des Positionssignals (112n); und

ii. wenigstens ein zusätzlicher Codebuch-Speicher (1218b) zum Codieren der Orte der ausgewählten Koeffizienten in wenigstens einem zusätzlichen Laufsegment (1124) des Positionssignals (112n),

wobei der Codierwirkungsgrad eines in dem ersten Codebuch- Speicher gespeicherten Codebuchs höher als der Codierwirkungsgrad von jeweils in den zusätzlichen Codebuch-Speichern gespeicherten zusätzlichen Codebüchern in bezug auf das allgemein erwartete Muster von ausgewählten Koeffizienten in dem ersten Laufsegment ist, und wobei der Codierwirkungsgrad der in den zusätzlichen Codebuch-Speichern gespeicherten zusätzlichen Codebücher höher als der Codierwirkungsgrad des in dem ersten Codebuch-Speicher gespeicherten Codebuchs in bezug auf das allgemein erwartete Muster ausgewählter Koeffizienten in den zusätzlichen Laufsegmenten ist.

12. Einrichtung zum Codieren von Ortsinformation, die ein Quellpositionssignal (112n) betrifft, das zum Teil durch Positionen eines Sets von ausgewählten Koeffizienten, die in wenigstens einer Dimension geordnet sind, definiert ist, wobei in dem Quellsignal ein allgemein erwartetes Muster ausgewählter Koeffizienten vorhanden ist, die in wenigstens einer Dimension geordnet sind, wobei die Einrichtung folgendes aufweist:

a. einen Vektorquantisierer (1212) zum Erzeugen eines Signals a um Codieren der Orte der ausgewählten Koeffizienten in einer ersten Komponente (902) des Positionssignals (112n) und

b. einen Lauflängencodierer (1214) zum Codieren der Orte der ausgewählten Koeffizienten in einer zweiten Komponente (904) des Positionssignals (112n),

wobei der Codierwirkungsgrad des Vektorquantisierers höher als der Codierwirkungsgrad des Lauflängencodierers in bezug auf das allgemein erwartete Muster ausgewählter Koeffizienten in der ersten Komponente ist und wobei der Codierwirkungsgrad des Lauflängencodierers höher als der Codierwirkungsgrad des Vektorquantisierers in bezug auf das allgemein erwartete Muster ausgewählter Koeffizienten in der zweiten Komponente ist.

13. Einrichtung zum Decodieren eines Signals, das ein Quellpositionssignal (112n) codiert, das zum Teil durch Positionen eines Sets von ausgewählten Koeffizienten definiert ist, die in wenigstens einer Dimension geordnet sind, wobei in dem Quellsignal ein allgemein erwartetes Muster ausgewählter Koeffizienten vorhanden ist, wobei das Codiersignal durch die folgenden Schritte erzeugt worden ist: für eine erste Komponente des Positionssignals, Erzeugen eines die Orte der ausgewählten Koeffizienten codierenden Signals nach einer ersten Methode, die einen ersten Wirkungsgrad in bezug auf das allgemein erwartete Muster ausgewählter Koeffizienten in der ersten Komponente hat; und für eine zweite Komponente des Positionssignals, Erzeugen eines die Orte der ausgewählten Koeffizienten codierenden Signals nach einer zweiten Methode, die einen zweiten Wirkungsgrad in bezug auf das allgemein erwartete Muster ausgewählter Koeffizienten in der zweiten Komponente hat,

wobei der zweite Wirkungsgrad höher als der Wirkungsgrad der ersten Methode in bezug auf das allgemein erwartete Muster ausgewählter Koeffizienten in der zweiten Komponente ist, und wobei der erste Wirkungsgrad höher als der Wirkungsgrad der zweiten Methode in bezug auf das allgemein erwartete Muster ausgewählter Koeffizienten in der ersten Komponente ist,

wobei die Einrichtung zum Decodieren folgendes aufweist:

a. eine erste Decodiereinrichtung zum Decodieren des die Orte der ausgewählten Koeffizienten codierenden Signals nach der ersten Methode; und

b. eine zweite Decodiereinrichtung zum Decodieren des die Orte der ausgewählten Koeffizienten codierenden Signals nach der zweiten Methode.

14. Einrichtung zum Decodieren eines Signals nach Anspruch 13, wobei eine von der ersten und der zweiten Methode zum Codieren das Codieren der Orte der ausgewählten Koeffizienten nach einer Methode (1316) aufweist, die die Orte zu einem Muster in wenigstens einer Dimension gruppiert; und

die andere von der ersten und der zweiten Methode zum Codieren das Codieren der Orte der ausgewählten Koeffizienten nach einer Methode (1320) aufweist, die die Distanz zwischen den Orten ausgewählter Koeffizienten mißt, wobei die Einrichtung zum Decodieren folgendes aufweist:

a. eine Musterdecodierer(1232)-Einrichtung zum Decdieren des die Orte der ausgewählten Koeffizienten codierenden Signals nach der Methode, die die Orte zu einem Muster in wenigstens einer Dimension gruppiert; und

b. eine Distanzdecodierer(1234)-Einrichtung zum Decodieren des die Orte der ausgewählten Koeffizienten codierenden Signals nach der Methode, die die Distanz zwischen den Orten ausgewählter Koeffizienten mißt.

15. Einrichtung zum Decodieren eines Signals nach Anspruch 14, wobei die Methode (1316), die die Orte zu einem Muster in wenigstens einer Dimension gruppiert, Vektorquantisierung umfaßt; und die Methode (1320), die die Distanz zwischen den Orten ausgewählter Koeffizienten mißt, Lauflängenco dierung umfaßt; wobei die Einrichtung zum Decodieren folgendes aufweist:

a. eine Einrichtung (1234) zum Decodieren des die Orte der ausgewählten Koeffizienten codierenden Signals, das durch Lauflängencodierung erzeugt wurde; und

b. eine Einrichtung (1232) zum Decodieren des die Orte der ausgewählten Koeffizienten codierenden Signals, das durch Vektorquantisierung erzeugt wurde.

16. Einrichtung zum Decodieren nach Anspruch 13, wobei das Codiersignal durch die Schritte erzeugt worden ist: für eine erste Komponente (1122) des Positionssignals, Erzeugen eines die Orte der ausgewählten Koeffizienten codierenden Signals unter Anwendung von Lauflängencodierung mit einem ersten Codebuch; und für eine zweite Komponente (1124) des Positionssignals, Erzeugen eines die Orte der ausgewählten Koeffizienten codierenden Signals unter Anwendung von Lauflängencodierung mit wenigstens einem zusätzlichen Codebuch, wobei die Decodiereinrichtung folgendes aufweist:

a. einen Lauflängendecodierer (1234) zum Decodieren der Orte; und

b. mit dem Lauflängencodierer verbunden:

i. einen ersten Codebuch-Speicher (1238a) zum Decodieren der Orte der ausgewählten Koeffizienten in der ersten Komponente des Positionssignals; und

ii. wenigstens einen zusätzlichen Codebuch-Speicher (1238b) zum Decodieren der Orte der ausgewählten Koeffizienten in der zweiten Komponente des Positionssignals.