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

Laurent Najman
email: l.najman@esiee.fr

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

Equivalence between Digital Well-Composedness and Well-Composedness in the Sense of Alexandrov on n-D Cubical Grids

Keywords: digital topology, discrete surfaces, wellcomposed images

published or not. The documents may come

Introduction

Fig. 1: Equivalence between DWCness in Z 2 and AWCness in the 2D Khalimsky grid H 2 : The 3 first sets in black in the raster scan order are DWC (they do not contain any critical configuration); their analog in H 2 are AWC (their dark grey boundaries are simple closed curves). At the opposite, the last set (circled in red) which is not DWC in Z 2 leads to an analog in H 2 whose boundary is not a simple closed curve (see the self-crossing of the boundary of this set in H 2 in red) and then is not AWC in H 2 .

In 1995, Latecki introduced in [START_REF] Latecki | Well-composed sets[END_REF] the notion of well-composedness as an elegant manner to get rid of the connectivity paradoxes well-known in digital topology. Roughly speaking, a set in Z 2 is said to be wellcomposed if its connectivities are equivalent, that is, its set of connected components is the same whatever the chosen connectivity. This definition has then been extended to dimension 3 in [START_REF] Longin | 3D well-composed pictures[END_REF] and in n-D in 2015 in [START_REF] Boutry | How to make n-D functions digitally well-composed in a self-dual way[END_REF]; at the same moment, this definition of well-composedness has been renamed digital well-composedness (DWCness).

Later, in 2013, Najman and Géraud [START_REF] Najman | Discrete setvalued continuity and interpolation[END_REF] introduced a new notion of well-composedness: a subset X in a Khalimsky grid, a topological analog of the cubical grid Z n but with combinatorial properties, is said to be well-composed in the sense of Alexandrov (AWC) if its boundary is made of a disjoint union of discrete (n-1)surfaces (the definition of a discrete surface is formally recalled later). This definition is used to be able to characterize gray-level images defined on a Khalimsky grid and whose set of shapes makes a tree; then, we can call "tree of shapes" this last set. This hierarchical representation is known to be powerful to make image segmentation or image filtering thanks to shapings (a filtering of the shapes of a given image based on its tree of shapes).

These two definitions, even if they seem very different, are related: it has been observed that in 2D and in 3D, a digital set is DWC if and only if it is AWC (see Figure 1). In other words, AWCness and DWCness are equivalent in 2D/3D on cubical grids. However, the question about their equivalence in 4D and beyond still remains an open question. For sake of completion, we propose here to prove that they are indeed equivalent in n-D, n ≥ 2 for sets and that it holds for gray-level images. A study of the relation between the different flavors can be found in [START_REF] Boutry | A Study of Well-Composedness in n-D[END_REF] and a list of some of the important properties of AWCness and DWCness can be found in [START_REF] Boutry | A tutorial on well-composedness[END_REF].

The plan is the following: Section 2 recalls the basics in matter of digital topology; Section 3 recalls some mathematical background relative to Z 2 n and H n ; Section 4 recalls how AWCness implies DWCness in n-D; Section 5 presents some lemmas, propositions and notations necessary in the next section; Section 6 proves that DWCness implies AWCness in n-D; Section 7 extends the proofs seen before from sets to gray-level images; Section 8 shows some possible applications of well-composedness for gray-level images; Section 9 concludes the paper; Sections A, B, C and D contains the proofs of the preceding assertions.

Note that a star has been added in the title of each assertion which seems to us crucial to understand the proof of the equivalence between AWCness and DWCness.

Digital topology

Let us recall the mathematical background necessary to define digital well-composedness and well-composedness in the sense of Alexandrov.

Digital topology and DWCness

B

Orthonormal canonical basis of Z n

x i i th coordinate of x ∈ Z n N * 2n (x) 2n-neighborhood of x ∈ Z n N * 3 n -1 (x) (3 n -1)-neighborhood of x ∈ Z n F (f 1 , . . . , f k ) ⊆ B ×
The Cartesian product

L(k) {k} when k ∈ Z, {k -1/2, k + 1/2} when k ∈ Z, S(z) S(z) = × i∈ 1,n L(z i ) S(z, F)    z + i∈ 1,k λ i f i λ i ∈ {0, 1}, ∀i ∈ 1, k    antag S (q)
The antagonist of q ∈ Z n in the block S Table 1: Notations relative to digital topology.

Fig. 2: The two classical neighborhoods used in digital topology when the dimension n of space is 2. The point p is depicted in black, and its neighborhoods are depicted in blue: the 2n-neighborhood is on the left side when the (3 n -1)-neighborhood is on the right side. We can observe that the 2n-neighborhood is made of 4 points and that the (3 n -1)-neighborhood is made of 8 points (because we are in 2D).

The following notations are detailed in Table 1. Let B = {e 1 , . . . , e n } be the canonical basis of Z n . We use the notation x i , where i belongs to 1, n 1 , to determine the i th coordinate of x ∈ Z n . We recall that the L 1 -norm of a point x ∈ Z n is denoted by . 1 and is equal to i∈ 1,n |x i | where |.| is the absolute value. Also, the L ∞ -norm is denoted by . ∞ and is equal to max i∈ 1,n |x i |. For a given point x ∈ Z n , an element of the set N * 2n (x) = {y ∈ Z n ; x -y 1 = 1} (resp. of the set N * 3 n -1 (x) = {y ∈ Z n ; x -y ∞ = 1}) is a 2nneighbor (resp. a (3 n -1)-neighbor ) of x (see Figure 2).

For any z ∈ Z n and any F = (f 1 , . . . , f k ) ⊆ B, we denote by S(z, F) the set:

   z + i∈ 1,k λ i f i λ i ∈ {0, 1}, ∀i ∈ 1, k    .
We call this set the block associated with the pair (z, F); its center is z + f ∈F f 2 , and its dimension, denoted by dim(S), is equal to k. We denote by S(c) the block centered at c ∈ Z 2 n . Note that we have:

S(c) = × i∈ 1,n L(c i ),
where L(k) := {k} when k ∈ Z, {k -1/2, k + 1/2} when k ∈ Z, and where × is the Cartesian product. Fig. 3: Let z ∈ Z 3 be equal to (0, 0, 0). We depict here the block S(z, F) = {(0, 0, 0), (1, 0, 0), (0, 1, 0), (1, 1, 0)} associated to the family F = {e 1 , e 2 }; this block is centered at c = ( 1 2 , 1 2 , 0) ∈ Z 3 2 . We can remark that S(c) = × k∈ 1,3 L(k) = {0, 1} × {0, 1} × {0} is equal to S(z, F) as explained before. More generally, a set S ⊂ Z n is said to be a block (see Figure 3) if there exists a pair (z, F) ∈ Z n × P(B) 2 such that S = S(z, F). Then, we say that two points p, q ∈ Z n belonging to a block S are antagonists [START_REF] Boutry | A Study of Well-Composedness in n-D[END_REF][START_REF] Boutry | How to make n-D functions digitally well-composed in a self-dual way[END_REF] in S if the distance between them equals the maximal distance using the L 1 norm between two points in S (see Figure 4); in this case we write p = antag S (q). Note that the antagonist of a point p in a block S containing p exists and is unique. Two points that are antagonists in a block of dimension k ≥ 0 are said to be k-antagonists; k is then called the order of antagonism between these two points. We say that a digital subset X of Z n contains a critical configuration in a block S of dimension 2 P(B) denotes the set of subsets of B.

Fig. 4: Some examples of antagonists in Z 2 : the two red points are antagonists in the block of dimension 1 encircled by the red curve; the two green points are antagonists in the block of dimension 2 encircled by the green curve; the orange point is antagonist with itself in the block of dimension 0 encircled in orange.

k ∈ 2, n if there exists two points {p, p } ∈ Z n that are antagonists in S s.t. X ∩ S = {p, p } (primary case) or s.t. S \ X = {p, p } (secondary case). Definition 1. A digital set X ⊂ Z n is said to be digitally well-composed [START_REF] Boutry | How to make n-D functions digitally well-composed in a self-dual way[END_REF][START_REF] Latecki | Well-composed sets[END_REF] (DWC) if it does not contain any primary or secondary critical configuration. Fig. 5: An example of 4-path in red in Z 2 joining the black points.

We recall that a 2n-path (see Figure 5) in a subset S of Z n is a finite sequence of points p 0 , . . . , p k of S with k ≥ 0 such that for any m ∈ 1, k , p m-1 and p m are 2n-neighbors in Z n . Proposition 1 ([10]). A digital set X ⊂ Z n is DWC iff for any block S of Z n and for any pair of points (p, p ) of X (respectively any pair of points (p, p ) of S \ X) which are antagonists in S, there exists a 2npath joining p and p in X ∩ S (respectively in S \ X).

Axiomatic digital topology and AWCness

All the notations of Table 2 are detailed below. For A and B two sets of arbitrary elements, A × B denotes

A, B

Two sets of arbitrary elements R ⊆ X × X A binary relation on the set X R(y) {x ∈ X ; x R y} R {(x, y) ∈ X × X ; x R y and x = y} |X| = (X, R) X supplied with the order relation R

X

The set of subparts of X U ⊆ 2 X A topology on X (X, U) = X A topological space

R -1
The inverse of the order relation R h

An element of a topological space X α X (h)

The closure of h in X β X (h)

The opening of h in X θ X (h)

The neighborhood of h in X α X (h)

α X (h) \ {h} β X (h) β X (h) \ {h} θ X (h) θ X (h) \ {h} S ⊆ X A subset of X α S (h) α X (h) ∩ S β S (h) β X (h) ∩ S θ S (h) θ X (h) ∩ S α S (h) α X (h) ∩ S β S (h) β X (h) ∩ S θ S (h) θ X (h) ∩ S α X (S) ∪ p∈S α X (p) β X (S) ∪ p∈S β X (p) θ X (S) ∪ p∈S θ X (p)
Table 2: Notations relative to axiomatic digital topology.

the Cartesian product of A and B and is defined as {(a, b) ; a ∈ A, b ∈ B}. A binary relation [START_REF] Bertrand | New notions for discrete topology[END_REF] R defined on a set of arbitrary elements X is a subset of X × X, and we denote by x ∈ R(y) or equivalently x R y the fact that (x, y) ∈ R. An order relation [START_REF] Bertrand | New notions for discrete topology[END_REF] is a binary relation R which is reflexive, antisymmetric, and transitive. We denote by R the binary relation on X defined such that, ∀x, y ∈ X, x R y ⇔ {x R y and x = y}.

A set X of arbitrary elements supplied with an order relation R on X is called a poset and is denoted by (X, R), or shortly |X| when no ambiguity is possible.

Let X be a set of arbitrary elements, and let U be a set of subsets of X. We say that U is a topology on X if ∅ and X are elements of U, if any union of elements of U are elements of U, and if any finite intersection of elements of U is an element of U. X supplied with U is denoted (X, U) or shortly X and is called a topological space. The elements of U are then called the open sets of X and any complement of an open set in X is called a closed set of X. We say that a subset of X which contains an open set containing a point x is a neighborhood of x in X. A topological space X is said (topologically) connected if it is not the disjoint union of two non-empty open sets.

A T 0 -space [START_REF] Alexandrov | Combinatorial topology[END_REF][START_REF] Alexandrov | Die grundlehren der mathematischen wissenschaften in einzeldarstellungen[END_REF][START_REF] John | General Topology[END_REF], let say X, is a topological space which satisfies the T 0 axiom of separation: for two distinct elements x, y of X, there exists a neighborhood of x in X which does not contain y or a neighborhood of y in X which does not contain x. A discrete space [START_REF] Alexandrov | Diskrete Räume[END_REF] is a topological space where any intersection of open sets is an open set. Posets are considered as topological spaces in the sense that we can induce a topology on any poset based on its order relation (Th. 6.52, p. 28 of [START_REF] Alexandrov | Combinatorial topology[END_REF]): for a poset (X, R), the corresponding Alexandrov space is the topological space of domain X where the closed sets are the sets C ⊆ X such that ∀x ∈ C, R(x) is included in C. Let us denote by R -1 the inverse of R. Then, by symmetry, we obtain that open sets are the sets U such that for any h ∈ U , R -1 (h) is included into U . Discrete T 0 -spaces are generally called Alexandrov spaces. Details can be found in [START_REF] Eckhardt | Digital topology[END_REF].

On an Alexandrov spaces |X| = (X, R), for any element h ∈ X, we define respectively the combinatorial closure of h: α(h) := {h ∈ X ; h ∈ R(h)}, its inverse operator called the combinatorial opening of h: β(h) := {h ∈ X ; h ∈ R(h )}, and the neighborhood of h:

θ(h) := {h ∈ X ; h ∈ R(h) or h ∈ R(h )}.
Obviously, thanks to the properties explained before, for any h ∈ X, α(h) will be a closed set in X and each β(h) will be an open set in X. In other words, combinatorial and topological definitions are equivalent in Alexandrov spaces.

The operators α, β and θ are also defined for sets: ∀S ⊆ X, α(S) := ∪ p∈S α X (p), β(S) := ∪ p∈S β X (p), and θ(S) := ∪ p∈S θ X (p), where α(S) is closed and β(S) is open thanks to the properties exposed before.

In this paper, we work with cubical Alexandrov spaces called Khalimsky grids [START_REF] Khalimsky | Computer graphics and connected topologies on finite ordered sets[END_REF] and denoted by |H n | = (H n , ⊆) (see Table 3); they are defined such that:

                   H 1 0 = {{a} ; a ∈ Z} , H 1 1 = {{a, a + 1} ; a ∈ Z} , H 1 = H 1 0 ∪ H 1 1 , H n = h 1 × • • • × h n ; ∀i ∈ 1, n , h i ∈ H 1 . H n = (H n , ⊆) The n-D Khalimsky grid h ∈ H n A face of H n dim(h)
The dimension of h

H n k The faces of dimension k in H n α(h) {h ∈ H n ; h ⊆ h} β(h) {h ∈ H n ; h ⊆ h } θ(h) {h ∈ H n ; h ⊆ h or h ⊆ h } |S| = (S, ⊆) A suborder of H n α S α ∩ (S × S) β S β ∩ (S × S) θ S θ ∩ (S × S) α S (h) α(h) ∩ S β S (h) β(h) ∩ S θ S (h) θ(h) ∩ S Int(S)
Interior of S CC(S, p)

The component of Elements of H n will often be called faces (of H n ).

Any face h of H n which is the Cartesian product of k elements, with k ∈ 0, n , of H 1 1 and of (n -k) elements of H 1 0 is said to be of dimension k [START_REF] Kovalevsky | Axiomatic digital topology[END_REF], which is denoted by dim(h) = k, and the set of all the elements of H n which are of dimension k is denoted by H n k .

Fig. 6: Basic operators in axiomatic digital topology: α is the combinatorial closure, β is the combinatorial opening, and θ is the neighborhood.

Using Khalimsky grids, for any element h ∈ H n , we obtain the following equalities:

α(h) = {h ∈ H n ; h ⊆ h}, β(h) = {h ∈ H n ; h ⊆ h }, θ(h) = {h ∈ H n ; h ⊆ h or h ⊆ h }.
Some examples of such sets are depicted in Figure 6. On the left column, in blue, we can see that the initial face h = {x 0 } leads to α(h) = {h} = {{x 0 }} since no Fig. 7: "Squared" versions of the basic operators used in axiomatic digital topology. other face in H n than {x 0 } is contained in h. On the left column in red, we can see that the initial face h = {x 0 , x 0 +1} leads to α(h) = {{x 0 }, {x 0 , x 0 +1}, {x 0 +1}} since they are the three faces of H n contained in h. We can continue this way with h in green which will contain nine faces. In the middle of Figure 6, the reasoning is dual: we consider the faces of H n including h. And the right column shows that the neighborhood in Khalimsky grids is the union of the closure and of the opening of a face. The "squared" versions of these operators, that is, α , β , and θ are depicted in Figure 7.

Note that the operators α and β are idempotent: α • α = α and β • β = β. However, the neighborhood operator is not idempotent.

From now on, the Khalimsky grids will be supplied with the order relation ⊆ by default.

Assuming that S is a subset of H n , the suborder We call path [START_REF] Bertrand | New notions for discrete topology[END_REF] into a set S ⊆ H n a finite sequence (p 0 , . . . , p k ) such that for all i ∈ 1, k , p i ∈ θ (p i-1 ) (see Figure 8). We say that a digital set S ⊆ H n is path-connected [START_REF] Bertrand | New notions for discrete topology[END_REF] if for any points p, q in S, there exists a path into S joining them. Path-connectedness and topological connectedness are equivalent [START_REF] Bertrand | New notions for discrete topology[END_REF][START_REF] Eckhardt | Digital topology[END_REF] in |H n | like in any Alexandrov space. The greatest (path-)connected set in the digital set S ⊂ H n containing p ∈ H n is called the connected component [START_REF] Alexandrov | Combinatorial topology[END_REF] of S containing p and we denote it by CC(S, p); by convention, when p does not belong to S, we write CC(S, p) = ∅. Any non-empty subset of a poset S which can be written CC(S, p) for some p ∈ S is called a connected component of S. The set of connected components of a poset S is denoted by CC(S). Let |S| be a suborder of H n . |S| is said to be countable if S is countable. Also, |S| is called locally finite if for any element h ∈ S, the set θ S (h) is finite. When |S| is countable and locally finite, it is said to be a CForder [START_REF] Bertrand | New notions for discrete topology[END_REF] in H n .

Let |S| be a CF-order in H n ; |S| is said to be a (-1)-surface if S = ∅, or a 0-surface if S is made of two different faces x, y ∈ X such that x ∈ θ (y), or a ksurface, k ∈ 1, n , if |S| is connected and for any h ∈ S, |θ S (h)| is a (k -1)-surface (see Figure 9). According to Evako et al. [START_REF] Alexander V Evako | Dimensional properties of graphs and digital spaces[END_REF], |H n | is an n-surface.

Any n-surface |S| is said homogeneous [START_REF] Daragon | Surfaces discrètes et frontières d'objets dans les ordres[END_REF], i.e., ∀h ∈ S, β S (h) contains an n-face.

Definition 2 ([28]

). The boundary of a suborder |S| of |H n | is denoted by ∂S and is defined as :

∂S := α(S) ∩ α(H n \ S).
Definition 3 (AWCness [START_REF] Najman | Discrete setvalued continuity and interpolation[END_REF] for sets). Let |S| be a suborder of |H n |. Then, S is said to be well-composed in the sense of Alexandrov (AWC) if the connected components of its boundary are discrete (n-1)-surfaces. We will see in Lemma 10 that Proposition 2 is essential since, for any z in a suborder S, it implies that when |α S (z)| is a (n -p)-surface and when

(X ∪ Y, R X ∪ R Y ∪ X × Y ).
|β S (z)| is a p-surface, then |θ S (z)| = |β S (z)| * |α S (z)| is an (n + 1)- surface.
This way, we will be able to reformulate AWCness of the immersions studied in this paper using only the operator β. As described before, we juggle with two cubical spaces in this paper (see the notations used here in Table 4): Z 2 n (in Figure 10) and H n (in Figure 11). More exactly, we need a bijection from (Z/2) to H n which

0 {0} 4 1 2 5 6 7 8 0 {0} {0,1} {1} {1,2} {2} {2,3} {3} {3,4} {4} 6 {3} 5 {2,3} 4 {2} 3 {1,2} 2 {1} 1 {0,1} 3
Fig. 11: Different immersions of the set presented in the preceding figure. In the raster scan order, the direct transform, the miss transform, the hit transform, and the image by the H n operator (described hereafter). Note that the representation of a set of

Z 2 is not unique in H 2 . H Transform from (Z/2) into H 1 H n Transform from Z 2 n into H n Z Transform from H 1 into (Z/2) Z n Transform from H n into Z 2 n ⊗ Product operator a ∧ b sup (α(a) ∩ α(b)) Card (X)
The cardinal of the set X A B Disjoint union of A and B preserves the structure between these two spaces. For this purpose, we define the function

H : (Z/2) → H 1 : ∀z ∈ (Z/2), H(z) =      {z, z + 1} if z ∈ Z, {z + 1 2 } otherwise.
From H, we can compute its inverse, that we denote by Z : H 1 → (Z/2), and that we define this way:

∀h ∈ H 1 , Z(h) =      a if ∃a ∈ Z s.t. h = {a, a + 1}, a -1/2 if ∃a ∈ Z s.t. h = {a}.
These bijections are depicted in Figure 12. We define also the bijection H n : Z 2 n → H n as the n-ary Cartesian product of H, and we denote by Z n :

H n → Z 2 n its inverse.
Then, for two sets A, B of faces of H n , we define the product operator ⊗:

A ⊗ B := {a × b ; a ∈ A, b ∈ B} .
As usual, for any a ∈ H n , n ≥ 1, and for any i ∈ 1, n , we denote by a i the i th coordinate of a in H n . We can show easily that ∀a ∈ H n , the closure of the Cartesian product is equal to the product of the closures:

α(a) = α × m∈ 1,n a m = ⊗ m∈ 1,n α(a m ),
and the same thing holds for the opening thanks to the symmetry of Alexandrov spaces:

β(a) = β × m∈ 1,n a m = ⊗ m∈ 1,n β(a m ).
3.1 Some relations between Z 2 n and H n Using H n , we obtain the following lemma.

Lemma 1. Let c be a value in (Z/2) \ Z, and let y be a value in Z. Then,

y ∈ c - 1 2 , c + 1 2 ⇔ β(H(y)) ⊆ β(H(c)).
In other words, when H(c) is a 0-face of H 1 , y is a neighbor of c in (Z/2) iff the opening of H(y) is included in the opening of H(c).

The proof of this assertion is postponed to page 29.

Notations 1. From now on, for any c ∈ Z 2 n , let 1 2 (c) denote the set of indices of the coordinates i ∈ 1, n satisfying c i ∈ (Z/2) \ Z.

By Lemma 1, we obtain that: Proposition 4. Let S be a block in Z n , and let c be its center in Z 2 n . Then S and c are related this way:

S = Z n (β(H n (c)) ∩ H n n ).
The proof of this assertion is postponed to page 29 and is depicted in Figure 13.

Supremum in H n

Notations 2. From now on, we write that an expression is WD if it is well-defined.

a ∧ b = sup (α(a) ∩ α(b)) {0} {0,1} {1} {1,2} {2} {-1,0} {-1} -1/2 0 1/2 1 3/2 -1 -3/2 (Z/2) H 1
Fig. 12: The bijection H between (Z/2) and H 1 preserves connectivity between the two spaces.

a ∧ b = (× i∈ 1,n a i ) ∧ (× i∈ 1,n b i ) = × i∈ 1,n (a i ∧ b i ), and we obtain α(a ∧ b) = α(a) ∩ α(b).
The proof of this assertion is postponed to page 30.

Some properties relative to antagonism

Let us now expose a simple lemma relative to antagonism. Lemma 3. Let x, y be two elements of Z n . Then, x and y are antagonists in a block of Z n of dimension k ∈ 0, n iff:

             Card {m ∈ 1, n ; x m = y m } = n -k, (1)
and

Card {m ∈ 1, n ; |x m -y m | = 1} = k. (2)
In other words, x and y are k-antagonists iff they have (n -k) equal coordinates and that the remaining coordinates differ from 1.

The proof of this assertion is postponed to page 30.

By Lemma 3, it follows that:

Lemma 4. ∀p, p ∈ Z n , p and p are k-antagonists, k ∈ 0, n , iff H n (p) ∧ H n (p ) is WD and belongs to H n n-k .
The proof of this assertion is postponed to page 30 and is depicted in Figure 14.

By Lemmas 2 and 4, it follows that: Lemma 5. Let p, p be two elements of Z n such that p and p are (3 n -1)-neighbors in Z n or equal. Then,

H n p + p 2 = H n (p) ∧ H n (p ).
The proof of this assertion is postponed to page 31.

By Lemma 5, the following assertion is true:

Proposition 5.
Let S be a block and let p, p ∈ S be any two antagonists in S. Then the center of the block S is equal to p+p 2 . Furthermore, its image by

H n in H n is equal to H n (p) ∧ H n (p ).
The proof of this assertion is postponed to page 31.

By Lemma 5, we obtain also: Lemma 6. Let p be an element of Z n , then we can reformulate the squared closure of H n (p) in the following manner: The proof of this assertion is postponed to page 31 and is depicted in Figure 15.

α (H n (p)) = v∈N * 3 n -1 (p) α(H n (p) ∧ H n (v)). H n (p) ∧ H n (p ) H n (p ) H n (p) (a) k = 1 H n (p) ∧ H n (p ) H n (p ) H n (p) (b) k = 2 H n (p) ∧ H n (p ) H n (p ) H n (p) (c) k = 3 Fig. 14: Computation of H n (p) ∧ H n (p ) in 3D. f Hn (v) N * 3 n -1 (p)
By Lemmas 2 and 4, it follows that: Lemma 7. Let S be a block in Z n of dimension k ≥ 2. Now, let p, p be two antagonists in S, and v be a 2nneighbor of p in S. Then, we have the following relation:

H n (p) ∧ H n (p ) ∈ α(H n (p) ∧ H n (v)).
The proof of this assertion is postponed to page 31. The proof of this assertion is postponed to page 32 and is depicted in Figure 16.

Additional background concerning n-surfaces

The following proposition results from the proof of Property 11 (p. 55) in [START_REF] Daragon | Surfaces discrètes et frontières d'objets dans les ordres[END_REF].

Proposition 6 (*). Let n ≥ 1 and k ∈ 0, n be two integers. Let |X| = (X, α X ) and |Y | = (Y, α Y ) be two k-surfaces in H n . Then, if |X| is a suborder of |Y |, then |X| = |Y |.
The proof of this assertion is postponed to page 32.

Notations 4. From now on, let us denote by the disjoint union operator: for A and B two sets of arbitrary elements, we denote by A B the union of A and B assuming that A ∩ B = ∅. Proposition 6 implies then:

Corollary 1. Let |X 1 | and |X 2 | be two k-surfaces, k ≥ 0, with X 1 ∩ X 2 = ∅. Then |X 1 X 2 | is not a k-surface.
In other words, the disjoint union of two k-surfaces, k ≥ 0, is not a k-surface.

The proof of this assertion is postponed to page 32. Proposition 3 implies the following assertion:

Proposition 7. Let a, b be two elements of H n with a ∈ β (b). Then |α (a) ∩ β (b)| is a (dim(a) -dim(b) -2)- surface.
The proof of this assertion is postponed to page 32.

4 The proof that AWCness implies DWCness in n-D n ≥ 2
The dimension of the ambient space

X A non-empty finite subset of Z n Y The complement of X in Z n X The image of X by H n Y The image of Y by H n I hit (X)
The hit-transform of X I miss (X)

The miss-transform of X N

The boundary of the two last transforms

f(p, z * ) α(H n (p)) ∩ α(H n (Y ∩ S)) ∩ β (z * ) f(p , z * ) α(H n (p )) ∩ α(H n (Y ∩ S)) ∩ β (z * )
Table 5: Notations relative to the proof that AWCness implies DWCness.

The new notations introduced in this section are summarized in Table 5.

Notations 5. From now on, we assume that n is an integer greater than or equal to 2, that X is a non-empty finite subset of Z n , that Y is the complement of X into Z n ; also, we define the sets:

X := H n (X), Y := H n (Y ).
Notations 6. The hit-transform of X into H n is defined such as:

I hit (X) := α(X ),
and the miss-transform, shortly the immersion, of X into H n is defined such as:

I miss (X) := Int I hit (X) .
For sake of simplicity, the boundary of the immersion of X is denoted by N:

N := ∂I miss (X).

Let us begin with a property of the closures of the sets X and Y. Proposition 8. The sets α(X ) and α(Y) are regular closed sets.

The proof of this assertion is postponed to page 32.

Lemma 9. Let X , Y be two subsets of H n n such that X Y = H n n . Then, α(X ) Int(α(Y)) = H n .
The proof of this assertion is postponed to page 33.

By Lemma 9 and by Proposition 8, we obtain:

Proposition 9. The hit-transform and the miss-transform of X have the same boundary which is equal to:

α(X ) ∩ α(Y).
The proof of this assertion is postponed to page 33 and is depicted in Figure 17.

By Proposition 3, we obtain: Proposition 10. For any z ∈ N, we have the property that |α N (z)| is a (dim(z) -1)-surface.

The proof of this assertion is postponed to page 33.

By Propositions 2 and 10, we obtain that:

Lemma 10 (*). The immersion I miss (X) of X is AWC iff ∀z ∈ N, |β N (z)| is a (n -2 -dim(z))-surface.
The proof of this assertion is postponed to page 33.

Figure 18 shows how we can compute in the 2D case if a set is AWC from a local point of view: the set circled in blue is AWC since for any vertex z ∈ N, |β N (z)| is a 0-surface, while the set circled in red is not AWC since there exists some vertex z such that |β N (z)| is not a 0-surface. ∈ N. In other words, when X contains a primary or secondary critical configuration, the image by H n of the center of the critical configuration belongs to the boundary N of the immersion of X.

H n (X)

I miss (X)

H n (Y ) H n \ I miss (X) α(H n (X)) α(I miss (X)) α(H n (Y )) α(H n \ I miss (X)) α(H n (X)) ∩ α(H n (Y )) α(I miss (X)) ∩ α(H n \ I miss (X)) X Y Y = Fig. 17:
The computation of the boundary of I miss (X) can be made using to different manners: either by computing directly α(I miss (X)) ∩ α(H n \ I miss (X)) using the definition or by computing α(H n (X)) ∩ α(H n (Y )) based on the closures of the sets H n (X) and H n (Y ).

|β N (z)| |β N (z)| z z
Fig. 18: AWCness of a subset of a Khalimsky grid can be expressed using a local point of view using the property that for any z in its boundary N,

|β N (z)| is a (n - dim(z) -2)-surface.
Fig. 19: β N (H n (c)) (in green and red) when X admits a 2D/3D critical configuration in the block of center c (whose image by H n is depicted in light gray) when n = 3.

The proof of this assertion is postponed to page 34 and is depicted in Figure 19.

Then the first main result of this paper is as follows. The summary is presented in Figure 20.

Theorem 1. Let X be a digital subset of Z n . Then, when its miss-transform (or equivalently its hit-transform) is well-composed in the sense of Alexandrov, then X is digitally well-composed.

Proof. The proof is the same if we choose the misstransform or the hit-transform since their boundaries are equal by Proposition 9.

So, we want to prove that AWCness implies DWCness in n-D. For this aim, we will show that if X is not DWC, then I miss (X) is not AWC. Since by Lemma 10,

I miss (X) is AWC iff ∀z ∈ N, |β N (z)| is a (n -2 - dim(z))
-surface, it is sufficient to prove that when X is not DWC, then there exists an element z * of N such that |β N (z * )| is not a (n -2 -dim(z * ))-surface. So, let us assume that X is not DWC, that is, X admits a primary or secondary critical configuration.

Let us treat the primary case, since the reasoning for the secondary case is similar: let us assume that there exists a block S of dimension k ∈ 2, n such that X ∩ S = {p, p } with p = antag S (p). This way, we can compute the image z * by H n into H n of the center of S. By Proposition 5,

z * = H n (p) ∧ H n (p ). Let us show that |β N (z * )| is not a (n -2 -dim(z))- surface. By Proposition 11, z * ∈ N, so the expression β N (z * ) is WD. Now, let us compute |β N (z * )|. For this aim, let us define: f(p, z * ) := α (H n (p)) ∩ β (z * ).
Using Lemma 6,

f(p, z * ) = y∈N * 3 n -1 (p) α(H n (p) ∧ H n (y)) ∩ β (z * ).
Using Lemma 8, we obtain that:

f(p, z * ) = y∈S\{p} α(H n (p) ∧ H n (y)) ∩ β (z * ).
Then, since we know that: 20: Summary of the proof of Theorem 1: since X is assumed not to be DWC, it contains a critical configuration in a block S whose center z * belongs to the boundary N. We can then check that the poset |β N (z * )| is made of two discrete 0-surfaces and then it is not a 0-surface, which means that X is not AWC. thus:

α(H n (p) ∧ H n (p )) ∩ β (z * ) = ∅, p p H(p ) H(p) z * ∈ N f(p, z * ) f(p , z * ) |β N (z * )| = |f(p, z * ) ∪ f(p , z * )| 0-surf 0-surf not AWC Fig.
f(p, z * ) = y∈S\{p,p } α(H n (p) ∧ H n (y)) ∩ β (z * ). By Lemma 2, f(p, z * ) = y∈S\{p,p } α(H n (p)) ∩ α(H n (y)) ∩ β (z * ),
and because S \ {p, p } = Y ∩ S, we obtain that:

f(p, z * ) = α(H n (p)) ∩ α(H n (Y ∩ S)) ∩ β (z * ),
With a similar calculation based on p , we obtain that:

f(p , z * ) := α (H n (p )) ∩ β (z * ) is equal to: α(H n (p )) ∩ α(H n (Y ∩ S)) ∩ β (z * ). Next, f(p, z * ) ∪ f(p , z * ) = α(H n (X ∩ S)) ∩ α(H n (Y ∩ S)) ∩ β (z * ),
which is equal by Lemma 8 to α(X ) ∩ α(Y) ∩ β (z * ), and then to β N (z * ) by Proposition 9.

Finally, we have that:

|β N (z * )| = |f(p, z * ) ∪ f(p , z * )| .
α (H n (p)) ∩ α (H n (p )) ∩ β (z * ) = ∅. However, by Proposition 7, |f(p, z * )| and |f(p , z * )| are both (n-dim(z * )-2)-surfaces. By Corollary 1, |β N (z * )| is not a (n -dim(z * ) -2)-surface, and then I miss (X) is not AWC.
The flow diagram of Theorem 1 (see below) is depicted in Figure 21. Now that we have proved that AWCness implies DWCness, let us prove the converse, but before let us present some general results relative to two spaces: H n and (Z/2) n .

5 General results relative to H n and (Z/2)

n
In this section, we present notations, lemmas and propositions necessary to prove in the next section that DWCness implies AWCness in n-D.

Definition of 1 (x)

Notations 7 (Integral coordinates). From now on, for each point x ∈ (Z/2) n , we will write:

1 (x) = {i ∈ 1, n ; x i ∈ Z}. Obviously, 1 (x) = 1, n \ 1 2 (x), and Card (1 (x)) = dim(H n (x)).

1, n

The set of integers between 1 and n

x An element of Z 2 n 1 (x)
The indexes of the integral coordinates

1 2 (x)
The complementary of 1 (x) in 1, n

The covering relation a b

The face a covers the face b opp c (b)

The opposite of b relatively to the face c

I A family of indexes in 1, n C A family of coefficients in (Z/2) H n {h,I,C} H n Z n (h) + i∈I λ i e i ; ∀i ∈ I, λ i ∈ C E β(z) \ (β(t) ∪ β(t )) Iso(u) H n Z n (u) + (Z(t m * ) -Z(z m * )) e m * C k n n! (n-k)! k!
{p ∈ β(c)} ⇔                                        ∀i ∈ 1 (Z n (p)) ∩ 1 2 (Z n (c)) , Z(p i ) ∈ Z(c i ) -1 2 , Z(c i ) + 1 2 , ∀i ∈ 1 (Z n (p)) ∩ 1 (Z n (c)) , Z(p i ) = Z(c i ), ∀i ∈ 1 2 (Z n (p)) ∩ 1 2 (Z n (c)) , Z(p i ) = Z(c i ), 1 2 (Z n (p)) ∩ 1 (Z n (c)) = ∅.
The proof of this assertion is postponed to section C at page 34 and an example of this proposition is depicted in Figure 22.

Covering and opposites

     1 (Z n (p)) ∩ 1 2 (Z n (c)) = {m} and Z n (p) ∈ Z n (c) -1 2 e m , Z n (c) + 1 2 e m .
Z 2 n , for i ∈ 1 (Z n (p)) ∩ 1 2 (Z n (c)) = {2}, we have that Z(p i ) = Z(c i ) -1 2 (first condition of Proposi- tion 12), for i ∈ 1 (Z n (p)) ∩ 1 (Z n (c)) = {1}, we have that Z(p i ) = Z(c i ) = 0 (second condition of Proposi- tion 12
), and the two other conditions of Proposition 12 are satisfied too because the intersections in the third and fourth conditions are empty sets.

The proof of this assertion is postponed to Section C at page 34. By Propositions 12 and 13, we obtain that:

Lemma 11. Let a, b, c be three elements of H n such that a = opp c (b), then there exists m ∈ 1, n such that:

-either Z n (a) = Z n (c) -1 2 e m and Z n (b) = Z n (c) + 1 2 e m , -or Z n (a) = Z n (c) + 1 2 e m and Z n (b) = Z n (c) -1 2 e m ,
which leads in both cases to:

Z n (a) + Z n (b) 2 = Z n (c).
Furthermore,

     1 (Z n (a)) = 1 (Z n (c)) {m} = 1 (Z n (b)) , 1 2 (Z n (a)) {m} = 1 2 (Z n (c)) = 1 2 (Z n (b)) {m}.
The proof of this assertion is postponed to Section C at page 35.

A very particular (n -dim(z) -2)-surface

Notations 8 (Subspaces of H n ). Let h be an element H n , and let be I be a family of indices into 1, n , and let be C a set of values in (Z/2). Then we define the following set:

H n {h,I,C} = H n Z n (h) + i∈I λ i e i ; ∀i ∈ I, λ i ∈ C .
It is then obvious that for any element h ∈ H n , we have the following relations:

Examples 1. For any element h ∈ H n ,              H n {h, 1 2 (Zn(h)),{-1 2 ,0, 1 2 }} = β(h), H n {h,1(Zn(h)),{-1 2 ,0, 1 2 }} = α(h), H n {h, 1,n ,(Z/2)} = H n .
We recall that a bijection f : X → Y is said to be an (order) isomorphism if for any

x 1 , x 2 ∈ X, then x 1 ∈ α X (x 2 ) is equivalent to f (x 1 ) ∈ α Y (f (x 2 )).
By Proposition 13, we obtain: Proposition 14. Let t, t , z three elements in H n such that t and t are opposite relatively to z. Now let define E := β(z) \ (β(t) ∪ β(t )), and let m * be the only coor-

dinate in 1, n such that m * ∈ 1 (Z n (t)) \ 1 (Z n (z)).
Then, the application Iso : E → H n such that, ∀u ∈ E,

Iso(u) := H n Z n (u) + (Z(t m * ) -Z(z m * )) e m * .
is an isomorphism from E to β(t). In other words, the order is preserved from E to β(t).

The proof of this assertion is postponed to Section C at page 35 and the notion of a "translation" in Khalimsky grids is depicted using the usual notion of translation in Z n (see Figure 24). As depicted on Figure 25, when t and t are opposite relatively to z, |E| depicted in red is isomorphic (as an order) to |β(t)| depicted in blue and to |β(t )| depicted in green.

By Lemma 11, we have the following lemma:

Lemma 12 (*). Assuming n ≥ 2, let z be an element of H n \ H n n and t, t be in H n dim(z)+1 such that they are opposite relatively to z. Then β (z) \ (β(t) ∪ β(t )) is a (n -dim(z) -2)-surface.
The proof of this assertion is postponed to Section C at page 37.

t z

Fig. 24: We depict here what is a "translation" in a 2D Khalimsky grid as a counterpart of the well-known notion of translation defined in Z n (and then Z 2 n by extension). The dark gray little squares on the left side represent the 0-faces z and the dark gray nodes on the right side represent their images by Z n of z. In the same way, the light gray rectangles on the left side represent a face t covering z and the light grey nodes on the right side represent the images of t by Z n . Since we cannot define naturally a "translation vector" in the 2D Khalimsky grid on the top left side, we go into Z 2 n on the top right side. Then we define in this last space the vector (Z n (t m * ) -Z n (z m * )) e m * (in red) utilized to orientate in the good direction the translation (from z to t); we recall that m * is the only coordinate where t and z differ. Then, we can observe that thanks to this translation we can transform all the elements p of the component encircled in blue (on the right down side) into the component encircled in green thanks to the operation p → p + (Z(t m * ) -Z(z m * )) e m * . Going back to the 2D Khalimsky grid thanks to the H n transform, we can then translate the suborder encircled in blue into the suborder encircled in green thanks to the

operation u → H n Z n (u) + (Z(t m * ) -Z(z m * )) e m * .
Observe that the order is preserved and then this translation is an isomorphism.

Definition and properties of the set T (u)

Notations 9. From now on, we will use the notation:

∀z ∈ H n \ H n n , ∀u ∈ β (z), T (u) := α(u) ∩ β (z) ∩ H n dim(z)+1 .
This set represents the (dim(z) + 1)-faces of the set α(u) ∩ β (z).

By proposition 12, we have: Lemma 13. For all z ∈ H n \H n n and for all u ∈ β (z),

t z t'
T (u) =    H n Z n (z) + (Z(u i ) -Z(z i )).e i ; i ∈ 1 (Z n (u)) ∩ 1 2 (Z n (z))   
The proof of this assertion is postponed to Section C at page 37 and is depicted in Figure 27.

