DE19802860B4

DE19802860B4 - Verfahren und Vorrichtung zum kontext-basierten arithmetischen Codieren/Decodieren

Info

Publication number: DE19802860B4
Application number: DE19802860A
Authority: DE
Inventors: Sung-Ryul Cho
Original assignee: Daewoo Electronics Co Ltd
Current assignee: WiniaDaewoo Co Ltd
Priority date: 1998-01-20
Filing date: 1998-01-26
Publication date: 2007-08-09
Anticipated expiration: 2018-01-27
Also published as: DE19802860A1; US5933105A; GB2333412A; GB9801173D0; GB2333412B

Abstract

Verfahren zum Codieren eines binären Formsignals, das eine Vielzahl an binären Blöcken enthält, wobei jeder binäre Block M×N binäre Pixel aufweist, M und N jeweils positive ganze Zahlen sind, und jeder binäre Pixel einen von zwei unterschiedlichen binären Werten aufweist, die jeweils einen Bereich außerhalb und innerhalb eines Objektes darstellen, bei welchem:
(a) eine Kontextzahl eines Zielpixels berechnet wird, basierend auf einem entsprechenden Kontext, und eine der Kontextzahl entsprechende Wahrscheinlichkeit ermittelt wird, wobei der Zielpixel einer der binären Pixel in dem binären Block ist und der Kontext aus den binären Pixeln bestimmt wird, die vor dem Zielpixel verarbeitet wurden;
(b) ein Zustand und ein vorhergesagter Pixelwert des Zielpixels durch Vergleich der Wahrscheinlichkeit des Zielpixels mit vorgegebenen Schwellwerten bestimmt wird;
(c) ein Übereinstimmungswert des Zielpixels durch Vergleich des vorhergesagten Pixelwertes mit seinem originalen Pixelwert berechnet wird, wobei der Übereinstimmungswert darstellt, ob der vorhergesagte Pixelwert identisch zu dem originalen...

Description

Die vorliegende Erfindung betrifft ein Verfahren und eine Vorrichtung zum Codieren/Decodieren eines binären Formsignals; und insbesondere ein Kontext-basiertes ("context-based") arithmetisches Codier/Decodier-Verfahren und eine entsprechende Vorrichtung zum Verbessern einer Codiereffizienz des binären Formsignals.
Ein binäres Formsignal, das die Position und Form eines Objektes darstellt, kann als ein binärer Alphablock (BAB) aus beispielsweise 16×16 binären Pixeln innerhalb eines Frames bzw. Bilds bzw. Halbbilds bzw. Teilbildes (oder einer Videoobjektebene) ausgedrückt werden, wobei jeder binäre Pixel einen binären Wert, beispielsweise 0 oder 1, aufweist, der entweder einen Hintergrundpixel oder einen Objektpixel darstellt. Ein BAB kann unter Verwendung eines herkömmlichen Bit-Map-basierten Formcodierverfahrens, wie ein Kontext-basiertes arithmetisches Codierverfahren (CAE = context-based arithmetic encoding, d.h. Kontext-basiertes arithmetisches Codieren) codiert werden.
Beispielsweise wird für einen Intra-Frame ein aktueller BAB unter Verwendung eines herkömmlichen Intra-CAE-Verfahrens codiert, bei welchem jeder Pixel in dem aktuellen BAB arithmetisch codiert wird, basierend auf einem Intra-Kontext, der sich aus einem Satz aus dem aktuellen Frame ausgewählter Pixel zusammensetzt. Mit anderen Worten werden beim Codieren des aktuellen BAB Pixel von benachbarten BABs verwendet, um den Intra-Kontext aufzustellen. Eine Grenze bzw. Umrandung mit der Breite 2 um den aktuellen BAB wird wie in 3 dargestellt verwendet, um einen aktuellen umrandeten BAB bereitzustellen. In 3 sind die Pixel in dem hellen Bereich des aktuellen umrandeten BABs der zu codierende Teil des aktuellen BAB und die Pixel in dem dunklen Bereich des aktuellen umrandeten BAB sind die Randpixel. Diese werden aus zuvor codierten und rekonstruierten BABs erhalten, außer denjenigen, die mit '0' markiert sind, die zur Zeit des Decodierens nicht bekannt sind.
Basierend auf dem aktuellen umrandeten BAB wird der Intra-Kontext wie in 1 gezeigt ausgewählt. Daher wird in 1 ein schattierter Pixel, d.h. ein Pixel in dem aktuellen BAB, unter Verwendung seines Intra-Kontexts 10, beispielsweise C0 bis C9, codiert.
Für einen Inter-Frame kann der aktuelle BAB unter Verwendung entweder der Intra-CAE- oder einer Inter-CAE-Technik codiert werden, abhängig davon, welche der beiden CAE-Techniken eine geringere Anzahl codierter Daten erzeugt. Gemäß der Inter-CAE-Technik wird ein Fehler, der eine Differenz zwischen dem aktuellen BAB und allen vorgegebenen, in einem vorhergehenden Frame enthaltenen, in Frage kommenden BABs darstellt, zuerst berechnet und ein ähnlichster in Frage kommender BAB und ein Bewegungsvektor mittels einer Bewegungsabschätzungstechnik ermittelt, wobei der ähnlichste in Frage kommende BAB einen in Frage kommenden BAB darstellt, der einen kleinsten Fehler unter den in Frage kommenden BABs erzeugt, und der Bewegungsvektor eine Verschiebung zwischen dem aktuellen BAB und dem ähnlichsten in Frage kommenden BAB angibt. Anschließend wird jeder Pixel in dem aktuellen BAB arithmetisch codiert, basierend auf einem Inter-Kontext, und eine Bewegungsvektordifferenz (BVD), die eine Differenz zwischen dem Bewegungsvektor und dessen Bewegungsvektorvorhersage (BVDV) darstellt, wird codiert, indem beispielsweise ein variables Lauflängencodierschema (VLC = "variable length coding", d.h. variable Lauflängencodierung) angewendet wird. Mit Bezug auf 2A und 2B setzt sich der Inter-Kontext aus zwei Untersätzen an Pixeln zusammen, einem ersten Untersatz an Pixeln 20A, beispielsweise C0 bis C3, die in 2A aus den Pixeln in dem aktuellen Frame auf ähnliche Weise ausgewählt werden, wie sie in dem Intra-CAE angewendet wird, und einem zweiten Untersatz an Pixeln 20B, beispielsweise C4 bis C8, die in 2B aus dem vorhergehenden Frame ausgewählt wurden, basierend auf dem Bewegungsvektor. Es wird nämlich eine Umrandung der Breite 1 um einen bewegungskompensierten BAB, der aus dem vorhergehenden Frame unter Verwendung des Bewegungsvektors ermittelt wird, verwendet, um einen umrandeten bewegungskompensierten BAB bereitzustellen, wie in
4 beschrieben. In 4 entspricht der helle Bereich dem bewegungskompensierten BAB und der dunkle Bereich der Umrandung. Sobald der umrandete bewegungskompensierte BAB bestimmt ist, wird der zweite Untersatz an Pixeln 20B, der die binären Pixel C4 bis C8 enthält, aus dem umrandeten bewegungskompensierten BAB ausgewählt, wobei die Pixelposition des Pixels C6 identisch zu derjenigen des schattierten Pixels ist.
Dementsprechend wird entweder der Intra-Kontext oder der Inter-Kontext wie oben dargestellt ausgewählt und eine Kontextzahl des schattierten Pixels in dem aktuellen BAB berechnet, basierend auf seinem entsprechenden Kontext. Sobald die Kontextzahl des schattierten Pixels verschlüsselt ist, wird eine der Kontextzahl entsprechende Wahrscheinlichkeit aus einer Wahrscheinlichkeitstabelle ermittelt, die den verschiedenen Kontextzahlen zugeordnete vorgegebene Wahrscheinlichkeiten enthält, und die ermittelte Wahrscheinlichkeit arithmetisch codiert, um dadurch ein codiertes binäres Formsignal zu erzeugen. Weitere Details der CAE-Technik und des BVD können in dem MPEG-4 Video Verification Model Version 7.0, International Organisation for Standardization, Coding of Moving Pictures and Associated Audio Information, ISO/IEC, JTC1/SC29/WG11 MPEG97/N1642, Bristol, April 1997 gefunden werden.

