Soutenance mémoire
Predictive Motion Vector Coding
The signaling required for approaches like the ones presented so far (i.e. smaller block sizes, symmetric and asymmetric partitioning schemes and bidirectional prediction) yields a myriad of highly correlated temporal prediction metadata. For instance, it is a known fact that motion vectors are highly correlated both spatially and temporally. This correlation is inherent to natural images as abrupt changes, either in space or in time, are infrequent. In order to improve compression efficiency of the temporal prediction metadata, modern video encoding standards use predictive coding on the temporal prediction metadata itself. Motion vectors are differentially coded from a motion vector prediction. A motion vector prediction is based on nearby (i.e. spatially or temporally) previously coded motion vectors. The motion vectors used for motion vector prediction vary on the video coding standard and the availability of nearby vectors. The motion vector prediction algorithm is specified in the video coding standard, as the prediction must be identical between the encoder and the decoder. For example, AVC uses an element-wise median of the motion vectors of three spatial neighboring blocks. As shown in fig. 2.5, these blocks are immediate neighbours, located: to the left, above and the above and to the right (Richardson, 2010, p. 159). In contrast, HEVC signals the predicted motion vector from a list of candidates. This list is made up of up to two spatial candidates (a ∈ {A0,A1},b ∈ {B0,B1,B2}) and one temporal candidate (c ∈ {C0,C1}), as can be seen in fig. 2.6. The candidate C0 represents the motion vector of co-located block in a previously encoded frame. In all cases, the first available candidate is chosen. In any case, if no candidate is available, the zero motion vector is used.
Rate-Constrained Motion Estimation As discussed earlier, the bit stream of an encoded video sequence will contain residual coefficients and metadata describing the prediction parameters. In many applications, like video-conferencing or streaming, it is desirable to limit the rate that the encoder can use to encode the video. When this happens, the residual coefficients and metadata now compete for the available bits. When bit rates are high, this is not problematic. However, when bit rates are low, the competition between the two can become so important that it can have an impact on the visual quality of the encoded sequence. For low bit rate scenarios, an unconstrained motion estimation algorithm will make decisions that require so much metadata that there will not be enough left for the residual. When this happens, the encoder will be forced to increase quantization to reduce the number of bits required to encode the residual. As such, that error criterion used for motion estimation must not only take into consideration distortion, but must also take into consideration the number of bits required by the metadata.
The most popular solution to this problem is to add an empirical weighing coefficient (λ) in the error criterion like so J(P,v) = SAD(P,v)+λR(v) . (2.4) In the previous equation, the function R(v) returns an approximation of the number of bits required to encode the motion vector related to the candidate at position v relative to P. It is important to understand that the weighing coefficient λ models the trade-off between the motion vector rate and the energy present in the SAD distortion. Minimizing this criterion in no way guarantees to minimize the rate-distortion ratio. One must not be confused by the terminology, there is an important difference between rate-distortion and rate-constrained. Rate-distortion Authors refer to the rate-distortion ratio as the total rate of the block (metadata + residual) over the squared error after quantization. Rate-constrained When referring to rate-constrained motion estimation, authors imply that only the vector rate is considered. The motion vector cost is weighted and added to the SAD of the residual before quantization. The exact definition of λ varies based on the encoder implementation. However, modern standards often recommend a value for λ.
For example, the recommended value of λ for 19 the H.264 1 video coding standard is λ = 0.85×2 QP−12 3 . (2.5) The reason why the standard comity recommends a certain value is that rate and distortion are design consideration of the quantization step size (Qstep) (Sullivan and Wiegand, 1998). The authors further explain that Eq. (2.5) is an approximation of the assumed functional relationship between the quantization parameter (QP) and λ up to a QP of about 25. This relationship “may not be completely realistic, the derivation reveals at least the qualitative insight that it may be reasonable” (Sullivan and Wiegand, 1998). We access the x and y elements of vectors v and p via subscripts. This allows to define the R function, used in Eq. (2.4), as follows: R(v) = G(4(vx−px))+G(4(vy−py)) , (2.6) where G(v) returns the length of the signed exponential Golomb code required to encode v, and p ∈ 14 Z2 is the motion vector predictor (MVP). The differential between the MV and the MVP is multiplied by four to obtain integer values conforming to the H.264 and the HEVC standards, which encode MVs using quarter pixel precision specified with fixed point notation. Signed exponential Golomb codes are used in the H.264 standard to encode the differences between MVs and the MVP. Although signed exponential Golomb codes are not used by the HEVC standard to encode MV information, they are the recommended metric used to quickly measure MV costs in rate-constrained block-matching algorithm (RCBMA) for HEVC (McCann et al., 2014).
As described in (Richardson, 2010), exponential Golomb codes are composed of a prefix part, a marker bit and an info part. The total length of an exponential Golomb code for an integer value v is measured with the following function: G(v) = 2×I(v)+1 . (2.7) The I() function returns the length of the info part which is multiplied by 2, because the prefix is the same length as the info. The added one represents the marker bit. The I() function is defined as follows: I(v) = _log2(2|v|+1) , (2.8) where |v| is multiplied by 2, because the code words used in the info part alternate between negative and positive values. One is added to represent that the value 0 is assigned to the code word ’0’. The _ operator represents the floor function. We started this chapter by describing ME and MC, the core concepts behind temporal predictions. We continued it by describing modern techniques related to temporal prediction. Some of these techniques are specified by the video coding standard, while others are not required but are strongly recommended and are ubiquitous in modern encoders. The presented techniques are important because they have an impact on successive elimination algorithms, which is the subject of the next chapter.
|
Table des matières
INTRODUCTION
CHAPTER 1 VIDEO ENCODER OVERVIEW
1.1 Overview of a Block-Based Hybrid Video Encoder
1.2 Quad-Tree-Structured Block-Based Video Coding
CHAPTER 2 TEMPORAL PREDICTION
2.1 Motion Estimation and Motion Compensation
2.2 Fractional Accuracy Motion Estimation and Motion Compensation
2.3 Bidirectional Temporal Prediction
2.4 Predictive Motion Vector Coding
2.5 Rate-Constrained Motion Estimation
CHAPTER 3 LITERATURE REVIEW ON SUCCESSIVE ELIMINATION
3.1 Transitive Elimination
3.2 Fast Summation
3.3 Multi-Level Successive Elimination Algorithm
3.4 Rate-Constrained Successive Elimination Algorithm
CHAPTER 4 LITERATURE REVIEW ON MOTION ESTIMATION ALGORITHMS
4.1 Optimality
4.2 Common assumptions of search algorithms
4.2.1 Monotonically Decreasing Search Area
4.2.2 Center-Biased Motion Vectors
4.3 2-D-Logarithmic Search
4.4 Predictive Search
4.5 Early Termination
4.6 TZ-Search Algorithm
4.7 Confidence Intervals For Motion Estimation
CHAPTER 5 MOTION ESTIMATION SEARCH ORDERING AND SUCCESSIVE ELIMINATION
5.1 Ordering and Transitive Elimination
5.2 SEA-Optimal Search Ordering
5.2.1 MVP Pruning
5.2.2 The Sorted Subset Approach
5.2.3 Experimental Results and Discussion
5.3 The Increasing Rate Rule
5.3.1 Early Termination
5.4 Cost-Based Search Ordering Pattern
5.4.1 Experimental Results and Discussion
5.5 Implementation Considerations of the Increasing Rate Rule
5.5.1 Asymmetric Distribution of Motion Vector Costs
5.5.2 Off-Centered Search Areas
5.6 Cost-Based Search Ordering
5.6.1 Fast Cost-Based Search Ordering Implementation
5.6.2 Early Termination Criterion
5.6.3 Experimental Results and Discussion
5.6.3.1 Comparison with HEVC HM Full Search
5.6.3.2 Comparison with RCSEA
5.6.3.3 Influence of Early Termination
5.6.3.4 Comparison with Suboptimal Algorithms
CHAPTER 6 ENHANCED RATE CONSTRAINT
6.1 Information Reuse when Partitioning Blocks
6.2 Improved Early Termination
6.3 Experimental Results and Discussion
6.3.1 Comparison with HEVC HM Full Search
6.3.2 Comparison with HM-CBSEA
CHAPTER 7 MULTI-LEVEL RATE-CONSTRAINED SUCCESSIVE ELIMINATION ALGORITHM IN SUB-OPTIMAL SEARCH ALGORITHMS
7.1 Justification for SEA in TZ-Search
7.2 Multi-Level Composition Patterns
7.2.1 Rectangular Partitions
7.2.2 Asymmetric Partitioning
7.3 Double-check Mechanism for RCSEA in TZ-Search
7.4 Cost-Based Search Ordering for Bi-Predictive Search
7.5 Experimental Results and Discussion
7.5.1 ML-RCSEA in TZ-Search
7.5.2 Double-check Mechanism for RCSEA in TZ-Search
7.5.3 Cost-Based Search Ordering for Bi-Predictive Search
7.5.4 Minimal SAD Savings Threshold
7.5.5 Comparison with State-Of-The-Art Methods
7.5.6 Detailed Time Savings
CONCLUSION
LIST OF REFERENCES
Télécharger le rapport complet
