光学跟踪器：ASEF和MOSSE

视频分析的重要子任务之一是跟踪视频上的对象。 它不是那么原始，以至于我不得不逐个像素地进行研究，但是它并不那么复杂，以至于毫无疑问需要解决方案的多层神经网络。 跟踪既可以用作目的，也可以用作其他算法的一部分：

• 计算进入某个区域或越过边界的独特人数
• 识别停车场中的汽车和商店中的人的典型路线
• 物体移动时监控摄像机自动旋转

甚至不用看文献，我就可以自信地说，解决问题的最佳方法是使用神经网络。 总的来说，您无法再写任何东西了，但并非总是可以使用一对GTX 1080Ti来完成任务。 在这种情况下，谁在乎如何跟踪视频上的对象呢？ 我将不仅尝试解释ASEF和MOSSE跟踪器的工作原理，还带您进入解决方案，以便使公式看起来很明显。

首先，我们将回答一个初步的问题：为什么可以发明一些东西，当您可以提供张量流的视频堆栈并离开计算机几周后？ 神经网络方法有一个严重的缺点：即使在现代视频卡上，也很难通过网络实现良好的发射率。 如果我们分析录制的视频，这不是问题，但是如果您想实时工作，它会在车轮上插入一根棍子。 假设我们要以10 FPS处理来自五个摄像机的视频。 即使在相对温和的条件下，神经网络的推理时间也应小于 $$$\ frac {1000} {5 \乘10} = $ 2$ 毫秒（在完全非并行的条件下）。 为了进行比较，YoloV3（具有相对简单架构的分类器网络）可以向 $$$50$ 毫秒。 此外，基于功能强大的图形卡的解决方案可能非常昂贵。

本文假定您已经处理过机器图像处理，熟悉线性代数的基本操作（卷积，范数，矩阵求逆），并且通常了解傅里叶变换。

以下：

• $$$A \ odot B$ 代表逐元素矩阵乘法 $$和 $$$B$
• $$$A \次B$ 表示矩阵的卷积 $$和 $$$B$
• $$$\帽子{A}（\ omega，\ nu）= \数学{F}（A（x，y））$ 意味着 $$$\帽子{A}（\ omega，\ nu）$ 傅里叶变换的频率矩阵应用于图像 $$。
• $$$\并行A \ parallel_2$ -表示矩阵元素的平方和 $$

琐碎的决定

乍一看，跟踪特定主题的任务似乎并不复杂。

可以有 $$$T$ 连续的视频帧 $$$I_t$ 大小 $$$w$ 在 $$$h$ 像素。 在视频的初始帧中 $$$I_0$ 一个矩形围绕某些对象 $$$F_0$$$$m$ 在 $$$n$ 。 需要在所有其他框架上找到该物体的位置 $$$I_t$ 。

我们去除图像中的噪点，然后将它们标准化为-1到1，以便亮度的一般变化不会影响检测。 拍摄视频的第一帧而无需标记 $$$I_1$ 。 如果 $$$I_0$ 和 $$$I_1$ -具有良好FPS的相邻视频帧，不太可能将所需对象从其原始位置移开。 利用这一点。 切出 $$$I_1$ 长方形 $$$F_1$ 从所需身体先前所在的位置开始。 “拖动” $$$F_0$ 通过 $$$F_1$ 然后在每个点上计算差异总和的平方

$$

$$G_ {L_2}（i，j）= \并行F_ {1}（i，j）-F_0 \ parallel_ {2}，i \ in [0，m]，j \ in [0，n]$$

在哪里计算差异 $$$G_ {L_2}（i，j）$ 需要结合中心 $$$F_0$ 与元素 $$$（i，j）$ 在 $$$F_1$ ，而缺失值则为零。 之后在矩阵中 $$$G_ {L2}$ 寻求最低限度； 它的位置减去中心的坐标 $$$F_1$ 并且将是所需对象的偏移量 $$$I_1$ 。