Die Druckschrift EP 0 755 155 A2 beschreibt ein Kodiersystem für eine verlustlose Bildkompression. Das System umfasst einen Bildkomprimierer, welcher den Kontext eines zu kodierenden Pixels verwendet, um den Wert des Pixels vorherzusagen, und einen Vorhersage-Fehler ermittelt. Weiterhin quantisiert der Komprimierer den Pixelkontext, zählt die Fehlerwerte für jeden quantisierten Kontext und verwendet diese Zählungen zum Erzeugen kontext-spezifischer Kodiertabellen für jeden quantisierten Kontext. Für das Kodieren eines bestimmten Pixels schlägt der Kodierer den Vorhersage-Fehler in der kontext-spezifischen Kodiertabelle für den Kontext des Pixels nach und kodiert diesen Wert.

Obwohl die Anzahl an zu übertragenden Bits durch Verwendung der herkömmlichen oben diskutierten CAE-Technik reduziert wird, wird weiterhin eine große Anzahl an Bits beim Übertragen des binären Formsignals benötigt. Dementsprechend ist eine weitere Reduktion der Anzahl an bei dem Codieren des binären Formsignals verwendeter Bits erwünscht.

Es ist Aufgabe der vorliegenden Erfindung, ein Verfahren und eine Vorrichtung zum adaptiven Codieren eines binären Formsignals unter Verwendung einer adaptiven arithmetischen Codiertechnik so zu schaffen, daß die Anzahl an Übertragungsdaten reduziert wird.

Die Erfindung löst diese Aufgabe jeweils mit den Gegenständen der Ansprüche 1, 7 und 13. Bevorzugte Ausführungsbeispiele sind in den Unteransprüchen beschrieben.

