9.6 Advanced variable length coding

H.263 pays special attention to variable length coding (VLC) for two different reasons. First, since H.263 is a low bit rate codec, it uses any means as well as arithmetic coding as an efficient VLC to enhance the compression efficiency. On the other hand, since H.263 is intended for mobile applications, where the channel error can be very severe and VLC coded data is very prone to the effects of errors, it uses a less compression efficient VLC to localise the side effect of channel errors. These two contradictory requirements are of course for two different applications and both are optional. In the normal mode, H.263 like the other standard video codecs uses the conventional VLC.

9.6.1 Syntax-based arithmetic coding

In the optional arithmetic coding mode of H.263 [25-E], all the corresponding variable length coding/decoding operations may be replaced by binary arithmetic coding/decoding. This mode is used to improve the compression efficiency. It is shown that use of arithmetic coding will improve the compression efficiency over the conventional Huffman coded VLC by approximately 5–10 per cent, depending on the type of data to be coded [10]. However, arithmetic coded data is as prone to channel errors as normal VLC data. Hence, care should be taken to protect data against channel errors.

The type of arithmetic coding is called syntax-based, since a symbol is VLC encoded using a specific table based on the syntax of the coder. This table typically stores lengths and values of the VLC codewords. The symbol is mapped to an entry of the table in a table look-up operation, and then the binary codeword specified by the entry is sent out normally to a buffer for transmitting to the receiver.

In variable length decoding (VLD), the received bit stream is matched entry by entry in a specific table based on the syntax of the coder. This table must be the same as the one used at the encoder for encoding the current symbol. The matched entry in the table is then mapped back to the corresponding symbol that is the end result of the VLD decoder and is then used for recovering the video pictures.

The use of this mode is indicated by the type information, ptype. Details of syntax-based binary arithmetic coding (SAC) were given in Chapter 3. The model for the arithmetic coding of each symbol is specified by the cumulative frequency of that symbol.

9.6.2 Reversible variable length coding

To decode VLC coded data, decoders need to find the beginning of the codeword that starts after the resynchronisation marker. The marker has a unique pattern which is known to the decoder. VLC coded data is decoded one bit at a time, and each time the found bits are compared against a set of codewords in a lookup table. If a valid codeword is found, the symbol is decoded, otherwise another bit from the bit stream is appended to the code and tested again. In the event of any error in the bit stream, either a wrong symbol is decoded or the result declared invalid. In the former, it is more likely that the decoded symbols that follow will all be wrong, and/or eventually an invalid codeword is detected. In the case of an invalid codeword, decoding is halted, and the decoder waits for the next resynchronisation marker to start decoding. Thus a single bit error may cause a large part of the picture, from the occurrence of the error to the next resynchronisation marker, to be corrupted.

One way of reducing the damaged area is to be able to decode the bit stream backward as well as forward. This is called reversible variable length coding (RVLC). The decoder normally decodes in the forward mode, but when an invalid codeword is detected it stops decoding and stores the remaining data, up to the next resynchronisation marker. It then decodes backward from the marker, to find an invalid codeword, as shown in Figure 9.18. The area between the forward and reverse nondecodable part becomes the erroneous part.

Figure 9.18: A reversible VLC

A variable length code able to work in both ways (RVLC) is required to be symmetric and its success very much depends on finding an invalid codeword arising from the error. If this is not found, then there is no way of identifying the erroneous area unless by postprocessing, which will be discussed in section 9.7.4. Fortunately, due to symmetry of RVLC codes, any error will most likely destroy the symmetry and will cause a nonvalid codeword.

9.6.3 Resynchronisation markers

The resynchronisation markers play an important role on the performance of H.263 video codec. If used too often, they limit the damaged area more tightly, so improving the error resilience of the codec. On the other hand, they incur some overheads, which can be costly for low bit rate video. In secure communication environments, they might be used only along with the picture header, where a single bit error can damage the whole picture. In this case, the overhead is minimised and the error-free picture quality is at its best. In normal transmission media, the resynchronisation markers are preferred to be used at each group of blocks (GOB), to give a balance between the compression efficiency (nonerroneous picture quality) and resilience to errors.

For an optimum balance between the resilience and the coding efficiency, the resynchronisation markers may be inserted where they are needed most. For example, if a GOB does not produce enough bits, or if it belongs to a B-picture, then markers may be inserted between several GOBs. Similarly, if a part of a picture is very active, such as the intraframe coded macroblocks, then within a GOB several markers can be inserted.

This optional mode of H.263 is defined under Annex K and is called the slice structure mode [25-K]. In this mode the slice header information within the bit stream acts as the resynchronisation marker. A slice header has more information than a GOB header (e.g. repeating picture header), such that out of order decoding of slices within a picture is possible. This is particularly useful for packetised transmission of H.263 coded data, where out of sequence decoding of packets reduces the decoding delay. Note that there is no complete independence between the slices, since some processing tools like deblocking filter mode interrelate adjacent slices [25-J].

In order to ensure that slice boundary locations can act as resynchronisation points, and ensure that slices can be sent out of order without causing additional decoding delays, the following rules are adopted in the slice structure mode:

