Method and apparatus for compression using reversible wavelet transforms and an embedded codestream

• US 6,195,465 B1
• Filed: 06/30/1995
• Issued: 02/27/2001
• Est. Priority Date: 09/21/1994
• Status: Expired due to Fees

• 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): Tran, Phuoc
• Application Number:
  US08/498,695
• Time in Patent Office: 2,069 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/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/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/196 being specially adapted for the computation of encoding parameters, e.g. by averaging previously computed encoding parameters processing of motion vectors H04N19/513
• 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 entropy coder comprising:

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

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 mechanism orders the plurality of coefficients and orders binary values within the plurality of coefficients in order to create the embedded codestream; and

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

2. The encoder defined in claim 1 wherein the reversible wavelet filter, the ordering and modeling mechanism and the entropy coder operate in a casual relationship to compress the input data in one pass.

3. The encoder defined in claim 1 wherein the reversible wavelet filter comprises at least one S-transform.

4. The encoder defined in claim 1 wherein the reversible wavelet filter comprises at least one TS-transform.

5. The encoder defined in claim 1 wherein different transforms are applied vertically and horizontally on the input data.

6. The encoder defined in claim 1 wherein the reversible wavelet filter applies TS-transforms on horizontal passes and at least one S-transform and at least one TS-transform on vertical passes.

7. The encoder defined in claim 1 wherein the reversible wavelet filter generates the plurality of coefficients by applying one-dimensional (1-D) filters separately along rows and columns of the input data.

8. The encoder defined in claim 1 wherein the reversible wavelet filter performs a pyramidal decomposition.

9. The encoder defined in claim 1 wherein binary values within each of the plurality of coefficients are embedded ordered.

10. The encoder defined in claim 9 wherein binary values within each of the plurality of coefficients are ordered according to bit significance.

11. The encoder defined in claim 1 wherein the plurality of coefficients are aligned with respect to each other prior to bit-plane encoding allows for quantization.

12. The encoder defined in claim 11 wherein less heavily quantized coefficients are aligned toward earlier bit-planes.

13. The encoder defined in claim 1 wherein a sign bit is encoded with the first non-zero magnitude bit.

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

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

16. The encoder defined in claim 14 wherein the entropy coder comprises a QM-coder.

17. The encoder defined in claim 14 wherein the entropy coder comprises a finite state machine coder.

18. The encoder defined in claim 14 wherein the entropy coder comprises a parallel coder.

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

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

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 mechanism models bits within a coding unit based on spatial and spectral dependencies of coefficients; and

an entropy coder, coupled to the ordering and modeling mechanism, operable to entropy code the embedded codestream to produce the compressed data stream, wherein the entropy coder performs coding based on the bits modeled by the ordering and modeling mechanism.

20. The encoder defined in claim 19 wherein the ordering and modeling mechanism models bits with contexts based on neighboring and parent coefficients.

21. The encoder defined in claim 20 wherein the contexts are causal.

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

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

and ordering and modeling mechanism coupled to the reversible wavelet filter, said ordering and modeling mechanism performing embedded quantization on the plurality of coefficients to generate an embedded codestream in response to the plurality of coefficients, wherein the ordering and modeling mechanism comprises a context model using contexts based on neighboring and parent coefficient values, and wherein the contexts are based on whether a first non-zero magnitude bit has been observed and the number of bit-planes since said first non-zero magnitude bit, if said first non-zero magnitude bit was observed; and

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

23. The encoder defined in claim 22 wherein the reversible wavelet filter performs a plurality of levels of separable pyramidal decompositions with horizontal and vertical transforms applied alternatively, and further wherein the reversible wavelet filter performs horizontal decomposition using only TS-transforms and performs vertical decomposition using a combination of TS-transforms and S-transforms.

24. The encoder defined in claim 23 wherein the reversible wavelet filter performs the vertical decomposition using two TS-transforms followed by two S-transforms.

25. The encoder defined in claim 22 wherein the ordering and modeling block orders the codestream using a header following by the coding units in order from top to bottom.

26. The encoder defined in claim 25 wherein within each coding unit includes uncoded LL coefficients in raster order followed by entropy coded data one bit-plane at a time.

27. The encoder defined in claim 26 wherein the entropy coded data in each coding unit is ordered from the most significant bit-plane to the least significant bit-plane.

28. The encoder defined in claim 22 wherein the ordering and modeling mechanism performs coefficient alignment.

29. The encoder defined in claim 22 wherein the ordering and modeling mechanism wherein coefficients are coded by bit-significance.

30. The encoder defined in claim 29 wherein coefficients are coded by bit-significance where the first bit-plane is the left most magnitude bit of all of the coefficients.

31. The encoder defined in claim 30 wherein a sign bit for each coefficient is not coded until the highest bit-plane where that coefficient has a non-zero magnitude.

