A classical 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 approach 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, which we solve 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.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Attributed tree matching and maximum weight cliques


    Beteiligte:
    Pelillo, M. (Autor:in) / Siddiqi, K. (Autor:in) / Zucker, S.W. (Autor:in)


    Erscheinungsdatum :

    01.01.1999


    Format / Umfang :

    141721 byte




    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    Attributed Tree Matching and Maximum Weight Cliques

    Pelillo, M. / Siddiqi, K. / Zucker, S. et al. | British Library Conference Proceedings | 1999


    Attributed hypergraph matching on a Riemannian manifold

    Wang, J. M. | British Library Online Contents | 2014


    Extended Attributed String Matching for Shape Recognition

    Chen, S. W. / Tung, S. T. / Fang, C. Y. et al. | British Library Online Contents | 1998


    Region Correspondence by Inexact Attributed Planar Graph Matching

    Wang, C. / Abe, K. / IEEE Computer Society et al. | British Library Conference Proceedings | 1995


    On the Problem of Attributed Relational Graph Matching

    Budin, A. | British Library Online Contents | 1992