Wonder A L Alves
email: wonder@uni9.pro.br

Ronaldo F Hashimoto
email: ronaldo@ime.usp.br

Beatriz Marcotegui
email: beatriz.marcotegui@mines-paristech.fr

Ultimate levelings

Keywords: residual morphological operator, ultimate attribute openings, ultimate grain filters, levelings, component trees, tree of shapes

This work presents a new class of residual operators called ultimate levelings which are powerful image operators based on numerical residues. Within a multi-scale framework, these operators analyze a given image under a series of levelings. Thus, contrasted objects can be detected if a relevant residue is generated when they are filtered out by one of these levelings. Our approach consists of, firstly, (i) representing the input image as a morphological tree; then, (ii) showing that a certain operation on this tree results in a leveling operator; and finally (iii) demonstrating that a sequential application of this operation on the tree is able to produce a family of levelings that satisfies scalespace properties. Besides, other contributions of this paper include: (i) the statement of properties of ultimate levelings, (ii) the presentation of an efficient algorithm for their computation, (iii) the provision of strategies for choosing families of primitives, (iv) the presentation of strategies for filtering undesirable residues, and (v) the provision of some illustrative examples of application of ultimate levelings. Furthermore, ultimate levelings are computationally efficient and their performance evaluations are comparable to the state of art methods for filtering and image segmentation.

Introduction

An operator in Mathematical Morphology (MM) can be seen as a mapping between complete lattices [START_REF] Serra | Image Analysis and Mathematical Morphology[END_REF]. In particular, mappings on the set of all gray level images F(D) defined on domain D ⊂ Z 2 and co-domain K = {0, 1, ..., K} are of special interest in MM, i.e., ψ : F(D) → F(D). Furthermore, when ψ satisfies the properties of being increasing (∀f, g ∈ F(D), f ≤ g ⇐⇒ ψ(f ) ≤ ψ(g)) and idempotent (∀f ∈ F(D), ψ(f ) = ψ(ψ(f ))), it is called morphological filter [START_REF] Serra | Image Analysis and Mathematical Morphology[END_REF]. The first condition preserves the lattice relation order, while the second condition responds to the fact that increasing operations are not invertible. By using these properties, information content reductions are expected after applying morphological filters [START_REF] Serra | An overview of morphological filtering[END_REF]. Relying on these characteristics, morphological filters remove selectively undesirable contents from images such as noise, background irregularities, etc.; while preserving desired contents [START_REF] Najman | Mathematical Morphology[END_REF][START_REF] Bangham | Multiscale nonlinear decomposition: the sieve decomposition theorem[END_REF][START_REF] Bangham | Scale-space from nonlinear filters[END_REF]. However, this is not always an easy task.

A complementary strategy is to effectively erase the desirable portion of an image, and then restore it through a difference with the original image. This gives rise to the idea of residual operators. Simply put, residual operators are transformations that involve combinations of morphological operators with differences (or subtractions). Morphological gradient, top-hat transforms, skeleton by maximal balls, ultimate erosion and ultimate opening are some examples of residual operators widely used in image processing applications.

In this study, we present a new large class of residual operators based on an indexed family of levelings. This class of residual operators analyzes the evolution of the residual value between two consecutive operators on a scale-space of levelings. The residual value of these operators can reveal important contrast information in images. This new class of operators includes some existing ones such as maximum difference of openings (resp., closings) by reconstruction [START_REF] Li | Residues of morphological filtering by reconstruction for texture classification[END_REF], differential morphological profiles [START_REF] Pesaresi | Image segmentation based on the derivative of the morphological profile[END_REF], ultimate attribute openings (resp., closings) [START_REF] Retornaz | Scene text localization based on the ultimate opening[END_REF], differential attribute profiles [START_REF] Dalla Mura | Morphological attribute profiles for the analysis of very high resolution images[END_REF], shape ultimate attribute openings (resp., closings) [START_REF] Hernández | Shape ultimate attribute opening[END_REF] and ultimate grain filters [START_REF] Alves | Ultimate grain filter[END_REF]. They have successfully been used as a preprocessing step in various applications such as texture features extraction [START_REF] Li | Residues of morphological filtering by reconstruction for texture classification[END_REF], segmentation of high-resolution satellite imagery [START_REF] Pesaresi | A new approach for the morphological segmentation of high-resolution satellite imagery[END_REF][START_REF] Dalla Mura | Morphological attribute profiles for the analysis of very high resolution images[END_REF], text location [START_REF] Retornaz | Scene text localization based on the ultimate opening[END_REF][START_REF] Alves | Text regions extracted from scene images by ultimate attribute opening and decision tree classification[END_REF], segmentation of building façades [START_REF] Hernández | Shape ultimate attribute opening[END_REF] and restoration of historical documents [START_REF] Meyer | Levelings and flat zone morphology[END_REF]. Given above considerations, in this paper, besides the presentation of this new class of residual operators, which we call ultimate levelings, we also show its properties, fast algorithms for its computation and possible applications for residual information extraction in image processing applications.

The remainder of this paper is structured as follows. Section 2 briefly recall some definitions and properties about scale-space representations based on levelings and residual operators. In Section 3, we provide the main contributions of this paper by (i) introducing the ultimate leveling as a class of residual operators, (ii) stating some of its properties and (iii) presenting an efficient algorithm for its computation. Section 4 provides some strategies for choosing a family of primitives. In Section 5, we present some strategies for filtering undesirable residues and, Section 6 provides some illustrative examples of application of ultimate levelings. Finally, Section 7 concludes this work and presents some future research directions.

Theoretical background

In many image processing problems, objects of interest may be present at different scales. For such situations, multi-scale approaches have been developed over the last few decades, where a sequence of coarser and coarser decompositions of the same image are derived. In this sense, F. Meyer and P. Maragos [START_REF] Meyer | Nonlinear scale-space representation with morphological levelings[END_REF] proposed a nonlinear scale-space (sequence of images) decomposition obtained from a sequence of operators of a general class of morphological filters called levelings giving rise to morphological scale-space based on levelings. Later, W. Alves et al. [START_REF] Alves | Scale-space representation based on levelings through hierarchies of level sets[END_REF] proved that there exists an efficient representation of morphological scale-space based on levelings through hierarchies of level sets.

Thus, for the sake of understanding, Sections 2.1 and 2.2 recall some definitions and properties of hierarchies of level sets and morphological scale-space based on levelings, respectively. Then, we present an efficient representation of morphological scale-spaces based on levelings through hierarchies of level sets. And, Section 2.3 provides a link between the state of art in residual operators and the main result of this paper, given in Section 3.

Hierarchies of level sets: component tree and tree of shapes

Image representations through trees have been proposed in recent years to carry out tasks of image processing and analysis such as filtering, segmentation, pattern recognition, contrast extraction, registration, compression and others. In this scenario, as illustrated in Fig. 1, the first step consists of constructing a representation of the input image by means of a tree, then the task of image processing or analysis is performed through modifications or information extraction in the tree itself, and finally an image is reconstructed from the modified tree. In order to build the trees considered in this paper, we need the following definitions. For any λ ∈ K = {0, 1, ..., K}, we define

X λ ↓ (f ) = {p ∈ D : f (p) < λ} and X ↑ λ (f ) = {p ∈ D : f (p)
≥ λ} as the lower and upper level sets at value λ from an image f ∈ F(D), respectively. These level sets are nested, i.e.,

X 1 ↓ (f ) ⊆ X 2 ↓ (f ) ⊆ ... ⊆ X K ↓ (f ) and X ↑ K (f ) ⊆ X ↑ K-1 (f ) ⊆ ... ⊆ X ↑ 0 (f ).
It is possible to show that the image f can be reconstructed using either the family of lower or upper sets, i.e., ∀p ∈ D,

f (p) = sup{λ : p ∈ X ↑ λ (f )} = inf{λ -1 : p ∈ X λ ↓ (f )}. (1)
Examples of lower and upper level sets are presented in Fig. 2. Observe that, given a λ ∈ K, the level set X λ ↓ (f ) or X ↑ λ (f ) may have more than one connected component.

Image f

Lower level sets

X 1 ↓ (f ) = X 0 ↓ (f ) X 3 ↓ (f ) = X 2 ↓ (f ) X 6 ↓ (f ) = X 5 ↓ (f ) = X 4 ↓ (f ) X 7 ↓ (f )
Upper level sets From lower or upper level sets, we define two other sets L(f ) and U(f ) composed by the connected components (CCs) of the lower and upper level sets of f , i.e., L(f

X ↑ 0 (f ) X ↑ 1 (f ) = X ↑ 2 (f ) X ↑ 3 (f ) = X ↑ 4 (f ) X ↑ 5 (f ) = X ↑ 6 (f ) = X ↑ 7 (f )
) = {C ∈ CC 4 (X λ ↓ (f )) : λ ∈ K} and U(f ) = {C ∈ CC 8 (X ↑ λ (f )) : λ ∈ K},
where CC 4 (X) and CC 8 (X) are sets of 4 and 8 connected CCs of X, respectively. The ordered pairs consisting of the CCs of the lower and upper level sets and the usual inclusion set relation, i.e., (L(f ), ⊆) and (U(f ), ⊆), induce two dual trees [START_REF] Caselles | Constructing the tree of shapes of an image by fusion of the trees of connected components of upper and lower level sets[END_REF] called component trees. This leads us to Def. 2.1, and consequently to Prop. 2.2. In Fig. 3, we have examples of component trees (L(f ), ⊆) and (U(f ), ⊆) built from the lower and upper level sets presented in Fig. 2. Observe that the CCs of the lower or upper level sets extracted from an image have a hierarchical structure in these trees. Definition 2.1. Let (T , ) be an ordered set. We say that induces a tree structure in T if the following two conditions hold:

1. ∃R ∈ T such that ∀N ∈ T , N R. In that case we shall say that R is the root of the tree. 2. ∀A, B, C ∈ T , if A B and A C then either B C or C B. In that case, we shall say that B and C are nested.

Proposition 2.2 (V. Caselles et. al [START_REF] Caselles | Constructing the tree of shapes of an image by fusion of the trees of connected components of upper and lower level sets[END_REF]). Both (L(f ), ⊆) and (U(f ), ⊆) are trees.

Tree of shapes

Combining these dual trees (L(f ), ⊆) and (U(f ), ⊆) into a single tree, the so called tree of shapes can be built [START_REF] Caselles | Constructing the tree of shapes of an image by fusion of the trees of connected components of upper and lower level sets[END_REF][START_REF] Monasse | Fast computation of a contrast-invariant image representation[END_REF]. In fact, let P(D) denote the Component tree (L(f ), ⊆)

Component tree (U(f ), ⊆)
Tree of shapes (SAT (f ), ⊆) powerset of D and let sat : P(D) → P(D) be the operator of saturation [START_REF] Caselles | Constructing the tree of shapes of an image by fusion of the trees of connected components of upper and lower level sets[END_REF][START_REF] Monasse | Fast computation of a contrast-invariant image representation[END_REF][START_REF] Caselles | Geometric Description of Images as Topographic Maps[END_REF]. Thus, let SAT (f ) = {sat(C) : C ∈ L(f ) ∪ U(f )} be the family of CCs of the lower and upper level sets, respectively, with all holes filled. The elements of SAT (f ), called shapes, are nested by the inclusion relation. The pair (SAT (f ), ⊆) induces a tree (see Prop. 2.3) which is called tree of shapes [START_REF] Caselles | Constructing the tree of shapes of an image by fusion of the trees of connected components of upper and lower level sets[END_REF][START_REF] Caselles | Geometric Description of Images as Topographic Maps[END_REF]. Fig. 3, we have an example of tree of shapes (SAT (f ), ⊆) built from the lower and upper level sets presented in Fig. 2.

