| 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.
|
