Lab#1 Solution

6.1 Key Information




Deadline: (1) Submission should be made before 6am on September 10 (Monday in Week7).
(2) Demonstration should be made in the lab session on week7.










Submission: All source code should be submitted as a zip file via Canvas and counts for 5% of your total assessment. Do not submit your output video file. Please provide a README file within the zip file, including the instructions to run your code.









Demonstration: You are allowed to use any video to demonstrate your code. Please have your corresponding output video ready for the demonstration. You are required to provide a working live demo to show your work to your tutor during the lab session on Week 7.









6.2 Demonstration Rules




Make sure you can demonstrate your program in the reasonable time. You can either use your laptop or the computer at the lab. Please test your program before coming to the demonstration lab.






You will be required to explain the implementation of your code to the tutor.









If you can not finish all the requirements, you should provide a live demo for the workable parts.



22 Chapter 6. LabSubmission1 Specification







6.3 Motion estimation with Macroblock matching (Lab Submission 1)










(a) Illustration of the block matching













Example extracted motion vectors. Please note that in your lab submission, you do not need to draw arrows. Highlight the pixels with high magnitude would be sufficient.



Figure 6.1: The illustration of block matching algorithm and the extracted optical flows.







This task is to perform the motion estimation with macroblock matching. The basic premise of motion estimation is that in most cases, consecutive video frames will be similar except for changes induced by objects moving within the frames. The basic idea of motion estimation is to define grids of block regions on two adjacent frames and find the displacement vector (a 2D Cartesian vector in 2D videos) between the matched blocks. To describe the meta-algorithm step by step:




Iterate the video frames Fi of size fx ⇥ fy; Define a grid block size K ⇥ K, K is preferred to be odd to make it easier to determine the central coordinate of each grid block. Each frame Fi results in fx fy/K2 grid blocks overall.



For each grid block Bi at (x, y) in frame Fi, search for the grid block B0i+1 at (x0, y0) in Fi+1



6.3 Motion estimation with Macroblock matching (Lab Submission 1) 23







with the minimum sum squared distance (SSD) between Bi and B0i+1. SSD can be computed as







SSD(Bi, Bi0+1) =
ÂÂÂ(Bi(bx, by, bc)
−
Bi+1(bx, by, bc))2
(6.1)
s
bx by bc







The displacement from Bi to B0i+1 can be represented as (x0 − x, y0 − y), a 2-D vector. To speed up, you can search the neighbour blocks only within a certain radius.




Save the displacement vectors of frame Fi in a 3D matrix of size fx/K ⇥ fy/K ⇥ 2 or two 2D matrices with size fx/K ⇥ fy/K each.



Visualise the displacement fields with a 2D image with the same size as frame Fi. The same magnitude value is assigned to all the pixels within the region covered by a single grid block. Alternatively you can draw arrows to represent the extracted displacement fields.
Visualise the boundary of the object with large displacement. Hint : the dilation or erosion might be helpful.



Repeat step 1-5 for all frames



For more details of in-depth understanding of the video estimation algorithm, you may refer to http://web.stanford.edu/class/ee398a/handouts/lectures/EE398a_MotionEstimation_ 2012.pdf









For a faster solution of estimating optical flow with Lucas-Kanade method please see http: //research.ijcaonline.org/volume61/number10/pxc3884611.pdf



and a Matlab solution at http://www.cs.ucf.edu/~gvaca/REU2013/p4_opticalFlow. pdf




Please note for the lab submission you are not required to use the Lucas-Kanade method.