An adaptive recent-biased search algorithm for fast multi-frame block-matching motion estimation

Multi-frame motion compensation improves the rate-distortion performance substantially by introducing much higher loading to the system. Without considering temporal correlations between multiple reference frames, conventional single-frame search algorithms can still be applied to multi-frame motion estimation, but using a rather inefficient frame-by-frame approach. In order to exploit this redundancy, a multi-frame extension of the well-known cross-diamond search algorithm is proposed. Unlike those algorithms that orderly search each reference frame, our algorithm adopts a novel recent-biased search strategy and makes use of 3-dimensional search patterns to sub-sample the 3-dimensional memory space as a whole. This approach significantly boosts the efficiency of the block-matching process. Besides, with the idea of diffusion detection, our algorithm can adapt its strategy effectively to different degree of motions. 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.05 dB. Simulations also prove that our algorithm considerably faster than the cross-diamond search and the diamond search algorithms with similar PSNR gain.