[人工智能][多目标跟踪学习笔记]光流法

光流法是进行目标跟踪的传统方法, 参照视频B站进行学习, 做的笔记.

1. 运动场(Motion Field)与光流(Optical Flow)

光流, 顾名思义就是光的流动. 对于图像来说, 什么是光的流动呢? 想象一下摄像头是运动的(目标是运动的也一样), 目标的运动变化其实就是"像素点"的"移动", 因此称为光流, 如下图所示:

如上图所示, 假如摄像头是移动的, 那么这棵树的亮度模式就会发生变化, 那么发生变化的这个趋势实际上就代表了目标的运动.

问题1: 那么, 我们认为的所谓像素点亮度模式的变化和目标真实的运动之间有什么关系呢?

我们把目标真实物理运动在某个观测上的投影(Projection)称为运动场(Motion Field), 例如下图: 目标在往左上方移动, 它在sensor上的投影(也就是我们的观测)也有一个对应的移动方向, 也就是向下移动.

? \space ?
问题2: 运动场和光流是等价的吗?

答案是否定的. 请看以下几种情况:

1. 有运动场 无光流 或 有光流, 无运动场

下图的左边, 假设球体是旋转的, 但是光源不动. 是有运动场, 无光流的情形.右边反之, 球体是不动的, 但光源是运动的.

? \space ?

2. 光流和运动场并不相等
   这个例子更直接. 例如理发店门口的彩灯, 我们知道真实的物理运动是水平向右的, 然而, 如果关注像素亮度的变化, 则光流的方向是向下的, 二者正好垂直.

? \space ?

2. 光流约束方程

我们如何更好地通过光流来估计运动呢?

首先我们要做一些假设, 这样问题才可以进行下去. 我们考虑以下连续的两帧图片:

这张图片中鹰是运动的目标. 我们如果关注其中一个像素$(x,y)$, 假定下一帧的位置在$(x+\delta x,y+\delta y)$, 我们可以得到该像素点的速度(也就是亮度运动模式, 理论上的光流方向):

$$(u,v)=(\delta x/\delta t,\delta y/\delta t)$$

假设1 两帧间的对应像素亮度不变

我们认为$\delta t$足够小, 以至于不会使我们关心的像素点在两帧之间产生亮度变化, 假设亮度用$I(?)$表示， 有:
$$I(x,y,t)=I(x+\delta x,y+\delta y,t+\delta t)$$

我们对等号右边进行多元函数的Taylor展开, 并忽略二次项及以上的高阶项, 有:
$$I(x+\delta x,y+\delta y,t+\delta t)=I(x,y,t)+\frac{?I}{?x}\delta x+\frac{?I}{?y}\delta y+\frac{?I}{?t}\delta t$$

联立上两式, 有:
$$\frac{?I}{?x}\delta x+\frac{?I}{?y}\delta y+\frac{?I}{?t}\delta t=0$$

令$\delta t\to 0$. 两边同除$\delta t$, 有:

$$\frac{?I}{?x}\frac{\delta x}{\delta t}+\frac{?I}{?y}\frac{\delta y}{\delta t}+\frac{?I}{?t}=0$$

式中的$\frac{\delta x}{\delta t},\frac{\delta y}{\delta t}$分别为光流真值(速度)$u,v$, 故将上式写为:

$$I_{x}u+I_{y}v+I_t=0$$

以上就是光流约束方程.

求解上式中$I_x,I_y,I_t$的方式与图像处理中求梯度的方式类似, 固定一个变量求其余变量得到差, 例如$I_x$按如下计算:

? \space ?
好, 现在我们知道了$I_x,I_y,I_t$, 如果讨论$u,v$平面, 则式$$I_{x}u+I_{y}v+I_t=0$$
规定了平面上的一条直线. 可是$u,v$都是变量, 我们无法获得准确值.

具体地, 如上图, 假设光流真值为$\mathbf{u}=(u,v)$, 我们将其分解为垂直直线方向与平行直线方向
$\mathbf{u}={\mathbf{u}}_{\mathbf{n}}+{\mathbf{u}}_{\mathbf{p}}$.

根据几何知识, 很快求得:

