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

DE19534730B4 - Verfahren zum Codieren und Decodieren von Daten - Google Patents

Verfahren zum Codieren und Decodieren von Daten Download PDF

Info

Publication number
DE19534730B4
DE19534730B4 DE19534730A DE19534730A DE19534730B4 DE 19534730 B4 DE19534730 B4 DE 19534730B4 DE 19534730 A DE19534730 A DE 19534730A DE 19534730 A DE19534730 A DE 19534730A DE 19534730 B4 DE19534730 B4 DE 19534730B4
Authority
DE
Germany
Prior art keywords
coefficients
data
bit
coefficient
block
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 - Fee Related
Application number
DE19534730A
Other languages
English (en)
Other versions
DE19534730A1 (de
Inventor
Ahmad Menlo Park Zandi
James D. Menlo Park Allen
Edward L. Menlo Park Schwartz
Martin Menlo Park Boliek
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.)
Ricoh Co Ltd
Original Assignee
Ricoh Co Ltd
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
Family has litigation
First worldwide family litigation filed litigation Critical https://patents.darts-ip.com/?family=23201171&utm_source=google_patent&utm_medium=platform_link&utm_campaign=public_patent_search&patent=DE19534730(B4) "Global patent litigation dataset” by Darts-ip is licensed under a Creative Commons Attribution 4.0 International License.
Application filed by Ricoh Co Ltd filed Critical Ricoh Co Ltd
Publication of DE19534730A1 publication Critical patent/DE19534730A1/de
Application granted granted Critical
Publication of DE19534730B4 publication Critical patent/DE19534730B4/de
Anticipated expiration legal-status Critical
Expired - Fee Related legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/10—Complex mathematical operations
    • G06F17/14—Fourier, Walsh or analogous domain transformations, e.g. Laplace, Hilbert, Karhunen-Loeve, transforms
    • G06F17/148—Wavelet transforms
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M7/00—Conversion 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/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/10—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding
    • H04N19/102—Methods 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/129—Scanning of coding units, e.g. zig-zag scan of transform coefficients or flexible macroblock ordering [FMO]
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/10—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding
    • H04N19/134—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding characterised by the element, parameter or criterion affecting or controlling the adaptive coding
    • H04N19/162—User input
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/10—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding
    • H04N19/134—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding characterised by the element, parameter or criterion affecting or controlling the adaptive coding
    • H04N19/167—Position within a video image, e.g. region of interest [ROI]
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/10—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding
    • H04N19/169—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding characterised by the coding unit, i.e. the structural portion or semantic portion of the video signal being the object or the subject of the adaptive coding
    • H04N19/186—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding characterised by the coding unit, i.e. the structural portion or semantic portion of the video signal being the object or the subject of the adaptive coding the unit being a colour or a chrominance component
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/30—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using hierarchical techniques, e.g. scalability
    • H04N19/36—Scalability techniques involving formatting the layers as a function of picture distortion after decoding, e.g. signal-to-noise [SNR] scalability
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/46—Embedding additional information in the video signal during the compression process
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/50—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using predictive coding
    • H04N19/593—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using predictive coding involving spatial prediction techniques
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/60—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using transform coding
    • H04N19/61—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using transform coding in combination with predictive coding
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/60—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using transform coding
    • H04N19/63—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using transform coding using sub-band based transform, e.g. wavelets
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/60—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using transform coding
    • H04N19/63—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using transform coding using sub-band based transform, e.g. wavelets
    • H04N19/635—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using transform coding using sub-band based transform, e.g. wavelets characterised by filter definition or implementation details
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/60—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using transform coding
    • H04N19/63—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using transform coding using sub-band based transform, e.g. wavelets
    • H04N19/64—Methods 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
    • H04N19/647—Methods 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 using significance based coding, e.g. Embedded Zerotrees of Wavelets [EZW] or Set Partitioning in Hierarchical Trees [SPIHT]
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/90—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using coding techniques not provided for in groups H04N19/10-H04N19/85, e.g. fractals
    • H04N19/98—Adaptive-dynamic-range coding [ADRC]
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N21/00—Selective content distribution, e.g. interactive television or video on demand [VOD]
    • H04N21/20—Servers specifically adapted for the distribution of content, e.g. VOD servers; Operations thereof
    • H04N21/23—Processing of content or additional data; Elementary server operations; Server middleware
    • H04N21/238—Interfacing the downstream path of the transmission network, e.g. adapting the transmission rate of a video stream to network bandwidth; Processing of multiplex streams
    • H04N21/2383—Channel coding or modulation of digital bit-stream, e.g. QPSK modulation
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N21/00—Selective content distribution, e.g. interactive television or video on demand [VOD]
    • H04N21/40—Client devices specifically adapted for the reception of or interaction with content, e.g. set-top-box [STB]; Operations thereof
    • H04N21/43—Processing of content or additional data, e.g. demultiplexing additional data from a digital video stream; Elementary client operations, e.g. monitoring of home network or synchronising decoder's clock; Client middleware
    • H04N21/438—Interfacing the downstream path of the transmission network originating from a server, e.g. retrieving encoded video stream packets from an IP network
    • H04N21/4382—Demodulation or channel decoding, e.g. QPSK demodulation
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N21/00—Selective content distribution, e.g. interactive television or video on demand [VOD]
    • H04N21/60—Network structure or processes for video distribution between server and client or between remote clients; Control signalling between clients, server and network components; Transmission of management data between server and client, e.g. sending from server to client commands for recording incoming content stream; Communication details between server and client 
    • H04N21/63—Control signaling related to video distribution between client, server and network components; Network processes for video distribution between server and clients or between remote clients, e.g. transmitting basic layer and enhancement layers over different transmission paths, setting up a peer-to-peer communication via Internet between remote STB's; Communication protocols; Addressing
    • H04N21/637—Control signals issued by the client directed to the server or network components
    • H04N21/6377—Control signals issued by the client directed to the server or network components directed to server
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N21/00—Selective content distribution, e.g. interactive television or video on demand [VOD]
    • H04N21/60—Network structure or processes for video distribution between server and client or between remote clients; Control signalling between clients, server and network components; Transmission of management data between server and client, e.g. sending from server to client commands for recording incoming content stream; Communication details between server and client 
    • H04N21/63—Control signaling related to video distribution between client, server and network components; Network processes for video distribution between server and clients or between remote clients, e.g. transmitting basic layer and enhancement layers over different transmission paths, setting up a peer-to-peer communication via Internet between remote STB's; Communication protocols; Addressing
    • H04N21/637—Control signals issued by the client directed to the server or network components
    • H04N21/6377—Control signals issued by the client directed to the server or network components directed to server
    • H04N21/6379—Control signals issued by the client directed to the server or network components directed to server directed to encoder, e.g. for requesting a lower encoding rate
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N21/00—Selective content distribution, e.g. interactive television or video on demand [VOD]
    • H04N21/60—Network structure or processes for video distribution between server and client or between remote clients; Control signalling between clients, server and network components; Transmission of management data between server and client, e.g. sending from server to client commands for recording incoming content stream; Communication details between server and client 
    • H04N21/65—Transmission of management data between client and server
    • H04N21/658—Transmission by the client directed to the server
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/10—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding
    • H04N19/102—Methods 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
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/10—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding
    • H04N19/102—Methods 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/115—Selection of the code volume for a coding unit prior to coding
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/10—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding
    • H04N19/102—Methods 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/13—Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/10—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding
    • H04N19/134—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding characterised by the element, parameter or criterion affecting or controlling the adaptive coding
    • H04N19/146—Data rate or code amount at the encoder output
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/42—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals characterised by implementation details or hardware specially adapted for video compression or decompression, e.g. dedicated software implementation

Landscapes

  • Engineering & Computer Science (AREA)
  • Signal Processing (AREA)
  • Multimedia (AREA)
  • Physics & Mathematics (AREA)
  • Mathematical Physics (AREA)
  • Theoretical Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Pure & Applied Mathematics (AREA)
  • Mathematical Analysis (AREA)
  • Mathematical Optimization (AREA)
  • Data Mining & Analysis (AREA)
  • Computational Mathematics (AREA)
  • Algebra (AREA)
  • General Engineering & Computer Science (AREA)
  • Software Systems (AREA)
  • Databases & Information Systems (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)
  • Image Processing (AREA)

Abstract

Verfahren zum Codieren von Eingangsdaten mit den folgenden Schritten:
a) eine überlappte, reversible Wavelet-Transformation wird auf die Eingangsdaten angewendet, um eine Reihe von Koeffizienten zu erzeugen, wobei die Transformation mittels einer Abfolge von Filteroperationen durchgeführt wird und wobei sich die Koeffizienten aus den Filteroperationen ergeben und Koeffizientengruppen Frequenzbänder darstellen, und
b) die Reihe von Koeffizienten werden in Daten komprimiert, die eine komprimierte Version der Eingangsdaten darstellen, indem die Bits der Reihe von Koeffizienten durch ein Kontextmodell verarbeitet werden, das zur Verarbeitung eines Koeffizienten sowohl bekannte Koeffizienten in anderen Frequenzbändern als des aktuell verarbeiteten Koeffizienten als auch benachbarte Koeffizienten im selben Frequenzband wie des aktuell verarbeiteten Koeffizienten verwendet.

