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

• US 7,167,592 B2
• Filed: 08/22/2002
• Issued: 01/23/2007
• Est. Priority Date: 09/21/1994
• Status: Expired due to Fees

• Current Assignee: Ricoh Company Limited
• Original Assignee: Ricoh Company Limited
• Inventors: Gormish, Michael J., Schwartz, Edward L., Boliek, Martin, Zandi, Ahmad
• Primary Examiner(s): Tran; Phuoc
• Application Number:
  US10/226,962
• Publication Number:
  US 20030118241A1
• Time in Patent Office: 1,615 Days
• Field of Search: 382/240, 382/251, 358/1.16
• US Class Current: 382/240
• 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/34 Scalability techniques involving progressive bit-plane based encoding of the enhancement layer, e.g. fine granular scalability [FGS]
• 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. A memory management system comprising:

a memory to store coded data of an embedded code stream, the coded data being categorized as more significant data and less significant data for access in an embedded casual fashion; and

a memory manager to control storage of the coded data in the memory by discarding a portion of the coded data categorized as less significant data to facilitate storage of the coded data categorized as more significant data.

2. The system defined in claim 1 wherein the memory manager discards the portion of the coded data categorized as less significant data without losing coded data categorized as more significant data.

3. The system defined in claim 1 wherein the memory manager is operable to discard a portion of the coded data characterized as less significant data stored in a first portion of the memory to store a portion of the coded data characterized as more significant data in the first portion of the memory.

4. The system defined in claim 3 wherein the memory manager causes the first portion of the memory storing the portion of the coded data characterized as less significant data stored to be overwritten with the coded data characterized as more significant data.

5. The system defined in claim 1 wherein the memory stores information indicative of memory allocation of the coded data.

6. The system defined in claim 1 wherein the coded data results from application of an embedded causal coder.

7. The system defined in claim 1 wherein the coded data comprises data resulting from application of a series of compression operations that includes application of a wavelet transform on input image data.

8. The system defined in claim 7 wherein the series of compression operations includes coding based on bit planes after application of the wavelet transform.

9. The system defined in claim 8 wherein the series of compression operations includes application of entropy coding subsequent to application of the wavelet transform and coding based on bit planes.

10. The system defined in claim 7 wherein the wavelet transform comprises a reversible wavelet transform.

11. The system defined in claim 1 further comprising one or more pointers to control storage of the coded data in the memory.

12. The system defined in claim 11 wherein the one or more pointers comprise a pointer assigned to each significance category, wherein portions of the coded data identified by a significance category is stored at the memory location addressed by one pointer assigned to the significance category.

13. The system defined in claim 12 wherein the one or more pointers comprise a first pointer to point at a beginning of a page of the memory and a second pointer to point to a next available page of the memory.

14. The system defined in claim 11 wherein the memory manager performs memory reassignment when all pages in the memory are in use and additional coded data categorized as more significant data is to be stored to cause reassignment of memory from use for storing portions of coded data categorized as less significant data to storage for additional coded data categorized as more significant data.

15. The system defined in claim 14 wherein the memory manager prevents storage of additional coded data categorized as less significant data to be stored in the memory.

16. The system defined in claim 14 wherein the memory manager sets one pointer of the one or more pointers to end of the page to cause subsequently coded data categorized as less significant data to be stored starting at the end of the page, the one pointer being decremented to store coded data categorized as more significant data.

17. The system defined in claim 14 wherein the memory manager reassigns any page of the memory assigned to storing coded data categorized as less significant data to use for storing coded data categorized as more significant data.

18. A method for managing memory, the method comprising:

storing coded data of an embedded code stream in a memory, the coded data being categorized as more significant data and less significant data for access in an embedded casual fashion; and

controlling storage of the coded data in the memory by discarding a portion of the coded data categorized as less significant data to facilitate storage of the coded data categorized as more significant data.

19. The method defined in claim 18 wherein discarding the portion of the coded data categorized as less significant data occurs without losing coded data categorized as more significant data.

20. The method defined in claim 18 wherein discarding the portion of the coded data characterized as less significant data stored in a first portion of the memory includes storing a portion of the coded data characterized as more significant data in the first portion of the memory.

21. The method defined in claim 20 further comprising causing the first portion of the memory storing the portion of the coded data characterized as less significant data stored to be overwritten with the coded data characterized as more significant data.

22. The method defined in claim 18 further comprising storing information indicative of memory allocation of the coded data.

23. The method defined in claim 18 wherein the coded data results from application of an embedded causal coder.

24. The method defined in claim 18 wherein the coded data comprises data resulting from application of a series of compression operations that includes application of a wavelet transform on input image data.

25. The method defined in claim 24 wherein the series of compression operations includes coding based on bit planes after application of the wavelet transform.

26. The method defined in claim 25 wherein the series of compression operations includes application of entropy coding subsequent to application of the wavelet transform and coding based on bit planes.

27. The method defined in claim 24 wherein the wavelet transform comprises a reversible wavelet transform.

28. The method defined in claim 18 further comprising using one or more pointers to control storage of the coded data in the memory.

29. The method defined in claim 28 wherein the one or more pointers comprise a pointer assigned to each significance category, wherein portions of the coded data identified by a significance category is stored at the memory location addressed by one pointer assigned to the significance category.

30. The method defined in claim 29 wherein the one or more pointers comprise a first pointer to point at a beginning of a page of the memory and a second pointer to point to a next available page of the memory.

31. The method defined in claim 28 further comprising performing memory reassignment when all pages in the memory are in use and additional coded data categorized as more significant data is to be stored to cause reassignment of memory from use for storing portions of coded data categorized as less significant data to storage for additional coded data categorized as more significant data.

32. The method defined in claim 31 further comprising preventing storage of additional coded data categorized as less significant data to be stored in the memory.

33. The method defined in claim 31 further comprising setting one pointer of the one or more pointers to end of the page to cause subsequently coded data categorized as less significant data to be stored starting at the end of the page, the one pointer being decremented to store coded data categorized as more significant data.

34. The method defined in claim 29 further comprising reassigning any page of the memory assigned to storing coded data categorized as less significant data to use for storing coded data categorized as more significant data.