Multiple People Tracking by Lifted Multicut and Person Re-identiﬁcation

原文链接：https://openaccess.thecvf.com/content_cvpr_2017/papers/Tang_Multiple_People_Tracking_CVPR_2017_paper.pdf

主要工作

将MCLMP融入到多目标跟踪领域

MCLMP（Minimum Cost Lifted Multicut Problem）——最小花费改进多边切割问题，之前这类方法主要用在经典的图像分割领域，以像素点或者像素块作为图节点，为节点之间的每条边分配去切断惩罚（边权重，有正有负），在一定的约束条件下对节点间多余的边进行切割（切断图像块与图像块之间的联系，剩余聚合的图像块便可以看作一个具有相同语义的区域）以最小化惩罚，然后得到聚类结果。这类方法最重要的是通过一些合理的节点连接权重的度量函数，衡量节点之间的关系，然后便是利用一些启发式的算法对图进行切割优化。

应用到多目标跟踪领域，作者将图的每个节点等效成视频帧中的每个检测到的目标，同一帧中的目标之间可以彼此相连（这里相连的原因是作者对检测得到的bbox没有进行NMS会有一些重复的框），然后对前后相差$\delta_t$帧的目标也进行连接（通过中心点距离或者bbox或者外观相似的阈值条件确定），此时的连接都是regular edges，另外还有一点就是通过additional edges去连接部分外观度量特别相似，然后帧间隔大于$\delta_t$的目标。边的连接权重或者切断惩罚通过下面的向量计算式得到:
$$
\begin{array}{c}
c_e=\log \frac{1-p_e}{pe}=-<\theta_{\gamma}, f^{(e)}> \
f^{(e)} \leftarrow \left( f_{st}, f_{dm}, f_{reID}, f_{st}^2,f_{st} \dot \ f_{dm} \dots, \xi_{min}^2\right), \ f^{(e)} \in \cal{R}^{14}
\end{array}
$$
其中：
- $\theta_{\gamma}$为可学习的映射参数（文中在训练跟踪视频的时候使用了一个Logistic Regression来预测这个参数）
- $f_{st}$代表检测框中心点和高相似度：$f_{s t}=\frac{\sqrt{\left(x_{v}-x_{w}\right)^{2}+\left(y_{v}-y_{w}\right)^{2}}}{\bar{h}}$
- $f_{dm}$代表两个目标的关键点集合匹配度（感觉有点儿像交并比），但又不完全是（图1是第一篇用这种DeepMatching的论文：Multiperson tracking by multicuts and deep matching）
- $f_{reID}$代表融合目标关键点特征的目标相似度（by StackNetPose），具体怎么融合看主要工作2
- $\xi_{min}$表示两个目标检测置信度中，较小的那个置信度。
图1 Deep Matching 示意图

提出融合人体外观和人体姿态的深度评估网络

作者提出了融合深度外观和人体关键点的评估网络名为：StackNetPose。具体做法为，先通过单独的人体关键点检测网络，得到各个关键点（每个行人图像14个points）的响应图（宽高与原图一致），然后融合成7张单通道的heatmap，两张行人图像得到14个heatmap（如下图中绿色部分），之后将这些heatmap与两张行人图像的RGB通道堆叠得到一个拥有20个通道输入的特征图，最后通过一个分类网络评估行人图像之间的相似度。

图2 深度提取网络示意图

MCLMP问题建模及约束解释

最小花费改进多边切割问题的定义或者用法如第一节所述，下面以一个简单得了例子来表述如何构建一个MCLMP模型。这是一个简单的双向图模型，每条边旁边的数字代表切掉这条表对应的花费或者收益，实线连接的边表示连接（joint），虚线连接的边表示剪掉（cut）。

图3 连接关系图

问题建模

MCLMP的规划模型如下：

目标函数
$$
\min {x \in{0,1} E^{\prime}} \sum{e \in E^{\prime}} c_{e} x_{e}
$$

其中$E’$表示图中所有的边（包括剪掉和连接的，包括regular edges 和 additional edges，additional edges是自己设置的），$c_e$表示$e$这条边剪掉所带来的花费，比如上图中$V_1，V_6$两个节点的弧形连接边，如果将这个边cut，那么将会花费5。$x_e$表示边的连接状态，$x_e=1$表示这条边被cut，$x_e=0$表示这条边是joint。因此对于一个都是joint关系的图，总体的花费都为0，需要cut掉一些产生收益的负权边（如上图的-1，-0.5的这些边）来进一步减少花费。
约束条件

约束1：
$$
\forall Y \in \operatorname{cycles}(G), \ \ \forall e \in Y: x_{e} \leq \sum_{e^{\prime} \in Y \backslash{e}} x_{e^{\prime}}
$$

直观表述：对任意一个循环连接（cut的虚线边也算作连接，也存在循环连接），循环圈中的每条边的连接状态值，小于等于剩余边连接状态值的之和。通俗解释，一个循环连接，要么就全都是joint的，此时所有的$x_e=0$，有$0 \le 0$，约束成立；要么就要有两条及以上的边是cut的，此时对被cut的边有$1 \le 1+k$，$k$为循环连接中cut边数量-2， $k \ge 0$。

约束2：
$$
\forall v w \in E^{\prime} \backslash E , \ \ \forall P \in v w \text {-paths(G) }: x_{v w} \leq \sum_{e \in P} x_{e}
$$

直观表述：对任意一条additional edges,其任意一条可行的regular edges组成的path（状态为0才能称之为path），path中所有连接边的状态值之和应该大于additional edges直接连接的状态值。通俗解释：任意一条additional edges（比如图3中的V1——V6边）状态为joint的前提是存在一个同样为joint的连接通路，这个通路可以是：V1——V2——V3——V6，也可以是：V1——V2——V5——V6，也可以两个都存在。

约束3：
$$
\forall v w \in E^{\prime} \backslash E , \ \ \forall C \in v w-\operatorname{cuts}(G): 1-x_{v w} \leq \sum_{e \in C}\left(1-x_{e}\right)
$$

通俗表述：对任意一条additional edges（比如图3中的V1——V6边）状态为cut的前提是所有V1——V6的连接通路均不存在一些状态为cut的边，这些通路包括：V1——V2——V3——V6，也可以是：V1——V2——V5——V6，V1——V4——V5——V6，都要有cut边。