Nicolas Boutry
email: nicolas.boutry@lrde.epita.fr

Laurent Najman
email: laurent.najman@esiee.fr

Thierry Géraud
email: thierry.geraud@lrde.epita.fr

Topological Properties of the First Non-Local Digitally Well-Composed Interpolation on n-D Cubical Grids

Keywords: well-composed images, critical configurations, digital topology, tree of shapes, mathematical morphology

In discrete topology, we like digitally well-composed (shortly DWC) interpolations because they remove pinches in cubical images. Usual well-composed interpolations are local and sometimes self-dual (they treat in a same way dark and bright components in the image). In our case, we are particularly interested in n-D self-dual DWC interpolations to obtain a purely self-dual tree of shapes. However, it has been proved that we cannot have an n-D interpolation which is at the same time local, self-dual, and well-composed. By removing the locality constraint, we have obtained an n-D interpolation with many properties in practice: it is self-dual, DWC, and in-between (this last property means that it preserves the contours). Since we did not published the proofs of these results before, we propose to provide in a first time the proofs of the two last properties here (DWCness and in-betweeness) and a sketch of the proof of self-duality (the complete proof of self-duality requires more material and will come later). Some theoretical and practical results are given.

Introduction

It is well-known that images coming from the digitization of the real world loose a part of their topological properties (their boundaries are no longer topological manifolds for example). In a discrete image, different possible connectivities exist (like c 2n and c 3 n -1 ), to cite only the most famous, which means that depending on the chosen connectivity, some algorithms will work in a specific way; this can lead to topological paradoxes (it can happen that a simple, closed curve in the digital plane no longer separates this plane into an interior and an exterior like in the Euclidian case). Latecki introduced then well-composed images with topological properties similar to the ones of the objects in the real world; for example, in 2D and 3D, an image which is well-composed will not longer have pinches in its boundary. Note that a summary of the different flavors of well-composednesses can be found in [START_REF] Boutry | A tutorial on well-composedness[END_REF].

The question which arises then is: since natural or synthetic discrete images are generally not well-composed, how can we compute a "good" DWC representation of a given image u? It has been shown in [START_REF] Boutry | On making n-D images well-composed by a selfdual local interpolation[END_REF] that it is impossible in a local manner, and thereafter we proposed a way to compute a well-composed approximation in [START_REF] Boutry | How to make images well-composed in n-D without interpolation[END_REF] (without interpolation). However, this last approach modifies the values of the initial function, and then we proposed a new method in [START_REF] Boutry | How to make n-D functions digitally well-composed in a self-dual way[END_REF] (with interpolation) that we can consider as being a "representation" of the initial image since it preserves the topology of this image. The aim of the present paper is thus to prove that this last representation is in-between (roughly speaking, it preserves the contours of the initial image), and that it is a well-composed interpolation (in the digital sense, that is, without critical configurations). This last property leads to a strong mathematical property: the tree of shapes of a same image is unique and no longer depends on the choice of connectivities (for the upper and lower threshold sets). This paper extends [START_REF] Boutry | How to make n-D functions digitally well-composed in a self-dual way[END_REF] and [START_REF] Boutry | How to make images well-composed in n-D without interpolation[END_REF] in the sense that we provide mainly:

the proof that digital well-composedness is equivalent to local 2n-connectivity (as seen in [START_REF] Boutry | How to make n-D functions digitally well-composed in a self-dual way[END_REF]), the proof of the characterization of a digitally well-composed gray-level image published in [START_REF] Boutry | How to make images well-composed in n-D without interpolation[END_REF], the proof that the interpolation provided in [START_REF] Boutry | How to make n-D functions digitally well-composed in a self-dual way[END_REF] is digitally well-composed, the formalization of the notion of in-betweeness (it preserves the contours, see [START_REF] Boutry | How to make n-D functions digitally well-composed in a self-dual way[END_REF]), the proof that the interpolation provided in [START_REF] Boutry | How to make n-D functions digitally well-composed in a self-dual way[END_REF] is in-between.

Among the different methods used to make an image well-composed, there exist two main approaches: topological reparations [START_REF] Boutry | How to make images well-composed in n-D without interpolation[END_REF][START_REF] González-Díaz | Well-composed cell complexes[END_REF][START_REF] Siqueira | Topological repairing of 3D digital images[END_REF][START_REF] Boutry | Weakly well-composed cell complexes over n-D pictures[END_REF] and well-composed interpolations [START_REF] Géraud | Selfduality and digital topology: links between the morphological tree of shapes and wellcomposed gray-level images[END_REF][START_REF] Köthe | Generische Programmierung für die Bildverarbeitung[END_REF][START_REF] Latecki | Well-composed sets[END_REF][START_REF] Mazo | Digital imaging: A unified topological framework[END_REF][START_REF] Rosenfeld | Topology-preserving deformations of twovalued digital pictures[END_REF][START_REF] Stelldinger | 3D object digitization: Majority interpolation and marching cubes[END_REF]. The topological reparations are generally not topology-preserving, such as in [START_REF] Boutry | How to make images well-composed in n-D without interpolation[END_REF][START_REF] Siqueira | Topological repairing of 3D digital images[END_REF], are limited to the 3D case [START_REF] González-Díaz | Cohomology ring of 3D cubical complexes[END_REF][START_REF] González-Díaz | Cubical cohomology ring of 3D photographs[END_REF][START_REF] González-Díaz | Cup products on polyhedral approximations of 3D digital images[END_REF][START_REF] González-Díaz | Towards digital cohomology[END_REF][START_REF] González-Díaz | On the cohomology of 3D digital images[END_REF], or are just proven to be weakly well-composed [START_REF] Boutry | Weakly well-composed cell complexes over n-D pictures[END_REF]. We will then not go further into details about topological reparations in this paper. However, well-composed interpolations are more likely to preserve the topology of the initial image, since they preserve the initial data, and a brief state-of-the-art will then be presented hereafter.

Applications of digital well-composedness are numerous: as well depicted in [START_REF] Boutry | A tutorial on well-composedness[END_REF], we do not have any hole problem [START_REF] Siqueira | Making 3D binary digital images wellcomposed[END_REF] or ambiguous cases using the technology called Marching Cubes [START_REF] Lorensen | Marching cubes: A high resolution 3D surface construction algorithm[END_REF], used to represent surfaces surrounding a set of points in a 3D space. We can also compute thin topological maps [START_REF] Marchadier | Thinning grayscale well-composed images[END_REF], we can proceed to text extraction using the tree of shapes of the sign of the morphological Laplacian [START_REF] Huynh | Morphology-based hierarchical representation with application to text segmentation in natural images[END_REF] made digitally well-composed, we can compute the Dahu pseudo-distance [START_REF] Géraud | Introducing the Dahu pseudo-distance[END_REF], a good approximation of the Minimum Barrier distance, to proceed to salient object detection [START_REF] Zhang | Minimum barrier salient object detection at 80 FPS[END_REF], and so on.

Section 2 briefly discusses the state-of-theart in matter of well-composed interpolations. Then, in Section 3, we recall the theoretical background relative to DWCness in n-D. In Section 4, we introduce new material relative to DWCness; in particular we prove some assertions from [START_REF] Boutry | How to make images well-composed in n-D without interpolation[END_REF] and from [START_REF] Boutry | How to make n-D functions digitally well-composed in a self-dual way[END_REF] related to DWCness itself. In Section 5, we explain how to compute our n-D interpolation based on a front-propagation algorithm (FPA). In Section 6, we show the main results of the paper, that is, the proofs that our interpolation is in-between and that its output is digitally well-composed (extending [START_REF] Boutry | How to make n-D functions digitally well-composed in a self-dual way[END_REF]). Section 7 shows some theoretical and practical applications resulting from our interpolation. Finally, Section 8 provides a sketch of the proof of self-duality, Section 9 concludes the paper, and Section 10 is the appendix of the paper, containing secondary proofs.

State-of-the-Art

In this section, we recall the different existing well-composed interpolations, and we detail why local self-dual interpolations cannot be well-composed in n-D, n ≥ 3. For the interested reader, all the details about the origin of well-composedness can be found in the tutorial [START_REF] Boutry | A tutorial on well-composedness[END_REF] of Boutry et al..

The restriction of an interpolation to the initial domain is equal to the initial image. In that sense, interpolations preserve the initial data. However, without constraints, there is no guarantee that the interpolation has the same topology as the initial image. For example, the 1D image • • represents two connected pixels, valued at 1. One non-constrained interpolation can then be • • •, where • denotes a pixel valued at 0. The two black points are then disconnected. For this reason, we will consider only what we call in-between interpolations, that is, interpolations such that the secondary pixels have values that are between the values of the primary pixels. They have the property not to create any new extrema in the image. In that sense, in-between interpolations preserve the topology of the initial image.

In 1998, Rosenfeld, Kong and Nakamura [START_REF] Rosenfeld | Topology-preserving deformations of twovalued digital pictures[END_REF] developed the first well-composed 2D interpolation, that is a method able to compute an image on a larger domain than the one of the initial image, such that its restriction to the initial domain equals the original image and such that the resulting interpolation is well-composed. This method can be decomposed in two steps: first, an image magnification [START_REF] Rosenfeld | Topology-preserving deformations of twovalued digital pictures[END_REF], which is equivalent to replacing each pixel of the original image by a set of (k + 1) × (k + 1) pixels (where k ≥ 1 is given) of the same value and which replaces the original pixel; second, a modification step removes the critical configurations of the magnified image by changing one of the values of the 4 points of the critical configuration (from 0 to 1 or the converse). Since the magnification process and the modifications are simple deformations [START_REF] Rosenfeld | Topology-preserving deformations of twovalued digital pictures[END_REF], they preserve the topology (in the sense that the two images have the same adjacency tree and the same homotopy type), and then the final image is a well-composed image topologically equivalent to the initial one.

Then, in 2000, Latecki [START_REF] Latecki | Well-composed sets[END_REF] developed an alternative method to make a 2D binary image well-composed. This new method is based on the image expansion of Köthe [START_REF] Köthe | Generische Programmierung für die Bildverarbeitung[END_REF], and consists of doubling the resolution of the square grid of the initial image by adding new pixels (the so-called "secondary" pixels) between the original pixels (the "primary" pixels). A secondary pixel added between two edge-connected pixels will take the value of these primary pixels iff they have the same value. Otherwise, they will be labeled as "boundary points". A secondary pixel added at the center of a square of 4 vertex-connected pixels will take the value of these pixels iff they all have the same value. In the complementary case, they will be labeled boundary points. Finally, we obtain 3 sets, a set of zeros, a set of ones, and a set of boundary points, each of them being wellcomposed. We can denote the difference between these two first algorithms: the one of Rosenfeld et al. is based on simple deformations, so it ensures topological equivalence, but the one of Latecki is based on a "counting process", which ensures well-composedness but no topological equivalence.

Then in 2006, Stelldinger proposed a method called Majority Interpolation [START_REF] Stelldinger | 3D object digitization: Majority interpolation and marching cubes[END_REF] which can be seen as a slightly modified 3D extension of Latecki's method [START_REF] Latecki | Well-composed sets[END_REF], since it is based on a similar counting process. The resulting binary image is always well-composed in the sense that the resulting boundary in the inter-polated image is a 2-manifold, but this method is not self-dual.

In 2000, Latecki [START_REF] Latecki | Well-composed sets[END_REF] developed the first gray-level well-composed interpolation method in 2D. Starting with the same image expansion as the one used for his binary interpolation, the new pixels are valued based on bilinear interpolation: a pixel added between 2 primary pixels is valued at the mean of these two pixels, and at the center of a square of primary pixel, the new pixel is set a the mean of the values of these 4 pixels if the restriction of the image to these four pixels is well-composed, and at the median of these same values otherwise. This last method has been slightly modified by Géraud et al. [START_REF] Géraud | Selfduality and digital topology: links between the morphological tree of shapes and wellcomposed gray-level images[END_REF] in 2015 where the new pixels added at the center of a square of 4 pixels is systematically the median of these four primary pixels, since the median is always the good solution in 2D to make an image well-composed. This method does not create any extrema. We can notice that these graylevel interpolation methods are self-dual in the sense that they do not overemphasize bright components over the dark ones, nor the converse. The counterpart of this powerful property is that the initial images having a integerbased value space, the value space of the new images is Z/4 for Latecki's method and Z/2 for the method of Géraud et al..

