Predictive and distribution-oriented fast motion estimation for H.264/AVC

For fast motion estimation (ME) in video coding, many fast block matching ME algorithms are proposed. Among these algorithms, Unsymmetrical-cross Multi-grid-hexagon Search (UMHexagonS) algorithm can be regarded as a distinguished representative. However, the excellent rate-distortion (R-D) performance of UMHexagonS comes at the cost of relatively high computational complexity of the initial search point decision and the hybrid search pattern. To tackle this disadvantage, a new fast ME algorithm is proposed. An experiment is performed to analyze the best motion vectors (MVs) distribution in natural video sequences. Based on the correlations between spatial and temporal blocks as well as the asymmetrical distribution of the best MVs in natural video sequences, a small diamond search pattern and an asymmetrical cross search pattern are jointly employed to locate the best matching block. Experimental results demonstrate that when compared to recently improved UMHexagonS, the ME time can be reduced up to 38.70 % while with a quite similar R-D performance as UMHexagonS. When compared with the fast directional gradient descent search (FDGDS), the ME time can be reduced up to 12.23 %, while with a better R-D performance than FDGDS, 0.11 dB BDPSNR increase and 2.14 % BDBitrate decrease. Especially, the proposed algorithm can work well in video sequences with various motion activities and formats, and is more suitable for real-time application.