Geometric Preservation of 2D Digital Objects Under Rigid Motions

Abstract

Rigid motions (i.e. transformations based on translations and rotations) are simple, yet important, transformations in image processing. In $\mathbb {R}^n$, they are both topology and geometry preserving. Unfortunately, these properties are generally lost in $\mathbb {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 $\mathbb {Z}^2$. In this article, we also focus on geometric issues in $\mathbb {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 $\mathbb {R}^2$ and (3) a digitization step for recovering a result within $\mathbb {Z}^2$. The intermediate modeling of a digital object of $\mathbb {Z}^2$ as a piecewise affine object of $\mathbb {R}^2$ allows us to avoid the geometric alterations generally induced by standard pointwise rigid motions. However, the final digitization of the polygon back to $\mathbb {Z}^2$ has to be carried out cautiously. In particular, our second, theoretical contribution is a notion of quasi-regularity that provides sufficient conditions to be fulfilled by a continuous object for guaranteeing both topology and geometry preservation during its digitization.

1 Introduction

Image processing and computer vision applications often require manipulation of discrete models of images. Among various existing discrete models (e.g. meshes, point clouds), digital images, defined as finite sets of points on $\mathbb {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 $\mathbb {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 [1]) or to fit a given model onto a structure of interest (e.g. for segmentation [2]). 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 of 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 shape, this is indeed the case in the Euclidean model currently used for our physical world. In $\mathbb {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 $\mathbb {Z}^n$, that implies a non-continuous behavior of rigid motions [3]. In other words, when applying a rigid motion operator ${{\mathfrak {T}}}$ on a digital point $\mathsf {p} \in \mathbb {Z}{}^n$, the resulting value ${{\mathfrak {T}}}(\mathsf {p})$ generally lies out of $\mathbb {Z}{}^n$. It is then necessary to find a way for carrying ${{\mathfrak {T}}}(\mathsf {p})$ back to $\mathbb {Z}^n$. The induced approximation may lead to altering the topological structure of the object $\mathsf {X}$ containing $\mathsf {p}$. It may also modify the global shape of $\mathsf {X}$ by slightly moving its different points in a heterogeneous way [4].

In the case of $\mathbb {Z}{}^2$, some strategies were recently investigated for providing topological guarantees when applying a rigid motion on digital objects [5, 6]. 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 $\mathsf {p}$ of $\mathsf {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(\mathsf {X})$ of the object $\mathsf {X}$ of $\mathbb {Z}{}^2$. More precisely, we propose to define $P(\mathsf {X})$ as a polygon modeling the general shape of the digital boundary of $\mathsf {X}$. Such a polygon, as a piecewise affine object of $\mathbb {R}{}^2$, can be processed in a topology and geometry preserving way by the transformation ${{\mathfrak {T}}}$. The main issue remaining to be tackled is then related to the digitization of the polygon ${{\mathfrak {T}}}(P(\mathsf {X}))$ back to $\mathbb {Z}^2$. Such digitization problem is related to pioneering works [7] developed by Pavlidis in the 1980s. However, while Pavlidis was interested in the digitization of “smooth” objects, i.e. objects of $\mathbb {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 [8]. A first contribution, in Sect. 3, is a sufficient condition for guaranteeing the preservation of connectedness during the process of digitization of an object of $\mathbb {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 [7]. 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 Sect. 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 Sect. 5, we consider, more generally, the case of well-composed objects, not necessarily convex. We also show that under the condition 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 Sect. 7. In order to make this work self-contained, we recall, in Sect. 2, some basic definitions and notations related to rigid motions, and various notions of regularity on digital images.

2 Rigid Motions and Digitization

2.1 Rigid Motions on $\mathbb {R}^2$

A rigid motion ${{\mathfrak {T}}}$ in the Euclidean space $\mathbb {R}^2$ is defined, for any point $\mathbf {x} = (x_1,x_2)^T \in {\mathbb {R}}^2$ as

$$\begin{aligned} {{\mathfrak {T}}}(\mathbf {x}) = \left( \begin{array}{l} \cos \theta ~-\sin \theta \\ \sin \theta ~~~~\cos \theta \end{array}\right) \left( \begin{array}{c} x_1 \\ x_2 \end{array} \right) + \left( \begin{array}{c} t_1 \\ t_2 \end{array} \right) \end{aligned}$$

(1)

where $\theta \in [0, 2\pi )$ is a rotation angle, and $(t_1,t_2)^T \in \mathbb {R}^2$ is a translation vector.

Let ${ X }$ be a continuous object in the Euclidean space $\mathbb {R}^2$. (In the sequel, we will implicitly consider that ${ X }$ is bounded and connected.) The transformation ${{\mathfrak {T}}}$ is bijective, isometric and orientation-preserving. Then, the transformed object ${{\mathfrak {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 $\mathbb {Z}^2$ from rigid motions on $\mathbb {R}^2$.

2.2 Digitization and Topology Preservation

A digital object $\mathsf {X} \subset \mathbb {Z}{}^2$ is generally the result of a digitization process applied on a continuous object ${ X }\subset \mathbb {R}{}^2$. (In the sequel, we will implicitly consider that $\mathsf {X}$ is a finite subset of $\mathbb {Z}^2$, which can be given as an image segmentation result in practice.) We consider the Gauss digitization [9], which is simply the intersection of a continuous object ${ X }$ with $\mathbb {Z}^2$

$$\begin{aligned} \mathsf {X}= { X }\cap \mathbb {Z}^2 \end{aligned}$$

(2)

The object $\mathsf {X}$ is a subset of $\mathbb {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 $\mathsf {X}$ within $\mathbb {R}^2$. Based on these different models, the structure of $\mathsf {X}$ can be defined in various topological frameworks which are mainly equivalent [10] to that of digital topology [11]. However, this digital topology of $\mathsf {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 the Gauss digitization, to a disconnected digital object $\mathsf {X}$.

Fig. 1

a A continuous object ${ X }$ in $\mathbb {R}{}^2$. b A Gauss digitization of ${ X }$, leading to the definition of $\mathsf {X}$ which is composed by the black points of $\mathbb {Z}^2$ within ${ X }$. c The digital object $\mathsf {X}$ represented as a set of pixels. The objects ${ X }$ and $\mathsf {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 }$

In the literature, various studies proposed conditions for guaranteeing the preservation of topology of digitized objects [12,13,14]. In particular, in [7] Pavlidis introduced the notion of r-regularity.

Definition 1

(r-regularity) An object ${ X }\subset \mathbb {R}^2$ is r-regular if for each boundary point of ${ X }$, there exist two tangent open disks of radius r, lying entirely in ${ X }$ and its complement $\overline{{ X }}$, respectively.¹

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 $\mathsf {X}$, for a dense sampling.

Proposition 1

([7]) An r-regular object ${ X }\subset \mathbb {R}^2$ has the same topological structure as its digitized version $\mathsf {X} = { X }\cap \mathbb {Z}^2$ if $r \ge \frac{\sqrt{2}}{2}$.

Remark 1

In [7], “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 [15,16,17].

It was shown that the digitization process of an r-regular object yields a well-composed object [13], whose definition relies on standard concepts of digital topology, recalled hereafter, for the sake of completeness.

Two distinct points ${{\mathsf {p}}}, {{\mathsf {q}}}\in \mathbb {Z}^2$, are k-adjacent if

$$\begin{aligned} \Vert {{\mathsf {p}}}- {{\mathsf {q}}}\Vert _{\ell } \le 1 \end{aligned}$$

(3)

with $k=4$ (resp. 8) when $\ell = 1$ (resp. $\infty$). From the reflexive–transitive closure of the k-adjacency relation on a finite subset $\mathsf {X} \subset \mathbb {Z}^2$, we derive the k-connectivity relation on $\mathsf {X}$. It is an equivalence relation, whose equivalence classes are called the k-connected components of $\mathsf {X}$. Due to paradoxes related to the discrete version of the Jordan theorem [18], dual adjacencies are used for $\mathsf {X}$ and its complement $\overline{\mathsf {X}}$, namely (4, 8)- or (8, 4)-adjacencies [19].

The notion of well-composedness [20] 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 $\mathsf {X} \subset \mathbb {Z}^2$ is well-composed if each 8-connected component of $\mathsf {X}$ and of its complement $\overline{\mathsf {X}}$ is also 4-connected.

This definition implies that the boundary² of $\mathsf {X}$ is a set of 1-manifolds whenever $\mathsf {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 }\subset \mathbb {R}^2$ is r-regular, with $r \ge \frac{\sqrt{2}}{2}$, then $\mathsf {X} = { X }\cap \mathbb {Z}^2$ is a well-composed digital object.

Fig. 2

a$\mathsf {X} \subset \mathbb {Z}^2$ (in gray) is neither connected nor well-composed. b$\mathsf {X}$ is 8-connected, but neither 4-connected nor well-composed. c$\mathsf {X}$ is 4-connected and well-composed

Fig. 3

Examples of non-injectivity and non-surjectivity of rigid motions followed by a digitization. a The square grid of $\mathbb {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 (Color figure online)

2.3 Digitized Rigid Motions

If we straightforwardly apply a rigid motion ${{\mathfrak {T}}}$, such as defined in Eq. (1), to a digital object $\mathsf {X} \subset \mathbb {Z}^2$, we generally obtain a transformed object ${{\mathfrak {T}}}(\mathsf {X}) \not \subset \mathbb {Z}^2$. In order to obtain a result in $\mathbb {Z}^2$, we further need a digitization operator

$$\begin{aligned} {{\mathfrak {D}}}: \mathbb {R}^2 \rightarrow \mathbb {Z}^2 \end{aligned}$$

(4)

which can be, for instance, the standard rounding function. Then, a digital analogue of ${{\mathfrak {T}}}$ can be defined as the composition of ${{\mathfrak {T}}}$, (restricted to $\mathbb {Z}{}^2$) with such digitization operator, i.e. ${{\mathfrak {D}}}\circ {{\mathfrak {T}}}_{\mid \mathbb {Z}^2}$.

As stated above, rigid motions on $\mathbb {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 ${{\mathfrak {T}}}$ on $\mathbb {Z}^2$ by setting

$$\begin{aligned} {{\mathcal {T}}}_{Point}^{-1} = {{\mathfrak {D}}}\circ {{\mathfrak {T}}}^{-1}_{\mid \mathbb {Z}^2} \end{aligned}$$

(5)

In other words, we use a backward model for the computation of the rigid motion of a digital object $\mathsf {X}$. Indeed, we consider that the object ${{\mathcal {T}}}_{Point}(\mathsf {X}) \subset \mathbb {Z}{}^2$ induced by the digitized version of the rigid motion ${{\mathfrak {T}}}$ is defined such that

$$\begin{aligned} \mathsf {p} \in {{\mathcal {T}}}_{Point}(\mathsf {X}) \Leftrightarrow {{\mathcal {T}}}_{Point}^{-1}(\mathsf {p}) \in \mathsf {X} \end{aligned}$$

(6)

2.4 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(\mathsf {X}) \subset \mathbb {R}{}^2$ the continuous object obtained as the union of the closed Voronoi cells associated to the points of $\mathsf {X}$; in other words, let us consider the digital object as its set of pixels. Then, the transformed digital object ${{\mathcal {T}}}_{Point}(\mathsf {X})$ is obtained as the Gauss digitization of the transformed object resulting from the rigid motion of $V(\mathsf {X})$ by ${{\mathfrak {T}}}$. More formally, we have

$$\begin{aligned} {{\mathcal {T}}}_{Point}(\mathsf {X}) = {{\mathfrak {T}}}(V(\mathsf {X})) \cap \mathbb {Z}^2 \end{aligned}$$

(7)

Note that this is equivalent to Eqs. (5) and (6).

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(\mathsf {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 [6], where it led to the definition of a notion of digital regularity (simply called regularity in [6]). Digital regularity provides a sufficient condition for guaranteeing that a well-composed digital object $\mathsf {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. (5–7), 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.

Fig. 4

Geometry and topology alterations induced by digitized rigid motions. a A well-composed object, in gray. 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 ${{\mathcal {T}}}_{Point}$ 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 non-digital regularity in these areas (Color figure online)

2.5 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 pointwise fashion.

To this end, we propose to represent a digital object of $\mathbb {Z}^2$ as a digitization of a continuous object, namely a polygon of $\mathbb {R}^2$. This strategy has several advantages. First, it allows us to apply any rigid motion in $\mathbb {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 a polygonization process. In particular, this means that a digitally convex object of $\mathbb {Z}^2$ will lead to a convex polygon. In that case, we will choose as a relevant polygon model its convex hull. In other cases, a polygon will be made depending on users polygonization policy.

Based on these hypotheses, we propose, as a first contribution, an algorithmic framework for rigid motion of digital objects in $\mathbb {Z}^2$. It relies on three successive steps: (1) polygonization of a digital object; (2) transformation of an intermediate piecewise affine object (polygon) of $\mathbb {R}^2$; and (3) digitization of the transformed polygon for recovering a result within $\mathbb {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 is correctly preserved. More precisely, such an observation can be done qualitatively and quantitatively, in which geometric properties, for example area and perimeter, are measured.

Generally, preserving the geometry also implies to preserve the topology. This implication is mostly offered in $\mathbb {R}^2$, while it is hardly obtained in $\mathbb {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 Sects. 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.

Fig. 5

Examples of quasi-1-regular (a) and non-quasi-1-regular (b–d) objects ${ X }$: b${ X }\not \subseteq ({ X }\ominus B_1) \oplus B_{\sqrt{2}}$; c${ X }\ominus B_1$ is not connected; d$\overline{{ X }} \ominus B_1$ is not connected. The objects ${ X }\subset \mathbb {R}^2$ are in blue, some disks $B_1$ and $B_{\sqrt{2}}$ are in red and gray, respectively, the erosion ${ X }\ominus B_1$ are in red, and the opening whose centers are in the erosion $({ X }\ominus B_1) \oplus B_{\sqrt{2}}$ are in green (Color figure online)

3 Quasi-r-Regularity

In order to make this article self-contained, let us first recall some notations and a few mathematical morphology notions [12, 21, 22]. We denote by $\oplus$ and $\ominus$ the classical operators of dilation and erosion, corresponding to the Minkowski addition, and its associated subtraction

$$\begin{aligned} X \oplus Y&= \bigcup _{y \in Y} X_y = \bigcup _{x \in X} Y_x \end{aligned}$$

(8)

$$\begin{aligned} X \ominus Y&= \bigcap _{y \in Y} X_{-y} \end{aligned}$$

(9)

where $X_y = \{x + y \mid x \in X\}$ and, in our case, $X, Y \subset \mathbb {R}^2$. We also denote by $\circ$ the composition of erosion and dilation, that is

$$\begin{aligned} X \circ Y = (X \ominus Y) \oplus Y \end{aligned}$$

(10)

We denote by $B_r$ a closed disk of $\mathbb {R}^2$ of radius $r > 0$ and centered on $(0,0) \in \mathbb {R}^2$.

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

Definition 3

(Quasi-r-regularity) Let $r > 0$. Let ${ X }\subset \mathbb {R}^2$ be a bounded, simply connected (i.e. connected and with no hole) object. We say that ${ X }$ is quasi-r-regular if it satisfies the following four properties:

• $X \ominus B_r$ is non-empty and connected;

• ${\overline{X}} \ominus B_r$ is connected;

• $X \subseteq ( X \ominus B_r ) \oplus B_{r\sqrt{2}}$; and

• ${\overline{X}} \subseteq ( {\overline{X}} \ominus B_r ) \oplus B_{r\sqrt{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 quasi-r-regularity and of Pavlidis’ r-regularity, we rewrite hereafter the definition of r-regularity of a bounded, simply connected object $X \subset \mathbb {R}^2$: X is r-regular if:

• $X \ominus B_r$ is non-empty and connected;

• ${\overline{X}} \ominus B_r$ is connected;

• $X = (X \ominus B_r ) \oplus B_r$; and

• ${\overline{X}} = ( {\overline{X}} \ominus B_r ) \oplus B_r$.

In particular we observe that the principal difference between both notions is the fact that the matching between X (resp. $\overline{X}$) and its opening need to be perfect in the case of r-regularity, while a “margin” $(\sqrt{2}-1)r$ is authorized in the case of quasi-r-regularity, which allows X to have 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 Sect. 7.

Proposition 3

If X is quasi-1-regular, then $\mathsf {X} = X \cap \mathbb {Z}^2$ and ${\overline{\mathsf {X} }} = {\overline{X}} \cap \mathbb {Z}^2$ are both 4-connected. In particular, $\mathsf {X}$ is then well-composed.

Proof

We prove the 4-connectedness of $\mathsf {X}$; the same reasoning holds for ${\overline{\mathsf {X}}}$. Let us first prove that $(X \circ B_1) \cap \mathbb {Z}^2$ is 4-connected. Let ${{\mathsf {p}}}$ and ${{\mathsf {q}}}$ be two distinct points of $(X \circ B_1) \cap \mathbb {Z}^2$. Let $B^{{\mathsf {p}}}_1$ and $B^{{\mathsf {q}}}_1$ be two disks of radius 1, included in $X \circ B_1$ and such that ${{\mathsf {p}}}\in B^{{\mathsf {p}}}_1$ and ${{\mathsf {q}}}\in B^{{\mathsf {q}}}_1$. (Such disks exist, from the definition of opening.) Let $b_{{\mathsf {p}}}$ and $b_{{\mathsf {q}}}$ be the centers of $B^{{\mathsf {p}}}_1$ and $B^{{\mathsf {q}}}_1$, respectively. We have $b_{{\mathsf {p}}}, b_{{\mathsf {q}}}\in X \ominus B_1$, from the definition of erosion. Since $X \ominus B_1$ is connected in $\mathbb {R}^2$, there exists a continuous path $\varPi$ from $b_{{\mathsf {p}}}$ to $b_{{\mathsf {q}}}$ in $X \ominus B_1$. Note that for any disk $B_1$, we always have $B_1 \cap \mathbb {Z}^2$ non-empty and 4-connected; in particular it contains at least two points of $\mathbb {Z}^2$. For a value $\varepsilon > 0$ small enough, two disks $B_1$ and $B'_1$ with centers distant of $\varepsilon$ are such that $B_1 \cap B'_1 \cap \mathbb {Z}^2 \ne \emptyset$. As a consequence, the union $\bigcup _{b \in \varPi } B_1(b) \cap \mathbb {Z}^2$ (with $B_1(b)$ the disk of center b) is a 4-connected set of $\mathbb {Z}^2$. In addition, we have ${{\mathsf {p}}}, {{\mathsf {q}}}\in \bigcup _{b \in \varPi } B_1(b) \cap \mathbb {Z}^2$. Then, ${{\mathsf {p}}}$ and ${{\mathsf {q}}}$ are 4-connected in $(X \circ B_1) \cap \mathbb {Z}^2$, and it follows that $(X \circ B_1) \cap \mathbb {Z}^2$ is a 4-connected set. Let us now prove that any point ${{\mathsf {r}}}\in X {\setminus } (X \circ B_1)$$\cap \mathbb {Z}^2$ is 4-adjacent to a point of $(X \circ B_1) \cap \mathbb {Z}^2$. Let us consider such a point ${{\mathsf {r}}}\in \mathbb {Z}^2$. We have ${{\mathsf {r}}}\in X \subseteq X \ominus B_1 \oplus B_{\sqrt{2}}$. Then, from the definition of dilation, there exists $b \in X \ominus B_1$ such that b is the center of the disk $B_{\sqrt{2}}(b)$ of radius $\sqrt{2}$, and ${{\mathsf {r}}}$ is a point in that disk. In particular, the distance between b and ${{\mathsf {r}}}$ lies in $(1,\sqrt{2}]$. As b is a point of $X \ominus B_1$, it is also the center of a disk $B_1(b)$ of radius 1 included in $X \circ B_1$. Let us consider the circle $C_1({{\mathsf {r}}})$ of radius 1 and center ${{\mathsf {r}}}$. This circle $C_1({{\mathsf {r}}})$ intersects $B_1(b)$, and this intersection is a circular segment of radius 1 and angle $\alpha \in [\frac{\pi }{2},\frac{2\pi }{3})$, included in $X \circ B_1$; in particular, we have $\alpha \ge \frac{\pi }{2}$ (see Fig. 6).

Then, this segment necessarily contains a point ${{\mathsf {t}}}\in \mathbb {Z}^2$, that lies in $(X \circ B_1) \cap \mathbb {Z}^2$. The points ${{\mathsf {r}}}$ and ${{\mathsf {t}}}$ are 4-adjacent. It follows that $X \cap \mathbb {Z}^2$ is 4-connected. $\square$

Fig. 6

Illustration for the proof of Prop. 3. a A part of object $X \subset \mathbb {R}^2$ is in blue; the erosion $X \ominus B_1$ is in red and the opening $(X \ominus B_1) \oplus B_{\sqrt{2}}$ is in green; the disk $B_1(b)$ is in red; and the circle $C_1(r)$ is in black. b The intersection of the circle $C_1(r)$ (in black) and the disk $B_1(b)$ (in red) is a circular segment of radius 1 and angle $\alpha$ such that $\cos (\frac{\alpha }{2})= \frac{d(r,b)}{2}$, where d(r, b) is the Euclidean distance between r and b. Since $d(r,b) \in (1,\sqrt{2}]$, we have $\alpha \in [\frac{\pi }{2},\frac{2\pi }{3})$ (Color figure online)

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.

4 Rigid Motions of Digitally Convex Objects

In this section, we first deal with a specific case of digital objects, namely convex ones. For rigid motion purpose, we build a continuous polygon corresponding to the convex hull of an input digital object. Then, we move this continuous polygon, and 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.

4.1 Digital Convexity

In the Euclidean space $\mathbb {R}^2$, an object ${ X }$ is said to be convex if, for any pair of points ${{x}}, {{y}}\in { X }$, the line segment joining ${{x}}$ and ${{y}}$

$$\begin{aligned}{}[{{x}}, {{y}}] = \{ \lambda {{x}}+ (1 - \lambda ) {{y}}\in \mathbb {R}^2 \mid 0 \le \lambda \le 1 \} \end{aligned}$$

(11)

is included in ${ X }$. However, this intuitive continuous notion cannot be directly transposed to digital objects in $\mathbb {Z}^2$. Indeed, given a digital object $\mathsf {X}$ in $\mathbb {Z}^2$, for ${{\mathsf {p}}}, {{\mathsf {q}}}\in \mathsf {X}$ we have $[{{\mathsf {p}}}, {{\mathsf {q}}}] \not \subset \mathbb {Z}^2$ if ${{\mathsf {p}}}\ne {{\mathsf {q}}}$.

In order to tackle this problem, various extensions of the notion of convexity have been proposed for $\mathbb {Z}^2$. We can cite, for instance: MP-convexity [23] which is a straightforward extension of the continuous notion; S-convexity [24] which uses convex objects in $\mathbb {R}^2$ to determine the convexity of objects in $\mathbb {Z}^2$; H-convexity³ [25, 26] which is a geometrical version of S-convexity, using the convex hull of digital objects; and D-convexity [27] 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 [25, Theorem 5]. Similar results under the assumption of 8-adjacency can be found in [26], via the chord property, which relate the MP-, H- and D-convexities. Under the condition that $\mathsf {X}$ has no isolated point (i.e. no point adjacent to other point within $\mathsf {X}$), it was then proved that $\mathsf {X}$ is H-convex iff it is S-convex [25, Theorem 4]. A more complete description on various notions of digital convexity can be found in [28, 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.

We recall hereafter the definition of the convex hull of a digital object $\mathsf {X} \subset \mathbb {Z}{}^2$, denoted by ${\mathcal Conv}(\mathsf {X})$:

$$\begin{aligned} {\mathcal Conv}(\mathsf {X}) = \biggr \{&{{x}}= \sum _{i=1}^{|\mathsf {X} |} \lambda _i {{\mathsf {p}}}_i \in \mathbb {R}^2 \; \biggr \vert \; \sum _{i=1}^{|\mathsf {X} |} \lambda _i = 1\nonumber \\&\wedge \forall i \in \{1,\ldots ,|\mathsf {X} |\}, (\lambda _i \ge 0 \wedge {{\mathsf {p}}}_i \in \mathsf {X}) \biggr \} \end{aligned}$$

(12)

Definition 4

(H-convexity [26]) A digital object $\mathsf {X} \subset \mathbb {Z}^2$ is H-convex if

$$\begin{aligned} \mathsf {X} = {\mathcal Conv}(\mathsf {X}) \cap \mathbb {Z}^2 \end{aligned}$$

(13)

i.e. if $\mathsf {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.

Fig. 7

A digital object $\mathsf {X}$ that is H-convex, but not connected. This is due, here, to the acute angle at the highest vertex of the convex hull ${\mathcal Conv}(\mathsf {X})$ that allows the induced polygon to “pass between” two 4-adjacent points of the background of $\mathsf {X}$ (Color figure online)

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

Property 1

Let $\mathsf {X}$ and $\mathsf {Y}$ be two digital objects in $\mathbb {Z}^2$. If $\mathsf {X}$ and $\mathsf {Y}$ are H-convex, then $\mathsf {X} \cap \mathsf {Y}$ is H-convex.

Proof

Let $\mathsf {X}$ and $\mathsf {Y}$ be two H-convex digital objects. We have $\mathsf {X} = {\mathcal Conv}(\mathsf {X}) \cap \mathbb {Z}^2$ and $\mathsf {Y} = {\mathcal Conv}(\mathsf {Y}) \cap \mathbb {Z}^2$. Then, it comes $\mathsf {X} \cap \mathsf {Y} = {\mathcal Conv}(\mathsf {X}) \cap {\mathcal Conv}(\mathsf {Y}) \cap \mathbb {Z}^2$. It is plain that ${\mathcal Conv}(\mathsf {X} \cap \mathsf {Y}) \subseteq {\mathcal Conv}(\mathsf {X}) \cap {\mathcal Conv}(\mathsf {Y})$ and then we have ${\mathcal Conv}(\mathsf {X} \cap \mathsf {Y}) \cap \mathbb {Z}^2 \subseteq {\mathcal Conv}(\mathsf {X}) \cap {\mathcal Conv}(\mathsf {Y}) \cap \mathbb {Z}^2$. Now, let us consider ${{\mathsf {p}}}\in {\mathcal Conv}(\mathsf {X}) \cap {\mathcal Conv}(\mathsf {Y}) \cap \mathbb {Z}^2$. We have ${{\mathsf {p}}}\in {\mathcal Conv}(\mathsf {X}) \cap \mathbb {Z}^2 = \mathsf {X}$ and ${{\mathsf {p}}}\in {\mathcal Conv}(\mathsf {Y}) \cap \mathbb {Z}^2 = \mathsf {Y}$. Then, we have ${{\mathsf {p}}}\in \mathsf {X} \cap \mathsf {Y} \subseteq Conv(\mathsf {X} \cap \mathsf {Y})$. But since ${{\mathsf {p}}}\in \mathbb {Z}^2$, it comes ${{\mathsf {p}}}\in Conv(\mathsf {X} \cap \mathsf {Y}) \cap \mathbb {Z}^2$. Consequently, we have ${\mathcal Conv}(\mathsf {X} \cap \mathsf {Y}) \cap \mathbb {Z}^2 = {\mathcal Conv}(\mathsf {X}) \cap {\mathcal Conv}(\mathsf {Y}) \cap \mathbb {Z}^2$. $\square$

4.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 $\mathsf {X}$ consists of computing its convex hull.

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

$$\begin{aligned} {\mathcal Conv}(\mathsf {X}) = \bigcap _{{\mathrm H}\in {{\mathcal {R}}}(\mathsf {X})} {\mathrm H}\end{aligned}$$

(14)

where ${{\mathcal {R}}}(\mathsf {X})$ is the smallest set of closed half-planes that include $\mathsf {X}$. This set is finite and sufficient for defining ${\mathcal Conv}(\mathsf {X})$. Each closed half-plane ${\mathrm H}$ of this subset is defined as

$$\begin{aligned} {\mathrm H}= \{ (x,y) \in \mathbb {R}^2 \mid a x + b y + c \le 0 \} \end{aligned}$$

(15)

with $a, b, c \in \mathbb {Z}$ and $\gcd (a,b)=1$. Note that the integer coefficients of ${\mathrm H}$ are obtained by a pair of consecutive vertices of ${\mathcal Conv}(\mathsf {X})$, denoted by ${{\mathsf {u}}}, {{\mathsf {v}}}\in \mathbb {Z}^2$, which are in the clockwise order, such that

$$\begin{aligned} (a, b)&= \frac{1}{\gcd (w_x, w_y)} (-\,w_y, w_x)\end{aligned}$$

(16)

$$\begin{aligned} c&= (a, b) \cdot {{\mathsf {u}}} \end{aligned}$$

(17)

where $(w_x, w_y) = {{\mathsf {v}}}- {{\mathsf {u}}}\in \mathbb {Z}^2$.

Fig. 8

A digital H-convex object $\mathsf {X}$ of $\mathbb {Z}^2$ (black dots and gray pixels). a The half-plane representation of $\mathsf {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 ${\mathcal Conv}(\mathsf {X})$ in $\mathbb {R}^2$, defined as the polygon whose vertices are these red points (Color figure online)

Many algorithms can be used to compute the convex hull of a digital object. In [29], 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 [30] 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 [31] can be used to obtain this decomposition. Alternatively, an approach presented in [32] uses tools of combinatorics on words to study contour words: the linear Lyndon factorization algorithm [33] 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 [34].)

The half-planes can then be deduced from the consecutive vertices of the computed convex hull, from Eqs. (15–17). An example of convex hull and half-plane modeling of an H-convex digital object is illustrated in Fig. 8.

4.3 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 ${{\mathfrak {T}}}$ are rational (see Eq. (1)). More precisely, on the one hand, the rotation matrix R is defined as $\frac{1}{r} \left( \begin{array}{cc} p &{} - \,q \\ q &{} p \end{array} \right)$ where $p, q, r \in \mathbb {Z}$ constitute a Pythagorean triple, i.e. $p^2 + q^2 = r^2$, $r \ne 0$. On the other hand, the translation vector is defined as $(t_1, t_2)^T \in \mathbb {Q}^2$. This assumption is fair, as we can always find rational parameter values as close as desired from any real values [35] for defining such a Pythagorean triple.

A half-plane ${\mathrm H}$, as defined in Eq. (15), is transformed by such (rational) rigid motion ${{\mathfrak {T}}}$ as follows:

$$\begin{aligned} {{\mathfrak {T}}}({\mathrm H}) = \{ (x,y) \in \mathbb {R}^2 \mid \alpha x + \beta y + \gamma \le 0 \} \end{aligned}$$

(18)

where $\alpha , \beta , \gamma \in \mathbb {Q}$ are given by $(\alpha \ \beta )^T = R (a\ b)^T$ and $\gamma = c + \alpha t_1 + \beta t_2$. This leads to a rational half-plane, which can be easily rewritten as an integer half-plane in the form of Eq. (15).

Since an H-convex digital object $\mathsf {X}$ is represented by a finite set of digital half-planes, we can define the rigid motion ${{\mathcal {T}}}_{{\mathcal Conv}}$ of $\mathsf {X}$ on $\mathbb {Z}^2$ via its continuous polygonal convex hull as follows:

$$\begin{aligned} {{\mathcal {T}}}_{{\mathcal Conv}}(\mathsf {X}) = {{\mathfrak {T}}}({\mathcal Conv}(\mathsf {X})) \cap \mathbb {Z}{}^2 = {{\mathfrak {T}}}\biggr ( \bigcap \limits _{{\mathrm H}\in {{\mathcal {R}}}(\mathsf {X})} {\mathrm H}\biggr ) \cap \mathbb {Z}^2 \end{aligned}$$

(19)

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

Note that we have

$$\begin{aligned} {{\mathfrak {T}}}\biggr ( \bigcap \limits _{{\mathrm H}\in {{\mathcal {R}}}(\mathsf {X})} {\mathrm H}\biggr ) \cap \mathbb {Z}^2&= \biggr (\bigcap \limits _{{\mathrm H}\in {{\mathcal {R}}}(\mathsf {X})} {{\mathfrak {T}}}( {\mathrm H}) \biggr ) \cap \mathbb {Z}^2 \nonumber \\&=\bigcap \limits _{{\mathrm H}\in {{\mathcal {R}}}(\mathsf {X})} ({{\mathfrak {T}}}( {\mathrm H}) \cap \mathbb {Z}^2) \end{aligned}$$

(20)

As the digitization of any continuous half-space of $\mathbb {R}{}^2$ is H-convex., from Eqs. (19–20), ${{\mathcal {T}}}_{{\mathcal Conv}}(\mathsf {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 $\mathsf {X}$ be a digital object of $\mathbb {Z}^2$. Let ${{\mathcal {T}}}_{{\mathcal Conv}}$ be the polygon-based rigid motion induced by a rigid motion ${{\mathfrak {T}}}$ with rational parameters. If $\mathsf {X}$ is H-convex, then ${{\mathcal {T}}}_{{\mathcal Conv}}(\mathsf {X} )$ is H-convex.

The polygon corresponding to the convex hull of ${{\mathcal {T}}}_{{\mathcal Conv}}(\mathsf {X})$ is not equal, in general, to the transformed convex hull of $\mathsf {X}$. However, we have the following inclusion relation.

Property 2

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

$$\begin{aligned} {\mathcal Conv}({{\mathcal {T}}}_{{\mathcal Conv}}(\mathsf {X})) \subseteq {{\mathfrak {T}}}({\mathcal Conv}(\mathsf {X})) \end{aligned}$$

(21)

The proof of this property derives from the fact that ${{\mathcal {T}}}_{{\mathcal Conv}}(\mathsf {X}) = {{\mathfrak {T}}}({\mathcal Conv}(\mathsf {X})) \cap \mathbb {Z}^2$. Thus we have ${{\mathcal {T}}}_{{\mathcal Conv}}(\mathsf {X}) \subseteq {{\mathfrak {T}}}({\mathcal Conv}(\mathsf {X}))$, and this inclusion also holds for the convex hull of ${{\mathcal {T}}}_{{\mathcal Conv}}(\mathsf {X})$.

Fig. 9

A sequence of transformations ${{\mathcal {T}}}_{{\mathcal Conv}}$ on an H-convex object $\mathsf {X}$. The convex hull of ${{\mathcal {T}}}_{{\mathcal Conv}}(\mathsf {X})$ is included in the transformed convex hull of $\mathsf {X}$, and the cardinality of ${{\mathcal {T}}}_{{\mathcal Conv}}(\mathsf {X})$ is lower than that of $\mathsf {X}$ (Color figure online)

First, this means that the cardinality of ${{\mathcal {T}}}_{{\mathcal Conv}}(\mathsf {X})$ is lower (often strictly) than that of $\mathsf {X}$. In other words, ${{\mathcal {T}}}_{{\mathcal Conv}}$ is a decreasing operator with respect to the cardinality of input digital object. A straightforward consequence is that ${{\mathcal {T}}}_{{\mathcal 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 H-convexity of the digital objects is preserved, which was the fundamental property digital satisfy. These facts are exemplified in Fig. 9 and experimentally observed in Sect. 6.

4.4 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 $\mathbb {R}{}^2$, the continuous definition of convexity intrinsically implies connectedness. By contrast, in $\mathbb {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 $\mathsf {X}$, composed of 8 points/pixels, is H-convex. Indeed, its convex hull contains only digital points that belong to $\mathsf {X}$. However, $\mathsf {X}$ is not connected (with neither 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 objects—when performing rigid transformations of a digital object, it is desirable to also provide topology guarantees, and more precisely connectedness guarantees.

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

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

Proposition 5

Let $\mathsf {X} \subset \mathbb {Z}^2$ be an H-convex digital object. If ${\mathcal Conv}(\mathsf {X} )$ is quasi-1-regular, then ${{\mathcal {T}}}_{{\mathcal Conv}}(\mathsf {X} )$ is H-convex, 4-connected and well-composed.

Proof

Let $\mathsf {X} \subset \mathbb {Z}^2$ be an H-convex digital object, and let us suppose that ${\mathcal Conv}(\mathsf {X})$ is quasi-1-regular. Then, from Prop. 4, ${{\mathcal {T}}}_{{\mathcal Conv}}(\mathsf {X})$ is H-convex. In addition, since ${\mathcal Conv}(\mathsf {X})$ is quasi-1-regular, then so is ${{\mathfrak {T}}}({\mathcal Conv}(\mathsf {X}))$. Thus, from Proposition 3 we deduce that ${{\mathfrak {T}}}({\mathcal Conv}(\mathsf {X})) \cap \mathbb {Z}^2 = {{\mathcal {T}}}_{{\mathcal Conv}}(\mathsf {X})$ is 4-connected and well-composed. $\square$

Remark 5

If ${\mathcal Conv}(\mathsf {X})$ is quasi-1-regular, then the initial object $\mathsf {X}$ is also 4-connected and well-composed.

5 Rigid Motions of General Digital Objects

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

5.1 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 [36, 37], invertible methods enable us to compute Euclidean polygons whose digitization is equal to the original discrete contour. These methods use the Vittone algorithm [38] in the preimage space for straight line recognition. In [39,40,41,42] the arithmetical recognition algorithm [30] is used to decompose a discrete contour and deduce a polygonal representation. These methods rely on the tangential cover of the contour [31], composed of the sequence of its maximal discrete straight segments. It was proved in [39] 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 [40,41,42], 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 [43, 44] 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 [45] 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 [46] to compute the polygonal simplification of a curve such that the Fréchet distance [47] 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(\mathsf {X})$ computed for a digital object $\mathsf {X}$ has to be coherent with respect to digitization, i.e. $P(\mathsf {X}) \cap \mathbb {Z}^2 = \mathsf {X}$. A second important property, in our framework of discrete geometry and exact computation, is that the vertices of $P(\mathsf {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 [43, 44] in the experiment section (Sect. 6) in which it guarantees the above two properties. Some other relevant, but sometimes antagonistic, properties are discussed in Sect. 5.3.

5.2 Rigid Motion of a Polygon

As $P(\mathsf {X})$ may be non-convex, we cannot use the half-plane representation, as it was done in Sect. 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(\mathsf {X})$ are integer (or rational) points, and those of ${{\mathfrak {T}}}(P(\mathsf {X}))$ are rational points, since the rigid motion ${{\mathfrak {T}}}$ is given by a rational matrix and a rational translation vector (see Sect. 4.3).

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

5.3 Digitization of Polygons and Geometry/Topology Preservation

Once the polygon ${{\mathfrak {T}}}(P(\mathsf {X}))$ has been computed, the resulting object, denoted by ${{\mathcal {T}}}_{{\mathcal Poly}}(\mathsf {X})$ can be deduced. Similarly to the case of H-convex digital objects (see Eq. (19)), this is done by embedding ${{\mathfrak {T}}}(P(\mathsf {X}))$ in $\mathbb {Z}^2$ via the Gauss digitization

$$\begin{aligned} {{\mathcal {T}}}_{{\mathcal Poly}}(\mathsf {X}) = {{\mathfrak {T}}}(P(\mathsf {X})) \cap \mathbb {Z}{}^2 \end{aligned}$$

(22)

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

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

Proposition 6

Let $\mathsf {X} \subset \mathbb {Z}^2$ be a digital object. Let $P(\mathsf {X} ) \subset \mathbb {R}^2$ be a polygon such that $P(\mathsf {X} ) \cap \mathbb {Z}^2 = \mathsf {X}$. If $P(\mathsf {X} )$ is quasi-1-regular, then ${{\mathcal {T}}}_{{\mathcal Poly}}(\mathsf {X} )$ is 4-connected and well-composed.

Proof

Let $\mathsf {X} \subset \mathbb {Z}^2$ be a digital object, and let us suppose that $P(\mathsf {X}) \subset \mathbb {R}^2$ is a quasi-1-regular polygon such that $P(\mathsf {X}) \cap \mathbb {Z}^2 = \mathsf {X}$. Then, ${{\mathfrak {T}}}(P(\mathsf {X}))$ is also a quasi-1-regular polygon. From Prop. 3 we deduce that ${{\mathfrak {T}}}(P(\mathsf {X})) \cap \mathbb {Z}{}^2 = {{\mathcal {T}}}_{{\mathcal Poly}}(\mathsf {X})$ is then 4-connected and well-composed. $\square$

Table 1 Experiments on geometry and topology preservation of a disk digitized of radius 10 under rotations of angle $\theta$ (the rotation center is the center of the disk). See Sect. 6.2

Table 2 Experiments on geometry and topology preservation on a square digitized of size $21 \times 21$, under rotations of angle $\theta$ (the rotation center is the barycenter of the square). See Sect. 6.2

Remark 6

Beyond topological guarantees (4-connectedness, well-composedness), the notion of quasi-1-regularity also presents some geometry properties. Indeed, any point of $\mathsf {X}$ is either part of $P(\mathsf {X}) \circ B_1$ (i.e. the “smooth” opening of a polygon) or part of the (noisy) boundary in $P(\mathsf {X}) {\setminus } (P(\mathsf {X}) \circ B_1)$. But, in this second case, this point is necessarily at a distance not greater than $\sqrt{2}-1 < 0,5$ (i.e. the half of a pixel size) from this opening $P(\mathsf {X}) \circ 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 ${{\mathcal {T}}}_{Point}$. This can be illustrated in Tables 1 and 2.

As stated above, $P(\mathsf {X})$ can be defined by following various policies. Then, there exist many (actually an infinite number of) polygons whose digitization leads to $\mathsf {X}$. In particular, it may happen that $P(\mathsf {X})$ is not quasi-1-regular, while $\mathsf {X}$ and ${{\mathcal {T}}}_{{\mathcal Poly}}(\mathsf {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 $\mathbb {Z}^2$, it may be useful that $P(\mathsf {X})$ has an area in $\mathbb {R}^2$ of the same order as the cardinal $|\mathsf {X}|$. This is a heuristic strategy, since we cannot 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 $\mathbb {Z}^2$ has an area of 1 in $\mathbb {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 [48].

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

6 Experiments and Results

In this section, we present some experimental results obtained with the proposed methods on different digital objects, which are convex and non-convex. The comparisons, in terms of topology and geometry—in particular, connectedness, convexity, area and perimeter—between three (resp. two) models of rigid motions ${{\mathcal {T}}}_{Point}, {{\mathcal {T}}}_{Conv}$ and ${{\mathcal {T}}}_{Poly}$ (resp. ${{\mathcal {T}}}_{Point}$ and ${{\mathcal {T}}}_{Poly}$) on convex (resp. non-convex) objects are 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.

6.1 Polygonization of Digital Objects

For an efficient computation of ${{\mathcal {T}}}_{Conv}$, we use the discrete version of the Melkman algorithm [34] 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 ${{\mathcal {T}}}_{Poly}$, for the polygonization of non-convex objects, we apply the method of dominant point detection proposed in [43, 44] with adaptation in order to obtain a result satisfying the two properties: (1) $P(\mathsf {X}) \cap \mathbb {Z}^2 = \mathsf {X}$ and (2) the vertices of $P(\mathsf {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 ${{\mathsf {p}}}_1$ and ${{\mathsf {p}}}_2$ of V, let us consider the set of the contour points between ${{\mathsf {p}}}_1$ and ${{\mathsf {p}}}_2$, denoted by $C({{\mathsf {p}}}_1,{{\mathsf {p}}}_2)$. First, we verify if

$$\begin{aligned} {C({{\mathsf {p}}}_1,{{\mathsf {p}}}_2) {\setminus } P \ne \emptyset } \end{aligned}$$

(23)

If there exists at least one point of $C({{\mathsf {p}}}_1,{{\mathsf {p}}}_2)$ outside of P; then, we select a point ${{\mathsf {p}}}_3 \in C({{\mathsf {p}}}_1, {{\mathsf {p}}}_2) {\setminus } P$ such that

$$\begin{aligned} {{\mathsf {p}}}_3 = \arg \max _{{{\mathsf {q}}}\in C({{\mathsf {p}}}_1, {{\mathsf {p}}}_2) {\setminus } P} \{ d({{\mathsf {q}}}) \mid (\varDelta {{\mathsf {q}}}{{\mathsf {p}}}_1 {{\mathsf {p}}}_2 \cap \mathbb {Z}^2) \subset \mathsf {X} \} \end{aligned}$$

where $d({{\mathsf {q}}})$ is the distance of ${{\mathsf {q}}}$ to the line passing by ${{\mathsf {p}}}_1$ and ${{\mathsf {p}}}_2$ and $\varDelta {{\mathsf {p}}}{{\mathsf {q}}}{{\mathsf {r}}}$ is the triangle whose vertices are ${{\mathsf {p}}}$, ${{\mathsf {q}}}$ and ${{\mathsf {r}}}$.

If Eq. (23) does not hold, then we verify whether there exists any point ${{\mathsf {q}}}\in \overline{\mathsf {X}} \cap P$ such that ${{\mathsf {q}}}$ is in the polygon constructed from the polygonal line of $C({{\mathsf {p}}}_1,{{\mathsf {p}}}_2)$ and the line segment from ${{\mathsf {p}}}_2$ to ${{\mathsf {p}}}_1$. If so, we select ${{\mathsf {p}}}_3 \in C({{\mathsf {p}}}_1,{{\mathsf {p}}}_2)$ such that

$$\begin{aligned} {{\mathsf {p}}}_3&= \arg \max _{{{\mathsf {q}}}\in C({{\mathsf {p}}}_1,{{\mathsf {p}}}_2)} \{ d({{\mathsf {q}}}) \mid ~ \\&\quad {(\forall {{\mathsf {r}}}_1 \in C({{\mathsf {p}}}_1,{{\mathsf {q}}}), (\varDelta {{\mathsf {p}}}_1 {{\mathsf {r}}}_1 {{\mathsf {q}}}\cap \mathbb {Z}^2) \subset \mathsf {X})} \\&\quad {~\vee ~} {(\forall {{\mathsf {r}}}_2 \in C({{\mathsf {q}}},{{\mathsf {p}}}_2), (\varDelta {{\mathsf {q}}}{{\mathsf {r}}}_2 {{\mathsf {p}}}_2 \cap \mathbb {Z}^2) \subset \mathsf {X})} \} \end{aligned}$$

Fig. 10

a Tangential cover (in red) of a contour curve [31], composed of the sequence of its maximal discrete straight segments, and dominant points (in green) detected by using the tangential cover [43, 44]. 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 (Color figure online)

Fig. 11

Experiments on H-convexity preservation for digitized rigid motions ${{\mathcal {T}}}_{Point}, {{\mathcal {T}}}_{Conv}$ and ${{\mathcal {T}}}_{Poly}$, with rotation angle of $\frac{\pi }{10}$ and translation of (0.1,0.2). See Sect. 6.2a the initial digital object $\mathsf {X}$, b${{\mathcal {T}}}_{Point}(\mathsf {X})$, c${{\mathcal {T}}}_{Conv}(\mathsf {X})$, d${{\mathcal {T}}}_{Poly}(\mathsf {X})$

Fig. 12

Polygon (in blue) and convex hull (in red) of the digital object $\mathsf {X}$ of Fig. 11a (Color figure online)

For either case, if such ${{\mathsf {p}}}_3$ exists, we add it to V between ${{\mathsf {p}}}_1$ and ${{\mathsf {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 [30] 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.

6.2 Topological and Convexity Preservation

The first experiment of rigid motions was carried out on an H-convex digital object (see Fig. 11a). Figure 11 presents the result of ${{\mathcal {T}}}_{Point}, {{\mathcal {T}}}_{Conv}$ and ${{\mathcal {T}}}_{Poly}$ on $\mathsf {X}$. It should be mentioned that, in general, the polygon $P(\mathsf {X})$ obtained by the method proposed in Sect. 6.1 is not equal to the convex hull ${\mathcal Conv}(\mathsf {X})$. In particular, even if $\mathsf {X}$ is H-convex, $P(\mathsf {X})$ is often non-convex, as illustrated in Fig. 12. Therefore, ${{\mathcal {T}}}_{Poly}$ does not guarantee to preserve the H-convexity of the transformed object (see Fig. 11d). On the contrary, ${{\mathcal {T}}}_{Conv}$ preserves the H-convexity of the transformed object as shown in Prop. 4 and Fig. 11a. By contrast, ${{\mathcal {T}}}_{Point}$ hardly preserves the H-convexity of the transformed object.

We performed the second experiments on two H-convex digital objects, namely a disk of radius 10 and a square of size $21 \times 21$. We provide an assessment of the performance of rigid motions using three transformation models: ${{\mathcal {T}}}_{Point}$, ${{\mathcal {T}}}_{Conv}$ and ${{\mathcal {T}}}_{Poly}$. 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 and 2 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 ${{\mathcal {T}}}_{Point}$ alter the boundary of the objects and modify their topology.

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

Fig. 13

Area (left) and perimeter (right) variations induced by successive rotations for the disk of radius 10 of Table 1. See Sect. 6.3 (Color figure online)

Fig. 14

Area (left) and perimeter (right) variations induced by successive rotations for the square of size $21 \times 21$ of Table 2. See Sect. 6.3 (Color figure online)

Fig. 15

Area (left) and perimeter (right) variations induced by successive rigid motions for the disk of radius 10 of Table 1. See Sect. 6.3 (Color figure online)

Fig. 16

Area (left) and perimeter (right) variations induced by successive rigid motions for the square of size $21 \times 21$ of Table 2. See Sect. 6.3 (Color figure online)

Fig. 17

Non-convex digital objects used as input for the experiments of Sect. 6.2. a, b, c

Fig. 18

Non-convex digital objects used as input for the experiments of Sect. 6.2. a. b. c

Fig. 19

Area (left) and perimeter (right) evolution of the three digital objects , and (see Fig. 17), under successive rigid motions ${{\mathcal {T}}}_{Point}$ and ${{\mathcal {T}}}_{Poly}$. See Sect. 6.2 (Color figure online)

Fig. 20

Area (left) and perimeter (right) evolution of the three digital objects , and (see Fig. 18), under successive rigid motions ${{\mathcal {T}}}_{Point}$ and ${{\mathcal {T}}}_{Poly}$. See Sect. 6.2 (Color figure online)

6.3 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 H-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 [49], and the perimeter is calculated based on curve segmentation by maximal digital standard segments [50] of the 4-connected curves extracted from the transformed objects. It has been proven that these estimators have multigrid convergence property [51].

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

Figures 13 and 14 report some quantitative comparisons of those geometric measures between rotations by ${{\mathcal {T}}}_{Point}$, ${{\mathcal {T}}}_{Conv}$ and ${{\mathcal {T}}}_{Poly}$ on the input images given in Tables 1 and 2. We can observe that ${{\mathcal {T}}}_{Point}$ and ${{\mathcal {T}}}_{Conv}$ do not preserve well the perimeter of the transformed objects since ${{\mathcal {T}}}_{Point}$ alters the boundary of the objects and ${{\mathcal {T}}}_{Conv}$ is a decreasing operator. By construction, ${{\mathcal {T}}}_{Poly}$ uses a polygon that fits the input digital object for the transformation; thus, it preserves well the perimeter. For the same reasons, ${{\mathcal {T}}}_{Conv}$ does not preserve the area, contrary to ${{\mathcal {T}}}_{Poly}$. Since ${{\mathcal {T}}}_{Point}$ is defined on a point-by-point model, it also preserves the area measure.

Figures 15 and 16 show results under rigid motions generated randomly with rotation angles $\theta \in [0, 2\pi )$ and translation values $t_1,t_2 \in [0, 1)$. The results are similar to those of Figs. 13 and 14. The difference is that the peaks at the special angles of $\frac{\pi }{2}k$ for ${{\mathcal {T}}}_{Conv}$ are not seen in Figs. 15 and 16 since random rigid motions are applied.

In our last experiments, we perform rigid motions on non-convex objects (see Figs. 17, 18). Again, we evaluate the proposed transformation models ${{\mathcal {T}}}_{Point}$ and ${{\mathcal {T}}}_{Poly}$ with respect to the following measures: (i) area and (ii) perimeter. The results are, respectively, shown in Figs. 19 and 20, for rigid motions ${{\mathcal {T}}}_{Poly}$ generated randomly with rotation angles $\theta \in [0, 2\pi )$ and translation values $t_1, t_2 \in [0, 1)$. We can observe that both ${{\mathcal {T}}}_{Point}$ and ${{\mathcal {T}}}_{Poly}$ have a stable behavior with respect to area measure, and ${{\mathcal {T}}}_{Poly}$ preserves better the perimeter than ${{\mathcal {T}}}_{Point}$.

Comparing three models of rigid motions ${{\mathcal {T}}}_{Point}$, ${{\mathcal {T}}}_{Conv}$ and ${{\mathcal {T}}}_{Poly}$, we can see that ${{\mathcal {T}}}_{Point}$ and ${{\mathcal {T}}}_{Poly}$ preserve better area. Whereas ${{\mathcal {T}}}_{Conv}$ is a decreasing operator, it is the only that allows the preservation of convexity. ${{\mathcal {T}}}_{Point}$ alters the boundary of the objects and does not preserve topology nor perimeter, while ${{\mathcal {T}}}_{Poly}$ preserves better perimeter and topology, when $P(\mathsf {X})$ is quasi-1-regular.

7 Conclusion

In this article, we proposed an algorithmic process for performing rigid motions on digital objects, i.e. finite subsets of $\mathbb {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 $\mathbb {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 $\mathbb {Z}^3$. Such an extension cannot be straightforward as topological (and geometric) properties of Gauss digitization for more than two dimensions are different and more complex than those in two dimensions [52]. In addition, we will describe how to consider not only simply connected objects, but more generally arbitrary-topology objects (this is tractable in $\mathbb {Z}^2$, but less simple in $\mathbb {Z}^3$). Second, from a practical point of view, we will investigate the relevance of different polygonization approaches, in order to identify 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-1-regularity; 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 [53] is available online.⁴