In addition, Mazo et al. [START_REF] Mazo | Digital imaging: A unified topological framework[END_REF] developed a method able to interpolate any image in n-D into a well-composed one, based on the connectivity function where ε = 1 corresponds to the max interpolation and ε = -1 corresponds to the min interpolation. Even if this method is initially made for binary images defined on Khalimsky grids, its extension to Z n and to gray level images is well known and frequently used. However this method is not self-dual, contrary to the one we are going to present in this paper.

In [START_REF] Boutry | On making n-D images well-composed by a selfdual local interpolation[END_REF], it has been suggested that the "ideal" well-composed interpolation I : u → I(u) of the gray-level image u into the gray-level image I(u) would be the one which verifies the following set of properties: Fig. 1: A counter-example proving that a self-dual interpolation satisfying the usual constraints (including locality) cannot ensure digital well-composedness [START_REF] Boutry | On making n-D images well-composed by a selfdual local interpolation[END_REF] in 3D and beyond. We finally obtain that the value at the center of the cube must be greater than or equal to 3 and lower than or equal to 1, which is impossible.

                       I is invariant by translations, I is invariant by π 2 rotations, I is invariant by axial symmetries, I is local, I is ordered, I is self-dual, I is an in-between interpolation, I(u) is digitally well-composed, ∀u.
where locality means that the interpolation is ordered and that the values at the secondary (new) pixels depend only on the nearest primary (old) pixels, orderedness means that the interpolation is local and first sets the values at the corners, then at the centers of the edges, then at the centers of the faces, and so on, in-betweeness means that the values of u at the centers of the edges are between the values of u at the extremities of the edges, that the values of u at the centers of the faces are between the values of u at the centers of its edges, and so on, self-duality formally means that for any image u,

I(-u) = -I(u),
that is, dark components are treated in the same way as bright components.

However, it has been shown in [START_REF] Boutry | On making n-D images well-composed by a selfdual local interpolation[END_REF] that such an interpolation does not exist, as depicted in Figure 1. Indeed, we can show that a local (ordered) interpolation will set the values of the new function at the corners of the cube (the green values), then it will use the mean function (since we want to be self-dual) on the extremities of the edge to set the values of the interpolation at the centers of these edges (which leads to the blue values). After that, since each face of the cube draws a "critical configuration" (observing the green values at its corners), the only possible values (drawn in red) at the centers of these squares will be the median of the values at the corners of the squares. Finally, the constraints such that the interpolation is in-between and DWC will lead to two incompatible inequations for the value m ∈ R of the interpolation at the center of the cube: m ≥ 3 and m ≤ 1. In other words, no self-dual local interpolation can ensure that the output image is always DWC as soon as n ≥ 3.

For this reason, a new interpolation, this times non-local and then not ordered, has been proposed in n-D in [START_REF] Boutry | How to make n-D functions digitally well-composed in a self-dual way[END_REF]. This interpolation is digitally well-composed and in-between (the proofs are provided herafter) and self-dual (the proof will be provided in another paper). Now, let us present the theoretical background relative to DWCness.

Theoretical background

After having recalled some basics in matter of n-dimensional digital topology [START_REF] Boutry | On making n-D images well-composed by a selfdual local interpolation[END_REF][START_REF] Boutry | How to make n-D functions digitally well-composed in a self-dual way[END_REF][START_REF] Kong | Digital topology: Introduction and survey[END_REF][START_REF] Rosenfeld | Digital topology[END_REF] in Z n , we recall the formal definition of n-D DWCness introduced first in [START_REF] Boutry | How to make n-D functions digitally well-composed in a self-dual way[END_REF] and some of its properties.

Basics of digital topology in Z n

For the moment, we will only work with digital sets, that is, subsets of Z n which are finite or whose complement in Z n is finite.

Let n ≥ 2 be a (finite) integer called the dimension. Now, let B = {e 1 , . . . , e n } be the (orthonormal) canonical basis of Z n . We use the notation x i , where i belongs to 1, n , to determine the i th coordinate of the vector x ∈ Z n . We recall that the L 1 -norm of a point x ∈ Z n is denoted by . For a given point x ∈ Z n , the 2n-neighborhood in Z n is noted N 2n (x) and is equal to {y ∈ Z n ; x -y 1 ≤ 1}, and the (3

n -1)- neighborhood in Z n is noted N 3 n -1 (x) and is equal to {y ∈ Z n ; x -y ∞ ≤ 1}. Let ξ be a value in {2n, 3 n -1}. The starred ξ- neighborhood of x ∈ Z n is noted N * ξ (x) and is equal to N ξ (x) \ {x}. An element of the starred ξ-neighborhood of x ∈ Z n is called a ξ-neighbor of x in Z n . Two points x, y ∈ X ⊂ Z n such that x ∈ N * ξ (y) or equivalently y ∈ N * ξ (x)
are said to be ξ-adjacent in X. Let x, y be two points in Z n and X be a subset of Z n . A finite sequence (p 0 , . . . , p k ) in X is a ξ-path in X when p 0 is ξ-adjacent only to p 1 in X, p k is ξ-adjacent only to p k-1 in X, and for any i ∈ 1, k -1 , p i is ξ-adjacent to p i-1 and to p i+1 only in X. Such paths are said to be of length k. A digital set X ⊂ Z n is said ξ-connected if for any pair of points x, y ∈ X, there exists a ξ-path joining them in X. A subset C of X which is ξ-connected and which is maximal in the inclusion sense, that is, there is no ξ-connected subset Y of X which is greater than C, is said to be a ξ-component of X.

n-D DWCness

In this subsection, we recall the notion of digital well-composedness for sets in Z n , that we call in this way because it is based on patterns called "k-dimensional critical configurations", k ∈ 2, n , and these patterns can only occur in subsets of Z n . So let us introduce the basic mathematical background which will allow us to generalize the notion of well-composedness based on critical configurations to dimension n ≥ 2. As usual, B = {e 1 , . . . , e n } is the canonical basis of Z n . Definition 1 Given a point z ∈ Z n and a family of vector F = (f 1 , . . . , f k ) ⊆ B, we define the block S(z, F) associated to the couple (z, F) such as:

   z + i∈ 1,k λ i f i λ i ∈ {0, 1}, ∀i ∈ 1, k    .
A subset S ⊂ Z n is called a block if there exists a couple (z, F) ∈ Z n × P(B) such that S = S(z, F). Note that a block which is associated to a family F ∈ P(B) of cardinality k ∈ 0, n is said to be of dimension k, what will be denoted by dim(S) = k. Figure 2 shows 2D, 3D and 4D blocks. We will denote the set of blocks of Z n by B(Z n ).

Using this notion of blocks, we can define antagonists. Two points p, q belonging to a block S ∈ B(Z n ) are said to be antagonists in S if their distance equals the maximal distance using the L 1 norm between two points into S. In other words, two points p and q in Z n are antagonists in S ∈ B(Z n ) if p, q ∈ S are such that: and in this case we write that q = antag S (p) or equivalently p = antag S (q). The antagonist of a point p in a block S ∈ B(Z n ) containing p exists and is unique. Sometimes we will use the notation S(p, q) where p, q ∈ Z n are (3 n -1)-neighbors or equal to indicate the block in B(Z n ) such that p and q are antagonists in this block.

p -q 1 = max{ x -y 1 ; x, y ∈ S},
In addition, two points which are antagonists in a block of dimension k ∈ 0, n are said k-antagonists. In this case, k of their coordinates differ, and they differ from a value 1, their other coordinates being equal. Two points which are 0-antagonists are equal, two points which are 1-antagonists are 2n-neighbors in Z n , and two points which are k-antagonists, k ∈ 0, n , in a block S ∈ B(Z n ) are (3 n -1)neighbors in Z n or equal. See Figure 3 for different possible pairs of antagonists (in white) in a 4D space. Now, we are able to define critical configurations of dimension k ∈ 2, n in a n-D space: Definition 2 Let X ⊂ Z n be a digital set, and let S ∈ B(Z n ) be a block of dimension k ∈ 2, n . We say that X contains a primary critical configuration of dimension k in the block S if X ∩ S = {p, p } with p, p ∈ S two points that are antagonists into S. We say that X contains a secondary critical configuration of dimension k in the block S if X ∩ S = S \ {p, p } with p, p ∈ S two points that are antagonists into S. A critical configuration of dimension k ∈ 2, n is either a primary or a secondary critical configuration of dimension k. There comes our definition of digitally wellcomposed sets: Definition 3 A digital set X ⊂ Z n is said digitally well-composed or DWC if it does not contain any critical configuration, that is, for any block S ∈ B(Z n ), the restriction X ∩ S is neither a primary nor a secondary critical configuration. Obviously, this definition is self-dual, since a set X ⊂ Z n contains a primary (respectively a secondary) critical configuration in the block S ∈ B(Z n ) iff its complement X c contains a secondary (respectively a primary) critical configuration in this same block S.

Digitally well-composed gray-level n-D images

Let us now recall the definition of well-composed (gray-level) images. Let u : D → Z be a gray-level image, that is, a mapping from a domain D ⊆ Z n to a totally ordered set (like R, Z, or Z/2). Let λ ∈ R be a given threshold, then the following sets are called the threshold sets [START_REF] Bertrand | Topological approach to image segmentation[END_REF][START_REF] Bertrand | Image segmentation through operators based on topology[END_REF][START_REF] Beucher | The morphological approach to segmentation: the watershed transformation[END_REF][START_REF] Meyer | Skeletons and perceptual graphs[END_REF] of u:

[u ≥ λ] = {x ∈ D ; u(x) ≥ λ}, [u > λ] = {x ∈ D ; u(x) > λ}, [u ≤ λ] = {x ∈ D ; u(x) ≤ λ}, [u < λ] = {x ∈ D ; u(x) < λ}.
They are respectively called the large upper, the strict upper, the large lower, and the strict lower threshold sets of u. Definition 4 A gray-level image u : D → Z is said digitally well-composed (DWC) if all its threshold sets are digitally well-composed.

DWCness for interval-valued maps

We have seen what means digital well-composedness for single-valued maps, that is, maps such that for a point p belonging to their domain D, the value at p is a real value. However, as seen in [START_REF] Aubin | Set-valued analysis[END_REF], which introduces set-valued analysis, we can define set-valued maps, that is, maps such that for a point p belonging to their domain D, the value at p is a subset of some value space V. We will be particularly interested in interval-valued maps, a class of setvalued maps such that the value at each point of the domain is an interval [a, b] ∩ V. But let us recall these definitions more formally. We call value space a subset of R which is isomorphic to Z. We call interval in a value space V any set which can be written a value space V is denoted by I V . An intervalvalued map [START_REF] Boutry | How to make n-D functions digitally well-composed in a self-dual way[END_REF] is a map U : D → I V (shortly written U : D V) such that for any p ∈ D, U (p) is an interval in the value space V. Now that we have defined interval-valued maps, we can define their threshold sets [START_REF] Boutry | How to make n-D functions digitally well-composed in a self-dual way[END_REF] (see Figures 7 and8).

[1,3] [2,4] [1,3] [4,5] [3,6] [4,5] [1,3] [2,4] [1,3] U [U 7] [U 6] [U 3] [U 5] [U 4]
Definition 5 For a given interval-valued map U : D ⊆ Z n V, we define for any λ ∈ V respectively the large upper, the strict upper, the strict lower, the large lower threshold sets as well:

[U λ] = { z ∈ D ∃ v ∈ U (z), v ≥ λ }, [U λ] = { z ∈ D ∀ v ∈ U (z), v > λ }, .[U λ] = { z ∈ D ∀ v ∈ U (z), v < λ }, [U λ] = { z ∈ D ∃ v ∈ U (z), v ≤ λ }. Definition 6 An n-D interval-valued map U : D ⊆ Z n V is said digitally well-composed u U (u , R) T (u ) T (u)

