Another framework, popular in image analysis, consists of considering a segmentation as a partition of the image domain where each element of the partition represents a segmented region. Thus the regions are not separated by "background pixels". As we will see in Section 2.2, in many cases, this framework also falls in the scope of the present study.

INTRODUCTION

This dissertation, written for the purpose of obtaining the French « Habilitation à diriger des recherches » from Université Paris-Est, presents our main contributions to the field of image analysis and understanding. This presentation includes work made after our PhD defense (2007), as well as work done before it, hence covering a period of more than ten years of research. A cut separating these two periods would be somehow arbitrary since :

-the time of a research project is long and its boundaries are fuzzy. It is most of the time not clear to establish the beginning and the end of a research work. As illustrations, we can highlight the fact that many of the results included in our PhD dissertation [START_REF] Cousty | Lignes de partage des eaux discrètes : théorie et application à la segmentation d'images cardiaques[END_REF] are published, often with some further enrichments, after the date of the defense or that some source codes corresponding to some work published in the form of an article in 2017 [START_REF] Cousty | Hierarchical segmentations with graphs : quasi-flat zones, minimum spanning trees, and saliency maps[END_REF] were already available online in 2007 before our PhD defense ; -the consistency between the research initiated before and after our PhD is strong. A goal of this dissertation is to highlight this consistency with the perspectives of showing the ability to continue in the same fruitful directions. This consistency covers both topics and points of view. For instance, concerning application topics, we work in 2004 on augmenting X-ray images made available to the cardiologists who perform catheter-based electrical intervention with 3D heart models acquired before the intervention (this work was published after 2008 in the form of two patents [START_REF] Vaillant | Method and system for registering 3D models of anatomical regions with projection images of the same[END_REF][START_REF] Vaillant | Method and apparatus for registering 3D models of anatomical regions of a heart and a tracking system with projection images of an interventional fluoroscopic system[END_REF]). The PhD topic of Ketan Bacchuwar, which we co-advise and which should be defended in 2018, includes merging information acquired, through X-ray images, at different steps of cardiac catheter-based interventions in order to annotate the intention of the clinician during stenting procedures. Concerning the point of view, three main objectives are carried out in most of our research projects : (i) establishing the correctness of the proposed solutions in the form of formal properties offering guarantees on the proposed solutions and helping to understand precisely in which sense they solve a given problem, (ii) proposing computable solutions with efficient algorithms, (iii) assessing qualitatively and quantitatively the proposed solutions in the context of real-world problems, coming, for instance, from industry collaborations. We emphasize that every project presented in this dissertation is the result of a collaboration, some of the collaborators being experienced researchers while some others are advised PhD students or interns. Each collaborator has an impact on the presented work. Besides deep propositions or problems raised by collaborators, naive questions or misunderstandings often lead to new developments and better explanations. The resulting interactions are always valuable contributions. The virtue of team-work has not to be demonstrated here, and the « Habilitation à diriger des recherches » which we seek to obtain with the present dissertation is a step forward to guarantee the development of our work as a team in the future.

Producing reproducable and teachable research is an important goal of our work. To this end, a precise mathematical formalization of the problems, of their analyses, and of the provided solutions is necessary to avoid, or at least to reduce, ambiguity. Additionally, to ease reproducability and dissemination of our research results, the source codes of many proposed algorithms are made available online. The list of this available resources is given in the appendix chapter of the dissertation. However, for the sake of concision, this dissertation provides only a literary introduction to our major contributions rather than a detailed and formalized presentation of the results. Such presentation has the advantage of providing a survey of our main contributions which is readable in a limited amount of time. However, only a detailed presentation would allow one to reproduce the provided results and, for this purpose, the reader is invited to refer to the cited articles and to test the provided programs. This dissertation is organized into four main sections that are all related to image analysis, mathematical morphology and digital topology. Each section corresponds to one part of the dissertation title.

Segmentation. Section 2 introduces our contributions to the field of image, or more generally data, segmentation. In particular, we detail in Section 2.1 our main results concerning region merging methods, and watershed segmentation in the framework of vertex-weighted graphs. This framework is adapted when one seeks for a separation of the segmented regions located on the pixels of an image, or more generally on the vertices of a graph whose vertex set is to be segmented. Section 2.2 details our contributions to the watershed segmentation problem in edge-weighted graph. In this framework, the set of obtained regions is a partition of the space (i.e. the image pixels, or the vertices of the graph) and the separation is located between the pixels, that is on the edges of the grid of pixels or on the edges of the graph. Finally, Section 2.3 studies watersheds of maps defined on pseudomanifolds handled in the framework of simplicial complexes. Such framework allows us to establish links between the watershed transform (i.e., the process allowing to obtain the watershed of a map) and the homotopic transforms (i.e., continuous deformation that preserves topological invariants of the object under transformation).

Hierarchy. Section 3 details our contribution to hierarchical analysis, a hierarchy being a series of nested partitions. We first present in Section 3.1, equivalent representations of hierarchies which are useful to propose new hierarchical analysis methods and to design algorithms to build and to process these hierarchies. In Section 3.2, we detail some problems and solutions related to hierarchies of watersheds in edge-weighted graphs. In Section 3.3, we show how one can combine hierarchies of partitions, such as, watershed hierarchies obtained from several distinct regional attributes. In Section 3.4, we introduce some methodological tools to hierachize an important class of image segmentation methods which depend on a scale parameter but do not lead to hierarchies of segmentations under the variation of this scale parameter. Finally, Section 3.5 presents the notion of a directed component hierarchy which allows generalizing the connected operators developed in the framework of mathematical morphology to the case of directed graphs where asymmetric information between pixels, or more generally data, can be taken into account for filtering and segmenting. Mathematical morphology filtering. Section 4 introduces our contributions to the problem of shape and image regularization by mathematical morphology filtering based on adjunctions. In Section 4.1, we study new mathematical morphology operators that are in particular able to deal with subgraphs of a given graph, considered as the working space and, in Section 4.2, we present an extension to simplicial complexes which are richer topological structures. This framework allows the processing of images, when the image is structured as a graph or as a simplicial complex, and also paves the way towards more general data regularization with mathematical morphology filters by adjunction.

Application to image analysis. Section 5 presents a series of application problems which are solved with the tools presented in the three first parts of the dissertation combined with classical tools from the domains of image processing and computer vision. For these application problems, an important effort is devoted to quantitative and qualitative assessments in conjunction with experts of the different application fields. Sections 5.1 and 5.2 present methods allowing the detection of functional and anatomical diseases in cardiology from Magnetic Resonance and X-Ray computerized tomography images, respectively. The two following sections, namely Sections 5.3 and 5.4, present image processing methods and softwares designed to help cardiologists during minimally invasive cardiac surgery monitored by X-ray imaging systems. In Section 5.5, the interest of mathematical morphology regularization by adjunction (see Section 4) as a preprocessing step to optical character recognition softwares is assessed. In Section 5.6, we present a novel evaluation framework for the hierarchies of partitions designed to capture various aspects of those representations corresponding to their use in computer vision and image analysis tasks. Based on this framework, we assess that hierarchical watershed methods, as presented in Section 3.2, are valuable candidates for such tasks. Finally, we present in Section 5.7, a search engine dedicated to browsing a database of digitized 3D artwork models. Each model is described by regional attributes computed on the regions of a watershed partition such as described in Sections 2.2 and 2.3. This dissertation is completed by the full list of our publications (Section 7) and by our CV provided in appendix. [START_REF] Cousty | Fusion Graphs : Merging Properties and Watersheds[END_REF]

IMAGE SEGMENTATION AND WATERSHEDS

Region merging and watershed on vertices

Fusion graphs, region merging and thinness of binary watersheds

Image segmentation is the task of delineating objects of interest that appear in an image. For this important and difficult task, connectivity often plays an essential role : in many cases, the result of such a process, also called a segmentation, is a set of connected regions lying in a background which constitutes the separation between regions. To define regions, an image is often considered as a graph whose vertex set is made of the pixels of the image and whose edge set is given by an adjacency relation on these pixels. In this framework * , the regions correspond to the connected components of foreground pixels (see for instance Figure 1) and are separated by a background. When the background set cannot be reduced, by point removal, while preserving the number of regions of the foreground set, it is called a cleft or a (binary) watershed [START_REF] Cousty | Fusion Graphs : Merging Properties and Watersheds[END_REF][START_REF] Bertrand | On topological watersheds[END_REF]. The notion of a cleft can be seen as a formalization of the intuitive notion of a frontier.

A popular approach to image segmentation, called region merging [START_REF] Pavlidis | Structural pattern recognition[END_REF][START_REF] Rosenfeld | Digital picture processing[END_REF], consists of progressively merging pairs of regions, starting from an initial segmentation that contains too many regions (see, for instance, Figures 1a andb). Given a subset S of an image equipped with an adjacency relation, merging two neighboring regions (connected components) of S is not straightforward. A problem occurs when we want to merge a pair of neighboring regions A and B of S and when each point adjacent to these two regions is also adjacent to a third one that we want to preserve during the merging operation. Figure 1c illustrates such a situation, where x is adjacent to regions A, B, C and y to A, B, D. Thus, we cannot merge A and B while preserving both C and D. This problem has been identified in particular by T. Pavlidis (see [START_REF] Pavlidis | Structural pattern recognition[END_REF], section 5.6 : "When three regions meet"), and, as far as we know, has not been solved in general.

A second question arises when dealing with such segmentations, called clefts, on a graph. Given a pixel adjacency graph, such as the one induced by the usual 4-adjacency relation [START_REF] Kong | Digital topology : Introduction and survey[END_REF] on a set of image pixels (see Figure 1b), we observe that a cleft may contain some « inner points », i.e., points which are not adjacent to any point outside the cleft (see Figure 1d,e). We can say that a cleft on this graph is not necessarily thin. On the other hand, such inner points do not seem to appear in any cleft when the considered graph is induced by the 8-adjacency relation (see, e.g., Figure 1f ). We prove in [START_REF] Cousty | Fusion Graphs : Merging Properties and Watersheds[END_REF] that this assertion is indeed true. More interestingly, we provide in [START_REF] Cousty | Fusion Graphs : Merging Properties and Watersheds[END_REF][START_REF] Cousty | Uniqueness of the Perfect Fusion Grid on Z d[END_REF] a framework to study properties of thinness of clefts in any kind of graph, and we identify the class of graphs in which any cleft is necessarily thin.

Four classes of fusion graphs.

A first major contribution of [START_REF] Cousty | Fusion Graphs : Merging Properties and Watersheds[END_REF] is the definition of a merging operation and the study of four nested classes of graphs in which the problematic situations, such as the one pointed out in the previous paragraph, are progressively avoided. These graphs are called the weak fusion graphs, the fusion graphs, the strong fusion graphs and the perfect fusion graphs. In particular, a graph is a fusion graph if any region A in this graph can always be merged with another region B, while preserving all other regions. We provide local characterizations of two of these classes and show that the two others cannot be locally characterized. Furthermore, we show that the class of perfect fusion graphs is a subset of the one of line graphs, which is well studied in graph theory (see, e.g., [START_REF] Berge | Graphes et hypergraphes[END_REF]). Thinness of separations. One of the most striking outcomes of [START_REF] Cousty | Fusion Graphs : Merging Properties and Watersheds[END_REF] is that the class of fusion graphs is exactly the class of graphs in which any cleft is thin (i.e., a cleft in which any point is adjacent to at least one region). Region merging with usual adjacency relations. Using this framework, we analyze the status of the graphs which are the most widely used for image analysis in 2D and in 3D. In one of the four classes of graphs which we have introduced and that we call the class of the perfect fusion graphs, any two neighboring regions A and B can always be merged, while preserving all other regions, by removing from the separation all the pixels which are adjacent to both A and B. In 2-dimensional image analysis, two adjacency relations on Z 2 , called the 4-and the 8-adjacencies [START_REF] Kong | Digital topology : Introduction and survey[END_REF], are commonly used. With the 4-adjacency (resp. the 8adjacency), each point is adjacent to its 4 (resp. 8) closest neighbors. For instance, the graph in Figure 1c is induced by the 4-adjacency. As seen above, the two neighboring regions A and B cannot be merged, while preserving all other regions, by removing x and y from the set of black vertices. Thus, in general, the graphs induced by the 4-adjacency are not perfect fusion graphs. Similar configurations can be found with the 8-adjacency. Thus the graphs induced by the 8-adjacency are not perfect fusion graphs either. More generally, the graphs induced by the direct and the indirect adjacencies [START_REF] Klette | Digital Geometry : Geometric Methods for Digital Picture Analysis[END_REF][START_REF] Kong | Digital topology : Introduction and survey[END_REF], which generalize the 4-and the 8-adjacencies to Z d , are not perfect fusion graphs (see Section 6 in [START_REF] Cousty | Fusion Graphs : Merging Properties and Watersheds[END_REF]). Additionally, we have proved that the graphs induced by the 8-adjacency relation are fusion graphs. Hence, any cleft is thin in these graphs. On the other hand, no other graph induced by the direct and indirect adjacency relations is a fusion graph, hence thick clefts may be found on these graphs.

Uniqueness of perfect fusion grids in arbitrary dimension. In [START_REF] Cousty | Fusion Graphs : Merging Properties and Watersheds[END_REF], we introduce a family of graphs on Z d that we call the perfect fusion grids, which can be used in image analysis, which are indeed perfect fusion graphs, and which are « between » the graphs induced by the direct and the indirect adjacencies. Let us give an intuitive presentation of these graphs in the two dimensional case. Consider the set C of all black squares in a chessboard (see Figure 2). The perfect fusion grid is simply the graph obtained, by setting adjacent any two corners which belong to a same square in C (see, for instance, the two graphs depicted Figure 2). Figure 3a shows a set of regions obtained in this grid thanks to a watershed algorithm [START_REF] Cousty | Weighted fusion graphs : merging properties and watersheds[END_REF]. It can be seen on Figure 3b that the problems pointed out in the previous paragraphs do not exist in this case : any pair of neighboring regions can be merged by simply removing from the black vertices the points which are adjacent to both regions (see Figure 3b,c). Furthermore, it can be verified on Figure 2 that any two points which are 4-adjacent are necessarily adjacent for the perfect fusion grid and that any two points adjacent for the perfect fusion grid are necessarily 8-adjacent. In this sense, the perfect fusion grid satisfies the geometric constraint of being « between » the graphs induced by the 4-and the 8-adjacency relations. The main result of [START_REF] Cousty | Uniqueness of the Perfect Fusion Grid on Z d[END_REF] establishes that the perfect fusion grid is the only perfect fusion graph on Z d which is between the direct and the indirect adjacency relations, whatever the dimension d ∈ N . As far as we know, up to now, in digital topology, there exists only one other result of unicity of an adjacency relation in arbitrary dimension. It is due to Kong [191] and, informally, it states that the only Alexandroff topology on Z d « between the direct and the indirect adjacency relations » is the topology proposed by Khalimsky [START_REF] Khalimsky | Computer graphics and connected topologies on finite ordered sets[END_REF].

Weighted fusion graphs and watersheds

