Amin Fehri
email: amin.fehri@mines-paristech.fr

Santiago Velasco-Forero
email: santiago.velasco@mines-paristech.fr

Fernand Meyer
email: fernand.meyer@mines-paristech.fr

CHARACTERIZING IMAGES BY THE GROMOV-HAUSDORFF DISTANCES BETWEEN DERIVED HIERARCHIES

Keywords: Gromov-Hausdorff Distance, Hierarchies, Stochastic Watershed, Texture, Classification

A hierarchy is a series of nested partitions in which a coarser partition results from merging regions of finer ones. Each hierarchy derived from an image provides a particular structural description of the image content, depending upon the criteria for merging neighboring regions. Distinct hierarchies derived from a same image reflect its various facets and the distances between them nicely characterize its content. In this paper the hierarchies are constructed with the versatile stochastic watershed algorithm and their inter-distances are measured with the Gromov-Hausdorff distance. Experiments conducted on images simulated by dead leaves model illustrate the advantages of our approach in terms of learning efficiency and understandability of the results.

INTRODUCTION

Hierarchical segmentation is a multi-scale image analysis technique that provides contours valuations proposals, with respect to given properties to enhance. It has been one of the fruitful approaches to perform segmentation tasks. The goal then is to find the hierarchical segmentation from which it is easier to find a suitable segmentation [START_REF] Beucher | Watershed, hierarchical segmentation and waterfall algorithm[END_REF][START_REF] Meyer | The dynamics of minima and contours[END_REF][START_REF] Najman | Geodesic saliency of watershed contours and hierarchical segmentation[END_REF][START_REF] Ouzounis | Maskbased second-generation connectivity and attribute filters[END_REF][START_REF] Arbelaez | Contour detection and hierarchical image segmentation[END_REF]. However, these different hierarchical segmentation approaches are application-dependent, and their efficiency depends on the types of structures present in the images. In this paper, we propose a new approach to take advantage of such multi-scale analysis. The main idea is to quantify the distance between different hierarchical representations to characterize images. In the proposed approach, we only use selected morphological hierarchical segmentation methods [START_REF] Meyer | Stochastic watershed hierarchies[END_REF]. However, any hierarchical method can fall within its scope.

First, we remind the reader of ways to generate hierarchical segmentations, which basically consist in progressive merging of images regions such that the regions we are interested in are the last to merge with their neighbors. Then starting from a set of hierarchies and a given image, we show how we can compute a distance between them: we use this representation to characterize classes of images in an analytical way. Finally, we illustrate the discriminative and explanatory power of these features on generated shape images. An overview of the process can be found in Fig. 1. Our main contributions are: (i) The use of the Gromov-Hausdorff distance to quantify the relative contributions of each hierarchy of segmentation, (ii) The introduction of image features in the form of interhierarchy distance matrices.

MORPHOLOGICAL HIERARCHIES

Hierarchies of Segmentations

Hierarchical segmentation is a low-level image analysis often used to make easier the obtention of a suitable segmentation. In this work, we limit ourselves to morphological hierarchies that can efficiently be obtained in a graph-based framework [START_REF] Cousty | Hierarchical segmentations with graphs: quasi-flat zones, minimum spanning trees, and saliency maps[END_REF]. For the sake of brevity, the reader is invited to refer to the section 2. of [START_REF] Fehri | Automatic selection of stochastic watershed hierarchies[END_REF] for a description of this process. Making use of such approaches, we have several ways to generate an indexed hierarchy of partitions (H, λ), with H a chain of nested partitions H = {π 0 , π 1 , . . . , π n |∀j, k, 0 ≤ j ≤ k ≤ n ⇒ π j π k }, with π n the single-region partition, π 0 the finest partition on the image and π i π j if all regions of π i are included in regions of π j , and λ : H → R + being an ultrametric stratification index verifying λ(π) < λ(π ) for two nested partitions π ⊂ π . This increasing map allows us to value each contour according to the level of the hierarchy for which it disappears: this is the saliency of the contour [START_REF] Arbelaez | Contour detection and hierarchical image segmentation[END_REF]. A contour then has various saliencies for various hierarchies. An example of this is shown in Fig. 1B.

A wide range of hierarchies

