Loïc Mazo
email: loic.mazo@unistra

Nicolas Passat
email: passat@unistra.fr

Michel Couprie
email: m.couprie@esiee.fr

Christian Ronse
email: cronse@unistra.fr

Paths, homotopy and reduction in digital images

Keywords: topology, digital imaging, paths, fundamental group, homotopy-type preservation

The development of digital imaging (and its subsequent applications) has led to consider and investigate topological notions, well-defined in continuous spaces, but not necessarily in discrete/digital ones. In this article, we focus on the classical notion of path. We establish in particular that the standard definition of path in algebraic topology is coherent w.r.t. the ones (often empirically) used in digital imaging. From this statement, we retrieve, and actually extend, an important result related to homotopy-type preservation, namely the equivalence between the fundamental group of a digital space and the group induced by digital paths. Based on this sound definition of paths, we also (re)explore various (and sometimes equivalent) ways to reduce a digital image in a homotopy-type preserving fashion.

In the mathematics community, after the pioneering works of Alexandroff, McCord [START_REF] Mccord | Singular homology groups and homotopy groups of finite topological spaces[END_REF] firmly linked finite spaces with simplicial complexes, while Stong [START_REF] Stong | Finite topological spaces[END_REF] undertook homeomorphism and homotopy type classifications. Many years later, at the end of the century, this subject yielded new developments whose main goal was to classify simplicial complexes via finite spaces [START_REF] Hardie | Homotopy theory of finite and locally finite T 0 -spaces[END_REF][START_REF] Osaki | Reduction of finite topological spaces[END_REF][START_REF] Barmak | Minimal finite models[END_REF][START_REF] Kukieła | On homotopy types of Alexandroff spaces[END_REF].

In the computer science community, works have essentially focused on specific -and pragmatic-questions related to topology, namely the definition of a notion of adjacency relation, and the induced notions of connectivity and arcs. These notions enable in particular to lead to high-level concepts of topology, such as homotopy, with natural applications to "homotopy type-preserving" transformations of topological spaces/digital images. The first -and very intuitive-solution to define an adjacency relation on Z n is to consider that two points are adjacent if there are neighbours in the n-D cubic grid (possibly enriched by some well chosen sets of "diagonals"). This framework led -in order to avoid paradoxical intersections between objects-to the classical definition of dual adjacencies in digital images [START_REF] Rosenfeld | Sequential operations in digital picture processing[END_REF][START_REF] Duda | Graphical data processing research study and experimental investigation[END_REF][START_REF] Rosenfeld | Connectivity in digital pictures[END_REF]. In this approach, known as digital topology, no topology is however actually defined and there are, in particular, no open/closed sets. To retrieve topological notions, a possible way is to define continuous analogues of n-D digital images, assuming that each point in such images physically corresponds to a unit n-cube of the Euclidean space. Following this analogy, it becomes possible to justify the use of dual adjacencies [START_REF] Ronse | An isomorphism for digital images[END_REF] and to define algebraic structures isomorphic to those used in topology [START_REF] Kong | A digital fundamental group[END_REF][START_REF] Lee | Holes and genus of 2D and 3D digital images[END_REF]. An alternative way to deal with connectivity in digital pictures is to find a topology in Z n , i.e., a family of subsets of Z n (defined as open sets), leading to the desired adjacency relation (in this framework, two points x, y are adjacent if the set {x, y} is connected). In [START_REF] Kong | The Khalimsky topologies are precisely those simply connected topologies on Z n whose connected sets include all 2n-connected sets but no (3 n -1)-disconnected sets[END_REF], it is proved that there is only one convenient solution -the product of Khalimsky lines [START_REF] Khalimsky | Topological structures in computer science[END_REF]-for defining such a framework, unfortunately this solution breaks the homogeneity of Z n . (To avoid this phenomenon, it is necessary to add points between those actually in the image, which is equivalent to identify the points of a digital image with some cells of abstract cellular complexes [START_REF] Kovalevsky | Finite topology as applied to image analysis[END_REF][START_REF] Klette | Topologies on the planar orthogonal grid[END_REF].) All these topological models have found practical applications in the context of digital image analysis, especially for the definition of "topology-preserving" procedures (i.e., procedures enabling to modify a binary digital image without altering its homotopy type), including reduction ones (used for skeletonisation or segmentation), see e.g. [START_REF] Couprie | New characterizations of simple points in 2D, 3D and 4D discrete spaces[END_REF].

The quite pragmatic motivations of the works on topological modelling of digital images can probably explain why most of the proposed definitions only aim at mimicking or adapting the definitions of the classical topology to retrieve intuitive notions such as connectivity and continuous deformation. Moreover, if the works of Alexandroff are relatively well known in both (mathematics and computer science) communities, those of McCord and Stong have visibly never been considered in the research related to topology in digital images. Consequently, it is generally believed that the classical definitions of topology cannot be "directly" embedded in the universe of digital images in a sound fashion 1 (i.e., while preserving their correct and intrinsic properties). In particular, it seems that paths in finite spaces have been quite systematically replaced by ad hoc definitions. This justifies to carefully explore the relations between continuous paths and digital paths of finite spaces.

The purpose of this article is to study the consequences of the use of the general topology standard definition of a path, namely a continuous function from [0, 1], when working in a digital space. We describe the images of such paths in a digital space and compare them with the regular digital paths defined in the framework of the Khalimsky topology [START_REF] Khalimsky | Computer graphics and connected topologies on finite ordered sets[END_REF] or in the equivalent framework of abstract cellular complexes [START_REF] Kovalevsky | Finite topology as applied to image analysis[END_REF]. We show that both definitions lead to very close geometrical objects: our first main result (Theorem 2) states that under each continuous path p, lies another continuous path which is a step function (for such a path, we say a finite path), whose image is included in the image of p and which is equal to p for at least one value of the parameter in each step interval. We also look at homotopy equivalence between paths and describe their discrete counterparts that we call deformations. We show that two finite paths with a same image are homotopically equivalent and our second main theorem (Theorem 3) establishes that two finite paths with distinct images are homotopically equivalent iff the image of one of them is a deformation of the image of the other one. Then, we retrieve (and in fact, extend, since we do not suppose the ambiant space to be finite), without the need of high level preliminary results, the property recently proved in algebraic topology [START_REF] Barmak | Minimal finite models[END_REF] that the fundamental group of a digital space is isomorphic to the group of digital paths equipped with the deformations. Since our model is based on classical definitions, we have the possibility of reinvest any external result in the field of image analysis and processing. In particular, we explore and compare some tools devoted to the reduction of finite, or countable, spaces and which have counterparts in continuous analogues embedded in the Euclidean space.

In order to do so, Section 2 first recalls background notions related to general topology and partially ordered sets. (These notions enable to make this article globally self-contained, and then more comprehensible for the reader.) In Section 3, we study in detail the paths in digital images, i.e., the continuous functions of [0, 1] → Z n (where Z n is interpreted from the topological point of view mentioned above) and we justify why we can avoid to consider the "functional side" of paths. In particular, we prove that the fundamental group of a digital space is isomorphic to the "fundamental-like" group which is generally considered in digital image analysis. Then, topological algebraic structures being well defined, we can borrow any tool in the existing literature on countable/finite spaces for use in image analysis and processing. Thereby, in Section 4, we study and confront various ways to make minimal changes in a digital image while preserving, as far as possible, its topology. Concluding remarks will be found in Section 5.

Background notions

General topology

