Image analysis – Image compression or coding – Pyramid – hierarchy – or tree structure
Reexamination Certificate
2000-05-01
2004-06-22
Johnson, Timothy M. (Department: 2625)
Image analysis
Image compression or coding
Pyramid, hierarchy, or tree structure
C382S248000, C382S251000, C382S264000, C382S266000
Reexamination Certificate
active
06754394
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 for 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.
Quantization of wavelet coefficients results in pleasing images because wavelet filters are overlapped. In contrast, quantization of block-based, non-overlapped transform coefficients suffer from artifacts at boundaries that are not pleasing.
Removing blocking artifacts from traditional block-based transforms such as the DCT is difficult for many reasons. The boundary affects every coefficient. Each transform coefficient affects many spatial domain locations. Smoothness in the transform domain involves complex relationships between many coefficients. For example, the class of all 2D linear ramps in the spatial domain does not have a nice DCT representation. It is difficult to combine transform domain smoothness constraints and quantization constraints. Typically, iterative solutions are used, with an enhancement operation (smoothing/de-ringing/edge enhancement) being performed in the spatial domain followed by limiting in the transform domain to keep the enhancement within the quantization error.
Edges are often the cause of artifacts in an image. Edge extraction is well known in the art as a means to identify edges and to remove the edges from an image. The use of gaussians in edge detection has a long history. For instance, see E. Marr and E. Hildreth, “Theory of Edged Section,” Proc. R. SOC. London, Vol. 207, pp. 187-217, 1980; V. T. and Thomaso A. Poggio, “On Edge Detection,” IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 8, pp. 147-63, 1986; L. Basano, D. Caprile, et al., “Edge-Detection Schemes Highly Suitable for Hardware Implementation,” J. Opt. Soc. Am., Vol. 5, pp. 1170-1175, 1988; and S. Mallate and S. Zhong, “Characterization of Signals from Multiscale Edges,” IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 14, pp. 710-732, 1992. However, even though these methods for detecting edges existed in the prior art, there is always a desire to improve the edge detection so that reconstructions can be made with sharp edges without artifacts near the edges.
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.
SUMMARY OF THE INVENTION
A method and apparatus for performing reconstruction is described. The method in the present invention provides for receiving DS and DD coefficients affected by a boundary, reconstructing SD coefficients to be smooth across the boundary, applying a vertical inverse transform individually on each tile, reconstructing D coefficients to be smooth across the boundary, and applying a horizontal inverse transform individually on each tile.
REFERENCES:
patent: 5481308 (1996-01-01), Hartung et al.
patent: 5600373 (1997-02-01), Chui et al.
patent: 5621466 (1997-04-01), Miyane et al.
patent: 5661822 (1997-08-01), Knowles et al.
patent: 406038193 (1994-02-01), None
Chui et al., “Wavelets on a Bounded Interval,” Numerical Methods of Approximation Theory, vol. 9, 1992, 53-75.
Boliek Martin
Gormish Michael J.
Keith Alexander F.
Schwartz Edward L.
Blakely , Sokoloff, Taylor & Zafman LLP
Johnson Timothy M.
Ricoh & Company, Ltd.
LandOfFree
Compression and decompression system with reversible... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Compression and decompression system with reversible..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Compression and decompression system with reversible... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3339393