Graph Matching via Sequential Monte Carlo

Yumin Suh¹, Minsu Cho², and Kyoung Mu Lee¹

¹Department of EECS, ASRI, Seoul National University, Seoul, Korea

²INRIA - WILLOW, École Normale Supérieure, Paris, France

Abstract. Graph matching is a powerful tool for computer vision and machine learning. In this paper, a novel approach to graph matching is developed based on the sequential Monte Carlo framework. By constructing a sequence of intermediate target distributions, the proposed algorithm sequentially performs a sampling and importance resampling to maximize the graph matching objective. Through the sequential sampling procedure, the algorithm effectively collects potential matches under one-to-one matching constraints to avoid the adverse effect of outliers and deformation. Experimental evaluations on synthetic graphs and real images demonstrate its higher robustness to deformation and outliers.

Keywords: graph matching, sequential Monte Carlo, feature correspondence, image matching, object recognition

LNCS 7574, p. 624 ff.

Full article in PDF | BibTeX

lncs@springer.com
© Springer-Verlag Berlin Heidelberg 2012