A fast multi-resolution block matching algorithm for motion estimation

In this paper, we present a fast multi-resolution block matching algorithm (BMA) for an MPEG-2 video encoder. Motion vectors (MVs) of spatially adjacent blocks are often exploited as credible MV candidates in searching continuous motions. However, they are no longer helpful when searching complex or random motions. We propose a novel multi-resolution BMA to solve this problem. At the coarsest level, a full search BMA (FSBMA) is performed for searching complex or random motions. Concurrently, spatial correlation of MV field is used for searching continuous motions. Here we present an efficient method for searching full resolution MVs without MV decimation even at the coarsest level. After the coarsest level search, two or three initial MV candidates are chosen for the next level. At the following levels, the MV candidates are refined within smaller search areas. Experimental results show that in comparison with FSBMA, the proposed BMA achieves a speed-up factor over 710 with minor PSNR degradation of 0.2 dB at most, under a normal MPEG2 encoding environment. Furthermore, our scheme is also suitable for hardware implementation due to regular data-flow. (C) 2000 Elsevier Science B.V. All rights reserved.