Reversible embedded wavelet system implementation

• US 7,016,545 B1
• Filed: 11/01/2000
• Issued: 03/21/2006
• Est. Priority Date: 09/21/1994
• Status: Expired due to Fees

• Current Assignee: Ricoh Company Limited
• Original Assignee: Ricoh Company Limited
• Inventors: Gormish, Michael J., Schwartz, Edward L., Boliek, Martin, Zandi, Ahmad, Keith, Alexander
• Primary Examiner(s): SHERALI, ISHRAT I
• Application Number:
  US09/704,991
• Time in Patent Office: 1,966 Days
• Field of Search: 382239-240, 382244-250, 375/240.11, 375/240.18, 375/240.19
• US Class Current: 382/239
• CPC Class Codes: G06F 17/148 Wavelet transforms
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: H04N 19/10 using adaptive coding
• CPC Class Codes: H04N 19/102 characterised by the element, parameter or selection affected or controlled by the adaptive coding
• CPC Class Codes: H04N 19/115 Selection of the code volume for a coding unit prior to coding
• CPC Class Codes: H04N 19/12 Selection from among a plurality of transforms or standards, e.g. selection between discrete cosine transform [DCT] and sub-band transform or selection between H.263 and H.264
• CPC Class Codes: H04N 19/129 Scanning of coding units, e.g. zig-zag scan of transform coefficients or flexible macroblock ordering [FMO]
• CPC Class Codes: H04N 19/13 Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
• CPC Class Codes: H04N 19/14 Coding unit complexity, e.g. amount of activity or edge presence estimation H04N19/146 takes precedence
• CPC Class Codes: H04N 19/146 Data rate or code amount at the encoder output
• CPC Class Codes: H04N 19/15 by monitoring actual compressed data size at the memory before deciding storage at the transmission buffer
• CPC Class Codes: H04N 19/162 User input
• CPC Class Codes: H04N 19/167 Position within a video image, e.g. region of interest [ROI]
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 19/186 the unit being a colour or a chrominance component
• CPC Class Codes: H04N 19/36 Scalability techniques involving formatting the layers as a function of picture distortion after decoding, e.g. signal-to-noise [SNR] scalability
• CPC Class Codes: H04N 19/42 characterised by implementation details or hardware specially adapted for video compression or decompression, e.g. dedicated software implementation H04N19/635 takes precedence
• CPC Class Codes: H04N 19/46 Embedding additional information in the video signal during the compression process H04N19/517, H04N19/68, H04N19/70 take precedence
• CPC Class Codes: H04N 19/593 involving spatial prediction techniques
• CPC Class Codes: H04N 19/60 using transform coding
• CPC Class Codes: H04N 19/61 : in combination with predictive coding
• CPC Class Codes: H04N 19/63 : using sub-band based transform, e.g. wavelets
• CPC Class Codes: H04N 19/635 : characterised by filter definition or implementation details
• CPC Class Codes: H04N 19/647 : using significance based coding, e.g. Embedded Zerotrees of Wavelets [EZW] or Set Partitioning in Hierarchical Trees [SPIHT]
• CPC Class Codes: H04N 19/98 : Adaptive-dynamic-range coding [ADRC]
• CPC Class Codes: H04N 21/6377 : directed to server one-way streaming services wherein the source is controlled by the destination H04L65/613
• CPC Class Codes: H04N 21/658 : Transmission by the client directed to the server

Abstract

A method and apparatus for performing compression and/or decompression is described. In one embodiment, the present invention comprises a system having a buffer, a wavelet transform unit, and a coder. The wavelet transform unit has an input coupled to the buffer to perform a wavelet transform on pixels stored therein and to generate coefficients at an output. The coder is coupled to the wavelet transform unit to code the transformed pixels received from the buffer.

Claims

1. A system comprising:

a buffer;

a wavelet transform unit having an input coupled to the buffer to perform a reversible wavelet transform on pixels stored in the buffer and to generate coefficients at an output;

a coder coupled to the wavelet transform unit to code bitplanes of wavelet transformed pixels from the wavelet transform unit and stored bitplanes of wavelet transformed pixels received from the buffer, wherein the coder comprises

a context model, and

a parallel entropy coder encoder, and

