Phuc Ngo

Nicolas Passat
email: nicolas.passat@univ-reims.fr

Yukiko Kenmochi
email: yukiko.kenmochi@esiee.fr

Isabelle Debled-Rennesson
email: isabelle.debled-rennesson@loria.fr

Geometric preservation of 2D digital objects under rigid motions

Keywords: Rigid motions, Geometry and topology preservation, Polygonization, Digitization, Quasi-rregularity

Rigid motions (i.e. transformations based on translations and rotations) are simple, yet important, transformations in image processing. In R n , they are both topology and geometry preserving. Unfortunately, these properties are generally lost in Z n . In particular, when applying a rigid motion on a digital object, one generally alters its structure but also the global shape of its boundary. These alterations are mainly caused by digitization during the transformation process. In this specific context, some solutions for the handling of topological issues were proposed in Z 2 . In this article, we also focus on geometric issues in Z 2 . Indeed, we propose a rigid motion scheme that preserves geometry and topology properties of the transformed digital object: a connected object will remain connected, and some geometric properties (e.g. convexity, area and perimeter) will be preserved. To reach that goal, our main contributions are twofold. First, from an algorithmic point of view, our scheme relies on (1) a polygonization of the digital object, (2) the transformation of the intermediate piecewise affine object of R 2 , and (3) a digitization step for recovering a result within Z 2 . The intermediate modeling of a digital object of Z 2 as a

Introduction

Image processing and computer vision applications often require manipulation of discrete models of images. Among the various existing discrete models (e.g. meshes, point clouds), digital images, defined as finite sets of points on Z n , are of wide importance. Indeed, digital images naturally fit with most image acquisition devices based on a Cartesian sampling of the observed scene (e.g. medical imaging scanners, remote sensing optical imagers). Being able to manipulate digital objects defined as finite subsets of Z n is then of paramount importance.

Such manipulations can involve rigid or non-rigid transformations. Non-rigid transformations are generally considered for matching different scenes (e.g. for registration [START_REF] Zitová | Image registration methods: A survey[END_REF]) or to fit a given model onto a structure of interest (e.g. for segmentation [START_REF] Faisan | Topology-preserving warping of binary images according to one-to-one mappings[END_REF]). In this context, topological preservation is crucial while geometry may evolve. Rigid transformations are much simpler operations. They are basically involved in the handling of digital objects, or preprocessing tasks. In this context, both topology and geometry preservation are crucial. Indeed, the structure of the digital objects has to be preserved, but their shape should also remain unchanged.

In this article, we are interested in rigid transformations on digital objects. More precisely, we focus on rigid motions. Rigid motions are defined as compositions of translations and rotations, namely the two most fundamental operations for "moving" objects in a scene. Intuitively, such rigid motions have to preserve the object; this is indeed the case in the Euclidean model currently used for our physical world. In R n , rigid motions are bijective, isometric operations; the structure of the handled objects is preserved such as their geometrical properties, and in particular their shape.

In general, this is no longer true in discrete spaces. This is mainly due to the sparse structure of Z n , that implies a non-continuous behaviour of rigid motions [START_REF] Ngo | Combinatorial structure of rigid transformations in 2D digital images[END_REF]. In other words, when applying a rigid motion operator T on a digital point p ∈ Z n , the resulting value T(p) generally lies out of Z n . It is then necessary to find a way for carrying T(p) back to Z n . The induced approximation may lead to altering the topological structure of the object X containing p. It may also modify the global shape of X by slightly moving its different points in a heterogeneous way [START_REF] Pluta | Bijective digitized rigid motions on subsets of the plane[END_REF].

In the case of Z 2 , some strategies were recently investigated for providing topological guarantees when applying a rigid motion on digital objects [START_REF] Ngo | Topologypreserving conditions for 2D digital images under rigid transformations[END_REF][START_REF] Ngo | Topologypreserving rigid transformation of 2D digital images[END_REF]. However, such approaches do not provide geometric guarantees. This weakness is mainly due to the fact that rigid motions are carried out in a pointwise way: each point p of X is transformed independently from the others, thus altering the shape of the object.

Our proposed solution for tackling the issue of geometry preservation is to consider an intermediate, continuous, representation P (X) of the object X of Z 2 . More precisely, we propose to define P (X) as a polygon modeling the general shape of the digital boundary of X. Such a polygon, as a piecewise affine object of R 2 , can be processed in a topology and geometry preserving way by the transformation T. The main issue remaining to be tackled is then related to the digitization of the polygon T(P (X)) back to Z 2 . Such digitization problem is related to pioneering works [START_REF] Pavlidis | Algorithms for Graphics and Image Processing[END_REF] developed by Pavlidis in the 1980s. However, while Pavlidis was interested in the digitization of "smooth" objects, i.e. objects of R 2 with boundaries having differentiable properties, we have to consider here some polygons, with non-differentiable boundary points.

This article is an extended and improved version of the conference paper [START_REF] Ngo | Convexity-preserving rigid motions of 2D digital objects[END_REF]. A first contribution, in Sec-tion 3, is a sufficient condition for guaranteeing the preservation of connectedness during the process of digitization of an object of R 2 . This condition, defined under the name of quasi-r-regularity, can be seen as an analogue of the r-regularity proposed by Pavlidis for smooth objects [START_REF] Pavlidis | Algorithms for Graphics and Image Processing[END_REF]. This condition is then involved in the next two sections, for preserving satisfactory geometry and topology properties during the rigid motion of a digital object. In Section 4, we describe our rigid motion process in the case where the input digital object is well-composed and convex. (In such case, the induced polygon is also convex.) The transformed object remains convex; in particular, its topology is unchanged. In Section 5, we consider, more generally, the case of well-composed objects, not necessarily convex. We also show that under the conditions of quasi-r-regularity, the transformed object remains well-composed and preserves the global geometry of its shape. Section 6 provides some experimental results of the proposed framework for rigid motions on convex and non-convex digital objects. A concluding discussion is proposed in Section 7. In order to make this work self-contained, we recall, in Section 2, some basic definitions and notations related to rigid motions, and the various notions of regularity on digital images.

Rigid motions and digitization

Rigid motions on R 2

A rigid motion T in the Euclidean space R 2 is defined, for any point x = (x 1 , x 2 ) T as

T(x) = cos θ -sin θ sin θ cos θ x 1 x 2 + t 1 t 2 (1)
where θ ∈ [0, 2π) is a rotation angle, and (t 1 , t 2 ) T ∈ R 2 is a translation vector. Let X be a continuous object in the Euclidean space R 2 . (In the sequel, we will implicitly consider that X is bounded and connected.) The transformation T is bijective, isometric and orientation-preserving. Then, the transformed object T(X ) has the same shape, i.e. the same geometry and topology, as X . In the next subsections, we will observe that these properties are generally lost during the digitization process required to define rigid motions on Z 2 from rigid motions on R 2 .

Digitization and topology preservation

A digital object X ⊂ Z 2 is generally the result of a digitization process applied on a continuous object X ⊂ R 2 . (In the sequel, we will implicitly consider that X is

(a) (b) (c)
Fig. 1 (a) A continuous object X in R 2 . (b) A Gauss digitization of X , leading to the definition of X which is composed by the black points of Z 2 within X . (c) The digital object X represented as a set of pixels. The objects X and X are not topologically equivalent: the digitization process led to a disconnection, due to the resolution of the discrete grid, not fine enough for catching the shape of X .

a finite subset of Z 2 , which can be given as an image segmentation result in practice.) We consider the Gauss digitization [START_REF] Klette | Digital Geometry: Geometric Methods for Digital Picture Analysis[END_REF], which is simply the intersection of a continuous object

