DE19819405A1 - Data compression system for wavelet transform - Google Patents

Abstract

The system includes a band buffer (501), coupled to an input of a wavelet transform unit (502). The wavelet transform unit performs a reversible wavelet transform on pixels stored in the buffer and to generate coefficients at its output. A coder, comprising a context model and a parallel entropy coder encoder, is coupled to the wavelet transform unit to code bitplanes of wavelet transformed pixels received from the transform unit and also the buffer.

Description

The present invention relates to the field of data compression and decompression expression systems; In particular, the present invention relates to a method and an apparatus for lossless and lossy coding and decoding of Data in compression / decompression systems.

Data compression is an extremely useful tool for large amounts of data save and transfer. For example, the time required is one Picture, such as As a facsimile transmission of a document to transfer, drastically reduces when compression is used to reduce the number of bits like that needed to create the image.

Many different data compression techniques exist in the art. Compression techniques can be divided into two broad categories, loss sticky coding and lossless coding. Lossy coding closes this Encoding, which leads to the loss of information, so that there is no guarantee of a perfect reconstruction of original data. The goal of a lossy Compression is that changes to the original data in such a way and that they are not objectionable or detectable. at  lossless compression, the entire information is maintained or maintained and the data is compressed in a way that a perfect reconstruction allows.

In lossless compression, input symbols or intensity data become converted to output code words. The input can contain the following data: Image data, audio data, one-dimensional data (eg, data that is spatially or temporal change), two-dimensional data (eg, data that is divided into two spatial data) Change directions (or a spatial dimension and a temporal dimension change)), or multidimensional / multispectral data. If the compression succeed rich, the codewords are represented by fewer bits than the number of bits, which were necessary for the uncoded input symbols (or intensity data). Lossless coding methods include lexical methods ("dictionary methods") coding (e.g., Lempel-Ziv), run-length coding, enumerating coding ("enu merative coding ") and entropy coding, for lossless image compression Compression is based on predictions or contexts plus coding. The JPEG standard for facsimile compression (ISO / IEC 11544) and DPCM (differential pulse Code modulation or "Differential Pulse Code Modulation" - an option in the JPEG standard (SIO / IEC 10918)) for continuous tone images Examples of lossless compression of images. In the lossy Compression becomes input symbols or intensity data before conversion Output codewords quantized. Quantization is meant to be relevant cha characteristics of the data while eliminating unimportant characteristics become. Lossy systems often use one before quantization Transformation to provide an energy compaction. JPEG is an example of a lossy coding method for image data.

Recent developments in image signal processing continue to focus on their Attention to the need for efficient and effective forms of data compression coding. Different forms of a transformation or pyramidal  Signal processing has been proposed, including multiple pyramidal processing ("multi-resolution pyramidal processing") and the Wavelet pyramidal processing ("wavelet pyramidal processing"). These forms are also called subband processing and hierarchical Called "hierarchical processing". The wavelet pyramidal processing Image data represents a specific type of multi-resolution pyramidal processing, the quadrature mirror filters (QMFs or "Quadrature Mirror Filters") can use to create subband decompositions of an original image. Bemer It is worth noting that other types of non-QMF wavelets exist. For more information With regard to wavelet processing, Antonini, M., et al. "Image Coding Using Wavelet Transform, IEEE Transactions on Image Processing, Volume 1, No. 2, April 1992; Shapiro, J. "An Embedded Hierarchical Image Coder Using Zerotrees of Wavelet Coefficients, "Proc. IEEE Data Compression Conference, pp. 39-44 214-223, 1993. Regarding the information about reversible transformation Said, A. and Pearlman, W. "Reversible Image Compression via Multire Solution Representation and Predictive Coding ", Dept. of Electrical, Computer and Systems Engineering, Renssealer Polytechnic Institute, Troy, NY 1993.

Compression often takes a long time and is memory intensive. It's okay worth the compression faster and / or with a reduced memory to carry out, if possible. Some applications never have a com used because either the quality could not be guaranteed, the Compression rate was not high enough or the data rate was uncontrollable. however the use of compression is desirable to reduce the amount of information that transmitted and / or stored to reduce.

Digital copiers, printers, scanners and multifunctional machines come with a Frame storage greatly improved. A compressed frame storage reduced the memory and thus the cost for a full-frame storage in this Pro are necessary. However, many full-frame stores come with stores  random access (RAMs) implemented. RAM is fast but im generally expensive. Hard disks can also be used as storage and are generally considered cheap (or generally less expensive) as the RAM). Therefore, it would be a benefit for any system manufacturer Generation of a less expensive system, consider a hard drive for the purpose, such as z. As frame memory, instead of a RAM to use.

A problem with using hard disks for time-sensitive applications It is difficult to directly access information from a hard disk to access how to access the same information from a RAM. Likewise, many hard disks use compression when they have information on the hard disk Save disk to increase the amount of information stored on the hard disk can be chert. The time it takes to complete the compression can also benefit from using hard drives in time-sensitive applications put off. Both the slow speed, the use of Hard disk is inherent, as well as the use of compression makes the Verwen hard drives in time-sensitive applications can be difficult to implement tationsthema.

The present invention provides fast lossy / lossless compression ready. The present invention represents system implementations that use the low-cost hard disk technology instead of expensive RAM. Further, the present invention provides rate matching Ready for a hard drive and provides compression to the Hard disk to bandwidths of other parts of the system implementation, such as. Legs Printing machine or an image forming device to adapt. The present The invention also provides for the use of RAM where time is spent on comm compression and decompression is not much slower than the RAM speed. In this way, the present invention performs a speed adaptation to a RAM by.  

A method and apparatus for performing compression and / or compression Decompression will be described. In one embodiment, the present invention de invention a system with a buffer, a wavelet transform unit and an encoder. The wavelet transformation unit has an input which is on The buffer is connected to a wavelet transformation with pixels through to store coefficients stored at one output produce. The encoder is connected to a wavelet transform unit to to encode the transformed pixels received from the buffer.

In the following description, further features are disclosed. It can different features of different embodiments combined become.

Fig. 1A shows context dependency ratios. Children are conditioned to their parents or parents.

Fig. 2A shows an order similar to a raster order.

Fig. 2B shows an alternative embodiment of an order described herein as a short fringe order.

Fig. 2C shows an alternative short seam order.

Figs. 3A to 3H show the result of each application of the transistor transform filter for a four-level transform on a wavelet tree of the present invention.

Fig. 4A is a block diagram of one embodiment of a forward / inverse filter unit for use in the implementation of the one-dimensional filters.

FIG. 4B is a block diagram of an embodiment of a first level-forward transform of the present invention.

FIG. 5 is a block diagram of one embodiment of a complete pre-transformation according to the present invention. FIG.

Fig. 6 is a timing chart regarding when coefficients who spent the.

Figs. 7A to 7H show the results (outputs) of each one-dimensional filter operation for the TT transformation.

Fig. 8 is a block diagram of a 10-tap forward / inverse filter unit.

FIG. 9 is a block diagram of one embodiment of the overlap unit for the forward / inverse filters of FIG. 8. FIG .

Fig. 10 shows the order of the code stream and the order within a coding unit.

Fig. 11 shows the bit depth of various coefficients in a two-level TS transformation and a TT transform decomposition from an input image with b bits per pixel.

Fig. 12 is an embodiment of the multiplier for the frequency band used for coefficient alignment in the present invention.

Fig. 13A shows a coefficient which is divided into the most important data and less important data.

Fig. 13B shows the lossless case where no data is deleted.

Fig. 13C shows the case where a bit plane of data has been cleared (ie, Q = 2), since erasing a bit plane corresponds to division by 2.

Fig. 14 is a flowchart showing an embodiment of the operation of the compression / decompression system.

FIG. 15 shows an embodiment where 6 bits are used for each tree.

Fig. 16 is a flow chart for coding the most important part.

Fig. 17 is a block diagram of one embodiment of the formatter and context model used during the most important data encoding run.

Fig. 18 shows an embodiment of a first bit plane unit.

Fig. 19 is a flowchart showing an embodiment of the coding processing of a LIC bit plane.

Fig. 20 is a block diagram of one embodiment of the predictive and contextual model for less important data.

Figure 21 is a block diagram of one embodiment of the context model that provides conditioning for header bits.

Fig. 22 shows memory usage for one embodiment of the context model with conditioning of all neighbors and parents.

Fig. 23 is a block diagram of one embodiment of the sign bits context model.

Fig. 24 shows an embodiment of parallel coding for the LIC.

Fig. 25 is a block diagram of an embodiment of a front end of a printer.

Fig. 26 is a block diagram of one embodiment of the rear end of the printer.

Fig. 27 is a block diagram of an alternative embodiment of the rear end of the printer.

Fig. 28 is a block diagram of one embodiment of an integrated circuit (IC) chip incorporating printer compression / decompression.

Fig. 29 shows the basic timing of the system during printing.

Fig. 30 shows one possible embodiment of how pixel data is organized.

Fig. 31 shows a band buffer of one page.

Fig. 32 is a timing chart of coding explaining current memory access requirements.

Fig. 33 shows how circular addressing can be used to handle the writing of data larger than the read data.

Fig. 34 shows an encoder and decoder pair.

Fig. 35 shows an embodiment of a binary context model.

Fig. 36 shows an alternative embodiment of a binary context model.

Fig. 37 shows the neighborhood coefficients for each coefficient of a Co unit.

Fig. 38 shows a pyramidal orientation based on an MSE orientation.

Fig. 39 shows an MSE alignment of wavelet coefficients.

There will be a method and apparatus for compression and decompression described. In the following description, numerous details are set forth, such as z. As delay types, bit rates, filter types, etc. For a person skilled but it will be clear that the present invention practiced without these specific details can be. In other cases, well-known structures and devices in Block diagram form, rather than in detail, to obfuscate the to avoid the present invention.

Some parts of the detailed descriptions that follow are in terms of Algorithms and symbolic representations of operations with data bits within a computer memory shown. This algorithmic descriptions and representations These funds represent the means used by experts in the field of data processing Working can be used to make the essence of their work more effective to other professionals to convey. An algorithm here and in general means a self-consistent one Sequence of steps leading to a desired result. At the steps These are those that are physical manipulations of physical Require quantities. Usually, but not necessarily, they take Quantities take the form of electrical and magnetic signals that are stored,  transmitted, combined, compared and otherwise manipulated. It has proved to be appropriate, mainly for reasons of uniform use these signals as bits, values, elements, symbols, signs, terms, numbers and to designate the like.

One should not forget, however, that all of these and similar terms are appropriate are associated with physical quantities and only appropriate designations represent that were given these quantities. Unless otherwise stated As will be apparent from the following discussion, it will be appreciated that throughout the present invention, the discussions, the terms such. B. "Processing" or "calculating" or "calculating" or "determining" or "displaying" or the like, on the effect and the processing of a computer system or a similar electronic calculation device, the data manipulated and transformed as physical (electronic) quantities in be represented within the registers and memory of the computer system, namely in other data, in a similar way than physical quantities within the Memory or registers or other such information storage, transmission or Display devices are stored or registered.

The present invention also relates to an apparatus for the operations therein perform. This apparatus can be specially designed for the required purposes or he can include a general-purpose computer that is powered by a computer pro program is selectively enabled or reconfigured, which is stored in the computer. Such a computer program can be stored in a computer-readable storage medium be stored, such. B. in any type of disk including floppy disk, optical Disk, CD-ROMs and Magneto-Optical Disk, Read-Only Memory (ROMs), Memory with random access (RAMs), EPROMs, EEPROMs, magnetic or optical Cards or any type of medium used to store electronic instructions NEN, each storage device having a computer system bus can be connected. The algorithms and displays presented herein are  not inherently related to any particular computer or apparatus. Various general purpose devices can be used with programs that support the or as may be appropriate, to build more specialized apparatus to carry out the required process steps to lead. The required structure for a variety of these machines will come from the following description. In addition, the present invention is not under Reference to any particular programming language. You will Welcome that a variety of programming languages can be used to support the To realize teachings of the invention as described herein.

The following terms are used in the following description. A de Finition for these different terms was included. The definitions are basically not a description of the state of the art, but should to facilitate understanding of the teachings of the present invention.

ABS coding ("ABS coding"):
A method of parallel entropy coding using simple codes (eg, run codes) for bit generation and probability estimation based on code words used (eg, table likelihood estimation). In one embodiment, the ABS encoding also includes a method of multiplexing and demultiplexing streams of different coders.

Alignment "):
The degree of displacement of the transform coefficients in one frequency band with respect to the other frequency bands.

arithmetic coding:
Shannon / Elias finite precision arithmetic, not necessarily a binary entropy coder.

B coding ("B coding"):
A binary entropy coder that uses a finite state machine (FSM) for compression. Unlike Huffman coding, the use of the finite state machine results in good binary symbol handling and is useful for a range of input probabilities.

binary entropy coder (binary entropy coder):
A noise-free coder that works on binary (yes / no) decisions, often called the most probable symbol (mps) and the least probable symbol (lps or leat probable symbol) be expressed.

Binary style ("binary-style"):
Encoding style with edge-fill or edge-fill Gray encoding of the pixels and a specific context model.

Binary style context model:
A context model for bi-level and bi-level and bounded-level image data.

Bit significance ("bit-significance"):
A number representation, similar to sign and magnitude, with head bits followed by the sign bit, followed by tail bits, if any. Embedding encodes in bit-level order with respect to this representation.

child-based order:
A scanning order by a two-dimensional image. It is similar to raster ordering except that the scanning works on two-by-two blocks. Consider scanning a "parent" frequency band in raster order. Each coefficient will have four children. These children are listed from the top left, top right, bottom left, and bottom right followed by the next parent and the next set of four children, and so on, to the end of the line. Then the processing returns to the next two lines and finally ends in the lower right corner. No lines are skipped. A child-based order is also referred to as a 2 × 2 block order.

Coefficient ("coefficient"):
Components after the transformation.

Components ("components"):
Components of the picture. The components form the pixels. For example, the red, green, and blue bands represent component bands. Each individual pixel is made up of red, green, and blue components. Components and component bands may contain any type of information that has a spatial imprint on the image.

Context Model:
Causally available information relative to the currently-to-be-coded bit representing historically learned information about the current bit, allowing a conditional probability estimate for entropy coding. For binary images, one possible context for a pixel is the previous two pixels in the same row and three pixels from the previous row.

Decomposition level:
Place in the wavelet decomposition pyramid. This is directly related to the resolution.

efficient transformation:
Transformation that achieves the best energy compression in the coefficients, while the minimum number of bits is used to represent those coefficients.

embedded context model:
A context model that separates the context bins and results in levels of importance in such a way that effective lossy compression is obtained if the more important values are preserved.

embedded with ordering ("embedded with ordering"):
A special case of embedded context models, where there is no explicit marking or mentioning of importance, but rather the compressed data is arranged so that the most important data is ahead.

embedded quantization (embedded quantization):
Quantization implemented by the code stream. For example, if the importance levels are placed in order, from the most important to the least important, then quantization is accomplished by simply truncating the code stream. The same functionality results in tags or markers, markers, pointers or pointers, or other signaling. Multiple quantizations can be performed on a decoded image, but only embedded quantization can be performed at encode time.

Entropy coder ("entropy code"):
A device that encodes or decodes a current bit based on a probability estimate. An entropy coder may also be referred to herein as a multicontext bi-entropy coder. The context of the current bit is some chosen configuration of "near" bits and allows a probability estimate for the best representation of the current bit (or more bits). In one embodiment, an entropy coder may include a binary coder, a parallel run-length coder, or a Huffman coder.

Entry point:
A point in the coded data starting with a known coding state. The encoder can start encoding at this point without decoding the previous data. In most cases, this requires the context and binary entropy coder to be reset to an initial state. The coded data for each coding unit starts at an entry point.

Fixed-length:
A system that converts a specific block of data into a specific block of compressed data, e.g. BTC (block clipping) and certain forms of VQ (vector quantization). Fixed-length codes are used for fixed rates and fixed-size applications, but Rate Distortion capability (see, e.g., Anneal K. Jain, "Principalities of Digital Image Processing", Prentice Hall, 1989), is often poor compared to variable rate systems.

Fixed rate ("fixed-rate"):
An application or system that maintains a certain pixel rate and has a narrow bandwidth channel. In one embodiment, to achieve this goal, local average compression is achieved rather than global average compression. For example, MPEG requires a fixed rate.

Fixed-size:
An application or system that includes a limited size buffer. In one embodiment, to achieve this goal, a global average compression is achieved, e.g. B. a print buffer. (The application can be a fixed rate, a fixed size application or an application with both).

Frequency band:
Each frequency describes a set of coefficients resulting from the same sequence of filter operations.

