Apparatus for compression using reversible embedded wavelets

• US 6,222,941 B1
• Filed: 08/09/1996
• Issued: 04/24/2001
• Est. Priority Date: 09/21/1994
• Status: Expired due to Term

• Current Assignee: Ricoh Company Limited, Ricoh Corporation (Ricoh Company Limited)
• Original Assignee: Ricoh Company Limited, Ricoh Corporation (Ricoh Company Limited)
• Inventors: Allen, James D., Schwartz, Edward L., Boliek, Martin, Zandi, Ahmad
• Primary Examiner(s): Couso, Jose L.
• Application Number:
  US08/693,649
• Time in Patent Office: 1,719 Days
• Field of Search: 382/232, 382/240, 348/384, 348/397-408, 348/414, 348/417, 348/418, 348/422, 348/437, 348/438, 364/724.05, 364/724.13, 364/724.14, 364/723, 364/724.1, 364/724.011, 364/715.02, 364/725
• US Class Current: 382/232
• 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/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/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/645 : by grouping of coefficients into blocks after the transform
• 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 encoding and decoding data is described. The present invention includes a method and apparatus for generating transformed signals in response to input data. In one embodiment, the transformed signals are generated using a reversible wavelet transform. The present invention also includes a method and apparatus for compressing the transformed signals into data representing a losslessly compressed version of the input data. In one embodiment, the present invention decomposes the input data using a non-minimal length reversible filter. The decomposition may be performed using multiple one-dimension filters.

Claims

1. A forward wavelet transform filter for filtering an input data signal comprising:

a first adder for adding a first pair of samples of the input data signal to generate a first result;

a first divider coupled to receive the first result to divide the first result by a first factor into a second result, wherein the second result is output as a first low-pass coefficient;

a first subtractor coupled to receive and subtract the first low-passed coefficient from the second result to produce a third result;

a second subtractor for subtracting a second pair of samples of the input data signal from each other to produce a fourth result;

a multiplier coupled to receive the fourth result to multiply the fourth result by a second factor to produce a fifth result;

a second adder coupled to receive and add the third result and the fifth result to produce a sixth result;

a second divider coupled to receive the sixth result and divide the sixth result by a third factor to generate a second low-pass coefficient, wherein the first low-pass coefficient and the second low-pass coefficient are output from the filter.

2. The filter defined in claim 1 wherein the multiplier comprises a shifter.

3. The filter defined in claim 1 wherein at least one of the first and second dividers comprises a shifter.

4. An inverse wavelet transform filter for filtering an input data signal comprising:

a first subtractor for subtracting a pair of low-pass coefficients to produce a first result;

a second subtractor for subtracting a shifted version of the first result from a high-pass coefficient to produce a second result;

a first adder for adding the second result to a shifted version of a low-pass coefficient and a least significant bit of the second result to produce a third result;

a third subtractor for subtracting the second result from the shifted version the low-pass coefficient and the least significant bit of the second result to produce a fourth result;

wherein the filter outputs a first sample based on the third result and a second sample based on the fourth result.

5. The filter defined in claim 4 further comprising a first clip mechanism coupled to receive the third result and clip the third result to produce the first sample.

6. The filter defined in claim 4 further comprising a divider coupled to the first result to divide the first number result by a first number to produce the shifted version of the first result.

7. The filter defined in claim 4 further comprising a multiplier coupled to the low-pass coefficient to multiply the low-pass coefficient to generate the shifted version of the low-pass coefficient.

8. The filter defined in claim 4 wherein bits of the first result are wired to an input of the second subtractor so that the first result appears at the input as the shifted version of the first result which represents the first result divided by a first number.

9. The filter defined in claim 8 where the first number comprises 4.

10. The filter defined in claim 4 wherein bits of the low-pass coefficient are wired to an input of the first adder so that the low-pass coefficient appears at the input as the shifted version of the low-pass coefficient which represents the low-pass coefficient multiplied by a first number.

11. The filter defined in claim 10 wherein the first number comprises 2.

12. The filter defined in claim 4 wherein bits of the first result are wired to a first input of the second subtractor so that the first result appears at the first input as the shifted version of the first result which represents the first result divided by a first number;

and

wherein bits of the low-pass coefficient are wired to a second input of the first adder so that the low-power coefficient appears at the second input as the shifted version of the low-pass coefficient which represents the low-pass coefficient multiplied by a first number.

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

