Jul, 2012

大规模图匹配的快速投影固定点算法

PDF
TL;DR本论文提出了一种快速的大型图匹配的近似算法，使用新的投影固定点方法和双向随机投影的方法实现算法，理论上保证收敛速度为线性，并在大型合成和真实图上进行了广泛的实验，与之前的算法相比，在速度和准确性方面都有更好的表现。
发现论文，激发创造
  • 随机匹配问题的改进近似算法

    本文研究了随机匹配问题，提出一种能够提高精度的探测边的新方法和其在最大化构建匹配的期望收益中的应用，尤其在求解在线偏二分图情况时取得了显著提升。

    May, 2015

  • 交替方向图匹配

    本文提出了一种基于约束的图匹配方法，能够处理任意阶数、任意势函数的约束，在先前依赖于图结构的分解方法的基础上，通过约束匹配的分解，将图匹配重构为非凸非可分的优化问题，通过交替方向乘子法将其分解为多个较小、易于解决的子问题，从而设计了一个模块化可扩展的框架，并对基于两两约束和高阶约束的两个不同实例进行了研究，实验结果表明，所提出的解决方案在广泛采用的合成和真实示例基准测试中优于现有的两两图匹配方法，并且在高阶设置中具有竞争力。

    Nov, 2016

  • 当 LP 成为解决你的匹配烦恼的良方：随机匹配的改进界限

    本研究研究了一种随机图模型和匹配问题，提出了基于线性规划和贪心的近似算法，并探讨了匹配问题在肾脏交流和在线广告上的应用。

    Aug, 2010

  • 具有截止时间实例的快速高效匹配算法

    介绍一种具有截止时间使用市场模型的在线加权匹配问题算法，并使用 FastGreedy 和 FastPostponedGreedy 算法来获得更好的时间复杂度和更高的竞争比。

    May, 2023

  • 图匹配问题的路径跟踪算法

    本文提出了一种凸凹规划方法，用于带标签的加权图匹配问题，并且提出的算法在四个数据集上的表现都优于现有算法。

    Jan, 2008

  • 可扩展多匹配的高阶投影幂迭代

    本文介绍了一种 Higher-Order Projected Power Iteration 方法来解决多目标匹配问题，能够在不限制问题规模的情况下处理几何一致性，并保证环一致性，实验结果表明该方法优于现有方法。

    Nov, 2018

  • 使用图拓扑的不确定性感知高效子图同构

    在没有节点标签的情况下，我们提出了一种在不精确匹配的情况下识别子图与完整图之间节点对应关系的方法，该方法包括两个步骤：提取子图的最小唯一拓扑保持子集及在全图中查找可行匹配，实现基于边界可交换性的独特路径配对扩展匹配集，并通过共识算法。

    Sep, 2022

  • 解锁多图匹配的运筹学潜力

    我们研究了不完全多图匹配问题，该问题是配对多个有限集合的 NP 难问题的推广，多图匹配在计算机视觉中起着关键作用，已经提出了许多专门的优化技术。我们填补了这一差距，并将已知的多维分配问题近似算法转化为不完全多图匹配问题。通过实验证明，我们的新方法在目标和运行时间方面显著优于以前的技术水平。我们的算法能够在两分钟内匹配超过 500 个关键点的 29 个图像，而考虑的最快竞争方法至少需要半小时，同时产生了更差的结果。

    Jun, 2024

  • 图匹配：松弛与否？

    本研究考虑权重无向图的精确和非精确匹配问题，通过定义 “friendly graphs” 和发展准确和近似解的确切条件和界限，以及优化找到最优近似同构的能力的凸松弛技术进行解决。

    Jan, 2014

  • 通过迭代重新加权图连接拉普拉斯进行鲁棒的多目标匹配

    我们提出了一种高效而稳健的迭代解法来解决多目标匹配问题，通过利用图连接拉普拉斯将高阶邻域的信息纳入我们的新颖可靠的迭代重新加权策略中，我们证明了我们的算法在合成和真实数据集上的优越性能，同时阐述了现有方法的严重局限性以及标准迭代重新加权最小二乘方法的不适用性。

    Jun, 2020