1 of 29

CLAP: Concave Linear APproximation for Quadratic Graph Matching

Yongqing Liang, Huijun Han, Xin Li*

Texas A&M University, USA

{lyq, hazelhan, xinli} @ tamu.edu

ISVC 2024

Lake Tahoe, USA

2 of 29

Background: Keypoints in Computer Vision

LF-Detection (Ono et al.’18)

SIFT Detector

Source: https://www.codeproject.com/articles/619039/bag-of-features-descriptor-on-sift-features-with-o?fid=1836776&df=90&mpp=25&prof=True&sort=Position&view=Normal&spc=Relaxed&fr=76

3 of 29

Point-wise Correspondence

Keypoints detection and matching

Source: RF-Net. Shen et al.

4 of 29

Applications in Computer Vision

Image stitching

3D reconstruction from image

SLAM

Keypoints detection 🡪 Correspondence Matching 🡪 Camera poses / 3D object

Source: https://pyimagesearch.com/2018/12/17/image-stitching-with-opencv-and-python/

5 of 29

Graph Matching in Computer Vision

Unary Matching: Finding correspondences by node features

Node features:

  • RGB
  • Local gradient
  • Network features

6 of 29

Problem of using nodes for graph matching

Pairwise Matching: Finding correspondences by pairwise features

Pairwise features:

  • Edge length
  • Topological features
  • Concat of Node features
  • Network features

7 of 29

8 of 29

Introduction

  • Point-wise Feature Correspondence 🡪
  • Graph Matching 🡪
  • Quadratic Assignment Problem (QAP) 🡪 Hard to optimize

​

  • We introduce a Linear Approximation Model that is concave for maximization.

​

9 of 29

Problem Setting

Node Features:

1

2

3

4

1

2

3

4

Graph matching?

Adjacency Features:

0

X

X

X

X

0

X

X

X

X

0

X

X

X

X

0

0

Y

Y

Y

Y

0

X

Y

Y

Y

0

Y

Y

Y

Y

0

 

 

 

 

 

 

10 of 29

Node Features:

1

2

3

4

1

2

3

4

Adjacency Features:

0

X

X

X

X

0

X

X

X

X

0

X

X

X

X

0

0

Y

Y

Y

Y

0

X

Y

Y

Y

0

Y

Y

Y

Y

Y

 

 

 

 

 

 

 

 

P

0

0

0

1

0

0

1

0

1

0

0

0

0

1

0

0

 

 

1

2

3

4

1

2

3

4

11 of 29

 

Objective

function

 

New

Objective

function

12 of 29

Our CLAP Model

  • Observation
  • Concave Linear APproximation (CLAP)
  • Converting symmetric matrix to semi-positive definite
  • Differentiable Linear Solver

​

13 of 29

But, solving P in discrete space is an NP problem.

We need to relax P to a continuous field P’.

The objective function is quadratic and its Hessian matrix is indefinite

🡪 Non-concave

🡪 Many local maximums

So existing solvers require long computing time to converge.

 

1

2

3

4

 

0

2

6

3

2

0

4

5

6

4

0

inf

3

5

inf

0

3

2

6

5

4

Example 2: Inner-product distance matrix

 

 

So,

Our contribution is find a linear approximation that is concave to solve the graph matching.

14 of 29

Our CLAP Model

  • Observation
  • Concave Linear APproximation (CLAP)
  • Converting symmetric matrix to semi-positive definite
  • Differentiable Linear Solver

​

15 of 29

Our Concave Linear APproximation (CLAP)

 

Node Features:

1

2

3

4

Adjacency Features:

0

X

X

X

X

0

X

X

X

X

0

X

X

X

X

0

 

 

 

Here, we optimize a L2 norm term indeed.

Can we optimize a L1 norm term instead?

​

Yes, we can.

16 of 29

Our Concave Linear APproximation (CLAP)

Node Features:

1

2

3

4

Adjacency Features:

0

X

X

X

X

0

X

X

X

X

0

X

X

X

X

0

 

 

 

🡪

Sum of squares 🡪 Sum of absolutes approximation

​

Advantages:

  1. L1 norm is more robust to outlier vs L2 norm
  2. With entropy regularization, the obj func could be comcave

17 of 29

Our CLAP Model

  • Observation
  • Concave Linear APproximation (CLAP)
  • Converting symmetric matrix to semi-positive definite
  • Differentiable Linear Solver

​

18 of 29

From Symmetry to Semi-positive Definite

Node Features:

1

2

3

4

Adjacency Features:

0

X

X

X

X

0

X

X

X

X

0

X

X

X

X

0

 

 

 

Observation of adjacency matrices DA , DB

  1. The diagonal entries are 0 (undefined)
  2. The matrix is symmetry.

​

We can modify the adjacency matrices to make them semi-positive definite while preserving their original meaning.

According to Gershgorin circle theorem, we could achieve this by modifying the diagonal entries.

19 of 29

Gershgorin Circle Theorem

  •  

0

 

 

 

 

 

20 of 29

Converting Symmetry to Semi-positive Definite

 

x could be A or B

 

21 of 29

Our CLAP Model

  • Observation
  • Concave Linear APproximation (CLAP)
  • Converting symmetric matrix to semi-positive definite
  • Differentiable Linear Solver

​

22 of 29

Differentiable Linear Solver (Sinkhorn)

Objective function

 

Lagrangian function

Derivatives

P_ij can be iteratively optimized.

23 of 29

Results on Synthetic Dataset

Synthetic dataset: random affine transformation

Qc-DGM: Deep graph matching under quadratic constraint. (2021 CVPR)

24 of 29

25 of 29

Acc. And Speedup compared with baseline

Qc-DGM: Deep graph matching under quadratic constraint. (2021 CVPR)

26 of 29

Results compared with related work

Qc-DGM: Deep graph matching under quadratic constraint. (2021 CVPR)

IPCA: Learning combinatorial embedding networks for deep graph matching. (2019 ICCV)

PCA : Combinatorial learning of robust deep graph matching: an embedding based approach (2020 T-PAMI)

CIE-H: Learning deep graph matching with channel independent embedding and hungarian attention. (2019 ICLR)

27 of 29

Pascal VOC Benchmark

28 of 29

Conclusion

  • A new linear model for fast graph matching.
  • We reformulated the pairwise graph matching as a concave maximization problem, which has a global maximum and can be solved efficiently.
  • We showed that a common symmetric edge attribute matrix can be refined to be- come positive semi-definite to construct a linear structure constraint.
  • The problem can be solved using the Sinkhorn algorithm.

​

  • Limitations:
    • Point / edge descriptors depend on learning. When the descriptors become unreliable, this could negatively impact matching accuracy.
  • Future Work:
    • Explore learning mechanisms to estimate confidence of local feature descriptors.

29 of 29

CLAP: Concave Linear APproximation for Quadratic Graph Matching

Yongqing Liang, Huijun Han, Xin Li*

Texas A&M University, USA

{lyq, hazelhan, xinli} @ tamu.edu

ISVC 2024

Lake Tahoe, USA