Given a grayscale image, or more generally a vertex-weighted graph (i.e., a graph and a map that assigns a scalar value to each vertex), the watershed transform [START_REF] Beucher | The morphological approach to segmentation : the watershed transformation[END_REF][START_REF] Couprie | Topological grayscale watershed transform[END_REF][START_REF] Digabel | Iterative algorithms[END_REF][START_REF] Meyer | Un algorithme optimal de ligne de partage des eaux[END_REF][START_REF] Vincent | Watersheds in digital spaces : An efficient algorithm based on immersion simulations[END_REF] is a powerful tool to obtain an initial segmentation for a region merging procedure. Let us consider a 2D grayscale image as a topographical relief, where the dark pixels correspond to basins and valleys, whereas the bright pixels correspond to hills and crests. Suppose that we are interested in segmenting dark regions. Intuitively, the watersheds of an image are constituted by the crests which separate the basins corresponding to regional minima. This notion is illustrated in Figure 4, where the white points in Figure 4(c) constitute a watershed of the image in Figure 4(a) equipped with the 8-adjacency relation. Due to noise and texture, real-world images often have a huge number of regional minima, hence the mosaic aspect of Figure 4(c). Nevertheless, it has been shown in numerous applications that this segmentation is an interesting starting point for a region merging process (see, e.g., [START_REF] Bleau | Watershed-based segmentation and region merging[END_REF][START_REF] Haris | Hybrid image segmentation using watersheds and fast region merging[END_REF][START_REF] Jasiobedzki | Automated analysis of retinal images[END_REF] In a merging process, in order to identify the next pair of neighboring regions to be merged, many methods are based on the values of the points that belong to the initial separation between regions. In particular, in mathematical morphology, several methods [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] are implicitly based on the assumption that the initial separation satisfies a fundamental constraint : the values of the points in the separation must convey a notion of contrast, called connection value, between the minima of the original image. The connection value between two minima A and B is the minimal value γ such that there exists a path from A to B the maximal value of which is γ. From a topographical point of view, this value can be intuitively interpreted as the minimal altitude that a global flooding of the relief must reach in order to merge the basins that flood A and B. As studied in [START_REF] Najman | Watersheds, mosaics and the emergence paradigm[END_REF], obtaining a separation which is guaranteed to satisfy such constraint is not straightforward.

In the topological approach to the watershed [START_REF] Bertrand | On topological watersheds[END_REF][START_REF] Couprie | Topological grayscale watershed transform[END_REF][START_REF] Couprie | Quasi-linear algorithms for the topological watershed[END_REF], we consider a transformation that iteratively lowers the value of a map F while preserving some topological properties, namely the number of connected components of each lower threshold of F . This transform and its result are called W-thinning ; a topological watershed being a W-thinning that is minimal for the relation ≤ on maps. This notion is illustrated in Figure 4 where the map H (Figure 4(b)) is a topological watershed of F (Figure 4(a)) equipped with the 8-adjacency relation. The divide of a map is the set of points that do not belong to any regional minimum (see the divide of H in Figure 4(c)). It has been proved in [START_REF] Bertrand | On topological watersheds[END_REF][START_REF] Najman | Watersheds, mosaics and the emergence paradigm[END_REF] that the values of the points in the divide of a W-thinning convey the connection value between the minima of the original map. More remarkably, any set of points that verifies this property can be obtained by a W-thinning. Therefore, the divide of a W-thinning is a good choice for the initial segmentation in many region merging methods.

The divide of a W-thinning and, in particular, of a topological watershed is not necessarily thin. Firstly, we observe that the divide of a topological watershed can contain some points adjacent to a unique connected component of its complement (see the points w and z in Figure 4(d), which depicts a zoom on a part of Figure 4(c)). Secondly, it may also contain some inner points, i.e., points that are not adjacent to any point outside the divide (see point x in Figure 4(d)). For implementing region merging schemes, these two kinds of thickness are problems. For instance, in Figure 4(d), regions A and B, which we would intuitively consider as neighbors, could hardly be considered as candidate to be merged in a computerized procedure since there is no point in the divide which is adjacent to both. To solve the first problem, we want any divide to be a cleft, that is a set of vertices that does not contain any point adjacent to a unique connected component of its complement. However, in general, a cleft is not necessarily thin. It can indeed contain some inner points and thus the second problem remains.

Thinness of watershed separations. In order to propose a solution to these issues, we have studied topological watersheds in vertex-weighted perfect-fusion graphs. One of our main result in [START_REF] Cousty | Weighted fusion graphs : merging properties and watersheds[END_REF] establishes that in a perfect fusion graph the divide of any topological watershed is always a thin cleft. In addition we have also been able to establish the following original contributions.

Thinness of maps. We introduce a notion of thinness for maps and characterize, thanks to a merging property, the class of graphs in which any topological watershed is thin.

Monotone immersion-like watershed. We introduce a transformation, called C-watershed, that necessarily produces a map whose divide is a cleft. We give a local characterization of the class of graphs in which any C-watershed is a W-thinning, this class being a sub-class of the class of fusion graphs and a super-class of the one of the perfect fusion graphs, allowing us to deduce the result of thinness of topological watershed in perfect fusion graphs. In order to compute C-watersheds on perfect fusion graphs, we introduce a linear-time immersion-like monotone algorithm, whereas, in general, a linear-time W-thinning algorithm does not exist and a monotone flooding algorithm does not lead to a divide satisfying the contrast preservation property mentioned above.

Grayscale characterizations of perfect fusion graphs. Finally, we derive some characterizations of perfect fusion graphs based on thinness properties of both C-watersheds and topological watersheds.

From these results, we can state that the perfect fusion grids constitute an interesting alternative to classical grids for watershed-based region merging methods when the obtained regions are intended to be separated by image pixels. An example of such a procedure could be described, starting from a cleft which is the divide of a C-watershed, by the iteration of the following three steps : (i) select the most significant region A according to a given criterion (e.g. the one with least dynamics described in [START_REF] Bertrand | On the dynamics[END_REF][START_REF] Grimaud | New measure of contrast : dynamics[END_REF]) ; (ii) select a region B such that A and B are neighbors and the minimal value of the points adjacent to both A and B is minimal ; and (iii) merge A and B by removing from the cleft all points adjacent to both A and B. An illustration of such a scheme using the dynamics is shown in Figure 5.

Due to the notion of a line graph, which is well studied in graph theory, we show that the properties established for vertex-weighted perfect fusion graphs also hold true for edge-weighted graphs. This last result invites us to investigate in depth a notion of watersheds for edge-weighted graphs.

Watershed on edges

Since the early work of Zahn [START_REF] Zahn | Graph-theoretical methods for detecting and describing gestalt clusters[END_REF], several efficient tools for image segmentation have been expressed in the framework of edge-weighted graphs. In general, they extract a cut from a pixel adjacency graph (i.e., a graph whose vertex set is the set of image pixels and whose edge set is given by an adjacency relations on these pixels). Informally, a cut is a set of edges which, when removed from the graph, separates it into different connected components : it is an inter-pixel separation which partition the image. Given a set of seed-vertices, which "mark" regions of interest in the image, the goal of these operators is to find a cut for which each induced connected component contains exactly one seed and which best matches a criterion based on the image contents. In order to define such a criterion, each edge of the graph is weighted by a measure of similarity (or dissimilarity) between the two pixels linked by this edge. In this context, the principle of min-cut segmentation [START_REF] Boykov | Fast approximate energy minimization via graph cuts[END_REF] (and its variant [START_REF] Shi | Normalized cuts and image segmentation[END_REF]) is to find a cut for which the (weighted) sum of edge weights is minimal. Shortest-path forest approaches such as [START_REF] Falcão | The image foresting transform : theory, algorithm and applications[END_REF][START_REF] Saha | Relative fuzzy connectedness among multiple objects : Theory, algorithms, and applications in image segmentation[END_REF] are also expressed in edge-weighted graphs. They look for a cut such that each vertex is connected to the closest seed for a particular distance in the graph. In [START_REF] Grady | Random walks for image segmentation[END_REF], the author considers another approach where the weight of an edge is interpreted as the probability that a random walker chooses this edge, when standing at one of its extremities. Then, the proposed segmentation operator finds a cut for which each vertex is connected to the seed that this random walker starting at this vertex will first reach.

For topographic purposes, the watershed has been extensively studied during the 19th century by Maxwell [START_REF] Maxwell | On hills and dales[END_REF] and Jordan [START_REF] Jordan | Nouvelles observations sur les lignes de faîtes et de thalweg[END_REF] among others. One hundred years later, the watershed transform was introduced by Digabel and Lantuéjoul [START_REF] Digabel | Iterative algorithms[END_REF] for image segmentation and is now used as a fundamental step in many powerful segmentation procedures such as the region merging segmentation methods presented in the previous section. Many approaches [7, 101, 103, 134, 218-220, 235, 307] have been proposed to define and/or compute the watershed of a vertex-weighted graph corresponding to a grayscale image. The digital image is seen as a topographic surface : the gray level becomes the elevation, the basins and valleys of the topographic surface correspond to dark areas, whereas the mountains and crest lines correspond to light areas. Intuitively, the watershed is a subset of the domain, located on the ridges of the topographic surface, that delineates its catchment basins. One of the most popular method to obtain a watershed consists of simulating a flooding of the topographic surface from its regional minima [START_REF] Beucher | The morphological approach to segmentation : the watershed transformation[END_REF][START_REF] Meyer | Un algorithme optimal de ligne de partage des eaux[END_REF][START_REF] Vincent | Watersheds in digital spaces : An efficient algorithm based on immersion simulations[END_REF]. The divide is made of « dams » built at those points where water coming from different minima would meet. Another approach, called topological watershed [START_REF] Bertrand | On topological watersheds[END_REF][START_REF] Couprie | Topological grayscale watershed transform[END_REF][START_REF] Couprie | Quasi-linear algorithms for the topological watershed[END_REF] (presented in the previous section), allows the authors to rigorously define the notion of a watershed in a discrete space and to prove important properties not guaranteed by most watershed algorithms [START_REF] Najman | Watersheds, mosaics and the emergence paradigm[END_REF]. It consists of lowering the values of a map (e.g., the grayscale mage) while preserving some topological properties, namely, the number of connected components of each lower cross-section. In this case, the watershed divide is the set of points which are not in any regional minimum of the transformed map.

An important motivation of our work in [START_REF] Cousty | Watershed cuts : Minimum spanning forests and the drop of water principle[END_REF][START_REF] Cousty | Watershed cuts : Thinnings, shortest path forests, and topological watersheds[END_REF] is to provide a notion of watershed in the unifying framework of edge-weighted graphs that can help to precisely determine the relation between watersheds and the popular methods presented in the first paragraph. In this framework, a watershed is a cut. Before going further, let us emphasize that any practical comparison between watersheds in edge-weighted graphs and in vertex-weighted graphs should be made with care. Indeed, in general, the choice of one of these frameworks depends on the application. In particular, the framework of vertex-weighted graphs is adapted when the segmented regions must be separated by pixels. In this case, note that the watershed separation is not necessarily one pixel width and can be arbitrary thick (see a study of this problem in the previous section). On the contrary, when an inter-pixel separation is desired, the framework of edge-weighted graphs is appropriate.

Before presenting the watershed in edge-weighted graphs in the next paragraphs, let us briefly introduce some basic ways to define an edge-weighted graph for segmenting a digital image. The graph can be obtained as a pixel or as a region adjacency graph : its vertex set is either the domain of the image to be processed or the set of regions of an initial partition of the image domain. In the latter case, the regions are often called the "image superpixels" (see, e.g., [START_REF] Achanta | Slic superpixels compared to state-of-the-art superpixel methods[END_REF]). In both cases, two typical settings for the edge set can be considered : (1) the edges are obtained from an adjacency relation between the image pixels, such as the well known 4-or 8-adjacency relations ; and (2) the edges are obtained by considering, for each vertex, its nearest neighbors for a distance in a features space onto which the vertices are mapped. A common feature space (see, e.g., [START_REF] Felzenszwalb | Efficient graph-based image segmentation[END_REF]) is the one where each pixel of a color image is mapped to a vector in dimension 5 made of the two spatial coordinates and the three spectral values describing the color of the pixel. The weight of an edge represents the dissimilarity of the pixels linked by this edge. For instance, in the case where the vertices are the pixels of a grayscale image, the weight of an edge can be the absolute difference of intensity between the two linked pixels. More elaborated weight map can be considered including distances in feature spaces as done in [START_REF] Felzenszwalb | Efficient graph-based image segmentation[END_REF] or learned gradient such as the one of [START_REF] Dollár | Fast edge detection using structured forests[END_REF]. The precise setting of the graph depends on the application context and will be discussed with more details in Section 5.6.

Drop of water principle. Our first contribution on the watershed problem in edge weighted graphs is a new definition of a watershed. Unlike previous approaches in discrete frameworks, the watershedscuts [START_REF] Cousty | Watershed cuts : Minimum spanning forests and the drop of water principle[END_REF][START_REF] Cousty | Watershed cuts : Thinnings, shortest path forests, and topological watersheds[END_REF] are defined thanks to the formalization of the intuitive "drop of water principle". Intuitively, a watershed cut is a cut for the minima of the original map (i.e., each connected component induced by the cut contains one and only one minimum of the map) which satisfies the drop of water principle (i.e., from each edge u of the cut, there exists two descending paths starting at u, ending in two distinct minima of the map, and not crossing any edge in the cut). An illustration of this notion of watershed cut is provided in Figure 6(a,b).

Consistency. Our second contribution in [START_REF] Cousty | Watershed cuts : Minimum spanning forests and the drop of water principle[END_REF][START_REF] Cousty | Watershed cuts : Thinnings, shortest path forests, and topological watersheds[END_REF] establishes the consistency of watershed-cuts. In particular, we prove that they can be equivalently defined by their "catchment basins" (through a steepest descent property) or by the "dividing lines" separating these catchment basins (through the drop of water principle presented in the previous paragraph). As far as we know, in discrete frameworks, our definition is the first one that satisfies such a property. Optimality. Our third contribution in [START_REF] Cousty | Watershed cuts : Minimum spanning forests and the drop of water principle[END_REF][START_REF] Cousty | Watershed cuts : Thinnings, shortest path forests, and topological watersheds[END_REF] establishes the optimality of watershed-cuts. In [START_REF] Meyer | Minimum spanning forests for morphological segmentation[END_REF], F. Meyer shows the link between minimum spanning forests (MSF) and flooding from marker algorithms. We extend the problem of minimum spanning forests and show that there is indeed an equivalence between the watershed-cuts and the cuts induced by minimum spanning forest rooted in the minima of the weight map. Such minimum spanning forest and its induced cut are illustrated in Figure 6 Linear-time algorithm. Our fourth contribution in [START_REF] Cousty | Watershed cuts : Minimum spanning forests and the drop of water principle[END_REF][START_REF] Cousty | Watershed cuts : Thinnings, shortest path forests, and topological watersheds[END_REF] consists of a linear-time algorithm to compute the watershed-cuts of an edge-weighted graph. The proposed algorithm does not require any sorting step, nor the use of any sophisticated data structure such as a hierarchical queue or a representation to maintain unions of disjoint sets. Thus, whatever the range of the edge weights, it runs in linear time with respect to the size (i.e., the number of edges) of the input graph. Furthermore, this algorithm does not need to compute the minima in a preliminary step. To the best of our knowledge, this is the first watershed algorithm satisfying such properties.

Thinning. Our fifth contribution in [START_REF] Cousty | Watershed cuts : Minimum spanning forests and the drop of water principle[END_REF][START_REF] Cousty | Watershed cuts : Thinnings, shortest path forests, and topological watersheds[END_REF] is a new thinning paradigm to characterize and compute the watershed cuts. Intuitively, a thinning is obtained from an edge-weighted graph by iteratively lowering the values of the edges that satisfy a certain property. We propose three different properties for selecting the edges which are to be lowered. They lead to three different thinning strategies. The effect of these transforms is to extend the minima of the original map in a way such that the minima of the transformed map constitute a minimum spanning forest rooted in the minima of the original map. Thus, we can prove that these thinnings allow for characterizing watershed cuts. The first of these three schemes uses a purely local strategy to detect the edges which are to be lowered. It is therefore well suited to parallel implementations. The second one leads to a sequential algorithm which runs in linear-time (with respect to the number of edges of the graph) whatever the range of the weight function and which is different than the one quoted in the previous paragraph. In practice, this second linear-time watershed cut algorithm is more flexible than the first one. Indeed, it allows the user to choose (with respect to the application requirements) between several strategies for setting the watershed position in the case where multiple acceptable solutions exist (e.g., when the watershed must be positioned across a plateau of constant altitude). Finally, our third thinning strategy establishes the link between watershed cuts and the popular flooding algorithms.

Connection value. Due to noise and texture, the weight maps derived from real world images often have a huge number of regional minima. Thus, their watersheds define too many catchment basins. As presented in Section 2.1.2, a common issue to reduce this so-called over-segmentation is to use the result of the watershed as a starting point for a region merging procedure. In order to identify the pairs of neighboring regions to be merged, many methods are based on the values of the points or edges that belong to the initial separation between regions. In particular, in mathematical morphology, several methods [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] assume that the values of the points or edges in the separation convey the connection value between any two minima of the original map. We recall that the connection value [START_REF] Bertrand | On topological watersheds[END_REF][START_REF] Bertrand | On the dynamics[END_REF][START_REF] Najman | Watersheds, mosaics and the emergence paradigm[END_REF] between two minima A and B is the minimal value γ such that there exists a path from A to B along which the maximal weight is γ. Surprisingly, in vertex-weighted graphs, several watershed algorithms do not produce a separation that verifies this property. In this case, the watershed is not on the most « significant contours » [START_REF] Najman | Watersheds, mosaics and the emergence paradigm[END_REF] and cannot be used to correctly compute morphological hierarchies such as those proposed in [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]. Our seventh contribution in [START_REF] Cousty | Watershed cuts : Minimum spanning forests and the drop of water principle[END_REF][START_REF] Cousty | Watershed cuts : Thinnings, shortest path forests, and topological watersheds[END_REF] is to establish that the values of the edges in any watershed cut (resp., more generally, in any cut induced by a minimum spanning forest) are sufficient to recover the connection values between the minima of the original map (resp., between the roots of the forest).

Shortest paths. In fact, the connection value itself is used for defining several important segmentation methods such as the fuzzy connectedness segmentation [START_REF] Ciesielski | General theory of fuzzy connectedness segmentations[END_REF][START_REF] Saha | Relative fuzzy connectedness among multiple objects : Theory, algorithms, and applications in image segmentation[END_REF][START_REF] Udupa | Relative fuzzy connectedness and object definition : Theory, algorithms, and applications in image segmentation[END_REF][START_REF] Udupa | Fuzzy connectedness and object definition : Theory, algorithms, and applications in image segmentation[END_REF], the image foresting transform [START_REF] Falcão | The image foresting transform : theory, algorithm and applications[END_REF] or the topological watershed [START_REF] Bertrand | On topological watersheds[END_REF]. Indeed, the two first methods fall in the category of shortest-path forests if a shortest path between two points x and y is defined as a path which « realizes » the connection value between x and y. In other words, in this setting, the length of a path is the maximum value of an edge along the path. Such a shortest-paths forest is called a γ-shortest-path forest. Our eighth contribution in [START_REF] Cousty | Watershed cuts : Minimum spanning forests and the drop of water principle[END_REF][START_REF] Cousty | Watershed cuts : Thinnings, shortest path forests, and topological watersheds[END_REF] is a proof that any minimum spanning forest is a γ-shortest-path forest and that the converse is, in general, not true. We also show that any watershed cut is a topological cut (i.e., a separation induced by a topological watershed defined in an edge-weighted graph) but that the converse is, in general, not true. We emphasize that this study helps, in practice, to choose among these segmentation techniques the one which will best solve a particular problem.

Figure 7 summarizes our main contributions on the watershed problem in edge-weighted graphs. The interest of watershed cuts to segment grayscale or color images and its versatility to segment, tensors medical images is illustrated in Figures 8 and9. Note also that the minimum spanning forest cuts, presented for showing the optimality property of watershed cut, can be used as a marker-based segmentation procedure when the forest is rooted in user-provided markers (or in markers provided by an automated algorithm). An illustration of such procedure is shown in Figure 10. In forthcoming Section 5, watershed-based softwares solving real-world application problems are assessed.

As shown with the above contributions, the watershed cut framework is interesting and fruitful per-se. Additionally, following the publication of [START_REF] Cousty | Watershed cuts : Minimum spanning forests and the drop of water principle[END_REF][START_REF] Cousty | Watershed cuts : Thinnings, shortest path forests, and topological watersheds[END_REF], this framework was shown seminal by opening the watershed doors towards other popular problems of combinatorial optimization and image processing. Indeed, a new type of convergence, under some (power) transformation of edge-weights, towards minimum spanning forests has been established in [START_REF] Allène | Some links between min-cuts, optimal spanning forests and watersheds[END_REF][START_REF] Allène | Some links between extremum spanning forests, watersheds and min-cuts[END_REF][START_REF] Challa | An introduction to gamma-convergence for spectral clustering[END_REF][START_REF] Couprie | Power watershed : A unifying graph-based optimization framework[END_REF][START_REF] Danda | Power tree filter : A theoretical framework linking shortest path filters and minimum spanning tree filters[END_REF] for min-cuts [START_REF] Boykov | Fast approximate energy minimization via graph cuts[END_REF], random-walks [START_REF] Grady | Random walks for image segmentation[END_REF], usual shortest paths (where the length of a path is defined as the sum of the successive edge weights) [START_REF] Falcão | The image foresting transform : theory, algorithm and applications[END_REF], and spectral clustering [START_REF] Luxburg | A tutorial on spectral clustering[END_REF]. This work allows certain watershed and MSF segmentation results to be embedded into an energy minimization framework. Conversely, when there exist multiple solutions to the watershed problems, this framework allows one to select an optimal MSF/watershed segmentation in the sense of these enegies. Note that results in the same spirit are presented in [START_REF] Ciesielski | Fuzzy connectedness image segmentation in graph cut formulation : A linear-time algorithm and a comparative analysis[END_REF] for the fuzzy-connectedness segmentation methods. The thinning paradigm introduced to characterize watershed cuts in the edge-weighted graphs also invite us to study the link between the watersheds and the homotopic thinning and, then, to revisit some topological properties of watersheds which were studied in continuous settings during the 70s. The investigation of such links is precisely the topic of the next section. Flow cut algorithm (Cousty [16]) (Meyer [9]) (Prim, Kruskal, [START_REF] Serra | Hierarchies and climbing energies[END_REF]) (Dijkstra [53], Falcao [START_REF] Bertrand | Watersheds in discrete spaces[END_REF])

M -cut M -kernel algorithm I -cut B-cut Figure 7.
Summary of our main contributions on the watershed problem in edge-weighted graphs. In the figure, N → N means that the notion N is a particular case of the notion N , hence, N ↔ N means that the notions N and N are equivalent ; A N means that the notion N can be computed thanks to algorithm A.

Homotopy, collapses and watersheds on simplicial complexes

The notion of topological W-thinning, introduced and studied in [START_REF] Bertrand | On topological watersheds[END_REF][START_REF] Couprie | Topological grayscale watershed transform[END_REF], shows that the watershed transformation (i.e., the process that computes a topological watershed from a map) can be investigated through a process involving the preservation of a single topological invariant, namely the number of connected components. Figure 11 depicts an object X that has two connected components. It has also two holes, meaning in 2D that its background contains two finite connected components. The number of holes is another topological invariant, that is, a quantity which is left unchanged by any continuous deformation. The intuitive notion of continuous deformation (see an example with Figure 11(b) and a counter-example with Figure 11(c)) is formalized by the notion of homotopy (the interested reader may refer to, e.g., [START_REF] Maunder | Algebraic Topology[END_REF] for a complete exposition). Transformations that preserve all topological characteristics, known as topology-preserving transformations, are used in many applications of image analysis. Homotopic skeletonization [START_REF] Couprie | New characterizations of simple points in 2D, 3D, and 4D discrete spaces[END_REF][START_REF] Kong | Digital topology : Introduction and survey[END_REF] is the best known and the most used transformation of this kind, with many applications both in 2D and 3D. In particular, skeletons are often used as a simplification of the original data, which facilitates shape recognition, registration, or animation. In Figure 12, we show in (c) an example of homotopic skeleton, obtained from the 2D object depicted in (a).

For our purpose, it is important to mention the medial axis, a geometrical notion introduced by Blum. for image analysis in the 60s [START_REF] Blum | A transformation for extracting descriptors of shape[END_REF][START_REF] Blum | An associative machine for dealing with the visual field and some of its biological implications[END_REF]. Intuitively, the medial axis of an object X is the set of the points in X with at least two closest points on the boundary of X (see Figure 13a). It is thus "centered" in X, and in the continuous framework, it has nice topological properties which assess that the medial axis is thin and contains the same topological information as the original object. More precisely, if we consider an object X that is an open subset of R n and its medial axis M A(X), then :

-there is a homotopy between M A(X) and X, as stated by G. Matheron in [START_REF] Matheron | Quelques propriétés topologiques du squelette[END_REF][START_REF] Matheron | Examples of Topological Properties of Skeletons[END_REF] and proved by A. Rivière in [START_REF] Rivière | Classification des points d'un ouvert d'un espace euclidien relativement à la distance au bord : Etude topologique et quantitative des classes obtenues[END_REF][START_REF] Rivière | Nervure d'un Ouvert d'un Espace Euclidien[END_REF] and by A. Lieutier in [START_REF] Lieutier | Any open bounded subset of R n has the same homotopy type as its medial axis[END_REF] ; and -the interior of M A(X) is empty [START_REF] Matheron | Quelques propriétés topologiques du squelette[END_REF][START_REF] Matheron | Examples of Topological Properties of Skeletons[END_REF] and moreover, M A(X) is Lebesgue negligible [START_REF] Rivière | Classification des points d'un ouvert d'un espace euclidien relativement à la distance au bord : Etude topologique et quantitative des classes obtenues[END_REF][START_REF] Rivière | Nervure d'un Ouvert d'un Espace Euclidien[END_REF]. Furthermore, if we denote by D X the distance map of X (that is, the map that associates to each point x of X the Euclidean distance from x to the boundary of X), the medial axis M A(X) can be obtained by extracting the "crests" of D X , or more precisely, the points x of X such that there exists at least two distinct steepest descent paths for D X starting from x. This property is illustrated in Figure 13(b), where the distance map of a rectangle is depicted as a topographical relief, and steepest descent paths issued from two crest points are shown. Also in Figure 12, the map depicted in (b) is the distance map of the object in Figure 12(a), and the skeleton shown in Figure 12(c) corresponds to a discrete notion of a medial axis.

(a) (c) (e) (f ) (b) (d) (f ) (g)
Through the notion of distance map, an interesting link between watershed and medial axis has been stated by L. Najman and M. Schmitt in [START_REF] Najman | Watershed of a continuous function[END_REF]. They showed that the watershed of D X is a subset of the medial axis M A(X). This property is illustrated in Figure 12, where it can be observed that the watershed (Figure 12(d)) of the distance map (Figure 12(b)) of Figure 12(a) is indeed a subset of the skeleton (Figure 12(c). More precisely, the watershed is composed by all the points of the skeleton that are adjacent to several connected components of its complementary set.

As far as we know, such a link between watershed and medial axis had never been established in a discrete framework. Moreover, in the framework of digital topology which is used in a majority of applications in image processing, fundamental properties like homotopy and thinness of skeletons cannot be both satisfied, as shown by the counter-examples of Figure 14.

Watershed on simplicial complexes. The work presented in [START_REF] Cousty | Collapses and watersheds in pseudomanifolds of arbitrary dimension[END_REF], which aims at establishing such links between watersheds and homotopy, holds true in a large family of n-dimensional discrete spaces, namely the pseudomanifolds. It is developed in the framework of simplicial complexes (triangulated objects) of arbitrary dimension, a pseudomanifold of dimension n being a simplicial complex without any « pinching of dimension n -1 » (see examples and counter-examples of pseudomanifolds in Figure 15). The first main contribution of [START_REF] Cousty | Collapses and watersheds in pseudomanifolds of arbitrary dimension[END_REF] is the definition of a watershed on these spaces that is based on the drop of water principle presented in Section 2.2.

Homotopy and watersheds. The second main contribution of [START_REF] Cousty | Collapses and watersheds in pseudomanifolds of arbitrary dimension[END_REF] is a property that establishes a relation between watershed and homotopy in this discrete framework. This link is even more general than the one discussed above in the continuous framework, as it holds true for arbitrary maps, distance maps being just a particular case, and for skeletons which are not necessarily medial axes. The notion of homotopy considered in [START_REF] Cousty | Collapses and watersheds in pseudomanifolds of arbitrary dimension[END_REF] relies on the collapse operation [START_REF] Whitehead | Simplicial Spaces, Nuclei and m-Groups[END_REF], a topology-preserving transformation known in algebraic topology. Then, it is proved in [START_REF] Cousty | Collapses and watersheds in pseudomanifolds of arbitrary dimension[END_REF] that any watershed of a map F is made of the closed contours of an ultimate collapse of the divide X of F (the elements of the space that do not belong to any regional minimum of F ), establishing a direct link between the watersheds of F and the homotopy type of X.

Watershed characterization with map homotopy. The third main contribution of [START_REF] Cousty | Collapses and watersheds in pseudomanifolds of arbitrary dimension[END_REF] is an equivalence result that establishes a deep link between watersheds and homotopy of maps, which is defined in [START_REF] Bertrand | Image segmentation through operators based upon topology[END_REF][START_REF] Couprie | Topological operators for grayscale image processing[END_REF] by considering the homotopy of every level sets of the considered maps. Intuitively, it states that a set X is a watershed of a map F if and only if there exists a so-called ultimate collapse H of F (this ultimate collapse is also a map) such that X is exactly the set of points adjacent to several distinct minima of H. To the best of our knowledge, no result of this kind has been obtained until now. Furthermore, due to this result, efficient algorithms based on homotopic transforms can be derived for computing a watershed of a map. [START_REF] Cousty | Collapses and watersheds in pseudomanifolds of arbitrary dimension[END_REF] is a property of thinness of watersheds and ultimate collapses in pseudomanifolds : in a pseudomanifold of dimension n, the dimension of any watershed The proposed notions can be used for segmenting the triangulated surfaces of 3D objects (see, e.g., Figure 16). Within this application context, the segmentation of simplicial complexes was the subject of many articles in the last decade. L. De Floriani et al. [START_REF] Comic | Smale-like decomposition and Forman theory for discrete scalar fields[END_REF][START_REF] Floriani | A Smale-like decomposition for discrete scalar fields[END_REF] tackled the problem as a Smalelike decomposition in discrete Morse theory (see also [START_REF] Jerše | Ascending and descending regions of a discrete Morse function[END_REF]) where the simplicial complex is segmented into ascending and descending subcomplexes. Based on the same theory, H. Edelsbrunner and J. Harer [START_REF] Edelsbrunner | The persistent Morse complex segmentation of a 3-manifold[END_REF] proposed another decomposition algorithm and they informally discuss some links with watershed algorithms. Furthermore, since the pioneering work of Mangan et al. [START_REF] Mangan | Partitioning 3D surface meshes using watershed segmentation[END_REF], many applications involving the segmentation of 3-dimensional meshes have been developed, often without mentioning explicitly simplicial complexes. The interested reader may refer to surveys articles [START_REF] Attene | Mesh segmentation -a comparative study[END_REF][START_REF] Shamir | A survey on mesh segmentation techniques[END_REF] or to the recent SHREC'12 Track : 3D mesh segmentation challenge [START_REF] Lavoué | SHREC'12 Track : 3D mesh segmentation[END_REF]. However, as far as we know, before the publication of [START_REF] Cousty | Collapses and watersheds in pseudomanifolds of arbitrary dimension[END_REF], a formal study of watersheds in simplicial complexes was not available.

Watershed dimension. An additional contribution of

The proposed framework can also be used for segmenting digital images equipped with triangular or cubical grids (see, e.g., Figure 17). Indeed, all notions and properties presented for simplicial complexes (which include the triangular grids) can be easily transposed (see [START_REF] Bertrand | Watersheds in discrete spaces[END_REF]) to the framework of cubical complexes (which include the cubical grids). Cubical complexes have been promoted in particular by V. Kovalevsky [START_REF] Kovalevsky | Finite topology as applied to image analysis[END_REF] in order to provide a sound topological basis for image analysis. Recent advances in this framework include the design of new image processing operators [START_REF] Couprie | New characterizations of simple points in 2D, 3D, and 4D discrete spaces[END_REF][START_REF] Liu | A simple and robust thinning algorithm on cell complexes[END_REF][START_REF] Robins | Theory and algorithms for constructing discrete Morse complexes from grayscale digital images[END_REF], new theoretical developments for considering the topology of digital label images [START_REF] Mazo | Topology on digital label images[END_REF], as well as applications in different fields such as computer graphics [START_REF] Noël | Coarse irradiance estimation using curvilinear skeleton[END_REF] or medical imaging [START_REF] Cardoso | Longitudinal cortical thickness estimation using Khalimsky's cubic complex[END_REF][START_REF] Cardoso | On the extraction of topologically correct thickness measurements using Khalimsky's cubic complex[END_REF].

x w z y z z z z X Y Z V W Figure 14.
Illustration of homotopic skeleton in 2D digital topology (X, Y, V, W ) and in cubical complexes (Z) : the object Y (black pixels) is an ultimate skeleton of X (black pixels). The foreground object in black is equipped with the indirect adjacency relation (also called 8-adjacency relation) and its complement, the background object in white, is equipped with the direct adjacency relation (also called 4-adjacency relation).

A homotopic skeleton (namely an ultimate collapse) Z of the two black objects X and Y considered in the framework of cubical complexes. (V ) : A homotopic skeleton in the hexagonal grid. The 6-adjacency relation is used for both the foreground (black) and background (white) objects. Any hexagon that is 6-adjacent to the black hexagon z is also black. (W ) A homotopic skeleton in the triangular grid. In this grid, we consider that any two black triangles that share a side or a vertex are adjacent. Note that any triangle adjacent to the black triangle z is also black. Thus, the three homotopic skeletons Z, V and W may be considered as "thick objects". A map F , an ultimate skeleton H of F and a watershed X of F . The map F , defined on the two dimensional cubical complex associated to the square grid (see e.g. [START_REF] Bertrand | Two-dimensional parallel thinning algorithms based on critical kernels[END_REF]), is obtained after some morphological filtering of an uranium oxyde image. The second (resp. third) row provides crops on a part of the images of the first (resp. second) row. The images of the third row also provide the interpretation of the images in terms of cubical complexes. As an illustration of the main result of this paper, it can be seen that the watershed X of F is also the set of the faces that are adjacent to two distinct regional minima of H.

HIERARCHICAL ANALYSIS

Hierarchical segmentations with graphs

Many image segmentation methods, such as the watershed cut method presented in Section 2.2, 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 detail levels, allowing the description of an object of interest as a union or a merging of several objects of interest that appear at lower detail levels. The level of a segmentation in the hierarchy is also called a scale (of observation). As noted by Guigues et al. [START_REF] Guigues | Scale-sets image analysis[END_REF], a hierarchy satisfies two important principles of multi-scale image analysis.

-First, the causality principle states that a contour presents at a scale k 1 should be present at any scale k 2 < k 1 . -Second, the location principle states that contours should be stable, in the sense that they do neither move nor deform from one scale to another. Since the early work of [START_REF] Pavlidis | Structural pattern recognition[END_REF], hierarchical image analysis has been the subject of intense research. For instance, one can refer to hierarchical watersheds, pioneered in [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], to quasi-flat zone hierarchies, studied notably in [START_REF] Meyer | Morphological scale-space representation with levelings[END_REF][START_REF] Nagao | Region extraction and shape analysis in aerial photographs[END_REF][START_REF] Soille | Constrained connectivity for hierarchical image partitioning and simplification[END_REF], to binary partition trees, introduced in [START_REF] Salembier | Binary partition tree as an efficient representation for image processing, segmentation, and information retrieval[END_REF], and to the scale-set theory, initiated in [START_REF] Guigues | Scale-sets image analysis[END_REF]. In the last few years, hierarchical segmentation has become a hot topic as attested by the popularity of [START_REF] Arbelaez | Contour detection and hierarchical image segmentation[END_REF], which presents a hierarchical segmentation machinery that reaches excellent practical results on the Berkeley image segmentation dataset [START_REF] Martin | A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics[END_REF][START_REF] Martin | Learning to detect natural image boundaries using local brightness, color, and texture cues[END_REF].

In [START_REF] Cousty | Hierarchical segmentations with graphs : quasi-flat zones, minimum spanning trees, and saliency maps[END_REF], we investigate a theory of hierarchical segmentation in graphs as used in image processing. More precisely, we investigate the relations between different representations of a hierarchy : by a dendrogram (direct set representation), by a saliency map (a characteristic function), and by a minimum spanning tree (a reduced domain of definition).

Intuitively, the saliency map of a hierarchical segmentation, as introduced in [START_REF] Najman | Geodesic saliency of watershed contours and hierarchical segmentation[END_REF], can be seen as an image of contours where the brightness of a region contour is proportional to the scale of the region in the hierarchy. More formally, given a graph G = (V, E) and a hierarchy H = (P 0 , . . . , P ) of partitions of V which is connected for G (i.e., any region in any partition of H is connected in G), the saliency map of H is the edge weight map Φ G (H) such that the weight of an edge u joining two vertices x and y is equal to the minimum index of a partition of H for which x and y belong to a same region. Figure 18 presents a (connected) hierarchy together with its dendrogram and saliency map representations.

The previous transform associates an edge weight map to any hierarchy. For our purpose of investigating relations between hierarchical representations, it is important to consider a « reverse » transform which associates a hierarchy to any edge weight map. To this end, the quasi-flat zones hierarchy of an edgeweighted graph is fundamental. Given an edge weight map w, the basic idea is to consider the connected component partitions of the (lower-) thresholds or level-sets of the map w, the threshold of w at a given level λ being simply the graph obtained by removing all edges whose weight is above λ. The series of (connected component) partitions obtained when the weight map is thresholded, in increasing order, at every possible weight value is a hierarchy, called the quasi-flat zones hierarchy of w. The quasi-flat zones hierarchy transform has long been used in image processing as a hierarchical image segmentation tool.

Bijection between saliency maps and hierarchies. The first major contribution of [START_REF] Cousty | Hierarchical segmentations with graphs : quasi-flat zones, minimum spanning trees, and saliency maps[END_REF] is a bijection theorem between connected hierarchies and saliency maps. In particular, it is shown that the inverse of the ‡. There also exist hierarchical image segmentation and filtering methods, such as, e.g., [START_REF] Salembier | Antiextensive connected operators for image and sequence processing[END_REF] and [START_REF] Monasse | Fast computation of a contrast-invariant image representation[END_REF] or watershed methods on the vertices of a graph (see e.g., Section 2.1), that deal with series of nested partial partitions (i.e., nested partitions of subsets of the image pixels). The study of these methods is beyond the scope of this manuscript. The interested reader can refer to [START_REF] Ronse | Ordering partial partitions for image segmentation and filtering : Merging, creating and inflating blocks[END_REF] for an algebraic study encompassing these methods. saliency map transform is the quasi-flat zones transform. In other words, given a hierarchy H, the quasi-flat zones hierarchy of the saliency map of H is necessarily H. Conversely, given a saliency map w, the saliency map of the quasi-flat zones hierarchy of w is precisely w. In this sense, we can say that H and Φ G (H) are two equivalent representations of a same hierarchy.

Characterization of saliency maps. The second major contribution of [START_REF] Cousty | Hierarchical segmentations with graphs : quasi-flat zones, minimum spanning trees, and saliency maps[END_REF] is a new characterization of the saliency map of a given hierarchy as the minimum function whose quasi-flat zones hierarchy is precisely the given hierarchy.

Characterization of minimum spanning trees. The third major contribution of [START_REF] Cousty | Hierarchical segmentations with graphs : quasi-flat zones, minimum spanning trees, and saliency maps[END_REF] is a new characterization of the minimum spanning trees of a given edge-weighted graph as the minimum subgraphs (for inclusion) whose quasi-flat zone hierarchies are the same as the one of the given graph. This result indicates that the quasi-flat zone hierarchy of a graph and of its minimum spanning trees are identical. Furthermore, it indicates that there is no proper subgraph of a minimum spanning tree that induces the same quasi-flat zone hierarchy as the initial weighted graph. Thus, a minimum spanning tree of the initial graph is a minimal graph representation of the quasi-flat zone hierarchy of the initial graph. More remarkably, a minimal representation of the quasi-flat zones hierarchy of an edge-weighted graph in this sense is necessarily a minimum spanning tree of the original graph. As far as we know, this characterization of minimum spanning tree is the first one relying on a notion introduced for image processing.

Efficient algorithms for saliency maps and quasi-flat zones hierarchy. We provide efficient original algorithms for computing (1) the quasi-flat zones hierarchy of an edge-weighted graph and (2) the saliency map of a hierarchy. Leveraging on the links established between quasi-flat zones hierarchies and minimum spanning trees, the algorithm that we propose in [START_REF] Najman | Playing with Kruskal : algorithms for morphological trees in edgeweighted graphs[END_REF] to compute quasi-flat zones hierarchies is a variation around Kruskal minimum spanning tree algorithm [START_REF]On the shortest spanning tree of a graph and the traveling salesman problem[END_REF], [129, chapter 23]. The time complexity of this algorithm is quasi-linear with respect to the size of the graph provided that the graph edges are either already sorted or can be sorted in linear time. Due to the algorithm that we propose in [START_REF] Cousty | Hierarchical segmentations with graphs : quasi-flat zones, minimum spanning trees, and saliency maps[END_REF], the saliency map of a hierarchy can be computed in linear-time from its tree-based (dendrogramme) representation. It has also to be noted that a minimum spanning tree of an edge weighted graph can also be efficiently computed in quasi-linear time [START_REF] Chazelle | A minimum spanning tree algorithm with inverse-ackermann type complexity[END_REF]. Hence, there is an efficient algorithm for obtaining any of the three studied hierarchical representations from any other one, allowing one to easily switch from one representation to another in applications.

The links established between the maps that weight the edges of a graph, the hierarchies on the vertex set of this graph, the saliency maps on the edges of this graph, and the minimum spanning trees for the maps that weight the edges of this graph are summarized in the diagram of Figure 19. These links constitute a necessary theoretical basis for the hierarchical analysis tools presented in the next sections.

Q F Z Saliency maps on E(G) Q F Z Connected hierarchies on V (G)

Maps on E(G)

Minimum spanning trees ⊆ (P 2 ): constrained minimization for (P 3 ): constrained minimization for the inclusion relation ⊑ on graphs.

the ≤ ordering on maps.

Ψ G Φ G (P 1 ): Φ -1 G = Q F Z Figure 19.
A diagram that summarizes the results of this section. The solutions to problems (P 1 ), (P 2 ), and (P 3 ) are quasi-flat zones, saliency maps and minimum spanning trees, respectively. The constraint involved in (P 2 ) and (P 3 ) is to leave the induced quasi-flat zones hierarchy unchanged. In the diagram, the symbols G, V (G), and E(G) are used to denote a connected graph, its vertex set, and its edge set respectively. The symbol QFZ stands for quasi-flat zones, and the symbols Φ G and Ψ G stand for the saliency map of a hierarchy and of a map respectively.

Hierarchical watershed cuts and minimum spanning forests

As seen in Section 2.2, a watershed cut of a map associates a region to every regional minimum of this map. We recall that, due to noise and texture, the maps derived from real-world images often have a huge number of regional minima, hence the mosaic aspect of watershed partitions (Figure 2.1(a)). In order to reduce this so-called over-segmentation, which is often unwanted in applications, two main processes have been considered in mathematical morphology.

1. The first one consists, starting from the watershed partitions, of iteratively merging pairs of adjacent regions until a certain criterion is satisfied.

2. The second process consists of filtering the map in order to reduce the number of its minima and considering the watershed partitions of the filtered map. In this case, the filtering is often controlled by a scalar parameter associated to the amount of minima (or the geometry, contrast, size, of the minima etc.) which must be suppressed by the filtering. The connected filters developed in mathematical morphology are well adapted to this task.

By its very construction, the first process builds a hierarchy and the second one builds a series of watershed partitions. It is therefore interesting to consider the following problems :

1. find some conditions such that the successive partitions produced by the first process are watershed segmentations.

2. Find some conditions that guarantee that the series of watershed partitions obtained under the variations of the filtering parameters in the second process make up a hierarchy (i.e. such that the partitions are nested).

These problems have long been considered in mathematical morphology and have shown to be closely related one to each other. However, as far as we know, before the publication of [START_REF] Cousty | Incremental algorithm for hierarchical minimum spanning forests and saliency of watershed cuts[END_REF][START_REF] Cousty | Constructive links between some morphological hierarchies on edge-weighted graphs[END_REF][START_REF] Najman | Playing with Kruskal : algorithms for morphological trees in edgeweighted graphs[END_REF], they do not receive any formal solution in discrete settings. Furthermore, the result of these processes is not in general a hierarchy of watersheds. The difficulties to tackle these questions are mainly due to the connection value preservation problem presented in Section 2.1.2 and to the region merging problems observed in Section 2.1.1. As shown in Section 2.2, in the framework of edge-weighted graphs, these two problems can be tackled with less difficulties. Therefore, we investigate in [START_REF] Cousty | Incremental algorithm for hierarchical minimum spanning forests and saliency of watershed cuts[END_REF][START_REF] Cousty | Constructive links between some morphological hierarchies on edge-weighted graphs[END_REF][START_REF] Najman | Playing with Kruskal : algorithms for morphological trees in edgeweighted graphs[END_REF] hierarchical watershed in edgeweighted graphs.

Hierarchies of minimum spanning forests and of watershed cuts. The first contribution of [START_REF] Cousty | Incremental algorithm for hierarchical minimum spanning forests and saliency of watershed cuts[END_REF] is a definition of minimum spanning forests (MSF) hierarchies and of watershed cuts hierarchies. MSFs can be used for marker-based segmentation (see [START_REF] Cousty | Watershed cuts : Minimum spanning forests and the drop of water principle[END_REF] and Section 2.2). Given an edge-weighted graph over the set of points to be studied (e.g., the pixels of an image) and a subset of points that mark the objects of interest, the problem is to find a spanning forest of minimum total weight such that each connected component is rooted in (i.e., contains exactly) one marker. The segmentation is then obtained as the connected components partition of the MSF. The resulting segmentation is therefore optimal in the sense of minimum spanning forests. If the markers are ranked by importance, an MSF hierarchy relative to these ranked markers is defined as a series of nested MSF such that the k-th MSF is rooted in the k-most important markers according to the ranking. Thus, when such series exists, one can obtain a series of associated nested partitions, hence a hierarchy of partitions where every partition is optimal. We recall that when the markers are the regional minima of the weight map the associated minimum spanning forest partitions are watershed segmentations defined by the drop of water principle [START_REF] Cousty | Watershed cuts : Minimum spanning forests and the drop of water principle[END_REF]. The minima are often ranked according to extinction values obtained from regional attributes [START_REF] Vachier | Extinction value : a new measurement of persistence[END_REF]. Extinction values can be computed from the component tree [START_REF] Salembier | Antiextensive connected operators for image and sequence processing[END_REF] of the weight map or directly from its quasi-flat zone hierarchy. Typical attributes are related to the area of the regions, their depth (also called dynamics [START_REF] Bertrand | On the dynamics[END_REF][START_REF] Grimaud | New measure of contrast : dynamics[END_REF]) or their volume. Intuitively, the extinction value of a minimum M for a given regional attribute is the smallest value λ M such that the minimum M « disappears » when all components with an attribute smaller than λ M are removed. The resulting hierarchies of partitions are called hierarchical watersheds. Figure 20 displays hierarchical watersheds of three images. For each image, two hierarchies are computed : for the first one, the minima are ranked with an area attribute and, for the second one, they are ranked by a dynamics attribute. Figure 21 shows the application of the same method for the segmentation of the surface of a 3D object represented as a mesh. The vertices of the considered graph are the triangles of the mesh and two vertices are linked by an edge if the corresponding triangles share a common side. The edges are weighted thanks to a curvature function.

Uprootings and MSF hierarchies. The second contribution of [START_REF] Cousty | Incremental algorithm for hierarchical minimum spanning forests and saliency of watershed cuts[END_REF] is the introduction of the uprooting transformation, which is a formalization of the first process presented above in the context of edgeweighted graphs, and a property which states that uprootings and MSFs hierarchies are equivalent, hence, providing a solution to the first problem stated above. Roughly speaking, given a weight map w and a ranking of the minima of w, an uprooting for w is a sequence of graphs (X 0 , . . . , X ) such that :

-X 0 is an MSF rooted in the minima of w ; -X i is obtained by adding to X i-1 the cheapest edge linking the connected component of X i-1 containing the minimum of rank i with a another connected component C of X i-1 . Hence, the connected component of X i-1 containing the minimum of rank i is "merged" to its neighboring connected component linked by the cheapest cost. Compatibility with morphological reconstruction. A desirable compatibility property in the context of morphological filtering is that any partition of a watershed hierarchy is a watershed cut of the geodesic reconstruction of the original map by the corresponding markers. In other words, it is desirable that under certain conditions (namely the filtering step is done by geodesic reconstruction) the two Figure 21. Illustration of the segmentation of the surface of a 3D object. First row : a triangular mesh, a crop on its associated dual graph, and its pseudo-inverse curvature. Second row : a saliency map representing a hierarchical segmentation of the surface. A framework for the indexing and retrieval of ancient artwork 3D models, using shape descriptors adapted to the surface regions of the segmentations, is detailed in Section 5.7. The mesh is provided by the French Museum Center for Research and Restoration (C2RMF, Le Louvre, Paris). strategies presented in the introduction of this section provide the "same results". A third major contribution of [START_REF] Cousty | Incremental algorithm for hierarchical minimum spanning forests and saliency of watershed cuts[END_REF] is a property stating that this is indeed true in the framework of edge weighted graphs. More precisely, given a hierarchy H = (P 0 , . . . , P ) of partitions and a ranking of the minima of a weight map w, the hierarchy H is an MSF hierarchy for this ordering if and only if, the partition P i is a watershed cut partition of the geodesic reconstruction of w by the markers of rank above i, for any i in {1, . . . , }.

Log-linear time MSF hierarchies algorithm. The fourth major contribution of [START_REF] Cousty | Incremental algorithm for hierarchical minimum spanning forests and saliency of watershed cuts[END_REF] is an algorithm to compute an uprooting of a map given any ranking of its minima, hence an MSF cut hierarchy relative to the given ranking of the minima. This algorithm runs in log-linear time with respect to the size of graph. It uses Tarjan's union find [START_REF] Tarjan | Efficiency of a good but not linear set union algorithm[END_REF] and Fredman and Tarjan's Fibonnacci heap [START_REF] Fredman | Fibonacci heaps and their uses in improved network optimization algorithms[END_REF] algorithms to manage collections of connected components and of edges adjacent to these connected components. It is also interesting to observe that this algorithm computes the resulting hierarchy in the form of a saliency map defined on the minimum spanning tree of the original graph, making use of the bijection between saliency maps and hierarchies presented in Section 3.1. If one needs the dendrogram representation of the hierarchy, the quasi-flat zone algorithm presented in [START_REF] Najman | Playing with Kruskal : algorithms for morphological trees in edgeweighted graphs[END_REF] can be used. An additional interesting feature of this algorithm is its incremental behavior : the first levels of the hierarchy are computed based only on the knowledge of the ranking of the less important minima. Thus, the ranking can be incrementally provided to the algorithm without any additional computational cost. As far as we know, the algorithm proposed in [START_REF] Cousty | Incremental algorithm for hierarchical minimum spanning forests and saliency of watershed cuts[END_REF], is the first saliency map algorithm compatible with the morphological filtering framework.

Constructive links between morphological hierarchies. In [START_REF] Cousty | Constructive links between some morphological hierarchies on edge-weighted graphs[END_REF], we provide a unified presentation of a family of popular morphological hierarchies in edge-weighted graphs : min-component trees, quasi flat zone hierarchies, binary partition trees (by altitude ordering), and hierarchy of watershed cuts. For any hierarchy of this family, we show if (and how) it can be obtained from any other element of the family. In this sense, the main contribution of [START_REF] Cousty | Constructive links between some morphological hierarchies on edge-weighted graphs[END_REF] is the study of all constructive links between these hierarchies.

Quasi-linear MSF hierarchies algorithm. Leveraging on these links, we derive in [START_REF] Najman | Playing with Kruskal : algorithms for morphological trees in edgeweighted graphs[END_REF] efficient quasi-linear time or linear time algorithms to compute these hierarchies. In particular, we provide in [START_REF] Najman | Playing with Kruskal : algorithms for morphological trees in edgeweighted graphs[END_REF] :

-a quasi-linear time algorithm that computes the binary partition tree by altitude ordering of an edge-weight map, provided that the edges are either already sorted or can be sorted in linear time. This binary partition tree is the fundamental structure that we substantially post-process to obtain the other hierarchies ; -a linear time post-processing algorithm that computes the quasi-flat zones hierarchy of the edge weight map ; -a linear time post-processing algorithm that computes a hierarchy of watershed cuts given a ranking of the minima of the weight map ; -a linear time post processing that ranks the minima of the weight map according to extinctions values by area, dynamics or volume. As far as we know, these algorithms are the most efficient known algorithms to compute the aforementioned hierarchies. Like the uprooting algorithm, this watershed cut hierarchy algorithm produces the resulting hierarchy in the form of a saliency map defined over the edges of the minimum spanning tree of the given edge-weighted graph, making again use of the bijection between saliency maps and hierarchies presented in Section 3.1.

Combinations of hierarchies

One difficulty in the design of many segmentation methods relies on combining different kinds of measures that are not necessarily homogeneous (e.g., the Mumford and Shah functional integrates photometric and boundary lengths measures). The same difficulty can occur with hierarchical segmentations, where different methods can capture distinct properties. With the hierarchical method presented in the previous section, the use of different attributes to rank the minima leads to hierarchies featuring different aspects of the image. For instance, with the area attribute, at the highest levels of the hierarchy, small regions vanish but low contrasted regions can remain. A high level of the area based hierarchies of Figure 20 is represented in the first column of Figure 23. On the other hand, with the dynamics attribute, the highest levels only contain contrasted regions but very small regions may remain. The second column of Figure 23 presents a high level of each of the dynamics based hierarchy shown in Figure 20. Attributes combining contrast and area can be designed, but such attributes would probably not be increasing. Attributes that are not increasing are known to be difficult to handle [START_REF] Salembier | Antiextensive connected operators for image and sequence processing[END_REF][START_REF] Urbach | Connected shape-size pattern spectra for rotation and scale-invariant classification of gray-scale images[END_REF] and to lead to hierarchies lacking some important stability properties such as the compatibility with the morphological filtering. Another approach, which we investigate in this section, consists of combining hierarchies. To this end, making use of the results presented in Section 3.1, we work on saliency maps instead of on the direct representation of the hierarchy. More precisely, the idea is to (1) consider the saliency maps of the hierarchy which are to be merged, (2) combine the weight of the saliency maps according to some functions from R 2 into R, such as, e.g., the min, the max or the average of the weights, and (3) consider the quasi flat zones hierarchy of the combination of saliency maps as the combined hierarchy. This approach was pioneered in [START_REF] Cousty | Raising in Watershed Lattices[END_REF] in the framework of graphs and with illustration in image segmentation. It was also investigated in [START_REF] Kiran | Fusion of ground truths and hierarchies of segmentations[END_REF] in the framework of Jordan nets in the Euclidean 2D plane R 2 , with applications to fusion of ground truths.

An important contribution of [START_REF] Cousty | Hierarchical segmentations with graphs : quasi-flat zones, minimum spanning trees, and saliency maps[END_REF][START_REF] Maia | Evaluation of combinations of watershed hierarchies[END_REF] is to explicit and to assess this later approach in the framework of graphs, which allows, in particular, for processing images of arbitrary dimension. Another contribution of [START_REF] Cousty | Hierarchical segmentations with graphs : quasi-flat zones, minimum spanning trees, and saliency maps[END_REF][START_REF] Maia | Evaluation of combinations of watershed hierarchies[END_REF] is to provide an efficient quasi-linear algorithm for the combinations of hierarchy by infimum, by supremum, and by average. Figure 22 presents, for each image of Figure 20 the saliency maps of the combination by average of the hierarchies obtained with the area and depth attributes (second and third column of Figure 20). One level of each of these hierarchies is represented in the third row of Figure 23 Figure 22. Hierarchies of partitions (depicted as saliency maps) obtained from the images of Figure 20 (first column). Each hierarchy is the combination by average of the hierarchical watersheds by area attribute (second column of Figure 20) and by dynamics attribute (third column of Figure 20) obtained from the images of Figure 20 (first column).

Hierarchizing graph-based image segmentation

In order to go beyond hierarchical watershed segmentations and to account for larger class of segmentation criteria, based on the framework of [START_REF] Cousty | Hierarchical segmentations with graphs : quasi-flat zones, minimum spanning trees, and saliency maps[END_REF], we made in [START_REF] Guimarães | Hierarchizing graph-based image segmentation algorithms relying on region dissimilarity : the case of the Felzenszwalb-Huttenlocher method[END_REF][START_REF] Guimarães | A hierarchical image segmentation algorithm based on an observation scale[END_REF] a first attempt towards a general theory for hierarchizing non-hierarchical image segmentation methods depending on a parameter which controls the desired level of simplification : each level of the hierarchy is "as close as possible" to the result that one would obtain with the non-hierarchical method using the corresponding scale as simplification parameter. The introduction of this hierarchization problem in the form of an optimization problem, as well as the proposed tools to tackle it, is an important contribution of [START_REF] Guimarães | Hierarchizing graph-based image segmentation algorithms relying on region dissimilarity : the case of the Felzenszwalb-Huttenlocher method[END_REF] which is detailed below. Indeed, with the hierarchized version of a segmentation method, the user can just select the level in the hierarchy, controlling the desired number of regions or can leverage on any of the tools introduced in hierarchical analysis. The main example investigated in this study is the criterion proposed by Felzenszwalb and Huttenlocher [START_REF] Felzenszwalb | Efficient graph-based image segmentation[END_REF].

As seen in Section 3.1, hierarchical analysis is closely related to minimum spanning trees. The first use of this tree in this context dates back to the seminal work of [START_REF] Zahn | Graph-theoretical methods for detecting and describing gestalt clusters[END_REF]. Lately, its use for image segmentation was introduced by Morris et al. [START_REF] Morris | Graph theory for image analysis : an approach based on the shortest spanning tree[END_REF] in 1986. In 2004, both Felzenszwalb and Huttenlocher [START_REF] Felzenszwalb | Efficient graph-based image segmentation[END_REF] and Nock and Nielsen [START_REF] Nock | Statistical region merging[END_REF] proposed an image segmentation method in which the pixel-merging order is similar to the creation of an MST, so-called "scale of observation". The methods, while being very effective in its own right, do not produce a hierarchy, and users face some major issues while tuning the method parameters.

-First, the number of regions may increase when the scale parameter increases. This should not be possible if this parameter was a true scale of observation : indeed, it violates the causality principle of multi-scale analysis. Such unexpected behavior of the Felzenszwalb-Huttenlocher method [START_REF] Felzenszwalb | Efficient graph-based image segmentation[END_REF] is demonstrated in Fig. 24 (b-d). -Second, even when the number of regions decreases, contours are not stable : they can move when the scale parameter varies, violating the location principle. Such situations generated by the Felzenszwalb-Huttenlocher method [START_REF] Felzenszwalb | Efficient graph-based image segmentation[END_REF] are also illustrated in Fig. 24 (b-d). Rather than trying to directly build the optimal hierarchy, a current trend in computer vision is to modify a first hierarchy into a second one, putting forward in the process the most salient regions. A seminal work in that direction is the one of Guigues et al. [START_REF] Guigues | Scale-sets image analysis[END_REF], which finds optimal cuts in the first hierarchy. This work has been extended in several directions, see for example [START_REF] Cardelino | A contrario selection of optimal partitions for image segmentation[END_REF] and [START_REF] Kiran | Global-local optimizations on hierarchies of segmentations[END_REF]. It is shown in [START_REF] Najman | On the equivalence between hierarchical segmentations and ultrametric watersheds[END_REF] that mathematical morphology provides tools and operators to modify hierarchies, in a spirit similar to what is achieved in [START_REF] Guigues | Scale-sets image analysis[END_REF]. In fact, hierarchies can be seen as weighted graphs (i.e., in the form of dendrograms whose nodes are equipped with a regional attribute) on which we can apply any graph-based operator [START_REF] Xu | Connected filtering on tree-based shape-spaces[END_REF], and the well-known watershed operator is itself related to an MST [START_REF] Cousty | Watershed cuts : Minimum spanning forests and the drop of water principle[END_REF]. However, such approaches cannot deal with criteria such as the ones proposed in [START_REF] Felzenszwalb | Efficient graph-based image segmentation[END_REF][START_REF] Nock | Statistical region merging[END_REF] for the merging of regions. It should be also mentioned that several authors [START_REF] Guigues | The hierarchy of the cocoons of a graph and its application to image segmentation[END_REF][START_REF] Haxhimusa | Irregular pyramid segmentations with stochastic graph decimation strategies[END_REF][START_REF] Haxhimusa | Segmentation graph hierarchies[END_REF][START_REF] Haxhimusa | Hierarchy of partitions with dual graph contraction[END_REF] proposed to build a hierarchy based on measures which are similar to the one proposed in [START_REF] Felzenszwalb | Efficient graph-based image segmentation[END_REF]. A survey of such hierarchical image segmentation methods can be found in [START_REF] Marfil | Pyramid segmentation algorithms revisited[END_REF].

In [START_REF] Felzenszwalb | Efficient graph-based image segmentation[END_REF], given a region dissimilarity and a scale of observation λ, a partition is said to be too fine at scale λ if there exits an adjacent-region pair whose dissimilarity is below the scale λ and the segmentation is said to be too coarse at scale λ, if there exists a refinement of the segmentation (i.e. a partition obtained by « splitting » some regions of the initial segmentation) which is not too fine. The method proposed in [START_REF] Felzenszwalb | Efficient graph-based image segmentation[END_REF], provides, given a certain observation scale λ, a partition which is neither too fine nor too coarse at scale λ when a particular dissimilarity is used.

Not-too-coarse/not-too-fine hierarchies. The first contribution of [START_REF] Guimarães | Hierarchizing graph-based image segmentation algorithms relying on region dissimilarity : the case of the Felzenszwalb-Huttenlocher method[END_REF] is the extension of this definition to hierarchies : a hierarchy is not-too-coarse (resp., fine) if, for any level λ, the partition at scale λ in the hierarchy is not too coarse (resp. fine) at scale λ. The example of Figure 24 shows that in general there is no hierarchy which is neither too coarse nor too fine. This difficulty motivates us to focus on hierarchies that are not-too-coarse (resp. fine) without being not-too-fine (coarse) at the same time. Such hierarchies always exist, whatever the chosen dissimilarity measure. Indeed, the trivial hierarchy whose levels are all the partition into singletons (resp., the partition into a single region containing all the points) is not too coarse (resp. fine). However, in general, there exist many hierarchies that are not too coarse (resp. fine) and one needs to choose among them.

Optimal not-too-coarse/not-too-fine hierarchies. The second contribution of [START_REF] Guimarães | Hierarchizing graph-based image segmentation algorithms relying on region dissimilarity : the case of the Felzenszwalb-Huttenlocher method[END_REF] is the introduction of an optimization problem in the lattice of hierarchies in order to make a choice in the large set of the hierarchies that are not-too-coarse (resp. fine). In order to present this problem, it is necessary to recall some notions for ordering hierarchies. A partition P is said smaller (or finer) than another partition P and P is said larger (or coarser) than P if the partition P is a refinement of P , i.e., the partition P can be obtained from P by splitting regions of and, conversely, P can be obtained from P by merging regions . The set of all partitions of V , together with the relation "is larger than", is a lattice [START_REF] Ronse | Ordering partial partitions for image segmentation and filtering : Merging, creating and inflating blocks[END_REF][START_REF] Serra | A lattice approach to image segmentation[END_REF]. The order relation "is larger than" on the partitions can be easily extended to the hierarchies : a hierarchy is larger than another if, at every level, the partition of the first hierarchy is larger than the partition of the second hierarchy. Having a lattice structure for hierarchies, it is then possible to define a notion of minimal/maximal hierarchies, leading to optimization in the lattice of hierarchies. Indeed, given a set H of hierarchies, an element H of H is said minimal (resp. maximal), whenever, for any hierarchy G of H such that G is smaller (resp. larger) than H, we have H = G. Hence, coming back to hierarchical image segmentation, it is relevant to consider the following optimization problem : find a maximal (resp. minimal) hierarchy in the set of all hierarchies which are not too coarse (resp. fine). In general, finding such a hierarchy is a complex task.

Hierarchizing method. The third contribution of [START_REF] Guimarães | Hierarchizing graph-based image segmentation algorithms relying on region dissimilarity : the case of the Felzenszwalb-Huttenlocher method[END_REF] is the proposition of a method to search for optimal not-too-coarse hierarchy, hence for hierarchizing the methods based on region dissimilarity such as [START_REF] Felzenszwalb | Efficient graph-based image segmentation[END_REF]. The proposed method is greedy and we cannot guarantee that the obtained hierarchy is nottoo-coarse. However, its computational cost makes it practicable for processing images. A first crux of the method is the handling of hierarchies by (saliency) maps defined over minimum spanning trees. The relation "is larger/smaller than" on hierarchies can be characterized using the relation "is less/greater than" on saliency maps. In particular, given two edge saliency maps w and w such that w(u) ≤ w (u) for any edge u, the associated quasi-flat-zone hierarchy of w is larger than the one of w . The algorithm presented in [START_REF] Guimarães | Hierarchizing graph-based image segmentation algorithms relying on region dissimilarity : the case of the Felzenszwalb-Huttenlocher method[END_REF] for searching a largest not-too-coarse hierarchy consists of iteratively lowering every weight of a map (while a certain condition is satisfied) starting from a map where all edges are initialized to a maximal value, i.e., a map corresponding to the smallest (not-too-coarse) hierarchy where all regions at all levels are singletons. Hence, the sequence of hierarchies associated to this sequence of maps are ordered from small to large.

When the dissimilarity measure of [START_REF] Felzenszwalb | Efficient graph-based image segmentation[END_REF] is considered it is shown in [START_REF] Guimarães | Hierarchizing graph-based image segmentation algorithms relying on region dissimilarity : the case of the Felzenszwalb-Huttenlocher method[END_REF] that the results on the Berkeley segmentation dataset [START_REF] Martin | A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics[END_REF][START_REF] Martin | Learning to detect natural image boundaries using local brightness, color, and texture cues[END_REF] of the hierarchized version of the segmentation method are better than those of the original one with the added property that it satisfies the strong causality and location principles from scale-sets image analysis. This technique being generic, it was furthermore applied in [START_REF] Guimarães | A graph-based hierarchical image segmentation method based on a statistical merging predicate[END_REF] and [START_REF] Guimarães | Hierarchical image segmentation relying on a likelihood ratio test[END_REF] to the measures presented in [START_REF] Nock | Statistical region merging[END_REF] and [START_REF] Peng | Automatic image segmentation by dynamic region merging[END_REF] respectively. Last, but not the least, considering the current trend in computer vision, an interesting perspective is obviously, on a specific application, to use learning techniques and train a measure to choose the correct region. First results in that direction are encouraging [START_REF] Couprie | Convolutional nets and watershed cuts for realtime semantic labeling of rgbd videos[END_REF].

Directed component hierarchies

As seen in previous sections, graph algorithms are effective for processing and analyzing images. Graphs allow for the representation of various adjacency relations (the edges) between pixels (the vertices). Weights can be defined both on the vertices in order to represent some information (e.g. luminance) and on the edges as a relationship measure. Following the historical symmetric definition of adjacency [START_REF] Rosenfeld | Connectivity in digital pictures[END_REF][START_REF] Rosenfeld | Adjacency in digital pictures[END_REF], most methods rely on undirected graphs as studied in previous sections. Some recent work aims at extending these methods beyond the symmetry hypothesis in order to improve popular image segmentation algorithms. This work leads to different algorithms based on the directed graph framework, and generally shows an ability to take into account more information than their symmetric counterparts. Such work includes min-cuts [START_REF] Boykov | Graph cuts and efficient N-D image segmentation[END_REF], random-walkers [START_REF] Singaraju | Interactive image segmentation via minimization of quadratic energies on directed graphs[END_REF], and shortest path forests [START_REF] Miranda | Oriented image foresting transform segmentation by seed competition[END_REF]. Following these successful attempts, we explore in [START_REF] Perret | Directed connected operators : asymmetric hierarchies for image filtering and segmentation[END_REF] how directed graphs can enrich and improve another family of graph operators based on hierarchies : the connected operators.

Connected operators [START_REF] Breen | Attribute openings, thinnings, and granulometries[END_REF][START_REF] Heijmans | Connected morphological operators for binary images[END_REF][START_REF] Salembier | Flat zones filtering, connected operators, and filters by reconstruction[END_REF] are effective image processing tools studied in the framework of mathematical morphology. They have been successful in a wide spectrum of applications (see [START_REF] Salembier | Connected operators : A review of region-based morphological image processing techniques[END_REF][START_REF] Salembier | Connected operators based on tree pruning strategies[END_REF] for recent surveys). Connected operators focus on the notion of connected components. The basic idea is that the only allowed operation is the deletion of a connected component (either from the object or from its complementary set), thus ensuring that the operators can neither create nor shift any contour. The extension of this approach to grayscale images (vertex or edge weighted graphs) leads to the definition of several hierarchical representations : the component tree [START_REF] Salembier | Antiextensive connected operators for image and sequence processing[END_REF], the binary partition tree [START_REF] Salembier | Binary partition tree as an efficient representation for image processing, segmentation, and information retrieval[END_REF], the tree of shapes [START_REF] Monasse | Scale-space from a level lines tree[END_REF] or the quasi-flat zones hierarchy [START_REF] Meyer | Morphological scale-space representation with levelings[END_REF]. Significant effort has been devoted to efficiently construct these hierarchies [START_REF] Najman | Playing with Kruskal : algorithms for morphological trees in edgeweighted graphs[END_REF][START_REF] Carlinet | A comparative review of component tree computation algorithms[END_REF][START_REF] Géraud | A quasi-linear algorithm to compute the tree of shapes of nD images[END_REF][START_REF] Najman | Building the component tree in quasi-linear time[END_REF][START_REF] Salembier | Antiextensive connected operators for image and sequence processing[END_REF] and to understand the relations that exist between them [START_REF] Cousty | Constructive links between some morphological hierarchies on edge-weighted graphs[END_REF]. A general definition scheme for a connected operator consists of four steps : (1) construct the image hierarchical representation ; (2) compute attributes for each region / node of the representation ; (3) select relevant nodes according to these attributes ; and (4) produce a filtered image or a segmentation map. For instance, the ranking of the minima by extinction value and the geodesic reconstruction used for hierarchical watersheds fall in the category of connected filters. More generally, connected operators have been used for filtering [START_REF] Salembier | Antiextensive connected operators for image and sequence processing[END_REF], segmentation [START_REF] Jones | Connected filtering and segmentation using component trees[END_REF], interactive segmentation [START_REF] Passat | Interactive segmentation based on component-trees[END_REF][START_REF] Westenberg | Volumetric attribute filtering and interactive visualization using the max-tree representation[END_REF], retrieval [START_REF] Chen | Using dendronal signatures for feature extraction and retrieval[END_REF], classification [START_REF] Urbach | Connected shape-size pattern spectra for rotation and scale-invariant classification of gray-scale images[END_REF], and registration [START_REF] Mattes | Tree representation for image matching and object recognition[END_REF]. Applications range from biomedical imaging [START_REF] Dufour | Filtering and segmentation of 3D angiographic data : Advances based on mathematical morphology[END_REF][START_REF] Wilkinson | Shape preserving filament enhancement filtering[END_REF], to astronomy [START_REF] Berger | Image processing[END_REF][START_REF] Perret | Connected component trees for multivariate image processing and applications in astronomy[END_REF], via remote sensing [START_REF] Alonso-González | Processing multidimensional SAR and hyperspectral images with binary partition tree[END_REF][START_REF] Kurtz | Extraction of complex patterns from multiresolution remote sensing images : A hierarchical top-down methodology[END_REF] and document analysis [START_REF] Naegel | A document binarization method based on connected operators[END_REF][START_REF] Perret | Hyperconnections and hierarchical representations for grayscale and multiband image processing[END_REF]. Connected operators provide well-established solutions for digital image processing, typically in conjunction with hierarchical schemes. In graph-based frameworks, such operators basically rely on symmetric adjacency relations between pixels.

Directed connected component. The first contribution of [START_REF] Perret | Directed connected operators : asymmetric hierarchies for image filtering and segmentation[END_REF] is the introduction of the notion of a directed connected component (see also [START_REF] Ronse | Axiomatics for oriented connectivity[END_REF] for an algebraic framework generalizing this graph-based notion). Given any vertex x of a directed graph, the directed connected component, or D-component, of basepoint x is the set of all vertices which can be reached from x with an ordered path (see illustration in Figure 25). When the graph is symmetric, the D-component of basepoint x is the connected component containing x and the set of all D-components of any symmetric graph partitions the graph vertices. However, when the graph is not symmetric, the D-components of two different basepoints may overlap without being equal. Hence, the the set of all D-components of a non-symmetric directed graph is no longer a partition of the graph vertices. We have establish a bijection between the D-components of a graph and its strongly connected components, the strongly connected component of a vertex x being the set of all vertices of the graph that can be reached from x and from which we can come back to x with ordered paths. Strongly connected components are well studied in graph theory and partition graph vertices. Hence, this bijection result helps in practice the handling of directed connected component.

Directed components hierarchy. The second main contribution of [START_REF] Perret | Directed connected operators : asymmetric hierarchies for image filtering and segmentation[END_REF] is the unification and the generalization to directed graphs of the definitions of the min/max-tree of a vertex weighted graph, min/max-tree of an edge-weighted graph, and the quasi-flat zones hierarchy of an edge-weighted graph. The generalization is obtained by (1) considering a series of nested directed graphs, called a stack of graphs, instead of a weighted undirected graph, and (2) considering the set of all D-components of each graph in this stack instead of its connected components. The directed component hierarchy of a stack of graphs is then the set of the D-components of all the directed graphs in the stack. When the stack of graphs is induced by thresholding at every possible values, in increasing/decreasing order, a vertex weighted undirected graph, then the notion of min/max-tree of a vertex weighted graph is recovered. When the stack of graphs is induced by thresholding at every possible values an edge-weighted undirected graph, then the notion of min/max-tree of an edge-weighted graph is recovered, and when every single vertex is furthermore added to every graph of the stack, the notion of quasi-flat zones hierarchy is recovered. Note that this framework also allows one to consider a graph which is weighted simultaneously on both its edges and vertices. However, when the graphs of the stack are directed and not symmetric, the set of all D-components, namely the directed component hierarchy of the stack, is no more a tree of components but a directed acyclic graph (DAG) of components. The directed component hierarchy is the key representation to perform directed connected filtering as presented in the following paragraphs.

Algorithm for directed components hierarchy. The third main contribution of [START_REF] Perret | Directed connected operators : asymmetric hierarchies for image filtering and segmentation[END_REF] is an efficient algorithm for building the directed component hierarchy of a stack of graphs. The algorithm has a O( .n) time complexity, where n is the size of the graph and where is the number of levels in the stack, that is to say the number of weight values when the stack is induced by a weight function.

Directed connected filtering. The fourth main contribution of [START_REF] Perret | Directed connected operators : asymmetric hierarchies for image filtering and segmentation[END_REF] is the introduction of several strategies, called directed connected filterings, to select relevant nodes of a D-component hierarchy in order to handle the increased complexity of D-component hierarchies compared to standard component trees. These strategies are designed to ensure the consistency of the node selection process in terms of D-components. Thinking in terms of directed connected operators, one may desire to mark each D-component as selected or as discarded. However, in contrast to the case of connected operators, we may fall into situations such as the one depicted in Fig. 4(b), where two D-components overlap. This creates an ambiguous situation if one of them is selected while the other is not selected, hence discarded. It is not obvious to decide whether the overlaping of the components (vertex labeled b in Figure 25(b)) must be filtered out or kept in the result. Given a Boolean criterion on components (examples of criteria are presented in the next paragraph), this observation leads us to the proposition of two strategies for filtering the D-components of a graph where priority is either given to the selected components (in our example of Figure 25(b), {b} would then be kept) or to the discarded ones (in our example of Figure 25(b), {b} would then be removed). When a stack of graphs is considered, one faces a similar choice when the criterion holds true for a region A at a given level and holds false for a region B which includes A at a higher level. Overall, given a filtering Boolean criterion on components, we identify in [START_REF] Perret | Directed connected operators : asymmetric hierarchies for image filtering and segmentation[END_REF] a total of four strategies to filter the D-component hierarchy, hence to perform directed connected filtering of an image.

Image processing with directed connected filters. The fifth main contribution of [START_REF] Perret | Directed connected operators : asymmetric hierarchies for image filtering and segmentation[END_REF] is the illustration of the relevance and of the versatility of directed connected filtering for processing images. To this end, three applications are presented where asymmetric information is taken into account in the form of a directed graph defined over the image pixels. The first application deals with blood vessels segmentation in retinal images. The basic idea is to consider the image as a directed graph where each pixel x is adjacent (1) to its four closest spatial neighbors as usually done with the 4-adjacency symmetric relation and ( 2) to its k nearest neighbors in a feature space in which all pixels are mapped. Here, we consider that a pixel x is closer to y than to z in the feature space if y is brighter than z. Whereas the neighboring relation resulting from ( 1) is symmetric the one resulting from ( 2) is strongly asymmetric, hence the need for directed filters to perform the segmentation. Note that this graph construction is often used in application (see, e.g., [START_REF] Felzenszwalb | Efficient graph-based image segmentation[END_REF]) without considering its asymmetric aspect, i.e., the symmetric closure of the graph is generally used : when an arc is found from a vertex x to a vertex y, the reverse arc from y to x is also added to obtain a symmetric graph. Then, the segmentation mask is obtained by discarding all D-components that are too small or not elongated enough. Figure 26 presents a result obtained by this method. Quantitatively, this method also compares favorably to other methods used on the standard DRIVE dataset [START_REF] Staal | Ridge-based vessel segmentation in color images of the retina[END_REF] and it is shown that considering the directed graph leads to better performance than considering its symmetric closure. The second application is the filtering of neurite images (see Figure 27). Finally, the last application considers the integration of prior asymmetric knowledge in a marker-based MRI myocardium segmentation procedure. Here, the criterion is to select the components of the hierarchy (induced by an edge-weighted graph) which intersect the user provided foreground marker but which do not intersect the background marker. For this application, it is known that some extremal intensity pixels are likely to not belong to the myocardium since they in general correspond to blood and fat (very bright) or to lungs (very dark). To prevent the connection of this pixel from the object marker the arcs ending at these pixels are penalized by multiplying their cost by a constant greater than one. Here, the graph is symmetric, but the weight of an arc from a vertex x to a vertex y is not necessarily the same as the weight of the arc from y to x (when one of them is preclassified as background while the other is not). The results of this procedure and of its symmetric counterpart (i.e. when the weight of the arcs ending at background preclassified pixels is not multiplied) are presented in Figure 28.

Directed connection value and oriented Image Foresting Transform. Interestingly, the last marker-based segmentation procedure presented in the previous paragraph and which is defined through the notion of a D-component hierarchy is the same as the oriented Image Foresting Transform (IFT) presented in [START_REF] Miranda | Oriented image foresting transform segmentation by seed competition[END_REF]. We recall that the Image Foresting Transform is defined thanks to shortest paths forests and can be computed, in the case of undirected graphs, with Dijkstra algorithm. In order to show the relation between the IFT and the proposed method, a notion of directed connection value is introduced in [START_REF] Perret | Directed connected operators : asymmetric hierarchies for image filtering and segmentation[END_REF]. The directed connection value from a vertex x to a vertex y is the minimum value γ such that there is a directed path from x to y the maximum value of which is γ. It can be shown that the segmentation method presented in the previous paragraph solve the following problem : find the set of vertices whose directed connection value from a vertex marked as object is less than the one to a vertex marked as background. This, second characterization of the marker-based segmentation method presented in the previous paragraph corresponds exactly to the method called oriented IFT in [START_REF] Miranda | Oriented image foresting transform segmentation by seed competition[END_REF].

MATHEMATICAL MORPHOLOGY FILTERING BY ADJUNCTION

From a formal point of view, digital image processing historically consists of analyzing the transformations that act on the subsets of Z 2 (the sets of pixels in a binary image) and the transformations that act on the maps from Z 2 to N (the images themselves). In such a perspective, mathematical morphology provides a set of filtering and segmenting tools that are very useful in applications.

On the other hand, there is a growing interest for considering digital objects not only composed of points but also composed of elements lying between them and carrying structural information about how the points are glued together (see [START_REF] Cousty | Watershed cuts : Minimum spanning forests and the drop of water principle[END_REF][START_REF] Dias | Dimensional operators for mathematical morphology on simplicial complexes[END_REF][START_REF] Bloch | Mathematical morphology on hypergraphs, application to similarity and positive kernel[END_REF][START_REF] Couprie | New characterizations of simple points in 2D, 3D, and 4D discrete spaces[END_REF][START_REF] Loménie | Morphological mesh filtering and α-objects[END_REF][START_REF] Ta | Partial difference equations over graphs : Morphological processing of arbitrary discrete data[END_REF] for recent examples). The simplest of these representations are the graphs. In Section 2.3, we have also quoted simplicial complexes, a generalization of the graphs allowing one to consider more topological invariants. Some recent work also shows the interest of hypergraphs [START_REF] Bloch | Mathematical morphology on hypergraphs, application to similarity and positive kernel[END_REF] and of formal concepts [START_REF] Atif | Mathematical morphology operators over concept lattices[END_REF][START_REF] Bloch | Morphological links between formal concepts and hypergraphs[END_REF] for processing images or even more general data. The domain of an image is then considered as a structure whose vertex set is made of the pixels and whose edge set is given by an adjacency relation on these pixels. Note that this adjacency relation can be either spatially invariant or spatially variant leading to operators that are either spatially invariant or spatially variant (see e.g. [START_REF] Lerallut | Image filtering using morphological amoebas[END_REF][START_REF] Stawiaski | Minimum spanning tree adaptive image filtering[END_REF][START_REF] Tankyevych | Spatially-variant morpho-hessian filter : Efficient implementation and application[END_REF][START_REF] Verdú-Monedero | Spatially-variant anisotropic morphological filters driven by gradient fields[END_REF] for examples of spatially variant morphological operators). In this context, it becomes relevant to consider the transformations acting on the set of all subgraphs (or all subcomlexes, etc.) and not only those acting on the set of all subsets of pixels. Such trend is also recently observed in signal processing [START_REF] Shuman | The emerging field of signal processing on graphs : Extending high-dimensional data analysis to networks and other irregular domains[END_REF].

The different operators created in the field of mathematical morphology can be regarded with respect to two main axiomatic sources sometimes referred to as connection and adjunction. The first one relies on preserving topological invariants (such as the number of connected components) of the image. The associated operators encompass the watershed transforms and region merging schemes presented in Section 2, the hierarchical segmentation tools and the connected filters presented in Section 3 as well as homotopicthinning and skeletonization operators (see a brief introduction in Section 2.3 or more complete surveys in [START_REF] Couprie | Discrete topological transformations for image processing[END_REF][START_REF] Saha | A survey on skeletonization algorithms and their applications[END_REF]). The operators of the second category focus on regularizing or simplifying the shapes of an image (or more generally of a dataset) regardless to an explicit connected component preservation constraint. They rely on an algebraic relation between operators called a Galois connection [START_REF] Birkhoff | Lattice theory[END_REF] or an adjunction [START_REF] Serra | Image Analysis and Mathematical Morphology[END_REF]. Such relation leads to morphological opening and closing by adjunction and encompass well-known mathematical morphology operators based on structuring elements. The two sources are not incompatible, and one can combine their axioms. Whereas Section 2 and 3 focus on connections, the present section is exclusively devoted to mathematical morphology filtering by adjunction on two discrete settings : the graph and the simplicial complexes. Before presenting the main contributions of [START_REF] Cousty | Morphological filtering on graphs[END_REF][START_REF] Dias | Dimensional operators for mathematical morphology on simplicial complexes[END_REF][START_REF] Youkana | Parallelization strategy for elementary morphological operators on graphs : algorithms and implementation on multicore/multithreaded architecture[END_REF][START_REF] Dias | Some morphological operators on simplicial complex spaces[END_REF] on this matter § , let us introduce some fundamental notions related to morphological filtering by adjunction.

The algebraic basis of mathematical morphology by adjunction is the lattice structure and the morphological operators act on lattices [START_REF] Heijmans | The algebraic basis of mathematical morphology. I Dilations and erosions[END_REF][START_REF] Ronse | Algebraic foundations of morphology[END_REF][START_REF] Serra | Image Analysis and Mathematical Morphology[END_REF]. In other words, the morphological operators map the element of a first lattice to the elements of a second one (which is not always the same as the first one). A (complete) lattice is a partially ordered set such that for any family of elements, we can always find a least upper bound and a greatest lower bound (called a supremum and an infimum). The supremum (resp., infimum) of a family of elements is then the smallest (greatest) element among all elements greater (smaller) than or equal to every element in the considered family. The classical lattice for binary image processing contains all shapes which can be drawn in the considered image, namely it is the family of all subsets of image pixels. The supremum is given by the union and the infimum by the intersection. A morphological operator is then a mapping that associates to any subset of pixels (a shape) another subset of pixels. In the lattice setting, a filter is an operator which is both increasing and idempotent meaning that (1) if we have two ordered elements, then the results of the operator applied to these elements are also ordered, so the §. A part of this work was developed during the PhDs of Fabio Dias [START_REF] Dias | A study of some morphological operators in simplicial complex spaces[END_REF] and Imane Youkana [START_REF] Youkana | Parallelization of Morphological Operators Based on Graphs[END_REF]. morphological operators preserve order and (2) after applying a filter to an element of the lattice, applying it again does not change the result. When a filter is extensive (i.e., when the result is always larger than the operand), it is called a closing and when it is anti-extensive (i.e., when the result is always smaller than the operand) it is called an opening. Intuitively, a filter can the be seen as an abstraction of the sieving process performed, e.g., by a gold miner who wants to separate gold nuggets form sand. Indeed, in such a process if the miner puts what remains in his sieve a second time in the same sieve then he does not remove any more sand (idempotence of the process) and if he has two buckets A and B of materials, if he puts the content of A and B together at the same time in his sieve then the quantity of gold remaining in his sieve is necessarily more important than if he puts only the content of A (increasingness of the process).

As said previously, the algebraic framework of morphology relies mostly on a relation between operators called an adjunction [START_REF] Heijmans | The algebraic basis of mathematical morphology. I Dilations and erosions[END_REF][START_REF] Serra | Image Analysis and Mathematical Morphology[END_REF]. Two operators : L 1 → L 2 and δ : L 2 → L 1 form an adjunction ( , δ) when for any X in L 2 and any Y in L 1 , we have δ(X) ≤ 1 Y if and only if X ≤ 2 (Y ), where ≤ 1 and ≤ 2 denote the order relations on respectively the lattice L 1 and the lattice L 2 . In this case is called an erosion and δ is called a dilation. It is well known that an operator is a dilation (resp., erosion) if and only if it commutes under supremum (resp., infimum). This adjunction relation is particularly interesting because it allows the extension of a single operator to a whole family of other interesting operators : having a dilation (resp., an erosion), an (adjunct) erosion (resp., a dilation) can always be derived, then by applying successively these two adjunct operators a closing and an opening are obtained in turn (depending which of the two operators is first applied), and composing this opening and closing leads to alternating filters. Furthermore, when the elementary dilations/erosions are iterated, series of ordered filters, called granulometries, can be obtained leading to size distribution analysis. Each of these operators satisfy a set of remarkable properties that are interesting in particular in the context of noise cleaning (more details on the use of morphological operators for image denoising are provided in the next paragraphs).

Filtering on graphs

Mathematical morphology on graphs was pioneered by Vincent [START_REF] Vincent | Graphs and mathematical morphology[END_REF] who considers the lattice of all subsets of vertices of a graph. In this lattice the supremum and infimum are simply the union and intersection of subsets of vertices. Hence, the operators investigated in [START_REF] Vincent | Graphs and mathematical morphology[END_REF] act on the vertices of a graph. In this lattice, a « natural » dilation maps any subset of vertices to the vertices that are neighbors of a vertex in that subset. This « natural » dilation is called the vertex-vertex dilation in the following. The adjunct vertex-vertex erosion is then the set of all vertices whose neighborhood is included in the initial set. From a methodological viewpoint, in the usual framework of mathematical morphology, one has to choose a structuring element that parametrizes the operator. With morphology on graph, the choice of a structuring element is, in general, replaced by the choice of the edge set that indicates which data are connected (see [START_REF] Heijmans | Graph morphology[END_REF][START_REF] Heijmans | Graph morphology in image analysis[END_REF] for a framework of morphology in graphs where one must choose both an edge set and a second "graph" that plays the role of a structuring element). In the digital setting, there is a direct correspondence between these two approaches. Indeed, when the vertex set of the graph is a subset of the grid points Z d and when the edge set is obtained from a symmetrical structuring element, then the vertexvertex dilations and erosions defined above are equivalent to the usual binary dilation and erosion by the considered structuring element as presented in standard textbook of mathematical morphology. However, the use of graphs opens the door to the processing of many kind of data and to new operators such as those described in the next paragraphs.

In particular, one can guess that dealing also with the edges of a graph can help for reaching a better « precision » [START_REF] Cousty | Watershed cuts : Minimum spanning forests and the drop of water principle[END_REF][START_REF] Cousty | Morphological filtering on graphs[END_REF][START_REF] Meyer | Micro-viscous morphological operators[END_REF][START_REF] Meyer | Morphological operators for flooding, leveling and filtering images using graphs[END_REF]. This was the motivation for defining the analog "natural" dilation of a subset of edges [START_REF] Cousty | Morphological filtering on graphs[END_REF][START_REF] Cousty | Some morphological operators in graph spaces[END_REF]. In order to account for the edges of a graph, one can a straightforwardly consider the lattice of all subsets of edges [START_REF] Cousty | Morphological filtering on graphs[END_REF][START_REF] Cousty | Some morphological operators in graph spaces[END_REF]. The supremum and infimum in this lattice are also the union and the intersection. Then, the « natural » edge-edge dilation of a subset of edges contains all edges which are adjacent to (i.e. which share a common vertex with) an edge in the initial subset. The adjunct edge-edge erosion of a subset of edges contains each edge whose neighborhood (i.e. the set of all edges adjacent to a given edge) is included in the initial subset.

Lattice of graphs. To bring mathematical morphology on graphs one step further, it interesting to consider a lattice whose elements are graphs, so that the operands and the results of the operators are both graphs. In particular, when the workspace is a graph, it is interesting to consider the lattice of all its subgraphs [START_REF] Cousty | Morphological filtering on graphs[END_REF][START_REF] Cousty | Some morphological operators in graph spaces[END_REF] : a graph is a subgraph of another when both the vertex and edge sets of the two graphs are included in each other. In the lattice of subgraphs, the supremum or union (resp., the infimum or intersection) of two graphs is defined by the union (resp., intersection) of the vertex and edge sets. Some elementary properties of this lattice are investigated in [START_REF] Cousty | Morphological filtering on graphs[END_REF]. In particular, it is shown that the lattice is not complemented and a minimal sup-generator of this lattice is provided.

« Natural » dilation/erosion on graphs. The first main contribution of [START_REF] Cousty | Morphological filtering on graphs[END_REF][START_REF] Cousty | Some morphological operators in graph spaces[END_REF] is the study of elementary operators in this lattice of graphs. Interestingly, when one applies simultaneously the vertexvertex and edge-edge dilations to the vertex and edge sets of a subgraph, the resulting pair of edge and vertex sets is still a subgraph, thus defining a « natural » dilation on subgraphs [START_REF] Cousty | Morphological filtering on graphs[END_REF][START_REF] Cousty | Some morphological operators in graph spaces[END_REF]. The adjunct erosion is obtained by the simultaneous applications of the vertex-vertex and edge-edge erosions. We emphasize that, contrarily to the previous work on morphology in graphs (such as [START_REF] Bloch | Mathematical morphology on hypergraphs, application to similarity and positive kernel[END_REF][START_REF] Heijmans | Graph morphology in image analysis[END_REF][START_REF] Loménie | Morphological mesh filtering and α-objects[END_REF][START_REF] Meyer | Micro-viscous morphological operators[END_REF][START_REF] Meyer | Morphological operators for flooding, leveling and filtering images using graphs[END_REF][START_REF] Ta | Partial difference equations over graphs : Morphological processing of arbitrary discrete data[END_REF][START_REF] Vincent | Graphs and mathematical morphology[END_REF]), the operand and the result of these operators are both graphs. This property can impact the results of further processing where connectivity and adjacency are involved [START_REF] Ouzounis | Mask-based second-generation connectivity and attribute filters[END_REF][START_REF] Ronse | Set-theoretical algebraic approaches to connectivity in continuous or digital spaces[END_REF][START_REF] Salembier | Flat zones filtering, connected operators, and filters by reconstruction[END_REF]. For instance, using the definition of a vertex-vertex dilation [START_REF] Vincent | Graphs and mathematical morphology[END_REF], dilating the subset X of red and blue vertices of Figure 29a leads to the set of red and blue vertices of Figure 29c which is connected. On the other hand, using the definition of a dilation of a subgraph [START_REF] Cousty | Morphological filtering on graphs[END_REF], dilating the subgraph induced by X (depicted in red and blue in Figure 29b) leads to the red and blue subgraph shown in Figure 29d which is not connected. However, in the last example the two connected components (i.e. the red and the blue subgraphs of Figure 29d) are adjacent to each other. Intuitively, one may say that, on this example, the operator acting on subgraphs reaches a better precision than the one acting on subsets of vertices by allowing to make the distinction between adjacency and connectedness. The evaluation of the practical impact of such distinction is beyond the scope of this chapter. In fact, as we will see in the next paragraphs the usual framework can be further enriched when one also considers operators which map set of edges to set of vertices and vice-versa.

Edge-vertex adjunctions. A second major contribution of [START_REF] Cousty | Morphological filtering on graphs[END_REF][START_REF] Cousty | Some morphological operators in graph spaces[END_REF] is the definition and study of four operators that are elementary building blocks for morphology in graphs. The originality of these operators lies in the fact that the operands and the results do not belong to the same lattice : one is a vertex set whereas the other is an edge set. Interestingly, these operators allow us to characterize and enrich the morphological operators presented the previous paragraph. More precisely :

1. the vertex-edge dilation is a dilation that maps any set of vertices to the set of edges that contain at least one of these vertices ;

2. the edge-vertex erosion, which is the adjunct erosion of the previous vertex-edge dilation, maps any set of edges to the set of vertices completely surrounded by edges of this set of edges (i.e., vertices whose adjacent edges all belong to this set of edges) ;

3. the edge-vertex dilation is a dilation that maps any set of edges to the set of vertices which are contained in one of these edges ; and 4. the vertex-edge erosion, which is the adjunct erosion of the previous edge-vertex dilation, maps any set of vertices to the set of edges whose two extremities lie in the initial set of vertices.

These operators are illustrated in Figure 30. The vertex-vertex (resp., edge-edge) dilation is simply the composition of the vertex-edge (resp., edge-vertex) dilation and the edge-vertex (resp., vertex-edge) dilation, whereas the adjunct vertex-vertex erosion (resp., edges) is the composition of the vertex-edge (resp., edgevertex) erosion and the edge-vertex (resp., vertex-edge) erosion. Since the four operators defined above can be grouped as pairs of adjunct operators, they also lead to openings and closings. For instance, the successive application of the vertex-edge dilation and the edge-vertex erosion is the closing which, given a set of vertices, fills in the points which do not belong to the set but which are completely surrounded by that set (i.e. the points whose (strict) neighborhood is completely included in that set). Note that this closing is not the same as the one obtained by composition of the vertex-vertex dilation and the vertex-vertex erosion. In fact, one can prove that the results of the two closings are ordered (when applied to the same subset of vertices the result of the first one is always included in the result of the second one). This leads to original interesting granulometries and alternating sequential filters which are further presented in the next paragraph.

Iterated operators. The third main contribution of [START_REF] Cousty | Morphological filtering on graphs[END_REF][START_REF] Cousty | Some morphological operators in graph spaces[END_REF] is the definition of new morphological filters (based on the composition and iteration of the basic building blocks presented in the previous paragraph) which allow regularizing images more precisely than the usual morphological operators based on structuring elements. The composition of any two dilations is still a dilation. Hence, by successive applications of elementary dilations (a same dilation can possibly be applied several times), one obtains series of dilations, adjunct erosions, openings and closings. When the dilations used in the compositions are those described a :

G b : X = (X • , X × ) c : δ • (X × ) d : × (X • ) e : • (X × ) f : δ × (X • ) g : [δ, ∆] (X) h : [ , E] (X) i : α 3 (X) j : β 3 (X)
Figure 30. Illustration of dilations and erosions on graphs. The working space is the graph G and we consider the subgraph X of G whose vertex set is X • and whose edge set is X × . The edge-vertex dilation and erosion of X • are represented in (c) and (e) respectively. The vertex-edge erosion and dilation of X × are represented in (d) and (f) respectively. The « natural » dilation and erosion of X are presented in (g) and (h) whereas (i) and (j) presents the result of another dilation and erosion on graphs (see more details on this operator in [START_REF] Cousty | Morphological filtering on graphs[END_REF]) in the previous paragraphs (i.e., the vertex-vertex dilation or the vertex-edge and edge-vertex dilations), the associated series of closings (resp., openings) is ordered : when applied to a same object, the result obtained with one closing (resp., opening) of the series is always smaller (resp., greater) than the result obtained with the next closings of the series. Note that, in such series, the number λ of iterations of the considered dilation/erosion constitutes a parameter of the filtering that is related to the size of the features to be preserved or removed. It is therefore often referred to as a size parameter of the dilations, erosions and filters. These series of openings and closings, called granulometries, are interesting for studying size distributions of subsets of vertices, subsets of edges and subgraphs of a graph (see e.g. [START_REF] Couprie | Distance, granulometry and skeleton[END_REF][START_REF] Ronse | Algebraic foundations of morphology[END_REF]). Furthermore, from granulometries, series of alternating sequential filters can be derived : each of them is a sequence of intermixed openings and closings of increasing size. These operators (which, contrarily to openings and closings, are not extensive or anti-extensive) progressively filter the objects in a balanced and progressive way. They constitute interesting tools for simplifying subsets of vertices, subsets of edges and subgraphs of a graph. Figure 31 (top row) presents the result of such a filtering procedure for a subset of pixels considered in the 4-adjacency graph. In this illustration, the edge-vertex and vertex-edge dilations and erosions were used to obtain the alternating sequential filters. As detailed in [START_REF] Cousty | Morphological filtering on graphs[END_REF], if, instead of the edge-vertex and vertex-edge dilations/erosions, only the vertex-vertex dilation/erosion was used, then the resulting filter would be less performing (see Figure 32). A quantitative assessment of this statement is provided in Section 5.5.

Figure 31. Illustration of morphological alternating sequential filters in graphs. The alternating sequential filters are obtained thanks to the vertex-edge and edge-vertex dilations. Top (resp., bottom) row : the filtering (right) is applied to a binary (resp., grayscale) image (left) considered in the 4-adjacency graphs (resp., in a spatially variant adjacency graph). The corresponding filterings in the usual pixel-based framework of structuring elements (i.e. the filters obtained on graphs from the natural dilation) are less performing (see e.g. Figure 32).

Distance maps and dilations on graphs. The first main contribution of [START_REF] Youkana | Parallelization strategy for elementary morphological operators on graphs : algorithms and implementation on multicore/multithreaded architecture[END_REF] is the study of distance maps on graphs that allow characterizing every (possibly iterated) dilation/erosion on graphs presented in previous paragraphs. A classical problem in graph theory is to find the minimal length of a path linking two vertices [START_REF] Dijkstra | A note on two problems in connexion with graphs[END_REF]. Depending of the application context, several notions of length can be associated to paths. In our context, we consider the simplest one which consists of counting the number of vertices in the path. The map which associates to any pair of vertices the minimal length of a path joining them clearly satisfies the axiom of a distance and is called the graph distance. Vincent shows in [START_REF] Vincent | Graphs and mathematical morphology[END_REF] an interesting relation between the graph distance and the iterated vertex-vertex dilations : a vertex x of the graph belongs to the result of the vertex-vertex dilation of size parameter λ of a given subset X of vertices if and only if there exists a point y of X such that the distance between x and y is less than λ. In other words, if we denote by D X the distance map to X (that is, the map that associates to any vertex of the graph the least distance between this vertex and a vertex in X), the vertex-vertex dilation of size parameter λ is the set of all points whose distance map value is below λ. In [START_REF] Youkana | Parallelization strategy for elementary morphological operators on graphs : algorithms and implementation on multicore/multithreaded architecture[END_REF], this link is extended to edge-edge, vertex-edge, and edge-vertex dilations. To this end, the paths between two edges and between an edge and a vertex are also considered and the length of a path becomes the number of edges and vertices along the path. Thus, following the morphological approach based on distance maps, three original notions of distance maps on graphs called edge-edge, edge-vertex, and vertex-edge distance maps are introduced in [START_REF] Youkana | Parallelization strategy for elementary morphological operators on graphs : algorithms and implementation on multicore/multithreaded architecture[END_REF]. Given a set of edges, the edge-edge (resp. edge-vertex) distance map provides for each edge (resp. each vertex) of the graph a distance to the closest edge in the input set. Given a set of vertices, the vertex-edge distance map provides for each edge a distance to the closest vertex in the input set. Then, all the dilations and erosions on graphs presented in the previous paragraph are characterized as a threshold set of one of these distance maps.

Linear-time dilation algorithms. A linear-time algorithm to compute the elementary dilations can be easily designed. Therefore, based on the straightforward definition, the time complexity of the naive algorithms to compute the iterated version of a dilation increases with the size parameter. More precisely, for a parameter value of λ, the algorithms run in O(λ.n) time, where n is the size of the underlying graph. However, based on the links between distance maps and dilations/erosions recalled in the previous paragraph, a O(n) time-complexity algorithm can be obtained for performing the same task. To this end, one needs to compute a distance map and to threshold it. In graph theory, it is well known that breadthfirst search algorithm provides an efficient linear-time complexity solution to obtain the length of a shortest path from one given vertex of the graph to all others. As presented in [START_REF] Youkana | Parallelization strategy for elementary morphological operators on graphs : algorithms and implementation on multicore/multithreaded architecture[END_REF], such an algorithm can be adapted to compute in linear-time any of the distance maps presented in the previous paragraph. The simple thresholding operation can be performed in linear time with respect to the size of the graph. Hence, based on the distance map algorithm presented in [START_REF] Youkana | Parallelization strategy for elementary morphological operators on graphs : algorithms and implementation on multicore/multithreaded architecture[END_REF], the result of any (possibly iterated) dilation or erosion on graphs presented in [START_REF] Cousty | Morphological filtering on graphs[END_REF] can be obtained in linear-time complexity with respect to the size of the underlying graph.

Parallel algorithms for morphological operators on graphs. The major contribution of [START_REF] Youkana | Parallelization strategy for elementary morphological operators on graphs : algorithms and implementation on multicore/multithreaded architecture[END_REF] is a parallel algorithm to compute the proposed distance maps, hence the morphological operators of [START_REF] Cousty | Morphological filtering on graphs[END_REF].

Parallel and/or separable algorithms for morphological operators and distance maps on images have been widely studied [START_REF] Chia | Parallel distance transforms on a linear array architecture[END_REF][START_REF] Coeurjolly | 2D subquadratic separable distance transformation for path-based norms[END_REF][START_REF] Man | Implementations of a parallel algorithm for computing euclidean distance map in multicore processors and GPUs[END_REF][START_REF] Pham | Parallel implementation of geodesic distance transform with application in superpixel segmentation[END_REF][START_REF] Saito | New algorithms for euclidean distance transformation of an n-dimensional digitized picture with applications[END_REF][START_REF] Shyu | Distance transformation in parallel[END_REF][START_REF] Soille | Recursive implementation of erosions and dilations along discrete lines at arbitrary angles[END_REF][START_REF] Svolos | Efficient binary morphological algorithms on a massively parallel processor[END_REF]. Based on the regular structure of the space, such computations use a static partitioning of the image into rows, columns or blocks processed in parallel. In order to handle the non-regular structure of a graph, our parallelization strategy is based on a dynamic partitioning of the space which depends on the input set and which is iteratively computed during the execution. More precisely, our strategy iteratively considers the successive level-sets of the distance maps, each level set being partitioned and then traversed in parallel. The time complexity of our parallel algorithm is analyzed in [START_REF] Youkana | Parallelization strategy for elementary morphological operators on graphs : algorithms and implementation on multicore/multithreaded architecture[END_REF]. Under some reasonable assumptions about the graph and set under consideration, our algorithm runs in O(n/p + K log 2 p) time, where n, p, and K are the size of the underlying graph, the number of available processors and the number of distinct level sets of the distance map, respectively. In [START_REF] Youkana | Parallelization strategy for elementary morphological operators on graphs : algorithms and implementation on multicore/multithreaded architecture[END_REF], an implementation of the proposed algorithm on a shared-memory multicore architecture is described and assessed on datasets of 45 images and 6 textured 3-dimensional meshes, showing a reduction of the processing time by a factor up to 55 over the previously available implementations on a 8 core architecture such as those available in nowadays desktop computers.

Stack operators. The morphological operators presented in the previous paragraphs are all increasing. As such, they all induce stack operators acting on functions weighting the vertices and/or edges of a graph (see [START_REF] Wendt | Stack filters[END_REF] for stack operators, [START_REF] Heijmans | Theoretical aspects of gray-level morphology[END_REF][START_REF] Maragos | Morphological filters-part i : Their set-theoretic analysis and relations to linear shift-invariant filters[END_REF][START_REF] Ronse | Flat morphology on power lattices[END_REF][START_REF] Serra | Image analysis and mathematical morphology[END_REF] for stack operators in the context of flat mathematical morphology, and [START_REF] Bertrand | On topological watersheds[END_REF][START_REF] Bertrand | On the dynamics[END_REF] for stack operators in the context of watershed image segmentation). This allows for the definition of morphological operators for weighted graphs, and thus for grayscale images, to be systematically inferred from the ones on non-weighted graphs (see [START_REF] Cousty | Morphological filtering on graphs[END_REF]). The idea is to decompose a function into level-sets by thresholding, then to apply a same operator to each level-set, before reconstructing a resulting function by "stacking" these results. Figure 31 (bottom row) presents the results obtained with the grayscale extension of the graph alternating sequential filters presented in the previous paragraph. Here the operator is applied to a grayscale image structured by a spatially variant graph obtained by removing the edges of the 4 adjacency graph connecting two pixels with a high difference of intensity.

Filtering on simplicial complexes

In the framework of graphs, it is difficult to characterize the topology of the considered objects. For example, given the set of vertices of a graph or more simply a graph, it is difficult to say if this object is a volumic object (3D), a surfacic object (2D), or a linear object (1D).

Introduced by Poincaré [START_REF] Poincaré | Analysis situs[END_REF] for studying the topology of spaces of arbitrary dimensions, a simplicial complex can be seen as a mesh, i.e. a space with a triangulation. The basic building block of the complex is the cell, which can be thought of as a set of elements having various dimensions glued together according to certain rules (e.g., a triangle, its edges and vertices, see Figure 33 and Figure 34). Although simplicial complexes have a wide variety of different usages (e.g., in computer graphics, in Computer-Aided Design or in modeling), their processing has mostly been considered in term of simplification, for example to obtain a simpler model with less details. However, it is more and more frequent to have data associated with the elements of a mesh (e.g. a curvature or a texture). Processing (filtering) the values associated with a mesh is not a common problem per se in the literature. On the other hand, filtering is a common theme in image processing, and abstract (simplicial or cubical) complexes have been promoted, in particular by Kovalevsky [START_REF] Kovalevsky | Finite topology as applied to image analysis[END_REF], in order to provide a sound topological basis for image analysis, and are more and more popular [START_REF] Cousty | Collapses and watersheds in pseudomanifolds of arbitrary dimension[END_REF][START_REF] Couprie | New characterizations of simple points in 2D, 3D, and 4D discrete spaces[END_REF][START_REF] Grady | Discrete Calculus[END_REF]. Then again, the values are most of the time located on one of the elements of the cell, usually the facet, i.e. the largest element of the cell. In a purely discrete perspective, being able to deal with smaller elements of the cell will allow a kind of "subpixelic" processing.

In this perspective, mathematical morphology provides a useful toolbox made of non-linear operators. Thanks to their algebraic definitions in the framework of lattices, those morphological operators can be applied to many kinds of organized information, and in particular to simplicial complexes. The complexes can be considered as a natural generalization of the graphs in the sense that a (symmetric) graph is a one dimensional complex. Mathematical morphology operators on graphs are well developed (see [START_REF] Heijmans | Graph morphology in image analysis[END_REF][START_REF] Meyer | Micro-viscous morphological operators[END_REF][START_REF] Ta | Partial difference equations over graphs : Morphological processing of arbitrary discrete data[END_REF][START_REF] Vincent | Graphs and mathematical morphology[END_REF] and Section 4.1). However, to the best of our knowledge, very few studies exist about basic morphological operators on complexes [START_REF] Loménie | Morphological mesh filtering and α-objects[END_REF], and none deal with the filtering problem. The goal of [START_REF] Dias | Dimensional operators for mathematical morphology on simplicial complexes[END_REF][START_REF] Dias | Some morphological operators on simplicial complex spaces[END_REF] is to help bridging this gap. As said previously, a simplicial complex is a generalization of a graph to an arbitrary dimension. If the workspace is a n-dimensional complex, the objects (i.e., the subsets of the workspace) to which one applies the morphological operators, as well as the results of the operators, can contain elements of various dimension between 0 and n. It then becomes possible to obtain dimensional operators that are able of filtering the parts of an objects according to their dimension. A large number of different dimensional operators can be considered : indeed, depending on the needs, for all values of i and j between 0 and n, it is possible to condition the presence or the absence of an element of dimension i in the result of a filtering with the presence / absence of some elements of dimension j in the object that one seeks to filter. The main result of [START_REF] Dias | Dimensional operators for mathematical morphology on simplicial complexes[END_REF][START_REF] Dias | Some morphological operators on simplicial complex spaces[END_REF] is a framework for building morphological operators on complex spaces. As main examples of application, we present a set of operators (erosions/dilations, granulometries/anti-granulometry, and alternate sequential filters) that act on the subcomplexes of a space which is itself a simplicial complex. Although this work is settled in the framework of simplicial complexes, all the results extend to cubical complexes. Overall, the panel of mathematical morphology operators introduced on simplicial complexes can be thought of as enrichment of the panel of operators on graphs which can themselves be seen as an enrichment of those on grid points. This is quantitatively verified in [START_REF] Mennillo | A Comparison of Some Morphological Filters for Improving OCR Performance[END_REF] where the operators on complexes provide better regularization results than those on graphs and on grid points. More details on this study is provided in Section 5.5.

APPLICATIONS AND ASSESSMENTS

Cardiac function assessment with MRI

In cardiology, obtaining precise information on the size and function of the left ventricle (LV) is essential both in clinical applications diagnosis, prognostic, therapeutic decisions and in the research fields. Thanks to 3D images acquired at different times of the heart cycle, (cine) magnetic resonance (MR) imagery permits a complete morphological LV characterization. The precision on the measures extracted from MR images has been demonstrated to be excellent [START_REF] Buser | Noninvasive evaluation of global left ventricular function with use of cine nuclear magnetic resonance[END_REF] and this is why MR imagery is a « gold standard » for LV analysis. Cine MR imagery provides temporal sequences of 3D cardiac images which can be seen as 3d+t images that allow for assessing the cardiac function of a patient through a computerized processing of the images. Based on the watershed cuts (see Section 2.2), we proposed in [START_REF] Cousty | Segmentation of 4D cardiac MRI : Automated method based on spatio-temporal watershed cuts[END_REF] a method and a software (see a screenshot in Figure 35) to automatically segment the left ventricle in such images and to compute some characteristic parameters of the cardiac function such as the ejection fraction, i.e., the volume of blood ejected during a heart cycle expressed as a fraction of the tele-diastolic volume (the volume of the filled ventricle). Due to the use of a watershed cut in a 4D edge-weighted graph, the successive segmentations obtained during the heartbeat are temporally consistent. To assess the quality of the results produced by the proposed software three main actions were carried out :

1. through a collaboration with the CHU Henri Mondor de Créteil, we have been able to compare, on a database of 18 patients, the segmentations produced by the software with those produced manually by two cardiologists ; the database [START_REF] Najman | An open, clinically validated database of 3d+ t cine-MR images of the left ventricle with associated manual and automated segmentations[END_REF] including ground truths is made available to the scientific community ;

2. we participated to the Cardiac MR Left Ventricle Segmentation Challenge at MICCAI conference in 2009. This allowed us to compare our results with those obtained by other teams : a set of images of 15 patients was analyzed from our laboratory, before the conference, and a set of 15 other patients was analyzed in 3 hours on the site of the conference [START_REF] Marak | 4D Morphological segmentation and the MICCAI LV-segmentation grand challenge[END_REF] ;

3. we participated to the Medi-Eval and ImPeic actions of the GDR STIC-santé. This led to the development of an evaluation platform for cardiac image segmentation algorithms [START_REF] Lebenberg | Nonsupervised ranking of different segmentation approaches : application to the estimation of the left ventricular ejection fraction from cardiac cine MRI sequences[END_REF]. This also led to the proposition of a method for estimating cardiac function from the results of several segmentation methods and we showed that the estimation was improved over the estimation from each method individually [START_REF] Lebenberg | Improved Estimation of Cardiac Function Parameters Using a Combination of Independent Automated Segmentation Results in Cardiovascular Magnetic Resonance Imaging[END_REF].

The participation to these three actions allowed us to confirm, by comparison of our results with those produced manually by cardiologists and automatically by other computerized procedures, that the proposed method is at the level of the state of the art of the field.

Coronary lesions detection and quantification in cardiac CT angiography

Coronary heart diseases refer to the group of disorders that affect the coronary artery vessels. They are the world leading cause of mortality (7.3 million deaths worldwide, according to the World Health Organization). Therefore, early detection of these diseases using less invasive techniques provides better therapeutic outcome, as well as reduces costs and risks, compared to an interventionist approach. Recent studies showed that X-ray computed tomography (CT) may be used to accurately locate and grade heart lesions in a non invasive way [START_REF] Marano | Italian multicenter, prospective study to evaluate the negative predictive value of 16-and 64-slice mdct imaging in patients scheduled for coronary angiography (nimiscad-non invasive multicenter italian study for coronary artery disease)[END_REF]. However, analysis of cardiac CT exams for coronaries lesions inspection remains a tedious and time consuming task as it is based on the manual analysis of the vessel cross sections. High accuracy is required, and thus only highly experienced clinicians are able to analyze and interpret the data for diagnosis. Computerized tools are critical to reduce processing time and to ensure quality of diagnostics. The goal of Imen Melki's PhD work [START_REF] Melki | Towards an automated framework for coronary lesions detection and quantification in cardiac CT angiography[END_REF] is to provide automated coronaries analysis tools to help in non-invasive CT angiography examination. A stenosis is a narrowing of a coronary artery, which happens in case of coronary artery disease. A typical processing pipeline allowing the detection of coronary artery stenoses is illustrated in Figure 36. Different algorithms covering the different processing steps of this pipeline were studied in [START_REF] Melki | Towards an automated framework for coronary lesions detection and quantification in cardiac CT angiography[END_REF]. The major contributions of [START_REF] Melki | Towards an automated framework for coronary lesions detection and quantification in cardiac CT angiography[END_REF] include (i) a novel algorithm to segment the heart volume in CT images [START_REF] Melki | A hybrid algorithm for automatic heart segmentation in CT angiography[END_REF][START_REF] Melki | A hybrid algorithm for automatic heart delineation in CT angiography[END_REF] and (ii) an algorithm to detect the stenosis from the centerline of the coronary arteries [START_REF] Melki | Automatic Coronary Arteries Stenoses Detection in 3D CT angiography[END_REF].

Heart segmentation in CT images. The first main contribution of [START_REF] Melki | Towards an automated framework for coronary lesions detection and quantification in cardiac CT angiography[END_REF] is an algorithm dedicated to heart volume segmentation in CT images. The approach extracts the heart as one single object that can be used as an input mask for automated coronary arteries segmentation. This work eliminates the tedious and time consuming step of manual removing obscuring structures around the heart (lungs, ribs, sternum, liver...) and quickly provides a clear and well defined view of the coronaries. Previous works related to heart segmentation have mainly focused on heart cavities delineation, which is not suited for coronaries visualization. In contrast, the algorithm proposed in [START_REF] Melki | A hybrid algorithm for automatic heart segmentation in CT angiography[END_REF][START_REF] Melki | A hybrid algorithm for automatic heart delineation in CT angiography[END_REF][START_REF] Melki | Towards an automated framework for coronary lesions detection and quantification in cardiac CT angiography[END_REF] extracts the heart cavities, the myocardium, and the coronaries as a single object. The proposed approach is based on the fitting of a geometric model of the heart, namely an ellipse, to a set of automatically extracted 3D points lying on the heart shell [START_REF] Fitzgibbon | Direct least square fitting of ellipses[END_REF]. A novel two-stage fitting scheme is used to improve the robustness to the outliers. The fitting result is further refined using a Random Walker (RW) segmentation approach [START_REF] Grady | Random walks for image segmentation[END_REF]. A segmentation result obtained with this approach is illustrated in Figure 37. Qualitative analysis of results obtained on a 70 exam database shows the efficiency and the accuracy of this approach. Stenoses detection in CT images. The second main contribution of [START_REF] Melki | Towards an automated framework for coronary lesions detection and quantification in cardiac CT angiography[END_REF] is an algorithm [START_REF] Melki | Automatic Coronary Arteries Stenoses Detection in 3D CT angiography[END_REF] to detect the severe cardiac stenoses from CT angiography images. The proposed approach comprises three main steps. The first one consists of extracting the vessel centerlines from the segmented heart volume. To perform this task, we have used the method proposed in [START_REF] Goldenberg | Computer-aided simple triage (CAST) for coronary CT angiography (CCTA)[END_REF]. The second step consists of segmenting the lumen of the vessels and their contours. We have used a watershed based procedure (see Section 2) where the vessel centerlines are used as markers. The watershed results are further refined to obtain a subpixelic contours. Finally, we perform an analysis of the area of the vessel sections along the vessel centerline in order to detect the stenoses. A regression on the area profile along the whole vessel provides a model for the theoretical healthy vessel of the patient and we detect the stenoses by considering vessel parts that significantly deviates from this ideal model (see Figure 5.2). We have tested our algorithm on the 48 multi-vendor CT angiography datasets of typical patients provided by the « MICCAI Stenosis detection/quantification and lumen segmentation challenge » organized in conjunction with the 15th International Conference on Medical Image Computing and Computer Assisted Intervention (MICCAI 2012) [START_REF] Kirişli | Standardized evaluation framework for evaluating coronary artery stenosis detection, stenosis quantification and lumen segmentation algorithms in computed tomography angiography[END_REF]. The proposed approach ranked third among 11 algorithms during the on-site evaluation of this challenge.

PCI procedures modeling through image processing

Percutaneous Coronary Intervention (PCI) is a minimally invasive procedure employed for the treatment of coronary artery stenosis. As described in the previous section, a stenosis is a narrowing of a coronary, which happens in case of coronary artery disease, a common pathology with its acute state being the heart attack potentially leading to death. PCI is a very mature procedure relying on the deployment of a stent, i.e., a fine metallic mesh having the shape of the artery at the location of the narrowing. Physicians are able to treat simple lesions, which impact a single vessel and complex lesions, with the narrowing extending over the different branches of a bifurcation or extreme cases when the vessel is completely occluded. These procedures require the visualization of the lumen of the coronary arteries which is achieved by injecting an iodine based contrast media at the ostia of each coronary tree (left or right). The contrast media is rapidly washed out by the blood flow. The propagation of the contrast media is documented under X-ray radiation to acquire the angiography sequences which are further used to diagnose the stenoses. The procedure is overall beneficial to the patient but has several side effects. The tolerance to the contrast agent is limited to some amount. Another side effect is the use of ionizing radiation which affects both the patient and the medical team present in the interventional room including the interventional cardiologist.

Physicians expect that the behavior of the imaging equipment is continuously optimized to ensure optimum image quality with minimum dose delivery or automatized processing of some sequences to enhance some details of interest at a particular moment. PCI procedure modeling can help to improve the interaction of the clinician with the imaging equipment. This concept refers to determining the intention of the clinician along the procedure. For this purpose, a continuous monitoring and labeling of the sequence is necessary. The key steps of the PCI procedure are : vessel diagnosis, guidewire navigation, stent positioning, stent deployment (balloon inflation), stenting assessment. Getting this information directly from the human operator is not acceptable from a workflow point of view. The PhD work of Ketan Bacchuwar [START_REF] Bacchuwar | Traitement d'images pour l'analyse sémantique du déroulement des procédures interventionnelles en cardiologie[END_REF] is dedicated to the design of image processing algorithms to identify the presence of different interventional tools in the images and link this information to high-level knowledge describing the steps of the procedure and the user expectations for each of them. This is a form of semantic analysis which is fundamentally different from the traditional automatic X-ray exposure control combining user interactions and measure of the statistics of the image.

Empty catheter segmentation. From first analysis of this PCI procedure, we observe that the seg- mentation of guiding catheter is of outmost importance. A guiding catheter is a tool that appears throughout the PCI procedure. It can contribute to significant semantic information since (i) it is the first tool to appear in the field of view, (ii) it is fixed at ostia for the rest of the procedure, and (iii) it is the conduct for all other tools/devices. Thus, its segmentation can help in procedure modeling to determine the events/phases of the arrival and removal location of other devices (guide wire, marker balls). We address in [START_REF] Bacchuwar | Scale-space for empty catheter segmentation in PCI fluoroscopic images[END_REF] the empty catheter case, i.e., when it is not filled with contrast media or a guidewire. Such empty catheter appears in 20% of the images acquired during PCI procedures and mostly in the first steps of the procedures where the analysis shall start. Contrary to a filled catheter, which is a highly contrasted structure relatively easy to segment, an empty catheter is relatively difficult to segment. Indeed, in the interventional fluoroscopic X-ray images, it appears as a low contrasted structure with two parallel and partially disconnected edges because it is just an empty tubular pipe made of a material with little radio-opacity (see Figure 39).

We devise a bottom up approach for segmenting the empty catheter in fluoroscopic images. We first use the level-set scale-space, i.e. , the hierarchy of all the level sets of the gray scale image, called the mintree, to extract curve blobs, small dark persistent regions that are potentially part of the empty catheter (see an illustration of this step in Figure 40). These curve blobs are disconnected in the image space. We then propose a structural graph-based scale-space, in the form of a hierarchy, where these curve blobs are connected. We analyze this hierarchy to select the cluster of curve blobs that maximizes a score of likelihood to be an empty catheter (see an illustration of this step in Figure 41). To evaluate our work, we use a database of 1250 fluoroscopic images from 6 patients. The results of the proposed method are illustrated in Figure 42. The centerline of the catheter in this dataset was manually delineated by a trained observer to define the ground truth. On this dataset, the mean precision and recall of the proposed method are 80.48 and 63.04% respectively. These experimental results are encouraging, showing that it is possible to locate with good precision the empty catheter in such noisy images.

Vessel of intervention dynamic detection. During a PCI procedure, the vessel of intervention (VOI) is the branch of the coronary vessel tree between the ostia and the distal end of the vessel across the coronary lesion. In the work presented in [START_REF] Bacchuwar | VOIDD : automatic vessel of intervention dynamic detection and tracking in PCI procedures[END_REF][START_REF] Bacchuwar | editeurs, Intravascular Imaging and Computer Assisted Stenting, and Large-Scale Annotation of Biomedical Data and Expert Label Synthesis[END_REF], we develop methods for automatic detection of VOI by combining the information from X-ray image sequences acquired at different steps of the procedure. Coronary lesions are treated by navigating a guidewire through the VOI, followed by implantation of a stent at the lesion in the VOI. Our aim is to automatically identify the guidewire arrival at the ostia of the coronary vessel tree and to determine the VOI which is going to be treated in the following steps of the PCI procedure, such as lesion reparation with angioplasty balloon, stenting, post-dilatation.

The main contribution of [START_REF] Bacchuwar | VOIDD : automatic vessel of intervention dynamic detection and tracking in PCI procedures[END_REF][START_REF] Bacchuwar | editeurs, Intravascular Imaging and Computer Assisted Stenting, and Large-Scale Annotation of Biomedical Data and Expert Label Synthesis[END_REF] is the proposition and the assessment of a method, called VOIDD, to automatically detect the so-called vessel of intervention, from the X-ray images acquired during the progress of PCI procedure. We combine information from two types of X-ray image sequences : i) the cine images from the reference sequence, in which the vasculature is depicted by injected contrast agent (see, for instance, Figure 43(top, right)), and ii) the fluoroscopic images from the fluoroscopic image stream, which are acquired following the reference sequence to aid navigation of various tools and especially the guidewire (see, for instance, Figure 43(top, left)). The proposed algorithm is able to recognize from the fluoroscopic image stream, the period corresponding to the guidewire navigation and to exploit it to determine the vessel of intervention location (see Figure 43) without adding any constraints to the procedure workflow. In order to reach this goal, a general tracking algorithm is proposed. It relies on features extracted from the two considered types of X-ray image sequences. These features consist of coronary vessel centerlines extracted from the reference sequence and of guidewire tip location candidates detected in the fluoroscopic image stream. Hessian based vesselness techniques are used to obtain the vasculature from the reference sequence. Guidewire tip detection is tackled with advanced approaches involving the use of min tree [START_REF] Salembier | Connected operators : A review of region-based morphological image processing techniques[END_REF]. Frèchet distance based curve matching approaches derived from [START_REF] Benseghir | A tree-topology preserving pairing for 3d/2d registration[END_REF] are used to match the guidewire tip location candidates to the detected vessels. Figure 43 presents the obtained results (input images, detected tip, matching, and detected vessel of intervention) for one image of one patient. In order to illustrate the variety of situations which can occur, Figure 44 presents the detected vessel of interventions for 12 patients. In [START_REF] Bacchuwar | VOIDD : automatic vessel of intervention dynamic detection and tracking in PCI procedures[END_REF], we also present an evaluation methodology designed to characterize the correctness of the guidewire tip detection and the correct identification of the VOI location. These developments are assessed on 15 clinical sequences dataset from 14 patients and comprising 9989 images with expert annotations. Encouraging results have been obtained with mean VOI retrieval rate of 93.22% (proportion of the annotated vessel of intervention that is recovered by the automated method) and mean tip detection accuracy of 99.05% (proportion of the navigation period of the guidewire which is correctly identified). These results tend to prove the robustness over different patient and imaging conditions.

