用线性近似加速图匹配，提升视觉特征对应效率。
CLAP: Concave Linear APproximation for Quadratic Graph Matching
- 将二次分配问题转化为凹线性模型，利用半正定矩阵约束结构属性。
- 在PascalVOC上达到当前最优性能，计算速度显著提升。
- 适合需要高效精准特征匹配的视觉任务研究者使用。
视觉数据中的点级特征对应是计算机视觉的基础问题。现有方法常将其建模为带有节点和边约束的二次分配问题（QAP），但求解过程因大量局部极值点而昂贵且困难。本文提出一种新的线性模型与求解器，通过半正定矩阵近似建立结构属性约束，将原QAP转化为可最大化且凹的线性模型。该模型可借助以高效和数值稳定著称的Sinkhorn最优传输算法求解。在广泛使用的PascalVOC基准测试中，本方法实现当前最优性能，并显著提升计算效率。源代码见：https://github.com/xmlyqing00/clap。
原文摘要 · Abstract (English)
Solving point-wise feature correspondence in visual data is a fundamental problem in computer vision. A powerful model that addresses this challenge is to formulate it as graph matching, which entails solving a Quadratic Assignment Problem (QAP) with node-wise and edge-wise constraints. However, solving such a QAP can be both expensive and difficult due to numerous local extreme points. In this work, we introduce a novel linear model and solver designed to accelerate the computation of graph matching. Specifically, we employ a positive semi-definite matrix approximation to establish the structural attribute constraint.We then transform the original QAP into a linear model that is concave for maximization. This model can subsequently be solved using the Sinkhorn optimal transport algorithm, known for its enhanced efficiency and numerical stability compared to existing approaches. Experimental results on the widely used benchmark PascalVOC showcase that our algorithm achieves state-of-the-art performance with significantly improved efficiency. Source code: https://github.com/xmlyqing00/clap
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。