Unequal-arm Adaptive Rood Pattern Search with Early Terminations For Fast Block-matching Motion Estimation on H.264

Based on a rood-shaped pattern of the motion-vector displacement distribution inherently resulted from block-matching motion estimation, a series of adaptive rood pattern search (ARPS) algorithms have been introduced. Among them, the unequal-arm ARPS has achieved superior performance on many accounts while maintaining a fairly close rate-distortion performance compared with that of the full search. In this paper, an enhanced version of the unequal-arm ARPS is introduced by incorporating early terminations at both the initial search and the refined local search stages. Its performance was compared with that of the UMHexagonS fast block-matching motion estimation algorithm based on the JM-9.3 software encoder. The experimental results show that the unequal-arm ARPS with early terminations has yielded significant search efficiency gain while consistently maintaining a fairly close rate-distortion performance compared with that of the UMHexagonS. Furthermore, the proposed algorithm is fairly simple on implementation