A Fast Algorithm for Optimizing Bit Rate Allocation of Motion Vectors
Zhang Zong · Chinese Journal of Computers · 2002
Recently, many variable size region wise motion estimation techniques have been proposed to replace the conventional constant size block motion estimation, improve the performance of video codec, particularly at very low bit rates. In these region wise motion estimation approaches, Lagrangian multiplier method was commonly adopted to optimize the bit allocation of motion vector field under the constraint of the target bit rate. However the high computation complexity prevents them from being applied in practices. On analyzing the nature of motion compensation prediction, this paper proposes a fast algorithm of optimizing bit allocation for the quadtree structured motion vectors (MV) field based on the minimum entropy criterion, according to which the quadtree structured leaf MVs will be pruned if and only if the increased entropy of MVs is greater than the associated decreased entropy of compensation frame difference (CFD),otherwise, will replace the corresponding root MV. By adaptively pruning along the backward search path of the quadtree, the proposed fast algorithm reaches a globally optimal solution to this problem. Through assuming a prior distribution, a closed format of the theoretical entropy of CFD is presented. Considering the lossy nature of video coding, a modified scheme to the theoretical entropy of CFD is also described, in which theoretical entropy of CFD for each sub block is multiplied by a suitable weighting factor according to its position in the quadtree. To capture the high correlation among MVs, a merging approach of MVs is simultaneously described, in which the MV with minimum norm will be lifted to its parent node position and coded with higher priority. Simulation experiments on a motion compensated three dimensional wavelet video codec show that the proposed optimally pruning algorithm is not only fast but also robust. It will yield an optimal bit allocation across MVs and CFD if a suitable searching depth is provided. Avoiding the concrete post processing of CFD, the proposed algorithm can also be applied to the conventional DCT based hybrid video codec.