Cardiac Electrophysiology

During a number of interventional procedures related to the improvement of electrical therapy of the heart (e.g. to cure some forms of cardiac arrhythmias), the physicians have to manipulate catheters inside the heart chambers. One of the surgical techniques involves positioning of catheters in the left atrium guided by interventional fluoroscopic images. The main anatomical structures of interest are not visible on these images and thus, the interventions can last up to seven hours.

In order to augment the quality of the interventional images, we propose a software [START_REF] Vaillant | Method and system for registering 3D models of anatomical regions with projection images of the same[END_REF][START_REF] Vaillant | Method and apparatus for registering 3D models of anatomical regions of a heart and a tracking system with projection images of an interventional fluoroscopic system[END_REF] to superimpose preinterventional 3D models of the atrium acquired, for instance, by CT devices.

To reach this goal, we search for a geometric transformation which maps a catheter inserted inside the coronary sinus to the medial axis of the sinus. Segmentations of the catheter in fluoroscopic images and of the sinus in preinterventional CT images can be obtained, for instance, by watershed-based procedures. The registration is then computed by energy minimization through a gradient descent algorithm.

A prototype has been installed in an electrophysiology laboratory. The software achieved a satisfying registration in 85% of the 20 cases which have been assessed.

Optical character recognition (OCR)

