i. Block matching can be considered as the most popular method for practical motion estimation due to its lesser hardware complexity. As a result it is widely available in VLSI, and almost all H.261 and MPEG 1-2 codecs are utilizing block matching for motion estimation. In block matching, the best motion vector estimate is found by a pixel-domain search procedure.

ii. The basic idea of block matching is depicted in Figure 3, where the displacement for a pixel (ni, n2) in frame k (the present frame) is determined by considering an Ni x N2 block centered about (771,772), and searching frame k + 1 (the search frame) for the location of the best-matching block of the same size.

iii. Block-matching algorithms differ in:

• the matching criteria (e.g., maximum cross-correlation, minimum error)

• the search strategy (e.g., three-step search, cross search), and

• the determination of block size (e.g., hierarchical, adaptive)

Exhaustive block matching algorithm

iv. The Exhaustive Search Block Matching Algorithm, is one of the first algorithms which was used for block based motion compensation.

v. Finding the best-matching block requires optimizing the matching criterion over all possible candidate displacement vectors at each pixel.

vi. That is, each block, from within the search window of the candidate frame, is compared to the current block and the best possible match is considered. It is explained in the figure below (Figure 4)

vii. In the above figure, the current block is shown in frame k (Reference frame) and the search window is shown in the frame k+1 (Candidate frame)

viii. In this method, for each block in the reference frame, the algorithm searches all candidate blocks within the search window in the candidate frame and selects the block that gives the smallest error based on the selected criteria.

ix. The advantage of Exhaustive block matching algorithm is that it evaluates the matching criterion in all the candidate blocks within the search window. Thus it is very accurate

x. The disadvantage of Exhaustive block matching algorithm is that it is a time consuming method.