Normalized Cuts

Normalized cuts segment an image by treating its pixels as the nodes of a weighted graph and splitting the graph where the connections between the parts are weak relative to the connections inside them. Shi and Malik (2000) defined the normalized cut criterion, noted that minimizing it exactly is NP-complete, and approximated it by solving a generalized eigenvalue problem. The same relaxation, with several eigenvectors and k-means, became normalized spectral clustering. The image segmentation hub places the method among the other classical ones.

Problem

Partition an image’s pixels, without labels or user input, into groups that are coherent in brightness, color, texture or motion. Shi and Malik framed this as perceptual grouping: capture the global impression of the scene first, then refine it hierarchically.

Inputs and Outputs

• Input: an image, a feature vector $F_i$ for each pixel (intensity, color, filter responses), and an affinity function with its parameters.
• Output: a two-way partition, applied recursively to give a hierarchy of segments, or a $k$-way label map; later methods also use the eigenvectors as features.

Intuition

Build a graph whose nodes are pixels and whose edge weights say how likely two pixels are to belong together. The obvious way to split it is the minimum cut: remove the set of edges with the smallest total weight. Wu and Leahy (1993), as Shi and Malik describe their work, clustered data and segmented images by recursively finding minimum cuts. Shi and Malik pointed out that, as Wu and Leahy had also noticed, the minimum cut favors cutting off small sets of isolated nodes: the cut grows with the number of edges it crosses, so a single pixel with few or weak connections is cheap to separate.

The normalized cut measures the cut as a fraction of each side’s total connection to the graph. Cutting off one pixel then costs 100 percent of its connections, while a cut between two large, well-connected regions costs a small fraction of either side’s.

Algorithm

The recursive two-way algorithm of Shi and Malik (2000):

1. Build a weighted graph $G = (V, E)$ with one node per pixel, connecting pixels within a radius $r$, and form the affinity matrix $W$ and the diagonal degree matrix $D$, $D_{ii} = d_i = \sum_j w_{ij}$.
2. Solve $(D - W)\,y = \lambda D y$ for the eigenvectors with the smallest eigenvalues.
3. Take the eigenvector with the second smallest eigenvalue and threshold it to split the graph in two, choosing the splitting point that minimizes the normalized cut.
4. Check whether the split is stable and its normalized cut is below a preset maximum.
5. If so, recursively partition each part.

Mathematical Formulation

Affinities. For brightness images Shi and Malik used the product of a feature-similarity term and a spatial-proximity term, set to zero beyond a radius $r$:

$$w_{ij} = \begin{cases} \exp\!\left(-\dfrac{\lVert F_i - F_j \rVert_2^2}{\sigma_I^2}\right) \exp\!\left(-\dfrac{\lVert X_i - X_j \rVert_2^2}{\sigma_X^2}\right) & \text{if } \lVert X_i - X_j \rVert_2 < r, \\[2mm] 0 & \text{otherwise,} \end{cases}$$

where $X_i$ is the pixel’s position. This is the same pair of range and spatial Gaussians that weighs neighbors in the bilateral filter.

The criterion. For a partition of $V$ into $A$ and $B$, with $\operatorname{cut}(A,B) = \sum_{u \in A, v \in B} w_{uv}$ and $\operatorname{assoc}(A,V) = \sum_{u \in A, t \in V} w_{ut}$,

$$\operatorname{Ncut}(A,B) = \frac{\operatorname{cut}(A,B)}{\operatorname{assoc}(A,V)} + \frac{\operatorname{cut}(A,B)}{\operatorname{assoc}(B,V)}.$$

Defining the normalized association $\operatorname{Nassoc}(A,B) = \operatorname{assoc}(A,A)/\operatorname{assoc}(A,V) + \operatorname{assoc}(B,B)/\operatorname{assoc}(B,V)$, and using $\operatorname{assoc}(A,V) = \operatorname{assoc}(A,A) + \operatorname{cut}(A,B)$, one gets $\operatorname{Ncut}(A,B) = 2 - \operatorname{Nassoc}(A,B)$: minimizing the dissimilarity between groups and maximizing the similarity within them are the same problem. The paper’s appendix gives a proof, due to Papadimitriou, that minimizing Ncut exactly is NP-complete even for graphs on regular grids, by reduction from the PARTITION problem.

Relaxation. Let $x \in \{1, -1\}^N$ indicate membership in $A$, let $k = \sum_{x_i > 0} d_i / \sum_i d_i$ and $b = k/(1-k)$, and set $y = (\mathbf{1} + x) - b(\mathbf{1} - x)$, so that $y_i \in \{2, -2b\}$. Shi and Malik showed that

