Dominant Sets and Pairwise Clustering Dominant Sets and Pairwise Clustering

(1)

Dominant Sets and Pairwise Clustering Dominant Sets and Pairwise Clustering

tra)(k

Marcello Pelillo Marcello Pelillo

Computer Vision and Pattern Recognition Group Computer Vision and Pattern Recognition Group

Dipartimento di Informatica Dipartimento di Informatica Universit

Universitàà CaCa’’ Foscari, VeneziaFoscari, Venezia

joint work with Massimiliano Pavan

(2)

Talk Talk ’ ’ s Outline s Outline

Dominant sets and their characterization

Evolutionary game dynamics for clustering

Experiments on intensity/color/texture image segmentation

Extension of the framework to hierarchical clustering

Experiments on the (hierarchical) organization of an image database

(3)

The (Pairwise) Clustering Problem The (Pairwise) Clustering Problem

Given:

- a set of n “objects”

- an n × n matrix of pairwise similarities Goal:

Goal: Partition the input objects into maximally homogeneous groups (i.e., clusters).

(4)

Applications Applications

Clustering problems abound in many areas of computer science and engineering.

A short list of applications domains:

Image processing and computer vision Computational biology and bioinformatics Information retrieval

Data mining

Signal processing Machine learning

…

(5)

What is a Cluster?

No universally accepted definition of a “cluster”.

Informally, a cluster should satisfy two criteria:

Internal criterion

Internal criterion: all objects inside a cluster should be highly similar to each other.

External criterion:

External criterion: all objects outside a cluster should be highly dissimilar to the ones inside.

(6)

Clustering as a Graph

Clustering as a Graph - - Theoretic Problem Theoretic Problem

(7)

An Illustrative Example: The Binary Case An Illustrative Example: The Binary Case

Suppose the similarity matrix is a binary matrix.

In this case, the notion of a cluster coincide with that of a maximal clique.

Given an unweighted undirected graph G=(V,E):

A clique is a subset of mutually adjacent vertices

A maximal clique is a clique that is not contained in a larger one

How to generalize the notion of a maximal clique to weighted graphs?

(8)

Basic Definitions Basic Definitions

j i

S

(9)

Assigning Node Weights / 1 Assigning Node Weights / 1

S

j i S - { i }

(10)

Assigning Node Weights / 2

(11)

Dominant Sets

(12)

From Dominant Sets to Local Optima From Dominant Sets to Local Optima

(and Back) / 1

(13)

The Standard Simplex The Standard Simplex

(when

(when n n = 3) = 3)

(14)

From Dominant Sets to Local Optima From Dominant Sets to Local Optima

(and Back) / 2 (and Back) / 2

Generalization of Motzkin-Straus theorem from graph theory

(15)

Talk Talk ’ ’ s Outline s Outline

Evolutionary game dynamics for clusteringEvolutionary game dynamics for clustering

(16)

Replicator Equations

(17)

The Fundamental Theorem of Natural Selection

(18)

Grouping by Replicator Equations

(19)

A MATLAB Implementation

(20)

Characteristic Vectors

(21)

Separating Structure for Clutter

(22)

(23)

Separating Structure from Clutter

(24)

(25)

Talk Talk ’ ’ s Outline s Outline

Experiments on intensity/color/texture image Experiments on intensity/color/texture image segmentation

segmentation

(26)

Image Segmentation Image Segmentation

Image segmentation problem:

Decompose a given image into segments, i.e. regions containing

“similar” pixels.

First step in many

computer vision problems

Example: Segments might be regions of the image depicting the same object.

Semantics Problem: How should we infer objects from segments?

(27)

Image Segmentation

(28)

Experimental Setup

(29)

Intensity Segmentation Results Intensity Segmentation Results

Dominant sets Ncut

(30)

Intensity Segmentation Results Intensity Segmentation Results

(97 x 115) (97 x 115)

Dominant sets Ncut

(31)

Color Segmentation Results Color Segmentation Results

(125 x 83) (125 x 83)

Original image Dominant sets Ncut

(32)

Texture Segmentation Results Texture Segmentation Results

(approx. 90 x 120)

(33)

Ncut Results

(34)

Dealing with Large Data Sets

(35)

Grouping Out

Grouping Out - - of of - - Sample Data Sample Data

(36)

(37)

(38)

Results on Berkeley Database Images Results on Berkeley Database Images

(321 x 481)

(39)

Results on Berkeley Database Images Results on Berkeley Database Images

(321 x 481)

(40)

Capturing Elongated Structures / 1

(41)

Capturing Elongated Structures / 2

(42)

“ “ Closing Closing ” ” the Similarity Graph the Similarity Graph

Basic idea

Basic idea: Trasform the original similarity graph G into a “closed”

version thereof (G_closed), whereby edge-weights take into account chained (path-based) structures.

Unweighted (0/1) case:

G_closed = Transitive Closure of G

Note:

Note: G_closed can be obtained from:

A + A²+ … + Aⁿ

(43)

Weighted Closure of Weighted Closure of G G

Observation

Observation: When G is weighted, the ij-entry of A^k represents the sum of the total weights on the paths of length k between vertices i and j.

Hence, our choice is:

A_closed = A + A²+ … + Aⁿ

(44)

Example: Without Closure (

Example: Without Closure ( σ σ = 2) = 2)

(45)

Example: Without Closure (

Example: Without Closure ( σ σ = 4) = 4)

(46)

Example: Without Closure (

Example: Without Closure ( σ σ = 8) = 8)

(47)

Example: With Closure (

Example: With Closure ( σ σ = 0.5) = 0.5)

(48)

(49)

Grouping Edge Elements Grouping Edge Elements

Here, the elements to be grouped are edgels (edge elements).

We used Herault/Horaud (1993) similarities, which combine the following four terms:

1. Co-circularity 2. Smoothness 3. Proximity 4. Contrast

Comparison with Mean-Field Annealing (MFA).

(50)

(51)

(52)

(53)

(54)

Talk Talk ’ ’ s Outline s Outline

Extension of the framework to hierarchical clusteringExtension of the framework to hierarchical clustering

(55)

Building a Hierarchy:

A Family of Quadratic Programs

(56)

An Observation

(57)

The effects of α

(58)

Bounds for the Regularization Parameter / 1

(59)

Bounds for the Regularization Parameter / 2

(60)

Bounds for the Regularization Parameter / 3

(61)

The Landscape of

The Landscape of f f

_α_α

(62)

Sketch of the Hierarchical Clustering Algorithm

(63)

Pseudo

Pseudo - - code of the Algorithm code of the Algorithm

(64)

Results on the IRIS dataset / 1

(65)

Results on the IRIS dataset / 2

(66)

Luo and Hancock

Luo and Hancock ’ ’ s Similarities (CVPR s Similarities (CVPR ’ ’ 01) 01)

(67)

Klein and Kimia

Klein and Kimia ’ ’ s Similarities (SODA s Similarities (SODA ’ ’ 01) 01)

(68)

Gdalyahu and Weinshall

Gdalyahu and Weinshall ’ ’ s Similarities (PAMI 01) s Similarities (PAMI 01)

(69)

Factorization Results

(Perona and Freeman, 98)

(70)

Typical-cut Results (From Gdalyahu, 1999)

(71)

Conclusions

(72)

On On - - going and Future Projects going and Future Projects

Grouping with asymmetric affinities: Game theoryGrouping with asymmetric affinities: Game theory

Clustering on hypergraphs (high-Clustering on hypergraphs (high-order relations)order relations)

Graph matching, object recognition and trackingGraph matching, object recognition and tracking

Video segmentationVideo segmentation

(73)

Other Applications of Dominant

Other Applications of Dominant - - Set Clustering Set Clustering

Bioinformatics Bioinformatics

Identification of protein binding sites Identification of protein binding sites

R. Zauhar, M. Bruist, Univ. of Sciences Philadelphia, USA (2005) Clustering gene expression profiles

Clustering gene expression profiles

T. Li et al, Fudan University, Hong Kong (2005) Security and video surveillance

Security and video surveillance

Detection of anomalous activities in video streams Detection of anomalous activities in video streams

R. Hamid et al., Georgia Institute of Tehcnology, USA (2005) Detection of malicious activities in the internet

Detection of malicious activities in the internet F. Pouget, Insitut Eurécom (2006)

Content

Content-based image retrieval-based image retrieval

G. Giacinto, F. Roli, University of Cagliari, Italy (2007)

(74)

References References

M. Pavan, M. Pelillo. A new graph-theoretic approach to clustering and

segmentation. Proc. IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Madison, WI, 2003.

M. Pavan, M. Pelillo. Dominant sets and hierarchical clustering. Proc. IEEE International Conference on Computer Vision, Nice, France, 2003.

M. Pavan, M. Pelillo. Efficient out-of-sample extension of dominant-set clusters.

In: Advances in Neural Information Processing Systems 17 (MIT Press, 2005).

A. Torsello, S. Rota Bulo’, M. Pelillo.Grouping with asymmetric affinities: A game-theoretic perspective. Proc. IEEE Computer Society Conference on Computer Vision and Pattern Recognition, New York, NY, 2006.

M. Pavan, M. Pelillo. Dominant sets and pairwise clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence 29(1):167-172, 2007.