PaperlayerView exact revision on arXiv

Source-linked AI summary

Superpixels: An Evaluation of the State-of-the-Art

David Stutz, Alexander Hermans, Bastian Leibe

arXiv:1612.01601v3cs.CV

TL;DR

Existing superpixel comparisons lacked a unifying, fair benchmark despite widespread use and many algorithms. The paper evaluates 28 algorithms across five datasets with optimized parameters, enforced connectivity and count-independent metrics, producing an overall ranking and practical recommendations.

  • Problem

    Widespread adoption and varying experimental setups made fair comparison and algorithm selection difficult.

  • Method

    The authors benchmark 28 algorithms across five datasets using optimized parameters, strict connectivity enforcement, multiple metrics, robustness tests and runtime analysis.

  • Results

    The evaluation produces an overall ranking and identifies six stable algorithms recommended for practice: ETPS, SEEDS, ERS, CRS, ERGC and SLIC.

  • Takeaways & Limitations

    The benchmark enables application-oriented selection among superpixel algorithms and provides implementations for comparison and use.

  • Takeaways & Limitations

    The tested algorithms’ generated-superpixel counts can depend strongly on other parameters, and VCCS is harder to control because it operates on point clouds before image-plane backprojection.

Abstract

from arXiv · show

Superpixels group perceptually similar pixels to create visually meaningful entities while heavily reducing the number of primitives for subsequent processing steps. As of these properties, superpixel algorithms have received much attention since their naming in 2003. By today, publicly available superpixel algorithms have turned into standard tools in low-level vision. As such, and due to their quick adoption in a wide range of applications, appropriate benchmarks are crucial for algorithm selection and comparison. Until now, the rapidly growing number of algorithms as well as varying experimental setups hindered the development of a unifying benchmark. We present a comprehensive evaluation of 28 state-of-the-art superpixel algorithms utilizing a benchmark focussing on fair comparison and designed to provide new insights relevant for applications. To this end, we explicitly discuss parameter optimization and the importance of strictly enforcing connectivity. Furthermore, by extending well-known metrics, we are able to summarize algorithm performance independent of the number of generated superpixels, thereby overcoming a major limitation of available benchmarks. Furthermore, we discuss runtime, robustness against noise, blur and affine transformations, implementation details as well as aspects of visual quality. Finally, we present an overall ranking of superpixel algorithms which redefines the state-of-the-art and enables researchers to easily select appropriate algorithms and the corresponding implementations which themselves are made publicly available as part of our benchmark at davidstutz.de/projects/superpixel-benchmark/.

1. Introduction

Superpixels group perceptually similar pixels into meaningful entities while reducing the primitives processed by later algorithms. This paper establishes a fair benchmark for comparing their growing range of algorithms and applications.

  • Motivation: Superpixels group pixels with similar color and low-level properties into perceptually meaningful entities, reducing the number of primitives for subsequent processing.They address pixel discretization and the computational burden of processing many pixels in large images.
  • Adoption: Superpixels have been applied to tracking, stereo, 3D reconstruction, saliency, detection, depth estimation, semantic segmentation, scene understanding, optical flow and related tasks.The paper lists these applications as evidence of broad adoption in computer vision.
  • Scope: The paper treats algorithms offering control over the number of generated superpixels as superpixel algorithms, distinguishing them from oversegmentation methods without that control.The authors note that the boundary between the two categories is generally difficult to define.
  • Requirements: Common requirements include partitioning, connectivity, boundary adherence, compactness, regularity, smoothness, efficiency and a controllable number of superpixels.These requirements describe both segmentation validity and practical usability.
  • Benchmark: The benchmark evaluates 28 algorithms on 5 datasets across visual quality, performance, runtime, implementation details and robustness to noise, blur and affine transformations.Parameters are optimized on separate training sets, connectivity is enforced, and integrated metrics summarize performance independently of superpixel count.

3. Algorithms