为了使检测过程中不会急剧过渡到零而不会“响”，最好先将矩形移到比所需的多一点的位置，然后将接近边界的值平滑地减小到零。 $$$F_0$ 和 $$$F_1$ 。 为此，每个 $$$F$ 需要乘以面具。 对于方形物体，优秀的老参展商会做。 $$$A = \ exp {\ frac {（x-i）^ 2 +（y-j）^ 2} {\ sigma ^ 2}}$ （其中 $$$（x，y）$ 是窗口的中心），但通常情况下，最好使用二维汉宁窗口。

对于 $$$I_2$ 窗户 $$$F_2$ 从框架上预测的位置获取 $$$I_1$ 等等。


相反 $$$L_2$ 可以使用规范 $$$L_1$ （ $$$G_ {L_ {1}}（i，j）= | F_1（i，j）-F_0 |$ ），然后减去矩阵的互相关（ $$$G_ {nCC}（i，j）=-\ sum_ {kl} {F_ {1，kl}（i，j）F_ ​​{0，kl}}，k \ in [0，m]，l \ in [ 0，n]$ ） 两者都被认为比 $$$L_2$ 但是它们有自己的特点。 $$$L_1$ 不可微分，并且对像素值的大差异不太敏感。 如果样本的对比度较低，并且图像的区域非常亮或非常暗，则互相关会产生假阳性。

$$$L_2$ 指标的版本没有这样的缺点：

$$

$$G_ {L_2} = \ sum {（F_ {1，kl}（i，j）-F_ {0，kl}）^ 2}$$

$$

$$= \ sum {（F_ {1，kl}（i，j））^ 2-2 F_ {1，kl}（i，j）F_ ​​{0，kl} +（F_ {0，kl}）^ 2 }$$

$$

$$= \ sum {（F_ {1，kl}（i，j））^ 2}-\ sum {2 F_ {1，kl}（i，j）F_ ​​{0，kl}} + \ sum {（F_ {0，kl}）^ 2}$$

$$

$$= E_ {F_1（i，j）} + 2 G_ {nCC}（i，j）+ E_ {F_0}$$

$$$E_ {F_1（i，j）}$ ，所选网站上的“能源” $$$I_t$ 充当平衡因素（ $$$E_ {F_0}$ ，样本像素值的平方和对于所有窗口位置都是相同的，在这里没有实际意义。

即使在对象线性移动的情况下（例如，照相机向下看传送带），这种原始算法也能很好地应对。 但是，由于模型和执行的简单性，此跟踪方法有几个缺点：

1. 没有自然变化的物体的简单线性运动是很少的。 通常，摄像机视场中的物体可能会发生某些类别的变化。 按复杂度增加的顺序：大小的增加/减小，转弯，仿射变换，射影变换，非线性变换，对象的变化。 即使我们省略了对象变化和非线性变换，我们也希望该算法能够从相对简单的旋转和大小变化中恢复。 显然，以上过程没有此属性。 大概吧 $$$F_0$ 它仍然会在物体上产生明显的响应，但是将难以确定样品的确切位置，并且轨迹将是不连续的。
   
   
   例子

   

   
   
2. 我们只显示了该算法的一个正样本，很难说会给出什么响应 $$$F_0$ 如果另一个类似的物体进入窗口。 好吧，如果所需的对象是对比的并且具有罕见的结构，但是如果我们要监视其他机器流中的机器怎么办？ 跟踪器会意外地从一辆车跳到另一辆车。
3. 在每一帧，我们丢弃整个背景故事。 可能也应该以某种方式使用它。
4. 而且，我们仅在图像中的一点上学习。 如果在对象的正确位置附近 ，跟踪器也会给出良好的响应，则效果会更好。 有点违反直觉，但请考虑：如果滤镜位于图片中对象的确切位置 $$$（x，y）$ 提供最佳价值，并且 $$$（x + 1，y + 1）$ -随机的东西，这意味着他对容易改变的小细节过于敏感。 相反，如果在 $$$（x，y）$ 和在 $$$（x + 1，y + 1）$ 大致相同的好值，过滤器会“钩住”较大的（我们希望是更永久的）信号。
5. 使用跟踪过程的简单实现，对于帧的每个像素，我们将整个窗口与所选项目乘以该帧的相应部分。 此操作的复杂性是 $$$O（m ^ 2n ^ 2）$ 。 在这种情况下，即使跟踪50至50像素的对象也不太好。 通过减小视频的大小可以部分解决此问题，但是当将图像缩小到宽度小于240像素时，甚至会丢失大量重要的细节，这使算法变得毫无意义。

