NOMT 近似在线的多目标跟踪算法

多目标跟踪算法可以分类两类：在线法和全局（批处理）方法。在线方法逐帧处理，适应大多数实际应用的需求；而全局方法考虑整个时间范围内的所有检测，具有更高的数据关联精度。在求解时，以往的工作会着眼于特征度量或关联模型。

NMOT 不片面追求高精度，而是从实际出发：

• 设计一种精确的亲和性度量以关联检测；

• 实现高效且准确的（近似）在线多目标跟踪算法。

首先，NMOT 引入了一种新颖的聚合局部流描述符（Aggregated Local Flow Descriptor, ALFD），该算法使用长期兴趣点轨迹（long term interest point trajectories, IPT）来编码两个时间帧中检测框之间的相对运动模式。尽管每个单独的 IPT 可能有错误，但它们共同提供了强大的信息来比较两个检测。通过一个学习模型，作者观察到 ALFD 提供了强大的亲和力度量，从而为关联算法提供了可靠的线索。

图 1. 边界框距离和外观相似度是多目标跟踪文献中常用的亲和性度量。但是，在拥挤的现实场景中，它们通常难以成功区分相邻或相似的目标。然而，光流轨迹提供了更可靠的方法来比较跨时间的不同检测。尽管个别轨迹可能不准确（$\textcolor{red}{红}$红 线），但它们共同提供了强大的信息来衡量亲和性。NMOT 提出了一种新颖的聚合局部流描述符，该描述符在多目标跟踪问题中可靠地利用了光流。该图最好用彩色显示。

其次，文章提出了一种近似在线多目标跟踪（Near-Online Multi-Target Tracking, NOMT）算法。将跟踪问题描述为时间窗口中目标与检测之间的数据关联，在每一帧重复执行。NMOT 通过将 ALFD 度量、目标动力学、外观相似性和长期轨迹正则化在内的多个线索集成到模型中来实现鲁棒性。并且 NMOT 能够实时运行（$\sim 10$∼10 FPS ）。 在每个时间帧 $t$t 中， NMOT 求解目标与大小为 $\tau$τ 的时间窗口 $[t-\tau, t]$[t−τ,t] 中的所有检测之间的全局数据关联问题（参见图 2）。该算法的关键特性是，当提供更多的检测时，能够修正以往的关联错误。为了同时达到精度和效率，该算法使用 ALFD 驱动的小轨迹生成候选假设轨迹，并使用并行联合树算法解决关联问题。

图 2. NMOT 算法使用时间窗口 $\tau$τ 在每个时间帧 $t$t 处解决全局关联问题。实心圆表示关联的目标，虚线圆表示未观察到的检测，虚线表示在时间窗口之前的最终目标关联，实线表示在当前时间范围内进行的（活动）关联。由于观测量有限，跟踪算法可能会在 $t_2$t2​ 处产生错误关联。然而一旦在 $t_3$t3​ 处提供了更多的观察结果，算法便能够修复 $t_2$t2​ 所产生的错误。此外，NMOT 方法能动态识别新目标（$\textcolor{red}{红色}$红色 圆圈）。

Data Association Models

给定长度为 $T$T 的视频序列 $V_1^T = \{I_1, I_2, ..., I_T\}$V1T​={I1​,I2​,...,IT​} 和一组检测假设 $\mathbb{D}_1^T = \{d_1, d_2, ..., d_N\}$D1T​={d1​,d2​,...,dN​}，其中 $d_i$di​ 由帧号 $t_i$ti​、边界框 $(d_i[x], d_i[y], d_i[w], d_i[h])$(di​[x],di​[y],di​[w],di​[h]) 以及分数 $s_i$si​ 参数化，多目标跟踪试图找到一个连贯的目标集合（关联）$\mathbb{A} = \{ A_1, A_2, ..., A_M\}$A={A1​,A2​,...,AM​}，其中每个目标 $A_m$Am​ 由一组出现期间的检测索引表示（例如，$A_1 = \{d_1, d_{10}, d_{23}\}$A1​={d1​,d10​,d23​}）； 即 $(V_1^T, \mathbb{D}_1^T) \rightarrow \mathbb{A}$(V1T​,D1T​)→A。

• 在线算法[5, 7, 10, 20, 27]的构想是寻找现有目标与当前时间帧中检测之间的关联：$(V_t^t, \mathbb{D}_t^t, \mathbb{A}^{t-1}) \rightarrow \mathbb{A}^t$(Vtt​,Dtt​,At−1)→At。

• 全局算法常将跟踪表述为网络流问题，以直接从检测假设中获得目标[KSP, 28, MCF]，即 $(V_1^T, \mathbb{D}_1^T) \rightarrow \mathbb{A}^T$(V1T​,D1T​)→AT；或采用迭代算法，逐步完善目标关联[2, 18, OLDAM, OM+APP]，即 $(V_1^T, \mathbb{D}_1^T, \mathbb{A}_{i}^T) \rightarrow \mathbb{A}_{i+1}^T$(V1T​,D1T​,AiT​)→Ai+1T​，其中 $i$i 表示一个迭代。

• NMOT 提出了一个新的框架来填补在线算法和全局算法之间的空白：在每个时间帧 $t$t 中 $(V_{1}^t, \mathbb{D}_{t-\tau}^t, \mathbb{A}^{t-1}) \rightarrow \mathbb{A}^t$(V1t​,Dt−τt​,At−1)→At，其中 $\tau$τ 是预定义的时间窗口大小。