Proposition 2.3 (V. Caselles et. al [START_REF] Caselles | Constructing the tree of shapes of an image by fusion of the trees of connected components of upper and lower level sets[END_REF]). The ordered set (SAT (f ), ⊆) is a tree.

Compact representation of trees

Tree of shapes and also component trees of an image f will be denoted generically by T f . It is well known that a tree T f can be completely represented by a compact and non-redundant data structure [START_REF] Caselles | Geometric Description of Images as Topographic Maps[END_REF][START_REF] Géraud | A quasi-linear algorithm to compute the tree of shapes of nd images[END_REF] so that, for each pixel p ∈ D is associated to the smallest shape or CC of the tree containing p. In this structure, by the parenthood relationship, one can easily find that, all its ancestors shapes or CCs in the tree are also associated to this pixel p. Then, we denote by SC(T f , p) the smallest shape or CC containing p in the tree T f . In particular, the compact representations of component trees (L(f ), ⊆) and (U(f ), ⊆) are known as, respectively, min-tree and max-tree [START_REF] Salembier | Anti-extensive connected operators for image and sequence processing[END_REF][START_REF] Carlinet | A comparison of many max-tree computation algorithms[END_REF]. Fig. 4 shows the component trees of Fig. 3 along with the highlighted pixels in red indicating their smallest component.

Component tree (L(f ), ⊆)

Component tree (U(f ), ⊆)

Image reconstruction from trees

Note that, by definition, an image can be reconstructed from its level sets (see Eq. 1). Inspired by this equation, we can define mappings level L : L(f ) → K, level U : U(f ) → K and level SAT : SAT (f ) → K as follows:

level L (C) = inf{λ -1 : C ∈ CC 4 (X λ ↓ (f )), λ ∈ K}, level U (C) = sup{λ : C ∈ CC 8 (X ↑ λ (f )), λ ∈ K} and level SAT (C) = f (y) such that y ∈ arg sup{|SC(T f , x)| : x ∈ C},
where T f = (SAT (f ), ⊆).

(

) 2
For the sake of simpler notation, from now on, the subscript indicating the tree will be dropped from the mappings level when it is clear from context. Using the mapping level, it is possible to prove that an image f ∈ F(D) can be reconstructed from a tree T f as follows, ∀p ∈ D, f (p) = level(SC(T f , p)). In such a case, we write: f = Rec(T f ). In particular, if f is obtained by Rec((L(f ), ⊆)) (resp., Rec((U(f ), ⊆)) and Rec((SAT (f ), ⊆))), then this operation is called lower (resp., upper and shape) reconstruction.

Pruning operations

Now, the following definition (Def. 2.4) characterizes pruning operations of a tree (T , ). Definition 2.4. We say that (T , ) is obtained by a pruning operation of a tree (T , ) if and only if, T ⊆ T , for any X ∈ T , Y ∈ (T \ T ) such that X Y . In such a case, we write T = P runing (T ).

Following this definition, if T f is a tree of an image f ∈ F(D), then we say T g is the pruned version of T f if and only if T g = P runing (T f ). Also, one can easily see that T g ⊆ T f and T g is still a tree (not a forest). In addition, since the nodes of T f and T g are nested by the inclusion relation order, it can be proved that, ∀p ∈ D, SC(T f , p) ⊆ SC(T g , p) [START_REF] Alves | Scale-space representation based on levelings through hierarchies of level sets[END_REF].

At the end of this subsection, we have all the ingredients of Fig. 1, that is, given an input image f , construct a tree, followed by pruning operations that modifies the original tree, and, finally reconstructed the image from the modified tree.

Morphological scale-space based on levelings

As previously mentioned, in many applications in image processing, objects of interest in an image may belong to many scales. In this situation, several representations of scale-space have been developed in recent decades, such as the scale-space through levelings. In this sense, a scale-space based on levelings, which are specializations of connected operators, is presented in this section through a hierarchy of level sets, more specifically, through component trees and tree of shapes. For that, firstly we recall some theory on connected operators and levelings. Then, recall that reconstructions of pruned trees are levelings. Finally, recall that a tree represents a scale-space that can be constructed by successive pruning operations in the tree.

Connected operators and levelings

In a few words, a connected operator ψ : F(D) → F(D) is a transformation that enlarges the partition of space created by flat zones and consequently do not create new contours [START_REF] Salembier | Flat zones filtering, connected operators, and filters by reconstruction[END_REF]. More precisely, see Def. 2.5. Definition 2.5 (P. Salembier and J. Serra [START_REF] Salembier | Flat zones filtering, connected operators, and filters by reconstruction[END_REF]). An operator ψ : F(D) → F(D) is said to be connected, if and only if, for any f ∈ F(D) the following relation is valid for any pixel p ∈ D, i. e.,

P f (p) ⊆ P ψ(f ) (p),
where P f and P ψ(f ) are two partitions on D generated by the flat zones of f and ψ(f ), respectively. In addition, P f (p) and P ψ(f ) (p) are two regions of P f and P ψ(f ) that contains the pixel p.

This definition emphasizes the processing based on regions since the output regions are obtained by merging adjacent regions from input image partition. An equivalent definition, introduced by F. Meyer [START_REF] Meyer | From connected operators to levelings[END_REF], emphasizes the local processing of region contours, i.e., if there is a transition between two adjacent pixels (p, q) in the operator output (that is, [ψ(f )](p) = [ψ(f )](q)), then a transition also occurs between the same pixels in the input image (that is,

f (p) = f (q)).
Connected operators represent a wide class of operators [START_REF] Meyer | Nonlinear scale-space representation with morphological levelings[END_REF][START_REF] Meyer | The levelings[END_REF][START_REF] Meyer | Levelings, image simplification filters for segmentation[END_REF] extensively studied in the literature. One of these specializations, known as levelings [START_REF] Meyer | Nonlinear scale-space representation with morphological levelings[END_REF][START_REF] Meyer | From connected operators to levelings[END_REF][START_REF] Meyer | The levelings[END_REF][START_REF] Meyer | Levelings, image simplification filters for segmentation[END_REF], is a powerful filter that preserves order, does not create new structures (regional extrema and contours) and its values are enclosed by values of neighbor pixels (see Def. 2.6). Definition 2.6 (F. Meyer [START_REF] Meyer | From connected operators to levelings[END_REF][START_REF] Meyer | The levelings[END_REF]). An operator ψ : F(D) → F(D) is said to be leveling, if and only if, for any f ∈ F(D) the following relation is valid for all pairs of adjacent pixels, i.e., ∀(p, q) ∈ A,

[ψ(f )](p) > [ψ(f )](q) ⇒ f (p) ≥ [ψ(f )](p) and [ψ(f )](q) ≥ f (q).
where A is a adjacency relation1 on D.

Morphological scale-space of levelings

Note that from the definition of a class of operators C (e.g., connected operators or levelings), it is possible to build a binary relation R on F(D) such that, for any (g, f ) ∈ R if and only if there exists ψ ∈ C such that g = ψ(f ). Thus, definition of levelings can be seen as a binary relation R leveling on F(D). Similarly, we can define the relation R connected . So, we say that g is leveling of f if and only if (g, f ) ∈ R leveling . Analogously, g is connected of f if and only if (g, f ) ∈ R connected . In [START_REF] Meyer | From connected operators to levelings[END_REF], F. Meyer, shows that R leveling is reflexive and transitive; and, if we ignore the constant images, then R leveling is anti-symmetric, i.e., R leveling is an order relation. With the help of this order relation, levelings can be nested and create a scale-space decomposition of an image f ∈ F(D) in the form of a series of levelings (g 0 = f, g 1 , . . . , g n ), where g k is leveling of g k-1 and, as a consequence of transitivity, g k is also a leveling of each image g j , for j < k [START_REF] Meyer | Nonlinear scale-space representation with morphological levelings[END_REF] and forms what we call a morphological scale-space of levelings.

Morphological scale-spaces are important for image segmentation since they have the following features: (i) simplification, i.e., all contours and all regional extrema of g i+1 are present in g i ; (ii) causality, i.e., any contour of g i+1 corresponds to a stronger contour of g i at the same location; and (iii) fidelity, i.e., no new extrema at larger scales [START_REF] Bangham | Multiscale nonlinear decomposition: the sieve decomposition theorem[END_REF][START_REF] Bangham | Scale-space from nonlinear filters[END_REF][START_REF] Meyer | Levelings and flat zone morphology[END_REF][START_REF] Meyer | Nonlinear scale-space representation with morphological levelings[END_REF].

In Fig. 5, we have an example of morphological scale-space based on levelings. Observe that, the coarser is the scale, the more simplified is the image; and at larger scales there are neither new contours nor new extrema.

Reconstruction of pruned trees

In this way, W. Alves et al. [START_REF] Alves | Scale-space representation based on levelings through hierarchies of level sets[END_REF] showed that scale-spaces based on levelings can be obtained by successive sequences of prunings. More precisely, let T f be a tree (max-tree, min-tree or tree of shapes) that represents an image f ∈ F(D) and let (T 0 f , T 1 f , T 2 f , . . .) be a sequence of trees obtained by successive prunings, i.e.,

T i f = T f , if i = 0, Pruning(T i-1 f ), if i > 0. for i = 0, 1, 2, . . . (3)
Then, W. Alves et al. [START_REF] Alves | Scale-space representation based on levelings through hierarchies of level sets[END_REF] have proved that reconstructions from pruned trees are levelings. Hence, if

Rec(T n f ) is a leveling of Rec(T k f ) and Rec(T k f ) is a leveling of Rec(T j f )
, then, by transitivity, we have also that Rec(T n f ) is a leveling of Rec(T j f ), for any 0 ≤ j ≤ k ≤ n. This shows that the sequence of trees generates a family of levelings that subsequently simplifies the image f , thus constituting a morphological scale-space. This fact leads us to Theo. 2.7.

Theorem 2.7 (Alves et al. [START_REF] Alves | Scale-space representation based on levelings through hierarchies of level sets[END_REF]). Let T f be a tree (max-tree, min-tree or tree of shapes) that represents an image f . Let (T 0 f , T 1 f , . . . , T n f ) be a sequence of trees obtained by successive prunings. Then, the sequence of reconstructions

(Rec(T 0 f ), Rec(T 1 f ), . . ., Rec(T n f )
) is a morphological scale-space of levelings.

Residual operators

This subsection provides a link between the state of art in residual operators and the main result of this paper, given in Section 3. As previously mentioned, a residual operator r ψ,φ : F(D) → F(D) is defined as the difference between two operators, say ψ : F(D) → F(D) and φ :

F(D) → F(D), applied to a given image f ∈ F(D), i.e., ∀p ∈ D, [r ψ,φ (f )](p) = [ψ(f )](p) -[φ(f )](p).
Operators ψ and φ are called primitives, and if [ψ(f )](p) > [φ(f )](p), then we say r ψ,φ (p) is a positive residue; or a negative residue if [ψ(f )](p) < [φ(f )](p); otherwise, we say r ψ,φ (p) is a null residue. Residual operators have been extended to extract residues of two increasing families of primitives {ψ i : F(D) → F(D), i ∈ I } and {φ i : F(D) → F(D), i ∈ I } indexed by a set I = {0, 1, ..., I M AX } such that, for any i, j ∈ I , if i ≤ j, then ψ i ψ j and φ i φ j . Note that, in notation of the index set I , it is explicitly indicated the partial order relation between primitive operators. Thus, the i -th residual operator applied to a given image f ∈ F(D) is defined as r ψi,φi (f ) = ψ i (f ) -φ i (f ) and the extended residual operator θ : F(D) → F(D) applied to an image f is defined as the supremum of residues, i.e., θ(f ) = sup i∈I {r ψi,φi (f )}. Skeleton by maximal balls and ultimate erosion are examples of extended binary residual operators commonly used in binary image processing.

