Review of Course Computer Vision Lecture 16:Tracking

为期末考试复习做个准备。

总文章地址。

Lecture 16: Tracking

Tracking 主要就是在视频中跟踪某些东西的运动轨迹，比如关键点跟踪，单目标跟踪，多目标跟踪，变换的相机跟踪，移动的相机跟踪，多相机跟踪等等。

难度在于以下几点：

1. 需要确认哪些特征可以被跟踪。
2. 一些点会随着时间变化而改变。
3. Drift：随着时间变化，小的误差会被积累形成大的误差 (Panorama 中也有类似的问题)。
4. 点可能突然出现或者突然消失，需要动态增删。

检测的点肯定想要是比较特殊有特征性，比如 SIFT 中的特征点或者 Harris Corners 等等。同时 Optical flow 也可以帮助 Tracking。

Simple KLT tracker

步骤如下：

1. 找到好的点去跟踪，比如利用 Harris Corner。
2. 对于每个好点，计算它们在相邻图中的 motion 变换 (仿射变换等)。
3. 对于上面的那些 motion 变换，连接起来，获得了运动轨迹。
4. 每 $10/15$ 张图像，引入新的 Harris Corner 点。
5. 跟踪新和旧的 Harris Corner 点，重复 1 2 3。

2D transformations

和之前章节定义的类似，我们定义平移变换为矩阵 $\begin{pmatrix}1 & 0 & b_1\\\ 0 & 1 & b_2\end{pmatrix}$，并且定义函数
$$
W(\mathbf{x};\mathbf{p})=\begin{pmatrix}1 & 0 & b_1\\\ 0 & 1 & b_2\end{pmatrix}\begin{pmatrix}x\\ y \\ 1\end{pmatrix}.
$$
其中，$\mathbf{p}=\begin{pmatrix}b_1\\ b_2\end{pmatrix}$，$\mathbf{x}=\begin{pmatrix}x\\y\end{pmatrix}$。

可以注意到 $\frac{\partial W}{\partial \mathbf{p}}=\begin{pmatrix}1 & 0\\0 & 1\end{pmatrix}$，向量函数对向量求导的定义是 Jacobian (雅可比)，设一个向量函数为 $F(x_1,x_2,\cdots,x_n)=(y_1,y_2,\cdots,y_m)$，则
$$
\frac{\partial F(x_1,x_2,\cdots,x_n)}{\partial (x_1,x_2,\cdots,x_n)}=\begin{pmatrix}\frac{\partial y_1}{\partial x_1} & \frac{\partial y_1}{\partial x_2} & \cdots\\ \frac{\partial y_2}{\partial x_1} & \ddots & \vdots \\ \vdots & \cdots & \ddots\end{pmatrix}.
$$
定义相似变换的矩阵为 $\begin{pmatrix}a & 0 & b_1\\\ 0 & a & b_2\end{pmatrix}$，此时 $\mathbf{p}=(a,b_1,b_2)^T$，则 $\frac{\partial W}{\partial \mathbf{p}}=\begin{pmatrix}x & 1 & 0\\\ y & 0 & 1\end{pmatrix}$。

仿射变换里实际上包含了上述的所有，也有旋转等变换，其矩阵为
$$
\begin{pmatrix}a_1 & a_2 & b_1\\\ a_3 & a_4 & b_2\end{pmatrix}.
$$
于是 $\mathbf{p}=(a_1,a_2,b_1,a_3,a_4,b_2)^T$，则
$$
\frac{\partial W}{\partial \mathbf{p}}=\begin{pmatrix}x & y & 1 & 0 & 0 & 0\\\ 0 & 0 & 0 & x & y & 1\end{pmatrix}.
$$

Iterative KLT tracker

首先，用 Harris Corner Detection 找到特征点以及其位置 $\mathbf{x}=(x,y)^T$。

对于 $\mathbf{x}$，创建其初始的特征模板为 $T(\mathbf{x})$，一般选择它邻域内的像素信息。

我们想要找到下一刻中 $\mathbf{x}$ 的变换，假设其作了某种 $\mathrm{p}$ 变换，则变换后的位置应该是 $W(\mathbf{x};\mathbf{p})$。