NMOT 算法的表现与在线算法类似，因为它在每个时间帧中输出关联。关键的区别在于，一旦有了更多的观察结果，过去所做的任何决定都可能会发生变化。使用新提出的全局关联算法可以解决每个时间窗口中的关联问题。所提方法还使人联想到迭代全局算法，因为迭代地增加轨迹（每帧一次迭代）时考虑到多个帧，从而可以提高关联精度。

Aggregated Local Flow Descriptor

给定兴趣点轨迹[31]，ALFD 在时间距离（$\Delta t=|t_i-t_j|$Δt=∣ti​−tj​∣）内对两个边界框之间的相对运动模式进行编码。ALFD 的主要直觉是，如果两个框属于同一目标，那么我们将在框的相对位置观察到许多支持 IPT。为了使其对检测中的细微定位误差、目标方向变化以及 IPT 中的异常值（误差）具有鲁棒性，NMOT 使用空间直方图构建 ALFD。 一旦获得了 ALFD，NMOT 将使用学习到的模型参数 $w_{\Delta t}$wΔt​ 和 ALFD 的线性乘积来度量两个检测之间的亲和力，即 $a_{A}(d_i, d_j) = w_{\Delta t} \cdot \rho(d_i, d_j)$aA​(di​,dj​)=wΔt​⋅ρ(di​,dj​)。

Interest Point Trajectories

NMOT 使用局部兴趣点检测器[4, FAST]和光流算法[4, 11]获得兴趣点轨迹。该算法旨在结合各种众所周知的计算机视觉技术来生成一组长而准确的点轨迹：

• 给定图像 $I_t$It​，NMOT 运行 FAST 兴趣点检测器[4, FAST]来识别要跟踪的“好点”。
• 为了避免冗余点，算法计算新检测到的兴趣点与现有 IPT 之间的距离，并使新点与现有 IPT 保持足够的距离（$> 4$>4 px）。为新点分配唯一的 ID。
• 对于 $t$t 中的所有 IPT，使用[4, 11]计算前向（$t \rightarrow t+1$t→t+1）和反向（$t+1 \rightarrow t$t+1→t）光流。反向流的起点由向前流的终点给出。终止在两者之间有较大分歧（$> 10$>10 px）的 IPT。

ALFD Design

首先定义讨论 ALFD 的必要符号。$\kappa_{id} \in \mathcal{K}$κid​∈K 表示具有唯一 $id$id 的 IPT，该 IPT 在存在期间由像素位置 $(\kappa_{id}(t)[x], \kappa_{id}(t)[y])$(κid​(t)[x],κid​(t)[y]) 参数化 。$\kappa_{id}(t)$κid​(t) 表示帧 $t$t 处的像素位置。如果 $\kappa_{id}$κid​ 不在帧 $t$t 中（终止或未启动），则返回 $\text{\o}$ø。

首先通过汇总位于 $d_i$di​ 框内且在帧 $t_j$tj​ 仍存在的 IPT 信息，来定义单向 ALFD $\rho'(d_i, d_j)$ρ′(di​,dj​)，即从 $d_i$di​ 到 $d_j$dj​。形式上，将 IPT 集定义为
$\mathcal{K}(d_i, d_j) = \{\kappa_{id} | \kappa_{id}(t_i) \in d_i\ \&\ \kappa_{id}(t_j) \neq \text{\o} \}$K(di​,dj​)={κid​∣κid​(ti​)∈di​ & κid​(tj​)​=ø}

对于每个 $\kappa_{id} \in \mathcal{K}(d_i, d_j)$κid​∈K(di​,dj​)，通过
$\begin{aligned} r_i(\kappa_{id})[x] &= ( \kappa_{id}(t_i)[x] - d_i[x] ) / d_i[w]\\ r_i(\kappa_{id})[y] &= ( \kappa_{id}(t_i)[y] -d_i[y] ) / d_i[h] \end{aligned}$ri​(κid​)[x]ri​(κid​)[y]​=(κid​(ti​)[x]−di​[x])/di​[w]=(κid​(ti​)[y]−di​[y])/di​[h]​
计算每个 $\kappa_{id}$κid​ 在 $t_i$ti​ 的相对位置 $r_i(\kappa_{id}) = (x, y)$ri​(κid​)=(x,y)。类似地计算 $r_j(\kappa_{id})$rj​(κid​)。请注意，$r_i(\kappa_{id})$ri​(κid​) 被限制在 $[0, 1]$[0,1] 之间，但是 $r_j(\kappa_{id})$rj​(κid​) 未受限制，因为 $\kappa_{id}$κid​ 可以位于 $d_j$dj​ 之外。

给定 $r_i(\kappa_{id})$ri​(κid​) 和 $r_j(\kappa_{id})$rj​(κid​)，计算相应的空间网格 bin 索引，如图 3所示，并累积计数构建描述符。ALFD 为 $r_i(\kappa_{id})$ri​(κid​) 定义了 $4 \times 4$4×4 网格，为 $r_j(\kappa_{id})$rj​(κid​) 定义了 $4 \times 4 + 2$4×4+2 网格，其中最后的 $2$2 区间对应检测之外的区域。第一个外区间定义检测的邻域（$ < width/4\ & < height/4$），第二个外区间表示其他更远的区域。

