Evaluating image segments by applying the description length to sets of superpixels

Alexander Schick, Rainer Stiefelhagen

Introduction

Defining a "good" image segmentation is a fundamental challenge in computer vision. The task is inherently subjective and scale-dependent; for instance, a valid segment could be an entire person or just their face. Traditional algorithms often rely on manually tuned parameters or assume that objects must possess uniform color or texture. This paper introduces a parameter-free, information-theoretic framework to evaluate segment quality by treating superpixels as atomic building blocks and measuring their "description length."

Methodology

The proposed framework builds upon the concept of segmentation-by-composition. The core intuition is that a high-quality segment should be easy to describe using its own internal components but difficult to describe using parts from the rest of the image.

Superpixels as Primitives

To achieve computational efficiency and robustness against noise, the image is first partitioned into a few hundred "superpixels"—homogeneous regions that respect natural object boundaries. This reduces the problem complexity from tens of thousands of pixels to a manageable set of primitives.

Initial superpixel decomposition of an image.

The Information-Theoretic Score Function

Each superpixel is modeled as a unimodal Gaussian distribution based on its color mean and covariance. The quality of a segment $S$ relative to the background $T$ is defined using the difference in Description Length (DL): $$Score(S) = DL(S|T) - DL(S|S)$$ If a segment is much easier to describe using its own parts ($DL(S|S)$ is low) than by using background parts ($DL(S|T)$ is high), it is identified as a meaningful region. To compute these lengths efficiently, the authors utilize the closed-form solution for Kullback-Leibler (KL) divergence between Gaussians. This allows for pre-computing divergences and storing them in a lookup table.

Applications and Results

The versatility of this score function is demonstrated across three distinct tasks:

  1. Salient Object Detection: An exhaustive sliding-window search identifies the window with the highest composition score.
  2. Automatic Segmentation: A greedy region-merging approach combines neighboring segments to maximize the global score.
  3. Dominant Object Segmentation: A hybrid approach grows the best segment around the most salient point.
Salient object detection identifying the primary subject.

The framework was evaluated using the Berkeley Segmentation Dataset (BSDS300). Key results indicate that the method successfully identifies salient objects—such as animals in complex natural backgrounds—and produces segmentations that align closely with human perception. Notably, the score function requires no per-task tuning, relying entirely on the statistical properties of the image data.

Discussion and Limitations

A significant advantage of this approach is its focus on composition over homogeneity. Unlike algorithms that fail on textured objects (e.g., a checkered shirt), this method succeeds because it only requires that the parts of a segment be "available" within itself to describe the whole.

However, the method is strictly limited by the quality of the initial superpixels. If a superpixel erroneously crosses an object boundary, the algorithm cannot correct it. Additionally, the greedy merging strategy used for automatic segmentation may occasionally settle into local optima. Future work may involve GPU acceleration to improve the speed of exhaustive saliency searches.

Summary updated

Abstract

Image segmentation is a fundamental task in computer vision and a prerequisite for many applications. But what is a good segmentation? One possible answer is given by the segmentation-by-composition framework that defines a good segment as one that can easily be composed by parts of itself. However, this framework is originally based on pixels which causes several problems, among them the need for additional input in form of boundary maps. In this paper, we transform this framework to the domain of superpixels, homogeneous image regions aligning well with object boundaries that can be used as atomic building blocks. At the core of this framework is a score function that quantifies the quality of a given segmentation. We extend this score function to the more general multi-segment case and compute it efficiently for sets of superpixels based on their description length. The score function is solely based on superpixels and does neither require any parameters nor are there thresholds involved. As our secondary contribution and to demonstrate the versatility of the score function for sets of superpixels, we show three applications: salient object detection, fully automatic parameter-free image segmentation, and a combination of both, the automatic segmentation of the most dominant object in an image.
BibTeX
@inproceedings{schick2011evaluating,
  author = {Alexander Schick and Rainer Stiefelhagen},
  title = {{Evaluating image segments by applying the description length to sets of superpixels}},
  booktitle = {Workshops @ ICCV},
  year = {2011},
  doi = {10.1109/iccvw.2011.6130414},
}
Figure