PaperlayerView exact revision on arXiv

Source-linked AI summary

SEEDS: Superpixels Extracted via Energy-Driven Sampling

Michael Van den Bergh, Xavier Boix, Gemma Roig, Luc Van Gool

arXiv:1309.3848v1cs.CV

TL;DR

Superpixel extraction methods often use computationally expensive strategies that progressively build regions, limiting real-time use. SEEDS starts from an initial partition and uses efficient hill-climbing boundary exchanges with a color-homogeneity energy. It achieves competitive state-of-the-art performance in real time on a single CPU.

  • Problem

    Existing superpixel algorithms rely on sophisticated progressive construction strategies whose computational cost is too high for real-time applications.

  • Method

    SEEDS refines an initial superpixel partition by exchanging boundary pixels with hill-climbing optimization over an energy combining color homogeneity and boundary shape.

  • Results

    SEEDS runs in real time at 30Hz on a single Intel i7 CPU at 2.8GHz while remaining competitive with state-of-the-art methods.

  • Takeaways & Limitations

    SEEDS provides an efficient superpixel framework whose run-time can be controlled on the fly while maintaining competitive benchmark performance.

  • Takeaways & Limitations

    Undersegmentation evaluation can depend on how pixels on or near label borders are treated, motivating a new metric beyond ad hoc tolerance choices.

Abstract

from arXiv · show

Superpixel algorithms aim to over-segment the image by grouping pixels that belong to the same object. Many state-of-the-art superpixel algorithms rely on minimizing objective functions to enforce color ho- mogeneity. The optimization is accomplished by sophis- ticated methods that progressively build the superpix- els, typically by adding cuts or growing superpixels. As a result, they are computationally too expensive for real-time applications. We introduce a new approach based on a simple hill-climbing optimization. Starting from an initial superpixel partitioning, it continuously refines the superpixels by modifying the boundaries. We define a robust and fast to evaluate energy function, based on enforcing color similarity between the bound- aries and the superpixel color histogram. In a series of experiments, we show that we achieve an excellent com- promise between accuracy and efficiency. We are able to achieve a performance comparable to the state-of- the-art, but in real-time on a single Intel i7 CPU at 2.8GHz.

1 Introduction

SEEDS replaces progressively constructed superpixels with boundary refinement from a complete partition, using efficient hill-climbing optimization. It targets real-time speed while retaining competitive segmentation quality.

  • Motivation: Existing superpixel methods progressively add cuts or grow regions, but their computational cost remains far from real-time.These methods rely on sophisticated optimization schemes and can approach the cost of full semantic segmentation.
  • SEEDS approach: SEEDS starts from a complete partition and iteratively exchanges boundary pixels between neighboring superpixels.The method initializes superpixels in a grid and refines their boundaries rather than incrementally constructing regions.
  • SEEDS approach: The objective combines color-distribution homogeneity with a term encouraging smooth boundary shapes.Its hill-climbing optimizer accepts a proposed boundary movement when the objective function increases.
  • Efficiency: Hierarchical block updates begin with large blocks and decrease to pixel-level changes, requiring one memory look-up for a single boundary-pixel move.This update strategy reduces the cost of evaluating proposed exchanges.
  • Results: 30Hz on a single Intel i7 CPU at 2.8GHz, while remaining competitive with the best non-realtime methods.The evaluation used the Berkeley segmentation benchmark and no GPU or dedicated hardware.

2 Towards Efficiently Extracted Superpixels

