Method for compression using reversible embedded wavelets

• US 7,418,142 B2
• Filed: 09/30/1997
• Issued: 08/26/2008
• Est. Priority Date: 09/20/1994
• Status: Expired due to Fees

• Current Assignee: Ricoh Company Limited
• Original Assignee: Ricoh Company Limited
• Inventors: Schwartz, Edward L., Boliek, Martin, Zandi, Ahmad, Allen, James D.
• Primary Examiner(s): Couso; Yon Jung
• Application Number:
  US08/941,466
• Publication Number:
  US 20020048405A1
• Time in Patent Office: 3,983 Days
• Field of Search: 382/232, 382/240, 382/244, 382/248, 382/246, 382/247, 382/239, 382/201, 382/263, 382/264, 382/260, 348/398, 348/403, 348/408, 348/438, 348/439, 348/404, 348/437, 348/407.1, 348/398.1, 348/403.1, 348/404.1, 348/408.1, 348/437.1, 348/438.1, 364/715.02, 341/107, 341/79, 708/203, 375/240.19, 375/240.18
• 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/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/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/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/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/2383 Channel coding or modulation of digital bit-stream, e.g. QPSK modulation arrangements for detecting or preventing errors in the information received by adapting the channel coding H04L1/0009; analogue front ends or means for connecting modulators, demodulators or transceivers to a transmission line H04L27/0002
• CPC Class Codes: H04N 21/4382 : Demodulation or channel decoding, e.g. QPSK demodulation analog front ends or means for connecting modulators, demodulators or transceivers to a transmission line H04L27/0002
• 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/6379 : directed to encoder , e.g. for requesting a lower encoding rate
• 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 method for encoding input data comprising:

applying an overlapped reversible wavelet transform to the input data to produce a series of coefficients, wherein the overlapped reversible wavelet transform is implemented in integer arithmetic such that, with integer coefficients, integer input data is losslessly recoverable; and

compressing the series of coefficients into data representing a compressed version of the input data, including context modeling bits of each of the series of coefficients based on known coefficients in other frequency bands and neighboring coefficients in the same frequency band.

2. The method defined in claim 1 wherein applying the overlapped reversible wavelet transform comprises applying to the input data a plurality of non-minimal length reversible filters comprised of a plurality of one-dimensional filters.

3. The method defined in claim 1 wherein the input data comprises image data.

4. The method defined in claim 1 wherein compressing comprises performing big significance embedding on the series of coefficients.

5. The method defined in claim 1 further comprising:

decompressing the losslessly compressed version of the input data into transformed signals; and

generating the input data from the transformed signals into a reconstructed version of the input data using an inverse reversible wavelet transform.

19. The method defined in claim 1 wherein the overlapped reversible wavelet transform comprises a Two, Ten transform.

27. The method defined in claim 1 wherein applying an overlapped reversible wavelet transform to the input data comprises applying non-minimal length reversible filters to produce the series of coefficients.

38. The method defined in claim 1 wherein the overlapped reversible wavelet transform is an efficient reversible transform in that it has its determinant is equal to 1.

6. A method for decoding data into original data comprising:

decompressing a compressed version of input data into a plurality of transformed signals, including context modeling bits of the plurality of transformed signals based on known transformed signals in other frequency bands and neighboring transformed signals in the same frequency band; and

generating a reconstructed version of original data from the plurality of transformed signals with an overlapped inverse reversible wavelet transform, wherein the overlapped inverse reversible wavelet transform is implemented in integer arithmetic such that, with integer coefficient, integer reconstructed original data is losslessly recoverable.

20. The method defined in claim 6 wherein the overlapped inverse reversible wavelet transform comprises a Two, Ten transform.

28. The method defined in claim 6 wherein generating a reconstructed version of the original data comprises applying non-minimal length reversible filters to produce the series of coefficients.

39. The method defined in claim 6 wherein the overlapped reversible wavelet transform is an efficient reversible transform in that its determinant is equal to 1.

7. A method for processing input data comprising:

generating a first plurality of transformed signals in response to the input data with a reversible overlapped wavelet transform using a pair of non-minimal length reversible filters, implemented in integer arithmetic such that, with integer signals, integer input data is losslessly recoverable;

compressing the first plurality of transformed signals into data representing a compressed version of the input data, including context modeling the first plurality of transformed signals based on known transformed signals in other frequency bands and neighboring transformed signals in the same frequency band;

decompressing the compresses version of the input data into a second plurality of transformed signals; and

generating the input data from the second plurality of transformed signals into a reconstructed version of the input data with an inverse reversible overlapped wavelet transform using a second pair of non-minimal length reversible filters.

21. The method defined in claim 7 wherein the overlapped reversible wavelet transform comprises a Two, Ten transform.

40. The method defined in claim 7 wherein the overlapped reversible wavelet transform is an efficient reversible transform in that its determinant is equal to 1.

8. A method for encoding input data comprising:

transform encoding the input data into a series of coefficients with an overlapped reversible wavelet transform, wherein the overlapped reversible wavelet transform is implemented in integer arithmetic such that, with integer coefficients, integer input data is losslessly recoverable; and

embedded coding the series of coefficients, including ordering the series of coefficients, performing bit significance embedding on the series of coefficients, wherein a first type of embedded coding is performed on a first portion of the data and a second type of embedded coding is performed on a second portion of data using context modeling based upon known coefficients in other frequency bands and neighboring coefficients in the same frequency band.

9. The method defined in claim 8 wherein the first type of embedded coding comprises tree coding.

10. The method defined in claim 8 wherein embedded coding comprises formatting the series of coefficients into sign-magnitude format.

