A Sparse Graph Formulation for Efficient Spectral Image Segmentation

Spectral Clustering is one of the most traditional methods for solving segmentation problems. Based on Normalized Cuts, it partitions an image using an objective function defined by a graph. Despite their mathematical attractiveness, spectral approaches have traditionally been neglected by the scientific community because of their practical issues and underperformance. In this paper, we adopt a sparse graph formulation based on the inclusion of extra nodes in a simple grid graph. While the grid encodes the spatial disposition of the pixels, the extra nodes account for the pixel color data. Applying the original Normalized Cuts algorithm to this graph leads to a simple and scalable method for spectral image segmentation, with a rich interpretable solution. Our experiments also show that our proposed methodology overperforms both traditional and modern unsupervised algorithms for segmentation in both real and synthetic data, establishing competitive results for many unsupervised segmentation datasets.