# A Sparse Graph Formulation for Efficient Spectral Image Segmentation

arXiv: https://arxiv.org/abs/2306.13166 · HTML: https://mlsanity.com/paper/2306.13166/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 47 references that are in the map.
- First posted on arXiv 22 Jun 2023.

## Builds on (most cited first, 19 of 19)

- [DINOv2: Learning Robust Visual Features without Supervision](https://mlsanity.com/paper/2304.07193/) (2023)
- [Emerging Properties in Self-Supervised Vision Transformers](https://mlsanity.com/paper/2104.14294/) (2021)
- [Image Segmentation Using Deep Learning: A Survey](https://mlsanity.com/paper/2001.05566/) (2020)
- [A Survey on Visual Transformer](https://mlsanity.com/paper/2012.12556/) (2020)
- [Invariant Information Clustering for Unsupervised Image Classification and Segmentation](https://mlsanity.com/paper/1807.06653/) (2018)
- [Localizing Objects with Self-Supervised Transformers and no Labels](https://mlsanity.com/paper/2109.14279/) (2021)
- [Cut and Learn for Unsupervised Object Detection and Instance Segmentation](https://mlsanity.com/paper/2301.11320/) (2023)
- [PiCIE: Unsupervised Semantic Segmentation using Invariance and Equivariance in Clustering](https://mlsanity.com/paper/2103.17070/) (2021)
- [Deep Spectral Methods: A Surprisingly Strong Baseline for Unsupervised Semantic Segmentation and Localization](https://mlsanity.com/paper/2205.07839/) (2022)
- [TokenCut: Segmenting Objects in Images and Videos with Self-supervised Transformer and Normalized Cut](https://mlsanity.com/paper/2209.00383/) (2022)
- [SegSort: Segmentation by Discriminative Sorting of Segments](https://mlsanity.com/paper/1910.06962/) (2019)
- [Unsupervised Learning of Image Segmentation Based on Differentiable Feature Clustering](https://mlsanity.com/paper/2007.09990/) (2020)
- [W-Net: A Deep Model for Fully Unsupervised Image Segmentation](https://mlsanity.com/paper/1711.08506/) (2017)
- [Object Segmentation Without Labels with Large-Scale Generative Models](https://mlsanity.com/paper/2006.04988/) (2020)
- [Finding an Unsupervised Image Segmenter in Each of Your Deep Generative Models](https://mlsanity.com/paper/2105.08127/) (2021)
- [ACSeg: Adaptive Conceptualization for Unsupervised Semantic Segmentation](https://mlsanity.com/paper/2210.05944/) (2022)
- [Scalable Spectral Clustering Using Random Binning Features](https://mlsanity.com/paper/1805.11048/) (2018)
- [Direct Estimation of Appearance Models for Segmentation](https://mlsanity.com/paper/2102.11121/) (2021)
- [Spectral Image Segmentation with Global Appearance Modeling](https://mlsanity.com/paper/2006.06573/) (2020)

## Abstract (arXiv)

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.