Nicolas Passat
email: passat@unistra.fr

Benoît Naegel
email: benoit.naegel@loria.fr

François Rousseau
email: rousseau@unistra.fr

Mériam Koob

Jean-Louis Dietemann

Interactive segmentation based on component-trees

Keywords: Mathematical morphology, component-tree, grey-level images, interactive segmentation

Component-trees associate to a discrete grey-level image a descriptive data structure induced by the inclusion relation between the binary components obtained at successive level-sets. This article presents an original interactive segmentation methodology based on component-trees. It consists of the extraction of a subset of the image component-tree, enabling the generation of a binary object which fits at best (with respect to the grey-level structure of the image) a given binary target selected beforehand in the image. A proof of the algorithmic efficiency of this methodological scheme is proposed. Concrete application examples on magnetic resonance imaging (MRI) data emphasise its actual computational efficiency and its usefulness for interactive segmentation of real images.

Introduction

The component-tree, also known as dendrone [START_REF] Hanusse | Sémantique des images par analyse dendronique[END_REF][START_REF] Chen | Using dendronal signatures for feature extraction and retrieval[END_REF], confinement tree [START_REF] Mattes | Efficient algorithms to implement the confinement tree[END_REF] or max-tree [START_REF] Salembier | Anti-extensive connected operators for image and sequence processing[END_REF], is a graph-based structure which models some characteristics of a grey-level image by considering its binary level-sets obtained from successive thresholding operations. Initially proposed in the field of statistics [START_REF] Wishart | Mode analysis: A generalization of the nearest neighbor[END_REF][START_REF] Hartigan | Statistical theory in clustering[END_REF], the component-tree has been (re)defined in the theoretical framework of mathematical morphology and involved, in particular, in the development of morphological operators [START_REF] Breen | Attribute openings, thinnings, and granulometries[END_REF][START_REF] Salembier | Anti-extensive connected operators for image and sequence processing[END_REF][START_REF] Salembier | Connected operators based on tree pruning strategies[END_REF].

By definition, component-trees are particularly well-suited for the design of methods devoted to process and/or analyse grey-level images based on a priori hypotheses related to the topology (connectedness) and the specific intensity (locally/globally minimal or maximal) of structures of interest. (The case of colour images is currently under investigation [START_REF] Naegel | Component-trees and multivalued images: A comparative study[END_REF][START_REF] Passat | An extension of component-trees to partial orders[END_REF]; the involvement of component-trees in fuzzy grey-level images is described in [START_REF] Palma | Fast fuzzy connected filter implementation using max-tree updates[END_REF].) Based on these properties, but also thanks to methodological developments related to complex knowledge handling [START_REF] Urbach | Vector attribute filters[END_REF][START_REF] Caldairou | Segmentation of complex images based on component-trees: Methodological tools[END_REF][START_REF] Naegel | Combining shape descriptors and component-tree for recognition of ancient graphical drop caps[END_REF], component-trees have been involved in the design of several image processing/analysis applications, especially for filtering/segmentation applications.

It has to be noticed that several works related to component-trees have been devoted to enable their efficient computation, under specific assumptions or in more general cases [START_REF] Mattes | Efficient algorithms to implement the confinement tree[END_REF][START_REF] Salembier | Anti-extensive connected operators for image and sequence processing[END_REF][START_REF] Breen | Attribute openings, thinnings, and granulometries[END_REF][START_REF] Najman | Building the component tree in quasi-linear time[END_REF][START_REF] Menotti | 1D component tree in linear time and space and its application to gray-level image multithresholding[END_REF][START_REF] Berger | Effective component tree computation with application to pattern recognition in astronomical imaging[END_REF][START_REF] Wilkinson | Concurrent computation of attribute filters on shared memory parallel machines[END_REF]. In particular, the ability to compute component-trees in (quasi-)linear time opens the way to the development of interactive and efficient segmentation methods, provided that the operations performed on an image via its component-tree also present a low algorithmic complexity.

The design of interactive segmentation methods is a quite active research field. This dynamism is in particular justified by (i) the increasing necessity to analyse images in a large spectrum of application fields (medical imaging, remote sensing, biometry, metrology, etc.), (ii) the difficulty to develop fully automatic segmentation methods (parametrisation, initialisation, etc.), and (iii) the importance to develop segmentation methods as tools for assisting the user by explicitly using its expertise. Most of interactive segmentation methods require the user's assistance to provide markers enabling to guide the segmentation process, from a parametric and/or geometric point of view, or to "correct" a rough segmentation initially performed in a manual fashion.

In this article, we focus on this second kind of issue, especially in the case where the structures of interest to be segmented are the ones of (local or global) extremal intensities, i.e., the darkest or the brightest ones, which is a frequent case in several applications and especially in medical imaging. In order to illustrate this issue, let us consider the toy-example in Figures 123. The binary image depicted in Figure 1(b) is, for instance, the expected segmentation of the grey-level image depicted in Figure 1(a) for a given set of semantic elements. A user, when performing an initial (manual) segmentation of the same image, in an inaccurate but fast and easy-to-do fashion, will generally obtain results such as the ones proposed in Figure 2 which roughly approximate the desired result. Based on the user-dependent way this initial segmentation is performed, we may obtain different kinds of initial segmentations: undersegmentation (Figure 2(a)), oversegmentation (Figure 2(b)), or mixed under/oversegmentation (Figure 2(c)). Such results will lead to the generation of false positives and/or false negatives (see Figure 3). A crucial issue then consists in removing, automatically, or at least quite easily in an interactive way, these errors in order to finally obtain a correct segmentation result.

In this article, we propose a method enabling to tackle this problem by considering the component-tree of the image to be segmented, and by finding the best segmentation induced by this component-tree with respect to an initial approximate segmentation provided by the user. More formally, we propose to answer the following question:

(Q) Let I be a grey-level image (Figure 1(a)), let T be its component-tree, and let M be a binary object defined on the same domain as I (a manual segmentation, Figure 2); how can we determine a part of T , and thus a part S of I (Figure 1(b)) which enables to fit at best M with the lowest computational cost?

This "best" segmentation can, in particular, be considered from a quantitative point of view, by finding a solution S which minimises the amount of false positives/negatives between S and M, which is actually supposed to be close to the correct result.

Such a question can be crucial, for instance to develop image analysis procedures involving ground-truth data [START_REF] Caldairou | Segmentation of complex images based on component-trees: Methodological tools[END_REF] or to propose assisted-segmentation procedures such as the ones which will be described in the last sections.

The sequel of this article is organised as follows. Section 2 presents related works dealing with component-trees in image analysis and with interactive segmentation methods. In Section 3, usual definitions related to digital imaging and component-trees are recalled, making this article self-contained. The contributions of this article are located in Sections 4-6:

• A theoretical study (Section 4) is proposed to answer question (Q), and to prove the algorithmic efficiency of the proposed solution.

• An interactive segmentation methodology, based on these theoretical results is described (Section 5).

• The methodology is applied on medical images, namely cerebral magnetic resonance data of adults and foetuses (Section 6). Its efficiency is then assessed by comparison to other strategies.

Concluding remarks and perspectives will be found in Section 7. For the sake of readability and concision, all the proofs are provided in Appendix A, at the end of the article.

Related works

This section presents previous works devoted to the use of component-trees for image processing/analysis and an overview of interactive segmentation methods, then enabling to position the proposed work in its methodological and applicative context.

Component-trees

Component-trees have been involved in the development of several applications related to image processing and analysis. Most of these methods are devoted to filtering and/or segmentation 1 . In particular, a large part of them have been developed for (bio)medical image processing: vessels [START_REF] Wilkinson | Shape preserving filament enhancement filtering[END_REF][START_REF] Urbach | Shape-only granulometries and gray-scale shape filters[END_REF][START_REF] Caldairou | Attribute-filtering and knowledge extraction for vessel segmentation[END_REF] and brain structures [START_REF] Dokládal | Topologically controlled segmentation of 3D magnetic resonance images of the head by using morphological operators[END_REF] segmentation from 3D magnetic resonance or X-ray data, melanocytic nevi segmentation from dermatological photographs [START_REF] Naegel | Segmentation using vector-attribute filters: methodology and application to dermatological imaging[END_REF], neuron filtering in 3D confocal microscopy or extraction of protein chains from 2D data [START_REF] Ouzounis | Mask-based second-generation connectivity and attribute filters[END_REF]. Other methods have also been developed for a large spectrum of application fields: segmentation of video data [START_REF] Salembier | Anti-extensive connected operators for image and sequence processing[END_REF], segmentation of wood micrograph [START_REF] Jones | Connected filtering and segmentation using component trees[END_REF], segmentation of astronomical data [START_REF] Berger | Effective component tree computation with application to pattern recognition in astronomical imaging[END_REF] and document analysis [START_REF] Naegel | Combining shape descriptors and component-tree for recognition of ancient graphical drop caps[END_REF].

