Palestra Prof. Dr. Jean Cousty

Palestra Prof. Dr. Jean Cousty

Sala de Seminário do DECOM - ICEB III - Dia 25/02/15 as 17:00.

Título: An introduction to hierarchical image segmentation

Many image segmentation methods look for a partition of the set of image pixels such that each region of the partition corresponds to an object of interest in the image. Hierarchical segmentation methods, instead of providing a unique partition, produce a sequence of nested partitions at different scales, enabling to describe an object of interest as a grouping of several objects of interest that appear at lower scales. This methodology became very popular in recent years as attested by the number of citations reached by a paper by Arbelaez et al on this subject: 879 citations since its publication in 2011 ! Quasi-flat zones hierarchies, hierarchical watersheds, or constrained connectivity are some examples of popular morphological hierarchies for image analysis applications.

In the first part of this presentation, we study three representations of hierarchies of partitions: dendrograms (direct representations), saliency maps, and minimum spanning trees. We provide a new bijection between saliency maps and hierarchies based on quasi-flat zones hierarchy as used in image processing and characterize saliency maps and minimum spanning trees as solutions to constrained minimization problems where the constraint is quasi-flat zones preservation. In practice, these results form a toolkit for new hierarchical methods where one can choose the most convenient representation. They also invite us to process non-image data with morphological hierarchies.

In the second part of this presentation, based on the aforementioned representation, we present an algothmic framework for computing hierarchies. More precisely, we provide linear or quasi-linear algorithms for producing some of the hierarchies used in mathematical morphology, in particular the ones corresponding to hierarchies of watershed cuts and hierarchies of constrained connectivity. A specific binary tree, corresponding to an ordered version of the edges of the minimum spanning tree, is the key structure in this study, and is computed thanks to variations around Kruskal algorithm for minimum spanning tree.