基于嵌套Benders分解的动态规划加速及其在多人姿态估计中的应用

基于嵌套Benders分解的动态规划加速算法及其在多人姿态估计中的应用Shaofei Wang1，Alexander Ihler2，Konrad Kording3，and Julian Yarkony41百度公司2加州大学欧文分校3宾夕法尼亚大学4益博睿数据实验室抽象。我们提出了一种新的方法来解决动态规划（DP），这是经常在计算机视觉，树结构图与指数节点状态空间。典型的DP方法必须枚举树的每个边缘上的两个相邻节点的联合状态空间以计算最优消息。在这里，我们提出了一个算法的基础上嵌套弯曲分解（NBD），迭代下界的消息在每一个边缘，并承诺是更有效的。我们应用我们的NBD算法以及一种新的最小权重集包装（MWSP）制定的多人姿态估计问题。虽然我们的算法是可证明的最佳终止时，它在线性时间实际DP问题，获得高达500倍的速度比传统的DP算法，具有多项式的复杂性。关键词：嵌套Benders分解，列生成，多人位姿估计1介绍许多视觉任务涉及在大的组合空间上进行优化，例如由生成大量竞争假设的低级检测器引起，这些竞争假设具体示例是多人姿态估计（MPPE），其是可以馈送到许多下游基于视觉的应用（诸如运动科学、安全和康复）中的基础图像处理任务。MPPE可以通过使用例如以下各项来生成身体部位的候选检测而以自底向上的方式接近：卷积神经网络（CNN），并随后将它们分组为人。然而，随后的优化问题对于非专业方法来说可能难以相对简单的（树结构或近似树结构）基于零件的模型可以使用动态规划（DP）来求解工作在加入百度之前是以独立研究员的身份完成的2S. Wang，中国山核桃A. Ihler，K. J.Yarkony目标检测[6]、姿态估计[17]和跟踪[14]任务。然而，典型的动态规划在变量呈现的状态数方面是二次的;当这是大的，它可以很快变得棘手。在某些特殊情况下，例如基于欧几里得距离的成本，可以使用像广义距离变换[7]这样的技巧来更有效地计算解决方案，例如在可变形零件模型[6，17]中，但不适用于更一般的成本函数。在本文中，我们研究了一个模型MPPE，制定为一个最小权重集包装问题，其中每一组对应于一个单独的per-son在图像中，并包括与该人相关的所有检测的集合（这可能包括多个检测的同一部分，由于噪声在低级别的检测器）。我们使用隐式列生成作为整数线性规划来解决集合包装问题，其中每列对应于潜在地与单个人相关联的姿势或部分检测的集合不幸的是，虽然这意味着成本函数的结构仍然是树状的，类似于单姿态部分模型[6，17]，但该模型中变量所采用的状态数量可以与图像中的任何数量的检测相关联，这意味着变量取该部分的所有检测的幂集中的值。这个属性使得树上的标准动态程序难以处理。为了解决这个问题，我们应用嵌套Benders分解（NBD）[13，5]方法，其迭代地降低节点之间的期望动态编程消息的界限。该过程以每个节点的最佳状态的确切消息终止，同时通常比两个幂集的所有组合上的直接枚举效率高得多。我们证明了我们的方法在MPII-多人验证集[2]上的有效性。 与现有的原始启发式求解器（例如[10]）对于MPPE模型，当LP松弛是紧的时，我们的公式可证明是最优的，在我们的实验中超过99%的情况下都是如此。我们的论文结构如下。我们在第2节中回顾了相关的DP算法和MPPE系统。在第3节中，我们将MPPE表示为最小权重集包装问题，我们通过隐式列生成（ICG）以动态规划作为定价方法来解决在第4节中，我们展示了如何ICG的定价步骤可以说是一个动态的程序。在第5节中，我们介绍了我们的NBD消息传递，它取代了DP中的传统消息传递最后，在第6节中，我们在MPII-多人验证集上进行实验，表明我们基于NBD的DP在实际MPPE问题上实现了高达500倍的动态编程速度，同时实现了与基于原始启发式方法的最先进求解器相当的2相关工作在本节中，我们描述了与我们的方法相关的一些相关的现有方法和工作应用具体而言，我们将讨论快速前-通过NBD加速DP并应用于MPPE3动态规划方法和基于组合优化的MPPE模型。2.1快速动态规划动态规划（DP）的时间复杂度随树中变量的数量线性增长对于二次增长是关键瓶颈的应用程序，应考虑两篇相关论文。在[12]中，树中变量之间的成对项在优化之前是已知的，并且在树中的每条边上都是相同的。因此，它们可以在推理之前预先排序，以便对于变量的每个状态，剩余变量的成对项是有序的。通过利用这些排序列表，可以通过仅处理列表的最低成本部分来计算消息，并且仍然保证最优性。在单独的工作线[4]中，引入了攻击DP的双LP松弛的列生成方法。应用对偶，原始中的成对项变成对偶中的约束。尽管穷尽地找到违反的约束将需要与用更标准的方法求解DP完全相同的时间复杂度类似地，LP不需要显式求解，而是可以作为DP求解。与这些工作相比，我们的DP在其成对相互作用中具有重要的结构，对应于我们利用的高树宽二进制伊辛模型。前面引用的工作并没有考虑到包含这些类型结构的域。2.2组合环境下的多人姿态估计我们的实验工作与[15，8，10]中的子图多割整数线性规划公式密切相关，我们将其简称为MC。MC将MPPE的问题建模为将检测分割成身体部位（或误报）并将这些检测聚类成姿势。聚类过程根据相关聚类[3，19，1]标准进行，成本由与检测相关的部分参数化。该公式是值得注意的，因为它通过允许姿势与给定身体部位的多个检测相关联来执行一种类型的非最大抑制（NMS）然而，MC的优化问题往往是太难精确地解决，因此攻击与启发式方法。此外，MC没有简单的方法来将先验模型并入图像中的姿势的数量。与MC相比，我们的模型允许有效的推理与可证明的guar-antees，同时建模的成本相关联的候选检测与零件的优化之前的先验。优化不需要将每个这样的检测与人相关联，而是可以将其标记为假阳性。在优化之前将检测与部分相关联在实践中是没有问题的，因为深度神经网络几乎总是在给定检测的标签上产生高度4S. Wang，中国山核桃A. Ihler，K. J.YarkonyDS3基于最小权集Packing的在本节中，我们将自底向上的MPPE任务表示为最小权重集打包（MWSP）问题，并使用隐式列生成来解决它。我们使用[8]的身体部位检测器，其在后处理（阈值化、非最大抑制（NMS）等）之后，输出一组具有成本的身体部位检测，我们将其解释为后续成本函数中的项。我们在本文件的正文中使用术语“检测”和“部分检测”。每个检测与恰好一个身体部位相关联。我们用十四个身体部位，包括头部和颈部，以及脚踝、膝盖、臀部、手腕和肩膀的左右变体。我们使用[8]的后处理系统，其输出成对成本，该成对成本鼓励或不鼓励将两个部分检测联合分配给共同姿态。因此，每个姿态由部分检测的选择组成;姿势可以不包含对身体部分的检测（对应于遮挡），或者包含对该部分的多个检测（NMS）。每个姿态与作为其成员的二次函数的成本相关联给定一组姿势及其相关成本，我们将MPPE问题建模为MWSP问题，其选择一组成对不相交（意味着没有两个所选姿势共享共同检测）的最小总成本的姿势。3.1问题公式化检测和部分形式上，我们将部分检测的集合表示为D，并使用d对其进行索引。类似地，我们使用R来表示身体部位的集合，并用r对其进行索引。我们使用Dr来表示部分r的部分检测的集合。我们使用Sr表示部分r的检测的幂集，并对其进行索引链球菌我们利用矩阵RSr∈{0，1}| D| ×| S|其中Sr= 1当且仅当检测d与配置% s。为方便起见，我们明确地定义颈部为零，因此它的幂集为S0.姿势：我们将D上所有可能姿势的集合，即D的幂集，表示为P，并将其索引为p。我们使用矩阵P ∈ { 0，1 }来描述检测到姿态的映射|D| ×|P|，并且当且仅当检测d与姿态p相关联时，设置P_dp = 1。由于P是D的幂集，所以它太大而不能被简单地考虑。因此，我们的算法通过构建子集合P来实现优化的相关位姿（参见第3.2节）。成对不相交约束：我们使用指示符向量γ ∈ {0，1}描述姿势的选择|P|其中，γp= 1表示选择姿态p ∈ P，否则γp= 0。解γ是有效的，当且仅当所选择的姿势是成对不相交的，其中该解满足Pγ≤1。等式的基础值对每个d∈ D，Pγ≤1是p∈PPdpγp≤1。通过NBD加速DP并应用于MPPE5(a) （b）姿态图1：我们的姿势模型的图形表示。(a)我们将图像中的姿势建模为增强树，其中每个红色节点表示身体部位，绿色边缘是传统图像结构的连接，而红色边缘是从颈部到颈部所有非相邻部位的增强连接（b）每个身体部位可以与多个部位检测相关联，红色节点表示身体部位，而青色节点表示该部位的部位检测，蓝色边缘指示将部位检测分配给人的某个部位，而青色边缘指示相同部位的检测之间的成对成本。因此，身体部位的可能状态由该部位的部位检测的功率集组成。成本函数：我们用一元成本θ ∈ R来表示姿态的总成本|D|其中θd是将检测d分配给姿态的成本，并且成对成本|D| ×| D|其中φd1 d2是将检测d1和d2分配给共同姿态的成本。我们使用Ω来表示实例化姿势的成本，这用于规则化图像中的人数姿势的成本被正式定义为：Θp=Ω+ Σd∈DθdPdp+ Σd1∈Dd2∈Dφd1d2Pd1pPd2p（1）通过在成对成本φ中强制一些结构，我们确保该优化问题作为动态规划是可处理的 考虑一个图G =（V，E），其中V=R，i. e. eachnodereprentsabodypart，andd（r，r）∈Eifpairwisetenpartranddpartrenon-zero. 计算机视觉中的一种常见模式是使用树结构模型来表示身体中的部位的位置，例如在[6，17]的可变形部位模型中;这迫使树5中的非相邻部位之间的成对项为零。在我们的应用程序中，我们增加了从颈部到所有其他非相邻身体部位的额外边缘的树模型。这在图1中示出。然后，5WLOG：我们假设φ是上三角形，并且检测按部分排序，其中父部分的编号低于子部分6S. Wang，中国山核桃A. Ihler，K. J.Yarkony0以上在 S0 的 颈 部 配 置 s 的 条 件下 ， 条 件 模 型 是 树 结 构 ， 并 且 可 以在 O（|R|k2）time，其中k是每个部分的最大检测次数。整数线性规划：我们现在将找到最低成本的姿态集合的问题转换为服从成对不相交约束的整数线性规划（ILP）：minγ∈{0，1}| P|ΘΘγ（2）S.T.Pγ≤1通过放松γ上的积分约束，得到了ILP的线性规划松弛，并利用Lagrange乘子集λ ∈ R将其转化为对偶形式|D|：minθγ= max −1λ（3）γ≥0Pγ≤1λ≥0Θ+Pλ≥03.2隐式列生成在本节中，我们将描述如何优化方程的LP松弛。（三）、如前所述，优化Eq. (3)是P的难以处理的大小。因此，我们可以使用一个有效的子集合PP，以避免在求解方程的同时枚举P。(3)没错该算法在运筹学文献中被称为隐式列生成（ICG），并在Alg.1.一、具体地说，我们在寻找具有负降低成本的姿态（行6）和重新优化Eq.（3）（第3行）。通过对每个颈部配置s0∈S0进行条件化，然后在与s0一致的所有姿势中识别出最低的降低成本姿势，我们将其表示为Ps0，来实现寻找具有负降低成本的姿势。算法1隐式列生成1：P←{}2：重复3：λ←MaximizedualinEq. （3）overcolumnsetP？4：P←{}5：对于s0∈ S0，6：p*←argΣminp∈Ps0Θp+Σd∈DλdP dp7：如果Θp*+d∈DλdPdp*0，则<8：P←[P∪p*]9：如果结束10：结束十一：P←[P，P]第12章：你是我的|P|=0通过NBD加速DP并应用于MPPE7sSsSS4动态规划Alg 1的关键步骤是在给定对偶变量λ（第6行）的情况下找到具有最低降低成本的姿态：Minp∈Ps0 Θp+ Σd∈DλdPdp（4）在运筹学文献中，求解Eq. (4)通常被称为定价。形式上，让我们假设图中描绘的图。1（a）的条件颈部配置，s0，从而成为一个树形图。我们将部分r的子集合定义为{r→}。我们还将µr定义为成本，或partrwithtsparentr的信息（associatedwithstates）：µr= min Σ SrSrφ+νr（五）s∈Srd∈Drd∈Drdssdds其中，第一项计算部分r和其父项r之间的成对成本。对于在特定时间段处生成的子项的成本的计算，并且定义为：νr=ψr+Σµr¯（六）s s sr¯∈{r→}Σ Σ Σr=（θd+λd）Sr+φddSrSr+φddS0SrSd∈DrDSd1∈Dr1 2d1sd2sd ∈D012第1秒0第2秒d2∈Dr1d2∈Dr因此求解Eq.（4）涉及沿着（条件）树图G=（V，E）从叶节点（手腕和脚踝）到根节点（头部）计算和传递消息;对于根节点，等式（5）等于等式（4）减去Ω。 要计算每个y∈Sr的µ r，并将节点定义为一个节点的任意一个节点，则需要使用多项式平均值计算。 我有一个|Dr|为|Dr|=15时，由于DP需要约30k个随机态，所以DP需要在9 × 108个态的联合空间中进行计算，这对于实际应用来说是非常昂贵的.5嵌套弯曲分解在本节中，我们提出了一个近似线性时间算法（w.r.t |SR|）在实践中，计算器会计算E q中的数据量termµr´i。 （六）、该算法的核心思想是应用嵌套Benders分解（NBD），使得对于每个父子边（r，r′），r′∈{r→}，我们对D r的仿射函数S进行最小的仿射运算;该仿射函数S的最大值为sµr′。8S. Wang，中国山核桃A. Ihler，K. J.YarkonySSs本质上，这些集合中的每一个都形成消息的较低信封，使它们依赖于较低信封中的最大值;如果这些集合的信封是一个小的信封（相对于|Sr'|），则新算法可以在O（1）中的任意一个节点上计算开销，但需要O（|Sr¯|），因此计算每个状态s∈ Sr的消息将花费O（|SR|）而不是O（|SR|×|Sr'|）的情况。5.1Benders分解公式现在，我们严格地定义了我们的Benders分解公式，用于特定的parentt-childddgepair（r，r′），其中对于s h或th和d，e e不为e ∈ E。我们可以找到一组具有较低带宽的函数，并将其存储为Z索引为z，并将第z个仿射函数参数化为（ωez，ωez，. . . ，ωezr）。为01| D|为了简化符号，我们在论文的其余部分去掉了上标e。如果Zeindformslowerevelopsofµr¯theheve：µr<$=maxωz+ Σ ωzSr， e=（r，r<$）∈E（7）sz∈Z e0D SDd∈Dr在Benders分解的上下文中，Z e中的一个仿射函数被称为Benderssrw。为了方便起见，我们将在以下内容中加入内容集Z当ω0=−∞，ω0=0，d∈Dr。0天我们在边缘（r，r′）的估计年龄上找到一个较低的边缘，如下：µr¯−=maxωz+Σ ωzSr， e=（r，r¯）∈E（8）sz∈Ze0D SDd∈Drwhhichsatis fie sµr<$$>−≤µr<$$>. 这两个条件是s*=argmins∈Srµr¯s s s如果下界是紧的5.2生成新的Bender行在Eq的有限元素t中 ， 没 有 新 的 定 义 的 细 奇 偶 校 验 对 （r，r′）。（六）、在该部分中，我们描述了如何在等式1的上下文中生成新的Benders行。（5），其中，将t-child对不定义为（r，r）。Givencuren ttteZeofanedge（r，r）∈E，withrassociatedwithtates，我们检查是否存在可以增加当前下限的新Benders行µr−。这通过以下公式计算：min Σ SrSrφ+νr−（九）s∈Srd∈Drd∈Drdssdds其中：通过NBD加速DP并应用于MPPE9ˆDSDSdsDS0以上dd∗0νr−=ψr+ Σµr¯−s ssr¯∈{r→}（十）整数线性规划在这里，我们重新公式方程。（9）作为整数线性rrpro ram. 我们使用i∈ {0，1}或v∈{0，1}|D|，y∈{0，1}|D|×|D|，当xs= 1当且仅当选择s∈Sr且ydd=Sr（dss∈SrxsSr）：minΣ νr−xs+ Σ φˆy ˆ（十一）Rx∈{0，1}| S|rrSs∈SrDD DDd∈Dry∈{0，1}| D| ×|D|S.T.Σxs= 1s∈Srd∈DrΣ-yddrdss∈Sr xsSr≤1， d∈Dr，d∈Drdddd ≤Sr，d∈Dr，d∈DrΣ≤xsSr，d∈Dr，d∈Drs∈Sr然后我们放松x，y为非负。在补充，我们提供的证据表明，这种放松总是紧。我们在下面表示松弛LP的对偶rr其中对偶变量δ0∈R，且δ1，δ2，δ3均在R中|D|×| D|索引的通过d，d：MaxΣδ0−δ1Σ+（δ1— δ2）Sr（十二）δ0∈R（δ1，δ2，δ3）≥0d∈Drd∈DrddΣd∈Drd∈DrdddddsS.T. νr−−δ0+（δ1— δ3）Sr≥0， εs∈SrSd∈Drd∈Drdddddsφd d1dd2dd3dd ≥0，ndn∈Drn，d∈DrObserveEq. （12）是D_r的一个仿射函数，因此，当双变量E_q是最优的时， （12）在w可以加到Ze，e=（r，r）处，给出一个新的B项。让我们将新的Benders行表示为z*，然后我们从对偶变量构造该行：z =δ0−∗ΣΣd∈Drd∈Dr1dd（十三）zdd∈Dr1dd -δ2，d∈Dr（十四）+S-δ+δ+δωδωδ+=10S. Wang，中国山核桃A. Ihler，K. J.Yarkonys*sR0R不是所有在childmesagesµ r ´ −上的低e r bounds，r´∈{r→}都是对s*∈Sr的最小化等式（1）的最小化。(9)，则新的Benders行z*在messageµr上形成一个紧密的下限，以用于该特定的parentates？。求解对偶LP可以直接以封闭形式求解（12），或者经由现成的LP求解器求解，这两者都给出了一个父st在εs的最大下界。然而，我们发现，新的Bender消息流策略被赋予了一个较低的下限，以确保所有的参数都是S∈ S，因此，我们可以使用四个流作为posile来形成消息上的一个紧密的下限。我们通过添加具有微小负幅度权重的L1正则化来实现这一点，以优选较小的δ1，δ2值。这种技术在运筹学文献中被称为我们给出了详细的推导，为什么这样的正则化提供了更好的整体下限的补充。5.3精确推理算法2嵌套弯曲分解1：G=（R，E），G是树结构图2：Ze←singlerowithω0=−∞，ω=0，d∈Dr，e=（r，r）∈E3：s*←，∆r4：重复D←0，r∈R5：对于r∈ R，从叶到根做6：对于z∈Ze，e=（r，r），r∈{r→}do7：经由等式（1）更新δ0（十五）8：通过等式（1）更新ωz（十三）9：结束10：结束11：s*←arg mins∈Srνr−，其中r是根俄.西12：forr∈RfrommchildrΣenoffroottooleavesdo13：s*←argmins∈SrrSrSrφ+νr−，wheres=s*rd∈Dr Σd∈DdssddsrΣ14：∆r←ˆrSrSrφ+νr−− maxeωz+ˆrωzSr，其中s=d∈Drd∈Ddssddsz∈Z0d∈Dddss*，s=s*，e=（r，r），r∈{r→}rr15：结束16：r←arg maxr∈Rr十七：Zs t e c e←Zstecez，其中z是新的边界，对于re=（r，r），r∈{r→}18：直到|阿德尔|<，19：返回姿态p对应于{s∈ R，r∈ R}鉴于基本的折弯机分解技术在前面的章节中描述，我们现在介绍嵌套折弯机分解算法，它被描述为Alg 2。该算法可以概括为四个步骤：通过NBD加速DP并应用于MPPE11Ss*R更新旧折弯机行（第5-10行）NBD算法重复更新基于节点的存储空间上的下一行，这使得Z可 从节点的存储空间中恢复。除了每次迭代都从头开始计算Z e 之外，我们重新使用由先前迭代产生的δ项，固定δ 1，δ 2，δ 3并且仅更新δ 0以在ν r−中给出新的子消息的情况下δ0←minνr−+Σ（δ1— δ3）Sr（十五）s∈Srsd∈Drd∈Drddddds计算每个节点的最优状态和间隙（第11-15行）接下来，我们从根节点到叶子节点，并计算每个节点的最优状态，给定消息的当前下限给定节点r的当前状态估计和itsparentr，weeme作为由itsel和其父节点估计的消息估计的消息所确定的间隙，并将该间隙表示为Ar（第14行）。注意根的∆始终为0，因为根没有父根。找到给出最大间隙的节点（第16行）我们找到节点r在所有节点上，间隙Δr最大，并将该节点表示为r*。计算并添加新的Benders行（第17行）我们通过求解方程，为r*生成一个新的Benders行z*（12）-（14）.然后将该行z*添加到dingsetZe上的c或re s p，其中ree=（r，r*），r*∈{r→}。当图中每个节点的间隙∆在期望的精度（在我们的实现中为0）下时，我们终止，并返回每个节点的最佳状态。在下文中，我们证明Alg 2在根部分（我们在这里表示为部分1）处以如由DP计算引理1.在Alg 2的终点，ν1−1成本等于姿势的成本对应于节点{s*，r∈R}证据在Alg 2的终止处，对于每个r ∈ R建立以下等式：state ss=s*，s=s*：rr∆r= 0 = Σ SrSrφ+νr−−maxωz+ΣωzSr（十六）d∈Drd∈Drdssddsz∈Z空间0d∈Drdds通过移动−maxωz+ΣωzSrtoth otheothersideestablish下面的z∈Z空间0d∈DrdΣSrSrφ +νr−=maxωz+ΣωzSr =µr−（十七）d∈Drd∈Drdssddsz∈Z空间0d∈Dr��12S. Wang，中国山核桃A. Ihler，K. J.YarkonySRs*111Wenowsubstituteµr¯−termsinEq. （10）具有Eq. （十七）νr−=ψr+ Σ SrSrφ+νr−（十八）ssd∈Drd∈Drdssdds注意在叶子上νr−=ψr，s∈Sr。从ν1−开始，我们递归地展开ν−s s s条款，并建立以下内容：Σ1−Σ Σrrνs*=ψs*+SSdsφdd（19）1rr∈R（r，r）∈Ed∈Drd∈Drdsrr它是由解选择的所有一元项和成对项的和{s*，r∈ R}.引理2. 在Alg 2的终点，ν1−的成本等于min s∈R1 ν1*第1条证据 我们用矛盾来证明这一点。假设ν1−/= mins∈R1ν1，根据*第1条对于引理1，这一定意味着ν1−>min s∈R1ν1。如果在最低限度-*第1条如果根的子族的贤人是紧的，那么它意味着ν1−不是紧的，∆1将是1已经是非零的，并且Alg 2将不会终止，从而产生矛盾。另一方面，如果来自子节点的某些消息的下限不紧，则该子节点的∆值将为非零，并且算法将继续运行，仍然产生矛盾。实验上，我们观察到NBD中的步骤所消耗的总时间从最大到最小排序为[1，2，4，3]。注意，求解LP的步骤是NBD中耗时第二少的步骤。6实验我们评估了我们的方法对一个朴素的动态规划为基础的公式的MPII-多人验证集[2]，其中包括418个图像。使用[8]的代码训练项φ、θ，并进行以下修改：1. 对于每对唯一的颈部检测dl、d2，我们设置Φdld2=∞;作为副作用，这也提高了推理速度，因为我们不需要探索颈部检测的整个功率集。2. 对于整个数据集，我们手动将Ω3. 我们将给定部分/节点的状态数限制为50，000。我们构造这个集合如下：我们从对应于包括的零个检测的状态开始，然后添加到对应于包括的一个检测的状态组中;然后将对应于所包括的两个检测的状态组相加，等等。如果添加组将使状态空间超过50，000秒，则不添加组和数据。SSS111通过NBD加速DP并应用于MPPE13(a)（b）第（1）款图2：NBD实现的时序比较和加速。(a)分别针对NBD和DP的问题实例的累积运行时间。(b)NBD相对于DP的加速因子，作为DP定价所花费的计算时间的函数。请注意，一般来说，随着DP问题变得更加困难，加速因子也会增加。我们比较了NBD和DP在ICG的每个步骤中找到的解决方案;对于所有问题实例和所有优化步骤，NBD获得与DP完全相同的解决方案（直到成本并列）。通过比较在问题实例中执行NBD与DP所花费的总时间，我们发现NBD比DP快44倍，并且在极端问题实例中可以快500倍。NBD和DP在所有418个实例上使用的累积运行时间的比较如图所示。2.我们观察到，由NBD提供的因子加速作为DP的计算时间的函数而增加在超过99%的问题实例中，由于D_P的整数对于LP松弛未能产生整数结果的那些实例，LP目标之间的间隙并且整数解都在LP目标的1.5%以内 这通过将Eq2中的ILP求解到PΦ来实现。部件头肩肘腕髋膝踝mAP（UBody）mAP时间（秒/帧）我们的90.687.379.570.1 78.5 70.564.881.877.61.95[10]93.088.278.268.4 78.9 70.064.381.977.60.136表1：我们显示了我们的方法与[10]的平均精度。运行时间在Intel i7- 6700 k四核CPU上测量。14S. Wang，中国山核桃A. Ihler，K. J.Yarkony为了完整起见，我们还报告了平均精度（AP）方面的MPPE准确性，并将其与最先进的原始启发式求解器[10]进行比较（图2）。①的人。 我们注意到，与[10]相比，我们在手腕和脚踝等难以定位的部位表现出色，但在头部和肩部等靠近颈部的部位表现不佳;这可能是来自[8]的成本在包括颈部的所有检测的功率集上训练的事实的副作用，因此对于某些情况，与多个颈部检测相关联的姿态可能是更好的选择。在更鲁棒的模型中，可以制作可靠的头部/颈部检测器，限制每个人只有一个头部/颈部。图3：我们的系统的示例输出。7结论我们已经将MPPE描述为MWSP问题，我们使用ICG解决该问题，并通过NBD解决相应的定价问题。对于超过99%的案例，我们找到了可证明的最佳解决方案，这在确定性知识很重要的领域（如康复干预）中我们的程序解决定价问题大大优于基线动态规划方法。我们预计NBD将在机器学习和计算机视觉中找到许多应用，特别是用于解决具有超高树宽图的动态例如，我们可以将子图多割跟踪[16]公式化为使用ICG解决的MWSP问题，通过NBD解决定价此外，对于主要包含循环的一般图，我们的NBD直接适用于对偶分解算法[9，18]，该算法将图分解为一组可通过动态程序求解的树。通过NBD加速DP并应用于MPPE15引用1. Andres，B.，Kappes，J.H.，Beier，T.，Kothe，U. Hamprecht，F.A.：具有封闭性约束的概率图像分割。见：ICCV（2011年）2. Andriluka，M.，Pishchulin，L. Gehler，P. Schiele，B.：2D人体姿态估计：新的基准和最先进的分析。In：Proc.CVPR（2014）3. Bansal，N. Blum，A.，Chawla，S.：相关聚类发表于：Journal of MachineLearningg. pp. 2384. Belanger，D.，Passos，A.，Riedel，S.，McCallum，A.：使用列生成在链中映射推理。见：NIPS的程序（2012）5. Birge，J.R.：多阶段随机线性规划的分解与分割方法。operationsreearch33（5），9896. Felzenszwalb，P.F.，Girshick，R.B.，McAllester，D.Ramanan，D.：使用区 分 性 训 练 的 基 于 部 分 的 模 型 进 行 对 象 IEEE Transactions onpatternanalysis and machi nei n e intellige nce32（9），16277. Felzenszwalb，P.F.，Huttenlocher，D.P.：采样函数的距离变换。Tech.代表，康奈尔大学计算机与信息科学（2004）8. Insafutdinov，E.，Pishchulin，L. Andres，B.，Andriluka，M.，Schiele，B. ： 深 切 割 ： 更 深 、 更 强 、 更 快 的 多 人 姿 势 估 计 模 型 。 CoRRabs/1605.03170（2016），http://arxiv.org/abs/1605.031709. Komodakis，N.，Paragios，N. Tziritas，G.：通过双重分解的MRF优化：重新审视信息传递。见：ICCV Proc.（2007）10. Levinkov，E.，Uhrig，J.，唐，S.，Omran，M.，Insafutdinov，E.，Kirillov，A.，Rother，C.，Brox，T.，Schiele，B.，Andres，B.：联合图分解和节点标记：问题，算法，应用。见：CVPR的Proc.（2017）11. Magnanti，T.L.，黄仁道：加速折弯机分解：化学增强和现代化的结构。operationsresearch29（3），46412. McAuley，J.J.，Caetano，T.S.：利用数据独立性进行快速置信传播。In：Proc. of ICML（2010）13. Murphy，J.：折弯机、嵌套折弯机和随机编程：直观的介绍。ArXiv预印本arXiv：1312.3158（2013）14. Pirsiavash，H.，Ramanan，D. Fowlkes，C.C.：用于跟踪可变数量对象的全局最优贪婪算法。In：Proc.CVPR（2011年）15. Pishchulin，L. Insafutdinov，E.，唐，S.，Andres，B.，Andriluka，M.，Gehler，P. Schiele，B.：DeepCut：联合子集分割和标记用于多人姿势估计。见：CVPR的程序（2016）16. 唐，S.，Andres，B.，Andriluka，M.，Schiele，B.：多目标跟踪的子图分解见：CVPR的Proc.（2015）17. 杨，Y.，Ramanan，D.：具有柔性部件混合的铰接姿态估计。见：CVPR的程序（2011）18. Yarkony，J.，福克斯角Ihler，A.：覆盖树与二次分配的下界。见：CVPR的程序（2010）19. Yarkony，J.，Ihler，A.，Fowlkes，C.：用于图像分割的快速平面相关聚类。见：ECCV（2012年）