Nothing Special   »   [go: up one dir, main page]

DE60015755T2 - Verlustfreie adaptive codierung von daten eines endlichen alphabets - Google Patents

Verlustfreie adaptive codierung von daten eines endlichen alphabets Download PDF

Info

Publication number
DE60015755T2
DE60015755T2 DE60015755T DE60015755T DE60015755T2 DE 60015755 T2 DE60015755 T2 DE 60015755T2 DE 60015755 T DE60015755 T DE 60015755T DE 60015755 T DE60015755 T DE 60015755T DE 60015755 T2 DE60015755 T2 DE 60015755T2
Authority
DE
Germany
Prior art keywords
parameter
value
coding
binary
decoding
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired - Lifetime
Application number
DE60015755T
Other languages
English (en)
Other versions
DE60015755D1 (de
Inventor
S. Henrique MALVAR
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Microsoft Corp
Original Assignee
Microsoft Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Priority claimed from US09/276,954 external-priority patent/US6850649B1/en
Priority claimed from US09/277,255 external-priority patent/US6477280B1/en
Priority claimed from US09/280,135 external-priority patent/US6678419B1/en
Application filed by Microsoft Corp filed Critical Microsoft Corp
Application granted granted Critical
Publication of DE60015755D1 publication Critical patent/DE60015755D1/de
Publication of DE60015755T2 publication Critical patent/DE60015755T2/de
Anticipated expiration legal-status Critical
Expired - Lifetime legal-status Critical Current

Links

Classifications

    • HELECTRICITY
    • H04ELECTRIC COMMUNICATION TECHNIQUE
    • H04NPICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/60Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using transform coding
    • H04N19/63Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using transform coding using sub-band based transform, e.g. wavelets
    • HELECTRICITY
    • H03ELECTRONIC CIRCUITRY
    • H03MCODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M7/00Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
    • H03M7/30Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
    • H03M7/40Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
    • HELECTRICITY
    • H03ELECTRONIC CIRCUITRY
    • H03MCODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M7/00Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
    • H03M7/30Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
    • H03M7/46Conversion to or from run-length codes, i.e. by representing the number of consecutive digits, or groups of digits, of the same kind by a code word and a digit indicative of that kind
    • HELECTRICITY
    • H04ELECTRIC COMMUNICATION TECHNIQUE
    • H04NPICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/60Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using transform coding
    • H04N19/63Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using transform coding using sub-band based transform, e.g. wavelets
    • H04N19/64Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using transform coding using sub-band based transform, e.g. wavelets characterised by ordering of coefficients or of bits for transmission
    • HELECTRICITY
    • H04ELECTRIC COMMUNICATION TECHNIQUE
    • H04NPICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/10Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding
    • H04N19/102Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding characterised by the element, parameter or selection affected or controlled by the adaptive coding
    • H04N19/13Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Multimedia (AREA)
  • Signal Processing (AREA)
  • Compression, Expansion, Code Conversion, And Decoders (AREA)
  • Compression Or Coding Systems Of Tv Signals (AREA)
  • Compression Of Band Width Or Redundancy In Fax (AREA)
  • Dc Digital Transmission (AREA)

Description

  • Erfindungsgebiet
  • Die vorliegende Erfindung betrifft allgemein die Bildkompression und insbesondere eine verbesserte Wavelet-Codierung und -Decodierung digitaler Bilder.
  • Urheberrechtliche Anmerkung/Genehmigung
  • Ein Teil der Offenlegung der vorliegenden Patents enthält Material, das dem Schutz des Urheberrechts unterliegt. Der Inhaber des Urheberrechts erhebt keinerlei Einwand gegen die Faksimile-Reproduktion der Patentschrift bzw. der Patentoffenlegung in der Form, in der sie in der Patentakte bzw. den Unterlagen im Patent- und Warenzeichenamt vorliegt, durch eine andere Person, behält sich ansonsten jedoch jeden urheberrechtlichen Schutz vor. Die folgende Anmerkung betrifft die Software und die Daten, die nachstehend beschrieben sind und in den Zeichnungen dazu vorkommen: Copyright@1998, Microsoft Corporation, alle Rechte vorbehalten.
  • Hintergrund der Erfindung
  • Digitale Bilder werden in vielerlei Anwendungen, wie beispielsweise auf Internetseiten, CD-Rom-Enzyklopädien, digitalen Kameras u. a. verwendet. In vielen Fällen ist es notwendig, die Bilder zu komprimieren, damit sie in einen kleinen Speicher passen oder in kurzer Zeit heruntergeladen werden können. So werden beispielsweise bei einer typischen Digitalkamera die Bilder mit einer Auflösung von 1024 × 768 Bildelementen (Pixel) mit einer Auflösung von 12 bis 24 Bit pro Pixel aufgenommen. Die Rohdaten in jedem Bild betragen daher etwa 1,2 bis 2,5 Megabyte. Um beispielsweise zu gewährleisten, dass mehrere Bilder auf eine Computerdiskette passen, ist es notwendig, die von jedem Bild verbrauchte Datenmenge zu reduzieren. Je größer das Komprimierungsverhältnis ist, das sich erreichen lässt, desto mehr Bilder passen auf eine Diskette oder in eine Speicherkarte und desto schneller können sie über ein Übertragungsmedium mit begrenzter Bandbreite, wie beispielsweise Telefonleitungen, übertragen werden.
  • Die Bildkomprimierung ist in den vergangenen zwanzig Jahren umfassend untersucht worden. Der JPEG-Standard, definiert von dem JPEG-Komitee (Joint Photografic Experts Group) der ISO (International Standards Organisation), wurde 1992 definiert und ist das beliebteste Verfahren zur Komprimierung digitaler Bilder. In JPEG werden kleine quadratische Pixelblöcke (mit den Abmessungen 3 × 3) mittels diskreter Cosinus-Transformation (DCT) in einen Frequenzbereich abgebildet. Die DCT-Koeffizienten werden quantisiert (durch einen Skalierungsfaktor dividiert und zur nächsten Ganzzahl gerundet) und über ein festgelegtes Zickzack-Abtastmuster auf einen eindimensionalen Vektor abgebildet. Jener Vektor wird über eine Kombination aus Lauflängen- und Huffman-Codierung codiert.
  • Die unabhängige Verarbeitung kleiner 8 × 8-Blöcke in JPEG ist ein Vorteil aus Implementierungssicht, speziell bei kostengünstiger Hardware. Allerdings führt sie auch zu dem Hauptproblem bei JPEG: Blockierungs-Artefakte. Da die Quantisierungsfehler von benachbarten Blöcken zwischen den Blöcken nicht miteinander korrelieren, aber innerhalb der Blöcke korrelieren, werden die Grenzen der 8 × 8-Blöcke in dem wiederhergestellten Bild infolge des potenziellen Unterschieds bei der Codierung zwischen angrenzenden Blöcken sichtbar. Derartige Artefakte bzw. Bildfehler werden als Blockierungs-Artefakte bezeichnet, die mithilfe von Transformierten mit überlappenden Basisfunktionen verringert (wenngleich nicht vollständig eliminiert) werden können.
  • Eine wirksame Möglichkeit zum Entfernen der Blockierungs-Bildfehler besteht darin, die Block-DCT durch eine Wavelet-Zerlegung zu ersetzen, die eine effiziente Zeit-Frequenz-Darstellung bietet. Eine sehr gute Komprimierungsleistung wird durch Quantisieren und Codieren von Wavelet-Koeffizienten erreicht.
  • In den letzten Jahren wurde in der Fachliteratur über viele Wavelet-basierte Bildkomprimierungssysteme berichtet. Mit Wavelets lassen sich Komprimierungsverhältnisse erreichen, die meist 20 bis 50 Prozent besser als bei JPEG sind. Wichtiger noch führen die Wavelet-Tranformierten zu Bildern, die nicht die störenden Blockierungs-Bildfehler von JPEG aufweisen. Daher werden Wavelet-basierte Transformierte immer beliebter. So verwenden bei der nächsten Überarbeitung von JPEG mit dem Namen JPEG 2000 sämtliche berücksichtigte Vorschläge Wavelets.
  • Einige der früheren Wavelet-Transformierten zerlegen Bilder in Koeffizienten, die 16 Teilbändern entsprechen. Daraus entsteht eine 4 × 4-Matrix aus Teilbändern, das so genannte Großblockformat, welches die Spektralzerlegung und die Anordnung von Kanälen darstellt. Die Buchstaben L und H werden zur Kennzeichnung der Tiefpassfilterung und der Hochpassfilterung für jedes Teilband verwendet. Das ersten Teilband umfasst LL und HL-Koeffizienten, wobei der erste Buchstabe in jeder Gruppe der horizontalen Filterung und der zweite der vertikalen Filterung entspricht. Bei jeder Teilband-Filterkombination werden zwei Stufen verwendet. Die Anordnung entspricht den Frequenzen, die von links nach rechts und von unten nach oben ansteigen. Diese Anord nung ist festgelegt, damit sowohl die Codeirung auch die Decodierung in festgelegter Art und Weise ablaufen. Danach erfolgt die Quantisierung der Koeffizienten, gefolgt von einer gewissen Form der komprimierenden Codierung der Koeffizienten, einschließlich der adaptiven Huffman-Codierung oder der arithmetischen Codierung, um das Bild weiter zu komprimieren. Diese Formen der Codierung können recht komplex sein, einschließlich von Zero-Tree-Strukturen, die von den Datentypen abhängen. Diese Codierer sind recht kompliziert und viele müssen für unterschiedliche zu komprimierende Bilder modifiziert werden, wodurch sie sich nur schwer in Hardware umsetzen lassen.
  • Eine Lösung für die Komplexität der Zero-Tree-basierten Ansätze zum Ordnen der Wavelet-Koeffizienten ist offen gelegt durch E. Ordentlich et al.: „A low complexity modeling approach for embedded coding of wavelet compression coefficients", Protokoll DCC 1998 Data Compression Conference (CAT. No. 98TB100225), Protokoll DCC 1998 Data Compression Conference, Snowbird, UT, USA, 30. März – 1. April 1998, Seiten 408–417, XP000925096, 1998 Los Alamitos, Ca, USA, IEEE Comput. Soc., ISBNO-8406-2. Ordentlich legt einen Zweistufenprozess offen, bei dem eine Gruppe von Koeffizienten als Funktion zuvor codierter Informationen außerhalb der Gruppe in zwei oder mehr Sätze von Koeffizienten zerlegt wird. Die zweite Stufe zerlegt die zwei oder mehr Sätze von Koeffizienten mithilfe der gewöhnlichen Kontextmodellierung, eingegrenzt durch eine ausgewählte Reihenfolge. Die entstehenden Zeichen werden anschließend mit einem adaptiven Lauflängen-Golomb-Rice-Codierer codiert.
  • Benötigt wird ein einfaches Codierverfahren, das bei Wavelet-Komprimierungskoeffizienten und ähnlichen Daten eines finiten Alphabets funktioniert und sowohl in Hardware als auch Software implementiert werden kann.
  • G. G. Langdon Jr. „An Adaptive Run-Length Coding Algorithm", IBM Technical Disclosure Bulletin, Band 26, Nr. 7b, Dezember 1983, Seiten 3783 bis 3785 legt einen adaptieren Lauflängen-Codieralgorithmus offen, der einen nicht adaptiven Lauflängencode nach Golomb und ein binäres adaptives Verfahren miteinander kombiniert. Die zur Anpassung verwendete Zähleinrichtung wird ebenfalls für den Codierer verwendet. Als Codierparameter wird eine Variable K eingesetzt, und eine andere Variable ist Count (Zählung), die eine binäre Ganzzahl speichert. Wenn Count einen bestimmten Punkt erreicht, wird der Wert von K inkrementiert, wodurch der Code verändert wird. Wenn ein „Nichtwiederholungs-"Ereignis vorliegt, wird die Variable K dekrementiert. Vor dem Dekrementieren von K erfolgen Verschiebeoperationen. Am Anfang des Codieralgorithmus wird K festgelegt. Der Decodierer beginnt mit einem Anfangswert für K.
  • T. Bell et al. „Modeling for Text Compression, ACM Computing Surveys, Band 21, Nr. 4, Dezember 1989, Seiten 557 bis 591, beschreibt ein Modellerstellungsverfahren für eine Textkomprimierung. Hierbei werden adaptive und nichtadaptive Modelle erörtert. Bei der adaptiven Modelerstellung nehmen sowohl der Codierer als auch der Decodierer anfangs einen bestimmten Bland-Modus ein, bei dem beispielsweise sämtliche Zeichen gleichwahrscheinlich sind und anschließend werden ihre Modelle in der gleichen Art und Weise, z.B. durch Vergrößern der Wahrscheinlichkeit des beobachteten Symbols, aktualisiert.
  • Die Aufgabe der Erfindung besteht darin, ein verbessertes, einfacheres Codierverfahren zu schaffen.
  • Diese Aufgabe wird durch die Erfindung gemäß den unabhängigen Ansprüchen gelöst. In den abhängigen Patenansprüchen sind bevorzugte Ausführungsformen definiert.
  • Die adaptive Codierung erfolgt an mit Vorzeichen versehenen Ganzzahldaten, bei denen Werte geringerer Größe wahrscheinlicher sind als jene mit größerer Größe. Die Codierung findet in Bitplanes statt, was eine Skalierbarkeit bei der Wiederherstellungsgenauigkeit ermöglicht, von verlustfrei (keine Fehler) bis zu verschiedenen Niveaus der approximierten Wiederherstellung. Im Unterschied zur Huffman-Codierung werden keine Code-Tabellen benötigt, da einfache Regeln die Codewörter aus den Eingabe-Strings ermitteln.
  • Bei einer Form wird für jede Bitplane das kürzeste Codewort (eine einfache 0) zugeordnet, um einen Lauf der wahrscheinlichsten Eingabe, Null, mit einer Länge von 2k darzustellen, wobei k ein Parameter ist, der die Codeworte steuert, die zum Darstellen von Strings quantisierter Koeffizienten verwendet werden, und versucht wird, die Anzahl von Bits in den Codewörtern zu minimieren. k wird vergrößernd adaptiert, wenn längere Läufe vorkommen, und ansonsten verkleinert, z.B. wenn Symbole auftreten, die sich von jenen in dem Lauf unterscheiden. Die Codierung der Bitplanes kann mit einem effizienten Entropie-Codierer erfolgen, z.B. mit einem adaptiven arithmetischen Codierer, bei einer Implementierung wird jedoch ein neuer, adaptiver Lauflängen-Golomb-Rice-Codierer verwendet.
  • Da keine datenabhängigen Datenstrukturen, wie beispielsweise Zero-Trees oder eine separate Liste für Satzpartitionen in Bäumen benötigt werden, lassen sich Hardware-Implementierungen leichter bauen, und Software-Implementierungen laufen schneller.
  • Kurze Beschreibung der Zeichnungen
  • 1 ist ein Blockdiagramm eines Computersystems, auf das die vorliegende Erfindung angewendet werden kann.
  • 2 ist ein Blockdiagramm eines Codierers, der Wavelet-Koeffizienten neu ordnet und sie anschließend in einer verlustfreien, adaptiven Art und Weise codiert.
  • 3 ist ein Blockdiagramm eines Decoders, der die codierten Koeffizienten, die von dem Codierer aus 2 erzeugt wurden, decodiert und unshuffled.
  • 4 ist ein Blockdiagramm der umgeordneten Wavelet-Koeffizienten, die von dem Codierer aus 2 erzeugt wurden.
  • 5 ist ein Ablaufdiagramm, das den Hochpegelbetrieb des Koeffizienten-Codierers aus 2 darstellt, der die Koeffizienten in Bitplanes unterteilt.
  • 6 ist ein Ablaufdiagramm, das ein weiteres Detail der Funktionsweise des Lauflängen-adaptiven Codierers aus 2 darstellt.
  • 7 ist ein Ablaufdiagramm, das das Schreiben einer Matrix aus Koeffizienten in neu geordneter Weise entsprechend jener aus 4 darstellt.
  • 8 ist ein Blockdiagramm, das die Verwendung des Codierers aus 2 und des Decodierers aus 3 in einer Software-Anwendungssuite zeigt, die Bilddaten bearbeitet.
  • Detaillierte Beschreibung
  • In der nachfolgenden detaillierten Beschreibung exemplarischer Ausführungsformen der Erfindung wird auf die beiliegenden Zeichnungen Bezug genommen, die einen Teil der Beschreibung bilden und in denen zur Veranschaulichung spezielle exemplarische Ausführungsformen abgebildet sind, die eine praktische Umsetzung der Erfindung darstellen. Diese Ausführungsformen sind so detailliert beschrieben, dass Fachleute die Erfindung anwenden können, und natürlich ist davon auszugehen, dass weitere Ausführungsformen zum Einsatz kommen können und logische, mechanische, elektrische oder andere Änderungen vorgenommen werden können, ohne vom Schutzumfang der Erfindung abzuweichen. Die nachfolgende detaillierte Beschreibung ist daher nicht in einem eingrenzenden Sinn aufzufassen, und der Schutzumfang der Erfindung ist lediglich durch die beiliegenden Patentansprüche definiert.
  • Die detaillierte Beschreibung ist in mehrere Abschnitte untergliedert. Ein erster Abschnitt beschreibt die Funktionsweise eines Computersystems, das die vorliegende Erfindung umsetzt. Anschließend erfolgt eine genaue Beschreibung einer festgelegten Neuordnung der quantisierten Wavelet-Koeffizienten und deren adaptiver Lauflängencodierung.
  • Darüber hinaus wird ein Decodierer für derartige codierte Daten beschrieben. Im Anschluss werden mithilfe von Ablaufdiagrammen weitere Details ausgewählter Blöcke der genauen Beschreibung erörtert. Darauf folgt eine allgemeine Beschreibung der Anwendung derartiger Codierer und Decodierer in einer Office Suite von Softwareanwendungen. In der Schlussfolgerung werden potenzielle Vorteile und weitere alternative Ausführungsformen beschrieben.
  • Hardware- und Betriebsumgebung
  • 1 ist eine kurze, allgemeine Darstellung einer geeigneten Rechnerumgebung, in der die Erfindung zum Einsatz kommen kann. Nachstehend wird die Erfindung im allgemeinen Kontext von computerlauffähigen Programmmodulen beschrieben, die Befehle enthalten, die von einem Personalcomputer (PC) ausgeführt werden können. Programmmodule enthalten Routinen, Programme, Objekte, Komponenten, Datenstrukturen usw., die spezielle Aufgaben ausführen und spezielle abstrakte Datentypen implementieren. Für Fachleute liegt es auf der Hand, dass die Erfindung mit anderen Computersystem-Konfigurationen praktiziert werden kann, einschließlich von Handgeräten, Multiprozessor-Systemen, programmierbarer Unterhaltungselektronik auf Mikroprozessor-Basis, Netzwerk-PCs, Minicomputern, Mainframe-Computern und dergleichen, die über Multimedia-Fähigkeiten verfügen. Die Erfindung kann ebenfalls in verteilten Rechnerumgebungen zur Anwendung kommen, in denen die Aufgaben durch entfernte Verarbeitungseinrichtungen ausgeführt werden, die über ein Datennetzwerk miteinander verbunden sind. In einer verteilten Rechnerumgebung können Programmmodule sowohl in lokalen als auch in entfernten Speichereinrichtungen vorliegen.
  • 1 zeigte eine universelle Computereinrichtung in Form eines konventionellen Personalcomputers 20, der über eine Verarbeitungseinheit 21, einen Systemspeicher 22 und einen Systembus 23 verfügt, der den Systemspeicher und die anderen Systemkomponenten mit der Verarbeitungseinheit 21 verbindet. Bei dem Systembus 23 kann es sich um einen von mehreren Typen handeln, einschließlich eines Speicherbusses oder einer Speichersteuerung, eines peripheren Busses und eines lokalen Busses, und er kann eine beliebige aus einer Vielzahl von Busstrukturen anwenden. Der Systemspeicher 22 enthält ein Read Only Memory (ROM) 24 und ein Random Access Memory (RAM) 25. Ein Basic-Input/Output-System (BIOS) 26, das im ROM 24 gespeichert ist, enthält die Basis-Routinen, die die Informationen zwischen den Komponenten des Personalcomputers 20 übertragen. Das BIOS 26 enthält weiterhin Startroutinen für das System. Der Personalcomputer 20 verfügt zudem über das Festplattenlaufwerk 27 zum Lesen einer Festplatte (nicht abgebildet) und zum Schreibett auf selbige, ein Magnetplatten-Laufwerk 28 zum Lesen einer entnehmbaren Magnetplatte 29 und zum Schreiben auf selbige und einen optischen Datenträger 30 zum Lesen einer entnehmbaren Bildplatte 31, z.B. ein CD-ROM oder ein anderes optisches Medium, und zum Schreiben auf selbige. Das Festplattenlaufwerk 27, das Magnetplattenlaufwerk 28 und der optische Datenträger 30 sind über eine Festplattenlaufwerk-Schnittstelle 32, eine Magnetplattenlaufwerk-Schnittstelle 33 und eine Schnittstelle 34 für den optischen Datenträger mit dem Systembus 23 verbunden. Die Laufwerke und deren dazugehörige computerlesbare Medien bieten eine nichtflüchtige Speichermöglichkeit für computerlesbare Befehle, Datenstrukturen, Programmmodule und andere Daten für den Personalcomputer 20. Obwohl die hier beschriebene exemplarische Umgebung eine Festplatte, eine entnehmbare Magnetplatte 29 und eine entnehmbare Bildplatte 31 verwendet, so liegt für Fachleute auf der Hand, dass auch andere Arten computerlesbarer Medien, die für einen Computer zugreifbare Daten speichern können, bei der exemplarischen Betriebsumgebung verwendet werden können. Zu solchen Medien gehören Magnetkassetten, Flash-Speicherkarten, universelle digitale Platten, Bernoulli-Kassetten, RAMs, ROMs und dergleichen. Programmmodule können auf der Festplatte, der Magnetplatte 29, der optischen Platte 31, dem ROM 24 und RAM 25 gespeichert werden. Zu den Programmmodulen können das Betriebssystem 35, ein oder mehrere Anwendungsprogramme 36, weitere Programmmodule 37 und Programmdaten 38 gehören. Ein Benutzer kann über Eingabevorrichtungen, wie beispielsweise eine Tastatur 40 und eine Zeigereinrichtung 42, Befehle und Information in den Personalcomputer 20 eingeben. Andere Eingabevorrichtungen (nicht abgebildet) umfassen ein Mikrofon, einen Joystick, ein Gamepad, eine Satellitenschüssel, einen Scanner und Ähnliches. Diese und andere Eingabevorrichtungen sind oft über eine Schnittstelle 46 für einen seriellen Port, die mit dem Systembus 23 verbunden ist, an die Verarbeitungseinheit 21 angeschlossen; sie können aber auch über andere Schnittstellen angeschlossen sein, die nicht in 1 abgebildet sind, wie beispielsweise über einen parallelen Port, einen Gameport oder einen universellen Serienbus (USB). Ein Monitor 47 oder eine andere Anzeigevorrichtung sind ebenfalls mit einem Systembus 23 verbunden, und zwar über eine Schnittstelle, wie beispielsweise einen Videoadapter 48. Zusätzlich zu dem Monitor verfügen Personalcomputer meist über weitere periphere Ausgabevorrichtungen (nicht abgebildet), wie beispielsweise Lautsprecher und Drucker. Personalcomputer 20 können mithilfe logischer Verbindungen zu einem oder mehreren entfernten Rechnern, wie beispielsweise dem entfernten Rechner 49, in einer vernetzten Umgebung arbeiten. Bei dem entfernten Rechner 49 kann es sich um einen weiteren Personalcomputer, einen Server, einen Router, einen Netzwerk PC, eine Partnervorrichtung oder um einen anderen üblichen Netzwerkknoten handeln. Im typischen Fall verfügt er über viele oder alle der oben im Zusammenhang mit dem Personalcomputer 20 beschriebenen Komponenten, von denen jedoch in 1 lediglich eine Speichervorrichtung 50 dargestellt ist. Zu den logischen Verbindungen aus 1 gehören ein Local Area Network (LAN) 51 und ein Wide Area Network (WAN) 52. Derartige Netzwerkumgebungen sind in Büros, in unternehmensweiten Computernetzwerken, Intranets und im Internet allgemein üblich.
  • Bei Anordnung in einer LAN-Netzwerkumgebung ist der PC 20 über eine Netzwerkschnittstelle oder einen Adapter 53 mit dem lokalen Netzwerk 51 verbunden. Bei Verwendung in einer WAN-Netzwerkumgebung, wie beispielsweise dem Internet, gehört zu den PC 20 meist ein Modem 54 oder eine andere Einrichtung zur Herstellung einer Datenübertragungsverbindung über das Netzwerk 52. Das Modem 54 kann intern oder extern zu dem PC 20 gehören und ist über eine serielle Schnittstelle 46 an den Systembus 23 angeschlossen. In einer vernetzten Umgebung können Programmmodule, wie beispielsweise jene, die Microsoft® Word umfassen, die in der Abbildung als resident im PC 20 dargestellt sind, oder Teile davon in einer entfernten Speichervorrichtung 50 gespeichert werden. Natürlich sind die dargestellten Netzwerkverbindungen lediglich zur Veranschaulichung gedacht, und sie können durch andere Einrichtungen, die eine Datenübertragungsverbindung zwischen den Computern herstellen, ersetzt werden.
  • Mithilfe vieler verschiedener Verfahren, einschließlich objektorientierter Programmierverfahren, kann die Software erstellt werden. C++ und Java sind zwei Beispiele für allgemeine objektorientierte Computerprogrammiersprachen, die eine Funktionalität im Zusammenhang mit der objektorientierten Programmierung bereitstellen. Objektorientierte Programmierverfahren sind ein Mittel zum Verkapseln von Datenelementen (Variablen) und Elementfunktionen (Verfahren), die auf jene Daten einwirken, in einer einzigen Einheit, auch als Klasse bezeichnet. Objektorientierte Programmierverfahren bieten weiterhin eine Möglichkeit, auf Grundlage vorhandener Klassen neue Klassen zu erzeugen.
  • Ein Objekt ist eine Instanz einer Klasse. Die Datenelemente eines Objekts sind Attribute, die innerhalb des Computerspeichers gespeichert sind, und die Verfahren sind ein lauffähiger Computercode, der auf diese Daten einwirkt, während potenziell noch andere Dienste bereitgestellt werden. Der Begriff eines Objekts wird bei der vorliegenden Erfindung so gebraucht, dass bestimmte Aspekte der Erfindung als Objekte in einer Ausführungsform implementiert sind.
  • Eine Schnittstelle ist eine Gruppe zusammengehöriger Funktionen, die in einer benannten Einheit organisiert sind. Jede Schnittstelle kann durch eine Kennung eindeutig identifiziert werden. Schnittstellen haben keine Instanziierung, das heißt, eine Schnittstelle ist eine Definition, nur ohne den lauffähigen Code, der zum Implementieren der Verfahren benötigt wird, die von der Schnittstelle angegeben werden. Ein Objekt kann eine Schnittstelle unterstützen, indem ein lauffähiger Code für die von der Schnittstelle angegebenen Verfahren bereitgestellt wird. Der von dem Objekt zugeführte lauffähige Code muss mit den von der Schnittstelle angegebenen Definitionen übereinstimmen. Das Objekt kann zudem weitere Verfahren bereitstellen. Fachleute erkennen, dass Schnittstellen nicht auf die Verwendung in einer oder durch eine objektorientierte Programmierumgebung begrenzt sind.
  • Genaue Beschreibung des Codierers und Decodierers
  • Ein vereinfachtes Blockdiagramm einer Wavelet-Tranformierten auf der Basis eines Bildpixel-Codierers ist in 2 abgebildet, wobei ein entsprechender Decodierer in 3 zu sehen ist. Zwar werden der Codierer und Decodierer im Hinblick auf Bildpixeldaten als die jeweiligen Eingabe- und Ausgabegrößen beschrieben, doch es können, falls gewünscht, auch andere Daten transformiert werden. Bei der abgebildeten Ausführungsform werden Bildpixeldaten zu einem Wavelet-Transformierungsblock 210 zugeführt, der in bekannter Art und Weise arbeitet und so Wavelet-Koeffizienten an einen Quantisierblock 220 liefert. Die Wavelet-Koeffizienten haben das Format eines großen Blocks, wie bereits in dem Abschnitt zum Hintergrund der Technik beschrieben. Die Quantisierung erfolgt mittels eines gleichförmigen Quantisierers, der von einer einen Quantisierungsschritt definierenden Schwelle T angesteuert wird. Dies führt zu der Darstellung jedes Koeffizienten, der zwischen den Stufen um den Wert in der Mitte der Stufe abfällt. Je kleiner T ist, desto geringer ist der Verlust bei der Quantisierung. Somit ist die Ausgangsgröße von Block 220 eine Reihe von Ganzzahlen, bei denen es sich um quantisierte Wavelet-Koeffizienten handelt. Wie aus vielen anderen Anwendungen bekannt, kann der Quantisierer auf der Basis des normalen Rundens arbeiten oder gegen null runden (auch bekannt als Quantisierer mit einer „toten Zone").
  • Eine Neuordnungs- und Blockierfunktion bzw. ein -Block 230 gruppiert die Wavelet-Koeffizienten in Cluster aus gleichen Werten. Daraus entsteht eine Clusterbildung bzw. Gruppierung von Blöcken von Frequenzkoeffizienten, die höchstwahrscheinlich null sind. Durch die Neuordnung wächst die Wahrscheinlichkeit der Gruppierung ähnlicher Daten in dem Sinne, dass die Daten dazu neigen, eine monoton abfallende Amplitudenvertei lung aufzuweisen. Die ersten Blöke tendieren dazu, Daten mit größer Amplitude aufzuweisen, wohingegen nachfolgende Blöcke Amplituden der Wavelet-Koeffizienten haben, die eine abfallende Tendenz aufweisen. Die Gruppierung erfolgt durch Festlegen einer Abtastreihenfolge, die datenunabhängig ist. Ein derartiger Gruppierungssatz ist in 4 abgebildet und hat beispielsweise 64 Blöcke von Wavelet-Koeffizienten. In 4 sind Komponenten mit niedriger Frequenz zur oberen linken Ecke der Gruppierung hin angeordnet, wobei sich Koeffizientenblöcke von Tief-Hoch-Teilbändern und Hoch-Tief-Teilbändern auf jeder Stufe abwechseln. Durch den Neuordnungs- und Blockierblock 230 entsteht in der angegebenen Abtastreihenfolge eine Sequenz aus Makroblöcken. Der erste Block 0 enthält sämtliche Koeffizienten der Ebene 0 des Wavelet-Baums. Dies entspricht der gröbsten Auflösung. Die Blöcke 0 bis 3 umfassen sämtliche Koeffizienten der Ebene 1. Die Blöcke 0 bis 15 umfassen alle Koeffizienten der Ebene 2, während Ebene 3 die Blöcke 0 bis 63 umfasst. Es sei angemerkt, dass sich auf jeder Ebene die Blöcke von den Tief-Hoch-Teilbändern und den Hoch-Tief-Teilbändern abwechseln, wobei ein Tief-Hoch-Teilband oben an der Sequenz steht. In dem nachfolgenden Abschnitt ,Mathematische Beschreibung' werden wir die Vorteile jener speziellen Anordnung erörtern. Möglich sind auch andere Anordnungen, wie für Fachleute deutlich wird, doch die obige Anordnung scheint besser zu funktionieren als andere. Die Bits werden sequenziell codiert, wobei mit dem signifikantesten Bit begonnen wird. Ein adaptiver Codierblock 240 empfängt die Makroblöcke und codiert sie verlustfrei. Durch das Clustern der Blöcke entstehen zu komprimierende Daten, die große Null-Cluster aufweisen. Eine weitere Neuordnung der Daten durch Codieren auf der Basis einer Bitplane erhöht die Wahrscheinlichkeit, große Null-Strings zu finden. Fängt man mit dem signifikantesten Bit für die erste Bitplane an, so führt dies zu einer höheren Wahrscheinlichkeit eines langen String aus Nullen. Zudem wird dadurch sichergestellt, dass die relevantesten Daten zuerst codiert werden. Wenn dann die dritte oder vierte Bitplane codiert wird, stehen die Chancen für eine 0 und eine 1 etwa gleich, und es kann effektiv eine direkte binäre Codierung ausgeführt werden.
  • Der Codierer ist eine Adaption eines Golomb-Rice-Codierers mit adaptiven Lauflängenmodifizierungen. Einfach ausgedrückt wird ein String aus 2k Nullen durch das Codewort repräsentiert, das aus einem einzigen Bit besteht, das gleich null ist. Die Länge des Strings aus Nullen, der von dem Null-Codewort repräsentiert wird, wird durch den Parameter k gesteuert, der sich bei Auftreten von Daten ausgehend von der beobachteten Häufigkeit von Nullen verändert. Wenn ein Nullwert codiert wird, wird angenommen, dass die Nullen wahrscheinlicher sind, so dass der Wert des Parameters k vergrößert wird. Wenn ein Wert ungleich null vorhanden ist, wird verkleinert. Durch angemessene Steuerung des Betrags einer solchen Erhöhung bzw. Verringerung kann der Codierer einen String aus Bits mit variierender Wahrscheinlichkeit von Nullen nachvollziehen, ohne dass der Overhead jene Wahrscheinlichkeit tatsächlich einschätzen muss. Um die rückwärts adaptive Art des Codierers 240 darzustellen, wird eine Rückkopplungsschleife 245 verwendet. Diese Codierung ermöglicht eine effiziente Komprimierung und schnelle Anpassung an Änderungen in der Statistik der eingehenden Daten. Der Codierer 240 gibt einen Bitstrom aus, der effektiv fortschreitend ist, da die signifikantesten Informationen am Anfang des Bitstroms stehen. Da die am wenigstens signifikanten Bits für die Bitströme mit geringerer Auflösung in der letzten Bitplane codiert werden, können sie effektiv gelöscht bzw. nicht codiert werden, wie durch einen Auflösungstreue-Block 250 dargestellt. Möglich ist dieser bei Datenübertragungen mit geringerer Bandbreite.
  • Das Decodieren, wie in Blockform in 3 abgebildet, ist im Wesentlichen die Umkehrung der Codierung und der Datentransformationen. Ein Bitstrom aus codierten Daten, z.B. jene, die von dem Codierer aus 2 erzeugt werden, wird in einem verlustfreien adaptiven Decodierblock 310 empfangen. Der Bitstrom kann direkt von dem Decodierer, von einem lokalen Speicher oder von einem entfernten Decodierer oder Speicher über eines von vielen Übertragungsmedien empfangen werden, z.B. durch Satellitenübertragung, Kabelübertragung oder ein anderes Netzwerk. Der Decodierblock 310 empfängt die Regeln, die während des Codierens über eine Vorwärtszuführleitung 315 entwickelt wurden Block 310 empfängt im Wesentlichen die String-Länge, die zu verwenden ist, und rekonstruiert die Daten entsprechend den Regeln. Erneut arbeitet er auf Blockebene, dies ist jedoch kein erfindungsgemäßes Erfordernis. Es ist jedoch praktischer als das Arbeiten an einer Gesamtdarstellung eines Bildes oder anderer Daten auf einmal, wozu eine größere Speicherkapazität erforderlich wäre, oder aber das Paging, falls ein solcher Speicher nicht zur Verfügung steht. Eine Form der Verringerung der Wiedergabetreue kann am Block 310 erfolgen, indem das letzte Bit in der Bitplane einfach nicht decodiert wird. Dadurch wird die Stufengröße, die von dem Parameter T gesteuert wird, effektiv verdoppelt. Es ist eine einfache Art und Weise, die Wiedergabetreue der Daten zu verringern.
  • Die Daten aus dem Block 310 sollten mit den ganzzahligen Daten aus Block 230 identisch sein. Allerdings können die Schichten mit höherer Auflösung des Bildes an diesem Punkt, angegeben mit Block 320, entfernt werden, indem einfach die Wavelet-Koeffizienten höherer Frequenz nicht verwendet werden. Sinnvoll wäre dies, wenn das zur Anzeige eines Bildes oder eines Bildsatzes verwendete Fenster klein ist. Anschlie ßend wird Block 330 verwendet, um die Blocke wieder in ihre ursprünglichen Positionen zurückzubringen bzw. umzuordnen. Die Ausgangsgrößen des Neuordnungsblocks 330 sind Ganzzahlen, die bei Block 340 unter Verwendung der Stufengröße, die von einem Header in dem empfangenen Bitstrom angegeben wird, zurückmultipliziert werden müssen. Dadurch entstehen rekonstruierte Wavelet-Koeffizienten. Der Header gibt ebenfalls Informationen darüber an, wie groß das Bild ist, und andere Standard-Bildformatdaten. Anschließend erfolgt bei 350 eine Umkehr-Wavelet-Transformation in bekannter Art und Weise. Es sollte erwähnt werden, dass die einzigen Verluste, abgesehen von den gewünschten und ausgewählten Verringerungen der Wiedergabetreue bzw. der Auflösung, in den Quantisierungsschritten auftreten, was sich durch Modifizierung des Parameters T steuern lässt.
  • Der Block zur wahlweisen Verringerung der Auflösung 320 kann auf verschiedene Art arbeiten. Eine Möglichkeit besteht darin, die Daten zu empfangen, indem die ganzen Zahlen genullt werden. Eine weitere Möglichkeit zur Verringerung der Auflösung besteht darin, die Funktionsweise des Unshuffle-Blocks 330 zu modifizieren, dem der Befehl erteilt werden kann, die Werte an einen bestimmten Punkt auf null zu setzen. Indem sowohl dem Unshuffle-Block 330 und dem Umkehr-Wavelet-Tranformationsblock 350 vorgegeben wird, wo die Nullen beginnen, können sie ohne, weiteres dahingehend modifiziert werden, dass die unnötige Verarbeitung tatsächlicher Daten an derartigen Punkten weggelassen wird.
  • Das erfindungsgemäße adaptive Codieren und Decodieren funktioniert sehr gut an Daten, die geclusterte Nullen mit sich ändernden Statistiken haben. Diese Art von Daten kann auch aus einer mit einer hohen Wahrscheinlichkeit von Daten mit nahezu exponentiellem Abfall der Wahrscheinlichkeit auf beiden Seiten der Nullen gekennzeichnet sein. Multimediadaten, beispielsweise statische Bilddaten und Videodaten haben diese Eigenschaft. Weiterhin hat auch die Transformation vieler Arten physischer Daten diese Eigenschaft. Beim Erfassen der physischen Daten tritt die Information normalerweise nur an wenigen Stellen auf, was bedeutet, dass die meisten anderen Daten null betragen. Ebenso ist eine Symmetrie der Daten wünschenswert bei dieser Art der Codierung, damit sie am besten funktioniert. Anders ausgedrückt, ein exponentieller Abfall sowohl der negativen als auch der positiven Werte auf beiden Seiten einer Informationsspitze ist von Vorteil. Beispiele für derartige physische Daten umfassen ECGs und andere biometrische Datentypen.
  • Mathematische Beschreibung der Codierung
  • Nun folgt eine mathematische Beschreibung der oben anhand der 2 und 3 erörterten Transformierungen sowie der Codierung und Decodierung. Die folgenden Schritte definieren den Codier-Algorithmus.
    • 1. In Anbetracht eines Bildfeldes x(m,n), m = 0, 1, ..., M–1, n = 0, 1,..., N–1, Berechnung von dessen Wavelet-Transformierungskoeffizienten X(r, s), r = 0, 1, ..., M–1, s = 0, 1, ..., N–1.
    • 2. Jeder Koeffizient X(r,s) wird entsprechend q(r,s) = sgn(X(r,s))⌊|X(r,s)|/T⌋ (1)quantisiert, wobei sgn( ) die gewöhnliche Signum-Funktion und T eine Quantisierungsschwelle ist. Dieser Schritt bildet die kontinuierlichen Wavelet-Koeffizienten X(r,s) in einer Sequenz aus ganzen Zahlen q(r,s) ab. Dies ist der einzige Schritt, bei dem es zu einem Informationsverlust kommt.
    • 3. Die quantisierten Koeffizienten werden in Blöcken gemäß uk(l) = q(rk + mod(l, MB), sk + ⌊l/MB⌋) (2)für l = 0, 1, ..., L–1 und k=0, 1, ..., K–1 neu geordnet und gruppiert, wobei L= MBNB die Blockgröße ist, K=MN/L die Gesamtanzahl von Blöcken ist und MB und NB durch MB=M/2J und NB=N/2J definiert sind. Der Parameter J steuert die Größe der rechteckigen Blöcke aus quantisierten Koeffizienten, die in uk(l) gruppiert sind, und folglich die Blockgröße. Für jedes k sind die Indizes der oberen linken Ecke (rk, sk) entsprechend der bereits beschriebenen Abtastreihenfolge definiert.
    • 4. Die Blöcke werden in Makroblöcken Ui der feststehenden Größe LKB in Form von Ut = {uk (l)} gruppiert, wobei k=iKB, iKB+1, iKB + KB–1. .....
  • Für jeden Makroblock werden seine Bitplanes nacheinander entsprechend dem adaptiven Lauflängen/Rice-(RLR)-Codierer quantisiert. Die binäre Codierung der Anzahl von Bits, die von dem RLR-Code für Ui verwendet werden, gefolgt von den tatsächlich ausgegebenen RLR-Bits, wird an den ausgegebenen Bitstrom angehängt.
  • Anschließend werden die folgenden Schritte zum Decodieren des PWC-Bit-Stroms angewandt: Decodieren der RLR-codierten Bits in Makroblöcken Ut für i: 0, 1, ... lmax–1.
    • 1. Wenn lmax < K, wird eine Version der Wavelet Koeffizienten mit niedrigerer Auflösung wiederhergestellt. Es ist zu berücksichtigen, dass angesichts der gewünschten Wiederherstellungsgenauigkeit innerhalb jedes Makroblocks lediglich die ersten Bitplanes decodiert werden. Alle Bits in den Bitplanes von q(rs), die nicht decodiert werden sollen, werden auf null gesetzt. Die Skalierbarkeit der Auflösung wir erreicht, indem lmax < K gewählt wird, wohingegen die Skalierbarkeit der Wiedergabetreue erreicht wird, indem lediglich ein Teilsatz der Bitplanes für jeden Makroblock decodiert wird.
    • 2. Nach Wiederherstellung von q(rs) werden die Wavelet-Koeffizienten wiederhergestellt durch:
      Figure 00140001
      Es sei angemerkt, dass die Quantisierungsregel aus (2), kombiniert mit der Rekonstruktionsregel aus (3), einen gleichförmigen Quantisierer mit einer toten Zone um den Ausgangwert herum umfasst, der nahezu optimal für eine skalare Minimalentropie-Quantisierung zufälliger Variablen mit Laplace-Wahrscheinlichkeitsverteilung (doppelseitig exponentiell) ist.
  • Zur Neuordnung der Wavelet-Koeffizienten, wie in Schritt 3 des PWC-Codierers beschrieben, wird die Sequenz der Indizes in der oberen linken Ecke (rk, sk definiert. Es wird die Abtastreihenfolge aus 4 verwendet, wobei MB = M/2J und NB = N/2J die Größe jedes Blocks steuert. Der Parameter J sollte so gewählt werden, dass der Block 0 genau sämtliche Wavelet-Koeffizienten mit der gröbsten Auflösung enthält, z.B. sämtliche Skalierfunktionskoeffizienten. Daher sollte J genauso groß sein wie die Anzahl der Auflösungsebenen (die Baumtiefe), die bei der Wavelet-Transformierung verwendet werden. Aus 4 lässt sich mühelos die Reihenfolge aller Indizes aus der oberen linken Ecke (rk, sk) ableiten.
  • Aus 4 wird klar, dass es zum Decodieren eines kompletten Satzes von Koeffizienten mit einer gewünschten Auflösung wünschenswert ist, sämtliche Blöcke von dem Index 0 bis zu Kmax– 1 zu verwenden, wobei Kmax eine Potenz von 4 ist. Daher wird in Schritt 1 des PWC-Decodierers lmax–1 so gewählt, dass Kmax eine Potenz von 4 ist.
  • Der Grund für das abwechselnde Abtasten der Tief-Hoch-(LH)-und der Hoch-Tief-(HL)-Wavelet-Koeffizienten innerhalb derselben Auflösungsebene ist einfach. Wenn man davon ausgeht, dass ein Originalbild ein bestimmtes Merkmal (oder kein Merkmal) an einer bestimmten räumlichen Stelle hat, so ist es wahrscheinlich, dass Cluster sowohl der LH- als auch der HL-Teilbänder, die jener Stelle entsprechen, große (oder kleine) Werte aufweisen. Indem sichergestellt wird, dass Blockpaare von LH- und HL-Teilbändern, die derselben räumlichen Stelle entsprechen, aneinander angrenzend in einem Makroblock oder zumindest in der Nähe oder dicht beieinander erscheinen, können wir daher mit größerer Wahrscheinlichkeit Cluster aus großen und kleinen Werten erzeugen. Dadurch erhöht sich die Wahrscheinlichkeit langer Lauflängen von Nullen in den Bitplanes der quantisierten Koeffizienten.
  • Ein Ablaufdiagramm in 7 beschreibt einen Algorithmus, der zum Schreiben der Koeffizientenblöcke in der in 4 dargestellten Reihenfolge verwendet wird. Der Algorithmus kann je nach Wunsch in Form von Computerprogrammbefehlen oder als Hardware, Firmware oder als eine Kombination aus all diesen implementiert werden. Der Algorithmus wird am Startblock 710 eingegeben. Bei 715 wird eine Eingabematrix Q, die M × N quantisierte Wavelet-Koeffizienten enthält, gelesen. Die Koeffizienten entsprechen jenen, die von dem Quantisierungsblock 220 bereitgestellt werden. Bei 720 wird eine Anzahl von Wavelet-Ebenen in bekannter Weise als JW definiert. Am Block 725 wird eine Blockgröße als NH × NV definiert, wobei NH genauso groß ist wie M/(2JW) und NV genauso groß ist wie N/(2JW). Der erste Ausgabeblock wird dann bei 730 geschrieben und IH und IV werden als NH und NV initialisiert, um beim Definieren von Schleifen zum Schreiben weiterer Blöcke, die größer sind, verwendet zu werden. Für ein vereinfachtes Beispiel wird angenommen, dass in 4 die Matrix Q 16 × 16 beträgt, vier Ebenen hat und eine Blockgröße von 1. Dadurch entsteht ein Anfangswert IH und IV von 1. Bei anderen Beispielen ist die Blockgröße größer, z.B. 8 × 8 oder 16 × 16 oder noch höher.
  • Mit einem Entscheidungsblock 740 wird ermittelt, ob die gesamte Matrix aus Koeffizienten geschrieben worden ist, indem überprüft wird, ob IH kleiner ist als M. Wenn IH immer noch kleiner ist als M, müssen mehr Koeffizienten geschrieben werden. Wie in 4 abgebildet, haben die ersten Koeffizientenblöcke die Abmessung 1 × 1, die sich dann auf 2 × 2 und 4 × 4 und so weiter vergrößern. Die nächsten Sätze von Ablaufdiagrammblöcken werden zum Schreiben der nachfolgenden Blöcke verwendet, indem ein Schleifendurchlauf von eins zu einem Blockgrößenparameter NBLK ausgeführt wird, der am Block 745 als IH/NH eingestellt wird. Bei 750 wird mithilfe von l eine verschachtelte Programmschleife definiert, und bei 755 mit J, um bei 760 die Schreibreihenfolge der Ausgabeblöcke LH und HL zu steuern. Bei der Anweisung 762 ,Nächstes J' wird J inkrementiert, während bei der Anweisung „Nächstes l" 764 l inkrementiert wird. Dadurch entstehen Reihen von Blöcken, die bei dieser speziellen Implementierung zuerst geschrieben wer den. Falls gewünscht, können auch Spalten zuerst geschrieben werden oder andere Reihenfolgen zum Schreiben verwendet werden. Zum ersten Mal in dieser Programmschleife, bei einer Matrix mit der Größe 16 mal 16 und vier Ebenen, ist NBLK ebenfalls 1, so dass lediglich die Blöcke 430 und 440 geschrieben werden.
  • Nach dem Schreiben der nächsten LH- und HL-Blöcke wird ein zweiter Satz von verschachtelten Programmschleifen bei 770 und 775 eingerichtet, wobei erneut bei 780 l und J verwendet werden, um Positionen zu definieren, an denen ein Ausgabeblock geschrieben wird. Dieser Ausgabeblock entspricht den Blöcken HH auf derselben Ebene, was beim ersten Durchlauf Block 450 entsprach. Mit den Arbeitsanweisungen NÄCHSTES J und NÄCHSTES l wird die verschachtelte Programmschleife bei 782 bzw. 784 abgeschlossen. Es sollte erwähnt werden, dass der HH-Block ebenfalls zum gleichen Zeitpunkt wie die obigen LH- und HL-Blöcke hätte geschrieben werden können, da die verschachtelten Programmschleifen identisch sind. Nachdem sämtliche Blöcke auf dieser Ebene geschrieben worden sind, werden IH und IV bei 790 als Exponenten von 2 inkrementiert und anschließend bei 740 verglichen, um festzustellen, ob IH immer noch kleiner als M ist. Wenn IH nicht kleiner als M ist, wird der Algorithmus bei 795 verlassen, nachdem erfindungsgemäß ein vollständig neu geordneter Satz von Wavelet-Koeffizienten erzeugt worden ist.
  • Beim zweiten Durchlauf durch die verschachtelten Programmschleifen werden die Blöcke 455, 460 und 470 geschrieben, gefolgt von den Blöcken 480, 475 und 490 beim dritten Durchlauf durch die verschachtelten Programmschleifen. Größere Matrixgrößen mit höheren Ebenen sind ebenfalls angedacht.
  • Zum Wiederherstellen der ursprünglichen Reihenfolge zum Zwecke der Decodierung kann man einfach das Ergebnis des Neuordnungs-Algorithmus in derselben Weise lesen, in der er geschrieben wurde. Alles, was benötigt wird, ist die Größe der Originalmatrix und die Anzahl der Ebenen, die geschrieben wurden. Danach wird die Schreibreihenfolge einfach umgekehrt, so dass die Koeffizienten in der ursprünglichen Reihenfolge entstehen. Eine direkte Abbildung wäre ebenfalls möglich, dazu müsste allerdings eine erhebliche zusätzliche Bandbreite geschaffen werden.
  • Details der Bitplane-Codierung
  • Der von dem Codierblock 240 ausgeführte Prozess kann mithilfe des Diagramms aus Tabelle 1 mühelos verstanden werden. Die Bitplanes sind einfach die Sequenzen von Bits eines speziellen Index in der binären Darstellung (Größe plus Vorzeichen) der eingehenden quantisierten Wavelet-Koeffizienten oder anderer Daten. So zeigt beispiels weise Tabelle 1 die Bitplanes für die Sequenzen der Werte {9, –6, 1, 0, –2, 3, –4, –1, 2}. In der Tabelle ist die Bitplane 4 die Sequenz {100000000}, die Bitplane 3 ist die Sequenz {010000100}, die Bitplane 2 ist die Sequenz {010011001} und die Bitplane 1 ist die Sequenz {101001010}.
  • Tabelle 1 – Bitplane-Zerlegung von ganzzahligen Daten
    Figure 00170001
  • Bei den Eingangsdaten in Tabelle 1 scheinen die Werte geringerer Größenordnung häufiger aufzutreten, was ebenfalls typisch für quantisierte Wavelet-Daten und für Daten eines finiten Alphabets ist. Man kann aus den obigen Mustern ableiten, dass die höheren Bitplanes tendenziell eine größere Häufigkeit von Nullen zeigen, da die Eingangswerte größerer Größenordnung weniger wahrscheinlich sind. Bei der Bitplane 1 (das niedrigstwertige Bit) und bei der Vorzeichen-Bitplane treten Nullen und Einsen im typischen Fall annähernd gleichwertig auf.
  • Das Ablaufdiagramm aus 5 beschreibt den Algorithmus zum effizienten Codieren der Eingangsdaten auf den Bitplanes, beginnend bei 505. Zuerst werden bei 510 die Bitplanes aus einem Eingabepuffer x ausgelesen. Bei 515 wird die Anzahl von Bitplanes bmax berechnet, und bei 520 wird bei allen Nullen ein Signifikanz-Flag-Vektor sflg gesetzt.
  • Bei 525 wird das variable Bit für den Bitplane-Index auf bmax eingestellt, so dass die Codierung mit der signifikantesten Bitplane beginnt. Die Werte der Bits, auf die von dem Index-„Bit" gezeigt wird, bilden bei 530 den Bitplanesvektor bp. Für jeden Ebenen-pb werden die Bits in zwei Teilsätze unterteilt, wie an den Blöcken 535 und 640 angegeben. x1 entspricht Positionen, für die ein Eintrag „1" in den höheren Ebenen noch nicht erfolgte – jene werden als signifikante Bits bezeichnet. x2 entspricht Positionen, für die eine „1" bereits auf höheren Ebenen vorkam – jene werden Verfeinerungs-Bits genannt.
  • Am Block 545 wird x1 mit dem Golomb-Rice-Codierer mit adaptiver Lauflänge (ARLGR) codiert, der die höhere Häufigkeit von Nullen in x1 nutzt. Für jedes Bit, das in x1 gleich 1 ist, wird das Vorzeichen-Bit ebenfalls codiert und an das Ende des ausgegebenen Codes angehängt.
  • Am Block 550 wird x2 durch direkte binäre Codierung codiert. Dies erfolgt, indem die x2-Bits an den Ausgabestrom angehängt werden. Beim Codieren entstehen minimale Verluste, da gewöhnlich Nullen und Einsen gleich häufig in x2 vorkommen.
  • Es ist darauf zu achten, dass die Vorzeichen-Bits nicht als Bitplane bezeichnet werden, da sie nicht als eine Bitplane verarbeitet werden. Die Vorzeichen-Bits werden beim Codieren der x1-Vektoren jeder Bitplane verschickt. Somit kann man auch davon ausgehen, dass der Vektor x1 von dem Alphabet {0, +1, –1} abgezogen wird, d.h. Bit plus Vorzeichen.
  • Eine wichtige Eigenschaft des Ablaufdiagramms aus 5 besteht darin, dass die Informationen, an denen sich die Bits befinden, die zu x1 gehören und die Bits, die zu x2 gehören, nicht expliziert codiert zu werden brauchen. Der Vektor sflg steuert die Zuordnung von Bits zu x1, und sflg wird zuerst bei allen Nullen initialisiert und anschließend aktualisiert, nachdem jede Bitplane bei 555 codiert wird. Daher kann der Decodierer mühelos die Veränderungen an sflg nachvollziehen. Um auf der nächsten Bitplane fortzufahren, wird bei 560 das Bit dekrementiert und überprüft, ob bei 565 die letzte Ebene decodiert worden ist. Falls nicht geht die Steuerung weiter zu Block 530, wo die nächste Bitplane codiert wird. Wenn das Bit gleich null war oder eine größere Zahl, falls eine Codierung mit geringerer Auflösung gewünscht wird, wird bei 570 ein Ausgabepuffer geschrieben, der die Ausgangswerte aller x1- und x2-Codierungen enthält, und der Prozess endet bei 575.
  • Der Golomb-Rice-Codierer mit adaptiver Lauflänge (ARLGR) befindet sich dort, wo die Codiervorteile liegen. Er bildet lange Vektoren x1 mit vielen Nullen kompakter mit weniger Nullen ab. Der ARLGR-Codierer kann zum Codieren binärer Sequenzen mit oder ohne dazugehörige Vorzeichen-Bits verwendet werden, wie nachstehend abgebildet. Um die Funktionsweise des ARLGR zu verstehen, betrachte man zuerst die Grundlagen der Lauflängencodierung und der Golomb-Rice-Codierung.
  • Allgemein besteht die Grundidee der Lauflängencodierung (Run length = RL) darin, lange Strings desselben Wertes in einem Eingabedatenvektor durch einen Code zu ersetzen, der den zu wiederholenden Wert angibt und die Häufigkeit der Wiederholung der Werte. Wenn derartige sich wiederholende Strings lang genug und häufig genug vorkommen, führt die RL-Codierung zu einer erheblichen Verringerung der Bit-Anzahl, die zur Darstellung des Datenvektors erforderlich ist.
  • Die RL-Codierung kann auf die Codierung von binären Daten angewandt werden, bei der entweder 0 oder 1 wesentlich häufiger vorkommt als die jeweils andere Zahl. Ein Beispiel befindet sich in Grafikdateien, in denen beispielsweise eine digitalisierte schwarze Zeichnung auf weißem Hintergrund vorkommt. Wenn die weißen Bildelemente (Pixel) von einem Bit = 0 dargestellt werden und die schwarzen Punkte von einem Bit = 1, liegt es auf der Hand, dass die Nullen wahrscheinlich viel häufiger auftreten. Deshalb verwenden viele Standardgrafikdateiformate die RL-Codierung.
  • 1966 schlug Golomb einen einfachen Code für die Darstellung positiver Zahlen vor. Später wurde nachgewiesen, dass der Golomb-Code tatsächlich optimal ist (die erwartete Mindestlänge hat), wenn die Zahlen von einer Quelle mit einen geometrischen Wahrscheinlichkeitsverteilung abgezogen werden, d.h., wenn Prob{x = n}=abn, wobei a und b Parameter sind. Einige Jahre später leitete Rice unabhängig davon einen Teilsatz des Golomb-Codes ab, der sich sehr leicht in die Praxis umsetzen lässt. Diese Codes sind als Golomb-Rice-Codes bekannt geworden.
  • Bei der vorliegenden Erfindung werden Golomb-Rice-Codes für eine Quelle von Bits mit RL-Codes kombiniert. Der entstehende Lauflängen-Golomb-Rice-Code ist in Tabelle 2 dargestellt. Der Code wird durch einen Parameter k charakterisiert, der die zum dem Codewort 0 dazugehörige Lauflänge steuert; die maximale Lauflänge beträgt 2k.
  • Tabelle 2 – Lauflängen-Golomb-Rice-Codierung einer Quelle, die Symbole ∈ {0, 1} generiert
    Figure 00190001
  • Zum Codieren des x1-Vektors in dem zuvor beschriebenen Bitplane-Codierer müssen wir das Vorzeichen an das Codewort jedes Bits anhängen, das ungleich null ist. Dazu wird eine einfache Erweiterung des RLGR-Codes verwendet, wie in Tabelle 3 abgebildet.
  • Tabelle 3 – Lauflängen-Golomb-Rice-Codierung einer Quelle, die Symbole ∈ {0, +1, –1} generiert
    Figure 00200001
  • Für eine bestimmte Quelle von Eingabevektoren unter Verwendung entweder des Alphabets {0, 1} oder {0, +1, –1} sollte der Parameter k so gewählt werden, dass die erwartet Codelänge minimiert wird. Wenn die Quelle keinen Speicher hat, im Verlauf der Zeit konstante statistische Werte aufweist und durch P0 = Prob{symbol = 0} gekennzeichnet ist, dann ist es leicht, den optimalen Wert von k als Funktion von P0 zu berechnen.
  • In der Praxis sind jedoch binäre Vektoren (oder binäre Vektoren plus Vorzeichenvektoren) nicht unveränderlich. Typische Beispiele dafür sind Daten aus der physikalischen Welt, z.B. quantisierte Wavelet-Koeffizienten von Bildern oder gescannten Dokumenten.
  • Daher besteht eine Notwendigkeit, den RLGR-Parametre k im Laufe der Zeit anzupassen, um den lokalen statistischen Werten der Daten am besten zu entsprechen. Dazu wurden viele Strategien ins Auge gefasst, die meisten davon schlossen das Unterteilen von Eingabedaten in Blöcke geeigneter Länge ein. Anschließend wird für jeden Block p0 geschätzt, und wird der optimale Wert von k berechnet. Ein zusätzlicher Code wird anschließend am Anfang jedes Blocks gesendet, um den Wert k anzuzeigen, der von dem Decodierer benutzt werden sollte.
  • Bei dem Codierter 240 wird ein neuer Ansatz verfolgt. Zur Veränderung des RLGR-Parameters k wird eine rückwärts adaptive Strategie angewendet. Unter rückwärts adaptiv ist zu verstehen, dass die Änderungen an k auf der Grundlage codierter Symbole berechnet werden und nicht direkt an den Eingabedaten. Die grundlegende Strategie besteht darin, dass der beim Codieren des nächsten Symbols verwendete Wert k nur von den zuvor codierten Daten abhängen sollte. Vorher ist alles, was der Decodierer zum Wiederherstellen der veränderten Werte von k tun sollte, dieselbe Anpassungsregel wie der Codierer anzuwenden. Zum Vereinfachen der Decodierung ist es deshalb wichtig, dass eine solche Regel zum Berechnen so einfach wie möglich ist.
  • Der neue adaptive Lauflängen-Golomb-Rice-Codierer (ARLGR) 240 wendet die folgenden Regeln zum Ändern des Parameters k an. Zuerst werden bei Block 604 mehrere Parameter definiert. Als Erstes wird ein Skalierungsfaktor L definiert und zum Definieren von kp als L*k verwendet. kp ist ein Hilfsparameter, dessen Wert sich um einen Betrag Up bzw. Dn nach oben bzw. unten bewegt und somit Teilbewegungen von k ohne Verwendung der Gleitpunktarithmetik ermöglicht. Schließlich wird Uq definiert und dazu verwendet, kp nach oben zu bewegen, wenn der Ausgabecode null ist und k null entsprach. Bei 606 wird ein Eingabepuffer x gelesen, der M Zahlen enthält. Bei 608 wird k auf k0 gesetzt, kp wird auf L*k gesetzt und der Lauf auf 0. Der Prozess wird mit einem Wert k in Gang gesetzt, der sich für Langzeitstatistiken eingehender Daten eignet, z.B. k = 2. Beginnend mit dem ersten Symbol, xindex = 1, wird das Symbol auf x (xindex) gesetzt und der maximale Lauf auf 2k.
  • Im Überblick wird im Codierprozess kp nach dem Codieren eines Quellensymbols auf Basis des ausgegebenen Ausgabecodes angepasst. Wenn der Ausgabecode 0 betrug und k ≠ 0 ist, dann wird kp um einen vorgegebenen Inkrementierungsschritt Up inkrementiert, d.h. es wird kp = kp + Up eingestellt. Wenn der Ausgabecode 0 betrug und k = 0, wird kp um einen vorgegebenen Inkrementierungsschritt Uq inkrementiert, d.h. kp = kp + Uq wird eingestellt. Wenn der Ausgabecode mit einer 1 begann (entspricht einer Eingabe ≠0) wird kp um einen vorgegebenen Dekrementierungsschritt Dn dekre mentiert, d.h. kp = kp – Dn wird eingestellt. Der Wert k zum Codieren des nächsten Eingabesymbols wird auf k = kp / L gesetzt (d.h. kp / L wird auf die nächste Ganzzahl abgestrichen).
  • Der Algorithmus basiert auf einer einfachen Strategie. Wenn man auf einen Lauf von Nullen trifft, wird k vergrößert, so dass längere Sequenzen von Nullen von einem einzigen Ausgabe-Bit = 0 erfasst werden können. Wenn ein Symbol ≠ 0 auftritt, wird k verkleinert, um zu lange Ausgabecodes zu vermeiden. Die Verwendung des Hilfsparameters kp und des Skalierungsfaktors L ermöglichen die Einstellung von k in Teilschritten, ohne dass die oben angeführte Gleitpunktarithmetik zur Anwendung kommen muss.
  • Bei den meisten Daten, die in dem ARLGR-Codierer getestet wurden, war die Leistung recht gut (die codierten Raten sehr nahe an Quellen-Entropien) bei den folgenden typisch ausgewählten Parametern: L = 4, Up = 4, Dn = 5 und Uq = 2. In einigen Fällen können Anpassungen dieser Parameter zu leicht verbesserten Ergebnissen führen.
  • Kehrt man zu der Beschreibung des Ablaufdiagramms aus 6 zurück, so wird nach der Initialisierung und der Definierung der Parameter, wie oben anhand der Blöcke 602, 604, 606, 608, 610 und 612 beschrieben, zuerst in Schritt 614 zuerst k überprüft, um festzustellen, ob k gleich null ist. Falls dies der Fall ist und das Symbol null ist, wird Uq in Schritt 618 zu kp hinzugefügt. Bei 620 wird eine Null an den Ausgabepuffer angehängt, und wenn kp in Schritt 622 außerhalb des Wertebereiches liegt – oberhalb von kpmax – wird es abgeschnitten. Bei 624 wird k auf die größte Ganzzahl eingestellt, die kleiner ist als kp/L, den Skalierungsfaktor. Anschließend wird xindex inkrementiert und wenn der Wert kleiner ist als M, wie in 628 ermittelt, wird bei 612 das nächste Symbol ausgewählt. Wenn der Wert größer ist als M, wird der Ausgabe-Bit-Puffer bei 630 dazugeschrieben und der Prozess endet bei 640.
  • Wenn bei erneuter Betrachtung des Entscheidungsblocks 616 das Symbol nicht gleich null war, wird bei 642 eine 1 an den Ausgabe-Bit-Puffer angehängt, und bei 644 wird ein Vorzeichen-Bit des Symbols an den Ausgabe-Bit-Puffer angehängt, wenn die Daten ein Vorzeichen-Bit haben, und die Verarbeitung geht weiter bei 622, wo überprüft wird, ob kp innerhalb des zulässigen Bereichs liegt.
  • Wenn k bei Block 614 ≠ 1 ist, wird bei 650 eine weitere Überprüfung des Symbols ausgeführt. Wenn das Symbol ≠ null ist, wird bei 652 eine 1 an den Ausgabe-Bit-Puffer angehängt und bei 654 wird ein k-Bit-Wert des Laufes an den Ausgabe-Bit-Puffer angehängt. Bei 656 wird Dn von kp subtrahiert, und die Verarbeitung geht weiter bei 644, wo ein optionales Zeichenbit angehängt wird.
  • Wird bei 650 festgestellt, dass das Symbol nun ist, wird die lauflänge bei 622 überprüft, um festzustellen, ob sie genauso groß wie runmax ist. Falls nicht, wird kp abgeschnitten, damit der Wert bei 622 nicht kpmax überschreitet. Wenn bei 662 der Lauf genauso lang wie runmax war, wird bei 664 eine Null an den Ausgabe-Bit-Puffer angehängt, und bei 666 wird der Lauf auf null gesetzt. Schließlich wird Up zu kp addiert und die Verarbeitung kehrt zurück zu Block 622 zwecks Abschneiden von kp, zu 624 zwecks Einstellen von k, zu 626 zwecks Inkrementieren von xindex und zu 628 zwecks Überprüfung, ob das letzte Symbol verarbeitet worden ist. Wenn dies der Fall ist, wird die Information bei 630 in den Ausgabe-Bit-Puffer geschrieben, und der Prozess endet bei 640.
  • In Tabelle 4 sind die Ergebnisse der Verwendung des Bitplane-Codierers an quantisierten Wavelet-Koeffizienten abgebildet. Es wird angemerkt, dass der einfache Bitplane-Codierer besser arbeitet als adaptive arithmetische Codierer (die als der Stand der Technik betrachtet werden), obwohl er rechnerisch einfacher ist.
  • Tabelle 4 – Ausgabecodelänge in Bytes für quantisierte und neu geordnete Wavelet-Koeffizienten als Eingabegrößen
    Figure 00230001
  • Ein wesentlicher Vorteil des Codierers, der nicht bei arithmetischen Codierern anzutreffen ist, ist die Skalierbarkeit. Bei der beschriebenen Bitplane-Codierung kann eine Version des Signals mit geringerer Wiedergabetreue mühelos erlangt werden, indem der Decodierprozess an einer Bitplane angehalten wird, die über der Ebene 1 liegt. Dies ermöglicht eine progressive Übertragung und Rekonstruktion der Informationen und ist ein wichtiges Merkmal bei Datenübertragungskanälen, wie beispielsweise dem Internet. Eine andere Anwendungsmöglichkeit der Skalierbarkeit liegt beispielsweise bei den Digitalkameras. Wenn der Benutzer mehr Bilder aufnehmen möchte und bereit ist, Einbußen bei der Qualität der bereits gespeicherten Bilder hinzunehmen, können untere Bitplanes vorhandener Bilder entfernt werden, um Speicherplatz für neue Bilder freizumachen.
  • Wenngleich der ARLGR-Codierer hier im Zusammenhang mit seiner Verwendung bei einem Bitplane-Codierer beschrieben wird, ist er auch recht nützlich als universeller Codierer für binäre Daten, bei denen der Wert 0 sehr viel wahrscheinlicher ist als der Wert
  • 1. Dies trifft besonders auf Fälle zu, bei denen sich die Wahrscheinlichkeitsverteilung konstant ändert. Zum Beispiel betrachte man das Problem der Codierung einer Schwarz-Weiß-Zeichnung, die mit einer Auflösung von 480 × 640 Pixel gescannt wird. Wenn man annimmt, dass die Abbildung von weiß = 0 und schwarz = 1 erfolgt, dann kann der ARLGR-Codierer direkt auf die Daten angewendet werden. Allerdings bewältigt der Codierer 240 Läufe von Einsen nicht sehr gut, weshalb zuerst ein Differenzenoperator quer über sämtliche Pixelreihen zum Einsatz kommt. Beginnend mit der zweiten Reihe und weiter auf dem Weg nach unten wird jeder Pixelwert durch 0 ersetzt, wenn er dieselbe Farbe wie das Pixel in der darüber befindlichen Reihe hat, oder auf 1, wenn er eine andere Farbe hat. Dies wird auch über die Spalten hinweg wiederholt. Die entstehenden Bits werden mit dem ARLGR-Codierer 240 codiert.
  • Dadurch wird eine Abbildung von Läufen von entweder weiß oder schwarz in Läufen von Nullen möglich, ohne dass irgendein Informationsverlust entsteht. Folglich werden die Daten besser geeignet für die ARLGR-Codierer. Tabelle 5 zeigt einen Vergleich der Leistung eines solchen einfachen Codierers mit anderen.
  • Tabelle 5 – Ausgabecodelänge in Bytes für die Codierung von typischen Schwarz-Weiß-Bilddaten
    Figure 00240001
  • Der Algorithmus des ARLGR-Codierers 240 ist dem Algorithmus der standardmäßigen Fax-Codierung um einen Faktor von fast 2 überlegen. Er verwendet lediglich 55 % der Bytes, die von dem Fax-Algorithmus verwendet werden. Der neue Codierer auf ARLGR-Basis übertraf den adaptiven arithmetischen Codierer nach dem Stand der Technik sogar noch geringfügig bei diesem speziellen Bild. Weiterhin war er rechnerisch am wenigsten komplex. Es sollte angemerkt sein, dass dies lediglich ein Beispiel ist, und dass die Ergebnisse in Abhängigkeit von dem verwendeten Bild und von der Einstellung der Parameter variieren können.
  • In 8 ist ein Blockdiagramm eine Büro-Programmfamilie allgemein bei 810 abgebildet. Eine spezielle Büroprogrammfamilie umfasst eine Vielzahl höherer Anwendungen, angegeben mit 812, einschließlich solcher Anwendungen wie Textverarbeitung, E-Mail, Tabellenkalkulation, Präsentationstools, Fotobearbeitungsprogramme und Browser. Unterstützt werden diese Anwendungen wenigstens von zwei niederen Softwarefunktionen, Hardwarefunktionen oder von einer Kombination dieser Funktionen bei Schritt 826 und 818. Zu den abgebildeten Funktionen gehört eine Video-Eingabe-Ausgabefunktion 826 und eine Fax/Scanner-Funktion 818. Auf dieser Ebene können sich noch viele andere Funktionen befinden.
  • Insbesondere bietet die Video-Funktion die Möglichkeit, sowohl Videodaten anzuzeigen also auch Video- und Bilddaten von externen Quellen zu empfangen. Die Video- und Fax/Scanner-Funktionen bringen den hier beschriebenen Codierer und Decodierer zur Anwendung, gekennzeichnet durch Block 832, um die zuvor beschriebenen Codier- und Decodierfunktionen zu erfüllen. Wenn ein Rohbild oder andere geeignete Daten als Pixel oder in anderer Form erfasst werden, werden sie mithilfe des Codierers 832 codiert. Wenn codierte Daten von einer Quelle empfangen werden, die die hier beschriebene Art von Codierung anwendet, wird der Decodierer weiterhin bei 832 von der Anwendung aufgerufen, die die Daten empfangen hat, um sie in ein anzeigbares oder verwendbares Format zu transformieren bzw. zu decodieren.
  • Es sollte erwähnt werden, dass viele der Anwendungen, die ein solches integriertes Büroprogrammpaket, wie beispielsweise Microsoft Office oder die Nachfolgeprodukte umfassen, die noch mehr Anwendungen integrieren können, immer häufiger Daten zu bearbeiten haben, die komprimiert oder dekomprimiert werden müssen. Die vorliegende Erfindung bietet eine Alternative zu anderen Formen der Codierung, die die Blockierungs-Artefakte entfernt, die in JPEG vorliegen, und sie lässt sich weniger schwierig in Software, Hardware oder Hybridformen aus selbigen nach Wunsch implementieren. Der Codierer/Decodierer aus Block 832 lässt sich ebenfalls leicht in eine derartige Büroprogrammfamilie integrieren.
  • Schlussfolgerung
  • Das Neuordnung quantisierter Wavelet-Koeffizienten erfolgt, um große und kleine Wavelet-Koeffizienten in separate Gruppen zu clustern, ohne dass dazu datenabhängige Datenstrukturen erforderlich sind. Anschließend werden die Koeffizienten ausgehend von einem Lauflängencode adaptiv codiert, der fortlaufend einen Parameter ändert, der die Codewörter, die zur Darstellung von Strings quantisierter Koeffizienten verwendet werden, steuert, wobei versucht wird, die Anzahl von Bits in den Codewörtern zu minimieren. Da das Ordnungsmuster festgelegt ist und die Codierung der Koeffizienten keine modifizierte Tabelle für jedes Bild erforderlich macht, bietet sich diese Erfindung für einfacherer Hardware- oder Software-Implementierungen an. Zu weiteren Vorteilen gehören der Wegfall von blockierenden Artefakten und die Codierung mit jeder gewünschten Komprimierungsrate bei Bilddaten in einem einzigen Durchlauf.
  • Es ist ein Decodierer beschrieben worden, der die obige Codierung und Blockierung in ungekehrter Reihenfolge anwendet. Zuerst erfolgt die Decodierung der codierten Koeffizienten, gefolgt von einem Unshuffle-Vorgang an den Koeffizienten. Die derart bearbeiteten Koeffizienten werden anschließend einer umgekehrten Wavelet-Transformierung unterzogen, um die transformierten und komprimierten Daten, z.B. Bildpixel, wiederherzustellen. Das adaptive arithmetische Codieren kann ebenfalls zusammen mit der Neuordnung angewendet werden, um ähnliche Komprimierungsvorteile zu erzielen, allerdings geschieht dies mit einer etwas höheren Komplexität.
  • Da keine datenabhängigen Datenstrukturen benötigt werden, wie beispielsweise Nullbäume (Zero Trees) oder eine separate Liste für eingestellte Partitionen in Bäumen, lassen sich die Hardware-Implementierungen leichter bauen. Es ist beabsichtigt, dass diese Anwendung sämtliche Abwandlungen oder Varianten der vorliegenden Erfindung umfasst.

Claims (37)

  1. Verfahren zum Codieren von Datenzeichen eines finiten Alphabets, wobei das Verfahren umfasst: Initialisieren einer String-Länge für einen adaptiven Lauflängencodierer; Modifizieren der String-Länge auf Basis eines modifizieren Codierungsparameters (k), der erzeugt wird durch: Anwenden eines Skalierungsfaktors (L) auf einen aktuellen Codierparameter, Regulieren des Wertes (kp) des skalierten Codierparameters auf Basis bereits codierter Zeichen, und Anwenden eines inversen Skalierungsfaktors auf den regulierten und skalierten Codierparameter, um den modifizierten Codierparameter zu erzeugen.
  2. Verfahren nach Anspruch 1, wobei der Codierparameter immer dann vergrößert wird, wenn ein erwartetes Zeichen auftritt.
  3. Verfahren nach Anspruch 1, wobei das erwartete Zeichen Null ist.
  4. Verfahren nach Anspruch 1, wobei der Codierparameter immer dann verkleinert wird, wenn ein erwartetes Zeichen nicht auftritt.
  5. Verfahren nach Anspruch 4, wobei das erwartete Zeichen Null ist.
  6. Verfahren nach Anspruch 1, wobei die Zeichen auf einer Bitplane-Basis codiert werden.
  7. Verfahren nach Anspruch 6, wobei die niedrigstwertigen Bitplanes unter Verwendung von Binärcodierung codiert werden.
  8. Verfahren nach Anspruch 6, wobei nur die höchstwertigen Bitplanes codiert werden, um die Auflösung der Codierung zu modifizieren.
  9. Verfahren nach Anspruch 1, wobei der Vorgang des Initialisierens der String-Länge für den adaptiven Lauflängencodierer einen Vorgang des Einstellens (612) der anfänglichen String-Länge umfasst, so dass sie 2 potenziert um einen anfänglichen Codierparameter entspricht.
  10. Verfahren nach Anspruch 9, wobei der anfängliche Codierparameter 2 beträgt.
  11. Verfahren nach Anspruch 1, wobei die Datenzeichen des finiten Alphabets unter Verwendung von Binärwerten charakterisiert werden und wobei der Vorgang des Regulierens des skalierten Codierparameters auf Basis bereits codierter Zeichen nacheinander die folgenden Vorgänge (650, 652656, 660670) für jeden Binärwert umfasst: Bestimmen, ob der Wert ein erster oder ein zweiter Binärwert ist; wenn der Wert der erste Binärwert ist, Durchführen keines Vorgangs, wenn nicht die Anzahl vorangehender Pixelpositionen, für die kein Vorgang durchgeführt worden ist, einer aktuellen String-Länge entspricht, und, wenn dies der Fall ist, Einrichten eines ersten Typs Codewort durch Darstellen der Anzahl vorangehender Werte, für die kein Vorgang durchgeführt worden ist, mit einem einzelnen ersten Codierwert; wenn der Wert der zweite Binärwert ist, Einrichten eines zweiten Typs Codewort durch Darstellen des Wertes unter Berücksichtigung und der Anzahl vorangehender Werte, für die kein Vorgang durchgeführt worden ist, mit einem zweiten Codierwert und einem Binärwort, das die Anzahl vorangehender Werte anzeigt, für die kein Vorgang durchgeführt worden ist; und wenn ein Codewort eingerichtet wird, Vergrößern des aktuellen Codierparameters um einen ersten vorgeschriebenen Betrag, wenn das Codewort von dem ersten Typ ist, und Verkleinern des aktuellen Codierparameters um einen zweiten vorgeschriebenen Betrag, wenn das Codewort von dem zweiten Typ ist.
  12. Verfahren nach Anspruch 1, wobei der Vorgang des Modifizierens der String-Länge auf Basis des modifizierten Codierparameters einen Vorgang (628, 612) des Änderns der aktuellen String-Länge umfasst, so dass sie 2 potenziert um den modifizierten Codierparameter entspricht.
  13. Verfahren nach Anspruch 11, wobei der Vorgang des Anwendens des inversen Skalierungsfaktors auf die regulierten und skalierten Codierparameter zum Erzeugen des modifizierten Codierparameters das Dividieren des regulierten und skalierten Codierparameters kp durch den Skalierungsfaktor L und das Einstellen (624) des modifizierten Codierparameters k auf den größten ganzzahligen Wert kleiner als kp/L umfasst.
  14. Verfahren nach Anspruch 1, das des Weiteren umfasst (650, 652656, 660670): nacheinander für jeden Binärwert: Bestimmen, ob der Wert ein erster oder ein zweiter Binärwert ist; wenn der Wert der erste Binärwert ist, Durchführen keines Vorgangs, wenn nicht die Anzahl vorangehender Pixelpositionen, für die kein Vorgang durchgeführt worden ist, einer aktuellen String-Länge entspricht, und, wenn dies der Fall ist, Einrichten eines ersten Typs Codewort durch Darstellen der Anzahl vorangehender Werte, für die kein Vorgang durchgeführt worden ist, mit einem einzelnen ersten Codierwert; und wenn der Wert der zweite Binärwert ist, Einrichten eines zweiten Typs Codewort durch Darstellen des Wertes unter Berücksichtigung und der Anzahl vorangehender Werte, für die kein Vorgang durchgeführt worden ist, mit einem zweiten Codierwert, und einem Binärwort, das die Anzahl vorangehender Werte anzeigt, für die kein Vorgang durchgeführt worden ist; wobei der Schritt des Modifizierens der String-Länge immer dann durchgeführt wird, wenn ein Codewort eingerichtet ist.
  15. Verfahren nach Anspruch 14, wobei der Vorgang des Modifizierens der String-Länge auf Basis des modifizierten Codierparameters einen Vorgang (628, 612) des Änderns der aktuellen Strng-Länge umfasst, so dass sie 2 potenziert um den modifizierten Codierparameter entspricht.
  16. Verfahren nach Anspruch 14, wobei der Vorgang des Regulierens des Wertes des skalierten Codierparameters auf Basis bereits codierter Werte einen Vorgang des Vergrößerns des aktuellen Codierparameters um einen vorgeschriebenen ersten Betrag, wenn das zuletzt generierte Codewort von dem ersten Typ ist, und das Verkleinern des aktuellen Codierparameters um einen zweiten vorgeschriebenen Betrag umfasst, wenn das zuletzt generierte Codewort vom zweiten Typ ist.
  17. Verfahren nach Anspruch 16, wobei der Vorgang des Anwendens des Skalierungsfaktors auf den aktuellen Codierparameter das Multiplizieren (608) des Skalierungsfaktors L mit dem aktuellen Codierparameter k umfasst, um den skalierten Codierparameter kp zu erzeugen.
  18. Verfahren nach Anspruch 17, wobei der Vorgang des Vergrößerns des aktuellen Codierparameters um einen ersten vorgeschriebenen Betrag, wenn das Codewort vom ersten Typ ist, die folgenden Vorgänge umfasst: Bestimmen (614), ob k Null entspricht; wenn k Null entspricht, Vergrößern (616, 618) von kp um ein erstes vorgeschriebenes Inkrement Uq; und wenn k nicht Null entspricht, Vergrößern (650, 660670) von kp um ein zweites vorgeschriebenes Inkrement Up.
  19. Verfahren nach Anspruch 18, wobei der Skalierungsfaktor L 4 beträgt, das erste vorgeschriebene Inkrement Uq 2 beträgt und das zweite vorgeschriebene Inkrement Up 4 beträgt.
  20. Verfahren nach Anspruch 18, wobei der Vorgang des Verkleinerns des aktuellen Codierparameters um einen zweiten vorgeschriebenen Betrag, wenn das Codewort von dem zweiten Typ ist, einen Vorgang (650656) des Verkleinerns von kp um ein vorgeschriebenes Inkrement Dn umfasst.
  21. Verfahren nach Anspruch 20, wobei der Skalierungsfaktor L 4 beträgt und das vorgeschriebene Inkrement Dn 5 beträgt.
  22. Verfahren nach Anspruch 14, wobei der Vorgang des Anwendens des inversen Skalierungsfaktors auf den regulierten und skalierten Codierparameter zum Erzeugen des modifizierten Codierparameters das Dividieren des regulierten und skalierten Codierparameters kp durch den Skalierungsfaktor L und das Einstellen (624) des modifizierten Codierparameters k auf den größten ganzzahligen Wert kleiner als kp/L umfasst.
  23. Computerlesbares Medium mit darauf gespeicherten Befehlen, die einen Computer veranlassen, das Verfahren nach einem der Ansprüche 1 bis 22 durchzuführen.
  24. Codierer zum Codieren von Daten eines finiten Alphabets, der umfasst: eine Einrichtung, die eine String-Länge für einen adaptiven Lauflängencodierer initialisiert; eine Einrichtung, die die String-Länge auf Basis eines modifizierten Codierparameters (k) modifiziert, der erzeugt wird durch: eine Einrichtung, die einen Skalierungsfaktor (L) auf einen aktuellen Codierparameter anwendet, eine Einrichtung, die den Wert (kp) des skalierten Codierparameters auf Basis bereits codierter Zeichen reguliert, und eine Einrichtung, die einen inversen Skalierungsfaktor auf den regulierten und skalierten Codierparameter anwendet, um den modifizierten Codierparameter zu erzeugen.
  25. Verfahren zum Decodieren von Datenzeichen eines finiten Alphabets, die unter Verwendung einer rückläufigen adaptiven Lauflängencodierung codiert worden sind, wobei das Verfahren umfasst: Initialisieren einer String-Länge für einen adaptiven Lauflängendecodierer; Modifizieren der String-Länge auf Basis eines modifizierten Decodierparameters, der erzeugt wird durch: Anwenden eines Skalierungsfaktors (L) auf einen aktuellen Decodierparameter (k), Regulieren des Wertes (kp) des skalierten Decodierparameters auf Basis bereits decodierter Zeichen, und Anwenden eines inversen Skalierungsfaktors auf den regulierten und skalierten Decodierfaktor, um den modifizierten Decodierparameter zu erzeugen.
  26. Verfahren nach Anspruch 25, wobei der Decodierparameter immer dann vergrößert wird, wenn ein erwartetes Zeichen auftritt.
  27. Verfahren nach Anspruch 26, wobei das erwartete Zeichen Null ist.
  28. Verfahren nach Anspruch 25, wobei der Decodierparameter immer dann verringert wird, wenn ein erwartetes Zeichen nicht auftritt.
  29. Verfahren nach Anspruch 28, wobei das erwartete Zeichen Null ist.
  30. Verfahren nach Anspruch 25, wobei die Zeichen auf einer Bitplane-Basis decodiert werden.
  31. Verfahren nach Anspruch 30, wobei die niedrigstwertigen Bitplanes unter Verwendung von Binärcodierung decodiert werden.
  32. Verfahren nach Anspruch 31, wobei nur die höchstwertigen Bitplanes decodiert werden, um die Auflösung der Codierung zu modifizieren.
  33. Verfahren nach Anspruch 25, wobei die Datenzeichen des finiten Alphabets durch eine Sequenz von Binärwerten charakterisiert werden und mit einem Prozess codiert werden, durch den die Sequenz von Binärwerten auf eine Reihe von Codeworten reduziert wird, aus denen hergeleitet werden kann, ob jeder Wert in der Sequenz den ersten Binärwert oder den zweiten Binärwert hat, wobei die Codewörter in zwei Typen vorhanden sind, von denen ein erster ein erster Codewortwert ist, der eine Anzahl von Binärwerten in einem String von Werten darstellt, die den ersten Binärwert haben, und der zweite einen zweiten Codewortwert umfasst, auf den ein Binärwort folgt, das die Anzahl von Binärwerten anzeigt, die dem Wert mit dem zweiten Binärwert vorangehen, die die ersten Binärwerte haben, wobei das Verfahren den Einsatz einer Rechenvorrichtung zum Durchführen der folgenden Prozessvorgänge umfasst: (a) Empfangen der Reihe von Codeworten; (b) Einrichten einer aktuellen String-Länge, die mit der anfänglichen Länge identisch ist, die beim Codieren der Sequenz von Binärwerten verwendet wird, wobei die String-Länge eine Anzahl aufeinanderfolgender Binärwerte darstellt, die den ersten Binärwert haben; (c) Bestimmen, ob das zuletzt empfangene Codewort von dem ersten oder dem zweiten Typ ist; (d) wenn das zuletzt empfangene Codewort von dem zweiten Typ ist, Generieren einer Anzahl von Werten, die den ersten Binärwert haben, der durch die Bi närwortkomponente des Codewortes angezeigt wird, und anschließend Generieren eines zusätzlichen Wertes, der den zweiten Binärwert hat; und (e) wenn das zuletzt empfangene Codewort von dem ersten Typ ist, Generieren einer Anzahl von Werten, die den ersten Binärwert haben, der der aktuellen String-Länge entspricht; (f) Modifizieren der aktuellen String-Länge, um eine neue aktuelle String-Länge auf Basis eines modifizierten Decodierparameters einzurichten, wobei der modifizierte Decodierparameter erzeugt wird durch: Anwenden eines Skalierungsfaktors auf einen aktuellen Decodierparameter, der anfänglich der gleiche ist wie der, der als der anfängliche Codierparameter beim Codieren verwendet wurde, Regulieren des Wertes des skalierten Decodierparameters auf Basis bereits decodierter Werte, und Anwenden eines inversen Skalierungsfaktors auf den regulierten und skalierten Decodierparameter, um den modifizierten Decodierparameter zu erzeugen; und (g) Wiederholen von Vorgang (c) bis (f) unter Verwendung der neuen aktuellen String-Länge.
  34. Verfahren nach Anspruch 33, wobei der Vorgang des Modifizierens der String-Länge auf Basis des modifizierten Decodierparameters einen Vorgang des Änderns der aktuellen String-Länge umfasst, so dass sie 2 potenziert um den modifizierten Decodierparameter entspricht.
  35. Verfahren nach Anspruch 33, wobei der Vorgang des Regulierens des Wertes des skalierten Decodierparameters auf Basis bereits decodierter Werte die folgenden Vorgänge umfasst: Vergrößern des aktuellen Decodierparameters um einen ersten vorgeschriebenen Betrag, wenn das zuletzt empfangene Codewort von dem ersten Typ ist; und Verkleinern des aktuellen Decodierparameters um einen zweiten vorgeschriebenen Betrag, wenn das zuletzt empfangene Codewort von dem zweiten Typ ist.
  36. Computerlesbares Medium mit darauf gespeicherten durch Computer ausführbaren Befehlen, die einen Computer veranlassen, das Verfahren nach einem der Ansprüche 25 bis 35 durchzuführen.
  37. Decodierer zum Decodieren von Daten eines finiten Alphabets, der umfasst: eine Einrichtung, die eine String-Länge zum Decodieren von Daten initialisiert, die adaptiver Lauflängencodierung unterzogen wurden; eine Einrichtung, die die String-Länge auf Basis eines modifizierten Decodierparameters (k) modifiziert, der erzeugt wird durch: eine Einrichtung, die einen Skalierungsfaktor (L) auf einen aktuellen Decodierparameter anwendet, eine Einrichtung, die den Wert (kp) des skalierten Decodierparameters auf Basis bereits decodierter Zeichen reguliert, und eine Einrichtung, die einen inversen Skalierungsfaktor auf den regulierten und skalierten Decodierparameter anwendet, um den modifizierten Decodierparameter zu erzeugen.
DE60015755T 1999-03-26 2000-03-24 Verlustfreie adaptive codierung von daten eines endlichen alphabets Expired - Lifetime DE60015755T2 (de)

Applications Claiming Priority (7)

Application Number Priority Date Filing Date Title
US09/276,954 US6850649B1 (en) 1999-03-26 1999-03-26 Image encoding using reordering and blocking of wavelet coefficients combined with adaptive encoding
US276954 1999-03-26
US09/277,255 US6477280B1 (en) 1999-03-26 1999-03-26 Lossless adaptive encoding of finite alphabet data
US280135 1999-03-26
US277255 1999-03-26
US09/280,135 US6678419B1 (en) 1999-03-26 1999-03-26 Reordering wavelet coefficients for improved encoding
PCT/US2000/007955 WO2000059116A1 (en) 1999-03-26 2000-03-24 Lossless adaptive encoding of finite alphabet data

Publications (2)

Publication Number Publication Date
DE60015755D1 DE60015755D1 (de) 2004-12-16
DE60015755T2 true DE60015755T2 (de) 2005-04-07

Family

ID=27402856

Family Applications (2)

Application Number Title Priority Date Filing Date
DE2000612717 Expired - Lifetime DE60012717T2 (de) 1999-03-26 2000-03-24 Bildcodierung unter verwendung einer umordnung von wavelet-koeffizienten
DE60015755T Expired - Lifetime DE60015755T2 (de) 1999-03-26 2000-03-24 Verlustfreie adaptive codierung von daten eines endlichen alphabets

Family Applications Before (1)

Application Number Title Priority Date Filing Date
DE2000612717 Expired - Lifetime DE60012717T2 (de) 1999-03-26 2000-03-24 Bildcodierung unter verwendung einer umordnung von wavelet-koeffizienten

Country Status (7)

Country Link
EP (2) EP1166565B1 (de)
JP (2) JP4540855B2 (de)
KR (1) KR100733949B1 (de)
AT (2) ATE272925T1 (de)
AU (3) AU3922200A (de)
DE (2) DE60012717T2 (de)
WO (3) WO2000059231A1 (de)

Families Citing this family (13)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
AU770148B2 (en) * 2000-12-06 2004-02-12 Canon Kabushiki Kaisha Digital image compression and decompression
AUPR192800A0 (en) 2000-12-06 2001-01-04 Canon Kabushiki Kaisha Digital image compression and decompression
US6798364B2 (en) 2002-02-05 2004-09-28 Intel Corporation Method and apparatus for variable length coding
US20060072834A1 (en) * 2003-04-17 2006-04-06 Lynch William C Permutation procrastination
ATE449405T1 (de) 2002-09-04 2009-12-15 Microsoft Corp Entropische kodierung mittels anpassung des kodierungsmodus zwischen niveau- und lauflängenniveau-modus
US7286945B2 (en) * 2003-11-19 2007-10-23 Honeywell International Inc. Apparatus and method for identifying possible defect indicators for a valve
US7274995B2 (en) * 2003-11-19 2007-09-25 Honeywell International Inc. Apparatus and method for identifying possible defect indicators for a valve
US7689051B2 (en) * 2004-04-15 2010-03-30 Microsoft Corporation Predictive lossless coding of images and video
KR101155525B1 (ko) * 2005-06-20 2012-06-19 삼성전자주식회사 기록/재생 장치 및 방법
WO2008070843A2 (en) * 2006-12-07 2008-06-12 Qualcomm Incorporated Line-based video rate control and compression
US8179974B2 (en) 2008-05-02 2012-05-15 Microsoft Corporation Multi-level representation of reordered transform coefficients
FR2934103B1 (fr) * 2008-07-16 2010-08-27 Sagem Securite Procede et systeme de transmission securisee d'une image entre deux points distants
CN108028928B (zh) * 2015-09-18 2021-02-19 皇家飞利浦有限公司 用于快速和高效的图像压缩和解压缩的方法和装置

Family Cites Families (9)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5321776A (en) * 1992-02-26 1994-06-14 General Electric Company Data compression system including successive approximation quantizer
US5717394A (en) * 1993-02-10 1998-02-10 Ricoh Company Ltd. Method and apparatus for encoding and decoding data
US5381145A (en) * 1993-02-10 1995-01-10 Ricoh Corporation Method and apparatus for parallel decoding and encoding of data
JP3943634B2 (ja) * 1995-11-02 2007-07-11 キヤノン株式会社 情報処理装置及び方法
US5818877A (en) * 1996-03-14 1998-10-06 The Regents Of The University Of California Method for reducing storage requirements for grouped data values
IL119523A0 (en) * 1996-10-30 1997-01-10 Algotec Systems Ltd Data distribution system
JP3213582B2 (ja) * 1997-05-29 2001-10-02 シャープ株式会社 画像符号化装置及び画像復号装置
JP2002501532A (ja) * 1997-05-30 2002-01-15 メルク エンド カンパニー インコーポレーテッド 新規血管形成阻害薬
EP0940994B1 (de) * 1998-03-06 2014-04-16 Canon Kabushiki Kaisha Bildverarbeitungsvorrichtung und -verfahren, und Speichermedium mit gespeicherten Schritten für ein solches Verfahren

Also Published As

Publication number Publication date
EP1188244B1 (de) 2004-11-10
WO2000059232A1 (en) 2000-10-05
JP4426118B2 (ja) 2010-03-03
EP1166565B1 (de) 2004-08-04
EP1166565A1 (de) 2002-01-02
WO2000059116A1 (en) 2000-10-05
ATE282260T1 (de) 2004-11-15
DE60012717T2 (de) 2005-01-13
AU3916900A (en) 2000-10-16
AU3922200A (en) 2000-10-16
KR20020008133A (ko) 2002-01-29
KR100733949B1 (ko) 2007-07-02
JP4540855B2 (ja) 2010-09-08
EP1188244A1 (de) 2002-03-20
DE60012717D1 (de) 2004-09-09
ATE272925T1 (de) 2004-08-15
AU3772300A (en) 2000-10-16
JP2002540711A (ja) 2002-11-26
JP2002540740A (ja) 2002-11-26
DE60015755D1 (de) 2004-12-16
WO2000059231A1 (en) 2000-10-05

Similar Documents

Publication Publication Date Title
DE19626615C2 (de) Verfahren und Apparat zur Kompression, das bzw. der reversible Wavelet-Transformationen und einen eingebetteten Kodestrom verwendet
DE19626600C2 (de) Kodierer und Verfahren zum Kodieren
DE69510662T2 (de) Kompakte Quellencodierungstabellen für Codierungs-/Decodierungssystem
DE69722601T2 (de) Datenkompression mit hybrider verlustloser entropiekodierung von run-length codes
DE19861377B4 (de) Ein verbessertes Kompressions- und Dekompressionssystem mit reversiblen Wavelets und verlustbehafteter Rekonstruktion
DE69421690T2 (de) Geraet und verfahren zur datenkompression
DE19506164C2 (de) Verfahren zum Komprimieren eingegebener Symbole in Codeworte
EP1487113B1 (de) Kodierung und Dekodierung von Transformationskoeffizienten in Bild- oder Videokodierern
DE69736329T2 (de) Verschachtelte verteilte kodierung von spärlich bestückten datensätzen
DE19534943B4 (de) Vorrichtung zur Komprimierung unter Verwendung von eingebetteten Kleinwellen
DE69622501T2 (de) Bildverarbeitungsvorrichtung und -verfahren
DE69806729T2 (de) Progressive blockbasierte kodierung für bildkompression
DE69116869T2 (de) Digitale bildkodierung mit einer zufallsabtastung der bilder
DE69511390T2 (de) Quellencodierer mit voreingestellter qualität
DE19534730B4 (de) Verfahren zum Codieren und Decodieren von Daten
DE69413759T2 (de) ADCT-Kompression mit minimalem Kompressionsgrad
DE60015755T2 (de) Verlustfreie adaptive codierung von daten eines endlichen alphabets
DE19819198A1 (de) Reversible DCT für verlustfreie/verlustbehaftete Kompression
DE69722495T2 (de) Adaptives Abtastverfahren für Wavelet-Videokodierung
DE102007020292A1 (de) Verfahren zur Komprimierung von Daten unter Verwendung einer Lauflängen-Kodierung insbesondere für medizinische Bilddaten
DE112012005164T5 (de) Verfahren und Vorrichtung für Context-Adaptive Binäre Arithmetische Codierung von Syntaxelementen
EP1571755A2 (de) Verfahren und Anordnung zur arithmetischen Enkodierung und Dekodierung mit Initialisierung eines Wahrscheinlichkeitsmodelles
DE112008003626T5 (de) Kodierung mit geringer Komplexität in Datenkomprimierungssystemen
EP1472888B1 (de) Kontextsensitive kodierung und dekodierung eines videodatenstroms
EP3624456A1 (de) Verfahren zur kompression und dekompression von bilddaten

Legal Events

Date Code Title Description
8364 No opposition during term of opposition