Head bits:
A bit significance representation, the header bits represent the carry bits from the most significant to most significant and including the first non-zero bit.

Huffman encoder ("Huffman Coder"):
In general, a fixed-length code that generates an integer number of bits for each symbol.

Importance levels:
A unit of encoded data that corresponds to the embedded data before it compresses an entire bit-level. The importance level includes all appropriate bit levels from the different coefficient frequency bands.

LPS (Least Probable Symbol) ("LPS (Least Probable Symbol)"):
The result of a binary decision with less than 50% probability. If two results are equally probable, it is unimportant what is called MPS or LPS as long as both the encoder and decoder perform the same designation.

Lossless / noise free / reversible coding:
Compressing data in a way that allows for a perfect reconstruction of the original data.

Lossy coding:
Coding data that does not guarantee perfect reconstruction of the original data. The changes to the original data may be made in such a manner that they are not visually objectionable or detectable. Often a fixed rate is possible.

MPS (Most Probable Symbol) ("MPS (Most Probable Symbol)"):
The result or result of a binary decision with more than 50% probability.

Overlapped transform:
A transformation where a single source point contributes to multiple coefficients of the same frequency. Examples are many wavelets and the overlapped orthogonal transform (LOT).

Parent coefficient ("parent coefficient"):
The coefficient or pixel in the next higher pyramid level that covers the same image space as the current coefficient or pixel. For example, the parent for the 1SC coefficients are the 2SD coefficients that are the parent for the 3SD coefficients in FIG. 1A.

Probability Estimator / Module (Probability Estimation Machine / Module):
Part of a coding system that tracks the likelihood within a context or records its lane.

Progressive pixel depth:
A code stream ordered with deeper bit planes of data at full image resolution.

Progressive pyramidal ("progressive pyramidal"):
A sequence of resolutions where each lower resolution is a linear factor of 2 in each dimension (a factor of 4 in area).

Q-coder ("Q-coder"):
A binary arithmetic coder where additions for multiplications have been substituted and probabilities have been constrained to discrete values and probability estimates are updated as bits are output.

Raster order:
A scanning order by a two-dimensional image. It starts in the upper left corner, moves from left to right, then returns to the left side of the next line, finally ending in the lower right corner. No lines are skipped.

Reversible transformation ("reversible transform"):
In one embodiment, a reversible transformation is an efficient transformation implemented with integer arithmetic whose compressed results can be constructed to the original values re.

Tail bits (or tail) (tail-bits (or tail)):
A bit significance representation, the tail bits represent magnitude bits that are less significant than the non-zero most significant bits.

Tile data segment ("tile data segment"):
Section of the code stream that completely describes a coding unit. "Tile" can be understood as a block or group.

TS transformation ("TS-transform"):
Two-Six Transformation, a specific reversible wavelet filter pair with a 2-tap low-pass analysis and a 6-tap high pass analysis filter. The synthesis filters represent quadrature mirrors ("quadrature mirror") of the analysis filter.

TT transformation ("TT-transform"):
A two-ten transform, a specific reversible wavelet filter pair with a 2-tap low-pass analysis and a 10-tap high pass analysis filter. The synthesis filters ("Synthesis" filters) are quadrature mirrors of the analysis filters.

United lossless / lossy ("unified lossless / lossy"):
The same compression system provides a code stream capable of lossless or lossy reconstruction. In one embodiment of the present invention, the code stream is capable of both without making any adjustments to or commands to the encoder.

Wavelet filters ("wavelet filters"):
The high and low pass synthesis and analysis filters used in the wavelet transform.

Wavelet transformation ("wavelet transform"):
A transformation with both "frequency" and "time (or space)" domain constraints. In one embodiment, it represents a transformation that includes a high pass filter and a low pass filter. The resulting coefficients are decimated by two (critically filtered) and the filters are applied to the low-pass coefficients.

Wavelet trees ("wavelet trees"):
The coefficients and the pixels related to a single coefficient in the SS portion of the highest level wavelet decomposition. The number of coefficients represents a function of the number of levels. Figure 1A shows the coefficients contained in a wavelet tree. The span of a wavelet tree depends on the number of decomposition levels. For example, with one level of decomposition, a wavelet tree spans four pixels, with two levels it spans 16 and so on. Table 1 below shows the number of pixels that are affected by a wavelet tree for different levels. In two dimensions, each wavelet tree includes three sub-trees called SD, DD, and DS.

Span of a wavelet tree for different levels of decompression

Span of a wavelet tree for different levels of decompression

The present invention provides a compression / decompression system a coding section and a decoding section. The coding section is for the Coding the input data responsibly to produce compressed data  while the decoding section is responsible for decoding previously coded data is verbally to a reconstructed version of the original input data produce. The input data may include a variety of data types, such as: B. Image data (still images or video images), audio data, etc. In one embodiment is the data digital signal data; however, digitized analogs are Data, text data formats and other formats possible. The source of the data for the Coding section and / or the decoding section may be a memory or a channel.

In the present invention, elements of the coding section and / or the Decoding section implemented in hardware or software, such as Those used in a computer system. The present The invention is a lossless compression / decompression system The present invention may also be configured to be lossy pression / decompression.

The system of the present invention uses fast lossy / lossless Compression by reversible wavelets, which will be described in more detail below. The system may have a printer, e.g. B. include a laser printer. On an off For example, the printer uses a low-cost hard disk to make a processed hard disk Save the amount of memory needed with expensive memory random access (RAM) is reduced. The compression is used to the limited bandwidth of the hard disk or storage device to the larger one Bandwidth required by the press to adjust. The coding techno Logic of the present invention meets the high speed, real-time requirement ments of the printing machine, while the present invention is either an ex Cellular lossless or lossy compression provides, as by the Image characteristics and the discontinuous nature of the hard disk are required.

The following detailed description provides a general overview of the Kom reversible wavelet compression, a compressed frame memory application,  a color laser printer and embodiments of a printer chip. The Aufberei The printer uses a hard disk to store. Because the Hard drive is slower than the printing press, the compression is used to to make a rate adjustment. An ad list technology can as well used to store the memory required during processing to decrease. A rendering machine based on an ad list allows it the compression system to handle bands of the image independently. Remarkable is that although the present invention has been described in terms of a printer system ben, the present invention is applicable to other systems, the Kom Pression and / or decompression subsystems included as parts thereof.

Also herein, an embedded unified lossless becomes described it / lossy compression system. The embedded characteristic of the system allows the quality by the transfer rate of the disk or Disk is determined. For slightly compressed pictures (eg most documents with Text and / or line drawing) a lossless compression is achieved. For more difficult to compress images (eg documents with noisy natural small images and / or halftones) becomes lossy compression higher Quality achieved.

For a description of a system or systems that are both lossless Compression as well as lossy compression of high quality of color See, for example, U.S. Patent Application Serial No. 08 / 642,518, filed on Apr May 3, 1996, entitled "Compression and Decompression with Wavelet Style and Binary Style Including Quantization by Device Dependent Parser, "and on the U.S. Patent Application No. 08 / 436,662, filed May 8, 1995, entitled "Method and Apparatus for Reversible Color Conversion ".

Reversible wavelets

The present invention uses compression by reversible wavelets.

Wavelet decomposition

The present invention initially performs a decomposition of an image (in the form of image data) or other data signal by reversible wavelets be used. In the present invention, a reversible wavelet trans Formation an implementation of an exact reconstruction system in integer Arith metic, so that a signal with integer coefficients recovered without loss can be. An efficient reversible transformation is one with a transforma tion matrix whose determinant is 1 (or almost 1).

Through the use of reversible wavelets, the present invention is in the Able to provide lossless compression with finite precision arithmetic. The results obtained by applying the reversible wavelet transform on the image data are generated are a series of coefficients.

The reversed wavelet transform of the present invention can be implemented be used by using a set of filters. In one embodiment the filters are a 2-tap low pass filter and a 6 tap high pass-filter to implement a transformation, referred to herein as TS-Trans formation or 2,6-transformation is called. In another embodiment form, the filters are a 2-tap low-pass filter and a 10-tap high pass filter to implement a transformation, referred to herein as a TT transformation or 2,10 transformation is called. These filters can can be implemented by adding only addition and subtraction operations (plus hardwa rewired bit shift).

The TT transformation has at least one advantage and at least one disadvantage towards the TS transformation. An advantage is that they have a better comm  Pression provides as the TS transformation. The disadvantage of TT transformation is that the longer 10-tap filter requires more hardware.

Two-dimensional wavelet decomposition

By using low-pass and high-pass filters in the present invention, multiple resolution decomposition is performed. The number of levels of decomposition is variable and may be any number; however, the current number of decomposition levels is equal to 2 to 8 levels. The maximum number of levels is log _{2 of} the maximum length or width of the input.

The most general way to transform with two-dimensional data perform such. As a picture, lies therein, the one-dimensional filter separately to apply, d. H. along the lines and then along the columns. The first level decomposition results in four different coefficient bands, referred to herein as SS, DS, SD and DD. The letters refer to smooth (S for "Smooth") and Detail (D) filters defined above, the respective low (L for "Low") and high (H for "high") pass filters. Consequently, that exists SS band of coefficients from the smooth filters in both the row direction and in the column direction.

Each frequency subband in a wavelet decomposition can be further decomposed. The The most common practice is to further decompose only the SS frequency subband. you may further decomposition of the SS frequency subband into each decomposition level include when each is generated. Such a multiple decomposition is called called pyramidal decomposition. The terms SS, SD, DS, DD and the Divisional level numbers denote each decomposition.

It is noteworthy that neither with the TS or the TT transformation of the present In the invention, the pyramidal decomposition does not increase the coefficient size.  

If the reversible wavelet transform is applied recursively to an image, The first level of decomposition works at the finest detail or the finest Resolution. At a first decomposition level, the image is divided into four subpictures (e.g. Subbands) decomposed. Each subband represents a band of spatial frequencies. The first level subbands are referred to as 1SS, 1SD, 1DS and 1DD. The Process of decomposing the original image contains a sub-scan with two in both horizontal and vertical dimension, so that the subbands first Levels 1SS, 1SD, 1DS and 1DD each have a quarter of the number of coefficients how the input pixels (or coefficients) of the image have.

The subband 1SS simultaneously contains low frequency horizontal and Low-frequency vertical information. Typically, a lot of the picture is energy concentrated in this subband (for the concept of energy see the above mentioned book by Anneal K. Jain ibid., see there in particular the terms "energy compaction "and" energy conservation "). The sub-band 1SD contains a low frequency horizontal and high frequency vertical information (eg horizontal Edge information or edge information or "edge" information). The subband 1DS contains high-frequency horizontal information and a low-frequency ver tical information (eg vertical edge information). The subband 1DD contains high-frequency horizontal information and high-frequency vertical information (eg, structural or diagonal edge information).

Each of the successive second, third and fourth lower decomposition levels is generated by decomposing the lower frequency SS subband of the previous level. This first-level subband 1SS is decomposed to produce sub-bands of 2SS, 2SD, 2DS and 2DD of the moderately detailed second level. Similarly, the sub-band 2SS is decomposed to produce roughly-detailed sub-bands 3SS, 3SD, 3DS, and 3DD of the third level. Also, the sub-band SS _{2 is} decomposed to produce coarse detailed sub-bands 4SS, 4SD, 4DS and 4DD of the third level. Due to the subsampling by two, every second level sub-band becomes one-sixteenth the size of the original picture. Each sample (eg pixel) at this level represents a moderate detail in the original image and a moderately detailed representation of the original image at the same location, respectively. Similarly, every third level sub-band is 1/64 the size of the original picture. Each pixel at this level corresponds to a relatively coarse detail in the original image and a coarse-grained reproduction of the original image at the same location. Likewise, every fourth level sub-band is 1/256 of the size of the original picture.

Because the decomposed images are physically smaller than that due to undersampling Original image, the same memory used to store the original image is used to store all decomposed subbands. With others In words, the original image and the decomposed subbands 1SS and 2SS are eliminated or deleted and not stored in a three-level decomposition.

Although only four subband decomposition levels are described, additional Levels developed in accordance with the requirements of a particular system become. Likewise, with other transformations, such as. B. a DCT or linearly spaced subbands, different parent-child ratios be determined.

It is noteworthy that a pyramidal decomposition does not match the coefficient size increases the wavelet filters of the present invention.

In other embodiments, other subbands may be in addition to the SS be disassembled as well.

Tree structure of the wavelets

There is a natural and useful tree structure for wavelet coefficients at one pyramidal decomposition. One result of the subband decomposition is a single SS freef quency subband corresponding to the last level of a decomposition. On the other There are as many SD, DS and DD bands as the number of levels. The Tree structure sets the parent of a coefficient in a frequency band such that it is a coefficient in a same frequency band at a lower resolution and related to the same spatial location.

In the present invention, each tree comprises the SS coefficients and three Subtrees, namely the DS, SD and DD subtrees. The processing of The present invention is typically performed on three subtrees. The Root of each tree is a pure smoothing coefficient. For a two-dimensional les signal, such. For example, a picture, there are three subtrees, each with four children. The Tree is hierarchically not limited to two-dimensional signals. For example, has for a one-dimensional signal, every sub-tree is a child. Higher dimensions result from the one-dimensional and two-dimensional case.

The process of multi-resolution decomposition can be done using a filter system be performed. Regarding a two-dimensional two-level transforma tion implemented using one-dimensional exemplary filters, see US Patent Application No. 08 / 498,695, filed June 30, 1995, with the Title "Method and Apparatus for Compression Using Reversible Wavelet Transforms and to Embedded Codestream "and US Patent Application No. 08 / 498,036 on June 30, 1995, entitled "Reversible Wavelet Transform and Embedded Codestream manipulation ".

Perform the forward wavelet transform

In the present invention, the wavelet transform is done with two 1D Opera tions, first horizontally, then vertically. In one embodiment leads  one piece of hardware performs the horizontal operation while another performs the vertical one Performs operations.

The number of levels determines the number of iterations. In one execution form a four-level decomposition is performed by the TT transformation is used in both the horizontal and in the vertical direction. at In another embodiment, the four-level decomposition is performed by four DS transformations are used instead.

The transformation of the present invention is very much in terms of calculation efficient. In one embodiment, the present invention arranges the calculations which are performed by the transformation to the amount of both a on-chip memory as well as one not on one Chip (Official Communication Chip Memory) and the required Reduce bandwidth.

Calculation orders or sequences of calculation and data flow for the transformation

As described above, in the present invention, the base unit is used Calculation of the transformation of the wavelet tree. Take a four-level trans formation, each wavelet tree represents a 16x16 block of pixels 16 × 16 block of pixels (all four components for CMYK images) is transposed into the trans formation of the present invention and all possible calculations, to generate coefficients are performed. (The inverse is similar, a 16 × 16 block with coefficients for each component is entered and all possible chen calculations are performed.) Since the present invention an overlapping te transformation uses the information from previous, adjacent Trees stored and used in the calculations. The border between the current wavelet tree and the previous adjacent information  referred to herein as a hem. The information that is saved about a hem, To carry out the transformation of the present invention will be described below described in detail.

Order of wavelet trees

The order of wavelet trees to calculate the transformation is important because in certain applications (e.g., printing) encoding units of the present invention have a large width and a small height. In one embodiment each coding unit 4096 × 256 pixels.

In the following discussion, each of the encoding units contains 4096x256 pixels. However, it is noteworthy that the ordering, which will be described below, applicable to coding units with other sizes. Fig. 2A shows an order similar to a raster order. This order is referred to herein as a long-tail-transformation order. Referring to Fig. 2A, the thick lines indicate the amount of data retained over the seams and indicate how much memory is required to compute the transformation. This data is proportional to a wavelet tree for the horizontal transformation but to the width of the image (4096 in this example) for the vertical transformation. The amount of memory for the data may require the use of external memory. However, because of the closeness of the rasterization during the inverse transform, the data may be output from the transform (for example, to a printer in a printer application) as soon as a horizontal row of wavelet trees needs to be converted to pixels.

Fig. 2B shows an alternate embodiment of an order referred to herein as a short trim order. The memory for the seams is proportional to the height of the encoding unit (256 in this example) for the horizontal transformation and a wavelet tree for the vertical transformation. This significantly reduces the amount of memory required, making storage on a chip (on-chip memory) practical.

Fig. 2C shows an alternative short seam order. At the expense of memory proportional to another wavelet tree, the number of successive pixels processed in raster order is increased. These alternative or similar alternatives may allow more efficient use of a fast page mode or RAM for the accelerated data output or an EDO RAM in the band buffer with little overhead in the seam memory. Efficiency is gained by the fact that most of the memory is desired or optimized for access to adjacent memory locations. Therefore, any increase in the use of adjacent memory accesses due to the sear sequence results in more efficient memory usage.

Calculation for a wavelet tree

