Fast Scheme for the Four-Step Search Algorithm in Video Coding

Due to the high computational complexity of the full-search algorithm, fast block motion estimation algorithms are needed for real-time implementations of the current video coding standards. Recently, a four-step search algorithm for block motion estimation has been proposed in the literature. In this paper, a fast scheme for the four-step search algorithm is proposed to reduce the computational complexity of the four-step search algorithm without loss of its accuracy. By using eight-bit partial sums and the corresponding lower bound for the modified sum of absolute difference (MSAD) criterion in the proposed scheme, a large number of candidate motion vectors are discarded while still retaining the optimal motion vector of the four-step search algorithm. In this way, the computational requirement of the four-step search algorithm is significantly reduced while maintaining its accuracy. It is shown that the byte-type data-parallelism on a single instruction multiple data (SIMD) architecture can be utilized to further accelerate the execution of the proposed scheme. Simulations of the scheme are carried out for various benchmark video sequences and the results demonstrate that the new scheme can reduce the computational complexity of the four-step search algorithm by 20 to 40 percent with no loss of its accuracy.