<figure><img src="image_1.png" /></figure>

HAL
open science

# A Digitization Map

Loïc Mazo

► To cite this version:

Loïc Mazo. A Digitization Map. 2025. hal-05094235

HAL Id: hal-05094235

https://hal.science/hal-05094235v1

Preprint submitted on 2 Jun 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A Digitization Map

Loïc Mazo

aICube-UMR 7357, 300 Bd Sébastien Brant - CS 10413, 67412, Illkirch, France

## Abstract

When scanning an object, it is well known that a simple shift of the sensor can lead to dramatic change in the produced digital image: cardinal, convexity, topology, etc may change. It is therefore necessary to get some knowledge of the set of all discretizations of the same object that can be obtained by the sensor depending on the placement of the object. In this paper, we aim at describing a *digitization map* in a general setting in which the ambient space is locally compact and Hausdorff, the object is any compact set and the sensor intersects this compact set with a given locally finite subset of the ambient space. This “digitization map” partitions the topological group modeling the object motion according to the produced digitization. We also present a *reduced digitization map* in which some digitizations are identified and, subsequently, some sensor movements are identified (because they produce equivalent digitizations).

**Keywords:** digitization, shift, group action, general topology

## 1. Introduction

Properties of real world objects are often studied via numerical models elaborated thanks to digital acquisitions. Such models make it possible to estimate geometric features as, area, volume, derivative, tangent, curvatures, Laplacian, convexity and so on (see for instance the bibliography in [KR04]) or to infer topological characteristics of the continuous object (among many others, let us cite [RMT19] for connectivity, [KRR92] for homotopy, [KMM04] for homology). However, the same object may have distinct digitizations depending on its position relative to the scanning device. A simple translation may impact on a qualitative feature as the estimated Euler characteristic. Hence, it is worth gaining some knowledge of the digitization variability related to a set of object (or device) positions and orientations. In this paper, we consider a very simple digitization method: the continuous object is digitized through its intersection with a given locally finite set. This is known as *Gauss digitization*. We focus on the way in which the preimages of the different Gauss digitizations of a single object divide the space of transformations. This has been used for at least three decades, often implicitly, to determine and encode the digitization set in *pattern matching*. In this case, the goal is to identify all the occurrences of a given pattern (a letter, a shape, etc.) in a digital image resulting from the scanning
of an Euclidean object. To build fast algorithms, it was proposed in [LV94] to
take into account the finiteness of the research space due to the discretization
process instead of using continuous optimization techniques. Then, a possible
way to realize the task is to build a dictionary with all the digitizations of the
pattern under a transformation class (e.g. rotations) and to travel the digital
image gliding a window and comparing its view with the discretizations recorded
in the dictionary. This research program led to several algorithms that recog-
nize in a scene the occurrences of a given pattern whatever its position when
it is subject to rotations [FU98, FNU02], scalings and translations [ABLP09],
affine and projective transformations [HL08, Hun12]. The last two cited works
explicitly mention the portioning of the transformation space (2D projective
transformations). The supports of the pattern and the scene are assumed to
be finite rectangular subsets of $\mathbb{Z}^n$. Then, the transformation space, which is
an affine subspace of $\mathbb{R}^n$ (points at infinity are not taken into account), is par-
titioned by hyperplanes where changes occur in the rounded image which is
composed of integer points. If two transformations produce two different im-
ages of the pattern, they lie in distinct cells of the partition (the converse is
not true). This makes it possible to enumerate all the possible pattern image
digitizations that may occur inside the scene. Inspired by the previous tech-
nique, a direct partitioning of the planar rigid transformation space related to
a digital image processing issue is proposed in [NKPT13]. Here, the goal is
to determine all the “discrete rigid transformations” acting on a finite square
of $\mathbb{Z}^2$. A discrete rigid transformations is defined as the composition of a rigid
transformations of $\mathbb{R}^2$, that is a rotation or a translation, followed by a rounding
operation. Observe that this latter goal requires a pointwise comparison of the
transformations whereas for the pattern matching problem such a comparison
is sufficient but not necessary. Furthermore, contrary to Hundt [Hun12], the
transformation space is not parametrized by the matrix coefficients. Instead,
the rotation angle and a translation vector is used leading to divide the space
of (continuous) rigid motions by cylinders whose basis are sinusoid periods and
whose directions are one or the other axis of the translation space. Such digital
transformations could make it possible to accomplish computer vision or image
processing tasks, such as topology preservation assessment [NKPT14] or image
registration [NKS<sup>+</sup>17], in fully discrete —and exact— processes.

The segmentation of the rigid motion space with respect to the action on
a given shape has also been used in algorithmic geometry by [DS98] in order
to solve an optimization problem: finding an algorithm that deliver an optimal
placement of a convex polygon to maximize the number of enclosed points among
a finite set of points. According to the authors, the applications include placing
labels on maps, cutting a piece with constraints, geometric tolerancing, robot
placement, etc. Let $P$ and $S$ be respectively the polygon and the finite set of
points. Let $n$ be the cardinal of $S$. In order to reduce the research space, the
authors extract from the transformation space the $n$ tori $S^1 \times S^1$ that contain the
rigid transformations sending a point $s \in S$ on the boundary of $P$. Then, the
authors delineate in each torus the $n-1$ regions that contain the transformations
sending into $P$ a point $s' \in S$, $s' \neq s$, Finally, the algorithm runs through each
torus to find the point which belongs to a maximum of regions.

Let us end by combinatorics. Counting the number of digitizations of a circle of fixed radius according to the position of its center is done in [HŽ04, HŽ06]. The technique is extended to some strictly convex sets in [HŽ10], to scalings in [HŽ13] and to count the number of circle digitizations having exactly *n* lattice points in [HŽ16]. Actually, the space of transformations is not mentioned in these articles. For instance, in the case of fixed radius circles, the position of the circle center is considered instead. Let $\varphi$ be the function that maps a circle center to the corresponding discretization. The domain of $\varphi$ is reduced to a unit square by noting that integer translations produce digitizations that can obviously be considered as equivalent. Then, the authors determine the frontiers of the preimages of the different digitizations up to integer translations. These frontiers are composed of circle arcs that intersect. Circle arcs are seen as edges of a planar graph on which Euler formula applies. Then, an asymptotic analysis of the number of vertices and their degrees gives an estimation on the number of discretizations. In a previous work [BM19], we also furnished some upper bounds for the number of Gauss digitizations, up to translations, of a plane shape bounded by a Jordan curve.

Our previous work followed on from a first one [MB18] qualitatively describing the partitioning of the translation space induced by the action on a plane object bounded by a Jordan curve. In particular, we showed that the structure induced on the torus by the digitization preimages is obtained by plotting the Jordan curve on the torus (thanks to a modulo 1 operation on the coordinates). We now propose to study this kind of partition in the more general case of a topological group continuously acting on a compact subset of a locally compact and Hausdorff space. The Gauss digitization is performed thanks to a locally finite subset of the space whose elements are called *digital points*. Particularly, we focus on topological properties of the partition. The paper is organized as follows. In Section 2.1, we present our notations and recall some definitions and results in general topology. Section 2.2 is devoted to the description of our Gauss digitization process and to the definition of the topic of the article, the *digitization map*, which links transformations with digitizations, that is with binary partitions of the set of digital points. We also describe the example that is used throughout Sections 2 and 3. Section 2.3 introduces the *digitization hinge* which is the locus of the digitization changes. Then, some topological properties of this subset of the transformation group are established. In Section 2.4, we focus on the partition of the whole group as a collection of *digitization cells* on which the digitizations are constant. As of Section 3, an equivalence on digitizations is assumed: two digitizations are equivalent if there exists a transformation that send one to the other. Section 3.1 formally defines the equivalence, shows its effect on our example and gives some comments about the definition. This equivalence on sets of digital points induces another equivalence on transformations described in Section 3.2. Indeed, the transformations belonging to the stabilizer of the set of digital points produce equivalent digitizations. The transformation space can be therefore quotiented by this stabilizer. Sections 3.3 and 3.4 give some properties of the projections of the digitization hinge and the digitization cells
on the quotient space. Section 4 is devoted to examples and counterexamples.
Eventually, Section 5 concludes the article giving a few further questions worth
to explore.

## 2. The digitization map

### 2.1. Terminology, notations and facts

Given a topological space $T$ and a set $A \subset T$, we write $A^{\circ}$ for its *interior* (the largest open subset of $A$), cl $A$ for its *closure* (the smallest closed set containing $A$), its *complement*, or *exterior*, $T \setminus A$ is denoted by $A^c$ and its *boundary* cl $A \setminus A^{\circ}$ is denoted by $\partial A$. A point $x \in T$ belongs to $\partial A$ if and only if any open neighborhood of $x$ intersects both $A$ and $A^c$. The boundary of an open, or closed, subset of $T$ has an empty interior.

Given three subsets $A, B, C$ of $T$, we say that $A$ separates $B$ from $C$ if any connected subset of $T$ containing a point of $B$ and a point of $C$ contains a point in $A$. In particular, for any set $A \subset T$, $\partial A$ separates $A$ from $A^c$ (and $A^{\circ}$ from $A^c$). Notice that if either $B$ or $C$ is empty, then $A$ separates $B$ from $C$ whatever the choice of $A$ among the subsets of $T$.

A topological space $T$ is *Hausdorff* if any two distinct points have disjoint neighborhoods. It is *locally compact* if any point of $T$ has a compact neighborhood. It is *locally connected at $x$* if any neighborhood of $x$ contains an open connected neighborhood of $x$. The space $T$ is *locally connected* if it is locally connected at any point. Connected components are close subsets but they need not be open. Nevertheless, if $T$ is locally connected, the connected components of the open subsets are also open. A collection of subsets of $T$ is *locally finite* if any point of $T$ has a neighborhood that intersects finitely many of these subsets. An union of a locally finite collection of closed sets is a closed set. A subset of $A$ is locally finite if any point in $T$ has a neighborhood that contains finitely many elements of $A$. In other words, the subset $A$ is locally finite if the collection of singletons $(\{a\})_{a \in A}$ is locally finite in $T$. The intersection of a locally finite subset with a compact set is finite.

A map between two topological spaces is *locally constant* at a point of its domain if this point has a neighborhood on which the map is constant. The map is *locally constant* if it is locally constant at every point of its domain. Any locally constant map on a connected set is constant.

A topological group $G$ is a topological space equipped with a group structure such that the group operation $(x, y) \in G \times G \mapsto xy \in G$ and the inverse map $\psi: g \in G \mapsto g^{-1} \in G$ are continuous. In this case, since $\psi$ is an involution, it is an homeomorphism. The topological group $G$ continuously acts on the topological space $T$ if there exists a continuous map $\rho: G \times T \to T$ such that $\rho(e, x) = x$ for any $x \in T$ (e is the identity element of $G$) and $\rho(g, \rho(h, x)) = \rho(gh, x)$ for any $g, h$ in $G$ and any $x$ in $T$. In this case, the transformations $x \mapsto \rho(g, x)$, $g \in G$, are homeomorphisms of $T$. Given a point $x \in T$, we write $\rho_x$ for the map $g \in G \mapsto \rho(g, x) \in T$. The map $\rho_x$ is continuous, one-to-one whenever the action of $G$ on $T$ is *free*, onto whenever this action is *transitive*
and bijective whenever the action is regular. When there is no ambiguity, we denote by $g \cdot x$ the action of $g$ on $x$, that is, $g \cdot x = \rho(g, x)$ where $\rho$ is the group action taken into consideration. Given a subset $A$ of $T$, we also write $g \cdot A$ for the set $\{g \cdot x | x \in A\}$. Observe in particular that, for any $g \in G$ and any $A \subset T$, $\partial(g \cdot A) = g \cdot \partial A$.