Based on the framework described in the previous section, one can generate several types of hierarchies that highlight different contours in the image. In particular, the model of the stochastic watershed (SWS) hierarchies [START_REF] Meyer | Stochastic watershed hierarchies[END_REF] , based upon the seminal work of [START_REF] Angulo | Stochastic watershed segmentation[END_REF] is able to adapt to the specific object properties to enhance (e.g. elongation, surfaces equilibrium, contrast) for segmentation tasks [START_REF] Fehri | Automatic selection of stochastic watershed hierarchies[END_REF]. It can also take spatial prior information into account in its making [START_REF] Fehri | Prior-based hierarchical segmentation highlighting structures of interest[END_REF]. If we consider our image as a topographic relief, flooding this image leads to watershed lines, i.e. to a segmentation. By spreading random flooding sources multiple times and flooding the image accordingly, one can characterize each contour of the image by its frequency of appearance in the associated segmentations. By only choosing high-level parameters such as the density governing the distribution of markers or their shape and size, we can then generate at will various multilevel representations of the images highlighting various types of regions. Thanks to this versatility, specific hierarchies can be built: for example, we can favor certain shapes in the images by considering a surface-based SWS hierarchy in which the measured areas are the ones of regions eroded with anisotropic structuring elements. An example of this is shown in Fig. 2: vertical structures are highlighted in (c), and horizontal ones in (d). An additional layer of supplementary complexity can be added via the possibility to combine hierarchies to obtain new ones. It can notably be done through the use of subdominant ultrametrics to obtain the supremum, infimum or a linear combination of two hierarchies [START_REF] Maia | Evaluation of combinations of watershed hierarchies[END_REF][START_REF] Cousty | Hierarchical segmentations with graphs: quasi-flat zones, minimum spanning trees, and saliency maps[END_REF]. In this work, when saliencies are probability values (as it is the case of stochastic hierarchies), the same procedure can lead to probabilistic combinations of hierarchies of the type AND(H 1 , H 2 ) and OR(H 1 , H 2 ). In Fig. 2(f), the circular and cross shapes are highlighted, as they respect the horizontal and vertical property. We argue that this wealth of controlled understandable options can lead to powerful features, through the use of a distance between hierarchies: the Gromov-Hausdorff distance.

FEATURES ON HIERARCHIES USING GROMOV-HAUSDORFF DISTANCE

Indeed, once provided with a family of hierarchies, one may wonder if there are ways to use the different information they provide to characterize images. The usual approach to do so

(a) (b) (c) (d) (e) (f) Fig. 2.
Saliency maps for different hierarchies (inverted for better visualization).

(a) Image, (b) Dynamics, (c)

H surf -V ertSE , (d) H surf -HorizSE , (e) H OR = OR(H surf -V ertSE , H surf -HorizSE ) (f) H AND = AND(H surf -V ertSE , H surf -HorizSE )
it to extract information at various levels of the hierarchies, which often requires a hard parameter-tuning [START_REF] Guigues | Scalesets image analysis[END_REF]. Furthermore, it obliterates the interesting property that hierarchical segmentations are more informative than flat segmentations as they capture simultaneously cluster structure at all levels of granularity. The study of most of the useful existing hierarchical clustering methods is made complex by the fact that they are defined algorithmically. The morphological hierarchies that we use fall within this scope. To study the properties of such hierarchies, works define a distance between hierarchical clusterings called Gromov-Hausdorff distance [START_REF] Gromov | Structures métriques pour les variétés riemanniennes[END_REF][START_REF] Gromov | Metric structures for Riemannian and non-Riemannian spaces[END_REF], and use it to study their stability and convergence [START_REF] Carlsson | Characterization, stability and convergence of hierarchical clustering methods[END_REF]. In this work, we make use of this distance to build a feature space that capture the relative information brought by several hierarchies applied on the same image.

Gromov-Hausdorff distance

In [START_REF] Gromov | Structures métriques pour les variétés riemanniennes[END_REF] (translated in English in [START_REF] Gromov | Metric structures for Riemannian and non-Riemannian spaces[END_REF]), the authors propose a distance, called Gromov-Hausdorff (GH) distance, to measure how far two compact metric spaces are from being isometric. It gives a very useful and natural way to distinguish between metric spaces. By reducing this distance to the subclass of ultrametric spaces, we can in particular quantify the relative contributions of different hierarchical clusterings. This distance, used intensively in several fields such as phylogenetics and data mining [START_REF] Felsenstein | Inferring phylogenies[END_REF], has also notably been used in image processing as a way to estimate the similarity between two points clouds [START_REF] Mémoli | Comparing point clouds[END_REF]. Let us consider two metric spaces (X 1 , u α ) and (X 2 , u β ). One supposes that we have defined two functions f : X 1 → X 2 and g : X 2 → X 1 that are maps from one space to the other. The GH-distance is expressed as:

d GH (X 1 , X 2 ) := 1 2 min f,g
max(dis(f ), dis(g), dis(f, g))

(1) With the distorsion dis(f ) and the joint distorsion dis(f, g) defined as:

dis(f ) := max (x,x )∈X 2 1 |u α (x, x ) -u β (f (x), f (x ))| dis(f, g) := max x∈X1,x ∈X2 |u α (x, g(x )) -u β (x , f (x))|
(2) Intuitively, it measures how close can we get to an isometric (distance-preserving) embedding between two metric spaces. As it is shown in [START_REF] Gromov | Structures métriques pour les variétés riemanniennes[END_REF][START_REF] Gromov | Metric structures for Riemannian and non-Riemannian spaces[END_REF][START_REF] Carlsson | Characterization, stability and convergence of hierarchical clustering methods[END_REF], to determine (1) for two hierarchies defined over different sets, one must match data points before any distance computation, which is a computationally heavy operation that leads some authors to provide heuristics to approximate it in specific configurations [START_REF] Mémoli | Comparing point clouds[END_REF][START_REF] Pankaj K Agarwal | Computing the gromov-hausdorff distance for metric trees[END_REF]. In our case we are dealing with structures that are much simpler: instead of considering objects-to-objects distances, we compute them for hierarchies based upon the same fine partition of an image. So the considered metric spaces differ only by their metrics and not by the space they cover, which means that the two distortions are symmetrical and equal to the joint-distortion as well. Thus, the GH distance (1) simply becomes:

d GH ((X, u α ), (X, u β )) = max x,x ∈X |u α (x, x ) -u β (x, x )|.
(3)

Ultrametric Normalization

To make sense of GH distances, one must be sure that ultrametric values are commensurable and of the same order of magnitude. Accordingly, we propose a way to normalize these values with respect to the number of regions in each level of the hierarchy. Let (H, λ) be an ultrametric hierarchy, with λ : X → R + which is strictly increasing with the inclusion order over H. Let us denote N = card(H), (H 0 , ..., H N ) the nested series of clustering associated with the hierarchy, which are numbers of regions in successive levels of the hierarchy (n 0 , ..., n N ), with 0 < n 0 ≤ n 1 ≤ ... ≤ n N = N . Then we take as a normalized ultrametric:

λ : H → [0, 1] H i → N -ni N (4)

An interhierarchy distance matrix as hierarchical feature

Provided with such a distance, we can now quantify the relative contributions of different hierarchies built upon the same image. This provides us with a condensed representation leveraging the information provided by all the different levels of these different hierarchies. To do so, let us consider an image I and a set of complementary hierarchies ((H 1 , λ 1 ), . . . , (H N , λ N )) built upon this image. As we have seen in the previous section, it is then straightforward to compute the GH-distance between these hierarchies, as they constitute ultrametric spaces upon the same set. We take advantage of it by building the following symmetrical distance matrix:

M (I, (H 1 , . . . , H N )) = d GH (λ i , λ j ) (i,j)∈{1,...,N } 2 (5)
Since this matrix is symmetrical, we retain for each image its upper triangular part only. This constitutes a descriptor of the image for which we only had to specify the high-level parameters governing the hierarchies generation. Summarizing, an overview of the proposed process to extract features from a family of hierarchies can be found in Fig. 1.

EXPERIMENTAL RESULTS

In this section, we present some experimental results highlighting the properties of the descriptors we have proposed in the previous section.

Dead leaves process classification

