ICMLMar, 2015

通过 Lifted Multicuts 的图分解分析和优化

PDF
TL;DR本研究通过将图划分的特征化为一组提升的多割来研究所有分解（聚类）的集合，发现了与通过必须连接和必须割约束定义分解类以及与度量比较聚类有关的实际相关的见解。通过定义提升多割多面体的某些面的属性，定义高效的分离程序并在分支中使用这些程序，找到了由最小成本提升多割定义的最优分解的算法。
decompositionsclusteringslifted multicutspolytopesbranch-and-cut algorithm
发现论文，激发创造
  • 运动分割的高阶最小成本提升多切割

    该论文针对运动分割中的局限性提出了一种基于超图的最小成本量切割方法和相应的启发式算法，准确构建出点轨迹的高阶图形模型，以更好地区分运动模型的不同变换，结果在 FBMS-59 数据集上表现优于现有技术。

    Apr, 2017

  • 抬升多切割凸多面体的切割平面和立方体平面

    对于提升多割问题的规范化面，本文回答了两个基本问题：哪些下界立方不等式定义了面，哪些割不等式定义了面。并且我们证明了对于割不等式的面定义性判定是 NP 难的。

    Feb, 2024

  • 多切割技术支持的高阶分割

    Multicuts 和 higher-order models 在图像分割和计算机视觉中被广泛应用，在考虑 higher-order terms 的计算插值中，我们提出了一种系统的方法，并对各种算法进行了全面和竞争性的评估，此方法允许计算出一组重要的模型的全局最优解，同时不会影响运行时间，同时还研究了可解的松弛问题和后处理技术。

    May, 2013

  • 图分解的端到端学习

    提出了一种基于条件随机场的端到端可训练框架来解决图分解问题，用于图的二值化和特征表示学习，并在 MNIST 和真实世界中的多人姿态估计任务中进行了验证。

    Dec, 2018

  • 潜在的随机步骤作为最大割、最小割和更多的松弛

    基于非负矩阵分解的概率模型统一了节点聚类和图简化，提供了建模任意图结构的框架。通过将硬聚类放松为软聚类，我们的算法将潜在的困难聚类问题转化为易处理的问题。

    Aug, 2023

  • 多目标联合分割和跟踪的多割切形式化

    本文提出一种基于最小代价多切割公式的联合图模型，该模型结合了点轨迹和对象检测的高级信息和本地关系，成功地解决了运动分割和多目标跟踪等任务。

    Jul, 2016

  • 联合图分解和节点标签化：问题、算法、应用

    定义了一个组合优化问题，其可行解定义了给定图形的分解和节点标记，并提出了两种局部搜索算法来高效地找到可行解，应用于计算机视觉任务达到 state-of-the-art 应用特定精度。

    Nov, 2016

  • 组合问题拉格朗日分解的双重升级框架

    提出了一种通用的双升算法框架来处理组合问题的 Lagrangean decomposition，表现出明显的效能优势，可用于图匹配和多切问题等多种应用。

    Dec, 2016

  • 基于 Multicut 和 Deep Matching 的多人跟踪

    本文提出了一种基于图形的跟踪方法，使用新的本地成对特征，解决包含离群点的多切割问题并在 MOT16 基准测试上取得了最优效果。

    Aug, 2016

  • 通过图粗化和最优割方法的受限层次聚类

    通过在短句设置中提取和总结相关信息，我们研究了以层次化方式对单词进行聚类的问题，特别是关注具有水平和垂直结构约束的聚类问题，我们通过将问题分为两个步骤来克服现有技术的瓶颈，首先，将其作为一个有软约束的正则化最小二乘问题来引导顺序图粗化算法的结果朝向水平可行解集，然后通过计算基于可用约束的最优截断高度从生成的层次树中提取平坦的聚类，我们展示了这种方法相对于现有算法具有很好的比较性能且计算上轻量级。

    Dec, 2023