Homework 3 - Optical Flow Estimation: Template Matching, Lucas-Kanade Method and Affine Motion
Homework 3 - Optical Flow Estimation
NOTE: For this homework it is required that you use LaTeX to write all equations and answers and turn in the compiled PDF file for submission.
Given two 6 × 6 images I1 and I2 shown in Figure 1, we want to calculate the optical flow between the image pair such that
I2 (x + u(x, y), y + v(x, y)) ≈ I1 (x, y) (1)
where (u(x, y), v(x, y)) is the displacement for the pixel with coordinate (x, y). The results for optical flow estimation are the two maps u and v whose size is the same as the input images I1 and I2 . Note: 1) Zero-padding is used in this homework. 2) The (x, y) coordinate system has the origin at the top-left corner of the image with the x-axis pointing rightward and the y-axis pointing downward.
0 0 0 0 0 0 0 1 1 1 0 0 0 1 3 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 (a) Image I1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 3 1 0 0 0 1 2 2 0 (b) Image I2
Figure 1: The image pair for optical flow estimation
1. Template Matching (2 points)
1 1 1 1 3 1 1 1 1
Figure 2: Template from the first image I1
We are interested in estimating the displacement for the pixel with coordinate (2, 2), which is on the 3rd row and 3rd column in I1 using technique called Template Matching. To start, we first crop a 3 × 3 region centering at (2, 2) in image I1 as the template shown in Figure 2. Then we slide this 3 × 3 template to overlay its center pixel with each of the pixel in I2 to calculate the mean squared error (MSE) between them as defined in Equation 3. This difference between the template and all pixels in I2 will then be used to create a difference map for the template. Here, we use T to denote the template, and we define its origin to be at the center such that
T (0, 0) = 3 (2)
As for template matching, we use mean squared error (MSE) for the difference. For a location (x′ , y′ ) in the second image I2 , the difference is calculated by
DT (x′ , y′ ) =121 1T (m, n) − I2 (x′ + m, y′ + n)∑∑9 m=−1 n=−1 (3)
With the resulting difference map, we can then find the displacement (u, v) by checking for the pixel in I2 with the minimum MSE.
Question 1.1: Please fill in the difference map for template T shown in Figure 3. Then find the pixel location with the lowest MSE in I2 and calculate the (u, v) defined in Equation 1 for pixel (x = 2, y = 2) in image I1 .
Figure 3: Difference map for template T
2. Lucas-Kanade Method (4 points)
The second technique to estimate optical flow (u, v) is called Lucas-Kanade method. We are still assuming the searching window has a size of 3 × 3. Kernels for calculating gradient Jx and Jy are as follows fx = [1, 0, −1] fy = [1, 0, −1]T (4)
Question 2.1: Please give the equation for estimating the displacement for (x = 2, y = 2) in image I1 and calculate the displacement (u, v) for the location.
Question 2.2: If window size increases from 3 × 3 to 5 × 5, what is the equation for estimating the displacement for (x = 2, y = 2) in image I1 ? Compare the displacement estimation from both window sizes and explain the reason for the difference.
3. Affine Motion (4 points)
Suppose that displacement of each pixel satisfies an affine model in Equation 5.
Then as for optical flow estimation, we only need to estimate the parameters for the affine model. We let each pixel contribute equally to the parameter estimation. That is to say: 1) all the pixels are involved in the estimation; 2) the weight for each pixel equals to 1. Question 3.1: Please derive a closed-form solution for estimating the parameters. (Recall the derivation of the linear models for estimating the displacement of each pixel.)
Question 3.2: Given two images I1 and I2 in Figure 1, please use your derivation to estimate the parameters of their affine model. (Give the equation and the numeric values of the parameters.)
