Home | Search | Help  
Home Page Università di Genova

Seminar Details


Date 4-12-2003
Time 14:30
Room/Location Sala congressi 3 piano
Title A New Graph-Theoretic Framework for Pairwise Data Clustering
Speaker Prof. Marcello Pelillo
Affiliation Dipartimento di Informatica -Universita' Ca' foscari di Venezia
Link http://www.dsi.unive.it/~pelillo/
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 novel 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 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. Moreover, in many computer vision applications, such as the organization of an image database, it is important to provide the data to be clustered with a hierarchical organization, and it is not clear how to do this within the dominant set framework. In the second part of the talk we address precisely this problem, and present a simple and elegant solution to it. To this end, we consider a family of (continuous) quadratic programs which contain a parameterized regularization term that controls the global shape of the energy landscape. When the regularization parameter is zero the local solutions are known to be in one-to-one correspondence with dominant sets, but when it is positive an interesting picture emerges. We determine bounds for the regularization parameter that allow us to exclude from the set of local solutions those inducing clusters of size smaller than a prescribed threshold. This suggests a new (divisive) hierarchical approach to clustering, which is based on the idea of properly varying the regularization parameter during the clustering process. We apply the proposed framework to the problem of organizing a shape database. Experiments with three different similarity matrices (and databases) reported in the literature have been conducted, and the results confirm the effectiveness of our approach.
Back to Seminars