Project topics and materials
Get Complete Project Material File(s) Now! »
Set of Neighborhood Motion Maps
From the above discussion, it is plain that a partition of the remainder range gi by C1(0) \ H depends on the rotation angle = arg(). In order to detect the set of all neighborhood motion maps for r = 1, 2, i.e. equivalence classes of rigid motions U|Nr(p), we need to consider critical angles i.e., angles that lead to topological changes of C1(0) \H. Indeed, from Proposition 3.5, we know that this is equivalent to computing all different frames in the remainder range. Such changes occur when at least one frame has a null area i.e., when at least two parallel line segments which bound a frame have their intersection equal to at least a line segment. To illustrate this issue, let us consider the minimal distance among the distances between all pairs of the parallel line segments in the remainder range. Thanks to rotational symmetries by an angle of k —where k = 4 for the square and k = 6 for the hexagonal grids—and based on the above discussion, we can restrict, without loss of generality, the parameter space of (x, y, ) to C1(0)× 0, k .
Neighborhood Motion Maps Graph
Let us consider as well the dual of the remainder range partitioning—presented in Figure 3.5. In this graph G = {Mr,E}, each node is represented by a neighborhood motion map (or a remainder range frame), while each edge between two nodes corresponds to a line segment shared by adjacent frames in the remainder range. Moreover, each edge is labeled with the color of the corresponding line segment (see Figure 3.4). We note that an edge color denotes the color of a digitization cell in the label map, in the transition between the two corresponding neighborhood motion maps. For instance, let us consider the hexagonal grid and G = {M1,E}. Then if there exists a red horizontal edge between two nodes then we observe a transition of the red neighbor i.e., d = 1, between two neighborhood motion maps connected by this edge. We invite readers to verify in Figure C.1 the neighborhood motion maps of the indexes (−1, 2) and (0, 2).
Non-surjectivity and Non-injectivity of Digitized Rigid Motions
In this section, we identify zones of the remainder range (unions of frames) which exhibit non-injectivity and non-surjectivity of the corresponding digitized rigid motions. This allows us to compare the loss of information induced by digitized rigid motions defined on the square and hexagonal grids. Square grid. Having computed the sets M1 and M2 we can observe that some frames of the remainder range correspond to neighborhood motion maps that exhibit nonsurjectivity or non-injectivity of corresponding digitized rigid motions. Let us first provide some important details about the remainder range frames. Neighborhood motion maps for N2(p) defined on the square grid, which present nonsurjectivity can be found in Appendix B. As can be noted from the figures in Appendix B, such neighborhood motion maps possess at least one non-labeled Gaussian integer w
(white square) that is surrounded by four labeled Gaussian integers at N1(w), whose preimages form a 2 × 2 square (see the neighborhood motion map of the frame (0, 0) for their preimages). For example, see the frames (2,−3), (3,−3), (2,−4) and (3,−4), depicted in Figure B.1. Using this observation and Equations (3.2–3.3) we state the following lemma.
Locally Bijective Digitized Rigid Motions
As seen above, the bijective digitized rigid motions, though numerous, are not dense in the set of all digitized rigid motions. Thus, we may generally expect defects, such as Gaussian integers with two preimages. However, in practical applications, the bijectivity of a given U on the whole Z[i] is not the main issue; rather, one usually works on a finite subset of the plane e.g., a square digital image. The relevant question is then: “given a finite subset S Z[i], is U restricted to S bijective?”. Actually, the notion of bijectivity in this question can be replaced by the notion of injectivity, since the surjectivity is trivial, due to the definition of U that maps S to U(S).
Table of contents :
Abstract
Résumé
Preface
I Digitized Rigid Motions of 2D Discrete Spaces
1 Introduction
2 Basic Notions
2.1 2D Discrete Spaces
2.2 Properties of Gaussian and Eisenstein Integers
2.3 Pythagorean and Eisenstein triples
2.4 Digitization – From C to Discrete Spaces
2.5 Rigid Motions
2.6 Digitized Rigid Motions
2.7 Rational Rotations
2.7.1 Pythagorean Rational Rotations
2.7.2 Eisenstein Rational Rotations
2.7.3 Density of Eisenstein Rational Rotations
3 Local Alterations Induced by Digitized Rigid Motions
3.1 Neighborhood Motion Map
3.2 Remainder Range Partitioning and Neighborhood Motion Maps
3.3 Set of Neighborhood Motion Maps
3.4 Neighborhood Motion Maps Graph
3.5 Non-surjectivity and Non-injectivity of Digitized Rigid Motions
3.6 Preservation of Information
3.7 Future Work and Conclusion
4 Bijective Digitized Rigid Motions on Square Grid
4.1 Globally Bijective Digitized Rigid Motions
4.2 Locally Bijective Digitized Rigid Motions
4.2.1 Forward Algorithm
4.2.2 Backward Algorithm
4.3 Finding a Local Bijectivity Angle Interval
4.3.1 Hinge Angles for Rigid Motions
4.3.2 An Algorithm for Finding the Local Bijectivity Angle Interval
5 Bijective Digitized Rotations on Regular Hexagonal Grid
5.1 Bijectivity of Digitized Rotations
5.1.1 Set of Remainders
5.1.2 Factorization of Primitive Eisenstein Integers
5.1.3 Reduced Set of Remainders
5.2 Characterization of Bijective Digitized Rotations
5.3 Density of bijective digitized rotations
II Digitized Rigid Motions of 3D Discrete Spaces
6 Introduction
7 Basic Notions
7.1 Rotations in Three Dimensions
7.1.1 Spatial Rotations and Quaternions
7.1.2 Spatial Rotations and Cayley Transform
7.2 Digitized Rigid Motions in Three Dimensions
7.2.1 Transformation Models
7.3 Point Status After Digitized Rigid Motions
7.4 Connected Digital Sets and Neighborhood
8 Characterizing the Bijectivity of 3D Digitized Rotations
8.1 Bijectivity Characterization
8.1.1 Set of Remainders
8.1.2 Dense Subgroups and Non-injectivity
8.1.3 Lipschitz Quaternions and Bijectivity
8.2 An Algorithm for Bijectivity Characterization
8.3 Future work and conclusion
9 Computing 3D Neighborhood Motion Maps
9.1 Motivation: Connectivity Alterations
9.2 Neighborhood Alterations Under Digitized 3D Rigid Motions
9.3 Arrangement of Quadrics
9.3.1 The Problem as Arrangement of Hypersurfaces
9.3.2 Uncoupling the Parameters
9.4 Computing Arrangement of Quadrics in 3D
9.4.1 Bifurcation and Critical Values
9.4.2 Detection of Critical Values
9.4.3 Sorting Critical Values
9.4.4 Sweeping a Set of Quadrics
9.5 Recovering Translation Parameter Values
9.6 Case Study
9.6.1 Combinatorial Issue
9.6.2 Implementation and Experiments
9.7 Future Work and Conclusion
A Neighborhood motion maps for GU1 (4-neighborhood case)
B Neighborhood motion maps for GU2 (8-neighborhood case)
C Neighborhood motion maps for GU1 and their graph
Bibliography
