Dans cette thèse, nous nous intéressons à la reconnaissance des primitives discrètes multi-échelles. Nous considérons qu'une primitive discrète multi-échelles est une superposition de primitives discrètes de différentes échelles ; et nous proposons des approches qui permettent de déterminer les caractéristiques d'une primitive discrète ou d'une partie d'une primitive discrète.Nous proposons une nouvelle approche de reconnaissance de sous-segment discret qui se base sur des propriétés portant sur l'ordre des restes arithmétiques de la droite discrète. Nous établissons des liens entre les points d'appuis du sous-segment discret et les points ayant des restes arithmétiques minimaux et maximaux sur la droite discrète. D'après les résultats de nos comparaisons, cette approche se relève être plus efficace que des approches existantes.Nous nous intéressons ensuite à des approches de reconnaissance d'arcs et de cercles discrets par le centre généralisé. Nous étudions le dual de la médiatrice généralisée et proposons de calculer le centre généralisé par des calculs de visibilité dans l'espace dual afin de réduire son temps de calcul. Cette approche est valide aussi bien dans une grille régulière que dans une grille irrégulière isothétique.Finalement, nous nous intéressons à des approches de reconnaissance de droite discrète par la préimage généralisée. Nous utilisons la notion de frontière afin de diminuer le nombre d'éléments rentrant dans le calcul de la préimage généralisée ; ce qui simplifie le calcul et réduit le temps de calcul. Cette approche s'applique aussi dans une grille régulière comme dans une grille irrégulière isothétique. / This thesis is about discrete geometry and particularly recognition of multi-scale discrete primitives. We consider that a multiscale discrete primitive is a superimposition of many discrete primitives of different scales. Then we propose approaches of recognition of discrete primitives or parts of a discrete primitives.Firstly we propose a new approach for the recognition of digital subsegment that is based on properties of the sequence of arithmetic remainders of the digital straight line. We show there are sorne links between the leaning points of the digital subsegment and the points that have the minimal and maximal arithmetic remainders on the digital straight line. Based on the results of comparisons with others approaches, the approach seems more efficient. Secondly we present sorne work on improving digital rings and circles recognition by general circumcenter. We use the dual of the generalized bissector in order to simplify the computation of the intersections of generalized bissectors as a polygon stabbing problem. The dual of the generalized bissector is computed likely for pixels of a regular grid or paves of an irregular isothetic grid. Finaly we present some work on improving digital straight line recogrutlon by generalized preimage. To reduce the number of elements to take into account for the computation of the generalized preimage we introduce the concept of boundary. The approach based on boundary could be used in a regular grid or an irregular isothetic grid.