X with Z 2 X = X ∩ Z 2 (2)
The object X is a subset of Z 2 ; but from an imaging point of view, it can also be seen as a subset of pixels, i.e. unit squares defined as the Voronoi cells of the points of X within R 2 . Based on these different models, the structure of X can be defined in various topological frameworks which are mainly equivalent [START_REF] Mazo | Digital imaging: A unified topological framework[END_REF] to that of digital topology [START_REF] Kong | Digital topology: Introduction and survey[END_REF]. However, this digital topology of X is often non-coherent with the continuous topology of X . This fact is illustrated in Fig. 1, where a connected continuous object X leads, after Gauss digitization, to a disconnected digital object X.

In the literature, various studies proposed conditions for guaranteeing the preservation of topology of digitized objects [START_REF] Serra | Image Analysis and Mathematical Morphology[END_REF][START_REF] Latecki | Preserving topology by a digitization process[END_REF][START_REF] Stelldinger | Towards a general sampling theory for shape preservation[END_REF]. In particular, in [START_REF] Pavlidis | Algorithms for Graphics and Image Processing[END_REF] Pavlidis introduced the notion of r-regularity.

Definition 1 (r-regularity) An object X ⊂ R 2 is rregular if for each boundary point of X , there exist two tangent open disks of radius r, lying entirely in X and its complement X , respectively1 .

The notion of r-regularity is based on classical concepts of differential geometry. In particular, r-regularity is strongly related to bounded values of curvature, parameterized by the resolution of the digitization sampling. Pavlidis proved the topological equivalence of an r-regular continuous, smooth, object X and its digital counterpart X, for a dense sampling.

Proposition 1 ([7]

) An r-regular object X ⊂ R 2 has the same topological structure as its digitized version

X = X ∩ Z 2 if r ≥ √ 2 2 .
Remark 1 In [START_REF] Pavlidis | Algorithms for Graphics and Image Processing[END_REF], "the same topological structure" between two objects means that there exists an homeomorphism between both. In the sequel, we will consider the same paradigm. However, it is worth mentioning that in the 2D case and for digital objects whose continuous analogues have a manifold boundary (this will be our case with well-composed objects, see below), most topological invariants are indeed equivalent, namely homotopy type, adjacency tree and homeomorphism [START_REF] Rosenfeld | Adjacency in digital pictures[END_REF][START_REF] Rosenfeld | Topologypreserving deformations of two-valued digital pictures[END_REF][START_REF] Boutry | A tutorial on wellcomposedness[END_REF].

It was shown that the digitization process of an rregular object yields a well-composed object [START_REF] Latecki | Preserving topology by a digitization process[END_REF], whose definition relies on standard concepts of digital topology, recalled hereafter, for the sake of completeness.

Two distinct points p, q ∈ Z 2 , are k-adjacent if

p -q ≤ 1 (3)
with k = 4 (resp. 8) when = 1 (resp. ∞). From the reflexive-transitive closure of the k-adjacency relation on a finite subset X ⊂ Z 2 , we derive the k-connectivity relation on X. It is an equivalence relation, whose equivalence classes are called the k-connected components of X. Due to paradoxes related to the discrete version of the Jordan theorem [START_REF] Maunder | Algebraic Topology[END_REF], dual adjacencies are used for X and its complement X, namely (4, 8)-or (8, 4)adjacencies [START_REF] Rosenfeld | Digital topology[END_REF].

The notion of well-composedness [START_REF] Latecki | Well-composed sets[END_REF] has been introduced to characterize the digital objects whose structure intrinsically avoids the topological issues of the Jordan theorem.

Definition 2 (Well-composed sets) A digital object X ⊂ Z 2 is well-composed if each 8-connected component of X and of its complement X is also 4-connected. This definition implies that the boundary 2 of X is a set of 1-manifolds whenever X is well-composed (see Fig. 2). In particular, there exists a strong link between r-regularity and well-composedness.

Proposition 2 ([13]) If an object X ⊂ R 2 is r-regular, with r ≥ √ 2
2 , then X = X ∩Z 2 is a well-composed digital object. 2 The boundary of X is defined here as the boundary of the continuous object obtained as the union of the closed Voronoi cells associated to the points of X, in R 2 .

Digitized rigid motions

If we straightforwardly apply a rigid motion T, such as defined in Eq. ( 1), to a digital object X ⊂ Z 2 , we generally obtain a transformed object T(X) ⊂ Z 2 . In order to obtain a result in Z 2 , we further need a digitization operator

D : R 2 → Z 2 (4)
which can be, for instance, the standard rounding function. Then, a digital analogue of T can be defined as the composition of T, (restricted to Z 2 ) with such digitization operator, i.e. D • T |Z 2 . As stated above, rigid motions on R 2 are bijective. By contrast, rigid motions followed by a digitization operator are, in general, neither injective nor surjective. This may lead to unwanted results, such as conflicted or empty pixels, as illustrated in Fig. 3. To overcome such issues, we generally consider the inverse of the rigid motion to define the discrete analogue of T on Z 2 by setting

T -1 P oint = D • T -1 |Z 2 (5)
In other words, we use a backward model for the computation of the rigid motion of a digital object X. Indeed, we consider that the object T P oint (X) ⊂ Z 2 induced by the digitized version of the rigid motion T is defined such that

p ∈ T P oint (X) ⇔ T -1 P oint (p) ∈ X (6)

Topology and geometry alterations caused by digitized rigid motions

This backward model can also be interpreted, in a forward way, as the digitization of a transformed continuous object. Indeed, let us denote by V (X) ⊂ R 2 the continuous object obtained as the union of the closed Voronoi cells associated to the points of X; in other words, let us consider the digital object as its set of pixels. Then, the transformed digital object T P oint (X) is obtained as the Gauss digitization of the transformed object resulting from the rigid motion of V (X) by T.

More formally, we have

T P oint (X) = T(V (X)) ∩ Z 2 (7)
Note that this is equivalent to Eqs. ( 5) and [START_REF] Ngo | Topologypreserving rigid transformation of 2D digital images[END_REF].

In other words, the problem of digital rigid motion can be expressed as a problem of digitization of a continuous object. However, this continuous object V (X) has a boundary consisting of pixel edges. In particular, such boundary is locally non-differentiable, and the approach proposed by Pavlidis for smooth-boundary object is then non-valid.

The issue of topology preservation in such non-differentiable case was investigated in [START_REF] Ngo | Topologypreserving rigid transformation of 2D digital images[END_REF], where it led to the definition of a notion of digital regularity (simply called regularity in [START_REF] Ngo | Topologypreserving rigid transformation of 2D digital images[END_REF]). Digital regularity provides a sufficient condition for guaranteeing that a well-composed digital object X will not be topologically modified by any arbitrary rigid motion. However, despite this topological property, the notion of digital regularity does not tackle the issue of geometry alteration. Indeed, the rigid motion model, such as defined in Eqs. [START_REF] Ngo | Topologypreserving conditions for 2D digital images under rigid transformations[END_REF][START_REF] Ngo | Topologypreserving rigid transformation of 2D digital images[END_REF][START_REF] Pavlidis | Algorithms for Graphics and Image Processing[END_REF], acts on the object in a pointwise way. It is then unable to preserve the global coherence of the object boundary, thus leading to a "noisy" result. This is illustrated in Fig. 4.

