A Sparse Graph Formulation for Efficient Spectral Image Segmentation
This work addresses the problem of efficient and scalable image segmentation for computer vision applications, offering an incremental improvement over existing spectral methods.
The paper tackled the practical issues and underperformance of spectral clustering for image segmentation by proposing a sparse graph formulation with extra nodes for color data, resulting in a method that outperforms both traditional and modern unsupervised segmentation algorithms on real and synthetic data.
Spectral Clustering is one of the most traditional methods to solve segmentation problems. Based on Normalized Cuts, it aims at partitioning an image using an objective function defined by a graph. Despite their mathematical attractiveness, spectral approaches are traditionally neglected by the scientific community due to their practical issues and underperformance. In this paper, we adopt a sparse graph formulation based on the inclusion of extra nodes to a simple grid graph. While the grid encodes the pixel spatial disposition, 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 an interpretable solution. Our experiments also demonstrate that our proposed methodology over performs both traditional and modern unsupervised algorithms for segmentation in both real and synthetic data.