$$\min_x \operatorname{Ncut}(x) = \min_y \frac{y^\top (D - W)\, y}{y^\top D\, y}, \qquad y_i \in \{2, -2b\}, \quad y^\top D \mathbf{1} = 0.$$

(The paper writes $\{1, -b\}$; scaling $y$ does not change the quotient.) This is a Rayleigh quotient. Letting $y$ take real values, it is minimized by an eigenvector of the generalized system

$$(D - W)\, y = \lambda D y,$$

equivalently of $D^{-1/2}(D - W)D^{-1/2} z = \lambda z$ with $z = D^{1/2} y$. The smallest eigenvalue is 0, with $y_0 = \mathbf{1}$; the eigenvectors are $D$-orthogonal, so the second smallest, $y_1$, automatically satisfies $y^\top D \mathbf{1} = 0$ and is the real-valued minimizer. It exactly minimizes $\sum_{i,j} (y_i - y_j)^2 w_{ij} / \sum_i y_i^2 d_i$ under that constraint, pushing strongly connected pixels toward similar values, but need not take two values, hence the discretization step.

Spectral graph theory. $D - W$ is the graph Laplacian and $D^{-1/2}(D - W)D^{-1/2}$ Chung’s normalized Laplacian. Shi and Malik also related Ncut to the conductance of a random walk on the pixels. Replacing $D$ by the identity in the denominators gives the average cut, relaxed by the Fiedler vector of $D - W$; the paper argues that it lacks Ncut’s link to within-group association, and reports that Ncut segmented better.

Parameters

• $\sigma_I$ sets how quickly affinity falls with feature difference. The paper says $\sigma$ was typically set to 10–20 percent of the range of the feature distance; for an $80 \times 100$ brightness image with intensities in $[0, 1]$ it used $\sigma_I = 0.1$.
• $\sigma_X$ and $r$ set the spatial reach; the same example used $\sigma_X = 4$ and $r = 5$ pixels. A larger $r$ captures longer-range grouping but makes $W$ denser.
• Splitting point. The split can be at 0, at the median, or at the Ncut-minimizing value; Shi and Malik searched $l$ evenly spaced candidates.
• Stopping and stability. Recursion stops when the best Ncut exceeds a threshold (0.04 and 0.08 in the paper’s examples), which thus controls the number of segments. Eigenvectors that vary smoothly rather than in steps are skipped: the paper histograms the eigenvector values and rejects it when the ratio of the smallest to the largest bin count exceeds 0.06.

Complexity

A full eigendecomposition costs $O(n^3)$ for $n$ pixels. Because $W$ is sparse and only a few low-precision eigenvectors are needed, the paper uses the Lanczos method, which runs in $O(mn)$ for $m$ sparse matrix–vector products of $O(n)$ each. The authors observed $m$ typically below $O(n^{1/2})$, which by this count puts the solve at roughly $O(n^{3/2})$. Randomly removing up to 90 percent of the connections in large neighborhoods did not change the eigenvectors, they report.

Implementation

The NumPy and SciPy code builds a noisy $30 \times 30$ disk image and its sparse affinity matrix with the paper’s formula and parameters ($\sigma_I = 0.1$, $\sigma_X = 4$, $r = 5$). It solves the generalized problem through the symmetric matrix $D^{-1/2} W D^{-1/2}$, whose largest eigenvalues are $1 - \lambda$, and splits the second eigenvector at the best of 30 evenly spaced thresholds. It then compares minimum cuts and segments a three-region image by k-means on three generalized eigenvectors.

import numpy as np
import scipy.sparse as sp
from scipy.sparse.linalg import eigsh
from scipy.sparse.csgraph import maximum_flow, breadth_first_order
from scipy.cluster.vq import kmeans2
from scipy.optimize import linear_sum_assignment

H = W = 30
yy, xx = np.mgrid[0:H, 0:W]
idx = np.arange(H * W).reshape(H, W)

def affinity(img, sigma_i=0.1, sigma_x=4.0, r=5):
    """Sparse W with Shi and Malik's weights: intensity term times distance term, zero beyond r."""
    f = img.ravel()
    rows, cols, vals = [], [], []
    for dy in range(-r + 1, r):
        for dx in range(-r + 1, r):
            d2 = dy * dy + dx * dx
            if d2 == 0 or d2 >= r * r:
                continue
            a = idx[max(0, -dy):H - max(0, dy), max(0, -dx):W - max(0, dx)].ravel()
            b = idx[max(0, dy):H + min(0, dy), max(0, dx):W + min(0, dx)].ravel()   # a shifted by (dy, dx)
            rows.append(a); cols.append(b)
            vals.append(np.exp(-(f[a] - f[b])**2 / sigma_i**2) * np.exp(-d2 / sigma_x**2))
    n = H * W
    return sp.csr_matrix((np.concatenate(vals), (np.concatenate(rows), np.concatenate(cols))), shape=(n, n))