图 3. 单向 ALFD $\rho'(d_i, d_j)$ρ′(di​,dj​) 的示意图。顶部图中将检测结果显示为彩色边框（$d_{\textcolor{red}{red}}$dred​, $d_{\textcolor{blue}{blue}}$dblue​ 和 $d_{\textcolor{green}{green}}$dgreen​）。一对具有连接线的圆圈表示 IPT，它们同时存在于 $t$t 和 $t + \triangle t$t+△t 帧中，并且位于 $t$t 帧的 $d_{\textcolor{red}{red}}$dred​ 内部。图中绘制了准确的（$\textcolor{green}{green}$green）、离群值（$\textcolor{black}{black}$black）和错误的（$\textcolor{red}{red}$red）IPT。底部图中显示了两个单向 ALFD $\rho'$ρ′ 示例，分别为 ($d_{\textcolor{red}{red}}$dred​, $d_{\textcolor{blue}{blue}}$dblue​) 和 ($d_{\textcolor{red}{red}}$dred​, $d_{\textcolor{green}{green}}$dgreen​)。$\textcolor{red}{red}$red 网格（$2\times2$2×2）表示 IPT 在 $t$t 帧中相对于 $d_{\textcolor{red}{red}}$dred​ 的位置。每个 $\textcolor{red}{red}$red 区域中的 $\textcolor{blue}{blue}$blue 和 $\textcolor{green}{green}$green 网格显示 IPT 在 $t+\triangle t$t+△t 帧中相对于相应框的位置（$2\times2 + 2$2×2+2 个外部区域）。网格中 $\textcolor{red}{red}$red 盒子表示在相同的相对位置中观察到的 IPT。凭直觉，在网格中观察到的 IPT 越多，两次检测属于同一目标的可能性就越大。相反，外部区域将为错误匹配提供更多的支持。为了避免混乱，插图使用 $2\times 2$2×2 网格显示。在实践中使用的是 $4\times 4$4×4。

通过一对单向 ALFD，将 ALFD 定义为
$\rho(d_i, d_j) = (\rho'(d_i, d_j) + \rho'(d_j, d_i))\ /\ n(d_i, d_j)$ρ(di​,dj​)=(ρ′(di​,dj​)+ρ′(dj​,di​)) / n(di​,dj​)

其中 $n(d_i,d_j)$n(di​,dj​) 是正规化子。 正规化子 $n$n 定义为

$n(d_i, d_j) = | \mathcal{K}(d_i, d_j) | + | \mathcal{K}(d_j, d_i) | + \lambda$n(di​,dj​)=∣K(di​,dj​)∣+∣K(dj​,di​)∣+λ
其中 $| \mathcal{K}(\cdot) |$∣K(⋅)∣ 是 IPT 的计数，而 $\lambda$λ 是常数。$\lambda$λ 确保当有更多支持 $\mathcal{K}(d_i, d_j)$K(di​,dj​) 时，ALFD 的 L1范数增加并且收敛到 $1$1 。实际中令 $\lambda=20$λ=20。

Learning the Model Weights

作者使用加权投票方式从训练数据集中学习模型参数 $w_{\Delta t}$wΔt​。给定一组检测 $\mathbb{D}_1^T$D1T​ 和相应的真实（GT）目标注释，

• 首先将 GT 目标 id 分配给每个检测。对于每个检测 $d_i$di​，测量其与 $t_i$ti​ 帧中所有 GT 框的重叠。如果最佳重叠 $o_i$oi​ 大于$ 0.5 $，则分配相应的目标 id（$，则分配相应的目标id（id_i$）；否则，将分配 $-1$−1。

