Multiple coder technique

• US 20030138158A1
• Filed: 01/08/2003
• Published: 07/24/2003
• Est. Priority Date: 09/21/1994
• Status: Active Grant

• Current Assignee: Edward L. Schwartz
• Original Assignee: Edward L. Schwartz
• Inventors: Schwartz, Edward L.
• Granted Patent: US 6,990,247 B2
• Time in Patent Office: Days
• US Class Current: 382/240
• CPC Class Codes: G06F 17/148 Wavelet transforms
• CPC Class Codes: G06K 15/02 using printers
• CPC Class Codes: G06K 15/1865 by compressing the rasterized print data
• 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/122 Selection of transform size, e.g. 8x8 or 2x4x8 DCT; Selection of sub-band transforms of varying structure or type
• CPC Class Codes: H04N 19/124 Quantisation
• 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/156 Availability of hardware or computational resources, e.g. encoding based on power-saving criteria
• 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/18 the unit being a set of transform coefficients
• CPC Class Codes: H04N 19/184 : the unit being bits, e.g. of the compressed video stream
• CPC Class Codes: H04N 19/186 : the unit being a colour or a chrominance component
• CPC Class Codes: H04N 19/1883 : the unit relating to sub-band structure, e.g. hierarchical level, directional tree, e.g. low-high [LH], high-low [HL], high-high [HH]
• 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/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.

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 coder comprises:

a context model; and

a parallel entropy coder encoder;

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

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

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

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

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

8. A method for compressing information comprising the steps of:

wavelet transforming pixel information received from a buffer, wherein at least one bitplane of coefficients represents reversible wavelet transformed pixels;

replacing pixels in the buffer with encoded bitplanes; and

coding bitplanes stored in the buffer.

9. A decompression system comprising:

a band buffer;

a plurality of coding units for coefficients to undergo an inverse transform operation;

at least one coding unit for storing pixels to be output to an output device;

at least one coding unit for pixels corresponding to previously inversed transformed coefficients to be sent to the output device;

a decompressor coupled to the band buffer, wherein the decompressor decompresses compressed data to transformed coefficients, writes the transformed coefficients to the band buffer, reads back transformed coefficients from the band buffer, performs an inverse transform on transformed coefficients read back from the band buffer to generate pixel values and writes pixels values to the band buffer.

10. The decompression system defined in claim 9 wherein the decompressor reads compressed data from a storage area.

11. The decompression system defined in claim 10 wherein the storage area comprises a hard disk.

12. The decompression system defined in claim 9 further comprising a print engine coupled to the band buffer.

13. A method comprising the steps of:

dividing a coefficient into most important data and less important data;

sending the most important data to a context model for coding immediately in coefficient order;

storing the less important data and a plurality of signaling bits in memory; and

after coding most important data of all coefficients in the set of coefficients, coding the less important data and embedding by order based, in part, on the plurality of signaling bits.

14. The method defined in claim 13 wherein the signaling bits comprise a first bit and a second bit.

15. The method defined in claim 13 wherein a first of the signaling bits indicates if the first bit of the less important data of the coefficient is a head or tail bit, and a second of the signaling bits indicates the sign bit if the first of the signaling bits indicates that the first bit of the less important data of the coefficient is a head bit.

16. The method defined in claim 13 wherein the signaling bits are stored adjacent to the less important data.

17. 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.

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

2 blocks of input data.

19. The forward transform defined in claim 17 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.

20. An apparatus for compressing an image, said apparatus comprising:

a compressor;

a workspace memory coupled to the compressor, wherein the workspace memory is the same size as the image and the compressor uses the workspace memory for encoding the image using coefficients that are larger than the pixels in the image.

21. A method for coding information comprising most important data and less important data, said method comprising the steps of:

coding the most important data;

coding the position of the first bit plane in the less important data for each coefficient that is not comprised entirely of zero head bits;

coding each bit plane of less important data that does not entirely comprise of zero head bits.

22. The method defined in claim 21 wherein the information comprises wavelet coefficients.

23. The method defined in claim 21 wherein the step for coding the position of the first less important bit plane comprises performing a look-ahead over the entire bit planes of less important data.

24. The method defined in claim 21 wherein the step of coding the most important data comprises the steps of:

for each tree,

coding the ss coefficient;

performing a look ahead for the most important data; and

for each non-ss coefficient,

coding a head or tail bit for each bit plane with data, and

coding a sign bit if the coefficient is not zero.

25. The method defined in claim 24 wherein the look ahead comprises a tree look ahead, and the step of performing the look ahead comprises coding the ss-coefficients and coding the first zero bit plane with non-zero head bits for the whole tree.

26. The method defined in claim 24 wherein the most important data is processed one wavelet tree at a time.

27. The method defined in claim 21 wherein the lookahead determines bit planes that comprise all zero head bits for all non-ss coefficient in the wavelet tree.

28. The method defined in claim 27 further comprising the steps of identifying the first bit plane to code-individually.

29. The method defined in claim 28 wherein the step of identifying the first bit plane to code individually comprises indicating all non-ss coefficients of the second decomposition are zero using a first bit and indicating all non-ss coefficients of the first decomposition are zero using a second bit.

30. The method defined in claim 21 wherein the step of coding the most important data comprises the following steps:

for each tree

coding the ss coefficient;

performing a lookahead to determine bitplanes that are all zero head bits for all non-SS coefficients in said each tree;

determining if the most important data of the entire tree is zero;

if the most important data for the entire tree is not zero then,

for all coefficients in the tree,

coding bits of the current coefficient for all bitplanes, wherein the current coefficient is the first non-ss coefficient in the tree and starting with the first bit plane that contains data;

