Compression and decompression with wavelet style and binary style including quantization by device-dependent parser

• US 7,634,145 B2
• Filed: 05/30/2006
• Issued: 12/15/2009
• Est. Priority Date: 09/21/1994
• Status: Expired due to Fees

• Current Assignee: Ricoh Company Limited, Ricoh Corporation (Ricoh Company Limited)
• Original Assignee: Ricoh Company Limited, Ricoh Corporation (Ricoh Company Limited)
• Inventors: Keith, Alexander F., Gormish, Michael J., Schwartz, Edward L., Boliek, Martin, Zandi, Ahmad
• Primary Examiner(s): Tran; Phuoc
• Application Number:
  US11/444,263
• Publication Number:
  US 20060233257A1
• Time in Patent Office: 1,295 Days
• Field of Search: 382/232, 382/233, 382/239, 382/240, 382/244, 382/248, 382/251
• US Class Current: 382/233
• 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/64 : characterised by ordering of coefficients or of bits for transmission
• 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 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 system comprising

a parser in a computer system to parse a codestream to create truncated data, thereby quantizing the codestream, the codestream having compressed data and markers, where the markers that include at least one marker to indicate locations of compressed data within a codestream for parsing;

and

a channel output coupled to the parser to receive the truncated data.

2. The system defined in claim 1 wherein the parser performs parsing without decoding or reencoding the compressed data.

3. The system defined in claim 1 wherein the parser selects compressed data from the codestream to include in the truncated data based on output device characteristics.

4. The system defined in claim 1 wherein the parser receives characteristics of an output device to determine quantization necessary for the output device.

5. The system defined in claim 1 wherein the at least one marker indicates what the compressed data in the codestream is.

6. The system defined in claim 1 wherein the at least one marker is in a tag in the codestream, the parser using the tag to guide in quantizing the codestream.

7. The system defined in claim 1 wherein the parser selects compressed data from the codestrearm based on characteristics of an output device.

8. The system defined in claim 7 wherein the output device is a display.

9. The system defined in claim 7 wherein the output device is a printer.

10. The system defined in claim 9 wherein the printer is a high spatial resolution, low pixel depth printer.

11. The system defined in claim 1 further. comprising a decompressor coupled to receive the truncated data and decompress the truncated data for an output device.

12. The system defined in claim 1 wherein the parser quantizes the codestream to obtain a predetermined level of distortion.

13. The system defined in claim 1 wherein the parser quantizes the codestream by performing scaling.

14. The system defined in claim 1 wherein performing scaling comprises choosing resolution.

15. The system defined in claim 1 wherein the parser quantizes the codestream by performing thresholding.

16. The system defined in claim 1 wherein the parser quantizes the codestream by performing dithering.

17. The system defined in claim 1 wherein the parser quantizes the codestream by discarding bit planes of one or more frequency bands.

18. The system defined in claim 1 wherein the truncated data includes bit planes that lead to a predetermined level of distortion.

19. The system defined in claim 1 wherein the truncated data includes bit planes that lead to a predetermined bit rate.

20. The system defined in claim 1 wherein the parser selects compressed data to allow decomposition of a region of interest.

21. The system defined in claim 1 wherein the truncated data consists of bits necessary to a transition from a preview image in a printer resolution image.

22. The system defined in claim 1 wherein the truncated data consists of bits necessary to a transition from a preview image to a medical monitor image.

23. The system defined in claim 1 wherein the at least one marker is in a tag for each tile.

24. The system defined in claim 1 wherein each tile in the codestream is preceded by a header.

25. The system defined in claim 1 wherein the at least one marker is in a header in the codestream.

26. The system defined in claim 1 wherein the parser modifies tags in the codestream after quantization of parsing.

27. The system defined in claim 26 wherein the parser modifies tags to reflect the truncated data as a new codestream.

28. The system defined in claim 1 wherein the compressed data comprises a lossless compression image.

29. The system defined in claim 1 further comprising a compressor to create the compressed data.

30. A method comprising

receiving, in a memory, a codestream having compressed data and markers, the markers including at least one marker to indicate a location of compressed data within a codestream for parsing;

parsing, using a computer system, compressed data in the codestream using a parser to make truncated data, thereby quantizing the codestream; and

sending, using the computer system, the truncated data to a channel.

