Relaxed Cheeger Cut for image segmentation

In this paper, we study and evaluate the application to image segmentation of a p-Laplacian based relaxation of the Cheeger Cut problem. Based on a l¹ relaxation of the initial clustering problem, we show that these methods can outperform usual well-known graph based approaches, e.g., min-cut/max-flow algorithm or l² spectral clustering, for unsupervised and very weakly supervised image segmentation. Experimental results demonstrate the benefits and the relevance of the proposed methodology, especially for a noisy image or when very few pixels are labeled for interactive image segmentation.