Given an equivalence relation on $T$, the projection (or quotient map) $\pi_{\sim}$ is the surjective map $x \in T \mapsto [x] \in T/\sim$ where $[x]$ denotes the equivalence class of $x$ and $T/\sim$ is the quotient set, the sets of all equivalence classes. The open sets of the quotient topology which equips $T/\sim$ are those subsets of $T/\sim$ whose preimages by $\pi_{\sim}$ are open subsets of $T$ (equivalently, a set is closed if and only if its preimage is closed). Obviously, with this topology, the quotient map $\pi_{\sim}$ is continuous. Furthermore, if $T$ is a topological group, the quotient map is an open map, that is, the image by $\pi_{\sim}$ of an open set is an open set. If $T$ is locally connected, the quotient set is itself locally connected.

## 2.2. Digitization and group action

Given a locally compact Hausdorff space $E$, we perform the digitizations of its compact subsets by means of a locally finite subset $D$ of $E$ (Gauss digitization). The points in $D$ are called digital points. The set of all finite subsets of $D$ is denoted by $\mathcal{F}(D)$. The cardinal of an element $A \in \mathcal{F}(D)$ is denoted by $|A|$. In this paper, we are interested to what happens to the digitization when a topological group acts on the (points of) a given compact subset of $E$, We say that a tuple $(E, D, G, K)$ is a digitization quadruple if $E$ is a locally compact Hausdorff space, $G$ is a topological group continuously acting on $E$, $D$ is a locally finite subset of $E$ and $K$ is a compact subset of $E$. Some properties presented thereafter (notably in Section 3) do not depend on the choice of the compact set $K$. In this case, the assumptions will refer to the digitization triple $(E, D, G)$. In the rest of Section 2 and in Section 3, definitions are illustrated by the same digitization quadruple $Q_{\text{ex}}$ defined by

$$Q_{\text{ex}} = (\mathbb{R}^2, S^+, \mathbb{Z}^2, M), \qquad (1)$$

where $S^+$ denotes the linear direct similitude group and $M$ denotes the compact subset of $\mathbb{R}^2$ shown on Figure 1. Other examples are gathered at the end of the article, in Section 4.

<figure><img src="image_3.png" /><figcaption>Figure 1: The compact set of $M \subset \mathbb{R}^2$ used in the examples of Sections 2 and 3. The interior of $M$ is depicted in pink and its boundary is in blue. The digital points of the plane are depicted as black points. Since we choose to exemplify Sections 2 and 3 with a digitization quadruple whose transformation group is linear, the origin $o = (0, 0)$ of the plane plays a special role. In order to identify it, it is depicted larger than the other digital points.</figcaption></figure>

Let us now define the map whose study is the topic of this article.
**Definition 2.1** (Digitization map). Let $Q = (E, G, D, K)$ be a digitization quadruple.

* The digitization map (relative $Q$) is the function $\mathcal{D}$ defined by

$$ \mathcal{D}: G \to \mathcal{F}(D) \\ g \mapsto (g \cdot K) \cap D. $$

* The digitization cardinal map is the function $\sigma: g \in G \mapsto |\mathcal{D}(g)| \in \mathbb{N}$.

In other words, $\mathcal{D}(g)$ is the digitization of the compact set $g \cdot K$ and $\sigma(g)$ is the number of digital points in $\mathcal{D}(g)$. Figure 2 showcases three values of the digitization map relative to the quadruple $Q_{\text{ex}}$.

<figure><img src="image_4.png" /><figcaption>Figure 2: Three values, depicted by sets of red points, of the digitization map relative to $Q_{\text{ex}}$. The linear similitude $e$ is the identity, $s_1$ is the rotation of angle $-\pi/4$ and $s_2$ the scaling of ratio 2. Observe that the origin $o$ belongs to $\mathcal{D}(g)$ for any $g \in S^+$ because the transformation group $S^+$ is linear and $o \in \mathcal{D}(e)$.</figcaption></figure>

In the remainder of Section 2, we assume a digitization quadruple $Q = (E, G, D, K)$ and we study the topological properties of the related digitization map $\mathcal{D}$.

## 2.3. The digitization hinge

The digitization hinge defined below plays the principal role in this article. It makes possible to segment the group $G$ in connected regions the elements of which yield the same digitization. Basically, the definition expresses that, continuously moving the set $K$ (thanks to the action of the elements of $G$), the digitization $\mathcal{D}(g) = (g \cdot K) \cap D$ may change when the boundary of $g \cdot K$, which is equal to $g \cdot \partial K$, meets a digital point. This point may appear, or disappear, in the digitization according to the way we continuously change the value of $g$.

In other words, setting<fnref n="1" /> $\partial \mathcal{D}(g) = D \cap g \cdot \partial K$, the critical transformations for the digitization issue are located in the set $\{g \in G \mid \partial \mathcal{D}(g) \neq \emptyset\}$. This is the set used in our definition. An example of digitization hinge is shown in Figure 3.

<footnote n="1">¹Since $E$ is Hausdorff, $\partial K$ is included in $K$ and therefore is compact. Then, $\partial \mathcal{D}$ is the digitization map relative to the quadruple $(E, G, D, \partial K)$.</footnote>
**Definition 2.2** (Digitization hinge). Let $Q = (E, G, D, K)$ be a digitization quadruple. The digitization hinge relative to $Q$ is the set $H_{\partial D}$ defined by

$$H_{\partial D} = \{g \in G \mid \partial D(g) \neq \emptyset\}. \qquad (2)$$

In the rest of the paper, when there is no ambiguity, we write $H$ instead of $H_{\partial D}$.

Sometimes, for computational or visualization reasons, it is interesting to look at the set $H^* = \psi(H)$ instead of $H$. We call $H^*$ the dual digitization hinge. It is equal to $\{g \in G \mid g \cdot D \cap \partial K \neq \emptyset\}$. Using $H^*$, we move $D$ instead of moving $K$.

<figure><img src="image_5.png" /><figcaption>Figure 3: The digitization hinge related to the quadruple $Q_{ex} = (\mathbb{R}^2, S^+, Z^2, M)$. The hinge is depicted in blue. The direct similitude space is represented by a cylinder whose basis is a circle (the red dotted line) and which has been cut along the red dashed line to get a plane representation. In Section 4.1, the same hinge is depicted in the complex plane deprived of its origin.</figcaption></figure>

The digitization hinge can be split into segments, each of them separating the transformation space into two regions (see Proposition 2.4). These digitization hinge segments and their inner sides are defined as follows (Figure 4 exemplifies this definition).

**Definition 2.3** (Hinge segment and its inner side). Assuming the digitization quadruple $(E, G, D, K)$, let $d \in D$.

* The hinge segment $H_{\partial D}^d$ is defined by

$$H_{\partial D}^d = \{g \in G \mid d \in \partial D(g)\},$$

* The hinge segment inner side is

$$I_D^d = \{g \in G \mid d \in D(g)\},$$

As we the hinge, in the following, we omit the subscripts $\partial D$ and $D$ when no confusion can occur.

The segment $H^d$ of the digitization hinge is composed of all the transformations in $G$ that move the set $K$ so that its boundary contains the digital point
<figure><img src="image_6.png" /><figcaption>Figure 4: The hinge segment $H^d$, where $d = (1, 0)$, relative to the quadruple $Q_{ex}$ is depicted in blue. The inner side of $H^d$ lie above $H^d$.</figcaption></figure>

d. Equivalently, $H^d$ contains all the transformations whose inverses send $d$ onto the boundary of $K$. Alike, $I^d$ contains the transformations whose inverses send $d$ into $K$.

The digitization hinge segments verify the following properties:

**Proposition 2.4.** Let $H$ be the digitization hinge relative $Q = (E, G, D, K)$ and $(H^d)_{d \in D}$ be its segments. Then,

$$H = \bigcup_{d \in D} H^d.$$

Furthermore, denoting by $I^d$ the inner side of $H^d$, $d \in D$,

a) the sets $H^d$ and $I^d$ are closed. The set $I^d \setminus H^d$ is open. In particular, $\partial(I^d) \subset H^d$;

b) the set $H^d$ separates $I^d$ from $(I^d)^c$;

c) if the map $\rho_d$ is open, then $\partial(I^d) = H^d$. In particular, $H^d$ has an empty interior.

*Proof.* The first equality, $H = \bigcup_{d \in D} H^d$, directly results from the definition of the digitization hinge $H$ (Definition 2.2).

Let us prove the other properties. Let $d \in D$. We set $\xi = \rho_d \circ \psi$. Hence, $\xi(g) = g^{-1} \cdot d$ for any $g \in G$. The map is continuous for $\psi$ and $\rho_d$ are continuous. Furthermore,

$$H^d = \xi^{-1}(\partial K), \quad I^d = \xi^{-1}(K) \text{ and } I^d \setminus H^d = \xi^{-1}(K^\circ).$$

Notice that, as a compact subset of a Hausdorff space, $K$ is closed.

a) Since $\xi$ is continuous, openness and closedness are transported by $\xi^{-1}$. Then, from the fact that $K$ and $\partial K$ are closed sets and $K^\circ$ is an open set, we derive that $H^d$ and $I^d$ are closed sets and $I^d \setminus H^d$ is an open set. Since $I^d \setminus H^d$ is open, it is included in the interior of $I^d$ and thus does not intersect $\partial(I^d)$. Hence, $\partial(I^d) \subset H^d$.
b) Because $\partial(I^d) \subset H^d$ and boundaries separate subsets from their exteriors, $H^d$ separates $I^d$ from its exterior.

c) Assume that $\rho_d$ is an open map. Then, so is $\xi$ (because $\psi$ is an homeomorphism). Let $g \in H^d$ and $U$ be an open neighborhood of $g$. Then, $\xi(U)$ is an open neighborhood of $g^{-1} \cdot d \in \partial K$. Therefore, $\xi(U)$ contains points in $K$ and in $K^c$. Thus, $U$ contains elements in $I^d$ and in its complement. We derive that $g \in \partial(I^d)$. Thus, $H^d \subset \partial(I^d)$ and since we proved the reverse inclusion in Item a, we have the equality. Furthermore, boundaries of closed sets have empty interiors, so $H^d$ has an empty interior. $\square$

In Section 4.7, we give some examples where maps $\rho_d$ are not open and where hinge segments have non-empty interiors.

**Lemma 2.5.** Let $(E, G, D, K)$ be a digitization quadruple. Then, the set collection $(I^d)_{d \in D}$ is locally finite in $G$.

*Proof.* Let $g \in G$. On the one hand, the set $g \cdot K$ is compact (for $\rho$ is continuous). On the other hand, since $D$ is locally finite, for any $x \in g \cdot K$, there exists an open neighborhood of $x$, $U_x$, such that $U_x \cap D$ is finite. Then, we can cover $g \cdot K$ with finitely many open sets $U_x$, say

$$g \cdot K \subset U = \bigcup_{x \in C} U_x,$$

where $C$ is a finite subset of $g \cdot K$. Observe that $U \cap D$ is finite. The continuity of $\rho$ implies that $\Omega = \rho^{-1}(U)$ is an open subset of $G \times E$. Clearly, $\{g\} \times K$ is included in $\Omega$. We derive that for any $x \in K$, there exists open sets $V_x \subset G$ and $W_x \subset E$ such that $(g, x) \in V_x \times W_x \subset \Omega$. Thanks to the compactness of $K$, we can extract a finite cover of $K$, $(W_x)_{x \in A}$ (with $A$ being a finite subset of $K$). We set $V = \bigcap_{x \in A} V_x$. The set $V$ is an open neighborhood of $g$ and $V \times K \subset \bigcup_{x \in A} V_x \times W_x \subset \Omega$. Then, for any $h \in V$, the compact set $h \cdot K$ is included in $U$ which contains a finite number of digital points. In other words, the neighborhood $V$ of $g$ intersects a finite number of sets $I^d$, $d \in D$. $\square$

Noting that, for any $d \in D$, the hinge segment $H^d = \{g \in G \mid d \in g \cdot \partial K\}$ is included in the set $I^d = \{g \in G \mid d \in g \cdot K\}$, we directly deduce from Lemma 2.5 the following corollary.

**Corollary 2.6.** Let $(E, G, D, K)$ be a digitization quadruple. Then, the hinge segment collection $(H^d)_{d \in D}$ is locally finite in $G$.

From Proposition 2.4-b and Corollary 2.6, we derive that, under the assumption that the maps $\rho_d: g \in G \mapsto g \cdot d \in E$ are all open, the digitization hinge has an empty interior.

