L. Zelnik-Manor and P. Perona
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
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.
|Recall, we use
intensity only and no texture information.
|Using the same scale as above
failed on this image.
|Using local-scaling the high
contrast trees as well as the low
contrast windows and building boundaries are detected.
|Only high contrast boundaries
|Both low contrast and high
contrast boundaries are detected.
The sky is over segmented.
|The lower contrast round roof
boundary was missed.
Experiments on synthetic data
Matlab 7 data
Matlab 6 data
These are fully automatic results: group number and scale