Origin of the FPA

The front propagation algorithm studied in the next subsection is related to the algorithm proposed in [START_REF] Crozet | A first parallel algorithm to compute the morphological tree of shapes of n-D images[END_REF][START_REF] Géraud | A quasi-linear algorithm to compute the tree of shapes of n-D images[END_REF], which computes in quasilinear time the morphological tree of shapes [START_REF] Caselles | Geometric description of images as topographic maps[END_REF] of a n-D image. Schematically, the tree of shapes computation algorithm is composed of 4 steps as depicted in Figure 9. The input is an integer-valued image u, defined on the n-D cubical grid. First an immersion step creates an interval-valued map U , defined on a larger space K. A front propagation step, based on a hierarchical queue, takes U and produces two outputs: an image u and an array R containing the elements of K. In this array, the elements are sorted so that the next step, an union-find-based tree computation, produces T (u ) the tree of shapes of u . Actually u Z n = u and T (u )

Z n = T (u). The last step, the emersion, removes from T (u ) all the elements of K \Z n , and also performs a canonicalization of the tree. So T (u), the tree of shapes of u, is obtained [START_REF] Géraud | A quasi-linear algorithm to compute the tree of shapes of n-D images[END_REF].

The front propagation step (highlighted in red in the schematic description) acts as a flattening of an interval-valued map U into a func-Algorithm 1: Handling of a hierarchical queue is ensured thanks to priority push and priority pop.

priority push(Q, h, U, )

/* modifies Q */ begin [lower , upper ] ← U (h) if lower > then ← lower else if upper < then ← upper else ← push(Q[ ], h) priority pop(Q, ) : h /* modifies Q, and sometimes */ begin if Q[ ] is empty then ← level next to such as Q[ ] is not empty ← return pop(Q[ ])
tion u , because we have:

∀ z, u (z) ∈ U (z).
In the following, we will denote by FP both the front propagation algorithm (the part highlighted in red in Figure 9) and the mathematical operator FP : U → u .

Last, let us give two important remarks. 1. We are going to reuse the front propagation algorithm FP, yet in a very different way than it is used in the tree of shapes computation algorithm. Indeed, its input U will be different (both the structure and the values of U will be different), and its purpose also will be different (flattening versus sorting). 2. Actually, the front propagation algorithm is just a part of the solution that we present to make n-D functions digitally well-composed.

Front-propagation algorithm

Let us now explain shortly the FP algorithm, which is recalled in Algorithm 2. The basic procedures used to handle the hierarchical queue are recalled in Algorithm 1 . The reader can also refer to [START_REF] Géraud | A quasi-linear algorithm to compute the tree of shapes of n-D images[END_REF] for the original version. This algorithm uses a classical front propagation on the definition domain of U . This propagation is based on a hierarchical queue, denoted by Q and the current (queue) level is denoted by . There are two notable differences with the well-known hierarchical-queue-based Algorithm 2: Computation of the function u from an interval-valued map U defined on Z n , s ∈ N * .

FP(U ) : Image ;

/* computes u */ ; begin for all h ∈ Z n do deja vu(h) ← false;

push(Q[ ∞ ], p ∞ ); deja vu(p ∞ ) ← true; ← ∞ /* start from root level */ ; while Q is not empty do h ← priority pop(Q, ); u (h) ← ; for all n ∈ N 2n (h) such as deja vu(n) = false do priority push(Q, n, U, ); deja vu(n) ← true; return u
propagation. First the values of U are intervalvalued so we have to decide at which (singlevalued) level to enqueue the domain points.

The solution is to enqueue a point h at the value of the interval U (h) that is the closest to (see the procedure priority push).

The image u actually stores the enqueuing level of the points. Second, when the queue at the current level, Q[ ], is empty (and when the hierarchical queue Q is not yet empty), we shall decide what is the next current level.

We have the choice of taking the next level, either less or greater than , such that the queue at that level is not empty (see the procedure priority pop). Practically, choosing going up or down the levels does not change the resulting image u . The neighborhood N 2n used by the propagation corresponds to the 2n-connectivity into Z n (but can easily be adapted to any cubical grid).

Like in [START_REF] Géraud | A quasi-linear algorithm to compute the tree of shapes of n-D images[END_REF], the initialization of the front propagation relies on the definition of a point, p ∞ (first point enqueued), and of a value ∞ ∈ U (p ∞ ),1 which is the initial value of the current level . Similarly to the case of the tree of shapes computation, p ∞ is taken in the outer boundary of the definition domain of U . The initial level ∞ is set at the median value of the points belonging to the inner boundary of the definition domain of U ; more precisely, when the interval-valued U is constructed from an integer-valued function u, ∞ is computed from the values of the inner boundary of u. Using the median operator ensures that ∞ is set in a self-dual way (the value ∞ chosen for an image u will be the opposite of the value ∞ chosen for -u). Note that a first example of propagation will be given hereafter to explain how works the flattening process step-by-step.

Let us now illustrate this algorithm on a simple run, depicted in Figure 10. The initial interval-valued image U is displayed in (i). Squares filled in gray indicate the points that have already been processed at previous iterations. A circle filled in orange indicates the point h being processed, and the value displayed in the circle is the current level ; it means that we have just executed the line " u (h) ← " of the algorithm. A dashed circle filled in green, say at a point p, indicates that this point is in the hierarchical queue Q; the value displayed in this circle, say v, is the queue level of this point, i.e., we have p

∈ Q[v].
When no symbol is displayed at a point, it means that this point is not yet processed and is not in Q; we then depict its value in U .

The input interval-valued image U is shown in (i). In the following, the point coordinates are (row , column); for instance we have U (2, 1) = U (2, 3) = [START_REF] Beucher | The morphological approach to segmentation: the watershed transformation[END_REF][START_REF] Boutry | A study of well-composedness in n-D[END_REF]. The initialization step is depicted by (ii). We assume that we have p ∞ = (1, 1) and ∞ = 2. The initialization thus adds p ∞ in Q [START_REF] Bertrand | Topological approach to image segmentation[END_REF], and sets ← ∞ , so the current level is 2. The first iteration of the 'while' loop is depicted by (iii). It pops the point h = (1, 1), and performs the assignment u (h) ← , precisely u (1, 1) ← 2. It then pushes its neighboring points (1, 2) and (2, 1) into Q, respectively with level 2 and 4. Indeed, we have U (1, 2) = [START_REF] Bertrand | Topological approach to image segmentation[END_REF][START_REF] Beucher | The morphological approach to segmentation: the watershed transformation[END_REF] and U (2, 1) = [START_REF] Beucher | The morphological approach to segmentation: the watershed transformation[END_REF][START_REF] Boutry | A study of well-composedness in n-D[END_REF] so priority push respectively chooses in these intervals the levels that are the closest to the current level = 2. The second iteration is depicted by (iv). Since the queue Q[ ] is not empty, the current level does not change, and [START_REF] Bertrand | Image segmentation through operators based on topology[END_REF][START_REF] Boutry | On making n-D images well-composed by a selfdual local interpolation[END_REF]. The third iteration is depicted by (v), popping (1, 3) from Q [START_REF] Bertrand | Topological approach to image segmentation[END_REF] (the current level does not change), and pushing [START_REF] Bertrand | Topological approach to image segmentation[END_REF][START_REF] Bertrand | Image segmentation through operators based on topology[END_REF] in Q [START_REF] Beucher | The morphological approach to segmentation: the watershed transformation[END_REF] since U (2, 3) = [START_REF] Beucher | The morphological approach to segmentation: the watershed transformation[END_REF][START_REF] Boutry | A study of well-composedness in n-D[END_REF]. For the fourth iteration, depicted by (vi), the current level is = 2, and the queue corre- sponding to the current level, namely Q [START_REF] Bertrand | Topological approach to image segmentation[END_REF], is empty. Indeed, the hierarchical queue is only composed of Q[3] ∪ Q [START_REF] Beucher | The morphological approach to segmentation: the watershed transformation[END_REF]; the four points depicted with circles in (vi) only contains the values 3 and 4. The procedure priority pop thus changes the current level to the closest level whose queue is not empty, so

the point h = (1, 2) is popped. u (h) ← is performed; precisely u ((1, 2)) ← 2. Then the points (1, 3) and (2, 2) are pushed respectively in Q[2] and Q[3] since = 2, U (1, 3) = [1, 3] = {1, 2, 3}, and U (2, 2) =
[1,3] [1,3] [1,3] [1,3] [2,4] [2,4] [4,5] [4,5] [3,6] 2 [1,3] [1,3] [1,3] 2 [2,4] 4 [4,5] [3,6] 2 [1,3] [1,3] 2 2 [2,4] 4 [4,5] 3 2 [1,3] [1,3] [1,3] [2,4] [2,4] [4,5] [4,5] [3,6] 2 [1,3] [1,3] 2 2 [2,4] 4 4 3 2 [1,3] [1,3]
(i) (ii) (iii) (iv) (v) (vi) (vii) (viii) (ix) (x) (xi) (xii)
← 3. The point h = (2, 2) is then popped from Q[3], the assignment u (2, 2) ← 3 is performed, and the neighbor point (3, 2) of h is pushed in Q[3] since U (3, 2) = [2, 4] = {2, 3, 4}.
The following iterations, depicted by the sub-figures (vii) to (xi), lead to the final integer-valued image u , depicted by (xii). This resulting image is such as:

∀ z ∈ D, u (z) ∈ U (z).
This front propagation algorithm thus flattens an interval-valued map U into the integer-valued image u = FP(U ).

Indeed, if we consider that orderedness and locality are not so necessary, we can use a front-propagation algorithm (FPA); in this case, our approach is then non-local.

So, let us proceed in two steps. First, we make the input image u depicted in Figure 11 "continuous" by using the span-based interpolation (detailed later); the values of the new image are not single values but intervals, as depicted in Figure 12. We call this new map the interval-valued interpolation U .

step 1 ♭ u 0 step 2 ♭ u 1 step 3 ♭ u 2 step 4 ♭ u 3
Fig. 13: Flattening process.

Then, we use the FPA to "flatten" this function into a third map u , which is then single-valued. Moreover, this new map u will have new topological properties thanks to the "regularization" properties of the FPA. The whole process is developed later.

We depicted the details of the flattening process in Figure 13: starting from the intervalvalued interpolation U , we add a border that we consider as being the initial front (for this reason, we depict it using green points), to ensure that the propagation starts from the contour. Then we propagate the front deeper and deeper in the image until the front, made of the green points, covers the whole domain of U . The new image is called u because it corresponds to U which has been flattened. Then, we remove the temporary border (see Figure 14) to obtain an interpolation which is "smoother" than the original image u. Applying this algorithm in n-D, n ≥ 2, leads to digitally well-composed images, as we will prove later.

Prerequisites relative to in-betweeness

In this subsection, we first recall basics in matter of digital topology coming from [START_REF] Boutry | On making n-D images well-composed by a selfdual local interpolation[END_REF] and that we will use to define in-betweeness.

A block of Z n can be subdivided into blocks of (Z/2) n (see Figure 15), where s belongs to N * , using the following procedure:

Definition 8 Let S ∈ B(Z n ) be a block of di- mension k ≥ 0 associated to a point z ∈ Z n
and the family of vectors F = (f 1 , . . . , f k ) ⊆ B associated to S. Then the cubical subdivision of S is denoted by Subd(S) and is equal to:

   z + i∈ 1,k λ i f i ; ∀i ∈ 1, k , λ i ∈ 0, 1 2 , 1    .
Let us define now the cubical subdivision of a domain: Definition 9 Let D ⊆ Z n be a bounded hyperrectangle. Then the cubical subdivision of Fig. 16: Computation of the direct parents in 1D and in 2D (extracted from [START_REF] Boutry | On making n-D images well-composed by a selfdual local interpolation[END_REF]).

