📝 Paper (Coming)

pip install ncut-pytorch

Ncut: Nyström Normalized Cut

Normalized Cut, a.k.a. spectral clustering, is a graphical method to analyze data grouping in the affinity eigenvector space. It has been widely used for unsupervised segmentation in the 2000s.

Nyström Normalized Cut, is a new approximation algorithm developed for large-scale graph cuts, \(O(n)\) time complexity, \(O(1)\) space complexity. Solve million-scale graph in milliseconds.

Video: Ncut applied to image encoder features from Segment Anything Model.
RGB color is 3D spectral-tSNE embedding of Ncut eigenvectors.

Video: hierarchical clustering visualization @preview.ipynb

Installation

pip install -U ncut-pytorch

Quick Start

The input to Ncut is a feature tensor shaped (N, D), where N is the number of points and D is the feature dimension. If you already extracted features from a model, start here.

import torch
from ncut_pytorch import Ncut, kway_ncut
from ncut_pytorch.color import umap_color

features = torch.rand(1960, 768)

ncut = Ncut(n_eig=20)
eigvecs = ncut.fit_transform(features)  # (1960, 20)
eigvals = ncut.eigval

clusters = kway_ncut(eigvecs[:, :10], n_clusters=10).argmax(dim=1)
rgb = umap_color(eigvecs[:, :20])

If you only have images and want a ready-made path, use the DINOv3 predictor. It is just a convenience wrapper around feature extraction, Ncut, and visualization.

from pathlib import Path
from PIL import Image
from ncut_pytorch.predictor import NcutDinov3Predictor

image_dir = Path("examples/images")
images = [Image.open(image_dir / f"view_{i}.jpg") for i in range(4)]

predictor = NcutDinov3Predictor(model_cfg="dinov3_vitl16").to("cuda")
predictor.set_images(images)

image = predictor.summary(n_segments=[10, 25, 50, 100], draw_border=True)
display(image)

summary

paper in prep, Yang 2025

AlignedCut: Visual Concepts Discovery on Brain-Guided Universal Feature Space, Huzheng Yang, James Gee*, Jianbo Shi*,2024

Normalized Cuts and Image Segmentation, Jianbo Shi and Jitendra Malik, 2000