Fast block-matching motion estimation by recent-biased search for multiple reference frames

Multi-frame motion compensation improves the rate-distortion performance substantially but introduces much higher loading to the system. Without considering temporal correlations, conventional single-frame block-matching algorithms can be used to search multiple frames in a rather inefficient frame-by-frame way. In order to exploit the motion characteristic in long-term memory, a multi-frame extension of the well-known cross-diamond search algorithm is proposed. Unlike those algorithms that evenly search each reference frame, our algorithm adopts a novel recent-biased spiral-cross search pattern to sub-sample the 3-dimensional memory space as a whole. This approach significantly boosts the efficiency of the block-matching process. Two new techniques, stationary block tracking and multiple searching paths, are employed to further improve the speed and accuracy. As compared to full search, experimental results show that our algorithm can reduce up to 99.5% complexity in terms of searching points while limiting the PSNR loss in 0.04 dB. Simulations also prove that our algorithm out-performs the cross-diamond search and diamond search algorithms in speed and accuracy.