**Proposition 2.7.** Let $Q = (E, G, D, K)$ be a digitization quadruple. If the maps $\rho_d, d \in D$, are open, then the digitization hinge relative to $Q$ has an empty interior.
**Proof.** Let H be the digitization hinge and let $g \in H$. From Corollary 2.6, the hinge segment family $(H^d)_{d \in D}$ is locally finite. Therefore, there exists an open neighborhood U of g and a finite subset A of D such that $H^d \cap U = \emptyset$ for any $d \notin A$. Then, $U \cap H \subset \bigcup_{d \in A} H^d$ (recall that, from Proposition 2.4, $H = \bigcup_{d \in D} H^d$). Besides, according to this latter proposition, the sets $H^a$, $a \in A$, are closed sets with empty interiors (for we assume that the maps $\rho_d$ are open). Thus, $\bigcup (H^d)_{d \in A}$ has an empty interior (a finite union of closed sets with empty interior has an empty interior). We derive that any open neighborhood of g included in U has at least one element outside $\bigcup (H^d)_{d \in A}$ and thus, outside H. Hence, the set H has an empty interior. □

See Section 4.7 for examples of hinges with non-empty interiors. We now prove, thanks to the following Lemma, that the digitization hinge is a closed set.

**Lemma 2.8.** Let $(E, G, D, K)$ be a digitization quadruple. Then, the digitization hinge set $\{g \in G \mid \mathcal{D}(g) \neq \emptyset\}$ is a closed subset of G.

**Proof.** We saw in Proposition 2.4 that the sets $I^d$ are closed sets. Then, according to Lemma 2.5, the set $\{g \in G \mid \mathcal{D}(g) \neq \emptyset\} = \bigcup_{d \in D} I^d$ is an union of a locally finite family of closed sets. So, it is a closed set. □

**Proposition 2.9.** Let $Q = (E, G, D, K)$ be a digitization quadruple. The digitization hinge H relative to Q is a closed set.

**Proof.** We apply Lemma 2.8 with $\partial K$ as compact subset of E. □

## 2.4. Digitization cells

In Section 2.4, we keep the same notations as in Section 2.3: H is the digitization hinge relative to $Q = (E, G, D, K)$ and $(H^d)_{d \in D}$ is the hinge segment collection. We now focus on the digitization preimages, that is on the sets $\mathcal{D}^{-1}(A)$, $A \in \mathcal{F}(D)$. For this, we need to use two intermediate sets defined below (Figure 5 illustrates the definition).

**Definition 2.10.** Let H be the digitization hinge relative to the digitization quadruple $(E, G, D, K)$ and A be a finite subset of D. We set

$$I_D^A = \{g \in G \mid A \subset \mathcal{D}(g)\},$$

$$O_D^A = \{g \in G \mid \mathcal{D}(g) \subset A\}.$$

Again, when there is no ambiguity, we will write $I^A$ and $O^A$ instead of $I_D^A$ and $O_D^A$. Observe that we defined in Section 2.3, the sets $I^a$ where $a \in D$, and we now define the sets $I^A$ where $A \subset D$. These two close notations are linked by the relation $I^a = I^{\{a\}}$. Hence, the former notation can be seen as an abbreviation of the latter notation.

Clearly, we have $\mathcal{D}^{-1}(A) = I^A \cap O^A$. Besides, as we defined the digitization hinge in Section 2.3 by means of the digitization map $\partial \mathcal{D}$, we will also consider
<figure><img src="image_7.png" /><figcaption>Figure 5: The sets $I_D^A$, $O_D^A$, $\mathcal{D}^{-1}(A)$, $\partial\mathcal{D}^{-1}(A)$ where $A$ is composed of the three digital points depicted in red on Subfigure (d) (the digitization quadruple is $Q_{ex}$). The transformation $g_0$ identified by a black point on Subfigure (c) produce the shape $g_0 \cdot M$ shown on Subfigure (d).</figcaption></figure>

in the sequel the preimages of digitizations by the map $\partial\mathcal{D}$, that is the sets $\partial\mathcal{D}^{-1}(A)$, $A \in \mathcal{F}(D)$. Notice that $\partial\mathcal{D}^{-1}(\emptyset) = G \setminus H$.

The sets $I^A$, $O^A$ and $\partial\mathcal{D}^{-1}(A)$ verify the following properties.

**Proposition 2.11.** Let $H$ be the digitization hinge relative to $Q = (E, G, D, K)$ and $(H^d)_{d \in D}$ be its segments. Let $A$ be a finite subset of $D$. Then,

$$I^A = \bigcap_{a \in A} I^a, \qquad (O^A)^c = \bigcup_{a \notin A} I^a, \\ \mathcal{D}^{-1}(A) = \bigcap_{a \in A} I^a \setminus \bigcup_{a \notin A} I^a, \qquad \partial\mathcal{D}^{-1}(A) = \bigcap_{a \in A} H^a \setminus \bigcup_{a \notin A} H^a.$$

*Proof.*

$$I_A = \{g \in G \mid A \subset \mathcal{D}(g)\} = \bigcap_{a \in A} \{g \in G \mid a \in \mathcal{D}(g)\} = \bigcap_{a \in A} I^a.$$

Alike,

$$(O^A)^c = \{g \in G \mid \mathcal{D}(g) \setminus A \neq \emptyset\} = \bigcup_{a \notin A} \{g \in G \mid a \in \mathcal{D}(g)\} = \bigcup_{a \notin A} I^a.$$

From the previous equalities, we derive that

$$\mathcal{D}^{-1}(A) = I^A \cap O^A = I^A \setminus (O^A)^c = \bigcap_{a \in A} I^a \setminus \bigcup_{a \notin A} I^a. \qquad (3)$$
Finally, we apply Equation (3) to the quadruple $(E, G, D, \partial K)$ to get

$$ \partial \mathcal{D}^{-1}(A) = \bigcap_{a \in A} \mathrm{H}^a \setminus \bigcup_{a \notin A} \mathrm{H}^a. \quad \square $$

**Corollary 2.12.** Let $(E, G, D, K)$ be a digitization quadruple. Then,

1. the collections $(\mathrm{I}^A)$, $(\mathcal{D}^{-1}(A))$ and $(\partial \mathcal{D}^{-1}(A))$, where $A$ describes $\mathcal{F}(D)$, are locally finite and,

2. for any finite subset $A$ of $D$,

(a) the boundaries of $\mathrm{I}^A$, $\mathrm{O}^A$, $\mathcal{D}^{-1}(A)$ and $\partial \mathcal{D}^{-1}(A)$ are included in $H$;

(b) the sets $\mathrm{I}^A$ and $\mathcal{D}^{-1}(A) \cup H$ are closed and the sets $\mathrm{O}^A$ and $\mathcal{D}^{-1}(A) \setminus H$ are open.

*Proof.* 1. Recall that the collection $(\mathrm{I}^d)_{d \in D}$ is locally finite (Lemma 2.5). Then, given $g \in G$, there exists an open neighborhood $U$ of $g$ such that the set $B$ of all $d \in D$ for which $\mathrm{I}^d \cap U \neq \emptyset$ is finite. Therefore, the set $B'$ of all $A \subset D$ such that $\mathrm{I}^A \cap U \neq \emptyset$ is finite (according to Proposition 2.11, $A \in B'$ implies $A \subset B$). We have proved that the collection $(\mathrm{I}^A)_{A \in \mathcal{F}(D)}$ is locally finite. Now, since $\mathcal{D}^{-1}(A) \subset \mathrm{I}^A$ for any $A \in \mathcal{F}(D)$, we get that the collection $(\mathcal{D}^{-1}(A))_{A \in \mathcal{F}(D)}$ is locally finite. Finally, applying the last result to the quadruple $(E, G, D, \partial K)$, we derive that the collection $(\partial \mathcal{D}^{-1}(A))_{A \in \mathcal{F}(D)}$ is locally finite.

2. (a) First, observe that the boundary of the intersection of a locally finite collection of subsets is included in the union of their boundaries. It is because the intersection of their interiors is included in the interior of their intersection (which is not true in the general case). Then, $\partial \mathrm{I}^A \subset \bigcup_{a \in A} \partial \mathrm{I}^a$. Besides, from Proposition 2.4, each boundary $\partial \mathrm{I}^a$ is included in the hinge segment $H^a$. Therefore, $\partial \mathrm{I}^A \subset H$. Alike,

$$ \partial \mathrm{O}^A = \partial \left( \bigcap_{a \notin A} (\mathrm{I}^a)^c \right) \subset \bigcup_{a \notin A} \partial ((\mathrm{I}^a)^c). $$

And, because the boundary of a subset coincides with the boundary of its exterior, $\partial \mathrm{O}^A \subset \bigcup_{a \notin A} \partial (\mathrm{I}^a) \subset H$.

Since $\mathcal{D}^{-1}(A) = \mathrm{I}^A \cap \mathrm{O}^A$, we derive from the previous results that the boundary of $\mathcal{D}^{-1}(A)$ is included in $H$.

Regarding $\partial \mathcal{D}^{-1}(A)$, it is sufficient to consider the digitization quadruple $(E, G, D, \partial K)$, observing that in this case the hinge is $\{g \in G \mid D \cap g \cdot \partial \partial K \neq \emptyset\}$ which is equal to $H$ for the boundary operator is idempotent on closed sets!.

(b) Let $A \in \mathcal{F}(D)$. According to Propositions 2.4 and 2.11, the set $\mathrm{I}^A$ is an intersection of closed sets. Then, it is closed.

Since, the boundary of $\mathcal{D}^{-1}(A)$ is included in $H$, the set $\mathcal{D}^{-1}(A) \cup H$ is equal to $\mathrm{cl}(\mathcal{D}^{-1}(A)) \cup H$ which is close because $H$ is closed (Proposition 2.9).
To prove the openness of $O^A$, we observe that