In this subsection, we recall some basic definitions and classical properties of topology without proof. The main purpose here is to introduce useful notations and to gather results needed in the sequel of the article. The reader interested in proofs, or details on a particular notion, can find them in any lecture book on general topology (for example, [START_REF] Munkres | Topology[END_REF][START_REF] Ya | Elementary Topology: Problem Textbook[END_REF]) or on algebraic topology (for example, [START_REF] Hatcher | Algebraic Topology[END_REF][START_REF] Maunder | Algebraic Topology[END_REF][START_REF] May | A Concise Course in Algebraic Topology[END_REF].

Topological spaces

Let X be a set, the elements of which will be called points. A topology on X is a collection U of subsets of X, called open sets, such that:

• = X \ X \ Y and Y = X \ (X \ Y) • . For any subset Y ⊆ X, the set U Y = {U ∩ Y | U ∈ U} is
a topology on Y called the topology induced by U on Y. The set {∅, X} is a topology on X called the trivial, or indiscrete, topology. The set 2 X of all subsets of X is a topology which is called discrete in mathematics. Here, since we find this designation confusing with the meaning of topology in a discrete space, we will call it ultra-discrete. Topology is a tool to give a precise meaning to the intuitive notion of "nearness". With the trivial topology, any point in X is near any other point in X while with the ultra-discrete topology, the space is totally disconnected. So, we are not interested by these two topologies but for examples and counterexamples. Therefore we must look at other topologies to use in finite or discrete spaces.

Continuous maps and spaces classification

Let X, Y be topological spaces (i.e., spaces equipped with a topology). A function f : X → Y is continuous if the preimage of any open set of Y is an open set of X. In particular, if the topology on Y has a basis B and the preimage of any set of B is an open set in X, then f is continuous. If f is bijective and both f and f -1 are continuous, then f is a homeomorphism and the spaces X, Y are called homeomorphic.

If Y is a subset of X, Y is a retract of X if there exists a continuous map, called a retraction, r : X → Y such that r(y) = y for all y ∈ Y. A continuous map r : X × [0, 1] → X is a (strong) deformation retraction if, for every x in X, y in Y we have r(x, 0) = x, r(x, 1) ∈ Y and r(y, 1) = y (and for every t in [0, 1], r(y, t) = y). If such a map exists, Y is a (strong) deformation retract of X.
When Y is not a subspace of X, there exists however a similar notion as the one of retraction. Two continuous maps f, g : X → Y are homotopic if there exists a continuous map, called a homotopy, h : X × [0, 1] → Y such that h(x, 0) = f (x) and h(x, 1) = g(x) for all x ∈ X. The spaces X and Y are homotopy equivalent (or have the same homotopy type) if there exist two continuous maps f : X → Y and g : Y → X, called homotopy equivalences, such that g • f is homotopic to the identity map id X and f • g is homotopic to id Y . If X and Y are homeomorphic, they are homotopy equivalent: given a homeomorphism ϕ between X and Y, ϕ and ϕ -1 are homotopy equivalences between X and Y. The converse is not true in general (for example, a ball is homotopy equivalent -but not homeomorphic-to a point). A topological space is contractible if it has the homotopy type of a single point.

Topological properties

A topological space X is connected if it cannot be split into two non-empty open sets. The union of any collection of connected subspaces of X, pairwise intersecting, is connected. In particular, if X, Y are connected and X ∩ Y ∅, then X ∪ Y is connected. The connected components of X are the maximal (for inclusion) connected subspaces of X. Every x in X belongs to exactly one such component since the set {x} is connected and the union of all connected sets containing x is connected and -trivially -maximal for inclusion. Hence, the connected components of a space X form a partition of X. Note also that the image of a connected set by a continuous map is connected.

Let x 1 , x 2 be two points in X. A path from x 1 to x 2 in X is a continuous map π : [0, 1] → X with π(0) = x 1 and π(1) = x 2 . A space X is path-connected if for every pair (x 1 , x 2 ) in X, there is a path from x 1 to x 2 in X. A path-connected space is connected.

A space X is compact if from each collection of open sets, the union of which is X (such a collection is called a cover), one can extract a finite cover. The image of a compact set by a continuous map is also compact.

A space X satisfies the separation axiom T 0 (or, shortly, is a T 0 -space) if for every pair (x 1 , x 2 ) (x 1 x 2 ) in X there is an open set of X which contains exactly one element of the pair. That is, one can distinguish them from a topological viewpoint. It is equivalent to state that x 1 does not belong to the closure of {x 2 } or x 2 does not belong to the closure of {x 1 }. If for every pair (x 1 , x 2 ) (x 1 x 2 ), x 1 does not belong to the closure of {x 2 } and x 2 does not belong to the closure of {x 1 }, that is, if for each x ∈ X, {x} is closed, then X is a T 1 -space. Hausdorff spaces, or T 2 -spaces, like R n equipped with the usual topology, have a stronger property: any two distinct points have disjoint neighbourhoods. Note that a T 2 -space is T 1 and a T 1 -space is T 0 .

Algebraic topology

Let X be a topological space. Two paths p, q in X are equivalent if they have the same extremities (i.e., p(0) = q(0) and p(1) = q(1)) and are homotopic by an homotopy h such that h(0, u) = p(0) = q(0) and h(1, u) = p(1) = q(1) for all u ∈ [0, 1]. It is easy to check that this relation on paths is actually an equivalence relation. We write [p] for the equivalence class of p. If p, q are two paths in X such that p(1) = q(0) we can define the product p • q by:

(p • q)(t) = p(2t) if t ∈ [0, 1 2 ], q(2t -1) if t ∈ [ 1 2 , 1].
This product is well defined on equivalence classes by [p]

• [q] = [p • q]. Let x be a point of X.
A loop at x is a path in X which starts and ends at x. The product of two loops at x is a loop at x and the set π 1 (X, x) of equivalence classes of loops at x is a group for this product.

It is called the fundamental group of X (with basepoint x) or the first homotopy group of X. If X is path-connected, the group π 1 (X, x) does not depend on the basepoint (i.e., for any points x, y ∈ X, π 1 (X, x) and π 1 (X, y) are isomorphic). Higher homotopy groups are defined by replacing loops at x by continuous maps from [0, 1] n to X that associate the boundary of the n-cube to x. The product on such maps is then defined by gluing two faces of the n-cubes:

p • q(t 1 , . . . , t n ) = p(2t 1 , t 2 , . . . , t n ) if t 1 ∈ [0, 1 2 ], q(2t 1 -1, t 2 , . . . , t n ) if t 1 ∈ [ 1 2 , 1].
Conventionally, the set of path-connected components of X is denoted by π 0 (X, x), but it has no group structure.

Let X and Y be two topological spaces with base points x and y. A continuous map f : X → Y is a weak homotopy equivalence if the morphisms

f n : π n (X, x) → π n (Y, y) defined by f n ([p]) = [ f • p]
are all bijective ( f 0 is just a bijection, not a morphism). Two spaces X, Y are weakly homotopy equivalent if there is a sequence of spaces X 0 = X, X 1 , . . . , X r = Y (r 1) such that there exist weak homotopy equivalences X i-1 → X i or X i → X i-1 for all i ∈ [1, r]. Hence, two weakly homotopy equivalent spaces X, Y have isomorphic homotopy groups.

Two homotopy equivalent spaces are weakly homotopy equivalent (the converse is not true in general but the Whitehead's theorem [START_REF] Whitehead | Combinatorial homotopy[END_REF][START_REF] Whitehead | Combinatorial homotopy[END_REF]) states that it is true in complexes (see Section 4.1).

Partially ordered sets

Because of their capacity to encompass all topological approaches on digital images, our work is presented in the framework of posets (Partially Ordered SETS). For this reason, but mainly to show how discrete spaces are concerned with continuity, this subsection on partially ordered sets is more detailed than the previous ones. We give proofs, as far as possible, while we state properties with hypothesis close to our subject. Readers interested in more general hypothesis may refer to [START_REF] Alexandroff | Diskrete Räume[END_REF][START_REF] Mccord | Singular homology groups and homotopy groups of finite topological spaces[END_REF][START_REF] Stong | Finite topological spaces[END_REF][START_REF] Arenas | Alexandroff spaces[END_REF][START_REF] May | Finite topological spaces[END_REF][START_REF] May | Finite spaces and simplicial complexes[END_REF].

Let X be a set. A binary relation on X is a partial order if it is reflexive, antisymmetric, and transitive. A partially ordered set, or poset, is a couple (X, ) where the relation is a partial order on X. The relation defined on X by x y if y x is a partial order on X called the dual order. We say that two points x, y in X are comparable if x y or y x. We say that a poset is locally finite if for each point x in X, there are finitely many points comparable with x (note that for many authors, locally finite means that each point x has a finite neighbourhood). As an example, N equipped with the dual of the usual order (i.e., with ) is not locally finite with the definition we use though each point n ∈ N has a finite neighborhood [0, n] (see Theorem 1 for the definition of the topology). If, for all pairs (x, y) of elements of X, x and y are comparable, the relation is a total order on X. A chain in X is a totally ordered subset of X. A poset is finite-dimensional if there is an integer n such that any chain in X has a cardinal less or equal than n + 1. The smallest integer n having this property is called the dimension of X and we write n = dim(X).

We write x⊳y when x y and x y and we set:

-x ↑ = {y ∈ X | x y} and x ↑⋆ = x ↑ \ {x} = {y ∈ X | x⊳y}; -x ↓ = {y ∈ X | y x} and x ↓⋆ = x ↓ \ {x} = {y ∈ X | y⊳x}.
If x and y are comparable, we write x ≍ y; otherwise, we write x y. The set of points comparable with a given point x is denoted x (x = x ↓ ∪ x ↑ ) and

x ⋆ = x \ {x} = x ↓⋆ ∪ x ↑⋆ . A point x ∈ X is minimal if x ↓ = {x} and maximal if x ↑ = {x}. A point x ∈ X is the minimum of X if x ↑ = X and is the maximum of X if x ↓ = X.
The Hasse diagram is the oriented graph of the covering relation defined by: y covers x (x ≺ y) if x⊳y and there is no z such that x⊳z⊳y. Orienting all arcs from top to bottom, this diagram offers good visual representations of (small) posets (see Figure 8).

Topology in posets

Let us forget for a while posets in order to define Alexandroff spaces. A topological space X is an Alexandroff space if any intersection of open sets is an open set. In such a space, closed sets satisfy the definition properties of open sets, namely, ∅, X are closed sets, any union and any intersection of closed sets is a closed set, so one can exchange open and closed sets, tThe obtained topology is then called the dual topology. As any set has a closure, any element x of an Alexandroff space has a smallest neighbourhood (an open set included in any open set containing x), denoted by U x , which is the closure of {x} for the dual topology. Conversely, a topological space X in which each point has a smallest neighbourhood is an Alexandroff space. Moreover, since for any open set V ⊆ X, we have V = x∈V U x , the set of smallest neighbourhoods is a basis for the topology. When a topological set X has the T 1 -separation property, each singleton is closed; thus an Alexandroff space with the T 1separation property is ultra-discrete. It is the reason why the only Alexandroff spaces worthy of interest are non-T 1 . We call the T 0 -Alexandroff spaces A-spaces. McCord has proved in [START_REF] Mccord | Singular homology groups and homotopy groups of finite topological spaces[END_REF] that if an Alexandroff space is not T 0 , the identification of the points that share the same smallest neighbourhood give a homotopy equivalent quotient space which is T 0 . Now let us go back to posets with the next theorem known as Alexandrov specialisation theorem which establishes a canonical link between A-spaces and posets.

Theorem 1 ([1]

) Let (X, U) be an A-space. The relation defined on X by x y if y ∈ U x is a partial order on X. Conversely, let (X, ) be a poset. The set U defined by U = {U ⊆ X | ∀x ∈ U, x ↑ ⊆ U} is a topology on X, (X, U) is an A-space and, for all x ∈ X, U x = x ↑ .

If Y is a subset of X, the topology associated to the poset (Y, ) is the topology induced by the one associated to the poset (X, ). The dual topology of the topology associated to the poset (X, ) is the topology associated to the dual order .

From now on, posets will always be equipped with the topology U described in Theorem 1.

The easy following property founds an interesting application when a continuous function, like a path, is defined from a compact subset of R n , that is a closed bounded subset, to a locally finite poset.

Property 1 Any compact locally finite poset is finite.

Proof Let X be a compact locally finite poset. Since X is compact, there exists a finite set A ⊆ X such that (U x ) x∈A is a finite subcover of the open cover (U x ) x∈X . As X is locally finite, each U x is finite and, therefore, X = x∈A U x is finite.

Continuity and connectivity

Property 2 Let X, Y be posets. A function f : X → Y is continuous iff it is non-decreasing.
Proof ( [START_REF] Stong | Finite topological spaces[END_REF]) (Stong assumes X and Y to be finite, but he does not use it in his proof) Suppose that f is continuous. Let x 1 x 2 be two points in

X. Since f -1 (U f (x1) ) is an open set contain- ing x 1 , it includes x ↑ 1 so x 2 ∈ f -1 (U f (x1) ) and f (x 2 ) ∈ U f (x1) , that is f (x 1 ) f (x 2 )
. Conversely, suppose that f is non-decreasing. For some y ∈ Y, take x ∈ f -1 (U y ), which means y f (x). For any

x ′ ∈ U x , x x ′ , so y f (x) f (x ′ ) and x ′ ∈ f -1 (U y ). Hence U x ⊆ f -1 (U y ) for any x ∈ f -1 (U y ). That is, f -1 (U y ) is open. Let x, y ∈ X. We say that x, y are adjacent if the set {x, y} is connected. A sequence (x i ) r i=0 (r 0) of points in X is an arc in X (from x 0 to x r ) if for all i ∈ [1, r],
x i-1 and x i are distinct and adjacent. The integer r is the length of the arc (

x i ) r i=0 . If for all x i , 1 i r -1, x i-1 < x i ⇔ x i > x i+1
, we say that the arc is minimal2 . If for all x, y ∈ X there exists an arc in X from x to y, we say that X is arc-connected. Property 3 Two points x, y ∈ X are adjacent iff x and y are comparable.

Proof Let S = {x, y} and suppose x, y are not comparable, that is x U y and y U x . Then, U x ∩ S = {x} and U y ∩ S = {y} are disjoint open sets of S . Therefore, S is not connected. If x, y are comparable, for example x y, every open set containing x contains y, so it is impossible to break S into two non-empty open sets. Thus S is connected.

Lemma 1 Let X be a poset. If x and y are comparable, then there is a path from x to y.

Proof ([36]) (Stong assumes X and Y to be finite, but he does not use it in his proof) Suppose x y and let p : [0, 1] → X be the function defined by p(t) = x if t 1 2 and p(t) = y if t > 1 2 . We claim that p is continuous, i.e., p is a path. To prove this assertion, it is sufficient to prove that for any

U z , p -1 (U z ) is open in [0, 1]. If x, y U z , then p -1 (U z ) is empty and thus is open. If x ∈ U z , z x y so y ∈ U z and p -1 (U z ) = [0, 1] is open. If x U z and y ∈ U z , then p -1 (U z ) =] 1 2 , 1] which is an open set of [0, 1].
The material for the next property, and for its proof, is also in [START_REF] Stong | Finite topological spaces[END_REF].

