Soutenance mémoire
Les réseaux euclidiens
Les réseaux euclidiens sont des ensembles discrets dont les points sont localisés relativement à une base. Leur répartition est ainsi uniforme et l’ensemble n’a pas besoin d’être défini en extension, la donnée de la base suffit à le caractériser.
Définition 1.1. Soit d ∈ N∗ , la dimension de l’espace. Un réseau euclidien Λ est un sous-groupe discret du groupe (Rd, +), muni de sa loi additive usuelle. Si Λ′est un sous-groupe de Λ, alors Λ′est aussi un réseau euclidien. Nous dirons que Λ′est un sous-réseau de Λ.
Théorème 1.1. Soit Λ ⊆ Rd. Alors, Λ est un réseau euclidien si et seulement s’il existe un ensemble {λ1, . . . ,λr} de vecteurs R-libres de Rd tel que : Λ = Zλ1 ⊕ . . .Zλr,
L’ensemble {λ1, . . . ,λr} est appelé une base du réseau Λ. Toutes les bases de Λ possèdent le même cardinal r, celui-ci est appelé le rang ou la dimension de Λ. Une propriété évidente des réseaux euclidiens vient répondre aux inconvénients formulés sur la définition de notre ensemble discret.
Proposition 1.2 (Invariance par translation). Soit e ∈ Λ. Λ est invariant par translation de e : Λ = Λ ⊕ e.
Cette propriété assure une répartition régulière des éléments ainsi qu’un voisinage identique pour chacun d’entre eux. La Figure 1.3(a) donne un exemple d’un réseau euclidien quelconque ainsi que de ses cellules et relations d’adjacence.
Espaces discrets réguliers
Nous avons aussi représenté sur cette figure les distances euclidiennes d’un élément à ses voisins. Ce sont les cercles en pointillés. Ils nous permettent de nous rendre compte que la solution n’est pas encore idéale. En effet, parmi les éléments adjacents, il existe trois distances différentes. L’idéal serait de pouvoir avoir une adéquation entre distance et voisinage. Il est visible qu’il y a une relation entre la longueur de l’arête commune entre deux cellules adjacentes et la distance entre les éléments associés. Une adéquation distance-voisinage met donc naturellement en jeu des polygones (ou des polytopes en dimension supérieure) réguliers. Deux cas sont possibles, un réseau hexagonal tel celui de la Figure 1.3(b) et un réseau carré comme Figure 1.3(c). Le cas du réseau hexagonal est idéal. Tous les voisins d’un élément sont à une distance identique. Néanmoins, si nous nous focalisons encore une fois sur un traitement informatique, bien que ce soit un ensemble discret, ce type de réseau pose un problème car il met en jeu pour sa construction le nombre irrationnel π. Au contraire, le réseau carré est lui très facilement représentable et manipulable en machine puisque nous pouvons le voir comme le réseau des entiers Z2 dans le plan (ou une homothétie de celui-ci). Son inconvénient est d’être un cas limite, c’est-à-dire qu’une cellule est adjacente à ses voisines aussi par ses sommets. Ce problème peut être en partie contourné en considérant différents types de connexité, par point, par segment,. . . Le réseau carré s’avère un bon compromis entre qualité de la représentation de l’espace continu et simplicité de la manipulation informatique. D’ailleurs, la plupart des formats d’images (PPM, JPEG, PNG,. . .) stockent l’information sous une forme matricielle et la localisation sur les périphériques de sortie se fait sur une matrice écran. Soit d la dimension de l’espace. Soit {e1, . . . , ed} la base canonique de l’espace vectoriel euclidien Rd. Un point x =Pdi=1 xiei ∈ Rd, avec x1, . . . , xd ∈ R, est représenté par (x1, . . . , xd). Nous nommons alors le réseau Ze1 + · · · + Zed l’espace discret. Il correspond à l’ensemble des points à coordonnées entières, Zd. N’importe lequel de ses sous-ensembles est un ensemble discret et un point v de l’espace discret est appelé un pixel dans le plan (contraction de picture element, élément d’image) et un voxel dans le cas des autres dimensions. Les termes pixel et voxel pourront aussi désigner la cellule associée au point discret. Nous allons maintenant nous focaliser sur le cas de l’espace discret à deux dimensions pour introduire les premières propriétés et les premiers objets discrets.
Spécificité du codage des segments de droites discrètes
Parmi les courbes, les plus simples à analyser sont les droites. Plusieurs caractérisations ont été formulées pour identifier un segment de droite discrète, en quelque sorte, des tests de linéarité. Elles utilisent la représentation de l’ensemble discret sous la forme d’un mot obtenu selon le codage de Freeman. Nous ne parlons ici que du cas de segments car d’un point de vue pratique, un ordinateur ne manipulera que des objets finis et donc des segments de droite plutôt que des droites. Dans le cas plus théorique de l’étude des droites elles-mêmes, la notion de droite discrète est très fortement liée à la combinatoire des mots [43] et nous pouvons trouver des résultats sur la caractérisation des droites discrètes et non pas simplement de segments discrets dans [66], par exemple. Le premier critère géométrique a été introduit par A. Rosenfeld dans [75]. Sa propriété de la corde a l’inconvénient de mettre en jeu des points de segments réels.
Définition 1.7 (Propriété de la corde [75]). Un ensemble de pixels E vérifie la propriété de la corde si pour tout couple p et q de pixels de E, et pour tout point m ∈ R2 du segment [pq], il existe un pixel r ∈ E tel que : kr − mk∞ < 1.
Théorème 1.3 ([75]). Une courbe discrète 0-connexe finie est un segment de droite discrète si et seulement si elle vérifie la propriété de la corde et que son code de Freeman n’est constitué que de deux labels consécutifs (par exemple, des 0 et des 1). Plus tard, S. H. Y. Hung introduit une propriété équivalente qui ne met en jeu que les pixels [41].
Décision sur la connexité d’un hyperplan discret
Y. Gérard s’est intéressé à répondre à la première question, à savoir, celle de la connexité d’un hyperplan discret arithmétique rationnel donné [38]. Son approche se base sur des concepts novateurs et notamment la notion de graphes périodiques. Il fournit les bases pour un algorithme qui déterminerait la connexité d’un hyperplan discret arithmétique rationnel en réduisant son graphe de connexité, qui peut être infini, à un autre fini, en le quotientant par un sous-groupe du réseau de ses périodes. Nous n’allons pas nous étendre ici sur la notion et les propriétés des graphes périodiques, mais nous allons transcrire ces résultats directement au niveau des hyperplans discrets arithmétiques rationnels. La principale propriété de ce type d’objets est l’existence d’un réseau de périodes (voir Proposition 2.10), et c’est sur celui-ci que vont reposer tous les résultats qui suivent. Sans perte de généralité, nous considérons dans la suite que le paramètre de translation µ est nul. En effet, dans le cas d’hyperplans rationnels, quel que soit µ, l’hyperplan est simplement une translation de celui dont ce paramètre est nul. Un premier résultat définit les composantes infinies dans les hyperplans discrets arithmétiques rationnels.
Lemme 3.2. Soient P(n, ω) un hyperplan discret arithmétique rationnel. Les voxels v1 et v1 +t, avec t ∈ Zd (t 6= 0) un vecteur de période de P(n, ω) appartiennent à la même composante k-connexe de P(n, ω) si et seulement si elle est infinie.
Étude de la 0-connexité des plans discrets
L’étude précédente se place dans le cas très général de la k-connexité des hyperplans discrets arithmétiques rationnels. D’autres études ont été menées sur un sous-problème, celui des plans discrets arithmétiques rationnels 0-connexes. Plus particulièrement, dans [18], R. Barneva et V. Brimkov isolent des cas où des solutions explicites existent et proposent dans le même temps un algorithme pour traiter le cas général. Ce dernier s’avère malheureusement incorrect comme nous l’avons montré dans [45] (Exemple 3.1, plus loin dans cette section). La différence majeure avec les travaux de Y. Gérard concerne le but recherché. Alors que Y. Gérard cherche à décider de la connexité d’un hyperplan discret arithmétique rationnel donné, R. Barneva et V. Brimkov déterminent la plus petite épaisseur qui rend un plan discret arithmétique rationnel 0-connexe. Dans cette étude, nous considèrerons encore le paramètre de translation µ nul, puisqu’elle se limite aux plans discrets arithmétiques rationnels.
Ensembles discrets minimaux et surfaces discrètes
Une courbe discrète plane est équivalente à un ensemble discret minimal, selon la définition de A. Rosenfeld. Ces objets sont facilement caractérisés de manière locale car ils peuvent être munis d’une paramétrisation, c’est-à-dire d’un parcours, unique à un changement de paramètre près (pixel initial et sens de parcours) [61]. Cela permet d’assurer que la courbe n’est pas en contact avec elle-même – un pixel ne peut être adjacent qu’avec son prédécesseur et son successeur dans la paramétrisation – et donc par des critères locaux, que le plan discret est bien séparé en uniquement deux composantes distinctes par la courbe. La Figure 4.6 fournit une illustration de ces propos. La situation se complique en dimension supérieure. Il est naturel d’espérer que l’ensemble des surfaces (voir des hypersurfaces) discrètes orientables corresponde à celui des ensembles discrets minimaux. Comme pour le passage des droites discrètes aux hyperplans discrets, le cas de la dimension 2 est quelque peu trompeur. Tout d’abord, il n’est pas possible de caractériser les ensembles discrets minimaux par des critères locaux comme l’a montré R Malgouyres [60]. Ils deviennent donc difficile à utiliser en pratique et une définition non locale de surfaces discrètes n’a que peu d’utilité. Ce problème semble lié à l’impossibilité de munir ces ensembles d’une paramétrisation. Des contacts peuvent avoir lieu entre deux parties de la surface sans remettre en cause la minimalité. Au cours d’une analyse locale, il est alors impossible d’assurer qu’il n’y a bien uniquement que deux composantes connexes dans le complémentaire. La Figure 4.7 reprend le contre-exemple proposé par R. Malgouyres dans [60] : l’objet de la Figure 4.7(a) ne peut clairement pas être un ensemble discret 2-minimal puisqu’il sépare l’espace en trois composantes 2-connexes distinctes ; pourtant il est localement équivalent à de tels ensembles comme le montre la Figure 4.7(b). Cet exemple permet de mettre en évidence la principale carence des ensembles discrets minimaux, ils n’assurent pas que la surface discrète n’est pas en contact avec elle-même. Une analyse locale ne fournissant pas l’information sur le nombre global de composantes connexes du complémentaire, il est impossible de déterminer si un tel contact est nécessaire pour avoir deux composantes distinctes ou s’il en crée d’autres.
|
Table des matières
I Géométrie discrète linéaire
1 Bases de topologie discrète plane et droites discrètes
1.1 Espaces discrets
1.1.1 Diagrammes de Voronoï et triangulations de Delaunay
1.1.2 Les réseaux euclidiens
1.1.3 Espaces discrets réguliers
1.2 Relations d’adjacence et connexités discrètes
1.3 Courbes et droites discrètes
1.3.1 Codage des courbes
1.3.2 Spécificité du codage des segments de droites discrètes
1.4 Droites discrètes arithmétiques
1.5 Conclusion
2 Extension en dimensions supérieures
2.1 Définition et premières propriétés
2.2 Hyperplans discrets arithmétiques et propriétés topologiques
2.2.1 Hyperplans discrets naïfs et standard
2.2.2 Relations d’adjacence supplémentaires
2.2.3 Hyperplans discrets k-minimaux
2.3 Hyperplans discrets arithmétiques et périodicité
2.4 Fonctionnalité des hyperplans discrets arithmétiques
2.4.1 Définitions
2.5 Codages symboliques des plans discrets naïfs
2.5.1 Codage par hauteurs
2.5.2 Représentation par restes
2.6 Plans discrets gracieux
2.7 Conclusion
3 Connexité des hyperplans discrets
3.1 État de l’art
3.1.1 Décision sur la connexité d’un hyperplan discret
3.1.2 Étude de la 0-connexité des plans discrets
3.2 Propriétés des hyperplans discrets arithmétiques (d − 1)-connexes
3.2.1 Premières propriétés
3.2.2 Principe de notre approche
3.2.3 Réductions arithmétiques préservant les composantes (d − 1)-connexes
3.2.4 Cas rationnel : réponse algorithmique
3.3 Hyperplans discrets arithmétiques k-connexes
3.4 Conclusion
II Modèles théoriques et pratiques de discrétisation séparants
4 Le passage du continu au discret : la discrétisation
4.1 Schémas de numérisation et modèles de discrétisation
4.1.1 Schémas de numérisations
4.1.2 Modèles de discrétisation
4.2 Propriétés des surfaces discrètes
4.2.1 Ensembles discrets minimaux et surfaces discrètes
4.2.2 Une première définition de surface discrète
4.2.3 Propositions alternatives
4.3 Conclusion
5 Modèles de discrétisation génériques pour les hypersurfaces
5.1 Modèles de discrétisation séparants
5.2 Caractérisation analytique
5.3 Approximations pratiques
5.4 Conclusion et perspectives
6 Applications : Cercles et hypersphères discrètes
6.1 Cercles discrets algorithmiques
6.1.1 Paramètres entiers
6.1.2 Cercles discrets algorithmiques à paramètres non entiers
6.2 Cercles discrets analytiques et épaisseur non constante
6.2.1 Couronnes discrètes analytiques
6.2.2 Cercles discrets analytiques à épaisseur non constante
6.3 Expressivité de nos modèles
6.3.1 Spécialisation et propriétés particulières
6.3.2 Liens avec les hypersphères discrètes analytiques
6.3.3 Cercles discrets 1-séparants
6.3.4 Cercles discrets 0-séparants
6.4 Conclusion et perspectives
Bibliographie
Télécharger le rapport complet