Note that other kinds of image processing applications have been considered, in particular, image registration [START_REF] Mattes | Tree representation for image matching and object recognition[END_REF][START_REF] Mattes | Efficient algorithms to implement the confinement tree[END_REF], image compression [START_REF] Salembier | Anti-extensive connected operators for image and sequence processing[END_REF], image retrieval [START_REF] Mosorov | A main stem concept for image matching[END_REF][START_REF] Alajlan | Geometry-based image retrieval in binary image databases[END_REF], image classification [START_REF] Urbach | Connected shape-size pattern spectra for rotation and scale-invariant classification of gray-scale images[END_REF], interactive 3D visualisation [START_REF] Westenberg | Volumetric attribute filtering and interactive visualization using the max-tree representation[END_REF], multithresholding [START_REF] Menotti | 1D component tree in linear time and space and its application to gray-level image multithresholding[END_REF] or document binarisation [START_REF] Naegel | A document binarization method based on connected operators[END_REF].

In the field of filtering/segmentation, all the proposed methods have been designed to detect the structures of interest by using information related to the value of attributes stored at each node of the tree. In such strategies, an attribute or, more generally, a set of attributes, are chosen according to the hypotheses related to the applicative context. These attributes are assumed to model some characteristic properties of the structures of interest, and can be used in different ways:

• the desired values of the attributes (or the number of nodes of maximal value [START_REF] Dokládal | Topologically controlled segmentation of 3D magnetic resonance images of the head by using morphological operators[END_REF]) can be chosen by the user in order to select the relevant nodes and thus obtain the associated segmentation [START_REF] Wilkinson | Shape preserving filament enhancement filtering[END_REF][START_REF] Urbach | Shape-only granulometries and gray-scale shape filters[END_REF][START_REF] Berger | Effective component tree computation with application to pattern recognition in astronomical imaging[END_REF][START_REF] Ouzounis | Mask-based second-generation connectivity and attribute filters[END_REF];

• the relevant values can be determined by analysing the signature of the attribute, i.e., the evolution of their value with respect to the grey-level of the nodes [START_REF] Jones | Connected filtering and segmentation using component trees[END_REF];

• the relevant values can be learnt from examples, e.g., by providing segmented ground-truth directly characterising the shape of the objects to be detected [START_REF] Naegel | Segmentation using vector-attribute filters: methodology and application to dermatological imaging[END_REF], or by feeding a classification process, in particular when the set of attributes becomes to large [START_REF] Urbach | Connected shape-size pattern spectra for rotation and scale-invariant classification of gray-scale images[END_REF][START_REF] Caldairou | Segmentation of complex images based on component-trees: Methodological tools[END_REF][START_REF] Naegel | Combining shape descriptors and component-tree for recognition of ancient graphical drop caps[END_REF].

In these works, component-trees have then only been used for their ability to discriminate nodes with respect to attributes, thus leading to automated/parametric segmentation methods.

It is however possible to directly use the component-tree structure by taking advantage of the spatial/photometric decomposition of the image into nodes/connected components that it provides, in order to perform interactive segmentation. Methods based on such an alternative strategy should compute a segmentation result, no longer thanks to node attributes, but to a user-defined approximate result, which should then be matched at best by a relevant set of nodes, as discussed in Section 1. To the best of our knowledge, the methodology proposed in the next sections is the first one based on this strategy.

Interactive segmentation

Automatic segmentation algorithms do not always provide accurate results and are sometimes not sufficiently robust, especially in application fields in which images are prone to variability. Moreover, it is often crucial to achieve a precise segmentation of an image (for instance, to build ground-truths or in the context of computer-aided diagnosis) in a reasonable time.

The design of interactive segmentation methods is then an active research field and provides a solution to this by allowing a user to guide and/or refine the segmentation in an interactive fashion. The purpose of an interactive segmentation algorithm is to speed up the time consuming process of manual segmentations (which are, moreover, prone to errors and imprecision in the localisation of object contours). Interactive segmentation algorithms can also help to ensure the reproducibility between different segmentations of identical images, provided for example by different experts. Several ways to introduce interaction in a segmentation process have been considered, depending on the segmentation strategy:

• model initialisation, fine tuning of parameters and eventually interactive model refinement in the context of deformable or level-set based models [START_REF] Kass | Snakes: Active contour models[END_REF][START_REF] Sethian | Level Set Methods and Fast Marching Methods: Evolving Interfaces in Computational Geometry[END_REF];

• delineation of the object of interest by successive interactive selections of optimal boundaries between the current cursor position and previously specified seeds positions in the context of intelligent scissors or live-wire algorithms, which are based on an optimal path search in a weighted graph [START_REF] Barrett | Interactive live-wire boundary extraction[END_REF][START_REF] Mortensen | Interactive segmentation with intelligent scissors[END_REF];

• manual depiction of foreground and background markers in the context of watershed algorithm [START_REF] Vincent | Watersheds in digital spaces: an efficient algorithm based on immersion simulations[END_REF][START_REF] Bertrand | Watersheds in discrete spaces[END_REF], seededregion growing based algorithms [START_REF] Adams | Seeded region growing[END_REF][START_REF] Mehnert | An improved seeded region growing algorithm[END_REF], graph-cuts [START_REF] Boykov | Interactive graph cuts for optimal boundary & region segmentation of objects in N-D images[END_REF][START_REF] Boykov | Graph cuts and efficient N-D image segmentation[END_REF] or binary-partition tree algorithms [START_REF] Salembier | Binary partition tree as an efficient representation for image processing, segmentation and information retrieval[END_REF][START_REF] Adamek | Using contour information and segmentation for object registration, modeling and retrieval[END_REF]. A comparative evaluation of interactive segmentation algorithms based on interactive marker selection is available in [START_REF] Mcguinness | A comparative evaluation of interactive segmentation algorithms[END_REF].

It could also be noted that most segmentation strategies can be used either in an unsupervised or semi-supervised fashion. By contrast with the above methods, the algorithm proposed in this paper involves only the rough delineation of foreground objects (and not background parts) and is based on a single scalar parameter (α) allowing to quickly browse among the different possible segmentations. Moreover, we focus in this article on the frequent case where the structures of interest to be segmented are the ones of locally extremal intensities.

Background notions

In this section, we recall standard notions related to component-trees. For complementary details, the reader may also refer to [START_REF] Salembier | Anti-extensive connected operators for image and sequence processing[END_REF][START_REF] Jones | Connected filtering and segmentation using component trees[END_REF][START_REF] Najman | Building the component tree in quasi-linear time[END_REF].

Definitions and notations

Let n ∈ N * . Let us consider an adjacency relation on the discrete grid defined by Z n , for instance, the 2n-or the (3 n -1)-adjacency, i.e., the 4-(resp. the 6-) or the 8-(resp. the 26-) adjacency in Z 2 (resp. Z 3 ). Let X ⊆ Z n be a non-empty set of Z n .

We say that two points x, y ∈ X are connected (in X), and we note x ∼ X y, if there exists a sequence (x k ) t k=1 (t ≥ 1) of elements of X such that x 1 = x, x t = y and x k , x k+1 are adjacent for all k ∈ [[1, t -1]]. Note that ∼ X is an equivalence relation on X. The connected components of X are the elements of the quotient set X/∼ X (noted C[X] in the sequel). We say that X is connected if

C[X] = {X}. Let E ⊂ Z n be a finite connected set. Let ⊥ < ⊤ ∈ Z. Let V = [[⊥, ⊤]] ⊂ Z.
A discrete grey-level image I can be defined as a function I : E → V (we also note I ∈ V E ).

For any v ∈ V, we define the thresholding function X v by

X v : V E → P(E) I → {x ∈ E | v ≤ I(x)}
where

P(E) = {Y | Y ⊆ E}.
For any v ∈ V, and any X ⊆ E, we define the cylinder function C X,v by

C X,v : E → V x → v if x ∈ X ⊥ otherwise
A discrete image I ∈ V E can then be expressed as

I = v∈V C X v (I),v = v∈V X∈C[X v (I)] C X,v
where is the pointwise supremum for the sets of functions.

Component-trees

Let K = v∈V C[X v (I)] be the set of all the connected components obtained from the different thresholdings of I at values v ∈ V. The inclusion relation ⊆ is then a partial order on

K. Let v 1 ≤ v 2 ∈ V. Let B 1 , B 2 ⊆ E be the binary images defined by B k = X v k (I) for k ∈ {1, 2}. Let C 2 ∈ C[B 2 ] be a connected component of B 2 . Then, there exists a (unique) connected component C 1 ∈ C[B 1 ] of B 1 such that C 2 ⊆ C 1 .
Based on these properties, it can be easily deduced that the Hasse diagram of the partially ordered set (K, ⊆) is a tree (i.e., a connected acyclic graph), and more especially a rooted tree, the root of which is the supremum X ⊥ (I) = E. This tree is called the component-tree of I. Definition 1. Let I ∈ V E be a grey-level image. The component-tree of I is the rooted tree T = (K, L, R) such that:

K = v∈V C[X v (I)] L = (X, Y) ∈ K 2 Y ⊂ X ∧ ∀Z ∈ K, Y ⊆ Z ⊂ X ⇒ Y = Z R = sup(K, ⊆) = X ⊥ (I) = E
The elements of K (resp. of L) are the nodes (resp. the edges) of T . The element R is the root of T . For any N ∈ K,

we set ch(N) = {N ′ ∈ K | (N, N ′ ) ∈ L}
which is the set of the children of the node N in T . An example of component-tree defined for a 2D image is illustrated in Figures 4 and5.

Each node of K is a binary connected component distinct from all the other nodes. However, such a connected component can be an element of C[X v (I)] for several (successive) values v ∈ V. For each X ∈ K, we set

m(X) = max{v ∈ V | X ∈ C[X v (I)]} = min x∈X {I(x)}
We then consider that X is "associated" to the value m(X), i.e., to the highest value of V which generates this connected component. This choice is justified by reconstruction considerations which will be detailed in Section 4.1. An example of such an element X can be observed in Figures 4(e) and (f) (on the right side of the images), where it corresponds to a same binary connected component, while it generates only one node at the level v = 4 (which is the child of a node at the level v = 2) in the component-tree depicted in Figure 5.

The following definition, establishing "correlation scores" between a node and a given binary object, will be useful in the sequel of the article.

Definition 2. Let I ∈ V E be a grey-level image. Let T = (K, L, R) be the component-tree of I. Let N ∈ K be a node of T . Let G ⊆ Z n be a binary object. We set p(N, G) = |N ∩ G| p * (N, G) = |(N \ N ′ ∈ch(N) N ′ ) ∩ G| n(N, G) = |N \ G| n * (N, G) = |(N \ N ′ ∈ch(N) N ′ ) \ G|

The value p(N, G) (resp. n(N, G)) is the number of points of N which belong (resp. do not belong) to G. Note in particular that p(N, G) + n(N, G) = |N|

The value p * (N, G) (resp. n * (N, G)) is the number of points of N which belong (resp. do not belong) to G and which do not belong to any children of N. Note in particular that

p * (N, G) + n * (N, G) = |N \ N ′ ∈ch(N) N ′ | Remark 3.
When building the component-tree of I, it is possible to store, at each node N ∈ K, the set of points

E N = N \ N ′ ∈ch(N) N ′ (1)
This leads, in particular, to an algorithmically useful partition {E N } N∈K of E. In such conditions, for a given binary object G ⊆ Z n , the computation of all the p(N, G), p * (N, G), n(N, G) and n * (N, G) (N ∈ K) can obviously be performed in linear time O(|E|). In the sequel, we will assume that p(N, G), p * (N, G), n(N, G) and n * (N, G) have been computed and are then available for every node N ∈ K.

Image processing based on component-trees

Component-trees can be used to develop image processing/analysis procedures based on filtering or segmentation strategies [START_REF] Jones | Connected filtering and segmentation using component trees[END_REF]. Such procedures generally consist in determining a subset K ′ ⊆ K among the nodes of the componenttree

T = (K, L, R) of a considered image I : E → V.
When performing filtering, the (grey-level) resulting image I f : E → V induced by this set of nodes K ′ can be reconstructed as

I f = X∈K ′ C X,m(X) (2)
For instance, let us consider again the image I of Figure 1(a), also depicted in Figure 6(a). Let T = (K, L, R) be the component-tree of I, depicted in Figure 6(b), and let K ′ ⊆ K be a subset of nodes of T , depicted in Figure 6(c). By applying Equation (2) on this set of nodes, we will then generate a filtered image I f corresponding to the one depicted in Figure 7(a). Note that in this image, the grey-levels of the three nodes are preserved since each node X ∈ K ′ is associated to a cylinder function of value m(X) (equal, for these three nodes, to 2, 3 and 4 respectively).

When performing segmentation, the (binary) resulting image I s ⊆ E is defined as the union of the nodes of K ′ , i.e., as

I s = X∈K ′ X
By applying this equation on the set of nodes K ′ ⊆ K of Figure 6(c), we will generate a segmented image I s corresponding to the one depicted in Figure 7(b).

In this last context, the determination of the nodes to preserve is a complex issue, which can be handled by considering attributes (i.e., qualitative or quantitative information related to each node) to characterise the nodes of interest. An alternative solution is to search the set of nodes K ′ ⊆ K which enables to generate a binary object being as similar as possible to a given binary target (e.g., an approximate segmentation obtained from a manual process). In the sequel of the article, we focus on this specific issue, which can be formalised as an optimisation problem.

Theoretical study

Problem to solve

Let I ∈ V E be a grey-level image. Let T = (K, L, R) be the component-tree of I. Let M ⊆ E be a binary image. Let d be a distance on P(E). Question (Q), in Section 1, can then be reformulated as follows.

