Reduced uneven multi-hexagon-grid search for fast integer pel motion estimation in H.264/AVC

A reduced uneven multi-hexagon-grid search algorithm for fast integer pel motion estimation in H.264/AVC is presented. The objective is to reduce the number of candidates for the block matching by predicting the likely area in which the minimum sum of absolute differences (SAD) can be taken. For this purpose, the proposed algorithm employs directionally partial hexagon search patterns utilizing the motion vectors computed in previous stages which supply the spatial correlation characteristics between adjacent macro blocks and the temporal ones between video frames. Experimental results show that the proposed method can save 39%similar to 69% of computational complexity compared with the original one at the cost of negligible degradation on RD performance.