The following equations set both the TS transform and the TT transformation fixed. For an input x (n), the output of the low-pass filter, the smooth signal s (n), and the high-pass filter, the detailed signal d (n), calculated as is shown in the following equation.

The inverse transformation is shown in the following equation.

where p (n) is calculated as follows:

p (n) = d (n) -t (n).

The TS transformation and the TT transformation differ in the definition of t (n). For the TS transformation:

For the TT transformation, the following applies:

It is noteworthy that in the following discussion the notation means after Round down or cut off and is sometimes referred to as ground function net.

The TS transformation

The effect of using the six-tap filter and a two-tap filter at even intervals is that three pieces of information are stored have to. The six-tap filter requires two delays. The two-tap Filter requires a delay, so that its result with respect to the result of Six-tap filter can be centered. In particular, two s (⚫) values and a d (⚫) value or a partial result from the d (⚫) calculation are stored. A Storage of these values is identical regardless of whether or not certain filter operation crosses a hem or not.

Figures 3A through 3H show the result of each application of the TS transform filter for a four-level transform on a wavelet tree of the present invention. In these figures, the output of the low-pass filter is referred to as "s" for "smooth". The output of the high pass filter is referred to as "d" for detail. The "B" denotes an intermediate value used to calculate a "d"; it is an x (2n) -x (2n + 1) value. The "B" values are used during the pre-transformation; for inverse transformation, a "d" value that is not used for any calculations is stored in its place. The notation "sd" indicates that a coefficient is the result of first a horizontal low-pass filter and then a vertical high-pass filter. The meanings of "ds", "dd", "ss", "dB" and "sB" are similar. The bold or bold rectangle corresponds to the 256 input pixels. The shaded "s", "ds" and "ss" values are calculated with a previous wavelet tree and used for use in the current wavelet tree.

With regard to the forward transformation, the "ss" coefficients of the previous level going to the inputs to the levels 2, 3 and 4 of the transformation. The "sd", "ds" and "dd" coefficients are done so that they are output can if they are calculated. The inverse transformation performs all calculations in one concerning the levels (the fourth level first, then the third, second and third finally the first one) and in terms of vertical (first) and horizontal (second)  Order through. Within one pass of the transformation is the data flow from forward and inversely identical, but the calculation is different.

TS transform hardware

Fig. 4A is a block diagram of one embodiment of a forward / inverse filter unit for use in the implementation of the one-dimensional filters. Only memory and calculation units are shown, hardware wired shifts are not shown. Referring to Figure 4A, a filter unit 4000 handles both forward and inverse transformation. Alternative embodiments may be used to separate units for forward and inverse transformation. For the forward transformation, inputs of the size "n" are used and the "s" and "d" outputs are generated. For inverse transformation, the "s" and "d" inputs are used and the other outputs are generated.

The adder 4001 is connected to receive n-bit inputs and to add them together to produce an output x (2n + 2) + x (2n + 3). The adder 4002 subtracts an n-bit input from the other and outputs the quantity x (2n + 2) -x (2n + 3). The outputs of the adders 4001 and 4002 are respectively connected to one input of the multiplexers (abbreviated to "mux") 4003 and 4004, respectively. The other inputs to the multiplexers 4003 and 4004 are connected to receive the s and d inputs, respectively. In one embodiment, the s input is n bits while the d input is greater than n bits.

The output of the multiplexers 4003 and 4004 is controlled by a forward / inverse control signal indicating whether the filter is in the forward or inverse mode. In either the forward or inverse mode, the output of the multiplexer 4003 is s (n + 1). On the other hand, the output of the multiplexer 4004 is p (n + 1) in the forward mode and d (n + 1) in the inverse mode.

The outputs from the multiplexers 4003 and 4004 along with a feedback of an s (n) output from the multiplexer 4006 are coupled to the inputs of the register file 4005 . The register file 4005 contains the entries for each component for the length of a wavelet tree. The data is typically passed through the register file 4005 . Based on the spatial location, the inputs to register 4005 are delayed to the output. An address input controls the outputs of the register file 4005 . In one embodiment, the register file 4005 includes two memory banks with one port per bank and is used in a ping-pong style, with back and forth access between the two memory banks.

The output of the multiplexer 4003 also represents the s output of the filter unit.

The outputs of the register file 4005 are coupled to the inputs of the multiplexer 4006 along with the externally buffered data at a hem buffer in 4020. The output 4006 A includes s (n-1), which is a twice-delayed version of the output from the multiplexer 4003 . The output 4006 B includes s (n), which is a delayed version of s (n + 1). The output 4006 C includes p (n) for the forward mode and d (n) for the inverse mode. The multiplexer 4006 is also controlled to provide externally buffered seam data at the seam buffer output 4021 .

The output 4006 C is connected to an input of the adders 4008 and 4009 . The other input to the adders 4008 and 4009 is the output of the multiplexer 4015 . The multiplexer 4015 handles the boundary conditions. On a boundary, the multiplexer outputs 4015 , like the zero hardwired to one of its inputs. The hard-wired zero can be changed to use other values in some embodiments. In a non-boundary condition, the multiplexer 4015 outputs t (n) output from the adder 4007 connected to s (n + 1) on an input to s (n-1) to another input by subtracting s (n-1) from s (n + 1).

The adder 4008 adds the output 4006 C from the multiplexer 4006 to the output from the multiplexer 4015 to produce the d output of the filter unit.

The adder 4009 subtracts the output of 4006 C from the multiplexer 4006 from the output from the multiplexer 4015 . The output of the adder 4009 is added to s (n) on the output 4006 B of the multiplexer 4006 by the adder 4010 to produce an n-bit output of the filter unit. The output 4009 is also subtracted from s (n) of the output 4006 B from the multiplexer 4006 by the adder 4011 , which outputs the other n-bit output of the filter unit in the inverse direction.

For seams that are longer than a wavelet tree, seam data may be stored in on-chip static RAM (SRAM) or external memory rather than a register file 4005 . Multiplexer 4006 provides access to and from this additional seam memory.

The largest hardware expenditure or the most hardware costs of the filter unit 4000 are due to the register file 4005 . The total amount of memory needed depends on the number of filter units. In one embodiment, a total of 60 locations are needed to store three values (s, s, d or ss, ss, sd). If more filter units are used, the required memory size is smaller. Therefore, the hardware costs or the hardware costs for the use of multiple filter units are low.

A fast inverse transformation allows less latency between the ends the decoding and start of the file output operation, such. B. printing. This reduces and allows the memory needed for decompression larger encoding units. A fast forward transformation allows the Filter can handle discontinuities in the data or data bursts, if one greater bandwidth is available, which in turn allows the transformation provides more data to the context model when looking forward to it  textmodell allows to process the data quickly. If the forward transformation does not keep up with the contextual model during coding becomes one Disk bandwidth or disk bandwidth is wasted during encoding, causing the Delayed time to the beginning of printing. Likewise, the controller and the Data flow through the use of multiple filters are simplified.

FIG. 4B is a block diagram of an embodiment of a forward transform the first level according to the present invention. Referring to FIG. 4B, two filter units 401 and 402 , such as those shown in FIG . For example, those shown in Fig. 4A undergo the first level of transformation. The filter unit 401 performs level 1 horizontal transformation while the filter unit 402 performs level 1 vertical transformation. In one embodiment, the first level of transformation operates on 2 × 2 blocks of the input. Four registers 403 to 406 function as delay units to delay spending of the filtering unit four hundred and first This is called a child-based order. Register 403 receives the S output of filter unit 401 while registers 404 and 405 receive the d output. The output of the register 404 is connected to the input of the register 406 . The outputs of the registers 403 and 406 are closed to the inputs of the multiplexer 407 , whereas the s output of the filter unit 401 and the output of the register 405 are connected to the inputs of the multiplexer 408 . Two multiplexers 407 and 408 select inputs to the filter unit 402 from those of the delayed coefficient output from the filter unit 401 .

The filter unit 401 operates consecutively on two vertically adjacent pairs of inputs. This produces four coefficients that are inputted with the proper delay, which is provided from the registers 403 to 406 for each component in the filter unit 402nd Three of these four results can be output immediately, the "ss" output is processed further.

The forward transmission according to the first level operates on groups of four pixels which are in 2 × 2 groupings. For discussion purposes, the first row or row should contain pixels a and b, while the second row should contain pixels c and d. The operation of the first level four transformation in Fig. 4B is as follows. During the first cycle, the horizontal transformation is applied to the a and b pixels processed by the filter unit 401 . The filter unit 401 generates the S _from what is stored in register 403, and D _on what is stored in register 404 and 405th In the next cycle, the pixels c and d are processed by the filter unit 401 to perform the horizontal transformation. As a result of the application of the filter unit 401 , S _cd stored in the register 403 and D _cd stored in the registers 404 and 405 are generated. In this cycle, S _ab from register 403 and S _cd from register 405 are processed by filter unit 402 , which performs a vertical pass of the transform and generates SS and SD. Likewise, during the second cycle, the value moves _from D, from the register 404 to the register 406th In the next cycle, the value D _ab from register 406 and D _cd from 405 are processed by filter unit 402 , which generates the outputs DS and DD. In the same cycle, filter unit 401 processes the a and b pixels from the next 2 x 2 block.

Fig. 5 is a block diagram of one embodiment of a forward transform according to the present invention. Referring to Fig. 5, level 1 transformation 502 performs the level 1 transformation. In one embodiment, the level 1 transformation comprises the level 1 transformation of FIG. 4B. The filter unit 505 handles the levels 2, 3 and 4 of the transformation. A memory 503 stores "ss" coefficients until sufficient coefficients are available to perform the transformation. The number of coefficients to be stored is shown in Table 2 below. (Each digit stores a coefficient for each component).

Table 2 - "ss" delay memory

The ordering unit 504 multiplexes the correct entries into the filter unit 505 . The input buffer 501 and the output buffer 506 may be required to tune between the transfer order needed by the transform and the order needed by the band buffer or the context model.

For the inverse transformation, the data flow is reversed, with the level 4 inverse transformation followed by the level 3, level 2 and level 1 transformation performed in an order. The output of the level 2 transformation is input to the level 1 transformation first level hardware 502 . Likewise, vertical filtering is performed before horizontal filtering. Since the horizontal and vertical filtering are identical except that one direction requires access to additional memories for the seams, inversion of the data flow can be performed with a small amount of multiplexing. Prior to the inverse transform, the two-byte coefficients must be converted from the embedded form with two signaling bits to normal two's complement numbers.

The elements shown in Figs. 4B and 5 can also be used for the TT transformations.

Transformations timing

The transformation timing of the forward transformation of Fig. 5 is based on the timing of the individual filter units. The first filter unit, the filter unit 401 , calculates horizontal level 1 transforms, while the second filter unit, the filter unit 402 , computes vertical level 1 transforms. The third filter unit, the filter unit 505 , calculates transforms for levels 2 to 4 or it is idle.

In one embodiment, the third filter unit ( 505 ), when not idle, computes horizontal transforms during even clock cycles and vertical transforms during odd clock cycles. The timing for inverse transformation is similar (but vice versa).

In the following example, 2 × 2 blocks within a wavelet tree will be in the Transposed transposed a raster order. It is noteworthy that a small Input / output (I / O) buffering might be required to get a fast-paged page support mode / EDO DRAM if 2 × 2 blocks within a wavelet tree instead be processed in raster order.

Fig. 6 is a timing chart for the case where coefficients are output. The following timing or timing applies to each pixel. There are four components per pixel.

Since it is more common for a person skilled in the art to read so-called pseudo codes in the English language, the pseudo code reproduced above in German is again reproduced in English:

TT 99999 00070 552 001000280000000200012000285919988800040 0002019819405 00004 99880 transformation

Figs. 7A to 7H show the results (outputs) of each one-dimensional filter operation of the TT transformation. A rectangle displays coefficients in a single wavelet tree that corresponds to the input pixels that are currently being processed. Shading indicates coefficients stored by the previous tree. The values labeled "B" represent intermediate results that are stored (and represent the difference between adjacent samples or values). The TT transformation is similar to the TS transformation, but requires more memory.

Fig. 8 is a block diagram of a 10-tap forward / inverse filter unit. It is noteworthy that hardware wired shifts and round offsets are not shown in order to avoid spoiling the present invention. It is noteworthy that the multiplexer 806 in Figure 8 also uses "mirroring" at transformation boundaries can be. It is also necessary for an implementation of the mirroring to make the "d" input 0 and multiplex the s (n + 2) input of the overlap unit.

Referring to Fig. 8, adders 801 and 802 are connected to receive the 2 n-bit inputs during the forward pass of the filter unit. The adder 801 adds the 2-n-bit inputs and outputs a value connected to an input of the multiplexer 803 . The adder 802 subtracts one input from the other, producing its output to an input of the multiplexer 804 . The multiplexers 803 and 804 are also connected to receive the s and d inputs, respectively, for the inverse-mode operation of the filter unit. The outputs of multiplexer 803 represent an n-bit input equal to s (n + 2) while the output of multiplexer 804 corresponds to an n + 1-bit input, p (n + 2) for forward and d (n + 2) for the inverse pass.

Both outputs of the multiplexers 803 and 804 are connected to the inputs of the memory 805 . Similarly, the inputs of the memory 805 are connected to the outputs 806 A and 806 D to F output from the multiplexer 806 . The memory 805 delays the inputs to its outputs based on the spatial location. In one embodiment, memory 805 includes a register file or SRAM connected in a ping-pong fashion with two banks or one port per bank. An address is connected to an input of the memory to control the outputs generated for the multiplexer 806 . In one embodiment, the address stores 16 or 28 digits per component.

The outputs of the memory 805 are connected to the inputs of the multiplexer 806 along with the external buffer data received from the seam buffer at 820. The output 806 A of the multiplexer 806 comprises s (n + 1), which is a once delayed version of s (n + 2) at the output from the multiplexer 803 . The output 806 B of the multiplexer 806 comprises s (n), which is a twice delayed version of the output of the multiplexer 803 . The output 806 C of the multiplexer 806 comprises p (n) for the forward pass, which is a twice delayed version of the output of the multiplexer 806 , and d (n) in the inverse pass, which is a twice delayed version of the output of the multiplexer 804 . Output 806 D includes s (n-2), which is a four-time delayed version of the output of multiplexer 803 . The output 806 E of the multiplexer 806 comprises s (n-1) which is three times delayed from the output of the multiplexer 803 . Finally, the output 806 includes F t (n + 1) in the forward pass, which is a once delayed version of the output of the multiplexer 804 , and d (n + 1) for the inverse pass, which is a once delayed version of the output of the multiplexer 804 is.

The overlap unit 807 is connected to receive the output of the multiplexer 803 along with the outputs 806 A, D and E from the multiplexer 806 . In response to these inputs, the overlap unit 807 generates t (n). An embodiment of the overlap unit is described in FIG. 9.

The output of the overlap unit 807 , t (n), is connected to an input of the adders 808 and 809 . The adder 808 adds t (n) to the output 806 C of the multiplexer 806 to produce the D output of the filter unit. The adder 809 sub subtracts the output 806 C of the multiplexer 806 from t (n). The output of the adder 809 is connected to an input of each of the adders 810 and 811 . The adder 810 adds the output of the adder 809 to the output 806 B of the multiplexer 806 to produce one of the n-bit outputs of the filter when operating as an inverse filter unit. The adder 811 subtracts the output of the adder 809 from the output 806 B of the multiplexer 806 to produce the other output of the filter unit when operating as an inverse filter.

Fig. 9 is a block diagram of an embodiment of the Überlappeinheit for the forward / inverse filter of FIG. 8. Referring to Fig. 9, the Überlappeinheit comprises adders 901-906, multipliers 907-909 and a divider 910th The multipliers and dividers may be hardware-wired shifters.

The overlap unit of Fig. 9 calculates t (n) for the TT transformation described above. Referring to Fig. 9, the adder 901 is connected to receive the s (n + 2) input and subtract it from the s (n-2) input, and generates an output which is coupled to an input of the adder 903 . The adder 902 is connected to receive the s (n-1) input and to subtract it from the s (n + 1) input. The output of the adder 902 is connected to the input of the multiplier 907 and multiplier 908 . The multiplier 907 multiplies its input by 2. In one embodiment, the multiplication is performed by shifting the bits to the left position. The output of multiplier 907 is closed to the other input of adder 903 .

The multiplier 908 multiplies the output of the adder 902 by 16. In one embodiment, the multiplication is performed by shifting the bits output from the adder 902 to the left four bit positions. The output of the multiplexer 908 is connected to an input of the adder 905 . The output of the adder 903 is connected to an input of the adder 904 and also to the input of the multiplexer 909 .

