Block Matching Algorithms For Motion Estimation

Block Matching Algorithms For Motion Estimation

Motion estimation is that the patterns corresponding to objects and background in a frame of video sequence move within the frame to form corresponding objects on the subsequent frame.

Block matching is to divide the current frame into a matrix of ‘macro blocks’ that are then compared with corresponding block and its adjacent neighbors in the previous frame to create a vector that stipulates the movement of a macro block from one location to another in the previous frame.

Block matching algorithms used for motion estimation in video compression. It implements and compares 7 different types.

Exhaustive Search (ES)

This algorithm calculates the cost function at each possible location in the search window. This leads to the best possible match of the macro-block in the reference frame with a block in another frame. The resulting motion compensated image has highest peak signal-to-noise ratio as compared to any other block matching algorithm. However this is the most computationally extensive block matching algorithm among all. A larger search window requires greater number of computations.

Three Step Search (TSS)

This is one of the earliest attempts at fast block matching algorithms. It runs as follows

1.      Start with search location at center

2.      Set step size ‘S’ = 4 and search parameter ‘p’ = 7

3.      Search 8 locations +/- S pixels around location (0,0) and the location (0,0)

4.      Pick among the 9 locations searched, the one with minimum cost function

5.      Set the new search origin to the above picked location

6.      Set the new step size as S = S/2

7.      Repeat the search procedure until S = 1

The resulting location for S=1 is the one with minimum cost function and the macro block at this location is the best match.

There is a reduction in computation by a factor of 9 in this algorithm. For p=7, while ES evaluates cost for 225 macro-blocks, TSS evaluates only for 25 macro blocks.

New Three Step Search (NTSS)

TSS uses a uniformly allocated checking pattern and is prone to miss small motions. NTSS is an improvement over TSS as it provides a center biased search scheme and has provisions to stop half way to reduce the computational cost. It was one of the first widely accepted fast algorithms and frequently used for implementing earlier standards like MPEG 1 and H.261.

Simple and Efficient Search (SES)

The idea behind TSS is that the error surface due to motion in every macro block is unimodal. A unimodal surface is a bowl shaped surface such that the weights generated by the cost function increase monotonically from the global minimum. However a unimodal surface cannot have two minimums in opposite directions and hence the 8 point fixed pattern search of TSS can be further modified to incorporate this and save computations. SES  is the extension of TSS that incorporates this assumption.

Four Step Search (4SS)

Four Step Search is an improvement over TSS in terms of lower computational cost and better peak signal-to-noise ratio. Similar to NTSS, FSS  also employs center biased searching and has a halfway stop provision.

Diamond Search (DS)

DS algorithm is exactly the same as 4SS, but the search point pattern is changed from a square to a diamond, and there is no limit on the number of steps that the algorithm can take. DS uses two different types of fixed patterns, one is Large Diamond Search Pattern (LDSP) and the other is Small Diamond Search Pattern (SDSP).

This algorithm finds the global minimum very accurately as the search pattern is neither too big nor too small. Diamond Search algorithm has a peak signal-to-noise ratio close to that of Exhaustive Search with significantly less computational expense.

Adaptive Rood Pattern Search (ARPS)

Adaptive rood pattern search (ARPS)  algorithm makes use of the fact that the general motion in a frame is usually coherent,  if the macro blocks around the current macro block moved in a particular direction then there is a high probability that the current macro block will also have a similar motion vector. This algorithm uses the motion vector of the macro block to its immediate left to predict its own motion vector.