ECCVJul, 2016

离散能量最小化问题的复杂度

PDF
TL;DR本文研究了离散能量最小化问题在 2 标签配对的情况下和三个以上标签的平面能量最小化问题的多项式时间内是否可以用合理的近似算法求解。结果表明，这两个问题都是 exp-APX 完全问题，不存在任何多项式时间的近似算法。此外，本文收集并综述了几个子类问题的复杂度，并将其排列在由 PO、APX 和 exp-APX 组成的复杂度尺度上，为视觉研究人员选择适当的模型或指导他们设计新算法提供了帮助。
discrete energy minimizationcomputer visiongraphical modelscomputational complexityapproximation algorithm
发现论文，激发创造
  • 使用部分枚举简化能源优化

    该文提出了一种基于小块标记枚举的大图通用最小化方法，可用于复杂高阶能量的优化。该方法在曲率正则化等难解问题上表现优越，并通过一种新颖的积分几何方法直接评估小块的曲率。

    Mar, 2013

  • 离散图模型 -- 优化视角

    本文说明了离散图形模型的离散能量最小化问题及其多种优化解法，其中包括多种精确优化方法和基于信息传递和图割技术的近似方法。

    Jan, 2020

  • 通用图模型 MAP 推断的剪枝部分最优化

    本文提出了一种新的多项式时间算法来解决最小化无向图模型的能量问题，利用凸松弛方法得到部分最优非松弛积分解，并采用迭代修建策略优化算法，相较之前的方法表现更好。

    Oct, 2014

  • 简约性标记

    本论文提出了一种新的离散能量最低化问题家族，称为简明标记。我们的能量函数包括一元潜势和高阶团势。其中，一元潜势是任意的，而团势则与分配给团的唯一标签的多样性成比例。我们的能量函数鼓励标记是简明的，即尽可能少地使用标签。此外，我们提出了一种高效的基于图割方法的算法，可以提供强有力的理论保证，用于简明标记问题。

    Jul, 2015

  • 基于数据驱动能量最小化方法的参数化主元化

    本文提出了一种用于训练参数化能量最小化模型的新策略，该策略结合了能量最小化方法和深度学习技术，并解决了在许多现代数据处理需求方面难以扩展到公共优化算法的双层优化问题。

    Aug, 2019

  • 现代推理技术在结构离散能量最小化问题中的比较研究

    该研究比较了 32 种现代化的最优化技术在计算机视觉中的应用，结果表明，与之前研究不同，多面体方法与整数规划解决方案在运行时间和解决方案质量方面在大范围的模型类型上具有竞争力。

    Apr, 2014

  • 能量最小化中的最大持久度

    本文针对离散的成对能量最小化问题（加权约束满足、最大求和标记），探讨了一种可在多项式时间内验证、对问题重新参数化和标签置换具有不变性、包含许多现有足够条件的新足够条件，以及通过特别构造的计算线性函数程序解决在任意多标签环境下确定有保持不变的分配任务。

    Apr, 2014

  • 有约束极小极大优化的复杂性

    本文通过分析优化问题的计算复杂性，阐明了一系列非凸非凹目标函数的约束极值优化问题存在的困难，同时证明了该问题在 Nemirovsky-Yudin 模型中的难度，这与最小化问题在同样设置下可以使用 Projected Gradient Descent 进行近似局部最小值的行为形成了对比。

    Sep, 2020

  • 量子退火用于计算机视觉最小化问题

    这项研究探讨了基于量子退火的推断算法在计算机视觉离散能量最小化问题中的应用，特别关注了立体匹配作为一个重要的计算机视觉标签问题，并使用 D-Wave System 提供的混合量子 - 经典求解器来与文献中最好的经典推断算法进行比较。

    Dec, 2023

  • 离散优化中可处理的三角形和无交凸性

    研究了离散优化问题的计算复杂度，基于限制变量 - 值分配三元组的每个三角形的成本，发现最大匹配问题和联合胜者性质是唯一的可接受限制，同时提出了一种基于无交集分配的凸基数函数问题类，证明了其在满足交叉自由凸性的前提下为可解的。

    Jan, 2014