Mathematical morphology offers powerful tools that are widely recognized for their utilities for application purposes, in particular for filtering out many image defects. The old opening and closing based on structuring elements are still widely used and are described in most image analysis textbooks, although their combination at various scales, namely the granulometries [START_REF] Couprie | Distance, granulometry and skeleton[END_REF][START_REF] Serra | Image analysis and mathematical morphology[END_REF], are not as well known. Their main implementation is on the usual 4, 6 or 8 connected grids [START_REF] Kong | Digital topology : Introduction and survey[END_REF], [START_REF] Serra | Image analysis and mathematical morphology[END_REF]chapter VI]. However, there exist several recent variations of these operators, depending on the space on which they are defined : we are especially interested in this section in graphs (see Section 4.1), first by considering only the vertices (corresponding to the pixels) [START_REF] Heijmans | Graph morphology[END_REF][START_REF] Vincent | Graphs and mathematical morphology[END_REF] and then, by considering edges (between pixels) and vertices [START_REF] Cousty | Morphological filtering on graphs[END_REF][START_REF] Meyer | Micro-viscous morphological operators[END_REF]. The incentive for using more evolved space representations is to enhance the performance by getting "subpixelic" accuracy. Such an idea has been pushed a step further by considering simplicial complexes (Section 4.2), a generalization of graphs. Although these new frameworks look promising from a theoretical point of view, to the best of our knowledge, to date, a systematic comparison of these old and novel operators for a dedicated application has not yet been performed. The goal of the work presented in [START_REF] Mennillo | A Comparison of Some Morphological Filters for Improving OCR Performance[END_REF] is to fill that gap, focusing on Optical Character Recognition, or OCR. As it is well known that connected filters, and especially area opening and closing [START_REF] Vincent | Morphological area openings and closings for grey-scale images[END_REF] are well adapted to document image analysis, we include them in this study.

