《视频分析前沿》二

简介

记录完Mean Shift，好像因为内容太多，目录显示老是错误，再开一篇。

五、mean shift及其应用

如何在不估算密度的情况下估计局部峰值的位置？

特征空间分析

低层次计算机视觉任务是非常困难的。执行低层次任务应该是任务驱动，支持独立的高层次的信息。它要求低层次阶段提供了一个可靠的输入，表示和提取特征过程只有很少的调优参数来控制。而基于特征空间分析的图像可以实现上述目标。

特征空间是通过一次处理小子集中的数据而获得的输入的映射。对于每个子集，获得感兴趣特征的参数表示，并将结果映射到参数的多维空间中的点。处理所有的输入后，重要特征对应于特征空间中更密集的区域。分析的目标是划分这些集群。

特征空间的性质取决于应用。对特征空间的分析与应用无关。它依赖于聚类数量的先验知识的方法，以及隐含地为空间中的所有聚类假设相同形状（通常是椭圆形）的方法，不能处理真实特征空间的复杂性。

由主导颜色产生的集群之间存在连续过渡，所以GMM对这些数据不适用。另外，GMM需要集群的数量作为参数，这会增加另外的困难。

任意结构化的特征空间只能通过非参数方法进行分析，非参数方法可分为两大类：层次聚类和密度估计。

• 分层聚类技术根据某种邻近度量来聚合或划分数据。分层方法往往计算成本昂贵，并且对数据融合（或除法）的有意义停止标准的定义并不简单。

• 特征空间可视为所表示参数的经验概率密度函数（p.d.f.）。特征空间中的密集区域对应于p.d.f.的局部最大值，即对应于未知密度的模式。确定模式的位置后，将圈定与其关联的集群。均值漂移方法基于迭代均值漂移过程实现模式检测和聚类，该方法将数据点移动到其邻域中的数据点的平均值。

Mean Shift

Funkunaga于1975年提出了mean shift，Hostetler和Cheng于1995年重新调整了它，Comaniciu在2000年左右发展了它。Comaniciu因其在物体跟踪方面的工作，在CVPR2000上获得了最佳论文奖。均值漂移方法对聚类，模式搜索，概率密度估计，跟踪等有用。

直观描述

作用：在一组数据样本中寻找模式，在$R^N$中显示相关概率密度函数（PDF），在任何特征空间中都能使用。

核密度估计也称为Parzen窗口技术。这是最流行的密度估算方法。考虑$d$维欧几里德空间中的$n$个数据点$x_i$的集合$S$。在点$x$中计算的具有核$K(x)$和$d\times d$对称正定带宽矩阵$H$的多元核密度估计器由下式给出：

$$\hat f(x) = \frac{1}{n} \sum_{i=1}^n K_H(x-x_i)$$

其中，

$$K_H(x)=|H|^{-1/2}K(H^{-1/2}x)$$

假设：数据点从相关PDF中采样。

$d$变量核$K(x)$是一个有界函数，满足以下严谨的性质：

• 正则化：$\int_{R^d}K(x)dx=1 $
• 对称性：$\int_{R^d}xK(x)dx=0$
• 指数级权重衰减：$lim_{||x|| \rightarrow \infty}||x||^d K(x)=0$且$\int_{R^d}xx^TK(x)dx=cI$

其中，$c$是常数。

可以通过两种不同方式从对称单变量核$K_1(x)$生成多变量核：

我们只对满足以下特殊类型的径向对称核感兴趣：

在实践中，带宽矩阵$H$被选择为对角线$H=diag[h_1^2,…,h_d^2]$，或者是成倍单位矩阵$H=h^2I$。

选择后者的好处：只需要一个带宽参数$h>0$，因此被广泛使用，

$$\hat f(x) = \frac{1}{nh^d}\sum_{i=1}^nK(\frac{x-x_i}{h})$$

核密度估计的权重通过密度与其估计之间的平方误差的平均值来测量。

Epanechnikov核

AMISE指标由Epanechnikov核最小化，其形式如下：