Purpose and contributions

Our purpose is to perform rigid motions on digital objects while preserving their geometry. In particular, we are interested in preserving the global shape of the objects. To tackle this issue, our main idea is to apply the rigid transformation on an object as a whole, and no longer in a point-wise fashion.

To this end, we propose to represent a digital object of Z 2 as a digitization of a continuous object, namely a polygon of R 2 . This strategy has several advantages. First, it allows us to apply the rigid motion in R 2 , with the geometric and topological guarantees within this space. Second, since a polygon has a discrete representation, it can be processed without numerical error, by considering transformations based on integers (or, equivalently, rationals).

In this context, our assumption is that the polygon has to relevantly capture the geometry of the digital object. In particular, this means that the Gauss digitization of the polygon has to get us back to the initial digital object. In other words, the global shape of the digital object, namely the succession of the convex and concave parts of its boundary, has to be captured by the polygonization process. In particular, this means that a digitally convex object of Z 2 will lead to a convex polygon. In that case, we will choose as relevant polygon model its convex hull. In the other cases, the polygon will depend on the user's polygonization policy.

Based on these hypotheses, we propose, as a first contribution, an algorithmic framework for rigid motion of digital objects of Z 2 . It relies on three successive steps: (1) the polygonization of the digital object; (2) the transformation of the intermediate piecewise affine object (polygon) of R 2 ; and (3) the digitization of the transformed polygon for recovering a result within Z 2 . In the case of an initial object being digitally convex, our framework is proved to provide a final digital object which is also digitally convex. In the other cases, it is experimentally observed that the shape of objects are correctly preserved. More precisely, such a observation can be done qualitatively and quantitatively in which geometric properties, for example area and perimeter, are measured. Fig. 4 Geometry and topology alterations induced by digitized rigid motions. (a) A well-composed object, in grey. The object is not digitally regular at the corners of the rectangle, and at the junction between the disk and the rectangle. (b) Digital rigid motion T P oint of (a). The boundary is more noisy than that of the initial object. In addition, we observe that the 4-connectivity has been lost at the junction between the disk and the circle (red frames), and at the opposite corner of the rectangle (blue frames); this is a side effect of nondigital regularity in these areas.

Generally, preserving the geometry also implies to preserve the topology. This implication is mostly offered in R 2 , while it is hardly obtained in Z 2 . This is the motivation for our second contribution. Indeed, we propose a new notion of quasi-r-regularity, defined on continuous objects, and in particular polygons. It provides sufficient conditions to be fulfilled by a continuous object for guaranteeing topology preservation during its digitization.

In Sections 4-5, we deal with simply connected objects, i.e. digital objects that are connected and without holes. The case of non-connected objects with holes may be handled without much difficulty from this case.

Quasi-r-regularity

In order to make this article self-contained, let us first recall some notations and a few mathematical morphology notions [START_REF] Serra | Image Analysis and Mathematical Morphology[END_REF][START_REF] Heijmans | The algebraic basis of mathematical morphology. I Dilations and erosions[END_REF][START_REF] Ronse | The algebraic basis of mathematical morphology: II. Openings and closings[END_REF]. We denote by ⊕ and the classical operators of dilation and erosion, corresponding to the Minkowski addition, and its associated subtraction

X ⊕ Y = y∈Y X y = x∈X Y x (8) X Y = y∈Y X -y (9)
where

X y = {x + y | x ∈ X} and, in our case, X, Y ⊂ R 2 .
We also denote by • the composition of erosion and dilation, that is

X • Y = (X Y ) ⊕ Y (10)
We denote by B r a closed disk of R 2 of radius r > 0 and centered on (0, 0) ∈ R 2 .

We are now ready to introduce the notion of quasir-regularity. Intuitively, a quasi-r-regular object X of R 2 presents sufficient conditions for guaranteeing that its connectedness will not be affected by a Gauss digitization process.

Definition 3 (Quasi-r-regularity) Let r > 0. Let X ⊂ R 2 be a bounded, simply connected (i.e. connected and with no holes) object. We say that X is quasi-rregular if it satisfies the following four properties:

-X B r is non-empty and connected; -X B r is connected; -X ⊆ (X B r ) ⊕ B r √ 2 ; and -X ⊆ (X B r ) ⊕ B r √ 2 ;
Remark 2 This definition does not require specific assumption on the boundary of X. In particular, it does not need to be differentiable.

Remark 3

In order to compare the two notions of quasir-regularity and of Pavlidis' r-regularity, we rewrite hereafter the definition of r-regularity of a bounded, simply connected object X ⊂ R 2 : X is r-regular if:

-X B r is non-empty and connected;

-X B r is connected; -X = (X B r ) ⊕ B r ; and -X = (X B r ) ⊕ B r .
In particular we observe that the principal difference between both notions is the fact that the matching between X (resp. X) and its opening need to be perfect in the case of r-regularity, while a "margin" is authorized in the case of quasi-r-regularity, thus allowing for non-smooth (for instance, non-differentiable, noisy. . . ) boundary. Examples of quasi-1-regular and non-quasi-1-regular objects are given in Fig. 5. Perspectives related to this remark will be evoked in Section 7.

Proposition 3 If X is quasi-1-regular, then X = X ∩ Z 2 and X = X ∩ Z 2 are both 4-connected.
In particular, X is then well-composed.

Proof We prove the 4-connectedness of X; the same reasoning holds for X. Let us first prove that (X • B 1 ) ∩ Z 2 is 4-connected. Let p and q be two distinct points of (X • B 1 ) ∩ Z 2 . Let B p 1 and B q 1 be two disks of radius 1, included in X • B 1 and such that p ∈ B p 1 and q ∈ B q 1 . (Such disks exist, from the definition of opening.) Let b p and b q be the centers of B p 1 and B q 1 , respectively. We have b p , b q ∈ X B 1 , from the definition of erosion. Since X B 1 is connected in R 2 ; there exists a continuous path Π from b p to b q in X B 1 . Note that for any a disk B 1 , we always have B 1 ∩ Z 2 non-empty and 4connected; in particular it contains at least two points of Z 2 . For a value ε > 0 small enough, two disks B 1 and

B 1 with centres distant of ε are such that B 1 ∩B 1 ∩Z 2 = ∅. As a consequence, the union b∈Π B 1 (b) ∩ Z 2 (with B 1 (b) the disk of center b) is a 4-connected set of Z 2 .
In addition, we have p, q ∈ b∈Π B 1 (b) ∩ Z 2 . Then, p and q are 4-connected in (X • B 1 ) ∩ Z 2 , and it follows that (X

• B 1 ) ∩ Z 2 is a 4-connected set. Let us now prove that any point r ∈ X \ (X • B 1 ) is 4-adjacent to a point of (X • B 1 ) ∩ Z 2 . Let us consider such point r. We have r ∈ X ⊆ X B 1 ⊕ B √ 2 . Then, from the definition of dilation, there exists b ∈ X B 1 such that b is the centre of a disk B √ 2 (b) of radius √ 2,
and r is a point in that disk. In particular, the distance between b and r lies in (1,

√ 2]. As b is a point of X B 1 , it is also the centre of a disk B 1 (b) of radius 1 included in X • B 1 .
Let us consider the circle C 1 (r) of radius 1 and centre r. This circle C 1 (r) intersects B 1 (b), and this intersection is a circular segment of radius 1 and angle α ∈ [ π 2 , 2π 3 ), included in X • B 1 ; in particular, we have α ≥ π 2 (see Fig. 6).

