A Fast Multi-Resolution Block Matching Algorithm for Multiple-Frame Motion Estimation

Myung Jun KIM  Yun Gu LEE  Jong Beom RA  

IEICE TRANSACTIONS on Information and Systems   Vol.E88-D   No.12   pp.2819-2827
Publication Date: 2005/12/01
Online ISSN: 
DOI: 10.1093/ietisy/e88-d.12.2819
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Image Processing and Video Processing
motion estimation,  multiple frame,  fast search,  multi-resolution structure,  

Full Text: PDF(328.3KB)>>
Buy this Article

In this paper, we propose a fast multi-resolution block matching algorithm with three resolution levels (upper, middle, and lower levels) for multiple-frame motion estimation (MFME). The main concept of the algorithm is to perform a fast search while maintaining a PSNR performance similar to a full search block matching algorithm (FSBMA). The algorithm combines motion vector prediction using the spatial correlation of motion vectors and a multiple candidate search based on a multi-resolution search. To further reduce the computational complexity, we propose two temporal reduction schemes. To reduce the number of previous reference frames to be processed, the first scheme is applied to the upper level by using the information obtained from the search results of the spatio-temporally adjacent macroblocks (MBs) and the result from the current MB in the middle level of the first reference frame. The other scheme is applied to the lower level by using statistical information. Experimental results show that the proposed algorithm guarantees an average PSNR loss of less than 0.23 dB with dramatically reduced computational complexity as compared to the FSBMA. In particular, for sequences with fast motion or frame skipping, the proposed method provides a more prominent PSNR performance than those of existing fast schemes with a comparable computational complexity.