Learning Segmentation by Random Walks
Marina Meilă, Jianbo Shi · 2000
We present a new view of image segmentation by pairwise similarities. We interpret the similarities as edge ows in a Markov random walk and study the eigenvalues and eigenvectors of the walk's transition matrix. This interpretation shows that spectral methods for clustering and segmentation have a probabilistic foundation. In particular, we prove that the Normalized Cut method arises naturally from our framework. Finally, the framework provides a principled method for learning the similarity function as a combination of features. 1 Introduction This paper focuses on pairwise (or similarity-based) clustering and image segmentation. In contrast to statistical clustering methods, that assume a probabilistic model that generates the observed data points (or pixels), pairwise clustering de- nes a similarity function between pairs of points and then formulates a criterion (e.g. maximum total intracluster similarity) that the clustering must optimize. The optimality criteria quant...
Cited by 364 works.
Authors
References
- Normalized cuts and image segmentation
- Spectral Graph Theory
- Finite Markov chains
- Authoritative sources in a hyperlinked environment
- Finite Markov Chains.
- Segmentation using eigenvectors: a unifying view
- Contour and Texture Analysis for Image Segmentation
- A factorization approach to grouping
- Feature grouping by 'relocalisation' of eigenvectors of the proximity matrix
- On clusterings-good, bad and spectral