Reversible wavelet transform and embedded codestream manipulation

• US 5,867,602 A
• Filed: 06/30/1995
• Issued: 02/02/1999
• Est. Priority Date: 09/21/1994
• Status: Expired due to Term

• Current Assignee: Ricoh Company Limited
• Original Assignee: Ricoh Company Limited, Ricoh Corporation (Ricoh Company Limited)
• Inventors: Gormish, Michael J., Schwartz, Edward L., Boliek, Martin, Zandi, Ahmad
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Tran, Phuoc
• Application Number:
  US08/498,036
• Time in Patent Office: 1,313 Days
• Field of Search: 382/232, 382/240, 382/244, 382/247, 382/248, 382/260, 382/276, 382/233, 348/398
• 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/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/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/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/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 compression and decompression system in which a reversible wavelet filter are used to generates coefficients from input data such as image data. The reversible wavelet filter is an efficient transform implemented with integer arithmetic that has exact reconstruction. The present invention uses the reversible wavelet filter in a lossless system (or lossy system) in which an embedded codestream is generated from the coefficients produced by the filter. An entropy coder performs entropy coding on the embedded codestream to produce the compressed data stream.

Claims

1. An encoder for encoding input data into a compressed data stream, said coder comprising:

a reversible wavelet filter for transforming the input data into a plurality of coefficients using a pyramidal decomposition;

an ordering and modeling mechanism coupled to the reversible wavelet filter, said ordering and modeling mechanism generating an embedded codestream in response to the plurality of coefficients, wherein the ordering and modeling order the plurality of coefficients and order binary values within each of the plurality of coefficients; and

a binary entropy coder, coupled to the ordering and modeling mechanism, operable to binary entropy code the embedded codestream to produce the compressed data stream.

2. The encoder defined in claim 1 wherein the reversible wavelet filter performs the pyramidal decomposition of the input data using a series of TS and S transforms.

3. The encoder defined in claim 1 wherein the reversible wavelet filter produces a series of coding units which undergo embedded coding and binary entropy coding using a set of statistics and probabilities, and further wherein the statistics and probabilities are reset at the start of coding of each coding unit.

4. The encoder defined in claim 1 wherein the encoding of the second bit is conditioned on its bit position from an initial one bit.

5. The encoder defined in claim 1 wherein the ordering and modeling mechanism uses a series of coefficients surrounding a particular coefficient as a context, and further wherein each of the series of coefficients contributes at least one bit for the context.

6. The encoder defined in claim 5 wherein a predetermined number of the coefficients provide an extra bit.

7. The encoder defined in claim 1 wherein the ordering and modeling mechanism comprises a context model using contexts based on neighboring and parent coefficient values, and further wherein the parent coefficient values are only of S-transform parents.

8. The encoder defined in claim 1 wherein the ordering and modeling mechanism comprises a context model using contexts based on neighboring and parent coefficient values, and further wherein the parent coefficient values are only of TS-transform parents.

9. The encoder defined in claim 1 wherein the ordering and modeling mechanism comprises a context model.

10. The encoder defined in claim 1 wherein the ordering and modeling mechanism encodes a sign bit based in part on a sign of another known coefficient.

11. The encoder defined in claim 1 wherein the ordering and modeling mechanism comprises a context model that uses adaptively changing contexts.

12. The encoder defined in claim 1 wherein the reversible wavelet filter transforms the input data into a plurality of coefficients using Monte Carlo division, wherein a pseudo random generator provides an output determinate of a rounding operation to be performed on the output of the wavelet of the filtering operation.

13. The encoder defined in claim 1 wherein the binary entropy coder comprises a finite state machine coder.

14. The encoder defined in claim 1 wherein the binary entropy coder comprises a high speed parallel coder.

15. The encoder defined in claim 1 wherein the binary entropy coder comprises a Q-coder.

16. The encoder defined in claim 1 wherein the reversible wavelet filter performs a two-dimensional decomposition.

17. The encoder defined in claim 16 wherein reversible wavelet filter comprises a two-dimensional filter having two one-dimensional filters cascaded followed by a two-dimensional rounding mechanism.

18. The encoder defined in claim 1 wherein the ordering and modeling mechanism comprises a context model that codes a single decision if a plurality of head bits are to coded and their north, south, east, and west neighbors and parents all have tail-information 0.

19. The encoder defined in claim 18 wherein the plurality of head bits comprises 16 head bits.

