# Image Segmentation Based on Multiscale Fast Spectral Clustering

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Dec 2018.

## Built on by (most cited first, 4 of 4)

- [Image Classification using Graph Neural Network and Multiscale Wavelet Superpixels](https://mlsanity.com/paper/2201.12633/) (2022)
- [A Comprehensive Survey on Spectral Clustering with Graph Structure Learning](https://mlsanity.com/paper/2501.13597/) (2025)
- [On Learning the Structure of Clusters in Graphs](https://mlsanity.com/paper/2212.14345/) (2022)
- [Multiscale Graph Construction Using Non-local Cluster Features](https://mlsanity.com/paper/2411.08371/) (2024)

## Abstract (arXiv)

In recent years, spectral clustering has become one of the most popular clustering algorithms for image segmentation. However, it has restricted applicability to large-scale images due to its high computational complexity. In this paper, we first propose a novel algorithm called Fast Spectral Clustering based on quad-tree decomposition. The algorithm focuses on the spectral clustering at superpixel level and its computational complexity is O(nlogn) + O(m) + O(m^(3/2)); its memory cost is O(m), where n and m are the numbers of pixels and the superpixels of a image. Then we propose Multiscale Fast Spectral Clustering by improving Fast Spectral Clustering, which is based on the hierarchical structure of the quad-tree. The computational complexity of Multiscale Fast Spectral Clustering is O(nlogn) and its memory cost is O(m). Extensive experiments on real large-scale images demonstrate that Multiscale Fast Spectral Clustering outperforms Normalized cut in terms of lower computational complexity and memory cost, with comparable clustering accuracy.