Learning Segmentation by Random Walks

We present a new view of image segmentation by pairwise similarities. Weinterpret the similarities as edge flows 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. Inparticular, we prove that the Normalized Cut method arises naturally from our framework. Finally, the framework provides aprincipled method for learning the similarity function as a combination of features.