UMHexagonS search algorithm for fast motion estimation

In video coding, motion estimation is the most time consuming part due to its high computational complexity. Based on the high temporal and spatial correlation of motion vector (MV), a new fast motion estimation algorithm of UMHexagonS (UMH) has been proposed to reduce computational complexity by using relatively few search points without degrading image quality, in which the modified patterns with new uneven cross, multi-hexagon-grid and hexagon are applied to. The proposed algorithm alleviates the computational burden and maintains the quality of video. Compared with the original UMH algorithm, the proposed algorithm has a better performance, and it reduces the number of search points by 32% at least and preserves similar average peak signal-to-noise ratio (PSNR) value at the same time.