this domain is the union of the subdivision of the blocks of Z n that are subset of this domain:

Subd(D) = S∈B(D) Subd(S). Obviously, Subd(D) ⊆ (Z/2) n .
For that, let us define the mapping o : This way, we can define the binary relation

R : Z 2 n × Z 2 n → {0, 1} such that p, q ∈ Z 2 n verify pRq which is said "p is parent of q" if o(p) ≤ o(q) and p -q ∞ ≤ 1/2. The pair ( Z 2 n , R) which represents Z 2 n supplied
with the order relation R is called a partial order or poset. In addition, a point p ∈ Z 2 n is said to be a direct parent of q ∈ Z 2 n if pRq, p = q, and there exists no point into Z

1 2 (z) = i ∈ 1, n ; z i ∈ Z 2 \ Z .
This notation, even if looking much simple, will be very useful in the sequel, because it permits to classify the points of Z

E k = z ∈ Z 2 n ; Card 1 2 (z) = k .
Then, we can remark that for any point z

∈ Z 2 n , the value k such that z ∈ E k is equal to o(z). Note that {E k } k∈ 0,n represents a par- tition of Z 2 n .
The sets of direct parents can then be defined very easily: Fig. 17: The computation of the ancestors of the center of a 1D block (edge) and of the ancestors of a 2D block (square) (extracted from [START_REF] Boutry | On making n-D images well-composed by a selfdual local interpolation[END_REF]).

0 0 1 1 1 1 1 2 0 0 0 0
Fig. 18: The computation of a group of the center of a 1D block (edge) and of the center of 2D block (square) (extracted from [START_REF] Boutry | On making n-D images well-composed by a selfdual local interpolation[END_REF]).

Proposition 1 Let z be an element of Z 2 n \ Z n . The set of direct parents (see Figure 16) of z is denoted by P(z) and equal to:

P(z) := i∈ 1 2 (z) z + e i 2 , z - e i 2 .
Definition 12 With z an element of Z The set of the ancestors of p (see Figure 17) is denoted by A(p) and is defined such that:

A(p) = P o(z) (z). Note that A(p) is a subset of Z n . Definition 14 Let z be an element of Z 2 n .
The group of p (see Figure 18) denoted by G(p) is defined such that: Z n . The set of opposites (see Figure 19) relatively to z is the set of paired points:

G(p) = k∈ 0,o(z) P k (z),
opp(z) = i∈ 1 2 (z) z - e i 2 , z + e i 2 .
Let a, b, z be three points of Z 2 n , we say that a is opposite to b relatively to z if {a, b} ∈ opp(z).

In the sequel we will use these notations:

Im(A,D,V) := {u : D ⊆ A → V ; D given} , Im(A,V) := {u ∈ Im(A,D,V) s.t. D ⊆ A} ,
where V is the space value, A is the ambient space, and D is the domain.

Definition 16 Let u ∈ Im(Z n , D, R) be a given image with D a bounded hyperrectangle. We call cubical interpolation of u any image

u : Subd(D) ⊆ Z 2 n → R
such that its restriction to D is equal to u.

Definition 17 An interpolation operator I :

Im(Z n , R) → Im( Z 2 n , R) is said to be a cu- bical interpolation method if for any image u ∈ Im(Z n , R) defined on a bounded hyper- rectangle D ⊆ Z n , I(u) : Subd(D) → R is a cubical interpolation of u.
The formal definition of an in-between interpolation will come later in the new materials relative to DWCness (see page 20) and will need the preceding definitions.

Definition 18 A cubical interpolation I from Im(Z n , R) to Im( Z 2 n , R) is said to be digi- tally well-composed (DWC) when for any u ∈ Im(Z n , R), then I(u) is DWC. With B = {-1 2 , 0, 1 2 } n
, where B z is the translation of B by z, and with "op" an operator on (finite) subsets of R, we define the following interpolation: Definition 19 Let u : D → R with D a bounded hyperrectangle in Z n . We define the operator-based interpolation:

I op (u) : D = Subd(D) → R such that, for any z ∈ D , (I op (u)) (z) := op{ u(z) } if z ∈ D, op{ u(z ), z ∈ B z ∩ D } otherwise.
This interpolation is local since it is computed at each point p ∈ D using only the nearest neighbors of p in Z

New material relative to DWCness

Let us start to present our new results, that is, the proofs of a part of the assertions presented in [START_REF] Boutry | How to make n-D functions digitally well-composed in a self-dual way[END_REF] and in [START_REF] Boutry | How to make images well-composed in n-D without interpolation[END_REF].

Reformulating DWCness with 2n-paths

We can reformulate digital well-composedness based on 2n-paths as asserted in [START_REF] Boutry | How to make n-D functions digitally well-composed in a self-dual way[END_REF]. Note that the proof provided below is new material. Theorem 1 A digital set X ⊂ Z n is digitally well-composed iff, for any block S ∈ B(Z n ) and for any couple of points (p, antag S (p)) such that they belong to X ∩ S (resp. S \ X), p and antag S (p) are 2n-connected in X ∩ S (resp. in S \ X).

Proof: Let us begin by the converse implication. If X is not digitally well-composed, there exists some block S ⊂ Z n such as X ∩S is a primary or a secondary critical configuration in Z n . In the primary case, Card(X ∩ S) = 2, what contradicts that Card(X ∩ S) ≥ k + 1 due to the fact that every couple of antagonists (p, p ) in this block is connected by a 2n-path in S. In the secondary case, Card(X c ∩S) = 2, what contradicts that Card(X c ∩ S) ≥ k + 1 for the same reason.

Concerning the direct implication, let us prove firstly that for two antagonists p and p in some block S ∈ B(Z n ) of dimension k ∈ 1, n such that p, p ∈ X, there exists a 2npath in X ∩S joining them when X is digitally well-composed. Let us proceed by induction.

Initialization (k = 1): the 2n-path joining p and p into X ∩ S is simply π = (p, p ).

Heredity (k ∈ 1, n -1 ): let us assume that this property is true for every l ∈ 1, k . Now, let us assume that there exists a couple of points p and p of X such as they are antagonists in a block S ∈ B(Z n ) of dimension (k + 1). We know that X is digitally well-composed and then does not contain any primary critical configuration. Consequently, there exists one point q ∈ X ∩ S such that q = p and q = p . That means that p and q are antagonists in some block S ∈ B(Z n ) of dimension l strictly lower than k + 1, and then they are connected by a 2n-path π pq = (p, . . . , q) in X ∩ S ⊂ X ∩ S. For the same reason, q and p are connected by a 2n-path π qp = (q, . . . , p ) ⊆ X ∩ S. Consequently, by joining the two paths π pq and π qp we obtain a 2n-path π pp in X ∩ S joining p and p .

A similar reasoning will prove that the non existence of secondary critical configurations in X (and then the non existence of primary critical configurations in X c ) implies that for any couple of points (p, p ) of X c and antagonists in some block S ∈ B(Z n ), there exists some 2n-path joining them in X c ∩ S. This proof is illustrated in Figure 20: two antagonists, depicted in red in the block S (the tesseract), are assumed to belong to a digitally well-composed set X ⊂ Z n , which is shown on Subfigure (A). Since the two red points (0, 0, 0, 0) and (1, 1, 1, 1) belong to X and are 4-antagonists in S, there exists at least one more point in the block S belonging to X (in the contrary case, X contains a critical configuration, which is impossible by hypothesis). A first possibility is shown on Subfigure (B), and a second possibility is shown on Subfigure (C), where the green point depicts this additional point. Let us treat first the case corresponding to Subfigure (B): since the points (0, 0, 1, 0) and (1, 1, 1, 1) are 3-antagonists in the 3D block C depicted in yellow, there must be at least one more point in this block which belongs to X (for the same reason as before), and then we obtain that the blue point localized in (1, 0, 1, 1) belongs to X, which is shown on Subfigure (D). Applying recursively the reasoning until X does not contain any critical configuration, we obtain that the point (1, 0, 1, 0) also belongs to X, which is shown in purple on Subfigure (F ). Finally, we obtain a 2n-path joining the two red points (0, 0, 0, 0) to (1, 1, 1, 1) into X ∩S. Let us now treat the case corresponding to Subfigure (C): if (0, 0, 0, 0) and (0, 0, 1, 1), which are 2-antagonists, are the only points of X in the block A, X ∩ A is a critical configuration, then there exists an ad-ditional point among (0, 0, 1, 0) and (0, 0, 0, 1) which belongs to X. The same thing happens in the block B where at least (0, 0, 1, 1) and (1, 1, 1, 1) belongs to X: at least (0, 1, 1, 1) or (1, 0, 1, 1) must belong to X. Let us assume that (0, 0, 0, 1) and (0, 1, 1, 1) belong to X, we obtain Subfigure (E) where a 2n-path joins the two red points (0, 0, 0, 0) to (1, 1, 1, 1) in X ∩S. Obviously, the reasoning is similar when (0, 0, 0, 0) and (1, 1, 1, 1) belong to X c . In this case, we obtain that a 2n-path joins these two points in X c ∩ S, thanks to self-duality of digital well-composedness.

Characterizing DWC gray-level n-D images on bounded hyperrectangles

Now let us recall that we can characterize [START_REF] Boutry | How to make images well-composed in n-D without interpolation[END_REF] gray-level DWC images defined on bounded hyperrectangles; for that, let us introduce our definition of such domains.

A set

I d that can be written [m, M ] ∩ V where V ⊂ R is countable and where m, M ∈ V verify m ≤ M is called a discrete interval.
The values m and M are then called the lower bound and the upper bound of I d respectively. Now, assuming that a sequence of discrete intervals ([m i , M i ] ∩ V i ) i∈ 1,n is given, we define the bounded hyperrectangle associated to this sequence of intervals as the Cartesian product of these discrete intervals:

i∈ 1,n [m i , M i ] ∩ V i .
When for each i ∈ 1, n , V i is equal to the same set Z, we call this set a bounded hyperrectangle in Z n . Now let us show that in the case of a graylevel image defined on a bounded hyperrectangle, we are able to detect the digital well-composedness of this image only using the upper (respectively lower) threshold sets, as proven using the following lemmas.

ε = min{|u(p)-u(q)| p, q ∈ D, u(p) = u(q)}.
Since Card (D) < +∞, ε > 0. Now, let us proceed in two steps.

Firstly, we can observe that for any λ ∈ R, every threshold set [u < λ] can be rewritten [u ≤ f (λ)] with f : R → R defined such that:

f (λ) = λ -ε/2 if λ ∈ V(u), λ otherwise.
That means that every threshold set [u < λ] is equal to [u ≤ λ ] for some λ ∈ R.

Secondly, we can observe that every threshold set [u ≥ λ] can be rewritten [u > f (λ)] using this same function f . That means that every threshold set

[u ≥ λ] is equal to [u > λ ] for some λ ∈ R.
Finally, all the threshold sets [u ≤ λ] and [u > λ] are digitally well-composed, then u is digitally well-composed. The reasoning is dual for the proposition in brackets.

We have previously defined blocks of Z n . The extension to blocks of a domain D ⊆ Z n is straightforward. For a given domain D ⊂ Z n , the set of blocks of D is denoted B(D) and is such that:

B(D) := {S ∈ B(Z n ) ; S ⊆ D} .
Lemma 2 Let n ≥ 2 be an integer, and let H be a bounded hyperrectangle in Z n . Let X and Y be two sets of Z n such as:

X ∩ Y = ∅ and X ∪ Y = H (i.e., (X, Y ) is a partition of H). Then, X is digitally well-composed iff Y is digitally well-composed.
Proof: Let us assume that X contains a primary critical configuration. It means that there exists some block S ∈ B(H) such that X ∩ S = {p, p } with p and p antagonists in S. Because X and Y are complementary in H, X ∩S and Y ∩S are complementary in S ⊆ H. The consequence is that Y ∩S = S\{p, p }, i.e., Y contains a secondary critical configuration in S. So, we have proven that X contains a primary critical configuration iff Y contains a secondary critical configuration. That finally means that X is digitally well-composed iff Y is digitally well-composed.

