A survey of fast mode decision algorithms for inter-prediction and their applications to high efficiency video coding

The emerging High Efficiency Video Coding (HEVC) standard attempts to improve the coding efficiency by a factor of two over H.264/AVC using new compression tools with high computational complexity. The increased computational complexity makes the real-time execution with reasonable computing power become one of the critical concerns for the commercialization of HEVC. A large number of prediction modes are the main causes of the increased complexity of HEVC. Thus, a fast decision of a prediction mode needs to be effectively used to reduce the computational complexity. To take advantage of large amounts of previous works and to find a guide for application to HEVC, this paper presents a survey of these efforts for the previous standards, especially for H.264/AVC, and examines the possibility of the previous algorithms to be applicable for HEVC. To this end, previous algorithms are categorized and then the effectiveness of each category for HEVC is evaluated. For this evaluation, a previous algorithm is modified for HEVC when it is not applicable to HEVC directly. Simulation results show that most previous algorithms with slight modification, in general, improve the encoding speed with a relatively small degradation of the compression efficiency. Among them, hierarchical mode decision is especially effective whereas mode pre-decision using motion or spatial homogeneity often results in inaccurate results.