def smallest_eigvecs(Wm, k):
    """First k solutions of (D - W) y = lambda D y, via the symmetric matrix D^-1/2 W D^-1/2."""
    d = np.asarray(Wm.sum(axis=1)).ravel()
    Dm = sp.diags(1 / np.sqrt(d))
    mu, Z = eigsh(Dm @ Wm @ Dm, k=k, which="LA")      # largest mu = 1 - lambda
    order = np.argsort(-mu)
    return 1 - mu[order], Z[:, order] / np.sqrt(d)[:, None], d

def cut(Wm, m):
    return Wm[m][:, ~m].sum()

def ncut(Wm, d, m):
    c = cut(Wm, m)
    return c / d[m].sum() + c / d[~m].sum()

# 1. Two regions: a disk (0.65) on a background (0.35), Gaussian noise 0.05.
rng = np.random.default_rng(0)
gt = (yy - 15)**2 + (xx - 15)**2 <= 8**2
img = np.where(gt, 0.65, 0.35) + rng.normal(0, 0.05, (H, W))
Wm = affinity(img)
lam, Y, d = smallest_eigvecs(Wm, 2)
y = Y[:, 1]                                             # second smallest generalized eigenvector
cands = np.linspace(y.min(), y.max(), 32)[1:-1]         # 30 evenly spaced splitting points
scores = [ncut(Wm, d, y > t) for t in cands]
m = y > cands[int(np.argmin(scores))]
g = gt.ravel()
if (m & g).sum() < (~m & g).sum():
    m = ~m                                              # the eigenvector's sign is arbitrary
print(f"lambda_1 = {abs(lam[0]):.4f}, lambda_2 = {lam[1]:.4f}")
print(f"Ncut split: Ncut {min(scores):.4f}, IoU with the disk {(m & g).sum() / (m | g).sum():.3f}")
print(f"true partition: cut {cut(Wm, g):.2f}, Ncut {ncut(Wm, d, g):.4f}")

# 2. Minimum cut: no partition can cut less than the weakest pixel's degree.
i = int(np.argmin(d))
single = np.zeros(H * W, bool); single[i] = True
print(f"pixel {tuple(int(v) for v in np.unravel_index(i, (H, W)))} alone: cut {d[i]:.2f}, Ncut {ncut(Wm, d, single):.4f}")

#    Minimum s-t cut between a pixel inside the disk and one in the background
#    (max-flow needs integer capacities, so weights are scaled by 1e4).
s, t = idx[15, 15], idx[0, 0]                          # disk center, image corner
cap = sp.csr_matrix((np.round(Wm.data * 1e4).astype(np.int32), Wm.indices, Wm.indptr), shape=Wm.shape)
res = maximum_flow(cap, s, t)
resid = cap - res.flow                                  # residual capacities
resid.data[resid.data < 0] = 0; resid.eliminate_zeros()
side = np.zeros(H * W, bool); side[breadth_first_order(resid, s, return_predecessors=False)] = True
print(f"min s-t cut: value {res.flow_value / 1e4:.2f}, source side {side.sum()} px, "
      f"IoU with the disk {(side & g).sum() / (side | g).sum():.3f}")

# 3. Three regions, k-way: k-means on the first three generalized eigenvectors.
lab = np.zeros((H, W), int)
lab[(yy - 10)**2 + (xx - 10)**2 <= 6**2] = 1            # disk
lab[16:27, 14:27] = 2                                   # square
img3 = np.choose(lab, [0.2, 0.5, 0.8]) + rng.normal(0, 0.05, (H, W))
W3 = affinity(img3)
lam3, Y3, d3 = smallest_eigvecs(W3, 3)
print("three regions: lambda", np.round(np.abs(lam3), 4))
_, km = kmeans2(Y3, 3, minit="++", seed=1)
conf = np.array([[((km == a) & (lab.ravel() == b)).sum() / ((km == a) | (lab.ravel() == b)).sum()
                  for b in range(3)] for a in range(3)])
r_, c_ = linear_sum_assignment(-conf)                   # match clusters to regions
print("per-region IoU", np.round(conf[r_, c_][np.argsort(c_)], 3))

Output:

lambda_1 = 0.0000, lambda_2 = 0.0035
Ncut split: Ncut 0.0041, IoU with the disk 1.000
true partition: cut 12.94, Ncut 0.0041
pixel (15, 28) alone: cut 1.35, Ncut 1.0001
min s-t cut: value 10.33, source side 899 px, IoU with the disk 0.219
three regions: lambda [0.     0.0001 0.0055]
per-region IoU [0.998 0.991 1.   ]