MOSSE，ASEF

简单的方法++？

卷起袖子，尝试解决上述问题。

增强原始图像。 我们对其应用了一些轻微的仿射变换。 您还可以添加噪音或更改伽玛。 因此，不是一个图像，而是一个微数据集 $$$P$ 图片。 有很多图像，但是只剩下一个窗口。 所以现在我们不仅要从图像上切出一个矩形，还要寻找一些滤镜 $$$W$ 这将给大家一个很好的回应 $$$I ^ p$ 。 我们将问题转化为最小化问题：

$$

$$W：\ min_W {\ parallel F ^ p-W \ parallel_2}，p \ in [1，P]$$

在哪里 $$$\并行F ^ p-W \ parallel_2$ -之间的像素差的平方和 $$$W$ 以及对象的确切位置的对应部分 $$$p$ 从具有真实标记的框架创建的合成图像。

此外，您可以对远离跟踪对象位置的矩形进行采样，并最大化上面显示的差异。

很难建议滤波器在物体的精确位置附近的点处给出良好的响应。 我们知道 $$$（x，y）$ 过滤应用程序 $$$L_2$ -metric应该给0，其次-更多，更远-甚至更多。 而且，我们没有任何首选的方向，响应应相对于 $$$（x，y）$ 。 看起来我们可以数学地表达应用于参考图像的滤镜的响应应该是什么样子！ 确切的外观可能会因特定的响应衰减功能而异，但是每个人都喜欢高斯吗？ 因此，我们假设 $$$W$ 适用于 $$$F_p$ 理想情况下应该给出结果 $$$G_p = 1-\ exp {\ frac {（x-i）^ 2 +（y-j）^ 2} {\ sigma ^ 2}}$ 。 因此，最小化问题变成：

$$

$$D_p（i，j）= \平行F ^ p（i，j）-W \ parallel_2$$

$$

$$W：\ min_W {\并行D_p（i，j）-G_p（i，j）\ parallel_2}，p \在[1，P]$$

现在，我们不在一点上最小化响应，而是将响应与期望值的偏差最小化。

等一下...我们做到了 $$$P \倍m \倍n$ 与等式 $$$m \次n$ 变量以最小化。 看来我们过分了。 让我们回去一点。

主要技巧

在所有问题中，最大的困难是复杂性。 $$$O（m ^ 2n ^ 2）$ 。 除了将一个搜索框巧妙地分割成几个小框之外，还是可以提出一些其他解决方案，或者以较小的分辨率在图片中进行搜索并进行高精度调整呢？

事实证明你可以！ Matanalysis告诉我们，普通空间中的功能折叠是其傅立叶图像的倍增。 我们能够对图像应用快速傅里叶变换，将它们的频率逐个元素相乘，然后将结果转换回矩阵 $$$O（mn \ log {mn}）$ ，这比诚实地最小化矩阵要快得多。 傅里叶！ 谁会想到的！ 在张量流时代，他仍然可以帮助我们实现计算机视觉。

（顺便说一下，这演示了一般的数学原理：如果您不想解决太空问题 $$$X$ 将其移入太空 $$$Y$ ，在那里进行决策，然后将决策转移回去。 解决方法通常比直接解决方法短。）

如上所示，我们可以使用互相关来定位图像中的样本。 但是互相关是水平和垂直反射的卷积 $$$W$ 。 Matanalysis建议，在这种情况下，有必要倍增频率 $$$F$ 在复共轭矩阵到频率矩阵上 $$$W$ ：

$$

$$\帽子{W}（\ omega，\ nu）= \数学{F}（W（x，y））$$

$$

$$\ hat {F}（\ omega，\ nu）= \数学{F}（F（x，y））$$

$$

$$\ hat {G} _ {conv}（\ omega，\ nu）= \ mathcal {F}（G_ {conv}（x，y））$$

$$

$$G_ {conv} = F \ otimes W \ rightarrow \ hat {G} _ {conv} = \ hat {F} \ odot \ hat {W} ^ *$$