Description

  • Die Erfindung betrifft Verfahren zum Codieren und Decodieren von Daten und betrifft darüber hinaus das Gebiet von Daten-Kompressions- und Dekompressionssystemen. Insbesondere betrifft die Erfindung ein Verfahren und eine Einrichtung zum verlustfreien und verlustbehafteten Codieren und Decodieren von Daten in Kompressions/Dekompressionssystemen.
  • Die Datenkompression ist ein äußerst brauchbares Werkzeug, um große Datenmengen zu speichern und zu übertragen. Beispielsweise wird die Zeit, die zum Übertragen eines Bildes, beispielsweise eine Faksimileübertragung eines Dokuments erforderlich ist, drastisch reduziert, wenn die Kompression angewendet wird, um die Anzahl an Bits zu verringern, die erforderlich sind, um das Bild neu zu erzeugen.
  • Im Stand der Technik gibt es viele verschiedene Datenkompressionstechniken, welche in zwei große Kategorien eingeteilt werden, nämlich ein verlustbehaftetes und ein verlustfreies Codieren. Verlustbehaftetes Codieren schließt ein Codieren ein, das auf einen Informationsverlust hinausläuft, so daß es keine Garantie für eine einwandfreie Rekonstruktion der ursprünglichen Daten gibt. Das Ziel einer verlustbehafteten Kompression besteht darin, daß Änderungen in den ursprünglichen Daten in einer sol chen Weise ausgeführt werden, daß sie nicht zu beanstanden oder feststellbar sind. Bei der verlustfreien Kompression wird die gesamte Information zurückerhalten, und die Daten werden in einer Weise komprimiert, welche eine einwandfreie Rekonstruktion ermöglicht.
  • Bei der verlustfreuen Kompression werden eingegebene Symbole oder Intensitätsdaten in ausgegebene Codeworte umgewandelt. Die Eingabe kann ein Bild, einen Ton, eindimensionale Daten (z.B. Daten, die sich räumlich oder zeitlich ändern) zweidimensionale Daten (z.B. Daten, die sich in zwei räumlichen Richtungen (oder einer räumlichen und einer zeitlichen Dimension) ändern) oder mehrdimensionale (mehrere spektrale) Daten enthalten. Wenn die Kompression erfolgreich ist, werden die Codeworte in weniger Bits dargestellt als die Anzahl Bits, welche für die uncodierten eingegebenen Symbole (oder Intensitätsdaten) erforderlich sind. Verlustfreie Codierverfahren schließen Wörterbuch-Codierverfahren (z.B. Lempel-Ziv), ein Lauflängen-Codieren, ein enumeratives Codieren und ein Entropie-Codieren ein. Bei der verlustfreien Bildkompression basiert eine Kompression auf Prädiktionen oder Kontexten plus Codieren. Die JBIG-Norm für Faksimile-Kompression und Differenzen-Pulscodemodulation (DPCM-Verfahren- eine Option in der JPEG-Norm) für fortlaufende Ton-Bilder sind Beispiele für eine verlustfreie Kompression von Bildern. Bei der verlustbehafteten Kompression werden eingegebene Symbole oder Intensitätsdaten vor einer Umsetzung quantisiert, um Codeworte auszugeben. Eine Quantisierung wird gewünscht, um relevante Kenngrößen der Daten zu konservieren, während unwichtige Kenndaten beseitigt werden. Vor einer Quantisierung benutzt ein verlustbehaftetes Kompressionssystem oft eine Transformation, um eine Energieverdichtung zu schaffen. JPEG ist ein Beispiel einer verlustbehafteten Codiermethode für Bilddaten.
  • Bei neueren Entwicklungen in der Bildsignal-Verarbeitung wird die Aufmerksamkeit auf einen Mangel an wirksamen und genauen Formen eines Datenkompressions-Codierens gerichtet. Verschiede ne Transformationsformen oder eine pyramidale Signalverarbeitung sind vorgeschlagen worden, einschließlich einer pyramidalen Verarbeitung mit Mehrfachauflösung und einer pyramidalen Elementarwellen- bzw. Wavelet-Verarbeitung. Diese Formen werden auch als Unterband-(subband-)Verarbeiten und hierarchisches Verarbeiten bezeichnet. Ein pyramidales Wavelet-Verarbeiten von Bilddaten ist eine spezifische Form von pyramidalem Verarbeiten mit Mehrfachauflösung, bei welchem Quadratur-Spiegelfilter (QMFs) verwendet werden können, um eine Unterbandzerlegung eines Vorlagenbildes zu erzeugen. Es gibt auch noch andere Arten von Nicht-QMF-Wavelets. (Bezüglich mehr Information zu Wavelet-Verarbeitung, siehe Antonini, M., et al., "Image Coding Using Wavelet Tranform" IEEE Transactions on Image Processing, Vol. 1, No. 2, April 1992; Shapiro, J., "An Embedded Hierarchical Image Coder Using Zerotrees of Wavelet Coefficients", Proc. IEEE Data Compression Conference, 5.214 bis 223, 1993).
  • Eine Schwierigkeit bei vielen bekannten Wavelet-Verarbeitungen besteht darin, daß ein großer Speicher erforderlich ist, um alle Daten zu speichern, während sie zu verarbeiten sind. Mit anderen Worten, um eine Wavelet-Verarbeitung durchzuführen, müssen alle Daten geprüft werden, bevor ein Codieren an den Daten durchgeführt wird. In einem solchen Fall gibt es keine Datenausgabe, bis zumindest ein voller Durchgang durch alle Daten gemacht worden ist. In der Praxis umfaßt eine Wavelet-Verarbeitung üblicherweise mehrere Durchgänge (multiple passes) durch die Daten. Deswegen ist oft ein großer Speicher erforderlich. Es ist wünschenswert, eine Wavelet-Verarbeitung zu benutzen, solange die Anforderung nach einem großen Speicher vermieden wird. Ferner ist es wünschenswert, eine Wavelet-Verarbeitung mit nur einem einzigen Datendurchgang durchzuführen.
    •
  • Viele Wavelet- oder Unterband-Transformations-Implementationen erfordern Filter in einer speziellen kanonischen Form. Beispielsweise müssen Tief- und Hochpaßfilter dieselbe Länge haben, die Summe der Quadrate der Koeffizienten muß eins sein, das Hochpaßfilter muß eine Zeit- und Frequenzumkehr des Tiefpaßfilters sein, usw. (siehe US-Patent 5,014,134, erteilt Mai 1991). Es ist wünschenswert, eine breitere Filterklasse zuzulassen. Das heißt, es ist wünschenswert, Wavelet- oder Unterband-Transformations-Implementierungen zu schaffen, welche Tief- und Hochpaßfilter verwenden die nicht dieselbe Länge haben, bei welchen die Summe der Quadrate der Koeffizienten nicht eins sein muß, das Hochpaßfilter nicht die Zeit- und Frequenzumkehr des Tiefpaßfilters haben muß, usw.
  • Die Erfindung ist gemäß der nebengeordneten Ansprüchen definiert. Vorteilhafte Weiterbildungen sind Gegenstand der auf die nebengeordneten Ansprüche unmittelbar oder mittelbar rückbezogenen Ansprüche.
  • Vorteilhaft ist eine verlustbehaftete und verlustfreie Kompression mit Hilfe einer Transformation geschaffen, welche eine gute Energieverdichtung schafft. Vorteilhaft ist auch ein Modellieren von gemeinsamen bzw. Verbund-Raum/Frequenzdomänen-Daten (joint spatial/frequency domain data) (eine Wavelet-Transformationsdomäne) vorgesehen, um einen effiziente Verdichtung (Kompression) zuzulassen. Ebenso ist eine progressive Übertragung mit einer Rate oder Verzerrung vorgesehen, die von dem Benutzer nach einem Codieren wählbar ist.
  • Ein Verfahren und eine Vorrichtung zum Codieren und Decodieren von Daten wird beschrieben. Vorteilhaft wird ein Verfahren und eine Einrichtung gezeigt, um transformierte Signale entsprechend eingegebenen Daten zu erzeugen. Vorteilhaft werden die transformierten Daten mit Hilfe einer reversiblen Wavelet-Transformation erzeugt. Vorteilhaft wird auch ein Verfahren und eine Einrichtung beschrieben, um die transformierten Signale in Daten zu verdichten, die eine verlustfreie komprimierte Version der eingegebenen Daten darstellen. Vorteilhaft werden die eingegebenen Daten mit Hilfe eines reversiblen Filters nicht-minimaler Länge zerlegt. Die Zerlegung kann mit mehreren eindimensionalen Filtern durchgeführt werden.
  • Vorteilhaft wird auch ein Verfahren und eine Einrichtung gezeigt, um eingebettetes Codieren der transformierten Signale durchzuführen. Das eingebettete Codieren gemäß der Erfindung umfasst ein Ordnen der Serie von Koeffizienten und ein Durchführen einer Bit-Signifikanz, die in den transformierten Signalen eingebettet ist.
  • Vorteilhaft wird auch ein Verfahren und eine Einrichtung gezeigt, um die verlustfrei komprimierte Version der eingegebenen Daten in transformierte Daten zu dekomprimieren. Darüber hinaus ist vorteilhaft eine verlustbehaftete Kompression von eingegebenen Daten durch ein Abbrechen bzw. Abschneiden von verlustfrei komprimierten Daten vorgesehen. Vorteilhaft wird auch ein Verfahren und eine Einrichtung gezeigt, um die eingegebenen Daten aus den transformierten Signalen in eine rekonstruierte Version der eingegebenen Daten mit Hilfe einer inversen, reversiblen Wavelet-Transformation zu erzeugen.
    •
  • Nachfolgend wird die Erfindung anhand von bevorzugten Ausführungsformen unter Bezugnahme auf die anliegenden Zeichnungen im einzelnen beschrieben, wobei gleiche Bezugszeichen gleiche Elemente bzw. Komponenten bezeichnen. Es zeigen:
  • 1A ein Blockdiagramm einer Ausführungsform eines Codierteils eines Codiersystems gemäß der Erfindung;
  • 1B ein Blockdiagramm einer Ausführungsform der Bit-Signifikanz-Einbettung gemäß der Erfindung;
  • 2A ein Blockdiagramm eines Wavelet-Analyse/Synthese-Systems;
  • 2B Vorwärts- und Rückwärts-(Umkehr-)Darstellungen von Transformationssystemen zum Filtern mit reversiblen Filtern mit nicht-überlappter minimaler Länge;
  • 3A bis 3D Ergebnisse zum Durchführen einer Vierstufen- bzw. Vierebenen-Zerlegung;
  • 4A ein Blockdiagramm einer pyramidalen Dreiebenen-Transformation;
  • 4B ein Blockdiagramm einer zweidimensionalen, Zweiebenen Transformation:
  • 4C ein Blockdiagramm von eindimensionalen Filtern, die eine Dekompression mit Mehrfachauflösung durchführen;
  • 4D ein Blockdiagramm eines Systems mit den reversiblen Wavelets der Erfindung;
  • 4E Blockdiagramme eines Vergrößerungs- und Analysesystems, welches die reversiblen Wavelets der Erfindung benutzt;
  • 5 eine Baumstruktur bei Wavelets-Koeffizienten;
  • 6a und 6a (fortgesetzt) ein Flußdiagramm einer Ausführungsform des Einzellisten-Nullbaum-Modellierens (single list zerotree modeling) zum Codieren in der Erfindung;
  • 6b und 6b (fortgesetzt) ein Flußdiagramm einer Ausführungsform des Einzellisten-Nullbaum-Modellierens zum Codieren in der Erfindung mit Hilfe eines reduzierten (verkleinerten) Flag-Speichers;
  • 6c ein Flußdiagramm einer Ausführungsform des Einzellisten-Nullbaum-Modellierens zum Decodieren in der Erfindung;
  • 6d ein Flußdiagramm einer Ausführungsform des Einzellisten-Nullbaum-Modellierens zum Decodieren in der Erfindung mit Hilfe eines reduzierten Flag-Speichers;
  • 7a ein Flußdiagramm einer Ausführungsform des Horizont-Modellierens zum Codieren in der Erfindung;
  • 7b ein Flußdiagramm einer Ausführungsform des Horizont-Modellierens zum Codieren in der Erfindung mit Hilfe eines reduzierten Flag-Speichers;
  • 7c ein Flußdiagramm des Horizont-Modellierens zum Decodieren in der Erfindung;
  • 7d ein Flußdiagramm des Horizont-Modellierens zum Decodieren in der Erfindung mit Hilfe eines reduzierten Flag-Speichers;
  • 8a ein Flußdiagramm einer Ausführungsform eines B-Durchgangs (B-pass) zum Codieren in der Erfindung;
  • 8b ein Flußdiagramm einer Ausführungsform des B-Durchgangs zum Codieren in der Erfindung mit Hilfe eines reduzierten Flag-Speichers;
  • 9a ein Flußdiagramm einer Ausführungsform des B-Durchgangs für ein Decodieren in der Erfindung;
  • 9b ein Flußdiagramm einer Ausführungsform des B-Durchgangs für ein Decodieren in der Erfindung mit Hilfe eines reduzierten Flag-Speichers;
  • 10 eine Ausführungsform des Vorwärts-Wavelet-Filters der Erfindung;
  • 11 ein Blockdiagramm einer Ausführungsform eines Umkehr-Wa velet-Filters gemäß der Erfindung;
  • 12 ein Bild und Koeffizienten in einem Zeilenpuffer für eine pyramidale Vierebenen-Zerlegung;
  • 13 ein Blockdiagramm einer Ausführungsform einer Wavelet-Filterung mit Hilfe einer Filter-Steuereinheit;
  • 14 ein Blockdiagramm einer weiteren Ausführungsform einer Wavelet-Filterung mit Hilfe einer Filter-Steuereinheit;
  • 15 eine Zuteilung von Speicherbänken, um horizontale und vertikale Zugriffe zu stützen;
  • 16 die Filteroperation für eine Zweiebenen-Zerlegung;
  • 17 ein Blockdiagramm einer Ausführungsform des Kontextmodells der Erfindung;
  • 18 ein Blockdiagramm einer Ausführungsform der Vorzeichen/Größeneinheit der Erfindung;
  • 19 ein Blockdiagramm einer Ausführungsform der Größen-Speichereinheit der Erfindung;
  • 20 ein Blockdiagramm einer Ausführungsform der Signifikanzeinheit der Erfindung;
  • 21 ein Blockdiagramm einer Ausführungsform der Baumspeichereinheit der Erfindung;
  • 22 eine Blockdiagramm einer Ausführungsform von Koeffizienten Verschieben gemäß der Erfindung;
  • 23 ein Blockdiagramm einer alternativen Ausführungsform der Signifikanzeinheit der Erfindung mit Hilfe eines Ab gleichs mal 1,5;
  • 24 eine dynamische Zuordnung eines codierten Datenspeichers für eine Durchgangsoperation;
  • 25a und 25b ein Flußdiagramm einer Ausführungsform des Codierprozesses gemäß der Erfindung;
  • 26a und 26b ein Flußdiagramm des Decodierens einer Ausführungsform des Decodierprozesses der Erfindung;
  • 27a und 27b ein Flußdiagramm einer Ausführungsform des Prozesses zum Modellieren jedes Koeffizienten sowohl für die Codier- als auch die Decodierprozesse der Erfindung;
  • 28a und 28b ein Flußdiagramm einer alternativen Ausführungsform des Codierprozesses der Erfindung;
  • 29a und 29b ein Flußdiagramm einer alternativen Ausführungsform eines Decodierprozesses der Erfindung;
  • 30a und 30b ein Flußdiagramm einer alternativen Ausführungsform des Prozesses zum Modellieren jedes Koeffizienten in den Codier- und Decodierprozessen der Erfindung , und
  • 31 eine Ausführungsform von Multiplikatoren für das Frequenzband, das für einen Koeffizientenabgleich in der Erfindung verwendet ist.
  • Nunmehr wird ein Kompressions- und Dekompressionsverfahren beschrieben. In der folgenden detaillierten Beschreibung der Erfindung werden zahlreiche spezifische Details angeführt, wie Typen von Codierern, Zahlen von Bits, Signalnamen, usw., um ein gründliches Verständnis der Erfindung zu schaffen. Für einen Fachmann ist ersichtlich, daß die Erfindung auch ohne diese spe ziellen Details in der Praxis ausgeführt werden kann. In anderen Fällen werden bekannte Strukturen und Vorrichtungen in Blockdiagrammform dargestellt und nicht im einzelnen beschrieben, um die Erfindung nicht unverständlich zu machen.
  • Einige Teile der detaillierten Beschreibungen, welche folgen, sind in Form von Algorithmen und symbolischen Darstellungen von Operationen an Datenbis in einem Computer-Speicher dargestellt. Diese algorithmischen Beschreibungen und Darstellungen sind die Mittel, die von Fachleuten auf dem Datenverarbeitungsgebiet verwendet werden, um das Wesentliche ihrer Arbeit anderen Fachleuten am effektivsten zu übermitteln. Ein Algorithmus wird hier und im allgemeinen als eine in sich logische Folge von Schritten aufgefaßt, die zu einem gewünschten Ergebnis führen. Die Schritte sind solche, welche physikalische Manipulationen von physikalischen Größen erfordern. Üblicherweise, obwohl nicht notwendigerweise, nehmen diese Größen die Form von elektrischen oder magnetischen Signalen an, die gespeichert, übertragen, verknüpft, verglichen oder auf andere Weise behandelt werden können. Es hat sich als praktisch erwiesen, prinzipiell aus Gründen eines häufigen Umgangs auf diese Signale als Bits, Werte, Elemente, Symbole, Zeichen, Terme (Glieder), Zahlen o.ä, zu verweisen.
  • Jedoch sind alle diese und ähnliche Terme den entsprechenden physikalischen Größen zuzuordnen, und sind nur bequeme Signaturen, die bei diesen Größen verwendet werden. Wenn nicht speziell etwas anderes angegeben, wie es aus den folgenden Besprechungen offensichtlich ist, ist festzuhalten, daß bei der vorliegenden Erfindung Erörterungen, bei welchen Begriffe verwendet werden, wie "Verarbeiten" oder "Berechnen" oder "Bemessen" oder "Bestimmen" oder "Anzeigen" o.ä., sich auf die Funktion oder Prozesse eines Computersystems oder einer ähnlichen elektronischen Recheneinrichtung beziehen, welche Daten behandelt und transformiert, die als physikalische (elektronische) Größen in den Computer-System-Registern und -Speichern in anderen Daten darge stellt sind, die in ähnlicher Weise als physikalische Größen in den Computersystem-Speichern oder -Registern oder in anderen derartigen Informationsspeichern, Übertragungs- oder Anzeigevorrichtungen dargestellt sind.
  • Die Erfindung betrifft auch eine Einrichtung zum Durchführen der hier angeführten Operationen. Die Einrichtung kann speziell für die geforderten Zwecke ausgeführt werden oder sie kann einen Universal-Rechner aufweisen, der durch ein in dem Computer gespeichertes Programm selektiv aktiviert oder konfiguriert ist. Die hier wiedergegebenen Algorithmen und Darstellungen beziehen sich nicht auf irgendeinen speziellen Computer oder ein anderes Gerät. Verschiedene Universaleinrichtungen können mit Programmen gemäß den hier wiedergegebenen Lehren verwendet werden, oder es kann sich als bequem erweisen, speziellere Einrichtungen zu schaffen, um die geforderten Verfahrensschritte durchzuführen. Die geforderte Struktur einer Vielzahl dieser Einrichtungen ergibt sich aus der nachstehenden Beschreibung. Außerdem ist die vorliegende Erfindung nicht bezüglich einer ganz bestimmten Programmiersprache beschrieben. Vielmehr können eine Vielzahl von Programmiersprachen verwendet werden, um die Lehren der Erfindung auszuführen.
  • Überblick über die Erfindung
  • Die Erfindung schafft ein Kompressions/Dekompressionssystem mit einem Codier- und Decodierteil. Der Codierteil ist zum Codieren von eingegebenen Daten vorgesehen, um komprimierte Daten zu erzeugen, während der Decodierteil um Decodieren vorher codierter Daten vorgesehen ist, um eine rekonstruierte Version der ursprünglichen Eingabedaten zu erzeugen. Die eingegebenen Daten können eine Vielzahl von Datentypen aufweisen, wie ein (Einzel- oder Video-)Bild, ein Tonsignal, usw. In einer Ausführungsform sind die Daten digitale Signaldaten; jedoch sind auch digitalisierte Analogdaten, Textdaten-Formate und andere Formate möglich. Die Quelle der Daten kann ein Speicher oder ein Kanal für den Codier- und/oder den Decodierteil sein.
  • Gemäß der Erfindung können Elemente des Codier- und/oder des Decodier-Teils in Hardware oder Software ausgeführt sein, wie sie in einem Computersystem verwendet sind. Die Erfindung schafft ein verlustfreies Kompressions-/Dekompressionssystem. Die Erfindung kann auch entsprechend zusammengestellt werden, um eine verlustbehaftete Kompression/Dekompression durchzuführen.
  • 1A ist ein Blockdiagramm einer Ausführungsform des Codierteils des Systems. Der Decodierteil des Systems arbeitet im Hinblick auf den Datenfluß in umgekehrter Reihenfolge. In 1A werden eingegebene Bilddaten 101 mit einem Wavelet-Transformationsblock 102 empfangen. Der Ausgang des Blocks 102 ist mit einer Bitsignifikanz-Einbettungsblock 103 verbunden. Entsprechend dem Ausgang von dem Block 102 erzeugt der Block 103 zumindest einen Bitfluß, der von einem Entropie-Coder 104 aufgenommen wird. Entsprechend dem Eingang von dem Block 103 erzeugt der Entropie-Coder 104 einen Codefluß 107.
  • In einer Ausführungsform weist der Bitsignifikanz-Einbettungsblock 103 eine Vorzeichen-Größen-Formatiereinheit 109, ein auf Frequenz basierendes Kontextmodell 105 und ein gemeinsames Raum/Frequenz-Kontextmodell 106 auf, wie es in 1B dargestellt ist. In einer Ausführungsform weist das Modell 106 ein Horizont-Kontextmodell auf. In einigen Ausführungsformen weist ein Frequenz-Kontextmodellblock 105 ein Nullbaum-Modell auf. In einer anderen Ausführungsform weist ein Frequenz-Kontextmodell 105 ein Signifikanz-Baummodell auf. Eine Vorzeichen-Größeneinheit 109, ein Frequenz-Kontextmodell 105 und das gemeinsame Raum/Frequenz-(JSF-)Kontextmodell 106 führen ein Bit-Signifikanz-Einbetten in der Erfindung durch. Der Eingang der Vorzeichen-Größeneinheit 109 ist mit dem Ausgang des Wavelet-Transformations-Codierblocks 102 verbunden. Der Ausgang der Einheit 109 ist mit einem Schalter 108 verbunden, der vorgesehen ist, um den Ausgang der Einheit 109 mit einem Eingang entweder des Blocks 105 oder des Blocks 106 zu verbinden. Der Ausgang der Blöcke 105 und 106 ist mit dem Eingang eines Entropie-Coders 104 verbunden, welcher den abgegebenen Codefluß 107 erzeugt.
  • In 1A werden bei der Erfindung die Bilddaten 101 empfangen und mit Hilfe reversibler Wavelets in dem Wavelet-Transformationsblock 102 transformiert-codiert, wie später noch ausgeführt wird, um eine Reihe von Koeffizienten zu erzeugen, die eine Zerlegung mit Mehrfach-Auflösung des Bildes darstellen. Diese Koeffizienten werden von dem Bit-Signifikanz-Einbettungsblock 103 empfangen.
  • Der Block 103 ordnet und setzt die Koeffizienten in ein Vorzeichen-Größen-Format um, und basierend auf dieser Signifikanz (wie später noch beschrieben wird) werden die formatierten Koeffizienten einer Kombination von verschiedenen Einbett-Modellierverfahren unterzogen. In der Erfindung werden die formatierten Koeffizienten jeweils einem von zwei Einbett-Modellierverfahren (z.B. einer auf Frequenz basierenden Modellierung und einer SJF-Modellierung) unterzogen.
  • In einer Ausführungsform werden die formatierten Koeffizienten entweder einer auf Frequenz basierenden Modellierung oder einer JSF-Modellierung unterzogen. Wenn die eingegebenen Daten Bilddaten mit Mehrfach-Bitebenen aufweisen, werden bei der Erfindung eine Anzahl Bitebenen mit einem frequenz-gestützen Modellieren codiert, während die verbleibenden Bitebenen mit einem JSF-Modellieren codiert werden. Die Entscheidung, welches Verfahren bei welchen Bitebenen anzuwenden ist, kann ein Benutzer-Parameter sein. In einer Ausführungsform werden höhere Bitebenen der Koeffizienten mit der frequenz-gestützten Modellierung der Erfindung geordnet und codiert. In dem frequenz-gestützten Kontextmodell-Verfahren der Erfindung ist die Signifikanz-Prädiktion der Koeffizientenbits auf die pyramidale Struktur des Wavelets bezogen. Die niedrigerwertigen Koeffizienten-Bitebenen werden mit dem JSF (joint space/frequency) Kontextmodell der Erfindung geordnet und codiert. Die JSF-Modellierung, beispielsweise eine Horizont-Modellierung, schafft Vorteile gegenüber einem frequenz-gestützten Codieren für Bitebenen, die weniger korreliert bezüglich der Frequenzdomäne durch die Koeffizientenrelationen sind.
  • Die Ergebnisse der Bit-Signifikanz-Einbettung sind Entscheidungen (oder Symbole), die mittels des Entropie-Coders zu codieren sind. In einer Ausführungsform werden alle Entscheidungen an einen einzigen Codierer gesendet. In einer anderen Ausführungsform werden Entscheidungen durch Signifikanz kenntlich gemacht, und Entscheidungen für jede Signifikanzebene werden von verschiedenen (physikalischen oder virtuellen) Mehrfach-Codiere codiert.
  • Die Bitflüsse, die sich von dem frequenz-gestützten Kontextmodell-Block 105 und dem JSF-Kontextmodell-Block 106 ergeben, werden in der Signifikanz-Reihenfolge mit Hilfe des Entropie-Coder 104 codiert. In einer Ausführungsform weist der Entropie-Coder einen binären Entropie-Coder auf. In einer weiteren Ausführungsform weist der Entropie-Coder 104 einen Q-Coder, einen B-Coder, wie er in US-Patent 5,272,478 definiert ist, oder einen Coder auf, wie sie in der am 10. Februar 1993 eingereichten US-Patentanmeldung S.N. 08/016,035 beschrieben ist, mit dem Titel "Verfahren und Einrichtung zum parallelen Decodieren und Codieren von Daten". (Bezüglich mehr Information zu dem Q-Coder, siehe Pennebaker, W.B., et al., "An Overview of the Basis Principles of the Q-coder, Adaptive Binary Arithmetic," IBM Journal of Research and Development, Vol. 32, S.717-26, 1988. In einer Ausführungsform erzeugt ein einziger Coder einen einzigen Code-Ausgangsfluß. In einer anderen Ausführungsform erzeugen mehrere (physikalische oder virtuelle) Coder mehrere (physikalische oder virtuelle) (Mehrfach-)Datenflüsse.
  • Wavelet-Zerlegung
  • Die Erfindung führt anfangs eine Zerlegung eines Bildes (in Form von Bilddaten) oder eines anderen Datensignals mit Hilfe reversibler Wavelets durch. In der Erfindung weist eine reversible Wavelet-Tranformation eine Implementierung eines exakten Konstruktionssystems im Ganzzahl-Arithmetik auf, so daß ein Signal mit ganzzahligen Koeffizienten verlustfrei wiedergewonnen werden kann. Durch Verwenden von reversiblen Wavelets kann mittels der Erfindung eine verlustfreie Kompression mit endlicher Präzisionsarithmetik geschaffen werden. Die Ergebnisse, die erzeugt worden sind, indem die reversible Wavelet-Transformation bei Bilddaten angewendet wird, sind eine Koeffizientenreihe. In einer Ausführungsform der Erfindung wird die reversible Wavelet-Transformation mit Hilfe eines Satzes Filter durchgeführt. In einer Ausführung sind die Filter ein Tiefpaßfilter mit zwei Abgriffen und ein Hochpaßfilter mit sechs Abgriffen. In einer Ausführungsform werden diese Filter nur mit Hilfe von Additions- und Subtraktionsoperationen (plus einem fest verdrahteten Bit-Shifting) implementiert.
  • In der Erfindung erzeugt das Hochpaßfilter mit Hilfe der Ergebnisse des Tiefpaßfilters ein Ausgangssignal. Die sich ergebenden Hochpaß-Koeffizienten sind nur wenige Bits, die größer als die Pixel-Auflösung sind, und die Tiefpaß-Koeffizienten sind dieselben wie die Pixel-Auflösung. Da nur die Tiefpaß-Filter wiederholt in einer pyramidalen Zerlegung gefiltert werden, wird die Auflösung in Mehrebenen-Zerlegungen nicht erhöht.
  • Ein Wavelet-Transformationssystem ist durch ein Paar FIR-Analysefilter h0(n), hI(n) und durch ein Paar FIR-Synthesefilter g0(n), g1(n) definiert. In der Erfindung sind h0 und g0 die Tiefpaßfilter und h1 und g1 sind die Hochpaßfilter. Ein Blockdiagramm des Wavelet-Systems ist in 2A dargestellt. In 2A werden für ein Eingangssignal x(n) die Analyse für h0 und h1 verwendet, und die Ausgänge durch 2 (kritisch unterabgetastet (subsampled)) gemindert, um die transformierten Signale y0'(n) und y1(n) zu erzeugen, welche hier als tiefpaß- bzw. hochpaß-gefilterte Koeffizienten bezeichnet werden. Die Analysefilter und deren entsprechende Dezimier- oder Unterabtast-Blöcke bilden den Analyseteil des Wavelet-Transformationssystems. Die Coder/Decoder enthalten die gesamte Verarbeitungslogik und Routinen, die in der transformierten Domäne (z.B. Prädiktion, Quantisierung, Codierung usw.) durchgeführt worden sind. Das in 2A dargestellte Wavelet-System enthält auch einen Syntheseteil, in welchem die transformierten Signale mit 2 hochgetastet (upsampled) werden (z.B. eine Null wird nach jedem Term eingesetzt), und durchlaufen dann Synthesefilter g0(n), g1(n) . Die tiefpaß-gefilterten y0(n) durchlaufen das Tiefpaß-Synthesefilter g0, und die hochpaß-gefilterten Koeffizienten y1(n) durchlaufen das Hochpaßfilter g1. Die Ausgänge der Filter g0(n) und g1(n) werden verknüpft, um x(n) zu erzeugen.
  • Während das Runter- und das Hochtasten in einigen Ausführungsformen durchgeführt werden, werden in anderen Ausführungsformen Filter verwendet, so daß die Rechnungen, welche infolge des Runter- und des Hochtastens nicht benötigt werden, nicht durchgeführt werden.
  • Das Wavelet-System kann anhand der Z-Tranformation beschrieben werden, wobei X(Z), X ^(Z) die eingegebenen bzw. ausgegebenen Signale sind, Y0(Z), Y1(Z) die tiefpaß- und hochpaßtransformierten Signale sind, H0(Z), H1(Z) die Tiefpaß- und die Hochpaß-Analysefilter sind und G0(Z), G1(Z) die Tiefpaß- und die Hochpaß-Synthesefilter sind. Wenn es keine Alteration oder Quantisierung in der Transformations-Domäne gibt, ist der Ausgang X ^(Z) in 2 gegen durch:
    Figure 00160001
  • In der Erfindung wird der zweite Term von X ^(Z), der als der "Aliasing"-Term bezeichnet ist, annulliert, da die Synthesefilter als der Quadratur-Spiegel des Synthesefilters definiert sind, d.h.
  • Figure 00170001
  • Hinsichtlich der Filter-Koeffizienten gilt:
    Figure 00170002
  • Daher wird für ein Quadratur-Spiegelfilterpaar nach einer Substitution der Ausgang:
    Figure 00170003
  • In dem Quadratur-Spiegelsystem der Erfindung ist der Ausgang nur in Form der Analysefilter definiert. Die Wavelet-Transformation wird rekursiv bei den transformierten Signalen angewendet, so daß die durch die Filter erzeugten Ausgangssignale direkt oder indirekt als Eingangssignale in den Filtern verwendet werden. In der beschriebenen Ausführungsform wird nur die tiefpaßtransformierte Komponente y0(n) rekursiv transformiert, so daß das System pyramidal ist. Ein Beispiel eines solchen pyramidalen Systems ist in 4A dargestellt.
  • Die Z-Transformation ist eine bequeme Darstellungweise, um die Operation von Hardware und/oder von Software an Daten auszudrücken. Eine Multiplikation Z–m modelliert eine m-Taktzyklus-Verzögerung in Hardware, und eine Anordnung greift auf das m-te vorherige Element in der Software zu. Derartige Hardware-Implementationen enthalten Speicher, Pipestufen, Schieberegister, Register, usw.
  • In der Erfindung sind die Signale x(n) und x ^(n) identisch bis auf eine multiplikative Konstante und einen Verzögerungsterm, d.h. in Form der Z-Transformation X ^(Z) = cZ–mX(Z).
  • Dies wird ein exaktes Rekonstruktionssystem genannt. Folglich ist in einer Ausführungsform der Erfindung die Wavelet-Transformation, die anfangs bei den eingegebenen Daten angewendet worden ist, exakt rekonstruierbar.
  • Eine Ausführungsform der Erfindung, bei welcher die Hadamard-Transformation verwendet ist, ist ein exaktes Rekonstruktionssystem, welches in normierter Form die folgende Darstellung in der Z-Domäne hat:
    Figure 00180001
  • Nach Substitution wird der Ausgang: X ^(Z) = Z–1X(Z),welches deutlich eine exakte Rekonstruktion ist. (Für mehr Information bezüglich der Hadamard-Transformation siehe Anil K. Jain, Fundamentals of Image Processing, S. 155).
  • Eine reversible Version der Hadamard-Transformation wird hier als die S-Transformation bezeichnet. (Für mehr Information bezüglich der S-Transformation siehe Said, A. and Pearlman, W, "Reversible Image Compression via Multiresolution Representation and Predictive Coding," Dept. of Electrical, Computer and Systems Engineering, Renssealaer Polytechnic Institute, Troy, NY 1993). Da die Hadamard-Transformation eine exakte Rekonstruktions-Transformation ist, ist die folgende nicht-normierte Version (welche sich von der Hadamard-Transformation durch konstante Faktoren unterscheidet) auch eine exakte Rekonstruktions-Transformation.
  • Figure 00180002
  • Wenn die Abtastwerte des Eingangssignals als x0, x1 gegeben sind, ist die S-Transformation eine resersible Implementation dieses Systems, nämlich
    Figure 00190001
  • Die Schreibweise ⌊.⌋ bedeutet Abrunden nach unten oder Kürzen und wird manchmal als die Boden-(floor)Funktion bezeichnet. Dementsprechend bedeutet die Decken-(ceiling)Funktion ⌈.⌉ aufrunden nach oben zu der nächsten ganzen Zahl.
  • Der Nachweis, daß diese Implementierung reversibel ist, folgt aus der Tatsache, daß die einzige in der Näherung verloren gegangene Information das niedrigstwertige Bit von x(0) + x(1) ist. Da jedoch das niedrigstwertige Bit von x(0) + x(1) und x(0) – x(1) identisch ist, kann dies aus dem Hochpaß-gefilterten Ausgang y1(0) wiedergewonnen werden. Mit anderen Worten, es gilt:
    Figure 00190002
  • Die S-Information ist eine nicht-überlappende Transformation mit reversiblen Filtern minimaler Länge. Filter minimaler Länge weisen ein Filterpaar auf, wobei beide Filter zwei Abgriff haben. Transformationen minimaler Länge schaffen keine gute Energieverdichtung. Filter minimaler Länge implementieren eine nicht-überlappte Transformation, da die Länge der Filter gleich der Anzahl Filter ist. Überlappte Informationen benutzen zumindest ein Filter, welches eine Länge hat, die größer als die Anzahl Filter ist. Überdeckte Informationen mit längeren Filtern (nicht-minimaler Länge) können eine bessere Energieverdichtung schaffen. Gemäß der Erfindung sind reversible Filter mit nicht-minimaler Länge vorgesehen, welche eine überlappte Transformation zu lassen.
  • Ein anderes Beispiel eines Exakt-Rekonstruktionssystems weist die Zwei/Sechs(TS)-Transformation auf, welche die Z-Domänen-Definition hat
    Figure 00200001
  • Nach Substitution ist der Ausgang dann X ^(Z) = 2Z–3X(Z),welches eine Exakt-Rekonstruktions-Transformation ist.
  • Die rationale, nicht-normierte Version der TS-Transformation weist auf:
    Figure 00200002
  • Wenn x(0), x(1), ... x(5) sechs Tastwerte des Signals sind, dann sind die ersten drei tiefpaß-gefilterten Koeffizienten y0(0) = y0(1), y0(2) und der erste hochpaß-gefilterte Koeffizient y1(0) gegeben durch
    Figure 00200003
    y1(0) = ⌊(–(x(0) + x(1))) + 8(x(2) – x(3)) + (x(4) + x(5))/8⌋.
  • Jedoch ist die gerade Vorwärts-Implementierung der rationalen nicht-normierten Version der TS-Transformation nicht reversibel. Das folgende Beispiel zeigt, daß die Implementierung lokal nicht reversibel ist . Eine längere Folge kann als ein Beispiel für den umfassenden Fall konstruiert werden. Da –(x(0) + x(1)) + (x(4) + x(5)) ≠ –yo(0) + xo(2) wegen des Abrundens ist, ist, um y0(0) und y0(2) zu berechnen, diese Transformation mit
  • Hilfe einer lokalen Information nicht reversibel.
  • Wenn beispielsweise x(0) = 1, x(1) = 1, x(2) = 3, x(3) = 1, x(4) = 1, x(5) = 1 ist, dann gilt: y0(0) = ⌊(1 + 1)/2⌋ = 1 y0(1) = ⌊(3 + 1)/2⌋ = 2 y0(2) = ⌊(1 + 1)/2⌋ = 1 y1(0) = ⌊[–(1 + 1) + 8(3 – 1) + (1 + 1)]/8⌋ = ⌊(–2 + 16 + 2)/8⌋ = 2und wenn x(0) = 1, x(1) = 2, x(2) = 4, x(3) = 1, x(4) = 1, x(5) = 1 ist, dann gilt: y0(0) = ⌊(1 + 2)/2⌋ = 1 y0(1) = ⌊(4 + 1)/2⌋ = 2 y0(2) = ⌊(1 + 1)/2⌋ = 1 y1(2) = ⌊[–(1 + 2) + 8(4 – 1) + (1 + 1)]⌋/8 = ⌊(–3 + 24 + 2)/8⌋ = ⌊23/8⌋ = 2
  • Da y0(0), y0(1), y0(2) und y1(0) dieselben sind für zwei verschiedene Sätze von Eingangssignalen x(0) ... x(5), ist die Transformation nicht reversibel, da, wenn y0(0), ... y1(0) gegeben ist, sie nicht aus dieser lokalen Information bestimmt werden kann, welche der zwei Sätze eingegeben wurden. (Es kann bekanntlich nur nachgewiesen werden, daß die Transformation nicht reversibel ist, wenn eine umfassende Information für alle Koeffizienten verwendet wird).
  • Nunmehr wird eine reversible TS-Transformation betrachtet, welche hier als RTS-Transformation bezeichnet ist, welche eine andere Hochpaß-Filteroperation schafft.
  • Wenn x(0), x(1), x(2), x(3), x(4), x(5) sechs (6) Tastwerte des Signals sind, dann sind die ersten drei tiefpaß-gefilterten Koeffizienten y0(0), y0(1), y0(2) und der erste hochpaß-gefilterte Koeffizient y1(0) gegeben durch:
    Figure 00220001
    y1(0) = ⌊(–⌊(x(0) + x(1))/2⌋ + 4(x(2) – x(3)) + ⌊(x(4) + x(5))/2⌋)/4⌋ = ⌊(–y0(0) + 4(x(2) – x(3)) + y0(2))/4⌋.
  • Da x(2) – x(3) = y1(0) –⌊–(y0(0) + y0(2))/4⌋ist, dann ist x(2) – x(3) vollständig bekannt. Mit yo(1) = ⌊(x(2) + x(3))/2⌋ und x(2) – x(3) und x(2) – x(3) wie oben festgelegt ist, können x(2) und x(3) wieder gewonnen werden, da die niedrigstwertigen Bits von x(0) + x(1) und x(0) – x(1) identisch sind.
  • Insbesondere gilt dann d(0) = x(2) – x(3) = y1(0) – ⌊(–y0(0) + y0(2)/4)⌋ x(2) = y0(1) + ⌊(d(0) + 1)/2⌋ x(3) = y0(1) + ⌈(d(0) – 1)/2⌉
  • Eine Ausführungsform des Vorwärts-Filters für die RTS-Transformation ist im Anhang A dargestellt, welcher in der Programmiersprache "C" ausgeführt ist. Zu beachten ist, daß mathematisch die Gleichung
    Figure 00220002
    und die Gleichung
    Figure 00220003
    dieselben sind, wenn sie mit einer unbegrenzten Präzisions-Arithmetik durchgeführt werden. Der Grund, weshalb die zweite Gleichung ein reversibles Filter darstellt, ist offensichtlich, wenn sie mit einer ganzzahligen Arithmetik durchgeführt worden ist. Beispiele von Hardware-Implementierungen des Tiefpaß- und des Hochpaßfilters werden in Verbindung mit 10 und 11 beschrieben.
  • Zu beachten ist, daß sowohl bei der TS- als auch bei der RTS-Transformation das Tiefpaßfilter implementiert wird, so daß der Bereich des eingegebenen Signals x(n) derselbe ist wie bei dem abgegebenen Signal y0(n). Wenn beispielsweise das Signal ein 8 Bit-Bild ist, ist auch das Ausgangssignal des Tiefpaßfilters 8 Bit. Dies ist eine wichtige Eigenschaft für ein pyramidales System, bei welchem das Tiefpaßfilter nacheinander angewendet wird, da in bekannten Systemen der Bereich des abgegebenen Signals größer ist als derjenige des eingegebenen Signals, was aufeinanderfolgende Anwendungen des Filters schwierig macht. Außerdem hat das Tiefpaßfilter nur zwei Abgriffe, wodurch es zu einem nicht-überlappenden Filter wird. Diese Eigenschaft ist wichtig für die Hardware-Implementierung, wie später noch beschrieben wird.
  • In einer Ausführungsform sind bezüglich der RTS-Transformation die Tiefpaß- und Hochpaßfilter so definiert:
    Figure 00230001
  • Folglich können die Ergebnisse von dem Tiefpaßfilter zweimal (in den ersten und dritten Termen) in dem Hochpaßfilter verwendet werden. Folglich müssen nur zwei weitere Informationen durchgeführt werden, um die Ergebnisse des Hochpaßfilters zu erreichen.
  • Viele überlappte reversible Filter nicht-minimaler Länge können bei der Erfindung verwendet werden. Solche Vorwärts- und inverse Darstellungen des Transformationssystems zum Filtern mit rever siblen Filtern nicht-überlappter minimaler Länge sind in 2B dargestellt. Beispielsweise kann die folgende Klasse Filter in der Erfindung verwendet werden. Für eine ganze Zahl L ≥ z gilt: d(0) = x(2(⌊L/2⌋ + 1)) – x(2(⌊L/2⌋ + 1) + 1)und y0(0) = ⌊(x(0) + x(1))/2⌋ y0(1) = ⌊((2) + x(3))/2⌋ y0(L – 1) = ⌊(x(2⌊(L – 1)/2⌋) + x(2⌊(L – 1)/2⌋ + 1))/2⌋und
    Figure 00240001
  • Die Länge des Tiefpaßfilters ist 2L. Wenn L ungerade ist, liegt das Filter näher bei einem symmetrischen Filter. Wenn ai, b, ci und k ganze Zahlen sind, und k ≤ b ist, dann ist das Filter reversibel. Wenn ai, b, ci und k Potenzen von zwei sind (oder das Negative oder Komplement einer Potenz von zwei), dann kann die Implementierung des Filters vereinfacht werden. Wenn k = b (unabhängig von den Werten von ai und i1) ist, dann wird der Bereich des Ausgangssignals des Hochpaßfilters y1 minimiert. Für jedes a1 hat dann, wenn es genau ein ci gibt, wobei ai = –ci ist, das Hochpaßfilter keine Antwort bei einem konstanten Eingang. Wenn ai = –cj ist, wenn j – (L – 1) = i ist, dann kann das Filter näher bei einem symmetrischen Filter sein.
  • Eine weitere brauchbare Eigenschaft ist
    Figure 00240002
  • Hiervon kommt es, daß das Hochpaßfilter kein Ansprechen auf ein sich linear änderndes Eingangssignal, wenn m = 1 ist, und auch auf ein sich quadratisch änderndes Eingangssignal hat, wenn m = 2 ist, usw, wobei m der momentane Zustand ist. Diese Eigenschaft ist hauptsächlich der Grund dafür, daß die RTS-Transformation eine bessere Energieverdichtung hat als die S-Transformation.
  • Obwohl Filter den Minimum-Beschränkungen für eine Reversibilität entsprechen müssen, können verschiedene Anwendungen Filter verwendet werden, welche keinen, einigen oder allen der übrigen Eigenschaften gerecht werden. In einigen Ausführungsformen wird eines der folgenden als Beispiel angeführten Hochpaßfiltern verwendet. Diese Filter sind in einer Schreibweise aufgelistet, welche gerade die ganzzahligen Koeffizienten der rationalen Version der Filter aufführt, um eine Unklarheit bei der Erfindung
    Figure 00250001
  • Das letzte Filter wird auch das (Zwei/Zehn-Two/Ten)TT-Filter bezeichnet, und es hat die Eigenschaft, dass es nicht auf eine kubisch ansteigende Funktion anspricht. Da 22 = 16 + 2 × 3 und 3 = 2 + 1 gilt, kann dieses Filter mit insgesamt sieben Additionen und Subtraktionen implementiert werden.
  • Die strikten Reversibilitäts-Anforderungen für Filter können durch Beachten des Folgenden gelockert werden. Hochpaß-Koeffizienten werden in irgendeiner Reihenfolge codiert und decodiert Pixel-Werte, welche den vorher decodierten Hochpaß-Koeffizienten entsprechen, sind genau bekannt, so daß sie in einer aktuellen Hochpaß-Filterung verwendet werden können. Beispielsweise kann das folgende Filter verwendet werden, wenn eine Rasterreihenfolge angewendet wird.
  • Figure 00260001
  • Das Verwenden eines einzigen, fest eingestellten Filters ist nicht erforderlich. Adaptive Filter oder mehrere Filter können verwendet werden. Die Daten, die verwendet sind, um sie an mehrere Filter anzupassen oder über diese auszuwählen, müssen auf Daten beschränkt werden, welche in den Decoder vor einer speziellen inversen Filteroperation verfügbar sind.
  • Eine Möglichkeit, mehrere Filter zu benutzen, besteht darin, die Hochpaß-Koeffizienten progressiv zu verarbeiten. Alternative Hochpaß-Filteroperationen (y1(0), y1(2), y1(4), ...) können zuerst mit einem reversiblen Filter, wie dem RTS-Hochpaßfilter, verarbeitet werden. Die restliche Verarbeitung (y1(1), y1(3), y1(5), ...) kann ein nicht-reversibles Filter mit bis zu sechs Abgriffen benutzen, da die exakten Werte der Eingänge in dem Überlappungsteil des Filters bekannt sind. Beispielsweise kann eines der folgenden Filter verwendet werden:
    Figure 00260002
  • In einigen Ausführungsformen kann das Hochpaßfilter durch eine Prädiktions-/Interpolations-Operation ersetzt werden. Ein Prädiktor/Interpolator kann die Differenz zwischen einem Paar Eingängenvoraussagen, die irgendwelche Daten verwenden, welche in dem Decoder vor der speziellen Prädiktions-/Interpolationsoperation verfügbar sind. Die vorhergesagte Differenz wird von der tatsächlichen Differenz der Eingänge subtrahiert und wird abgegeben. In einer Ausführungsform werden bekannte Prädiktionsverfahren, die in DPCM verwendet sind, ein progressives Codieren und ein Raumdomänen-Codieren verwendet.
  • Mit Hilfe der Tiefpaß- und der Hochpaßfilter der Erfindung wird eine Mehrfach-Auflösungs-Zerlegung durchgeführt. Die Anzahl an Kompositionsebenen ist variabel und kann irgendeine Anzahl sein; jedoch reicht gegenwärtig die Anzahl an Zerlegungsebenen von zwei bis fünf Ebenen.
  • Wenn beispielsweise die reversible Wavelet-Transformation rekursiv bei einem Bild angewendet wird, arbeitet die erste Zerlegungsebene mit dem feinsten Detail oder der feinsten Auflösung. Auf einer ersten Zerlegungsebene wird ein Bild in vier Unterbilder (z.B. Unterbänder) zerlegt. Jedes Unterband stellt ein Band von Ortsfrequenzen dar. Die Unterbänder der ersten Ebene sind bezeichnet mit LL0, LH0, HL0 und HH0. Der Prozeß, das ursprüngliche Bild zu zerlegen, schließt ein Unterabtasten (subsampling) durch zwei sowohl in horizontalen als auch in vertikalen Dimensionen ein, so daß die Unterbänder LL0, LH0, HL0 und HH0 der ersten Ebene, die jeweils ein Viertel so viele Koeffizienten haben wie das eingegebene Signal, Pixels (oder Koeffizienten) des Bildes hat, wie in 3A dargestellt ist.
  • Ein Unterband LL0 enthält gleichzeitig niederfrequente horizontale und niederfrequente vertikale Informationen. Üblicherweise ist ein großer Teil der Bildenergie in diesem Unterband konzentriert. Das Unterband LH0 enthält niederfrequente horizontale und hochfrequente vertikale Information (z.B. horizontale Randinformation). Das Unterband HL0 enthält hochfrequente, horizontale und niederfrequente vertikale Information (z.B. vertikale Randinformation). Das Unterband HH0 enthält hochfrequente horizontale und vertikale Information (z.B. Struktur- oder Diagonal-Rand-Information).
  • Jede der folgenden zweiten, dritten und vierten unteren Zerlegungsebenen wird dadurch erzeugt, daß das niederfrequente LL-Unterband der vorhergehenden Ebene zerlegt wird. Das Unterband LL0 der ersten Ebene wird zerlegt, um Unterbänder LL1 LH1, HL1 und HH1 der moderat detaillierten zweiten Ebene zu erzeugen. Ähnlich wird das Unterband LL1 zerlegt, um grob detaillierte Unterbänder LL2, LH2 HL2 und HH2 der dritten Ebene zu erzeugen. Ebenso wird das Unterband LL2 erzeugt, um grober detaillierte Unterbänder LL3, LH3, HL3 HH3 der dritten Ebene zu erzeugen, wie in 3D dargestellt ist. Infolge des Unterabtastens durch zwei ist jedes Unterband der zweiten Ebene ein Sechzehntel der Größe des ursprünglichen Bildes. Jeder Tastwert (z.B. Bildelement) auf dieser Ebene stellt ein moderates Detail in dem ursprünglichen Bild an derselben Stelle dar. Ebenso ist jedes Unterband der dritten Ebene 1/64 der Größe des ursprünglichen Bildes. Jedes Bildelement auf dieser Ebene entspricht einem relativ groben Detail in dem ursprünglichen Bild an derselben Stelle. Ebenso ist jedes Unterband der vierten Ebene 1/256 der Größe des ursprünglichen Bildes.
  • Da die zerlegten Bilder infolge des Unterabtastens kleiner als das ursprüngliche Bild sind, kann derselbe Speicher, der zum Speichern des ursprünglichen Bildes verwendet worden ist, verwendet werden, um alle zerlegten Unterbänder zu speichern. Mit anderen Worten, das ursprüngliche Bild und die zerlegten Unterbänder LL1 und LL1 werden ausrangiert und nicht in einer Dreiebenen-Zerlegung gespeichert.
  • Eine Elter-Kind-Beziehung besteht zwischen einer Unterband-Komponente, die ein grobes Detail darstellt, relativ zu einer entsprechenden Unterband-Komponente in der nächsten feiner detaillierten Ebene.
  • Obwohl nur vier Unterband-Zerlegungsebenen dargestellt sind, könnten zusätzliche Ebenen entsprechend den Anforderungen eines bestimmten Systems entwickelt werden. Ebenso können mit anderen Transformationen, wie DCT oder linear mit Zwischenraum angeordneten Unterbändern verschiedene Elter-Kind-Beziehungen definiert werden.
  • Der Prozeß einer Mehrfachauflösungs-Zerlegung kann mit Hilfe eines Filtersystems, wie demjenigen in 4A durchgeführt werden. Ein eingegebenes Signal, das ein eindimensionales Signal mit einer Länge L darstellt, wird mittels Filtereinheiten 401 und 402 tiefpaß- und hochpaß-gefiltert, bevor es durch zwei über Einheiten 403 und 405 mit zwei unterabgetastet wird. Ein unterabgetastetes Ausgangssignal von der Einheit 403 wird durch Einheit 405 und 406 tiefpaß- und hochpaßgefiltert, bevor es über Einheiten 406 bzw. 408 mit zwei unterabgetastet wird. Unterband-Komponenten L und H erscheinen an entsprechenden Ausgängen von Einheiten 407 und 408. In ähnlicher weise wird das Ausgangssignal von der Einheit 405 über Einheiten 409 und 410 tiefpaß- und hochpaßgefiltert, bevor es durch Einheiten 411 bzw. 412 unterabgetastet wird. Unterband-Komponenten L und H erscheinen an entsprechenden Ausgängen der Einheit 411 und 412. Wie vorstehend beschrieben, sind die Filter in einer Ausführungsform der Erfindung, die bei einer Unterband-Zerlegung verwendet sind, digitale Quadratur-Spiegelfilter, um die horizontalen und vertikalen Frequenzbänder in nieder- und hochfrequente Bänder aufzuspalten. 4B stellt eine zweidimensionale Transformation in zwei Ebenen dar. 4C stellt eine zweidimensionale Transformation in zwei Ebenen dar, die mit Hilfe von eindimensionalen Filtern implementiert ist, wie sie in 10 und 11 dargestellt sind. Die eindimensionalen Filter werden in jeder anderen Position angewendet, um eine Berechnung zu vermeiden, die durch Unterabtasten unnötig wird. In einer Ausführungsform benutzen eindimensionale Filter eine Berechnung zwischen einer Tiefpaß- und Hochpaßberechnung gemeinsam.
  • Daher schafft die Erfindung ein System zur Kompression und Dekompression, in welcher überlappte reversible Filter von nicht-minimaler Länge verwendet werden. 4D ist ein Blockdiagramm einer Ausführungsform eines solchen Systems. In 4D wird anfangs eine hierarchische Zerlegung durchgeführt. Die Ergebnisse der hierarchischen Zerlegung werden zur Kompression an einem Kompressor abgegeben. Die durchgeführte Kompression kann eine Vektor-Quantisierung, eine Skalar-Quantisierung, ein Null-Lauf längen-Zählen, ein Huffman-Codieren, usw. sein. Der Ausgangswert des Kompressors verdichtet Daten, die eine verdichtete Version der ursprünglichen eingegebenen Daten darstellt. Ein Dekompressor kann die Daten irgendwann (in der Zukunft) erhalten und die Daten dekomprimieren. Die Erfindung führt dann eine inverse Zerlegung mit Hilfe von überlappten reversiblen Filtern von nicht-minimaler Länge durch, um eine rekonstruierte Version der ursprünglichen Daten zu erzeugen.
  • Die reversiblen Wavelet-Filter der Erfindung können auch beispielsweise in Analyse-Vergrößerungssystemen verwendet werden, wie in 4E dargestellt ist. In 4E wird eine hierarchische Zerlegung an eingegebenen Daten mit Hilfe von überdeckten reversiblen Wavelet-Filtern von nicht-minimaler Länge durchgeführt. Die Analyseeinheit erhält die von den Filtern erzeugten Koeffizienten und klassifiziert sie in Entscheidungen, z.B. nicht vollständig Codieren der Koeffizienten nur relevante Information wird extrahiert. Beispielsweise können in einem Dokumenten-Archiviersystem leere Seiten mit Hilfe nur des gröbsten Tiefpaß-Unterbands erkannt werden. Bei einem anderen Beispiel würde nur Hochpaß-Information von einem ganz bestimmten Unterband verwendet werden, um zwischen Textbild und Bildern natürlicher Szenen zu unterscheiden. Die hierarchische Zerlegung kann zum Registrieren von Mehrfachbildern verwendet werden, so daß eine grobe Registrierung zuerst mit Hilfe von groben Unterbändern gegeben ist. In einer anderen Ausführungsform werden die Koeffizienten einer Vergrößerung oder Filterung unterzogen, auf die eine inverse Zerlegung folgt. Ein scharfes Abgrenzen, Rand-Vergrößerungen, eine Rauschkontrolle, usw. können mit Hilfe einer hierarchischen Zerlegung durchgeführt werden. Folglich schafft die Erfindung eine Wavelet-Transformation für ein Verwenden in gemeinsamen Zeit/Raum- und Frequenz-Domänen Analyse- und Filter-/Vergrößerungssystemen.
  • Eingebettete Bit-Signifikanz-Codierung
  • In der Erfindung werden die Koeffizienten, die als Ergebnis der Wavelet-Zerlegung erzeugt worden sind, entropie-codiert. In der Erfindung werden die Koeffizienten anfangs einem eingebetteten Codieren unterzogen, bei welchem die Koeffizienten in einer visuell signifikanten Reihenfolge geordnet oder, allgemeiner ausgedrückt, bezüglich einer gewissen Fehlermetrik (z.B. einer Verzerrungsmetrik) geordnet werden. Fehler- oder Verzerrungsmetriken enthalten Peak-Fehler und einen mittleren quadratischen Fehler (MSE). Zusätzlich kann ein Ordnen durchgeführt werden, um Präferenz einer Bit-Signifikanz-Raumstelle, Relevanz für ein Datenbasis-Fragen (data base querring) und eine Richtung (vertikal, horizontal, diagonal, usw.) zu geben. Die Erfindung benutzt mehrere eingebettete Codier-Techniken, wobei ein Teil der Koeffizienten auf einer Signifikanz-Ebene mit einer Codiertechnik codiert wird, während die restlichen Koeffizienten mit anderen Techniken codiert werden. In der Erfindung sind ein auf Frequenz basierendes Modellieren und ein gemeinsames bzw. Verbund-Raum/Frequenz-Modellieren zwei verschiedene eingebettete Codiersysteme, die verwendet werden, um die Koeffizienten zu codieren, die durch die Wavelet-Transformation der Erfindung erzeugt worden sind. Das auf Frequenz basierende Modellieren schließt ein Voraussagen einer Anzahl Koeffizienten auf einer höheren Frequenz ein, wenn ein Koeffizient auf einer niedrigeren Frequenz codiert wird. Das gemeinsame Raum/Frequenz-Modellieren hat den Vorteil sowohl der bekannten Frequenzbänder als auch der benachbarten Pixel (oder Daten). Eine Ausführungsform des gemeinsamen Raum/Frequenz-Modellierens wird hier als Horizont-Modellieren. bezeichnet.
  • Die Daten werden anfangs in ein Vorzeichen-Größen-Format formatiert, auf welches Daten folgen, die basierend auf einer Signifikanz zu sortieren sind. Nachdem die Daten bezüglich der vorgegebenen Signifikanz-Metrik sortiert sind, werden die Daten codiert. Sowohl das auf der Frequenz basierende Codieren als auch das Horizont-Codieren kann auf einem Bit-Signifikanz-Ordnen basieren. Aber es können auch verschiedene Verfahren zum Codieren der Ereignisse verwendet werden.
  • Wenn ein digitales Signal x(n) für jedes x(n) mit R-Präzisionsbits dargestellt wird, dann codiert das eingegebettete Codieren der Erfindung das höchstwertige Bit (oder Bits) für jedes x(n) des Signals, dann das nächste signifikante Bit (oder Bits) usw. Beispielsweise kann im Falle einer visuellen definierten Anordnung ein Bild, welches eine bessere Qualität in der Mitte also entlang der Ecken oder nahe der Ränder erfordert (wie einige medizinische Bilder), einem Codieren unterworfen werden, so daß die niederwertigen Bits der zentralen Pixel vor den höherwertigen Bits der Randpixel codiert werden können.
  • Für ein eingebettetes System, das auf einer Bit-Signifikanz-Verzerrungs(Verzeichnungs-)maßnahme beruht, werden binäre Werte der Daten nach der Größe geordnet. Wenn die Werte nicht-negative ganze Zahlen sind, wie es bezüglich der Intensität von Pixels vorkommt, ist die Reihenfolge, die angewendet werden kann, die Bitebenen-Reihenfolge, (beispielsweise von der höchstwertigen zu der niedrigstwertigen Bitebene). In Ausführungsformen, in welchen auch negative Zweierkompliment-Ganzzahlen zugelassen sind, ist die eingebettete Reihenfolge des Vorzeichenbits dasselbe wie das erste Nicht-Null-Bit des Absolutwerts der ganzen Zahl. Daher wird das Vorzeichenbit nicht beachtet, bis ein Nicht-Null-Bit codiert wird. Folglich sind die möglichen Werte für ein Ereignis in dem eingebetteten Signifikanz-System der Erfindung dreifach, bevor das Vorzeichenbit codiert wird. Die dreifachen Ereignisse sind "nicht-signifikant", "positiv-signifikant" und "negativ-signifikant". Beispielsweise ist mit Hilfe einer Vorzeichen Größen-Schreibweise die 16 Bit-Zahl – 7:
    1000000000000111.
  • Auf einer Bitebenen-Basis sind die ersten zwölf Entscheidungen "nicht-signifikant". Das erste 1 Bit kommt bei der dreizehnten Entscheidung vor, die "negativ-signifikant" ist. Nachdem das Vorzeichenbit codiert ist, werden die möglichen Ereignisse auf binäre reduziert, d.h. 0,1. Die 14-ten und 15-ten-Ereignisse sind beide "1".
  • In einer Ausführungsform der Erfindung wird eine Liste verwendet, um eine Spur der Koeffizienten zu erhalten. In einer Ausführungsform unterscheidet ein Einbit Flag, das als das Gruppen-Flag bezeichnet wird, das jedem Koeffizienten zugeordnet ist, Koeffizienten, deren Vorzeichenbit noch nicht codiert worden ist, von den Koeffizienten mit dem bereits codierten Vorzeichenbit. In einer anderen Ausführungsform können zwei oder mehr Listen statt eines Flag-Bits verwendet werden. In anderen Ausführungsformen wird eine einzige Liste ohne ein Flag verwendet.
  • In einer weiteren Ausführungsform werden Listen überhaupt nicht verwendet. Alle Entscheidungen für einen Koeffizienten werden erzeugt und durch Signifikanz kenntlich gemacht, bevor irgendwelche Entscheidungen für den nächsten Koeffizienten erzeugt werden. Hierdurch entfällt die Notwendigkeit, alle Koeffizienten in Listen zu speichern.
  • Codier- und Decodierprozeß der Erfindung
  • Die folgenden Flußdiagramme in 25a bis 30b sind Ausführungsformen der Codier- und Decodierprozesse der Erfindung. 25a und 25b sind ein Flußdiagramm, das den Coder-Transformations- und Modellierprozeß der Erfindung erläutert. In 25a und 25 beginnt der Coder-Transformations- und Modellierprozeß mit Gewinnen von eingegebenen Daten (Verarbeitungsblock 2501). Nach Gewinnen von eingegebenen Daten verwendet die Erfindung ein reversibles Wavelet-Filter (Verarbeitungsblock 2502).
  • Als nächstes wird durch eine Untersuchung bestimmt, ob eine weitere Zerlegungsebene gewünscht wird (Verarbeitungsblock 2503). Wenn eine weitere Zerlegungsebene gewünscht wird, wird die Verarbeitung beim Verarbeitungsblock 2504 fortgesetzt, in welchem an das reversible Filter die LL-Koeffizienten angelegt werden, die sich aus der unmittelbar vorhergehenden Zerlegung ergeben, und die Verarbeitung geht zurück auf den Verarbeitungsblock 2503. Auf diese Weise ermöglicht die Erfindung, eine Anzahl Zerlegungsebenen durchzuführen.
  • Wenn eine weitere Zerlegungsebene nicht gewünscht wird, geht die Verarbeitung auf Verarbeitungsblock 2506 über, in welchem das Gruppen-Flag für jeden Koeffizienten in der A-Gruppe initialisiert wird. Nach einem Initialisieren des Gruppen-Flags wird die Bitebene für den A-Durchgang SA auf die höchstwertige Bitebene (max) gesetzt (Verarbeitungsblock 2507). Als nächstes wird die Bitebene für den B-Durchgang SB auf die nächst höchstwertige Bitebene (max – 1) gesetzt (Verarbeitungsblick 2508).
  • Dann wird bei einer Untersuchung bestimmt, ob die Bitebene für den A-Durchgang SA mit einem auf Frequenz basierenden Modell zu codieren ist (Verarbeitungsblock 2509). Wenn die Bitebene SA zu dem auf Frequenz basierenden Modell zu codieren ist, wird die Verarbeitung beim Verarbeitungsblock 2510 fortgesetzt, wobei jeder Koeffizient mit dem auf Frequenz basierenden Modell und dem Entropie-Code modelliert wird. Wenn andererseits die Bitebene SA nicht mit dem auf Frequenz basierenden Modell zu codieren ist, wird die Verarbeitung beim Verarbeitungsblock 2511 fortgesetzt, in welchem jeder Koeffizient mit einem gemeinsamen Raum/Frequenz-Modell und Entropie-Code modelliert wird.
  • Auf jeden Fall wird die Verarbeitung danach beim Verarbeitungsblock 2512 fortgesetzt, in welchem durch eine Untersuchung bestimmt wird, ob die Bitebene SA größer oder gleich null ist, wodurch angezeigt wird, ob sie die letzte Bitebene ist. Wenn die Bitebene SA größer oder gleich null ist, geht die Verarbeitungsschleife auf den Verarbeitungsblock 2509 zurück. Wenn dagegen die Bitebene SA nicht größer oder gleich null ist, geht die Verarbeitung beim Verarbeitungsblock 2513 weiter, bei welchem durch eine Untersuchung bestimmt wird, ob die Bitebene SB größer oder gleich null ist, so daß der Prozeß festlegt, ob die Bitebene die letzte Bitebene ist, um einen B-Durchlauf vorzunehmen. Wenn die Bitebene SB größer oder gleich null ist, wird die Verarbeitung beim Verarbeitungsblock 2509 fortgesetzt. Wenn jedoch die Bitebene SB nicht größer oder gleich null ist, wird die Verarbeitung beim Verarbeitungsblock 2514 fortgesetzt, wobei codierte Daten entweder auf einem Kanal gesendet oder in einem Speicher gespeichert werden. Nach einem Speichern oder Senden der codierten Daten, endet der Coder-Transformations- und Modellierprozeß der Erfindung.
  • 26a und 26b stellen einen Decoder-Transformations- und Modellier-Prozeß der Erfindung dar. In 26a beginnt der Decoder-Transformations- und Modellierprozeß der Erfindung durch Wiederauffinden codierter Daten (Verarbeitungsblock 2601). Die codieren Daten können von einem Kanal aus oder von einem Speicher oder einem anderen Übertragungssystem empfangen werden. Nach Wiederauffinden der codierten Daten, wird ein Gruppen-Flag für jeden Koeffizienten in der A-Gruppe initialisiert (Verarbeitungsblock 2601). Nach dieser Initialisierung wird die Bitebene für den A-Durchgang SA auf die höchstwertige Bitebene (max) (Verarbeitungsblock 2603) gesetzt, und die Bitebene für den B-Durchgang SB wird auf die nächste Bitebene nach der höchstwertigen (max – 1) (Verarbeitungsblock 2604) gesetzt. Dann wird der Wert jedes Koeffizienten auf einen Anfangswert null gesetzt (Verarbeitungsblock 2605).
  • Nach Initialisieren des Wertes jedes Koeffizienten auf null, wird durch eine Untersuchung bestimmt, ob die Bitebene SA somit einem auf Frequenz basierenden Modell zu decodieren ist oder nicht (Verarbeitungsblock 2606). Wenn die Bitebene SA mit einem auf Frequenz basierenden Modell zu decodieren ist, geht die Verarbeitung beim Verarbeitungsblock 2607 weiter, in welchem jeder Koeffizient mit einem auf Frequenz basierenden Modell und einem Entropie-Code modelliert wird. Wenn die Bitebene SA nicht mit einem auf Frequenz basierenden Modell zu modellieren ist, geht die Verarbeitung beim Verarbeitungsblock 2608 weiter, in welchem jeder Koeffizient mit einem gemeinsamen Raum/Frequenz-Modell und einem Entropie-Decodieren modelliert wird.
  • Nachdem jeder Koeffizient modelliert ist, geht die Verarbeitung beim Verarbeitungsblock 2609 weiter, in welchem die Bitebene SA festlegt, wenn es die letzte Ebene ist, indem geprüft wird, ob sie größer oder gleich null ist. Wenn die Bitebene SA größer oder gleich null ist, wird die Verarbeitung beim Verarbeitungsblock 2606 fortgesetzt. Wenn dagegen die Bitebene SA nicht größer oder gleich null ist, wird durch einen Test bestimmt, ob die B-Durchgang-Bitebene SB größer oder gleich null ist (Verarbeitungsblock 2610), wodurch angezeigt wird, daß es die letzte Bitebene für den B-Durchgang ist. Wenn dem so ist, wird die Verarbeitung beim Verarbeitungsblock 2606 für ein weiteres Decodieren fortgesetzt. Wenn dagegen die Bitebene für den B-Durchgang SB nicht größer oder gleich null ist, wird ein inverses reversibles Filter bei den Koeffizienten für die gröbste Zerlegungsebene angewendet (Verarbeitungsblock 2611). Dann wird durch einen Test bestimmt, ob alle Ebenen invers gefiltert worden sind (Verarbeitungsblick 2612). Wenn dem nicht so ist, wird das inverse reversible Filter wieder an den Koeffizienten auf der gröbsten verbleibenden Zerlegungsebene angelegt (Verarbeitungsblock 2613). Danach wird mit der Verarbeitung auf den Verarbeitungsblock 2612 zurückgegangen, um noch einmal zu testen, ob alle Ebenen invers gefiltert worden sind.
  • Sobald alle Ebenen invers gefiltert worden sind, wird die Verarbeitung beim Verarbeitungsblock 2612 fortgesetzt, in welchem es zu einem Speichern oder einer Übertragung von rekonstruierten Daten kommt.
  • 27a und 27b veranschaulichen eine Ausführungsform des Prozesses zum Modellieren jedes Koeffizienten. Der dargestellte Prozeß veranschaulicht den Modellierprozeß entweder für auf Frequenz basierendes oder JSF-Modellieren und ein Codieren oder Decodieren. Das heißt, jeder der vier Blöcke (2507, 2508, 2607, 2608) können mit dem Modellierprozeß der 28a und 28b implementiert werden. In 27 beginnt ein Anfangsprozeß durch Initialisieren einer Untersuchung, ob das Modellieren in einem Durchgang durchzuführen ist (Verarbeitungsblock 2701).
  • Wenn das Modellieren nicht in einem Durchgang durchzuführen ist, wird durch eine Untersuchung bestimmt, ob die Bitebene SA größer als die Bitebene SB ist (Verarbeitungsblock 2702). Wenn dies nicht ist, dann geht der Prozeß auf den Verarbeitungsblock 2703 über, in welchem ein Flag (do_A_flag) gelöscht wird, um anzuzeigen, daß ein A-Durchgang nicht durchzuführen ist. Wenn die Bitebene SA größer als die Bitebene SB ist, dann wird die Verarbeitung beim Verarbeitungsblock 2704 fortgesetzt, wobei das Flag (do_A_flag) gesetzt wird, um anzuzeigen, daß ein A-Durchgang durchzuführen ist.
  • Entweder nach dem Verarbeitungsblock 2703 oder 2704 wird eine Verarbeitung beim Verarbeitungsblock 2705 fortgesetzt, bei welchem durch eine Untersuchung bestimmt wird, ob die Bitebene SB gleich der Bitebene SA ist. Wenn Bitebenen nicht gleich sind, wird bei der Erfindung ein Flag (do_B_flag) gelöscht, um zu verhindern, daß ein B-Durchgang vorkommt (Verarbeitungsblick 2705), und die Verarbeitung wird danach beim Block 2707 fortgesetzt. Wenn die Bitebene SB gleich der Bitebene SA ist, wird das do_B_flag Flag gesetzt, um anzuzeigen, daß ein B-Durchgang durchzuführen ist (Block 2706), und die Verarbeitung wird danach beim Block 2707 fortgesetzt.
  • Beim Block 2707 wird durch eine Untersuchung bestimmt, ob das A-Durchgangsflag gesetzt wird, und das Null- bzw. Nichtbaum-Modellieren durchzuführen ist. Wenn das Flag anzeigt, daß ein A-Durchgang vorkommt und ein Nullbaum-Modellieren durchzuführen ist, wird ein "bestimmtes/unbestimmtes"-Flag bei dem "unbestimmten"-Zustand für jeden Koeffizienten initialisiert (Block 2708) und die Verarbeitung geht beim Block 2709 weiter. Wenn dagegen entweder das A-Durchgang-Anzeigeflag oder die Nullbaum-Modellieranzeige nicht gesetzt wird, geht die Verarbeitung direkt beim Block 2709 weiter. Im Block 2709 wird der erste Koeffizient auf die Veränderlich C gesetzt.
  • Sobald der erste Koeffizient auf die Veränderliche C gesetzt ist, wird durch eine Untersuchung bestimmt, ob das B-Durchgang-Anzeigeflag gesetzt ist (Verarbeitungsblock 2719). Wenn das B-Durchgang-Anzeigeflag (do_B_flag) gesetzt ist, wird bei der Erfindung ein B-Durchgang beim Koeffizienten C durchgeführt (Block 1710) und die Verarbeitung wird beim Block 2711 fortgesetzt. Wenn dagegen das B-Durchgang-Flag nicht gesetzt ist, dann wird ein B-Durchgang nicht bei C durchgeführt und die Verarbeitung wird direkt beim Block 2711 fortgesetzt.
  • Dann wird bei einer Untersuchung bestimmt, ob das A-Durchgang-Anzeigeflag (do_A_flag) gesetzt ist (Block 2711). Wenn dieses Flag gesetzt ist, dann wird ein A-Durchgang beim Koeffizienten C durchgeführt (Block 2717). Danach wird die Verarbeitung beim Block 2713 fortgesetzt. Wenn das A-Durchgang-Anzeigeflag nicht gesetzt ist, geht die Verarbeitung beim Block 2713 weiter, ohne einen A-Durchgang beim Koeffizienten C durchzuführen.
  • Beim Block 2713 wird durch eine Untersuchung bestimmt, ob der Koeffizient C der letzte Koeffizient ist. Wenn der Koeffizient nicht der letzte Koeffizient ist, wird die Verarbeitung beim Block 1714 fortgesetzt, wobei der nächste Koeffizient der Veränderlichen C zugeordnet wird, und die Verarbeitung beim Block 2719 weitergeht. Wenn jedoch der Koeffizient C der letzte Koeffizient ist, wird die Verarbeitung beim Block 2715 fortgesetzt, wobei eine Untersuchung festlegt, ob das B-Durchgangsflag (do_B_flag) gesetzt ist. Wenn dieses Flag gesetzt ist, wird die Bitebene SB gleich der Bitebene SB – 1 gesetzt (Block 2716) und die Verarbeitung geht beim Block 2717 weiter. Wenn das B-Durchgang-Anzeigeflag nicht gesetzt ist, geht die Verarbeitung beim Block 2717 weiter. Im Block 2717 wird durch eine Untersuchung bestimmt, ob das A-Durchgangsflag gesetzt ist. Wenn es gesetzt ist, dann wird die Bitebene SA gleich der Bitebene SA – 1 gesetzt (Block 2718), und die Verarbeitung endet. Ebenso endet, wenn das A-Durchgangsflag nicht gesetzt ist, die Verarbeitung unmittelbar.
  • In einigen Ausführungsformen kann, ob ein Koeffizient in einer ganz bestimmten Bitebene in der A- oder B-Gruppe ist, ohne Verwenden eines Flag-Bits bestimmt werden. Hierdurch wird ein Speicherbit pro Koeffizient gespart, was bei großen Bildern von Bedeutung ist. Statt dessen wird eine Maske mit Hilfe einer UND-Logik mit einem Koeffizienten verglichen. Wenn das Ergebnis der UND-Logik null ist, dann ist das Bit in der A-Gruppe; andernfalls ist es in der B-Gruppe. Ein Beispiel dieser Masken ist in Tabelle 7 für 8 Bitebenen dargestellt. Diese Masken sind das Zweierkomplement von 2(Bitebene+1) (ohne das Vorzeichenbit).
  • Tabelle 7 – Masken
    Figure 00390001
  • Da unabhängige Masken dem A- bzw. dem B-Durchgang zugeordnet werden können (was hiermit mit MA und MB bezeichnet ist), können soviele A-Durchgänge erforderlichenfalls vor dem entsprechenden B-Durchgang durchgeführt werden. In einer Ausführungsform mit 17 Bitebenen werden drei A-Durchgänge durchgeführt; dann werden gleichzeitig 14 A- und B-Durchgänge und schließlich zwei B-Durchänge durchgeführt. Da A-Durchgangsentscheidungen üblicherweise wirksamer als B-Durchgang-Entscheidungen codiert werden können, kann ein Durchführen von mehreren A-Durchgängen anfangs eine Qualität für eine verlustbehaftete Kompression verbessern.
  • 28a und 28b stellen eine Ausführungsform des Codierers der Erfindung dar, welcher einen verkleinerten Flag-Speicher be nutzt, (wie später noch in der detaillierten Beschreibung ausgeführt wird). In 28a beginnt der Coder-Transformations- und Modellierprozeß durch Erwerben eingegebener Daten (Block 2801). Danach wird bei der Erfindung ein reversibles Wavelet-Filter verwendet (Block 2802). Als nächstes wird bei einer Untersuchung bestimmt, ob eine andere Zerlegungsebene gewünscht wird (Block 2803).
  • Wenn dies gewünscht wird, geht die Verarbeitung beim Block 2804 weiter, bei welchem an das reversible Filter die LL-Koeffizienten angelegt werden, welche sich aus der unmittelbar vorhergehenden Kompression ergaben, und mit der Verarbeitung wird auf Block 2803 zurückgegangen. Auf diese Weise kann bei der Erfindung eine Anzahl Zerlegungsebenen durchgeführt werden. Wenn eine andere Zerlegungsebene nicht gewünscht wird, geht die Verarbeitung beim Block 2805 weiter, wobei die Bitebene für den A-Durchgang SA auf die höchstwertige Bitebene (max) gesetzt wird. Als nächstes wird die Bitebene für den B-Durchgang SB auf die dem höchstwertigen Bit nächstkommende Bitebene (max – 1) gesetzt (Block 2806).
  • Als nächstes wird die Maske MA auf –2(SA+1) gesetzt. (Block 2807). Die Maske MB wird –2(SB+1) gesetzt (Block 2808). Dann wird durch eine Untersuchung bestimmt, ob die Bitebene für den A-Durchgang SA mit einem auf Frequenz basierenden Modell codiert wird (Block 2808). Wenn die Bitebene SA in dem auf Frequenz basierenden Modell zu codieren ist, wird mit der Verarbeitung beim Block 2809 fortgefahren, wo ein Bit jedes Koeffizienten mit dem auf Frequenz basierenden Modell und einem Entropie-Code modelliert wird. Wenn andererseits die Bitebene SA nicht mit dem auf Frequenz basierenden Modell zu codieren ist, wird beim Block 2810 fortgefahren, wobei ein Bit jedes Koeffizienten mit einem gemeinsamen Raum/Frequenz-Modell und einem Entropie-Code modelliert wird.
  • Auf jeden Fall wird die Verarbeitung beim Block 2811 fortge setzt, wo durch eine Untersuchung bestimmt wird, ob die Bitebene SA größer oder gleich null ist, wodurch angezeigt wird, ob es die letzte Bitebene ist . Wenn die Bitebene SA größer oder gleich null ist, wird mit der Verarbeitungsschleife auf Block 2808 zurückgegangen. Wenn dagegen die Bitebene SA nicht größer oder gleich null ist, wird beim Block 2812 fortgefahren, wobei durch eine Untersuchung bestimmt wird, ob die Bitebene SB größer oder gleich null ist, so daß der Prozeß festlegt, wenn die Bitebene die letzte Bitebene ist, um einen Bit-Durchgang vorzunehmen. Wenn die Bitebene SB größer oder gleich null ist, wird beim Block 2808 fortgefahren. Wenn dagegen die Bitebene SB nicht größer oder gleich null ist, wird beim Block 2813 fortgefahren, in welchem codierte Daten entweder auf einem Kanal gesendet oder in einem Speicher gespeichert werden. Nach einem Speichern oder Senden der codierten Daten endet der Coder-Transformations- und Modellierprozeß der Erfindung.
  • 29a und 29b veranschaulichen eine alternative Ausführungsform des Decoder-Transformations- und Modellierprozesses der Erfindung, wobei ein verkleinerter Flag-Speicher verwendet wird. In 29A beginnt der Decoder-Transformations- und Modellierprozeß der Erfindung durch ein Wiederauffinden codierter Daten (Block 2901). Die codierten Daten können von einem Kanal oder einem Speicher oder einem anderen Übertragungssystem erhalten werden. Sobald die Codedaten empfangen sind, wird die Bitebene für den A-Durchgang SA auf die höchstwertige Bitebene (max) (Block 2903) gesetzt, und die Bitebene für den B-Durchgang SB wird auf die der höchstwertigen Ebene am nächsten kommende Bitebene (max – 1) gesetzt (Block 2904). Nach einem Initialisieren des Wertes für jeden Koeffizienten auf null wird der Wert jedes Koeffizienten auf einen Anfangswert null gesetzt (Block 2905). Dann wird die Maske MB auf –2(SB+1) gesetzt (Block 2902), und die Maske MA wird auf –2(SA+1) gesetzt (Block 2915).
  • Dann wird durch eine Untersuchung bestimmt, ob die Bitebene SA mit einem auf Frequenz basierenden Modell zu decodieren ist oder nicht (Block 2906). Wenn die Bitebene SA mit einem solchen Modell zu decodieren ist, wird beim Block 2907 fortgefahren, in welchem ein Bit jedes Koeffizienten mit einem auf Frequenz basierenden Modell und einem Entropie-Decodieren modelliert wird. Wenn die Bitebene SA nicht mit einem auf Frequenz basierenden Modell zu decodieren ist, wird beim Block 2908 fortgefahren.
  • Nachdem jeder Koeffizient modelliert ist, wird beim Block 2909 fortgefahren, in welchem die Bitebene SA festlegt, ob sie die letzte Bitebene ist, indem geprüft wird, ob sie größer oder gleich null ist. Wenn die Bitebene SA größer oder gleich null ist, wird beim Block 2906 fortgefahren. Wenn dagegen die Bitebene SA nicht größer oder gleich null ist, dann wird bestimmt, ob die B-Durchgangs-Bitebene SB größer oder gleich null ist (Block 2910), um dadurch anzuzeigen, daß es die letzte Bitebene für einen B-Durchgang ist. Wenn dem so ist, wird mit der Verarbeitung beim Block 2902 für ein weiteres Decodieren fortgefahren. Wenn dagegen die Bitebene für den B-Durchgang SB nicht größer oder gleich null ist, wird ein inverses reversibles Filter bei den Koeffizienten für die größste Zerlegungsebene angewendet (Block 2911). Dann wird bestimmt, ob alle Ebenen invers gefiltert worden sind (Block 2912) und wenn dem nicht so ist, wird das inverse, reversible Filter wieder an den Koeffizienten auf der gröbsten verbleibenden Zerlegungsebene verwendet (Block 2913). Danach wird mit der Verarbeitung auf Block 2912 zurückgegangen, in welcher wieder einmal bestimmt wird, ob alle Ebenen invers gefiltert sind. Sobald alle Ebenen invers gefiltert sind, wird mit der Verarbeitung beim Block 2912 fortgefahren, bis zu einem Speichern oder einer Übertragung von rekonstruierten Daten.
  • 30a und 30b veranschaulichen eine Ausführungsform des Prozesses zum Modellieren jedes Koeffizienten. Ähnlich wie in 27a und 27b kann der Prozeß der 30a und 30b verwendet werden, um die Modellierschritte in 28a bis 29b zu implementieren. In 30a beginnt ein Initialisierprozeß dadurch, daß zuerst geprüft wird, ob ein A-Durchgang gewünscht wird, und ob SA größer oder gleich 0 ist (Block 3001). Wenn dem so ist, wird das Flag (do_A_flag), da anzeigt, daß ein A-Durchgang durchzuführen ist, gesetzt (Block 3004) und es wird beim Block 3002 fortgefahren. Anderenfalls wird das Flag (do_A_flag) gelöscht (Block 3003).
  • Wenn die Bitebene SA größer als die Bitebene SB ist, dann wird beim Block 3004 fortgefahren, wobei ein Flag gesetzt wird, um anzuzeigen, daß ein A-Durchgang vorgekommen ist. Wenn die Bitebene SA nicht größer als die Bitebene SB ist, dann wird beim Block 3003 fortgefahren, in welchem das Flag, das einen A-Durchgang anzeigt, angenommen wird, um es zu löschen. Nach jedem der Blöcke 3003 oder 3004 wird die Verarbeitung von Block 3002 fortgesetzt, wobei bestimmt wird, ob die Bitebene SB größer oder gleich der Bitebene sA ist, und wenn ein B-Durchgang gewünscht wird. Wenn die Bitebenen nicht gleich sind, wird bei der Erfindung ein Flag (do_B_flag) gesetzt, um zu verhindern, daß ein B-Durchgang vorkommt (Block 3005) und die Verarbeitung geht beim Block 3007 weiter. Wenn die Bitebene SB gleich der Bitebene SA ist, wird das (do_B_flag) gesetzt, um anzuzeigen, daß ein B-Durchgang durchgeführt ist (Block 3006), und danach wird mit der Verarbeitung beim Block 3007 fortgefahren.
  • Beim Block 3007 wird bestimmt, ob das A-Durchgangsflag gesetzt wird, und das Nullbaum-Modellieren durchzuführen ist. Wenn das Flag anzeigt, daß ein A-Durchgang vorgekommen ist und ein Nullbaum-Modellieren durchzuführen ist, wird ein "bestimmtes/unbestimmtes" Flag in dem "unbestimmten" Zustand für jeden Koeffizienten initialisiert, welcher Kinder hat (Block 3008), und es wird beim Block 3009 fortgefahren. Wenn dagegen entweder das A-Durchgang-Anzeigeflag oder die Nullbaum-Modellieranzeige nicht gesetzt sind, wird direkt beim Block 3009 mit der Verarbeitung fortgefahren. Im Block 3009 wird der erste Koeffizient auf die Veränderliche C gesetzt.
  • Sobald der erste Koeffizient der Veränderlichen C zugeordnet worden ist, wird bestimmt, ob das B-Durchgangs-Anzeigeflag gesetzt ist (Block 3019). Wenn das B-Durchgangs-Anzeigeflag (do_B_flag) gesetzt ist, wird bei der Erfindung ein B-Durchgang beim Koeffizienten C durchgeführt (Block 3010) und die Verarbeitung wird beim Block 3011 fortgesetzt. Wenn dagegen das B-Durchgangs-Flag nicht gesetzt ist, dann wird ein B-Durchgang bei der Veränderlichen C nicht durchgeführt, und die Verarbeitung wird direkt beim Block 3011 fortgesetzt.
  • Dann wird bestimmt, ob der A-Durchgangs-Anzeigeflag gesetzt worden ist (Block 3011). Wenn dieses Flag gesetzt worden ist, dann wird ein A-Durchgang beim Koeffizienten durchgeführt (Block 3017). Danach wird beim Block 3013 fortgefahren. Wenn das A-Durchgangs-Anzeigeflag gesetzt ist, wird beim Block 3013 fortgefahren, ohne einen A-Durchgang beim Koeffizienten C durchzuführen. Beim Block 3013 wird bestimmt, ob der Koeffizient C der letzte Koeffizient ist.
  • Wenn der Koeffizient C nicht der letzte ist, wird beim Block 3013 fortgefahren, wobei der nächste Koeffizient der Veränderlichen C durchgeführt wird, und die Verarbeitung beim Block 3019 fortgesetzt wird. Wenn jedoch der Koeffizient der letzte Koeffizient ist, wird beim Block 3015 fortgefahren, wobei bestimmt wird, ob das B-Durchgangsflag (do_B_flag) gesetzt wird. Wenn das B-Durchgangsflag gesetzt ist, wird die Bitebene SB gleich der Bitebene SB – 1 gesetzt (Block 3016) und es wird beim Block 3017 fortgefahren. Wenn das B-Durchgangs-Anzeigeflag nicht gesetzt wird, wird mit der Verarbeitung beim Block 3017 fortgefahren. Beim Block 3017 wird bestimmt, ob das A-Durchgangsflag gesetzt ist. Wenn es gesetzt ist, wird die Bitebene SA gleich der Bitebene SA – 1 gesetzt (Block 3018) und die Verarbeitung beendet. Wenn das A-Durchgangsflag nicht gesetzt ist, wird die Verarbeitung ebenfalls unmittelbar beendet.
  • Koeffizienten-Bäume
  • In einem pyramidalen System können die Koeffizienten in Sätzen gruppiert werden, wobei eine Baumstruktur verwendet wird. Die Wurzel jedes Baumes ist ein rein tiefpaß-gefilterter Koeffizient. 5 veranschaulicht die Baumstruktur eines rein tiefpaß-gefilterten Koeffizienten des transformierten Bildes. Für ein zweidimensionales Signal, wie ein Bild, hat die Wurzel des Baums drei "Kinder" und der Rest der Verzweigungspunkte haben jeweils vier Kinder. Der Baum begrenzt hierarchisch nicht die zweidimensionalen Signale. Beispielsweise hat für ein eindimensionales Signal eine Wurzel ein Kind und nicht mit Wurzel versehene Verzweigungspunkte haben jeweils zwei Kinder. Höhere Dimensionen erfolgen von den ein- und zweidimensionalen Fällen aus.
  • Die Baumstruktur ist auch aus der Arbeitsweise der in 4A bis 4C dargestellten Filter ersichtlich. Die Arbeitsweise der Filterpaare mit einem Unterabtasten bewirkt, daß die vorher beschriebenen Koeffizienten in Beziehung gesetzt werden.
  • Nachdem in der Erfindung die Koeffizienten in ein Vorzeichen-Größen-Format gebracht worden sind, bestimmt ein Kontext-Modell, welches der verschiedenen Codierverfahren zu verwenden ist, um die Koeffizienten weiter zu codieren. Ein auf Frequenz basierendes Codierschema, wie ein Nullbaum-Codieren, codiert wirksam die Signifikanzdaten, die einer vorgegebenen Unterband-Zerlegung für einen spezifizierten Schwellenwert zugeordnet sind. Zusätzlich zum Verwenden von Symbolen, welche die Signifikanz oder Insignifikanz eines einzelnen isolierten Koeffizienten in der zugeordneten Unterband-Zerlegung anzeigen, werden die Eingänge von Insignifikanteneltern für alle Insignifikant-Kinder (mit Größen kleiner oder gleich dem vorgegebenen Schwellenwert) zusammengruppiert und gemeinsam codiert. Diese Bäume werden manchmal auch als Nullbäume bezeichnet. Diese insignifikanten Bäume werden mit einem einzigen dedizierten Symbol codiert, was manchmal als eine Nullbaum-Wurzel bezeichnet wird. Wenn es jedoch einen signifikanten Descendenten gibt, wird der Eingang eines insigni fikanten Koeffizienten mit Hilfe des Symbols für eine "Isolierte Null" codiert. Folglich wird ein Baum mit vier Symbolen (positiv signifikant, negativ signifikant, isoliert null oder Nullbaum-Wurzel) für Entscheidungen codiert, bei welchen das Vorzeichen des Koeffizienten noch nicht codiert worden ist.
  • Ein auf Frequenz basierendes Codieren ist insbesondere in Kompressionssystemen brauchbar, da das gemeinsame Codieren von insignifikanten Bäumen eine kleine Anzahl von Ausgangskoeffizienten zuläßt, um die Insignifikanz einer großen Anzahl von descendenten Koeffizienten vorherzusagen. Da die Eingänge an dem Baum, welcher descendenten Koeffizienten zugeordnet ist, von der Wurzel aus vorhergesagt werden kann, werden keine zusätzlichen Symbole benötigt, um diese Insignifikanz zu codieren. Die Insignifikanz des ganzen Baums wird mit sehr niedrigen Kosten codiert. Folglich bestehen die höherwertigen Bitebenen aus insignifikanten Koeffizienten, von welchen viele weder Nullbaum-Wurzeln noch isolierte Nullen sind (d.h. sie sind Kinder in insignifikanten Bäumen, welche nicht zu codieren sind).
  • Shapiro offenbar ein auf Frequenz basierendes Modell, den sogenannten Nullbaum in US-Patent 5,321,776. Bei Shapiro's-Verfahren werden zwei Listen, eine dominante und eine Subordinatenliste verwendet, um alle Koeffizienten zu speichern. Für jede Signifikanzebene werden zwei Durchgänge gemacht, ein dominanter Durchgang und ein Subordinatendurchgang. In einer Ausführungsform ist das auf Frequenz basierende Modell der Erfindung ein Nullbau.
  • In einer anderen Ausführungsform wird ein auf Frequenz basierendes Modell, das dem Nullbaum entspricht (wie er von Shapiro beschrieben worden ist) verwendet. Statt mehrerer Listen zu verwenden, wird nur eine einzige Liste verwendet, wobei jedes der Listenelemente markiert ist, Teile einer der beiden Gruppen zu sein. Die Trennung von Koeffizienten in eine A- und eine B-Gruppe ist äquivalent der Trennung, die Shapiro mit dominanten bzw. Subordinanten-Listen erreicht. Shapiro's Benutzen von mehreren Listen läßt eine größere Flexibilität beim Ordnen von Koeffizienten in der Subordinatenliste aufgrund einer größeren Software/Hardware-Komplexität zu. Bei dem Nullbaum-Verfahren mit einer einzigen Liste werden zwei Durchgänge, der A- und der B-Durchgang, verwendet, welche äquivalent Shapiro's dominanten Durchgang bzw. dem Subordinaten-Durchgang sind. Das Nullbaum-Modell mit einer einzigen Liste wird nachstehend beschrieben.
  • Das Codiersystem der Erfindung enthält eine Liste der Koeffizienten in Vorzeichen-Größenform in einem Speicher. Jedes Element in der Liste hat eine Ein-Bit-Ebene, welche anzeigt, ob das Element ein Teil der "A-" oder der "B-Gruppe" ist. Am Anfang einer Stufe werden diese Koeffizienten, die noch nicht als signifikant befunden worden sind, kenntlich gemacht, daß sie in der A-Gruppe sind. Diese Koeffizienten, die vorher als signifikant bezüglich der vorherigen größeren Schwellenwerte befunden worden sind, werden kenntlich gemacht als in die B-Gruppe gehörig. Die Liste enthält die Koeffizienten in der Reihenfolge, in welche sie für ein Codieren bearbeitet werden. Am Anfang der allerersten Stufe werden alle Koeffizienten als Teile der A-Gruppe markiert, da kein Koeffizient als signifikant festgelegt worden ist. Wenn Koeffizienten als signifikant oder insignifikant bestimmt werden, werden die Lebel für ihre Eingänge von der ursprünglichen A-Gruppen-Benennung in der B-Gruppen-Benennung geändert. Diese Liste wird anschließend mit zunehmend feineren Schwellenwerten wieder verfeinert. Das heißt, es kommen mehrere Durchgänge durch die Liste vor.
  • In einer Ausführungsform sind die binären Ereignisse, welche den Koeffizienten in der B-Gruppe entsprechen, arithmetisch unter einem Markov-Kontext-Modell nullter Ordnung codiert. Die quaternären Ereignisse, die den Koeffizienten der A-Gruppe entsprechen, werden auch unter einem Markov-Kontext-Modell nullter Ordnung codiert.
  • Die Ordnung von Koeffizienten in der Liste der Erfindung erhält die Baumstruktur, daß kein "Kind" vor seinem Elternteil modelliert werden kann. Folglich ist eine Ordnung, welche die Baumstruktur bewahrt, festgelegt und wird durchwegs verwendet. In einer Ausführungsform werden die Koeffizienten im Speicher in einer Reihenfolge von der ersten verwendeten Speicherstelle aus gespeichert. In der anderen Ausführungsform kann eine verknüpfte Liste verwendet werden.
  • In einer Ausführungsform werden die Koeffizienten in einem eingebetteten Bit-Signifikanz- oder Bitebenen-System codiert. Da die Koeffizienten von der höchstwertigen zu der niedrigstwertigen Ebene codiert werden, muß die Anzahl Bitebenen in den Daten festgelegt werden. Bei der Erfindung ist dies dadurch erreicht, daß eine obere Grenze in den Größen der koeffizienten Werte gefunden wird, die aus den Daten berechnet oder aus der Tiefe des Bildes und den Filterkoeffizienten abgeleitet worden sind. Wenn beispielsweise die obere Grenze 149 ist, dann gibt es 8 Signifikanz-Bits oder 8 Bitebenen.
  • In 6a und 6b ist eine Ausführungsform des eine einzige Liste aufweisenden Nullbaum-Codierprozesses der Erfindung dargestellt. In einer Ausführungsform kann in 6a der Modellierprozeß der 27a und 27b verwendet werden. In 6a beginnt der Prozeß damit, zu testen, ob das Gruppenflag für den Koeffizienten C auf die "A-Gruppe" gesetzt ist (Block 2321). Wenn nicht; dann endet der Prozeß. Wenn dagegen das Gruppenflag für den Koeffizienten C auf die "A-Gruppe" gesetzt ist, wird eine Verarbeitung beim Block 3222 fortgesetzt, wobei bestimmt wird, ob das "bestimmte/unbestimmte" Flag für den Koeffizienten C auf "unbestimmt" gesetzt ist. Wenn das "bestimmte/unbestimmte" Flag für den Koeffizienten nicht auf "unbestimmt" gesetzt ist, endet der Prozeß. Wenn dagegen das "bestimmte/unbestimmte" Flag für den Koeffizienten C auf "unbestimmt" gesetzt ist, wird die Verarbeitung beim Block 3203 fortgesetzt, wobei bestimmt wird, ob das Bit SA des Koeffizienten C eins ist.
  • Wenn das Bit SA des Koeffizienten C nicht eins ist, wird beim Block 3207 fortgefahren. Wenn dagegen das Bit SA des Koeffizienten eins ist, wird mit der Verarbeitung beim Block 3204 fortgefahren, wobei zuerst bestimmt wird, ob das Vorzeichen des Koeffizienten C positiv ist. Wenn das Vorzeichen des Koeffizienten C nicht positiv ist, wird die Entscheidung als "negativ signifikant" in "A-Gruppen"-Kontext(en) codiert (Block 3205) und der Prozeß wird beim Block 3229 fortgesetzt. Wenn das Vorzeichen des Koeffizienten C positiv ist, wird die Entscheidung als "positiv signifikant" in "A-Gruppen"-Kontext(en) codiert (Block 3203), und der Prozeß wird beim Block 3229 fortgesetzt. Beim Block 3229 wird das Gruppenflag für C auf die "B-Gruppe" gesetzt.
  • Beim Block 3207 wird bestimmt, ob das Bit SA für alle die Descendenten (Kinder) des Koeffizienten C null ist. Wenn das Bit SA nicht null ist, wird die Entscheidung als "insignifikant mit signifikanten Kindern" (01) in "A-Gruppe"-Kontext(en) codiert (Block 3208) und der Prozeß endet. Wenn dagegen das Bit SA für alle Descendenten (Kinder) des Koeffizienten C null ist, wird die Entscheidung als "Nullbaum-Wurzel" auf (00) in "A-Gruppen"-Kontext(en) codiert (Block 3209). Danach wird das "bestimmt/unbestimmt" Flag für alle die Descendenten des Koeffizienten C auf "bestimmt" gesetzt (Block 3221) und der Prozeß endet.
  • In einer weiteren Ausführungsform kann der Beendigungstest für den Prozeß darin bestehen, ob ein gewünschtes Kompressionsverhältnis erreicht ist oder nicht. In einer Ausführungsform sind die binären Ereignisse, die sich aus dem B-Durchgang ergeben, unter einen Markov-Quellen-Kontext-Modell nullter Ordnung entropie-codiert. Das 2 Bit-Alphabet (Größe 4), das sich aus dem A-Durchgang ergibt, wird ebenfalls unter einer Markov-Quelle nullter Ordnung durch einen quaternären (Alphabet der Größe 4) arithmetischen Coder codiert.
  • In 6b und 6b (fortgesetzt) ist eine alternative Ausführungsform des Nullbaum-Codierprozesses der einzigen Liste der Erfindung mit Hilfe eines verringerten Flag-Speichers dargestellt. In einer Ausführungsform kann der Prozeß der 6b als der A-Durchgang in dem Prozeß von 30 verwendet werden. In den beiden 6b beginnt der Prozeß damit, zu untersuchen, ob das Ergebnis eines UNDens von Koeffizienten C mit der Maske MA null ist (Block 3201). Wenn dem nicht so ist, endet der Prozeß. Wenn dagegen das Ergebnis des UNDens von Koeffizient C mit der Maske MA null ist, wird die Verarbeitung beim Block 3202 fortgesetzt, wo bestimmt wird, ob das "bestimmte/unbestimmte" Flag für den Elternteil des Koeffizienten C "unbestimmt" gesetzt ist. Wenn das Flag für den Elternteil des Koeffizienten nicht "unbestimmt" gesetzt ist, endet der Prozeß. Wenn jedoch das "bestimmte/unbestimmte" Flag für den Elternteil des Koeffizienten C auf "unbestimmt" gesetzt ist, wird die Verarbeitung beim Block 3203 fortgesetzt, bei welchem bestimmt wird, ob das Bit SA des Koeffizienten C eins ist.
  • Wenn das Bit SA des Koeffizienten C nicht eins ist, wird beim Block 3207 fortgefahren. Wenn dagegen das Bit SA des Koeffizienten C eins ist, wird die Verarbeitung beim Block 3204 fortgesetzt, bei welchem bestimmt wird, ob das Vorzeichen des Koeffizienten C positiv ist. Wenn das Vorzeichen des Koeffizienten C nicht positiv ist, wird die Entscheidung als "negativ signifikant" in "A-Gruppen"-Kontext(en) codiert (Block 3205), und der Prozeß endet. Wenn das Vorzeichen des Koeffizienten C positiv ist, wird die Entscheidung als "positiv signifikant" in "A-Gruppen"-Kontext(en) codiert (Block 3206), und der Prozeß endet. In einer Ausführungsform wird ein quaternärer Coder verwendet, und quaternäre Entscheidungen werden in einem Kontext codiert. In einer anderen Ausführungsform wird ein binärer Coder verwendet und drei Kontexte werden benutzt (z.B. die drei Kontexte sind das erste Bit der Entscheidung, das zweite Bit, bei welchem das erste Bit null ist, und das zweite Bit, wenn das erste Bit eine eins ist).
  • Beim Block 3207 wird bestimmt, ob das Bit SA für alle Descen denten (Kinder) des Koeffizienten C null ist. Wenn das Bit SA nicht null ist, wird die Entscheidung als "insignifikant für signifikante Kinder", "isolierte Null", (01) in "A-Gruppen"-Kontext(en) codiert (Block 3208), und der Prozeß endet. Wenn dagegen das Bit SA für alle Descendenten (Kinder) des Koeffizienten C null ist, wird die Entscheidung als "Nullbaum-Wurzel" (00) in "A-Gruppen"-Kontext(en) codiert (Block 3209). Dann wird das "bestimmte/unbestimmte" Flag für den Koeffizienten C auf "bestimmt" gesetzt (Block 3210). Danach werden das "bestimmte/unbestimmte" Flag für alle die Descendenten des Koeffizienten, welche ihrerseits Descendenten haben, auf "bestimmt" gesetzt (Block 3211), und der Prozeß endet.
  • Decodierschritte
  • In der Erfindung wird ein Decodieren im Sperrschritt (lockstep) mit dem Codieren durchgeführt. In 6c ist eine Ausführungsform des A-Durchgangs-Prozesses für einen Nullbaum-Horizont-Decodierprozeß dargestellt und sie kann in Verbindung mit dem Prozeß von 27 verwendet werden. In 6c beginnt der Prozeß damit, zu untersuchen, ob das Gruppenflag für den Koeffizienten C auf die "A-Gruppe" gesetzt ist (Block 3521). Wenn nicht, endet der Prozeß. Wenn dem jedoch so ist, wird die Verarbeitung beim Block 3528 fortgesetzt, bei welchem bestimmt wird, ob das "bestimmte/unbestimmte" Flag für den Koeffizienten C auf "unbestimmt" gesetzt ist. Wenn nicht, endet der Prozeß. Wenn dem so ist, dann wird der Prozeß beim Block 3502 fortgesetzt, bei welchem eine ternäre Entscheidung in A-Gruppen-Kontext(en) decodiert wird.
  • Dann wird bestimmt, ob die Entscheidung "positiv signifikant" ist (Block 3503). wenn die Entscheidung "positiv signifikant" ist, wird das Vorzeichen des Koeffizienten C auf positiv gesetzt (Block 3505). Die Größe des Koeffizienten wird auf 2SA gesetzt (Block 3507), das Gruppenflag für den Koeffizienten C wird auf die "B-Gruppe" gesetzt (Block 3541), und der Prozeß endet.
  • Wenn die Entscheidung "nicht signifikant" ist (Block 3503), wird bestimmt, ob die Entscheidung "negativ signifikant" ist (Block 3504). Wenn die Entscheidung nicht "negativ signifikant" ist, wird der Prozeß beim Block 3509 fortgesetzt, bei welchem bestimmt wird, ob die Entscheidung eine Nullbaum-Wurzel ist. Wenn die Entscheidung nicht eine Nullbaum-Wurzel ist, endet der Prozeß. Wenn die Entscheidung eine Nullbaum-Wurzel ist, wird das "bestimmte/unbestimmte" Flag für alle Descendenten des Koeffizienten C auf "unbestimmt" gesetzt (Block 3531), und der Prozeß endet.
  • Wenn jedoch bei der Überprüfung des Blockes 3504 festgestellt wird, daß die Entscheidung "negativ signifikant" ist, dann wird das Vorzeichen des Koeffizienten C auf negativ gesetzt (Block 3506), die Größe des Koeffizienten wird auf 2SA gesetzt (Block 3507), das Gruppenflag für den Koeffizienten C wird auf die B-Gruppe gesetzt (Block 3541), und der Prozeß endet.
  • In 6d ist eine alternative Ausführungsform des A-Durchgangs-Prozesses für einen Nullbaum-Horizont-Decodierprozeß mit einem verkleinerten Flag-Speicher dargestellt und sie kann in dem in 30 beschriebenen Prozeß verwendet werden. In 6d beginnt der Prozeß damit, zu untersuchen, ob das Ergebnis des UNDens von Koeffizient C mit der Maske MA null ist (Block 3501). Wenn dem nicht so ist, dann endet der Prozeß. Wenn jedoch das Ergebnis des UNDens von Koeffizient C mit der Maske MA null ist, wird die Verarbeitung beim Block 3508 fortgesetzt, wobei bestimmt wird, ob das "bestimmte/unbestimmte" Flag für den Elternteil von C "unbestimmt" ist. Wenn dem nicht so ist, endet der Prozeß. Wenn dem so ist, dann wird der Prozeß beim Block 3502 fortgesetzt, bei welchem die ternäre Entscheidung in A-Gruppen-Kontext(en) decodiert wird.
  • Dann wird bei einer Überprüfung bestimmt, ob die Entscheidung "positiv signifikant" ist (Block 3503). Wenn die Entscheidung "positiv signifikant" ist, wird das Vorzeichen des Koeffizienten positiv gesetzt (Block 3505), die Größe des Koeffizienten wird auf 2SA gesetzt (Block 3507), und der Prozeß endet.
  • Wenn die Entscheidung nicht "positiv signifikant" ist, wird festgestellt, ob sie "negativ signifikant" ist (Block 3504). Wenn die Entscheidung nicht "negativ signifikant" ist, wird der Prozeß beim Block 3509 fortgesetzt, bei welchem in einer Untersuchung festgestellt wird, ob die Entscheidung eine Nullbaum-Wurzel ist. Wenn die Entscheidung nicht eine Nullbaum-Wurzel ist, endet der Prozeß. Wenn die Entscheidung eine Nullbaum-Wurzel ist, wird das "bestimmte/unbestimmte" Flag für den Koeffizienten C auf "bestimmt" gesetzt (Block 3510), die "bestimmten/unbestimmten" Flags für alle Descendenten von Koeffizienten C, welche ihrerseits Descendenten haben, werden auf "unbestimmt" gesetzt (Block 3511), und der Prozeß endet.
  • Wenn jedoch bei der Kontrolle von Block 3504 festgestellt wird, daß die Entscheidung "negativ signifikant" ist, dann wird das Vorzeichen des Koeffizienten C auf negativ gesetzt (Block 3506), die Größe des Koeffizienten c wird auf 2SA gesetzt (Block 3507), und der Prozeß endet.
  • Alternativen bestehen in der Wahl, die von Shapiro getroffen worden ist, um quaternäre Entscheidungen zu verwenden, um Bäume zu beschreiben. Es können größere Alphabete verwendet werden, um die Kenndaten eines ganzen Baumes weiter zu spezifizieren, wenn die Wurzel des Baumes codiert wird. In einer Ausführungsform werden die folgenden Sätze von hexanären (6-ary) Entscheidungen verwendet.
    • – Insignifikant mit insignifikanten Kindern (Nullbaum-Wurzel)
    • – Insignifikant mit mindestens einem signifikanten Kind
    • – Signifikant, positiv und alle Kinder nicht-negativ
    • – Signifikant, positiv und zumindest ein Kind ist negativ
    • – Signifikant, negativ und alle Kinder sind nicht-positiv
    • – Signifikant, negativ und zumindest ein Kind ist positiv
  • In dieser Ausführungsform wird eine Vorzeichen-Information zusätzlich zu einer Insignifikanz für einen ganzen Baum vorausgesagt. In einer anderen Ausführungsform können Bäume mit anderen Vorzeichen-Zwängen oder mit Größen-Zwängen vorhergesagt werden. Alternative Prädiktoren sind insbesondere brauchbar zum Darstellen von Struktur oder zum Darstellen von Mehrfach-Auflösungsmerkmalen. Mit größeren Alphabeten kann die Verwendung von Markov-Kontexten höherer Ordnung (wie später noch beschrieben wird) nützlich sein.
  • Auf Mehrfach-Durchgang-Liste basierendes, gemeinsames, eingebettetes Raum/Frequenz/Modellieren
  • In der Erfindung codiert ein eingebettetes Frequenz-Codieren, wie das hier beschriebene Horizont-Ordnung-Modellieren, die ternären Ereignisse, die den Koeffizienten in der A-Gruppe entsprechen. Beim Horizont-Codieren sind alle Initialisationen, die den Codierschritten vorausgehen, identisch mit dem auf Frequenz basierenden System. In einer Ausführungsform wird ein binäres Entropie-Codieren mit drei Kontexten "A-Gruppen-Größe", "A-Gruppen-Vorzeichen" und "B-Gruppe" durchgeführt.
  • 7a ist ein Flußdiagramm einer Ausführungsform des A-Durchgangs für einen Horizont-Codierprozeß mit einer einzigen Liste gemäß der Erfindung. Dieser Prozeß kann in dem Prozeß von 27 verwendet werden. In 7a beginnt der A-Durchgang-Prozeß damit, zu untersuchen, ob das Gruppenflag für einen Koeffizienten C auf die "A-Gruppe" gesetzt ist (Block 3111). Wenn nicht, endet der Prozeß. Wenn der Gruppenflag für den Koeffizienten C auf die "A-Gruppe" gesetzt ist, wird die Verarbeitung beim Block 3102 fortgesetzt, bei welchem bestimmt wird, ob das Bit SA des Koeffizienten C eins ist. Wenn das Bits SA des Koeffizienten C nicht eins ist, wird die Entscheidung als insignifikant "0" in dem "A-Gruppen"-Kontext codiert (Block 3103), und der Prozeß endet. Wenn das Bit SA des Koeffizienten C eins ist, dann wird die Verarbeitung bei Block 3104 fortgesetzt, bei welchem bestimmt wird, ob das Vorzeichen von Koeffizienten C positiv ist. Wenn das Vor zeichen des Koeffizienten C positiv ist, wird die Entscheidung "als positiv signifikant" (10) in "A-Gruppen"-Kontext(en) codiert (Block 3106), und der Prozeß wird bei Block 3117 fortgesetzt. Wenn dagegen das Vorzeichen von Koeffizienten C nicht positiv ist, wird die Entscheidung als "negativ signifikant" (11) in "A-Gruppen"-Kontext(en) codiert (Block 3105), und der Prozeß wird bei Block 3117 fortgesetzt. Bei Block 3117 wird das Gruppenflag für Koeffizienten C auf die "B-Gruppe" gesetzt.
  • 7b ist ein Flußdiagramm einer alternativen Ausführungsform des A-Durchgangs für einen Einzellisten-Horizont-Codierprozeß mit Hilfe eines verkleinerten Flag-Speichers. Dieser Prozeß kann in dem Prozeß von 30 verwendet werden. In 7b beginnt der A-Durchgangsprozeß damit, zu untersuchen, ob das Ergebnis des UNDens von Koeffizient C mit der Maske MA null ist (3101). Wenn nicht, dann endet der Prozeß. Wenn das Ergebnis des UNDens von Koeffizient C mit der Maske MA null ist, wird die Verarbeitung beim Block 3102 fortgesetzt, bei welchem in einer Untersuchung bestimmt wird, ob das Bit SA des Koeffizienten C eins ist. Wenn das Bit SA des Koeffizienten C nicht eins ist, wird die Entscheidung als insignifikant (0) in einem "A-Gruppen"-Kontext codiert (Block 3103), und der Prozeß endet. Wenn das Bit SA des Koeffizienten C eins ist, dann wird die Verarbeitung beim Block 3104 fortgesetzt, bei welchem mit einer Untersuchung bestimmt wird, ob das Vorzeichen von Koeffizienten C positiv ist. Wenn das Vorzeichen von Koeffizienten C positiv ist, wird die Entscheidung als "positiv signifikant" (10) in "A-Gruppen"-Kontext(en) codiert (Gruppe 3106) und der Prozeß endet. Wenn dagegen das Vorzeichen von Koeffizienten C nicht positiv ist, wird die Entscheidung als "negativ signifikant" (11) in "A-Gruppen"-Kontext(en) codiert (Block 3105), und der Prozeß endet.
  • Decodierschritte
  • In 7c ist eine Ausführungsform des A-Durchgangs-Prozesses für einen Einzellisten-Horizont-Decodierprozeß der Erfindung dargestellt und sie kann in dem Prozeß von 27 verwendet wer den. In 7c beginnt der Prozeß damit, zu untersuchen, ob das Gruppenflag für den Koeffizienten C auf die "A-Gruppe" gesetzt ist (Block 3411). Wenn nicht, endet der Prozeß. Wenn jedoch das Gruppenflag für den Koeffizienten C auf die "A-Gruppe" gesetzt ist, wird die Verarbeitung beim Block 3402 fortgesetzt, bei welchem die quaternäre Entscheidung in A-Gruppen-Kontext(en) decodiert wird.
  • Dann wird bei der Untersuchung bestimmt, ob die Entscheidung "positiv signifikant" ist (Block 3403). Wenn die Entscheidung "positiv signifikant" ist, wird das Vorzeichen des Koeffizienten C positiv gesetzt (Block 3405), die Größe des Koeffizienten wird auf 2SA gesetzt (Block 3407), das Gruppenflag für den Koeffizienten wird auf die "B-Gruppe" gesetzt (Block 3418) und der Prozeß endet.
  • Wenn die Entscheidung nicht "positiv signifikant" ist, wird bei der Untersuchung festgestellt, ob sie "negativ signifikant" ist (Block 3404). Wenn die Entscheidung nicht "negativ signifikant" ist, endet der Prozeß. Wenn jedoch die Entscheidung "negativ signifikant" ist, dann wird das Vorzeichen des Koeffizienten C negativ gesetzt (Block 3406), die Größe von C wird auf 2SA gesetzt (Block 3407), das Gruppenflag für den Koeffizienten C wird auf "B-Gruppe" gesetzt (Block 3418), und der Prozeß endet.
  • In 7d ist eine alternative Ausführungsform des A-Durchgangs-Prozesses für einen Einzellisten-Horizont-Decodierprozeß mit Hilfe eines verkleinerten Flag-Speichers dargestellt und sie kann in dem Prozeß der 30 verwendet werden. In 7d beginnt der Prozeß damit, zu untersuchen, ob das Ergebnis des UNDens von Koeffizient C mit der Maske MA null ist (Block 3401). Wenn dem nicht so ist, dann endet der Prozeß. Wenn jedoch das Ergebnis des UNDens von Koeffizient C mit der Maske MA null ist, wird die Verarbeitung beim Block 3402 fortgesetzt, bei welchem die ternäre Entscheidung in A-Gruppen-Kontext(en) decodiert wird.
  • Dann wird bei einer Untersuchung bestimmt, ob die Entscheidung "positiv signifikant" ist (Block 3403). Wenn die Entscheidung "positiv signifikant" ist, wird das Vorzeichen des Koeffizienten C positiv gesetzt (Block 3405), die Größe des Koeffizienten wird auf 2SA gesetzt (Block 3407), und der Prozeß endet. Wenn die Entscheidung nicht "positiv signifikant" ist, wird bei einer Untersuchung bestimmt, ob sie "negativ signifikant" ist (Block 3404). Wenn die Entscheidung nicht "negativ signifikant" ist, endet der Prozeß. Wenn jedoch die Entscheidung "negativ signifikant" ist, dann wird das Vorzeichen des Koeffizienten C negativ gesetzt (Block 3406), die Größe von C wird auf 2SA gesetzt (Block 3407) und der Prozeß endet.
  • B-Durchgang sowohl für Nullbaum als auch Horizont
  • In einer Ausführungsform sind der B-Durchgangsprozeß sowohl für den Nullbaum als auch für den Horizont der Erfindung dieselben. Ausführungsformen für den B-Durchgang-Algorithmus für den Codierprozeß und den Decodierprozeß sind in 8a und 8b bzw. 9a und 9b dargestellt.
  • In 8a ist eine Ausführungsform des B-Durchgangsprozesses dargestellt, der teilweise für den Nullbaum und den Einzellisten-Horizont-Codierprozeß verwendet wird und in dem Prozeß der 27 verwendet werden kann. In 8a untersucht der Prozeß anfangs, ob das Gruppenflag für den Koeffizienten C gesetzt ist (Block 3311). Wenn nicht, dann endet der Prozeß. Wenn dagegen das Gruppenflag gesetzt ist, wird die Verarbeitung beim Schritt 3302 fortgesetzt, bei welchem in einer Untersuchung bestimmt wird, ob das Bit SB des Koeffizienten C "1" ist. Wenn das Bit von SB des Koeffizienten C nicht "1" ist, dann wird die Entscheidung als "0" in "B-Gruppen"-Kontext(en) codiert (Block 3303), und der Prozeß endet. Wenn das Bit SB des Koeffizienten C "1" ist, dann wird die Entscheidung als "1" in "B-Gruppen"-Kontext(en) codiert (Block 3304), und der Prozeß endet.
  • In 8b ist eine alternative Ausführungsform des B-Durch gangs-Prozesses dargestellt, welcher teilweise für einen Nullbaum- und Einzellisten-Horizont-Codierprozeß verwendet werden kann und einen verkleinerten Flag-Speicher benutzt, und sie kann in dem Prozeß von 30 verwendet werden. In 8b wird bei dem Prozeß anfangs untersucht, ob das Ergebnis des UNDens des Koeffizienten C mit der Maske MB nicht-null ist (Block 3301). Wenn nicht, dann endet der Prozeß. Wenn dagegen das Ergebnis des UNDens von Koeffizient C mit der Maske MB nicht-null ist, wird die Verarbeitung bei Block 3302 fortgesetzt, bei welchem bestimmt wird, ob das Bit SB des Koeffizienten C "1" ist. Wenn das Bit von SB des Koeffizienten nicht "1" ist, dann wird die Entscheidung als "0" in "B-Gruppen"-Kontext(en) codiert (Block 3303), und der Prozeß endet. Wenn das Bit SB des Koeffizienten C "1" ist, dann wird die Entscheidung als "1" in "B-Gruppen"-Kontext(en) codiert (Block 3304), und der Prozeß endet.
  • In 9a ist eine Ausführungsform des B-Durchgangs-Decodieren der Erfindung dargestellt und sie kann in dem Prozeß der 27 verwendet werden. In 9a wird durch eine Untersuchung anfangs bestimmt, ob das Gruppenflag für Koeffizient C auf die "B-Gruppe" gesetzt ist (Block 3611). Wenn nicht, dann endet der Prozeß. Wenn jedoch das Gruppenflag für Koeffizient C nicht auf die "B-Gruppe" gesetzt ist, dann werden die Entscheidungen in den "B-Gruppen"-Kontext(en) decodiert (Block 3602). Bei einer Untersuchung wird dann unterschieden, ob die Entscheidung eine "1" ist (Block 3603). Wenn die Entscheidung nicht eine 21" ist, endet der Prozeß. Wenn die Entscheidung eine "1" ist, wird das Bit SB von Koeffizient C gesetzt (3604), und der Prozeß endet.
  • In 9b ist eine alternative Ausführungsform des B-Durchgang-Codierens der Erfindung mit Hilfe eines verkleinerten Flag-Speichers dargestellt, und sie kann in den Prozeß von 30 verwendet werden. In 30b wird bei einer Untersuchung anfangs bestimmt, ob das Ergebnis des UNDens von Koeffizient C mit der Maske MB nicht-null ist (Block 3601). Wenn das Ergebnis des UNDens von Koeffizient C mit der Maske MB null ist, dann endet der Prozeß. Wenn jedoch das Ergebnis des UNDens von Koeffizient C mit der Maske MB nicht-null ist, dann werden die Entscheidungen in den "B-Gruppen"-Kontext(en) decodiert (Block 3602). Bei einer Untersuchung wird dann entschieden, ob die Entscheidung eine "1" ist (Block 3603). Wenn die Entscheidung nicht eine "1" ist, dann endet der Prozeß. Wenn die Entscheidung eine "1" ist, dann wird das Bit SB des Koeffizienten C gesetzt (Block 3604), und der Prozeß endet.
  • Mit Hilfe der Verknüpfung von Nullbaum-Ordnungs-Codieren und Horizont-Ordnungs-Codieren schafft die Erfindung ein Bit-Signifikanz-Codieren der Koeffizienten, welche durch die reversiblen Wavelets erzeugt worden sind. Die Verwendung sowohl der A-Gruppen als auch der B-Gruppe und der ternären sowie der binären Ereignisse, welche den "A"- bzw. "B"-Durchgängen entsprechen, ist speziell wichtig im Hinblick auf die Tatsache, daß ein Schalten vorgenommen wird mit Hilfe des Nullbaum-Ordnens auf das Horizont-Ordnens am Ende eines A-Durchgangs. Dies kompensiert die Ineffizienz in der Vorhersage, welche ein Nullbaum-Anordnen der niederwertigen Bits begleitet. Folglich beginnt in der Erfindung das System durch ein Nullbaum-Codieren mit Daten höherwertiger Bits, und nach einer Anzahl Durchgänge durch die Liste, d.h. nachdem eine Anzahl Bitebenen codiert sind, schaltet der Coder der Erfindung, um den Rest der Daten mit Hilfe des Horizont-Codierens zu codieren. Die Anzahl Durchgänge kann statistisch oder adaptiv durch Überwachen der Leistung des Nullbaum-Ordnungs-Codierblocks gewählt werden.
  • Kontext-Modell-Alternativen
  • In einer Ausführungsform werden fünf binäre Kontext-Fächer (bins) verwendet. Dies ist klein im Vergleich mit anderen Systemen, wie JBIG, welches etwas mehr als 1024 Kontexte verwendet. Eine Kompression kann mit Hilfe von mehr Kontext-Fächern verbessert werden. Entscheidungen können an einer räumlichen Adresse, einer Ebene und/oder einer Bitposition konditioniert werden. Entscheidungen können auch durch vorher decodierte Daten kondi tioniert werden, welche nahe bei den aktuellen Daten in einer räumlichen Adresse, einer Ebene und/oder einer Bitposition sind. Im allgemeinen können Markov-Kontexte nullter Ordnung, die vorher beschrieben worden sind, durch Markov-Kontexte höherer Ordnung ersetzt werden.
  • Mehrere Beispiele folgen. Das höchstwertige (und folglich sehr leicht vorhersagbare) Bit jeder Mantisse (B-Gruppendaten in einigen Ausführungsformen) könnte einen anderen Kontext als den Rest der Bits verwenden. Die signifikante/nicht-signifikante Entscheidung könnte in derselben Entscheidung konditioniert werden, die für räumlich nahe, vorherige Koeffizienten in derselben Transformationsebene gemacht worden sind. In ähnlicher Weise könnten die Vorzeichenbits für signifikante Koeffizienten an dem Vorzeichen für räumlich nahe, vorherige Koeffizienten auf derselben Ebene oder auf dem Vorzeichen des Koeffizienten des Elternteils konditioniert werden.
  • Kontextmodell-Verbesserungen können insbesondere wichtig sein, wenn Bilder verdichtet werden, welche eine räumliche oder eine mehrfache Auflösungsstruktur haben. Grauskala-Bilder von Zeilen-Zeichnungen oder Texte sind ein Beispiel von Bildern mit diesen beiden Strukturtypen. Verbesserungen sind auch wichtig zum Verdichten von Dateien, welche bereits mit einem spezifischen Peak-Fehler komprimiert oder dekomprimiert worden sind.
  • Alternative Ausführungsformen der Erfindung
  • Die Erfindung kann auch in Hardware und/oder Software ausgeführt werden. Eine Hardware-Implementation der Erfindung erfordert ein Implementieren der Wavelet-Filter, ein Speicher/Datenfluß-Management, um die Daten für die Filter zu schaffen, ein Kontext-Modell, um das eingebettete Codieren der Erfindung zu steuern, ein Speicher/Daten-Flußmanagement, um die Daten für das Kontext-Modell zu schaffen, und einen binären Entropie-Coder.
  • Wavelet-Filter
  • Eine Ausführungsform des Vorwärts-Wavelet-Filters der Erfindung ist in 10 dargestellt. Das in 10 dargestellte Wavelet-Filter paßt 4 16 Bit Zweier-Komplement-Eingabepixels an, die als x(2) – x(5) dargestellt sind.
  • In 10 verwendet das Tiefpaßfilter mit 2 Anschlüssen "1 1" einen 16 Bit-Addierer 1001. Die Ausgänge sind mit S bzw. D bezeichnet. Der Ausgang des Addierers (S) wird abgeschnitten bei 16 Bits mit Hilfe eines um "1" verschiebenden Blocks 1003, welcher eine Funktion "Teilen durch 2" durchführt, indem dessen 17 Bit-Eingaben um ein Bit nach rechts verschoben werden.
  • Das Hochpaßfilter mit 6 Abgriffen "–1 –1 8 –8 1 1" erfordert die Berechnung von –S0 + 4D1 + S2. Die Funktion S2 – S0 wird mit einer 16 Bit-Subtrahiereinheit 1003 berechnet, welche den Ausgang des Blocks 1003 und des Y0(o) erhält. Der 4D1-Term wird mit Hilfe einer Subtrahiereinheit 1002 und eines um 2 verschiebenden Blocks 1004 berechnet. Der Ausgang, welcher mittels der 16 Bit Subtrahiereinheit 1002 erzeugt wird, wird um zwei Stellen nach links verschoben, um dadurch effektiv dessen Ausgang mit vier zu multiplizieren. Ein Addieren des 4D1-Ausgangs von dem Block 1004 mit dem Ausgang der Subtrahiereinheit 1005 wird durch einen 20 Bit-Addierer 1006 durchgeführt. Der Ausgang des letzten Addierers wird bei 18 Bit mit Hilfe eines um zwei verschiebenden Blocks 1007 abgeschnitten. Der Block 1007 führt eine Teilfunktion durch vier durch, indem dessen 20 eingegebene Bits um zwei Bits nach rechts verschoben werden.
  • Folglich ist die gesamte erforderliche Hardware (wobei Register zum Speichern vorübergehender Ergebnisse nicht mitgezählt sind:
    • • 1 @ 16 Bit-Addierer
    • • 2 @ 16 Bit-Subtrahiereinheiten
    • • 1 @ 19 Bit-Addierer.
  • Hierbei wird ein Verschieben durch das Verdrahten vorgenommen, so daß keine Logik benötigt wird. In anderen Ausführungsformen können für Eingänge einer Größe N ein N-Bit-Addierer, zwei N-Bit-Subtrahiereinheiten und ein (N + 3) Bit-Addierer verwendet werden. Infolge der sehr niedrigen Hardware-Kosten dieser Addierer/Subtrahiereinheiten können erforderlichenfalls parallele Implementationen der Filter verwendet werden.
  • Alternativ kann statt des Subtrahierens X(3) und X(2), X(4) – X(5) berechnet werden und aufbewahrt werden, bis es später als X(2) – X(3) für die nächste Verschiebung oder Anwendung des Filters benötigt wird. Sowohl das Vorwärtsfilter (als auch das nachstehend beschriebene inverse Filter) können durch eine Pipe-Line verbunden werden, um einen höheren Durchsatz zu erreichen.
  • Das inverse Wavelet-Filter ist in 11 dargestellt. Die Eingangssignale von Y0(0) und Y0(2) werden von einer Subtrahiereinheit 1101 subtrahiert. Das Ergebnis der Subtraktion wird nach rechts um zwei Bits durch den Schiebeblock 1102 verschoben. Hierdurch wird effektiv der Ausgang der Subtrahiereinheit um vier geteilt. Eine Subtraktion wird zwischen dem Ausgangssignal des Blocks 1104 und dem Y1(0) Eingangssignal durchgeführt. Das Eingangssignal Y0(1) wird um ein Bit nach links durch den Schiebeblock 1103 verschoben, wodurch das Eingangssignal mit zwei multipliziert wird. Nachdem Y0(1) um 1 verschoben ist, (multipliziert mit zwei), ist das niedrigstwertige (LS-)Bit der verschobene Wert des LS-Bits, das aus dem Ausgangssignal der Subtrahiereinheit 1104 genommen und mit dem 16 Bit-Ausgangssignal vom Block 1103 verknüpft worden ist, um ein Eingangssignal für einen Addierer 1105 und eine Subtrahiereinheit 1106 zu bilden. Der andere Eingang des Addierers 1105 und der Subtrahiereinheit 1106 ist das Ausgangssignal des Subtrahierers 1104. Die Ausgangssignale des Addierers 1105 und des Subtrahierers 1106 werden anschließend abgeschnitten.
  • Die Wahl von zwei Schnittoperationen kann angewendet werden. In beiden Fällen wird der 20 Bit-Wert um 1 (geteilt durch 2) auf einen 19 Bit-Wert verschoben. Für ein System, das nur eine ver lustfreie Kompression durchführt, können die niedrigstwertigen 16 Bits abgegeben werden. (Die restlichen 3 Bits können ignoriert werden). Bei einem verlustbehafteten (oder einem verlustbehafteten/verlustfreien) System wird der 19 Bit-Wert auf null gesetzt, wenn er negativ ist und wird auf 216– 1 gesetzt, wenn er größer als 216– 1 ist; anderenfalls können die niedrigstwertigen 16 Bits abgegeben werden. Für Eingangssignale der Größe N Bits können ein N-Bit-Subtrahierer, ein (N + 2) Bit-Subtrahierer, ein (N + 3)-Bit-Addierer und ein (N + 3) Bit-Subtrahierer verwendet werden, und die Schneideeinheit gibt N Bits ab.
  • Speicher-Verwendung
  • Bezüglich des Speicher- und Datenfluß-Managements für die Wavelet-Filter gemäß der Erfindung ist für Bilder, bei welchen ein Vollbild in einen Speicher eingebracht werden kann, ein Speicher/Datenfluß-Management nicht eine schwierige Ausgabe. Selbst für (1024 × 1024) 16 Bit-medizinische Bilder (z.B. zwei M Bytes in der Größe), die einen Vollbildpuffer erfordern, ist dies für viele Anwendungen vernünftig. Für größere Bilder (z.B. A4, 400 DPI Vierfarben-Bilder sind es über 50 M Bytes hinsichtlich der Größe) ist ein Durchführen der Wavelet-Transformation mit einer begrenzten Größe eines Zeilenpuffer-Speicher wünschenswert.
  • Ein Vollbild-Puffer ist für die Erfindung nicht notwendig, um ein Eindurchlauf-System zu implementieren. Deswegen kann der erforderliche Speicher etwa um einen Faktor 100 (verglichen mit einem Vollbild-Puffer für große Bilder) verkleinert werden. Das Eindurchlauf-System der Erfindung wird später beschrieben.
  • Die in dem Filter-Speicher gespeicherten Daten sind eine Reihe von Koeffizienten, die dem eingebetteten Codieren und dem binären Entropie-Codieren zu unterziehen sind. Das eingebettete Codieren verwendet ein Kontext-Modell, um die Verwendung von auf Frequenz basierendem Codieren oder ein Horizont-Codieren zu koordinieren und um Daten in der richtigen Reihenfolge zu schaffen. Das Kontext-Modell arbeitet in Verbindung mit einem Spei cher-Management-Schema. Für Systeme mit einem Vollbild-Puffer ist ein Vorsehen von Daten in der richtigen Reihenfolge nicht schwierig. Für Systeme ohne einen Vollbild-Puffer schafft das Transformationsdaten-Management-Schema der Ausführungsform der Erfindung mit einem Durchlauf (was unten noch beschrieben wird) Koeffizienten an dem Kontext-Modell, so daß das Kontext-Modell nur Koeffizienten für einen Baum puffern muß. Ein auf Frequenz basierendes Eindurchlauf-Kontext-Modell und ein gemeinsames, einen Durchlauf erledigendes Raum-Frequenz-Kontext-Modell arbeiten zu einer bestimmten Zeit an einem Baum.
  • Die Ergebnisse der Einbettungsoperation der Erfindung bestehen darin, Bitströme für den auf Frequenz basierenden Modelliermechanismus der vorliegenden Erfindung und den gemeinsamen Raum/Frequenz-Modelliermechanismus der Erfindung zu erzeugen. Diese Datenströme werden dann mit Hilfe eines binären Entropie-Codierers codiert.
  • Für ein System mit einem Vollbild-Puffer kann ein binärer Entropie-Codierer (oder irgendein anderer Codierer) verwendet werden. Für Systeme ohne einen Vollbild-Puffer müssen entweder mehrere unabhängige Codierer verwendet werden, oder der Codierer muß in der Lage sein, mehrere unabhängige Codierer zu simulieren. Ebenso wird ein Speicher- oder Kanal-Management gefordert, um eine Speicherspur der Ausgangssignale von den unabhängigen Codierern zu erhalten. Ein Vorteil der Erfindung liegt darin, daß die zu verwaltenden Daten Prioritäten unterworfen (eingebettet) sind. Wenn ausreichend Raum oder Bandbreite während einer Kompression oder einer Übertragung nicht verfügbar ist, können weniger wichtige Daten unterwegs (on the fly) ausrangiert werden, die für eine vernünftige verlustbehaftete Kompression vorgesehen sind.
  • Eindurchgang-System gemäß der Erfindung
  • Die Erfindung schafft eine Eindurchgang-Transformation, die es ermöglicht, die eingegebenen Daten in dem System vollständig zu verarbeiten, wenn sie empfangen werden. In einem solchen System ist die Verarbeitung der Daten nicht abhängig von Daten, welche folgen. Ein Speicher, der erforderlich ist, um ein Bild zu komprimieren, ist unabhängig von der Länge des Bildes. Durch Entfernen die Abhängigkeit, schafft die Erfindung ein System, das verdichtete Daten abgeben kann, bevor alle Daten verarbeitet werden können.
  • A. Datenmanagement für eine Eindurchgang-Transformation
  • 12 stellt einen Abschnitt eines Bildes dar, das in einer Rasteranordnung durch eine Bandform mit Hilfe der Lehren der Erfindung zu verdichten ist. Es wird eine Vierebenen-Zerlegung betrachtet. Jeder Baum hat 24 × 24 = 16 × 16 = 256 Koeffizienten. Da jedoch das Hochpaßfilter der Wavelet-Transformation in der Erfindung überlappt wird, hängt jeder Baum von mehr als 256 eingegebenen Pixels ab. Das Tiefpaßfilter (L) mit zwei Abgriffen "1 1" verursacht nicht irgendein Überlappen; das gesamte Überlappen kommt von dem Hochpaßfilter (H) mit sechs Abgriffen "–1 –1 8 –8 1 1". Das größte Überlappen kommt für die Kaskade von drei Anwendungen des Tiefpaßfilters vor, worauf eine Anwendung des Hochpaßfilters (LLLH) folgt. Drei Anwendungen des Tiefpaßfilters (LLL) erfordern ein Unterstützen von 23 = 8 eingegebenen Pixels. Stützbereiche von (8 × 8) Größenpixels sind in 12 dargestellt. Wenn das Hochpaßfilter in der Kaskade enthalten ist, sind die Stützbereiche (6 × 23) × (6 × 23) = 48 × 48 Pixels. Ein (48 × 48) Pixel-Stützbereich besteht aus 36 (8 × 8) Blöcken, wie in 12 dargestellt ist.
  • Die Koeffizienten in einem in 12 dargestellten (48 × 48) Pixel-Stützbereich sind laufend zu verarbeiten. Der leicht schattierte Bereich des Stützbereichs veranschaulicht Pixel, die bereits in den vorherigen Stützbereichen verwendet worden sind. Der leicht schattierte Bereich, der außerhalb des Stützbereichs ist, veranschaulicht Pixel, die bereits in vorherigen Stützbereichen verwendet worden sind, und in zukünftigen Stützbereichen benötigt werden. Der schwarze (16 × 16) Bereich ist der Teil des Stützbereichs, welcher Pixel enthält, die vorher noch nicht verwendet worden sind. Dementsprechend enthält der dunkel schattierte (16 × 16) Bereich Pixel, die vorher noch nicht verwendet worden sind, aber welche in dem nächsten (48 × 48) Stützbereich verwendet werden. Eine Dreiebenen-(16 × 16) Transformation wird berechnet, die vorherigen Ergebnisse für acht andere (16 × 16) Dreiebenen-Transformationen werden von einem Puffer aus zurückgerufen, und die vierte Transformationsebene wird bei den neun (16 × 16) Dreiebenen-Transformationen angewendet. Das Puffern, das erforderlich ist, um dies zu erreichen, ist groß genug, um die Dreiebenen-Transformations-Koeffizienten für (2 × 2) (Bildbreite + 32)) × 16 Pixel plus genug zu speichern, um ein 16 Zeilen-(ein Band-)Puffer von Pixel zu speichern.
  • 13 ist ein Blockdiagramm einer Ausführungsform der Eindurchgang-Wavelet-Filtereinheit, welche eine Filtersteuereinheit 1301, einen Speicher 1302 und einen Filter 1303 aufweist. Der Filter 1303 weist das in Verbindung mit 10 beschriebene Filter auf. Ein Speicher 1302 betrifft den Speicher, der vorstehend in Verbindung mit 12 beschrieben worden ist, und speichert entweder Pixel oder Koeffizienten. Die Filtersteuereinheit 1301 legt den Datenfluß zwischen dem Speicher 1302 und dem Filter 1303 fest. Die Arbeitsweise der Filtersteuereinheit 1301 wird weiter unten noch beschrieben.
  • In 14 ist eine alternative Wavelet-Filtereinheit dargestellt. Um einen hochschnellen Betrieb zu erreichen, können mehrere Filter verwendet werden. Da in einer Ausführungsform das Filter 1303 4 oder 5 Eingänge erfordert (z.B. inverses Filter, Vorwärtsfilter) und zwei Ausgangssignale erzeugt, könnte die erforderliche Speicher-Bandbreite wesentlich sein. Der Speicher kann mehr Pixel/Koeffizienten pro Speicherstelle haben, mehrere Banken/oder mehrere Ausgänge. Ein Speicher-Interface 1401 verringert die Speicherbandbreite, die erforderlich ist, um schmale Puffer für lokale Daten zu schaffen, die während einer Verarbeitung verwendet worden sind. Eine Speicher-Interface-Einheit 1401 schafft auch ein Multiplexen/Demultiplexen zwischen dem Eingang/Ausgang/I/O des Speichers 1302 und dem Ein-/Ausgang des Filters 1303.
  • Zusätzlich zu der Speicherbandbreite, die zum Filtern erforderlich ist, kann eine zusätzliche Bandbreite für ein Eingeben der Pixel in den Speicher 1302 und für ein Ausgeben der Koeffizienten an das Kontext-Modell erforderlich sein. Wenn Pixel in einer Rasteranordnung eingegeben werden, kann ein zusätzlicher Speicher für den Bandpuffer erforderlich sein.
  • Wenn ein Speicher mehrere Elemente (Pixel oder Koeffizienten) pro Speicherstelle speichert, kann er statt horizontal oder vertikal benachbarte Elemente in einer Spalte oder Zeile zu speichern, die Menge an Speicher-Zugriffen und das erforderliche Puffern verringern, wenn Elemente in einem (N × N) Block, wenn N eine Potenz von 2 ist, dieselbe Speicherstelle benutzen. Dies erlaubt die gleich Bequemlichkeit für vertikale und horizontale Zugriffe.
  • Mehrere Speicherbänke können ebenfalls implementiert werden, so daß sowohl ein horizontaler als auch ein vertikaler Zugriff den gleichen Vorteil von mehreren Bänken haben kann, wie in 15 gezeigt ist. Für den Fall von zwei Bänken kann ein Bankauswählbit, das zum Auswählen einer der Bänke vorgesehen ist, in einer Ausführungsform durch eine exclusive ODER-Behandlung der LS-Bits der horizontalen und vertikalen Koordinaten gebildet werden. Für den Fall von vier Bänken kann das Zweibänke-Auswählbit gebildet werden durch Addieren (Modul 4 mit einem 2 Bit-Adierer) der zwei L S-Bits der horizontalen und vertikalen Koordinaten.
  • In 16 ist eine Eindurchgang-Filteroperation für eine Zweiebenen-Zerlegungs-Implementierung durch die Filtersteuereinheit 1301 (13) dargestellt. Zu Zwecken der Darstellung ist eine Zweiebenen-Beschreibung zuerst erörtert, um die generelle Technik der Erfindung zu erläutern. In anderen Ausführungsformen werden Zerlegungen von drei Ebenen, vier Ebenen oder höheren Ebenen verwendet. Eine Zweiebenen-Zerlegung hat 16 Koeffizienten pro Baum und erfordert eine Berechnung mit 16 Eingangspixel, die vorher noch nicht verwendet worden sind. Die Filterung für einen Koeffizientenbaum wird in 16 oder weniger Zeiteinheiten durchgeführt, um der Eingangs- oder Ausgangsrate zu entsprechen. Für dieses Beispiel werden zwei parallel arbeitende Filter verwendet, um den gewünschten Durchsatz von zwei Filteroperationen pro Zeiteinheit zu erreichen. Für jede örtliche Speicherstelle, an welcher die Vorderkante eines Filters verwendet wird, zeigt 16 eine Zahl, welche die Zeit anzeigt, daß jede Filteroperation durchgeführt wird.
  • Da die Filterreihenfolge durch die Vorderkante des Filters festgelegt ist, erzeugt ein Filtern nicht alle Koeffizienten eines Baumes vor einem Erzeugen eines der Koeffizienten des nächsten Baumes. Das Filtern der Kinder des Baumes kommt vor dem Filtern der Eltern, und ein Tiefpaßfiltern erfolgt vor dem entsprechenden Hochpaßfiltern. Die Filterung arbeitet auf einer A-Gruppe von Koeffizienten, welche dieselbe Anzahl von Koeffizienten eines Typs hat, die einen Baum gibt.
  • Die horizontale Filterung von Ebene 1 wird während der Zeit 0 bis 7 durchgeführt, und die Ergebnisse werden in einem temporären Puffer gespeichert. (Jede räumliche Speicherstelle läuft auf zwei Koeffizienten hinaus.) Während der Zeit 2 bis 9 wird eine vertikale Filterung (mit Hilfe des zweiten Filters) an Daten in dem Puffer und an Daten aus einer vorherigen horizontalen Filterung aus dem Speicher (zweimal pro räumlicher Speicherstelle) durchgeführt. Ein vertikales Filtern kann beginnen, sobald die zweite horizontale Filteroperation beendet ist. Die HH-, HL- und LH-Koeffizienten sind bereit für ein Abgeben an das Kontext-Modell (in der entsprechenden Zeit). Die LL-Koeffizienten werden in der nächsten Ebene verwendet.
  • Mit nur zwei Filtern kann eine horizontale Filterung der Ebene 0 nicht bis zum Zeitpunkt 8 beginnen, wenn die horizontale Filterung der Ebene 1 vollständig ist, was ein Filter verfügbar macht. Ein horizontales Filtern der Ebene 0 kann nicht enden bis zur Zeit 10 eines Zyklus, nachdem die vertikale Filterung der Ebene 0 vollständig ist, wobei alle erforderlichen Daten geprüft werden. Als nächstes kann während der Zeit 11 und 12 die vertikale Filterung der Ebene 1 vorkommen.
  • In der nachstehenden Tabelle 1 ist die Arbeitsweise jedes Filters während jeder Zeiteinheit angegeben. Das Format der Einträge ist Ebenenzahl, horizontal oder vertikal ("H" oder "V") und die räumliche Adresse der Vorderkante. Die Eingänge der vertikalen Filteroperationen werden entweder als Tiefpaß oder als Hochpaß durch einen Index "L" oder "H" identifiziert. Es ist nicht notwendig, ein Filter zum Durchführen einer horizontalen Filterung und das andere zum Durchführen einer vertikalen Filterung zuzuordnen, da beide Filter identisch sind.
  • Tabelle 1
    Figure 00700001
  • Obwohl eine horizontale Filterung der Ebene 1 für die nächste Gruppe von eingegebenen Pixels zur Zeit 11 wieder beginnen kann, würde dies bewirken, daß das Filter schneller arbeitet als die Eingabe- oder Ausgaberate. Stattdessen laufen bei der Erfindung die Filter leer durch, und die nächste Gruppe wird zum Zeitpunkt 16 gestartet. Leerdurchlaufende Filterzyklen können für Spei cherübertragungen verwendet werden. Statt am Ende der Filterung für jede Gruppe vorzukommen, können die Leerlaufzyklen erforderlichenfalls auch über die Filterzyklen verteilt werden.
  • Im Hinblick auf die Erläuterung des Zweiebenen-Falles ist in Tabelle 2 der Dreiebenen-Fall dargestellt. Konzentrationen von zwei oder vier Zeiteinheiten werden verwendet, um die Information auf eine Seite zu übertragen, um dadurch das Lesen zu erleichtern.
  • Tabelle 2
    Figure 00710001
  • In Tabelle 3 ist der Vierebenen-Fall dargestellt. Da es nunmehr 256 Zeiteinheiten pro Koeffizientengruppe sind, ist der Einfachheit halber nur die Filterungsebene und -richtung dargestellt. Tabelle 3
    Figure 00720001
  • Das Ausgangssignal des Filterungs- und Speicheruntersystems der Erfindung ist eine Reihe von Koeffizienten, die einer eingebetteten Bit-Signifikanz-Codierung in der Erfindung unterzogen sind.
  • B-Kontext-Modell für das Eindurchgang-System
  • In einer Ausführungsform der Erfindung wird bezüglich des eingebetteten Bit-Signifikanz-Kontextmodells für das Eindurchgang-System jeder Baum in vier Teilen verarbeitet. Die Wurzel des Baums, der höchste Ebenen-LL-Koeffizient wird durch eine Eindurchgang-Horizont-Ordnungscodierung codiert. Die drei Unterbäume, die mit jeweils in Wurzeln von drei Kindern beginnen, die Koeffizienten der höchsten Ebene HH, HL und LH, werden sowohl durch ein Eindurchgang-Verbund-Raum/Frequenz-Modellieren und ein auf Frequenz basierendes Eindurchgang-Modellieren verarbeitet.
  • Die Koeffizienten werden so codiert, daß codierte Daten vor dem eingebetteten Bit-Signifikanz-Kontext-Modell abgegeben werden können, das auf allen Daten arbeitet.
  • Eindurchgang-Signifikanzbaum
  • Das Nullbaum-Kontext-Modell kann nicht in dem Eindurchgang-System verwendet werden. Ein Nullbaum erfordert eine Liste (oder mehrere Listen), die jeden Koeffizienten enthalten, und ein Nullbaum macht mehrere Durchgänge durch die Liste(n). Ein alternatives, auf Frequenz basierendes Modell, ein Eindurchgang-Signifikanzbaum, erfordert nicht irgendeine Liste, welche alle Koeffizienten enthält. Ein weiterer Unterschied zwischen einem Eindurchgang-Signifikanzbaum und einem Nullbaum ist der, daß ein Signifikanzbaum alle Kinder vor einem Verarbeiten der Eltern verarbeitet, wenn Entscheidungen erzeugt werden, im Unterschied zu einem Nullbaum, welcher zuerst den Elternteil verarbeitet.
  • Das Kontext-Modell der Erfindung ist in Blockdiagrammform in 17 dargestellt. Das Kontextmodell 1700 erfordert zwei Verarbeitungseinheiten, die Vorzeichen-Größeneinheit 109 (1A) und die Signifikanz-Einheit 1702. Das Kontext-Modell 1700 verwendet auch zwei Speicher (mit Speicher-Steuerlogik), einen Größenspeicher 1701 und einen Baumspeicher 1703. Jeder dieser zwei Speichereinheiten kann mit mehreren Speicherbereichen durchgeführt werden, um ein Wechseln während eines hochschnellen Betriebs zuzulassen (d.h. während Daten in einen zu schreiben sind, wird der andere gelesen oder geleert).
  • Der Größenspeicher 1701 ordnet Koeffizienten in dem Baum in einer Reihenfolge, die auf der Signifikanz basiert, wie beispielsweise einer Reihenfolge, die auf deren Größe basiert. Dies wird erreicht durch Aufrechterhalten einer Warteschlange für jede möglich Größe. Die Signifikanz-Einheit 1702 erhält Koeffizienten in der Signifikanz-Reihenfolge (z.B. der Größe) und erzeugt Entscheidungen für einen Coder, welcher den A-Durchgangs-Algorithmus behandelt. Der Baumspeicher 1703 ist mit der Signi fikanz-Einheit 1702 verbunden und eliminiert Nullbäume nach allen Nullen.
  • Bei der folgenden Erörterung ist angenommen, daß die Koeffizienten 18 Bits sind, und daß die Eingangsdaten einer Vierebenen-Zerlegung unterzogen werden. Eine Ausführungsform der Vorzeichen-Größeneinheit 109 ist in 18 dargestellt und setzt eingegebene Koeffizienten in ein Vorzeichen-Größenformat um. Eine Vorzeichen-Größeneinheit 109 ist angeschlossen, um 18 Bits der Koeffizienten aufzunehmen, und enthält einen Inverter 1803, einen Multiplexer (MUX) 1802, einen Prioritätscoder 1803 und einen Zähler 1804. Die Vorzeichen/Größeneinheit 109 gibt eine Signifikanzanzeige (z.B. einen 5 Bit-Wert), die Mantisse des eingegebenen Koeffizienten (z.B. 17 Bits), das Vorzeichen des eingegebenen Koeffizienten (1 Bit) und einen Index vom Zähler 1804 aus (z.B. 7 Bits) ab.
  • MUX 1802 ist vorgesehen, um 17 Bits des Koeffizienten direkt in die Vorzeichen/Größeneinheit 109 und eine invertierte Version der 17 Bits von der Zweierkomplement-Einheit 1801 aus aufzunehmen. Basierend auf dem Vorzeichenbit (Koeffizientenbit 17), das an dem Auswähleingang von MUX 1802 erhalten worden ist, wird der positive der zwei Eingangswerte als die Mantisse abgegeben.
  • Die Vorzeichen/Größeneinheit 109 benutzt einen Prioritätscoder 1803, um das erste signifikante Bit jedes Koeffizienten zu bestimmen. Basierend auf dem ersten signifikanten Bit jedes Koeffizienten kann die Signifikanzebene dem Koeffizienten zugeordnet werden.
  • Der Zähler 1804 wird verwendet, um einen Index dem aktuellen Baumelement zuzuordnen. Für eine Vierebenen-Zerlegung ändert sich der Index von 0 bis 84 (da 1 + 4 + 16 + 64 = 85, die Zahl von Elementen in einem Unterbaum ist). Die eingegebenen Koeffizienten sind eine Baumanordnung, wobei angenommen wird, daß die Eltern zuerst und die Kinder zuletzt in diesem Beispiel sind.
  • Die Koeffizienten sind von verschiedenen Zerlegungsebenen, wie in Tabelle 4 für die Koeffizienten in der Anordnung dargestellt ist.
  • Tabelle 4
    Figure 00750001
  • 19 ist eine Ausführungsform des Blockdiagramms des Größenspeichers 1701. Ein Zähler und ein Speicher ist jeder möglichen Signifikanzebene zugeordnet (außer nichts wird für Null-Koeffizienten benötigt, welche nicht codiert werden müssen). Beispielsweise sind der Zähler 1916 und der Speicher 1936 der Signifikanz-Ebene 17 zugeordnet. In einer Ausführungsform gibt es 16 Signifikanzebenen. Daher gibt es 17 Zähler und 17 zugeordnete Speicher.
  • In einer Ausführungsform muß jeder Speicher 85 Speicherstellen für jeden möglichen Koeffizienten in einem Unterbaum haben (da jeder Unterbaum 85 Koeffizienten enthält), jedoch kann die Speichergröße bis auf eine Potenz von 2 abgerundet werden, wie beispielsweise 128. Jeder Speichereintrag kann ein Vorzeichenbit, einen 7 Bit-Index und N Größenbits enthalten, wobei N die signifikante Ebene ist. Wenn die Verwendung eines Speichers fester Breite gewünscht wird, können Einträge für signifikante 16 und 0, 15 und 1, etc. verknüpft werden, so daß jedes Wort zwei Eintragungen hat, die sich auf 32 Bits belaufen. Natürlich muß bei einer ungeraden Anzahl von Signifikanzebenen ein Wort nur einen Eintrag enthalten, welcher in diesem Beispiel Ebene 7 ist.
  • Vorzeichen-, Index- und Mantisse-Werte, die von der Vorzeichen-Größeneinheit 109 empfangen worden sind, werden in den entsprechenden Speicher an der Adresse geschrieben, welche durch den zugeordneten Speicher-Zähler vorgesehen ist. Der zugeordnete Speicher wird dann inkrementiert, so daß der nächste Koeffizient auf dieser Signifikanzebene an der nächsten Stelle gespeichert werden kann.
  • Der Speicher wird von jedem der Speicher 1920 bis 1926 in abnehmender Signifikanz-Anordnung gelesen. Der Ausgangswert jedes Koeffizienten enthält sein Mantisse, das Vorzeichen und den abgegebenen Index. Wenn der Zähler für die höchste Signifikanzebene bzw. -stufe, (z.B. Stufe 16) nicht-null ist, wird er dekrementiert, und der Speicher wird an dieser Adresse gelesen. Dies wird wiederholt, bis der Zählerwert null ist. Dann wird die nächste Signifikanzstufe (z.B. Stufe 15) betrachtet. Jede Signifikanzstufe wird wiederum betrachtet, bis alle Zähler auf null dekrementiert worden sind, und alle Speicher geleert sind. In einem Realzeit-System kann es wünschenswert sein, zwei Bänke von Zählern und Speichern zu verwenden, so daß eine Bank für das Eingeben und die andere für das Ausgeben verwendet werden kann.
  • Die Zähler adressieren ihren zugeordneten Speicher, so daß ein LIFO (das zuletzt Eingegebene wird zuerst ausgegeben) implementiert ist. Ein LIFO-Speicher ist die korrekte Reihenfolge, wenn Unterbäume in der Reihenfolge von Eltern zuerst eingegeben werden. Andererseits wenn Unterbäume zuerst als Kind eingegeben worden sind, könnte die Operation der Zähler geändert werden, um einen FIFO (zuerst eingeben, zuerst ausgeben) durchführen.
  • 20 ist ein Blockdiagramm einer Ausführungsform einer Signifikanzeinheit 1702. In 20 wird ein Indexzähler 2001 verwendet, um durch jeden Koeffizienten in einem Unterbaum, die Kinder zuerst, durchzugehen. In einer Ausführungsform wird der Indexzähler 2001 bei 84 initialisiert und zählt rückwärts auf null. Ein Signifikanzzähler 2004 beginnt auf der Maximum-Signifikanz stufe, (z.B. 16 in dem Beispiel 9 und zählt jedesmal rückwärts, wenn der Indexzähler 84 einen Zyklus beendet (auf 84 zurückkehrt), so daß der Signifikanzzähler 2004 eine Spur der Bitebene hält. Die Stufe/Ebene eines ganz bestimmten Index wird durch Logik festgelegt (Index auf Stufe 2003), welche die in der vorstehenden Tabelle 4 dargestellte Funktion durchführt.
  • Ein Größenspeicher 1701 erzeugt einen Index, eine Größe und ein Vorzeichen des nächsten Koeffizienten in dem Speicher, welcher durch das Ausgangssignal des Signifikanzzählers 2004 freigegeben ist. Wenn der von dem Speicher angegebene Index derselbe ist, wie der abgegebene Index des Indexzählers 2001, setzt die Äquivalenzlogik 2002 die Nicht-Null-Ausgangsanzeige durch. Die Nicht-Null-Ausgangsanzeige bedeutet, daß der Größenspeicher den nächsten Index usw. bei dem nächsten Zyklus erzeugen sollte. Wenn dies nicht eine Anpassung ist, dann wird eine Nicht-Anpassungsanzeige an einen Diskussionsgenerator 2008 gesendet.
  • In einer Ausführungsform werden drei Flip-Flops, die als Flag 0 (2005) Flag 1 (2006) und Flag 2 (2007) verwendet werden, um eine Speicherspur von Nicht-Null-Daten zu erhalten und werden Zerlegungsebenen 0,1 bzw. 2 zugeordnet. Die Anzahl an erforderlichen Flip-Flops ist eins weniger als die Anzahl Zerlegungsebenen. Die Flip-Flops 2005 bis 2007 werden zuerst gelöscht. Wenn das Nicht-Null-Signal von der Äquivalenzlogik 202 eingesetzt wird, werden alle Flip-Flops in den Flip-Flops 2005 bis 2007, die einer Ebene weniger als der aktuellen Ebene zugeordnet sind, gesetzt. Das Flip-Flop, das der aktuellen Ebene zugeordnet ist, wird gelöscht. Die Ebene ist mit einer Index-Ebenen-Logik 2003 versehen, welche die Ebene entsprechend dem Index von dem Index-Zähler 2001 erzeugt.
  • "Codierte" Flags werden gespeichert (in einigen Ausführungsformen eine Registerdatei), und zwar ein Bit für jeden Index. Wenn das Nicht-Null-Signal durchgesetzt ist, wird das Bit gesetzt, das dem aktuellen Index-Zählerwerts des codierten Flags zugeord net ist. Andernfalls wird, wenn der Signifikanz-Zählerwert der Maximumwert ist, das zugeordnete Bit gelöscht. Andernfalls bleibt der Wert des Bits unverändert. Das bereits codierte Ausgangssignal von einer codierten Flag-Speicherung ist dasselbe wie der neue Wert des Bits, das dem aktuellen Index zugeordnet ist. In einer alternativen Ausführungsform werden die codierten Flags nicht verwendet, und das bereits codierte Signal wird niemals verwendet.
  • In einer Ausführungsform bestimmt ein Entscheidungsgenerator 2008, wenn die aktuelle Ebene 3 ist, und die vorherige Ebene es nicht war. Entsprechend dieser Festlegung setzt der Entscheidungsgenerator 2008 das Startsignal durch, und der gegebene Startpegel ist der vorherige Pegel. Wenn das Nicht-Null-Signal durchgesetzt ist, gibt der Entscheidungsgenerator 2008 eine Entscheidung als "signifikant" ab und gibt auch das Vorzeichen (00,01) und die Mantisse ab. Wenn dagegen der bereits codierte Eingang durchgesetzt ist, wird keine Entscheidung abgegeben. Andernfalls gibt, wenn das Flag-Flip-Flop, das der aktuellen Ebene zugeordnet ist, gesetzt ist, der Entscheidungsgenerator 2008 die Entscheidung als "unwichtig, mit signifikanten Kindern" (10) ab. Andernfalls gibt der Entscheidungsgenerator 2008 die Entscheidung als "unwichtig und Kinder unwichtig" (11) ab und setzt das Nullsignal durch.
  • Um sowohl ein auf Frequenz basierendes Modellieren als auch ein Horizont-Eindurchgang-Verbund-Raum/Frequenz-Modellieren durchzuführen, wird die folgende Änderung an der Signifikanzeinheit 2000 gemacht. Der Signifikanzzähler 2004 wird mit einem Schwellenwert verglichen, und der gesamte Nullausgang wird nur durchgesetzt, wenn der Zählerwert größer als der Schwellenwert ist.
  • In einer Ausführungsform ist die Signifikanz-Kategorie, die in den Baumspeicher 1703 eingegeben worden ist (siehe 21, die nachstehend beschrieben wird) der Ausgangswert des Signifikanzzählers 2004. In dieser Ausführungform des Kontext-Modells (z.B. eine Bit-Signifikanz-Einbettungseinheit) basiert die Signifikanz-Kategorie auf der Anzahl Bitebenen, und es sind siebzehn verschiedene Signifikanz-Kategorien. Dies ist eine beliebige Wahl. In einer anderen Ausführungsform können Bitebenen kombiniert werden, um weniger Signifikanz-Kategorien zu erzeugen. Ebenso kann eine Ebenen-Information zu einer Bitebene-Information hinzugefügt werden, um mehr Signifikanz-Kategorien zu erzeugen. Mehr Signifikanz-Kategorien können eine bessere, verlustbehaftete Kompression schaffen, während weniger eine Hardware-Komplexität reduzieren können.
  • 21 ist ein Blockdiagramm einer Ausführungsform der Baumspeichereinheit der Erfindung. In 21 hat der Speicher 2101 adäquaten Speicherplatz zum Speichern einer Entscheidung und einer Signifikanzanzeige für jede mögliche Entscheidung. In einer Ausführungsform ist für eine Vierebenen-Zerlegung mit 17 Signifikanzstufen die Anzahl Speicherstellen im Speicher 2101 gleich 85 × 17 = 1445.
  • Um auf den Speicher 2101 zuzugreifen, werden Adressen erzeugt. Ein Zähler 2102 ist anfangs null. Wenn der Entscheidungsgenerator 2008 den gesamten Nulleingang nicht durchsetzt, wird der Wert im Zähler 2102 verwendet, um den Speicher zu adressieren. Wenn der Entscheidungsgenerator 2008 den eingegebenen Start durchsetzt, wird der aktuelle Wert des Zählers 2102 in einem der Register 2110 bis 2112 entsprechend der Startebene gespeichert, welche als ein Auswählmechanismus wirkt. Der Zähler 2102 wird dann inkrementiert.
  • Wenn der Entscheidungsgenerator 2008 den gesamten Nulleingang durchsetzt, wird der Wert in dem Register (z.B. 2110, 2111, 2112), das durch die eingegebene Stufe ausgewählt worden ist, verwendet, um den Speicher 2101 zu adressieren; dieser Wert 1 wird in den Zähler 2102 geladen. Dies bewirkt, daß die Speicherstellen, die für unwichtige Kinder eines unwichtigen Elternteils verwendet worden sind, ignoriert wird.
  • Während einer Speicherabgabe wird der Zähler 2102 dekrementiert, um die Adresse der auszugebenden Speicherstelle zu schaffen. Der Ausgangswert von dem Baumspeicher 2100 wird von einem Entropie-Codierer empfangen, der die Entscheidung an der spezifizierten Signifikanz entsprechend codiert. Für eine Realzeit-Operation können zwei Baumspeichereinheiten verwendet werden, so daß eine zum Eingeben verwendet wird, während die andere zum Ausgeben verwendet wird.
  • Koeffizienten-Abgleich
  • In einer Ausführungsform der Erfindung verwendet das Nullbaum-Kontext-Modell ein nicht-normiertes (1 + Z–1) Tiefpaßfilter. Jedoch kann das Nullbaum-Kontext-Modell auch mit normierten Filtern wie (1+Z–1/√2), verwendet werden. Um normierte Filter zu verwenden, kann eine Abgleichseinheit, wie beispielsweise die Ausgleichseinheit 2200 in 22 zwischen dem Vorwärts-Wavelet-Filter 1000 und dem Kontext-Modell 105 verwendet werden, um die Energie zu kompensieren, die von dem nicht-normierten Filter, welches die Kompression verbessert, gewonnen wird (oder anderenfalls verloren wird). Da ein Abgleichen eine nicht-gleichförmige Quantisierung für eine verlustbehaftete Operation zuläßt, kann ein Abgleich die visuelle Qualität von verlustbehafteten Bildrekonstruktionen verbessern. In dem eindimensionalen Fall würden Koeffizienten für jedes Niveau des Baums einen unterschiedlichen Abgleich haben (Divisoren = √2, 2, 2√2, 4, Multiplikatoren = 2√2, 2, √2, 1. In dem zweidimensionalen Fall würden die Teiler 2, 4, 8, 16 und die Multiplikatoren würden 8, 4, 2, 1 sein.
  • Da der Abgleich gerade für ein Gruppieren ähnlicher binärer Entscheidungen für ein Codieren ist, ist ein Verwenden des exakten Normierungswertes nicht kritisch. Der Abgleich muß während des Decodierens invertiert werden, so daß eine Multiplikation und Division erforderlich sind. Ein Verwenden von Faktoren/Divisoren, die Potentenzen von zwei sind, würde ein hardware-effizientes Verschieben zulassen, was stattdessen durchzuführen ist.
  • Wenn Koeffizienten mit einer Potenz von zwei multipliziert werden, sind die weniger signifikanten, hinzugefügten Nullbits nicht zu codieren.
  • Jedoch kann statt die Abgleichfaktoren/Divisoren auf die Potenz von zwei zu begrenzen, eine Annäherung, wie √2 ≈ 1,5 oder √2 ≈ 2 ÷ 1,5 im folgenden Verfahren angewendet werden. Statt Koeffizienten mit dem Faktor/Divisor zu multiplizieren/dividieren, würde nur die "signifikanten" Koeffizienten stattdessen mit dem Faktor/Divisor skaliert. Die Vorzeichen-Größeneinheit kann so, wie in 23 dargestellt, modifiziert werden, um einen "1,5" Prioritätscoder 2301 zu erhalten, welcher auf die Position entweder von (1) dem höchstwertigen "1"-Bit, wenn das dem höchstwertigen Bit nächstfolgende Bit auch "1" ist, oder aber (2) auf eins weniger als auf die Position des höchstwertigen "1"-Bits zurückkehrt. Eine Wahrheitstabelle für einen "1,5", Prioritätscoder für 3 Eingangsbits ist in Tabelle 5 dargestellt.
  • Tabelle 5
    Figure 00810001
  • In Abhängigkeit von der Stufe des Koeffizienten, die durch den augenblicklichen Indexwert angezeigt ist, wählt ein Multiplexer 2302 die Signifikanz entweder des Standard-Prioriätscoders oder des "1,5"-Prioritätscoders aus. Wenn der "1.5"-Abgleich verwendet wird, enthält die Mantisse (N + 1) Bits, wobei N der Signifikanzwert ist. Andererseits enthält die Mantisse N Bits.
  • Eine Abgleicheinheit 200, die einen Multiplexer mit zwei Eingängen aufweist, der als ein Schieberegister wirkt, kann ein Abgleichen mit eins oder zwei durchführen. Wenn dies mit dem 1,5-Abgleich verknüpft wird, der durch die Vorzeichen-Größen-Einheit vorgesehen ist, erlaubt dies Abgleichen von 1,1,5,2 oder 3, welches eine gute Annäherung der gewünschten Multiplikatoren für eindimensionale Signale ist, da die Zahlen einfacher sind (z.B. Potenzen von zwei). (Für zweidimensionale Signale, wie Bilder, sind die Zahlen einfacher). Während eines Decodierens ist das (N + 2)te Bit der Mantisse (welche nicht codiert ist) das Komplement des (N + 1)ten Bit, wenn der "1,5"-Prioritätscoder verwendet wird.
  • Ein Koeffizienten-Abgleich kann verwendet werden für ein Abstimmen des Nullbaums und für eine feinere und nichtgleichförmige Quantisierung. Im Fall von Bildern (zweidimensionalen Signalen) gleicht eine Ausführungform der RTS-Transformation die Koeffizienten dadurch ab, daß das Frequenzband mit den Zahlen multipliziert wird, die in 31 dargestellt sind. Ein Multiplizieren dieser Zahlen läuft auf die RTS-Transformation hinaus, die eine sehr nahe Annäherung an die exakten Rekonstruktions-Wavelets der TS-Transformationen sind. Der Entropie-Coder muß den Abgleichprozeß in Betracht ziehen, um wirksam zu sein.
  • Auf Frequenz basierendes Kontext-Modell bei partiellen Bitebenen
  • Ein alternatives Verfahren des auf Frequenz basierenden Modellierens verwendet partielle Bitebenen oder partielle Signifikanzbits. Eine Implementierung davon ist es, jede Bitebene zweimal zu verarbeiten, so daß die Durchgänge einen A1-Durchgang, einen B1-Durchgang, einen A0-Durchgang und einen B0-Durchgang enthalten. Die Namen der Durchgänge wurden gewählt, da der A1-Durchgang Koeffizienten behandelt, die mit "11" beginnen und der A0-Durchgang, die behandelt, welche mit "11" beginnen.
  • Während des A1-Durchgangs für die Bitebene F ist ein Koeffi zient der A-Gruppe nur signifikant, wenn beide Bits S und S – 1 nicht-null sind. Während des A2-Durchgangs ist ein Koeffizient in der A-Gruppe signifikant, wenn das Bits S nicht-null ist. Da die zwei höchstwertigen Bits bekannt sind, werden der B1- und B0-Durchgang nur benötigt, um S – 1 Bits zu verarbeiten (unter der Annahme, daß S = 0 die niedrigstwertige Bitebene ist).
  • Da alternierende partielle Bitebenen sich um einen Faktor von 1,5 oder 2/1,5 unterscheiden, kann der Abgleich für unterschiedliche Ebenen dadurch erreicht werden, daß die gewünschten partiellen Bitebenen für jede Stufe gruppiert werden. Partielle Bitebenen bewirken ein feineres Modellieren der Daten aufgrund der Elter/Kind-Beziehung, die für das auf Frequenz basierende Kontext-Modell verwendet worden sind. Mehr als zwei Durchgänge, beispielsweise mit vier oder acht Durchgänge, können für ein noch feineres Modellieren verwendet werden. Beispielsweise würde im Fall von vier Durchgängen der All-Durchgang Koeffizienten behandeln, welche mit "111" beginnen. Die anderen Durchgänge würden "110", "101" und "100" behandeln. Ein weniger feines Modellieren könnte auch angewendet werden. Beispielsweise würde ein Durchgang nur mit jeder weiteren Bitebene gemacht. In dem Fall des weniger feinen Modellierens werden mehr Bits von der B-Gruppe codiert.
  • C. Codierer- und Speicher/Kanal-Management für ein Eindurchgang-System
  • Ein Speicher-Management für codierte Daten in dem Eindurchgang-System wird für Systeme dargestellt, welche alle Daten im Speicher speichern, und für Systeme, die Daten an einen Kanal übertragen. In dem Eindurchgang-System müssen codierte Daten so gespeichert werden, daß auf sie in einer eingebetteten kausalen Form zugegriffen werden kann, so daß weniger signifikante Daten weggeworfen werden können, ohne signifikantere Daten zu verlieren. Da codierte Daten variabel lang sind, kann eine dynamische Speicherzuordnung verwendet werden.
  • In einer Ausführungsform der Erfindung benutzt das eingebettete Codierschema 18 Bitebenen und teilt 18 Signifikanzstufen den Daten zu. Der Codierer in einem Eindurchgang-System muß "eingebettet kausal" sein. Das heißt, die Codierereignisse, die einer Bitebene entsprechen, erfordern nicht Information von niederwertigeren Bitebenen. In dem Eindurchgang-Fall werden üblicherweise alle Bits von einem Baum codiert, bevor irgendwelche Bits in dem nächsten Baum codiert werden, so daß Bits unterschiedlicher Signifikanz nicht getrennt werden. Für Codierer, die einen inneren Zustand nicht benutzen, wie Huffman-Codierer, ist dies kein Problem. Doch benutzen viele hochentwickelte Kompressoren mit einer besseren Kompression den internen Zustand.
  • Ein Weg, um diese Schwierigkeit für diese Codierer zu lösen, ist 18 verschiedene Codierer, vielleicht 18Q-Codierer-Chips zu verwenden. Eine Technik, die die Verwendung von 9 Q-Codierer-Chips erlauben würde, ist in dem US-Patent 5,097,261 (Langdon, Jr.), beschrieben, das am 17.3.1992 erteilt worden ist, und den Titel hat: "Datenkompression für ein Aufzeichnen auf ein Aufzeichnungsmedium". Ein besserer Weg benutzt einen in eine Pipeline eingebundenen Codierer, um verschiedene virtuelle Codes mit einem einzigen Codierer durchzuführen, wie es beispielsweise in der US-Patentanmeldung S.N. 08/016,035 beschrieben ist, die am 10.2.1993 eingereicht worden ist und den Titel trägt: "Verfahren und Einrichtung für paralleles Decodieren und Codieren von Daten". In einem solchen Codierer sind die Mehrbit-Generatorzustände für jede Wahrscheinlichkeit jeweils einem Teil der Daten zugeordnet. Beispielsweise könnte jeder von 18 Zuständen einer ganz bestimmten Bitebene für 18 Bit-Daten zugeordnet sein. Register in den Schiebeeinheiten in dem Codierer sind ebenfalls jedem Teil der Daten zugeordnet. In dem Codierer wird kein Verschachteln durchgeführt; jeder Teil der Daten ist einfach bitverpackt.
  • In Ausführungsformen entweder mit mehreren tatsächlichen oder virtuellen Codierern ist ein Speicher jedem Teil der Daten zuge ordnet. Wenn eine Kompression beendet ist, ist eine verknüpfte Liste, welche den zugeordneten Speicher plus des Inhalts des zugeordneten Speichers beschreibt, das Ergebnis. Wenn der Speicher überläuft, bewirkt der Speicher-Zuordnungs-Leitweg, daß wichtigere Daten über weniger wichtige Daten geschrieben werden. Beispielsweise kann das niedrigstwertige Bit von numerischen Daten als erstes überschrieben werden. Die Information, die beschreibt, wie ein Speicher zugeordnet wird, muß zusätzlich zu den codierten Daten gespeichert werden.
  • 24 zeigt ein Beispiel einer dynamischen Speicherzuordnungseinheit für drei Signifikanz-Kategorien. Es werden nur drei Kategorien beschrieben, um ein Unverständlichmachen der Erfindung zu vermeiden; üblicherweise würden eine größere Anzahl Kategorien, wie 8, 16 oder 18 verwendet werden. Eine Registerdatei (oder ein anderer Speicher) hält einen Speicher für jede signifikante Kategorie plus einen weiteren Zeiger, um die nächste freie Speicherstelle anzuzeigen. Der Speicher ist in festes Seitengrößen aufgeteilt.
  • Anfangs zeigt jeder Zeiger, welcher einer Signifikanz-Kategorie zugeordnet ist, auf den Beginn einer Speicherseite, und der freie Zeiger zeigt auf die nächste verfügbare Speicherseite. Codierte Daten, die mit Hilfe einer Signifikanz-Kategorie identifiziert worden sind, werden an der Speicherstelle gespeichert, welche durch den entsprechenden Zeiger adressiert worden ist. Der Zeiger wird dann auf die nächste Speicherstelle inkrementiert.
  • Wenn der Zeiger das Maximum für die augenblickliche Seite erreicht, wird die Adresse des Startes der nächsten freien Seite, die in dem freien Zeiger gespeichert ist, mit der augenblicklichen Seite als Verbindungsglied gespeichert. In einer Ausführungsform könnte der Teil des codierten Datenspeichers oder ein gesonderter Speicher oder eine Registerdatei für diesen Zweck verwendet werden. Dann wird der augenblickliche Zeiger auf die nächste freie Seite gesetzt. Der freie Zeiger wird inkrementiert. Diese Stufen bewirken, daß eine neue Speicherseite einer ganz bestimmten Signifikanz-Kategorie zugeordnet ist und Verbindungsglieder zu Speicherseiten vorgesehen werden, welche Daten für eine gemeinsame Signifikanz-Kategorie enthalten, so daß die Zuordnungsreihenfolge während des Decodierens bestimmt werden kann.
  • Wenn alle Seiten in dem Speicher verwendet sind und es mehr Daten gibt, welche signifikanter sind als die am wenigsten signifikanten Daten in dem Speicher, kann ein Wiederzuordnen des Speichers durchgeführt werden. Drei derartige Zuordnungstechniken werden beschrieben. In allen drei Fällen wird ein Speicher, der dem niedrigstwertigen Daten zugeordnet ist, wieder signifikanteren Daten zugeordnet und es wird nicht mehr der niedrigstwertige Datenwert gespeichert.
  • Zuerst wird die Seite, die von den niedrigstwertigen Daten augenblicklich verwendet wird, einfach den höherwertigen Daten zugeordnet. Da typische Entropie-Coder interne Zustandsinformation verwenden, gehen alle niedrigstwertigen Daten, die vorher auf dieser Seite gespeichert sind, verloren. Zweitens wird die Seite, die gerade von den niedrigstwertigen Daten benutzt wird, den höherwertigen Daten zugeordnet. Im Unterschied zu dem vorherigen Fall wird der Zeiger auf das Ende der Seite gesetzt, und da höherwertige Daten auf der Seite geschrieben sind, wird der entsprechende Zeiger dekrementiert. Dies hat den Vorteil, daß die niedrigstwertigen Daten beim Start der Seite erhalten werden, wenn die höherwertigen Daten nicht die ganze Seite erfordern.
  • Drittens kann statt der aktuellen Seite mit niedrigstwertigen Daten, die wieder zuzuordnen sind, eine Seite von niedrigstwertigen Daten wieder zugeordnet werden. Dies erfordert, daß die codierten Daten für alle Zeiten unabhängig codiert sind, welche die erreichte Kompression verringern können. Es ist auch erfor derlich, daß die uncodierten Daten, die dem Start aller Seiten entsprechen, identifiziert werden. Da eine Seite mit niedrigstwertigen Daten ausrangiert werden kann, ist eine größere Flexibilität in der Quantisierung verfügbar.
  • Die dritte Alternative kann in einem System besonders attraktiv sein, das eine fest Kompressionsrate über Bereiche des Bildes erreicht. Eine genau festgelegte Anzahl Speicherseiten kann einem Bereich des Bildes zugeteilt werden. Ob weniger signifikante Daten erhalten werden oder nicht, kann von der Kompression abhängen, die in einem ganz bestimmten Bereich erreicht worden ist. Der Speicher, der einem Bereich zugeordnet ist, kann nicht vollständig genutzt werden, wenn eine verlustfreie Kompression zugeordnet ist, die weniger als den Speicherplatz erfordert. Ein Erreichen einer fest vorgegebenen Kompressionsrate bei einem Bereich des Bildes kann einen direkten Zugriff auf die Bildbereiche unterstützen.
  • Wenn eine Kompression beendet ist, können die Daten erforderlichenfalls an einen Kanal oder eine Speichereinrichtung in der Signifikanz-Reihenfolge übertragen werden. Die verschiedenen Bindeglieder und Zeichen würden dann nicht mehr länger benötigt werden und es könnte eine mehrfache Durchgang-Decodierung durchgeführt werden. Andererseits können für ein Eindurchgang-Decodieren die Zeiger der Daten der jeweiligen Signifikanz erhalten werden.
  • In einigen Anwendungsfällen können einige Signifikanz-Kategorien nicht verwendet werden. Beispielsweise kann ein 16 Bit-Kompressor bei einem medizinischen 12 Bit-Bit verwendet werden, so daß Signifikanz-Kategorien, die Bitebenen 15...12 entsprechen, unbenutzt sein würden. In Implementationen mit großen Seiten und vielen ungenutzten Signifikanz-Kategorien würde dies Speicherplatz vergeuden (wenn das System nicht im voraus erkennt, daß einige Kategorien nicht benutzt werden), da ihnen kein Speicher zugeordnet werden muß. Eine weitere Lösung bei dieser Speicher vergeudung würde darin bestehen, einen kleinen Speicher (oder ein entsprechendes Register) zu verwenden, um einen Zählwert für jede Signifikanz-Kategorie zu halten. Der Zählwert würde eine Speicherspur der Anzahl von "unbedeutenden, nicht-signifikanten Kinder"-Entscheidungen halten, die auftreten, bevor irgendeine andere Entscheidung vorkommt. Der Speicher, der erforderlich ist, um diese Zählwerte zu speichern, muß gegenüber dem Speicher, der von nicht-genutzten Signifikanz-Kategorien benutzt worden ist, "ausgetauscht" werden.
  • Die Möglichkeit, Daten in jede Seite von beiden Enden her zu schreiben, kann benutzt werden, um den gesamten Speicherinhalt, der in dem System verfügbar ist, besser zu nutzen. Wenn alle Seiten zugeteilt sind, kann eine Seite, die ausreichend freien Platz an dem Ende hat, für eine Benutzung von diesem Ende her zugeteilt werden. Die Möglichkeit, beide Enden einer Seite zu benutzen, muß gegenüber den Kosten ausgeglichen sein, die Speicherspur der Stelle zu halten, an welcher sich die zwei Datentypen begegnen. Dies ist jedoch schwierig für den Fall, daß einer der Datentypen nicht signifikant war und einfach überschrieben werden könnte.
  • Verwenden eines Kanals
  • In einem System, bei welchem Daten in einem Kanal übertragen werden, statt in einem Speicher gespeichert zu werden und Speicherseiten fest vorgegebener Größe verwendet werden (aber nur eine Seite pro Signifikanz-Kategorie benötigt wird), wird dies, wenn eine Speicherseite voll ist, in den Kanal übertragen, und eine Speicherstelle kann wieder benutzt werden, sobald die Daten übertragen sind. In einigen Anwendungsfällen kann die Seitengröße des Speichers die Größe von Datenpaketen sein, die in dem Kanal verwendet werden, oder ein Mehrfaches der Paketgröße sein. (Zu beachten ist, daß in einer Ausführungsform zwei Seiten pro Signifikanz-Stufe verwendet werden können, so daß Daten in eine Seite geschrieben werden können, während die anderen für ein Abgeben an den Kanal gelesen werden).
  • In einigen Kommunikationssystem, beispielsweise ATM (asynchroner Transfer-Mode), können Prioritäten Paketen zugeordnet werden. ATM hat zwei Prioritätsstufen, eine primäre und eine sekundäre. Sekundäre Pakete werden nur übertragen, wenn ausreichende Bandbreite verfügbar ist. Ein Schwellenwert kann benutzt werden, um zu bestimmen, welche Signifikanz-Kategorien primär sind und welche sekundär sind. Ein anderes Verfahren würde darin bestehen, einen Schwellenwert an dem Codierer zu verwenden, um Signifikanz-Kategorien nicht zu übertragen, die weniger signifikant waren als ein Schwellenwert.
  • Verlustbehaftete Kompression mit begrenztem Peakfehler
  • In einigen Anwendungen wird eine perfekte (verlustfreie) Rekonstruktion nicht benötigt. Es kann jedoch wünschenwert sein, eine Kompression mit einem spezifizierten Maximum-Peakfehler zu erreichen. Der Peakfehler soll ±E sein. Dies kann durch Abschneiden der verdichteten Daten erreicht werden, so daß alle weniger signifikanten Daten, die nicht benötigt werden, um die geforderte Genauigkeit zu erreichen, ausgeschieden werden.
  • Ein andere Möglichkeit, um eine Kompression mit einem spezifizierten Maximum-Peakfehler zu erreichen, ist durch einen Wert, der kleiner als oder gleich (2 × E + 1) ist, jedes Pixel des zu komprimierenden Bildes (mit einer ganzzahligen Division) zu teilen. Während einer Rekonstruktion wird jedes Pixel in dem Bild verarbeitet mit: Ausgabepixel = (2 × E + 1) × eingegebenes Pixel + E.(Alternativ hierzu kann, statt E während einer Dekompression hinzuzufügen, eine Subtraktion während einer Kompression vor einem Teilen durch (2 × E + 1) vorkommen).
  • Ein anderer Weg, um eine Kompression mit einem spezifizierten Maximum-Peakfehler zu erreichen, besteht darin, die Division und Multiplikation durch Verschiebungen zu ersetzen. Der Verschiebewert ist ⌊log2(2 × E + 1)⌋. Da ein Verschieben bequem ist, kann eine bessere Fehlerspezifizierung (ein Ersetzen des Peakfehlers) Fehler der Form (–2n < Fehler < –2n) sein.
  • Das Vorhergehende sollte nicht mit einer Quantisierung von Koeffizienten verwechselt werden, was auf dem Gebiet der verlustbehafteten Bildkompression allgemein bekannt ist. In vielen verlustbehafteten Kompressionssystemen (z.B. JPEG) werden Transformations-Domänen-Koeffizienten einem Maximum-Peakfehler zugeordnet, welcher nur indirekt den Peakfehler des Bildes steuert. Eine kritische Differenz besteht darin, daß die Erfindung die Quantisierung an Pixel durchführt, und eine verlustfreie Kompression von Koeffizienten benutzt.
  • Eine Transformations-Domänenquantisierung kann ebenfalls benutzt werden. Viele Koeffizienten haben eine Wirkung auf einen Peakfehler, der sich über mehrere Stufen/Ebenen der Transformation ausbreitet. Es ist leichter die Wirkung auf einen Peakfehler für Hochpaß-Koeffizienten zu bestimmen, die keine Kinder haben.
  • Es wird nunmehr ein eindimensionales Signal betrachtet, welches mit einem Maximum-Peakfehler von ±E zu codieren ist. Dies kann dadurch erreicht werden, daß die feinsten Hochpaß-Koeffizienten in ±2E quantisiert werden. Für ein zweidimensionales Signal können, da es zwei Anwendungen des Hochpaßfilters gibt, die feinsten HH-Koeffizienten mit ±4E quantisiert werden.
  • Eine Alternative, um eine Quantisierung bei dem eingegebenen Bild anzuwenden, besteht darin, die Entscheidungen in dem Entropie-Coder zu steuern. Ein Beispiel hierfür ist das folgende. Für jeden Koeffizienten wird, wenn ein Einstellen des Koeffizienten auf null den Fehler in irgendeinem Pixel nicht hervorrufen würde, das durch diesen Koeffizienten beeinflußt worden ist, um den Maximum-Fehler zu überschreiten, der Koeffizient null gesetzt. In einigen Implementierungen werden nur ganz bestimmte Koeffizienten geprüft, vielleicht nur die Wechselstrom-Koeffizienten, welche keine Kinder haben. Koeffizienten können mit einer Strategie betrachtet werden, bei der einer zu einer bestimmten Zeit betrachtet wird. Andere Strategien können kleine Gruppen von Koeffizienten berücksichtigen und auswählen, um die größtmögliche Untermenge der Gruppen zu null zumachen.
  • BEISPIELSCODE FÜR RTS-TRANSFORMATION (VORWÄRTS) – EINE EBENE/STUFE ZERLEGUNG
    Figure 00920001
  • BEISPIELSCODE FÜR RTS-TRANSFORMATION (INVERS) – EINE EBENE/STUFE ZERLEGUNG
    Figure 00920002
  • ZWEI EBENEN/STUFEN ZERLEGUNG-RTS-TRANSFORMATION (VORWÄRTS)
    Figure 00930001
  • ZWEI EBENEN/STUFEN ZERLEGUNG-RTS-TRANSFORMATION (INVERS)
    Figure 00930002
  • Figure 00940001
  • 1A
    • 101
    BILDEINGABE
    102
    REVERSIBLE WAVELETS
    103
    BIT-SIGNIFIKANZ-EINBETTUNG
    104
    ENTROPIE-CODER
    107
    CODESTROM
  • 1B
    • 108
    SCHALTER
    108a
    WAVELET-KOEFFIZIENTEN
    109
    VORZEICHEN/GRÖßENFORMAT
    105
    AUF FREQUENZ BASIERENDES KONTEXT-MODELL
    106
    GEMEINSAMES RAUM/FREQUENZ-KONTEXT-MODELL
    110
    BITS ZU CODIERER
  • 2B
    • 1
    EINGEGEBENE DATEN
    2
    REVERSIBLE FILTER NICHT-MINIMALER LÄNGE (VORWÄRTS)
    3/4
    KOEFFIZIENTEN
    5
    REVERSIBLE FILTER NICHT-MINIMALER LÄNGE (UMKEHR)
    6
    REKONSTRUIERTE DATEN
  • ZU 4D/4E
    • 40
    HIERARCHISCHE ZERLEGUNG MIT HILFE ÜBERLAPPTER REVERSIBLER
    FILTER NICHT-MINIMALER LÄNGE
    41
    KOMPRESSOR
    42
    DEKOMPRESSOR
    43
    INVERSE ZERLEGUNG MIT HILFE VON FILTERN
    44
    ANALYSEEINHEIT
    45
    ENTSCHEIDUNGEN
    KLASSIFIKATIONEN
    46
    VERGRÖßERUNG ODER FILTEREINHEIT
    47
    INVERSE ZERLEGUNG MIT HILFE VON FILTERN
  • 6a
    • 3221
    IST DAS GRUPPENFLAG FÜR C "A-GRUPPE"?
    3222
    IST DAS "BESTIMMTE/UNBESTIMMTE" FLAG FÜR C "UNBESTIMMT"?
    3203
    IST BIT SA VON C EINS?
    3294
    IST VORZEICHEN VON C POSITIV?
    3205
    CODEENTSCHEIDUNG "NEGATIV SIGNIFIKANT" IN "A-GRUPPEN"-
    KONTEXT(E)
    3206
    CODEENTSCHEIDUNG "POSITIV SIGNIFIKANT" IN "A-GRUPPE"-
    KONTEXT(E)
    3229
    GRUPPENFLAG FÜR C IN B-GRUPPE SETZEN
  • 6a(FORTGESETZT)
    • 3207
    IST FÜR ALLE DESCENDENTEN (KINDER) VON C BIT SA NULL?
    3208
    CODEENTSCHEIDUNG "UNWICHTIG BEI SIGNIFIKANTEN KINDERN" (01)
    IN "A-GRUPPE"-KONTEXT(E)
    3209
    CODEENTSCHEIDUNG "NULLBAUM-WURZEL" (00) IN "A-GRUPPE"-
    KONTEXT(E)
    3221
    "BESTIMMTES/UNBESTIMMTES" FLAG FÜR ALLE DESCENDENTEN AUF
    "BESTIMMT" SETZEN
  • 6b
    • 3201
    IST C UND MA NULL?
    3202
    IST DAS "BESTIMMTE/UNBESTIMMTE" FLAG FÜR DEN ELTERNTEIL VON
    C "UNBESTIMMT"?
    3203
    IST BIT SA VON C EINS?
    3204
    IST VORZEICHEN VON C POSITIV?
    3205
    CODEENTSCHEIDUNG "NEGATIV SIGNIFIKANT" IN "A-GRUPPE"-
    KONTEXT(E)
    3206
    CODEENTSCHEIDUNG "POSITIV SIGNIFIKANT" IN "A-GRUPPE"-
    KONTEXT(E)
  • ZU 6b (FORTSETZUNG)
    • 3207
    FÜR ALLE DESCENDENTEN (KINDER) VON C IST BIT S NULL?
    3208
    CODEENTSCHEIDUNG "UNWICHTIG BEI SIGNIFIKANTEN KINDERN" (01)
    IN "A-GRUPPE"-KONTEXT(E)
    3209
    CODEENTSCHEIDUNG "NULLBAUM-WURZEL" (00) IN "A-GRUPPE"-
    KONTEXT(E)
    3210
    "BESTIMMTES/UNBESTIMMTES" FLAG FÜR C AUF "BESTIMMT" SETZEN
    3211
    "BESTIMMTES/UNBESTIMMTES" FLAG FÜR ALLE DESCENDENTEN VON
    C, WELCHE IHRERSEITS DESCENDENTEN HABEN, AUF "BESTIMMT"
    SETZEN
  • 6c
    • 3521
    IST DAS GRUPPENFLAG FÜR C "A-GRUPPE"?
    3528
    IST DAS "BESTIMMTE/UNBESTIMMTE" FLAG FÜR C "UNBESTIMMT"?
    3502
    ENTSCHEIDUNG IN A-GRUPPEN-KONTEXT DECODIEREN
    3503
    IST ENTSCHEIDUNG "POSITIVE SIGNIFIKANZ"?
    3504
    IST ENTSCHEIDUNG "NEGATIVE SIGNIFIKANZ"?
    3505
    VORZEICHEN VON C AUF POSITIV SETZEN
    3506
    VORZEICHEN VON C AUF NEGATIV SETZEN
    3507
    GRÖßE VON C AUF 2**Sa SETZEN
    3510
    IST ENTSCHEIDUNG "NULLBAUM-WURZEL"?
    3531
    "BESTIMMTES/UNBESTIMMTES" FLAG FÜR ALLE DESCENDENTEN RUF
    "BESTIMMT" SETZEN
    3541
    GRUPPENFLAG FÜR C IN B-GRUPPE SETZEN
  • 6d
    • 3501
    IST C UND MA NULL?
    3508
    IST DAS "BESTIMMTE/UNBESTIMMTE" FLAG FÜR DEN ELTERNTEIL VON
    C "UNBESTIMMT"?
    3502
    ENTSCHEIDUNG IN A-GRUPPEN-KONTEXT DECODIEREN
    3503
    IST ENTSCHEIDUNG "POSITIVE SIGNIFIKANZ"?
    3504
    IST ENTSCHEIDUNG "NEGATIVE SIGNIFIKANZ"?
    3509
    IST ENTSCHEIDUNG "NULLBAUM-WURZEL"?
    3505
    VORZEICHEN VON C AUF POSITIV SETZEN
    3506
    VORZEICHEN VON C AUF NEGATIV SETZEN
    3507
    GRÖßE VON C AUF 2**Sa SETZEN
    3510
    "BESTIMMTES/UNBESTIMMTES" FLAG FÜR C AUF "BESTIMMT" SETZEN
    3511
    "BESTIMMTES/UNBESTIMMTES" FLAG FÜR ALLE DESCENDENTEN VON
    C, WELCHE IHRERSEITS DESCENDENTEN HABEN, AUF "BESTIMMT"
    SETZEN
  • 7a
    • 3111
    IST DAS GRUPPENFLAG FÜR C "A-GRUPPE"?
    3102
    IST BIT SA VON C EINS?
    3103
    ENTSCHEIDUNG "UNWICHTIG" IN "A-GRUPPE"-KONTEXT CODIEREN
    3104
    IST VORZEICHEN VON C POSITIV?
    3105
    ENTSCHEIDUNG "NEGATIV SIGNIFIKANT" (11) IN "A-GRUPPE"-
    KONTEXT(E) CODIEREN
    3106
    ENTSCHEIDUNG "POSITIV SIGNIFIKANT" (10) IN "A-GRUPPE"-
    KONTEXT(E) CODIEREN
    3117
    GRUPPENFLAG FÜR C IN B-GRUPPE SETZEN
  • 7b
    • 3101
    IST C UND MA NULL?
    3102
    IST BIT SA VON C EINS?
    3103
    ENTSCHEIDUNG "UNWICHTIG" (0) IN "A-GRUPPEN"-KONTEXT CODIEREN
    3104
    IST VORZEICHEN VON C POSITIV?
    3105
    ENTSCHEIDUNG "NEGATIV SIGNIFIKANT" (11) IN "A-GRUPPEN"-
    KONTEXT(E)
    3106
    ENTSCHEIDUNG "POSITIV SIGNIFIKANT" (10) IN "A-GRUPPE"-
    KONTEXT(E)
  • 7c/d
    • 3401
    IST C UND MA NULL?
    3411
    IST DAS GRUPPENFLAG FÜR C "A-GRUPPE"?
    3402
    TERNERE ENTSCHEIDUNG IN "A-GRUPPE"-KONTEXTEN CODIEREN
    3403
    IST ENTSCHEIDUNG "POSITIVE SIGNIFIKANZ"?
    3404
    IST ENTSCHEIDUNG "NEGATIVE SIGNIFIKANZ"?
    3405
    VORZEICHEN VON C AUF POSITIV SETZEN
    3406
    VORZEICHEN VON C AUF NEGATIV SETZEN
    3407
    GRÖßE VON C AUF 2**Sa SETZEN
    3418
    GRUPPENFLAG FÜR C AUF "B-GRUPPE" SETZEN
  • 8a/b
    • 3301
    IST C UND MB NULL?
    3311
    IST DAS GRUPPENFLAG FÜR C "B-GRUPPE"?
    3302
    IST BIT SB VON C "1"?
    3304
    ENTSCHEIDUNG "1" IN "B-GRUPPE"-KONTEXT CODIEREN
    3303
    ENTSCHEIDUNG "0" IN "B-GRUPPE"-KONTEXT CODIEREN
  • 9a/B
    • 3601
    IST C UND MB NICHT NULL?
    3611
    IST DAS GRUPPENFLAG FÜR C "B-GRUPPE"?
    3601
    ENTSCHEIDUNG IN "B-GRUPPEN"-KONTEXT DECODIEREN
    3603
    ENTSCHEIDUNG "1"?
    3604
    BIT Sb VON C SETZEN
  • 17
    • 109
    VORZEICHEN/GRÖßE
    1701
    GRÖßENSPEICHER
    702
    SIGNIFIKANZEINHEIT
    1703
    BAUMSPEICHER
  • 21
    • 1
    ENTSCHEIDUNG EINGEBEN
    SIGNIFIKANZ-KATEGORIE EINGEBEN
    2
    ENTSCHEIDUNG EINGEBEN
    SIGNIFIKANZ-KATEGORIE AUSGEBEN
    3
    ALLES NULL
  • 22
    • 1000
    VORWÄRTS-WAVELET-FILTER
    2200
    ABGLEICHEINHEIT
    105
    KONTEXTMODELL
  • 25a
    • 2501
    EINGEGEBENE DATEN GEWINNEN
    2502
    REVERSIBLES FILTER ANWENDEN
    2503
    ANDERE ZERLEGUNGSEBENE GEWÜNSCHT?
    2504
    REVERSIBLES FILTER BEI LL KOEFFIZIENTEN ANWENDEN
    2506
    GRUPPENFLAG FÜR JEDEN KOEFFIZIENTEN IN A-GRUPPE
    INITIALISIEREN
    2507
    BITEBENE FÜR A-DURCHGANG, SA AUF HÖCHSTWERTIGE BITEBENE
    (MAX) SETZEN
    2508
    BITEBENE FÜR B-DURCHGANG, SB AUF NÄCHSTE HÖCHSTWERTIGE
    BITEBENE (MAX – 1) SETZEN
  • 25b
    • 2509
    SA MIT RUF FREQUENZ BASIERENDEM MODELL CODIEREN?
    2510
    EIN BIT JEDES KOEFFIZIENTEN MIT AUF FREQUENZ BASIERENDEN
    MODELLIEREN UND ENTROPIE-CODIEREN
    2511
    EIN BIT FÜR JEDEN KOEFFIZIENTEN JSF-MODELL MODELLIEREN UND
    ENTROPIE-CODIEREN
    2514
    CODIERTE DATEN ÜBERTRAGEN ODER SPEICHERN
  • 26a
    • 2601
    CODIERTE DATEN WIEDER AUFFINDEN
    2602
    GRUPPENFLAG FÜR JEDEN KOEFFIZIENTEN IN A-GRUPPE
    INITIALISIEREN
    2603
    BITEBENE FÜR A-DURCHGANG, SA AUF HÖCHSTWERTIGE BITEBENE
    (MAX) SETZEN
    2604
    BITEBENE FÜR B-DURCHGANG, SB AUF NÄCHSTE HÖCHSTWERTIGE
    BITEBENE (MAX – 1) SETZEN
    2605
    ANFANGSWERT FÜR JEDEN KOEFFIZIENT AUF NULL SETZEN
    2606
    SA MIT AUF FREQUENZ-BASIERENDEM MODELL DECODIEREN?
    2607
    EIN BIT FÜR JEDEN KOEFFIZIENT MIT AUF FREQUENZ-BASIERENDEM
    MODELL MODELLIEREN UND ENTROPIE-CODIEREN
    2608
    EIN BIT FÜR JEDEN KOEFFIZIENTEN JSF-MODELL MODELLIEREN UND
    ENTROPIE-DECODIEREN
  • 26b
    • 2611
    INVERSES REVERSIBLES FILTER BEI KOEFFIZIENTEN VON GRÖBSTER
    ZERLEGUNGSEBENE ANWENDEN
    2612
    ALLE EBENEN INVERS GEFILTERT?
    2613
    INVERSES REVERSIBLES FILTER BEI KOEFFIZIENTEN AUS GRÖBSTER
    VERBLEIBENDERZERLEGUNGSEBENE ANWENDEN
    2614
    REKONSTRUIERTE DATEN SPEICHERN/ÜBERTRAGEN
  • 27a
    • 2701
    EIN DURCHGANG?
    2703
    do_A_flag LÖSCHEN
    2704
    do_A_flag SETZEN
    2705
    do_B_flag LÖSCHEN
    2706
    do_B_flag SETZEN
    2707
    do_A_flag? UND NULLBAUM#
    2708
    BESTIMMTES/UNBESTIMMTES FLAG AUF UNBESTIMMT FÜR JEDEN
    KOEFFIZIENTEN INITIALISIEREN
    2709
    C = ERSTER KOEFFIZIENT
  • 27b
    • 2710
    B-DURCHGANG RUF C
    2712
    A-DURCHGANG AUF C
    2713
    IST C LETZTER KOEFFIZIENT?
    2714
    C = NÄCHSTER KOEFFIZIENT
  • 28a
    • 2801
    EINGEGEBENE DATEN GEWINNEN
    2802
    REVERSIBLES FILTER ANWENDEN
    2803
    IST ANDERE ZERLEGUNGSEBENE GEWÜNSCHT?
    2804
    REVERSIBLES FILTER LL-KOEFFIZIENTEN ANWENDEN
    2805
    BITEBENE FÜR A-DURCHGANG, SA AUF HÖCHSTWERTIGE BITEBENE
    (MAX) SETZEN
    2806
    BITEBENE FÜR B-DURCHGANG, SB AUF NÄCHSTE HÖCHSTWERTIGE
    BITEBENE (MAX – 1) SETZEN
    2807
    MASKE MA AUF –(2(SA+1)) SETZEN
    2814
    MASKE MB AUF –(2(SB+1)) SETZEN
  • 28b
    • 2808
    SA MIT AUF FREQUENZ-BASIERENDEM MODELL MODELLIEREN?
    2809
    EIN BIT FÜR JEDEN KOEFFIZIENTEN MIT AUF FREQUENZ-BASIERENDEM
    MODELL MODELLIEREN UND ENTROPIE-CODIEREN
    2810
    EIN BIT FÜR JEDEN KOEFFIZIENTEN MIT JSF-MODELL MODELLIEREN
    UND ENTROPIE-CODIEREN
    2813
    CODIERTE DATEN ÜBERTRAGEN ODER SPEICHERN
  • 29a
    • 2901
    CODIERTE DATEN WIEDER AUFFINDEN
    2903
    BITEBENE FÜR A-DURCHGANG, SA AUF HÖCHSTWERTIGE BITEBENE
    (MAX) SETZEN
    2904
    BITEBENE FÜR B-DURCHGANG, SB AUF NÄCHSTE HÖCHSTWERTIGE
    BITEBENE (MAX – 1) SETZEN
    2905
    ANFANGSWERT VON JEDEM KOEFFIZIENTEN AUF NULL SETZEN
    2902
    MASKE MB AUF –(2(SB+1)) SETZEN
    2915
    MASKE MA AUF –(2(SA+1)) SETZEN
    2906
    SA MIT AUF FREQUENZ-BASIERENDEM MODELL DECODIEREN?
    2907
    EIN BIT FÜR JEDEN KOEFFIZIENTEN MIT AUF FREQUENZ-BASIERENDEM
    MODELL MODELLIEREN UND ENTROPIE-CODIEREN
    2908
    EIN BIT FÜR JEDEN KOEFFIZIENTEN JSF-MODELL MODELLIEREN UND
    ENTROPIE-DECODIEREN
  • 29b
    • 2911
    INVERSES REVERSIBLES FILTER BEI KOEFFIZIENTEN VON GRÖBSTER
    ZERLEGUNGSEBENE AUS ANLEGEN
    2912
    ALLE EBENEN/STUFEN INVERS GEFILTERT?
    2913
    INVERSES REVERSIBLES FILTER AN KOEFFIZIENTEN VON GRÖBSTER
    VERBLEIBENDER ZERLEGUNGSEBENE AUS ANLEGEN
    2914
    REKONSTRUIERTE DATEN SPEICHERN/ODER ÜBERTRAGEN
  • 30a
    • 3001
    A-DURCHGANG ERWÜNSCHT UND SA ≥ 0?
    3003
    do_A_flag LÖSCHEN
    3004
    do_A_flag SETZEN
    3002
    B-DURCHGANG ERWÜNSCHT UND SA ≥ SB?
    3005
    do_B_flag LÖSCHEN
    3006
    do_B_flag SETZEN
    3007
    do_A_flag? UND NULLBAUM
    3008
    BESTIMMTES/UNBESTIMMTES FLAG AUF UNBESTIMMT FÜR JEDEN
    KOEFFIZIENTEN INITIALISIEREN, WELCHER KINDER HAT
    3009
    C = ERSTER KOEFFIZIENT
  • 30b
    • 3012
    A-DURCHGANG BEI C
    3013
    IST C LETZTER KOEFFIZIENT?
    3014
    C = NÄCHSTER KOEFFIZIENT

Claims (29)

  1. Verfahren zum Codieren von Eingangsdaten mit den folgenden Schritten: a) eine überlappte, reversible Wavelet-Transformation wird auf die Eingangsdaten angewendet, um eine Reihe von Koeffizienten zu erzeugen, wobei die Transformation mittels einer Abfolge von Filteroperationen durchgeführt wird und wobei sich die Koeffizienten aus den Filteroperationen ergeben und Koeffizientengruppen Frequenzbänder darstellen, und b) die Reihe von Koeffizienten werden in Daten komprimiert, die eine komprimierte Version der Eingangsdaten darstellen, indem die Bits der Reihe von Koeffizienten durch ein Kontextmodell verarbeitet werden, das zur Verarbeitung eines Koeffizienten sowohl bekannte Koeffizienten in anderen Frequenzbändern als des aktuell verarbeiteten Koeffizienten als auch benachbarte Koeffizienten im selben Frequenzband wie des aktuell verarbeiteten Koeffizienten verwendet.
  2. Verfahren nach Anspruch 1, bei welchem die reversiblen Filter nicht-minimaler Länge eine Anzahl eindimensionaler Filter aufweisen.
  3. Verfahren nach Anspruch 1, bei welchem die Eingangsdaten Bilddaten aufweisen.
  4. Verfahren nach Anspruch 1, bei welchem der Schritt des Komprimierens den Schritt umfasst, dass mit der Reihe von Koeffizienten ein eingebettetes Codieren durchgeführt wird, bei welchem die Koeffizienten in einer signifikanten Reihenfolge geordnet werden.
  5. Verfahren nach Anspruch 1, das ferner die Schritte aufweist: Dekomprimieren einer komprimierten Version der Eingangsdaten in transformierte Signale, und Erzeugen der Eingangsdaten aus den transformierten Signalen in einer rekonstruierten Version der Eingangsdaten mit Hilfe einer inversen, reversiblen Wavelet-Transformation.
  6. Verfahren zum Decodieren von Eingangsdaten, welche gemäß den Verfahrensschritten des Patentanspruchs 1 codiert wurden, in ursprüngliche Daten, wobei das Verfahren die folgenden Schritte umfasst: Dekomprimieren der Eingangsdaten in transformierte Daten bestehend aus Koeffizienten, wobei zur Bestimmung der Bits der Koeffizienten ein Kontextmodell angewandt wird, das sowohl auf Daten von Koeffizienten in anderen Frequenzbändern als auch von Koeffizienten des selben Frequenzbandes basiert, und Erzeugen einer rekonstruierten Version der ursprünglichen codierten Daten aus den transformierten Daten durch Anwenden einer überlappten reversiblen Wavelet-Transformation.
  7. Verfahren zum Verarbeiten von Eingangsdaten, das die folgenden Schritte umfasst: Erzeugen einer Anzahl transformierter Signale aus den Eingangsdaten gemäß den Verfahrensschritten des Patentanspruchs 1, wobei bei der Wavelet-Transformation reversible Filter nicht-minimaler Länge verwendet werden, Rekonstruieren der Eingangsdaten durch Decodieren gemäß den Verfahrensschritten des Patentanspruchs 6.
  8. Verfahren zum Codieren von Eingangsdaten, das die folgenden Schritte umfasst: auf die Eingangsdaten wird eine reversible Wavelet-Transformation angewandt und damit eine Reihe von Koeffizienten erzeugt, wobei sich Koeffizienten aus den Filteroperationen ergeben und Koeffizientengruppen Frequenzbänder darstellen, und die Reihe von Koeffizienten wird eingebettet codiert, indem Schritte zum Ordnen der Reihe von Koeffizienten durchgeführt werden und wobei eine Bit-Signifikanz-Einbettung mit der Reihe von Koeffizienten durchgeführt wird, wobei ein erster Typ des eingebetteten Codierens mit einem ersten Teil der Daten durchgeführt wird und ein zweiter Typ des eingebetteten Codierens mit einem zweiten Teil der Daten durchgeführt wird, wobei eine Kontextmodell-Verarbeitung durchgeführt wird, die auf bekannten Koeffizienten in anderen Frequenzbändern und benachbarten Koeffizienten im selben Frequenzband basiert.
  9. Verfahren nach Anspruch 8, bei welchem der Schritt des Durchführens des ersten Typs von eingebettetem Codieren ein Baumcodieren umfasst.
  10. Verfahren nach Anspruch 8, bei welchem der Schritt des eingebetteten Codierens den Schritt des Formatierens der Reihe von Koeffizienten in ein Vorzeichen-Größen-Format bzw. Vorzeichen-Betrag-Format umfasst.
  11. Verfahren zum Codieren von Eingangsdaten, das die folgenden Schritte umfasst: auf die Eingangsdaten wird eine reversible Wavelet-Transformation angewandt und damit eine Reihe von Koeffizienten erzeugt, wobei sich Koeffizienten aus den Filteroperationen ergeben und Koeffizientengruppen Frequenzbänder darstellen, und die Reihe von Koeffizienten wird in ein Vorzeichen-Größe-Format bzw. Vorzeichen-Betrag-Format umgewandelt, um eine Reihe von formatierten Koeffizienten zu erzeugen; ein erster Teil der Reihe von formatierten Koeffizienten wird codiert, indem ein erster Typ eines eingebetteten Codierens verwendet wird, um einen ersten Bitstrom zu erzeugen; ein zweiter Teil der Reihe von formatierten Koeffizienten wird codiert, indem ein zweiter Typ eines eingebetteten Codierens verwendet wird, wobei gemäß diesem zweiten Typ Daten modelliert werden, indem die bekannten Koeffizienten in anderen Frequenzbändern und benachbarte Koeffizienten im selben Frequenzband verwendet werden, um einen zweiten Bitstrom zu erzeugen; und der erste Bitstrom und der zweite Bitstrom werden zu einem einzigen Bitstrom codiert.
  12. Verfahren nach Anspruch 11, welches ein Entropie-Codieren des einzigen Bitstroms umfasst.
  13. Verfahren nach Anspruch 11, bei welchem der Schritt des Durchführens des ersten Typs von eingebettetem Codierens das Durchführen eines Baumanordnungs-Codierens umfasst.
  14. Verfahren nach Anspruch 11, bei welchem der erste Teil die Bits der Reihe von formatierten Koeffizienten umfasst, die das höchstwertige Bit der Reihe von Koeffizienten enthalten, und der zweite Teil die Bits der Reihe von formatierten Koeffizienten umfasst, die nicht in dem ersten Teil sind.
  15. Verfahren nach Anspruch 11, bei welchem die Schritte der Transformierung von Eingangsdaten, Konvertierung der Reihe von Koeffizienten, Codierung eines ersten Teiles einer Reihe von formatierten Koeffizienten und Codierung eines zweiten Teiles der Reihe von formatierten Koeffizienten zu dem einzigen Bitstrom führen, der eine verlustfrei komprimierte Version der Eingangsdaten ist.
  16. Codierer zum Codieren von Eingangsdaten, wobei der Codierer umfasst: ein reversibler Wavelet-Filter zum Transformieren der Eingangsdaten in eine Anzahl von Koeffizienten, wobei sich Koeffizienten aus den Filteroperationen ergeben und Koeffizientengruppen Frequenzbänder darstellen, einen eingebetteten Codierer, der mit dem reversiblen Wavelet-Filter gekoppelt ist, um ein eingebettetes Codieren mit der Anzahl von Koeffizienten durchzuführen, um einen Bitstrom zu erzeugen, wobei der eingebettete Codierer ein Kontextmodell umfasst, das bei der Verarbeitung von Koeffizienten sowohl bekannte Koeffizienten in anderen Frequenzbändern wie des aktuell verarbeiteten Koeffizienten, als auch, benachbarte Koeffizienten im selben Frequenzband wie des aktuell verarbeiteten Koeffizienten verwendet, und einen Entropiecodierer, der an den eingebetteten Codierer angeschlossen ist, um ein Entropie-Codieren mit dem Bitstrom durchzuführen, um codierte Daten zu erzeugen.
  17. Codierer zum Codieren von Eingangsdaten, der Folgendes umfasst: einen Transformationscodierer, der angeschlossen ist, um auf die Eingangsdaten eine reversible Wavelet-Transformation anzuwenden und damit eine Reihe von Koeffizienten zu erzeugen, wobei sich Koeffizienten aus den Filteroperationen ergeben und Koeffizientengruppen Frequenzbänder darstellen; und einen eingebetteten Codierer, der angeschlossen ist, um auf die Koeffizienten ein Ordnen und Durchführen einer Bit-Signifikanz-Einbettung anzuwenden, um codierte Daten zu erzeugen, wobei der eingebettete Codierer ein Kontextmodell umfasst, das bei der Verarbeitung von Koeffizienten sowohl bekannte Koeffizienten in anderen Frequenzbändern als des aktuell verarbeiteten Koeffizienten als auch benachbarte Koeffizienten im selben Frequenzband wie des aktuell verarbeiteten Koeffizienten verwendet.
  18. Verfahren nach Anspruch 1, 6 bis 8 und 11, bei welchem die überlappte reversible Wavelet-Transformation eine 2/10-Transformation umfasst.
  19. Verfahren nach Anspruch 7, bei welchem die überlappte reversible Wavelet-Transformation ein Paar von reversiblen Filtern nicht-minimaler Länge umfasst, die als ein 2/10-Transformations-Filterpaar arbeiten.
  20. Decoder zum Decodieren von Eingangsdaten, welche gemäß den Verfahrensschritten des Patentanspruchs 1 komprimiert wurden, in ursprüngliche Daten, wobei der Decoder umfasst: einen Dekomprimierer, um die Eingangsdaten in transformierte Daten bestehend aus einer Anzahl von Koeffizienten zu dekomprimieren, indem eine Kontextmodellierung verwendet wird, die auf bekannten Koeffizienten in anderen Frequenzbändern und benachbarten Koeffizienten desselben Frequenzbandes basiert; und eine überlappte inverse reversible Wavelet-Transformation, die an den Dekomprimierer angeschlossen ist, um eine rekonstruierte Version von ursprünglichen Daten von der Anzahl von Koeffizienten zu erzeugen.
  21. Verfahren nach Anspruch 1, bei welchem der Schritt des Anwendens einer überlappten reversiblen Wavelet-Transformation auf die Eingangsdaten das Anwenden von reversiblen Filtern nicht-minimalen Länge umfasst, um die Reihe von Koeffizienten zu erzeugen.
  22. Verfahren nach Anspruch 6, bei welchem der Schritt des Erzeugens einer rekonstruierten Version der ursprünglichen Daten das Anwenden von reversiblen Filtern nicht-minimaler Länge umfasst, um die Reihe von Koeffizienten zu erzeugen.
  23. Verfahren nach Anspruch 8 und 11, bei welchem der Schritt des Transformationscodierens das Anwenden eines Paares von reversiblen Filtern nicht-minimaler Länge umfasst, um die Eingangsdaten in eine Reihe von Koeffizienten zu transformationscodieren.
  24. Codierer nach Anspruch 16, bei welchem der reversible Wavelet-Filter ein Paar von reversiblen Filtern nicht-minimaler Länge umfasst.
  25. Codierer nach Anspruch 17, bei welchem der Transformationscodierer ein Paar von reversiblen Filtern nicht-minimaler Länge umfasst.
  26. Codierer nach Anspruch 16, bei welchem der reversible Wavelet-Filter ein 2/10-variabler Wavelet-Filter ist.
  27. Codierer nach Anspruch 26, bei welchem der Codierer ein Kontextmodell und einen Bitgenerator umfasst, der an das Kontextmodell angeschlossen ist.
  28. Codierer nach Anspruch 27, bei welchem das Kontextmodell Bits von Koeffizienten modelliert, die auf bekannten Koeffizienten in anderen Frequenzbändern und auf benachbarten Koeffizienten im selben Frequenzband basieren.
  29. Decoder nach Anspruch 20, bei welchem die inverse Wavelet-Transformation einen inversen 2/10-reversiblen Wavelet-Filter umfasst.
DE19534730A 1994-09-20 1995-09-19 Verfahren zum Codieren und Decodieren von Daten Expired - Fee Related DE19534730B4 (de)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US31014194A 1994-09-20 1994-09-20
US08/310,141 1994-09-20

Publications (2)

Publication Number Publication Date
DE19534730A1 DE19534730A1 (de) 1996-05-02
DE19534730B4 true DE19534730B4 (de) 2006-04-27

Family

ID=23201171

Family Applications (1)

Application Number Title Priority Date Filing Date
DE19534730A Expired - Fee Related DE19534730B4 (de) 1994-09-20 1995-09-19 Verfahren zum Codieren und Decodieren von Daten

Country Status (4)

Country Link
US (1) US7418142B2 (de)
JP (1) JP3302229B2 (de)
DE (1) DE19534730B4 (de)
NL (1) NL1001247C2 (de)

Families Citing this family (26)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6549666B1 (en) 1994-09-21 2003-04-15 Ricoh Company, Ltd Reversible embedded wavelet system implementation
GB2325584B (en) * 1997-05-01 2000-03-29 Ricoh Kk Decompression system using inverse wavelet transform
JP3471366B2 (ja) * 1997-07-30 2003-12-02 三菱電機株式会社 画像圧縮・伸張方法および画像圧縮・伸張装置
DE19744407C1 (de) 1997-10-08 1999-02-11 Luratech Ges Fuer Luft Und Rau Verfahren zur mehrdimensionalen, diskreten Wavelet-Transformation und Transformationseinheit zur Durchführung des Verfahrens
US7065253B2 (en) * 1999-09-03 2006-06-20 Intel Corporation Wavelet zerotree coding of ordered bits
DE10146582A1 (de) * 2001-09-21 2003-04-24 Micronas Munich Gmbh Vorrichtung und Verfahren zur Teilbandzerlegung von Bildsignalen
JP2004015741A (ja) * 2002-06-11 2004-01-15 Fujitsu Ltd 画像処理方法、画像処理プログラムおよび画像処理装置
US7395210B2 (en) * 2002-11-21 2008-07-01 Microsoft Corporation Progressive to lossless embedded audio coder (PLEAC) with multiple factorization reversible transform
US7826670B2 (en) * 2005-06-15 2010-11-02 Fujifilm Corporation Data compression apparatus and data compression program storage medium
JP4360379B2 (ja) * 2006-05-16 2009-11-11 ソニー株式会社 画像処理装置及び画像処理方法、プログラム及び記録媒体
JP5035154B2 (ja) * 2008-03-07 2012-09-26 富士通株式会社 映像信号処理装置及び映像信号処理方法
JP2009290552A (ja) * 2008-05-29 2009-12-10 Fujifilm Corp 動画圧縮装置および動画圧縮プログラム
US8538189B2 (en) * 2008-11-14 2013-09-17 Ati Technologies Ulc Image noise filter and method
WO2010091930A2 (en) * 2009-02-12 2010-08-19 Zoran (France) Frame buffer compression for video processing devices
US8559733B2 (en) * 2009-03-31 2013-10-15 Citrix Systems, Inc. Methods and systems for approximating progressive image encoding using image partitioning
JP2011019008A (ja) * 2009-07-07 2011-01-27 Fujifilm Corp 動画圧縮送信装置、動画圧縮送信プログラム、および動画圧縮送信方法
US20120134426A1 (en) * 2009-08-20 2012-05-31 Thomson Licensing Method and apparatus for reusing tree structures to encode and decode binary sets
US8793391B2 (en) * 2010-11-30 2014-07-29 Deutsche Telekom Ag Distortion-aware multihomed scalable video streaming to multiple clients
US20160029024A1 (en) * 2011-08-10 2016-01-28 Zoran (France) S.A. Frame buffer compression for video processing devices
US20130166767A1 (en) * 2011-11-23 2013-06-27 General Electric Company Systems and methods for rapid image delivery and monitoring
FR3005816B1 (fr) * 2013-05-17 2019-11-29 Jean-Claude Colin Procede pour encoder, notamment des images compressees, notamment par "range coder" ou compression arithmetique.
US8879858B1 (en) 2013-10-01 2014-11-04 Gopro, Inc. Multi-channel bit packing engine
US9423455B2 (en) * 2014-12-15 2016-08-23 Genesys Testware, Inc. Design-for-test techniques for a digital electronic circuit
US20160234529A1 (en) * 2015-02-05 2016-08-11 Syed Shakir Iqbal Method and apparatus for entropy encoding and decoding
US10462490B2 (en) * 2015-11-06 2019-10-29 Raytheon Company Efficient video data representation and content based video retrieval framework
CN112995637B (zh) * 2021-03-10 2023-02-28 湘潭大学 一种基于三维离散小波变换的多剖面医学图像压缩方法

Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4751742A (en) * 1985-05-07 1988-06-14 Avelex Priority coding of transform coefficients
US5014134A (en) * 1989-09-11 1991-05-07 Aware, Inc. Image compression method and apparatus

Family Cites Families (105)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US3506327A (en) 1964-04-23 1970-04-14 Battelle Development Corp Wavefront reconstruction using a coherent reference beam
US3950103A (en) 1972-10-27 1976-04-13 Canadian Patents And Development Limited Method and apparatus to determine spatial distribution of magnitude and phase of electro-magnetic fields especially optical fields
DE2640140C2 (de) 1976-09-07 1982-10-07 Philips Patentverwaltung Gmbh, 2000 Hamburg Verfahren und Anordnung zur redundanzvermindernden Bildcodierung
DE2640157C2 (de) 1976-09-07 1982-10-07 Philips Patentverwaltung Gmbh, 2000 Hamburg Verfahren und Anordnung zum redundanzvermindernden Codieren von Bildern
US4136954A (en) 1976-12-29 1979-01-30 Jamieson John A Imaging apparatus including spatial-spectral interferometer
US4223354A (en) 1978-08-30 1980-09-16 General Electric Company Phase corrected raster scanned light modulator and a variable frequency oscillator for effecting phase correction
US4393456A (en) 1981-03-19 1983-07-12 Bell Telephone Laboratories, Incorporated Digital filter bank
EP0070948B1 (de) 1981-07-28 1985-07-10 International Business Machines Corporation Sprachkodierungsverfahren und Ausführungsanordnung für das genannte Verfahren
US4437087A (en) 1982-01-27 1984-03-13 Bell Telephone Laboratories, Incorporated Adaptive differential PCM coding
US4674125A (en) 1983-06-27 1987-06-16 Rca Corporation Real-time hierarchal pyramid signal processing apparatus
US4599567A (en) 1983-07-29 1986-07-08 Enelf Inc. Signal representation generator
US4652881A (en) 1984-01-10 1987-03-24 Lewis Bernard L Efficient adaptive filter bank
FR2577084B1 (fr) 1985-02-01 1987-03-20 Trt Telecom Radio Electr Systeme de bancs de filtres d'analyse et de synthese d'un signal
US4701006A (en) 1985-02-20 1987-10-20 Stanford University Optical-digital hologram recording
GB2181318B (en) 1985-10-04 1989-12-28 Sony Corp Two-dimensional finite impulse response filters
US4760563A (en) 1986-01-09 1988-07-26 Schlumberger Technology Corporation Seismic exploration using exactly invertible discrete transformation into tau-p space
US4929223A (en) 1986-02-18 1990-05-29 Adolph Coors Company Packaging alignment system
DE3732085A1 (de) 1986-03-26 1989-04-06 Ant Nachrichtentech Digitaler filterbaum
US4663660A (en) 1986-06-20 1987-05-05 Rca Corporation Compressed quantized image-data transmission technique suitable for use in teleconferencing
GB8621994D0 (en) 1986-09-12 1986-10-22 Crosfield Electronics Ltd Image processing
US4868868A (en) 1986-09-30 1989-09-19 Oki Electric Industry Co., Ltd. Sub-band speech analyzing and synthesizing device
FR2606576B1 (fr) 1986-11-07 1989-02-03 Labo Electronique Physique Dispositif pour transmettre des images de television haute definition dans des canaux a bande etroite
GB2197766B (en) 1986-11-17 1990-07-25 Sony Corp Two-dimensional finite impulse response filter arrangements
US4815023A (en) 1987-05-04 1989-03-21 General Electric Company Quadrature mirror filters with staggered-phase subsampling
US4817182A (en) 1987-05-04 1989-03-28 General Electric Company Truncated subband coding of images
BE1000643A5 (fr) 1987-06-05 1989-02-28 Belge Etat Procede de codage de signaux d'image.
DE3853555T2 (de) 1987-06-09 1995-08-17 Sony Corp Verarbeitung des Bewegungsvektors in digitalen Fernsehbildern.
US4837517A (en) 1987-07-16 1989-06-06 Schlumberger Technology Corporation Spatial frequency method and apparatus for investigating earth conductivity with high vertical resolution by induction techniques
US4785349A (en) 1987-10-05 1988-11-15 Technology Inc. 64 Digital video decompression system
US4936665A (en) 1987-10-25 1990-06-26 Whitney Theodore R High resolution imagery systems and methods
US4881075A (en) 1987-10-15 1989-11-14 Digital Equipment Corporation Method and apparatus for adaptive data compression
US5156943A (en) 1987-10-25 1992-10-20 Whitney Theodore R High resolution imagery systems and methods
US4827336A (en) 1987-12-18 1989-05-02 General Electric Company Symbol code generation processing from interframe DPCM of TDM'd spatial-frequency analyses of video signals
US4858017A (en) * 1988-01-22 1989-08-15 The Trustees Of Columbia University In The City Of New York System and method for hierarchal image encoding and decoding
US5095447A (en) 1988-03-25 1992-03-10 Texas Instruments Incorporated Color overlay of scanned and reference images for display
US5018210A (en) 1988-03-25 1991-05-21 Texas Instruments Incorporated Pattern comparator with substage illumination and polygonal data representation
US5001764A (en) 1988-03-25 1991-03-19 Texas Instruments Incorporated Guardbands for pattern inspector
US4985927A (en) 1988-03-25 1991-01-15 Texas Instruments Incorporated Method of detecting and reviewing pattern defects
US4897717A (en) 1988-03-30 1990-01-30 Starsignal, Inc. Computer-based video compression system
EP0339589A3 (de) 1988-04-28 1992-01-02 Sharp Kabushiki Kaisha Orthogonales Transformationskodierungssystem für Bilddaten
US4982283A (en) 1988-05-06 1991-01-01 General Electric Company Line-sequential pyramid processing of a plurality of raster-scanned image variables
US4899147A (en) 1988-06-03 1990-02-06 Unisys Corporation Data compression/decompression apparatus with throttle, start-up and backward read controls
US4829378A (en) 1988-06-09 1989-05-09 Bell Communications Research, Inc. Sub-band coding of images with low computational complexity
US4904073A (en) 1988-08-10 1990-02-27 Aware, Inc. Fractal tiling for multiple mirror optical devices
FR2637400B1 (fr) 1988-09-30 1990-11-09 Labo Electronique Physique Dispositif de traitement ameliore d'un signal echographique
US4929946A (en) 1989-02-09 1990-05-29 Storage Technology Corporation Adaptive data compression apparatus including run length encoding for a tape drive system
FR2643986B1 (fr) 1989-03-03 1991-05-17 Thomson Csf Procede d'analyse d'un signal par ondelettes
US4918524A (en) 1989-03-14 1990-04-17 Bell Communications Research, Inc. HDTV Sub-band coding using IIR filter bank
JPH02305182A (ja) 1989-05-19 1990-12-18 Fuji Photo Film Co Ltd 画像信号圧縮符号化装置
US5072308A (en) 1989-06-21 1991-12-10 International Mobile Machines Corporation Communication signal compression system and method
US4987480A (en) 1989-07-11 1991-01-22 Massachusetts Institute Of Technology Multiscale coding of images
US4974187A (en) 1989-08-02 1990-11-27 Aware, Inc. Modular digital signal processing system
US5073964A (en) 1989-08-04 1991-12-17 Aware, Inc. Signal processing device and method
US5241395A (en) 1989-08-07 1993-08-31 Bell Communications Research, Inc. Adaptive transform coding using variable block size
US5097261A (en) 1989-11-22 1992-03-17 International Business Machines Corporation Data compression for recording on a record medium
US5173880A (en) 1989-12-26 1992-12-22 Exxon Production Research Company Method of generating seismic wavelets using seismic range equation
US5068911A (en) 1990-02-09 1991-11-26 Aware, Inc. Method and apparatus for representing an image
US4973961A (en) 1990-02-12 1990-11-27 At&T Bell Laboratories Method and apparatus for carry-over control in arithmetic entropy coding
US5103306A (en) 1990-03-28 1992-04-07 Transitions Research Corporation Digital image compression employing a resolution gradient
US4999705A (en) 1990-05-03 1991-03-12 At&T Bell Laboratories Three dimensional motion compensated video coding
DE4016172C1 (de) 1990-05-19 1991-03-28 Werner 5900 Siegen De Ackermann
US5101446A (en) 1990-05-31 1992-03-31 Aware, Inc. Method and apparatus for coding an image
US5128757A (en) 1990-06-18 1992-07-07 Zenith Electronics Corporation Video transmission system using adaptive sub-band coding
DE69028772T2 (de) 1990-07-11 1997-04-03 Philips Electronics Nv Vorrichtung zur Ableitung eines kompatiblen Zeilensprungfernsehsignals mit geringer Auflösung und anderen Komponenten eines hochauflösenden Zeilensprungfernsehsignals sowie Vorrichtung zur Wiederherstellung des Originalsignals
US5148498A (en) 1990-08-01 1992-09-15 Aware, Inc. Image coding apparatus and method utilizing separable transformations
US5081645A (en) 1990-08-06 1992-01-14 Aware, Inc. Novel spread spectrum codec apparatus and method
US5128791A (en) 1990-08-13 1992-07-07 Bell Communications Research, Inc. Multi-channel HDTV system
US5097331A (en) 1990-08-24 1992-03-17 Bell Communications Research, Inc. Multiple block-size transform video coding using an asymmetric sub-band structure
US5049992A (en) 1990-08-27 1991-09-17 Zenith Electronics Corporation HDTV system with receivers operable at different levels of resolution
US5049993A (en) 1990-10-03 1991-09-17 Bell Communications Research, Inc. Format conversion preprocessing method and circuit
GB2252002B (en) 1991-01-11 1995-01-04 Sony Broadcast & Communication Compression of video signals
JP3012698B2 (ja) 1991-01-29 2000-02-28 オリンパス光学工業株式会社 画像データの符号化装置および符号化方法
US5121191A (en) 1991-03-15 1992-06-09 Aware, Inc. Method and apparatus for coding motion pictures
US5276525A (en) 1991-03-22 1994-01-04 Bell Communications Research, Inc. Two-dimensional block scanning for subband image and video coding
US5262958A (en) 1991-04-05 1993-11-16 Texas Instruments Incorporated Spline-wavelet signal analyzers and methods for processing signals
WO1992021101A1 (en) * 1991-05-17 1992-11-26 The Analytic Sciences Corporation Continuous-tone image compression
US5235434A (en) 1991-06-27 1993-08-10 Polaroid Corporation Method and apparatus for selectively adjusting the brightness of large regions of an image
US5349348A (en) 1991-08-15 1994-09-20 International Business Machines Corporation Multi-mode data stream generator
US5315670A (en) * 1991-11-12 1994-05-24 General Electric Company Digital data compression system including zerotree coefficient coding
GB2262854B (en) * 1991-12-24 1995-05-24 Sony Broadcast & Communication Image processing apparatus
US5347479A (en) 1991-12-27 1994-09-13 Nec Corporation Small-size wavelet transform apparatus
CA2088082C (en) * 1992-02-07 1999-01-19 John Hartung Dynamic bit allocation for three-dimensional subband video coding
US5321776A (en) 1992-02-26 1994-06-14 General Electric Company Data compression system including successive approximation quantizer
KR0150955B1 (ko) 1992-05-27 1998-10-15 강진구 비트고정을 위한 영상압축방법과 신장방법 및 그 장치
US5511151A (en) 1992-06-10 1996-04-23 Canon Information Systems, Inc. Method and apparatus for unwinding image data
JPH0638193A (ja) * 1992-07-17 1994-02-10 Casio Comput Co Ltd 画像圧縮装置
US5379355A (en) 1992-08-24 1995-01-03 Ricoh Corporation Data encoding using one or more adaptive decision trees
US5638498A (en) 1992-11-10 1997-06-10 Adobe Systems Incorporated Method and apparatus for reducing storage requirements for display data
US5563960A (en) 1993-01-22 1996-10-08 David Sarnoff Research Center, Inc. Apparatus and method for emphasizing a selected region in the compressed representation of an image
US5412741A (en) * 1993-01-22 1995-05-02 David Sarnoff Research Center, Inc. Apparatus and method for compressing information
US5414780A (en) 1993-01-27 1995-05-09 Immix Method and apparatus for image data transformation
IL104636A (en) 1993-02-07 1997-06-10 Oli V R Corp Ltd Apparatus and method for encoding and decoding digital signals
US5381145A (en) 1993-02-10 1995-01-10 Ricoh Corporation Method and apparatus for parallel decoding and encoding of data
JP2933457B2 (ja) 1993-02-18 1999-08-16 日本電気株式会社 ウェーブレット変換符号化方法
US5420891A (en) 1993-03-18 1995-05-30 New Jersey Institute Of Technology Multiplierless 2-band perfect reconstruction quadrature mirror filter (PR-QMF) banks
US5546477A (en) 1993-03-30 1996-08-13 Klics, Inc. Data compression and decompression
GB2281465B (en) 1993-08-27 1997-06-04 Sony Uk Ltd Image data compression
US5495292A (en) * 1993-09-03 1996-02-27 Gte Laboratories Incorporated Inter-frame wavelet transform coder for color video compression
JP2720926B2 (ja) 1993-10-26 1998-03-04 富士ゼロックス株式会社 画像符号化装置
US5453945A (en) 1994-01-13 1995-09-26 Tucker; Michael R. Method for decomposing signals into efficient time-frequency representations for data compression and recognition
AU1727495A (en) * 1994-01-14 1995-08-01 Houston Advanced Research Center Boundary-spline-wavelet compression for video images
US5541594A (en) * 1994-03-28 1996-07-30 Utah State University Foundation Fixed quality source coder with fixed threshold
US5534925A (en) 1994-05-02 1996-07-09 Cognitech Inc. Image compression by optimal reconstruction
US5602589A (en) 1994-08-19 1997-02-11 Xerox Corporation Video image compression using weighted wavelet hierarchical vector quantization
US5566089A (en) 1994-10-26 1996-10-15 General Instrument Corporation Of Delaware Syntax parser for a video decompression processor

Patent Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4751742A (en) * 1985-05-07 1988-06-14 Avelex Priority coding of transform coefficients
US5014134A (en) * 1989-09-11 1991-05-07 Aware, Inc. Image compression method and apparatus

Also Published As

Publication number Publication date
DE19534730A1 (de) 1996-05-02
NL1001247A1 (nl) 1996-03-20
JP3302229B2 (ja) 2002-07-15
JPH08116265A (ja) 1996-05-07
US20020048405A1 (en) 2002-04-25
NL1001247C2 (nl) 1997-05-27
US7418142B2 (en) 2008-08-26

Similar Documents

Publication Publication Date Title
DE19534730B4 (de) Verfahren zum Codieren und Decodieren von Daten
DE19534943B4 (de) Vorrichtung zur Komprimierung unter Verwendung von eingebetteten Kleinwellen
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
DE19861377B4 (de) Ein verbessertes Kompressions- und Dekompressionssystem mit reversiblen Wavelets und verlustbehafteter Rekonstruktion
US7167592B2 (en) Method and apparatus for compression using reversible wavelet transforms and an embedded codestream
DE602004002525T2 (de) Verfahren zum Umcodieren eines nach JPEG2000 komprimierten Bildes
DE69635055T2 (de) Kodierung von zerotree-informationen in einem bildkodierungssystem mit wavelettransformation
DE69421690T2 (de) Geraet und verfahren zur datenkompression
DE69633129T2 (de) Waveletbaum-bildcoder mit überlappenden bildblöcken
DE69628760T2 (de) Speicherung und wiedergewinnung von grossen digitalen bildern
DE69511390T2 (de) Quellencodierer mit voreingestellter qualität
DE69736329T2 (de) Verschachtelte verteilte kodierung von spärlich bestückten datensätzen
DE19819405B4 (de) Implementation eines reversiblen eingebetteten Wavelet-Systems
DE60012717T2 (de) Bildcodierung unter verwendung einer umordnung von wavelet-koeffizienten
DE69420794T2 (de) Kodierungsvorrichtung zur Bildkompression
DE69936304T2 (de) Bereichsbasierte skalierbare bildkodierung
GB2302244A (en) Wavelet transform filter
GB2313757A (en) Method using an embedded codestream
Akrouf Application of multirate digital signal processing to image compression

Legal Events

Date Code Title Description
OP8 Request for examination as to paragraph 44 patent law
8364 No opposition during term of opposition
R119 Application deemed withdrawn, or ip right lapsed, due to non-payment of renewal fee

Effective date: 20140401