论文地址：Online Multi-Target Tracking with Tensor-Based High-Order Graph Matching
基于高阶图匹配的多目标跟踪器
一、 摘要二、 相关介绍三、 高阶超图匹配1. 问题设置2. 张量公式3. 双向单元ℓ1-norm迭代4. 构建高阶图匹配张量A． 外貌亲密度B． 运动一致性C． 空间潜力四、 实验五、 总结一、 摘要
将目标相应轨迹匹配投影为一个超图匹配问题，在关联的所有序列上最大化多线性目标函数。由一个张量来定义关联元组之间的成对信息的相似度，运动一致性和空间结构的关系。并且传统的外貌特征提取直接使用矩形边界框，当边界框重叠大的时侯，会影响外貌相似度矩阵的计算，本方法提出了一个基于object mask的相似度矩阵，只使用真实目标区域的特征来改良之前的问题。
创新贡献：
提出了一种在线MTT框架，通过将MTT中相应关系的搜索构造为一个超序图匹配问题，可以灵活地集成高阶信息。提出一个双向单元ℓ1-norm张量迭代算法区解决超图中轨迹和检测1对1匹配的问题。为了更好地刻画成对外观亲和力，提出了一种基于目标 mask的度量学习网络
二、 相关介绍
现在随着检测器的繁荣，DBT范式取得了很大的成功，有些网络甚至直接将目标轨迹生成转变为一个全局优化问题，直接一次性处理视频。
另一种最近流行的批处理解决方案（offline）是将数据关联作为子图分解问题来考虑的子图多分割任务，在计算点之间亲密度的同时还可以通过传递性约束确保长期时间一致性。由于是批处理，所以不是online 方法。
本论文提出了一种基于张量的高阶图匹配的在线多目标跟踪框架，以引入更多的全局信息进行匹配。
具体地说，搜索当前检测观测值与历史上一些选定的跟踪检测值之间的对应关系作为一个超图匹配问题，其高阶能量函数由成对的外观相似度、运动一致性和空间结构信息组成。
在超图中，每个目标(检测轨迹中的单独目标或当前检测观察)用一个节点表示，每个轨迹或观察用一个超边缘表示。提取超边缘之间的几何关系作为空间结构信息（红线）。匹配问题是找到观测值和保持其拓扑的轨迹之间的超边对应，如下图：
举例说明观察轨迹与高阶图的匹配：
由轨迹采样或检测的观测组成的超边缘用椭圆表示。候选分配由实线和点线(E1 ~E18)表示，红线反映它们的几何关系。我们的目标是通过超图匹配找到保持其拓扑的节点对应，然后根据节点对应分配观测到相应的轨迹。D表示缺失检测，实线为最后得到的关联，则我们可以将O1,O2分配给T2, T3，轨迹T1在当前阶段消失。(E1 ~ E18)的权重代表通过超图匹配获得的匹配可能性，检测和轨迹之间的分配在他们之间产生，例如O2分配给T3，相应的E16~E18值会很高。轨迹T1匹配到虚拟节点D，代表检测丢失，在缺失外观相似度的情况下，由几何关系推导。
为了实现轨迹和检测一对一的关联，双向单元ℓ1-norm迭代算法可以解决超图匹配问题。一个轨迹到观测（向前）和观测到轨迹（向后）两者的总能量应当都是有界的单元，这个迭代更新的基本思想是通过张量操作后对分配矩阵的行和列分别进行ℓ1 单元标准化。
外貌亲密度计算方面， 不同于传统的方法计算外貌亲密度使用边界框中的特征，作者认为边界框的重叠会影响外貌的提取与亲密度的计算，所以提出了另一种基于object mask的参数学习网络，只考虑真正前景的特征，而不是用带有背景噪声的边界框计算。
三、 高阶超图匹配
1. 问题设置
在时刻ttt,假设轨迹T={T1,T2,TN}\mathcal T = \{T_1,T_2,T_N\}T={T1,T2,TN}根据某些原则（费布拉切数列）采样生成N1=∑n∣T∣∣Tn∣N_1=∑_n^{|\mathcal T|}|T_n |N1=∑n∣T∣∣Tn∣个已追踪检测，TnT_nTn表示从第nnn个轨迹采样检测的数量，当前帧检测到N2N_2N2个观察值，因为轨迹的消失或者新生，以及误检或漏检，N1N_1N1一般不等于N2N_2N2。从111到Ns(s=1,2)N_s(s=1,2)Ns(s=1,2)，is,js,ksi_s, j_s, k_sis,js,ks不断变化。使用i=(i1,i2),j=(j1,j2),k=(k1,k2)i = (i_1,i_2),j=(j_1,j_2),k=(k_1,k_2)i=(i1,i2),j=(j1,j2),k=(k1,k2)表示检测观察值和历史轨迹可能的关联。
使用Si11,Si21S_{i_1}^1,S_{i_2}^1Si11,Si21分别表示轨迹和观察值，将轨迹和观察值匹配问题就转变为寻找一个N1×N2N_1×N_2N1×N2的分配矩阵XXX。X(i1,i2)X_{(i_1,i_2 )}X(i1,i2)即XiX_iXi，当Si11,Si21S_{i_1}^1,S_{i_2}^1Si11,Si21符合匹配则X(i1,i2)X_{(i_1,i_2 )}X(i1,i2)为1，否则则为0。在多目标追踪任务中，一个轨迹只能最多分配给一个目标检测，反之亦然，每行每列的总和为1，认为X\mathcal XX为分配矩阵的集合:
X={X∈{0,1}N1×N2}s.t.∀i1,∑i1Xi1,i2=1;∀i2,∑i2Xi1,i2=1(1)\begin{array}{l} \mathcal{X}=\left\{X \in\{0,1\}^{N_{1} \times N_{2}}\right\} \\ \text { s.t. } \quad \forall i_{1}, \sum_{i_{1}} X_{i_{1}, i_{2}}=1 ; \forall i_{2}, \sum_{i_{2}} X_{i_{1}, i_{2}}=1 \end{array} \tag{1}X={X∈{0,1}N1×N2}s.t.∀i1,∑i1Xi1,i2=1;∀i2,∑i2Xi1,i2=1(1)
MOT任务目的是最大化X\mathcal XX的得分，从候选空间中选择N=min(N1,N2)N = min(N_1,N_2)N=min(N1,N2)个最佳连接：
score(X)=Hc1c2⋯cNXc1Xc2⋯XcN(2)\operatorname{score}(\mathcal{X})=H_{c_{1} c_{2} \cdots c_{N}} X_{c_{1}} X_{c_{2}} \cdots X_{c_{N}} \tag{2} score(X)=Hc1c2⋯cNXc1Xc2⋯XcN(2)
ci∈RN1N2,i=1,2,…,Nc_i∈R^{N_1 N_2 },i=1,2,…,Nci∈RN1N2,i=1,2,…,N代表候选连接的下标，每个下标代表一组匹配，Hc1c2⋯cNH_{c_1 c_2⋯c_N }Hc1c2⋯cN是关于连接组合的潜在整合函数,下面会介绍。HHH得分越高，则匹配的组合越多。
但是这样操作当考虑nnn阶信息时，搜索空间的计算量会非常大。因此作者只采用了p(p≤3)p(p≤3)p(p≤3)阶。P=1,2,3P=1,2,3P=1,2,3分别对应1对1，2对2，3对3对比匹配。当然，高阶信息可以被直接整合。为了简化，模型使用p=3p=3p=3，即3对3进行对比匹配，匹配问题变为：
maxscore(X)=∑i,j,kHi,j,kXiXjXks.t.{∑i2Xi1i2=1,i1=1,2,⋯,N1∑i1Xi1i2=1,i2=1,2,⋯,N2(3)\begin{array}{l} \max \quad \operatorname{score}(\mathcal{X})=\sum_{i, j, k} H_{i, j, k} X_{i} X_{j} X_{k} \\ \text { s.t. } \quad\left\{\begin{array}{ll} \sum_{i_{2}} X_{i_{1} i_{2}}=1, \quad i_{1}=1,2, \cdots, N_{1} \\ \sum_{i_{1}} X_{i_{1} i_{2}}=1, \quad i_{2}=1,2, \cdots, N_{2} \end{array}\right. \end{array} \tag{3} maxscore(X)=∑i,j,kHi,j,kXiXjXks.t.{∑i2Xi1i2=1,i1=1,2,⋯,N1∑i1Xi1i2=1,i2=1,2,⋯,N2(3)
如下图：
（在轨迹和观测集合中分别添加虚拟节点，以解释轨迹的开始、结束或遗漏的检测。一个单元ℓ1-norm虚拟节点的约束不能满足需求。）
观察检测Oi2O_{i_2 }Oi2通过连接选择分配给了相应的第n条轨迹轨迹：
n=argmaxn1∣Tn∣∑i1Xi1i2,∀i1∈Tn(4)n=\operatorname{argmax}_{n} \frac{1}{\left|T_{n}\right|} \sum_{i_{1}} X_{i_{1} i_{2}}, \quad \forall i_{1} \in T_{n} \tag{4} n=argmaxn∣Tn∣1i1∑Xi1i2,∀i1∈Tn(4)
n=1,2,…,∣Tn∣n=1,2,…,|\mathcal T_n |n=1,2,…,∣Tn∣是轨迹索引，具体过程如下：
1：序列中所有检测D
2：序列帧数F
3：逐帧进行操作
4：从已存在轨迹TiT_iTi中进行采样多个轨迹检测
5：当前帧的检测OfO_fOf
6：通过Eq.(7)Eq.(7)Eq.(7)挑选候选可能连接X\mathcal XX
7：通过Eq.(8)Eq.(8)Eq.(8)计算候选连接的高阶能量张量
8：随机赋值VVV进行迭代更新,匹配小于阈值退出
9：更新并返回TTT
2. 张量公式
张量即高维矩阵，KKK阶张量S∈RI1×I2⋅⋅⋅×IKS ∈ R^{I_1×I_2···×I_K }S∈RI1×I2⋅⋅⋅×IK，每个元素代表Si1…ik…iK(1≤ik≤iK)S_{i_1…i_k…i_K }(1≤i_k≤i_K)Si1…ik…iK(1≤ik≤iK)，张量的每个维度代表一种模式。
一个张量和一个向量可以像矩阵和向量一样相乘，表示如下:
B=S⊗nVBi1…in−1in+1…iK=∑inSi1…in−1in…iKVin\begin{array}{l} \mathcal{B}=\mathcal{S} \otimes_{n} V \\ \mathcal{B}_{i_{1} \ldots i_{n-1} i_{n+1} \ldots i_{K}}=\sum_{i_{n}} \mathcal{S}_{i_{1} \ldots i_{n-1} i_{n} \ldots i_{K}} V_{i_{n}} \end{array} B=S⊗nVBi1…in−1in+1…iK=∑inSi1…in−1in…iKVin
VVV是InI_nIn维度的向量，相乘后获得B∈RI1×I2⋅⋅⋅In−1×In+1…×IkB∈ R^{I_1×I_2···I_{n-1}×I_{n+1}…×I_k }B∈RI1×I2⋅⋅⋅In−1×In+1…×Ik, ⊗n⊗_n⊗n表示第nnn维上的Kronecker积。
那么下面的Eq.(5)Eq.(5)Eq.(5)可以表示为一个可以通过幂次迭代算法有效求解的张量逼近问题：
max∑Si1i2⋯iKVi1(1)Vi2(2)⋯ViK(K)s.t.∥Vk∥22=1,∀k∈{1,2,…,K}(5)\begin{array}{c} \max \sum \mathcal{S}_{i_{1} i_{2} \cdots i_{K}} V_{i_{1}}^{(1)} V_{i_{2}}^{(2)} \cdots V_{i_{K}}^{(K)} \\ \text { s.t. }\left\|V^{k}\right\|_{2}^{2}=1, \forall k \in\{1,2, \ldots, K\} \end{array} \tag{5} max∑Si1i2⋯iKVi1(1)Vi2(2)⋯ViK(K)s.t.∥∥Vk∥∥22=1,∀k∈{1,2,…,K}(5)
3. 双向单元ℓ1-norm迭代
匹配问题Eq.(3)Eq.(3)Eq.(3)尝试获得一个分配矩阵，这里使用双向单元ℓ1-norm迭代去解决。基本思想是通过引入Yi2=Xi,(Yi∈[0,1])Y_i^2=X_i,(Y_i∈[0,1])Yi2=Xi,(Yi∈[0,1])来重改Eq.(3)将ℓ1−normℓ1-normℓ1−norm先变为l2−norml_2-norml2−norm：
maxY∑i,j,kHi,j,kYi2Yj2Yk2s.t.{∑i2Yi1i22=1,i1=1,2,⋯,N1∑i1Yi1i22=1,i2=1,2,⋯,N2(6)\begin{array}{l} \max _{Y} \sum_{i, j, k} H_{i, j, k} Y_{i}^{2} Y_{j}^{2} Y_{k}^{2} \\ \text { s.t. } \quad\left\{\begin{array}{ll} \sum_{i_{2}} Y_{i_{1} i_{2}}^{2}=1, \quad i_{1}=1,2, \cdots, N_{1} \\ \sum_{i_{1}} Y_{i_{1} i_{2}}^{2}=1, \quad i_{2}=1,2, \cdots, N_{2} \end{array}\right. \end{array} \tag{6}maxY∑i,j,kHi,j,kYi2Yj2Yk2s.t.{∑i2Yi1i22=1,i1=1,2,⋯,N1∑i1Yi1i22=1,i2=1,2,⋯,N2(6)
然后分别对赋值矩阵XXX的行和列进行l2l_2l2单位归一化，迭代更新解。在算法111中体现，○○○表示hadamard乘积（元素相乘）。⊗k⊗_k⊗k表示Kronecker积（张量积），经过证明收敛。
4. 构建高阶图匹配张量
假设轨迹集T={T1,T2,⋅⋅⋅,TNT}T = \{T_1,T_2,· · · ,T_{N_T}\}T={T1,T2,⋅⋅⋅,TNT}，当前帧检测的观察集O={O1,O2,⋅⋅⋅,ON2}O = \{O_1,O_2,· · · ,O_{N_2} \}O={O1,O2,⋅⋅⋅,ON2}，时间N\mathcal NN根据费布拉切数列从TTT中采样获得的追踪检测集D={D1,D2,⋅⋅⋅,DN1}D=\{D_1,D_2,· · · ,D_{N_1}\}D={D1,D2,⋅⋅⋅,DN1}。Di,OjD_i,O_jDi,Oj为四元表示(x,y,w,h)(x,y,w,h)(x,y,w,h)，代表边界框中心位置，宽和高。依据Eq.(7)Eq.(7)Eq.(7)，通过一个距离阈值ηηη去过滤DDD和OOO的连接，避免搜索由于一对一地将跟踪的检测与观测连接而产生的巨大的解决空间：
C={(i1,i2)∣Di1∈Tt,d(Pt,Oi2)hi2≤η}(7)\mathcal{C}=\left\{\left(i_{1}, i_{2}\right) \mid D_{i_{1}} \in T_{t}, \frac{d\left(P_{t}, O_{i_{2}}\right)}{h_{i_{2}}} \leq \eta\right\} \tag{7} C={(i1,i2)∣Di1∈Tt,hi2d(Pt,Oi2)≤η}(7)
PtP_tPt表示当前时刻轨迹TtT_tTt均匀运动假设预测的位置，hi2h_{i_2 }hi2表示观测值Oi2O_{i_2 }Oi2的高，d(a,b)d(a,b)d(a,b)表示a，ba，ba，b中心点的欧氏距离。
然后构造一个高阶张量H∈RK×K×K,K=∣C∣H ∈ R^{K×K×K},K = |\mathcal C|H∈RK×K×K,K=∣C∣来整合外貌相似度，运动一致性和空间结构潜在性：
Hijk=ϕa(i,j,k)ϕm(i,j,k)ϕs(i,j,k)(8)H_{i j k}=\phi_{a}(i, j, k) \phi_{m}(i, j, k) \phi_{s}(i, j, k) \tag{8}Hijk=ϕa(i,j,k)ϕm(i,j,k)ϕs(i,j,k)(8)
i,j,k∈C，ϕa(i,j,k)，ϕm(i,j,k)，ϕs(i,j,k)i,j,k ∈ \mathcal C，ϕ_a (i,j,k)，ϕ_m (i,j,k)，ϕ_s (i,j,k)i,j,k∈C，ϕa(i,j,k)，ϕm(i,j,k)，ϕs(i,j,k)分别代表当同时选择连接i，j，ki，j，ki，j，k时的外貌相似度，运动一致性和空间潜在结构。
A． 外貌亲密度
外貌亲密度常用于数据关联，不同目标之间的外貌亲密度应当相对较小，相同目标的亲密度应该较大。许多方法中，使用成对或者三组行人补丁作为输入的一个孪生网络来获得亲密度矩阵，但是当边界框重叠时，这种方法由于共享特征而无法分辨身份，因此我们使用一个基于ResNet-FPN作为backbone的Mask RCNN的孪生网络来只在maskmaskmask区域提取外貌特征。
目标边界框以及maskmaskmask由Mask RCNN获得，底部特征（ResNet50第三阶段的最后卷积层）通过mask选择。然后选取三组样本作为浅层孪生网络的输入，提取128维的外观特征，三元组损失为：
L=∑imax(cos(predi,negi)−cos(predi,posi)+m,0)(9)\mathcal{L}=\sum_{i} \max \left(\cos \left(p r e d_{i}, n e g_{i}\right)-\cos \left(p r e d_{i}, p o s_{i}\right)+m, 0\right) \tag{9} L=i∑max(cos(predi,negi)−cos(predi,posi)+m,0)(9)
predi，posi，negipred_i，pos_i，neg_ipredi，posi，negi分别表示预测样本，正样本和负样本。mmm代表正确错误样本对的分隔范围，cos(a,b)cos(a,b)cos(a,b)代表aaa和bbb的余弦距离。
计算选择连接元组时外观亲密度所产生的能量：
ϕa(i,j,k)=aiajak(10)\phi_{a}(i, j, k)=a_{i} a_{j} a_{k} \tag{10} ϕa(i,j,k)=aiajak(10)
ai=a(i1,i2)=cos(fi1,fi2),fi⋅a_i= a(i_1,i_2 )=cos(f_{i_1 },f_{i_2 } ), f_{i_· }ai=a(i1,i2)=cos(fi1,fi2),fi⋅代表网络提取的深度特征。
B． 运动一致性
一般情况下，会假设一个目标的速度在短时间内是恒定的。可以使用一个简单的线性模型来预测目标当前状态(x,y,w,h)(x,y,w,h)(x,y,w,h)，运动一致性计算如下：
ϕm(i,j,k)=exp(−w13∑c={i,ik}∥Ptc−Olc∥2)(11)\phi_{m}(i, j, k)=\exp \left(-\frac{w_{1}}{3} \sum_{c=\{i, i k\}}\left\|P_{t_{c}}-O_{l_{c}}\right\|_{2}\right) \tag{11}ϕm(i,j,k)=exp⎝⎛−3w1c={i,ik}∑∥Ptc−Olc∥2⎠⎞(11)
w1w_1w1是一个权重参数；tct_ctc是一在连接ccc的情况下，追踪轨迹的索引；lcl_clc是在ccc的连接情况下，目标检测观察值的索引。
C． 空间潜力
对于某些情况，简单的运动模型进行线性预测就过于简单，例如摄像机的运动。在这些情况下，节点(轨迹或观测)的相对结构信息可以被利用，因为它是仿射不变势。为了对这种仿射不变性进行建模，在HHH中定义了连接元组的空间势：
ϕs(i,j,k)=exp(−w2∑c1,c2∥d(Ptc1,Ptc2)−d(Olc1,Olc2)∥)(12)\phi_{s}(i, j, k)=\exp \left(-w_{2} \sum_{c_{1}, c_{2}}\left\|d\left(P_{t_{c 1}}, P_{t_{c 2}}\right)-d\left(O_{l_{c 1}}, O_{l_{c 2}}\right)\right\|\right) \tag{12} ϕs(i,j,k)=exp(−w2c1,c2∑∥d(Ptc1,Ptc2)−d(Olc1,Olc2)∥)(12)
w2w_2w2是一个权重参数，c1，c2∈{i,j,k}c1，c2∈\{i,j,k\}c1，c2∈{i,j,k}。注意，这里使用节点距离的绝对差而不是相对比，因为距离越大，改变相对位置的可能性就越小。
除了MOT16-13 and MOT16-14使用w1=0.4,w2=1.1,η=0.5w_1 = 0.4, w_2 = 1.1, η = 0.5w1=0.4,w2=1.1,η=0.5，其他数据集使用w1=0.7,w2=0.3w_1 = 0.7, w_2 = 0.3w1=0.7,w2=0.3
四、 实验
追踪MOT16挑战的结果，将其与其他私有检测器的公开方法进行比较。
消融mask实验：
不同阶张量的对比
五、 总结
本文提出了一种多目标跟踪器，它将分配任务描述为一个具有有效解的高阶图匹配问题。该公式可以方便地嵌入运动一致性和空间结构不变性等高阶信息。另外，加入孪生网络，提取基于id mask的特征来表示外貌相似度，并且实验证明使用mask比全局的效果要好。算法的公式实现简洁并且实时运行。
只是公式中直接使用线性运动来预测运动模型，不适用所有场景，因此有待改善。
一个基于高阶图匹配的多目标跟踪器：Online Multi-Target Tracking with Tensor-Based High-Order Graph Matching