Les appareils d'acquisition d'image 3D sont désormais omniprésents dans plusieurs domaines scientifiques, dont l'imagerie biomédicale, la science des matériaux ou encore l'industrie. La plupart de ces appareils (IRM, scanners à rayons X, micro-tomographes, microscopes confocal, PET scans) produisent un ensemble de données organisées sur une grille régulière que nous nommerons des données digitales, plus couramment des pixels sur des images 2D et des voxels sur des images 3D. Lorsqu'elles sont bien récupérées, ces données approchent la géométrie de la forme capturée (comme des organes en imagerie biomédicale ou des objets dans l'ingénierie). Dans cette thèse, nous nous sommes intéressés à l'extraction de la géométrie sur ces données digitales, et plus précisément, nous nous concentrons à nous approcher des quantités géométriques différentielles comme la courbure sur ces objets. Ces quantités sont les ingrédients critiques de plusieurs applications comme la reconstruction de surface ou la reconnaissance, la correspondance ou la comparaison d'objets. Nous nous focalisons également sur les preuves de convergence asymptotique de ces estimateurs, qui garantissent en quelque sorte la qualité de l'estimation. Plus précisément, lorsque la résolution de l'appareil d'acquisition est augmenté, notre estimation géométrique est plus précise. Notre méthode est basée sur les invariants par intégration et sur l'approximation digitale des intégrations volumiques. Enfin, nous présentons une méthode de classification de la surface, qui analyse les données digitales dans un système à plusieurs échelles et classifie les éléments de surface en trois catégories : les parties lisses, les parties planes, et les parties singulières (discontinuités de la tangente). Ce type de détection de points caractéristiques est utilisé dans plusieurs algorithmes géométriques, comme la compression de maillage ou la reconnaissance d'objet. La stabilité aux paramètres et la robustesse au bruit sont évaluées en fonction des méthodes de la littérature. Tous nos outils pour l'analyse de données digitales sont appliqués à des micro-structures de neige provenant d'un tomographe à rayons X, et leur intérêt est évalué et discuté. / 3D image acquisition devices are now ubiquitous in many domains of science, including biomedical imaging, material science, or manufacturing. Most of these devices (MRI, scanner X, micro-tomography, confocal microscopy, PET scans) produce a set of data organized on a regular grid, which we call digital data, commonly called pixels in 2D images and voxels in 3D images. Properly processed, these data approach the geometry of imaged shapes, like organs in biomedical imagery or objects in engineering. In this thesis, we are interested in extracting the geometry of such digital data, and, more precisely, we focus on approaching geometrical differential quantities such as the curvature of these objects. These quantities are the critical ingredients of several applications like surface reconstruction or object recognition, matching or comparison. We focus on the proof of multigrid convergence of these estimators, which in turn guarantees the quality of estimations. More precisely, when the resolution of the acquisition device is increased, our geometric estimates are more accurate. Our method is based on integral invariants and on digital approximation of volumetric integrals. Finally, we present a surface classification method, which analyzes digital data in a multiscale framework and classifies surface elements into three categories: smooth part, planar part, and singular part (tangent discontinuity). Such feature detection is used in several geometry pipelines, like mesh compression or object recognition. The stability to parameters and the robustness to noise are evaluated with respect to state-of-the-art methods. All our tools for analyzing digital data are applied to 3D X-ray tomography of snow microstructures and their relevance is evaluated and discussed.

Dans un espace discret, comme l'ensemble des points à coordonnées entières, la modélisation de l'isotropie pose des difficultés théoriques notables. À ce jour, aucune théorie géométrique sur $\ZZ^n$ n'est apte à rendre compte de l'isotropie telle qu'elle est décrite par la géométrie euclidienne. Dans l'optique de contribuer à cette problématique, nous nous intéressons à la conception d'algorithmes capables de donner aux rotations discrètes des propriétés proches de celles de la rotation euclidienne. Ces algorithmes doivent de plus fonctionner à base d'arithmétique entière. Après avoir montré la non-existence de rotation discrète transitive sur $\ZZ^n$, nous introduisons un codage de rotations discrètes que nous relions à la fois à la dynamique symbolique et aux automates cellulaires. Il s'agit alors de mener une étude locale des rotations discrètes. Cette étude se situe au carrefour entre géométrie discrète et systèmes dynamiques symboliques. La pertinence des configurations obtenues est justifiée par l'existence de transducteurs planaires capables d'effectuer des rotations à partir des configurations. Ensuite, afin de réinterpréter ces configurations dans le cadre de la théorie des systèmes dynamiques, nous étendons des notions classiques de cette théorie à la dimension 2. Pour la rotation discrétisée, la dynamique symbolique associée est conjuguée avec un jeu de deux translations orthogonales sur un tore bidimensionnel. Après analyse, nous constatons que les configurations obtenues sont des superpositions de configurations de faible complexité. Cela évoque alors les généralisations planaires des mots sturmiens étudiées entre autres par Valérie Berthé et Laurent Vuillon. Des résultats analogues sont aussi obtenus pour les rotations $3$-transvections. L'analyse les rotations discrètes par le biais de systèmes dynamiques a permis de nombreux résultats : mise en évidence de la quasipériodicité des configurations, calcul de la fréquence des symboles, caractérisation des rotations discrétisées bijectives, ce qui est aussi la réciproque du théorème d'Éric Andrès et Marie-Andrée Jacob. Nous avons aussi étudié les discontinuités du processus de rotation. Ces discontinuités ont lieu pour des angles issus d'un sous-ensemble des angles quadratiques (i.e. les angles charnières). En combinant ces remarques, nous aboutissons à deux algorithmes. Le premier algorithme réalise des rotations sans faire aucun calcul à virgule flottante et sans calculer aucun sinus ni aucun cosinus. Il fonctionne de manière incrémentale et en ordre de complexité optimal. Le second algorithme est une implémentation de la rotation $3$-transvections sur automates cellulaires. D'autres pistes pour la conception d'algorithmes sont mentionnées dans la thèse. En outre, nous nous intéressons aussi aux méthodes substitutives qui engendrent les configurations de rotations. Pour les angles quadratiques, nous montrons que les configurations de rotations sont des entrelacements de configurations autosimilaires; et nous présentons le schéma d'une approche basée sur les graphes de Rauzy pour l'inférence de substitutions planaires. En combinant ces deux approches, nous mettons en avant les éléments essentiels de la démonstration de l'autosimilarité de $C_{\pi/4}$. Les applications potentielles de cette thèse concernent à terme l'implémentation d'algorithmes de rotations pour processeurs graphiques. Elle contribue aussi à l'étude des méthodes algorithmiques pour la modélisation physique en milieu discret de phénomènes isotropes.

