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.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Attributed tree matching and maximum weight cliques


    Contributors:
    Pelillo, M. (author) / Siddiqi, K. (author) / Zucker, S.W. (author)


    Publication date :

    1999-01-01


    Size :

    141721 byte




    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



    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