wherein the most important data is not embedded and is coded in coefficient order without buffering, a portion of less important data is buffered, embedded and written to memory in order of importance.

2. The system defined in claim 1 wherein the buffer comprises a band buffer to store at least one band of pixels.

3. The system defined in claim 1 wherein the encoder comprises a high speed parallel coder.

4. The system defined in claim 1 wherein the encoder comprises a QM-coder.

5. The system defined in claim 1 where the encoder comprises a finite state machine coder.

6. The system defined in claim 1 further comprising a coded data interface.

7. An integrated circuit (IC) chip comprising:

a pixel data interface to transfer pixel data between the IC chip and memory;

a reversible wavelet transform coupled 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 coding the data provided therefrom; and

an encoder to encode coefficients generated by the reversible wavelet transform based on contexts provided by the context model, wherein the encoder encodes a first data of coefficients in a set of coefficients in coefficient order, and wherein the encoder then encodes a second data and embeds the second data by order based, in part, on a plurality of signaling bits, the first data having a higher priority than the second data.

8. The IC defined in claim 7 further comprising a coefficient data interface coupled to transfer coefficients from the transform to the memory without coding.

9. The IC defined in claim 7 wherein the coefficient data interface transfers coefficients from memory to the context model for encoding.

10. The IC defined in claim 7 further comprising a coded data interface for providing entropy coded data to memory.

11. The IC defined in claim 10 further comprising a decoder to decode encoded data.

12. The IC defined in claim 9 further comprising a coded data interface to provide the decoder with entropy coded data for decoding.

13. The IC defined in claim 7 further comprising a reversible color space converter coupled between the pixel data interface and the reversible wavelet transform to perform reversible color space conversion.

24. The method defined in claim 7 wherein the encoder codes bit planes of wavelet transformed pixels from the reversible wavelet transform and stored bit planes of wavelet transform pixels.

14. A system comprising:

a context model;

a probability estimation machine coupled to the context model;

a bit generator coupled to the probability estimation machine; and

an encoder rate control coupled to an output of the bit generator to control the encoding rate by determining average codeword length, wherein the encoder rate control encodes a first data of coefficients in a coefficient order, and wherein the encoder rate control then encodes a second data and embeds the second data by order based, in part, on a plurality of signaling bits, the first data having a higher priority than the second data.

15. The system defined in claim 14 wherein an encoder rate control adjusts quantization.

16. The system defined in claim 14 comprising a signaling block to signal a decoder regarding a new quantization level.

17. The system defined in claim 14 further comprising a signaling block to generate header data for a compressed data stream output of the encoder which is concatenated onto the compressed bit stream to indicate to the decoder a new level of quantization.

18. The system defined in claim 14 wherein the encoder rate control stores an indication of the quantization level is necessary for subsequent use by the decoder.

19. A system comprising:

modeling means for providing contexts;

probability estimating means for providing probability estimates in response to contexts from the context model;

bit generation means for providing zero or more bits in response to probability estimates from the probability estimating means; and

encoder rate control means for coupled to an output of the bit generation means for controlling the encoding rate by determining average codeword length, wherein the encoder rate control means encodes a first data of coefficients in a coefficient order, and wherein the encoder rate control means then encodes a second data and embeds the second data by order based on at least one or more signaling bits, the first data having a higher importance than the second data.

20. The system defined in claim 19 wherein an encoder rate control means adjusts quantization.

21. The system defined in claim 19 further comprising means for signaling a decoder regarding a new quantization level.

22. The system defined in claim 19 further comprising means for generating header data for a compressed data stream output of the encoder which is concatenated onto the compressed bit stream to indicate to the decoder a new level of quantization.

23. The system defined in claim 19 wherein the encoder rate control means stores an indication of the quantization level is necessary for subsequent use by the decoder.

25. An integrated circuit (IC) chip comprising:

a pixel data interface to transfer pixel data between the IC chip and memory;

a reversible wavelet transform coupled 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 coding the data provided therefrom; and

an encoder to encode coefficients generated by the reversible wavelet transform based on contexts provided by the context model,

wherein the encoder codes the most important data of coefficients in a set of coefficients immediately in coefficient order and then codes the less important data and embeds the less important data by order based, in part, on a plurality of signaling bits.