Nach Anspruch 1 ist ein Verfahren geschaffen zum Codieren eines binären Formsignals, das eine Vielzahl an binären Blöcken enthält, wobei jeder binäre Block M×N binäre Pixel aufweist, M und N jeweils positive ganze Zahlen sind, und jeder binäre Pixel einen von zwei unterschiedlichen binären Werten aufweist, die jeweils einen Bereich außerhalb und innerhalb eines Objektes darstellen, bei welchem: (a) eine Kontextzahl eines Zielpixels berechnet wird, basierend auf einem entsprechenden Kontext, und eine der Kontextzahl entsprechende Wahrscheinlichkeit ermittelt wird, wobei der Zielpixel einer der binären Pixel in dem binären Block ist und der Kontext aus den binären Pixeln bestimmt wird, die zeitlich vor dem Zielpixel verarbeitet werden; (b) ein Zustand und ein vorhergesagter Pixelwert des Zielpixels durch Vergleich der Wahrscheinlichkeit des Zielpixels mit Schwellwerten bestimmt wird; (c) ein Übereinstimmungswert des Zielpixels durch Vergleich des vorhergesagten Pixelwertes mit seinem originalen Pixelwert berechnet wird, wobei der Übereinstimmungswert angibt, ob der vorhergesagte Pixelwert identisch zu dem originalen Pixelwert ist oder nicht; (d) die Schritte (a) bis (c) wiederholt werden, bis alle binären Pixel in dem binären Block verarbeitet sind; (e) ein umgeordneter, in eine erste und eine zweite Folge aufgeteilter binärer Block erzeugt wird, wobei die erste und die zweite Folge durch Klassifizieren der binären Pixel des binären Blocks gemäß deren Zustände aufgestellt werden; und (f) die erste und die zweite Folge arithmetisch codiert werden, um dadurch das codierte binäre Formsignal zu erzeugen.

Nach Anspruch 7 ist eine Vorrichtung geschaffen zum Codieren eines binären Formsignals, das eine Vielzahl an binären Blöcken aufweist, wobei jeder binäre Block M×N binäre Pixel aufweist, M und N jeweils positive ganze Zahlen sind, und jeder binäre Pixel einen von zwei unterschiedlichen binären werten aufweist, die einen Bereich jeweils außerhalb und innerhalb eines Objektes darstellen, mit: einer Kontextzahl-Berechnungseinheit zum Verschlüsseln einer Kontextzahl für jeden der binären Pixel in dem binären Block, basierend auf einem entsprechenden Kontext und zum Ermitteln einer der Kontextzahl entsprechenden Wahrscheinlichkeit, wobei der Kontext aus den binären Pixeln bestimmt wird, die zeitlich vor allen binären Pixel verarbeitet wurden; einer Zustand-Bestimmungseinheit zum Bestimmen eines Zustands und eines vorhergesagten Pixelwertes von allen binären Pixeln durch Vergleich der Wahrscheinlichkeit mit Schwellwerten; einer Vergleichseinheit zum Berechnen eines Übereinstimmungswertes für alle binären Pixel durch Vergleich des vorhergesagten Pixelwertes mit seinem originalen Pixelwert, wobei der Übereinstimmungswert darstellt, ob der vorhergesagte Pixelwert identisch zu dem originalen Pixelwert ist oder nicht; einer Umordnungseinheit zum Erzeugen eines umgeordneten, in eine erste und eine zweite Folge aufgeteilten binären Blockes, wobei die erste und die zweite Folge durch Klassifizieren der binären Pixel des binären Blocks gemäß deren Zustände aufgestellt werden; und einer adaptiven arithmetischen Codiereinheit zum arithmetischen Codieren der ersten und der zweiten Folge, um dadurch das codierte binäre Formsignal zu erzeugen.

Nach Anspruch 13 ist eine Vorrichtung geschaffen zum Decodieren eines codierten binären Formsignals, um dadurch ein decodiertes binäres Formsignal bereitzustellen, mit: einer adaptiven arithmetischen Decodiereinheit zum arithmetischen Decodieren des codierten binären Formsignals, basierend auf Wahrscheinlichkeitssätzen, um dadurch decodierte binäre Formdaten bereitzustellen, die eine erste und eine zweite Folge enthalten, wobei die erste und die zweite Folge rekonstruierte Übereinstimmungswerte der binären Pixel aufweisen; einer Kontextzahl-Berechnungseinheit zum Berechnen einer Kontextzahl für alle binären Pixel, basierend auf einem entsprechenden Kontext, und zum Ermitteln einer der Kontextzahl entsprechenden Wahrscheinlichkeit, wobei der Kontext aus binären Pixeln bestimmt wird, die zeitlich vor allen binären Pixeln rekonstruiert wurden; einer Zustand-Bestimmungseinheit zum Ermitteln eines Zustandes und eines vorhergesagten Pixelwertes von allen binären Pixeln durch Vergleich der Wahrscheinlichkeit mit vorgegebenen Schwellwer ten; einer Auswahleinheit zum Auswählen der rekonstruierten Übereinstimmungswerte für alle binären Pixel aus der ersten oder der zweiten Folge als Antwort auf den Zustand jedes der binären Pixel; und einer Ausgabeeinheit zum Rekonstruieren eines binären Pixels jedes der binären Pixel durch Vergleich des ausgewählten rekonstruierten Übereinstimmungswertes mit dem vorhergesagten Pixelwert und zum sequentiellen Bereitstellen der rekonstruierten binären Pixelwerte entsprechend der decodierten binären Formdaten als das decodierte binäre Formsignal.