a reversible wavelet filter for transforming the input data into a plurality of coefficients, wherein the wavelet filter comprises;

a first adder to add a first pair of samples of the input data signal to generate a first result;

a first output circuit coupled to the first adder to output a first low-pass coefficient that is a shifted version of the first result;

a first subtractor having inputs of a second low-passed coefficient and the first low-pass coefficient, the first subtractor to subtract the second low-passed coefficient from the first low-pass coefficient to produce a second result;

a second subtractor to subtract a second pair of samples of the input data signal from each other to produce a third result;

a second adder coupled to add a shifted version of the third result and the second result to produce a fourth result;

a second output circuit coupled to generate a third low-pass coefficient that is a shifted version of the fourth result, such that the filter outputs comprise the first and third low-pass coefficients; and

an embedded coder coupled to the reversible wavelet filter to perform embedded coding on the plurality of coefficients, such that a bit stream is generated; and

an entropy coder coupled to the embedded coder to perform entropy coding on the bit stream to create coded data.

14. The filter defined in claim 13 further comprising a divider coupled to the first adder and the first output to divide the first result by a first number to generate the shifted version of the first output.

15. The filter defined in claim 13 further comprising a divider coupled to the second adder and the second output to divide the fourth result by a first number to generate the shifted version of the fourth result.

16. The filter defined in claim 13 wherein bits of the first result are wired to a first input of the first subtractor so that the first result appears at the first input as the shifted version of the first result which represents the first result divided by a first number;

wherein bits of the third result are wired to a second input of the second adder so that the third result appears at the second input as the shifted version of the third result which represents the third result divided by a first number; and

wherein bits of the fourth result are wired to the output so that the fourth result appears at the output as the shifted version of the fourth result which represents the fourth result divided by a first number.

17. The filter defined in claim 14 wherein the first number comprises 2.

18. The filter defined in claim 15 wherein the first number comprises 4.

19. The filter defined in claim 13 wherein bits of the first result are wired to an input of the first subtractor so that the first result appears at the input as the shifted version of the first result which represents the first result divided by a first number.

20. The filter defined in claim 19 wherein the first number comprises 2.

21. The filter defined in claim 13 wherein bits of the third result are wired to an input of the second adder so that the third result appears at the input as the shifted version of the third result which represents the third result divided by a first number.

22. The filter defined in claim 21 wherein the first number comprises 4.

23. The filter defined in claim 13 wherein bits of the fourth result are wired to the output so that the fourth result appears at the output as the shifted version of the fourth result which represents the fourth result divided by a first number.

24. The filter defined in claim 23 wherein the first number comprises 2.

25. A forward wavelet transform filter for filtering an input data signal comprising:

a first adder to add a first pair of samples of the input data signal to generate a first result;

a first output circuit coupled to the first adder to output a first low-pass coefficient that is a shifted version of the first result;

a first subtractor having inputs of a second low-pass coefficient and the first low-pass coefficient, the first subtractor to subtract the second low-pass coefficient from the first low-pass coefficient to produce a second result;

a second subtractor to subtract a second pair of samples of the input data signal from each other to produce a third result;

a second adder coupled to add a shifted version of the third result and the second result to produce a fourth result;

a second output circuit coupled to generate a third low-pass coefficient that is a shifted version of the fourth result, such that the filter outputs comprise the first and third low-pass coefficients.

26. The filter defined in claim 25 further comprising a divider coupled to the first adder and the first output to divide the first result by a first number to generate the shifted version of the first result.

27. The filter defined in claim 26 wherein the divider comprises a bit shifter.

28. The filter defined in claim 26 wherein the first number comprises 2.

29. The filter defined in claim 25 further comprising a divider coupled to the second adder and the second output to divide the fourth result by a first number to generate the shifted version of the fourth result.

30. The filter defined in claim 29 wherein the divider comprises a bit shifter.

31. The filter defined in claim 29 wherein the first number comprises 4.

32. The filter defined in claim 25 wherein bits of the first result are wired to an input of the first subtractor so that the first result appears at the input as that the shifted version of the first result which represent the first result divided by a first number.

33. The filter defined in claim 32 wherein the first number comprises 2.