(Q') How can we compute a set of nodes K ′ ⊆ K such that d( N∈K ′ N, M) is minimal, i.e., such that the best binary object which can be built from K is as close as possible to M? More formally, the problem can be summarised as a minimisation problem, consisting in determining2 K = arg min

(a) v = v = v = v = 2 3 4 v = 1 0 (b) (c)
K ′ ∈P(K) d N∈K ′ N, M
An intuitive solution for determining a useful distance d is to consider the amount of false positives/negatives induced by N∈K ′ N with respect to the considered binary object of interest M.

Definition 4. Let α ∈ [0, 1]. Let d α : P(E) × P(E) → R + be the function defined by d α (X, Y) = α.|X \ Y| + (1 -α).|Y \ X| (3)
The pseudo-distance3 d α constitutes a good similarity criterion between binary objects. Note that

d 0 (X, Y) = |Y \ X| d 1 (X, Y) = |X \ Y| i.e., d 0 (X, Y) (resp. d 1 (X, Y))
is the amount of false negatives (resp. false positives) in X with respect to Y.

In the next sections, we will consider this distance. It will be established that it leads to algorithmically efficient processes, and satisfactory applicative results.

Preliminary properties

The following property directly derives from the definitions of Section 3.2.

Property 5. Let I ∈ V E be a grey-level image. Let T = (K, L, R) be the component-tree of I. Let N ∈ ch(E). Let K N = {N ′ ∈ K | N ′ ⊆ N}. Let I |N ∈ V N
be the grey-level image corresponding to the restriction of I to the node N. The Hasse diagram (K N , L N ) of the partially ordered set (K N , ⊆) enables to define the component-tree

T N = (K N , L N , N) of I |N which is actually a subtree of T . Note in particular that {E} ∪ {K N } N∈ch(E) is a partition of K, while {(E, N)} N∈ch(E) ∪ {L N } N∈ch(E) is a partition of L.
Definition 6. Let I ∈ V E be a grey-level image. Let T = (K, L, R) be the component-tree of I. Let x ∈ E. We set

K x = {N ∈ K | x ∈ N}
which is the subset of all the nodes of K which contain x.

Since E ∈ K, the following property is obvious, while the next one derives from the structure of the componenttree.

Property 7. Let I ∈ V E be a grey-level image. Let T = (K, L, R) be the component-tree of I. Let x ∈ E. Then, K x is non-empty. Property 8. Let I ∈ V E be a grey-level image. Let T = (K, L, R) be the component-tree of I. Let x ∈ E. Then, (K x , ⊆) is a completely ordered set.
Definition 9. Let I ∈ V E be a grey-level image. Let T = (K, L, R) be the component-tree of I. We define the function

G : P(K) → P(E) K ′ → N∈K ′ N We set Q = G(P(K)) = {G(K ′ )} K ′ ⊆K
which is the set of all the binary objects which can be generated from the subsets of nodes of K.

Although there exist 2 |K| distinct subsets K ′ of K, most of these subsets generate a same binary object of E, more formally, we have |Q| ≤ |P(K)| (and generally |Q| ≪ |P(K)|). Property 10. Let I ∈ V E be a grey-level image. Let T = (K, L, R) be the component-tree of I. Let Q be the set of the objects which can be generated from the subsets of nodes of K. Let Q ∈ Q. Then, we have

C[Q] = min ⊆ G -1 (Q)
Less formally, the set of the connected components of Q is actually a subset of nodes of K which is included in any other subset of nodes K ′ of K generating Q. Such sets K ′ are then redundant (they contain in particular some nodes which are included in other nodes, and then useless for the generation of Q).

Main properties 4.3.1. Smallest superset / largest subset

In this subsection, we first focus on a specific case of the considered issue, which consists in finding a subset of nodes of the component-tree of an image I such that the object generated by these nodes is included in (resp. includes) the binary target G and is the largest (resp. the smallest) one verifying this property. This problem is equivalent to consider a distance d which only takes into account the amount of false negatives (resp. false positives) with respect to G (the link between such a distance d and the distance d α of Definition 4 will be discussed in the next subsection).

From an applicative point of view, solving this specific problem makes sense when the initial rough segmentation proposed by the user is larger than (or smaller than) the desired result, as illustrated, for instance, by Figures 1(a,b), 2(a,b), and 3(a,b), in Section 1.

The following property establishes that there exists a (unique) solution to this problem.

Property 11. Let I ∈ V E be a grey-level image. Let T = (K, L, R) be the component-tree of I. Let Q be the set of the objects which can be generated from the subsets of nodes of

K. Let G ⊆ E. Then there exist G + , G -∈ Q such that G + = min ⊆ {Q ∈ Q | G ⊆ Q} G -= max ⊆ {Q ∈ Q | Q ⊆ G}
We define now two functions which enable to compute these solutions G + and G -(Definition 12, Properties 13 and 14) and we show that they authorise a computation in linear time with respect to the size (i.e., the number of nodes) of the component-tree of the considered image I or the size of the support E of this image (Property 15). Definition 12. Let I ∈ V E be a grey-level image. Let T = (K, L, R) be the component-tree of I. Let G ⊆ E. Let F + , F -∈ P(K) K be the functions recursively defined, for all N ∈ K, by

F + (N) = {N} if p * (N, G) 0 N ′ ∈ch(N) F + (N ′ ) if p * (N, G) = 0 F -(N) = {N} if n(N, G) = 0 N ′ ∈ch(N) F -(N ′ ) if n(N, G) 0 In particular, if ch(N) = ∅, we have N ′ ∈ch(N) F -(N ′ ) = N ′ ∈ch(N) F + (N ′ ) = ∅,
which guarantees the termination of these recursive definitions.

Property 13. Let σ ∈ {+, -}. Let I ∈ V E be a grey-level image. Let T = (K, L, R) be the component-tree of I. Let G ⊆ E. Then we have C[G σ ] = F σ (E)
The following property immediately derives from Property 13.

Property 14. Let σ ∈ {+, -}. Let I ∈ V E be a grey-level image. Let T = (K, L, R) be the component-tree of I. Let G ⊆ E. Then we have G σ = N∈F σ (E) N Property 15. Let σ ∈ {+, -}. Let I ∈ V E be a grey-level image. Let T = (K, L, R) be the component-tree of I. Let G ⊆ E. Then C[G σ ]
(and thus G σ ) can be computed with a linear algorithmic complexity O(max{|K|, |E|}), with respect to the number of nodes of the tree or the size of the image.

General case

We now focus on the general case of the problem stated in Section 4.1, which consists in finding a set of nodes K of the component-tree of an image I verifying Equation (3), for the distance d α proposed in Definition 4. The purpose is then to find the best compromise (according to a chosen weight α ∈ [0, 1]) between the amount of false positives and false negatives with respect to a binary target G.

Since the set Q of the objects which can be generated from the subsets of nodes of a component-tree is finite, there necessarily exists a solution to this problem. Hereafter, we show that such a solution (Definition 16) can be computed in linear time with respect to the size (i.e., the number of nodes) of the component-tree of the considered image I or the size of the support E of this image (Properties 19 and 20).

Definition 16. Let α ∈ [0, 1]. Let I ∈ V E be a grey-level image. Let T = (K, L, R) be the component-tree of I. Let G ⊆ E. Let ≺ ∈ {<, ≤}. Let F α : K → P(K) and c α : K → R + be the functions recursively cross-defined, for all N ∈ K, by F α (N) = {N} c α (N) = α.n(N, G) if α.n(N, G) ≺ (1 -α).p * (N, G) + N ′ ∈ch(N) c α (N ′ ) and F α (N) = N ′ ∈ch(N) F α (N ′ ) c α (N) = (1 -α).p * (N, G) + N ′ ∈ch(N) c α (N ′ ) otherwise.
In particular, if ch(N) = ∅, we have N ′ ∈ch(N) F α (N ′ ) = ∅ (which guarantees the termination of these recursive definitions), and

N ′ ∈ch(N) c α (N ′ ) = 0. Definition 17. Let α ∈ [0, 1]
. Let I ∈ V E be a grey-level image. Let T = (K, L, R) be the component-tree of I. Let Q be the set of the objects which can be generated from the subsets of nodes of K. Let G ⊆ E. We define G α ∈ Q as

G α = N∈F α (E)

N

From a reasoning similar to (and actually simpler than) the one of Property 13, we have the following result.

Property 18. Let α ∈ [0, 1]. Let I ∈ V E be a grey-level image. Let G ⊆ E. Then we have

F α (E) = C[G α ] Property 19. Let α ∈ [0, 1]
. Let I ∈ V E be a grey-level image. Let T = (K, L, R) be the component-tree of I. Let Q be the set of the objects which can be generated from the subsets of nodes of K. Let G ⊆ E. Then, we have

d α (G α , G) = c α (E) = min Q∈Q {d α (Q, G)} Property 20. Let α ∈ [0, 1]. Let I ∈ V E be a grey-level image. Let G ⊆ E. Then F α (E) = C[G α ]
(and thus G α ) can be computed with an algorithmic complexity O(max{|K|, |E|}), linear with respect to the number of nodes of the tree or the size of the image.

Remark 21.

The set of nodes F α (E) and its associated binary object G α enable to minimise d α (., G), and thus to obtain an optimal solution to the issue considered in this work. However, F α (E) and G α are generally not unique.

To illustrate this assertion, let us consider the trivial case where G = ∅ (resp. G = E) and α = 0 (resp. α = 1).

Obviously, in such a case, any set of nodes and any associated binary object minimise d 0 (., G) (resp. d 1 (., G)), which is always equal to 0. However, the way to define ≺ in Definition 16 enables to break this non-determinism by choosing to favour the smallest (<) or the largest (≤) solution (with respect to the inclusion relation ⊆) among all the possible ones. In particular, if ≺ is set to < (resp. to ≤) we have F + = F 0 (resp. F -= F 1 ) (the easy proof of this assertion is left to the reader), which enables to establish a link between the studies of Sections 4.3.1 and 4.3.2.

Methodology / technical details

Algorithmics

From the above study, which provides an answer to the question stated in Section 1, we can derive the method described in Algorithm 1. For the sake of simplicity, Algorithm 1 is described in a non-optimal but easy-to-understand way. In particular, the method is presented in an iterative fashion, while it is intrinsically recursive.

In its general form, the method corresponds to Definition 16, which solves the general case considered in Section 4.3.2. In the specific case where α = 0 and ≺ = < (resp. α = 1 and ≺ = ≤), the method corresponds to the computation of F + (resp. F -) in Definition 12, which solves the specific case of the smallest result including (resp. the largest result included in) the rough segmentation, considered in Section 4.3.1.

From this segmentation method, we can straightforwardly derive the (naive) interactive segmentation method described in Algorithm 2. By definition, Step 1 of this method presents a complexity O(k. max{|K|, |E|}), since Algorithm 1 has to be performed k times. Once this precomputation performed, the interactive choice of the result can be done by the user by inspection of the k proposed binary results.

By opposition to the case of a thresholding operation on a grey-level image, where

X v 2 (I) ⊆ X v 1 (I) whenever ⊥ ≤ v 1 < v 2 ≤ ⊤, we may think that sometimes G α 2 G α 1 while 0 ≤ α 1 < α 2 ≤ ⊤.
Fortunately, as stated by the following property, the increasing property of thresholding is actually inherited by the developed method.

Property 22. Let I ∈ V E be a grey-level image. Let G ⊆ E. Let α 1 < α 2 ∈ [0, 1]. Then we have G α 2 ⊆ G α 1 .

Algorithm 1 -Segmentation method

Input I : E → V (image to be segmented) R ⊆ E (rough segmentation of I) α ∈ [0, 1] (weight parameter for false positives/negatives) ≺ ∈ {<, ≤} (order involved in the cost minimisation formula) Prune T by removing from K all the successive children of F α i+1 Compute F α i and S α i from T by applying Steps 2 and 3 of Alg. 1 end for 2-b -Segmentation results computation ("Splitting strategy") Compute F α 1 and S α 1 from T by applying Steps 2 and 3 of Alg. 1 for i from 2 to k do

Output G α ⊆ E (final segmentation of I) Algorithm 1 -Component-tree computation T = (K, L, R) (component-tree of I) for all N ∈ K do E N = N \ N ′ ∈ch(N) N ′ p * (N, G) = |E N ∩ G| n(N, G) = |N \ G| end for 2 -Cost minimisation for v = ⊤ to ⊥ do for all N ∈ K such that m(N) = v do if ch(N) = ∅ (i.e., if N is a leaf) then if α.n(N, G) ≺ (1 -α).p * (N, G) then c α (N) = α.n(N, G) F α (N) = {N} else c α (N) = (1 -α).p * (N, G) F α (N) = ∅ end if else if α.n(N, G) ≺ (1 -α).p * (N, G) + N ′ ∈ch(N) c α (N ′ ) then c α (N) = α.n(N, G) F α (N) = {N} else c α (N) = (1 -α).p * (N, G) + N ′ ∈ch(N) c α (N ′ ) F α (N) = N ′ ∈ch(N) F α (N ′ ) end if end if end for end for 3 -Result computation G α = N∈F α (E) N

Algorithm 2 -Interactive segmentation method (naive version)

Input I : E → V (image to be segmented) R ⊆ E (rough segmentation of I) {α i } k i=1 (with k ≥ 2)
F α i = ∅ for all N ∈ F α i-1 do Let T N be the subtree of T induced by N (see Property 5) Compute F α i N from T N by applying Step 2 of Alg. 1 F α i = F α i ∪ F α i N end for Compute G α i from F α i (Step 3 of Alg. 1) end for 3 -Segmentation choice Let S k = k i=1 C S α i ,i (see Eq. 4) Choose G ⋆ ∈ {G α i } k i=1 by a standard thresholding of S k
The first consequence of this property is the ability to store the k different results obtained for k increasing values 0 ≤ α 1 < α 2 < . . . < α k-1 < α k ≤ 1, induced by a method such as the one described in Algorithm 2, as a grey-level image S k : E → [ [1, k]] defined -similarly to the filtering process proposed in Section 4.1 (Equation 2)-by

S k = k i=1 C G α i ,i (4)
where G α i ⊆ E is the binary result of the segmentation method (Algorithm 1) for the parameter α i . In such a situation, we can avoid to store k distinct binary images, and the interactive choice of the result by the user can be performed (of course, in real-time) by actually performing a standard thresholding of S k among the values [ [1, k]] (these values being associated to the set of parameters {α i } k i=1 by the trivial one-to-one mapping induced by Equation 4). The second consequence of Property 22 is the possibility to optimise the computation of the k solutions G α i by taking advantage of the fact that G α 2 ⊆ G α 1 whenever α 1 < α 2 . Indeed, let us suppose that for α ∈ [0, 1], a given node N ∈ K belongs to set of nodes F α which generates the solution G α , i.e., that N is a connected component of G α . Then, for any α -< α (resp. α + > α), N will necessarily be included in a connected component of G α -(resp. N will include all the connected components of G α + that it intersects). This implies in particular that two strategies can be considered for computing k solutions G α i with 0 ≤ α 1 < α 2 < . . . < α k-1 < α k ≤ 1:

1. "Pruning strategy", where the sets F α i are computed from i = k to 1. Once F α i has been computed, all the nodes which are children of a node of F α i are removed from the current component-tree (since these nodes are no longer eligible for lower values of α). The next set of nodes F α i-1 is then computed from this pruned component-tree. [START_REF] Caldairou | Segmentation of complex images based on component-trees: Methodological tools[END_REF] 2. "Splitting strategy", where the sets F α i are computed from i = 1 to k. Once F α i has been computed, the component-tree associated to each sub-image induced by a connected component of G α i (i.e., each node of F α i , see Property 5) is built. The next set of nodes F α i+1 is then computed as the union of the results of the process on each one of these component-trees (since the nodes which have no node of F α i among their successive children are no longer eligible for higher values of α).

In the worst case (i.e., when G α k = E for the "Splitting strategy" and G α 1 is only composed of leaves for the "Pruning strategy"), the algorithmic complexity of these strategies remains the one of Step 1 of Algorithm 2, namely O(k. max{|K|, |E|}). However, in real applications, we may reasonably suppose that the complexity will significantly decrease since the successive G α will progressively become larger/smaller (enabling to reduce the size of the image to be processed and/or the number of considered nodes during the successive solution computations).

The two optimised versions of the interactive segmentation method are described in Algorithm(s) 3.

Software

This section describes the actual image segmentation tool which may be developed based on the theoretical and methodological studies presented above4 .

Nodes selection

Component-tree computation. The component-tree is computed using Salembier's algorithm [START_REF] Salembier | Anti-extensive connected operators for image and sequence processing[END_REF], which is based on a recursive flooding of an image from its maxima 5 .

For each node N are stored two attributes related to the current marker G: p * (N, G) and n(N, G). These attributes are computed during the tree computation, using a minor modification of Salembier's algorithm. For efficiency reasons and to avoid redundancies, each pixel is stored in only one node of the tree, which is the highest node containing the pixel. Therefore, for each node N is stored exactly the set of pixels defined by

E N = N \ N ′ ∈ch(N) N ′ The computation of p * (N, G) = |E N ∩ G|
involves only pixels stored in node N: this attribute can therefore be updated each time a new pixel is stored in a node N during the component-tree computation. The computation of n(N, G) = |N \ G| involves pixels which are not all stored in N. Therefore, each time a new pixel is stored in a node N is updated the value n * (N, G) = |E N \ G| during the tree computation. A second pass is then necessary to compute n(N, G) for each node, based on the property: n(N, G) = N ′ ∈ch(N) n * (N ′ , G). This is achieved using a depth-first scan of the tree nodes.

Interactive segmentation

Interactive segmentation is based on two information: the marker image and the value of the α parameter. Depending on the application, the user may interact on one or both of them.

In the case where only the α parameter is used, it can be advantageous to use the increasing property (Property 22) of the nodes selection procedure. This way, the results associated to various α sampled at regular values can be precomputed, in order to speed up the interactive and visualisation process. This method is summarised in Algorithm 3.

In the other case where both parameters (marker image and α value) are used, it can be more advantageous to recompute the segmentation result each time a new value of α is selected. In this case, the attributes p * (N, G) and n(N, G) stored in each node need also to be recomputed each time a new marker image is validated. An interactive procedure can then be designed using the following scheme:

1. component-tree computation (automatic step); 2. manual drawing of a marker image (user interaction); 3. attributes computation (automatic step); 4. choice of an α value (user interaction) ; 5. result computation (automatic step); 6. if the result is not satisfactory, back to 2 (marker modification) or back to 4 (α modification with the same marker). Some examples of segmentation results obtained on a test image are depicted in Figure 8. They illustrate, in particular, the different kinds of markers which can be considered (the wide variability of markers being authorised by the α parameter).

Application to medical image analysis

The analysis of medical data (magnetic resonance imagery (MRI), computed tomography, etc.) is required for a large spectrum of applications, including for instance computer-aided diagnosis, patient follow-up, or presurgical planning. For such purposes, segmentation is generally a step of a complex pipeline involving both image processing and expert (e.g., radiologist, surgeon) handling. In particular, the reliability of the results provided by this first segmentation step dramatically influences the quality of the whole analysis protocol.

In this section, we consider a classical issue in medical image analysis, namely the segmentation of the brain (i.e., both grey and white matter) or the whole intracranial volume (i.e., grey and white matter, plus the cerebrospinal fluid) from MRI data. This choice is justified by the following two arguments. First, segmentation algorithms applied to brain MRI can be accurately assessed by using simulated images from the commonly used BrainWeb database [START_REF] Cocosco | BrainWeb: Online interface to a 3D MRI simulated brain database[END_REF], which provides MRI images with their associated anatomical ground-truth. Such assessment are proposed in Section 6.1. Second, although the application of a segmentation method on simulated data constitutes a necessary prerequisite for its validation, its evaluation on real data remains fundamental. As the segmentation of the intracranial volume constitutes an important prerequisite, especially in foetal brain analysis from MRI data, it can then be interesting to evaluate the adequacy of the method to this task. This study is proposed in Section 6.2.

In both studies (on simulated and real images), the validation protocol will consider results obtained by the proposed method (denoted CT), and by the graph-cut method [START_REF] Boykov | Interactive graph cuts for optimal boundary & region segmentation of objects in N-D images[END_REF][START_REF] Boykov | Graph cuts and efficient N-D image segmentation[END_REF] (denoted GC). We chose to restrict the comparison with existing "high-level" methods to the only graph-cut one, since (i) it has been often proved to be the most efficient among other interactive methods (in terms of computation time and result accuracy) [START_REF] Mcguinness | A comparative evaluation of interactive segmentation algorithms[END_REF], and (ii) it presents, for the user, a modus operandi similar to the proposed component-tree method 6 . Note finally that, by opposition to the graph-cut method, the component-tree method is devoted to the case where the structures of interest to be segmented are the ones of (locally) extremal intensities. Such a case is however quite frequent in several application fields, and in particular in the ones proposed hereafter.

Simulated brain images 6.1.1. Images

BrainWeb7 is a database, providing simulated normal brain realistic MRI data for several acquisition modalities (T1, T2, etc.) and acquisition parameters. Each image is provided with an anatomical ground-truth, which associates, in particular, each voxel of the intracranial volume to a specific tissue class, as illustrated in Figure 9(a,b). For the proposed experiments, the considered BrainWeb data have been chosen with classical acquisition parameters (with respect to a standard brain MRI acquisition), namely by considering T1-weighting, with 1 × 1 × 1 mm resolution, 1 to 9% noise level, and 20 to 40% inhomogeneity field. Three (axial) slices have been chosen among the whole 3D image, at the top, middle and bottom of the brain, respectively. For each slice, six versions with different noise ratios and inhomogeneity fields have been considered. They are denoted S n i (where n and i corresponds to the noise and the intensity inhomogeneity levels, in %). These six versions (S 1 20 , S 5 20 , S 9 20 , S 1 40 , S 5 40 , and S 9 40 ) are depicted in Figure 10, for the middle slice.

Segmentation protocol

The two considered segmentation methods have been applied as follows. For GC, the following two steps have been performed as many times as necessary: (i) manual drawing of both object and background markers, (ii) graph-cut processing 8 . For CT, the following two steps have been performed as many times as necessary: (i) manual drawing of object markers, (ii) node selection by tuning of α.

Computation time vs. quality

Experiments have been carried out in order to study the link between the quality of the segmentation results and the time required to obtain them.

Two measures have been used to evaluate the quality of the result: 10, with CT (a-f) and GC (g-l) after 120 seconds (zoomed images). In white: true positives. In red: false positives. In green: false negatives.

• the κ index defined by κ = 2.TP 2.TP + FP + FN where TP, FP and FN are respectively the amounts of true positives, false positives and false negatives with respect to the BrainWeb ground-truth image;

• the mean point-to-set distance D between the borders ∂S and ∂G of the segmentation result and the ground-truth, defined by

D = 1 |∂S | + |∂G| x∈∂S d(x, ∂G) + x∈∂G d(x, ∂S )
where d is a standard point-to-point distance (in our case, the Euclidean distance). This distance D is expressed in pixels in the sequel.

The evolution of the κ index and the mean point-to-set distance, with respect to time, obtained for each one of the six (n, i) configurations (by gathering the results of the three users on the three slices) are depicted in Figure 12. Examples of segmentation results for the slice of Figure 10, obtained at the end of the process (120 seconds) are depicted in Figure 11 which emphasises in particular the false positives and negatives with respect to the BrainWeb ground-truth image.

Real foetal brain images 6.2.1. Applicative context

Most of knowledge concerning brain maturation is based on post mortem studies which do not allow joint analysis of anatomical structure development and cognitive development. The non-invasive nature of MRI provides unique opportunities for in vivo investigation of the developing human brain. In the case of foetuses, MRI is a valuable complement to prenatal sonography to confirm and characterise suspected brain abnormalities.

Image interpretation is generally performed based on foetal brain atlas book and neuro-paediatricians have to make the correspondence mentally between 3D MRI data and 2D printed histological images which is tedious and error prone.

The development of ultrafast 2D acquisition sequences has led to significant improvements in the clinical utility of foetal MRI [START_REF] Glenn | Magnetic resonance imaging of the fetal brain and spine: An increasingly important tool in prenatal diagnosis, part 1[END_REF]. However, the slice acquisition time is still very critical and has to be as short as possible to reduce the impact of foetal motion on the exam, since foetal MRI is often performed without sedation. As a result, sets of thick 2D slices are generally acquired in clinical studies and interpretation remains limited by visual inspection.

In the context of foetal MRI study, removal of non-brain tissues in MR images (also known as skull stripping [START_REF] Smith | Fast robust automated brain extraction[END_REF][START_REF] Dogdas | Segmentation of skull and scalp in 3-D human MRI using mathematical morphology[END_REF][START_REF] Sadananthan | Skull stripping using graph cuts[END_REF]) is an important step in enabling accurate measurement of brain structures. While this is a crucial step for morphometry studies, it remains an open issue, especially for foetal MRI where the region of interest is surrounded by many other structures.

Images and ground-truth

The considered images are foetal MR scans: T2 weighted HASTE sequence (TE/TR = 147/3190 ms) on a 1.5 T Siemens Avanto MRI Scanner (SIEMENS, Erlangen, Germany), resolution : 0.74 × 0.74 × 3.45 mm. An example of foetal brain MRI 9 is provided in Figure 13 (left column).

By opposition to the validations performed on simulated data in the previous subsection, there is -by definitionno ground-truth directly available here. The considered ground-truth is then the one provided by manual segmentation carried out by medical experts.

These six versions (S 1 20 , S 5 20 , S 9 20 , S 1 40 , S 5 40 , and S 9 40 ) are depicted in Figure 10, for the middle slice.

Segmentation protocol

The CT and GC methods have been applied as in Section 6.1, still on 2D slices, while (by opposition to the above study) the whole intracranial volume has been processed for each considered image. Although foetal brain MR data are actually 3D ones, this 2D slice-by-slice approach is actually justified by the following two facts: (i) the size of foetal brains (approximately 100 × 80 × 70mm for the considered data), and the resolution of the data (approximately 4mm interslice distance) generate only a small number of slices in the 3D volume (approximately, 15 slices), and (ii) the possible movements of the foetus during the acquisition process may result in spatial inaccuracies between successive slices (e.g., translations, rotations), making the spatial continuity assumption (verified for adults brain images and justifying 3D segmentation approaches) irrelevant here. Moreover, note that, by opposition to Section 6.1, the considered results have been the ones consisting of the areas bounded by the external curve generated by the segmentation results of CT and GC (indeed, for skull stripping, the relevant information is the boundary of the intracranial volume). In green: false negatives.

Computation time vs. quality

The same experiment as in Subsection 6.1.3 has been carried out in order to study the link between the quality of the segmentation results and the time required to obtain them. For each one of the 17 slices of the 3D image (partially visualised in Figure13 (left column)), several segmentations have been performed, by 3 different users, with both CT and GC.

The evolution of the κ index and the mean point-to-set distance, with respect to time (obtained by gathering the results of the three users on the 17 slices) are depicted in Figure 15.

Examples of segmentation results, obtained at the end of the process (60 seconds) are depicted in Figure 11 which emphasises in particular the false positives and negatives with respect to the BrainWeb ground-truth image.

Discussion

From the results of these experiments, performed on both synthetic and real images, several remarks can be made. For simulated and in vivo MR data, one may notice that the final results (obtained at 120 seconds for BrainWeb, and 60 seconds for foetuses) are generally very similar (see Figures 11 and14), despite intrinsically different modus operandi (GC tries to fit at best the boundary of the object on highest gradient values of the image, thus following a "1D approach", while CT tries to fit at best the object markers in the image, thus following a "2D approach"). From a qualitative point of view, the (intermediate and final) results are nearly always better with CT than with GC (with an increase in quality for the considered criteria κ and D which is small but however proportionnaly significant with respect to the small gap between the obtained and optimal values). Note in particular that BrainWeb experiments tend to show that the quality improvement between CT and GC becomes higher when the noise ratio increases.

One may notice that CT is robust to noise (at least up to 9% in the current experiments), and to intensity inhomogeneity (at least up to 40% in the current experiments), while it does not integrate any regularisation scheme in order to correct such image artifacts. For the robustness of CT to noise, this can be explained by three facts. First, noise cannot generate false positive results out of the markers, since the process implies that a binary connected component must, at least, intersect (and thus, for noise, "be included in") the marker, in order to belong to the segmentation result. Second, noise of value higher (resp. lower) than the structures of interest of high (resp. low) values, included in the markers, generally generate binary connected components which are included in relevant connected components obtained by thresholding at a lower (resp. higher) value. Then, except in cases where the marker is a quite large superset of the searched structure (see Figure 8(c,f) for an example), CT is not altered by such noise. Third, noise of value lower (resp. higher) than the structures of interest of high (resp. low) values, included in the markers, may possibly generate "holes" in relevant connected components obtained by thresholding at a high (resp. low) value. However, in order to generate such false negatives, it is necessary for such noise to have a relative value difference larger than the gap between the value of the structure of interest and the value of its neighbouring background, which is possible, but statistically unfrequent (see the small white points in Figure 8(d,e) for an example). Moreover, the robustness of CT to intensity inhomogeneity can also be justified by the fact that methods based on connected filtering become sensitive to such effects only when the intensity of the structures of interest and the intensity of their direct neighbouring background have a nonempty intersection, which is the case only for images where the contrast is quite low and/or where the intensity inhomogeneity becomes huge (which is generally not the case, even in medical imaging).

From a time cost point of view, CT and GC both converge rapidly and in comparable times (asymptotic results reached at 60s, with a low improvements -and sometimes a quality decrease-past this time). For very low values (here 30s), the results of CT are more satisfactory (better mean value), and more homogeneous between users (lower standard deviation) than those of GC. It may however be noticed that for larger 2D images, and a fortiori for 3D images, the computational cost of CT may become lower than the one of GC. Indeed, GC relies on classic techniques of maximal flow/minimal cut computation [START_REF] Ford | Flows in networks[END_REF] (improved by optimised versions [START_REF] Boykov | An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision[END_REF]) which lead to obtain a result in (low order) polynomial time [START_REF] Boykov | Graph cuts and efficient N-D image segmentation[END_REF] with respect to the size of the image. By comparison, as stated in Property 20, the proposed CT method can be run in linear time with respect to the size of the image (since the number of nodes in a component-tree is generally lower than the size of the image). In such conditions, the relevance to use a CT segmentation method increases when the size of the image becomes high.

Finally, since:

(i) CT presents computation times similar to GC for 2D images, and has a lower algorithmic complexity which may lead to better computation times for larger images; (ii) it only requires to determine one family of markers ("objects") vs. two families of markers ("objects" and "background") for GC, which may in particular lead to involve CT in the developement of example-based segmentation strategies (for instance for the segmentation of 3D images); (iii) it is parameter free (except α which has to be tuned during the segmentation process, and is thus not of same nature than the five predetermined GC parameters), by opposition to GC;

it can be concluded that CT is a relevant segmentation tool for images where the structures of interest correspond to photometric local maxima, even in cases of noise and intensity inhomogeneity. In this context, it presents an ergonomic alternative to the state-of-the-art GC.

Conclusion

In this article, an original methodological scheme, based on component-trees, has been proposed for segmentation purpose. By opposition to the other existing approaches based on component-trees, it does not rely on the use of knowledge modelled by attributes stored at each nodes of the tree (which enables to decide which ones have to be preserved to generate the segmentation result), but on a user-defined raw segmentation from which the most relevant nodes are extracted to obtained a refined result.

From a theoretical point of view, it has been proved that, in such a strategy, these relevant nodes could be discriminated in linear time (with respect to the size of the component-tree). Based on this result, efficient algorithms have been proposed, finally leading to an interactive segmentation method. This method has been assessed in the experimental context of both adult and foetal brain analysis from MRI slices. In the validity area of component-trees, namely in cases where structures of interest present locally maximal intensity values, these experiments have emphasised the robustness of the method in terms of segmentation accuracy, its fastness and its ergonomy, in particular by comparison to the state-of-the-art graph-cuts algorithm.

The method is currently designed to perform segmentation of nD images based on an initial nD raw segmentation (with any n ≥ 1). It is then particularly well-fitted for processing 2D data (the raw segmentation of which is quite easy). In the context of 3D image segmentation, the proposed methodological scheme may naturally be involved for the design of example-based segmentation, where a 3D segmentation example (e.g., registered atlas, raw segmentation obtained or another method, etc.) may replace the manual segmentation provided in a manual fashion in the 2D case. Consequently, further works will now consist of providing such 3D extensions of this method.

From a more theoretical point of view, research efforts will also be devoted to study the impact of using nonstandard connectivity (such as second-generation connectivities [START_REF] Serra | Connectivity on complete lattices[END_REF], and in particular mask-based ones [START_REF] Ouzounis | Mask-based second-generation connectivity and attribute filters[END_REF]) on the behaviour of the proposed method. Moreover, an extension of the proposed methodology to the case of the level line trees [START_REF] Monasse | Scale-space from a level lines tree[END_REF], which provide an auto-dual representation of the image structure into level-sets, and is then better suited for segmentation applications involving structures of interest which do not present locally extremal values in the considered images, may also be considered.

Proof of

Proof of Property 20

The proof is similar to the proof of Property 15. The only difference lies in the fact that the set of conditions to be tested (α.n(N) ≺ (1α).p * (N) + N ′ ∈ch(N) c α (N ′ )) requires at most |K| comparison operations (≺) and 4.|K| arithmetic operations (., +, -), while the computation of all the terms c α (.) involves (at most) the value c α (N ′ ) only once for any N ′ ∈ K, leading to less than |K| additions in the set of all the terms. Such supplementary operations then do not increase the algorithmic complexity O(|K|) of the computation of F α (E) by comparison to F σ (E). Hence the result holds.

Proof of Property 22

Let N 1 ∈ F α 1 and N 2 ∈ F α 2 . By definition, N 1 ∈ C[G α 1 ] and N 2 ∈ C[G α 2 ] are connected components of G α 1 and G α 2 , respectively, which verify either (N 1 ⊆ N 2 ) ∨ (N 2 ⊆ N 1 ) or (N 1 ∩ N 2 = ∅) (see Property 8). Let us suppose that G α 2 G α 1 . Then, there exists a node N ∈ K such that N ∈ F α 2 while ∀N ′ ∈ F α 1 , N N ′ . Let K ′ ⊆ F α 1 be the set of nodes forming the part of G α 1 included in N, i.e., such that N ′ ∈K ′ N ′ = N ∩ G α 1 (note that we may possibly have K ′ = ∅). Let G ′α 2 be the set defined by G ′α 2 = (G α 2 \ N) ∪ (N ∩ G α 1 ), i.e., the set obtained by substituting the nodes of K ′ to the node N in G α 2 . Let t = |N ∩ G|, f = |N \ G|, t ′ = |(N ∩ G α 1 ) ∩ G| and f ′ = |(N ∩ G α 1 ) \ G|, with, obviously, f ′ < f and t ′ < t. Then, we have

d α 2 (G α 2 , G) = d α 2 (G α 2 \ N, G) + α 2 . f -(1 -α 2 ).t d α 2 (G ′α 2 , G) = d α 2 (G α 2 \ N, G) + α 2 . f ′ -(1 -α 2 ).t ′
Moreover, from the very definition of G α 2 , we have

d α 2 (G α 2 , G) ≤ d α 2 (G ′α 2 , G)
and then, it comes

α 2 .( f -f ′ ) ≤ (1 -α 2 ).(t -t ′ )
Now, let G ′α 1 be the set defined by G ′α 1 = G α 1 ∪ N, i.e., the set obtained by substituting the node N to the nodes of K ′ in G α 1 . We have

d α 1 (G α 1 , G) = d α 1 (G α 1 \ N, G) + α 1 . f ′ -(1 -α 1 ).t ′ d α 1 (G ′α 1 , G) = d α 1 (G α 1 \ N, G) + α 1 . f -(1 -α 1 ).t
Moreover, from the very definition of G α 1 , we have

d α 1 (G α 1 , G) ≤ d α 1 (G ′α 1 , G)
and then, it comes (1α 1 ).(t

-t ′ ) ≤ α 1 .( f -f ′ )
But in such conditions, we have

α 2 .( f -f ′ ) ≤ (1 -α 2 ).(t -t ′ ) ≤ (1 -α 1 ).(t -t ′ ) ≤ α 1 .( f -f ′ )
which straightforwardly implies that ff ′ = tt ′ = 0, a contradiction. Consequently, we have G α 1 ⊆ G α 2 .

Figure 1 :Figure 2 :Figure 3 :

 123 Figure 1: (a) A grey-level image. (b) A segmentation of (a), assumed to be the expected one.

Figure 4 :Figure 5 :

 45 Figure 4: (a) A grey-level image I : [[0, 9]] 2 → [[0, 4]] (from 0, in black, to 4, in white). (b-f) Threshold images X v (I) (white points) for v varying from 0 (b) to 4 (f).

Figure 6 :Figure 7 :

 67 Figure 6: (a) A grey-level image. (b) The component-tree of T = (K, L, R) (a). (c) A set of nodes K ′ ⊆ K selected from the component-tree T (in grey).

Algorithm 1 -Algorithm 3 -Algorithm 1 -

 131 weight parameters (increasing values with respect to k) ≺ ∈ {<, ≤} (order involved in the cost minimisation formula)Output G ⋆ ⊆ E (final segmentation of I) Segmentation results computation for all i ∈ [[1, k]] do Compute G α i by applying Alg. 1 end for 2 -Segmentation choice Choose G ⋆ ∈ {G α i } ki=1 Interactive segmentation methods (choose either Step 2-a: "Pruning strategy" or Step 2-b: "Splitting strategy") Input I : E → V (image to be segmented) R ⊆ E (rough segmentation of I) {α i } k i=1 (with k ≥ 2) weight parameters (increasing values with respect to k) ≺ ∈ {<, ≤} (order involved in the cost minimisation formula) Output G ⋆ ⊆ E (final segmentation of I) Component-tree computation See Step 1 of Alg. 1 2-a -Segmentation results computation ("Pruning strategy") Compute F α k and S α k from T by applying Steps 2 and 3 of Alg. 1 for i from k -1 to 1 do

Figure 8 :

 8 Figure 8: (a,d), (b,e), (c,f) Examples of markers (in red) and associated segmentation for a given α (in blue). (Image is from the Berkeley Segmentation Dataset [45].)

Figure 9 :

 9 Figure 9: (a) A BrainWeb image (axial slice), and (b) its associated ground-truth (from light-grey to dark grey: white matter, grey-matter, cerebrospinal fluid, extracranial volume).

Figure 10 :Figure 11 :

 1011 Figure 10: BrainWeb images S n i considered for the proposed validations (see text). The ground-truth proposed in Figure 9(b) is the one corresponding to this slice.

40 Figure 12 :

 4012 Figure 12: Quality of the segmentation results on BrainWeb, depending on the time required to compute these segmentations, for CT (red full line) and GC (green dashed line). Each dot (resp. vertical line) is the mean value (resp. the mean standard deviation) of the results obtained by the different users. Left column: κ index. Right column: D.

Figure 13 :Figure 14 :

 1314 Figure 13: (a-d) Foetus brain images (subset of axial slices sampled in the whole image). (e-h) Zoom on the cerebral part of (a-d).

Figure 15 :

 15 Figure 15: Quality of the segmentation results on foetus images, depending on the time required to compute these segmentations, for CT (red full line) and GC (green dashed line). Each dot (resp. vertical line) is the mean value (resp. the mean standard deviation) of the results obtained by the different users. (a) κ index. (b) D.

  Property 19 Let us suppose that ch(E) = ∅. Then we have Q = {∅, E}, d α (∅, G) = (1α).p(E, G) and d α (E, G) = α.n(E, G). If we have α.n(E, G) ≺ (1α).p * (E, G) + N∈ch(E) c α (N) =0 then it comes F α (E) = {E}, c α (E) = α.n(E) and thus we haved α (G α , G) = d α (E, G) = c α (E) = min Q∈Q {d α (Q, G)} If we have α.n(E, G) ⊀ (1α).p(E, G) then it comes F α (E) = ∅, c α (E) = (1α).p(E, G) = (1α).p * (E, G) and thus we haved α (G α , G) = d α (∅, G) = c α (E) = min Q∈Q {d α (Q, G)}Consequently, the property is true whenever ch(E) = ∅.Let us now suppose that ch(E) ∅ and that the property holds for any N ∈ ch(E) (with respect to I |N , T N and G ∩ N, instead of I, T and G, see Property 5). Note thatmin Q∈Q {d α (Q, G)} = min{d α (E, G), min Q∈Q\{E} {d α (Q, G)}} while d α (E, G) = α.|E \ G| = α.n(E)and minQ∈Q\{E} {d α (Q, G)} = min Q∈Q\{E} α.|Q \ G| + (1α).|G \ Q| Note also that {Q ∩ N} N∈ch(E) is a partition of Q whenever Q E while {G \ N∈ch(E) N} ∪ {G ∩ N} N∈ch(E)is a partition of G (by omitting the possibly empty subsets). If Q E, we haved α (Q, G) = α.|Q \ G| + (1α).|G \ Q| with Q \ G = N∈ch(E) (Q ∩ N) \ G G \ Q = ((G \ N∈ch(E) N) ∪ N∈ch(E) (G ∩ N)) \ Q Then, we have |Q \ G| = N∈ch(E) |(Q ∩ N) \ G| |G \ Q| = |(G \ N∈ch(E) N) \ Q| + N∈ch(E) |(G ∩ N) \ Q| and thus α.|Q \ G| + (1α).|G \ Q| ) α.|(Q ∩ N) \ G| + N∈ch(E) (1α).|(G ∩ N) \ Q| +(1α).|(G \ N∈ch(E) N) \ Q| =                      N∈ch(E) α.|(Q ∩ N) \ (G ∩ N)| + N∈ch(E) (1α).|(G ∩ N) \ (Q ∩ N)| +(1α). |G \ N∈ch(E) N| =p * (E)From the above partition properties, it then comes thatmin Q∈Q\{E} {d α (Q, G)} = min Q∈Q\{E} {α.|Q \ G| + (1α).|G \ Q|} = min Q∈Q\{E}          N∈ch(E) α.|(Q ∩ N) \ (G ∩ N)| + N∈ch(E) (1α).|(G ∩ N) \ (Q ∩ N)| +(1α).p * (E)          = (1α).p * (E) + N∈ch(E) d α (Q ∩ N, G ∩ N) = (1α).p * (E) + N∈ch(E) c α (N)by induction hypothesis. Consequently, we have min Q∈Q {d α (Q, G)} = min{α.n(E), (1α).p * (E) + N∈ch(E) c α (N)} and the result follows by induction from Definition 16.