The prediction of motion values is the same as if a GOB header was present (see section 9.1.2), preventing the use of motion vectors of blocks outside the current slice for the prediction of the values of motion vectors within the slice.
The advanced intra coding mode [25-I] treats the slice boundary as if it was a picture boundary with respect to the prediction of intra block DCT coefficient values.
The assignment of remote motion vectors for use in overlapped block motion compensation within the advanced prediction mode [25-F] also prevents the use of motion vectors of blocks outside of the current slice for use as remote motion vectors.

For complete independence between slices, the recommendation describes the optional independent segment decoding mode [25-R]. When this mode is used, the slice boundaries are treated like the picture boundaries, including the treatment of motion vectors which cross these boundaries. If need be, the boundary pixels are extrapolated to be able to use other optional modes such as: unrestricted motion vector, advanced prediction mode, deblocking filter and scalability [25-R].

9.6.4 Advanced intra/inter VLC

For further improvement to compression efficiency, H.263 specifies some optional modes that can use the normal Huffman designed VLC codes differently from the other standard video codecs. The following two optional modes describe situations where proper use of VLC improves the encoding efficiency.

9.6.4.1 Advanced intra coding

In this optional mode [25-I], intra blocks are predictively coded using nearby blocks in the image to predict values in each intra block. A separate VLC is used for the intra VLC coefficients, and also the quantisation of the DC coefficient for intra is different. This is all done to improve the coding efficiency of the intra macroblocks.

The prediction may be made from the block above or the block to the left of the current block being decoded. An exception occurs in the special case of an isolated intra coded macroblock in an inter coded frame with neither the macroblock above nor to the left being intra coded. In this case, no prediction is made. In prediction, DC coefficients are always predicted in some manner, although either the first row or column of AC coefficients may or may not be predicted as signalled on a macroblock-by-macroblock basis. Inverse quantisation of the intra DC coefficient is identical to the inverse quantisation of AC coefficients for predicted blocks, unlike the core H.263 or other standards that use a fixed quantiser of eight bits for intra DC coefficients.

Also, in addition to zigzag scanning, two more scans are employed, alternate horizontal and alternate vertical scans, as shown in Figure 9.19. Alternate vertical is similar to the alternate scan mode of MPEG-2. For intra predicted blocks, if the prediction mode is set to zero, a zigzag scan is selected for all blocks in a macroblock, otherwise the prediction direction is used to select a scan on a block basis. For instance, if the prediction refers to the horizontally adjacent block, an alternate vertical scan is selected for the current block, otherwise (for DC prediction referring to the vertically adjacent block), alternate horizontal scan is used for the current block.

click to expand
Figure 9.19: Alternate scans (a horizontal) (b vertical)

For nonintra blocks, the 8 x 8 blocks of transform coefficients are always scanned with zigzag scanning, similar to all the other standard codecs. A separate VLC table is used for all intra DC and AC coefficients.

Depending on the value of intra_mode, either one or eight coefficients are the prediction residuals that must be added to a predictor. Figure 9.20 shows three 8 × 8 blocks of quantised DC levels and prediction residuals labelled A(u, v), B(u, v) and E(u, v), where u and v are row and column indices, respectively.

click to expand
Figure 9.20: Three neighbouring blocks in the DCT domain

E(u, v) denotes the current block that is being decoded. A(u, v) denotes the block immediately above E(u, v) and B(u, v) denotes the block immediately to the left of E(u, v). Define C(u, v) to be the actual quantised DCT coefficient. The quantised level C(u, v) is recovered by adding E(u, v) to the appropriate prediction as signalled in the intra_mode field.

The reconstruction for each coding mode is given by:

Mode 0: DC prediction only

(9.9)

Mode 1: DC and AC prediction from the block above

(9.10)

Mode 2: DC and AC prediction from the block to the left

(9.11)

where Q P_A, Q P_B and Q P_c denote the quantisation parameter (taking values between 1 and 31) used for A(u, v), B(u, v) and C(u, v), respectively.

9.6.4.2 Advanced inter coding with switching between two VLC tables

At low frame rates (very common for low bit rate applications), the DCT coefficients of interframe coded macroblocks are normally large. Also, in general, the VLC tables designed for intraframe coded macroblocks suits larger value coefficients better. Hence to improve the compression efficiency of the H.263 codec, the inter coded macroblocks are allowed to use the VLC tables that primarily designed for intra macroblocks, but with a different interpretation of level and run. This is made optional and is called alternative inter VLC mode [25-S]. It is activated when significant changes are evident in the picture.

The intra VLC is constructed so that codewords have the same value for last (0 or 1) in both the inter and intra tables. The intra table is therefore produced by reshuffling the meaning of the codewords with the same value of last. Furthermore, for events with large level, the intra table uses a codeword which in the inter table has large run.

Encoder action

The encoder uses the intra VLC table for coding an inter block if the following two criteria are satisfied:

the intra VLC results in fewer bits than Inter VLC
if the coefficients are coded with the intra VLC table, but the decoder assumes that the inter VLC is used, coefficients outside the 64 coefficients of a 8 × 8 block are addressed.

With many large coefficients, this will easily happen due to the way the intra VLC is used.

Decoder action

At the decoder the following actions are taken:

the decoder first receives all coefficient codes of a block
the codewords are then interpreted assuming that inter VLC is used; if the addressing of coefficients stays inside the 64 coefficients of a block, the decoding is ended
if coefficients outside the block are addressed, the codewords are interpreted according to the intra VLC.