$${\mathbf{u}}_{\mathbf{n}}=\frac{|I_t|}{\sqrt{I_x^2+I_y^2}}(I_x,I_y)$$

然而, ${\mathbf{u}}_{\mathbf{p}}$我们不知道, 因此需要更多的约束条件.

3. Lucas Kanade算法

接上文, 我们需要更多的约束条件. Lucas Kanade算法所做的假设是:

假设2 假定对于每个像素, 运动场与光流和其邻域中的像素均相同

假设某像素的某邻域为$W$, 大小为$n\times n$的矩形, 则对于$W$中的每个像素$(k,l)\in W$, 光流都相同, 因此有:
$$I_x(k,l)u+I_y(k,l)v+I_t(k,l)=0,(k,l)\in W$$
上面是$n^2$个方程, 我们写为矩阵形式:
$$?\begin{array}{cc}{I}_x(1,1)& I_y(1,1)\\ ...& ...\\ I_x(n,n)& I_y(n,n)\end{array}?\left[\begin{array}{c}u\\ v\end{array}\right]=?\begin{array}{c}?I_t(1,1)\\ ...\\ ?I_t(n,n)\end{array}?$$

记为:
$$\mathbf{A}\mathbf{u}=\mathbf{B},A\in {\mathbb{R}}^{n^2\times 2},u=[u,v{]}^T,B\in {\mathbb{R}}^{n^2\times 1}$$

$n^2$这个数有点大, 为了计算方便, 我们将方程写为:

$$({\mathbf{A}}^{\mathbf{T}}\mathbf{A})\mathbf{u}={\mathbf{A}}^{\mathbf{T}}\mathbf{B}$$
其中${\mathbf{A}}^{\mathbf{T}}\mathbf{A}\in {\mathbb{R}}^{2\times 2}$. 假设${\mathbf{A}}^{\mathbf{T}}\mathbf{A}$可逆, 有:
$$\mathbf{u}=({\mathbf{A}}^{\mathbf{T}}\mathbf{A}{)}^{?1}{\mathbf{A}}^{\mathbf{T}}\mathbf{B}$$

因此就求解出光流了. 然而, LK算法以上的求解方式也有其局限性, 必须要求:

1. $A^{T}A$可逆.
2. $A^{T}A$必须是well-conditioned. 所谓well-conditioned, 就是指其两个特征值${\lambda }_1,{\lambda }_2$满足:
   二者都不要太接近0, 且
   ${\lambda }_1\ge {\lambda }_2$且
   不可以${\lambda }_1>>{\lambda }_2$.

weil-conditioned的意义是, 如果特征值都太小, 则求解出的$u$也很小, 结果不可靠.
如果两个特征值相差很大, 则并不能确保具体的运动方向.

4. 粗糙到精细的光流估计(光流金字塔, Coarse to fine estimation)

LK算法有一个先验假设, 即$\delta t$足够小, 也就是小运动假设. 但如果运动范围很大的时候, 怎么做呢?

我们可以降低图片的分辨率, 例如通过池化的方式, 这样原来的大运动就会变成小运动. 如下图所示.

转化成小运动之后, 我们就可以利用之前的算法求解光流了.

假定我们有四种分辨率, 从低到高是1, 2, 3, 4. 在1分辨率上, 我们利用小运动的估计来计算光流, 假设结果为$(u,v{)}^0$.

这样, 我们在2分辨率上利用1分辨率上计算出的光流, 产生一个新的图像(类似于插帧). 这个图像会更接近原始分辨率的运动, 但不精确. 这一步叫做"Wrap".

因此, 同样地我们对插帧后的2分辨率再计算光流, 得到插帧到最终图像的光流变化$\Delta (u,v{)}^1$. 因此此时我们可以得到更精确的光流估计$(u,v{)}^1=(u,v{)}^0+\Delta (u,v{)}^1$. 这一步叫做"Plus".

再对3分辨率上应用此光流插帧, 一直这样下去. 如图所示:

因此, 我们就从粗糙分辨率的小运动, 一步一步估计到了精细分辨率的大运动, 总之是一个Warp+Plus的迭代过程.