$$ (O^A)^c = \bigcup_{a \notin A} I^a = \{g \in G \mid D'(g) \neq \emptyset\}, $$

where $D'$ is the digitization map relative to the quadruple $(E, G, D \setminus A, K)$. Then, from Lemma 2.8, taking $D \setminus A$ as locally finite subset<fnref n="2" /> of $E$, we get that $O^A$ is the complement of a closed set: it is an open set.

Eventually, $D^{-1}(A) = I^A \cap O^A$. Then, $D^{-1}(A) \setminus H = (I^A \setminus H) \cap (O^A \setminus H)$ The set $O^A \setminus H$ is open. Indeed, $H$ is closed (Proposition 2.9) and we just proved that $O^A$ is open.

We now prove that the set $I^A \setminus H$ is also open. We have

$$ I^A \setminus H = \bigcap_{a \in A} I^a \setminus H = \bigcap_{a \in A} (I^a \setminus H^a) \setminus H, $$

where the second equality comes from the inclusion $H^a \subset H$ proved for any $a$ in Proposition 2.4. Noticing that the sets $I^a \setminus H^a$ are open (again from Proposition 2.4), $A$ is finite and $H$ is closed, we conclude that $I^A \setminus H$ is open and therefore $D^{-1}(A) \setminus H$ is open. □

It is plain that the collections $(D^{-1}(A))_{A \in \mathcal{F}(D)}$ and $(\partial D^{-1}(A))_{A \in \mathcal{F}(D)}$ partition the space $G$. We will refine the latter partition by taking the connected components of its parts. This has two advantages: those connected components are easy to identify and to compute (see Figure 6) and the resulting partition is a refinement of the first partition, $(D^{-1}(A))_{A \in \mathcal{F}(D)}$, whose description is the aim of the article.

**Definition 2.13 (Digitization cell).** Let $Q = (E, G, D, K)$ be a digitization quadruple. A digitization cell relative to $Q$ is a connected component of a set $\partial D^{-1}(A)$, $A \in \mathcal{F}(D)$.

We have proved in Corollary 2.12 that the boundaries of the sets $\partial D^{-1}(A)$ are included in the digitization hinge. This property does not extend to digitization cells in the general case. Indeed, consider what happens if we use the field $\mathbb{Q}$ instead of $\mathbb{R}$ for the transformation parameters in the action group of the digitization quadruple $Q_{\text{ex}}$. The transformation space would be totally disconnected and the digitization cells would be singletons (see also Section 4.8). Nevertheless, assuming that the group $G$ is locally connected, we have the following result.

**Proposition 2.14.** Let $(E, G, D, K)$ be a digitization quadruple. If $G$ is locally connected, then the boundaries of the digitization cells are included in the digitization hinge.

<footnote n="2">²The reader can check that the proof is still valid when $D$ is finite and $A = D$.</footnote>
<figure><img src="image_8.png" /><figcaption>Figure 6: Digitization cells. The figure exhibits some digitization cells relative to the quadruple $Q_{\text{ex}}$. The yellow cells are components of $\partial D^{-1}(\emptyset)$. The other displayed cells are those encountered along the hinge segment $H^a$ where $a = (0,1)$ (the cells on the gray hinge segments are not showcased). The blue cells are the components of $\partial D^{-1}(\{a\})$, the magenta cells are the components of $\partial D^{-1}(\{a,b\})$ where $b = (0,-1)$, the red cells are the components of $\partial D^{-1}(\{a,c\})$ where $c = (0,1)$. The other cells, represented by bullets, are singletons. For instance, the two cyan bullets are the components of $\partial D^{-1}(\{a,d\})$ where $d = (1,1).</figcaption></figure>

*Proof.* Let $C$ be a digitization cell. If $C$ is a connected component of a set $\partial D^{-1}(A)$ where $A \neq \emptyset$, then $C$ is included in $H$ which is closed (Proposition 2.9). Thereby, the boundary of $C$ is included in $H$. We now assume that $C$ is a component of $G \setminus H$. Due to Proposition 2.9, $G \setminus H$ is open and, because $G$ is locally connected, $C$ is open. Since components are closed subsets, we derive that the boundary of $C$ in $G \setminus H$ is empty. Moreover, it can be seen that, because $G \setminus H$ is open, this boundary is $\partial C \setminus H$. Then, $\partial C$ is included in $H$. $\square$

Let us now show that the digitization map is constant on the digitization cells.

**Lemma 2.15.** Let $Q = (E, G, D, K)$ be a digitization quadruple. Let $C$ be a digitization cell and $g \in C$. Then, $C$ is included in $I^A$, $O^A$ and $D^{-1}(A)$ where $A = \mathcal{D}(g)$.

*Proof.* Let $B \in \mathcal{F}(D)$, $C$ be a connected component of $\partial D^{-1}(B)$ and $g \in C$. We set $A = \mathcal{D}(g)$.

1. $B = \emptyset$.

In this case, $C$ is a connected component of $G \setminus H$. Let $d$ be any digital point. Since $H = \bigcup_{a \in D} H^a$, we derive that $C \cap H^d = \emptyset$. Because $C$ is connected and $H^d$ separates $I^d$ from its exterior (Proposition 2.4-b), we get that $C$ is included in either $I^d$ or in its exterior. Hence, for any $d \in A$, $C$ is included in $I^d$ and, for any $d \notin A$, $C$ is included in $(I^d)^c$. Using Proposition 2.11, we derive that $C$ is included in $I^A$, $O^A$ and $D^{-1}(A)$.

2. $B \neq \emptyset$.

Let us remove the subset $B$ from the digital set $D$: $D' = D \setminus B$. We
denote by $\mathcal{D}'$ the digitization map relative to $Q' = (E, G, D', K)$. Since $C \subset \partial\mathcal{D}^{-1}(B)$, on the one hand

$$C \subset (\partial\mathcal{D}')^{-1}(\emptyset). \qquad (4)$$

On the other hand, for any $h \in C$,

$$\mathcal{D}(h) = \mathcal{D}'(h) \cup B. \qquad (5)$$

In particular, taking $h = g$, and setting $A' = \mathcal{D}'(g)$, $A = A' \cup B$. From Equation (4), we get that $C$ is a connected subset of $G \setminus H_{\partial\mathcal{D}'}$. Thus, $C$ is included in a digitization cell relative to $Q'$ and, according to the first part of the proof, it is included in $I_D^{A'}$, $O_D^{A'}$ and $(\mathcal{D}')^{-1}(A')$. Then, we derive from Equation (5) that $C$ is included in $I_D^A$, $O_D^A$ and $\mathcal{D}^{-1}(A)$. $\square$

Thanks to Lemma 2.15, we directly get that the digitization cells refine the partition $(\mathcal{D}^{-1}(A))_{A \in \mathcal{F}(D)}$ of the group $G$.

**Corollary 2.16.** Let $Q = (E, G, D, K)$ be a digitization quadruple. The digitization map $\mathcal{D}$ is constant on each digitization cell relative to $Q$.

We show on Figure 7 the digitization map by putting color labels on the digitization cells of $G$, each label being associated to a value of the map. The colored cells of Figure 7 are those of $G \setminus H$. Indeed, they have a non-zero area on the figure unlike those of $\partial\mathcal{D}^{-1}(A)$ if $A \neq \emptyset$. Likely, in most practical cases, attention will be focused on these cells. Nevertheless, it may happen that all the information is carried by the digitization hinge. It is the case if the compact set $K$ of the digitization quadruple has an empty interior. Then, $\partial K = K$ and the digitization cells in $G \setminus H$ are all associated to an empty digitization.

<figure><img src="image_9.png" /><figcaption>Figure 7: The digitization map (lower ratios) relative to the digitization quadruple $Q_{\text{ex}}$. The similitudes belonging to the yellow cell produce the same digitization set, namely the singleton $\{o\}$ where $o = (0, 0) \in \mathbb{Z}^2$. The digitizations associated to the other colored cells are shown on the right where the red bullet stands for the point $o$. The symmetry of the digitization map is the subject of the next section (Section 3).</figcaption></figure>

The next proposition gives some properties of the cardinal digitization map.

**Proposition 2.17.** Let $(E, G, D, K)$ be a digitization quadruple. For any $g \in G$,
a) $\sigma(g)$ is a local maximum of $\sigma$;

b) if $g \notin H$, $\sigma$ is locally constant at $g$;

c) if $g \in H$ and the maps $\rho_d$, $d \in D$, are open, $\sigma$ is not locally constant at $g$.

Furthermore, the elements of $G$ at which $\sigma$ is locally constant are dense in $G$.

*Proof.* Let $g \in G$ and $A = \mathcal{D}(g) \in \mathcal{F}(D)$.

a) By Definition 2.10 and Corollary 2.12, $g \in O^A$, which is open. Moreover, for any $h \in O^A$, $\mathcal{D}(h) \subset A$, hence $\sigma(h) \le \sigma(g)$. Therefore, $\sigma(g)$ is a local maximum of $\sigma$.

b) If $g \notin H$, then $g$ belongs to $\mathcal{D}^{-1}(A) \setminus H$ which is open (Corollary 2.12). Since, obviously, $\sigma$ is constant on $\mathcal{D}^{-1}(A)$, we conclude that $\sigma$ is locally constant at $g$.

c) Let us assume that $g \in H$ and the maps $\rho_d$, $d \in D$, are open. Since $g \in H$, there exists $a \in D$ such that $g \in H^a$. Let $U$ be an open neighborhood of $g$. Because $A = \mathcal{D}(g)$, $g$ belongs to $O^A$ which is an open set (Corollary 2.12). Thereby, $V = U \cap O^A$ is an open neighborhood of $g$. Thanks to Proposition 2.4-c, we get that $V \setminus I^a$ is not empty. Let $h \in V \setminus I^a$. Because $h \in V \subset O^A$, $\mathcal{D}(h) \subset \mathcal{D}(g)$ and, because $h \notin I^a$, the digital point $a$, which belongs to $\mathcal{D}(g)$, does not belong to $\mathcal{D}(h)$. We derive that $|\mathcal{D}(h)| < |\mathcal{D}(g)|$. Hence, $\sigma$ is not locally constant at $g$.

Finally, let us consider $g_0 \in G$ where $\sigma$ is not locally constant. Let $U$ be an open neighborhood of $g_0$. Then, there exists $g_1 \in U$ such that $\sigma(g_1) < \sigma(g_0)$ for $\sigma$ has a local maximum at $g_0$. Alike, if $\sigma$ is not locally constant at $g_1$, there exists $g_2 \in U$ such that $\sigma(g_2) < \sigma(g_1) < \sigma(g_0)$. Continuing that way, it can be seen that, because the values of $\sigma$ are non-negative integers, in at most $\sigma(g_0)$ steps an element of $U$ at which $\sigma$ is locally constant is found. Thus, the elements at which $\sigma$ is locally constant are dense in $G$. $\square$

**Proposition 2.18.** The map $\sigma$ is constant on a connected subset of $G$ if and only if $\mathcal{D}$ is constant on this subset.

*Proof.* The “if” part of the statement is obvious. Let us assume that $\sigma$ is constant on the connected set $C$. Since $C$ is connected, it suffices to prove that $\mathcal{D}$ is locally constant on $C$. So, let $g \in C$. We set $A = \mathcal{D}(g)$. By Definition 2.10 and Proposition 2.12, $g \in O^A$, which is open. Thus, $O^A \cap C$ is an open neighborhood of $g$ in $C$. Let $h \in O^A \cap C$. By definition of $O^A$, $\mathcal{D}(h) \subseteq A$. Furthermore, $|\mathcal{D}(h)| = |A|$ by the principal assumption. Then, $\mathcal{D}(h) = A$: $\mathcal{D}$ is locally constant on $C$. $\square$

### 3. The reduced digitization map

When looking at the digitization hinge of Figure 7, an order 4 symmetry appears in the angle direction. Nevertheless, adding a quarter of turn to a direct similitude does change the digitization. Alike, we show below (Figure 8)
the digitization hinge and three digitization cells<fnref n="3" /> relative to the same compact shape $M$ found in the quadruple $Q_{ex}$ but using the translations instead of the direct similitudes as group of actions. The existence of a symmetry is even

<figure><img src="image_10.png" /><figcaption>Figure 8: Left: the digitization hinge (in gray) relative to the shape $M \subset \mathbb{R}^2$ depicted on Figure 1 for the action of translations using the digital set $\mathbb{Z}^2$. Right: the set of three red, resp. green, blue, digital points is the digitization produced by the translations belonging to the red, resp. green, blue, cell of the left part of the figure.</figcaption></figure>

more an evidence. On the right of this latter figure, we show the digitizations associated to the three selected cells. Most of us will consider these digitizations as being “equal”. Indeed, looking at the digitization of a shape on a computer screen, we generally not matter about its position and anyway, the softwares generally center the shape for us. Similarly, depending on the context, one can also accept some rotations, scaling, axial symmetries, ..., in the definition of the equivalence. The purpose of Section 3.1 is to precisely define this equivalence relation in link with the group acting on the space $E$. In Section 3.2, we will see how the equivalence induces the symmetries observed on Figures 7 and 8.

### 3.1. Equivalence relation on digitizations

The fact that we are interested in the digitizations of “a shape” on which a transformation group is acting suggests that this shape “remains the same” whatever the transformation that acts on it. So, it is consistent to assume the same identity persistence in the digital space. That is why below we introduce an equivalence relation which reflects the fact that two digital shapes may be considered identical if one of these shapes is obtained from the other by the action of an element of the group of transformations.

**Definition 3.1** (Equivalence relative $G$). Let $(E, G, D, K)$ be a digitization quadruple. The equivalence relative $G$ is the binary relation on $\mathcal{F}(D)$, noted $=_{G}$, such that

$$ \forall A, B \in \mathcal{F}(D), A =_{G} B \iff \exists g \in G, B = g \cdot A \text{ and } D \setminus B = g \cdot (D \setminus A). \quad (6) $$

Observe that using this equivalence implies that, for instance, two point sets such as ':' and'..' will be considered as identical if $G$ is the group of rigid motions

<footnote n="3">³Actually, a viewpoint on the digitization hinge which is unbounded.</footnote>
<figure><img src="image_11.png" /><figcaption>Figure 9: The digitization map shown in Figure 7 is redrawn using the equivalence relative G: a single color is used for transformations that produce equivalent digitizations.</figcaption></figure>

