Graphical models for graph matching: Approximate models and optimal algorithms

Comparing scene, pattern or object models to structures in images or determining the correspondence between two point sets are examples of attributed graph matching. In this paper we show how such problems can be posed as one of inference over hidden Markov random fields. We review some well known inference methods studied over past decades and show how the Junction Tree framework from Graphical Models leads to algorithms that outperform traditional relaxation-based ones. (C) 2004 Elsevier B.V. All rights reserved.