Attributed tree homomorphism using association graphs

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 only focussed 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 an ε-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 the evolutionary game theory