• 从所有正检测（ $id_i \geq 0$idi​≥0）的检测中收集一组检测 $\mathcal{P}_i^{\Delta t} = \{d_j \in \mathbb{D}_1^T | t_j - t_i = \Delta t\}$PiΔt​={dj​∈D1T​∣tj​−ti​=Δt}。对于每一对，按如下方式计算边距 $m_ {ij}$mij​：
  $m_{ij} = \begin{cases} (o_i - 0.5) \cdot (o_j - 0.5)& \text{if } id_i == id_j \\ -(o_i - 0.5) \cdot (o_j - 0.5)& \text{if } id_i \not= id_j \end{cases}$mij​={(oi​−0.5)⋅(oj​−0.5)−(oi​−0.5)⋅(oj​−0.5)​if idi​==idj​if idi​​=idj​​
  直观地，如果两次检测均来自同一目标，则 $m_ {ij}$mij​ 应为正值；如果 $d_i$di​ 和 $d_j$dj​ 来自不同的目标，则 $m_ {ij}$mij​应为负值。幅度由定位精度加权。

• 给定所有的对和边距，学习模型 $w_{\Delta t}$wΔt​ 如下：
  $w_{\Delta t} = \frac{\sum_{\{i \in \mathbb{D}_1^T | id_i \geq 0\}} \sum_{j \in \mathcal{P}_i^{\Delta t}} m_{ij} (\rho'(d_i, d_j) + \rho'(d_j, d_i))}{\sum_{\{i \in \mathbb{D}_1^T | id_i \geq 0\}} \sum_{j \in \mathcal{P}_i^{\Delta t}} |m_{ij}| (\rho'(d_i, d_j) + \rho'(d_j, d_i))}$wΔt​=∑{i∈D1T​∣idi​≥0}​∑j∈PiΔt​​∣mij​∣(ρ′(di​,dj​)+ρ′(dj​,di​))∑{i∈D1T​∣idi​≥0}​∑j∈PiΔt​​mij​(ρ′(di​,dj​)+ρ′(dj​,di​))​
  在所有 ALFD 模式上计算带符号的加权平均值，其中权重由目标和检测之间的重叠确定。直观地讲，检测之间的 ALFD 模式若与 GT 很好地匹配，则对模型参数的贡献更大。

加权投票方法的优点是 $w_{\Delta t}$wΔt​ 中的每个元素都以 $[-1, 1]$[−1,1] 为界，从而 ALFD 度量 $a_{A}(d_i, d_j)$aA​(di​,dj​) 也在 $[-1, 1]$[−1,1] 区间，因为 $||\rho(d_i, d_j)||_1 \leq 1$∣∣ρ(di​,dj​)∣∣1​≤1。图 4显示了使用上述方法学习的两个模型。可以采用其他学习算法，例如 LIBSVM。

图 4. 两个学习到的模型权重 $w_{\Delta 1}$wΔ1​ 和 $w_{\Delta 20}$wΔ20​ 的可视化。在明亮的（白色）区域中具有较高的 $\rho$ρ 值会产生较高的亲和力度量值。随着时间距离的增加，模型权重倾向于扩展到相邻的目标箱中，以考虑可能的目标方位变化和更高的 IPT 误差。

Properties

本节讨论 ALFD 相似性度量 $a_{A}(d_i, d_j)$aA​(di​,dj​) 的性质：

• 首先，与外观或空间度量不同，ALFD通过 IPT 隐式利用 $t_i$ti​ 至 $t_j$tj​ 时段所有图像中的信息。由于使用相邻像素信息计算光流，因此 $\mathcal{K}(d_i, d_j)$K(di​,dj​) 会随着感受野的增加而对所有支持图像信息进行编码。
• 其次，由于 ALFD 设计的集体性，它可以在任意时间长度内提供强大的亲和力度量。与外观或空间度量相比有明显的好处，特别是在较长的时间距离上（有关分析，请参见实验5.1节）。
• 第三，它通常适用于任意场景（静态或移动摄像机）以及任意目标类型（人或汽车）。
• ALFD 的一个缺点是当发生遮挡时会变得不可靠。当目标发生遮挡时，起始于目标的 IPT 倾向于粘附在遮挡者上。它促使作者结合在5.1节中讨论的目标动力学信息。

Near Online Multi-target Tracking (NOMT)

算法采用近似在线多目标跟踪框架，在每个时间帧中更新并输出目标 $\mathbb{A}^t$At，同时考虑到时间窗口 $[t-\tau, t]$[t−τ,t] 中的输入。NMOT 通过假设生成和选择方案来实现。为了便于讨论，这里定义干净目标 $\mathbb{A}^{* t - 1} = \{A_1^{* t - 1}, A_2^{* t - 1}, ...\}$A∗t−1={A1∗t−1​,A2∗t−1​,...}，不包含 $[t -\tau, t-1]$[t−τ,t−1] 中的所有相关检测。

给定 $[t - \tau, t]$[t−τ,t] 中的一组检测和干净目标 $\mathbb{A}^{* t - 1}$A∗t−1，为每个目标 $A_m ^ {* t-1}$Am∗t−1​ 以及新进入目标生成多个目标假设$H_m^t = \{ H_{m, 1}^t = \text{\o}, H_{m, 2}^t, H_{m, 3}^t ... \}$Hmt​={Hm,1t​=ø,Hm,2t​,Hm,3t​...} ，其中 $\text{\o}$ø（空假设）表示目标的终止，每个 $H_{m, k}^t$Hm,kt​ 表示 $[t - \tau, t]$[t−τ,t] 中与目标关联的一组候选检测（4.3节）。 每个 $H_{m, k}^t$Hm,kt​ 可能包含 $0$0 到 $\tau$τ 个检测（每帧可能有 $0$0 或 $1$1 个检测）。

给定所有现有和新目标的假设集，该算法使用图模型（4.3节）为所有目标（每个目标一个）找到最一致的一组假设（MAP）。作为关键特性，NMOT 能够修正在先前时间帧中产生的任何关联错误（对于时间窗口 $[t -\tau, t]$[t−τ,t] 内的检测）。

Model Representation

在详细介绍每个步骤之前，先讨论基础模型表示。将该模型表述为一个能量最小化框架：
$\hat{x} = \mathrm{argmin}_{x} E(\mathbb{A}^{* t - 1}, \mathbb{H}^t(x), \mathbb{D}_{t - \tau}^t, V_1^t)$x^=argminx​E(A∗t−1,Ht(x),Dt−τt​,V1t​)
其中 $x$x 是整数状态向量，指示为相应目标选择了哪个假设，$\mathbb{H}^t$Ht 是所有假设的集合 $\{ H_1^t, H_2^t, ... \}${H1t​,H2t​,...}，而 $\mathbb{H}^t(x)$Ht(x) 是一组选定假设 $\{H_{1, x_1}^t, H_{2, x_2}^t, ... \}${H1,x1​t​,H2,x2​t​,...}。解决优化问题时，可以通过使用选定的假设 $\mathbb{H}^t(\hat{x})$Ht(x^) 对 $\mathbb{A}^{* t - 1}$A∗t−1 进行扩展来唯一标识更新的目标 $\mathbb{A}^t$At。 后文隐去 $V_1^t$V1t​ 和$\mathbb{D}_{t - \tau}^t$Dt−τt​，以避免方程式混乱。能量定义如下：
$\begin{aligned} E(\mathbb{A}^{* t - 1}, \mathbb{H}^t(x)) &= \sum_{m \in \mathbb{A}^{* t - 1}} \Psi(A_m^{* t - 1}, H_{m, x_m}^t) \\ &+ \sum_{ (m, l) \in \mathbb{A}^{* t - 1} } \Phi(H_{m, x_m}^t, H_{l, x_l}^t) \end{aligned}$E(A∗t−1,Ht(x))​=m∈A∗t−1∑​Ψ(Am∗t−1​,Hm,xm​t​)+(m,l)∈A∗t−1∑​Φ(Hm,xm​t​,Hl,xl​t​)​
其中 $\Psi( \cdot )$Ψ(⋅) 编码单个目标的运动、外观和 ALFD 度量一致性，而 $\Phi( \cdot )$Φ(⋅) 表示不同目标之间的排他关系（例如，没有两个目标共享同一检测）。如有新进目标的假设，则将相应目标定义为一个空集 $A_m^{* t-1} = \text{\o}$Am∗t−1​=ø。

Single Target Consistency

该势函数度量假设 $H_{m, x_m}^t$Hm,xm​t​ 与目标 $A_m^{* t - 1}$Am∗t−1​ 的相容性。 数学上，可以将其分解为一元、成对和高阶项，如下所示：

$\begin{aligned} \Psi(A_m^{* t - 1}, H_{m, x_m}^{t}) & = \sum_{i \in H_{m, x_m}^t} \psi_u(A_m^{* t - 1}, d_i) \\ & + \sum_{(i, j) \in H_{m, x_m}^t} \psi_p(d_i, d_j) + \psi_{h}(A_m^{* t - 1}, H_{m, x_m}^t ) \end{aligned}$Ψ(Am∗t−1​,Hm,xm​t​)​=i∈Hm,xm​t​∑​ψu​(Am∗t−1​,di​)+(i,j)∈Hm,xm​t​∑​ψp​(di​,dj​)+ψh​(Am∗t−1​,Hm,xm​t​)​

$\psi_u$ψu​ 使用 ALFD 相似性度量和目标动态特性（5.1节）编码每个检测 $d_i$di​ 在目标假设 $H_{m, x_m}^{t}$Hm,xm​t​ 中的兼容性。

$\psi_p$ψp​ 使用 ALFD 度量 $H_{m, x_m}^{t}$Hm,xm​t​（5.2节）内检测之间的成对兼容性（假设的自我一致性）。

最后，$\psi_{h}$ψh​ 实现了一个长期的平滑度约束和外观一致性（5.3节）。

Mutual Exclusion

该势函数避免选择两个在图像平面上具有较大重叠（排斥力）的目标以及检测的重复分配。
NMOT 没有像匈牙利算法中那样使用“硬”排除约束，而是使用“软”代价函数来提高灵活性并简化计算。如果单目标一致性足够强，则可以克服软惩罚成本。同样，这种表述使得有可能重新使用在第4.3节中讨论的流行图推理算法。势能可以写成如下：
$\begin{aligned} \Phi(H_{m, x_m}^t , H_{l, x_l}^t ) &= \sum_{f=t - \tau}^t \alpha \cdot o^2(d(H_{m,x_m}^t, f), d(H_{l, x_l}^t, f)) \\ & + \beta \cdot \mathbb{I}(d(H_{m,x_m}^t, f), d(H_{l, x_l}^t, f)) \end{aligned}$Φ(Hm,xm​t​,Hl,xl​t​)​=f=t−τ∑t​α⋅o2(d(Hm,xm​t​,f),d(Hl,xl​t​,f))+β⋅I(d(Hm,xm​t​,f),d(Hl,xl​t​,f))​

其中 $d(H_{m,x_m}^t, f)$d(Hm,xm​t​,f) 在时间点 $f$f 给出假设 $H_{m,x_m}^t$Hm,xm​t​ 的相关检测（如果没有，返回 $\text{\o}$ø），$o^2(d_i, d_j) = 2 * IoU(d_i, d_j)^2$o2(di​,dj​)=2∗IoU(di​,dj​)2 ，并且 $\mathbb{I}(d_i, d_j)$I(di​,dj​) 是一个指标函数。式中前者惩罚假设之间有太多重叠，而后者则惩罚检测的重复分配。实验中使用 $\alpha = 0.5$α=0.5 和 $\beta = 100$β=100（足够大以避免重复分配）。

Hypothesis Generation

在实际中 $\mathbb{H}^t$Ht 的空间很大，因此无法对上述目标函数进行直接优化。 为了应对这一挑战，NMOT 首先针对每个目标分别提出了一组候选假设 $H_m$Hm​（图 5 (b)），然后使用 CRF 推理算法找到一个相干解（coherent solution, MAP）。

图 5. NMOT 算法的示意图。（a）给定一组现有目标 $\mathbb{A}^{t-1}$At−1 和检测 $\mathbb{D}_{t - \tau}^t$Dt−τt​，（b）使用小轨迹 $\mathcal{T}$T 生成一组候选假设 $\mathbb{H}^t$Ht。使用假设构建 CRF 模型，（c）使用推理算法选择最一致的解 $x$x，并且（d）通过用解 $\mathbb{H}^t(\hat{x})$Ht(x^) 扩展先前的目标 $\mathbb{A}^{t-1}$At−1 来获得输出目标 $\mathbb{A}^{t}$At。 详情见正文。

由于所有后续步骤都取决于生成的假设，因此拥有一套全面的目标假设至关重要。 NMOT 使用 tracklets 生成现有目标和新目标的假设。注意，由于独立生成每个目标的假设集，因此可以并行执行以下步骤。

Tracklet Generation

对于所有确定的检测（$\forall d_i \in \mathbb{D}_{t - \tau}^t,\ s.t.\ s_i > 0$∀di​∈Dt−τt​, s.t. si​>0），使用 ALFD 指标 $a_{A}$aA​ 构建一个 tracklet ：

• 从某个检测轨迹$\mathcal{T}_i = \{d_i\}$Ti​={di​} 开始，通过贪心算法添加最佳匹配检测 $d_k$dk​ 来增加轨迹，使得 $k = \mathrm{argmax}_{k \in \mathbb{D}_{t - \tau}^t \backslash \mathcal{T}_i} max_{j \in \mathcal{T}_i} a_{A}(d_j, d_k)$k=argmaxk∈Dt−τt​\Ti​​maxj∈Ti​​aA​(dj​,dk​)，其中 $\mathbb{D}_{t - \tau}^t \backslash \mathcal{T}_i$Dt−τt​\Ti​ 是 $[t-\tau, t]$[t−τ,t] 中不包括 $\mathcal{T}_i$Ti​ 中已包含帧的检测集。
• 如果最佳 ALFD 度量低于 $0.4$0.4 或 $\mathcal{T}_i$Ti​ 已满（检测到 $\tau$τ 个），则终止迭代。
• 此外，从 $[t - \tau, t]$[t−τ,t] 中的每个 $A_m^{t- 1}$Amt−1​ 中提取剩余检测，以获得额外的轨迹（即 $\forall m, A_m^{t -1} \backslash A_m^{*t - 1}$∀m,Amt−1​\Am∗t−1​）。
• 由于可以有相同的小轨迹，因此在输出集合 $\mathbb{T}$T 中仅保留唯一的小轨迹。

Hypotheses for Existing Targets

由轨迹集合 $\mathbb{T}$T 为每个现有目标 $A_m^{* t- 1}$Am∗t−1​ 生成一组目标假设 $H_m^t$Hmt​。为了避免不必要的大量假设，这里采用门控策略：

• 对于每个目标 $A_m^{* t- 1}$Am∗t−1​，使用具有多项式函数的最小二乘算法24获得目标预测器。实验中根据数据集改变多项式的阶数（MOT 为 $1$1，KITTI 为 $2$2）。
• 如果在 $t - \tau, t]$t−τ,t] 的任意帧中，预测和 $\mathcal{T}_i$Ti​ 中的检测重叠（IoU）大于某个阈值，则将 $\mathcal{T}_i$Ti​ 设置为 $H_m^t$Hmt​。在实践中，算法设置保守的阈值 $0.1$0.1 来获得丰富的假设。
• 忽略太旧的目标（在 $[t - \tau -T_{active}, t]$[t−τ−Tactive​,t] 中没有相关的检测）以减少不必要的计算负担。作者使用 $T_{active} = 1\ sec$Tactive​=1 sec。