34. The filter defined in claim 25 wherein bits of the third result are wired to an input of the second adder so that the third result appears at the input as the shifted version of the third result which represents the third result divided by a first number.

35. The filter defined in claim 34 wherein the first number comprises 4.

36. The filter defined in claim 25 wherein bits of the fourth result are wired to the output so that the fourth result appears at the output as the shifted version of the fourth result which represents the fourth result divided by a first number.

37. The filter defined in claim 36 wherein the first number comprises 2.

38. The filter defined in claim 25 wherein bits of the first result are wired to a first input of the first subtractor so that the first result appears at the first input as the shifted version of the first result which represents the first result divided by a first number;

wherein bits of the third result are wired to a second input of the second adder so that the third result appears at the second input as the shifted version of the third result which represents the third result divided by a first number; and

wherein bits of the fourth result are wired to the output so that the fourth result appears at the output as the shifted version of the fourth result which represents the fourth result divided by a first number.

39. A wavelet transform filter for filtering an input data signal comprising:

first adder means for adding a first pair of samples of the input data signal to generate a first result;

first output means coupled to the first adder means for outputting a first low-pass coefficient that is a shifted version of the first result;

first subtracting means for subtracting a second low-pass coefficient from the first low-pass coefficient to produce a second result, wherein the second low-pass coefficient is received by the first subtracting means as a feedback;

second subtracting means for subtracting a second pair of samples of the input data signal from each other to produce a third result;

second adder means for adding a shifted version of the third result to the second result to produce a fourth result;

second output means for generating a third low-pass coefficient that is a shifted version of the fourth result, such that the filter outputs comprise the first and third low-pass coefficients.

40. The filter defined in claim 39 wherein the first output means comprises a divider.

41. The filter defined in claim 40 wherein the divider comprises a bit shifter.

42. The filter defined in claim 39 wherein the second output means comprises a divider.

43. The filter defined in claim 42 wherein the divider comprises a bit shifter.

44. A forward wavelet transform filter for filtering an input data signal comprising:

first adding means for adding a first pair of samples of the input data signal to generate a first result;

dividing means for dividing the first result by a first factor into a second result, wherein the second result is output as a first low-pass coefficient;

first subtracting means for subtracting a low-passed coefficient from the second result to produce a third result;

second subtracting means for subtracting a second pair of samples of the input data signal from each other to produce a fourth result;

multiplying means to multiply the third result by a second factor to produce a fifth result;

second adding means for adding the third result and the second result to produce a sixth result; and

second dividing means for dividing the sixth result by a third factor to generate a second low-pass coefficient, wherein the first low-pass coefficient and the second low-pass coefficient are output from the filter.

45. The filter defined in claim 44 wherein the multiplying means comprises a shifter.

46. The filter defined in claim 44 wherein at least one of the first dividing means or the second dividing means comprises a shifter.

47. An inverse wavelet transform filter for filtering an input data signal comprising:

first subtracting means for subtracting a pair of low-pass coefficients to produce a first result;

second subtracting means for subtracting a shifted version of the first result from a high-pass coefficient to produce a second result;

adding means for adding the second result to a shifted version of a low-pass coefficient and a least significant bit of the second result to produce a third result; and

third subtracting means for subtracting the shifted version the low-pass coefficient and the least significant bit of the second result to produce a fourth result, wherein filter outputs a first sample based on the third result and a second sample based on the fourth result.

48. The filter defined in claim 47 further comprising a clipping means for clipping the third result to produce the first sample.

49. The filter defined in claim 47 further comprising a dividing means for dividing the first result by a first number to produce the first input.

50. The filter defined in claim 47 further comprising a multiplying means for multiplying the low-pass coefficient to generate the second input.

51. A decoder for decoding input data into a decompressed data stream, the decoder comprising:

an entropy decoder to perform entropy decoding to generate decoded data;

an embedded decoder coupled to the entropy decoder to generate a plurality of coefficients in response to the decoded data; and

an inverse filter coupled to the embedded decoder to generate the decompressed data stream in response to the plurality of coefficients, the inverse filter comprising

a first subtractor for subtracting a pair of low-pass coefficients to produce a first result;

a second subtractor for subtracting a shifted version of the first result from a high-pass coefficient to produce a second result;

a first adder for adding the second result to a shifted version of a low-pass coefficient and a least significant bit of the second result to produce a third result;