Infimum

We have seen before the notion of supremum of the intersection of the closure of two faces in H n . Let us see now the infimum of the intersection of the openings of two elements a, b ∈ H n .

a ∨ b = inf (β(a) ∩ β(b)) .
The notion of supremum is illustrated in Figure 26.

Lemma 14. Let a, b be two elements of H n . Then,

{β(a) ∩ β(b) = ∅} ⇔ {a ∨ b is WD } .
Furthermore, when a∨b is WD, it satisfies the relations:

   a ∨ b = × i∈ 1,n (a i ∨ b i ), β(a ∨ b) = β(a) ∩ β(b).
The proof of this assertion is postponed to Section C at page 38.

Decomposition lemma

Now let us show that we can "decompose" any face of β (z) as a function of its (dim(z) + 1)-faces. By Lemma 13, we obtain that:

Lemma 15 (Decomposition lemma). Let z be a face in H n \ H n n .
Each face u ∈ β (z) can be decomposed in the following manner (see Figure 27):

u = v∈T (u) v.
The proof of this assertion is postponed to Section C at page 38.

Lemma 16. Let v, v be two elements of β (z) such that v = v . Then T (v) = T (v ).
Proof. We can easily prove this lemma by counterposition thanks to Lemma 15. By Proposition 12, we can prove the following assertion:

Lemma 17. Let v, f be two faces of H n such that f ∈ β(v). For all k ∈ dim(v), dim(f ) : Card (α(f ) ∩ β(v) ∩ H n k ) = C k-dim(v) dim(f )-dim(v) .
The proof of this assertion is postponed to Section C at page 39, and an example of counting of faces is depicted in Figure 28.

Antagonism and β N (z)

By Lemmas 2 and 4, and by Proposition 7, we obtain that: Fig. 30: In n-D with n ≥ 3, removing an element p of Z n and one of its k-antagonists p (both in red) with k ≥ 3 in a k-block S (the set of green and red nodes) does not separate this same block: S \ {p, p } (depicted by the green nodes) is 2n-connected.

Lemma 18 (*). Let us assume that n ≥ 2. Let z be in H n such that dim(z) ≤ n -2, and let a, b be in

H n n ∩ β (z). Then α (a) ∩ α (b) ∩ β (z) = ∅ implies that Z n (a) and Z n (b) are (n -dim(z))-antagonist into Z n .
The proof of this assertion is postponed to Section C at page 39 and a demonstration of this assertion is depicted in Figure 29. 5.9 Connectivity of S(z) minus two of its antagonists when dim(z) ≤ (n -3) Lemma 19. Let n ≥ 3 be an integer. Let z be in H n such that dim(z) ≤ n -3, and let p, p be in S(z)

such that p = antag S(z) (p ). Then S(z) \ {p, p } is 2n- connected into Z n .
The proof of this assertion is postponed to Section C at page 40 and two examples are given in Figure 30.

The proof that DWCness implies AWCness in n-D

We assume that X is a non-empty finite subset of Z n , that Y is its complement in Z n , that N is the boundary of the hit/miss-transform of X.

Notations 10. From now on, we define for any z ∈ N:

{F i } i∈I = CC(|β N (z)|).
In this section, we present lemmas relative to the suborder β N (z) in general, and properties relative to |β N (z)| when it is assumed not to be connected and/or each component of β N (z) is a (n-dim(z)-2)-surface.

Then, using these assertions, we prove that DWCness implies AWCness in n-D. Now let us present very briefly the proof which follows. We assume that X is DWC. Then, we show that in the "2D case" (dim(z) = n-2), the I miss (X) is AWC by a case-by-case study (we will show that |β N (z)| is a 0-surface). Thanks to this last property, we can start a proof by induction on the dimension of z (dim(z) ≤ (n -3)) where we want to prove that |β N (z)| is a (ndim(z) -2)-surface, that is, it is connected and for any

u ∈ β N (z), we have that θ β N (z) (u) is a (n-dim(z)-3)- surface.
This last property is easy to prove thanks to the induction hypothesis. However, proving that |β N (z)| is connected is much more complex and need the properties and lemmas detailed hereafter. Finally, thanks to the last lemma in the following subsection, we will see that when X is DWC, |β N (z)| is connected and we will end the proof thanks to the induction procedure.

Properties and lemmas relative to |β N (z)| under some constraints

Let us define two hypotheses that will be very useful in the sequel.

Hypothesis 1 (n ≥ 3). "There exists z ∈ N such that dim(z) ≤ (n -3) and satisfying that β N (z) is not connected".

Hypothesis 2. "Each component F i of β N (z) is a (n -dim(z) -2)-surface."
We are going to detail which properties we get when some of these hypotheses are true.

Basic lemmas

Lemma 20. We assume that X is a non-empty finite

subset of Z n , that Y is its complement in Z n , that N is the boundary of the hit/miss-transform of X. Then each component |F i | of |β N (z)| is closed in β (z).
The proof of this assertion is postponed to page 40.

Lemma 21. We assume that X is a non-empty finite subset of Z n , that Y is its complement in Z n , that N is the boundary of the hit/miss-transform of X. Then for two different components F i and F j of |β N (z)|:

β(F i ) ∩ F j = ∅, and α(F i ) ∩ F j = ∅.
The proof of this assertion is postponed to page 40.

Lemma 22. We assume that X is a non-empty finite subset of Z n , that Y is its complement in Z n , that N is the boundary of the hit/miss-transform of X. For each u ∈ β N (z), there exists one unique index i * ∈ I such that u ∈ F i * and it satisfies that:

               α F i * (u) = α β N (z) (u), β F i * (u) = β β N (z) (u), θ F i * (u) = θ β N (z) (u).
The proof of this assertion is postponed to page 40.

F j is a (n -dim(z) -2)-surface included in the (n -dim(z) -2)-surface |β (z) \ (β(t) ∪ β(t ))|
, they are equal. Since π must intersect F j to join t and t in β (z), we obtain a contradiction.

As a consequence of Hypotheses 1 and 2, and using Lemmas 12 and 20 and Proposition 6, we obtain: Property 1 (*). We assume that n ≥ 3 and that there exists z ∈ N such that dim(z) ≤ (n-3) and that β N (z) is not connected (Hypothesis 1). We assume also that each component of

β N (z) is a (n -dim(z) -2)-surface (Hypothesis 2). Then, ∀i ∈ I, ∀t ∈ H n dim(z)+1 , {t ∈ F i ⇒ opp z (t) ∈ F i } .
The proof of this assertion is postponed to page 40 and is depicted in Figure 31; its flow diagram is depicted in Figure 32. As a consequence of Hypothesis 1, and using Property 1, we obtain: Property 2. We assume that n ≥ 3 and that there exists z ∈ N such that dim(z) ≤ (n-3) and that β N (z) is not connected (Hypothesis 1). For each value i in I,

F i contains at most (n -dim(z)) (dim(z) + 1)-faces.
The proof of this assertion is postponed to page 41.

6.1.4 β N (z) is a closure of (n -1)-faces in β (z)
Lemma 23. Let x, y be two elements of Z n and S be a block such that x = antag S (y). Then for all z ∈ S:

   α(H n (x)) ∩ α(H n (y)) ⊆ α(H n (x)) ∩ α(H n (z)), α(H n (x)) ∩ α(H n (y)) ⊆ α(H n (z)) ∩ α(H n (y)).
The proof of this assertion is postponed to page 41. By Lemmas 2, 8 and 23, and Proposition 4, we obtain that: Lemma 24. Let X be a non-empty finite subset of Z n , Y its complement in Z n , and N be the boundary of the miss-tranform of X in H n . For each z ∈ N:

β N (z) = f ∈H n n-1 ∩β N (z) α(f ) ∩ β (z),
in other words, β N (z) is equal to the union of the closures (into β (z)) of its (n -1)-faces.

The proof of this assertion is postponed to page 41.

6.1.5 F i is the closure of some particular (n -1)-faces in β (z)

By Lemma 24, we obtain:

Lemma 25.
Let X be a non-empty finite subset of Z n , Y its complement in Z n , and N be the boundary of the miss-tranform of X in H n . For each z ∈ N, and for any i ∈ I, the component

F i of |β N (z)| is the closure in β (z)
of a set of (n -1)-faces, i.e.:

F i = f ∈H n n-1 ∩Fi α(f ) ∩ β (z).
The proof of this assertion is postponed to page 42.

f i = z i }. Then, dim(f ) = dim(z) + Card (I) .
The proof of this assertion is postponed to Section C at page 42.

As a consequence of Hypotheses 1 and 2, and using Lemmas 25 and 26, we obtain: Property 3. We assume that n ≥ 3 and that there exists z ∈ N such that dim(z) ≤ (n-3) and that β N (z) is not connected (Hypothesis 1). We assume also that each component of β N (z) is a (n -dim(z) -2)-surface (Hypothesis 2). Then, ∀i ∈ I, ∀m ∈ dim(z) + 1, n -1 :

F i ∩ H n m = ∅.
The proof of this assertion is postponed to page 42, and its flow diagram is depicted in Figure 33. Property 4. We assume that n ≥ 3 and that there exists z ∈ N such that dim(z) ≤ (n-3) and that β N (z) is not connected (Hypothesis 1). We assume also that each component of

β N (z) is a (n -dim(z) -2)-surface (Hypothesis 2). Now, ∀i ∈ I, ∀v ∈ F i , ρ(v, |F i |) = dim(v) -dim(z) -1.
The proof of this assertion is postponed at page 43. As a consequence of Hypotheses 1 and 2, and using Properties 3 and 4 and Lemmas 16, 17 and 20, we obtain: Property 5. We assume that n ≥ 3 and that there exists z ∈ N such that dim(z) ≤ (n-3) and that β N (z) is not connected (Hypothesis 1). We assume also that each component of β N (z) is a (n -dim(z) -2)-surface (Hypothesis 2). Then, for all i ∈ I, F i contains at least (n -dim(z)) (dim(z) + 1)-faces.

The proof of this assertion is postponed to page 43; its flow diagram is depicted in Figure 34. As a consequence of Hypotheses 1 and 2 and using Properties 2 and 5, we have: Property 6 (*). We assume that n ≥ 3 and that there exists z ∈ N such that dim(z) ≤ (n-3) and that β N (z) is not connected (Hypothesis 1). We assume also that each component of β N (z) is a (n -dim(z) -2)-surface (Hypothesis 2). Then, for all i ∈ I, F i contains exactly (n -dim(z)) (dim(z) + 1)-faces. As a consequence of Hypotheses 1 and 2, and using Property 6, we have: Property 7 (*). We assume that n ≥ 3 and that there exists z ∈ N such that dim(z) ≤ (n-3) and that β N (z) is not connected (Hypothesis 1). We assume also that each component of β N (z) is a (n -dim(z) -2)-surface (Hypothesis 2). Then,

Card (I) = 2.
The proof of this assertion is postponed to page 43. Notations 11. From now on, for each i ∈ I, we define:

T (F i ) = F i ∩ H n dim(z)+1 .
This set represents the (dim(z) + 1)-faces of F i .

As a consequence of Hypotheses 1 and 2, and using Properties 1 and 5, we obtain: Fig. 35: Some possible cases of T (F i ) when n = 3 and dim(z) = 0. Property 8. We assume that n ≥ 3 and that there exists z ∈ N such that dim(z) ≤ (n-3) and that β N (z) is not connected (Hypothesis 1). We assume also that each component of β N (z) is a (n -dim(z) -2)-surface (Hypothesis 2). For all i ∈ I, T (F i ) is equal to:

H n (Z n (z) + λ m e m ); m ∈ 1 2 (Z n (z)) ,
with each λ m being exactly one value in -1 2 , 1 2 . The proof of this assertion is postponed to page 43 and Figure 35 depicts the different possible cases of T (F i ) when n = 3 and dim(z) = 0.

6.1.12 Characteristical points of each F i under Hyp. 1 and 2

As a consequence of Hypotheses 1 and 2, and using Properties 6 and 8, we obtain that: Property 9. We assume that n ≥ 3 and that there exists z ∈ N such that dim(z) ≤ (n-3) and that β N (z) is not connected (Hypothesis 1). We assume also that

each component of β N (z) is a (n -dim(z) -2)-surface (Hypothesis 2). For all i ∈ I, t∈T (Fi) t exists in H n n ∩ β (z).
We will call this face the characteristical face of the component F i .

The proof of this assertion is postponed to page 44; its flow diagram is depicted in Figure 36. As a consequence of Hypotheses 1 and 2, using Properties 1 and 9 and Lemmas 14 and 15, we have: Property 10 (*). We assume that n ≥ 3 and that there exists z ∈ N such that dim(z) ≤ (n-3) and that β N (z) is not connected (Hypothesis 1). We assume also that each component of β N (z) is a (n -dim(z) -2)-surface (Hypothesis 2). For each i ∈ I:

F i ⊆ α   t∈T (Fi) t   .
Note that an intuition of this property is given in Figure 37 and its proof is given at page 44.

Formulas of each component F i under Hyp. 1 and 2

As a consequence of Hypotheses 1 and 2, using Properties 9 and 10 and Propositions 6 and 7, we have:

t 1 t 2 ∨t u t 3
Fig. 37: Assuming the hypothesis of Property 10, let t 1 , t 2 , t 3 be the three different (dim(z) + 1)-faces into F i (we depict the case dim(z) = (n -3)); these faces are not opposite to each others. Since β(t 1 ) ∩ β(t 2 ) is not empty, u = t 1 ∨ t 2 is WD. Also, since β(u) ∩ β(t 3 ) is not empty, u ∨ t 3 exists and is equal to

t∈T (Fi)
t. This term is equal to inf (β(u) ∩ β(t 3 )) and then belongs to β(u) ∩ β(t 3 ), this way, t 3 and u ∈ α

  t∈T (Fi) t   .
In the same way, t 1 and t 2 will belong to α(u)

⊆ α   t∈T (Fi) t   . Finally, t 1 , t 2 and t 3 belong to the closure of   t∈T (Fi) t   , and then F i is included in α   t∈T (Fi) t   .
Property 11 (*). We assume that n ≥ 3 and that there exists z ∈ N such that dim(z) ≤ (n-3) and that β N (z) is not connected (Hypothesis 1). We assume also that each component of β N (z) is a (n -dim(z) -2)-surface (Hypothesis 2). Then, From now on, we will use the following notation: Notations 12. We assume that n ≥ 3 and that there exists z ∈ N such that dim(z) ≤ (n-3) and that β N (z) is not connected (Hypothesis 1). We assume also that each component of β N (z) is a (n -dim(z) -2)-surface (Hypothesis 2). We denote: As a consequence of Hypotheses 1 and 2, using Property 12 and Lemma 19, we obtain that: Property 12 (*). We assume that n ≥ 3 and that there exists z ∈ N such that dim(z) ≤ (n -3) and that β N (z) is not connected (Hypothesis 1). We assume also that each component of

F i = α   t∈T (Fi) t   ∩ β (z).
a := t∈T (F1)
β N (z) is a (n -dim(z) - 2)-surface (Hypothesis 2). Then, Z n (a) and Z n (b) are (n -dim(z))-antagonist in Z n .
The proof of this assertion is postponed to page 45.

6.1.17 Hyp. 1 and 2 imply that X is not DWC As a consequence of Hypotheses 1 and 2, using Property 12 and Lemma 19, we obtain: Property 13 (*). We assume that n ≥ 3 and that there exists z ∈ N such that dim(z) ≤ (n -3) and that β N (z) is not connected (Hypothesis 1). We assume also that each component of β N (z) is a (n -dim(z) -2)-surface (Hypothesis 2). Then, X contains a critical configuration of dimension (n -dim(z)).

The proof of this assertion is postponed to page 45 and is depicted in Figure 39.

The key lemma

When we group together Hypotheses 1 and 2, we obtain that X is not DWC. It means that Hypothesis 1, Hypothesis 2 and { X is DWC } are incompatible by Property 13. In other words, when we know that X is DWC and that the components F i are (n -dim(z) -2)surfaces (Hypothesis 2), then β N (z) is connected (because Hypothesis 1 is false). It leads to the following lemma, crucial for the proof that DWCness implies AWCness.

Lemma 27 (*). Let X be a non-empty finite subset of Z n , Y its complement in Z n , and N be the boundary of the miss-transform of X in H n . For each z ∈ N, let us consider the suborder β N (z) . When X is DWC and when each component Let n be an integer satisfying n ≥ 2. Let us assume that X is a non-empty finite subset of Z n , that Y is its complement in Z n , and that N is the boundary of the miss-transform of X in H n .

F i of β N (z) is a (n-dim(z)-2)- surface (Hypothesis 2), then β N (z) is connected.
We want to prove that the fact that X is DWC implies that I miss (X) is AWC too. For this aim, let us assume that X is DWC. Proving that I miss (X) is AWC is equivalent by Lemma 10 to prove that for any z ∈ N, we have the property that

|β N (z)| is a (n -dim(z) -2)- surface.
In other words, it is sufficient to prove that for any k ∈ 1, n , the property:

(P k ) = ∀z ∈ N ∩ H n n-k , |β N (z)| is a (n -2 -dim(z)) -surface ,
is true. We will proceed by induction.

When k = 1, dim(z) = n -1, and then β N (z) = ∅, then |β N (z)| is a (-1)-surface, which proves that (P 1 ) is true.

When k = 2, dim(z) = n -2, and then, since X is DWC, we have only two possible cases (modulo rotations and symmetries) (see Figure 42). In both DWC cases, β N (z) is made of two faces which are not neighbors, and then |β N (z)| is a 0-surface. Note that Figure 42 shows the case for n = 2 but the reasoning is exactly the same for any n ≥ 2. Now, for the case k ≥ 3, we can decompose (P k ) this way: since (n -dim(z) -2) ≥ 1, (P k ) is equivalent to say that:

(P A k ) = ∀z ∈ N ∩ H n n-k , ∀u ∈ β N (z), θ β N (z) (u) is a (n -dim(z) -3)-surface and (P B k ) = ∀z ∈ N ∩ H n n-k , |β N (z)| is connected are true.
To prove that these two properties are true, we are going to prove that for each k ≥ 3, (P A k ) is true thanks to the induction hypothesis, that (P A k ) implies Hypothesis 2, and that Hypothesis 2 implies (P B k ).

Let us then prove that assuming that (P ) is true for any ∈ 1, k -1 (induction hypothesis), the property

I

The indexes of the components of

|β N (z)| {F i } i∈I The components of |β N (z)| T (F i ) The (dim(z) + 1)-faces of F i a First characteristical point of β N (z) b Second characteristical point of β N (z) (P k ) ∀z ∈ N ∩ H n n-k , |β N (z)| is a (n -2 -dim(z)) -surface (P A k ) ∀z ∈ N ∩ H n n-k , ∀u ∈ β N (z), θ β N (z) (u) is a (n -dim(z) -3)-surface (P B k ) ∀z ∈ N ∩ H n n-k , |β N (z)| is connected
θ β N (z) (u) = β β N (z) (u) * α β N (z) (u) = β (u) ∩ β (z) ∩ N * α β N (z) (u) = β (u) ∩ N * α β N (z) (u) = β N (u) * α β N (z) (u) = β N (u) * α (u) ∩ β N (z) = β N (u) * α (u) ∩ β (z) ∩ N = β N (u) * α (u) ∩ β (z)
However, by the induction hypothesis, β N (u) is a (n -dim(u) -2)-surface, and by Proposition 7,

α (u) ∩ β (z) is a (dim(u) -dim(z) -2)-surface. It means by Propo- sition 2 that θ β N (z) (u) is a (n -dim(z) -3)-surface, (P A k ) is then true.
Let us prove now that (P A k ) shows Hypothesis 2. For any i ∈ I, the component |F i | of β N (z) is connected by definition. Also, by Lemma 22, for any u ∈ F i , we have that:

θ Fi (u) = θ β N (z) (u) ,
which is a (n -dim(z) -3)-surface (see before). Then |F i | is a (n-dim(z)-2)-surface, and then Hypothesis 2 is true. Now, to prove that (P B k ) is true, we just have to apply Lemma 27, β N (z) is then connected. Indeed, as detailed in the proof of Property 13, when Hypotheses 1 and 2 are true, X contains a critical configuration. However, Lemma 27 tells that when we have X DWC and when furthermore Hypothesis 2 is true, we obtain that Hypothesis 1 is false, which explains the connectedness of β N (z) , and then (P B k ) is true.

Since (P A k ) and (P B k ) are true, (P k ) is then true.