Lemma 3 Let n ≥ 2 be an integer, and let H be a bounded hyperrectangle. Let u : H → R be a gray-level image. Then, u is digitally wellcomposed iff for any λ ∈ R the threshold set [u ≤ λ] is digitally well-composed (or equivalently iff for any λ ∈ R the threshold set [u ≥ λ] is digitally well-composed).

Proof: Using Lemma 1, we know that u is digitally well-composed iff for any λ ∈ R, [u ≤ λ] and [u > λ] are digitally well-composed. Furthermore, using Lemma 2, and because

[u ≤ λ] ∩ [u > λ] = ∅ and [u ≤ λ] ∪ [u > λ] = H (with H a bounded hyperrectangle), we know that [u ≤ λ] is digitally well-compo- sed iff [u > λ] is digitally well-composed. We can conclude that u is digitally well-composed iff [u ≤ λ] is digitally well-composed.
Like exposed in [START_REF] Boutry | How to make n-D functions digitally well-composed in a self-dual way[END_REF], there exists a characterization for gray-level digitally well-composed images defined on bounded hyperrectangles. It is the natural extension of the characterization of Latecki for 2D images in [START_REF] Latecki | Well-composed sets[END_REF]. Let us recall that for two reals a, b, the interval value intvl(a, b) of the pair (a, b) is equal to: In both cases, u is obviously not digitally wellcomposed. Conversely, if there exists a value λ ∈ R such that [u ≥ λ] contains a critical configuration in a block S ∈ B(D), either [u ≥ λ] ∩ S is a primary critical configuration (1), or it is a secondary critical configuration (2). In case (1), there exists p, p ∈ S such that p = antag S (p) and [u ≥ λ] ∩ S = {p, p }, which means that min{u(p), u(p )} ≥ λ, and in parallel we have [u < λ] ∩ S = S , which means that max{ u(p ) p ∈ S } < λ, and then the intersection we are looking for is empty. In case (2), we can proceed to a dual reasoning to obtain the same result. This concludes the proof.

Practically, this characterization means that for a given and finite dimension n ≥ 2, we can easily check if an image defined on a domain D is digitally well-composed with an algorithm [START_REF] Boutry | A study of well-composedness in n-D[END_REF]. Furthermore, the complexity of this algorithm is for a fixed dimension in linear time relatively to the number of blocks in the domain D, which means that it is very fast for small dimensions.

Characterizing DWC interval-valued maps

Now, let us show how we can characterize interval-valued maps seen before.

Proposition 4 An n-D interval-valued map U : D ⊆ Z n
V defined on a bounded hyperrectangle D is digitally well-composed iff both U : D → V and U : D → V are digitally well-composed.

Proof: Indeed, for any λ ∈ V, we have the remarkable equalities:

             [U λ] = [ U > λ], (1) [U λ] = [ U < λ], (2) [U λ] = [ U ≥ λ], (3) [U λ] = [ U ≤ λ]. (4)
This way, if U is digitally well-composed, then for any λ ∈ V, [U λ] and [U λ] are digitally well-composed, and then by ( 3) and ( 4), U and U are digitally well-composed by Lemma 3. Conversely, if both U and U are digitally well-composed, then for any λ ∈ V,

[ U > λ], [ U < λ], [ U ≥ λ],
and [ U ≤ λ] are digitally well-composed and then by ( 1) to (4), U is digitally well-composed.

Extending topological notions from Z n to (Z/2) n

The topological notions that have been presented before can be naturally extended from Z n to (Z/2) n .

For example, a digital set is a subset X of (Z/2) n such that X or X c := (Z/2) n \ X is finite. In addition, two points p, q ∈ (Z/2) n are said to be 2n-neighbours respectively (3 n -1)neighbors) in (Z/2) n if ||p-q|| 1 = 1/2 (respectively if ||p-q|| ∞ = 1/2), the 2n-neighborhood (respectively the (3 n -1)-neighborhood) of a point p ∈ (Z/2) n are the sets

N 2n (p, (Z/2) n ) = {q ; ||p -q|| 1 ≤ 1/2},
and respectively

N 3 n -1 (p, (Z/2) n ) = {q ; ||p -q|| ∞ ≤ 1/2},
from which we deduce their starred versions which are respectively

N * 2n (p, (Z/2) n ) = N 2n (p, (Z/2) n ) \ {p}
and

N * 3 n -1 (p, (Z/2) n ) = N 3 n -1 (p, (Z/2) n ) \ {p}.
For ξ ∈ {2n, 3 n -1}, the ξ-connectivity and then the ξ-components are computed based on the ξ-neighborhood relationship in (Z/2) n . In the same manner, blocks in (Z/2) n are defined such that, given a point z ∈ (Z/2) n and a family of vector:

F = (f 1 , . . . , f k ) ⊆ B, the block associated to the couple (z, F) in (Z/2) n is S 2 (z, F, (Z/2) n ) equal to:    z + i∈ 1,k λ i f i λ i ∈ {0, 1/2}, ∀i ∈ 1, k    ,
and the set of blocks in (Z/2) n are denoted by B((Z/2) n ). By extension, the set of blocks of the domain D as a subset of (Z/2) n is equal to:

B(D, (Z/2) n ) := {S ∈ B((Z/2) n ) ; S ⊆ D} .
Based on this definition of block of (Z/2) n , we define that two points p, q ∈ (Z/2) n are antagonists in a block of (Z/2) n if they maximize the L 1 -distance between two points into this block. Then, let X ⊂ (Z/2) n be a digital set, and let S ∈ B((Z/2) n ) be a block of dimension k ∈ 2, n . We say that X contains a primary critical configuration of dimension k in the block S as a subset of (Z/2) n if X ∩S = {p, p } with p, p ∈ S two points that are antagonists into S. We say that X contains a secondary critical configuration of dimension k in the block S as a subset of (Z/2) n if X ∩ S = S \ {p, p } with p, p ∈ S two points that are antagonists into S. As usual, a critical configuration in (Z/2) n is either a primary or a secondary critical configuration in (Z/2) n .

A subset X of (Z/2) n is then said digitally well-composed (DWC) if it does not contain any primary or secondary critical configuration in (Z/2) n .

Formalization of our interpolation

Let us formally define the different operators used to compute our n-D interpolation.

Using the span operator on the interpolations I min (u) and I max (u), we obtain the following span-based interpolation of u that we call I Span (u), defined such that:

   I Span (u) = I min (u) I Span (u) = I max (u).
Since this interpolation is interval-valued, we say it is an immersion of u. Then, starting from I Span (u) : D ⊂ Z 2 n Z as developed above, we add an outer border to the hyperrectangle D , which becomes D + , and we define

U + : D + Z/2 such that ∀p ∈ D , U + (p) = (I Span (u))(p), and ∀p ∈ D + \ D , U (p) = { ∞ (u)}.
Then we proceed to the front propagation on U + with p ∞ belonging to the outer border of D + . We obtain the single-valued image u : D + → Z/2 from which we remove the border.

Finally, we obtain the interpolation u DWC : D → Z/2 of u.

With α ∈ R, let us denote by b α the operator which adds an outer border set at {α} to a interval-valued image defined on an hyperrectangle, and b -the operator which removes the outer border to a single-valued image defined on an hyperrectangle. We can then define our interpolation in this way:

u DWC := I DWC (u),
where

I DWC := b -• FP • b ∞ (.) • I Span .
An example of the complete process is depicted in Figure 21. We start from an image u that we interpolate using the interval-valued interpolation I Span (u) at which we add a border to obtain U + . This boundary is displayed in light gray and is filled with a single value ∞ (u), which is actually the median value of When we take U + as input to the FPA, p ∞ can be any point of its boundary. This way, which is similar to [START_REF] Géraud | A quasi-linear algorithm to compute the tree of shapes of n-D images[END_REF], we ensure that the propagation starts from the outer boundary of U + , and that all the points of the inner boundary of u are enqueued. Having ∞ (-u) = -∞ (u) guarantees that U + remains self-dual with respect to u. Then the flattening process is applied on U + and results in the image u .

Figure 22 depicts the propagation steps: we start from Subfigure (a) where p ∞ is the only point to be enqueued in

Q[ ∞ (u)] = Q[8].
Then, until Q [START_REF] Boutry | How to make n-D functions digitally well-composed in a self-dual way[END_REF] is empty, the propagation continues across the domain of the image, which contains (at least) the outer boundary, as shown on Subfigure (b) in light gray. The green pixels correspond to the points which have been enqueued during the propagation, and that are not valued yet. Then is set at 9, and the same process reiterates, until the whole domain of the image has been enqueued and valued, which results in u on Subfigure (j). (g) = 7 The final result is u DWC which corresponds to u minus its boundary.

Let us notice that in practice, we will have an integer-valued map u whose values are defined into Z, and then its immersion U will be also defined into Z. When we add a border to the domain of U , we obtain a new function U + , which is no more defined into Z but into Z/2, since the median at which we set the border belongs to Z/2. The use of a generic library is then necessary [START_REF] Levillain | Writing reusable digital topology algorithms in a generic image processing framework[END_REF] (or we can round the value of ∞ but we can loose perfect selfduality [START_REF] Géraud | Selfduality and digital topology: links between the morphological tree of shapes and wellcomposed gray-level images[END_REF]). The consequence is that u and the final image u DWC will have their value domain equal to Z/2.

Properties of our n-D DWC interpolation

In this section, we formally define what is an in-between interpolation on cubical grids, we show that the FPA satisfies what we call an intrinsic continuity property, and we prove that our interpolation is in-between thanks to this intrinsic property. Then, we prove a second intrinsic continuity property of the FPA, we recall the two well-known DWC interpolations of Mazo et al. [START_REF] Mazo | Digital imaging: A unified topological framework[END_REF], and we deduce from these facts that our interpolation is DWC.

Definition of in-betweeness

Fig. 23: The example u is depicted on the left side with a blue frame. From left to right, some random interpolation, the min interpolation, the max interpolation, the median interpolation and finally the interpolation published in [START_REF] Boutry | How to make n-D functions digitally well-composed in a self-dual way[END_REF] and studied here.

u (p) ∈ {z -,z + }∈opp(p) intvl(u (z + ), u (z -)).
Some examples of interpolations, which are in-between or not, are depicted in Figure 23 (see hereafter).

First intrinsic property of the FPA

Two main continuity properties of the FPA are of major interest for the sequel. Both properties relate the values of the flattened image u at two pixels p and q of the domain D ⊂ (Z/2) n of U which are neighbors in (Z/2) n depending on the values U (p) and U (q). We say that these properties are intrinsic in the sense that they are a direct result of the internal Fig. 24: From tom to bottom, we can observe in red the boundaries of the upper large threshold sets of the images depicted in the figure before and corresponding to λ. The random interpolation introduces new contours and pinches, and is not in-between. Conversely, the other interpolations preserve the boundaries while they separate the level lines containing self-crossings into simple closed curves. Note that our interpolation (on the right side) behaves sometimes like a min interpolation and sometimes like a max interpolation.

functioning of the algorithm. But let us introduce first some additional notations concerning the FPA.

We define : D → R as the level map: for a given point z ∈ D , (z) ∈ R is the value of when we enqueue z into the hierarchical queue Q during the front propagation. Note that it is different from the "enqueuing level" presented just before in the algorithm. In addition, we define the enqueuing time map t : D → N such that, for any point z ∈ D , t(z) is the time at which the point z has been enqueued into Q during the front propagation. We say that a position p ∈ D is being processed while the current position h is equal to p. Obviously, for any p ∈ D , we use the notation u (p) assuming that this pixel has been valued yet by the front propagation algorithm (we recall that each pixel of u is valued only once). Now, let us expose the first intrinsic continuity property of the FPA that we will use later to prove that the interpolation method developed in this paper is in-between.

Lemma 4 Let U : D ⊆ (Z/2) n
R be an n-D interval-valued map, and let u = FP(U ) : D → R be the function resulting from the front propagation algorithm applied on U . Now, let a, m ∈ D be 2n-neighbors in (Z/2) n such that