The multiplier 909 multiplies the output of the adder 903 by 2. In one embodiment, this multiplication is performed by shifting the bits output from the adder 903 to the left bit position. The output of multiplier 909 is connected to the other input of adder 904 . The output of the adder 904 is connected to the other input of the adder 905 . The output of the adder 905 is connected to an input of the adder 906 , which adds it to 32, which is a hardwired re-wired input. The output of the adder 906 is connected to the output of the divider 910 . Divider 910 divides the input by 64. In one embodiment, this division is accomplished by shifting the bits of the input to the right six bit positions. The output of divider 910 includes the t (n) output. It is noteworthy that Figure 9 shows each output with the current value on the lines.

It is noteworthy that both in the reversible TS transformation as well TT transformation, similar to the S transformation, implemented the low-pass filter so is that the span of the input signal x (n) is the same as that of the output signal s (n). That is, there is no growth in the smoothed out gear. If the input signal is b-bit low, then the smooth or smoothed one Output as well b bits. For example, if the signal is an 8-bit image, that is Output of the low-pass filter as well 8 bits. This is an important property for one pyramidal system, where the smooth output is further decompressed by e.g. B. successively applying the low-pass filter. In prior art systems  the spread of the output signal is greater than that of the input signal, whereby successive or successive applications of the filter are difficult. As well There is no systemic error due to rounding in the integer implemen tions of transformation, so that all errors in a lossy system can be controlled or controlled by the quantization. Additionally points the low pass filter only taps on it, turning it into a non-overlapping filter do. This property is important for the hardware implementation.

Embedded ordering

In the present invention, the coefficients generated as a result of Wavelet decomposition generated, entropy-coded. In the present invention The coefficients initially undergo an embedded ordering in which the coefficients categorized in a visually significant order, or more generally with respect to the same error metric (eg distortion metric or Distorsionsmetrik). Error or distortion metrics include e.g. B. a spike error or mean squared error or mean square error (MSE). Additionally, ordering may be performed to provide a bit significance space location, a relevance in terms of database query and one direction (vertical, hori zontal, diagonal, etc.) to give preference.

The ordering of the data is performed to determine the embedded quantization of the To generate code stream. In the present invention, two ordering Systems uses: a first to order the coefficients and a second to the Order the binary values within a coefficient. The order of the present Invention generates a bitstream which is subsequently provided with a binary entropy coder is encoded.

Bit-significance representation

Most transform coefficients represent signed numbers, themselves if the original components are unsigned (any coefficient, which is output by at least one detail filter is signed). at In one embodiment, the embedded order is for binary values within a coefficient is used, an order bit plane bit plane. The Coefficients are output in a bit significance representation before encoding suppressed. The bit significance is a sign-magnitude representation where the sign bit, rather than being the most significant bit (MSB), with the first bit in magnitude is coded nonzero. That is, the sign bit follows the first bit Amount other than zero, rather than preceding all magnitude bits. Likewise, that will Sign bit considered that it is in the same bit plane as the most significant Magnitude bit not equal to zero.

The bit significance format represents a number using three sets of bits: head, tail, and sign. The header bits are all zero bits from the MSB up to and including the first nonzero magnitude bit. The bit plane in which the first non-zero magnitude bit occurs determines the significance of the coefficient. The set of tail bits includes the magnitude bits after the first non-zero magnitude bit up to the LSB. The sign bit simply denotes the sign, where 0 can represent a positive sign and 1 a negative sign. A number, such as ± 1 ⁿ , with a zero bit as the MSB, has only one header. A zero coefficient has no tail or sign bits. Table 3 shows all possible values for forming bit coefficients ranging from -7 to 8.

Table 3 - Bit significance representation for 4-bit values

In Table 3, the bit significance representation shown in each column includes or two bits. In the case of two bits, the first bit is the first 1-bit and will followed by the sign bit.

In the case where the values are non-negative integers, as shown e.g. For example, as regards the intensity of the pixels, the order that can be used is the bit-plane order or bit-plane order (eg, from the most significant to the least significant bit-plane). The embodiments where negative integer integer numbers are also allowed, the embedded order of the sign bit is the same as the first non-zero bit of the integer value of the integer. Therefore, the sign bit is ignored until a nonzero bit is encoded. If you use z. For example, a sign magnitude notation, the 16-bit number is -7:

1,000,000,000,000,111th

On a bit-plane basis, the first twelve decisions become "insignificant" or Be zero. The first 1-bit occurs at the thirteenth decision. Next will be the sign bit ("negative") is encoded. After the sign bit is encoded, processed the tail bits. The fifteenth and sixteenth decisions are respectively "1".

Since the coefficients are from the most significant bitplane to the least significant bit level, the number of bit-planes in the data must be determined. In the present invention this is accomplished by setting an upper bound on the amounts of coefficient values found by the data are found or derived from the depth of the image and the filter coefficients. If z. B. the upper limit is 149, then there are eight significant bits or eight bit planes. To speed up the software, a bit-plane encoder can not be used. In an alternative embodiment, a bitplane is encoded only if one Coefficient as a binary number becomes significant.

coefficients orientation

The present invention sets coefficients before bit-plane encoding other. This is because the coefficients in different Frequenzunterbän different frequencies that are similar to FFT or DCT. By aligning the coefficients, the present invention controls quantization. The less heavily quantized coefficients are directed towards the earlier ones  Bite planes aligned (eg moved to the left). Thus, these coefficients, if the stream is cut off, have more bits that set them than the more intense quantized coefficients.

In one embodiment, the coefficients for the best rate-distortion performance capability in terms of SNR ("Signal to Noise Ratio" or "Signal to Noise Ratio") There are many possible orientations or arrangements including one that is almost statistical Error metrics, such. B. MSE is. Alternatively, the orientation could be a psychovisu allow quantization of the coefficient data. The orientation has a significant influence on the evolution of image quality (or in other words on the rate ver distortion curve), but it has a negligible influence the final one Compression ratio of the lossless system. Other orientations can be one specific coefficient quantization, an area of interest fidelity co dieren ("Region of Interest" fidelity) or a resolution-progressive direction ("resolution progressive alignment").

The alignment may be signaled in the header of the compressed data or it can be fixed for a particular application (that is, the system has only one off direction). The orientation of the different-sized coefficients is known to both the encoder and the decoder and has no influence on the efficiency of the entropy coder.

The bit depths of the various coefficients in a two-level TS transform and a TT transform decomposition from a b-bit per pixel input image are shown in FIG . Fig. 12 illustrates one embodiment of the multiplier for the frequency band used for coefficient alignment in the present invention. To align the coefficients, the 1-DD coefficient size is used as a reference, and shifts are made with respect to that size. A shift of n represents a multiplication by 2 ⁿ .

In one embodiment, the coefficients with respect to the magnitude of the largest Coefficients shifted to align all the coefficients in the image produce. The aligned coefficients are then handled in bit planes, the Importance levels, from the most significant one level to the lowest significant importance level. The sign is with the last header bit of each coefficient. The sign bit is where the last header is inside, regardless of the level of importance last header is inside. It is important that the alignment is simply the order controls in which the bits are sent to the entropy encoder. In fact, one will Do not fill, move, save or encode extra zero bits guided.

Table 4 shows an embodiment of alignment numbers for aligning coefficients cient.

Table 4 - Coefficient orientation

The alignment of coefficients of different sizes is common to both the encoder as well as the decoder and has no influence on the efficiency of En tropiekodierers.

It is noteworthy that the coding units of the same data set differ Alignments can have.  

Order the code stream and the context model

Fig. 10 shows the ordering of the code stream and the ordering within a coding unit. Referring to Fig. 10, the header 1001 is followed by the encoding units 1002 in order from the top band to the bottom. (The header 1001 is optional in applications designed for a single image type.) Each encoding unit includes most important data 1003 , less important data 1004, and least importantly, data 1005 .