New Target Hypotheses

由于新目标可以在任何时间、任何位置进入场景，因此需要自动识别新目标。可以通过将集合 $\mathbb{T}$T 中的任意小轨迹视为潜在的新目标来自然地识别新目标。我们对轨迹使用非最大抑制，以避免重复的新目标。对于每个 tracklet $\mathcal{T}_i$Ti​，只需添加一个空目标 $A_m^{* t- 1} = \text{\o}$Am∗t−1​=ø 到 $\mathbb{A}^{*T- 1}$A∗T−1，并将关联的假设设置为$H_m^T=\{\text{\o}，\mathcal{T}_i\}$HmT​={ø，Ti​}。

Inference with Dynamic Graphical Model

一旦有了所有新目标和现有目标的全部假设，就可以将问题表示为无向图模型的推理问题，其中一个节点代表目标，状态是假设索引，如图 5© 所示。 这个问题的主要挑战是：

• 图模型表示可能存在循环；

• 图的结构取决于每种情况下的假设。

为了有效地得到精确解，NMOT 首先对图的结构进行动态分析，并在结构分析的基础上应用适当的推理算法。

在给定图模型的情况下，使用连接组件分析17找到独立的子图（在图5（c）中用虚线框显示），并对每个子图并行执行独立的推理算法：

