Learning Segmentation by Random Walks

TLDR

The paper proposes a novel perspective on image segmentation based on pairwise similarities. It models similarities as edge flows in a Markov random walk, analyzes the transition matrix’s eigenstructure, and offers a principled way to learn the similarity function from features. The framework demonstrates that spectral clustering and segmentation methods are probabilistically grounded, showing that the Normalized Cut algorithm emerges naturally from this perspective.

Abstract

We present a new view of image segmentation by pairwise similarities. We interpret 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. 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.