Rate-constrained hierarchical motion estimation using BFOS tree pruning

The rate-distortion efficiency of motion compensation is improved by employing a nonuniformly sampled displacement field. The field is constructed based on a hierarchy of component displacement fields. Using block matching, the component displacement vectors are determined in a successive refinement manner, from the coarsest level to the finest level of the hierarchy. Based on the hierarchical block-matching motion compensation, a tree is constructed whose nodes are labelled with the distortions and bit rates resulting from the compensation. The BFOS algorithm is used to efficiently find pruned subtrees of the tree. Each pruned subtree corresponds to a nonuniformly sampled displacement field that furnishes the best rate-distortion performance. Compared to the conventional fixed-size block matching algorithm, and under the some bit-rate constraint, our hierarchical algorithm improves the average PSNR by up to 2.2 dB and offers superior subjective video quality