Normalized cuts and image segmentation

By Jianbo Shi, Jitendra Malik. 1997

Subfields: Computer Vision and Pattern Recognition

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Vision and Pattern Recognition

Citations in the corpus

InstanceCut: From Edges to Instances with MultiCut (2016, methodology): “More recent methods are based on spectral clustering [47, 1, 3, 26].”
Perceiver: General Perception with Iterative Attention (2021, neutral): “K ¨ ohler 1967; Shi & Malik 2000).”
Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering (2016, background): “And the last step is the graph pooling operation that trades spatial resolution for higher filter resolution.”
Geometric Deep Learning on Graphs and Manifolds Using Mixture Model CNNs (2016, methodology): “ng, considering images as manifolds and employing tools from differential geometry for their processing and analysis. More recent graph-based image processing methods relying on spectral graph theory [46, 40, 61, 29] can be traced back to these works. Manifold learning. A similar trend of employing ”
Local Aggregation for Unsupervised Learning of Visual Embeddings (2019, methodology): “Given the need for cluster-based identification, a variety of alternative approaches to k-means are theoretically possible, including DBSCAN [17], Affinity Propagation [19], spectral methods [63, 66], and gaussian mixtures [60, 61].”
Open-World Instance Segmentation: Exploiting Pseudo Ground Truth From Learned Pairwise Affinity (2022, methodology): “In segmentation literature [3, 60], Oriented Watershed Transform (OWT), globalized contour through Normalized Cut (gPb) [48] and Ultrametric Contour Map (UCM) [2] are also used for grouping from the edge map of an image.”
Per-Pixel Classification is Not All You Need for Semantic Segmentation (2021, neutral): “Then, inspired by early works on non-semantic groupings [11, 33], mask classification-based methods became popular demonstrating the best performance in PASCAL VOC challenges [16].”
Deep Interactive Object Selection (2016, methodology): “Strokebased methods are popular, and use a number of underlying algorithms, including normalized cuts [22], graph cut [2, 11, 26], geodesics [1, 4], the combination of graph cut and geodesics [20, 9] and random walks [8].”
Deep Clustering for Unsupervised Learning of Visual Features (2018, methodology): “Unsupervised learning has been widely studied in the Machine Learning community [19], and algorithms for clustering, dimensionality reduction or density estimation are regularly used in computer vision applications [27, 54, 60].”
Learning Representations for Automatic Colorization (2016, methodology): “These scribble colors are propagated under the assumption that adjacent pixels with similar luminance should have similar color, with the optimization relying on Normalized Cuts [36].”
Cross-Stitch Networks for Multi-task Learning (2016, methodology): “In particular, we select four well established and diverse tasks on different types of image datasets: 1) We pair semantic segmentation [27, 45, 46] and surface normal estimation [11, 18, 52], both of which require predictions over all pixels, on the NYU-v2 indoor dataset [47].”
A Multi-View Embedding Space for Modeling Internet Images, Tags, and Their Semantics (2012, methodology): “Normalized cut (NC) (Ng et al., 2001; Shi and Malik, 2000): For text clustering, the normalized cut model is usually formulated as computing the eigenvectors of”
Semantic Image Segmentation via Deep Parsing Network (2015, background): “Existing works such as [31, 29, 9, 34, 11, 2, 8, 25, 22] can be generally categorized into two groups based on their definitions of the unary and pairwise terms of MRF.”
Weakly Supervised Action Labeling in Videos under Ordering Constraints (2014, methodology): “We compare our method to normalized cuts (or spectral clustering) [31].”
Learning visual groups from co-occurrences in space and time (2015, methodology): “…vision, showing up in the tasks of edge/contour detection Canny (1986); Arbelaez et al. (2011); Isola et al. (2014) , (semantic) segmentation Shi & Malik (2000); Malisiewicz & Efros (2007), and object proposals Alexe et al. (2012); Zitnick & Doll ´ ar (2014); Krahnenbuhl & Koltun (2015),…”
Recognizing indoor scenes (2009, methodology): “In particular, we produce candidate ROIs from a segmentation obtained using graph-cuts [6].”
On the Binding Problem in Artificial Neural Networks (2020, methodology): “One particularly successful approach is the spectral graph-theoretic framework of normalized cuts (Shi and Malik, 2000), which treats image segmentation as a graph-partitioning problem in which nodes are given by pixels and weighted edges reflect the similarity between pairs of (neighboring) pixels.”
Multi-Object Representation Learning with Iterative Variational Inference (2019, background): “…results on real-world images, however, many approaches (such as “semantic seg-mentation” or object detection) rely on supervised signals (Girshick, 2015; He et al., 2017; Redmon & Farhadi, 2018), while others require hand-engineered features (Shi & Malik, 2000; Felzenszwalb & Huttenlocher, 2004).”
Understanding How Dimension Reduction Tools Work: An Empirical Approach to Deciphering t-SNE, UMAP, TriMAP, and PaCMAP for Data Visualization (2020, methodology): “The various methods approach initialization differently: t-SNE uses random values, UMAP applies spectral embedding (Shi and Malik, 1997), and TriMap first runs PCA.”