31. The method defined in claim 30 wherein parsing the bit stream occurs without decoding or reencoding the compressed data.

32. The method defined in claim 30 wherein parsing the bit stream comprises selecting compressed data from the codestream to include in the truncated data based on output device characteristics.

33. The method defined in claim 30 further comprising:

the parser receiving characteristics of an output device; and

determining quantization necessary for the output device based on the characteristics.

34. The method defined in claim 30 wherein the at least one marker indicates what the compressed data in the codestream is.

35. The system defined in claim 30 wherein the at least one marker is in a tag in the codestream, and further wherein parsing the bit stream comprises using the tag to guide in quantizing the codestream.

36. The method defined in claim 30 wherein parsing the bit stream comprises the parser selecting compressed data from the codestream based on characteristics of an output device.

37. The method defined in claim 36 wherein the output device is a display.

38. The method defined in claim 36 wherein the output device is a printer.

39. The method defined in claim 36 wherein the printer is a high spatial resolution, low pixel depth printer.

40. The method defined in claim 30 wherein parsing the bit stream comprises performing quantization to obtain a predetermined level of distortion.

41. The method defined in claim 30 wherein parsing the bit stream comprises performing scaling.

42. The method defined in claim 30 wherein performing scaling comprises choosing a resolution.

43. The method defined in claim 30 wherein parsing the bit stream comprises performing thresholding.

44. method defined in claim 30 wherein parsing the bit stream comprises performing dithering.

45. The method defined in claim 30 wherein parsing the bit stream comprises discarding bit planes of one or more frequency bands.

46. The method defined in claim 30 wherein the truncated data includes bit planes that lead to a predetermined level of distortion.

47. The method defined in claim 30 wherein the truncated data includes bit planes that lead to a predetermined bit rate.

48. The method defined in claim 30 wherein the parser selects compressed data to allow decomposition of a region of interest.

49. The method defined in claim 30 wherein the truncated data consists of bits necessary to a transition from a preview image to a printer resolution image.

50. The method defined in claim 30 wherein the truncated data consists of bits necessary to a transition from a preview image to a medical monitor image.

51. The method defined in claim 30 wherein the at least one marker is in a tag for each tile.

52. The method defined in claim 30 wherein each tile in the codestream is preceded by a header.

53. The method defined in claim 30 wherein the at least one marker is in a header in the codestream.

54. The method defined in claim 30 further comprising modifying tags in the codestream after quantization of parsing.

55. The method defined in claim 54 wherein modifying tags in the codestream comprises modifying tags to reflect the truncated data as a new codestream.

56. An article of manufacture having one or more computer readable storage media storing instructions thereon which, when executed by a system, cause the system to perform a method comprising:

receiving a codestream having compressed data and markers, the markers including at least one marker to indicate a location of compressed data within a codestream for parsing;

parsing compressed data in the codestream using a parser to make truncated data, thereby quantizing the codestream; and

sending the truncated data to a channel.

57. The article of manufacture defined in claim 56 wherein parsing the bit stream occurs without decoding or reencoding the compressed data.

58. The article of manufacture defined in claim 56 wherein parsing the compressed data comprises selecting compressed data from the codestream to include in the truncated data based on output device characteristics.

59. The article of manufacture defined in claim 56 wherein the method further comprises:

receive characteristics of an output device; and

determine quantization necessary for the output device based on the characteristics.

60. The article of manufacture defined in claim 56 wherein the at least one marker indicates the composition of the compressed data in the codestream.

61. The article of manufacture defined in claim 56 wherein parsing compressed data comprises selecting compressed data from the codestream based on characteristics of an output device.

62. The article of manufacture defined in claim 61 wherein the output device is a display.

63. The article of manufacture defined in claim 61 wherein the output device is a printer.

64. The article of manufacture defined in claim 63 wherein the printer is a high spatial resolution, low pixel depth printer.

65. A system comprising:

a parser to receive a codestream of lossless compressed data and markers;

a channel coupled to the parser;

a decompressor coupled to the channel; and

an output monitor coupled to supply output supply characteristics to the parser to control quantization performed by the parser,

wherein the parser to parse the codestream based on one or more markers in the codestream in order to perform device dependent quantization of the codestream, where the one or more markers include at least one marker to indicate locations of compressed data within the codestream for the parsing.