Project topics and materials
Get Complete Project Material File(s) Now! »
From digital geometry to discrete rotations
The rotation is a geometrical transformation that have probably been introduced by the Greeks one or two centuries B.C. for studying astrology. The rotation is inseparable from the Archimedes constant, better-known since the 17th or 18th century as π. Archimedes was the rst to rigorously study π by realizing that he can obtain a lower and a upper bound by inscribing circles in regular polygons and calculating the outer and inner polygons respective perimeter [12].
Between Archimedes, about ve centuries B.C. and the end of the 19 th century, many mathematicians tried to give a good approximation of π or its exact value. The accuracy of the estimation of π quickly increases with the development of mathematics. With the introduction by Liouville of transcendental number in 1844[13] and the demonstration by Lindemann in 1882 that π is one of these numbers [14], we know that π cannot be exactly represented or computed.
The impact of the belonging of π to the transcendental numbers on digital geometry is very important. Indeed, we know that each computation from Zn to Zn using π will give an approximated result. More generally, π is not the only problem of the rotations in discrete space. Particular angles exist that allow rotations to be performed without using π denoted by Pythagorean angles[15]. Whereas, performing rotations using these angles will imply dierent problems that will be explained in Chapter 2. Some methods have been developed in digital geometry in order to solve these problems and to perform rotations in discrete space that keep some of the properties of the Euclidean rotations.
These rotations will be introduced in Chapter 2. However, the method that have been proposed cannot solve all the problems of rotations in discrete space. Each one of them have some properties but none have all the properties of Euclidean rotation. Therefore, during my thesis, we tried to improve the understanding of rotations in discrete space. In the next section, we give a quick overview of the content of this manuscript.
Structure of this manuscript
This manuscript is centered on six chapters. Chapter 1 is nished, so it is useless to introduce it.
Chapter 2 presents a survey on 2D discrete rotations. The rotations in the 2D discrete space have been studied during the last 30 years. However many problems are remaining in the application of rotations in the discrete space. Thus, in Chapter 2, we also introduce and explain these problems. We also present a short study on the rotation in dierent regular grid and show that using other regular grid can give better result than orthogonal grid.
In the Euclidean space, for a given point and center of rotations, there is an innity of dierent rotations of the point around the given center. This is not true in a discrete space as the number of dierent rotations is nite and depends on the distance between the point and the center. Chapter 3 presents a discrete rotation using this property of rotations in the discrete space and then gives a method that estimates the angle of rotation from a given pair of digital images that represent the same object before and after a rotation.
Survey on discrete rotations in the plane
In this section, we present some of the existing discrete rotation according to Denition 2.2. The rst rotation is the rotation by discrete circle, then we present the rotation by Pythagorean line already addressed in previous section. We then present the shear rotation that consist in the decomposition of the rotation into three sheer transforms. Finally, we present the rotation by hinge angles which is the rotation that we mainly studied in this thesis.
Table of contents :
Abstract
Abstract
Acknowledgements
List of Figures
1 Introduction
1.1 Introduction to the rotation problem in Z2
1.2 A quick history of geometry
1.3 Digital geometry
1.4 From digital geometry to discrete rotations
1.5 Structure of this manuscript
2 Rotations in 2D discrete spaces
2.1 Introduction
2.2 Denitions and Properties
2.3 Survey on discrete rotations in the plane
2.3.1 Rotation by discrete circle
2.3.2 Rotation by Pythagorean lines
2.3.3 Shear rotation and quasi shear rotation
2.3.4 Rotation by hinge angles
2.4 Rotation in other grids
2.4.1 Connectivity on the discrete grids
2.4.2 Methodology
2.4.3 Experimental result
2.5 Conclusion
3 2D rotations in a discrete space using hinge angles
3.1 Introduction
3.2 Hinge angles
3.2.1 Denition of hinge angles
3.2.2 Properties related to Pythagorean angle
3.3 Rotation by hinge angles
3.3.1 Computing the lower bound rotation angle for grid point
3.3.2 Computing the lower bound rotation angle for a set of grid points
3.3.3 Digital image rotation by a lower bound rotation angle
3.4 Obtaining admissible rotation angles from two digital images
3.4.1 Setting Rotation Centers
3.4.2 Computing lower and upper bounds of rotation angles from two corresponding point pairs
3.4.3 Incremental computing lower and upper bounds of rotation angles
3.5 Experimental Evaluation using Synthetic Data
3.6 Discussion on practical application to digital images
3.6.1 Synthetic data
3.6.2 Real data
3.7 Conclusion
4 3D Rotations in discrete space using hinge angles
4.1 Introduction
4.2 Hinge angles
4.3 Multi-grids
4.3.1 Denition of multi-grids
4.3.2 Multi-grid line equations
4.3.3 Rational multi-grids
4.3.4 Properties of rational multi-grids
4.4 Hinge angles characterized by a multi-grid
4.4.1 Hinge angles and rational multi-grids
4.4.2 Quintuplet integer representation of hinge angles
4.5 3D discrete rotations around a Pythagorean axis
4.5.1 Comparing hinge angles with integer computations
4.5.2 Upper bound of the number of 3D hinge angles
4.5.3 3D discrete rotations induced by hinge angles
4.5.4 3D incremental discrete rotation
4.6 Conclusion
5 Estimation of rotation between a pair of 3D digital images
5.1 Introduction
5.2 Finding a 3D discrete rotation from a pair of digital images
5.2.1 Approximation of the rotation axis by a 3D Pythagorean vector
5.2.1.1 First step
5.2.1.2 Second step
5.2.2 Approximation of the rotation angle using rational multi-grids
5.3 Conclusion
6 Study on Pythagorean n-tuples
6.1 Introduction
6.2 Pythagorean triples
6.3 Pythagorean quadruples
6.4 Approximation of a given 3D vector by a Pythagorean 3D vector
6.4.1 Generation of Pythagorean quadruples
6.4.2 Approximation methods
6.4.3 Experiments
6.5 Pythagorean n-tuples
6.6 Approximation of an nD vector by an nD Pythagorean vector
6.7 Conclusion
7 Conclusion
7.1 Discrete rotation in 2D
7.2 Discrete rotation in 3D
7.3 Discrete rotation in nD
8 Appendix
Bibliography