20. The encoder defined in claim 1 wherein the ordering and modeling mechanism comprises a context model that encodes with M-ary centers.

21. The encoder defined in claim 1 wherein coding of coefficients on the lowest level of decomposition is coded using a DPCM scheme.

22. The encoder defined in claim 1 wherein the ordering and modeling mechanism comprises a context model that uses contexts based on whether a non-zero magnitude bit has been observed in a coefficient and the number of bit-planes since said first non-zero magnitude bit, and wherein bits after the first non-zero magnitude bit are not conditioned.

23. The encoder defined in claim 1 wherein the reversible wavelet filter, ordering and modeling mechanism and binary entropy coder perform non-bitplane coding.

24. The encoder defined in claim 1 wherein the ordering and modeling mechanism comprises a look-up table to provide conditioning.

25. The encoder defined in claim 24 wherein the look-up table provides a context based on a parent of a current coefficient, and the coefficients above and below the current coefficient.

26. The encoder defined in claim 25 wherein the parent of the current coefficient comprises only an S-transform parent.

27. The encoder defined in claim 25 wherein the parent of the current coefficient comprises only a TS-transform parent.

28. The encoder defined in claim 25 wherein conditioning on the parent is obtained by ORing with the output of the look-up table handling the handles the other conditioning.

29. The encoder defined in claim 24 wherein the look-up table provides a context based on a previous context, a coefficient above the current coefficient, the location of the current coefficient and a coefficient below the current coefficient.

30. The encoder defined in claim 24 further comprising a second look-up table that obtains state information from the current context look-up table for combination with newly available data for the next bitplane.

31. The encoder defined in claim 1 further comprises a finite amount of work space memory, and further wherein the reversible wavelet filter comprises wavelet transforms of different heights.

32. The encoder defined in claim 1 wherein the reversible wavelet filter comprises overlapped filters.

33. The encoder defined in claim 1 wherein the reversible wavelet filter comprises non-minimal filters.

34. The encoder defined in claim 1 wherein the reversible wavelet filter comprises filters that do not cause growth in the low pass.

35. The encoder defined in claim 1 wherein the reversible wavelet filter comprises non-linear morphological filters.

36. The encoder defined in claim 1 further comprises a memory and coefficients generated by the wavelet transform are stored in a the memory in magnitude/mantissa form.

37. The encoder defined in claim 1 wherein the ordering and modeling mechanism performs M-ary coding.

38. The encoder defined in claim 1 wherein the ordering and modeling mechanism generates an embedded codestream that is embedded by band only.

39. The encoder defined in claim 1 wherein the ordering and modeling mechanism generates a non-embedded codestream.

40. An encoder for encoding input data into a compressed data stream, said entropy coder comprising:

a reversible wavelet filter for transforming the input data into a plurality of coefficients using a pyramidal decomposition with a variable number of levels;

a memory having a fixed size coupled to the reversible wavelet filter, wherein the reversible wavelet filter uses the memory to store information during computation of the plurality of coefficients;

a control mechanism coupled to the reversible wavelet filter and the fixed size memory to select the number of levels based on the fixed size of the memory;

an ordering and modeling mechanism coupled to the reversible wavelet filter and the fixed sized memory, said ordering and modeling mechanism generating an embedded codestream in response to the plurality of coefficients, wherein the ordering and modeling mechanism orders the plurality of coefficients and order binary values within each of the plurality of coefficients; and

a binary entropy coder, coupled to the ordering and modeling mechanism, operable to binary entropy code the embedded codestream to produce the compressed data stream.

41. A method for encoding input data into a compressed data stream comprising the steps of:

transforming the input data into a plurality of coefficients using a reversible wavelet filter;

generating an embedded codestream in response to the plurality of coefficients, including the steps of ordering the plurality of coefficients and order binary values within each of the plurality of coefficients; and

binary entropy coding the embedded codestream to produce the compressed data stream.

42. The method defined in claim 41 further comprising the step of parsing the compressed data stream.

43. The method defined in claim 41 further comprising the step of applying image processing functions to a scaled representation of the compressed data stream.

44. The method defined in claim 43 wherein the image processing functions are only applied to the lowest pass.

45. The method defined in claim 44 further comprising the step of displaying the scaled representation and only applying the image processing functions on displayed pixels.

46. An apparatus for encoding input data into a compressed data stream comprising:

means for transforming the input data into a plurality of coefficients using a reversible wavelet filter;

