Image analysis – Image compression or coding – Including details of decompression
Reexamination Certificate
1999-11-05
2003-04-15
Tran, Phuoc (Department: 2621)
Image analysis
Image compression or coding
Including details of decompression
C382S232000, C382S248000
Reexamination Certificate
active
06549666
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the field of data compression and decompression systems; particularly, the present invention relates to a method and apparatus for lossless and lossy encoding and decoding of data in compression/decompression systems.
BACKGROUND OF THE INVENTION
Data compression is an extremely useful tool for storing and transmitting large amounts of data. For example, the time required to transmit an image, such as a facsimile transmission of a document, is reduced drastically when compression is used to decrease the number of bits required to recreate the image.
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.
In lossless compression, input symbols or intensity data are converted to output codewords. The input may include image, audio, one-dimensional (e.g., data changing spatially or temporally), two-dimensional (e.g., data changing in two spatial directions (or one spatial and one temporal dimension)), or multi-dimensional/multi-spectral data. If the compression is successful, the codewords are represented in fewer bits than the number of bits required for the uncoded input symbols (or intensity data). Lossless coding methods include dictionary methods of coding (e.g., Lempel-Ziv), run length encoding, enumerative coding and entropy coding. In lossless image compression, compression is based on predictions or contexts, plus coding. The JBIG standard for facsimile compression (ISO/IEC 11544) and DPCM (differential pulse code modulation—an option in the JPEG standard (ISO/IEC 10918)) for continuous-tone images are examples of lossless compression far images. In lossy compression, input symbols or intensity data are quantized prior to conversion to output codewords. Quantization is intended to preserve relevant characteristics of the data while eliminating unimportant characteristics. Prior to quantization, lossy compression system often use a transform to provide energy compaction. JPEG is an example of a lossy coding method for image data.
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-QMF 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. For information on reversible transforms, see Said, A. and Pearlman, W. “Reversible Image Compression via Multiresolution Representation and Predictive Coding”, Dept. of Electrical, Computer and Systems Engineering, Renssealaer Polytechnic Institute, Troy, N.Y. 1993.
Compression is often very time consuming and memory intensive. It is desirable to perform compression faster and/or with reduced memory when possible. Some applications have never used compression because either the quality could not be assured, the compression rate was not high enough, or the data rate was not controllable. However, the use of compression is desirable to reduce the amount of information to be transferred and/or stored.
Digital copiers, printers, scanners and multifunction machines are greatly enhanced with a frame store. A compressed frame store reduces memory and thus the costs required for a frame store in these products. However, many frame stores are implemented with random access memories (RAMs). RAM is fast but generally expensive. Hard disks may also be used as memories, and are generally considered inexpensive (or less expensive generally than RAM). Therefore, any system manufacturer would find an advantage in producing a lesser expensive system using a hard disk, for purposes such as a frame store, instead of RAM.
One problem with using hard disks for time sensitive applications is that it is difficult to directly access information from a hard disk as fast as the same information could be accessed from a RAM. Also, many hard disks utilize compression when storing information onto the disk to increase the amount of information that may be stored onto the disk. The time necessary to perform the compression may also be a deterrent to using hard disks in time sensitive applications. Both the slow speed inherent in the use of hard disks and the use of compression make utilizing hard disks in time sensitive applications a difficult implementation issue.
The present invention provides for fast lossy/lossless compression. The present invention sets forth system implementations that permit usage of inexpensive hard disk technology instead of expensive RAM. Furthermore, the present invention provides for rate matching to a hard disk and for using compression to match the hard disk to bandwidths of other portions of the system implementation, such as a print engine. The present invention also provides for using RAM where the time to compress and decompress is not much slower than the RAM speed. In this way, the present invention performs rate matching to RAM.
SUMMARY OF THE INVENTION
A method and apparatus for performing compression and/or decompression is described. In one embodiment, the present invention comprises a system having a buffer, a wavelet transform unit, and a coder. The wavelet transform unit has an input coupled to the buffer to perform a wavelet transform on pixels stored therein and to generate coefficients at an output. The coder is coupled to the wavelet transform unit to code the transformed pixels received from the buffer.
REFERENCES:
patent: 5511151 (1996-04-01), Russell et al.
patent: 5638498 (1997-06-01), Tyler et al.
patent: 5809176 (1998-09-01), Yajima
patent: 6020975 (2000-02-01), Chen et al.
patent: 6026198 (2000-02-01), Okada
patent: 2293733 (1996-03-01), None
patent: 2293734 (1996-03-01), None
patent: 2303030 (1997-05-01), None
patent: 2303031 (1997-05-01), None
Blakely , Sokoloff, Taylor & Zafman LLP
Ricoh Company LTD
Tran Phuoc
LandOfFree
Reversible embedded wavelet system implementation 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 embedded wavelet system implementation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reversible embedded wavelet system implementation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3032673