A New Rate-Complexity-Distortion Model for Fast Motion Estimation Algorithm in HEVC

摘要

In the high efficiency video coding (HEVC) standard, motion estimation (ME) adopts a quadtree coding structure and a larger search range to improve the coding performance. These advanced coding tools, however, dramatically increase the computational complexity. To accelerate ME, fast methods have been proposed that reduce ME complexity at the expense of rate-distortion (R-D) performance. However, none of these methods can claim their tradeoff to be optimal. In this paper, we propose an optimal fast motion estimation (FME) algorithm based on an analytical model of rate-complexity-distortion (R-C-D). We extend the traditional R-D model by introducing the ME complexity into it, which enables us to explicitly express the R-D performance under different complexity budgets. Based on the R-C-D model, the proposed FME finds the R-C-D optimized search ranges for some representative prediction units (PUs), which are then extended or refined dynamically according to motion characteristics for neighboring PUs. The proposed FME enables an R-D performance close to that of full search. When compared with the default FME method in the reference software of HEVC, the proposed fast algorithm can reduce the complexity by over 80% while improving the R-D performance. Furthermore, our proposed FME algorithm is hardware friendly, as regular data flow enables high data reuse efficiency.