Yukiko Kenmochi

Phuc Ngo

Nicolas Passat

Hugues Talbot

Keywords: topology, digitization, geometric transformations. Math. classification: 00X99

Curvature is a continuous and infinitesimal notion. These properties induce geometrical difficulties in digital frameworks, and the following question is naturally asked: "How to define and compute curvatures of digital shapes?" In fact, not only geometrical but also topological difficulties are also induced in digital frameworks. The -deeper -question thus arises: "Can we still define and compute curvatures?" This latter question, that is relevant in the context of digitization, i.e., when passing from R n to Z n , can also be stated in Z n itself, when applying geometric transformations on digital shapes. This paper proposes a preliminary discussion on this topic.

Digital shapes, digital boundaries and rigid transformations: A topological discussion

Introduction

In the continuous domain, the computation of curvature requires that the considered shapes -and more precisely their boundaries -present certain good properties, mostly in terms of differentiability. When passing from the continuous universe (R n ) to the discrete one (Z n ), the handling of curvature becomes much more complex. It is easy to guess that the induced difficulties derive from the necessity to model infinitesimal properties -namely the differentiability of boundaries -into a finite framework. However, even before considering such geometrical concerns, it is crucial to keep in mind that there also exist topological concerns. Indeed, beyond its putative differentiability, the notion of boundary itself often becomes ill-defined in Z n . In other words, while the boundary of a continuous shape in R n is an object of dimension n -1, and most often a (n -1)-manifold, it is unfortunately infrequent that the boundary of a digital shape in Z n be a discrete hypersurface, and a fortiori a discrete (n -1)-manifold.

During the last decades, some efforts were devoted to tackle this issue in the context of digitization. More precisely, some conditions were provided to guarantee the preservation of good geometrical and topological properties of shape boundaries, when passing from R n to Z n . However, if we now know how to correctly handle curvature during this digitization step, it remains challenging to also define adequate conditions for curvature definition and analysis when processing digital shapes. In particular, it is difficult to preserve correct topological -and thus geometrical -properties of digital shape boundaries when applying geometric transformations, even the most simple one such as rigid transformations.

In this paper -that is mainly related to the works published in [?, ?] -we expose some preliminary results devoted to this question. More precisely, we focus on the specific case of digital shapes defined on Z 2 , and on their behaviour under rigid transformations. Considering such a low dimension and such simple transformations may seem meaningless and irrelevant at a time when the hot topics are related to high-dimension objects under arbitrary deformations. Nevertheless, beyond this apparent triviality, we show that the induced issues are not straightforward, and we intend to develop sound foundations for further developments at higher dimensions and for more general transformations.

(a) S 1 ⊂ R 2 (b) S 2 ⊂ R 2 (c) D(S 1 ) ⊂ Z 2 (d) D(S 2 ) ⊂ Z 2

Digital shapes and their boundaries

Let us consider a finite closed set S in R 2 whose boundary is a (set of) 1-manifold(s) as an original shape. Since computers handle only finite structures, such a continuous shape S is represented as a digital image, i.e., a finite set of pixels associated to points of Z 2 . The induced digital shape is denoted by D(S), referring to the digitization procedure D that allows us to pass from R 2 to Z 2 . There exist several models for D [?]. For instance, if we consider the Gaussian model, we obtain D(S) = S ∩ Z 2 ; in other words, the digital shape D(S) of S is simply obtained by "sampling" S with respect to the regular structure of Z 2 . We will note D(S) the complement of D(S) in Z 2 .

It is mandatory to provide an explicit and sound definition for the notion of boundary of a digital shape D(S). To this end, let us first consider the links that exist between the points of Z 2 and the pixels of a digital image. A pixel P , associated to a point x of Z 2 , can be seen as a unit square of R 2 centered on x. In other words, we have

P = x + [-1/2, 1/2] 2 ⊂ R 2 .
From a structural point of view, the pixels of a digital image are nothing but the Voronoi cells of R 2 induced by the points of Z 2 . In particular, some couples of pixels share a part of their (continuous) boundaries. More precisely, two pixels P 1 and P 2 associated to x 1 and x 2 , respectively, satisfy this assertion iff their exists an edge between x 1 and x 2 in the (dual) Delaunay diagram associated to the above Voronoi diagram.

Based on these considerations, the boundary ∂D(S) of the digital shape D(S), also called the digital boundary for short, is straightforwardly associated to the continuous boundary induced by the pixels of D(S). Indeed, ∂D(S) can be modeled by a set of couples of points (x, x) ∈ D(S)×D(S), that share an edge in the Delaunay diagram of Z 2 . . Some inner and outer r-radius open balls are depicted in magenta, with r higher that the pixel size of the "topologypreserving" digitization grid. (b) A shape that is not r-regular (in cyan). An example of r-radius open balls couple is depicted, where the "inner" ball (in red) does not entirely lie into the shape.

The handling of digital boundaries can be considered from a topological point of view. To this end, we can use the standard notion of neighbourhood stated in digital topology

[?]. The k-neighbourhood of a point x ∈ Z 2 is defined by N k (x) = {y ∈ Z 2 | x -y p = 1}, for k = 4, 8
where p = 1, ∞, respectively. Then, the boundary of D(S) is defined by

∂D(S) = {(x, y) | x ∈ D(S), y ∈ D(S), y ∈ N 4 (x)}.
Figure 1 illustrates two examples of digitization procedure, where it is easily seen that the topology of a digital shape is not always the same as that of the initial continuous shape. More precisely, we observe that digital shape boundaries are not always guaranteed to be 1-manifolds, even though the original shape boundaries are.

Digitization and topology preservation

The issue of topological alteration of shape boundaries during the digitization process has been considered in the literature. In particular, Latecki et al. defined some conditions for guaranteeing boundary integrity, based on two key notions, namely r-regularity and well-composedness.

Definition 1 (r-regularity [?]). A closed set S ⊂ R 2 is r-regular if for each boundary point of S, there exist two tangent open balls of radius r, lying entirely in S and its complement S, respectively. This definition derives from classical concepts of differential geometry, namely osculating balls and normal vectors. By considering the class of r-regular shapes in R 2 , the condition for preserving topological properties -especially in terms of boundaries -between a continuous shape and its digital counterpart is the following.

Proposition 2 ([?]

). An r-regular set S ⊂ R 2 has the same topological structure as its digitized version D(S), for pixels of size d < r.

This result is indeed an extension of the compatibility property between S and D(S), presented by Pavlidis in [?]. In particular, Latecki et al. were driven by more pragmatic motivations, related to some sampling devices for image acquisition, like CCD cameras. Figure 2 provides an example and a counterexample of r-regular shapes.