在哪里 $$$G_ {conv} = \ exp {\ frac {（x-i）^ 2 +（y-j）^ 2} {\ sigma ^ 2}}$ -完善的参考图像响应功能。 请注意 $$$L_2$ 我们最小化了度量并最大化了卷积度量，所以现在，响应越大越好。

如果我们只有一张图像，那么我们将找到确切的滤波器频率矩阵：

$$

$$\ hat {W} ^ * = \ frac {\ hat {G} _ {conv}} {\ hat {F}}$$

其中右侧是指按元素划分。 但是早一点我们产生了 $$$P$ 来自源的图像。 我们可以通过傅立叶方法应用它们。 没有一个具有理想频率的滤波器可以理想地满足所有图像，但是您可以获得足够好的信号。 有两种方法可以解决问题：

1. 您可以找到一组理想的滤波器，然后将它们平均为一个。 这就是“ 平均精确合成滤波器” （ASEF）的作者所采用的方式：

   $$

   $$\ hat {W} ^ * = \ frac {1} {P} \ sum_ {p = 1} ^ {P} \ hat {W} ^ * _ p = \ frac {1} {P} \ sum_ {p = 1} ^ {P} {\ frac {\帽子{G} _p} {\帽子{F} ^ p}}$$
   在这里，我们使用傅立叶图像的线性特性。 如上所示，添加频率似乎可以平均几个滤波器的权重。
2. 您可以找到平均满足所有图片的滤波器频率 $$$L_2$ ：

   $$

   $$\ hat {W} ^ *：\ min _ {\ hat {W} ^ *} {\ sum_ {p = 1} ^ {P} {\ parallel \ hat {F} ^ p \ odot \ hat {W} ^ *-\帽子{G} _p \ parallel_2}}$$
   要找到最小值，您需要采用过滤器元素的导数：

   $$

   $$\ frac {\ delta} {\ delta \ hat {W} ^ *} \ sum_ {p = 1} ^ {P} {\ parallel \ hat {F} ^ p \ odot \ hat {W} ^ *-\帽子{G} _p \ parallel_2} = 0$$
   在使用自适应相关过滤器的视觉对象跟踪中可以找到对这种导数的真实捕获，该过滤器提供平方误差过滤器（MOSSE过滤器）的最小输出和。 结果是这样的：

   $$

   $$\ hat {W} ^ * = \ frac {\ sum_ {p = 1} ^ {P} {\ hat {G} _p \ odot \ hat {F} ^ {p *}}} {\ sum_ {p = 1} ^ {P} {\帽子{F} ^ p \ odot \帽子{F} ^ {p *}}}$$

嗯，好像公式中涉及相似的元素。 在 $$$P = 1$ ASEF和MOSSE的公式完全相同。 $$$\帽子{W} ^ *$ 一个图像可以表示为

$$

$$\ hat {W} ^ * = \ frac {\ hat {G_p}} {\ hat {F ^ p}} = \ frac {\ hat {G_p} \ odot \ hat {F} ^ {p *}} { \ hat {F ^ p} \ odot \ hat {F} ^ {p *}}$$

用ASEF的公式代替并得到

$$

$$\ hat {W} ^ * = \ sum_ {p = 1} ^ {P} {\ frac {\ hat {G} _p \ odot \ hat {F} ^ {p *}} {\ hat {F} ^ p \ odot \ hat {F} ^ {p *}}}$$

是的 现在，更好地看到ASEF和MOSSE仅在滤波器平均方法上有所不同！ 有人认为，MOSSE产生比ASEF更好的过滤器。 听起来很合逻辑：将整个图像包调整为一个整体要好于平均滤镜。

我们得到之后 $$$\帽子{W} ^ *$ ，我们在频域中计算响应 $$$\ hat {G} _ {conv} = \ hat {F} \ odot \ hat {W} ^ *$ ，然后将其转换为空间域，并在结果矩阵中寻找最大值 $$$G$ 。 最大的位置是对象的新位置。

附加点

