📝 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: Heatmap is cosine distance of eigenvectors, w.r.t the mouse pointer. details

Installation

pip install -U ncut-pytorch

Install PyTorch separately if your environment does not already provide it. Predictor examples also need torchvision, and the optional Lightning-based M-space trainer uses pytorch-lightning~=2.0.

Quick Start: Ncut with DINO Features

from ncut_pytorch.predictor import NcutDinov3Predictor
from PIL import Image

predictor = NcutDinov3Predictor(model_cfg="dinov3_vitl16")
predictor = predictor.to('cuda')

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

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

summary

Quick Start: Ncut with Your Features

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

features = torch.rand(1960, 768)
eigvecs = Ncut(n_eig=20).fit_transform(features)  # (1960, 20)

# Color visualizations
rgb_umap = umap_color(eigvecs[:, :20])      # UMAP-based RGB
rgb_mspace = mspace_color(features, n_eig=20)  # M-space RGB

# Discrete segmentation
n_cluster = 10
kway_eigvecs = kway_ncut(eigvecs[:, :n_cluster])
cluster_assignment = kway_eigvecs.argmax(1)
cluster_centroids = kway_eigvecs.argmax(0)

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