DE68926876T2

DE68926876T2 - Vorrichtung zur Vektorquantisierung von Bildern

Info

Publication number: DE68926876T2
Application number: DE68926876T
Authority: DE
Inventors: Taejeong Kim
Original assignee: AT&T Corp
Current assignee: AT&T Corp
Priority date: 1988-11-18
Filing date: 1989-11-10
Publication date: 1996-12-19
Anticipated expiration: 2009-11-11
Also published as: DE68926876D1; CA1315392C; US5444800A; JPH07112279B2; EP0369689A2; EP0369689A3; JPH02183684A; EP0369689B1

Description

Allgemeiner Stand der Technik

Bei der Datenverarbeitung für Bildübertragung sind in der Vergangenheit verschiedene Techniken zur Reduzierung der für die Übertragung der Daten erforder lichen Bitrate verwendet worden. Eine Anzahl dieser Techniken sind umfassend als Bildkompression charakterisiert worden, was bedeutet, daß für die Wahrnehmung irrelevante Aspekte der Bilddaten entfernt und die Redundanzen in den Daten durch die Codiertechnik reduziert werden, um die erforderliche Bitrate zu reduzieren. Die Vielfalt an Techniken hat sich vervielfacht, da die Erfordernisse hinsichtlich Bildqualität gleichzeitig mit der Nachfrage nach der verfügbaren Kanalbandbreite gestiegen sind.
Eine der Techniken, derartige Ergebnisse zu erzielen, ist die Technik, die als Bildkompression unter Verwendung von Vektorquantisierung bekannt ist, wobei Blöcke oder Vektoren, die jeweils eine Gruppe individueller Bildpunkte darstellen, unabhängig codiert werden. Es wurde nachgewiesen, daß mit dieser Technik mäßig niedrige Raten in Bit pro Bildpunkt wirksam erzielt werden können.
Um die gleiche Übertragungsqualität aufrechtzuerhalten und die Bitraten weiter zu senken, ist es notwendig gewesen, eine Art von Vektorquantisierung einzusetzen, die als Vektorquantisierung mit Speicherung charakterisiert werden kann. In die Codierprozedur wird Speicherung miteinbezogen, indem in jedem aufeinanderfolgenden Eingabeblock Speicherung von zuvor codierten Blöcken verwendet wird. Bei einer bestimmten Art dieser Technik, die als Vektorquantisierung mit endlichen Zuständen (finite state vector quantization) bekannt ist, kommt eine Anzahl von Zuständen zur Anwendung, die Schlüsselinformationen über zuvor codierte Vektoren zusammenfassen, um aus einer Familie sogenannter Code lexika eines auszusuchen, um jeden eingegebenen Vektor zu codieren. Ein Beispiel für eine derartige Technik findet sich in dem Artikel mit dem Titel "Image Compression Based on Vector Quantization With Finite Memory" von R. Aravind und Allen Gersho in Optical Engineering, Band 26, Juli 1987, S. 570-580.
Codierer und Decodierer eines derartigen Systems weisen eine Rückkopplungsstruktur auf, in der die durch die Ausgangssignale bestimmten internen Zustände rückgekoppelt und zusammen mit den Eingangssignalen zum Codieren und Decodieren verwendet werden. Das Ziel derartiger Finite-State-Techniken liegt darin, die Qualität der erzielten Übertragung beizubehalten und gleichzeitig die erwünschte niedrige Bitrate zu erreichen. Falls der interne Zustand einen kleinen Bereich, der den zu codierenden eingegebenen Vektor enthält, genau darstellen kann, kann mit Finite-State-Vektorquantisierung das oben genannte Ziel erreicht werden, indem eine relativ kleine zeitlich schwankende Menge an Codelexika verwendet wird.
Die Technik, auf die oben Bezug genommen worden ist, und andere im Umfeld der Bildcodierung wurden hinsichtlich der Bildcodierung mit zwei besonderen Faktoren konfrontiert. Der eine ist die Tatsache, daß, da die Bilder zweidimensionale Eigenschaften haben, jeder Bildpunktblock, üblicherweise ein rechteckiger Bildpunktblock, außerhalb des Blockes mehr benachbarte Bildpunkte aufweist als ein eindimensionaler Stichprobenblock wie im Umfeld der Sprachcodierung, und der andere ist die Tatsache, daß die meisten üblichen Bilder eine sehr hohe Korrelation zwischen benachbarten Bildpunkten aufweisen. Erstere Eigenschaft bezeichnen wir als örtliche Nachbarschaft.
Dessen ungeachtet ist es früheren Versuchen, die örtliche Nachbarschaft auszunutzen, nicht gelungen, die Möglichkeiten sowohl zur Verbesserung der Übertragungsqualität und der Reduktion der Bitrate maximal zu nutzen. Das System von Aravind und Gersho, auf das oben Bezug genommen wurde, schmälert den Effekt der örtlichen Nachbarschaft, indem Informationen über die örtlich benachbarten Bildpunkte in indirekte Informationen, wie zum Beispiel das Vorhandensein und die Arten von Helligkeitsprüngen, umgewandelt werden.
Die Technik des oben zitierten Artikels von Aravind und Gersho sucht die Kanten des Bildes innerhalb jeden Blocks; bei Zustandscodelexikonblöcken jedoch, die als beste Entsprechung für Bildblöcke mit derartigen internen Kanten ausgewählt worden sind, wird beim Anpassen an nachfolgende benachbarte Bildblöcke, die möglicherweise eine Fortsetzung der Bildkante aufweisen, kein Bildpunkt mit Vorrang gegenüber irgendeinem anderen Bildpunkt in einem derartigen Codelexikonblock behandelt. Somit wirkt sich nach der Technik von Aravind und Gersho ein Teil der Relevanz der örtlichen Nachbarschaft nicht auf das Codieren des nachfolgenden Bildblocks aus.
Aravind und Gersho offenbaren auch in ICASSP 86 Proceedings, 7-11 April 1986, Seiten 137-140, "Low-rate image coding with finite-state vector quantization" eine Bildcodiertechnik nach dem Oberbegriff von Anspruch 1.
Die Blöcke in der gleichen Spalte und vorangehenden Zeile und in der gleichen Zeile und vorangehenden Spalte werden mit Hilfe eines Kantenklassifizierers klassifiziert, der den Block gemäß irgendeiner Kante (d.h. ein Übergang zwischen schwarz und weiß), die angetroffen wird, klassifiziert oder, falls keine derartige Kante angetroffen wird, mit Hilfe der Durchschnittshelligkeit des Blocks klassifiziert. Diese Kantenklassifizierung und Durchschnittshelligkeitsklassifizierung wird unter Verwendung aller Bildpunkte in den relevanten Blöcken durchgeführt.
Eine Aufgabe der vorliegenden Erfindung liegt darin, die Leistung derartiger Codiertechniken im Hinblick auf die übertragene Bildqualität und/oder die Reduktion der für die Übertragung erforderlichen Bitrate zu verbessern. Ferner wird durch einen neuaufblühenden Markt für wirtschaftliche Speichertechniken für Bilder für Archivzwecke, zum Beispiel für Anwendungen in Medizin, Geophysik, Luftaufnahmetechnik oder Satellitenfotografie, für elektronisches Einkaufen oder für Videokonferenzen, die Notwendigkeit erhöht, derartige Techniken bis an ihre Grenzen zu verschieben und darüberhinaus die Einfachheit des Decodierens zu einer Hauptaufgabe des Systems zu machen, selbst auf Kosten eines größeren Aufwands für die Codiertechniken.

Zusammenfassung der Erfindung

Die Erfindung hat den in den unabhängigen Ansprüchen 1, 4, 7 und 8 dargelegten Inhalt. Es hat sich herausgestellt, daß die wirksamste Art, Speicherung in ein derartiges System einzubeziehen, darin besteht, die zweidimensionale örtliche Nachbarschaft auf eine Weise einzusetzen, die die Helligkeitskontinuität zwischen örtlich eng zusammenliegenden Bildpunkten der benachbarten Blöcke direkt steuert. Indirekte Informationen werden überhaupt nicht mehr in Betracht gezogen, wie zum Beispiel die Klassifizierung von Sprüngen, so daß die Erfindung Zustandscodelexika verwendet, die im Hinblick auf die beste Helligkeitsanpassung an die relativ am nächsten liegenden Bildpunkte der Vektoren ausgewählt sind, die den vorhergehenden Block und den Block in einer Zeile davor darstellen, um nicht die Signifikanz ihrer örtlichen Nachbarschaft zu verlieren.
Die direktere Anwendung der örtlichen Nachbarschaft, die der Gegenstand der vorliegenden Erfindung ist, wird als Vektorquantisierung mit "Seitenanpassung" oder "Überlappungsanpassung" für zweidimensionale Informationsblöcke bezeichnet.
Weiterhin hat sich herausgestellt, daß Codierung mit variabler Länge basierend auf Lernbildstatistiken oder einem eingegebenen Bild selbst die Wirksamkeit des vorliegenden modifizierten Systems weiter erhöht. Da die rauschfreie Codierung mit variabler Länge, die vorgeschlagen wird, einfach ist, kann ihre volle Beschreibung an den Empfanger in einem Nachrichtensystem mit einem nur unbedeutenden Anstieg der Bitrate übertragen werden. Gemäß dieses Merkmals der Erfindung wird sogar eine Familie rauschfreier Codes mit variabler Länge beschrieben, die sogenannten Kanalsymbolentropien sehr nahe kommen. Mit diesem besonderen Merkmal der Erfindung können auch andere Finite-State-Vektorquantisierungskonstruktionen nachgerüstet werden.

Kurze Beschreibung der Zeichnungen

Weitere Merkmale und Vorteile der vorliegenden Erfindung gehen aus der folgenden ausführlichen Beschreibung hervor, die zusammen mit der Zeichnung gelesen werden muß, in der:
Figur 1 eine Blockdiagrammdarstellung eines Senders für ein erfindungsgemäßes Nachrichtensystem ist.
Figur 2 ein Blockdiagramm ist, das die Beziehung zwischen Sender und Empfanger in einem derartigen System zeigt.
Figur 3 ein ausführlicheres Blockdiagramm ist, das den erfindungsgemäßen Sender zeigt;
Figur 4 ein Flußdiagramm des erfindungsgemäßen Codelexikonauslegungsverfahrens ist;
Figur 5 ein Flußdiagramm für den Betrieb der vorliegenden Erfindung während des eigentlichen Prozesses der Bildinformationscodierung ist.
Figur 6 ein Flußdiagramm für die Technik ist, um das Codelexikon für den nächsten Zustand zu finden;
Figur 7 die typische Bildpunktanordnung zeigt, die bei der Anordnung mit "Seitenanpassung" sowohl beim Lernen (Codelexikonauslegung) und beim Codieren verwendet wird; und
Figur 8 die typische Bildpunktanordnung zeigt, die bei der Anordnung mit "Überlappungsanpassung" sowohl beim Lernen (Codelexikonauslegung) und beim Codieren verwendet wird.