Some residual operators are defined on a single increasing family of primitives {ψ i : i ∈ I } such that ψ i ψ i+1 and residues r ψi,ψi+1 are consecutively extracted along with the primitives family. For simplicity, we denote, from this moment on, the i -th residual operator r ψi,ψi+1 by r i . Thus, in the same way as defined above, the residual operator defined from this single family is given by the supremum of consecutive residues applied for any image f ∈ F(D), that is,

θ(f ) = sup i∈I {r i (f ) : r i (f ) = ψ i (f ) -ψ i+1 (f )}. ( 4
)
In this sense, in 1997, W. Li et al. [START_REF] Li | Residues of morphological filtering by reconstruction for texture classification[END_REF] used the result of this operator, along with all the residues, when the primitives are openings (and by duality, closings) by reconstruction, to build, for each pixel p ∈ D, features (among others) for texture classification.

A few years later, in 2000, M. Pesaresi and J. A. Benediktsson [START_REF] Pesaresi | Image segmentation based on the derivative of the morphological profile[END_REF], used the same concept to define, for each pixel p ∈ D, the derivative of morphological profile applied to high resolution satellite images segmentation. The morphological profile is a large vector constructed, for each pixel p ∈ D, by concatenation of openings (and by duality, closings) by reconstruction. The derivative of morphological profile is nothing more than the large vector built from all consecutive residues. Also in [START_REF] Pesaresi | Image segmentation based on the derivative of the morphological profile[END_REF], the authors used, along with the derivative of morphological profile, the point where occurs its greatest derivative to build a large vector to characterize each pixel for image segmentation. It is worth mentioning that the studies initiated by M. Pesaresi and J. A. Benediktsson [START_REF] Pesaresi | Image segmentation based on the derivative of the morphological profile[END_REF][START_REF] Pesaresi | A new approach for the morphological segmentation of high-resolution satellite imagery[END_REF] have had high-impact contributions in the remote sensing domain [START_REF] Ghamisi | A survey on spectralspatial classification techniques based on attribute profiles[END_REF].

Afterwards, in 2007, S. Beucher [START_REF] Beucher | Numerical residues[END_REF] proposed the ultimate opening (and by duality, ultimate closing), which is a residual operator where the primitives are openings by structuring elements of increasing sizes {γ Bi : i ∈ I ≥ } (and, respectively, closings by structuring elements of decreasing sizes {ϕ Bi : i ∈ I ≤ }). Many advances inspired in morphological profile and ultimate opening have been proposed over the last few years which include, for example, the ultimate attribute opening (UAO) and by duality ultimate attribute closing (UAC) [START_REF] Retornaz | Scene text localization based on the ultimate opening[END_REF], which are residual operators where primitives are attribute openings {γ κ i : i ∈ I ≥ } and attribute closings {ϕ κ i : i ∈ I ≤ }, respectively. Similarly, in [START_REF] Dalla Mura | Morphological attribute profiles for the analysis of very high resolution images[END_REF][START_REF] Ouzounis | Differential area profiles: Decomposition properties and efficient computation[END_REF], the authors have been proposed the attribute openings (resp. closings) profiles where the greatest derivatives are equivalent to the ultimate attribute opening based on the same primitives.

From the above, we can see that residual operators are very important for image processing and analysis.

Computation of residual operators by successive prunings

Algorithms for residual operator computation have been proposed using trees [START_REF] Alves | Ultimate grain filter[END_REF][START_REF] Ouzounis | Differential area profiles: Decomposition properties and efficient computation[END_REF][START_REF] Wilkinson | Concurrent computation of differential morphological profiles on giga-pixel images[END_REF][START_REF] Fabrizio | Fast implementation of the ultimate opening[END_REF][START_REF] Wilkinson | An efficient parallel algorithm for multi-scale analysis of connected components in gigapixel images[END_REF].

If (T 0 f , T 1 f , . . . , T I M AX f
) is a sequence of trees obtained by successive prunings from a tree T f such that

ψ 0 (f ) = Rec(T 0 f ), ψ i (f ) = Rec(T i f ) and T i f = Pruning(T i-1 f
), for i ∈ I, then (ψ 0 (f ), ψ 1 (f ), . . . , ψ I M AX (f )) constitutes a morphological scale-space based on levelings. Then, the nodes of T i f , which are not in T i+1 f , can be used to calculate the residues r i (f ) between ψ i (f ) and ψ i+1 (f ). In Fig. 6, we have an example of computation of the residual operator (at the bottom right) by a sequence of successive prunings (at the top row) of the component tree (L(f ), ⊆) (at left). Note that the morphological scale-space and residues are given, respectively, at the middle and bottom rows. In this way, a consecutive residual operator can be obtained by a sequence of successive prunings of a tree which in turn defines a morphological scale-space based on specific family of levelings. In this paper, a larger collection of levelings is considered. The resulting operators are called ultimate levelings and they will be defined more formally in Section 3.

Tf = (L(f ), ⊆) T 0 f = Tf ψ0(f ) = f r0(f ) T 1 f ψ1(f ) r1(f ) T 2 f ψ2(f ) r2(f ) T 3 f ψ3(f ) r3(f ) T 4 f ψ4(f ) r4(f ) T 5 f ψ5(f ) r5(f ) T 6 f ψ6(f ) sup{ri(f )} N r(0) N r(1) N r(2) N r(3) N r(4) N r(5)

Ultimate levelings

Ultimate levelings constitute a wider class of residual operators defined from an indexed family of levelings {ψ i : i ∈ I} such that for any i, j ∈ I, i ≤ j ⇔ ψ j is leveling of ψ i . Note that this larger class of operator includes families of openings and closings by reconstruction studied by Pesaresi et al. [START_REF] Pesaresi | Image segmentation based on the derivative of the morphological profile[END_REF]. An ultimate leveling analyzes the evolution of the residual value presented in two consecutive primitives, i.e.

r + i (f ) = [ψ i (f ) -ψ i+1 (f ) ∨ 0] and r - i (f ) = [ψ i (f ) - ψ i+1 (f )∨0],
i, j ∈ I, i ≤ j ⇔ ψ j is a leveling of ψ i . That is, R + θ (f ) = sup i∈I {r + i (f ) : r + i (f ) = [ψ i (f ) -ψ i+1 (f ) ∨ 0]} (resp., R - θ (f ) = sup i∈I {r - i (f ) : r - i (f ) = [ψ i+1 (f )-ψ i (f )∨0]}). Thus, the ultimate leveling R θ is the supremum between R + θ and R - θ , i.e., R θ (f ) = R + θ (f ) ∨ R - θ (f ).

Associated information to ultimate levelings

Residual values of these operators can reveal important contrasted structures in the image. Besides residues, other associated information can be obtained such as properties of the operators that produced the residual value. For example, S. Beucher [START_REF] Beucher | Numerical residues[END_REF] introduced a function q Imax : D → I that associates to each pixel the major index that produces the maximum non-null residue, i.e.,

q + Imax (p) = max{i + 1 : [r + i (f )](p) = [R + θ (f )](p) > 0} (5)
and

q - Imax (p) = max{i + 1 : [r - i (f )](p) = [R - θ (f )](p) > 0}. ( 6
)
The functions q + Imax and q - Imax (resp., q + κmax and q - κmax ) are combined into a single function q Imax (resp., q κmax ), i.e.,

p ∈ D, q Imax (p) = q + Imax (p), if [R θ (f )](p) > [R + θ (f )](p), q - Imax (p), otherwise. (7)
Furthermore, replacing the max operator by any other rank-order operators can have some other interesting functions as, for example: q I median q Imin , q κ median and q κmin . These functions may be very useful to analyze the extracted residues as already done in some applications [START_REF] Pesaresi | Image segmentation based on the derivative of the morphological profile[END_REF][START_REF] Hernández | Shape ultimate attribute opening[END_REF][START_REF] Pesaresi | A new approach for the morphological segmentation of high-resolution satellite imagery[END_REF][START_REF] Beucher | Numerical residues[END_REF][START_REF] Alves | Extraction of numerical residues in families of levelings[END_REF]. In Fig. 7, we present the input image f (shown in Fig. 6), its ultimate leveling R θ (f ), and the associated image q Imax . Note that the colors in q Imax indicate the primitive operator index that generated the maximum residue shown in R θ (f ).

Input image f

Ultimate leveling R θ (f ) Associated image q Imax In the remainder of this section, we present some theoretical contributions of this paper, including properties of ultimate levelings and an efficient algorithm for ultimate leveling computation.

Properties of ultimate levelings

In this section, we will present two properties of ultimate levelings: structures preservation (in Subsection 3.2.1) and complementation (in Subsection 3.2.2). But, before that, it is worth mentioning that ultimate levelings are not morphological filters, i.e., they are not increasing and are also not idempotent, in spite of the i-th residue r + i (resp., r - i ) is an idempotent operator, that is,

r + i (r + i (f )) = ψ i (r + i (f )) -ψ i+1 (r + i (f )) ∨ 0 = ψ i ([ψ i (f ) -ψ i+1 (f ) ∨ 0]) -ψ i+1 ([ψ i (f ) -ψ i+1 (f ) ∨ 0]) ∨ 0 = ψ i ([ψ i (f ) -ψ i+1 (f ) ∨ 0]) -0 = ψ i (f ) -ψ i+1 (f ) ∨ 0 = r + i (f ).
We show as a contribution of this paper that ultimate levelings have very interesting properties on structures preservation (contours and regional extrema) and complementariness (see Sections 3.2.1 and 3.2.2, respectively). Moreover, positive ultimate levelings R + θ are anti-extensive, i.e. R + θ (f ) ≤ f . Furthermore, a residual decomposition (r 0 (f ), . . . , r I M AX -1 (f )) of an image f ∈ F(D) can also be used to build residual hierarchies, and also it can be used for image reconstruction, since

r + i (f ) = ψ i (f )-ψ i+1 (f )∨0 and r - i (f ) = ψ i+1 (f )-ψ i (f )∨0, we have that ψ i (f ) = ψ i+1 (f ) + r + i (f ) -r - i (f )
, and, consequently, we can reconstruct an image f from a residual decomposition as follows:

f = ψ I M AX (f ) + I M AX -1 i=0 r + i (f ) - I M AX -1 i=0 r - i (f ). (8)

Properties on structures preservation

Levelings are operators that satisfy good properties on structures preservation (contours and regional extrema). Indeed, these properties are widely desired in segmentation applications. In this section, we show that ultimate levelings inherit some of these properties.

Given an image f and a family of primitives {ψ i : i ∈ I} indexed by a set I,

