Entropy rate superpixel segmentation

By Ming-Yu Liu, Oncel Tuzel, Srikumar Ramalingam, Ramalingam Chellappa. Computer Vision and Pattern Recognition, 2011

1,046 citations recorded by the source corpus.

We propose a new objective function for superpixel segmentation. This objective function consists of two components: entropy rate of a random walk on a graph and a balancing term. The entropy rate favors formation of compact and homogeneous clusters, while the balancing function encourages clusters with similar sizes. We present a novel graph construction for images and show that this construction induces a matroid — a combinatorial structure that generalizes the concept of linear independence in vector spaces. The segmentation is then given by the graph topology that maximizes the objective function under the matroid constraint. By exploiting submodular and mono-tonic properties of the objective function, we develop an efficient greedy algorithm. Furthermore, we prove an approximation bound of ½ for the optimality of the solution. Extensive experiments on the Berkeley segmentation benchmark show that the proposed algorithm outperforms the state of the art in all the standard evaluation metrics.

Subfields: Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/0baa66007d2cfe8e98720310ad0ed7bdee7a873d

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

Superpixel-Based Fast Fuzzy C-Means Clustering for Color Image Segmentation (2019, background): “Fortunately, superpixel [34] is able to address the problem.”
SEEDS: Superpixels Extracted Via Energy-Driven Sampling (2012, methodology): “We use exactly the same metrics as used in [6](2).”
Geo-semantic segmentation (2015, methodology): “In our experiments we apply the entropy rate super-pixel segmentation method introduced in [7].”
Discriminative coupled dictionary hashing for fast cross-media retrieval (2014, methodology): “Denote p A as the distribution of the subgraph membership, p A is formulated as: P The balancing function is deﬁned using the entropy maximum theory: The aforementioned three functions are proved to be mono-tonically increasing and submodular with respect to A [10][7].”
DeepOrgan: Multi-level Deep Convolutional Networks for Automated Pancreas Segmentation (2015, methodology): “After evaluation of several image region generation methods Achanta et al. (2012), we chose entropy rate Liu et al. (2011) to extract N superpixels on axial slices.”
Deep hierarchical parsing for semantic segmentation (2015, methodology): “We use the publicly available implementation of [12] to obtain 100 (same as RCPN) and 800 super-pixels per image for SIFT Flow and Daimler Urban, respectively.”
Spatial aggregation of holistically‐nested convolutional neural networks for automated pancreas localization and segmentation☆ (2017, methodology): “This also results in a simpler overall pancreas localization and segmentation system using HNNs only, rather than the previous hybrid setup involving non-deep- and deep-learning method components ( Roth et al., 2016a ). Lastly, our current method reports an overall improved DSC performance compared ”
Superpixels and Polygons Using Simple Non-iterative Clustering (2017, methodology): “We compare SNIC to the state-of-the-art in superpixel segmentation [13] [16] [17] [18] [28] [30] and the polygonal partitioning to the corresponding state-of-the-art [12].”
Multi-Scale Representation Learning on Proteins (2022, methodology): “…homogeneous clusters, and (ii.) a balancing term encouraging clusters with similar sizes, the entropy rate superpixel (ERS) segmentation algorithm [Liu et al., 2011] outperforms previous methods across different tasks [Stutz et al., 2018] and achieves the desired properties of molecular…”
3D Convolutional Neural Networks for Crop Classification with Multi-Temporal Remote Sensing Images (2018, methodology): “[39] to hyper-pixels, and every 8 × 8 patch sample (16 × 16 patch shown in Figure 11 instead for better vision) is then obtained by the superposition of the corresponding hyper-pixel upon 8 × 8 background template.”
Classification of Hyperspectral Images by Exploiting Spectral–Spatial Information of Superpixel via Multiple Kernels (2015, methodology): “Third, given the superpixel number L, an oversegmentation algorithm called entropy rate superpixel (ERS) [30] is applied on the base images to generate a 2-”
Image Segmentation by Cascaded Region Agglomeration (2013, methodology): “SLIC and ERS have been shown in [1, 14] to outperform other methods, including MeanShift [4], Turbopixels [13], graph-based methods [18, 6, 22], and others [17, 8], on at least some of the data sets, and we do not compare to those methods.”
Lazy Random Walks for Superpixel Segmentation (2014, background): “There are other important superpixel approaches that have been proposed to fulfill the need of increasing applications, such as the algorithms in [20], [21], [24], [27], [28], and [33].”
No More Discrimination: Cross City Adaptation of Road Scene Segmenters (2017, methodology): “Then, we additionally perform superpixel segmentation on the image pair using Entropy Rate Superpixel [17], which would group the nearby pixels into regions while the boundaries of the objects can be properly preserved.”
Regional Multi-Scale Approach for Visually Pleasing Explanations of Deep Neural Networks (2018, methodology): “The superpixel method has the advantage that the number of resulting regions is controllable, thereby enabling multi-scale processing; therefore, we adopt a previously proposed algorithm: entropy rate superpixel segmentation [20].”