高阶MOT可扩展：一种有效的提升不相交路径近似求解器

6330使高阶MOT可扩展：一种有效的提升不相交路径近似求解器Andrea Hornakova* 1Timo Kaiser* 2Paul Swoboda1Michal Rolinek3Bodo Rosenhahn2Roberto Henschel2*作者贡献相等，1Max Planck Institute for Informatics，Saarland Informatics Campus，2Institute for Information Processing，LeibnizUni versityHannover，3MaxPlanckInstituteforIntelligentSystems，Tübingen摘要我们提出了一个有效的近似消息传递求解器解除不相交路径问题（LDP），一个自然的，但NP-难模型的多目标跟踪（MOT）。我们的跟踪器可以扩展到来自长而拥挤的MOT序列的非常大的实例。我们的近似求解器使我们能够处理MOT 15/16/17基准测试，而不牺牲解决方案的质量，并允许解决MOT 20，这是遥不可及的LDP求解器到现在为止，由于其规模和复杂性。在所有这四个标准的MOT基准测试，我们实现的性能相当或更好，比目前国家的最先进的方法，包括跟踪器的基础上，最佳的LDP求解器。1. 介绍从视频中获得高级理解是计算机视觉中已经研究了很长时间的期望任务。然而，解决这个问题还有很长的路要走。一个计算机视觉系统，能够提取出现在视频中的对象的运动轨迹被认为是一个先决条件的目标。这种被称为多目标跟踪（MOT）的任务具有许多应用，例如，在视频监控[18]，体育分析[2，42]，城市规划[3]或自动驾驶[39，19]领域。然而，解决MOT是具有挑战性的，特别是对于长且拥挤的序列。MOT的主要方法是检测跟踪范式，它将问题分为两个子任务。首先，通过对象检测器在所有视频帧中检测对象然后，跨帧链接检测虽然对象检测器的性能通过CNN的最新进展得到了显著改善[47，63，46，17]，但称为数据关联的后一项任务仍然具有挑战性。数据关联根据成对成本进行推理，成对成本指示每对检测属于同一对象的可能性。外观和时空信息往往是模糊，特别是在拥挤的场景中，因此成对成本可能会产生误导。此外，对象检测器在拥挤的场景中由于部分遮挡而产生更多的错误。为了解决这些问题，数据关联结合全球背景是至关重要的。不相交路径问题（DP）[65，35]是MOT的自然模型。使用最小成本流算法有效地计算结果，该算法可提供全局最优解。不幸的是，长程时间相互作用的积分是有限的，因为DP服从一阶马尔可夫链假设：对于每个轨迹，仅在直接链接的检测之间确保一致性，这是忽略多个链接的检测之间的更高阶一致性的强简化。为了解决这一缺陷，[28]通过在提升边缘方面使用额外的连接性先验，将DP推广到提升的不相交路径（LDP）。这使得公式更有表现力，同时它保持了DP的可行性集（Sec. （3）第三章。优化问题使得能够考虑属于一个轨迹的任意检测之间的成对成本因此，它能够有效地结合长距离时间相互作用，并导致召回率和准确率的显著改善[28]。类似的扩展已经为multicut问题[56，57]。虽然LDP的全球背景的整合是至关重要的，以获得高质量的跟踪结果，它使得数据关联问题NP-难。 [28]介绍 一个全球最佳的LDP求解器可用于半拥挤的序列与合理的计算工作。然而，当应用于较长和拥挤的序列时，由于太高的损耗，这样的方法不再是易于处理的对运行时和内存的要求。为了缩小这一差距，我们提出了第一个近似的LDP求解器。由此产生的跟踪器规模大的问题实例，并结合了全球范围内的相似，ilar的准确性作为全球最佳的LDP求解器。此外，我们的求解器输出原始/双重差距方面的证书。特别是，我们的求解器是基于拉格朗日（对偶）分解的问题。这个对偶是迭代最优的6331通过双块坐标上升（也称为消息传递）使用来自[54]的技术，参见第二节。4.1. decom-位置依赖于子问题，在一个切割平面的方式添加。我们获得高质量的原始解决方案，通过解决最小成本流问题的边缘成本synn- thesizing信息从基地和解除边缘的双重任务，并通过本地搜索过程中改善他们我们在四个标准MOT基准测试中验证了求解器的质量（第（五）。我们实现了与w.r.t.相当或更好的性能当前最先进的跟踪器，包括基于MOT 15/16/17 [37，45]上的最佳LDP求解器[28]的跟踪器此外，我们提出的跟踪器在由长且拥挤的序列组成的更具挑战性的MOT20数据集[16]上的表现与最先进的技术相当。因此，轻量级功能和快速求解器对于在如此大规模的序列上执行跟踪至关重要。因此，我们的工作扩展了在更广泛的情况下成功地制定LDP。本工作的贡献总结如下：• 我们通过引入比全局最优LDP求解器具有更好的可扩展性的近似求解器，同时产生类似的跟踪性能，并且独立于Gurobi[22]，使LDP问题更易于访问和应用。• 我们提出了一种MOT系统，该系统通过使用比最先进的跟踪器[28]中使用的计算要求低得多的特征，可扩展到具有挑战性的序列我们的系统以可扩展的方式结合了高阶一致性，即。它使用近似解算器并提供最优的间隙。我们使LDP求解器1和MOT管道2可用。2. 相关工作（提升的）不相交路径。不相交路径问题是多目标跟踪的自然模型，并且可以使用快速组合求解器来解决[35]。它已被用于[6，65]中MOT的数据关联步骤。其扩展已用于融合不同的物体探测器[12]或多相机MOT[27，38]。它的主要缺点是，它不允许整合远程信息，因为它只评估轨迹内的对象检测之间的直接连接。在[28]中引入的提升不相交路径问题通过引入提升边缘来增强DP，提升边缘使得能够奖励或惩罚对象检测之间的任意连接。这种远程信息的结合导致跟踪性能的显著改善，在主要MOT基准上产生最先进的作者使用Gurobi [22]提供了一个全局最优解算器。尽管有很多有效的子程序，一般的时间com-1https://github.com/LPMP/LPMP2https://github.com/TimoK93/ApLift所提供的求解器的复杂性保持指数级。因此，为了将基于LDP 的方法扩展到高密度的MOT问题，如在MOT20中，降低所使用的LDP求解器的复杂性是至关重要的，因为检测之间的可行连接的数量多重切割和提升多重切割。LDP类似于（提升的）多切[14，29]。在[26，33，36，51，55，56]中，多切已用于MOT，在[5，57]中，多切被这些跟踪器通过启发式近似地解决了潜在的组合问题，而不提供对最优性的差距的估计。我们的方法，提供了一个近似的解决方案，连同一个下限，使评估的解决方案的质量。此外，LDP提供了比提升的多切割严格更好的松弛[28]。MOT的其他数据关联模型。一些作品采用贪婪启发式来获得跟踪结果[9，68，7]。这样的策略通常遭受遮挡或模糊情况，导致轨迹误差。其他人使用二分匹配[31，52，69，62，61，60]来分配新的检测与已经计算的轨迹，最佳的过去。由于没有纳入全球背景，如果单个边缘成本具有误导性，则它们容易出错。高阶MOT框架确保轨迹的所有检测内的这可以通过经由广义最小团问题[64]一次计算一个轨迹来贪婪地完成，或者全局地使用最大多团问题[15]的扩展。一些作品采用连续域松弛。当MOT被公式化为二元二次规划[23，25，58，24]时，已经使用了适用于非凸情况的Frank-Wolfe算法的修改[23]。二进制线性规划的一些近似使用LP-松弛，在连续域中优化，并从连续域中导出二进制解[32，12，11]。然而，他们不提供的最优差距，与我们的工作。高阶MOT可以被认为是使用图卷积的分类问题[10]。它允许直接在跟踪任务上训练特征。多重图匹配问题是图匹配问题的推广，已用于MOT[30]。这里，多图匹配的循环一致性约束确保轨迹的高阶一致性用于MOT中的高阶匹配的消息传递已经在[4]中使用，采用MPLP [20]的变体。与我们的公式相反，[4]不对遮挡进行建模，并且不允许连接先验。多目标跟踪的概率方法包括多假设跟踪[34，13]，联合概率数据关联[48，53]和其他[53，44]。3. 问题公式化在[28]中引入的提升不相交路径问题（LDP）是用于找到一组不相交路径的优化问题。6332∈联系我们X {}∈⟨⟩--联系我们∈∈R∈ R ∈联系我们Σ∈ X∈∀∈ X ∈ S ∈ X∈ X∈ X ∈ XΣ⟨⟩∈X（v1v2，. . .，vl−1v l）：我一期+1∈R有向无环图中的顶点不相交路径。每个路径的成本由该路径中的边的成本确定，如在基本不相交路径问题（DP）中，但是另外存在由提升边定义的更高阶成本如果提升边的端点是同一路径的一部分，则提升边会增加成本。这个问题是多对象跟踪（MOT）的自然公式，其中提升的边缘允许在长距离上重新识别相同的对象。虽然具有更大的表达性，但LDP是NP-难的[28]，而DP可简化为最小成本流。下面，我们概括了LDP的公式[28]。3.1. 符号和定义。流网络：有向非循环图G=（V，E）。起点和终点：节点s，tV。提升图：有向无圈图G′=（V′，E′），其中V′= Vs，t.从v开始到w结束的路径集合是4. LDP的Lagrange分解算法下面，我们概括拉格朗日分解和我们的算法中使用的消息传递原语（Sec.4.1）。然后，我们提出将LDP问题（3）分解为较小但易于处理的子问题（第二节）。4.2-4.4 ）。该分解是（3）的LP松弛的双重任务。因此，它提供了一个由消息传递迭代增加的下限。我们在[54]中开发的拉格朗日分解框架的简化版本中解决问题（3我们的启发式获得原始解决方案使用的对偶成本的子问题（节。4.6）。4.1. 拉格朗日分解我们有一个优化问题minx∈Xc，x其中0，1n是可行集，cRn是目标向量.它的Lagrange分解由一组子问题S给出，子问题S具有相关的可行集Xs{0，1}ds.vv∈ E，Σ对于每个s∈ S。 Xs的每个坐标i对应于.X的一个坐标通过注入π：[d]-[n]al-v1=v，v1=wS由矩阵SSds，n其中（一）A∈ {0，1}对于vw-路P，它的边集是PE，它的节点集是PV.可达关系（As）ij= 1πs（i）=j. 对于每对子问题s，s′∈ S，其中包含一对坐标i，j，使得对于两个节点v，定义w∈Vs s′作为vwGvw-路径（G）。我们假设它是自反的，并且suG，utG u V，即可以从S到达所有节点，并且所有节点可以到达汇聚节点T。流量变量：如果流量通过相应的边缘，则变量y〇，1E具有值1节点变量z〇，IV表示通过每个节点的流。值0/1强制路径节点不相交。提升边缘E’的变量由y’表示。0，1E′。 yv′w=1表示节点v和w通过G中的流y连接。从形式上讲，πs（i）= πs′（j），我们有一个耦合约束xi= xj，对于每个xss，xs′s′.我们要求每个可行解x对于子问题都是可行的，即x，s：Asx s.我们要求子问题的目标等价于原始目标，即。c，x=s∈S∠θ s，Asx∠X. 这里θsRDS 定义子问题的目标。给定每个s∈ S的成本θs，拉格朗日分解的下界为yv′w = 1P∈vw-路（G）：ij∈PE：yij= 1时。（二）minθs，xs.（四）xs ss∈S提升不相交路径问题。 给定边成本c∈RE，给定耦合约束xs=xs′和γ∈R，则一个se-S流网络G中的节点成本d∈RV和边成本c′∈′′I j形式为θs+=γ，θs′的- =γ是提升图G′的提升不交路问题I j称为重新参数化。是miny∈{0，1}E，y′ ∈{0，1}E′，z∈{0，1}Vc，y，+c′，y′，+d，z，可行原始解在重新参数化下是不变的，但下界（4）不是。对偶下界的最优值等于原问题的凸松弛的最优值，见[21]。S.T.y节点不相交s，t-G中的流，通过G的节点的z流y，y′根据（2）可行（三）最小边际消息传递。下面，我们描述了基于最小边缘在下界中单调非递减的重新参数化更新。给定子问题s∈S的变量xs，相关的最小边际为vw-路径⑹=6333我SsSs集合E’可以是任意的。 创造一个提升的边vw仅当vw∈ R由于公式（2），且仅当ms=min我我∠θ，x∠−min我θ，x（5）Gv和w不属于相邻帧。 我们描述xs∈Xs：xs=1xs∈Xs：xs=0我们在SEC的选择五点二。其他符号和缩略语见附录8.1。即最优解与所选变量分别设置为10的情况。6334JE∈E∞EvXEVWvuv⟨⟩EE∈∪EEE′EE′（zout，yout，y′out）=0∨5：α=提升成本[w]，下一个[u]=wi i jiE+∈∈ ∈ Rvu命题1（[54]）。 给定耦合约束xs=w同意，即y输出= y输入如果vw∈E且y′out=y′in如果我xs′和ω∈[0，1]，则下列运算是非减的vw∈E′。大众汽车大众汽车w.r.t. 对偶下界（4）θs−=ω·ms，θs′+=ω·ms。（六）重新参数化的目标是双重的。(i)改进目标下限，以了解我们的解决方案离最优解有多远。(ii)使用重新参数化的成本作为我们的原始启发式的输入，产生高质量的原始解决方案。 关键部分是有效计算(i) 用于获得下界的子问题的最优解（4），(ii) 用于获得最小边际的约束最优值（5）和（iii）使用重新参数化成本的原始启发式（Sec. 4.6）。拉格朗日分解已被用于其他问题，但子问题的分解和最小化，灰程序是特定的问题因此，为LDP开发它们是以可扩展的方式解决LDP的重要贡献，同时保持小的差距达到最佳。4.2. 流入和流出子问题对于流图的每个节点V V，我们引入两个子问题：流入和流出子问题。子问题包含所有传入的响应。节点V的输出边与对应节点一起最主要的是，流入和流出。 流出子问题分别包含边δ−（v）∪δ−′（v）和δ+（w）∪δ+（w）。在这里，我们领养流入和流出子问题的优化。给定成本θ out，节点v的流出问题的最优解可以通过在由从v可到达的顶点定义的子图上进行深度优先搜索来计算。算法依赖于以下数据结构：• 提升成本[u]包含所有ut-路径w.r.t.到连接v与路径顶点的所有提升边的成本。• 下一个[u]包含的最好邻居的顶点uw.r.t. 值 提升成本。也就是说，next[u]=argminw：uw∈δ+（u）提升成本[w]算法1选择退出成本输入起始顶点v，边成本θ~输出最优值opt，提升成本w：vw δ+（v）主动αvw最优解1：foru V：vuGdo2：提升成本[u]=，下一个[u]=第三章： 端4：提升成本[t] = 0，下一个[t] =t5：提升成本DFS输出（v，v，0〜，提升成本，下一个）6：w：vw∈δ（v）：αvw=θ~v+θ~vw+liftedcost[w]7：opt = min（minvw∈δ+（v）αvw，0）标准符号，其中δ−（v），分别δ+（v）表示所有E引入vEv. 似-算法2提升成本DFS输出，分别 传出自其中δ−′（v），δ+（v）分别表示进入到的提升边.输入v，u，θ~，提升成本，下一个从...出去节点流出子问题的可行解V定义为产量提升成本，下一个一曰： α=0第二章： 对于uw∈δ+（u）dooutv出来δ+（v）’outδ+（v）3：如果next[w]=0，则 Lifted-Cost-DFS-Out（v，w，θ~）zv∈ {0，1}，y∈ {0，1}E ，y∈ {0，1}E′：4：如果提升成本[w]<α，则P∈ vt-路（G）s.t.zv= 1yout=1vw∈PEy′out=1u∈PV（七）6：如果结束第七章： 端8：如果next[u]=，则 next[u]=t因此，要么没有流通过顶点v并且所有的基边和提升边具有标签零。或者，在G中存在一个被标记为1的Vt-路径P。在这种情况下，与对应于P中的第一边的v相邻的基边是1。 所有连接v与P的顶点的提升边也具有值1。所有其他基准边和提升边均为零。流出子问题的每个可行解可以由路径Vt-路径P表示。 流入子问题X的可行集类似地定义。我们9：提升的cost[u]=α+θ~′Alg. 图1和图2给出了一般的部门优先搜索（DFS）过程，其在给定顶点v的情况下，计算从v可到达的所有顶点的最优路径。Alg. 1取输入顶点v和边成本θ~θ。其子程序Alg.2递归地计算从v可到达的每个顶点u的值lifted cost[u]。的总体最优成本min（z，y，y’）∈Xoutθ〜，（z，y，y’）子问题是由最小的节点和基地v~out关于out有时为了更好的可读性而省略superscipts。流入和流出子问题之间的约束对于节点变量，我们添加约束zin=zout。为边和提升边的代价为minvu∈δ+（v）θv+θvu+提升成本[u]。我们实现线性复杂度，利用最小成本路径的子路径是最小的。V V一个边vw E E′，我们需要在v的流出子问题和流入子问题中流入子问题的优化是类似的。输入和输出子问题的消息传递。 我们出来.6335O||||ij∈C∈{∈|关于我们Cθ,otherwiseΣUVΣUVIJXIJ∞∈×UVUVUV如果（1−yij）+ij∈Cψijzi*j（1−yij）≥1−ykl，5：如果θ′C≥0，则返回opt4：opt=可以通过调整Alg来计算一个最小边际（5）1，并强制取边或不取边。然而，在执行操作（6）的情况下逐个计算最小边际将是低效的，因为它将涉及调用Alg。一个子问题，我们在优化过程中只添加那些改善放松。详情见附录8.4。4.4.切割子问题正+ +（δ E（v）+δ E′（v））次。因此，我们在附录8.2中提出了计算最小边值序列的有效算法。该程序通过选择用于计算最小边限的边的顺序来节省计算，并且重新使用先前的计算。4.3.路径子问题该子问题包含一个解除边缘vw和路径P从v到w的基础和解除边缘组成。它们反映了（i）如果在v和w之间存在活动路径，则提升边vw必须被标记为1，并且（ii）不能存在有效路径。是路径P内的恰好一个无效提升边缘，如果vw是切割子问题的目的是反映如果存在将u和v（uv-切割）分开的所有标记为0的基边的切割，则提升边uv必须标记为0。可 行 集 。割 子 问 题 由 提 升 边 uv 和 uv- 割C={ij∈E|i∈A，j∈B}其中A，B V且A ∩ B =. 可行解空间XC定义为yu′v∈{0，1}，y∈{0，1}C： yu′v≤Σyij，i∈A：Σyij≤1，ij∈Cij∈C活跃原因是不活动的提升边缘将P分成必须断开的两个段。这与激活提升边缘vw是矛盾的，因为它指示v和w之间的连接。路径子问题类似于多割的循环不等式[14]。为了区分底部边缘和提升边缘uv∈C⇒yu′v≥yuv。（十）约束规定：（i）如果切割中的所有边都是0，则提升边uv是0，（ii）存在至多一个有效的外出响应。A中每个顶点的传入边B和（iii）如果还存在基边uv C，则每当它是活动的时，提升边uv必须是活动的。路径P，我们使用符号PE=P∩E和PE′ =P∩ E′。为了定义路子问题的可行解，我们定义了强基边E0=vwE vw-路径⑹=大众也就是说，基边vw是强的当且仅当图G中除了vw本身不存在其他的vw-路。vw -路的路子问题的可行集X_P算法3切割-子问题-优化输入边成本θC输出子问题的最优值1：定义eψ∈RA×B：C′C′CP被定义为y∈{0，1}PE，y′{0，1}E′∪{vw}：2：ψij=θuv+θuv，ij=uv∧uv∈C∧θuv>0∞，如果ij∈/CIJkl∈PE′∪ {vw}：（8）3：z*∈ argminΣ Σψ ij z ij，s.t. z1≤1，z1≤1Σ Σ′ ′z∈{0，1}A×Bi∈A j∈Bkl∈PE∩E0：（9）第六章： 如果kl∈C：zkl= 1则ij∈ΣPE\kl （1−yij）+ij∈PE′∪{vw}（1−yij）≥1−ykl。7：返回opt +θ′C8：其他9：α= minij∈CθC等式（8）要求PE’或vw中的提升边缘可以10：如果|θ′C|>α则返回θ′C+ α只有当子问题的至少一个其他边为零时，它才为零。等式（9）对于强基边缘强制相同。路径子问题的优化在Alg. 12在附录中原则如下。它检查是否恰好存在一个正边缘，以及它是否是提升的或强的基本边缘。 如果是，则最优解是（i）除了两个最大的边缘之外的所有边缘，或者（ii）所有边缘，以给出较小的目标值的那个为准。如果上述条件不成立，则可以选择包含所有负边缘的我们使用的路径优化算法的变化与固定为0或1的边缘计算最小边际。切割平面。 由于存在指数级多条路径uv机十一：else返回选项十二： end if关于可行集C的割子问题的优化由Alg给出。3 .第三章。其关键是解决顶点集A和A之间的线性分配问题（LAP）[1]。B.如果边ij属于C，则（i，j）AB的分配成本ψ ij是切割边成本θ C，否则。在uv-割C包含基边uv且提升边代价θ′C为正的特殊情况下，指派代价ψ uv增加θ′C.切割边缘的候选最优标记由LAP变量的值给出。若θ′C≥0，则最优值Pij∈PEij∈PE′∪{vw}\{kl}6336UVuu∈\{}∈∈O||∈苏在【详细】苏u输出tut由LAP找到的是切割子问题的最优值。如果它是负的，我们区分两种情况：（i）如果存在标记为1的切割边kl，则将提升边成本θ′C添加到LAP 的最优值。（ii）否则─从第一路径的末端或第二路径的开始切断一个节点是否使连接成为如果是，并且连接正在减少目标，则节点被切断并且路径被连接。看是否激活最小成本削减更好边和提升边UV或保持所有边不活动。我们使用Alg的变体。3，其中边缘变量被限制为0或1以用于计算最小边缘。切割平面。有很多次切割的问题-算法4初始化-MCF1： u V s，t：（〇，Ic，αin）=Opt-In-Cost（u，θin）（〇，Ic，αout）=Opt-Out-Cost（u，θout）lems。因此，我们只添加那些提高下限的。详见附录8.5。2：u∈V\{s，t}：θmcf=αin，θmcf3：u∈ {uv ∈ E|us，vt}：θmcf=α输出=α输出+α输入4.5. 消息传递用于优化拉格朗日分解的总体算法是Alg。19在附录中一是流入和5. 实验u输出v输入uv uv对每个节点初始化流出子问题。然后，对于多次迭代或直到收敛，每个子问题的成本通过计算最小边际和调整reparametrization proportionally到最小边际的值来迭代地调整。此外，每第k次迭代额外的路径和削减子问题被分离，并添加到拉格朗日分解。求解器复杂性。 我们需要（Einp）空间，其中Einp是图稀疏化之前的所有边。最耗时的是计算每个进出子问题的提升边最小边缘。Alg. 6为一个流出子问题计算它们，并且它在每帧的检测数量上是线性的。这显著提高了最优LDP求解器LifT的复杂性，使得LDP适用于大型问题实例。详见附录8.14。4.6. 原始舍入为了计算原始解，我们解决了最小成本流（MCF）的基础边缘的问题，并改善了这个初始解的局部搜索启发式。在没有提升边的情况下，不相交路径问题是MCF的一个实例，其可以通过组合求解器（如我们采用的连续最短路径求解器[1]）来有效地优化。我们通过在MCF图G mcf =（V mcf，E mcf）中将每个节点uV分裂成两个节点u in，u outVmcf，向E mcf添加附加边u in u out，并在所有边E mcf上设置容量[0，1]来强制节点不相交路径。除了s和t之外的每个节点具有需求0。Alg. 4使用Alg从输入/输出子问题计算MCF边缘成本。1.一、 我们从V的流入子问题和U的流出子问题中获得每个流边缘U的成本，使用它们的最小值，其中边缘UV是主动的。这很好地结合了来自基部和提升边缘的成本我们描述了局部搜索启发式算法，以提高算法的MCF解决方案。25在附录中它适用于不相交路径的首先，如果路径被分割导致目标减少，则路径被分割。第二，探讨合并 如果两个路径的合并是不可能的，我们迭代地检查我 们 将 我 们 的 LDP 求 解 器 集 成 到 MOT 系 统 中（Appendix，Fig.1）并在具有挑战性的数据集上显示高阶MOT可扩展到大问题实例。在接下来的部分中，我们描述了我们的实验装置和目前的结果。我们澄清的基础和提升图和他们的稀疏化的边缘成本计算和建设。5.1. 成对成本我们使用多层感知器（MLP）来预测两个检测属于同一轨迹的相似性我们将最大帧距离分成20个相等长度的间隔，并为每组帧距离训练一个单独的MLP我们将MLP输出转换为检测之间的边缘的成本，并将其用于我们的目标（3）。负成本指示两个检测属于同一轨迹。正成本反映了相反的情况。MLP架构。每个MLP由具有与输入大小相同数量的神经元的完全连接层组成，随后是LeakyReLU激活[43]和完全连接的单神经元输出层。我们在训练中添加了S形激活。我们在下面的段落中描述了用作输入的空间和视觉特征。空间特征使用两个检测v和w的边界框信息。我们把这些盒子对齐，使它们的中心重叠。相似性特征σvw ，Spa[0，1]是两个对齐的盒子之间的交集。外观特征。我们通过在来自[66，59，50]的相应基准和附加数据的训练集上训练方法[67]来为每个检测v创建外观特征Fv使用由σvw，App：= max 0，Fv，Fw给出的检测v和w之间的相似性特征σ vw，App值越高表示相似性越高。全局上下文规范化。这两个特征σvw、Spa、σvw、App完全取决于节点v和w。为了包括全局上下文，我们将两个特征的几个归一化版本附加到边缘特征向量，受[28]的启发边ij的两个特征σij，*经历五向正规化。在每一种情况下，来自相对的最大特征值是相对的6337·}|∈联系我们联系 我们|{∈|- -|边缘的evant集合被选择为归一化值。归一化通过将两个特征σij，*除以它们的五个归一化值中的每一个来完成这产生10个值。通过下式获得边缘ij为了避免边缘成本的重复计数，我们随后将非连续帧之间的所有基本边缘的成本设置为零，使得仅提升的边缘保持成本。如果提升的边的成本约为零，则它不是有区别的，并且我们除σ2ij，* 通过五个归一化值中的每一个。-移除它，除非它与（零值）底边重叠连同两个未归一化特征σij，*，边缘特征向量具有长度22。详见附录8.9。训练 我们在包含采样边缘的批次B上迭代地训练我们的MLP。 为了补偿真正边缘和真负边缘之间的不平衡，我们使用α平衡的焦点损失[40]，其中γ= 1。我们定义α-权重α（g，Δf），以对边缘vw的正确分类进行加权，其中地面真值流值g vw0，1、帧f v中的v与帧f w中的w之间的时间距离Δf以及值g0，1via α（g，∆f）：= 1/vwE：f vfw=∆f，g vw=g . 我们使用Adam优化分类器，其中Ir= 0。1，β1= 0。9，β2= 0。999和ε= 10−8。为了降低复杂性，同时保持品种在训练过程中，ING，我们引入了一个扩展的采样。 给定帧f，我们通过从帧f开始的固定帧移位序列中采样检测来创 建 批 次B（f），确保所有时间距离Δf都存在于B（f）中（详见附录8.11）。然后，我们将k个最近的检测子采样到k= 160的随机生成的图像位置，这使训练对拥挤的场景敏感。我们用数据集的所有帧f的批次B（f）训练3个时期的MLP。5.2. 图构建我们创建的基础和解除图形边缘之间的检测与时间距离高达2秒。我们还将来自源s的边缘添加到每个检测，并将t添加到每个检测。为了降低计算复杂度，我们在基础图和提升图两者上应用稀疏化，如稍后描述的。成本 我们从相同的MLP分类器获得基础成本和提升成本c和c’（第二节）。5.1）。 由于分类精度随着帧距离Δf的增加而降低，我们将成本乘以衰减权重ωΔf：=（10Δf +0. 1）-1，使得表示长时间距离的边具有较低的权重。从s到t的边的成本为零。最后，我们使用简单的启发式算法来找到明显匹配或不匹配的对。我们将相应的成本设置为绝对值高，匹配为负，不匹配为正，从而引入软约束。一个明显的匹配是由一个几乎最大的特征相似性。如果检测对的边界框之间的位移太高，则检测对显然是不匹配的详见附录8.12。稀疏化 基准边是两个边集的交集。第一个集合包含每个v V’的边缘，从每个后续时间帧到它的3个最近（最低成本）邻居。 第二组为每个顶点选择最好的边缘，其前面的帧类似。此外，长于6帧的边必须具有低于3的成本。0的情况。到5.3. 推理为了与现有技术进行公平比较，我们使用跟踪器[7]过滤和细化检测，如[28]中所示与[28]不同，我们在运行求解器之前应用tracktor来恢复丢失的检测。当我们在全局图上求解MOT 15/16/17时，我们在时间间隔内求解MOT 20，以减少内存消耗和运行时间。首先，我们解决了非重叠的相邻区间的问题，并固定在区间中心的轨迹。其次，我们解决了一组新的间隔，其中每个人都涵盖了未分配的检测在两个初始相邻的间隔，并使连接到固定的轨迹片段的问题。我们使用MOT20中50帧的最大边缘长度。因此，150是最小间隔长度，使得当将检测分配给轨迹时使用来自检测的这样，求解器就有足够的上下文来做出每个决策。超过200帧的间隔显著增加了MOT20的复杂度，因此我们在实验中使用间隔长度150。后期处理。我们使用简单的启发式检查，如果在长时间的差距基础边缘对应于合理的运动，并分裂轨迹，如果必要的。最后，我们使用线性插值恢复丢失的检测轨迹内附录8.13包含有关推断的更多详细信息。5.4. 跟踪评价我们评估我们的方法在四个标准的MOT基准。MOT15/16/17基准测试[37，45]包含从静态或静态拍摄的半拥挤视频序列。移动的照相机。MOT20 [16]包括具有相当高的帧数和每帧检测的拥挤场景，参见表1。1.一、挑战不仅仅来自数据大小。由于频繁的遮挡，检测器在拥挤的场景中产生更多的错误，并且随着人们到摄像机的距离高，外观特征的区分性较低在这种情况下，使用高阶信息会有所帮助。然而，我们的图中的边缘的数量与每帧的检测数量成二次方增长。因此，使跟踪器可扩展到这些海量数据至关重要。 我们使用以下成分来解决问题：（i）用于获得边缘成本的快速但准确的方法，（ii）快速提供高质量结果的近似LDP求解器，（iii）预处理启发式，（iv）为每个决策保持足够上下文的区间解。我们使用相应数据集的训练数据进行训练，并使用公共检测进行训练和测试。6338↑↓MOT17 MOT20表1. ApLift与最佳性能求解器w.r.t. MOT挑战的MOTA指标越高越好，越低越好。最右边的两列：每个序列的平均帧数和数据集的每个帧的平均检测数方法MOTA ↑IDF1 ↑MT ↑ML ↓FP ↓FN ↓IDS ↓Frag↓ApLift（我们的）58. 九点五十六5513 264177391927362241 2112[10]第五十七章.6591474 279 16953 2013841210 1420[7]第52话.6527 365 3316930236680 1648 4374[68]第六十八章：一个女人5596 621 75214076200672 2583 496560.第60章大结局565电话：+86-510-6666666传真：+86-510 -6666666[28]第六十八章.5656637 791 14966 206619 1189 3476[10]第五十八章. 861。7 679 788 17416 2135941185 226561.第61章大结局七六六。1 260 237916860180495 802[28]第61话.364电话：+86-510 - 8888888传真：+86-510- 8888888[10]第五十八章.6617 207 258 4949 70252 354 684[41]57.055电话：0167 262433273573 475 859[28]第52话. 五块六电话：0244 186 6837 21610 730 1047[10]第51话.5586 225 187 7260 21780375 87251.第51章大结局159电话：0284 1631007019288677 1022[7]第四十四章. 一百四十六电话：+86-130 - 1896477传真：+86-130 - 1896477表2.提升图稀疏化、消息传递和使用零基代价对不经后处理的MOT17列车的影响。E′MP步骤基本费用IDF1↑ MOTA↑FP↓FN↓IDS↓密集82零七十一066岁。328261092631369密集0-70366岁。328321092651354密集82原稿69岁。866岁。328241092661355稀疏82原稿69岁。166岁。32825109263 1316表3. LDP解算器的运行时和IDF 1比较：ApLift（我们的），具有6、11、31和51次迭代，以及来自MOT 20的序列MOT 20-01的前n帧上的LifT[28]（两步程序）。n测量 LifTOur6Our11Our31Our5150IDF1 ↑80。6我们比较我们的方法使用标准的MOT指标。MOTA[8]和IDF1 [49]被认为是最具代表性的，因为它们结合了其他指标（特别是召回率和精度）。IDF1更容易受到不一致射束的惩罚。我们还报告了大部分跟踪（MT）和大部分丢失的轨迹（ML）、假阴性（FN）和假阳性（FP）、ID开关（IDS）和碎片化（Frag），如由基准的评估协议[8]所提供的选项卡. 1示出了与最佳（w.r.t. MOTA）在测试集上的同行评审方法我们的近似求解器在MOT 15/16/17上实现了与最佳LDP求解器[28]几乎相同的结果，同时使用更简单的功能。总的来说，我们的方法在所有评估的基准测试中与最先进的方法相当我们的完整结果和视频是公开的3.所提出的方法实现了总体低FN值，但是3https：//motchallenge.net/method/MOT=4031 chl=13MOT16MOT15帧密度1119.8170.9845.631.8845.630.8525.710.883岁383岁381. 581.5时间[s] 272241635100IDF1 ↑80。482岁582岁581. 681.6时间[s]484142497218150IDF1 ↑78。181.081.079岁。879岁。86339FP值略高。FP/FN主要受输入检测的预处理和后处理中的插值的后处理（轨迹分割和插值）对MOT20的影响（导致FP，但减少FN和IDS）在附录（表1）中进行了分析4）.选项卡. 图2显示了各种设置对MOT17列车性能的影响虽然我们通常将基边成本设置为零（秒5.2），我们需要在使用稀疏提升图时保留它们。消息传递和 密 集 提 升 边 缘 都 改 善 了 IDF1 和 IDS 。 然 而 ，MOTA、FN和FP几乎保持不变。最后，我们将求解器的运行时间与中的样本序列的两步LifT版本进行比较。选项卡. 3 .第三章。随着问题复杂性的增加，我们的求解器执行LifT w.r.t.运行时，同时实现类似的IDF1。与直觉相反，当我们朝着越来越好的优化目标值前进时，由于不完美的边缘成本，跟踪度量可能会略微降低。我们将我们的求解器与附录8.14中MOT17列车上的最佳（一步）LifT进行了比较。6. 结论我们证明了NP-hard LDP模型适用于处理MOT 20的大规模序列。近似LDP求解器、有效可计算的成本和为每个决策保持足够上下文的数据细分的组合使得这成为可能。7. 确认这 项 工 作 得 到 了 德 国 联 邦 教 育 和 研 究 部（BMBF）的支持，在LeibnizKILabor项目下（批准号：01DD20003）、数字创新中心（ZDIN）和德国研究共同体（DFG）在卓越集群PhoenixD（EXC2122）内的德国卓越战略下。6340引用[1] Ravindra K Ahuja ，Thomas L Magnanti，and James BOrlin.网络流量。马萨诸塞州剑桥市Alfre