The context model determines both the order in which the data is encoded and the conditioning used for the specific bits of the data. The Ordering is considered first. The ordering of the data concerning the highest level has already been described above. The data is divided into "main data", what is interchangeably referred to herein as the main body or chunks becomes (MIC or "Most Important Chunk"), which is lossy in transformations is coded, and "less important data", which is interchangeable herein than the the least important part or least important parts (LIC or "Least Important Chunk), and in an embedded unified or coded lossless / lossy manner.

The order in which the coefficients are processed during each bit-plane is running from low resolution to high resolution (from low frequency to the high frequency). The coefficient subband coder within each bitplane runs from the high level (low resolution, low frequency) to the low Level (high resolution, high frequency). Within each frequency subband finds the coding takes place in a defined order or sequence. On an off The order may be a raster order, a 2 × 2 block Order, a serpentine order or tortuous order, a Peano-Abtast order ("Peano scan order") and so on.  

In the case of a four-level decomposition using the code stream of Fig. 3, the order is as follows:
4-SS, 4-DS, 4-SD, 4-DD, 3-DS, 3-SD, 3-DD, 2-DS, 2-SD, 2-DD, 1-DS, 1-SD, 1 DD.

An embodiment of the context model used in the present invention will be described below. This model uses bits within one Encoding unit based on the spatial and spectral dependence of the coefficients cient. The available binary values of the neighboring coefficients and the Parent coefficients can be used to create contexts. The However, contexts are more efficient for decoding and small in number Adaptation causal.

The present invention provides a context model to model the bitstream, by the coefficients in the embedded bit significance order for the binary entropy coder is generated.

Fig. 37 shows the neighborhood coefficients for each coefficient of a coding unit. Referring to Fig. 37, the neighborhood coefficients are referred to by obvious geographical designations (e.g., N = north, NE = northeast, NW = northwest, W = west, E = east, SE = southeast, etc.). Are a coefficient, such. For example, given P in Figure 37, and a current bit-plane, the context model may use any information from the entire coding unit before the given bit-plane. The parent coefficient of the present coefficient is also used for this context model.

The header bits are the most compressible data. Therefore, a large amount of context or conditioning is used to improve the compression. Rather than using the neighborhood or parent coefficient values to determine the context for the present bit of the present coefficient, the information is used on two signaling bits described in connection with Figure 13A. This information may be stored in memory or may be dynamically calculated by the neighborhood or parent coefficient.

Implement embedding for storage on a disc

One embodiment of the embedding scheme for the present invention is based on the fact that when starting to encode data, the whole Band buffer is full of data, so there is no extra space available the tape for use as memory. The present invention writes some of the less important data into the memory later embedded should be. In the present invention, the data would be embedded should, in the memory, and these are the less important data. The more important Data is coded directly. The least important data include a certain amount Number of least significant bits.

In one embodiment, a portion of each coefficient is returned to the Memory written for later coding, the head bits and tail bits must be known, as well as it must be known whether the sign bit is OK order was processed according to a correct Ensuring coding. In one embodiment, two or more Signaling bits (e.g., 3, 4, 5, etc.) are used to control the head, tail, and sign to display bit information.

In one embodiment, where 8-bit memory locations are used, two show Signal bits indicate the header, tail and sign bit information. The usage of two signaling bits allows the least important six importance levels are written back to the memory with two signaling bits. On Signaling bit indicates whether the most significant bit or the most significant bit of the  six importance levels is a head or tail bit. If the first signalis If this bit indicates that it is a header bit, then the second signaling bit is that Sign for the coefficient. On the other hand, if the first signaling Bit indicates that the most significant bit of data going back to memory is written, is a tail bit, then the second signaling bit is a free one signaling bit, which may contain additional tail information, such as. B., whether the most important tail bit is the first tail bit or a later tail bit.

Fig. 13A shows a coefficient which is divided into the main data 1301 called MIC and less important data 1302 called LIC. In one embodiment, the MIC comprises the six higher-order bits of each coefficient, while the LIC comprises the six lower-order bits. The most important data 1301 is sent to the context model to be coded immediately in a coefficient order. No buffering in external memory is required for this data. The less important data 1302 is written into memory (e.g., RAM) for later encoding and nesting in this order. In addition, the two signaling bits in the data are written to memory. The signaling bit 1303 indicates whether the most significant bit in the data written to the memory is a header. The signaling bit 1304 indicates the sign for the coefficient or shows if the tail bit is included in the data or not. It is noteworthy that the signaling bits may be stored in a concatenated manner with the less important data 1302 or stored in another memory or other memory location associated with the memory that stores less important data 1302 such that the signaling bits which can be identified with each section of a coefficient.

Examples in Table 5 show the use of two signaling bits. The columns of the body of Table 5 are intended to align with the data types in Figure 13A. The sign bits are denoted by "S", the tail bits are denoted by "T", the bits to be ignored are designated by "x", the value of the tail one bit is denoted by "h" or "t". In Table 5, h = 0 and t = 1 for the signaling bits. In an alternative embodiment, the conventio NEN be reversed. In one embodiment, a sign bit in Table 5 indicates 0 with a positive sign, while a sign bit in Table 5 indicates 1 with a negative sign. An opposite assignment can be used. It is noteworthy that the sign bit is always held with the first "on" bit, so that it can be coded for embedding at the same time.

Table 5

In Table 5 above, "T" denotes the corresponding bit in the coefficient and can be either 0 or 1.

In one embodiment, while decoding, the most important Data are decoded, they are written to memory, and at the same time the correct two signaling bits are written to memory to store for initialize storing less important data. (Depending on the  Alignment of the coefficients can be some of the most important data in the second Bytes are stored as well.) With this initialization, decoding is required less important data with one bit level at a time just reading and then that Write one byte (or less in some embodiments) per coefficient. When the coefficients are read, entered into the inverse transformation they are converted to a normal numeric form (eg Two's complement).

In addition to having "most important data" and "less important data", one can also omit or delete or quantize data during encoding. Coefficients are quantized by a quantization scaling factor 2 ^Q-1 . (The quantization of the coefficients is described in the JPEG standard.) In the present invention, the quantization represents a power of 2, since division is accomplished by omitting bit-planes. For example, Q = 1 represents a division by 1, and thus the coefficients do not change while Q = 2 represents a division by 2, which means that a bit plane has been deleted. These divisions can be implemented by using shifts (eg, a shift by one bit position for Q = 2). Figures 13B and 13C show the format of the most important and less important data when both quantization orientation and coefficient alignment are considered for different subbands.

Fig. 13B shows the lossless case where no data is deleted. Following the convention of JPEG, it is called a quantization Q = 1 because the current coefficient is divided by 1 (lossless). The most important data is displayed without cross-hatching, while the least important data is cross-hatched.

Fig. 13C shows the case where a bit plane with data has been deleted (ie, Q = 2) because the omission of a bit plane is equal to a division by 2. The omitted bit plane is shown in black.

Notably, in addition to what is shown in Figures 13B and C, the most important data also contains the SS coefficients. Although the coefficients for 8-bit data are shown, the use of a reversible color space would require 9-bit data, increasing the size of the chrominance coefficients by one bit.

In the present invention, the sign bit context model includes coding of the sign after the last bit of the header. There are three contexts for the sign, depending on whether the N coefficient is positive, negative or the sign still is not coded. Alternatively, a context may be used for the sign or the sign can always be coded as 50%.

Order of coding for wavelet coefficients

One embodiment of ordering coding for wavelet coefficients is summarized in the following pseudo-code:

encode the most important data
encode the position of the first less important bit-plane with data for each less important bit-plane
encode a less important databit level.

When the key data is encoded, the first bit level becomes less important data that does not consist entirely of zero overhead bits for each coefficient determined. This allows the encoder and decoder, over entire bits to look away from less important data. This is especially useful for Encoding of units of black and white data, where all information in  are the K coefficients and the CMY coefficients are all zero. A non-coding the bit planes individually helps a compression ratio, in particular, if R2 (7) is the longest run-length code that is available. (See U.S. Patent Nos. 5,381,145 and 5,583,500 for a description of the "R2" code). However, if the four parallel coding cores with components working synchronously, the processing becomes speed through the component with the most bit planes to be coded certainly; Cores assigned to other components are during unencoded bite levels idle.

A flowchart showing an embodiment of the operation of the above pseudo-code is shown in FIG . Referring to Fig. 14, the textual model begins with the coding of the most significant part (MIC) (processing block 1401 ). After encoding the MIC, the processing logic encodes the position of the first LIC bit plane with data (processing block 1402 ), where LIC represents the least significant piece. This applies to the whole coding unit. Either 0, 1, 2, 3, 4, 5, or 6 bit-planes will contain data if there are six bit-planes in the LIC. Then, the processing logic sets a current LIC bitplane variable to the first LIC bitplane with data (processing block 1403 ).

Next, a test determines if all LIC bit planes have been encoded with data (processing block 1404 ). If so, the process ends; if not, the processing logic encodes a LIC bit plane (processing block 1405 ) and sets the current LIC bit plane variable to the next LIC bit plane (processing block 1406 ). Thereafter, the processing returns to the processing block 1404 .

Order coding for the most important data

An embodiment of the order for coding the most important data is as follows:

The most important data are processed for a wavelet tree or with one wavelet tree at a time. They are not embedded for re-iterating. An MIC lookahead determines bit planes, which are all zero overhead bits, for all non-SS coefficients in the wavelet tree. In one embodiment, a 4-bit number is sufficient to identify the first bit-plane to encode individually. In an alternative embodiment, shown in Figure 15, one bit is used to indicate that all non-SS coefficients 1501 of the second decomposition (hatched area) are zero, and another bit to indicate that all are not -SS coefficients 1503 of the first decomposition are zero. These two bits are used in addition to the four bits used to specify the first bit-plane.

In an alternative embodiment, a tree lookahead may be used where the SS coefficients are encoded, and then for the whole tree encodes the first bit plane with non-zero overhead bits.

To consider a context re-entry delay if a condition For the SS and first bit-plane encoding, the current Encoding / decoding the bits of the SS coefficient (which is 9 bits, if any) reversible color space is used) and the predictor value is alternated. If conditioning is not used then alternation is not required.  

As previously discussed, the contextual model of the present invention uses a predictor. An embodiment of the prediction or foresight can be used for the most important data, ie the most important parts (MIC). In one embodiment, as shown in Figure 15, 6 bits are used for each tree: 4 for a maximum bit level, 1 for level 0 all zero, 1 for level 1 all zero. If the maximum bit-level is zero, then the two extra bits become redundant, but this is not important. Otherwise, an adaptive coding decision is used to decide "isolated zero / not zero". For non-zero coefficients, they can be further specified by the following:

• - An M-ary operation to get the value and sign of a coeffi to determine the cus- (Total: 2 cycles per coefficient)
• An adaptive coding decision is used to "± 1 / not ± 1 ", a second cycle is used to adjust the pre sign with the amount equal to 1 and the sign and the value for to get the amounts greater than 1. (Total: 3 cycles per coef fizient)
• - Similarly, "± 1 / not ± 1", "± 2.3 / not ± 2.3", etc. for a total of 4 cycles per coefficient are performed.
• - The following procedure:
  

It is noteworthy that "specifying" a bit or bits is adaptive coding can be, coding with 50% probability or simply coding bits to the coded data stream.

If all or most of the bit-planes are to be coded individually, some may Levels of transformation have unused bit planes due to an orientation - Unused bit planes are never encoded. There are a number of options for Handle a bit-to-context delay for the header and tail bits. On The method is to do three coefficients alternately. A DD, an SD and a DS. The sign bit for non-zero coefficients may be at the end of the coefficient be coded - since all the most important data is always lossless, is an exact Consequences of the first "on" bit not necessary.

An embodiment of a flowchart showing the pseudo-code for encoding the most significant part is shown in FIG . Referring to Figure 16, the process begins with the process logic setting the current tree to the first tree (processing block 1601 ). Then, the processing logic encodes the SS coefficient (processing block 1602 ). After encoding the SS coefficient, the processing logic encodes the position of the first bitplane with data in the MIC of the tree (processing block 1603 ) or performs the MIC predictor.

Then the processing logic tests whether the MIC of the whole tree is zero (processing block 1604 ). If the MIC of the whole tree is zero, processing continues at processing block 1614 ; otherwise, processing transfers to processing block 1605 where the processing logic sets the current coefficient to the first non-SS coefficients in the tree.

After setting the current coefficient to the first non-SS coefficient in the tree, the processing logic sets the current bit plane to data with the first bit plane (processing block 1606 ). Then, the processing logic encodes one bit of the current coefficient in the current bit plane (processing block 1607 ). Thereafter, the processing logic tests whether all bit-planes have been encoded (processing block 1608 ). If all bit-planes have been encoded, the processing logic sets the current bit-plane to the next bit-plane (processing block 1609 ) and proceeds to processing block 1607 . If all bit-planes have been encoded, the processing logic tests to see if the current coefficient is zero (processing block 1610 ). If the current coefficient is not zero, the processing logic encodes the sign bit (processing block 1611 ) and processing transfers to processing block 1613 . If the current coefficient is zero, then processing logic transfers to processing block 1613 .

At processing block 1613 , the processing logic tests whether all coefficients in the tree have been encoded. If all the coefficients in the tree have not been encoded, then the processing logic sets the current coefficient to the nearest coefficient in the tree (processing block 1612 ), and processing transfers to processing block 1606 . If all the coefficients in the tree have been encoded, then the processing logic tests to see if all trees have been encoded (processing block 1614 ). If all trees have been encoded, processing ends; otherwise, processing transfers to processing block 1615 , where the processing logic sets the current tree to the next tree, and processing transfers to processing block 1602 .

Fig. 17 is a block diagram of one embodiment of the formatter and a context model used during the most important data encoding run. Referring to Fig. 17, a barrel shifter 1701 is connected to receive the magnitude of the coefficient and a quantization level used during encoding to prevent the most important data from being the minimum Exceed disk bandwidth, thereby ensuring lossless decompression. Thus, the quantization level controls the barrel slide 1701 . In one embodiment, the barrel shifter 1701 shifts the magnitude bits by 0, 1, 2, or 3 to support the quantizations 1, 2, 4, or 8. In an alternative embodiment, a lower or higher number of quantizations is supported, such as. Eg only two quantizations.

The output of barrel shifter 1701 includes the six lower-level bit planes, which are the less important data, and the remainder of the higher-order bits, which are the most important data. In an alternative embodiment, a simple separation mechanism is used to generate these two outputs.

Both outputs of the barrel shifter 1701 are input to the first bit plane unit 1702 , which determines which bit planes have data in them. The first bit plane unit 1702 is used to find the bit plane with the first "on" bit for the whole coding unit (see Fig. 10) for use when processing the less important data. Another bit-plane unit 1706 is connected to receive the most important data output from a barrel shifter 1701 as well. The first bitplane unit 1706 is used for each tree as the more important data is processed. An embodiment of the first bit plane unit will be described below with reference to FIG .

The barrel shifter 1701 is also closed to the comparison unit 1703 and 1704 which make two comparisons with the most important data to produce the two-bit signaling information for the less important data. The comparison unit 1703 determines if the most important data is equal to 0, thereby indicating whether a tail bit has already occurred (ie whether the coding is still in the tail). The output of compare unit 1703 is the tail-a-bit. A comparison unit 1704 determines whether the most important data is equal to one. If the most important data is equal to 1, then the output from the above table 5 is 0. The output of a compare unit 1704 is connected to an input of the multiplexer (MUX) 1705 . The other input to the multiplexer 1705 is connected to receive the sign bit. A select input of the multiplexer 1705 is controlled by the output of a compare unit 1703 so that if the output of the compare unit 1703 indicates that the bit is a tail bit, then the output of the multiplexer 1705 is a "first tail" bit 1304 . However, if the output of compare unit 1703 indicates that the bit is the header, then multiplexer 1705 is controlled to output the sign.

In one embodiment, compare units 1703 and 1704 may be implemented using simple bit comparators.

A memory 1707 is connected to receive the sign bit, the most important data output from the barrel shifter 1701 , and the output of the bit plane unit 1706 . Memory 1707 is used to delay coefficients such that parent and neighborhood information is available for conditioning. The organization of memory 1707 is discussed below.

Context models (CM) 1710-1712 provide a conditioning for the sign, the head, tail and other bits ready. Each of these context models is described below.

Fig. 18 shows an embodiment of a bit plane unit. Referring to FIG. 18, the first bit plane unit 1800 includes an OR gate 1801 that is connected to receive a coefficient and a feedback from the output of a register 1802 . The output of an OR gate 1801 is connected to the input of a register 1802 . Register 1802 is controlled by a start of a Tree / Encoder Reset Display. The output of register 1802 is connected to a priority encoder 1803 . The output of the priority encoder 1803 is the output of a first bit-plane unit 1800 .

At startup, register 1802 is cleared. Each bit of a register 1802 is ORed with each bit of the input coefficient, using the OR gate 1801 . For each bit of the coefficient that is 0, the value of the register 1802 remains its current value, which is output to the priority encoder. For each bit of the coefficient that is a 1 (eg, the first one), the output of the OR gate 1801 to the register 1802 is 1, which is output to the priority encoder 1803 . The priority encoder 1803 then locates the first 1, which is the first bit plane of the coefficient, which has a 1.

Order or order of processing for less important data

Each bit-level for the least important data is processed as follows:

do for every tree
do for each coefficient
if start from the foresight interval
do foresight
if foresight is not active
encode head or tail bits
if first "on" bit
encode sign bit.

An embodiment of the processing of encoding a LIC bit plane is shown in the flowchart of FIG . The processing of encoding a LIC bit-plane begins with the processing logic determining the current tree to the first tree (processing block 1901 ). Then, the processing logic sets the current coefficient to the first non-SS coefficient in the tree (processing block 1902 ). After setting the current coefficient to the first non-SS coefficient in the tree, the processing logic tests whether encoding is at the start of a foresight interval (processing block 1903 ). If the encoding process is at the start of a predictive interval, the processing logic performs a foresight (processing 1904 ) and processing proceeds to processing block 1905 . If the encoding process is not at the start of a foresight interval, the processing logic goes directly to processing block 1905 and determines if foresight is active.

If look ahead is active, processing continues at processing block 1909 where the processing logic determines whether all coefficients in the tree are encoded. If all coefficients in the tree are encoded, processing continues at processing block 1913 ; otherwise, the processing logic sets the current coefficient to the nearest coefficient in the tree after the predictive interval (processing block 1910 ), and processing transfers to processing block 1903 .

If foresight is not active, the processing logic encodes the header or tail bit (processing block 1906 ) and then tests to see if the first non-zero bit has been received (processing block 1907 ). If the first non-zero bit has not been received, processing continues at processing block 1911 . If the first non-zero bit has been received, processing continues at processing block 1908 where the processing logic encodes the sign bit, and then processing transfers to processing block 1911 .

At processing block 1911 , the processing logic determines whether all coefficients in the tree have been encoded. If all coefficients in the tree have not been encoded, the processing logic sets the current coefficient to the nearest coefficient in the tree (processing block 1912 ) and proceeds to processing block 1903 . If all the coefficients in the tree have been encoded, processing transfers to processing block 1913 , where the processing logic tests whether all trees have been encoded. If all the trees have not been encoded, the processing logic sets the current tree to the next tree (processing block 1914 ) and processing continues at processing block 1902 . If all trees have been encoded, processing ends.

Processing a wavelet tree at one time may not be important, but there the transformation causes data to be read in that order and written, it may be appropriate. If the data is through wavelet trees can be adapted to a bit-to-context delay be made by alternating DD, SD and DS coefficients (Alternate between subtrees). Otherwise, a subband may be at a time be encoded. Regardless of the chosen order will be unused Head / tail bits never encoded due to the alignment of different subbands and do not require idle or unproductive cycles.

Fig. 20 is a block diagram of an embodiment of the predictor and counter models for less important data. In one embodiment, the most important data and the less important data use the same context models (CM) that provide conditioning for the sign, head and tail bits.

Referring to Fig. 20, context models 2001 through 2003 are connected to the input data. A sign context model 2001 is connected to receive the tail-a-bit, a sign / first-tail bit signal, and the data. The header contextual model 2002 is connected to receive the tail-a-bit and the data. The tail bit context model 2003 is connected to receive the tail-a-bit, a sign / first-tail bit signal, and the data. In response to their inputs, each context model produces a context from 2001 to 2003 . The mentioned "first tail bit" may also be referred to as "first tail bit".

The contexts generated by the context models 2001 through 2003 are connected to the inputs of the 2004 multiplexer. The multiplexer 2004 is controlled by the preceding bits and the bit significance representation itself. The head context model 2002 is used until a 1-bit is seen at the data input. The sign context model 2001 is used when the last bit was the first 1-bit of the header. Thereafter, the tail context model 2003 is used.

The output of the multiplexer 2004 is connected to the "= head?" Unit 2005 and the first-in-first-out (FIFO) buffer 2006 . The "= header?" Unit 2005 tests whether the current context is a header bit context with zero overhead bits in the neighborhood and parent. If all contexts are in the header, a signal from the "= header?" Unit 2005 clears the FIFO 2006 .

The contexts and results are buffered in the FIFO 2006 or in the memory for the before-seeing interval. At the end of the interval, if necessary, a predictor's decision and / or individual decisions are encoded. If the coefficients are processed with a wavelet tree at a time, the FIFO foreseeing may be a single FIFO used for all subbands, or multiple FIFOs may be used, one for each subband.

Remarkably, if it was expedient to reduce the multiplexing, the key data could also use foresight. But it can be something be redundant, both a foresight and a first bitplane for each tree to use.

If a core assigned to a component encodes a sign bit, become cores that are assigned to any other components that are not encode a sign bit at the same bit plane, be idle or unproductive. Therefore, up to four clock cycles can be used for sign bits, if  each core encodes a sign bit at a different bit-plane. At a Embodiment, there are up to six head or tail bits per coefficient.

One potential timing issue is that the most important part or chunk is sufficient compressed well, so that the disk during the decoding of a part of the Data is inactive or unproductive. If there is enough memory bandwidth for gives the band buffer, a foresight can be used to identify the most important Data to process fast. Then the less important data can head-start or received a head start. Likewise, it would be good if the disk burst over transmission rate or a discontinuous transmission rate that would be higher as the maximum sustained rate. Hard drives usually have one significant buffer on and maybe a reading ahead would be in these Buffer eliminate the useless or unproductive time.

Conditioning a part of the contextual model

The conditioning used in the context model depends on the hard the hardware costs or the hardware costs compared to the compression compromises from. Therefore, in the following sections, many options become available for conditioning presented, which can be noticed by designers.

Context model for SS coefficients

In one embodiment of the context model, SS coefficients are not encoded. Since they make up only 1/256 of the original data, their encoding only results a small profit. If you want to encode, you can Gray coding, conditioning on the previous bit in the same coefficient and / or to a corresponding bit in the previous coefficient become.  

Context Model for First Bitplane Information

The four bits of the first bit plane information for the first bit plane for the most important data of each wavelet tree can be similar to the SS coefficients be treated. You only increase the size of the original data by 1/512. at In one embodiment, they may be uncoded on their small size as compared to remain the original data or a Gray coding or another Konditio go through.

Similarly, if six bits are used as shown in Figure 15, they can be treated as SS coefficients.

Context Model for Header Bits

Figure 21 is a block diagram for one embodiment of the context model that provides header bit conditioning. Referring to Fig. 21, the context model 2100 includes shift registers similar to those found in a bit-plane context model. An important difference is that instead of using previous coefficient bits from the current bit-plane, conditioning is based on tail-on information that uses all previous bit-planes and the previously encoded information in the current bit-plane. Similarly, some bits for identifying the coded bit plane or group of coded bit planes and the subband or group of coded subbands are generated from the level of importance and subband bucketing (guess-like).

Referring to FIG. 21, the context model includes two inputs, the current significance level 2110 and the coefficients from memory 2111 . The current significance level 2110 is connected to the inputs of the tail information / bit generator block (s) 2101 and the importance level and subband memory area formation block 2102 , the memory formed in particular including data for an application, and The storage area creation process is also referred to as a "bucketing" block and can also be understood as a variable assignment. The coefficients from the memory are also connected to block 2101 and registers 2103 to 2106 .

The block 2101 takes the coefficients and determines whether or not there is a bit. In one embodiment, 2101 also determines from where the one bit is. The output of the block 2101 represents one or two bits based on the tail-in information. In one embodiment, the tail information establishes a relationship as to whether or not the first nonzero magnitude bit has been observed (eg, whether the first "one bit" has been observed), and if so that's how many bite planes this is about. Table 6 describes the tail information bits.

Table 6 - Definition of tail information

From the 2-bit tail information, a 1-bit "tail-on" value is synthesized to indicate if the tail information is zero or not. In a Ausfüh The tail information and the tail-a-bits are updated immediately after the coefficient has been coded. At another off an update occurs later to parallel context generation to enable.  

In addition, the two bits can be used to indicate that the important thing level has been coded. The first two bit planes use the value 0, the second two 1, the third two 2 and the remaining bit planes 3. In addition there is one Run-length coding of the bits that are all zero-head bits.

The 10 bits of context for the header bits include the 2 bits of information each from the parent and the west coefficient, 1 bit of information respectively from the north, east, southwest and south coefficients and 2 bits of importance level information.

In one embodiment, the tail information does not become for some or all Frequency bands used. This allows a frequency band to be decoded without first decoding his parent.

In one embodiment, the assignment of the bit-planes of each frequency band to the importance levels uses an alignment. Parental tail information determination uses a second alignment that uses fewer bit planes of the parent than has actually been encoded. This allows some bit-planes of a frequency band to be decoded without decoding the corresponding bit-planes of the parent at the same level of nullity (see Figure 38). For example, an image may be encoded with a pyramidal orientation, but the parent tail information is based on MSE alignment (see Fig. 39). This allows the decode to decode a pyramidal orientation, to simulate MSE alignment, or to simulate any alignment between pyramidal and MSE.

Referring to Fig. 21, the outputs of the block 2101 to A transitions of the registers 2103-2106 are coupled. Registers 2103 to 2106 accumulate the neighborhood data. For example, the upper / left shift registers maintain bits during the line that is just above the current coefficient. The current shift register contains the bits of the current line of coefficients while the lower / right shift register 2105 contains the lines of the line just below the shift register. Finally, the parent register 2106 maintains the parent data. The outputs of the shift registers form the context.

The output of the importance level and the bucket block 2102 may also be used for a context. This would be part of the context if the subbands and different levels are to be coded to the same context. If so, the output from block 2102 is connected to the outputs of registers 2103 through 2106 to form the context. If not, the context includes only the outputs of registers 2103 through 2106 .

Likewise, the output from the context model 2100 is one bit.

Coding can be done by choosing between DD, SD and DS coefficients client to the bit-to-context delay to use data from the current bit-plane (alternating between subtrees) becomes).