The filtering step is generally just one step in the many ones composing the full application chain. Linear filters can be evaluated by their response to some model of noise. It is more difficult to apply the same evaluation process to the non-linear morphological filters. This is why we choose to assess the performance of an OCR against some model of noise/degradation dedicated to documents [START_REF] Baird | Document image defect models[END_REF][START_REF] Baird | Calibration of document image defect models[END_REF][START_REF] Kanungo | Global and local document degradation models[END_REF]. Indeed, OCR is the process of converting a scanned document to machine-encoded text [START_REF] Rice | Optical character recognition : An illustrated guide to the frontier[END_REF]. Such an operation is generally impacted by the quality of the original document and by the introduction of artifacts during the scanning process. Our performance evaluation is hence a measure of the ability of the aforementioned morphological operators to improve OCR performance when used as a preprocessing step on degraded binary document images. In this work, the statistics-based degradation models described in [START_REF] Kanungo | Global and local document degradation models[END_REF] was used.

It is clear following this experiment that morphological filtering can greatly improve OCR accuracy when used as a preprocessing step. The different results shown in this experiment are potent indicators of the efficiency of several morphological filters in the context of OCR. Indeed, preprocessing using such filters leads to an increase of respectively up to 65.49% and up to 69.06% in character and word accuracy on binary documents. It is shown that the best accuracy improvement of the OCR is obtained with a preprocessing performed on simplicial complexes, followed by the one on graphs, and the one on regular grid (classical framework based on structuring elements). Furthermore, it is also shown that area opening and closing [START_REF] Vincent | Morphological area openings and closings for grey-scale images[END_REF] do not perform as well as ASF (see Section 4) on complexes and on graphs for this task and that the results can be further improved when image resolution is upscaled before filtering. Finally, it is also assessed that the original image (i.e., before applying the degradation model) is better recovered when the degraded image is filtered on simplicial complexes than on graphs or on grids. This confirms that practically, mathematical morphology filtering on simplicial complexes is an enrichment of mathematical morphology filtering on graphs, which itself is an enrichment of mathematical morphology filtering on regular grids with structuring elements.