Ausführliche Beschreibung

In Figur 1 wird eine grundlegende Ausführungsform gezeigt, die eine ähnliche Organisation aufweist wie Systeme, die dazu verwendet werden können, Codieralgorithmen des Finite-State-Vektorquantisierungstyps zu praktizieren, einschließlich dem,das in dem oben zitierten Artikel von Aravind et al. offenbart ist; doch wird sich bei genauerer Lektüre herausstellen, daß die Ausführungsform von Figur 1 gezielt auf die besonderen Merkmale der vorliegenden Erfindung ausgelegt ist. In Figur 1 wird insbesondere eine Ausführungsform der vorliegenden Erfindung gezeigt, die bei einem Sender eines Nachrichtensystems verwendet wird, das Bilder zwischen entfernten Stellen überträgt. Die Organisation dieses Senders ist so ausgelegt, daß er das abgetastete Bildsignal, das auf konventionelle Weise für Fernsehbildübertragung, aber wahlweise mit einer höheren Auflösung abgetastet ist, annehmen kann. Sie enthält auch eine Möglichkeit, die Bildpunkte, wie durch die Blockformierungsstufe 11 von Figur 1 gezeigt, zu Blöcken zu formen. Bei jedem Block handelt es sich um einen 4x4- Block aus Bildpunkten, wobei zum Beispiel der erste Block die ersten vier Bildpunkte jeder der ersten vier Zeilen abgetasteter Bildpunkte enthält. Jeder resultierende Bildpunktblock läuft dann zum Quantisierer 12, der eine Suche nach dem nächstgelegenen Nachbarn durchführt, um, wie hiernach beschrieben, aus dem speziellen ausgewählten Codelexikon den erwünschten Eintrag auszuwählen. Die Suche wird von der Logikschaltung 42 geleitet, die mit dem Codierabschnitt 41, der den Block 11 und Quantisierer 12 enthält, in Verbindung steht. Die Logik ist derart, daß der entsprechende Codewortindex mit der entsprechend niedrigen Bitrate, aber mit einer optimalen Anpassung der Bildpunktblockkanten übertragen werden kann, wie hiernach ausführlicher beschrieben wird. Die Blockbildung und die Suche des Quantisierers nach dem nächstgelegenen Nachbarn werden, wie in Abschnitt 2.1.1 des Artikels von Aravind beschrieben, durchgeführt. Dies kann kurz wie folgt beschrieben werden: der Block von Bildpunkten ist zum Beispiel ein vier-mal-vier-Block der kleinsten Bildeinheiten. Diese Blöcke werden, wie zu erwarten ist, auf die kompakteste Art zusammengesetzt, so daß sie Zeile für Zeile in der Richtung, in der das Bild über die Anzeige oder über eine andere zweidimensionale Darstellung des Bildes hinweg entwickelt wird, vier Bildpunkte breit und vier Bildpunkte tief sind. Mit anderen Worten werden zur Erzeugung der Blöcke benachbarter Bildpunkte vier Zeilen verwendet. Die Bildpunktblöcke werden dann an den Quantisierer geschickt. Von dem gegenwärtig dynamisch ausgewählten Zustandscodelexikon durch die ausgewählte eine der Menge 14 von Schalterpositionen, zum Beispiel vom Schalter 20, werden die begrenzten Codelexikoneinträge C&sub1;, C&sub2;, Cn auf der Basis der kleinsten Entfernung mit dem Eingangs-Istbildpunkblock x für jeden Bildpunkt im Block verglichen. Es wird derjenige Wert von Ci ausgewählt, der den kleinsten mittleren guadratischen Fehler liefert, und der Index dieses Codelexikonwertes, das heißt der Wert von i, wird vom Quantisierer 12 als der übertragene Codewortindex weitergeleitet. Gleichzeitig wird dieser Codewortindex als Teil der Vorgeschichte der Bildinformationen verwendet, die dazu verwendet wird, das Codelexikon des nächsten Zustands dynamisch auszuwählen, das zum Codieren des nächsten Blocks von Bildpunkten verwendet wird.
Die Logik, um diese Bildvorgeschichte zum Auswählen des nächsten Zustandscodeworts einzusetzen, findet sich in der Logikschaltung 42 von Figur 1. Der Index des vorangegangenen Codeworts wird zum Dequantisierer 13 weitergegeben, bei dem es sich im Grunde um eine Nachschlagetabelle handelt, die den Index des vorangegangenen Zustandscodelexikons in ein Codewort zurückwandelt, das einen Block darstellt; und das resultierende Ausgangssignal wird Verzögerungen und anderen logischen Verarbeitungen unterzogen, um die darauffolgende Positionierung des Schaltungsschalters 20 zu beeinflussen. Damit die dequantisierten Werte nur einen benachbarten Block von Bildpunkten beeinflussen, werden die Signale durch die jeweilige Einblockverzögerung 23 und die Verzögerung 25 von einer Zeile von Blöcken gegeben, um zu den entsprechenden Zeiten am Spaltenzustandsausgang bzw. am Zeilenzustandsausgang anzukommen. Von den Nachschlagetabellen 22 und 27 wird wahlweise der Spaltenzustandsraum 21 bzw. der Zeilenzustandsraum 28 einbezogen, um die Anzahl der Zustandslexika 19 zu reduzieren. Der Spaltenzustandsraum 21 und der Zeilenzustandsraum 28 sind die Mengen der Repräsentationen für die letzten Bildpunktspalten bzw. die letzten Bildpunktzeilen sämtlicher repräsentativen Blöcke in allen Zustandscodelexika 19.
Die oben erwähnten Blöcke 21, 22, 27 und 28 sind der Mechanismus zum Reduzieren der Anzahl von Zustandscodelexika, was wiederum den erforderlichen Speicherraum (im Codierer) reduziert. Falls es hinsichtlich der Anzahl der Zustandscodelexika oder des Speicherraumes keine Begrenzung gibt, können diese Blöcke entfallen. Unter den berücksichtigten Werten der Spalten und Zeilen von Bildpunkten lassen Filter 24 und 26 nur die letzte Spalte bzw. die letzte Bildpunktzeile durch, bei denen es sich um die Bildpunktspalte und die Bildpunktzeile unmittelbar neben dem gegenwärtig codierten Block handelt oder von diesem überlappt wird. Diese sind die für die Codierung der gegenwärtigen Bildpunkte relevantesten Bildpunkte, falls Wertesprünge im Bild vermieden werden sollen. Es ist somit dieser Bereich der Logikschaltung 42, in dem sich die vorliegende Erfindung hinsichtlich Organisation und Betrieb von der in der oben zitierten Referenz von Aravind und Gersho unterscheidet. Der Unterschied liegt in den Techniken zum Auswählen eines der Zustandscodelexika 19 auf der Basis des am Spaltenzustandsausgang ankommenden jeweiligen Spaltenzustands und des am Zeilenzustandsausgang ankommenden jeweiligen Zeilenzustands. Diese Werte werden dann an die Steuerposition des Schalters 20 angelegt, um das Zustandscodelexikon zu steuern, das im Quantisierer 12 für die Suche nach nächstgelegenen Nachbarn beim Codieren des gegenwärtigen Blocks von zu codierenden Bildpunkten verwendet wird. So könnten zum Beispiel die Zustandscodelexika geordnet werden, so daß aufeinanderfolgende Mengen von Zeilenzuständen, deren Verwendung für gleiche Indizes von Spaltenzuständen bekannt ist, nach Zeilenzustandsindex aufeinanderfolgend angeordnet werden, gefolgt von der gleichen aufeinanderfolgenden Anordnung von Zeilenzuständen für den in der Reihenfolge nächsten Index von Spaltenzuständen, usw., bis alle Spaltenzustände, deren Verwendung bekannt ist, der Reihe nach angeordnet sind. Das Spaltenzustandsindexausgangssignal von Block 22 veranlaßt dann das entsprechende Zählen der Spaltenzustandspositionen durch Schalter 20, wonach das Zeilenzustandsindexausgangssignal von Block 27 das entsprechende Zählen der Zeilenzustandspositionen von Schalter 21 veranlaßt, innerhalb der entsprechenden Anordnung von Zeilen des zuvor gezählten Spaltenzustands. Die Nachschlagetabellen 22 und 27 werden benötigt, da bei der reduzierten Menge 19 von Zustandscodelexika nicht jeder Zeilenzustandsindex des (später beschriebenen) Supercodelexikons zusammen mit jedem Spaltenzustandsindex des Supercodelexikons verwendet wird. Bei dem ausgewählten Zustandscodelexikon handelt es sich um dasjenige, das gemäß dem Prozeß der Codelexikonauslegung aus statistisch ähnlichen Blöcken im Supercodelexikon wahrscheinlich die gleichen statistischen zweidimensionalen Eigenschaften erzeugen wird, das heißt, die ähnlichste benachbarte Kante, bei der es sich für den Fall des vorausgehenden Blocks um eine Spaltenkante oder im Fall des um eine Zeile zurückliegenden Blocks um eine benachbarte Zeilenkante handelt. Da die Eingangseignale zu den Blöcken 22 und 27 von den Zustandsräumen 21 und 28 lediglich zuvorbestimmte, endliche mögliche Werte aufweisen können und die Eingangssignale von Filtern 24 und 26 lediglich zuvorbestimmte, endliche mögliche Werte aus einer größeren Menge von Werten aufweisen können, können die Suchoperationen in den Blöcken 22 und 27 nach dem nächstgelegenen Nachbarn, falls erwünscht, durch Nachschlagetabellen implementiert werden.
Es sollte hervorgehoben werden, daß es sich bei allen in der Logikschaltung 42 eingesetzten Prozessen um Nachschlagetabellenprozesse handelt, und sie im Vergleich zu der rechnerintensiven Suche nach dem nächstgelegenen Nachbarn, die im Quantisierer 12 auftritt, im allgemeinen sehr schnell bewerkstelligt werden können.
Figur 2 illustriert ein weiteres Bearbeiten des Codewortindexausgangssignals von Figur 1, um es zur eigentlichen Übertragung über ein Übertragungsmedium und zum Empfangen am Empfänger vorzubereiten. Mit anderen Worten liegt der Codewortindex bei gegebenen Eigenschaften des Mediums oder den statistischen Eigenschaften des Bildes selbst nicht unbedingt in einer für die übertra gung optimalen binären Form vor.
Mit anderen Worten wird der Codewortindex in dem Codierer 31 einer weiteren binären Codierung unterzogen, bei der übrigens als Reaktion auf eine Vorsatzlängenbestimmung in einer Vorsatzlängenbestimmungsvorrichtung 33 und das binäre Übertragungscodelexikon 32 eine weitere Reduktion der Bitrate stattfindet.
Es hat sich herausgestellt, daß rauschfreie Codes mit veränderlicher Länge für das System von Figuren 1 und 3 von Vorteil sind. Die Eins-zu-Eins-Abbildung gemäß Figur 2, die Kanalsymbole in binäre Folgen verwandelt, wird als Binärcodierer bezeichnet, und ihr Gegenstück wird als Binärdecodierer bezeichnet. Die Kanalsymbole, die aus einem Quellencodierer kommen, wie zum Beispiel aus einem FSVQ (finite state vector quantiser = Finite- State-Vektorquantisierer), weisen ein endliches Alphabet auf (d.h. ein Alphabet endlicher Größe). Bei einer gegebenen Klasse von Quellen, in diesem Fall Bildern, nehmen die Kanalsymbole eine bestimmte Wahrscheinlichkeitsverteilung an. Da für die Symbole aus einem endlichen Alphabet mit einer bekannten Wahrscheinlichkeitsverteilung bewährte Theorien über rauschfreie Codes vorliegen, kann man einfach die optimalen rauschfreien Codes auf die Kanalsymbole anwenden. Wenn jedoch das Alphabet relativ groß ist, ergeben sich mögliche Probleme, wenn rauschfreie Codes wie zum Beispiel der Huffmann-Code blind angewendet werden. So können zum Beispiel der Binärcodierer oder der Binärdecodierer relativ kompliziert sein und sehr große Pufferspeicher erfordern. Diese Probleme werden hauptsächlich von den großen Unterschieden in der Länge des Binärcodeworts hervorgerufen. Die Länge eines Codeworts in einem rauschfreien Code wird manchmal als eine Stufe des rauschfreien Codes bezeichnet. Auf der anderen Seite kann bei unbekannter Kanalsymbolverteilung der für eine Wahrscheinlichkeitsverteilung entworfene optimale rauschfreie Code für eine andere Verteilung sehr schlecht sein. Es könnte argumentiert werden, daß, da der Binärcodierer die Kanalsymbolstatistiken hat, der entsprechende optimale rauschfreie Code jedesmal verwendet werden kann. Bei derartigen Fällen muß zur richtigen Decodierung die Beschreibung des optimalen rauschf reien Codes ebenfalls an den Binärdecodierer übertragen werden. Eine derartige Beschreibung kann leider mehr als eine vernachlässigbare Menge an Informationen enthalten. Das heißt, die Übertragung der Beschreibung des optimalen rauschfreien Codes kann die Gesamtbitrate erheblich erhöhen. Das Gegenmittel für alle oben erwähnten Probleme besteht darin, die Anzahl der Stufen des rauschfreien Codes zu begrenzen. Es tritt dann die Frage auf: "Wird jeder rauschfreie Code mit nur wenigen Stufen ein gutes Verhalten zeigen?" Aufgrund der in unserer Anwendung angetroffenen besonderen Form der Kanalsymbolverteilung wird nun gezeigt, daß die Antwort für Vektorquantisierer mit Seitenanpassung und Vektorquantisierer mit Überlappungsanpassung positiv ist.
Nach der Übertragung über den Nachrichtenkanal oder Speicherkanal 37 zum Empfänger wird der Binärcode von dem Binärdecodierer 34 gemäß dem binären Nachschlagecodelexikon 35, das dem binären Codelexikon 32 des Senders gleich ist, in den Codewortindex zurückgewandelt. Die Codierlogik 36 mit variabler Länge von Figur 2 kann gemäß den unten beschriebenen mathematischen Formeln implementiert werden. Alternativ dazu kann sie auch gemß anderer rauschfreier Codierverfahren variabler Länge nach dem Stand der Technik implementiert werden. Für die Zwecke der vorliegenden Erfindung handelt es sich bei der oben beschriebenen Version um eine bevorzugte Alterna tive, aber nicht um eine ausschließliche Alternative. In Figur 3 wird der Empfänger gezeigt, der an den Ausgang des Binärdecodierers 34 angekoppelt ist und das relativ zur Anzahl der über den Nachrichtenkanal 37 übertragenen Bit qualitativ hochwertige Ausgangsbild bereitstellt. Dieser Empfänger enthält einen Dequantisierer 43, bei dem es sich wiederum um eine Nachschlagetabelle handelt, die funktionsmäßig mit der des Dequantisierers 13 im Sender und in sich selbst identisch ist, und eine Logikschaltung 44, die mit der Logikschaltung 42 des Senders im wesentlichen identisch ist. Die Bildaufbauschaltung 45 kehrt im Grunde den Prozeß um, der in der Blockbildungsschaltung 11 von Figur 1 Blöcke von Bildpunkten formt, vorbehaltlich einiger zusätzlicher Funktionen für die Überlappungsanpassung und Decodierung, die später beschrieben werden.

