Fast Block Matching Motion Estimation Algorithm Based On Search Pattern For Video Coding

The fast block matching motion estimation (BMME) algorithm based on search pattern has been adopted as the main technique of inter-frame coding in many international video coding standards since H.261. It is also the hot research point in the related field and several new algorithms were proposed each year recently. But the module of motion estimation is still the most time-exhausted one in video coding while occupying the most system resources. The performance of this kind of motion estimation algorithms having been upgraded significantly under the effort of researchers can not meet the requirement of real-time application. Whether we can find the new break- through is the key to get more advancement of BMME algorithm in the future.The fast motion estimation algorithms are classified by the approaches of how to accelerate the search process, and the in-depth study of the fast block matching motion estimation algorithm based on search pattern is performed in this paper. Based on the summary and analysis of the similar fast algorithms, the developing clue of this kind of algorithm is unveiled. A new directional model of motion vector distribution (MVD) is brought forward from the understanding of the MVD and the statistical results of the actual data, which can reflect the characters of MVD more precisely. The evolution progress of the fast BMME algorithm based on search pattern is also discovered and described. The conception of the conditional MVD in this paper is first given out in the world, including the prior probability distribution and the posterior probability distribution of motion vectors, and the characters of these two types of conditional MVD are summarized here.Three new search patterns based on the directional model are designed, which are the first directional search patterns with the distinct directionality in the world. And three new fast BMME algorithms are proposed with different performance by using three new patterns. Both the experiment results and the theoretical analysis have proved that the new algorithms are much more effective and efficient than the classic and famous algorithms. Finally, the related issues about the new algorithms are discussed in ten aspects, which is the most comprehensive and detailed discussion in the related literature at the present time.