# Homework 8

This assignment covers Lukas-Kanade tracking method. Please hand in motion.py and this notebook file to Gradescope.

## 0. Displaying Video

We have done some cool stuff with static images in past assignemnts. Now, let’s turn our attention to videos! For this assignment, the videos are provided as time series of images. We also provide utility functions to load the image frames and visualize them as a short video clip.

Note: You may need to install video codec like FFmpeg. For Linux/Mac, you will be able to install ffmpeg using apt-get or brew. For Windows, you can find the installation instructions here.

## 1. Lucas-Kanade Method for Optical Flow

### 1.1 Deriving optical flow equation

Optical flow methods are used to estimate motion at each pixel location in two consecutive image frames. The optical flow equation at a spatio-temporal point $\mathbf{p}=(x, y, t)$ is given by:

$$I_x({\mathbf{p}})v_{x} + I_y({\mathbf{p}})v_{y} + I_t({\mathbf{p}}) = 0$$

,where $I_x$, $I_y$ and $I_t$ are partial derivatives of pixel intensity $I$, and $v_{x}={\Delta x}/{\Delta t}$ and $v_{x}={\Delta x}/{\Delta t}$ are flow vectors.

Let us derive the equation in order to understand what it actually means. First, we make a reasonable assumption (a.k.a. brightness constancy) that the pixel intensity of a moving point stays the same between two consecutive frames with small time difference. Consider pixel intensity $I(x, y, t)$ of a point $(x, y)$ in the first frame $t$. Suppose that the point has moved to $(x+\Delta{x}, y+\Delta{y})$ after $\Delta{t}$. According to the brightness constancy constraint, we can relate intensities of the point in the two frames using the following equation:

$$I(x,y,t)=I(x+\Delta{x},y+\Delta{y},t+\Delta{t})$$
• a. Derive the optical flow equation from the brightness constancy equation. Clearly state any assumption you make during derivation.

• b. Can the optical flow equation be solved given two consecutive frames without further assumption? Which values can be computed directly given two consecutive frames? Which values cannot be computed without additional information?

a.

$$I(x,y,t)=I(x+\Delta{x},y+\Delta{y},t+\Delta{t})$$

$$I(x+\Delta{x},y+\Delta{y},t+\Delta{t}) \approx I(x,y,t) + I_x\Delta{x} + I_y\Delta{y} + I_t\Delta{t}$$

$$I_x\Delta{x} + I_y\Delta{y} + I_t\Delta{t} = 0$$

$$I_x \frac{\Delta{x}}{\Delta{t}} + I_y\frac{\Delta{y}}{\Delta{t}} + I_t= 0$$

$$I_x({\mathbf{p}})v_{x} + I_y({\mathbf{p}})v_{y} + I_t({\mathbf{p}}) = 0$$

b.

### 1.2 Overview of Lucas-Kanade method

The Lucas–Kanade method assumes that the motion of the image contents between two frames is approximately constant within a neighborhood of the point $p$ under consideration (spatial coherence).

Consider a neighborhood of $p$, $N(p)={p_1,…,p_n}$ (e.g. 3x3 window around $p$). According to the optical flow equation and spatial coherence assumption, the following should be satisfied:

For every $p_i \in N(p)$,

$$I_{x}(p_i)v_x + I_{y}(p_i)v_y = -I_{t}(p_i)$$

These equations can be written in matrix form $Av=b$, where

$$A = \begin{bmatrix} I_{x}(p_1) & I_{y}(p_1)\\ I_{x}(p_2) & I_{y}(p_2)\\ \vdots & \vdots\\ I_{x}(p_n) & I_{y}(p_n) \end{bmatrix} \quad v = \begin{bmatrix} v_{x}\\ v_{y} \end{bmatrix} \quad b = \begin{bmatrix} -I_{t}(p_1)\\ -I_{t}(p_2)\\ \vdots\\ -I_{t}(p_n) \end{bmatrix}$$

Note that this linear system may not have solution for $v$ as it is usually over-determined. Instead, Lucas-Kanade method estimates the flow vector by solving the least-squares problem, $A^{T}Av=A^{T}b$.