It is noteworthy that the memory is needed to store coefficients needed for conditioning (see Fig. 17). The memory usage for one embodiment of the context model with conditioning of all neighbors and parents is shown in FIG . A short hem-transformation order is assumed. (An external memory can be used to support a long seam transformation order, which would require both additional memory space and additional bandwidth.)

The conditioning of high-level parents is particularly expensive. The level 4 DD coefficient for a given tree is not calculated up to 16 trees later than most of the level 1 DD coefficients for that tree. Similarly, storing entire coefficients to be coded later (unshaded in Fig. 22) is much more expensive than just storing tail information for later use in conditioning (cross-hatched in Fig. 22). The conditioning of only the "West" information, which is the same tree, and the parent generated without data from "West" trees would significantly reduce the amount of memory required. If a parent or West information was not available, copying the information from the north or east is useful.

Context model for sign bits

The context model that provides conditioning for sign bits is simple. If the sign of the above pixels is known, it will be for conditioning used. If the sign bit for the above pixel is unknown, then uncoded bit (R2 (0)) is used. Alternatively, no coding (R2 (0)) for all Sign bits are used.

Fig. 23 is a block diagram of one embodiment of the context model for flag bits. Referring to Fig. 23, a multiplexer 2301 receives a north flag 2303 and a 0-bit 2304 (wired) and is controlled by a north tail one bit 2302 to output the north sign bit 2303 , if the north tail one bit 2302 is a 1; otherwise, the multiplexer 2301 outputs a 0. Thus, the north pixel provides north tail-a-bit 2302 and north sign bit 2303 to provide a context for the pixel south of the north pixel.

Context Model for tail bits

No conditioning is used for tail bits. In one embodiment a fixed probability state is used and no probability Update is used. Table 7 shows three options for codes used for  Tail bits are to be used. The second option, which uses R2 (1) and R2 (0), is a good choice.

Table 7 - Probability states (codes) used for tail bits

In one embodiment, the code according to a golden ratio ("Golden Ratio" code) that is good for probabilities of M ≅ 60%, L ≅ 40% is as follows:

input codeword MMM 00 MML 110 ML 01 LM 10 SS 111

Kontextbin Summary

The minimum number of context bins that could be used in the system are as follows. SS, first bit plane for each tree, sign and tail bits all are not encoded (the code used is R2 (0)). Although no PEM state or Most Probable Symbol (MPS) bit or MPS bit must be stored, there must be some logic to select the R2 (0) code.  

Therefore, the hardware cost is zero depending on how it is counted or a context bin. Adaptive coding should be used for header bits. For less important data is that, as one bit-level is encoded at a time, the condition not important to the bit-plane. For the most important data, the first bit level for each wavelet tree reduce the number of bit planes sufficiently, so that Conditioning the bit-plane is not important. It is less clear what the useful This is also reflected in this sub-band conditioning Minimal context example to be ignored. The tail-a-bits of these three neighbors and one parent could be used for a total of four bits (16 context bins) become. An additional context bin may be for a forerunner or for a before to be used. (It may be convenient to use the two header context bins together to make room for the anticipation, so that the memory size is still a power of 2).

With four cores (which requires a four-fold replication of contexts) and two context memory banks per core would be the minimum number to use context bins between 128 and 144, depending on how "non-encoded" contexts are counted and whether two head context bins come together be mapped or brought together by illustration.

A system with a lush conditioning scope is as follows:

• For SS (9 bits) and a first bit plane (4 bits) use 4 context bins per bit, for a total of 52 context bins (this could be split into banks, they do not have to be duplicated).
• Tail bits are not coded, but both R2 (0) and R2 (1) are ver applies. Depending on how they are counted, this costs 0, 1 or 2 Context bins.
• - Two adaptive contexts and one "no-code" context are considered to be the best chenbits used.  
• The header bits can be 8 bits of neighbor / parent and 2 bits for subband / bit use level information (1024 context bins).
• - A context is used for predicting.

An alternative embodiment of a context model including an Off of a sign / amount unit, the input coefficients in a Sign / magnitude format is described in U.S. Patent Application No. 08 / 498,695, filed on 30 June 1995, entitled "Method and Apparatus for Compression Using Reversible Wavelet Transforms and Embedded Codestream "and the U.S. Patent Application No. 08 / 498,036, filed June 30, 1995, entitled "Re versatile wavelet transform and embedded codestream manipulation "and also in U.S. Patent Application Serial No. 08 / 642,518, filed May 3, 1996, entitled "Compression and Decompression with Wavelet Style and Binary Style Including Quantization by Device Dependent Parser ", and US Patent Application No. 08/643, 268, filed May 3, 1996, entitled "Compression / Decompression Using Reversible Embedded Wavelets ".

The context model provides contexts for entropy encoding of the data. On an off The entropy coding that is achieved by the present invention will be described is performed by binary entropy coders. A single encoder can can be used to generate a single output code stream. alternative Multiple (physical or virtual) encoders can be used to multiple to generate (physical or virtual) data streams.

M-ary coding for LIC

Fig. 24 shows the use of M-ary encodings for the LIC. The use of M-ary for reduced coding works as a forerunner (as shown). First, the state of the next eight coefficients is examined. If there is anything in the header, entropy coding is performed on the header bits so that all header bits, one per cycle, are entropy encoded until all header bits are encoded at the eight coefficients. Referring to Fig. 24, the header bits which are 1 are encoded in the first and third cycles, while the header bits which are 0 are encoded in the second and fourth cycles. Once the header bits are entropic-coded, the sign and tail bits are encoded in the same cycle. For example, in Fig. 24, all sign and tail bits following a header bit which is 1 are encoded in the fifth cycle. In this way, the total number of cycles is reduced.

A printing system application of the present invention

Fig. 25 is a block diagram of an embodiment of the front end of a printer. Referring to Fig. 25, a renderer receives data in the form of a page description language (PDL) or a display list. The conditioner 2501 may include raster image processing. For each spot (eg, each spot), renderer 2501 determines its color (eg, black and white, 8-bit RGB values, 8-bit CMYK values, depending on the application ). The output of the renderer 2501 represents a set of pixels that are formatted in bands and stored in a band buffer (memory) 2503 .

In an alternative embodiment, data is from a page description language (PDL), such as B. Adobe Postscript® or Microsoft Windows® GDI, to a Display list or prepared in a display list. The display list or display list is used to create bands of pixels. In this embodiment assume that the pixels represent continuous tonal values, and any semitones processing or dithering or dithering by the printing press is required, is performed after decompression.  

In the present invention, the memory used for the band buffer 2503 is also used as a work space for compression (without increasing the required memory). This dual use will be described in more detail below.

The compressor 2504 compresses each band of pixels. If the input of the compressor 2504 represents dithered pixels, the compressor 2504 would still operate, but the compression achieved would probably be poor with wavelet processes. A binary context model can be used with halftone or dither pixels. The compressor 2504 writes the compressed data to the disk 2505 . The disk 2505 may be a hard disk. In an alternative embodiment, the disk 2505 may be a random access memory (RAM), a flash memory, an optical disk, any type of memory device, or any type of communication channel.

Fig. 26 is a block diagram of one embodiment of the rear end of the printer. Referring to Fig. 26, the rear end of the printer 2500 includes a decompressor 2602 connected to the disk 2505 , a tape buffer (memory) 2603, and a printing machine 2604 . The decompressor 2602 reads compressed data from the hard disk 2505 and decompresses it. The decompressed data is stored in the band buffer (memory) 2603 in the form of pixels. In the band buffer 2,603th it may be the same memory as the band buffer 2503, as a working space for the compressor 2504 to processing th The decompressor 2602 keeps the band buffer 2603 has sufficient power so that the pixels sent to the printing press in 2604 in real time can be.

Fig. 27 illustrates an alternative embodiment incorporating an optional enhancement. Referring to Figure 27, pixels from the decompressor 2602 pass to the band buffer 2603 via an enhancement block 2705 , while other information, which is the information that is not yet pixels (sub-coefficients), goes directly to the band buffer 2603 is sent. An improvement block 2705 may perform such functions by interpolation, smoothing, error diffusion, halftone and / or Zitterver processing.

The required bandwidth between the decompressor 2602 and the band buffer 2603 allows the decompressor 2602 to write out the transformation coefficients to the band buffer 2603 to access the band buffer 2603 to obtain certain coefficients and perform the inverse transformation with such coefficients and then back to write to the tape buffer 2603 . Noteworthy is that the band buffer 2603 may be small as a working memory. For example, if a full page image is 64 megabytes and a tape buffer 2603 is 16 megabytes, it would still be considered a small memory.

In one embodiment, 400 dpi, 32 bit / pixel (four 8-bit components, CMYK) A4 images require approximately 8 Mbps data rate from the tape buffer 2603 to the print engine or printer 2604 at approximately 8 pages / minute. The transfer rate of an exemplary hard disk is about 2 Mbytes per second (eg, 1.7-3.5 Mbytes / s). Therefore, a typical compression rate of about 4: 1 is required to match the bandwidth of the disk 2601 to the bandwidth of the printer. In one embodiment, the compressor 2504 in FIG. 25 and the decompressor 2602 in FIG. 26 or 27 are contained in a single integrated circuit chip.

Fig. 28 is a block diagram of one embodiment of an integrated circuit (IC) chip incorporating printer compression / decompression. Referring to Fig. 28, the pixel data interface 2801 is connected to the band buffer (not shown). The pixel data interface or pixel data interface 2801 is connected to the band buffer (not shown). The pixel data interface 2801 generates addresses for reading and writing the pixels from and to the band buffer, respectively. An optional reversible color space 2802 may be included to perform a reversible color space conversion. The coefficient data interface 2804 generates addresses for reading and writing coefficients and correctly assembles two byte coefficients. Coefficient data interface 2804, along with pixel data interface 2801, handles any line buffers or coefficient buffers required in external memory. The coefficient data interface 2804 and the use of a reversible color space will be discussed in more detail below.

It is noteworthy that the double arrows imply that the data in both directions can flow. For example, when compressing the data, the Data from left to right through the various components of the IC chip. On On the other hand, when the data is compressed, the data moves in the general from right to left.

When the data is encoded, the pixel data from the pixel data interface 2801 or the reversible color space 2802 (if included) is received by the wavelet transform block 2803 , which performs the wavelet transform on the pixel data. In one embodiment, the transformation performed by the wavelet transform block 2803 represents an overlapped wavelet transform. It provides energy compression for both lossless and lossy image compression. For lossy compression, the block boundary artifacts, the JPEG plagues, are avoided. The filter coefficients are normalized, if properly aligned, to provide scalar quantization with good results in lossy compression. In one embodiment, the wavelet transform block 2803 performs a 2, 6 transform. In another embodiment, the wavelet transform block 2803 performs a 2.10 transformation. Wavelet transform block 2803 may perform other well known transforms. Various implementations of the wavelet transform block 2803 will be described in more detail below.

The coefficient output from the wavelet transform block 2803 may be written back to the memory (e.g., the band buffer) via the coefficient interface 2804 for later encoding. In one embodiment, the data that is written back to the memory is less important data and will be described in more detail below. Such data is later read back into the IC chip and encoded.

The coefficients output from the wavelet transform block 2803 or received via the coefficient data interface 2804 are provided to the context model 2805 . The context model 2805 provides the context for encoding (and decoding) data using the encoder / decoder 2806 . In one embodiment, the context model 2805 supports sending data directly for encoding. In this way, the context model 2805 works as the most important context model. An architecture for implementing various context models has been described above.

In one embodiment, the encoder / decoder 2806 includes a high speed parallel encoder. The high speed parallel coder handles different bits in parallel. In one embodiment, the high speed economy encoder is implemented in a VLSI hardware or a multiprocessor computer without sacrificing compression performance. One embodiment of a high speed parallel coder which can be used in the present invention is described in U.S. Patent No. 5,381,145, entitled "Method and Apparatus for Parallel Decoding and Encoding of Data", issued January 10, 1995.

In alternative embodiments, the binary entropy encoder comprises either one Q encoders, a QM encoder, an FSM encoder, etc. The Q and QM encoders are well known and represent efficient binary entropy coders. The FSM coders Provide the simplest conversion of a probability and a result ("outcome") to a compressed bit stream. In one embodiment the FSM encoder realizes look-up tables for both a decoder as well as a coder can be used. A variety of probability Estimation methods can be used with such a FSM encoder. at In one embodiment, the FSM encoder of the present invention comprises a B coder disclosed in U.S. Patent No. 5,272,478 entitled "Method and Apparatus for Entropy Coding ", issued December 21, 1993.

The output of the encoder / decoder 2806 is connected to the coded data interface 2807 , which provides an interface to the disk or other storage medium or even another channel.

The coded data interface 2807 sends and receives coded data from the disc. In one embodiment, if the SCSI controller or controller is included in the chip, it may be implemented at that location. In another embodiment, the coded data interface 2807 communicates with an external SCSI controller. Non-SCSI memory or communication can be used.

During decompression, encoded data is received by the encoder / decoder 2806 from the disk (or other memory or channel) via the encoded data interface 2807 and decompressed therein using contexts from the context model 2805 . The coefficients resulting from the decompression are inversely transformed by the wavelet transform block 2803 . (Note that although a wavelet transform block 2803 performs both forward and inverse transforms in one embodiment, in other embodiments, the two transforms may be performed by separate blocks.) The output of the transform block 2803 includes pixels undergoing any optional color space conversion and output to the band buffer via the pixel data interface 2801 .

The basic timing of the system during printing is shown in FIG . Referring to Fig. 29, the coded data from each coding unit is read from the disc. As much data as possible is read and after a short delay coefficients are decoded. After the decoding is completed, the inverse wavelet transform is calculated. After the transformation is completed, the pixels can be sent to the printing device. It is noteworthy that the cross-hatching in Fig. 29 indicates when various actions occur for a specific coding unit.

Embed coefficients for storage on a disc

Fig. 10 shows the organization of coded data in the present invention. Referring to Fig. 10, the most important data 1003 is encoded in coefficient order (not embedded) immediately after being transformed. Therefore, these data do not need to be buffered. In one embodiment, the amount of key data 1003 is limited so that it can always be read from the disc.

A certain amount of less important data 1004 is buffered, embedded and written to the disk in order of importance. The amount of data that can be buffered, embedded, and written is determined based on the transmission time. That is, the system reads the data until the transfer time from the disk is exhausted. The transfer rate of the disc determines how much data is retained. These rates are known and dependent on physical characteristics of a particular transmission.

For images that are difficult to compress, some data may be omitted during the encoding time. The data is shown as least important data 1005 . In the case where there is no possibility that the least important data can be read on the assumption of the best possible disk transfer rate, there is no reason to store that data on the disk. For many and perhaps most images, no data would be deleted or deleted.

The ordering of coded data and how it is accomplished will be described below described in more detail.

The following is the band buffer management during compression and decom followed by a description of the embedding scheme for the encoded data. Hardware implementations of the transformation, the Kon Text model and the parallelism with the encoder / decoder are also described.

Pixel and coefficient interfaces

Fig. 30 shows one possible embodiment of how pixel data is organized. Referring to Fig. 30, one page (picture) 3000 is divided into bands 3001 to 3004 . In one embodiment, page 3000 may include a page description language or a display list description of a page used to generate pixels for the individual bands. In one embodiment, each band is individually rasterized 3001 to 3004 by a display list technology is used. Each band 3001 to 3004 is further divided into coding units (eg, 3001 A-D).