The evaluation organizes the tested methods by high-level algorithmic approach, revealing distinct trade-offs in controllability, compactness and connectivity handling. Categories include watershed-, density-, graph-, contour-, path-, clustering- and energy-based methods.

  • Categorization: The benchmark categorizes algorithms by high-level approach to make the large set of evaluated methods easier to compare.The categories are based on the algorithms’ core processing strategies.
  • Density-based: Density-based methods perform mode-seeking in a computed density image, but usually cannot control the number or compactness of superpixels.EAMS and QS are given as examples, and are therefore categorized as oversegmentation algorithms.
  • Graph-based: Graph-based methods partition an undirected image graph using edge weights, with approaches differing in whether they merge, cut or eliminate regions.FH, ERS and POISE merge bottom-up; NC and CIS use cuts; PB uses elimination.
  • Path-based: Path-based methods connect seed points through pixel paths, making the number of superpixels controllable while usually lacking compactness control.PF uses discrete image gradients, whereas TPS uses edge detection.
  • Clustering-based: Clustering-based methods use color, spatial and sometimes depth information to control superpixel number and compactness, but require post-processing to enforce connectivity.DASP is an example using depth information.
  • Energy optimization: Energy-optimization methods iteratively exchange pixels between neighboring grid-initialized superpixels, while controlling number, compactness and early termination.The formulation optimizes an energy over successive region exchanges.

4. Datasets

The benchmark uses five datasets spanning indoor, outdoor and person images, selected for common applications and available pixel-level annotations. The authors caution that natural-image coverage may underrepresent specialized domains.

  • Dataset selection: The benchmark evaluates two indoor datasets, two outdoor datasets and one person dataset selected to reflect common applications with large pixel-level annotations.The datasets are BSDS500, SBD, NYUV2, SUNRGBD and Fash.
  • Scope: Because the benchmark focuses on natural images, specialized domains such as medical imaging may not be represented well.This is an explicit scope boundary of the dataset selection.
  • BSDS500: BSDS500 contains 500 outdoor images with at least 5 high-quality ground-truth segmentations per image, evaluated across all available segmentations.For each image and metric, the ground-truth segmentation producing the worst score is selected for averaging.
  • SBD: SBD contains 715 varied outdoor images whose scenes are generally more complex than BSDS500, often including multiple foreground objects or no clear foreground.Its semantic ground truth is pre-processed to ensure connected segments.
  • Indoor datasets: NYUV2 and SUNRGBD provide indoor RGB-depth imagery, with 1449 and 10335 images respectively, while their ground truth is lower quality or pre-processed compared with BSDS500.SUNRGBD combines data from multiple devices and excludes images originating from NYUV2.
  • Fash: Fash contains 685 full-body fashion-blogger images with varied backgrounds and semantic ground truth pre-processed to ensure connected segments.The dataset was previously used for clothes parsing.

5. Benchmark

The benchmark evaluates boundary adherence, leakage, explained variation, compactness, and achievable segmentation accuracy, then aggregates key metrics across superpixel counts for number-independent comparison.

  • Metrics: Boundary Recall measures boundary adherence against ground truth, with higher values indicating better adherence.Boundary pixels are matched within a neighborhood whose radius is 0.0025 times the image diagonal, rounded upward.
  • Metrics: Undersegmentation Error measures superpixel leakage across nearby ground-truth segments, so lower values indicate less leakage.The benchmark uses UENP, while related formulations differ in their treatment of overlap and metric range.
  • Metrics: Explained Variation quantifies image variation explained by superpixels without ground truth, with higher values indicating better performance.It uses the mean colors of each superpixel and the whole image.
  • Metrics: Compactness compares each superpixel’s area with the area of a circle having the same perimeter, with higher values preferred.The circle is treated as the most compact two-dimensional shape.
  • Metrics: 53?
  • Number-independent evaluation: AMR, AUE, and AUV integrate miss rate, undersegmentation error, and unexplained variation over K = 200–5200, enabling number-independent comparison.Lower values are better, and the aggregated metrics support side-by-side comparison across datasets.

6. Parameter Optimization

The benchmark optimizes parameters for fair comparison while accounting for connectivity and the number of generated superpixels. These choices expose trade-offs among performance, runtime, and compactness.

  • Parameter optimization: Parameters are optimized on separate training sets using discrete grid search that jointly minimizes (1 − Rec) + UE.The procedure addresses categorical, integer, and runtime-varying parameters.
  • Controlling the number of generated superpixels: Several algorithms require constraints because parameters other than the target setting strongly influence the number of generated superpixels.This dependence is demonstrated for LSC, CIS, VC, CRS, and PB, including after connectivity enforcement.
  • Controlling the number of generated superpixels: Oversegmentation algorithms without direct superpixel-count control are tuned through approximate parameter relationships or broad parameter searches.EAMS and QS permit rough control, whereas FH is evaluated over many combinations to approach the desired count.
  • Connectivity: Connectivity is strictly enforced by relabeling each connected component as a separate superpixel, with additional merging for implementations producing many tiny components.The procedure compensates for implementations that do not ensure connected superpixels.
  • Performance trade-offs: More iterations usually increase Rec and runtime, while higher compactness CO usually lowers Rec; joint optimization therefore favors higher runtime and lower compactness.Most algorithms achieve reasonable Rec with about 3–10 iterations, but optimization with respect to Rec and UE favors more iterations.

