Highly efficient motion estimation algorithms in video coding

Abstract

In most of the digital video coding standards, e.g. H.264/AVC, motion estimation and compensation is a crucial process. Motion compensation compensates the displacements of objects from the reference frame to the current frame, and such displacements are found by motion estimation. Together they remove the temporal redundancy between frames in a video. However, the computational complexity of motion estimation is very high. Recent research has shown that it takes 50-70% of the total H.264/AVC encoding time. To realize some common applications, for example real-time encoding, the computational complexity of the encoder has to be reduced. A more efficient motion estimation algorithm is therefore necessary. In the first part of this work, the gradient descent search approach, which has search points that strictly follow a descending path of the error surface, is re-evaluated. It is found that the gradient descent search approach together with the one-at-a-time search strategy result in a more efficient motion estimation search strategy. A new algorithm named enhanced gradient descent search (EGDS) is proposed based on these strategies. Experimental results show that EGDS out performs many traditional motion estimation algorithms. Furthermore, the adaptive search patterns approach is studied. There are two motion content classifiers, namely the geographic classifier and the predicted MV classifier. An in-depth analysis of the motion estimation error surface is conducted. It is found that a global minimum point affects its nearby error surface more than the error surface further away from it. Based on this, the error descent rate (EDR) at the search window centre can be used to estimate the motion content of a macro-block. A novel motion estimation algorithm called search patterns switching (SPS) algorithm, which uses the EDR as motion content classifier, is proposed. An optimum threshold for the SPS algorithm is found which is universal and video content independent. Performance evaluations prove that SPS algorithm is very fast and robust. Motion estimation in hardware implementation is researched. The systolic array architecture, which is a popular and efficient architecture for motion estimation algorithm hardware implementations, is analyzed. Several systolic array implementations for fast block matching algorithms are proposed. A novel method to simulate the speed and power consumption of block matching algorithm implementations in systolic array is also proposed which helps the design of video encoding chip and future research in hardware-oriented motion estimation algorithms. Finally, variable block size motion estimation is studied. It is found that in traditional fast variable block size motion estimation (FVBSME) algorithms, substantial computation is wasted because distortion data cannot be reused. A novel FVBSME algorithm called joint search (JS) algorithm is proposed to address the problem. Using full distortion data reuse together with a novel stopping criterion and a filled search pattern, JS algorithm is much faster than other FVBSME algorithms while having video quality close to that of the exhaustive search.

Date of Award	15 Jul 2008
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Lai Man PO (Supervisor)