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 2013Datasets
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.
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, nin points are randomly generated as inlier nodes for graph GP. Then, we added the Gaussian noise N(0,&sigma2) for each dimension (x-y coordinates) to construct perturbed graph Q. We also added randomly distributed distracting nPout and nQout outlier points for graph GP and GQ respectively. We adjusted the domain size to locate 10 points in 256 by 256 area. The graph attribute aPij was defined as the Euclidean distance between the nodes (or the points) vPi and vPj in graph GP, and likewise for aQij. The affinity matrix was calculated by Wia,jb = exp(- |aPij - aQab |2/&sigmas2), where the scale factor &sigmas2 was set to 100.
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 dia;jb used in [1], and set Wia;jb = max( 50 - dia;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 % |
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.