Note that the distinction between filtering and segmentation based on component-trees is generally not clearly defined, since segmentation is performed in a filtering fashion (see Section 4.1 for more details).

The notation arg min, used here for the sake of clarity, is potentially inaccurate since several sets of nodes P may minimise a given distance d.

The function d α is actually not a distance sinced α (X, Y) = d α (Y, X) if and only if α = 1/2, d α (X, Y) = 0 ⇔ X = 0 ifand only if α ∈ ]0, 1[, and d α does not satisfy, in general, the triangle inequality.

Such a tool can be freely downloaded from the following url: http://webloria.loria.fr/˜naegelbe/index.php/software

Another efficient algorithm is Najman's one[START_REF] Najman | Building the component tree in quasi-linear time[END_REF], which is based on Tarjan's union-find algorithm. This latter algorithm is particularly well suited for images having a large number of different values, but in our case it was slower than Salembier's algorithm on our validation images.

Note, however, that in the graph-cut method, the user has to mark two kinds of areas assumed to be included in the object and in the background, respectively, while in the component-tree method, the users has only to mark (and actually to roughly segment) the object.

http://www.bic.mni.mcgill.ca/brainweb

The graph-cuts software considered here is the one proposed in[START_REF] Mcguinness | A comparative evaluation of interactive segmentation algorithms[END_REF] which requires to set five parameters. The values for these parameters, determined by preliminary tests on the considered images, have been: no smoothing, α = 1, σ = 1, λ = 0, histogram quantisation = 1.

Note that in Section 6.1 (see Figures9 and

[START_REF] Passat | An extension of component-trees to partial orders[END_REF], which deals with adult brains, the white matter, grey-matter and cerebrospinal fluid appear in light grey, dark grey and black, respectively, while in the current case which corresponds to foetus brains, these tissues appear in light grey, dark grey and white, respectively.

Acknowledgements

The research leading to these results has received funding from the European Research Council under the European Community's Seventh Framework Programme (FP7/2007-2013 Grant Agreement no. 207667), and from the French Agence Nationale de la Recherche (Grant Agreement ANR-2010-BLAN-0205). This work is also funded by NIH Grant R01 NS055064 and a CNRS grant for collaboration between LSIIT and BICG.

A. Appendix : Proofs

Proof of Property 11 If G = ∅, by setting G + = ∅ ∈ Q, we are done. Let us now suppose that G ∅. For any x ∈ G, we set N x = min ⊆ K x .

Let G + = x∈G N x . Then we have

and thus

Let us suppose that there exists x ∈ Q ′ \ G -. In particular, we have x ∈ G. There exists

By induction from the definition of F + (E) and F -(E), we easily deduce that

In particular, it follows that

Let y ∈ G such that y ∈ N and y N ′ ∈ch(N) N ′ (such a point y exists as p * (N, G) 0). Then, N = min ⊆ K y , and since y ∈ G + , we must have N ⊆ G + . Consequently, we have N∈F + (E) N ⊆ G + , and then andin particular, n(N, G) 0. But then, there exists y ∈ N such that y G, and thus, G - G: contradiction. Consequently, we have G -⊆ N∈F -(E) N, and then

Proof of Property 15

From the definition of F σ (E), it is easily proved that each node is processed at most once. For each one of these O(|K|) processed nodes, one equality (related to p * (N, G) or n(N, G), which are assumed to be precomputed, see Remark 3) is tested, and the status of the node ("in" or "out of" the result F σ (E)) is possibly modified. These two operations have a constant algorithmic complexity O(1). The whole process then presents a linear complexity O(|K|). The generation of G σ from F σ (E) can be performed by modifying, for each node N of K and for each point x of N (these points being stored in E N for each node N, see Remark 3) the status of x to indicate that it belongs to G σ . This process then presents an algorithmic complexity O(|E|). Hence the result holds.