Overlapped reversible transforms for unified lossless/lossy compression

Abstract

Recently, a number of reversible wavelet transforms have been identified which allow for exact reconstruction in integer arithmetic. Different transforms vary in how rounding is performed. The present invention provides a transform, which is linear except for the rounding with non-linear operations in order to create a reversible implementation. Also, the present invention also provides transforms which are decomposed into all finite inpulse response parts.

We claim: 
     
       1. An apparatus comprising: a wavelet transform with dynamically selectable non-linearities to maintain reversibility, wherein the dynamically selectable non-linearities comprise a plurality of offsets; and   an encoding unit having an input coupled to receive coefficients from the wavelet transform and having an output of compressed data.   
     
     
       2. The apparatus defined in claim 1 wherein the wavelet transform comprises a forward transform filter. 
     
     
       3. The apparatus defined in claim 1 wherein the dynamically selectable non-linearities control rounding. 
     
     
       4. The apparatus defined in claim 3 wherein the wavelet transform performs a first rounding scheme when a first of the non-linearities is selected and a second rounding scheme when a second of the non-linearities is selected. 
     
     
       5. An apparatus comprising: a forward transform filter having logic to explicitly control rounding with dynamic selection of an offset; and   an encoding unit coupled to the forward transform filter.   
     
     
       6. A system comprising: a reversible wavelet transform having rounding associated with integer division and dynamically selectable non-linearities to control the rounding, wherein the dynamically selectable non-linearities comprise a plurality of offsets; and   a coding unit coupled to receive coefficients from the reversible wavelet transform and having an output of compressed data.   
     
     
       7. The system defined in claim 6 further comprising: a decoding unit coupled to receive the compressed data; and   an inverse filter of the reversible wavelet transform coupled to receive a plurality of coefficients from the decoding unit.   
     
     
       8. The system defined in claim 7 wherein the inverse wavelet filter comprises a linear filter. 
     
     
       9. The system defined in claim 7 wherein the inverse wavelet filter comprises reversible wavelets. 
     
     
       10. A wavelet transform with an integer arithmetic implementation that allows exact reconstruction of an input signal from outputs of the wavelet transform so as to be reversible by dynamically selecting an offset that controls rounding. 
     
     
       11. The wavelet transform defined in claim 10 wherein the offset changes when rounding is utilized to maintain reversibility of the wavelet transform. 
     
     
       12. The wavelet transform defined in claim 10 wherein the wavelet transform comprises a reversible Two-Six transform. 
     
     
       13. The wavelet transform defined in claim 10 wherein the wavelet transform comprises a reversible Three-Five transform. 
     
     
       14. The wavelet transform defined in claim 10 wherein the wavelet transform comprises a low pass filter and a high pass filter. 
     
     
       15. The wavelet transform defined in claim 14 wherein the offset modifies the integer arithmetic implementation of the high-pass filter. 
     
     
       16. The wavelet transform defined in claim 14 wherein the high-pass filter generates an output using an output of the low-pass filter. 
     
     
       17. The wavelet transform defined in claim 14, wherein the output of the low-pass filter does not grow. 
     
     
       18. The wavelet transform defined in claim 14 wherein the high-pass filter comprises selection logic for providing the offset from a plurality of offset inputs in response to at least one selection control signal. 
     
     
       19. The wavelet transform defined in claim 18 wherein the selection logic comprises a multiplexer. 
     
     
       20. The wavelet transform defined in claim 18 further comprising selection signal generation logic to generate said at least one selection control signal in response to a signal derived from remainders of division operations performed on two different low-pass results. 
     
     
       21. The wavelet transform defined in claim 18 further comprising selection control signal generation logic to generate said at least one control selection signal in response to a first signal derived from remainders of division operations performed on two different low-pass results and a bit of one of the two different low-pass results. 
     
     
       22. A system comprising: a forward wavelet transform that transforms input signals into a first series of coefficients using integer arithmetic, wherein the forward wavelet transform dynamically selects an offset to control rounding; and   a compressor having an input coupled to receive coefficients from the forward wavelet transform and having an output of compressed data.   
     
     
       23. The system defined in claim 22 further comprising: a decompressor to decompress the compressed data into a second series of coefficients; and   a reverse wavelet transform operating on the second series of coefficients to generate an exact reconstructed version of the input signal, such that the forward wavelet transform is reversed.   
     
     
       24. An encoder comprising: a wavelet transform with an integer arithmetic implementation that allows exact reconstruction of an input signal from outputs of the wavelet transform so as to be reversible by dynamically selecting an offset that controls rounding; and   an entropy coder.   
     
     
       25. The encoder defined in claim 24 further comprising a coefficient data ordering and modeling mechanism coupled to the wavelet transform and the entropy coder that order coefficients and models the coefficients for the entropy coder. 
     
     
       26. An apparatus comprising: a wavelet transform means for transforming input data with dynamically selectable non-linearities to maintain reversibility, wherein the dynamically selectable non-linearities comprise a plurality of offsets; and   an encoding means for receiving coefficients from the wavelet transform and generating compressed data.   
     
     
       27. The apparatus defined in claim 26 wherein the wavelet transform means comprises a forward transform filter. 
     
     
       28. The apparatus defined in claim 26 wherein the dynamically selectable non-linearities control rounding. 
     
     
       29. The apparatus defined in claim 28 wherein the wavelet transform means includes means for performing a first rounding scheme when a first of the non-linearities is selected and a second rounding scheme when a second of the non-linearities is selected. 
     
     
       30. An apparatus comprising: a forward transform filter means for explicitly controlling rounding with dynamic selection of an offset; and   an encoding means coupled to the forward transform filter means for encoding information generated by the forward transform filter means.   
     
     
       31. A system comprising: a reversible wavelet transform means having rounding associated with integer division and non-linearities for controlling the rounding; and   a coding means for receiving coefficients from the reversible wavelet transform and generating compressed data.   
     
     
       32. The system defined in claim 31 further comprising: a decoding means for decoding the compressed data; and   an inverse filter means for performing an inverse filter operation on a plurality of coefficients from the decoding means.   
     
     
       33. The system defined in claim 32 wherein the inverse wavelet filter means comprises a linear filter. 
     
     
       34. A system comprising: a forward wavelet transform means for transforming input signals into a first series of coefficients using integer arithmetic, wherein the forward wavelet transform means dynamically selects an offset to control rounding; and   a compression means for receiving coefficients from the forward wavelet transform and generating compressed data.   
     
     
       35. The system defined in claim 34 further comprising: a decompression means for decompressing the compressed data into a second series of coefficients; and   a reverse wavelet transform means operating on the second series of coefficients for generating an exact reconstructed version of the input signal, such that the forward wavelet transform is reversed.   
     
     
       36. An encoder comprising: a wavelet transform means for transforming input data with an integer arithmetic implementation that allows exact reconstruction of an input signal from outputs of the wavelet transform so as to be reversible by dynamically selecting an offset that controls rounding; and   an entropy coder.   
     
     
       37. The encoder defined in claim 36 further comprising a coefficient data ordering and modeling means for ordering coefficients and models the coefficients for the entropy coder. 
     
     
       38. A method comprising; performing a wavelet transform on input data with dynamically selectable non-linearities to maintain reversibility, wherein the dynamically selectable non-linearities comprise a plurality of offset; and   encoding coefficients generated from performing the wavelet transform to create compressed data.   
     
     
       39. The method defined in claim 38 wherein the dynamically selectable non-linearities control rounding. 
     
     
       40. The method defined in claim 38 wherein performing a wavelet transform comprises performing a first rounding scheme when the first of the non-linearities is selected and a second rounding scheme when a second of the non-linearities is selected. 
     
     
       41. The method defined in claim 38 further comprising: decoding the compressed data; and   inverse filtering a plurality of coefficients resulting from decoding the compressed data using a reversible wavelet transform.   
     
     
       42. The method defined in claim 38 wherein performing a wavelet transform comprises selecting an offset to control rounding. 
     
     
       43. The method defined in claim 42 wherein the offset changes when rounding is used less to maintain reversibility of the wavelet transform. 
     
     
       44. The method defined in claim 38 wherein the wavelet transform comprises a reversible Two-Six transform. 
     
     
       45. The method defined in claim 38 wherein the wavelet transform comprises a reversible Three-Five transform. 
     
     
       46. The method defined in claim 38 wherein the wavelet transform comprises a low pass filter and a high pass filter. 
     
     
       47. The method defined in claim 46 wherein the offset modifies the integer arithmetic implementation of the high-pass filter. 
     
     
       48. An article of manufacture having a recordable medium with executable instruction stored thereon which, when executed by a processing device, cause the processing device to: perform a wavelet transform on input data with dynamically selectable nonlinearities to maintain reversibility, wherein the dynamically selectable nonlinearities comprise a plurality of offset; and   encode coefficients generated from performing the wavelet transform to create compressed data.   
     
     
       49. The article defined in claim 48 wherein the dynamically selectable nonlinearities control rounding. 
     
     
       50. The article defined in claim 48 further comprising instructions to cause the processing device to perform a first rounding scheme when the first of the non-linearities is selected and a second rounding scheme when a second of the non-linearities is selected. 
     
     
       51. The article defined in claim 48 further comprising instructions to cause the processing device to: decode the compressed data; and   inverse filter a plurality of coefficients resulting from decoding the compressed data using a reversible wavelet transform.   
     
     
       52. The article defined in claim 48 further comprising instructions to cause the processing device to select an offset to control rounding. 
     
     
       53. The article defined in claim 52 wherein the offset changes when rounding is used less to maintain reversibility of the wavelet transform. 
     
     
       54. The article defined in claim 48 wherein the wavelet transform comprises a reversible Two-Six transform. 
     
     
       55. The article defined in claim 48 wherein the wavelet transform comprises a reversible Three-Five transform. 
     
     
       56. The article defined in claim 48 wherein the wavelet transform comprises a low pass filter and a high pass filter. 
     
     
       57. The article defined in claim 56 wherein the offset modifies the integer arithmetic implementation of the high-pass filter.