CS4551 Spring 2020 HW #3

1

CS4551 Multimedia Software Systems

Homework 3 (10%) – Block-based Motion Compensation

, .

• What to turn in:

o Submit source code with necessary files for “compile and run”.

o Do NOT submit data files.

o You MUST provide a readme.txt file containing all information to help with the grading process.

• If your program produces any compile errors, you will receive 0 automatically no matter how close your 

program is to the solution.

• Programming requirements:

o You are not allowed to use any Java built-in image class methods, library, or tools to complete this 

homework.

o Do not create one mega-size main class.

o Do not change any given methods of MImage class nor create a new class that duplicates MImage 

class. Treat MImage as a part of imported library.

o Test your program with all test data.

o If you do not meet any of the requirements above, you will receive a significant reduction.

Download the test dataset (video frames of 200 PPM images, Walk_001.ppm ~ Walk_200.ppm) from CSNS. Before 

programming, check the images using Irfanview.

0. What your program should do

Name your main application CS4551_[YourLastName].java (e.g. CS4551_Doe.java) and expand the given 

template program to perform the following tasks.

Receive the input file as command line arguments.

java CS4551_Doe

Display the following main menu to the user and receive the user’s input.

Main Menu-----------------------------------

1. Block-based Motion Compensation

2. Fast Motion Compensation

3. Quit 

Please enter the task number [1-3]:

After performing a selected task, go back to display the menu again.

CS4551 Spring 2020 HW #3 rev.

2

1. Task 1 – Block-based Motion Compensation (80 pts) 

Write a routine(method) that compensates motions between two images (one is the target image and the other 

one is the reference image). Receive two images as parameters. Make the routine perform the followings:

• Receive an integer 𝑛 for the macro block size from the user. 𝑛 must be 8, 16, or 24.

• Receive an integer 𝑝 for search window from the user. 𝑝 must be 2, 4, 8, 12, or 16.

• Divide the target image into a set of 𝑛 × 𝑛 macro blocks.

• For each target macro block:

o Estimate one motion vector by finding the best matched macro block (a.k.a. predicted block) in the 

reference image using 𝑝 for the search area size and MSD (Mean Square Difference) for the 

matching criteria. When you compute MSD, use Gray values:

Gray = round(0.299 * R + 0.587 * G + 0.114 * B)

o After finding the best matched block, compute the motion vector and the error block

▪ Compute the motion vector using

𝑑 = (𝑑𝑥, 𝑑𝑦) = (𝑡𝑥,𝑡𝑦) − (𝑟𝑥, 𝑟𝑦)

where (𝑡𝑥,𝑡𝑦) is the upper left corner location of the target block and (𝑟𝑥, 𝑟𝑦) is the upper left 

corner location of the best matched block location in the reference frame.

▪ Compute the error block (a.k.a. residual block) consisting of pixel differences (absolute values) 

between the target block and the best matched block (a.k.a. predicted block).

𝑒 = |𝑝𝑖𝑥𝑒𝑙_𝑖𝑛_𝑡𝑎𝑔𝑟𝑒_𝑏𝑙𝑜𝑐𝑘 − 𝑐𝑜𝑟𝑟𝑒𝑠𝑝𝑜𝑛𝑑𝑖𝑛𝑔_𝑝𝑖𝑥𝑒𝑙_𝑖𝑛_𝑚𝑎𝑡𝑐ℎ𝑒𝑑_𝑏𝑙𝑜𝑐𝑘|

• Outputs

o Display and Save your error (or residual) image. Your error image is a composition of all error 

blocks. Scale error values to range [0, 255]. In order to do so, compute 𝑀𝐼𝑁𝑒𝑟𝑟𝑜𝑟 and 𝑀𝐴𝑋𝑒𝑟𝑟𝑜𝑟

and map values from [𝑀𝐼𝑁𝑒𝑟𝑟𝑜𝑟, 𝑀𝐴𝑋𝑒𝑟𝑟𝑜𝑟] to [0, 255] using

𝑆𝑐𝑎𝑙𝑒𝑑𝐸𝑟𝑟𝑜𝑟 =

𝑒 − 𝑀𝐼𝑁𝑒𝑟𝑟𝑜𝑟

𝑀𝐴𝑋𝑒𝑟𝑟𝑜𝑟 − 𝑀𝐼𝑁𝑒𝑟𝑟𝑜𝑟

× 255

o Save the estimated motion vectors to the “mv.txt”. It should have motion vectors of all target blocks. 

Refer to the, refer sample mv.txt file.

CS4551 Spring 2020 HW #3 rev.

3

• Extra credit (20 pts) Implement matching in the half-pixel accuracy:

o Use the best matched block at full-pel position as the starting point, shown as the red dot in the 

figure below.

o Check the neighboring candidate blocks in half-pel positions, which are shown as the blue diamonds.

o Select the block with the least MSD among the 8 half-pel blocks and one best full-pel block as the 

final matched block in the half-pel block-based motion compensation.

2. Task 2 – Fast Motion Compensation (20 pts)

Implement logarithmic search for matching. Provide an additional menu option for this. Display and save motion 

vectors and a residual image. Also, display the number of matches performed given 𝑝.

Sample results will be posted on CSNS.