An advantage of using multiple encoding units per band is that sections the tape buffer in rotation or rotating as memory during the decom  Pressing (similar to the ping pong buffers) can be used. With others In other words, some of the pixels may be decompressed, stored in the tape buffer, and too while the second part of the tape buffer is working Memory can be used to store coefficient while decoded where a third part of the buffer is used to store the pixels correspond to the coefficients.

FIG. 31 shows a band buffer 3101 of page 3100 . The band buffer 3101 comprises coding units 3001 A-D. The coding units 3101 A and 3101 B act as working memory for the decompressor to store coefficients. The encoding unit 3101C stores pixels to be output to the printer (or channel) while the encoding unit 3101D operates as a work space for the decompressor by storing the next pixels.

The portions of the tape buffer 3101 may be used in rotation when the entire page 3100 is printed. For example, for the next encoding unit, the pixels in the encoding unit 3101D are the pixels to be output to the printer. When this occurs, the encoder units 3101 B and 3101 C will be used as the working space for the decompressor to store coefficients. Also at that time, a coding unit 3101A will be used as the working memory for the decompressor to store the next pixels to be output to the printer.

In the present invention, the coefficients are larger than the pixels. That's why twice as much memory is allocated to the workspace memory. At a Alternatively, the bands may be in more or less coding units be split. For example, in one embodiment, the bands may be in eight Coding units are each divided.  

Memory Bandwidth

Together, the pixel data interface and the coefficient data interface manage the tape buffer efficiently. If a fast-page mode DRAM, an EDO DRAM or other memories are used, which are consecutive Access, then these interfaces transmit data from one another the addresses in long enough bursts to the potential bandwidth of the memory efficient to use. Some buffers may be needed to handle burst accesses or to support discontinuous access to consecutive addresses.

Figure 32 is a timing diagram of decoding showing memory access requirements for concurrent memory access and parallel memory access, respectively. Referring to Fig. 32, the bandwidth required for decoding is as follows. Recall that in one embodiment, a 2 MHz pixel clock, an 8 MHz component clock, and a 32 MHz decoder clock were used and that the printer requires 1 byte / component clock, the transform reads two bytes per coefficient and writes Byte per component. If the transformation is performed in half the encoding unit time, this would require a 6 byte / component clock. The speed of the transformation is limited by the memory bandwidth, not the computation time. If a bandwidth of a 24 byte / component clock is available, the transform can be calculated within one eighth of the encoder unit time. The transformation may require extra bandwidth if external memory is used for seams. In one embodiment, encoding coefficients requires writing two bytes per component clock for the most significant part of the encoded data. Decoding requires reading and writing one byte per component clock for each bitplane of the less important part of the encoded data. It should be noted that in some embodiments this may be less. Bandwidths of 4 bytes per component clock and 24 bytes per component clock would respectively be required if both operations require half the encoder unit time. Additional bandwidth may be required if external memory was used for context seam information.

In one embodiment, the maximum burst mode transmission rate is four Memory accesses per component clock (one access per encoder clock). That's why For a 32-bit data bus, the maximum transfer rate is slightly less than 16 bytes / com ponententakt. With a 64-bit data bus, the maximum transfer rate is something less than 32 bytes / component clock.

Reduction of LIC Memory Bandwidth Requirements

Each bit of each coefficient in the LIC requires reading and writing of the external memory during decoding (encoding requires only one Read). These memory accesses make up the majority of the required memory tape wide out. In one embodiment, instead of that, the present invention stores it stores each LIC coefficient in 8 bits, the coefficients being less than 8 bits, if possible, are used to reduce the bandwidth requirements adorn.

Table 8 shows how much memory is needed to store the LIC coefficients for decoding each bitplane. Referring to Table 8, when dealing with the MIC, one bit is written per coefficient, which is the tail-one-bit. What is written for the bit-plane 5 is read back for bit-level 4: 2 to 3 bits, which was the tail-a-bit, which was bit 5, and if bit 5 was 1, then a sign bit. The percentage indicates for each bit level what percentage of the coefficients participate. This can be made clearer by looking at Fig. 13B. Referring to Fig. 13B, the bit plane 5 has coefficients of all participating subbands because all the coefficients from the DD1 to the DS4 and SD4 subbands have data in the bit plane 5 (as indicated by shading). , The bitplane 0 has only coefficients from the DD1 subband. As shown in Table 8, both bit-planes 4 and 5 have coefficients of all subbands, so that the percentage is 100%, while bit-plane 0 has only 25% of the coefficients (in the DD1 sub-band). As more decodes occur, some bit-planes are completed before a bit-level 0 is reached.

Table 8 - Required bits to store LIC coefficients during decoding

In Table 8, during the beginning of decoding, there is no decoding of the bit planes occurred; therefore, only one bit (bit / coefficient) of each coefficient becomes read to determine if it is a head or a tail. If the decoding As the rate increases, the number of bits per coefficient increases.

Fig. 33 shows how circular addressing can be used to handle the writing of data larger than the read data. This occurs because the results of processing produce more bits to write than were originally read. Referring to Fig. 33, the process begins by writing one bit per coefficient, which is 1/8 of the memory space. Subsequently, one bit per coefficient is read while writing 2 to 3 bits per coefficient. Then, the 2 to 3 bits per coefficient are read while writing 3 to 4 bits per coefficient. This continues until all the data has been dealt with.

There are a few options to simplify hardware implementations. Instead of that always the minimum number of bits are used, only z. B. 1, 2, 4, 6 or 8 bits would be used, which would cause a bit in some Sizes would be wasted. A space for the sign bit could always be be used even if the sign bit was not coded in the LIC or was not known yet.

One option that would further reduce memory bandwidth would be the tail-a-bit not to be stored, if it is not necessary 20027 00070 552 001000280000000200012000285911991600040 0002019819405 00004 19908. For example, if you have the Bit level 0 writes, there are 6 bits that are either header or tail bits. If any of these bits are not 0, tail-on must be true, and it is There is no need to save the tail-a-values and the sign bit can be used as the seventh bit are stored.

Memory bandwidth for the most important chunk (MIC) can also be reduced by variable length memory techniques. Simply using the minimum number of bits rather than always using 8 bits per coefficient would result in savings. Storing 6-bit predictive values (as in Fig. 15) rather than 0 coefficient bits would result in even more efficient use of the memory.

Reversible color space

The present invention provides an optional implementation of a reversible color Space conversion ready, which allows a conversion between two color spaces, so that it is completely reversible and implementable in integer arithmetic. The means the color space data being converted can be reversed to all existing data, regardless of any rounding or one any clipping that occurs during the forward conversion process. Reversible color spaces are described in U.S. Patent Application Serial No. 08 / 436,662, commonly known as US Pat Title "Method and Apparatus for Reversible Color Conversion", filed on 8 May 1995 and assigned to the present applicant.

The color space conversions allow the advantages of an opposite color space, without sacrificing the ability to deliver lossless results. For the lossless Case, an opposite color space provides a decorrelation that compresses improved. For the lossy code, an opposite color space allows that Luminance information is less quantized as chrominance information, which is a higher visual quality. If a reversible color space with the transformation is used in the present invention, a correct embedding of the Luminance and chrominance coefficients sub-sample the lossy one Superior compression while still allowing lossless compression becomes.

If a reversible color space is used, it is desirable to have the coefficients so that the most significant bit or the most significant bit of the 8-bit luminance components and the 9-bit chrominance components have the same orientation to have. For lossy compression, this alignment causes Chro min data is quantized twice as often as luminance data, and allowed as well as the possibility of a lossless compression for or regarding the Luminance and a lossy (but very high quality) compression for or in terms of chrominance. These two results take advantage the characteristics of the human visual system.  

Other pixel operations

Often, a printer will have documents that are mostly or completely non-existent are continuous. For example, text images with only black and white (only the 0 and 255 value) be common.

In one embodiment, the histogram of bands is completed. For example can pure 0.255 black and white images (the K component) new to 0.1 images be imaged. Similar densifications can be made with regard to spot color images or Point color images are performed. It is noteworthy that when a comp is used, the compression must be lossless. However, the scored lossless compression significantly improved when the compaction performed becomes.

Alternatively, instead of using the overlapped wavelet transform described herein, binary and spot color images through a lossless, on Bite-level based JBIG-like context model.

In another alternative embodiment, the system may be designed to include a binary mode. Figure 35 shows an embodiment of a binary context model that is similar to the JBIG style context model template. Referring to Fig. 35, shift registers 3501 to 3503 provide multiple bits per JBIG standard. The shift registers 3501 and 3502 receive second and first upper rows from the line buffer 3500 . The "upper" lines provide the bits corresponding to the pixels in the Northwest (NW), North (N), and Northeast (NE) positions of the template, as shown in Fig. 37. The outputs of the shift registers 3501 and 3502 are provided directly to the context model 3505 . The outputs of the shift register 3503 are provided to an optional multiplexer 3504 , which may implement the adaptive template of the JBIG standard. The context model 3505 is connected to the probability estimator 3506 , which in turn is connected to the bit generator 3507 . The context model 3505 , the probability estimator 3506 and the bit generator 3507 work together as is well known in the art.

The output of multiplexer 3504 in conjunction with the outputs of shift registers 3501 and 3502 and feedback from the bit generator form the context bin address used to address the context memory. In one embodiment, the context memory 3505 includes 1024 6-bit contexts to describe each probabilistic state. This requires a context memory of 1024 by 6 bits.

Because the bit generator is a decoded bit from the current line as part of the context There is a large "bit-to-context" delay including the Access time for the context memory.

FIG. 36 shows an alternate embodiment that uses the decoded bit from the current line to access the probability estimator in conjunction with a same address block 3601 that receives the outputs of the shift registers 3501 and 3502 and the output of the multiplexer 3504 . The PEM 3506 receives the previous bit and uses it to select the correct context pair from the one used. The selected context is updated and both contexts are written back to memory. The same address block 3601 detects addresses that have already been written so that the data is already in the probability estimator. The same address block 3801 also sends the signal to use the data already in the PEM (which may be updated data) instead of the old information in memory.

In one embodiment, the decoder 1024 includes context bits with 6 bits to describe each probability state. This requires a 512x12 bit context memory. The outputs of the shift registers 3501 and 3502 along with the output of the multiplexer 3504 provide a partial context bin address which only misses the use of the previous bit. This leads to a selection of a context bin pair from the context memory 3505 . More than one bit of a context bin can be excluded from the subcontext. Each memory location contains 2 ⁿ probability states, where n is the number of excluded bits.

It is noteworthy that the "bit-to-context" delay is reduced. The context Memory access may occur before the previous bit is decoded. The Processing of the PEM state for both states in a pair can be done in parallel begin before the previous bit is decoded. A high-speed operation can be reached.

Kodiererratensteuerung

In addition to the ability to quantize the data, performing a Rate control in the encoder as well as measuring the rate so that decisions can be made about the quantization. If the rate indicates that the Compression is not good (that is, not at a desired level, the Quantization can be increased. On the other hand; if the rate indicates that the Compression is too high, the quantization can be reduced. Rate control Ent Divisions must be made identically in the encoder and the decoder become.

A method of ensuring that the encoder and decoder are the same Make decisions is to use a signaling. The encoder measures the rate at predetermined intervals and stores the quantization Q in one Memory for future use in the next interval. The decoder calls just re-quantize the memory for each interval. This would  require extra storage. For example, an on-chip SRAM would be SRAM, which is on a chip, with 256 bits of 2 bits (to display a change in q by +2, +1, 0, -1 or to save Q as 1, 2, 3, 4) sufficient to change the Q quantization every 16 lines for a 4096 line image.

There are many options for rate measurement. Fig. 34 shows an encoder and decoder pair. Referring to Figure 34, there is shown an encoder / decoder pair including context models (CM), probability estimation models (PEM) and bit generators (BG) along with a run count reorder unit. ), an interleaved word reorder unit and a shifter. All of this is well known in the art. For the description, reference is made to US Pat. Nos. 5,381,145 and 5,583,500 by the present applicant, the contents of which are hereby incorporated by reference.

The rate measurement must be explicit if the decoder is not in the same place or can measure at the same place. For example, the rate measurement is the decoder provided as part of the compressed code stream.

Another option for rate handling, shown as the smaller circle (position 2 in Figure 34), is to count the start of the interleaved words in the encoder. In another embodiment, this is done after the biting stage (position 4 in Figure 34). Because the encoder and decoder start a codeword at the same time, implicit rate signaling can be used. The counting may be performed with a counting hardware comprising a register and an adder which adds the code word lengths and determines the average code word length. Hardware for performing the counting and determining an average number of bits is well known in the art and is shown as block 3401 in FIG . It is obvious that this block can be used to perform similar measurements at other locations in the system (e.g., positions 1, 2, 3, 4 on both the encoder and decoder).

Other options would be to count the size of completed codewords after the bit generator and before the nested word reordering unit (position 3 in Figure 34), or determine the current amount of data written to the disk (position 1 in Figure 34).

The rate measurement may be implicit: both the encoder and the decoder perform the same rate determination calculation. For example, the encoder and decoder could accumulate the average size of a codeword each time a new codeword is started. This is represented by the position in FIG . (The current size can not be used because the encoder does not know the size to the end of the codeword). If the R codes used in the core vary in size from R2 (0) to R2 (7), the average codeword size varies from 1 to 4.5 bits. If the probability estimate works well, the use of the middle should be very accurate. In other cases, the differences between the minimum and maximum codeword length are typically not as large as the mean, so the estimate should still be useful. The average size of an Rz (k) codeword is (k / 2) +1 bits.

It may be the goal that in almost all cases the most important data is compressed well and no quantization (Q = 1) will be required. Only "pathological" Images will require quantization (Q <1). Including the quantisie However, it can guarantee that the system is not pathological Pictures will collapse.

Another advantage of encoder rate control is that coding is less important Data can be stopped when the maximum bandwidth is exceeded. This  increases the speed of coding and reduces the total time out given data (eg the total printing time is reduced).

Continuously tracking the effects of quantization changes (the value of Q) is important. For example, the definition of the largest coefficient in a Group of coefficients to be consistent with the quantization changes. As well the reconstruction of quantized coefficients (if bit planes omitted) must be omitted the number of omitted bit-planes to achieve the best results account.

High speed parallel coding and context model

The entropy coding portion of the present invention comprises two parts. First High-speed encoding cores that work in parallel are likely to do so assessment and biter production. Second, a contextual model represents the Contexts ready to be used for coding.

The number of cores needed to achieve the desired speed be, is application-dependent.

The other part of the entropy coding system is the context model for the coefficients of the present invention. There are a large number of tradeoffs involved in the Implementation of the context model are possible. In one embodiment provides The present invention is a context model with a low hardware cost, the one Parallelism provides for the use of high-speed parallel encoders to assist the present invention. Embodiments of the context model are described above.

Although only the context model for wavelet coefficients is described herein, FIG The present invention is not limited to context models that use only wavelet coefficients  supporting clients. For example, if a bit-plane encoding mode for binary or spot color images is desired to use an additional contextual model, as it is z. In U.S. Patent Application No. 08 / 642,518, filed May 3, 1996, entitled "Compression and Decompression with Wavelet Style and Binary Style Including Quantization by Device Dependent Parser, "and in the US patent application No. 08 / 643,268, filed May 3, 1996, entitled "Compression / Decompres sion Using Reversible Embedded Wavelets ".

parallelism

In one embodiment, four high speed encoding cores are used to encode / decode 8 bits per coefficient, where coefficients are from 8 to 12 bits range (13, if a reversible color space is used). In one execution form, a kernel is assigned to each component of the four components, whereby the parallelism and the data flow are simplified. Each coefficient can Use up to 16 cycles to encode / decode bits (including Ent decisions on foresight, etc.).

The present invention synchronizes the cores for each component, even if certain cores are unproductive because of their successful ones Foresight or another kernel handles a sign bit after a first "A" bit. The total time to run the context model depends on the data, in particular the effectiveness of the foresight and in a lesser extent Scope vary from the location of the first "on" bits.

The invention can be summarized in particular as follows:
A method and apparatus for performing compression and / or decompression is described. In one embodiment, the present invention includes a system including a buffer, a wavelet transform unit, and an encoder. The wavelet transform unit has an input connected to the buffer to perform a wavelet transform with the pixels stored therein and to produce coefficients at the output. The encoder is connected to the wavelet transform unit to encode the transformed pixels received from the buffer.

LIST OF REFERENCE NUMBERS Fig. 14

1401

Encode MIC

1402

Encode the position of the first LIC bit plane with data

1403

Set the current LIC bit plane to the first LIC bit plane with data

1404

All LIC bit planes encoded with data

1405

Encode a LIC bitmap

1406

Set the current LIC bit plane to the next LIC bit plane

Fig. 16

1601

Put current tree to first tree

