Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2410.17101 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917812640940032 |
|---|---|
| author | Liang, Yongqing Han, Huijun Li, Xin |
| author_facet | Liang, Yongqing Han, Huijun Li, Xin |
| contents | 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 |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_17101 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | CLAP: Concave Linear APproximation for Quadratic Graph Matching Liang, Yongqing Han, Huijun Li, Xin Computer Vision and Pattern Recognition 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 |
| title | CLAP: Concave Linear APproximation for Quadratic Graph Matching |
| topic | Computer Vision and Pattern Recognition |
| url | https://arxiv.org/abs/2410.17101 |