By induction, (P k ) is then true for any k ∈ 1, n , and then I miss (X) (and I hit (X) since their boundaries are the same) are AWC, which leads to the second main result of this paper: Theorem 2. Let X be a digital subset of Z n . Then, when X is DWC, its miss-transform and equivalently its hit-transform are well-composed in the sense of Alexandrov. From now on, we will call gray-level image on Z n any mapping from Z n to Z, and gray-level image on H n any plain map from H n to H 1 (the definition is given hereafter). So, in this section, we show how we extend Theorems 1 and 2 from sets to gray-level images based on cross-section topology [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] using span-based immersions [START_REF] Géraud | A quasi-linear algorithm to compute the tree of shapes of n-D images[END_REF][START_REF] Najman | Discrete setvalued continuity and interpolation[END_REF].

The flow diagram of

Plain maps

Table 8 summarizes the new notations inserted in this section.

Let us now recall some mathematical background coming from set-valued analysis [START_REF] Aubin | Set-valued analysis[END_REF][START_REF] Najman | Discrete setvalued continuity and interpolation[END_REF] to be able to

|X|, |Y |

Two Alexandrov spaces

F : X → Y An application from X to Y F : X Y A set-valued map from X to Y U : X Y A plain map from X to Y D(F ) The domain of F h A face of H n ϕ(h) z + 1 2 if h = {z, z + 1}, z if h = {z}, ≤ ϕ
The natural order relation on define the class of gray-level images on H n we will work with in this paper.

H 1 [U λ] {x ∈ H n ; ∃y ∈ U (x), y ≥ λ} [U λ] {x ∈ H n ; ∀y ∈ U (x), y > λ} [U λ] {x ∈ H n ; ∃y ∈ U (x), y ≤ λ} [U λ] {x ∈ H n ; ∀y ∈ U (x), y < λ} u : Z n → Z A gray-level image [u ≥ λ] {x ∈ Z n ; u(x) ≥ λ} [u > λ] {x ∈ Z n ; u(x) > λ} [u ≤ λ] {x ∈ Z n ; u(x) ≤ λ} [u < λ] {x ∈ Z n ; u(x) < λ}
Let |X| := (X, α X ) and |Y | := (Y, α Y ) be two Alexandrov spaces; as usual, the operators β X and β Y will denote the inverse of α X and α Y respectively. Since α X and α Y are closures in X and Y , β X and β Y denote the openings in these same spaces.

An application F from X to Y such that for any x ∈ X, F (x) is a subset of Y is called a set-valued map, and we denote this fact by F : X Y . The

domain of F is the set D(F ) ⊆ X such that ∀x ∈ X, F (x) = ∅ ⇔ x ∈ D(F ). A set-valued map F : X R is said to be upper semi-continuous (USC) at x ∈ D(F ) if ∀x ∈ β X (x), F (x ) ⊆ β Y (F (x)). A set-valued map is said to be upper semi-continuous (USC) if it is USC at each point x ∈ D(F ).
A set X is said degenerate if there exists some p such that X = {p}. A set-valued USC map F : X Y is said to be a quasi-simple map if for any x ∈ D(F ), F (x) is a connected set and furthermore, for any

x ∈ D(F ) such that {x} = β(x), F (x) is degenerate. An open point p ∈ H n is a face of H n satisfying that β(x) = {x}. A quasi-simple map F : X
Y is said to be a simple map if for any quasi-simple map F 2 : X Y such that F and F 2 are equal on open points, then for any

x ∈ D(F ), F (x) ⊆ F 2 (x). A set-valued map F : X Y is said closed-valued if for any x ∈ D(F ), F (x) is a closed subset of Y , and is said interval-valued if for any x ∈ D(F ), F (x) is connected. A set-valued map F : X
Y is said to be a plain map if it is a closed-valued interval-valued simple map.

Threshold sets and AWCness of a plain map

Let us define a bijection ϕ :

H 1 → (Z/2): ∀h ∈ H 1 , ϕ(h) =      z + 1 2 if h = {z, z + 1}, z if h = {z},
Now, let us define an order relation ≤ ϕ on H 1 : we will say, for

h 1 , h 2 ∈ H 1 , that h 1 ≤ ϕ h 2 if ϕ(h 1 ) ≤ ϕ(h 2 )
. This way, as in [START_REF] Najman | Discrete setvalued continuity and interpolation[END_REF],

. . . ≤ ϕ {0} ≤ ϕ {0, 1} ≤ ϕ {1} ≤ ϕ . . . .
We will abusively omit the symbol ϕ when no confusion may arise. Now that we have introduced an order relation on H 1 , we can define the threshold sets [START_REF] Najman | Discrete setvalued continuity and interpolation[END_REF] of a plain map U : H n H 1 corresponding to λ ∈ H 1 as being the following sets:

[U λ] = {x ∈ H n ; ∃y ∈ U (x), y ≥ λ}, [U λ] = {x ∈ H n ; ∀y ∈ U (x), y > λ}, [U λ] = {x ∈ H n ; ∃y ∈ U (x), y ≤ λ}, [U λ] = {x ∈ H n ; ∀y ∈ U (x), y < λ}.
Definition 7. Assuming that a plain map U : H n H 1 is given, we say that U is well-composed in the sense of Alexandrov [START_REF] Najman | Discrete setvalued continuity and interpolation[END_REF] (AWC) if the connected components of the boundary of each of its thresholds sets are discrete (n -1)-surfaces.

Span-based immersions

0 1 2 {0} [0,1] [0,2] {1} [1,2] {2}
Fig. 44: A span-based immersion U (on the right side) of a gray-level image u (depicted on the left side). We recall that for any finite subset S of Z, assuming that we know the minimum m := min(S) and the maximum M := max(S) of S, the span of S into H 1 is denoted by Span(S) and is defined as: {{m}, {m, m + 1}, {m + 1}, . . . , {M -1, M }, {M }}, when m < M and as {{m}} when m = M . Obviously, Span(S) is then a closed connected subset of H 1 .

∂[U {0}] ∂[U {1}] ∂[U {2}] ∂[U {0}] ∂[U {1}] ∂[U {2}]
Then, the span-based immersion of a gray-level image u : Z n → Z is the plain map U : H n H 1 defined such that ∀z ∈ H n :

U (h) = Span {u(Z n (q)); q ∈ β(h) ∩ H n n } .
Assuming that for a given h ∈ H n , U (h) is closed and connected, we will identify U (h) and its associated interval in Z defined as [m, M ] where m := min(U (h)) and M := max(U (h)). For example, we will identify U (h) := {{0}, {0, 1}, {1}} and the interval [0, 1]. Figure 44 shows an example of immersion of a graylevel image u; as depicted on Figure 45, the immersion of u is AWC. Based on 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], we can extend easily well-composedness from subsets of Z n to gray-level images on Z n . Let u : Z n → Z be a gray-level image, and let λ ∈ Z be a given threshold. The large upper, strict upper, large lower, and strict lower threshold sets corresponding to λ are respectively:

Extension of DWCness to gray-level images

[u > 0] [u > 1] [u > 2] [u < 0] [u < 1] [u < 2]
[u ≥ λ] = {x ∈ Z n ; u(x) ≥ λ}, [u > λ] = {x ∈ Z n ; u(x) > λ}, [u ≤ λ] = {x ∈ Z n ; u(x) ≤ λ}, [u < λ] = {x ∈ Z n ; u(x) < λ}.
Definition 8. A gray-level image u : Z n → Z is said digitally well-composed [START_REF] Boutry | How to make n-D functions digitally well-composed in a self-dual way[END_REF][START_REF] Latecki | Well-composed sets[END_REF] (DWC) if for every threshold λ ∈ Z, all its threshold sets are digitally well-composed.

Figure 46 depicts the threshold sets of the gray-level image depicted in Figure 44: this image is DWC since its threshold sets do not contain any critical configuration.

The proof for gray-level images

For sets, we have proved that a digital subset X of Z n satisfies that its miss-transform (or equivalently its hittransform) is AWC iff X is DWC. Now, we are going to prove that the span-based immersion U of a given gray-level image u : Z n → Z is AWC iff u is DWC.

Lemma 28. Let u : Z n → Z be a gray-level image and let U : H n H 1 be its span-based immersion. Then, for any λ ∈ Z, we have the following equalities:

             Int(α(H n ([u > λ]))) = [U {λ}], Int(α(H n ([u < λ]))) = [U {λ}], α(H n ([u ≥ λ]))) = [U {λ}], α(H n ([u ≤ λ]))) = [U {λ}].
Proof. Let λ be an integer and let us begin with the proof that [U {λ}] is equal to the miss-transform of

[u > λ]. Let h be a face of H n . Then, h ∈ [U {λ}], ⇔ U (h) {λ}, ⇔ Span {u(Z n (h )); h ∈ β(h) ∩ H n n } {λ}, ⇔ min {u(Z n (h )); h ∈ β(h) ∩ H n n } > λ, ⇔ ∀h ∈ β(h) ∩ H n n , u(Z n (h )) > λ, ⇔ ∀h * ∈ β(h), ∀h n ∈ β(h * ) ∩ H n n , u(Z n (h n )) > λ, ⇔ ∀h * ∈ β(h), ∀h n ∈ β(h * ) ∩ H n n , Z n (h n ) ∈ [u > λ], ⇔ ∀h * ∈ β(h), ∀h n ∈ β(h * ) ∩ H n n , h n ∈ H n ([u > λ]), ⇔ ∀h * ∈ β(h), β(h * ) ∩ H n n ⊆ H n ([u > λ]), ⇔ ∀h * ∈ β(h), β(h * ) ∩ H n n ∩ H n ([u > λ]) = ∅, ⇔ ∀h * ∈ β(h), β(h * ) ∩ H n ([u > λ]) = ∅, ⇔ ∀h * ∈ β(h), ∃h ∈ H n ([u > λ]) ∩ β(h * ), ⇔ ∀h * ∈ β(h), ∃h ∈ H n ([u > λ]), h ∈ β(h * ), ⇔ ∀h * ∈ β(h), ∃h ∈ H n ([u > λ]), h * ∈ α(h ), ⇔ ∀h * ∈ β(h), h * ∈ α(H n ([u > λ])), ⇔ β(h) ⊆ α(H n ([u > λ])), ⇔ h ∈ Int (α (H n ([u > λ]))) ,
which is equivalent to say that h belongs to the misstransform of [u > λ]. Then the first equality is proved. We deduce the second equality by following the same reasoning.

The third equality follows from the fact that, by using Lemma 9 with X = H n ([u ≥ λ]) and Y = H n ([u < λ]), we obtain:

α(H n ([u ≥ λ]))) = H n \ Int(α(H n ([u < λ]))), = H n \ [U {λ}], = [U {λ}].
The fourth equality follows the dual reasoning.

Let us now announce the main result of this paper about gray-level images. Proof. This result follows from Lemma 28 and Theorems 1 and 2.

Applications of well-composedness to image processing

An important result of the equivalence between AWCness and DWCness for n-D cubical images is that finally all the interpolations [START_REF] Boutry | A Study of Well-Composedness in n-D[END_REF][START_REF] Boutry | How to make n-D functions digitally well-composed in a self-dual way[END_REF][START_REF] Mazo | Digital imaging: A unified topological framework[END_REF] which provide DWC images provide at the same time AWC images, which is surprising because intuitively we could think that it is harder to make an AWC image than a DWC Image (see [START_REF] Boutry | How to make n-D plain maps defined on discrete surfaces Alexandrov-well-composed in a self-dual way[END_REF] for an AWC interpolation on discrete surfaces).

A second important result is that every application existing on DWC images can be applied on AWC images, like the ones described hereafter. A third result, that we found very important too, is that in some way we unify the theory behind the paper of Najman and Géraud [START_REF] Najman | Discrete setvalued continuity and interpolation[END_REF] and the computing counterpart of Géraud et al. [START_REF] Géraud | A quasi-linear algorithm to compute the tree of shapes of n-D images[END_REF], both about the tree of shapes: the first uses AWCness to explain that it is a sufficient condition to the existence of the tree of shapes, when the second explains that the sufficient condition so that the graph of shapes computed with a front propagation algorithm is a tree is DWCness. For these three reasons, we propose to expose some of the main applications relative to these flavors of well-composedness.

The first interesting applications concerns the treebased shape-space of Xu et al. [START_REF] Xu | Morphological filtering in shape spaces: Applications using tree-based image representations[END_REF], where we decompose an image into a tree based on its well-composed interpolation [START_REF] Boutry | How to make n-D functions digitally well-composed in a self-dual way[END_REF]. Using a filtering procedure in the shapespace, we can remove components in the image that are not relevant, and then make object segmentation in images (see Figure 47). This paradigm of shape-space has been extended to graph-based shape-spaces [START_REF] Boutry | Connected filters on generalized shape-spaces[END_REF] which allows us to segment clusters of objects which are geometrically related in the image like characters in a document image (see Figure 48).

A second approach using well-composedness is to compute interpolations of the Laplacian of an image [START_REF] Huynh | Morphology-based hierarchical representation with application to text segmentation in natural images[END_REF]; the zero-level-lines of the Laplacian are then a good approximation of the boundaries of the object in an image (see Figure 49).

A third approach which need well-composedness is the Dahu pseudo-distance [START_REF] Thierry Géraud | Introducing the dahu pseudo-distance[END_REF] where we compute the distance between two points in an image based on the distance in the tree of shapes between the two shapes containing these two points (see Figure 50). This pseudodistance has been shown as being a good approximation of the well-known minimum-barrier distance (MBD). Fig. 49: Starting from a gray-level image (see (a)), we compute 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]. Fig. 50: Computation of the Dahu pseudo-distance [START_REF] Thierry Géraud | Introducing the dahu pseudo-distance[END_REF]: the distance between the components B and F depends on the number of level lines that are crossed in the image when we go from the interior of B to the interior of F in the domain of the image (see the left side), this distance is easily computable by computing the length of the path joining the corresponding nodes B and F in the tree (see the right side). A direct application of this Dahu pseudo-distance can be found in [START_REF] Ôn | Saliency-based detection of identy documents captured by smartphones[END_REF] (see Figure 51) and corresponds to a saliency-based detection of identity documents captured by smartphones.

Conclusion

In this paper, we proved that DWCness and AWCness are equivalent in n-D. Thanks to cross-section topology, we have easily extended this result to gray-level images.

We say that an image is continuous well-composed (CWC) when the boundary of its continuous analog [START_REF] Longin | 3D well-composed pictures[END_REF] is a topological (n-1)-manifold. This property is known to be equivalent to DWCness in 2D and 3D; their relation in 4D and beyond is an open question. Our next step could then be to study the relation between DWCness and CWCness in n-D.

A Proofs of Section 3

Lemma 1. Let c be a value in (Z/2) \ Z, and let y be a value in Z. Then,

y ∈ c - 1 2 , c + 1 2 ⇔ β(H(y)) ⊆ β(H(c)).
In other words, when H(c) is a 0-face of H 1 , y is a neighbor of c in (Z/2) iff the opening of H(y) is included in the opening of H(c).

Proof. When c belongs to (Z/2) \ Z,

H(c) = c + 1 2 ∈ H 1 0 ,
and then we have:

S = Z n (β(H n (c)) ∩ H n n ).
Proof. This proof is depicted in Figure 13. Now, we can remark that:

S =      c + i∈ 1 2 (c) λ i e i ; ∀i ∈ 1 2 (c), λ i ∈ - 1 2 , 1 2
     .
Then, for any y ∈ S,

-if i ∈ 1, n \ 1 2 (c), then y i = c i , -if i ∈ 1 2 (c) such that λ i = 1/2, then y i = c i + 1/2 with c i ∈ (Z/2) \ Z, -and if i ∈ 1 2 (c) such that λ i = -1/2, hence y i = c i -1/2 with c i ∈ (Z/2) \ Z.
Then, for any i ∈ 1, n , by Lemma 1, H(y i ) ∈ β(H(c i )), and then

H n (y) ∈ β(H n (c)). Because y ∈ Z n , H n (y) ∈ H n n , and then H n (y) ∈ β(H n (c)) ∩ H n n , which leads to y ∈ Z n (β(H n (c)) ∩ H n n ). Conversely, let us assume that y ∈ Z n (β(H n (c)) ∩ H n n ). Then, H n (y) ∈ β(H n (c))∩H n
n , which means that y ∈ Z n , and H n (y) ∈ β(H n (c)). In other words, for any i ∈ 1, n , H(y i ) ∈ β(H(c i )). Two cases are then possible: Proof. Let a 1 , b 1 be two elements of H 1 , then it is easy to show by a case-by-case study (see Figure 52 for the different possible cases) that:

c i ∈ Z, hence y i = c i , or c i ∈ (Z/2) \ Z and thus by Lemma 1, y i ∈ {c i -1 2 , c i + 1 2 }. This way, y ∈ S.
a ∧ b = (× i∈ 1,n a i ) ∧ (× i∈ 1,n b i ) = × i∈ 1,n (a i ∧ b i ),
   {α(a 1 ) ∩ α(b 1 ) = ∅} ⇔ {a 1 ∧ b 1 is WD} , {a 1 ∧ b 1 WD} ⇒ {α(a 1 ∧ b 1 ) = α(a 1 ) ∩ α(b 1 )} .
Now let us treat the case where a, b ∈ H n . For this aim, let us remark that:

α(a) ∩ α(b) = α(× i∈ 1,n a i ) ∩ α(× i∈ 1,n b i ), = ⊗ i∈ 1,n α(a i ) ∩ ⊗ i∈ 1,n α(b i ), = ⊗ i∈ 1,n (α(a i ) ∩ α(b i )) .
Then, when α(a) ∩ α(b) = ∅, we obtain that for any i ∈ 1, n , α(a i ) ∩ α(b i ) is not empty, which implies that a i ∧ b i is WD and that we have:

α(a i ) ∩ α(b i ) = α(a i ∧ b i ).
This way, α(a) ∩ α(b) is equal to ⊗ i∈ 1,n α(a i ∧ b i ), and then is equal to:

α(× i∈ 1,n (a i ∧ b i )),
and then the supremum of α(a

) ∩ α(b) is × i∈ 1,n (a i ∧ b i ).
We can then denote by a ∧ b this last term. Furthermore, it satisfies α(a ∧ b) = α(a) ∩ α(b).

Conversely, when a∧b is WD, the supremum of α(a)∩α(b) exists and thus α(a) ∩ α(b) = ∅. Lemma 3. Let x, y be two elements of Z n . Then, x and y are antagonists in a block of Z n of dimension k ∈ 0, n iff:

           Card {m ∈ 1, n ; x m = y m } = n -k, (1)
and

Card {m ∈ 1, n ; |x m -y m | = 1} = k. (2)
In other words, x and y are k-antagonists iff they have (n-k) equal coordinates and that the remaining coordinates differ from 1.

Proof. Let x, y be two elements of Z n satisfying ( 1) and ( 2) with k ∈ 0, n . Now, let us take c ∈ Z n such that ∀i ∈ 1, n , c i := min(x i , y i ), and let us define:

I x := {i ∈ 1, n ; c i = x i } ,
and

I y := {i ∈ 1, n ; c i = y i } .
By [START_REF] Alexandrov | Diskrete Räume[END_REF], there are (n -k) coordinates i such that x i = y i = c i , and then k coordinates i such that x i = c i or y i = c i . Then,

Card(I x ∪ I y ) = k.
Since by [START_REF] Alexandrov | Combinatorial topology[END_REF] we have:

   x = c + i∈I x e i , y = c + i∈I y e i ,
then x and y belong to S(c, F ) where

F := e i ∈ B ; i ∈ I x ∪ I y
is of cardinality k. Furthermore, the L 1 norm of x -y is equal to k, and thus x and y maximize the L 1 -distance between two points into S(c, F ). So, x and y are antagonists in S(c, F ).

Conversely, let us assume that x, y ∈ Z n are antagonists in a block S(c, F ) of dimension k ∈ 0, n . For any i ∈ 1, n , e i belongs to F and hence |x i -y i | = 1, or it does not belong to F and hence x i = y i . Since Card(F ) = k by hypothesis, this concludes the proof. Proof. The intuition of the proof is depicted in Figure 14 for the 3D case. Let p, p be defined in Z n and k ∈ 0, n such that p and p are antagonists in a block of dimension k ∈ 0, n . By Lemma

z i = H(p i ), then z i , z i ∈ H 1 1 .
When i is in I, p i = p i -1, and α(z i ) ∩ α(z i ) = {{p i }}, and then

