DE69635073T2

DE69635073T2 - Bildcodierverfahren und -system zum Erzeugung arithmetischen Codes mit reduzierter Bitrate

Info

Publication number: DE69635073T2
Application number: DE69635073T
Authority: DE
Inventors: Takahiro Minato-ku Hongu
Original assignee: NEC Corp
Current assignee: NEC Corp
Priority date: 1995-11-08
Filing date: 1996-11-07
Publication date: 2006-06-01
Anticipated expiration: 2016-11-08
Also published as: JPH09135358A; EP0773666B1; EP0773666A2; EP0773666A3; US5867600A; DE69635073D1

Description

Die vorliegende Erfindung betrifft einen Bildcodierer zum arithmetischen Codieren von Bilddaten und insbesondere einen Bildcodierer zur arithmetischen Bildcodierung, wobei binäre Bilddaten für ein Bild komprimiert werden, das Textbuchstaben, Diagramme, Rasterbilder, usw. enthält.
Es wird ein JBIG-(Joint Bi-level Image coding experts Group)Codierschema als internationales Standard-Codierschema zum Komprimieren von Bi-Level-Standbilddaten vorgeschlagen, das auf Bildcodierer anwendbar ist. Das Codierschema verwendet als Standard für einen auf einem arithmetischen Code basierenden Entropiecode den QM-Code, der auf der Basis eines Q-Codes und eines Me-1-Codes entwickelt wurde.
Ein Codierer gemäß dem JBIG-Standard verwendet normalerweise eine Symbolauftrittswahrscheinlichkeitstabelle, um die Anordnung oder Struktur zu vereinfachen. In einem derartigen Codierer ist die Codiereffizienz erhöht, d.h., die Code-Bitrate wird niedriger, wenn ein Fehler zwischen einer von der Tabelle erhaltenen vorausgesagten Symbolauftrittswahrscheinlichkeit und einer tatsächlichen Auftrittswahrscheinlichkeit kleiner wird. Dementsprechend sind in der ungeprüften japanischen Patentveröffentlichung Nr. Hei 5-183759 ein Codierer und ein Decodierer beschrieben, die mehrere derartige Tabellen aufweisen, wobei während des Codier- und des Decodiervorgangs gemäß dem Bildtyp, der jede Seite eines Dokuments bildet, eine Tabelle selektiv verwendet wird.
In jüngster Zeit enthalten Dokumentseiten typischerweise Rasterbilder und/oder Diagramme sowie Textbuchstaben. Außerdem kann eine einzelne Seite Fotos enthalten, die durch Dithern, Fehlerdiffusion, usw. in einer Pseudo-Gradation oder Grauabstufung dargestellt sind und sich daher in einigen Eigenschaften unterscheiden, z.B. in statistischen Eigenschaften. Außerdem werden sich in einem in einer Dokumentseite enthaltenen einzelnen Bild Bereiche mit homogener Bildpunkt- oder Rasterdichte und Bereiche, in denen die Bildpunkt- oder Rasterdichte sich an einer Kontur drastisch ändert, hinsichtlich der Eigenschaften unterscheiden. Daher entsteht beim Stand der Technik ein Problem dahingehend, daß Bereiche mit verschiedenen Eigenschaften in einer Seite unter Verwendung der gleichen Symbolauftrittswahrscheinlichkeitstabelle codiert und decodiert werden, d.h. alle Bereiche einer Seite werden nicht notwendigerweise optimal codiert oder decodiert.
Daher ist es Aufgabe der vorliegenden Erfindung, ein Bi-Level-Bildcodierverfahren und -system zum Erzeugen arithmetischer Codes mit reduzierter Bitrate durch optimales Codieren jedes Pixels auch für eine Bildseite bereitzustellen, die Buchstaben und Bilder enthält.
Diese Aufgabe wird durch die Merkmale von Patentanspruch 1 gelöst.
Gemäß einem Aspekt der Erfindung werden durch einen arithmetischen Bildcodierer arithmetische Codes mit reduzierter Bitrate bereitgestellt, wobei eine zu codierende Bildseite in mehrere Bereiche geteilt wird und ein arithmetischer Codierer jedes Eingangspixel (das Pixel s_i) unter Verwendung eines vorausgesagten MPS-(wahrscheinlichstes Symbol)Wertes und einer vorausgesagten LPS-(am wenigsten wahrscheinliches Symbol)Auftrittswahrscheinlichkeit codiert, die unter Verwendung eines Templates und einer Tabel le für vorausgesagte LPS-Wahrscheinlichkeiten erzeugt werden. Dem Pixel s_i wird durch Analysieren eines der Bereiche, dem das Pixel s_i zugeordnet ist, eines von vorgegebenen Pixelattributen zugewiesen. Unter mehreren vorgegebenen Templates, wobei jedes für einen entsprechenden der Bereiche optimal angepaßt ist, wird ein Template ausgewählt, das dem zugewiesenen Pixelattribut zugeordnet ist. Unter mehreren vorgegebenen Tabellen für vorausgesagte LPS-Wahrscheinlichkeiten, wobei jede für einen entsprechenden der Bereiche optimal angepaßt ist, wird eine dem zugewiesenen Pixelattribut zugeordnete Tabelle für vorausgesagte LPS-Wahrscheinlichkeiten ausgewählt.
Die Bereiche können Zeilengruppen sein, in die eine Bildseite horizontal geteilt ist, Pixelblöcke, in die eine Bildseite geteilt ist, oder auch ein einzelnes Pixel. Im letztgenannten Fall wird ein vorgegebener Pixelblock zum Bestimmen des Pixelattributs bereitgestellt.
In einer Ausführungsform weisen die vorgegebenen Pixelattribute ein Zeichenbildattribut, ein Dither-/Rasterbildattribut und ein Halbtonbildattribut auf. Für jedes der Attribute werden ein optimales Template und eine optimale Tabelle für vorausgesagte LPS-Wahrscheinlichkeiten bereitgestellt.
Bei der Bestimmung des Attributs eines Eingangspixels, werden statistische Eigenschaften verwendet, wie beispielsweise eine periodische Eigenschaft der Dither-/Rasterbilder, ein kontinuierliches Auftreten von MPS-Symbolen, usw.
Templates und die vorausgesagte LPS-Auftrittswahrscheinlichkeit können derart angeordnet oder strukturiert sein, daß sie dem JBIG-(Joint Bi-level Image coding expert Group)Standard entsprechen.
In einer anderen Ausführungsform wird ein spezifisches Pixel des für die Erzeugung von Kontextdaten verwendeten Templates zu einer Position bewegt, die mit dem zu codierenden Eingangspixel hochgradig korreliert ist, um die Bitrate der Ausgangscodes zu reduzieren.
Die Aufgaben und Merkmale der vorliegenden Erfindung werden anhand der folgenden ausführlichen Beschreibung in Verbindung mit den beigefügten Zeichnungen verdeutlicht; es zeigen:
1 ein Diagramm zum Darstellen, wie 2M-Kontexte gemäß den Prinzipien der binären arithmetischen Codierung auf das numerische Zeilensegment abgebildet werden;
2 ein Diagramm zum Darstellen von gemäß dem JBIG-Standard definierten Zwei- und Dreizeilen-Templates;
3 ein Diagramm zum Darstellen eines auf einer binären arithmetischen Codierung basierenden Markov-Modell-Codierers;
4 ein Diagramm zum Darstellen von Datenstrukturen eines Wahrscheinlichkeitsvoraussageadressen-RAM-Speichers 70 und einer QE-Tabelle 90 und der Beziehung zwischen dem RAM-Speicher 70 und der Tabelle 90;
5 ein Blockdiagramm zum Darstellen einer exemplarischen Ausführungsform eines arithmetischen Bildcodierers gemäß einem Aspekt der vorliegenden Erfindung;
6 ein Blockdiagramm zum Darstellen einer realen Anordnung mit einer Schaltschaltung 540 und Qe-Tabellen-ROM-Speichern 590a, 590b und 590c;
7 ein Ablaufdiagramm zum Darstellen der Arbeitsweise einer in 5 dargestellten Pixelattributbestimmungseinrichtung 520;
8 ein Ablaufdiagramm zum Darstellen der Arbeitsweise eines in 5 dargestellten Kontextdatengenerators 520; und
9 ein Blockdiagramm zum Darstellen einer zweiten exemplarischen Ausführungsform eines arithmetischen Bildco dierers gemäß einem anderen Aspekt der vorliegenden Erfindung.
Einleitung
Zum besseren Verständnis der vorliegenden Erfindung, wird ein Markov-Modell-Codierer beschrieben, in dem ein arithmetischer Codierer (oder ein QM-Codierer) verwendet wird, der ein Subset des vorstehend erwähnten JBIG-Standards darstellt.
In einem Rahmen oder einer Seite eines Bi-Level-Bildes wird die Entscheidung, ob ein Pixel oder ein Symbol den Wert 0 oder 1 aufweist, normalerweise in gewissem Maß durch vorangehende Symbole beeinflußt. Wenn die Wahrscheinlichkeit dafür, daß ein (zu codierendes) Symbol s_i den Wert 0 oder 1 annimmt, durch die M vorangehenden Symbole s_i-1, s_i-2, ..., s_i-M (Referenzpixel) festgelegt wird, aber nicht durch weitere vorangehende Symbole beeinflußt ist, d.h. die bedingte Wahrscheinlichkeit für das Symbol s_i ist : P(s_i|s_i-1, s_i-2, ..., s_i-M) = P(s_i|s_i-1, s_i-2, ..., s_i-M, s_i-(M+1)) können diese Pixel s_i-1, s_i-2, ..., S_i-M als M-fache Markov-Informationsquelle betrachtet werden, die nachstehend als "Kontext" bezeichnet wird. Weil jedes Referenzpixel durch einen Binärwert dargestellt wird, kann vorausgesetzt werden, daß für jedes Pixel s_i einer (CX_i) der möglichen 2^M Kontexte {CX_i|i = 0, 1, 2, ..., 2^M – 1) vorhanden ist.
Bei einer Codierung gemäß dem Markov-Modell wird jeder der möglichen 2^M Kontexte in Abhängigkeit von der Auftrittswahrscheinlichkeit des Kontexts auf ein numerisches Zeilensegment abgebildet, das sich von 0 bis 1 erstreckt. 1 zeigt ein Diagramm zum Darstellen, wie die 2^M Kontexte gemäß den Prinzipien der binären arithmetischen Codierung auf das numerische Zeilensegment abgebildet werden. In 1 entsprechen die vertikalen Spalten dem numerischen Zeilensegment. Für einen vorgegebenen Kontext SX_i wird ein Symbol, dem das zu codierende Pixel s_i mit höherer Wahrscheinlichkeit zugeordnet ist, als wahrscheinlichstes Symbol (MPS) bezeichnet, und ein Symbol, dem das zu codierende Pixel s_i mit geringerer Wahrscheinlichkeit zugeordnet ist, wird als am wenigsten wahrscheinliches Symbol (LPS) bezeichnet. Zur vereinfachenden Beschreibung wird vorausgesetzt, daß die wahrscheinlichsten Symbole (MPS) für die an der Unterseite von 1 dargestellten Symbole alle den Wert 0 haben. Die beiden rechten Spalten sind erweiterte Ausdrücke für die Spalte (für s_i-1), die die Auftrittswahrscheinlichkeit einer Symbolsequenz S_i-1 = 010 ... s_i-1 darstellt, und die folgende Spalte (für ein Symbol s_i). Eine abgeschätzte Wahrscheinlichkeit für s_i = MPS (in diesem Beispiel 0) nach dem Auftreten einer Symbolsequenz S_i-1 liegt in einem Bereich (oder einem Augenden) A_i, der durch das Bezugszeichen 4 bezeichnet und durch einen Code C_i dargestellt wird, der den unteren Grenzwert des Augenden A_i darstellt und durch das Bezugszeichen 8 bezeichnet ist. Eine abgeschätzte Wahrscheinlichkeit für s_i = LPS (in diesem Beispiel 1) nach dem Auftreten einer Symbolsequenz S_i-1 liegt in einem Bereich 2 (A_i für LPS) und ist durch Qe(ST_i) bezeichnet. Daher ist die vorausgesagte Wahrscheinlichkeit für ein am wenigsten wahrscheinliches Symbol (LPS) im Vergleich zu derjenigen für ein wahrscheinlichstes Symbol (MPS) im oberen Teil jeder Spalte angeordnet.
Gemäß dem JBIG-Standard sind die vorstehend erwähnten Referenzpixel s_i-1, s_i-2, ..., s_i-M die einen Kontext CX_i bilden, als zwei Anordnungen von 10 Pixeln definiert, wie in 2 dargestellt ist. Diese Anordnungen werden als "Templates" bezeichnet. In jedem Template ist ein Pixel mit dem Etikett "?" ein zu codierendes Pixel, und ein Pixel mit dem Etikett "A" ist ein spezielles Pixel, das in einer geeigneten Voraussageposition angeordnet sein kann, die gemäß einer durch den T.82-Standard (internationaler JBIG-Standard) be schriebenen AT-(Adaptive Template)Funktion vorgeschrieben ist. Ein Markov-Modell-Codierer codiert jedes Eingangspixel durch Abschätzen der MPS-Auftrittswahrscheinlichkeit von einem Kontext, der von den vorangehenden Pixeln unter Verwendung eines der Templates extrahiert wird.
3 zeigt ein Diagramm zum Darstellen einer Anordnung eines exemplarischen Markov-Modell-Codierers, der auf einer binären arithmetischen Codierung basiert. Der Markov-Modell-Codierer von 3 weist auf: einen RAM-Speicher (Direktzugriffsspeicher) 30 zum Speichern von Pixeln, die vor dem aktuellen Pixel s_i eingegeben worden sind und zum Erzeugen eines Kontexts CX_i für das Pixel s_i erforderlich sind, einen Kontextdatengenerator 50, einen Wahrscheinlichkeitsvoraussageadressen-RAM-Speicher 70, einen LPS-Auftrittswahrscheinlichkeitstabellenspeicher (Qe-Tabelle) 90 und einen arithmetischen Codierer (QM-Codierer) 10.
4 zeigt ein Diagramm zum Darstellen von Datenstrukturen des Wahrscheinlichkeitsvoraussageadressen-RAM-Speicher 70 und der QE-Tabelle 90 und der Beziehung zwischen dem RAM-Speicher 70 und der Tabelle 90. Weil das Ausgangssignal des Speichers 30 dem Adressenanschluß des Kontextdatengenerators 50 zugeführt wird, wird jedem der möglichen 210 Kontexte ein MPS-Wert und einer der Zustände zugeordnet, der durch 7 Bits im RAM-Speicher 70 identifiziert ist. Der zugeordnete Zustand wird dem Adressenanschluß der Tabelle 90 zugeführt, durch den eine Liste der Tabelle 90 identifiziert wird. Jede der Listen der Tabelle 90 weist eine geschätzte LPS-Auftrittswahrscheinlichkeit Qe(ST_i) und im Fall des Auftretens eines LPS-Symbols ein MPS-Wert-Invertierungsflag auf. Die dargestellte LPS-Auftrittswahrscheinlichkeitstabelle 90 weist ferner Werte NSTA_i und NSTB_i des nächsten Zustands auf, falls ein MPS- bzw. ein LPS-Symbol auftritt. Die Werte NSTA_i und NSTB_i des nächsten Zustands sind tatsächlich in Speicherstellen gespeichert, die sich von denjenigen der Qe-Tabelle 90 unterscheiden, und auf die Werte wird in Abhängigkeit vom Wert von s_i, der auch einem der Adressenanschlüsse der Qe-Tabelle 90 zugeführt wird, separat zugegriffen.
Nachstehend wird unter Bezug auf die 3 und 4 die Arbeitsweise des Markov-Modell-Codierers beschrieben. Dem Speicher 30 und dem QM-Codierer 10 werden Eingangspixel zugeführt. In Antwort auf die Eingabe eines Pixels s_i liest der Kontextdatengenerator 50 die Kontextdaten CX_i vom Speicher 30 aus und führt sie den Adressenanschlüssen des Wahrscheinlichkeitsvoraussageadressen-RAM-Speichers 70 zu, der einen 1-Bit-Voraussagewert g_i für ein MPS-Symbol und einen 7-Bit-Zustandswert ST_i ausgibt, die in einer den Kontextdaten CX_i zugeordneten Liste enthalten sind. Der Zustandswert ST_i wird der Qe-Tabelle 90 zugeführt, die eine vorausgesagte LPS-Auftrittswahrscheinlichkeit an den QM-Codierer 10 ausgibt.
Unter der Voraussetzung, daß S_i = s₀s₁ .... s_i-1s_i = S_i-1· s_i ist, arbeitet der QM-Codierer 10 folgendermaßen:

1. Wenn s_i = LPS ist, dann A_i = Qe(ST_i) C_i = C_i-1 + (A_i-1 – Qe (ST_i)
2. Wenn s_i = MPS ist, dann A_i = A_i-1 – Qe(ST_i) C_i = C_i-1 (unverändert)

In der vorstehenden Gleichung bezeichnen A_i und C_i die Länge und den unteren Wert des Augenden für LPS-Symbole nach der Codierung der Symbolsequenz S_i, und Qe(ST_i) bezeichnet eine abgeschätzte LPS-Auftrittswahrscheinlichkeit für einen vorgegebenen Kontext CX_i.
Wenn ein Bi-Level-Bild, z.B. ein Buchstabenbild, in einem vorstehend beschriebenen JBIG-System codiert wird, be ginnt die LPS-Auftrittswahrscheinlichkeit mit einem Anfangswert von 0,5 und ändert sich graduell auf 0,1, während ein Auslesevorgang aus der LPS-Auftrittswahrscheinlichkeitstabelle (Qe-Tabelle) gemäß einem binären Eingangssymbol und einer Änderung des Zustandswertes im Wahrscheinlichkeitsvoraussageadressen-RAM-Speicher 70 wiederholt wird. Bei einer arithmetischen Codierung gilt: je besser die abgeschätzte LPS-Auftrittswahrscheinlichkeit mit der tatsächlichen Auftrittswahrscheinlichkeit übereinstimmt, desto größer ist die Codiereffizienz. Daher muß die Qe-Tabelle 90 gemäß den Eigenschaften zu codierender Bilder optimal vorbereitet werden.
Ausführungsform I
Gemäß einem Aspekt der Erfindung wird ein arithmetischer Bildcodierer bereitgestellt, der dazu geeignet ist, einen Bildrahmen oder eine Bildseite, die Zeichen, ein Dither- oder Rasterbild und/oder ein durch Fehlerdiffusion erhaltenes Halbtonbild enthält, zu codieren, indem LPS-Auftrittswahrscheinlichkeitstabellen für jeden der Bereiche fein geändert werden, in die ein Bildrahmen geteilt ist. Der Bildrahmen kann auf eine beliebige geeignete Weise geteilt werden. Beispielsweise kann ein Rahmen horizontal in Zeilengruppen oder in Blöcke mit einer Zeile aus beliebig vielen Pixeln und einer Spalte aus beliebig vielen Pixeln geteilt werden. Alternativ kann, anstatt einen Rahmen zu segmentieren, die LPS-Auftrittswahrscheinlichkeitstabelle für jedes Pixel geändert werden. Ein Modus zum Ändern von LPS-Auftrittswahrscheinlichkeitstabellen (nachstehend als "Tabellenänderungsmodus" bezeichnet) ist in Abhängigkeit von der Weise, wie ein Bildrahmen geteilt wird, als Zeilengruppenmodus, Blockmodus oder Pixelmodus definiert.
5 zeigt ein Blockdiagramm zum Darstellen einer exemplarischen Ausführungsform eines arithmetischen Bildcodierers gemäß einem Aspekt der Erfindung. Das in 5 dargestellte arithmetische Bildcodiersystem 500 weist einen arithmetischen Codierer (QM-Codierer) 10, einen Speicher 30 und einen Wahrscheinlichkeitsvoraussageadressen-RAM-Speicher 70 auf, wobei diese Komponenten mit den entsprechenden, in 3 dargestellten Komponenten identisch sind.
Der arithmetische Bildcodierer 500 weist ferner auf: eine Pixelattributbestimmungseinrichtung 520 zum Bestimmen, welches von vorgegebenen Pixelattributen einem Eingangspixel s_i zugeordnet ist, auf der Basis von unter Verwendung eines vorgegebenen Templates vom Speicher 30 extrahierten Daten und zum Ausgeben von Pixelattributdaten, und einen Kontextdatengenerator 550 zum Erzeugen von Kontextdaten CX_i durch Extrahieren von Pixeldaten, die dem Eingangspixel s_i vorangehen, unter Verwendung eines Templates, das gemäß den von der Pixelattributbestimmungseinrichtung 520 ausgegebenen Pixelattributdaten ausgewählt wird. Das System 500 weist ferner an Stelle einer einzelnen QM-Tabelle drei LPS-Auftrittswahrscheinlichkeitstabellen (QM-Tabellen) 590a, 590b und 590c für Zeichenbilder, Dither- oder Rasterbilder bzw. durch Fehlerdiffusion erzeugte Halbtonbilder und eine entsprechende Schaltschaltung 540 zum selektiven Übertragen eines neuen Zustandswertes NST1_i, NST2_i bzw. NST3_i und einer LPS-Auftrittswahrscheinlichkeit Qe1(ST_i), Qe2(ST_i) bzw. Qe3(ST_i) auf, die von den drei QM-Tabellen 590a, 590b und 590c an den Wahrscheinlichkeitsvoraussageadressen-RAM-Speicher 70 bzw. an den QM-Codierer 10 ausgegeben werden.
Eine Pixeleingangsleitung ist mit dem QM-Codierer 10 und dem Speicher 30 verbunden, dessen Ausgang mit dem Kontextdatengenerator 550 und der Pixelattributbestimmungseinrichtung 520 verbunden ist. Der Ausgang der Pixelattri butbestimmungseinrichtung 520 ist mit einem anderen Eingang des Kontextdatengenerators 550 und einem Steuereingangsanschluß der Schaltschaltung 540 verbunden. Das Ausgangssignal des Kontextdatengenerators 550 wird dem Adressenanschluß des Wahrscheinlichkeitsvoraussageadressen-RAM-Speichers 70 zugeführt. Das 7-Bit-Zustandswert-Ausgangssignal ST_i und das Eingangspixel s_i werden den Adressenanschlüssen jeder der Qe-Tabellen 590a, 590b und 590c zugeführt. Der Wahrscheinlichkeitsvoraussageadressen-RAM-Speicher 70 gibt einen MPS-Schätzwert g_i an den QM-Codierer 10 aus.
Die Schaltschaltung 540 in 5 weist einen dualen Eins-aus-Drei-Selektor mit für den Dual-Selektor gemeinsam verwendeten 2-Bit-Steuereingangsanschlüssen auf. Einer des Dual-Selektors der Schaltung 540 weist drei Kontakte auf, die mit den Zustandswertanschlüssen der Qe-Tabellen-RAM-Speicher 590a bis 590c verbunden sind, und der gemeinsame Anschluß ist mit dem NSTα_i-Eingang des Wahrscheinlichkeitsvoraussageadressen-RAM-Speichers 70 verbunden. Der andere Selektor der Schaltung 540 weist drei Kontakte auf, die mit den LPS-Auftrittswahrscheinlichkeitsausgangsanschlüssen der Qe-Tabellen-RAM-Speicher 590a bis 590c verbunden sind, und sein gemeinsamer Anschluß ist mit dem Qeα(ST_i)-Eingangsanschluß des QM-Codierers 10 verbunden. Der 2-Bit-Steuereingangsanschluß der Schaltung 540 ist mit dem Wahrscheinlichkeitsvoraussageadressen-RAM-Speicher 70 verbunden.
5 zeigt den Datenfluß des erfindungsgemäßen Bildcodierers nur schematisch, die reale Anordnung unterscheidet sich von der in 5 dargestellten Anordnung. Beispielsweise wird die Schaltschaltung 540 wie in 6 dargestellt implementiert. 6 zeigt ein Blockdiagramm einer tatsächlichen Anordnung mit der Schaltschaltung 540 und den Qe-Tabellen-ROM-Speichern 590a, 590b und 590c. Die Einrichtung 540 weist also einen 2-auf-4-Decodierer auf, wobei zwei Eingangsanschlüsse des Decodierers mit dem Ausgang der Pixelattributbestimmungseinrichtung 520 verbunden sind und drei von vier Ausgangsanschlüssen des Decodierers mit einem Chipauswahlanschluß CS jedes der Qe-Tabellen-ROM-Speicher 390a bis 390c verbunden sind, die vorzugsweise aus verschiedenen ROM-Chips gebildet werden. Anstatt dedizierte Ausgangsleitungen zu verwenden, sind die Datenanschlüsse der Qe-Tabellen-ROM-Speicher mit dem Datenbus verbunden, der außerdem mit dem QM-Decodierer 10 und dem RAM-Speicher 7C verbunden ist, wie dies in verwandten Fachgebieten herkömmlich realisiert wird.
Der 2-auf-4-Decodierer 540 und die Qe-Tabellen-ROM-Speicher 590a, 590b und 590c sind Komponenten eines LPS-Wahrscheinlichkeitsprädiktors 580.
Im Betrieb werden dem QM-Codierer 10 und dem Speicher 30, der vor dem Eingangspixel s_i zugeführte Pixeldaten speichert, Eingangspixel zugeführt. Eine Pixelattributbestimmungseinrichtung 520 bestimmt auf der Basis von vom Speicher 30 extrahierten Daten gemäß dem vorstehend erwähnten Tabellenänderungsmodus, welches Pixelattribut unter den drei Kategorien Zeichenbild, Dither-/Rasterbild und Fehlerdiffusionsbild dem Eingangspixel s_i zugeordnet ist. 7 zeigt ein Ablaufdiagramm zum Darstellen einer durch die Pixelattributbestimmungseinrichtung 520 ausgeführten Verarbeitung.
In 7 liest die Bestimmungseinrichtung 520 in Antwort auf den Empfang eines Pixels s_i Daten vom Speicher 30 aus, um das Pixelattribut des empfangenen Pixels s_i zu bestimmen. Im Zeilengruppenmodus oder im Blockmodus werden in Schritt 700 im Modus definierte Daten einer Zeilengruppe oder eines Blocks vom Speicher 30 ausgelesen. Im Pixelmodus werden durch ein vorgegebenes Template definierte Daten gelesen. Die gelesenen Daten werden in Schritt 720 geprüft, um festzustellen, ob die Daten eine periodische Eigenschaft besitzen. Wenn dies der Fall ist, gibt die Bestimmungseinrichtung 520 in Schritt 740 Dither-/Rasterbilder darstellende Pixelattributdaten aus, andernfalls schreitet die Verarbeitung zu Schritt 760 fort, um die gelesenen Daten beispielsweise durch Berechnen von Lauflängen (Run Length) einem anderen Prüfvorgang zu unterziehen, um zu bestimmen, ob in den Daten eine MPS-Kontinuität vorhanden ist. Wenn dies der Fall ist, gibt die Bestimmungseinrichtung 520 in Schritt 780 Zeichenbilder darstellende Pixelattributdaten aus, und gibt andernfalls in Schritt 790 Fehlerdiffusionsbilder darstellende Pixelattributdaten aus. Die Verarbeitung der Pixelattributbestimmungseinrichtung 520 basiert folgendermaßen auf bekannten statistischen Bildeigenschaften:
Die Auftrittswahrscheinlichkeit eines am wenigsten wahrscheinlichen Symbols (LPS-Auftrittswahrscheinlichkeit) ändert sich in Abhängigkeit vom Bildtyp. Beispielsweise weisen Bi-Level-Bilder, z.B. Zeichenbilder, eine niedrige LPS-Auftrittswahrscheinlichkeit von lediglich 0,1 auf. Andererseits weisen durch eine Halftoning-Technik von Photos erhaltene Bilder eine hohe LPS-Auftrittswahrscheinlichkeit von 0,4 auf.
8 zeigt ein Ablaufdiagramm zum Darstellen einer erfindungsgemäßen Verarbeitung des Kontextdatengenerators 550. Beim Empfang der Pixeldaten s_i wählt der Kontextdatengenerator 550 in Schritt 800 eines von drei vorgegebenen Templates aus, das dem durch die Pixelattributdaten von der Pixelattributbestimmungseinrichtung 520 spezifizierten Pixelattribut zugeordnet ist. Jedes der vorgegebenen Templates weist 10 Pixel auf, d.h. die gleiche Pixelzahl wie die im JBIG-Standard definierte Pixelzahl, und hat eine andere Pixelanordnung, die für die statistischen Bildeigenschaften des Pixelattributs optimal geeignet ist. Der Kontextdatenge nerator 550 liest in Schritt 820 unter Verwendung des ausgewählten Templates Daten vom Speicher 30 aus und speichert in Schritt 830 die gelesenen Daten als Kontextdaten CX_i in einem (nicht dargestellten) Signalspeicher, der mit dem Adressenbus verbunden ist, so daß die Kontextdaten CX_i für einen Zugriff auf eine Liste des Wahrscheinlichkeitsvoraussageadressen-RAM-Speichers 70 verwendet werden können, der dem Kontext CX_i zugeordnet ist, wie im oberen Teil von 4 dargestellt ist.
Nachstehend wird unter Bezug auf die 4 bis 6 diskutiert, wie auf die drei Qe-Tabellen 590a bis 590c zugegriffen wird. Der Wahrscheinlichkeitsvoraussageadressen-RAM-Speicher 70 gibt einen 1-Bit-Voraussagewert g_i für ein MPS-Symbol und einen 7-Bit-Zustandswert ST_i aus, die in einer durch die Kontextdaten CX_i identifizierten Liste gespeichert sind. Der Zustandswert ST_i und die Eingangspixeldaten s_i werden den Adressenanschlüssen jedes der drei Qe-Tabellen 590a bis 590c zugeführt. Gleichzeitig werden die vom Pixelattributgenerator 520 ausgegebenen Pixelattributdaten durch den Decodierer 540 decodiert, um zu veranlassen, daß eine der drei Ausgangsleitungen des Decodierers 540, die dem durch die Einrichtung 520 bestimmten Pixelattribut zugeordnet ist, den logischen Wert "1" annimmt, wodurch eine Qe-Tabelle 590a, die dem bestimmten Pixelelement zugeordnet ist, unter den in 6 dargestellten Qe-Tabellen 590a bis 590c ausgewählt wird, wobei α einen der Buchstaben "a", "b" und "c" darstellt. Auf diese Weise gibt die ausgewählte Qe-Tabelle 590a eine vorausgesagte LPS-Auftrittswahrscheinlichkeit Qeα(TS_i) für ein Pixel s_i aus. Die vorausgesagte LPS-Auftrittswahrscheinlickeit Qeα(TS_i) wird bei der arithmetischen Codierung des QM-Codierers 10 zusammen mit dem vorausgesagten MPS-Wert g_i verwendet. Die ausgewählte Qe-Tabelle 590a gibt ferner einen neuen Zustandswert NSTA_i oder NSTB_i, der zum durch diese Ausgabeoperation veranlaßten Aktualisieren des Zustandswertes in der Liste verwendet wird, an den Wahrscheinlichkeitsvoraussageadressen-RAM-Speicher 70 aus. Wenn der vorausgesagte MPS-Wert g_i mit dem aktuellen Pixelwert s_i übereinstimmt, wird der neue Zustandswert NSTA_i ausgegeben. Wenn g_i ≠ s_i ist, wird der neue Zustandswert NSTB_i ausgegeben.
Daher kann der QM-Codierer 10 anschließend jedes der Eingangspixel s_i unter Verwendung eines vorausgesaten MPS-Wertes g_i und einer vorausgesagten LPS-Auftrittswahrscheinlichkeit Qeα(TS_i) codieren, die unter Verwendung eines optimalen Template und einer optimalen Qe-Tabelle 390a für eine Zeilengruppe, der das Pixel s_i zugeordnet ist, eines Blocks, dem das Pixel zugeordnet ist, oder des Pixels erzeugt werden.
Ausführungsform II
9 zeigt ein Blockdiagramm zum Darstellen einer zweiten exemplarischen Ausführungsform eines arithmetischen Bildcodierers gemäß einem anderen Aspekt der vorliegenden Erfindung. Der in 9 dargestellte arithmetische Bildcodierer ist mit dem in 5 dargestellten Bildcodierer identisch, außer daß die Pixelattributbestimmungseinrichtung 520 durch eine AT-Erzeugungs-/Pixelattributbestimmungseinrichtung 920 ersetzt wurde und die Qe-Tabelle 590c eliminiert und entsprechend der duale 1-aus-3-Selektor 540 mit einem 2-Bit-Steuereingangsanschluß durch einen dualen 1-aus-2-Selektor 940 mit einem 1-Bit-Steuereingangsanschluß ersetzt wurde. Nachstehend werden nur Merkmale beschrieben, die sich von denjenigen der ersten exemplarischen Ausführungsform unterscheiden.
In dieser Ausführungsform wird jede Bildseite in mehrere Zeilengruppen geteilt. Eine AT-Erzeugungs-/Pixelattributbestimmungseinrichtung 920 bestimmt zunächst die Position des Template-Pixels "A" gemäß einem durch den T.82-Standard (internationaler JBIG-Standard) beschriebenen adaptiven Template. Durch Analysieren der statistischen Eigenschaften der Zeilengruppe, der das Pixel s_i zugeordnet ist, plaziert die AT-Erzeugungs-/Pixelattributbestimmungseinrichtung 920 das Template-Pixel "A" an einer Position, die mit dem Pixel s_i hochgradig korreliert ist. Beispielsweise wird, wenn die Einrichtung 920 festgestellt hat, daß die Zeilengruppe eine periodische Eigenschaft mit einer Periode von 5 Pixeln in der horizontalen Richtung aufweist, das Pixel "A" an einer Pixelposition 5 Pixel vor dem Pixel s_i angeordnet. Die AT-Erzeugungs-/Pixelattributbestimmungseinrichtung 920 bestimmt das Pixelattribut der Zeilengruppe auf die gleiche Weise wie in der ersten Ausführungsform. Dadurch wird für jede Zeilengruppe ein optimales Template bestimmt.
Wenn die Zeilengruppe, der das Pixel s_i zugeordnet ist, ein Ditherbildattribut aufweist, läßt die Einrichtung 920 die Positionsinformation für das Pixel A sowie die Pixelattributdaten zum Kontextdatengenerator 950 durch. Der Kontextdatengenerator 950 erzeugt unter Verwendung der Positionsinformation für das Pixel A Kontextdaten CX_i. Daher wird durch die Verwendung eines optimalen Template und einer geeigneten Qe-Tabelle für jede Zeilengruppe eine verbesserte Codiereffizienz erhalten.

Claims

Bi-Level-Bildcodierverfahren zum Bereitstellen eines arithmetischen Codes mit reduzierter Bitrate, wobei eine zu codierende Bildseite in mehrere Bereiche geteilt wird und ein arithmetischer Codierer jedes Eingangspixel s_i unter Verwendung eines vorausgesagten MPS-(wahrscheinlichstes Symbol)Wertes und einer vorausgesagten LPS-(am wenigsten wahrscheinliches Symbol)Auftrittswahrscheinlichkeit codiert, die unter Verwendung eines Templates und einer Tabelle für vorausgesagte LPS-Wahrscheinlichkeiten erzeugt werden, wobei das Verfahren die Schritte aufweist: Zuweisen eines von vorgegebenen Pixelattributen zum Pixel s_i durch Analysieren eines der Bereiche, dem das Pixel s_i zugeordnet ist; Auswählen eines Template, das dem zugewiesenen Pixelattribut für das Template zugeordnet ist, aus mehreren vorgegebenen Templates, wobei jedes für einen entsprechenden der Bereiche optimal angepaßt ist; und Auswählen einer dem zugewiesenen Pixelattribut zugeordneten Tabelle für vorausgesagte LPS-Wahrscheinlichkeiten unter den mehreren vorgegebenen Tabellen für vorausgesagte LPS-Wahrscheinlichkeiten, wobei jede für einen entsprechenden der Bereiche optimal angepaßt ist.
Verfahren nach Anspruch 1, ferner mit dem Schritt zum Teilen der zu codierenden Bildseite in mehrere Zeilengruppen, um die mehreren Bereiche zu erhalten.
Verfahren nach Anspruch 1, ferner mit dem Schritt zum Teilen der zu codierenden Bildseite in mehrere Blöcke, die durch eine erste beliebige Anzahl von Zeilen und eine zweite beliebige Anzahl von Spalten definiert sind, um die mehreren Bereiche zu erhalten.
Verfahren nach einem der Ansprüche 1 bis 3, ferner mit dem Schritt zum Bestimmen, daß jeder der mehreren Bereiche ein Pixel darstellt, wobei der Zuordnungsschritt den Schritt zum Zuweisen eines der vorgegebenen Pixelattribute zum Pixel s_i durch Analysieren eines vorgegebenen Pixelblocks aufweist, der das Pixel s_i enthält.
Verfahren nach einem der Ansprüche 1 bis 4, ferner mit den Schritten: Auswählen eines Zeichenbildattributs, eines Dither-/Rasterbildattributs und eines Halbtonbildattributs für die vorgegebenen Pixelattribute; Bereitstellen von Templates, wobei jedes für das Zeichenbildattribut, das Dither-/Rasterbildattribut bzw. das Halbtonbildattributs optimal angepaßt ist, als die mehreren vorgegebenen Templates; und Bereitstellen von Tabellen für vorausgesagte LPS-Wahrscheinlichkeiten, wobei jede das Zeichenbildattribut, das Dither-/Rasterbildattribut bzw. das Halbtonbildattributs optimal angepaßt ist, als die mehreren vorgegebenen Tabellen für vorausgesagte LPS-Wahrscheinlichkeiten.
Verfahren nach Anspruch 5, wobei der Zuweisungsschritt den Schritt zum Zuweisen des Dither-/Rasterbildattributs zum Pixel s_i aufweist, wenn der eine Bereich, dem das Pixel s_i zugeordnet ist, eine periodische Eigenschaft aufweist.
Verfahren nach Anspruch 5, wobei der Zuweisungsschritt den Schritt zum Zuweisen des Zeichenbildattributs zum Pixel s_i aufweist, wenn der eine Bereich, dem das Pixel s_i zugeordnet ist, eine MPS-Sequenz aufweist, die länger ist als eine vorgegebene Länge.
Verfahren nach einem der Ansprüche 1 bis 7, ferner mit den Schritten: Auswählen von Templates, die gemäß dem JBIG-(Joint Bi-level Image coding Expert Group)Standard definiert sind, für die vorgegebenen Templates; und Anpassen der vorausgesagten LPS-(am wenigsten wahrscheinliches Symbol)Auftrittswahrscheinlichkeit an den gemäß dem JBIG-Standard definierten QM-Code.
Verfahren nach Anspruch 8, ferner mit dem Schritt zum Bewegen eines spezifischen Pixels des Templates zu einer Position, die mit dem Pixel s_i hochgradig korreliert ist, gemäß der durch den T.82-(JBIG)Standard definierten AT-(adaptives Template)Funktion.
Bi-Level-Bildcodiersystem zum Bereitstellen arithmetischer Codes mit einer reduzierten Bitrate, wobei eine zu codierende Bildseite in mehrere Bereiche geteilt wird, mit: einem arithmetischen Codierer (10) zum Codieren jedes Eingangspixels s_i unter Verwendung eines vorausgesagten MPS-(wahrscheinlichstes Symbol)Wertes und einer vorausgesagten LPS-(am wenigsten wahrscheinliches Symbol)Auftrittswahrscheinlichkeit; mehreren Tabellen (590) für vorausgesagte LPS-Wahrscheinlichkeiten zum Speichern mindestens der vorausgesagten LPS-Auftrittswahrscheinlichkiet in einer Liste, die durch einen dem Pixel s_i zugeordneten Zustandswert identifiziert ist, wobei jede Tabelle für einen entsprechenden der Bereiche optimal angepaßt ist, wobei ein Bereich einem vorgegebenen Pixelattribut für jede der Tabellen für vorausgesagte LPS-Wahrscheinlichkeiten zugeordnet ist; einer Einrichtung (520) zum Zuweisen eines der vorgegebenen Pixelattribute zum Pixel s_i durch Analysieren eines der Bereiche, dem das Pixel s_i zugeordnet ist; einer Einrichtung (550) zum Auswählen eines dem zugewiesenen Pixelattribut zugeordneten Template unter mehreren vorgegebenen Templates, wobei jedes für einen entsprechenden der Bereiche optimal angepaßt ist; einer Einrichtung (70) zum Speichern mindestens des vorausgesagten MPS-Wertes und des Zustandswertes in einer Liste, die durch Kontextdaten identifiziert ist, die unter Verwendung des ausgewählten Template von dem Pixel s_i vorangehenden Pixeldaten erzeugt werden; und einer Einrichtung (540) zum Auswählen einer dem zugewiesenen Pixelattribut zugeordneten Tabelle für vorausgesagte LPS-Wahrscheinlichkeiten unter den mehreren Tabellen für vorausgesagte LPS-Wahrscheinlichkeiten.
System nach Anspruch 10, wobei die mehreren Bereiche mehrere Zeilengruppen aufweisen, in die eine Bildseite horizontal geteilt ist.
System nach Anspruch 10, wobei die mehreren Bereiche mehrere Blöcke aufweisen, die durch eine erste beliebi ge Anzahl von Zeilen und eine zweite beliebige Anzahl von Spalten definiert sind, um die mehreren Bereiche zu erhalten.
System nach einem der Ansprüche 10 bis 12, wobei jeder der mehreren Bereiche ein Pixel ist, und wobei die Zuweisungseinrichtung (520) eine Einrichtung zum Zuweisen eines der vorgegebenen Pixelattribute zum Pixel s_i durch Analysieren eines vorgegebenen Pixelblocks aufweist, der das Pixel s_i enthält.
System nach einem der Ansprüche 10 bis 13, wobei das vorgegebene Pixelattribut ein Zeichenbildattribut, ein Dither-/Rasterbildattribut und ein Halbtonbildattribut aufweist; die mehreren vorgegebenen Templates drei Templates aufweisen, wobei jedes für das Zeichenbildattribut, das Dither-/Rasterbildattribut bzw. das Halbtonbildattribut optimal angepaßt ist; und die mehreren Tabellen (590) für vorausgesagte LPS-Wahrscheinlichkeiten drei Tabellen für vorausgesagte LPS-Wahrscheinlichkeiten aufweisen, wobei jede für das Zeichenbildattribut, das Dither-/Rasterbildattribut bzw. das Halbtonbildattribut optimal angepaßt ist.
System nach Anspruch 14, wobei die Zuweisungseinrichtung (520) eine Einrichtung zum Zuweisen des Dither-/Rasterbildattributs zum Pixel s_i aufweist, wenn der eine der Bereiche, dem das Pixel s_i zugeordnet ist, eine periodische Eigenschaft aufweist.
System nach Anspruch 14, wobei die Zuweisungseinrichtung (520) eine Einrichtung zum Zuweisen eines Zei chenbildattributs zum Pixel s_i aufweist, wenn der eine der Bereiche, dem das Pixel s_i zugeordnet ist, eine MPS-Sequenz aufweist, die länger ist als eine vorgegebene Länge.
System nach einem der Ansprüche 10 bis 16, wobei die vorgegebenen Templates und die vorausgesagte LPS-Auftrittswahrscheinlichkeit gemäß dem JBIG-(Joint Bi-level Image coding expert Group)Standard definiert sind; und die arithmetischen Codes mit reduzierter Bitrate gemäß dem JBIG-Standard definierte QM-Codes sind.
System nach Anspruch 17, ferner mit einer Einrichtung zum Bewegen eines spezifischen Pixels des Templates zu einer Position, die mit dem Pixel s_i hochgradig korreliert ist, gemäß der durch den T.82-(JBIG)Standard definierten AT-(adaptives Template)Funktion.