Rate-distortion optimal motion estimation algorithm for video coding

A rate-distortion optimal motion estimation algorithm that leads to an efficient bit allocation between inter- and intra-frame information is presented. For coders in which motion vectors are differentially encoded, the rate-distortion optimization process is formulated as a shortest path finding problem. Adopting this framework, we show that the optimal solution for the conventional block-based motion estimation followed by 1-D DPCM and Huffman coding can be obtained by using dynamic programming or the Viterbi algorithm without resorting to an iterative procedure. Since memory and computational requirements for the optimal algorithm increase dramatically with the search range, we propose an effective fast algorithm that closely approximates the optimal performance while requiring considerably less complexity. When used in a hybrid motion compensated (MC) coding system, the proposed scheme outperforms the conventional MSE-optimal motion estimation approach in terms of PSNR performance under a low-bit-rate constraint. Our experimental results demonstrate overall gains in the range of 0.5 to 1.4 dB