Prior superpixel methods use graph cuts, region growing, flooding, clustering, or geometric flows, but efficiency and quality remain difficult to balance. SEEDS instead refines boundaries from a regular-grid initialization without repeatedly growing regions from centers.

  • Graph-based methods: Graph-based methods represent pixel similarities with edges and optimize partitions through progressively added cuts or clustering.Examples include Normalized Cuts, agglomerative graph clustering, and entropy-rate maximization with a balancing term.
  • Non-graph methods: Watersheds flood gradient surfaces, while Turbopixels grow regions through geometric flows.These approaches form superpixels without the graph representation used by graph-based methods.
  • Growing methods: SLIC grows superpixels around regular-grid centers through repeated clustering and center updates.Other related approaches use geodesic distances, additional centers, or appearance and motion constraints.
  • Efficiency gap: 5Hz is the reported speed for SLIC, the fastest among the compared non-graph methods, which generally do not run in real time.The passage also states that these methods often obtain inferior performance to graph-based alternatives.
  • SEEDS distinction: SEEDS bypasses center-based growing by directly exchanging pixels between neighboring superpixels through boundary movement.Although it also starts from a regular grid, it avoids computing distances from superpixels to surrounding pixels at every growth iteration.

3 Superpixels as an Energy Maximization

The paper formulates superpixel extraction as maximizing an energy over valid, spatially connected image partitions. The formulation separates color-distribution likelihood from an optional boundary-shape prior while restricting assignments to a fixed number of superpixels.

  • Problem formulation: Superpixel quality depends on grouping similar pixels within objects and following object boundaries with regular shapes.The formulation represents each superpixel through its color distribution and boundary shape.
  • Partition representation: The partitioning maps each of N image pixels to one of K superpixels, with K fixed for comparison with prior work.The assigned-pixel sets are disjoint and collectively represent the image partition.
  • Valid partitions: A valid superpixel is spatially connected, so S contains valid partitions while C contains both valid and invalid partitions.Figure 2 contrasts a connected partition in S with a disconnected partition that belongs to C but not S.
  • Energy maximization: The objective seeks a partition s ∈ S that maximizes the energy function E(s, I).The optimization searches for the highest-energy valid partition among an extremely large partition space.

4 Energy Function

The energy function combines a color-distribution term with an optional boundary-shape prior. Its histogram-based formulation supports efficient hill-climbing updates while encouraging homogeneous colors and regular boundaries.

  • Energy formulation: The energy function is the sum of a color-likelihood term H(s) and an optional boundary-shape prior G(s).H(s) evaluates color distributions, while G(s) can enforce preferred boundary shapes.
  • Color Distribution Term: H(s): H(s) evaluates each superpixel's color distribution using a measure designed to reward concentration in one or a few colors.The paper assumes color distributions are independent across superpixels and does not impose neighboring color constraints.
  • Color Distribution Term: H(s): The hill-climbing implementation efficiently evaluates and updates histogram-based color scores during proposed partition changes.The algorithm accepts a proposed partition when its energy is not lower than the current partition.
  • Boundary Term: G(s): G(s) penalizes local boundary irregularities and can favor compactness, smooth boundaries, or proximity to image edges.Within SEEDS, this boundary term is optional when additional control over superpixel shape is desired.
  • Boundary Term: G(s): The boundary term uses local N × N patches whose label histograms reward patches dominated by one superpixel, thereby encouraging regular shapes.Patches near boundaries contain multiple labels, so penalizing such mixtures reduces pixels close to irregular boundaries.

5 Superpixels via Hill-Climbing Optimization

SEEDS refines an initial superpixel partition through hill-climbing boundary movements, using hierarchical block-to-pixel updates and efficiently evaluated histogram-based energy changes.

  • Optimization: Hill-climbing iteratively proposes local partition changes by moving pixels between neighboring superpixels and accepts changes that improve the energy.The partition starts from the current solution, and small modifications can be evaluated quickly.
  • Boundary Updates: The algorithm uses pixel-level and block-level boundary updates, treating both as the same operation at different scales.Block updates move groups of pixels, while pixel updates move a boundary by one pixel.
  • Initialization: A grid initializes the partition, while hierarchical blocks are constructed from 2 × 2 or 3 × 3 blocks and combined to form consistent initial superpixels.The largest block is a quarter of the target superpixel size, and the desired count is selected through the initial block size and number of levels.
  • Boundary Updates: Block sizes decrease hierarchically from large movements to individual pixels, improving convergence and enabling final boundary tuning.Large block updates are used first because they move more pixels and help avoid local maxima; pixel updates finish the refinement.
  • Energy Evaluation: Pixel-level histogram intersections can be evaluated with one memory access because a pixel histogram activates a single color bin.For block updates, the method relies on concentrated color histograms and reports that the assumptions hold in 93% of cases.
  • Energy Evaluation: Hierarchical boundary updates preserve smooth superpixel boundaries without requiring an explicit boundary term in the energy function.Removing that term makes energy evaluation more efficient.
  • Termination: The algorithm can stop at an application-defined time or under a runtime budget because each iteration is extremely fast.The current iteration can be completed with negligible additional time.

