Prediction-biased diamond search algorithm: a new approach to reduce motion estimation complexity

Motion estimation (ME) is an inevitable part of video coding. However, ME demands extensive computational power. This imposes a severe challenge to hand-held video application devices with limited computational capability. Fast ME techniques reduce the computational load but affect the visual quality of the de-compressed video. There has been a longstanding interest in designing an efficient fast ME method to lower the computational intricacy without adversely affecting video quality. In this paper, we have utilized motion information from the neighboring blocks to predict the center of the search pattern for the present block. We have modified the existing center-biased diamond search algorithm by incorporating the prediction scheme into it. The proposed prediction-biased diamond search (PDS) algorithm uses a compact search pattern around the predicted center in the first step of ME. This, in turn, lowers the number of search points remarkably. Experimental results indicate that the proposed PDS algorithm can reduce the number of search points by more than 50% over the conventional diamond search algorithm. More importantly, the PDS algorithm requires a minimal amount of computation to predict the center of the search. It, therefore, significantly decreases the overall computational load of the encoder. Our experimental results indicate that the degradation introduced by the PDS algorithm is only 1.57% compared to the optimal full search algorithm.