$$K(x)=c_{k,d}k(||x||^2),k_E(x)=\left\{ \begin{aligned} 1-x && 0\le x \le 1 \\ 0 && x>1 \end{aligned} \right.$$

多维情况：

$$K_E(x)=\left\{ \begin{aligned} \frac{1}{2}c_d^{-1}(d+2)(1-||x||^2) && ||x|| \le 1 \\ 0 && otherwise \end{aligned} \right.$$

其中$c_d$是$d$维单位球体的体积。

高斯核

一维情况：

$$k_N(x)=exp(-\frac{1}{2}x),x \ge 0$$

多维情况：

$$K_N(x)=(2\pi)^{-d/2}exp(-\frac{1}{2}||x||^2)$$

使用$K(x)=c_{k,d}k(||x||^2)$改写：

$$\hat f(x) = \frac{1}{nh^d}\sum_{i=1}^nK(\frac{x-x_i}{h})\Rightarrow \hat f_{h,K}(x)=\frac{c_{k,d}}{nh^d}\sum_{i=1}^n k(||\frac{x-x_i}{h}||^2)$$

分析具有相关密度$f(x)$的特征空间的第一步是找到该密度的模式。

模式位于梯度的零点之中$\bigtriangledown f(x)=0$，并且可以使用均值漂移来定位这些零点而不用估计密度。

密度梯度估计量作为密度估计的梯度：

$$\hat \bigtriangledown f_{h,K}(x) \equiv \bigtriangledown \hat f_{h,K}(x) = \frac{2c_{k,d}}{nh^{d+2}}\sum_{i=1}^n(x-x_i)k'(||\frac{x-x_i}{h}||^2)$$

假设所有$x(\ge 0 )$都存在核配置$k$的导数，我们定义函数：

$$g(x)=-k'(x)=-\frac{dk(x)}{dx}$$

现在使用$g(x)$表示配置$k$，核$G(x)$定义为：

核$K(x)$被称为$G(x)$的影。

注意：Epanechnikov核是均匀核的影，即$d$维单位球体；而普通内核及其阴影具有相同的表达式。

将$g(x)$代入，得到

$$\begin{align*} \hat \bigtriangledown f_{h,K}(x)&=\frac{2c_{k,d}}{nh^{d+2}}\sum_{i=1}^n(x_i-x)g(||\frac{x-x_i}{h}||^2) \\ &= \frac{2c_{k,d}}{nh^{d+2}}[\sum_{i=1}^ng(||\frac{x-x_i}{h}||^2)][\frac{\sum_{i=1}^nx_ig(||\frac{x-x_i}{h}||^2)}{\sum_{i=1}^ng(||\frac{x-x_i}{h}||^2)}-x] \end{align*}$$

其中，$\sum_{i=1}^ng(||\frac{x-x_i}{h}||^2)$是另一个核密度估计。（这一步没看懂）

第一项与核$G(x)$计算出的$x$处密度估计值成正比：

$$\hat f_{h,G}(x)=\frac{c_{g,d}}{nh^d}\sum_{i=1}^n g(||\frac{x-x_i}{h}||^2)$$

第二项是均值偏移，它是加权平均值之间的差值，使用核$G$表示权重，以及核（窗口）的中心。

而$\hat \bigtriangledown f_{h,K}(x)$又能被改写成：

$$\hat \bigtriangledown f_{h,K}(x) = \hat f_{h,G}(x)\frac{2c_{k,d}}{h^2c_{g,d}}m_{h,G}(x),m_{h,G}(x)=\frac{1}{2}h^2c\frac{\hat \bigtriangledown f_{h,K}(x)}{\hat f_{h,G}(x)}$$

而使用正态核时，第$j$个mean shift向量为：

$$m_{h,N}(y_j)=y_{j+1}-y_j=\frac{\sum_{i=1}^nx_i exp(-||\frac{y_j-x_i}{h}||^2)}{\sum_{i=1}^n exp(-||\frac{y_j-x_i}{h}||^2)}-y_j$$

它表明具有核$G$的平均移动向量与用核$K$获得的归一化密度梯度估计成比例。因此，平均偏移向量总是指向密度的最大增加方向。局部均值向大多数点所在的区域移动。均值漂移由连续的均值漂移向量$m_{h,G}(x)$计算和由$m_{h,,G}(x)$引起的核（窗口）$G(x)$的变化而实现。保证上述步骤收敛于密度估计具有零梯度的附近点。

低密度值的区域对于特征空间分析不感兴趣，并且在这样的区域中，平均移位步长很大。同样地，在局部最大值附近，步骤很小，分析更精确。因此，均值漂移过程是自适应梯度上升方法。

收敛证明

用$\{y_j\}_{j=1,2,…}$表示核$G$的连续位置序列，我们有：

$$y_{j+1}=\frac{\sum_{i=1}^nx_ig(||\frac{y_j-x_i}{h}||^2)}{\sum_{i=1}^ng(||\frac{y_j-x_i}{h}||^2)},j=1,2,...$$

$y_{j+1}$是用核$G$计算的$y_j$的加权平均值，$y_1$是核初始化位置的中心。

用核$K,\{\hat f_{h,K}(j)\}_{j=1,2,…}$计算的相应密度估计序列由下式给出：

$$\hat f_{h,K}(j)=\hat f_{h,K}(y_j),\space\space j=1,2,...$$

定理1：如果核$K$具有凸的和单调递减的特性，则序列$\{y_j\}_{j=1,2,…}$和$\{\hat f_{h,K}(j)\}_{j=1,2,…}$收敛，并且如果$y_k \neq y_{k+1}$，那么对于所有$k=1,2,…$，$\hat f_E(k) < \hat f_E(k+1)$，则$\{\hat f_{h,K}(j)\}_{j=1,2,…}$也是单调增加的。

证明：

图：收敛证明中使用的$d$维窗口：$S_h(y_k)$、$S_h’(y_k)$、$S_h’’(y_k)$。点$y_{k+1}$是落入$S_h(y_k)$的数据点的平均值。

$n_k$、$n_k’$和$n_k=n_k’+n_k’’$是落在$d$维窗口$S_h(y_k)$、$S_h’(y_k)=S_h(y_k)-S_h’’(y_k)$和$S_h’’(y_k)=S_h(y_k) \cap S_h(y_{k+1})$中的数据点的数量。

在不失一般性的情况下，我们可以假设原点位于$y_k$。 使用密度估计的定义与Epanechnikov核，并注意到$||y_k-x_i||^2=||x_i||^2$我们有

$$\begin{align*} \hat f_E(k) &= \hat f_k(y_k, K_E) \\ &= \frac{1}{nh^d}\sum_{x_i\in S_h(y_k)}K_E(\frac{y_k-x_i}{h}) \\ &=\frac{d+2}{2n(h^dc_d)}\sum_{x_i \in S_h(y_k)}(1-\frac{||x_i||^2}{h^2}) \end{align*}$$

因为核$K_E$是非负的，所以有：

$$\begin{align*} \hat f_E(k+1) &= \hat f_{k+1}(y_{k+1},K_E)\\ & \ge \frac{1}{nh^d}\sum_{x_i \in S_h''(y_k)}K_E(\frac{y_{k+1}-x_i}{h}) \\ &= \frac{d+2}{2n(h^dc_d)} \sum_{x_i \in S_h''(y_k)}(1-\frac{||y_{k+1}-x_i||}{h^2}) \end{align*}$$

接着，因为有$n_k’=n_k-n_k’’$，得到：

$$\hat f_E(k+1)- \hat f_E(k) \ge \frac{d+2}{2n(h^dc_d)h^2}[\sum_{x_i \in S_h(y_k)}||x_i||^2-\sum_{x_i \in S_h''(y_k)}||y_{k+1}-x_i||^2-n_k'h^2]$$

同样，通过对于$x_i \in S_h’(y_k)$定义$||y_{k+1}-x_i||^2 \ge h^2 $，这引出：

$$\sum_{x_i\in S_h'(y_k)}||y_{k+1}-x_i||^2 \ge n_k'h^2 \\ -n_k'h^2 \ge -\sum_{x_i\in S_h'(y_k)}||y_{k+1}-x_i||^2$$

最后得到：

$$\begin{align*} \hat f_E(k+1)- \hat f_E(k) &\ge \frac{d+2}{2n(h^dc_d)h^2}[\sum_{x_i \in S_h(y_k)}||x_i||^2-\sum_{x_i \in S_h''(y_k)}||y_{k+1}-x_i||^2-n_k'h^2]\\ &\ge \frac{d+2}{2n(h^dc_d)h^2}[\sum_{x_i \in S_h(y_k)}||x_i||^2-\sum_{x_i \in S_h''(y_k)}||y_{k+1}-x_i||^2-\sum_{x_i\in S_h'(y_k)}||y_{k+1}-x_i||^2]\\ &= \frac{d+2}{2n(h^dc_d)h^2}[\sum_{x_i \in S_h(y_k)}||x_i||^2-\sum_{x_i \in S_h(y_k)}||y_{k+1}-x_i||^2]\\ &= \frac{d+2}{2n(h^dc_d)h^2}[2y_{k+1}^T\sum_{x_i\in S_h(y_k)}x_i - n_k||y_{k+1}||^2]\\ 因为\sum_{x_i\in S_h(y_k)}x_i为n_k个y_{k+1}之和，\\ &=\frac{d+2}{2n(h^dc_d)h^2}n_k||y_{k+1}||^2 \end{align*}$$

所以，成单调递增，又因为核是凸的，所以必存在极限且收敛。

注意：

• 基于梯度的算法的步长对整体性能至关重要。 如果步长太大，算法将发散，而如果步长太小，则收敛速度可能非常慢。
• 保证收敛是由于平均漂移向量的自适应幅度，这也消除了选择适当步长的额外步骤的需要。 与传统的基于梯度的方法相比，这是一个主要优点。
• 对于离散数据，收敛的步骤数取决于所使用的内核。 停止迭代的实际方法是设置平均漂移向量幅度的下限。

让我们分别用$y_c$和$\hat f_{h,K}(y_c)$表示序列$\{y_j\}_{j=1,2,…}$和$\{\hat f_{h,K}(j)\}_{j=1,2,…}$的收敛点。平均漂移向量的大小收敛到零。 第$j$个均值漂移向量是：

$$m_{h,G}(y_j)=y_{j+1}-y_j$$

当$m_{h,G}(y_c)=y_c-y_c=0$，、

$$\bigtriangledown \hat f_{h,K}(y_c)=0$$

因为$\{\hat f_{h,K}(j)\}_{j=1,2,…}$单调递增，平均漂移迭代满足平均漂移的轨迹被局部最大值吸引。汇聚到相同模式的所有位置的集合定义了该模式的吸引力区域。

其他

模式检测算法：

1. 运行均值漂移，找到密度的静止点。
2. 通过仅保留局部最大值来修剪这些点。

避免错误的极值：

可以通过用小范数的随机向量扰动每个静止点，并使平均移位过程再次收敛来测试该极值点。如果收敛点不变（最大公差），则该点是局部最大值。

新的模式检测算法：

1. 使用简单平均漂移算法查找所有模式
2. 通过扰乱它们来修剪模式（找到鞍点和高原）
3. 修剪极值点的附近，使用窗口并选取最高点

当采用正态核时，两个连续均值漂移向量之间角度的余弦严格为正，即

$$\frac{m_{h,N}(y_j)^Tm_{h,N}(y_{j+1})}{||m_{h,N}(y_j)||||m_{h,N}(y_{j+1})||}>0$$

朝向模式的平均漂移向量的路径遵循平滑轨迹，两个连续平均漂移向量之间的角度总是小于90度。

特征空间的鲁棒性分析

• 要检测所有重要模式，基本均值漂移算法应运行多次（原则上并行演化），初始化覆盖整个特征空间。
• 应解决两个重要问题：特征空间的度量和核的形状。 从输入域到特征空间的映射通常假设成非流体度量。
• 在实践中，最好确保特征空间的度量是欧几里德空间，因此带宽矩阵由单个参数控制。
• 应选择均值漂移过程的起点，使核（窗口）细分整个特征空间（非常稀疏的区域除外）。
• 随着窗口向模式演化，保证几乎所有数据点都被访问，因此在特征空间中捕获的所有信息都被利用。
• 请注意，由于终止迭代的阈值，到给定模式的收敛可能会产生略微不同的位置。
• 同样，在平坦的平台上，梯度值接近于零，平均移动过程可能会停止。

• 可以通过后处理消除劣品。

  • 融合距离小于核带宽的模式候选者，选择与最高密度相对应的模式候选者。
  • 特征空间的整体结构可以通过测量沿两个模式确定的方向上的密度切割所定义的山峰的重要性来确定。

• 在收敛到模式的吸引力区域之后，即收敛到该模式的所有均值平移过程所访问的数据点，自动圈出任意形状的集群。

Mean Shift优点：

• 可以独立使用
• 适用于实际数据分析
• 不假设任何先前的形状（例如椭圆形）数据集群
• 可以处理任意特征空间
• 只需要选择一个参数
• $h$（窗口大小）有物理的含义，与K-Means不同

Mean Shift缺点：

• 窗口大小（带宽选择）并非易事
• 不合适的窗口大小可能导致模式合并，或生成其他“浅”模式 ，解决方案：使用自适应窗口大小

带宽$h$的功能：

• 尺度缩放因子
• 控制概率块在一个点周围扩散的范围
• 控制密度估算的平滑度或粗糙度
• 带宽选择存在欠平滑或过度平滑的危险

可以考虑四种不同的带宽选择方法：

• 与核密度估计器相关的最佳带宽定义为最小化AMISE的带宽。 在多变量情况下，得到的带宽公式几乎没有实际用途。
• 带宽被视为最大工作范围的中心，在该范围内，对于给定数据，获得相同数量的聚类。
• 最佳带宽最大化目标函数，通常比较集群间和集群内的可变性。
• 人工调节会取得好效果。

应用

聚类

不连续保持平滑，图像分割，视觉跟踪等。

平滑

选择L*u*v*是因为它被设计为最佳地近似感知上均匀的颜色空间并且它具有线性映射属性。像素的空间坐标被合并到其特征空间表示中。

分割

References

• Dorin Comaniciu, Peter Meer: Mean Shift: A Robust Approach Toward Feature Space Analysis. IEEE Trans. Pattern Anal. Mach. Intell. 24(5): 603-619 (2002).
• Dorin Comaniciu, Peter Meer: Distribution Free Decomposition of Multivariate Data. Pattern Anal. Appl. 2(1): 22-30 (1999).
• Code: http://coewww.rutgers.edu/riul/research/code/EDISON/edison_src.zip

PS：整理到这里已经快吐了，应用就截图了。

六、多变量局部极小值检测及mean shift在其他领域的应用

多变量局部极小值检测

为了分解数据，需要定义密度函数的局部最大值（模式）的吸引盆地和簇边界，即模型周围的谷。

选择聚类集群索引$v$并定义其补集，

$$C_v \equiv \bigcup_{u \neq v}D_u$$

因此，有以下两个函数：

$$\hat f_{D,K}(x)=\frac{1}{nh^d}\sum_{x_D \in D}K(\frac{x-x_D}{h})\\ \hat f_{C,K}(x)=\frac{1}{nh^d}\sum_{x_C \in C}K(\frac{x-x_C}{h})$$

因此，$x$处的密度估计是：

$$\hat f_K(x)\equiv \frac{1}{nh^d}\sum_{i=1}^nK(\frac{x-x_i}{h})=\hat f_{D,K}(x)+ \hat f_{C,K}(x)$$

上述函数的梯度为：

$$m_K(x)=h^2\frac{\hat \bigtriangledown f_K(x)}{\hat f_K(x)}=\alpha_D(x)m_{D,K}(x)+\alpha_C(x)m_{C,K}(x)$$

其中，

$$m_{D,K}(x)=\frac{\sum_{x_D\in D}x_DK(\frac{x-x_D}{h})}{\sum_{x_D\in D}K(\frac{x-x_D}{h})}-x\\ m_{C,K}(x)=\frac{\sum_{x_C\in C}x_CK(\frac{x-x_C}{h})}{\sum_{x_C\in C}K(\frac{x-x_C}{h})}-x$$

且

$$\alpha_D(x)=\frac{\hat f_{D,K}(x)}{\hat f_K(x)},\ \ \ \ \ \ \ \alpha_C(x)=\frac{\hat f_{C,K}(x)}{\hat f_K(x)}, \ \ \ \ \ \alpha_D(x)+\alpha_C(x)=1$$

利用它来寻找局部极小值点。 假设$x_s$是位于$D$和$C$之间边界上的一阶极小值点。边界条件是

$$m_K(x_s)=0$$

这意味着矢量$\alpha_D(x_s)m_{D,K}(x_s)$和$\alpha_C(x_s)m_{C,K}(x_s)$具有相等的幅度，是共线的，但指向相反的方向。 这解释了$x_s$的不稳定性。

解决一阶鞍点不稳定性：

(a). 沿着由$\alpha_D(x_s)m_{D,K}(x_s)$和$\alpha_C(x_s)m_{C,K}(x_s)$定义的直线对C的轻微扰动将确定开始向C移动的点$x_s$。

(b). 通过使用新的向量$r_D(x_s)$和$r_C(x_s)$，极小值点变得稳定并具有吸引力。

新向量的定义：

$$r_D(x)=\frac{\alpha_C(x_s)m_{C,K}(x_s)}{||\alpha_D(x_s)m_{D,K}(x_s)||}\alpha_D(x_s)m_{D,K}(x_s)\\ r_C(x)=\frac{\alpha_D(x_s)m_{D,K}(x_s)}{||\alpha_C(x_s)m_{C,K}(x_s)||}\alpha_C(x_s)m_{C,K}(x_s)$$

通过交换$\alpha_D(x_s)m_{D,K}(x_s)$和$\alpha_C(x_s)m_{C,K}(x_s)$的范数得到，这次，在扰动的情况下，得到的结果

$$r(x)=r_D(x)+r_C(x)$$

$r(x)$将指向极小值点，它将是一个具有吸引力的稳定点。

这个检测算法应该靠近山谷开始。

mean shift在视觉跟踪的应用

一个视觉跟踪器通常包含两个主要组件：

• 目标表示和定位是一个自下而上的过程，必须对应目标外观的变化。
• 过滤和数据关联是一个自上而下的过程。

配准(registration)是指同一区域内以不同成像手段所获得的不同图像图形的地理坐标的匹配。包括几何纠正、投影变换与统一比例尺三方面的处理。

目标表示和定位的算法与配准方法有关。目标定位和配准都使似然类型函数最大化。 不同之处在于，在跟踪中，在两个连续帧中仅假定目标的位置和外观的微小变化。

目标表达

参考目标模型由特征空间中的概率密度函数 $q$ 表示。可以将目标模型视为以空间位置 $0$ 为中心。在后续帧中，目标候选者在位置 $y$ 处定义，并由概率密度函数 $p(y)$ 表示。为了满足低计算成本，应使用离散密度，即m-bin直方图。 因此，我们有：

$$目标模型: \hat q = \{\hat q_u\}_{u=1,...,m},\sum_{u=1}^m \hat q_u=1\\ 目标候选: \hat p (y)= \{\hat p_u(y)\}_{u=1,...,m},\sum_{u=1}^m \hat p_u=1$$

直方图不是最佳的非参数密度估计，但它足以满足跟踪目的。 也可以采用其他离散密度估计。

下面的相似性函数表示$p$和$q$之间的相似性，

$$\hat \rho (y) \equiv \rho [\hat p(y),\hat q]$$

上述函数起着可能性的作用。 其在图像中的局部最大值表示第二帧中存在与第一帧中定义的$q$类似的表示的对象。

如果仅使用颜色信息来表示目标，则相似度函数可以对图像点阵上的相邻位置具有大的变化但是丢失空间信息。为了找到这些函数的最大值，基于梯度的优化过程难以应用，并且只能使用费时的穷举搜索。

我们通过在空间域中使用各向同性核来屏蔽对象来规范相似性函数。

目标模型

当携带连续空间信息的核权重用于定义特征空间表示时，$\hat p (y)$变为$y$的平滑函数。

目标由图像中的椭圆形区域表示。为了消除不同目标维度的影响，首先将所有目标标准化为单位圆。 这是通过用$h_x$和$h_y$独立重新调整行和列维度来实现的。

设$\{x_i^\ast\}_{i=1,…,n}$是定义为目标模型的区域中的归一化像素位置。 该区域以$0$为中心。

同性核是具有凸的和单调递减的核profile $k(x)$，将更小的权重分配给距离中心更远的像素。使用这些权重增加了密度估计的鲁棒性，因为外围像素是最不可靠的，经常受到遮挡（杂乱）或来自背景的干扰的影响。

函数$b$：$R^2\rightarrow \{1…m\}$ 在位置$x_i$处将像素与量化特征空间中其bin的索引$b(x_i^\ast)$相关联。 后将目标模型中特征$u =1,…,m$的概率计算为

$$\hat q_u=C\sum_{i=1}^nk(||x_i^\ast||^2)\delta[b(x_i^\ast)-u]$$

其中$\delta$是克罗内克函数。 归一化常数$C$通过施加条件$\sum_{u=1}^m \hat q_u=1$而得到，其中

$$C=\frac{1}{\sum_{i=1}^nk(||x_i^\ast||^2)}$$

令$\{x_i\}_{i=1,…,n_h}$为目标候选者的归一化像素位置，以当前帧中的$y$为中心。

使用相同的核profile $k(x)$，但带宽为$h$，目标候选者中特征$u=1,…,m$的概率由下式给出：

$$\hat p_u(y)=C_h\sum_{i=1}^{n_h}k(||\frac{y-x_i}{h}||^2)\delta[b(x_i)-u]$$

其中，

$$C_h=\frac{1}{\sum_{i=1}^{n_h}k(||\frac{y-x_i}{h}||^2)}$$

$C_h$能够由给定的核和不同的$h$值预先计算得到。

基于巴氏系数的度量

相似度函数定义目标模型和候选者之间的距离。

我们将两个离散分布之间的距离定义为：

$$d(y)=\sqrt{1-\rho[\hat p(y),\hat q]}$$

其中应用了巴氏系数：

$$\hat \rho(y) \equiv \rho[\hat p(y), \hat q]=\sum_{u=1}^m \sqrt{\hat p_u(y)\hat q_u}$$

巴氏系数是$m$维单位向量之间角度的余弦，$(\sqrt{\hat p_1},…,\sqrt{\hat p_m})^T$和$(\sqrt{\hat q_1},…,\sqrt{\hat q_m})^T$。

$d(y)$有以下几个理想的性质：

• 添加了一个度量结构。巴氏距离或Kullback散度没有作为度量。
• 具有清晰的几何解释。
• 使用离散密度，因此它对目标的尺度是不变的。
• 对任意分布有效，因此优于Fisher线性判别式。
• 它近似于卡方统计量，同时在比较空直方图箱时避免了卡方检验的奇点问题。

目标定位

要在当前帧中找到与目标对应的位置，应将距离$d(y)=\sqrt{1-\rho[\hat p(y),\hat q]}$作为$y$的函数最小化。

定位过程从前一帧（模型）中目标的位置开始，并在邻域中搜索。

由于距离函数是平滑的，因此该过程使用由均值漂移向量提供的梯度信息。

距离最小化

最小化距离$d(y)$相当于最大化巴氏系数。在当前帧中搜索新目标位置开始于前一帧中目标的位置$y_0$。因此，必须首先计算当前帧中位置$y_0$处的目标候选者的概率$\{\hat p_u(\hat y_0)\}_{u=1,…,m}$。

对$\hat p_u(\hat y_0)$进行使用泰勒展开，获得了巴氏系数的线性近似：

$$\rho[\hat p(y), \hat q] \approx \frac{1}{2}\sum_{u=1}^m\sqrt{\hat p_u(\hat y_0)\hat q_u}+\frac{1}{2}\sum_{u=1}^m \hat p_u(y)\sqrt{\frac{\hat q_u}{\hat p_u(\hat y_0)}}$$

当目标候选者$\{\hat p_u(y)\}_{u=1,…,m}$没有从初始$\{\hat p_u(\hat y_0)\}_{u=1,…,m}$急剧变化时，近似是令人满意的，这通常是连续帧之间的有效假设。

回看

$$\hat p_u(y)=C_h\sum_{i=1}^{n_h}k(||\frac{y-x_i}{h}||^2)\delta[b(x_i)-u]$$

能从

$$\rho[\hat p(y), \hat q] \approx \frac{1}{2}\sum_{u=1}^m\sqrt{\hat p_u(\hat y_0)\hat q_u}+\frac{1}{2}\sum_{u=1}^m \hat p_u(y)\sqrt{\frac{\hat q_u}{\hat p_u(\hat y_0)}}$$

得到

$$\rho[\hat p(y), \hat q] \approx \frac{1}{2}\sum_{u=1}^m\sqrt{\hat p_u(\hat y_0)\hat q_u}+\frac{C_h}{2}\sum_{i=1}^{n_h}w_ik(||\frac{y-x_i}{h}||^2)$$

其中，

$$w_i=\sum_{u=1}^m \sqrt{\frac{\hat q_u}{\hat p_u(\hat y_0)}}\delta[b(x_i)-u]$$

为了最小化距离$d(y)$，上式的第一项与$y$无关，第二项必须最大化。第二项表示在当前帧中使用核profile $k(x)$ 在$y$处计算的密度估计，数据由$w_i$加权。

局部邻域中的这种密度的模式是使用均值漂移方法可以找到的最大值。

在此过程中，根据以下关系将核从当前位置递归移动到新位置：

$$\hat y_1 = \frac{\sum_{i=1}^{n_h}x_iw_ig(||\frac{\hat y_0-x_i}{h}||^2)}{\sum_{i=1}^{n_h}w_ig(||\frac{\hat y_0-x_i}{h}||^2)}$$

其中，$g(x)=-k’(x)$假设所有$x \in [0, \infty)$都存在$k(x)$的导数。

使用e核时：

$$k(x)=\left\{ \begin{aligned} &\frac{1}{2}c_d^{-1}(d+2)(1-x), && if \ \ x\le 1 \\ &0, &&otherwise \end{aligned} \right.$$

在这种情况下，核的导数$g(x)$是常数，且新位置可以变为，

$$\hat y_1 = \frac{\sum_{i=1}^{n_h}x_iw_i}{\sum_{i=1}^{n_h}w_i}$$

巴氏系数的最大化也可以解释为匹配的过滤程序。

目标定位算法

给定：目标模型$\{\hat q_u\}_{u=1,…,m}$和它前一帧的位置$\hat y_0$。

1. 用$\hat y_0$初始化当前帧中目标的位置，计算$\{\hat p_u(\hat y_0)\}_{u=1,…,m}$，并进行评估

   $$\rho[\hat p(\hat y_0),\hat q]=\sum_{u=1}^m \sqrt{\hat p_u(\hat y_0)\hat q_u}$$

2. 根据$w_i=\sum_{u=1}^m \sqrt{\frac{\hat q_u}{\hat p_u(\hat y_0)}}\delta[b(x_i)-u]$，得出权重$\{w_i\}_{i=1,…,n_h}$

3. 根据$\hat y_1 = \frac{\sum_{i=1}^{n_h}x_iw_ig(||\frac{\hat y_0-x_i}{h}||^2)}{\sum_{i=1}^{n_h}w_ig(||\frac{\hat y_0-x_i}{h}||^2)}$找到目标候选者的下一个位置。

4. 计算$\{\hat p_u(\hat y_1)\}$，并且评估

   $$\rho[\hat p(\hat y_1), \hat q]=\sum_{u=1}^m \sqrt{\hat p_u(\hat y_1)\hat q_u}$$

5. 直到$\rho[\hat p(\hat y_1), \hat q]<\rho[\hat p(\hat y_0), \hat q]$，执行$\hat y_1 \leftarrow \frac{1}{2}(\hat y_0+ \hat y_1)$，评估$\rho[\hat p(\hat y_1),\hat q]$。

6. 如果$||\hat y_1-\hat y_0||< \varepsilon$，退出；否则，执行$\hat y_0 \leftarrow \hat y_1$，之后回到第2步。

通过将向量$\hat y_0$和$\hat y_1$约束在原始图像坐标中的相同像素内来得到第6步中使用的停止准则阈值。较低的阈值将引起减少像素精度。

从实时性约束，我们还将均值漂移迭代次数限制为$Nmax$，通常等于20。在实践中，平均迭代次数要小得多，大约为4次。

自适应尺度

对于给定的目标模型，目标帧中的目标的位置使先前位置估计的邻域中的$d(y)=\sqrt{1-\rho[\hat p(y),\hat q]}$最小化。然而，目标的尺度经常在时间上变化，因此，必须相应地调整核的带宽$h$。

用$h_{prev}$表示前一帧中的带宽。 我们通过运行目标定位算法三次测量当前帧中的带宽$h_{opt}$，带宽$h=h_{prev}$，$h=h_{prev}+\Delta h$，$h=h_{prev}-\Delta h$。 典型值是$\Delta h = 0.1h_{prev}$。 保留最好的结果$h_{opt}$，它能够产生最大的巴氏系数。 为了避免过度敏感的尺度自适应，通过滤波获得与当前帧相关联的带宽

$$h_{new} = \gamma h_{opt}+(1-\gamma)h_{prev}$$

其中，$r$的默认值是0.1。

实验结果

• 将RGB颜色空间作为特征空间，并将其量化为16×16×16个bin。
• e核用于直方图计算，均值漂移迭代基于加权平均值。
• 目标用手动标注椭圆区域初始化。
• 没有假设运动模型。

基于核的跟踪器证明对部分遮挡，杂波，干扰物和相机运动具有鲁棒性。

下图表示通过计算上图中标记的81×81像素矩形的巴氏系数得到的表面，第105帧，MS算法在四次迭代中收敛而没有穷举搜索。

这是一个两分钟的序列，一个人从她进入地铁平台跟踪，直到她上火车（大约3600帧）。 由于图像压缩得到低质量的序列而使跟踪变得更具挑战性。 请注意目标大小的变化。

跟踪算法的扩展

背景信息很重要

• 首先，如果某些目标特征也存在于背景中，则它们与目标定位的相关性会降低。
• 其次，很难准确描绘目标，其模型也可能包含背景特征。
• 背景信息的不当使用可能会影响比例选择算法，从而需要确定适当的目标比例。

考虑目标周围的区域，让$\{\hat o_u\}_{u=1,…,m}$是特征空间中背景的离散表示（直方图），$\hat o^\ast$是其最小的非零项。 权重：

$$\{v_u=\text{min}(\frac{\hat o^\ast}{\hat o_u},1)\}_{u=1,...,m}$$

然后，新的目标模型表示由下式定义：

$$\hat q_u =Cv_u\sum_{i=1}^nk(||x_i^\ast||^2)\delta[b(x_i^\ast)-u],\\ C= \frac{1}{\sum_{i=1}^nk(||x_i^\ast||^2)\sum_{u=1}^mv_u\delta[b(x_i^\ast)-u]}$$

对比之前的：

$$\hat q_u=C\sum_{i=1}^nk(||x_i^\ast||^2)\delta[b(x_i^\ast)-u],\\ C=\frac{1}{\sum_{i=1}^nk(||x_i^\ast||^2)}$$

同样，新的目标候选者表示为：

$$\hat p_u(y)=C_hv_u\sum_{i=1}^{n_h}k(||\frac{y-x_i}{h}||^2)\delta[b(x_i)-u],\\ C_h = \frac{1}{\sum_{i=1}^{n_h}k(||\frac{y-x_i}{h}||^2)\sum_{u=1}^mv_u\delta[b(x_i)-u]}$$

乒乓球从一帧到另一帧的运动大于其自身尺寸。

在具有挑战性的环境下，均值漂移将会失败。

判别性跟踪特征的在线选择

跟踪成功或失败主要取决于物体与周围环境的区别。

• 如果对象非常独特，我们可以使用简单的跟踪器来跟踪它。
• 如果物体具有低对比度或被伪装，我们将仅通过强加关于场景结构或预期运动的先验知识来获得稳健的跟踪。

跟踪器可以区分对象和背景的程度与使用的图像特征直接相关。而大多数跟踪应用程序使用一组先验确定的固定特征进行。许多论文评估不同的色彩空间，以找出要使用的固定特征。然而，这些方法忽略了区分对象和背景的事实是最重要的。 不能总是事先指定背景。

然而，这些方法忽略了区分对象和背景的事实是最重要的。 不能总是事先指定背景。关键问题是在线自适应选择，自适应选择适当的跟踪特征。

目标跟踪被视为一个局部判别问题，有两个类：前景和背景。

上图示出了汽车穿过一片阳光和阴影的低对比度图像的情况。 通过阳光跟踪汽车的最佳特征在阴影中表现不佳，反之亦然。

我们的想法是最能区分对象和背景的特征是跟踪的最佳特征。当物体外观变化时，最具判别性的一组特征也会有所不同。需要解决在线特征选择问题。

特征选择是一种降维的技术，其中从$n$个候选者中选择一组$m$个特征，其中通常$m<<n$。该方法可以通过丢弃不相关或冗余的特征来提高分类性能。

特征选择中的两个主要组成部分是选择标准函数和搜索策略。有很多方法可以评估特征的判别力：增强方差比（AVR）用于特征排序。AVR是要素的类间方差与要素的类内方差之比。

特征子集选择的目标是找到最适合分类任务的$m$个特征。已经证明，特征排序和特征子集选择的组合对于从数千个候选特征中离线选择有判别力的子集是有效的。但要实现在线选择，我们不得不考虑简化的选择标准，非穷举搜索空间和启发式搜索策略。

重要的是要注意，用于跟踪的特征仅需要局部判别，因为对象仅需要与其周围环境明显区分。

采取以下步骤：

1. 定义了一组候选“种子”特征。
2. 使用从最近跟踪的帧中获取的样本计算对象和背景类的特征值的分布。
3. 使用对数似然比生成一个函数，该函数将与对象关联的特征值映射到正值，将与背景关联的特征值映射到负值。（这是将每个“种子”特征非线性转换为新的“调整”特征。）
4. 使用两类方差比来评估调整的候选特征，以测量前景/背景类的分布的可分离性。
5. 最具判别力的特征用于将权重值分配给新的帧中的像素，从而产生权重图像，其中对象像素具有高值并且背景像素具有低值。
6. 将均值漂移算法应用于该权重图像表面，以估计当前帧中对象的2D位置。

“种子”特征

可以使用各种特征进行跟踪，包括颜色，纹理，形状和运动。我们使用应用于局部图像窗口内的R，G，B像素值的滤色器组响应的直方图来表示目标外观。种子候选特征集由摄像机R，G，B像素值的线性组合组成：

$$\mathcal{F} \equiv \{ w_1R+w_2G+w_3B | w_\ast \in [-2,-1,0,1,2] \}$$

也就是说，由-2和2之间的整数系数组成的线性组合。这种候选者的总数将是$5^3$。

通过修剪冗余系数$(w_1’,w_2’,w_3’)=k(w_1,w_2,w_3)$和防止$(w_1,w_2,w_3)=(0,0,0)$，我们留下了49个特征池。

所有特征都归一化到0到255范围内，并进一步离散化为32或64个bin的直方图。

接下来是创建“调整”特征。

“调整”特征

该方法通过计算对象和背景的特征值分布的对数似然比，基于类条件分布来变换每个种子特征。

1. 首先，它创建一个“调整”的新特征，以区分对象和背景像素。
2. 其次对于具有良好判别力的特征，该方法将潜在的多模式对象和背景分布合并成单峰分布。
3. 选择覆盖对象的矩形像素组来表示对象像素，而选择较大的周围像素环来表示背景。

我们通过将每个直方图归一化其中的元素数量，为对象形成经验离散概率分布$p(i)$，并为背景形成q$(i)$。

“调整”特征变为类条件“种子”特征分布的对数似然比。 给出特征值$i$的对数似然比：

$$L(i)=log\frac{\text{max}\{p(i),\delta\}}{\text{max}\{q(i),\delta\}}$$

非线性对数似然比将对象/背景分布映射为对象颜色的正值，将与背景关联的颜色映射为负值。将这些对数似然比值反投影到图像中，产生适合于跟踪的权重图像。

评估特征的判别力

我们想要使用两类方差比来测量调整特征$L(i)$在对象和背景类之间的可分性。

使用等式$\text{var}(x)=Ex^2-(Ex)^2$，我们计算$L(i)$相对于对象类分布$p(i)$的方差为：

$$\begin{align*} var(L;p)&=E[L^2(i)]-(E[L(i)])^2\\ &=\sum_i p(i)L^2(i)-[\sum_ip(i)L(i)]^2 \end{align*}$$

并且类似地用于背景类分布$q(i)$。

对数似然函数的方差比现在可以定义为：

$$\text{VR}(L;p,q) \equiv \frac{\text{var}(L;(p+q)/2)}{[\text{var}(L;p)+\text{var}(L;q)]}$$

方差比背后的直觉是我们希望对象和背景上的像素的对数似然值被紧密聚类（低类内方差），而理想情况下两个类别应尽可能地分开（高类间方差）。

排名权重图像

下图示出了在基于两类方差比度量对特征进行排序之后，由所有49个候选特征产生的样本对象和权重图像集。

跟踪

特征排序机制嵌入在跟踪系统中，如图所示。

上图为具有在线自适应特征选择的跟踪系统。 前一帧中的对象和背景像素的样本引导候选特征的评估，从而导致基于判别力的特征的等级排序。 将前$N$个最佳特征应用于当前帧以计算$N$个权重图像。 将均值漂移过程应用于每个权重图像以计算2D位置估计。组合这些$N$个估计以确定当前帧中对象的最佳位置并且过程迭代。

1. 给定被跟踪对象的先前位置，从前一帧中对对象和背景像素进行采样。
2. 使用方差比对潜在跟踪要素进行排名，以确定每个要素如何区分对象与背景。
3. 前$N$个最具判别力的个体特征用于计算当前帧的权重图像。
4. 由于视频的连续性，当前帧中的对象和背景特征的分布与前一帧保持相似，并且最具判别力的特征仍应有效。
5. 在$N$个新的权重图像中的每一个中初始化局部均值漂移过程。 这些均值漂移过程收敛于当前帧中对象的2D位置的$N$个估计。
6. 使用初始中值估计量。 选择中位数而不是均值来试图增加对任何单个均值漂移过程的鲁棒性，从而产生较少汇总估计的对象位置的错误估计。
7. 更新目标模型：因此，估计的特征分布是初始和当前特征分布的直接平均值。

下图显示了一条迹线，显示49个中的哪五个特征被选择为对跟踪序列的每个帧最具判别力。

方差比的缺点

方差比在计算上是高效的，并且在选择能够最大化前景物体与周围背景之间的整体对比度的特征方面做得很好。但是，它最适合于相对均匀的背景，并且当跟踪物体附近存在附近的干扰物时，它不一定是最佳使用方法。

References

• Dorin Comaniciu, Visvanathan Ramesh, Peter Meer: Kernel-Based Object Tracking. IEEE Trans. Pattern Anal. Mach. Intell. 25(5): 564-575 (2003)
• Robert T. Collins, Yanxi Liu, Marius Leordeanu: Online Selection of Discriminative Tracking Features. IEEE Trans. Pattern Anal. Mach. Intell. 27(10): 1631-1643 (2005)

七、用于跟踪的粒子滤波

密集视觉杂乱元素中跟踪曲线的问题具有挑战性。因为背景杂乱中的元素可能会模仿前景特征的一部分。而卡尔曼滤波是不适合的，因为它基于单峰高斯分布假设，并不能用于其他假设。因为杂乱元素导师密度为多模态，所以需要考虑非单高斯模型。

卡尔曼滤波器是递归线性估计器，是概率密度传播过程的特例。 它仅适用于高斯密度。在单高斯情形中，扩散是纯线性的，密度函数演变为高斯脉冲，可以平移，扩散和加强，始终保持高斯状态，如图所示。

• 确定性分量导致密度函数漂移。
• 动态模型的随机分量导致了不确定性的不断扩大。
• 外部观察的作用是在扩散上叠加反应效应。

在杂乱元素中，通常会有几个相互竞争的观测结果，这些结果倾向于鼓励非高斯状态密度，如下图。

Condensation算法旨在解决这种更普遍的情况，一种比卡尔曼滤波器更简单的算法。它使用“因子化抽样”，其中可能解释的概率分布用随机生成的集合表示。使用学习到的动态模型和视觉观察，随时间传播随机集。尽管使用了随机抽样，但它几乎是实时运行的。

粒子滤波跟踪

时间$t$的建模对象的状态表示为$x_t$及其历史$\mathcal{X}_t=\{x_1,…,x_t\}$。类似地，时间$t$处的图像特征集合是具有历史$\mathcal{Z}_t=\{z_1,…,z_t\}$的$z_t$。

在一般处理中，对密度不作任何假设（线性、高斯、单模态）。对于概率框架，一般假设对象的动态形成一个时间马尔可夫链，即：

$$p(x_t|\mathcal{X}_{t-1})=p(x_t|x_{t-1})$$

即，新状态仅受前一状态的限制，与先前的历史无关。其动态由条件密度$p(x_t|x_{t-1})$的形式决定。

步长为标准正态变量的一维随机游动，以单位速度向右漂移叠加，写为：

$$p(x_t|x_{t-1}) \propto \text{exp}(-\frac{1}{2}(x_t-x_{t-1}-1)^2)$$

度量：$z_t被$认为是相互独立的，相对于动态过程是独立的。根据$p(\mathcal{Z}_t|\mathcal{X}_t)=\prod_{i=1}^tp(z_i|x_i)$，得到：

$$p(\mathcal{Z}_{t-1},x_t|\mathcal{X}_{t-1})=p(x_t|\mathcal{X}_{t-1})\prod_{i=1}^{t-1}p(z_i|x_i)$$

贝叶斯法则：

• $p(A,B)=p(B|A)p(A)$
• $p(A|B)=\frac{p(A,B)}{p(B)}=\frac{p(B|A)p(A)}{p(B)}$
• $p(A_i|E)=\frac{p(E|A_i)p(A_i)}{p(E)}=\frac{p(E|A_i)p(A_i)}{\sum_ip(E|A_i)p(A_i)}$

扩散

给定具有独立观测值的连续值马尔可夫链，时间$t$处的条件状态密度$p_t$由下式定义：

$$p_t(x_t)=p(x_t|\mathcal{Z_t})$$

随着时间的推移传播状态密度的规则是：

$$p(x_t|\mathcal{Z}_t)=k_tp(z_t|x_t)p(x_t|\mathcal{Z}_{t-1})$$

其中，$p(x_t|\mathcal{Z}_{t-1})=\int_{x_{t-1}}p(x_t|x_{t-1})p(x_{t-1}|\mathcal{Z}_{t-1})$。

传播规则应解释为从数据推断后验状态密度。有效先验$p(x_t|\mathcal{Z}_{t-1})$实际上是从前一时间步的后验取得的预测，$p(x_{t-1}|\mathcal{Z}_{t-1})$在动态模型$p(x_t|\mathcal{Z}_{t-1})=\int_{x_{t-1}}p(x_t|x_{t-1})p(x_{t-1}|\mathcal{Z}_{t-1})$上叠加一个时间步。

由于观测密度非高斯分布，状态密度$p(x_t|\mathcal{Z}_t)$也非高斯分布。现在的问题是如何应用非线性滤波器来评估状态密度随时间的变化，而不需要过多的计算负载。

因子化采样

后验密度$p(x|z)$表示可从数据中推导出的关于$x$的所有知识。根据贝叶斯法则，

$$p(x|z)=kp(z|x)p(x)$$

因子化采样算法从近似于后验$p(x|z)$的分布生成随机变量$x$。

首先，从先验密度$p(x)$生成样本集$\{s^{(1)},…,s^{(N)}\}$，然后以概率$\pi_n$选择索引$n \in \{1,…,N\}$，其中：

$$\pi_n=\frac{p_z(s^{(n)})}{\sum_{j=1}^Np_z(s^{(j)})}$$

且$p_z(x)=p(z|x)$为条件观测密度。

condensation算法

condensation算法基于因子化采样，但扩展为迭代地应用于序列中的连续图像。

假设每个时间步骤的过程是一个因子化抽样，迭代的输出将是加权的样本集，用权重$\pi_t^{(n)}$表示为$\{s_t^{(n)},n=1,…,N\}$，表示在时间$t$时$p(x_t|\mathcal{Z}_t)$近似的条件状态密度。

它是由$p(x_{t-1}|\mathcal{Z}_{t-1})$的样本集表示$\{(s_{t-1}^{(n)},\pi_{t-1}^{(n)}),n=1,…,N\}$得到的，即前一时间步的输出。

在图的顶部，时间步$t-1$的输出是加权样本集$\{s_{t-1}^{(n)},\pi_{t-1}^{(n)},n=1,…,N\}$。目的是在连续的时间步长中保持固定大小$N$的样本集。第一个操作是从集合$\{s_{t-1}^{(n)}\}$中抽样$N$次，选择一个概率为$\pi_{t-1}^{(n)}$的给定元素。有一些元素，特别是那些权重高的元素，可能会被多次选择，导致新集合中元素的相同副本。其他权重相对较低的人可能根本就没有被选择。

从新集合中选择的每个元素现在都要经过预测步骤。

1. 首先，漂移元素，并且由于这是确定性的，因此新集合中的相同元素经历相同的漂移。
2. 然后进行扩散，是随机的，相同的元素现在被分开，因为每个元素都经历了自己独立的运动步骤。在此阶段，已生成新时间步的样本集，但尚未生成其权重。
3. 最后，采用观测步骤，从观测密度中产生权重。

结果

基于颜色的粒子滤波跟踪

粒子滤波已被证明非常成功用于非线性和非高斯估计问题。如何定义相似性测量对于基于PF的跟踪器的性能非常重要。

颜色直方图对于跟踪非刚性物体具有许多优点，因为它们对部分遮挡是稳健的，是旋转和尺度不变的并且是有效计算的。

使用粒子滤波器跟踪目标，方法是使用巴氏距离将其直方图与样本位置的直方图进行比较。与均值漂移跟踪器相比，采用多个假设的跟踪器可以在杂乱和遮挡的情况下更可靠地跟踪对象。作者在粒子滤波的框架中使用颜色直方图和多个假设。

粒子滤波的关键思想是通过加权样本集$S=\{(s^{(n)},\pi^{(n)}|n=1,…,N\}$来近似概率分布。每个样本$s$代表对象的一个假设状态，具有相应的离散采样概率$π$，其中$\sum_{n=1}^N \pi^{(n)}=1$。

通过根据系统模型传播每个样本来描述样本集的演变过程。然后根据观察值对该组的每个元素进行加权。

通过以下步骤估计对象的平均状态：

$$E[S]=\sum_{n=1}^N\pi^{(n)}s^{(n)}$$

颜色分布模型

假设分布被离散化为$m$个bin。使用函数$h(x_i)$生成直方图，该函数将位置$x_i$处的颜色分配给相应的bin。

在我们的实验中，直方图通常使用$8\times8\times8$ bin在RGB空间中计算。为了使算法对光照条件不太敏感，可以使用HSV颜色空间对V具有较低的灵敏度（例如，$8\times 8\times 4$ bin）。

它使用垂直椭圆形区域内的颜色分布。为了在边界像素属于背景或被遮挡时增加颜色分布的可靠性，通过使用加权函数将更小的权重分配给更远离区域中心的像素：

$$k(r)=\left\{ \begin{aligned} & 1-r^2 &&r<1 \\ & 0 && otherwise \end{aligned} \right.$$

其中$r$是距离区域中心的距离。

位置$y$处的颜色分布$p_y=\{p_y^{(u)}\}_{u=1,…,m}$计算如下：

$$p_y^{(u)}=f\sum_{i=1}^Ik(\frac{||y-x_i||}{a}\delta[h(x_i)-u])$$

其中，$a=\sqrt{H_x^2+H_y^2}$，$f=\frac{1}{\sum_{n=1}^Ik(\frac{||y-x_i||}{a})}$。

回想一下，对象的估计状态如下：

$$E[S]=\sum_{n=1}^N\pi^{(n)}s^{(n)}$$

因此，我们需要一种相似性度量，它基于论文中的颜色分布来计算每个样本的权重。

考虑离散密度，例如我们的颜色直方图$p=\{p^{(u)}\}_{u=1,…,m}$和$q=\{q^{(u)}\}_{u=1,…,m}$，系数被定义为

$$\rho[p,q]=\sum_{u=1}^m\sqrt{p^{(u)}q^{(u)}}$$

作为两个分布之间的距离，作者使用巴氏距离：

$$d=\sqrt{1-\rho[p,q]}$$

为了对样本集进行加权，必须在目标直方图和假设的直方图之间计算巴氏系数。

样本的权重写为：

$$\pi{(n)}=\frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{d^2}{2\sigma^2}}=\frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{(1-\rho[p_s(n),q])}{2\sigma^2}}$$

由方差$σ$的高斯分布指定。

下图示出了图1所示的足球运动员的矩形区域的巴氏系数。

目标模型更新

通过丢弃图像异常值，其中对象被遮挡或太嘈杂，可以确保当跟踪器丢失对象时不更新模型。

要执行上述操作，更新条件为：

$$\pi_{E[S]}>\pi_T$$

其中$\pi_{E[S]}$为平均状态$E[S]$的观测概率，$\pi_T$为阈值。

通过以下式子（$a$是学习速率）为每个bin实现目标模型的更新：

$$q_t^{(u)}=(1-\alpha)q_{t-1}^{(u)}+\alpha p_{E[S_t]}^{(u)}$$

结果

用于视觉跟踪的核粒子滤波器

PF在处理多模态概率密度函数方面取得了良好的性能。然而，当动态系统具有非常小的系统噪声或观察噪声具有非常小的方差时，PF表现不佳。在这种情况下，粒子集合在状态空间中迅速坍缩为一个点。采用大量（和或可变）粒子来改善PF的方法则不太理想。标准的PF经常不能产生一个捕捉“不规则”运动的粒子集，导致逐渐漂移的估计和最终的目标损失。

作者提出了一种新的粒子滤波器：核粒子滤波器（KPF）。KPF估算核密度的梯度，并将粒子移向后验模式，从而更有效地分配粒子。利用均值漂移算法实现了梯度估计和粒子分配。给定$t$时刻的粒子集合：$s_t=\{s_t^{(n)}\}_{n=1}^N$和相关的权值$\{w_t^{(n)}\}_{n=1}^N$，用核$K$估计后验核密度可表示为：

$$\hat p(x_t|Y_t) = \sum_{n=1}^N K_\lambda(x_t-s_t^{(n)})w_t^{(n)}$$

其中$K_\lambda$是由核宽度$\lambda$缩放的核：

$$K_\lambda(x_t-s_t^{(n)})=\frac{1}{\lambda^{n_x}}K(\frac{x_t-s_t^{(n)}}{\lambda})$$

选择核和宽度以便最小化后验PDF和相应的核估计之间的平均积分平方误差（MISE）。当使用高斯核并且后验也是具有单位协方差矩阵的高斯核时，最佳核宽度由下式给出：

$$\lambda_{opt}=(\frac{4}{(n_x+2)N})^{\frac{1}{n_x+4}}$$

当密度通常是多模式时，我们让$\lambda=\lambda_0=(1/2)\lambda_{opt}$。

给定后验估计 $\hat p(x_t|Y_t)=\sum_{n=1}^NK_\lambda(x_t-s_t^{(n)})w_t^{(n)}$，我们现在估计其梯度并通过使用MS将粒子沿着梯度方向朝向后验模式移动。每个粒子移动到其样本均值，由下式确定：

$$m(s_t^{(n)})=\frac{\sum_{l=1}^NH_\lambda(s_t^{(n)}-s_t^{(l)})w_t^{(l)}s_t^{(l)}}{\sum_{l=1}^NH_\lambda(s_t^{(n)}-s_t^{(l)})w_t^{(l)}}$$

其中为任意核。

均值漂移可以重复应用于粒子集。当粒子改变位置时出现问题：新粒子不再遵循后验分布。在KPF中，这是通过重新加权粒子来补偿的。表示时刻第$i$个均值漂移过程后的粒子集为$\{s_{t,i}^{(·)}\}$，在每个均值漂移过程后，在新的粒子位置重新计算权值：

$$w_{t,i}^{(n)}=\frac{p(s_{t,i}|Y_t)}{q_{t,i}(s_{t,i}^{(n)})}$$

其中$q_{t,i}(x_t)=\sum_{l=1}^NK_\lambda(x_t-s_{t,i}^{(l)})$。

两到五次迭代足以将粒子移动到三维到九维空间中的高概率区域附近。为了防止密度中的局部平台过早停止梯度上升，在每次迭代时会向粒子添加一个小的扰动。

结果

混合粒子滤波

跟踪不同数量的非刚性物体的问题有两个主要困难：首先，观测模型和目标分布可以是高度非线性和非高斯的。其次，存在大量不同数量的对象会产生重叠和模糊的复杂交互。

一种有效的方法是将混合粒子滤波器与Adaboost相结合。混合粒子滤波器非常适合多目标跟踪，因为它为每个参与者分配混合成分。

混合粒子滤波器的关键问题是建议分布的选择和进出场景物体的处理。建议分布可以使用一个混合模型来构建，该模型包含了来自每个参与者的动态模型和Adaboost生成的检测假设的信息。学习到的Adaboost建议分布允许快速检测进入场景的参与者，而滤波过程使人们能够跟踪各个参与者。

大多数多目标跟踪采用固定数量的对象。要有效管理不同数量的对象，重要的是要有一个自动检测过程。BraMBLe有一个基于固定背景建模的自动目标检测系统。作者将放宽固定背景的假设，使能够适用于变化的背景。当多目标的后验是多模态时，粒子滤波器可能表现不佳。Vermaak等人引入了混合粒子滤波器（MPF），其中每个组件都用一个单独的粒子滤波器建模。BPF是基于MPF的。

作者采用基于色调饱和度值（HSV）颜色直方图的多色观测模型。HSV直方图由$N=N_hN_s+N_v$个区间组成，并且表示$b_t(d) \in \{1,…,N\}$作为与时间$t$处的像素位置$d$处的颜色矢量$y_t(k)$相关联的bin索引。

时间$t$处颜色分布的核密度估计由下式给出：

$$k(n;x_t)=\eta\sum_{d \in R(x_t)} \delta[b_t(d)-n]$$

其中$\delta$是$\delta$函数，$\eta$是一个标准化常数，它确保$k$是概率分布$\sum_{n=1}^Nk(n;x_t)=1$，而位置$d$可以是$R(x_t)$内的任何像素位置。

如果我们将$K^\ast = \{k^\ast(n;x_0\}_{n=1,…,N}$表示为参考颜色模型，而将$K(x_t)$表示为候选颜色模型，那么我们需要测量$K^\ast$和$K(x_t)$之间的数据（即相似性）。我们应用巴氏系数来定义HSV直方图上的距离$\xi$。

$$\xi[K^\ast,K(x_t)]=\left [1-\sum_{n=1}^N \sqrt{k^\ast (n; x_0)k(n; x_t)} \right]^{\frac{1}{2}}$$

一旦我们获得HSV颜色直方图上的距离，我们使用如下似然分布：

$$p(y_t|x_t) \propto e^{-\lambda\xi^2[K^\ast,K(x_t)]}$$

其中$\lambda$是20。

当我们考虑颜色分布的空间布局时，得到了更好的近似。如果我们将跟踪区域定义为$r$个子区域$R(x_t)=\sum_{j=1}^rR_j(x_t)$的总和，则将似然性计算为与每个子区域相关联的参考直方图的总和：

$$p(y_t|x_t) \propto e^{\sum_{j=1}^r-\lambda\xi^2[K_j^\ast,K_j(x_t)]}$$

为了处理多个目标，后验分布被建模为$M$个分量非参数混合模型：

$$p(x_t|y_{0:t})=\sum_{j=1}^M \Pi_{j,t}P_j(x_t|y_{0:t})$$

其中，混合权重满足$\sum_{m=1}^M \Pi_{m,t}=1$。

它从适当的建议分布$\tilde x_t^i \sim q(x_t|x_{0:t-1},y_{0:t})$中对候选粒子进行采样。在最简单的场景中，它被设置为$q(x_t|x_{0:t-1},y_{0:t})=p(x_t|x_{t-1})$。

这些粒子按以下重要性比加权：

$$w_t^i = w_{t-1}^i \frac{p(y_t|\tilde x_t^i)p(\tilde x_t^i|x_{t-1}^i)}{q(\tilde x_t^i|x_{0:t-1}^i,y_{0:t})}$$

混合粒子滤波器引入了MPF的两个重要扩展：

1. 它使用Adaboost构建建议分布。 它结合了最近在建议分布中的观测（通过Adaboost检测），并且大大优于朴素转换的先前建议。
2. Adaboost提供了一种获取和维护混合表示的机制。 它允许我们有效地检测离开和进入场景的对象。

作者采用了最初用于检测人脸的Viola和Jones的级联Adaboost算法。作者采用了最初用于检测人脸的Viola和Jones的级联Adaboost算法。

将Adaboost合并到建议分布中

通过考虑合理的运动，可以减少误报的数量。建议分布的表达式如下所示：

$$q_B^\ast(x_t|x_{0:t-1},y_{1:t})=\alpha q_{ada}(x_t|x_{t-1},y_t)+(1-\alpha)p(x_t|x_{t-1})$$

其中，$q_{ada}$是高斯分布，参数$\alpha$可以动态设置。当$\alpha=0$时，BPF降低为MPF。通过增加$\alpha$，它更加重视Adaboost检测。

结果

总结

前面还好，看到混合粒子滤波那里就彻底懵了。

References

• M. Isard and A. Blake. Condensation–conditional density propagation for visual tracking. Int. J. Computer Vision, 29(1):5–28, 1998.
• S. Arulampalam, S. Maskell, N. Gordon, and T. Clapp, “A tutorial on particle filters for on-line non-linear/non-Gaussian Bayesian tracking,” IEEE Transactions on Signal Processing, vol 50 pp. 50, pp.174–188, Feb. 2002.
• K. Nummiaroa, E. Koller-Meierb, L. V. Gool, “An adaptive color-based particle filter” Image and Vision Computing 21 (2003) 99 , Image and Vision Computing 21 (2003) 99– 110
• C.Chang, and R. Ansari, “Kernel Particle Filter for Visual Tracking”, IEEE SIGNAL PROCESSING LETTERS, VOL. 12, NO. 3, pp242-245, 2005
• K. Okuma, et al., “A Boosted Particle Filter: Multitarget Detection and Tracking”, ECCV 2004 (2004), pp. 28-39.

八、多线索跟踪

多线索跟踪

粒子滤波框架的一个重要优点是它允许来自不同测量源的信息以某种原则的方式融合。之前与粒子滤波器的数据融合主要局限于面部和手部跟踪环境中简单轮廓形状内部和周围的肤色和边缘线索。

作者提出了一种基于粒子滤波器的视觉跟踪器，它以一种新颖的方式融合了三种线索：颜色，运动和声音，即它将颜色作为主要的视觉提示并将其与声音定位线索或运动活动线索融合在一起。

目标跟踪任务的目标是跟踪视频中的指定对象。作者使用弱对象模型，以免对对象类型过于严格，并对对象姿势，光照，运动等的大变化实现鲁棒性。

在这种情况下，轮廓线索不如颜色线索适合于表示被跟踪实体的视觉外观。基于边缘的线索的使用要求先前已知要跟踪的对象类别，并且可以预先学习精确的轮廓模型。

作者使用基于直方图的颜色模型。 似然性建立在假设区域中的经验颜色分布与参考模型之间的直方图距离上。它使用类似于颜色似然性的形式，基于直方图连续帧差异引入运动线索。

对于视听跟踪，系统设置包括单个摄像头和一对立体声麦克风。然后通过测量到达两个麦克风的信号之间的到达时间延迟（TDOA）来获得声音定位提示。

颜色线索往往非常持久，并且对姿势和照明的变化具有鲁棒性。然而，它们更容易出现歧义，特别是如果场景包含以与感兴趣对象的颜色分布类似的颜色分布为特征的其他对象。另一方面，运动和声音提示倾向于是间歇性（断断续续的）的，但是当它们存在时是非常有判别性的，即，它们能够以低歧义性定位对象。

声音线索仅在图像的水平方向上给出定位信息，我们可以首先搜索该方向，并将搜索限制在状态空间的剩余部分中，以将水平图像分量视为高度可能包含该对象感兴趣的区域。

对于多个测量源，仍然可以应用通用粒子滤波框架。然而，可以通过利用模型结构与各种测量模态中的信息之间的关系来设计提高粒子滤波器效率的策略。

假设我们有测量源，因此瞬时测量矢量可以写成$y=(y^1,…,y^M)$。

我们还假设在给定状态的情况下测量是有条件独立的，因此似然性可以被分解为，

$$p(y|x)=\prod_{m=1}^Mp(y^m|x)\\ p(x|x')=\prod_{m=1}^Mp(x_m|x_m')$$

对于视听跟踪，系统设置包括单个摄像头和一对立体声麦克风。连接麦克风的线穿过摄像机的光学中心，并与摄像机光轴正交。

与自然离散化的视频序列相反，音频样本连续到达，并且没有自然音频帧的概念。原始图像和音频帧包含许多关于对象跟踪的冗余信息。它通过信号处理传递原始数据，以提取对跟踪过程重要的特征。

动态模型

状态演化模型可以写成，

$$p(x_n|x_{n-1})=(1-\beta_u)\mathcal{N}(x_n|x_{n-1},\Lambda)+\beta_u\mathcal{U}_{\mathcal{X}}(x_n)$$

其中$\mathcal{N}(·|\mu,\Sigma)$表示均值为$\mu$，方差为$\Sigma$的高斯分布，$\mathcal{U}_\mathcal A(·)$表示$\mathcal {A}$上的均匀分布，$0\le\beta_u\le1$是均匀分布成分的权重，$\Lambda=diag(\sigma_x^2,\sigma_y^2,\sigma_\alpha^2)$，具有对象状态的成分上的随机游走模型的方差的对角矩阵。

颜色线索

轮廓线索对于具有独特形状的物体非常有用。但是，杂乱的边缘可能会严重污染它们。 它们可能不适用于没有要跟踪的预定义对象类的场景。

作者使用RGB并使用巴氏相似系数：

$$D(h_1,h_2)=\left(1-\sum_{i=1}^B\sqrt{h_{i,1}h_{i,2}} \right)^{1/2}$$

颜色似然模型写为：

$$p(y^C|x) \propto \text{exp}\left(-\sum_{c\in\{R,G,B\}}D^2(h_x^c,h_{ref}^c)/2\sigma_C^2 \right)$$

运动线索

在静止摄像头的情况下，作者提出将帧差信息嵌入似然模型中，类似于为颜色测量开发的模型，以利用运动线索。

运动似然模型写为：

$$p(y^M|x) \propto \text{exp}(-D^2(h_x^M,h_{ref}^M)/2\sigma_M^2)$$

其中参考运动直方图是均匀的：

$$h_{i,ref}^M=\frac{1}{B},\ \ \ \ i=1,...,B$$

且$h_x^M$是基于时间 $t$ 和 $t-1$ 处的亮度的绝对差的测量直方图。

声音线索

声音线索是间歇性的，但是在它存在时可能有很强的判别性。

通过测量到达包括该对的两个麦克风的音频信号之间的TDOA来获得声音定位线索。广义交叉相关函数（GCCF）的最大化用于估计TDOA。

作者通过假设候选TDOA测量值是独立的，开发了TDOA测量的多假设似然模型。

所提出的方法使用颜色作为主要线索并将其与声音定位线索中的信息融合。 这适用于视频电话会议应用。

声音似然仅提供关于图像中的对象 $x$ 坐标的信息。因此，它首先模拟和重新采样 $x$ 分量，然后模拟剩余状态分量（对象 $y$ 坐标和比例因子）的新值。

第二个设置用于涉及静止摄像机的监视应用程序。 它将颜色与运动定位线索融合在一起。

在模拟比例因子之前，它首先模拟和重新采样关于运动可能性的位置参数。

利用前景背景纹理识别进行鲁棒跟踪

许多跟踪方法隐含地假设前景或背景的某些属性是恒定的或至少是可预测的。这些假设可能会被广泛的常见情况所破坏，例如部分或完全遮挡，光照变化，旋转等。

最好将两个层的信息组合在一起，并将跟踪视为前景-背景分类问题。作者将跟踪视为对目标的动态区分，而不是跟踪过程中在线学习的定位背景。

模板跟踪器专注于对象外观，它们倾向于忽略同样重要的背景数据。从背景中获取的信息可以作为目标要避免的负面例子。

剩下的问题包括所使用的特征的较差的判别力，对高斯模型假设的敏感性，以及在处理目标/背景的外观的剧烈变化方面的失败。

本文提出了一种使用前景/背景判别范例的新型跟踪方法。它使用纹理特征进行辨别，从而获得比颜色更好的判别力。不是像在共同模板匹配中那样最大化与目标的相似性度量，而是通过最大化区别分数来将目标与背景区分开。因此，该方法对于场景中的变化将更加鲁棒。它不需要任何先前的目标知识。 该算法对于视角和光照条件的剧烈变化是稳健的。摄像头可以移动，背景可以发生改变。

在所提出的算法中，通过最大化与纹理特征空间中的背景的区别来检测被跟踪对象。与强度和颜色相比，纹理具有更高的判别力，同时保留了良好的局部性。前景/背景区别由在线训练的区别函数量化。

首先，我们考虑对象纹理的表示。可以使用Gabor滤波器分析对象纹理的变换补偿图像 $I(\phi(p;θ))$。每对Gabor滤波的形式如下：

$$G^s(p)=cos(\frac{p}{r}·n_v)\text{exp}(-\frac{||p||^2}{2\sigma^2})\\ G^a(p)=sin(\frac{p}{r}·n_v)\text{exp}(-\frac{||p||^2}{2\sigma^2})\\$$

其中$\sigma, r, v$分别表示尺度，中心频率，方向，$n_v=\{cos v,sin v\}$。

将这些参数设置为一系列值会创建一组过滤器。 把他们表示为 $G_1,…,G_K$。像素 $p$ 处的对象纹理由向量$f(p)\in \mathbb{R}^K$表示，向量$f(p)\in \mathbb{R}^K$由图像$I(\phi(q;θ))$对Gabor滤波器的响应组成：

$$[f(p)]_k=\sum_{q\in \mathbb{R}^2}G_k(p-q)I(\varphi(q;\theta))$$

其中，$[f(p)]_k$表示$f(p)$的第$k$个组成。

候选目标的出现由$n$个采样像素处的纹理向量的有序集合表示，$p_1,…,p_n$，见图1：

目标检测相当于根据两个标准找到给出最佳$\mathcal{F}$的参数$θ$：

1. $\mathcal {F}$与一组对象特征$\mathcal{F_O}$之间的相似性，

   $$\mathcal{F_O}=[f_1^o,...,f_n^o]$$

   $\mathcal{F}$和$\mathcal{F_O}$中向量的顺序也是有价值的信息。也就是说，$f(p_i)$应该特别匹配$f_i^o$，因为它们都表示$p_i$。

2. $\mathcal {F}$与一组背景模板特征之间的对比，

   $$\mathcal{F_B}=\{f_1^b,...,f_M^b\}, \ \ \ f_j^b\in \mathbb{R}^K$$

   这些是当前目标位置附近的背景图案的纹理向量。通过在围绕对象的上下文窗口中采样，在线获得背景图案集，如下图中的示例。该标准意味着目标窗口中的每个$f(p_i)$应该与所有$f_j^b$区分开。

   

当我们考虑在前景和背景的不同外观条件下的跟踪时，上述两组特征是需要随时间更新的动态量。通过最大化一组区别函数的总和来执行搜索具有满足上述两个标准的特征 $\mathcal{F}$ 的图像区域：

$$\text{max}_\theta \sum_{i=1}^ng_i(f(p_i;\theta))$$

这里，$g_i(f(p_i;\theta))$是区分像素 $p_i$ 处的对象纹理与所有背景纹理的区别函数。我们选择$g_i$作为线性函数：

$$g_i(f)=a_i^Tf+b_i$$

其中，$a_i\in\mathbb{R}^K$，$b_i\in\mathbb{R}$是参数。每个 $g_i$ 都经过训练，以便：

$$g_i(f_i^o)>0,\ \ 且\ \ \forall f\in\mathcal{F_B}:g_i(f)<0$$

对于目标检测，基于 $g_i$ 最大化的方法可以容忍目标外观的更多变化，而不是最小化到目标模型 $f_i^o$ 的距离测量的常见方法。这在下图中示出。

根据 $g_i$（$g_i(f)=a_i^Tf+b_i$）的定义，我们需要最大化：

$$\text{max}_\theta\sum_{i=1}^na_i^Tf(p_i;\theta)+b_i$$

常数参数 $b_i$ 不影响最大化结果，因此可以被移除。

回看$[f(p)]_k=\sum_{q\in\mathbb{R}^2}G_k(p-q)I(\phi(q;\theta))$，我们可以重写上面的等式，如：

$$\text{max}_\theta\sum_{q\in\mathbb{R}^2}I(\phi(q;\theta))w(q)$$

其中，$w(q)=\sum_{i=1}^n\sum_{k=1}^Ka_{ik}G_k(p_i-q)$。

原则上，任何线性分类器都可用于训练 $g_i$ 。但是，鉴于训练集的动态特性，所选分类器应允许以增量模式进行训练。此外，它应该在计算上易于实时跟踪。为此，作者采用LDA（线性判别分析）。函数 $g_i$ 最小化了 $a_i$ 和 $b_i$ 的成本函数。

$$\text{min}_{a_i,b_i}(a_i^Tf_i^o+b_i-1)^2+\sum_{j=1}^M\alpha_j(a_i^Tf_j^b+b_i+1)^2+\frac{\lambda}{2}||a_i||^2$$

闭式解为：

$$a_i=_\mathcal{K_i}[\lambda I+B]^{-1}[f_i^o-\overline f^b]$$

其中，$\overline f^b=\sum_{j=1}^M\alpha_jf_j^b$，$B=\sum_{j=1}^M\alpha_j[f_j^b-\overline f^b][f_j^b-\overline f^b]^T$，$_{K_i}=\frac{1}{1+\frac{1}{2}[f_i^o-\overline f^b]^T[\lambda I+B]^{-1}[f_i^o-\overline f^b]}$。

区别函数仅取决于对象特征$f_i^o$，平均向量 $\overline f^b$ 和背景中所有纹理图案的协方差矩阵$B$，其可以在跟踪期间更新。

需要更新特征向量 $f_i^o$ 以跟踪前景的变化外观。然而，过快更新会容易导致突然的跟踪失败并且导致目标窗口的漂移。这是通过简单的衰变来完成的：

$$f_i^{o(t)}=(1-\gamma)f_i^{o(t-1)}+\gamma f(p_i;\theta)$$

背景模型也类似：

$$\begin{align*} \overline f^{b(t)}&=(1-\gamma)\overline f^{b(t-1)} + \gamma \overline f_{new}^b,\\ B^{(t)}&=(1-\gamma)B^{(t-1)} + (1-\gamma)\overline f^{b(t-1)}\overline f^{b(t-1)T}-\overline f^{b(t)}\overline f^{b(t)T}+\frac{\gamma}{m}\sum_{j=M+1}^{M+m}f_j^bf_j^{bT} \end{align*}$$

其中，$\overline f_{new}^b=\frac{1}{m}\sum_{j=M+1}^{M+m}f_j^b$。

基于定位/分割的跟踪

在前景和背景在外观上相似，存在快速变化或变形的物体外观以及背景高度可变的情况下，跟踪仍然是困难的。更具挑战性的任务是通过视频序列从背景精确地分割目标区域。作者以非参数形式的“图像片块（patch）袋”得到了两类前景/背景外观模型。对于分割，它利用“超像素”的概念来空间自适应地对来自给定图像帧的视觉表示两类随机片进行采样。

作者提出了两种算法：

算法1：基于定位的跟踪

算法1跟踪的步骤为：

1. 图像采样以生成前景/背景外观表示
2. 类条件图像模型匹配以生成似然或置信度图
3. 高置信/似然模式搜索跟踪
4. 用于非参数外观模型更新的双向一致性检查和重采样

设 $p$ 表示图像块，$\mathcal{P}$ 表示从图像采样的一组块，$Ω$ 表示块模型。$\mathcal{P}_t^F$表示从前景在时间 $t$ 从图像采样的一组片块（patch）。$\Omega_t^{F|B}$表示在时间 $t$ 的联合前景/背景模型。给定一组补丁 $\mathcal{P}$，我们将 $knn(p,\mathcal{P})$定义为 $\mathcal{P}$ 中 $p$ 的第 $k$ 个最近邻。

在位置跟踪的情况下，我们在固定的前景窗口内建模目标的外观，并在周围的“上下文窗口”内建模背景的外观。我们分别从图形和背景区域中提取图像块。然后创建初始前景和背景“外观袋”以初始化外观模式 $\Omega_1^{F|B}$。对于 $t>1$，它在从前一帧预测的外部上下文矩形内进行采样，以产生混合样本集。

给定时间 $t$ 处的模型 $\Omega_t^{F|B}$，我们训练前景/背景二元分类器 $C_t$，并使用它来分类片块样本$\mathcal{P}_{t+1}$。对于位置估计，我们不会对 $\mathcal{P}_{t+1}$ 做出硬决策，而是使用分类置信度的度量。本文介绍了三种不同分类算法的结果：KNN，PCA+KDE和SVM。

KNN

对于KNN，对于每个图像块 $p\in\mathcal{P}_{t+1}$，片块 $\Omega_t^F$ 和 $\Omega_t^B$ 袋中从 $p$ 到其第 $k$ 个最近邻的距离定义为：

$$d_p^x=||p-knn(p,\Omega_t^x)||,\ \ x\in\{F,B\}$$

设 $σ_d$ 表示值 $\{d_p^F,d_p^B|p\in\mathcal{P}_{t+1}\}$ 的标准偏差。$p\in\mathcal{P}_{t+1}$ 的归一化前景似然值定义为：

$$l_p^F=\frac{g(d_p^F;\sigma_d)}{g(d_p^F;\sigma_d)+g(d_p^B;\sigma_d)}$$

其中，$g(x;s)=exp(-x^2/s^2)$。在实践中，我们选择 $k=2$ 或 $3$，$k$在$2$到$10$内不敏感。

KDE

对于KDE，它首先使用主成分分析（PCA）执行尺寸缩减，以将 $\Omega_t^{F|B}$ 中的片块映射到较低维的子空间。然后它从PCA映射的特征构建前景和背景KDE。令 $kde(·;x_t)$ 分别表示前景（$x=F$）和背景（$x=B$）的似然函数。$p\in\mathcal{P}_{t+1}$ 的归一化前景似然计算如下：

$$l_p^F=\frac{kde(p;\Omega_t^F)}{kde(p;\Omega_t^F)+kde(p;\Omega_t^B)}$$

SVM

对于SVM，通过使用 $\Omega_t^{F|B}$ 训练支持向量机（SVM），并在 $t+1$ 处对所有图像块进行测试以产生类标签和置信度值。由于SVM产生正值和负值，它通过将负置信度（背景）截断为零并在 $[0,1]$ 范围内重新调整正置信值来计算似然性。

跟踪：它将每个片块前景似然/置信度值 $l_p^F$ 映射到 $p$ 的图像坐标上以创建置信响应图（CRM）（下图(c),(d)）。然后它运行均值漂移算法来定位该相应图的模式并将其指定为对象位置。

更新：首先，模糊的片块样本，定义为所有 $p\in\mathcal{P}_{t+1}$ 中使得 $0.8\le\frac{d_p^F}{d_p^B}\le\frac{1}{0.8}$ 被丢弃。保留剩余的片块并将其分类为前景或背景，产生两个集合。这些集合需要被修剪：

$$\overline d_{t+1}^x-\lambda_1 \ast \sigma_{t+1}^x \le d_p^x \le \overline d_{t+1}^x+\lambda_2\ast\sigma_{t+1}^x \ \ \ x\in\{F,B\}$$

最后，初始更新模型计算为

$$\Omega_{t+1}^{F'|B'}=\Omega_{t+1}^{F|B}\cup\mathcal{P}_{t+1}^{F'|B'}$$

这个新模型被重新采样以形成 $\Omega_{t+1}^{F|B}$。

算法2：基于分割的跟踪

基于分割的跟踪的不同之处在于，我们现在尝试清晰准确地划分图像中的目标。我们假设我们提供了一个（或多个）带标注的帧，我们的目标是传播这些标签以对视频中其他前景/背景的出现进行分割和分类。关键的区别在于，分割跟踪必须为出现在前景或背景区域中的所有可能的复杂视觉图案保持完整（准确性）外观表示。

作者首先使用标准分割算法将每个视频帧分割成片段或“超像素”，而不是对单个像素进行操作。然后，作者将跟踪问题视为对结果段进行分类的问题。

采样：给定分割算法的输出，预期小段或大段具有大致相同的视觉均匀度。因此，从图像片段采样的随机图像块的大小被固定为图像块号的固定比例（1％-6％）或预定限制（150-250）中的较小者。

匹配：它基于其表示 $\mathcal{P}_{t+1}^i$（从 $\mathcal{S}_{t+1}^i$ 采样的一组随机图像块）的分类结果将任何新图像段 $\mathcal{S}_{t+1}^i$ 分类到前景/背景外观模型 $\Omega_t^{F|B}$。将 $\mathcal{S}^i$分配给 $F$ 或 $B$ 的决定是通过比较所有patch的平均或中值距离，并选择产生较小值的类来做出的。

更新：前景和背景通常具有复杂的多模式分布。 如果我们均匀地执行重采样，则可能错误地移除一些外观分布模式。它在最终的“生存概率”计算中引入了一个额外的分割因子。

形状模型：作者还利用弱形状模型进行基于分割的跟踪。弱形状模型有望通过纯粹的外观解决难以区分的前景/背景匹配的模糊性，并且能够允许快速运动。

作者提出了一种通过从背景中反复分割图形来进行跟踪的范例。在分割中获得的精确空间支持提供了关于轨迹的丰富信息，并且能够可靠地跟踪非刚性物体而不会漂移。前景/背景分割通过利用静态图像线索和时间一致线索在每个帧中顺序操作，其中包括颜色的外观模型和通过低级区域对应传播前景/背景掩码的空间模型。基于超像素的条件随机场线性组合线索。

如果跟踪器知道对象的准确支持掩码，则跟踪变得更加容易。知道支持掩码，而不仅仅是中心的空间模型，可以更可靠地预测对象的某些部分将来的位置。如果支持掩码可用，外观模型也可以更可靠地更新，背景杂乱的干扰大大减少。许多跟踪器假设所讨论的对象具有矩形或椭圆形。 在没有漂移的情况下，在杂乱的场景中跟踪非刚性物体会有困难。

如上图所示，在视频的每一帧中，它使用基于超像素的条件随机场来组合静态图像线索和时间一致性模型。时间一致性模型包括外观，尺度和空间支持。通过估计条件随机场中图形与背景的后边缘概率来计算软前景/背景掩码。

作者首先处理每个帧并应用边界概率（Pb）算子，该算子返回一个软边界图，总结了局部对比线索。然后，作者通过使用基于约束Delaunay三角剖分（CDT）的快速图像分割技术将图像中的像素分组为超像素。超像素表示不仅降低了后续处理阶段的计算复杂度，而且通过强化超像素内部的一致性，使计算更加稳健。

图2：预处理：对于每个帧(a)，我们使用边界概率算子来计算软边界图(b)，它总结了局部亮度，颜色和纹理对比。 我们使用快速图像分割技术，其建立边界图(c)的分割直线近似，并应用约束Delaunay三角剖分（CDT）将图像分割成一组三角形(d)。 我们在这个三角测量中使用三角形作为处理后期的超像素。

在CDT三角测量之上，在每帧中顺序地完成前景/背景分割。分割采用静态图像线索和跟踪线索，即时间一致性模型。时间一致性由三部分组成：

• 亮度或颜色的外观模型
• 一个简单的尺寸和横竖比例模型
• 一个空间模型，告诉我们使用低级超像素对应关系在前一帧中对象到当前帧的位置

然后，它使用条件随机场模型来组合前景/背景分割的线索。一旦我们获得了前景掩码，就可以更新时间一致性模型。

模型在跟踪过程中，它维护和更新三种时间一致性模型：尺度，外观和空间支持。

• 对于尺度，它使用三个参数：物体的大小（以像素为单位），在水平方向上与物体中心的中间距离，以及在垂直方向上与物体中心的中值距离。
• 对于外观，它对RGB空间中前景对象和直方图背景的亮度（或颜色）分布建模。
• 对于空间模型，它告诉我们在给定对象在前一帧中的位置的位置。 它避免使用任何动力学模型。

这是通过解决基于位置和亮度的线性变换问题的对应关系，类似于Earth Mover距离。之后，它通过使用学习率以直接的方式更新时间一致性模型。然后，它使用条件随机场（CRF）进行前景/背景分割。 CRF为判别标记提供了一般概率框架，特别适合于组合多个线索源。

图4：时间一致线索的一个例子。 (a)是滑冰顺序中的一帧，(b)是我们获得的前景/背景掩码。(c)显示下一帧。两个帧(a)和(c)都表示为三角测量，并且我们计算两组三角形之间的区域对应关系/分配。该对应关系用于将掩码(b)转换为(d)，空间“先验”是帧中的三角形(d)支持对象，越暗意味着越高概率。

图5：通过结合时间一致线索和静态图像线索的前景/背景分割。 对于(a)中的样本框架，我们在(b)中显示空间先验和先前出现的组合。 然而，当我们将信息传递到新帧时，不可避免地会发生错误。我们的分割跟踪器利用亮度和纹理对比的组合时间先验和静态图像线索，总结在轮廓对比图(c)中。 得到的分割(d)遵循高对比度轮廓并校正时间先验中的误差。然后使用(d)中的精确支持掩码来更新物体外观和比例。如果将物体支撑近似为椭圆(e)，使用椭圆支持，其可靠性降低得多。

图6：我们将提出的算法与Lipinski序列上基于均值漂移的跟踪器与颜色进行比较。

图7：我们的分割跟踪器在#1454帧和#1455帧之间切换摄像头后重新启动。摄像头切换后，尺度、空间支持和背景外观线索无效；图形外观和静态图像线索仍然有效。起初，跟踪器不确定对象在哪里。随着时间的推移，跟踪器会累积有关对象的信息。

图8：四个体育视频序列的样本结果。

References

• PEREZ, P. , et al, “Data fusion for visual tracking with particles”, Proceedings of the IEEE, 92(3): 495 - 513, 2004.
• Hieu T. Nguyen, et al, “Robust tracking using foreground-background texture discrimination”, IJCV, 69(3), 2006.
• L. Lu and G. Hager, “A Nonparametric Treatment on Location Segmentation Based Visual Tracking”, CVPR (oral), 2007.
• X. Ren and J. Malik, “Tracking as Repeated Figure/Ground Segmentation”, CVPR, 2007.

九、集成跟踪&W4

集成跟踪

如果跟踪器仅考虑对象而不考虑背景，则可能无法将对象与背景区分开来，并且跟踪可能会失败。集成学习方法将弱分类器的集合组合成单个强分类器。它将跟踪视为分类问题，并训练分类器以将对象与背景区分开来。这是通过为参考图像中的每个像素构建特征向量并训练分类器以将对象的像素与背景的像素分开来完成的。

给定一个新的视频帧，它使用分类器来测试像素并形成置信度图。图的峰值是它认为物体移动到的位置，它使用均值漂移来找到峰值。当对象和背景改变其外观时，跟踪器必须相应地进行调整。它不断训练新的弱分类器并将它们添加到弱分类器的集合中。该集成实现了两个目标：调整每个弱分类器以将对象与特定帧中的背景分离，并且整体作为整体确保时间一致性。

整个算法如下进行：

• 它维护着一组弱分类器，用于创建当前帧中像素的置信度图。
• 它运行均值漂移以找到其峰值（即对象的新位置）。
• 然后它通过在当前帧上训练新的弱分类器并将其添加到整体来更新整体。

集合跟踪在许多重要方向上扩展了传统的均值漂移跟踪。

1. 第一点

• 均值漂移跟踪通常与RGB颜色的直方图一起使用，因为灰度图像不能提供足够的跟踪信息，并且由于指数存储器要求，高维特征空间不能用直方图建模。
• 集成跟踪可以通过引入局部邻域信息来处理灰度图像，并且它不会受到指数内存爆炸的影响，因为它不再局限于使用直方图，因为它可以与任何类型的分类器一起使用。

1. 第二点

• 集成跟踪提供了一种原则性的方式，其中分类器随时间集成。
• 这与使用最近的直方图表示前景对象的现有方法或者第一帧和最后帧的直方图的一些特殊组合形成对比。
• 它将耗时的训练阶段分解为一系列简单易学的学习任务，可以在线执行。

1. 第三点

• 它可以自动调整在不同特征空间上训练的不同分类器的权重。
• 它还可以无缝集成离线和在线学习。
• 随着时间的推移，集成分类器可以在部分遮挡或光照变化的情况下提高跟踪器的稳定性。
• 在更高级别上，可以将集成跟踪视为用于在时变分布上训练分类器的方法。

集成跟踪不断更新弱分类器的集合，以将前景对象与背景分离。可以随时添加或删除弱分类器以反映对象外观的变化或合并有关背景的新信息。它并不明确表示对象，而是使用分类集合来确定像素是否属于对象。每个弱分类器都在正面和负面的例子上进行训练。强分类器AdaBoost用于对下一帧中的像素进行分类，从而生成像素的置信度图。

图1：集成更新和测试。(a)将时刻$t-1$的图像像素映射到特征空间。这些例子被当前的弱分类器集合（由两个分离的超平面表示）分类。合并输出用于产生置信度图，该置信图被馈送到均值漂移算法。(b)它在时间$t$训练一个新的弱分类器（虚线）在图像的像素上并将其添加到整体。

弱分类器

让每个像素表示为由一些局部信息组成的 $d$ 维特征向量，让 $\{x_i,y_i\}_{i=1}^N$ 分别表示 $N$ 个样本及其标签，其中 $x_i\in\mathcal{R}^d$ 和 $y_i in \{-1,+1\}$。弱分类器由 $h(x)$ 给出，$\mathcal{R}^d \rightarrow \{-1,+1\}$ 定义为：

$$h(x)=sign(\text{h}^Tx)$$

其中 $\text{h} \in \mathcal{R}^d$ 是使用加权最小二乘回归计算的分离超平面，

$$\text{h}=(A^TWA)^{-1}A^TWy$$

矩阵 $A$ 的每一行（表示为 $A_i$ ）对应于用常数1增加的一个样本 $x_i$，即 $A_i=[x_i,1]$，$W$ 是权重的对角矩阵。

更新分类器

通过维护随时间训练的 $T$ 个分类器列表来利用视频的时间一致性。在每个帧中，它保持 $K$ 个“最佳”弱分类器，丢弃剩余的 $T-K$ 个弱分类器，在新可用数据上训练 $T-K$ 个新的弱分类器并重建强弱分类器。关于对象的现有知识可以以参与强分类器的一个或多个弱分类器的形式并入跟踪器中，但是在更新阶段不能被移除。

它在所有分类器中使用相同的特征空间，但不一定必须得是这种情况。融合各种线索被证明可以改善跟踪结果，而集成跟踪提供了一个灵活的框架。该算法保持“最佳”的 $K$ 个弱分类器。但是，在添加新的弱分类器之前，需要更新剩余的 $K$ 个弱分类器的权重。它要求新的弱分类器表现得比偶然性好得多。 在权重重新计算期间，如果弱分类器的性能比偶然性差，则将其权重设置为零。

结果表明，AdaBoost对异常值敏感，因此需要异常拒绝方案。 用于跟踪的矩形框可能不准确。一种简单的方法是将过于“困难”的例子视为异常值并改变其标签。之前，它使用：

$$y_i=\left\{ \begin{aligned} &+1 && inside(r_j,p_i) \\ &-1 && otherwise \end{aligned} \right.$$

其中 $r_j$ 是当前矩形，$p_i$ 是样本i的像素位置，而$inside(r,p)$是预测，如果像素 $p$ 在矩形 $r$ 内，则该预测为真。

异常拒绝版本如下：

$$y_i=\left\{ \begin{aligned} &+1 && inside(r_j,p_i)\land(w_i < \Theta)\\ &-1 && otherwise \end{aligned} \right.$$

其中 $w_i$ 是运行强分类器后像素 $p_i$ 的权重，$\Theta$是一些预定义的阈值，在我们的例子中，它被设置为 $\Theta=\frac{3}{8}$，其中 $N$ 是样本的数量。

图2.异常拒绝：(a)输入图像。(b)具有异常拒绝的置信度图。(c)没有异常拒绝的置信地图。 异常拒绝过程可生成更清晰的置信度映射，从而实现更稳定的跟踪过程。

多分辨率

它在多尺度框架中运行集成跟踪。 这使得跟踪器能够提取多个尺度的特征。对于金字塔的每个级别，它运行独立的集成跟踪，输出置信度图。 然后将这些图组合以形成由均值漂移跟踪器使用的单个置信度图。它为每个金字塔等级训练一个弱分类器，并为每个这样的等级维持一个强分类器。每个强分类器生成置信度图，并且将所有置信度图调整为原始图像的大小并求平均以形成置信度图。

图3：跨多个尺度组合特征可改善对象/背景分离。(a)输入图像。(b)置信度图计算为置信图(c-e)的加权平均值。(c)原始图像的置信度图。(d)半尺度图像的置信度图。(e)四分之一尺度图像的置信度图。

它使用5个弱分类器，每个弱分类器处理每个像素的11维特征向量，其由在5×5窗口上计算的8个二维局部直方图以及像素R，G和B值组成。

为了提高稳健性，它仅计算高于某个预定义阈值的边缘。它在金字塔的三个层次上运行跟踪器，组合置信度图，并在得到的置信度图上运行均值漂移。

在每个帧中，它丢弃一个弱分类器并添加新训练的弱分类器。 它允许跟踪器每帧丢弃最多两个弱分类器，因为丢弃多于此可能是遮挡的标志，并且在这种情况下它不会更新整体。该算法以每秒几帧的速度运行。

图4：调整弱分类器。顶行显示3帧。底行显示了每个帧中使用的集成分类器。 每帧有五个弱分类器（即最高分类器在当前帧上训练，下面的分类器在前一个帧上训练，依此类推）。每个类别的前8个bin是5×5局部直方图，最后三个bin是像素颜色。bin的大小表示特征的权重。

图5：使用移动摄像机进行集成跟踪和每帧的置信度图。 置信度图对应于虚线矩形。

图6：使用移动摄像机进行集成跟踪和每帧的置信度图。

图7：使用（顶部）和不使用（底部）更新的集成跟踪。

W4：视觉监控

W4跟踪人和他们的身体部位，并监控他们在单色视频中的活动。W4构建了人们运动的动态模型，以回答有关他们正在做什么以及他们在何时何地采取行动的问题。它构建了人们的外观模型，以便它可以通过图像中的遮挡事件跟踪人。W4仅适用于单色固定视频源，因为W4专为户外任务而设计，特别适用于夜间或其他无法获得颜色的弱光环境。

W4的主要特点是：

• 即使背景不是完全静止，也可以统计学习背景场景以检测前景物体。
• 使用形状和周期性运动线索区分人与其他对象（例如汽车）。
• 即使他们一起移动或彼此交叉，也可以同时跟踪多个人。
• 在跟踪期间为每个人构建一个外观模型，可用于在遮挡后识别人。
• 使用静态形状模型和动态外观模型的二阶运动跟踪来检测和跟踪每个人的六个主要身体部位（头部，手部，脚部，躯干）。

在第一阶段（检测）中，W4使用统计背景模型检测前景像素；它们被分组为前景团，并计算每个团的一组全局和局部特征。在第二阶段（轮廓分析）中，使用静态轮廓形状和动态周期性分析将每个团分类为三个预定类别中的一个：单个人，组中人和其他对象。

如果将团分类为单人，则将基于轮廓的姿势分析应用于团以估计检测到的人的姿势。如果一个人处于直立姿势，则应用进一步的动态周期运动分析和对称分析来确定该人是否携带物体。如果该人没有携带物体或者处于与站立姿势不同的通用姿势，则W4使用轮廓边界形状分析来检测身体部位。

如果将团归类为一组物体，则W4无法检测个体的身体部位，姿势或携带的物体。相反，W4假设该组中的所有人都处于直立姿势，并将该组划分为多个个体。如果团被分类为除人之外的对象，则W4不进行任何进一步的轮廓分析；它只是通过视频跟踪对象。在基于轮廓的分析之后，跟踪器计算先前跟踪的团与当前检测到的团之间的对应关系，构建外观和运动模型，并恢复被跟踪的团的轨迹。

检测人

W4使用双峰分布背景模型。通过用三个值表示每个像素来建模背景场景；其最小 $m(x)$ 和最大 $n(x)$ 强度值以及训练期间连续帧之间的最大强度差 $d(x)$。随时间的像素中值滤波器被应用于几秒的视频（通常为20-40秒）以区分移动像素和静止像素。然后，仅处理那些静止像素以构建初始背景模型。

W4使用两种不同的方法来更新背景：

• 基于像素的更新方法更新背景模型以适应背景场景中的照明变化。
• 基于对象的更新方法更新背景模型以适应背景场景中的物理变化。

在跟踪期间，W4动态构造变化图以确定是基于像素还是基于对象的更新方法。变化图包括检测支持图，运动支持图和变化历史图。

当大部分（$> 80％$）图像被检测为前景时，W4停止跟踪并开始学习新的背景模型参数。使用以下方法检测前景像素：

$$B(x)=\left\{ \begin{aligned} &0\ \text{background}&&\left\{ \begin{aligned} &(I^t(x)-m(x))<kd_\mu \\ &\lor I^t(x)-n(x))<kd_\mu \end{aligned} \right. \\ &1\ \text{foreground} && \text{otherwise} \end{aligned} \right.$$

作者进行了一系列实验以确定使用不同背景场景的最佳阈值常数 $k$，并且 $k=2$ 给出最高的真阳性率和最低的假阳性率。

图5是针对不同阈值（$K$）的前景区域检测的示例。

W4使用基于区域的噪声清除来通过使用二进制连通分量分析来消除噪声区域。

图6：前景区域检测的示例，而背景具有不同的强度变化。

W4为每个检测到的前景对象生成一组形状和外观特征，用于区分人与其他对象，检测组中移动的人，以及检测携带对象的人。W4计算轮廓的全局和局部形状特征。

全局形状特征：W4使用每个前景区域的中值坐标作为对象位置的估计。W4通过应用主成分分析（PCA）确定前景区域的主轴。 主轴用于计算身体部位和身体姿势的相对方向。通过中间坐标的最佳拟合轴是通过最小化到轴的垂直距离的平方和来计算的。长轴的方向由与其协方差矩阵的最大特征值相关联的特征向量给出。2D二进制轮廓的形状由其投影直方图表示。W4计算每帧中轮廓的1D垂直/水平投影直方图。通过将二进制前景区域分别投影在垂直于长轴和沿长轴的轴上来计算垂直和水平投影直方图。投影直方图通过将重新缩放投影重新缩放到固定长度并将中心坐标对准中心来归一化。

图7：基于轮廓的形状特征：(a)输入图像 (b)检测到的前景区域 (c)其质心和长轴 (d)其边界的轮廓 (e) 其轮廓上的凸/凹顶点 (f)水平和(g)垂直投影直方图。

局部形状特征：一些身体部位可能出现在轮廓边界的极值点或曲率最大值处。因此，W4分析轮廓边界的形状以找到“自然”顶点作为身体部位的候选位置集。它实现了两种寻找点顶点的方法：一种递归凸包算法，用于在轮廓边界上找到凸包和凹包顶点（仅当W4需要检测身体部位的初始位置时）；以及基于轮廓边界的局部曲率的角点检测器。

可以使用静态形状分析，例如尺寸周长，纵横比或动态运动分析，例如速度或运动的周期性，以将人与其他对象区分开。W4将静态形状线索与动态周期性分析相结合，以区分人与其他物体。使用轮廓投影直方图，通过轮廓随时间的自相似性来确定周期性运动。W4分析轮廓的垂直投影直方图，以确定前景区域是否包含多个人。

图8：包含不同人数的轮廓示例，通过背景减法检测到它们的团，它们的投影直方图以及它们与检测到的头部位置的轮廓边界。

跟踪人

W4跟踪人，即使它们无法将它们分割为单个前景区域，例如分割，合并和遮挡等。W4为每个人使用二阶运动模型来估计其在后续帧中的位置。W4使用两阶段匹配策略来更新其人的全局位置估计。

位移的初始估计被计算为人的中位坐标的运动。 它允许我们快速缩小对象运动的搜索空间。在通过基于中值的估计将对象的轮廓从前一帧移位之后，它在当前和先前轮廓之间执行二元边缘相关。 仅在5x3组位移上计算此相关性。

图9：使用两个连续帧之间的轮廓边匹配的身体运动估计：输入图像（第一和第二）；基于中值差的轮廓边缘对齐（第三）；剪影相关后的最终对齐（第四）。

当合并区域分裂并且人们“重新出现”时，问题在于确定对应关系。W4将人的灰度纹理外观和形状信息组合在称为纹理时间模板的2D动态模板中。时间纹理模板具有两个部分：表示人的灰度纹理外观的纹理分量和表示最后 $N$ 帧的人体形状信息的形状分量。

图10：时间纹理模板的纹理（第二行）和形状（第三行）如何随时间更新的示例。

检测和跟踪人体部位（头部，手部，脚部）对于理解人类活动非常重要。W4想要找到六个主体部位（例如，头部，手部（2），脚部（2）和躯干）的位置，并跟踪它们以便理解动作。W4使用基于轮廓的身体模型，该模型由六个主要身体部位和十个次要部分（肘部（2），膝盖（2），肩部（2），腋窝（2），臀部和上背部）组成，可能位于轮廓边界，可以帮助定位主要部分。

主要和次要身体部位应与主要姿势的顺序一致（变化很小）。只要身体保持相同的主姿势，这些顺序就会被保留。此顺序可能因不同观点而异。 由于组件的相对运动或局部遮挡，一些组件可能在轮廓边界上缺失或某些组件可以按顺序（肘手或手肘）进行局部切换。 但是，应保留某些部分（头部，脚部）的相对位置。通过删除缺失部分或切换一些相邻部分（肘手）的位置，应该从主姿势的顺序生成给定轮廓中的身体部位的任何顺序。因此，如果我们知道给定轮廓的姿势和至少一个身体部位的位置，则标记问题变为将一组身体部位映射到一组轮廓线段而不违反预期顺序的问题。

图12：轮廓边界上的身体部位的顺序的示例。

作者观察到，四种不同的主要姿势（站立，坐姿，爬行/弯曲和躺下）在身体部位的顺序上存在很大差异。任何身体姿势被分类为四个主要姿势中的一个，然后每个主要姿势被分类为三个基于视图的外观之一（前/后，左侧和右侧）。身体姿势由标准化的水平和垂直投影直方图，中位坐标和其轮廓的长轴表示。每个主要姿势的平均标准化水平和垂直投影模板是使用三个不同视图中的七个不同人的4500个轮廓通过实验计算的。这些特征用于确定给定姿势与四种主要姿势之一的相似性。W4使用绝对差值和的方法来估计最相似的主要姿势。通常，当人从一种姿势转换到另一种姿势时发生错误分类。

在图14中，展示了用于身体姿势估计的站立，爬行/弯曲，躺下和坐姿的标准化垂直和水平投影模板。

W4将头部作为参考点来定位其他部分。 与其他头部相比，头部是稳定的身体部位，并且通常可以容易地预测其位置。然后，它试图找到其他主要身体部位。

图15：展示W4如何标记身体部位的示例：(a)原始图像，(b)检测到的轮廓，(c)检测到的凸包和凹包顶点，(d)用于估计的头部位置的轮廓段。

图16：使用轮廓模型以不同动作定位身体部位的示例。

W4使用模板匹配和运动预测来跟踪直立人的身体部位。W4采用身体部位的二阶运动模型。在每个帧中，在预测头部和手部的位置之后，使用时间纹理模板来验证和细化它们的位置。然后更新这些时间纹理模板。

监控人和物体之间的相互作用，并检测异常事件，例如存放物体，交换行李或移除物体，需要能够检测携带物体的人，从人物中分割物体，以及构建物体的外观模型，以便它可以在后续帧中识别。W4结合了两个观察来分析携带物体的人：人体形状是对称的，人们表现出周期性运动。W4为每个携带对象构造一个外观模型，以便它可以通过分析来检测“谁”携带“哪个”对象。

图17：(a)携带物体的人的例子和(b)通过背景减除法检测的前景区域。

组中人

形状分析使W4能够在有一小群人一起移动或相互交互时找到并跟踪人。W4通过分析其全局形状并将其与个体的形状模型进行比较来确定任意前景对象是否对应于一组人。W4试图通过识别他们的头来计算该组中的人数。W4结合了两种基于几何形状线索的方法和二元轮廓的垂直投影直方图来检测头部。

图24：(a)轮廓分析，(b)轮廓提取，(c)凸包/角检测，(d)垂直投影直方图和(e)最终头部检测。

基于局部顶点集的曲率，角顶点被分类为其附近的形状是否与预期的头部形状相似。消除了具有非类似曲率图案的顶点。在轮廓的垂直投影直方图上的显着峰值用于过滤局部形状分析的结果。仅当在其附近存在显着的投影直方图峰值时才保留潜在的头部。选择峰值阈值作为整个直方图的平均值。

图25：(c)仅使用轮廓边界的头部检测的示例。(d)仅基于垂直直方图。(e)合并这两种方法后的最终结果。

W4使用轮廓的局部几何形状将前景区域划分为表示各个人的子区域。为此，它首先计算每个人的身体躯干轴到该区域中每个像素的距离。然后W4将距离标准化为标准化距离值。W4通过使用归一化距离信息来检测组中的每个人。

图27：应用于单个图像中的前景区域的人物分割的示例。

W4为每个检测到的头部创建动态强度模板，在跟踪期间更新它们，并使用基于相关性的匹配来跟踪它们。在跟踪期间，W4更新其当前跟踪信息（例如当前正被跟踪的人数）。W4跟踪每个前景区域内的前景区域和个体。当一个人加入一个组时，所有关于该人的外貌和动作信息都会更新，W4会开始跟踪该人作为该组的一部分。同样，当一个人离开一个组时，W4会单独跟踪该人。

W4在跟踪和分割单个人时构造时间纹理模板。由于当人们一起移动时不能正确地预测个体的中值坐标，所有坐标都相对于头部的质心而不是相对于身体的中间坐标来表示。

图29：检测和跟踪多人的示例。

References

• S. Avidan, “Ensemble Tracking”, TPAMI, 29 (2) pp. 261 - 271, 2007.
• I. Haritaoglu, D. Harwood, L. S. Davis , “W4: Real-Time Surveillance of People and Their Activities , ”, TPAMI, 22(8), pp. 809-830, 2000.

十、人脸检测&行人检测&目标检测

人脸检测

它描述了一种人脸检测框架，能够在实现高检测率的同时极快地处理图像，能够构建正面检测系统，而且能够非常快速地检测面部。 在384 x 288像素图像上运行，在Intel Pentium III上以每秒15帧的速度检测到面部。仅适用于单个灰度图像中存在的信息，不使用辅助信息，例如视频序列中的图像差异或彩色图像中的像素颜色。

三个主要贡献：

• 它提出了一种称为积分图的新图像表示，可以进行非常快速的特征评估。
• 它提出了一种简单有效的分类器，它使用AdaBoost学习算法构建，从一大组潜在特征中选择少量关键视觉特征。
• 它提出了一种在“级联”中组合分类器的方法，该方法允许快速去除图像的背景区域，同时在有希望的面部区域上花费更多的计算。

它使用Haar基函数作为简单的特征，它使用三种特征形状：

• 双矩形特征的值是两个矩形区域内像素之和的差值。 这些区域具有相同的尺寸和形状，并且水平或垂直相邻（见下图）。
• 三个矩形特征计算从中心矩形中的和减去的两个外部矩形内的和。
• 四矩形特征计算矩形对角线对之间的差。

使用图像的中间表示（称为积分图）可以非常快速地计算矩形特征。位置$x$，$y$处的积分图包含$x$，$y$（包括端点）上方和左侧像素的总和：

$$ii(x,y)=\sum_{x' \le x,y' \le y}i(x',y')$$

其中$ii(x,y)$是积分图，$i(x,y)$是原始图像。

使用积分图，可以在四个数组中计算任何矩形和。 显然，上面定义的两个矩形特征涉及相邻的矩形和，它们可以在六个数组中计算，八个用于三个矩形特征，九个用于四个矩形特征。

AdaBoost的变体用于选择特征和训练分类器。AdaBoost结合了一系列弱分类函数，形成一个更强大的分类器。为了使弱学习器得到提升，在第一轮学习之后，重新加权这些例子以重视那些被前一个弱分类器错误分类的例子。最终的强分类器采用带有阈值的弱分类器加权组合的形式。

上表用于从一组大的弱分类器中选择关键的弱分类器。由于每个不同的特征/阈值组合都有一个弱分类器，因此有效的 $KN$ 个弱分类器，其中$K$是特征的数量，$N$是样本的数量。给定 $N=20000$ 和 $K=160000$ 的任务，有 $32$亿个不同的二元弱分类器！使用AdaBoost，可以在大约 $10^{11}$ 个操作中学习200个特征分类器。一个关键优势是在每一轮中，使用样本权重对先前选择的特征的整体依赖性进行编码，这可以用于在恒定时间内评估给定的弱分类器。最初的实验表明，由200个特征构造的分类器将产生合理的结果。检测率为95％，分类器在测试数据集上产生1/14084的误报率。但对于实际应用的面部检测器，误报率必须接近1/1000000。对于人脸检测任务，AdaBoost选择的初始矩形特征是有意义的。 选择的第一个特征似乎集中在眼睛区域通常比鼻子和脸颊区域更暗的特性（见下图）。选择的第二个特征依赖于眼睛比鼻梁更暗的特性。

注意力的级联

提出了一种构建级联分类器的算法，该算法可以在大幅缩短计算时间的同时提高检测性能。在使用更复杂的分类器来实现低误报率之前，使用更简单的分类器来拒绝大多数子窗口。级联中的阶段是使用AdaBoost训练分类器构建的。从双特征强分类器开始，通过调整强分类器阈值可以获得有效的人脸过滤器，以最大限度地减少漏报。阈值越低，检测率越高，误报率越高。

第一个分类器的正结果触发第二个分类器的评估，该分类器也经过调整以实现非常高的检测率。 第二个分类器的正结果触发第三个分类器，依此类推。任何一点的负面结果都会导致立即拒绝子窗口。

给定训练的级联分类器，级联的误报率为：

$$F=\prod_{i=1}^Kf_i$$

其中 $F$ 是级联分类器的误报率，$K$ 是分类器的数量，$f_i$是第 $i$ 个分类器的误报率。 检测率是

$$D=\prod_{i=1}^K d_i$$

其中 $D$ 是级联分类器的检测率，$K$ 是分类器的数量，$d_i$ 是第 $i$ 个分类器在检测到它的样本上的检测率。

如果每个阶段的检测率为$0.99$（因为 $0.9≈0.99^{10}$），则10级分类器可以实现$0.9$的检测率。实现这种检测率可能听起来像是一项艰巨的任务，因为每个阶段只需要达到约$30％$（$0.30^{10}≈6×10^{-6}$）的假阳性率，这一点变得非常容易。任何给定的子窗口将向下进行级联，一次一个分类器，直到确定窗口为负。AdaBoost学习过程仅尝试将错误降至最低，并且不是为了以较高的误报率为代价来实现高检测率。

一种简单而传统的折衷方法是调整AdaBoost的阈值。较高的阈值会产生分类器，误报率较低，检测率较低。较低的阈值会产生具有更多误报和更高检测率的分类器。在大多数情况下，具有更多功能的分类器将实现更高的检测率和更低的误报率。同时，具有更多特征的分类器需要更多时间进行计算。

选择 $f_i$ 的最大可接受速率和 $d_i$ 的最小可接受速率。级联的每一层都由AdaBoost训练，使用的特征数量增加，直到达到目标检测和此级别的误报率。一个例子：1个200特征分类器和10个20特征分类器的级联。

最终的探测器是38层级分类器，包括总共6060个特征。级联中的第一个分类器使用两个特征构造，并且拒绝大约50％的非面部，同时正确地检测接近100％的面部。下一个分类器有十个特征，拒绝80％的非面部，同时检测几乎100％的面部。接下来的两个层是25特征分类器，接着是三个50特征分类器，后面是具有各种不同数量特征的分类器。

通过从一组9500个不包含面部的图像中选择随机子窗口来收集用于训练级联的第一级的非面部子窗口。每层最多收集6000个这样的非面部子窗口。 9500非面部图像中包含大约3.5亿个非面部子窗口！在单个466 MHz AlphaStation XP900上，整个38层探测器的训练时间为几周。我们已经将算法并行化，以便在大约一天内训练完整的级联。

由于大多数子窗口被级联的前两个阶段丢弃，因此每个子窗口评估平均8个特征，总共6060个。人脸探测器可以在约0.067秒内处理384x288像素图像，这比Schneiderman-Kanade探测器快约600倍。在多个比例和位置扫描最终检测器。

我们注意到了一些不同的失败模式。面部探测器被训练在正面，直立的面部。 非正式观察表明，人脸探测器可以探测到平面倾斜约±15度且平面外约±45度的面部。旋转的度数越大，探测器就越不可靠。面部检测器在明显遮挡的面上失效。 如果眼睛被遮挡，检测器通常会失败。 嘴巴不那么重要，因此通常仍会检测到被遮住嘴的脸。

行人检测

在图像中检测人物是一项具有挑战性的任务，因为它们的外观可变，并且可以采用各种各样的姿势。第一个需求是一个强大的特征集，即使在光线不足的情况下，即使在杂乱的背景下也能干净地区分人形。作者研究了人体检测特征集的问题，表明局部归一化的定向梯度直方图（HOG）描述符提供了优异的性能。为了简单和快速，它使用线性SVM作为基线分类器。 它使用更简单的架构和单个检测窗口。

基本思想是局部物体外观和形状可以通过局部强度梯度或边缘方向的分布很好地表征，即使没有对应梯度或边缘位置的精确知识。在实际中，这通过将图像窗口划分为小空间区域（“单元”）来实现，对于每个单元，在单元的像素上累积梯度方向或边缘取向的局部1-D高度图。为了更好地对光照，阴影等进行不变性，在使用它们之前对比度标准化局部响应也是有用的。

这可以通过在较大空间区域（“块”）上累积局部直方图“能量”的度量并使用结果来标准化块中的所有单元来完成。用HOG描述符的密集（和重叠）网格平铺检测窗口，并使用传统的基于SVM的窗口分类器中的组合特征向量给出人类检测链。

图1：特征提取和对象检测链的概述。 探测器窗口平铺有重叠块网格，其中提取了方向梯度直方图特征向量。 将组合的矢量馈送到线性SVM以进行对象/非对象分类。 在所有位置和比例下在图像上扫描检测窗口，并且在输出金字塔上运行传统的非最大抑制以检测对象实例。

HOG有几个优点：

• 捕获局部形状特征的边缘或梯度结构。
• 如果平移或旋转比局部空间或方向bin尺寸小得多，则几乎没有区别。

实验：作者选择了1239个图像作为正面训练样例，以及它们的左右反射（共2478个图像）。 从1218个无人训练照片中随机抽样的一组固定的12180个patch提供了初始的负集。当前线性SVM检测器在不到一秒的时间内处理320x240比例尺空间图像（4000个检测窗口）。

对于彩色图像，它计算单独的梯度，它为每个颜色通道计算单独的梯度，并将具有最大范数的梯度作为像素的梯度向量。

目标检测

作者将对象检测和分割不是作为单独的任务，而是作为两个紧密协作的过程。为了学习对象类别的外观可变性，它首先建立一个局部外观的码本，这些码本是其成员对象（的特定视点）的特征。这是通过提取兴趣点周围的局部特征并使用凝聚聚类方案对其进行分组来完成的。初始聚类步骤至关重要。 它评估不同的聚类方法，并描述用于码本生成过程的有效算法。

基于此码本，它学习隐式形状模型（ISM），该模型指定可以在对象上出现的码本项。它不会尝试为类对象可能采用的所有可能形状定义显式模型，而是根据哪些局部外观彼此一致来隐式定义“允许”形状。这种方法的优点是它具有更大的灵活性，并且需要更少的训练样例来学习可能的物体形状。例如，在学习对关节状物体（牛或行人）进行分类时，不需要在训练集中看到每种可能的关节。

它为自上而下的分割问题推导出概率公式，产生像素方式的前景/背景分割。它还提供每像素置信度估计，指定可以置信的细分程度。然后使用自上而下的分割来提高识别率。 它允许仅汇总对象区域的置信度并丢弃来自背景的影响。 可以解决重叠假设之间的歧义。

Codebook

整个方法以尺度不变的方式制定，使其适用于对象尺度通常未知的现实情况。码本：任何基于局部特征的方法的第一个任务是确定图像中哪些特征对应于哪些对象结构。当假定对象是刚性的时，少量匹配通常足以估计对象姿势。但是，在尝试查找某个类别的对象时，任务变得更加困难。

不仅特征外观受不同观察条件的影响，而且对象的局部结构和特征的空间配置在类别成员之间也可能有很大差异。所有类别成员中只有极少数定位特征。作者通过对在一定范围内重复出现的局部特征进行采样，建立一个局部外观词汇（称为码本），这些码本是对象类别的特定视点的特征。

视觉上相似的特征在无监督的聚类步骤中组合在一起。 结果是对象外观的紧凑表示。首先应用尺度不变的兴趣点检测器，为每个图像获得一组信息区域。使用和评估几种不同的兴趣点探测器，如Harris，Harris-Laplace，Hessian-Laplace和高斯差分（DoG）。它还通过定位描述符表示提取的图像区域。 它比较了简单的Greyvalue补丁，SIFT和局部形状上下文描述符。

接下来，它将视觉上相似的特征分组，以创建定位外观的码本。 为了使表示尽可能简单，它表示集群中心在集群中的所有特征。K-means计算简单。 但是，它要求用户预先指定簇的数量。 并且，不能保证所获得的簇在视觉上是紧凑的，等等…凝聚聚类方案通过连续合并特征来自动确定聚类的数量，直到达到聚类紧凑性的截止阈值。 但是，运行时和内存要求通常都要高得多。

ISM

作者提出了一种用于凝聚聚类的RNN算法，该算法实现了与K-Means相似的性能。形状模型：引入隐式形状模型$ISM(C)=(C,PC)$，它由对象类别的局部出现的码本 $C$ 和空间概率分布 $P_C$ 组成，它指定每个可以在对象上找到的码本项的位置。每个局部部分的位置仅取决于对象中心。此外，它能够以非参数方式学习识别模型。

要学习空间概率分布 $P_C$，它将码本项与图像匹配。它不仅激活最匹配的码本项，而且激活相似性高于截止阈值的所有项。对于每个码本项，它存储相对于对象中心激活的所有位置。

识别：给定新的测试图像，我们应用兴趣点检测器并提取所选位置周围的特征。然后将提取的特征与码本匹配以激活码该项。从所有这些匹配的集合中，它通过执行广义Hough变换来收集一致的配置。每个激活的项根据所学习的空间分布对对象中心的可能位置进行投票。在投票空间中搜索一致的假设作为局部最大值。

接下来，需要在投票空间中找到假设为最大值。为了计算效率，它采用两阶段搜索策略（见图4）。 在第一阶段，在分组的3D Hough累加器阵列中收集投票以便快速找到有希望的位置。在第二阶段，然后使用原始（连续）3D投票来细化来自该第一阶段的候选最大值。

Segmentation

为了从前景和背景概率获得整个图像的分割，我们为每个像素建立似然比。

$$L=\frac{p(\text{p}=figure|O_n,x)+\epsilon}{p(\text{p}=ground|O_n,x)+\epsilon}$$

References:

• Paul A. Viola, Michael J. Jones: Robust Real-Time Face Detection International Journal of Computer Vision . International Journal of Computer Vision 57(2): 137-154 (2004)
• Navneet Dalal, Bill Triggs: Histograms of Oriented Gradients for Human Detection. CVPR (1) 2005: 886-893
• Bastian Leibe, Ales Leonardis, Bernt Schiele: Robust Object Detection with Interleaved Categorization and Segmentation. International Journal of Computer Vision 77(1-3): 259-289 (2008)