A unifying framework for relational structure matching

The matching of relational structures is a problem that pervades computer vision and pattern recognition research. During the past few decades, two radically distinct approaches have been pursued to tackle it. The first views the matching problem as one of explicit search in state-space. The most popular method within this class consists of transforming it in the equivalent problem of finding a large maximal clique in a derived “association graph.” In the second approach, the relational matching problem is viewed as one of energy minimization. In this paper we provide a unifying framework for relational structure matching which does unify the two existing approaches. The work is centered around a remarkable result proved by Motzkin and Straus (1965) which allows us to formulate the maximum clique problem in terms of a continuous optimization problem. We present a class of continuous- and discrete-time “replicator” dynamical systems developed in evolutionary game theory and show how they can naturally be employed to solve our relational matching problem. Experiments are presented which demonstrate the effectiveness of the proposed approach