In [?], it was also shown that the (topology-preserving) digitization process of an r-regular shape must yield a well-composed shape [?], whose definition relies on the following concepts of adjacency, connectedness and connected components, in digital topology [?]. Let X be a digital shape in Z 2 . We say that two distinct points x, y of X are k-adjacent (for k = 4, 8) if x ∈ N k (y) (and -equivalently -y ∈ N k (x)). From the induced (symmetric) k-adjacency relation on X, we obtain, by reflexive-transitive closure, the (equivalence) k-connectedness relation. The k-connected components of X are the equivalence classes for this relation. From these notions, we can define the notion of well-composedness.

X 1 of Z 2 (in black). Its boundary ∂X 1 (in green) is a 1-manifold. (b) A shape X 2 of Z 2 (in black) that is not well-composed.
Its boundary ∂X 2 (in green) is not a 1-manifold (see the red dots).

Definition 3 (Well-composedness [?]

). A digital shape X in Z 2 is well-composed if each 8connected component of X and of its complement X is also a 4-connected component.

Based on this definition, it is plain that the boundary ∂X of a digital shape X is a 1-manifold whenever X is well-composed. Some examples and counter-examples of well-composed shapes are provided in Figure 3.

As stated above, there actually exists a strong link between r-regularity and well-composedness.

Theorem 4 ([?]

). If S is r-regular, then D(S) is well-composed.

Consequently, a continuous shape S of R 2 that is r-regular -and whose boundary is a continuous 1-manifold that authorises curvature analysis -still presents good properties after digitization, since its digital counterpart D(S) is well-composed and then also presents as border ∂D(S) a 1-manifold.

Rigid transformations of digital shapes

As stated above, in the digital framework, curvature analysis makes sense when considering shapes that are well-composed. In the continuity of this result, the question that we consider now is the following: "What are the conditions for allowing curvature analysis not only on a digital shape X but also on its image by a geometric transformation?". In particular, we focus on the most simple -yet non-trivial -case of rigid transformations.

In R 2 , a rigid transformation is a function

T : R 2 → R 2 x → R.x + t (4.1)
where R is a rotation matrix, i.e., an element of the group SO(2), and t ∈ R 2 is a translation vector. The rigid transformation T is a bijection, and its inverse function T -1 is also a rigid transformation.

Based on these definitions, the digital rigid transformations consist of composing the continuous rigid transformations with the standard rounding operator. We note RIG Z 2 the set of all the digital rigid transformations.

Two transformation models can be considered for a digital rigid transformation T associated to a transformation T . The Lagrangian (forwards) model consists of computing the direct image of the digital shape X by the transformation. However, as T is often neither injective nor surjective, this leads to topological defects. The Eulerian (backwards) model consists of computing the transformed image X T as the shape whose image by the digital analogue T -1 of the inverse function T -1 of T , lies into X. This is more satisfactory, since T -1 is defined on the whole transformed space Z 2 . In this model, that we consider hereafter, we have

X T = D(T (X ⊕ )) (4.2)
where ⊕ is the classical dilation operator defined in mathematical morphology [?, Ch. 1], and is the unit square of R 2 , centered on the origin. These relationships with well-known concepts of mathematical morphology are actually not a coincidence, as it will be discussed later. Unfortunately, the Eulerian model is not exempt from topological difficulties. In particular, the family of well-composed shapes is not stable with respect to RIG Z 2 . In other words, the transformed shape X T obtained from a well-composed shape X with respect to a digital rigid transformation T is not necessarily well-composed itself. In that case, its topological properties are, of course, altered, and in particular, its boundary is no longer a (set of) 1-manifold(s). See Figure 4 for an example.

Rigid transformations and topology preservation

In this section, we summarise the main contribution of this work, that consists of defining a subfamily of well-composed shapes that remain stable -and topologically invariant -under any digital rigid transformations. The digital shapes forming this family are called regular, in reference to the above notion of r-regularity for continuous shapes in R 2 . The set of regular digital shapes can be defined in Z 2 as follows.

Definition 5 ((Non-)singular shapes). Let X ⊂ Z 2 be a digital shape. We say that X is singular if at least one point x of X (resp. X) has its whole 4-adjacent set included in X (resp. X).

Definition 6 (Regularity [?, ?]). Let X ⊂ Z 2 be a non-singular, well-composed shape. We say that X is regular if for any 4-adjacent points x, y ∈ X (resp. X), there exists a 2 × 2 set = {z, z + 1} × {t, t + 1} ⊂ Z 2 such that x, y ∈ ⊆ X (resp. X).

The regularity of a digital shape can be characterised as follows, and thus leads to a linear-time complexity pattern-based regularity analysis.

Proposition 7 ([?, ?]). A digital shape X ⊂ Z 2 is regular iff none of the configurations depicted in Figure 5 appears in X and X.

Note that the first configuration (Figure 5(a)) characterises the non-well-composed shapes [?]. The main interest of regularity is to guarantee the stability of well-composed shapes -and their topological invariance -under any rigid transformation. In particular, we have the following result.

Theorem 8 ([?]

). Let X ⊂ Z 2 be a well-composed shape. If X is regular, then, for any digital rigid transformation T , the transformed digital shape X T is still well-composed, and has the same topological structure as X.

Remark 9. This result establishes regularity as a sufficient condition for the stability of wellcomposedness, together with topological invariance. Our conjecture is however that this condition is also necessary. Following mathematical morphology terminology [?, Ch. 1], if X is regular, then X is opened and closed by any structuring element , i.e.

γ (X) = X ⊕ = X (5.1) φ (X) = X ⊕ = X (5.2)
However, the converse is not true, as illustrated in Figure 6. Nevertheless, it is plain that there exist strong links between these morphological operations and the notions of regularity and topological invariance. Our conjecture is that the regular shapes X are exactly those whose both the dilated X ⊕ and the eroded X have the same topological structure as X. This intuition derives from the continuous analogue of this assertion for r-regular shape S of R 2 , where the discs of radius r play the role of [?].

Conclusion

This work constitutes a preliminary attempt to provide solutions for curvature definition and analysis of digital shapes, not only in their initial space but also in the spaces obtained under rigid transformations.

Some results have been proposed in the specific case of shapes in Z 2 under rigid transformations. It has been proved in [?] that these results can, of course, be interpreted in the framework of binary digital images, but also extended to grey-level and label images, thus providing efficient image processing and analysis strategies.

Nevertheless, many efforts remain to do towards solutions in more general cases. In particular, the handling of (i) higher dimensions, i.e., Z 3 and more generally Z n for n ≥ 3, and (ii) arbitrary geometric transformations, still remain open issues. Moreover, it may be important to derive not only sufficient, but also necessary conditions, for curvature analysis. It may additionally be useful to deal with both Eulerian and Lagrangian models.

