Grouping with Asymmetric Affinities: A Game-Theoretic Perspective

Pairwise grouping and clustering approaches have tra-ditionally worked under the assumption that the similari-ties or compatibilities between the elements to be grouped are symmetric. However, asymmetric compatibilities arise naturally in many areas of computer vision and pattern recognition. Hence, there is a need for a new generic ap-proach to clustering and grouping that can deal with asym-metries in the compatibilities. In this paper, we present a generic framework for grouping and clustering derived from a game-theoretic formalization of the competition be-tween the hypotheses of group membership, and apply it to perceptual grouping. In the proposed approach groups correspond to evolutionary stable strategies, a classic no-tion in evolutionary game theory. We also provide a com-binatorial characterization of the stable strategies, and, hence, of the elements that belong to a group. Experiments show that our approach outperforms both state-of-the-art clustering-based perceptual grouping approacheswith sym-metric compatibilities, and other approaches explicitly de-signed to make use of asymmetric compatibilities. 1