1602

Encode SS coefficients

1603

Perform MIC (or tree) foresight (

FIG.

5)

1604

Is the MIC of the entire tree 0?

1605

Set current coefficients to first non-SS coefficients in the tree

1606

Set current bit-plane to first bit-plane with data

1607

Encode bits of a current coefficient in the current bit plane

1608

All bitplanes coded?

1609

Set the current bit-level to the next bit-level

1610

Is current coefficient 0?

1611

Encode sign bit

1612

Set current coefficients to nearest coefficients in the tree

1613

All coefficients encoded in the tree?

1614

All trees encoded?

Fig. 19

1901

Put current tree to first tree

1902

Set current coefficients to first non-SS coefficients in the tree

1903

At the start of a foresight interval?

1904

foresee

1905

Foresight enabled?

1906

Code head or tail bit

1907

First non-zero bit?

1908

Encode sign bit

1909

All coefficients encoded in the tree?

1910

Set current coefficients to the nearest coefficient in the tree by default

1911

All coefficients encoded in the tree?

1912

Set current coefficients to the nearest coefficient in the tree

1913

All trees encoded?

Claims (78)

1. System with:
a buffer;
a wavelet transform unit having an input connected to the buffer for performing a reversible wavelet transform on pixels stored in the buffer and producing coefficients at an output;
an encoder coupled to the wavelet transform unit to encode bit planes of wavelet-transformed pixels from the wavelet transform unit and stored bit planes of wavelet-transformed pixels received from the buffer. 2. The system of claim 1, wherein the buffer comprises a band buffer to to save at least a band of pixels. The system of claim 1, wherein the encoder comprises:
a context model; and
a parallel entropy coder;
wherein the key data is not embedded and encoded in a buffers-free-of-buffers order, a part of less important data is buffered, embedded, and written to memory in the order of importance. 4. The system of claim 1, wherein the encoder is a high speed parallelism encoder. The system of claim 1, wherein the encoder comprises a QM encoder includes. The system of claim 1, wherein the encoder comprises an encoder with a state machine comprising finite states or an FSM encoder. The system of claim 1, further comprising an interface for encoded data includes. 8. A method of compressing information comprising the steps of:
a wavelet transform of pixel information received from a buffer is performed, wherein at least one bit-plane of coefficients represents reversible wavelet-transformed pixels;
the pixels in the buffer are replaced by coded bit planes; and
Bit planes stored in the buffer are encoded. 9. decompression system comprising:
a band buffer;
a number of coding units for coefficients to undergo an inverse transform operation;
at least one encoding unit for storing pixels to be output to an output device;
at least one encoding unit for pixels corresponding to previously inverted transformed coefficients to be sent to the output device;
a decompressor connected to the band buffer, the decompressor decompressing compressed data into transformed coefficients, writing the transformed coefficients to the band buffer, reading back transformed coefficients from the band buffer, inverse transforming with the transformed coefficients read back from the band buffer , is performed to generate pixel values and writes pixel values to the band buffer. 10. decompression system according to claim 9, wherein the decompressor reads compressed data from a storage area. The decompression system of claim 10, wherein the storage area includes a hard disk. 12. decompression system according to claim 9, further comprising a printing machine which is connected to the band buffer. 13. Method comprising the following steps:
a coefficient is split into key data and less important data;
the most important data is sent to a context model for immediate coding in coefficient order or coefficient order;
the less important data and a number of signaling bits are stored in a memory; and
after encoding the most important data of all the coefficients in the set of coefficients, the less important data are encoded and embedded in accordance with an order based in part on the number or plurality of signaling bits. 14. The method of claim 13, wherein the signaling bits comprise a first bit and include a second bit.   15. The method of claim 13, wherein a first of the signaling bits indicates if the first bit of the less important data of the coefficient is a header or a Tail bit and a second of the signaling bits indicates the sign bit, if that first of the signaling bits indicates that the first bit of the less important data of the Coefficient is a bit header. 16. The method of claim 13, wherein the signaling bits adjacent to less important data are stored. 17. Forward transformation, comprising:
an input buffer having an input connected to receive input data and first and second outputs for transmitting even and odd samples;
a first-level transform unit connected to receive the even and odd values and to generate coefficients, wherein horizontal low-pass and vertical high-pass coefficients represent outputs of the pre-wait transform;
a memory having a first input connected to receive ss coefficients generated by the first-level transformation and by the first level transformation of the first level transformation unit and a second input by ss, respectively Receive coefficients from higher level transform filtering;
an ordering unit having a first input connected to the memory for ordering ss coefficients for higher levels of filtering; and
a first filter unit connected to the ordering unit for applying a number of transformation levels, the filter unit performing a transformation of ss coefficients according to a higher level and a higher level transformation ss coefficients, respectively, received from the ordering unit wherein the filter unit generates ss coefficient values which are fed back to the second input of the memory and to the second input of the ordering unit. 18. A forward transform according to claim 17, wherein the first-level trans formation with 2 × 2 blocks of input data works or processes this. 19. A forward transform according to claim 17, wherein the initial level transformation comprises:
a second filter unit for performing a first level horizontal transformation in which the second filter unit has first and second outputs; a first single delay connected to the first output of the second filter;
a second single delay connected to the second output of the second filter;
a double delay connected to the second output of the second filter;
a first multiplexer connected to receive the outputs of the first single delay and the double delay;
a second multiplexer connected to receive an output of the first filter unit and an output of the second single delay; and
a third filter unit connected to receive the outputs from the first and second multiplexers and to perform a first level vertical transformation. 20. An apparatus for compressing an image, the apparatus comprising:
a compressor;
a workspace memory connected to the compressor, the workspace memory having the same size as the image, and the compressor using the workspace memory to encode the image by using coefficients greater than the pixels in the image. 21. A method of encoding information comprising the most important data and the less important data, the method comprising the steps of:
Coding the most important data;
Encoding the position of the first bit plane in the less important data for each coefficient that is not entirely zero header bits;
Encoding each bitplane of less important data that is not entirely zero overhead bits. 22. The method of claim 21, wherein the information is wavelet coefficients includes. 23. The method of claim 21, wherein the step of encoding the Position the first less important bit-plane performing a foresight across the entire bitplanes of less important data. 24. The method of claim 21, wherein the step of encoding the most important data comprises the steps of:
for every tree,
Encoding the ss coefficient;
Performing a foresight for the most important data; and
for each non-ss coefficient,
Coding a header or tail bit for each bit-plane with data
and
Encoding a sign bit if the coefficient is not zero. 25. The method of claim 24, wherein the anticipation or the prediction includes a tree anticipator, and the step of Performing the foresight, coding the ss coefficients and coding the first one Zero bit-plane with non-zero overhead bits for the entire tree. 26. The method of claim 24, wherein the most important data with a Wavelet tree at one time or wavelet tree for wavelet tree processed the. 27. The method of claim 21, wherein the anticipating bit planes true, all zero overhead bits for all non-ss coefficients in the wavelet tree include. The method of claim 27, further comprising the steps of identifying the first bit level to encode individually. 29. The method of claim 28, wherein the step of identifying the first bit plane to encode individually, indicating that all non-ss coeffi the second decomposition are zero, using a first bit, and that Indicate that all non-ss coefficients of the first decomposition are zero, below Using a second bit. 30. The method of claim 21, wherein the step of encoding the most important data comprises the steps of:
for every tree
Encoding the ss coefficient;
Performing a prediction to determine bit planes that are all zero overhead bits for all non-SS coefficients in each tree;
it is determined if the most important data of the whole tree is zero;
if the most important data of the whole tree is not zero, then
for all coefficient in the tree
Bits of the current coefficient for all bit-planes are encoded, the current coefficient being the first non-ss coefficient in the tree and starting with the first bit-plane containing data;
the sign bit is encoded if the current coefficient is not zero. 31. The method of claim 21, wherein the step of encoding the less important data comprises the steps of:
for every tree;
for each coefficient;
foresight is performed if at the start of a previous viewing interval;
Coding a header or tail bit if foresight is not active;
and
Encoding a sign bit if the first one bit has occurred and the look ahead is not active. 32. Apparatus for coding information comprising the most important data and the less important data, the apparatus comprising:
means for encoding the most important data;
means for encoding the position of the first bit plane in the less important data for each coefficient that does not consist entirely of zero overhead bits;
means for encoding each bitplane of less important data that does not consist entirely of zero overhead bits. The apparatus of claim 32, wherein the information is wavelet coefficients includes. 34. Apparatus according to claim 32, wherein the means for coding the Position of the first less important bit-plane means to perform of foreseeing the entire bit-planes of less important data. 35. Apparatus according to claim 32, wherein said means for encoding the most important data comprises:
means for encoding the SS coefficient for each tree;
means for making a prediction of the most important data for each tree;
means for coding a header or tail bit for each bit plane with data for each non-SS coefficient for each tree; and
means for encoding a sign bit if the coefficient for each non-SS coefficient for each tree is not zero. The apparatus of claim 35, wherein the anticipation is a tree prediction and the means for performing the foresight comprises means for encoding the SS coefficients and means for encoding the first one Zero-bit level with non-zero overhead bits for the entire tree. 37. Apparatus according to claim 35, wherein the most important data according to a Wavelet tree at one time or wavelet tree for wavelet tree processed the. 38. Apparatus according to claim 32, wherein the means for performing the Predictably, the bit planes determine all the zero overhead bits for all non-ss coefficients include in the wavelet tree.   39. Apparatus according to claim 38, further comprising means for identifying the first bit level to encode individually. 40. Apparatus according to claim 39, wherein the means for identifying the first bit plane to encode individually, includes means to under Use a first bit to indicate that all non-ss coefficients of the second Zeros are zero, and means include using a second bits indicate that all non-ss coefficients of the first decomposition are zero are. 41. Apparatus according to claim 32, wherein said means for encoding the most important data comprises:
means for coding the SS coefficient for each tree;
means for performing a look-ahead to determine bit planes that are all zero overhead bits for all non-SS coefficients in each tree;
means for determining if the most important data of the whole tree is zero for each tree; and
means for encoding bits of the current coefficient for all bit-planes in the tree if the most important data for the whole tree is non-zero, the current coefficient being the first non-ss coefficients in the tree and being at the first bit-plane is started, which contains data;
means for encoding the sign bit if the current coefficient is not zero for all coefficients in the tree if the most important data for the whole tree is not zero. 42. Apparatus according to claim 32, wherein the means for encoding the less important data comprises:
means for performing a prediction for each coefficient for each tree, if at the start of a foresight interval;
means for coding a header or tail bit for each coefficient for each tree if the anticipation is not active; and
means for encoding a sign bit for each coefficient for each tree if the first one bit has occurred and the look ahead is not active. 43. A method for m-ary encoding information, the method comprising the steps of:
a predetermined number of coefficients are examined;
entropy coding each header bit with one per cycle until all header bits in the predetermined number of coefficients are encoded;
encoding the sign and tail bits of the predetermined number of coefficients in the same cycle. 44. An integrated circuit (IC) chip, comprising:
a pixel data interface for transferring pixel data between the IC chip and the memory;
a reversible wavelet transform connected to the pixel data interface to transfer information to and from the memory via the pixel data interface;
a context model coupled to the reversible wavelet transform to provide contexts for encoding the data supplied thereby;
an encoder to encode coefficients generated by the reversible wavelet transform based on contexts provided by the context model. 45. The IC of claim 44, further comprising a coefficient data interface, which is connected to coefficient from the transformation to the memory without To transfer coding.   46. The IC of claim 44, wherein the coefficient data interface is Koeffi from the memory to the context model for coding. 47. The IC of claim 44, further comprising an interface for encoded data. to provide entropy-coded data to the memory. The IC of claim 47, further comprising a decoder to encode data to decode. The IC of claim 46, further comprising an interface for encoded data. to provide the decoder with entropy-coded data for decoding. 50. The IC of claim 44, further comprising a reversible color space converter. that between the pixel data interface and the reversible wavelet transform is connected to perform a reversible color space conversion. 51. A decoder for decoding coded data, the decoder comprising:
at least one bit generator connected to receive the encoded data and to decode the encoded data based on a probability estimate, the at least one bit generator generating a decoded bit from a current line;
a probability estimator connected to the at least one bit generator for providing the probability estimate based on the decoded bit from the current line;
a context model coupled to the probability estimator to provide a number of contexts to the probability estimator based on a partial context address, wherein the probability estimator selects among the plurality of contexts based on the decoded bit. 52. The decoder of claim 51, further comprising an indicator for like addresses or an equal-address indicator that corresponds to the probability estimate machine is connected to detect the addresses that have already been read indicating that the data is already in probability estimation engine, the same address indicator providing an indication of the Probability estimator generated that indicates that the data is already in one Probability estimation engine, based on the sub-context, the is addressed. 53. The decoder of claim 51, further comprising a number of shift registers which are attached to the context model to the sub-context address provide. 54. The decoder of claim 51, further comprising a line buffer to is closed to provide a number or upper row of lines. 55. Context Model, comprising:
a first bit plane unit connected to receive less important data and most important data to determine which bit planes have data in it, the first bit plane unit displaying the bit plane having the first one bit for the entire coding unit for use, when the less important data is processed, generated;
a comparison mechanism connected to receive the less important data and the most important data to generate signaling information for the less important data;
a memory coupled to receive the sign bit, the most important data, and a first bit-plane indication with data, the memory delaying coefficients to provide conditioning information;
a first context model connected to the memory to provide sign bits contexts;
a second context model connected to the memory and the most important data to provide contexts for the header bits; and
the third context model attached to the memory and the most important data to provide tail bits contexts. 56. Context model according to claim 55, further comprising a separation mechanism, to divide the input data into the more important and less important data. 57. Context model according to claim 56, wherein the separation mechanism or Separation mechanism comprises a barrel slide or "barrel" slider. 58. Context model according to claim 57, wherein the barrel slide data shifts based on a quantization level. 59. The contextual model of claim 55, wherein the comparison mechanism comprises:
a first compare unit for determining if the most important data is equal to zero to indicate that a tail bit has already occurred, the output of the first compare unit being a tail-a-bit;
a second compare unit for determining if the most important data is equal to one, an output of the second compare unit being equal to zero if the most important data is equal to one; and
a multiplexer connected to receive the output of the second compare unit and the sign bit to output a first tail bit if the select input is in a first state and to output the sign if the select input is in a second state , 60. The contextual model of claim 58, wherein the selected input is the Tail-in-output of the first comparison unit.   61. The contextual model of claim 58, wherein at least one of the first or second comparison unit comprises a bit comparator. 62. The context model of claim 55, wherein the first bit level comprises:
an OR gate connected to receive a coefficient and a feedback;
a register connected to receive the output of the OR gate; and
a priority encoder connected to receive the output of the register for recording the first bit-plane of the coefficient having a one. 63. The context model of claim 62, wherein the register has a reset input to reset the contents of the register at the start of the coding unit Zen. 64. The context model of claim 62, wherein the reset input is also the Resets the content or data content of the register at the start of each tree. 65. A method of performing compression comprising the following steps:
the average length of codewords is determined to identify a coding rate; and
a compression rate is adjusted based on a desired amount of compression. 66. The method of claim 65, further comprising the steps of:
a degree of quantization level is increased if the coding rate indicates that the compression is below a first desired level; and
the degree of quantization is lowered if the coding rate indicates that the compression is above the second desired level. 67. The method of claim 66, wherein the first and second desirable Level are not the same. 68. The method of claim 65, wherein the step of determining the average length of codewords after bit generation. 69. The method of claim 65, further comprising the step of providing a Decoder a new compression rate is signaled. 70. The method of claim 69, wherein the signaling is explicit. 71. The method of claim 69, wherein the signaling is implicit. 72. System comprising:
a context model;
a probability estimator that is connected to the context model;
a bit generator connected to the probability estimator; and
a coding rate controller connected to an output of the bit generator to control the coding rate by determining a mean code word length. 73. The system of claim 72, wherein a coding rate control is a quanti adjusted or adjusted. 74. The system of claim 72 including a signaling block for decoding to signal with respect to a new quantization level. 75. The system of claim 72, further comprising a signaling block to To generate header data for a compressed data stream output of the encoder, the is chained to the compressed bitstream to give the encoder a new quantization level. 76. The system of claim 72, wherein the coding rate control is a display of quantization level stores for subsequent use the decoder is necessary. 77. A method of processing a least significant portion of data bit-planes for a set of transformed coefficients, comprising the steps of:
a first part of data is read from a memory; and
a second data set greater than the first is written to the memory while the first data set is read to balance transformed bit planes with less data in the lower order bit planes of the set of transformed coefficients. 78. The method of claim 77, wherein the bits used to store the Coefficients required for the least significant part or batch are increasing as the bit plane number decreases.