Fast motion estimation algorithms for overlapped block motion compensation

Abstract

While block motion compensation has been the preferred method for reducing inter-frame dependencies in most standards for video coding (H.261, MPEG), a new proposal for very low bit rate video coding (H.263) has included overlapped block motion compensation (OBMC) as an optional mode of operation. In this paper, we present fast algorithms for motion estimation when compensating with OBMC. Standard block matching motion vectors are not optimal for OBMC. Our algorithms estimate which block motion vectors yield the most improvements upon optimizing motion, orders the blocks and optimizes motion vectors based on the ordering. The estimation is based on readily available information about block matching, viz., prediction errors over blocks. As simulation results will demonstrate, the algorithms result in near optimal performances at low computational costs. An additional advantage of the algorithms is that they may be terminated after a few motion vectors have been optimized and still result in high performance gains. This is of advantage in situations where the available computational power at the encoder varies (as in a videophony situation where the frame rate adapts depending on scene activity or available band-width) and it becomes desirable that the motion vectors chosen for optimization result in the highest gains possible.