Abstract
The matching of hierarchical relational structures is of significant interest in computer vision and pattern recognition. We have recently introduced a new solution to this problem, based on a maximum clique formulation in an (derived) “association graph.” This allows us to exploit the full arsenal of clique finding algorithms developed in the algorithm community. However, thus far we have focused on one-to-one correspondences (isomorphisms), which appears to be too strict a requirement for many vision problems. In this paper, we provide a generalization of the association graph framework to handle many-to-one correspondences. We define a notion of a ?-homomorphism (a many-to-one mapping) between attributed trees, and provide a method of constructing a weighted association graph where maximal weight cliques are in one-to-one correspondence with maximal similarity subtree homomorphisms. We then solve the problem by using replicator dynamical systems from evolutionary game theory.