A PAMI/NIPS paper on matching free trees

[Marcello Pelillo]

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