Ncut: Nyström Normalized Cut

Normalized Cut (Ncut), also known as Spectral Clustering, is a graph-theoretic method for unsupervised data grouping. It analyzes the “spectrum” (eigenvectors) of the data’s similarity graph to find natural clusters.

However, the most powerful part is the spectral embedding. The eigenvectors provide a low-dimensional, smooth coordinate system that reveals the underlying geometry of the data. This embedding maps similar data points close together and dissimilar ones far apart, making it ideal for:

1. Visual Concept Discovery: Finding semantic objects in feature space.
2. Unsupervised Segmentation: Grouping pixels without labels.
3. Data Visualization: Projecting high-dimensional features into 3D for RGB visualization.

Originally introduced by Shi & Malik (2000), it became a foundational algorithm in computer vision for image segmentation. Today, with the rise of powerful feature extractors like DINO and SAM, Normalized Cut is experiencing a renaissance.

Link