U (a) ⊆ U (m). Then u (m) < u (a) implies that u (a) = U (a) and u (m) > u (a) im- plies that u (a) = U (a).
The proof of this lemma has been postponed in the appendix at page 26.

In-betweeness of our interpolation

Let us announce one of the most important result of the paper.

Proposition 5 Let u : D ⊂ Z n → Z be a given image. Then the image:

u DWC := I DWC (u)
is an in-between interpolation of u.

Proof: Let u : D → Z be a given image, and u DWC = I DWC (u) be its interpolation. This way, we know that ∀z ∈ D, u DWC (p) = u(p). Let us assume now that u DWC is not inbetween. Then there exists some point m ∈ Subd(D) \ D such that u DWC (m) does not belong to:

{p -,p + }∈opp(m) intvl(u DWC (p -), u DWC (p + )).
In other words, there exists two points a, b ∈ Subd(D) such as {a, b} ∈ opp(m) and:

u DWC (m) ∈ intvl(u DWC (a), u DWC (b)).
Two situations are then possible:

-either u DWC (m) < min(u DWC (a), u DWC (b)) (Case 1) -or u DWC (m) > max(u DWC (a), u DWC (b) (Case 2).
Since these two relations are dual, we will study only the first case, the reasoning being the same for the second.

By hypothesis, u DWC (m) < u DWC (a), and then: u (m) < u (a), (P 1).

In addition, we know that a and m are 2nneighbors in D (P 2). Finally, since a ∈ P(m),

U + (a) = (I Span (u))(a) ⊆ (I Span (u))(m) = U + (m) (P 3
). This way, we have the three properties of Lemma 4 and we can conclude that

u DWC (a) = u (a) = U + (a).
With the same reasoning applied to b, we obtain that u DWC (b) = U + (b), which leads to:

u DWC (m) < min( U + (a), U + (b)).

By construction,

U + (a) = min {u(p) ; p ∈ A(a)}, and

U + (b) = min {u(p) ; p ∈ A(b)}.
This implies that u (m) < min {u(p) ; p ∈ A(m)} (since A(a) ∪ A(b) = A(m)), which is equal to U + (m). However u DWC (m) < U (m) is impossible by construction. This concludes the proof.

Second intrinsic continuity property of the FPA and the Key Lemma

Now let us begin with a preliminary lemma which correlates the values of the initial interval-valued image U , the interpolation u and the map of levels : D → R. This lemma will be necessary to prove the second intrinsic continuity property detailed after.

Lemma 5 Let U : D ⊆ (Z/2) n
R be an n-D interval-valued map, and let u = FP(U ) : D → R be the function resulting from the front propagation algorithm applied on U . Now, let r be a point of D . We can observe the two following implications:

   u (r) < U (r) ⇒ (r) ≤ u (r) (1) u (r) > U (r) ⇒ (r) ≥ u (r) (2) ♭ u (p) ⌈U⌉(p) ⌊U⌋(q) λ u (q) ♭ ℓ (p) ℓ(q)
ℝ ℝ Fig. 25: A situation impossible to obtain with p, q ∈ D being 2n-neighbors.

The proof of this lemma is reported into the appendix at page 27.

There follows a lemma that we call the first intrinsic property of the FPA. Note that this is the key to understand why a digitally wellcomposed interval-valued image results in a digitally well-composed single-valued image.

Lemma 6 (The Key Lemma) Let U : D ⊆ (Z/2) n R be an n-D interval-valued map, and let u = FP(U ) : D → R be the gray-level function resulting from the front propagation algorithm applied on U . Let p, q ∈ D be two 2n-neighbors in (Z/2) n and λ ∈ R. Then, it is impossible to get the following set of properties together:

       u (p) ≤ λ, (H1) U (p) > λ, (H2) u (q) > λ, (H3) U (q) ≤ λ. (H4)
The proof of this lemma is in the appendix at page 27.

The proof of DWCness of our interpolation

Let us recall how we obtain u DWC :

u DWC = I DWC (u), with I DWC = b -• FP • b ∞(.) • I Span .
So, when computing u DWC , we start from I Span (u) which is DWC thanks to the following proposition.

Proposition 6 For any

u : D ⊂ Z n → Z, the n-D interval-valued function I Span (u) : D ⊂ Z 2 n
Z is digitally well-composed, and the interpolation operator I Span is self-dual (it verifies ∀ u, I Span (u) = -I Span (-u)).

Proof: This follows from the fact that the min interpolation I min (u) and the max interpolation I max (u) are DWC (see Proposition 2).

Then, we obtain b ∞(u) (I Span (u)), which is DWC since adding a constant border preserve DWCness. (see Proposition 7 in the appendix at page 28). Now we want to prove that

FP(b ∞(u) (I Span (u)))
is DWC. This property follows from the fact that the FPA preserves DWCness:

Theorem 2 If the n-D interval-valued map U : D ⊂ Z 2 n R, defined on a bounded hyperrectangle D , is digitally well-composed, the resulting n-D function u = FP(U ) is dig- itally well-composed.
Proof: Let us assume that u is not digitally well-composed. Then, there exists some λ ∈ R such that [u ≥ λ] contains a critical configuration of primary or secondary type. Let us begin with the primary case.

If [u ≥ λ] contains a critical configuration of primary type, that means that there exists some block S ⊆ D of dimension k (with 2 ≤ k ≤ n) such that [u ≥ λ] ∩ S = {p, p } where p and p are two antagonists in S. In other words, we have:

   u (p) ≥ λ, u (p ) ≥ λ, u (p ) < λ, ∀ p ∈ S \ {p, p }.
We know that u (p ) < λ implies that

U (p ) < λ, ∀ p ∈ S \ {p, p }.
. This way, we obtain the following relation:

max U (p ) p ∈ S \ {p, p } < λ.
Moreover, U is digitally well-composed (since U is digitally well-composed) by Proposition 4. The characterization of a digitally well-composed single-valued function implies that intvl( U (p), U (p )) intersects Span{ U (p ) p ∈ S \ {p, p }}, so there exists some p * ∈ {p, p } such that: In addition, we have:

U (p * ) < λ. u I Span (u) U +
U (p * ) ≥ λ, U (antag S (p * )) ≥ λ.
This means that these two antagonists in S belong to the set [ U ≥ λ] which is digitally well-composed. Then, there exists a 2npath connecting them into [ U ≥ λ] ∩ S. Consequently, there exists some point p * ∈ N 2n (p * ) ∩ S such that:

U (p * ) ≥ λ.
We thus end up with the four properties: u (p * ) ≥ λ, U (p * ) < λ, u (p * ) < λ, and U (p * ) ≥ λ with p * , p * 2n-neighbors in D . Thanks to Lemma 6, we obtain a contradiction. For the secondary case, a dual reasoning leads also to a contradiction.

Since removing a border of constant width preserves DWCness, we obtain finally that the image u DWC is DWC: Note that the proof of DWCness of u DWC is summarized in Figure 26.

Applications

Here we present some possible theoretical and practical applications relative to our n-D digitally well-composed interpolation.

Theoretical applications

In this subsection, we show that, thanks to DWC images, the tree of shapes does not depend on the chosen connectivity.

As described in [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 n-D images[END_REF][START_REF] Najman | Discrete set-valued continuity and interpolation[END_REF], the tree of shapes is a hierarchical representation of a graylevel images based on the connected components of its threshold sets. More formally, given an image u : D ⊆ (Z/2) n → Z and a couple of dual connectivities (c a , c b ), let us define the two following sets:

T < (u) := {Γ ∈ CC ca ([u < λ])} λ , T ≥ (u) := {Γ ∈ CC c b ([u ≥ λ])} λ .
Based on these sets and using the saturation or cavity fill-in operator Sat [START_REF] Caselles | Geometric description of images as topographic maps[END_REF], defined such that:

Sat c (Γ ) := Ω \ CC c (Ω \ Γ, p ∞ )
where Ω is the ambient space, Γ ⊆ Ω, p ∞ ∈ Ω and c is a given connectivity, we can define the upper shapes and respectively the lower shapes of u:

S < (u) := {Sat c b (Γ ) ; Γ ∈ T < (u)} , S ≥ (u) := {Sat ca (Γ ) ; Γ ∈ T ≥ (u)} .
Then, the set defined by:

S(u) := S < (u) ∪ S ≥ (u)
is called the tree of shapes of u.

We can easily understand that the tree of shapes computed with c a := c 2n and c b := c 3 n -1 will not always be the same as the one computed with c a := c 3 n -1 and c b := c 2n . In other words, the resulting tree depends on the couple of connectivities (c a , c b ).

Let us assume now that we work with a DWC gray-level image u : D → Z. DWCness implies that we do not have critical configurations (where the choice of the connectivity matters at a local point of view), it implies then that the connected components of a DWC set will not depend on the chosen connectivity neither (see Subsection 10.4 for the proof of Theorem 5 presenting this result). We call this property well-composedness based on the equivalence of connectivities [START_REF] Boutry | How to make n-D functions digitally well-composed in a self-dual way[END_REF] (EWCness). Now, there comes one of the main properties (according to us) that can be obtained thanks to n-D well-composed interpolations like the one we propose in this paper or the ones of Mazo et al. [START_REF] Mazo | Digital imaging: A unified topological framework[END_REF]:

Theorem 4 Let u be a gray-level image from a domain D to a space value V isomorphic to Z. Let D be either (Z/2) n or a bounded hyperrectangle in (Z/2) n with n ∈ N * . When u is DWC, the tree of shapes S(u) of u does not depend of the chosen connectivities.

Proof: When u is a DWC image, its threshold sets are DWC and then EWC by Theorem 5, and then the sets T < (u) and T ≥ (u) are not functions of the used connectivity. Since each component Γ of T < (u) or T ≥ (u) is DWC, the set Ω \ Γ is DWC too by self-duality of DWCness, and then it is EWC. The consequence is that the sets Sat c (Γ ) for any Γ in T < (u) or T ≥ (u) are not functions of the used connectivity c neither. Then S < (u) and S ≥ (u) do not depend on the chosen connectivity. It concludes the proof.

Practical application

An interesting application of our interpola-Fig. 27: Starting from a gray-level image (see (a)), we compote its well-composed gray-level Laplacian, then we deduce from its sign (see (b)) the labeling of the different characters (we look "inside" the zero-level-lines), and then we label the characters of the image (see (c) and (d)). This picture is extracted from [START_REF] Huynh | Morphology-based hierarchical representation with application to text segmentation in natural images[END_REF]. tion is the computation of the Laplacian of an image [START_REF] Huynh | Morphology-based hierarchical representation with application to text segmentation in natural images[END_REF] and of its zero-crossings; the zero-level-lines of the Laplacian often contain pinches since the Laplacian is a second derivation of the initial signal. Then, to get rid of these pinches, we interpolate the Laplacian using the method described in the present paper, and then the zero level-lines become simple closed curves (see Figure 27).

8 Sketch of the proof of self-duality Since the proof of the computation of the selfduality of u needs additional tools, it will be published in a future paper. In brief, the proof is in two steps. First, given a point p ∞ and a value ∞ , we have to prove the determinism of the computation of u : the choice of the next current level (when Q[ ] is empty), which can be performed either increasingly or decreasingly, does not change the final valuation of u . Then, knowing that, we can prove the self-duality.

Let us denote by nextlevel the operation that changes the current level in the case where the possible levels are in Z. It corresponds to the first line inside the if block in the routine priority pop of Algorithm 1. A simple implementation can be:

1. Choose at random a direction between increasing (∆ ← +1) or decreasing (∆ ← -1). Otherwise, switch the direction (∆ ← -∆) and run the look-up of step 2.

Since the hierarchical queue Q cannot be empty when nextlevel is called (the propagation is not completed), we have found the new current level .

Note than at each call to nextlevel, we pick at random a direction to look for the new current level.

When the routine nextlevel is called, the algorithm has inspected (popped from Q) all the points related to a node of the tree of shapes at level . Finding the next closest level in Q, either increasingly or decreasingly, ensures that we are going to inspect the points of the child nodes, and not the ones of the other descendants. It means that we do not skip the immediate sub-shapes of the one just processed. The children nodes correspond to distinct and separated connected components, so the order in processing these nodes has no influence on the propagation and, as a consequence, on the result of the algorithm. The same image u is obtained whatever the choice of the direction in the step 1 of the routine nextlevel. Said differenty, we just browse the nodes of the tree of shapes in a downward fashion; there are several ways to browse the nodes downwards, but they do not lead to different results. This is illustrated in Figure 28 with the image (left) and its tree of shapes (right) on the top row. When the current level is medium gray, we process the shape A (middle row), and afterwards, the hierarchical queue (in yellow) contains two non-empty bins: the black level one, of shape B, and the light-gray level one, of shape C. Choosing as the next current level the former (decreasing the current gray level) or the latter (increasing it) just changes the order used to browse the tree of shapes downwards, but does not change the result. As a conclusion, we can change the strategy of the routine nextlevel in finding the next level , since we ensure that it is the first non-empty level increasingly or decreasingly.

We have the guarantee that the computation of u from U is deterministic. Now we can prove that the algorithm is self-dual, meaning that -U leads to -u .

Assuming that we start from p ∞ at level ∞ for U , we have to start at -∞ for -U . Since usually we chose for ∞ the median value of the border of u, we have such a property.

To compute u from U , let us pick a different strategy for nextlevel than the one above (we know that it does not change the result). For that, we just remove the step 1 "choose at random a direction", and we chose the initial direction ∆ ← +1 before the propagation. It means that the hierarchical queue will be browse with increasing values of until there is no more points, then decreasingly until there is no more points, then again increasingly, and so on. With -u, we can pick a different strategy: remove again step 1 from nextlevel but initialize the direction with ∆ ← -1. It is trivial to see that the propagation of the algorithm with -U in the image space is the same than for U , except that the levels in the hierarchical queue and the current level are changed from to --we can say that both the strategy in browsing the hierarchical queue and the queue itself have been symmetrized. The result we obtain is provably -u . Last, since the particular strategy of nextlevel that we have chosen to run the algorithm on -u provides us with the same result than any valid strategy, we can conclude that:

(U ) = -(-U ), with being the flattening operation performed by the algorithm. This algorithm is therefore self-dual.

Conclusion

In this paper, we have proven two of the fundamental properties of the first non-local interpolation introduced in the discrete topology community to repair cubical images containing pinches: digital well-composedness and inbetweeness.

In the future, we will provide the proof that this interpolation is also self-dual, that is, treats bright and dark components in the same manner, contrary to the min/max interpolations of Mazo et al. [START_REF] Géraud | Selfduality and digital topology: links between the morphological tree of shapes and wellcomposed gray-level images[END_REF][START_REF] Mazo | Digital imaging: A unified topological framework[END_REF] (the min interpolation emphasizes dark components and the max interpolation emphasizes the bright components). This property is crucial for the tree of shapes since it leads to what we call pure self-Case Relation 1 Relation 2 Relation 3

(1.1) t(a) < t(m) u (a) = U (a) u (m) ≥ u (a) (1.2) t(a) < t(m) u (a) ∈ U (a) u (m) = u (a) (1.3) t(a) < t(m) u (a) = U (a) u (m) ≤ u (a) (2.1.a) t(m) < t(a) u (a) = U (a) u (m) > u (a) (2.1.b) t(m) < t(a) u (a) = U (a) u (m) = u (a) (2.2) t(m) < t(a) u (a) = U (a) u (m) > u (a) (2.3) t(m) < t(a) u (a) ∈ U (a) u (m) = u (a) (2.4) t(m) < t(a) u (a) = U (a) u (m) < u (a) (2.5.a) t(m) < t(a) u (a) = U (a) u (m) < u (a) (2.5.b) t(m) < t(a) u (a) = U (a) u (m) = u (a)
We obtain finally that u (a) < u (m) implies that we are in Case 1.1, 2.1.a, or 2. R be an n-D interval-valued map, and let u = FP(U ) : D → R be the function resulting from the front propagation algorithm applied on U . Now, let r be a point of D . We can observe the two following implications:

   u (r) < U (r) ⇒ (r) ≤ u (r) (1) u (r) > U (r) ⇒ (r) ≥ u (r) (2)
Proof: By a case-by-case study, we can establish a correlation between (r) and u (r) for any given point r ∈ D . The possible cases are (r) < U (r) (1), (r) ∈ U (r) (2), and (r) > U (r) (3):

1. we obtain that (r) < u (r) because u (r) ∈ U (r), and at the same time, u (r) is equal to U (r) because it is the nearest value to (r) in U (r); 2. we obtain that u (r) = (r) because the nearest value to (r) in U (r) is (r) itself, and at the same time we obtain simply the initial property u (r) ∈ U (r) (no additional assumption is possible);

3. we obtain that (r) > u (r) because u (r) ∈ U (r), and at the same time u (r) = U (r) because this is the nearest value to (r) into U (r).

Finally, we obtain this table:

Case Relation 1 Relation 2 (1) : (r) < U (r) (r) < u (r) u (r) = U (r) (2) : (r) ∈ U (r) (r) = u (r) u (r) ∈ U (r) (3) : (r) > U (r) (r) > u (r) u (r) = U (r)
Then we can observe that if u (r) < U (r), that is, if u (r) = U (r), we are then either in the case [START_REF] Aubin | Set-valued analysis[END_REF] or in the case (2) and then we obtain that (r) ≤ u (r).

Conversely, if u (r) > U (r), that is, if u (r) = U (r), we are then either in the case (2) or in the case (3) and then we obtain that (r) ≥ u (r).

Lemma 6 Let

U : D ⊆ (Z/2) n
R be an n-D interval-valued map, and let u = FP(U ) : D → R be the gray-level function resulting from the front propagation algorithm applied on U . Let p, q ∈ D be two 2n-neighbors in (Z/2) n and λ ∈ R. Then, it is impossible to get the following set of properties together:

       u (p) ≤ λ, (H1) U (p) > λ, (H2) u (q) > λ, (H3) U (q) ≤ λ. (H4)
Proof: Now, let p, q be two 2n-neighbors in D and let us assume that there exists a value λ ∈ R verifying (H1), (H2), (H3) and (H4).

We can observe easily thanks to (H1) and (H2) that u (p) < U (p) and then using Lemma 5, we obtain: (p) ≤ u (p) (H5).

In addition, thanks to (H3) and (H4), we obtain u (q) > U (q) and using Lemma 5, this results in:

(q) ≥ u (q) (H6).

Taking into consideration the two 2n-neighbors p and q, we have 4 possible scenarios as depicted in Figure 29: 1. either p is enqueued before q, then two subcases are possible:

push(Q,p,U,ℓ') push(Q,q,U,ℓ') push(Q,q,U,ℓ') (1.a) (1.b) (2.a) (2.b) h ← pop(Q,ℓ) = p h ← pop(Q,ℓ) = p h ← pop(Q,ℓ) = q h ← pop(Q,ℓ) = q push(Q,q,U,ℓ') push(Q,p,U,ℓ') push(Q,p,U,ℓ')
Fig. 29: The 4 possible scenarios when only two 2n-neighbors p and q in D are considered.

(a) either q is enqueued when p is the current position, (b) or q is enqueued before p is the current position. 2. either q is enqueued before p, then two subcases are possible: (a) either p is enqueued when q is the current position, (b) or p is enqueued before q is the current position.

Let us notice that since p and q are 2nneighbors, q cannot be enqueued after p is the current position, and similarly p cannot been enqueued after q is the current position (all the 2n-neighbors of the current position will have been enqueued when it has been processed). Now let us show that whatever the scenario we choose, we always obtain a contradiction.

(1.a): p is enqueued before q, and then q is enqueued when p is the current position. It means that (q) = u (p). However, we have seen that u (p) ≤ λ by (H1), and that (q) ≥ u (q) > λ by (H6) and (H3). This leads to a contradiction.

(1.b): p is enqueued before q, and q is enqueued before the current position is set at p. This way, since the current level at t(p) is equal to (p) ≤ u (p), it is equal to (q) ≤ u (p) at t(q) (no jump of the non-empty queue level Q[u (p)] is allowed by the algorithm). This means by (H1) that (q) ≤ λ. However, by (H6) and (H3), (q) > λ. This leads to a contradiction.

(2.a) is the symmetrical case of (1.a) and (2.b) is the one of (1.b) and then they lead also to contradictions.

The conclusion is that whatever the scenario (and one of these scenarios happens during the computation of the interpolation), the combination of hypotheses (H1), (H2), (H3) and (H4) leads to a contradiction. These hypotheses are then incompatible. We want to show that U 1 is digitally wellcomposed on D , and for that we are going to show by an induction process that, ∀k ∈ 0, 2n , U 1 D k is digitally well-composed.

Initialization (k = 0): U 1 D0 = U 0 which is DWC by hypothesis.

Heredity (k ∈ 1, 2n ): assuming that the image U 1 D k-1 is DWC, let us show that U 1 D k is DWC too. Two cases are then possible.

either k is odd, then se k = {0, -1 2 e k+1 2 }, and then we obtain the configuration depicted in Figure 30 (Case 1), or k is even, then se k = {0, k (p) = u - k (p) = c and that dim(S * ) ≥ 1, there exist two points p, q ∈ S * which are not antagonists into S and such that u + k (p) = u + k (q) and u - k (p) = u - k (q), then (A) and (B) are both true, 4. or p max ∈ D k-1 and p min ∈ ∆D. Then we are in the first case in Figure 30. A dual reasoning leads to the fact that (A) and (B) are both true.

We can then conclude by induction that U 1 is DWC.

Proof that digital well-composedness implies equivalent connectivities

Let us recall the definition of well-composedness based on the equivalence of connectivities [START_REF] Boutry | How to make n-D functions digitally well-composed in a self-dual way[END_REF] (EWCness).

Definition 21 Let X be a digital set in Z n . X is said to be EWC or well-composed based on the equivalence of its connectivities if the two following conditions hold:

any of its 2n-components is also one of its (3 n -1)-components and vice versa. any 2n-component of X c is also a (3 n -1)component of X c and vice versa.

We can underline that this definition is clearly self-dual, and since the connectivity does not matter for this class of sets, we will sometimes say that their connectivities (and the ones of their complement in Z n ) are equivalent. In addition, this definition is the "natural" extension of the one of Latecki in [START_REF] Latecki | Well-composed sets[END_REF] for 2D sets. Now that we have the definition of EWCness for sets, we can define EWCness for graylevel images.

Definition 22 A gray-level image u : D ⊆ Z n → Z is said well-composed based on the equivalence of connectivities (EWC) if all its threshold sets are well-composed based on the equivalence of connectivities.

The definitions of EWCness for sets and images are extended naturally to (Z/2) n : a subset X of (Z/2) n is said EWC if the connected components of X and of (Z/2) n \ X do not depend on the chosen connectivity, and a gray-level image u : D ⊆ (Z/2) n → Z is said EWC if all its threshold sets are EWC.

Let us recall that EWCness is a global property, since it is based on connected components, and that DWCness is based on local properties, that is, there is no critical configurations. That shows that the link between DWCness and EWCness is not so obvious. Before proving that DWCness implies EWCness in any (finite) dimension n, n ≥ 2, let us announce some lemmas. Lemma 7 Let p, p ∈ Z n be two points in a digitally well-composed set X ⊂ Z n . If p and p are (3 n -1)-connected into X, they are also 2n-connected into X.

Proof: Let p, p be two points in X ⊂ Z n which is digitally well-composed. Assuming that p and p are (3 n -1)-connected into X, there exists a (3 n -1)-path π = (q 0 = p, q 1 , . . . , q k-1 , q k = p ) of length k ≥ 0 joining them into X. For any i ∈ 0, k -1 , q i and q i+1 are (3 n -1)-adjacent, and then antagonists in a block S(q i , q i+1 ). Since X is digitally well-composed and q i and q i+1 belong to X, by Theorem 1, there exists a 2n-path joining q i and q i+1 into X ∩ S(q i , q i+1 ). Then, p and p are 2n-connected into X.

Theorem 5 Let X ⊂ Z n be a digitally wellcomposed set. Then, X is well-composed based on the equivalence of connectivities (EWC). In other words, we have: CC 2n (X) = CC 3 n -1 (X), and CC 2n (X c ) = CC 3 n -1 (X c ). Proof: Let assume that X ⊂ Z n is DWC. By Lemma 7, each 2n-component of X is also a (3 n -1)-component of X (see details in Figure 31a), and each (3 n -1)-component of X is also a 2n-component of X (see details in Figure 31b).

Recall that the converse of Theorem 5 is not true in 3D (see Figure 32): a 3D subset of Z n can be EWC without being DWC, since the (3 n -1)-components and the 2n-components of this set are equal, but it contains a 2D critical configuration at the top and then is not DWC (the reasoning holds for any dimension n ≥ 3).

Corollary 1 Let u : D → Z be a gray-level image. Then, when u is DWC, u is EWC.

Proof: This follows directly from Theorem 5.

  1 and is equal to i∈ 1,n |x i | where |.| is the absolute value. In addition, the L ∞ -norm is denoted by . ∞ and is equal to max i∈ 1,n |x i |.

Fig. 2 :

 2 Fig. 2: 2D, 3D and 4D blocks.

Fig. 3 :

 3 Fig. 3: In the raster scan order: the white points are 1-antagonists, 2-antagonists, 3antagonists, and 4-antagonists.

Fig. 4 :

 4 Fig. 4: The white points draw 2D primary critical configurations.

Figures 4 ,

 4 Figures 4, 5 and 6 depict respectively 2D, 3D, and 4D critical configurations.

Fig. 5 :

 5 Fig. 5: The white points draw a 3D primary critical configuration on the left and a secondary 3D critical configuration on the right.

Fig. 6 :

 6 Fig. 6: The white points draw a 4D primary critical configuration on the left and a secondary 4D critical configuration on the right.

Fig. 7 :

 7 Fig. 7: A family of (large upper) threshold sets {[U λ]} λ of an interval-valued image U . We can remark the straightforward inclusion relationship [U λ] ⊆ [U λ -ε] for any λ ∈ R and ε > 0.

  Fig. 8: A family of (strict upper) threshold sets {[U λ]} λ of an interval-valued image U . We can remark the straightforward inclusion relationship [U λ] ⊆ [U λ -ε] for any λ ∈ R and ε > 0.

Fig. 9 :Definition 7

 97 Fig. 9: Computation of the tree of shapes.

Fig. 10 :Fig. 11 :UFig. 12 :

 101112 Fig. 10: The front propagation algorithm applied on a digitally well-composed interval-valued image U .

step 5 ♭ u 4 Fig. 14 :Fig. 15 :

 541415 Fig. 14: The interpolation of u.

Z 2 n

 2 → N, called the order, defined as the number of half coordinates of z.

2 n

 2 \ {p, q} such that pRr and rRq. Definition 10 We denote by 1 2 (z) the set of the coordinates of the point z ∈ Z 2 n such that they are not integers:

2 n

 2 just based on the number of integral coordinates. Definition 11 Let k be an element of 0, n . We denote by E k the set of points in Z 2 n such that they have (n -k) integral coordinates:

2 n

 2 define the 0 th order parents of z denoted P 0 (z) and equal to {z}. In addition, we define recursively, for any z element of Z \ Z n , and for k ∈ 1, o(z) : P k (z) = p∈P(z) P k-1 (p).Now we define a category of points that we call ancestors (of a point p ∈ Z 2 n ). They are very useful because they represent the set of positions of the pixels of which directly depends the value of the interpolation at p when using local interpolations.Definition 13 Let z be an element of Z 2 n .

Fig. 19 :

 19 Fig.19: Computation of opposites relatively to the center of a 1D block (up row) and relatively to the center of a 2D block (bottom row); points of the same color are paired.

2 n.

 2 Proposition 2 ([5,[START_REF] Mazo | Digital imaging: A unified topological framework[END_REF]) The (n-D) interpolations I min and I max are digitally well-composed.

Fig. 20 :

 20 Fig.20:Step-by-step construction of the 2n-path joining the two (red) antagonists into X ∩ S into Z n .

Lemma 1

 1 Let u : D → Z be a gray-level image defined on a bounded hyperrectangle D in Z n . Then u is digitally well-composed on D iff for any λ ∈ R, [u ≤ λ] and [u > λ] are both digitally well-composed (or equivalently iff [u ≥ λ] and [u < λ] are both digitally well-composed). Proof: The direct implication is obvious. For the converse implication, let us define V(u) := {u(z) z ∈ D} and:

[Proposition 3

 3 min(a, b), max(a, b)], and the span of a finite subset S of R is denoted by Span(S) and is equal to: [min(S), max(S)]. Let n ≥ 2 be an integer, and let H be a bounded hyperrectangle. A gray-level image u : D ⊂ Z n → R is digitally well-composed iff for any block S ∈ B(D) such that dim(S) ≥ 2 and for any pair of points (p, p ) ∈ S × S such that p = antag S (p), intvl(u(p), u(p )) intersects Span u(p ) p ∈ S \ {p, p } . Proof: Let us assume that there exists a block S ∈ B(D) and a couple of points (p, p ) ∈ S × S such that this intersection is empty. Let us denote by S the set S \{p, p }. Then either: max{ u(p ) p ∈ S } < min(u(p), u(p )), and in this case [u ≥ min(u(p), u(p ))] ∩ S is equal to {p, p } and then is a primary critical configuration, or: max(u(p), u(p )) < min{ u(p ) p ∈ S }, and [u ≥ min{ u(p ) p ∈ S }]∩S is equal to S , which is a secondary critical configuration.

Fig. 21 :

 21 Fig. 21: The complete process in detail.

1 Fig. 22 :

 122 Fig. 22: From U + to u .

Definition 20 A

 20 cubical interpolation method I : Im(Z n , R) → Im( Z 2 n , R) is said inbetween if for any image u ∈ Im(Z n , R) defined on a bounded hyperrectangle D ⊆ Z n , its cubical interpolation u = I(u) defined on D = Subd(D) is such that at each point p ∈ D \ D, the value u (p) satisfies the relation:

Fig. 26 :

 26 Fig.26: Summary of the proof that u DWC is DWC: we know by Proposition 6 that I Span (u) is DWC. Then, Proposition 7 ensures that adding a border preserves DWCness and then U + is DWC. Theorem 2 shows that the front propagation preserves DWCness, and then u is DWC. Finally, removing the outer border preserves DWCness, which concludes the proof: u DWC is DWC.

Theorem 3

 3 Let u : D ⊂ Z n → Z be a given image. Then the image u DWC = I DWC (u) is digitally well-composed.

Fig. 28 :

 28 Fig. 28: The algorithm propagation, where progressing with increasing or decreasing gray levels does not change the result.

  2 and then u (a) = U (a), and that u (a) > u (m) implies that we are in Case 1.3, 2.4, or 2.5.a, and then u (a) = U (a). This concludes the proof. 10.2 Proof of the secund intrinsic property of the FPA Lemma 5 Let U : D ⊆ (Z/2) n

10. 3 Proposition 7 2 n; 2 nZ 2 n 2 ,

 372222 The proof that adding a constant border preserves DWCNess Let us denote by δ the dilation operator and by se the structuring element defined such thatse := p ∈ Z ||p|| ∞ ≤ 1/2 .Let U 0 : D ⊂ Z be a DWC intervalvalued map defined on a bounded hyperrectangle D in Z . Now, let U 1 : D Z be another interval-valued map defined on a bounded hyperrectangle D = δ(D, se), such that U 1 | D = U 0 and for any p ∈ D \ D, U (p) = {c} (where c in a given constant in R). Then, U 1 is a DWC interval-valued map.Proof: First let us introduce some notations. Let (se k ) k∈ 1,2n be a sequence of structuring elements defined s.t. ∀k ∈ 1, 2n : se k = 0, and let (D k ) k∈ 0,2n be a sequence of domains s.t. D 0 = D and s.t., ∀k ∈ 1, 2n :D k = δ(D k-1 , se k ).In this manner, D 2n = δ(D, se) = D .

1 Fig. 30 :

 130 Fig. 30: Two possible configurations when dilating the domain D k-1 into D k with our structuring elements.

1 2 e k 2 =S

 2 }, and then we obtain the configuration depicted in Figure30(Case 2).Let us now denote ∆D the set equal to D k \ D k-1 . Let us remark that this set is also an hyperrectangle. In addition, let us denote byu + k , u - k , u + k-1 and u - k-1 the images U 1 D k , U 1 D k , U 1 D k-1 , U 1 D k-1 respectively. We can say that U 1 D k is DWC iff ∀S ∈ B(D k , Z2n ) s.t. dim(S) ≥ 2, ∀p, p ∈ S s.t. p = antag S (p), we have the following relations: + k(p), u + k (p )) ∩ Span{u + k (q) ; q ∈ S \ {p, p }} = ∅, (A) intvl(u - k (p), u - k (p )) ∩ Span{u - k (q) ; q ∈ S \ {p, p }} = ∅. (B) So let S be such a block of D k into Z 2 n ,and let p min and p max be two elements of S such that, for any i ∈ 1, n , min{p i ; p ∈ S},p max i = max{p i ; p ∈ S}.In this manner, p min and p max are antagonists in S. Then, 4 cases are possible: 1. p min and p max belong to D k-1 , then S ⊆ D k-1 , and in this way, ∀p ∈ S, u + k (p) = u + k-1 (p) and u - k (p) = u - k-1 (p), which implies that the intersections in (A) and (B) are non empty since u + k-1 and u - k-1 are DWC and dim(S) ≥ 2, 2. or p min and p max belong to ∆D, then S ⊆ ∆D, and then ∀p ∈ S, u + k (p) = u - k (p) = c, which means that (A) and (B) are true since dim(S) ≥ 2, 3. or p min ∈ D k-1 and p max ∈ ∆D. Then we are in the second case in Figure 30. In other words, ∩ D k-1 = {p ∈ S ; p k/2 = p min k/2 }, S ∩ ∆D = {p ∈ S ; p k/2 = p max k/2 }, which means that S can decomposed into two blocks of dimension dim(S) -1 ≥ 1, the first being S ∩ D k-1 and the second being S * := S ∩ ∆D. Since S * verifies that ∀p ∈ S * , u +

  If A is a 2n-component of a DWC set X, then each point p ∈ X which is (3 n -1)connected to any point p element of X belongs to A since (3 n -1)-connectivity implies 2n-connectivity in a DWC set. If B is a (3 n -1)-component of a DWC set X, each couple of points q, q ∈ B are also 2n-connected into X since (3 n -1)connectivity implies 2n-connectivity in a DWC set.

Fig. 31 :

 31 Fig. 31: DWCness implies EWCness.

Fig. 32 :

 32 Fig. 32: EWCness does not imply DWCness in n-D (n ≥ 3).

  2. Look in Q for the next closest level , applying ← + ∆, such as Q[ ] is not empty. 3. If found, is the new current level; done.

The ∞ subscript in ∞ comes from the fact that it is related to the point p ∞ which represents the initial position of the algorithm, itself corresponding to the outer border of the domain of the image.

duality: the tree of shape of an image is equal to the tree of shape of the opposite image.

We will also prove that this interpolation is integral-translation-invariant and π/2-rotationinvariant. Proof: Let us begin with the case t(a) < t(m), that is, a has been enqueued before m. Three cases are possible.

, and the current level stays at the value u (m) until m is processed (at least). Since a and m are 2n-neighbors, and since a is enqueued after m, a is enqueued after t(m) and at the latest while m is processed. This way, (a) = u (m), and then u (a) = U (a) < u (m) (Case 2.