Research And Implementation Of Fast Motion Estimation Algorithm For H.264

New video coding standard H.264 was published by ITU-T Video Coding Experts Group (VCEG) and the ISO/IEC Moving Picture Experts Group (MPEG) formed a Joint Video Team (JVT) in 2003. Because some advanced coding technologies are used in H.264, such as variable block size motion estimation, fractional pixel motion estimation, multi-reference frame motion estimation, rate-distortion optimization (RDO), context-based adaptive binary arithmetic coding (CABAC), context-adaptive variable length coding (CAVLC) etc, H.264 gain more coding efficiency than other video sequence standard. However these technologies are employed, the motion estimation of H.264 is much higher computation complexity than previous video coding standards. Because of these reasons, the study of motion estimation algorithm is always hot spot research in recent years to reduce the computational complexity of motion estimation in H.264.Based on the consideration of various motion characteristics of different video series, we propose a motion estimation algorithm based on vector prediction and multi-direction gradient descent search. Firstly, the algorithm utilizes the temporal and spatial correlations of the motion vectors for obtaining a predictive vector to determinate initial search point. Secondly, it determines the motion type of the current block by using adaptive thresholds. After that, different search patterns and strategies are intelligently employed. The algorithm can extend the search scope and improve the speed of motion search, and thus avoid being trapped in a local minimum of the search process. Experiment results show that the proposed algorithm can save more encoding time than the traditional hybrid Unsymmetrical-cross Multi-Hexagon-grid Search (UMHexagonS), simplified UMHexagonS and Enhanced Predictive Zonal Search (EPZS) algorithms with the motion estimation accuracy.Based on the statistical analysis of extensive experiment results of various QCIF video test sequence, we observed three statistical features, such as the distribution of modes is not uniform; The mode of a macroblock and the mode of macroblocks neighboring have strong correlation; the uplayer mode and dwonlayer mode have a certain correlation; At the same, because the distribution of modes is not uniform, in some cases, we can ignore some modes that have very little effect on encoding efficiency and are almost not used. Based on the analysis above, we propose a fast mode decision algorithm in H.264 base on statistical feature. The algorithm takes advantage of the above statistical features to early termination of mode decision, so it can reduce computation load and improve efficiency of video coding. Experiment results show that the proposed algorithm can save more encoding time than the mode decision algorithm of High Complexity Mode (HCM) and Fast High Complexity Mode (FHCM) with negligible degradation of rate-distortion performance.The paper is organized as follows. Firstly, principle of video coding in H.264 are briefly introduced, principles and key technologies of motion estimation in H.264 are detailed introduced. Secondly, Fast integer pixel motion estimation algorithms and fast mode decision algorithm in JM15.1 (H.264 Reference Software) are detailed. Lastly, a new fast integer pixel motion estimation algorithm and a new fast mode decision algorithm are proposed.