Search methods in motion estimation

[update: Sep. 14, 2010]
Search algorithms:

• Three-step search (3SS): based on coarse-find approach. The first step size is half of maximum motion displacement.
• 2D-logarithmic search (2DLOG):
• Orthogonal search algorithm (OSA):
• Cross search algorithm (CSA)
• Conjugate direction search algorithm (CDS): 3 steps: search x direction, search y, search in diagonal direction.
• Full search (exhaustive search)

Matching algorithm:

• Cross Correlation Function (CCF, or Normalized CCF)
• Mean Square Error (MSE)
• Mean Absolute Error (MAE)
• Sum of Absolute Difference (SAD) -- this one is commonly used (simplicity in hardware implementation) #

Full search: raster order

Full search: spiral order

Fast search: three-step


Logarithmic


cross search



one at a time


nearest neighbours: this one is used in H.263 and MPEG4