if ψ i+1 (f ) is a leveling of ψ i (f ) and (p, q) ∈ A, then [ψ i (f )](p) = [ψ i (f )](q) ⇒ [ψ i+1 (f )](p) = [ψ i+1 (f )](q), which implies [0∨ψ i (f )-ψ i+1 (f )](p) = [0∨ψ i (f )- ψ i+1 (f )](q) (resp. [0 ∨ ψ i+1 (f ) -ψ i (f )](p) = [0 ∨ ψ i+1 (f ) -ψ i (f )](q)), which shows that r + i (f ) (resp. r - i (f )) is connected of ψ i (f ). Besides, if [ψ i+1 (f )](p) > [ψ i+1 (f )](q), then [ψ i (f )](p) ≥ [ψ i+1 (f )](p) > [ψ i+1 (f )](q) ≥ [ψ i (f )](q), since ψ i+1 (f ) is a leveling of ψ i (f ). Thus, we de- rive 2 statements: (i) [0 ∨ ψ i (f ) -ψ i+1 (f )](p) ≥ [0 ∨ ψ i (f ) -ψ i+1 (f )](q) (i.e., [r + i (f )](p) ≥ [r + i (f )](q)); and (ii) [ψ i (f )](p) > [ψ i (f )](q). Therefore, if [ψ i+1 (f )](p) > [ψ i+1 (f )](q),
then a transition on positive residues r + i (f ) implies a transition on ψ i (f ) with the same order. We can come to the same conclusion,

if we consider [ψ i+1 (f )](p) = [ψ i+1 (f )](q). Therefore, ∀(p, q) ∈ A, [r + i (f )](p) ≥ [r + i (f )](q) ⇒ [ψ i (f )](p) > [ψ i (f )](q)
, which shows also that r + i (f ) (resp., r - i (f )) is an arcwise connected operator (or monotone planing [START_REF] Meyer | From connected operators to levelings[END_REF]) of ψ i (f ). This leads us to Lemma 3.2.

Lemma 3.2. If (ψ 0 (f ), ψ 1 (f ), ..., ψ n (f )) is a scale-space based on levelings, then r + i (f ) = [0 ∨ ψ i (f ) -ψ i+1 (f )] (resp., r - i (f )) is an arcwise connected operator of ψ i (f ), for 0 ≤ i ≤ n -1.
On one hand, although connected operators never introduce new contours [START_REF] Bangham | Scale-space from nonlinear filters[END_REF], they may turn a regional minimum into a maximum and vice-versa. On other hand, arcwise connected operators are a specialization of connected operators which do not create regional minima or maxima [START_REF] Meyer | From connected operators to levelings[END_REF]. Since levelings are a particular kind of arcwise connected operators, they share the same property. Besides, levelings also preserve order and this characteristic allows us to state Props. 3.3 and 3.4. These propositions guarantee that ultimate levelings are also connected operators and preserve order. Note that, we can easily prove Props. 3.3 and 3.4 with the help of Lemma 3.2 and the fact that connected (resp., arcwise connected and levelings) operators are closed under composition, infimum and supremum. As positive (resp., negative) ultimate levelings are arcwise connected operators, and, therefore they will inherit the property of not creating regional maxima (resp., minima). Proposition 3.7. Positive ultimate levelings do not create new regional maxima. In other words, if R + θ (f ) (resp., R - θ (f )) has a regional maximum X ⊆ D, then f possesses a regional maximum (resp., minimum) Z ⊆ X .

Proof. Let X ⊆ D be a regional maximum of R + θ (f ) and let y = arg max{f (x) : x ∈ X } be a pixel of X with maximum value in f . Then, there is a flat-zone Z in f that contains y. Clearly, Z ⊆ X , since R + θ is a connected operator. Now, suppose, by contradiction, that Z is not a regional maximum of f . Then, there is a pixel p / ∈ Z adjacent to some pixel q ∈ Z such that f (p) > f (q) = f (y). Thanks to Prop. 3.4, we have that R + θ is an arcwise connected operator. Thus,

f (p) ≥ f (q) ⇒ [R + θ (f )](p) ≥ [R + θ (f )](q), but as q ∈ Z ⊆ X and X is a regional maximum of R + θ (f ), then [R + θ (f )](p) = [R + θ (f )](q)
. So, p ∈ X . However, this is a contradiction, since y is the pixel of X with maximum value in f , and, consequently, f (p) ≤ f (y). Therefore Z is a regional maximum of f .

Properties with respect to complementation

Two operators ψ and ϕ are dual with respect to complementation if applying ψ to an image f is equivalent to applying ϕ to the complement of f and taking the complement of the result [START_REF] Soille | Beyond self-duality in morphological image analysis[END_REF], i.e., ψ(f ) = [ϕ(f c )] c , where f c is the complement of image f and is defined, for each pixel p ∈ D, as f c (p) = K -f (p). Similarly, ψ and ϕ are complementary if applying ψ to an image f is equivalent to applying ϕ to the complement of f , i.e. ψ(f ) = ϕ(f c ). Proposition 3.8. Let (ψ 0 (f ), ψ 1 (f ), ..., ψ n (f )) and (ϕ 0 (f ), ϕ 1 (f ), ..., ϕ n (f )) be two scale-spaces based on levelings such that for any 0 ≤ i ≤ n, ψ i (f ) is dual of ϕ i (f ). Then, r + i (f ) and r - i (f ) are complementary, where

r + i (f ) = [0 ∨ ψ i (f ) - ψ i+1 (f )] and r - i (f ) = [0 ∨ ϕ i+1 (f c ) -ϕ i (f c )]).
Proof.

r + i (f ) = [0 ∨ ψ i (f ) -ψ i+1 (f )] = [0 ∨ (ϕ i (f c )) c -(ϕ i+1 (f c )) c ] = [0 ∨ (K -ϕ i (f c )) -(K -ϕ i+1 (f c ))] = [0 ∨ ϕ i+1 (f c ) -ϕ i (f c )] = r - i (f c )
Corollary 3.9. Ultimate attribute openings and closings are complementary.

An operator ψ is self-dual with respect to complementation if its dual operator with respect to the complementation is ψ itself [START_REF] Soille | Beyond self-duality in morphological image analysis[END_REF]

, i.e. ψ(f ) = [ψ(f c )] c . Similarly, ψ is self-complementary if ψ(f ) = ψ(f c ). Proposition 3.10. Let (ψ 0 (f ), ψ 1 (f ), ..., ψ n (f )) be a scale-space based on lev- elings such that ψ i (f ) is self-dual. Then, we have that r i (f ) = r + i (f ) ∨ r - i (f ) is self-complementary.
- θ (f ) is an ultimate attribute closing of f , then [R + θ (f ) ∨ R - θ (f )] is self-complementary.

Construction of ultimate levelings

Thanks to Theo. 2.7, it is known that if (T 0 f , T 1 f , . . . ,

T I M AX f
) is a sequence of trees obtained by successive prunings such that ψ 0

(f ) = Rec(T 0 f ), ψ i (f ) = Rec(T i f ) and T i f = Pruning(T i-1 f
), for i ∈ I, then (ψ 0 (f ), ψ 1 (f ), . . . , ψ I M AX (f )) constitutes a morphological scale-space based on levelings. Then, let N r(i) be the set of nodes removed from T i f to build the pruned tree

T i+1 f , i.e. N r(i) = T i f T i+1 f
. Since these trees are derived from successive prunings, we can present Prop. 3.13, which states that residues can be computed in parallel.

Proposition 3.13. If i, j ∈ I such that i = j, then N r(i) ∩ N r(j) = ∅.
Therefore, we can calculate positive (resp., negative) residues of all pixels of a given node C ∈ N r(i) by

r + T i f (C) =    [level(C) -level(parent(C)) ∨ 0], if parent(C) / ∈ N r(i), [level(C) -level(parent(C)) ∨ 0] + r + T i f (parent(C)), otherwise, (9)
and thus,

∀p ∈ D, [r + i (f )](p) = r + T i f (SC(T i f , p)), if SC(T i f , p) ∈ N r(i), 0, otherwise, (10)
and consequently, this leads us to Alg. 1 for ultimate leveling computation through a top-down approach, which is a generalization of J. Fabrizio and B. Marcotegui's algorithm [START_REF] Fabrizio | Fast implementation of the ultimate opening[END_REF]: (i) the residue of the parent node is calculated;

(ii) it is then propagated to its child nodes; (iii) every child node compares its residue with the residue of its parent node and keeps the maximum of these two values in R θ ; (iv) after this step, each child node becomes a parent node and the process is repeated.

Algorithm 1: Basic computation of the ultimate levelings.

1 BasicComputationOfUltimateLeveling(Tree T f , node C) begin

2 if ∃i ∈ I such that C ∈ N r(i) then 3 r + i [C] = level(C) -level(parent(C)) ∨ 0; 4 r - i [C] = level(parent(C)) -level(C) ∨ 0; 5 if parent(C) ∈ N r(i) then 6 r + i [C] = r + i [C] + r + i [parent(C)]; 7 r - i [C] = r - i [C] + r - i [parent(C)]; 8 R + θ [C] = R + θ [parent(C)] ∨ r + i [C]; 9 R - θ [C] = R - θ [parent(C)] ∨ r - i [C]
; // From here, compute q + and q - The input of Alg. 1 is a tree (max-tree, min-tree or tree of shapes). These trees can be built by simple algorithms based on union-find such as proposed in [START_REF] Géraud | A quasi-linear algorithm to compute the tree of shapes of nd images[END_REF][START_REF] Berger | Effective component tree computation with application to pattern recognition in astronomical imaging[END_REF] with time complexity O(|D| log(|D|)). Once the tree is built (see algorithms in [START_REF] Carlinet | A comparison of many max-tree computation algorithms[END_REF][START_REF] Géraud | A quasi-linear algorithm to compute the tree of shapes of nd images[END_REF]), function BasicComputationOfUltimateLeveling is executed from the root node. Conditions given at lines 2 and 5 depend on the chosen family of primitives and their verifications can be done in constant time. Since function BasicComputationOfUltimateLeveling visits each node of the tree exactly once and the number of nodes of the tree is at most the number of pixels in the image, BasicComputationOfUltimateLeveling is executed with time complexity O(|D|). At the end, we can reconstruct the output of Alg. 1

(i.e., ∀p ∈ D, R θ (p) = R + θ [SC(T , p)] ∨ R - θ [SC(T , p)]
) in O(|D|) time complexity. Therefore, the time complexity of the proposed algorithm is O(|D| log(|D|)).

Strategies for choosing a family of primitives

The results of ultimate leveling operators depend directly on the chosen primitives. In fact, since residues are obtained by the difference of two consecu-tive primitives and they can be computed by the difference between two consecutive pruned trees, the output of Alg. 1 depends on the set N r(i) = T i f T i+1 f (see lines 2 and 5). Thus, a family of primitives (ψ 0 (f ), ψ 1 (f ), ..., ψ I M AX (f )) can be obtained by the reconstruction from a sequence of consecutive pruned trees

(T 0 f = T f , T 1 f , ..., T I M AX f
), which in turn can be derived from the sets N r(i) by using the following formula:

T i+1 f = T i f N r(i). ( 11
)
The choice of N r(i) sets determines the pruning strategy. A logical predicate Γ : P(D) → {True, False} marks the tree branches to be pruned (see Alg. 2). These markings (and consequently, every tree T i f and its set N r(i)) can be obtained, for example, through a postorder traversal of T f . The node visiting order does not alter the ultimate leveling result thanks to Prop. 3.13. As an illustration, Fig. 6 shows an example of marking the tree (by sorting the height of CCs) in which we can deduce the sequence of nodes N r(i) and, consequently, the sequence of pruned trees.

Algorithm 2: Basic computation of choose a primitives family.

1 chooseThePrimitivesFamily(tree T f ) begin 2 i = 0 3 T 0 f = T f 4 foreach node C of a postorder traversal of T f do 5 if Γ(C) is true then 6 N r(i) is the subtree of T i f rooted in C 7 T i+1 f = T i f N r(i) 8 i = i + 1
Observe that the set with the largest number of primitives that can be derived from a tree T f is given by the criterion: ∀C ∈ T f , Γ(C) = C is not root . It can be a good idea to use all these primitives if the purpose involves shape recognition. However, that does not seem to be a good idea if the purpose is to identify contrasted regions from a natural image, since the residue generated between two consecutive operators can be very close to zero. This may occur because the objects of an image decompose very slowly. Thus, in the following subsections, we present some strategies to build primitive families that can generate more significant residues for the ultimate levelings.