• 式的分母中的术语具有有趣的物理意义。 $$$\ hat {F} ^ p \ odot \ hat {F} ^ {p *}$ 矩形的能谱是 $$$p$ 该图像。
• 注意有趣的对称性。 为了获得响应，必须将滤波器频率乘以镜像频率。 现在，您需要将响应频率乘以镜像频率（并归一化）以获得滤波器频率。
• 在现实生活中，按元素除法会导致被零除，因此通常在分母中添加正则化常数 $$$\ epsilon$ 。 有人认为，这种正则化使滤波器更加关注低频，从而提高了泛化能力。
• 处理真实视频时，通常需要保存有关从先前帧获得的跟踪对象的信息。 移至下一帧时，无法计算 $$$\帽子{W}$ 从头开始，并更新前一个。 更新ASEF的公式：

  $$

  $$\ hat {W} ^ * _ i = \ frac {\ eta} {P} \ sum_ {p = 1} ^ {P} {\ frac {\ hat {G_p}} {\ hat {F ^ p}}} +（1-\ eta）\帽子{W} ^ * _ {i-1}$$
  对于MOSSE，您需要分别累加分子和分母：

  $$

  $$A_i = \ eta \ sum_ {p = 1} ^ {P} \帽子{G} _p \ odot \ hat {F} ^ {p *} +（1-\ eta）A_ {i-1}$$

  $$

  $$B_i = \ eta \ sum_ {p = 1} ^ {P} \帽子{F} ^ p \ odot \ hat {F} ^ {p *} +（1-\ eta）B_ {i-1}$$

  $$

  $$\ hat {W} ^ * _ i = \ frac {A_i} {B_i}$$
  在哪里 $$$\ eta$ -学习速度。
• 重要的是要记住，傅立叶变换与计算并不完全相同 $$$G$ 老实说，如本文开头所述。 在计算FFT时，丢失的元素不会消失，而是在相反的一侧进行替换，就像图像从右到左以及从下到上循环一样。 但是在本文的开头，我们已经决定将边缘变暗 $$$F$ ，因此此问题不会产生明显的影响。
• 如上所述，互相关具有令人不快的特征：通常，滤光器可以在图像的白色区域中给出强烈的响应，即使它们在对比区域中不一致。 问题不限于此。 如果整个样本的对比度较低，则即使是一个具有非常强的正值或非常负值的匹配像素也会干扰滤镜。 为了消除这种影响，预处理中必须包括图像像素的非线性变换，这将“压”太亮和太暗的区域到中间。 因此，这些对比区域的重合对度量有更大的贡献。 ASEF和MOSSE文章使用对数：

  $$

  $$I = \日志{I + 1}$$
  像素在哪里 $$$我$ 从0到255。在我看来，这太苛刻，并且忽略了黑色区域中深色滤镜响应强烈的问题。 这样的方案效果更好：

  $$

  $$I =符号（I-127）\ sqrt {| I-127 |}$$
  然后是归一化，结果证明大多数元素都以零为中心。
  
• 这样的算法如何确定被跟踪物体已从帧中消失？ 对从下一帧收到的响应进行更详细的分析将有助于此处。 MOSSE的创建者提供了PSR指标-峰旁瓣比。 让 $$$g_ {max}$ -最大元素 $$$G$ 对应于对象的新位置 $$$（x，y）$ 。 我们排除了正方形 $$$11 \乘11$ 在这个最大值附近。 我们计算剩余像素的平均值和标准偏差（ $$$\ mu_ {sl}，\ sigma_ {sl}$ ） 然后

  $$

  $$PSR = \ frac {g_ {max}-\ mu_ {sl}} {\ sigma_ {sl}}$$
  如果该值高于某个阈值，则认为检测成功。 阈值通常在3到10之间的范围内。为了进行可靠的检测，PSR通常保持在20以上。
  
  （请注意，这里的PSR根本不代表信号处理理论中通常所说的含义；因此，请不要用谷歌搜索，不会有什么好处）
• 该算法非常简单。 使用OpenCV实施在具有320x400的图像中对Core-i7进行跟踪的过程需要0.5到2毫秒，具体取决于被跟踪对象的大小。

MOSSE算法

全部放在一起。

一般情况：

滤波器频率矩阵： $$$\帽子{W}$
用于计算滤波器频率的辅助矩阵： $$$A，B$
理想理想响应的频率矩阵： $$$\帽子{G}$
跟踪过程中的训练速度： $$$\ eta$
对象当前位置的矩形： $$$R$
转换数量： $$$P$
响应阈值： $$$PSR_ {thr}$