6 Experiments

The experiments evaluate SEEDS on the Berkeley Segmentation Dataset using standard and corrected metrics, highlighting both metric limitations and runtime-quality behavior.

  • Dataset and Evaluation: The Berkeley Segmentation Dataset contains 500 images, with 200 training, 100 validation, and 200 test images used for evaluation.The only tuned parameter is selected on training data, while reported results use the 200 test images.
  • Dataset and Evaluation: The evaluation uses undersegmentation error, boundary recall, achievable segmentation accuracy, and the newly introduced corrected undersegmentation error.Lower values are better for UE and CUE, while higher values are better for BR and ASA.
  • Metrics: The standard undersegmentation error can penalize qualitatively different segmentations equally when boundary pixels are assigned across object borders.Because object boundaries lie between pixels, a single boundary-pixel error can fully penalize a superpixel on both sides.
  • Metrics: Corrected undersegmentation error matches each superpixel to its largest-overlap ground-truth segment and counts error on only one side.The authors state that this avoids ad hoc tolerances and better represents undersegmentation error.

6.2 Parameters

The parameter study addresses color space, boundary-term weighting, neighborhood size, histogram resolution, and approximation accuracy.

  • Parameter Choices: LAB color space gives the highest performance in the authors’ experiments, while the boundary-term weight and neighborhood size involve a smoothness-performance trade-off.No standard metric for superpixel smoothness or compactness is available, so these settings are difficult to evaluate directly.
  • Parameter Choices: The hierarchical design leaves only the histogram bin count to tune, set to 5 bins per color channel, or 125 bins total.This setting produced the best performance on a subset of the Berkeley training set.
  • Approximation Check: The Proposition 1 approximation holds for 97% of pixel-level updates and 89% of block-level updates.These rates were obtained by explicitly comparing the approximation with the full energy function over training-set updates.

6.3 Histograms and Block-level Updates

SEEDS combines histogram-based color modeling with hierarchical block updates to accelerate boundary refinement. Boundary priors mainly affect shape and boundary recall, while compactness can worsen segmentation metrics.

  • Histograms and Block-level Updates: SEEDS uses histograms for color distributions and introduces SPH and SPM baselines to isolate the effects of histograms and block-level updates.SPH uses pixel-level histogram updates, whereas SPM uses SLIC’s mean-based distance measure.
  • Histograms and Block-level Updates: 20 ms versus 200 ms: SEEDS produces a result similar to SLIC’s 10 iterations in one-tenth the time.The comparison is reported for available processing time in Fig. 8.
  • Histograms and Block-level Updates: Block updates make SEEDS converge faster and reach a better result than pixel-level histogram updates, which are more prone to local maxima.Histogram-based updating converges faster than means-based updating, while means-based updating reaches a slightly better final result.
  • Boundary Priors: Boundary priors have little effect on CUE, UE, and ASA except under strict compactness, while all priors reduce boundary recall.The evaluated priors include smoothing, compactness, edge snapping, and their combination.
  • Boundary Priors: Boundary recall is best without a boundary prior; the combined prior provides a compromise between compact shapes and performance.The remaining experiments therefore omit boundary priors.