Then, this segment necessarily contains a point t ∈ Z 2 , that lies in (X • B 1 ) ∩ Z 2 . The points r and t are 4-adjacent. It follows that X ∩ Z 2 is 4-connected. This notion of quasi-r-regularity will be used in the next two sections for guaranteeing the preservation of topological properties of digital objects during rigid motions, via their polygonal representation.

: (b) X ⊆ (X B 1 ) ⊕ B √ 2 ; (c) X B 1 is not connected; (d) X B 1 is not connected. The objects X ⊂ R 2 are

Rigid motions of digitally convex objects

In this section, we first deal with a specific case of digital objects, namely the convex ones. For rigid motion purpose, we build a continuous polygon corresponding to the convex hull of the input digital object. Then, we move this continuous polygon, and we finally digitize it for retrieving the final transformed digital object. We show that, by this process, the digital convexity is preserved if the convex hull is quasi-1-regular.

Digital convexity

In the Euclidean space R 2 , an object X is said to be convex if, for any pair of points x, y ∈ X , the line segment joining x and y

[x, y] = {λx + (1 -λ)y ∈ R 2 | 0 ≤ λ ≤ 1} (11)
is included in X . However, this intuitive continuous notion cannot be directly transposed to digital objects of Z 2 . Indeed, given a digital object X in Z 2 , for p, q ∈ X we have [p, q] ⊂ Z 2 if p = q.

In order to tackle this problem, various extensions of the notion of convexity have been proposed for Z 2 . We can cite, for instance: MP-convexity [START_REF] Minsky | Perceptrons: An Introduction to Computational Geometry[END_REF] which is a straightforward extension of the continuous notion; Sconvexity [START_REF] Sklansky | Recognition of convex blobs[END_REF] which uses convex objects in R 2 to determine the convexity of objects in Z 2 ; H-convexity3 [START_REF] Kim | On the cellular convexity of complexes[END_REF][START_REF] Eckhardt | Digital lines and digital convexity[END_REF] which is a geometrical version of S-convexity, using the convex hull of digital objects; and D-convexity [START_REF] Kim | Digital straight lines and convexity of digital regions[END_REF] which is based on the notion of digital line.

In the case of 4-adjacency modeling of digital objects, MP-and H-convexities have been proved equivalent [START_REF] Kim | On the cellular convexity of complexes[END_REF]Theorem 5]. Similar results under the assumption of 8-adjacency can be found in [START_REF] Eckhardt | Digital lines and digital convexity[END_REF], via the chord property, which relate the MP-, H-and D-convexities. Under the condition that X has no isolated point (i.e. no point adjacent to one other point within X), it was then proved that X is H-convex iff it is S-convex [START_REF] Kim | On the cellular convexity of complexes[END_REF]Theorem 4]. A more complete description on various notions of digital convexity can be found in [START_REF] Cristescu | Non-Connected Convexities and Applications[END_REF]Chapter 9].

In this section, the notion of H-convexity was chosen. This is motivated, on the one hand, by its compliance with the other kinds of convexities in the case of 4-connected (and, a fortiori, well-composed) digital objects. On the other hand, the notion of H-convexity relies on the explicit definition of the convex hull of the digital object. Such polygonal object provides us with a continuous model that can be involved in the continuous part of our rigid motion algorithmic process. Fig. 7 A digital object X that is H-convex, but not connected. This is due, here, to the acute angle at the highest vertex of the convex hull Conv(X) that allows the induced polygon to "pass between" two 4-adjacent points of the background of X.

We recall hereafter the definition of the convex hull of a digital object X ⊂ Z 2 , denoted by Conv(X).

Conv(X) = x = |X| i=1 λ i p i ∈ R 2 |X| i=1 λ i = 1 (12) ∧ ∀i ∈ {1, . . . , |X|}, (λ i ≥ 0 ∧ p i ∈ X) Definition 4 (H-convexity [26]) A digital object X ⊂ Z 2 is H-convex if X = Conv(X) ∩ Z 2 (13)
i.e. if X is equal to the digitization of its continuous polygonal convex hull.

Remark 4 An H-convex object is not necessarily connected. This is exemplified in Fig. 7.

It is important to notice that, similarly to continuous convexity, H-convexity remains stable by intersection. In particular, we have the following property.

Property 1 Let X and Y be two digital objects in Z 2 . If X and Y are H-convex, then X ∩ Y is H-convex.
Proof Let X and Y be two H-convex digital objects. We have

X = Conv(X) ∩ Z 2 and Y = Conv(Y) ∩ Z 2 . Then, it comes X ∩ Y = Conv(X) ∩ Conv(Y) ∩ Z 2 . It is plain that Conv(X ∩ Y) ⊆ Conv(X) ∩ Conv(Y) and then we have Conv(X ∩ Y) ∩ Z 2 ⊆ Conv(X) ∩ Conv(Y) ∩ Z 2 . Now, let us consider p ∈ Conv(X) ∩ Conv(Y) ∩ Z 2 . We have p ∈ Conv(X)∩Z 2 = X and p ∈ Conv(Y)∩Z 2 = Y. Then, we have p ∈ X ∩ Y ⊆ Conv(X ∩ Y). But since p ∈ Z 2 , it comes p ∈ Conv(X ∩ Y) ∩ Z 2 . Consequently, we have Conv(X ∩ Y) ∩ Z 2 = Conv(X) ∩ Conv(Y) ∩ Z 2 .

Polygonization of H-convex digital objects

The first step of the algorithmic process for computing the rigid motion of an H-convex digital object X consists of computing its polygonal convex hull.

If X contains at least three non-colinear points, then its convex hull Conv(X) is a non-trivial convex polygon whose vertices are some points of X. As these vertices are grid points of Z 2 , the polygon Conv(X) is defined as the intersection of closed half-planes with integer coefficients

Conv(X) = H∈R(X) H ( 14
)
where R(X) is the smallest set of closed half-planes that include X. This set is finite and sufficient for defining Conv(X). Each closed half-plane H of this subset is defined as

H = {(x, y) ∈ R 2 | ax + by + c ≤ 0} (15)
with a, b, c ∈ Z and gcd(a, b) = 1. Note that the integer coefficients of H are obtained by a pair of consecutive vertices of Conv(X), denoted by u, v ∈ Z 2 , which are in the clockwise order, such that

(a, b) = 1 gcd(w x , w y ) (-w y , w x ) (16) c = (a, b) • u (17)
where (w x , w y ) = vu ∈ Z 2 . Many algorithms can be used to compute the convex hull of a digital object. In [START_REF] Debled-Rennesson | Detection of the discrete convexity of polyominoes[END_REF], a linear time algorithm determines whether a given polyomino is convex and, in that case, it returns its convex hull. This method relies on the incremental digital straight line recognition algorithm [START_REF] Debled-Rennesson | A linear algorithm for segmentation of digital curves[END_REF], and uses the geometrical properties of leaning points of maximal discrete straight line segments on the contour. The algorithm scans the contour curve and decomposes it into discrete segments whose extremities must be leaning points. The tangential cover of the curve [START_REF] Feschet | Optimal time computation of the tangent of a discrete curve: Application to the curvature[END_REF] can be used to obtain this decomposition. Alternatively, an approach presented in [START_REF] Brlek | Lyndon + Christoffel = digitally convex[END_REF] uses tools of combinatorics on words to study contour words: the linear Lyndon factorization algorithm [START_REF] Duval | Factorizing words over an ordered alphabet[END_REF] and the Christoffel words. A linear time algorithm decides convexity of polyominoes and can also compute the convex hull of a digital object (it is presented as a discrete version of the classical Melkman algorithm [START_REF] Melkman | On-line construction of the convex hull of a simple polyline[END_REF]).