in $\mathbb{R}^2$ whereas they will considered as distinct if G is the group of translations in $\mathbb{R}^2$. Nevertheless, we must pay attention that the information given by a digital shape is not only due to the points that are turned “on” but also by the points that are turned “off”. For instance, in the case of rotations acting on $\mathbb{R}^2$ equipped with $\mathbb{Z}^2$ as digital subspace, the pairs $P_1 = \{(0,0), (5,0)\}$ and $P_2 = \{(0,0), (3,4)\}$ are not equivalent though there exists rotations that send $P_1$ on $P_2$. Indeed, these latter rotations do not send $D \setminus P_1$ on $D \setminus P_2$: the informations provided by the digitizations cannot be superimposed and compared.

Clearly, the equivalence relative G is an equivalence relation. Using the quotient space $\mathcal{F}(D)/\mathcal{G}$ instead of $\mathcal{F}(D)$ as codomain of the digitization map makes it possible to simplify this map as shown by Figure 9. Nevertheless, even if the number of colors needed to display the digitization map has been reduced thanks to the equality $\mathcal{G}$, the symmetry observed on the cells is still present. Another relation, on the domain side of the map, has to be put forward to exploit the symmetry of the digitization hinge. This the subject of the following section (Section 3.2).

## 3.2. Equivalence relation on transformations

The definition of an equivalence relation on the transformation space rely on the notion of “stabilizer”. Recall that the (setwise) stabilizer subgroup of G with respect to D is the set of all transformations in G that fix D:

$$S = \{g \in G \mid g \cdot D = D\}. \qquad (7)$$

Thanks to the stabilizer, we can simplify the definition of the equivalence relative G. We omit the proof which is elementary.

### Proposition 3.2.

$$\forall A, B \in \mathcal{F}(D), A =_G B \iff \exists g \in S, B = g \cdot A.$$

Let us now define the equivalence relation on the domain side of the digitization map. Two transformations $g_1, g_2$ in G are equal up to (an element of) S, we write $g_1 \sim_D g_2$, if there exists $h \in S$ such that $g_1 = hg_2$. The quotient
Definition 3.4-2 is justified by Proposition 3.3 and the fact that equivalent digitizations have the same cardinal (for the transformations in G are one-to-one correspondences). On Figure 10, we showcase the reduced digitization map for the example used in Section 2.

<figure><img src="image_12.png" /><figcaption>Figure 10: The reduced digitization map corresponding to the digitization map shown in Figure 7.</figcaption></figure>

In the next section, we examine what happens to the digitization hinge and cells in the quotient transformation space.

### 3.3. Quotient hinge

We have to ways to define the digitization hinge in the quotient transformation space: using the projection $\pi_D$ or intrinsically, using $\partial\mathfrak{D}$. We choose to begin with the latter definition and then prove that both definitions coincide. Let us write $\emptyset$ for the class of the empty set with respect to the equivalence relative $G$:

$$ \emptyset = \pi_G(\emptyset). $$

This class is a singleton: it only contains the empty set. Moreover, it is the only singleton in $\mathfrak{F}(D)$ unless the stabilizer $S$ is reduced to the identity element of $G$. In this case, the two equivalence relations $\cong_G$ and $\sim_D$ are equality equivalences and the digitization map cannot be actually reduced, at least in the way envisaged in Section 3.

**Definition 3.5.** Let $(E, G, D, K)$ be a digitization quadruple. The quotient hinge is the set $\mathfrak{H}$ defined by

$$ \mathfrak{H} = \{g \in \mathfrak{G} \mid \partial\mathfrak{D}(g) \neq \emptyset\}. $$

Before looking at the projection of the digitization map, $\pi(H)$, we need to ensure that $H$ is invariant under the equivalence relation $\sim_D$.

**Proposition 3.6.** The digitization hinge $H$ is saturated with respect to the equivalence relation $\sim_D$. In other words,

$$ \forall g, h \in G, g \sim_D h \text{ and } h \in H \implies g \in H. $$
*Proof.* Let $g \in G$ and $h \in H$ such that $g \sim_D h$. Then, there exists $s \in S$ such that $g = sh$. Then,

$$ 
\begin{aligned}
\partial \mathcal{D}(g) &= D \cap (sh) \cdot \partial K \\
&= (s \cdot D) \cap s \cdot (h \cdot \partial K) \quad \text{for } s \in S \\
&= s \cdot (D \cap h \cdot \partial K) \quad \text{for } s \text{ is one-to-one} \\
&\neq \emptyset \quad \text{for } h \in H.
\end{aligned} 
\quad (8) $$

Thus, $g \in H$. □

We can now prove the equivalence of the two ways of defining the quotient hinge.

**Proposition 3.7.** Let $(E, G, D, K)$ be a digitization quadruple. Then,

$$ \mathfrak{H} = \pi_D(H). $$

*Proof.* Let $\mathfrak{g} = S \cdot g$ be a class in $\mathfrak{G}$.

$$ 
\begin{aligned}
\partial \mathfrak{D}(\mathfrak{g}) \neq \emptyset &\iff \partial \mathcal{D}(g) \neq \emptyset \quad (\text{thanks to the commutative diagram 3.4-1}) \\
&\iff g \in H \quad (\text{by definition of H}) \\
&\iff \mathfrak{g} \in \pi_D(H) \quad (\text{by Proposition 3.6}).
\end{aligned} 
\quad \square $$

As in Section 2, the quotient hinge can be divided into segments that separate an inner side from its complement (the quotient space $\mathfrak{G} = G/S$ being equipped with the quotient topology).

**Proposition 3.8.** Let $(E, G, D, K)$ be a digitization quadruple. Then,

$$ \mathfrak{H} = \bigcup_{d \in D} \pi_D(H^d), $$

and, for any $d \in D$, the set $\pi_D(H^d)$ separates $\pi_D(I^d)$ from its exterior.

*Proof.* The first statement of Proposition 3.8 directly results from the equalities $H = \bigcup_{d \in D} H^d$ (Proposition 2.4) and $\mathfrak{H} = \pi_D(H)$ (Proposition 3.7). To obtain the second statement about separations, it suffices to prove that the boundary of $\pi_D(I^d)$ is included in $\pi_D(H^d)$. To do this we proceed in two steps. First we show that $\pi_D(I^d)$ is closed, then we show that $\pi_D(I^d) \setminus \pi_D(H^d)$ is included in the interior of $\pi_D(I^d)$.

* Let us prove that $\pi_D(I^d)$ is a closed set in the quotient topology, that is, $\pi_D^{-1}(\pi_D(I^d))$ is closed in $G$.

$$ 
\begin{aligned}
\pi_D^{-1}(\pi_D(I^d)) &= \{g \mid \exists s \in S, d \in \mathcal{D}(sg)\} \\
&= \{g \mid \exists s \in S, d \in (sg) \cdot K\} \\
&= \{g \mid \exists s \in S, s \cdot d \in g \cdot K\} \\
&= \{g \mid \exists s \in S, s \cdot d \in \mathcal{D}(g)\} \\
&= \bigcup_{s \in S} I^{s \cdot d}.
\end{aligned} 
$$
Since $(I^d)_{d \in D}$ is a locally finite collection of closed sets (Lemma 2.5 and Proposition 2.4), we are done.

* The set $\pi_D(I^d) \setminus \pi_D(H^d)$ is included in $\pi_D(I^d \setminus H^d)$ which is open because $\pi_D$ is an open map and $I^d \setminus H^d$ is an open set (Proposition 2.4) Hence, $\pi_D(I^d) \setminus \pi_D(H^d)$ is included in the interior of $\pi_D(I^d)$.

Thanks to the results shown in the previous items, we conclude straightforwardly. □

Let us state a result that makes the quotient hinge faster to compute than using Proposition 3.8. Indeed, noticing that the stabilizer $S$ of the digital set $D$ acts on $D$, we show in the following proposition that it is enough to pick a representative in each orbit for the action of $S$ on $D$ to get the whole quotient hinge $\mathfrak{H}$. Recall that such a set of representatives is called a *section*.

**Proposition 3.9.** Let $(E, G, D, K)$ be a digitization quadruple. Let $D_0$ be a section of $D$ for the action of the stabilizer of $D$ in $G$. Then,

$$ \mathfrak{H} = \bigcup_{o \in D_0} \pi_D(H^o). $$

*Proof.* Thanks to Proposition 2.4, we know that $H = \bigcup_{d \in D} H^d$. Therefore, $\pi_D(\bigcup_{d \in D_0} H^d) \subset \pi_D(H) = \mathfrak{H}$. Conversely, let us consider an element $\mathfrak{g} \in \mathfrak{H}$ and let $\mathfrak{g}$ a representative of $\mathfrak{g}$. Then, there exists $d \in D$ such that $d \in g \cdot \partial K$. By definition of $D_0$, there exists $d_0 \in D_0$ and $s \in S$ such that $d_0 = s \cdot d$. Thus, $d_0 \in (sg) \cdot \partial K$. In other words, $sg$ belongs to $H^{d_0}$. Thereby, $\pi_D(sg) \in \pi_D(H^{d_0})$. On the other hand, $sg \in Sg$, that is $\pi_D(sg) = \mathfrak{g}$. Then, $\mathfrak{g} \in \bigcup_{d \in D_0} \pi_D(H^d)$. Hence, the result holds. □

We end the section on the quotient hinge by two topological properties inherited from Section 2.

**Proposition 3.10.** Let $(E, G, D, K)$ be a digitization quadruple.

a) The quotient hinge $\mathfrak{H}$ is a closed set.

b) If the maps $\rho_d$ are open for any $d \in D$, then $\mathfrak{H}$ has an empty interior.

*Proof.* a) On the one hand, because the digitization hinge $H$ is closed and projections are open maps, $\pi_D(G \setminus H)$ is an open subset of $\mathfrak{G}$. On the other hand, since the hinge $H$ is saturated with respect to the relation $\sim_D$ (Proposition 3.6), $\pi_D(G \setminus H) = \pi_D(G) \setminus \pi_D(H) = \mathfrak{G} \setminus \mathfrak{H}$. Eventually, we get that $\mathfrak{G} \setminus \mathfrak{H}$ is open. Hence, the result holds.

b) Assuming that the maps $\rho_d$ are open, we proved that the digitization hinge has an empty interior (Proposition 2.4). Let us consider an open subset $\mathfrak{A}$ of $\mathfrak{H}$. We set $A = \pi_D^{-1}(\mathfrak{A})$. Then, because $H$ is saturated with respect to $\sim_D$, we have $A \subset H$. Due to the continuity of $\pi_D$, $A$ is open. Therefore, $A$ is included in the interior of $H$ which is empty. Then $A$ is empty. Eventually, because $\pi_D$ is onto, $\mathfrak{A} = \emptyset$: $\mathfrak{H}$ has an empty interior. □

<figure><img src="image_13.png" /></figure>
### 3.4. Quotient cells

The quotient space $\mathfrak{G}$ being equipped with the quotient topology, we found it difficult to use the connected components of subsets of the quotient space. That is why the definition of the quotient cells does not mimic the definition of the digitization cells. We will see that this leads to a finer partition of the quotient space than that which would be obtained with the connected components.

**Definition 3.11.** Let $Q = (E, G, D, K)$ be a digitization quadruple. The quotient cells relative to $Q$ are the projections of the digitizations cells, that is the sets $\pi_D(C)$ where $C$ is a connected component of $\partial D^{-1}(A)$ for some $A \in \mathcal{F}(D)$.

First, we gather some results about the sets $\mathfrak{D}^{-1}(\mathfrak{A})$ and $\partial \mathfrak{D}^{-1}(\mathfrak{A})$, $\mathfrak{A} \in \mathfrak{F}(D)$.

**Lemma 3.12.** Let $(E, G, D, K)$ be a digitization quadruple and $\mathfrak{A} \in \mathfrak{F}(D)$.

1. Noticing that $\mathfrak{A}$ is a subsset of $\mathcal{F}(D)$, we have