a third subtractor for subtracting the second result from the shifted version of the low-pass coefficient and the least significant bit of the second result to produce a fourth result, wherein filter outputs a first sample based on the third result and a second sample based on the fourth result.

52. The filter defined in claim 51 wherein bits of the first result are wired to an input of the second subtractor so that the first result appears at the input as the shifted version of the first result which represents the first result divided by a first number.

53. The filter defined in claim 52 wherein the first number comprises 4.

54. The filter defined in claim 51 wherein bits of the low-pass coefficient are wired to an input of the first adder so that the low-pass coefficient appears at the input as the shifted version of the low-pass coefficient which represents the low-pass coefficient multiplied by a first number.

55. The filter defined in claim 54 wherein the first number comprises 2.

56. The filter defined in claim 51 wherein bits of the first result are wired to a first input of the second subtractor so that the first result appears at the first input as the shifted version of the first result which represents the first result divided by a first number;

and

wherein bits of the low-pass coefficient are wired to a second input of the first adder so that the low-pass coefficient appears at the second input as the shifted version of the low-pass coefficient which represents the low-pass coefficient multiplied by a first number.

57. The filter defined in claim 51 further comprising a first clip mechanism coupled to receive the third result and clip the third result to produce the first sample.

58. The filter defined in claim 51 further comprising a divider coupled to the first result to divide the first number result by a first number to produce the first input.

59. The filter defined in claim 51 further comprising a multiplier coupled to the low-pass coefficient to multiply the low-pass coefficient to generate the second input.

60. A decoder for decoding input data into a decompressed data stream, the decoder comprising:

an entropy decoder to perform entropy decoding to generate decoded data;

an embedded decoder coupled to the entropy decoder to generate a plurality of coefficients in response to the decoded data; and

an inverse filter coupled to the embedded decoder to generate the decompressed data stream in response to the plurality of coefficients, the inverse filter comprising

a first subtractor for subtracting a pair of low-pass coefficients to produce a first result;

a second subtractor for subtracting a shifted version of the first result from a high-pass coefficient to produce a second result;

a first adder for adding the second result to a shifted version of a low-pass coefficient and a least significant bit of the second result to produce a third result;

a third subtractor for subtracting the second result from the shifted version of the low-pass coefficient and the least significant bit of the second result to produce a fourth result, wherein filter outputs a first sample based on the third result and a second sample based on the fourth result;

wherein bits of the first result are wired to an input of the second subtractor so that the first result appears at the input as the shifted version of the first result which represents the first result divided by a first number;

wherein bits of the low-pass coefficient are wired to an input of the first adder so that the low-pass coefficient appears at the input as the shifted version of the low-pass coefficient which represents the low-pass coefficient multiplied by a first number;

wherein bits of the first result are wired to a first input of the second subtractor so that the first result appears at the first input as the shifted version of the first result which represents the first result divided by a first number; and

wherein bits of the low-pass coefficient are wired to a second input of the first adder so that the low-pass coefficient appears at the second input as the shifted version of the low-pass coefficient which represents the low-pass coefficient multiplied by a first number.

61. An inverse wavelet transform filter for filtering an input data signal comprising:

a first subtractor for subtracting a pair of low-pass coefficients to produce a first result;

a second subtractor for subtracting a shifted version of the first result from a high-pass coefficient to produce a second result;

a first adder for adding the second result to a shifted version of a low-pass coefficient and a least significant bit of the second result to produce a third result;

a third subtractor for subtracting the second result from the shifted version of the low-pass coefficient and the least significant bit of the second result to produce a fourth result;

wherein filter outputs a first sample based on the third result and a second sample based on the fourth result;

wherein bits of the first result are wired to an input of the second subtractor so that the first result appears at the input as the shifted version of the first result which represents the first result divided by a first number;

wherein bits of the low-pass coefficient are wired to an input of the first adder so that the low-pass coefficient appears at the input as the shifted version of the low-pass coefficient which represents the low-pass coefficient multiplied by a first number;

wherein bits of the first result are wired to a first input of the second subtractor so that the first result appears at the first input as the shifted version of the first result which represents the first result divided by a first number; and

wherein bits of the low-pass coefficient are wired to a second input of the first adder so that the low-power coefficient appears at the second input as the shifted version of the low-pass coefficient which represents the low-pass coefficient multiplied by a first number.