Normalized Cuts and Image Segmentation

“Normalized Cuts and Image Segmentation” by Jianbo Shi and Jitendra Malik of the University of California at Berkeley was presented at the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) in 1997, and an extended version appeared in IEEE Transactions on Pattern Analysis and Machine Intelligence in August 2000, by which time Shi had joined Carnegie Mellon University. It treats segmentation as partitioning a weighted pixel graph, proposes the normalized cut as the criterion, and approximates the best partition with a generalized eigenvector. The conference version received the PAMI Technical Committee’s Longuet-Higgins Prize in 2007. This article covers the paper as published, mainly the journal version; the algorithm, its derivation and a worked example are in the normalized cuts article.

Problem

The paper opens with perceptual grouping: Wertheimer had listed factors such as similarity, proximity and good continuation that make parts of a scene group together, but the computational side of grouping was, the authors argue, still unsolved. Two observations shape the paper. First, an image may have no single correct partition; in a Bayesian view several interpretations are plausible, and choosing among them needs prior knowledge, low level (coherent brightness, color, texture, motion) and higher level (objects and their symmetries). Second, partitioning is hierarchical, so a segmenter should return a tree of partitions rather than one flat answer. Low-level cues should propose coarse groups, working “from the big picture downward” in the paper’s words, and leave higher-level knowledge to confirm or refine them.

Earlier graph methods built on minimal spanning trees or limited neighborhoods were efficient, but their criteria depended on local properties of the graph, which the authors judged inadequate for a global impression of the scene. Markov random field and variational formulations, the paper notes, left attractive criteria that greedy or gradient-descent methods cannot globally optimize. Any formulation must say what a good partition is and how to compute it efficiently.

The closest prior work was Wu and Leahy (1993), who, as the paper describes them, clustered data and segmented images by recursively finding minimum cuts, which can be computed exactly. Shi and Malik pointed out, as Wu and Leahy had also noticed, that the minimum cut favors cutting off small sets of isolated nodes; in their Fig. 1, cutting off any single node of the right half costs less than splitting the points into left and right halves.

Contribution

As the paper presents its contributions:

• A global criterion. The normalized cut measures a cut as a fraction of each side’s total connection to the whole graph, so that cutting off a small set is no longer cheap. The authors show that minimizing it is equivalent to maximizing a normalized association within the groups, so the two goals of grouping, dissimilar groups and coherent ones, are satisfied together.
• An efficient approximation. Minimizing the normalized cut exactly is NP-complete, but relaxing the discrete indicator to real values turns it into a generalized eigenvalue problem that sparse solvers handle quickly.
• A grouping algorithm based on that eigenvector, applied to point sets and to brightness, color, texture and motion.
• Connections to spectral graph theory and to other eigenvector-based grouping criteria.

The journal version calls the work, as first presented at CVPR, the first application of spectral partitioning to computer vision.

Method

The paper derives, over a page of algebra, that minimizing Ncut over discrete indicators equals minimizing a Rayleigh quotient $y^\top (D - W) y / y^\top D y$ with two-valued $y$; letting $y$ take real values makes the second smallest generalized eigenvector of $(D - W)y = \lambda D y$ the relaxed solution (derivation in the normalized cuts article). The NP-completeness proof, an appendix credited to Christos Papadimitriou, reduces PARTITION to normalized cuts on a regular grid.

The algorithm weights each edge by a feature-similarity Gaussian times a spatial-proximity Gaussian, zero beyond a radius $r$; solves the sparse eigensystem with the Lanczos method; splits the second eigenvector at the best of $l$ evenly spaced thresholds; and recurses on each part. Recursion stops when the best Ncut exceeds a limit, which thus sets the number of segments, and a stability test skips smoothly varying eigenvectors, using a histogram ratio threshold of 0.06 in all experiments.

The journal version also sketches a simultaneous $k$-way alternative, k-means on several eigenvectors followed by merging or recursively cutting the resulting segments, arguing that it uses information in the higher eigenvectors that the two-way method wastes; all results in the paper still use the recursive two-way algorithm.

The CVPR 1997 version (seven pages) already contains the criterion, the derivation, the Lanczos-based algorithm, the point-set, brightness, color and zebra experiments, and a brief textual comparison with the average cut. Its opening figure, captioned “How many groups?”, is a point set that can be read as four, three or two groups, and its stability test is different: a cut is unstable if moving the splitting point around the optimum barely changes the Ncut. By our comparison of the two texts, the journal version adds the NP-completeness appendix, the motion experiments, the timing section, the $k$-way method, the histogram stability test, the Cheeger-constant bounds, the random-walk and spring–mass interpretations, and the average-association comparison.

Results

The experiments are qualitative figures of segments. The journal version shows:

• Point sets (Fig. 5): two Poisson clusters of different densities.
• Brightness (Figs. 4 and 6–8): the $80 \times 100$ baseball image with $\sigma_I = 0.1$, $\sigma_X = 4$, $r = 5$ and segments of Ncut below 0.04; two noisy synthetic images; and a $126 \times 106$ weather radar image whose ill-defined boundaries, the authors note, would make edge detection perform poorly.
• Color (Fig. 9): a $77 \times 107$ image using HSV-derived features $[v,\ v s \sin h,\ v s \cos h]$.
• Texture (Fig. 10): preliminary results on a zebra, with difference-of-offset-Gaussian filter responses at six orientations and five scales; because the features are orientation-variant, the authors note, skin regions with different stripe orientations should come out as separate segments.
• Motion (Fig. 11): image sequences treated as spatiotemporal graphs, with affinities comparing each pixel’s distribution of image velocity; the authors refer to their ICCV 1998 paper for motion segmentation and tracking.

On timing, the paper reports about 2 minutes for a $100 \times 120$ image on a 200 MHz Intel Pentium, and about 20 seconds for a $300 \times 400$ image with a multiresolution implementation on a 300 MHz Pentium.

The closest thing to an evaluation is Section 6.1, which places the normalized cut between two eigenvector criteria: the average cut, which divides the cut by each side’s number of nodes and is relaxed by the Fiedler vector of $D - W$, and the average association, which rewards tight clusters and corresponds to the largest eigenvectors of $W$, as in Sarkar and Boyer. On 32 one-dimensional points in two groups, with weight functions of three fall-off rates, average association picks out small tight clusters when weights fall off fast, average cut has trouble deciding where to cut when they fall off slowly, and normalized cut partitions correctly in all three cases; on the zebra, average association splits off only small background clusters. Texture regions differ in internal coherence, the authors argue, so tolerance to the weighting function matters.

Impact

The PAMI Technical Committee lists the paper (J. Shi, J. Malik) among the 2007 winners of the Longuet-Higgins Prize, which recognizes CVPR papers from ten years earlier with significant impact on computer vision research; the prize therefore belongs to the CVPR 1997 version.

The relaxation became one of the standard forms of spectral clustering. Ng, Jordan and Weiss (2001), citing the observation that direct $k$-way partitioning beat recursive bipartition, proposed an algorithm that uses $k$ eigenvectors at once. Von Luxburg’s (2007) tutorial names its normalized spectral clustering algorithm with generalized eigenvectors after Shi and Malik (2000), derives it as the relaxation of Ncut, and counts the paper among those that made spectral clustering popular in machine learning.

In vision, Malik, Belongie, Leung and Shi (2001) fed normalized cuts contour and texture affinities; Ren and Malik (2003) used it to produce superpixels; Cour, Bénézit and Shi (2005) made it multiscale, with long-range connections in linear time; and Arbeláez et al. (2011) turned its eigenvectors into a boundary signal for the gPb contour detector (see edge detection).

Limitations

• Hand-set parameters and cues. The results depend on $\sigma_I$, $\sigma_X$, $r$ and the stopping threshold, which the paper sets per experiment (for the radar image, $\sigma_I = 0.007$, $\sigma_X = 15$, $r = 10$). It concedes that defining similarity from cues that may conflict, with weighting that may vary between regions of a textured image, is not trivial.
• Relaxation. The paper notes that higher eigenvectors become unreliable as approximation errors accumulate; von Luxburg (2007) stresses that the relaxation carries no general quality guarantee.
• Cost and locality. Only a sparse $W$ keeps the computation feasible, and Arbeláez et al. note that this limits naive implementations to local affinities.
• Smooth eigenvectors. Arbeláez et al. report that k-means on the eigenvectors breaks up large uniform regions where they vary smoothly; the paper’s recursive algorithm avoided cutting such eigenvectors with its stability test.
• Criterion choice. Ren and Malik (2003), citing normalized cuts among other graph-partitioning frameworks, write that such objectives are typically driven by the designer’s intuition or computational convenience, and set out to learn the criterion from human segmentations instead.
• Qualitative evaluation. The paper reports no benchmark. On BSDS500 boundaries, Arbeláez et al. later measured Cour et al.’s multiscale variant at an ODS F-measure of 0.64, against 0.73 for gPb-owt-ucm.

What Came After

Image segmentation moved toward learned grouping (Ren and Malik, 2003), benchmarks with human ground truth such as BSDS, and later semantic segmentation with convolutional networks, where labels come from a trained classifier rather than graph partitioning. The paper’s ideas survive in spectral clustering, superpixels and hierarchical boundary-based segmenters. Graph cuts took the opposite route, keeping the exactly solvable minimum $s$–$t$ cut and constraining it with user-supplied seeds.