• 如果一个子图由多个节点组成，则使用结点树算法[21, libDAI]来获得对应子图的解。
• 否则，为目标选择最优假设。

找到状态 $x$x 后，可以通过用 $\mathbb{H}^t(x)$Ht(x) 扩充 $\mathbb{A}^{* t - 1}$A∗t−1 来唯一地标识新的目标集： $\mathbb{A}^{* t - 1} + \mathbb{H}^t(x) \rightarrow \mathbb{A}^t$A∗t−1+Ht(x)→At。 此过程使我们可以调整 $[t- \tau, t]$[t−τ,t] 中 $\mathbb{A}^{t - 1}$At−1 的任何关联（即添加、删除、替换或不修改）。

Model Details

本节将讨论公式3中描述的势函数的详细信息。

Unary potential

如前几节所述，NMOT 使用 ALFD 指标作为比较检测结果的主要关联度量。假设中每次检测的一元势函数可通过以下方法测量：

$\mu_A (A_m^{* t- 1}, d_i) = -\sum_{\Delta t \in \mathcal{N}} a_A(d(A_m^{* t- 1}, t_i - \Delta t), d_i)$μA​(Am∗t−1​,di​)=−Δt∈N∑​aA​(d(Am∗t−1​,ti​−Δt),di​)

其中 $\mathcal{N}$N 是一组预定义的邻帧距离，而 $d(A_m^{* t- 1}, t_i)$d(Am∗t−1​,ti​) 给出 $A_m^{* t - 1}$Am∗t−1​ 在 $t_i$ti​ 帧的关联检测 。尽管可以定义任意大集合 $\mathcal{N}$N，但在建模长期亲和度量时，为了计算效率，作者选择 $\mathcal{N} = \{1, 2, 5, 10, 20\}$N={1,2,5,10,20}。

尽管 ALFD 度量在大多数情况下都提供了非常强大的信息，但仍有少许失败情况，包括遮挡、错误的 IPT 等。为补足此类情况，作者设计了一个附加的目标动力学（TD）特性 $\mu_T (A_m^{* t- 1}, d_i)$μT​(Am∗t−1​,di​)。同样使用在4.2节中讨论的多项式最小二乘预测器，作者将特征定义如下：

