# Reweighted Random Walks for Graph Matching

## Authors

## Abstract

Graph matching is an essential problem in computer vision and machine learning. In this paper, we introduce a random walk view on the problem and propose a robust graph matching algorithm against outliers and deformation. Matching between two graphs is formulated as node selection on an association graph whose nodes represent candidate correspondences between the two graphs. The solution is obtained by simulating random walks with reweighting jumps enforcing the matching constraints on the association graph. Our algorithm achieves noise-robust graph matching by iteratively updating and exploiting the confidences of candidate correspondences. In a practical sense, our work is of particular importance since the real-world matching problem is made difficult by the presence of noise and outliers. Extensive and comparative experiments demonstrate that it outperforms the state-of-the-art graph matching algorithms especially in the presence of outliers and deformation.

## Paper

ECCV 2010 paper. (pdf, 4.53MB)

### Presentation

pdf file (poster), 1.95MB

### Code

zip file (MATLAB), 35KB - updated May 2013### Datasets

zip file (png images), 10.2MB - the image dataset used in Sec.4.3
zip file (MATLAB code and data), 170MB

- additional codes and data with ground truths for image matching demo

### Citation

Minsu Cho, Jungmin Lee, Kyoung Mu Lee. "Reweighted Random Walks for Graph Matching", European Conference on Computer Vision (ECCV), 2010.

* A high-order generalization of this work is provided in our CVPR2011 paper here.

## Experimental Results

We performed intensive experiments for the proposed method in three tasks: (1) synthetically generated random graphs, (2) point matching task using the CMU House image sequence and random point sets, and (3) feature matching using a real image dataset (30 pairs). These three experiments are designed to evaluate the performance of our algorithm (RRWM)[1] on various graph matching tasks and to compare it with other state-of-the-art methods: Spectral Matching (SM)[2], Spectral Matching with Affine Constraints (SMAC)[3], Hyper Graph Matching (HGM)[4], Integer Projected Fixed Point method (IPFP)[5], Graduated Assignment algorithm (GAGM)[6], and Successive Projection Graph Matching (SPGM)[7]. We additionally tested the performance of the random walk matching with conventional row-wise normalization denoted by NRWM. For details, refer to our paper[1].

1. Minsu Cho, Jungmin Lee, Kyoung Mu Lee. "Reweighted Random Walks for Graph Matching", ECCV 2010.

2. M. Leordeanu and M. Hebert. "A Spectral Technique for Correspondence Problems Using Pairwise Constraints", ICCV 2005.

3. T. Cour and P. Srinivasan and J. Shi. "Balanced graph matching", NIPS 2006.

4. R. Zass and A. Shashua. "Probabilistic graph and hypergraph matching", CVPR 2008.

5. M. Leordeanu and M. Herbert. "An Integer Projected Fixed Point Method for Graph Matching and MAP Inference", NIPS 2009.

6. S. Gold and A. Rangarajan. "A Graduated Assignment Algorithm for Graph Matching", PAMI 1996.

7. B. J. van Wyk and M. A. van Wyk. "A pocs-based graph matching algorithm", PAMI 2004.

### Random Graph Matching

In this experiment, following the experimental protocol of previous work, e.g. [6,3], we performed a comparative evaluation on random graph matching problems. For details, refer to our paper.

Outliers on Both Graphs |
||

Outliers on only One Graph |
||

Deformation |
||

Edge Density |
||

### Matching on the CMU House sequence

In this section, we performed feature point matching on the CMU House image sequencewhich has been widely used in the previous work and compared with other methods. For details, refer to our paper.

### Random Point Set Matching

We also performed more general point matching experiment by synthetically generating random point sets.

For this experiment, we followed a conventional point set matching setup . For each trial, two point sets P and Q were generated in 2D domain. As we did in random graph matching problem, n

_{in}points are randomly generated as inlier nodes for graph G

