Motion Estimation And Compensation Based On Deformable Block Matching Algorithm

Motion estimation and compensation using deformable block matching algorithm (DBMA) is discussed. DBMA is developed to reduce the prediction error of traditional block matching algorithm (BMA), that is, to increase the accuracy of motion estimation and to estimate the nontranslational motion. Here we propose a Nodal-search based DBMA. Some ameliorative methods are further proposed, which can alleviate the computation and improve the quality more effectively.This thesis first describes the video compression system to indicate the importance of motion estimation and compensation. Then the famous BMA and some typical fast algorithms are introduced. Finally some fundamental characteristics of fast BMAs are summarized. By analyzing the property of real video sequence, the translational model adopted by BMA is demonstrated to be inaccurate in the interframe prediction, and a nodal-displacement-based deformation model is proposed. To estimate the nodal displacements, we developed a nodal search-based algorithm (NS-DBMA), which has lower computation and better performance than original gradient-based algorithm (GB-DBMA). Some improved methods are further proposed, such as the two-mode hybrid method which combines BMA and DBMA, the auto-terminate method which stops searching when the prediction is good enough, the cross-search method which uses simple search pattern, the sub-pixel accuracy prediction which denotes motion more accurately and computing optimization method.Experimental results show that the basic NS-DBMA has only half computation of GB-DBMA but gets better subjective and objective quality, and is much easier to implement by VLSI. The most effective method, which synthesizes all ameliorative methods, has only 42% computation of the Full Search while outperforms 1.53dB. It could be used as a substitute for BMA in real coding system.