Le contexte général de mes activités de recherche est la géométrie discrète. Cette thématique s'intègre, au moins d'un point de vue historique, dans l'analyse de formes dans des images numériques. En effet, de nombreux systèmes d'acquisition de données images fournissent des données organisées sur une grille régulière, appelées données discrètes. Que ce soit pour une visualisation ou pour l'extraction de mesures sur ces objets discrets (paramètres de formes), les axiomes et théorèmes de la géométrie euclidienne ne sont pas directement applicables. Une approche classique consiste à une transposition de ces théorème et mesures dans l'espace discret. Ces différentes re-définitions donnent lieu au paradigme mathématique et informatique qu'est la géométrie discrète. Dans ce contexte, nos contributions portent sur l'analyse des modèles et objets fondamentaux (grille, droite, plan, cercle, ...) permettant la définition d'algorithmes de reconstruction géométrique. Dans un second temps, nous nous sommes intéressés à des algorithmes performants pour l'analyse volumique d'objets discrets (transformation en distance, axe médian,...), ainsi qu'à leurs généralisations.

Cette thèse concerne le développement d'une méthodologie pour la modélisation numérique de chambres réverbérantes à brassage de mode (CRBMs). Ce moyen d'essai est utilisé pour les mesures en immunité et en émission de systèmes électroniques dans le domaine de la compatibilité électromagnétique (CEM). L'objectif de ces travaux consiste à proposer une modélisation numérique qui prend en compte un maximum de caractéristiques réelles des CRBMs. L'outil numérique utilisé pour la résolution des équations de Maxwell est la méthode des différences finies dans le domaine temporel. Les caractéristiques géométriques des équipements présents dans les CRBMs sont retranscrites dans le domaine numérique à l'aide de la géométrie discrète qui contrairement aux mailleurs commerciaux permet de contrôler les propriétés topologiques des maillages tridimensionnels obtenus. Les caractéristiques intrinsèques (le facteur de qualité essentiellement) sont intégrées a posteriori via un filtre spécifique appliqué aux solutions temporelles sans perte. Une étude approfondie de l'influence de la source (position, type....) sur la puissance numérique injectée est également présente. Enfin, ces travaux de thèse se concluent par une confrontation directe entre des résultats numériques et expérimentaux suivant les critères normatifs et statistiques actuels.

Dans un contexte d'exploration et d'exploitation pétrolières, le traitement des données acquises par sismique réflexion requiert une analyse structurale à des fins de modélisation. Cette analyse passe par une phase d'extraction des structures horizontales représentant les empilements géologiques. Les techniques actuelles nécessitent beaucoup de temps et l'attention quasi permanente d'un spécialiste pour réaliser et valider cette opération effectuée structure par structure. De plus, la quantité de données sismiques augmentant rapidement avec l'évolution des techniques d'acquisition, leur traitement représente une charge de travail de plus en plus importante. Dans cette thèse, nous nous proposons d'alléger la phase d'extraction des structures horizontales en réalisant une segmentation presque automatique de ces dernières à l'aide d'outils basés sur des techniques morphologiques et topologiques. Nous présentons également quelques applications s'appuyant sur les structures que nous avons extraites. Ces applications facilitent l'analyse des données 3D en proposant de nouvelles méthodes de calcul d'attributs sismiques à partir des données d'amplitude.

