pff's homepage

Tiered Scene Labeling with Dynamic Programming

Below is a C++ implementation of the algorithm described in the paper:

Tiered Scene Labeling with Dynamic Programming
P. Felzenszwalb, O. Veksler
IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2010

The package includes the labeling algorithm and illustrates its use for binary segmentation using shape priors. See the README file and tiered.cpp for more information.

Code Download
(last updated on 10/16/10)


Dynamic programming (DP) has been a useful tool for a variety of computer vision problems. However its application is usually limited to problems with a one dimensional or low treewidth structure, whereas most domains in vision are at least 2D. In this paper we show how to apply DP for pixel labeling of 2D scenes with simple "tiered" structure. While there are many variations possible, for the applications we consider the following tiered structure is appropriate. An image is first divided by horizontal curves into the top, middle, and bottom regions, and the middle region is further subdivided vertically into subregions. Under these constraints a globally optimal labeling can be found using an efficient dynamic programming algorithm. We apply this algorithm to two very different tasks. The first is the problem of geometric class labeling where the goal is to assign each pixel a label such as "sky", "ground", and "surface above ground". The second task involves incorporating simple shape priors for segmentation of an image into the "foreground" and "background" regions.

A tiered labeling

Binary segmentation with shape priors
We model an object by a sequence of parts, and encourage the boundary between the background and each part to have certain slants. Each part is captured by a different label of the middle region. In the example below we use a "leaf shape" prior to segment the image into background and different foreground parts.