The half-planes can then be deduced from the consecutive vertices of the computed convex hull, from Eqs. [START_REF] Rosenfeld | Adjacency in digital pictures[END_REF][START_REF] Rosenfeld | Topologypreserving deformations of two-valued digital pictures[END_REF][START_REF] Boutry | A tutorial on wellcomposedness[END_REF]. An example of convex hull and half-plane modeling of an H-convex digital object is illustrated in Fig. 8.

Convexity-preserving rigid motion

In order to perform rigid motions without any numerical approximation, one can consider only rigid motions with rational parameters. Doing so, only exact computations with integers can be involved. This does not constitute an applicative restriction, due to the density of rational values within the rotation and translation parameter space.

Thus, we assume hereafter that all the parameters of a rigid motion T are rational (see Eq. ( 1)). More precisely, on the one hand, the rotation matrix R is defined as 1 r p -q q p where p, q, r ∈ Z constitute a Pythagorean triple, i.e. p 2 +q 2 = r 2 , r = 0. On the other hand, the translation vector is defined as (t

1 , t 2 ) T ∈ Q 2 .
This assumption is fair, as we can always find rational parameter values as close as desired from any real values [START_REF] Anglin | Using Pythagorean triangles to approximate angles[END_REF] for defining such a Pythagorean triple.

A half-plane H, as defined in Eq. ( 15), is transformed by such (rational) rigid motion T as follows

T(H) = {(x, y) ∈ R 2 | αx + βy + γ ≤ 0} (18)
where α, β, γ ∈ Q are given by (α β) T = R(a b) T and γ = c + αt 1 + βt 2 . This leads to a rational half-plane, which can be easily rewritten as an integer half-plane in the form of Eq. [START_REF] Rosenfeld | Adjacency in digital pictures[END_REF]. Since an H-convex digital object X is represented by a finite set of digital half-planes, we can define the rigid motion T Conv of X on Z 2 via its continuous polygonal convex hull as follows

T Conv (X) = T(Conv(X))∩Z 2 = T H∈R(X) H ∩Z 2 (19)
Fig. 9 A sequence of transformations T Conv on an H-convex object X. The convex hull of T Conv (X) is included in the transformed convex hull of X and the cardinality of T Conv (X) ∩ Z 2 is lower than that of X.

This constitutes an alternative to the standard pointwise rigid motion defined in Eq. ( 5).

But, we have

T H∈R(X) H ∩ Z 2 = H∈R(X) T(H) ∩ Z 2 = H∈R(X) (T(H) ∩ Z 2 ) ( 20
)
The digitization of any continuous half-space of R 2 is Hconvex. Then, from Eqs. [START_REF] Rosenfeld | Digital topology[END_REF][START_REF] Latecki | Well-composed sets[END_REF], T Conv (X) is expressed as the intersection of a finite number of H-convex digital objects. The following proposition is then a corollary of Property 1.

Proposition 4 Let X be a digital object of Z 2 . Let T Conv be the polygon-based rigid motion induced by a rigid motion T with rational parameters. If X is H-convex, then T Conv (X) is H-convex.

The polygon corresponding to the convex hull of T Conv (X) is not equal, in general, to the transformed convex hull of X. However, we have the following inclusion relation.

Property 2 With the same hypotheses as in Prop. 4, we have

Conv(T Conv (X)) ⊆ T(Conv(X)) (21)
The proof of this property derives from the fact that T Conv (X) = T(Conv(X)) ∩ Z 2 . Thus we have T Conv (X) ⊆ T(Conv(X)), and this inclusion also holds for the convex hull of T Conv (X). First, this means that the cardinality of T Conv (X) is lower (often strictly) than that of X. In other words, T Conv is a decreasing operator with respect to the cardinality of the input digital object. A straightforward consequence is that T Conv is not bijective, in general. Second, this means that the polygons of the two convex hulls of the input and output digital objects may be distinct, with respect to their number and size of edges, and angles at vertices. However, the convexity of the objects is preserved, which was the fundamental property to satisfy. These facts are exemplified in Fig. 9 and experimentally observed in Section 6.

Rigid motions and topological aspects of convexity

In the previous subsections, we proposed an algorithmic scheme for performing rigid motions on H-convex digital objects, while preserving their H-convexity. In R 2 , the continuous definition of convexity intrinsically implies connectedness. By contrast, in Z 2 the notion of H-convexity (such as various other notions of digital convexity) does not always offer guarantees of connectedness, e.g. with respect to 4-and 8-adjacencies.

In order to illustrate that fact, let us consider the example of Fig. 7. The digital object X, composed of 8 points/pixels, is H-convex. Indeed, its convex hull contains only digital points that belong to X. However, X is not connected (neither with 4-nor 8-adjacencies). Such phenomenon is mainly caused by angular and/or metric factors: whenever an angle of the convex hull polygon is too acute, and/or when an edge is too short, such disconnections may happen.

Then, in addition to providing geometry guarantees of convexity -via the H-convexity of digital objectswhen performing rigid transformations of a digital object, it is desirable to also provide topology guarantees, and more precisely connectedness guarantees.

To reach that goal, we use the notion of quasi-rregularity introduced in Section 3. This additional notion provides us with sufficient conditions for ensuring that a digital H-convex object will remain not only Hconvex but also connected after any rigid motion.

In particular, the next proposition is a corollary of Propositions 3 and 4.

Proposition 5 Let X ⊂ Z 2 be an H-convex digital ob- ject. If Conv(X) is quasi-1-regular, then T Conv (X) is H- convex, 4-connected and well-composed.
Proof Let X ⊂ Z 2 be an H-convex digital object, and let us suppose that Conv(X) is quasi-1-regular. Then, from Prop. 4, T Conv (X) is H-convex. In addition, since Conv(X) is quasi-1-regular, then so is T(Conv(X)). Thus, from Prop. 3 we deduce that T(Conv(X))∩Z 2 = T Conv (X) is 4-connected and well-composed.

Remark 5 If Conv(X) is quasi-1-regular, then the initial object X is also 4-connected and well-composed.

Rigid motions of general digital objects

In this section, we now deal with rigid motions of digital objects without convexity hypothesis.

Polygonization of a digital object