7. Experiments

The experiments evaluate visual quality and quantitative performance across superpixel algorithms, showing trade-offs among boundary adherence, compactness, regularity, and smoothness. Proposed aggregate and stability analyses complement ground-truth metrics and expose algorithmic differences across datasets and operating conditions.

  • Qualitative evaluation: Visual quality balances boundary adherence against compactness, regularity, and smoothness, reflecting abstraction from versus sensitivity to low-level image content.The relative importance of these properties depends on the application.
  • Qualitative evaluation: Most algorithms adhere well to important image boundaries at large K, while FH, QS, CIS, PF, PB, TPS, TP, and SEAW show inferior adherence.EAMS is the only evaluated oversegmentation algorithm demonstrating adequate boundary adherence.
  • Qualitative evaluation: A compactness parameter enables a gradual trade-off between boundary adherence and compactness, but compactness does not guarantee regularity or smooth boundaries.SLIC, VC, and CCS illustrate cases where compactness is combined with regular arrangement, whereas other algorithms separate these properties.
  • Qualitative evaluation: Clustering-based, contour-evolution, and iterative-energy algorithms mostly provide good visual quality, whereas path-based, density-based, and oversegmentation algorithms perform poorly.Graph-based algorithms show mixed results, and strong boundary adherence can come at the cost of compactness, regularity, or smoothness.
  • Quantitative evaluation: Stability measures based on min Rec, max UE, and min EV identify algorithms whose performance changes monotonically with K, while variation in generated superpixel counts often relates to poorer metric performance.ETPS, ERGC, ERS, CRS, and SLIC provide good stability bounds; algorithms meeting the desired superpixel count within appropriate bounds are preferable.
  • Quantitative evaluation: AMR, AUE, and AUV summarize performance independently of K and support understandable ranking, while EV complements Rec and UE but should not be used alone.Rec and UE identify consistently strong algorithms such as ERGC, ETPS, CRS, SLIC, and ERS; EV is ground-truth independent but may misidentify well-performing algorithms.

FH reFH SLIC vlSLIC SEEDS reSEEDS preSLIC

The evaluation examines implementation effects, robustness, and high-superpixel-count behavior while comparing algorithms under controlled connectivity. It finds that implementation details and blur affect performance, whereas most algorithms tolerate considered noise and can preserve image content at K ≈20,000.

  • Influence of Implementations: Implementation details affect both performance and runtime, with improved connectivity associated with better performance in reSEEDS and reFH.reSEEDS and preSLIC have lower runtimes than SEEDS and SLIC, while reFH is slower than FH.
  • Robustness: Most algorithms remain robust to salt and pepper noise, with only slight reductions in Rec and UE.QS and VC compensate for noise by generating additional superpixels.
  • Robustness: Blurring reduces Rec and UE and can reduce the number of generated superpixels for QS and VC.The evaluation considers average blur with filter sizes k ∈{0, 5, 9, 13, 17}.
  • High Superpixel Counts: At K ≈20,000, nearly all evaluated algorithms achieve Rec ≥0.99, UE ≈0.03, and EV > 0.9.The experiments reduce primitives from 481 · 321 = 154401 to approximately 20,000, although VC and PF are exceptions.
  • Ranking: The ranking orders algorithms by AMR + AUE on each dataset, with the lowest sum receiving rank one.Some algorithms were excluded from particular datasets because they could not be evaluated there.

8. Conclusion