• a. What is the condition for this equation to be solvable?
• b. Reason about why Harris corners might be good features to track using Lucas-Kanade method.

• $A^TA$可逆
• 因为噪声的存在，$A^TA$不能太小
• $A^TA$的特征值$λ_1$和$λ_2$都不能太小
• $A^TA$应当是well-conditioned
• $\frac{λ_1}{λ_2}$不能太大，（$λ_1$是较大的特征值）

• 较大的特征值对应的特征向量表示强度变化最快的方向
• 另外一个特征向量则与它正交

### 1.3 Implementation of Lucas-Kanade method

In this section, we are going to implement basic Lucas-Kanade method for feature tracking. In order to do so, we first need to find keypoints to track. Harris corner detector is commonly used to initialize the keypoints to track with Lucas-Kanade method. For this assignment, we are going to use skimage implementation of Harris corner detector.

skimage中提供了Harris角点检测的实现。

skimage中的Harris角点检测可以参考：Programming Computer Vision with Python （学习笔记九）

Implement function lucas_kanade in motion.py and run the code cell below. You will be able to see small arrows pointing towards the directions where keypoints are moving.

We can estimate the position of the keypoints in the next frame by adding the flow vectors to the keypoints.

### 1.4 Feature Tracking in multiple frames

Now we can use Lucas-Kanade method to track keypoints across multiple frames. The idea is simple: compute flow vectors at keypoints in $i$-th frame, and add the flow vectors to the points to keep track of the points in $i+1$-th frame. We have provided the function track_features for you. First, run the code cell below. You will notice that some of the points just drift away and are not tracked very well.

Instead of keeping these ‘bad’ tracks, we would want to somehow declare some points are ‘lost’ and just discard them. One simple way to is to compare the patches around tracked points in two subsequent frames. If the patch around a point is NOT similar to the patch around the corresponding point in the next frame, then we declare the point to be lost. Here, we are going to use mean squared error between two normalized patches as the criterion for lost tracks.

Implement compute_error in motion.py, and re-run the code cell below. You will see many of the points disappearing in later frames.

## 2. Pyramidal Lucas-Kanade Feature Tracker

In this section, we are going to implement a simpler version of the method described in “Pyramidal Implementation of the Lucas Kanade Feature Tracker”.

TLD算法学习之L-K光流法理论篇二

One limitation of the naive Lucas-Kanade method is that it cannot track large motions between frames. You might have noticed that the resulting flow vectors (blue arrows) in the previous section are too small that the tracked keypoints are slightly off from where they should be. In order to address this problem, we can iteratively refine the estimated optical flow vectors. Below is the step-by-step description of the algorithm:

Let $p=\begin{bmatrix}p_x & p_y \end{bmatrix}^T$ be a point on frame $I$. The goal is to find flow vector $v=\begin{bmatrix}v_x & v_y \end{bmatrix}^T$ such that $p+v$ is the corresponding point of $p$ on the next frame $J$.

• Initialize flow vector:
$$v= \begin{bmatrix} 0\0 \end{bmatrix}$$

$$G=\sum_{x=p_x-w}^{p_x+w}\sum_{y=p_y-w}^{p_y+w} \begin{bmatrix} I_{x}^2(x,y) & I_{x}(x,y)I_{y}(x,y)\ I_{x}(x,y)I_{y}(x,y) & I_{y}^2(x,y) \end{bmatrix}$$

• for $k=1$ to $K$

• Compute temporal difference: $\delta I_k(x, y) = I(x,y)-J(x+g_x+v_x, y+g_y+v_y)$
• Compute image mismatch vector:
$$b_k=\sum_{x=p_x-w}^{p_x+w}\sum_{y=p_y-w}^{p_y+w} \begin{bmatrix} \delta I_k(x, y)I_x(x,y)\ \delta I_k(x, y)I_y(x,y) \end{bmatrix}$$
• Compute optical flow: $v^k=G^{-1}b_k$
• Update flow vector for next iteration: $v := v + v^k$
• Return $v$

Implement iterative_lucas_kanade method in motion.py and run the code cell below. You should be able to see slightly longer arrows in the visualization.