Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
1999-08-06
2002-06-18
Kelley, Chris (Department: 2613)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
C382S251000
Reexamination Certificate
active
06408026
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to image and video data compression and more particularly to a deadzone quantizer.
BACKGROUND OF THE INVENTION
Image data for digital video and still images are often compressed to represent images with less data, thus save storage costs and transmission time and cost. In general, the goal in image data compression is to decrease the data required to represent an image. However, the reduction in data representing an image must be accomplished without substantial penalty in picture quality.
The most effective compression is achieved by approximating the original image, rather than reproducing it exactly. In the motion picture arena, two standards (referred hereinbelow as “MPEG-1” and “MPEG-2”) have been developed by the Motion Picture Experts Group (MPEG) to specify both the coded digital representation of video signal for the storage media, and the method for decoding. In the still image arena, the Joint Photographic Experts Group (JPEG) has set the international standard (referred hereinbelow as “JPEG” and “JPEG 2000”) for color image compression. For MPEG-1, MPEG-2, as well as JPEG and forthcoming JPEG 2000, the greater the compression, the more approximate (“lossy”) the rendition is likely to be.
The above-mentioned compression standards use the image transform. The most common transform is the discrete cosine transform (DCT) which is used in MPEG-1, MPEG-2 and JPEG. Another transform type is wavelet transform which will be adopted by the JPEG 2000 standard. The DCT has certain properties that simplify coding models and make the coding efficient in terms of perceptual quality measures. In general, the DCT is a method of decomposing a block of data into a weighted sum of spatial frequencies. Each of the spatial frequency patterns for a DCT, e.g., an 8×8 DCT, has a corresponding coefficient, in which the amplitude needed to represent the contribution of that spatial frequency pattern in the block of data being analyzed. In other words, each spatial frequency pattern is multiplied by its coefficient and the resulting 64 8×8 amplitude arrays are summed, each pel separately, to reconstruct the 8×8 block. Note that the 8×8 DCT consists an 8 by 8 array of pels. Pel is a contraction for picture or print element used in the displaying/printing industry.
At the heart of the compression is a quantizer. When the DCT is computed for a block of pels, it is desirable to represent the coefficients for high spatial frequencies with less precision. Quantization allows the reduction of accuracy with which the DCT coefficients are represented when converting the DCT coefficient to an integer representation. Quantization is very important in image compression, as it tends to make many coefficients zero, especially those for high spatial frequencies, and thus saves storage space and/or transmission bandwidth.
Conventionally, a DCT coefficient is quantized by dividing it by a nonzero positive number called a quantization step size and rounding the quotient to the nearest integer called a quantization index. By multiplying this integer quantization index with the quantization step size, an approximation of the true DCT coefficient is obtained. This approximation is called the quantized transform coefficient, quantized DCT coefficient, quantization value or reconstruction value. The bigger the quantization step size is, the lower the quantized DCT coefficient precision. The lower precision coefficients can be transmitted to a decoder with fewer bits than higher precision coefficients. The use of large quantization step sizes for high spatial frequencies allows the encoder to selectively discard high spatial frequency activity that the human eye cannot readily perceive.
FIGS. 1A-1D
(prior art) illustrate quantization and dequantization.
FIG. 1A
shows unquantized DCT coefficients
100
at an interval of one. It is to be noted that the unquantized DCT coefficient is a real number and can be either an integer or a non-integer.
FIG. 1B
shows quantization intervals
102
at an interval of &Dgr;. For example, the interval &Dgr; chosen is 4. Each interval
102
is called a “bin”. The center interval surrounding the value zero “0”, e.g., values −2 and 2, is called the “zero bin”.
FIG. 1C
shows quantized DCT coefficient index
104
after quantization at quantization intervals
102
. Conventionally, the quantized DCT coefficient indices are always integers. In addition, all bins have the same size, except the outer-most bins from a predetermined cutoff value to infinity.
FIG. 1D
shows dequantized DCT coefficient
106
after quantized DCT coefficient is dequantized using quantization intervals
102
.
The quantizer above is known as a uniform quantizer since all bins have the same size. However, because in transform-based image and video coding, the AC coefficients typically have a sharp concentration around zero in their distribution, a different bin size for the zero bin is needed to improve the rate-distortion performance. A quantizer having a different zero bin width than the bin width for all other bins is known as a deadzone quantizer. A deadzone quantizer therefore is characterized by two parameters, the zero bin width and the outer bin width. In many applications, such as coders based on ISO JPEG, ISO MPEG-2and ITU-T H.263, the bin widths are chosen so that the zero bin width is twice the outer bin width, i.e. zero bin width/outer bin width=2. Although this ratio has been empirically verified to give reasonably good performance across a variety of distributions and images, it is often not the optimal ratio for a particular distribution or image.
S. Mallat and F. Falzon, in a paper entitled “Understanding image transform codes,” Proc. SPIE Aerospace Conference, April 1997, disclose a fixed ratio of 1.62 for zero bin width over outer bin width. This ratio is obtained for a large class of distributions, and thus is not optimal for a particular distribution or image that an encoder is currently encoding.
It has seldom been studied what is the optimal choice of the zero bin width and the outer bin width for different distributions and/or different images, and furthermore, how this optimal parameter set can be efficiently computed. LoPresto et al. have studied optimal parameter set in a paper entitled “Wavelet Image Coding Using Rate-Distortion Optimized Backward Adaptive Classification” (Proc. SPIE Visual Communications and Image Processing, Vol. 3024, p.1026, 1997). In this paper, the wavelet coefficient distribution is approximated with a generalized Gaussian distribution. For each of several types of generalized Gaussian distributions, 500 deadzone quantizers are tabled. For a given coefficient, its distribution is fitted with one of the several pre-selected generalized Gaussian distributions. The 500 deadzone quantizers for the selected generalized Gaussian distribution are then compared by using the Lagrange multiplier method to choose one of the 500 deadzone quantizers. This method requires a multiple of 500 comparisons before the final selection is made. Thus, this method is computationally expensive. More importantly, since only several typical generalized Gaussian distributions are used to fit the actual distribution, the resulting deadzone quantizer is not an optimal one. Therefore, although this technique tunes more specifically to a particular distribution or image than the previous methods of using fixed ratios, e.g., 2 or 1.62, this technique does not solve the general problem of finding the optimal solution for a particular distribution or image.
Without an analytical framework, that is, without the understanding of the relationships among the number of bits required to approximate an image (bit rate), the approximation accuracy (distortion) and the two parameters of a deadzone quantizer, an optimal deadzone quantizer may be found with an exhaustive (brute-force) numerical search which is the only known method to date. For example, if only the distribution is known, various zero bin widths and outer bi
Heid David W.
Kelley Chris
Philippe Gims
Skjerven Morrill & MacPherson LLP
Sony Corporation
LandOfFree
Deadzone quantization method and apparatus for image... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Deadzone quantization method and apparatus for image..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Deadzone quantization method and apparatus for image... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2895124