Supervised Assessment of Segmentation Hierarchies

(Code available at the bottom of the page)

The objective of this research line is to provide supervised measures for the assessment of segmentation hierarchies. In other words, to evaluate the quality of such hierarchies by comparing them to a ground truth database such as the BSDS500.

We focus on those hierarchies that can be represented as a tree or a dendogram, such as the Binary Partition Trees (BPT)1 or Ultrametric Contour Maps (UCM)2. Starting from a fine partition that will form the leaves of the tree, they are formed by iteratively merging the most similar pairs of neighboring regions, as in the following Figure:

This way, pruning the tree at different levels can give us a large collection of partitions represented in the same hierarchy. The number of regions grows rapidly, so when assessing the hierarchies, it is not feasible to compare all the represented partitions against the ground truth.

The approach followed by previous works is to select a representative set of partitions from the hierarchy and compare this set to the ground truth. Specifically, only the set of partitions formed at each merging of the algorithm is considered, as in the previous Figure, indexed by the number of regions (BPT) or the probability of boundary threshold (UCM). This strategy leads to quality evolution curves as the ones in the following figure:

This set of representative partitions, however, is a very reduced set with respect to all possible partitions. As an example, the partition in the following figure is not represented in the merging-sequence partition set:

Our proposal is to compute the partitions that represent the upper-bound quality of the tree, that is, the partitions that best match the ground truth. 

Our ECCV2012 paper presents the algorithm to compute the upper-bound partition with respect to the boundary F-measure3. To do so, we model the problem as a Linear Fractional Combinatorial Problem, which can be efficiently solved.

The experiments show that the measure is much more discriminant than the previous approaches. Quantitatively, the following chart compare how the measures discriminate the random technique used as baseline:

As a qualitative example, the following figure shows: four diferent images, the ground truth partitions on BSDS500, the representative partition in the merging-sequence set (ODS), the OIS representative, and the upper-bound partition in the hierarchy:

As this examples shows, the merging-sequence partition set potentially masks the quality that a tree can achieve, so representing the quality of the tree by this set can be misleading.

As a simpler approach, our ICASSP2012 paper presents a dynamic programming algorithm to find the upper-bound partitions with respect to the asymmetrical partition distance4. In this case, dynamic programming can be used thanks to the fact that the measure is local, which is not the case for the  F measure.

Downloads

The package hierarch_upper_bound_fb contains the Matlab code to compute the upper-bound boundary F measure and to reproduce all the experiments from the ECCV2012 paper. It has the pre-computed results, the necessary scripts to reproduce the paper experiments, and the functions to use the code in your own experiments.

The following dependencies are needed:

• BSDS300 segbench code.
• IBM ILOG CPLEX Optimization Studio for Academics.

Once installed in your system, please read the README file of our package and the install.m script to make the code work. The code comes pre-computed for 64-bit mac and linux machines. For 32-bit mac and linux architechtures, try whether the install script successfully compiles it. Windows machines have not been tested but it should not be difficult to compile the needed files using mex (see install.m for more details).

• 1. Salembier, P. & Garrido, L. Binary partition tree as an efficient representation for image processing, segmentation, and information retrieval. IEEE Transactions on Image Processing, 2000 (9) 561-576.
• 2. Arbeláez, P.; Maire, M.; Fowlkes, C. C. & Malik, J. Contour Detection and Hierarchical Image Segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011 (33) 898-916.
• 3. Martin, D.; Fowlkes, C. & Malik, J. Learning to Detect Natural Image Boundaries Using Local Brightness, Color, and Texture Cues. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004 (26) 530-549.
• 4. Cardoso, J. S.; Carvalho, P.; Teixeira, L. F. & Corte-Real, L. Partition-distance methods for assessing spatial segmentations of images and videos. Computer Vision and Image Understanding, 2009 (113) 811 - 823.