Evaluation of hierarchies for natural image analysis

Hierarchies of partitions are multi-scale image representations that were first proposed in [START_REF] Horowitz | Picture segmentation by a tree traversal algorithm[END_REF][START_REF] Tanimoto | A hierarchical data structure for picture processing[END_REF]. They have since appeared under various names : pyramids, hierarchies of segmentations, partition trees, scale-sets. In a hierarchy (of partitions), an image is represented as a sequence of coarse to fine partitions satisfying the strong causality principle [START_REF] Koenderink | The structure of images[END_REF][START_REF] Morel | Variational methods in image segmentation : with seven image processing experiments[END_REF] : any partition is a refinement of the previous one in the sequence (see Section 3). They have various applications in computer vision and image analysis : image segmentation [START_REF] Perret | Directed connected operators : asymmetric hierarchies for image filtering and segmentation[END_REF][START_REF] Arbelaez | Contour detection and hierarchical image segmentation[END_REF][START_REF] Guigues | Scale-sets image analysis[END_REF][START_REF] Pont-Tuset | Multiscale combinatorial grouping for image segmentation and object proposal generation[END_REF][START_REF] Ren | Image segmentation by cascaded region agglomeration[END_REF][START_REF] Salembier | Optimum graph cuts for pruning binary partition trees of polarimetric sar images[END_REF][START_REF] Salembier | Binary partition tree as an efficient representation for image processing, segmentation, and information retrieval[END_REF][START_REF] Xu | Hierarchical segmentation using tree-based shape spaces[END_REF], occlusion boundary detection [START_REF] Hoiem | Recovering occlusion boundaries from an image[END_REF], image simplification [START_REF] Perret | Directed connected operators : asymmetric hierarchies for image filtering and segmentation[END_REF][START_REF] Guigues | Scale-sets image analysis[END_REF][START_REF] Soille | Constrained connectivity for hierarchical image partitioning and simplification[END_REF], object detection [START_REF] Salembier | Binary partition tree as an efficient representation for image processing, segmentation, and information retrieval[END_REF], object proposal [START_REF] Pont-Tuset | Multiscale combinatorial grouping for image segmentation and object proposal generation[END_REF], visual saliency estimation [START_REF] Yan | Hierarchical saliency detection[END_REF]. In particular, they have gained a large popularity with the work presented in [START_REF] Arbelaez | Contour detection and hierarchical image segmentation[END_REF] whose hierarchical approach to the general problem of natural image segmentation outperformed state-of-the-art approaches.