^{P}. Then, we added the Gaussian noise N(0,&sigma

^{2}) for each dimension (x-y coordinates) to construct perturbed graph Q. We also added randomly distributed distracting n

^{P}

_{out}and n

^{Q}

_{out}outlier points for graph G

^{P}and G

^{Q}respectively. We adjusted the domain size to locate 10 points in 256 by 256 area. The graph attribute

**a**

^{P}

_{ij}was defined as the Euclidean distance between the nodes (or the points) v

^{P}

_{i}and v

^{P}

_{j}in graph G

^{P}, and likewise for

**a**

^{Q}

_{ij}. The affinity matrix was calculated by

**W**

_{ia,jb}= exp(- |

**a**

^{P}

_{ij}-

**a**

^{Q}

_{ab}|

^{2}/&sigma

_{s}

^{2}), where the scale factor &sigma

_{s}

^{2}was set to 100.

(a) Outliers |
||

(b) Deformation |
||

_{in}= 20, outliers n

^{P}

_{out}=n

^{Q}

_{out}= 0. For the outlier experiment in Fig.(a), the number of outliers n

^{P}

_{out}=n

^{Q}

_{out}are varied from 0 to 30 by increments of 2, while fixing inlier number n

_{in}= 20, deformation noise &sigma = 0. In both experiments, the best 4 methods, RRWM, GAGM, SPGM, and IPFP, provide comparable results and among them RRWM is better than others. With increasing deformation and outliers, we can see that the performance curves of SM show the similar trends as reported in [2]. Note that as outliers or deformation increases, RRWM, GAGM, SPGM, and IPFP largely outperform other methods such as SM, SMAC, HGM, and NRWM. However, as the point set matching problems are relatively easy, the top-ranked methods do not show large performance gaps between them. Nevertheless, note that our RRWM generates consistently the best performance in accuracy, and is most scalable among the top-ranked methods.

### Real Image Matching

In this experiment we applied our method to challenging real image matching problems using local feature detectors. We constructed a dataset of 30 image pairs containing various images most of which are collected from Caltech-101 and MSRC datasets, and generated candidate correspondences using the MSER detector[2] and the SIFT descriptor[3]. Using the distance of 128-dim SIFT descriptor, all the possible candidate matches were collected if the feature pair has closer distance in SIFT feature space than a loose threshold &delta = 0.6, allowing multiple correspondences for each feature. To measure the dissimilarity between two candidate region correspondences (i,a) and (j,b), we adopted the mutual projection error function d

_{ia;jb}used in [1], and set

**W**

_{ia;jb}= max( 50 - d

_{ia;jb}, 0 ). The ground truths were manually labeled for all candidate correspondences of each image pair, and the accuracy and relative objective score were computed and compared with SM, SMAC, and GAGM.

1. Minsu Cho, Jungmin Lee, Kyoung Mu Lee. "Feature Correspondence and Deformable Object Matching via Agglomerative Correspondence Clustering", ICCV 2009.

2. J. Matas, O. Chum, M. Urban and T. Pajdla. "Robust Wide Baseline Stereo from Maximally Stable Extremal Regions", BMVC 2002.

3. David G. Lowe. "Object Recognition from Local Scale-Invariant Features", ICCV 1999.

The results are shown in the following and summarized in Table.1.

Methods | RRWM |
SM | SMAC | GAGM |

Avg. of accuracy (%) | 64.01 % |
52.08 % | 39.74 % | 58.74 % |

Avg. of relative score (%) | 100 % |
82.41 % | 59.35 % | 92.13 % |

**Table 1**. Matching performance on the real image dataset (30 pairs)

In the following figures, the algorithm, true matches per ground truths, and objective scores are captioned. This experiment and the dataset are designed for producing the challenging feature matching problems where unary local features are very ambiguous. Our RRWM clearly outperforms other methods both in accuracy and objective score as summarized in Table.1. Note that the second best, GAGM was about ten times slower than RRWM in this experiment as similar in the previous experiments.