$$\pi_D^{-1}(\mathfrak{D}^{-1}(\mathfrak{A})) = \mathfrak{D}^{-1}(\mathfrak{A}).$$

2. For any $A \in \mathfrak{A}$,

$$\mathfrak{D}^{-1}(\mathfrak{A}) = \pi_D(\mathfrak{D}^{-1}(A)).$$

3. In particular,

$$\partial \mathfrak{D}^{-1}(\emptyset) = \mathfrak{G} \setminus \mathfrak{H}.$$

4. The boundary of $\mathfrak{D}^{-1}(\mathfrak{A})$ is included in $\mathfrak{H}$.

5. The collection $(\mathfrak{D}^{-1}(\mathfrak{A}))_{\mathfrak{A} \in \mathfrak{F}(D)}$ is locally finite.

*Proof.* Let $\mathfrak{A} \in \mathfrak{F}(D)$.

1. According to Diagram 3.4-1,

$$(\pi_D^{-1}(\mathfrak{D}^{-1}(\mathfrak{A}))) = \mathfrak{D}^{-1}(\pi_G^{-1}(\mathfrak{A})).$$

Since $\pi_G^{-1}(\mathfrak{A}) = \mathfrak{A}$, we are done.

2. Let $A \in \mathfrak{A}$ and $\mathfrak{g} \in \mathfrak{G}$. Firstly, let us assume $\mathfrak{D}(\mathfrak{g}) = \mathfrak{A}$. We pick some $g \in \mathfrak{g}$. Then, according to Diagram 1, $\pi_G(\mathfrak{D}(g)) = \mathfrak{A}$. That is, $\mathfrak{D}(g) =_G A$. Therefore, there exists $s \in S$ such that $\mathfrak{D}(g) = s \cdot A$ (Proposition 3.2), which is equivalent to $s^{-1}g \in \mathfrak{D}^{-1}(A)$ (for $t \cdot \mathfrak{D}(g) = \mathfrak{D}(tg)$ for any $t \in S$). Since $\pi_D(s^{-1}g) = \pi_D(g) = \mathfrak{g}$, we conclude that $\mathfrak{g} \in \pi_D(\mathfrak{D}^{-1}(A))$. Conversely, let us assume $\mathfrak{g} \in \pi_D(\mathfrak{D}^{-1}(A))$. Then, there exists $g \in \mathfrak{g}$ such that $g \in \mathfrak{D}^{-1}(A)$. From Diagram 1, we get that $\mathfrak{D}(\mathfrak{g}) = \pi_G(\mathfrak{D}(g))$. Since $g \in \mathfrak{D}^{-1}(A)$, $\mathfrak{D}(g) = A$. Thus, $\mathfrak{D}(\mathfrak{g}) = \pi_G(A) = \mathfrak{A}$. We are done.

3. According to the previous item applied to the quadruple $(E, G, D, \partial K)$, $\partial \mathfrak{D}^{-1}(\emptyset) = \pi_D(\partial \mathfrak{D}^{-1}(\emptyset))$. Since $\partial \mathfrak{D}^{-1}(\emptyset)$ is equal to $G \setminus H$ and $H$ is saturated with respect to $\sim_D$, we derive that $\partial \mathfrak{D}^{-1}(\emptyset) = \pi_D(G) \setminus \pi_D(H)$, that is $\partial \mathfrak{D}^{-1}(\emptyset) = \mathfrak{G} \setminus \mathfrak{H}$.

4. Let us prove that the closure of $\mathfrak{D}^{-1}(\mathfrak{A})$ is included in $\mathfrak{D}^{-1}(\mathfrak{A}) \cup \mathfrak{H}$ and the interior of $\mathfrak{D}^{-1}(\mathfrak{A})$ includes $\mathfrak{D}^{-1}(\mathfrak{A}) \setminus \mathfrak{H}$.
• Thanks to Item 1 and because $H$ is saturated and $\mathfrak{H} = \pi_D(H)$ (Proposition 3.6 and 3.7), we have

$$ \begin{aligned} \pi_D^{-1}(\mathfrak{D}^{-1}(\mathfrak{A}) \cup \mathfrak{H}) &= \pi_D^{-1}(\mathfrak{D}^{-1}(\mathfrak{A})) \cup \pi_D^{-1}(\mathfrak{H}) \\ &= \bigcup_{A \in \mathfrak{A}} \mathfrak{D}^{-1}(A) \cup H. \end{aligned} $$

Since $(\mathfrak{D}^{-1}(A))_A$ is a locally finite collection and the sets $\mathfrak{D}^{-1}(A) \cup H$ are closed (Corollary 2.12), we derive that $\pi_D^{-1}(\mathfrak{D}^{-1}(\mathfrak{A}) \cup \mathfrak{H})$ is a closed subset of $G$. Hence, $\mathfrak{D}^{-1}(\mathfrak{A}) \cup \mathfrak{H}$ is closed for the quotient topology. Since, it contains $\mathfrak{D}^{-1}(\mathfrak{A})$, it contains its closure.

• Thanks to Item 2 and because $\mathfrak{H} = \pi_D(H)$, we have $\mathfrak{D}^{-1}(\mathfrak{A}) \setminus \mathfrak{H} = \pi_D(\mathfrak{D}^{-1}(A)) \setminus \pi_D(H)$. Then, $\mathfrak{D}^{-1}(\mathfrak{A}) \setminus \mathfrak{H} \subset \pi_D(\mathfrak{D}^{-1}(A) \setminus H)$. We have proved in Corollary 2.12, that $\mathfrak{D}^{-1}(A) \setminus H$ is open. Furthermore, the map $\pi_D$ is open. Thus, $\pi_D(\mathfrak{D}^{-1}(A) \setminus H)$ is open. As an open subset of $\mathfrak{D}^{-1}(\mathfrak{A})$, $\pi_D(\mathfrak{D}^{-1}(A) \setminus H)$ is included in the interior of $\mathfrak{D}^{-1}(\mathfrak{A})$. Therefore, $\mathfrak{D}^{-1}(\mathfrak{A}) \setminus \mathfrak{H}$ is included in the interior of $\mathfrak{D}^{-1}(\mathfrak{A})$.

Eventually, the quotient hinge $\mathfrak{H}$, which is equal to $(\mathfrak{D}^{-1}(\mathfrak{A}) \cup \mathfrak{H}) \setminus (\mathfrak{D}^{-1}(A) \setminus \mathfrak{H})$, contains $\text{cl} \mathfrak{D}^{-1}(\mathfrak{A}) \setminus (\mathfrak{D}^{-1}(\mathfrak{A}))^\circ$, that is, contains the boundary of $\mathfrak{D}^{-1}(\mathfrak{A})$.

5. Let $g \in \mathfrak{G}$ and $g \in \mathfrak{g}$. Since the collection $(\mathfrak{D}^{-1}(A))_A$ is locally finite (Corollary 2.12), there exists an open neighborhood $U$ of $g$ that intersects finitely many sets $\mathfrak{D}^{-1}(A)$ where $A \in \mathcal{F}(D)$. We set $\mathfrak{A} = \pi_D(U)$. Since $\pi_D$ is an open map, $\mathfrak{A}$ is an open neighborhood of $g$. Besides, according to the definition of $\mathfrak{D}$ (Diagram 1), $\mathfrak{A}$ intersects $\mathfrak{D}^{-1}(\mathfrak{A})$ where $\mathfrak{A} \in \mathfrak{F}(D)$ if and only if $U$ intersects $\mathfrak{D}^{-1}(A)$ for some $A \in \mathfrak{A}$. We derive that $\mathfrak{A}$ intersects finitely many sets of the collection $(\mathfrak{D}^{-1}(\mathfrak{A}))_{\mathfrak{A} \in \mathfrak{F}(D)}$ which prove that this collection is locally finite. $\square$

Observe that applying Lemma 3.12 to the quadruple $(E, G, D, \partial K)$, we obtain similar results for the map $\partial \mathfrak{D}$.

Below, we show that, for any $\mathfrak{A} \in \mathfrak{F}(D)$, the digitization cells included in $\partial \mathfrak{D}^{-1}(\mathfrak{A})$ coincide with the connected components of $\partial \mathfrak{D}^{-1}(\mathfrak{A})$. In other words, it is equivalent to define the digitization cells as the components of the sets $\partial \mathfrak{D}^{-1}(A)$, $A \in \mathcal{F}(D)$ or as the components of $\partial \mathfrak{D}^{-1}(\mathfrak{A})$, $\mathfrak{A} \in \mathfrak{F}(D)$.

**Lemma 3.13.** Let $(E, G, D, K)$ be a digitization quadruple. Let $\mathfrak{A} \in \mathfrak{F}(D)$. The connected components of $\partial \mathfrak{D}^{-1}(\mathfrak{A})$ are the connected components of the sets $\partial \mathfrak{D}^{-1}(A)$, $A \in \mathfrak{A}$.

*Proof.* Let $C$ be a connected component of $\bigcup_{A \in \mathfrak{A}} \partial \mathfrak{D}^{-1}(A)$. The map $\partial \sigma: g \in G \mapsto |\partial \mathfrak{D}(g)|$ is constant on $C$ (because all the sets $A$ in $\mathfrak{A}$ share the same cardinal). Thus, $\partial \mathfrak{D}$ is constant on $C$ for $C$ is connected (Proposition 2.18). We derive that $C$ is a connected subset of $\partial \mathfrak{D}^{-1}(A)$ for some $A \in \mathfrak{A}$. Moreover, as a connected subset, $C$ is maximal in $\bigcup_{A \in \mathfrak{A}} \partial \mathfrak{D}^{-1}(A)$. Hence, it is a fortiori maximal in $\partial \mathfrak{D}^{-1}(A)$: $C$ is a connected component of $\partial \mathfrak{D}^{-1}(A)$.
Conversely, let us assume that $C$ is a connected component of $\partial\mathcal{D}^{-1}(B)$ for some $B \in \mathfrak{A}$. Then $C$ is included in a connected component $C'$ of $\bigcup_{A \in \mathfrak{A}} \partial\mathcal{D}^{-1}(A)$. Since we just prove that $C'$ is also a component of $\partial\mathcal{D}^{-1}(B')$ for some $B' \in \mathfrak{A}$, we easily derive that $B' = B = \partial\mathcal{D}(g)$ for any $g \in C \subset C'$. Furthermore, $C$ and $C'$, which overlap, are equal. Eventually, we get that $C$ is a connected component of $\bigcup_{A \in \mathfrak{A}} \partial\mathcal{D}^{-1}(A)$. $\square$

We now give results linking the quotient cells with the digitizations cells in $G$.

**Proposition 3.14.** Let $(E, G, D, K)$ be a digitization quadruple.

1. Let $\mathfrak{A} \in \mathfrak{F}(D)$. The connected components of $\partial\mathfrak{D}^{-1}(\mathfrak{A})$ are unions of quotient cells.

2. The quotient cells form a partition of $\mathfrak{G}$.

3. Let $\mathfrak{A} \in \mathfrak{F}(D)$. If, for any $A \in \mathfrak{A}$, $\partial\mathcal{D}^{-1}(A)$ has a finite number of connected components, then the quotient cells coincide with the connected components of $\partial\mathfrak{D}^{-1}(\mathfrak{A})$

*Proof.* 1. Let $\mathfrak{C}$ be a connected component of $\partial\mathfrak{D}^{-1}(\mathfrak{A})$ for some $\mathfrak{A} \in \mathfrak{F}(D)$. We pick an element $c$ in $C = \pi_D^{-1}(\mathfrak{C})$. Let us prove that the whole digitization cell containing $c$, written $C_c$, is included in $C$. Applying Lemma 3.12 (Item 1) to the quadruple $(E, G, D, \partial K)$, we get that there exists $A \in \mathcal{F}(D)$ such that $c \in \partial\mathcal{D}^{-1}(A)$. Then $C_c$ is a connected component of $\partial\mathcal{D}^{-1}(A)$. Thanks to the continuity of the projection $\pi_D$, $\pi_D(C_c)$ is connected. Furthermore, it is included in $\pi_D(\partial\mathcal{D}^{-1}(A))$ which is equal to $\partial\mathfrak{D}^{-1}(\mathfrak{A})$ (from Lemma 3.12). Thus, the quotient cell $\pi_D(C_c)$ is included in the component of $\partial\mathfrak{D}^{-1}(\mathfrak{A})$ containing $\pi_D(c)$, that is in $\mathfrak{C}$. Thereby, $\mathfrak{C} = \pi_D(C)$ is an union of quotient cells.

2. Since the digitization cells form a partition of $G$, it is enough to prove that two quotient cells are equal or disjoint. So, let $\pi_D(C_1), \pi_D(C_2)$ be two digitization cells. Assuming $\pi_D(C_1) \cap \pi_D(C_2) \neq \emptyset$, let $g_1 \in C_1$ and $g_2 \in C_2$ such that $\pi_D(g_1) = \pi_D(g_2)$. We set $A_1 = \partial\mathcal{D}(g_1)$ and $A_2 = \partial\mathcal{D}(g_2)$. Then, there exists $s \in S$ such that $g_2 = sg_1$ (which implies $A_2 = s \cdot A_1$). Since, $g \in \partial\mathcal{D}^{-1}(A_1) \mapsto sg \in \partial\mathcal{D}^{-1}(A_2)$ is an homeomorphism, $sC_1$ is a component of $\partial\mathcal{D}^{-1}(A_2)$ that intersects $C_2$. Therefore, $sC_1 = C_2$ and $\pi_D(C_1) = \pi_D(C_2)$.

3. Let $\mathfrak{A} \in \mathfrak{F}(D)$. Asumme that $\partial\mathcal{D}^{-1}(A)$ has a finite number of connected components for any $A \in \mathfrak{A}$. Then, because the collection $(\partial\mathcal{D}^{-1}(A))_{A \in \mathcal{F}(D)}$ is locally finite (Corollary 2.12), the collection formed by the digitization cells included in $\partial\mathcal{D}^{-1}(\mathfrak{A})$ is also locally finite. Since these digitization cells are the connected components of $\partial\mathcal{D}^{-1}(\mathfrak{A})$ (Lemma 3.13), and their collection is locally finite, they are open subsets of $\partial\mathcal{D}^{-1}(\mathfrak{A})$. Now, observe that the restriction of $\pi_D$ to $\partial\mathcal{D}^{-1}(\mathfrak{A})$ is open because $\partial\mathcal{D}^{-1}(\mathfrak{A})$ is saturated with respect to the relation $\sim_D$. Then, the quotient cells in $\partial\mathfrak{D}^{-1}(\mathfrak{A})$ are open. Because $\pi_D$ is continuous, they are also connected. Hence, they form a partition of open connected subsets of $\partial\mathfrak{D}^{-1}(\mathfrak{A})$. We derive that the quotient cells are the connected components of $\partial\mathfrak{D}^{-1}(\mathfrak{A})$. $\square$
We end the section on quotient cells by topological properties inherited from Section 2.

**Proposition 3.15.** Let $(E, G, D, K)$ be a digitization quadruple. The reduced digitization map $\mathcal{D}$ and its quotient cells have the following properties:

a) the map $\mathcal{D}$ is constant on the quotient cells;

