Image analysis – Image compression or coding – Transform coding
Reexamination Certificate
1999-08-20
2001-02-27
Tran, Phuoc (Department: 2721)
Image analysis
Image compression or coding
Transform coding
C382S244000
Reexamination Certificate
active
06195466
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the field of compression and decompression systems; more particularly, the present invention relates to lossless discrete cosine transform (DCT)-based compression which is reversible.
BACKGROUND OF THE INVENTION
The Discrete Cosine Transform (DCT) is an irrational transform commonly used in lossy image compression. The DCT is commonly used in lossy image compression. It is used in many modes of the JPEG standard and the MPEG standards and future HDTV in the United States. For a discussion on the various standards, see ISO Standard documents ISO/EEC 10918 (JPEG), 11172 (MPEG 1), 13818 (MPEG 2) and William B. Pennebaker and Joan L. Mitchell, “JPEG Still Image Data Compression Standard,” 1993. The basis vectors of DCT have irrational values. Theoretically, integer inputs result in irrational transform coefficients. Therefore, infinite precision is required to perform those transforms exactly. For use in compression, transform coefficients must be rounded to a finite representation.
With most transform implementations, the rounding coefficients to integers does not guarantee that every unique integer input results in a different output. Therefore, the inverse DCT cannot reconstruct the input exactly. The error due to forward and inverse DCT transforms without quantization is referred to as systemic error. This systemic error prevents DCT implementations from being used in lossless compression without retaining a difference or error image.
In practical DCT implementations, the transform basis vectors are also rounded. The difference between a given implementation and the ideal transform (or a high accuracy floating point implementation) is referred to as mismatch. Low mismatch is required for data interchange. There can be a trade-off between the amount of mismatch and speed, cost and other desirable features.
A parameterized transform referred to herein as the Allen Parameterized Transform (APT) is a family of fast transforms which can implement the DCT or rational transforms that are arbitrarily close to the DCT. The APT is also referred to as a generalized Chen transform (GCT) For more information on the APT, see J. Allen, “Generalized Chen Transform: A Fast Transform for Image Compression,”
Journal of Electronic Imaging
, Vol. 3(4), October 1994, pgs. 341-347; J. Allen, “An Approach to Fast Transform Coding in Software,”
Signal Processing: Image Communication
, Vol. 8, pp. 3-11, 1996; and U.S. Pat. No. 5,129,015.
The present invention provides a reversible block based transform, such as, for example, a reversible DCT. The DCT of the present invention may be included in a DCT-based compressor/decompressor that may be used in a lossless compression/decompression system. The present invention also provides DCT transforms with no systemic error and no (or low) mismatch.
SUMMARY OF THE INVENTION
A reversible Discrete Cosine Transform (DCT) is described. The reversible DCT may be part of a compressor in a system. The system may include a decompressor with a reversible inverse DCT for lossless decompression or a legacy decompressor with an inverse DCT for lossy decompression.
In one embodiment, the compressor comprises a DCT compressor having a multiple rotations (e.g., 2 point (2×2) integer rotations), a 4 point parametrized transform, and a subsidiary matrix. The 4 point transform comprises a rotation by B, while the subsidiary matrix comprises a rotation by A and a rotation by C.
The present invention also provides a method for creating a look up table for rounding offsets for use in a reversible DCT.
REFERENCES:
patent: 5129015 (1992-07-01), Allen et al.
patent: 5703799 (1997-12-01), Ohta
patent: 5790441 (1998-08-01), Oami et al.
Schwartz Edward L.
Zandi Ahmad
Blakely , Sokoloff, Taylor & Zafman LLP
Ricoh & Company, Ltd.
Tran Phuoc
LandOfFree
Reversible DCT for lossless-lossy compression does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Reversible DCT for lossless-lossy compression, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reversible DCT for lossless-lossy compression will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2608443