Algorithms for Hierarchical Graph-Based Segmentation

Get HGB code on GitHub

Edward Cayllahua-Cahuina, Jean Cousty, Silvio Guimarães, Yukiko Kenmochi, Guillermo Cámara-Chávez & Arnaldo de Albuquerque Araújo

Hierarchical image segmentation provides a region-oriented scale-space, i.e., a set of image segmentations at different detail levels in which the segmentations at finer levels are nested with respect to those at coarser levels. Guimarâes et al., 2017, proposed a hierarchical graph-based image segmentation (HGB) method based on the Felzenszwalb-Huttenlocher dissimilarity. This HGB method computes, for each edge of a graph, the minimum scale in a hierarchy at which two regions linked by this edge should merge according to the dissimilarity. In order to generalize this method, we first propose an algorithm to compute the intervals which contain all the observation scales at which the associated regions should merge. Then, following the current trend in mathematical morphology to study criteria which are not increasing on a hierarchy, we present various strategies to select a significant observation scale in these intervals. This is the code for Hierarchical Graph Based Segmentation from a non Increasing Edge Observation Attribute [Cayllahua et al., 2019] .

Image Result of the original HGB method (saliency map) Result of the HGB method with the newly proposed  upper P-rank selection strategy
A segmentation obtained from Min-rule hierarchy (48 Regions) A segmentation obtained from Upper P-rank hierarchy (48 Regions)
A segmentation obtained from Min-rule hierarchy (100 Regions) A segmentation obtained from Upper P-rank hierarchy (100 Regions)
Images used for tests come from PASCAL VOC 2010 and VOC 2012 dataset. Click here to see more hierarchical image segmentation results. For a video showing segmentations obtained from HGB, click here.

Get the code

Click here to get the code.

Build/Install

This code was compiled and executed in Linux. To compile use:

./compileHGB.sh

Usage

The program takes as input an image file in the format XXXX.ppm and produces as output a saliency map XXXX.pgm, which is the visualization of the hierarchy after performing the hierarchical graph based segmentation from a non increasing edge observation attribute of the input image.

To execute the program:

./hgbSegmentation.sh INPUT_IMAGE.ppm OUTPUT_SM.pgm OPTION PARAMETER AREASIMP

Where:

OPTION:

1: Use Min: select minimum value on positive observation intervals
2: Use Max: select the last upper bound on negative intervals

3: Lower-length: On positive intervals, apply length threshold and min-rule
4: Upper-length: apply length threshold and max-rule

5: Lower-area: On positive intervals, apply area and  min-rule
6: Upper-Narea: On negative intervals, apply area and  max-rule

7: Lower-depth: On positive intervals, apply depth filter and min-rule
8: Upper-Ndepth: On negative intervals, apply depth filter and max-rule

9: Lower p-rank: On positive intervals, apply rank filter and  min-rule
10: Upper p-rank: On negative intervals, apply rank filter and  max-rule

PARAMETER: Refers to the alpha or ranking parameter (threshold)

AREASIMP: Refers to the area simplification parameter. If no value is passed, then the value 0.004 is assumed.

Example:

./hgbSegmentation.sh Images/3063.ppm /tmp/salida.pgm 10 0.001 0.003

Citation

Please cite as

@InProceedings{Cayllahuaetal2019,
author="Cayllahua-Cahuina, Edward
and Cousty, Jean
and Guimar{\~a}es, Silvio
and Kenmochi, Yukiko
and C{\'a}mara-Ch{\'a}vez, Guillermo
and de Albuquerque Ara{\'u}jo, Arnaldo",
title="A Study of Observation Scales Based on Felzenswalb-Huttenlocher Dissimilarity Measure for Hierarchical Segmentation",
booktitle="Discrete Geometry for Computer Imagery",
year="2019",
publisher="Springer International Publishing",
pages="167--179",
isbn="978-3-030-14085-4"
}

Licence information

This software is governed by the CeCILL license under French law and abiding by the rules of distribution of free software. You can use, modify and/ or redistribute the software under the terms of the CeCILL license as circulated by CEA, CNRS and INRIA at the following URL .

Institutions

Edward Cayllahua-Cahuina [1,2], Jean Cousty [1], Silvio Guimarães [3], Yukiko Kenmochi [1], Guillermo Cámara-Chávez[4], & Arnaldo de Albuquerque Araújo [1,2]
[1] Université Paris-Est, LIGM (UMR 8049), CNRS, ENPC, ESIEE Paris, UPEM
[2] Universidade Federal de Minas Gerais, DCC - NPDI
[3] Pontifícia Universidade Católica De Minas Gerais - VIPLAB
[4] Universidade Federal de Ouro Preto - DECOM