Attribute based primitives

As stated in Section 2, tree nodes correspond to image regions defined by level sets. Characteristics of these regions such as area, volume, height, width or circularity can be computed and assigned to tree nodes as node attributes. Several attributes can be combined in a vector, as proposed in [START_REF] Urbach | Vector-attribute filters[END_REF], but in this paper only scalar attributes are considered. Thus, formally, a node attribute is a function κ : P(D) → R representing a region feature. Some attributes are increasing, i.e., A, B ∈ P(D), A ⊆ B ⇒ κ(A) ≤ κ(B). If attributes are increasing, their values also follow a well-defined ordering in the tree due to the hierarchy of the level sets. Thanks to this property, attribute opening (resp., closing and grain filter) is performed by simply pruning the tree nodes whose attribute value κ is lower than a given threshold t followed by reconstruction of the pruned tree. For non increasing attributes several strategies (min, max, direct or Viterbi optimization) are proposed in [START_REF] Salembier | Anti-extensive connected operators for image and sequence processing[END_REF].

Thus, families of attribute openings, attribute closings and grain filters can be determined from a family of increasing thresholds (t 1 , t 2 , ..., t I M AX ) for an increasing attribute κ. For example, the family of thresholds can be derived from a tree T f , i.e.,

t i ∈ T κ = {κ(C) : C ∈ T f } such that 1 ≤ i ≤ |T κ | = I M AX . Thus, T 0 f = T f , T i+1 f = P runing(T i f ) = {C ∈ T i f : κ(C) ≤ t i+1 } and ψ i = Rec(T i f ), for 0 ≤ i < I M AX . Therefore, a node C ∈ N r(i) = T i f T i+1 f satisfies the conditions of criterion Γ, if and only if, κ(C) ≤ t i and κ(parent(C)) > t i or equivalently κ(C) = κ(parent(C)) So, ∀N ∈ T f , Γ(N ) = κ(N ) = κ(parent(N )) .
Residual values of negative (resp. positive) ultimate levelings R - θ (resp. R + θ ) are the biggest difference between two consecutive operators from a given primitive family. In this sense, Fig. 8 shows an example of an application of R - θ in a given image f ∈ F(D) where we analyze the evolution of residual values for a given pixel using two primitive families: area closing and height closing. Primitive families based on area attribute (or similarly, volume) tend to simplify images very slowly leading to very small residues. We can get bigger residues if we choose primitive families that tend to simplify the image more quickly, as evidenced in Fig. 8: family of height closings simplifies more quickly than family of area closings. In both cases, we see that the residues generated for the selected pixel are the largest transition between two consecutive primitives, which are the following: 2 for area closings and 59 for height closings, but, in both cases, they are smaller than the real contrast (that is, approximately 117) of the object that contains the selected pixel.

Based on these considerations, B. Marcotegui et al. [START_REF] Marcotegui | Ultimate opening and gradual transitions[END_REF], proposed a solution for primitive selection called gradual transition and, in this paper, we propose a second solution, based on extinction values [START_REF] Grimaud | New measure of contrast: the dynamics[END_REF][START_REF] Vachier | Extinction value: a new measurement of persistence[END_REF].

• Primitives based on gradual transition

As seen previously, families of attribute openings (resp. closings) and grain filters can be determined from families of increasing thresholds (t 1 , . . . , t I M AX ) for an increasing attribute κ. Thus, a node C ∈ N r(i) ⊆ T i satisfies the conditions of criterion Γ, if and only if, κ(C) ≤ t i and κ(parent(C)) > t i or equivalently κ(C) = κ(parent(C)) which also is equivalent to κ(parent(C)) -κ(C) > 0. Thus, one way to reduce this discomfort is to mark the nodes that have a great variation ∆ of attribute value with respect to its parent, i.e., C ∈ T f satisfies the conditions of criterion Γ, if and only if,

κ(parent(C)) -κ(C) > ∆. So, ∀N ∈ T f , we do: Γ(N ) = κ(parent(N )) -κ(N ) > ∆ .
Note that, choosing ∆ = 0 gives the classic ultimate leveling, ∆ = 1 integrates a series of non-null residues, ∆ = 2 integrates a series of residues separated by at least 2 consecutive null residues, and so on [START_REF] Marcotegui | Ultimate opening and gradual transitions[END_REF]. Note that, it is not easy to find the best value for ∆, since it is a global information and is not always possible to estimate the real contrast for all regions of the image.

• Primitives based on extinction values

Extinction values [START_REF] Grimaud | New measure of contrast: the dynamics[END_REF][START_REF] Vachier | Extinction value: a new measurement of persistence[END_REF] are good candidates to define a pruning predicate Γ. Extinction values are measures extracted from regional extrema (minima or maxima). In short, the extinction value of a regional extremum M for an increasing attribute κ is the maximal size of the attribute filter, such that there still exists a regional extremum M that contains M after the filtering [START_REF] Grimaud | New measure of contrast: the dynamics[END_REF][START_REF] Vachier | Extinction value: a new measurement of persistence[END_REF]. Thus, we can mark only the nodes such that their attribute value corresponds to an extinction value. This procedure can be done by the following algorithm [START_REF] Silva | Efficient computation of new extinction values from extended component tree[END_REF]:

1. For each leaf L of T f (i.e. regional extremum), the path towards the root is initiated.

(a) When a node N L with more than one child appears (i.e. a ramification) in the path, the following verification is performed:

i. Let C L ∈ children(N L ) be the node such that L ⊂ C L (i.e., C L is ancestral of L). If there exists another C ∈ children(N L ) such that κ(C) > κ(C L ), then κ(C L
) is defined as the extinction value for leaf L (note that, in this case, this is the maximum attribute value that maintains the regional extremum L [START_REF] Silva | Efficient computation of new extinction values from extended component tree[END_REF]). Thus, Γ(C) is true for all C ∈ children(N L ) and then an iteration for the next leaf is performed. ii. Otherwise, we continue the leaf path until the next ramification N L is found and the procedure is repeated. iii. Finally, if the path reaches the root, then its extinction value is set as the attribute value of the first node in the path before arriving at the root, which is the maximum image extinction value.

Fig. 10 shows the evolutions of residual values of a given pixel obtained from ultimate attribute closings based on extinction values. As we can see, comparing with the ones of Fig. 9, the residual values using height attribute with extinction value strategy are bigger than the ones obtained by using gradual transitions.

A summary of this section is illustrated on Fig. 11. Applications of ultimate levelings based on different families of primitives are shown highlighting the following aspects: (i) polarity of objects extracted from ultimate levelings: light (resp. dark) objects are residues extracted from anti-extensive (resp. extensive) primitives as attribute openings (resp. attribute closings) and objects in both polarities are residues extracted from self-dual primitives as grain filters; (ii) the choice of attribute type: attribute filters that simplify images more slowly, such as area attribute ones, tend to produce less contrast, whereas attribute filters that simplify images more abruptly tend to produce more contrast such as height attribute filters. (iii) the choice of a strategy for selecting primitives that produce more contrast such as primitives based on gradual transition or 20 on extinction values. In this way, we should remark that the parameter ∆ for selecting primitives based on gradual transition is a global information so that it is not always possible to estimate real contrast for all regions of the image, whereas extinction values are obtained from local information of the image associated to regional extrema and this makes them good alternatives to design non-parametric ultimate levelings.

Primitives based on marked image

Primitives based on marked image can be obtained by a traditional algorithm Λ, such as the one originally proposed by F. Meyer [START_REF] Meyer | The levelings[END_REF], to construct levelings that takes two images as arguments: an input image f ∈ F(D) and a marker image g ∈ F(D). It modifies g in such a way that it becomes a leveling of f . Let us denote by Λ(f, g) the leveling of f obtained from marker g.

It can be shown that anti-extensive (resp. extensive) levelings, named opening by reconstruction (resp. closing by reconstruction), can be constructed from marker images. They can be obtained by pruning operations of extended maxtrees (resp. min-trees) [START_REF] Alves | Scale-space representation based on levelings through hierarchies of level sets[END_REF]. In this case, the nodes of the tree to be pruned are determined according to the image marker [START_REF] Alves | Scale-space representation based on levelings through hierarchies of level sets[END_REF]. Then, let T ρ (T f , g) and T ρ * (T f , g) denote the trees obtained from, respectively, an opening and a closing by reconstruction of tree T f by marked image g ∈ F(D). Thus, families of openings (resp. closings) by reconstruction (ψ 0 (f ), ψ 1 (f ), . . . , ψ I M AX (f )) can be determined from families of markers (g 1 , g 2 , ..., g I M AX ) in the following way:

T 0 = T f , ψ 0 (f ) = Rec(T 0 ) = f , T i = P runing(T i-1 ) = T ρ (T i-1 , g i ) (resp. T ρ * (T i-1 , g i ))
and ψ i (f ) = Rec(T i ) for 1 ≤ i < I M AX . Thus, families of markers may be used to generate morphological scale-spaces based on levelings as shown by F. Meyer in [START_REF] Meyer | Nonlinear scale-space representation with morphological levelings[END_REF][START_REF] Meyer | Levelings and flat zone morphology[END_REF].

If primitives are neither extensive nor anti-extensive, then we can separately calculate positive and negative ultimate levelings and after combine them (see Prop.16 in [START_REF] Meyer | From connected operators to levelings[END_REF]).

In general, N r(i) is a set of connected components of graph T i T i+1 and, consequently, a node C ∈ N r(i) ⊆ T i satisfies the conditions of criterion Γ, if and only if node C is removed (and, at the same time, its parent node is preserved) by the pruning operation generated by the corresponding marker image.

Strategies for filtering undesirable residues

Ultimate levelings are operators that extract residual information from primitive families. During the residual extraction process, it is very common that undesirable regions of the input image contain residual information that should be filtered out. These undesirable residual regions often include desirable residual regions (which should be preserved) due to the design of the ultimate levelings which consider maximum residues.

T. Retornaz [START_REF] Retornaz | Automatic detection of text from natural scenes: a semantic descriptor for content based image retrieval[END_REF] already described this problem, called myopia, which is normally produced by nested structures (in fact, this can be confirmed by Prop. 3.7). In this way, J. Hernández and B. Marcotegui [START_REF] Hernández | Shape ultimate attribute opening[END_REF] proposed a solution for this problem using shape information during the residual extraction process. However, the drawback of this solution is that residual values are modified according to a similarity function and thus the properties of ultimate levelings are lost.

In this work, we propose an approach to preserve the original extracted residual values while filtering out residues extracted from undesirable regions.

As shown in Fig. 12, we calculate ultimate levelings R θ only for residues r i satisfying a given similarity criterion Ω.

ψ 0 (f ) ψ 1 (f ) ψ 2 (f ) ... ... ψ I M AX-1 (f ) ψ I M AX (f ) r1(f ) r2(f ) r3(f ) ... r I M AX-2 (f ) r I M AX-1 (f ) R θ (f ) = sup{ri(f ) : ri(f ) satisfies Ω}
Figure 12: Scheme for filtering out residues r i extracted from undesirable regions. For example, the residues in red do not satisfies the criterion Ω and thereby they are filtered out; the supremum is evaluate only on the blue ones.