b) the map $\mathfrak{s}$ is constant on a connected subset of $\mathcal{G}$ if and only if $\mathcal{D}$ is constant on this subset;

c) We have the following local properties:

i. for any $g \in \mathcal{G}$, either the map $\mathfrak{s}$ is locally constant at $g$ or $g \in \mathfrak{h}$ and $\mathfrak{s}$ has a local maximum at $g$;

ii. if the maps $\rho_d$ are open for any $d \in D$, then $\mathfrak{s}$ is locally constant at $g \in \mathcal{G}$ if and only if $g \notin \mathfrak{h}$.

iii. the elements of $\mathcal{G}$ at which $\mathfrak{s}$ is locally constant are dense in $\mathcal{G}$;

Moreover, if $G$ is locally connected,

d) the quotient cells in $\mathcal{G} \setminus \mathfrak{h}$ are open;

e) the boundaries of the connected components of $\mathcal{G} \setminus \mathfrak{h}$ are included in $\mathfrak{h}$.

*Proof.* a) This a straightforward consequence of Corollary 2.16 and of the definition of the quotient cells.

b) We prove the “only if” part (the “if” part is obvious). The proof is almost the same as for Proposition 2.18. Let $\mathcal{C}$ be a connected subset of $\mathcal{G}$ on which $\mathfrak{s}$ is constant. Since $\mathcal{C}$ is connected, it is enough to prove that $\mathcal{D}$ is locally constant on $\mathcal{C}$. So, let $g \in \mathcal{C}$ and $g \in \mathfrak{h}$. We set $A = \mathcal{D}(g)$. By Definition 2.10 and Corollary 2.12, $g \in \mathcal{O}^A$, which is open. Thus, $\pi_D(\mathcal{O}^A) \cap \mathcal{C}$ is an open neighborhood of $g$ in $\mathcal{C}$ (for $\pi_D$ is open). Let $h \in \pi_D(\mathcal{O}^A) \cap \mathcal{C}$ and $h \in \mathfrak{h} \cap \mathcal{O}^A$. By definition of $\mathcal{O}^A$, $\mathcal{D}(h) \subseteq A$. Furthermore, $|\mathcal{D}(h)| = |A|$ by the principal assumption and Diagram 2. Then, $\mathcal{D}(h) = \mathcal{D}(g) = A$ and $\mathcal{D}(h) = \mathcal{D}(g)$ according to Diagram 1. Therefore, $\mathcal{D}$ is locally constant at $g$ and thereby constant on $\mathcal{C}$.

c) i-ii. Let $g \in \mathcal{G}$ and $g$ be a representative of $g$ (i.e. $\pi_D(g) = g$). By Proposition 2.17, the map $\sigma$ is locally constant at $g$ or $g \in H$, the disjunction being exclusive if the maps $\rho_d$ are open for any $d \in D$. Furthermore, if $g \in H$, $\sigma(g)$ is a local maximum. Because projections are open maps and $g \in H$ if and only if $g \in \mathfrak{h}$ (Propositions 3.6 and 3.7), we get that $\mathfrak{s}$ is locally constant at $g$ or (xor if the maps $\rho_d$ are open) $g \in \mathfrak{h}$. In the latter case, $\mathfrak{s}(g)$ is a local maximum.

iii. Regarding the density of the elements in $\mathcal{G}$ at which $\mathfrak{s}$ is locally constant, the proof is the same as in Proposition 2.17.

We now assume that $G$ is locally connected. Then, the quotient set $\mathcal{G}$ is itself locally connected.
d) The quotient cells in $\mathcal{G} \setminus \mathcal{H}$ are the projections of the digitization cells in $G \setminus H$. We saw (Proposition 2.9) that $G \setminus H$ is open. Then, because $G$ is locally connected, the components of $G \setminus H$ are open in $G$. We derive that their projections on $\mathcal{G}$ are open in $G$ (for $\pi_D$ is an open map).

e) Noting that a quotient space obtained from a locally connected space is itself locally connected, the proof is the same as that of Proposition 2.14 □

# 4. Examples and counterexamples

In this section, we showcase the digitization hinges and cells for some well-known groups acting on $\mathbb{R}^2$. The digital set is $\mathbb{Z}^2$ and the hinges and cells are all related to the compact set $M$ shown in Figure 1.

We will also discuss what can happen when the assumptions of our results are not met.

We begin by giving another view of the hinge relative to the quadruple $Q_{\text{ex}}$. Indeed, in Sections 2 and 3 we used a cylinder to represent the space of plane linear direct similitudes. Below, the complex plane (deprived of its origin) is used instead.

## 4.1. Linear direct similitudes (complex plane view)

We denote by $\mathbb{C}$, resp. $\mathbb{C}^*$, the complex plane, resp. the complex plane deprived of its origin. Given a linear direct similitude $g$, we write $\bar{g}$ for the complex number representing $g$ in $\mathbb{C}^*$. Alike, a digital point $d \in \mathbb{R}^2$ is represented by the Gaussian integer $\bar{d}$. Let us explain how we compute a hinge segment $H^d$, $d \in D$, in $\mathbb{C}^*$. Let $\gamma_0: [0, 1] \to \mathbb{C}$ be a parametric representation of $\partial M$ in the complex plane. Since the origin of $\mathbb{R}^2$ does not belong to $\partial M$, we have

$$ 
\begin{align*}
g \in H^d &\iff d \in g \cdot \partial M \\
&\iff \exists t \in [0, 1], \bar{g} \times \gamma(t) = \bar{d} \\
&\iff \exists t \in [0, 1], \bar{g} = \bar{d}/\gamma(t).
\end{align*}
$$

It follows that, for any $d \neq 0$, $t \in [0, 1] \mapsto d/\gamma(t) \in \mathbb{C}^*$ is a parametrization of the hinge segment $H^d$ (in $\mathbb{C}^*$). If $d = 0$, $H^d$ is empty. Knowing that the whole hinge $H$ is equal to $\bigcup_{d \in D} H^d$ (Proposition 2.4), it is easy to determine the hinge segments $H^d$ that have to be plotted to get the view of $H$ in a given viewport. The resulting plot is shown in Figure 11 for the same viewport as in Figure 3. On Figure 11 we also represent the dual hinge $H^*$ which is defined by

$$ H^* = \psi(H) = \{g \in G \mid g \cdot D \cap \partial K \neq \emptyset\}. \qquad (9) $$

Regarding the digitization quadruple $Q_{\text{ex}}$, the dual hinge is the union of the parametric curves $t \in [0, 1] \mapsto \gamma(t)/d$ where $\gamma$ is a parametrization of $\partial M$, the union being over all non-zero Gaussian integers $d$.
<figure><img src="image_14.png" /><figcaption>Figure 11: (a) The digitization hinge relative to the quadruple $Q_{ex}$ (Equation (2)). The direct similitude space is represented by the complex plane deprived of its origin. The digitization hinge segment $H^d$, where $d = (1, 0)$, is depicted in blue. (b) The dual of the hinge shown in (a). The parametric equation of the segment $H^d$ (in blue) in $H^*$ is the same as the parametrization of $\partial M$ in $\mathbb{C}$. (c) The reduced digitization map with the same viewport and the same cells highlighted as in Figure 10.</figcaption></figure>

## 4.2. Translations

The stabilizer of the digital set $D = \mathbb{Z}^2$ is the group of integer translations. Its action on $D$ is transitive. Then, the quotient hinge is obtained by projecting a single hinge segment $H^d$, $d \in D$ (Proposition 3.9). The reduced digitization map is showcased in Figure 12.

<figure><img src="image_15.png" /><figcaption>Figure 12: The reduced digitization map for the action of translations over the shape $M$ depicted in Figure 1. The quotient space is a torus which was unstitched along the red border line. Notice that the blue region is a singleton containing the translations with vectors $(1/2 + u, 1/2 + v)$ where $u, v \in \mathbb{Z}$ (which are all equivalent for the relation $\sim_D$).</figcaption></figure>

## 4.3. Linear scalings

In the case of scalings, the stabilizer of the digital set $D = \mathbb{Z}^2$ is trivial (no scaling but the identity transformation preserves the digital set). The digitization map for the action of the linear scalings on the shape depicted in Figure 1 is showcased in Figure 13.

## 4.4. Special orthogonal group

The space $SO(2)$ of linear rotations is homeomorphic to $S^1$ and the stabilizer $S$ of the digital set $\mathbb{Z}^2$ is the subgroup generated by the right angle rotation (cyclic group $C^4$ of 4-fold rotations). Hence, the quotient space $G/S$ is also homeomorphic to $S^1$. The reduced digitization map related to the compact shape $M$ is showcased in Figure 14.
<figure><img src="image_16.png" /><figcaption>Figure 14: The reduced digitization map for the action of the linear rotations on the compact *M* depicted in Figure 1.</figcaption></figure>

<figure><img src="image_17.png" /></figure>

### 4.5. Orthogonal group