Funktion des Finite-State-Vektorquantisierers

Die Funktion des Senders von Figur 1 kann mathematisch definitiver wie folgt gekennzeichnet werden: der Finite-State-Vektorquantisierer funktioniert im Grunde wie endliche Automaten, wie auf dem Gebiet digitaler Schaltungen definiert. Bei einer gegebenen Vektordimension k bildet der Codierer zu jedem Abtastzeitpunkt i einen k-dimensionalen Quellvektor xi von einem endlichen Alphabet zur Übertragung in ein Kanalsymbol yi ab, und ein beliebiger entsprechender empfangender Decodierer bildet das Kanalsymbol zurück in einen k-dimensionalen Wiedergabevektor i ab. Zum Zweck digitaler Übertragung und/oder Speicherung werden die Kanalsymbole üblicherweise durch Binärfolgen dargestellt.
Um den Codierer und Decodierer des Finite-State- Vektorquantisierers ausführlich zu beschreiben, werden sie in verschiedene Bausteine oder Komponenten zerlegt. Diese Komponenten sind (1) ein Zustandsraum 5, bei dem es sich um eine endliche Menge von Zuständen handelt, (2) eine Menge von Zustandscodelexika {Cs:s&epsi;S}, (3) ein Quantisierer q, (4) ein Dequantisierer p, bei dem es sich um eine Codelexika(-tabellen)-Nachschlagefunktion handelt, und schließlich (5) eine Nächstzustandsfunktion f. Es folgt eine allgemeine Beschreibung dieser Bausteine. Der Zustandsraum ist eine Ansammlung von M Symbolen, Zustände genannt, d.h. S = {s&sub1;, s&sub2;,...,sM}, wobei s&sub1;, s&sub2;,...,sM Zustände bezeichnen. Jedes Zustandscodelexikon ist eine Menge von N k-dimensionalen Vektoren, Codeworte genannt. Die Menge von Zustandscodelexika sind durch die Zustände indiziert, und die Gesamtzahl der Zustandscodelexika ist somit gleich der Größe des Zustandsraums, also M. Die Vereinigung aller Zustandscodelexika wird Supercodelexikon genannt und ist mit C bezeichnet. Das heißt, C = s&epsi;S Cs. Die Indexmenge Y = {1,2, ..., N}, die alle Zustandscodelexika gemein haben, wird Kanalsymbolraum genannt. Der Grund für diesen Namen liegt darin, daß die Indizes der Codeworte innerhalb des Zustandscodelexikons Kanalsymbole sind, die schließlich über den Kanal übertragen oder gespeichert werden. Der Quantisierer ist eine Abbildung von dem kartesischen Produkt des k-dimensionalen Euklidischen Raumes Rk und des Zustandsraumes S zum Kanalsymbolraum Y. Das heißt q: Rk x S T Y, wobei x das kartesische Produkt bezeichnet. Man kann es auch so auffassen, daß es sich bei dem Quantisierer um eine Sammlung aus Abbildungen handelt {qs: s &epsi; S}, derart, daß jedes qs eine Abbildung von Rk auf Y ist. Aus Gründen der Zweckmäßigkeit der Beschreibung wird allerdings die erste Definition des Quantisierers verwendet. Die Idee, daß der Quantisierer eine Datenkomprimierung erzielt, impliziert, daß der Quantisierer offensichtlich eine Viele-auf-Eins-Abbildung sein sollte, und somit existiert sein Gegenstück nicht. Allerdings wird eine Abbildung p definiert, Dequantisierer genannt, um das Gegenstück des Quantisierers nachzuahmen. Insbesondere ist der Dequantisierer eine Abbildung von Y x 5 auf C. Wenn man berücksichtigt, daß der Quantisierer eine Sammlung von Abbildungen {qs: s &epsi; S} ist, kann auch der Dequantisierer als eine Sammlung von Einszu-Eins-Abbildungen {ps: s &epsi; S} angesehen werden, derart, daß ps: Y T Cs ist. In diesem Fall ist jedes Pa eine Tabellennachschlagefunktion, die jedes Kanalsymbol in das Codewort in Cs abbildet, bei dem der Index gleich dem Kanalsymbol ist. Da der Finite-State-Vektorquantisier- Codierer und -Decodierer wie endliche Automaten funktionieren, sollten ihre internen Zustände zu jedem Abtastzeitpunkt aktualisiert werden. Interne Zustände werden durch die Nächstzustandsfunktion f aktualisiert. Die Nächstzustandsfunktion f ist eine Abbildung von dem J- fachen kartesischen Produkt des Supercodelexikons C auf den Zustandsraum, wobei J die Anzahl der zurückliegenden Wiedergabevektoren ist, die zur Erzeugung des nächsten Zustands beitragen. Das heißt f: x =1 C T S. Mit anderen Worten erzeugt die Nächstzustandsfunktion den nächsten Zustand aus der endlichen zurückliegenden Geschichte ausgewählter Codeworte.
Nun kann der Codierer und Decodierer des Finitestate-Vektorquantisierers hinsichtlich der oben beschriebenen Bausteine charakterisiert werden. Der Finite-State-Vektorquantisiercodierer kann durch folgende fünf Bestandteile charakterisiert werden: ein Zustandsraum, eine Menge von Zustandscodelexika, ein Quantisier er, ein Dequantisierer und eine Nächstzustandsfunktion, d.h. (S, {Cs, s &epsi; S}, q,p,f). Zu einem Abtastzeitpunkt i sei angenommen, daß der Codierer einen Zustand si in S hat. Der Quantisierer bildet dann einen k-dimensionalen Quellvektor xi derart in ein Kanalsymbol yi ab, daß yi der Index des Codewortes innerhalb des Zustandscodelexikons Csi ist, das xi hinsichtlich eines bestimmten Kriteriums am nächsten kommt. Das resultierende Codewort, das der Wiedergabevektor ist, ist mit i bezeichnet. Ein einfaches und allgegenwärtiges Kriterium ist die Minimierung des mittleren guadrierten Fehlers, die als &sub1;k
definiert ist, wobei [xi]j und [ i]j die j-ten Komponenten der Vektoren xi bzw. i sind. In dieser Erörterung ist der Quantisierer im Grunde ein speicherloser Vektorquantisierer mit dem Zustandscodelexikon als seinem Codelexikon. Es können deshalb verschiedene Quantisiererstrukturen gefunden werden, die im Finite-State-Vektorquantisierer verwendet werden können, zum Beispiel der hier beschriebene Vektorquantisierer mit vollständiger Suche, der VQ mit Baumsuche, der Mehrschritt-VQ, und der Produkt-VQ. In dieser Arbeit jedoch wird nur der VQ mit vollständiger Suche betrachtet. Unter der Annahme einer eindeutigen Indizierung soll η die Funktion bezeichnen, die ein Element einer Menge in ihren Index abbildet. So zum Beispiel, falls A = {a&sub1;, a&sub2;,...,a&sub1;,..., aL), dann ist η (ai, A) = 1. Die Funktionsweise des Quantisierers zum Abtastzeitpunkt i wird nun durch die folgende Gleichung zusammengefaßt
wobei min&supmin;¹ die Funktion bezeichnet, die bedeutet "die Variable, die die darauffolgende Menge minimiert". Der Ausdruck innerhalb der eckigen Klammer stellt das Codewort der minimalen Verzerrung vom Quellvektor dar und wird der Wiedergabesvektor genannt.
Nach der Erzeugung eines Kanalsymbols durch den Quantisierer muß der Codierer als Vorbereitung für die Codierung des nächsten Quellvektors den Zustand aktualisieren. Die Nächstzustandsfunktion führt diese Aktualisierung durch Abbilden der endlichen zurückliegenden Wiedergabesvektoren in den nächsten Zustand Si+1 durch. Es sei darauf hingewiesen, daß die Wiedergabesvektoren noch nicht zur Verfügung stehen, obwohl sie während des Quantisierprozesses implizit bestimmt werden. Der Dequantisierer 13 macht Wiedergabesvektoren für die Nächstzustandsfunktion verfügbar. Der Dequantisierer ist eine Tabellennachschlagefunktion, wobei die Nachschlagetabelle ein Zustandscodelexikon ist. Bei einem gegebenen Abtastzeitpunkt i und einem Zustand si bildet der Dequantisierer ein Kanalsymbol yi in ein Codewort in Csi ab, dessen Index yi ist. Mit anderen Worten, falls i den Wiedergabesvektor zum Zeitpunkt i bezeichnet, ist i = p(yi,si) derart, daß xi &epsi; Csi und yi=η( i),Cs ist. Da die Wiedergabesvektoren nun durch den Dequantisierer zur Verfügung stehen, ist die Nächstzustandsfunktion durch die folgende Beziehung dargestellt: si+1 = f( i), i-1, .... Unter der Annahme, daß der Anfangszustand s&sub0; gegeben ist, werden der Quantisierer und die Nächstzustandsfunktion wiederholt, wie oben beschrieben, um die Folge von Kanalsymbolen y&sub0;, y&sub1;, y&sub2;,... aus der Folge von Quellvektoren x&sub0;, x&sub1;, x&sub2;,... zu erzeugen. Durch Übertragung oder Speicherung wird diese Folge von Kanalsymbolen von dem Decodierer empfangen und dann in eine Folge von Wiedergabesvektoren, mit &sub0;, &sub1;, &sub2;,... bezeichnet, zurück umgewandelt.
Der Finite-State-Vektorquantisierdecoder ist durch die vier Bestandteile gekennzeichnet: einen Zustandsraum, eine Menge von Zustandscodelexika, einen Dequantisierer und eine Nächstzustandsfunktion, d.h. (S,{Cs: s&epsi;S), p,f). Alle diese Komponenten sind mit denen des Finite-State-Vektorquantisiercodierers identisch und sind schon ausführlich beschrieben. Wenn der Finite- State-Vektorquantisierdecodierer ein Kanalsymbol empfängt, wählt der Dequantisierer im Zustandscodelexikon das Codewort aus, das dem internen Zustand derart entspricht, daß der Index des Codewortes mit dem empfangenen Kanalsymbol identisch ist. Die Nächstzustandsfunktion aktualisiert auf der Basis der ausgewählten Codeworte (oder Wiedergabesvektoren) den internen Zustand des Decodierers. Unter der Annahme, daß der anfängliche Zustand des Codierers auch dem Decodierer bekannt ist, kann die Nächstzustandsfunktion des Decodie rers die Codiererzustände verfolgen. Die von dem Decodierer erzeugten Wiedergabesvektoren sind deshalb mit den entsprechenden, im Codierer bestimmten Wiedergabesvektoren identisch.
Zusammengefaßt ist bei gegebenem anfänglichem Zustand s&sub0; die Finite-State-Vektorquantisiercodierung die progressive Wiederholung der folgenden Operationen.
yi = q(xi, si)
i = p(yi, si)
si+1 = f( i, i-1,..., i-j+1)
Bei gegebenem anfänglichen Zustand s&sub0; ist die Decodieroperation des Finite-State-Vektorquantisierers als die progressive Wiederholung der folgenden Operationen zusammenge faßt.
i = p(yi, si)
si+1 = f( i, i-1,..., i-j+1)

