Highly efficient predictive zonal algorithms for fast block-matching motion estimation

Motion estimation (ME) is an important part of any video encoding system since it could significantly affect the output quality of an encoded sequence. Unfortunately, this feature requires a significant part of the encoding time especially when using the straightforward full search (FS) algorithm. We propose two techniques, the generalized motion vector (MV) predictor and the adaptive threshold calculation, that can be used to significantly improve the performance of many existing fast ME algorithms. In particular, we apply them to create two new algorithms, named advanced predictive diamond zonal search and predictive MV field adaptive search technique, respectively, which can considerably reduce, if not essentially remove, the computational cost of ME at the encoder, while at the same time give similar, and in many cases better, visual quality with the brute force full search algorithm. The proposed algorithms mainly rely upon very robust and reliable predictive techniques and early termination criteria with parameters adapted to the local characteristics combined with the zonal based patterns. Our experiments verify the considerable superiority of the proposed algorithms versus the performance of possibly all other known fast algorithms, and FS.

I. Introduction

Block-matching motion estimation (BMME) is an essential part of several video-coding standards, such as MPEG-1/2/4 and ITU-T H.261/263/263+. By using motion estimation (ME) and compensation, we are able to exploit the temporal correlation and reduce the redundancy that exists between frames of video sequences, which leads to high compression.