A PAMI/NIPS paper on matching free trees
Marcello Pelillo
pelillo at dsi.unive.it
Mon Jan 21 09:07:33 EST 2002
The following paper, accepted for publication in the IEEE Transactions on
Pattern Analysis and Machine Intelligence, is accessible at the following
www site:
http://www.dsi.unive.it/~pelillo/papers/pami-2001.ps.gz
A shorter version of it has just been presented at NIPS*01, and can be
accesses at:
http://www.dsi.unive.it/~pelillo/papers/nips2001.ps.gz
(files are gzipped postscripts)
Comments and suggestions are welcome!
Best regards,
Marcello Pelillo
================================
Matching Free Trees, Maximal Cliques, and Monotone Game Dynamics
Marcello Pelillo
University of Venice, Italy
Abstract
Motivated by our recent work on rooted tree matching, in this paper we
provide a solution to the problem of matching two free (i.e., unrooted)
trees by constructing an association graph whose maximal cliques are in
one-to-one correspondence with maximal common subtrees. We then solve the
problem using simple payoff-monotonic dynamics from evolutionary game
theory. We illustrate the power of the approach by matching articulated
and deformed shapes described by shape-axis trees. Experiments on hundreds
of larger, uniformly random trees are also presented. The results are
impressive: despite the inherent inability of these simple dynamics to
escape from local optima, they always returned a globally optimal
solution.
================================
________________________________________________________________________
Marcello Pelillo
Dipartimento di Informatica
Universita' Ca' Foscari di Venezia
Via Torino 155, 30172 Venezia Mestre, Italy
Tel: (39) 041 2348.440
Fax: (39) 041 2348.419
E-mail: pelillo at dsi.unive.it
URL: http://www.dsi.unive.it/~pelillo
More information about the Connectionists
mailing list