Spectral Embedding and Min Cut for Image Segmentation

Abstract

Recently it has been shown that min-cut algorithms can provide perceptually salient image segments when they are given appropriate proposals for source and sink regions. Here we explore the use of random walks and associated spectral embedding techniques for the automatic generation of suitable proposal regions. To do this, we first derive a mathematical connection between spectral embedding and anisotropic image smoothing kernels. We then use properties of the spectral embedding and the associated smoothing kernels to select multiple pairs of source and sink regions for min-cut. This typically provides an over-segmentation, and therefore region merging is used to form the final image segmentation. We demonstrate this process on several sample images. 1