The paper presents a broad, fair benchmark of superpixel algorithms using controlled parameters, connectivity enforcement, and metrics that summarize performance across superpixel counts. It concludes with application-relevant observations and recommends six stable algorithms for practice.

  • Conclusion: The benchmark compares algorithms across visual quality, performance metrics, runtime, implementation details, and robustness to noise, blur, and affine transformations.It evaluates 28 algorithms on five datasets covering indoor, outdoor, and person images.
  • Conclusion: AMR, AUE, and AUV summarize performance independently of the number of generated superpixels and support an overall ranking for algorithm selection.The evaluation also considers minimum, maximum, and standard deviation rather than simple metric averages.
  • Conclusion: Six recommended algorithms are ETPS, SEEDS, ERS, CRS, ERGC, and SLIC, which show superior Rec, UE, and EV performance and can be considered stable.Their runtime and compactness-parameter characteristics differ by algorithm and implementation.
  • Conclusion: The benchmark implementations and evaluation software are publicly available at davidstutz.de/projects/superpixel-benchmark/.The release is intended to accompany the benchmark and its algorithm comparisons.

Appendix B. Datasets

The appendix describes BSDS500 in detail because it uniquely provides multiple ground-truth segmentations per image. It also specifies how metrics are aggregated across those segmentations and points to additional qualitative examples.

  • Datasets: BSDS500 is the only dataset used that provides several ground-truth segmentations per image.This makes it the dataset discussed in detail in the appendix.
  • Datasets: Additional example images from all used datasets appear in Figure B.17 and support qualitative results in Appendix E.1.The examples complement the detailed BSDS500 discussion.
  • Datasets: For BSDS500, the evaluation averages the lowest metric value across an image’s ground-truth segmentations, applying the same method to Rec, UE, EV, ASA, and UELevin.This follows the methodology of Arbeláez et al.

Appendix C. Benchmark

The appendix introduces the expressiveness of the evaluation metrics and explains how AMR, AUE, and AUV are computed.

  • Benchmark: The section examines how expressive the selected evaluation metrics are.
  • Benchmark: It provides computational details for Average Miss Rate, Average Undersegmentation Error, and Average Unexplained Variation.
  • Benchmark: The section connects metric expressiveness with the computation of aggregate benchmark measures.

Appendix C.1. Expressiveness and Correlation

The appendix examines metric correlations and the evaluation protocol, emphasizing fair parameter optimization, standardized initialization, and metrics designed to compare algorithms across superpixel counts.

  • A correlation of −0.47 between Rec and UE indicates that SEEDS combines high Rec with comparatively lower UE.
  • AMR, AUE, and AUV summarize performance independently of K by integrating Boundary Miss Rate, UE, and Unexplained Variation over K = 200–5200.The areas are computed using the trapezoidal rule.
  • Parameter optimization includes color space selection, while additional color spaces are excluded when unsupported or unreported to limit overhead.
  • The benchmark standardizes initialization across algorithms that directly control superpixel counts and those using regular-grid initialization.

Appendix E.1. Qualitative

The qualitative appendix shows that increasing the number of superpixels generally improves both boundary adherence and compactness, while compactness parameters still enable an explicit trade-off.

  • The qualitative comparisons cover BSDS500, SBD, Fash, NYUV2, and SUNRGBD, with results shown at approximately K = 1200 and K = 3600.
  • NC, RW, and SEAW were not evaluated on SUNRGBD because their MATLAB implementations used exhaustive memory.
  • For K ≈400, the compactness parameter provides a gradual trade-off between boundary adherence and compactness across the shown algorithms.
  • Higher K generally improves boundary adherence, although FH, QS, CIS, PF, PB, TPS, and SEAW remain exceptions.With more superpixels, missed image boundaries have a less serious effect.
  • Higher K increases compactness even for algorithms without a compactness parameter.The effect of parameter optimization on Rec and UE remains visible, including for algorithms that do provide compactness control.

Appendix E.2. Quantitative

The quantitative appendix compares ground-truth-dependent and ground-truth-independent metrics across datasets, while also examining metric redundancy and runtime scaling.

  • Rec, UE, and EV are examined on SBD, SUNRGBD, and Fash, while ASA and UELevin are examined on BSDS500 and NYUV2.
  • ETPS and SEEDS show above-average Rec across SBD, SUNRGBD, and Fash, whereas EV provides a more consistent cross-dataset view for distinguishing algorithms.
  • ASA closely follows 1 − UE and therefore adds no new quantitative comparison insight, while UELevin offers another but harder-to-interpret viewpoint.
  • Most algorithms have runtime that scales roughly linearly with image size, while the number of generated superpixels has little influence.
  • For K ≈400, W runs in roughly 1.9 ms on SBD and 7.9 ms on SUNRGBD as image size increases from 75,988 to 322,080 pixels.
Loading 1612.01601v3…