In order to assess the results of hierarchical watersheds (as described in Section 3.2) in the context of natural image segmentation, the first main contribution of [START_REF] Perret | Evaluation of hierarchical watersheds[END_REF] is a novel evaluation framework for hierarchies of partitions specifically designed to capture the various aspects of those representations : 1) quality of regions and contours, 2) quality of produced segmentations with horizontal cuts (i.e. partitions extracted from the hierarchy where every region is taken at the same scale) and optimal non-horizontal cuts (i.e. partitions extracted from the hierarchy where the regions can be taken at different scales), and 3) easiness of finding a set of regions representing a semantic object (see [START_REF] Perret | Evaluation of morphological hierarchies for supervised segmentation[END_REF] for a preliminary study on this aspect). These measures are evaluated on two types of natural image datasets : 1) Pascal Context segmentation dataset [START_REF] Mottaghi | The role of context for object detection and semantic segmentation in the wild[END_REF] (2 498 images), and 2) MS-COCO [START_REF] Lin | Microsoft coco : Common objects in context[END_REF] and Pascal VOC'12 [START_REF] Everingham | The pascal visual object classes challenge 2012 (voc2012) results[END_REF] object segmentation datasets (291 875 objects from 40 504 images and 3 427 objects from 1 449 images respectively). Compared to the classical approach for hierarchy evaluation that focuses only on the horizontal cuts and on the image segmentation problem, we believe that the proposed framework offers a richer assessment that better accounts for the hierarchical nature of the representations and it is not limited to a single use case, which better suits to the wide spectrum of applications in computer vision and image analysis. This framework can be used to evaluate and understand the strengths and weaknesses of the considered hierarchies of segmentations. In particular, it allows us to identify a watershed hierarchy based on a novel extinction value, the number of parent nodes, that outperforms the other hierarchies of morphological segmentations, namely, the quasi-flat zones hierarchy, the watershed hierarchy based on dynamics, area, and volume extinction values, cited in increasing order of mean score according to [START_REF] Perret | Evaluation of hierarchical watersheds[END_REF].

Then, we study the importance of the gradient measure for all these methods and the benefit to perform a post-filtering of some hierarchies. The most simple gradient measures use only colorimetric information from the two pixels of an edge to set up the weight of this edge : in this category, we consider an Euclidean distance in the RGB color space and an Euclidean distance in the Lab color space, the latter being more compliant with human color perception [START_REF] Gonzalez | Digital image processing[END_REF]. However, recent advances on contour detection have led to non local supervised gradient estimators achieving better performance on contour detection benchmarks : in this category, we consider the structured edge detector (SED) from [START_REF] Dollár | Fast edge detection using structured forests[END_REF]. We do not observe a clear improvement with Lab gradient compared to RBG gradient. However, there is almost always a large gain by switching from a local RGB or Lab gradient to the supervised non-local gradient SED. We noticed also that the segmentations extracted from quasi-flat zones hierarchies and watershed hierarchies based on dynamics failed to retrieve the main objects of interest of the image unless the hierarchies are post-processed to remove the smallest regions.

Finally, the properties of the best hierarchical watershed solutions are discussed and compared to stateof-the-art approaches proposed in the computer vision field. As reference state-of-the-art results, we include Multiscale Combinatorial Grouping (MCG) hierarchies from [START_REF] Pont-Tuset | Multiscale combinatorial grouping for image segmentation and object proposal generation[END_REF], Convolutional Object Boundaries (COB) hierarchies from [START_REF] Maninis | Convolutional oriented boundaries : From image segmentation to high-level tasks[END_REF], and Least Effort Segmentation (LEP) from [START_REF] Zhao | Segmenting natural images with the least effort as humans[END_REF] in our assessments. Comparing to state-of-the-art methods, the hierarchical watershed method does not perform as well as other methods in terms of mean score but is competitive for a certain number of measures (such as the measures based on non-horizontal cuts).

In terms of execution times, the watershed approach is at least an order of magnitude faster than other methods (mean execution time of 90ms on images of size 481 × 321 pixels for the hierarchical watershed methods vs 800 ms, 2s, and 24s for the methods described in [START_REF] Maninis | Convolutional oriented boundaries : From image segmentation to high-level tasks[END_REF], [START_REF] Zhao | Segmenting natural images with the least effort as humans[END_REF] and [START_REF] Pont-Tuset | Multiscale combinatorial grouping for image segmentation and object proposal generation[END_REF], respectively). We also performed tests on high resolution RGB images (4160 × 2340 pixels) giving a mean processing time of 5.5 s composed of 4 s to compute SED gradient and 1.5 s to construct the watershed hierarchy.

Overall, we concluded from the experiments that watershed hierarchies are valuable candidates for various computer vision tasks.

Artwork 3D models indexing and classification

3D shape modeling and digitizing have received more and more attention for a decade, leading to an increasing amount of 3D model warehouses, either in domain-specific or wide-usage contexts. These 3D model databases require new tools for indexing, classifying, and retrieving the objects in order to provide the end-user with easy access to the models. Content-based document retrieval (CBDR) has been a very active research field for a few years, and concerns textual documents, images, videos, and more recently 3D models. Usually CBDR is divided into two different steps : (i) an off-line step performs the document indexing by computing descriptors and features that are easily and fast compared, and thus builds an efficient summary of each document, called a signature ; (ii) an on-line step, in which the user performs a search in the database thanks to a search engine. By means of signature comparison, the system ranks the database models according to their similarity to a query given as input. A feedback loop based on user interaction refines the results.

