Publication

Titre

Rotations dans les espaces discrets 2D et 3D

Rotations in 2D and 3D discrete spaces

Détails

Soutenance effectuée le 22 septembre 2010 à 14h30

à L'ESIEE Paris, amphithéatre 260

Cliquez ici pour télécharger la thèse(Anglais, 10Mo, version non finale)

Résumé (fr)

Cette thèse présente une étude sur les rotations dans les espaces discrets en 2 et 3 dimensions. Un espace discret est, par opposition à un espace continu, un espace borné avec un nombre fini de points. En informatique, les espaces continus n'existent pas ; en effet, même l'utilisation de nombres flottants ne permet qu'une approximation grossière du continu. Les données utilisées dans le cadre de l'informatique sont le plus souvent entières. Par exemple, une image numérique n'est composée que de points à coordonnées entières et, pour la couleur, à valeurs entières. De plus l'utilisation des nombres flottants pour approcher le continu pose des problèmes de précision. Pour ces raisons, nous avons choisi durant cette thèse de nous concentrer sur les espaces discrets et de n'utiliser que des entiers durant les calculs.

Dans le domaine de la vision par ordinateur, la rotation est une transformation requise pour de nombreuses applications. Dans la plupart des applications, la rotation utilisée est la rotation euclidienne discrétisée. Les résultats donnés par cette rotation dans les espaces discrets ne sont pas bons car il y a une importante perte d'informations, la qualité visuelle de l'image est dégradée et une partie des propriétés mathématiques de la rotation continue est perdue. Par conséquent avec le développement de l'informatique, le besoin de développer de nouvelles méthodes de rotations adaptées aux espaces discrets s'est fait sentir.

Dans cette thèse, nous nous sommes donc concentrés sur le développement des rotations dans les espaces discrets et sur leur compréhension. Nous nous sommes principalement intéressés aux angles charnières qui représentent la discontinuité de la rotation dans les espaces discrets. En effet, dans ces espaces, effectuer deux rotations d'une image avec deux angles très proches peut donner le même résultat. Cette particularité est capturée par les angles charnières. L'utilisation de ces angles particuliers permet de décrire une rotation qui donne les mêmes résultats que la rotation continue discrétisée sans avoir recours aux calculs flottants. Ces angles permettent aussi de décrire une rotation incrémentale qui décrit toutes les rotations possibles d'une image numérique donnée (chose impossible dans le continu car il y a une infinité de rotations possibles). L'utilisation des angles charnières peut-être étendue dans les espaces discrets en trois dimensions. Pour ce faire, on définit les multi-grilles qui sont des plans de rotations qui contiennent trois ensembles de droites parallèles. Ces droites représentent les discontinuités de la rotation en 3D. Elles servent donc à définir les angles charnières dans les plans de rotations. Les multi-grilles permettent d'obtenir les mêmes résultats en 3D que ceux obtenus en 2D.

Mots clés : Rotation, Rotation discrète, Géométrie discrètes, Angle charnière, Multi-grille.

Abstract (en)

This thesis presents a study on rotations in 2- and 3-dimensional discrete spaces. By opposition to the continuous space, a discrete space is a space with bounds and a finite number of points. In computer science, continuous spaces do not exist; indeed, the floating numbers used to simulate the continuous space only give a crude approximation of the continuous space. Data used in the computer science field are mostly composed of integers. For example, a digital image contains only discrete points with integer coordinates and integer values that encode the color of the point. Moreover, using floating numbers to approach real numbers implies precision problems. For these reasons, we decided, during this thesis, to work in discrete spaces and to use only integers for all computations. In the computer vision field, the rotation is a transformation required for many applications. Most of applications use the Euclidean rotation and then apply the rounding function on the obtained results. The results obtained by using this rotation in discrete spaces are not satisfactory since much information is lost, the visual quality is affected and most of the properties of the continuous rotation are lost. Accordingly, with the expansion of computer science, it is necessary to develop new rotation methods adapted to discrete spaces.

In this thesis, we have chosen to study the rotations in discrete spaces and to improve their understanding. We mainly studied hinge angles that represent the discontinuity of the rotation in the discrete space. Indeed, in discrete space, it is possible to perform two rotations of the same digital image with two angles that are slightly different while obtaining the same result. This particularity of the rotation in discrete space is formalized by hinge angles. Using hinge angles allows us to describe a discrete rotation that gives the same results than the discretized Euclidean rotation, although using only integers during computations. These particular angles also allow the description of incremental rotation that performs all possible rotations of a given digital image. Such an incremental rotation is impossible in continuous space since there is an infinity of continuous rotations. Using hinge angles can also be extended to the rotations in 3-dimensional discrete spaces. The extension requires multi-grids, which consist in rotation planes containing three sets of parallel lines. These parallel lines represent the discontinuities of the rotation in 3D discrete space. Thus they are useful to describe hinge angles in rotation planes. Multi-grids allow us to obtain the same results in 3D discrete rotations as the results obtained in 2D discrete rotations.

This thesis contains five chapters given after an introduction in Chapter 1 to the problematic of discrete spaces and rotations in discrete spaces. Chapter 2 gives a state of the art about discrete rotations in the plane, shows the properties of Euclidean rotations that are lost in discrete spaces and explains which problems arise with the lost of properties. The end of this chapter is a study of rotations in the discrete spaces tiled by triangles or hexagons. Chapter 3 introduces the hinge angles that allow the design of a discrete rotation in the plane and an incremental discrete rotation that computes all possible rotations for a given digital image. Then we propose a method to estimate, for a pair of digital images, the rotation that transforms the first image into the second one. The chapters 4 and 5 are the extension of the results presented in chapter 3 in the 3D discrete space. Chapter 6 presents a study on Pythagorean $n$-tuples. We show that they are dense in any dimensions and we propose a method to find for any $n$-vector a Pythagorean $n$-tuple that approximates this vector. This study is required to obtain the result of Chapters 4 and 5.

Keywords: Rotation, Discrete rotation, Digital geometry, Hinge angle, Multi-grid.