22. The method defined in claim 8 wherein the overlapped reversible wavelet transform comprises a Two, Ten transform.

29. The method defined in claim 8 wherein transformed coding comprises applying a pair of non-minimal length reversible filters to transform code the input data into the series of coefficients.

41. The method defined in claim 8 wherein the overlapped reversible wavelet transform is an efficient reversible transform in that its determinant is equal to 1.

11. A method for encoding input data comprising:

transforming input data into a series of coefficients with an overlapped reversible wavelet transform, wherein the overlapped reversible wavelet transform is implemented in integer arithmetic such that, with integer coefficients, integer input data is losslessly recoverable;

converting the series of coefficients into sign-magnitude format to produce a series of formatted coefficients;

coding a first portion of the series of coefficients using a first type of embedded coding to produce a first bit stream;

coding a second portion of the series of formatted coefficients using a second type of embedded coding that models data using known coefficients in other frenuency bands and neighboring coefficients in the same frequency to produce a second bit stream; and

coding the first bit stream and second bit stream into a single bit stream.

12. The method in claim 11 further comprising entropy coding the single bit stream.

13. The method defined in claim 11 wherein the first type of coding comprises tree order coding.

14. The method defined in claim 11 wherein the first portion comprises the bits of the series of formatted coefficients that include the most significant bit of each of the series of coefficients and the second portion comprises the bits of the series of formatted coefficients that are not in the first portion.

15. The method defined in claim 11 wherein the single bit stream represents a losslessly compressed version of the input data.

23. The method defined in claim 11 wherein the overlapped reversible wavelet transform comprises a Two, Ten transform.

30. The method defined in claim 11 wherein transformed coding comprises applying a pair of non-minimal length reversible filters to transform code the input data into the series of coefficients.

42. The method defined in claim 11 wherein the overlapped reversible wavelet transform is an efficient reversible transform in that its determinant is equal to 1.

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

a reversible wavelet filter to transform the input into a plurality of coefficients, wherein the reversible wavelet filter is implemented in integer arithmetic such that, with integer coefficients, integer input data is losslessly recoverable;

an embedded coder coupled to the reversible wavelet filter to perform embedded coding on the plurality of coefficients to generate a bit stream, when the embedded coder comprises a context model to model data based on known coefficients in other frequency bands and neighboring coefficients in the same frequency band; and

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

24. The method defined in claim 16 wherein the reversible wavelet filter comprises a Two, Ten transform.

31. The method defined in claim 16 wherein the reversible wavelet filter comprises a pair of non-minimal length reversible filters.

43. The encoder defined in claim 16. wherein the reversible wavelet filter performs an overlapped reversible wavelet transform this is efficient in that its determinant is equal to 1.

17. An encoder for encoding input data comprising:

a transform coder coupled to receive the input data and generate a series of coefficients to represent a decomposition of the input data using an overlapped reversible wavelet transform, wherein the overlapped reversible wavelet transform is implemented in integer arithmetic such that, with integer coefficients, integer input data is losslessly recoverable; and

an embedded coder coupled to receive the series of coefficients and perform bit-significance encoding on the series of coefficients to create coded data, when the embedded coder comprises a context model to model data based on known coefficients in other frequency bands and neighboring coefficients in the same frequency band, the embedded coder producing the coded data as the series of coefficients are received.

18. The encoder defined in claim 17 wherein the transform coder and the embedded coder operate to generate coded data from the input data on a single pass through the data.

25. The method defined in claim 17 wherein the overlapped reversible wavelet transform comprises a pair of non-minimal length reversible filters that operate as a Two, Ten transform filter pair.

32. The method defined in claim 17 wherein the transform coder comprises a pair of non-minimal length reversible filters.

26. A decoder for decoding input data comprising:

a decompressor to decompress a compressed version of input data into a plurality of coefficients using context modeling based on known coefficients in other frequency bands and neighboring coefficients in the same frequency band; and

an overlapped inverse reversible wavelet transform coupled to the decompressor to generate a reconstructed version of original data from the plurality of coefficients, wherein the overlapped inverse reversible wavelet transform is implemented in integer arithmetic such that, with integer coefficients, integer reconstructed original data is losslessly recoverable.

44. The decoder defined in claim 26. wherein the overlapped inverse reversible wavelet transform is an efficient reversible transform in that its determinant is equal to 1.

33. A System comprising:

a reversible Two/Ten wavelet filter, wherein the reversible Two/Ten wavelet filter is implemented in integer arithmetic such that with integer coefficients, an integer signal is losslessly recoverable; and

a coder coupled to the Two/Ten filter to code coefficients generated by the Two/Ten wavelet transform filter.

34. The system defined in claim 33 wherein the coder comprises a context model, and a bit generator coupled to the context model.

35. The system defined in claim 34 wherein the context model models bits of coefficients based on known coefficients in other frequency bands and neighboring coefficients in the same frequency band.

45. The system defined in claim 33 wherein the reversible Two/Ten variable wavelet filter performs an overlapped reversible wavelet transform is an efficient reversible transform in that its determinant is equal to 1.

36. A decoding system comprising:

a decoder to decode compressed data into a series of coefficients; and

an inverse Two/Ten reversible wavelet filter coupled to the decoder, wherein the inverse Two/Ten reversible wavelet transform is implemented in integer arithmetic such that with integer coefficients, integer reconstructed original data is losslessly recoverable.

37. The method defined in claim 36 wherein the decoder comprises a context model to model data based on known coefficients in other frequency bands and neighboring coefficients in the same frequency band.

46. The decoding system defined in claim 36 wherein the overlapped reversible wavelet transform is an efficient reversible transform in that its determinant is equal to 1.