Even though this preliminary study allows us to understand and solve some topological problems of digital shapes under their rigid transformations, geometrical problems still remain: geometries of digital shapes are not preserved under rigid transformations in general. For example, see Figure 7. It is expected to investigate geometry-preserving conditions of digital shapes during their rigid transformations as well. (a) A digital half plane, which is regular, and (b) its transformed shape, which is still well-composed (i.e., the topology is preserved) but not a digital half plane any more (i.e., the geometry is not preserved).

Figure 1 .

 1 Figure 1. (a,b) Continuous shapes S 1 and S 2 in R 2 (in cyan) and their boundaries (in blue). (c,d) The associated digital shapes D(S 1 ) and D(S 2 ) in Z 2 (in cyan), and their digital boundaries (in blue). (c) The digital boundary of D(S 1 ) is a 1-manifold. (d) The digital boundary of D(S 2 ) is not a 1-manifold, by contrast with that of S 2 .

Figure 2 .

 2 Figure2. (a) An r-regular shape (in cyan). Some inner and outer r-radius open balls are depicted in magenta, with r higher that the pixel size of the "topologypreserving" digitization grid. (b) A shape that is not r-regular (in cyan). An example of r-radius open balls couple is depicted, where the "inner" ball (in red) does not entirely lie into the shape.

Figure 3 .

 3 Figure 3. (a) A well-composed shape X 1 of Z 2 (in black). Its boundary ∂X 1 (in green) is a 1-manifold. (b) A shape X 2 of Z 2 (in black) that is not well-composed. Its boundary ∂X 2 (in green) is not a 1-manifold (see the red dots).

Figure 4 .

 4 Figure 4. An original digital circle (left) and its rigid transformations (center and right). The original digital shape is well-composed while the transformed ones are not well-composed.

Figure 5 .

 5 Figure 5. Forbidden patterns in regular shapes (up to π/2 rotations, symmetries and value inversion).

Figure 6 .

 6 Figure 6. (a) A regular shape (in black). (b) A non-regular shape (in black) that is however opened and closed by a structuring element .

Figure 7 .

 7 Figure 7. (a) A digital half plane, which is regular, and (b) its transformed shape, which is still well-composed (i.e., the topology is preserved) but not a digital half plane any more (i.e., the geometry is not preserved).

Acknowledgements

The research leading to these results has received partial funding from the French Agence Nationale de la Recherche (Grant Agreement ANR-10-BLAN-0205).


Phuc Ngo

Yukiko Kenmochi

Nicolas Passat

Hugues Talbot

Combinatorial properties of 2D discrete rigid transformations under pixel-invariance constraints

Keywords: combinatorial structure, discrete rigid transformation, pixel-invariance constraints

come   L'archive ouverte pluridisciplinaire

Introduction

Rigid transformations, (i.e., transformations based on translations and rotations) are involved in the design of many computer vision and image processing techniques (see, e.g., [START_REF] Yilmaz | Object tracking: A survey[END_REF][START_REF] Zitová | Image registration methods: A survey[END_REF]). Such transformations are generally performed by considering the Euclidean space (R n ) associated to the Eulerian space (Z n ) of the data. As a consequence, they need to be interfaced with a subsequent digitization process to finally produce results in Z n .

In [START_REF] Ngo | Combinatorial structure of rigid transformations in 2D digital images[END_REF], we have recently proposed to study rigid transformations on Z 2 as a fully discrete process. In this context, three main questions were considered: (i) How many rigid transformations can be defined on a finite subspace of Z 2 ? (ii) How to generate all of them? (iii) What are the topological relationships between them? Some combinatorial and algorithmic answers, inspired by the approaches developed in [START_REF] Hundt | Combinatorial bounds and algorithmic aspects of image matching under projective transformations[END_REF][START_REF] Hundt | A combinatorial geometrical approach to twodimensional robust pattern matching with scaling and rotation[END_REF], were provided, and then contributed to the state of the art in this research field [START_REF] Hundt | Combinatorial bounds and algorithmic aspects of image matching under projective transformations[END_REF][START_REF] Hundt | A combinatorial geometrical approach to twodimensional robust pattern matching with scaling and rotation[END_REF][START_REF] Amir | Faster two-dimensional pattern matching with rotations[END_REF][START_REF] Thibault | Rotations in 2D and 3D discrete spaces[END_REF]. In [START_REF] Ngo | Combinatorial structure of rigid transformations in 2D digital images[END_REF], a combinatorial structure -namely a graph -is used to represent the 2D discrete rigid transformations. This structure has a polynomial complexity O(N 9 ) where N × N is the size of images. However, this high complexity makes it difficult to generate the whole graph for large images, and to further find admissible transformations that best match two given images, namely a template and a target image; the later problem is called image registration. Practically in computer vision, some constrained search paradigms are used for registration issues (see, e.g., [START_REF] Zitová | Image registration methods: A survey[END_REF][START_REF] Amintoosi | A fast image registration approach based on SIFT key-points applied to super-resolution[END_REF]). Indeed the constraints introduce prior knowledge of transformations and contribute to reduce the research space.

In this article, we extend the study initiated in [START_REF] Ngo | Combinatorial structure of rigid transformations in 2D digital images[END_REF], by investigating the effects of geometric constraints on the proposed graph. In particular, we focus on pixel-invariance constraints, which consist of forcing the correspondence between points in an initial (sub)space (of Z 2 ) and transformed points -or more generally regions.

This study is organised as follows. We first recall background notions on discrete rigid transformations (Sec. 2), and express pixel-invariance constraints in the associated parameter space (Sec. 3). We then develop an algorithmic process for generating a combinatorial structure modeling all the discrete rigid transformations and their relationships under the given constraints (Sec. 4). A complexity analysis is proposed for this algorithm and the induced structure (Sec. 5). Finally, we conclude the article (Sec. 6).

2 Background notions of discrete rigid transformations

Digital images and digital rigid transformations

In the continuous framework, an image can be formalised as a function I : R 2 → V, where V is any value space. A digital image associated to I can then be defined as I : Z 2 → V, by sampling I on the discrete space Z 2 . In other words, we have I = I |Z 2 , and for each p ∈ Z 2 , the value I( p) models the value of I on the associated pixel p + [- 1 2 , 1 2 ] 2 , namely the Voronoi cell of R 2 induced by Z 2 around p. This paradigm relies on the digitisation function, where [ . ] is a rounding operator, defined as

D : R 2 -→ Z 2 (x, y) -→ ([x], [y]) (1)
In the continuous framework, a 2D rigid transformation, composed of translation and rotation, is expressed as a bijection T : R 2 → R 2 defined, for any x = (x, y) ∈ R 2 , by

