Motion Estimation And Compensation Technology In Video Compression

Motion estimation and compensation (ME/MC) in video compression is discussed. The block matching algorithm (BMA) produces large prediction error when estimating non-translational motion and it consumes over half computation of video codec. Fast BMA is first discussed and deformable block matching algorithm (DBMA) is proposed to increase the accuracy of prediction.The human visual system and background knowledge of video coding are introduced to show the guideline of compression and the important role of ME/MC. The popular block-based compression system and existent standards are introduced to show the usage of ME/MC and its history. The common models for video sequences of the real world and some estimation methods are also discussed.In order to reduce the complexity of BMA, some famous algorithms are summarized first. By analyzing the property of video sequence and real motion field, some key points for speeding up BMA are discussed. Based on those, an adaptive fast search algorithm (APFS) is proposed, which reduces about 60% search points comparing with the algorithms recommend by H.264 while same quality on average. A sub-pixel fast algorithm using both parabolic prediction and search is proposed to reduce half computation of sub-pixel BMA. We also propose a simple motion re-estimation method for video transcoder, which has very low computation and qualifies for real-time transcoding.For increasing prediction accuracy, BMA is first demonstrated to be inaccurate for nontranslation motion. A nodal-displacement based deformable model is proposed and a nodal search algorithm (NS-DBMA) is developed, which has high prediction accuracy, low computation and is easy to implement. Some improved algorithms, such as fast integer method, two-mode hybrid method, sub-pixel accuracy prediction and hexagon search method, are further proposed. Experimental results show that the improved DBMA has only 16.5% computation of Full Search BMA while outperforms 3.79dB, and also 1.2dB gain in real coding system.