Efficient direction-oriented search algorithm for block motion estimation

Motion estimation is one of the most crucial and time-consuming component of video compression methods. However, much research has been done to improve computational complexity at the expense of the loss in performance of matching of blocks. A novel block matching algorithm named efficient direction-oriented search is proposed. For this, the proposed algorithm firstly aims to dynamically switch between search regions based on the location of minimum distortion error. The search region dimension is also made adaptive for faster convergence. Then the computational complexity is reduced by using a proposed horizontal, vertical wings diamond search pattern and, two ±45° inclined hexagon-shaped direction-oriented search patterns. For further speed-up in the search process, partial distortion calculations are employed. A method for optimal threshold value selection based on the distortion statistics for different partial distortion calculations is presented. The performance of the proposed algorithm is evaluated for different video sequences containing: slow, medium, fast, and directional motion content. The experimental results indicate that significant improvement in speed-up can be achieved while maintaining the better peak signal-to-noise-ratio performance. For directional motion video sequences, the proposed method even outperforms the full search algorithm with a significantly lower computational cost.