Non-iterative motion estimation for overlapped block motion compensation

We study motion estimation in overlapped block motion compensation. Due to the interaction between neighboring motion vectors, it remains an open problem how to find the optimal motion vector set minimizing the motion compensation error. In this paper we present a non-iterative motion estimation algorithm to search for a sub-optimal solution. II utilizes the relationship between block motion estimates, by exploiting known motion estimates in the causal past and predicting the unknown future. Our algorithm significantly outperforms other known non-iterative algorithms, including conventional block matching and windowed block matching. Furthermore, while only costing a fraction of the computation needed by iterative algorithms, our non-iterative algorithm obtains most of the gain realizable by using the iterative algorithms. The experimental results show that iteration is not necessary to achieve large gains, in contrast to common belief.