Compression/decompression using reversible embedded wavelets

• US 5,966,465 A
• Filed: 05/03/1996
• Issued: 10/12/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, Keith, Alexander F.
• Primary Examiner(s): Tran, Phuoc
• Application Number:
  US08/643,268
• Time in Patent Office: 1,257 Days
• Field of Search: 382/232, 382/233, 382/240, 382/248, 382/260, 382/263, 382/264, 382/276
• 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/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/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 comprising:

a memory; and

a forward transform operating on data in the memory, wherein the transform is computed and stored in the memory by storing calculation results in locations containing no longer necessary information such that the forward transform is computed in place in the memory;

wherein the memory comprises;

a plurality of lines of memory; and

a line buffer having a plurality of entries containing pointers to the plurality of lines of memory, wherein each of the plurality of entries are associated with an individual memory lines, wherein the pointers are moved between entries in the line access buffer to resemble scrolling of the memory without moving the data in the memory lines.

2. The encoder defined in claim 1 wherein the forward transform comprises a critically sampled transform.

3. The encoder defined in claim 1 wherein the forward transform comprises a reversible wavelet.

4. The encoder defined in claim 1 wherein an initial calculation causes a detail output to replace a partial product required to derive the detail output.

5. The encoder defined in claim 4 wherein input values are replaced by a smooth output and a partial product.

6. The encoder defined in claim 1 further comprising:

an embedded order quantizer coupled to the forward transform;

a context model coupled to the embedded order quantizer.

7. The encoder defined in claim 6 further comprising an embedded binary style coding mechanism.

8. The encoder defined in claim 7 further comprising:

a binary entropy coder coupled to the context model and the embedded binary style coding mechanism, wherein the forward transform, the embedded order quantizer, and the context model are operable to compress image data using reversible embedded wavelets and the binary style coding mechanism is operable to compress image data using the binary coding scheme; and

selection control coupled to select wavelet or binary style based on whether portions of the image data have characteristics of continuous-tone image data or of binary image data, respectfully.

9. The encoder defined in claim 1 further comprising software to manage the line buffer.

10. The encoder defined in claim 1 wherein the forward transform is applied to only as many lines of the image that are necessary to completely compute a set of wavelets that make up at least one band of wavelet units.

11. The encoder defined in claim 1 further comprising a context model, and an entropy coder.

12. The encoder defined in claim 11 computed sets wavelet coefficients in the memory are modeled, entropy coded and removed from the memory.

13. The encoder defined in claim 1 wherein the forward transform is applied to an entire image while storing in the memory only a band image at a time.

14. The encoder defined in claim 1 wherein the pointers in the line buffer are rearranged to give the appearance that the memory is scrolling.

15. An encoder comprising:

a memory; and

a Two-Six transform operating on data in the memory, wherein the Two-Six transform is computed and stored in the memory by storing calculation results in locations containing no longer necessary information, such that the Two-Six transform is computed in place in the memory.

16. An encoder comprising:

a memory; and

a Two-Ten transform operating on data in the memory, wherein the Two-Ten transform is computed and stored in the memory by storing calculation results in locations containing no longer necessary information, such that the Two-Ten transform is computed in place in the memory.

17. The encoder defined in claim 16 wherein the memory comprises:

a plurality of lines of memory; and

a line buffer having a plurality of entries containing pointers to the plurality of lines of memory, wherein each of the plurality of entries are associated with an individual memory lines, wherein the pointers are moved between entries in the line access buffer to resemble scrolling of the memory without moving the data in the memory lines.

18. The system defined in claim 17 wherein encoded data is transferred out of the memory and the locations are overwritten with new image data, and further wherein the pointers in the line access buffer are moved such that the top line of the previously stored data that remains in the memory appears as the top of the memory.

19. The encoder defined in claim 16 further comprising:

an embedded order quantizer coupled to the forward transform; and

a context model coupled to the embedded order quantizer.

20. The encoder defined in claim 16 further comprising an embedded binary style coding mechanism.

21. The encoder defined in claim 16 further comprising:

a binary entropy coder coupled to the context model and the embedded binary style coding mechanism, wherein the forward transform, the embedded order quantizer, and the context model are operable to compress image data using reversible embedded wavelets and the binary style coding mechanism is operable to compress image data using the binary coding scheme; and

selection control coupled to select wavelet or binary style based on whether portions of the image data have characteristics of continuous-tone image data or of binary image data, respectfully.

22. The encoder defined in claim 16 further comprising software to manage the line buffer.

23. The encoder defined in claim 16 wherein the forward transform is applied to only as many lines of the image that are necessary to completely compute a set of wavelets that make up at least one band of wavelet units.

