# Graph Matching Matching two human bodies with 5 and 4 features.

Our method simultaneously estimates the correspondence and a smooth non-rigid transformation between shapes. Our method is able to factorize the 20-by-20 pairwise affinity matrix as Kronecker product of six smaller matrices. The first two groups of matrices of size 5-by-6 and 4-by-10 encode the structure of each of the graphs. The last two matrices encode the affinities for nodes (5-by-4) and edges (16-by-10).

## Introduction

Graph matching (GM) plays a central role in solving correspondence problems in computer vision. Graph matching problems that incorporate pair-wise constraints can be cast as a quadratic assignment problem (QAP). Unfortunately, QAP is NP-hard and many algorithms have been proposed to solve different relaxations.

We propose factorized graph matching (FGM) for better interpreting and optimizing graph matching problems. We show that the affinity matrix can be factorized as a Kronecker product of smaller matrices. There are four main benefits of using this factorization in graph matching:

• There is no need to compute the costly (in space and time) pair-wise affinity matrix;
• It provides a unified view for GM that reveals commonalities and differences between methods;
• The factorization allows the use of a path-following optimization algorithm that leads to improved optimization strategies and matching performance;
• The factorization enables us to incorporate geometric transformations (rigid or non-rigid) to GM.

## Code

Available at here.

## Results

An example of the path-following optimization for matching two houses

The images are taken from the CMU House Image Dataset. The two graphs are computed by the Delaunay Triangulation. The edge feature is the distance between nodes. You can reproduce the same result using the function demoHouse.m in the code.

This video compares different graph matching methods on the Car and Motorbikes image datasets.

This dataset consists of 30 pairs of cars and 20 pairs of motorbikes taken from the PASCAL image dataset. The graphs are computed by the Delaunay triangulation. The edge feature is computed as the distance between nodes as well as the angle between the edge and the horizontal line.

## Publications

• 
Factorized Graph Matching
IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 38(9):1774-1789, 2016
F. Zhou and F. De la Torre
• 
Deformable Graph Matching
IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2013
F. Zhou and F. De la Torre
• 
Factorized Graph Matching
IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2012
F. Zhou and F. De la Torre

## References

• 
An Integer Projected Fixed Point Method for Graph Matching and MAP Inference
Advances in Neural Information Processing Systems (NIPS), 2009
M. Leordeanu, M. Hebert and R. Sukthankar
• 
A Path Following Algorithm for the Graph Matching Problem
IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 2009
M. Zaslavskiy, F. R. Bach, and J.-P. Vert
• 
A Survey for the Quadratic Assignment Problem
European Journal of Operational Research, 2007
E. M. Loiola, N. M. De Abreu, P. O. Boaventura, P. Hahn and T. M. Querido