Lecture 12: Mean Shift and Normalized Cuts
CAP 5415 Fall 2006

Each Pixel

Data Vector

Example

Once we have vectors…
• Group the vectors into clusters • Algorithms that we talked about last time:
– K-means – EM (Expectation Maximization)

• Today:
(From Comanciu and Meer)

– Mean-Shift – Normalized Cuts

Mean-Shift
• Like EM, this algorithm is built on probabilistic intuitions. • To understand EM we had to understand mixture models • To understand mean-shift, we need to understand kernel density estimation (Take Pattern Recognition!)

Basics of Kernel Density Estimation
• Let’s say you have a bunch of points drawn from some distribution • What’s the distribution that generated these points?

Using a Parametric Model
• Could fit a parametric model (like a Gaussian) • Why:
– Can express distribution with a few number of parameters (like mean and variance)

Non-Parametric Methods
• We’ll focus on kernel-density estimates • Basic Idea: Use the data to define the distribution • Intuition:
– If I were to draw more samples from the same probability distribution, then those points would probably be close to the points that I have already drawn – Build distribution by putting a little mass of probability around each data-point

• Why not:
– Limited in flexibility

Example

Formally

Kernel

• Most Common Kernel: Gaussian or Normal Kernel • Another way to think about it:
(From Tappen – Thesis)

– Make an image, put 1(or more) wherever you have a sample – Convolve with a Gaussian

What is Mean-Shift?
• The density will have peaks (also called modes) • If we started at point and did gradient-ascent, we would end up at one of the modes • Cluster based on which mode each point belongs to

Gradient Ascent?
• Actually, no. • A set of iterative steps can be taken that will monotonically converge to a mode
– No worries about step sizes – This is an adaptive gradient ascent

Results

(x = yj)

Results

Normalized Cuts
• Clustering approach based on graphs • First some background

Graphs
• A graph G(V,E) is a triple consisting of a vertex set V(G) an edge set E(G) and a relation that associates with each edge two vertices called its end points.

Connected and Disconnected Graphs
• A graph G is connected if there is a path from every vertex to every other vertex in G. • A graph G that is not connected is called disconnected graph.

(From Slides by Khurram Shafique)

(From Slides by Khurram Shafique)

Can represent a graph with a matrix a b c e d One Row Per Node

Can add weights to edges

[

0 1 0 0 1

1 0 0 0 0

0 0 0 0 1

0 0 0 0 1

1 0 1 1 0

]
(Based on Slides by Khurram Shafique)

[

0 1 3 ∞ ∞

1 0 4 ∞ 2

3 4 0 6 7

∞ ∞ 6 0 1

∞ 2 7 1 0

]

Adjacency Matrix: W

Weight Matrix: W

(Based on Slides by Khurram Shafique)

Minimum Cut
A cut of a graph G is the set of edges S such that removal of S from G disconnects G. Minimum cut is the cut of minimum weight, where weight of cut is given as

Minimum Cut
• There can be more than one minimum cut in a given graph

• All minimum cuts of a graph can be found in polynomial time1.

H. Nagamochi, K. Nishimura and T. Ibaraki, “Computing all small cuts in an undirected network. SIAM J. Discrete Math. 10 (1997) 469-481.
1

(Based on Slides by Khurram Shafique)

(Based on Slides by Khurram Shafique)

How does this relate to image segmentation?
• When we compute the cut, we've divided the graph into two clusters • To get a good segmentation, the weight on the edges should represent pixels affinity for being in the same group

Affinities for Image Segmentation
Brightness Features

• Interpretation:
– High weight edges for pixels that
(Images from Khurram Shafique)

• Have similar intensity • Are close to each other

Min-Cut won't work though
• The minimum-cut will often choose a cut with one small cluster

We need a better criterion
• Instead of min-cut, we can use the normalized cut

• Basic Idea: Big clusters will increase assoc(A,V), thus decreasing Ncut(A,B)
(Image From Shi and Malik)

Finding the Normalized Cut
• NP-Hard Problem • Can find approximate solution by finding the eigenvector with the second-smallest eigenvalue of this generalized eigenvalue problem

Results

• That splits the data into two clusters • Can recursively partition data to find more clusters • Code available on Jianbo Shi's webpage

Figure from “Normalized cuts and image segmentation,” Shi and Malik, 2000

So what if I want to segment my image?
• Ncuts is a very common solution • Mean-shift is also very popular