z i ∧ z i = {p i } ∈ H 1 0 , or p i = p i + 1, and α(z i ) ∩ α(z i ) = {{p i }} and then z i ∧z i = {p i } ∈ H 1 0 . When i belongs to 1, n \ I, z i = z i and α(z i ) ∩ α(z i ) = α(z i ) and then z i ∧ z i = z i ∈ H 1 1 . It follows then that × i∈ 1,n (z i ∧ z i ) belongs to H n n-k . Also, since α(z i )∩α(z i ) = ∅ for any i ∈ 1, n , α(H n (p))∩ α(H n (p )) is equal to ⊗ i∈ 1,n (α(z i ) ∩ α(z i ))
which is nonempty, and then, by Lemma 2, H n (p) ∧ H n (p ) exists and is equal to × i∈ 1,n (z i ∧ z i ), which belongs to H n n-k .

Let us now prove the converse implication. Let p, p be two points of Z n , and z = H n (p), z = H n (p ) such that z ∧ z is WD and belongs to H n n-k . Then, we define

I = {i ∈ 1, n ; z i ∧ z i ∈ H 1 0 },
p + p 2 = Z n (H n (p) ∧ H n (p )).
This is equivalent to say that for any i ∈ 1, n , we have

p i +p i 2 = Z(H(p i ) ∧ H(p i )) by Lemma 2.
Let us rename the following equality:

H(p i ) ∧ H(p i ) = {p i , p i + 1} ∧ {p i , p i + 1} (P ).
Since p and p are (3 n -1)-neighbors in Z n or equal, they satisfy for any i ∈ 1, n that p i ∈ {p i -1, p i , p i + 1}. Then we have 3 possible cases:

p i = p i -1, and then by (P ):

H(p i ) ∧ H(p i ) = {p i -1, p i } ∧ {p i , p i + 1} = {p i },
and then Z(H(p i ) ∧ H(p i )) = p i -1 2 = p i +p i 2
, or we have p i = p i -1, and then a symmetrical reasoning leads to the same result, or p i = p i , and then the result is immediate.

The proof is done.

Proposition 5. Let S be a block and let p, p ∈ S be any two antagonists in S. Then the center of the block S is equal to p+p 2 . Furthermore, its image by

H n in H n is equal to H n (p) ∧ H n (p ).
Proof. Starting from the two antagonists p, p in S, we can compute z ∈ Z n and F ⊆ B such that S = S(z, F ). In fact, for all i ∈ 1, n , z i = min(p i , p i ), and F = {e i ; i ∈ 1, n , p i = p i }. Then, it is clear that:

p = (p -z) + z = z + p i =z i e i ,
and in the same manner:

p = (p -z) + z = z + p i =z i e i .
Then,

p + p = 2z + f ∈F f, which shows that p+p 2
is the center of S in (Z/2) n . The second part of the proposition follows from Lemma 5. Lemma 6. Let p be an element of Z n , then we can reformulate the squared closure of H n (p) in the following manner:

α (H n (p)) = v∈N * 3 n -1 (p) α(H n (p) ∧ H n (v)).
Proof. This proof is depicted in Figure 15. Let p be an element of Z n . Then, let us compute the value of α(H n (p)):

α(H n (p)) = α H n (× i∈ 1,n p i ) , = α × i∈ 1,n H(p i ) , = ⊗ i∈ 1,n α (H(p i )) , = ⊗ i∈ 1,n α ({p i , p i + 1}) , = ⊗ i∈ 1,n {{p i }, {p i , p i + 1}, {p i + 1}}, = ⊗ i∈ 1,n H p i -1 2 , H(p i ), H p i + 1 2 , = ⊗ i∈ 1,n H({p i -1 2 , p i , p i + 1 2 }), = H n ⊗ i∈ 1,n {p i -1 2 , p i , p i + 1 2 } , = H n q ∈ Z 2 n ; q -p ∞ ≤ 1 2 .
We can deduce that:

α (H n (p)) = H n (q) ; q ∈ Z 2 n , q -p ∞ = 1 2 , = f ∈ H n ; Z n (f ) -p ∞ = 1 2 . However, Z n (f ) -p ∞ = 1 2 is equivalent to: v -p ∞ = 1 with v := 2Z n (f ) -p. Then, α (H n (p)) is equal to the set of elements f ∈ H n satisfying v ∈ N * 3 n -1 (p) and f = H n v+p 2
. By Lemma 5, we obtain that:

α (H n (p)) = H n (v) ∧ H n (p) ∈ H n ; v ∈ N * 3 n -1 (p) ,
which leads to the required formula by applying the α operator on both sides.

Lemma 7. Let S be a block in Z n of dimension k ≥ 2. Now, let p, p be two antagonists in S, and v be a 2n-neighbor of p in S. Then, we have the following relation:

H n (p) ∧ H n (p ) ∈ α(H n (p) ∧ H n (v)
× i∈ 1,n (H(p i ) ∧ H(p i )).
Likewise, the second term is equal to:

⊗ i∈ 1,n (α(H(p i )) ∩ α(H(v i ))) .
Then it is sufficient to show that for all i ∈ 1, n :

H(p i ) ∧ H(p i ) ∈ α(H(p i )) ∩ α(H(v i )). (P )
Let us define

I = {i ∈ 1, n ; p i = p i } .
Since v is a 2nneighbor of p into S, there exists an index i * in I such that v i * = p i * , i.e., v i * = p i * , and ∀i ∈ 1, n \{i * }, v i = p i . When i ∈ 1, n \ I or when i = i * , the property (P ) is obviously true. When i ∈ I \ {i * }, then v i = p i , which implies:

α(H(p i )) ∩ α(H(v i )) = α(H(p i )) = {{p i }, {p i + 1}, {p i , p i + 1}} . When p i = p i -1, we obtain H(p i ) ∧ H(p i ) = {p i },
and when

p i = p i + 1, we obtain H(p i ) ∧ H(p i ) = {p i + 1}. Then, in both cases, H(p i ) ∧ H(p i ) ∈ α(H(p i )) ∩ α(H(v i )).
The proof is done. Proof. This proof can be observed in Figure 16. Let us proceed by counterposition. Let y be an element of Z n such that:

α(H n (y)) ∩ β(z * ) = ∅.
Then, for all i ∈ 1, n , α(H(y i )) ∩ β(z * i ) is not empty. Now, let us show that y belongs to S. Since there exists p i ∈ α(H(y i )) ∩ β(z * i ), then H(y i ) ∈ β(p i ) and p i ∈ β(z * i ), which leads to H(y i ) ∈ β(z * i ) by transitivity of the operator β, and then H n (y) ∈ β(z * ). Since y ∈ Z n , H n (y) ∈ H n n , and then Heredity (k ≥ 1): we assume that when two (k-1)-surfaces satisfy an inclusion relationship, that is, when they are nested, then they are equal. Now, let |X| and |Y | be two k-surfaces, k ≥ 1, such that |X| is a suborder of |Y |. Then, for all x ∈ X, x ∈ Y and so we can write:

H n (y) ∈ β(z * )∩H n n , which is equivalent to y ∈ Z n (β(z * ) ∩ H n n ),
θ X (x) = θ (x) ∩ X ⊆ θ (x) ∩ Y = θ Y (x)
because X ⊆ Y . However, |θ X (x)| and |θ Y (x)| are (k -1)surfaces and |θ X (x)| is a suborder of |θ Y (x)|, then we have thanks to the induction hypothesis:

|θ X (x)| = |θ Y (x)|.
Now, let us assume that we have:

X Y (P ).
Then let x be a point of X and y a point of Y \ X. Since |Y | is connected (because it is an k-surface with k ≥ 1), it is path-connected, and so x, y ∈ Y implies that there exists a path π joining them into Y . This way, there exist x ∈ X and y ∈ Y \ X such that:

y ∈ θ (x ).
In other words, y ∈ θ Y (x ), where θ Y (x ) is equal to θ X (x ) since x ∈ X. This leads to y ∈ X. We obtain a contradiction on (P ). Thus we have X = Y . Supplying these two posets with ⊆, we obtain |X| = |Y |.

By applying the induction on k until n, this property is true for any finite k ∈ 0, n .

Corollary 1. Let |X 1 | and |X 2 | be two k-surfaces, k ≥ 0, with X 1 ∩ X 2 = ∅. Then |X 1 X 2 | is not a k-surface.
In other words, the disjoint union of two k-surfaces, k ≥ 0, is not a k-surface.

Proof. Let |X 1 | and |X 2 | be two disjoint k-surfaces in H n with k ∈ 0, n . If we assume that |X 1 X 2 | is a k-surface, then X 1 ⊆ X 1 X 2 implies by Proposition 6 that X 1 = X 1 X 2 , which is a contradiction since X 2 is non-empty. Then |X 1 X 2 | is not a k-surface. Proposition 7. Let a, b be two elements of H n with a ∈ β (b). Then |α (a) ∩ β (b)| is a (dim(a) -dim(b) -2)- surface. Proof. Since |H n | is an n-surface, then |α (a)| is a (ρ(a, |H n |)-
ρ(b, |α (a)|) = ρ(b, |H n |) = dim(b),
the proof is done.

B Proofs of Section 4

Proposition 8. The sets α(X ) and α(Y) are regular closed sets.

Proof. Let us prove that α(X ) is a regular closed set, the same reasoning applies for α(Y). The fact that

Int(α(X ))) ⊆ α(X ) implies: α(Int(α(X ))) ⊆ α(X )
by monotonicity of α. Conversely, any element x ∈ X satisfies β(x) = {x} ⊆ X , and so Int(α(X )), which is equal to {h ∈ α(X ) ; β(h) ⊆ α(X )}, contains X . This implies that α(Int(α(X ))) ⊇ α(X ). Thus α(X ) is a regular closed set.

Lemma 9. Let X , Y be two subsets of H n n such that X Y = H n n . Then, α(X ) Int(α(Y)) = H n .
Proof. Let us first prove that the union is disjoint. For this aim, let us remark that h ∈ α(X ) is equivalent to say that there exists some x ∈ X such that h ∈ α(x). In other words, there exists some x ∈ X such that x ∈ β(h). Now, let us remark that h ∈ Int(α(Y)) is equivalent to say that β(h) ⊆ α(Y). If we assume that:

α(X ) ∩ Int(α(Y)) = ∅, (P )
we can deduce that there exists some h ∈ H n such that there exists x ∈ X satisfying that:

x ∈ β(h) ⊆ α(Y), leading to x ∈ α(Y). Since x ∈ X ⊂ H n n , then x ∈ Y
, which is a contradiction. Then (P ) is wrong and the intersection of α(X ) and Int(α(Y)) is empty.

Let us now prove that their union is equal to H n . The fact that α(X ) Int(α(Y)) ⊆ H n is obvious. Now, let us prove the converse inclusion. Let h be a face of H n . Two cases are possible:

-either β(h) ⊆ α(Y), then h ∈ Int(α(Y)), -or β(h) ⊆ α(Y), then the fact that α(X ) ∪ α(Y) = H n
implies that we have:

β(h) ∩ α(X ) = ∅,
then there exists x ∈ X such that:

β(h) ∩ α(x) = ∅.
Then there exists p ∈ β(h) ∩ α(x) which means that h ∈ α(p) and p ∈ α(x), and then by transitivity, h ∈ α(x) ⊆ α(X ).

Then α(X ) Int(α(Y)) ⊇ H n . The proof is done. Proposition 9. The hit-transform and the miss-transform of X have the same boundary which is equal to:

α(X ) ∩ α(Y).
Proof. The boundary N of I hit (X) is equal to: α(I hit (X)) ∩ α(H n \ I hit (X)), also equal by idempotence of α to:

α(X ) ∩ α(H n \ α(X )),
which is equal by Lemma 9 to:

α(X ) ∩ α(Int(α(Y))),
and by regularity of α(Y) (see Proposition 8), then:

N = α(X ) ∩ α(Y).
In the same manner, the boundary N of I miss (X) is equal to:

α(I miss (X)) ∩ α(H n \ I miss (X)),
which is equal to:

α(Int(α(X ))) ∩ α(H n \ Int(α(X ))),
which is by Proposition 8 equal to:

α(X ) ∩ α(H n \ Int(α(X ))),
and by Lemma 9, it is equal to:

α(X ) ∩ α(α(Y)), equal to: α(X ) ∩ α(Y),
by idempotence of α. This way, we have:

N = N = α(X ) ∩ α(Y).
Proposition 10. For any z ∈ N, we have the property that

|α N (z)| is a (dim(z) -1)-surface. Proof. Since N is closed, ∀z ∈ N, |α N (z)| = |α (z)|, which is a (ρ(z, |H n |) -1)-surface by Proposition 3 since H n is an n- surface. Since ρ(z, |H n |) = dim(z), |α N (z)| is a (dim(z) -1)- surface. Lemma 10. The immersion I miss (X) of X is AWC iff ∀z ∈ N, |β N (z)| is a (n -2 -dim(z))-surface.
Proof. Let us recall that two disjoint components C 1 and C 2 of N are separated:

C 1 ∩ θ(C 2 ) = ∅.
For this reason, for any z ∈ N,

θ N (z) = θ (z) ∩ C∈CC(N) C, = C∈CC(N) (θ (z) ∩ C), = θ CC(N,z) (z). Since n ≥ 2, I miss (X) is AWC iff ∀C ∈ CC(N), C is a (n - 1)-surface, i.e., ∀C ∈ CC(N), ∀z ∈ C, |θ C (z)| is a (n -2)- surface, which means that ∀C ∈ CC(N), ∀z ∈ C, |θ N (z)| is a (n -2)-surface,
(z)| is a (n -2 -dim(z))-surface.
it is clear that (1) is satisfied by hypothesis. Also, for each i ∈ 1, n \ {m}, we have Z(p i ) = Z(c i ), which implies (2) and (3). Now let us assume that ( 4) is false, it means that there exists some i ∈

1 2 (Z n (p)) ∩ 1 (Z n (c)) such that Z(c i ) is
in half and such that Z(p i ) is integral. Then we obtain that

|Z(c i ) -Z(p i )| = 1 2
, which means that i = m (Z n (c) and Z n (p) are different only on the m th coordinate). However, i belongs to 1 2 (Z n (p))∩1 (Z n (c)) and m belongs to 1 (Z n (p))∩ 1 2 (Z n (c)). We obtain a contradiction:

{i} ⊆ 1 (Z n (p)) ∩ 1 2 (Z n (c)) ∩ 1 2 (Z n (p)) ∩ 1 (Z n (c)) = ∅, then (4)
is true. ( 5) is true because p has one more integral coordinate than c by hypothesis. 53: Assuming that a and b cover c, that the index i * is defined such that a i * = c i * and that the index j * defined such that b j * = c j * . When i * and j * are different, we obtain that β(a) ∩ β(b) in light gray is not empty.

Lemma 11. Let a, b, c be three elements of H n such that a = opp c (b), then there exists m ∈ 1, n such that:

-either Z n (a) = Z n (c) -1 2 e m and Z n (b) = Z n (c) + 1 2 e m , -or Z n (a) = Z n (c) + 1 2 e m and Z n (b) = Z n (c) -1 2 e m ,
which leads in both cases to:

Z n (a) + Z n (b) 2 = Z n (c).
Furthermore,

     1 (Z n (a)) = 1 (Z n (c)) {m} = 1 (Z n (b)) , 1 2 (Z n (a)) {m} = 1 2 (Z n (c)) = 1 2 (Z n (b)) {m}.
Proof. By Propositions 12 and 13, there exist i * , j * ∈ 1, n such that:

                 1 (Z n (a)) ∩ 1 2 (Z n (c)) = {i * } , Z n (a) ∈ Z n (c) -1 2 e i * , Z n (c) + 1 2 e i * , 1 (Z n (b)) ∩ 1 2 (Z n (c)) = {j * } , Z n (b) ∈ Z n (c) -1 2 e j * , Z n (c) + 1 2 e j * .
Also, since a and b cover c, we have that a ∈ β(c) and b ∈ β(c). Applying β on these expressions, we obtain that β(a) ⊆ β(c) and that β(b) ⊆ β(c) (by transitivity of β). Due to the fact that for each i ∈ 1, n , we have a i = c i iff i = i * , and b j = c j iff j = j * , then we have: 53), then when m = i * , we have

                 β(a i * ) ⊂ β(c i * ), ∀i ∈ 1, n \ {i * }, β(a i ) = β(c i ), β(b j * ) ⊂ β(c j * ), ∀i ∈ 1, n \ {j * }, β(b i ) = β(c i ), If i * = j * (see Figure
β(a m ) ⊂ β(c m ) = β(b m ), when m = j * , we have β(b m ) ⊂ β(c m ) = β(a m ), and when m ∈ 1, n \ {i * , j * }, we have β(a m ) = β(c m ) = β(b m ). We obtain that β(a) ∩ β(b) = ⊗ i∈ 1,n (β(a i ) ∩ β(b i )) = ∅,
which contradicts the hypothesis that a and b are opposites. Then we have i

* = j * . Because Z n (a), Z n (b) belong to Z n (c) - 1 2 e i * , Z n (c) + 1 2 e i *
and because they are different, we obtain that:

-either Z n (a) = Z n (c) -1 2 e i * and Z n (b) = Z n (c) + 1 2 e i * , -or Z n (a) = Z n (c) + 1
2 e i * and Z n (b) = Z n (c) -1 2 e i * , which leads obviously to:

Z n (a) + Z n (b) 2 = Z n (c).
When m ∈ 1, n \{i * }, we have then dim(a m ) = dim(c m ) = dim(b m ), and when m = i * , we have dim(a m ) = dim(c m ) + 1 = dim(b m ). We can then conclude that:

     1 (Z n (a)) = 1 (Z n (c)) {i * } = 1 (Z n (b)) , 1 2 (Z n (a)) {i * } = 1 2 (Z n (c)) = 1 2 (Z n (b)) {i * }.
Proposition 14. Let t, t , z three elements in H n such that t and t are opposite relatively to z. Now let define E := β(z)\(β(t)∪β(t )), and let m * be the only coordinate in 1, n

such that m * ∈ 1 (Z n (t)) \ 1 (Z n (z)).
Then, the application

Iso : E → H n such that, ∀u ∈ E, Iso(u) := H n Z n (u) + (Z(t m * ) -Z(z m * )) e m * .
is an isomorphism from E to β(t). In other words, the order is preserved from E to β(t).

Proof. Let t, t , z be three elements of H n such that t = opp z (t), then by Proposition 13), we obtain that there exists some value m ∈ 1,

n such that 1 2 (Z n (z))∩1 (Z n (t)) = {m}, Z n (t) = Z n (z) + 1 2 e m , and Z n (t ) = Z n (z) -1 2 e m (or the converse case Z n (t) = Z n (z) -1
2 e m , and Z n (t ) = Z n (z) +

1 2 e m but by symmetry, we do not need to treat this case). We know by Examples 1 that

β(t) = H n {t, 1 2 (Z n (t)),{-1 2 ,0, 1 2 }} and β(t ) = H n {t , 1 2 (Z n (t )),{-1 2 ,0, 1 2 }} . Since E is equal to β(z) \ (β(t) ∪ β(t ))
, we can reformulate it using Notation 8. Indeed,

β(z) = H n {z, 1 2 (Z n (z)),{-1 2 ,0, 1 2 }} , = H n         z + i∈ 1 2 (Z n (z)) λ i e i ; λ i ∈ - 1 2 , 0, 1 2         , = H n         z + i∈ 1 2 (Z n (t) {m}) λ i e i ; λ i ∈ - 1 2 , 0, 1 2 
       , = H n      z + λ m e m + i∈ 1 2 (Z n (t)) λ i e i ; λ m ∈ {-1 2 , 0, 1 2 }, λ i ∈ -1 2 , 0, 1 2      , = H n         t + i∈ 1 2 (Z n (t)) λ i e i ; λ i ∈ - 1 2 , 0, 1 2         ∪ H n         z + i∈ 1 2 (Z n (t)) λ i e i ; λ i ∈ - 1 2 , 0, 1 2         ∪ H n         t + i∈ 1 2 (Z n (t)) λ i e i ; λ i ∈ - 1 2 , 0, 1 2         , = β(t) ∪ E ∪ β(t ).
Since this is a disjoint union, it is clear that :

E = H n         z + i∈ 1 2 (Z n (t)) λ i e i ; λ i ∈ - 1 2 , 0, 1 2
        .
Now that we have this equality, we can prove that their exists an isomorphism between β(t), E and β(t ). By symmetry, it is sufficient to prove that E and β(t) are isomorphic. For that, we define the application τ +,m : H n → H n such that for any u ∈ H n :

τ +,m (u) = H n Z n (u) + 1 2 e m .
Let us show first that this application maps E to β(t). Let u be an element of E, then there exists for any i ∈ 1 2 (Z n (t))

one value λ i ∈ {-1 2 , 0, 1 2 } such that u = H n   Zn(z) + i∈ 1 2 (Z n (t)) λ i e i    .
This way,