There exist various methods for polygonizing a digital object. In the field of digital geometry, numerous approaches used the contour curves extracted from the digital objects; each method computes a polygonal representation of the digital object with particular properties. In [START_REF] Sivignon | Discrete analytical curve reconstruction without patches[END_REF][START_REF] Dexet | Invertible polygonalization of 3D planar digital curves and application to volume data reconstruction[END_REF], invertible methods enable us to compute Euclidean polygons whose digitization is equal to the original discrete boundary. These methods use the Vittone algorithm [START_REF] Vittone | Recognition of digital naive planes and polyhedrization[END_REF] in the preimage space for straight line recognition. In [START_REF] Feschet | On the min DSS problem of closed discrete curves[END_REF][START_REF] Dörksen-Reiter | Debled-Rennesson, Convex and concave parts of digital curves[END_REF][START_REF] Dörksen-Reiter | A linear algorithm for polygonal representations of digital sets[END_REF][START_REF] Roussillon | Faithful polygonal representation of the convex and concave parts of a digital curve[END_REF] the arithmetical recognition algorithm [START_REF] Debled-Rennesson | A linear algorithm for segmentation of digital curves[END_REF] is used to decompose a discrete contour and deduce a polygonal representation. These methods rely on the tangential cover of the contour [START_REF] Feschet | Optimal time computation of the tangent of a discrete curve: Application to the curvature[END_REF], composed of the sequence of its maximal discrete straight segments. It was proved in [START_REF] Feschet | On the min DSS problem of closed discrete curves[END_REF] that all polygonal representations of the contour can be deduced from its tangential cover, leading to a linear algorithm which computes the polygon with minimal integral summed squared error. In [START_REF] Dörksen-Reiter | Debled-Rennesson, Convex and concave parts of digital curves[END_REF][START_REF] Dörksen-Reiter | A linear algorithm for polygonal representations of digital sets[END_REF][START_REF] Roussillon | Faithful polygonal representation of the convex and concave parts of a digital curve[END_REF], the goal was different. It consisted of determining a reversible polygon that faithfully represents the convex and concave parts of the boundary of a digital object. The polygonization method proposed in [START_REF] Nguyen | A discrete geometry approach for dominant point detection[END_REF][START_REF] Ngo | Efficient dominant point detection based on discrete curve structure[END_REF] also exploits the idea of maximal straight segment primitives. It allows to identify the characteristic points on a contour, called dominant points, and to build a polygon representing the given contour. Another technique presented in [START_REF] Gérard | Introduction to digital level layers[END_REF] is the curve decomposition. It uses the analytical primitives, called digital level layers, to decompose a given contour and to obtain an analytical representation. Another algorithm is proposed in [START_REF] Sivignon | A near-linear time guaranteed algorithm for digital curve simplification under the Fréchet distance[END_REF] to compute the polygonal simplification of a curve such that the Fréchet distance [START_REF] Fréchet | Sur quelques points du calcul fonctionnel[END_REF] between the simplified polygon and the original curve is lower than a given error.

It should be mentioned that, for a given digital object, different results can be obtained from these various polygonization techniques. In other words, the polygonal representation of a digital object is not unique. However, the crucial property to be satisfied is that the polygon P (X) computed for a digital object X has to be coherent with respect to digitization, i.e. P (X)∩Z 2 = X. A second important property, in our framework of discrete geometry and exact calculus, is that the vertices of P (X) have integer or rational coordinates.

It should be mentioned that none of the methods mentioned above respects both of these properties. Most of them compute simplified polygon of input contours with criteria to minimize. Consequently, we adapt a polygonization strategy based on [START_REF] Nguyen | A discrete geometry approach for dominant point detection[END_REF][START_REF] Ngo | Efficient dominant point detection based on discrete curve structure[END_REF] in the experiment section (Section 6) in which it guarantees the above two properties. Some other relevant, but sometimes antagonistic, properties are discussed in Section 5.3.

Rigid motion of a polygon

As P (X) may be non-convex, we cannot use the halfplane representation, as it was done in Section 4.2 for convex polygons. Here, we use a standard vertex representation, by modeling a polygon via a sequence of successive vertices of its boundary.

Note that the vertices of P (X) are integer (or rational) points, and those of T(P (X)) are rational points, since the rigid motion T is given by a rational matrix and a rational translation vector (see Section 4.3).

Then, for each vertex of the polygon P (X), we simply apply the rigid motion T (see Eq. ( 1)) and preserve the order of the vertex sequence.

Discretization of polygons and geometry / topology preservation

Once the polygon T(P (X)) has been computed, the resulting object, denoted by T Poly (X) can be deduced. Similarly to the case of H-convex digital objects (Eq. ( 19)), this is done by embedding T(P (X)) in Z 2 via the Gauss digitization

T Poly (X) = T(P (X)) ∩ Z 2 (22)
Various ways exist for carrying out this digitization in an exact way. For instance, it is possible to decompose T(P (X)) into a partition of triangles whose vertices are (rational-coordinate) vertices of the boundary of T(P (X)). Each of such triangles being defined as a convex region modeled by three half-planes with rational parameters, the points of Z 2 contained herein can be determined without numerical error.

In order to ensure the connectedness preservation of X, we require, as for the H-convex case, that the polygon P (X) of X, is quasi-1-regular.

Proposition 6 Let X ⊂ Z 2 be a digital object. Let P (X) ⊂ R 2 be a polygon such that P (X) ∩ Z 2 = X. If P (X) is quasi-1-regular, then T Poly (X) is 4-connected and well-composed.

Proof Let X ⊂ Z 2 be a digital object, and let us suppose that P (X) ⊂ R 2 is a quasi-1-regular polygon such that P (X) ∩ Z 2 = X. Then, T(P (X)) is also a quasi-1-regular polygon. From Prop. 3 we deduce that T(P (X)) ∩ Z 2 = T Poly (X) is then 4-connected and well-composed.

Remark 6 Beyond topological guarantees (4-connectedness, well-composedness), the notion of quasi-1-regularity also presents some geometry properties. Indeed, any point of X is either part of P (X) • B 1 (i.e. the "smooth" opening of a polygon) or part of the (noisy) boundary in P (X)\(P (X)•B 1 ). But, in this second case, this point is necessarily at a distance not greater than √ 2 -1 < 0, 5 (i.e. the half of a pixel size) from this opening P (X) • B 1 . In other words, quasi-1-regularity describes objects with boundaries that may not be completely smooth (in particular, they may be non-differentiable), but that will be, in the worst cases, only slightly noisy, by contrast with results of standard pointwise rigid motions T P oint . This can be illustrated in Tables 1 and2.

As stated above, P (X) can be defined by following various policies. Then, there exist many (actually an infinite number of) polygons whose digitization leads to X. In particular, it may happen that P (X) is not quasi-1-regular while X and T Poly (X) are indeed 4-connected and well-composed.

This statement emphasizes the importance of choosing wisely a polygonization policy. In this context, various properties may be relevantly targeted.

A first property is related to the preservation of area. Indeed, due to the digitization procedure of the polygon, carried out by a regular sampling with respect to Z 2 , it may be useful that P (X) has an area in R 2 of the same order as the cardinal |X|. This is a heuristic strategy, since we can not guarantee that the digitized result will have exactly the same area as the initial digital object. It is however justified by the fact that each pixel (i.e. Voronoi cell) of a point of Z 2 has an area of 1 in R 2 . Consequently, for digital objects that are sufficiently large, the analogy between the area and the number of digital points makes sense. For smaller digital objects, where the boundary points are no longer negligible with respect to the overall set of points, this heuristics can be refined by considering more accurate formulas, for instance via Pick's theorem [START_REF] Pick | Geometrisches zur Zahlenlehre, Sitzungsberichte des Deutschen Naturwissenschaftlich-Medicinischen Vereines für Böhmen[END_REF].

A second property is related to the positioning of P (X) with respect to X. More precisely, it may be relevant that the barycentre of both P (X) and X be the same. Otherwise, the shift between both may statistically induce a translation bias in the rigid motion result.

Experiments and results

In this section, we present some experimental results obtained with the proposed methods on different digital objects, which are convex and not-convex. The comparison, in terms of topology and geometry -in particular, connectivity, convexity, area and perimeter-between three (resp. two) models of rigid motions T P oint , T Conv and T P oly (resp. T P oint and T P oly ) on convex (resp. nonconvex) objects is made. The effects of rigid motions on boundaries of digital objects are especially focused on.

