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.

1. Introduction

Image Segmentation refers to the problem of grouping image pixels in meaningful regions with the goal of understanding or summarizing the visual content of that image [1]. Because of that, image segmentation has found applications in many domains, such as medical image analysis, autonomous driving, and photo editing, to name a few [1]. This intense industrial appeal led to the development of many algorithms that tackled the problem using variational [2], graphical [3, 4], statistical [5] and, more recently, deep learning techniques [6].