Motion classification-based fast motion estimation for high-efficiency video coding

High efficiency video coding (HEVC), the latest video coding standard, is becoming popular due to its excellent coding performance. However, the significant gain in performance is achieved at the cost of substantially higher encoding complexity than its precedent H.264/AVC, in which motion estimation (ME) is the most time-consuming module that effectively removes temporal redundancy. Test zone search (TZS) is adopted as the default fast ME method in the reference software of HEVC; however, its computational complexity is still too high for real-time applications. Several fast ME algorithms have been recently proposed to further reduce ME complexity; however, these approaches typically lead to non-negligible performance loss. To address this problem, this paper proposes a motion classification-based fast ME algorithm. By exploring the motion relationship of neighboring blocks and the coding cost characteristic, the prediction unit (PU) is first categorized into one of three classes, namely, motion-smooth PU, motion-medium PU and motion-complex PU. Then different search strategies are carefully designed for PUs of each class according to their respective motion and content characteristics. Furthermore, a fast search priority-based partial internal termination scheme is presented to rapidly skip impossible positions that speeds up cost computation during the ME process. Extensive experimental results demonstrate that the proposed algorithm achieves as much as 12.47% and 20.25% reductions in total encoder complexity when compared with TZS under low delay P and random access configuration, respectively, with negligible rate-distortion degradation; thus, it outperforms state-of-the-art fast ME algorithms in terms of both coding performance and complexity reduction.