This procedure can be implemented in several manners. To decide whether a residue r + i (f ) (resp., r - i (f )) is filtered out or not, just checking nodes C ∈ N r(i) that satisfy a given filtering criterion Ω : P(D) → {desirable, undesirable}. Thus, we only calculate the ultimate leveling R θ for residues r + i (resp., r - i ) such that satisfy the criterion Ω. So, positive (resp. negative) residues are redefined as follows:

∀p ∈ D, [r Ω+ i (f )](p) =    r + T i f (SC(T i f , p)), if SC(T i f , p) ∈ N r(i) and ∃C ∈ N r(i) such that Ω(C) is desirable; 0, otherwise. (12)
Ultimate levelings obtained from filtering out undesirable regions are redefined as follows:

R

Ω (f ) = R + Ω (f ) ∨ R - Ω (f ), (13)
where,

R + Ω (f ) = sup{r Ω+ i (f ) : i ∈ I} and R - Ω (f ) = sup{r Ω- i (f ) : i ∈ I}. (14)
Below are listed two examples for filtering strategy. The first one is based on feature vector [START_REF] Urbach | Connected shape-size pattern spectra for rotation and scale-invariant classification of gray-scale images, Pattern Analysis and Machine Intelligence[END_REF][START_REF] Urbach | Vector-attribute filters[END_REF] similar to the research from J. Hernández and B. Marcotegui [START_REF] Hernández | Shape ultimate attribute opening[END_REF] and the second one is based on stable regions [START_REF] Matas | Robust wide-baseline stereo from maximally stable extremal regions[END_REF].

Filtering based on shape information

Shape recognition is one of the fundamental problems in field of image analysis and various approaches have been proposed over the last decades. One of the shape recognition subproblems is called decision problem [START_REF] Hernández | Shape ultimate attribute opening[END_REF][START_REF] Veltkamp | Shape similarity measures, properties, and constructions[END_REF] that consists in comparing two patterns A and B using a similarity measure d : P(D) × P(D) → R + by means of a given threshold α, that is, deciding whether the similarity is greater or smaller than the threshold. Thus, we can construct Ω according to a similarity criterion, comparing the shape corresponding to a node C ∈ N r(i) and a reference shape Ω ref ∈ P(D). Thus, the criterion Ω is defined for any node C ∈ P(D) as follows:

Ω(C) = desirable, if d(C, Ω ref ) ≤ α, undesirable, otherwise. (15)
This filtering strategy was first introduced by J. Hernández and B. Marcotegui [START_REF] Hernández | Shape ultimate attribute opening[END_REF] where several shape similarity functions were studied.

Filtering based on Maximally Stable Extremal Regions

Maximally Stable Extremal Regions (MSER) originally introduced by Matas et al. [START_REF] Matas | Robust wide-baseline stereo from maximally stable extremal regions[END_REF] have been widely used in a variety of applications in computer vision as region detector. The regions detected by this method are the CCs of level sets with maximum stability and, as shown by Kimmel et al. [START_REF] Kimmel | Are MSER features really interesting?, Pattern Analysis and Machine Intelligence[END_REF], are invariant to affine transformations and thereby this method has an advantage compared to the SIFT detector. In this way, stability can be seen as a relationship between intensities and attributes of comparable CCs. More formally, a stability function associates to any CC C λ , extracted from a level set at value λ, the following value:

Stability(C λ ) = κ(C λ ) |κ(C λ-∆ ) -κ(C λ+∆ )| , (16)
where ∆ ∈ K is a stability parameter and C λ-∆ , C λ and C λ+∆ are comparable CCs extracted from level sets at values, λ -∆, λ and λ + ∆, respectively. Then, the CCs that correspond to the local maxima of stability function are called MSERs. It is worth mentioning that MSER variants [START_REF] Kimmel | Are MSER features really interesting?, Pattern Analysis and Machine Intelligence[END_REF][START_REF] Xu | Tree-based morse regions: A topological approach to local feature detection, Image Processing[END_REF] can be explored.

Based on these considerations, the criterion Ω is defined for any node C ∈ P(D) as follows:

Ω(C) = desirable, if C is MSER, undesirable, otherwise. (17)

Examples of application of ultimate levelings

This section provides some illustrative examples of application of ultimate levelings in order to give a glimpse of their usefulness.

Blood vessels segmentation

Blood vessels segmentation from images such as of Fig. 13a is a very important problem for retinal image analysis. Since ultimate levelings preserve location and shape of contours, it is appropriate to apply them along with a shape-based filter such as presented in Subsection 5.1. In fact, an approach is to first apply the closing top-hat operator (with a disk-shaped structuring element with a radius of 7 pixels) in order to reduce the amount of undesirable information (see Fig. 13c); and, then, apply an ultimate leveling with anti-extensive primitives and using a filter that emphasizes elongated objects defined as (although other definitions can be found at [START_REF] Lantuejoul | On the use of the geodesic metric in image analysis[END_REF][START_REF] Morard | Efficient geodesic attribute thinnings based on the barycentric diameter[END_REF][START_REF] Serna | Segmentation of elongated objects using attribute profiles and area stability: Application to melanocyte segmentation in engineered skin[END_REF]):

Ω elongation (C) =    desirable, if d(C, Ω ref ) = 1 E(C) ≤ α, undesirable, otherwise. ( 18
)
where E(C) = π SemiMajorAxis(C) 2 /(4 Area(C)) is the elongation measure [START_REF] Xu | Two applications of shape-based morphology: Blood vessels segmentation and a generalization of constrained connectivity[END_REF], obtained from Area(C) and SemiMajorAxis(C) which are, respectively, the area of CC (or shape) C and the length of semi-major axis of the best fitting ellipse on C computed by central moments.

We can see in Fig. 13e the result of this application. Just for comparison, Fig. 13d shows an application of ultimate levelings without applying elongation filtering. As we can observe, the elongation filter significantly improves the result.

Beans segmentation

Automated systems for inspection of agricultural products are very relevant for classification, quality estimation, and storage supervision of fruits and vegetables. In particular, since bean constitutes the staple diet of people in some countries, their visual quality inspection could reduce significantly the timeconsuming and high-cost of manual inspection task. One step to accomplish this automated inspection is to obtain a segmentation of beans from images such as of Fig. 14a. For that, we can apply ultimate levelings using grain filters (Fig. 14b and Fig. 14c) or attribute closings (Fig. 14d and Fig. 14e) as primitives along with filtering based on MSER, as discussed in Subsection 5.2. As we can see, the ultimate levelings using grain filters as primitives were able to segment the whole bean with no holes, since grain filters are self-dual operators.

Scene-text detection

Texts present within scenes are usually associated to digital media semantic contexts and may constitute important content-based descriptors. In particular, the problem of separating text from non-text regions in images, such as the ones presented in Fig. 15 taken from ICDAR dataset [START_REF] Lucas | Icdar 2003 robust reading competitions[END_REF], is a step to solve the scene-text detection problem. One approach is to solve another supervised classification problem that comes first which consists of deciding whether a connected component is a character or not. For that, we can define some features (descriptors) used in scene-text detection problems [START_REF] Retornaz | Scene text localization based on the ultimate opening[END_REF][START_REF] Alves | Text regions extracted from scene images by ultimate attribute opening and decision tree classification[END_REF][START_REF] Alves | Extraction of numerical residues in families of levelings[END_REF] such as: aspect ratio (H 1 ), rectangularity (H 2 ), number of holes (H 3 ) and color variance (H 4 ). From them, given a set of thresholds α i , β i ∈ R + , for i = 1, 2, 3, 4, we can build logical predicates Γ i (C) = α i ≤ H i (C) ≤ β i . For the purpose of this application, we used: The ultimate leveling with this composite filter can be used in a first step of scene-text detection problems in which a set of candidate characters is extracted and then a set of candidate text regions is constructed by merging candidate characters. Thus, these candidate text regions are classified as text or non-text regions [START_REF] Retornaz | Scene text localization based on the ultimate opening[END_REF][START_REF] Alves | Text regions extracted from scene images by ultimate attribute opening and decision tree classification[END_REF][START_REF] Fabrizio | Text detection in street level images[END_REF]. Fig. 15c shows the results of application of ultimate levelings in some images (presented at Fig. 15a) of ICDAR dataset [START_REF] Lucas | Icdar 2003 robust reading competitions[END_REF]. It is worth mentioning that text regions are extracted even in images with both polarities, low contrast, complex background and illumination problems. Just for comparison, Fig. 15e shows the results of application of Pesaresi's approach [START_REF] Pesaresi | Image segmentation based on the derivative of the morphological profile[END_REF]. As we can observe, the ultimate levelings along with a composite MSER-based filter significantly improves the result generating images without noises.

Conclusion

This work presents a new class of residual operators called ultimate levelings which are powerful multi-scale image operators defined on levelings scale-space. Besides, other contributions of this paper include: (i) the statement of properties of ultimate levelings (in Subsection 3.2), (ii) the presentation of an efficient algorithm for their computation inspired by Fabrizio and Marcotegui's algorithm [START_REF] Fabrizio | Fast implementation of the ultimate opening[END_REF] (in Subsection 3.3), (iii) the provision of strategies for choosing families of primitives (in Section 4), (iv) the presentation of strategies for filtering undesirable residues (in Section 5), (v) the provision of some illustrative examples (retinal blood vessels extraction, beans segmentation and text location) of application of ultimate levelings (in Section 6).

Furthermore, ultimate levelings are computationally efficient and their performance evaluations are comparable to the state of art methods for filtering and image segmentation. For example, some operators included in ultimate levelings class have been demonstrated to have good perfomance evaluation [START_REF] Li | Residues of morphological filtering by reconstruction for texture classification[END_REF][START_REF] Retornaz | Scene text localization based on the ultimate opening[END_REF][START_REF] Hernández | Shape ultimate attribute opening[END_REF][START_REF] Alves | Ultimate grain filter[END_REF][START_REF] Alves | Text regions extracted from scene images by ultimate attribute opening and decision tree classification[END_REF]. We also provide a plugin and source code for the popular free image processing software ImageJ [53] that gives access for some ultimate levelings operators. Instructions for download and installation can be found at http://www.ime.usp.br/ ~wonder/UL.

As a future work, in order to avoid nesting of residual regions, we plan to analyze a series of residues between nodes and, using a certain criterion, take a global decision for selecting the best residues.

Figure 1 :

 1 Figure 1: Image representation through a tree.

Figure 2 :

 2 Figure 2: Examples of lower and upper level sets extracted from an image. At right is the input image f and at top and bottom rows, respectively, are the level sets X λ ↓ (f ) and X ↑ λ (f ).

Figure 3 :

 3 Figure 3: Examples of trees (L(f ), ⊆) and (U (f ), ⊆) built from the lower and upper level sets presented in Fig. 2.

Figure 4 :

 4 Figure 4: Examples of component trees along with the highlighted pixels in red indicating their smallest component.

Figure 5 :

 5 Figure 5: Example of a scale-space based on levelings.

Figure 6 :

 6 Figure 6: An example of ultimate attribute closing is shown: (top) Trees derived by successive prunings; (middle) primitives family {ψ i (f ) : ψ i (f ) = Rec(T i ), i = 0, 1, ..., 6}; (bottom) extracted residues {r 0 (f ), r 1 (f ), ..., r 5 (f )}; and the result of ultimate attribute closing sup{r i (f )}.

Figure 7 :

 7 Figure 7: Example of the associated image q Imax and the ultimate leveling R θ (f ) of the input image presented in Fig. 6.

Proposition 3 . 3 .Corollary 3 . 5 .Corollary 3 . 6 .

 333536 Ultimate levelings are connected operators. Proposition 3.4. Positive (resp., negative) ultimate levelings are arcwise connected operators. Consequently, Props. 3.3 and 3.4 lead us to Corollaries 3.5 and 3.6. Ultimate grain filters are connected operators. Ultimate attribute openings (resp., closings) are arcwise connected operators.