SEITENANPASSUNGS-VEKTORQUANTISIERUNG

Ein Seitenanpassungs-Vektorquantisierer gemäß der vorliegenden Erfindung liegt innerhalb einer Klasse von FSVQ. Wie der Name "Seitenanpassung" schon sagt, versucht der Seitenanpassungsvektorquantisierer den Helligkeits(Graupegel-)Übergang über die Grenzen der Wiedergabesvektoren so glatt wie möglich zu machen. Den Seitenanpassungsvektorquantisierern liegt die Annahme zugrunde, daß es sich bei den Bildpunktzeilen und -spalten des Quellbildes um Markow-Prozesse erster Ordnung handelt. Falls die Annahme richtig ist, dann tragen die dem gegenwärtigen Block (dem zu codierenden Block) benachbarten Bildpunkte alle in der gesamten zurückliegenden Geschichte enthaltenen Informationen über den gegenwärtigen Block. Mit anderen Worten, falls die Bildpunktzeilen und -spalten Markow erster Ordnung sind, so ist der gegenwärtige Block bei gegebenen, dem gegenwärtigen Block benachbarten Bildpunkten von dem gesamten Rest der zurückliegenden Geschichte bedingt unabhängig. Unter Nichtbeachtung des Quantisierungseffektes auf die zurückliegende Geschichte muß daher der Zustand ausschließlich von dem zu codierenden Bildpunktblock benachbarten Bildpunkten erzeugt werden. Diese Tatsache steht mit dem Konzept der in Abschnitt 1 formulierten örtlichen Nachbarschaft (siehe die schraffierten Gebiete in Figur 7) in enger Beziehung. Die Annahme legt auch nahe, daß die beste Auswahl des Zustandscodelexikons die Menge der Codeworte, deren Grenzbildpunkte den Wiederga bebildpunkten am ähnlichsten sind, die zu der Zustandserzeugung beiträgt. Mit anderen Worten sollte das Zustandscodelexikon die Menge von Codeworten mit der besten "Seitenanpassung" sein. Die "Seitenanpassung" hat gegenüber anderen Arten von Finite-State-Vektorquantisierern den Vorteil, daß selbst dann, wenn der Wiedergabesvektor nicht das beste Codewort im Supercodelexikon ist, der Fehler, den er einführt, im reproduzierten Bild oft weniger sichtbar ist.
In Figur 2 wird der Gesamtaufbau des Seitenanpassungsvektorquantisierers als Blockdiagramm dargestellt. Alle Elemente im Diagramm werden in Kürze beschrieben. Um in diesem Abschnitt eine mögliche Verwirrung zu vermeiden, wird für die matrixartigen Vektoren mit Zeilen und Spalten der Ausdruck Blöcke und für Zeilenvektoren oder Spaltenvektoren Vektoren verwendet.
Um unter Verwendung der im vorausgegangenen Abschnitt verwendeten Sprache den Seitenanpassungsvektorquantisierer zu charakterisieren, wird mit der Definition des Zustandsraums begonnen. Es sei angenommen, daß alle Quell-(Bildpunkt-)Blöcke die Größe m mal n aufweisen, d.h. Matrizen mit m Reihen und n Spalten von Bildpunkten. Jeder Zustand wird durch ein Paar aus einem Spaltenzustandsvektor der Dimension m und einem Zeilenzustandsvektor der Dimension n dargestellt. Das heißt, ein Zustand hat die Form (u, v), wobei u ein Spaltenzustandsvektor ist und v ein Zeilenzustandsvektor. Die Spaltenzustandsvektoren sollen das Alphabet u haben, genannt Spaltenzustandsraum, und die Zeilenzustandßvektoren sollen das Alphabet v haben, genannt Zeilenzustandsraum. Der Zustandsraum ist dann das kartesische Produkt aus dem Spaltenzustandsraum und dem Zeilenzustandsraum, d.h. s = u x v. Die Bedeutung dieser Spalten- und Zeilenzustandsvektoren liegt darin, daß sie die Wiedergabesbildpunkte darstellen, die dem zu codierenden Quellblock benachbart sind.
Wie schon weiter oben erwähnt, muß ein Seitenanpassungsvektorquantisierer für jeden Zustand im Zustands raum ein Zustandscodelexikon aufweisen. Die Beschreibung von Zustandscodelexika wird unter der Annahme eines Supercodelexikons C begonnen. Bei einem gegebenen Zustand s = (u, v) wird das entsprechende Zustandscodelexikon als diejenige Untermenge des Supercodelexikons C bezeichnet, deren Elemente entlang den Seiten mit u und v am besten "übereinstimmen", d.h. entlang der ersten Spalte bzw. der ersten Zeile. Genauer gesagt soll die Seitenanpassungsverzerrung e wie folgt definiert sein. Zuerst sollen [x] und [x] die l. Spalten- bzw. l. Zeilenvektoren eines Blocks x bezeichnen. Das heißt, [x] = (x1l, x2l,...,xel)T und [x] = (x1l, x2l,...,xln), wobei xjl das Element von x in der j-ten Zeile und l-ten Spalte und der Hochindex T die Transponierte bezeichnet. Bei gegebenem Zustand s = (u,v) und einem m mal n Block x wird die Seitenanpassungsverzerrung für ein bestimmtes Verzerrungsmaß d und Gewichtungskonstanten a und b als e(s,x) = a d(u, [x] ) + b d(v, [x] definiert. So kann zum Beispiel das Verzerrungsmaß der mittlere quadratische Fehler und a = b = 1/2 sein. Das Zustandscodelexikon Cs für den Zustand s = (u, v) wird dann mit Ca = (c , c ,...,c ) definiert, derart daß die Elemente von Cs folgende Bedingungen erfüllen: c &epsi; C für 1 = 1, 2,...,N. e(s,csli) ≤ e(s,csl2) immer dann, wenn l ≤ l&sub1; ≤ l&sub2; ≤ N ist. e(s,c ≤ e(s,c) für 1 = 1, 2,...,N und für alle c &epsi; C-Cs. In Worten, bei einem gegebenen Zustand s ist das Zustandscodelexikon Cs eine Teilmenge des Supercodelexikons, die N Codeworte mit der kleinsten Seitenanpassungsverzerrung enthält, mit wachsender Ordnung von Seitenanpassungsverzerrung angeordnet. Es sei bei dieser Definition darauf hingewiesen, daß es sich bei dem Zustandscodelexikon nicht nur um eine Menge, sondern um eine geordnete Menge (eine Folge) handelt. Diese ordnenden Informationen sind von großer Bedeutung, wenn weiter unten die rauschfreie Codierung betrachtet wird.
Der Quantisierer und der Dequantisierer des Seitenanpassungsvektorquantisierers unterscheiden sich nicht von der allgemeinen Definition eines Finite-State- Vektorquantisierers bzw. -dequantisierers. Wie im vorangegangenen Abschnitt definiert, ist die Quantisiereroperation mit voller Suche mit dem Verzerrungsmaß d
und die Dequantisiereroperation ist p(y,s) = c derart, daß c &epsi; Cs und η (c,Cs) = y.
Es wird nun die Nächstzustandsfunktion des Seitenanpassungsvektorquantisierers im Zusammenhang mit der eigentlichen Codierung beschrieben. Bei einem Seitenanpassungsvektorquantisierer tragen lediglich zwei zurückliegende Reproduktionsblöcke zu der Erzeugung des Zustands bei. Unter der Annahme, daß die Codierung in einem Bild zuerst von links nach rechts (von West nach Ost) und dann von oben nach unten (von Norden nach Süden) fortschreitet, sind diese beiden Reproduktionsblöcke die Nachbarn des nächsten Quellenblocks in der Nord- und Westrichtung, wie in Figur 7 gezeigt. Der schraffierte Bereich in Figur 7 entspricht den, die zu der Zustandserzeugung für die Codierung des letzten Blocks in der Figur beitragen. Es sei angenommen, daß alle Bildpunktblöcke bis zu xi zu ..., l-2, i-1 i codiert worden sind und daß die Nächstzustandsfunktion auf die Codierung von xi+1 vorbereitet. Die Nächstzustandsfunktionsoperation f wird dann dargestellt als si+1 = f( i, i-j+1), wobei J nun die Anzahl von Blockspalten in einem Bild ist (d.h. die Anzahl von Blöcken, die in die Bildbreite passen). Insbesondere bildet die Nächstzustandsfunktion den westlichen Wiedergabesblock i in den Spaltenzustandsvektor ui+1 und den nördlichen Wiedergabesblock i-J+1 in den Zeilenzustandsvektor vi+1 ab. Bei gegebenem Spaltenzustandsraum U und Zeilenzustandsraum V werden der Spaltenzustandsvektor und der Zeilenzustandsvektor durch die Regel der kleinsten Verzerrung erzeugt. Das heißt,
si+1 = (ui+1,vi+1)
= f( i, i-J+1)
Da der Definitionabereich und der Zielbereich der Abbildung f sowohl endlich als auch (hinsichtlich der Mächtigkeit) relativ klein sind, ist die Abbildung f durch eine Nachschlagetabelle realisiert.
Es werden nun die vorgeschlagenen Seitenanpassungsvektorquantisierer-Codier- und Decodierverfahren als auch das Auslegungsverfahren beschrieben. Bei Codiersituationen mit realen Bildern gibt es verschiedene Bildpunktblöcke, auf die der Seitenanpassungsvektorquantisierer nicht angewendet werden kann, da der Zustand nicht richtig definiert werden kann. Es handelt sich hierbei um die Blöcke an der oberen und der linken Grenze des Bildes. Da, wenn diesen Blöcken Zustände willkürlich zugewiesen werden, die Codierverzerrung nicht nur für diese, sondern auch für die ihnen folgenden Blöcke vergrößert wird, werden sie getrennt von den übrigen behandelt. Als Ergebnis steigt die Rate des Codes geringfügig an (typischerweise um Bruchteile von einem Prozent). Bei Vernachlässigung dieses Anstiegs beträgt die Rate des Seitenanpassüngsvektorquantisierers log&sub2;N/(m n) Bit pro Bildpunkt. Zum Beispiel beträgt bei m = n = 4 (Figur 7) und N = 256 die Rate 1/2 Bit pro Bildpunkt.

SMVQ-Codierverfahren

(1) Codieren der ersten Zeile und der ersten Spalte von Bildpunktblöcken im Bild durch speicherlose VQ (z.B. VQ mit voller Suche) mit dem Supercodelexikon. Für den Rest der Blöcke werden lediglich Schritte 2 und 3 wiederholt.
(2) Erzeugen des Zustands aus dem westlichen und dem nördlichen Wiedergabesblock.
(3) Codieren eines Blocks unter Verwendung des Quantisierers mit dem entsprechenden Zustandscodelexikon.

SMVQ-Decodierverfahren

(1) Decodieren der ersten Zeile und der ersten Spalte von Bildpunktblöcken im Bild durch Tabellennachschlagen im Supercodelexikon. Für den Rest der Blöcke werden Schritte 2 und 3 wiederholt.
(2) Erzeugen des Zustands aus dem westlichen und dem nördlichen Wiedergabesblock.
(3) Decodieren eines Blocks unter Verwendung des Dequantisierers mit dem entsprechenden Zustandscodelexikon.
Das Auslegungsverfahren des Seitenanpassungsvektorquantisierers ist einfach, da die Auslegung des Zustandgcodelexikons keine Quellenstatistiken erfordert.

Codelexikon-Auslegungsverfahren

Für die Verwendung der vorliegenden Erfindung zum Codieren zweidimensionaler Informationen ist die Auslegung der Zustandscodelexika nach dem Prinzip der "Seitenanpassung" und "Uberlappungsanpassung" wesentlich. Die erfolgreiche Auslegung hängt von der angemessenen Auswahl aus der riesigen Anzahl möglicher quantisierter Vektoren ab.
Pro zu codierenden Block gibt es 16 Bildpunkte. Bei dem typischen System sind für jeden Bildpunkt 256 Graustufen möglich. Aus diesem Grund gibt es für jeden Block (256)16 bzw. mehr als 40 Milliarden mögliche Vektoren.
Beginnend mit zweidimensionalen Datenfeldern oder visuellen Bildern, die in gewisser Weise als für die beabsichtigte Verwendung des Systems typisch angesehen werden können, muß bestimmt werden, welche Codevektoren der (256)¹&sup6; Möglichkeiten am repräsentativsten sind.
Im Gegensatz zum Auslegungsverfahren des Bezugsdokuments von Aravind und Gersho, das mit unterschiedlichen Zustandscodelexika beginnt, die dann zufälligerweise zusammengenommen ein Supercodelexikon umfassen, beginnt das Auslegungsverfahren der vorliegenden Erfindung, wie in Figur 4 gezeigt, mit dem Supercodelexikon als den besten 1024 Repräsentanten der in den Lernbildern gefundenen Bildpunktblöcke. Es kann jedes der gutbekannten Optimierungsverfahren, wie z.B. das Verfahren der maximalen Ähnlichkeit, wie es auf Vektoren angewendet wird, verwendet werden.
Als nächstes wird unter Verwendung der Grundsätze der "Seitenanpassung" und "Uberlappungsanpassung" zur Ausbildung der unterschiedlichen Zustandscodelexika aus dem Supercodelexikon wie folgt vorangeschritten:
Aus den über 10&sup6; möglichen Paaren rechter Spalten und unterer Zeilen der 10²&sup4; repräsentativen Blöcke des Supercodelexikons (um diejenigen zu erhalten, die für die oben erwähnte "Anpassung" verwendet werden, um zu codierende zweidimensionale Informationsblöcke einzugeben), werden diejenigen Paare von Spalten und Zeilen, die die Blöcke des Supercodelexikons am besten repräsentieren, wie folgt ausgewählt:
Für jedes Kandidatenpaar derartiger 10&sup6; Paare bilden die 256 am besten passenden Blöcke, deren oberste Zeile mit dem Zeilenabschnitt des Kandidatenpaars paarig ist und wobei die linke Spalte jedes Blocks mit dem Spaltenabschnitt des Kandidatenpaars paarig ist, ein vorläufiges Zustandscodelexikon. Wiederum können die am besten angepaßten Blöcke für jedes Kandidatenpaar durch irgendeines der gutbekannten Optimierungsverfahren für Vektoren, zum Beispiel minimaler Verzerrung der Seitenanpassung, bestimmt werden.
Aus den über 10&sup6; möglichen Zustandscodelexika wird eine reduzierte Menge = (128)² = 16.000 (ungefähr) als diejenige ausgewählt, die für die 256 Elemente von jedem die besten Summenergebnisse (kleinste Summenverzerrungen) aufweist, bei Anpassung an die Paarkombinationen aus 128 Zeilenabschnitten und den 128 Spaltenabschnitten.
Die Zustandscodelexika sind in einem Speicher oder in einer Speichervorrichtung, der bzw. die die Menge 19 von Zustandscodelexika in Figur 1 umfaßt, dargestellt.

Überlappungsanpassungsvektorquantisierer

Der Überlappungsanpassungsvektorquantisierer (OMVQ = Overlap-match vector quantizer) ist innerhalb einer Klasse von Finite-State-Vektorquantisierern, die dem Seitenanpassungs-Vektorquantisierer recht ähnlich ist. Im Gegensatz zu allen anderen VQ für Bilder jedoch, einschließlich dem Seitenanpassungsvektorquantisierer, werden die Quellen-(Bildpunkt-)Blöcke von OMVQ mit teilweisen Überlappungen ausgebildet. Mit anderen Worten, falls die Überlappungsbreite und -höhe no Spalten bzw. mo Zeilen beträgt, sind die ersten no Spalten eines Quellenblocks die Kopien der letzten no Spalten des Quellenblocks auf der linken Seite (im Westen), und die ersten mo Zeilen eines Quellenblocks sind die Kopien der letzten mo Zeilen des Quellenblocks direkt darüber (im Norden), mit Ausnahme der Blöcke entlang den Grenzen der Bilder. Diese Situation ist in Figur 8 für den Fall von m = n = 4 und mo = no = 1 dargestellt.
Da der Aufbau von OMVQ dem des Seitenanpassungs vektorquantisierers sehr ähnlich ist, werden die Bausteine der Überlappungsanpassungsvektorquantisierer durch Ausleihen der im vorausgegangenen Abschnitt eingeführten Notationen beschrieben. Das Blockdiagramm der Überlappungsanpassungsvektorquantisierer wird in Figuren 1 und 3 gezeigt. Für OMVQ sollen Quellblöcke der Größe m mal n betrachtet werden. Jeder Zustand im Zustandsraum wird dann durch ein Paar Blöcke dargestellt: ein Spaltenzustandsblock genannter m-mal-no-Block und ein Zeilenzustandsblock genannter m&sub0;-mal-n-Block. Das heißt, ein Zustand hat die Form (u,v), wobei u ein m-mal-no-Spaltenzustandsblock und v ein mo-mal-n-Zeilenzustandsblock ist. Die Spalten- und Zeilenzustandsblöcke sollen Alphabete u und v aufweisen, genannt der Spaltenzustandsraum bzw. Zeilenzustandsraum. Wie bei SMVQ ist der Zustandsraum S von OMVQ das kartesische Produkt u x v. Die Bedeutung dieser Spalten- und Zeilenzustandsblöcke liegt darin, daß sie die Wiedergabesbildpunkte darstellen, die den zu codierenden Quellenblock überlappen.
Das Zustandscodelexikon von OMVQ ist wie folgt definiert. Bei einem gegebenen Supercodelexikon C und einem Zustand s = (u,v) ist das entsprechende Zustandscodelexikon als die Untermenge von C definiert, deren Elemente im Überlappungsbereich mit u und v am besten "übereinstimmt". Um die Zustandscodelexika von OMVQ zu beschreiben, wird die Anpassungsverzerrung e neu definiert und als die Überlappungsanpassungsverzerrung bezeichnet. Als eine Erweiterung der weiter oben lingeführten Notationen sollen [x] 1, l2, ..., lj und [x] 1, l2, ..., lj die m-mal-j- und j-mal-n-Blöcke kennzeichnen, die durch das Sammeln der Spalten l&sub1; bis lj bzw. das Sammeln der Zeilen l&sub1; bis lj gebildet werden. Bei gegebenem Zustand s = (u,v) und einem m-mal-n-Block x ist die Überlappungsanpassungsverzerrung bei einem bestimmten Verzerrungsmaß d und Konstanten a und b definiert als e(s,x) = ad(u, [x] 1, l2, ..., lno) + bd(v, [x] 1, l2, ..., lmo) Die Definition der Zustandscodelexika von OMVQ ist dann die gleiche wie die bei SMVQ, wobei die Seitenanpassungsverzerrung durch die Überlappungsanpassungsverzerrung ersetzt ist. Das heißt, bei einem gegebenen Supercodelexikon C und einem Zustand s = (u,v) ist das Zustandscodelexikon Cs für den Zustand s als Cs = (c , c , ...,c ) definiert, derart daß die Elemente von Cs den Bedingungen (A), (B) und (C) des vorausgegangenen Abschnitts genügen. Es soll wieder hervorgehoben werden, daß die Elemente von jedem Zustandscodelexikon sequentiell geordnet sind.
Wie schon gezeigt worden ist, unterscheiden sich die Zustandscodelexika von OMVQ, der Quantisierer und der Dequantisierer von OMVQ nicht von denjenigen der allgemeinen FSVQ.
Zur Beschreibung der Nächstzustandsfunktion von OMVQ sei angenommen, daß alle teilweise überlappten Quellblöcke bis zu xi zu ..., i-2, i-1, i codiert worden sind. Der Zustand si+1 wird dann durch die Nächstzustandsfunktion f als si+1 = f( i, i-J+1) erzeugt, wobei J nun die Anzahl der teilweise überlappenden Blockspalten in einem Bild ist (d.h. die Anzahl der teilweise überlappenden Blöcke, die in die Bildbreite passen). Falls n die Anzahl der Bildpunktspalten im Bild kennzeichnet, kann J durch J = ( -n)/(n-no) + 1 berechnet werden. Insbesondere bildet die Nächstzustandsfunktion den westlichen Wiedergabesblock i in den Spaltenzustandsblock ui+1 und den nördlichen Wiedergabesblock i-J+1 in den Zeilenzustandsblock vi+1 ab. Bei gegebenem Spaltenzustanderaum u und Zeilenzustandsraum v werden der Spaltenzustandsblock und der Zeilenzustandsblock durch die Regel der minimalen Verzerrung erzeugt. Das heißt, si+1 = (ui+1,vi+1)
= f( i, i-J+1)
Da der Definitionsbereich und der Zielbereich der Abbildung f sowohl endlich als auch (hinsichtlich der Mächtigkeit) relativ klein sind, wird die Abbildung f durch eine Nachschlagetabelle realisiert. Die Bildpunkte, die zu der Zustandserzeugung beitragen, sind in Figur 8 als die schraffierte Fläche gezeigt.
Wie wohl festzustellen war, ist die Definition von OMVQ parallel zu der von SMVQ. Insbesondere wenn mo = no = 1 ist, kann man OMVQ als SMVQ mit einem einfachen Vorprozessor betrachten. Das auf ein Bild angewendete OMVQ-Verfahren ist mit dem auf das erweiterte Bild angewendeten SMVQ-Verfahren insbesondere dann identisch, wenn der Vorprozessor das "erweiterte Bild" durch Duplizieren von Bildpunktzeilen und -spalten, die sich in dem Überlappungsbereich von OMVQ befunden hätten, aufbaut. Es sei allerdings darauf hingewiesen, daß auch das rekonstruierte Bild erweitert ist.
Um das Wiedergabesbild wiederzugewinnen, das die Größe des Quellenbildes aufweist, wird ein weiterer Baustein, Überlappungsentfernungsfunktion genannt, eingeführt, der jedes Paar duplizierter Bildpunkte in einen Wiedergabesendbildpunkt abbildet. Aufgrund des Quantisierungsfehlers sind die duplizierten Bildpunkte in der Wiedergabe mit ihren Zwillingsbrüdem nicht identisch. Mit anderen Worten liegen für jeden duplizierten Bildpunkt zwei unterschiedliche Wiedergabesversionen vor. Es ist durchaus denkbar, daß diese beiden Wiedergabesversionen über den Quellenbildpunkt mehr Informationen enthalten als eine einzelne Wiedergabe. Die Überlappungeentfernungsfunktion sollte aus diesem Grund nicht einfach eine der beiden Wiedergabesversionen verwerfen. Genauer gesagt sei die Überlappungsbeseitigungsfunktion h eine Abbildung, die auf jedes Zwillingspaar von Wiedergabesbildpunkten zutrifft, das im Codierer dupliziert wird und einen Wiedergabesendbildpunkt erzeugt. Falls x&sub1; und x&sub2; ein Zwillingspaar von Wiedergabesbildpunkten kenn zeichnen, wird der Wiedergabesendbildpunkt als = h(x&sub1;, x&sub2;) dargestellt. Ein Beispiel der Überlappungsbeseitigungsfunktion ist h(x&sub1;,x&sub2;) = (x&sub1; + x&sub2;)/2.
Es werden nun die OMVQ-Codier- und Decodierverfahren als auch das Auslegungsverfahren beschrieben. Bei gegebenen Zustandscodelexika und gegebener Nächstzustandsfunktion ist das Codierverfahren von OMVQ mit dem von SMVQ identisch, mit der Ausnahme, daß die Quellenblöcke einander teilweise überlappen. Auf der anderen Seite benotigt das Decodierverfahren von OMVQ im Vergleich zum SMVQ-Decodierverfahren einen Schritt mehr, nämlich die Überlappungsbeseitigungsoperation. Das Decodierverfahren von OMVQ ist somit ganz einfach das von SMVQ, gefolgt von der Überlappungsbeseitigungsoperation.
Das Auslegungsverfahren von OMVQ ist wiederum dem von SMVQ ähnlich und kann durch Figur 4 dargestellt werden.

OMVQ-Auslegungsverfahren

(1) Supercodelexikon:
Entwerfen eines Supercodelexikons unter Verwendung irgendeines Codelexikonauslegungsalgorithmus.
(2) Zustandsraum:
Erzeugen von Spaltenzustandsraum und Zeilenzustandsraum durch einen Codelexikonauslegungsalgorithmus unter Verwendung der letzten na Spalten bzw. der letzten mo Zeilen des Codewortes im Supercodelexikon als die Lernmengen.
(3) Zustandscodelexikon:
Auslegen eines Zustandscodelexikons durch Wählen der Untermenge des Supercodelexikons, die den Bedingungen der Zustandscodelexika, oben beschrieben unter "Auslegungsverfahren" genügt. Wenn mo = no = 1 ist, können Supercodelexikon, Zustandscodelexika und Zustandsraum zwischen SMVQ und OMVQ austauschbar verwendet werden.
Die Frage des rauschfreien Codierens des Codewortindexes zur Übertragung wird nun wiederaufgegriffen.
Wegen der hohen Korrelation von Bildern und dem Ordnen in jedem Zustandscodelexikon durch die Anpassungsverzerrung kann man sich denken, daß die Kanalsymbolver teilung einen monoton abnehmenden Trend annimmt. Experimentell wurde festgestellt, daß die Kanalsymbolverteilung für gewisse Konstanten a und b tatsächlich in der Nähe von {b µ-a: µ = 1,2,...,N} ist. Im folgenden Text wird für die schnell abklingenden Verteilungen eine Klasse von rauschf reien Codes mit nur wenigen Pegeln vorgeschlagen, und es wird gezeigt, daß sie fast optimal sind.
Bei dem vorgeschlagenen rauschfreien Code handelt es sich im Grunde um den für die Treppenannäherung an schnell abklingende Verteilungen ausgelegten, gut bekann ten Huffman-Code. Wenn es sich bei der Anzahl von Symbolen nicht um einen Exponent von 2 handelt, können sich der vorgeschlagene rauschfreie Code und der Huffman Code für die Annäherung jedoch geringfügig unterscheiden. Bei einer gegebenen schnell abnehmenden Wahrscheinlichkeits verteilung P, (P&sub1;, P&sub2;,...,PN) soll die Treppenannäherung derart definiert werden, daß für j = 0,1,2,...,log&sub2; N unter der Annahme, daß log&sub2; N eine ganze Zahl ist,
(A) µ = θ, für alle 2j-1 < µ, θ ≤ 2j
Wegen Teil (B) der Definition ist ebenfalls eine Wahrscheinlichkeitsverteilung. Bei großem N ist die Auslegung des Huffman Codes für im allgemeinen keine einfache Aufgabe. Da allerdings die Verteilung in einer besonderen Form vorliegt, kann die Auslegung des Huffman Codes wie folgt stark vereinfacht werden. Zuerst wird ein Huffman-Vorsatzcode für die Menge von Wahrscheinlichkeiten ausgelegt,
Um Symbole innerhalb des Summierungsintervalls zu unterscheiden, wird an den Huffman-Vorsatzcode für jedes j ein einfacher binärer Code fester Länge, Nachsatz genannt, angehängt. Für jedes j beträgt die Anzahl von Symbolen innerhalb des Summierungsintervalls [2j-1], wobei [x] die kleinste ganze Zahl kennzeichnet, aber nicht kleiner als x, und somit ist die Länge des Nachsatzes max {j-1, 0}. In diesem Zusammenhang hat "Vorsatzcode" zwei Bedeutungen: die eine ist, daß jedes binäre Codewort in einem Vorsatzcode kein Vorsatz in irgendeinem anderen binären Codewort in dem Code ist, und die andere ist, daß es sich um einen Vorsatz zu dem Nachsatz handelt. Der resultierende rauschfreie Code ist auch ein Vorsatzcode im ersteren Sinne. Es ist außerdem nicht schwierig, zu zeigen, daß, wenn N ein Exponent von 2 ist, der vorge schlagene rauschfreie Code für die Verteilung P optimal ist.

Codebuch-Auslegung

In Figur 4 wird anhand eines Flußdiagramms das Verfahren gezeigt, mit dem das Supercodelexikon und alle daraus abgeleiteten Zustandscodelexika ausgelegt werden. Zunächst sollten die Lernbilder derart ausgewählt werden, daß sie hinsichtlich einer bestimmten wichtigen Eigenschaft den zu übertragenden Bildern statistisch ähnlich sind. Diese werden als Lernbilder bezeichnet. Im ersten Schritt werden diese Lernbilder im Schritt 61 in kleine Blöcke geteilt. Diese Lernblöcke werden dann über den Lloyd-Anhäufungsalgorithmus angehäuft.
Das Endergebnis des Anhäufungsverfahrens ist, daß es den Aufbau eines Supercodelexikons von vektorquantisierten Codes, z.B. ganze 1024, gestattet. Im nächsten Schritt zum Zusammenfügen von Zustandscodelexika aus dem Supercodelexikon wird mit dem Ableiten der Eigenschaften begonnen, womit aus dem Supercodelexikon verschiedene Komponenten für die Zustandscodelexika ausgewählt werden können. Der erste Schritt bei diesem Verfahren wird in Schritt 63 illustriert, bei dem es um die Auswahl der letzten Bildpunktspalte für jedes Codewort geht, das in dem Supercodelexikon einen Block darstellt. Diese Mengen von letzten Bildpunktspalten werden gemäß dem Lloyd- Anhäufungsalgorithmus im Schritt 64 angehäuft. Das Parallelverfahren, bei dem die letzte Bildpunktzeile ausgewählt wird, enthält die parallelen Schritte 65 und 66; und der Anhäufungsschritt 66 für die Zeilenvektoren wählt wiederum aus dem Supercodelexikon die N Codeworte mit minimaler Anpassungsverzerrung aus, so daß aus diesen beiden parallelen Verfahren schließlich Zustandscodelexika erhalten werden, die jeweils eine Größe N aufweisen, z.B. N=256. Insbesondere werden die Informationen in den angehäuften Codeworten wie folgt organisiert: Für jedes u bzw. v, bei denen es sich um Wertepaare mit u im Spaltenzustandsraum und v im Zeilenzustandsraum handelt, werden aus dem Supercodelexikon die N Codeworte mit minimaler Anpassungsverzerrung ausgewählt. Die Auswahl von Codeworten mit minimaler Anpassungsverzerrung, wie im Schritt 67 erfordert, beinhaltet Anpassungsverzerrungsberechnung und -suche, die rechenintensiv sind, um zum Beispiel 16.000 Zustandscodelexika zu erstellen. Es ist vorteilhaft, daß diese intensive Berechnung mit analogen Bildern vor dem Echtzeitbetrieb von Sender 10 aus Figur 1 erreicht wird.
In Figur 5 wird ein Flußdiagramm gezeigt, durch das der Betrieb von Codierer 41 aus Figur 1 auf geringfügig unterschiedliche Weise erläutert werden kann, um daß Verständnis zu fördern. Die Schritte hier haben offensichtliche Analogien in dem Block in Figur 1. So zum Beispiel teilt Schritt 71 das zu übertragende eingegebene Bild in kleine Blöcke von vier-mal-vier-Bildpunkten. Schritt 72 sucht den nächsten Nachbarn des Codeworts im gegenwärtigen Zustandslexikon, gemäß der schon beschriebenen Technik der Suche nach dem nächsten Nachbarn mit dem kleinsten mittleren quadratischen Fehler. Der aus dem Zustandscodelexikon abgeleitete resultierende Codewortindex wird dann im Schritt 73 wieder in sein Codewort umgewandelt, um die Vergangenheitsbildstatistik bereitzustellen, die, wie oben mathematisch beschrieben, für die Techniken der kleinsten Kantenunterbrechung oder der kleinsten Überlappungsunterbrechung benötigt wird. Der Codewortindex wird auch auf den binären Übertragungscodierschritt 74 angewendet, um in Schritt 75 dem Index ein rauschfreies, binäres Codewort variabler länge zuweisen zu können. Das aus dem Tabellennachschlagen von Schritt 73 resultierende Codewort (analog zum Dequantisierer 13) wird auf die Logikschaltung 42 von Figur 1 angewendet, wie in den Schritten von Figur 6 gezeigt. Es sei darauf hingewiesen, daß Figuren 5 und 6 zueinander passen. Wie in Figur 5 für die Seitenanpassungsoperation benachbarter Spalten gezeigt, führt dieser Schritt 81 eine Verzögerung um einen Block ein, so daß der codierte Block links von dem gegenwartig codierten Bildpunktblock x während der Codierung von x dargestellt werden muß. Jener codierte Block unmittelbar links von Bildpunktblock x ist in der letzten vorausgegangenen Bildpunktspalte, wobei es sich dabei, wie in Schritt 83 festgestellt, um den nächsten Nachbarn im Spaltenzustandsraum handelt. Für jenen Spaltenzustand u wird dann ein aus den analogen Blöcken 84, 85 und 86 abgeleiteter ähnlicher Vektor v eingesetzt, was zu einer größeren Verzögerung führt, so daß der Block in der zuvor codierten Zeile oder Menge von Zeilen für die Kontinuitätsprüfung verwendet wird, was zu einem Zeilenzustandsvektor v führt (der den nächsten Nachbarn im niedrigeren Zustand darstellt). Danach wird durch Tabellennachschlagen das entsprechende Zustandscodelexikon für die Vektoren u und v gesucht, was im Schritt 87 zur Wahl eines Zustandscodelexikons führt. An dieser Stelle sei darauf hingewiesen, daß der Unterschied zwischen Seitenanpassung und Überlappungsanpassung folgender ist: Bei der erfindungsgemäßen Seitenanpassungsvektorquantisierung werden die Bildpunktblöcke der Bilder nicht überlappt, so daß Zeilen 1, 2, 3 und 4 die erste Menge von Blöcken, Zeilen 5, 6, 7 und 8 die zweite Menge von Blöcken usw. darstellen, und ein ähnliches Prinzip gilt für die Spalten. Bei der Überlappungsanpassungsvektorquantisierung stellen Zeilen 1, 2, 3 und 4 die erste Menge von Blöcken dar, danach stellen Zeilen 4, 5, 6 und 7 die zweite Menge von Blöcken dar, so daß die Bildpunkte in Zeile 4 nun nach angemessenen Verzögerungen sequentiell derart in unterschiedliche Blöcke codiert werden, daß das Ausmaß der Helligkeitsveränderung in ihrer Codierung von Zeile zu Zeile 80 klein wie möglich gehalten wird. Die Veränderung wird durch die Überlappung auf einem Mindestmaß gehalten, doch wird eine gewisse Veränderung durch die Tatsache erzwungen, daß im Block, andere Werte vorliegen, zum Beispiel aus Zeile 3. Diese beiden Techniken stehen dahingehend im Gegensatz zu der Technik von Aravind und Gersho, daß letzterer das Ausmaß der Kontinuität zwischen Bildpunkten über eine Kante hinweg betont, die möglicherweise durch den Block hindurchläuft, ohne zu den Kanten der jeweiligen Blöcke selbst zu laufen. Im Gegensatz dazu verwendet das erfindungsgemäße Verfahren die örtliche Nachbarschaft ohne das Ausmaß an Abschwächung, das beim Umwandeln von Bild punktwerten in indirekte Informationen auftritt, wie dies bei Aravind und Gersho der Fall ist.

Claims

1. Verfahren zum Codieren eines Signals zum Bilden eines codierten Signals, wobei das Signal einen bestimmten Block in einer Gruppe von in Zeilen und Spalten angeordneten Blöcken darstellt, wobei jeder Block in der Gruppe von Blöcken eine Gruppe von ebenfalls in Zeilen und Spalten angeordneten Bildpunkten umfaßt und das Verfahren folgende Schritte umfaßt:

a. Auswählen, allein basierend auf dem Block, der sich in den mehreren Blöcken zwar in der gleichen Spalte wie der bestimmte Block, aber in der unmittelbar vorangehenden Zeile befindet, und basierend auf dem Block, der sich in den mehreren Blöcken zwar in der dem bestimmten Block unmittelbar vorangehenden Spalte, aber in der gleichen Zeile befindet, eines Codelexikons aus mehreren Codelexika, wobei jedes Codelexikon Codeworte umfaßt und wobei jedes Codewort einen zugeordneten Index aufweist;

b. Auswählen, basierend auf einem vorbestimmten Fehlerkriterium, eines Codewortes, das dem bestimmten Block am nächsten kommt, in dem ausgewählten Codelexikon;

c. Bilden des codierten Signals auf der Basis des dem ausgewählten Codewort zugeordneten Indexes; und

d. Ubertragen des codierten Signals über einen Nachrichtenkanal; dadurch gekennzeichnet, daß

das Auswählen eines Codelexikons allein auf der Basis der letzten Zeile von Bildpunkten in dem Block, der sich in den mehreren Blöcken zwar in der gleichen Spalte wie der bestimmte Block, aber in der unmittelbar vorangehenden Zeile befindet, und der letzten Spalte von Bildpunkten in dem Block, der sich in den mehreren Blöcken zwar in der dem bestimmten Block unmittelbar vorangehenden Spalte, aber in der gleichen Zeile befindet, erfolgt.

2. Verfahren nach Anspruch 1, wobei der Schritt des Auswählens eines Codelexikons folgende Schritte umfaßt:

a. Bilden eines ersten Codewortes basierend auf einem ersten Index, wobei der erste Index demjenigen Codewort in dem Codelexikon zugeordnet ist, das dazu verwendet wird, den Block zu codieren, der sich zwar in der gleichen Spalte wie der bestimmte Block, aber in der unmittelbar vorangehenden Zeile befindet;

b. Bilden eines zweiten Codewortes basierend auf einem zweiten Index, wobei der zweite Index demjenigen Codewort in dem Codelexikon zugeordnet ist, das dazu verwendet wird, den Block zu codieren, der sich zwar in der dem bestimmten Block unmittelbar vorangehenden Spalte, aber in der gleichen Zeile befindet;

c. Erzeugen eines Zeilenzustandsausgangssignals durch Verzögern des ersten Codewortes um eine Zeile und Filtern des ersten Codewortes, um nur die letzte Zeile von Bildpunkten in der Gruppe von Bildpunkten in dem Block durchzulassen, der sich zwar in der gleichen Spalte wie der bestimmte Block, aber in der unmittelbar vorangehenden Zeile befindet;

d. Erzeugen eines Spaltenzustandsausgangssignals durch Verzögern des zweiten Codewortes um eine Spalte und Filtern des zweiten Codewortes, um nur die letzte Spalte von Bildpunkten in der Gruppe von Bildpunkten in dem Block durchzulassen, der sich zwar in der dem bestimmten Block unmittelbar vorangehenden Spalte, aber in der gleichen Zeile befindet;

e. Auswählen des Codelexikons basierend auf dem Zeilenzustandsausgangssignal und den Spaltenzustandsausgangssignalen.

3. Verfahren nach Anspruch 1, wobei der Schritt des Auswählens eines Codewortes folgende Schritte umfaßt:

a. Erzeugen eines Supercodelexikons basierend auf einer von einer Menge von Lernblöcken abgeleiteten Menge von Codeworten, wobei jeder der Lernblöcke eine Gruppe von Bildpunkten umfaßt, und

b. Erzeugen mehrerer Codelexika aus dem Supercodelexikon durch ein Verfahren, das folgende Schritte umfaßt:

i. Paarbildung zwischen demjenigen Teil jedes der Codeworte in den Lernblöcken, der die letzte Zeile von Bildpunkten in den Lernblöcken darstellt, und demjenigen Teil jedes der Codeworte in den Lernblöcken, der die letzte Spalte von Bildpunkten in den Lernblöcken darstellt,

ii. Auswählen, für jedes der Paare, einer gemäß einem Fehlerkriterium am besten zu dem Paar passenden Untermenge der Menge von Codeworten, wobei die Untermenge von Codeworten das jedem der Paare zugeordnete Codelexikon bildet, und

iii. weiteres Auswählen einer Untermenge der Codelexika, wobei die Codeworte jedes der ausgewählten Codelexika in der Untermenge von Codelexika einem Verzerrungsmaß genügen.

4. Verfahren zum Decodieren eines von einem Nachrichtenkanal empfangenen Signals zum Bilden eines decodierten Signals, wobei das Signal einen einem Codewort zugeordneten Index darstellt, wobei das Codewort einen bestimmten Block in einer Gruppe von in Zeilen und Spalten angeordneten Blöcken darstellt, wobei jeder Block eine Gruppe von ebenfalls in Zeilen und Spalten angeordneten Bildpunkten umfaßt und das Verfahren folgende Schritte umfaßt:

a. Empfangen des Signals von dem Nachrichtenkanal;

b. Auswählen eines Codelexikons aus mehreren Codelexika, wobei in jedem Codelexikon mehrere Codeworte gespeichert sind und wobei ein Index jedes der Codeworte identifiziert, wobei das Auswählen allein auf der Basis der Blockzeile, die sich zwar in der gleichen Spalte wie der bestimmte Block, aber in der unmittelbar vorangehenden Zeile befindet, und auf der Basis des Blocks, der sich in der dem bestimmten Block zwar unmittelbar vorangehenden Spalte, aber in der gleichen Zeile befindet, erfolgt;

c. Bestimmen des Codewortes für den bestimmten, von dem Index identifizierten Block nur aus den Codeworten in dem ausgewählten Codelexikon; und

d. Bilden des decodierten, Codewort-basierenden Signals; dadurch gekennzeichnet, daß

das Auswählen allein auf der Basis der letzten Zeile von Bildpunkten im Block, der sich zwar in der gleichen Spalte wie der bestimmte Block, aber in der unmittelbar vorangehenden Zeile befindet, und auf der Basis der letzten Spalte von Bildpunkten im Block, der sich zwar in der dem bestimmten Block unmittelbar vorangehenden Spalte, aber in der gleichen Zeile befindet, erfolgt.

5. Verfahren nach Anspruch 4, wobei der Schritt des Auswählens eines Codelexikons folgende Schritte umfaßt:

a. Bilden eines ersten Codewortes basierend auf einem ersten Index, wobei der erste Index demjenigen Codewort in dem Codelexikon zugeordnet ist, das dazu verwendet wird, den Block zu codieren, der zwar sich in der gleichen Spalte wie der bestimmte Block, aber in der unmittelbar vorangehenden Zeile befindet;

d. Erzeugen eines Spaltenzustandsausgangssignals durch Verzögern des zweiten Codewortes um eine Spalte und Filtern des zweiten Codewortes, um nur die letzte Spalte von Bildpunkten in der Gruppe von Bildpunkten in dem Block durchzulassen, der sich zwar in der dem bestimmten Block unmittelbar vorangehenden Spalte, aber in der gleichen Zeile befindet; und

6. Verfahren nach Anspruch 4, wobei der Schritt des Auswählens eines Codelexikons folgende Schritte umfaßt:

a. Erzeugen eines Supercodelexikons basierend aüf einer von einer Menge von Lernblöcken abgeleiteten Menge von Codeworten, wobei jeder der Lernblöcke eine Gruppe von Bildpunkten umfaßt; und

i. Paarbildung zwischen demjenigen Teil jedes der Codeworte in dem Lernblock, der die letzte Zeile von Bildpunkten in den Lernblöcken darstellt, und demjenigen Teil jedes der Codeworte in den Lernblöcken, der die letzte Spalte von Bildpunkten in den Lernblöcken darstellt,

ii. Auswählen, für jedes der Paare, einer gemäß einem Fehlerkritenum am besten zu dem Paar passenden Untermenge der Menge von Codeworten, wobei die Untermenge von Codeworten das jedem der Paare zugeordnete Codelexikon bildet, und

7. System zum Codieren eines Signals zum Bilden eines codierten Signals, wobei das Signal einen bestimm ten Block in einer Gruppe von in Zeilen und Spalten angeordneten Blöcken darstellt, wobei jeder Block in der Gruppe von Blöcken eine Gruppe von ebenfalls in Zeilen und Spalten angeordneten Bildpunkten umfaßt und das System folgendes umfaßt:

a. Mittel zum Auswählen, allein basierend auf dem Block, der sich in den mehreren Blöcken zwar in der gleichen Spalte wie der bestimmte Block, aber in der unmittelbar vorangehenden Zeile befindet, und auf dem Block, der sich in den mehreren Blöcken zwar in der dem bestimmten Block unmittelbar vorangehenden Spalte, aber in der gleichen Zeile befindet, eines Codelexikons aus mehreren Codelexika, wobei jedes Codelexikon Codeworte umfaßt und wobei jedes Codewort einen zugeordneten Index aufweist;

b. Mittel zum Auswählen, basierend auf einem vorbestimmten Fehlerkritenum, eines Codewortes, das dem bestimmten Block am nächsten kommt, in dem ausgewählten Codelexikon;

c. Mittel zum Bilden des codierten Signals auf der Basis des dem ausgewählten Codewort zugeordneten Indexes; und

d. Mittel zum Übertragen des codierten Signals über einen Nachrichtenkanal; dadurch gekennzeichnet, daß

das Mittel zum Auswählen eines Codelexikons angeordnet ist, um das allein auf der letzten Zeile von Bildpunkten in dem Block, der sich in den mehreren Blöcken zwar in der gleichen Spalte wie der bestimmte Block, aber in der unmittelbar vorangehenden Zeile befindet, und der letzten Spalte von Bildpunkten in dem Block, der sich in den mehreren Blöcken in der dem bestimmten Block zwar unmittelbar vorangehenden Spalte, aber in der gleichen Zeile befindet, basierende Codelexikon auszuwählen.

8. System zum Decodieren eines von einem Nachrichtenkanal empfangenen Signals zum Bilden eines decodierten Signals, wobei das Signal einen einem Codewort zugeordneten Index darstellt, wobei das Codewort einen bestimmten Block in einer Gruppe von Blöcken darstellt, wobei jeder Block eine Gruppe von Bildpunkten umfaßt und das System folgendes umfaßt:

a. Mittel zum Empfangen des Signals von dem Nachrichtenkanal;

b. Mittel zum Auswählen eines Codelexikons aus mehreren Codelexika, wobei in jedem Codelexikon mehrere Codeworte gespeichert sind und wobei ein Index jedes der Codeworte identifiziert, wobei das Auswählen allein auf der Basis des Blocks, der sich zwar in der gleichen Spalte wie der bestimmte Block, aber in der unmittelbar vorangehenden Zeile befindet, und auf der Basis des Blocks, der sich in der dem bestimmten Block zwar unmittelbar vorangehenden Spalte, aber in der gleichen Zeile befindet, erfolgt;

c. Mittel zum Bestimmen des Codewortes für den bestimmten, von dem Index identifizierten Block nur aus den Codeworten in dem ausgewählten Codelexikon; und

d. Mittel zum Bilden des decodierten Codewortbasierenden Signais, dadurch gekennzeichnet, daß

das Mittel zum Auswählen angeordnet ist, das allein auf der letzten Zeile von Bildpunkten im Block, der sich zwar in der gleichen Spalte wie der bestimmte Block, aber in der unmittelbar vorangehenden Zeile befindet, und auf der Basis der letzten Spalte von Bildpunkten im Block, der sich zwar in der dem bestimmten Block unmittelbar vorangehenden Spalte, aber in der gleichen Zeile befindet, basierende Auswählen auszuführen.