Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
1996-12-20
2002-01-15
Kelley, Chris (Department: 2613)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
Reexamination Certificate
active
06339614
ABSTRACT:
BACKGROUND OF THE INVENTION
The invention relates to the compression of video signals. More particularly, the invention relates to a method and apparatus for quantizing and run length encoding transform coefficients in a video coder.
A number of transform-based video coders utilize a quantization algorithm and a run length encoding algorithm to compress a video signal. In general, quantization refers to reducing the magnitude of transform coefficients, and increasing the number of zero valued transform coefficients. Run length encoding is a technique wherein a series of repetitive data symbols are compressed into a shorter code which indicates the length of a code and the data being repeated.
The purpose of a video coder is to reduce the data required to represent the video signal while maintaining an acceptable viewing quality. Thus, there exists a need in the art for efficient compression techniques to further this purpose. One method of increasing the efficiency of a compression technique is to reduce the number of processing cycles required to implement the technique.
Quantization and run length encoding are two of the more expensive steps in a video coder in terms of the number of processing cycles required to implement these techniques. Increased coding efficiency during these steps of a compression algorithm would free processing cycles the video coder could use to improve video compression. For example, a video coder could use the extra processing cycles to increase the number of encoded frames which would increase the viewing quality of the decompressed video signal, or perform better motion estimation in block motion compensated transform based video coders.
One reason conventional run length encoding and quantization techniques are expensive is that they are susceptible to branch misprediction errors. For example, run length encoding techniques for block motion compensated transform based video coders reduce a serial bit stream to a sequence of a triple of values. Each triple of values comprises a run value representing the number of consecutive values of zero, a coefficient value representing a non-zero value, and a sign for the non-zero coefficient value. Such a run length algorithm could be implemented using the following pseudo-code:
Initialize run length to zero
Traverse coefficients in run order
result=abs(coeff/quantizer)
if result equal to zero then
increment run length
else
write run length
write result
write sign of coeff
initialize run length to zero
end if
end.
It can be appreciated that the above pseudo-code utilizes a conditional IF branching statement to determine whether the algorithm should count the values of zero (increment run length) or write out the non-zero coefficient (result) and current zero value count (run length). To minimize processing cycles, modern central processing units (CPU), such as Intel's Pentium™ and Pentium Pro™ microprocessors, attempt to predict which branch of the branching statement the algorithm is going to select based upon previous branch selections. If the CPU mispredicts which branch is selected, the CPU must utilize extra CPU cycles to correct the misprediction. This is referred to as a branch misprediction penalty. As the branch misprediction penalty increases, coding efficiency decreases. Modern run length encoding techniques as the one described above lead to significant branch misprediction penalties for Pentium™ processors, and even higher penalties for Pentium Pro™ processors. It is estimated that the branch misprediction penalty running conventional run length encoding algorithms on Pentium™ processors is 3 cycles per coefficient, and for Pentium Pro™ processors is 10 cycles per coefficient.
In addition, conventional quantization techniques are expensive since they quantize only one value at a time. This requires a large number of calculations which further decreases coding efficiency.
In view of the foregoing, it can be appreciated that a substantial need exists for quantizing and run length encoding algorithms for improving the coding efficiency for transform based video coders.
SUMMARY OF THE INVENTION
This and other needs are met by a method and apparatus for quantizing and run length encoding video data for transform based coders. The video data is separated into blocks of pixels. The pixel values are transformed to another set of values which can be represented with less data. The transformed values are quantized by generating a quantized magnitude and sign for multiple transformed values at a time, while removing branch misprediction errors during the quantizing process. The quantized values are run length encoded while removing branch misprediction errors during the run length encoding process.
REFERENCES:
patent: 5021891 (1991-06-01), Lee
patent: 5087913 (1992-02-01), Eastman
patent: 5146221 (1992-09-01), Whiting et al.
patent: 5253055 (1993-10-01), Civanlar et al.
patent: 5295077 (1994-03-01), Fukuoka
patent: 5337087 (1994-08-01), Mishima
patent: 5347310 (1994-09-01), Yamada et al.
patent: 5369502 (1994-11-01), Fukudat et al.
patent: 5434684 (1995-07-01), Sugiyama
patent: 5450599 (1995-09-01), Horvath et al.
patent: 5506580 (1996-04-01), Whiting et al.
patent: 5543844 (1996-08-01), Mita et al.
patent: 5553164 (1996-09-01), Itagaki
patent: 5559557 (1996-09-01), Kato
patent: 5606421 (1997-02-01), Suzuki et al.
patent: 5706216 (1998-01-01), Reisch
patent: 5724097 (1998-03-01), Hibi et al.
patent: 5724453 (1998-03-01), Ratnakar et al.
patent: 5732157 (1998-03-01), Osawa
patent: 5734439 (1998-03-01), Mishima et al.
patent: 5751232 (1998-05-01), Inoue et al.
patent: 5786780 (1998-07-01), Park et al.
patent: 5798718 (1998-08-01), Hadady
patent: 5861922 (1999-01-01), Murashita et al.
patent: 5875266 (1999-02-01), Fukuda et al.
patent: 5905813 (1999-05-01), Terane
patent: 5933533 (1999-08-01), Fukuda et al.
patent: 5933538 (1999-08-01), Fukuda et al.
patent: 5832128 (1999-11-01), Suzuki
patent: 5982437 (1999-11-01), Ojazaki et al.
patent: 6055273 (2000-04-01), Isomura
Kenyon & Kenyon
Vo Tung
LandOfFree
Method and apparatus for quantizing and run length encoding... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for quantizing and run length encoding..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for quantizing and run length encoding... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2859817