In a first experiment, we highlight the discriminative power of the unsupervised hierarchical features we introduced, as long as their understandability. In the spirit of [START_REF] Yan | How intelligent are convolutional neural networks?[END_REF], we want to test if these features capture pertinent information leading to a quicker understanding of the images. To do so, we consider a classification problem on a set of simulated images from different dead leaves process [20][21]. In a dead leaves model, two dimensional textured surfaces (which are called "leaves" or "primary grains") are sampled from a shape and size distribution and then placed on the image plane at random positions, occluding one another to produce an image. It is well-known that such a model creates images which share many properties with natural images such as scale invariance and other statistics properties [22][23]. In our experiment, we have simulated five classes with 100 images each, by using dead leaves model with different primary grains: circles, crosses, flowers, horizontal and vertical lines. Examples of simulated images can be found in Fig. 3. Note that we have included different sizes and orientations tweaks to increase the difficulty of the identification. For each of these images, we compute the following hierarchies: dynamics, surfacebased SWS hierarchies with structuring elements of various sizes and forms (cross, circle, diagonals, horizontal and vertical lines), as long as probabilistic AND and OR of these SWS hierarchies. Then we generate for each of these images the interhierarchy distance matrices of equation 5. We can then use these matrices as features in a classical classification pipeline using a linear support vector machines (SVM) to classify images of each class. We notice that the system can trary to CNN that have a black-box behavior, our approach shows what is often referred to as an "aha moment", i.e. a moment of sudden realization and comprehension [START_REF] Yan | How intelligent are convolutional neural networks?[END_REF]. This translates a form of understanding of the content of the image, which is corroborated by the study of the importance of which specific interhierarchy distances were the more useful to discriminate between two types of classes. For example, discriminating between horizontal and vertical lines will mainly be due to d GH (H surf -V ertSE , H surf -HorizSE ), while discriminating between crosses and circles will mainly be due to d GH (H surf -CrossSE , H surf -HexSE ). A visualization of the quality of the feature space thus generated can be found in Fig. 5(a), where we project the features in a space of two dimensions using the t-SNE algorithm [START_REF] Van Der Maaten | Visualizing data using t-SNE[END_REF]. Furthermore, using the variable selection method L 1 -SVM [25], we can isolate the more discriminative distances for two specific classes to separate. For example, the t-SNE visualization in Fig. 5(a) shows us that discriminating between the classes "Flowers" and "Horizontal Lines" is not straightforward. The more discriminative variable between these two classes is the distance between H surf -V ertSE and H AND(surf -V ertSE,surf -HexSE) : this is a geometrical interpretation of the image content, as they respectively capture straight lines and lines with a protuberance (i.e. flowers). Projecting the distance features onto the subspace of the two more discriminative variables properly separates these two classes, as can be seen in Fig. 5(b). We are thus provided with a good way to control and understand features generation to be further used in vision-based system, especially when we have prior information about the type of objects we are looking for in images, and/or when we have very few training examples and want to maximize their usefulness.

CONCLUSIONS AND DISCUSSIONS

In this work, we have proven the efficiency of features created by estimating the differences between different hierarchical segmentations of the same images. The proof-of-concept experiments we conducted show that these features can provide a geometrical interpretation of the image content, and help to analyze images classes with very few examples. Furthermore, this approach can be extended to any type of hierarchies to capture various types of information. We see three ways to use such information. First, if we know well the type of images we want to discriminate, we can generate at will the hierarchies that will be the more discriminative. Secondly, if we build a sufficiently wide range of complementary hierarchies for an unknown class of images, we can characterize these images by looking at the way they react to these operators through the study of interhierarchy distances. In line with classical morphological approaches, we can thus gain knowledge about images by studying the way they react to given operators. Finally, many methods exist to extract a segmentation out of a hierarchical segmentation, and our approach provides a way to identify the hierarchies that will lead to the best results in such a process.

Fig. 1 .

 1 Fig. 1. Overview of our approach A: We start from an image and a set of morphological hierarchical segmentations techniques. B: Each of these techniques highlight different contours of the image, and we can quantify their relative contribution using the Gromov-Hausdorff distance. C: We proposed to use the interhierarchy Gromov-Hausdorff distance matrices as features.

Fig. 3 .Fig. 4 .

 34 Fig. 3. False-color representation of simulated images by dead leaves model with different primary grains.

Fig. 5 .

 5 Fig. 5. (a) We notice that the classes "Flowers" and "Horizontal Lines" are not well separated (b) These two distances between hierarchies provide a geometrical understanding of the images content.

  Dropout(.5) ) + FullyCon64 + Dropout (.5) + SoftMax. Categorical cross-entropy as loss function and adaptive gradient (Adagrad) as optimizer. The code used to train the CNN and scripts to generate the synthetic images are available online at https://github.com/./.

1 (12 Conv + 12 Conv + MaxPolling(3 × 3) + Dropout(0.3) ) + (24 filters + 24 filters + MaxPolling(3 × 3)+