我们肯定想要最小化这个变换的误差，即最小化
$$
\sum_{\mathbf{x}} [I(W(\mathbf{x};\mathbf{p}))-T(\mathbf{x})]^2.
$$
由于 $\mathbf{p}$ 可能很大，我们这里会选择残差连接 $\mathbf{p}$，即
$$
\sum_{\mathbf{x}} [I(W(\mathbf{x};\mathbf{p_0+\Delta p}))-T(\mathbf{x})]^2.
$$
一般我们会初始化 $\mathbf{p_0}$ 为我们最好的猜测结果，然后计算 $\mathbf{\Delta p}$。

注意到 $\mathbf{\Delta p}$ 会是小量，考虑 Taylor 展开，有
$$
\sum_{\mathbf{x}} [I(W(\mathbf{x};\mathbf{p_0+\Delta p}))-T(\mathbf{x})]^2\\
\approx\sum_{\mathbf{x}} [I(W(\mathbf{x};\mathbf{p_0})+\frac{\partial W}{\partial \mathbf{p}}\mathbf{\Delta p})-T(\mathbf{x})]^2\\
\approx\sum_{\mathbf{x}} [I(W(\mathbf{x};\mathbf{p_0}))+\nabla I \frac{\partial W}{\partial \mathbf{p}}\mathbf{\Delta p}-T(\mathbf{x})]^2.
$$
此时的计算只是二次多项式，会容易很多。

求最小值，于是求导，即
$$
\arg\min \sum_{\mathbf{x}} [I(W(\mathbf{x};\mathbf{p_0}))+\nabla I \frac{\partial W}{\partial \mathbf{p}}\mathbf{\Delta p}-T(\mathbf{x})]^2\\
\implies \sum_{\mathbf{x}} (\nabla I \frac{\partial W}{\partial \mathbf{p}})^T[I(W(\mathbf{x};\mathbf{p_0}))+\nabla I \frac{\partial W}{\partial \mathbf{p}}\mathbf{\Delta p}-T(\mathbf{x})]=0\\
\implies \mathbf{\Delta p}=H^{-1}\sum_{\mathbf{x}} (\nabla I \frac{\partial W}{\partial \mathbf{p}})^T[-I(W(\mathbf{x};\mathbf{p_0}))+T(\mathbf{x})].
$$
其中 $H=\sum_{\mathbf{x}} (\nabla I \frac{\partial W}{\partial \mathbf{p}})^T(\nabla I \frac{\partial W}{\partial \mathbf{p}})$，要求 $H$ 必须要可逆。

如果是平移变换，$H$ 的表达式是我们熟知的类似 Hessian 矩阵，在 Harris Corner 以及其他地方都出现过，即
$$
H=\sum_{\mathbf{x}} \begin{pmatrix}I_x^2 & I_xI_y\\I_xI_y & I_y^2\end{pmatrix}.
$$

如果是最广泛的仿射变换，矩阵就比较巨大了。

在这里，我们给出 KLT tracker 的步骤，在 Harris Detection 检测了特征点后。

1. 初始化 $\mathbf{p_0}$。
2. 对于每个特征点 $\mathbf{x}$，计算初始模板 $T(\mathbf{x})$。
3. 对每个特征点 $\mathbf{x}$，计算 $W(\mathbf{x};\mathbf{p_0})$。
4. 测量误差 $I(W(\mathbf{x};\mathbf{p_0}))-T(\mathbf{x})$。
5. 计算 $I$ 的梯度 $\nabla I=(I_x,I_y)$。
6. 计算 Jacobian 矩阵 $\frac{\partial W}{\partial \mathbf{p}}$。
7. 计算 $\nabla I\frac{\partial W}{\partial \mathbf{p}}$。
8. 计算 Hessian 矩阵的逆矩阵 $H^{-1}$。
9. 根据前面的公式，算出 $\mathbf{\Delta p}$。
10. 更新参数 $\mathbf{p_0}\leftarrow \mathbf{p_0+\Delta p}$。
11. 重复 3~10，直到 $\mathrm{\Delta p}$ 足够小。

这样我们能获得相邻两个图像之间的轨迹，对于多个图像，我们对每 $15\sim 20$ 个图像做一遍 Harris Detection。

难点：

1. 设立初始模板 $T(\mathbf{x})$ 的邻域大小，太小不仅会纳入噪声，而且会错过大幅度的 motion；太大可能会遇到 occlusion (遮挡)，一般选择 $15\times 15$ 或 $31\times 31$。
2. 求 $T(\mathbf{x})$ 需要某种窗函数，比如汉明窗，高斯窗等。