Project 1: Block Matching Algorithm

In this project, we will implement three Block Marching Algorithms (BMA). The third method is particularly important as it will compute faster than the first two methods.

NOTE: Submit your program source code on GitHub Classroom, and a project report on Gradescope.

Part I - Write a C/C++ or Python program for implementing an exhaustive block matching algorithm (EBMA) with integer-pel accuracy

• Program inputs: video sequence, block size, search range
• Program outputs: estimated motion field
• Assignment deliverables:
  • Program source code
  • Project report describing your findings. It must include the following items:
    1. Plot of estimated motion field for two images from video sequence
    2. The predicted image and the prediction error image
    3. The PSNR of the predicted frame relative to its original
• Experiments such as:
  1. Impact of different search range
  2. Impact of different predicted-block size ($16 \times 16$ as starting point)

Use the YUV videos provided at HERE. Since block size is small, motion compensation can be slow to process. Choose two frames that have sufficient motion between them so that it's easy to observe the effect of inaccurate motion estimation. If necessary, choose frame that have several intervening frames.

Part II - Write a C/C++ or Python program for implementing an exhaustive block matching algorithm (EBMA) with half-pel accuracy

• Program inputs: video sequence, block size, search range
• Program outputs: estimated motion field
• Assignment deliverables:
  • Program source code
  • Project report describing your findings. It must include the following items:
    1. Plot of estimated motion field for two images from video sequence
    2. The predicted image and the prediction error image
    3. The PSNR of the predicted frame relative to its original
    4. Compare the predicted image and its PSNR with results from integer-pel accuracy
    5. Compare execution time relative to results from integer-pel accuracy
• Experiments such as:
  1. Impact of different search range
  2. Impact of different predicted-block size ($16 \times 16$ as starting point)

Part III - Write a C/C++ or Python program for implementing hierarchical block matching algorithm (HBMA}

• Program inputs: video sequence, block size, search range
• Program outputs: estimated motion field
• Assignment deliverables:
  • Program source code
  • Project report describing your findings. It must include the following items:
    1. Plot of estimated motion field for two images from video sequence
    2. The predicted image and the prediction error image
    3. The PSNR of the predicted frame relative to its original
    4. Compare the predicted image and the PSNR of the predicted image with results from integer-pel and half-pel accuracy
    5. Compare execution time relative to results from integer- and half-pel accuracy
• Experiments such as:
  1. Impact of different search range
  2. Impact of different predicted-block size ($16 \times 16$ as starting point)

Bonus Problem (20 points in addition to the 100 points of the project)

Assuming the motion between two frames can be approximated by an affine mapping. Determine the affine parameters using the indirect method. First, apply the HBMA or EBMA algorithm you implemented, to determine a block-based motion field between the two frames. Then determine the affine parameters using the least-squares method of Equation (6.7.3) in the textbook (Wang etc., Video Processing and Communications). Show the predicted image based on the affine parameters and the associated prediction error (in terms of PSNR) (as above). Compare the results to those obtained with the starting block-based motion estimation.

Compare the results when applied to 2 frames experiencing primarily camera motion, as well as to 2 frames experiencing no camera motion. Discuss the results. Note that for debugging purposes, it may be useful to artificially generate a pair of frames, where the second is generated by applying an affine mapping to the first.