Jun, 2024

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

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

    本文研究的是图匹配问题，提出了一种基于学习的方法，用于解决基于图的模式识别问题。通过训练示例和标签，我们可以学习节点与边之间的兼容性，在解决问题时可以取得更好的效果。实验结果表明，该方法比现有算法更为有效。

    Jun, 2008

  • 交替方向图匹配

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

    Nov, 2016

  • 图匹配：自行决定松弛程度的风险

    研究了图匹配问题，通过实验证明了最优解不可达，证实了松弛算法加梯度下降算法的方法能在实践中达到优秀的效果。

    May, 2014

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

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

    Nov, 2018

  • 大规模（脑）图匹配的快速近似二次规划

    本文介绍了一种快速的近似二次分配算法（FAQ），能够更高效地在大数据和图值数据上处理 QAP 问题，通过在 C.elegans 连通图匹配案例上的实证表明其优越性。

    Dec, 2011

  • 最优输运在图匹配中的应用

    本文提出一种名为 GOAT 的修正版算法，它使用最优输运的方法替代了线性分配算法，以加快计算和提高准确性，用于解决图匹配问题。

    Nov, 2021

  • 可微分的近端图匹配

    本文介绍了一种基于邻近算子的图匹配算法 (DPGM)，通过将图匹配问题转化为一系列凸优化问题，实现了从图亲和矩阵到节点对应预测的可微分映射，该方法能够与深度学习框架有机地集成在一起，同时在合理的迭代次数内收敛于稳定点，并在多样数据集和 PASCAL VOC 关键点上取得了良好性能，超过了现有的图匹配算法。

    May, 2024

  • 图匹配的函数表示

    本研究提出一种新的基于功能表征的图匹配方法，能够降低相关算法的时间和空间复杂度，并且具有比现有方法更准确的匹配性能。

    Jan, 2019

  • 利用谐波分析将领域知识纳入匹配问题

    探究加速解决二次分配问题（QAP）的新方法，利用特殊的优化函数方法在傅里叶空间中优化对称群 Sn，以及在多个优化任务中学习参数。实验表明，新方法在实际领域中可以优于现有方法。

    Jun, 2012

  • KerGM: 基于核函数的图匹配

    本文提出了在 Hilbert 空间中的一些规则，引入了新的外积算法，可以在重现核 Hilbert 空间中将 Lawler 的 QAP 视为 Koopmans-Beckmann 的对齐，有效地解决了大规模亲和力矩阵的问题。提出基于熵正则化的 Frank-Wolfe 算法 (EnFW) 对 QAP 进行优化，具有与原始 FW 算法相同的收敛速率，同时显著减少每个外层迭代的计算负担，实验表明我们提出的算法在匹配准确性和可扩展性方面显著优于现有技术。

    Nov, 2019