Graph-Theoretic Approach to Clustering and Segmentation

Abstract

We develop a framework for the image segmentation problem based on a new graph-theoretic formulation of clustering. The approach is motivated by the analogies between the intuitive concept of a cluster and that of a dominant set of vertices, a notion that generalizes that of a maximal complete subgraph to edge-weighted graphs. We also establish a correspondence between dominant sets and the extrema of a quadratic form over the standard simplex, thereby allowing us the use of continuous optimization techniques such as replicator dynamics from evolutionary game theory. Such systems are attractive as they can be coded in a few lines of any high-level programming language, can easily be implemented in a parallel network of locally interacting units, and offer the advantage of biological plausibility. We present experimental results on real-world images which show the effectiveness of the proposed approach.