τ +,m (u) = H n   Zn(z) + 1 2 e m + i∈ 1 2 (Z n (t)) λ i e i    .
Since Z n (z) + 1 2 e m = Z n (t), we obtain that

τ +,m (u) = H n   Zn(t) + i∈ 1 2 (Z n (t)) λ i e i    ,
and then

τ +,m (u) ∈ H n {t, 1 2 (Z n (t)),{-1 2 ,0, 1 2 }}
which is in fact β(t).

Now we want to prove that τ +,m is injective, which is immediate because it is a translation. To prove that τ +,m is surjective, let us proceed this way: let v be a point in β(t), then there exists for any i ∈ 1 2 (Z n (t)) one value

λ i ∈ {-1 2 , 0, 1 2 } such that v = H n (Z n (t) + i∈ 1 2 (Z n (t)) λ i e i ). Its antecedent is simply u = H n   Zn(z) + i∈ 1 2 (Z n (t)) λ i e i    which obviously belongs to E.
This translation is then a bijection from E to β(t). Now we need to prove that it preserves the order: let a, b be two elements of E such that a b, then, by Proposition 13, there exists a value i ∈ 1 2 (Z n (t)) such that:

           Z n (a) ∈ {Z n (b) -1 2 e i , Z n (b) + 1 2 e i }, Z(a i ) ∈ Z, Z(b i ) ∈ (Z/2) \ Z,
Now let us define a = τ +,m (a) and b = τ +,m (b). We want to prove that a covers b . In fact, we can write a = H n (Z n (a) + 1 2 e m ) and b = H n (Z n (b) + 1 2 e m ). We obtain then that:

Z n (a ) = Z n (a) + 1 2 e m , ∈ {Z n (b) -1 2 e i + 1 2 e m , Z n (b) + 1 2 e i + 1 2 e m }, ∈ {Z n (b ) -1 2 e i , Z n (b ) + 1 2 e i }.
It remains to show that Z(a i ) belongs to Z and that Z(b i ) belongs to (Z/2) \ Z. Since we have the three following conditions: (1) Z(b i ) belongs to (Z/2) \ Z, (2) Z n (b ) = Z n (b) + 1 2 e m , and (3) m ∈ 1 2 (Z n (t)) (which contains i), then m = i, which leads to Z(b i ) = Z(b i ). Then Z(b i ) belongs to (Z/2) \ Z. The fact that Z(a i ) belongs to Z comes from the fact that Z(a i ) ∈ {Z(b i ) -1 2 e i , Z(b i ) + 1 2 e i }. This concludes the proof. Lemma 12. Assuming n ≥ 2, let z be an element of H n \H n n and t, t be in H n dim(z)+1 such that they are opposite relatively to z. Then β (z) \ (β(t) ∪ β(t )) is a (n -dim(z) -2)surface.

Proof. Since t and t are two opposites,

1 (Z n (t)) = 1 (Z n (t ))
by Lemma 11,and Card (1 (Z n (t))) = Card (1 (Z n (z))) + 1. Now let m * be the coordinate in 1, n such that m * ∈ 1 (Z n (t)) \ 1 (Z n (z)). We can then write:

Z n (t) = Z n (z) + (Z(t m * ) -Z(z m * )) e m * .
Now let define E := β(z) \ (β(t) ∪ β(t )), and let define the application Iso : E → H n such that ∀u ∈ E,

Iso(u) := H n Z n (u) + (Z(t m * ) -Z(z m * )) e m * .
Intuitively, this application translates the point u from E to β(t) directed by the vector e m * . More exactly, by Proposition 14, Iso is an isomorphism from |E| to |β(t)|. This way,

|β (z) \ (β(t) ∪ β(t ))| = |E \ {z}| is isomorphic by Proposi- tion 14 to |β(t) \ {Iso(z)}| = |β (t)| which is a (n -dim(t) - 1) = (n -2 -dim(z))-surface.
(x)) ∩ α(H n (y)) ⊆ α(H n (z)) ∩ α(H n (y)).
Lemma 13. For all z ∈ H n \ H n n and for all u ∈ β (z),

T (u) =    H n Z n (z) + (Z(u i ) -Z(z i )).e i ; i ∈ 1 (Z n (u)) ∩ 1 2 (Z n (z))    Proof.
Let us define:

A :=    H n Z n (z) + (Z(u i ) -Z(z i )).e i ; i ∈ 1 (Z n (u)) ∩ 1 2 (Z n (z))   
Let us show first that A ⊆ T (u). Since we have u ∈ β (z), Proposition 12, 1 (Z n (u)) ∩ 1 2 (Z n (z)) = ∅. Then let t be a face in A, t can be written:

t = H n Z n (z) + (Z(u i * ) -Z(z i * )).e i * , with i * ∈ 1 (Z n (u)) ∩ 1 2 (Z n (z)). We recall that 1 2 (Z n (u)) ∩ 1 (Z n (z)) = ∅
because u ∈ β (z), we then have the different subcases when i ∈ 1, n :

1. i belongs to (1 (Z n (u)) ∩ 1 (Z n (z))) ∪ 1 2 (Z n (u)) ∩ 1 2 (Z n (z)) , then u i = z i and then t i = z i = u i implies that t i ∈ α(u i ) ∩ β(z i ). 2. or i = i * ∈ 1 (Z n (u)) ∩ 1 2 (Z n (z)), then t i = u i with Z(u i ) = Z(z i ) ± 1 2 . Since Z(t i ) = Z(z i ) ± 1 2 ,
we have then

t i ∈ {Z(z i ) -1/2, Z(z i ) + 1/2}, {Z(z i ) + 1/2, Z(z i ) + 3/2} . Also, β(z i ) =    {Z(z i ) -1/2, Z(z i ) + 1/2}, {Z(z i ) + 1/2}, {Z(z i ) + 1/2, Z(z i ) + 3/2}    t i .
This way, t i ∈ α(u i ) ∩ β(z i ).

or

i ∈ 1 (Z n (u)) ∩ 1 2 (Z n (z)) \ {i * }, then t i = z i with Z(z i ) = Z(u i ) ± 1 2
. Also, we have

α(u i ) = {Z(u i ), Z(u i ) + 1}, {Z(u i )}, {Z(u i ) + 1} , which contains Z(z i ) + 1 2 = {Z(t i ) + 1 2 } = t i . This way, t i ∈ α(u i ) ∩ β(z i ).
We have finally t ∈ α(u) ∩ β(z), and since by construction we have t = z, t ∈ α(u) ∩ β (z). Furthermore, Z n (t) has the same dim(z) integral coordinates as z plus the i * -th one, and then t ∈ H n dim(z)+1 , then A ⊆ T (u).

Let us show now that T (u) ⊆ A. Let t be in T (u). Since t ∈ β(z), we know that:

{∀i ∈ 1, n , i ∈ 1 (Z n (z)) ⇒ i ∈ 1 (Z n (t))} . Also, t ∈ H n dim(z)+1
, then there exists an unique coordi-

nate i * in 1 (Z n (t)) \ 1 (Z n (z)). Since t i ∈ {z i , u i } for each i ∈ 1, n , then t i * = u i * = z i * and for all i ∈ 1, n \ {i * }, t i = z i . Because we have t ∈ α(u), i * ∈ 1 (Z n (u))∩ 1 2 (Z n (z))
. Also, we have:

t = H n Z n (z) + (Z(u i * ) -Z(z i * )).e i * ,
then we finally obtain that t ∈ A. (3) When a 1 ∈ H 1 0 and b 1 ∈ H 1 1 , then the reasoning is the same as before.

(4) When a 1 , b 1 ∈ H 1 1 , then there exist i, j ∈ Z such that a 1 = {i, i+1} and b 1 = {j, j +1}. We obtain then β(a 1 ) = {{i, i + 1}}, β(b 1 ) = {{j, j + 1}}. Lemma 15 (Decomposition lemma). Let z be a face in H n \ H n n . Each face u ∈ β (z) can be decomposed in the following manner (see Figure 27):

β(a) ∩ β(b) = β(× i∈ 1,n a i ) ∩ β(× i∈ 1,n b i ), = ⊗ i∈ 1,n β(a i ) ∩ ⊗ i∈ 1,n β(b i ), = ⊗ i∈ 1,n (β(a i ) ∩ β(b i )) , = ∅, then for all i ∈ 1, n , β(a i ) ∩ β(b i ) = ∅, which imples that a i ∨ b i exists and β(a i ) ∩ β(b i ) = β(a i ∨ b i ). This way: β(a) ∩ β(b) = β(× i∈ 1,n a i ) ∩ β(× i∈ 1,n b i ) = ⊗ i∈ 1,n (β(a i ) ∩ β(b i )) = ⊗ i∈ 1,n β(a i ∨ b i ) = β(× i∈ 1,n a i ∨ b i ) whose infimum is × i∈ 1,
u = v∈T (u) v.
Proof. We need first to show that v∈T (u) v exists. For this aim, it is sufficient to show that t∈T (u) β(t) = ∅. However, u ∈ β (z) implies by Lemma 13 that

T (u) =    H n Z n (z) + (Z n (u i ) -Z n (z i )).e i ; i ∈ 1 (Z n (u)) ∩ 1 2 (Z n (z))    .
For all i * ∈ 1 (Z n (u)) ∩ 1 2 (Z n (z)), let us denote:

t i * := H n Z n (z) + (Z n (u i * ) -Z n (z i * )) e i * , then T (u) = {t i * } i * ∈1(Z n (u))∩ 1 2 (Z n (z)) .
This way, t∈T

β(t) = i * ∈1(Z n (u))∩ 1 2 (Z n (z)) β(t i * ) = i * ∈1(Z n (u))∩ 1 2 (Z n (z)) β   × m∈ 1,n t i * m   = i * ∈1(Z n (u))∩ 1 2 (Z n (z)) m∈ 1,n β t i * m = m∈ 1,n i * ∈1(Z n (u))∩ 1 2 (Z n (z)) β t i * m (u)
We want to show that for all m ∈ 1, n ,

i * ∈1(Z n (u))∩ 1 2 (Z n (z)) β t i * m = ∅.
Since u belongs to β(z), then:

-either m ∈ 1 (Z n (z)) ∪ 1 2 (Z n (u)), then Z(u m ) = Z(z m ).
And because

m = i * for all i * ∈ 1 (Z n (u)) ∩ 1 2 (Z n (z)), t i * m = z m = u m , and: i * ∈1(Z n (u))∩ 1 2 (Z n (z)) β t i * m = β(u m ) = ∅. -or m ∈ 1 (Z n (u)) ∩ 1 2 (Z n (z)), then Z(u m ) ∈ Z(z m ) - 1 2 , Z(z m ) + 1 2 .
Then, there exists a value i * ∈ 1

(Z n (u))∩ 1 2 (Z n (z)) such that i * = m, for which Z(t i * m ) = Z(u m ) ∈ {Z(z m ) - 1 2
, Z(z m ) + 1 2 }, and then:

i * ∈1(Z n (u))∩ 1 2 (Z n (z)) β t i * m = β(t m m ) ∩ i * ∈1(Z n (u))∩ 1 2 (Z n (z))\{m} β t i * m , = β(u m ) ∩ β(z m ).
Two cases are possible. Either Z(u m ) = Z(z m ) -1 2 , then:

β(u m ) ∩ β(z m ) = β(H n (Z(z m ) - 1 2 )) ∩ β(z m ) = {{Z(z m ) - 1 2 , Z(z m ) + 1 2 }} ∩        {Z(z m ) -1/2, Z(z m ) + 1/2}, {Z(z m ) + 1/2}, {Z(z m ) + 1/2, Z(z m ) + 3/2}        = {{Z(z m ) - 1 2 , Z(z m ) + 1 2 }} = β(u m ) = ∅
Or Z(u m ) = Z(z m ) + 1 2 , then:

β(u m ) ∩ β(z m ) = β(H n (Z(z m ) + 1 2 )) ∩ β(z m ) = {{Z(z m ) + 1/2, Z(z m ) + 3/2}} ∩        {Z(z m ) -1/2, Z(z m ) + 1/2}, {Z(z m ) + 1/2}, {Z(z m ) + 1/2, Z(z m ) + 3/2}        = {{Z(z m ) + 1/2, Z(z m ) + 3/2}} = β(u m ) = ∅
This way, for all m ∈ 1, n ,

i * ∈1(Z n (u))∩ 1 2 (Z n (z)) β t i * m = ∅,
and then t∈T (u)

β(t) = ∅, which implies that t∈T (u) t exists in H n .
Let us compute now this term, following the calculus made before:

β t∈T (u) t = m∈ 1,n i * ∈1(Z n (u))∩ 1 2 (Z n (z)) β t i * m = m∈ 1,n β(u m ) = β(× m∈ 1,n u m ) = β(u)
and then u = t∈T (u) t.

Lemma 17. Let v, f be two faces of

H n such that f ∈ β(v).
For all k ∈ dim(v), dim(f ) :

Card (α(f ) ∩ β(v) ∩ H n k ) = C k-dim(v) dim(f )-dim(v) .
Proof. This proof is an enumeration problem: we want to find the total number of k-faces of α(f ) ∩ β(v). We recall that by Proposition 12 for all w ∈ H n , we have:

w ∈ α(f ) ∩ β(v) ⇔        ∀m ∈ 1 (Z n (f )) ∩ 1 2 (Z n (v)) , w m ∈ {v m , f m }, and ∀m ∈ 1 2 (Z n (f )) ∪ 1 (Z n (v)) , w m = v m (= f m ).        .
Then, dim(v) coordinates of w in α(f )∩β(v) are fixed and integral, which means that (k -dim(v)) of its coordinates are free, that is, in half or integral. These last coordinates can be chosen among the (n -dim(v)) half coordinates of v minus the (n -dim(f )) half coordinates of f , which explains the (dim(f ) -dim(v)) term. This concludes the proof. Lemma 19. Let n ≥ 3 be an integer. Let z be in H n such that dim(z) ≤ n -3, and let p, p be in S(z) such that p = antag S(z) (p ). Then S(z) \ {p, p } is 2n-connected into Z n . Proof. Let x, y be in S(z) \ {a, b} with x = y. Then there exists a value k ∈ 1, n -dim(z) such that x and y are kantagonists (since they belong to the block S(z) of dimension (n -dim(z))). Let us now proceed by induction on the value of k.

Initialization (k = 1): when x and y are 1-antagonists in Z n , they are 2n-neighbors and then there exists a 2n-path π joining them into S(z) \ {a, b} such that π = (x, y).

Heredity (k ∈ 2, n -dim(z) ): we assume that for all the elements x, y in S(z) \ {a, b} such that they are (k -1)antagonists into S(z), there exists a 2n-path joining them into S(z)\{a, b}. Let us show that when x and y are k-antagonists, x and y are 2n-connected into S(z) \ {a, b}. By hypothesis, x and y are k-antagonists with k ≥ 2 and belong to S(z), then they are antagonists in a block S ⊆ S(z) of dimension k. This way, x admits in S a total number of k 2n-neighbors (which are different from itself) where at most one is into {a, b}. Indeed, if a and b were neighbors of x, they would be identical or 2-antagonists. These two cases are impossible since a and b are (n -dim(z))-antagonists with (n -dim(z)) ≥ 3. Then there exists a 2n-neighbor v x of x into S \ {a, b}; v x is then (k -1)-antagonist of y and 2n-neighbor of x, then x and y are connected into S(z) \ {a, b} thanks to the induction hypothesis.

D Proofs of Section 6

Lemma 20. We assume that X is a non-empty finite subset of Z n , that Y is its complement in Z n , that N is the boundary of the hit/miss-transform of X. Then each component

|F i | of |β N (z)| is closed in β (z).
Proof. Since β N (z) is equal to the intersection N ∩ β (z) and N is closed in H n as intersection of two closed sets of H n , then β N (z) is closed in β (z). Because when a subset of a topological space is closed, each connected component is closed too, then the connected components of β N (z) are closed in β (z), and then for each i ∈ I, F i is closed in β (z).

Lemma 21. We assume that X is a non-empty finite subset of Z n , that Y is its complement in Z n , that N is the boundary of the hit/miss-transform of X. Then for two different components F i and F j of |β N (z)|:

β(F i ) ∩ F j = ∅, and α(F i ) ∩ F j = ∅.
Proof. Let i, j be two different values of I. Now, let us assume that the intersection β(F i )∩F j is not empty, then there exists some z ∈ β(F i ) ∩ F j . It means that we have at the same time z ∈ β(F i ) and z ∈ F j . It is equivalent to say that there exists some a ∈ F i such that z ∈ β(a) and z ∈ F j . Then, there exists some a ∈ F i such that a ∈ α(z) and z ∈ F j . So, there exists some a ∈ F i which satisfies a ∈ α(F j ). Now, we know that F j is a connected component of the closed set N, and then α(F j ) = F j . Then, there exists a ∈ F i ∩ F j , which would mean that F i ∩F j is non-empty. We have a contradiction. Lemma 22. We assume that X is a non-empty finite subset of Z n , that Y is its complement in Z n , that N is the boundary of the hit/miss-transform of X. For each u ∈ β N (z), there exists one unique index i * ∈ I such that u ∈ F i * and it satisfies that:

             α F i * (u) = α β N (z) (u), β F i * (u) = β β N (z) (u), θ F i * (u) = θ β N (z) (u).
Proof. Let u be an element of β N (z). Then there exists one, and only one, value i * ∈ I such that u belongs to F i * .

-First, let us remark that:

α β N (z) (u) = α (u) ∩ i∈I F i , = (α (u) ∩ F i * ) ∪   α (u) ∩   i∈I\{i * } F i     , = (α (u) ∩ F i * ) ∪   i∈I\{i * } α (u) ∩ F i   ,
However, we can remark that if for any i * 2 ∈ I \ {i * }, we have α (u) ∩ F i * 2 = ∅, then there exists some z ∈ α (u) ∩ F i * 2 , and then there exists z ∈ F i * 2 such that u ∈ β (z), which implies u ∈ β(F i * 2 ), and then F i * and F i * 2 are neighbors. Contradiction. -By symmetry, we obtain a same reasoning.

-With the two preceding assertions true, we can remark that:

θ β N (z) (u) = θ (u) ∩ β N (z), = (α (u) ∪ β (u)) ∩ β N (z), = (α (u) ∩ β N (z)) ∪ (β (u) ∩ β N (z)), = α β N (z) (u) ∪ β β N (z) (u), = (α F i * (u) ∪ β F i * (u), = θ F i * (u).
Property 1. We assume that n ≥ 3 and that there exists z ∈ N such that dim(z) ≤ (n -3) and that β N (z) is not connected (Hypothesis 1). We assume also that each compo- Then for all j ∈ I, j = i, we have β(F i ) ∩ F j = ∅ by Lemma 21, and then β(t) ∩ F j = ∅, and β(t ) ∩ F j = ∅. This way, F j ⊆ β (z) \ (β(t) ∪ β(t )), which is by Lemma 12 a (n-dim(z)-2)-surface (like F j ). However, when two discrete surfaces of same rank satisfy an inclusion relationship, they are equal (see Proposition 6), then we have :

nent of β N (z) is a (n -dim(z) -2)-surface (Hypothesis 2). Then, ∀i ∈ I, ∀t ∈ H n dim(z)+1 , {t ∈ F i ⇒ opp z (t) ∈ F i } . Proof.
F j = β (z) \ (β(t) ∪ β(t )).
This implies that F i is included into β(t) ∪ β(t ) and then F i = F i ∩ (β(t) ∪ β(t )). Since t and t belong to F i , we obtain finally that:

F i = β F i (t) ∪ β F i (t ),
which is a disjoint union of two open non-empty sets, i.e., F i is not connected, which is impossible.

Property 2. We assume that n ≥ 3 and that there exists z ∈ N such that dim(z) ≤ (n -3) and that β N (z) is not connected (Hypothesis 1). For each value i in I, F i contains at most (n -dim(z)) (dim(z) + 1)-faces.

Proof. β (z) contains exactly 2(n-dim(z)) pairs of opposite (dim(z) + 1)-faces, and then by Property 1, for all i in I, F i contains at most (n -dim(z)) (dim(z) + 1)-faces.

Lemma 23. Let x, y be two elements of Z n and S be a block such that x = antag S (y). Then for all z ∈ S:

   α(H n (x)) ∩ α(H n (y)) ⊆ α(H n (x)) ∩ α(H n (z)), α(H n (x)) ∩ α(H n (y)) ⊆ α(H n (z)) ∩ α(H n (y)).
Proof. By symmetry, it is sufficient to show the first assertion (see Figure 54). Let I = {i ∈ 1, n ; x i = y i }. Let z be an element of S, then for all i ∈ I, z i ∈ {x i , y i } and for all i ∈ 1, n \ I, x i = y i = z i .

When i ∈ 1, n \ I, x i = y i = z i and then:

α(H(x i )) ∩ α(H(y i )) = α(H(x i )), = α(H(x i )) ∩ α(H(z i )).
When i ∈ I, either z i = x i , and:

α(H(x i )) ∩ α(H(y i )) ⊆ α(H(x i )), ⊆ α(H(x i )) ∩ α(H(z i )),
or z i = y i and we obtain immediately:

α(H(x i )) ∩ α(H(y i )) = α(H(x i )) ∩ α(H(z i )).
A simple application of the Cartesian product is then sufficient to end the proof.

Lemma 24. Let X be a non-empty finite subset of Z n , Y its complement in Z n , and N be the boundary of the misstranform of X in H n . For each z ∈ N:

β N (z) = f ∈H n n-1 ∩β N (z) α(f ) ∩ β (z),
in other words, β N (z) is equal to the union of the closures (into β (z)) of its (n -1)-faces.

x' x y' y S Π Fig. 55: Let x be in X and y be in Y such that they are antagonist in a block S ⊂ Z n . They are joined by a 2n-path π ⊆ S containing a pair (x , y ) ∈ X × Y such that x ∈ N * 2n (y ).

Proof. Let us begin with the first inclusion. Since for all f ∈

β N (z), f ∈ N, then α(f ) ∩ β (z) ⊆ β N (z) because β N (z) is closed in the subspace β (z).
Now let us prove the second inclusion. Let u be an element of β N (z). Let us recall that S(z) = Z n (β(z)∩H n n ) is the block centered at z (see Proposition 4). Then by Lemma 8:

β N (z) = α(H n (X)) ∩ α(H n (Y )) ∩ β (z), = α(H n (X ∩ S(z))) ∩ α(H n (Y ∩ S(z))) ∩ β (z).
This way, there exist x ∈ X ∩ S(z) and y ∈ Y ∩ S(z) such that u ∈ α(H n (x))∩α(H n (y)). Also, x and y belonging to the same block S(z) and being different, they are k-antagonist, k ≥ 1. Now let I be the set {i ∈ 1, n ; x i = y i } = {j 1 , . . . , j k } where the sequence (j i ) i is strictly increasing. We can then define the 2n-path π, i.e., a sequence in Z n such as two consecutive elements in the sequence are 2n-neighbors in Z n , joining x and y into S(z): π = (p 0 = x, p 1 , . . . , p k-1 , p k = y), satisfying the recursive relation:

p 0 = x, p l = p l-1 + (y j l -x j l ).e j l , ∀l ∈ 1, k , Now, let us define l * := min{l ∈ 1, k ; p l ∈ Y } -1,
then we obtain two points x := p l * ∈ X and y := p l * +1 ∈ Y which are 2n-neighbors in the block S(z) (see Figure 55). Since y -x = l∈ 1,l * +1 (y j l -x j l ).e j l , y and x are antagonist in a block of dimension (l * + 1) that we will call S . Moreover:

x = x + l∈ 1,l * (y j l -x j l ).e j l , (1) x = y + (x j l * +1 -y j l * +1 ).e j l * +1 , (2) then ∀i ∈ 1, n , x i ∈ {y i , x i }, which implies x ∈ S .

Then, using Lemma 23:

α(H n (x)) ∩ α(H n (y )) ⊆ α(H n (x )) ∩ α(H n (y )).
Moreover, y ∈ S where x and y are antagonist, so one more time using Lemma 23,

α(H n (x)) ∩ α(H n (y)) ⊆ α(H n (x)) ∩ α(H n (y )),
and then we obtain by transitivity that:

α(H n (x)) ∩ α(H n (y)) ⊆ α(H n (x )) ∩ α(H n (y )).
This way, u ∈ α(H n (x )) ∩ α(H n (y )). Also, x and y being 2n-neighbors, they are 1-antagonist and then u belongs to the closure of the (n -1)-face f := H n (x ) ∧ H n (y ) by Lemma 2.

Because H n (x ) and H n (y ) belong to β (z), we have

z ∈ α(H n (x )) ∩ α(H n (y )) = α(f ) and then f ∈ β(z). Since f is of dimension n-1 and z of dimension lower than or equal to n -3, f is different from z. Because f is the supremum of α(H n (x )) ∩ α(H n (y )) ⊆ N, it belongs to N. Finally, we have u ∈ α(f ) ∩ β (z) with f ∈ β N (z) ∩ H n n-1 .
Lemma 25. Let X be a non-empty finite subset of Z n , Y its complement in Z n , and N be the boundary of the misstranform of X in H n . For each z ∈ N, and for any i ∈ I, the component F i of |β N (z)| is the closure in β (z) of a set of (n -1)-faces, i.e.:

F i = f ∈H n n-1 ∩F i α(f ) ∩ β (z).
Proof. Using Lemma 24, we have:

β N (z) = f ∈H n n-1 ∩β N (z) α(f ) ∩ β (z),
where for all f ∈ H n n-1 ∩ β N (z), the orders |α(f ) ∩ β (z)| are connected; indeed, any two faces a, b in this poset different from f are connected by the path π = (a, f, b). Now, let us show by a double inclusion that we can prove the result we are looking for.

For any i ∈ I, and for each f ∈ H n n-1 ∩ F i , |α(f ) ∩ β (z)| is connected, and share f with F i . Since they are both subsets of β N (z), by definition of F i ,

F i ⊇ α(f ) ∩ β (z).
Hence,

F i ⊇ f ∈H n n-1 ∩F i α(f ) ∩ β (z).
Conversely, F i is a connected component of |β N (z)| which is closed in β (z), and then F i is also closed in β (z), which means that for f ∈ F i , α(f ) ∩ β (z) ⊆ F i , then for any f ∈ F i ∩ H n n-1 , α(f ) ∩ β (z) ⊆ F i , and then:

F i ⊆ f ∈H n n-1 ∩F i α(f ) ∩ β (z).
That concludes the proof.

Lemma 26. Let f, z be two elements of H n such that f ∈ β(z), and let be I = {i ∈ 1, n ; f i = z i }. Then, dim(f ) = dim(z) + Card (I) .

Proof. Since f ∈ β(z), then for all i ∈ 1, n , f i ∈ β(z i ) and then three cases are possible:

dim(z i ) = 1, and then f i = z i (because β(z i ) = {z i }), or dim(z i ) = 0 and dim(f i ) = 0, then f i = z i (because the only face of dimension 0 in β(z i ) is z i ), or dim(z i ) = 0 and dim(f i ) = 1, and then

f i ∈ H Z(z i ) - 1 2 , H Z(z i ) + 1 2 .
In other words, the number of coordinates where f and z are different is equal to the the number of times when the dimension of f i is strictly greater than the dimension of z i when i is in 1, n .

Property 3. We assume that n ≥ 3 and that there exists z ∈ N such that dim(z) ≤ (n -3) and that β N (z) is not connected (Hypothesis 1). We assume also that each component of β N (z) is a (n -dim(z) -2)-surface (Hypothesis 2).

Then, ∀i ∈ I, ∀m ∈ dim(z) + 1, n -1 :

F i ∩ H n m = ∅.
Proof. Intuitively, F i being an union of closures of (n -1)faces in β (z) by Lemma 25, it contains faces of all dimensions between (n -1) and (dim(z) + 1).

Formally, since F i is non empty, there exists one face f ∈ H n n-1 ∩F i ⊆ β (z) such that α(f )∩β (z) is included into F i . Furthermore, α(f ) ∩ β (z) is not empty because f ∈ β (z), then α(f ) ∩ β (z) is equal to:

{H n (u) ; u i ∈ {Z(f i ), Z(z i )}, ∀i ∈ 1, n } \ {z}.
Let us define I = {i ∈ 1, n ; z i = f i } = {j 1 , . . . , j k } where the sequence (j i ) i is strictly increasing, and let us define the sequence (u l ) l∈ 0,k included into Z n (α(f ) ∩ β(z)) defined such that: u 0 = Z n (f ), u l+1 = u l + (Z(z j l ) -Z(f j l )) e j l , ∀l ∈ 0, k -1 .

Since f belongs to β(z) by hypothesis, |Z(f i ) -Z(z i )| = 1 2 , ∀i ∈ I. In this way, H n (u l ) is of dimension (dim(f ) -l) for any l ∈ 0, k . By Lemma 26, k = dim(f ) -dim(z), and then dim(H n (u l )) ranges dim(z)+1, n-1 when l ranges 0, k-1 . For these values of l, H n (u l ) belongs to α(f ) ∩ β (z). This concludes the proof. Property 4. We assume that n ≥ 3 and that there exists z ∈ N such that dim(z) ≤ (n -3) and that β N (z) is not connected (Hypothesis 1). We assume also that each component of β N (z) is a (n -dim(z) -2)-surface (Hypothesis 2). Now, ∀i ∈ I, ∀v ∈ F i ,

ρ(v, |F i |) = dim(v) -dim(z) -1.
Proof. Let u be an element of F i of dimension between dim(z)+ 1 and n -1; this is possible thanks to Property 3. We want to show by induction that ρ(u,

|F i |) = k is equivalent to dim(u) = k + dim(z) + 1.
Initialization (k = 0): first, let us assume that u is of dimension dim(u) = dim(z) + 1. Since F i ⊆ β (z), α (u) ∩ F i ⊆ α (u)∩β (z) = ∅, then α F i (u) = ∅, and then ρ(u, |F i |) = 0. Now, let us assume that ρ(u, |F i |) = 0, then u belongs to F i which is closed in β (z), and then α(u) ∩ β (z) ⊆ F i . In this way, the only faces whose rank is 0 in F i are the (dim(z) + 1)-faces of β (z). Finally we have for each u ∈ F i the equivalence ρ(u, |F i |) = 0 ⇔ dim(u) = dim(z) + 1.

Heredity (k ≥ 1): we can assume that for each l ∈ 0, k -1 , ρ(u, |F i |) = l ⇔ dim(u) = dim(z) + 1 + l. Let us show that for all v ∈ F i and k ≥ 1, we have the equivalence ρ(v,

|F i |) = k ⇔ dim(v) = k + dim(z) + 1.
Let v be in F i such that dim(v) = k + dim(z) + 1. Then, using the induction hypothesis, we obtain: In other words, max dim(u) ; u ∈ α F i (v) = k+dim(z), and then: max dim(u) ; u ∈ α (v) ≥ k + dim(z). This way, v is of dimension greater than or equal to (k + dim(z) + 1).

Let us assume now that dim(v) ≥ k+dim(z)+2. Since v ∈ F i , α(v) ∩ β (z) ⊆ F i , and then v covers one or several faces in F i of dimension(s) greater than or equal to (k+dim(z)+1), and then max dim(u) ; u ∈ α F i (v) ≥ k + dim(z) + 1, which implies that ρ(v, |F i |) ≥ k + 1, which is impossible. Then dim(v) = k + dim(z) + 1. The reciprocal implication is then proved. Property 5. We assume that n ≥ 3 and that there exists z ∈ N such that dim(z) ≤ (n-3) and that β N (z) is not connected (Hypothesis 1). We assume also that each component of β N (z) is a (n-dim(z)-2)-surface (Hypothesis 2). Then, for all i ∈ I, F i contains at least (n -dim(z)) (dim(z) + 1)faces.

Proof. Let i be in I, then for all m ∈ dim(z) + 1, n -1 , F i ∩ H n m = ∅ by Property 3. This way, there exists t ∈ H n n-2 ∩ F i , and because F i is a (n-2-dim(z))-surface, β F i (t) is a ((ndim(z) -2) -ρ(t, |F i |) -1) = 0-surface by Property 4. Then there exists v, v ∈ H n n-1 ∩ F i such that v ∈ θ(v ). However, α(v) ∩ β (z) and α(v ) ∩ β (z) contain both (n -dim(z) -1) (dim(z) + 1)-faces (cf. Lemma 17), and v = v implies that T (v) = T (v ) (cf. Lemma 16), and then there exists at least one face into T (v ) which is not among the (n -dim(z) -1) faces of T (v). However, T (v) ∪ T (v ) ⊆ F i (because F i is closed into β (z) by Lemma 20). This way, F i ∩ H n dim(z)+1 contains at least (n -dim(z)) faces.

Property 7. We assume that n ≥ 3 and that there exists z ∈ N such that dim(z) ≤ (n -3) and that β N (z) is not connected (Hypothesis 1). We assume also that each component of β N (z) is a (n -dim(z) -2)-surface (Hypothesis 2). Then, Card (I) = 2.

Proof. The non-connectivity of |β N (z)| implies obviously that Card (I) ≥ 2. Moreover, for each i ∈ I, F i contains (ndim(z)) (dim(z) + 1)-faces by Property 6, while β (z) contains 2(n -dim(z)) (dim(z) + 1)-faces, the maximum of components of |β N (z)| s then equal to two.

Property 8. We assume that n ≥ 3 and that there exists z ∈ N such that dim(z) ≤ (n -3) and that β N (z) is not connected (Hypothesis 1). We assume also that each component of β N (z) is a (n -dim(z) -2)-surface (Hypothesis 2).

For all i ∈ I, T (F i ) is equal to:

H n (Z n (z) + λ m e m ); m ∈ 1 2 (Z n (z)) ,
with each λ m being exactly one value in -1 2 , 1 2 .

T (F i ), we can then write:

F i ⊆ α   t∈T (F i ) t   .
Property 11. We assume that n ≥ 3 and that there exists z ∈ N such that dim(z) ≤ (n -3) and that β N (z) is not connected (Hypothesis 1). We assume also that each component of β N (z) is a (n -dim(z) -2)-surface (Hypothesis 2). Then,

F i = α   t∈T (F i ) t   ∩ β (z).
Proof. Let i be a coordinate in I. Then is a (n -dim(z) -2)-surface by Proposition 7. This is also the case concerning F i by hypothesis. This way,

F i = α   t∈T (F i ) t   ∩ β (z)
by Proposition 6.

Property 12. We assume that n ≥ 3 and that there exists z ∈ N such that dim(z) ≤ (n -3) and that β N (z) is not connected (Hypothesis 1). We assume also that each component of β N (z) is a (n -dim(z) -2)-surface (Hypothesis 2). Property 13. We assume that n ≥ 3 and that there exists z ∈ N such that dim(z) ≤ (n-3) and that β N (z) is not connected (Hypothesis 1). We assume also that each component of β N (z) is a (n-dim(z)-2)-surface (Hypothesis 2). Then, X contains a critical configuration of dimension (n-dim(z)).

Proof. Let assume that Hypothesis 1 is true, that is,

  [START_REF] Bertrand | New notions for discrete topology[END_REF] of |H n | relative to S is the poset |S| = (S, ⊆) with, for any h ∈ S, α S (h) = α(h) ∩ S, β S (h) = β(h) ∩ S, and θ S (h) = θ(h) ∩ S. For any suborder |S| of |H n |, we call interior of S the open set defined such as: Int(S) := {h ∈ H n ; β(h) ⊆ S}. A set S ⊆ H n is said to be a regular open set (respectively a regular closed set) if S = Int(α(S)) (respectively S = α(Int(S))).

Fig. 8 :

 8 Fig. 8: An example of path in red in H 2 joining the black points: two successive points a and b on the path satisfy that a ∈ θ (b).

Fig. 9 :

 9 Fig.9: On the top-left, a set which is a discrete 1-surface (a simple closed curve), and on the bottom-right a set which is not a discrete 1-surface (since it contains a "pinch" encircled in red).

Let

  |X| := (X, R X ) and |Y | := (Y, R Y ) be two posets; it is said that |X| and |Y | can be joined [5] if X ∩ Y = ∅. If |X| and |Y | can be joined, the join of |X| and |Y | is denoted |X| * |Y | and is equal to:

Proposition 2 (

 2 [START_REF] Daragon | Discrete frontiers[END_REF]). Let |X| and |Y | be two posets that can be joined. The poset |X| * |Y | is an (n + 1)surface with n ∈ Z iff there exists some integer p ∈ -1, n + 1 such that |X| is a p-surface and |Y | is a (n -p)-surface.

Proposition 3 (

 3 Property 10 in [13]). Let |S| be a suborder of |H n |. Then |S| is an n-surface iff for any h ∈ S, |α S (h)| is a (k -1)-surface and |β S (h)| is a (n -k -1)surface with k = ρ(h, |S|).

3 2 n

 2 Mathematical background relative to Z and H n

Fig. 10 :

 10 Fig. 10: A set in Z 2 .

Notations 3 .

 3 Let a, b be two elements of H n , then we denote by a ∧ b the supremum of α(a) ∩ α(b):

Fig. 13 : 2 n

 132 Fig. 13: Explanation of the formula S(c) = Z n (β(H n (c)) ∩ H n n ): we start from a block S of center c (top left side), we go into the Khalimsky grid (top right side) using the transformation H n , then we compute the n-faces contained in β(H n (c)) (down right side), and then we go back into Z 2 n using Z n (down

By Propositions 5

 5 and 9 and by Lemmas 2, 4, and 7, we obtain that: Proposition 11 (*). Let S be a block of dimension k ∈ 2, n s.t. X ∩ S = {p, p } (or s.t. Y ∩ S = {p, p }) and p = antag S (p), then H n p+p 2

Figure 19

 19 Figure 19 depicts examples of β N (z * ) in the case n = 3. Let us now remark that |β N (z * )| is the disjoint union of |f(p, z * )| and of |f(p , z * )|:

Definition 4 (

 4 Covering relation). Let a, b be two elements of H n . We say that a covers b, when a ∈ β (b) and dim(a) = dim(b) + 1. We denote it a b. By Proposition 12, we obtain: Proposition 13. Let p, c be two elements of H n . Then, p c iff there exists m ∈ 1, n such that:

Fig. 21 :Fig. 22 :

 2122 Fig. 21: Flow diagram of Theorem 1.

Definition 5 (

 5 Opposites[START_REF] Mazo | Digital imaging: A unified topological framework[END_REF]). Let a, b, c be three elements of H n . We say that a and b are opposite relatively to c and we denote it a = opp c (b) when a c, b c and β(a) ∩ β(b) = ∅. On Figure 23, some examples of opposite faces are depicted: we have a = opp c (b) with a in red, b in blue, and c in pink.

Fig. 23 :

 23 Fig. 23: Examples of opposites in H 2 : blue and red faces are opposites relatively to the pink face.

Fig. 25 :

 25 Fig. 25: When t and t are opposite relatively to z, then the orders |β(t)| (in blue), |β(t )| (in green) and |β(z) \ (β(t) ∪ β(t ))| (in red) are isomorphic orders.

Fig. 26 :Definition 6 .

 266 Fig. 26: Examples of infimum: β(x) is in red, β(y) is in blue, their intersection is in purple, and the infimum of β(a) ∩ β(b) is surrounded in green.

Fig. 27 :

 27 Fig.27: Decomposing faces of β (z) into (dim(z) + 1)faces. On the left, a (dim(z)+2)-face is decomposed into two (dim(z) + 1)-faces and on the right a (dim(z) + 3)face is decomposed into three (dim(z) + 1)-faces.

Fig. 28 :Fig. 29 :

 2829 Fig.28: When f is of dimension 2 (in green) and when f ∈ β(v) where v is of dimension 0 (in blue), then we have in α(f ) ∩ β(v) a number of one 2-face, of two 1faces (in pink) and of one 0-face.

Fig. 32 :

 32 Fig. 32: Flow diagram of Property 1. The blue points refer to hypotheses assumed to be true.

6. 1 . 6 1 Lemma 26 .

 16126 Under Hyp. 1 and 2, F i contains faces of each dimension in dim(z) + 1, n -Let f, z be two elements of H n such that f ∈ β(z), and let be I = {i ∈ 1, n ;

Fig. 33 :

 33 Fig. 33: Flow diagram of Property 3. The blue points refer to hypotheses assumed to be true.

6. 1 . 8

 18 Minimal number of (dim(z) + 1)-faces into F i under Hyp. 1 and 2

Fig. 34 :

 34 Fig. 34: Flow diagram of Property 5. The blue points refer to hypotheses assumed to be true and the red points are assertions whose diagrams have been already drawn.

6. 1 .

 1 10 Number of components of |β N (z)| under Hyp. 1 and 2

6. 1 .

 1 11 Decomposing components T (F i ) under Hyp. 1 and 2

Fig. 36 :

 36 Fig. 36: Flow diagram of Property 9. The blue points refer to hypotheses assumed to be true and the red points are assertions whose diagrams have been already drawn.

Fig. 38 :

 38 Fig. 38: Flow diagram of Property 11. The blue points refer to hypotheses assumed to be true and the red points are assertions whose diagrams have been already drawn.

6. 1 .

 1 [START_REF] Eckhardt | Digital topology[END_REF] The two characteristical points of |β N (z)| under Hyp. 1 and 2

  16 Z n (a) and Z n (b) are (n -dim(z))-antagonist under Hyp. 1 and 2

Fig. 39 :

 39 Fig. 39: We can observe the structure of β N (z) when we have (n -dim(z)) = 3, assuming that |β N (z)| is not connected: |β N (z)| is then made of 6 1-faces in red, of six 2-faces in blue, and together they correspond to the disjoint union of two 1-surfaces |F 1 | = α (a) ∩ β (z) (on the left) and |F 2 | = α (b) ∩ β (z) (on the right).

Fig. 40 :

 40 Fig. 40: Flow diagram of Lemma 27. The blue points refer to hypotheses assumed to be true and the red points are assertions whose diagrams have been already drawn.

  The flow diagram of Lemma 27 is depicted in Figure 40.

6. 2

 2 The proof that DWCness implies AWCness A list of notations inserted in this section are depicted in Table7, and the flow diagram of Theorem 2 (see below) is depicted in Figure41.

Table 7 :Fig. 42 :

 742 Fig. 41: Flow diagram of the proof that DWCness implies AWCness.

  Theorem 2 is depicted in Figure 43. 7 The n-D Proof for gray-level images

Fig. 43 :

 43 Fig. 43: Flow diagram of Theorem 2. The red point refers to an assertion whose diagram has been already drawn.

Fig. 45 :

 45 Fig. 45: All the threshold sets of U of Figure 44 are AWC since their boundaries are either made of disjoint 1-surfaces in H 2 or empty.

Fig. 46 :

 46 Fig. 46: All the threshold sets (in white) of the image u of Figure 44 are DWC.

Theorem 3 .

 3 Let u : Z n → Z be a gray-level image. Its span-based immersion U : H n H 1 is well-composed in the sense of Alexandrov iff u is digitally well-composed.

Fig. 47 :

 47 Fig. 47: An example of extraction of objects based on the tree-based shape-space [30].

Fig. 48 :

 48 Fig. 48: Extracted from [25]: we start from a color image in (a), we compute its graph-based shape-space, and then we group the shapes which correspond to the same character (w.r.t. some geometrical or alignment criteria). The results of the filtering are shown in (b), (c), and (d) for different filterings.

Fig. 51 :

 51 Fig. 51: Example of saliency-based detection of identity documents captured by smartphones [29].

2 n

 2 β(H(c)) = {{c -1/2, c + 1/2}, {c + 1/2}, {c + 1/2, c + 3/2}}. Also, when y ∈ Z, H(y) = {y, y + 1} ∈ H 1 1 , and then: β(H(y)) = {{y, y + 1}}. If y belongs to {c -1 2 , c + 1 2 }, we obtain that β(H(y)) ⊆ β(H(c)). Conversely, if {{y, y + 1}} is included into {{c -1/2, c + 1/2}, {c + 1/2}, {c + 1/2, c + 3/2}}, it means that y ∈ {c -1/2, c + 1/2}. Proposition 4. Let S be a block in Z n , and let c be its center in Z . Then S and c are related this way:

Lemma 2 .

 2 Let a, b be two elements of H n . Then, α(a) ∩ α(b) = ∅ iff the a ∧ b is WD. Furthermore, when a ∧ b is WD, we can switch the operators × and ∧ in this way:

  and we obtain α(a ∧ b) = α(a) ∩ α(b).

Fig. 52 :

 52 Fig. 52: Study case-by-case showing that, when a, b ∈ H 1 , a ∧ b exists iff α(a) ∩ α(b) = ∅. The closures α(a) and α(b) are depicted in red, and the face encircled in blue corresponds to a ∧ b when it exists.

Lemma 4 .

 4 ∀p, p ∈ Z n , p and p are k-antagonists, k ∈ 0, n , iff H n (p) ∧ H n (p ) is WD and belongs to H n n-k .

Lemma 8 .

 8 Let S be a block of Z n , and let z * ∈ H n be the image by H n of the center of S. For all y ∈ Z n , {y ∈ S} ⇒ {α(H n (y)) ∩ β(z * ) = ∅}.

4 . 6 .

 46 which is the reformulation of a block centered at z * by PropositionProposition Let n ≥ 1 and k ∈ 0, n be two integers. Let |X| = (X, α X ) and |Y | = (Y, α Y ) be two k-surfaces in H n . Then, if |X| is a suborder of |Y |, then |X| = |Y |.Proof. Let us proceed by induction on k. Initialization (k = 0): when |X| and |Y | are two 0-surfaces, the inclusion X ⊆ Y implies directly that X = Y since they have the same finite cardinality, and then |X| = |Y |.

1 )

 1 -surface by Proposition 3, and then is a (dim(a)-1)-surface. Now, we can remark that because b belongs to α (a), we can write: α (a) ∩ β (b) = β α (a) (b), and then, again by Proposition 3, |α (a)∩β (b)| is a ((dim(a)-1) -ρ(b, |α (a)|) -1)-surface. Since we have:

  Fig.53: Assuming that a and b cover c, that the index i * is defined such that a i * = c i * and that the index j * defined such that b j * = c j * . When i * and j * are different, we obtain that β(a) ∩ β(b) in light gray is not empty.

  Fig. 54: When z belongs to the block S where x and y are antagonist, we have the relation α(H n (x)) ∩ α(H n (y)) ⊆ α(H n (z)) ∩ α(H n (y)).

Lemma 14 .( 2 )

 142 Let a, b be two elements of H n . Then, {β(a) ∩ β(b) = ∅} ⇔ {a ∨ b is WD } .Furthermore, when a ∨ b is WD, it satisfies the relations:   a ∨ b = × i∈ 1,n (a i ∨ b i ), β(a ∨ b) = β(a) ∩ β(b).Proof. Let us treat first the case a 1 , b 1 ∈ H 1 and let us proceed case by case.(1) When a 1 , b 1 are in H 1 0 , then there exists i, j ∈ Z such thata 1 = {i} et b 1 = {j}. Then β(a 1 ) = {{i -1, i}, {i}, {i, i + 1}}, β(b 1 ) = {{j -1, j}, {j}, {j, j + 1}}. (A) Then i = j and β(a 1 ) ∩ β(b 1 ) = {{i -1, i}, {i}, {i, i + 1}} and a 1 ∨ b 1 = {i} which implies that β(a 1 ) ∩ β(b 1 ) = β(a 1 ∨ b 1 ). (B) Or i = j -1, and β(a 1 ) ∩ β(b 1 ) = {{i, i + 1}} and a 1 ∨ b 1 = {i, i + 1}, which implies β(a 1 ) ∩ β(b 1 ) = β(a 1 ∨ b 1 ).(C) Or i = j + 1, and β(a 1 ) ∩ β(b 1 ) = {{j, j + 1}} anda 1 ∨ b 1 = {j, j + 1}, which implies β(a 1 ) ∩ β(b 1 ) = β(a 1 ∨ b 1 ). (D) Or i ∈ {j -1, j, j + 1}, then β(a 1 ) ∩ β(b 1 ) = ∅ and a 1 ∨ b 1 does not exist. When a 1 ∈ H 1 1 and b 1 ∈ H 1 0 , then there exist i, j ∈ Z such that a 1 = {i, i + 1} and b 1 = {j}. Then β(a 1 ) = {{i, i + 1}}, β(b 1 ) = {{j -1, j}, {j}, {j, j + 1}}. (A) Then i = j, β(a 1 ) ∩ β(b 1 ) = {{i, i + 1}}, a 1 ∨ b 1 = {i, i + 1}and β(a 1 ) ∩ β(b 1 ) = β(a 1 ∨ b 1 ). (B) Or i = j -1, β(a 1 ) ∩ β(b 1 ) = {{j -1, j}}, a 1 ∨ b 1 = {j -1, j}, and β(a 1 ) ∩ β(b 1 ) = β(a 1 ∨ b 1 ). (C) Or i ∈ {j -1, j}, then β(a 1 ) ∩ β(b 1 ) = ∅ and a 1 ∨ b 1 does not exist.

  (A) Then i = j, which implies β(a 1 )∩β(b 1 ) = {{i, i+1}}, a 1 ∨ b 1 = {i, i + 1} and β(a 1 ) ∩ β(b 1 ) = β(a 1 ∨ b 1 ). (B) Or i = j, β(a 1 ) ∩ β(b 1 ) = ∅ and a 1 ∨ b 1 does not exist. When a, b belong to H n , n ≥ 1, such that β(a) ∩ β(b) = ∅,we obtain that:

  n a i ∨b i and then a∨b = × i∈ 1,n a i ∨ b i , and β(a ∨ b) = β(a) ∩ β(b).

Lemma 18 .

 18 Let us assume that n ≥ 2. Let z be in H n such that dim(z) ≤ n -2, and let a, b be inH n n ∩ β (z). Then α (a) ∩ α (b) ∩ β (z) = ∅ implies that Z n (a) and Z n (b) are (n -dim(z))-antagonist into Z n . Proof. The fact that a, b ∈ β (z) implies that z ∈ α (a) ∩ α (b), and then α(a) ∩ α(b) = ∅, which implies that a ∧ b exists and α(a) ∩ α(b) = α(a ∧ b) by Lemma 2. This way, z ∈ α (a) ∩ α (b) ⊆ α(a ∧ b),and then a ∧ b ∈ β(z). Let us assume that we have a = b. Thenα (a) ∩ α (b) ∩ β (z) = α (a) ∩ β (z) is a (n -dim(z) -2)-surface by Proposition 7, and then is non empty (because (n -dim(z)) ≥ 2). This is impossible by hypothesis, and then we have a = b. Since a and b are different and they are both into H n n , they are not neighbors and this way α (a) ∩ α (b) = α(a) ∩ α(b) = α(a ∧ b). We obtain that α(a ∧ b) ∩ β (z) = ∅. We have seen that z ∈ α(a ∧ b), then α(a ∧ b) ∩ β (z) ∪ {z} = α(a ∧ b) ∩ β(z) = {z}, and then z = a ∧ b. By Lemma 4, we deduce that Z n (a) and Z n (b) are (n -dim(z))-antagonists.

  ρ(v, |F i |) = max ρ(u, |F i |) ; u ∈ α (v) ∩ F i + 1, = max dim(u) -dim(z) -1 ; u ∈ α F i (v) + 1, = max dim(u) ; u ∈ α F i (v) -dim(z). Since v ∈ F i , α(v)∩β (z) ⊆ F i and then α (v)∩β (z) ⊆ α F i (v), which leads to: max dim(u) ; u ∈ α F i (v) , ≥ max dim(u) ; u ∈ α (v) ∩ β (z) , ≥ dim(v) -1,and in the same time,max dim(u) ; u ∈ α F i (v) ≤ dim(v) -1 because u ∈ α (v). This way, max dim(u) ; u ∈ α F i (v) = dim(v) -1 and then ρ(v, |F i |) = dim(v) -dim(z) -1 = k. The direct implication is then proved.Let us assume now that v ∈ F i satisfies ρ(v, |F i |) = k. By the induction hypothesis, we obtain one more time:ρ(v, |F i |) = max dim(u) ; u ∈ α F i (v) -dim(z).



  F i ⊆ β (z), which implies by Property 10 that F i ⊆ α belongs to H n n by Property 9. Also,F i ∩H n n = ∅, and then we have F i ⊆ α

  Then, Z n (a) and Z n (b) are (n -dim(z))-antagonist in Z n . Proof. Since by Property 11, we have F 1 = α (a) ∩ β (z) and F 2 = α (b) ∩ β (z), and since they are disjoint, then we have: α (a) ∩ α (b) ∩ β (z) = ∅. By Lemma 18, Z n (a) and Z n (b) are then (n-dim(z))-antagonists.

.

  |β N (z)| is not connected. At the same time, we assume that the components |F i | of β N (z) are (n -dim(z) -2)-surfaces. Then the two characteristical faces a and b exist by Property 12. Now, let u, v be in S(z) \ {Z n (a), Z n (b)}. Since this set is 2n-connected for (n -dim(z)) ≥ 3 by Lemma 19, there exists a 2n-path π = (p 0 = u, . . . , p l = v) joining u and v into S(z) \ {Z n (a), Z n (b)} with l ≥ 1. We can deduce from it a path π into H n such that: n(p 0 ), H n (p 0 ) ∧ H n (p 1 ), H n (p 1 ), . . . , H n (p l-1 ), H n (p l-1 ) ∧ H n (p l ), H n (p l )For all m into 0, l -1 , we haveH n (p m-1 ) ∧ H n (p m ) ∈ H n n-1since p m-1 and p m are 2n-neighbors into Z n .Let us assume now that there exists a value m ∈ 0, l -1 such that H n (p m-1 ) ∧ H n (p m ) ∈ N, then H n (p m-1 ) ∧ H n (p m ) ∈ β N (z) and then: either H n (p m-1 ) ∧ H n (p m ) ∈ α (a) ∩ β (z) and then β (H n (p m-1 ) ∧ H n (p m )) = {H n (p m-1 ), H n (p m )}contains a, which is impossible by definition of π, or H n (p m-1 ) ∧ H n (p m ) ∈ α (b) ∩ β (z) and then β (H n (p m-1 ) ∧ H n (p m )) = {H n (p m-1 ), H n (p m )} contains b, which is impossible for the same reason.

Table 4 :

 4

Notations relative to the immersion from Z 2 n to H n .

  Let S be a block of Z n , and let z * ∈ H n be the image by H n of the center of S. For all y ∈ Z n ,

	α(Hn (y))
		Hn (S)	Hn(S)
		z *
	α(Hn (y))	Hn (S)	Hn(S)
	Fig. 16: When y (whose image by H n is one of the big
	square in blue) does not belong to the block S centered
	at Z n (z * ) (z * is depicted in black), we obtain that the
	closure of H n (y) (the sets of 9 faces in blue) does not
	intersect the opening in H n n of z * (in red).
	Lemma 8. {y ∈ S} ⇒ {α(H n (y)) ∩ β(z
	3.4 Property of images of blocks by H n
	Let us observe a basic property of the image of blocks
	by the bijection H n .
	Proposition 4 implies that:

* ) = ∅}.

Table 6 :

 6 Notations relative to the relation between to H n and (Z/2)

n . Proposition 12. Let p, c be two elements in H n . We have the following equivalence:

Table 8 :

 8 Notations related to gray-level images.

  whose cardinality is equal to k thanks to Lemma 2. Now, let us observe that, for any i ∈ 1, n ,p i ∈ {p i -1, p i +1} iff z i ∧z i ∈ H 1 0, then p and p have exactly k different coordinates, and they differ from one. Then, p and p are antagonists in a block of dimension k by Lemma 3.Lemma 5. Let p, p be two elements of Z n such that p and p are (3 n -1)-neighbors in Z n or equal. Then,

	H n	p + p 2	= H

n (p) ∧ H n (p ). Proof. Since p and p are (3 n -1)-neighbors in Z n or equal, they are antagonists in a block of dimension k ∈ 0, n , and then by Lemma 4, H n (p) ∧ H n (p ) is WD. Now, let us prove that:

  Proof. Since p and v are 2n-neighbors, they are antagonists in a block of dimension 1. Then, by Lemma 4, H n (p) ∧ H n (v) is WD. For the same reason, H n (p) ∧ H n (p ) is WD. By Lemma 2, the first term of the relation is equal to:

).

  It is sufficient to show that the hypothesis of non connectivity of |β N (z)| and of presence of two opposite faces in a same connected component of |β N (z)| are incompatible. The reasoning of this proof is depicted on Figure 31. Let i be in I such that there exists t, t ∈ H n dim(z)+1 ∩ F i satisfying t = opp z (t).

∈ N. In other words, when X contains a primary or secondary critical configuration, the image by H n of the center of the critical configuration belongs to the boundary N of the immersion of X.

Proof. Let v be a 2n-neighbor of p in S, which is possible since dim(S) ≥ 1. Then, v and p are 1-antagonists which implies by Lemma 4 that H n (p) ∧ H n (v) is WD. Hence, by Lemma 2:

If we assume that v belongs to X, it means that v = p , or in other words that k = 1, which is wrong since dim(S) ≥ 2. Then, v ∈ Y , and so

by Proposition 9. Now, using Proposition 5,

) by Lemma 7, and thus to N.

