Experiments with new overlapped block motion estimation algorithms

A new international standard for videoconferencing uses overlapped block motion compensation (OBMC) in the advanced prediction mode for improved motion compensation accuracy. Optimal motion estimates for OBMC may be computed by a computationally expensive iterative algorithm. A recent paper has suggested a computationally inexpensive two pass algorithm to compute motion estimates for OBMC. In the first pass, exhaustive search block matching is used to compute motion. This motion is then used for OBMC. Using a combination of the average OBMC error over and the variance of the error over a block and its neighbors, blocks are ordered. In the second pass, motion of the significant blocks form the ordering are optimized. In this paper, we investigate two fast search block motion estimation algorithms in the place of the exhaustive search algorithm. The algorithms are the three step search and gradient search block motion estimation algorithm. Simulations results with a head and shoulders video sequence reveals that the gradient search algorithm performs close to exhaustive search algorithm while the three step algorithm has lower performance.