Data processing: artificial intelligence – Neural network – Learning task
Reexamination Certificate
2001-06-05
2004-03-09
Patel, Ramesh (Department: 2121)
Data processing: artificial intelligence
Neural network
Learning task
C706S015000, C706S016000
Reexamination Certificate
active
06704718
ABSTRACT:
BACKGROUND OF INVENTION
1. Field of the Invention
The present invention relates in general to data compression and more particularly to a system and method for performing trainable nonlinear prediction of transform coefficients in data compression such that the number of bits required to represent the data at a given signal to noise ratio is decreased.
2. Related Art
Data compression is widely used and vital to the high-speed and efficient exchange and storage of data. One of the goals of data compression is to compress original data as much as possible, transmit or store the compressed data, and then uncompress the compressed data to reconstruct the original data. Moreover, this compression should be performed in such a way that the noise introduced into the data by the compression remains acceptable. Better compression means that, at a given signal to noise ratio, the compressed data are smaller and thus use fewer bits of information to represent the original data. Using fewer bits of information both reduces the time required to transmit the compressed data and the amount of storage space needed to store the compressed data. This can significantly shorten the download time of compressed data (such as from the Internet) and can save precious space on storage media (such as a hard disk). This results in a savings of both time and expense.
Some popular types of data compression techniques use transform coefficients. For example, wavelet-based data compression, which is commonly used in the compression of two-dimensional (2D) images, performs a linear, reversible transformation on the original image data to produce wavelet coefficients. Wavelets are a set of basis functions that capture image information in both time and frequency space. Wavelet-based data compression is generally preferred over other types of transform-coefficient compression because after transformation many wavelet coefficients are close to zero. After quantization to integer values (for transmission or storage) many of these wavelet coefficients become zero. The end result is good compression, because long sequences of zeros can be represented efficiently by, for example, run-length encoding.
In general, wavelet-based data compression is a three-step process involving data transformation, quantization and lossless encoding. More specifically, during the first step of the process the data is transformed. A wavelet transformation is performed using wavelet decomposition on the data to obtain wavelet coefficients. Wavelet decomposition is a linear, invertible mapping of the data from one space to another space. This mapping or transformation yields the wavelet coefficients.
The second step of wavelet-based data compression involves quantizing the wavelet coefficients by dividing by a floating point number called a quantization threshold Q and then taking the integer part of the result. This generates quantized values for the data. During this quantization step, the data is scaled and information may be discarded when the integer part is kept and the fractional part is ignored. For example, if the image being compressed includes detail that the human eye cannot perceive, then this information may be usefully discarded. After this quantization step, for suitable choices of Q, many quantized wavelet coefficients, which were not previously zero, map to zero. The amount of information lost in the quantization step, and therefore the quality of the reconstructed image, can be controlled by varying Q.
The third step of wavelet-based data compression involves using an entropy encoder to encode, without loss, the quantized wavelet coefficients resulting from the quantization procedure. In general, any suitable entropy encoding technique may be used. For example, common entropy encoding techniques in include Huffman, arithmetic and run-length encoding. Each of these encoding techniques is well known to those having ordinary skill in the art.
One problem, however, with current transform-coefficient compression (such as wavelet-based data compression) is that the linear transformation of the data results in less than optimal compression. This is because after the linear transformation there exist residual correlations among the transform coefficients. For example, these residual correlations occur in the transform coefficients corresponding to edges in an original image. The presence of these residual correlations in the transformed data indicates a redundancy in the representation of the original image. If this redundancy is removed, then this could result in improved compression.
Therefore, what is needed is a data compression system and method that improves the compression performance of existing transform coefficient data compression techniques by overcoming the limitations of the linear transformation. What is also needed is a data compression system and method that takes advantage of residual correlations to improve compression performance. Although several other known techniques (such as, for example, arithmetic encoding and zero tree techniques) attempt to take advantage of these residual correlations, what is further needed is a better and more efficient technique for achieving improved data compression.
SUMMARY OF INVENTION
To overcome the limitations in the prior art as described above and other limitations that will become apparent upon reading and understanding the present specification, the present invention includes a system and method for using nonlinear predictors to predict transform coefficients during data compression. Using nonlinear predictors reduces the number of bits required to represent the data being compressed (at a given signal to noise ratio) and therefore improves compression. The present invention overcomes the limitations of linear transformations used in data compression by utilizing, in a new way, the nonlinear dependencies remaining after the linear transformation.
Existing transform coefficients compression techniques perform a linear transformation on the data. After this linear transformation, however, nonlinear dependencies between transform coefficients still remain. The present invention models these nonlinear dependencies by generating a nonlinear function describing the dependencies. Using this nonlinear function, a prediction of the transform coefficients can be made and these predicted transform coefficients can be compared to the original transform coefficients. The predicted transform coefficients are then subtracted from the original transform coefficients to obtain residual coefficients.
Better and more accurate predictions of the transform coefficients allow the variance of the transform coefficients to be reduced. Since the mean of the residuals is zero, reducing the variance of the transform coefficients increases the probability that more transform coefficients will quantize to zero. This in turn increases the lengths of the runs of zeros that are presented to the entropy encoder. Increasing the length of the runs of zeros to be encoded achieves better compression because long strings of zeros can be encoded efficiently.
In general, the nonlinear prediction data compression system of the present invention includes a nonlinear prediction encoder for compressing data and a nonlinear prediction decoder for decompressing the data. The nonlinear prediction encoder of the present invention includes a prediction module that generates predicted transform coefficients. The prediction module includes a trainable nonlinear predictor for generating predicted transform coefficients, a store for storing data used by the predictor in the prediction, and an inverse quantizer for providing unquantized residuals to the prediction module. The trainable nonlinear predictor may include a neural network.
The present invention also includes a method for compressing data using a nonlinear predictor. The method includes a novel training technique that is used to train the nonlinear predictor. This training technique includes an in-loop training technique whereby the nonlinear predictor is tr
Burges Chris J. C.
Malvar Henrique S.
Simard Patrice Y.
Fischer Craig S.
Hirl Joseph P.
Lyon & Harr L.L.P.
Patel Ramesh
LandOfFree
System and method for trainable nonlinear prediction of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for trainable nonlinear prediction of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for trainable nonlinear prediction of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3267056