T (x) = ( cos θ -sin θ sin θ cos θ ) ( x y ) + ( a b ) (2)
where a, b, θ ∈ R and θ ∈ [0, 2π[. In particular, such a transformation is unambiguously modeled by the triplet of parameters (a, b, θ), and will sometimes be noted by T abθ . When applied on an image I : R 2 → V, it provides a new transformed image

I • T -1 : R 2 → V.
Following the digitisation paradigm proposed above, a digital rigid transformation T : Z 2 → Z 2 associated to T can be defined, for any p = (p, q) ∈ Z 2 , by

T (p) = D • T (p) = ( [p cos θ -q sin θ + a] [p sin θ + q cos θ + b] ) (3)
In general, this function is not bijective. However, by setting T -1 :

Z 2 → Z 2 as T -1 = D • T -1 , it becomes possible to define the digital transformed image I • T -1 : Z 2 → V
with respect to T . In the sequel of this article, we focus on such digital rigid transformations. From this point on -for the sake of readability and without loss of correctness -we will denote them T instead of T -1 , due to the bijectivity of T and T -1 .

Discontinuities of digital rigid transformations

For any x in Eq. ( 2), if we change the value of (a, b, θ) slightly, then the new point T ( p) also changes slightly. More formally, the function (a, b, θ) → T abθ is continuous. Contrariwise, in Eq. ( 3), an infinitesimal variation of (a, b, θ) may lead to a variation of T (p) from a point of Z 2 to another one. More precisely, the parameter space R We focus in particular on the triplets (a, b, θ) and their associated transformations T abθ , which lead to such discontinuities in the space of digital rigid transformations. Such critical transformations are those that map at least one discrete point onto the discrete half-grid

H = ( R × (Z + 1/2) ) ∪ ( (Z + 1/2) × R ) (i.e.
, the boundaries of the Voronoi cells of R 2 induced by Z 2 ). Definition 1 ( [START_REF] Ngo | Combinatorial structure of rigid transformations in 2D digital images[END_REF]) Let (a, b, θ) ∈ R 3 , and T abθ : R 2 → R 2 be its associated rigid transformation. We say that T abθ is a critical transformation if ∃p ∈ Z 2 s.t. T abθ (p) ∈ H.

It is plain that in the parameter space (a, b, θ), the critical transformations are modeled by 2D surfaces analytically defined, for any p = (p, q) ∈ Z 2 and k, l ∈ Z, by

Φ pqk : R 2 -→ R (b, θ) -→ a = ϕ pqk (θ) = k + 1 2 + q sin θ -p cos θ, (4)
Ψ pql : R 2 -→ R (a, θ) -→ b = ψ pql (θ) = l + 1 2 -p sin θ -q cos θ. (5)
The surfaces Φ pqk (resp. Ψ pql ) are termed tipping surfaces [START_REF] Ngo | Combinatorial structure of rigid transformations in 2D digital images[END_REF]. Their intersection ϕ pqk (resp. ψ pql ) on the 2D plane (a, θ) (resp. (b, θ)) are called tipping curves. These tipping surfaces/curves, which correspond to the discontinuities of digital rigid transformations expressed in the parameter space (a, b, θ), are illustrated in Fig. 1.

Partition of parameter space and discrete rigid transformation graph

The digitisation process (Eq. ( 1)) generally maps distinct rigid transformations (Eq. ( 2)) onto the same digital rigid transformation (Eq. ( 3)). More precisely, the set of all the non-critical transformations can be partitioned into equivalence classes induced by the equivalence relation ∼ defined by ( In [START_REF] Ngo | Combinatorial structure of rigid transformations in 2D digital images[END_REF], we have shown that this subdivision of the parameter space could be modeled using a dual combinatorial structure, namely a graph. In particular, each 3D open cell (i.e., each DRT) is associated to a vertex, and each tipping-surface segment (linked to a critical transformation) shared by two adjacent 3D open cells, is associated to an edge. The resulting graph is called a DRT graph [START_REF] Ngo | Combinatorial structure of rigid transformations in 2D digital images[END_REF] (see Fig. 2).

T abθ ∼ T a ′ b ′ θ ′ ) ⇐⇒ (T abθ = T a ′ b ′ θ ′ ).
From a theoretical point of view, the notions introduced above are correctly defined for images and transformations on Z 2 and R 2 . Practically, our purpose is to study such transformations on images of finite sizes. Under this hypothesis, only a finite subset of digital rigid transformations are relevant, namely those which actually affect such finite images. From this point on, we focus on this finite case and assume that the digital images are defined on subsets of Z 2 of size N × N (N ∈ N). We have the next property.

Property 2 ([5])

The DRT graph associated to a digital image of size N × N has a space complexity of O(N 9 ).

In [START_REF] Ngo | Combinatorial structure of rigid transformations in 2D digital images[END_REF], an exact computation algorithm was also proposed to build this graph in linear time w.r.t. its size. The DRT graph models a kind of "neighbouring" relationship between DRTs. Indeed, the existence of an edge between two vertices indicates that the associated transformations differ in one pixel among the N 2 ones. This property opens a way of involving this combinatorial structure in image processing tasks.

We now study the effects of forcing the correspondence between points in the initial and transformed spaces. We focus in particular on the subdivision of the parameter space and the induced graph from the algorithmic and combinatorial points of view.

3 Constraints and feasible rigid transformation set

Pixel-invariance constraints and interpretation in the parameter space

In the context of rigid transformations in R 2 , forcing the correspondence between points p in the initial space and p ′ in the transformed one leads to restricting the transformations T . Moreover, forcing the correspondence between k ≥ 2 distinct pairs of points ( p i , p ′ i ) restricts the number of feasible transformations T to at most one. Indeed, from the relation expressed in Eq. ( 2) we obtain for every pair of corresponding points two equations representing the trigonometric surfaces. We then need at least two pairs of corresponding points to obtain a rigid transformation as the feasible transformation. As illustrated in Fig. 3(a), each pair of surfaces represents a pair of corresponding points, and the intersection of two pairs of surfaces determines the feasible transformation.

Restricting discrete rigid transformations, under similar constraints, is more permissive. Indeed, when forcing the correspondence between one or several pairs of pixels ( p i , p ′ i ) of Z 2 , a larger space of transformations may remain valid (see Fig. 3(b-g)).

Definition 3 Let p = (p, q) ∈ A ⊂ Z 2 and p ′ = (p ′ , q ′ ) ∈ B ⊂ Z 2 , such that A, B

are of size N × N. There exists a pixel-invariance constraint between p and p ′ if the authorised digital rigid transformations T between A and B satisfy the equality T

(p) = p ′ , i.e., if p ′ -1/2 < p cos θ -q sin θ + a < p ′ + 1/2, ( 6
)
q ′ -1/2 < p sin θ + q cos θ + b < q ′ + 1/2. ( 7
)
More generally, there exist pixel-invariance constraints between two sets { p i } m i=1 and

{ p ′ i } m i=1 (m ≥ 1) if T ( p i ) = p ′ i (i.e., if Eqs. (6)-(7) are satisfied) for every i ∈ [[1, m]].
In absence of constraints, the 3D parameter space (a, b, θ), induced by the subset of size N × N where the image is defined, is divided into cells whose boundaries are all the tipping surfaces Φ pqk and Ψ pql , with p, q ∈ [[0, N -1]] and k, l ∈ [[0, N]]. In this context, the whole volume of the parameter space models adequate rigid transformations.

In contrast, under a pixel-invariance constraint, some discrete rigid transformations may become irrelevant. Equivalently, only a part of the parameter space -namely the subspace of parameters (a, b, θ) that satisfy this constraint -remains valid. From Eqs. ( 6)- [START_REF] Thibault | Rotations in 2D and 3D discrete spaces[END_REF], this parameter subspace is defined by the intersection of 4 half-spaces associated to 4 tipping surfaces for one pixel correspondence (see Fig. 3(b)).

Feasible rigid transformation set

More generally, if a set P of m pixel correspondences is provided, the parameter subspace of relevant transformations is defined as the intersection of m regions induced by these constraints, i.e., as the intersection of 4m half-spaces defined by Eqs. ( 6)-( 7). Let us first define the half-spaces induced by tipping surfaces Φ pqk and Ψ pql :

H + pqk = {(a, b, θ) | a > Φ pqk (b, θ)} and H - pqk = {(a, b, θ) | a < Φ pqk (b, θ)}, (8)
V + pql = {(a, b, θ) | b > Ψ pql (a, θ)} and V - pql = {(a, b, θ) | b < Ψ pql (a, θ)}. (9)
The subspace of interest, called feasible rigid transformation set, is defined as follows.

Definition 4 Let P = {(p i , p ′ i )} m i=1 (m ≥ 1
) be a set of corresponding pixel pairs. The feasible rigid transformation set (FRTS) associated to P is the subspace R ⊂ R 3 of the parameter space (a, b, θ), defined as

R = ∩ i∈[[1,m]] ( H + p i q i p ′ i ∩ H - p i q i p ′ i +1 ∩ V + p i q i q ′ i ∩ V - p i q i q ′ i +1
) .

Note that a constraint of one pixel pair (namely, m = 1), the FRTS is observed as a "tube" in the parameter space (a, b, θ) (see Fig. 3(b)). We can consider that a pixelinvariance constraint leads to all rotations with a center

x ∈ R 2 inside of pixel p ∈ Z 2 (i.e., x ∈ p+[-1/2, 1/2] 2 )
. For constraints of two pixel pairs (namely, m = 2), the FRTS becomes a "bounded region" (see Fig. 3(c)).

The FRTS generated by m pixel correspondences is divided into DRTs induced from the (N 2m) remaining pixels of the given image of size N × N. In particular, the combinatorial structure of DRTs in a FRTS, modeling this subdivision, is a subgraph of the DRT graph. We introduce, in the following, a notion of directional convexity of a region R, such that R is "convex along an axis", and show that any FRTS R is directionally convex. This property is used in the next sections to study the combinatorial structure of DRTs in R.

Definition 5

We say that a region R ⊆ R n in an n-variable space (x 1 , . . . ,

x n ) is x k - convex if, for any two points p 1 , p 2 ∈ R such that the segment [p 1 p 2 ] = {α.p 1 +(1-α).p 2 | α ∈ [0, 1]} is parallel to the x k -axis, [ p 1 p 2 ] is included in R.
Property 6 The FRTS R is both a-and b-convex. [START_REF] Hundt | A combinatorial geometrical approach to twodimensional robust pattern matching with scaling and rotation[END_REF] Combinatorial structure of discrete rigid transformations in a feasible rigid transformation set

So far, we know that a FRTS contains all rigid transformations satisfying all constraints, and is subdivided into DRTs (see Sec. 2.3). This section presents a method for constructing a combinatorial structure of DRTs in a FRTS by following the three stages:

(1) finding the boundaries of a FRTS, (2) finding tipping surfaces passing a FRTS and (3) constructing a DRT graph in a FRTS. Before describing these stages, we first explain an algorithm for building a graph modeling a subdivision of the parameter space from a given set of tipping surfaces, which is used later in the first and third stages.

Sweeping algorithm for incremental partition graph construction

We may generalize the problem of subdivision of the parameter space by tipping surfaces as follows: given a set of tipping surfaces S , we would like to construct a graph modeling the subdivision of the parameter space (a, b, θ) induced by S . Such a graph is called a partition graph and denoted by G. In G each vertex is associated to a 3D open cell of the subdivision, and each tipping-surface segment shared by two adjacent 3D open cells, is associated to an edge. This problem can be answered with the help of 3D arrangements of surfaces [START_REF] Sharir | Recent developments in the theory of arrangements of surfaces[END_REF]. In [START_REF] Ngo | Combinatorial structure of rigid transformations in 2D digital images[END_REF], we have proposed the sweeping algorithm for constructing a DRT graph of a given image (see Section 2.3), which is a specific case of generating a partition graph. Such a method has a complexity O(n 3 ), where n is the number of surfaces. Here we present a similar method that builds the partition graph G based on the relations that link tipping surfaces and tipping curves (see Eqs (4)-( 5) and Fig. 1). Such a subdivision can be fully described from its two cross-sections on the planes (a, θ) and (b, θ), respectively expressed by two sets of tipping curves. Therefore, instead of constructing directly the partition graph in the 3D parameter space (a, b, θ), we will first build the structures of the graphs in the 2D planes (namely, (a, θ) and (b, θ) planes), and then combine them to build the complete partition graph. Note that G becomes a DRT graph if we consider all tipping surfaces for a given image. We first define a cut for a plane -either (a, θ) or (b, θ) -denoted by γ, as a monotonic line intersecting exactly once for each tipping curve in the plane. A cut is then represented by its sequence of intersecting tipping curves (see Fig. 4(a)). Such a cut can be modeled by a directed graph according to their sequences of tipping curves.

Definition 7 Let γ = (ϕ 1 , ϕ 2 , . . .) be a cut. A graph G γ = (V γ , E γ ) w.r.t. γ consists of -a set of vertices V γ = {v 0 , v 1 , .
. .}, and -an ordered set of labelled edges E γ = ((v 0 , v 1 , ϕ 1 ), (v 2 , v 1 , ϕ 2 ), . . .) and each edge (u, w, f ) ∈ E γ connects two vertices u, w ∈ V γ separated by the tipping curve f , which is considered as an edge label. In practice, elements of E are also ordered in the same way as γ (see Fig. 4(a)).

The main idea of the sweeping method in 2D is that a cut is swept through all tipping curves on the plane in finite time, allowing us to construct the graph afterwards. We assume that γ starts at θ = 0 and ends at θ = 2π. While sweeping the cut, its sequence changes only at intersections of tipping curves, called event points. The moment at which a cut reaches an event point, the algorithm performs an update of its sequence, and generates new vertices and edges in the graph (see Fig. 4(b)). We call this an elementary step of the algorithm. The set of event points forms a series of elementary steps. Therefore, instead of moving the cut continuously, we need to maintain a set of sorted event points w.r.t. θ, and progress the cut in their increasing order to build the graph incrementally.

For building a graph G in 3D, two cuts are used such that each cut sweeps on either the plane (a, θ) or (b, θ). We denote those cuts by γ a and γ b respectively. For each update of the cuts, γ a and γ b , the associated graphs, G γ a and G γ b , are respectively modified, so that a part of G is generated. We call such a part of G a partial graph, denoted by δG . In fact, δG is a combination of the two graphs G γ a and G γ b as follows (see Fig. 5).

Definition 8 The partial graph δG

= (δV, δE) is generated from G γ a = (V γ a , E γ a ) and G γ b = (V γ b , E γ b ), such that -δV = {(v a , v b ) | v a ∈ V γ a , v b ∈ V γ b }, and -δE = {((u 1 , v), (u 2 , v), ϕ u ) | u 1 , u 2 ∈ V γ a , v ∈ V γ b , (u 1 , u 2 , ϕ u ) ∈ E γ a } ∪ {((u, v 1 ), (u, v 2 ), ϕ v ) | v 1 , v 2 ∈ V γ b , u ∈ V γ a , (v 1 , v 2 , ϕ v ) ∈ E γ b }.
Therefore, when an elementary step is applied, the sweep progresses as the partial graph δG is generated and integrated in G for constructing the final graph as well. The following proposition has been originally proposed in [START_REF] Ngo | Combinatorial structure of rigid transformations in 2D digital images[END_REF] for constructing a DRT graph, and this is valid for a partition graph as well.

Proposition 9 Let S be a set of tipping surfaces and G be a partition graph modeling the subdivision of the parameter space by S . We have

G = ∪ i∈[[1,e]] δG i ,
where δG i is a partial graph at the i-th elementary step and e is the number of ordered event points.

More details about the sweeping algorithm for tipping surfaces can be found in [START_REF] Ngo | Combinatorial structure of rigid transformations in 2D digital images[END_REF].

Finding the feasible rigid transformation set boundary

It is possible to describe a FRTS R by a set of half-spaces constituting the boundary of R, instead of using all the half-spaces of R as described in Definition 4. This section explains how to find such a set using the above sweeping algorithm.

A FRTS R in the parameter space (a, b, θ) can be fully described from its two crosssections R H and R V on planes (a, θ) and (b, θ), defined as

R H = ∩ i∈[[1,m]] ( h + p i q i q ′ i ∩ h - p i q i q ′ i +1 ) and R V = ∩ i∈[[1,m]] ( v + p i q i p ′ i ∩ v - p i q i p ′ i +1 ) (10)
where h + p i q i q ′ i and h -

p i q i q ′ i +1 (resp. v + p i q i p ′ i and v - p i q i p ′ i +1
) are the cross-sections in the plane (a, θ) (resp. (b, θ)) of H + p i q i q ′ i and H -

p i q i q ′ i +1 (resp. V + p i q i p ′ i and V - p i q i p ′ i +1
). This is illustrated in Fig. 3(d-g). They are expressed as shown in Eq. ( 8) (resp. Eq. ( 9)) by replacing the tipping surfaces Φ pqk and Ψ pql by the tipping curves ϕ pqk and ψ pql respectively. We call h + pqk , v + pql , upper half-planes and h - pqk , v - pql lower half-planes. Relying on the similarity of R V and R H , hereafter we consider only R H . Our problem is then specified as follows: given a constraint set of half-planes of R H defined from m corresponding pixel pairs, P = {(p i , p ′ i )} m i=1 , report the boundary half-planes of R H . From Property 6, it is obvious that R H contains two sets of boundary half-planes:

-a upper boundary sequence U = (h + p i q i q ′ i , . . .) contains only the upper half-planes; -a lower boundary sequence L = (h - p i q i q ′ i +1 , . . .) contains only the lower half-planes. The 2D sweeping algorithm, presented in Sec. 4.1, is used to find such U and L of R H , such that the cut γ is now represented as a sequence of half-planes intersecting it. Note that no partition graph is built in this stage, and we only need to observe the sequence of the cut γ during its update in order to obtain U and L. Indeed, while sweeping γ its sequence changes at event points. We remark that γ is in R H when its sequence of half-planes is separated into two successive sequences of γ + and γ -, namely γ = γ + γ -, where γ + contains only the upper half-planes and γ -contains only the lower half-planes. Moreover, we see that the last element of γ + and the first element of γ - determine the upper and lower boundaries of R H respectively. The cut is located out of R H when there is no more such a separation. According to the change of γ in R H , the

= (h + 111 , h - 112 , h + 001 , h - 002 ); when it goes in R H it has become γ 2 = (h + 001 , h + 111 , h - 002 , h - 112 ); when it goes out of R H it becomes γ 3 = (h + 111 , h - 112 , h + 001 , h - 002 ). (b)
Example of tipping surfaces (in red) passing R in the parameter space (a, b, θ) and (c) its cross-section R H on the plane (a, θ).

upper and lower boundaries are added progressively in U and L at each event point. See Fig. 6(a) for the illustration.

By using two cuts γ a and γ b sweeping on the two planes (a, θ) and (b, θ), we can find the boundary of a FRTS R. At each event point either on (a, θ) or (b, θ), the algorithm updates and checks the sequences of both cuts. From this, we obtain the boundary of R, and the first θ at which both sequences of γ a and γ b are separated in two parts (resp. have no more separation), denoted by θ min (resp. θ max ) of R that need in the next stage.

Finding tipping surfaces passing by a feasible rigid transformation set

As the subdivision of a FRTS R is induced by the tipping surfaces existing in R (see Fig. 6(b)), we need to determine tipping surfaces among all Φ pqk and Ψ pql for p, q ∈ [[0, N -1]] and k, l ∈ [[0, N]], where N × N is the image size. Now looking at the cross-sections of R, this problem is equivalent to finding tipping curves ϕ pqk (resp. ψ pql ) passing R H (resp. R V ) (see Fig. 6

(c)).

A tipping curve ϕ pqk passes R H if it intersects one of the boundary segments of ϕ p ′ q ′ k ′ of R H . This is easily verified by the following steps: (i) verify if ϕ pqk and ϕ p ′ q ′ k ′ intersect, i.e., if the following relation is satisfied [5, Property 2]: ϕ pqk (θ) and a lower = min

∆ 1 +∆ 2 > 0 and |KP± √ ∆ 1 | ≤ P 2 +Q 2 and |KQ± √ ∆ 2 | ≤ P 2 +Q 2 , where P = p-p ′ , Q = q-q ′ , K = k-k ′ , ∆ 1 = P 2 (P 2 +Q 2 -K 2 ) and ∆ 2 = Q 2 (P 2 +Q 2 -K 2 ); (ii) if
h - pqk ∈L ϕ pqk (θ),
and verify if a upper ≤ a ≤ a lower , where the value a at the above intersection θ is calculated from Eq. ( 4).

Note that the values cos θ and sin θ are used to represent θ. All cos θ, sin θ, cos θ min , sin θ min , cos θ max , sin θ max , a, a min and a max are quadratic irrationals 4 . As shown in [START_REF] Ngo | Combinatorial structure of rigid transformations in 2D digital images[END_REF], their comparisons can be achieved exactly in constant time.

We define tipping surfaces of interest as a set of tipping surfaces that bound or pass a FRTS R. Similarly, tipping curves of interest of R H (resp. R V ) is the set of the boundary tipping curves of R H (resp. R V ) and the tipping curves passing R H (resp. R V ).

DRT-graph construction in a feasible rigid transformation set

In order to build the DRT graph in a FRTS R, we use the sweeping algorithm described in Sec. 4.1. However the cut γ in this part sweeps from θ min to θ max instead of [0, 2π[, and contains only tipping surfaces existing between the upper and lower boundaries of R. The following question then arises: how can we detect event points in R? Or when is an elementary step applied? Because of the similarity of R V and R H , in the following we consider only the cross-section R H of R. Event points in R H are now defined as intersections of tipping curves of interest being either on a boundary segment or inside of R H , as illustrated in Fig. 6(c). According to its nature, it is called either a boundary event point or an inside event point. Similarly to the method in Sec. 4.3 if an intersection coordinate (θ, a) satisfies θ min ≤ θ ≤ θ max and a min ≤ a ≤ a max , then it is verified to be an event point. The algorithm described in Sec. 4.1 deals with any inside event points. In contrary, the boundary event points must be treated separately as follows.

As described in Sec. 4.1, an elementary step at each event point consists of (i) updating the graphs G γ a and G γ b according to the change of γ a and γ b respectively (explained below) and (ii) building the partial graph δG from G γ a and G γ b (see Definition 7).

In [START_REF] Ngo | Combinatorial structure of rigid transformations in 2D digital images[END_REF], we classified inside event points into two cases: simple intersections and degeneracies (see Fig. 7). Figure 8 shows an elementary step at a simple intersection. In [START_REF] Ngo | Combinatorial structure of rigid transformations in 2D digital images[END_REF], the degeneracies are processed by modifying this simple case.

Regarding boundary event points, they can be classified into the following six cases (Fig. 9), which are easily detected by checking the tipping curves intersecting at the event point with the tipping curves in γ and the upper and lower bound sequences U and L. The procedure for handling them in simple cases is explained below, while the degenerate cases are treated similarly to [START_REF] Ngo | Combinatorial structure of rigid transformations in 2D digital images[END_REF] and omitted in this paper due to the page number limitation. As illustrated in Fig. 9, an event point:

-changes the boundary, which is either upper (a) or lower (b); -does not change the boundary, such that one of the tipping curves • goes in (resp. out) R by the upper boundary (c) (resp. (d));

• goes in (resp. out) R by the lower boundary (e) (resp. (f)). We first explain how to update the cut for (a) and (b). Without loss of generality, let q = {ϕ u , ϕ v } be a boundary event point generated by two tipping curves ϕ u , ϕ v and γ, γ ′ be the cuts before and after q respectively. Assuming γ = (ϕ 1 , ϕ 2 , . . . , ϕ n-1 , ϕ n ), if q is -the upper boundary, i.e., ϕ u = ϕ 1 and ϕ v = ϕ 2 , then γ ′ = (ϕ v , ϕ 2 , . . . , ϕ n-1 , ϕ n ), -the lower boundary, i.e., ϕ u = ϕ n and ϕ v ϕ n-1 , then γ ′ = (ϕ 2 , ϕ 3 , . . . , ϕ n-1 , ϕ v ). Similarly, the procedures for updating the cut for (c) and (d) are given as follows. Let q = {ϕ u , ϕ v } be an event point on the upper boundary, i.e., ϕ u = ϕ 1 . We have two cases:

-when ϕ v goes in R H , i.e., ϕ v ϕ 2 , then γ ′ = (ϕ 1 , ϕ v , ϕ 2 , . . . , ϕ n ); -when the curve ϕ v goes out R H , i.e., ϕ v = ϕ 2 , then γ ′ = (ϕ 1 , ϕ 3 , . . . , ϕ n ). The procedures for (e) and (f) can be considered in the same way. Fig. 10 illustrates he elementary steps for those boundary event points.

Complexity and experiments

Complexity analysis

The space complexity of a DRT graph is proportional to its number of vertices and edges. In absence of constraints, the DRT graph G for an image of size N × N, has a O(N 9 ) complexity (Property 2). This results from the fact that (i) the number of event points of the whole space is O(N 6 ), and (ii) at each elementary step (i.e., for each event point), there are O(N 3 ) vertices generated in the partial graph δG of G [START_REF] Ngo | Combinatorial structure of rigid transformations in 2D digital images[END_REF]. Given one pixel-invariance constraint, some of the potential DRTs become irrelevant. Following the similar proof scheme as above, we can show that the number of event points (i) decreases from O(N 6 ) to O(N 5 ) (due to Property 4 in [START_REF] Ngo | Combinatorial structure of rigid transformations in 2D digital images[END_REF] on tipping curves periodicity), and (ii) at each elementary step, O(N 2 ) vertices are generated instead of O(N 3 ) since, as explained in Sec. 4, δG of G is generated from two graphs G γ a and G γ b of two cuts γ a and γ b sweeping on the planes (a, θ) and (b, θ) respectively. Each of the cut intersects at most O(N 2 ) tipping curves on the plane. Then at each intersection, there are O(N 2 ) vertices generated in δG. This leads to the following property.

Property 10

The DRT graph G associated to a digital image of size N × N under one pixel-invariance constraint has a space complexity of O(N 7 ).

Regarding more complex pixel invariance constraints, we cannot use a similar approach to obtain the theoretical upper bound complexity of G in a FRTS. This is due to the space complexity of G depending on the distance between the involved pixels. Thus, we construct G using our method and we investigate its complexity in practice.

Computational experiments

Experiments were carried out on 2D digital images I of size N × N, for 1, 2, 3, 5 and 10 constraints, to investigate how these constraints affect the complexity of the DRT graph. The first experiment (Fig. 11(a)) validates the theoretical O(N 7 ) space complexity for one given pixel-invariance constraint. Previous works in [START_REF] Amir | Faster two-dimensional pattern matching with rotations[END_REF][START_REF] Thibault | Rotations in 2D and 3D discrete spaces[END_REF] on discrete rotations provide a complexity of only O(N 3 ). However, they consider only a rotation center at a pixel center, while our approach makes no such assumption. In other words, we consider any discrete rotation whose rotation center is located inside a pixel region, due to one pixel-invariance constraint, instead of a pixel center. For this reason, the complexity is increased from O(N 3 ) to O(N 7 ). Given two pixel-invariance constraints, the bounded FRTS R varies randomly with the selected corresponding pixels. Results obtained for an image of size 5 × 5 are shown in Fig. 11(b) for two random pixel choices with some fixed distances. Results for different image sizes are shown in Fig. 11(c). By taking into account the largest complexity for each image size we obtain a worst case complexity O(N 5.5 ) of a DRT graph G in R. We could expect that R is strictly reduced when given supplementary pixel-invariance constraints, i.e., more than two constraints. Nevertheless, the third experiment shows that it is not always true. Let us set two pixel-invariance constraints (in red and blue in Fig. 11(d)), and the associated FRTS R (Fig. 11(e)). A supplementary constraint determined by green pixels in Fig. 11(d) does not reduce R; green dotted lines do not pass through R. Actually (see Fig. 11(f)), there exist two kinds of pixels: one contains some pixels providing no contribution to R such as the green ones, and another contains pixels reduce R such as purple ones. Consequently, the complexity of G depends on given pixel-invariance constraints, but not on the number of constraints.

However, in practice, the more constraints are imposed, the lower the complexity of the DRT graph. This is shown in the experiments for 5 and 10 constraints illustrated in Fig. 11(h) and (i) respectively. Overall there is a downward trend in the numbers of vertices and edges in the DRT graph, though the experimental complexity do not exceed O(N 5.5 ).

This article continued the study initiated in [START_REF] Ngo | Combinatorial structure of rigid transformations in 2D digital images[END_REF] by investigating the effects of geometric constraints on rigid transformations of digital images. In this work, we addressed pixel-invariance constraints which consist of specifying the correspondence between points in an initial (sub)space (of Z 2 ) and pixels in the transformed space. By enforcing correspondence between one or several pairs of pixels, we consequently restrict the feasible transformations into a parameter subspace, called a feasible rigid transformation set (FRTS), in which all such constraints are satisfied. A proposed algorithm allowed us to build a combinatorial structure (namely a graph) for modeling the subdivision of the FRTS on a subset of Z 2 of size N × N. We have theoretically analysed the complexity of the graph with one given pixel-invariance constraint to be O(N 7 ). For more than one constraint, the complexity could not be theoretically calculated. However, using our proposed graph construction method we actually built the experimentally investigated its complexity, which was shown not to exceed O(N 5.5 ).

Note that the FRTS is generated from a finite intersection of regions of the imposed constraints. In practice, due to the precision of pixel-invariance constraints, we may obtain an empty set of feasible rigid transformations induced by these constraints. In order to avoid this problem, one solution can be to change the resolution of the images. Namely, we degrade the image resolution as in [START_REF] Thibault | Rotations in 2D and 3D discrete spaces[END_REF] until we find a non empty and bounded FRTS.

Fig. 1 .

 1 Fig. 1. Tipping surfaces in the 3D parameter space (a, b, θ) (left) and their cross-sections, namely tipping curves, in the 2D planes (a, θ) and (b, θ) (right).

  3 of (a, b, θ) is divided into 3D open cells where the function (a, b, θ) → T abθ = D • T abθ is piecewise constant, bounded by 2D surfaces where it is discontinuous.

Fig. 2 .

 2 Fig. 2. Parameter space subdivided by four tipping surfaces (left) and its DRT graph (right).

  This also leads to the straightforward definition of an equivalence relation on the parameters (a, b, θ) associated to these transformations. In this isomorphic framework, each equivalence class is called a discrete rigid transformation (DRT), and is modeled by 3D open cells bounded by 2D tipping surfaces, which subdivide the parameter space (a, b, θ) (see Fig. 1(a)).

Fig. 3 .

 3 Fig. 3. Rigid transformation sets induced by geometric constraints in continuous (a) and discrete (b,c) frameworks. (a) Transformations with one-point correspondence (red line) and two-point correspondences (red dot). (b,c) Transformations with one-pixel (b) and two-pixels (c) correspondences (red volumes). (d,e) (resp. (f,g)) Cross-sections of (b) (resp. (c)) on the planes (a, θ) and (b, θ) via the use of tipping curves.

Fig. 4 .

 4 Fig. 4. (a) Example of a cut and its graph. (b) Progress of the cut at an event point by which the cut is updated and the corresponding graph is modified.

Fig. 5 .

 5 Fig. 5. Construction of a partial graph δG by combining two graphs G γa and G γ b .

Fig. 6 .

 6 Fig. 6. (a) Progression of the cut γ in the cross-section R H of FRTS R on the plane (a, θ). The initial cut is γ 1= (h + 111 , h - 112 , h + 001 , h - 002 ); when it goes in R H it has become γ 2 = (h + 001 , h + 111 , h - 002 , h - 112 ); when it goes out of R H it becomes γ 3 = (h + 111 , h - 112 , h + 001 , h - 002 ). (b)Example of tipping surfaces (in red) passing R in the parameter space (a, b, θ) and (c) its cross-section R H on the plane (a, θ).

Fig. 7 .

 7 Inside event point classification: a simple intersection if it is generated by only two tipping curves (a), otherwise it is a degeneracy (b,c), i.e., when there are more than two tipping curves.

Fig. 8 .Fig. 9 .

 89 Fig. 8. Updating the graph G γa w.r.t. the change of the cut γ a at a simple intersection.

Fig. 10 .

 10 Illustrations of elementary steps -update γ and generate its graph G γ -for a tipping curve changing (a) an upper or (b) a lower boundary, and going (c) in or (d) out of an upper boundary.

Fig. 11 .

 11 Fig. 11. Experiments for one (a), two (b,c), three (d-g), five (h) and ten (i) pixel-invariance constraints (see Sec. 5.2).

  they intersect, then calculate the following values at the intersection [5, Corollary 1]: sin θ = KQ± +Q 2 , and verify if θ min ≤ θ ≤ θ max , where θ min and θ max are obtained in Sec. 4.2; (iii) if (ii) is verified, then calculate a upper = max

	√ ∆ 1 P 2 +Q 2 and cos θ = KP± P 2 h + √ ∆ 2 pqk ∈U

A quadratic irrational is an irrational number that is a solution of some quadratic equations.

⋆ The research leading to these results has received funding from the French Agence Nationale dela Recherche (Grant Agreement ANR-2010-BLAN-0205 03).