The orthogonal group has two connected components (rotations and symmetries) and the stabilizer *S* of the digital set Z² is the subgroup generated by the right angle rotation and the symmetry along the *x*-axis. Hence, the quotient space *G*/*S* is connected, homeomorphic to S¹. In the particular case of the shape *M* showcased in Figure 1, the reduced digitization map is the same as that due to rotations (see Figure 14).

### 4.6. Special Euclidean Group

The special Euclidean group of R² is composed of affine rotations and translations. The stabilizer of Z² is the subgroup formed by the integer translations and the affine rotations whose angles are multiple of π/2. Thereby, the quotient space is homeomorphic to S¹ × S¹ × S¹. On Figure 15, we show the quotient hinge for the shape *M* (Figure 1) and the digital set Z².

### 4.7. Non-open maps $\rho_d$, $d \in D$

a) We assume a digitization triple ($\mathbb{R}^n$, $G$, $\mathbb{Z}^n$) where $G$ is a group of linear transformations. Let $o = (0, \dots, 0) \in \mathbb{R}^n$. Since $G$ is composed of linear maps, the orbit of $o$ is $\{o\}$. In other words, $\rho_o(G) = \{o\}$. Thus, $\rho_o$ is not an open map. Now, if $o \in \partial K$, then $H^o = G$. Thereby, we have a counterexample of Proposition 2.4-c if the hypothesis “the map $\rho_d$ is open” is removed.

<footnote n="4">⁴The animation works with several pdf readers but not all. See the documentation of the animate package.</footnote>
<figure><img src="image_18.png" /><figcaption>Figure 15: The quotient hinge of the special Euclidean group acting on the compact set $M$ depicted in Figure 1 using $\mathbb{Z}^2$ as digital set. The quotient space is represented by a cube whose opposite faces have to be identified. The animated graphic travel through the cube along the angle axis (the two other axes encode the translation parameter).</figcaption></figure>

Furthermore, $H^o = G$ implies $H = G$ showing us that Proposition 2.7 could fail if, for just one digital point $d$, $\rho_d$ is not open.

In the case of linear transformations, a workaround for the above situation is easily found. It is enough to remove the origin $o$ from the digital set $D$ to get rid of the mentioned drawback. Let us describe below another example where $G$ needs not be linear.

b) We assume the digitization triple $(E, G, D)$ where $E$ is connected, $G$ is compact and Hausdorff and the action of $G$ on $E$ is not transitive (for instance $E = \mathbb{R}^n$, $G = SO(n)$ and $D = \mathbb{Z}^n$). By continuity, the orbits for the action of $G$ are compact and thus, closed. Since $E$ is connected and the action of $G$ is not transitive, the orbits cannot be open (the only clopen proper subset of $E$ is the empty set): no map $\rho_d$ is open. If the boundary of the compact set $K$ which is digitized is the orbit of some $d \in D$, then $H^d$ and $H$ are equal to $G$. Therefore, the interior of $H$ is not empty.

Observe that if $\partial K$ is an orbit of a point $e \in E$ and $\partial K$ does not meet $D$, then $H^d$ is empty for any $d \in D$ (orbits do not intersect). In this case, $H = \emptyset$. If, furthermore, $G$ is connected, the digitization map has only one cell: there is just one digitization.

c) In the previous items, we putted forward examples in which the digitization hinge equals the whole transformation space due to the removal of the assumption “the maps $\rho_d, d \in D$, are open”. Then, because the set of elements of $G$ at which the cardinal digitization map $\sigma$ (or $\mathfrak{s}$) is locally constant is dense in $G$ (or $\mathfrak{G}$), Propositions 2.17-c) and 3.15-c) fail: there exists a point in the (reduced) digitization hinge where the cardinal digitization map is locally constant. On Figure 16, we show another example in which the digitization hinge is not equal to $G$ and the cardinal digitization map is locally constant at some points in the hinge. In this example, the maps $\rho_d, d \in D$, are not open (mainly because the action of $G$ is not transitive) and the interior of the hinge $H$ is not empty.

### 4.8. Non-locally connected transformation group

When local connectedness is not assumed regarding the action group $G$, Proposition 2.14 may fails as shown by the following example. Let us assume a digitization triple $(\mathbb{R}^n, T_Q^n, \mathbb{Z}^n)$ where $T_Q^n$ denotes the translations acting on $\mathbb{R}^n$ with a rational vector. Then, the transformation group $T_Q^n$ is totally disconnected and, whatever the choice of the compact set $K$, the digitizations cells are
<figure><img src="image_19.png" /><figcaption>Figure 17: (Adapted from [BM19])</figcaption></figure>

Left: a triangular shape of $\mathbb{R}^2$ is digitized by its intersection with $\mathbb{Z}^2$. Right: the action of the translation group produces a reduced digitization map on the torus $S^1 \times S^1$. In the two yellow cells the triangle is digitized as a singleton whereas it is digitized as a pair (congruent to the pair $\{(0,0), (1,0)\}$) in the two red cells.

<figure><img src="image_20.png" /><figcaption>Figure 18: Left: the compact $M'$: a unit square with a side replaced by the curve $t \mapsto t \sin(4\pi/t)$. The four red points compose the digitization of $M'$. Right: the digitization hinge $H$ for the action of the translation group $T^2$ on $M'$ is in blue. The red digitization cells in $T^2 \setminus H$, which are infinitely numerous, map to the empty digitization.</figcaption></figure>

# 5. Conclusion

In this paper, we generalized previous works about the variability of a simple digitization process known as “Gaussian digitization”. Indeed, in [MB18], we looked at the sets of integer points contained in planar bodies bounded by a Jordan curve which are displaced thanks to translations. Here, we tried to find the broadest framework to define Gaussian digitizations up to object displacements. To this end, we extended the study not only to other action groups over $\mathbb{R}^n$ but also to topological groups continuously acting on locally compact Hausdorff spaces. The accent was put on a topological description of the partition of the action group induced by the preimages of the digitizations.
Future work includes solving a technical issue: is the projection of a digitization cell on the quotient space $G$ a quotient cell (not just a part of a quotient cell)? At this point, we found neither proof nor counterexample. We would also like to look at other (more sophisticated) digitization processes. This required to restrict the space of the objects that are digitized. For instance, Ronse and Tajine [RT00, RT01, TR02] studied Hausdorff discretizations in metric spaces. They showed that many well-known digitization processes fall under this Hausdorff scheme. Hence, metric spaces are good candidates for such an extension to other type of digitizations. Combinatorics is another aspect worth exploring. In [BM19], we used the notion of “toggling boundary” to propose an upper bound on the number of digitizations, up to translations, of a plane object (using $\mathbb{Z}^2$ as digital set). The toggling boundary is composed of the digital points that can enter or leave the digitization when the digitized object is translated by a vector belonging to $[0, 1)^2$, that is to a section of $\mathbb{R}^2$ for the quotient by $\mathbb{Z}^2$. It should be possible to extend this notion to the framework of this article and to link it with the “quotient cells” defined in Section 3.4.

## Acknowledgement

This article originates from an internship conducted many years ago (in 2017) by a student, Léo Bouaillon, and supervised by Étienne Baudrier and the author. The aim was to study all the discretizations of a planar object subjected to affine rotations. Léo did a great job, but unfortunately we didn’t have time to follow up. Retirement gives me the opportunity to expand on Léo’s work.

## References

[ABLP09] Amihood Amir, Ayelet Butman, Moshe Lewenstein, and Ely Porat. Real two dimensional scaled matching. Algorithmica, 53(3):314–336, 2009.

[BM19] Etienne Baudrier and Loïc Mazo. Combinatorics of the Gauss digitization under translation in 2D. Journal of Mathematical Imaging and Vision, 2019.

[DS98] Matthew Dickerson and Daniel Scharstein. Optimal placement of convex polygons to maximize point containment. Comput. Geom., 11(1):1–16, 1998.

[FNU02] Kimmo Fredriksson, Gonzalo Navarro, and Esko Ukkonen. Optimal exact and fast approximate two dimensional pattern matching allowing rotations. In Alberto Apostolico and Masayuki Takeda, editors, Combinatorial Pattern Matching, pages 235–248, Berlin, Heidelberg, 2002. Springer Berlin Heidelberg.
[FU98] Kimmo Fredriksson and Esko Ukkonen. A rotation invariant filter for two-dimensional string matching. In Martin Farach-Colton, editor, *Combinatorial Pattern Matching*, pages 118–125, Berlin, Heidelberg, 1998. Springer Berlin Heidelberg.

[HL08] Christian Hundt and Maciej Liskiewicz. Combinatorial bounds and algorithmic aspects of image matching under projective transformations. In *Mathematical Foundations of Computer Science 2008, 33rd International Symposium, MFCS 2008, Torun, Poland, August 25-29, 2008, Proceedings*, pages 395–406, 2008.

[Hun12] Christian Hundt. *On the computational complexity of projective image matching*. PhD thesis, University of Lübeck, 2012.

[HŽ04] M. N. Huxley and Jovisa Žunić. On the number of digitizations of a disc depending on its position. In *Combinatorial Image Analysis, 10th Int Workshop, IWCIA 2004, New Zealand*, pages 219–231, 2004.

[HŽ06] M. N. Huxley and Jovisa Žunić. Different Digitisations of Displaced Discs. *Foundations of Computational Mathematics*, 6(2):255–268, apr 2006.

[HŽ10] M. N. Huxley and Jovisa Žunić. The number of configurations in lattice point counting. In *Forum Mathematicum*, 22(1):127–152, 2010.

[HŽ13] M. N. Huxley and Jovisa Žunić. The number of configurations in lattice point counting. In *Proceedings of the London Mathematical Society*, 107(6):1331–1352, 2013.

[HŽ16] M. N. Huxley and Jovisa Žunić. The Number of Different Digital N-Discs. *Journal of Mathematical Imaging and Vision*, 56(3):403–408, 2016.

[KMM04] Tomasz Kaczynski, Konstantin Mischaikow, and Marian Mrozek. *Computational homology*, volume 157 of *Applied Mathematical Sciences*. Springer, 2004.

[KR04] R. Klette and A. Rosenfeld. *Digital Geometry*. Morgan Kaufman, 2004.

[KRR92] T.Y. Kong, A.W. Roscoe, and A. Rosenfeld. Concepts of digital topology. *Topology and its Applications*, 46:219–262, 1992.

[LV94] Gad M. Landau and Uzi Vishkin. Pattern matching in a digitized image. *Algorithmica*, 12(4/5):375–408, 1994.

[MB18] Loïc Mazo and Étienne Baudrier. Object digitization up to a translation. *J. Comput. Syst. Sci.*, 95:193–203, 2018.
[NKPT13] Phuc Ngo, Yukiko Kenmochi, Nicolas Passat, and Hugues Talbot. Combinatorial structure of rigid transformations in 2d digital images. *Comput. Vis. Image Underst.*, 117(4):393-408, 2013.

[NKPT14] Phuc Ngo, Yukiko Kenmochi, Nicolas Passat, and Hugues Talbot. Topology-preserving conditions for 2d digital images under rigid transformations. *J. Math. Imaging Vis.*, 49(2):418-433, 2014.

[NKS+17] Phuc Ngo, Yukiko Kenmochi, Akihiro Sugimoto, Hugues Talbot, and Nicolas Passat. Discrete rigid registration: A local graph-search approach. *Discret. Appl. Math.*, 216:461-481, 2017.

[RMT19] Christian Ronse, Loïc Mazo, and Mohamed Tajine. Correspondence between topological and discrete connectivities in Hausdorff discretization. *Math. Morphol. Theory Appl.*, 3(1):1-28, 2019.

[RT00] Christian Ronse and Mohamed Tajine. Discretization in Hausdorff space. *Journal of Mathematical Imaging and Vision*, 12(3):219-242, 2000.

[RT01] Christian Ronse and Mohamed Tajine. Hausdorff discretization for cellular distances and its relation to cover and supercover discretizations. *Journal of Visual Communication and Image Representation*, 12(2):169-200, 2001.

[TR02] Mohamed Tajine and Christian Ronse. Topological properties of Hausdorff discretization, and comparison to other discretization schemes. *Theoretical Computer Science*, 283(1):243-268, 2002.
<ce:title>Discrete Geometry for Computer Imagery</ce:title>.