Image analysis – Image compression or coding – Adaptive coding
Reexamination Certificate
2002-10-03
2004-09-21
Bali, Vikkram (Department: 2621)
Image analysis
Image compression or coding
Adaptive coding
C382S236000
Reexamination Certificate
active
06795584
ABSTRACT:
FIELD OF THE INVENTION
The present invention is generally related to the field of video coding and compression and, more particularly, to a method and system for context-based adaptive variable length coding.
BACKGROUND OF THE INVENTION
A typical video encoder partitions each frame of the original video sequence into contiguous rectangular regions called “blocks”. These blocks are encoded in “intra mode” (I-mode), or in “inter mode” (P-mode). For P-mode, the encoder first searches for a block similar to the one being encoded in a previously transmitted “reference frame”, denoted by F
ref
. Searches are generally restricted to being no more than a certain spatial displacement from the block to be encoded. When the best match, or “prediction”, has been identified, it is expressed in the form of a two-dimensional (2D) motion vector (&Dgr;x, &Dgr;y) where &Dgr;x is the horizontal and &Dgr;y is the vertical displacement. The motion vectors together with the reference frame are used to construct a predicted block F
pred
:
F
pred
(
x,y
)=
F
ref
(
x+&Dgr;x, y+&Dgr;y
)
The location of a pixel within the frame is denoted by (x, y).
For blocks encoded in I-mode, the predicted block is formed using spatial prediction from previously encoded neighboring blocks within the same frame. For both I-mode and P-mode, the prediction error, i.e. the difference between the block being encoded and the predicted block, is represented as a set of weighted basis functions of some discrete transform. Transforms are typically performed on an 8×8 or 4×4 block basis. The weights—transform coefficients—are subsequently quantized. Quantization introduces loss of information, thus quantized coefficients have lower precision than the original ones.
Quantized transform coefficients and motion vectors are examples of “syntax elements”. These, plus some control information, form a complete coded representation of the video sequence. Prior to transmission from the encoder to the decoder, all syntax elements are entropy coded, thereby further reducing the number of bits needed for their representation. Entropy coding is a lossless operation aimed at minimizing the number of bits required to represent transmitted or stored symbols (in our case syntax elements) by utilizing properties of their distribution (some symbols occur more frequently than others).
One method of entropy coding employed by video coders is Variable Length Codes (VLC). A VLC codeword, which is a sequence of bits (0's and 1's), is assigned to each symbol. The VLC is constructed so that the codeword lengths correspond to how frequently the symbol represented by the codeword occurs, e.g. more frequently occurring symbols are represented by shorter VLC codewords. Moreover, the VLC must be constructed so that the codewords are uniquely decodable, i.e., if the decoder receives a valid sequence of bits of a finite length, there must be only one possible sequence of input symbols that, when encoded, would have produced the received sequence of bits.
To correctly decode the bitstream, both encoder and decoder have to use the same set of VLC codewords and the same assignment of symbols to them. As discussed earlier, to maximize the compression, the most frequently occurring symbols should be assigned the shortest VLC codewords. However, the frequency (probability) of different symbols is dependant upon the actual frame being encoded. In the case where a single set of VLC codewords, and a constant assignment of symbols to those codewords is used, it is likely that the probability distribution of symbols within a given frame will differ from the probabilities assumed by the VLC, even though the average symbol probability across the entire sequence may not. Consequently, using a single set of VLC codewords and a single assignment of symbols to those codewords reduces coding efficiency.
To rectify this problem different methods of adaptation are used. One approach, which offers reasonable computational complexity, and a good compression versus efficiency trade-off, and which is currently used in the state-of-the art video coders, is now described. For a set of symbols, a number of tables specifying VLC codewords (VLCs) are provided for the encoder and the decoder to use. The table selected to encode a particular symbol then depends on the information known both to the encoder and decoder, such as the type of the coded block (I- or P-type block), the component (luma or chroma) being coded, or the quantization parameter (QP) value. The performance depends on how well the parameters used to switch between the VLCs characterize the symbol statistics.
In the decoder, the block in the current frame is obtained by first constructing its prediction in the same manner as in the encoder, and by adding to the prediction the compressed prediction error. The compressed prediction error is found by weighting the transform basis functions using the quantized coefficients. The difference between the reconstructed frame and the original frame is called reconstruction error.
The compression ratio, i.e. the ratio of the number of bits used to represent original sequence and the compressed one, may be controlled by adjusting the value of the quantization parameter (QP) used when quantizing transform coefficients. The compression ratio also depends on the method of entropy coding employed.
Coefficients in a given block are ordered (scanned) using zigzag scanning, resulting in a one-dimensional ordered coefficient vector. An exemplary zigzag scan for a 4×4 block is shown in FIG.
1
.
Zigzag scanning presumes that, after applying 2 dimensional (2D) transform, the transform coefficients having most energy (i.e. higher value coefficients) correspond to low frequency transform functions and are located toward the top-left of the block as it is depicted in FIG.
1
. Thus, in a coefficient vector produced through zigzag scanning, the higher magnitude coefficients are most likely to appear toward the start of the vector. After quantization most of the low energy coefficients become equal to 0.
The vector of coefficients can be further processed so that each nonzero coefficient is represented by 2 values: a run (the number of consecutive zero coefficients proceeding a nonzero value in the vector), and a level (the coefficient's value).
CAVLC (Context-based Adaptive VLC) is the method of coding transform coefficients used in the JVT coder “Joint Final Committee Draft (JFCD) of Joint Video Specification (ITU-T Rec. H.264 | ISO/IEC 14496-10 AVC”. In summary, encoding a single 4×4 block using CAVLC involves five steps:
1. Encoding the total number of nonzero coefficients in the block, combined with the number of “trailing ones”.
The number of trailing ones is defined as the number of coefficients with a magnitude of one that are encountered before a coefficient with magnitude greater than one is encountered when the coefficient vector is read in reverse order (i.e. 15, 14, 13, 12, 11, . . . in FIG.
1
). The VLC used to code this information is based upon a predicted number of nonzero coefficients, where the prediction is based on the number of nonzero coefficients in previously encoded neighboring blocks (upper and left blocks).
2. Encoding the sign of any trailing ones.
3. Encoding the levels (magnitudes) of nonzero coefficients other than the trailing ones.
4. Encoding the number of zero values in the coefficient vector before the last nonzero coefficient, i.e. the sum of all the “runs”. The VLC used when coding this value depends upon the total number of nonzero coefficients in the block, since there is some relationship between these two values.
5. Encoding the run that occurs before each nonzero coefficient, starting from the last nonzero value in the coefficient vector.
The VLC used to encode a run value is selected based upon the sum of the runs from step (4), and the sum of the runs coded so far. For example, if a block has a “sum of runs” of 8, and the first run encoded is 6, then all remaining runs must be 0, 1, or 2. B
Karczewicz Marta
Ridge Justin
Bali Vikkram
Nokia Corporation
Ware Fressola Van Der Sluys & Adolphson
LandOfFree
Context-based adaptive variable length coding for adaptive... 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-based adaptive variable length coding for adaptive..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Context-based adaptive variable length coding for adaptive... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3205621