1. Introduction
Motion estimation is an important part of most video encoding systems. For video compression applications, the estimated motion vectors (MVs) are used to produce a motion-compensated prediction of a frame to be coded from a previously coded reference frame. Among motion estimation methods, the Block-Matching Algorithm (BMA) seems to be the most popular method due to its effectiveness and simplicity for both software and hardware implementations. BMA is also used extensively in all current international video compression standards such as MPEG-1, MPEG-2, MPEG-4, H.261, and H.263. As the Full-Search (FS) method requires a very large amount of computation, various fast algorithms for block matching have been developed to speed up the search.