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).

- Feng Zhou (CMU)
- Fernando De la Torre (CMU)

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)^{[6]}. Unfortunately, QAP is NP-hard and many algorithms have been proposed to solve different relaxations.

We propose **factorized graph matching (FGM)**^{[1]}^{[2]}^{[3]} 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
^{[5]}algorithm that leads to improved optimization strategies and matching performance; - The factorization enables us to incorporate geometric transformations (rigid or non-rigid) to GM.

Available at here.

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.

Download the [Video 3MB].

This video compares different graph matching methods on the Car and Motorbikes image datasets^{[4]}.

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.

Download the [Video 30MB].

- [1]Factorized Graph MatchingUnder Review at IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI)

F. Zhou and F. De la Torre[Paper 8MB] - [2]Deformable Graph MatchingIEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2013

F. Zhou and F. De la Torre - [3]Factorized Graph MatchingIEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2012

F. Zhou and F. De la Torre

- [4]An Integer Projected Fixed Point Method for Graph Matching and MAP InferenceAdvances in Neural Information Processing Systems (NIPS), 2009

M. Leordeanu, M. Hebert and R. Sukthankar[Webpage] - [5]A Path Following Algorithm for the Graph Matching ProblemIEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 2009

M. Zaslavskiy, F. R. Bach, and J.-P. Vert[Webpage] - [6]A Survey for the Quadratic Assignment ProblemEuropean Journal of Operational Research, 2007

E. M. Loiola, N. M. De Abreu, P. O. Boaventura, P. Hahn and T. M. Querido