2001 | OriginalPaper | Buchkapitel
Many-to-many Matching of Attributed Trees Using Association Graphs and Game Dynamics
verfasst von : Marcello Pelillo, Kaleem Siddiqi, Steven W. Zucker
Erschienen in: Visual Form 2001
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 a (derived) “association graph.” This allows us to exploit the full arsenal of clique finding algorithms developed in the algorithms community. However, thus far we have focussed on one-to-one correspondences (isomorphisms), and many-to-one correspondences (homomorphisms). In this paper we present a a general solution for the case of many-to-many correspondences (morphisms) which is of particular interest when the underlying trees reflect real-world data and are likely to contain structural alterations. We define a notion of an ε-morphism 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 morphisms.We then solve the problem by using replicator dynamical systems from evolutionary game theory. We illustrate the power of the approach by matching articulated and deformed shapes described by shock trees.