1.

Introduction

The motion vector (MV) takes a nontrivial portion of the coded video data, thus its effective coding is important in video compression.¹ The state-of-the-art technology, H.264/AVC, computes the differential MV (DMV) of a given MV using the median of its three spatially causal neighboring blocks’ MVs as its predictive MV (PMV), and the DMV is entropy-coded. Its coding performance mainly depends on the goodness of the predictor. Although the median PMV has been widely used, it is not always the best in the sense of the rate-distortion (RD) optimality of the coded MV.

The so-called MV Competition (MVComp) method² chooses, for each block, the optimal PMV (OPMV) in the RD sense from a set of candidate PMVs [hereafter referred to as a candidate set (CS)] as a part of the RD-optimal MV estimation process and signals its selected OPMV to the decoder. The CS may include some or all of the MVi's in Fig. 1. It can also include some derived vector such as the median. The additional bit overhead for signaling the selected OPMV is shown to be less than bit reduction obtained by using the MV predictor which is optimal for each block.²

Fig. 1

Example of candidate PMVs.

2.

Motivation

We note that some PMVs in the CS cannot be the OPMV for a given block and that the decoder can identify these by means of a simple contradiction testing. It can be exploited to reduce the signaling bits for the OPMV in the MVComp method² by precluding these infeasible PMVs from being used in the block-wise signaling. A previous report was published in which a similar concept of excluding infeasible PMVs (Ref. 3) was utilized, however, ours is distinct from it in several respects. First, unlike the component-wise decision of the best predictor and separate signaling for each component of the MV,³ our scheme determines and signals the optimal predictor as a 2-D vector. Furthermore, while the previous scheme³ excludes PMVs based on the vector length of the corresponding DMV, the proposed one excludes PMVs based on the actual rate comparison of the DMV. Note that two DMVs of different lengths can have entropy-coded representations having identical numbers of coded bits, as shown in Fig. 2. The benefit obtained from this distinction will be explained later with the proposed tie-breaking rule.

Fig. 2

Contour plot of equal rate of entropy-coded DMV in H.264/AVC.

3.

Proposed Motion Vector Coding

The basic concept of the contradiction testing is to bring the truth of a certain statement into question to see whether the statement is mathematically contrary to a known fact. If the statement is untenable under the known fact, it is rejected.⁴ Here, we make use of the common fact, agreed on by the encoder and decoder in encoding the MV, that the OPMV selected for coding a given MV should be the PMV in the CS producing the minimum RD of its DMV. When a decoder is supplied with a DMV, it can identify some PMVs in the CS which cannot be the OPMV, as follows. We investigate whether a temporarily recovered MV, computed as MV = DMV + PMV by using a PMV in the CS, is chosen or not as its OPMV. Note that the recovered MV is subject to the same MV coding process as the encoder according to the minimum RD criterion known as the common fact. If it is not chosen as the OPMV, the PMV is unable to be the OPMV and the decoder knows that it is excluded from the set of signaling candidates by the encoder. By doing this contradiction testing one by one for all PMVs in the CS, a reduced set of CS (hereafter denoted by CS’), which consists of only those signaling candidates for a given block, can be defined. The signaling index bits for the OPMV received by the decoder identify a member of CS’. In some blocks, CS’ may have only one member, no matter how large the cardinality of the CS may be, and, in this case, the encoder does not send any index bits (thus saving a lot of bits), but the decoder can properly handle this by performing exactly the same process of pruning the CS as the encoder.

4.

Tie-Breaking Rule

In the process of testing each member in the CS for contradictions, a tie in the rates often occurs, since non-identical DMVs may produce entropy-coded representations of the same length, as shown in Fig. 2. Therefore, a tie-breaking rule is indispensable for further enhancing the coding performance. If more than one PMV gives rise to the same rate of their DMVs, we set up a simple tie-breaking rule pre-agreed on by encoder and decoder in which the first PMV (that appeared in the CS) is to be selected as the OPMV. Since the order inside the CS does not affect the coding performance, it is sufficient to define the member order within the CS in advance. Using this simple tie-breaking rule, the encoder and decoder can reduce the cardinality of CS’ as much as possible. If the PMVs in the CS are similar to each other, it is more likely that CS’ has just one member, thus saving many signaling bits. It is the benefit of the tie-breaking rule. Figure 3 shows a simple illustration of MV decoding by the proposed method.

Fig. 3

Illustration of contradiction testing.

5.

Experimental Results

The proposed scheme is implemented in KTA reference software version 2.6r1 (Ref. 5) and its performance is tested under the conditions recommended by the Joint Collaborative Team on Video Coding for evaluating high efficiency video coding standardization.⁶ The class B (Kimono, ParkScene, Cactus, BasketballDrive), C (RaceHorses, PartyScene, BasketballDrill, BQMall), and D (RaceHorses, BlowingBubbles, BasketballPass, BQSquare) sequences are coded with quantization parameters of 22, 27, 32, and 37, respectively. The proposed scheme is compared with the H.264/AVC standard (as an anchor) and the MVComp scheme² in terms of the Bjøntegaard Delta Bit Rate (BDBR).⁷ Several CSs with cardinalities of 2 to 5 are used: CS₂ = {median (MV₁,MV₂,MV₃), MV₄}, CS₃ = CS₂ U {MV1}, CS₄ = CS₃ U {MV₂}, and CS₅ = CS₄ U {MV₃} (see Fig. 1). Figure 4 summarizes the results. The MVComp scheme with CS₂ achieves a high coding gain of 1.81% in BDBR, however its performance is degraded to 0.24% of BDBR loss as the cardinality of the CS increases. The increased signaling overhead is the reason for the degradation. On the other hand, the proposed scheme achieves a higher coding gain of 2.03% BDBR in the case of CS₂, which reaches up to 3.20% BDBR for Cactus. It is achieved by effectively reducing the number of index bits by contradiction testing. Its benefit is even more evident when the cardinality of the CS becomes larger: the proposed scheme is better than the anchor by 1.39% BDBR with CS₅, while MVComp (Ref. 2) method suffers from decreased coding gain. Unlike the MVComp method,² the proposed one always achieves bit-saving, regardless of the cardinality of the CS. It demonstrates the utility of the proposed idea of contradiction testing associated with MV coding.

Fig. 4

BDBR comparison with H.264/AVC.

6.

Conclusions

We presented an MV coding scheme capable of using the OPMV in the sense of the minimum RD while considerably reducing its index overhead. The experiments showed that the proposed method achieves a coding gain of 2.03% in BDBR with CS₂ compared to the H.264/AVC standard. Compared to the MVComp scheme,² the proposed contradiction testing with a tie-breaking rule provides a stable coding gain for all of the candidate sets.