Coded data generation or conversion – Digital code to digital code converters – To or from variable length codes
Reexamination Certificate
2002-11-22
2003-11-11
Young, Brian (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
To or from variable length codes
C382S246000, 37
Reexamination Certificate
active
06646578
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a system and method for context adaptive entropy decoding of transform coefficients in compressed video images.
2. Description of the Prior Art
There is an increasing reliance on video data in rich media applications running on devices or systems such as personal computers, wireless devices, surveillance systems, video conferencing system and set-top boxes. Video data compression system play a key role in increasing the efficiency of video data transmission. Video data is compressed or coded for transmission by taking advantage of the spatial redundancies within a given frame and the temporal redundancies between successive frames. Intraframe compression operates on single frames independently of other frames to exploit spatial redundancies within the frame, whereas interframe compression exploits both spatial and temporal redundancies.
Video compression systems exploit temporal redundancies using interframe prediction coding. Interframe coding is based on predicting the current source frame using the previously coded frame, and coding only the prediction error between the source frame and the predicted frame. Approximations are done in the prediction process, by assuming the motion is uniform across all pixels of each motion estimation block in each frame. It is noted that intercoding can be done for both uni-directional and bidirectional prediction. Transmission efficiencies are realised in intercoding by transmitting the prediction error, as the amount of information present in the prediction error is generally less than that in the actual pixel values. The resulting prediction residuals from inter coding are processed through a frequency domain transform and a quantizer that sets the values of the transform coefficients to discrete values within a pre-specified range. Further compression of the video information is realized by entropy coding the resulting quantized transform coefficients before transmission or storage of the encoded bit stream. The entropy coder is used to represent the resulting information from the quantizer, the motion vector information, and other encoder information using short code words to code the information with the highest likely probability of occurrence, and long code words to code the information with the least likely probability of occurrence. The general approach to code the information with the highest likely probability of occurrence using short code words and the information with the least likely probability of occurrence using long code words is referred to as Variable Length Coding.
Since the video data is transmitted or stored in the form of a compressed bitstream, a decoder is needed to decode the bitstream to reconstruct the video data. First the decoder performs entropy variable-length-decoding of the quantized coefficients, then performs inverse quantization and inverse transform operations to form the image difference pixel values. Finally the image difference values are added to the image prediction pixel values to form the final reconstructed image pixels values.
As an example of entropy coding and decoding of transform coefficients, consider the case of entropy coding/decoding specified in the H.264 video coding standard. In H.264, entropy decoding of coefficients is done on a 4×4 block basis. As an illustrative example, consider the following 4×4 block of quantized transform coefficients at the encoder.
6
0
0
0
5
−4
0
0
0
3
0
0
0
−1
1
0
The first step in the encoding process for the above 4×4 quantized transform coefficients is to apply a zigzag scan to the above quantized transform coefficient block to produce a sequence of coefficients. The zigzag scan is performed according to the following diagram:
The resulting series of coefficients is then 6, 0, 5, 0, −4, 0, 0, 0, 3, 0, −1, 0, 0, 0, 1, 0. The coefficients are typically grouped into (Run_before, Coefficient_level) pairs where Run_before is the number of consecutive zero coefficients preceding a non-zero coefficients in the resulting zigzag order from low frequency coefficients to high frequency coefficients, and Coefficient_level is the value of the non-zero coefficients. The resulting (Run_before, Coefficient_level) pairs are then (0,6) (1,5), (1,−4), (3,3), (1,−1) and (3,1). In H.264, the Run_before information is separated from the Coefficient_level information and each is placed in a separate sequence. The resulting Run_before and Coefficient_level sequences are then:
Run_before: 6, 5, −4, 3,−1, 1
Coefficient_level: 0, 1, 1, 3, 1, 3
The second step in the coding process is to encode the Run_before information and the Coefficient_level information to produce the bit stream corresponding to the original quantized 4×4 transform coefficient data.
At the decoder side, the step in the entropy decoding process for the coded quantized transform coefficient data is to decode the bitstream generated by the encoder to produce the Run_before information and the Coefficient_level information. For the example discussed above, this first step in the decoding process results in the following two sequences:
Run_before: 6, 5, −4, 3, −1, 1
Coefficient_level: 0, 1, 1, 3, 1, 3
The second step in the decoding process is to use the zigzag scan order described above to recover the 4×4 block of quantized transform coefficients based on the above two sequences.
When the video data is transmitted at medium to high bit rates, the bits used to represent Run_before and Coefficient_levels dominate the compressed bit stream. It is therefore desirable to compress the Run_before and Coefficient_level information in the most efficient way. In a typical variable-length decoding system, each Run_before symbol and Coefficient_level symbol would be associated with a unique variable-length codeword such that frequently-occurring symbols have shorter lengths and rarely-occurring symbols have longer lengths. However, since different types of video content and different bit rates usually lead to different statistics of the 4×4 transform coefficient data, a fixed mapping of Run_before and Coefficient_level symbols and variable legth codewords may not always provide optimal entropy compression. To solve this problem, context-adaptive variable length coding (CAVLC) schemes were developed so that the entropy coding process can adapt to different data statistics and always produce good entropy compression.
One of the known prior art CAVLC methods is described in a document “Committee Draft” by the Joint Video Team (JVT) of ISO/IEC MPEG and ITU-T VCEG. The H.264 standard specifies the use of context-adaptive variable length coding (CAVLC) in order to entropy decode the quantized transform coefficients information. Briefly, the method decodes the Coefficient_levels and Run_before using multiple variable-length decoding tables where a table is selected to decode each symbol based on the context of previously decoded symbols. One important aspect of the method is that the Coefficient_level and Run_before sequences are decoded in backward order, i.e. from coefficients corresponding to high frequencies to coefficients corresponding to low frequencies. For the example described above, the original scan order (from low frequency to high frequency) is given by
Coefficient_level: 6, 5, −4, 3, −1, 1
Run_before: 0, 1, 1, 3, 1, 3
whereas the CAVLC bitstream's order is given by:
Coefficient_level: 1, −1, 3, −4, 5, 6
Run_before: 3, 1, 3, 0, 1, 1
It was observed that the CAVLC ordering of the coefficient values the coefficient_level sequences often results in a number of coefficients at the beginning of the sequence with absolute value equal to 1. Consecutive coefficients starting with the first coefficient in the sequence and with absolute value of 1 are called trailing ones (T
1
s). At most 3 trailing ones could be considered. The presence of the T
1
s in the Coefficient_level sequence
Chari Santosh K.
Drange John R. S.
Nguyen John
UB Video Inc.
Young Brian
LandOfFree
Context adaptive variable length decoding system and method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Context adaptive variable length decoding system and method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Context adaptive variable length decoding system and method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3147399