Image analysis – Image compression or coding – Predictive coding
Reexamination Certificate
2000-10-23
2004-07-06
Chen, Wenpeng (Department: 2624)
Image analysis
Image compression or coding
Predictive coding
C382S248000, C382S251000
Reexamination Certificate
active
06760479
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to image compression in general and, more particularly, to an improved predictive-transform method and apparatus for use in image compression.
BACKGROUND OF THE INVENTION
There are many image compression methods and devices known in the art. Some known prior art compression methods are based on coding schemes which decompose images into blocks. Such known methods may use uncorrelated coefficients or coefficient errors, for example Discrete Cosine Transform (DCT). However, these schemes are currently not considered to be the most efficient compression schemes. Further, at high compression ratios, methods using image block decomposition tend to produce artifacts, the most prominent of which are “blocking” artifacts where a pattern of the image blocks may be visible in the image reproduced after decompression. Known image compression standards using such schemes include JPEG and MPEG.
Said and Pearlman wavelet coding, also known as S&P wavelet coding, is presently considered to be the most efficient image compression technique available and is commercially used for image compression applications in both private industry and government institutions. Said and Pearlman wavelet coding is described in Said and Pearlman, “A new fast and efficient image coder based on set partitioning in hierarchical trees, ” IEEE Trans. CSVT, vol. 6, n. 3, pp 243-250, June 1996. An algorithm used in this technique method is available from the Rensselaer Polytechnic Institute, Troy, N.Y.
Notwithstanding a superior efficiency over other known image compression methods, the S&P wavelet algorithm suffers excessive smoothing when operating at low bit rates. This excessive smoothing manifests itself in blurred images.
In Feria, E. H., “Predictive-Transform Coding,”, Proceedings of 1986 IEEE NAECON, Dayton, Ohio, May 1986, the present inventor describes a lossy compression scheme characterized by an uncorrelated coefficient error superstructure.
SUMMARY OF THE INVENTION
A fundamental problem addressed by the present invention is the combined lossy lossless compression of digital signals and images for efficient storage of the images and/or their transmission in bandwidth limited channels. The compressed images can be monochrome or color images and can be used for the compression of still and moving pictures. There are potential applications for the method and apparatus of the present invention in diverse fields, including but not limited to efficient storage of images for personal computers, storage of medical images, storage of finger prints and ballistic or bullet prints, storage of planetary images, transmission of facsimile information for commercial applications, transmission and storage of digital images in the movie industry and other industries, and transmission of digital images for high definition television (HDTV) systems.
The present invention successfully overcomes the excessive smoothing problem associated with the S&P wavelet algorithm. This is achieved by integration of several novel ideas into a method which is hereinafter referred to as Super Predictive-Transform (PT) Coding.
The application of lossless compression in accordance with an embodiment of the present invention to using either q distinct Huffman type coders or an Arithmetic coder that must be reinitialized after each new group of quantizer symbols is received. This approach has led to a significant improvement in the compression derived from the Super Predictive-Transform Coder. The present invention can be successfully applied to other coding algorithms such as those used for JPEG and MPEG or to any other coding scheme where uncorrelated coefficients are used.
The superimposed geometry of the coder input and prediction vectors of the Super Predictive-Transform in accordance with the present invention leads to the elimination of undesirable blocking artifacts that are otherwise obtained with PT based coders when operating at very low bit rates.
An aspect of the present invention involves the “integration” of a new symbol stream generator, Huffman or Arithmetic coders with properly synchronized initializations, the superimposed geometry of the coder input and prediction signals, and simple round off scalar quantizers in a minimum mean squared error (MMSE) predictive-transform modeling and coding formulation. The synergistic operation of all of the aforementioned inventions together with a solid theoretical foundation is what has given rise to a simple, elegant, and powerful technique which has proven to outperform the S&P wavelet algorithm.
The Super PT coder of the present invention does not suffer of the smoothing problem encountered with the S&P wavelet algorithm.
The Super PT coder does not suffer of blocking artifacts when operating at very low bit rates. This is due to the superimposition property of each encoded pixel block.
The lossless encoding of each element of a truncated coefficient error in accordance with an embodiment of the present invention, significantly improves the Signal-to-Noise Ratio (SNR) and visual quality of the reconstructed images.
It will be understood by persons skilled in the art, in view of the detailed description below, that the present invention can be implemented by computer software or dedicated hardware or any combination of computer software and hardware, in accordance with specific applications.
REFERENCES:
patent: 5295203 (1994-03-01), Krause et al.
patent: 5933571 (1999-08-01), Bannai et al.
patent: 5966470 (1999-10-01), Miyashita et al.
patent: 6396955 (2002-05-01), Abe
“Predictive-Transform Residual Vector Quantization,” Syed A. Rizvi et al., 1998 Internatiopnal Conference on Image Processing vol. 2, Oct. 4-7, 1998, pp. 584-588.*
“Fixed and Adaptive Predictors for Hybrid Predictive/Transform Coding,” Staffan Ericsson, IEEE Transactions on Communications, vol. COM-33, No. 12, Dec. 1985, pp. 1291-1302.*
Feria and Rizvi, Super Predictive Transform Residual Vector Quantization (with Syed A. Rizvi),Proceedings of 1999 IEEE International Conference on Image Processing,Kobe, Japan, Oct. 24-28, 1999.
Said and Pearlman, A new fast and efficient image codec based on set partitioning in hierarchical trees,IEEE Trans. CSVT, vol. 6, n. 3, pp 243-250, Jun. 1996.
“Super Predictive-Transform Coding”,Proceedings of 1999 DSP World ICSPAT, Orlando, Florida, Nov. 2-4, 1999.
Feria, E.H., “Predictive-Transform Coding,”Proceedings of 1986 IEEE NAECON, Dayton, Ohio, May 1986.
Erlan H. Feria, “Linear predictive transform of monochrome images,”Image and Vision Computing,vol. 5, No. 4, Nov. 1987, pp. 267-278.
Erlan H. Feria, “Analog and Leaky Predictive Transform Image Coding for Noisy Channels: Further Results,”IEEE NAECON, May 1992.
Chen Wenpeng
Darby & Darby
Research Foundation of the City University of New York
LandOfFree
Super predictive-transform coding does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Super predictive-transform coding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Super predictive-transform coding will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3197133