Self-Tuning Spectral Clustering
L. Zelnik-Manor and P. Perona
NIPS 2004
Abstract
Spectral clustering has been theoretically analyzed and empirically proven useful. There are still open issues:
(i) Selecting the appropriate scale of analysis,
(ii) Handling multi-scale data,
(iii) Clustering with irregular background clutter, and,
(iv) Finding automatically the number of groups.
We explore and address all the above issues. We first propose that a `local' scale should be used to compute the affinity
between each pair of points. This local scaling leads to better clustering especially when the data includes multiple scales and when the clusters are placed within a cluttered background. We further suggest exploiting the structure of the eigenvectors to infer automatically the number of groups. This leads to a new algorithm in which the final randomly initialized k-means stage is eliminated.

Paper in pdf

Matlab code and data for synthetic experiments



Experiments:

Image segmentation results, based on gray-scale differences alone. The number of clusters was set manually here to force a large number of clusters. Since the scale is tuned locally for each pixel we obtained segments with both high and low contrast to the surrounding. We compare our result with those obtained using a single scale (set manually) and k-means (algorithm of Jg-Jordan-Weiss). To have a fair comparison we chose a scale which worked well for one of the images and used the same scale for all other images. Both algorithms were asked to provide the same number of clusters. Using a single scale we usually got a smaller number of clusters than asked for as due to low sensitivity some clusters were determined by the final k-means to be redundant.
Our result (self-tuning)
 Single Scale Segmentation
For this image we got good results using both approaches.
image 1 seg result
image 1 NJW result
Recall, we use intensity only and no texture information.
image 2 seg result
 Using the same scale as above failed on this image.
image 2 NJW result
Using local-scaling the high contrast trees as well as the low
contrast windows and building boundaries are detected.
image 3 seg result
Only high contrast boundaries are detected.

image 3 NJW result
image 4 seg result
 image 4 NJW result
Both low contrast and high contrast boundaries are detected.
The sky is over segmented.
image 5 seg result
 The lower contrast round roof boundary was missed.

image 5 NJW result



Experiments on synthetic data

Matlab 7 data
Matlab 6 data

These are fully automatic results: group number and scale recovered automatically!!

synthetic 1synthetic3synthetic 11
synthetic 5synthetic 6synthetic 10
synthetic 7synthetic 8synthetic 9