MeanShift 视频目标追踪

简介

在视频的目标追踪算法中，可以分为两类，一类是卡尔曼滤波、MeanShift、ASMS这种根据相似性，从前一个帧计算当前帧目标的位置；另外一类是使用分类算法，当然也包括深度学习中的YOLO、FAST-RCNN这种对每一帧图像检测目标的位置。

Mean Shift作为一种特征空间的分析技术，可以最终定位到使得密度度量函数(density function)最大的位置。在视频的目标追踪中，通过在初始阶段计算得到关于目标的颜色直方图表示，在视频的接下来的帧中，将与目标的直方图的Bhattacharyya相关性系数、概率权重等作为更新的依据。MeanShift的更新过程可以使用下图解释。

流程

核密度估计

在$d$d维的空间$R^{d}$Rd中，对于点$\{x_i\}_{i=1\dots n}${xi​}i=1…n​，核密度估计的核函数记为 $K(x)$K(x)，窗口的大小记为 $h$h，则对于以$x$x为中心点的值为:
$\hat{f}(x)=\frac{1}{nh^d}\sum_{i=1}^{n}K(\frac{x-x_i}{h})$f^​(x)=nhd1​i=1∑n​K(hx−xi​​)

常用的核函数有

1. Epanechnikov 核函数
   $K_{E}(x)= \left\{ \begin{aligned} &\frac{1}{2}c_d^{-1}(d+2)(1-\|x\|^2) ,& \|x\| < 1\\ & 0 & otherwise \end{aligned} \right.$KE​(x)=⎩⎨⎧​​21​cd−1​(d+2)(1−∥x∥2),0​∥x∥<1otherwise​
   其中 $c_d$cd​是$d$d维空间的容量。
2. 高斯核函数
   $K_N(x)=(2\pi)^{-d/2}\exp\left(-\frac{1}{2}\|x\|^2\right)$KN​(x)=(2π)−d/2exp(−21​∥x∥2)

相关性

当使用直方图表示图像中某个区域的像素分布时，该直方图可以看做一个向量。衡量两个向量的相似性可以使用余弦相似度来计算。

假设目标的直方图向量为$q=\{q_1,q_2,\dots,q_m\}$q={q1​,q2​,…,qm​}，当前位置的直方图向量为 $p=(p_1,p_2,\dots,p_m)$p=(p1​,p2​,…,pm​)，则两个向量之间的余弦相似度为：
$\begin{aligned} &\cos \theta=\frac{p^Tq}{\|p\|\cdot \|q\|}\\ &=\sum_{i=1}^{m}\sqrt{p_i q_i} \end{aligned}$​cosθ=∥p∥⋅∥q∥pTq​=i=1∑m​pi​qi​​​

表示

在原始的论文中，并不是直接使用计算得到的颜色直方图来表示目标以及用于算法的计算，而是考虑了目标区域中以区域中心像素点为中心的核函数作为像素点的权重。原始论文中，设$\{x_i^*\}_{i=1\dots n}${xi∗​}i=1…n​为要追踪目标的像素点，假设以0为中心（在实际计算的时候，就是按照中心像素位置标准化一下）。目标区域的颜色直方图为：
$q(u)=C\sum_{i=1}^{n}k(\|x_i^*\|^2)\delta[b(x_i^*)-u]$q(u)=Ci=1∑n​k(∥xi∗​∥2)δ[b(xi∗​)−u]
其中
$\delta(x)=\left\{ \begin{aligned} &1, &x=0\\ & 0, & otherwise \end{aligned} \right.$δ(x)={​1,0,​x=0otherwise​
即计算的时候，只累加到当前像素的颜色对应的直方图bin中。其中$C$C是标准化项，
$C=\frac{1}{\sum_{i=1}^{n} k(\|x_i^*\|^2)}$C=∑i=1n​k(∥xi∗​∥2)1​
对于算法运行过程中候选位置的颜色表示的方法与之相同。

算法迭代过程

Mean Shift算法流程
输入：目标的颜色表示 $q$q，前一个视频帧的目标位置 $\hat{y}_0$y^​0​
迭代过程：
1.   计算得到当前帧目标位置的颜色表示 $\{p_u(\hat{y}_0)\}_{u=1\dots m}${pu​(y^​0​)}u=1…m​，并计算相似度 $\rho[p(\hat{y}_0),q]=\sum_{u=1}^{m}\sqrt{p_u(\hat{y_0})q}$ρ[p(y^​0​),q]=∑u=1m​pu​(y0​^​)q​
2.   计算得到权重 $\{w_i\}_{i=1\dots n_h}${wi​}i=1…nh​​, $w_i=\sum_{u=1}^{m}\delta[b(x_i)-u]\sqrt{\frac{q}{p_u(\hat{y}_0)}}$wi​=∑u=1m​δ[b(xi​)−u]pu​(y^​0​)q​​
3.   计算得到新的位置：$\hat{y}_1=\frac{\sum_{i=1}^{n_h}x_i w_i g\left(\left\|\frac{\hat{y}_0-x_i}{h}\right\|^2\right)}{\sum_{i=1}^{n_h}w_i g\left(\left\|\frac{\hat{y}_0-x_i}{h}\right\|^2\right)}$y^​1​=∑i=1nh​​wi​g(∥∥∥​hy^​0​−xi​​∥∥∥​2)∑i=1nh​​xi​wi​g(∥∥∥​hy^​0​−xi​​∥∥∥​2)​
4.   根据新的位置计算得到颜色表示 $\{p_u(\hat{y_1})\}_{u=1\dots m}${pu​(y1​^​)}u=1…m​以及相似性 $\rho[p_u(\hat{y}_1),q]=\sum_{u=1}^{m}\sqrt{p_u(y_1)q}$ρ[pu​(y^​1​),q]=∑u=1m​pu​(y1​)q​
5.   while $\rho[p_u(\hat{y}_1),q] < \rho[p_u(\hat{y}_0),q]$ρ[pu​(y^​1​),q]<ρ[pu​(y^​0​),q]   do $\hat{y}_1\leftarrow \frac{1}{2}(\hat{y}_0+\hat{y}_1)$y^​1​←21​(y^​0​+y^​1​)
6.   if $\|\hat{y}_1-\hat{y}_0\| < \epsilon$∥y^​1​−y^​0​∥<ϵ   结束
else  $\hat{y}_0\leftarrow \hat{y}_1并继续从第一步开始$y^​0​←y^​1​并继续从第一步开始

目标尺寸的适应

由于视频中，目标可能从较远的位置移动到较近的位置或相反。这样目标在图像中所占的像素个数就会发生变化。原论文中，通过在迭代过程中，调整窗口$h$h的值浮动$\pm 10\%$±10%，并选择使得相似性最大的那个值。

实现

代码已上传Github上，由于测试使用的视频较大，因此程序运行中计算量较大，速度较慢。如果换成小一点的，比如原论文中$320\times 240$320×240大小的会比较快。此外，由于MeanShift受限于计算的窗口，如果目标在某段时间被遮挡住，MeanShift可能会丢失目标。

参考

1. Mean-shift Tracking
2. Real-Time Tracking of Non-Rigid Objects using Mean Shift