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



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:


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