32. The encoder defined in claim 22 wherein the ordering and modeling mechanism orders coefficients within each bit-plane from the low resolution, low frequency level (LL) to the high resolution, high frequency (HH) level.

33. The encoder defined in claim 32 wherein the ordering and modeling mechanism orders coefficients as follows:

4-LL, 4-HL, 4-LH, 4-HH, 3-HL, 3-LH, 3-HH, 2-HL, 2-LH, 2-HH, 1-HL, 1-LH, 1-HH.

34. The encoder defined in claim 33 wherein the ordering and modeling mechanism codes within each subblock in raster scan order.

35. The encoder defined in claim 22 wherein if said first non-zero magnitude bit has not been observed, then the context model uses contexts to condition a coefficient that includes information corresponding to a parent of the coefficient and information from at least on coefficient positioned NW, N, NE, W, E, SW, S or SE of the coefficient.

36. The encoder defined in claim 35 wherein context model uses contexts to condition a coefficient that includes the parent of the coefficient more than one level from the coefficient.

37. The encoder defined in claim 35 wherein if said first non-zero magnitude bit has been observed, then the context model uses contexts that include:

(a) said first non-zero magnitude bit occurred at last bit-plane,

(b) said first non-zero magnitude bit occurred between two and three bit-planes earlier, or

(c) said first non-zero magnitude bit occurred more than three bit-planes earlier.

38. The encoder defined in claim 22 wherein a sign bit of the present coefficient is encoded immediately after the present bit of the present coefficient is the first non-zero magnitude bit.

39. The encoder defined in claim 22 wherein a context for coding a sign bit when the sign of the coefficient immediately north is not known comprises a fixed probability.

40. The encoder defined in claim 39 wherein the fixed probability comprises approximately 0.5.

41. The encoder defined in claim 22 wherein contexts for coding binary values after the first non-zero magnitude bit comprise fixed probabilities.

42. The encoder defined in claim 41 wherein a context for coding a first binary value after the first non-zero bit comprises a fixed probability of approximately 0.7.

43. The encoder defined in claim 22 wherein a context for coding second and third binary values after the first non-zero bit comprises a fixed probability of approximately 0.6.

44. The encoder defined in claim 22 wherein a context for coding fourth and subsequent binary values after the first non-zero bit is coded at a fixed probability of 0.5.

45. The encoder defined in claim 22 wherein the entropy coder comprises a Q-coder.

46. The encoder defined in claim 22 wherein the entropy coder comprises a QM-coder.

47. The encoder defined in claim 22 wherein the entropy coder comprises a finite state machine coder.

48. The encoder defined in claim 22 wherein the entropy coder comprises a parallel coder.

49. The encoder defined in claim 22 wherein if said first non-zero magnitude bit has not been observed, then the context model uses contexts to condition a coefficient that includes information corresponding to a parent of the coefficient.

50. The encoder defined in claim 22 wherein if said first non-zero magnitude bit has not been observed, then the context model uses contexts to condition a coefficient that includes information from at least one coefficient positioned NW, N, NE, W, E, SW, S or SE of the coefficient.

51. A method of encoding input data into a compressed data stream comprising:

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, wherein generating the embedded codestream comprises the steps of ordering the plurality of coefficients and ordering binary values within the plurality of coefficients in order to create the embedded codestream; and

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

52. The method defined in claim 51 wherein transforming, generating and entropy coding are preformed causally.

53. The method defined in claim 51 wherein transforming comprises applying different transforms vertically and horizontally on the input data.

54. The method defined in claim 53 further comprising applying at least one TS-transform to the input data.

55. The method defined in claim 53 further comprising applying at least one S-transform to the input data.

56. The method defined in claim 51 further comprising performing a pyramidal decomposition of a plurality of levels on the input data, including applying horizontal and vertical transforms alternatively using only TS-transforms for horizontal decomposition and using a combination of TS-transforms and S-transforms for vertical decomposition.

57. A method of decoding an encoding data stream comprising:

retrieving coded data for a coding unit;

modeling a bit of each coefficient with a context model and an entropy decoder,

reordering coefficients based on spatial and spectral dependencies of coefficients; and

applying an inverse wavelet filter on the coefficients starting with the coarsest level.

58. The method defined in claim 57 further comprising determining whether all levels have been inverse filtered and, if not, then applying the inverse filter on the coefficients from the next coarsest level.

59. The method defined in claim 58 further comprising repeating the step of determining until all levels have been inverse filtered.

60. A decoder for decoding encoded data comprising:

an entropy decoder for entropy decoding the encoded data into a codestream of coefficients;

a reordering mechansim to reorder coefficients within a coding unit based on spatial and spectral dependencies of coefficients to create a reordered codestream; and

an inverse reversible wavelet filter coupled to the reordering mechanism for transforming the reordered codestream of coefficients into reconstructed data.

61. The decoder defined in claim 60 wherein the entropy decoder decodes the encoded data into an embedded codestream of coefficients.