It should be mentioned that the digital objects used in these experiments have their associated polygons quasi-1-regular.

Polygonization of digital objects

For an efficient computation of T Conv , we use the discrete version of the Melkman algorithm [START_REF] Melkman | On-line construction of the convex hull of a simple polyline[END_REF] to compute the convex hull of H-convex objects. This algorithm has a linear time complexity with respect to the number of digital points.

Concerning T P oly , for the polygonization of nonconvex objects, we apply the method of dominant point detection proposed in [START_REF] Nguyen | A discrete geometry approach for dominant point detection[END_REF][START_REF] Ngo | Efficient dominant point detection based on discrete curve structure[END_REF] with adaptation in order to obtain a result satisfying the two properties: (1) P (X) ∩ Z 2 = X and (2) the vertices of P (X) are integer points. More precisely, we initialize the ordered vertex set V of the polygon P as the sequence of dominant points (supposing that the order is clockwise). For each consecutive vertices p 1 and p 2 of V , let us consider the set of the contour points between p 1 and p 2 , denoted by C(p 1 , p 2 ). First, we verify if

(C(p 1 , p 2 ) \ P ) = ∅, (23)
i.e., if there exits at least one point of C(p 1 , p 2 ) outside of P , then, we select a point p 3 ∈ C(p 1 , p 2 ) \ P such that

p 3 = arg max q∈C(p1,p2)\P {d(q) | (∆qp 1 p 2 ∩ Z 2 ) ⊂ X}
where d(q) is the distance of q to the line passing by p 1 and p 2 and ∆pqr is the triangle whose vertices are p, q and r. If Eq. ( 23) does not hold, then we verify whether there exits any point q ∈ (X ∩ P ) such that q is in the polygon constructed from the polygonal line of C(p 1 , p 2 ) and the line segment from p 2 to p 1 . If so, we select p 3 ∈ C(p 1 , p 2 ) such that

p 3 = arg max q∈C(p1,p2)\P {d(q) | (∀r 1 ∈ C(p 1 , q), (∆p 1 r 1 q ∩ Z 2 ) ⊂ X) ∨ (∀r 2 ∈ C(q, p 2 ), (∆qr 2 p 2 ∩ Z 2 ) ⊂ X)}.
For either case, if such p 3 exists, we add it to V between p 1 and p 2 . We repeat this process with V until no point is added; see Fig. 10 for an illustration. Note that dominant points are also vertices of the obtained polygon. It is shown in [START_REF] Debled-Rennesson | A linear algorithm for segmentation of digital curves[END_REF] that dominant point detection algorithm can be achieved with a linear time complexity with respect to the number of contour points. Furthermore, the algorithm involves exact computation with integers and the obtained polygon has integer vertices.

Topological and convexity preservation

The first experiment of rigid motions was carried out on an H-convex digital object (see Fig. 11(a)). Figure 11 presents the result of T P oint , T Conv and T P oly on X. It should be mentioned that, in general, the polygon P (X) obtained by the method proposed in Section 6.1 is not equal to the convex hull Conv(X). In particular, even if X is H-convex, P (X) is often non-convex, as illustrated in Fig. 12. Therefore, T P oly does not guarantee to preserve the convexity of the transformed object (see Fig. 11(d)). On the contrary, T Conv preserves the convexity of the transformed object as shown in Prop. [START_REF] Pluta | Bijective digitized rigid motions on subsets of the plane[END_REF] and Fig. 11(a). By contrast, T P oint hardly preserves the convexity of the transformed object.

We performed the second experiments on two Hconvex digital objects, namely a disk of radius 10 and a square of size 21 × 21. We provide an assessment of the performance of rigid motions using three transformation models: T P oint , T Conv and T P oly . The experiment was conducted under a sequence of successive rotations around the origin (center of the objects), to evaluate the topological alterations accumulated in the transformed images. The experiment is as follows: a rotation is applied on the input image; then the transformed image is used as input for the next rotation, and so on. Tables 1 and2 provide the visual results of rotated images by the three transformation models on the disk and the square, respectively.

From both experiments, we observe that the rigid motions by T P oint alter the boundary of the objects and modify their topology.

Indeed, the initial disk and square objects are wellcomposed and H-convex; however the transformed objects are not. By contrast, the rigid motions by T Conv allow us to preserve topology together with convexity, as shown in Prop. 5, as far as Conv(X) is quasi-1-regular. However, as mentioned in Section 4.3, T Conv is a decreasing operator with respect to the cardinality of the input object (see Remark 2). The rigid motions by T P oly avoid this effect since T P oly is based on a polygon that fits the size of the digital object in a better way than the convex hull. Similarly to T Conv , T P oly allows the topological preservation when P (X) is quasi-1-regular, as shown in Prop. 6.

Area and perimeter preservation

Now, we aim to quantify experimentally the accuracy and stability of geometric measurements using the three models of rigid motions on convex digital objects. More precisely, we observe two measures: area and perimeter. The area is computed as the number of digital points within the transformed objects [START_REF] Klette | Multigrid convergence of calculated features in image analysis[END_REF] and the perimeter is calculated based on curve segmentation by maximal digital standard segment [START_REF] Kovalevsky | Theoretical and experimental analysis of the accuracy of perimeter estimates[END_REF] of the 4-connected curves extracted from the transformed objects. It has been proven that these estimators have multigrid convergence property [START_REF] Coeurjolly | Multigrid convergence of discrete geometric estimators[END_REF].

Two series of experiments are performed: the first with rotations for angles θ varying from 0 to 2π; the second with rigid motions randomly generated.

Figs. 13 and 14 report some quantitative comparisons of those geometric measures between rotations by T P oint , T Conv and T P oly on the input images given in Tables 1 and2. We can observe that T P oint and T Conv do not preserve well the perimeter of the transformed objects since T P oint alters the boundary of the objects and T Conv is a decreasing operator. By construction, T P oly uses a polygon that fits the input digital object for the transformation; thus it preserves well the perimeter. For the same reasons, T Conv does not preserve the area, contrary to T P oly . Since T P oint is defined on a point-bypoint model, it also preserves the area measure. In our last experiments, we perform rigid motions on non-convex objects (see Fig. 17 and Fig. 19). Again, we evaluate the proposed transformation models T P oint and T P oly with respect to the following measures: (i) area and (ii) perimeter. The results are respectively shown in Fig. 18 and Fig. 20, for rigid motions T P oly generated randomly with rotation angles θ ∈ [0, 2π) and translation values t 1 , t 2 ∈ [0, 1). We can observe that T P oint and T P oly both have a stable behaviour with respect to area measure, and T P oly preserves better the perimeter than T P oint .

Comparing three models of rigid motions T P oint , T Conv and T P oly , we can see that T P oint and T P oly preserve better area. Whereas T Conv is a decreasing operator, it is the only that allows the preservation of convexity. T P oint alters the boundary of the objects and does not preserve topology nor perimeter, while T P oly

T P oint (X) #Points=317 #Points=317 #Points=317 #Points=317 #Points=317 T Conv (X) #Points=297 #Points=273 #Points=257 #Points=237 #Points=213 T P oly (X) #Points=297 #Points=297 #Points=297 #Points=297 #Points=317
Table 1 Experiments on geometry and topology preservation on a disk of radius 10, for rotations of angle θ (the rotation centre is the centre of the disk). See Section 6.2.