Weitere Vorteile und Ausgestaltungen der vorliegenden Erfindung werden nunmehr anhand bevorzugter Ausführungsbeispiele mit Bezug auf die beigefügte Zeichnung näher erläutert. In der Zeichnung zeigen:
1 eine Intra-Schablone (-Template) und eine Kontext-Konstruktion;
2A und 2B eine Inter-Schablone (-Template) und eine Kontext-Konstruktion;
3 einen aktuellen umrandeten BAB;
4 einen umrandeten bewegungskompensierten BAB;
5 ein Blockdiagramm einer Kontext-basierten arithmetischen Codiervorrichtung gemäß der vorliegenden Erfindung; und
6 ein Blockdiagramm einer Kontext-basierten arithmetischen Decodiervorrichtung gemäß der vorliegenden Erfindung.
In 5 ist ein Blockdiagramm einer Kontext-basierten arithmetischen Codiervorrichtung gemäß einem bevorzugten Ausführungsbeispiel der vorliegenden Erfindung dargestellt.
Ein binäres Formsignal enthält eine Vielzahl an binären Blöcken, wobei jeder binäre Block M×N, beispielsweise 16×16, binäre Pixel aufweist und jeder binäre Pixel einen binären Wert hat, beispielsweise 1 oder 0, der entweder einen Objektpixel oder einen Hintergrundpixel darstellt, wobei M und N jeweils positive ganze Zahlen sind. Jeder Block des binären Formsignals wird einer Speichereinheit 110 eingegeben und dort als ein aktueller binärer Block gespeichert. Anschließend wird jeder binäre Pixel in dem aktuellen binären Block einer Vergleichseinheit 140 als ein aktueller Pixel bereitgestellt.
Zwischenzeitlich verschlüsselt bzw. berechnet eine Kontextzahl-Berechnungseinheit 120 eine Kontextzahl entsprechend jedem der binären Pixel in dem aktuellen binären Block auf dieselbe Weise, wie sie in der herkömmlichen CAE-Technik angewendet wird, unter Verwendung ihres entsprechenden Kontexts, d.h. entweder einem Intra-Kontext oder einem Inter-Kontext. Die Kontextzahl-Berechnungseinheit 120 ermittelt ebenfalls eine der Kontextzahl entsprechende Wahrscheinlichkeit, basierend auf der Wahrscheinlichkeitstabelle, wie es in dem Stand der Technik geschieht. Die Kontextzahl und ihre Wahrscheinlichkeit werden einer Zustand-Bestimmungseinheit 130 jeweils als eine dem aktuellen Pixel entsprechende Kontextzahl und aktuelle Wahrscheinlichkeit bereitgestellt.
Die Zustand-Bestimmungseinheit 130 vergleicht die aktuelle Wahrscheinlichkeit von der Kontextzahl-Berechnungseinheit 120 mit einem vorgegebenen Schwellwert, um zu bestimmen, ob der aktuelle Pixel mit der aktuellen Kontextzahl zu einem guten Zustand oder einem schlechten Zustand gehört. Falls in dem Vergleich die aktuelle Wahrscheinlichkeit als größer oder als gleich dem vorgegebenen Schwellwert bestimmt wird, wird der aktuelle Pixel als der gute Zustand, und andernfalls als der schlechte Zustand bestimmt. Die Zustand-Bestimmungseinheit 130 gibt ein Zustandsanzeigesignal aus, das den Zustand des aktuellen Pixels der Vergleichseinheit 140 bereitstellt. Die Zustand-Bestimmungseinheit 130 stellt ebenfalls einen dem aktuellen Pixel entsprechenden vorhergesagten Pixelwert der Vergleichseinheit 140 bereit. Der vorhergesagte Pixelwert wird durch Vergleich der aktuellen Wahrscheinlichkeit mit einem Vorhersage-Schwellwert, beispielsweise dem halben Wert der maximalen Wahrscheinlichkeit, bestimmt. Entsprechend der Wahrscheinlichkeitstabelle, die durch Berücksichtigung beispielsweise eines binären Wertes 0, falls die aktuelle Wahrscheinlichkeit größer als oder gleich dem Vorhersage-Schwellwert ist, bestimmt worden ist, wird ein binärer Wert 0 bestimmt, und andernfalls ein binärer Wert 1 als der vorhergesagte Pixelwert.
Entsprechend einem anderen Ausführungsbeispiel der vorliegenden Erfindung kann der vorgegebene Schwellwert zwei Level haben, beispielsweise einen hohen Level und einen niedrigen Level, um einen Zustand eines binären Pixels zu bestimmen. Mit anderen Worten wird der aktuelle Pixel als der gute Zustand bestimmt, falls die aktuelle Wahrscheinlichkeit größer als oder gleich dem hohen Level oder kleiner als der niedrige Level ist, und andernfalls, d.h., falls die aktuelle Wahrscheinlichkeit kleiner als der hohe Level und größer als oder gleich dem niedrigen Level ist, wird der aktuelle Pixel als der schlechte Zustand bestimmt.
Anschließend vergleicht die Vergleichseinheit 140 den von der Zustand-Bestimmungseinheit 130 übertragenen vorhergesagten Pixelwert mit dem von der Speichereinheit 110 bereitgestellten aktuellen Pixelwert. Falls der vorhergesagte Pixelwert und der aktuelle Pixelwert in dem Vergleich als identisch miteinander bestimmt werden, ordnet die Vergleichseinheit 140 dem aktuellen Pixel einen Übereinstimmungswert "0", und andernfalls einen Übereinstimmungswert "1" zu. Die aktuelle Pixelinformation, die den Übereinstimmungswert und das Zustandsanzeigesignal enthält, wird einer Umordnungseinheit 150 bereitgestellt.
Die obigen Prozesse werden wiederholt für alle binären Pixel in dem aktuellen binären Block durchgeführt, und anschließend wird die aktuelle Pixelinformation für alle binären Pixel sequentiell der Umordnungseinheit 150 bereitgestellt.
Die Umordnungseinheit 150 speichert die aktuelle Pixelinformation für alle binären Pixel in dem aktuellen binären Block und erzeugt eine erste und eine zweite Folge durch Umordnen der Übereinstimmungswerte in der aktuellen Pixelinformation als Antwort auf deren entsprechende Zustandsanzeigesignale. Die erste Folge enthält die Übereinstimmungswerte, die den als der gute Zustand bestimmten binären Pixeln entsprechen, und die zweite Folge die Übereinstimmungswerte, die den als der schlechte Zustand bestimmten binären Pixeln entsprechen. Die Umordnungseinheit 150 zählt ebenfalls die Zahl der Übereinstimmungswerte 0 in der ersten und der zweiten Folge und stellt den Zählwert der Wahrscheinlichkeitssatz-Bestimmungseinheit 160 bereit.
Die Wahrscheinlichkeitssatz-Bestimmungseinheit 160 ermittelt optimale Wahrscheinlichkeitssätze, die jeweils der ersten und der zweiten Folge entsprechen, unter Verwendung der von der Umordnungseinheit 150 bereitgestellten Zählwerte und erzeugt ein Auswahlsignal, das angibt, welche Wahrscheinlichkeitssätze ermittelt wurden. Das Auswahlsignal wird codiert und anschließend einem Multiplexer 180 über eine Leitung L10 bereitgestellt und die optimalen Wahrscheinlichkeitssätze werden einer adaptiven arithmetischen Codiereinheit 170 über eine Leitung L20 eingespeist.
Gemäß der vorliegenden Erfindung wird eine dem Übereinstimmungswert mit einer Zahl 0 zugeordnete Wahrscheinlichkeit größer, wenn der Zählwert ansteigt, während eine dem Übereinstimmungswert mit einer Zahl 1 zugeordnete Wahrscheinlichkeit kleiner wird.
Die adaptive arithmetische Codiereinheit 170 codiert die erste und die zweite Folge unter Verwendung bekannter arithmetischer Codiertechniken, basierend auf den von der Wahrscheinlichkeitssatz-Bestimmungseinheit 160 über die Leitung L20 bereitgestellten optimalen Wahrscheinlichkeitssätzen, um dadurch dem Multiplexer 180 codierte binäre Daten bereitzustellen.
Bei dem Multiplexer 180 werden die codierten binären Daten von der adaptiven arithmetischen Codiereinheit 170 und das codierte Auswahlsignal von der Wahrscheinlichkeitssatz-Bestimmungseinheit 160 gemultiplext, um dadurch ein über einen Sender (nicht gezeigt) zu übertragendes codiertes binäres Formsignal zu erzeugen.
In 6 ist ein Blockdiagramm einer Kontext-basierten arithmetischen Decodiervorrichtung gemäß dem bevorzugten Ausführungsbeispiel der vorliegenden Erfindung dargestellt.
Das über einen Übertragungskanal übertragene codierte binäre Formsignal wird einem Demultiplexer 200 eingegeben.
Der Demultiplexer 200 teilt das codierte binäre Formsignal in ein codiertes Auswahlsignal und codierte binäre Daten auf. Das codierte Auswahlsignal wird einer Wahrscheinlichkeitssatz-Bestimmungseinheit 210 über eine Leitung L40 eingegeben, und die codierten binären Daten werden einer adaptiven arithmetischen Decodiereinheit 220 über eine Leitung L30 bereitgestellt.
Die Wahrscheinlichkeitssatz-Bestimmungseinheit 210 decodiert das codierte Auswahlsignal, um ein decodiertes Auswahlsignal zu erzeugen, und ermittelt Wahrscheinlichkeitsätze als Antwort auf das decodierte Auswahlsignal.
Die adaptive arithmetische Decodiereinheit 220 decodiert die codierten binären Daten unter Verwendung bekannter Kontextbasierter arithmetischer Decodiertechniken, die den bei der adaptiven arithmetischen Codiereinheit 170 in 5 angewendeten Kontext-basierten arithmetischen Codiertechniken entsprechen, basierend auf den ermittelten Wahrscheinlichkeitssätzen, und stellt die decodierten binären Daten, welche die erste und die zweite Folge enthalten, einer Speichereinheit 230 bereit, wobei die erste Folge decodierte Übereinstimmungswerte der als guter Zustand bestimmten binären Pixel aufweist und die zweite Folge diejenigen Pixel aufweist, die als der schlechte Zustand bestimmt worden sind. Die aus der ersten und der zweiten Folge bestehenden decodierten binären Daten werden in der Speichereinheit 230 gespeichert.
Zwischenzeitlich berechnet eine Kontextzahl-Berechnungseinheit 240 eine Kontextzahl eines binären Arbeitspixels, der jedem der in dem aktuellen binären Block enthaltenen binären Pixel ent spricht, unter Verwendung von dessen Kontext, der aus den zeitlich vor dem binären Arbeitspixel rekonstruierten binären Pixeln ausgewählt ist. Die bei der Kontextzahl-Berechnungseinheit 240 berechnete Kontextzahl wird einer Zustand-Bestimmungseinheit 250 übertragen.
Die Zustand-Bestimmungseinheit 250 ermittelt zuerst eine Wahrscheinlichkeit, die der von der Kontextzahl-Berechnungseinheit 240 abgeleiteten Kontextzahl entspricht, und bestimmt einen Zustand des binären Arbeitspixels durch Vergleich der Wahrscheinlichkeit mit dem vorgegebenen Schwellwert, wie in der Kontext-basierten arithmetischen Codiervorrichtung aus 5 beschrieben ist. Dementsprechend wird der binäre Arbeitspixel als der gute Zustand bestimmt, falls die Wahrscheinlichkeit größer als oder gleich dem vorgegebenen Schwellwert ist; und andernfalls wird der binäre Arbeitspixel als der schlechte Zustand bestimmt. Die Zustand-Bestimmungseinheit 250 erzeugt ein Zustandsanzeigesignal, das den guten oder den schlechten Zustand darstellt, wie er für den binären Arbeitspixel bestimmt ist. Ferner wird, basierend auf der Wahrscheinlichkeit, ein vorhergesagter Pixelwert des binären Arbeitspixels ermittelt, wie in der Kontext-basierten arithmetischen Codiervorrichtung aus 5 dargestellt ist. Der vorhergesagte Pixelwert und das Zustandsanzeigesignal werden einer Umordnungseinheit 260 bereitgestellt.
Die Umordnungseinheit 260 wählt einen Übereinstimmungswert aus der ersten oder der zweiten in der Speichereinheit 230 gespeicherten Folge als Antwort auf das von der Zustand-Bestimmungseinheit 250 ausgegebene Zustandsanzeigesignal aus. Mit anderen Worten nimmt die Umordnungseinheit 260 den Übereinstimmungswert aus der in der Speichereinheit 230 gespeicherten ersten Folge heraus, falls das Zustandsanzeigesignal den guten Zustand darstellt, während der Übereinstimmungswert unter den Übereinstimmungswerten ausgewählt wird, die in der in der Speichereinheit 230 gespeicherten zweiten Folge enthalten sind, falls das Zustandsanzeigesignal den schlechten Zustand anzeigt. Anschließend rekonstruiert die Umordnungseinheit 260 einen bi nären Pixelwert des binären Arbeitspixels durch Vergleich des Übereinstimmungswertes mit dem vorhergesagten Pixelwert aus der Zustand-Bestimmungseinheit 250. Falls der Übereinstimmungswert eine Zahl 0 aufweist, wird der vorhergesagte Pixelwert als der rekonstruierte Pixelwert genommen. Andernfalls, d.h. falls der Übereinstimmungswert eine Zahl 1 aufweist, wird ein invertierter binärer Wert des vorhergesagten Pixelwertes als der rekonstruierte Pixelwert bestimmt. Jeder rekonstruierte Pixelwert wird als ein decodiertes binäres Formsignal ausgegeben.
Die obigen Decodierprozesse werden wiederholt durchgeführt, bis alle Pixelwerte des aktuellen binären Blocks rekonstruiert sind.