6.5 Number of Iterations and Post Processing

Hierarchical boundary updates allow SEEDS to obtain good segmentations at 30 Hz while retaining time for further convergence at 15 Hz. A means-based post-processing stage combines fast histogram convergence with a small accuracy gain.

  • Number of Iterations and Post Processing: Means-based updating converges more slowly but reaches a slightly better result, so SEEDS uses it during the final pixel-level post-processing updates.This preserves histogram updating’s fast convergence while adding the means-based accuracy improvement.

6.6 Comparison to State-of-the-Art

Against ERS, SLIC, FH, and GRID on Berkeley benchmarks, SEEDS matches key undersegmentation errors, improves several quality measures, and runs substantially faster. It also outperforms the other superpixel methods on BSDS300 contour detection while remaining orders of magnitude faster.

  • Benchmark Comparisons: SEEDS is compared with ERS, SLIC, Felzenszwalb–Huttenlocher, and GRID, with ERS treated as a performance-oriented reference and SLIC as the fastest prior method.FH parameters are selected to obtain the desired number of superpixels with the best performance.
  • Benchmark Comparisons: SEEDS matches ERS on UE and CUE, outperforms it on BR and ASA, and is orders of magnitude faster.The comparison includes SEEDS at 15 Hz and the earlier SEEDS ECCV12 version at 5 Hz; ERS runs below 1 Hz in this experiment.
  • Benchmark Comparisons: On the BSDS300 contour detection benchmark, SEEDS outperforms the other superpixel methods while remaining orders of magnitude faster.The evaluation averages boundaries from segmentations produced at 12 scales ranging from 6 to 600 superpixels.

7 Conclusions

SEEDS uses efficient hill-climbing exchanges and histogram-based energy evaluation to balance segmentation accuracy with efficiency. Its runtime is controllable and it operates in real time on a single CPU, while its energy function can be adapted to additional inputs and features.

  • Conclusions: SEEDS maximizes a color-homogeneity energy through efficient pixel exchanges between neighboring superpixels.The energy uses histogram intersection distance for efficient evaluation.
  • Conclusions: SEEDS can run in real time with runtime controlled on the fly using one CPU without GPUs or dedicated hardware.The conclusion reports competitiveness with state-of-the-art methods on standard benchmark datasets.
  • Conclusions: The framework can adapt its boundary-update energy to applications using color, depth, optical flow, video, texture, or edges while maintaining real-time properties.The paper presents this adaptability as a feature for different applications and input sources.

A Evaluating Pixel-level and Block-level Movements

This section proves two propositions used to speed up evaluation of pixel-level and block-level movements. The derivations rely on assumptions about superpixel sizes and concentrated color histograms.

  • A Evaluating Pixel-level and Block-level Movements: The section proves both propositions used to speed up evaluating pixel-level and block-level movements.The proofs develop expressions for the energy terms associated with candidate pixel or block movements.
  • A Evaluating Pixel-level and Block-level Movements: Proposition 1 assumes similarly sized superpixels and a neighboring superpixel whose color histogram is concentrated in one bin.Under these assumptions, the color-term evaluation is simplified by removing contributions from other superpixels and histogram normalization.
  • A Evaluating Pixel-level and Block-level Movements: The proofs simplify the relevant inequalities by expanding squares, canceling repeated terms, and reordering the remaining expressions.The color-term proof similarly starts from the energy definition and compares two partitions differing in the affected superpixel.
  • A Evaluating Pixel-level and Block-level Movements: Using the concentrated-histogram and similar-size assumptions, the derivation obtains the expression stated in Eq. (25).The preceding steps evaluate intersection distances and then apply the assumptions to reach the proposition’s final form.
  • A Evaluating Pixel-level and Block-level Movements: The block-level derivation treats the pixels whose patches intersect a pixel as candidates for movement between superpixels.The proof analyzes a labeling change involving movement from superpixel Ak to An.
Loading 1309.3848v1…