In [START_REF] Philipp-Foliguet | Artwork 3D model database indexing and classification[END_REF], we focus on 3D model indexing and retrieval. The first interactive 3D model search engines appear on the web around 2001-2002. The Princeton 3D Model Search Engine, associated to the widely used Princeton Shape Benchmark (PSB), (http://shape.cs.princeton.edu/benchmark/) allows the user to perform text queries, 2D sketch queries, and to compare 3D models through some 3D shape descriptors [START_REF] Funkhouser | A Search Engine for 3D Models[END_REF]. The 3D Search Tool from the University of Thessaloniki (http://3d-search.iti.gr/3DSearch) is based on the 3D generalized Radon transform and make comparisons within a 2.000 model database [START_REF] Daras | Efficient 3-d model search and retrieval using generalized 3-d radon transforms[END_REF] ; the results are only based on geometric comparisons, without learning, leading to some mis-classifications of the database. The European Network of Excellence Aim@Shape (http ://www.aimatshape.net.) presents a geometric search engine which provides content-based retrieval with different matching methods (global or local, etc.). The SHREC 3D Shape Retrieval Contests allowed the comparison of 3D shape descriptors and 3D retrieval methods thanks to databases associated with ground-truths [START_REF] Veltkamp | SHREC2007 : 3D Shape Retrieval Contest[END_REF]. Ohbuchi et al. [START_REF] Ohbuchi | Learning semantic categories for 3d model retrieval[END_REF] proposed a retrieval system based on multiresolution global features, which retrieves object categories from a single example.

In [START_REF] Philipp-Foliguet | Artwork 3D model database indexing and classification[END_REF], we present a 3D indexing and retrieval search engine, called "RETIN-3D", dedicated to 3D artwork model databases. Some examples of such 3D artwork models are presented in Figure 46. The aim is to provide user friendly tools for classification, for content-based indexing, for retrieval, and for visualization of such dataset. These tools are firstly dedicated to historians and archaeologists, who will be able to find, display and compare artworks in a few clicks. One can also imagine that museum visitors, provided with their smartphone, could have the opportunity to query a database in front of a statue and thus get a lot of additional information. The database classification is addressed by means of global shape indexing. Unlike CAD models or artificial models that are often used in 3D model warehouses, artwork models are digitized in a high resolution (between 30,000 and 300,000 vertices) and do not exhibit regular surfaces. We compare several global shape descriptors for a classification task. The RETIN-3D search engine uses these shape descriptors to retrieve similar objects thanks to an active learning strategy. Unlike search engines which are asked by textual requests or 2D/3D sketches, the query consists in a 3D model, and the search engine extracts from the database a category of models similar in a certain way to the query. The user leads the search to the desired category, annotating some objects as relevant or irrelevant to his search. A screenshot of the proposed search engine is presented in Figure 47.

Not surprisingly, global shape descriptors are not sufficient to discriminate objects differing by some specific details. Thus, we propose to use local shape descriptors computed on regions of the surface. To obtain regions of the surface, we consider watershed cuts of maps defined on the surface of the 3D object and which behaves like a local curvature estimator. The framework of watershed cuts on simplicial complexes, presented in Section 2.3, is particularly adapted to this task. Then, shape descriptors are computed for each region of the surface partition, and the search engine is adapted to 3D region descriptor bags. Partial matching results are therefore also possible.

Experiments show that the combination of an accurate surface segmentation and local shape descriptors significantly improves the database classification. The end-user (a museum curator, for instance) may be particularly interested in partial shape matching, for example to classify fragments or to classify objects according to minor details. The active learning strategy, developed in our search engine RETIN-3D is thus an important tool for the end-user.

CONCLUSION

This dissertation is an overview of our main research results. It covers a period of almost fifteen years of activity. Our primary interest is image segmentation (Sections 2 and 3) and filtering (Section 4) with applications to medical imaging (Sections 5.1, 5.2, 5.3, and 5.4), optical character recognition (Section 5.5), computer vision (Section 5.6 and the ongoing PhD work of Karla Otiniano et Edward Cayllahua about human action recognition and scene parsing, respectively), 3D surfaces analysis (Section 5.7), biological imaging (ongoing PhD work of Diane Genest about classifying images of fish embryos according to potential anatomical malformations), video processing [START_REF] De Souza | Hierarchical video segmentation using an observation scale[END_REF][START_REF] Nhimi | Evaluation of morphological hierarchies for supervised video segmentation[END_REF] (not described in this dissertation), and multimedia processing (pending call for projects to extend preliminary works of our collaborators [START_REF] Da Fonseca | Tag propagation approaches within speaking face graphs for multimodal person discovery[END_REF][START_REF] Sargent | PUC Minas and IRISA at Multimodal Person Discovery[END_REF] using algorithms presented in this dissertation). We have provided new solutions to image processing problems (watershed segmentation, hierarchical analysis, and mathematical morphology filtering by adjunctions) with associated algorithms and implementations. We highlighted the interests of these novel solutions from theory, computational efficiency, and application points of view. In particular, these solutions have been embedded in a wide variety of robust and fast softwares solving application problems.

An important part of our work relies on graphs. This framework is adapted to discrete spaces (thus to images stored in a computer memory), allows the versatility of the proposed tools (thus, their use in various applications), and relies on solid theoretical and algorithmic bases. In addition to providing original solutions to image processing problems by working in this graph framework, we have been able to highlight new graph problems (and their solutions) in relation with image processing applications. As main examples, we point out (i) the introduction of four original classes of graphs, namely the fusion graphs, presented in Section 2.1.1, which are adapted to some region merging image analysis methods, and (ii) the original characterization of the minimum spanning trees of a given edge-weighted graph relying on an image segmentation method, namely the quasi-flat zone hierarchical segmentation method. So far these results have not yet been used outside the field of image processing but this could happen in the future. In this dissertation, we also mentioned some results concerning segmentation and filtering in the framework of simplicial complexes. This framework is a generalization of the one of graphs. It is then richer and also more complex than the framework of graphs. It allows to better account for the topological properties of the object under considerations and the operators defined on such spaces can reach a better precision than their counterparts on graphs. Finally, we have recently explored watershed segmentation in hypergraphs which is a kind of generalization of simplicial complexes adapted to deal with other kind of data such as movie datasets or authorship datasets [START_REF] Dias | Watersheds on hypergraphs for data clustering[END_REF] which are less structured than the digital images or the discrete surfaces.

In order to close this dissertation, we would like to sketch six interesting directions for future midterm research work.

1. Recent advances in machine learning [START_REF] Lecun | Deep learning[END_REF] provide disruptive innovations in computer vision leading to a large improvement of results for numerous tasks such as object recognition [START_REF] Sermanet | Overfeat : Integrated recognition, localization and detection using convolutional networks[END_REF] or scene labeling [START_REF] Farabet | Learning hierarchical features for scene labeling[END_REF]. Following this trend, a large gap of performance is obtained in [START_REF] Maninis | Convolutional oriented boundaries : From image segmentation to high-level tasks[END_REF] for the natural image segmentation problem. However, the results are still far from human performance which leaves room for improvements in a near future. First attempts to learn gradients measure for (nonhierarchical) watershed segmentation [START_REF] Bai | Deep watershed transform for instance segmentation[END_REF][START_REF] Porter | Learning watershed cuts energy functions[END_REF] show that it is a promising but not easy direction. Providing a complete framework allowing the learning of adapted gradient and regional attributes for hierarchical watershed segmentation would surely be a step forward in the field.

2. For image segmentation, the question of evaluation is a fundamental one. A considerable amount of work is nowadays devoted to the construction of a sound evaluation framework [START_REF] Perret | Evaluation of hierarchical watersheds[END_REF][START_REF] Perret | Evaluation of morphological hierarchies for supervised segmentation[END_REF][START_REF] Arbelaez | Contour detection and hierarchical image segmentation[END_REF][START_REF] Pont-Tuset | Measures and meta-measures for the supervised evaluation of image segmentation[END_REF][START_REF] Pont-Tuset | Supervised evaluation of image segmentation and object proposal techniques[END_REF].

The assessment is performed with the existing ground-truth segmentations available in the literature [START_REF] Everingham | The pascal visual object classes challenge 2012 (voc2012) results[END_REF][START_REF] Lin | Microsoft coco : Common objects in context[END_REF][START_REF] Martin | A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics[END_REF][START_REF] Mottaghi | The role of context for object detection and semantic segmentation in the wild[END_REF]. These works mainly focus on comparing a hierarchical segmentation provided by a computer with one or several ground-truth segmentations provided by humans. One should note that such ground-truth segmentations are not hierarchical, and as such, we can not truly assess the benefit of a hierarchical organization. Although the question of the evaluation of hierarchies is an even more complex question, we are deeply convinced that the computer-vision community at large would benefit of hierarchical ground truths, i.e., the full decomposition of a complex image in its semantic parts and the iterative refinement of those parts into subparts. Up to our knowledge, the work presented in [START_REF] Maire | Hierarchical scene annotation[END_REF] is the single attempt to provide a hierarchical ground-truth dataset. The authors of [START_REF] Maire | Hierarchical scene annotation[END_REF] define a hierarchical ontology of semantic objects with 3 levels and asked human subjects to decompose scenes according to it : the dataset is thus strongly oriented towards the category identified in the ontology and does not correspond to a general segmentation objective. Building a hierarchical ground-truth dataset and an associated evaluation framework for the general image segmentation problem is a full research topic for the future. It includes notably the design of computerized tools allowing the user to hierarchically annotate the images, as well as measures to compare a human provided hierarchy to the results of the hierarchical segmentation algorithms.

3. An important aspect of the work presented in [START_REF] Cousty | Hierarchical segmentations with graphs : quasi-flat zones, minimum spanning trees, and saliency maps[END_REF], which is briefly recalled in Section 3.1, is to underline and to make precise the close link that exists between hierarchical classification [START_REF] Gordon | A review of hierarchical classification[END_REF][START_REF] Nakache | Approche pragmatique de la classification : arbres hiérarchiques, partitionnements[END_REF][START_REF] Silla | A survey of hierarchical classification across different application domains[END_REF] and hierarchical image segmentation. Indeed, the work presented in [START_REF] Cousty | Hierarchical segmentations with graphs : quasi-flat zones, minimum spanning trees, and saliency maps[END_REF] allows us to recover and to generalize some results known in hierarchical clustering. Whereas classification methods were used as image segmentation tools for a long time, our results incite us to use hierarchical methods initially designed for image segmentation for processing non image data. We showed preliminary results of the use of hierarchical watersheds and saliency maps for analyzing and visualizing a small dataset of US cities [START_REF]NetworkX Examples : Knuth Miles[END_REF]. Some illustrations of this analysis are presented in Figures 48,[START_REF] Kiran | Climbing : a unified approach for global constraints on hierarchical segmentation[END_REF][START_REF] Melki | A hybrid algorithm for automatic heart segmentation in CT angiography[END_REF][START_REF] Melki | A hybrid algorithm for automatic heart delineation in CT angiography[END_REF]. With the emergence of the so-called "big-data", exploring large databases with the tools presented in this dissertation seems a promising direction for future research. To go one step further, leveraging on the relations between the notions of watershed and homotopy (Section 2.3), new insights for such classification of large datasets could be obtained by establishing links between the presented notions and the topological persistence theory [START_REF] Edelsbrunner | Topological persistence and simplification[END_REF]. Moreover, the links between mean shift and topological persistence established in [START_REF] Paris | A topological approach to hierarchical segmentation using mean shift[END_REF], the links between spectral clustering and minimum spanning tree investigated in [START_REF] Challa | An introduction to gamma-convergence for spectral clustering[END_REF] as well as relations with the notion of a tree of shapes introduced in [START_REF] Monasse | Fast computation of a contrast-invariant image representation[END_REF] and further studied in [START_REF] Géraud | A quasi-linear algorithm to compute the tree of shapes of nD images[END_REF] also deserve our attention in this future research direction.

4. We have not reviewed in this manuscript numerous other interesting graph-based approaches which are related to mathematical morphology. Differential equations is one of them. Indeed, discrete settings are recently becoming the subject of numerous studies [START_REF] Desbrun | Discrete exterior calculus[END_REF][START_REF] Grady | Discrete Calculus[END_REF] : the main idea is that one can write on graphs an exact discrete version of differential equations, and efficiently solve many problems. For example, some graph generalizations of the partial differential equations of mathematical morphology [START_REF] Alvarez | Axioms and fundamental equations of image processing[END_REF] can be written [START_REF] Purkait | Super resolution image reconstruction through bregman iteration using morphologic regularization[END_REF][START_REF] Sakaridis | Theoretical analysis of active contours on graphs[END_REF][START_REF] Ta | Nonlocal pdes-based morphology on weighted graphs for image and data processing[END_REF], offering a greater flexibility than the continuous framework (notably, an easy integration of patch-based processing and novel applications). Following the characterization of watersheds in terms of minimum spanning forests, presented in Section 2.2, and the links established in [START_REF] Allène | Some links between extremum spanning forests, watersheds and min-cuts[END_REF] between min-cuts and watersheds, the power-watershed framework is proposed in [START_REF] Couprie | Power watershed : A unifying graph-based optimization framework[END_REF] to unify in a same energy minimization formulation several well-known optimization methods, namely, random-walks, min cuts, shortest path forests and watersheds. Many applications can be designed within this framework including some that are surprising for mathematical morphology : for example the (power) watershed can be used to perform an anisotropic diffusion process [START_REF] Couprie | Anisotropic diffusion using power watersheds[END_REF] or to produce a surface reconstruction from unstructured cloud points [START_REF] Couprie | Surface reconstruction using power watershed[END_REF]. Many other links with seemingly unrelated methods can be searched and found : for example, the popular mean-shift approach [START_REF] Cheng | Mean shift, mode seeking, and clustering[END_REF][START_REF] Comaniciu | Mean shift : A robust approach toward feature space analysis[END_REF] can be seen [START_REF] Paris | A topological approach to hierarchical segmentation using mean shift[END_REF] as computing a max-tree in the feature space, and filtering this max-tree with a depth criterion. We also believe that further exploring the links with variational methods, which have bee widely studied in image processing, may lead to new interesting methods. Exploring the convergence of discrete differential methods towards their continuous counterparts when the space is refined might also lead to interesting results (see, e.g., [START_REF] Coeurjolly | Multigrid convergent principal curvature estimators in digital geometry[END_REF]). Indeed, this family of properties, studied under the name of multigrid convergence [START_REF] Klette | Multigrid convergence of calculated features in image analysis[END_REF], offers the guarantee that the discrete methods behave as one would wait from a modelization in a continuous and regular space. Exploring, detailing and emphasizing such links with other methods is indeed a promising research direction.

5. In Section 4.2, first bases for mathematical morphology filtering on simplicial complexes are presented. In this context, it is possible to obtain a large number of distinct filters since we can choose to condition the presence / absence of an element of dimension i in the result of the filter to the presence / absence of a group of elements of any dimension j between 0 and n in the operand. This increased degree of complexity compared to frameworks based on structuring elements or on graphs is difficult to handle. In particular, the work presented in [START_REF] Dias | Dimensional operators for mathematical morphology on simplicial complexes[END_REF][START_REF] Dias | Some morphological operators on simplicial complex spaces[END_REF] investigates some examples of operators which can be designed on simplicial complexes to reach a better precision on the results but it does not provide systematic means to build all possible morphological operators of the framework. Consequently, we cannot guarantee that the most efficient operators have been found. Providing such construction, which we call morphological calculus on simplicial complexes, will be an interesting topic for our future research. We also note that the morphological operators presented in Section 4.2 relies on an elementary « block » distance in the sense that any edge of the graph (or more generally any element of the complex) has a unit contribution to the length of the geodesics. As a consequence, the results of the operators presented in Section 4.2 depict some digitization artifacts known as « blockinness » effects (see Figure 52). With morphological calculus, we intend to integrate an additional degree of flexibility by letting the operators depend on an arbitrary distance between the elements of the graphs or complexes. For instance, the set of edges and vertices of a 4-adjacency graph can be embedded into an Euclidean space, the distance between two elements is then given as the Euclidean distance between the barycenters of the elements. As illustrated in Figure 52, this setting seems to be an effective way to reduce the « blockiness » effect observed when the implicit distance mentioned above is used.

6. Finally, we notice that the five perspectives presented above, as well as the current improvement in sensor resolutions both result in larger datasets, larger object descriptors, a larger size of working spaces, and higher numbers of iterations of the operators. Hence, this current trend induces a need of extensive computation. In order to cope with this need, advanced hardware architectures might be considered. This includes multi-core shared memory architecture and GPU available on nowadays desktop computers as well as computer clusters. In order to benefit from such architectures, some strategies for distributing the computation must be designed at large grain level. At a finer grain level, it might also be interesting to consider parallelization strategies of the proposed algorithms as well as block computing when the size of the data is too large to fit within the memory of the computation unit. Being able to propose such strategies will probably be an important factor of success to develop the perspectives drawn in this conclusion. -Financement de deux séjours par an pour J. Cousty (4/6 semaines par an) au Brésil.

-Financement de deux post-doctorants pendant un an.

-Financement d'un doctorant brésilien pour effectuer une année sandwich en France.

-Financement CAPES (agence de coordination du perfectionnement du personnel de l'enseignement supérieur brésilien

Figure 1 .

 1 Figure 1. (a) : Original image (cross-section of a brain, after applying a gradient operator). (b) : A segmentation of (a) (obtained by a watershed algorithm [219] using the 4-adjacency relation). (c) : A zoom on a part of (b) ; the graph induced by the 4-adjacency relation is superimposed in gray. (d) : The inner points (black points not adjacent to any white point) of (a). (e) Another zoom on (b) showing two inner points w and z. (f) : A segmentation of (a) with the 8-adjacency relation : there is no inner point.

Figure 2 .Figure 3 .

 23 Figure 2. Illustration of the two perfect fusion grids on Z 2 . The gray squares constitute subsets of the two chessboard on Z 2 and the associated graphs are the subgraphs of the perfect fusion grids (Z 2 , Λ 2 (1,1) ) and (Z 2 , Λ 2 (1,0) ) induced by {0, . . . , 4} × {0, . . . , 4}.

Figure 4 .

 4 Figure 4. (a) : Original image (cross-section of a brain, after applying a gradient operator) ; (b) : a topological watershed of (a) with the 8-adjacency ; (c) : the divide X (white points) of the topological watershed shown in b ; (d) : a zoom on a part of c. The point x is interior for X and w and z are adjacent to a unique connected component of the complementary set X of X.

Figure 5 .

 5 Figure 5. Region merging on a perfect fusion grid ; (a), the divide of a C-watershed of Figure 4(a) ; and (b, c, d), several steps of region merging starting from (b).

Figure 6 .

 6 Figure 6. Illustration of watershed and MSF cuts on edge-weighted graph. (a) A graph G and an edgeweight map w ; the minima of w are depicted in bold ; (b), the set of dashed edges is a watershed cut of w ; and (c), the subgraph in bold is an MSF rooted in the minima of w and the induced MSF-cut is composed by the dashed edges.

Figure 8 .

 8 Figure 8. Results obtained by applying a grayscale watershed on a filtered map. (a), The cameraman grayscale image and (b), an image representation of an edge-weighted graph derived from (a) where the edges are given by the 4-adjacency relation and the weight of an edge is the absolute difference of intensity between the pixels linked by this edge. (c, d) A watershed-cut (with a image area filtering parameter k = 22 pixels) superimposed in white to the original image I ; (e, f ) a watershed in a vertex weighted graph (flooding algorithm of [219]) of the filtered (area parameter k = 22 pixels) Deriche optimal edge detector ; and (g, h) same as (c, d) from a morphological gradient. In each image, the image resolution is doubled in order to superimpose the resulting contours.

Figure 9 .

 9 Figure 9. Diffusion tensor images segmentation. (a) : A close-up on a cross-section of a 3D brain DTI. (b) : Image representation of the markers (same cross-section as (a)), obtained from a statistical atlas, for the corpus callosum (dark gray) and for its background (light gray) (c) : Segmentation of the corpus callosum by an MSF-cut for the markers. The tensors belonging to the component of the MSF which extends the marker labeled "corpus callosum" are removed from the initial DTI : thus the corresponding voxels appear black.

Figure 10 .Figure 11 .

 1011 Figure 10. Illustration of different watersheds from markers. (a) Original image ; (b) the markers are superimposed in black. In the second row the resulting watersheds are superimposed in black to the original image. (c) : Relative MSF ; (d) : watershed by flooding of the Deriche optimal edge detector ; (e) : watershed by flooding of a morphological gradient of the image.

Figure 12 .Figure 13 .

 1213 Figure 12. Illustration of a relation between watersheds and homotopic skeletons. (b) An set. (b) : the distance map of (a) represented as a topographical relief. (c) : a homotopic skeleton of (a). (d) : A watershed of (b).

Figure 15 .Figure 16 .Figure 17 .

 151617 Figure 15. Illustration of 2D simplicial complexes made of the depicted triangles (dark gray), their sides (medium gray) and their corners (sides intersection). (a) A topological torus. (b,c) Pinched tori : the pinchings (of dimensions 0 and 1 respectively) are marked in light gray. The tori in (a) and (b) are pseudomanifolds of dimension 2 whereas the one in (c) is not a pseudomanifold.

Figure 18 .

 18 Figure 18. (a-d) Illustration of a hierarchy H = (P 0 , P 1 , P 2 , P 3 ). For every partition, each region is represented by a gray level : two dots with the same gray level belong to the same region. (e) The hierarchy H is represented as a (component) tree, often called a dendrogram, where the inclusion relation between the regions of the successive partitions is represented by line segments. (f) A graph G such that the hierarchy H is connected for G. (g) The saliency map Φ G (H) for the hierarchy H on G.

Figure 20 .

 20 Figure 20. First column : three color images ; second and third columns : hierarchies of watersheds (saliency maps) driven by area attribute and by dynamics attribute respectively.

Figure 23 .

 23 Figure 23. First and second column : one level of the hierarchies depicted in Figure 20 ; third column : one level of the hierarchies depicted in Figure 22. First (resp. second, and third) row : the partitions contain 500 (resp. 75, and 250) regions.

Figure 24 .

 24 Figure 24. Examples illustrating the results of the method proposed by[START_REF] Felzenszwalb | Efficient graph-based image segmentation[END_REF] and it hierarchization, obtained from the original image (a) : three image segmentations, shown in (b), (c) and (d), are obtained by the method proposed in[START_REF] Felzenszwalb | Efficient graph-based image segmentation[END_REF] when the observation scale k is set such that k = 10000, 8000, 9000 that lead to 4, 7 and 8 regions, respectively. In Figures(b), (c) and (d), the number of regions is not monotonic, when k increases, and the contours between two different k are clearly not stable ; they illustrate the violation of the causality and location principles. In contrast, three image segmentations, shown in (e), (f) and (g), are extracted from the hierarchy computed by our hierarchized version of[START_REF] Felzenszwalb | Efficient graph-based image segmentation[END_REF] : both causality and location principles are respected.

Figure 25 .

 25 Figure 25. Some elementary directed graphs. The set of D-components in (a) (resp. (b) and (c)) are {{a, b}, {b}} (resp. {{a, b}, {c, b}, {b}} and {{a}, {b, a, c}, {c}}).

Figure 26 .

 26 Figure 26. Segmentation results on the DRIVE database. On each row, from left to right : pre-processed image, filtering result, and evaluation of the segmentation.

Figure 27 .

 27 Figure 27. (a) Neurite image ; (b) directed connected filtering.

Figure 28 .

 28 Figure 28. Segmentation based on the D-component hierarchy. (b,c,e) The considered sets are superimposed in red to the original image. (d,f) The internal border of the segmentation results are superimposed in red to the original image.

Figure 29 .

 29 Figure 29. Illustration of a vertex-dilation and of a graph-dilation.

Figure 32 .

 32 Figure 32. illustration of usual ASF applied to the image of Figure 31(top, left). In (a) and (c) the size parameter of the filter is the same as in Figure 31(top, right) whereas in (b) and (c) the number of iterations of basic operators are the same as in Figure 31(top, right).

Figure 33 .

 33 Figure 33. Graphical representation of (a) a 0-simplex, (b) a 1-simplex, (c) a 2-simplex, and (d) a 2-cell.

Figure 34 .

 34 Figure 34. Illustration of morphological dilations and erosions on complexes. The working space C is the simplicial complex represented in black and gray. Some subcomplexes X, Y and Z of C are depicted in gray : Y is a dilation of X and Z is an erosion of X.

Figure 35 .

 35 Figure 35. Example of Left Ventricular Myocardium segmentation. (a) Three orthogonal sections of a volume of the 3D+t cardiac MR image superimposed with the internal border of the segmented LV myocardium ; and (b) a 3D rendering of the segmented LV myocardium.

Figure 36 .

 36 Figure 36. Automated coronary stenosis detection and quantification from CT angiography pipeline.

Figure 37 .

 37 Figure 37. A 3D rendering of a segmented heart for coronaries visualization. Top left : The original volume. Top right : Anterior view of the heart to visualize the right coronary artery (RCA). Bottom left : Inferior view to inspect the posterior descending artery (PDA). Bottom right : Left view showing the left coronary artery with the left anterior descending (LAD) and the circumflex (CX) arteries.

Figure 38 .

 38 Figure 38. Vessel Area Profile : (Top) A lumen view of a diseased vessel. (Bottom) Original and smoothed vessel area profile per 2D section. The vessel theoretic profile is constructed using a robust linear regression

Figure 39 .

 39 Figure 39. Empty catheter appearance in record image (left) and fluoroscopic image (right), all other components of the imaging situation (patient, geometry) are identical. Fluoroscopic images are noisier and the contrasts are weaker than in the record images. Our work is focused on fluoroscopic images which is the main image source during PCI.

Figure 40 .

 40 Figure 40. Curve blobs extraction, from left to right : Input image ; lower level-sets of input image ; corresponding min tree where each node is one of the connected components of the level-sets ; centerlines of the selected curve blobs overlayed on input image.

Figure 41 .

 41 Figure 41. Curve blobs clustering ; from left to right : extracted curve blobs (see Fig 40) ; connection of curve blobs on structural scale-space ; hierarchy of deep connected components (clusters of curve blobs at different scales) ; selected deep connected component.

  (a) Empty catheter segmentation on fluoroscopic images. (b) Empty catheter segmentation on fluoroscopic images (in presence of other elongated interventional and anatomical objects) (c) Estimated centerline of segmented empty catheter from 3 different patients.

Figure 42 .

 42 Figure 42. Results of empty catheter segmentation in X-ray fluoroscopic images. In (a) and (b), from left to right : input image, selected cluster of curve blobs from hierarchy, fitted curve on the cluster (estimated centerline)

Figure 43 .

 43 Figure 43. Illustration of VOIDD algorithm. (top) Iso-phase image pair, i.e., a fluoroscopic image (left) with guidewire tip acquired during the navigation of the tool and the reference image (right) at the same cardiac phase acquired with contrast agent injection before the navigation of the tool ; (bottom left) segmented guidewire tip in fluoroscopic images and (bottom right) the result of matching the detected guidewire to the vasculature as well as the detected vessel of intervention in red.

Figure 44 .

 44 Figure 44. Detected VOI in 12 patient sequences.

Figure 45 .

 45 Figure 45. (a) : Rendering of the coronary sinus segmented from a CT image. (b) : Rendering of the left atrium segmented from a CT image. (c) : An interventional fluoroscopic X-ray image ; a radiocontrast agent is injected in the atrium to evaluate the quality of the resulting registration. (d) Superimposition of the CT model to the fluoroscopic image produced by the proposed software.

Figure 46 .

 46 Figure 46. Some objects of the EROS-3D database : figurines, moulds, vases. The 3D model collection EROS-3D used in this work is provided by the C2RMF (Le Louvre, Paris).

Figure 47 .

 47 Figure 47. RETIN-3D user interface : left, the 3D models are ranked by their classification rate, top left is the model query ; relevant (resp. irrelevant) objects are annotated with a green (resp. red) mark ; at the bottom, the active learning panel. The zoom selected model (right panel) is colored according to the cord length values at each 3D surface point : yellow the low values, blue the high. The RETIN-3D interface allow to zoom and rotate the selected model.

Figure 48 .

 48 Figure 48. Saliency map of a hierarchical watershed (driven by population attribute) on the Knuth Miles dataset (i.e., 128 representative US cities with positions and populations). Each vertex is a city and two neighboring cities are linked by an edge if they share an edge in the Voronoi diagram of the cities. The width and gray-level of an edge is the inverse of its weight in the associated saliency map.

Figure 49 .

 49 Figure 49. Same as Figure 48 but the size of the vertices and of the labels are given by the extinction value (for the population attribute) of the cities.

Figure 50 .

 50 Figure 50. Saliency map of a hierarchical watershed (driven by population attribute) on the Knuth Miles dataset (i.e., 128 representative US cities with positions and populations). The saliency weights are projected on the edges of the Voronoi diagram of the cities.

Figure 51 .

 51 Figure 51. Ranking (from top to bottom and left to right) of the Knuth Miles dataset cities according to catchment basins size (i.e., extinction value of the cities by population attribute).

Figure 52 .

 52 Figure 52. Morphological filtering on graphs with implicit block distance (middle) and with Euclidean distance (right) from the original image depicted on the left.

Table des matières

 des

	1 Introduction
	2 Image segmentation and watersheds

  ). -Participation au projet ANR Kidico (2010-2015). -Participation au projet franco-brésilien CAPES-COFECUB (2008-2014) avec l'Université Paris 6, l'ENSEA, l'UFMG et l'Université de Campinas. Ce projet finance des missions de professeurs français au Brésil et de professeurs brésiliens en France. -Professeur à l'école d'automne de morphologie mathématique organisé par l'Indian Statistical Institute de Bangalore du 19 au 22 octobre 2010 à Bangalore, Inde, http://www.isibang.ac.in/ ~cwjs70/. Logiciels et données mis à disposition de la communauté scientifique -Participation au développement de la bibliothèque libre de traitement d'image PINK : http:// perso.esiee.fr/~coupriem/Pink/doc/html/index.html. -Développement de la bibliotèque SM de segmentation hiérarchiques d'images sur graphes : http: //perso.esiee.fr/~dpt-it/sm. -Développement d'une base de données dédiée à l'évaluation de méthodes de segmentation du myocarde ventriculaire gauche dans des images cardiaques : http://www.laurentnajman.org/heart/ index.html. -Développement, avec Imane Youkana, d'une bibliothèque pour le calcul parallèle de cartes de distance adaptés au filtrage morphologique sur graphe : http://perso.esiee.fr/~dpt-it/MorphoPar/ ParDMaps.tgz.

Je souhaite remercier aussi ESIEE Paris, et son organisme de tutelle, la Chambre de Commerce et d'Industrie de Paris Île-de-France, pour m'avoir offert un environnement favorable au développement de mes travaux de recherche, à la jonction des mondes académique et industriel.Enfin, merci à ma famille et mes amis pour m'avoir soutenu et supporté tout au long de ces années !

†. Note that, in the framework of mathematical morphology, there exists another approach, called watershed from markers[START_REF] Beucher | The morphological approach to segmentation : the watershed transformation[END_REF], to reduce the so-called over-segmentation problem. In many cases, this approach may be seen as a region merging procedure (see[START_REF] Meyer | Minimum spanning forests for morphological segmentation[END_REF]).

Remerciements

Je remercie chaleureusement les membres du jury d'avoir accepté d'évaluer mon travail. Leur temps est précieux. Je suis très honoré qu'ils en aient consacré une partie pour s'intéresser à mes travaux.

Je tiens également a remercier tous mes collègues, enseignant-chercheurs, doctorants et stagiaires, pour les interactions humaines et scientifiques riches que nous avons construites au cours de ces quinze dernières années et qui ont grandement contribué aux travaux présentés dans ce mémoire.

État civil et Coordonnées