Optimizing the motion vector accuracies in block-based video coding.

Abstract

In advanced video coders, motion vectors are used to improve the prediction of the frame to be encoded. These motion vectors and the prediction error or difference frame must be encoded with bits. The number of bits allocated to the motion vectors in most video coders is based on heuristics and empirical experiments, and typically is large enough to encode the motion vectors with 1 or 1/2 pixel accuracy. But the best motion vector accuracies are not known. In this dissertation, we analyze the effect of motion vector accuracy on the encoding bit rate in block-based video coding and derive a theoretical framework to find the optimal motion vector accuracies that minimize the total rate. To do this, we analytically model the effect of motion vector accuracy on the difference frame energy. The energy-accuracy model is then used to obtain expressions for the total bit rate in terms of the motion accuracies for a wide variety of block-based, lossless and lossy video coders. Minimizing these expressions leads to simple procedures for determining how accurately to encode the motion vectors, for the classical case where all motion vectors are encoded with the same accuracy and for a new adaptive case where different vectors may be encoded with different accuracies within a frame. We implement several entropy and MPEG-like video coders based on our analysis, and present experimental results on real video sequences. These results suggest that our formulas are accurate, and that significant bit rate savings can be achieved in both lossless and lossy video coding when our optimization procedures are used. Moreover, motion vectors are computed accurately only when needed and hence the computational complexity of the video coders is considerably reduced. Our theory quantifies phenomena that previous researchers had observed empirically. For example, our formulas indicate that the motion vectors must be encoded more accurately where more texture is present, and less accurately when there is much scene noise or when the level of compression is high. Finally, our work can easily be applied to other types of video coders and to many aspects of motion-compensated video coding.