$\mu_T(A_m^{* t - 1}, d_i) = \left\{\begin{matrix} \infty,\ \ \ \ if\ o^2(p(A_m^{* t - 1}, t_i), d_i) < 0.5\\ -\eta^{t_i - f(A_m^{* t - 1})} o^2(p(A_m^{* t - 1}, t_i), d_i),\ \ \ \ otherwise \end{matrix}\right.$μT​(Am∗t−1​,di​)={∞,    if o2(p(Am∗t−1​,ti​),di​)<0.5−ηti​−f(Am∗t−1​)o2(p(Am∗t−1​,ti​),di​),    otherwise​

其中 $\eta$η 是一个衰减因子（$0.98$0.98），它折算了长期预测，$f(A_m^{* t - 1})$f(Am∗t−1​) 表示 $A_m^{* t - 1}$Am∗t−1​ 的最后一个关联帧 ，$o^2$o2 代表在4.1节中讨论的 $IoU^2$IoU2，而 $p$p 是在4.2节中描述的多项式最小二乘预测器。

使用这两个度量，NMOT 将一元势函数 $\psi_u(A_m^{* t- 1}, d_i)$ψu​(Am∗t−1​,di​) 定义为：

$\psi_u(A_m^{* t - 1}, d_i) = \min(\mu_A(A_m^{* t - 1}, d_i), \mu_T(A_m^{* t - 1}, d_i)) - s_i$ψu​(Am∗t−1​,di​)=min(μA​(Am∗t−1​,di​),μT​(Am∗t−1​,di​))−si​

其中 $s_i$si​ 表示 $d_i$di​ 的检测分数。$\mathrm{min}$min 运算符使算法能够在大多数情况下使用 ALFD 度量，但仅当 TD 度量非常有把握时（预测和检测之间的重叠超过 $0.5$0.5）才使用它。如果 $A_m^{* t - 1}$Am∗t−1​ 为空，则势函数变为 $-s_i$−si​。

Pairwise potential

二元势函数 $\psi_p(\cdot)$ψp​(⋅) 仅由 ALFD 度量定义。与一元势函数相似，在 $H_{m, x_m}^t$Hm,xm​t​ 中定义检测之间的成对关系，
$\psi_p (d_i, d_j) = \left\{\begin{matrix} -a_A(d_i, d_j),\ \ \ if\ |d_i-d_j| \in \mathcal{N}\\ 0,\ \ \ \ \ \ otherwise \end{matrix}\right.$ψp​(di​,dj​)={−aA​(di​,dj​),   if ∣di​−dj​∣∈N0,      otherwise​

它度量假设 $H_{m, x_m}^t$Hm,xm​t​ 的自洽性。

High-order potential

NMOT 采用高阶势函数来调整目标关联过程，使其具有物理可行性和外观相似性。

• 首先，受[2, GMCP]的启发，NMOT 通过惩罚呈现突然运动的假设来实现物理可行性。
• 其次，类似于[GMCP]，NMOT 编码了 $A_m^{* t- 1}$Am∗t−1​ 和 $H_{m, x_m}^t$Hm,xm​t​ 中所有检测之间的长期外观相似性。

直觉由以下势函数编码：
$\begin{aligned} \psi_h (A_m^{* t- 1}, H_{m, x_m}^t) &= \gamma \cdot \sum_{i \in H_{m, x_m}^t} \xi(p(A_m^{* t- 1} \cup H_{m, x_m}^t, t_i), d_i) \\ & + \epsilon \cdot \sum_{(i, j) \in A_m^{* t- 1} \cup H_{m, x_m}^t} \theta - K(d_i, d_j) \end{aligned}$ψh​(Am∗t−1​,Hm,xm​t​)​=γ⋅i∈Hm,xm​t​∑​ξ(p(Am∗t−1​∪Hm,xm​t​,ti​),di​)+ϵ⋅(i,j)∈Am∗t−1​∪Hm,xm​t​∑​θ−K(di​,dj​)​

其中 $\gamma, \epsilon, \theta$γ,ϵ,θ 是标量参数，$\xi(a, b)$ξ(a,b) 测量两个框中 $(x, y, height)$(x,y,height) 的平方距离之和，且由 $p$p 在 $[t- \tau, t]$[t−τ,t] 期间的平均高度正则，而 $K(d_i, d_j)$K(di​,dj​) 表示关联检测的颜色直方图的交叉核。

NMOT 使用 LAB 颜色直方图的金字塔，其中第一层是整个方框，第二层是 $3 \times 3$3×3 的网格。直方图仅使用 A 通道和B 通道，每个通道具有 $4$4 个区间（结果 $4 \times 4 \times (1+9)$4×4×(1+9) 区间）。实际中使用 $(\gamma, \epsilon, \theta) = (20, 0.4, 0.8)$(γ,ϵ,θ)=(20,0.4,0.8)。

Experimental Evaluation

为了评估所提出的算法，作者使用 KITTI 目标跟踪基准和 MOTChallenge 数据集。

KITTI 跟踪基准由大约$19000$19000帧（$\sim32$∼32 分钟）组成。该数据集由 $21$21 段训练和 $29$29 段测试视频序列组成，这些视频序列是使用安装在车辆顶部的摄像头在行驶中录制的。每个视频序列的帧数从 $78$78 到 $1176$1176 帧不等，其中目标对象数量不定（汽车、行人和骑自行车的人）。这些视频以 $10$10 FPS录制。数据集非常具有挑战性，因为：

• 场景拥挤（遮挡和杂乱）

• 相机不稳定

• 目标对象出现在任意位置，大小不一

在监视摄像机的多目标跟踪中采用的许多常规假设（技术）在这种情况下不适用（例如固定的进（出）位置、背景减除等）。

MOTChallenge 共计 $11,286$11,286 帧（$\sim16.5$∼16.5 分钟），FPS 不统一。数据集由 $11$11 段训练和 $11$11 段测试视频序列组成。其中一些视频使用移动平台录制，另一些则来自监控视频。所有序列只包含行人。组成视频具有各种配置，因此针对特定场景进行了特别调整的跟踪算法通常不会很好地工作。

评估采用了 CLEAR MOT 跟踪指标。为了与其他方法进行公平比较，作者使用了两个数据集提供的参考目标检测。

ALFD Analysis

首先对所提 ALFD 相似性指标进行去除分析。从训练集中选择两个序列，即 KITTI 的0001和 MOTChallenge 的 PETS09-S2L1进行分析。给定所有检测和真实标注，首先找到检测和注释之间的标签关联。对于每个检测，如果重叠大于 $0.5$0.5，则分配真实 id。作者在 $1, 2, 5, 10, 20$1,2,5,10,20 帧距离（$\Delta t$Δt）中收集所有可能的检测对，以获得正负对。以两检测平均高度归一化后的底部中心之间的L2距离（NDist2）以及两者的颜色直方图之间的交叉核（HistIK）作为亲和力度量基线。图 6 和 Table 1. 显示了每个亲和力度量的 ROC 曲线和 AUC。可以观察到，无论摄像机配置和物体类型如何，ALFD 亲和力度量在所有时间范围内均表现最佳。随着时间距离的增加，其他指标如预期的那样很快变得不可靠，而 ALFD 指标仍然可以提供强有力的线索来比较不同的检测结果。

KITTI Testing Benchmark Evaluation

Table 2. 总结了 NMOT 和其他最新算法在整个 $28$28 段测试视频序列的评估准确性（比较也可在 http://www.cvlibs.net/datasets/kitti/eval_tracking.php 中获得，其中包括其他匿名提交）。作者还使用一元匹配函数和匈牙利算法实现了在线跟踪算法（HM）。设置任何代价大于 $- 0.5$−0.5 的匹配为无效匹配。

在随后的评估中，作者设置时间窗口 $\tau = 10$τ=10 并过滤掉只有一个检测或检测分数中值低于 $0$0 的目标。使用卡尔曼滤波器从离散检测集 $\mathbb{A}$A 中获得连续轨迹。

由于 KITTI 评估系统未提供骑车人类别的结果（由于缺乏足够的数据），因此作者报告汽车和行人类别的准确性。作者还以更先进的检测结果（HM+ [32]和{NOMT+ [32]）进行了实验。

MOT Challenge Evaluation

Table 3. 总结了 NMOT 和其他最新算法在 MOTChallenge 测试视频序列上的评估准确性（比较也可在 http://nyx.ethz.ch/view_results.php?chl=2 中获得）。该网站提供了一组使用[9]获得的参考检测。

与 KITTI 实验相似， NMOT 比其他最新的方法有显著的优势。算法实现了最低的身份交换和碎片，同时实现了最高的检测精度（最低的误报（FP）和漏报（FN））。反过来，与其他现有技术相比，NMOT 记录的 MOTA 最高，且领先幅度较大（$> 14\%$>14%）。 这两个实验表明，ALFD 度量和 NMOT 算法通常适用于任意应用场景。

Timing Analysis

为了解 NMOT 方法的及时性，作者通过计算检测时间（$\mathbb{A}^T$AT 中 $d_i$di​ 的 $t_i$ti​）与最后一个关联时间之间的差来测量延迟。最后一个关联时间定义为：

• 如果在 $t$t 时刻检测 $d_i$di​ 新添加到目标 $A_m^t$Amt​ 或替换 $A_m^{t-1}$Amt−1​ 中的任何其他检测 $d_j$dj​（例如 $t_i = t_j$ti​=tj​），记录 $t$t 为 $d_i$di​ 的最后关联时间；
• 如果 $d_i$di​ 在 $A_m^{t-1}$Amt−1​ 中，则对 $d_i$di​ 的最后关联时间不做任何更改。

最后一个关联时间告诉我们，算法在何时首次将 $d_i$di​ 识别为 $A_m^T$AmT​ （目标 $m$m 的最终轨迹输出）的一部分。KITTI 测试集的平均值和标准差分别为 $0.59\pm 1.75$0.59±1.75，搭配[32] 为 $0.66\pm 1.87$0.66±1.87 （没有延迟的比例为 $84.7\%$84.7% 和 $83.9\%$83.9%），MOTChallenge 测试集的平均值和标准差分别为$0.87\pm 2.04$0.87±2.04（没有延迟的占比为 $77.6\%$77.6%）。这表明 NMOT 确实是一种近乎在线的方法。

NMOT 算法不仅不仅精度高，而且非常高效。利用并行计算，在16核的2.5GHz CPU 上可以实现实时效率（$\sim 10 FPS$∼10FPS）。Table 4. 总结了每个计算模块所花费的时间。

参考资料：

• 多目标跟踪方法 NOMT 学习与总结
• 基于层次关联的鲁棒多目标跟踪
• Machine learning for high-speed corner detection
• MOT 评价指标-“Evaluating Multiple Object Tracking Performance, the CLEAR MOT Metrics”
• Multi-Target Multi-Camera Tracking （MTMC Tracking）评价指标
• Course 8 An Introduction to theAn Introduction to theKalman FilterKalman Filter
• Belief Propagation 解决计算机视觉问题
• Histogram intersection(直方图交叉核,Pyramid Match Kernel)
• histogram（直方图）里的bin是什么意思呢？