Wednesday, December 03, 2008

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


cross search

one at a time

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

No comments:

Post a Comment