coding the sign bit if the current coefficient is not zero.

31. The method defined in claim 21 wherein the step of coding the less important data comprises the steps of:

32. An apparatus for coding information comprising most important data and less important data, said apparatus comprising:

means for coding the most important data;

means for coding the position of the first bit plane in the less important data for each coefficient that is not comprised entirely of zero headbits;

means for coding each bit plane of less important data that does not entirely comprise of zero head bits.

33. The apparatus defined in claim 32 wherein the information comprises wavelet coefficients.

34. The apparatus defined in claim 32 wherein the means for coding the position of the first less important bit plane comprises means for performing a look-ahead over the entire bit planes of less important data.

35. The apparatus defined in claim 32 wherein the means for coding the most important data comprises:

means for coding the SS coefficient for each tree;

means for performing a look ahead for the most important data for each tree;

means for coding a head or tail bit for each bit plane with data for each non-SS coefficient for each tree; and

means for coding a sign bit if the coefficient is not zero for each non-SS coefficient for each tree.

36. The apparatus defined in claim 35 wherein the look ahead comprises a tree look ahead, and the means for performing the look ahead comprises means for coding the SS-coefficients and means for coding the first zero bit plane with non-zero head bits for the whole tree.

37. The apparatus defined in claim 35 wherein the most important data is processed one wavelet tree at a time.

38. The apparatus defined in claim 32 wherein the means for performing the lookahead determines bit planes that comprise all zero head bits for all non-ss coefficient in the wavelet tree.

39. The apparatus defined in claim 38 further comprising means for identifying the first bit plane to code individually.

40. The apparatus defined in claim 39 wherein the means for identifying the first bit plane to code individually comprises means for indicating all non-ss coefficients of the second decomposition are zero using a first bit and means for indicating all non-ss coefficients of the first decomposition are zero using a second bit.

41. The apparatus defined in claim 32 wherein the means for coding the most important data comprises:

means for coding the SS coefficient for each tree;

means for performing a lookahead to determine bitplanes that are all zero head bits for all non-SS coefficients in said each tree;

means for determining if the most important data of the entire tree is zero for each tree; and

means for coding bits of the current coefficient for all bitplanes for all coefficients in the tree if the most important data for the entire tree is not zero, wherein the current coefficient is the first non-ss coefficient in the tree and starting with the first bit plane that contains data;

means for coding the sign bit if the current coefficient is not zero for all coefficients in the tree if the most important data for the entire tree is not zero.

42. The apparatus defined in claim 32 wherein the means for coding the less important data comprises:

means for performing a lookahead for each coefficient for each tree if at the start of a lookahead interval;

means for coding a head or tail bit for each coefficient for each tree if the lookahead is not active; and

means for coding a sign bit for each coefficient for each tree if the first on bit has occurred and the lookahead is not active.

43. A method for m-ary coding of information, said method comprising the steps of:

examining a predetermined number of coefficients;

entropy coding all of the head bits one per cycle until all head bits in the predetermined number of coefficients are coded;

coding 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 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;

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

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

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

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

48. The IC defined in claim 47 further comprising a decoder to decode encoded data.

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

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

51. A decoder for decoding coded data, said decoder comprising:

at least one bit generator coupled to receive the coded data and to decode the coded data based on a probability estimation, wherein said at least one bit generator generates a decoded bit from a current line;

a probability estimation machine coupled to said at least one bit generator to provide the probability estimate based on the decoded bit from the current line;

a context model coupled to the probability estimation machine to provide a plurality of contexts to the probability estimation machine based on a partial context address, wherein the probability estimation machine selects among the plurality of context based on the decoded bit.

52. The decoder defined in claim 51 further comprising a same address indicator coupled to the probability estimation machine to detect addresses that have already been read indicating that the data is already available in the probability estimation machine, wherein the same address indicator generates an indication to the probability estimation machine indicating that the data is already in a probability estimation machine based on the partial context being addressed.

53. The decoder defined in claim 51 further comprising a plurality of shift registers coupled to the context model to provide the partial context address.

54. The decoder defined in claim 51 further comprising a line buffer coupled to provide a plurality of above lines.

55. 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.

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

57. The context model defined in claim 56 wherein the separation mechanism comprises a barrel shifter.

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

59. The context model defined in claim 55 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.

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

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

62. The context model defined in claim 55 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.

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

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

65. A method for performing compression comprising the steps of:

determining the average length of codewords to identify an encoding rate; and

adjusting a compression rate based on a desired amount of compression.

66. The method defined in claim 65 further comprising the step of:

increasing an amount of quantization level if the encoding rate indicates compression is below a first desirable level; and

decreasing the amount of quantization if the encoding rate indicates that compression is above the second desired level.

67. The method defined in claim 66 wherein the first and second desirable levels are not the same.

68. The method of claim 65 wherein the step of determining the average length of codewords is performed after bit generation.

69. The method of claim 65 further comprising the step of signaling a new compression rate to a decoder.

70. The method of claim 69 wherein the signaling is explicit.

71. The method of claim 69 wherein the signaling is implicit.

72. 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.

73. The system defined in claim 72 wherein an encoder rate control adjusts quantization.

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

75. The system defined in claim 72 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.

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

77. A method for processing a least important portion of data bitplanes for a set of transformed coefficients, and method comprising the steps of:

reading a first portion of data from memory; and

writing a second amount of data greater than the first to memory while reading the first amount of data to compensate for transformed bitplanes with less data in the lower order bitplanes of the set of transformed coefficients.

78. The method defined in claim 77 wherein the bits required to store the least important chunk coefficients increase as the bit plane number decreases.