Property 4 Let X be a poset. The following statements are equivalent:

1. X is path-connected; 2. X is connected; 3. X is arc-connected.
Proof 1 ⇒ 2 is true in any topological space. To prove 2 ⇒ 3, suppose X is connected and take a point x ∈ X. By proposition 3, it is straightforward to prove that the sets A of points in X that are connected to x by an arc and its complement, X = B \ A, are open. As X is connected and A ∅, B is empty and X is arc-connected. Finally to prove 3 ⇒ 1, suppose X is arc-connected. From Lemma 1, we derive easily that X is path-connected.

Observe that the above property means that the standard definition of paths and the digital one lead to the same path-connected components.

Homotopy

Let f, g be two continuous maps from a topological space Y to X. We write f g when f (a) g(a) for all a ∈ Y. It is straightforward that the relation is a partial order on C(Y, X), the set of continuous maps from Y to X. For some given ([36, 26, 2]), we do not use here the compact-open topology on continuous functions but the Alexandroff topology associated to the poset (C(Y, X), ).

x 1 , x 2 ∈ X, y 1 , y 2 ∈ Y, we set C(Y, X) ⋆ = { f ∈ C(Y, X) | f (y 1 ) = x 1 , f (y 2 ) = x 2 }. Unlike others authors
Property 5 ([36]) Let X be a poset and Y any topological space. Let p, p ′ ∈ C(Y, X) be such that p ′ p. Then, there is a homotopy h between p and p ′ such that for all y ∈ Y, p(y

) = p ′ (y) ⇒ ∀u ∈ [0, 1], h(y, u) = p(y) = p ′ (y). Proof Define h : Y × [0, 1] → X by h(y, t) = p(y) if t < 1 and h(y, 1)= =p ′ (y). Let U x be some smallest neighbourhood for some x ∈ X. Then, h -1 (U x ) = p -1 (U x ) × [0, 1[ ∪ p ′-1 (U x ) × {1}. Now, y ∈ p ′-1 (U x ) ⇒ p ′ (y) ∈ U x ⇒ p(y) ∈ U x (for p ′ p) ⇒ y ∈ p -1 (U x ). Thus, p ′-1 (U x ) ⊆ p -1 (U x ) and h -1 (U x ) = p -1 (U x ) × [0, 1[ ∪ p ′-1 (U x ) × [0, 1]. As p, p ′ are continuous, p -1 (U x ) and p ′-1 (U x ) are open and, therefore, h -1 (U x ) is open which establishes the continuity of h.
Corollary 1 Let X be a poset. If X has a maximum, or a minimum, then X is contractible. In particular, for any x ∈ X, x ↓ and x ↑ are contractible.

Proof Let x be the minimum of X and ϕ the constant map that takes X onto {x}. The function ϕ is non-decreasing and verifies ϕ id X . Hence, thanks to Property 5, we derive that {x} is a strong deformation retract of X.

The following corollary is a direct consequence of the Property 5 (taking Y = [0, 1]). It is of first importance for our study of paths in posets.

Corollary 2 Let X be a poset and a, b be two points in X. Let p, p ′ be two paths in X from a to b such that p ′ p. Then, p and p ′ are equivalent 3 . Property 6 Let X be a poset and Y a compact topological space. The connected components of C(Y, X) (resp. C(Y, X) ⋆ ), equipped with the binary relation , are the homotopy equivalence classes of C(Y, X) (resp. C(Y, X) ⋆ ).

Proof Suppose that f and g are in the same connected component of C(Y, X) (resp. C(Y, X) ⋆ ). From Properties 4 and 3 (applied to the poset C(Y, X) or C(Y, X) ⋆ ), there exists a sequence (q i ) r i=0 (r 1) of paths in C(Y, X) (C(Y, X) ⋆ ) such that q 0 = f , q r = g and, for all i ∈ [1, r], q i-1 , q i are comparable, and thus, thanks to Property 5, homotopy equivalent. Hence, f and g are homotopy equivalent (from Property 5, we easily derive that, if

f, g ∈ C(Y, X) ⋆ , there is a homotopy h such that for all t ∈ [0, 1], h(., t) ∈ C(Y, X) ⋆ ). Conversely, let h : Y ×[0, 1] → X be a homotopy between some maps f and g of C(Y, X) (with h(y i , t) = x i for all t ∈ [0, 1] and i ∈ {1, 2}). Define h ⋆ : [0, 1] → C(Y, X) by (h ⋆ (t)) (y) = h(y, t). It is clear that h ⋆ (0) = f and h ⋆ (1) = g (and h ⋆ (t) ∈ C(Y, X) ⋆ ).
We want to prove that h ⋆ is continuous and is therefore a path from f to g. Let t be a point in the preimage h

-1 ⋆ (U p ) of some smallest neighbourhood in C(Y, X). As h is continuous, for each y ∈ Y, there are open sets V y ⊆ Y, I y ⊆ [0, 1] such that y ∈ V y , t ∈ I y and h(V y × I y ) ⊆ U p(y) . Thanks to the compacity of Y, there is a finite subset A of Y such that {V y } y∈A is a finite cover of Y. Then I = y∈A I y is an open neighbourhood of t and for all t ′ ∈ I, y ∈ Y, h(y, t ′ ) ∈ h(V y , I) ⊆ h(V y , I y ) ⊆ U p(y) hence t ′ ∈ h -1 ⋆ (U p ) and I ⊆ h -1 ⋆ (U p ).
We can now conclude that h ⋆ is continuous and that f, g are in the same

(path-)connected component of C(Y, X) (C(Y, X) ⋆ ).
As a particular case of Property 6, we obtain that the connected components of Π a,b , the set of paths in X from a to b equipped with the binary relation , are the equivalence classes of Π a,b and from Property 4 we derive immediately the following corollary.

Corollary 3 Let X be a poset and a, b two points in X. Two paths p, p ′ in X from a to b are equivalent iff there exists a sequence (p i ) r i=0 (r 0) in Π a,b such that p 0 = p, p r = p ′ and, for all i ∈ [1, r], p i-1 and p i are comparable.

Paths and arcs

The aim of Section 3 is to understand precisely how paths behave in a poset and to study the link between their image and the arcs defined in Section 2.2.2. In the sequel of the article, (X, ) is a poset (X need not to be finite nor, even, locally finite).

Finite paths

We say that a function f : [0, 1] → X is a step function if there exists finitely many intervals

(I i ) r i=0 (r ∈ N) such that f is constant on each interval I i and [0, 1] = r i=0 I i . If for all i ∈ [1, r], sup(I i-1 ) = inf(I i ) and f (I i-1 ) f (I i ), we write f = r i=0 x i 1 Ii where {x i } = f (I i ).
Note that we use the notation f = r i=0 x i 1 Ii by analogy with mathematical analysis but it is purely formal and there is no meaning behind this summation.

As a path in X is a continuous map from [0, 1] to X and [0, 1] is compact, the image of a path p in a locally finite poset X is compact and therefore finite (Property 1). Nevertheless, this does not mean that p is a step function. For example, let x⊳y be faces in X and consider the map p : [0, 1] → {x, y} defined by p(0) = x, p = {x} for any positive integer r. The function p is a loop at x in X (continuity of p is obvious since ∅, {y}, {x, y} are the only open sets in {x, y}) but this path goes through x and y countably many times and it is even impossible to tell which is the second point crossed by the path p. Observe that this path is greater than the constant path p 0 : [0, 1] → {x} and less than p 1 : [0, 1] → X defined by p 1 (0) = x, p 0, 1 2 = {y}, p 1 2 , 1 = {x} and thus p is equivalent to p 0 and p 1 (Property 5).

Definition 1 (Finite path)

A path p in X is a finite path if it is a step function p = r i=0 x i 1 Ii . The sequence (I i ) r
i=0 is called the intervals sequence of p and the sequence (x i ) r i=0 the track of p. A finite path is regular if there is no singleton in its intervals sequence. A finite path is

minimal if for all x i , 1 i r -1, in the track of p, x i-1 < x i ⇔ x i > x i+1 .
Proposition 1 The track of a finite path is an arc, and any arc is the track of a regular finite path.

Proof Let p = r i=0 x i 1 Ii , (r 0), be a finite path. If r = 0, it is obvious that χ is an arc. If r 1, take i ∈ [1, r]. The set {x i-1 , x i } = p (I i-1 ∪ I i ) is connected since I i-1 ∪ I i is connected and p is continuous. Hence, χ is an arc. Let χ = (x i ) r i=0 (r 0) be an arc. If r = 0, the constant path p defined by p([0, 1]) = {x 0 } has track χ. If r = 1,
from Lemma 1 and its proof, there exists a regular path from x 0 to x 1 . If r 2, the product p 1 . . . p r of regular paths p i from x i-1 to x i (1 i r) is a path with track χ and it can easily be seen, from the very definition of this product, that a product of regular paths is regular.

Lemma 2 A step function p = r i=0 x i 1 Ii is a finite path in X iff for all i ∈ [0, r -1], x i ≍ x i+1 and x i x i+1 ⇔ sup (I i ) ∈ I i . Proof Suppose p is continuous. Let i ∈ [0, r -1]. By Proposition 1, x i ≍ x i+1 . If x i x i+1 , then x i U xi+1 (since x i
x i+1 by convention when writing p = r i=0 x i 1 Ii ). So the open set p -1 (U xi+1 ) includes the interval I i+1 but not the interval I i . Thus, inf(I i+1 ) = sup(I i ) is not in I i+1 , i.e., sup (I i ) ∈ I i . If the inequality x i x i+1 is false then x i+1 U xi and the open set p -1 (U xi ) includes the interval I i but not the interval I i+1 . So sup(I i ) is not in I i . Hence, the equivalence x i x i+1 ⇔ sup (I i ) ∈ I i holds. Conversely, suppose that there is some s 0 such that any step function r i=0 x i 1 Ii with r s is continuous when for all i ∈ [0, r -1],

x i ≍ x i+1 and x i x i+1 ⇔ sup (I i ) ∈ I i . Let p = s+1 i=0 x i 1 Ii be a step function such that for all i ∈ [0, s], x i ≍ x i+1 and x i x i+1 ⇔ sup (I i ) ∈ I i . Indeed, for all i ∈ [0, s -1], x i ≍ x i+1 and x i x i+1 ⇔ sup (I i ) ∈ I i so the step function p ′ = s-1 i=0 x i 1 Ii + x s 1 Is∪Is+1 is continuous. Let U be an open set in X. If x s , x s+1 U, or x s , x s+1 ∈ U, then p -1 (U) = p ′-1 (U) is open.
If x s ∈ U and x s+1 U then necessarily the inequality x s x s+1 is false which implies that sup (I s ) I s . Thus, I s+1 is closed and p -1 (U) = p ′-1 (U)\ I s+1 is open. If x s U and x s+1 ∈ U then, since x s and x s+1 are comparable, x s x s+1 and, by hypothesis, sup (I s ) ∈ I s . Thus, I s+1 is open and p -1 (U) = p ′-1 (U) ∪ I s+1 is open. As in each case the preimage of an open set is open, p is continuous. Observing that, if s = 0, the map p is constant and therefore, continuous, we may conclude by induction.

Theorem 2 is the main result of Section 3.1. It states that any path p in a poset is equivalent to a finite path, the track of which is "very close" to the image of p. Thus, it is a first link between the continuous notion of path and the discrete one of arc.

Theorem 2 For all x, y ∈ X and any path p from x to y, there exists a minimal regular finite path from x to y, p ′ p, the track of which is included in the image of p. Moreover, in any interval I in the interval sequence of p ′ , there is an element t such that p ′ (t) = p(t).

Proof Let p be a path from x to y in X.

For each t ∈ [0, 1], p -1 (U p(t)
) is open and contains t. Let J t be the connected component of p -1 (U p(t) ) containing t (J t is an open interval). Since [0, 1] is compact and the family (J t ) t ∈ [0, 1] is an open cover of [0, 1], there exists a finite subset A of [0, 1], such that (J t ) t ∈ A covers [0, 1]. If, for some t, t ′ ∈ A, J t ∩ J t ′ ∅ and p(t) p(t ′ ), we remove t ′ from A and we replace J t by J t ∪ J t ′ so we can suppose that J t ∩ J t ′ ∅ ⇒ p(t) p(t ′ ) (observe that it implies that t cannot belong to J t ′ ). Let A ′ be a subset of A such that A ′ is a minimal cover of [0, 1] (for any strict subset B of A ′ , (J t ) t ∈ B does not cover [0, 1]). Let (t i ) r i=0 be the (strictly) ordered sequence of reals in A ′ (where r is the cardinal of A ′ ). From the hypothesis on A ′ , we derive that the sequences (inf(J ti )) r i=0 and (sup(J ti )) r i=0 are strictly ordered, J ti-1 ∩ J ti ∅ for all i ∈ [1, r] and J ti-1 ∩ J ti+1 = ∅ for all i ∈ [1, r -1] . Finally, for each i = 1, . . . , r, we choose a real w i in J ti-1 ∩ J ti and we set w 0 = -∞, w r+1 = +∞, p(w 0 ) = x, p(w r+1 ) = y. Observe that for any i = 1, . . . , r, p(t i-1 )⊳p(w i ) and p(t i )⊳p(w i ). We set

J w0 = J 0 ∩ 0, t0 2 , J wr+1 = J 1 ∩ tr +1 2 , 1 and, for i ∈ [1, r], if J wi J ti-1 ∩ J ti , we set J wi to any open interval J such that w i ∈ J ⊂ J ⊂ J wi ∩ J ti-1 ∩ J ti . We define p ′ : [0, 1] → p ([0, 1]) by: p ′ (t) = p(w i ) if t ∈ J wi (0 i r + 1), p(t i ) if t ∈ sup(J wi ), inf(J wi+1 ) (0 i r),
Since sup(J wi ), inf(J wi+1 ) ⊂ J ti and for all (t, u) ∈ [0, 1]×J t , p(t) p(u), we have straightforwardly p ′ p. Furthermore, p ′ is a step function. We have stated above that p(t i-1 )⊳p(w i ) and p(t i )⊳p(w i ) for any i ∈ [1, r]. So, in order to prove the minimality of p ′ and, thanks to Lemma 2, its continuity, we still need to look at the extremities, that is, to compare p(w 0 ) with p(t 0 ) and p(t r ) with p(w r+1 ). If p(t 0 ) = x, then p ′ (t) = p(t 0 ) = x on [0, inf(J 1 )], otherwise 0 ∈ J t0 so p(t 0 )⊳p(w 0 ). Similarly, if p(t r ) = y, then p ′ (t) = p(t r ) = y on sup(J tr ), 1 , otherwise 1 ∈ J tr so p(t r )⊳p(w r+1 ). Now, we are able to conclude that p ′ is a minimal finite path from x to y. As for any i ∈ [1, r], J wi ⊂ J ti-1 ∩ J ti , we have ] v i-1 , u i ⊂ sup(J wi ), inf(J wi+1 ) and p ′ is regular. As w i ∈ J wi and t i ∈ sup(J wi ), inf(J wi+1 ) (for t i J ti-1 ∩ J ti and t i J ti ∩ J ti+1 ), in any interval I in the interval sequence of p ′ , there is an element t such that p ′ (t) = p(t).

There is no hope to find in the general case finite paths greater than a given path. For instance, consider the poset X = {x, y, z} where x y, x z. Let p : [0, 1] → X be the function defined by p(t) = x if t belongs to the Cantor set C (i.e., t has a ternary numeral with no "1"), p(t) = y if t C and the first "1" in a ternary numeral of t is in odd position (starting from point), p(t) = z if t C and the first "1" in a ternary numeral of t is in even position. The map p is continuous because p However any open set of [0, 1] containing 0, contains real numbers with ternary numerals the first "1" of which is in even, or odd, position. Thus, a finite path greater than p should have a value in 0 greater than y and z. Such a value does not exist in X. Moreover, observe that, for any integer n, we can find a subset of Z n isomorphic to X.

-1 ({y}) =] 1 3 , 2 3 [∪]
The two following technical results will be needed in the proof of Proposition 3 and Theorem 3.

Lemma 3 For all x, y ∈ X and any paths p 1 , p 2 , p 3 from x to y such that p 1 p 2 and p 3 p 2 , there are three finite paths from x to y, p ′

1 p 1 , p ′ 2 p 2 , p ′ 3 p 3 , such that p ′ 1 p ′ 2 and p ′ 3 p ′ 2 .
Proof The proof of Lemma 3 is close to the proof of Theorem 2. However we need to make some changes in the proof of the theorem. For all t ∈ [0, 1], we now define J t as an interval containing t and included in p -1

1 (U p1(t) ) ∩ p -1 2 (U p2(t) ) ∩ p -1 3 (U p3(t)
). The finite set A ′ is such that (J t ) t ∈ A ′ is a minimal cover of [0, 1] and the sequences (t i ) r i=0 , (w i ) r i=0 are defined as in the proof of Theorem 2. Observe that it is no longer possible to assume that t i-1 , t i J ti-1 ∩ J ti and therefore, it may happen that p(t i-1 ) = p(w i ) or p(t i ) = p(w i ). The maps p ′ k , k ∈ {1, 2, 3}, are defined by:

p ′ k (t) = p k (w i ) if t ∈ J wi (0 i r + 1), p k (t i ) if t ∈ sup(J wi ), inf(J wi+1 ) (0 i r).
Of course, we still have p ′ k p k for each k ∈ {1, 2, 3} and the proof of continuity for the three maps need not to be changed (except that we replace p(t i-1 )⊳p(w i ) and p(t i )⊳p(w i ) by p(t i-1 ) p(w i ) and p(t i ) p(w i )). Proof Let p be a non-regular finite path. Let u ∈ [0, 1] such that {u} is an interval of the intervals sequence of p and I, J be the intervals before and after {u} in this sequence (if u = 0 or u = 1, we set I = ∅ or J = ∅). We denote by x the point in X such that p(u) = x. Since p is continuous, there is a real ε > 0 such that p (]uε, u + ε[) ⊆ U x and we can choose

Lemma 4 -Let p be a finite

ε such that ]u -ε, u[∩[0, 1] ⊆ I, ]u, u + ε[∩[0, 1]) ⊆ J. Set p ε x : [0, 1] → X, the function defined by p ε x (t) = x if t ∈ [u -ε 2 , u + ε 2 ]
and p ε x (t) = p(t) otherwise. Clearly, we have p ε x p and, from Lemma 2, we derive that p ε

x is a finite path (since p is itself a finite path) which has the same track as p. This way, we can remove all singletons from the intervals sequence of p, resulting in a regular path p ′ p with same track than p.

Let p 1 p 2 be two finite paths. Thanks to the first part of the proof, we know there is a regular path p ′ 1 p 1 p 2 . We slightly modify the above construction of p ′ in order to get p ′ 1 p ′ 2 . Let u ∈ [0, 1] such that {u} is an interval of the intervals sequence of p 2 and I 2 , J 2 be the intervals before and after {u} in this sequence (if u = 0, or u = 1, we set

I 2 = ∅ or J 2 = ∅). Set x = p(u). Take ε > 0 such that p (]u -ε, u + ε[) ⊆ U x , ]u -ε, u[∩[0, 1] ⊆ I, ]u, u + ε[∩[0, 1]) ⊆ J and either ]u -ε, u] or [u, u + ε[ is included in an interval of the intervals sequence of p ′
1 (such a choice is possible since p ′ 1 is regular). Suppose, for example, that [u, u + ε[ is included in an interval of the intervals sequence of p ′ 1 (the other case is similar) and, therefore, u 1, J ∅, and there is a point y x (since

p ′ 1 p 2 ) in X such as p ′ 1 ([u, u + ε[) = {y}. Set p ε x : [0, 1] → X, the function defined by p ε x (t) = x if t ∈ [u, u + ε 2 ] and p ε x (t) = p 2 (t) otherwise.
As above, we have p ′ 2 continuous and p ′ 2 p 2 .

Moreover, we have also p ′ 1 p ′ 2 . Doing successively this construction for all singletons in the intervals sequence of p 2 , we obtain a regular path p ′ 2 with same track as p 2 and such that p ′ 1 p ′ 2 p 2 .

Arcs

Theorem 2 means that every path in a poset is homotopic to a finite path, the image of which is an arc. Processing digital images, one usually either just look at images of paths, that is at arcs, and ignore functional definition or link arcs with paths in continuous analogs. In this subsection we focus our attention on relations between arcs and paths in the poset itself.

We can think at a track (of a finite path) as a map from the set of finite paths onto arcs (Proposition 1). Obviously this map is not injective. The next proposition gives some light upon this point.

Proposition 2 Two finite paths in X with same track are equivalent.

Proof Let p = r i=0 x i 1 Ii and p ′ = r i=0 x i 1 Ji be two paths in X with same track (r is a non negative integer). For each i = 0 . . . , r, we denote α i , β i (α ′ i , β ′ i ) the lower and upper bound of I i (J i ). Thanks to Lemma 2, we know that, for each i = 0, . . . , r, intervals I i and J i have the same form:

α i ∈ I i ⇔ α ′ i ∈ J i and β i ∈ I i ⇔ β ′ i ∈ J i .
For all u ∈ [0, 1], we denote K i,u the interval with the same form as I i , J i and the bounds of which are (1u)α i + uα ′ i and (1u)β i + uβ ′ i . It follows again from Lemma 2 that the step function p u = r i=0 x i 1 Ki,u is a finite path. Let h : [0, 1] × [0, 1] → X be the function defined by h(t, u) = p u (t). We have h(t, 0) = p(t) and h(t, 1) = p ′ (t) for all t ∈ [0, 1]. It can be seen that for any open set U, h -1 (U) is an union of open trapezoid in [0, 1] × [0, 1], the bases of which are p -1 (U) × {0} and p ′-1 (U) × {1}. Hence, h is continuous: p and p ′ are equivalent. Now a new question arises: it is not difficult to see that the converse of the previous proposition is false (i.e. unless X is a singleton, there are in X equivalent finite paths which have distinct tracks), but when two finite paths are homotopic, what about their tracks? To go further, we need to introduce an elementary modification on arcs (see also [START_REF] Cointepas | Modélisation homotopique et segmentation tridemensionnelle du cortex cérébral à partir d'IRM pour la résolution des problèmes directs et inverses en EEG et en MEG[END_REF][START_REF] Kong | The Khalimsky topologies are precisely those simply connected topologies on Z n whose connected sets include all 2n-connected sets but no (3 n -1)-disconnected sets[END_REF]).

Definition 2 (Stretching)

An arc χ = (x i ) r i=0 (r 2) is an elementary stretching of an arc χ ′ if for some j ∈ [1, r -1], χ ′ = (x i ) r i=0,i j or x j-1 = x j+1 and χ ′ = (x i ) r i=0,i j-1,i j . An arc χ is a deformation of an arc χ ′ if there is a sequence (χ i ) s i=0 of arcs in X such that χ 0 = χ, χ s = χ ′ and for any i ∈ [1, s], either χ i is an elementary stretching of χ i-1 or χ i-1 is an elementary stretching of χ i .

We will also call elementary stretching the transformation between an arc and an elementary stretching of this arc. Observe that if χ = (x i ) r i=0 is an elementary stretching of χ ′ = (x i ) r i=0,i j , necessarily the three points x j-1 , x j , x j+1 are mutually comparable. Barmak and Minian in [START_REF] Barmak | Minimal finite models[END_REF] use a similar notion which leads to the same deformations: an arc

χ = (x i ) r i=0 (r 2) is close to an arc χ ′ if for some j k j ′ in [1, r -1], χ ′ = (x i ) r i=0,i [ j, j ′ ] and x j ⊳ . . . ⊳x k ⊲ . . . ⊲x j ′ or x j ⊲ . . . ⊲x k ⊳ . . . ⊳x j ′ .
Proposition 3 Let p, p ′ be two finite paths with tracks χ, χ ′ . If χ ′ is a deformation of χ, then p and p ′ are equivalent. Proof Let p and p ′ be two finite paths in X with tracks χ, χ ′ . Since a deformation is a sequence of elementary stretchings and homotopy is an equivalence relation, it is sufficient to prove the result for an elementary stretching. So we assume that χ ′ is an elementary stretching of χ and, thanks to Lemma 4, we can also assume that p and p ′ are regular. We set p = r i=0,i j x i 1 Ii or r i=0,i j-1,i j x i 1 Ii and p ′ = r i=0 x i 1 Ji (2 r and 1 j r -1). If x j-1 ⊳x j ⊳x j+1 or x j+1 ⊳x j ⊳x j-1 , we set p 1 (t) = p(t) if t ∈ i j J i and p 1 (J j ) = {x j-1 }. Otherwise (x j ⊳x j-1 and x j ⊳x j+1 , or x j-1 ⊳x j and x j+1 ⊳x j ), let α and β be the lower bound and the upper bound of J j (α β since p ′ is regular) and γ = α+β 2 . We set 2). In any case, we can derive from Lemma 2 that p 1 is a path. Since the tracks of p 1 and p are the same, p 1 and p are equivalent. Moreover, it can easily be seen that p 1 p ′ or p ′ p 1 . Thus p 1 and p ′ are equivalent and, by transitivity, p and p ′ are equivalent.

p 1 (t) = p(t) if t ∈ i j J i , p 1 (t) = x j-1 if t ∈ [α, γ[, p 1 (t) = x j+1 if t ∈]γ, β] and p 1 (γ) = x j-1 if x j-1 ⊳x j+1 , p 1 (γ) = x j+1 if x j+1 ⊳x j-1 (see Figure
p ′ ¢ ≤ α γ β x j+1 x j x j-1 p 1 ¢ ≤ α γ β x j+1
x j

x j-1 (a)

p ′ ¢ ≤ α γ β x j x j+1 x j-1 p 1 ¢ ≤ α γ β x j x j+1 x j-1 (b)
Fig. 2 (a) Case x j+1 ⊳x j ⊳x j-1 (case x j-1 ⊳x j ⊳x j+1 is similar). (b) Case x j ⊳x j-1 , x j ⊳x j+1 (case x j-1 ⊳x j , x j+1 ⊳x j is similar with an open interval J j ). Note that in this case, it could happen that x i-1 = x i+1 .

We can now state that the notion of deformation is the discrete counterpart of the continuous notion of homotopy equivalence.

Theorem 3 Two finite paths p, p ′ in X with tracks χ χ ′ are equivalent iff χ is a deformation of χ ′ . Proof Let p and p ′ be two distinct finite equivalent paths in X from point a to point b and Π a,b be the poset of paths in X from a to b. Since p and p ′ are equivalent, there is a path from p to p ′ in Π a,b (Proposition 6) and, thus, there is an arc in Π a,b from p to p ′ (Property 4). Of course we can suppose that this arc is minimal (otherwise we delete the superfluous paths). Moreover, we claim that we can build a minimal arc in Π a,b from p to p ′ , the elements of which are all finite. Suppose that P = (p i ) r i=0 (r 2) is a minimal arc in Π a,b from p to p ′ , the k first elements of which are finite (1 k r -1). Case 1: p k p k-1 . Since P is minimal, we have p k p k+1 . We derive from Theorem 2 that there is a finite path q in Π a,b such that q p k . Thus, the sequence P ′ = (q i ) r i=0 where q k = q and q i = p i otherwise, is a minimal arc in Π a,b from p to p ′ , the k + 1 first elements of which are all finite. Case 2: p k-1 p k , and thus p k+1 p k . Thanks to Corollary 3, we know there exist three finite paths q, q ′ , q ′′ such that q p k-1 , q ′ p k , q ′′ p k+1 and q q ′ , q ′′ q ′ . If p k+1 p ′ we set P ′ = (q i ) r i=0 where q k-1 = q, q k = q ′ , q k+1 = q ′′ and q i = p i otherwise. Then, P ′ is a minimal arc in Π a,b from p to p ′ , the k + 2 first elements of which are finite. If p k+1 = p ′ we set P ′ = (q i ) r+1 i=0 where q i = p i if i k -2, q k-1 = q, q k = q ′ , q k+1 = q ′′ and q r+1 = p ′ . Then, P ′ is a minimal arc in Π a,b from p to p ′ , the elements of which are all finite. This way, we build iteratively an arc in Π a,b from p to p ′ , the elements of which are all finite.

Therefore, to prove that the tracks of p is a deformation of the track of p ′ it is sufficient to do so for two finite and comparable paths, say p 1 and p ′ 1 . Moreover, thanks to Lemma 4 and Lemma 2, we can easily build two comparable regular (finite) paths from a to b, q = r i=0 x i 1 Ii q ′ = s j=0 y j 1 J j , with same tracks as p 1 and p ′ 1 and such that the intervals I i (0 i r) have no common bounds with the intervals J j (0 j s). Thus, we denote (α i ) r+s+1 i=0 the strictly increasing sequence the elements of which are the bounds of the intervals I i and J j : α 0 = 0, α r+s+1 = 1, for each 1 i r + s either q or q ′ , but not both, change its value on α i and no others changes occur. For each i ∈ [0, r + s + 1] and each j ∈ [0, r + s] we define the step functions q i and q ′ j by q i (t) = q ′ (t) if t < α i , q(t) otherwise and q

′ j (t) = q ′ (t) if t < α j +α j+1 2
, q(t) otherwise. In particular, q 0 = q and q r+s+1 = q ′ (since q ′ (1) = q(1)). We denote by χ i and χ ′ j the tracks of q i and q ′ j (i

∈ [0, r + s + 1], j ∈ [0, r + s]).
From Lemma 2, we easily derive that the step functions q i and q ′ j are finite paths from a to b. We want now to prove that, for all i ∈ [0, r + s], either χ k (χ k+1 ) is equal to χ ′ k or is a stretching of χ ′ k or the converse. The proof consists in checking the 2 × 4 configurations relative to q k and q ′ k and to q ′ k and q k+1 . These 8 configurations are depicted in Figures 3 and4 which clearly establish that in any case we have equality or stretching. Note that in the Figures 3 and4 we denote by f (t -) and f (t + ) the values taken by a finite path f on some intervals ]tε, t[, ]t, t + ε[ where ε > 0 is small enough to assume that f is constant on these intervals.

The converse part of the proof is given by Proposition 3.

To go further in the parallelism between paths and arcs, homotopies and deformations, we will now study the arc product defined by (x 0 , . . . , x r ).(y 0 , . . . , y s ) = (x 0 , . . . , x r , y 1 , . . . , y s ). More formally:

Definition 3 (Arcs product) Let χ 1 = (x i ) r
i=0 and χ 2 = (y i ) s i=0 (r, s 0) be two arcs such that x r = y 0 . The arc product is defined by χ 1 .χ 2 = (z i ) r+s i=0 where

z i = x i if i r and z i = y i-r if i r.
Let x be a point in X. It is easy to check that being a deformation or equal is an equivalence relation in the set of arcs in X from x to x. We write [χ] for the equivalence class of an

q k ¢ ≤ α k α k +α k+1 2 p(α - k ) p(α + k ) p ′ (α k ) q ′ k ¢ ≤ α k α k +α k+1 2 p(α - k ) p(α + k ) p ′ (α k ) (a) q k ¢ ≤ α k α k +α k+1 2 p(α + k ) p(α - k ) p ′ (α k ) q ′ k ¢ α k α k +α k+1 2 p(α - k ) p(α + k ) p ′ (α k ) (b) q k ¢ ≤ α k α k +α k+1 2 p(α k ) p ′ (α - k ) p ′ (α + k ) q ′ k ¢ ≤ α k α k +α k+1 2 p(α k ) p ′ (α - k ) p ′ (α + k ) (c) q k ¢ ≤ α k α k +α k+1 2 p(α k ) p ′ (α + k ) p ′ (α - k ) q ′ k ¢ ≤ α k α k +α k+1 2 p(α k ) p ′ (α + k ) p ′ (α - k ) (d) Fig. 3 (a) q k is a stretching of q ′ k (depending on p(α + k ) = p ′ (α k )
or not, we use one of the two cases in the definition of elementary stretchings). (b)

q k = q ′ k . (c) q ′ k is a stretching of q k . (d) If p ′ (α + k ) p(α k ), q ′ k is a stretching of q k , otherwise q k = q ′ k .
arc χ and we denote by ρ(X, x) the set of equivalence classes. It is not more difficult to verify that the arc product is well defined on classes by [

χ 1 ].[χ 2 ] = [χ 1 .χ 2 ]
and ρ(X, x) equipped with the arc product is a group (the identity element of which is [(x)] and the inverse of

[(x i ) r i=0 ] is [(x i ) i=r 0]
). Theorem 4 Let x ∈ X. The fundamental group π 1 (X, x) of X with basepoint x is isomorphic to the group ρ(X, x).

Proof By Theorem 2 we know that there are finite paths in any class of π 1 (X, x) and by Theorem 3, we may define a map ϕ : π 1 (X, x) → ρ(X, x) by ϕ([p]) = [χ] where χ is the track of any finite path equivalent to p. From Proposition 3, we derive that ϕ is injective and from Proposition 1, ϕ is surjective. Finally, ϕ is a morphism since we can easily see that the track of a product of two finite paths is the product of the tracks of these finite paths.

Remark 1 Barmak and Minian in [START_REF] Barmak | Minimal finite models[END_REF] have proved the same result in a different way and in the frame of finite spaces. They establish an isomorphism between ρ(X, x) and a group of loops composed with edges of the simplicial complex K(X) associated to X (see section 4.1), then invoke an isomorphism between the edge-paths group of K(X) and the fundamental group of its geometric realization |K(X)| (see section 4.1) described by Spanier [START_REF] Spanier | Algebraic Topology[END_REF] and conclude thanks to the weak homotopy equivalence between |K(X)| and X established by McCord (see section 4.1).

q ′ k ¢ ≤ α k+1 α k +α k+1 2 p(α - k+1 ) p(α + k+1 ) p ′ (α k ) q k+1 ¢ ≤ α k+1 α k +α k+1 2 p(α - k+1 ) p(α + k+1 ) p ′ (α k ) (a) q ′ k ¢ ≤ α k+1 α k +α k+1 2 p(α + k+1 ) p(α - k+1 ) p ′ (α k ) q k+1 ¢ ≤ α k+1 α k +α k+1 2 p(α + k+1 ) p(α - k+1 ) p ′ (α k ) (b) q ′ k ¢ ≤ α k+1 α k +α k+1 2 p(α k+1 ) p ′ (α - k+1 ) p ′ (α + k+1 ) q k+1 ¢ ≤ α k+1 α k +α k+1 2 p(α k+1 ) p ′ (α - k+1 ) p ′ (α + k ) (c) q ′ k ¢ ≤ α k+1 α k +α k+1 2 p(α k+1 ) p ′ (α + k+1 ) p ′ (α - k+1 ) q k+1 ¢ ≤ α k+1 α k +α k+1 2 p(α k+1 ) p ′ (α + k+1 ) p ′ (α k+1 ) - (d) Fig. 4 (a) q ′ k = q k+1 . (b) If p ′ (α k ) p(α - k+1 ), q ′ k is a stretching of q k+1 , otherwise q ′ k = q k+1 . (c), (d) q ′ k = q k+1 .

Reduction

In this section, we are interested in retractions, or more general decreasing transformations, that minimally alter the topology of a poset and the topology of a continuous analogue. In particular, we will visit minimal modifications of such sets that do not change homotopy type. But before thinking at transformations, we present in section 4.1 the way we embed a digital image in a poset and how the continuous analogue of the digital image is defined.

Complexes

Complexes are topological sets whose combinatorial organisation provide a way to link digital images, namely subspaces of Z n , with the continuous Euclidean space R n .

Simplicial complexes

Simplicial complexes are among the simplest combinatorial structures. They are commonly used in the field of geometric modelling.

An abstract simplicial complex is a set K of non-empty subsets, called simplices, of a set V, such that each non-empty subset of a simplex is a simplex. The elements of V are called vertices. Each vertex must belong to at least one simplex. A non-empty (proper) subset of a simplex is a (proper) face of the given simplex. For in this section we focus on digital images, we assume that the simplices of a complex are finite and that their cardinalities are bounded. Thus, we can define the dimension of a simplex which is its number of vertices minus one and the dimension of a complex which is the maximum of the dimensions of its simplices.

In R n , a set of points are geometrically independent if any k-hyperplane (k n) contains no more than k + 1 of them. The (geometric) simplex spanned by a set of geometrically independent points is the convex hull of these points which are the vertices of the geometric simplex. A k-face of a simplex is a simplex spanned by k vertices of the simplex. A (geometric) simplicial complex K is a set of simplices in R n such that any face of a simplex in K is a simplex in K and any intersection of two simplices in K is a simplex in K. The faces of the complex are the faces of its simplices. The vertices of the complex are the vertices of its simplices. Note that the vertices of a complex need not be geometrically independent. The geometric realization |K| of the complex K is the union of its simplices equipped with the topology the closed sets of which are the sets that intersect each simplex in a closed set of R n . Because a union of closed sets is not always a closed set, this topology could be different from the usual topology on R n . But here, as K is locally finite, i.e. any vertex belongs to finitely many simplices, this topology is the usual topology on R n . The open simplices of |K| are the interiors of its k-faces (k 1) and its 0-faces. Each point x in |K| belongs to a unique open simplex spanned by some vertices v 1 , . . . , v k (k 1) and there exists a unique k-uple

(b 1 , . . . , b k ) in [0, 1] k such that x = k i=0 b i v i .
Let f be a function between the set of vertices of two complexes K and K ′ , the function

|K( f )| which associates to each point x = k i=0 b i v i in |K| the point y of |K ′ | defined by y = k i=0 b i f (v i )
is the simplicial map associated to f . This map is continuous.

A realization of an abstract simplicial complex K is a geometric simplicial complex whose vertices are in one to one correspondence with the vertices of K and whose simplices are spanned by the images of the simplices of K. Any abstract simplicial complex K of dimension n can be realized in R 2n+1 [START_REF] Hilton | Homology Theory[END_REF].

There is a narrow link between posets and simplicial complexes discovered by Alexandroff [START_REF] Alexandroff | Diskrete Räume[END_REF]. Let X be a poset. The points in X are the vertices of a simplicial complex K(X) the simplices of which are the (finite) chains of X (see figure 6). Conversely, it is plain that the simplices of a given simplicial complex K, equipped with the inclusion relation, is a locally finite poset denoted X(K). Note that K(X(K)) is not equal to K but to a simplicial complex called the barycentric subdivision of the complex K. These correspondences are not only algebraic and the topologies on the poset and the geometric realization of the complex are concerned as well. The following theorem due to McCord gives the key-properties of the map ϕ X : |K(X)| → X which associates to each point in the geometric realization of K(X), the highest element of the unique open simplex it belongs to (remember that a simplex of K(X) is a chain).

Theorem 5 (McCord [29]

) Let X be a poset. There is a weak homotopy equivalence ϕ X : |K(X)| → X. Furthermore, one can associate to each continuous map f : X → Y between two posets the simplicial map |K( f )| such that the following diagram is commutative:

X Y |K(X)| |K(Y)| f |K( f )| ϕX ϕY
Observe that, as we have proved that the fundamental group π 1 (X, x) of a poset X with basepoint x is isomorphic to the group ρ(X, x) of its arcs from x to x (for any x ∈ X), Theorem 5 gives by transitivity an isomorphism between ρ(X, x) and the fundamental group of the geometric realization of K(X).

Cubical complexes

In digital images, grids are often cubical ones, so it is interesting in image analysis to replace simplices in complexes by n-cubes.

We set F1 0 = {{a} | a ∈ Z} and F1 1 = {{a, a + 1} | a ∈ Z}. A subset f of Z n which is the Cartesian product of m elements of F1 1 and nm elements of F1 0 is a face or an m-face (of Z n ), m is the dimension of f , and we write dim( f ) = m. We denote by F n m the set composed of all m-faces of Z n and by F n the set composed of all faces of Z n . Let f ∈ F n be a face. The set {g ∈ F n | g ⊆ f } is a cell and any union of cells is an abstract cubical complex. The geometric cubical complexes are defined in the same manner, except we change the definition of F1 1 by setting

F1 1 = {[a, a + 1] | a ∈ Z}.
The geometric realization |K| of a geometric cubical complex K is the union of its faces (see figure 5). The points in a digital image are often a measure of a physical quantity on a piece of the Euclidean space. Then, the abstract cellular complex framework -and in particular the cubical complexes -enable to model the adjacency relations between these pieces of the Euclidean space in a topologically sound manner. Furthermore, as an abstract cellular complex (equipped with the inclusion) is a poset, Theorem 5 ensures that this complex is weakly homotopy equivalent to its geometric realization (more precisely, to the geometric realization of the associated simplicial complex -see figure 6 -) which is a conceivable representation of the tessellation of the Euclidean space captured by the measure device. We say that this geometric realization is the continuous analogue of the digital image. The second part of Theorem 5 says that any continuous transformations of the complex image has an equivalent on the continuous analogue compatible with the weak homotopy equivalence.

Collapses

Whitehead has defined elementary transformations on complexes as follows. Let X be a complex and (x, y) a pair of faces in X such that x is the only face of X including y. Then, (x, y) is a free pair, and the set Y = X \ {x, y} is an elementary collapse of X, or X is an elementary expansion of Y. If a set Y is obtained from X by a sequence of elementary collapses (a sequence of elementary collapses and expansions), then Y is a collapse of X (X and Y are simple-homotopy equivalent) and one write X ց Y (X ցY). A set is collapsible if it collapses onto a singleton.

If Y is a collapse of X then |Y| is a strong deformation retract of |X| (and thus, |X| and |Y| are homotopy equivalent) [START_REF] Whitehead | Simplicial spaces, nuclei and m-groups[END_REF]. Figure 7 illustrates this property.

Unipolar points

In the 60's, Stong [START_REF] Stong | Finite topological spaces[END_REF] introduced the notion of (co)linear points in order to classify finite spaces with respect to homotopy type. More recently, May [START_REF] May | Finite topological spaces[END_REF] called them beat points and Bertrand [START_REF] Bertrand | New notions for discrete topology[END_REF] unipolar points. We keep this last designation. In the same article, and for the same goal, Stong also defined the core of a finite space (see Definition 5) which is the smallest subset of X homotopic to X. Most results in this subsection were first established in Stong's article for finite spaces. Most of his proofs can be easily adapted to posets so we do not recall them.

Definition 4 (Unipolar point) Let X be a poset.

-A point x ∈ X is down unipolar if there is y⊳x such that z⊳x implies z y (i.e. x ↓⋆ = y ↓ ).

-A point x ∈ X is up unipolar if it is down unipolar for the dual order on X.

-A point is unipolar if it is either down unipolar or up unipolar.

Proposition 4 Let X be a poset. A point x ∈ X is unipolar iff X \ {x} is a strong deformation retract of X.

Proof The "only if" part of this proof is in [START_REF] Stong | Finite topological spaces[END_REF]. The "if" part is original and rely on our Theorem 2.

Let us assume that Y = X \ {x} is a strong deformation retract of X. Thus, there is an homotopy h : X × [0, 1] → X such that h(z, t) = z for all (z, t) ∈ Y × [0, 1] and h(x, 0) = x, h(x, 1)

x. The map h(x, .) : [0, 1] → X is a path in X from x to h(x, 1) so, following Theorem 2, we denote p = r i=0 x i 1 Ii (r 1), with p h(x, .), a regular finite path from x to h(x, 1) with property that in any interval I of the interval sequence of p, there is an element t such that p(t) = h(x, t). Let t 1 ∈ I 1 verifying p(t 1 ) = h(x, t 1 ) = x 1 which is an element of Y comparable to x (Proposition 1). The map h(., t 1 ) : X → X is continuous and, therefore, non-decreasing (Property 2) so for any y ∈ Y, y⊳x ⇒ y x 1 and x⊳y ⇒ x 1 y (since h(., t 1 ) is the identity map on Y). As x 1 is comparable to x, we derive that x is unipolar. Definition 5 (Core) Let Y ⊆ X. We say that Y is a core of X if it has no unipolar point and it is a strong deformation retract of X. Property 7 1. Any finite poset has a core. 2. Two finite posets are homotopy equivalent iff they have homeomorphic cores.

Observe in particular that Property 7 implies that one can greedily remove the unipolar points of a finite poset in order to obtain a core which will be homeomorphic to any other core of the same poset. In particular, when the poset is contractible, we have the corollary below.

Corollary 4 If X is finite and contractible, there is a sequence (x i ) r i=0 (r 0) of points in X such that X = {x j } r j=0 and, for all i ∈ [1, r], x i is unipolar in {x j } i j=0 . Furthermore, if x ∈ X is unipolar, we can choose x r = x.

Proof The fact that X is contractible means that X is homotopy equivalent to a point. Since X is finite, X has a core and any core of X is a singleton (Property 7). It is not difficult to see that it implies that one can greedily construct a sequence (x i ) r i=0 (r 0) of points in X such that X = {x j } r j=0 and, for all i ∈ [1, r], x i is unipolar in {x j } i j=0 .

Bertrand [START_REF] Bertrand | New notions for discrete topology[END_REF] has established that down (or up) unipolar points can be deleted in parallel, that is, if x y are down unipolar points in X then y is down unipolar in X \ {x}. It is no longer true for unipolar points (forgetting "down") as shown by the example of Figure 8. Nevertheless, we can state the next proposition.

Proposition 5 If x y are unipolar points then either (a) y is unipolar in X \ {x} or (b), for one order on X ( or ), x is down-unipolar and covers y, for the other order y is downunipolar and covers x and the map ϕ : X \ {x} → X \ {y} defined by ϕ(z) = z if z y and ϕ(y) = x is an homeomorphism. Proof Let x y be unipolar points in X. If x and y are not comparable, it is easy to see that y is unipolar in X \ {x} since Definition 4 only involves comparable points. If x and y are comparable, we can set x⊳y. If y is up-unipolar, y is unipolar in X \ {x} since definition 4 applied to y only involves points z such that y⊳z. We suppose now that y is down unipolar and we denote z the maximum of y ↓⋆ . Hence, for any t ∈ X, t⊳y ⇔ t z (1). If x z, obviously this inference is true for any t ∈ X \ {x} and y is unipolar in X \ {x}. If x = z and x is down unipolar, we use the result established in [START_REF] Bertrand | New notions for discrete topology[END_REF]. If x = z and x is up unipolar, necessarily y is the minimum of x ↑⋆ : for any t ∈ X, x⊳t ⇔ y t (2). We define ϕ : X \ {x} → X \ {y} by ϕ(t) = t if t y and ϕ(y) = x. Trivially, ϕ is a bijection and from (1) and (2) we derive that ϕ and ϕ -1 are non-decreasing, that is, continuous.

Simple points

Simple points were first introduced by Bertrand in [START_REF] Bertrand | New notions for discrete topology[END_REF] in order to perform topologically sound thinning algorithms in posets. They have been used by Barmak and Minian [START_REF] Barmak | Simple homotopy types and finite spaces[END_REF] to define a collapse operation in posets which corresponds actually to the collapse operation in complexes associated to posets. The proofs of Property 8 and Theorem 6, which are out of scope of this paper, can be found in [START_REF] Barmak | Simple homotopy types and finite spaces[END_REF].

Definition 6 (Simple point)

A point x ∈ X is down simple (in X) if x ↓⋆ is contractible. A point x ∈ X is up simple (in X) if x ↑⋆ is contractible.
A point is simple (in X) if it is either down simple or up simple.

Observe that unipolar points are simple points since if x ∈ X is a down (up) unipolar point, x ↓⋆ (x ↑⋆ ) has a maximum (minimum) and is therefore contractible (Property 1). We saw previously (Proposition 4) that the removal of a unipolar point is a strong deformation retraction. It is no longer true for simple points. See Figure 9 for a counterexample where the removal of a simple point is not even a retraction. Nevertheless, Property 8 states that homotopy groups are not changed by such a deletion and, furthermore, Theorem 6 ensure that this deletion corresponds to a deformation retract on the continuous analogue.

Property 8 [START_REF] Barmak | Simple homotopy types and finite spaces[END_REF] Let X be a finite poset. Let x ∈ X be a simple point. Then, the inclusion i : X \ {x} → X is a weak homotopy equivalence. [START_REF] Barmak | Simple homotopy types and finite spaces[END_REF]) Let X be a finite poset. Let x ∈ X be a simple point and K(X), K(X \ {x}) the simplicial complexes associated to X and X \ {x}. Then, K(X) ց K(X \ {x}). Fig. 9 X is the subset of F2 depicted in (a) and x is the 2-face in X (note that X = x ↓ ). The face x is simple since x ↓⋆ , depicted in (b), is clearly contractible. But X \ {x} = x ↓⋆ is not a retraction of X, for a retraction, as any continuous function, preserves connectivity and it is impossible to find an image for x in x ↓⋆ , while leaving unchanged the other points in X, without disconnecting some connected subset of X.

Theorem 6 (Barmak and Minian

From an algorithmic point of view, simple points have good properties since they can be deleted in parallel. Obviously, if x, y are two points in X with dim(x) = dim(y), there is no need to know wether x has been deleted from X or not to decide if y ↓⋆ , or x ↑⋆ is contractible. Moreover, as we have seen above, the decision on the contractibility can be greedily performed. Thus, a topology-preserving thinning procedure consists of repeating until stability the removal of the k-dimensional simple points for k = 0 to n. Figure 10 gives an example of the result of such a procedure when applied to a 2D-picture. A detailed study of algorithms quite similar to the previous scheme can be found in [START_REF] Lohou | Contribution à l'analyse topologique des images : étude d'algorithmes de squelettisation pour images 2D et 3D selon une approche topologie digitale ou topologie discrète[END_REF].

Free pairs and unipolar/simple points

In this subsection, we suppose X ⊆ F n . In order to perform thinning on X, it is usual to do collapses when X is a complex but, viewing X as a poset, it is possible to remove unipolar or simple points. So we want to compare these three ways to reduce a subset of F n .

Lemma 5 Let 0 k m n and x ∈ F n m . Let y ∈ x ↓ be a k-face. 1. There exist exactly mk faces in x ↓ of dimension (k + 1) which include y. 2. Let x 1 , x 2 be two (m -1)-faces in x ↓ such that x = x 1 ∪ x 2 and y intersects both x 1 and x 2 . If k 0, there exists in y ↓ exactly one (k -1)-face which are included in x 1 and one (k -1)-face which are included in x 2 .

Proof If k = m, Lemma 5 is trivial. Suppose now that m > k. Without loss of generality, we can assume that x = n i=1 I i where I i ∈ F 1 1 if i m, I i ∈ F 0 1 otherwise (see Section 4.1.2) and y = n i=1 J i where ∅ ⊂ J i ⊂ I i if i mk and J i = I i otherwise. 1. It is plain that the only (k + 1)-faces included in x and including y are the mk faces z j , 1 j mk defined by z j = n i=1 K i with K i = J i if i j and K j = I j . 2. Since y intersects both x 1 and x 2 , there exists j ∈

[m -k + 1, m] such that x 1 = n i=1 K1 i and x 2 = n i=1 K2 i with K i 1 = K i 2 = I i if i j, ∅ ⊂ K j 1 ⊂ I j and K j 2 = I j \ K j 1. Therefore, the only (k -1)-face z included in y and in x 1 (resp. x 2 ) is z = n i=1 L i with L i = J i if i j and L j = K i 1 (resp. L j = K i 2).
An easy consequence of Lemma 5, is that the boundary x ↓⋆ of a cell x ↓ in F n is not contractible since for any k-face y in x ↓⋆ , there exist at least two (k + 1)-faces including y, except if y is maximal in x ↓⋆ , and two (k -1)-faces included in y, except if y is minimal in x ↓⋆ , and therefore x ↓⋆ has no unipolar point. So, x ↓⋆ is not contractible (Corollary 4).

Corollary 5

The boundary x ↓⋆ of a cell x ↓ in F n is not contractible. Lemma 6 Let x, y ∈ X, x y, be two faces with dim(x) = dim(y) -1. Then, y ↓⋆ \ {x} is contractible.

Proof We set m = dim(y) and Y = y ↓⋆ \ {x}. If m = 1, lemma 6 is trivial (Y is a singleton). Suppose now that m 2. We denote x ′ the face opposite to x in y ↓ : x ′ = y \ x. We will shrink Y to {x ′ }, removing unipolar points from Y. First, we remove the faces in x ↓⋆ in decreasing order relatively to their dimension. For any (m -2)-face z in x ↓ we derive from Lemma 5 that there are two (m -1)-faces in y ↓ including z, one of which is x. Hence, z is up unipolar in Y and, thanks to Propositions 4 and 5, we deduce that the set

Y 1 = {z ∈ Y | z x ↓ or dim(z) < m -2} is a strong deformation retract of Y.
Since, according to Lemma 5, any (mk)-face in x ↓⋆ is included in exactly one (mk + 1)-face in y ↓ \ x ↓ , we can inductively remove all faces of x ↓ from Y with the same argumentation as above. Hence, Z = Y \ x ↓ is a strong deformation retract of Y. In a second step, we are going to prove that the faces in Z \ x ′↓ are successively down unipolar if we remove them in an increasing order w.r.t. their dimension. Note that, since x ′ = y\ x, there is no 0-face in Z \ x ′↓ . So, suppose we have removed all faces in Z \ x ′↓ of dimension less than k (1 k m -2) and let z be a k-face in Z \ x ′↓ . Lemma 5 ensures that there exists in z ↓ exactly one (k -1)-face in Z 1 = Z \ {t ∈ Z | dim(t) < k} (which belongs to x ′↓ ) so z is down unipolar in Z 1 . Hence, we can inductively prove that x ′↓ is a strong deformation retract of Y. As any cell is contractible (Property 1), we are done.

Remark 2

The previous lemma is false if we omit the hypothesis dim(x) = dim(y) -1 and if dim(y) 3. Indeed, when the dimension of y is greater than 2, one can find a face x ∈ y ↓ , with dim(x) < dim(y) -1, such that there exists a subset X of Y = y ↓⋆ \ {x} which contains at least txo points but no unipolar point for X and the minimal (maximal) points of which are minimal (maximal) points of y ↓⋆ . Therefore any core of Y (and also any core of y ↓⋆ ) include X. So, Y is not contractible (and neither is y ↓⋆ ). Such a subset X is depicted in Figure 11 in a three dimensional space.

Proposition 6 Let X be a subcomplex of F n . a) If x ∈ X is unipolar, then x is simple and there exists y ∈ X such as (y, x) is a free pair. b) If x ∈ X is simple, there exist y, z ∈ x ↑⋆ such as (y, z) is a free pair. c) If (x, y) is a free pair, y is unipolar and x is simple in X \ {y}. Fig. 11 The set X shown in this figure contains eighteen faces included in the boundary of a 3-face: six 2faces (in green), six 1-faces (in red) and six 0-faces (in blue). The subset of X composed of the 0-faces and the 1-faces of X is a closed arc as is the subset of X composed of the 1-faces and the 2-faces of X. Thus, there are no unipolar points in X and all minimal (maximal) points in X are minimal (maximal) points for the boundary of the 3-face. Therefore, the boundary of the 3-face and any subset of this boundary including X will not be contractible.

Proof a) Let x ∈ X be a unipolar point. Since X is a complex, x ↓ ⊆ X and thus, x cannot be down unipolar (for a m-face in a cubical complexe covers 2m faces). So, x is up unipolar, i.e. x ↑⋆ has a minimum (denoted y) and is therefore contractible (Corollary 1). Hence, x is simple. Moreover, dim(y) = dim(x) + 1 (for X is a complex) and, y being the only face in x ↑⋆ with this dimension, we deduce from Lemma 5-a that it does not exist any face z ∈ x ↑⋆ such that dim(z) > dim(y). Thus, (y, x) is a free pair in X. b) Let x ∈ X be a simple face. Then, x ↑⋆ is contractible (for x ↓⋆ is not contractible: Corollary 5). Hence, either x ↑⋆ is a singleton or there is a face y unipolar in x ↑⋆ (Corollary 4). If x ↑⋆ is a singleton {y}, (y, x) is a free pair. Otherwise, we derive from the previous part of this proof that there is a face z in x ↑⋆ such that (z, y) is a free pair in x ↑⋆ and thus in X. c) Let (x, y) be a free pair. The face x is the only face in y ↑⋆ so y is up unipolar and, since X is a complex, dim(y) = dim(x) -1. Moreover, thanks to Lemma 6, we conclude that x is simple in X \ {y} (for x ↓⋆ ∩ (X \ {y}) = x ↓⋆ \ {y}).

w-simple points

The example of Figure 11 puts in evidence the need of a weaker condition on points to be deleted when processing the reduction of a digital image. The following definition of a wsimple point ("w" stands for "weak") and their properties are due to Barmak and Minian [START_REF] Barmak | One-point reductions of finite spaces, h-regular CW-complexes and collapsibility[END_REF] who call them γ-points. Bertrand in [START_REF] Bertrand | New notions for discrete topology[END_REF] defines a quite similar notion.

Definition 7 A point x of a poset is a w-simple point if the poset x ⋆ is homotopically trivial, i.e. if all its homotopy groups are trivial.

Property 9 gives several ways to prove that an element of a finite poset is a w-point and Property 10 ensures that the deletion of a w-point does not modify the homotopy groups.

Property 9 Let X and Y be finite posets. Then x ⋆ is homotopically trivial if x ↓⋆ or x ↑⋆ is homotopically trivial.

Property 10 Let X be a finite poset. Let x ∈ X be a w-simple point. Then, the inclusion i : X \ {x} → X is a weak homotopy equivalence.

Last, Theorem 7 states that, when deleting a w-point in a finite poset, the homotopy type of the continuous analogue keeps unchanged. In a 3D-image X, the cost to decide wether the set x ⋆ is homotopically trivial is not expensive. Indeed, K(x ⋆ ) is a 2-dimensional simplicial complex and it is enough to compute its connected components and its Euler characteristic. Moreover, the scheme proposed for the deletion of simple points is still valid (same dimensional w-simple points can be remove in parallel). An example of the use of this scheme on a 3-D image is given in Figure 12.

Conclusion

We have studied the links between the standard notion of path in a topological space and the notion of path in a graph (here, the Hasse diagram) and showed that there are closer that it could be thought. In particular, they lead to the same fundamental group. It is a new validation of the use of posets, as Kalimsky spaces or complexes spaces, to analyse or process digital images. In a further work in preparation, we will study the relations between the digital paths, and the digital fundamental groups in Z n , as defined by [START_REF] Kong | A digital fundamental group[END_REF], and the paths and fundamental groups in F n . Anyway, we hope we have succeeded to convince the reader that continuity is also a rich concept when applied to discrete or finite spaces. In fact, when dealing with finites spaces, the problems arise from injectivity, rather than from continuity. Such notions as Jordan curves, surfaces, manifolds which involve homeomorphisms, i.e. one-to-one correspondences, with pieces of R n cannot be used as-is in finite spaces and must be adapted. Nevertheless, standard topology offers a set of tools usable in finite spaces and useful links between finite spaces and continuous analogues.

  (i) ∅, X are open sets; (ii) any finite intersection of open sets is an open set; (iii) any union of open sets is an open set. The complement in X of an open set is called a closed set. From the above definition, any finite union of closed sets is a closed set and any intersection of closed sets is a closed set. A set of open sets is a basis for a topology if any open set is a union of open sets of this basis. A neighbourhood of a point x ∈ X is a subset of X including an open set containing x. The closure Y of a subset Y ⊆ X is the smallest closed set including Y. The interior Y • of a subset Y ⊆ X is the largest open set included in Y. It is also the union of all open sets included in Y. Closure and interior are dual notions since Y

Fig. 1 (

 1 Fig. 1 (a) An arc χ. The arrows give the ordering of the sequence. (b, c) Two elementary stretching of χ .

Fig. 5 (

 5 Fig. 5 (a) An abstract (cubical) cell C composed of one 2-face, four 1-faces and four 0-faces The four small black squares represent four points in Z n mutually 8-adjacent. (b) The geometric (cubical) cell gC which is the realization of C. (c) The geometric realization |gC| of gC.

Fig. 6 (

 6 Fig. 6 (a) An abstract cubical 2-cell f which models a digital point of Z n . (b) The Hasse diagramm of X( f ). (c) The simplicial complex K(X( f )). (d) The geometric realization of K(X( f )).

Fig. 7 (

 7 Fig. 7 (a) A complex X. (d) A complex Y which is an elementary collapse of X. (b-c) Two steps in a strong deformation retraction of |X| onto |Y|.

Fig. 8

 8 Fig. 8 Left: a subset X of F n . Right: its Hasse diagram. The 2-face x is down unipolar and the 1-face y is up unipolar. Neither x in X \ {y} or y in X \ {x} are unipolar.

Fig. 10

 10 Fig. 10 Left: the original image. Right: a squeleton obtained by the parallel removal of simple points of same dimension until stability.

Theorem 7

 7 Let X be a finite poset and let x ∈ X be a w-simple point. Then |K(X \ {x})| and |K(X)| are simple-homotopy equivalent.

Fig. 12

 12 Fig. 12 Reduction by w-points removal in 3D-space. Left: a hollow pinched torus whith five little holes. Right: The same torus after the removal of w-points untill stability.

  path. There is a regular path p ′ with same track as p such that p ′ p. -Let p 1 p 2 be two finite paths. There are two regular paths p ′ 1 p 1 , p ′ 2 p 2 with same tracks as p 1 and p 2 such that p ′

	1	p ′ 2 .

In[START_REF] Latecki | Multicolor well-composed pictures[END_REF], Latecki writes "topology is basically not a finite concept and reduces to triviality whenever applied to finite sets".

The definition of a path by Kovalevsky[START_REF] Kovalevsky | Finite topology as applied to image analysis[END_REF] in the framework of cellular complexes corresponds to the definition of an arc given above while the definition of a digital path by Kong et al.[START_REF] Kong | A topological approach to digital topology[END_REF] in the framework of the Khalimsky topology corresponds to the definition of a minimal path above.

See Section 2.1.4