Low complexity algorithm for sub-pixel motion estimation of HEVC

The next generation video coding standard, namely HEVC(High Efficiency Video Coding) introduced many efficient algorithms to enhance the coding efficiency. However, the computational complexity of motion estimation is still the most bottle neck for its implementation. In this paper, we propose a complexity reduction algorithm for fractional-pixel motion estimation (FPME). Firstly, a fast termination algorithm is proposed to fast terminate FPME using a threshold. Next, the proposed algorithm designs several original search orders and search patterns for 1/2 pixel and 1/4 pixel motion estimation, respectively. These proposed patterns are on the basis of the probability of each search point and its surrounding integer search points. Simulation result shows that the proposed algorithm succeed in reduction of search point for up to 38% with almost no coding efficiency loss.