C Proofs of Section 5

Proposition 12. Let p, c be two elements in H n . We have the following equivalence:

Proof. Let us prove first that p ∈ β(c) implies this set of four properties. The relation p ∈ β(p) is equivalent to say that for any i ∈ 1, n , p i ∈ β(c i ). Each term p i belongs to H 1 1 or to H 1 0 , and so does c i , which leads to four cases. Then, assuming that for i ∈ 1, n , we have p i ∈ β(c i ), we obtain that:

This leads to the 4 formulas described above, which concludes the direct implication.

Conversely, it we have these four properties, 1 2 (p)∩1 (c) = ∅ shows that:

and since in these three cases, we obtain that

Proposition 13. Let p, c be two elements of H n . Then, p c iff there exists m ∈ 1, n such that:

Proof. We can reformulate the fact that we have p c in the following manner (see Proposition 12):

By (4), 1 (Z n (c)) ⊆ 1 (Z n (p)), and then (2) can be reformulated:

which implies that at least the dim(c) integral coordinates of Z n (c) are integral for Z n (p). Since dim(p) = dim(c) + 1 by ( 5), p admits one more integral coordinate than c and it

and then there exists one index of coordinate m ∈ 1, n such

By (1) to (4), we obtain then that for each coordinate i ∈ 1, n , Z(p i ) = Z(c i ) except for the case i = m where:

which concludes the direct sense.

Conversely, if there exists m ∈ 1, n such that :

Proof. For each m ∈ 1 2 (Z n (z)), we have that the two faces H n (Z n (z) -1 2 e m ) and H n (Z n (z) + 1 2 e m ) belong to β (z). Then for all m ∈ 1 2 (Z n (z)), we have the possible cases:

-H n (Z n (z)-1 2 e m ) ∈ T (F i ), and then H n (Z n (z)+ 1 2 e m ) ∈ T (F i ) (by Property 1), (P 1)

or H n (Z n (z) + 1 2 e m ) ∈ T (F i ), and then H n (Z n (z) -1 2 e m ) ∈ T (F i ) (for the same reason as before), (P 2)

By (P 1) and (P 2), we have at most (n-dim(z)) faces into T (F i ) ⊆ β (z). If there exists a coordinate m ∈ 1 2 (Z n (z)) such that (P 3) is true, we will have less than (n -dim(z)) (dim(z) + 1)-faces into T (F i ), what is impossible by Property 5, then (P 3) is never true. We have then either (P 1) or (P 2) for each m ∈ 1 2 (Z n (z)). This way, there exists for

Since these two sets have (n -dim(z)) faces and since they satisfy an inclusion relationship, they are equal, and then:

Property 9. We assume that n ≥ 3 and that there exists z ∈ N such that dim(z) ≤ (n -3) and that β N (z) is not connected (Hypothesis 1). We assume also that each component of β N (z) is a (n -dim(z) -2)-surface (Hypothesis 2). For all i ∈ I, t∈T (F i ) t exists in H n n ∩β (z). We will call this face the characteristical face of the component F i .

Proof. Let i be a coordinate in I. It is sufficient to show that:

By Property 8, there exists a family of faces

. This way:

β(t m j ).

When j belongs to 1 (Z n (z)), we obtain t m j = z j because t m belongs to β(z). Then

When j belongs to 1 2 (Z n (z)),

Then each term

β(t m j ) is non empty, and then

The fact that t∈T (F i )

t belongs to H n n is due to the fact that Card (T (F i )) = (n -dim(z)) by Property 6 and to the fact that the faces of T (F i ) are different two by two.

Property 10. We assume that n ≥ 3 and that there exists z ∈ N such that dim(z) ≤ (n -3) and that β N (z) is not connected (Hypothesis 1). We assume also that each component of β N (z) is a (n -dim(z) -2)-surface (Hypothesis 2).

For each i ∈ I:

Proof. Let u be in F i , u ∈ β (z), and then by Lemma 15,

and then: either Z n (a) ∈ X, then v a ∈ Y , from which we deduce that v b ∈ Y , and then Z n (b) ∈ X (and X contains a primary critical configuration), or Z n (a) ∈ Y , then v a ∈ X, from which we deduce that v b ∈ X, and then Z n (b) ∈ Y (and X contains a secondary critical configuration).

By Property 12, this critical configuration is of dimension (n -dim(z)).

In brief, either we have X ∩ S(z) = {Z n (a), Z n (b)} or we have X ∩S(z) = S(z)\{Z n (a), Z n (b)} where both are critical configurations of dimension (n -dim(z)).