Image analysis – Image compression or coding – Transform coding
Reexamination Certificate
1999-07-30
2001-04-17
Boudreau, Leo (Department: 2621)
Image analysis
Image compression or coding
Transform coding
C382S232000, C382S278000
Reexamination Certificate
active
06219458
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the field of data compression and decompression systems; particularly, the present invention relates to overlapped transforms which are both reversible and efficient, including filters which may be decomposed such that all parts of an implementation are finite impulse response (FIR).
BACKGROUND OF THE INVENTION
Many different data compression techniques exist in the prior art. Compression techniques can be divided into two broad categories, lossy coding and lossless coding. Lossy coding involves coding that results in the loss of information, such that there is no guarantee of perfect reconstruction of the original data. The goal of lossy compression is that changes to the original data are done in such a way that they are not objectionable or detectable. In lossless compression, all the information is retained and the data is compressed in a manner which allows for perfect reconstruction. Lossless coding methods include dictionary methods of coding (e.g., Lempel-Ziv), run length coding, enumerative coding and entropy coding.
Recent developments in image signal processing continue to focus attention on a need for efficient and accurate forms of data compression coding. Various forms of transform or pyramidal signal processing have been proposed, including multi-resolution pyramidal processing and wavelet pyramidal processing. These forms are also referred to as subband processing and hierarchical processing. Wavelet pyramidal processing of image data is a specific type of multi-resolution pyramidal processing that may use quadrature mirror filters (QMFs) to produce subband decomposition of an original image. Note that other types of non-QNF wavelets exist For more information on wavelet processing, see Antonini, M., et al., “Image Coding Using Wavelet Transform”,
IEEE Transactions on Image Processing
, Vol. 1, No. 2, April 1992; Shapiro, J., “An Embedded Hierarchical Image Coder Using Zerotrees of Wavelet Coefficients”,
Proc. IEEE Data Compression Conference
, pgs. 214-223, 1993.
A wavelet transform which is implemented with integer arithmetic that has exact reconstruction is referred to as reversible transform. Examples of reversible wavelet transforms are shown in the CREW wavelet compression system, such as described in Edward L. Schwartz, Ahmad Zandi, Martin Boliek, “Implementation of Compression with Reversible Embedded Wavelets,” Proc. of SPIE 40th Annual Meeting, vol. 2564, San Diego, Calif., July 1995.
A reversible implementation of the LeGall-Tabatabai 5,3 filters was discovered. See S. Komatsu, K. Sezaki, and Y. Yasuda, “Reversible Sub-band Coding Method of Light/Dark Images”,
Electronic Information Communication Research Dissertation D-
11, vol. J78-D-II, no. 3, pp. 429-436, 1995. This implementation has growth in the size of the low pass (smooth) coefficients, which is undesirable, particularly for applications having multiple pyramidal decompositions. See also K. Irie and R. Kishimoto, “A Study on Perfect Reconstruction Subband Coding”,
IEEE Trans. Circuits Syst
., vol. 1, no. 1, pp. 42-48, 1991, and C. Lu, N. Omar, and Y. Zhang, “A Modified Short-Kernal Filter Pair for Perfect Reconstruction of HDTV Signals”,
IEEE Trans. Circuits Syst
., vol. 3, no. 2, pp. 162-164, 1993.
Said and Pearlman created a number of reversible transforms. They start with the simple S-transform and predict high pass coefficients with other known information to create larger transforms. Although not apparent, Said and Pearlman use a “predictor A” that is essentially the TS-transform. For more information, see A. Said and W. Pearlman, “Reversible Image Compression Via Multiresolution Representation and Predictive Coding”, in
Visual Communications and Image Processing
, vol. 2094, pp. 664-674, SPIE, November 1993.
Overlapped transforms such as wavelet filter pairs are well-known in the art of lossy image compression. For lossy image compression, when the output of a non-overlapped transform is quantized, discontinuities between adjacent transform basis vectors often result in undesirable artifacts. Overlapped transforms do not have these discontinuities, resulting in better lossy compression. However, such transforms are not used in lossless compression because they are either inefficient or not reversible, or both. It is desirable to utilize overlapped transforms in lossless compression systems.
Polyphase decompositions and ladder filters are known in the art. Ladder filters are a cascade of ladder steps, in which each ladder step performs an operation on a two dimensional vector. Prior art ladder filter methods provide a reversible decomposition of overlapped filters. For example, see F. Bruckers & A. van den Enden, “New Networks for Perfect Inversion and Perfect Reconstruction,” IEEE Journal on Selected Areas in Communications, Vol. 10, No. 1 (IEEE 1992). However, the reversible decomposition using ladder filter methods may be infinite impulse response (IIR). IIR decompositions may result in systems that cannot be implemented. Furthermore, IIR decomposition may require the use of intermediate values that grow without bound. The storage and processing of values without bound is clearly impractical. On the other hand, finite impulse response (FIR) implementations require finite storage and processing and, therefore, are practical. Thus, what is needed is a ladder filter decomposition that results in an FIR implementation.
The present invention provides overlapped transforms which are both reversible and efficient so that the transform may be used for both lossy and lossless compression. Furthermore, the present invention also provides filters and methods for decomposing filters such that all parts of an implementation are finite impulse response (FIR). This provides for long reversible, efficient filters.
SUMMARY OF THE INVENTION
A system for compression and/or decompression is described. An apparatus that may be used in the system comprises a wavelet transform and an encoding unit. The wavelet transform has dynamically selectable non-linearities to maintain reversibility. The encoding unit has an input that receives coefficients from the wavelet transform and outputs compressed data.
The present invention also provides an apparatus for transforming an input signal. In one embodiment, the apparatus comprises a separation unit and a set of forward transforms. The separation unit separates the input into even and odd samples. The set of forward transforms are reversible and are coupled in a finite impulse response (FIR) ladder configuration as ladder filter elements. The set of forward reversible transforms have integer inputs and outputs, and the transform is such that it has no redundancy in the least significant bits of the output.
REFERENCES:
patent: 4633386 (1986-12-01), Terepin
patent: 5561616 (1996-10-01), Slavin
patent: 6018753 (2000-01-01), Kovacevic et al.
A. Zandi et al., “CREW: Compression with Reversible Embedded Wavelets”, Proceedings DCC '95 Data Compression Conference, pp. 212-221, Snowbird, UT, Mar. 28-30, 1995 , IEEE Comput. Soc. Press.
Schwartz Edward L.
Zandi Ahmad
Blakely , Sokoloff, Taylor & Zafman LLP
Boudreau Leo
Novik Dmitry A.
Ricoh Co. Ltd.
LandOfFree
Overlapped reversible transforms for unified lossless/lossy... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Overlapped reversible transforms for unified lossless/lossy..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Overlapped reversible transforms for unified lossless/lossy... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2540445