Learning-based bypass zone search algorithm for fast motion estimation

Video coding has been widely explored by academia and industry in recent years, mainly due to the great popularization of video applications and multimedia-capable devices. The Motion Estimation (ME) process receives special attention since it is one of the most complex steps in video coding. The Test Zone Search (TZS) is the main algorithm employed for integer ME in recent video codecs, such as those based on the High Efficiency Video Coding (HEVC), and has been used in the standardization process of the future Versatile Video Coding (VVC) standard. However, even though it is designed as a fast ME algorithm, the computational effort required by TZS is still very high, compromising the encoding process in multimedia-capable devices that operate on limited energy or computational resources. This work presents the Bypass Zone Search (BZS) algorithm, a learning-based solution for fast ME that improves TZS, aiming at a better tradeoff between compression efficiency and computational cost. First, a set of analyses on TZS is presented, which allowed the design of two strategies to reduce the ME computational cost. The first one, named as Learning-based Bypass Motion Estimation (LBME), consists of a machine learning-based approach that predicts whether the best motion vector has already been found and bypasses the remaining ME steps. The second strategy, named as Astroid Raster Pattern (ARP), is a novel search pattern developed for the most complex TZS step, the Raster Search. By combining the two proposed strategies in BZS, the ME processing time is reduced by 60.98% (Random Access) and 63.05% (Low Delay) in comparison to TZS. The overall HEVC encoding time is reduced by 14.32% (Random Access) and 17.64% (Low Delay), with a negligible loss of 0.0837% (Random Access) and 0.04% (Low Delay) in BD-rate.