24. The encoder defined in claim 16 further comprising a context model, and an entropy coder.

25. The encoder defined in claim 16 computed sets wavelet coefficients in the memory are modeled, entropy coded and removed from the memory.

26. The encoder defined in claim 16 wherein the forward transform is applied to an entire image while storing in the memory only a band image at a time.

27. The encoder defined in claim 16 wherein the pointers and the line buffer are rearranged to give the appearance that the memory is scrolling.

28. An encoder comprising:

a buffer comprising a plurality of lines of memory and a line buffer having a plurality of entries containing pointers to the plurality of lines of memory, wherein each of the plurality of entries are associated with an individual memory lines, wherein pointers are moved between entries in the line access buffer to resemble scrolling of the buffer without moving the data in the memory lines;

a forward transform operating on data in the buffer, wherein the forward transform is computed and stored in the buffer by storing calculation results in locations containing no longer necessary information, such that the transform is computed in place in the buffer memory;

an embedded quantizer coupled to the forward transform; and

an entropy coder coupled to the embedded quantizer.

29. The encoder defined in claim 28 wherein the forward transform comprises a Two-Six transform.

30. The encoder defined in claim 28 wherein the forward transform comprises a Two-Ten transform.

31. A method for encoding data comprising:

applying a first one dimensional wavelet transform to each line in a buffer having a plurality of memory lines;

applying a second one dimensional wavelet transform to each column in the buffer;

modeling a set of completely computed wavelet coefficients;

entropy coding the set of completely computed wavelet coefficients;

removing the set of completely computed wavelet coefficients from the buffer after entropy coding;

moving pointers between entries in a line access buffer associated with the buffer to resemble scrolling of the buffer without moving the data in the plurality of memory lines.

32. The method defined in claim 31 wherein the first one dimensional wavelet transform and the second wavelet transform are the same.

33. A decoder comprising:

a buffer memory; and

an inverse transform operating on data in the buffer memory, wherein the inverse transform is computed and stored in the memory by storing calculation results in locations containing no longer necessary information, such that the inverse transform is computed in place in the buffer memory.

34. The decoder defined in claim 33 wherein the inverse transform comprises a critically sampled transform.

35. The decoder defined in claim 33 wherein the inverse transform comprises a reversible wavelet transform.

36. The decoder defined in claim 33 wherein an initial calculation causes a detail output to replace a partial product required to derive the detail output.

37. The decoder defined in claim 36 wherein input values are replaced by a smooth output and a partial product.

38. A decoder comprising:

a buffer memory; and

an Two-Six transform operating on data in the buffer memory, wherein the Two-Six transform is computed and stored in the memory by storing calculation results in locations containing no longer necessary information, such that the Two-Six transform is computed in place in the buffer memory.

39. A decoder comprising:

a buffer memory; and

an Two-Ten transform operating on data in the buffer memory, wherein Two-Ten transform is computed and stored in the memory by storing calculation results in locations containing no longer necessary information, such that the Two-Ten transform is computed in place in the buffer memory.

40. An encoder comprising:

a buffer comprising a plurality of lines of memory and a line buffer having a plurality of entries containing pointers to the plurality of lines of memory, wherein each of the plurality of entries are associated with an individual memory lines;

a reversible wavelet transform coupled to the buffer to receive image data and generate a plurality of coefficients, wherein the buffer stores the plurality of coefficients;

an ordering mechanism coupled to receive coefficients from the buffer for ordering, wherein the ordering mechanism stores ordered coefficients in the buffer; and

a coder coupled to receive ordered coefficients from the buffer and generate encoded data;

wherein pointers are moved between entries in the line access buffer to resemble scrolling of the buffer without moving the data in the memory lines.

41. The system defined in claim 40 wherein the transform comprises an overlapping transform.

42. The system defined in claim 40 wherein encoded data is transferred out of the buffer and the locations are overwritten with new image data, and further wherein the pointers in the line access buffer are moved such that the top line of the previously stored data that remains in the buffer appears as the top of the buffer.

43. A computer software product including a computer readable medium having executable instructions stored therein, which when executed by the processor, causes the processor to:

apply a first one dimensional wavelet transform to each line in a buffer having a plurality of memory lines;

apply a second one dimensional wavelet transform to each column in the buffer;

model a set of completely computed wavelet coefficients;

entropy code the set of completely computed wavelet coefficients;

remove the set of completely computed wavelet coefficients from the buffer after entropy coding;

move pointers between entries in a line access buffer associated with the buffer to resemble scrolling of the buffer without moving the data in the plurality of memory lines.