The thresholded eigenvector recovers the disk exactly (IoU 1.000, Ncut 0.0041). Since the relaxation minimizes the same quotient over a larger set, $\lambda_2 = 0.0035$ is a lower bound on the Ncut of any two-way partition. The minimum cut prefers something else. Cutting out the disk costs 12.94, but the background pixel at row 15, column 28, which noise pushed to 0.155, has a total connection of only 1.35, so the global minimum cut cannot be the disk boundary; isolating that pixel has Ncut 1.0001, about 240 times the disk’s. The $s$–$t$ cut fares no better: the corner pixel has few neighbors within $r$, so isolating it (10.33) is cheaper than cutting around the disk.

With three regions the generalized eigenvalues are 0, 0.0001 and 0.0055, and k-means on the three eigenvectors separates background, disk and square with per-region IoU of at least 0.991. Over noise seeds 0–9, the two-way IoU was 0.995–1.000 and the three-region IoUs at least 0.991; the weakest pixel always cut less than the disk boundary (by factors of 1.9 to 9.6), and the $s$–$t$ cut isolated the corner in 8 of 10 runs.

Properties and Behavior

• No bias toward tiny segments. Isolating a single pixel costs an Ncut above 1, as the example shows.
• Global but approximate. The eigenvector depends on the whole graph, but the relaxation carries no general quality guarantee. Von Luxburg (2007) stresses this and reports Guattery and Miller’s “cockroach” graphs, on which unnormalized spectral clustering (the relaxation of RatioCut, see Variants) returns a RatioCut worse than the optimum by a factor proportional to the number of vertices.
• Higher eigenvectors. Later eigenvectors can subdivide the parts further, but the paper found them unreliable, because approximation error accumulates under the orthogonality constraint, and recommends recomputing on each part.

Limitations

• Affinity design. Results depend on the features and on $\sigma_I$, $\sigma_X$ and $r$; the paper notes that combining conflicting cues, and weighting every region of a textured image well, is not trivial.
• Bias toward balanced partitions. Shi and Malik describe Ncut, like the average cut, as seeking a “balanced partition”. By our reasoning from the criterion, the normalization which removes the small-set bias also rewards splits with comparable total connection on each side, so a small but distinct object can lose to a split through a large, weakly varying region.
• Cost. Large images remain slow even with sparse Lanczos solvers, and the sparsity that makes them feasible limits affinities to short range.

Variants

• Simultaneous $k$-way cuts. Shi and Malik also described clustering pixels by k-means on several eigenvectors into an oversegmentation, then greedily merging segments to minimize a $k$-way Ncut, $\sum_i \operatorname{cut}(A_i, V - A_i)/\operatorname{assoc}(A_i, V)$, or recursively cutting the condensed graph of segments; the paper’s results all use the recursive two-way version.
• Spectral clustering. Ng, Jordan and Weiss (2001) stacked the $k$ largest eigenvectors of $D^{-1/2} A D^{-1/2}$, normalized each row to unit length, and ran k-means on the rows, with Gaussian affinities whose $\sigma$, in their experiments, was chosen as the value giving the tightest clusters. Von Luxburg (2007) shows that relaxing Ncut leads to the eigenvectors of the random-walk Laplacian $L_{\text{rw}} = I - D^{-1}W$, which are Shi and Malik’s generalized eigenvectors, while relaxing RatioCut, which measures each side by its number of vertices, leads to the unnormalized Laplacian $D - W$. She advocates $L_{\text{rw}}$ over both $D - W$ and $L_{\text{sym}} = I - D^{-1/2} W D^{-1/2}$.
• Contour and texture cues. Malik, Belongie, Leung and Shi (2001) combined intervening-contour and texton affinities, gated by local texturedness, oversegmented by k-means on eigenvectors 2–12, and finished with recursive two-way cuts on the graph of segments.
• Multiscale normalized cuts. Cour, Bénézit and Shi (2005) decomposed the graph into sparse affinity matrices at several scales linked by cross-scale constraints, capturing long-range connections with running time linear in the number of pixels.
• Spectral boundaries in gPb. Arbeláez et al. (2011) observed that k-means on the eigenvectors breaks up large uniform regions. Instead they take oriented derivatives of 16 generalized eigenvectors, weighted by $1/\sqrt{\lambda_k}$, as a “spectral” boundary signal, sPb, combined with local cues in the gPb contour detector behind the gPb-owt-ucm hierarchy (see edge detection). In their boundary benchmark on BSDS500 (Table 1), multiscale normalized cuts reached an ODS F-measure of 0.64 against 0.73 for gPb-owt-ucm.

Graph cuts take the opposite route: they keep the minimum $s$–$t$ cut, which can be computed exactly, and, for interactive segmentation, constrain it with user-supplied seeds and an energy with region and boundary terms.