Motion Vector Search

• C(x+k,y+i) - pixels in the macro block with upper left corner (x,y) in the Target.

  R(X+i+k,y+j+l) - pixels in the macro block with upper left corner (x+i,y+j) in the Reference.

  Cost function is:

  

  Where MAE stands for Mean Absolute Error.

• Goal is to find a vector (u, v) such that MAE (u, v) is minimum

• Full Search Method:

  1.

  Search the whole $\left[-p,p\right]$ searching region.

  2.

  Cost is:

  

  operations,

  assuming that each pixel comparison needs 3 operations (Subtraction, Absolute value, Addition).

• Two-Dimensional Logarithmic Search:

  Similar to binary search. MAE function is initially computed within a window of $\left[-p/2, p/2 \right]$ at nine locations as shown in the figure.

  Repeat until the size of the search region is one pixel wide:

  1.

  Find one of the nine locations that yields the minimum MAE.

  2.

  Form a new searching region with half of the previous size and centered at the location found in step 1.

  

• Hierarchical Motion Estimation:

  

  1.

  Form several low resolution version of the target and reference pictures

  2.

  Find the best match motion vector in the lowest resolution version.

  3.

  Modify the motion vector level by level when going up

• Performance comparison:

       -----------------------------------------------------------------
  	Search Method          Operation for 720x480 at 30 fps
  				 p = 15                 p=7
      -----------------------------------------------------------------
        Full Search               29.89 GOPS            6.99 GOPS
        Logarithmic                1.02 GOPS          777.60 MOPS
        Hierarchical             507.38 MOPS          398.52 MOPS
      -----------------------------------------------------------------