# 2D Bijective rigid rotation: quantitative and qualitative study

Stéphane Breuils, David Coeurjolly, Jacques-Olivier Lachaud

► To cite this version:

Stéphane Breuils, David Coeurjolly, Jacques-Olivier Lachaud. 2D Bijective rigid rotation: quantitative and qualitative study. Journal of Mathematical Imaging and Vision, 2025, 67 (4), pp.37. 10.1007/s10851-025-01252-y . hal-05125278

HAL Id: hal-05125278

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

Submitted on 23 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_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
2D Bijective Rigid Rotation: quantitative and qualitative study

Stéphane Breuils¹*, David Coeurjolly² and Jacques-Olivier Lachaud³

¹*Université Savoie Mont Blanc, CNRS, LAMA, Chambéry, F-73000, France.

ID 0000-0002-8636-4977.

²CNRS, INSA Lyon, Université Claude Bernard Lyon 1, LIRIS, UMR5205, Villeurbanne, F-69622, France. ID 0000-0003-3164-8697.

³Université Savoie Mont Blanc, CNRS, LAMA, Chambéry, F-73000, France.

ID 0000-0003-4236-2133.

*Corresponding author: stephane.breuils@univ-smb.fr;

Contributing authors: david.coeurjolly@cnrs.fr; jacques-olivier.lachaud@univ-smb.fr;

**Abstract**

Preserving surfaces or volumes is crucial when applying rigid transformations of 2D/3D digital objects in medical images and computer vision. To achieve this goal, the digital geometry community has focused on characterizing bijective digitized rotations and reflections. However, the angular distribution of these bijective rigid transformations is far from being dense. Other bijective approximations of rigid transformations have been proposed, but the state-of-the-art methods lack the experimental evaluations necessary to include them in real-life applications. This paper presents several new methods to approximate digitized rotations with bijective transformations, including the composition of bijective digitized reflections, bijective rotation by circles and bijective rotation through optimal transport. These new methods and several classical ones are compared in terms of accuracy with respect to Euclidean rotations, as well as computational complexity and practical speed in real-time applications and continuity. Finally, we determine some topological stability results of bijective rigid rotations.

**Keywords:** discretized rotations, bijective rotations

# 1 Introduction

While rotations and translations in $\mathbb{R}^d$ are trivial isometric and bijective transforms, their digitized counterparts in $\mathbb{Z}^d$ have attracted a lot more attention, as in general, they do not preserve distances and are not bijective. Of course, direct applications of such transformations in $\mathbb{Z}^d$ belong to image processing or computer vision fields (template matching, object tracking...). However, the study of digitization effects of such rigid motions in $\mathbb{Z}^d$ has led to interesting number theoretic and arithmetical results. For instance,

Nouvel and Rémila (2004) has characterized the set of angles for which the digitized rotation is bijective in $\mathbb{Z}^2$, while Breuils et al. (2022) has determined this set of bijective angles in $\mathbb{Z}^3$. Along the same lines, Pluta et al. (2018) exhibited the set of bijective angles on the hexagonal grid. We can also take an interest in bijective transformations that are close to rigid transformations: quasi-shear transforms (Andres (1996); Carstens et al. (1999); Toffoli and Quick (1997)), or reflections (Andres et al. (2019); Breuils et al. (2021)). For specific applications, Passat et al. (2022) have proposed
an approximation of rotations that preserves the
homotopy for subsets of $Z^2$.

In this article, we follow this line of previous
works focusing on a more practical question in $Z^2$:
for a given rotation angle, what is the best possible
discrete bijective transformation. More precisely,
we are looking for a bijective transformation from
$Z^2$ to $Z^2$ (or subsets of $Z^2$) that minimizes some
quality metrics: a Euclidean distance-based one,
a metric that quantifies some continuity preserva-
tion, or image partition preservation. In this con-
text, we review existing bijective rotation methods
and propose two new approaches: the first one
relies on the composition of discrete reflections fol-
lowing the work of Breuils et al. (2021), the second
one on bijective rotation using circular annulus
(Andres (1992)). We demonstrate that the com-
position of four discrete reflections leads to the
rotation with the lowest metric error. For this
last approach, we also provide a lookup table that
returns the best sequence of reflections (and their
parameters) for a large set of angles.

We are also interested in how bijective rigid
transformations can preserve other qualitative
properties within images. A classical tool for mea-
suring the stability of transformations of functions
is persistent homology (e.g. see Edelsbrunner et al.
(2008)). However it is yet unclear how to use it
in the context of bijective rigid transformations,
since the image function may vary considerably
around contours and the bijective transformation
can shuffle slightly the pixels around the trans-
formed contours. Ngo et al. (2013) have studied
under which sufficient conditions a digitized rota-
tion preserves the topology of a binary picture
or an image partition, and their result is remark-
ably simple and local: just a few configurations
must be avoided. They also proposed a “repairing
tool” to remove these configurations. The consid-
ered transformation is however not bijective (some
points may disappear while some others are dupli-
cated in the transformation). A few years later
Ngo et al. (2019) aimed at improving the geometry
of the rotated image and proposed to polygo-
nalize the input digital set, rotate the polygon
and rediscretize it to mimic a digitized rotation.
This process offers some topological and geomet-
ric guarantees (for a subclass of sets), but is more
a heuristic solution and not really a bijective rigid
transformation in the grid. Passat et al. (2022)
have proposed a bijective affine transformation

whose aim is to preserve the homotopy of digital
sets within images through a combinatorial opti-
mization scheme. Their method remains limited
to extremely small images ($\approx 30 \times 30$). We pro-
pose here to show how the worst-case error of any
bijective transformation induces stability results
of an image partition: the interiors of regions are
preserved, the region adjacency graph is preserved
under natural conditions.

## 2 Bijectivity of digitized rigid transformation

Let us consider rigid transformations that act on
the integer lattice $Z^d$. A digitized rigid transfor-
mation is the composition of a rigid transforma-
tion $T \in E(d)$ (element of the Euclidean group)
and a rounding to the nearest integer operator
$\mathcal{D} : \mathbb{R}^d \rightarrow Z^d$. The rigid transformation is bijec-
tive, whereas the rounding operator is not, see
Figure 1.

However, there are three possibilities to ensure
the bijectivity of digitized rigid transformations,
either

(a) define a digitized transformation that leaves invariant discrete lines (reflection) or discrete circles (rotation),

(b) characterize rigid transformations that are bijective after digitization. Once the characterization is known, it is not difficult to approximate any rigid transformation with the "nearest" bijective one.

(c) or by construction, like finding a bijective map that minimizes an error with respect to the real rigid transformation.

In the following, we only consider reflections and
rotations acting on the integer lattice $Z^2$. We start
by briefly recalling the state-of-the-art bijective
approximation of rigid transformations.

### 2.1 Quasi-shears

The quasi-shear approach by Andres (1996) consists of the discretization of the continuous horizontal and vertical shears that approximate rotation. This is a one-to-one point mapping thus bijective. Note that the shear method is not limited to 2D as shown by Toffoli and Quick (1997) and extends well to non-square lattices as shown by Carstens et al. (1999).
<figure><img src="image_2.png" /><figcaption>Fig. 1: 2D digitized rotations of points in blue. The digitized rotation of (a) is not bijective, since it yields holes and double points, whereas the rotation of (b) is bijective.</figcaption></figure>

## 2.2 Reflection with respect to discrete lines

This more recent method was presented by Andres et al. (2019) and was designed to leave invariant discrete lines after reflections. The reflection of a point is computed by simply identifying its position with respect to the point of intersection between the discrete line and its perpendicular discrete line. Again, this approach leads to a one-one point (bijective) map.

z

## 2.3 Bijective digitized reflections and rotations

We focus in this subsection on the approach that follows (b). First, let us recall the necessary and sufficient conditions for a digitized rotation and a digitized reflection to be bijective:

* for digitized rotations the subset $R$ of angles such that $\forall \alpha \in R$, $\mathcal{D} \circ \mathcal{R}_{\alpha}$ is bijective, where $\mathcal{R}_{\alpha}$ is the rotation of angle $\alpha$ centered at the origin,

* for digitized reflections, the subset $H$ of vectors such that $\forall \mathbf{m} \in H$, $\mathcal{D} \circ \mathcal{H}_{\mathbf{m}}$ is bijective, where $\mathcal{H}_{\mathbf{m}}$ is the reflection across the straight line with normal vector $\mathbf{m}$ and passing through the origin.

We start by recalling the characterization of 2D bijective digitized rotation with angle $\alpha \in [0, \frac{\pi}{2}]$ made by Nouvel and Rémila (2004). It consists of the following set of angles:

$$R := \{ \alpha \in [0, \frac{\pi}{2}] , \text{ such that} $$

$$ \begin{aligned} \cos(\alpha) &= \frac{2n + 1}{2n^2 + 2n + 1}, \\ \sin(\alpha) &= \frac{2n^2 + 2n}{2n^2 + 2n + 1}, n \in \mathbb{Z}^+ \end{aligned} \quad (1) $$

We denote by $R^k$ the subset of angles of $R$ limited to integers $0 \le n \le k$. More recently, Roussillon and Coeurjolly (2016) expressed the bijectivity condition in the complex plane by the Gaussian integers $\gamma \in \mathbb{Z}[i]$ (ring of Gaussian integers) with the equivalent formula:

$$R = \left\{ \frac{\gamma \cdot \gamma}{\sqrt{(\gamma \cdot \gamma^*)}} \mid \gamma = (n+1) + ni, n \in \mathbb{Z}^+ \right\}.$$

In order to express the bijectivity condition of digitized reflections, Breuils et al. (2021) used the Geometric Algebra $\mathbb{G}^2$ with basis vectors $\mathbf{e}_1, \mathbf{e}_2$. The resulting subset $H$ of bijective digitized reflections is

$$H = H_1 \cup H_2 \cup H_3 \cup H_4, \quad (2)$$

where

$$ \begin{aligned} H_1 &= \{ \mathbf{m} \in \mathbb{Z}^2, \mathbf{m} = -n\mathbf{e}_1 + (n+1)\mathbf{e}_2, n \in \mathbb{Z}^+ \}, \\ H_2 &= \{ \mathbf{m} \in \mathbb{Z}^2, \mathbf{m} = -(n+1)\mathbf{e}_1 + n\mathbf{e}_2, n \in \mathbb{Z}^+ \}, \\ H_3 &= \{ \mathbf{m} \in \mathbb{Z}^2, \mathbf{m} = -\mathbf{e}_1 + (2n+1)\mathbf{e}_2, n \in \mathbb{Z}^+ \}, \\ H_4 &= \{ \mathbf{m} \in \mathbb{Z}^2, \mathbf{m} = -(2n+1)\mathbf{e}_1 + \mathbf{e}_2, n \in \mathbb{Z}^+ \}. \end{aligned} \quad (3) $$

Again we denote by $H^k$ the subset of reflections of $H$ limited to integers $0 \le n \le k$.

In the following, we introduce some notions of geometric algebra that allow us to express the composition of reflections as either reflection or rotations.
## 2.4 Geometric Algebra

Geometric algebra was introduced through the works of W. K. Clifford, whose aim was to unify and to generalize both Grassmann algebra and W. R. Hamilton's quaternion. The product of the algebra is called the geometric product and is defined in any dimension. This product combines the outer and inner product as follows.

**Definition 1.** Geometric product, outer product and inner product (e.g., Dorst et al. (2007)). Let $(e_1, e_2)$, be an orthonormal basis of the inner product space $\mathbb{R}^2$. Given two vectors $\mathbf{m}, \mathbf{n} \in \mathbb{R}^2$ with $\mathbf{m} = m_x e_1 + m_y e_2$, $\mathbf{n} = n_x e_1 + n_y e_2$, the geometric product $\mathbf{mn}$ is defined as

$$ \mathbf{mn} = \mathbf{m} \wedge \mathbf{n} + \mathbf{m} \cdot \mathbf{n} \quad (4) $$

where

$$ \mathbf{m} \wedge \mathbf{n} = (m_x n_y - m_y n_x) \mathbf{e}_{12} \quad (5) $$

is the outer product between $\mathbf{m}$ and $\mathbf{n}$ and represents the oriented area spanned by $\mathbf{m}$ and $\mathbf{n}$. and

$$ \mathbf{m} \cdot \mathbf{n} = (m_x n_x + m_y n_y) \quad (6) $$

Note that the geometric product is invertible and for a vector $\mathbf{m} \in \mathbb{R}^2$,

$$ \mathbf{m}^{-1} = \frac{\mathbf{m}}{\mathbf{m} \cdot \mathbf{m}} = \frac{\mathbf{m}}{\|\mathbf{m}\|^2} $$

This geometric product generates the 4-dimensional ($2^d$ for a $d$ dimensional vector space) geometric algebra $\mathbb{G}^2$ over $\mathbb{R}$. The set $\{1, e_1, e_2, e_{12}\}$ forms a graded basis of $\mathbb{G}^2$. The grades range from 0 for scalars, 1 for vectors, 2 for bivectors. The geometric product acts on basis vectors and bivectors as follows

$$ e_1 e_2 = -e_2 e_1 $$

$$ e_1 e_1 = e_2 e_2 = 1 $$

$$ e_{12} e_1 = -e_2 = -e_1 e_{12} $$

$$ e_{12} e_2 = e_1 = -e_2 e_{12} $$

**Example:** Let $\mathbf{m} = m_x \mathbf{e}_1 + m_y \mathbf{e}_2$, and $\mathbf{n} = (m_x \cos \frac{\alpha}{2} - m_y \sin \frac{\alpha}{2}) \mathbf{e}_1 + (m_x \sin \frac{\alpha}{2} + m_y \cos \frac{\alpha}{2}) \mathbf{e}_2$ ($\frac{\alpha}{2}$ is the angle between $\mathbf{m}$ and $\mathbf{n}$), the result of $\mathbf{mn}$ is

$$ \begin{aligned} \mathbf{mn} &= (m_x \mathbf{e}_1 + m_y \mathbf{e}_2) \left( (m_x \cos \frac{\alpha}{2} - m_y \sin \frac{\alpha}{2}) \mathbf{e}_1 + (m_x \sin \frac{\alpha}{2} + m_y \cos \frac{\alpha}{2}) \mathbf{e}_2 \right) \\ &= \|\mathbf{m}\|^2 \left( \cos \frac{\alpha}{2} + \sin \frac{\alpha}{2} \mathbf{e}_{12} \right). \end{aligned} $$

**Definition 2.** Reflection. The reflection $\mathbf{x}'$ of a point $\mathbf{x} \in \mathbb{R}^2$ with respect to a hyperplane of normal vector $\mathbf{m} \in \mathbb{R}^2$ can be written as

$$ \mathbf{x}' = -\mathbf{m}\mathbf{x}^{-1} = \mathbf{x} - 2 \frac{\mathbf{m} \cdot \mathbf{x}}{\mathbf{m} \cdot \mathbf{m}} \mathbf{m}. \quad (7) $$

A rotation can be expressed as the composition of two reflections. In geometric algebra, it is conveniently expressed thanks to the geometric product as follows.

**Definition 3.** Rotation as the composition of two reflections. Assuming $\mathbf{m}, \mathbf{n}$ be the two unit normal vectors of the reflections with a relative of $\frac{\alpha}{2}$, the rotation of angle $\alpha$ of $\mathbf{x} = x\mathbf{e}_1 + y\mathbf{e}_2$ is expressed as

$$ \begin{aligned} \mathbf{x}' &= (\mathbf{nm})\mathbf{x}(\mathbf{nm})^{-1} \\ &= (\cos \frac{\alpha}{2} + \sin \frac{\alpha}{2} \mathbf{e}_{12})\mathbf{x}(\cos \frac{\alpha}{2} - \sin \frac{\alpha}{2} \mathbf{e}_{12}) \\ &= \left( (x \cos \frac{\alpha}{2} + y \sin \frac{\alpha}{2})\mathbf{e}_1 + (x \cos \frac{\alpha}{2} - y \sin \frac{\alpha}{2})\mathbf{e}_2 \right) \\ &= \left( (x \cos \alpha - y \sin \alpha)\mathbf{e}_1 + (x \sin \alpha + y \cos \alpha)\mathbf{e}_2 \right) \end{aligned} $$

**Definition 4.** Composition of $n$ reflections. The composition of reflections with normal vectors $\mathbf{m}_1, \mathbf{m}_2, \dots, \mathbf{m}_n$ is expressed as the reflection induced by the hyperplane defined by the geometric product of the normal vectors

$$ \mathbf{m}_1 \mathbf{m}_2 \cdots \mathbf{m}_n. \quad (8) $$

As a consequence, if $n$ is even and each normal vector is a unit vector, then the above geometric product acts as a rotation of a point $\mathbf{x}$.

## 2.5 Metrics for comparing bijective transformations

Let $\mathcal{T}$ be an arbitrary bijective transformation. We will use several metrics to evaluate its quality with respect to a given Euclidean rotation $\mathcal{R}_\alpha$. First of all, we will limit error computations to some domain $D$, generally $[-100, 100] \cap \mathbb{Z}^2$, which corresponds to an image resolution $201 \times 201$.

The cardinality of $D$ is denoted by $\#D$. The Euclidean distance between two points $p$ and $q$ is $d_2(p, q) = \|p - q\|$, with $\| \cdot \|$ the Euclidean norm,
<figure><img src="image_3.png" /><figcaption>Fig. 2: Angular density distributions of bijective digitized rotations colored in black (a), bijective digitized reflections colored in blue (b), the composition of 2 bijective digitized reflections colored in red (c) and the composition of 4 bijective digitized reflections colored in green (d).</figcaption></figure>

and for finite sets X and Y, we define:

$$d_2(p, Y) := \min_{q \in Y} d_2(p, q), \\ d_H(X, Y) := \max\{\max_{p \in X} d_2(p, Y), \max_{q \in Y} d_2(q, X)\},$$

the latter being the classical Hausdorff distance. The first metric is the standard root mean square error defined as:

$$L_2(\mathcal{T}, \alpha) := \sqrt{\frac{1}{\#D} \sum_{p \in D} \|\mathcal{T}(p) - \mathcal{R}_{\alpha}(p)\|^2}.$$

The second metric is the worst case error:

$$L_{\infty}(\mathcal{T}, \alpha) := \max_{p \in D} \|\mathcal{T}(p) - \mathcal{R}_{\alpha}(p)\|.$$

Denoting $N_8(p)$ the eight neighbours of a pixel $p$, the third metric, based on Saadetoğlu et al. (2024), is the continuity error, defined as:

$$L_c(\mathcal{T}) := \sqrt{\frac{1}{8\#D} \sum_{p \in D} \sum_{q \in N_8(p)} \|\mathcal{T}(p) - \mathcal{T}(q)\|^2}.$$

Finally, we combine the worst-case error and the continuity error balanced with some coefficient $\lambda \ge 0$ as:

$$L_{\infty+\lambda c}(\mathcal{T}, \alpha) := L_{\infty}(\mathcal{T}, \alpha) + \lambda L_c(\mathcal{T}).$$

In Section 8, we further extend these metrics with some quantification of the preservation of partitions during a rotation.

## 3 Composition of bijective digitized reflections

Transformations based on either Pythagorean triples or discrete reflections lead to bijective digitized rigid maps. However, the resulting angular distribution of both $R^k$ and $H^k$ is far from being dense, even for large $k$, see Figure ??a-c. When computing a rotation by an angle that is not in $R^k$ and $H^k$, one option would be to consider the nearest bijective rotation or reflection. However, this leads to low quality transformations (e.g. the mean squared distance error between rotated grid points and the original subset of the grid can be significant). Since the composition of an even number of reflections results in a rotation, an alternative is to compose bijective digitized reflections, for instance 4 of them, to approximate a given target rotation angle. More precisely, we aim at constructing a look-up table that associates, to some prescribed rotation angles, the sequence of reflections that minimizes some error metrics as described in section 2.5.

### 3.1 Candidate set construction and duplicates

First of all, let us fix $k = k_{max}$ and compute the composition of the elements of $H^{k_{max}}$. The set of the compositions of 4 bijective digitized reflections $C^{k_{max}}$ is expressed as

$$C^{k_{max}} := \{(\mathbf{m}_1, \mathbf{m}_2, \mathbf{m}_3, \mathbf{m}_4), \text{ such that } \\ \mathbf{m}_1, \mathbf{m}_2, \mathbf{m}_3, \mathbf{m}_4 \in H^{k_{max}}\}. \quad (9)$$
From our experiments, we do not compose more reflections than 4 since the maximum angular uncertainty is already lower than one degree (0.00015 rad) for $k_{max} = 15$. Figures 2c and 2d show the two normalized angular histograms of $C^{k_{max}}$ for 2 and 4 reflections.

**Remark 1.** $\#C^{k_{max}} = (4k_{max})^4$.

Furthermore, $C^{k_{max}}$ is a superset of the Pythagorean triple based angle set:

**Proposition 1.** $R^{k_{max}} \subset C^{k_{max}}$.

*Proof.* Let $\gamma = (k+1)+ki \in R^{k_{max}}$. Since the subalgebra composed of the scalar and bivector $\mathbb{R} \oplus \bigwedge^2 \mathbb{R}^2$ is isomorphic to the complex numbers $((e_{12})^2 = i^2 = -1)$, then $\exists \mathbf{m}_1, \mathbf{m}_2 \in H^{k_{max}}, \gamma = \mathbf{m}_1\mathbf{m}_2$. For instance, choose $\mathbf{m}_1 = \mathbf{e}_1, \mathbf{m}_2 = (k+1)\mathbf{e}_1 + k\mathbf{e}_2$. Their product is

$$ \mathbf{m}_1\mathbf{m}_2 = (\mathbf{e}_1)((k+1)\mathbf{e}_1 + k\mathbf{e}_2) = (k+1) + k\mathbf{e}_{12}, $$

which corresponds to the sought rotation. Now choosing for instance $\mathbf{m}_3 = \mathbf{m}_4 = \mathbf{e}_1$, we have defined $\mathbf{m} = \mathbf{m}_1\mathbf{m}_2\mathbf{m}_3\mathbf{m}_4$ that belongs to $C^{k_{max}}$ and corresponds to the rotation $\gamma$. $\square$

We also observe that several compositions of bijective digitized reflections result in the same rotation angle. This becomes critical if the value of $k_{max}$ increases (with $k_{max} = 15$, $\#C^{k_{max}} = 1.3 \times 10^7$). In order to reduce the overhead associated with the storage of this table, the duplicates must be removed. This involves sorting $C^{k_{max}}$ by increasing angle of the resulting rotation. Furthermore, it is important to note that two compositions resulting in the same angle might have different digitizations, see the example of Figure 3.

Therefore, letting $C_{\alpha}^{k_{max}}$ be the subset of $C^{k_{max}}$ restricted to the transformations resulting exactly in the angle $\alpha$, we choose a representative $\bar{C}_{\alpha}^{k_{max}}$ for each angle $\alpha$ as:

$$ \bar{C}_{\alpha}^{k_{max}} := \arg \min_{\mathbf{m} \in C_{\alpha}^{k_{max}}} L_{*}(\Pi_{i=1}^{4}(\mathcal{D} \circ -\mathbf{m}_{i}\mathbf{p}\mathbf{m}_{i}^{-1}), \alpha), $$

where $L_{*}$ is a user-chosen metric among $L_2, L_{\infty}, L_{\infty+\lambda c}$.

Note that, for all $\mathbf{m} \in C_{\alpha}^{k_{max}}$, we have $\Pi_{i=1}^{4}\mathbf{m}_i = \cos(\frac{\alpha}{2}) + \sin(\frac{\alpha}{2})\mathbf{e}_{12}$. Finally, with $k_{max} = 15$, we have reduced the number of transformations to $\#\bar{C}^{k_{max}} \approx 10^5$ instead of $1.3 \times 10^7$ before.

## 3.2 Rotation angle to the most accurate bijective composition

Given a target rotation angle $\alpha$ and $\bar{C}^{k_{max}}$ sorted and without duplicates, seek $\bar{C}_{\beta}^{k_{max}} \in \bar{C}^{k_{max}}$ that best approximates $R_{\alpha}$. Firstly, since $\bar{C}^{k_{max}}$ is sorted by ascending angle, finding $\bar{C}_{\beta}^{k_{max}}$ closest to the sought angle $\alpha$ is a binary search operation. However, this element is not necessarily the composition that is the most accurate: it may not minimize the distance to the Euclidean rotation $R_{\alpha}$. For instance, let us consider a target rotation angle $\epsilon$ near 0, there might be a composition of 4 bijective reflections resulting in $\epsilon$ whereas the most accurate one is simply the composition of the two trivial reflections with normal vectors $\mathbf{m}_1 = \mathbf{m}_2 = \mathbf{e}_1$.

To address this issue, we start by identifying the $K$ elements of $\bar{C}^{k_{max}}$ nearest to $\bar{C}_{\beta}^{k_{max}}$, where the latter is chosen such that $|\beta - \alpha|$ is minimal. We call this subset $NN(\bar{C}_{\beta}^{k_{max}}, \alpha)$.

Finally, the best composition of digitized reflections is determined within $NN(\bar{C}_{\beta}^{k_{max}}, \alpha)$ according to the user-chosen metric $L_{*}$ as:

$$ \dot{\mathbf{m}} := \arg \min_{\mathbf{m} \in NN(C_{\alpha}^{k_{max}}, \alpha)} L_{*}(\Pi_{i=1}^{4}(\mathcal{D} \circ -\mathbf{m}_{i}\mathbf{p}\mathbf{m}_{i}^{-1}), \alpha). \quad (10) $$

## 3.3 Computational complexity

The computational cost of sorting the $C^{k_{max}}$ and removing duplicates is

$$ O(\max(\#D, \#C^{k_{max}}) \log(\#C^{k_{max}})). \quad (11) $$

Note that $\#D = 201 \times 201$. Since this latter operation can be computationally expensive, we choose to precompute $\bar{C}^{k_{max}}$. In practical implementation, we go a step further by precomputing the table of the most accurate composition of bijective digitized reflections for each integer angle in degree. It is worth mentioning this table remains reusable, as the number of points increases. Therefore, if we consider an image of size $N \times N$, the complexity of the approach is the complexity of applying bijective digitized reflections to each point of the image. Thus, the overall complexity is $O(N^2)$. Table 2, page 14, shows two examples of the composition of digitized reflections applied to an image. The resulting implementation of this approach is available in DGtal.
<figure><img src="image_4.png" /><figcaption>Fig. 3: Composition of 2 bijective digitized reflections $\mathbf{m}_1, \mathbf{m}_2$. (a) $\mathbf{m}_1 = -2\mathbf{e}_1 + 3\mathbf{e}_2$, $\mathbf{m}_2 = -5\mathbf{e}_1 + 4\mathbf{e}_2$. (b) $\mathbf{m}_1 = 4\mathbf{e}_1 + 5\mathbf{e}_2$, $\mathbf{m}_2 = 3\mathbf{e}_1 + 2\mathbf{e}_2$. The angle between the normal vectors in (a) and (b) is the same whereas their digitizations (points in blue) are different, for example $4\mathbf{e}_1 + \mathbf{e}_2$ is in the lattice of (b) but not (a).</figcaption></figure>

## 4 Bijective rotation by circles

We build a bijective approximation of a rotation by decomposing the plane into concentric digital circles around the center of rotation. The points along each digital circle are sorted according to the angle they form with the center of rotation and the x-axis. Then the global transformation is constructed by mapping circles onto themselves, shifting the points according to the desired angle $\alpha$.

More precisely, assuming the origin of the frame lies at the center of rotation, let $C^r := \{p \in \mathbb{Z}^2, r \le \|p\|_2 < r + 1\}$. It is clear that $(C^r)_{r \in \mathbb{Z}, r \ge 0}$ forms a partition of $\mathbb{Z}^2$. We then sort the points of each circle $C^r$ according to their angle with the x-axis: let $(C_i^r)_{i=0,...,n^r-1}$ be the induced sequence of points, where $n^r$ is the cardinality of $C^r$. We have thus $\forall 0 \le i < j < n^r$, $\angle(C_i^r O_x) < \angle(C_j^r O_x)$. Denoting by $\lfloor \cdot \rfloor$ the nearest integer rounding operator, we define the rotation along circles $R_\alpha^C$ of angle $\alpha$ as:

$$ \forall p \in \mathbb{Z}^2, R_\alpha^C(p) = q, \text{ with } p = C_i^r, q = C_j^r, \\ \text{and } j = \left( i - \left\lfloor \frac{\alpha}{2\pi} n^r \right\rfloor \right) \mod n^r. $$

This transformation is clearly bijective: it maps the points of a circle onto the same circle, and the shift of indices is a one-to-one mapping. This transformation also preserves circles and minimizes the radial error in some sense.

From a computational point of view, rotating a whole image of size $N \times N$ takes a time $\Theta(N^2)$, see Table 1. It suffices to proceed circle by circle, each shift takes a time linear in the number of points of the circle. If one is interested in rotating just one point $p = C_i^r$, the complexity is then $O(\log N)$: it takes $O(1)$ to find the correct circle radius $r$, then $O(\log N)$ worst case to find the index $i$ of $p$ in the sequence, and finally $O(1)$ to get the shifted point.

## 5 Optimal Transport method

In recent years, Optimal Transport (OT for short) has become a key mathematical framework for manipulating generalized probability density functions (e.g. Villani (2009)). The most general way to describe the interest of OT is that it allows quantifying meaningfully how costly it is to move masses from a generalized probability density function to another one, so-called the Wasserstein distance. Depending on the nature of the measures, discrete-to-discrete, semi-discrete, or continuous-to-continuous, a huge literature exists on numerical methods to efficiently solve OT problems Peyré et al. (2019); Flamary et al. (2021). When dealing with discrete measures with unit masses, the OT problem boils down to an optimal assignment problem: given two sets of points $X = \{x_i\}_n$ and $Y = \{y_i\}_n$ in $\mathbb{R}^d$, and a cost function $c: \mathbb{R}^d \times \mathbb{R}^d \to \mathbb{R}^+$, we are looking for the
permutation $\sigma$ in $\{1..n\}$ such that

$$ \sum_{i=1}^{n} c(x_i, y_{\sigma(i)}) $$

is minimal. Back to our setting, if $X$ and $Y$ are two discrete sets and $c$ the squared Euclidean distance, the OT approach allows us to construct a bijective map $X \to Y$ that minimizes the mean squared $l_2$ error between $X$ and $Y$. If $X$ is a finite disk of $\mathbb{Z}^d$ and $T \in E(d)$ any continuous rotation, one can define the OT variant of $T$ (e.g., OT based rotations) as the optimal assignment between $X$ and $T(X)$ for the (squared) $l_2$ cost. On the computational side, the Hungarian method can be used to compute the optimal assignment (see, for example, Peyr\'e et al. (2019)) with an $O(n^4)$ computational cost, for $n$ the number of pixels. In this paper, we rely on a fast network simplex algorithm Bonneel (2018). The worst-case computational cost remains highly polynomial in $n$ (i.e., $O(N^8)$ for an image $N \times N$), but the upper bound is not reached in practice. To get an idea of computation times, rotating a $100 \times 100$ image takes several minutes on an Apple M2 processor.

# 6 Optimal Transport by circles

Since the OT of an image is very costly and impracticable for nowadays image resolutions, we construct a new bijective transformation by mixing rotation by circles and OT. More precisely, for a constant $k \ge 2$, we group concentric circles $C^r$ by $k$-tuples, leaving only $C^0$ alone. We thus build digital sets $D^i$ that are grouped into concentric circles:

$$ D^0 := C^0 \quad \forall i \ge 0, D^{i+1} := \bigcup_{j=1}^{k} C^{ki+j}. \quad (12) $$

Then, given a rotation $T_\alpha$ of angle $\alpha$, for each circular ring $D^i$, we perform the optimal transport between $T_\alpha(D^i)$ and $D^i$ to find the best (as of $L_2$) bijective rotation within each ring. Note that the computational cost is now $N \times O(k^4N^4)$, since the number of points within a ring is proportional to $kN$. Finally, we can build a lookup table for a fixed number of angles (like 360) that gives the assignment for each ring.

# 7 Experimental results and discussions

We consider the following bijective approximations approaches

* Quasi-shears (QSH)

* Rotation as the composition of discrete line reflections (CDLR)

* Bijective digitized rotations (BROT)

* Composition of bijective digitized reflections (CBDR)

* Bijective rotation by circles (RBC)

* Optimal transport (OT)

* Optimal transport by circles (OTC)

The next subsections present the respective performances of these approaches both in terms of computational complexity and accuracy.

## 7.1 Computational complexity

We evaluate the computational complexity of rotating a full image of size $N \times N$. As for the quasi-shear approach, we consider the Final_QSR algorithm of Andres (1996). Applying a shift to a point is a constant time algorithm, leading to an overall complexity in $O(N^2)$. Concerning the rotation as the composition of the discrete line reflection approach, we rely on Algorithm 1 of Andres et al. (2019). The function $X(y)$ defined in line 2 computes a rounding operation and this operation is a constant-time operation. The table 1 summarizes the complexity of both the image transformation and the table precomputation for the methods presented in this paper.

## 7.2 Accuracy for a fixed image size

The accuracy of each method is given in terms of Euclidean distance between the continuous rotation and its discrete approximation. More precisely, we compute both the $L_2$ and $L_\infty$ norms of the error between the Euclidean rotation and the approximation method. As for the CDLR method, we change it by modifying Algorithm 1 Andres et al. (2019), see Algorithm2, where we choose the first reflection such that one metric is minimized, please refer to Algorithm 2 in the appendix. By default, we choose the worst-case error $L_\infty$. Figures 4 and 5 display, respectively, the $L_2$-error
<table><caption>**Table 1:** For the main approaches, the first two lines describe the time complexity and the precomputation time complexity to apply each bijective transformation method to a $N \times N$ image. The remaining lines present both the time (ms) to transform a 201 × 201 image (Image transf.) as well as the precomputation time required for the same image (Precomp.). For CBDR, we choose $k_{max} = 15$. Methods proposed in this paper are emphasized in bold font. For OTC-k, k stands for the width of each ring (see Eq. (12)).</caption><thead><tr><th></th><th>QSH</th><th>CDLR</th><th>BROT</th><th>CBDR</th><th>RBC</th><th>OT</th><th>OTC-k</th></tr></thead><tbody><tr><th>Complexity</th><td>Θ(N<sup>2</sup>)</td><td>Θ(N<sup>2</sup>)</td><td>Θ(N<sup>2</sup>)</td><td>Θ(N<sup>2</sup>)</td><td>Θ(N<sup>2</sup>)</td><td>O(N<sup>8</sup>)</td><td>O(N<sup>2</sup> log(N))</td></tr><tr><th>Image transf.</th><td>n.a.</td><td>n.a.</td><td>n.a.</td><td>Eq.(11)</td><td>O(N<sup>2</sup>)</td><td>n.a.</td><td>O(k<sup>3</sup>N<sup>5</sup>)</td></tr><tr><th>Precomp.</th><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>Timings (ms)</th><td>QSH</td><td>CDLR</td><td>BROT</td><td>CBDR</td><td>RBC</td><td>OT</td><td>OTC-2</td><td>OTC-3</td><td>OTC-4</td></tr><tr><th>Image transf.</th><td>2.7</td><td>43.5</td><td>3.8</td><td>3.8</td><td>3.5</td><td>&gt; 10<sup>5</sup></td><td>15.9</td><td>16</td><td>16</td></tr><tr><th>Precomp.</th><td>0</td><td>0</td><td>0</td><td>5300</td><td>13</td><td>0</td><td>4 &middot; 10<sup>5</sup></td><td>7 &middot; 10<sup>5</sup></td><td>13 &middot; 10<sup>5</sup></td></tr></tbody></table>

and $L_{\infty}$-error for each method as a function of the angle of rotation for a 200 × 200 image.

We also evaluate the continuity of each method in Figure 6. For both methods CBDR and CDLR, we combine both $L_{\infty}$ and $L_c$ using the last formula of Section 2.5. The results are shown for $\lambda \in [0, 100]$ and for angles in [0, 90] in Figure 11. Some visual results are shown in Figure 12 for the same target angle but with different $\lambda$.

Overall, bijective rotations (BROT) constitute the worst trade-off because their angle density is too scarce, however, it preserves the continuity the most. Quasi-shears (QSH) is among the best methods, since it has quite regular errors and preserves the continuity well. Composition of discrete line reflections (CDLR) induces low errors. However, for angles far from multiples of $\pi/2$, it does not preserve the continuity even after penalizing the $L_{\infty}$-errors by the $L_c$ term. Rotations by circles (RBC) induce quite large errors (especially in the worst-case). However the errors of their optimal transport extensions (OTC-k) decrease as the width k of each ring is increased. Indeed method OTC with rings of width 4 is only outperformed by CBDR, and not for all angles. Increasing the ring width would probably induce the method with the lowest average error, but its precomputation is very costly (several days). Compositions of Bijective Digitized Reflections (CBDR) provide generally the best results on average and is competitive with respect to QSH in the worst-case, while staying fast to compute.

## 7.3 Evaluation of CBDR: Impact of image Size, K and $k_{max}$

In this subsection, we study the impact of changing the CBDR parameters:

* the size of the image,

* $k_{max}$ the cardinality of the subset of bijective reflections,

* K the number of composition of bijective reflections closest to the target angle.

For the sake of clarity, we compute the average, minimum and maximum values of both the $L_{\infty}$ and $L_2$ norms of the errors. Figure 14 shows the evolution of the errors when we increase K for an image of size 201 × 201 and for an image of size 1001 × 1001. Increasing $k_{max}$ from 30 to 50 does not have any noticeable effect on the resulting curves. A low $k_{max} = 8$ however has a large effect on the errors, an explanation of these large errors is the fact that for $k_{max}=8$, the angular density distribution is sparser than for $k_{max} = 30$ as shown in Figure 13.

Finally, these results show that both $k_{max} = 30$ and $K = 1000$ are good candidates for CBDR. Increasing more $k_{max}$ is interesting for larger images but then the precomputation time is a problem. For $k_{max} = 50$, the precomputation time is approximately 7 hours.

## 7.4 Impact of the image size for each approach

To further support the previous section, Figures 9 and 10 show some statistics about both $L_{\infty}$ and $L_2$ for each method with image sizes ranging from 200 × 200 to 1000 × 1000. First, the impact of increasing the image size is the most noticeable for RBC while it has almost no impact on QSH. Increasing image size has also a limited impact on CBDR. This effect is reduced by increasing further $k_{max}$ at the price of a larger precomputation time.
<figure><img src="image_5.png" /><figcaption>**Fig. 4:** Plots of $L_2$-errors for the different bijective transformations as a function of the angle (91 angles between $[0, \frac{\pi}{2}]$), y-range is between 0 and 2 pixels.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>**Fig. 5:** Plots of $L_\infty$-errors for the different bijective transformations as a function of the angle (91 angles between $[0, \frac{\pi}{2}]$), y-range is between 0 and 8 pixels.</figcaption></figure>
<figure><img src="image_7.png" /><figcaption>**Fig. 6:** Plots of $L_c$-errors for the different bijective transformations as a function of the angle (91 angles between $[0, \frac{\pi}{2}]$), y-range is between 0 and 3 pixels.</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>**Fig. 7:** Plots of $L_2$-errors for the different bijective transformations as a function of the angle (91 angles between $[0, \frac{\pi}{2}]$) for an image of size 1000 x 1000, y-range is between 0 and 6 pixels.</figcaption></figure>
<figure><img src="image_9.png" /><figcaption>**Fig. 8:** Plots of $L_{\infty}$-errors for the different bijective transformations as a function of the angle (91 angles between $[0, \frac{\pi}{2}]$) for an image of size 1000 × 1000, y-range is between 0 and 6 pixels.</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>**Fig. 9:** Plots of average, minimum and maximum of $L_2$-errors for the different bijective transformations (91 angles between $[0, \frac{\pi}{2}]$) for images of sizes between 300 × 300 to 1000 × 1000.</figcaption></figure>
<figure><img src="image_11.png" /><figcaption>Fig. 10: Plots of average, minimum and maximum of $L_\infty$-errors for the different bijective transformations (91 angles between $[0, \pi/2]$) for images of sizes between 300 × 300 to 1000 × 1000.</figcaption></figure>

## 7.5 Enforce continuity for CBDR and CDLR

Furthermore, it is possible to enforce the continuity of the bijective transformation for several angles by choosing a $\lambda$ that minimizes $L_\infty$ while ensuring a low $L_c$. Table 2 gives a visual comparison of each approximation method for both the worst case and a fixed angle (61°). For both the worst case and the fixed angle, we also show the $L_2$-error field with respect to the Euclidean rotation.

Note that all implementations are available in DGtal<fnref n="1" />. The next subsection gives a brief overview of these resulting implementations.

## 7.6 Implementation details

We slightly changed the algorithm of Andres et al. (2019) by adding a solver that looks for the two Discrete Line Reflections that minimize a distortion metric as defined in Section 2.5. Note that the user can add his/her own metric distortion

by inheriting from the Policy class. The user can rotate any image or a $\mathbb{Z}^2$ point by creating a CDLR object. The framework of CBDR is based on digitized reflections, implemented in the DigitizedReflection class. Thanks to the digitized reflections, the class CBDR_naiverotation composes an even number of digitized reflections. The class CBDRSolver allows finding the CBDR_naiverotation that minimizes a metric distortion implemented in the Policy class (the same as CDLR). In order to avoid the tedious computation of each optimal composition of bijective rotation, we invite the user to download the pre-computed table. The OTC method uses a table that gives the assignment that minimizes the $L_2$ average error for each RBC ring. Note that the OTC precomputed table is also available online.

## 8 Rotations of regions and partitions

Up to now we have looked at how pixels are rotated through different bijective transformations and we have measured the errors in distance

<footnote n="1">¹Pull request #1741 retrieved from https://github.com/DGtal-team/DGtal/pull/1741</footnote>
<figure><img src="image_12.png" /><figcaption>**Table 2:** For each method, from left to right: the image rotation inducing its worst-case $L_2$ result, pointwise error with respect to the Euclidean rotation (the redder the higher), and the image rotated by 61-degree and its corresponding error. The expected rotated image bounding box is in blue and each circular inset is a zoom on the central part (delineated in green).</figcaption></figure>
<figure><img src="image_13.png" /><figcaption>Fig. 11: Plots of $L_\infty$, $L_2$, $L_c$ by optimizing $L_{\infty+\lambda c}$ with $\lambda \in [0, 100]$ for both CDLR and CBDR methods for angles $\in [0, \pi/2]$.</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>Fig. 12: Bijective rotation of the same image and the same target angle (10°) with CDLR but we choose to minimize with respect to $L_{\infty+\lambda c}$ (a) with $\lambda = 0$, (b) with $\lambda = 70$.</figcaption></figure>

induced by these transformations. As stated in the introduction, other properties could be interesting to preserve through bijective transformations, like the persistent homology of the image function or the homotopy of image regions. Since this objective is out of reach at the moment; we take an interest here in how regions are transformed. For instance, when trying to register a segmented image to another segmented image, we wish to see how regions are mapped to one another. We then wish to keep transformed regions as connected as possible, to keep regions adjacent, and also to guarantee that transformed regions do not become too intertwined.

We use the fact that, for each bijective transformation $T_\alpha$ associated with a rotation of angle $\alpha$, there is a strict upper-bound $\mu$ on the distortion with respect to the Euclidean rotation. Indeed, $L_\infty(T_\alpha, \alpha) < \mu$ implies:

$$ \forall \mathbf{p} \in D, d_2(T_\alpha(\mathbf{p}), \mathcal{R}_\alpha(\mathbf{p})) < \mu. \quad (13) $$

For instance, for images of size $D = 201 \times 201$ with $k_{\max} = 15$, CBDR presents an upper bound $\mu \approx 1.5$ (see Figure 5). This bound implies that

$$ d_H(T_\alpha(D), \mathcal{R}_\alpha(D)) < \mu. \quad (14) $$

Indeed, Let $\delta := \max_{\mathbf{z} \in T_\alpha(D)} d_2(\mathbf{z}, \mathcal{R}_\alpha(D))$. So

$$ \begin{aligned} \delta &= \max_{\mathbf{p} \in D} d_2(T_\alpha(\mathbf{p}), \mathcal{R}_\alpha(D)) \\ &\le \max_{\mathbf{p} \in D} d_2(T_\alpha(\mathbf{p}), \mathcal{R}_\alpha(\mathbf{p})) < \mu. \end{aligned} $$

The same reasoning applies to $\delta' := \max_{\mathbf{x} \in \mathcal{R}_\alpha(D)} d_2(\mathbf{x}, T_\alpha(D))$, leading to $\delta' < \mu$. We have proven (14) since $d_H(T_\alpha(D), \mathcal{R}_\alpha(D)) = \max\{\delta, \delta'\}$.

Before stating some properties, we need a few definitions to characterize interior points within a region. For some digital set $X \subset \mathbb{Z}^2$, we denote by $\partial X$ its interpixel boundary (i.e. the topological boundary of the union of pixels of $X$, seen as squares). If $I$ is an interval of $\mathbb{R}^+$, then the $I$-subset
<figure><img src="image_15.png" /><figcaption>Fig. 13: Angular density distributions of the composition of bijective reflections for $k_{max} = 8$ in the first row and $k_{max} = 15$ in the second row. The composition of 2 bijective digitized reflections is colored in red in the left column and the composition of 4 bijective digitized reflections is colored in green in the right column.</figcaption></figure>

$X_I$ of X is defined as:

$$X_I := \{\mathbf{x} \in X \mid \mathrm{d}_2(\mathbf{x}, \partial X) \in I\}. \quad (15)$$

Obviously, $X_{[0, \frac{1}{2}]} = \emptyset$ and $X = X_{[\frac{1}{2}, +\infty[}$ and all $X_{\{a\}}$ are mutually disjoint sets. The set $X_{\frac{1}{2}}$ corresponds to the border of X (i.e. pixels of $\tilde{X}$ directly adjacent to pixels not in X). For some non-negative real number $\epsilon$, we call $\epsilon$-core of X

the $[\epsilon, +\infty[$-subset of X, which we denote $X_{\ge \epsilon}$ as a shorthand (see Figure 15 for an illustration).

We show first how interiors of regions may not interlace when transformed.

**Proposition 2.** Let X and Y be two mutually disjoint subsets of the domain $D \subset \mathbb{Z}^2$, then $T_\alpha(X_{\ge \epsilon})$ and $T_\alpha(Y_{\ge \nu})$ are nowhere adjacent whenever $\epsilon + \nu \ge 2\mu + 1$.
<figure><img src="image_16.png" /><figcaption>Fig. 14: Plots of the average,min and max of L∞-errors (left) and L₂ errors (right) for K ∈ [30, 2000] and for kmax = {8, 30, 50} are shown. The image size is 201 × 201 in the first row and 1001 × 1001 in the second row.</figcaption></figure>

Proof. We assume that the cores are not empty, otherwise the result is obvious. Let x be in the ϵ-core of X and y in the ν-core of Y. For any x' ∈ ∂X and y' ∈ ∂Y, we have d₂(x, x') ≥ ϵ and d₂(y, y') ≥ ν. Since X and Y are mutually disjoint sets, we have immediately d₂(x, y) ≥ ϵ + ν.

Now, by triangular inequality, we have:

$$d_2(\mathcal{R}_\alpha(\mathbf{x}), \mathcal{R}_\alpha(\mathbf{y})) \le d_2(\mathcal{R}_\alpha(\mathbf{x}), \mathcal{T}_\alpha(\mathbf{x})) \\ + d_2(\mathcal{T}_\alpha(\mathbf{x}), \mathcal{T}_\alpha(\mathbf{y})) \\ + d_2(\mathcal{T}_\alpha(\mathbf{y}), \mathcal{R}_\alpha(\mathbf{y})).$$

Since $\mathcal{R}_\alpha$ is an isometry, it preserves distances so $d_2(\mathcal{R}_\alpha(\mathbf{x}), \mathcal{R}_\alpha(\mathbf{y})) = d_2(\mathbf{x}, \mathbf{y})$. Furthermore, from (13), we know that $d_2(\mathcal{R}_\alpha(\mathbf{x}), \mathcal{T}_\alpha(\mathbf{x})) < \mu$ and $d_2(\mathcal{R}_\alpha(\mathbf{y}), \mathcal{T}_\alpha(\mathbf{y})) < \mu$. Reordering terms above, it yields

$$d_2(\mathcal{T}_\alpha(\mathbf{x}), \mathcal{T}_\alpha(\mathbf{y})) > d_2(\mathbf{x}, \mathbf{y}) - 2\mu \\ > \epsilon + \nu - 2\mu.$$

The conclusion follows if $\epsilon + \nu - 2\mu \ge 1$, since then the transformed x and y cannot be adjacent

(a necessary condition to be adjacent is that the distance is less or equal to 1). □

We illustrate Proposition 2 in Figures 16 and 17. As input, we use the regions of Figure 15 and we check the potential adjacencies of their ϵ-cores after bijective rotations, for two values of ϵ ($\sqrt{2}/2$ and $3/2$). We compare five bijective rotations (CBDR, OTC2, QSH, RBC, CDLR) and we test every integer degree rotation angle from 0 to 90°. We display for each rotation which angle gives the greatest number of bad adjacencies between ϵ-cores.

As expected by the above proposition, the bijective rotations having the lowest L∞-error show the smallest number of bad adjacencies. Experiments show that CBDR, QSH and OTC2 present much fewer bad adjacencies than RBC and, more surprisingly, CDLR. For higher values of ϵ, the number of bad adjacencies decreases quickly (and is guaranteed to be zero if $2\epsilon > 2\mu+1$ with $\mu$ the L∞-error of this rotation for this angle).

Experiments also show that the proposition is a bit conservative. For instance QSH rotation
<figure><img src="image_17.png" /><figcaption>Fig. 15: Illustration of some $\epsilon$-cores of several regions within a domain. From left to right: input regions, distance function to the interpixel region boundaries, $\frac{\sqrt{2}}{2}$-cores, $\frac{3}{2}$-cores and 2-cores of input regions (pixels outside cores are in white).</figcaption></figure>

presents no bad adjacencies for $\frac{3}{2}$-cores of a 65 × 65 image. We also notice that CDLR presents only one bad adjacency for angle 54°, which is indeed its worst-case $L_\infty$-error. We did not display the results for 2-cores, since every bijective rotation presents no bad adjacency, regardless of the angle. This was expected for CBDR and CDLR (since it is guaranteed for $\mu < 3/2$ according to above), but not for the other rotations. However, keep in mind that the input image is quite small, while $L_\infty$-errors of Figure 5 are computed for images of size 201 × 201.

Finally, the shape of rotated regions varies considerably between the different bijective rotation methods. Visually, CBDR, OTC and QSH are the most pleasant to the eye, while RBC and CDLR present unusual deformations (even if the latter has quite a low $L_\infty$-error). Figure 18 confirms that CBDR, OTC and QSH are indeed much better for preserving the connectivity of regions in images, regardless of the rotation angle.

We now evaluate how the adjacency graph of regions is preserved through bijective rotations. Let {$X^1, \dots, X^n$} be a family of disjoint subsets of the domain $D \subset \mathbb{Z}^2$ (generally called regions). Two different regions $X^i$ and $X^j$ are said adjacent if and only if $d_H(X^i, X^j) = 1$, and we denote the non-reflexive symmetric relation as $X^i \sim X^j$. Adjacency relations are preserved through bijective transformation $T_\alpha$ in the following sense: **Proposition 3.** Assume the $\epsilon$-core of $X^i$ and the $\nu$-core of $X^j$ are not empty. If $X^i \sim X^j$, then

$$d_H(T_\alpha(X^i \ge \epsilon), T_\alpha(X^j \ge \nu)) < \nu + \epsilon + 2\mu + 1. \quad (16)$$

Otherwise if $X^i \not\sim X^j$ and $d_H(X^i, X^j) \ge \rho \ge \sqrt{2}$, then

$$d_H(T_\alpha(X^i \ge \epsilon), T_\alpha(X^j \ge \nu)) > \rho + \nu + \epsilon - 2\mu - 1. \quad (17)$$

*Proof.* For the sake of clarity, we omit the parameter $\alpha$ in $T_\alpha$ and $\mathcal{R}_\alpha$. If $X^i \sim X^j$, then $d_H(X^i \ge \epsilon, X^j \ge \nu) \le \epsilon + \nu + 1$ (even if the boundaries of the two regions intersect, the centers of pixels are at a distance of at least 1). Using triangular inequality, we get:

$$\begin{aligned} d_H(T(X^i \ge \epsilon), T(X^j \ge \nu)) &\le d_H(T(X^i \ge \epsilon), \mathcal{R}(X^i \ge \epsilon)) \\ &\quad + d_H(\mathcal{R}(X^i \ge \epsilon), \mathcal{R}(X^j \ge \nu)) \\ &\quad + d_H(\mathcal{R}(X^j \ge \nu), T(X^j \ge \nu)) \\ &< 2\mu + \epsilon + \nu + 1, \end{aligned}$$

using two times (14) and the equality $d_H(\mathcal{R}(X^i \ge \epsilon), \mathcal{R}(X^j \ge \nu)) = d_H(X^i \ge \epsilon, X^j \ge \nu)$ (the rotation $\mathcal{R}$ preserves Euclidean distances).

If $X^i \not\sim X^j$ and $d_H(X^i, X^j) \ge \rho \ge \sqrt{2}$, then $d_H(X^i \ge \epsilon, X^j \ge \nu) \ge \epsilon + \nu + \rho - 1$. So, again by triangular inequality we have:

$$\begin{aligned} d_H(\mathcal{R}(X^i \ge \epsilon), \mathcal{R}(X^j \ge \nu)) &\le d_H(\mathcal{R}(X^i \ge \epsilon), T(X^i \ge \epsilon)) \\ &\quad + d_H(T(X^i \ge \epsilon), T(X^j \ge \nu)) \\ &\quad + d_H(T(X^j \ge \nu), \mathcal{R}(X^j \ge \nu)), \end{aligned}$$

which entails (using the same arguments):

$$\begin{aligned} d_H(X^i \ge \epsilon, X^j \ge \nu) &< 2\mu + d_H(T(X^i \ge \epsilon), T(X^j \ge \nu)) \\ &\Leftrightarrow \epsilon + \nu + \rho - 2\mu - 1 < d_H(T(X^i \ge \epsilon), T(X^j \ge \nu)), \end{aligned}$$
<figure><img src="image_18.png" /><figcaption>**Fig. 16:** Bijective rotations of $\sqrt{2}/2$-cores of image regions. Each column displays the result of a different bijective rotation method. Each row displays the worst case of each bijective rotation, and displays the result of every rotation for this angle. The number of incorrect adjacencies (two pixels belonging to different $\epsilon$-cores that are adjacent) is written in the lower right part of each image.</figcaption></figure>

thus concluding the proof. □

These properties can be used to show a kind of robustness result for the region adjacency graph of an image partition through a bijective rigid transformation. For some positive $\mu$, let $\tilde{\mu}$ be the adjacency relation between subsets $X, Y$ of $\mathbb{Z}^2$ defined as $X \tilde{\mu} Y$ whenever $d_H(X, Y) < 4\mu + 2$.

**Proposition 4.** Assume $\mu$ is the upper-bound error the bijective transformation $\mathcal{T}$ for a given angle $\alpha$. Let us choose $\epsilon = \mu + \frac{1}{2}$. Let $\{X^1, \dots, X^n\}$ be a family of disjoint subsets of $\mathbb{Z}^2$, such that $\forall i \in \{1, \dots, n\}, X_{\ge \epsilon}^i \neq \emptyset$. Then, $\forall i, j \in \{1, \dots, n\}, i \neq j$, we have

non-interlacing: $\mathcal{T}(X_{\ge \epsilon}^i) \not\asymp \mathcal{T}(X_{\ge \epsilon}^j)$,
<figure><img src="image_19.png" /><figcaption>**Fig. 17:** Bijective rotations of $\frac{3}{2}$-cores of image regions. Each column displays the result of a different bijective rotation method. Each row displays the worst case of each bijective rotation, and displays the result of every rotation for this angle. The number of incorrect adjacencies (two pixels belonging to different $\epsilon$-cores that are adjacent) is written in the lower right part of each image.</figcaption></figure>

**adjacency:** $X^i \sim X^j$ implies $\mathcal{T}(X_{\ge \epsilon}^i) \stackrel{\mu}{\sim} \mathcal{T}(X_{\ge \epsilon}^j)$,

**separation:** $X^i \not\sim X^j$ and $d_H(X^i, X^j) \ge 4\mu + 2$ implies $\mathcal{T}(X_{\ge \epsilon}^i) \stackrel{\mu}{\not\sim} \mathcal{T}(X_{\ge \epsilon}^j)$.

For the second point, Proposition 3, Equation (16) implies that ($\alpha$ is omitted for conciseness):

$$d_H(\mathcal{T}(X_{\ge \epsilon}^i), \mathcal{T}(X_{\ge \epsilon}^j)) < 2\epsilon + 2\mu + 1 = 4\mu + 2,$$

*Proof.* For the first point, Proposition 2 concludes immediately with $\epsilon = \nu = \mu + \frac{1}{2}$.

which means $\mathcal{T}(X_{\ge \epsilon}^i) \stackrel{\mu}{\sim} \mathcal{T}(X_{\ge \epsilon}^j)$.
<figure><img src="image_20.png" /><figcaption>**Fig. 18:** Number of bad adjacencies for each type of bijective rotation as a function of the angle (in degrees). Increasing the parameter of the cores decreases this number. QSH, CBDR and OTC2 present the smallest numbers of bad adjacencies, while RBC and CDLR are very unstable and may induce a lot of bad adjacencies. Results for 2-cores are not displayed since every type of bijective rotation presents no bad adjacencies regardless of the angle (note, however, that the size of the image is 65 × 65, hence quite small).</figcaption></figure>
For the third point Equation (17) tells that:

$$d_H(\mathcal{T}(X_{\ge \epsilon}^i), \mathcal{T}(X_{\ge \epsilon}^j)) > \rho + 2\epsilon - 2\mu - 1 = 4\mu + 2,$$

by substituting $\rho = 4\mu + 2$ and again $\epsilon$. This shows $\mathcal{T}(X_{\ge \epsilon}^i) \not\sim \mathcal{T}(X_{\ge \epsilon}^j)$. □

In other words, the adjacencies of regions are stable in some sense through bijective rotations, provided that regions have a non-empty core and non-adjacent regions are not too close to each other.

Overall, CBDR, OTC and QSH seem more adapted to rotate partitions and to compute the rigid registration of partitions. Furthermore, using the $\epsilon$-cores to make the registration seems a much more pertinent approach than using the regions themselves.

## 9 Conclusion

In this paper, we presented multiple approaches and conducted a quantitative and qualitative study of the main 2D bijective rigid rotations. Our experimental results highlight the performances of optimal transport with circles, quasi-shears rotation and the composition of bijective digitized reflections both in terms of accuracy and preservation of continuity. The symmetrized version of QSH offers a compelling balance of low precomputation, low $L_\infty$ error and strong robustness to variations in image size. CBDR could be preferred for its low $L_2$ error and its continuity qualities, but it requires quite large precomputation time. OTC presents also low errors but requires high precomputation time and is only usable for medium size images. The other tested methods are outmatched by the previous ones: OT gives the lowest error but it is limited to mini-images with current algorithms, RBC presents high $L_\infty$ error, CDLR is outperformed by QSH and CBDR in all categories.

We also considered the problem of rotating a partition in a bijective way and how the worst-case error of any bijective transformation induces stability results of an image partition. Tackling the problem of registration with bijective and as continuous as possible rigid transformation is among our perspectives as well as extending to 3D the proposed approximation methods. Overall QSH seems the most promising method for image

registration, while both CBDR and QSH are competitive candidates for 3D bijective rotations.

## Acknowledgments

This work is supported by both the Savoie Mont-Blanc University (TRDRECAL project) and the French National Research Agency (StableProxies project, ANR-22-CE46-0006).

## References

* Andres, E., Dutt, M., Biswas, A., Largeteau-Skapin, G., Zrour, R.: Digital two-dimensional bijective reflection and associated rotation. In: Discrete Geometry for Computer Imagery, pp. 3–14. Springer, Berlin, Heidelberg (2019)

* Andres, E.: Cercles discrets et rotations discrétes. PhD thesis, Université Louis Pasteur, Strasbourg, France (1992)

* Andres, E.: The quasi-shear rotation. In: Miguet, S., Montanvert, A., Ubéda, S. (eds.) Discrete Geometry for Computer Imagery, pp. 307–314. Springer, Berlin, Heidelberg (1996)

* Breuils, S., Kenmochi, Y., Andres, E., Sugimoto, A.: Conjecture on characterisation of bijective 3D digitized reflections and rotations. In: International Workshop on Empowering Novel Geometric Algebra for Graphics and Engineering, pp. 41–53 (2022). Springer

* Breuils, S., Kenmochi, Y., Sugimoto, A.: Visiting bijective digitized reflections and rotations using geometric algebra. In: International Conference on Discrete Geometry and Mathematical Morphology, pp. 242–254 (2021). Springer

* Bonneel, N.: Fast Network Simplex for Optimal Transport (2018). https://github.com/nbonneel/network_simplex

* Carstens, H.-G., Deuber, W.A., Thumser, W., Koppenrade, E.: Geometrical bijections in discrete lattices. Combinatorics, Probability and Computing 8(1-2), 109–129 (1999)

* Dorst, L., Fontijne, D., Mann, S.: Geometric Algebra for Computer Science, An Object-Oriented
Approach to Geometry. Morgan Kaufmann, ??? (2007)

DGtal: Digital geometry tools and algorithms library. https://dgtal.org/

Edelsbrunner, H., Harer, J., et al.: Persistent homology - a survey. Contemporary mathematics 453(26), 257–282 (2008)

Flamary, R., Courty, N., Gramfort, A., Alaya, M.Z., Boisbunon, A., Chambon, S., Chapel, L., Corenflos, A., Fatras, K., Fournier, N., Gautheron, L., Gayraud, N.T.H., Janati, H., Rakotomamonjy, A., Redko, I., Rolet, A., Schutz, A., Seguy, V., Sutherland, D.J., Tavenard, R., Tong, A., Vayer, T.: Pot: Python optimal transport. Journal of Machine Learning Research 22(78), 1–8 (2021)

Ngo, P., Passat, N., Kenmochi, Y., Debled-Rennesson, I.: Geometric preservation of 2d digital objects under rigid motions. Journal of Mathematical Imaging and Vision 61(2), 204–223 (2019)

Ngo, P., Passat, N., Kenmochi, Y., Talbot, H.: Topology-preserving rigid transformation of 2d digital images. IEEE Transactions on Image Processing 23(2), 885–897 (2013)

Nouvel, B., Rémila, E.: Characterization of Bivariate Discretized Rotations. In: International Workshop on Combinatorial Image Analysis, pp. 248–259 (2004). Springer

Peyré, G., Cuturi, M., et al.: Computational optimal transport: With applications to data science. Foundations and Trends in Machine Learning 11(5-6), 355–607 (2019)

Passat, N., Ngo, P., Kenmochi, Y., Talbot, H.: Homotopic affine transformations in the 2D cartesian grid. Journal of Mathematical Imaging and Vision 64(7), 786–806 (2022)

Pluta, K., Roussillon, T., Cœurjolly, D., Romon, P., Kenmochi, Y., Ostromoukhov, V.: Characterization of bijective digitized rotations on the hexagonal grid. Journal of Mathematical Imaging and Vision 60(5), 707–716 (2018)

Roussillon, T., Coeurjolly, D.: Characterization of bijective discretized rotations by Gaussian integers. Research report, LIRIS UMR CNRS 5205 (2016)

Saadetoğlu, M., Nagy, B., Avkan, A.: Digital continuity of rotations in the 2d regular grids. Annals of Mathematics and Artificial Intelligence 92(1), 115–137 (2024)

Toffoli, T., Quick, J.: Three-dimensional rotations by three shears. Graphical Models and Image Processing 59(2), 89–95 (1997)

Villani, C.: Optimal Transport: Old and New vol. 338. Springer, Berlin (2009)

# A Appendix

## A.1 QSH algorithm

Starting from the QSH algorithm presented in Andres (1996), we recall the definition of horizontal and vertical quasi shears VQS, HQS as follows

$$ \left| \begin{array}{l} \text{HQS}(a, b, c): \quad \mathbb{Z}^2 \rightarrow \mathbb{Z}^2 \\ \mathbf{x} = x\mathbf{e}_1 + y\mathbf{e}_2 \mapsto \mathbf{x} + \lfloor \frac{ay+c}{b} \rfloor \mathbf{e}_1. \end{array} \right. $$

$$ \left| \begin{array}{l} \text{VQS}(a, b, c): \quad \mathbb{Z}^2 \rightarrow \mathbb{Z}^2 \\ \mathbf{x} = x\mathbf{e}_1 + y\mathbf{e}_2 \mapsto \mathbf{x} + \lfloor \frac{ax+c}{b} \rfloor \mathbf{e}_2. \end{array} \right. $$

Then, given a rotation angle $\theta$ and a rotation center $(x_0, y_0)$,

$$ \left| \begin{array}{l} \text{QSR}(\theta, x_0, y_0): \quad \mathbb{Z}^2 \mapsto \mathbb{Z}^2 \\ \mathbf{x} \mapsto \text{HQS}' \circ \text{VQS}' \circ \text{HQS}'(\mathbf{x}). \end{array} \right. $$

with $\text{HQS}' = \text{HQS}(-a', b', \lfloor \frac{b'-2y_0a'}{2} \rfloor)$ and $\text{VQS}' = \text{VQS}(a, \omega, \lfloor \frac{\omega-2ax_0}{2} \rfloor)$ and $\omega = 2^{15}, a = \lfloor \omega \cos \theta \rfloor, a' = \lfloor \omega \cos(\frac{\theta}{2}) \rfloor$ and $b' = \lfloor \omega \sin(\frac{\theta}{2}) \rfloor$. Algorithm 1 presents a symmetrized version of the original QSH algorithm of Andres (1996) used for our experiments.

## A.2 CDLR algorithm

Let us also recall the bijective reflection algorithm as presented in Andres et al. (2019). Algorithm 2 is the base for CDLR computation. Since we are focusing on bijective rotation, we slightly revise this algorithm by double looping over a range of
<caption>**Algorithm 1:** Pseudocode of the symmetrized QSH method</caption>

1 **Function QSH**
   **Input:** $\theta$ rotation angle
   $x_0, y_0$ rotation center
2 $\theta_f = \theta - 2\pi \lfloor \frac{\theta+\pi}{2\pi} \rfloor$ // restrict to $[0, 2\pi[$
3 $Q = \lfloor \frac{1}{2} + \frac{2\theta_f}{\pi} \rfloor$ // Quadrant
4 $\theta_f = \theta - Q \frac{\pi}{2}$ // Angle in $[0, \frac{\pi}{2}]$
5 $\theta_{sym} = \frac{\pi}{2} - \theta_f$ // Sym. angle in $]0, \frac{\pi}{2}]$
6 To all points of the input image
7 **if** $\theta_f - \frac{\pi}{4} > 0$ **then**
8 Apply $QSR(\theta_{sym}, x_0, y_0)$
9 Apply $\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$
10 **else** Apply $QSR(\theta_f, x_0, y_0)$
11 **if** $Q = 1$ **then** Apply $\begin{bmatrix} 0 & -1 \\ 1 & 0 \end{bmatrix}$
12 **else if** $Q = 2$ **then** Apply $\begin{bmatrix} -1 & 0 \\ 0 & -1 \end{bmatrix}$
13 **else if** $Q = 3$ **then** Apply $\begin{bmatrix} 0 & 1 \\ -1 & 0 \end{bmatrix}$

reflections CDLRef and choosing the composition
that minimizes a given metric.

<caption>**Algorithm 2:** Pseudocode of the bijec-
tive reflection method used in CDLR</caption>

1 **Function CDLRef**
   **Input:** $\theta$ the rotation angle
   $x_0, y_0$ the rotation center
   $x, y$ the digital point to rotate
2 $a = \sin \theta, b = \cos \theta$ // Extract slope $a/b$
3 $k = \lfloor (x - x_0) + \frac{a}{b}(y - y_0) + \frac{1}{2} \rfloor$
4 $X : y \mapsto \lfloor \frac{2k-1}{2} + x_0 - \frac{a}{b}(y - y_0) \rfloor$
5 $(x_1, y_1) = (X(\lfloor abk + y_0 \rfloor), \lfloor abk + y_0 \rfloor)$
6 $(x_2, y_2) = (X(\lfloor abk + y_0 \rfloor), \lfloor abk + y_0 \rfloor)$
7 **if** $-b/2 \le a(x_1 - x_0) - b(y_1 - y_0) < b/2$
   **then**
8 $\lfloor (x', y') = (X(2y_1 - y), 2y_1 - y) \rfloor$
9 **else if**
   $-b/2 \le a(x_2 - x_0) - b(y_2 - y_0) < b/2$
   **then**
10 $\lfloor (x', y') = (X(2y_2 - y), 2y_2 - y) \rfloor$
11 **else**
12 $\lfloor (x', y') = (X(y_1 + y_2 - y), y_1 + y_2 - y) \rfloor$