Reversible embedded wavelet system implementation

• US 6,229,927 B1
• Filed: 11/05/1999
• Issued: 05/08/2001
• Est. Priority Date: 09/21/1994
• Status: Expired due to Fees

• Current Assignee: Ricoh Company Limited, Ricoh Corporation (Ricoh Company Limited)
• Original Assignee: Ricoh Company Limited, Ricoh Corporation (Ricoh Company Limited)
• Inventors: Schwartz, Edward L.
• Primary Examiner(s): Tran, Phuoc
• Application Number:
  US09/435,018
• Time in Patent Office: 550 Days
• Field of Search: 382/232, 382/240, 382/244, 382/248, 382/260, 382/263, 382/264, 382/251, 341/50, 341/51, 341/52, 708/300, 708/301, 708/308, 708/400, 708/401, 708/203
• US Class Current: 382/248
• 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 forward transform comprising

an input buffer having an input coupled to receive input data and first and second outputs to transfer even and odd samples;

a first level transform unit coupled to receive the even and odd samples and generate coefficients, wherein horizontal low pass and vertical high pass coefficients are outputs of the forward transform

a memory having a first input coupled to receive ss coefficients generated by the first level transform the first level transform unit and a second input to receive ss coefficients from higher level transform filtering;

an order unit having a first input coupled to the memory to order ss coefficients for higher levels of filtering; and

a first filter unit coupled to the order unit to apply a plurality of transform levels, wherein the filter unit performs a higher level transform ss coefficients received from the order unit, wherein the filter unit generates ss coefficients values that are fed back to the second input of the memory and the second input the order unit.

2. The forward transform defined in claim 1 wherein the first level transform operates on 2×

2 blocks of input data.

3. The forward transform defined in claim 1 wherein the first level transform comprises:

a second filter unit to perform a first level horizontal transform, wherein the second filter unit having a first output and a second output;

a first single delay coupled to the first output of the second filter;

a second single delay coupled to the second output of the second filter;

a double delay coupled to the second output of the second filter;

a first multiplexer (MUX) coupled to receive the outputs of the first single delay and the double delay;

a second MUX coupled to receive an output of the first filter unit and an output of the second single delay; and

a third filter unit coupled to receive outputs from the first and second muxes and to perform a first level vertical transform.

4. A context model comprising:

a first bit plane unit coupled to receive less important data and most important data to determine which bit planes have data in them, wherein the first bit plane unit generates an indication of the bit plane with the first on bit for the entire coding unit for use when processing the less important data;

a comparison mechanism coupled 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 an indication of the first bit plane having data, wherein the memory delays coefficients to provide conditioning information,

a first context model coupled to the memory to provide contexts for sign bits;

a second context model coupled to the memory and the most important data to provide contexts for head bits; and

the third context model coupled to the memory and the most important data to provide contexts for tail bits.

5. The context model defined in claim 4 further comprising a separation mechanism to separate the input data into the more and less important data.

6. The context model defined in claim 5 wherein the separation mechanism comprises a barrel shifter.

7. The context model defined in claim 6 wherein the barrel shifter shifts data based on a quantization level.

8. The context model defined in claim 4 wherein the comparison mechanism comprises:

a first comparison unit to determine if the most important data is equal to zero to indicate that a tail bit has already occurred, wherein the output of the first comparison unit is a tail on bit;

a second comparison unit to determine whether the most important data is equal to one, wherein an output of the second comparison unit is equal to zero when the most important data is equal to one; and

a multiplexer coupled to receive the output of the second comparison 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.

9. The context model defined in claim 7 wherein the select input comprises the tail on output of the first comparison unit.

10. The context model defined in claim 7 wherein a least one of the first and second comparison units comprises a bit comparator.

11. The context model defined in claim 4 wherein the first bit plane unit comprises:

an OR gate coupled to receive a coefficient and a feedback;

a register coupled to receive the output of the OR gate; and

a priority encoder coupled to receive the output of the register to record the first bit plane of the coefficient that has a 1.

12. The context model defined in claim 11 wherein the register includes a reset input to reset the contents of the register at the start of the coding unit.

13. The context model defined in claim 11 wherein the reset input also resets the contents of the register at the start of each tree.