Dipartimento di Informatica
Università Ca' Foscari di Venezia
Technical Report Series in Computer Science
CS-99-2
Attributed Tree Matching and Maximum Weight Cliques
M. Pelillo, K. Siddiqi, and S. W. Zucker
Abstract
A classic way of matching relational structures consists of finding a
maximum clique in a derived ``association graph.''
However, it is not clear how to apply this approach to
problems where the graphs are hierarchically organized,
i.e. are trees, since maximum cliques are not constrained to preserve the
partial order.
We have recently provided a solution to this problem
by constructing the association graph using the graph-theoretic concept
of connectivity.
In this paper, we extend the approch to the problem
of matching attributed trees.
Specifically, we show how to derive a ``weighted'' association graph,
and prove that the attributed tree matching problem is equivalent to finding
a maximum weight clique in it.
We then formulate the maximum weight clique problem in terms of a continuous
optimization problem, and show how to solve it
using ``replicator'' dynamical systems developed in theoretical biology.
This formulation is attractive because it
can motivate analog and biological implementations.
We illustrate the power of the
approach by matching articulated and deformed shapes described by shock trees.
Return to technical report list.