Cette thèse se situe dans le cadre de la géométrie discrète qui constitue l'une des grandes familles de méthodes dédiées à l'analyse automatisée des formes dans les images numériques 2D et 3D. Tous les systèmes d'acquisition d'images fournissent des données organisées sur une grille régulière, appelées données discrètes. Les méthodes que nous nous proposons d'explorer et d'étendre conservent aux données ce caractère discret, par opposition aux techniques qui construisent préalablement un modèle continu approximant les objets à analyser. Nous nous intéressons plus particulièrement à l'étude des courbes et des surfaces discrètes. Dans un premier temps, nous analysons les objets de base que sont les droites, les plans et les cercles discrets. Nous présentons des algorithmes qui permettent de les caractériser et proposons des extensions à ces méthodes. Ensuite, nous étudions des métriques sur les objets discrets comme la transformation en distance euclidienne ou la notion de géodésique discrète. Une approche basée sur la visibilité dans les domaines discrets est introduite. La troisième partie est consacrée à la définition et à l'évaluation d'estimateurs de mesures euclidiennes telles que la longueur, la courbure ou l'aire. Des résultats de convergence de ces estimateurs sont établis. Enfin, nous présentons les applications dans lesquelles ces recherches ont été utilisées~: classification automatisée d'objets archéologiques et analyse des micro-structures d'échantillon de neige.

Dans cette thèse, différents problèmes de la combinatoire des mots et de géométrie discrète sont considérés. Nous étudions d'abord l'occurrence des palindromes dans les codages de rotations, une famille de mots incluant entre autres les mots sturmiens et les suites de Rote. En particulier, nous démontrons que ces mots sont pleins, c'est-à-dire qu'ils réalisent la complexité palindromique maximale. Ensuite, nous étudions une nouvelle famille de mots, appelés mots pseudostandards généralisés, qui sont générés à l'aide d'un opérateur appelé clôture pseudopalindromique itérée. Nous présentons entre autres une généralisation d'une formule décrite par Justin qui permet de générer de façon linéaire et optimale un mot pseudostandard généralisé. L'objet central, le f-palindrome ou pseudopalindrome est un indicateur des symétries présentes dans les objets géométriques. Dans les derniers chapitres, nous nous concentrons davantage sur des problèmes de nature géométrique. Plus précisément, nous don-nons la solution à deux conjectures de Provençal concernant les pavages par translation, en exploitant la présence de palindromes et de périodicité locale dans les mots de contour. À la fin de plusieurs chapitres, différents problèmes ouverts et conjectures sont brièvement présentés.

En informatique, les images sont numériques et donc composées de pixels en 2D et de voxels en 3D. Dans une scène virtuelle 3D, il est impossible de manipuler directement les objets comme des ensembles de voxels en raison du trop gros volume de données. Les objets sont alors polyédrisés, c'est-à-dire remplacés par une collection de facettes. Pour ce faire, il est primordial de savoir décider si un sous-ensemble de voxels peut être transformé en une facette dans la représentation polyédrique. Ce problème est appelé reconnaissance de plans discrets. Pour le résoudre, nous mettons en place un nouvel algorithme spécialement adapté pour les ensembles de voxels denses dans une boite englobante. Notre méthode atteint une complexité quasi-linéaire dans ce cas et s'avère efficace en pratique. En parallèle, nous nous intéressons à un problème algorithmique annexe intervenant dans notre méthode de reconnaissance de plans discrets. Il s'agit de calculer les deux enveloppes convexes des points de Z2 contenus dans un domaine vertical borné et situés de part et d'autre d'une droite quelconque. Nous proposons une méthode de complexité optimale et adaptative pour calculer ces enveloppes convexes. Nous présentons le problème de manière détournée : déterminer le nombre rationnel à dénominateur borné qui approxime au mieux un nombre réel donné. Nous établissons le lien entre ce problème numérique et son interprétation géométrique dans le plan. Enfin, nous proposons indépendamment un nouvel algorithme pour calculer l'épaisseur d'un ensemble de points dans le réseau Zd. Notre méthode est optimale en 2D et gloutonne mais efficace en dimension supérieure