辅助功能： 培训 。 输入：图像 $$$我$ 当前的学习速度 $$$\ eta_ {当前}$

1. $$$A_ {新}：= 0，B_ {新}：= 0$
2. 直到我明白了 $$$P$ 转换：
   
   1. 应用以图像中心为中心的小型随机仿射变换。 $$$R$
   2. 从带有对象的矩形图像切出 $$$F$
   3. 在其上应用遮罩以平滑消除边缘
   4. 翻译 $$$F$ 在频域中： $$$\帽子{F}$
   5. $$$A_ {新} = A_ {新} + \帽子{G} \ odot \帽子{F} ^ *$
   6. $$$B_ {新} = B_ {新} + \帽子{F} \ odot \帽子{F} ^ *$
   
   
3. 如果 $$$\ eta_ {current} \ geq 1.0$ 然后更换 $$和 $$$B$ 在 $$$A_ {新}$ 和 $$$B_ {新}$ 。 否则：
   

   $$

   $$B：= \ eta B_ {new} +（1-\ eta）B$$

   $$

   $$A：= \ eta A_ {new} +（1-\ eta）A$$
4. 计算滤波器频率：

   $$

   $$\ hat {W} ^ * = \ frac {A} {B}$$

初始化 。 输入：图像 $$$我$ 围绕对象位置的矩形 $$$R_ {init}$

1. $$$R：= R_ {init}$
2. 准备所需的响应 $$$G$ 。 通常，这是一个完全零的矩阵，中心有一个小高斯。
3. 培训内容 ： $$$我$ ，1.0
4. 翻译 $$$G$ 在频域中： $$$\帽子{G}$

跟踪 ：输入：图像 $$$我$

1. 切矩形 $$$F$ 来自 $$$我$ 用于对象的现有先前位置 $$$R$
2. 在其上应用遮罩以平滑消除边缘
3. 翻译 $$$F$ 在频域中： $$$\帽子{F}$
4. $$$\ hat {G} _ {response} = \ hat {W} \ odot \ hat {F} ^ *$
5. 翻译 $$$\帽子{G} _ {响应}$ 到空间域： $$$G_ {response}$
6. 在中找到最大值 $$$G_ {response}$ ： $$$g_ {max}，（x，y）$
7. 计算响应功率 $$$PSR：= \ frac {g_ {max}-\ mu_ {sl}} {\ sigma_ {sl}}$
8. 如果 $$$PSR <PSR_ {thr}$ 退出失败
9. 更新位置 $$$R$ 。 如果R超出图像，或者确定对象增加/减少，请调整R。
10. 培训内容 ： $$$我$ ， $$$\ eta$
11. 回程 $$$R$

实施细节可能有所不同。 举个例子

• 只能预处理 $$$F$ ，而不是整个图像。
• $$$G$ 可以为每个具有不同功能和响应宽度的图像变换重新创建图像。
• 您可以同时在对象的多个比例尺上训练几个不同的滤镜，以检测距离及其附近的移动。

看起来像什么

首先，举几个二维傅立叶变换的例子。


现在，让我们继续一个真实的工作示例：


相同示例，其期望的响应范围更窄：


$$$W$ 对于前三种情况 $$$G$ 当用于训练输入图像的16种转换时：


如果要查看它的实时效果，请从此处下载我的测试存储库，其中包含MOSSE的实现以及调试图片的输出。 您可以在 github 上找到更多的MOSSE 选项 。 另外，它在OpenCV中 。

结论

谢谢您的关注，哈布罗夫斯克。 MOSSE和ASEF跟踪不是世界上最复杂的算法。 不仅容易有效地应用它们，而且更容易理解如何指导其创建者。 我希望我的解释能帮助您进入研究人员的头脑，跟随他们的思想进程。 这可能是有用的：机器学习不是知识的静态领域；这里有创造力和研究的地方。 尝试更深入地研究一些已建立的算法：去除不必要的肢体以进行加速，或者添加一些对策以使其在您的特定情况下更好地工作。 你会喜欢的！

本文是在DSSL的支持下编写的。