Learning Segmentation by Random Walks

Abstract

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...

Keywords

Affiliated Institutions

• Carnegie Mellon University US
• University of Washington US

Related Publications