Cette thèse présente une étude sur les rotations dans les espaces discrets en 2 dimensions et en 3 dimensions. Dans le cadre de l'informatique, l'utilisation des nombres flottants n'est pas recommandée du fait des erreurs de calculs que cela implique. Nous avons donc fait le choix de nous concentrer sur les espaces discrets. Dans le domaine de la vision par ordinateur, la rotation est une transformation requise pour de nombreuses applications. L'utilisation de la rotation continue discrétisée donne des résultats de mauvaise qualité. Pour cette raison, il est nécessaire de développer de nouvelles méthodes de rotation adaptées aux espaces discrets. Nous nous sommes principalement intéressés aux angles charnières qui représentent la discontinuité de la rotation dans les espaces discrets. Dans ces espaces, deux rotations d'une image avec deux angles très proches peuvent donner le même résultat, ce qui est capturé par les angles charnières. L'utilisation de ces angles permet de décrire une rotation qui donne les mêmes résultats que la rotation continue discrétisée tout en n'utilisant que des nombres entiers. Ils permettent aussi de définir une rotation incrémentale qui décrit toutes les rotations possibles d'une image digitale donnée. Les angles charnières peuvent être étendus dans les espaces discrets en trois dimensions. Pour cela, on définit les multi-grilles qui sont des plans de rotations contenant trois ensembles de droites parallèles. Elles représentent les discontinuités de la rotation en 3D. Les multi-grilles permettent d'obtenir les mêmes résultats en 3D que ceux obtenus en 2D / This thesis presents a study on rotation in 2 dimensional and 3 dimensional discrete spaces. In computer science, using floating numbers is problematic due to computation errors. Thus we chose during this thesis to work only in discrete space. In the field of computer vision, the rotation is a transformation required for many applications. Using discretized Euclidean rotation gives bad results. Then, it is necessary to develop new rotation methods adapted to the discrete spaces. We mainly studied the hinge angles that represent the discontinuity of the rotation in the discrete space. Indeed, it is possible to perform two rotations of the same digital image with two angles that are slightly different and obtain the same result. This is captured by hinge angles. Using these angles allow us to describe a discrete rotation that gives the same results than the discretized Euclidean rotation without using floating numbers. They also allow describing an incremental rotation that performs all possible rotations of a given digital image. Using hinge angles can also be extended to the rotations in 3 dimensional discrete spaces. The extension requires the multi-grids that are 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 the hinge angles in rotation planes. Multi-grids allow obtaining the same results in 3D discrete rotations than the results obtained in 2D discrete rotations. This thesis presents a study on rotation in 2 dimensional and 3 dimensional discrete spaces. In computer science, using floating numbers is problematic due to computation errors. Thus we chose during this thesis to work only in discrete space. In the field of computer vision, the rotation is a transformation required for many applications. Using discretized Euclidean rotation gives bad results. Then, it is necessary to develop new rotation methods adapted to the discrete spaces. We mainly studied the hinge angles that represent the discontinuity of the rotation in the discrete space. Indeed, it is possible to perform two rotations of the same digital image with two angles that are slightly different and obtain the same result. This is captured by hinge angles. Using these angles allow us to describe a discrete rotation that gives the same results than the discretized Euclidean rotation without using floating numbers. They also allow describing an incremental rotation that performs all possible rotations of a given digital image. Using hinge angles can also be extended to the rotations in 3 dimensional discrete spaces. The extension requires the multi-grids that are 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 the hinge angles in rotation planes. Multi-grids allow obtaining the same results in 3D discrete rotations than the results obtained in 2D discrete rotations