Corollary 3 . 11 .

 311 Ultimate grain filters are self-complementary. Corollary 3.12. If R + θ (f ) is an ultimate attribute opening of f and R

10 foreachS

 10 ∈ children(C) do 11 BasicComputationOfUltimateLeveling (T f , S);

  primitives based on attribute level of the pixel fixed area closing (null residues) area closing (negative residues) height closing (null residues) height closing (negative residues)

Figure 8 :

 8 Figure 8: Evolution of residual values of the pixel marked in red of the input image obtained from ultimate attribute (area and height) closings.

  based on gradual transition ultimate height closing based on gradual transition primitives based on gradual transition level of the pixel fixed area closing (null residues) area closing (negative residues) height closing (null residues) height closing (negative residues)

Figure 9 :

 9 Figure 9: Evolution of residual values of the pixel marked in red of the input image obtained from ultimate attribute (area and height) closings using a family of primitives based on gradual transition. (see Fig.8).

8

 8 Figure 9: Evolution of residual values of the pixel marked in red of the input image obtained from ultimate attribute (area and height) closings using a family of primitives based on gradual transition. (see Fig.8).

  Figure 9: Evolution of residual values of the pixel marked in red of the input image obtained from ultimate attribute (area and height) closings using a family of primitives based on gradual transition. (see Fig.8).

  based on extinction values) ultimate height closing based on extinction values) primitives based on extinction values level of the pixel fixed area closing (null residues) area closing (negative residues) height closing (null residues) height closing (negative residues)

Figure 10 :

 10 Figure 10: Evolution of residual values of the pixel marked in red of the input image obtained from ultimate attribute (area and height) closings using a family of primitives based on extinction values.

Figure 11 :

 11 Figure 11: Example of applications of ultimate levelings where each row contains applications of UAO, UAC and UGF using primitive families based on attributes (area and height of bounding box), gradual transition (GT) with ∆ = 5 and extinction values (EV).

  (a) input RGB image (b) input image (channel G) (c) closing top-hat (d) UAO applied in (c) (e) UAO with elongation filter (f) Overlap: (b) and (e)

Figure 13 :

 13 Figure 13: Application of ultimate leveling (ultimate attribute opening) with elongation shape information.

  (a) input image (b) UGF with filtering based on MSER. (c) highlight the result of (b). (d) UAC with filtering based on MSER. (e) highlight the result of (d).

Figure 14 :

 14 Figure 14: Example of applications of ultimate levelings for beans segmentation.

Γ 1 (

 1 C) = 0 ≤ H 1 (C) ≤ 8 Γ 2 (C) = 0, 4 ≤ H 2 (C) ≤ 0.95 Γ 3 (C) = 0 ≤ H 3 (C) ≤ 5 Γ 4 (C) = 0 ≤ H 4 (C) ≤ 60 (19)These logical predicates can be used along with filtering based on MSER in the following wayC is MSER and Γ i (C) are all true, for i = 1, . . . , 4, undesirable, otherwise.

  (a) input images (b) Results using ultimate levelings. (c) Highlight the of results (b).

  (d) Results using Pesaresi's approach[START_REF] Pesaresi | Image segmentation based on the derivative of the morphological profile[END_REF] (e) Highlight the of results (d).

Figure 15 :

 15 Figure 15: Application of ultimate grain filter with composite filter.

  keeping the maximum positive and negative residues for each pixel. More precisely, see Def. 3.1.Definition 3.1 (Ultimate levelings). A positive ultimate leveling operator R +

θ

(resp., negative R - θ ) is the supremum of positive (resp., negative) residues r + i (resp., r - i ) extracted from a family {ψ i : i ∈ I} indexed by a set I, such that, for any

An adjacency relation A on D is binary relation on pixels of D. Thus, (p, q) ∈ A if and only if p is an adjacent of q or alternatively q ∈ A(p). Common examples of adjacency relation on D are 4 or 8-connectivities.

Acknowledgments

This paper was financially supported by CAPES, CNPq and FAPESP (grant numbers: 2016/02547-5).


Jibril Frej
email: jibril.frej@etu.univ-grenoble-alpes.fr

Didier Jean-Pierre Chevallet
email: jean-pierre.chevallet@imag.fr

Schwab Laboratoire D'

Enhancing Translation Language Models with Word Embedding for Information Retrieval

Keywords: Information Retrieval, Language Model, Word Embedding

 that proposes to estimate the translation probability of a Translation Language Model using the cosine similarity between Word Embedding. The results we obtained so far did not show a statistically significant improvement compared to classical Language Model.

Introduction

Information Retrieval Systems (IRS) are computer assistants that help to retrieve digital documents, in which user is supposed to found relevant information for his task. Hence an IRS is about semantics, because user information needs is topically related and serve to help to accomplish user's task.

Curiously, most commercial and experimental search engine do not handle any sort of semantics nor knowledge to solve queries. This is because matching computations are mostly based on statistical word distributions, and intersection between query and documents. Also, most IR models see query and document as simple bag of word. Though, these systems provide satisfaction to their user, as long as statistics are possible, i.e. documents are long enough and queries are expressed using the same vocabulary as documents.

When we are not in this situation, that is, if documents to be retrieved are very short and/or there is a strong discrepancy between document vocabulary and user's one, IRS are facing the problem of term mismatch. For example, the collection Europeanna 1 gives access to millions of digital objects from cultural heritage, by a very small textual meta-data description. Even, descriptions are made by specialists that are prone to use technical terms.

Hence, in this paper we propose to study the effect of exploiting semantic resources to reduce term mismatch negative effect on collection with specialized vocabularies. We focus on automatically constructed resources, namely word Embedding resources, first because they cover a very large vocabulary, and second, because they seem to capture interesting word semantics (Mikolov et al., 2013).

A very simple way to exploit a resource to solve term mismatch, is to expand queries or documents with words that are semantically similar according to the resource. This approach has been heavily studied [START_REF] Carpineto | A survey of automatic query expansion in information retrieval[END_REF] and suffers from a definitive problem: how to control query meaning shift when a-priory the query is statically modified, i.e. for all documents ?

In this paper, we propose not to change the query nor the document but to adapt the matching function. This adaptation requires to change the formula that computes the Relevant Status Value (RSV). This formula depends on the Information Retrieval (IR) model.

There are several large categories of IR model: Vector Space, Logical Based, Probabilist, Graph Based, and Language Models (LM). Among these models, only the Probabilist models like the famous BM25 formula of Robertson [START_REF] Robertson | Okapi at trec-3[END_REF] A simple way to include a Knowledge Resource in a LM matching function, is Translation Language Models [START_REF] Berger | Information retrieval as statistical translation[END_REF] where the translation probability between query and document terms is taken into account, in addition to the exact term matching. Probability are estimated using the mutual information between the two terms and is the highest if the considered terms have the same distribution over the collection. This computation can be considered as an automatic basic knowledge resource extracted from the corpus itself. Recently, it has been proposed to estimate the translation probability using Neural Word Embedding (Zuccon et al., 2015).

Word Embedding denotes a set of methods to produce Knowledge resources with vector representation of words2 that express some semantics learned from word usage in very large text collection. Usually these methods are based on the distributional hypothesis [START_REF] Harris | Distributional structure[END_REF]: words that occur in the same contexts tend to have similar meaning. The vector representation of words are computed using their context so that words with similar meaning will have similar vector representation. Word Embedding includes dimension reduction techniques on the word co-occurrence matrix (Latent Semantic Analysis [START_REF] Deerwester | Indexing by latent semantic analysis[END_REF])), probabilistic models (Latent Dirichlet Allocation [START_REF] Blei | Latent dirichlet allocation[END_REF]) and more recently shallow neural networkbased methods such as the skip-gram model that can also learn phrases vector representations and is very effective on word similarity and word analogy tasks (Mikolov et al., 2013). As we said before, these vector representations can be used to capture semantic relationships between words by measuring the similarity between the vectors, with the cosine similarity measure for example.

Such vector representation could help us with the vocabulary mismatch problem since they provide us a new way to estimate the translation probability between query and document terms by considering their semantic similarity. The empirical results show that improving Dirichlet Language Model using Word Embedding is possible.

In the rest of this paper, we first recall LM formulas in section 2, present the extension with the translation model in section 3, then the usage of Word Embedding within this model in section 4. We present the implementation of this model in section 5 and results on the Cultural Heritage in CLEF (CHiC) Dataset3 , a sub part of the Europeanna, in section 6.

Language models

In this part, we recall basics on the Language Model in order to detail our modifications of the formula in the next section. The query likelihood Language Model aims to rank documents d by computing the probability of a document interpreted as the likelihood that it is relevant to the query q. Hence, the Relevance Status Value (RSV) of a Language Model based IR is expressed by:

RSV pq, dq " ppd|qq

Using Bayes rule, we have:

RSV pq, dq " ppq|dqppdq ppqq (2)
We can ignore the constant ppqq to rank documents and we also consider that ppdq is uniform over all the documents of the collection and can also be ignored. Therefore, to rank documents with respect to a given query, we only have to compute the probability of having q, knowing d. In LM model, document d is replaced by its language model, i.e. the probability distribution of terms of the vocabulary in d denoted θ d . So the RSV is:

RSV pq, dq » rank ppq|θ d q

(3)

In this work, we chose the multinomial event model for θ d , and the unigram language model4 , so the probability of a given word does not depend on its context:

RSV pq, dq » rank log pppq|θ d qq " |q| ÿ i"1 log pppq i |θ d qq (4)
With q i the i th term of the query and |q| the query size. To estimate ppq i |θ d q, Dirichlet Language Model is used since it has been shown to work better with Translation Language Models (Karimzadehgan & Zhai, 2010) :

ppq i |θ d q " |d| µ `|d| p ml pq i |θ d q `µ µ `|d| ppq i |Cq (5)
µ P R `is the smoothing parameter and p ml pq i |θ d q is estimated using the maximum likelihood 5 and is equal to:

p ml pq i |θ d q " cpq i , dq |d| (6)
With cpq i , dq the frequency of q i in d and |d| the document size. The same goes for ppq i |Cq the smoothing term which is also estimated with the maximum likelihood : ppq i |Cq " cpq i , Cq{|C|. This estimation of ppq i |θ d q leads to the following ranking formula (see the appendix for more details) :

RSV pq, dq » rank ÿ i:cpq i ,dqą0 " log ˆ1 `cpq i , dq µppq i |Cq ˙ `|q|log ˆµ µ `|d| ˙(7)
We decided to present equations ( 5) and ( 7) even though they are equivalent for ranking documents because both of them can be found to describe Dirichlet Language Model. In the frame of our work, and for reasons that are developed in the appendix, we will introduce the next models by giving the expression of ppq i |θ d q as in equation ( 5).

As we said previously, one issue of these models is the term mismatch problem: as we can see on equation ( 7) ranking takes into account only the terms that appear in both the considered document and query. Consequently, relevant documents that do not contain the exact query terms will not be considered. One approach to solve this problem is to adapt the language model to take into account the semantic similarities between terms.

Translation Language Models

Translation Language Models (TLM) try to estimate the semantic similarity between two terms by using tools from statistical translation. The main idea is to estimate the likelihood of translating a document to a query using the translation probability between terms [START_REF] Karimzadehgan | Estimation of statistical translation models based on mutual information for ad hoc information retrieval[END_REF]. To do so, the maximum likelihood estimator in the Dirichlet language model p ml pq i |θ d q is replaced with the likelihood that the query has been produced by a translation of the document p t pq i |θ d q:

ppq i |θ d q " |d| µ `|d| p t pq i |θ d q `µ µ `|d| ppq i |Cq (8)
p t pq i |θ d q is calculated the following way :

p t pq i |θ d q " ÿ uPd p t pq i |uqp ml pu|θ d q (9)
With p t pw|uq the probability to translate term u into term w which is estimated using mutual information between u and w (Karimzadehgan & Zhai, 2010) :

p t pw|uq "
Ipw, uq ř

w 1 PV Ipw 1 , uq (10)
Ipw, uq is the mutual information score between word u and w, defined as follow :

Ipw, uq " ÿ Xw"0,1 ÿ Xu"0,1 ppX w , X u qlog ˆppX w , X u q ppX w qppX u q ˙(11)
With X w and X u binary random variables indicating if a word is absent or present (refer to (Karimzadehgan & Zhai, 2010) for more details).

Word Embedding-based Translation Language Model

Within the frame of this work, word Embedding are used instead of mutual information in order to estimate the translation probability p t pq i |uq. The model is named Word Embedding-based Translation Language Model (WETLM). We consider the new estimation of the translation probability, denoted p cos pq i |uq, to be proportional to the similarity between q i and u that is measured with the cosine between the vectors of the two terms :

p cos pq i |uq " cospq i , uq ř u 1 PV cospu 1 , uq (12)
Consequently the ranking formula becomes :

ppq i |θ d q " |d| µ `|d| p cos pq i |θ d q `µ µ `|d| ppq i |Cq (13)
With p cos pq i |θ d q " ř uPd p cos pq i |uqp ml pu|θ d q. Both the estimation of the translation probability p t and p cos underestimate the self-translation probability: we can have p cos pu|wq ą p cos pu|uq for u ‰ w which is not desirable for a translation language model [START_REF] Karimzadehgan | Axiomatic analysis of translation language model for information retrieval[END_REF].

One way to make sure that the self-translation probability is the highest for a given term is to redefine it by introducing a hyper-parameter α P r0, 1s that "controls" the self-translation probability [START_REF] Karimzadehgan | Estimation of statistical translation models based on mutual information for ad hoc information retrieval[END_REF]:

p cos´α pw|uq " # α `p1 ´αqp cos pw|uq if u " w p1 ´αqp cos pw|uq if u ‰ w (14)
This formula ensures the fact that we have p cos´α pu|uq ą p cos´α pu|wq@u, w P V for α ą 0.5. The model that uses p cos´α to estimate the translation probability will be referred as WETLM-α. We set the value of α to 0.45 since it is the one that produced the best results for the Threshold T = 0.7. This approach was not developed in the paper Integrating and Evaluating Neural Word Embedding in Information Retrieval by [START_REF] Zuccon | Integrating and evaluating neural word embeddings in information retrieval[END_REF] since they reported that the word Embedding they used did not underestimate the self-translation probability.

Implementation and data

For this work, instead of using an already existing Information Retrieval System (IRS) such as Terrier, we developed our own IRS in C++ to easily add word Embedding to the classical mod-els and also because having a low retrieval time 6 is not an objective: before trying to compute a fast IRS, we should make sure that the Word Embedding-based language models outperforms state of the art Language models. In order for our results to be comparable with other work that used Terrier, we made sure that with the same pre-processing on the corpus, we obtain the same results as Terrier ( see the appendix for more details about our IRS ). When doing so, we noticed that Terrier does not implement Dirichlet language model using equation (7) (more details in the appendix).

During pre-processing, we used a Stop List and replaced capital letters with lower case letters on both the collection and the queries. In order to have the same results as Terrier with our IRS, we also removed characters that were not digits or letters and deleted words that contained more that 4 digits or more than 3 consecutive identical characters. We did not use any stemmer on our collection since the best results were obtained without any stemming.

We used the Cultural Heritage in CLEF (CHiC) 2012 English collection for ad hoc retrieval. This collection is composed of 1 107 176 documents containing "metadata records describing digital representations of cultural heritage objects" [START_REF] Petras | Cultural heritage in clef (chic) overview[END_REF] With #d and #q being respectively the number of documents in the collection and the number of queries. Avdl is the average document length and Avql is the average query length. To evaluate the models, the top 1000 documents were returned for each query, the MAP and P@10 were computed using the standard tool for evaluating an ad hoc retrieval: trec_eval.

We used the word2vec-GoogleNews-vectors word Embedding of dimension 300, pre-trained on the google news Corpus (3 billion words) that are available here7 . As we said earlier, the CHiC collection we used have a very specific vocabulary and even if the word Embedding we used were trained on a 3 billion words corpus, a lot of word of the vocabulary were missing :

• only 42.68% of the words of the vocabulary have an Embedding;

• but 91.92% of word occurrences in the collection have an Embedding.

On the other hand, most of the queries's terms had an Embedding :

• 94.95% of the queries terms have an Embedding;

• 2% of the queries have none of their term that posses an Embedding.

Finally, the translation probability described in equation ( 12) is not the one that was implemented: we computed the cosine similarity between two words if it was above a given threshold

  , or Language Models provide state of the art results. Some recent proposals of IR Graph Modeling[START_REF] Bannour | Modèle unifié pour la recherche d'information sémantique[END_REF] have the advantage to fuse one single model document index and knowledge base, and exploit only one matching function: activation propagation from query term to document through indexing terms and knowledge concept nodes. Beside the nice property of this model to exploit a Knowledge Base at query time, without query or document expansion, experiments of this model are still bellow the state of the art of Probabilistic or Language models. For this reason, we have decided to work on the transformation of a Language Model formula. We did not chose a Probabilistic model because formulas of the LM model are much simpler for similar results[START_REF] Manning | Introduction to Information Retrieval[END_REF], hence they are easier to transform.

Table 1 :

 1 and 50 queries for ad hoc retrieval tasks. Below is a table summing up some statistics of the collection: CHiC 2012 statistics

	#d	Avdl Vocabulary Size #q Avql
	1 107 176 30.92	290 265	50 1.84

http://www.europeana.eu

Most of the time the vectors are real-valued.

http://ims.dei.unipd.it/data/chic/

Usually in IR the unigram language model give the best results with the lowest computational cost[START_REF] Manning | Introduction to Information Retrieval[END_REF]

Which is the case with Terrier

https://github.com/mmihaltz/word2vec-GoogleNews-vectors

T. This allowed us to reduce the number of cosine similarities to compute and also it acts like a noise reducer since we did not take into account the similarity between non similar terms. We found that T = 0.7 produces the highest MAP on the CHiC collection using word2vec-GoogleNews-vectors.

Results

Instead of giving the value of the parameter µ that produces the optimal results, we decided to display the MAP for a range of values of µ to see if the WETLM outperforms (or not) the Dirichlet LM consistently or if for some values of µ one model performs better than the other.

At first we evaluated the Dirichlet LM, the optimal value we found for µ was 44. Retrieved documents are evaluated using the Mean Average Precision and P@10: We checked that the results obtained are identical to the ones produced by Terrier with the same pre-processing on the collection. Also we decided to explore values of µ that are close to the Average Document Length (Avdl) since the optimal value of µ in the Dirichlet Language Model is usually around the Avdl. 5: Values of the P@10 on the CHIC2012 collection using WETLM As we can see the WE-based Translation Language Model seems to sightly outperform the Dirichlet Language model for every µ. The optimal value of µ we found is different for the two models : µ opt " 44 for the Dirichlet LM and µ opt " 24 for the WETLM. We performed a paired t-test over the average precision of each query for µ = 36 for both models, the measured p-value with R is 0.1733 > 0.01. Unfortunately the improvement is not statistically significant.

In the table below we show some of the results collections presented in the work of ( We performed a paired t-test over the average precision of each query for µ = 36 to compare LM and WETLM-α models : the measured p-value with R is 0.01219 > 0.01 : the improvement is still not statistically significant.

Conclusion and future work

The results we obtained are consistent with the ones in [START_REF] Zuccon | Integrating and evaluating neural word embeddings in information retrieval[END_REF] since they observed the same improvement as we did in the MAP. They also checked that their improvements were independent of the corpus and the training set for the Word Embedding: they do not need to be trained on the same corpus used in retrieval. For now our results are limited to one corpus and one set of word embedding, one of our objective in the near future is to perform the experiments on different corpora and also to improve our model by considering the context of the terms of the query by using phrase vectors (Mikolov et al., 2013) to replace the query or to perform query expansion and by modifying the translation probability so that it satisfies a set of constraints [START_REF] Karimzadehgan | Axiomatic analysis of translation language model for information retrieval[END_REF]

The last term of the equation above depends only on the query and collection, therefore it can be ignored to rank documents, which leads to :

Why equation (5) instead of equation ( 7) :

As we said previously, usually language model RSV functions are presented using a sum that goes through terms that appear in both the document and the query, as in equation ( 7). The reason is that this formulation is more compatible with the usage of an inverted index. In fact an inverted index just associates to a term, all documents with non null term frequency: this is called the posting list. When using inverted index, the matching computation have to compute partial RSV sum for all documents found in posting lists, in parallel. If the formula only requires terms to have non null frequency in documents as in formula (7) the matching algorithm is trivial. If the formula need all terms of the query, as in formula (5) then some partial matching sums has to be corrected during matching computation and the matching algorithm is much more complex and less efficient. In our experimental system, we do not use any inverted index: we store the all index in a direct structure in main memory. Hence, matching is done by simply browsing all documents and computing RSV strait using the formula.

The models we presented that used statistical translation and word Embedding cannot be written with only a sum over q X d as in equation ( 7) : this is why we used equation (5) to give the expression of the rank. Hence the implementation using a inverted fil is more problematic, and for example, cannot be done in a simple way in Terrier. That is the reason why we could not use Terrier for these experiments.

Terrier's Dirichlet Language Model :

Moreover during the experiment, when we tried to obtain the same results as Terrier, we noticed that they did not implement exactly equation ( 5) to compute the score of each document. Below is the formula they used to compute the score of documents :

Compared to equation ( 5) where the quantity log ´µ µ`|d| ¯is computed |q| times, this formula computes it only |q X d| times. Since log ´µ µ`|d| ¯ă 0, equation(15) gives a little bit more importance to query terms that do not appear in documents. For our experiment, the Dirichlet language model was implemented using equation (5) but we also checked that we obtained the same results as Terrier when computing equation (15).

Some details about the implemented Information Retrieval System

In order to have the same results as Terrier, our IRS performed the following pre-processing on the collection :

• We replaced with a space all the characters that were not integers or letters, for example the term pre-processing is broken down into the two terms pre and processing.

• We also replaced majuscule letters with their minuscule equivalent

• We deleted terms that contained more than 4 digits

• We deleted terms that had more than 3 consecutive identical characters Also, when we implemented equation (13) ( the ranking formula of the WETLM), we decided to remove the normalization terms when p cos pq i , θ d q or ppq i |Cq were equal to 0 :

|d| µ`|d| p cos pq i |θ d q `µ µ`|d| ppq i |Cq if p cos pq i |θ d q ‰ 0 and ppq i |Cq ‰ 0 p cos pq i |θ d q if p cos pq i |θ d q ‰ 0 and ppq i |Cq " 0 ppq i |Cq if p cos pq i |θ d q " 0 and ppq i |Cq ‰ 0 (16)

We decided to do so in order to avoid underweighting the translation probability of a query term that is not in the collection and conversely to avoid underweighting the smoothing term of associated to a word that is in the collection but does not have any similar terms in the considered document.