**Next:**Content
Based Image Retrieval
**Up:**Computer
Vision
**Previous:**Integrating
Descriptions from Multiple
###
Matching Hierarchical Structures
Using Association Graphs

It is well known that the problem of matching two relational structures
can be posed as an equivalent problem of finding a maximal clique in a
(derived) ``association graph.'' However, it is not clear how to apply
this approach to computer vision problems where the graphs are hierarchically
organized, i.e., are trees, since maximal cliques are not constrained to
preserve the partial order. We have provided a solution to the problem
of matching two trees by constructing the association graph using the graph-theoretic
concept of connectivity. We prove that in the new formulation there is
a one-to-one correspondence between maximal cliques and maximal subtree
isomorphisms. This allows us to cast the tree matching problem as an indefinite
quadratic program using the Motzkin-Straus theorem, and we use ``replicator''
dynamical systems developed in theoretical biology to solve it. Such continuous
solutions to discrete problems are attractive because they can motivate
analog and biological implementations. The framework is also extended to
the matching of attributed trees by using weighted association graphs.
We illustrate the power of the approach by matching articulated and deformed
shapes described by shock trees.
*M. Pelillo (University of Venice), K. Siddiqi, S. W. Zucker (Yale
University)*

*Annual Report*

*Mon Jun 26 21:22:20 GMT 2000*