* Title: Evaluation of search strategies for block matching

* Group members:            Email:

  Marcus Isaksson           isaksson@stanford.edu
  Joakim Jalden             jocke@stanford.edu 

* Project description:

The goal of the project is to evaluate a set of different search
strategies for block matching used for motion estimation. In particular
the following strategies will be investigated:
  * 2D coarse-to-fine search [1]
  * conjugate direction search [2]
These strategies will be compared to the optimal, but slow, full search
strategy. If time allows, we may also implement and evaluate some other
search strategies.

The following criteria will be used in the evaluation:
  * Computational complexity   
  * Efficiency, i.e. time and space requirements
  * Prediction error variance and distribution

The experiments will be carried out for integer-pel, half-pel, and
quarter-pel accuracy of motion compensation using bilinear interpolation
for sub-pel positions.

The different strategies will be implemented in Matlab, and possibly C/C++
if that is required for decent performance.

As test data for the evaluation we will use some of the video sequences
found on the ISE lab homepage. We will only be interested in continuous
sequences. i.e we will not be investigating effects due to sudden scene
changes.

* References:

[1] Jain J.R., Jain A.K., Displacement Measurement and Its Application in
Interframe Image Coding, IEEE Transactions on Communications, Vol. 29,
No. 12, December 1981

[2] Srinivasan R., Rao K.R., Predictive Coding BAsed on Efficient Motion
Estimation, IEEE Transactions on Communications, Vol. 33, No. 8, August
1985