means for generating an embedded codestream in response to the plurality of coefficients, including means for ordering the plurality of coefficients and ordering binary values within each of the plurality of coefficients; and

means for binary entropy coding the embedded codestream to produce the compressed data stream.

47. The apparatus defined in claim 46 further comprising means for parsing the compressed data stream.

48. The apparatus defined in claim 46 further comprising means for applying image processing functions to a scaled representation of the compressed data stream.

49. The apparatus defined in claim 48 wherein the image processing functions are only applied to the lowest pass.

50. The apparatus defined in claim 49 further comprising means for displaying the scaled representation and only applying the image processing functions on displayed pixels.

51. The apparatus defined in claim 46 wherein the means for ordering uses a series of coefficients surrounding a particular coefficient as a context, and further wherein each of the series of coefficients contributes at least one bit for the context.

52. The apparatus defined in claim 51 wherein a predetermined number of the coefficients provide an extra bit.

53. The apparatus defined in claim 46 wherein the means for ordering comprises a context model using contexts based on neighboring and parent coefficient values, and further wherein the parent coefficient values are only of S-transform parents.

54. The apparatus defined in claim 46 wherein the means for ordering comprises a context model using contexts based on neighboring and parent coefficient values, and further wherein the parent coefficient values are only of TS-transform parents.

55. The apparatus defined in claim 46 wherein the ordering and modeling mechanism encodes a sign bit based in part on a sign of another known coefficient.

56. The apparatus defined in claim 46 wherein the means for ordering comprises a context model that codes a single decision if a plurality of head bits are to coded and their north, south, east, and west neighbors and parents all have tail-information 0.

57. The apparatus defined in claim 46 wherein coding of coefficients on a lowest level of decomposition is coded using a DPCM scheme.

58. The apparatus defined in claim 46 wherein the means for ordering comprises a context model that uses contexts based on whether a non-zero magnitude bit has been observed in a coefficient and a number of bit-planes since said first non-zero magnitude bit, and wherein bits after the first non-zero magnitude bit are not conditioned.

59. The apparatus defined in claim 46 wherein the means for ordering performs M-ary coding.

60. The apparatus defined in claim 46 wherein the means for ordering generates an embedded codestream that is embedded by band only.

61. The apparatus defined in claim 46 wherein the means for ordering generates a non-embedded codestream.

62. A decoder comprising:

a model to each bit of each coefficient of a plurality of ordered coefficients containing ordered binary values;

a binary entropy decoder coupled to the model to decode the plurality of ordered coefficients into a codestream of coefficients based on information from the model; and

an inverse reversible wavelet filter coupled to receive the codestream of coefficients and transform the coefficients into reconstructed data.

63. The decoder defined in claim 62 wherein the inverse reversible wavelet filter applies an inverse filter on the coefficients starting at the highest level of decomposition.

64. The decoder defined in claim 62 wherein the model uses a series of coefficients surrounding a particular coefficient as a context, and further wherein each of the series of coefficients contributes at least one bit for the context.

65. The decoder defined in claim 64 wherein a predetermined number of the coefficients provide an extra bit.

66. The decoder defined in claim 62 wherein the model uses contexts based on neighboring and parent coefficient values, and further wherein the parent coefficient values are only of S-transform parents.

67. The decoder defined in claim 62 wherein the model uses contexts based on neighboring and parent coefficient values, and further wherein the parent coefficient values are only of TS-transform parents.

68. The decoder defined in claim 62 wherein the model and binary entropy coder decode a single decision if a plurality of head bits are to coded and their north, south, east, and west neighbors and parents all have tail-information 0.

69. The decoder defined in claim 62 wherein decoding of coefficients on a lowest level of decomposition is performed using a DPCM scheme.

70. The decoder defined in claim 62 wherein the model uses contexts based on whether a non-zero magnitude bit has been observed in a coefficient and a number of bit-planes since said first non-zero magnitude bit, and wherein bits after the first non-zero magnitude bit are not conditioned.

71. The decoder defined in claim 62 wherein the model and binary entropy coder perform M-ary decoding.

72. A method for decoding compressed data comprising the steps of:

(a) modeling each bit of each coefficient of a plurality of ordered coefficients containing ordered binary values;

(b) binary entropy decoding said each bit, based on information generated as a result of modeling, to generate a codestream of coefficients;

(c) inverse wavelet filtering of coefficients in the codestream from the highest level of decomposition to consecutively lower levels of decomposition.