18-899 Project: Search Algorithms for
Block-Matching in Motion Estimation

By Mohamed Alkanhal and Deepak Turaja


Block matching is the most popular one for the motion estimation. It's used in H.261, H.263 and MPEG-1 codecs. The best matched block is usually found by using the pixel-domain search methods. Several search strategies are in the literature such as full search (FS), three step search(TSS) , new three step search(NTSS), fast three step search (FTSS), fourstep search (4SS) and spiral search algorithm (SSA). Here, we are going to analyse and evaluate the most important block matching algorithms. The quality and speed will be considered in our analysis.

Project plan:

1. Feb. 18 - Feb. 25: literature survey.
2. Feb. 26 - Mar. 13: Implement and evaluate some search algorithms
3. Mar. 13 - May 8 :

  • a. Continue the the implementation and evaluation

  • b. Try to improve some of these algorithm