Claims

Verfahren zum Codieren eines binären Formsignals, das eine Vielzahl an binären Blöcken enthält, wobei jeder binäre Block M×N binäre Pixel aufweist, M und N jeweils positive ganze Zahlen sind, und jeder binäre Pixel einen von zwei unterschiedlichen binären Werten aufweist, die jeweils einen Bereich außerhalb und innerhalb eines Objektes darstellen, bei welchem: (a) eine Kontextzahl eines Zielpixels berechnet wird, basierend auf einem entsprechenden Kontext, und eine der Kontextzahl entsprechende Wahrscheinlichkeit ermittelt wird, wobei der Zielpixel einer der binären Pixel in dem binären Block ist und der Kontext aus den binären Pixeln bestimmt wird, die vor dem Zielpixel verarbeitet wurden; (b) ein Zustand und ein vorhergesagter Pixelwert des Zielpixels durch Vergleich der Wahrscheinlichkeit des Zielpixels mit vorgegebenen Schwellwerten bestimmt wird; (c) ein Übereinstimmungswert des Zielpixels durch Vergleich des vorhergesagten Pixelwertes mit seinem originalen Pixelwert berechnet wird, wobei der Übereinstimmungswert darstellt, ob der vorhergesagte Pixelwert identisch zu dem originalen Pixelwert ist oder nicht; (d) die Schritte (a) bis (c) wiederholt werden, bis alle binären Pixel in dem binären Block verarbeitet sind; (e) ein umgeordneter, in eine erste und eine zweite Folge von Übereinstimmungswerten aufgeteilter binärer Block erzeugt wird, wobei die erste und die zweite Folge von Übereinstimmungswerten durch Klassifizieren der binären Pixel des binären Blocks gemäß deren Zustände aufgestellt werden; und (f) die erste und die zweite Folge von Übereinstimmungswerten arithmetisch codiert werden, um dadurch das codierte binäre Formsignal zu erzeugen.
Verfahren nach Anspruch 1, bei welchem im Schritt (b): (b11) dem Zielpixel ein guter Zustand oder ein schlechter Zustand durch Vergleich der Wahrscheinlichkeit mit einem ersten vorgegebenen Schwellwert zugeordnet wird, wobei der Zielpixel als der gute Zustand bestimmt wird, falls die Wahrscheinlichkeit größer als oder gleich dem ersten vorgegebenen Schwellwert ist, und andernfalls der Zielpixel als der schlechte Zustand bestimmt wird; und (b12) der vorhergesagte Pixelwert des Zielpixels durch Vergleich der Wahrscheinlichkeit mit einem zweiten vorgegebenen Schwellwert bereitgestellt wird.
Verfahren nach Anspruch 1, bei welchem im Schritt (b): (b21) dem Zielpixel ein guter Zustand oder ein schlechter Zustand durch Vergleich der Wahrscheinlichkeit mit einem ersten und einem zweiten vorgegebenen Schwellwert zugeordnet wird, wobei der Zielpixel als der gute Zustand bestimmt wird, falls die Wahrscheinlichkeit größer als oder gleich dem ersten vorgegebenen Schwellwert, oder kleiner als der zweite vorgegebene Schwellwert ist, und andernfalls der Zielpixel als der schlechte Zustand bestimmt wird; und (b22) der vorhergesagte Pixelwert des Zielpixels durch Vergleich der Wahrscheinlichkeit mit einem dritten vorgegebenen Schwellwert bereitgestellt wird.
Verfahren nach einem der vorhergehenden Ansprüche, bei welchem im Schritt (c) der Übereinstimmungswert einen binären Wert 0 aufweist, falls der vorhergesagte Pixelwert identisch zu dem originalen Pixelwert ist, und andernfalls der Übereinstimmungswert einen binären Wert 1 aufweist.
Verfahren nach einem der vorhergehenden Ansprüche, bei welchem im Schritt (f): (f1) die Anzahl an Übereinstimmungswerten mit dem binären Wert 0 in der ersten und der zweiten Folge von Übereinstimmungswerten gezählt wird, um dadurch die Zählwerte bereitzustellen; (f2) jeweils der ersten und der zweiten Folge von Übereinstimmungswerten entsprechende Wahrscheinlichkeitssätze unter Verwendung der Zählwerte ermittelt werden; und (f3) die erste und die zweite Folge von Übereinstimmungswerten unter Verwendung der Wahrscheinlichkeitssätze arithmetisch codiert werden, um dadurch das codierte binäre Formsignal auszugeben.
Verfahren nach Anspruch 5, bei welchem dem Übereinstimmungswert mit dem binären Wert 0 eine größere Wahrscheinlichkeit zugeordnet wird und dem Übereinstimmungswert mit dem binären Wert 1 eine kleinere Wahrscheinlichkeit zugeordnet wird, wenn der Zählwert ansteigt.
Vorrichtung zum Codieren eines binären Formsignals, das eine Vielzahl an binären Blöcken aufweist, wobei jeder binäre Block M×N binäre Pixel aufweist, M und N jeweils positive ganze Zahlen sind, und jeder binäre Pixel einen von zwei unterschiedlichen binären Werten aufweist, die einen Bereich jeweils außerhalb und innerhalb eines Objektes darstellen, mit: einem Mittel (120) zum Berechnen einer Kontextzahl für alle binären Pixel in dem binären Block, basierend auf einem entsprechenden Kontext, und zum Ermitteln einer der Kontextzahl entsprechenden Wahrscheinlichkeit, wobei der Kontext aus den binären Pixeln bestimmt wird, die vor jedem der binären Pixel verarbeitet wurden; einem Mittel (130) zum Bestimmen eines Zustands und eines vorhergesagten Pixelwertes aller binären Pixel durch Vergleich der Wahrscheinlichkeit mit vorgegebenen Schwellwerten; einem Mittel (140) zum Berechnen eines Übereinstimmungswertes für alle binären Pixel durch Vergleich des vorhergesagten Pixelwertes mit seinem originalen Pixelwert, wobei der Übereinstimmungswert angibt, ob der vorhergesagte Pixelwert identisch zu dem originalen Pixelwert ist oder nicht; einem Mittel (150) zum Erzeugen eines umgeordneten, in eine erste und eine zweite Folge von Übereinstimmungswerten aufgeteilten binären Blockes, wobei die erste und die zweite Folge von Übereinstimmungswerten durch Klassifizieren der binären Pixel des binären Blocks gemäß deren Zustände aufgestellt werden; und einem Mittel (170) zum arithmetischen Codieren der ersten und der zweiten Folge von Übereinstimmungswerten, um dadurch das codierte binäre Formsignal zu erzeugen.
Vorrichtung nach Anspruch 7, bei welcher das Bestimmungsmittel (130) aufweist: ein Mittel zum Zuordnen eines guten Zustandes oder eines schlechten Zustandes zu jedem binären Pixel durch Vergleich der Wahrscheinlichkeit mit einem ersten vorgegebenen Schwellwert, wobei der binäre Pixel als der gute Zustand bestimmt wird, falls die Wahrscheinlichkeit größer als oder gleich dem ersten vorgegebenen Schwellwert ist, und andernfalls der binäre Pixel als der schlechte Zustand bestimmt wird; und ein Mittel zum Bereitstellen des vorhergesagten Pixelwertes für jeden binären Pixel durch Vergleich der Wahrscheinlichkeit mit einem zweiten vorgegebenen Schwellwert.
Vorrichtung nach Anspruch 7, bei welchem das Bestimmungsmittel (130) aufweist: ein Mittel zum Zuordnen eines guten Zustandes oder eines schlechten Zustandes zu jedem binären Pixel durch Vergleich der Wahrscheinlichkeit mit einem ersten und einem zweiten vorgegebenen Schwellwert, wobei der binäre Pixel als der gute Zustand bestimmt wird, falls die Wahrscheinlichkeit größer als oder gleich dem ersten vorgegebenen Schwellwert, oder kleiner als der zweite vorgegebene Schwellwert ist, und andernfalls der binäre Pixel als der schlechte Zustand bestimmt wird; und ein Mittel zum Bereitstellen des vorhergesagten Pixelwertes für jeden binären Pixel durch Vergleich der Wahrscheinlichkeit mit einem dritten vorgegebenen Schwellwert.
Vorrichtung nach einem der Ansprüche 7 bis 9, bei welcher der Übereinstimmungswert einen binären Wert 0 aufweist, falls der vorhergesagte Pixelwert identisch zu dem originalen Pixelwert ist, und andernfalls der Übereinstimmungswert einen binären Wert 1 aufweist.
Vorrichtung nach einem der Ansprüche 7 bis 10, bei welcher das Codiermittel (170, 160) aufweist: ein Mittel zum Zählen der Anzahl an Übereinstimmungswerten mit dem binären Wert 0 in der ersten und der zweiten Folge von Übereinstimmungswerten, um dadurch die Zählwerte bereitzustellen; ein Mittel zum Ermitteln der jeweils der ersten und der zweiten Folge von Übereinstimmungswerten entsprechenden Wahrscheinlichkeitssätze unter Verwendung der Zählwerte und zum Bereitstellen eines Auswahlsignals, das angibt, welche Wahrscheinlichkeitssätze ermittelt wurden; ein Mittel zum Codieren des Auswahlsignals, um dadurch ein codiertes Auswahlsignal zu erzeugen; ein Mittel zum arithmetischen Codieren der ersten und der zweiten Folge von Übereinstimmungswerten unter Verwendung der Wahrscheinlichkeitssätze, um dadurch codierte Übereinstimmungswerte auszugeben; und ein Mittel zum Bereitstellen des codierten binären Formsignals durch Multiplexen des codierten Auswahlsignals und der codierten Übereinstimmungswerte.
Vorrichtung nach Anspruch 11, bei welcher dem binären Pixel mit dem Übereinstimmungswert 0 eine größere Wahrscheinlichkeit und dem binären Pixel mit dem Übereinstimmungswert 1 eine kleinere Wahrscheinlichkeit zugeordnet wird, wenn der Zählwert ansteigt.
Vorrichtung zum Decodieren eines codierten binären Formsignals, um dadurch ein decodiertes binäres Formsignal bereitzustellen, mit: einem Mittel (220) zum arithmetischen Decodieren des codierten binären Formsignals, basierend auf Wahrscheinlichkeitssätzen, um dadurch decodierte binäre Daten bereitzustellen, die eine erste und eine zweite Folge enthalten, wobei die erste und die zweite Folge rekonstruierte Übereinstimmungswerte der binären Pixel aufweisen; einem Mittel (240) zum Berechnen einer Kontextzahl für alle binären Pixel, basierend auf einem entsprechenden Kontext, und zum Ermitteln einer der Kontextzahl entsprechenden Wahrscheinlichkeit, wobei der Kontext aus den binären Pixeln bestimmt wird, die vor jedem der binären Pixel rekonstruiert wurden; einem Mittel (250) zum Bestimmen eines Zustandes und eines vorhergesagten Pixelwertes von allen binären Pixeln durch Vergleich der Wahrscheinlichkeit mit vorgegebenen Schwellwerten; einem Mittel (260) zum Auswählen eines der rekonstruierten Übereinstimmungswerte für jeden binären Pixel aus der ersten oder der zweiten Folge als Antwort auf den Zustand jedes binären Pixels; und einem Mittel zum Rekonstruieren (260) eines binären Pixelwertes jedes binären Pixels durch Vergleich des ausgewählten rekonstruierten Übereinstimmungswertes mit dem vorhergesagten Pixelwert und zum sequentiellen Bereitstellen der rekonstruierten binären Pixelwerte, entsprechend der decodierten binären Daten, als das codierte binäre Formsignal.
Vorrichtung nach Anspruch 13, bei welcher das Decodiermittel (220) das codierte binäre Formsignal basierend auf denselben Wahrscheinlichkeitssätzen decodiert, wie sie bei einem Codierer verwendet werden, der das codierte binäre Formsignal bereitgestellt hat.
Vorrichtung nach Anspruch 13 oder 14, bei welcher der ausgewählte rekonstruierte Übereinstimmungswert aus der ersten Folge ausgewählt wird, falls der Zustand des binären Pixels der ersten Folge entspricht, und andernfalls der ausgewählte rekonstruierte Übereinstimmungswert aus der zweiten Folge ausgewählt wird.