preserves better perimeter and topology, when P (X) is quasi-1-regular.

Conclusion

In this article, we proposed an algorithmic process for performing rigid motions on digital objects, i.e. finite subsets of Z 2 , while preserving their global shape. This shape preservation was expressed in terms of geometry, but also in terms of topology, since the object should not be erroneously disconnected due to the discrete structure of Z 2 . In order to tackle these issues, our contributions were twofold. From a methodological point of view, we proposed to consider an intermediate continuous model of the digital object, namely a polygonal model. Such polygon is continuous and can then be processed by standard continuous transformations; it also remains discrete, and can then be processed without numerical error. From a theoretical point of view, we proposed a new notion of quasi-r-regularity that provides sufficient conditions for guaranteeing topological preservation when digitizing a continuous object. This notion of quasi-r-regularity was indeed required to correctly handle the mandatory digitization step induced by the use of an intermediate continuous polygonal model.

This work opens the way to various perspectives. First we will investigate how this rigid motion scheme can be extended to the 3D case, i.e. to digital objects defined in Z 3 . Such an extension cannot be straightforward as topological (and geometric) properties of Gauss digitization for more than two dimensions are different Table 2 Experiments on geometry and topology preservation on a square of size 21 × 21, for rotations of angle θ (the rotation centre is the barycentre of the square). See Section 6.2.

and more complex than those in two dimensions [START_REF] Lachaud | Properties of Gauss digitized shapes and digital surface integration[END_REF].

In addition, we will describe how to consider not only simply connected objects, but more generally arbitrarytopology objects (this is tractable in Z 2 , but less simple in Z 3 ). Second, from a practical point of view, we will investigate the relevance of different polygonization approaches, in order to identfy those that are the best fitted to the proposed transformation approach. We will also investigate digital objects that correspond to limit cases, just beyond the domain of validity of quasi-1regularity; indeed, some of these objects (often thin, or small-sized) may preserve some topological properties, although not being quasi-1-regular. Third, we will explore more deeply the notions of regularity. In particular, we will aim at proposing a notion that may encompass both the notions of Pavlidis' r-regularity and of quasi-r-regularity. Such notion could allow us to better understand -and handle-the intrinsic mechanisms of topology-preserving digitization, in various regular grids, adjacency models and space dimensions. An online demonstration based on the DGtal library [START_REF]DGtal: Digital geometry tools and algorithms library[END_REF] is available online4 . Fig. 15 Area (left) and perimeter (right) variations induced by successive rigid motions for the disk of radius 10 of Table 1. See Section 6.3. Fig. 20 Area (left) and perimeter (right) evolution of the three digital objects X 1 , X 2 and X 3 (see Fig. 19), under successive rigid motions T P oint and T P oly . See Section 6.2.

Fig. 2 (

 2 Fig.2(a) X ⊂ Z 2 (in grey) is neither connected, nor wellcomposed. (b) X is 8-connected, but neither 4-connected nor well-composed. (c) X is 4-connected and well-composed.

Fig. 3

 3 Fig.3Examples of non-injectivity and non-surjectivity of rigid motions followed by a digitization. (a) The square grid of Z 2 and the associated Voronoi cell boundaries. (b) Rigid motion followed by a digitization applied on the square grid of (a); the red and blue pixels correspond to non-surjectivity and non-injectivity cases, respectively.

Fig. 5

 5 Fig. 5 Examples of quasi-1-regular (a) and non-quasi-1-regular (b,c,d) objects X: (b) X ⊆ (X B 1 ) ⊕ B √ 2 ; (c) X B 1 is not connected; (d) X B 1 is not connected. The objects X ⊂ R 2 arein blue, the disks B 1 are in red and the disks B √ 2 are in black, the erosions X B 1 are in red and the openings (X B 1 ) ⊕ B √ 2 are in green.

Fig. 6 2 ,

 62 Fig. 5 Examples of quasi-1-regular (a) and non-quasi-1-regular (b,c,d) objects X: (b) X ⊆ (X B 1 ) ⊕ B √ 2 ; (c) X B 1 is not connected; (d) X B 1 is not connected. The objects X ⊂ R 2 arein blue, the disks B 1 are in red and the disks B √ 2 are in black, the erosions X B 1 are in red and the openings (X B 1 ) ⊕ B √ 2 are in green.

Fig. 8 A

 8 Fig.8A digital H-convex object X of Z 2 (black dots and grey pixels). (a) The half-plane representation of X, depicted by the 5 red support lines. The red points/pixels are those required to define these closed half-spaces. (b) The convex hull Conv(X) in R 2 , defined as the polygon whose vertices are these red points.

Fig. 10 (

 10 Fig.10(a) Tangential cover (in red) of a contour curve[START_REF] Feschet | Optimal time computation of the tangent of a discrete curve: Application to the curvature[END_REF], composed of the sequence of its maximal discrete straight segments, and dominant points (in green) detected by using the tangential cover[START_REF] Nguyen | A discrete geometry approach for dominant point detection[END_REF][START_REF] Ngo | Efficient dominant point detection based on discrete curve structure[END_REF]. (b) Polygon of dominant points (in blue). (c) Polygon of the contour curve (in purple) and its vertices (in yellow), obtained from (b), such that it encloses all contour points and does not contain any point outside of the contour curve.

Fig. 11

 11 Fig. 11 Experiments on convexity preservation for rigid motions T P oint , T Conv and T P oly , with rotation angle of π 10 and translation of (t x , t y ) = (0.1, 0.2). See Sec. 6.2.

Fig. 12

 12 Fig. 12 Polygon (in blue) and convex hull (in red) of the digital object X of Fig. 11(a).

Figs. 15

 15 Figs.[START_REF] Rosenfeld | Adjacency in digital pictures[END_REF] and 16 show results under rigid motions generated randomly with rotation angles θ ∈ [0, 2π) and translation values t 1 , t 2 ∈ [0, 1). The results are similar to those of Figs. 13 and 14. The difference is that the peaks at the special angles of π 2 k for T Conv are not seen in Figs. 15 and 16 since random rigid motions are applied.

2

 2

Fig. 16 3 Fig. 17 Fig. 18 3 Fig. 19

 1631718319 Fig. 16 Area (left) and perimeter (right) variations induced by successive rigid motions for the square of size 21 × 21 of Table2. See Section 6.3.

This definition of r-regularity can be equivalently expressed as the invariance of X with respect to both opening and closing by a structuring element defined as a close ball of radius r. This mathematical morphology analogy will be given in Section 3.

Kim introduced in [25] the definition of cellular convexity and proved the equivalence to the one using the convex hull[START_REF] Kim | On the cellular convexity of complexes[END_REF] Lemma 10]. In[START_REF] Eckhardt | Digital lines and digital convexity[END_REF], Eckhardt reformulated and renamed this notion H-convexity.

http://ipol-geometry.loria.fr/ ~phuc/ipol_demo/ RigidMotion2D

Acknowledgments

We would like to thank the anonymous referees for their valuable comments. In particular, we are especially grateful to referee 3, who pointed out an improved definition of quasi-r-regularity.

This work was partly funded by the French Agence Nationale de la Recherche, grant agreement ANR-15-CE40-0006 (CoMeDiC, https://lama.univ-savoie. fr/comedic), by the French Programme d'Investissements d'Avenir (LabEx Bézout, ANR-10-LABX-58), and by a mobility grant from the French Groupe de Recherche IGRV (CNRS).